完成情况
我是在大三的暑假实习项目，实际投入天数2个月，能通过基本测试，但是整体不太稳定，尤其是Project3B最后一个测试函数错误概率大概是10%，且每次错误的原因都不尽相同，实在没办法保证其正确性。
思路分享
以下是对项目任务的概述，以及我实现项目的一些阅读资料，如有错漏望请指正：
Project 1
目标：实现一个单节点键值存储（非分布式系统），使用column family。
这个存储系统支持四个基本的操作：Put/Delete/Get/Scan
需要完成两个部分：
- 实现单节点的引擎（需要实现
kv/storage/standalone_storage/standalone_storage.go）
- 实现键值存储的处理函数（需要实现
kv/Server/Server.go的四个基本的函数）
查阅查阅badger相关的API，如果不理解可以参考kv/storage/raft_storage/raft_server.go中的写法。将结点之间进行同步的部分剔除，即可得到单一结点的函数，对于本节的编程具有一定帮助。
阅读kv/util/engine_util，里面有很多工具函数。
为了方便理解整体框架，需要至少了解列族（Column Family）的意义。
如果不清楚应该调用那些接口，也可以参考往年的代码（慎重，很容易被带歪）。
该项目有 3 个需要做的部分包括，本次项目本人写的文档链接: https://github.com/LX-676655103/Tinykv-2021/blob/course/doc/project2.md
- Implement the basic Raft algorithm（实现基本的 Raft 算法，Project 2a）
- Build a fault-tolerant KV server on top of Raft（在 Raft 基础上搭建可容错 KV 服务器，Project 2b）
- Add the support of raftlog GC and snapshot（增加raftlog 垃圾回收机制以及快照机制，Project 2c）
Project 2a
Raft 是一个一致性协议，本部分实现了 Raft 算法中的领导人选举、日志复制以及Raft对外的Rawnode接口等内容。Raft 将一致性问题分解成了三个相对独立的子问题：
- 领导选举：当现存的领导人宕机的时候, 一个新的领导人需要被选举出来
- 日志复制：领导人必须从客户端接收日志条目(log entries)然后复制到集群中的其他节点，并且强制要求其他节点的日志保持和自己相同。
- 安全性：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令
阅读清单：
注意事项：
- 本部分是本项目的重要核心部分，需要小心实现。很多地方需要对照论文以及演示网站的操作进行实现，不能仅仅面对测试编程，否则可能造成后续项目出现问题（尤其是2B以及3B的测试是模拟真实环境测试，问题发生的场景与实际bug位置存在较大的偏移，会使得调试极其困难）
- 在进行调试时，对于有些测试可以使用debugger，但是对于比较复杂的测试还要学会使用日志调试。记得使用
log/log.go给工具来打日志，比方说结点新建或者重新恢复之后的内部变量的值、选举的消息、节点状态变更情况等等，反正哪里有bug打哪里。
- 请求安装快照，如果当前结点为领导人，则其在发送日志时获取日志或任期失败（出现异常），则需要使用快照同步。
Project 2b
用 A 部分中实现的 Raft 模块构建容错键值存储服务器，该服务器是一个多副本键值(key/value)存储服务器。所构建的服务器集群应该能在大多数服务器存活（处于活动状态且可通讯）的情况下持续工作，处理客户端的请求。
本次需要编写的代码量不大，主要需要编写4个方法，包括kv/raftstore/peer_msg_handler.go中的方法HandleRaftReady以及proposeRaftCommand；以及kv/raftstore/peer_storage.go中的方法Append以及SaveReadyState。但是由于整体体系的复杂性，需要阅读以及理解的代码量非常大。
PS. BargerDB 中应该存在比较严重的内存泄漏或者内存占用问题（可能是异步关闭导致的占用），导致每次进行2-3个测试后就会内存溢出，这个bug是项目自带的，我也很懵逼，可以使用脚本进行单个的测试，或者使用goland的测试功能进行单独测试（推荐使用脚本）。
基本格式就是进入对应的包，使用测试命令测试单个函数，不能测试整个文件，同样会造成内存溢出的问题。
cd ./kv/test_raftstore/
go test -test.v -test.run="TestOnePartition2B"
阅读清单：
服务器的基本工作流程如下：
for {
select {
case <-s.Ticker:
Node.Tick()
default:
if Node.HasReady() {
rd := Node.Ready()
saveToStorage(rd.State, rd.Entries, rd.Snapshot)
send(rd.Messages)
for _, entry := range rd.CommittedEntries {
process(entry)
}
s.Node.Advance(rd)
}
}
Project 2c
服务器将定期检查日志的数量，当日志的数量超过阈值，就会将部分日志丢弃（discard log entries exceeding the threshold from time to time）检查日志的数量并丢弃超过阈值的日志。
func (d *peerMsgHandler) onRaftGCLogTick() {
......
if appliedIdx > firstIdx && appliedIdx-firstIdx >= d.ctx.cfg.RaftLogGcCountLimit {
compactIdx = appliedIdx
}
......
request := newCompactLogRequest(regionID, d.Meta, compactIdx, term)
d.proposeRaftCommand(request, nil)
}
代码主要分为两部分，Raft 模块以及 raftstore 模块的修改，Raft 模块需要对 raft.go、log.go 以及 rawnode.go 共三个文件进行修改； raftstore 模块就是对上述2B中的四个方法进行扩展即可，具体参见文档。
Project 3
在这个项目中，将实现带有平衡调度器 (balance scheduler) 的 multi raft-based 的 kv 服务器。该服务器就集群由多个 raft groups 组成，每个 raft group 负责一个单独的键范围，该项目有3个部分，包括：
- 实现成员变更（membership change）和领导变更（leadership change）
- 在 raftstore 上实现 conf 更改 和 区域拆分（region split）
- 引入调度器
Project 3a
实现成员变更（membership change）和领导变更（leadership change），Membership change 也即是 conf change，用于在raft group中添加或移除 peer，可以改变 raft group 的 quorum。Leadership change 也即是 leader transfer，用于将领导权转移给另一个peer，这对于平衡非常有用。
需要修改的代码位于 raft/raft.go and raft/rawnode.go，另请参阅proto/proto/eraft.proto查看需要处理的新消息，详细参考文档。
Project 3b
在完成 Part A 后，Raft module 支持成员的增加与移除以及 leadership 转移，这部分需要在A部分的基础上让 TinyKV 支持定义在 proto/proto/raft_cmdpb.proto 中的 admin command，命令分为四类：
- CompactLog
- TransferLeader
- ChangePeer
- Split
TransferLeader 以及 ChangePeer 是基于 Raft 的与领导变更和成员变更相关的命令。这些命令将作为基本的操作步骤，用于后续进行平衡调度过程中。 Split 将一个 Region 分裂为两个 Region，这是 multi raft 的基础。
需要修改的代码位于 kv/raftstore/peer_msg_handler.go 以及 kv/raftstore/peer.go 中。
阅读清单：
Project 3c
调度器 Scheduler 拥有关于整个集群 cluster 的一些信息，如每一个 region 所在的位置，每个 region 的 startkey 以及 endkey 等等。
为了获取这些信息，Scheduler 要求每个 Region 定期向 Scheduler 发送心跳请求 RegionHeartbeatRequest ；当调度器 Scheduler 接收到这些信息后，会使用搜集到的区域信息， 检查 TinyKV 集群中是否存在不平衡问题，如存在 store 包含太多 region 等情况，如果需要进行 ChangePeer 或 TransferLeader Scheduler 会返回对应的响应 RegionHeartbeatResponse ，该响应会作为 SchedulerTask 进行处理，这些请求定义 proto/pkg/schedulerpb/schedulerpb.pb.go 中。
本部分实现了Region的均衡调度，主要是为了更加合理地调用3B中实现的功能。
Project4
本部分代码实现了面向Clients的Server层，主要是实现服务器的事务系统API以及保证SI特性的MVCC。任务书写的很泛，主要看kvrpcpb.proto文件的注释，对照数据结构进行编写，这部分对写过类似事务处理的人可能难度不大，但是对于初学者不太友好，建议参考基本的代码框架进行修改，不要从头开始。
该部分的处理逻辑不太复杂，但是由于接口介绍比较模糊，可能不知道应该使用哪些方法进行处理，建议可以参考别人的代码，该部分会者不难，难者不会。
阅读清单：
