周 斌,李 波

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

基于時序參數(shù)的重復(fù)數(shù)據(jù)刪除索引優(yōu)化技術(shù)研究

周 斌,李 波

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

針對系統(tǒng)中存在的索引檢索效率問題，提出了一種基于時序參數(shù)的快速索引優(yōu)化算法，該算法通過時間參數(shù)和序數(shù)參數(shù)獲取數(shù)據(jù)塊的熱度值，將高熱度值的數(shù)據(jù)塊指紋組合成了一個高優(yōu)先度的快速索引.快速索引與主索引組成了重復(fù)數(shù)據(jù)刪除中的兩層索引結(jié)構(gòu)，從而提高了系統(tǒng)的檢索性能.通過實(shí)驗(yàn)驗(yàn)證了基于時序參數(shù)的索引優(yōu)化算法的優(yōu)越性.

重復(fù)數(shù)據(jù)刪除；索引優(yōu)化；時序參數(shù)

據(jù)國際數(shù)據(jù)公司(IDC)統(tǒng)計，2009年的全球數(shù)據(jù)總量為0.8ZB，而到2010年底，全球數(shù)據(jù)總量已經(jīng)增長到1.2ZB，2011年，全球數(shù)據(jù)總量達(dá)到1.82ZB，并且數(shù)據(jù)總量還將繼續(xù)高速增長.為了應(yīng)對信息量的不斷增長，重復(fù)數(shù)據(jù)刪除作為一種較好的處理重復(fù)數(shù)據(jù)的方式，能夠保證存儲系統(tǒng)中數(shù)據(jù)塊的惟一性，從而完成重復(fù)數(shù)據(jù)的檢索和消除.隨著系統(tǒng)容量的不斷擴(kuò)大，重復(fù)刪除系統(tǒng)面臨新問題：即隨著索引體積不斷增大，已無法完整存放在內(nèi)存中.為了將新存入的數(shù)據(jù)特征值和已保存的數(shù)據(jù)特征值進(jìn)行比較，需要通過系統(tǒng)索引進(jìn)行檢索，從而帶來大量的硬盤訪問開銷.由于硬盤的訪問速度嚴(yán)重滯后，索引檢索的效率降低，開銷增大.

面對重復(fù)數(shù)據(jù)刪除系統(tǒng)的檢索瓶頸，本文主要針對重復(fù)數(shù)據(jù)刪除系統(tǒng)的索引進(jìn)行優(yōu)化，提出了一種基于時序參數(shù)的重復(fù)數(shù)據(jù)刪除索引優(yōu)化算法.該算法是一種基于數(shù)據(jù)塊熱度值的高優(yōu)先度的快速索引算法，通過使用兩層索引檢索的方式優(yōu)化索引檢索的性能.最后，本文對索引優(yōu)化算法的性能進(jìn)行了測試，驗(yàn)證了該索引優(yōu)化算法的優(yōu)越性.

1 相關(guān)研究工作

重復(fù)數(shù)據(jù)刪除索引作為制約系統(tǒng)性能的重要環(huán)節(jié)，一直是國內(nèi)外專家研究的重點(diǎn).目前被廣泛使用的重復(fù)數(shù)據(jù)刪除索引主要有：DDFS Index[1,2]、Sparse Index[3]和Extreme Binning[4]等.

DDFS是美國普林斯頓大學(xué)提出的一種針對海量數(shù)據(jù)情況下的數(shù)據(jù)指紋檢索技術(shù).DDFS認(rèn)為應(yīng)當(dāng)將數(shù)據(jù)作為一個整體來看待，同一數(shù)據(jù)的不同數(shù)據(jù)塊很可能被先后存儲或使用.因此，DDFS使用一種定長的容器來存放同一數(shù)據(jù)塊及其指紋，保證這些數(shù)據(jù)塊的集中存放，當(dāng)DDFS讀取某一個數(shù)據(jù)塊的指紋時，會讀取該數(shù)據(jù)塊所在容器的所有指紋.如果該容器中其他數(shù)據(jù)塊接下來被讀取，就能直接在內(nèi)存中進(jìn)行比較，以減少系統(tǒng)的I/O開銷.同時，DDFS將Bloom Filter[5]引入到主索引中，并利用數(shù)據(jù)的局部性原理減少了系統(tǒng)索引檢索開銷.但由于DDFS的Bloom Filter直接構(gòu)建在主索引上，受制于Bloom Filter在刪除和更新上的缺陷，DDFS的更新較為困難.

Sparse Index是由Lillibridge等人在2009年提出的一種稀疏矩陣抽樣索引.通過將數(shù)據(jù)塊組合為數(shù)據(jù)段，并對數(shù)據(jù)段中的哈希值進(jìn)行抽樣，形成稀疏索引.Sparse Index本質(zhì)上是一種局部數(shù)據(jù)重復(fù)性檢測，雖然能提高系統(tǒng)的處理效率，但由于缺乏全局性的數(shù)據(jù)判斷，系統(tǒng)的重刪率不高.

Extreme Binning是由Bhagwat等人在2009年提出的一種基于分層思想的相似性檢索.它將相似的文件塊集中起來，將文件通過滑動窗口分塊技術(shù)分成數(shù)據(jù)塊，使用哈希函數(shù)求出這些數(shù)據(jù)塊的對應(yīng)指紋，然后從中選出這個文件的具有代表性的關(guān)鍵數(shù)據(jù)塊指紋；接著，將關(guān)鍵數(shù)據(jù)塊的指紋組合成一個常駐內(nèi)存的體積較小的主要索引.而剩下的數(shù)據(jù)塊指紋則組成存放于此盤中的二級索引.Extreme Binning的最大特點(diǎn)是將每個文件的硬盤訪問次數(shù)降低到了一次.與Sparse Index類似，由于Extreme Binning使用了數(shù)據(jù)空間的局部性及相似性特征，系統(tǒng)的重復(fù)數(shù)據(jù)刪除被局限在局部刪除，因此Extreme Binning的重刪率不高.

2 基于時序參數(shù)的索引優(yōu)化技術(shù)

為解決系統(tǒng)檢索瓶頸，提高索引檢索在內(nèi)存中的命中率，本文構(gòu)建了一種基于時序參數(shù)的索引優(yōu)化技術(shù)，即快速索引.

2.1 熱度值的計算

為了實(shí)現(xiàn)快速索引的高命中率，快速索引中存放的應(yīng)該是能在接下來反復(fù)被檢索的高價值的數(shù)據(jù)塊的指紋.系統(tǒng)中需要一種衡量數(shù)據(jù)價值的參數(shù)，用于判斷哪些數(shù)據(jù)是高價值數(shù)據(jù).為了實(shí)現(xiàn)這種價值判斷，需要使用系統(tǒng)清理中引入的序數(shù)參數(shù)Cites和時間參數(shù)Time.

重復(fù)數(shù)據(jù)刪除索引中用于標(biāo)明每個數(shù)據(jù)塊的引用次數(shù)的參數(shù)，被稱為序數(shù)參數(shù).重復(fù)數(shù)據(jù)刪除索引中用于標(biāo)明每個數(shù)據(jù)塊的最后訪問時間的參數(shù)，被稱為時間參數(shù).重復(fù)數(shù)據(jù)刪除系統(tǒng)中，數(shù)據(jù)塊在第t期的熱度值表示該數(shù)據(jù)塊在時間范圍t內(nèi)的系統(tǒng)數(shù)據(jù)價值，該值記為Hotkeyt.

在重復(fù)數(shù)據(jù)刪除系統(tǒng)中，一個數(shù)據(jù)塊的熱度值越高，則其數(shù)據(jù)價值越高.高熱度值數(shù)據(jù)塊擁有如下特征：在系統(tǒng)中被反復(fù)引用、最近多次被使用等.由于系統(tǒng)擁有時間局部性，即如果一個數(shù)據(jù)塊正在被訪問，那么它在近期很可能還會被訪問.因此，系統(tǒng)能通過熱度值找出當(dāng)期被頻繁訪問的數(shù)據(jù)塊，依據(jù)時間局部性原理，這些數(shù)據(jù)塊在下一期中也很可能被頻繁訪問，因此應(yīng)該將這些高熱度值的數(shù)據(jù)塊的指紋放入快速索引中.

考慮到數(shù)據(jù)塊的熱度值不應(yīng)是固定不變的，應(yīng)該是動態(tài)的、隨時間和具體訪問情況變化的，因此，數(shù)據(jù)塊的熱度值應(yīng)該是在系統(tǒng)的使用過程中積累并實(shí)時生成的，定義如下：

(1)

公式(1)是該數(shù)據(jù)塊在未考慮歷史影響的條件下在第(t+1)期的熱度值，t表示系統(tǒng)運(yùn)行的期數(shù)(每期都會重新生成快速索引)，Hotkeyt+1表示快速索引第(t+1)期某數(shù)據(jù)塊的熱度值，Cites為該數(shù)據(jù)塊的序數(shù)參數(shù)值，Time為該數(shù)據(jù)塊的時間參數(shù)值，Size為該數(shù)據(jù)塊的大小，Hotkeyt為該數(shù)據(jù)塊的上期熱度值，C1和C2為給定的經(jīng)驗(yàn)常數(shù).

(1+Cites)為該數(shù)據(jù)塊的序數(shù)參數(shù)對于熱度值的影響因子，表明不同數(shù)據(jù)塊的不同引用次數(shù)對于數(shù)據(jù)塊熱度值的影響.由于系統(tǒng)存在局部性原理，因此數(shù)據(jù)塊的Cites越大，熱度值也應(yīng)越大.同時，由于當(dāng)期Cites為0的數(shù)據(jù)塊并不會被當(dāng)期清理，因此這些數(shù)據(jù)塊也應(yīng)該擁有對應(yīng)的熱度值.在計算熱度值時，使用(1+Cites)而不是直接使用Cites，能避免直接使用Cites參數(shù)導(dǎo)致的歸零問題，保證所有的數(shù)據(jù)塊都有可能被加入到快速索引中.

但是，如果簡單地使用Hotkeyt+1來表示該數(shù)據(jù)塊在第(t+1)期的熱度值就難免會發(fā)生抖動.為了減少抖動，避免高熱度數(shù)據(jù)在某一期中的意外情況，本文引入一個熱度歷史系數(shù)λ.λ表示上一期的熱度值在當(dāng)期熱度值計算中所占的比重.因此在Hotkeyt+1中加入熱度歷史系數(shù)λ，就得到了完整的第(t+1)期的熱度值：

(2)

2.2 基于時序參數(shù)的快速索引

基于數(shù)據(jù)塊熱度值的定義，根據(jù)公式(2)，主索引對應(yīng)的每個數(shù)據(jù)塊都能求出在某一期中的熱度值，并將這些熱度值按順序排列起來.

將主索引中熱度值從大到小排列中的前N(N為指定的快速索引的尺寸)個指紋組合成一個新的小規(guī)模的高優(yōu)先度索引稱為快速索引，其中N的取值應(yīng)當(dāng)依賴于數(shù)據(jù)塊的數(shù)量以及內(nèi)存的容量.由于這個快速索引中存放的都是滿足在系統(tǒng)中被反復(fù)引用、最近多次使用等條件的數(shù)據(jù)塊指紋，依據(jù)數(shù)據(jù)局部性原理，這些數(shù)據(jù)塊在系統(tǒng)接下來的運(yùn)行中也將被多次使用，從而保證了快速索引的高命中率.

當(dāng)N的取值增大時，即快速索引的容量增大，快速索引的命中率也將顯著提高，但同時會增加快速索引的檢索開銷；當(dāng)N的取值減小時，即快速索引的容量縮小，快速索引的命中率將有所降低.因此，當(dāng)N過大或過小時，都會使得快速索引的性能降低，甚至失去作用.為了充分發(fā)揮快速索引的作用，必須根據(jù)重復(fù)數(shù)據(jù)刪除系統(tǒng)的情況，在保證命中率的前提下，確定N的合理取值，這樣才能提高系統(tǒng)的整體性能.

引入快速索引后的系統(tǒng)索引檢索流程如圖1所示，新數(shù)據(jù)塊的指紋將首先在快速索引中進(jìn)行檢索，如果在快速索引中檢索成功，則用檢索到的指紋的指針代替數(shù)據(jù)塊，并刪除新數(shù)據(jù)塊；如果在快速索引中檢索失敗，則回到主索引進(jìn)行二次檢索.

圖1 基于快速索引的檢索流程Fig.1 Retrieval process based on fast index

2.3 快速索引的更新

數(shù)據(jù)塊的熱度值是隨著期數(shù)t不斷變化的，因此，為了保證快速索引始終能夠適應(yīng)重復(fù)數(shù)據(jù)刪除系統(tǒng)的實(shí)時需求，要對快速索引進(jìn)行更新操作，將當(dāng)期的高熱度數(shù)據(jù)塊的指紋加入快速索引中，同時清理熱度值降低后不符合要求的數(shù)據(jù)塊指紋.

重復(fù)數(shù)據(jù)刪除系統(tǒng)的運(yùn)行有周期性規(guī)律，可以按照工作強(qiáng)度分為忙時和閑時.當(dāng)系統(tǒng)處于忙時狀態(tài)，重復(fù)數(shù)據(jù)刪除系統(tǒng)不進(jìn)行清理和更新，而是通過更新Cites參數(shù)和Time參數(shù)對需要清理的數(shù)據(jù)塊進(jìn)行標(biāo)記，并為熱度值的計算積累參數(shù)，從而節(jié)省CPU與存儲空間.當(dāng)系統(tǒng)處于閑時狀態(tài)，重復(fù)數(shù)據(jù)刪除系統(tǒng)將執(zhí)行清理，計算所有數(shù)據(jù)塊的熱度值，同時依據(jù)新的熱度值重新生成快速索引，充分利用系統(tǒng)的CPU與存儲資源.

3 快速索引的改進(jìn)

如圖1中的快速索引的檢索流程，在包含快速索引的兩層索引檢索中，新的數(shù)據(jù)塊指紋將優(yōu)先在快速索引中進(jìn)行檢索，當(dāng)快速索引中檢索未命中時，返回主索引進(jìn)行檢索.用t1來表示快速索引的平均檢索開銷，t2為主索引的平均檢索開銷，快速索引中的命中率為n，則包含快速索引的兩層索引檢索平均開銷Ta為：

Ta=nt1+(1-n)t2,

(3)

又由于在本系統(tǒng)中，

t2=30t1.

(4)

將式(4)帶入式(3)中得：Ta≤t2，即包含快速索引的兩層索引檢索平均開銷小于主索引.因此，包含快速索引的兩層索引檢索的平均性能要優(yōu)于主索引.

當(dāng)數(shù)據(jù)塊指紋在快速索引中檢索未命中時，兩層索引檢索的平均開銷Tb為：

Tb=t3+t2,

(5)

其中t3為完整檢索快速索引的開銷，在本系統(tǒng)實(shí)驗(yàn)環(huán)境中有：

t3≈3t1,

(6)

為了減少這種快速索引未命中時的開銷，本文將Bloom Filter引入到快速索引中，其未命中時平均檢索時間變?yōu)門b，則：

(7)

其中tq為快速索引Bloom Filter檢索時間，且在實(shí)驗(yàn)環(huán)境中：

(8)

即在快速索引中加入Bloom Filter后，能明顯提升快速索引未命中時兩層索引檢索的效率，改善重復(fù)數(shù)據(jù)刪除系統(tǒng)的用戶體驗(yàn)，其兩層索引的整體平均檢索時間為：

(1-Ps)ta+t2].

(9)

4 性能測試與分析

本節(jié)主要測試快速索引的大小為何值時，系統(tǒng)擁有最高的檢索效率.實(shí)驗(yàn)著重測試在不同大小的快速索引的情況下，新文件加入已運(yùn)行的重復(fù)數(shù)據(jù)刪除系統(tǒng)所花費(fèi)的時間.

首先將重復(fù)數(shù)據(jù)刪除系統(tǒng)存儲空間清空，接著存儲500 MB的數(shù)據(jù)庫文件；然后，按照快速索引占主索引大小的5%、10%、15%，即N=5%、N=10%、N=15%分別生成快速索引，并進(jìn)行后續(xù)實(shí)驗(yàn).從被選取的數(shù)據(jù)庫文件集中分別選10,20,…,100MB的數(shù)據(jù)庫文件，見表1，分別通過3種包含不同大小快速索引的兩層索引系統(tǒng)以及主索引系統(tǒng)，將其存入重復(fù)數(shù)據(jù)刪除系統(tǒng)中，觀察并記錄不同索引條件下的重復(fù)數(shù)據(jù)刪除系統(tǒng)的處理時間.

表1 快速索引性能測試

如表1所示，當(dāng)N=5%時，快速索引帶來的存儲及檢索的額外開銷較小，根據(jù)第2部分中提及的N的大小對于快速索引命中率的影響，此時快速索引檢索的命中率不高，導(dǎo)致系統(tǒng)檢索效率不穩(wěn)定.

當(dāng)N=15%時，快速索引帶來的存儲及檢索的額外開銷較大，同時快速索引的命中率有所提升.在這種情況下，系統(tǒng)檢索的性能較為穩(wěn)定，但效率不是最優(yōu).

當(dāng)N=10%時，快速索引帶來的存儲及檢索的額外開銷較為適中，實(shí)驗(yàn)中系統(tǒng)檢索的穩(wěn)定性接近N=15%，而效率優(yōu)于N=5%和N=15%.

在實(shí)驗(yàn)環(huán)境下，當(dāng)N=5%時，包含快速索引的兩層索引的檢索效率較單純的主索引檢索提高了16%；當(dāng)N=10%時，檢索效率提高了20%；當(dāng)N=15%時，檢索效率提高了18%.因此，當(dāng)快速索引的大小為主索引的10%(N=10%)時，包含快速索引的兩層索引的性能為最優(yōu).

5 總結(jié)

面對系統(tǒng)存儲壓力不斷增大的現(xiàn)狀，重復(fù)數(shù)據(jù)刪除系統(tǒng)需要解決系統(tǒng)索引檢索效率的問題.為此，本文通過在索引中引入時序參數(shù)，并依據(jù)數(shù)據(jù)塊的熱度值構(gòu)建了一種包含快速索引的兩層索引.實(shí)驗(yàn)結(jié)果證明基于時序參數(shù)的重復(fù)數(shù)據(jù)刪除索引能提供高效的索引檢索效率.

[1] Zhu B, Li K, Patterson H. Avoiding the disk bottleneck in the data domain deduplication file system[C]//USENIX. Proceedings of the 6th USENIX Conference on File and Storage Technologies (FAST′08). San Jose: USENIX, 2008:269-282.

[2] Jain R, Rawat M, Jain S. Data optimization techniques using bloom filter in big data[J]. International Journal of Computer Applications, 2016, 142(3):23-27.

[3] Lillibridge M, Eshghi K, Bhagwat D, et al. Sparse indexing: large scale, inline deduplication using sampling and locality[C]//USENIX. Proceedings of the 7th USENIX Conference on File and Storage Technologies(FAST′09). San Francisco: USENIX, 2009:111-123.

[4] Bhagwat D, Eshghi K, Long D D E, et al. Extreme binning: scalable, parallel deduplication for chunk-based file backup[C]// IEEE/ACM. Proceedings of the 17th IEEE/ACM International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS′09). London: ACM, 2009:1-9.

[5] Zhang P, Huang P, He X, et al. Resemblance and mergence based indexing for high performance data deduplication[J]. Journal of Systems and Software, 2017, 128(6):11-24.

The Research of Data Deduplication Index Optimization Based on Time and Cites Parameters

ZhouBin，LiBo

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

A fast index optimization algorithm based on time and cites parameters was proposed for the efficiency of index retrieval. It obtained the hot values of data chunks through the time and cites parameters and then the fingerprints of data chunks with high hot values were combined to a fast index with high priority. Two layer index was formed with the fast index and the main index which improved the retrieval performance of the system. Finally, the advantages of the index optimization algorithm based on time and cites parameters were verified by experiments.

data deduplication; index optimization; time and cites parameters

2017-02-17

周 斌(1971-)，男，副教授，博士，研究方向：大數(shù)據(jù)存儲與處理，E-mail：binzhou@mail.scuec.edu.cn

湖北省自然科學(xué)基金資助項(xiàng)目(2016CFB650)

TP311

A

1672-4321(2017)02-0133-05