使用 Go 实现的一个基于 Raft 的分布式 KV 数据库。
- 实现 Raft 一致性协议，支持快照压缩
- 实现集群、主备的分布式 KV 服务器
- 扩展实现了 2PC, 2PL 的分布式事务
- 实现 MapReduce 框架
详见 实现笔记.md。
-
Lab1
- 实现 MapReduce 框架
-
Lab2
- 实现可靠网络下单机 KV 服务器 (带 version)
- 基于 KV 服务器实现分布式锁服务
- 在不可靠网络实现 at-most-once 语义
- 在不可靠网络实现锁
-
Lab3
- 实现 Raft 协议领导选举
- 实现日志记录和扩散
- 实现持久化恢复
- 实现快照压缩
-
Lab4
- 基于 Raft 实现复制状态机 RSM
- 在不可靠网络实现主备 KV 服务器
- 实现 KV 服务器的持久化快照
-
Lab5
-
实现集群 KV 服务器的分片移动
-
实现不可靠控制器的重做
-
实现并发的控制器
-
扩展
实现主备 KV 服务器存储配置
实现 exactly-once 语义
实现范围 key 查询 B 树
实现 Raft 协议的租期读
实现主备下的单机事务
实现集群下的分布式事务
-
具体细节看代码和实现笔记。
MapReduce 任务按需要处理的文件数量=map任务数，每个map处理一个文件，将其处理为中间过程 KV 列表。指定reduce任务数，把 KV 列表按 key 哈希+取模分桶到 reduce 个桶里，形成中间文件 mr-mapId-reduceId。所有 map 任务完成，则 reduce 任务把当前所有 mr-*-该id 处理，对每个 key 的全部 value 归纳为这个 key 的答案。最后所有key的答案就是 MapReduce 结果。
空闲的 worker 进程(可go手动启动)初始化时接受 map/reduce 函数，不断通过RPC联系协调者，协调者根据阶段分配 map/reduce 任务；拿不到任务时随机等待退避。协调者每1s看一次是否超时，若超时(如10s)，协调者重新把这个任务标记空闲，回收。因为幂等，重做无所谓，即使超时做好了多次也没关系。所有reduce都完成就标记结束。
写文件的原子性：先写临时文件，写完再 rename，重复执行不会产生半写文件，容错增强。
KV 服务器支持 get, put 操作。加版本号，一开始为 0 表示不存在。所有 put 导致版本号+1，get 不变。put 必须传入当前版本号。除了正常结果和报错外，put 失败后返回版本不对的话有两种可能：①真的不对；②第一次put成功，但网络不可靠，第二轮再put版本不对。所以这种情况返回 ErrMaybe 让业务自己处理。
实现 at-most-once 语义，即：不可靠执行 0 次，可靠执行最多 1 次，不会重复执行 put。可以存储最后一次结果，保证严格最多执行一次，需要客户端传 id 和自增请求id(那么客户端单线程，一定只有最后一次询问不可靠重做，那么服务端存储每个客户端最后一次结果和请求id即可)。
KV 的存储直接用 map 即可。get和put都是一直调用，直到RPC返回成功，失败就100ms睡眠重试。
基于 KV 服务器实现分布式锁，key 是锁名(业务规定)，value 是持有锁的客户端id(随机初始化)，如果无锁设置 0 字符串。获取锁：如果 value 不是自己就睡眠 100ms 等，否则设置 value 为自己。释放锁同理，设置 value 为空锁。
Raft一致性协议。每个节点有三个状态，基本行为如下：
- leader。
- 主节点，提供写服务(写命令日志)，即主备结构，仅leader对外提供服务。
- 周期性对follower发送心跳，与此同时同步自己的日志给follower。得到大等于半数反馈后，确认命令日志生效，对外通道发送应用命令通知。
- follower。
- 接收leader的心跳，同步日志，同步后反馈结果给leader。
- 如果长时间没收到心跳，竞选candidate。
- candidate。
- 给每个发竞选，收到半数同意(任期和日志最新会同意)后成为新的leader，任期+1。看到更新的任期认其为leader。
- 刚成为leader的话，马上发心跳同步日志。
日志复制的匹配问题：如果follower日志不匹配，计算回退到指定下标(或不优化，一条条回退直到匹配)。
压缩：如果(上层，如KV服务器)确认持久了，那么raft层可以丢弃一部分不再需要使用的日志。只需要持久快照之后的新日志。对应做偏移删除。
使用中间抽象工具RSM(复制状态机)打通Raft和上层的逻辑。服务器给RSM命令。RSM收到命令时，把抽象命令传给Raft，Raft经过多数同意后，用通道把应用命令信息传给RSM，RSM通知服务器执行具体命令。如果Raft不同意(不是leader)，直接给服务器上报。
一个具体KV服务器收到一个客户端命令后，等待RSM通知所有KV服务器执行，该服务器并返回给该客户端。在分布式环境下，两个客户端A,B分别发送命令执行同key的put，如果A网络不可靠，B成功执行后，A重发再执行，就会导致结果是A覆盖而不是B覆盖A。所以，必须按客户端ID和请求ID做去重，记录最后请求返回而不是重新发送命令。从而客户端幂等。
客户端从认为的leader开始轮询所有已知服务器，如果它不是leader就顺位请求下一个并记录leader。如果是就正常执行返回。
KV服务器做序列化持久化，可调用快照，同时往下通知Raft，Raft裁剪日志，认为通知时往前的都持久化了可以丢了，并保留快照，如果follower落后到日志被截断，leader就主动把快照发给follower让他计算出这个内容。
key分给不同的分片(shard)处理，key哈希取模得到它所属分片，一个组负责若干个分片。一个组是lab4的一个主备KV集群。多个分片组成整个分布式KV集群。配置信息(组负责的分片，它有的服务器)信息存在一个单机KV服务器(或可扩展为主备)，由配置控制器负责存取，客户端(client)从控制器取当前组的KV集群，构造当前集群的连接客户端(clerk)，对这组做lab4的操作get/put。服务端按分片做多个map+last result。
默认第1组负责全部分片。配置更改时，按分片的粒度：给旧组冻结(不允许服务)并取该分片KV，然后取出给新的分组安装，然后删除旧组对应数据。这几个操作的执行步骤与get/put一样，是raft日志命令。过程中注意容错，如安装失败需要重试直到成功。会走raft，所以对集群是多数一致通过操作的。
冻结时或分片无数据，服务端对请求返回 ErrWrongGroup，Clerk 太久没重试成功也会返回该错误。Client 对该错误进行睡眠+重试，下一次重试会重新查询配置。
控制器本身可能失效/网络不可靠，此时会并发另起控制器。在要修改配置前，先put预写一个挂起配置，表示正在变更的下一个配置，落后就覆盖，恰好相同且内容一致则直接继续。完成全部分片迁移后，更新当前配置，这样即使多个控制器并行尝试，最终也只能有一个成功更新，其他看到新配置变化已变化的会休眠重判。
通过全局bool featureflag/ 控制这些扩展是否分别生效。
单机KV存储配置可以直接更改为主备KV存储，逻辑不变。
网络不可靠的话，无法做到严格传输层exactly-once。业务层只需要last result即可保证。
要实现范围查询，把map改为B树，手写或调库，其他不变。
要实现Raft租期读：
- leader做一个小于心跳超时时间的租期长度。新leader等待一个长度(让旧的过期)后，收集所有follower的最后应答日志同步的时间，如果过半数还在租期长度，刷新自己的租期。
- raft暴露当前是否是租期的接口。服务端查询是租期的话，get操作不走lab4流程(写日志->一致性->执行读)，而是直接执行读。其他逻辑不变。
- 因为服务端直接读绕过了串行的应用日志通知，所以必须对服务端加锁。
要实现事务：
- 做一个 etcd 事务接口，事务定义为：判断一系列 get 是否全成立 compare，是执行 success 序列全部 get/put；否执行 fail 序列的。
- 对客户端增加接口。对服务端，整个事务就是一个raft命令日志，按lab4流程走，等价于新增一个操作。可以不必事务ID，幂等可以让request id做。
- ACID满足：快照恢复保证原子、可串行化隔离级别(若同时租期读，是读已提交，除非补做MVCC)、raft日志持久化，业务自己保证一致性。
要实现分布式事务：
-
客户端把要执行的 compare/success/fail 按分片分组，搞出每个 shard 要做的子事务 compare/success/fail，然后按 shard 顺序排好。因为get/put不会影响其他key(不依赖，相互独立)，故同key顺序一致即可，不同key顺序不一样是可以的。
-
服务端做两阶段锁2PL：检查要做的全部 key 是否有其他事务 id 加锁，有就事务冲突，重试(破坏死锁请求保持条件)。如果没，就原子加锁(或失败回滚放锁)；执行完 success/fail 或回滚时，放锁。注意遍历锁按字典序，锁资源按顺序获取，破坏死锁循环等待条件。
-
严格两阶段提交S2PC：①准备阶段：对各种异常(事务冲突等)重试，成功记录compare的各组结果的与，决定后面对各组子事务走什么。如果重试，把不用重试的 prepared 组遍历发送事务中断，然后sleep100ms重试。
②提交阶段：有错误返回各种错误，否则收集各组事务执行结果。
-
客户端自增事务id，服务端对同id重放直接返回缓存而不是重做。