From Skiplist To Patricia Trie
众所周知，RocksDB 在执行写入时，将数据以 Append 方式写入 WAL(Write-Ahead-Log) 以及 MemTable，且不允许 MemTable 插入失败（这给我们造成了很大的麻烦，详见正文）。
RocksDB 在 MemTable 的内存用量超过阈值时，就把它转换成 Immutable MemTable 并创建新的 MemTable，顾名思义，Immutable MemTable 只可读取，不可写入。
RocksDB 的 SkipList 使用了 LockFree 技术，多线程插入时基本可以达到 Linear Scale，性能十分出众。但是，在 Insert 过程中，SkipList 需要执行 O(log(n)) 次 KeyCompare，当 KeyValue 中的 Value 很小时（例如 MyRocks 中的 SecondaryIndex，其 Value 一般是空的，即长度为 0），SkipList 的性能就难以接受了。
为此，我们首先使用基于数组的红黑树来实现 MemTable，但效果一般，并且并发插入性能还不如 SkipList。最终，我们下定决心，花费巨大精力实现了一个 Patricia Trie（后面简称 Patricia），作为 MemTable 的支撑结构。
Benchmark 过程中我们特意将 WAL 关闭，并且将 KeyValue 中的 Value 设为空，从而更能体现出不同 MemTable 之间的性能差别。
先看写性能（Put 操作）：
从上面的数据不难看出，Patricia 的性能远超 SkipList，并且，随着线程数增加，两者性能差距的倍数也在增加！实际上，这个性能比较中还掺杂了 RocksDB 本身的开销，如果去除 RocksDB 本身的开销，两者的性能差距大约是 7.35 倍（详见文末的证明）。
前面提到，我们使用 Patricia 作为 MemTable 的支撑结构。为了尽可能发挥 Patricia 的性能，我们使用了一些特殊的技巧，但本质上其思路并不复杂：
| 将任务拆分成多个小尺度的子任务，使它们可以并行执行，同时在执行过程中巧妙地处理冲突，尽可能减少锁的数量，缩小锁的粒度。 |
为了应对高并发的场景，Patricia MemTable 使用了 InstanceTLS，有效降低了多线程协调的损耗，使得 Patricia MemTable 能够最大限度上发挥出算法本身的性能（特别是写性能）。
▶ TLS 指 Thread Local Storage，从而 InstanceTLS 指的就是实例级的 TLS，即对于每个对象实例 a，其 InstanceTLS 成员 b 指的就是，通过 a.b.get_tls()，获得 a.b 对应于当前线程的 TLS 对象。
在实现的过程中，RocksDB 的一些设计缺陷给我们带来了一些非本质的，但是又很麻烦的问题：
- RocksDB 本身的限制：RocksDB 切换 MemTable 使用的方案是，MemTable 提供一个虚函数，告诉 RocksDB 该 MemTable 的实际内存用量，如果 RocksDB 觉得这个用量超过了限制（write_buffer_size），就会切换到一个新的 MemTable
◆ 即便发生了切换，这个切换也不是立即生效的，因为可能还有其它线程正在写这个 MemTable
◆ 只要 RocksDB 向 MemTable 写入，这个写入就必须成功，不能失败
◆ 在 WriteBatch 中，不管 WriteBatch 有多大，一个 WriteBatch/BatchGroup 只会写一个 MemTable
- Patricia 实现上使用了单块大内存作为 MemPool，数据结构需要的内存块都在 MemPool 中分配，并且使用 MemPool 内的 Offset 代替指针实现数据结构上的各种链接，这种设计有非常巨大的优势：
◆ 整个 Patricia 可以作为一个整体进行 memmove，读写文件（例如使用 mmap……）
◆ Offset 可以使用 32 位整数代替 64 位指针，从而节省一半的指针空间
▷ 内存一般都是对齐访问的，从而，即便 32 位的 Offset 只能表达 232(4G) 个不同的值，
按 4 对齐后却可以访问 234，即 16G 的地址空间
在多线程环境下，上述 1 严重制约了 2，以单块内存作为 MemPool 并使用 Offset 代替指针的 Patricia，一旦 MemPool 已满，就能不能继续插入数据，因为要继续插入数据，只能为 MemPool realloc 一块更大的内存，然而，如果 realloc 新的内存块时，另外一个线程正在读取这块内存……
我们曾尝试过修改 RocksDB 使得它允许 MemTable 插入失败，以便当 MemTable 插入失败时，就切换新的 MemTable，最后，因为 RocksDB 中相关的控制逻辑过于复杂，导致这个修改需要的工程量太大，不得不放弃！
于是我们就只能在 MemTable 的实现中解决这个问题：当一个 Patricia 写满时，就创建一个新的 Patricia，新的数据写入新的 Patricia，这样，写的问题解决了，读的时候，就需要在多个 Patricia 中搜索，最终，算上 InstanceTLS，每个并发写线程至少对应一个 Patricia。
还有一个细节需要处理，在某些情况下（例如一个应用层的 Session 连接），用户开启一个线程，写少量一些数据，然后退出该线程，这样会导致创建非常多的 Patricia，所以，我们又在 InstanceTLS 之上加入了一个对 Patricia 对象的复用，线程退出时把它对应的那个 Patricia（没写满的） 加入一个空闲表，每个线程创建 InstanceTLS 时先从空闲表中取，只有空闲表为空的时候，才真正创建新的 Patricia。
▶ 当然，我们总要划出一个边界：对于使用非常多（例如成千上万）的线程并发写入的场景，此时，每个读操作将会读取非常多（例如成千上万）的 Patricia，造成性能降低。我们不会为这种病态场景做优化。
优化永无止境，有一天，我们意识到，内存分配可以只分配虚拟内存！如此一来，对于每个 Patricia，我们一开始就给它分配尽可能大（16G）的一块虚拟内存，报告给 RocksDB 的内存用量是实际使用的内存用量，这样，不管 RocksDB 往 MemTable 中塞入多少数据，只要（对单个 Patricia 而言）没有超出 16G，这个 Patricia 就可以继续插入数据，从而减小了 Patricia 的数量，最终提高读性能。
▶ 这中间还有一个小插曲：Linux 中允许 mmap NO_RESERVE，从而几乎可以分配任意大的虚拟地址空间，然而 Windows 不允许单个进程虚拟地址空间超过 PAGEFILE + PhysicalMemory，从而在 Windows 下就不能肆意地分配 16G 虚拟内存……
当然，我们也继续保留让单个线程可以写多个 Patricia，————万一碰到大于 16G 的情况呢……
结合上自动调节 Patricia Set 所占用内存空间大小，使得这一结构的时空性能都很优秀。具体而言，
对于写入操作，Patricia MemTable 会将写线程的写入点映射到对应的 Patricia Set，再将数据写入。
而对于读请求，考虑到其占比较小，使用一个实时的堆状聚合器是再好不过的选择。这种堆状聚合器在点查询时（Get 操作），会将请求转发给每个 Patricia Set，将下层返回值汇总回传给上层；而在持续查询过程中（Seek 操作），这个堆状聚合器会以多路归并器的形式工作，使用下层 Patricia Set 的返回值更新缓存在聚合器中的数据，再回报给上层。
Patricia MemTable 的独特设计使得我们要详细地解释各类读操作的性能：
- 对于每个 MemTable 实例，通过使用 InstanceTLS，每个写线程都有一个独立的 Patricia 对象
- 对于每个读操作，需要逐个搜索所有的 InstanceTLS Patricia
- 如果 MemTable 是通过 n 个写线程生成的，读的时候，就需要搜索 n 个 Patricia
- 不管是 SkipList MemTable，还是 Patricia MemTable，读性能都可以按线程的数量 Scale
所以我们只看单线程读的性能：
- SkipList MemTable 的单线程读
- Patricia MemTable 在 1，4，6 个写线程的情况下的单线程读操作。
我们测得的读操作吞吐量的直观对比：
在 Get 操作上，Patricia MemTable 明显快于 SkipList MemTable。
在 Seek 操作上，Patricia MemTable 在 6 个写线程时稍低于 SkipList MemTable，这说明大略比例上，Patricia 的效率是 SkipList 的 6 倍左右。
需要特别指出的是，实际上由于 RocksDB 本身的开销，算法的运行效率并不等价于 MemTable 的效率，其实 Patricia Trie 的算法效率是要更高一些的，若要得出一个关于算法效率相对精确的结果，请参阅文末的注解。
在读写混合时，由于 Patricia MemTable 算法的优越性，在单一写线程时的混合吞吐量（Put，Get，Seek操作），一样有很大的优势。
Put，Get，Seek 线程数均为 1 时的混合吞吐量：
通过上文的分析，我们可以得出，Patricia MemTable 在保障了读性能的情况下，大大优化了 MemTable 的写入性能，吞吐量远超原生的 SkipList MemTable，是其效率的四倍以上。
至此，我们简要的介绍了为高压写场景优化的 Patricia MemTable，更多关于 TerarkDB 的信息与资料，欢迎访问我们的官网。
由于 RocksDB 本身需要消耗一定的时间，所以为了计算算法本身的性能，需要刨除 RocksDB 消耗的时间。
为简便，不妨设线程数为 n, 数据尺寸为 s, RocksDB 层的处理速度为 vr。
而 vp，vs 分别是 Patricia 与 SkipList 的处理速度，tp，ts 分别是 Patricia 与 SkipList 的运行时间。
对于读操作的情况，具体有，
显然，
结合上文的数据，可以得出 Patricia 的读性能大约是 SkipList 的 7.3 倍。
而对于写操作来说，我们可以列出如下的方程 :
其中，tr 是 RocksDB 层的所占用的时间。
又因为我们测得 Patricia MemTable 的 Put 操作占了整个写入流程 49% 的时间，
所以结合测试数据可以得出 Patricia 的写性能大约是 SkipList 的 7.35 倍。