Raft节点快速重启方案

[AlexStocks]

ref link OpenAtomFoundation/pikiwidb#247

基于 log index 与 sequence number 映射的快速重启方案（望哥提出）

使用该方案的原因

• Binlog 和 WAL 存在重复性，因此考虑关闭 WAL 以提高性能
• 快照时应当对 rocksdb 做 flush，但对性能影响较大，因此考虑快照时不做flush

pikiwidb raft 层面之下的状态机实际通过 RocksDB 做存储，RocksDB 是个基于 LSM 树的存储引擎，即便写入成功，也有可能是存在内存中而不是磁盘上，若这个时候服务器宕机，在关闭WAL的前提下，将会丢失内存中的数据。

设想这样的场景：如果我们在做快照时不进行 flush，某个 follower 节点宕机，丢失了 rocksdb 内存中的数据，一段时间后重启。

• 如果落后的日志不多，能够与 leader 现有日志匹配得上，就不需要快照；这时候该节点就会从保存的日志条目中 apply，但是如果做快照时把原本内存中对应的日志给删了，那就回放不出原本内存的数据了。
• 如果落后的日志太多，不能与 leader 现有日志匹配得上，就需要快照 + 追加日志的方式恢复数据；但这里 leader 发送的快照是在没有 flush 的情况下安装的，因此没有内存中数据，追加的日志也因为日志截断而不包含内存中数据。

如果要重启后保证 rocksdb 内存数据不丢失，就需要保证快照和快照之后的追加日志能够覆盖 rocksdb 内存中的数据。一种解决方案是快照时必须 flush，保证没有内存数据，但是对性能影响较大；另一种是保证追加日志能覆盖内存数据，也是本方案的核心思想。

为避免频繁 flush，提出了新的快照方案：在快照时不 flush，只对已经持久化的数据做快照，但是在截断日志时，保证不会截掉内存中数据对应的日志。后续服务器宕机后重启时，通过 braft 日志恢复 rocksdb 内存中丢失的数据和 raft 落后的日志，与原本 raft 协议有所不同的是，raft 从落后的日志开始回放，本项目应该从 rocksdb 丢失内存数据中对应的最早的日志处重放。

方案概述

一个宕机的节点重新启动时，丢失的数据分为两部分：

1. raft 层面落后的操作日志（已commit未apply）
2. rocksdb 内存中没来得及 flush 的数据（已apply）

对于第一种，raft 协议本身就可以保证同步；对于第二种，想要通过 braft 的日志找到rocksdb内存中的数据（rocksdb的WAL被关闭），需要本地做一些支持：在重新启动后通过日志恢复数据时，保证回放的日志点在原本内存数据对应的日志点之前，最理想的情况是刚好找到原本内存数据对应的最小日志索引。本方案的设计是，在持久化时写入已持久化的最大日志索引，重启时读取磁盘上这个最大持久化日志索引，在它的基础上 + 1 就得到最理想的日志回放点。

具体来说，Pikiwidb 中的每个 rocksdb 实例都有9个列族存储数据，不同列族 flush 的进度也不同，因此需要找到最落后的列族中原内存中最旧的操作（最小 sequence number）对应的 log index。内存的数据重启后不能直接找回了，但可从落盘后的最新数据入手，即 flush 进度最慢的列族的已持久化数据中最后的写操作（最大 seqno）对应的 log index，从这个日志的后一个日志开始回放。

需要做的具体工作：

1. 在运行时维护 applied log index 与 sequence number 的关系：
   每个 Redis 实例维护一个存放所有列族 logidx 与 seqno 映射的链表，在每次异步写成功后，在该链表后添加最新的映射—— applied log index（刚刚解析的 binlog 在 braft 中的 idx）和 本次 WriteBatch 之前的 latest seqno + 1。这样就可以在 flush 时通过本次 flush 最大的 seqno 找到不超过该 seqno 的最新日志索引，flush 成功后就可以确认该索引以及之前的日志操作都是 rocksdb 已经持久化过的。
   出于性能考虑，并不会每次都添加新映射，而是有一定周期地更新。

2. Flush 时将 log index 存入 SST 文件：
   （存seqno只是为了debug，未来可删去）这里通过 rocksdb table property 特性，在每次 Flush 时将本列族的 logidx 与 seqno 的映射持久化到 SST 文件；具体来说，每次 Flush 时会对每个 key 遍历检查，我们可以保存最大的 seqno，最后利用最大的 seqno 在上述维持 seqno 与 logidx 的链表中，找到不大于该 seqno 的最大 seqno 与 logidx 的映射，这个映射中的 logidx 就是本次持久化对应的已知最新的 logidx，然后将该 logidx 写入SST，以供重启时提取。

   例如：Log100(Seq200, Seq201) , Log101(Seq202, Seq203)

   • 当我们 apply Log100 后，就应当在链表后添加 100:200 的映射，apply Log101 后，就应该添加 101:202 的映射
   • 当我们 flush 的内存中最新操作为 Seq200或201 时，应当在链表中找到 100:200 这个映射，然后将日志索引 100 写入 SST；当最新的操作为 Seq202或203 时，我们就应当找到 101:202 这个映射，把 101 写入SST。
   • 如果周期为2，假设 Log100 添加到链表中，Log101 没有添加到链表中，Log102(Seq204...) 添加到链表中。那么 Seq200-203 都应当找到 100:200 映射，然后将 100 写入 SST，Seq204 及以后的应当找到 102:204。

3. 在每次 Flush 完后，需要清理该链表：
   通过 rocksdb 提供的 event listener 特性实现，在每次 flush 完毕后触发清理操作，清理掉链表中已经持久化的最新映射之前的映射，主要要保留已持久化的最新的映射。

   例如：链表中已经有 100:200->102:204 两个映射

   • 当我们 flush 的最大 seqno 为 200-203 时，持久化 Log100，它之前没有别的映射，所以不能删除映射
   • 当我们 flush 的最大 seqno >= 204 时，持久化 Log102，就可以删除 100:200 这个映射

4. 重启后如何恢复数据：
   重启后需要通过 table property 特性，从已有的 SST 文件中读取之前保存的最大的 logidx。得到所有列族中最小最新 logidx，我们应当从 logidx + 1 处开始回放 braft 操作日志。