面向數(shù)據(jù)特征的內存跳表優(yōu)化技術

摘 要:跳表作為數(shù)據(jù)庫中被廣泛采用的索引技術,優(yōu)點在于可以達到類似折半查找的復雜度O(log(n)).但是標準跳表算法中,結點的層數(shù)是通過隨機算法生成的,這就導致跳表的性能是不穩(wěn)定的.在極端情況下,查找復雜度會退化到O(n).這是因為經(jīng)典跳表結構沒有結合數(shù)據(jù)的特征.一個穩(wěn)定的跳表結構應該充分考慮數(shù)據(jù)的分布特征去決定結點層數(shù).基于核密度估計的方式估計數(shù)據(jù)累積分布函數(shù),預測數(shù)據(jù)在跳表中的位置,進而設計用于判定結點層數(shù)的跳表算法.另外,跳表的查找過程中,結點層數(shù)越大的結點被訪問的概率越高.針對歷史數(shù)據(jù)的訪問頻次,設計一種保證頻繁訪問的“熱”數(shù)據(jù)盡可能地在跳表的上層,而訪問較少的“冷”數(shù)據(jù)在跳表的下層的跳表算法.最后,基于合成數(shù)據(jù)和真實數(shù)據(jù)對標準跳表和5 種改進的跳表算法進行了全面的實驗評估并開源代碼.實驗結果表明,優(yōu)化的跳表最高可以獲取60%的性能提升.這為未來的科研工作者和系統(tǒng)開發(fā)人員指出了一個很好的方向.

近年來,伴隨著移動互聯(lián)網(wǎng)和大數(shù)據(jù)的熱潮,行業(yè)對數(shù)據(jù)處理能力,尤其是在線聯(lián)機事務處理能力(OLTP)提出了更高的要求.一個比較典型的案例是在2019 年的“雙十一”,阿里巴巴當天創(chuàng)下了6100 萬次/s 處理峰值的紀錄(https://developer.aliyun.com/article/727517).如此巨大的數(shù)據(jù)處理能力,與阿里自研數(shù)據(jù)庫OceanBase[1]息息相關的.在摩爾定律的作用下,計算機硬件(多核、大內存、固態(tài)硬盤等)的性能一直在快速發(fā)展,這很大程度上促進了數(shù)據(jù)庫得以支撐類似“雙十一”這種高吞吐率的應用.典型地,計算機處理器的性能從單方面提高頻率轉向增加核心數(shù)的方向轉變.為了適配新硬件的特性及最大限度地發(fā)揮硬件的性能,數(shù)據(jù)庫領域很多模塊都要針對性地進行適配.索引技術作為數(shù)據(jù)庫存儲層的核心,同樣需要提出適配.跳表(Skiplist[2])是數(shù)據(jù)庫領域的一個重要索引技術,它具有結構簡單、易于實現(xiàn)、無鎖并發(fā)、O(log(n))的查找復雜度等優(yōu)點,因此在LevelDB,MemSQL,Redis 等數(shù)據(jù)庫中都有廣泛應用.

跳表是基于線性鏈表改進而來的.傳統(tǒng)的鏈表中,每個結點只包含一個結點指針域,而跳表的每個基礎結點包含多個指針域.圖1 是理想情況下的跳表示意圖,水平方向來看,每一層都是單向鏈表,而且越往上的層級,結點越稀疏,跳表通過維護每個結點的層數(shù),保證每層結點個數(shù)都比下一層大致減半.跳表的查找操作是從最上層結點依次往下縮小查找區(qū)間,過程類似于折半查找.對于跳表的插入操作,先根據(jù)待插入key 查找到待插入的位置,然后算法通過隨機算法確定結點的層數(shù),再插入結點.假設結點key 的層數(shù)為3,則維護下三層鏈表的指針.第1.1 節(jié)將對跳表做詳細介紹.

Fig.1 Example of skiplist in ideal case

圖1 理想情況的跳表示例

但我們認為,跳表不是一個穩(wěn)定的數(shù)據(jù)結構.計算機科學中,經(jīng)典的不穩(wěn)定的數(shù)據(jù)結構是二叉查找樹.二叉樹的特性只需要保證左小右大的特質,一旦數(shù)據(jù)從小到大依次插入二叉樹,二叉樹便退化為線性表,此時的查找復雜度也從O(log(n))退化到O(n).因此提出了平衡二叉樹,通過左旋和右旋操作,改進了二叉樹的穩(wěn)定性.

跳表結構的查找時間是通過多層鏈表指針域達到加速的效果.但跳表的層數(shù)隨機算法導致它不是一個穩(wěn)定的結構,具體來說,包含以下兩點挑戰(zhàn).

·數(shù)據(jù)偏斜.跳表的優(yōu)點在于可以達到類似折半查找的復雜度O(log(n)),但是跳表的層數(shù)是通過隨機算法生成的,這會導致性能的不穩(wěn)定.在極端情況下,會生成類似于圖2 的跳表結構,此時的查找復雜度等價于鏈表的查找復雜度(都是O(n)),跳表的優(yōu)點便不復存在了.這主要是因為跳表的隨機生成層數(shù)的算法并沒有結合數(shù)據(jù)特征去生成跳表結構.我們認為,一個穩(wěn)定的跳表結構應該充分考慮數(shù)據(jù)的分布特征,在插入key 的同時,根據(jù)分布特征去決定層數(shù),而不是隨機生成;

·熱度數(shù)據(jù).我們發(fā)現(xiàn),跳表的查找過程中,結點層數(shù)越大的結點被訪問的概率越高.比如圖1 中,查找結點8,直接在第1 層便找到了,便不需要繼續(xù)一直下沉操作了.這促使我們可以充分考慮熱度數(shù)據(jù)的特征,讓熱度數(shù)據(jù)的層數(shù)盡可能高,訪問效率便更快一些.

Fig.2 Example of skiplist in worst case

圖2 最壞情況的跳表示例

本文的貢獻如下:

·基于數(shù)據(jù)分布估計的跳表結構.本文基于核密度估計的方式去估計數(shù)據(jù)集合的累積分布函數(shù),進一步預測數(shù)據(jù)在跳表中的位置和結點層數(shù),從而達到跳表查找性能的優(yōu)化目的;

·基于冷熱數(shù)據(jù)分層的跳表結構.本文針對歷史數(shù)據(jù)的訪問頻次信息,設計了一種冷熱分層的跳表算法,對頻繁訪問的熱度數(shù)據(jù)保證盡可能的在跳表的上層,而訪問較少的冷數(shù)據(jù)在跳表的下層,從而保證熱度數(shù)據(jù)訪問加速的效果;

·跳表選型.本文基于合成數(shù)據(jù)和真實數(shù)據(jù)對標準跳表和5 種改進的跳表算法進行了全面的實驗評估并開源代碼.實驗結果表明,優(yōu)化的跳表最高可以獲取60%的性能提升.

本文第1 節(jié)對跳表和密度估計進行全面的介紹.第2 節(jié)對相關工作進行總結.第3 節(jié)根據(jù)數(shù)據(jù)分布特征進行跳表算法的優(yōu)化設計.第4 節(jié)根據(jù)熱度數(shù)據(jù)特征對跳表進行優(yōu)化算法設計.第5 節(jié)通過合成和真實數(shù)據(jù)集對上述算法進行實驗驗證.第6 節(jié)對全文進行總結,并提出對未來工作的設想.

1 預備知識

本節(jié)將完整介紹跳表的概念和基本操作,然后討論標準跳表算法所遇到的問題.

1.1 跳 表

跳表從結構上可以看成多層鏈表結構.它的結點結構和鏈表的結點結構很相似,不同的是,鏈表結點除了數(shù)據(jù)域之外只包含一個next 指針域,而跳表結點包含多個指針域.每個結點所包含的指針個數(shù)(層數(shù))是可變的.跳表結點一旦被創(chuàng)建,指針個數(shù)便確定.多個指針域按照“層”的方式,維護多個單向鏈表.通過隨機函數(shù)(幾何分布)控制每個結點的指針個數(shù)(層數(shù)),從而保證每一層的“鏈表”個數(shù)依次減半.因此,跳表是一種隨機性算法.

算法1 闡述了標準跳表中的隨機生成層數(shù)的算法.原理相當于做一次拋硬幣的(伯努利實驗)實驗,統(tǒng)計首次拋出反面的次數(shù).如果遇到正面繼續(xù)拋,遇到反面則停止,用實驗中拋硬幣的次數(shù)K 作為結點的層數(shù).顯然,隨機變量K 服從參數(shù)p=1/2 的幾何分布.K 的期望值E[K]=1/p=2.也就是說,跳表中元素的平均層數(shù)為2 層,包含N 個元素的跳表的指針域個數(shù)大致為2n 個.

算法1.基于伯努利實驗的跳表層數(shù)決策算法.

數(shù)據(jù)庫索引一般需要提供3 種訪問操作:查找、插入、刪除.跳表的查找操作是從最上層開始查找,依次按照范圍往下查找,直到最下面一層為止.如圖3 所示,假設我們要查找結點7.首先,我們從最上第4 層開始找到結點1,然后下沉到第3 層,依次查找到結點6;再下沉到第2 層,查找到結點11,發(fā)現(xiàn)7 小于11,回退到結點6;然后再下沉到第1 層,繼續(xù)查找結點7.如果在第1 層還沒有找到,則返回不存在該結點.數(shù)據(jù)查找的時間復雜度為O(log(n)),其中,n 為跳表中數(shù)據(jù)元素的個數(shù).

Fig.3 Example of searching node 7

圖3 查找結點7 的示例

跳表的插入操作主要包含3 個步驟:首先,通過類似查找的算法找到待插入的元素,并記錄出查找過程中的下沉結點;然后,采用上面的隨機算法決定層數(shù),分配結點;最后,在每一層上修改插入結點的后繼指針和下沉結點的后繼指針.比如圖4,假設我們要插入結點8,先通過查找操作,記錄圖中的結點,確定結點8 的待插入位置;第2 步,假設根據(jù)算法1 生成結點8 的層數(shù)為2;最后,把圖中指針域和結點8 的指針域修改正確.數(shù)據(jù)插入的復雜度為O(log(n)).跳表的刪除操作是類似于插入操作的逆操作,先查找到結點,然后修改指針域.圖5 展示了刪除結點2 的過程.數(shù)據(jù)刪除的復雜度也為O(log(n)).

Fig.4 Example of insert node 8 in skiplist

圖4 插入結點8 的示例

Fig.5 Example of delete node 2 in skiplist

圖5 刪除結點2 的示例

1.2 數(shù)據(jù)分布估計

在數(shù)據(jù)庫領域,系統(tǒng)在運行過程中通常需要基于歷史運行數(shù)據(jù)分析出數(shù)據(jù)的分布特征,這有利于加速或優(yōu)化數(shù)據(jù)處理.比如,數(shù)據(jù)庫管理系統(tǒng)的查詢優(yōu)化器模塊需要采用直方圖的方式進行統(tǒng)計數(shù)據(jù)分布情況,這部分數(shù)據(jù)通常被記錄在數(shù)據(jù)字典內.直方圖一般分為等寬直方圖和等高直方圖,但直方圖的數(shù)據(jù)還不足夠細致.

在人工智能領域,可以借助機器學習的手段進行密度函數(shù)估計(PDF)和累計分布函數(shù)(CDF)的估計.對于密度估計的手段,可以分為兩類:一類是參數(shù)估計,需要假設數(shù)據(jù)服從特定的分布,然后估計分布的參數(shù);另一類是無參數(shù)估計(非監(jiān)督學習),包含直方圖估計、核函數(shù)估計、k 最近鄰估計和神經(jīng)網(wǎng)絡估計等.下文我們簡單介紹一種實用的技術:核函數(shù)估計.

假定隨機變量x∈R,概率密度函數(shù)為f(x).需要在給定的一組x 的隨機樣本x1,x2,x3,…,xn∈R 的基礎上,計算f(x)的一個估計

需要充分接近真實的f(x).核函數(shù)估計基于所有的樣本信息計算近似密度函數(shù):

其中,n 表示樣本的數(shù)量的個數(shù),h 為帶寬,φ(x)被稱為核函數(shù).核函數(shù)需要滿足下述4 個性質.

(1)對稱性:φ(u)=φ(?u);

(2)標準化:

(3)遞減性:φ′(x)當u>0;

(4)期望為0:E(φ)=0.

常見的核函數(shù)包括高斯、余弦、均勻、三角形等.對于累計分布函數(shù)的估計,可以對公式(1)求積分得到.

2 相關工作

下面分3 個方向介紹和本文直接相關的工作.

·索引技術.

在過去的幾十年中,已經(jīng)提出了各種不同的索引結構[3],例如基于磁盤的B+樹[4]和面向內存系統(tǒng)的T 樹[5]以及平衡/紅黑樹[6,7].由于原始內存索引結構具有較差的緩存命中率,因此提出了針對緩存優(yōu)化的B+樹變體,例如CSB+樹[8],它能夠通過使用偏移量而不是結點之間的指針來定位數(shù)據(jù).此外,最新的工作還有采用SIMD 指令(比如FAST[9])或GPU[9?11]優(yōu)化數(shù)據(jù)庫索引的技術.對于字符串的索引結構也有大量的研究,例如字典樹/前綴樹[12?15].此外,還有針對索引存儲空間進行優(yōu)化設計的索引結構,如wavelet 樹[16,17]等.跳表[2]具有與樹型索引大致相同的平均搜索復雜度,但跳表的實現(xiàn)難度小很多.即便是lock-free 的跳表實現(xiàn),通過使用CAS 指令可以很容易地實現(xiàn)跳表[18],而這對于B+樹來說是非常困難的.Abraham 等人[19]結合跳表和B 樹來進行有效的查詢處理.

·密度估計.

對于數(shù)據(jù)分布的估計,最簡單直接的方式是通過直方圖統(tǒng)計(https://en.wikipedia.org/wiki/Histogram),直方圖雖然簡單,但被廣泛應用在數(shù)據(jù)庫查詢優(yōu)化系統(tǒng)中[20].核密度估計法[21]可以用來估計未知的密度函數(shù),屬于非參數(shù)檢驗方法之一,由Rosenblatt 和Parzen 提出,又叫Parzen 窗(Parzen window).基本原理和直方圖有些類似,是一種平滑的無參數(shù)密度估計法.在機器學習社區(qū)中對密度估計也進行了大量研究[22?25].還有基于深度學習的DeepNADE 密度估計[26].密度估計可以應用于排名[27].如何最有效地模擬CDF,仍然是一個值得進一步研究的問題.

·智能數(shù)據(jù)庫技術.

對于借助機器學習的方法優(yōu)化數(shù)據(jù)處理的技術由來已久,我們主要列舉3 個類別的代表性工作:

(1)比較有代表性的工作是SIGMOD 18 上,Dean 等人[28]開創(chuàng)性的手段借助機器學習的技術優(yōu)化B+樹的存儲空間和hash 索引的沖突問題,提出了learned index 的概念.本文繼承同樣的思想,結合跳表的數(shù)據(jù)結構對跳表進行優(yōu)化.自Google 之后,2019 年出現(xiàn)了大量的關于learned index 的研究[29].Galakatos 等人提出了FITing-Tree[29],可以在查詢精度和存儲空間之間達到平衡.Ding 等人[30]提出了ALEX 索引,進一步對learned index 在動態(tài)數(shù)據(jù)集上進行優(yōu)化.Wu[31]針對二級索引設計了Succinct 類索引;

(2)Pavlo[32]和Chaudhuri[33]提出了人工智能的方法還可以用于優(yōu)化數(shù)據(jù)庫運維的難度,降低DBA 的難度.代表性工作主要是卡耐基梅隆大學提出的OtterTune[34]和阿里巴巴達摩院的iBTune[35],iBTune 被大規(guī)模應用在阿里巴巴線上系統(tǒng)中,主要用于數(shù)據(jù)庫緩存大小的自動設置;

(3)另外,在數(shù)據(jù)挖掘領域存在大量采用機器學習的手段學習位置敏感的哈希函數(shù)用于構建近似最近鄰索引的工作,例如文獻[36,37].

3 基于數(shù)據(jù)分布的跳表

本節(jié)首創(chuàng)性地采用數(shù)據(jù)分布特征去優(yōu)化跳表結構,接下來我們將介紹3 個優(yōu)化算法.

3.1 Cdf-list

跳表是一種有序結構,對于給定的key 在跳表中的排序位置location 和數(shù)據(jù)的分布特征有很直接的關聯(lián).已知數(shù)據(jù)累計分布函數(shù)的情況下,對于包含N 個元素的數(shù)據(jù)集,元素key 和key 的位置location 滿足公式(2):

當插入key 的時候,我們通過核密度估計的方式估計出數(shù)據(jù)的累計分布函數(shù)

,公式(3)可以預判key 所在的位置

估計:

一旦可以估計key 的位置,可以通過位置信息決定層數(shù),而不只是通過簡單的random 方式.

算法2 陳述了基于CDF 信息計算key 層數(shù)的cdf-list 算法.

算法2.cdf-list 的層數(shù)決策算法.

與算法1 中random 的方式相比,算法2 充分利用了數(shù)據(jù)的分布特征.算法2 的輸入為數(shù)據(jù)集個數(shù)N、數(shù)據(jù)集的累積分布函數(shù)CDF、待插入的key.輸出為待插入key 的層數(shù)level.首先,通過公式(3)計算出待插入key 在跳表中從小到大的排序位置location(第2 行),注意:如果location 的結果為小數(shù),需要向上取整.為了創(chuàng)建出類似于圖1 的跳表結構,處在不同location 的key 的高度是可以被計算的(第3 行～第10 行).理想情況下,跳表中高度大于等于2 的key 對應的位置應該是21 的倍數(shù),高度大于等于3 的key 對應的位置應該是22 的倍數(shù),依此類推,高度大于等于k+1 的key 對應的高度應該是2k 的倍數(shù).根據(jù)位置判定層數(shù),實際上是通過判定location 的二進制數(shù)字的末尾有幾個零:如果有k 個零,那么高度則為k+1.例如,處在第8(二進制1000)個位置的數(shù)據(jù)高度應該是4層.下面用一個例子對跳表創(chuàng)建過程進行說明.

例1:為便于理解,這里我們假設數(shù)據(jù)服從均勻分布,數(shù)據(jù)集是包含12 個元素的集合(真實數(shù)據(jù)集會很大).數(shù)據(jù)集為{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.依此類推,可以創(chuàng)建出接近于圖1 所示的跳表結構.

3.2 Bound-list

公式(3)對于location 的估計會存在誤差,因為累計分布函數(shù)的估計存在偏差.這可能會導致多個連續(xù)的key判定到同一個location,從而多個連續(xù)的key 的高度會相同.如圖6 所示:比如說數(shù)據(jù)中元素7,8,9 的location 估計的都是8,這就導致判定的高度都為4,這樣的結構在查詢過程中是不合理的.

Fig.6 Unsuited structure caused by CDF error

圖6 CDF 誤差導致的不合理結構

為了容忍位置估計的誤差,我們提出了容忍偏差的算法.首先,我們采用一個長度為N 的數(shù)組,該數(shù)組預先記錄理想情況下每個位置的元素的高度.算法3 給出了數(shù)組的創(chuàng)建過程.算法的輸入是數(shù)據(jù)集的大小N,輸出為location 和層數(shù)的映射數(shù)組level_array.對于包含N 個元素的數(shù)據(jù)集,首先分配一個N+1 大小的數(shù)組(第2 行),并初始化為0(第3 行).注意,level_array[0]代表的是head 頭結點.初始設置步長為1(第4 行),將level_array 中每個元素累計加1(第6 行～第8 行).然后步長step 變?yōu)?,偶數(shù)位置的level_array 數(shù)值加1.依此類推,step 每次乘以2(第9 行),直到step

算法3.構造bound-list 的層數(shù)數(shù)組.

例如包含12 個元素的數(shù)據(jù)集,構建的level_array 數(shù)組為{4,1,2,1,3,1,2,1,4,1,2,1,3}.我們可以看到,level_array 數(shù)組和圖1 對應的跳表每個結點的高度一一對應.其中,level_array[0]=4 代表的是head 頭結點.然后引入額外的bound,每次高度選取時,我們結合判定位置前后的bound 區(qū)間內選取最大的level 作為最終值.算法4 給出了具體的細節(jié).

算法4.容忍CDF 估計誤差的層數(shù)決策算法.

算法4 與算法2 類似,都是根據(jù)cdf 值決定待插入key 的層數(shù).不同的是,算法4 結合bound 區(qū)間去判定層數(shù),容忍了估計導致的誤差.算法4 的輸入是數(shù)據(jù)集個數(shù)N、數(shù)據(jù)估計出的累計分布函數(shù)cdf、待插入的key 和誤差限bound 以及算法3 生成的數(shù)組level_array.算法的輸出是待插入key 的層數(shù).首先,根據(jù)估計的cdf 值估計出key在跳表中的位置(第 2 行).location 的位置并不是精確的,第 3 行、第 4 行計算一個 location 的區(qū)間[lower_bound,upper_bound].然后,通過在level_array 數(shù)組的區(qū)間[lower_bound,upper_bound]中選取最大值作為待插入key 的level,并把這個最大值所在數(shù)組位置的值設置為1,從而保證在插入附近連續(xù)的key 時,key 的高度不一樣.

例2:類似于例1 的均勻數(shù)據(jù)集為{5,4,3,2,1,6,7,8,9,10,12,11}.初始時,bound-list 為空,通過算法3 構建出level_array.構建的level_array 數(shù)組為{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 之后,需要修改層數(shù)數(shù)組為

.接著插入元素4,預判l(wèi)ocation 為4,結合bound,對應層數(shù)為1.依此類推,插入跳表中所有結點.

3.3 Partition-list

Cdf-list 和bound-list 需要提前知道數(shù)據(jù)集的大小,對于數(shù)據(jù)集大小未知的情況下,我們提出了partition-list.Partition-list 把數(shù)據(jù)集2p?1 等分.可以通過下述公式判定key 屬于哪個分區(qū):

類似bound-list 的方式,我們通過調用算法3 的函數(shù)build_array(2p?1)構建長度為2p的partition_array 數(shù)組.Partition-list的偽代碼如算法5.

算法5.Partition-list 的層數(shù)決策算法.

算法5 首先將partition-list 劃分成2p?1 個partition,插入key 時,第1 個落入某個parition 的key1 的層數(shù)采用level_array 去決策(第4 行).若新插入的key2 落入key1 所屬的同樣的partition,則需要算法1 類似的隨機方法計算層數(shù)(第7 行).算法能夠保證最上面的p 層,在每一個partition 里都有唯一的key,并且最上面p 層的key的高度和分布基本類似于圖1 的理想狀況.

例3:數(shù)據(jù)集為{6,7,8,9,10,5,4,3,2,1,14,13,12,11}.初始時,partition-list 為空,最大高度為6.假設p=3,我們把數(shù)據(jù)集分成23?1 個分區(qū).當key=6 時,partition=3,對應的高度get_level(5)=1+(6?3)=4.當key=5 時,此時partition=3,partition3 內已經(jīng)有一個高度大于3 的key,所以key=5 對應的高度應該通過random_level(3)生成一個高度不大于3 的層數(shù),如圖7 所示.

Fig.7 Example of partition-based skiplist

圖7 基于分區(qū)的跳表示例

4 結合訪問熱度的跳表

4.1 Hot-list

數(shù)據(jù)庫key 的查找過程中,我們是需要從上層結點依次向下層結點搜索查找的過程.引言部分指出,結點層數(shù)高的結點,查找的效率相對比結點低的結點要高.基于此,我們設計了一套針對熱度數(shù)據(jù)優(yōu)化的跳表hot-list.

我們根據(jù)歷史數(shù)據(jù)的訪問頻率,把數(shù)據(jù)集中訪問頻率較高的2h?1 個數(shù)據(jù)判定為熱度數(shù)據(jù).我們通過算法6,想構建一個最上面h層都是熱數(shù)據(jù),maxlevel?h 層及以下層級的都是冷數(shù)據(jù).

算法6.Hot-list 的層數(shù)決策算法.

算法6 的輸入是待插入的key 和參數(shù)h,總體依然是采用level 的random 方案.但我們對key 做了一個分層.熱度數(shù)據(jù)的層數(shù)高度都在高層(第2 行、第3 行),冷數(shù)據(jù)都在下層(第4 行～第6 行).通過上述代碼,仍然可以保持每層從下往上依次減半的規(guī)律.并且h層以下都是冷數(shù)據(jù),h 層以上都是熱度數(shù)據(jù).

例4:類似于例1 的均勻數(shù)據(jù)集為{5,4,3,2,1,6,7,8,9,10,12,11}.初始時,hot-list 為空,最大高度為6.假設1,2,3,4,5 這5 個key 被頻繁訪問,也就是屬于熱度數(shù)據(jù).我們設置h 為3,對于1,2,3,4,5 這幾個key,我們采用第3 行代碼的方式創(chuàng)建層數(shù)level,level 一定大于3.對于其他的key,用第5 行的方式創(chuàng)建level,層數(shù)肯定不大于3.這就保證熱度數(shù)據(jù)層數(shù)大于等于3,冷數(shù)據(jù)小于等于3.加速熱度數(shù)據(jù)的訪問.

4.2 Mix-list

上述算法partition-list 和hot-list 可以結合優(yōu)化成下述算法7,同時,結合partition 方案和冷熱分層的方案進行設計,原理類似便不展開介紹.原則上,bound-list 同樣可以和hot-list 進行方案結合,但我們認為,partition-list的適用性比bound-list 要好(bound-list 需要知道數(shù)據(jù)集的大小),因此我們只考慮partition-list 和hot-list 結合的方案.

算法7.基于數(shù)據(jù)分布和熱度的層數(shù)決策算法.

4.3 總結對比

表1 對上述算法進行總結.標準跳表雖然需要的信息少,適用范圍廣,但卻不夠穩(wěn)定.cdf-list 和bound-list 可以基于估計的CDF 信息以及數(shù)據(jù)集大小去判定層數(shù).但是它們需要提前對數(shù)據(jù)集大小,削減了應用的范圍.partition-list 只需要估計CDF 函數(shù)便可以使用,對參數(shù)p 的設置需要進一步評估.hot-list 結合數(shù)據(jù)的冷熱信息進行判定層數(shù),參數(shù)h 同樣會影響性能.mix-list 是partition-list和hot-list 的結合.

Table 1 Summary of algorithms

表1 算法對比總結

5 實驗及分析

5.1 硬件環(huán)境

本文的實驗基于刀片式HP ProLiant DL380p Gen8 服務器進行性能評估.服務器搭配的處理器為E5-2620,搭載15MB 三級緩存,內存為256GB 的DDR4.運行系統(tǒng)為CentOS 7 x86_64(linux 3.10).跳表基于C++實現(xiàn),g++4.8.5 編譯,采用CLion 2019.1 開發(fā),Googletest 進行單元測試,Spdlog 進行日志打印,實現(xiàn)代碼開源在“碼云”平臺(https://gitee.com/bombel/cdf_skiplist).本節(jié)首先對基于CDF 優(yōu)化的算法(skiplist,cdf-list,bound-list,partition-list)進行性能評測,然后針對熱度數(shù)據(jù)優(yōu)化的算法(skiplist,hot-list,mix-list)進行測評.默認情況下,partition-list 中的p=13,hot-list 中的h=20.

5.2 測試數(shù)據(jù)集

不同分布的數(shù)據(jù)集對CDF 的特征有很明顯的影響,本文首先針對不同分布下的合成數(shù)據(jù)集進行性能評估,包括均勻分布、正態(tài)分布、齊夫分布.具體介紹如下.

(1)均勻分布:我們基于均勻分布隨機數(shù)生成器生成測試數(shù)據(jù)集.為了反映數(shù)據(jù)集大小對不同跳表的性能影響,分別生成包含215,218,221,224 個鍵值對的數(shù)據(jù)集,其中,key 和value 都是浮點數(shù)類型;

(2)正態(tài)分布:采用正態(tài)分布生成器生成5 個不同方差(均值為10、方差分別為1,3,5,7,9)、大小都為221的數(shù)據(jù)集,因為方差反映了數(shù)據(jù)的稀疏程度,方差越大,數(shù)據(jù)越稀疏;

(3)齊夫分布:齊夫分布是一種反映數(shù)據(jù)偏斜程度的數(shù)據(jù)集,廣泛用在數(shù)據(jù)庫的測試場景.我們分別生成參數(shù)為0.1,0.3,0.5,0.7 的齊夫分布.數(shù)據(jù)集的大小都為221;

(4)真實數(shù)據(jù)集.我們基于Amazon 和Youtube 的真實數(shù)據(jù)集(http://snap.stanford.edu/data/index.html)對算法性能進行評測.數(shù)據(jù)集大小分別為334 863 和1 134 890,每個數(shù)據(jù)項代表的是分別是YouTube 用戶id 和Amazon 用戶的id.

通過下述實驗我們可以發(fā)現(xiàn),數(shù)據(jù)的稀疏程度對跳表性能影響不大,因此對于亞馬遜和YouTube 的數(shù)據(jù)分布我們并沒有去分析.數(shù)據(jù)集總結見表2.

Table 2 Dataset

表2 數(shù)據(jù)集

5.3 CDF優(yōu)化實驗結果

本節(jié)評估CDF 優(yōu)化算法的效果,主要測試查詢吞吐率(QPS)和吞吐率性能比.圖8 和圖9 分別反映的是基于正態(tài)分布和齊夫分布數(shù)據(jù)集下的性能的結果.橫軸分別是正態(tài)分布的方差和齊夫分布的參數(shù),縱軸分別是查詢的吞吐率性能(QPS,單位是k/s)和cdf-list,bound-list,partition-list 相對skiplist 的吞吐率性能比.

從實驗結果可以發(fā)現(xiàn):

(1)相同數(shù)據(jù)量的情況下,不管是正態(tài)分布還是齊夫分布,每個算法的性能基本不受分布參數(shù)的影響;

(2)但在方差為1 和齊夫分布參數(shù)為0.7 時的數(shù)據(jù)集下,每個算法的性能都略有增加,這是因為實驗中的跳表不容許重復key 出現(xiàn),上述兩個參數(shù)情況下,會導致過多key 重復,導致跳表結點數(shù)量下降,性能有所增加;

(3)根據(jù)圖8(b),圖9(b),bound-list 可以提高60%的性能,cdf-list 和partition-list 的相比skiplist 性能有大約25%的提升.

Fig.8 Performance influenced by the parameter of normal distribution’s variance

圖8 正態(tài)分布不同方差下,吞吐率的性能和性能比

Fig.9 Performance influenced by the parameter of Zipfian distribution

圖9 齊夫分布下不同參數(shù)吞吐率的性能和性能比

圖10 是均勻數(shù)據(jù)集下的實驗.圖10(a)反映了數(shù)據(jù)集大小對不同跳表的查詢吞吐率性能的影響,橫軸對應的數(shù)據(jù)集大小,縱軸是查詢吞吐率的性能;圖10(b)反映的是cdf-list,bound-list,partition-list 相對skiplist 的吞吐率性能比.實驗結果反映3 點.

(1)整體上來看,所有跳表的查詢性能都隨著數(shù)據(jù)集大小的增大而下降.這是因為數(shù)據(jù)集越大,跳表的層數(shù)會越高,并且每次要對比的key 的個數(shù)越多,導致性能下降.雖然skiplist 和B+樹有區(qū)別,但這也是為什么MySQL,Postgresql 等按B+樹組織表結構的數(shù)據(jù)庫,建議單表的行數(shù)不要太大的原因;

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

(3)其中有一個異常的結果,在小數(shù)據(jù)集下,partition-list 的性能很差,相比skiplist 沒有性能提升.這是因為參數(shù)p=13 在此時的設置是不合適的,圖11 會詳細介紹.

Fig.10 Performance influenced by dataset size with uniform distribution

圖10 均勻分布下,數(shù)據(jù)集大小對算法性能的影響

Partition-list 算法的性能受參數(shù)p 的影響.圖11 展示了在221 數(shù)據(jù)集大小的均勻分布數(shù)據(jù)集下,參數(shù)p 對partition-list 的吞吐率影響.實驗結果表明,p 只有在一個合理的區(qū)間內,partition-list 的性能才會好,尤其是p 的值接近于log2(N)之后會發(fā)生急劇下降.我們給出了p 的一個經(jīng)驗參考值:log2(N)?5.此外可以看出,partition-list的吞吐率在p=17 時和bound-list 性能接近.由于Partition-list 對于數(shù)據(jù)集的大小信息未知,這會導致partition-list的高度比bound-list 要高.實際上,bound-list 和skiplist 一樣,平均高度都是2.而對于partition-list 的平均高度一定大于2.比如圖7 中,大于maxlevel?p 層(紅線以上)的節(jié)點的平均高度是2+maxlevel?p(一定大于2),而小于等于max_level-p 的節(jié)點的平均高度是2.所以整體的平均高度一定大于2.一些不需要的高度原因導致了partitionlist 相對bound-list 的性能損失.

Fig.11 Performance influenced by parameter p

圖11 參數(shù)p 對性能的影響

圖12 是真實數(shù)據(jù)集Amazon 和YouTube 的實驗結果.實驗結果表明:(1)算法在小數(shù)據(jù)Amazon 集合下性能加速不明顯,在大數(shù)據(jù)YouTube 下性能加速很明顯,這與圖10 的結果一致;(2)小數(shù)據(jù)下的優(yōu)化效果不如大數(shù)據(jù)集下的優(yōu)化效果.skiplist 的優(yōu)化算法尤其時bound-list 更加適合于大數(shù)據(jù)集.

Fig.12 Performance under real dataset

圖12 真實數(shù)據(jù)集合下的性能

5.4 熱度數(shù)據(jù)實驗結果

本節(jié)對比skiplist,partition-list,hot-list,mix-list 這幾個跳表.為了反映數(shù)據(jù)庫的訪問熱度特征,我們針對數(shù)據(jù)集中1%的數(shù)據(jù)查詢80 次,其他的數(shù)據(jù)只查詢1 次的方式模擬冷熱數(shù)據(jù).

圖13 反映的是基于正態(tài)分布不同方差的數(shù)據(jù)集下的性能對比圖,圖14 反映的是基于齊夫分布不同參數(shù)的數(shù)據(jù)集下的性能對比圖.實驗結果表明:(1)hot-list 可以獲取大致50%的性能提升;(2)hot-list 基本不受數(shù)據(jù)集分布的影響;(3)mix-list 相比hot-list 幾乎沒有性能提升.

Fig.13 Performance influenced by the parameter of normal distribution’s variance

圖13 正態(tài)分布下方差對性能的影響

Fig.14 Performance influenced by the parameter of Zipfian distribution

圖14 齊夫分布下參數(shù)對性能的影響

hot-list 的性能會受參數(shù)h 影響,圖15 展示了在221 數(shù)據(jù)集大小的均勻分布數(shù)據(jù)集下,參數(shù)h 對hos-list 性能比的影響.

Fig.15 Performance influenced by parameter h

圖15 參數(shù)h 對性能的影響

實驗結果表明,hot-list 算法的h 對性能有很大的影響,h 只有在一個合理的區(qū)間內才能有加速的效果.我們可以給出h 的參考區(qū)間:[log2(M),log2(N)],其中,N 為數(shù)據(jù)集的個數(shù),M 為熱度數(shù)據(jù)的個數(shù).

此外,為了反映熱度數(shù)據(jù)的頻度特征對不同跳表算法性能的影響,我們采用服從齊夫分布、參數(shù)分別為0.7和0.9 的兩個分布分別模擬熱度數(shù)據(jù),圖16 展示了不同算法的性能結果,其實參數(shù)p=17,h=10.

Fig.16 Performance under different Zipfian distribution dataset

圖16 訪問頻度(不同齊夫分布參數(shù))對性能和性能比的影響

我們可以發(fā)現(xiàn),在參數(shù)為0.9 時,6 個算法的性能普遍好于0.1 參數(shù)時的性能.這是因為數(shù)據(jù)高頻訪問時,cache利用率更高.注意,hot-list 和mix-list 只有在熱度數(shù)據(jù)明顯的時候(參數(shù)為0.9),才有性能的提升.

6 結論及展望

本文重點研究數(shù)據(jù)庫跳表索引優(yōu)化這一經(jīng)典問題.針對跳表由于隨機性導致的不穩(wěn)定性問題,提出了3 個優(yōu)化算法cdf-list,bound-list,partition-list.針對熱度數(shù)據(jù)需要被頻繁訪問的問題,采用冷熱分層處理跳表節(jié)點的方式,提出了hot-list 和mix-list跳表算法.在已知數(shù)據(jù)集大小的情況下,bound-list 的性能提升明顯;如果對數(shù)據(jù)集大小不可知的情況下(一般情況),partition-list 也能獲取理想的性能提升.實驗結果表明,partition-list 可以獲得最大60%的性能提升.此外,hot-list 可以用作在冷熱數(shù)據(jù)明顯的場景,比如類似“雙十一”熱度商品大促的情形.以本文的partiton-list 算法為代表的設計方案,可以給未來的科研人員和開發(fā)人員提供一個新的設計方向.

未來工作中,我們可以考慮基于人工智能的手段去優(yōu)化CDF 的學習過程和冷熱數(shù)據(jù)學習的過程.本文的跳表結構并沒有針對多核特征去做優(yōu)化,未來可以結合多核的特性進一步思考.

審核編輯：湯梓紅