看动画学会 Raft 算法

程序员小王

发布于 2021-07-22 10:55:12

5570

发布于 2021-07-22 10:55:12

文章被收录于专栏：架构说架构说

分布式系统中数据必然会存在于多台机器，一致性简单地说就是分布式系统中的各个部分保持数据一致

但让数据保持一致往往并不像看上去那么简单，假设我们有两台机器 A 与 B，这时 A 更新了数据，A 需要将更新的指令同步到 B，如果 A 到 B 网络传输到 B 数据落地的总时间为 500ms，那么这个 500ms 就是可能造成数据不一致的时间窗口，假如两台机器分属不同机房，甚至分属不同国家的机房，其时间窗口会更大，具体会造成什么影响呢？

在谈分布式一致性之前，我们首先了解一个定理，那就是 CAP 定理，请注意，CAP 是定理而非理论，CAP 定理证明了一个分布式系统只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项。

一致性（Consistency）：指的就是整个集群的所有节点数据保持一致
可用性（Availability）：在数据同步过程中，集群是否是可用状态
分区容忍性（Partition tolerance）：是否能够容忍网络分区的发生

C 和 A相对好理解，这里着重说一下 P（Partition tolerance）分区容忍性，听着比较拗口，说实话，刚开始看到他的时候也是一脸茫然，分区？什么是分区？其实分区（Partition）简单的说就是服务器之间的网络通信断了，两边的服务器变成两个独立的集群，这就是所谓的分区，断了的原因有很多比如交换机故障，路由器故障，扫地阿姨把网线拔了等等，然后什么是容忍性（tolerance），这个就很好理解了，是不是发生分区了我的服务就不再提供服务了呢，当然不是，否则也就没有高可用一说了，那么我们能否说不做网络故障可能发生的假设呢，答案必然是不能的，首先网络延迟是必然的，网络延迟的过程中也可以将其当做发生分区，另外网络故障也可以说是必然的。

在所有分布式系统中 P 几乎都是不可抛弃的，所以说我们的选择也就只剩两个了 AP 和 CP。（两项）

如何理解 CP 与 AP

举个简单例子，若我们集群有两台机器，而两台机器网络发生中断而导致出现分区:

如果我们在双发无法通信的情况下继续允许两边进行写入，则必然造成数据的不一致，这时我们实现了 AP 而抛弃了C。
但如果我们禁止其中一方进行写入，这样就可以保证系统的一致性了，但我们却因为将一中一个副本置为不可用而导致了A属性的丧失，也是说实现了 CP。

至此分布式和一致性的背景知识就介绍完毕（摘抄自网络），篇幅问题就不展开聊了，下面进入正题。

Raft 算法

分布式一致性是分布式系统中最基本的问题,用来保证分布式系统的高可靠。解决分布式环境下一致性的问题不得不提 Paxos 算法，但由于 Paxos 算法过于晦涩难懂且难以实现，Diego Ongaro 提出了一种更易于理解和实现并能等价于 Paxos 算法的共识算法 —— Raft 算法。

因为 Raft 算法清晰易懂越来越多的开源项目尝试引入 Raft 算法来解决分布式一致性问题。在分布式存储领域基于 Raft 算法构建的项目百花齐放，欣欣向荣。

所以学会 Raft 算法对于理解很多支持分布式的开源项目有很大的帮助，分布式协议和算法这块也是后端程序员进阶必须掌握的知识，所以一起变强吧！

介绍 Raft 算法的文章早已是汗牛充栋，本文先介绍两个非常优秀的网站：

The Secret Lives of Data-CN 以图文方式介绍 Raft 算法，是非常好的入门材料。将其阅读完后您大概率已经了解了 Raft 算法，如果您仍有疑问可以回来继续阅读本文。

https://acehi.github.io/thesecretlivesofdata-cn/raft/

Raft Scope 是 Raft 官方提供的互动式演示程序，它展示了 Raft 集群的工作状态。您可以用它模拟节点宕机、心跳超时等各种情况。有了 Raft Scope 我们可以亲自“动手” 观察 Raft 集群是如何工作、如何处理各种故障的。

https://raft.github.io/raftscope/index.html

遗憾的是这个程序几乎没有任何说明非常难以上手。本文接下来将先介绍如何使用 Raft Scope 然后用它模拟几种 Raft 集群工作中会遭遇的典型状况。

下面就一起通过 Raft Scope 的动画来学习 Raft 算法吧！

Raft Scope 说明

可以看到 Raft Scope 界面由三部分组成。

最下方有两个滑块：上面的是进度条您可以拖动它回看刚刚发生过事件，下面的是变速器滑块越靠左系统运行越慢。

左上角部分是一个由 5 个节点组成的 Raft 集群，每个圆圈代表集群中的一个节点。点击节点可以看到它的状态。对话框的右下角有一些按钮，我们可以点击按钮模拟各种状况。我们直接右键点击节点也可以看到这些按钮

这些按钮的功能是:

stop: 节点停机
resume: 启动停机的节点
restart: 将节点立即重启
time out: 模拟心跳超时，点击按钮后相应节点会认为 Leader 发生了心跳超时。
request: 向集群提交新的数据

节点中间的数字是节点当前的任期号(Term), 节点的颜色似乎同样是用来表示任期的。节点可能处于 Follower、Candidate 或者 Leader 状态。

S2 处于 Candidate 状态，实心原点表示它现在收到的投票。图中的两个原点表示收到了 S2 和 S4 的投票，这 5 个小圆点和集群中节点的位置是对应的，左下角的小圆点表示 S4, 最上面的小圆点表示 S1。在集群选举过程中节点外的动态边框表示 Election Timeout。

黑色实心边框表示 S5 是 Leader。Follower 外面的边框表示 HeartBeat 超时倒计时。

右上角的表格表示各节点的日志，每行表示一个节点。

表格最上面的数字是日志的序号(Log Index)。Log Index 是一个自增且连续的 ID，它可以作为一条日志唯一标识。节点中最大的 Log Index 也反映了这个节点的状态机是否与集群一致。

表格里的单元格表示日志项(Entry)，其中的数字表示提交日志的任期(Term)。虚线框表示日志尚未提交，实线框表示日志已经提交。

我们可以点击 leader 节点的 request 按钮来查看向 Raft 集群提交数据的过程。

Leader 选举

Raft Scope 启动后会立即进行第一次 Leader 选举，在集群运行过程任何一个 Follower 出现心跳超时都会引发新一轮选举。

我们可以点击任意一个 Follower 的 time out 按钮模拟心跳超时，随后此 Follower 会发起新一轮选举。

或者我们可以点击 Leader 的 stop、restart 来模拟 Leader 宕机或者重启，并观察随后的集群选举过程。

比较奇怪的是，Raft Scope 中的 Leader 节点也可以通过点击 time out 来模拟心跳超时，在实际的 Raft 集群中 Leader 节点通常不会对自己进行心跳检测。

Leader 选举的更多介绍可以查看：Leader选举。不过 The Secret Lives of Data 有两处说的可能不太清楚：

这里的选举超时是指新一轮选举开始时，每个节点随机思考要不要竞选 Leader 的时间，这个时间一般100-到200ms，非常短。

Candidate 发起选举时会将自身任期(Term)+1并向其它所有节点发出 RequestVote 消息，这条消息中包含新任期和 Candidate 节点的最新 Log Index

收到 RequestVote 的节点会进行判断:

def onRequestVote(self, request_vote)
    if request_vote.term <= self.term:
        # 若 RequestVote 中的任期小于或等于(<=)当前任期
        # 则继续 Follow 当前 Leader 并拒绝给 RequestVote投票
        return False
    if request_vote.log_index < self.log_index:
        # 若 request_vote 发送者的 log_index 不如自己新，节点也会拒绝给发送者投票
        # 这种机制确保了已经提交到集群中的日志不会丢失，即保证 Raft 算法的安全性
        return False
    if self.voted_for is None:
        # 若在本 term 中当前节点还未投票，则给 request_vote 的发送者投票
        self.voted_for = request_vote.sender
        return True
    else:
        return False

Follower 超时

现在我们研究一下 The Secret Lives of Data 没有详细说明的 Follower 超时处理过程。

我们可以点击任意一个 Follower 的 time out 按钮模拟心跳超时，随后此 Follower 会发起新一轮选举。

根据上文中的 onRequestVote 逻辑，超时的 Follower 的 Log Index 是否与集群中的大多数节点相同决定了这次选举的不同结果。

首先来看超时 Follower 的 Log Index 与集群中大多数相同的情况：

现在我们点击 S5 的 time out 按钮，随后我们看到 S5 发起了一轮投票。因为 5 个节点的 Log Index 是一致的, 所以包含原 Leader 在内的大多数节点都投票给了 S5。

现在 S5 成为了新一任 Leader.

接下来我们看另外一种情况。S5 由于网络问题没有收到带有 Log Entry 1 的心跳包并导致心跳超时，S5 随后会发起一次投票:

由于 S5 的 Log Index 比较小其它节点拒绝投票给他，集群 Leader 和任期不变：

日志复制

日志复制的介绍您可以查看：日志复制

现在我们进一步探究日志复制的过程:

客户端将更改提交给 Leader, Leader 会在自己的日志中写入一条未提交的记录(Entry)
在下一次心跳时 Leader 会将更改发送给所有 Follower
一旦收到过半节点的确认 Leader 就会提交自己日志中的记录4
并向客户端返回写入成功
Leader 会在下一次心跳时通知所有节点提交日志

这里比较复杂的情况是在第 4 步完成之后 Leader 崩溃。由于此时客户端已经收到了写入成功的回复，所以在选出新的 Leader 之后要继续完成提交。

在 Leader 提交了自己的日志后我们立即关掉 Leader:

随后集群发起了一次选举，S3 成为新任 Leader:

可能是因为 Raft Scope 存在 Bug, S3 本应该当选后立即完成提交工作。但是实际上需要我们再一次 Request 之后，日志1 和日志 2 才会被一起提交。

脑裂问题

在 Leader 崩溃时可能会有多个节点近乎同时发现心跳超时并转变为 Candidate 开始选举：

其它节点投票情况多种多样，但只要保证获只有得到过半投票的候选人才能成为 Leader。那么选举结果只有两种可能：

有且只有一个候选人获得过半投票成为 Leader 并开始新的任期
没有一个候选人获得过半投票，没有选出 Leader 进入下一轮投票

绝对不会选出多个 Leader

网络分区问题

Raft 甚至可以在网络分区的情况下正常工作：

在发生网络分区后可能存在 3 种情况:

任意分区中的节点数都不超过一半：这种情况只有集群被分成 3 个或更多分区时才会出现，十分罕见。因为 Leader 选举和 Commit Log 都需要超过一半节点确认才可以进行，在这种情况下 Raft 集群不能正常工作。
leader 所在的分区有超过一半的节点：这种情况视作其它分区中的 Follower 宕机，系统仍然可以继续工作。在分区修复后，Follower 节点会重新与 Leader 同步。
leader 所在分区中节点数不超过一半，但存在节点数超过一半的分区。这种情况最为复杂: