分布式共识系列文章：

• 《解决分布式一致性问题，不得不了解的Paxos算法》
• 《基本Paxos协议是如何实现分布式数据一致性的？》
• 《可用于实际应用场景中的Multi Paxos实用算法》

前面几篇文章介绍了Paxos算法，一直是分布式协议的标准，但Paxos算法难于理解，更难以实现。即使google的分布式锁系统Chubby以Paxos算法实现，也遇到了很多坑。为了简化分布一致性算法，斯坦福大学提出了一种Raft算法。

Raft 算法在2013年发表，就是建立在希望得到一个更易于理解的 Paxos 算法的替代品。论文题目《In Search of an Understandable Consensus Algorithm》就可以看出来，可理解性是Raft算法的主要目标之一。到现在已经有了十多种语言的Raft算法的实现框架，最为出名的就是Etcd。

Etcd是CoreOS团队于2013年6月发起的开源项目，它的目标是构建一个高可用的分布式键值(key-value)数据库。

Leader选举（Leader Election）

在一个由 Raft 协议组织的集群中有三类角色：Leader（领袖）、Follower（群众）、Candidate（候选人）。

Raft三类角色的状态转换

• Leader：处理所有客户端交互，日志复制等。集群一般只能有一个领导，领导在位期间就是一个任期（Term）。Leader定期向Follower发送心跳，宣示自己的存在。
• Follower：如果Follower在election timeout内没有收到来自Leader的心跳，那么会认为Leader挂掉了。Follower会更新自己的当前任期（Current Term）并成为Candidate，并开始选举新的Leader。
• Candidate：候选人，有可能被选为一个新的领导人。如果收到了多数的投票就当选为Leader。如果超过一定时间没有收到选票，就重新发起选举。

一个最小的 Raft集群需要三个参与者，这样才可能投出多数票。如下图所示，初始状态下 ABC三个节点开始选举Leader。

Raft协议Leader选举

Leader选举过程中有三种可能的情形发生：

• A节点要投自己一票，并把提议（拉票请求）发给B和C，B和C接受了A的提议，也投票给A。A成为Leader。
• A节点投了自己一票，B节点也投了自己一票，C节点支持A节点的提议，少数服从多数。A成为Leader。
• A节点、B节点、C节点都各自投了自己一票。没有节点获得多数票。

以上前二种情况都能选出 Leader，第三种情况本轮投票无效，出现了平票（Split Votes）。因为没有任何一方获得多数票，所以要发起新的一轮投票。

Raft协议为了不让选举机制反复出现平票，定义了一个随机超时机制（randomized election timeouts）。一旦发生平票，平票的节点会各自再来一次随机timeout倒数，然后重新拉票。先发起拉票的节点就可以优先获得了多数节点的投票。

数据同步（Log Replication）

Raft 协议强依赖 Leader 节点的可用性来确保集群数据的一致性。数据的流向只能从 Leader节点向 Follower 节点转移。

1. 当 Client 向集群 Leader 节点提交数据（v=3）后，Leader 节点接收到的数据处于未提交状态（Uncommitted）。
2. 接着 Leader 节点会并发向所有的 Follower 节点复制数据并等待接收响应。
3. Leader节点确保至少集群中超过半数节点确认接收到数据。
4. Leader向 Client 发送Ack确认数据已接收，表明此时数据状态进入已提交（Committed）状态。Leader 节点向Follower 节点发通知告知该数据状态（v=3）已提交。

数据从Leader向Follower转移过程

Leader挂掉对一致性的影响

接下来我们看一下，如果在数据转移过程中，Leader挂掉，对数据一致性会造成什么影响。

1. 在数据到达 Leader 节点前，这个阶段 Leader 挂掉。显然不影响一致性。

数据到达Leader前，Leader挂掉

2. 当数据到达 Leader 节点，但未复制给 Follower 节点。这个阶段 Leader 挂掉，数据属于未提交状态。Client 没有收到 Ack确认会认为超时失败，于是发起重试。

Follower 节点重新选主，新的Leader上没有该数据。Client 重新提交数据到新Leader可以成功。原来的 Leader 节点恢复后作为 Follower 加入集群，从当前任期的新 Leader 同步数据，保持和 Leader 数据一致。

数据到达Leader，处于未提交状态

3 当数据到达 Leader 节点，并成功复制给所有Follower节点，但Follower节点尚未向 Leader 响应接收。此时 Leader 挂掉。

虽然数据在 Follower 节点处于未提交状态（Uncommitted），但已经保持一致。重新选出 Leader 后可完成数据提交。此时 Client 由于不知到底提交成功没有，会重试提交。针对这种情况 Raft 要求 RPC 请求实现幂等性，也就是要实现内部去重机制。

当数据到达 Leader 节点，并成功复制给所有Follower节点，但尚未提交

4. 数据到达 Leader 节点，并成功复制给 Follower 部分节点，但还未向 Leader 响应接收。在这个阶段 Leader 挂掉，数据在 Follower 节点处于未提交状态（Uncommitted）且数据不一致。

Raft 协议要求投票只能投给拥有最新数据的节点。这样拥有最新数据的节点会被选为 Leader，再同步数据到 Follower，数据不会丢失并实现最终一致。

5 数据到达 Leader 节点，并成功复制给 Follower 所有或多数节点，数据在 Leader 处于已提交状态，但在 Follower 处于未提交状态。这个阶段 Leader 挂掉，重新选出新 Leader 后的处理流程和上面第3种情况一样。

数据在Leader 节点处于已提交，在Follower处于未提交状态

6 数据到达 Leader 节点，成功复制到 Follower 所有或多数节点，数据在所有节点都处于已提交状态，但由于某种原因，Client未收到Ack响应。这个阶段 Leader 挂掉，集群内部数据其实已经是一致的，Client 重新提交数据，基于幂等策略对一致性无影响。

集群内数据已达成一致

从上面的讨论可知，在Leader向Follower进行数据同步的不同阶段，Leader挂掉也不会影响数据的最终一致性。那么如果由于网络分区，导致双Leader出现，即所谓脑裂的情况，那么对数据一致性会有影响吗？

脑裂的情况

所谓脑裂，就是集群中出现了双 Leader，这种情况通常是由于网络分区导致。一山不容二虎，一个集群也不能有二主。我们来看一下这种情况下，Raft协议如何将集群恢复到正常。

1. 网络分区将原先的 Leader 节点和 Follower 节点分隔开，由于Follower 收不到 Leader 的心跳将发起选举产生新的 Leader。
2. 这时就产生了双 Leader，原先的 Leader 独自在一个区，向它提交数据不可能复制到多数节点，所以永远提交不成功。
3. 向新的 Leader 提交数据可以提交成功，网络恢复后旧的Leader 发现集群中有了新 Leader，于是自己主动降级为 Follower，并从新 Leader 那里同步数据，最终达成集群数据一致。

脑裂最终达成一致

总结

设计Raft算法的目的是实现一种可理解性较好的Multi Paxos算法。看了上面的讲解，大家是否也觉得Raft算法理解起来非常容易呢？

我会持续更新关于物联网、云原生以及数字科技方面的文章，用简单的语言描述复杂的技术，也会偶尔发表一下对IT产业的看法，请大家多多关注，欢迎留言和转发，希望与大家互动交流，谢谢。