ToplingDB 省略 L0 Flush

ToplingDB fork 自 RocksDB，自然而然地兼容了 RocksDB 的生态，但是，兼容 RocksDB 有优点，就自然有缺点，例如 RocksDB 的 L0 Flush 在我们看来就完全是多余的，但是，要去掉 L0 Flush，并且在 RocksDB 的巨大的 Code Base 上动刀，难度杠杠的，不过，至少，我们的思路是清晰的：

省略 L0 Flush

1. L0 中的数据很新，即便 Flush 到了 SST，实际上一般都在内存中
2. 在实际场景中，L0 Flush 之后，一般很快就会发生 L0->L1 Compact
3. 在最坏情况下，L0 中的同一份数据会存在至少存在 4 个甚至 5 个副本，比如提交一个较大的 WriteBatch时，同一份数据有以下副本：
   1. WriteBatch 中的副本
   2. MemTable 中的副本
   3. WAL Log 中的副本（WAL 一般不使用 Direct Write，从而在 PageCache 中）
   4. L0 SST 中（Flush 结束，新的 Version 产生，旧的 Version 还在使用中，L0 SST 在 PageCache 中，因为 L0 Flush 很频繁，所以这样的新旧 Version 经常同时存在）
      1. BlockCache，用新的 Version 访问数据，导致数据被加入 BlockCache（从而又多了一个副本，共 5 个副本）
4. 某些情况下，写入 WriteBatch 之前用户业务层还会维护一个副本，此时最多就是 6 个副本
   1. 这个副本超出了引擎的管控范围，不在讨论范围内

副本数多了，最重要的不是浪费内存和磁盘空间（因为 L0 的数据总量并不大），而是浪费 CPU 和内存带宽，最最严重的是浪费 IO 带宽，并且因为 Flush 是在极短的时间内将内存中的数据写到 SST 文件中，会造成一个很大的 IO 尖刺。

然而我们仔细思考，L0 Flush 是可以省略掉的，但是引擎的 Write 流程和数据的组织方式需要进行大幅度的调整：

1. 预留 WAL Log 文件空间，并 mmap 到内存（以只读方式，便于排错）
   1. 写 WAL Log 仍然用 write，便于排错
2. 关闭 WAL Log 时，写入结束标记（EOF）并 truncate 到文件实际尺寸
3. WAL Log 中 Key 内部及 Value 内部不能有 Padding（以便在用户空间直接通过 Slice 访问）
   1. RocksDB 当前的 WAL 中，当 KV 跨 Page 时，会填入 Padding
4. WAL Log 中每个 WriteBatch 要有 checksum（至少 64 位）
   1. 当进程挂掉时，WAL 中未完成的 WriteBatch 会发生 checksum 错误
   2. Replay WAL 时，将 checksum 错误的认为是非正常的 EOF
5. MemTable 中不保存 Value，而是保存指向 KV 在 WAL 中的偏移（从而可以通过 WAL 的 mmap 去访问）
6. 借助 CSPP Trie，即便在 DB 异常关闭的情况下（进程挂掉，但OS和硬件都没挂），还可以省去 Replay WAL 阶段
   1. 借助每次 WriteBatch 之后保存的 WAL 偏移来跳到最后失败的那个 WriteBatch
   2. 当然，如果 OS 和硬件无法信赖，那就只能 Replay 了，借助 checksum 来尽量恢复数据

这样可以将副本减少到两个（WriteBatch 和 WAL，MemTab 中只是索引），注意，这里，最重要是节省了 CPU 和内存带宽的消耗，而不是内存空间！

并且，即便 DB 压力再提高 1 倍，也不会象 Flush 到 SST 那样产生 IO 带宽尖刺，因为数据写入 WAL 的速度是相对比较均匀的。

读放大也减少了

省略 L0 Flush 之后，就只有 Compact，最初的 Compact 就是 MemTab+WAL 的组合体(简称 MemTab 吧) 与 L1 的 Compact。以这样的方式，最多就只需要两个 MemTab：

1. 一个正在执行 MemTab + L1 Compact 的 MemTab，此 MemTab 只读，不可写
2. 一个活动中的可写的 MemTab

具体策略上，一旦可写的 MemTab2 达到尺寸限制（应该是两个限制并且很大，例如 10G 和 20G，对应 rocksdb 的 level0_slowdown_writes_trigger 和 level0_stop_writes_trigger），就需要产生新的 MemTab3，并执行 MemTab2 + L1 Compact，如果此时上一个 MemTab1 + L1 仍在执行中，写入就要主动卡顿甚至暂停一下了。所以：

1. MemTab + L1 Compact 最好是多线程执行，并且每个线程的数据量大致均等，也不做任何压缩
2. 为了让后续的 L1 + L2 Compact 尽可能并发，L1 的 SST 文件数目要尽量多一点，大小要尽量均匀一点

这两个需求加到一起，就又需要 MemTab 有 GetRandomKeys 功能，以便在 MemTab + L1 Compact 中可以将输入和输出数据都分得更细更均匀。

更进一步

如果我们有能力进行更大的改造，WriteBatch 中的那份副本也可以省略，就是写 WriteBatch 时将数据直接写到 WAL 中，但这样在填充 WriteBatch 期间，就只能单线程运行，而这是我们不能接受的，所以，省略 WriteBatch 的副本，需要基于 thread local WAL 来实现。

即便如此，SeqNum 也是个问题，在这样的 WriteBatch 中，所有 KV 的 seqnum 必须是相同的（rocksdb 的 seq_per_batch），并且，在 commit 之前，这个 WriteBatch 中的数据必须是对外不可见的。