MIT 6.824 2020 (3) Fault-tolerant Key/Value Service实现笔记

该博客主要关注功能实现，Read Lease等优化之后有时间填坑：）

Basic Q&A

首先需要问自己这些问题，想清楚后后就能理解server层和raft层之间的交互逻辑了。

Q:对于client来说，在进行read请求时，是向leader发送（保证得到最新的数据），还是向任意一个节点发送呢？

A:client的读写请求都向leader发送，如果不知道leader是谁，就随机向一个server进行询问。raft通过这种方式保证了线性语义（强一致性），但是损失了读性能（这与zookeeper是相反的）。

Q:raft在进行写请求的时候，如果随机选中了一个旧的leader（比如在一个非majority的parition中的旧leader)，那写请求的拒绝执行是通过什么机制实现的？

A:请求的回复应该是阻塞的，得等到leader确认该log被复制到大多数replica时，才能给出一个promise；所以，作为leader的server需要有处理请求超时的逻辑，防止自己是minority的旧leader，无法commit客户端的请求却久久不释放客户端连接。

Q:为什么每个leader的term期开始时都要追加一个no-op log？

A:因为leader只能提交当前term期的log, 通过no-op log日志的提交能够间接提交之前的term期的未提交日志，这样能够保证leader在自己拿到任期后能尽快地进入可读状态。（原文中说的是leader可以尽快知道commit index,本质上说的是一样的事）。

Q:server需要维护每个client的最后请求的序列号一防止重复执行，那这个信息是由leader在AP rpc里同步到followers吗？

A:对，所以ClientId和Seq这两个信息都要作为log entry的一部分，followers commit的时候，server层可以可以根据根据这个进行去重。防止一个请求被apply多次。

开始编码前的建议

个人感觉这部分比lab2要难调试一些，回顾起来，主要有两方面：遇到了很多死锁的问题；加上server和client后，log更多了，看起来比较吃力。所以，有以下推荐：

• 跑测试的时候，把-race打开

• 用logrus库来代替std log，支持多日志级别

• 调试时借助死锁检测工具，如go-deadlock

Part A: Key/value service without log compaction

线性一致性

要满足线性一致性，可以理解为对于同一个数据对象，一个Read请求，一定要读到“在时间上最新的”已经返回Success的write请求的数据。考虑这么一个场景，网络分区发生了，一个follower被选举为了新的leader，他的commit index其实可能是小于旧leader的，所以他的数据其实是旧的，那么如果这时候来了一个Read请求，他该如何操作，才能保证这个Read请求读到的是最新的数据呢？

最自然的想法就是将read也作为一个cmd，放在log里进行replica，这个log commit后，再返回read的结果，这样就能保证读到的是最新的数据了。这个线性顺序也就是log提交的顺序。

当然，这不是必须的，有Read Lease/ follower read等优化。

请求超时

做partition3A时遇到了问题处于minority的leader旧久久不释放客户端请求的情况，这里我为server端增加了一个处理请求超时时间为1s，过了1s如果leader没有收到raft层的consensus，直接返回timeout Err。然后为client端增加超时换target server重试的逻辑。

添加NO-OP log的位置

2023.11.17 要在两个地方加NO-OP日志, 一个是选举成功成为新leader后，另外一种作为leader，收到其他节点的RV rpc请求，发现Term比自己高，但是其log日志落后所以拒绝时，要更新自己的CurrentTerm，然后这里还要添加NO-OP!

我的设计中，希望重复的log不要放到raft的log中，所以我是在kv.rf.Start前就做了去重操作；清华佬的想法相反，在log commit并且apply时再进行去重操作。

记录结果

关于是否需要记录最后一次session的结果的问题，我之前没有想过，因为我认为记录的是旧的结果，这会违反线性一致性。举个例子，比如一个Get操作，第一次超时了，但是leader成功commit并记录了结果，那Get操作重试时，如果直接返回这个结果，那这就是旧数据，因为client重试的这段时间可能这个数据又发生改变了。但是后来偶然看到这位大佬认为需要记录结果。论点如下：

为什么要记录应用的结果？因为通过这种方式同一个命令的多次 apply 最终只会实际应用到状态机上一次，之后相同命令 apply 的时候实际上是不应用到状态机上的而是直接返回的，那么这时候应该返回什么呢？直接返回成功吗？不行，如果第一次应用时状态机报了什么例如 key not exist 等业务上的错而没有被记录，之后就很难捕捉到这个执行结果了，所以也需要将应用结果保存下来。

我觉得有道理，所以记录结果是必要的。

那么，这样满不满足线性一致性呢？

其实如果将client和server看做是一个整体系统，那么实际上是满足线性一致性的。从调用client的Get和Append、Put的接口的角度来说，由于client的逻辑中向外部隐藏了超时重试的逻辑，知道成功得到结果才会返回给调用者，所以从外界来看，这是个线性一致的系统（包括测例也是这样测的）。由于测例里就是从调用client的接口测的，所以测出来是满足线性一致性的。

我之前没有记录结果，依然通过了所有测例，究其原因，是因为：Get接口本身就不需要，读最新的数据是符合线性一致性的；而在这个lab里，Put,Append是一定会成功的，即一定能够成功执行，不会出现‘ key not exist 等业务上的错而没有被记录’这种情况。如果将Append语义改为不存在key,则返回KeyNotExistErr的话，那就必须记录结果了。

cmd去重的时机

2023.11.18 遇到了问题，发生网络分区时，leader发生变化后，原leader上没处理完的session会timeout，如果该session对应的日志已经成功replicate了但未提交，那么其对应replica的raft日志中也有这条日志了，且没提交，如果该replica在网络分区后被选为了新的leader，由于server层对下层raft中未提交的日志是无感知的，如果此时之前timeout的client如果在这个新leader上进行重试，重新开始这个session，由于server层无法进行去重判断，也就无法保证其向下传递的raft日志是唯一的！

结论：去重操作无法在建立session时判断，raft中的log也无法保证唯一性，只能将去重操作后移到提交时进行。

2023.11.20

发现下层raft有bug，即leader在等待AppendEntires回复时，由于会释放自己的锁，所以这段时间内自己的term、log都有可能改变，在接到回复后判断要考虑周全。这种情形在分布式系统中应该很常见。

另外一个细节问题，session需要对结果结果进行过滤，Result中要加入Client+Seq信息来表示这是个结果的Seq，session收到的如果是旧的Seq则需要丢弃，并继续等待。

测强一致性的这个测试点 TestPersistPartitionUnreliableLinearizable3A 官方代码设计得很好，用15个节点并发对7个server发送随机请求，并记录下每个请求开始和结束的时间点，如果测例发现你的实现不满足线性一致性，那最终会生成一个Porcupine的html文件，将整个过程可视化！第一眼看到有点惊艳的，就像当时看CMU15445 bustub的B+树的可视化工具一样，不知道问什么对这种visualization毫无抵抗力。我一开始没过这个测例，马上发现我把Append的语义理解错了，Append在key不存在时，应该相当于Put，而我是把他当异常处理的，修改后就过了。

Part B: Key/value service with log compaction

basic snapshot

Snapshot可以视为从index=0开始的一段连续log的compaction结果，由于raft层是对log内容无感知的，所以这个snapshot是由上层进行，然后通知raft层丢弃之前的log以减少raftstate的存储空间的。

值得注意的点：

Snapshot是对于已经Applied的log来说的，不会对没有提交的log进行compaction。

Snapshot中要存的信息：lastIncludedIndex, lastIncludedTerm，data。存lastIncludedIndex和lastIncludedTerm的原因论文中有讲，是为了在Snapshot后没有新log的情况下，能够处理RV和AP的rpc请求。我自己的实现中，将lastIncludedIndex和lastIncludedTerm存在了raft state中。

Snapshot是快照，持久化时应该将log清零并持久化，所以应该同时将被改变的state也持久化。

Snapshot和raftstate是分开存储的，正常情况下只需要持久化raftstate，只有compaction时才会涉及到snapshot。

type Persister struct {
   mu        sync.Mutex
   raftstate []byte
   snapshot  []byte
}

要做的事情，server层snapshot的持久化实现，如下:

• server层根据 raft层提供的接口，比如 rf.NeedCompaction(maxraftstate)来判断是否需要进行compaction,，如果大于maxraftstate了，则返回true。NeedCompaction的调用位置可以是server层每次apply新log后。
• raft层实现接口SaveStateAndSnapshot(snapshot_last_index int, data map[string]string)，该函数阻塞式地进行持久化，将写入文件

maxraftstate的含义如下，即被持久化的raft state的大小。raft state包括 Term、votedFor、log，之前做lab 2的persist中已经涉及过了。

maxraftstate indicates the maximum allowed size of your persistent Raft state in bytes (including the log, but not including snapshots)

• raft层log的总长度的需要提供接口GetLen()，total_len = snapshot_len + len(log)
• server恢复时，首先需要使用kv.kvdata = rf.ReadSnapshot()来读取快照。

InstallSnapshot RPC

由于Snapshot的形成时机是由上层server层判断的，各个server节点可以根据本节点的raft state大小独立进行Snapshot。一个leader在进行snapshot后，会丢弃之前的已经commited的log，如果此时有落后很多的或者新加入的follower需要snapshot之前的log的话（nextIndex < snapshot.last_index)，leader是无法给出的，所以这时候就需要leader调用follower的InstallSnapshot RPC来将整个Snapshot传输给他。

InstallSnapshot RPC的实现上，有以下：

• InstallSnapshot的参数，term, snapshot，论文Figure 13里的offset和done参数都不需要（这个设计很像IP报文的分段传输字段的设计），因为我们不需要实现分chunk传输。返回参数，term。
• InstallSnapshot的逻辑：首先判断term期，term期小于自己的term直接return。然后看自己的log长度，如果log没这么长,则施行持久化Snapshot；再看对应lastIncludedIndex位置的log的term和lastIncludedTerm是不是相同，如果entry相同，则施行持久化Snapshot，并保留lastIncludedIndex之后的log；如果不相同，则之后的log都是错的，所以持久化Snapshot后直接丢弃即可。

其实个人感觉snapshot没必要放在raft层进行持久化，语义上server层保留并持久化更符合直觉，raft层只需要知道lastIncludedIndex和lastIncludedTerm就好了。

2022.11.22 跑TestSnapshotSize3B发现超时了，把HeartBeatInterval和UpdateCommitInterval改小就过了。

2022 11.23 修了些小bug, 通过了所有测例，重复执行 TestSnapshotUnreliableRecoverConcurrentPartitionLinearizable3B 这个测试点500次没有都没有遇到问题，就当PASS了（跑得真慢啊，没关log跑了二十多分钟）。

Q:为什么要分chunk传输？

A:论文里说是为了维持心跳？我觉得分chunk主要是链路层的最大报文长度是有限制的。我不懂，知道的同学请告诉我：）

future work

• 现在本质上处理log的逻辑还是单线程的，会导致一个client拖累后面的client的处理，其实可以可以考虑改造成分发的形式

• Read Index（Read Lease） / Follower Read

  这篇博客讲了etcd对于读的优化。为了达到线性一致性，那在处理get请求时leader就不能返回旧的数据回去，那能不能直接返回结果呢？答案是不能，因为在发生网络分区时，一个leader有可能只是minority的leader，它的状态机可能是落后与majority的leader的，如果直接返回结果，那就可能返回旧的结果，违反线性一致性。这里我采取的方法是将Read请求也作为一个log放在log队列中，等到commit到这个log时，再给client回复，我这里为了能。

  更好的做法其实是采用Read Index的方法，即leader收到get请求时，记录一下当前的commit index作为read index，然后再向所有成员发送一次心跳，如果收到大部分的成员的回复，那说明自己仍然是leader，这时就可以等待apply到read index（commit的过程是异步的，假设a=1，前leader apply并完成了一个put a = 2的请求然后挂掉了，新leader当选后，自己的状态机可能还是apply index < commit index的状态，那这时候如果不等apply index赶上commit index，那就会返回旧的数据a=1; 还要考虑到commit index本身也会滞后于前leader，所以在更新前，可能得保证自己任期的no-op log的心跳收到了大多数回复，commit index赶上了上任leader）时，再回复结果。从线性顺序上，可以认为这个get请求发生在read index上。read index相比于我这个naive的做法优势很明显，一方面将等待时间从last index commit(我这么称呼的，因为read log是放在log队列末尾的) 缩短到了commit index commit（更正：其实这一点算不上优化，因为还是需要发送心跳，并接收到大多数节点的success回复，这和将Read log这条log进行majarity replicate的网络时间消耗是一样的）；另一方面，大大减少了log的大小，从而减小compaction（snapshot）发生的频率。

  还有点值得注意的是，对于一个leader来说，需要先至少提交一次自己任期的log后，才能开始对外提供Read服务，这是因为leader在一开始是不知道commit index是多少的(或者说commit index初始化为0)，所以无法进行Read Index；这个约束对应着raft论文里“leader只能提交自己term期的log”这条规则。

  Read Lease是在Read index上的优化，为了减小leader的读延迟。即leader处理get请求时，不需要每次都去询问其他所有成员，而是在租约内直接给client答复。要点是租约严格小于election timeout的时间，这样就能保证租约内不会出现新的leader。租约通过每次AP rpc请求来进行续约。

  而Follower Read也是在Read index上的优化，为了扩展读性能。以上方法本质上还是由Leader来处理读请求，所以follower再多，也只是看戏，整体读性能也不会提升。而Follower Read参考PingCAP CTO的博客：

  如何保证 Follower 上读到最新的数据呢？最土的办法就是将请求转发给 Leader，然后 Leader 返回最新的 Committed 的数据就好了嘛，Follower 当做 Proxy 来用。这个思路没有任何问题，而且实现起来也很简单还安全。但是，很明显这个地方可以优化成：Leader 只要告诉 Follower 当前最新的 Commit Index 就够了，因为无论如何，即使这个 Follower 本地没有这条日志，最终这条日志迟早都会在本地 Apply。

  TiDB 目前的 Follower Read 正是如此实现的，当客户端对一个 Follower 发起读请求的时候，这个 Follower 会请求此时 Leader 的 Commit Index，拿到 Leader 的最新的 Commit Index 后，等本地 Apply 到 Leader 最新的 Commit Index 后，然后将这条数据返回给客户端，非常简洁。

  其实Follower Read我认为是牺牲了读延迟来来换取可扩展性，说他牺牲了读延迟是因为Follower向Leader请求ReadIndex的过程需要多消耗一个RTT。所以，我认为要兼具读延迟和较好的可扩展性，更好的办法是使用multi-raft，并将每个shard的LeaseOwner均分到各个机器上，每个shard都由各自的LeaseOwner来处理读写请求。CockroachDB的multi-raft选择的是这种做法，它的每个shard都大约为64MB，shard过大了或者过热了会进行分裂，它能够通过检测各个shard的访问热度以及在各个机器上的分布情况，去做负载均衡，保证各个机器的负载差不多。

• raft成员变更。该博客讲解了raft中的成员变更。raft成员变更的方法可以分为两阶段变更和单步变更。论文中的Section 6, Cluster Membership Changes，增加了一个JoinPhase阶段，该阶段内的RV以及Commit Log时，都需要分别获得$C_{old}$和$C_{new}$(C用来表示configuration，即raft集群含有的node是哪些）中的多数派的同意，这样就避免了两个多数派同时出现时，可以分别单独进行决策的情况。

• raft snapshot copy-on-write?

参考资料

http://nil.csail.mit.edu/6.824/2020/labs/lab-kvraft.html 官方handout

https://tanxinyu.work/consistency-and-consensus/#etcd-%E7%9A%84-Raft etcd

https://zhuanlan.zhihu.com/p/78164196 Ed huang谈Raft读性能优化，以及对TiDB跨数据中心的容灾展望