周 斌,李 波

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

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

周 斌,李 波

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

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

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

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

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

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

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

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

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

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

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

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

2.1 熱度值的計(jì)算

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

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

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

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

(1)

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

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

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

(2)

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

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

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

當(dāng)N的取值增大時(shí)，即快速索引的容量增大，快速索引的命中率也將顯著提高，但同時(shí)會(huì)增加快速索引的檢索開(kāi)銷；當(dāng)N的取值減小時(shí)，即快速索引的容量縮小，快速索引的命中率將有所降低.因此，當(dāng)N過(guò)大或過(guò)小時(shí)，都會(huì)使得快速索引的性能降低，甚至失去作用.為了充分發(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í)時(shí)需求，要對(duì)快速索引進(jìn)行更新操作，將當(dāng)期的高熱度數(shù)據(jù)塊的指紋加入快速索引中，同時(shí)清理熱度值降低后不符合要求的數(shù)據(jù)塊指紋.

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

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

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

Ta=nt1+(1-n)t2,

(3)

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

t2=30t1.

(4)

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

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

Tb=t3+t2,

(5)

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

t3≈3t1,

(6)

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

(7)

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

(8)

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

(1-Ps)ta+t2].

(9)

4 性能測(cè)試與分析

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

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

表1 快速索引性能測(cè)試

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

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

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

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

5 總結(jié)

面對(duì)系統(tǒng)存儲(chǔ)壓力不斷增大的現(xiàn)狀，重復(fù)數(shù)據(jù)刪除系統(tǒng)需要解決系統(tǒng)索引檢索效率的問(wèn)題.為此，本文通過(guò)在索引中引入時(shí)序參數(shù)，并依據(jù)數(shù)據(jù)塊的熱度值構(gòu)建了一種包含快速索引的兩層索引.實(shí)驗(yàn)結(jié)果證明基于時(shí)序參數(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ù)存儲(chǔ)與處理，E-mail：binzhou@mail.scuec.edu.cn

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

TP311

A

1672-4321(2017)02-0133-05