武警8710部隊(duì)通信科 段志剛武警警官學(xué)院 吳耕銳 薄 鳥

?

一種武警云計(jì)算環(huán)境下集群重復(fù)數(shù)據(jù)刪除策略

武警8710部隊(duì)通信科 段志剛
武警警官學(xué)院 吳耕銳 薄 鳥

1　引言

隨著大數(shù)據(jù)時代的發(fā)展，數(shù)據(jù)量正在爆炸式增長，數(shù)據(jù)更新變化也在時刻進(jìn)行［1］。調(diào)查發(fā)現(xiàn)云端數(shù)據(jù)中心有60%以上數(shù)據(jù)是冗余的，這就為數(shù)據(jù)同步提出了巨大挑戰(zhàn)。針對云環(huán)境下集群分布式存儲的全局重復(fù)數(shù)據(jù)刪除，存在著數(shù)據(jù)塊索引磁盤瓶頸和存儲節(jié)點(diǎn)信息孤島兩大困難：（1）數(shù)據(jù)塊索引磁盤瓶頸：在存儲服務(wù)器節(jié)點(diǎn)的磁盤上建立一個數(shù)據(jù)塊索引序列，完成集群內(nèi)數(shù)據(jù)存儲節(jié)點(diǎn)的重復(fù)數(shù)據(jù)刪除。（2）重復(fù)數(shù)據(jù)刪除節(jié)點(diǎn)信息孤島：針對云環(huán)境下集群系統(tǒng)的重復(fù)數(shù)據(jù)刪除過程，往往忽略節(jié)點(diǎn)之間的重復(fù)數(shù)據(jù)刪除，由此產(chǎn)生了重復(fù)數(shù)據(jù)刪除節(jié)點(diǎn)的孤島效應(yīng)。

2　相關(guān)工作

現(xiàn)有云環(huán)境下的全局重復(fù)刪除技術(shù)，如EMC公司的data domain全局重復(fù)數(shù)據(jù)刪除陣列、IBM公司的protectTier、SEPATON公司的S2100-ES2等［2-4］，由于在全局?jǐn)?shù)據(jù)縮減率、單節(jié)點(diǎn)存儲率、數(shù)據(jù)分布或者系統(tǒng)通信開銷上存在不足，利用這些技術(shù)來設(shè)計(jì)由成千上萬節(jié)點(diǎn)構(gòu)成的集群，很可能不會成功。Bhagwat設(shè)計(jì)了Extreme Binning策略，Extreme Binning基于文件的相似性，以加密Hash生成的Chunk ID。文獻(xiàn)［5］設(shè)計(jì)了一種支持云環(huán)境下大數(shù)據(jù)備份的可擴(kuò)展在線集群重復(fù)數(shù)據(jù)刪除框架。

本文利用Bloom Filter機(jī)制為存儲節(jié)點(diǎn)內(nèi)的所有數(shù)據(jù)塊指紋建立一個全局的快速索引，從而實(shí)現(xiàn)支持高數(shù)據(jù)縮減率、高吞吐率、低通信開銷及負(fù)載均衡的全局重復(fù)數(shù)據(jù)刪除。

3　基于Bloom Filter的全局?jǐn)?shù)據(jù)刪重策略

利用Bloom Filter機(jī)制可以將集群內(nèi)所有節(jié)點(diǎn)存儲的數(shù)據(jù)塊指紋表示成Bloom Filter指紋摘要（Fingerprint Summary），形成全局的快速索引序列。例如集群中有p個存儲服務(wù)器節(jié)點(diǎn)，假設(shè)所有節(jié)點(diǎn)的Bloom Filter長度全部為n，并且所有節(jié)點(diǎn)采用k個相同且相互獨(dú)立的哈希函數(shù)。數(shù)據(jù)中心接收到客戶端發(fā)送來的數(shù)據(jù)塊指紋時，檢測該塊是新塊還是已存儲的數(shù)據(jù)塊，其過程如圖1所示：

圖1　重復(fù)數(shù)據(jù)刪除過程

基于Bloom Filter機(jī)制及相似性理論，在超塊的基礎(chǔ)上進(jìn)行有狀態(tài)路由的重復(fù)數(shù)據(jù)檢測刪除的算法描述如下： （1）控制服務(wù)器節(jié)點(diǎn)依次計(jì)算出超塊Q｛fp1，fp2，fp3，…fpn｝中所有數(shù)據(jù)塊指紋對應(yīng)的k個哈希函數(shù)值，將hi（xj）保存并分發(fā)到每一個存儲節(jié)點(diǎn)；（2）利用哈希值hi（xj）依次從FSA獲取映射位置的列值。若某一列對應(yīng)的值全是0（Negative），可判定其為新數(shù)據(jù)塊；（3）若任一哈希值hi（xj）映射的列向量的值不全為0（Positive），返回一條Duplication Possible的消息；（4）查詢結(jié)束后，若返回的數(shù)據(jù)塊類型值為Duplication Possible。若依次查詢到某一節(jié)點(diǎn)所有hi（xj）映射的位全部是1，則返回消息為Positive；（5）利用按行查詢即節(jié)點(diǎn)確認(rèn)算法返回的結(jié)果是節(jié)點(diǎn)的ID，進(jìn)而在對應(yīng)的存儲節(jié)點(diǎn)進(jìn)一步的細(xì)粒度查詢重復(fù)數(shù)據(jù)，確認(rèn)數(shù)據(jù)塊是否是重復(fù)的。

4　實(shí)驗(yàn)分析

在實(shí)驗(yàn)室現(xiàn)有的硬件環(huán)境下，選用1臺計(jì)算機(jī)作為客戶端，1臺配置Hadoop框架的服務(wù)器及4臺計(jì)算機(jī)搭建Hadoop集群［6］。

通過與文獻(xiàn)［7］提出的基于Bloom Filter數(shù)據(jù)重復(fù)刪除策略、文獻(xiàn)［8］設(shè)計(jì)的Σ-Dedupe方案對比，實(shí)驗(yàn)結(jié)果如圖5-4所示。實(shí)驗(yàn)結(jié)果表明，三種方案在數(shù)據(jù)重刪消耗時間大致相同的情況下，本文設(shè)計(jì)的G-dedupe會獲得最大的數(shù)據(jù)縮減率，在數(shù)據(jù)龐大的集群存儲系統(tǒng)中就能極大地節(jié)省存儲空間，提高集群系統(tǒng)的整體性能。

圖3　試驗(yàn)對比結(jié)果

5　結(jié)論

本文主要研究集群內(nèi)部的全局重復(fù)數(shù)據(jù)刪除。運(yùn)用 Bloom Filter 技術(shù)為集群數(shù)據(jù)中心中存儲的所有數(shù)據(jù)塊建立快速索引的摘要信息，合成一個可以檢測重復(fù)數(shù)據(jù)的指紋摘要陣列，分布在存儲節(jié)點(diǎn)前端的控制服務(wù)器，控制服務(wù)器節(jié)點(diǎn)將客戶端發(fā)送到的數(shù)據(jù)塊指紋合并成若干粒度大小均勻的超塊，進(jìn)行重復(fù)數(shù)據(jù)的檢測，然后將數(shù)據(jù)塊的重復(fù)刪除分布到存儲節(jié)點(diǎn)中進(jìn)行。研究成果實(shí)現(xiàn)了數(shù)據(jù)同步中的數(shù)據(jù)縮減率問題，為集群存儲節(jié)省了大量的存儲空間。

參考文獻(xiàn)

［1］IBM Cloud Computing ［EB/OL］. http：//www.ibm.com/ibm/cloud.

［2］吳朱華.云計(jì)算核心技術(shù)剖析［M］.北京：人民郵電出版社，2011，5.

［3］陳釗.基于云災(zāi)備的數(shù)據(jù)安全存儲關(guān)鍵技術(shù)研究［D］.北京郵電大學(xué)，2012.

［4］李俊中. 云存儲環(huán)境下數(shù)據(jù)完整性驗(yàn)證方法研究［D］.重慶郵電大學(xué)，2013.

［5］Bobbarjung D R， Jagannathan S， Dubnicki C. Improving duplicate elimination in storage systems［J］. Acm Transactions on Storage，2006，2（4）：424-448.

［6］葉明江，崔勇，徐恪等.基于有狀態(tài)Bloom filter引擎的高速分組檢測［J］.軟件學(xué)報(bào)， 2006，18：117-126.

［7］毛波，葉閣焰，藍(lán)琰佳等.一種基于重復(fù)數(shù)據(jù)刪除技術(shù)的云中云存儲系統(tǒng)［J］.計(jì)算機(jī)研究與發(fā)展，2015（6）：1278-1287.

［8］楊超，張俊偉，董學(xué)文等.云存儲加密數(shù)據(jù)去重刪除所有權(quán)證明方法［J］.計(jì)算機(jī)研究與發(fā)展，2015，1（1）：248-258.

作者簡介：

段志剛（1977—），男，江西景德鎮(zhèn)人，現(xiàn)供職于武警8710部隊(duì)通信修理所，助理工程師，主要研究武警通信與信息化。

吳耕銳（1985—），福建漳州人，現(xiàn)供職于武警警官學(xué)院信息工程系，研究方向：信息化。

薄鳥（1986—），女，陜西西安人，現(xiàn)供職于武警警官學(xué)院數(shù)學(xué)與物理系，研究方向：固體物理。