Raft

Table of Contents

1 Raft

Raft是一种分布式共识算法。它可以用来替代Paxos算法,而且Raft算法比Paxos算法更易懂、更容易实现。

参考:
In Search of an Understandable Consensus Algorithm (原始论文)
Visualization of Raft: http://thesecretlivesofdata.com/raft/

1.1 问题描述

什么是分布式共识呢?假设有一个分布式key-value存储系统,它有多台(如10台)服务器组成集群共同提供服务,有很多client往这个分布式系统中写数据,如何确保这10台服务器上的数据是一致的?这就是分布式共识问题。

1.2 节点状态(Follower/Candidate/Leader)

每个节点可以处于下面三种状态中的一种:

  • Follower
  • Candidate
  • Leader

1.3 任期(Term)

Raft算法将时间划分成为不同长度的任期(Term),如图 1 所示。任期用连续的数字进行表示。每一个任期的开始都是一次选举(election),一个或多个Candidate会试图成为Leader。如果一个Leader赢得了选举,它就会在该任期的剩余时间担任Leader。在某些情况下,选票会被瓜分,有可能没有选出Leader,那么,将会开始另一个任期,并且立刻开始下一次选举。 Raft算法可保证在给定的一个任期最多只有一个Leader。Leader在它宕机之前会一直保持Leader的状态。

raft_term.png

Figure 1: Time is divided into terms, and each term begins with an election.

2 Raft算法简介

Raft算法的基本描述为:Client只能向Leader发送更新请求(这和Paxos是不同的,在Paxos算法中Client可向任一节点发送更新请求),Leader等待大多数其它节点(即Follower)都完成修改后,再返回给Client,并提交Log。然后Leader负责把已经提交的Log复制到所有其他节点中。

从上面的描述中可知, Raft有两个基本过程:“Leader Election”(决定哪个节点是Leader)和“Log Replication”。

2.1 Leader Election

Leader Election的基本过程为:
1、系统刚开始运行时,大家都是Follower,没有Leader,也没有Candidate;
2、如果Follower在一段时间(称为ElectionTimeout,例如每个结点设置为150ms到300ms内的一个随机数)内没有收到Leader发送的心跳消息,则Follower自己变为Candidate;
3、Candidate发送Request Vote消息给其它节点;
4、其它节点在一个给定任期内有一次投票权,它按照先来先服务(first-come-first-served)的原则把选票投给它收到的第一个Request Vote消息所对应的Candidate;
5、如果Candidate收到大多数节点的选票,则Candidate就变为了Leader;
6、如果选举后,没有一个Candidate收到大多数节点的选票,则重新进行一次选举。

2.2 Log Replication

所有的写操作必需通过Leader进行,接受Client端命令的过程:
1、Leader接受Client请求;
2、Leader把指令追加到日志(日志目前还没有Commit);
3、Leader通过AppendEntries RPC把未提交的日志发送到Follower;
4、Leader收到“大多数”Follower的确认后,才Commit该日志,把日志在状态机中回放,并返回结果给Client;

提交Log到Follower过程:
1、在下一个心跳阶段,Leader再次发送AppendEntries RPC给Follower,告诉它们日志已经Commited;
2、Follower收到Commited日志后,将日志在状态机中回放,这样Follower中数据和Leader中一致。

说明:Raft不是一种强一致性算法,它只需要大多数的Follower确认后就可以返回给Client端。而微软设计的 PacificA 是一种强一致性算法,它需要所有的“从节点”返回成功后“主节点”才返回给Client端。

2.3 Membership Changes

除了前面介绍的“Leader Election”和“Log Replication”过程外,Raft的完整实现一般还应具备处理集群成员的变更(Membership Changes)的情况。

集群成员的变更和成员的宕机与重启不同,因为前者会修改成员个数进而影响到领导者的选取和决议过程,一旦节点个数发生变化,判断“大多数节点”就不同了。当然,可以简单地让运维人员将系统临时下线,修改配置,重新上线,但这往往不可取,因为它会使系统暂时不可用。这里不介绍Raft是如何处理“Membership Changes”的,请参考原始论文。


Author: cig01

Created: <2017-09-02 Sat 00:00>

Last updated: <2018-06-30 Sat 22:30>

Creator: Emacs 25.3.1 (Org mode 9.1.4)