MIT 6.824

Raft QA

Raft 主要在什么场景中使用

• 元信息服务，也称为配置服务、分布式协调服务等。用以追踪集群中元信息（如哪些机器、副本位置）、多副本选主等。
• 数据复制（系统中存储的数据），使用 Raft 作为数据复制和冗余的一种手段。与之相对，GFS 使用简单的主从复制的方法来冗余数据，可用性和一致性都比 Raft 要差。

Raft 为了简洁性做了哪些牺牲（性能问题）

• 每个操作都要落盘。如果想提高性能可能需要将多个操作 batch 起来。
  主从同步数据较慢。在每个 Leader 和 Follower 之间只允许有一个已经发出 AppendEntries；只有收到确认了，Leader 才能发下一个。类似 TCP 中的“停等协议”。如果写入速度较大，可能将所有的 AppendEntries Pipeline 起来性能会好一些（即 Leader 不等收到上一个 AppendEntries 的 RPC Reply，就开始发下一个）
• 只支持全量快照。如果状态机比较小这种方式还可以接受，如果数据量较大，就得支持增量快照。
• 全量快照同步代价大。如果快照数据量很大，每次全量发送代价会过高。尤其是如果 Follower 本地有一些较老的快照时，我们只需要发增量部分即可。
• 难以利用多核。因为 log 只有一个写入点，所有操作都得抢这一个写入点。

Raft prevote机制

节点 A 和其他节点发生网络隔离后，会不断发起选举但一直无法当选，推高 Term。等网络恢复通信后，由于 A 的 Term 最高，会强迫当前的 Leader 下台，重新选主。但由于在隔离期间日志被落下很多，A 通常也无法成为 Leader，最终大概率是原来的 Leader 的 Term 被拉上来之后，重新当选为 Leader。这个过程形象的称之为“惊群效应”。

PrevVote机制：每次发起选举时，不再推高 Term，但是会拿着 Term+1 去跟其他 Peer 要票，如果能要到合法的票数，再去推高 Term。

• 如果能要到多数票就保证了没发生网络隔离、日志是最新的
• 如果要不到多数票，就不能推高 Term，防止网络隔离的节点一直推高 Term。

新任期leader为什么同步no-op日志

因为leader选举的一个依据是日志的新旧程度(lastLogIndex)，但是受限于从节点的日志复制进度，commitIndex <=lastLogIndex。所以如果在一个新任期的开始，客户端的读(commitIndex, lastLogIndex]之间的日志，可能读取的是未提交的数据。

因此规定在任期开始时，leader会在处理所有读请求之前写入一个”no-op”日志，主节点的lastLogIndex自增，然后将(nextIndex[i], lastLogIndex]区间的日志发送给响应的从节点，这样当多数从节点接收到后，leader节点可以提交这个日志项，commitIndex更新为lastLogIndex，确保读到最新数据。

“no-op”日志即只有 index 和 term 信息，command 信息为空，也是要写到磁盘存储的。

本质原因：新Leader当选后，旧任期的日志只能通过commit自己任期的日志来捎带提交，如图 Raft-figure8 所示：

(c)中S5刚写完一条日志就挂了，S1重新当选Leader，Term=4。此时还没有新的请求写入，如果S1将此前的index=2 && term=2 的日志append到多数节点并提交了（埋下了隐患）
(d)中S1又挂了，S5重新当选，并将 index=2 && term=3 的日志复制到其他节点并提交，此时 index=2 的日志提交了两次，已提交过的日志被覆盖了！！！

虽然加了这个约束不会重复提交了，但如果一直没新的请求进来，旧term的日志迟迟无法提交，Leader 查到日志有记录但又不能回复，线性一致性要求不能返回陈旧的数据，Leader 迫切地需要知道这条日志到底能不能提交。

因此需要在 Leader 刚选举成功的时候立刻追加一条”no-op”日志，”no-op”日志一经提交，隐式地提交了之前任期未提交的日志，确认当前 commitIndex。

Raft 和 Paxos 有什么区别

• Raft 和 Paxos 都是共识协议，而所有的共识协议在原理上都可以等价为 Paxos，共识协议本质上都是 Paxos。
• Raft 是为了解决 Paxos 理解和实现都相对复杂的问题。将共识协议拆成两个相对独立的过程：领导者选举和日志复制，以降低理解和实现的复杂度。
• Raft 其实是和 Multi-Paxos 等价，因为 Paxos 只解决单个值的共识问题。
• Paxos 只要某个日志在多数节点存在后就可以安全提交；但在 Raft 中如果不是当前任期的日志，即使超过半数也不能直接提交，只能通过提交当前任期的日志来间接提交。
• 在Paxos 在选举时，Leader 可能需要借机补足日志，但 Raft 中选举过程完全不涉及日志复制，因为只有具有最新日志的 Candidate 才能成为 Leader，而 Paxos 不限制这一点。
• Paxos 允许乱序 commit 日志，而 Raft 只允许顺序提交。
• Paxos 每个节点的 term 是不一致的，全局自增；在 Raft 中 term 每个节点独立自增，但需要对齐。

Raft 在工程中有哪些常见的优化

由于领导者选举是个低频操作，主要 IO 路径优化还是集中在日志同步流程上。

• batch：Leader 每次攒一批再刷盘和对 Follower 进行同步。降低刷盘和 RPC 开销。
• pipeline：每次发送日志时类似 TCP 的“停-等”协议，收到 Follower 确认后才更新 nextIndex，发送后面日志。其实可以改成流水线式的，不等前面日志确认就更新 nextIndex 继续发后面的。当然，如果后面发现之前日志同步出错，就要回退 nextIndex 重发之前日志——而原始版本 nextIndex 在同步阶段是单调递增的。
• 并行 append：Leader 在 append 日志到本地前，就先发送日志给所有 Follower。

简述基于 raft 的分布式 KV 系统的架构

一个基于 raft 的分布式 KV 系统，实际上是由一组使用 raft 算法进行状态复制的节点组成。客户端会选择将请求发送到 Leader 节点，然后由 Leader 节点进行状态复制，即发送日志，当收到多数的节点成功提交日志的响应之后，Leader 会更新自己的 commitIndex，表示这条日志提交成功，并且 apply 到状态机中，然后返回结果给客户端。

以上是单个 raft 集群的分布式 KV 系统架构。如果系统中数据量较大，一个 raft 集群可能无法承受大量的数据，性能也会受到影响。因此还基于此设计了可分片的分布式 shardkv 系统。shardkv 由多个 raft 集群组成，每个集群负责一部分 shard 数据。Shard 到 raft 集群的映射关系，保存在独立的配置服务中。

如何处理客户端的重复请求

如果客户端的请求已经提交，但是 server 返回的过程中结果丢失，那么客户端会发起重试，导致这个请求在状态机中被执行了两次，会违背线性一致性。

因此需要保证客户端的请求只能被状态机应用一次，可以维护一个去重哈希表(duplicateTable)，客户端 ID + 命令 ID 组成一个唯一的标识符，
每次请求的时候，判断 map 中是否存在这个命令，有就则直接返回结果，而不用再发送到 raft 模块进行同步。

还需注意的一个细节：一个客户端只会重试当前最新的这个命令，对于已经成功执行的命令就没必要重试了，因此去重 map 只需要为每一个客户端存储一个当前最新的命令即可。

这样做有一个前提：客户端默认在同一个时刻只会有一个命令，即一个 Clerk 内部是不会有并发的请求的

Shard 数据如何迁移

启动一个后台定时任务，定期从配置服务中获取最新的配置，如果检测到配置发生变更，则变更对应 shard 的状态，标记为需要进行迁移。

同时启动另一个后台定时任务，定期扫描 shard 的状态，如果检测到需要进行迁移的 shard，则发送消息，通过 raft 模块进行同步。然后在 Leader 节点中处理 shard 迁移的请求，将 shard 数据从原所属的 raft 集群中迁移到新的集群中。

如何处理 Shard 迁移与客户端请求的关系

如果客户端请求的 key 所属的 shard 并没有在迁移中，那么可以正常提供服务。否则则返回错误，让客户端进行重试。

此外，客户端请求和 shard 迁移请求存在并发情况，需要保证线性一致性。因此将 shard 迁移的请求也传入到 raft 模块进行同步，这样和客户端的请求是一致的，利用 raft 的一致性来保证两种不同请求的先后顺序，前面的执行结果一定对后续的请求可见。

线性一致读

什么是线性一致读

所谓线性一致读，一个简单的例子是在 t1 的时刻我们写入了一个值，那么在 t1 之后，我们一定能读到这个值，不可能读到 t1 之前的旧值。即当 Client 向集群发起写操作的请求并且获得成功响应之后，该写操作的结果要对所有后来的读请求可见。

为什么有线性一致的问题

实现共识算法并不意味着能线性一致。共识算法只能保证不同节点对 Raft Log 能达成一致，但 Log 后面的状态机的一致性没有做详细规定，用户可以自由实现。例如 TiKV 在将 commit 的 Log 应用状态机（RocksDB）上时，可推出各个 TiKV 状态机的状态能达成一致，但不能保证同时将某个 Log 应用到 RocksDB 上，即各个节点不能实时一致，加之 Leader 会在不同节点之间切换，所以 Leader 的状态机也不总有最新的状态。Leader 处理请求时稍有不慎，没有在最新的状态上进行，这会导致整个系统违反线性一致性。

Raft LogRead

每个 read 都有一个对应的 Op log，和 write 一样都走一遍一致性协议的流程。这个方法依据 commit index 对所有请求都做了排序，Log 是严格全序的，将这些 R/W 操作一个一个应用到状态机，所得的结果必定符合线性一致性。

缺点：RPC 和 Log 开销、性能差（所有请求被序列化了，无法并发的操作状态机）

ReadIndex

由于只读请求并没有需要写入的数据，因此并不需要将其写入Raft日志，而只需要关注收到请求时leader的commit index。只要在该commit index被应用到状态机后执行读操作，就能保证其线性一致性。因此使用了ReadIndex的leader在收到只读请求时，会按如下方式处理：

1. 确认 read 返回的数据的哪个点？记录当前的commit index，作为read index; 如果新 Leader 不知道最新的 committ index，则提交一个 No-op log entry 来提交之前的 log entry
2. 确认当前的 Leader 是不是还是 Leader？避免网络分区时 Leader 被孤立的情况。向集群中的所有节点广播一次心跳，是否收到了过半数量的心跳响应
3. 等到 leader 本地的apply index >= read index，此时可以保证只读操作的线性一致性，让状态机执行读操作并返回结果

缺点：每次 read 发送心跳开销太大

Lease read

为了减少了 ReadIndex 每次 read 发送 heartheat 的开销，每次 leader 发送RPC的时候，会首先记录一个时间点 start，当系统大部分节点都回复时，就可以认为 leader 的 lease 有效期可以到 start + election timeout + clock drift bound（正负未知） 这个时间点。因为 follower 至少在 election timeout的时间之后才会重新发生选举，所以在Election Timeout内只需要确认一次即可

缺点：对分布式系统的时钟准确性要求很高，否则可能会出现不一致

Follower read

TiKV的特性：当客户端对一个 Follower 发起读请求的时候，Follower 会请求此时 Leader 的 Commit Index，然后等本地 Apply 到 Leader 最新的 Commit Index 后，自己将这条数据返回给客户端。从而显著减轻 Leader 的负载，并提高读取性能。

缺点：

• 需要额外的通信延迟，因为每个读请求都需要先去询问领导者最新的commitIndex，所以减低延迟不明显，但好在优化读吞吐。
• 破坏线性一致性：由于Apply是异步的，Follower 可能比 Leader 先 Apply 这条记录，这样在 Follower 读到这条记录时，Leader 过一会才能读取到。但是好在是永远返回最新的数据。

ShardKV

分布式 KV 服务将是一个复制状态机，由几个使用 raft 进行状态复制的 kv 服务节点组成。分布式 KV 服务需要保证在集群大多数节点正常的情况下依然能够正常提供服务，即使有一些其他的错误或者网络分区。

架构图

主要流程

客户端

客户端 Clerk 会向 KV 服务发送三种类型的请求：Get/Put/Append。

保证线性一致性：要求客户端的修改对后续的请求都是生效的，即其他客户端能够立即看到修改后的结果，而不会因为我们的多副本机制而看到不一样的结果，最终的目的是要 kv 服务对客户端来说看起来“像是只有一个副本”。

服务端

服务端的 KVServer 描述了一个 kv server 节点所维护的状态。里面维护了一个 raft 库中的 Raft 结构体，表示其是一个 raft 集群中的节点，它会通过 raft 提供的功能向其他的 KVServer 同步状态，让整个 raft 集群中的数据保持一致。

1. 服务端收到请求后，先存储到 raft 日志中，然后等待 raft 模块同步完成，等待 notifyCh 中的状态机操作结果
   • raft 集群中的 Leader 节点处理了 Start 请求之后，会将日志同步到其他的 Follower 节点。
   • 当多数的节点都正常处理之后，Leader 会更新自己的 commitIndex，然后将日志通过 applyCh 这个通道发送过去。
2. 服务端启动 applyTask 后台线程，从 applyCh 中接收来自 raft 的日志消息。取出的日志消息对应的 Operation 已在节点间中同步完成，因此将 Operation 应用到本地状态机中，把返回结果（读到的值/写是否成功）存储到 notifyCh 中。
3. 这时 Get/Put/Append 方法就能从这个 notifyCh 中获取到结果，并返回给客户端。

参考链接

6.824 Schedule: Spring 2022
Students’ Guide to Raft
MIT 6.824 distributed systems 2022
简介与课程翻译|6.824
MIT 6.824涉及的部分论文翻译
GeminiCx/6.824-2022
MIT6.824-lab3AB-2022（万字推导思路及代码构建）
2021 MIT 6.824 札记
2022-6.824-Lab2:Raft
Raft 算法、分布式 KV 面试汇总