写了一个 C++ 实现的 raft，这里就简单做些记录
repo
实现 raft 要用到一些基础库，当然也要自己写了：
参考
参考资料主要看 raft paper，前人踩过的坑我没有意识到，但其实 paper 里面都有提
raft paper 不只是 paper，还是非常好的实现参考手册。细节上的推敲比前司的代码注释还要靠谱多几倍，我以后写文档能有这水平该多好
测试是通过适配 MIT-6.824 的 test_test.go 文件来完成。但是由于它们是 lab 形式，改造成本那是相当大（后面实现细节再提）
实现上的细节
这里会提一些 paper 上不怎么强调（我觉得）的实现细节
协程模型
paper 只是说要怎么跑，没说要如何设计哪个模块在哪个线程/协程上
方法很多，我这里是基于协程实现
每个 raft 服务都至少开启 2 个协程：
- 一个是 RPC 监听协程 co0
- 另一个是 FSM（状态机）协程 co1
依据 FSM 不同的状态（leader / follower / candidate）会产生更多的协程
比如 RPC 每次处理是固定拉出一个协程，像 appendEntries 这种需要发出给不同 peer 的也会生成 peer 个协程进行 RPC call
一旦发生状态上的转换（比如接收 RPC 时，发现自己的 currentTerm 已经落后于收到的 term，要求转为 follower），这些拉出去的协程就需要进行取消操作
一个简单的做法是协程带上事务标记 transaction，转换时对标记递增即可，只要协程在对应的取消点检查标记无法对应，则立刻退出
状态间的转换
对照 raft paper 中的状态转换图可以知道
FSM 中的每一种状态（leader / follower / candidate）都会处于一个大循环内
并且通过逻辑时钟 term、选举投票 voteFor 或者本地 RPC 超时等行为进行任意状态间的转换
这里会有一些坑
follower 维持
比如，paper 中提到 follower 没有收到 RPC 时会转换为 candidate 参与选举，反之收到 RPC 则保持 follower。
这里需要注意，如果收到 requestVoteRPC，那是不计入保持 follower 状态的，该超时还是会超时
心跳处理
还有 leader 心跳收到的回复，如果实现了日志副本，那就不应该区分空包心跳和 appendEntriesRPC，收到 peer 回复就要处理返回值，而不是一直心跳就不管了
转换的处理
一个略显隐蔽的地方是，不建议直接通过调用函数去转换状态
比如从 leader 到 follower，就不要在 becomeLeader() 跑一堆循环满足条件后再调用 becomeFollower()
因为状态机是一个环，你这样写其实是是一个调用链很深的递归，如果实现方式不对，那是会爆栈的（编译器不会聪明到所有尾递归都能转换）
可以写成事件循环的形式，投递一个事件，消费一个事件，固定在某个协程中执行，这样就避免了递归问题
过期的回复
收到 RPC 时如何处理 stale term，paper 没有细说
一个简单的策略就是回复一个 term 为负数的 RPC response
原发送方收到后优先处理 term（得知比自己落后，表明接收方没有 followUp() 到最新的 term 而是选择了忽略），再看其它字段，因为过期就应该忽略而不是处理
RPC 上的实现
连接管理
RPC 在初期实现时 client 端建议用短连接，否则容易在不可靠网络上 hang 住无法实现下一次对应 peer 的心跳或者投票，换句话说就是不要在原来拉出的协程继续执行，这样就陷入和同步写法相同的 blocking 状态
另外这里用长连接感觉收益并不大，因为下一次需要用到 client 时都是需要一定的定时时间的，本身就需要花费数百毫秒
但是后面使用到一定优化技巧时可以考虑每次定时周期对每个 peer 维护单个长连接 RPC client
不可靠网络
由于 test_test.go 用到的是一个假的网络，而我的实现就是走 TCP 协议栈的，因此后面要做一个不可靠网络模拟就非常纠结了
一个简单的做法是实现一个代理层，比如收到未处理的 request 或者要发出前的 response 都走到某一个（或多个）proxy 上，那就方便操作了，
协程上 usleep（注意不是系统调用）一定的时间就可以模拟 RTT 延迟
靠一定概率把 response 丢弃也可以模拟丢包
包乱序就不需要实现了，只要你保证每一个 session 都用单独的 TCP 连接去处理，本身就不会有乱序问题，不然还用什么可靠传输协议
日志副本
Safety
appendEntriesRPC 用于同步日志副本
其中关键的一点是 prevLogIndex 对于前缀空的日志是默认允许的（假设为从 index=-1 的日志开始发出的 entries[]），即对端收到后要 reply true
但不能说 prevLogIndex 对应日志为空就是上面的行为，比如当前 leader crash 后又选出一个新的 leader，而此前 leader 发出的 RPC 因为日志不一致而做了强制截断（paper 中提到的 overwrite）处理，那么后来的 leader 发出的 prevLogIndex 可能过于超前，从而误判为前缀空的日志
以及前面说到的要和心跳一致处理，否则对端收到 leaderCommit 并更新自身 commitIndex 后，leader 还不知情
简单的优化
对着 paper 做实现不一定能过所有的 test，因为模拟了一些极端场合，你要在一定时限内完成，所以不仅要正确性，还要一定的性能
简单点的策略有对发出的 entries[] 进行批量发出，这里做了个倍增处理，默认 64 个，如果成功，下次再尝试 128 个，失败则退回，如此递推
还有别人提到的快速恢复，失败时考虑整个 term 都跳过，而不是 nextIndex 只减一，还没有想过是否有正确性问题，暂时没举出反例
以及快速重试，appendEntries 是定时触发的，paper 提到如果失败则进行立刻重试（而不是等到下一次定时触发），我在实现中进一步如果成功且下一次预估不会发出空包心跳时也会立刻重试（发出更多的 entries[]）
paper 还提到 conflictTerm，我没做，但也是个思路
还有
持久化
MIT lab 用到的持久化看着是全局一次性落盘的，我这里用的是 write-ahead log，每次重启时对着 redo 一遍即可（给个 SQLite 的做法以供参考）
当然并不是一定要用 write-ahead，只是提供在持久化的同时实现随机写改为顺序写的能力
字段维护
一个比较诡异的是，raft 中提到的 lastApplied 我从来都没用过
虽然 commit 和 apply 也算是两回事，但因为这里写的是纯算法层，并没有提交到上层的 apply 操作，因此没管
往知乎搜了一遍，确实不影响正确性，那算了吧
问题排查
分布式上的问题排查还是靠打日志
因为异步事件、定时超时事件太多了，运行时打断点并没有好的回报，
除非你是要排查某些地方突然 hang 住了但是又没有 crash，这个时候可以确实可以 debug 看下，但最好 debug 完立刻在对应地方打上日志，方便下次排查
END
暂时就想到这么多，先这样吧