HOT: A Height Optimized Trie Index for Main-memory Database System

摘要

高效 节省空间
核心思想是每个节点的bits(span)动态变化以实现高的fanout和好的cache效率

节点的设计 紧凑，用SIMD能快速查找

HOT在String关键字上性能和空间表现极好，在整型关键字上也很有竞争力

介绍

在内存数据库中，好的Trie树索引要比B树索引性能好得多。但Trie树也有问题，如ART在整型key上的fanout大，性能好，但在字符串key上，平均fanout就小得多了。这种由于数据的稀疏导致fanout小在Trie树上是普遍存在的。

基于以上问题，本文中提出了HOT，完全的索引功能，好的查找性能，极小的空间消耗（尤其是string data，索引本身要比string data小很多）。

HOT最重要的特性是不论数据分布如何（稀疏/稠密）它都能达到一个很大的平均fanout。与其他Trie树相比，HOT的span是不定的随着数据分布而调整，而保持fanout的稳定来避免数据稀疏的问题。——空间消耗减少、树的高度降低，提高了cache efficient。

另外HOT在节点的layout上针对现代CPU进行了特殊设计。节点为cache efficient进行了优化，并支持SIMD优化查询。

同步用的ROWEX

项目

相关工作

Trie树已经证明了在内存数据库上性能更好。之前的研究都是如何降低树的高度。下面来看一下在binary trie上进行的优化。

如图，一共有13个key插入到了一个binary trie(a)中，一个简单的优化就是将路径中没有分支(区分)的节点进行合并，也就是Radix Tree(b)，合并之后的树就是一个满二叉树了。虽然radix大大减少了节点数，但是span为1时树的高度实在是太高了，所以有了增大span，来降低树的高度(c)。增大span带来一个问题就是在存储稀疏数据时，节点太空了，造成了空间的浪费。在c的基础上，把那些只有一个孩子的节点进行合并到区分节点上（不应该叫作合并，两种解决方法，乐观方法是只记录跳过的个数，悲观方法会记录前缀，最后图中叫omit。和radix tree一个意思，也是ART中的路径压缩path compression），这样又省下了两个节点。为了解决span大空间浪费的问题，ART提出了adaptive node，极大的减少了空间消耗。但ART还有一个问题就是，在稀疏数据上，树的下层节点fanout都很小，没有影响到fanout和整体树的高度。

对以上方法做一个总结，那就是他们都是把多个binary trie的节点结合成一个，以降低高度增加fanout。但是这些方法选取的结合标准，也就是每个节点的span，这与数据的存储是独立的。——这也就导致空间消耗与访问性能都严重依赖于数据是如何存储的

基于以上工作，本文提出了HOT，结合多个BiNode成一个Node，使得Node达到预先定义的fanout k来优化最终的高度。每个节点调整相应的span来表示区分的bits，忽略其他(不能用作区分key的)bits(如跳过)。

HOT

前面说要把多个BiNode节点合并成一个节点使其达到fanout k。最重要的优化是增加span，但是当前的索引span都是固定的，全局的，不管存多少key——因此性能和内存消耗都随着数据集而变化。
为了解决稀疏数据的问题，HOT的每个节点根据数据分布适应性变化span，稠密的数据span小（如根节点附近），稀疏的数据span较大（低层）。——HOT两个特性：基于数据的span和固定的fanout k。

准备： k-约束 Trie

HOT的每个节点都代表一个fanout最大为k的binary radix tree。一个节点最多存k-1个内部节点BiNode和k个叶子(指针)。

有多种节点组合方式，k=3，3.a的划分节点少，3.b的划分高度低。

插入

与B树类似，一般情况下只影响插入的那个节点，其他情况需要对树的结构进行调整。

下面看例子，k=3(每个节点可以有3个BiNode和两个leaf)，4.a是初始状态

• 一般情况，4.b，插入新key0010后节点没有溢出，只需要创建新的区分节点BiNode，只适用于entries少于k个的情况
• 叶子节点下推：需要创建一个新的节点而不是向一个已经存在的节点加一个BiNode。如果mismatching的BiNode本身一个叶子并且这个Node n是中间节点(h(n)>1)，那么就用一个新的节点来取代这个leaf。这个新节点包含一个BiNode和两个leaf。——未影响树的高度。如图4.c
• 除了上面的一般情况和leaf-node pushdown还有溢出 ，如图4.d，对于这种情况有两种解决办法，用哪种取决于当前节点和父节点的高度：1) parent pull up，那这节点的根BiNode移到父节点，如果父节点也溢出递归移根BiNode直到根节点，根节点溢出分裂，适用于h(n)+1 = h(n.parent)——不需要修改中间的高度；2)创建中间节点：当前节点直接分裂成两个节点，直接创建一个新的节点，把root BiNode移进去，适用于h(n)+1<h(n.parent)，意味着在中间加个节点不会增加树的高度。

HOT的属性

HOT是纯Trie树，每个节点都代表着key的前缀。但它和基于比较的多路结构又比较像(进行log2(n)次比较)。像B树，HOT的每个节点的最大fanout是有界的，通过动态分布数据和节点来减少树的高度。另一个相似就是都只有新建一个根节点才增加树的高度。
Trie有一个通用的属性，把给定的key插入到索引中，不论插入顺序，最终的结果都是一样的。

节点的实现

k，节点的物理组织， 节点内的操作

概览

节点内可以直接用binary radix tree，但BiNode之间的的指针会浪费空间，效率低可能导致Cache miss或数据依赖。HOT需要一个节省空间的、快的、紧凑的节点。

The key idea behind our node layout is to linearize a k-constrained trie to a compact bit string that can be searched in parallel using SIMD instructions.

主要思想是把k-约束的trie线性化为一个紧凑的能使用SIMD并行查找的bit String。为此，把区分bits连续存储。

图5a包含7个key，区分bits位是{3,4,6,8,9}。把每个key这5个区分位组成了partial key(dense)。把Partial key连续存储就能用SIMD进行并行查找所有key了而不用再遍历相应的Trie。但是为了插入的简化，事实上节点内用的并不是这个dense partial key，而用的是sparse partial key，下面插入会讲。

最大fanout设为32，对CPU Cache够大，对快速更新够小。一个node最多有31个区分bit positions（足够区分32个key，想想最坏的情况，32bit从第0位到第32位依次为1，其余为0）。为了SIMD操作，Partial key需要对齐。在物理层面上，Partial key有三种存储表示，8-bit, 16-bit和32-bit数组。对每个节点总选最小的。

除了partial key，每个节点还需要存bit positions(存哪些位能用来区分不同的key)。最简单的方法就是存到一个数组中(图5cI，把34689存了起来)，但是比较慢，因为在进行数据并行的key比较前需要从search key中先提取bit positions相应的数据形成comparison key再和Partial key进行比较。

（PEXT指令就是A通过B指定的掩码把A中相应的比特位传输到C的低比特位中）

为了加速key的提取，这里充分利用了BMI2的PEXT指令——通过位掩码从一个integer中提取指定bit(把原始key和位掩码作与操作)。图5.c.II是单掩码，在最大bit Position和最小bit position接近时可以用(小于64)，否则要用图5.c.III，多掩码，用多个8bit掩码来表示，PEXT对它进行快速的并行抽取。
PEXT介绍

到这里，node的layout有两个需要自适应调整的地方，第一是Partial keys，有8bit, 16bit和32bit的数组可选，选择的依据是区分bits的个数(如需要15位bit来区分这32个key，就选择16bit的partial keys;最好的情况是用5bit区分，选8bit partial key；最坏的情况需要31位，选32bit Partial key)；第二是单掩码和多掩码的区别，选择的依据是最小bit position和最大bit position之间的距离，小于64用单掩码，多余64用多掩码。

物理节点的layout

一个节点包含四部分内容，头文件、bit positions、Partial key和value
头文件中包含的信息有子树的高度，描述used entries的位掩码(这是什么)和同步版本的锁

bit Positions部分包含offset和掩码。offset记录的是位掩码开始的地址。

总是用最小的节点。对于一个节点存了n个entries，就分配n个partial keys和n个values，当需要修改节点的时候用copy-on-write。value中存的是指针还是tid，用最高有效位进行区分。

这9种节点的选择总是依赖于discriminative bits的分布，从中选取最小的。一个节点中有n个数据就分配n个partical key和n个value，修改(插入与删除)时用copy-on-right进行节点的替换。除了节省空间外，copy-on-write可以帮助并发。

查找

查找的最后一步得到Tid取到相应的元组后需要与search key进行比较——这是必须的，因为在radix tree上查找可能出现假阳性（它把中间的给删掉了）。

节点的查找分成两步：1.从search key中提取dense partial key 2.与节点的sparse partial key比较。

插入

考虑如果节点内存的是dense partial key，那么在图5中再插入一个新的节点0110101101之后，原来的bit positions就不足够区分这7+1个key了，需要再添加一位bit position，bit position添加后那原来的dense Partial key也全部需要修改，代价非常大。
为了解决以上问题，节点中存的实际上是sparse Partial key。两者的区别是稀疏Partial key是从根BiNode沿着路径只把那些与内部BiNode不同的区分bit设为1，其他都是0.

The difference to dense partial keys is that for sparse partial keys, only those discriminative bits are extracted that correspond to inner BiNodes along the path from the root BiNode and that all other bits are set to 0. Thus, sparse partial key bits set to 0 are intentionally left undefined. In case of a deletion this allows to remove unused discriminative bits.
(还是没有搞懂)

一个新的key如何插入HOT节点中的：在bianry trie中插入前会检查是否已经存在，如果没有匹配，可以确定mismatching bit。与bianry radix tree比，精确的确定mismatching bit是不可能的，因为HOT节点内已经不是显式的bianry radix tree了。但是可以直接确定这个mismatching的子树（也就是HOT节点）中所有的leaf entries并把这些entries标记为受影响的entries。用SIMD指令，把那些具有与search key相同前缀假阳性匹配上的的Partial key标记为受影响(we therefore mark all partial keys that have the same prefix up to the mismatching bit position as the initially matching false positive partial key as affected. )。然后，如果这个节点的bit Positions不包含这个mismatching bit，所有的sparse Partial key都要用PDEP指令记录并创建包含mismatching bit position的的Partial key。
（PDEP与PEXT相反，它是把A的低比特位通过掩码B映射到C相应的位置上）
为了直接构建新的sparse Partial key表示，利用了它与受影响的entries共享了mismatching bit前的的公共前缀。

同步协议

ROWEX
读不阻塞，不重启；写需要保证任何时候数据结构都是合法的

修改操作（插入与删除）分成五步：1) 遍历的时候决定哪些节点需要修改，放到栈里，这些节点称作受影响节点；2) 对受影响的节点自底向上加锁以防止死锁；3) 验证阶段检查有没有受影响节点废弃了，也就是在同时被删除掉了，如果有，该操作需要restart(需要先把之前锁住的节点unlock); 4)如果验证成功，进行插入操作，换成新节点(copy-on-write)，之前的节点标记废弃；5) 自上而下unlock

最重要的是决定哪些节点是受影响节点：一般情况是 包含mismatching BiNode的节点以及其父节点；leaf node pushdown，受影响节点只有包含mismatching BiNode的节点，一旦发生溢出需要遍历其祖先节点把其加入到受影响节点中去，直到1) parent pull up，一个节点有足够的空间或者到了根节点 2) 创建中间节点，到一个节点n满足 height(n.parent)>= height(n)。 最后在最后一个访问的节点上加一个父节点。

删除的时候给节点标记为废弃而不是直接删除，两个好处，一是废弃标记可以让writer检测受影响节点有没有废弃的，然后restart；二是reader与并发的写之间不需要锁，因为写的过程中要把原来的节点标记为废弃但没有删除，reader还是可以读，又不耽误写。

回收策略是epoch-based reclaim，没有reader和writer访问时删除标记为废弃的节点。