Bugtrap

前面一小节我们主要学习了基于 multi raft 的 shardkv 的大致架构和代码框架，从这一节开始就开始具体的实现编码了。 我们首先来处理一下 shard controller，shardctrler 也是一个分布式 KV 服务，这和我们前一个部分实现的分布式 KV 类似，只是其存储的是 shardkv 的一些配置信息。 Shardctrler 存储的配置信息，实际上是多个带编号的配置组合而成的数组，每个配置都有一个唯一的编号（数组下标），配置中存储的是 shard id 到 Group id 的映射关系，以及 Group id 对应的 KVServer。 每次只要有了新的配置产生，就会向数组中新增一个元素。KV 客户端或者服务端可以向 shardctrler 获取最新的或者旧的配置信息。 123456789101112131415161718type ShardCtrler struct { mu sync.Mutex me int rf *raft.Raft applyCh chan raft.ApplyMsg / ...

上一节我们主要处理了 shardkv 中的 shardctrler 的客户端逻辑，这一节我们处理一下 shardctrler 的服务端的逻辑。 其实 Server 这边的处理和前一个部分我们实现的分布式 KV 的 Server 非常类似，逻辑基本上是差不多的。 我们依然需要维护状态机、通知 channel、去重的哈希表，在前面的概述中提到了，由于 shardctrler 是存储的一些配置信息，并不会存储用户数据，所以数据相对来说是比较少的，因此我们可以不用去实现分布式 KV 中的 snapshot 机制。 这里我们接收客户端的四种请求 Query、Join、Leave、Move，然后将其通过 raft 模块进行各个节点之间的状态同步。 然后我们在后台的 apply 线程中处理 raft 已经 commit 的数据，主要是将操作应用到状态机中。 123456789101112131415func (sc *ShardCtrler) applyLogToStateMachine(op Op) *OpRelpy { var err Err var config Config ...

前面一节我们主要对 shardctrler 的服务端进行了处理，主要沿用了之前分布式 KV 的一部分代码，并且由于 shard ctrler 数据量较少，我们也不需要 snapshot 的逻辑。 当 raft 模块状态同步完成之后，节点会发送已经 commit 的日志，我们就会在后台常驻的 apply 线程中进行处理，主要是将用户的操作持久化到状态机中，这一节就来看看状态机中具体的操作逻辑是什么样的。 前面其实提到了我们有四个客户端的方法，分别是 Query、Join、Leave、Move，实际上状态机的处理，就是对这几种方法进行处理，将处理完成之后的配置存储起来，供外部调用，接下来就依次看看这几个方法的大致处理逻辑。 Query Query 的逻辑比较简单，是通过配置编号 num 进行查询，我们会在状态机中维护一个配置数组，num 其实就是数组的下标，所以能够直接获取到下标对应的配置。 123type CtrlerStateMachine struct { Configs []Config} Join Join 主要是添加一个 Group 到集群中，我们需要处 ...

前面一节我们处理了配置变更的需求，主要是定时从 shardctrler 中拉取配置，我们对传入 raft 模块的结构体进行了一些改造，使其能够兼容两种不同类型的请求，分别是用户操作和配置变更。 用户操作和之前的一样，并没有任何的变化，只是反解析结构体的时候需要注意。 配置变更的操作，上一节主要是简单处理了一下，主要的 shard 迁移流程需要我们继续完善。 在商讨 shard 迁移的具体流程之前，我们可以来简单看一下官方 lab4 给出的一些提示： 在 KVServer 中添加定期从 shardctrler 拉取配置的代码，并且如果客户端请求的 shard 不属于当前 Group，那么应该返回 ErrWrongGroup 错误。这个加上之后，应该仍然能通过第一个测试。 确保 KVServer 中的 Get、Put、Append 方法和配置变更同时发生时，需要有一致的行为。 一次处理一个配置变更的请求，并且按照顺序。 需要在 shard 迁移期间，确保对重复请求的过滤，保证线性一致性。 在一个 shard 迁移到新的 Group 之后，原来的 Group 可以继续持有并不属于它的旧的 ...

前面一节我们处理了单个 Group 的逻辑，其实比较简单，和我们前面在 Lab3 实现的分布式 KV 是基本类似的。 今天这一节来处理下配置变更的问题。 shardkv 需要定时从 shardctrler 这边拉取最新的配置，然后根据配置来确定哪些 shard 应该是需要进行迁移的。 上一节我们已经写了一个简单的拉取配置的后台任务，但是按照 lab 的提示，我们每次只能够拉取一个配置，并且按照顺序处理，这样做的目的主要是为了避免覆盖还未完成的配置变更任务。 123456789101112// 获取当前配置func (kv *ShardKV) fetchConfigTask() { for !kv.killed() { kv.mu.Lock() newConfig := kv.mck.Query(kv.currentConfig.Num + 1) kv.mu.Unlock() // 传入 raft 模块进行同步 kv.ConfigCommand(RaftCommand{ConfigChange, newC ...

前面几节我们主要实现了分片分布式 KV 中的第一个重要的组成部分，那就是 shard controller，并且实现了获取和更改配置的接口。 接下来我们就需要回归到 shardkv 的具体逻辑了，这里贴一下我们的整体架构图，简单回顾一下： 我们的 shardkv 是由多个 Replica Group 组成的，每个 Replica Group 又是由一个 raft 集群组成，使用 raft 共识算法保证数据的一致性。每个 Group 都负责了一部分 shard 的读写请求，全部的 Group 组合到一起，就是一个完整的 shardkv 服务。 Shardctrler 负责存储配置信息，主要是 shard 到 Group 的分配关系，当配置发生变化的时候，Group 应该根据配置处理 shard，并且这里需要保证在处理配置变更时，客户端不能看到不一致的结果。 客户端会通过 Get、Put、Append 这三个方法来访问 shardkv，需要保证 Put 成功之后的结果对于后续的请求是可见的，即使 Put 请求和配置变更同时发生。 首先我们可以处理一种最简单的情况，即集群中只有一个 Gro ...

在 shardkv 的分片迁移和清理大致完成之后，我们还需要修改几个地方，才能够将测试 run 起来。 主要有以下改动： matchGroup 方法，需要判断 shard 的状态，如果是 GC 或者 Normal 状态，均可以继续提供服务 StartServer 方法中，需要注册 labgob 相关的结构体。 makeSnapshot 和 restoreFromSnapshot 中， config 信息也需要进行持久化，并且需要初始化 shard 的状态 fetchConfigTask 中，需要加上一个判断，如果任何一个 shard 的状态是非 Normal 的，则说明前一个 shard 迁移的流程还在进行中，我们就跳过拉取新的配置，避免覆盖之前的任务 Apply 的时候，客户端操作也需要判断 Group 是否匹配

前面一节我们主要处理了 shardkv 分片迁移的主要流程，配置变更时更改 shard 的状态，并且启动一个后台线程，定期获取 shard 的状态，执行实际的 shard 迁移。 Shard 有四种状态： Normal MoveIn MoveOut GC 在前面的实现中，如果一个 shard 已经从 Group 迁移出去了，这个 shard 还会在这个 Group 中存在，并且数据也会继续保留。 但实际上，因为 shard 已经完全迁移到了另一个 Group 中，所以这个 shard 在原 Group 中已经可以不用继续保留了，我们可以将其删除掉。 在 lab4 的 challenge 1 中，要求我们及时清理 Group 中已经无效的 shard，这样能够及时释放空间。 在上一节 shard 迁移的流程中，如果一个 shard 已经完成了迁移，我们会将其置为 GC 状态，所以我们可以启动一个后台线程，定时获取需要执行 GC 的 shard。 拿到这些 shard 之后，我们需要做两件事情，一是给旧的 Group 发送消息，删除对应的 shard；二是给当前 Group 的 sha ...

在分布式系统中进行调试本就是一个难点，而本实验无疑让这一点更加困难： 多机日志混杂。用单机模拟的分布式系统，将所有节点的日志汇聚到了一块，无疑加大了根据日志进行问题定位的难度。 网络环境复杂。为了在较短时间测出各种边角情况，本实验的测试通过（使用 labrpc 进行 mock）接管 RPC 层，将真实环境中频次很低的网络故障（RPC 消息乱序到达或者干脆丢失）大大提高。这让日志中的时间线非常难以追踪，进而定位各种事情发生的因果关系。 实验所需的 Raft 的代码并不算太多，最终大家花在调试（Debug）的时间要远比编码的时间要多，当然在真实工作中也是如此。因此，一个科学的调试方法就显的非常重要，他能大大加快你定位问题的速度。甚而，一个好的调试方法能让枯燥的调试过程变成充满趣味性的通关过程。 下面主要参考 Debugging by Pretty Printing 一文和我的一些经验，来介绍一种针对本实验多节点日志混杂、RPC 通信多变的情况的调试技术。 基本原理 对于编程调试，我们最常用的方法有两种：借助工具单步执行和手动埋点分析。但无论是多线程还是分布式编程，使用（类似的 gdb） ...

Raft 通常是是一个多机、多线程的库（lib），因此会涉及大量并发编程知识。 由于在语言层面内置 goroutine 和 channel，Golang 大大简化了并发编程复杂度，这也是课程选择 golang 为编程语言的主要原因。 Goroutine goroutine 是一种轻量级线程，是 go runtime 提供的一种用户态线程，因此也被称为协程。所谓轻量，就是相比操作系统线程，每个 goroutine 耗费的资源更少、goroutine 间切换耗费也更低（不会陷入内核态），因此可以有更高的并发度。因此，我们在 golang 中，可以相对随意的创建新的 goroutine。 但我们在决定是否使用 goroutine 时，仍然有一些原则和技巧可以遵循。原则上来说，使用 goroutine 的目的主要有两种： 提升计算性能：主要针对计算密集型任务，多开 goroutine，充分利用现代计算机多核性能。 旁路 IO 负载：主要针对有 IO 型任务的负载，比如 RPC 和文件 IO，将其放到单独 goroutine 中，避免影响主干工作流性能。 对于 raft 来说，主要后面一种情 ...