数据库 Raft 笔记

yfractal · 2020年06月25日 · 最后由 yfractal 回复于 2020年06月26日 · 2480 次阅读

前言

Raft 资料挺多的，比如 https://raft.github.io/，再比如 6.824: Distributed Systems 里相关的内搜。

下面这篇文章，主要是总结性质。特点是从实现出发，先做最简单的实现，然后说明这种实现会有什么问题，并说明要如何解决。

目前是暂时没有图片，懒是主要原因，其次是，了解 Raft 的话，可视化比较有用，但深入到细节，可能例子和代码（测试）更实惠。

Raft 看起来挺简单，但有非常多的细节，实现的时候，会发现有各种 bug。下面的文章，主要是想缕一下这些细节。

Raft 是做什么的

Raft 是一个复制 log 的算法（准确的说，是解决分布式系统一致性的算法，存储好的 log 被称为 commited log）。这里面 log 可以是一个数字，比如 1，也可以是一条命令，比如 put(key0, val0)。

Raft 的 leader 节点，会接收客户端传来的 command（eg: put(key0, val0)），并将 command 复制给 Raft 集群里的所有节点。

当 leader 知道 command 被存好的时候，会将节点存储的位置，通过请求返回给客户端。

Raft 如何定义存好了（committed)？

Raft 认为，一个 command 被多数（majority）节点保存，就认为这个 command 是存好了的，称为 committed。

这样可以保证，集群中，多数的节点正常工作集群可用，从而提高了可用性。

Raft 的两个阶段

Raft 为了方便理解和实现，规定任何一个时刻，只有一个节点，可以接收客户端创来的 command，这个节点被称为 leader。

所以 Raft 被分为两个阶段，一个是选举（elect），一个是复制（replica）。

Raft 选举

选举是指，在所有节点里，挑出一个节点，使这个节点成为 leader。

选举的过程是，某个节点 node0 向所有其他节点，发送投票（RequestVote）请求。请求大体是，我是 node0，我想成为 leader。node0 根据其他节点的返回，来判断是否要把自己变成 leader。

我们先假设只投一轮。因为我们希望只选出一个 leader，显然，每个节点，只能投一个节点。并且，只有一个节点获得了多数的认可的时候，才能成为 leader。

因此一个节点在投票的时候，如果已经投过了，就不能再投了。节点在收集选票的时候，获得多数节点认可的时候，就把自己的状态更新为 leader。

假设我们有 3 个节点，每个节点都选了自己，显然没办法选出 leader。因此 Raft 规定，如果一段时间内，没有 leader 出现（自己成为 leader 或者收到合法的 leader 的消息），则再次发起送新一轮投票（RequestVote）请求。

那么问题来了，当一个节点收到 RequestVote 请求的时候，如果判断这是新一轮的投票呢？

为了解决这个问题，Raft 让每个节点都记录一个 term。term 是一个从 0 开始的单增字段。每个节点，在发起 RequestVote 前，会让 term 增加 1（term += 1）。

一个节点，收到比自己的 term 大的时候请求时，就可以知道，有其他发起了新的一轮投票。

所以 follower 收到的 requestVote 有一下 3 种情况。

requestVote.term < self.term，我们可以知道，请求是之前的轮数，所以忽略该请求。

requestVote.term > self.term，有节点发起新一轮投票了，所以该节点进入新一轮投票，新一轮的投票，谁也没投过，所以投赞成票。既：

self.term = requestVote.term
requestVoteReply.VoteGranted = true
self.votedFor = requestVote.candidateId
return requestVoteReply

requestVote.term == self.term，如果当前节点，没有投过任何节点，或者投的就是这个节点，返回 true。既

if self.votedId == nil || self.votedFor == requestVote.candidateId {
  self.votedId = requestVoteReply.CandidateId
  requestVoteReply.VoteGranted = true
} else {
  requestVoteReply.VoteGranted = fasle
}

return requestVoteReply

通过上面的机制，Raft 可以保证任何一个 term，只有唯一一个 leader 节点。并且可以通过 term 来判定事件发生的先后关系（这里面不能用机器的本地时间原因是，机器的本地时间可能不一致或者虚拟机停机之类的原因导致无法正确推断先后关系）。

保活

因为节点间，只有通过发消息，才能获取彼此的状态。所以 leader 会向 followers 发 ping 消息保活。

如果 follower 一段时间没有收到 ping 消息，则认为当前的 leader 不可用了，会发起投票。

复制 log (Log replication)

我们知道，对于整个集群来讲，一个 command 如果被多数节点存储了，则认为这个 command 是 committed 的。

具体的过程是：leader 收到客户端传来请求要存 command0，leader 存储 command0，并通知其他节点存储 command0，当 leader 收到多数节点（majority - 1）的成功的返回的时候，leader 知道，包括自己在内，有多数节点，已经存了 command0，则返回客户端的请求，告知存储成功。

follower 接收 command 条件：相同的 preEntry.index

下面来看 follower 接收 command 的条件。

因为 Raft 会接受多个 command。所以一个数组来存所有的 command，这个数组被称为 entries。

假设 leader 当前的 entries 是 [a, b, c]，希望某个 follower 接受 command c。

而 follower 的 entries 是 [a]，接收 c 的话，就变成了 [a, c]。leader 和 follower 的 entries 是不一样的，所以 follower 要拒绝请求。

还是上面的例子。如果 follower 的 entries 是 [a, b]，接收 c 就会变成了 [a, b, c]，和 leader 的 entries 一致，所以要接收。

那么，条件应该是，希望被存储的 command 之前所有的 entries，在 leader 和 follower 里是一样的。

这样虽然满足条件，但 entries 多的时候，需要通过网络传很多数据，无法满足性能要求。

下面我们来看 Raft 如何优化，假设状态是：

raft0: leader, entries=[a, b]
raft1: follower, entries=[a, b]

raft0 收到 c 变成

raft0: leader, entries=[a, b, c]
raft1: follower, entries=[a, b]

raft1 收到 raft0 的请求增加 c，而 raft0 在 c 之前的 entries 是 [a, b]，raft1 的是 [a, b]

由于 raft1.preEntries == request.preEntries，更新自己的 entries，raft1.entries.append(c)

这个时候的状态是

raft0: leader, entries=[a, b, c]
raft1: follower, entries=[a, b, c]

此时，raft0 同步 command d。我们知道 raft1 已经验证过 a、b 了，所以只验证 c 就可以了。这样就可以减少网络请求数据。

并且，我们可以看出来，一个 entries 内相同 index 存储的 command 一定是相同的，所以，我们只要验证 preIndex 即可。

follower 接受 command 条件：相同的 `preEntry.term`

从上面的例子可以推断，可以通过前一个 index 是否相同，来判断 entry 是否相同。

实际上，这个推论只有在 leader 不变的情况下，才成立。

leader 变换的情况如下：

1. 初始情况
   有三个节点，raft0, raft1, raft2
   term = 1
   raft0: state=leader, entries = [a]
   raft1: state=follower, entries = [a]
   raft2: state=follower, entries = [a]
2. raft0 收到 command b
   entries 变成 [a, b]，
   raft0: state=leader, entries = [a, b]
   raft1: state=follower, entries = [a]
   raft2: state=follower, entries = [a]
3. leader crash，raft1 变成 leader
   状态变成
   term = 2
   raft0: state=follower, entries = [a, b]
   raft1: state=leader, entries = [a]
   raft2: state=follower, entries = [a]
4. 这时候，raft1 收到 command c 和 d
   状态变成
   raft0: state=follower, entries = [a, b]
   raft1: state=leader, entries = [a, c, d]
   raft2: state=follower, entries = [a]

如果这个时候 raft0 收到复制 d 的请求，[a, b] != [a, c,] 显然不应该接受。但 preIndex 是相同的，之前的假设是不成立的。

出现这种情况的原因是，有新的 leader 产生。为了避免这个问题，需要在判断 index 是否相等的同时，还要判断 term 是否一样。

follower 接收 command 前置条件：leader 选举

通过 index 和 term 已经可以判断前一个 entry 是否一样，从而判定，是否接受 entry。但仍然会有下面这种情况出现：

1. 初始情况
   term = 1
   raft0: state=leader, entries = [{term:1, index:1, command: a}, {term:1, index:2, command: b}]
   raft1: state=follower, entries = [{term:1, index:1, command: a}, {term:1, index:2, command: b}]
   raft2: state=follower, entries = [{term:1, index:1, command: a}]
2. raft0 crash, raft2 变成 leader
   term = 2
   raft0: state=follower, entries = [{term:1, index:1, command: a}, {term:1, index:2, command: b}]
   raft1: state=leader, entries = [{term:1, index:1, command: a}, {term:1, index:2, command: b}]
   raft2: state=leader, entries = [{term:1, index:1, command: a}]
3. raft1 收到 command b，所有节点同步后得到
   raft0: state=follower, entries = [{term:1, index:1, command: a},{term:2, index:2, command: c}]
   raft1: state=leader, entries = [{term:1, index:1, command: a},{term:2, index:2, command: c}]
   raft2: state=leader, entries = [{term:1, index:1, command: a},{term:2, index:2, command: c}]

我们看到，index = 2 的 entry 从 b 变成了 c。而在初始条件下，command b 已经被大多数节点存储，那么 b 是 committed 的。但最终 c 被替换了。不符合 committed 的定义。

Raft 为了解决这个问题，对 leader 选举增加了这样的要求：一个收到 RequestVote 的节点，只有判定发送方的数据（通过最后一个 entry）比较新的时候，才能投同意票。

比较新指的是下面两种情况：

候选人节点传来的 term 比接收到 RequestVote 的节点的 term 大。
当 term 相同时，候选人节点的 index 要大于等于接收到 RequestVote 的节点的 index。

按照这个规则，当 raft2 发 RequestVote 请求的时候，最后一个 entry 的 term = 1，index = 1。对于 raft0 和 raft1，term=1, index=2，都不符合条件，所以 raft2 无法被选为 leader。也就不会出现上面提到的问题。

处理冲突

我们看下面这种情况

1. 初始情况
   term = 2
   raft0: state=leader, entries = [{term:1, index:1, command: a}]
   raft1: state=follower, entries = [{term:1, index:1, command: a}, {term:1, index:2, command: b}]
   raft2: state=follower, entries = [{term:1, index:1, command: a}]
2. raft0 收到 command c
   term = 2
   raft0: state=leader, entries = [{term:1, index:1, command: a},  {term:2, index:2, command: c}]
   raft1: state=follower, entries = [{term:1, index:1, command: a}, {term:1, index:2, command: b}]
   raft2: state=follower, entries = [{term:1, index:1, command: a}]

当 raft0 向 raft1 发起 AppendEntries 请求，希望同步 entry={term:2, index:2, command: c}。对于 raft1 而言，符合同步条件，会将 {term:1, index:2, command: b} 替换成 {term:2, index:2, command: c}。变成

2. 同步后的状态
   term = 2
   raft0: state=leader, entries = [{term:1, index:1, command: a},  {term:2, index:2, command: c}]
   raft1: state=follower, entries = [{term:1, index:1, command: a}, {term:2, index:2, command: c}]
   raft2: state=follower, entries = [{term:1, index:1, command: a}]

同时 Raft 还需要处理，follower 和 leader 相差很多的情况。

term = 2
raft0: state=leader, entries = [{term:1, index:1, command: a},  {term:2, index:2, command: b}, {term:2, index:3, command: c}]
raft1: state=follower, entries = [{term:1, index:1, command: a}]

我们这里，先假设 raft0 被选为 leader 后，一直没有新的 leader 产生。我们知道 leader 被选举出来的条件是，leader 包含了所有 committed 的 entries，所以 follower 应该同 leader 保持一致。

当一个节点成为 leader 后，会把自己最后一个 entry 发给 follower，如果 follower 拒绝，则说明有之前的 entry 没有被同步，这时候 leader 会再次发倒数第二个和倒数第一个 entry 给 follower，以此类推直到成功为止。

上面的例子是第一次发 appendEntriesArgs.entries= [{term:2, index:3, command: c}]，由于失败，则发 appendEntriesArgs.entries= [{term:2, index:2, command: b}, {term:2, index:3, command: c}]

现在，我们再考虑 leader 变化的情况。

如果有新的 leader 产生，则只有新的 leader 可以复制 command。

所以当 follower 收到的 appendEntriesArgs.term < self.term 时候，会拒绝请求，并把 self.term 返回给发送请求的 leader，leader 收到请求后，知道有新的 leader 产生，则将自己的状态改成 follower。

如果 appendEntriesArgs.term >= self.term，follower 只要更新自己的 term 即可。

Ping

Ping 首要目的是用来保活的。但 ping 同时要带上 leader 的最后一个 committed index。

这是因为，follower 也需要知道哪些 entry 是被 committed 了。如果 ping 消息不带上 last committed index 的话，follower 始终无法把最后一个 entry 标为 committed。

这是因为，最开始 leader 在向 follower 发 AppendEntries 请求的时候，这个 entry 可能还没有被 committed，所以 follower 不能把这个 entry 标为 committed。

只有之后发 ping 消息的时候，这个 entry 可能已经是 committed 了，所以需要 ping 来通知 follower。

闲话

实现 Raft 最大感受是，bug 层出不穷、随机出现且不好排查，但原因都是由于的细节理解不到位导致的。

所以就写了这样一篇文章作为整理。

下一篇可能会有使用 Erlang 实现 Raft。

changelog

根据一楼建议：

Raft 是一个复制 log 的算法

更新为

Raft 是一个复制 log 的算法（准确的说，是解决分布式系统一致性的算法，存储好的 log 被称为 commited log）

参考

[6.824: Distributed Systems LEC 5、LEC 6、LEC 7、 Lab 2A][1]

[In Search of an Understandable Consensus Algorithm][2]

[Students' Guide to Raft][3]

[1]: https://pdos.csail.mit.edu/6.824/schedule.html?from=timeline [2]: https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf
[3]: https://thesquareplanet.com/blog/students-guide-to-raft/

4 个赞

piecehealth #1 2020年06月26日

Raft 是一个复制 log 的算法

Raft 是解决分布式系统一致性的算法，log 其实是 commit log，不说明一下容易产生歧义。

yfractal #2 2020年06月26日

对

piecehealth 回复

感谢，已更新。

需要登录后方可回复, 如果你还没有账号请注册新账号

4 个赞

共收到 2 条回复

收到新回复，点击立即加载

数据库 Raft 笔记

数据库 Raft 笔记

前言

Raft 是做什么的

Raft 如何定义存好了（committed)？

Raft 的两个阶段

Raft 选举

保活

复制 log (Log replication)

follower 接收 command 条件：相同的 preEntry.index

follower 接受 command 条件：相同的 preEntry.term

follower 接收 command 前置条件：leader 选举

处理冲突

Ping

闲话

changelog

参考

follower 接受 command 条件：相同的 `preEntry.term`