上次我们分享 CAP 定理时，我们了解到，在网络分区的情况下，我们必须在一致性和可适应性之间做出选择，更具体地说，我们实际上是在强一致性和最终一致性之间做出选择。 在最终一致性方面，我们通常会听到很多东西，比如读修复、写修复、反熵等等。 不过，在强一致性方面，我们经常听到某**发布的强一致性算法，原因是强一致性必须有合理的数学证明，大家都会相信，另外，还需要经过大规模的落地验证才能让大家认可，所以在商业上广泛应用的强一致性算法很少， 如Paxos、Zookeeper's Zab、Raft等。 由于在某些场景下必须保证强一致性，如金融支付、票务系统等，本文将介绍强一致性系列的算法。
如果要谈共识算法，就不得不提 Paxos，因为 Paxos 在刚开始提出的时候缺乏工程实现细节，更像是一个理论框架，导致实现细节看起来像 Paxos 的算法，甚至有人会说世界上只有一种共识算法， 那就是Paxos。这里暂且不赘述 Paxos 的细节，因为 Paxos 算法是出了名的难，导致作者 Lamport 甚至发表了《Paxos Made **》来解释他的算法，但这里提到 Paxos 是因为 Paxos 的重要性在于它有严谨的数学证明，如果你真的想了解 Paxos， 建议先了解 Paxos 家族的其他算法，比如本文要提到的 Raft，最后如果对 Paxos 在工程端的实现感兴趣，可以参考 Google 团队对 Paxos 的实用总结“Paxos Made Live — An Engineering Perspective”。
从所解决的问题类型来看，有两种类型的共识算法，即：拜占庭容错算法（Bezantine Fault Tolerance，BFT）和容错算法（crash fault tolerance, cft）。拜占庭容错算法主要用于求解 if节点作恶在如何同步集群状态的情况下，常见的拜占庭容错算法有pbft; 容错算法主要在处理它们节点故障或遇到网络问题如何保持整个集群的状态一致，常见的容错算法有zab、筏子等。
虽然拜占庭将军问题和拜占庭容错算法PBFT很早就被提出来了，但可以说，直到区块链的出现，才发现了大规模的应用场景，企业内部的大部分应用仍然属于容错算法，比如谷歌的分布式锁系统通过Paxos达成共识——Chubby， 而今天我们就要介绍一下企业中常见的共识机制——筏子。
Raft是斯坦福大学Diego Ongaro的博士生，2013年与他的导师John Ousterhout合著了《寻找一种可理解的共识算法》，并获得了2014年Usenix年度技术会议最佳**奖。
通俗易懂的算法最大的优点就是在工程上不容易出错，这也导致了2013年以后的新系统如果需要强一致性，通常会优先选择筏子，比如2013年的etcd，2015年的influxdb、ipfs和cockroachdb等; 理解的另一个好处是实现相当多，所以可以找到相当多的参考实现，如果在 GitHub 上搜索 paxos 和 raft，会发现有近 3 倍的转发数量相差。
接下来，我将详细介绍 raft 算法，从节点记录的内容（状态、术语、日志和状态机）开始，然后是两个模块——领导者选举和日志复制。
在 raft 中，节点有三种状态，分别是 leader、candidate 和 follower。 木筏属于强大的领导者模型，所以一个 Raft 集群中只能有一个 Leader，其他节点会尊重 Leader，Leader 说什么就做什么，这也导致了 Raft 只能做容错（CFT），而不能处理拜占庭容错（BFT）的事实。
节点状态任期听起来像是只有 leader 才需要的东西，是的，但为了容错，集群中的任何节点都可能在 leader 失败后成为候选节点并参与 leader 选举，因此每个节点都需要知道当前术语。
任期是一个严格递增的数字，而木筏是强势领导模式，所以一个任期内最多只能有一个领导者，只有当领导者在场时，他才能为外部世界提供服务。如下图为例，每届任期从领导人选举开始（深蓝色间隔），然后是集群可以对外服务的时间（浅蓝色间隔），每届任期只有在领导人失败后才会启动下一次选举，因此每个任期的长度不固定， 而且在领导人选举中也可能有任期失败（如第3任期），这意味着任期内没有领导人，因此将直接进行下一轮领导人选举。
术语日志由索引、术语和命令组成，索引是一个严格递增的数字，这里的术语表示在哪个术语期间记录的日志，指令表示要执行哪些操作。 在下图中，红色框表示日志索引 4 出现在项 2 处，指令是将 x 设置为 2。
log 状态机的中文翻译应该是状态机，但这里我们用数据状态机来区分它与节点状态。 Raft 记录了用户通过日志发送的指令，但写入日志只是一个记录，并不意味着数据的状态真的发生了变化，在日志复制一节中，我会解释从添加日志到改变数据状态的条件，但这里我们先知道添加日志与更改数据状态不是一回事
在上一篇文章中提到，CP 模型通常使用两阶段提交（2pc），这就是为什么 raft 将日志与数据状态机分开，写入日志是第一阶段，更改数据状态机是第二阶段。 例如，如果每次添加新日志时都满足更改数据状态的条件，则数据状态也会随着日志中的说明而更改。 
日志和数据状态机的关系我们上面提到节点有三种状态——follower、candidate 和 leader，所以让我们根据不同的节点状态和每个状态可能遇到的事件来了解 Raft Leader 选举的机制。
每个节点在刚开始的时候都是一个跟随者，跟随者会为领导者的心跳信息维护一个计时器，根据计时器的结果，有两种可能：
继续成为追随者：在计时器倒计时到 0 之前，节点在收到来自领导者的心跳消息或候选人投票请求消息 （RequestVote RPC） 时，会重置计时器以继续作为追随者。 成为候选人：当计时器倒计时到0时，没有收到leader心跳消息，也没有收到其他候选人消息，follower认为集群中没有leader，发起选举，成为候选人。 当一个节点从追随者变为候选者时，它会增加一个任期并投票给自己（下图中的节点 a）。 上面提到，一个任期内最多只能有一个领导者，所以当节点发起选举时，任期增加一个，这意味着节点认为上一任期已经结束，进入下一任期。
关注者不会收到心跳消息，不会成为候选人，也不会发送投票请求
一旦节点成为候选节点，它就会向每个节点发送一个 RequestVote RPC，并维护一个选举超时计时器，这可以通过以下三种方式之一发生：
成为领导者：只要候选人获得超过半数的选票，候选节点将状态更改为 leader（下图中的节点 A），并开始向其他节点发送心跳消息。 回退到追随者：当候选人在选举期间发现他们已经有相同任期的领导人或更高任期的领导人时，他们会将其状态改回追随者。 选举超时：当候选人的倒计时时钟为0时，他或她没有办法成为领导者，并且他没有收到其他领导者的心跳消息，此时节点会判断选举失败，开始下一次选举，候选人的任期加一， 代表新学期的开始，并将他的投票数重置为 1，最后再次向其他节点发送投票请求。
当候选人获得多数选票时，他将成为领导者并发送心跳信息
在节点是 leader 的期间，它会继续向其他节点发送心跳消息，以防止其他节点举行选举，但集群也可能因为分区的原因有两个 leader，当分区恢复时，其中一个 leader 发现另一个 leader 的任期比他高， 而任期较低的领导者将返回给追随者，这样集群就会回到只有一个领导者的状态。
leader不断发送心跳，阻止其他节点发起选举以上是某个节点在三种状态下可能遇到的三种情况，接下来是节点遇到投票请求时会如何投票（RequestVote RPC）：
高任期的节点不会被投票为低任期，高日志索引的节点不会被投票给低日志索引的节点只有日志最完整的节点才能成为领导者。如果候选者满足上一点，则节点将优先考虑发送第一个投票请求的候选人。每个节点在一个任期内只能投一票。 如上所述，有一个从日志中更改数据状态机的条件，本节将解释 raft 如何复制日志并更改数据状态机。 由于 raft 是一个强 leader 模型，只有 leader 才能接收到来自客户端的写入请求进行处理，并且在收到客户端的请求后，leader 会将客户端的指令写入日志中，然后将日志复制请求（appendentries rpc）发送到其他节点，只要 leader 收到超过一半的答复是成功的，领导者将执行 log 命令，更改其数据状态机，并回复客户端。
以上情况是理想情况，但实际上，由于各种问题，每个追随者的日志可能会不一致（如下图所示）。 Raft 专为 appendentries RPC 设计不允许直接复制最新的日志，并跳过中间未复制的日志。如下图所示，如果 leader 向第一个跟随者发送索引 8 的日志复制请求，则该跟随者的最新日志最多只有索引 5，因此 leader 的请求将被拒绝，并且 leader 会继续向第一个跟随者发送索引 7 的日志复制请求， 并且 follower 会拒绝，直到 leader 将索引 6 的日志复制请求发送给第一个 follower，follower 会接受它，并从索引 6 重新同步到索引 8。
因此，如果 raft 集群想要对外服务，至少一半的节点必须有完整的日志记录才能对外服务，因为没有完整日志记录的节点无法成功回复最新的日志输入请求。
追随者并没有完全复制领导者的记录，现在我们已经讨论了 Raft 是如何工作的，让我们回到两个 Raft 设计理念——随机选举超时、两阶段提交优化和分区容错。
从追随者到候选人的**，可以发现每个节点的计时器倒计时时间都不一样，所以有些节点成为候选人的速度比较快，而有些节点还在倒计时，这种设计是为了避免节点同时发起投票，导致选票分散，进而造成选举失败， 大家还记得上面说过，每个选举任期只有在有领导之后才能对外任职，所以 RAFT 要尽量保证选举能够成功，为了避免节点频繁发起选举，Raft **建议将超时时间设置在 150 到 300ms 之间。
如上文所述，两阶段提交应该只有在集群完成提交阶段后才会回复客户端，但在 raft 中，只有 leader 会在执行阶段完成后回复客户端，因此等于省略了一半的信息传播，这是对 raft 的优化。 但你一定想知道，追随者如何知道他们什么时候可以进入执行阶段？ 你还记得我们之前提到的心跳消息吗？ 其实心跳信息也是日志拷贝请求信息（appendentries rpc），日志请求信息也会被包括在内leadercommit，代表 leader 最新进入执行阶段的日志索引，所以 leader 在传播心跳消息时，不仅通知关注者不要发起选举，还会复制日志并同步数据状态机的状态，以减少信息量。
在上一篇文章之后，大家会好奇 raft 是如何处理分区容错问题的，以下面这个 ** 为例，在 raft 集群再次分区后，确实可能会产生两个 leader，导致裂脑的问题，但是我们上面提到，日志复制只有在大多数节点响应成功后才会成功发送回客户端， 所以无论分区如何切割，最多只有一个分区，节点超过一半因此，只有一个领导者可以继续对外服务，而其他领导者即使收到客户的请求也只能回复失败。
在分区的情况下，最多只能使用一个分区对外服务如上文所述，两阶段提交可以保持集群中大部分节点的状态一致，实现强一致性。 在拜占庭容错算法PBFT中，将两阶段提交升级为三阶段提交，并改变流程以避免某些节点作恶，导致无法达成共识。
希望读完这篇文章，读者能够理解 raft 算法是如何工作的，Raft 之所以在 2014 年发布后被很多系统迅速采用的原因之一是它易于理解，另一个原因是 raft 在实现中与系统完美解耦，从而可以基于 raft 开发系统， 其他共识机制，如Zookeeper的ZAB，在发布之初是针对Zookeeper的。因此，其他系统更难在zab之上开发。
各种语言的 raft 教材和实现版本很多，如果想了解更多，建议直接阅读 **如果觉得直接阅读太难，也可以观看 raft 作者在伊利诺伊大学亲自讲解 raft** 最后，如果想深入研究源码研究， 您可以研究 HashiCorp 的版本，因为此版本已在 Consul、IPFS 和 InfluxDB 等主要系统中使用。