共计 2449 个字符，预计需要花费 7 分钟才能阅读完成。
（一）背景 ToplingDB，尽管 fork 自 RocksDB 并且兼容其 API，但实现了本性难移的改良，最重要的就是实现了性能更高的 CSPP MemTable(Rep) 和 SST。CSPP MemTable 基于 Topling CSPP Trie，无论读写，CSPP Trie 的单线程性能都很高，并且多线程性能近乎线性扩大。本文具体介绍如何将 CSPP Trie 的能力利用到 MemTable。在 RocksDB 中，MemTable 设计上分两层，下层叫 MemTable，上层叫 MemTableRep，下层是 MemTable 公共代码，间接与 DB 进行交互，MemTableRep 是凋谢的接口层，能够有不同的实现，仅被 MemTable 应用，不间接与 DB 进行交互。（二）CSPP MemTableRepCSPP Trie 的构造函数：MainPatricia::MainPatricia(size_t valsize, intptr_t maxMem,
ConcurrentLevel, fstring fpath_or_conf) {...}其中 valsize 参数指该 CSPP Trie 的所有 Value（此 Value 非 DB 的 Value）其长度都是定长 valsize，当 valsize == 0 时，CSPP Trie 相当于是个 std::set<string>，非 0 时，相当于 std::map<string, FixLenValue>（FixLenValue 必须是 POD 类型）。在 MemTable 中，一个 UserKey 会有多个版本，咱们实现该性能对应的逻辑等效品是：std::map<string, vector<pair<Tag, string> > // Tag is uint64{Seq(56 bits), ValueType(8 bits)}
这与 RocksDB 的 SkipList MemTable 不同，SkipList 通过 InternalComparator 来实现该性能，其逻辑等效品是：// InternalComparator 先比拟 UserKey，再比拟 Tag，Seq 从大到小
std::map<pair<string, Tag>, string, InternalComparator>
在 CSPP Trie 的单块内存中，不能用原始指针，而应用 uint32 整数代替指针，并且咱们对齐到 4 字节，于是最低 2 bit 都是 0，所以咱们将 uint32 转化为 uint64 再左移 2 位，从而就能够用 32 位的整数来实现 16G 的寻址范畴。这样做最大的益处是该单块内存能够 memmove，能够存储到文件再间接 mmap……麻烦之处在于，咱们要手工进行将偏移转化为内存地址，还要手工实现这种 vector 的追加、搜寻等等，一个繁难的实现计划就像这样：
VecMeta 相似于 std::vector 对象自身（蕴含 data_ptr, size, capacity），咱们同时把 size/num 的最高位作为 lock bit，作为 UserKey 级别的锁——多个线程并发写同一个 UserKey 时。前面的逻辑就都比较简单了：应用 VecMeta 实现逻辑 std::vector<Entry>，其中 Entry 是：struct alignas(uint32) Entry {
uint32 value_offset;
uint64 tag;
}; 而后再顺着 Entry.value_offset 拜访 Value 内容，Value 内容跟 SkipList 完全相同，都是以变长编码 value length 的作为前缀，前面跟 value 的数据内容。RocksDB 的 MemTable/MemTableRep 本来 Key 和 Value 都是变长 len 前缀编码的，因为其所有的 MemTableRep 都是基于比拟的容器，保留了 Key 的原始内容，这样的设计很正当。而 CSPP Trie 并不保留原始 Key，而是在搜寻过程中重建 Key，RocksDB 的接口设计就不适合了，所以咱们对其进行了重构，将 Key 的类型泛化为 Slice，对其本来的 MemTableRep，转调一下即可。Value 的编码方式咱们没有必要改变，仍放弃原样，以缩小代码批改，并放弃兼容性。（三）Copy On WriteCSPP Trie 在多线程并发插入的时候，应用了 Copy On Write，从而后面的 FixLenValue(具体为 VecMeta) 局部就可能会被 Copy On Write，如果线程 A 和 B 并发执行，A 正在 Copy On Write VecMeta，线程 B 正在批改 VecMeta.num，这就完蛋了，线程 B 批改的是旧的 num（线程 A 执行 Copy On Write 之前的 num）！每到这种时候，咱们都会想到一个计划：退出一个中间层！于是咱们失去：
退出这个高亮的中间层，它就是简略的 uint32，作为一个指针，指向 VecMeta，这个 uint32 一旦调配，永不扭转，所以听凭 CSPP Trie 怎么 Copy On Write，都不会有影响。首次插入一个 UserKey 时，在 CSPP MemTable 中，牵涉到 3 块内存的调配（在 CSPP Trie 的 mempool 中）：len 前缀编码后的 ValueEntryVec 中的 Entry（此时只有一个 Entry）VecMeta 这 3 块内存咱们最后为每块内存独自调用调配函数，起初意识到，这些内存大多时候会一起拜访，特地是大多数 UserKey 都只有一条 Entry。所以这三个内存调配就合成了一次调配，而后三块内存各取所需，所以，逻辑上它们是三块内存，但物理上紧紧相邻，改善了空间局部性，从而进步 CPU cache 命中率。（四）ConvertToSSTCSPP Trie 外部的 mempool 能够是文件 mmap，咱们利用这个能力，能够将 MemTable 间接“转化”成 SST，防止了通过 MemTable Flush 遍历 MemTable 将所有 KeyValue 逐条写入 SST。既优化了 IO，又升高了 CPU 和内存的耗费。具体内容，能够看：对于共享内存 shm 和内存映射 mmap 的区别是什么？– 知乎 (zhihu.com)
【完】
