ToplingDB CSPP Trie 设计思想

MemTable 的并发写实际上是⼀个 Ordered Index 并发写 的 问题。RocksDB 对此的解决⽅案是 SkipList，业内知名的⽅案还有 libart、hot、bwtree 等等。

我们的解决⽅案是 CSPP Trie（Crash Safe Parallel Patricia Trie），⽬前尚未⽤到 Crash Safe 功能。

CSPP Trie 代码已开源：topling-zip/cspptrie.cpp

Patricia Trie 介绍

Patricia Trie 也叫 Radix Tree，两者是同⼀个东西，只是名字不同，Wikipedia 上有⾮常好的介绍，我们就在此略过对其原理性的介绍（Radix Tree on wikipedia）。

Patricia Trie 的 Topling 实现

现代多核多路 CPU 最怕的就是跨核修改相同地址（更准确的说是相同 CacheLine）的内存，这⼀点我们⽆法改变，只能去适应。⸺其实，我们只需要把多核多路 CPU 看做是集成在⼀个主板上的分布式系统，就⽐较容易理解硬件的限制了。

变⻓结点

Trie 树结点最多有 256 个孩⼦，如果我们总是给它分配这么多空间，那就是定⻓结点，事情将会⾮常简单，即便是在多核并发写场景：

• Copy On Write 将成为多余的东西
• 纯插⼊时，Token 和 LazyFree 也成为多余

Copy on Write

要在多核下⾼效⼯作，多个核彼此之间的交互必须尽可能地最少化。然⽽，传统上，如果我们要修改⼀个结点，那就对这个结点加锁，改完之后解锁。⸺很多现有系统确实是这样⼲的！在核数较少，性能需求也不⼤的场景，这种⽅式貌似看不出有啥问题。

然⽽，现在的 CPU 动辄⼏⼗上百个核， 双路 AMD Epyc 有128核256线程 16 内存通道，双路 Intel Xeon 9282 有 112核224线程 24 内存通道。如果还⽤传统⽅案，多线程并发写⽐单线程还要差。

Copy On Write 的核⼼要旨有两点：

• 把要修改的结点拷⻉⼀份，在拷⻉上修改
• 使⽤ CAS 替换指向该结点的指针

接下来，我们还不能⽴即释放旧的结点，因为可能同时其它线程还在访问旧的结点。

Token + LazyFree

传统上，与 Copy On Write 结合使⽤的，是引⽤计数，⾸先就要对每个结点增加⼀个引⽤计数字段，每次要访问结点，先增加引⽤计数，访问结束了再减⼩引⽤计数。从⽽，根据引⽤计数，我们就能知道结点是否可以被释放。

然⽽，引⽤计数有两⼤问题：

1. 浪费空间

在 BTree 这样的数据结构中，结点尺⼨⼀般都很⼤，引⽤计数占的空间⽐例很低（引⽤计数⼀般不保存在⻚内，⽽是在⻚的元数据中），⼏乎可以忽略。然⽽在 Patricia 中，结点的平均尺⼨很⼩，引⽤计数占的空间⽐例就太⾼了。

1. 增减引⽤计数是写操作

写操作会导致 CPU Cache 变脏，即便是在单核环境下，也会严重影响性能。在多核环境下，写内存（被多个核⼼都 Cache 了的内存）会引起 CPU 核⼼之间的交互，这个问题⽐空间浪费要更加严重。

所以，我们必须另想办法，⾸先，引⽤计数的两⼤问题是绝对不能有的（实际上，因为⼼中的执念，从⼀开始就根本没考虑过引⽤计数）。

我们⽤ Token + LazyFree 解决了这个问题（参⻅CSPP Trie 设计解析）。

Instance TLS

主流平台（Windows&Linux）很早就⽀持 TLS(Thread Local Storage)，C++11 也在语⾔层⾯⽀持 TLS。但是这些 TLS 都是线程的全局变量，在很多时候，我们需要对象级的 TLS，但这个功能在C++ 的语⾔层⾯没有⽀持。

boost，tbb 有实例级的 TLS，但其底层实现使⽤了 map/hsahmap，性能较差，为了保证性能，我⾃⼰轮了⼀个 Instance TLS。

Thread Cache MemPool

使⽤了 Instance TLS 的 MemPool，关键点：Thread Cache 的不是 Memory，⽽是 Memory FreeList，确切地说，是 把 FreeList head 做成 Instance TLS。

MemPool 的核⼼就是把内存管理局部化，全局的 malloc 有各种实现，这些 malloc ⼀般都会考虑 Thread Cache 问题。MemPool 也有很多开源实现，最典型的就是 std::allocator ，但是这些 MemPool 都有⼀个普遍的问题：

其操作的对象是全地址空间的指针，它们作为 MemPool 内存管理的局部化，只是把指针的逻辑管理局部化了，但指针的指向在物理（这个物理指的是指针的值，不是指物理地址）上仍然是分散的。

所以，MemPool 我们也得⾃⼰实现，实际上，我很早以前（2012年）就实现了这种 MemPool

并使⽤在多种场景下，我们的 MemPool 有以下关键 Feature：

1. 整个 MemPool 是⼀整块连续内存
2. 使⽤块内偏移代替指针，数据结构的链接关系使⽤块内偏移来表达
3. 1. 从⽽这块内存可以随意地被 memmove，可以 mmap ……
4. 对块内偏移进⾏适当的对⻬，以增加寻址范围
5. 1. 使⽤ 32 位整数作为块内偏移来寻址任意字节，寻址范围是 2的32次⽅，即 4G，如果我们把地址对⻬到 8，寻址范围就增加到 8 倍，即 32G，如果对⻬到 4，就是 16G。

虽然这些关键 Feature 很早就已经确定，但是对于多线程并发写，因为⼀直没有需求，也就⼀直没有实现。对于 CSPPTrie ，并发写是必备需求，所以也就⾃然⽽然地把 malloc 的 Thread Local思想⽤到了 MemPool。

深层话题

既然 MemPool 中⽤的都是块内偏移，那么它就可以直接 mmap 过来使⽤，这⼀点，也在很早以前就是我们的传统了：把数据结构创建好，保存⽂件，使⽤的时候以 readonly 的⽅式 mmap 进来。

CSPP Trie 把我们的这个传统往前⼜推进了⼀步：以 Read Write 的⽅式使⽤ mmap！初⼀乍看，好像⽆⾮是把 malloc 的 anonymous mmap 换成显名的 mmap，并没有什么新意……

但是，仔细思考这两个关键点：

• Copy On Write
• 显名 Writable mmap

Copy On Write 保证了在任意时刻，数据结构都是完整可⽤的，⽽我们知道，在 mmap 上写⼊数据是跨进程即时⽣效的，并且，即便写 mmap 的进程崩溃，崩溃前⼀刻写⼊的数据也是对外可⻅的，并且操作系统在定时刷脏时会将写⼊ mmap 的内容 sync 到⽂件中，从⽽这些更改就持久化到⽂件中了。

基于以上事实，我们可以得出结论：CSPP Trie 原⽣实现了事务 ACID 中的 ACD 三个属性。余下的 Isolation，本质上是更上层系统的功能。

从⽽，如果基于 CSPP Trie 来实现存储引擎，在某种程度上可以代替 WAL-Log 的功能。

最终，我们得到了⼀个 Crash Safe Parallel Patricia Trie，简称 CSPP Trie。