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

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

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

?

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

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

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

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

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

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

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

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

1　DBMB算法

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

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

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

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

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

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

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

(1)

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

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

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

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

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

(2)

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

(3)

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

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

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

1.3DBMB算法流程

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

算法:DBMB(sourceFolder,targetFolder)輸入:源文件夾sourceFolder,目標文件夾targetFolder輸出:主索引primaryIndex1.initializeprimaryIndex;//初始化主索引2.readfilefromsourceFolder;//讀取文件3.forallfilei∈sourceFolderdo4. iffilei.size()<=64kbyte5. mergesmallfiles;//聚合小文件6. chunkFile=CDC(filei);//文件分塊7. chunkID=MD5(filei);//計算數(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　實驗測試與分析

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

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

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

2.1Linux數(shù)據(jù)集實驗

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

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

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

2.2運維數(shù)據(jù)集實驗

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

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

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

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

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

結(jié)　語

針對傳統(tǒng)EB算法去重率較低以及磁盤數(shù)據(jù)匹配吞吐率較低的缺陷，提出聚合小文件為局部性單元，并基于最大塊、最小塊以及中間塊的多特征匹配策略，提高重復數(shù)據(jù)刪除率；同時采用Bloom filter記錄和維護指紋容器中的數(shù)據(jù)，有效提高了磁盤數(shù)據(jù)匹配的時間效率. 實驗結(jié)果表明，本研究提出的DBMB算法的去重率和執(zhí)行時間均優(yōu)于傳統(tǒng)EB算法，且對小文件去重時具有較低的內(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] 張志珂, 蔣澤軍, 蔡小斌,等. 相似索引:適用于重復數(shù)據(jù)刪除的二級索引[J]. 計算機應用研究, 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] 付印金, 肖儂, 劉芳. 重復數(shù)據(jù)刪除關(guān)鍵技術(shù)研究進展[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/.

【中文責編：坪梓；英文責編：子蘭】

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

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

張宗華(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的重復數(shù)據(jù)刪除算法[J]. 深圳大學學報理工版，2016，33(5)：531-535.