重刪環(huán)境下雙B-樹索引性能優(yōu)化研究

周 斌，曹鴻源

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

根據(jù)國際數(shù)據(jù)公司IDC[1]預(yù)測(cè)，2020年全球數(shù)據(jù)總量將會(huì)達(dá)到甚至超過40ZB[2].目前提出的重復(fù)數(shù)據(jù)刪除技術(shù)，雖然能在很大程度上節(jié)省系統(tǒng)的存儲(chǔ)空間，但是重復(fù)數(shù)據(jù)刪除系統(tǒng)的性能和擴(kuò)展性仍面臨著巨大的挑戰(zhàn)[3].同時(shí)，指紋索引的出現(xiàn)加快了檢索的速度和效率，但是隨著全球數(shù)據(jù)量呈現(xiàn)爆炸式增長，指紋數(shù)據(jù)量也隨之飛速增長.例如：存有800 TB大小的數(shù)據(jù)，假設(shè)切分得到的數(shù)據(jù)塊的平均大小為8KB，那么將至少產(chǎn)生2 TB的SHA-1(20Byte)指紋[4]，這些指紋數(shù)據(jù)量仍是非常巨大的.由于內(nèi)存存儲(chǔ)量有限，過多的指紋只能存放在磁盤中，隨著訪問磁盤次數(shù)增多，必然導(dǎo)致重復(fù)數(shù)據(jù)刪除系統(tǒng)的檢索性能下降.目前的索引機(jī)制研究按索引結(jié)構(gòu)分類，可分為：(1)哈希索引機(jī)制研究[5-7]，主要聚焦于哈希表.哈希表是一種數(shù)據(jù)結(jié)構(gòu)，具有快速寫入和讀取的優(yōu)點(diǎn).但哈希表仍存在一些不足之處，由于哈希表是基于數(shù)組結(jié)構(gòu)，如果哈希表被基本填滿，性能會(huì)下降得非常厲害；(2)樹型索引機(jī)制研究[8,9]，主要聚焦于B樹.B樹具有良好的擴(kuò)展性和插入刪除的性能，其中，優(yōu)化的B樹中，B-樹可以在非葉子節(jié)點(diǎn)結(jié)束查詢，B+樹具有良好的空間利用率，但是B樹不適合過大數(shù)量的數(shù)據(jù)索引，樹的高度過大會(huì)嚴(yán)重影響查詢速率；(3)位圖索引機(jī)制研究，主要聚焦于布隆過濾器.布隆過濾器主要用于識(shí)別一個(gè)數(shù)據(jù)塊或關(guān)鍵字是否存在于存儲(chǔ)容器中.但是布隆過濾器很大的缺點(diǎn)就是不能插入數(shù)據(jù)塊，也不能刪除已有數(shù)據(jù)塊.并且隨著容器中數(shù)據(jù)塊的增多，誤報(bào)率也將隨之變大.為了提高重復(fù)數(shù)據(jù)刪除系統(tǒng)的性能，本文在國內(nèi)外相關(guān)研究的基礎(chǔ)上，圍繞指紋索引結(jié)構(gòu)，提出一種基于雙B-樹索引檢索性能的優(yōu)化方案.

1 基于雙B-樹索引結(jié)構(gòu)

雙B-樹索引結(jié)構(gòu)是由兩棵樹結(jié)構(gòu)不同的B-樹構(gòu)成，如圖1所示：

(1)對(duì)于第一棵B-樹B-tree-1，根據(jù)B-樹的特點(diǎn)，優(yōu)化樹結(jié)構(gòu).為盡可能的減少B-樹的遍歷次數(shù)，增加了B-樹每個(gè)節(jié)點(diǎn)(磁盤頁)中的指紋數(shù)量，同時(shí)增加了節(jié)點(diǎn)分支的數(shù)目，從而使B-樹的高度更小，由此可以提高指紋的檢索效率.

(2)對(duì)于第二棵B-樹B-tree-2，是在B-樹的基礎(chǔ)上，結(jié)合了LRU(Least Recently Used)算法，設(shè)定B-tree-2樹的存儲(chǔ)數(shù)量為B-tree-1的1/m(m具體最優(yōu)值在實(shí)驗(yàn)中得到)，利用LRU的最近最少使用的思想，提高B-tree-2檢索命中率，從而提升了系統(tǒng)的檢索效率.

圖1 雙B-樹示意圖Fig.1 Double B-tree schematic diagram

1.1 B-tree-1

B-樹的高度決定著系統(tǒng)的讀取效率，在這里把B-tree-1設(shè)計(jì)成“矮扁平”形狀.如圖2所示，因?yàn)锽-樹的時(shí)間復(fù)雜度與樹的高度有關(guān)，樹越矮，時(shí)間復(fù)雜度越低.同時(shí)增加每個(gè)節(jié)點(diǎn)的指紋數(shù)量，在不影響樹的承載量的情況下，減少磁盤訪問的次數(shù)，從而提升了系統(tǒng)的讀取效率.

圖2 B-tree-1樹示意圖Fig.2 B-tree-1 schematic diagram

1.2 B-tree-2

在數(shù)據(jù)管理系統(tǒng)中，研究人員對(duì)數(shù)據(jù)庫索引技術(shù)的研究一直未曾停止過.就目前數(shù)據(jù)庫系統(tǒng)應(yīng)用需求來看，數(shù)據(jù)庫索引結(jié)構(gòu)優(yōu)化和提升的空間仍舊很大.在現(xiàn)有系統(tǒng)應(yīng)用中，Hash索引、二叉樹索引、B-樹索引和TRIE樹索引等是使用較為普遍的索引結(jié)構(gòu).由于B-樹的檢索速度快，且可以在非葉子節(jié)點(diǎn)處結(jié)束遍歷，并且B-樹也很適合改進(jìn)，因此，B-樹索引得到了廣泛的應(yīng)用.目前，存在的B+樹等，就是在B-樹的基礎(chǔ)上改進(jìn)而來的.

在實(shí)際應(yīng)用中，數(shù)據(jù)訪問一般是隨機(jī)的，且當(dāng)前訪問時(shí)間最近的數(shù)據(jù)，有可能在近段時(shí)間再次訪問.如果讓B-樹緩存中始終保留這些數(shù)據(jù)，那么可以大大減少外部存儲(chǔ)訪問的次數(shù)，進(jìn)而提高重復(fù)數(shù)據(jù)刪除的檢索性能.為此，本文設(shè)計(jì)中，在B-樹的基礎(chǔ)上加入了LRU算法.

LRU(Least Recently Used，最近最少使用)[10,11]算法是根據(jù)數(shù)據(jù)的歷史訪問記錄來清除數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高”.在由LRU算法優(yōu)化而來的算法中，LRU-2，MQ(2)，2Q三種算法，雖然都能提高數(shù)據(jù)查詢的命中率，但是其復(fù)雜度和付出的代價(jià)也相應(yīng)提高，4種算法對(duì)比如表1所示：

表1 LRU系列算法的對(duì)比

根據(jù)表1中的數(shù)據(jù)可以明顯看出，隨著命中率的提升，算法的復(fù)雜度和代價(jià)也相應(yīng)地提高，在此基礎(chǔ)上考慮，為了能夠提高B-tree-1的命中率且盡量減少復(fù)雜度，本文選擇了經(jīng)典的LRU算法.

在LRU算法設(shè)定中，計(jì)數(shù)器為命中的緩存計(jì)數(shù)，當(dāng)緩存空間不足，并且不需要清理數(shù)據(jù)的時(shí)候，通過遍歷所有的計(jì)數(shù)器，將最少使用的數(shù)據(jù)替換.LRU算法的弊端在于假如緩存空間和緩存的數(shù)據(jù)都較大，需要清除數(shù)據(jù)的時(shí)候，則需要遍歷所有計(jì)數(shù)器，就會(huì)造成比較嚴(yán)重的性能與資源消耗，導(dǎo)致檢索效率降低.

為達(dá)到高效的檢索性能，僅僅只有LRU算法的計(jì)數(shù)功能已經(jīng)不能滿足本文的需求，本文針對(duì)傳統(tǒng)的LRU算法進(jìn)行了改進(jìn)：

LRU自帶的計(jì)數(shù)功能雖然可以很好記錄最新訪問的數(shù)據(jù)，并使其插入或者調(diào)動(dòng)到鏈表的頭部，但是隨著B-tree-2中指紋數(shù)量的增加，遍歷所有計(jì)數(shù)器的時(shí)間也會(huì)增加，這給內(nèi)存開銷增大了壓力.鑒于此，假設(shè)在LRU中的鏈表中加入時(shí)間參數(shù)T，即，在時(shí)間T內(nèi)未被訪問，便被淘汰掉.這樣不僅保存了LRU算法原本的優(yōu)點(diǎn)，還可以和B-tree-2高度融合，適配了B-tree-2的需求.

B-tree-2的主要原理是，避免大量的檢測(cè)和計(jì)數(shù)器的遍歷所帶來的系統(tǒng)開銷，在這里設(shè)定一個(gè)時(shí)間參數(shù)T，每間隔一定時(shí)間T，檢測(cè)該節(jié)點(diǎn)的數(shù)據(jù)指紋有無被訪問，沒有則清除該節(jié)點(diǎn)釋放緩存，如圖3所示.為此，再為節(jié)點(diǎn)加入一個(gè)時(shí)間點(diǎn)t，用來標(biāo)記最近一次訪問的時(shí)間點(diǎn)，數(shù)據(jù)指紋一但在T時(shí)間內(nèi)被訪問，t就會(huì)自動(dòng)刷新到被訪問的時(shí)刻.因?yàn)闃錉钏饕腹?jié)點(diǎn)的存在，如果父節(jié)點(diǎn)未被訪問的時(shí)間大于設(shè)定的時(shí)間參數(shù)T，且此父節(jié)點(diǎn)下的子節(jié)點(diǎn)也在時(shí)間參數(shù)T內(nèi)未被訪問，那么父節(jié)點(diǎn)及其子節(jié)點(diǎn)才會(huì)從索引中全部淘汰.

圖3 B-tree-2樹示意圖Fig.3 B-tree-2 schematic diagram

算法中，引用了指紋訪問頻次以及最近一次操作時(shí)間，從而得出此指紋熱度值，如果一個(gè)指紋被引用的次數(shù)越高，并且被引用的時(shí)間越新，則這個(gè)指紋就會(huì)被長時(shí)間留在B-tree-2索引中，反之則會(huì)被釋放掉.

2 實(shí)驗(yàn)結(jié)果與分析

為了測(cè)試本文提出的基于雙B-樹的索引結(jié)構(gòu)算法的有效性和優(yōu)越性，本文通過實(shí)驗(yàn)得到DBIS算法與B-樹的寫入、讀取和刪除速度，并將實(shí)驗(yàn)結(jié)果進(jìn)行了比較和分析.

在模擬系統(tǒng)中使用可變長切分算法對(duì)文件進(jìn)行分塊處理，選用基于文件內(nèi)容進(jìn)行數(shù)據(jù)切分的CDC算法，每個(gè)數(shù)據(jù)塊設(shè)置為平均4kB.采用哈希算法是SHA-l算法，并且對(duì)于長度小于264位的消息，SHA-l會(huì)產(chǎn)生一個(gè)20個(gè)字節(jié)的信息，作為數(shù)據(jù)塊的指紋，識(shí)別數(shù)據(jù)塊.索引結(jié)構(gòu)選用傳統(tǒng)的B-樹索引結(jié)構(gòu)和雙B-樹索引結(jié)構(gòu).實(shí)驗(yàn)中m的取值為1/15，時(shí)間參數(shù)T的取值為0.15s.

2.1 寫入性能測(cè)試

實(shí)驗(yàn)開始先分別初始化B-樹和DBIS樹，接著將已經(jīng)通過重復(fù)數(shù)據(jù)刪除系統(tǒng)處理函數(shù)產(chǎn)生的數(shù)據(jù)指紋進(jìn)行寫入，同時(shí)，通過使用編譯器本身帶有的計(jì)時(shí)器作為系統(tǒng)時(shí)間計(jì)時(shí)器，并統(tǒng)計(jì)得出DBIS樹索引和B-樹索引在不同索引量的情況下，寫入操作分別所需要的時(shí)間.具體測(cè)試結(jié)果如圖4所示.

圖4 DBIS樹與B-樹插入性能對(duì)比圖Fig.4 DBIS and B-tree insertion performance comparison diagram

由圖4可見，DBIS樹在寫入性能上比基本的B-樹差，DBIS樹的復(fù)雜度要比B-樹相對(duì)較高.DBIS樹插入時(shí)同時(shí)要考慮兩棵樹的計(jì)算時(shí)間，B-tree-2在給B-tree-1傳遞消息的同時(shí)，B-tree-1要給B-tree-2一定消息回復(fù)，這導(dǎo)致了更多的時(shí)間消耗.

2.2 讀取性能測(cè)試

讀取性能測(cè)試是在已經(jīng)寫入100000條隨機(jī)選取的數(shù)據(jù)情況下進(jìn)行，同時(shí)通過編譯器自帶的計(jì)時(shí)器進(jìn)行計(jì)時(shí)操作，統(tǒng)計(jì)出DBIS樹索引和B-樹索引在不同指紋數(shù)量的情況下，讀取操作分別所需要的時(shí)間.測(cè)試分別采用隨機(jī)生成5000、10000、15000、20000條查詢條件，并測(cè)試DBIS樹索引和B-樹索引所需時(shí)間并比較，具體測(cè)試結(jié)果如圖5所示.

圖5 DBIS樹與B-樹讀取性能對(duì)比圖Fig.5 DBIS and B-tree reading performance comparison diagram

由圖5可見，DBIS樹具有較為良好的讀取性能，由于B-tree-2檢測(cè)命中率的提高，很大程度上節(jié)約了時(shí)間，而且B-tree-1的“矮扁平”的特點(diǎn)，減少了訪問次數(shù)，進(jìn)而也減少了檢索的時(shí)間，所以讀取性能相對(duì)于傳統(tǒng)B-樹應(yīng)用于內(nèi)存數(shù)據(jù)庫中的情況有較好的優(yōu)化和改善，并隨著讀取數(shù)據(jù)量的增加會(huì)有更明顯的提升.

2.3 刪除性能測(cè)試

刪除性能測(cè)試是在已經(jīng)寫入100000條隨機(jī)選取的數(shù)據(jù)情況下進(jìn)行，同時(shí)通過編譯器自帶的計(jì)時(shí)器進(jìn)行計(jì)時(shí)操作，統(tǒng)計(jì)得出DBIS樹索引和B-樹索引在不同指紋數(shù)量的情況下，刪除操作需要花費(fèi)的時(shí)間.測(cè)試分別采用隨機(jī)生成5000、10000、15000、20000條查詢條件，并測(cè)試DBIS樹索引和B-樹索引所需時(shí)間并比較，具體測(cè)試結(jié)果如圖6所示.

圖6 DBIS樹與B-樹刪除性能對(duì)比圖Fig.6 DBIS and B-tree deleting performance comparison diagram

由圖6可以得出，DBIS樹索引刪除操作要比B-樹索引操作更節(jié)約時(shí)間，能夠快速地定位到要?jiǎng)h除的對(duì)象，便能更快地刪除要?jiǎng)h除的對(duì)象.

通過以上的幾個(gè)模擬對(duì)比試驗(yàn)，可以得出：基于雙B-樹的索引結(jié)構(gòu)在內(nèi)存中保存熱指紋的特性，優(yōu)化了重復(fù)數(shù)據(jù)刪除系統(tǒng)的讀取和刪除性能.

3 結(jié)束語

當(dāng)前，重復(fù)數(shù)據(jù)刪除技術(shù)是一個(gè)研究熱點(diǎn)，企業(yè)界和學(xué)界對(duì)此技術(shù)的研究和改進(jìn)仍在繼續(xù)，而在重復(fù)數(shù)據(jù)刪除系統(tǒng)中，指紋索引的優(yōu)化對(duì)系統(tǒng)性能的提升起著尤為重要的作用.優(yōu)化的指紋索引可以減少因多次訪問磁盤給CPU帶來的額外開銷和消耗的大量時(shí)間，但是目前的指紋索引讀寫效率低下，特別是讀的性能相對(duì)較弱等.為了改進(jìn)以上不足，針對(duì)系統(tǒng)索引結(jié)構(gòu)的讀性能優(yōu)化方面，本文提出了基于雙B-樹的索引結(jié)構(gòu)檢索性能優(yōu)化方案.具體內(nèi)容如下：

(1)索引的優(yōu)化是對(duì)重復(fù)數(shù)據(jù)刪除系統(tǒng)性能提升的一個(gè)重要方向，通過對(duì)索引結(jié)構(gòu)等相關(guān)技術(shù)的深入研究，本文總結(jié)了當(dāng)前索引結(jié)構(gòu)的優(yōu)缺點(diǎn)，指出了索引結(jié)構(gòu)中讀性能處于瓶頸的狀態(tài)；

(2)本文提出的基于雙B-樹索引結(jié)構(gòu)，并將此索引結(jié)構(gòu)應(yīng)用到內(nèi)存中，旨在減少磁盤訪問次數(shù)，提高重復(fù)數(shù)據(jù)刪除系統(tǒng)的性能.詳細(xì)介紹了B-tree-1和B-tree-2實(shí)現(xiàn)思想和步驟，并在理論上說明了此索引結(jié)構(gòu)對(duì)提高系統(tǒng)讀取性能的有效性；

(3)改進(jìn)了LRU算法，在LRU算法中加入時(shí)間參數(shù)，提高了熱指紋的命中率，使其更適配于B-tree-2；

(4)最后與傳統(tǒng)的B-樹索引結(jié)構(gòu)進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明本文所設(shè)計(jì)的索引優(yōu)化方案，有效地提升了系統(tǒng)的讀取性能.