Raft Algorithm

共识算法(consensus algorithm)能够让集群机器在丢失部分成员的情况下仍然能作为一个整体工作，是分布式系统绕不开的话题。Raft算法最早出于教育的目的被提出来，提出者最初的思想就是该算法的易于理解性。本文是对Raft论文及算法的的理解。

Replicated state machines

复制状态机(replicated state machine)指的是分布式系统下所有节点都运行着完全相同的确定状态机，用于解决分布式系统下的容错问题。由于所有节点都运行着同样的状态机，那么对任一节点只要有相同的输入，必要会产生相同的输出。复制状态机是通过日志复制(replicated log)实现的，每个节点上都存储了同样顺序的相同命令，所以每个节点最终都会产生相同的输出。共识算法的任务就是保持复制日志的一致性。

Basic

Raft中的每个节点在任意时刻都处于以下三种状态之一：

• leader: 正常情况下只有一个，负责处理客户的所有请求；
• follower: 被动节点，不发送任何请求，只对leader的candidate的请求做出响应
• candidate: 负责产生新的leader。

在Raft算法中时间被划分成期(term)，每期以选举(election)开始，如果当期没有新leader产生，则会快速开始下一期。期数以一个单增的整数表示，每个节点维护自身的当前期数(current term)，节点之间的通信都会以期数为准。若某节点的CT小于另一节点，则其会将自身的CT更新为大值；若candidate或leader发现自身的CT过期了，则其会自动降级成follower；如果节点收到一个CT过期的请求，则会将其忽略。

Raft使用RPC来通。

Leader election

Raft使用心跳机制来触发选举。服务启动时，所有节点均为follower，并且只要它能接收到来自leader或candidate的有效RPC信息，就会一直保持follower的身份。leader会持续向所有follower发送周期性的心跳(不带日志信息的AppendEntries)来维持领导地位，若follower在一段时间内没有接受到通信(选举超时)，会认为目前无leader并开始leader选举。

开始选举时，follower增加其C值并转为candidate，投票给自己并且对集群中的其他节点发送RequestVote，candidate状态会一直保存，除非下面三件事的其中之一发生：a.其赢得选举，b.其他节点成为leader，c.当期没有产生leader。

• candidate只有收到超过半数的投票才能成为leader，并且每个节点最多只能为一个candidate投票，并且投票遵守先到先服务原则。当candidate成为leader后会对所有节点发送心跳信息，阻止新的选举。
• 在等待投票期间，candidate可能会收到其他节点的心跳信息。如果该心跳信息的CT值大于自身，则说明该leader身份是有效的，candidate会自动降级为follower，否则的话会无视过期的心跳。
• 若当期没有产生leader，那么candidate的身份会过期，增加自身CT值等待新一轮选举。容易发现，若没有额外的管制措施的话，有可能某一时刻有多个节点称为candidate，永远也无法产生leader。Raft使用随机选举计时器来确保任意时刻仅有少数几个节点开启选举拉票。

Log replication

产生leader之后，其会负责处理客户的请求。每条客户请求都包含一条需要在复制状态机上执行的命令，leader会将该命令添加到日志中形成记录，然后给所有节点发送AppendEntries要求复制该记录。当记录被安全复制后，leader命令状态机执行该记录并给客户返回结果。若follower挂掉或者通信环境不佳，则leader会一直持续发送AppendEntries。每条日志记录包括状态机命令、期数和日志索引。若leader生成的一条日志被超过半数节点所复制，则称该日志为已提交(committed)，提交状态的日志会被leader送入状态机执行。leader会记录提交日志的最大索引，并将其随AppendEntries发送给所有节点使其知晓，从而维护个节点状态机的执行进度。

从设计角度来说，各节点中的日志记录必须满足以下两条性质：

• 如果不同日志中的两条记录拥有相同的索引与期数，则它们存储了相同的命令；
• 如果不同日志中的两条记录拥有相同的索引与期数，则它们之前的所有日志完全相同。

通俗地说就是各节点之间日志记录在某一时间点的一致性。但是由于leader的频繁变更，日志的一致性需要额外的措施来进行维护。

Raft算法解决一致性问题的方法很粗暴，直接规定以当前leader的日志为准，将leader的日志复制到所有follower中。leader会为每个follower维护一个nextIndex值，指代leader将要发送给follower的下一条日志索引，新leader上位时该值全被重置成新leader最后一条日志之后的索引(在上图中为1111)。如果有follower存在不一致，则下一次AppendEntries的一致性检查会失败，leader会减少nextIndex并重发AppendEntries，最终会找到与该follower日志保持一致的位置，将该位置之后的日志复制到follower即可。该机制保证了leader的仅追加(append-only)属性。

Safety

上节说的是各节点在存储上的一致性，然后还需要机制来保证各节点状态机在执行上的一致性，这就需要保证任何时期的leader都包含之前时期所提交过的所有记录。Raft算法处理这一问题的方法同样很简单，增加选举限制：并不是任意节点都能被选举为leader，除非该节点包含所有已提交的记录。该限制由RequestVote实现，在RequestVote包含了candidate的日志信息，follower接收到投票请求时，会比较自身日志与candidate日志的时效性，其优先级为term>index，若candidate的日志信息已过时，follower会拒绝投票。

另一个问题是上任的遗留提交问题，有可能出现这样一种情况，某leader在任期间已将一条命令复制到半数节点上，但是还未来得及提交就挂了，该命令可能会被新任leader的新命令所覆盖。然后面临的问题是，上任leader副本超过半数的命令应不应该提交？(待补充，这里没太看懂)

Availability

为了保证Raft系统的可用性，在时间上有一定要求：

其中boradcastTime为节点之间的通信时间，MTBF为节点的平均故障时间。这很好理解，如果选举超时比节点之间的通信时间还要短，那么任何candidate都会在收到投票之前就超时降级；如果选举超时比节点平均故障时间还要长，那么就无法保证leader的稳定性。

Cluster membership changes

(待补充)