参考 Coroutines for Go，Coroutine Wiki。

什么是协程（coroutine）？通常使用的函数（function）也被称为子例程（subroutine），一系列调用会形成一个调用栈（call stack），调用者（caller）和被调用者（callee）是父子关系。而协程不同，协程之间是对等关系，每个协程都有一个调用栈。协程有非对称和对称两种实现，非对称协程使用 resume 和 yield 关键字，调用者使用 resume 恢复某个协程，被调用者使用 yield 暂停当前协程，然后控制会转移到调用者。对称协程只使用 yield 关键字，但是需要指定将控制转移给哪个协程。经典的例子，比较两个二叉树是否包含相同的序列（中序遍历），代码。

协程的控制转移是主动的（非抢占式），不需要操作系统支持，也不需要使用锁和信号量等同步原语。线程的控制转移是被动的（抢占式），由操作系统调度，上下文切换更加昂贵，需要使用同步原语保护共享变量。协程只提供并发性，而线程可以利用多核 CPU 实现并行。切换的速度，协程最多 10 纳秒，线程几微秒，Goroutines 和 Virtual Threads（Java 21） 几百纳秒。

网络上各种术语的解释很混乱，根据多线程模型，我倾向于使用用户线程和内核线程的对应关系，来描述不同的实现。简单描述一下我的理解：平常使用的是一对一模型，Goroutines 和 Virtual Threads 使用的是多对多模型。协程不能简单的看作多对一模型，协程是非抢占式的用户线程，描述的是多个用户线程之间的协作关系，实际上可以在各个模型上实现协程。

---

关于 Goroutines 的实现，可以看 Dmitry Vyukov 的演讲 Go scheduler: Implementing language with lightweight concurrency。其他资源：Scalable Go Scheduler Design Doc，The Go scheduler，HACKING。

简单的设计，使用一对一模型 + 线程池，缺点是线程的内存占用较大，Goroutine 阻塞会导致线程阻塞，没有“无限数量”的栈。所以，使用多对多模型，Goroutine 占用内存更小，可以被 Go runtime 完全控制。如果 Goroutine 因为锁/通道/网络 IO/计时器而阻塞，Goroutine 将会进入阻塞队列，运行此 Goroutine 的内核线程不会阻塞，Go runtime 可以从 Run Queue 中调度 Runnable 的 Goroutine 到该内核线程上（复用，Multiplex）。

但是，当 Goroutine 进行系统调用，控制将从 Goroutine 转移到系统调用处理程序，Go runtime 是无法感知该处理流程的，直到系统调用返回，所以此时运行 Goroutine 的内核线程是无法被复用的。有可能所有内核线程都阻塞在系统调用上，而该系统调用所需的资源被某个 Runnable 的 Goroutine 持有，从而发生死锁。所以在系统调用发生时总是会创建/唤醒一个内核线程，执行 Run Queue 中的 Goroutine。当内核线程从系统调用返回，Go runtime 将内核线程上的 Goroutine 放入 Run Queue，使该内核线程空闲从而保证指定的并行度（由 GOMAXPROCS 指定）。

关于 GOMAXPROCS，runtime 文档的描述如下：The GOMAXPROCS variable limits the number of operating system threads that can execute user-level Go code simultaneously. There is no limit to the number of threads that can be blocked in system calls on behalf of Go code; those do not count against the GOMAXPROCS limit.

该实现的瓶颈在全局的互斥锁（MUTEX），内核线程创建 Goroutine 以及获取 Goroutine 都需要操作共享的 Run Queue。解决方案很容易想到，就是为每个内核线程创建本地变量，从而避免频繁访问全局的共享变量。该方案会增加获取下一个 Goroutine 的复杂性，Go 调度器实现的获取顺序是， Local Run Queue、Global Run Queue、Network Poller、Work Stealing。

由于发生系统调用时会创建/唤醒内核线程，也就是说内核线程的数量会多于 CPU 的核心数量。新的调度器为每个内核线程分配本地资源，但是实际上执行 Go 代码的内核线程的数量是固定的（由 GOMAXPROCS 指定），所以空闲线程不应该持有资源，会造成资源浪费以及降低 Work Stealing 的效率。所以，设计上引入一个新的实体，也就是处理器（Processor），从而调度模型从 GM 变为 GMP。Go runtime 不会为每个内核线程分配资源，而是为 Processor 分配资源，Processor 的数量就是 CPU 的核心数量。在新的模型中，当 Goroutine 发生系统调用时，Goroutine 会创建/唤醒新的内核线程，然后将 Processor 对象交给新的内核线程。

目前，调度器已经足够好，不过可以更好。公平性（Fairness）和性能的权衡：设计者想要以最小的性能开销获得最小的公平性。FIFO 队列可以一定程度上保证公平性，但是如果当前 Goroutine 陷入无限循环，队列中的 Goroutine 将会饥饿，所以设计者使用 10 ms 的时间片轮转调度（时分共享，抢占式）。另一方面，FIFO 队列缺少局部性（影响性能），最后进入队列的 Goroutine 会在最后运行。常见的场景，当前 Goroutine 创建另一个 Goroutine，然后自身被阻塞等待另一个 Goroutine 执行。缺少局部性的 FIFO 会产生很大延迟，所以设计者在 Local Run Queue 的尾部添加一个单元素的 LIFO 缓冲区，每次获取 Goroutine 都会首先从缓冲区中获取（Direct Switch）。

该设计引入额外两个问题，一个是其他内核线程从当前内核线程 Work Stealing 时，将 LIFO 中的 Goroutine 窃取，影响 Direct Switch 的执行。解决方案是只有 Goroutine 被放入 LIFO 超过 3 μs 才能被窃取。另一个问题是，不断创建 Goroutine 会导致 LIFO 缓冲区总是有元素，从而 FIFO 队列中的 Goroutine 会饥饿，解决方案是当前 Goroutine 和 LIFO 中的 Goroutine 共享同一个 10 ms 的时间片。

如果 Local Run Queue 一直不为空，Global Run Queue 会饥饿。所以，假设当前是第 schedTick 次获取，设计者设置当 schedTick % 61 == 0 时，优先从 Global Run Queue 获取 Goroutine。为什么使用 61，因为 61 不大不小，太大会饥饿，太小会因为 Global Run Queue 的 MUTEX 限制性能，并且参考哈希表的设计，使用质数而不是 2 的幂会更随机/公平。

最后，Network Poller 可能会饥饿，解决方案是使用后台线程从中定期获取 Goroutine。之所以不像处理 Global Run Queue 饥饿一样在当前线程中获取，是因为从 Network Poller 获取 Goroutine 涉及到 epoll_wait() 系统调用（很慢）。

---

课程网站，实验网站，实验指南。

Part A: The Controller and Static Sharding

实现

基本上就是复制 lab4 的代码，实现平衡分片到服务器的代码会花点时间，像在做算法题。

测试

使用命令 time go test -race -run 5A -count 1 -failfast -timeout 0 开始测试：

① 测试 TestMulti，报错 test_test.go:61: Shards wrong。日志显示，不同状态机的 Shards 数组包含相同的元素，但是顺序不同。可以想到，错误原因在于改变状态机的代码是非确定性的，由于提示中有说 map 遍历顺序的不确定性，所以我们可以很快定位错误。要使遍历顺序具有确定性，只好将 map 中的键放在数组中，排序之后遍历。

Part B: Shard Movement

实现

假设副本组 G1 负责的分片 S1 需要移动到副本组 G2。在 G1 发送分片之后，以及 G2 接收分片之前，都不应该处理和该分片相关的客户端请求，不论是新收到的请求还是已经在 applyCh 中的请求。G1 应该返回 ErrWrongGroup，G2 应该使用条件变量等待分片的到达。和 lab4 相同，如果服务器发现其已经不是 leader，则不应该继续等待。而且，G2 必须将接收的分片使用 Raft 应用到状态机之后，才能返回响应。为了方便的发送和删除分片，服务器应该按分片来存储数据。如果服务器需要发送多个分片，可以简单地串行发送，更好的做法是，并发地向不同副本组发送分片，在单个 RPC 中包含所有需要发向该副本组的分片。

如果在 G2 更新配置之前，G1 发送的分片到达 G2，该如何处理？在请求中应该包含配置编号，如果 G2 发现更大的配置编号，则使用条件变量等待配置更新，再处理该请求。如果 G1 发生故障，G2 可能会收到重复的分片，在将分片应用到状态机之前，应该限制该分片所属的配置编号和当前配置相同，并且使用副本组编号和配置编号的组合来去重。如果分片的配置编号小于当前配置编号，则直接响应 OK。

对于客户端请求，必须实现跨副本组的重复检测。例如，副本组 G1 已执行客户端的请求但未响应，然后 G1 向 G2 发送分片，最终客户端会向 G2 发送重复的请求。简单的解决方案是，G1 不仅发送分片，还发送用于重复检测的数据，所以重复检测的数据最好也是按照分片来存储。

服务器需要定期检查配置是否变更，在一个副本组中，只有 leader 会检查，还是所有副本都会检查？应该是只有 leader 检查配置变更，然后使用 Raft 将变更复制到其他副本中。因为不同副本检查配置变更的时机不同，服务器拒绝 applyCh 中相关请求的时机也就不同，从而状态机会不一致。在将配置变更应用到状态机之后，才开始发送分片，从而确保不同副本都会发送相同的分片。

在检查配置变更时，需要根据配置编号获取下一个配置，而不能直接获取最新配置，因为在未检查期间配置可能变更多次。如果 Raft 选举出新的 leader，它会检查下一个配置变更将其添加到日志，若此时通道中已经存在旧 leader 提交的一个/多个配置变更的日志，有可能会导致不正确的覆盖。所以，在将变更应用到状态机之前，应该总是限制配置编号是单调递增的。

配置必须线性地变更，如果配置变更多次，之后的变更必须等待之前的变更完成。可以将等待发送和接收的分片记录到状态中，然后使用条件变量检查状态来确定之前的配置是否完成。特别的，如果配置的编号为 1，则不需要记录状态。如果 leader 在变更配置的过程中崩溃，新的 leader 需要知道当前配置是否变更完成，所以上述状态应该使用 Raft 复制到副本中。同时，创建一个线程定期检查（或者使用条件变量），如果当前服务器是 leader，则发送状态中记录的待发送分片，发送完成之后删除对应分片。

测试

使用命令 time go test -race -run 5B -count 1 -failfast -timeout 0 开始测试：

① 在将配置应用到状态机之后，没有拒绝 applyCh 中的相关请求。 ② 在处理发送分片的 RPC 的响应时，忘记检查假设，需要确保当前配置编号和发送 RPC 时相同。 ③ 读取快照的语句放在初始化之前，导致错误的状态。 ④ Op 中的 map 会和 Raft 的 e.Encode(rf.log) 竞争，所以总是使用 map 的副本。 ⑤ 在修改状态时，没有唤醒条件变量。 ⑥ 有些状态只有 leader 会修改，所以 follower 需要特殊处理。

⑦ 如果 leader 接收分片，使用 Raft 复制到多数副本，在返回响应之后所有副本都崩溃。重启之后，由于 Raft 对提交之前任期的日志条目存在限制，该日志无法提交。此时，客户端请求该分片的数据将会阻塞直到日志应用，而日志无法提交除非在当前任期提交一个日志。解决方案就是，在重启之后总是添加一个空日志条目，来推进 commitIndex。之前测试有发生过低概率的报错，我当时就怀疑是 Raft 的实现有问题。

总结

Part B 有点折磨，有些很蠢的错误，花费很长时间才定位到。例如 ⑥，主要是太相信某个部分不会出错，结果就是那个地方有问题。例如 ①，以为已经实现某个功能，实际上存在遗漏，在定位错误时就不会往那个方面想。原因在于，没有在完成部分功能时做相关的测试，从而将发现错误的时间延后，此时代码已经有很多其他逻辑，定位错误会更加困难。错误 ②③④⑤ 是细节上的遗漏，因为功能实现并不是线性的过程，添加某个功能会修改已经实现的部分，逻辑交互在一起难免会有遗漏，特别是在代码组织很糟糕的情况下。整体来说，程序的并发运行会产生意想不到的交错，特别是存在网络或者机器故障的情况下，真的很难在最开始就写出正确的代码。

课程网站，实验网站，实验指南。

单个客户端只会串行发送 RPC，但服务器会收到多个客户端的 RPC。

Part A: Key/value service without snapshots

实现

实现 Clerk 的 Get 和 PutAppend 方法。如果不知道谁是 leader，则迭代地向每个服务器发送 RPC。直到某个服务器回复操作成功，此时记录该服务器为 leader，以免每次发送 RPC 都需要重新确定 leader。如果标记为 leader 的服务器回复操作失败或者超时未回复，依然需要迭代所有服务器。因为 leader 随时可能变化，甚至是在迭代的过程中，所以需要在迭代的外层添加一个无限循环。

实现 KVServer 的 Get、Put 和 Append 方法。基本的结构是，首先调用 rf.Start 方法，如果不是 leader 则响应 ErrWrongLeader。否则，在正常情况下，我们等待通道中出现对应的命令，将命令应用到状态机，然后返回响应。由于 rf.Start 方法不保证会提交指定的命令，我们需要一种能够检测当前服务器已经不是 leader 的方法，从而避免客户端阻塞在非 leader 服务器上。方式如下，可以定时调用 rf.GetState 检查当前服务器的任期是否和之前调用 Start 得到的任期不一致，或者在通道中出现和请求不匹配的消息。

对于每个服务器，我们应该使用一个线程来读取 ApplyMsg，不断地将已提交的命令应用到状态机。我们不能等待 RPC 去读取对应的 ApplyMsg，因为只有 leader 会收到 Clerk 的 RPC，此时其他服务器需要自动同步。需要注意，不是所有提交的命令都会应用到状态机，因为会存在重复的请求。例如，当前 leader 在提交日志之后崩溃，客户端没有收到响应，然后向新的 leader 发送重复的请求，如果此时命令没有被应用到状态机，依然会调用 rf.Start 方法，重复的请求会出现在日志中。

我们需要为每个客户端记录其最后应用到状态机的命令对应请求的标识，来过滤重复的请求。特别的，Get 请求不会对状态机产生影响，并且将 Get 请求放入日志只是为保证单个客户端视图的单调性，所以我们不需要过滤重复的 Get 请求，也就不需要保存上次 Get 请求的结果，而总是应该返回最新的结果。对于每个 Clerk，只缓存上次请求的 RequestId 是否有可能产生错误？例如，某个很早之前发送的 RPC 到达 KVServer，而对应的 RequestId 已经被覆盖。不会发生该情况，TCP 会保证发送顺序和到达顺序一致。

测试

使用命令 time go test -race -run 4A -count 1 -failfast -timeout 0 开始测试：

① 测试无法停止，查看日志发现，客户端请求阻塞在非 leader 服务器上。通过定时检查服务器的任期，可以解决该问题。

Part B: Key/value service with snapshots

实现

什么时候检查大小？可以定时检查。如果超过大小，该执行什么操作？调用 rf.Snapshot。什么时候读取快照？在服务器启动时，以及从通道中。特别的，如果 maxraftstate = -1，则不需要快照。通道中的快照是否有可能比服务器的当前状态更小？

测试

使用命令 time go test -race -run 4B -count 1 -failfast -timeout 0 开始测试：

① 报错 panic: runtime error: slice bounds out of range [-190:]。Raft 发送快照给服务器，而服务器也发送快照给 Raft，状态交叠从而产生错误。要解决该问题，第一个想法是在 Raft 向服务器发送快照时不释放锁，但是有可能产生死锁。第二个想法是，在服务器从通道接收快照消息之后，再更新 Raft 的状态。但是还是不行，如果服务器读取快照消息却没有应该到状态机，然后服务器在 Raft 更新状态之前，调用 persister.RaftStateSize 检查大小，此时 Raft 更新状态，之后服务器调用 rf.Snapshot 方法传递一个更小的快照，必然会产生索引越界。或者，服务器调用 rf.Snapshot 方法传递一个更大的快照，然后 Raft 更新状态，也会索引越界。而且，在之后更新状态必须重新检查假设，很麻烦。简单起见，依然在解锁之前更新状态，同时在 rf.Snapshot 中过滤更小的快照。

② 测试 TestSnapshotRecover4B，报错 test_test.go:148: duplicate element x 0 333 y in Append result。定位错误很慢，日志太长不好看，看半天看不出问题。原因是服务器从通道读取快照之后，通道中有快照已经包含的命令消息，所以会重复应用命令。在应用消息到状态机之前，需要限制消息的日志索引必须大于最后应用到状态机的日志索引。其实只要查看修改状态机的关键代码，应该是可以很快找到错误的。

③ 测试 TestSnapshotRecoverManyClients4B，报错 test_test.go:293: get wrong value, key 19。错误的信息表明状态缺失，定位错误很慢，主要日志太多，打印的信息也不全，经常需要添加打印信息然后重新测试，果然应该在最开始就打印所有信息。错误的原因在 Raft 代码，没有限制快照消息在日志消息之前发送，服务器会提前收到快照之后的命令，使得服务器在收到快照时会丢弃快照，因为最后应用的命令索引大于快照的最后索引。解决方案很简单，只需要做一下限制就行。

总结

每次做实验都会遇到两个难点，一个是功能实现，一个是定位错误。

关于功能实现：例如，如何实现将 ApplyMsg 应用到状态机？最开始，我是想让每个 RPC 去读取消息，然后将其应用到状态机。但是，思考之后，会发现不可行，然后又去想其他方案。实现方式的设计依赖于对整个交互逻辑的正确理解，难点在于处理异常情况，像是 leader 变更、服务器崩溃。

关于定位错误：总是应该在日志中包含所有信息，避免需要添加信息然后重新测试的情况，会非常痛苦。定位错误不要只看日志，一定要先思考可能是哪个部分有问题，比如说状态机的状态有问题，那么在什么情况下会修改状态？找到修改状态的代码，然后思考这段代码在什么情况下会有问题。如果代码没有问题，那么想一想是不是外界的输入有问题，什么样的输入会产生该错误？然后，我们就可以找到外部依赖的代码，确定是否有可能产生该输入序列。