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

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

?

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

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

【文章摘要】

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

【關鍵詞】

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

0　引言

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

1　Bloom Filter

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

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

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

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

2.1全局去重策略的設計與實現(xiàn)

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

圖1　指紋摘要陣列

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

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

2.2存儲節(jié)點的去重策略

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

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

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

2.3指紋摘要陣列FSA的同步

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

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

3　結束語

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

【參考文獻】

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

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

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

陳曉（1991-），男，在讀碩士研究生，主要研究領域為云計算.

張龍軍，教授，主要研究方向為網(wǎng)絡安全、云計算.

【作者簡介】

基金項目：國家自然科學基金（NO.61003250）