共识算法 | 米奇妙妙屋

1. Paxos 协议

Paxos 算法由 Leslie Lamport 在 1990 年提出，它是少数在工程实践中被证实的强一致性、高可用、去中心的分布式

协议。Paxos 协议用于在多个副本之间在有限时间内对某个决议达成共识。Paxos 协议运行在允许消息重复、丢失、

延迟或乱序，但没有拜占庭式错误的网络环境中，它利用“大多数 (Majority)机制”保证了 2n+1 的容错能力，即 2n+1

个节点的系统最多允许 n 个节点同时出现故障。

关于节点数量：

2n + 1的意思是节点数量最好是基数，大多数机制要求至少还有超过一半数量的节点正常，这个集群才算正常。假如集群有5个节点，这里就运行至多2个节点挂掉。

假设是偶数个节点，比如说6个，6 / 2 + 1 = 4个，还是之多允许2个节点挂掉，和节点为5个的情况没区别，反而增加了成本，所以节点数最好是奇数。这与后面的投票机制是差不多的。

拜占庭错误与非拜占庭错误

一般地，把出现故障( crash 或 fail-stop，即不响应)但不会伪造信息的情况称为“非拜占庭错误”( non-byzantine fault)或“故障错误”( Crash Fault);

伪造信息恶意响应的情况称为“拜占庭错误”( Byzantine Fault)，对应节点为拜占庭节点。

1.1 核心概念

Proposal：提案（提案 = 提案编号 acceptNumber + 提案值 acceptValue）;
Proposal Number：提案编号;
Proposal Value：提案值。

1.2 参与角色

Proposer（提案者）：处理客户端请求，主动发起提案；
Acceptor (投票者) ：被动接受提案消息，参与投票并返回投票结果给 Proposer 以及发送通知给 Learner；
Learner（学习者）：不参与投票过程，记录投票相关信息，并最终获得投票结果。

在实际的分布式业务场景中，一个服务器节点或进程可以同时扮演其中的一种或几种角色，而且在分布式环境中往往同时存在多个 Proposer、多个 Acceptor 和多个 Learner。

1.3 基础逻辑

Paxos 算法是指一个或多个提案者针对某项业务提出提案，并发送提案给投票者，由投票者投票并最终达成共识的算法。

“达成共识”过程的特点：

可以由一个或多个提案者参与；
由多个投票者参与；
可以发起一轮或多轮投票；
最终的共识结果是一个值，且该值为提案者提出的其中某个值。

1.4 Basic Paxos

分为两个阶段，Prepare 阶段和 Accept 阶段。

1.4.1 Prepare

分为两个环节：

Proposer 发起广播消息给集群中的 Acceptor 发送一个提案编号为 n 的 prepare 提案请求。
Acceptor 收到提案编号为 n 的 prepare 提案请求，则进行以下判断：如果该 Acceptor 之前接受的 prepare 请求编号都小于 n 或者之前没有接受过 prepare 请求，那么它会响应接受该编号为 n 的 prepare 请求并承诺不再接受编号小于 n 的 Accept 请求，Acceptor 向 Proposer 的响应数据包含三部分内容：接受编号 n 的提案状态信息、之前接受过的最大提案编号和相应提案值；如果该 Acceptor 之前接受过至少一个编号大于 n 的 prepare 请求，则会拒绝该次 prepare 请求。

通过以上 prepare 阶段处理流程可以知道：

prepare 请求发送时只包含提案编号，不包含提案值；
集群中的每个 Acceptor 会存储自己当前已接受的最大提案编号和提案值。

假设分布式环境中有一个 Proposer 和三个 Acceptor，且三个 Acceptor 都没有收到过 Prepare 请求，Prepare 阶段示意图如下：

假设分布式环境中有两个 Proposer 和三个 Acceptor，ProposerB 成功发送 prepare 请求，在发送 Accept 请求时出现故障宕机，只成功给 Acceptor1 发送了 accept 请求并得到响应。

当前各个 Acceptor 的状态分别为：

Acceptor1，同意了 ProposerB 发送的提案编号 2 的 Accept 请求，当前提案值为：orange；
Acceptor2，接受了 ProposerB 发送的提案编号 2 的 Prepare 请求；
Acceptor3，接受了 ProposerB 发送的提案编号 2 的 Prepare 请求；

此时 ProposerA 发起 Prepare 请求示意图如下：

说明：

ProposerA 发起 prepare(1)的请求，由于该编号小于提案编号 2，所以请求被拒绝；
ProposerA 发起 prepare(3)的请求，该编号大于编号 2，则被接受，Accetpor1 返回 Promised(3,2,’orange’)，表示接受编号 3 的提案请求，并将之前接受过的最大编号提案（2）和提案值（orange）返回。
Acceptor2 和 Acceptor3 均返回 Promised(3)，表示接受编号 3 的提案请求。

1.4.2 Accept

如果 Proposer 接收到了超过半数节点的 Prepare 请求的响应数据，则发送 accept 广播消息给 Acceptor。如果 Proposer 在限定时间内没有接收到超过半数的 Prepare 请求响应数据，则会等待指定时间后再重新发起 Prepare 请求。

Proposer 发送的 accept 广播请求包含：

accept 请求包含相应的提案号；
accept 请求包含对应的提案值。如果 Proposer 接收到的 prepare 响应数据中包含 Acceptor 之前已同意的提案号和提案值，则选择最大提案号对应的提案值作为当前 accept 请求的提案值，这种设计的目的是为了能够更快的达成共识。而如果 prepare 返回数据中的提案值均为空，则自己生成一个提案值。

Acceptor 接收到 accept 消息后的处理流程如下：

判断 accept 消息中的提案编号是否小于之前已同意的最大提案编号，如果小于则抛弃，否则同意该请求，并更新自己存储的提案编号和提案值。
Acceptor 同意该提案后发送响应 accepted 消息给 Proposer，并同时发送 accepted 消息给 Learner。Learner 判断各个 Acceptor 的提案结果，如果提案结果已超过半数同意，则将结果同步给集群中的所有 Proposer、Acceptor 和所有 Learner 节点，并结束当前提案。

当 Acceptor 之前没有接受过 Prepare 请求时的响应流程图：

当 Acceptor 之前已存在接受过的 Prepare 和 Accept 请求时的响应流程图：

该示例中 prepare 请求返回数据中已经包含有之前的提案值（1,’apple’）和（2,’banana’），Proposer 选择之前最大提案编号的提案值作为当前的提案值。

关于提案编号和提案值：

提案编号

在 Paxos 算法中并不自己生成提案编号，提案编号是由外部定义并传入到 Paxos 算法中的。我们可以根据使用场景按照自身业务需求，自定义提案编号的生成逻辑。提案编号只要符合是“不断增加的数值型数值”的条件即可。

提案值

提案值的定义也完全是根据自身的业务需求定义的。在实际应用场景中，提案值可以是具体的数值、字符串或是 cmd 命令或运算函数等任何形式，比如在分布式数据库的设计中，我们可以将数据的写入操作、修改操作和删除操作等作为提案值。

1.4.3 最终值的选择

Acceptor 每次同意新的提案值都会将消息同步给 Learner，Learner 根据各个 Acceptor 的反馈判断当前是否已超过半数同意，如果达成共识则发送广播消息给所有 Acceptor 和 Proposer 并结束提案。在实际业务场景中，Learner 可能由多个节点组成，每个 Learner 都需要“学习”到最新的投票结果。关于 Learner 的实现，Lamport 在其论文中给出了下面两种实现方式：

选择一个 Learner 作为主节点用于接收投票结果（即 accepted 消息），其他 Learner 节点作为备份节点，Learner 主节点接收到数据后再同步给其他 Learner 节点。该方案缺点：会出现单点问题，如果这个主节点挂掉，则不能获取到投票结果。
Acceptor 同意提案后，将投票结果同步给所有的 Learner 节点，每个 Learner 节点再将结果广播给其他的 Learner 节点，这样可以避免单点问题。不过由于这种方案涉及很多次的消息传递，所以效率要低于上述的方案。

1.4.4 活锁问题

由于 Proposer 每次发起 prepare 请求都会更新编号，那么就有可能出现这种情况，即每个 Proposer 在被拒绝时，增大自己的编号重新发起提案，然后每个 Proposer 在新的编号下不能达成共识，又重新增大编号再次发起提案，一直这样循环往复，就成了活锁。活锁现象就是指多个 Proposer 之间形成僵持，在某个时间段内循环发起 preapre 请求，进入 Accept 阶段但不能达成共识，然后再循环这一过程的现象。活锁现象示例图：

活锁会导致多个 Proposer 在某个时间段内一直不断地发起投票，但不能达成共识，造成较长时间不能获取到共识结果。活锁有可能自行解开，但该过程的持续时间可长可短并不确定，这与具体的业务场景实现逻辑、网络状况、提案重新发起时间间隔等多方面因素有关。

解决活锁问题，有以下两种常见的方法：

当 Proposer 接收到响应，发现支持它的 Acceptor 小于半数时，不立即更新编号发起重试，而是随机延迟一小段时间，来错开彼此的冲突。
可以设置一个 Proposer 的 Leader，集群全部由它来进行提案，等同于下文的 Multi-Paxos 算法。

1.5 Multi-Paxos

首先我们可以设想一下：在多个 Proposer 的环境中最理想的达成共识的交互过程是什么样子的？就是这样一种情

况：集群中的某个 Proposer 发送一次广播 prepare 请求并获得超半数响应，然后再发送一次广播 accept 请求，并获

得超过半数的同意后即达成共识。但现实中多个 Proposer 很可能会互相交错的发送消息，彼此之间产生冲突，而且

在不稳定的网络环境中消息发送可能会延迟或丢失，这种情况下就需要再次发起提案，影响了执行效率。Multi-Paxos

算法就是为了解决这个问题而出现。

Multi-Paxos 算法是为了在保障集群所有节点平等的前提下，依然有主次之分，减少不必要的网络交互流程。Multi-

Paxos 算法是通过选举出一个 Proposer 主节点来规避上述问题，集群中的各个 Proposer 通过心跳包的形式定期监测

集群中的 Proposer 主节点是否存在。当发现集群中主节点不存在时，便会向集群中的 Acceptors 发出申请表示自己

想成为集群 Proposer 主节点。而当该请求得到了集群中的大多数节点的同意后随即该 Proposer 成为主节点。

集群中存在 Proposer 主节点时，集群内的提案只有主节点可以提出，其他 Proposer 不再发起提案，则避免了活锁问

题。由于集群中只有一个节点可以发起提案，不存在冲突的可能，所以不必再发送 prepare 请求，而只需要发送

accept 请求即可，因此减少了协商网络交互次数。

1.6 总结

通过Proposer向Acceptor发起提案，如果Acceptor没有接受过其他提案，那么直接返回当前的提案号并不再接受

编号小于 n 的 Accept 请求，如果接受过其他提案，那么同时也会返回之前接受过的最大提案编号和相应提案值；

如果Proposer收到的回应中有其他提案号，那么他会选择最大的提案号所对应的提案值作为自己的提案值，否则就

自己创建一个提案值。Acceptor收到提案后判断消息中的提案编号是否小于之前已同意的最大提案编号，如果小于

则抛弃，否则同意该请求，并更新自己存储的提案编号和提案值，同时发送响应Proposer和Learner,Learner 判断

各个 Acceptor 的提案结果，如果提案结果已超过半数同意，则将结果同步给集群中的所有节点并结束当前提案。

2. Zab协议

Zab（Zookeeper Atomic Broadcast）是为ZooKeeper协设计的崩溃恢复原子广播协议，它保证zookeeper集群数据的一致性和命令的全局有序性。

2.1 核心概念

集群角色：
- Leader：同一时间集群总只允许有一个Leader，提供对客户端的读写功能，负责将数据同步至各个节点；
- Follower：提供对客户端读功能，写请求则转发给Leader处理，当Leader崩溃失联之后参与Leader选举；
- Observer：就是没有选举权和被选举权的 Follower 。
服务状态：
- LOOKING：当节点认为群集中没有Leader，服务器会进入LOOKING状态，目的是为了查找或者选举Leader；
- FOLLOWING：follower角色；
- LEADING：leader角色；
- OBSERVING：observer角色；
可以知道Zookeeper是通过自身的状态来区分自己所属的角色，来执行自己应该的任务
ZXID：

Zxid是极为重要的概念，它是一个long型（64位）整数，分为两部分：纪元（epoch）部分和计数器（counter）部分，是一个全局有序的数字。

epoch代表当前集群所属的哪个leader，leader的选举就类似一个朝代的更替，你前朝的剑不能斩本朝的官，用epoch代表当前命令的有效性，counter是一个递增的数字。

2.2 选举

Leader发生选举有两个时机：

服务启动的时候当整个集群都没有leader节点会进入选举状态，如果leader已经存在就会告诉该节点leader的信息，自己连接上leader，整个集群不用进入选举状态。
服务运行中，可能会出现各种情况，服务宕机、断电、网络延迟很高的时候leader都不能再对外提供服务了，所有当其他几点通过心跳检测到leader失联之后，集群也会进入选举状态。

选举规则：

首先比较epoch，epoch相等则比较counter，值更大的成为leader，如果都相等，则比较服务的serverId，这个Id是配置zookeeper集群所配置的，所以我们配置zookeeper集群的时候可以把服务性能更高的集群的serverId配置大些，让性能好的机器担任leader角色。

选举流程：

所有节点第一票先选举自己当leader，将投票信息广播出去；
从队列中接受投票信息；
按照选举规则判断是否需要更改投票信息，将更改后的投票信息再次广播出去；
判断是否有超过一半的投票选举同一个节点，如果是选举结束根据投票结果设置自己的服务状态，选举结束，否则继续进入投票流程。

举例：

当集群启动时，所有节点的zxid的相同，所以直接比较serverId，这里假设后启动的节点serverId更大。

第一个启动的节点首先将票投给自己，当第二个节点启动时，首先投票给自己，然后收到第一个节点的投票请求，但是其serverId更大，所以会拒绝为第一个节点投票，同时要求其将票投给自己，第三个节点同理。知道有一个节点的票数超过节点数的一半进而成为leader。

2.3 原子广播

zab在广播状态中保证以下特征

可靠传递: 如果消息m由一台服务器传递，那么它最终将由所有服务器传递。
全局有序: 如果一个消息a在消息b之前被一台服务器交付，那么所有服务器都交付了a和b，并且a先于b。
因果有序: 如果消息a在因果上先于消息b并且二者都被交付，那么a必须排在b之前。

有序性是zab协议必须要保证的一个很重要的属性，因为zookeeper是以类似目录结构的数据结构存储数据的，必须要求命名的有序性。

比如一个命名a创建路径为/test，然后命名b创建路径为/test/123，如果不能保证有序性a命名在b之前，b命令会因为父节点不存在而创建失败。

如上图所示，整个写请求类似一个二阶段的提交。

当收到客户端的写请求的时候会经历以下几个步骤：

Leader收到客户端的写请求，生成一个事务（Proposal），其中包含了zxid；
Leader开始广播该事务，需要注意的是所有节点的通讯都是由一个FIFO的队列维护的；
Follower接受到事务之后，将事务写入本地磁盘，写入成功之后返回Leader一个ACK；
Leader收到过半的ACK之后，开始提交本事务，并广播事务提交信息
从节点开始提交本事务。

有以上流程可知，zookeeper通过二阶段提交来保证集群中数据的一致性，因为只需要收到过半的ACK就可以提交事务，所以zookeeper的数据并不是强一致性。

zab协议的有序性保证是通过几个方面来体现的，

服务之前用TCP协议进行通讯，保证在网络传输中的有序性；
节点之间都维护了一个FIFO的队列，保证全局有序性；
通过全局递增的zxid保证因果有序性，每当一个leader被选举出来后，其会将epoch + 1，并且每次提案counter也会 + 1。

特殊情况：

一共有5个节点，此时S2是leader，当第4条消息来到时，S1最先复制了提案，但是此时S2宕机了，其他节点还未复制到提案，此时进行选举，S1成为leader，因为epoch大家都相等，但是其counter最大（因为刚刚复制了最新的信息），新leader会提交前任未提交完的提案，也就是索引为4的信息。

但是可能S2还未将消息复制给其他节点或者已经复制了的节点宕机了：

此时leader本地写入了索引为6的提案，并且复制给了S0，假如此时S0、S1全部宕机，就会选出S4作为leader，因为S4本地根本没有前任的消息，所以无法提交，然后只有开启自己任期内的工作

假如后面S0、S1又活过来了，S4就会将新消息复制给他们，就会覆盖他们本地的消息，但是这些被覆盖的消息本身未进行提交，所以也无所谓。

2.4 状态流转

服务在启动或者和leader失联之后服务状态转为LOOKING；
如果leader不存在选举leader，如果存在直接连接leader，此时zab协议状态为ELECTION；
如果有超过半数的投票选择同一台server，则leader选举结束，被选举为leader的server服务状态为LEADING，其他server服务状态为FOLLOWING/OBSERVING；
所有server连接上leader，此时zab协议状态为DISCOVERY；
leader同步数据给从节点，使各个从节点数据和leader保持一致，此时zab协议状态为SYNCHRONIZATION；
同步超过一半的server之后，集群对外提供服务，此时zab状态为BROADCAST。

可以知道整个zookeeper服务的工作流程类似一个状态机的转换，而zab协议就是驱动服务状态流转的关键。

3. Raft协议

3.1 复制状态机

Raft协议可以使得一个集群的服务器组成复制状态机，在详细了解Raft算法之前，我们先来了解一下什么是复制状态机。一个分布式的复制状态机系统由多个复制单元组成，每个复制单元均是一个状态机，它的状态保存在一组状态变量中，状态机的变量只能通过外部命令来改变。简单理解的话，可以想象成是一组服务器，每个服务器是一个状态机，服务器的运行状态只能通过一行行的命令来改变。每一个状态机存储一个包含一系列指令的日志，严格按照顺序逐条执行日志中的指令，如果所有的状态机都能按照相同的日志执行指令，那么它们最终将达到相同的状态。因此，在复制状态机模型下，只要保证了操作日志的一致性，我们就能保证该分布式系统状态的一致性。

在上图中，服务器中的一致性模块(Consensus Modle)接受来自客户端的指令，并写入到自己的日志中，然后通过一致性模块和其他服务器交互，确保每一条日志都能以相同顺序写入到其他服务器的日志中，即便服务器宕机了一段时间。一旦日志命令都被正确的复制，每一台服务器就会顺序的处理命令，并向客户端返回结果。

为了让一致性协议变得简单可理解，Raft协议主要使用了两种策略。一是将复杂问题进行分解，在Raft协议中，一致性问题被分解为：leader election、log replication、safety三个简单问题；二是减少状态空间中的状态数目。下面我们详细看一下Raft协议是怎样设计的。

3.2 Raft一致性算法

在Raft体系中，有一个强leader，由它全权负责接收客户端的请求命令，并将命令作为日志条目复制给其他服务器，在确认安全的时候，将日志命令提交执行。当leader故障时，会选举产生一个新的leader。在强leader的帮助下，Raft将一致性问题分解为了三个子问题：

leader选举：当已有的leader故障时必须选出一个新的leader。
日志复制：leader接受来自客户端的命令，记录为日志，并复制给集群中的其他服务器，并强制其他节点的日志与leader保持一致。
安全safety措施：通过一些措施确保系统的安全性，如确保所有状态机按照相同顺序执行相同命令的措施。

3.2.1 基本概念

一个Raft集群拥有多个服务器，典型值是5，这样可以容忍两台服务器出现故障。服务器可能会处于如下三种角色：leader、candidate、follower，正常运行的情况下，会有一个leader，其他全为follower，follower只会响应leader和candidate的请求，而客户端的请求则全部由leader处理，即使有客户端请求了一个follower也会将请求重定向到leader。candidate代表候选人，出现在选举leader阶段，选举成功后candidate将会成为新的leader。可能出现的状态转换关系如下图：

从状态转换关系图中可以看出，集群刚启动时，所有节点都是follower，之后在time out信号的驱使下，follower会转变成candidate去拉取选票，获得大多数选票后就会成为leader，这时候如果其他候选人发现了新的leader已经诞生，就会自动转变为follower；而如果另一个time out信号发出时，还没有选举出leader，将会重新开始一次新的选举。可见，time out信号是促使角色转换得关键因素，类似于操作系统中得中断信号。

在Raft协议中，将时间分成了一些任意长度的时间片，称为term，term使用连续递增的编号的进行识别，如下图所示：

每一个term都从新的选举开始，candidate们会努力争取称为leader。一旦获胜，它就会在剩余的term时间内保持leader状态，在某些情况下(如term3)选票可能被多个candidate瓜分，形不成多数派，因此term可能直至结束都没有leader，下一个term很快就会到来重新发起选举。

term也起到了系统中逻辑时钟的作用，每一个server都存储了当前term编号，在server之间进行交流的时候就会带有该编号，如果一个server的编号小于另一个的，那么它会将自己的编号更新为较大的那一个；如果leader或者candidate发现自己的编号不是最新的了，就会自动转变为follower；如果接收到的请求的term编号小于自己的当前term将会拒绝执行。

server之间的交流是通过RPC进行的。只需要实现两种RPC就能构建一个基本的Raft集群：

RequestVote RPC：它由选举过程中的candidate发起，用于拉取选票
AppendEntries RPC：它由leader发起，用于复制日志或者发送心跳信号。

3.2.2 选举过程

Raft通过心跳机制发起leader选举。节点都是从follower状态开始的，如果收到了来自leader或candidate的RPC，那它就保持follower状态，避免争抢成为candidate。Leader会发送空的AppendEntries RPC作为心跳信号来确立自己的地位，如果follower一段时间(election timeout)没有收到心跳，它就会认为leader已经挂了，发起新的一轮选举。

选举发起后，一个follower会增加自己的当前term编号并转变为candidate。它会首先投自己一票，然后向其他所有节点并行发起RequestVote RPC，之后candidate状态将可能发生如下三种变化:

赢得选举,成为leader: 如果它在一个term内收到了大多数的选票，将会在接下的剩余term时间内称为leader，然后就可以通过发送心跳确立自己的地位。(每一个server在一个term内只能投一张选票，并且按照先到先得的原则投出)
**其他server成为leader：**在等待投票时，可能会收到其他server发出AppendEntries RPC心跳信号，说明其他leader已经产生了。这时通过比较自己的term编号和RPC过来的term编号，如果比对方大，说明leader的term过期了，就会拒绝该RPC,并继续保持候选人身份; 如果对方编号不比自己小,则承认对方的地位,转为follower.
选票被瓜分,选举失败: 如果没有candidate获取大多数选票, 则没有leader产生, candidate们等待超时后发起另一轮选举. 为了防止下一次选票还被瓜分,必须采取一些额外的措施, raft采用随机election timeout的机制防止选票被持续瓜分。通过将timeout随机设为一段区间上的某个值, 因此很大概率会有某个candidate率先超时然后赢得大部分选票.

3.2.3 日志复制

一旦leader被选举成功，就可以对客户端提供服务了。客户端提交每一条命令都会被按顺序记录到leader的日志中，每一条命令都包含term编号和顺序索引，然后向其他节点并行发送AppendEntries RPC用以复制命令(如果命令丢失会不断重发)，当复制成功也就是大多数节点成功复制后，leader就会提交命令，即执行该命令并且将执行结果返回客户端，raft保证已经提交的命令最终也会被其他节点成功执行。leader会保存有当前已经提交的最高日志编号。顺序性确保了相同日志索引处的命令是相同的，而且之前的命令也是相同的。当发送AppendEntries RPC时，会包含leader上一条刚处理过的命令，接收节点如果发现上一条命令不匹配，就会拒绝执行。

在这个过程中可能会出现一种特殊故障：如果leader崩溃了，它所记录的日志没有完全被复制，会造成日志不一致的情况，follower相比于当前的leader可能会丢失几条日志，也可能会额外多出几条日志，这种情况可能会持续几个term。如下图所示：

在上图中，框内的数字是term编号，a、b丢失了一些命令，c、d多出来了一些命令，e、f既有丢失也有增多，这些情况都有可能发生。比如f可能发生在这样的情况下：f节点在term2时是leader，在此期间写入了几条命令，然后在提交之前崩溃了，在之后的term3中它很快重启并再次成为leader，又写入了几条日志，在提交之前又崩溃了，等他苏醒过来时新的leader来了，就形成了上图情形。在Raft中，leader通过强制follower复制自己的日志来解决上述日志不一致的情形，那么冲突的日志将会被重写。为了让日志一致，先找到最新的一致的那条日志(如f中索引为3的日志条目)，然后把follower之后的日志全部删除，leader再把自己在那之后的日志一股脑推送给follower，这样就实现了一致。而寻找该条日志，可以通过AppendEntries RPC，该RPC中包含着下一次要执行的命令索引，如果能和follower的当前索引对上，那就执行，否则拒绝，然后leader将会逐次递减索引，直到找到相同的那条日志。

然而这样也还是会有问题，比如某个follower在leader提交时宕机了，也就是少了几条命令，然后它又经过选举成了新的leader，这样它就会强制其他follower跟自己一样，使得其他节点上刚刚提交的命令被删除，导致客户端提交的一些命令被丢失了，下面一节内容将会解决这个问题。Raft通过为选举过程添加一个限制条件，解决了上面提出的问题，该限制确保leader包含之前term已经提交过的所有命令。Raft通过投票过程确保只有拥有全部已提交日志的candidate能成为leader。由于candidate为了拉选票需要通过RequestVote RPC联系其他节点，而之前提交的命令至少会存在于其中某一个节点上,因此只要candidate的日志至少和其他大部分节点的一样新就可以了, follower如果收到了不如自己新的candidate的RPC,就会将其丢弃.大致理解为先看term，再看index。

还可能会出现另外一个问题, 如果命令已经被复制到了大部分节点上,但是还没来的及提交就崩溃了,这样后来的leader应该完成之前term未完成的提交. Raft通过让leader统计当前term内还未提交的命令已经被复制的数量是否半数以上, 然后进行提交.