張宗華，屈　英，葉志佳，牛新征

1)國家電網(wǎng)公司北京電力醫(yī)院信息通訊部，北京 100073；2)電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，四川成都 611731

?

基于多特征匹配和Bloom filter的重復(fù)數(shù)據(jù)刪除算法

張宗華1，屈英2，葉志佳2，牛新征2

1)國家電網(wǎng)公司北京電力醫(yī)院信息通訊部，北京 100073；2)電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，四川成都 611731

針對EB(extreme binning)算法重復(fù)數(shù)據(jù)刪除率低，磁盤I/O開銷大的缺陷，提出基于多特征匹配和Bloom filter的重復(fù)數(shù)據(jù)刪除算法DBMB(deduplication based on multi-feature matching and Bloom filter). 將小文件聚合為局部性文件單元，作為一個(gè)整體進(jìn)行去重處理，采用最大、最小以及中間數(shù)據(jù)塊ID的多重相似性特征進(jìn)行匹配，并基于Bloom filter優(yōu)化磁盤數(shù)據(jù)塊的查找和匹配過程. 結(jié)果表明，DBMB算法能有效提升重復(fù)數(shù)據(jù)刪除率，降低算法執(zhí)行時(shí)間，同時(shí)減少處理小文件的內(nèi)存開銷，性能提升顯著.

計(jì)算技術(shù)；重復(fù)數(shù)據(jù)刪除；多特征匹配；布隆過濾器；EB算法；磁盤優(yōu)化

重復(fù)數(shù)據(jù)刪除(deduplication)是一種能有效優(yōu)化存儲(chǔ)空間、提高存儲(chǔ)效率的技術(shù)，目前被廣泛應(yīng)用于數(shù)據(jù)備份和歸檔系統(tǒng)中. 在基于數(shù)據(jù)塊的重復(fù)數(shù)據(jù)刪除技術(shù)中，索引的內(nèi)存占用量和運(yùn)行效率是影響系統(tǒng)性能的關(guān)鍵. EB(extreme binning)是Bhagwat等[1]提出的一種可擴(kuò)展的數(shù)據(jù)塊級去重技術(shù)，能較好地緩解內(nèi)存占用問題. EB算法基于數(shù)據(jù)流的相似性，通過建立和維護(hù)文件的代表塊(representative chunk)指紋索引，并將文件主體在磁盤中以指紋容器(bin)保存. 由于EB算法只在內(nèi)存中保存文件的代表塊ID，且對于每個(gè)文件的備份至多只需訪問一次磁盤，有效減小了內(nèi)存占用以及磁盤的訪問時(shí)間. 然而，傳統(tǒng)的EB算法采用文件的最小塊ID作為主索引，實(shí)質(zhì)是犧牲部分重復(fù)刪除率來獲取低內(nèi)存占用，其去重率相對較低. 為此，張志珂等[2]提出一種基于相似哈希的二級索引結(jié)構(gòu)，以相似哈希計(jì)算文件指紋，提高了小文件的重復(fù)數(shù)據(jù)刪除率. 但相似哈希只適用于處理文檔數(shù)據(jù)，很難滿足實(shí)際應(yīng)用場景中復(fù)雜多樣的文件類型. Xia等[3]提出一種重復(fù)數(shù)據(jù)刪除算法SiLo，該算法通過聚合強(qiáng)關(guān)聯(lián)文件為一個(gè)數(shù)據(jù)段，挖掘數(shù)據(jù)段間的數(shù)據(jù)相似性，同時(shí)結(jié)合數(shù)據(jù)流的局部性特征，以此提高文件重刪率，然而該算法對數(shù)據(jù)段大小較敏感，選取合適的段長度較困難.

EB算法的另一個(gè)缺陷是，雖然對于每個(gè)備份的文件至多需要訪問一次磁盤，但其訪問磁盤時(shí)采用順序遍歷的方式，當(dāng)磁盤中存儲(chǔ)的指紋容器較大時(shí)，遍歷所需時(shí)間較長. Zhang等[4]對EB算法進(jìn)行拓展，提出一種wWrR策略，通過同時(shí)訪問和更新多個(gè)磁盤數(shù)據(jù)塊和指紋，降低總的I/O操作次數(shù)，然而該算法未能優(yōu)化磁盤數(shù)據(jù)塊的查找和匹配過程，導(dǎo)致時(shí)間開銷仍較高.

針對上述EB算法的缺陷，本研究提出了基于多特征匹配和Bloom filter(布隆過濾器)的重復(fù)數(shù)據(jù)刪除算法——DBMB(deduplication based on multi-feature matching and Bloom filter). 針對傳統(tǒng)EB算法去重率較低，且小文件對內(nèi)存占用影響較大的問題，通過聚合局部小文件為一個(gè)文件單元，采用多特征匹配進(jìn)行重復(fù)數(shù)據(jù)刪除處理；同時(shí)針對EB算法遍歷磁盤中指紋容器耗時(shí)較多的缺陷，采用Bloom filter對每個(gè)存入磁盤的數(shù)據(jù)塊進(jìn)行記錄，查詢時(shí)只需通過Bloom filter再次計(jì)算即可，有效降低了磁盤查詢時(shí)間. 在兩個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行測試，結(jié)果顯示相較于EB，DBMB能降低對小文件的內(nèi)存開銷，并有效提高重復(fù)數(shù)據(jù)刪除率和算法運(yùn)行效率.

1　DBMB算法

為了解決EB算法去重率較低以及磁盤訪問開銷較高的問題，本研究提出DBMB算法，主要改進(jìn)思路如下：

1) 聚合多個(gè)小文件為局部文件單元，并對文件單元進(jìn)行去重處理，提高對小文件的去重率；

2) 提出一種多特征匹配策略，選取文件的最大塊、最小塊以及中間塊進(jìn)行匹配，若均不同才認(rèn)為兩文件完全不同；否則表明存在相似部分，進(jìn)行去重處理；

3) 采用Bloom filter，記錄和維護(hù)磁盤中數(shù)據(jù)塊的存儲(chǔ)狀態(tài)，使算法執(zhí)行過程中無需讀取磁盤數(shù)據(jù)，有效減少磁盤I/O開銷.

1.1小文件聚合及多特征匹配

在典型的存儲(chǔ)系統(tǒng)中，小文件(一般小于64 kbyte)所占物理空間為20%左右，其文件數(shù)目卻高達(dá)總數(shù)的80%，在采用傳統(tǒng)的EB算法去重時(shí)，內(nèi)存開銷大而去重效果較差. 為此，本研究提出聚合小文件為局部性文件單元，將其作為一個(gè)整體進(jìn)行重復(fù)數(shù)據(jù)刪除. 具體而言，對于在順序存儲(chǔ)的小文件(例如存儲(chǔ)在同一個(gè)文件夾下)，通過聚合成局部性文件單元，將多個(gè)小文件作為一個(gè)整體進(jìn)行重復(fù)數(shù)據(jù)刪除，減少小文件在主索引中的記錄條數(shù)，最終使小文件的內(nèi)存開銷得以降低.

為了改善EB算法去重率較低的缺陷，本研究提出一種多特征匹配的文件相似性檢測策略. 對于一個(gè)新文件，計(jì)算所有數(shù)據(jù)塊指紋，并選取具有最大、最小以及中間特征指紋值的數(shù)據(jù)塊與主索引中已有記錄進(jìn)行匹配. 若存在匹配成功的指紋，則可判定新文件與已存儲(chǔ)的文件存在相同的數(shù)據(jù)塊，進(jìn)行去重處理. 只有當(dāng)所有特征都不匹配時(shí)，才判定該文件不存在重復(fù)數(shù)據(jù)塊，在主索引中增加一條對該文件的描述記錄，分別存儲(chǔ)代表塊特征指紋，并將文件的其他數(shù)據(jù)塊存入磁盤. 根據(jù)Broder理論[5]，兩個(gè)文件的最小數(shù)據(jù)塊指紋相同的概率為

(1)

其中， F1和F2是兩個(gè)以數(shù)據(jù)塊集合表示的文件； H(x)是哈希函數(shù). 同理，兩文件的最大塊和中間塊指紋相同的概率也有類似結(jié)論. 由式(1)可以看出，由于采用了最小塊、最大塊以及中間塊指紋進(jìn)行特征匹配，所以理論上本研究的多特征匹配策略相較于只采用最小塊匹配的EB算法，在去重率方面具有更好的性能.

1.2基于Bloom filter的磁盤數(shù)據(jù)塊去重

由于EB算法對磁盤數(shù)據(jù)塊去重時(shí)，需要遍歷磁盤中的指紋容器，這會(huì)造成大量的I/O開銷. 為此，本研究通過建立和維護(hù)一個(gè)Bloom filter，當(dāng)數(shù)據(jù)塊存入磁盤時(shí)，記錄相應(yīng)狀態(tài)位；當(dāng)需要查詢磁盤中是否存在相同數(shù)據(jù)塊時(shí)，只需通過再次計(jì)算狀態(tài)位的值即可，避免了將磁盤的指紋容器讀入內(nèi)存. 算法添加和查詢一個(gè)元素的時(shí)間復(fù)雜度均為O(k)(k為哈希函數(shù)個(gè)數(shù))，大大提高了訪問磁盤的時(shí)間效率.

在判斷一個(gè)元素是否已存在時(shí)，Bloom filter會(huì)有一定的誤檢率(false positive rate)，所以需要根據(jù)數(shù)據(jù)塊集合的大小，選擇合適的哈希函數(shù)個(gè)數(shù)k和位數(shù)組長度m. 誤檢率的計(jì)算公式為

f=(1-e-kn/m)k

(2)

令p=e-kn/m， 則有l(wèi)nf=kln(1-p)=-(m/n)lnpln(1-p)， 由對稱性法則可知，當(dāng)p=1/2即k=(m/n)ln2時(shí)，誤檢率f取得最小值. 同時(shí)，當(dāng)給定誤檢率的上限φ時(shí)，位數(shù)組長度m需滿足

(3)

由式(3)可見，當(dāng)已知文件數(shù)據(jù)塊數(shù)量n以及系統(tǒng)的誤檢率上限φ時(shí)，就能相應(yīng)地計(jì)算出最佳的位數(shù)組長度m以及哈希函數(shù)個(gè)數(shù)k. φ一般根據(jù)經(jīng)驗(yàn)來確定，本研究取0.01%.

基于前文所述，改進(jìn)的算法主索引結(jié)構(gòu)如圖1. 其中最大、最小以及中間塊ID作為文件的代表ID進(jìn)行多特征匹配，位數(shù)組用于Bloom filter記錄磁盤數(shù)據(jù)塊的存儲(chǔ)狀態(tài)，文件指針則用于連接主索引記錄與磁盤指紋容器.

圖1　改進(jìn)的主索引結(jié)構(gòu)Fig.1　Structure of improved primary index

1.3DBMB算法流程

DBMB算法偽代碼如圖2，對于給定的源文件夾和目標(biāo)文件夾，圖2中第4～7行算法首先對小于64 kbyte的小文件進(jìn)行聚合，并采用基于內(nèi)容的分塊算法(content-defined chunking，CDC)[6]對文件進(jìn)行變長分塊，隨后基于MD5信息摘要算法計(jì)算數(shù)據(jù)塊指紋. 第7行算法選取最大、最小以及中間塊ID(MD5值)作為文件代表塊ID，并進(jìn)行文件的多特征匹配. 第8～16行，若在主索引中找到該代表ID，則表明已存儲(chǔ)了相似的文件，采用Bloom filter對磁盤中的數(shù)據(jù)塊進(jìn)一步匹配，并存儲(chǔ)不同的數(shù)據(jù)塊；否則，直接將所有數(shù)據(jù)塊存儲(chǔ).

算法:DBMB(sourceFolder,targetFolder)輸入:源文件夾sourceFolder,目標(biāo)文件夾targetFolder輸出:主索引primaryIndex1.initializeprimaryIndex;//初始化主索引2.readfilefromsourceFolder;//讀取文件3.forallfilei∈sourceFolderdo4. iffilei.size()<=64kbyte5. mergesmallfiles;//聚合小文件6. chunkFile=CDC(filei);//文件分塊7. chunkID=MD5(filei);//計(jì)算數(shù)據(jù)塊的MD5值8. findrepresentIDfromchunkID;9. iffindrepresentIDfromprimaryIndex//找到代表塊ID10. forallchunkIDi∈chunkIDdo11. iffindchunkIDi12. bloomFilter.insert(chunkIDi);13. bin.insert(chunkIDi);14.else//未找到代表塊ID15. bloomFilter.insert(chunkID);16. bin.insert(chunkID);17.writebinfiletotargetFolder;18.returnprimaryIndex

圖2DBMB算法偽代碼

Fig.2Pseudo code of DBMB

2　實(shí)驗(yàn)測試與分析

本研究通過實(shí)驗(yàn)評估DBMB算法的去重性能，主要從重復(fù)數(shù)據(jù)刪除率(去重率)、算法執(zhí)行時(shí)間以及算法的內(nèi)存開銷3個(gè)維度測試，其中去重率定義為原始數(shù)據(jù)量與存儲(chǔ)數(shù)據(jù)量之比，內(nèi)存開銷定義為處理1 Mbyte數(shù)據(jù)所需的內(nèi)存. 實(shí)驗(yàn)采用Linux Kernel Archives數(shù)據(jù)[7]和某公司真實(shí)的運(yùn)維數(shù)據(jù)，其數(shù)據(jù)集特征如表1. 本研究在Linux系統(tǒng)下實(shí)現(xiàn)了DBMB算法，硬件環(huán)境為2.4 GHz四核處理器，4 Gbyte內(nèi)存，500 Gbyte硬盤.

首先初始化Bloom filter的相關(guān)參數(shù)，由存儲(chǔ)備份系統(tǒng)的統(tǒng)計(jì)經(jīng)驗(yàn)，每個(gè)指紋容器的元素?cái)?shù)目一般不超過1 000，同時(shí)Bloom filter的誤檢率取0.01%，則由式(3)可計(jì)算出最小的數(shù)組長度m為2 500字節(jié)，哈希函數(shù)個(gè)數(shù)k=(m/n)ln2=14.

表1　測試數(shù)據(jù)集特征

2.1Linux數(shù)據(jù)集實(shí)驗(yàn)

對于Linux數(shù)據(jù)集，傳統(tǒng)EB算法和DBMB算法重復(fù)數(shù)據(jù)刪除后的存儲(chǔ)空間變化如圖3(a). 圖3(a)中橫坐標(biāo)表示內(nèi)核代碼版本，實(shí)驗(yàn)中是從1.1.13到2.6.33順序排列；縱坐標(biāo)表示占用的存儲(chǔ)空間. 由圖3(a)可見，在前350個(gè)版本的去重中，DBMB算法和EB算法的去重效果相差不大，這是因?yàn)榍捌诎姹靖膭?dòng)相對較小，文件重復(fù)率較高. 但隨著數(shù)據(jù)量的進(jìn)一步增大，DBMB算法展現(xiàn)出了多特征匹配的優(yōu)勢，對相似度較低的文件也能檢測出重復(fù)數(shù)據(jù)塊. EB算法處理的數(shù)據(jù)最終占用空間為7.69 Gbyte，去重率為13.13∶1.00；而DBMB算法占用的存儲(chǔ)空間為5.64 GB，去重率為17.91∶1.00，相比前者提高了36.41%.

DBMB算法和EB算法在Linux數(shù)據(jù)集上的執(zhí)行時(shí)間如圖3(b). 從圖3(b)可以看出，當(dāng)數(shù)據(jù)量較小時(shí)，兩個(gè)算法的執(zhí)行時(shí)間增長較慢. 而隨著數(shù)據(jù)量的增大，指紋容器中的元素個(gè)數(shù)也相應(yīng)增多，對磁盤中數(shù)據(jù)的匹配成為EB算法的瓶頸，其算法執(zhí)行時(shí)間陡增. 對于DBMB算法，由于其采用了Bloom filter優(yōu)化磁盤去重過程，添加和查詢操作的時(shí)間復(fù)雜度均為O(k)，其算法執(zhí)行時(shí)間不受數(shù)據(jù)規(guī)模的影響，故保持緩慢增長. EB算法最終執(zhí)行時(shí)間為125.47 s，而DBMB算法為76.54 s，相較于前者性能提升了38.99%.

圖3　Linux數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Fig.3　Results of Linux data set

2.2運(yùn)維數(shù)據(jù)集實(shí)驗(yàn)

分別采用EB算法和DBMB算法對運(yùn)維數(shù)據(jù)集進(jìn)行重復(fù)數(shù)據(jù)刪除，實(shí)驗(yàn)結(jié)果與Linux數(shù)據(jù)集相似，最終實(shí)驗(yàn)結(jié)果如圖4. 其中EB算法去重后的數(shù)據(jù)為761.38 Mbyte，去重率為8.44∶1.00，算法執(zhí)行時(shí)間為16.84 s；而DBMB算法處理后的數(shù)據(jù)為537.78 Mbyte，去重率為11.95∶1.00，算法執(zhí)行時(shí)間為12.05 s. DBMB算法的去重率和運(yùn)行效率比EB算法分別提升了41.59%和28.44%.

圖4　運(yùn)維數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Fig.4　Results of operational data set

圖5展示了EB算法和DBMB算法在對兩個(gè)數(shù)據(jù)集去重的內(nèi)存開銷. 由于Linux數(shù)據(jù)集小文件較多，所以DBMB算法聚合小文件的策略在一定程度上減小內(nèi)存占用量. 而對于運(yùn)維數(shù)據(jù)集，由于其主要是大文件，故DBMB算法的內(nèi)存開銷與EB算法基本持平.

由上述兩個(gè)數(shù)據(jù)集的測試結(jié)果可知，本研究提出的基于多特征匹配和Bloom filter改進(jìn)的EB算法比傳統(tǒng)EB算法具有更高的去重性能和更快的時(shí)間效率，且對于小文件占主導(dǎo)的存儲(chǔ)系統(tǒng)能有效減小內(nèi)存開銷.

圖5　EB和DBMB的內(nèi)存開銷Fig.5　Memory overhead of EB and DBMB

結(jié)　語

針對傳統(tǒng)EB算法去重率較低以及磁盤數(shù)據(jù)匹配吞吐率較低的缺陷，提出聚合小文件為局部性單元，并基于最大塊、最小塊以及中間塊的多特征匹配策略，提高重復(fù)數(shù)據(jù)刪除率；同時(shí)采用Bloom filter記錄和維護(hù)指紋容器中的數(shù)據(jù)，有效提高了磁盤數(shù)據(jù)匹配的時(shí)間效率. 實(shí)驗(yàn)結(jié)果表明，本研究提出的DBMB算法的去重率和執(zhí)行時(shí)間均優(yōu)于傳統(tǒng)EB算法，且對小文件去重時(shí)具有較低的內(nèi)存開銷.

/

[1] Bhagwat D, Eshghi K, Long D D E, et al. Extreme binning: scalable, parallel deduplication for chunk-based file backup[C]// IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems.Dresden, Germany: IEEE, 2009: 1-9.

[2] 張志珂, 蔣澤軍, 蔡小斌,等. 相似索引:適用于重復(fù)數(shù)據(jù)刪除的二級索引[J]. 計(jì)算機(jī)應(yīng)用研究, 2013, 30(12):3614-3617.

Zhang Zhike, Jiang Zejun, Cai Xiaobin, et al. Similar index: two-level index used for deduplication[J]. Application Research of Computers, 2013, 30(12):3614-3617.(in Chinese)

[3] Xia Wen,Jiang Hong,Feng Dan,et al.SiLo:a similarity-locality based near-exact deduplication scheme with low RAM overhead and high throughput[C]// USENIX Annual Technical Conference. Compton, USA: USENIX Association, 2011:26-28.

[4] Zhang Zhike, Bhagwat D, Litwin W, et al. Improved deduplication through parallel binning [C]// IEEE the 31st International Performance Computing and Communications Conference. Ottawa, Canada: IEEE, 2012: 130-141.

[5] Broder A Z. On the resemblance and containment of documents[C]// Compression and Complexity of Sequences. Atlanta, USA: IEEE, 1997: 21-29.

[6] 付印金, 肖儂, 劉芳. 重復(fù)數(shù)據(jù)刪除關(guān)鍵技術(shù)研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(1):12-20.

Fu Yinjin, Xiao Nong, Liu Fang. Research and development on key techniques of data deduplication[J]. Journal of Computer Research and Development, 2012, 49(1):12-20.(in Chinese)

[7] Linux Kernel Organization. The Linux Kernel[DB/OL]. Compton, USA: Linux Kernal Organization[2016-05-12].https://www.kernel.org/.

【中文責(zé)編：坪梓；英文責(zé)編：子蘭】

2016-08-12；Accepted：2016-09-05

Deduplication based on multi-feature matching and Bloom filter

Zhang Zonghua1, Qu Ying2, Ye Zhijia2, and Niu Xinzheng2?

1)Ministry of Information and Communication, Beijing Electric Power Hospital, State Grid Corporation of China, Beijing 100073, P.R.China 2)School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, Sichuan Province, P.R.China

Aiming at low deduplication rate and high disk I/O overhead of EB (extreme binning), we propose a deduplication algorithm based on multi-feature matching and Bloom filter (DBMB). Firstly, we group small files as a local file unit in order to process them as a whole. Then we take the maximum, minimum and middle ID of data chunk for similarity matching. Finally, we optimize the process of searching and matching disk data blocks based on Bloom filter. The experiment results show that DBMB algorithm can effectively increase the deduplication rate and reduce the execution time. In the meantime, DBMB reduces the memory overhead of small files deduplication, the comprehensive performance is improved significantly.

computing technology; deduplication; multi-feature matching; Bloom filter; extreme binning; disk optimization

Zhang Zonghua，Qu Ying，Ye Zhijia，et al．Deduplication based on multi-feature matching and Bloom filter[J]. Journal of Shenzhen University Science and Engineering, 2016, 33(5): 531-535.(in Chinese)

TP 301.6

Adoi：10.3724/SP.J.1249.2016.05531

國家自然科學(xué)基金資助項(xiàng)目(61300192)；中央高?；究蒲袠I(yè)務(wù)費(fèi)資助項(xiàng)目(ZYGX2014J052)；北京電力醫(yī)院一體化運(yùn)維監(jiān)控與管理資助項(xiàng)目

張宗華(1977—)，男，國家電網(wǎng)公司北京電力醫(yī)院工程師. 研究方向：電力信息化．E-mail：zhang.zonghua@nc.sgcc.com.cn

Foundation：National Natural Science Foundation of China (61300192); Fundamental Research Funds for the Central Universities (ZYGX2014J052); Integration of Operational Monitoring and Management Project of Beijing Electric Power Hospital

? Corresponding author：Associate professor Niu Xinzheng．E-mail: xinzhengniu@uestc.edu.cn

引文：張宗華，屈英，葉志佳，等．基于多特征匹配和Bloom filter的重復(fù)數(shù)據(jù)刪除算法[J]. 深圳大學(xué)學(xué)報(bào)理工版，2016，33(5)：531-535.