本文由 简悦 SimpRead 转码， 原文地址 www.toutiao.com
前面几篇文章介绍了 Paxos 算法，一直是分布式协议的标准，但 Paxos 算法难于理解，更难以实现。Raft 算法在 2013 年发表，就是建立在希望得
分布式共识系列文章：
前面几篇文章介绍了 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) 数据库。
在一个由 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 倒数，然后重新拉票。先发起拉票的节点就可以优先获得了多数节点的投票。
Raft 协议强依赖 Leader 节点的可用性来确保集群数据的一致性。数据的流向只能从 Leader 节点向 Follower 节点转移。
- 当 Client 向集群 Leader 节点提交数据（v=3）后，Leader 节点接收到的数据处于未提交状态（Uncommitted）。
- 接着 Leader 节点会并发向所有的 Follower 节点复制数据并等待接收响应。
- Leader 节点确保至少集群中超过半数节点确认接收到数据。
- Leader 向 Client 发送 Ack 确认数据已接收，表明此时数据状态进入已提交（Committed）状态。Leader 节点向 Follower 节点发通知告知该数据状态（v=3）已提交。
数据从 Leader 向 Follower 转移过程
接下来我们看一下，如果在数据转移过程中，Leader 挂掉，对数据一致性会造成什么影响。
- 在数据到达 Leader 节点前，这个阶段 Leader 挂掉。显然不影响一致性。
数据到达 Leader 前，Leader 挂掉
- 当数据到达 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 节点，但尚未提交
- 数据到达 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 协议如何将集群恢复到正常。
- 网络分区将原先的 Leader 节点和 Follower 节点分隔开，由于 Follower 收不到 Leader 的心跳将发起选举产生新的 Leader。
- 这时就产生了双 Leader，原先的 Leader 独自在一个区，向它提交数据不可能复制到多数节点，所以永远提交不成功。
- 向新的 Leader 提交数据可以提交成功，网络恢复后旧的 Leader 发现集群中有了新 Leader，于是自己主动降级为 Follower，并从新 Leader 那里同步数据，最终达成集群数据一致。
脑裂最终达成一致
设计 Raft 算法的目的是实现一种可理解性较好的 Multi Paxos 算法。看了上面的讲解，大家是否也觉得 Raft 算法理解起来非常容易呢？
我会持续更新关于物联网、云原生以及数字科技方面的文章，用简单的语言描述复杂的技术，也会偶尔发表一下对 IT 产业的看法，请大家多多关注，欢迎留言和转发，希望与大家互动交流，谢谢。