In Search of an Understandable Consensus Algorithm

Raft算法[2]是一致性新晋的热门选手。Raft在一些方面和Viewstamped Replication[4]相似。Raft也有一它自己的特点[1,3]:

1. 强领导者: Raft中领导者的地位更高，日志条目指由leader发送给其它部分。这个方式更加简单且易于理解；
2. 领导选举: Raft在领导选举中使用了一随机的计数器，这在解决领导选举的冲突时会更加有效；
3. 成为变更: Raft在成员变更时使用了一种新的joint consensus方法，这使得及时在成员变更时Raft也能工作。

Raft存在以下概念: Leader: 通常情况下，系统中只有一个leader，Follower: 通常情况下，出leader之外的都是follower。 Candidate: 领导人选举时的一种身份状态。Term: 一个成员担任领导人的这段时间，算法中会用一个递增的数字(任期号)表示。Raft主要分为3个部分: 1. 领导选举; 2. 日志复制；3. 安全性。

领导选举

到Follower发现自己和Leader之间的心跳出现问题时，它就会启动一次新的选举。Foller首先要递增它当前的任期号，然后转变自己为Candidate状态，然后并行地向其它成员发送投票请求，知道以下情况发生然后停止: 1. 它赢得了选举; 2. 其它成员成为Leader，3. 一段时间过后没有选举出领导人。

当一个Candidate获得半数以上的选票时，它就赢得了选举。每个领导者只会对一个任期号的第一个投票请求投票。在赢得选举之中，就会向其它成员发送消息来确定自己的地位。在等待投票的时候，它就可能收到其它成员的投票的请求，如果这个请求中的任期号比自己当前的任期号，那么它就会投这一票并回到Follower的状态，否则，拒绝请求。这里可能发生的一种情况时几个候选人争夺Leader位置导致无法选举出Leader，Raft使用的解决方案时选举超时的时间从一个时间区间内随机选择(比如150ms ～ 300ms)，

日志复制

对于Leader处理的每一条记录，它都会把这条记录追加到自己的日志里面，然后向所有的Follower发送消息，要求他们复制这条记录，当确认这条记录被一半以上的称为保存之后，Leader向客户端返回成功，对于没有及时回复Leader的Follower，Leader会一致重试指到所有的Follower都保存了所有的日志。日志在被复制到多数的成员中之后，Leader就会提交这个日志，同时这日志之前的所有的日志也会被提交。日志在每个成员都是顺序保存的。Raft维护日志有以下的特点:

1. 如果不同的日志中的两个条目有相同的索引和任期号，那么它们就保存了相同的内容；
2. 如果不同的日志中的两个条目有相同的索引和任期号，那么它们之前的所有条目也相同。

对领导选举的限制

​ 不同于其它的一致性算法(包括Viewstamped Replication)一个成员可以被选举为Leader，及时它没有保存所有的已经提交的日志条目。这些算法就需要额外的机制来让新的Leader获取到这个日志。而Raft不同，它可以保证所有的之前的任期号内的已经提交的日志都已经保存在新的Leader之中。 ​ Raft使用的方式是一个成员只能在已经包含了所有的已经提交的日志条目的情况下才能赢得选举。一个成员要想赢得选举，它必须获得半数以上的选票，这些选票中一定会有一个成员保存了所有的已经提交的条目，这样就可以达到阻止没有包含所有的已经提交的日志的成员被选举为Leader。Raft通过比较两份日志中最后一条日志条目的索引值和任期号来定义谁比较新，如果最后的条目的任期号不同，那么任期号大的比较新，如果任期号相同，那么索引更大的比较新。在Raft中，Leader处理日志的一些不一致时直接通过强制要求Follower复制自己的日志来解决的，有冲突的日志会被覆盖(只会是那些没有提交的日志)。

安全性

关于Raft的安全性的证明，论文[1]中有详细的描述，这里就不说了。

成员变更

为了保证在成员(配置)变更的时候算法还是安全的，要求这个过程中不能存在一个时间点有两位Leader。但是直接从旧的配置切换到新的配置都不能做出保证，因为不能保证所有成员在同时配置被更新。为了解决这个问题，在Raft中使用的方式是集群先切换到一个过渡的配置，然后在切换到新的配置。这个过度配置称之为共同一致，一旦共同一致被提交，那么系统就可以切换到新的配置之上。这里的共同一致时新老配置的结合:

    1.  日志会被复制给所有新老配置的所有成员；
    2.  新老配置中的成员都可以作为Leader；
    3.  达成一致需要分别在新老配置上获得多数支持。

此外，即使在成员变更的时候，集群依然可以工作。对于新加入的成员，它可能没有保存任何的日志条目，这种情况下追赶上来可能需要一段比较长的时间，Raft使用了一个额外的阶段，在这个阶段之中，新的成员会以没有投票权的身份参与进来，知道这个成员追赶上来。还存在另外一个问题，移除不在新配置中的成员可能扰乱集群。这些成员将不会再接收到心跳，所以当选举超时，他们就会进行新的选举过程。它们会发送拥有新的任期号的投票请求，这样会导致当前的Leader回退成Follower状态。新的Leader最终会被选出来，但是被移除的服务器将会再次超时，然后这个过程会再次重复，导致整体可用性大幅降低。为了解决这个问题，当服务器确认当前Leader存在时，服务器会忽略投票请求，还有当服务器在当前最小选举超时时间内收到一个投票请求，它不会更新当前的任期号或者投出选票。这不会影响正常的选举，但这有利于避免被移除的服务器扰乱，如果Leader能够发送心跳给集群，那么它就不会失去Leader的身份。

日志压缩

这部分旧不赘言了，可以参考论文[1]。

参考

1. In Search of an Understandable Consensus Algorithm (Extended Version).
2. https://en.wikipedia.org/wiki/Raft，维基百科
3. :https://github.com/maemual/raft-zh_cn，Raft论文中文翻译
4. Viewstamped Replication Revisited: http://www.pmg.csail.mit.edu/papers/vr-revisited.pdf