近年来, 伴随着移动互联网和大数据的热潮, 行业对数据处理能力, 尤其是在线联机事务处理能力(OLTP)提出了更高的要求.一个比较典型的案例是在2019年的“双十一”, 阿里巴巴当天创下了6100万次/s处理峰值的纪录(https://developer.aliyun.com/article/727517).如此巨大的数据处理能力, 与阿里自研数据库OceanBase^[1]息息相关的.在摩尔定律的作用下, 计算机硬件(多核、大内存、固态硬盘等)的性能一直在快速发展, 这很大程度上促进了数据库得以支撑类似“双十一”这种高吞吐率的应用.典型地, 计算机处理器的性能从单方面提高频率转向增加核心数的方向转变.为了适配新硬件的特性及最大限度地发挥硬件的性能, 数据库领域很多模块都要针对性地进行适配.索引技术作为数据库存储层的核心, 同样需要提出适配.跳表(Skiplist^[2])是数据库领域的一个重要索引技术, 它具有结构简单、易于实现、无锁并发、O(log(n))的查找复杂度等优点, 因此在LevelDB, MemSQL, Redis等数据库中都有广泛应用.

跳表是基于线性链表改进而来的.传统的链表中, 每个结点只包含一个结点指针域, 而跳表的每个基础结点包含多个指针域.图 1是理想情况下的跳表示意图, 水平方向来看, 每一层都是单向链表, 而且越往上的层级, 结点越稀疏, 跳表通过维护每个结点的层数, 保证每层结点个数都比下一层大致减半.跳表的查找操作是从最上层结点依次往下缩小查找区间, 过程类似于折半查找.对于跳表的插入操作, 先根据待插入key查找到待插入的位置, 然后算法通过随机算法确定结点的层数, 再插入结点.假设结点key的层数为3, 则维护下三层链表的指针.第1.1节将对跳表做详细介绍.

但我们认为, 跳表不是一个稳定的数据结构.计算机科学中, 经典的不稳定的数据结构是二叉查找树.二叉树的特性只需要保证左小右大的特质, 一旦数据从小到大依次插入二叉树, 二叉树便退化为线性表, 此时的查找复杂度也从O(log(n))退化到O(n).因此提出了平衡二叉树, 通过左旋和右旋操作, 改进了二叉树的稳定性.

跳表结构的查找时间是通过多层链表指针域达到加速的效果.但跳表的层数随机算法导致它不是一个稳定的结构, 具体来说, 包含以下两点挑战.

●数据偏斜.跳表的优点在于可以达到类似折半查找的复杂度O(log(n)), 但是跳表的层数是通过随机算法生成的, 这会导致性能的不稳定.在极端情况下, 会生成类似于图 2的跳表结构, 此时的查找复杂度等价于链表的查找复杂度(都是O(n)), 跳表的优点便不复存在了.这主要是因为跳表的随机生成层数的算法并没有结合数据特征去生成跳表结构.我们认为, 一个稳定的跳表结构应该充分考虑数据的分布特征, 在插入key的同时, 根据分布特征去决定层数, 而不是随机生成;

●热度数据.我们发现, 跳表的查找过程中, 结点层数越大的结点被访问的概率越高.比如图 1中, 查找结点8, 直接在第1层便找到了, 便不需要继续一直下沉操作了.这促使我们可以充分考虑热度数据的特征, 让热度数据的层数尽可能高, 访问效率便更快一些.

本文的贡献如下:

●基于数据分布估计的跳表结构.本文基于核密度估计的方式去估计数据集合的累积分布函数, 进一步预测数据在跳表中的位置和结点层数, 从而达到跳表查找性能的优化目的;

●基于冷热数据分层的跳表结构.本文针对历史数据的访问频次信息, 设计了一种冷热分层的跳表算法, 对频繁访问的热度数据保证尽可能的在跳表的上层, 而访问较少的冷数据在跳表的下层, 从而保证热度数据访问加速的效果;

●跳表选型.本文基于合成数据和真实数据对标准跳表和5种改进的跳表算法进行了全面的实验评估并开源代码.实验结果表明, 优化的跳表最高可以获取60%的性能提升.

本文第1节对跳表和密度估计进行全面的介绍.第2节对相关工作进行总结.第3节根据数据分布特征进行跳表算法的优化设计.第4节根据热度数据特征对跳表进行优化算法设计.第5节通过合成和真实数据集对上述算法进行实验验证.第6节对全文进行总结, 并提出对未来工作的设想.

1 预备知识

本节将完整介绍跳表的概念和基本操作, 然后讨论标准跳表算法所遇到的问题.

1.1 跳表

跳表从结构上可以看成多层链表结构.它的结点结构和链表的结点结构很相似, 不同的是, 链表结点除了数据域之外只包含一个next指针域, 而跳表结点包含多个指针域.每个结点所包含的指针个数(层数)是可变的.跳表结点一旦被创建, 指针个数便确定.多个指针域按照“层”的方式, 维护多个单向链表.通过随机函数(几何分布)控制每个结点的指针个数(层数), 从而保证每一层的“链表”个数依次减半.因此, 跳表是一种随机性算法.

算法1阐述了标准跳表中的随机生成层数的算法.原理相当于做一次抛硬币的(伯努利实验)实验, 统计首次抛出反面的次数.如果遇到正面继续抛, 遇到反面则停止, 用实验中抛硬币的次数K作为结点的层数.显然, 随机变量K服从参数p=1/2的几何分布.K的期望值E[K]=1/p=2.也就是说, 跳表中元素的平均层数为2层, 包含N个元素的跳表的指针域个数大致为2n个.

算法1.基于伯努利实验的跳表层数决策算法.

输入:跳表最大层数maxlevel;

输出:待插入key的层数.

1: Function random_level(maxlevel)

2: level=1;

3:   While (random(0, 1) < 0.5)

4:    level++;

5: Return min(level, maxlevel);

数据库索引一般需要提供3种访问操作:查找、插入、删除.跳表的查找操作是从最上层开始查找, 依次按照范围往下查找, 直到最下面一层为止.如图 3所示, 假设我们要查找结点7.首先, 我们从最上第4层开始找到结点1, 然后下沉到第3层, 依次查找到结点6;再下沉到第2层, 查找到结点11, 发现7小于11, 回退到结点6;然后再下沉到第1层, 继续查找结点7.如果在第1层还没有找到, 则返回不存在该结点.数据查找的时间复杂度为O(log(n)), 其中, n为跳表中数据元素的个数.

跳表的插入操作主要包含3个步骤:首先, 通过类似查找的算法找到待插入的元素, 并记录出查找过程中的下沉结点; 然后, 采用上面的随机算法决定层数, 分配结点; 最后, 在每一层上修改插入结点的后继指针和下沉结点的后继指针.比如图 4, 假设我们要插入结点8, 先通过查找操作, 记录图中的结点, 确定结点8的待插入位置; 第2步, 假设根据算法1生成结点8的层数为2;最后, 把图中指针域和结点8的指针域修改正确.数据插入的复杂度为O(log(n)).跳表的删除操作是类似于插入操作的逆操作, 先查找到结点, 然后修改指针域.图 5展示了删除结点2的过程.数据删除的复杂度也为O(log(n)).

1.2 数据分布估计

在数据库领域, 系统在运行过程中通常需要基于历史运行数据分析出数据的分布特征, 这有利于加速或优化数据处理.比如, 数据库管理系统的查询优化器模块需要采用直方图的方式进行统计数据分布情况, 这部分数据通常被记录在数据字典内.直方图一般分为等宽直方图和等高直方图, 但直方图的数据还不足够细致.

在人工智能领域, 可以借助机器学习的手段进行密度函数估计(PDF)和累计分布函数(CDF)的估计.对于密度估计的手段, 可以分为两类:一类是参数估计, 需要假设数据服从特定的分布, 然后估计分布的参数; 另一类是无参数估计(非监督学习), 包含直方图估计、核函数估计、k最近邻估计和神经网络估计等.下文我们简单介绍一种实用的技术:核函数估计.

假定随机变量x∈R, 概率密度函数为f(x).需要在给定的一组x的随机样本x₁, x₂, x₃, …, x_n∈R的基础上, 计算f(x)的一个估计$\hat f(x), \hat f(x)$需要充分接近真实的f(x).核函数估计基于所有的样本信息计算近似密度函数:

$ {\hat f_h}(x) = \frac{1}{{nh}}\sum\nolimits_{i = 1}^N {\phi \left( {\frac{{x - {x_i}}}{h}} \right)} $

(1)

其中, n表示样本的数量的个数, h为带宽, ϕ(x)被称为核函数.核函数需要满足下述4个性质.

(1) 对称性:ϕ(u)=ϕ(-u);

(2) 标准化:$\int_{ - \infty }^\infty {f(x){\rm{d}}x} = 1$;

(3) 递减性:ϕ'(x)当u > 0;

(4) 期望为0:E(ϕ)=0.

常见的核函数包括高斯、余弦、均匀、三角形等.对于累计分布函数的估计, 可以对公式(1)求积分得到.

2 相关工作

下面分3个方向介绍和本文直接相关的工作.

●索引技术.

在过去的几十年中, 已经提出了各种不同的索引结构^[3], 例如基于磁盘的B+树^[4]和面向内存系统的T树^[5]以及平衡/红黑树^{[6, 7]}.由于原始内存索引结构具有较差的缓存命中率, 因此提出了针对缓存优化的B+树变体, 例如CSB+树^[8], 它能够通过使用偏移量而不是结点之间的指针来定位数据.此外, 最新的工作还有采用SIMD指令(比如FAST^[9])或GPU^[9-11]优化数据库索引的技术.对于字符串的索引结构也有大量的研究, 例如字典树/前缀树^[12-15].此外, 还有针对索引存储空间进行优化设计的索引结构, 如wavelet树^{[16, 17]}等.跳表^[2]具有与树型索引大致相同的平均搜索复杂度, 但跳表的实现难度小很多.即便是lock-free的跳表实现, 通过使用CAS指令可以很容易地实现跳表^[18], 而这对于B+树来说是非常困难的.Abraham等人^[19]结合跳表和B树来进行有效的查询处理.

●密度估计.

对于数据分布的估计, 最简单直接的方式是通过直方图统计(https://en.wikipedia.org/wiki/Histogram), 直方图虽然简单, 但被广泛应用在数据库查询优化系统中^[20].核密度估计法^[21]可以用来估计未知的密度函数, 属于非参数检验方法之一, 由Rosenblatt和Parzen提出, 又叫Parzen窗(Parzen window).基本原理和直方图有些类似, 是一种平滑的无参数密度估计法.在机器学习社区中对密度估计也进行了大量研究^[22-25].还有基于深度学习的DeepNADE密度估计^[26].密度估计可以应用于排名^[27].如何最有效地模拟CDF, 仍然是一个值得进一步研究的问题.

●智能数据库技术.

对于借助机器学习的方法优化数据处理的技术由来已久, 我们主要列举3个类别的代表性工作:

(1) 比较有代表性的工作是SIGMOD 18上, Dean等人^[28]开创性的手段借助机器学习的技术优化B+树的存储空间和hash索引的冲突问题, 提出了learned index的概念.本文继承同样的思想, 结合跳表的数据结构对跳表进行优化.自Google之后, 2019年出现了大量的关于learned index的研究^[29].Galakatos等人提出了FITing-Tree^[29], 可以在查询精度和存储空间之间达到平衡.Ding等人^[30]提出了ALEX索引, 进一步对learned index在动态数据集上进行优化.Wu^[31]针对二级索引设计了Succinct类索引;

(2) Pavlo^[32]和Chaudhuri^[33]提出了人工智能的方法还可以用于优化数据库运维的难度, 降低DBA的难度.代表性工作主要是卡耐基梅隆大学提出的OtterTune^[34]和阿里巴巴达摩院的iBTune^[35], iBTune被大规模应用在阿里巴巴线上系统中, 主要用于数据库缓存大小的自动设置;

(3) 另外, 在数据挖掘领域存在大量采用机器学习的手段学习位置敏感的哈希函数用于构建近似最近邻索引的工作, 例如文献[36, 37].

3 基于数据分布的跳表

本节首创性地采用数据分布特征去优化跳表结构, 接下来我们将介绍3个优化算法.

3.1 Cdf-list

跳表是一种有序结构, 对于给定的key在跳表中的排序位置location和数据的分布特征有很直接的关联.已知数据累计分布函数的情况下, 对于包含N个元素的数据集, 元素key和key的位置location满足公式(2):

$ CDF(key) = \frac{{location}}{N} $

(2)

当插入key的时候, 我们通过核密度估计的方式估计出数据的累计分布函数$\widehat {CDF}(key)$, 公式(3)可以预判key所在的位置$\widehat {location}$估计:

$ \widehat {location} = \left\lceil {\widehat {CDF}(key) \times N} \right\rceil $

(3)

一旦可以估计key的位置, 可以通过位置信息决定层数, 而不只是通过简单的random方式.

算法2陈述了基于CDF信息计算key层数的cdf-list算法.

算法2. cdf-list的层数决策算法.

输入:数据集个数N, 数据累计分布函数CDF, 待插入的key;

输出:待插入key的层数.

1: Function get_level(key)

2: location=CDF(key)×N;

3: level=1;

4: step=2;

5: While (step < =location)

6:    If (location%step==0)

7:      level++;

8:      End If

9: step=step < < 1;

10: Return level;

与算法1中random的方式相比, 算法2充分利用了数据的分布特征.算法2的输入为数据集个数N、数据集的累积分布函数CDF、待插入的key.输出为待插入key的层数level.首先, 通过公式(3)计算出待插入key在跳表中从小到大的排序位置location(第2行), 注意:如果location的结果为小数, 需要向上取整.为了创建出类似于图 1的跳表结构, 处在不同location的key的高度是可以被计算的(第3行~第10行).理想情况下, 跳表中高度大于等于2的key对应的位置应该是2¹的倍数, 高度大于等于3的key对应的位置应该是2²的倍数, 依此类推, 高度大于等于k+1的key对应的高度应该是2^k的倍数.根据位置判定层数, 实际上是通过判定location的二进制数字的末尾有几个零:如果有k个零, 那么高度则为k+1.例如, 处在第8(二进制1000)个位置的数据高度应该是4层.下面用一个例子对跳表创建过程进行说明.

例1:为便于理解, 这里我们假设数据服从均匀分布, 数据集是包含12个元素的集合(真实数据集会很大).数据集为{5, 4, 3, 2, 1, 6, 7, 8, 9, 10, 12, 11}.初始时, cdf-list为空, 插入元素5的时候, 虽然当前并没有插入1, 2, 3, 4这4个结点, 但可以预判元素5的位置.因为元素5的cdf值为5/12, 元素5应该所处的位置为5(二进制101), 对应的跳表高度为1.依此类推, 可以创建出接近于图 1所示的跳表结构.

3.2 Bound-list

公式(3)对于location的估计会存在误差, 因为累计分布函数的估计存在偏差.这可能会导致多个连续的key判定到同一个location, 从而多个连续的key的高度会相同.如图 6所示:比如说数据中元素7, 8, 9的location估计的都是8, 这就导致判定的高度都为4, 这样的结构在查询过程中是不合理的.

为了容忍位置估计的误差, 我们提出了容忍偏差的算法.首先, 我们采用一个长度为N的数组, 该数组预先记录理想情况下每个位置的元素的高度.算法3给出了数组的创建过程.算法的输入是数据集的大小N, 输出为location和层数的映射数组level_array.对于包含N个元素的数据集, 首先分配一个N+1大小的数组(第2行), 并初始化为0(第3行).注意, level_array[0]代表的是head头结点.初始设置步长为1(第4行), 将level_array中每个元素累计加1(第6行~第8行).然后步长step变为2, 偶数位置的level_array数值加1.依此类推, step每次乘以2(第9行), 直到step < N为止(第5行).

算法3.构造bound-list的层数数组.

输入:数据集个数N;

输出:location与层数的映射数组level_array.

1: Function build_array(N)

2: level_array=new int[N+1]

3: set_zero(level_array);

4: step=1;

5: While (step < =N)

6:    For (i=0; i < =N; i=i+step)

7:      level_array[i]++;

8:    EndFor

9:   step=step < < 1;

10: Return level_array;

例如包含12个元素的数据集, 构建的level_array数组为{4, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3}.我们可以看到, level_ array数组和图 1对应的跳表每个结点的高度一一对应.其中, level_array[0]=4代表的是head头结点.然后引入额外的bound, 每次高度选取时, 我们结合判定位置前后的bound区间内选取最大的level作为最终值.算法4给出了具体的细节.

算法4.容忍CDF估计误差的层数决策算法.

输入:数据集个数N, 数据累计分布函数CDF, 待插入的key, 误差限bound, 层数数组level_array;

输出:待插入key的层数.

1: Function get_level(key)

2: location=CDF(key)×N;

3: lower_bound=max(location-bound, 1);

4: upper_bound=min (location+bound, N);

5: level=0;

6: For (i=lower_bound; i < =upper_bound; i++)

7:    If (level_array[i] > =level)

8:      level=level_array[i];

9:      level_array[i]=1;

10:   End If

11: EndFor

12: Return level;

算法4与算法2类似, 都是根据cdf值决定待插入key的层数.不同的是, 算法4结合bound区间去判定层数, 容忍了估计导致的误差.算法4的输入是数据集个数N、数据估计出的累计分布函数cdf、待插入的key和误差限bound以及算法3生成的数组level_array.算法的输出是待插入key的层数.首先, 根据估计的cdf值估计出key在跳表中的位置(第2行).location的位置并不是精确的, 第3行、第4行计算一个location的区间[lower_bound, upper_bound].然后, 通过在level_array数组的区间[lower_bound, upper_bound]中选取最大值作为待插入key的level, 并把这个最大值所在数组位置的值设置为1, 从而保证在插入附近连续的key时, key的高度不一样.

例2:类似于例1的均匀数据集为{5, 4, 3, 2, 1, 6, 7, 8, 9, 10, 12, 11}.初始时, bound-list为空, 通过算法3构建出level_array.构建的level_array数组为{4, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3}.插入元素5的时候, 预判元素5的cdf值为5/12, 元素5应该所处的位置为5.假设bound为1, 则我们从level_array^[5-1]到level_array[5+1]之间选取最大值3, 即get_level(5)=3.插入5之后, 需要修改层数数组为{4, 1, 2, 1, 1, 1, 2, 1, 4, 1, 2, 1, 3}.接着插入元素4, 预判location为4, 结合bound, 对应层数为1.依此类推, 插入跳表中所有结点.

3.3 Partition-list

Cdf-list和bound-list需要提前知道数据集的大小, 对于数据集大小未知的情况下, 我们提出了partition-list. Partition-list把数据集2^p-1等分.可以通过下述公式判定key属于哪个分区:

$ partition = \left\lceil {CDF(key) \times \left( {{2^p} - 1} \right)} \right\rceil $

(4)

类似bound-list的方式, 我们通过调用算法3的函数build_array(2^p-1)构建长度为2^p的partition_array数组. Partition-list的伪代码如算法5.

算法5. Partition-list的层数决策算法.

输入:数据累计分布函数CDF, 待插入的key, 参数p, 层数数组partition_array;

输出:待插入key的层数.

1: Function get_level(key)

2: partition=CDF(key)×(2^p-1);

3: If (level_array[partition]!=0)

4:    level=level_array[partition]+maxlevel-p;

5:    level_array[partition]=0;

6: Else

7:    level=random_level(maxlevel-p);

8: End If

9: Return level;

算法5首先将partition-list划分成2^p-1个partition, 插入key时, 第1个落入某个parition的key1的层数采用level_array去决策(第4行).若新插入的key2落入key1所属的同样的partition, 则需要算法1类似的随机方法计算层数(第7行).算法能够保证最上面的p层, 在每一个partition里都有唯一的key, 并且最上面p层的key的高度和分布基本类似于图 1的理想状况.

例3:数据集为{6, 7, 8, 9, 10, 5, 4, 3, 2, 1, 14, 13, 12, 11}.初始时, partition-list为空, 最大高度为6.假设p=3, 我们把数据集分成2³-1个分区.当key=6时, partition=3, 对应的高度get_level(5)=1+(6-3)=4.当key=5时, 此时partition=3, partition3内已经有一个高度大于3的key, 所以key=5对应的高度应该通过random_level(3)生成一个高度不大于3的层数, 如图 7所示.

4 结合访问热度的跳表 4.1 Hot-list

数据库key的查找过程中, 我们是需要从上层结点依次向下层结点搜索查找的过程.引言部分指出, 结点层数高的结点, 查找的效率相对比结点低的结点要高.基于此, 我们设计了一套针对热度数据优化的跳表hot-list.

我们根据历史数据的访问频率, 把数据集中访问频率较高的2^h-1个数据判定为热度数据.我们通过算法6, 想构建一个最上面h层都是热数据, maxlevel-h层及以下层级的都是冷数据.

算法6. Hot-list的层数决策算法.

输入:待插入的key, 参数h;

输出:待插入key的层数.

1: Function get_level(key)

2: If (key is hot key)

3:    level=random_level(h)+maxlevel-h;

4: Else

5:    level=random_level(maxlevel-h);

6: End If

7: Return level;

算法6的输入是待插入的key和参数h, 总体依然是采用level的random方案.但我们对key做了一个分层.热度数据的层数高度都在高层(第2行、第3行), 冷数据都在下层(第4行~第6行).通过上述代码, 仍然可以保持每层从下往上依次减半的规律.并且h层以下都是冷数据, h层以上都是热度数据.

例4:类似于例1的均匀数据集为{5, 4, 3, 2, 1, 6, 7, 8, 9, 10, 12, 11}.初始时, hot-list为空, 最大高度为6.假设1, 2, 3, 4, 5这5个key被频繁访问, 也就是属于热度数据.我们设置h为3, 对于1, 2, 3, 4, 5这几个key, 我们采用第3行代码的方式创建层数level, level一定大于3.对于其他的key, 用第5行的方式创建level, 层数肯定不大于3.这就保证热度数据层数大于等于3, 冷数据小于等于3.加速热度数据的访问.

4.2 Mix-list

上述算法partition-list和hot-list可以结合优化成下述算法7, 同时, 结合partition方案和冷热分层的方案进行设计, 原理类似便不展开介绍.原则上, bound-list同样可以和hot-list进行方案结合, 但我们认为, partition-list的适用性比bound-list要好(bound-list需要知道数据集的大小), 因此我们只考虑partition-list和hot-list结合的方案.

算法7.基于数据分布和热度的层数决策算法.

输入:数据累计分布函数CDF, 待插入的key, 误差限bound, 层数数组partition_array, 参数h和p;

输出:待插入key的层数.

1: Function get_level(key)

2: partition=CDF(key)×(2^p-1);

3: If (key is hot key)

4:    level=random_level(h)+maxlevel-h;

5:    level_array[partition]=0;

6: Else If (level_array[partition]!=0)

7:    level=level_array[partition]+maxlevel-p;

8:    level_array[partition]=0;

9: Else

10:    level=random_level(maxlevel-p);

11: End If

12: Return level;

4.3 总结对比

表 1对上述算法进行总结.标准跳表虽然需要的信息少, 适用范围广, 但却不够稳定.cdf-list和bound-list可以基于估计的CDF信息以及数据集大小去判定层数.但是它们需要提前对数据集大小, 削减了应用的范围. partition-list只需要估计CDF函数便可以使用, 对参数p的设置需要进一步评估.hot-list结合数据的冷热信息进行判定层数, 参数h同样会影响性能.mix-list是partition-list和hot-list的结合.

5 实验及分析 5.1 硬件环境

本文的实验基于刀片式HP ProLiant DL380p Gen8服务器进行性能评估.服务器搭配的处理器为E5-2620, 搭载15MB三级缓存, 内存为256GB的DDR4.运行系统为CentOS 7 x86_64(linux 3.10).跳表基于C++实现, g++ 4.8.5编译, 采用CLion 2019.1开发, Googletest进行单元测试, Spdlog进行日志打印, 实现代码开源在“码云”平台(https://gitee.com/bombel/cdf_skiplist).本节首先对基于CDF优化的算法(skiplist, cdf-list, bound-list, partition-list)进行性能评测, 然后针对热度数据优化的算法(skiplist, hot-list, mix-list)进行测评.默认情况下, partition-list中的p=13, hot-list中的h=20.

5.2 测试数据集

不同分布的数据集对CDF的特征有很明显的影响, 本文首先针对不同分布下的合成数据集进行性能评估, 包括均匀分布、正态分布、齐夫分布.具体介绍如下.

(1) 均匀分布:我们基于均匀分布随机数生成器生成测试数据集.为了反映数据集大小对不同跳表的性能影响, 分别生成包含2¹⁵, 2¹⁸, 2²¹, 2²⁴个键值对的数据集, 其中, key和value都是浮点数类型;

(2) 正态分布:采用正态分布生成器生成5个不同方差(均值为10、方差分别为1, 3, 5, 7, 9)、大小都为2²¹的数据集, 因为方差反映了数据的稀疏程度, 方差越大, 数据越稀疏;

(3) 齐夫分布:齐夫分布是一种反映数据偏斜程度的数据集, 广泛用在数据库的测试场景.我们分别生成参数为0.1, 0.3, 0.5, 0.7的齐夫分布.数据集的大小都为2²¹;

(4) 真实数据集.我们基于Amazon和Youtube的真实数据集(http://snap.stanford.edu/data/index.html)对算法性能进行评测.数据集大小分别为334 863和1 134 890, 每个数据项代表的是分别是YouTube用户id和Amazon用户的id.

通过下述实验我们可以发现, 数据的稀疏程度对跳表性能影响不大, 因此对于亚马逊和YouTube的数据分布我们并没有去分析.数据集总结见表 2.

5.3 CDF优化实验结果

本节评估CDF优化算法的效果, 主要测试查询吞吐率(QPS)和吞吐率性能比.图 8和图 9分别反映的是基于正态分布和齐夫分布数据集下的性能的结果.横轴分别是正态分布的方差和齐夫分布的参数, 纵轴分别是查询的吞吐率性能(QPS, 单位是k/s)和cdf-list, bound-list, partition-list相对skiplist的吞吐率性能比.

从实验结果可以发现:

(1) 相同数据量的情况下, 不管是正态分布还是齐夫分布, 每个算法的性能基本不受分布参数的影响;

(2) 但在方差为1和齐夫分布参数为0.7时的数据集下, 每个算法的性能都略有增加, 这是因为实验中的跳表不容许重复key出现, 上述两个参数情况下, 会导致过多key重复, 导致跳表结点数量下降, 性能有所增加;

(3) 根据图 8(b), 图 9(b), bound-list可以提高60%的性能, cdf-list和partition-list的相比skiplist性能有大约25%的提升.

图 10是均匀数据集下的实验.图 10(a)反映了数据集大小对不同跳表的查询吞吐率性能的影响, 横轴对应的数据集大小, 纵轴是查询吞吐率的性能; 图 10(b)反映的是cdf-list, bound-list, partition-list相对skiplist的吞吐率性能比.实验结果反映3点.

(1) 整体上来看, 所有跳表的查询性能都随着数据集大小的增大而下降.这是因为数据集越大, 跳表的层数会越高, 并且每次要对比的key的个数越多, 导致性能下降.虽然skiplist和B+树有区别, 但这也是为什么MySQL, Postgresql等按B+树组织表结构的数据库, 建议单表的行数不要太大的原因;

(2) 不同算法之间对比.可以看到, 性能最好的是bound-list, 其次是cdf-list和partition-list, skiplist最差;

(3) 其中有一个异常的结果, 在小数据集下, partition-list的性能很差, 相比skiplist没有性能提升.这是因为参数p=13在此时的设置是不合适的, 图 11会详细介绍.

Partition-list算法的性能受参数p的影响.图 11展示了在2²¹数据集大小的均匀分布数据集下, 参数p对partition-list的吞吐率影响.实验结果表明, p只有在一个合理的区间内, partition-list的性能才会好, 尤其是p的值接近于log₂(N)之后会发生急剧下降.我们给出了p的一个经验参考值:log₂(N)-5.此外可以看出, partition-list的吞吐率在p=17时和bound-list性能接近.由于Partition-list对于数据集的大小信息未知, 这会导致partition-list的高度比bound-list要高.实际上, bound-list和skiplist一样, 平均高度都是2.而对于partition-list的平均高度一定大于2.比如图 7中, 大于maxlevel-p层(红线以上)的节点的平均高度是2+maxlevel-p(一定大于2), 而小于等于max_level-p的节点的平均高度是2.所以整体的平均高度一定大于2.一些不需要的高度原因导致了partition- list相对bound-list的性能损失.

图 12是真实数据集Amazon和YouTube的实验结果.实验结果表明:(1)算法在小数据Amazon集合下性能加速不明显, 在大数据YouTube下性能加速很明显, 这与图 10的结果一致; (2)小数据下的优化效果不如大数据集下的优化效果.skiplist的优化算法尤其时bound-list更加适合于大数据集.

5.4 热度数据实验结果

本节对比skiplist, partition-list, hot-list, mix-list这几个跳表.为了反映数据库的访问热度特征, 我们针对数据集中1%的数据查询80次, 其他的数据只查询1次的方式模拟冷热数据.

图 13反映的是基于正态分布不同方差的数据集下的性能对比图, 图 14反映的是基于齐夫分布不同参数的数据集下的性能对比图.实验结果表明:(1) hot-list可以获取大致50%的性能提升; (2) hot-list基本不受数据集分布的影响; (3) mix-list相比hot-list几乎没有性能提升.

hot-list的性能会受参数h影响, 图 15展示了在2²¹数据集大小的均匀分布数据集下, 参数h对hos-list性能比的影响.

实验结果表明, hot-list算法的h对性能有很大的影响, h只有在一个合理的区间内才能有加速的效果.我们可以给出h的参考区间:[log₂(M), log₂(N)], 其中, N为数据集的个数, M为热度数据的个数.

此外, 为了反映热度数据的频度特征对不同跳表算法性能的影响, 我们采用服从齐夫分布、参数分别为0.7和0.9的两个分布分别模拟热度数据, 图 16展示了不同算法的性能结果, 其实参数p=17, h=10.

我们可以发现, 在参数为0.9时, 6个算法的性能普遍好于0.1参数时的性能.这是因为数据高频访问时, cache利用率更高.注意, hot-list和mix-list只有在热度数据明显的时候(参数为0.9), 才有性能的提升.

6 结论及展望

本文重点研究数据库跳表索引优化这一经典问题.针对跳表由于随机性导致的不稳定性问题, 提出了3个优化算法cdf-list, bound-list, partition-list.针对热度数据需要被频繁访问的问题, 采用冷热分层处理跳表节点的方式, 提出了hot-list和mix-list跳表算法.在已知数据集大小的情况下, bound-list的性能提升明显; 如果对数据集大小不可知的情况下(一般情况), partition-list也能获取理想的性能提升.实验结果表明, partition-list可以获得最大60%的性能提升.此外, hot-list可以用作在冷热数据明显的场景, 比如类似“双十一”热度商品大促的情形.以本文的partiton-list算法为代表的设计方案, 可以给未来的科研人员和开发人员提供一个新的设计方向.

未来工作中, 我们可以考虑基于人工智能的手段去优化CDF的学习过程和冷热数据学习的过程.本文的跳表结构并没有针对多核特征去做优化, 未来可以结合多核的特性进一步思考.

本文由人工智能赋能的数据管理、分析与系统专刊特约编辑李战怀教授、于戈教授和杨晓春教授推荐.