面向數據特征的內存跳表優化技術

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

近年來,伴隨著移動互聯網和大數據的熱潮,行業對數據處理能力,尤其是在線聯機事務處理能力(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 節將對跳表做詳細介紹.

Fig.1 Example of skiplist in ideal case

圖1 理想情況的跳表示例

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

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

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

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

Fig.2 Example of skiplist in worst case

圖2 最壞情況的跳表示例

本文的貢獻如下:

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

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

·跳表選型.本文基于合成數據和真實數據對標準跳表和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.基于伯努利實驗的跳表層數決策算法.

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

Fig.3 Example of searching node 7

圖3 查找結點7 的示例

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

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

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

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

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

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

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

(2)標準化:

(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):

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

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

估計:

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

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

算法2.cdf-list 的層數決策算法.

與算法1 中random 的方式相比,算法2 充分利用了數據的分布特征.算法2 的輸入為數據集個數N、數據集的累積分布函數CDF、待插入的key.輸出為待插入key 的層數level.首先,通過公式(3)計算出待插入key 在跳表中從小到大的排序位置location(第2 行),注意:如果location 的結果為小數,需要向上取整.為了創建出類似于圖1 的跳表結構,處在不同location 的key 的高度是可以被計算的(第3 行～第10 行).理想情況下,跳表中高度大于等于2 的key 對應的位置應該是21 的倍數,高度大于等于3 的key 對應的位置應該是22 的倍數,依此類推,高度大于等于k+1 的key 對應的高度應該是2k 的倍數.根據位置判定層數,實際上是通過判定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,這樣的結構在查詢過程中是不合理的.

Fig.6 Unsuited structure caused by CDF error

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

為了容忍位置估計的誤差,我們提出了容忍偏差的算法.首先,我們采用一個長度為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

算法3.構造bound-list 的層數數組.

例如包含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 估計誤差的層數決策算法.

算法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,預判location 為4,結合bound,對應層數為1.依此類推,插入跳表中所有結點.

3.3 Partition-list

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

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

算法5.Partition-list 的層數決策算法.

算法5 首先將partition-list 劃分成2p?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,我們把數據集分成23?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 所示.

Fig.7 Example of partition-based skiplist

圖7 基于分區的跳表示例

4 結合訪問熱度的跳表

4.1 Hot-list

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

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

算法6.Hot-list 的層數決策算法.

算法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.基于數據分布和熱度的層數決策算法.

4.3 總結對比

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

Table 1 Summary of algorithms

表1 算法對比總結

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

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

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

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

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

Table 2 Dataset

表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%的提升.

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

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

Fig.9 Performance influenced by the parameter of Zipfian distribution

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

圖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 會詳細介紹.

Fig.10 Performance influenced by dataset size with uniform distribution

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

Partition-list 算法的性能受參數p 的影響.圖11 展示了在221 數據集大小的均勻分布數據集下,參數p 對partition-list 的吞吐率影響.實驗結果表明,p 只有在一個合理的區間內,partition-list 的性能才會好,尤其是p 的值接近于log2(N)之后會發生急劇下降.我們給出了p 的一個經驗參考值:log2(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.一些不需要的高度原因導致了partitionlist 相對bound-list 的性能損失.

Fig.11 Performance influenced by parameter p

圖11 參數p 對性能的影響

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

Fig.12 Performance under real dataset

圖12 真實數據集合下的性能

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 幾乎沒有性能提升.

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

圖13 正態分布下方差對性能的影響

Fig.14 Performance influenced by the parameter of Zipfian distribution

圖14 齊夫分布下參數對性能的影響

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

Fig.15 Performance influenced by parameter h

圖15 參數h 對性能的影響

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

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

Fig.16 Performance under different Zipfian distribution dataset

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

我們可以發現,在參數為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 的學習過程和冷熱數據學習的過程.本文的跳表結構并沒有針對多核特征去做優化,未來可以結合多核的特性進一步思考.

審核編輯：湯梓紅