高可用与共识算法

强一致性、高可用的存储组件是构建现代分布式系统的必要条件，广泛应用于注册中心、配置中心等平台设施中，分布式锁、协调器等等各类场景需求也有相关需求，在该领域有众多知名的开源组件，如etcd、zookeeper、Tikv等等。

共识算法是实现这类组件的关键算法。简单的说共识算法是协调多个节点达成共识的算法，这是构建高可用系统的基石。大部分典型的共识算法都是基于状态复制机来实现的，每个节点都有一个状态机以及一个日志，状态机用于保持一个共识的结果，这样客户端只要连接到任意节点上就可以获取到状态机的内容。而日志是用于保证输入的顺序，只要保证所有日志的提交顺序是一致的则可以保证各个节点的状态机是一直的。

共识算法有很多种，就我知道的有paxos、raft、zab、VR(Viewstamped Replication)等等。paxos以复杂和难以理解著称，通常来说raft是更容易理解的算法，也更容易在工程实践中采用，而且在性能上并没有损失，所以下面我们讨论一下raft的的基本原理和一些要点。 下面的文章主要基于raft的paper整理而成，相关资料可以从https://raft.github.io/获取。

raft算法原理与实现

raft最主要的贡献在于2点，一个是将复杂的分布式算法分解成几个独立的解释和解决的子问题，并且。将状态进行简化，最小程度的考虑必要的问题，这些工作使得raft共识算法成为一种有效的新的方法。广泛的应用于教学和工程实践中： raft算法的基本流程是首先选举出leader，由leader完成日志复刻的功能。如果follower仅仅接受来自leader的日志复制请求，而没有反向的日志流。raft的leader是一个强大的leader。当follower的日志和leader的日志不同时会强制覆盖自己的日志给follower。当leader宕机时，会选出新的leader，来继续任务。

raft讲上述的基本流程拆分成3个部分：选主过程(leader election)、日志复制(log replication)、安全性(safety)加上成员变更（membership changing）。不过在具体讨论这4个部分的内容的过程中我们还是简单的讨论下raft的一些关键模型和概念：

角色和周期

节点的角色

raft的典型节点可以分为3种：follower、candidate、leader。

• follower：所有节点在初始化之后都是follower。follower的职责仅仅是接受来自leader的复制日志的请求，或是在leader宕机时（未在超时时间内接受到心跳信息）成candidate尝试成为leader，亦或是接受到candidate的投票请求时响应改请求
• candidate：当leader宕机时，超过超时时间的follower会转变成candidate，candidater会向集群内的所有机器发送请求投票给自己的请求。
• leader：leader负责日志复制的过程。并且将自己的日志通过心跳发送给其他机器同步日志，所有来自客户端的写请求都会由leader处理，在过半数的机器提交之后就可以返回成功标志给客户端。

任期周期

raft工作流程由一个个任期组成，通常来说任期由2部分组成一部分是选举阶段，在该阶段集群会尝试进行选主，选主如果成功则进入了常规操作阶段。在选举阶段是没办法响应客户端请求的，只有进入常规操作阶段才能正常的提供服务。 当然也会存在没有选出主节点的情况，这时，会开启一个新的任期。此外还有一点需要说明，一个集群内的节点可能在同一时刻处于不同的任期中的，因此任期本身是有编号的，如果节点接受到更高任期节点发送过来的请求则会更新自己的任期并转变成follower。 在raft中，实施上只需要2中rpc，一种是由候选人发出的请求投票信息，用于在选主阶段将请求其他服务器投票给自己，另一种是附加条目请求，由领导人发起，用来复制日志并提供一种心跳机制。

Leader election

raft使用一种从leader到follower的心跳机制来探活机器，如果在一个心跳周期内follower如果没有收到来自leader的心跳，则follower会认为集群内没有leader节点，自动转成candidate并发起投票请求。 在选举过程中follwer会将任期加1，并且转换成candidate持续发送请求，直到下面3个情况发生： （1）赢得半数以上的票数赢得选举。每个服务器会对一个任期投出一张选票，会投票给最先到来的请求。 （2）其他服务器成为领导者，候选人也会接收到其他机器的投票请求rpc，如果接收到投票请求所属的任期小于当前任期，候选人则会承认该请求发送者的领导者地位，并转换成follower，如果rpc所属的任期比自己小就拒绝掉该请求。 （3）一段时间后没有，这种情况下是可能有同时存在多个候选人，因此没有一个候选人获取了大多数人的支持，这种情况下则需要结束当前任期开始一个新的任期。为了避免重复这种现象，rafr使用随机选举超时时间的方法来确保很少发生选票瓜分的情况。 其实这里还涉及到一个选举超时时间的设定。基本上来说raft的算法要求系统满足下面的时间要求： 广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF） 广播时间是节点发送rpc的品能根据rt时间，故障时间通常至少有几个月。因此选项时间大概在几十或者几百毫秒比较合适。

Log replication

领导者接收到的来自客户端的请求后会给在本地日志附加一套新的记录，并且并发的发送该记录给其他机器中。当这条日志条目被安全的复制，领导人会应用这条日志条目到他的状态机中，并且把结果返回给客户端。如果有follower没有返回请求，则leader会不断重试。

每一条日志条目存储一个条状态机指令和从领导人收到这条指令时的任期号。日志中的任期号用来检测是否出现不一致的情况。每条日志也有一个整数索引值表明他的位置。 当一个日志对应的rpc接收到大多数机器的响应则说明该日志已经被提交了，raft会保证已提交的日志会被可用的状态机执行。一旦当前的日志被提交，该条日志之前的所有日志都会被提交。包括有其他领导人创建的、以及此前任期创建的日志。领导人会保持当前被提交的日志的最大索引号，该索引会跟随追加条目的rpc，因此该索引号会被其他服务器提交。 raft的日志具有日志匹配的特性：

• 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。领导人最多在一个任期里在指定的一个日志索引位置创建一条日志条目，同时日志条目在日志中的位置也从来不会改变。
• 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。因为在发送附加日志 RPC 的时候，领导人会把新的日志条目紧接着之前的条目的索引位置和任期号包含在里面。如果跟随者在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝接收新的日志条目。

然而在leader宕机的情况下，附加日志的rpc会不一致。如上图所示，follower的日志可能比leader多或者少，这种情况下leader会强制复制自己的日志，从而简化操作。 为了使得follower和自己的日志一致，领导人必须找到最后2者一致的地方。然后删除从这个点那之后的所有日志。为了找到这个不一致的其实日志，leader在发送追加日志的rpc的时候回针对每个follwer维护一个nextIndex。每当leader进入常规阶段时，会将nextIndex初始化为leader的最后一条日志，会将这个nextIndex给发送给其他follwer。如果follwer和当前机器不一致则会返回失败，而这时leader会把该follwer对应的nextIndex-1，跟随下一次追加日志的rpc发送，直到找到不一致的日志起始点。

Safety

前面的章节里描述了 Raft 算法是如何选举和复制日志的。然而，到目前为止描述的机制并不能充分的保证每一个状态机会按照相同的顺序执行相同的指令。这里需要讨论一些特殊的限制：

选举限制

在基于leader 的一致性算法中，领导人必须存储已经提交的所有日志。为了保证这一点raft的策略是在投票阶段杜绝这种情况。RPC 中包含了候选人的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求。 Raft 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。

提交之前任期内的日志条目

下图描述了一种之前未讨论过的情况

如图的时间序列展示了为什么领导人无法决定对老任期号的日志条目进行提交。在 (a) 中，S1 是leader，部分的复制了索引位置 2 的日志条目。在 (b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处。然后到 (c)，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交。如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志。反之，如果在崩溃之前，S1 把自己主导的新任期里产生的日志条目复制到了大多数机器上，就如 (e) 中那样，那么在后面任期里面这些新的日志条目就会被提交（因为S5 就不可能选举成功）。 这样在同一时刻就同时保证了，之前的所有老的日志条目就会被提交。 为了消除这种场景，Raft 永远不会通过计算副本数目的方式去提交一个之前任期内的日志条目。只有当前任期里的日志条目通过计算副本数目可以被提交；一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。 Cluster membership change

多节点的成员变更

前3个小节的内容基本描述了整个raft的主要内容，但是在工程实践中还有一个问题需要讨论，如果完成节点的配置替换，或者希望新增或者删除节点改如何处理呢？在如上图的情况中，在新旧2个配置的集群中可能会同时存在2个组，分别产生2个leader的情况，违反了safety。 raft的原文中提出了一种2阶段提交的方式：

基本思路是不允许旧配置和新配置同时进行决策，而是在2者之间加入一段Joint Consensus的过渡时期。具体的做法来说：向leader发送一个集群配置变更的请求Cold,new，leader将改日志复制给其他节点，尝试commit，如果失败了就重试，如果commit成功说明大部分节点都有该日志了，这时即使leader宕机了，重新启动的节点也是拥有该节点的。这时leader发送一个Cnew状态变更指令，带到这个指令commit之后就可以只使用新配置来选主了。

Single Cluster MemberShip Change

这里描述的方式虽然可行，但是实践中大部分不会采用这么麻烦的方式，一种策略也是Diego在其博士论文中提出的Single Cluster MemberShip Change，其基本思路就是上问中出现两个leader的根本原因是2个集群的节点不存在重叠，也就是说无法存在一个仲裁者来觉得采用哪个配置。

如果所示，实际上如果每次只变更一个节点，要获得大多数集群的投票新旧集群就必定有相交，Single Cluster MemberShip Change定了一种configuration LogEntry添加到日志，configuration LogEntry代表了集群配置的更新。Diego还论证了configuration LogEntry只要追加到日志就行了，因为如果configuration LogEntry没有被提交其影响也仅仅是系统配置回滚到原始配置而已。 当然这种方式也有问题在于如果前一次的configuration LogEntry还没有完全提交，新一次的configuration LogEntry就被写入了也可能导致老配置被回滚而配置错误，不过一般情况下，配置变更是人为可控的，完全可以等到新配置生效后再进行下一个节点的配置。 不过即使是这样实践中还是有更简单的方式比如etcd就是等到configuration LogEntry完全应用之后再进行下一次配置变更。

raft 语义与概念

最后我们总结一下raft的实现要点

状态

状态	所有服务器上持久化
currentTerm	服务器最新任期号（初始化为 0，持续递增）
votedFor	在当前获得选票的candidateId
log[]	日志条目集；每一个条目包含一个用户状态机执行的指令，和收到时的任期号

状态	所有服务器上非持久化
commitIndex	已知的最大的已经被提交的日志条目的索引值
lastApplied	最后被应用到状态机的日志条目索引值（初始化为 0，持续递增）

状态	所有服务器上非持久化
nextIndex[]	对于每一个服务器，需要发送给他的下一个日志条目的索引值（初始化为leader最后索引值加一）
matchIndex[]	对于每一个服务器，已经复制给他的日志的最高索引值

rpc协议

追加日志

请求参数	解释
term	leader的任期号
leaderId	leader的 Id，以便于跟随者重定向请求
prevLogIndex	新的日志条目紧随之前的索引值
prevLogTerm	prevLogIndex 条目的任期号
entries[]	准备存储的日志条目（表示心跳时为空；一次性发送多个是为了提高效率）
leaderCommit	领导人已经提交的日志的索引值

返回参数	解释
term	当前的任期号，用于领导人去更新自己
success	跟随者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志时为真

接收者实现：

1. 如果 term < currentTerm 就返回 false
2. 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配，则返回 false
3. 如果已经存在的日志条目和新的产生冲突（索引值相同但是任期号不同），删除这一条和之后所有的
4. 附加日志中尚未存在的任何新条目
5. 如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个

请求投票

请求参数	解释
term	leader的任期号
candidateId	请求选票的候选人的 Id
lastLogIndex	候选人的最后日志条目的索引值
lastLogTerm	候选人最后日志条目的任期号

返回参数	解释
term	当前的任期号，用于领导人去更新自己
voteGranted	候选人赢得了此张选票时为真

接收者实现：

1. 如果term < currentTerm返回 false
2. 如果 votedFor 为空或者为 candidateId，并且候选人的日志至少和自己一样新，那么就投票给他

规则

所有服务器：

• 如果commitIndex > lastApplied，那么就 lastApplied 加一，并把log[lastApplied]应用到状态机中
• 如果接收到的 RPC 请求或响应中，任期号T > currentTerm，那么就令 currentTerm 等于 T，并切换状态为跟随者 follower：
• 响应来自候选人和领导者的请求
• 如果在超过选举超时时间的情况之前都没有收到领导人的心跳，或者是候选人请求投票的，就自己变成候选人 candidate：
• 在转变成候选人后就立即开始选举过程
  • 自增当前的任期号（currentTerm）
  • 给自己投票
  • 重置选举超时计时器
  • 发送请求投票的 RPC 给其他所有服务器
• 如果接收到大多数服务器的选票，那么就变成领导人
• 如果接收到来自新的领导人的附加日志 RPC，转变成跟随者
• 如果选举过程超时，再次发起一轮选举 leader：
• 一旦成为领导人：发送空的附加日志 RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以阻止跟随者超时
• 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端
• 如果对于一个跟随者，最后日志条目的索引值大于等于 nextIndex，那么：发送从 nextIndex 开始的所有日志条目：
  • 如果成功：更新相应跟随者的 nextIndex 和 matchIndex
  • 如果因为日志不一致而失败，减少 nextIndex 重试
• 如果存在一个满足N > commitIndex的 N，并且大多数的matchIndex[i] ≥ N成立，并且log[N].term == currentTerm成立，那么令 commitIndex 等于这个 N

约束和特性

请求参数	解释
选举安全特性	对于一个给定的任期号，最多只会有一个领导人被选举出来
领导人只附加原则	对于一个给定的任期号，最多只会有一个领导人被选举出来领导人绝对不会删除或者覆盖自己的日志，只会增加
日志匹配原则	如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间全部完全相同
领导人完全特性	如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中
状态机安全特性	如果一个leader已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志

参考资料

• raft 相关资料
• 论文中文翻译
• 博士论文