陳　曉　張龍軍　王　謙　武警工程大學(xué)信息工程系　陜西西安　71008

?

集群重復(fù)數(shù)據(jù)刪除策略的研究

陳曉張龍軍王謙武警工程大學(xué)信息工程系陜西西安71008

【文章摘要】

提出了集群內(nèi)的全局重復(fù)數(shù)據(jù)刪除方案，運(yùn)用 Bloom Filter 技術(shù)為集群中存儲(chǔ)的所有數(shù)據(jù)塊建立快速索引的摘要信息，組成一個(gè)可以檢測(cè)重復(fù)數(shù)據(jù)的指紋摘要陣列（FSA），分布在存儲(chǔ)節(jié)點(diǎn)前端的控制服務(wù)器，控制服務(wù)器節(jié)點(diǎn)將客戶端發(fā)送到的數(shù)據(jù)塊指紋合并成若干粒度大小均勻的超塊，進(jìn)行重復(fù)數(shù)據(jù)的檢測(cè)，然后將超塊有狀態(tài)地路由到各個(gè)存儲(chǔ)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)刪重。利用FSA檢測(cè)全局范圍內(nèi)所有存儲(chǔ)節(jié)點(diǎn)之間的重復(fù)數(shù)據(jù)，獲取較高的重復(fù)數(shù)據(jù)刪除率，極大的提高了內(nèi)存空間的利用率。

【關(guān)鍵詞】

重復(fù)數(shù)據(jù)刪除；指紋摘要陣列；超塊

0　引言

隨著大數(shù)據(jù)時(shí)代的發(fā)展，數(shù)據(jù)量正在爆炸式增長(zhǎng)，數(shù)據(jù)更新變化也在時(shí)刻進(jìn)行。數(shù)據(jù)量從TB上升到PB甚至EB，隨著數(shù)據(jù)集關(guān)聯(lián)性的日益繁雜，面向云環(huán)境的集群中心會(huì)產(chǎn)生大量冗余數(shù)據(jù)。調(diào)查發(fā)現(xiàn)云端數(shù)據(jù)中心有60%以上數(shù)據(jù)是冗余的，這就為數(shù)據(jù)同步提出了巨大挑戰(zhàn)。為支持云環(huán)境下分布式存儲(chǔ)的特點(diǎn)，單一的數(shù)據(jù)同步技術(shù)已難以滿足節(jié)省存儲(chǔ)空間和系統(tǒng)擴(kuò)展的需求，集群內(nèi)所有節(jié)點(diǎn)之間進(jìn)行數(shù)據(jù)去重的數(shù)據(jù)同步技術(shù)應(yīng)運(yùn)而生。集群重復(fù)數(shù)據(jù)刪除是在存儲(chǔ)系統(tǒng)全局范圍內(nèi)進(jìn)行分布并行的數(shù)據(jù)刪重技術(shù)。它通過有效的數(shù)據(jù)路由指導(dǎo)策略將客戶端上傳的數(shù)據(jù)分發(fā)到集群內(nèi)的存儲(chǔ)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)刪重。

1　Bloom Filter

我們假設(shè) Bloom Filter 使用一個(gè)長(zhǎng)度為 n的位數(shù)組 N，首先將位數(shù)組N的所有位初始化為0。設(shè)定一個(gè)包含 m 個(gè)元素的集合 S={x1, x2,…xm}，Bloom Filter 使用 k 個(gè)相互獨(dú)立的哈希函數(shù)h1, h2,…,hk，它們分別將集合 S 中的每一個(gè)元素映射到位數(shù)組{1, 2, …,n}的范圍中，當(dāng)有任意一個(gè)x元素進(jìn)入集合S 中，第 i個(gè)獨(dú)立哈希函數(shù)映射的位置N [hi(x)]（i =1, …, k）就會(huì)被置為 1。對(duì)于不同的元素，其獨(dú)立的哈希函數(shù)可能會(huì)映射到同一位置，即某一位被重復(fù)地置為 1。例中采用 3 個(gè)相互獨(dú)立的哈希函數(shù)，即 k = 3，當(dāng)元素x1和 x2先后被插入到位數(shù)組N時(shí)，有兩個(gè)哈希函數(shù)映射到位數(shù)組中的第 8 位，此時(shí)只有第一次映射起作用，即位數(shù)組第8位映射的是先進(jìn)入集合的元素x1。

判斷一個(gè)未知的元素 y 是否屬于集合 S，需要對(duì)元素y 應(yīng)用 k 次哈希函數(shù)得到k個(gè)哈希值，檢查所有的哈希值對(duì)應(yīng)的位 N [hi(y)]（i =1, …, k）是否都被置為了 1。如果都為 1，則y 可能是集合中的元素，此時(shí)將這種情況視為Positive，否則 元素y 就不屬于集合S，這種情況為 Negative。y1不是集合 S 中的元素，而 y2可能屬于集合 S。

DDFS重復(fù)數(shù)據(jù)刪除系統(tǒng)設(shè)計(jì)使用一個(gè)Bloom Filter 來表示整個(gè)集群中全部的數(shù)據(jù)塊指紋，并被抽象成指紋摘要向量，它具有常量級(jí)的時(shí)間復(fù)雜度，是建立在磁盤索引訪問之前的快速索引機(jī)制，能夠較快的查詢并判斷重復(fù)數(shù)據(jù)塊，可以較高的提升系統(tǒng)吞吐率。

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

2.1全局去重策略的設(shè)計(jì)與實(shí)現(xiàn)

利用Bloom Filter機(jī)制，可以將集群內(nèi)所有存儲(chǔ)節(jié)點(diǎn)上存儲(chǔ)的數(shù)據(jù)塊指紋表示成Bloom Filter指紋摘要（Fingerprint Summary），形成全局的快速索引序列。例如集群中有p個(gè)存儲(chǔ)服務(wù)器節(jié)點(diǎn)，假設(shè)所有節(jié)點(diǎn)的 Bloom Filter長(zhǎng)度全部為 n，并且所有節(jié)點(diǎn)采用k個(gè)相同且相互獨(dú)立的哈希函數(shù)。為實(shí)現(xiàn)全局的重復(fù)數(shù)據(jù)刪除，將集群內(nèi)每一個(gè)節(jié)點(diǎn)的Bloom Filter指紋摘要聚合到一塊，組成Bloom Filter代表的陣列（Bloom Filter Array，BFA），保存到數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)前端的控制服務(wù)器節(jié)點(diǎn)中心并分發(fā)到每個(gè)存儲(chǔ)節(jié)點(diǎn)，BFA又可稱作指紋摘要陣列，即Fingerprint Summary Arra，簡(jiǎn)稱FSA，如下圖 1所示：

圖1　指紋摘要陣列

當(dāng)集群服務(wù)器中心接受客戶端發(fā)送的數(shù)據(jù)塊指紋時(shí)，此指紋信息首先會(huì)傳輸?shù)酱鎯?chǔ)服務(wù)器節(jié)點(diǎn)前端的控制服務(wù)器中，并將數(shù)據(jù)塊指紋按照均勻的粒度組成超塊Q，根據(jù)Bloom Filter 陣列依次進(jìn)行重復(fù)數(shù)據(jù)檢測(cè)。檢測(cè)完成后刪除重復(fù)的數(shù)據(jù)，將可能不重復(fù)的數(shù)據(jù)有狀態(tài)的路由到存儲(chǔ)節(jié)點(diǎn)進(jìn)行細(xì)粒度的檢測(cè)，最后確定數(shù)據(jù)塊是否是新塊或是已存在的數(shù)據(jù)塊。數(shù)據(jù)中心接收到客戶端發(fā)送來的數(shù)據(jù)塊指紋時(shí)，檢測(cè)該塊是新塊還是已存儲(chǔ)的數(shù)據(jù)塊，其流程如圖2 所示：

圖2　重復(fù)數(shù)據(jù)檢測(cè)流程

2.2存儲(chǔ)節(jié)點(diǎn)的去重策略

DDFS系統(tǒng)為保持冗余的局部性，采取了基于流的塊排列（SISL）技術(shù)，在容器（Container）中根據(jù)先后的邏輯關(guān)系存儲(chǔ)一個(gè)文件的數(shù)據(jù)塊及相應(yīng)指紋。冗余局部性是指一個(gè)數(shù)據(jù)塊是重復(fù)塊的時(shí)候，其附近的數(shù)據(jù)塊極可能也是重復(fù)快。

控制中心服務(wù)器將超快指紋分發(fā)到存儲(chǔ)節(jié)點(diǎn)之前，必須進(jìn)行存儲(chǔ)節(jié)點(diǎn)的選擇。選取存儲(chǔ)節(jié)點(diǎn)時(shí)，常用的方法是利用數(shù)據(jù)塊指紋取模的算法，這樣就會(huì)存在比較大的弊端，由于數(shù)據(jù)塊在存儲(chǔ)之前被置亂，所以一個(gè)存儲(chǔ)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)塊可能來自于不同的文件，刪重后的數(shù)據(jù)仍然會(huì)存儲(chǔ)到此節(jié)點(diǎn)，數(shù)據(jù)的局部性便會(huì)受到一定的影響，進(jìn)而影響后續(xù)數(shù)據(jù)刪重的效果及效率。另一種方法是利用指紋前綴來選擇存儲(chǔ)節(jié)點(diǎn)，將屬于同一類指紋前綴的數(shù)據(jù)塊存放到一個(gè)節(jié)點(diǎn)，但是指紋前綴不能判斷表數(shù)據(jù)塊是否來自同一文件，因而數(shù)據(jù)的局部性也不能得到改善。

設(shè)計(jì)在選取存儲(chǔ)節(jié)點(diǎn)時(shí)，首先，計(jì)算出節(jié)點(diǎn)內(nèi)已存在的數(shù)據(jù)塊指紋數(shù){r1,r2,r3,…,rm}，所有的 m個(gè)值可以反映出超塊Q與存儲(chǔ)節(jié)點(diǎn)中數(shù)據(jù)的相似度。然后，計(jì)算各節(jié)點(diǎn)的相對(duì)存儲(chǔ)使用率，以一個(gè)存儲(chǔ)節(jié)點(diǎn)的存儲(chǔ)使用率比整個(gè)服務(wù)器集群內(nèi)所有節(jié)點(diǎn)的平均存儲(chǔ)率來計(jì)算各個(gè)節(jié)點(diǎn)的相對(duì)存儲(chǔ)使用率{w1,w2,w3,…,wm}，利用節(jié)點(diǎn)相對(duì)存儲(chǔ)使用率可以為存儲(chǔ)節(jié)點(diǎn)的相似度加權(quán){ r1/w1, r2/w2, r3/w3,…rm,/wm, }。最后，在存儲(chǔ)節(jié)點(diǎn)中選取滿足Idi滿足ri/wi=max{ r1/ w1, r2/w2, r3/w3,…rm,/wm, }的重復(fù)數(shù)據(jù)刪除節(jié)點(diǎn)作為超塊Q的路由目標(biāo)節(jié)點(diǎn)。

2.3指紋摘要陣列FSA的同步

在前文敘述中，本章節(jié)結(jié)合Summary Cache的協(xié)議保持各節(jié)點(diǎn)之間以及控制服務(wù)器節(jié)點(diǎn)的FSA的數(shù)據(jù)同步，維護(hù)FSA的一致性。在每個(gè)存儲(chǔ)服務(wù)器節(jié)點(diǎn)都會(huì)保存一個(gè)全局的指紋摘要陣列FSA的副本，這樣當(dāng)有新數(shù)據(jù)塊存儲(chǔ)到相應(yīng)的存儲(chǔ)節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)就會(huì)查詢（讀操作）此前存儲(chǔ)的FSA副本，并動(dòng)態(tài)地更新（寫操作）本地保存的FSA副本陣列，即新數(shù)據(jù)塊運(yùn)用k個(gè)哈希函數(shù)計(jì)算得出的值在指紋摘要陣列相應(yīng)的行中置為1。此時(shí)數(shù)據(jù)中心前端的控制服務(wù)器節(jié)點(diǎn)中地FSA保存的數(shù)據(jù)依然是之前存儲(chǔ)的。這樣，控制服務(wù)器節(jié)點(diǎn)與所有存儲(chǔ)節(jié)點(diǎn)間的FSA副本數(shù)據(jù)同步問題就變得尤為重要，它直接關(guān)系著集群內(nèi)數(shù)據(jù)塊的縮減率及去重的效果。

控制服務(wù)器節(jié)點(diǎn)的FSA與各存儲(chǔ)節(jié)點(diǎn)間的FSA 副本的可以進(jìn)行實(shí)時(shí)數(shù)據(jù)同步，也可以采取周期性數(shù)據(jù)同步的方式維護(hù)數(shù)據(jù)的一致性。實(shí)時(shí)性的數(shù)據(jù)同步需要在每次數(shù)據(jù)存儲(chǔ)時(shí)，所有存儲(chǔ)節(jié)點(diǎn)中的FSA陣列都需要即時(shí)更新，可以運(yùn)用基于副本的信息一致性策略[96]進(jìn)行個(gè)節(jié)點(diǎn)FSA陣列的實(shí)時(shí)同步，但由于用戶眾多且更新頻率較快的事實(shí)，會(huì)引起節(jié)點(diǎn)間數(shù)據(jù)實(shí)時(shí)同步的一致性維護(hù)策略較大的開銷。本文采取了周期性數(shù)據(jù)同步的策略進(jìn)行數(shù)據(jù)的一致性維護(hù)。周期性的方法則是指設(shè)置一定的時(shí)間間隔進(jìn)行FSA 副本的同步操作。但周期性同步數(shù)據(jù)的過程中，可能有多個(gè)節(jié)點(diǎn)存儲(chǔ)了新的數(shù)據(jù)塊，即FSA中有多條記錄進(jìn)行了修改

3　結(jié)束語(yǔ)

文章主要研究了集群內(nèi)部的全局重復(fù)數(shù)據(jù)刪除。刪除集群內(nèi)重復(fù)的數(shù)據(jù)，以節(jié)省存儲(chǔ)空間。通過 FSA 可以在所有存儲(chǔ)節(jié)點(diǎn)間進(jìn)行全局范圍的重復(fù)數(shù)據(jù)檢測(cè)，以消除各節(jié)點(diǎn)間的冗余數(shù)據(jù)，獲取較高的重復(fù)數(shù)據(jù)刪除率，最大程度地節(jié)省集群系統(tǒng)的存儲(chǔ)空間。

【參考文獻(xiàn)】

[1] Mitzenmacher M. Compressed Bloom filters[J]. Networking IEEE/ACM Transactions on, 2002, 10(5):604-612.

[2] 魏建生. 高性能重復(fù)數(shù)據(jù)檢測(cè)與刪除技術(shù)研究[D]. 華中科技大學(xué), 2012.

[3] 王龍翔, 張興軍, 朱國(guó)鋒等. 重復(fù)數(shù)據(jù)刪除中的無向圖遍歷分組預(yù)測(cè)方法[J]. 西安交通大學(xué)學(xué)報(bào), 2013, 47(10): 51-56.

陳曉（1991-），男，在讀碩士研究生，主要研究領(lǐng)域?yàn)樵朴?jì)算.

張龍軍，教授，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、云計(jì)算.

【作者簡(jiǎn)介】

基金項(xiàng)目：國(guó)家自然科學(xué)基金（NO.61003250）