数据库内核月报 － 2021 / 01

背景

如何选择内存索引结构是设计和优化数据库时的一个关键问题。因为无论是内存数据库还是磁盘数据库，内存索引都是一个至关重要的部分，极大地影响了数据库的性能表现。对于内存数据库，内存索引是读写路径上的核心结构，而对于磁盘数据库，在服务器内存足以缓存绝大部分热数据的场景下，内存索引可以大幅加速热数据的读写。

然而，选择合适的内存索引结构并不是一件简单的事情。首先，一直以来内存索引的设计在学术界和工业界都是一个万家争鸣的局面，内存索引结构的种类非常多，并且没有哪一种索引能在各个方面都实现领先，因此在选择时就需要根据不同的场景进行权衡。其次，一些内存索引的论文中使用的工作负载与实际应用场景存在一些差距，或者数据量较小，或者索引键的组成较为简单，仅使用整型或者反转的email地址，因此这些论文中的评估对索引结构选择的参考价值不大。另外，不同内存索引的实验评估中使用的硬件系统环境和工作负载都不同，甚至存在较大差异，难以比较它们之间的性能优劣。

因此，给各类内存索引一个“同场竞技”的机会是非常必要的。一方面，在相同的硬件环境和工作负载下对内存索引进行评估，可以给内存索引的选择提供参考。另一方面，对内存索引的评估也有助于更深入的理解不同内存索引的设计理念对性能的影响，为设计新的内存索引提供一些启发和借鉴。

在本文中，我们根据一定标准选择了五种内存索引，评估了它们在不同场景下的性能表现。由于内存索引结构种类很多，对所有的内存索引进行评估显然不可行，因此我们根据如下的标准来选择进行评估的内存索引：

• 支持数据库的通用语义：随机写入，点查询，范围查询
• 具有代表性：同一类的内存索引可能有很多变体，比如字典树就有Patricia Trie、ART、HOT等等，我们仅选择同一类中具有代表性的内存索引结构
• 已经集成进数据库系统：一些内存索引虽然性能优异，但是存在诸多限制，难以在数据库系统中应用

根据这样的标准，我们选择了Skiplist，BwTree，BTree，Masstree和ART这五种内存索引。我们将它们集成进了PolarDB X-Engine的MemTable中，使用db_bench评估了它们在不同数据量，不同索引键长度下的随机写入、点查询、范围查询这几方面的性能表现。

实验评估

实验环境

• Intel(R) Xeon(R) CPU E5-2682 v4 @ 2.50GHz， 32core 64threads， 2Socket.
• L1-Cache：32KB Data Cache，32KB Instruction Cache
• L2 Cache：256KB
• L3 Cache：32MB
• RAM：512GB，2133 MHz DDR4

实验设计

关于我们评估的五种内存索引，其中Skiplist是PolarDB X-Engine的MemTable使用的无锁实现，BwTree是OpenBwTree这篇paper中的开源实现，In-memory BTree是基于Logical and Physical Versioning的无锁BTree，Masstree也是论文中的开源实现，ART是我们根据论文实现的。

我们分别使用db_bench的fillrandom，readrandom，seekrandom来评估内存索引的性能，通过系统参数控制不发生SwitchMemTable和Flush，使用32线程压测一个ColumnFamily。db_bench原有的索引键生成方式是在64位整型后补ASCII字符0，我们修改了索引键的生成方式，使较长的索引键和数据库中复合索引的键模式接近，而较短的索引键和数据库中整型索引键一致。

实验结果

点查询

改变数据量

我们使用长度为64Bytes的字符串类型的key和128Bytes的value，测试了五种内存索引在不同数据量大小的场景下的点查询吞吐（200M-10G，对应1million-50million的键值对）。实验结果显示，五种内存索引中In-memory BTree，Masstree和ART都能达到千万级别的吞吐，其中ART在不同数据量的场景下性能表现都是最佳的。

从结果中我们观察到，在我们的测试场景下，ART的点查询性能显著地高于其他的树形索引，我们为此深入研究了ART的实现，并结合测试负载的特点，认为ART性能突出的原因主要有两点：

• 数据结构自身查找性能的差距。字典树的查找开销是常量级O(k)，而搜索树的查找开销是对数级O(LlogN)。在较为理想的情况下，一个朴素的字典树，每一层对应key中一个位置的字节，考虑每个节点的扇出最高是256，最少只需要搜索4层即可覆盖超过40亿个key的索引空间，无论是计算开销还是访存开销都很低。
• 使用自适应的节点格式，并在不同的节点格式中使用不同的查找方式。字典树中不同的节点可能有不同的扇出，ART共有四种不同的节点格式：Node4、Node16、Node48和Node256，分别存储不同扇出的节点。采用这样的设计有两个好处：
  • 提高缓存效率。针对扇出较小的节点，如果统一使用包含256个指针的节点，可能会有较多的空闲空间，如果使用变长的节点形式，内存分配过程中可能会产生大量的内存碎片。采用不同格式的节点，并预分配固定的空间，可以在节省内存的同时降低写入时内存分配的开销、减少内存碎片。
  • 可以根据不同格式的节点选择最优的查询方式。除了Node256可以直接通过下标找到子节点的指针外，其他节点的查询都需要额外开销，这里针对不同格式的节点，选择了合适的查询方式。对于Node4，节点中最多存储4个字符和4个指针，因为数据量小，只需要顺序遍历即可。对于Node16，节点中最多存储16个字符和16个指针，可以使用SIMD指令集，在几个CPU cycle内并行比较节点包含的所有字符，找出子节点的指针。对于Node48，节点中使用一个长度256的uint8数组和最多存储48个指针，uint8数组作为一个hashmap，将字符映射到指针数组中的对应位置。

我们也观察到，在我们的测试场景下，Masstree的性能介于ART和In-memory BTree之间，这也是符合我们的预期的。Masstree实际上是介于字典树和搜索树之间的结构，以8字节为单位形成字典树，每层节点最高扇出为2，每层节点对所涵盖的key的8字节内容使用BTree来索引。相对于In-memory BTree，这样的设计可以在一定程度上减少索引键前缀的重复比较，在存在公共前缀的场景下带来性能提升。同时Masstree在每层节点内的BTree中，做了更精细的优化，将8字节字符串转换为整型进行比较，并在border node中引入特殊的存储组织形式。然而，即便64Bytes的较长的索引键并非ART索引的理想场景，而对Masstree非常有利，Masstree的性能相对于ART依然存在明显差距。因为Masstree虽然形似字典树，但在每层节点中搜索的代价依然是对数级O(logN)，而ART在这样的场景下虽然层数更多，但在每层节点中搜索的代价仅为O(1)。

另外，我们还观察到BwTree的性能是最差的，原因是尽管BwTree在读到一个包含多版本的节点时会做Node Consolidate，其最终形态和BTree差不多，但是BwTree中节点之间使用间接指针相连，访问节点需要进行一次哈希查找才能获得节点的实际地址，这样的间接引用在纯内存场景会带来相当大的开销，对性能的影响往往是致命的。当然，开源版本的BwTree实现可能比较朴素，缺少工程优化，我们了解到Hekaton中使用的BwTree做了非常多的工程优化来弥补因间接引用等设计上的缺陷带来的性能损失。然而，实际上Hekaton发表的关于BwTree的论文中也没有和In-memory BTree进行性能对比，而是和磁盘BTree（BerkeleyDB）进行了对比。

对于Skiplist和BTree这两类传统的索引结构，其中BTree在纯内存场景依然具有比较好的性能表现，原因是因为BTree读路径的空间局部性和时间局部性相似，对CPU cache比较友好，能很好利用硬件prefetch带来的性能增益。而Skiplist虽然查询的算法复杂度也是对数级，然而读路径几乎每次访问都会发生一次cache miss，带来很大的访存开销。

改变索引键长度

我们测试了五种内存索引在不同索引键长度下的点查询吞吐（8Bytes-64Bytes），测试中使用的数据量均为50million的键值对。实验结果显示，五种索引在索引键长度增加时吞吐都有所下降。其中搜索树类型的内存索引性能下降的原因是索引键每次比较的开销更大，而字典树类型的内存索引性能下降的原因则是索引层数增加。

值得注意的是，Masstree的性能随着索引键变长，下降幅度相对较小。原因并不是因为Masstree在不同索引键长度的场景下可扩展性更好，而是因为Masstree在索引键较短（或索引键公共前缀较短）的场景下（如实验中8Bytes索引键的场景）性能表现较差，所以64Bytes索引键的场景相对于8Bytes索引键的场景下键幅度不大。因为在索引键较短（或索引键公共前缀较短）的场景下，Masstree在结构上退化为了BTree，无法通过减少前缀重复比较提升性能，相对于BTree的性能提升仅仅来自于设计上更精细的优化，例如将8字节字符串转换为整型进行比较。

而对于ART来说，不论索引键的公共前缀长度如何，都能获得极好的性能表现，这得益于使用path compression和lazy expansion来优化字典树查询。在较不理想的场景（索引键较长且公共前缀也较长）下，索引键可能有很多很长的公共子串和唯一后缀，如果使用朴素实现，可能会产生非常多的扇出为1的节点，造成额外的访存开销。使用path compression和lazy expansion可以较好地解决这样的问题。而索引键较短或公共前缀较短的场景则是ART的理想场景，自然可以获得极佳的性能。

范围查询

改变数据量

我们在点查询的对应实验场景下测试了不同数据量大小的场景下五种内存索引的范围查询性能。实验结果显示，五种内存索引中In-memory BTree在不同数据量的场景下性能表现都是最佳的。另一个值得注意的地方是，在所有场景下点查询性能最佳的ART的范围查询性能并不好。

数据结构特点和代码实现影响了五种内存索引的范围查询性能。从数据结构特点的角度来看，键值对在BTree的叶节点中全局有序紧密排列，范围查询在一次点查询后顺序迭代，迭代时CPU cache的效率很高。而对于ART，即便我们做了一些调整，使用有序双向链表连接ART的值节点，在链表中迭代的过程中每次访问都会发生一次cache miss。

改变索引键长度

我们在点查询的对应实验场景下测试了不同索引键长度下五种内存索引的范围查询性能。和对应场景的点查询性能表现类似，五种索引在索引键长度增加时吞吐都略有下降。

写入

我们使用长度为64Bytes的字符串类型的key和128Bytes的value，测试了五种内存索引在50million数据量的场景下的写入吞吐。实验结果显示，五种内存索引的写入性能较为接近。尽管内存索引的写入性能和点查询性能是有一定关联的，因为每次写入时找到插入位置的过程都类似一次点查询，然而写路径上还有一些加锁、修改数据结构、分配内存的操作，所以五种内存索引的实际写入性能差异不大。