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

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

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

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

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

Fig.1 Example of skiplist in ideal case

圖1 理想情況的跳表示例

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

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

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

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

Fig.2 Example of skiplist in worst case

圖2 最壞情況的跳表示例

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

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

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

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

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

1 預(yù)備知識(shí)

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

1.1 跳 表

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

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

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

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

Fig.3 Example of searching node 7

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

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

Fig.4 Example of insert node 8 in skiplist

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

Fig.5 Example of delete node 2 in skiplist

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

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

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

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

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

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

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

(1)對(duì)稱(chēng)性:φ(u)=φ(?u);

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

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

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

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

2 相關(guān)工作

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

·索引技術(shù).

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

·密度估計(jì).

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

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

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

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

(2)Pavlo[32]和Chaudhuri[33]提出了人工智能的方法還可以用于優(yōu)化數(shù)據(jù)庫(kù)運(yùn)維的難度,降低DBA 的難度.代表性工作主要是卡耐基梅隆大學(xué)提出的OtterTune[34]和阿里巴巴達(dá)摩院的iBTune[35],iBTune 被大規(guī)模應(yīng)用在阿里巴巴線上系統(tǒng)中,主要用于數(shù)據(jù)庫(kù)緩存大小的自動(dòng)設(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),接下來(lái)我們將介紹3 個(gè)優(yōu)化算法.

3.1 Cdf-list

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

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

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

估計(jì):

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

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

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

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

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

3.2 Bound-list

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

Fig.6 Unsuited structure caused by CDF error

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

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

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

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

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

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

例2:類(lèi)似于例1 的均勻數(shù)據(jù)集為{5,4,3,2,1,6,7,8,9,10,12,11}.初始時(shí),bound-list 為空,通過(guò)算法3 構(gòu)建出level_array.構(gòu)建的level_array 數(shù)組為{4,1,2,1,3,1,2,1,4,1,2,1,3}.插入元素5 的時(shí)候,預(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,對(duì)應(yīng)層數(shù)為1.依此類(lèi)推,插入跳表中所有結(jié)點(diǎn).

3.3 Partition-list

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

類(lèi)似bound-list 的方式,我們通過(guò)調(diào)用算法3 的函數(shù)build_array(2p?1)構(gòu)建長(zhǎng)度為2p的partition_array 數(shù)組.Partition-list的偽代碼如算法5.

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

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

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

Fig.7 Example of partition-based skiplist

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

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

4.1 Hot-list

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

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

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

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

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

4.2 Mix-list

上述算法partition-list 和hot-list 可以結(jié)合優(yōu)化成下述算法7,同時(shí),結(jié)合partition 方案和冷熱分層的方案進(jìn)行設(shè)計(jì),原理類(lèi)似便不展開(kāi)介紹.原則上,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é)對(duì)比

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

Table 1 Summary of algorithms

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

5 實(shí)驗(yàn)及分析

5.1 硬件環(huán)境

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

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

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

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

(2)正態(tài)分布:采用正態(tài)分布生成器生成5 個(gè)不同方差(均值為10、方差分別為1,3,5,7,9)、大小都為221的數(shù)據(jù)集,因?yàn)榉讲罘从沉藬?shù)據(jù)的稀疏程度,方差越大,數(shù)據(jù)越稀疏;

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

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

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

Table 2 Dataset

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

5.3 CDF優(yōu)化實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

Fig.10 Performance influenced by dataset size with uniform distribution

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

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

Fig.11 Performance influenced by parameter p

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

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

Fig.12 Performance under real dataset

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

5.4 熱度數(shù)據(jù)實(shí)驗(yàn)結(jié)果

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

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

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

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

Fig.14 Performance influenced by the parameter of Zipfian distribution

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

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

Fig.15 Performance influenced by parameter h

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

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

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

Fig.16 Performance under different Zipfian distribution dataset

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

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

6 結(jié)論及展望

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

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

審核編輯：湯梓紅