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

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

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

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

Fig.1 Example of skiplist in ideal case

圖1 理想情況的跳表示例

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

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

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

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

Fig.2 Example of skiplist in worst case

圖2 最壞情況的跳表示例

本文的貢獻(xiàn)如下:

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

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

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

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

1 預(yù)備知識

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

1.1 跳 表

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

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

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

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

Fig.3 Example of searching node 7

圖3 查找結(jié)點7 的示例

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

Fig.4 Example of insert node 8 in skiplist

圖4 插入結(jié)點8 的示例

Fig.5 Example of delete node 2 in skiplist

圖5 刪除結(jié)點2 的示例

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

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

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

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

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

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

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

(2)標(biāo)準(zhǔn)化:

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

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

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

2 相關(guān)工作

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

·索引技術(shù).

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

·密度估計.

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

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

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

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

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

(3)另外,在數(shù)據(jù)挖掘領(lǐng)域存在大量采用機(jī)器學(xué)習(xí)的手段學(xué)習(xí)位置敏感的哈希函數(shù)用于構(gòu)建近似最近鄰索引的工作,例如文獻(xiàn)[36,37].

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

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

3.1 Cdf-list

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

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

,公式(3)可以預(yù)判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 的結(jié)果為小數(shù),需要向上取整.為了創(chuàng)建出類似于圖1 的跳表結(jié)構(gòu),處在不同location 的key 的高度是可以被計算的(第3 行～第10 行).理想情況下,跳表中高度大于等于2 的key 對應(yīng)的位置應(yīng)該是21 的倍數(shù),高度大于等于3 的key 對應(yīng)的位置應(yīng)該是22 的倍數(shù),依此類推,高度大于等于k+1 的key 對應(yīng)的高度應(yīng)該是2k 的倍數(shù).根據(jù)位置判定層數(shù),實際上是通過判定location 的二進(jìn)制數(shù)字的末尾有幾個零:如果有k 個零,那么高度則為k+1.例如,處在第8(二進(jìn)制1000)個位置的數(shù)據(jù)高度應(yīng)該是4層.下面用一個例子對跳表創(chuàng)建過程進(jìn)行說明.

例1:為便于理解,這里我們假設(shè)數(shù)據(jù)服從均勻分布,數(shù)據(jù)集是包含12 個元素的集合(真實數(shù)據(jù)集會很大).數(shù)據(jù)集為{5,4,3,2,1,6,7,8,9,10,12,11}.初始時,cdf-list 為空,插入元素5 的時候,雖然當(dāng)前并沒有插入1,2,3,4 這4 個結(jié)點,但可以預(yù)判元素5 的位置.因為元素5 的cdf 值為5/12,元素5 應(yīng)該所處的位置為5(二進(jìn)制101),對應(yīng)的跳表高度為1.依此類推,可以創(chuàng)建出接近于圖1 所示的跳表結(jié)構(gòu).

3.2 Bound-list

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

Fig.6 Unsuited structure caused by CDF error

圖6 CDF 誤差導(dǎo)致的不合理結(jié)構(gòu)

為了容忍位置估計的誤差,我們提出了容忍偏差的算法.首先,我們采用一個長度為N 的數(shù)組,該數(shù)組預(yù)先記錄理想情況下每個位置的元素的高度.算法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 頭結(jié)點.初始設(shè)置步長為1(第4 行),將level_array 中每個元素累計加1(第6 行～第8 行).然后步長step 變?yōu)?,偶數(shù)位置的level_array 數(shù)值加1.依此類推,step 每次乘以2(第9 行),直到step

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

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

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

算法4 與算法2 類似,都是根據(jù)cdf 值決定待插入key 的層數(shù).不同的是,算法4 結(jié)合bound 區(qū)間去判定層數(shù),容忍了估計導(dǎo)致的誤差.算法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ù)組位置的值設(shè)置為1,從而保證在插入附近連續(xù)的key 時,key 的高度不一樣.

例2:類似于例1 的均勻數(shù)據(jù)集為{5,4,3,2,1,6,7,8,9,10,12,11}.初始時,bound-list 為空,通過算法3 構(gòu)建出level_array.構(gòu)建的level_array 數(shù)組為{4,1,2,1,3,1,2,1,4,1,2,1,3}.插入元素5 的時候,預(yù)判元素5 的cdf 值為5/12,元素5 應(yīng)該所處的位置為5.假設(shè)bound 為1,則我們從level_array[5?1]到level_array[5+1]之間選取最大值3,即get_level(5)=3.插入5 之后,需要修改層數(shù)數(shù)組為

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

3.3 Partition-list

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

類似bound-list 的方式,我們通過調(diào)用算法3 的函數(shù)build_array(2p?1)構(gòu)建長度為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 類似的隨機(jī)方法計算層數(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.假設(shè)p=3,我們把數(shù)據(jù)集分成23?1 個分區(qū).當(dāng)key=6 時,partition=3,對應(yīng)的高度get_level(5)=1+(6?3)=4.當(dāng)key=5 時,此時partition=3,partition3 內(nèi)已經(jīng)有一個高度大于3 的key,所以key=5 對應(yīng)的高度應(yīng)該通過random_level(3)生成一個高度不大于3 的層數(shù),如圖7 所示.

Fig.7 Example of partition-based skiplist

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

4 結(jié)合訪問熱度的跳表

4.1 Hot-list

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

我們根據(jù)歷史數(shù)據(jù)的訪問頻率,把數(shù)據(jù)集中訪問頻率較高的2h?1 個數(shù)據(jù)判定為熱度數(shù)據(jù).我們通過算法6,想構(gòu)建一個最上面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.假設(shè)1,2,3,4,5 這5 個key 被頻繁訪問,也就是屬于熱度數(shù)據(jù).我們設(shè)置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 可以結(jié)合優(yōu)化成下述算法7,同時,結(jié)合partition 方案和冷熱分層的方案進(jìn)行設(shè)計,原理類似便不展開介紹.原則上,bound-list 同樣可以和hot-list 進(jìn)行方案結(jié)合,但我們認(rèn)為,partition-list的適用性比bound-list 要好(bound-list 需要知道數(shù)據(jù)集的大小),因此我們只考慮partition-list 和hot-list 結(jié)合的方案.

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

4.3 總結(jié)對比

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

Table 1 Summary of algorithms

表1 算法對比總結(jié)

5 實驗及分析

5.1 硬件環(huán)境

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

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

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

(1)均勻分布:我們基于均勻分布隨機(jī)數(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)對算法性能進(jìn)行評測.數(shù)據(jù)集大小分別為334 863 和1 134 890,每個數(shù)據(jù)項代表的是分別是YouTube 用戶id 和Amazon 用戶的id.

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

Table 2 Dataset

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

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

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

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

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

(2)但在方差為1 和齊夫分布參數(shù)為0.7 時的數(shù)據(jù)集下,每個算法的性能都略有增加,這是因為實驗中的跳表不容許重復(fù)key 出現(xiàn),上述兩個參數(shù)情況下,會導(dǎo)致過多key 重復(fù),導(dǎo)致跳表結(jié)點數(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ù)集大小對不同跳表的查詢吞吐率性能的影響,橫軸對應(yīng)的數(shù)據(jù)集大小,縱軸是查詢吞吐率的性能;圖10(b)反映的是cdf-list,bound-list,partition-list 相對skiplist 的吞吐率性能比.實驗結(jié)果反映3 點.

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

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

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

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 的吞吐率影響.實驗結(jié)果表明,p 只有在一個合理的區(qū)間內(nèi),partition-list 的性能才會好,尤其是p 的值接近于log2(N)之后會發(fā)生急劇下降.我們給出了p 的一個經(jīng)驗參考值:log2(N)?5.此外可以看出,partition-list的吞吐率在p=17 時和bound-list 性能接近.由于Partition-list 對于數(shù)據(jù)集的大小信息未知,這會導(dǎo)致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.一些不需要的高度原因?qū)е铝藀artitionlist 相對bound-list 的性能損失.

Fig.11 Performance influenced by parameter p

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

圖12 是真實數(shù)據(jù)集Amazon 和YouTube 的實驗結(jié)果.實驗結(jié)果表明:(1)算法在小數(shù)據(jù)Amazon 集合下性能加速不明顯,在大數(shù)據(jù)YouTube 下性能加速很明顯,這與圖10 的結(jié)果一致;(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é)果

本節(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ù)集下的性能對比圖.實驗結(jié)果表明:(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 對性能的影響

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

此外,為了反映熱度數(shù)據(jù)的頻度特征對不同跳表算法性能的影響,我們采用服從齊夫分布、參數(shù)分別為0.7和0.9 的兩個分布分別模擬熱度數(shù)據(jù),圖16 展示了不同算法的性能結(jié)果,其實參數(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 結(jié)論及展望

本文重點研究數(shù)據(jù)庫跳表索引優(yōu)化這一經(jīng)典問題.針對跳表由于隨機(jī)性導(dǎo)致的不穩(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 也能獲取理想的性能提升.實驗結(jié)果表明,partition-list 可以獲得最大60%的性能提升.此外,hot-list 可以用作在冷熱數(shù)據(jù)明顯的場景,比如類似“雙十一”熱度商品大促的情形.以本文的partiton-list 算法為代表的設(shè)計方案,可以給未來的科研人員和開發(fā)人員提供一個新的設(shè)計方向.

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

審核編輯：湯梓紅