《Hyperion: building the largest in-memory search tree》

目标

更高的内存效率。
ART和HOT都是固定的数据结构，尽可能地利用SIMD并行计算来提高效率(为此最重要的是对齐alignment，固定的规整的数据结构)。但Hyperion完全放弃了这个做法，用的是顺序存储，线性查找。并在插入删除移动数据保持数据的紧凑以追求更高的空间效率。

怎么实现的

主要树的数据结构，容器与节点的物理布局，操作，内存管理器几个方面来分析

1. 容器

Hyperion是一个span为16的trie树(65536-ary)。Hyperion中一个特殊的定义——容器。把节点存在容器中，最简单的容器包含16bit的Partial key，这16bit又是两个8bit的两个节点TNode和SNode。同时，容器是允许嵌套的，也就是图2b中的(aet)这个容器嵌套到了它的父节点h所在的容器。容器越大，查找与更新越复杂，所以大的容器会从其父容器内弹出。所以如何弹出呢？
为了极致的内存效率，容器是以32byte增长的，这样会造成大量的内存碎片导致内存效率低，为此，设计了一个内存管理器，那么内存管理器是如何工作的呢?

2. 数据结构与布局

节点组成容器，一个基本容器包含16bit Partial key，也就是说如果这16bit都是中间节点的话，最多有2¹⁶个孩子节点。

2.1 容器的布局

4byte的头文件，19bit表示该容器的大小，8bit 未使用的字节数，3bit的跳表标志J(用于遍历时跳过TNode，容器跳表如何工作?) ，S是容器拆分标志。
容器初始化为32byte，除去头文件，有效荷载为28byte。当容器空间不足请求分配新的空间也是以32字节增长。

2.2 TNode和SNode的布局

k表示它是TNode还是SNode，t表示节点类型，01表示内部节点， 10,11表示叶子节点(区别在于有无value)，00是非法节点。d表示delta encoding增量编码(用与稠密数据，如果当前节点与其兄弟节点很近，如a和b，那么可以在d存一个001，这样b就不用存了节省空间)。js是跳转标志(如果孩子很多，想要跳转到下一个Tnode)，jt是跳表标志(是SNode的跳表，加速其Snode的访问)。c是孩子容器标志，c=00表示不存在子容器，因此该节点是叶子节点，01表示存在子容器指针HP。10表示嵌入子容器。如图7的一个SNode h所示。

h有子容器，所以在它的后面加上一个5byte的指针。(图7a这是父子容器分离的情况)

图7b是子容器嵌入父容器的情况。嵌入的情况子容器就直接写在其父节点SNode的后面。h把c设为10表示存在嵌入子容器。嵌入子容器的头文件只有1byte，只存它整体的大小(包含头文件本身)，也就是说，嵌入子容器最大就是256byte。(文中说是Snode最大是256byte)。

嵌入容器太大不能存在父SNode中，必须弹出。弹出步骤：嵌入容器弹出，分配新容器的内存(由指针HP引用)，初始化一个空的容器；嵌入容器的有效荷载拷贝到新容器，然后更新这个新容器的头文件(大小，空余空间)
嵌入容器弹出后，更新就容器。存引用新容器的指针，把子容器标志设为c=01。原来嵌入容器空下来的内存呢？把接下来的字节数据移动，把空的内存放在容器最后，最后更新容器的free属性。如果空的太多会回收以保证未使用的空闲内存总是很小。 容器是可以循环嵌套的。

子容器标志c=11表示子节点是路径压缩节点PC node.一个PC有1byte的头文件，7bit表示大小，1bit表示是不是有值，从而把PC大小限制在127个字符。有值的话直接加在头文件后面。如果新的key的加入导致PC需要划分，递归的转化为嵌入孩子直到两个Partial key能够存到两个独立的PC。

3 操作

查找与删除就是在Trie上的前序遍历。到下一个TNode/SNode的偏移量是根据图5中的标志(js, jt,容器跳表之类的，下节)和嵌入子容器或压缩路径节点的大小来算的。插入是保序的，这就需要移动字节数组，如图8所示。兄弟节点保序可以尽早检测到缺的key，范围查询也更快。

更新与删除 和插入查找的复杂度一样。删除几乎都会造成内存唯一。更新只会在key没有相应的值的时候会产生内存位移。(节点类型10和11)

有序的范围查询用的是回调函数(什么是回调函数)

4 内存管理

ART, HOT为了alignment，为了SIMD，都有过度分配。如ART的Node48可能只存了17个。这些布局可以很简单的计算偏移量从而能够高效的并行计算。

精确分配(exact-fit)的性能严重受到内存充分配的影响。精确分配的内存要么在堆上分配，要么通过匿名内存映射MMAP。堆分配快，但是频繁的重分配会产生过度的碎片；而mmap会产生kernal trap 什么是kernal trap

内存管理器tcmalloc和jemalloc都试图减少碎片化的影响，通过支持指定大小的分配或合并未使用的段。但是tcmolloc旨在提高性能，并且不向操作系统释放内存；jemolloc主要强调扩展性的并发支持。

自制的内存管理器把2016byte以下的小内存分配在内存映射段上，更大的存在堆中。

内存管理器用了一个层次数据结构来高效的分配和释放段。如图9.
SB₀处理2016byte以上的内存请求，SB_i复杂处理32byte*i的内存请求。最后的chunk用来存一个容器。所以每个Superbin可以存2¹⁴×2⁸×2¹²个容器。
不像一般的8byte指针，这里的Hyperion指针是5byte，包含了各层次的id。整个trie只存HP。用HP把整个trie从虚拟内存中分离开来了，这可以使内存管理器可以按照自己的意愿来重新组织和移动chunk。

superbin开销很小，可以放到一个cache line中。superbin的数据结构包含了一个metabin指针数组的引用，以便可以单独初始化新metabin。另外superbin还包含16个未满的metabin的id的有序链表，以便快速找到空闲chunk。metabin除了存housekeeping变量外，还有256bit的数组来知道它下面哪些bin是不满的和bin数组。bin用4096bit区分哪些chunk是空的。每个bin 512字节大，所以一个metabin是133416byte。

对分配器需要存内部分配的大小，每个段8byte。而kernal不追踪每个映射段多大，这里用superbin的id定义了chunk的大小。与堆相比，每次分配节省11byte(怎么节省的原先的指针8byte，记录段的大小8byte，现在只需要指针5byte，不需要记录段的大小)。一旦分配了1048576个chunk中的12128个，省下的开销已经补偿了metabin的数据结构开销。每个满的metabin会省10MiB。

Extended Bins用来分配大于2016byte的内存，有SB₀管理。Extended Bins大小16byte，只存extended Hyperion Pointer(eHP)，其中有一个常规指针(8byte)，一个整形Interger记录请求存储的大小(4byte)，一个short型记录本次分配中多分配的内存(2byte)，剩下2byte存housekeeping flat。尽管trie是以32byte扩张的，但eHP不是，请求8KiB时以256byte扩张，请求8KiB，以1Kib扩张，更大时以4KiB扩张。用来减少对内存的分配次数，减少碎片。

Chained Extended Bins(CEB)是8个extended bin chunks进行原子的分配和释放。这意味着一个HP有8个extended bin chunks， 必须位于SB₀中一个bin中8个连续块中。一些扩展容器的堆指针可能是空的。这个概念允许我们访问8个独立的扩展bin块，而不必在trie中处理多个HP。

Arenas：每个trie都要一个固定的根节点，简化了前缀树的并行。那么就不用单个的256-ary的trie，可以创建256个trie(根据key)。对一个key进行操作的时候，首先把它映射到某个trie T_i上。

Arenas enable thread-safe concurrent access using one memory manager per arena. Every arena therefore has its own set of superbins and controls access using a spin lock. The individual tries T_i are mapped to a set of arenas A_j in a simple round-robin fashion: T_i → A_{i mod j}.

Arenas使得每个trie都有自己的superbins集合，也就是说每个trie都有自己的内存管理器，并由它保证线程安全的并发访问。并发访问控制使用自旋锁实现的。Trie T_i与Arenas A_j之间的映射是通过一个简单的round-robin函数。

偏斜分布会限制Arenas的效益。

5 一些优化

5.1 Delta Encoding 增量编码 d

如C3中 a和e是兄弟节点，a是97，e是101，那么这里e就可以不用存了，可以只存一个101-97=4，存在增量编码标志d中。这对于密集的数据是很有效的。

5.1 跳转后继 js

线性扫描容器中一个度为k的两层的trie比较的次数是O(k²)。当trie很大时，允许从一个TNode跳转到下一个TNode，来减少比较到最多O(2k)。用一个标志位js来表示这个TNode后面有没有跟一个跳转引用(记录下一个兄弟节点的偏移量，16bit)。最大的跳转距离就是65535byte，最大的SNode是256byte。
这其实就是用空间换效率，只有孩子>=2时用。这是因为如果只有一个孩子，很可能这个孩子就在cache line里，顺着扫描过去比花2byte跳转过去代价更低。
跳转后继js的一个缺点就是，这个TNode下面的插入与删除都需要对js进行更改。并发问题？

5.2 跳表

想想一个TNode下，最多有256个SNode孩子节点，总是线性扫描过去工作量还是相当大的。于是引入的跳表来加速访问。对于一个容器来说也是同理。TNode的jt标志和容器的J标志表示有没有存在跳表。

上面的js是从一个TNode跳到下一个TNode，但对于最多有256个孩子SNode的TNode来说，光是访问它自己的孩子工作量也是很大的。并且随着孩子的增多，硬件预取也跟不上了，导致增加了cache miss。由于增量编码的关系，有可能用了跳表只知道一个SNode的增量编码不知道它的前一个兄弟节点的target key导致自己的key也不知道了。解决这个问题两种方法：事先得知道target key，可以把target key存在跳表里；跳到预先定义的节点。这里用的第二种方法。
TNode跳表用15个无符号short表示它的15个SNode。
一个TNode跳表有15个entries e_i，0-14， e_i表示第16*(i+1)个SNode。这个映射就使得存目的地key和跳转偏移量就不必要了。一个key k_i的跳表entry可以由bit shift来决定JT(k_i)=(k_i>>4)-1。如果key消失了，需要创建额外的destination points.怎么实现的没有看懂

容器跳表要跳的是TNode。容器的跳表标志J有3bit，允许在3个entry间隔中存至多49个entry。也就是说对于任意一个TNode，最多只用遍历256/49=6个TNode。一旦容器跳表完全扩展并且entry适当平衡，跳表就不用更新了。检查跳表状态的指令是不必要的，这一点特别重要，因为这些指令会把分支指令添加到扫描算法的关键路径上。
每个entry编码成32bit的integer，8bit表示这个key，24bit存偏移量。entry是根据key排序的，偶尔更新。

5.3 容器拆分

垂直拆分容器。考虑一个容器中有65536个子容器，这个容器超过400KiB大。容器大的时候，再字节移位(插入，删除)和重新分配的开销就非常大了。拆分容器可以减少这个开销。

一个容器最多能分成8chunks，chunk_i管理[32 · i, (32 · (i + 1)) − 1],i ∈ [0, 7] 的TNode。如chunk₃管[96,127] TNode。每次迭代容器分一次。

图11展示了容器X的垂直切割。切割旨在重平衡新创建的容器。新创建的容器X1包含了key范围[0,159], X2包含key范围[160,255]。

拆分容器会产生两个新创建的容器，每个容器有自己的扩展bin指针(eHP)。链式指针3.2节用来存eHP，可能存在8个分裂容器。分裂的容器分配在连续的chunks上，图11的红色部分。尽管容器X1最小的可以是57，但X1还是负责范围[0,159],因此X1的eHP定位在第一个chained chunk。X2的eHP索引是5，因为最小的可能TNode key是160(160/32=5)。

扫描算法用内管管理器API把HP转化成虚拟内存地址。对于链式指针，加一个请求TNode key。假设下一个要找的partial key是110，在容器X1里。X1的父容器只存了一个HP指向链式指针。需要 用110来决定返回哪一个分裂容器的地址。110/32=3，chunk3是第一个检查的，321都是空的，返回容器地址索引0。

链式指针促进了多个孩子相连无需存储多个link。

哪些容器需要分裂：每次插入对容器进行扫描的时候都要检查 size_c >= a+b*s。
size_c是容器大小， a=16KiB, b=64KiB, 分裂延迟 s ∈ [0, 3]。分裂延迟2bit，S标志，图3，初始化为0。
通过检查，拆分也可能中止。...

5.4key预处理

对key进行转化使其更适合数据结构。在索引最小化的key预处理已经有了广泛的研究。

Oracle的 reverse key index是一种在线的key 预处理启发式算法，不需要提前了解数据，反转key的字节顺序，并用单调递增的元素用于平衡索引。

key的预处理就是一个内射函数f，把一个输入key k∈K₁转化为一个输出key k^'∈K₂。这种内射需要维持CRUD(增删改查)的一致性，但是对于范围查询，f必须是可逆的，并且在键间保持二进制可比。

Hyperion提供了一种可选的key预处理，专门为均匀分布的key（如随机整数和哈希加密）。通过注入8个零bit减少key前四个字节编码的熵。通过向key的第二第三第四字节注入两个0位，第三级容器的总数从2³²下降到了2²⁶。更少更大的容器可以大大提升内存效率。零bit注入是一个内射的可逆的二进制保序的函数。

把0位注入相应字节的两个有效最低位，可以保持高效的增量编码和部分键值均匀分布。

测试

数据集，integer和String都分为连续的和随机的。
Integer随机的是SIMD-oriented Fast Mersenne Twister生成的
变长String用的是Google Books n-gram corpus测试的。

测试包含插入、查找和范围查询。
Hyperion和除了ART和HOT的数据结构都与k/v存储类似，key和value都存在数据结构中。ART和HOT用的是指针

对于整数键，Hyperion的嵌入式容器的阈值设置为8 KiB，这意味着如果父容器的增长超过8192字节，则会弹出一个嵌入的子容器。对于大小可变的键，例如字母数字字符串，阈值被设置为16kib以更好地利用路径压缩。当嵌入式容器的大小超过256字节的限制时，它就会被弹出。

字符串数据集上，分为n-gram的字典排序字符串和随机的n-gram字符串