MOT索引

MOT索引基于最先进的Masstree的免锁索引，用于多核系统的快速和可扩展的键值（KV）存储，通过B+树的Trie实现。在多核服务器和高并发工作负载上，性能优异。它使用各种先进的技术，如乐观锁方法、缓存感知和内存预取。

在比较了各种最先进的解决方案之后，我们选择了Masstree作为索引，因为它显示了点查询、迭代和修改的最佳总体性能。Masstree是Trie和B+树的组合，用以谨慎利用缓存、预取、乐观导航和细粒度锁定。它针对高争用进行了优化，并对其前代产品增加了许多优化，如OLFIT。然而，Masstree索引的缺点是它的内存消耗更高。虽然行数据占用相同的内存大小，但每个索引（主索引或辅助索引）的每行内存平均高了16字节——基于磁盘的表使用基于锁的B树，大小为29字节，而MOT的Masstree大小为45字节。

我们的实证研究表明，成熟的免锁Masstree实现与我们对Silo的强大改进相结合，恰能为我们解决这一方面的问题。

另一个挑战是对具有多个索引的表使用乐观插入。

Masstree索引是用于数据和索引管理的MOT内存布局的核心。我们的团队增强并显著改进了Masstree，同时提交了一些关键贡献给Masstree开源。这些改进包括：

  • 每个索引都有专用内存池：高效分配和快速索引下移
  • Masstree全球GC：快速按需内存回收
  • 具有插入键访问的大众树迭代器实现
  • ARM架构支持

我们为Masstree开放源码实现贡献了我们的Masstree索引改进，可以https://github.com/kohler/masstree-beta找到。

MOT的主要创新是增强了原有的Masstree数据结构和算法，它不支持非唯一索引（作为二级索引）。设计细节请参见非唯一索引。

MOT支持主索引、辅助索引和无键索引（限制参见不支持的索引DDL和索引）。

非唯一索引

一个非唯一索引可以包含多个具有相同键的行。非唯一索引仅用于通过维护频繁使用的数据值的排序来提高查询性能。例如，数据库可能使用非唯一索引对来自同一家庭的所有人员进行分组。但是，Masstree数据结构实现不允许将多个对象映射到同一个键。我们用于创建非唯一索引的解决方案（如下图所示）是为映射行的键添加一个打破对称的后缀。这个添加的后缀是指向行本身的指针，该行具有8个字节的常量大小，并且值对该行是唯一的。当插入到非唯一索引时，哨兵的插入总是成功的，这使执行事务分配的行能够被使用。这种方法还使MOT能够为非唯一索引提供一个快速、可靠、基于顺序的迭代器。

图 1 非唯一索引
MOT索引 - 图1

上图描述了一个MOT的T表的结构，它有三个行和两个索引。矩形表示数据行，索引指向指向行的哨兵（椭圆形）。哨兵用键插入唯一索引，用键+后缀插入非唯一索引。哨兵可以方便维护操作，无需接触索引数据结构就可替换行。此外，在哨兵中嵌入了各种标志和参考计数，以便于乐观插入。

查找非唯一辅助索引时，会使用所需的键（如姓氏）。全串联键只用于插入和删除操作。插入和删除操作总是将行作为参数获取，从而可以创建整个键，并在执行删除或插入索引的特定行时使用它。