Undefined01's blog

最近的笔记

6.824 与 Raft

34分钟阅读

6.824 是一门非常棒的分布式系统公开课。这门课程不仅公布了提纲、录像，还有配套的Lab实验以及对应的本地测试。本系列文章使用 2021 版实验。

Raft 是一个易于理解的分布式共识（consensus）协议。在论文中就直截了当地提出易于理解是 Raft 的设计目标之一。6.824 的助教也提到正是由于 Raft 更易于理解，6.824 在 2016 年把课程实验需要实现的共识算法从 Paxos 改成了 Raft ，并在课后调查中取得了非常正面的反映。

同时，Raft具有大量的学习资源，如 Raft 动画演示 和它的中文版，对初步理解 Raft 执行流程有非常大的帮助。此外还有 Raft 可视化 用可交互的方式展示 Raft 达成共识的过程，在有疑问时能够作为参照。

Raft 本身只是一个分布式共识协议，用以提供容错性和强一致性。在 CAP 定理中，Raft 选择了一致性(C)和分区容错性(P)。

如果将 Raft 本身看做黑盒模型：

  • 业务服务器存在于每个 Raft 节点上，并被相应的节点上的 Raft 服务给予输入。
  • 在业务客户端看来，客户端需要写操作时，不能直接访问业务服务器，而必须以 Raft Leader 为中介向业务服务器发送 Command。需要读操作时，则可以直接访问任意一个节点上的业务服务器。
  • 如果随机读取一个节点上的数据可以得到顺序一致性，并且不是强一致性或者线性一致性（Linearizable）。即 Leader 写操作后在 Follower 立即读不一定能读到最新值，但是某次读到最新值后下一次读一定不可能是旧值。除此之外，另一个不同节点的读还是可能读到旧值。因为 Leader 的写操作完成的瞬间，Leader 增加的 commitIndex 可能还未通知到 Follower，对 Follower 的读操作还是旧值（非可线性化）。另外 client 访问的还可能是一个已经和 Leader 失联很久的 Follower 节点。
  • 如果每次都读取 Leader 节点上的业务服务器，在 Leader 未发生变更的情况下可以得到强一致性或者线性一致性。即写操作（新增日志）不是瞬间完成的，这段时间内仍然可能读到旧数据。但是当写操作结束，即日志已经被 committed，则读操作保证能够读到新数据）。更加一般的处理是当 Follower 收到请求时将请求转发给 Follower 认为的 Leader，同时 Leader 立即向至少一半的节点确认自己是否仍然是 Leader，若还是 Leader 则返回读结果，否则返回失败让 client 重新尝试从另一个节点读取。

在每个节点的业务服务器看来，只需要独立地接受本节点上的 Raft 服务的写请求即可提供顺序一致性/线性一致性的服务。

Lab 的整体结构

6.824中 Raft 的实验（Lab 2）分为四个部分，分别是：

  • 2A：选举（Election）
  • 2B：日志同步（Log Replication）
  • 2C：持久化（Persistance）
  • 2D：日志压缩/快照（Compaction/Snapshot）

Lab的四个部分对应 Raft 的四个主要模块，可分别实现和验证，再次体现了 Raft 的模块性和易于实现、易于测试的特点。

阅读顺序

建议先快速浏览一遍 Raft 论文 （主要是第五节），知道每个部分在说什么，了解一些 Raft 关键词汇的定义和流程。然后利用 Raft 动画演示 （中文版）对照论文过一遍流程。最后详读论文，理解各种情况下 Raft 的处理方式，有疑问时对照 Raft 可视化 的参考实现。

实现建议

在6.824的实验页面中，有非常多的提示。下面我也根据我的个人经验给出一些实现上的建议。

  1. 正确优先。这是一个课程实验，而做实验的主要目的是通过实践检验自己的理解，而不是尝试自己造一个“轮子”。因此在实现的时候应该做到正确优先。不必过多的考虑效率问题，不要过早开始“优化”。
  2. 责任划分。在设计的时候尽可能的细化每个函数、每个协程执行所需要的前提条件和执行结果。想明白每个函数、每个协程该做什么，不该做什么。这样能大大简化函数间的交互，减小犯错的可能。现有的交通法规就利用了“责任划分”。在开车时司机要同时关注各个方向上的路况比较困难，但是责任划分让直行的车只管前方，变道的车注意变道，尾随的车保持车距，大大简少了开车时需要注意的信息，也降低了出错率。
  3. 调试信息。在代码达到一定的复杂度之后，基本不可能再通过经典的 gdb 进行单步调试了。此时最有效的调试方式就是调试信息，也就是 log 。但是 log 的设计也有一定的技巧，既要保证在出错时， log 带有足够的信息，又要保证 log 不会太多，使有效信息被埋没。通常而言调试信息要尽量包含执行的关键信息和程序的执行路径，方便检查 log 时和代码对照。
  4. 谨慎用锁。这句话并不是说不鼓励用锁，而是用锁的时候需要反复检查锁是否真的能够提供原子性，或者是否可能产生死锁。在实验中，可以使用“一把大锁”锁住整个 Raft 结构体以保证原子性。你可能会担心效率，但是别忘了“正确优先”。平时的编程中也应该避免自作聪明的使用“无锁”。细粒度的锁通常只会带来少量的性能提升，和更加难以排查的 bug。同时本实验使用的 go 语言并不提供 RAII 机制，因此锁不会自动释放，容易死锁。建议封装加锁解锁操作并进行日志输出，方便死锁时进行排查。go 的 channel 机制也很容易造成死锁，也需要注意。

2A 选举（Election）

具体过程应阅读论文，以下仅供思路整理。

大致流程

  • 根据 Figure 2 初始化 Raft 节点。所有 Raft 节点最初都是 Follower 。

  • 当 Follower 一定时间没有收到 Leader 的消息之后，开始选举。 通常而言，为了避免启动时所有节点同时竞选，选举时间会加上一定的随机值。 currentTerm可以认为是“任期”（下简称为 term）。 选举时，该节点 term 加一，身份更新为 Candidate 并向所有其他节点发送 RequestVote 请求。 Candidate 必定投票给自己。

  • Raft 的所有节点在收到 任意一个 RPC 时都需要检查自己与发送消息的节点的 term 值。如果自己的更加新，则无条件拒绝该操作。如果对方的更加新，则无条件更新自己的 term 并重置选举状态（变为 Follower 且 VotedFor 清空）。

  • 收到 RequestVote 的节点首先检查发送节点的任期（term）是否更新，不是则直接拒绝，以保证大多数承认的 term 单调递增（但不必每次间隔都是1）。随后节点检查自己是否已批准某个候选人（VotedFor）。如果没有或正好是发送请求的节点，则批准。（后面还会有其他条件，但此时不必理会）

  • Candidate 在收到过半节点的批准之后，晋升为 Leader

  • Leader 需要每隔一段时间向所有节点发送消息（AppendEntries），确认连接畅通和保持自己的任期。

分析

  • 在选举时，Follower 总是会给同一个 term 内最先向自己请求 RequestVote 的节点投票。因此两个 Candidate 同时选举时有可能发生“分票”，没有节点获得过半选票。此时 Raft 集群中没有 Leader，无法提供服务直到某次选举成功选出 Leader。因此 Raft 的选举间隔不能太长，论文中为 150ms ~ 300ms。这保证了不可能出现 term 相同的 Leader，term 也可能因此不连续。

  • Raft 使用了“强势 Leader”策略，也即只有 Leader 可以发送 RPC 消息给其他节点，以同步日志。当 Follower 与 Leader 的日志出现冲突时，无条件同步 Leader 的日志。因此需要保证日志过旧的节点不能当选。（见 2B）

  • 对于分区容错问题，在出现分区后有可能出现两个主节点接受 Client 的请求（上一轮的 Leader 和过半节点新选举出的 Leader）。 此时拥有少于一半 Follower 的 Leader 将因为无法提交（commit）新的日志（因为提交日志同样需要过半 Follower 同步，具体细节在 2B 部分）从而无法完成 Client 的请求。 当两个 Leader “合并”时，term 更低的无条件变为 Follower 。term 更高的 Leader 是过半节点新选举出来的 Leader，可以继续正常履行职责。

  • Raft 是“非拜占庭将军”条件下的共识算法，也即节点之中不能有“内鬼”，传输过程中信息不能被篡改，或者节点发生错误时不能传播错误的数据。通过给每个节点不断发 term 很高的请求即可轻易夺得 Leader 身份，被篡改的或出现错误的 log 也会因为 Leader 的身份强制同步到 Follower 中。 但是 Raft 能够容忍网络延迟、丢包、重包和包的乱序到达。

  • AppendEntries 实际上是在 2B 部分推送日志时使用的 RPC 。Raft 将不带任何日志的 AppendEntries 调用视为心跳包。

实现细节

论文的 Figure 2 给出了 Raft 节点本身需要维护的状态，以及各个 RPC 请求的参数和返回值。2A、2B 部分可以直接照抄论文给出的数据结构。

在实验中，首先需要实现 Follower、Candidate 和 Leader 的状态转换。每一个状态下需要完成不同的工作。 状态转换条件可参考上面 大致流程 小节中的分析。

之后，需要实现 RequestVote 和 AppendEntries 两个 RPC 的发送和接收。 当前两个 RPC 不需要携带任何日志信息，LastLogIndex 和 LastLogTerm 直接填 0 即可。

PS：理论上不需要实现 AppendEntries RPC 也可通过 2A 部分的测试。 因为 2A 部分只要求出现 Leader，而不要求网络畅通的情况下保持同一个 Leader。 可能会报 warning: term changed even though there were no failures，但测试还是算正常通过。 即使 Leader 不定时发送 AppendEntries ， Follower 会在选举超时后发起新的选举。

在实现中，建议在所有节点 Raft 结构体的 log 中加入一个空的日志，即 log[0]，其 index 和 term 均为 0。 这样即可以保证 log 的 index 从 1 开始，方便上述 lastLogIndex 和 lastLogTerm 的填写，也可以简化后续许多的判断。

此外，还可以为 RPC 抽象出一个通用的 HandleRequest 函数。 该函数首先为 RPC 的返回值填入当前节点的 currentTerm ，随后比较请求的 term 和自身的 currentTerm。 如果请求的 term 更小则直接拒绝该请求，不再进行后续的其他处理。 如果请求的 term 大于等于自身的 currentTerm，则视为接受到了一次合法的心跳包，重置自己的选举计时器。 更进一步地，如果请求的 term 更大则更新自身的 term 并重置选举状态（变为 Follower 且 VotedFor 清空）。

RPC 请求返回时同样需要进行上述比较，不再赘述。

需要注意的是，RPC 之间、超时选举的线程等都可能会出现并发读写，因此需要注意对共享数据的保护，防止读到不一致的数据（如节点状态刚刚转换为 Candidate 但还未设置 voteFor 时收到了 RequestVote 请求）。 建议直接在 Raft 结构体中加入一个锁，每次发起 RPC 请求前后都加锁，而 RPC 请求的过程中不能加锁（多个节点互相请求 RequestVote 会造成死锁）。 RPC 函数则直接全程加锁即可。

针对 6.824 实验中的测试用例，测试框架要求 Leader 发送心跳包的频率不超过每秒 10 次，在网络连接良好的情况下则需要在 5 秒内完成选举。 因此发送心跳包的频率可以固定为 100ms 一次，而选举的超时时间可以设置为 200ms ~ 400ms 。

2B 日志同步（Log Replication）

具体过程应阅读论文，以下仅供思路整理。

大致流程

  • 只有 Leader 可以接受客户的写请求，给日志分配一个 index 并将日志追加到自己的 log 中。index 应该是连续且单调递增的。 其他节点不应该接受 Client 的请求。
  • Raft 中的日志有两种状态：提交和未提交。通常由 commitIndex 判断。如果 log 的 index >= commitIndex 则视为已提交。 Leader 刚刚接受请求时该日志为未提交状态，也即如果出现网络错误，该日志可能丢失。 如果日志被过半的节点接收，则该日志变为提交状态，此时 Raft 能保证该日志不会被丢失或覆盖。（实际上存在一些特殊情况，即使日志被过半的节点接收后也不应该提交，见下文分析） Client 也应该在日志被成功 commit 之后才视为请求成功。
  • Leader 通过 AppendEntries 分别向每个节点推送其所需要同步的日志信息。
  • Leader 会为每个节点维护一个 nextIndex 和 matchIndex 值。分别对应“下一次发送 AppendEntries 时附带的 log 的起始 index”（包含）和“节点 log 中的最大 index”（包含）。 初始时，每个节点的 nextIndex 是 lastLogIndex + 1，也即下一次 AppendEntries 不发送任何 log ，用以试探 Follower 最新的 logIndex 。 初始时，每个节点的 matchIndex 是 0。
  • Leader 在发送 AppendEntries 时，会发送从该节点 nextIndex 到最新的一系列 log（即 log[nextIndex:]）。而 prevLogTerm/prevLogIndex 则是这一系列 log 前面一个日志的 term/index，用以辅助 Follower 判断。
  • Follower 在收到 AppendEntries 请求后应该先确认 Leader 的合法性（Leader term 大于等于自己的 term）、更新自己的 term 值。 随后检查自己的 log 是否与发送过来的 log 连续，如果不连续则可能缺失了部分信息，拒绝。 Leader 在收到拒绝之后会减少 nextIndex 以增加发送的 log 量。
  • Raft 保证日志的顺序。因此 Follower 不能随意接受 AppendEntries 发来的 log，需要确认自己最新的 log 和发来的 log 之间是否有缺失的 log 未被推送。 利用 Index 的连续且单调的性质，如果自己的 log[PrevLogIndex].Term == PrevLogTerm，则发来的 log 可以安全的接在 PrevLogIndex 的后面。如果 Follower 存有大于 PrevLogIndex 的日志，则无条件丢弃并与 Leader 同步（见下文分析）。同时根据参数里的 commitIndex 更新自己的 commitIndex。
  • Leader 根据 AppendEntries 返回值，更新维护的 nextIndex 和 matchIndex，以便下次推送。
  • Leader 在确认过半节点成功接受某个日志之后，将该日志提交（存在例外情况，如论文中 Figure 8，见下文分析）。由于 index 的单调性，已提交的日志前也一定已提交，故只需维护最后一个提交的 index 即可（commitIndex）。 此时只有 Leader 认为该日志提交。但是 commitIndex 将在下一次 AppendEntries 时同步给其他节点。
  • 任意一个节点 在 commitIndex 更新之后，需要将日志作用于节点维护的业务层状态机上，并用 lastApplied 维护最后一个已作用于状态机上日志的 index。（可能是为了方便并发，实际上可以直接用 commitIndex 作为 lastApplied ）
  • 为了保证 commit 过的日志不会被丢失，Raft 不能让日志不是最新的节点成为 Leader。因此需要在 2A 中的 RequestVote 中增加一个选举条件，即只有在请求中的 (lastLogTerm, lastLogIndex) 与自己相同或更新时才批准其成为 Leader。 如果某个消息已被 commit ，其必定存在于过半的节点上，因此没有这个消息的节点竞选时必定会被过半的节点拒绝，从而无法当选 Leader。 如果某个消息未被 commit 而某个没有这个消息的节点当选，则在后续的 AppendEntries 中 Follower 将会被强制与 Leader 同步而丢弃此未被 commit 的消息。

分析

  • Raft 中的日志并没有显式的保存日志的 index，而是利用日志在 log 数组中的下标计算得出。 这既可以保证日志的连续性（相邻只差1），也保证了日志的 index 不会随着 Leader 的变化（term 的更新）而改变。
  • Client 在请求 Leader 增加日志时，如果 Leader 返回并且声称日志已提交，则 Raft 能够保证这个日志不被丢失。 而如果这个日志一直未被提交，也不能说明这个日志已经被丢失，因为 Leader 可能在后续的 AppendEntries 中收到过半的确认而将其提交。 因此如果 Client 的请求长时间没有被提交，也不可以随意重复发送请求，只能无止境地等待下去。 为了避免这个问题，现实中通常需要保证这个请求是幂等的，即业务服务器收到重复的请求不会产生副作用。这样当一段时间内没有收到回复时，Client 可以安全地重发请求。
  • Raft 中 Follower 验证 log 的连续性时只使用了请求中的 prevLogTerm/prevLogIndex 信息。原因是同一个 Leader 发来日志的 index 一定是单调递增的。 日志的 index 相同而内容不同说明这个日志是由两个不同的 Leader 发起的，此时日志的 term 也会不同。 这一点论文中也有相应的证明，对任意两个节点，如果他们相同 index 的 log[index].Term 相同，则 index 及 index 之前的所有 log 及其内容都一定相同。 因此只需判断 log[prevLogIndex].Term == prevLogTerm 即可。
  • 当 Follower 拒绝 AppendEntries 操作之后，说明 prevLogIndex > rf.lastLogIndex 或者 log[prevLogIndex].Term != prevLogTerm 。 对于前一种情况，说明发来的日志不足，需要在下一次 AppendEntries 中增加发来的 log（即减少 Leader 中对应的 nextIndex）。 对于后一种情况，说明 Follower 和 Leader 有冲突。如果需要同步同样需要增加发来的 log（即减少 Leader 中对应的 nextIndex），直到某次匹配后安全的覆盖冲突的日志。
  • Follower 收到的 AppendEntries 请求中的 prevLogIndex 可能小于 commitIndex。 这可能是由于网络延迟导致的过期的请求，也可能是上一轮 AppendEntries 时的回复未及时到达 Leader 而超时重发的请求。 此时 Follower 可以安全的忽略这一次 AppendEntires 请求。
  • Leader 在收到 AppendEntries 的返回值，根据 matchIndex 计算新的 nextCommitIndex = median(matchIndex) 时，完全可能出现 nextCommitIndex < commitIndex 的情况。 这是因为之前的 commitIndex 是由上一个 Leader 维护的，而当前 Leader 可能刚刚当选，因为网络或者 Follower 节点宕机并没有收到过半节点的 AppendEntries 回复。 此时可以安全地忽略 commitIndex 的更新。
  • Raft 论文的 Figure 8 中指出了 Leader 更新 commitIndex 时的一种特殊情况。 如果最后一个日志的 term （即 lastLogTerm） 不等于（其实一定是小于） Leader 的 currentTerm，那么即使过半的节点已经收到了这个日志，Leader 也不应该提交这个日志。 这是因为如果 Leader 在提交这个日志之后立即崩溃或掉线时，其他节点还未收到这个日志被提交的消息。 而 2B 为此新增的 2A 选举条件在这个前提下并不生效，新 Leader 可能是完全没收到这个日志中的一个节点，根据 Leader 的权威性其他节点只能被迫丢弃这个日志，从而导致和旧 Leader 的不一致。
  • 在原论文中和 Raft 可视化的演示中，Leader 在 AppendEntries 失败之后即将 nextIndex 减一。不断重复尝试 AppendEntries 直到 Follower 接受发出的日志。 但是由于每次 nextIndex 只减一，在某个节点长时间下线后 Leader 将会尝试非常多次之后才能成功同步，且每次 AppendEntries 将会携带大量 log。 因此 Raft (extended version) 中提到了一种优化，在 AppendEntries 的返回值中额外携带一个 nextIndex，由 Follower 指定下一次尝试的 Index，可以跳过大量的无用尝试。
  • 如果需要实现 nextIndex 的优化，在 prevLogIndex > rf.lastLogIndex 时可以直接返回 rf.lastLogIndex + 1 作为 nextIndex。 而如果是 log[prevLogIndex].Term != prevLogTerm 则需要在 Follower 中找到第一个 term 与 prevLogTerm 相同的日志，返回该日志的 index + 1 作为 nextIndex。

实现细节

2A 部分几乎已经实现了 2B 部分所需的所有数据结构和 RPC 函数。因此 2B 部分只需要根据流程和分析完形填空即可。

2C 持久化（Persistance）

目前 Raft 节点的所有信息包括 log 均存于内存之中。如果程序 crash 了，重启后该节点的所有数据都将丢失。

这本身不在 Raft 协议的容错范围之内。 因为如果某个日志已被 commit，但是拥有该日志的部分节点因为 crash 丢失了日志信息，从而拥有该日志的节点数回到了半数以下。 此时如果发生竞选则可能丢失已经 commit 的日志并引发致命的错误。

而持久化能够保证在节点发生 crash 后重新上线时仍然拥有 crash 之前的日志，从而给 Raft 集群提供 crash 的容错。

在论文的 Figure 5 中已经给出了实现持久化时需要保存的三个状态：currentTerm、votedFor 和 log。 其中，currentTerm 和 votedFor 共同保证了节点在选举期间发生 crash 时不会重复投票；log 保证了已被 commit 的日志不会被丢失或覆盖。 其余状态都可以在上线之后重新计算或同步，不会对 Raft 的运行产生致命的影响。

而该部分的代码非常简单，即在每一次完成 RPC 调用且对持久状态有修改之后保存一次节点的状态。重启时恢复这三个状态即可，其余状态（包括身份）都重置为初始值。 需要注意的是对持久化的数据也需要保证修改的原子性，也即不可在修改的某个中间状态保存。

实现细节

几乎不需要修改 2B 的代码，只需要在代码中批量查找 rf.currentTerm 、rf.votedFor 和 rf.log 的修改位置，在每一次修改之后调用 rf.persist() 保存状态即可。

2D 快照（Compaction/Snapshot）

当 Raft 运行相当一段时间之后，会产生大量的日志，占用大量的内存。 同时对某个下线已久的节点而言，同步到最新的状态将会消耗非常大的资源。

快照是对 Raft 维护的状态机的持久化。 如果有一个状态机的快照，则所有快照之前的日志都可以丢弃。 如果某个节点需要同步快照之前的日志，Leader 可以直接发送快照从而直接同步到快照的状态，然后在此基础上进行 AppendEntries 。

快照可以在任意一个节点上独立地进行，且快照的状态可以和 Leader 不同。

在实验中，快照由业务服务器发起。 首先业务服务器对业务的状态机创建快照，同时记录下创建快照时 Raft 日志的 Index 和 Term。 随后调用 Snapshot 函数通知 Raft 服务，使其可以安全的丢弃快照前的所有日志。 之后的通信中 Leader 会基于新的快照同步其他节点。

如果某个节点落后过多，Leader 会发起 InstallSnapshot RPC，并发送自己的快照。收到快照的节点首先使用 ApplyMsg 通知业务服务器，业务服务器在准备完毕后调用 CondInstallSnapshot 确认是否应该安装这个快照（在不与 Leader 状态冲突的情况下，状态机比快照更新则不必安装快照）。在 CondInstallSnapshot 确认安装之后也应该在返回之前同步修改 Raft 节点的内容。

实现细节

相比于 2B，2D 需要在 Raft 中增加 snapshotIndex 和 snapshotData 两个变量，分别记录快照中包含到的最后一个日志的 index 和快照的二进制数据。这两个变量需要在 Raft 的持久化（2C）中保存。

在需要时，客户端会主动调用 Raft 的 Snapshot 方法。 此时 Raft 应该删除参数中给定 index 及之前的所有日志，将 index 和 data 保存到 snapshotIndex 和 snapshotData 中，并调用 persist 保存状态。 由于我们约定了 log[0] 的特殊性，因此也可以直接用 log[0] 表示快照中存有的最后一条日志，其 term 和 index 设为对应值，避免了在 2B 中再次特殊处理快照的逻辑。 同时，2B 中所有对 rf.log 的下标引用都应该减去 snapshotIndex ，RPC 中的 prevLogIndex 则不需要修改。

Leader 在发起 AppendEntries 前则需要增加一个特殊判断。如果对应 peer 的 nextIndex 大于等于 snapshotIndex，则直接正常发起 AppendEntries RPC 同步日志即可。 而如果 nextIndex 小于 snapshotIndex，则需要发起 InstallSnapshot RPC 。 InstallSnapshot RPC 只需要发送快照本身，Follower 在确认通用的 RPC 检查通过之后直接清空自己的日志并通知业务服务安装快照即可。 快照之外的日志将由后续的 AppendEntries RPC 同步。

在向 applyCh 写入信息时，测试框架可能因为日志达到一定数量而调用 rf.Snapshot 创建快照。 因此在 applyCh 写入信息时需要保证此时没有持有锁，否则在 Shapshot 中加锁时可能造成死锁。

关系图谱