集群重復數據刪除策略的研究

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

?

集群重復數據刪除策略的研究

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

【文章摘要】

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

【關鍵詞】

重復數據刪除；指紋摘要陣列；超塊

0　引言

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

1　Bloom Filter

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

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

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

2　基于 Bloom Filter的全局數據刪重策略

2.1全局去重策略的設計與實現

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

圖1　指紋摘要陣列

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

圖2　重復數據檢測流程

2.2存儲節點的去重策略

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

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

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

2.3指紋摘要陣列FSA的同步

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

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

3　結束語

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

【參考文獻】

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

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

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

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

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

【作者簡介】

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