- 团队名称：ng-raft-engine
- 作者：@JaySon-Huang @lidezhu @CalvinNeo
- 项目仓库：https://github.com/JaySon-Huang/tiflash/commits/raft_ps_6.3
写放大和空间放大更低的 raft-engine。
随着 TiDB 承载的集群规模越来越大，以及 Dynamic Region 特性的引入，单个 TiKV 上承载的数据量愈发增加，单个 TiKV 实例中冷热 Region 带来的问题也会愈发明显。
目前的 tikv/raft-engine 对于 raft-log 的存储，使用了 append-only 的方式落盘到文件系统上。随着热 Region 的更新，有效的数据更多地集中在新的文件中。旧的文件中数据有效率下降，但是其中仍然存在少部分冷 Region 的 raft-log。为了回收硬盘上空间，raft-engine 需要不断地将冷的 raft-log 数据重写到新的文件中，带来写放大，与前台其他写入任务争抢 IO 资源。
随着近年存储技术的发展 SSD 性价比得到提升以及进一步普及，带来的变化是随机写入性能的大幅提升。我们实现了一个存储引擎 PageStorage，它参考 Ext4 中的设计，在内存中引入 SpaceMap 组件来管理硬盘上文件中哪些块是空闲的。数据删除后文件中无效的数据块记录在 SpaceMap 中，PageStorage 可以藉此来复用原文件中空闲的区域。
我们在 PageStorage 的基础上实现了 ng-raft-engine，借助内存的 SpaceMap 以及 SSD 出色的随机写入性能，我们避免了冷数据的反复重写带来的写放大。测试中，带 lz4 压缩的 raft-engine 写放大系数约 1.2，而 ng-raft-engine 能够做到 0.7，同时让硬盘空间放大维持在一个很低的水平。
由于 PageStorage 是用 C++ 实现，我们通过 FFI 的形式暴露 PageStorage 的接口，将 ng-raft-engine 中对 raft-log 持久化的操作从写入文件改为写入到 PageStorage 中。以 Region ID 和 Log index 作为 PageId 来读写 PageStorage 中的数据。为了维持 raft-engine 读取的高效性，我们在 MemTable 中保留 RaftGroup 的 first_index 信息。
ng-raft-engine 整体的架构如下。PageDirectory 是一个内存中的 ordered_map，存储着 PageId 到硬盘上 BlobFile 的物理位置。每个 SpaceMap 管理硬盘上的一个 BlobFile。多个 SpaceMap 及其对应的 BlobFile 作为 BlobStore。所有写入、删除 PageId->PageEntry 的操作都会记录在 WALStore 中。
与 raft-engine 写入到 append-only 文件的末尾不同，ng-raft-engine 中通过 SpaceMap 对 BlobFile 中的空余空间进行复用。在复用空间的情况下，写 BlobFile 只需要 fdatasync，而可以省去 sync metadata 的开销。SpaceMap 以红黑树的形式，以空闲块 (FreeBlock) 在 BlobFile 内的 offset 为 key，以空闲块的大小为 value。
下面主要阐述 ng-raft-engine 与 raft-engine 在写入和 purge 过程的差异， ng-raft-engine 是如何利用 SpaceMap 来减少写放大的。
写入 log file 整体可以分为两步：
-
对写入的 log file 进行 lz4 压缩后，在 SpaceMap 中找到合适的 BlobFile 及其插入 offset
-
将数据持久化到 BlobFile 中，以 (RegionId, LogIndex) 为 PageId 记录在 PageStorage 中
SpaceMap 的更新如下：
新压缩数据 D 需要插入，遍历 SpaceMap 的各个节点查找是否有大于 D.size 的空闲块 F。如果 F.size 正好等于 D.size，则将空闲块从 SpaceMap 中移除；如果空闲块大小大于 D.size，则将 SpaceMap 中的 F 替换为新的空闲块 {offset=F.offset-D.size, size=F.size-D.size}。 F.offset 即 D 写入到硬盘文件的 offset。
如果 SpaceMap 中无满足条件的空闲块，则创建新的 BlobFile 及 SpaceMap 并写入其中。
我们将 SpaceMap 中查找空闲块的操作实现为具有原子性，一旦 SpaceMap 中分配好了 offset，写入的数据不会被其他写入所覆盖。因此我们可以充分利用 SSD 的 IO 深度，并行进行多个写入 BlobFile 的 IO 操作。
删除 log file 可以分为四步
- 在 PageDirectory 中找到 (RegionId, LogIndex) 对应在硬盘上存储的 offset,size 信息
- BlobStore 中的 SpaceMap 会插入下删除后 BlobFile 空闲块的 F{offset, size}，为了减少碎片，提高空间利用率，我们会尝试将 F 与其在 SpaceMap 中的前、后两个空闲块进行合并
- 将 delete (RegionID, LogIndex) 写入 PageStorage 中持久化
- 更新 MemTable 中的信息
这样在数据删除后，BlobFile 中无效的数据块可以被后续的写入重复利用。
raft-engine 的内存 MemTable 中有最新数据在硬盘上的 index，因此在 compaction 阶段可以减少大量无效数据的读取。但是由于无效数据过多会引起空间放大问题，它仍然需要将旧的文件中有效数据读出来并重新写入到新的文件中。
因此 raft-engine 每次调用 pruge_expired_files 的时候，都会返回带有老旧 log entries 的 RegionId 列表，上层需要进行 compact log 操作来让 purge 顺利地推进到让旧的文件得到释放，减少空间放大。但这个行为会引入额外的写放大。
如果下游同一 raft group 的存储（如 tiflash）写入跟不上，过于频繁的 compact log 操作会导致数据同步给下游时无法通过发送 raft-log，而只能采取更加消耗 IO 资源的扫描 snapshot 方式来进行数据的同步。加剧其他行为对前台写入的 IO 影响。
在 ng-raft-engine 中，我们通过 SpaceMap 的内存结构来让 BlobFile 中无效的数据块得到重新写入新数据的能力。因此大多数情况下我们都不需要对旧的数据进行重写。同时也不需要为了减少空间放大让上层进行 compact log 操作。
问个 naive 的问题：原本的 raft-engine 本身是起到 WAL 的作用吗？换成 SpaceMap 之后在 recovery 时是怎么保证不同块之间的顺序的？