分布式共识之Raft算法

Raft算法属于Multi-Paxos算法，但是做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，在理解和算法实现上都相对容易许多。

etcd集群的共识就采用了Raft算法。从本质上说，Raft算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

如何选举领导者

有哪些成员身份？

领导者（Leader）、跟随者（Follower）和候选人（Candidate） 3种状态。

  • 跟随者：接收和处理来自领导者的消息，当等待领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。

  • 候选人：属于中间态，候选人将向其他节点发送请求投票RPC消息，如果赢得了大多数选票，就晋升当领导者。

  • 领导者：一切以我为准，平常的主要工作内容就是3部分，处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们现在不要发起新的选举”

选举领导者的过程

可以参考这个动图一步一步演示选举的过程：http://thesecretlivesofdata.com/raft/

  1. 假设现在有3个节点，初始状态下，集群中所有的节点都是跟随者的状态。
节点 任期编号 超时时间 身份状态
A 0 150ms 跟随者
B 0 200ms 跟随者
C 0 300ms 跟随者

Raft算法实现了随机超时时间的特性。也就是说，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。各节点超时时间相同可能会导致选举冲突，随机更合适。

因为节点A超时时间最小，它会最先因为没有等到领导者的心跳信息，发生超时。

这个时候，节点A就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票RPC消息，请它们选举自己为领导者。

节点 任期编号 超时时间 身份状态 动作
A 1 150ms 候选人 任期+1，投自己一票，并向其他节点发送投票请求
B 0 200ms 跟随者 如果接收到候选人A的请求投票消息，在编号为1的这届任期内，也还没有进行过投票，那么它将把选票投给节点A，并增加自己的任期编号。
C 0 300ms 跟随者 同B

如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届任期内新的领导者。

节点A当选领导者后，他将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举，篡权。

节点 任期编号 超时时间 身份状态 动作
A 1 150ms 领导者 给其他节点发送心跳消息
B 1 200ms 跟随者 接收心跳
C 1 300ms 跟随者 同B

问题1：节点间如何通讯？

1.请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票；

2.日志复制（AppendEntries）RPC，是由领导者发起，用来复制日志和提供心跳消息。

问题2：什么是任期？

领导者也是有任期的，每个任期由单调递增的数字（任期编号）标识，比如节点A的任期编号是1。任期编号是随着选举的举行而变化的。

  1. 跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期号，比如节点A的当前任期编号为0，那么在推举自己为候选人时，会将自己的任期编号增加为1。

  2. 如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如节点B的任期编号是0，当收到来自节点A的请求投票RPC消息时，因为消息中包含了节点A的任期编号，且编号为1，那么节点B将把自己的任期编号更新为1。

  3. 在Raft算法中约定，如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。比如分区错误恢复后，任期编号为3的领导者节点B，收到来自新领导者的，包含任期编号为4的心跳消息，那么节点B将立即恢复成跟随者状态。

  4. 如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。比如节点C的任期编号为4，收到包含任期编号为3的请求投票RPC消息，那么它将拒绝这个消息。

问题3：选举有哪些规则

  1. 领导者周期性地向所有跟随者发送心跳消息（即不包含日志项的日志复制RPC消息），通知大家我是领导者，阻止跟随者发起新的选举。

  2. 如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举。

  3. 在一次选举中，赢得大多数选票的候选人，将晋升为领导者。

  4. 在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举。

  5. 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。比如节点C的任期编号为3，先收到了1个包含任期编号为4的投票请求（来自节点A），然后又收到了1个包含任期编号为4的投票请求（来自节点B）。那么节点C将会把唯一一张选票投给节点A，当再收到节点B的投票请求RPC消息时，对于编号为4的任期，已没有选票可投了。

  6. 日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的候选人。比如节点B的任期编号为3，节点C的任期编号是4，节点B的最后一条日志项对应的任期编号为3，而节点C为2，那么当节点C请求节点B投票给自己时，节点B将拒绝投票。

如何复制日志？

副本数据是以日志的形式存在的，日志是由日志项组成。日志项是一种数据格式，它主要包含用户指定的数据，也就是指令（Command），还包含一些附加信息，比如索引值（Log index）、任期编号（Term）。

指令指业务数据；索引数字一定是连续的。

日志复制步骤

你可以把Raft的日志复制理解成一个优化后的二阶段提交（将二阶段优化成了一阶段），减少了一半的往返消息，也就是降低了一半的消息延迟。

  1. 接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。

  2. 领导者通过日志复制RPC，将新的日志项复制到其他的服务器。

  3. 当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项应用到它的状态机中。

  4. 领导者将执行的结果返回给客户端。

  5. 当跟随者接收到心跳信息，或者新的日志复制RPC消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没应用，那么跟随者就将这条日志项应用到本地的状态机中。

步骤3以后，领导者并没有再通知跟随者去commit，而是直接返回客户端（二阶段变一阶段）。 那跟随者什么时机去commit呢？ 就是步骤5。

如何实现日志的一致？

  1. 首先，领导者通过日志复制RPC的一致性检查，找到跟随者节点上，与自己相同日志项的最大索引值。也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了。

  2. 然后，领导者强制跟随者更新覆盖的不一致日志项，实现日志的一致。

如何解决成员变更的问题？

如何避免脑裂（集群出现多个主）的问题呢？

举一个例子：

假设我们有一个由节点A、B、C组成的Raft集群，现在我们需要增加数据副本数，增加2个副本，扩展为由节点A、B、C、D、E， 5个节点组成的新集群。

比如在进行成员变更时，节点A、B和C之间发生了分区错误，

  1. 节点A、B组成旧配置中A、B、C中的“大多数”，那么这时A依旧是领导者。

  2. 节点C和新节点D、E组成了A、B、C、D、E 5个节点新配置的“大多数”，它们可能会选举出新的领导者（比如节点C）。那么这时，就出现了同时存在2个领导者的情况。

单节点变更解决脑裂问题

单节点变更，就是通过一次变更一个节点实现成员变更。这样不管旧的集群配置是怎么组成的，旧配置的“大多数”和新配置的“大多数”都会有一个节点是重叠的。 也就是说，不会同时存在旧配置和新配置2个“大多数”。

参考