索引是实现高效数据访问最重要的技术, 被广泛地用于数据库系统. 现实生活中, 数据库的应用场景各式各样, 不同的应用场景具有不同的数据分布. 传统的索引方法往往针对于某种特定场景进行优化或者对于各种场景都进行了广泛地权衡, 而没有考虑数据的实际分布. 如果知道了数据的确切分布, 现有的索引方法几乎都还可以做更进一步的优化. 2018年, Kraska等人^[1]提出了学习型索引的概念, 探索使用机器学习模型来模拟数据分布, 证明了学习型索引可以通过利用数据分布降低索引内存占用, 并且提高索引在特定分布数据集上的查询性能, 从而为高效的索引设计提供了一种新的研究方向.

但学习型索引最大的问题在于对插入和更新的支持较弱, 这大大限制了学习型索引的使用场景. 学习型索引的插入和更新一直都是一项具有挑战性的工作^{[2, 3]}, 为了支持插入和更新, 有两种常用的方法: 一种是原地更新(in-place)^{[4, 5]}的方式, 给键值数组分配冗余的空间, 当新的数据插入时, 通过键值移动来容纳插入; 另一种是使用单独缓冲区(delta buffer)^{[4, 6, 7]}的方式, 使用一个单独的缓冲区缓冲新的插入, 当缓冲区中的键值达到一定数量时, 再与底层数组合并. 学习型索引通常使用一个较大的排序键值数组存储底层数据, In-place的方式会带来大量的键值移动, Delta Buffer则需要容量较大的缓冲区来均摊合并的代价. 无论是大量的键值移动还是容量较大的缓冲区, 都会带来较大开销, 增加各项操作的延迟. 因此, 降低数据插入更新的成本, 对于学习型索引在数据库中的应用十分迫切.

为了减少索引的内存占用, 同时保持高效稳定的查询性能, 并且降低插入更新的成本, 本文设计了一种基于Radix Tree^[8]的工作负载自适应学习型索引ALERT(a workload-adaptive learned index based on radix tree). ALERT具有两层结构.

● 底层使用一种基于贪心策略的分段算法, 利用数据分布将数据划分为多个不定长分段, 尽可能地减少分段的数量; 段内采用具有最大误差界的线性插值模型学习数据的分布, 用于高效地预测, 保证稳定且有界的段内搜索性能;

● 上层使用Radix Tree来管理底层分段, 因为底层分段的数量相对于原始数据量大大减少, 在数据量较小的情况下, Radix Tree能够较好地支持查询插入等操作. 此外, Radix Tree在键长度较短时十分高效, 与学习型索引所适用的数值类型键长较短的特点相契合.

ALERT使用一种插入缓冲的方式, 避免了插入时的数据移动, 并且尽可能地减少缓冲区中键值数目过多对各项操作的影响. 随着数据的大量插入, 索引的查询性能会受到影响, 因此需要对新插入的数据进行重组优化. 然而, 在缺乏查询工作负载信息的情况下进行数据重组工作具有盲目性. 在现实场景中, 查询工作负载往往具有一定的偏态分布, 某些数据被访问的频率要高于其他数据, 而某些数据很少会被查询涉及. 如果后续的查询不会访问到重组涉及的数据, 那么会带来大量不必要的开销. 因此, ALERT使用两种自适应重组优化方法, 有针对性地对工作负载中点查询和范围查询涉及的热点数据进行重组优化.

本文实现了ALERT的原型, 并进行了大量的实验和比较. 实验表明: ALERT具有较高的构建效率, 也保证了相对高效的点查询和范围查询性能, 并且能够很好地支持插入和更新, 与业界流行的学习型索引相比, 构建时间平均降低了81%, 内存占用平均降低了75%, 在保持了优秀的读性能的同时, 使得插入延迟平均降低了50%; 同时, 通过感知查询工作负载有针对性地进行重组优化, 以较低的代价降低了插入对于索引性能的影响, 改善了索引的性能, 相对于不使用自适应重组优化, 使查询延迟平均降低了15%.

1 相关工作 1.1 传统索引

B树^[9]和B+树^[10]被设计用于加速数据库系统上的搜索. 为了降低存储成本, 提高访问效率, 人们提出了许多变种. B+树在现代处理器上具有良好的缓存行为: 如果将B+树节点的大小与缓存线对齐, 那么节点中的所有数据都会在一条缓存线中被访问. 为了利用这个特性, Rao等人提出了可以高效利用缓存的B+树变体: CSS-tree^[11]和CSB+-tree^[12], 从而提供更快的查询性能. 另一方面, 随着硬件的发展, 现代处理器将多个核心集成于一个芯片中, 并且每个核都配有矢量(SIMD)单元, 另外, GPU, FPGA等异构加速硬件的性能也越来越高. 为了利用现代处理器不断增长的计算能力, FAST^[13]根据架构特性组织排布元素和树的层级结构, 从而利用SIMD指令和GPU来加速查询的性能.

Radix Tree是数据库中另一种常用的索引结构, 可以看作是一种以二进制位为关键字的特殊前缀树. Radix Tree有许多有趣且有用的特性: 查询插入性能只取决于键的长度, 而不取决于数据量; 键值按顺序存储, 从而支持范围查询. 然而, 对于特定数据分布来说, Radix Tree的内部节点会具有许多稀疏分布的分支, 从而造成过多的内存消耗和糟糕的缓存利用率. ART (the adaptive radix tree)^[14]解决了Radix Tree内部节点稀疏的问题. ART的节点的大小与节点中键空间填充的密度成比例, 使用自适应大小的节点来减少稀疏节点造成的内存浪费. 一棵ART可以有4种不同的节点类型, 并根据非空子节点的数量选择节点类型. 为了优化稀疏的区域, ART使用了路径压缩, 通过压缩只有一个子节点的所有内部节点, 可以显著降低树的高度和空间消耗. 因此, ART在数据库系统中具有广泛的应用, 是数据库系统的首选索引结构之一, 包括一些完全成熟的数据库管理系统, 如HyPer^[15]和DuckDB^[16], 也使用了ART.

1.2 学习型索引

学习型索引背后的思想在于: 索引可以看作从查找键到存储位置的近似函数, 从而将索引的构建问题转换为使用机器学习模型来学习数据累积分布的问题. Kraska等人^[1]提出的学习型索引RMI (recursive model index)将数据递归地进行分区, 在一个分区中使用模型学习数据的一个子集, 从而建立一个按阶段组织的具有层次结构的模型, 在每个阶段使用模型的预测结果选择下一阶段的模型, 直到最后一个阶段预测查找键在排序数组中的位置. 为了保证索引能够准确地找到所查询的键值, 需要记录下最后一个阶段中的每个模型对于所有数据的预测位置与其真实位置的最小误差和最大误差, 并使用二分搜索进行修正. RMI利用数据分布加快查询的速度, 降低索引的大小, 但仍存在较多问题: 首先, 构建较为耗时, 并且需要复杂的调优; 其次, 采用自顶向下的构建算法, 盲目地将数据分配给下面的模型, 从而造成了模型的冗余或过载, 并且不具有最差情况下的性能保证; 最后, RMI是静态索引, 缺乏对动态插入更新的支持. RS (radix spline)^[17]是另一种静态学习型索引. RS提出的目的是为了更快地构建学习型索引, 并且保持优秀的索引大小和查询性能. 与RMI不同, RS自底向上构建索引, 这避免了自顶向下构建时给底层模型分配数据的盲目性, 实现了只需遍历一次数据的高效构建. 但RS也有一些缺点, 容易受到数据分布偏移的影响, 当具有离群点时, RS使用的Radix Table会变得很大, 从而大大增加了索引的内存占用.

RMI等静态学习型索引提出后, 后续的研究主要集中在解决学习型索引对插入和更新的动态支持上. 现有动态学习型索引的解决方案大致有两种: 一种是给底层数组的存储节点分配冗余的空间, 用于容纳新的插入, 如ALEX^[6]为叶子节点分配冗余的空间, 将叶子节点配置为Gapped Array^[18], 当新键插入时, 插入的键会直接放到模型预测的位置, 如果该位置被占用, 则通过移动为新键的存入腾出空间; 另一种方法是使用传统索引作为Delta Buffer, 对学习型索引中的新插入的键值进行缓冲, 然后批量合并至学习型索引, 以均摊单次插入的开销, 如Fitting-Tree^[4], ASLM^[6]和Dabble^[7]等. PGM-index^[19]采用的方法有所不同, 静态版本的PGM-index在理论上具有最差情况下的性能保证, 动态版本则基于静态的PGM-index构建. PGM-index应用一种指数级方法^{[20, 21]}, 定义一系列静态PGM-index, 分别建立在大小为2⁰, 2¹, …, 2^b的集合S₀, S₁, …, S_b上, 其中, b=Θ(logn). 每插入一个键key, 查找第1个空的集合S_i, 并在集合S₀∩S₁∩…∩S_b∩{k}上构建一个新的PGMindex, 合并后的新集合包含2ⁱ个键, 作为新的S_i, S_i之前的i个集合被清空. 但动态PGM-index相对于静态版本牺牲了查询性能, 因为需要搜索b个静态的PGM-index.

2 索引设计

ALERT结合Radix Tree和机器学习模型, 目标是在大量减少索引内存占用的同时, 使得整个索引的查询复杂度仍保持在常数级别. 图 1描述了ALERT的整体结构. 索引采用两层结构, 自底向上构建: 下层将数据分段, 划分成多个Segment; 上层的Radix Tree中存储了Segment的最大键和地址, 用于管理这些Segment. 查找分为两步: 首先使用Radix Tree找到查找键key可能所在的Segment, 然后在Segment内进行查找.

下面将分别对索引的两层结构进行详细介绍.

● 下层利用数据的分布将数据划分成多个不定长的Segment. 每个Segment中的数据都训练一个机器学习模型, 通过模型预测数据的位置进行查询, 具有常数的时间复杂度, 而与Segment内的数据量无关. 不定长Segment具有更好的灵活性, 这也是减少总的Segment数量、进而减少索引内存占用的关键. 不同的Segment之间组织为链表结构, 相对有序, 使得范围查询也可以非常高效;

● 上层使用Radix Tree来管理Segment. 假设第i个Segment中的最大键为max_key_i, Segment的地址为seg_i, 则在RadixTree中存储形如〈max_key_i, seg_i〉的一系列键值对. 上层选用Radix Tree有两个原因: 首先, Radix Tree查询插入等操作的时间复杂度只与键长有关, 且Segment中的机器学习模型适用的数值类型键长较短, 从而对下层Segment的管理开销可以保持在较小的常数级别; 其次, 下层Segment的数量相对于原始数据量减少, 只索引Segment的情况下, Radix Tree的大小降低, 从而对缓存更加友好, 具有更高的查询效率.

Radix Tree相关研究较多, 对于Radix Tree的内部节点具有许多稀疏分布的分支的问题, 我们可以利用已有的相关工作给出的解决方案, 如ART, 这里不作过多介绍. 下面重点介绍ALERT下层Segment的模型表示和分段算法, 以及如何结合下层的Segment和上层的Radix Tree, 实现高效的批量加载、点查询和范围查询等操作.

2.1 Segment表示

Segment的设计有两个目标: 利用数据分布实现高效的Segment内部搜索; 减少Segment的数量从而降低索引内存占用. 下面将首先讨论使用何种机器学习模型学习Segment内的数据分布, 然后使用一种基于贪心策略的算法尽可能地减少Segment的数量.

为了将机器学习模型引入Segment的设计之中, 需要解决两个问题.

● 选取什么模型来学习数据的分布. 模型的选取需要兼顾准确率和训练开销, 最近, 一些学习型索引的工作^{[1, 4, 17, 19, 22, 23]}表明: 使用一系列简单的线性模型, 如线性插值, 可以高效地建模数据分布;

● 如何处理模型的误差, 保证有界性. 模型的误差需要通过局部搜索来修正, 而局部搜索的效率取决于误差的大小. 常用的误差衡量准则是均方误差, 但均方误差并不能保证误差界, 可能会导致一个范围很大的局部搜索. 更好的选择是使用最大误差, 保证模型的预测值与真实分布的差值都在一个最大误差界内, 使得局部搜索的距离不会超过最大误差范围, 从而保证索引查找性能在最坏情况下的有界性.

综合以上的讨论, 选择使用满足最大误差界的分段线性插值模型^[24]来建模数据的分布. 下面给出使用满足最大误差的分段线性插值模型建模数据累积分布的形式化定义.

给定一组包含m个不同键的有序集合U={x₁, x₂, …, x_m}, 令A为一个大小为n(n≥m), 有序存储U中键(允许重复)的数组. 对于集合U中的每一个键x_i, 使用p_i=rank(x_i)表示有序数组A中小于x_i的键的数量, 即x_i在数组中的第1个起始位置的下标, 令d_i=(x_i, p_i), 构造训练集D={d₁, d₂, …, d_m}. 定义S[i, j]={d_i, d_i+1, …, d_j}, 给定最大误差界ε, 则目标是在满足最大误差界的前提下, 将D分成尽可能少的k个Segment S[i₁, i₂−1], S[i₂, i₃−1], …, S[i_k, i_k+1−1], 其中, i₁=1, i_k+1−1=m. 任意Segment S[i_j, i_j+1−1], 1≤j≤k中的数据, 都可以用一个线性插值模型f_j(x)=a·x+b来近似, 并且满足最大误差:

$ \left|f_j(x)-p_i\right| \leqslant \varepsilon, i \in\left[i_j, i_{j+1}-1\right] $

(1)

满足上述条件的线性插值模型可以用作对Segment S[i_j, i_j+1−1]的查找, 并且模型的预测误差不超过ε, 从而保证了Segment内查找的最大误差界.

对于每一个Segment, 可以看作一个五元组〈keys, values, slope, pre_segment, next_segment〉, 其中, keys和values是存储数据的键值数组, slope是模型参数, pre_segment指向上一个Segment的指针, next_segment是指向下一个Segment的指针. 键值在数组中从0位置开始有序存放. 由于一个满足最大误差界的线性插值模型f(key)=slope×key便可近似Segment键值数组中数据的累计分布, 因此模型参数只有一个线性插值模型的斜率slope. 通过模型f(key), 可以预测给定键在键值数组中的下标pos, 从而只需在预测值附近[pos−ε, pos+ε]的较小范围内进行局部搜索来修正误差, 从而保证了常量的搜索时间.

2.2 分段划分算法

下面讨论如何在满足线性插值模型最大误差界的前提下, 将数据分成尽可能少的Segment, 从而降低上层Radix Tree的大小和管理开销. 对于这个问题有很多相关研究, 这里使用Liu等人提出的一种称作可行空间窗口(feasible space window, FSW)的线性算法^[25]. FSW具有线性的时间复杂度和常量的空间开销, 其高效性和可行性也已在学习型索引^{[4, 17]}中得到了印证. FSW使用贪心的思想, 在满足数据点误差边界的情况下, 尽可能找到最远处的划分点, 使得每一个Segment尽可能包含更多的数据点, 从而减少Segment的数量. 图 2中, 横坐标为键的大小, 纵坐标为键的存储位置, 不同的键及其存储位置构成了坐标系中若干个不同的点d_i=(x_i, p_i).

下面结合图 2, 示意说明FSW算法的过程: 设最大误差界为ε, 令dh_i=(x_i, p_i+ε), dl_i=(x_i, p_i−ε), 选择数据的第1个点d₁作为起始点, 依次扫描数据, 当第2个点d₂加入时, 由d₁和dh₂的连线u₁表示可行窗口的上界, 由d₁和dl₂的连线l₁表示可行窗口的下界, 二者中间包裹的区域称为可行窗口. 随着新的数据点的加入, 形成的上界u_i或下界l_i在可行窗口内, 则可行窗口也会进行收缩. 如当第3个点d₃加入时, 构造连线u₂和l₂, 此时可行窗口收缩至u₂和l₁之间的区域. 当新加入的数据点d_e落在可行窗口外时, 说明之前加入的点至少存在一个违反最大误差, 此时使用起始点至d_e之前的点构建一个新的Segment, 并将d_e作为新的起始点, 继续构建下一个Segment, 直至扫描完全部数据.

3 索引操作 3.1 批量加载

批量加载操作用于构建或重建索引, ALERT采用自底向上的方式批量加载来构建索引. 批量加载之前, 需要保证要加载的数据是有序的. 首先使用FSW分段算法构建Segment的集合, 将数据划分至不同Segment的键值数组中存储, 然后在每个Segment中保存线性插值模型的参数; 将每个Segment中最大的键和指向Segment的指针构成键值对, 插入到上层Radix Tree中进行管理, 并在下层将Segment组织成链表的形式.

批量加载算法的时间复杂度为O(n), 这得益于FSW分段算法线性的时间复杂度和Radix Tree插入时只与键长有关的常量时间复杂度, 虽然构建过程中需要将数据拷贝至Segment的键值数组中, 但对于每一个元素, 批量加载仍只有常数的均摊开销, 因而批量加载算法具有较高的构建效率.

3.2 点查询

给定一个查找键keymax_key_i, 点查询操作分为两步.

● 第1步, 在Radix Tree中查询key可能所在的Segment. 对于查找键key, 在Radix Tree查找键max_ key_i, 使得max_key_i-1 < key≤max_key_i. max_key_i为key在Radix Tree中第1个大于等于key的键, 对应的Segment即key可能所在的Segment. 需要注意: 在Radix Tree中查询时, 需要将key转换成可比较的二进制字节数组形式, 如无符号长整型的key, 可视为长度为8的字节数组;

● 第2步, 得到查找键key可能所在的Segment之后, 需要在Segment内搜索. 首先使用模型得到查找键的预测位置pred=(key-keys[0])×slope, 然后使用局部搜索修正模型预测的误差. 由于模型的预测位置与真实位置的最大误差不超过ε, 因此只需搜索预测位置附近的范围[pred−ε, pred+ε].

查找键key的可比较二进制字节数组长度为k, 则Radix Tree查询key所在Segment的时间复杂度为O(k). Segment内部搜索的时间复杂度取决于内部键值数组的搜索, 如果使用二分查找, 则是一个只与分段最大误差有关的常量O(logε). 综上, 点查询的时间复杂度为O(k+logε), 具有常量的查询时间.

3.3 范围查询

范围查询分为两步: 第1步类似点查询, 首先在Radix Tree中查询起始键可能所在的Segment, 然后在此Segment中找到第1个不小于起始键的位置; 第2步进行遍历, 从Segment中第1个不小于起始键的位置开始, 直至到大于或者等于终止键. 由于Segment之间在下层组织成了链表形式, 如果当前Segment遍历结束, 那么继续遍历下一个Segment, 直至Segment中的键值落在查询区间之外或者所有Segment都已被遍历.

范围查询的开销由两部分组成: 一部分是查找第1个不小于起始键位置的开销, 此部分与点查询开销相同; 另一部分是遍历数据的开销, 这也是范围查询的主要开销所在, 并且查询的范围越大, 此部分开销占比越大. 由于数据在Segment内部键值数组中连续存储, Segment之间组织成链表结构, 所以只需要从起始位置开始连续访问, 相对于B树和Radix Tree等范围查询时需要递归地遍历叶子节点的方式, 十分高效.

3.4 数据插入

不定长Segment带来了降低内存等好处, 但同时也给插入和更新带来了很大的挑战. 为了支持插入和更新, 有两种常用的方法: 原地更新(in-place)和使用单独缓冲区(delta buffer). In-place通过分配冗余的空间容纳插入, 但会带来大量的键值移动; Delta Buffer的问题是单个缓冲区会具有较多的键值数量, 会降低查询和插入的性能. 针对上面两种方法存在的问题, 本文设计了一种插入缓冲的方式, 有两个目标.

● 尽可能避免插入时数据移动带来的开销;

● 减少缓冲区中键值数目过多对查询插入性能的不利影响.

首先分析使用In-place方式处理键值插入时的场景. 当新插入一个键值key时, 首先查找要插入的Segment, 然后需要在Segment的键值数组中找到第1个不小于key的位置, 准备在此插入, 但此位置已有键值, 这种情况可以视作新插入的键值与原来存在的键值发生了冲突. 借鉴拉链法^[26]解决哈希冲突的思想, 在Segment的键值数组中, 每一个冲突的位置均使用一个缓冲区容纳新的插入. 在任意一个Segment的键值数组seg.keys中, 其pos位置对应缓冲区中的键key, 满足seg.keys[pos−1] < key≤seg.keys[pos]. 缓冲区默认采用链表实现, 以高效地应对频繁插入的场景. 插入缓冲并不维护链表中数据的有序性, 只需将新的键值插入到链表尾部.

这样的缓冲设计符合两个设计目标: 首先, 向缓冲区中插入键值不需要移动现有数据, 避免了键值数组中数据分布的改变, 因此不会降低模型精度, 使得键值数组中的搜索能够保证原有的性能; 其次, 每一个冲突的位置均使用一个缓冲区, 从而将新插入的键值分散存储在不同的缓冲区中, 缓解了单个缓冲区键值过多的开销, 并且也有利于后面更细粒度地感知查询的分布进行重组优化.

结合插入缓冲, ALERT的插入操作十分高效, 查找要插入的Segment时间复杂度为O(k), 在Segment中查找要插入的缓冲区时间复杂度为O(logε), 将键值插入到缓冲区时间复杂度为O(1). 综上, 插入操作总的时间复杂度为O(k+logε), 保持在常数级别, 可以保证索引较高的插入效率.

4 自适应重组优化

随着数据的插入, 缓冲区中的数据不断积累, 导致落在缓冲区的查询效率较低, 因此需要对缓冲区中的数据进行重组优化. 最朴素的重组策略是: 当一个缓冲区中数据过多时, 将这个缓冲区所在Segment的所有缓冲区和键值数组中的数据合并, 通过分段算法重组为若干新的Segment. 这种策略假设查询的访问模式是均匀的, 重组会给对Segment中所有新插入数据的查询带来收益. 然而在现实场景中, 某些数据的访问频率要高于其他数据, 并且在不久的将来更有可能被再次访问, 而某些数据很少被查询涉及. 上述策略在缺乏查询工作负载信息的情况下进行重组优化, 具有盲目性, 如果后续查询不会访问重组涉及的数据, 会带来大量不必要的开销.

为了降低重组优化的开销, 本节提出了两种自适应重组优化方法, 分别为感知点查询和范围查询. 将重组优化视为查询的副作用, 将对缓冲区的重组优化推迟到查询执行时. 图 3展示了结合自适应重组优化的索引插入和查询的流程, 每个Segment均有一个对应的插入缓冲, 插入缓冲被划分为无序区和有序区.

查询和插入首先使用第3.2节中所描述点查询算法的第一步, 在Radix Tree中找到要插入的键对应的Segment. 对于插入, 直接插入到Segment对应缓冲的无序区; 对于查询, 先查找有序区然后查找无序区, 并在查询过程中执行重组优化.

4.1 点查询自适应重组优化

为了在点查询过程中自适应地对缓冲区中的数据进行重组优化, 使用自组织链表^[27]作为缓冲区的实现.自组织链表最常用的自组织规则是MTF (move-to-front)规则, 每当查找到一个节点, 将其移动到链表头部. MTF规则基于最近被访问过的数据将来被访问的概率也更高的思想, 将热点数据移至链表头部, 在数据访问局部性较强的场景下, 比普通链表具有更短的平均访问距离. 但使用MTF规则会导致自组织链表单个操作的代价较高, 对于频繁访问的节点, 可能会在链表头部附近反复移动, 带来了许多不必要的开销.

为了解决上述问题, 设计了一种基于自适应窗口的MTF规则, 降低对于频繁访问节点单个操作的代价.在链表头部维护一个大小为k的窗口, 窗口内维护的数据都是最近访问的前k个数据, 即链表中最可能被频繁访问的前k个节点. 查找时, 如果要查找的节点在窗口中, 那么直接返回, 而不需要移动; 如果不在窗口内, 那么仍需要按照MTF规则将此节点移动至链表头部, 此时, 原来窗口的最后一个节点被移出窗口. 窗口的存在, 避免了对频繁访问节点的移动, 减少了对查找的影响. 另外, 原始的MTF规则可视为窗口为1时的特殊情况.

下面确定窗口的大小k, 即确定最可能被频繁访问节点的个数. 由于工作负载十分复杂多变, 人为很难根据经验设定k值. 因此, 采用基于指数衰减的方式来计算k值, 在线地更新窗口大小以适应工作负载的变化.首先, 设置窗口初始大小为0. 每次插入时, 线性扩张窗口, 将窗口大小加1; 统计每次查找过程中找到目标节点时的访问距离dis, 并使用指数衰减的方式更新窗口大小k_t=α·k_t-1+(1−α)·dis_t, 其中, k_t−1是第t−1次查找后窗口的大小; k_t是第t次查找后窗口的大小; dis_t是第t次查找时的访问距离; α为衰减因子, 一般设置为0.01~0.05^[28], 较高的值会给予最近的查找更多的权重. 假设一个节点在真实分布中的访问概率为p, 可以证明, 指数衰减的估计与真实分布的标准差为$ \sqrt {\alpha (1 - p)/(2 - p)} $^[29]. 使用指数衰减的方式简单高效, 准确率较高, 通过不断关注新的查找, 逐渐减少以往较久时间前查找的影响, 从而自适应查询分布的变化.

结合基于自适应窗口的MTF规则, 自组织链表在查找的同时进行重组优化. 当找到满足的节点时, 使用指数衰减更新窗口大小; 同时, 若访问距离大于窗口大小, 则将此节点移至链表头部. 相对于查找, 插入时首先线性扩张窗口的大小, 然后插入到链表的尾部即可. 综上所述, 通过使用基于自适应窗口MTF规则的自组织链表作为缓冲区的实现, 可以在不影响插入性能的同时, 使得缓冲区在进行点查询的同时重组数据, 从而逐渐自适应点查询的分布, 改善点查询的查询效率.

4.2 范围查询自适应重组优化

自组织链表通过感知点查询进行自适应重组优化, 但并不适用于范围查询, 有两个原因.

● 将满足范围查询条件的节点移动至链表头部会污染窗口, 降低点查询自适应重组优化的效果;

● 范围查询需要访问链表的所有节点, 因此移动节点到链表头部也不能优化范围查询.

为了解决上述问题, 提高范围查询效率, 在点查询自适应重组优化的基础上, 将缓冲区划分为无序区和有序区, 通过感知范围查询, 把无序区中的数据自适应合并至有序区, 在不影响插入性能和点查询自适应重组优化效果的前提下, 改善缓冲区的范围查询性能, 进一步地将范围查询频繁的Segment重新训练, 改善整个Segment中数据的查询性能.

无序区采用上节所述的自组织链表实现, 具有高效的插入性能, 并且可以自适应点查询的分布. 有序区采用B+树实现, 能够较为高效地维护数据的有序性, 在数据量相对不大的情况下, 可以支持高效的范围查询.无序区到有序区中的数据合并视为范围查询的副作用, 在进行范围查询的同时, 利用对无序区中满足查询条件的数据进行排序的时机, 将这些数据转换至有序区中存储, 在不影响无序区中自适应链表窗口的同时, 减少无序区中键值的数量, 减轻无序区中查询的压力, 从而使得整个缓冲区的组织结构逐渐趋于适应当前工作负载, 提升整个缓冲区的查询效率.

缓冲区使用链表和B+树, 相对于键值数组, 具有更多的内存占用, 并且不能够有效地利用数据的分布. 随着插入的进行, Segment的缓冲区中存储的数据越来越多, 这种情况将越来越严重, 因此需要进行重新训练, 将键值数组和缓冲区中的数据合并, 使用分段算法将这些数据存储在若干个新Segment的键值数组中, 从而降低索引的内存占用, 提升后续查询的效率.

重新训练的开销来自于两个方面: 一个是合并时排序的开销, 另一个是分段算法的开销. 为了减少重新训练对索引的负面影响, 需要确定重新训练的时机.

合并缓冲区和键值数组中的数据时, 需要对缓冲区无序区中的数据进行排序. 为了减少此部分开销, 需要尽可能地减少缓冲区中无序区数据的数量. 因此, 重新训练需要满足的第1个条件为

$ \frac{{\sum\nolimits_{i = 0}^{seg.size} {seg.buffer[i].ordered{{\_}}buffer.size} }}{{\sum\nolimits_{i = 0}^{seg.size} {seg.buffer[i].size} }} > threshold $

(2)

即: 在一个Segment缓冲区中有序区存储的键值总数达到缓冲区中所有键值总数的一定比例时, 才考虑进行重新训练, 从而减小对无序数据排序的开销. 另外, 由于范围查询是将无序区中数据合并至有序区的唯一途径, 缓冲区中有序区键值数目较多, 说明了对此Segment的范围查询较为频繁, 而重新训练可以大大改善范围查询的效率, 由此证明了此Segment具有足够重新训练的必要.

分段算法具有线性的开销, 但重新训练需要涉及较多的数据, 因此, 重新训练需要满足的第2个条件为缓冲区中的键值总数目达到所在Segment中键值总数目的一定比例, 使得每个键值可以均摊重新训练的开销.

5 实验评估

本文对ALERT进行了详细的实验, 并与传统索引B+树和ART, 以及学习型索引PGM-index和ALEX, 在真实数据集和合成数据集上进行了大量的对比. 所有实验都在一台使用64位Ubuntu16.04操作系统、内核版本为4.4.0-131-generic的服务器上进行, 内存为64 GB, 使用型号为Intel(R) Xeon(R) Silver 4114 CPU@ 2.20 GHz的处理器. ALERT使用C++实现, 上层的Radix Tree采用ART. 实验过程中, 将ALERT和PGM-index的分段最大误差设为32, ALEX的最大节点大小设置为1 MB, 其余索引均采用默认设置.

实验中使用4个数据集, 包括2个真实数据集face^[30], osmc^[31]和2个合成数据集normal, uniform, 这些数据集在现有学习型索引的研究工作中被广泛使用. face是Facebook网站上的用户ID, osmc是公开地图OpenStreetMap上的Cell ID, normal是从参数为(0, 2)的正态分布中采样生成, uniform是一系列连续的无符号整数. 每个数据集均包含2亿个64位的无符号整数. 将每一个无符号整数视为一个键, 然后为每一个键随机生成一个8字节的值, 从而构成实验中所需要的键值对数据集. 对于一个给定的数据集, 首先批量加载2亿键值初始化索引, 然后执行1千万次查询或插入操作, 然后报告操作的平均延迟.

5.1 构建性能

使用2亿有序键值批量加载索引, 观察索引的构建性能. 图 4展示了6种不同索引分别在4个数据集上的批量加载时间, 时间越短, 说明构建性能越好. ALERT具有较高的构建效率, 达到了与B+树相近的速度. 在4个数据集上, 与ART相比, 构建时间平均降低了73%; 与静态学习型索引PGM相比, 构建时间平均降低了64%; 与动态学习型索引DPGM和ALEX相比, 构建时间平均降低了81%. 这得益于索引使用的FSW分段算法只需遍历一次数据, 具有线性的构建时间. 理论上, PGM-index的分段算法也具有线性的时间复杂度, 但其常数系数要高于ALERT. ART在构建过程中需要动态地扩张内部节点, 在大量数据下, 构建性能会急剧下降. 虽然ALERT上层也采用ART, 但因为只需要索引Segment, 数据量大大减少, 降低了上层索引耗费的开销.由于ALEX需要在批量加载过程中递归地构建模型, 其耗时远远高于其他5个索引. 另外可以发现, ALERT和ALEX在分布较为简单的合成数据集上比在复杂的真实数据集上构建时间更短. 这也说明了学习型索引对于分布较为简单的数据构建性能更加高效, 而复杂的分布则会影响学习型索引的构建性能.

5.2 索引大小

批量加载2亿键值之后, 比较每个索引大小. 索引大小使用内存占用来衡量, 各个索引大小的计算方式如下: B+树只在叶子节点中存储键值数据, 因此索引大小为所有内部节点之和; ART的索引大小为所有节点之和减去所有键值的大小, 因为键值被编码进了节点; PGM的索引大小为所有节点的总大小减去所有键值的大小; ALEX的索引大小为索引使用的所有模型和元数据的大小总和; ALERT的大小为上层Radix Tree的大小加上下层Segment的大小再减去所有键值的大小. 图 5展示了6种不同索引在4个数据集上的索引大小. 在4个数据集上, ALERT相对于传统索引, 减少了内存占用, 尤其在合成数据集normal和uniform上的大小几乎可以忽略不计, 即使在分布较为复杂的真实数据集face和osmc上, 相对于B+树, 也分别降低了54.2%和73.3%, 相对于ART分别降低了95.8%和97.5%. 这也说明了学习型索引利用数据分布减少内存占用的优势.

传统索引的内存占用要远大于学习型索引, 尤其是ART, 虽然通过自适应节点相对于普通Radix Tree取得了较大改进, 但仍具有相当大的内存占用. Leis等人^[11]也指出, ART平均使用8−52字节来存储每一个键, 这也与实验结果相符. 与学习型索引DPGM和ALEX相比, ALERT的内存占用平均降低了75%. 虽然PGM具有更少的内存占用, 但其动态版本DPGM则需要更多的内存; ALEX使用了Gapped Array作为节点的实现, 具有冗余的空间, 所以也具有相对较大的内存占用.

5.3 查询性能

查询操作包括点查询和范围查询, 二者的性能分别使用一批查询操作的平均延迟来衡量. 查询操作的选取满足一定的分布, 查找键的选取使用Zipfian分布, 从而关注某些热点记录; 范围查询要扫描键的数量使用均匀分布, 从0−100的范围内随机选择. 在批量加载构建好的索引上分别执行1千万次点查询和1千万次范围查询操作, 观察6种不同索引在4个数据集上两种查询操作的平均延迟. 下面分别对ALERT的点查询性能和范围查询性能进行讨论.

点查询的实验结果如图 6所示, 在normal和uniform数据集上, 学习型索引可以很好地学习数据的分布, 相对于B+树和ART, ALERT将延迟最大分别降低了78.1%和39.3%. 即使在分布十分复杂的face和osmc数据集上, ALERT也达到了与B+树相近的性能. 在学习型索引之中, ALERT的点查询性能相对于动态学习型索引DPGM和ALEX在4个数据集上均具有优势, 但差于静态学习型索引PGM. 这是因为PGM通过递归地构建线性分段模型, 可以很好地学习数据中非线性的分布; 而动态学习型索引, 为了性能往往采用简单的模型和更为复杂的数据结构, 因此相对于静态学习型索引牺牲了一定的查询性能.

范围查询的实验结果如图 7所示, ALERT在4个数据集上均取得了优异的范围查询性能, 尤其在normal和uniform上表现最优.

与点查询不同, 范围查询的性能主要取决于查询的范围, B+树、PGM和ALERT使用数组存储键值, 当找到第1个满足查询条件的键值之后, 只需连续地访问下层的键值数组, 因此范围查询的性能较好. DPGM由于将键值分散存储于多个静态PGM-index之中, 访问时需要遍历多个静态PGM-index并合并结果, 因此相对于PGM, 性能大大降低. ALEX将键值存储于Gapped Array, 访问时需要跳过间隙, 也影响了性能. ART范围查询时需要递归遍历叶子节点, 因此性能最差. ALERT在4个数据集上的范围查询延迟相对于ART, DPGM和ALEX最大分别降低了47.5%, 54.9%和36.4%. 可以预见: 随着查询范围的增大, ALERT可以连续访问下层键值数组带来的优势, 将使得这种差距越来越大.

5.4 插入性能

在批量加载构建好的索引上运行执行1千万次插入操作, 插入操作使用均匀分布从数据集中选取. 因为静态索引PGM不支持插入, 因此观察剩余5种不同索引在4个数据集上插入操作的平均延迟. 实验结果如图 8所示: ALERT达到了与传统索引B+树和ART相近的性能, 在normal和uniform数据集上, 甚至优于传统索引. 与学习型索引相比, ALERT在4个数据集上的插入延迟相对于DPGM和ALEX平均降低了50%. 这是由于ALEX需要进行节点内数据的移动甚至节点的分裂和递归插入, DPGM则需要对若干个已满的静态PGM进行合并和重新训练, 均具有较大的开销. 而ALERT只需找到对应的缓冲区, 将键值追加到缓冲区的无序区中, 通过将维护索引中数据有序和重新训练等重组工作视为查询的副作用, 推迟执行, 保证了较高的插入效率.

5.5 分段最大误差的影响

分段最大误差影响ALERT中分段的一个重要参数, 它影响了索引占用内存的大小和查询的延迟. 设置不同的分段最大误差大小, 在face数据集上使用2亿个数据构建索引, 并进行1千万次点查询操作, 观察不同分段最大误差下索引的表现情况.

图 9展示了不同分段最大误差下的查询延迟以及索引大小.

增大分段最大误差可以减少Segment数量, 使得索引具有更小的上层Radix Tree, 从而也降低了索引的内存占用. 点查询操作延迟的总时间分为两部分: 一部分是在Radix Tree中搜索Segment的时间, 另一部分是Segment内进行搜索修正模型误差的时间. 随着分段最大误差大小的增加, 搜索Segment的时间占总时间的比例越来越小. 这是因为较小的Radix Tree更容易被缓存, 具有更高的搜索效率. 但与此同时, 由于Segment内局部搜索的范围与分段最大误差的大小有关, 增大分段最大误差会使得此部分开销越来越大, 从而造成了点查询操作延迟总时间上的增长.

下面给分段最大误差的设置提供一些指导准则, 较大的分段最大误差使索引具有更低的内存占用, 但会对查询性能造成损耗. 也就是说, 牺牲一定的查询性能可以换取更低的内存占用. 例如, 将分段最大误差大小由2调至16, 仅增大了的4.3%查询延迟, 却可以带来84.7%的索引占用内存大小的降低. 根据这个准则, 可以很方便地通过调节分段最大误差的大小对索引的内存占用和查询延迟三者进行权衡. 但需要注意的是, 分段最大误差大小的设置并不是越大越好. 从图 9可以看到: 此场景下, 当分段最大误差超过128时, 索引的内存占用大小基本不再降低, 而查询延迟却在增长. 因此, 可以将分段最大误差的大小设置在16−128之间.

5.6 自适应重组优化效果

为了观察缓冲区点查询和范围查询自适应重组优化的效果, 首先对包含2亿数据的face数据集进行下采样, 得到2百万数据; 然后批量加载这2百万数据构建索引, 并将剩余数据随机插入, 构造缓冲区中具有大量新插入键值的场景. 接下来, 分200个批次分别进行1千万次点查询和1千万次范围查询, 观察各批次查询之间平均延迟的变化趋势. 查询的键值使用Zipfian分布从新插入的数据中选取, 从而使得查询都落在缓冲区中, 范围查询的范围从0−1000随机选取. 下面分别对点查询和范围查询自适应重组优化的效果进行分析.

图 10(a)展示了分别使用自组织链表和普通链表时, 点查询平均延迟的变化趋势. 起初, 二者都具有较高的延迟, 这是由于正在预热操作系统缓存. 从第2个批次开始, 使用普通链表方案的查询延迟逐渐趋向平稳, 并在900 ns左右震荡; 而使用自组织链表的方案通过自适应查询的分布, 延迟逐渐降低. 在第4个批次之后, 使用自组织链表方案的查询延迟开始低于使用普通链表的方案. 第180个批次之后, 自组织链表的自适应窗口逐渐趋于稳定, 查询延迟稳定在770 ns附近, 相较于普通链表方案, 降低了约14.4%的延迟. 两种方案的查询延迟在140−160批次均出现波动, 这可能是由于不同批次查询分布的变化, 导致索引查询过程中出现缓存失效造成的.

图 10(b)展示了使用自适应合并和不使用自适应合并的情况下, 范围查询平均延迟的趋势变化. 起初, 范围查询需要将无序区中满足查询范围的数据合并至有序区, 从而具有较大的延迟. 但随着缓冲区中数据的不断重组和合并, 从第50个批次开始, 使用自适应合并方案的延迟开始低于不使用自适应合并的方案. 最终, 从第110个批次开始稳定在6 050 ns附近. 而不使用自适应合并方案的延迟则一直在7 150附近波动, 相较于不使用自适应合并的方案, 使用自适应合并的方案降低了15.4%的延迟. 不使用自适应合并的方案始终需要遍历所涉及无序区中的所有数据, 而使用自适应合并的方案仅需要在第1次遍历无序区时, 将范围查询涉及合并至有序区, 这是使用自适应合并方案稳定后优于不使用自适应合并的关键所在. 此外, 自适应合并只需对查询涉及的数据进行重组, 具有较低的开销. 可以看到: 在自适应合并的过程中, 查询的延迟呈现指数式降低, 说明了自适应合并具有较快的收敛速度, 可以很快自适应查询的分布.

6 总结与展望

本文设计了一种基于Radix Tree的工作负载自适应学习型索引ALERT, 旨在利用数据的分布减少索引的内存占用, 保证相对高效的查询性能. 通过使用一种高效的插入缓冲, 降低数据插入更新的成本, 解决学习型索引插入更新支持较弱的问题. 同时, 使用两种自适应重组优化方法, 通过感知点查询和范围查询的分布, 自适应工作负载, 以较低的代价降低了插入对于索引性能的影响. 但本文工作仍存在以下不足之处: ALERT目前只支持单线程下的查询和插入更新, 为ALERT提供并发支持具有重要意义; 目前, 学习型索引支持的键类型受限于定长的数值类型, 如何支持索引不定长的字符串类型, 也是未来考虑优化的一个方向.