周斌　王晶奇　張瑩

摘要：重復數(shù)據(jù)刪除技術是一種數(shù)據(jù)縮減技術，它可以減少對物理存儲空間的需求，從而滿足日益增長的數(shù)據(jù)存儲需求。該文將Bloom過濾器應用于重復數(shù)據(jù)刪除技術中，加入兩級fingerprint映射表，經過多個高效率的散列函數(shù)的計算，以引入較小的“假陽性錯誤率”為代價，增大磁盤的空余量。

關鍵詞：布隆過濾器；重復數(shù)據(jù)刪除；數(shù)據(jù)指紋；假陽性錯誤

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）08-1793-03

1 重復數(shù)據(jù)刪除和布隆過濾器的概念

1.1 重復數(shù)據(jù)刪除技術的定義[1]

重復數(shù)據(jù)刪除是一種數(shù)據(jù)縮減技術，通常用于基于磁盤的備份系統(tǒng)，旨在減少存儲系統(tǒng)中使用的存儲容量。它的工作方式是在某個時間周期內查找不同文件中不同位置的重復可變大小數(shù)據(jù)塊。重復的數(shù)據(jù)塊用指示符取代。高度冗余的數(shù)據(jù)集（例如備份數(shù)據(jù)）從數(shù)據(jù)重復刪除技術的獲益極大；用戶可以實現(xiàn)10比1至50比1的縮減比。而且，重復數(shù)據(jù)刪除技術可以允許用戶的不同站點之間進行高效，經濟的備份數(shù)據(jù)復制。

重復數(shù)據(jù)刪除技術支持在已有的磁盤設備上存儲更多的備份數(shù)據(jù)。因此采用“重復數(shù)據(jù)刪除”技術可以增加保存?zhèn)浞輸?shù)據(jù)的時間，減少數(shù)據(jù)中心的消耗，降低成本。

1.2 Bloom過濾器

1.2.1 Bloom過濾算法

Bloom過濾算法[2]，是由巴頓布隆于 1970年提出的，它實現(xiàn)的基礎是一個很長的二進制位向量和一系列隨機散列函數(shù)。Bloom Filter是一種基于散列的查找算法，用于查找一個元素是否在集合中，并用“1”（可能存在），“0”（不存在）來表示，將Kb的空間降到Bit的數(shù)量級，減少了磁盤的存儲壓力。前面之所以將“1”表示成可能存在，是因為隨著新數(shù)據(jù)的不斷插入，fingerprint映射表的的“1”越來越多，那么假如新插入的數(shù)據(jù)從未出現(xiàn)在源數(shù)據(jù)中，但他的幾個映射位都置“1”，這時該算法的缺點就出現(xiàn)了，也就是“假陽性錯誤率”，在增加了錯誤率這個因素之后，Bloom Filter通過允許少量的錯誤來節(jié)省大量的存儲空間。

1.2.2 Bloom算法的原理

下面介紹bloom過濾器的結構與實現(xiàn)原理[3]：

當原數(shù)據(jù)為空，那么fingerprint映射表也為空，則狀態(tài)位都置“0”，如圖1。

新插入的數(shù)據(jù)塊a經過MD5計算后，將其結果再經過bloom算法中的n個hash函數(shù)（此時n=4）計算后生成4個“1”，那么fingerprint中的某4位將被置“1”，如圖2。

當有新數(shù)據(jù)塊繼續(xù)要插入時，如果通過上面方法計算后的fingerprint中的某4位已經置“1”，那么進行第二級bloom算法的計算，但只要有fingerprint映射表中的某一位沒有被置“1”，那么新插入的數(shù)據(jù)就沒有在原數(shù)據(jù)中出現(xiàn)，將“0”位置“1”，如圖3。

2 重復數(shù)據(jù)的刪除

重復數(shù)據(jù)刪除技術的性能受多方面因素的影響：對何種數(shù)據(jù)應用重復刪除，何時、何地進行消重，以及如何進行消重，其實現(xiàn)過程主要包括：文件數(shù)據(jù)塊化、數(shù)據(jù)塊指紋化、數(shù)據(jù)塊指紋的管理。

2.1 文件數(shù)據(jù)塊化

重復數(shù)據(jù)刪除的首要任務就是將文件數(shù)據(jù)塊化，其數(shù)據(jù)分塊的主要算法有三種：定長切分（FPS）、變長切分（CDC）以及滑動切分算法（SB）。

2.2 數(shù)據(jù)塊指紋化

數(shù)據(jù)塊指紋化是指將已切分的數(shù)據(jù)塊經過Hash算法計算得到指紋的過程。MD5是計算機安全領域廣泛使用的hash函數(shù)，MD5值是128位的，正好滿足數(shù)據(jù)指紋小的要求，理想情況下不同數(shù)據(jù)塊的指紋是不同的，但是hash函數(shù)中hash值之間的“碰撞”是必不可少的，那么盡量減少沖突將需要更多的計算。

雖然經過MD5計算的hash值的“碰撞”率很低，但是只要有一個例外發(fā)生，如果實現(xiàn)不做任何處理，那么可能導致數(shù)據(jù)塊的丟失。下面以圖4為例介紹該系統(tǒng)如何消除沖突的過程。

其實現(xiàn)過程如下：

1）將待處理的數(shù)據(jù)塊bk1進行MD5計算得到數(shù)據(jù)指紋fp1

2）將fp1與fingerprint比較，判斷是否發(fā)生碰撞，如果沒有沖突，說明該數(shù)據(jù)塊在源文件中未出現(xiàn)，將fp1寫入fingerprint，并將數(shù)據(jù)塊寫入源文件。

3）如果發(fā)生碰撞，那么將fingerprint中相同的fp1對應的數(shù)據(jù)塊bk1與bk1比較，如果數(shù)據(jù)塊相同，證明是重復數(shù)據(jù)，則不做處理。

4）如果經過比較數(shù)據(jù)塊不同，那么將fp1與bk1寫入相應的fingerprint與文件。

3.3 內存消耗的計算與原數(shù)據(jù)塊大小的關系

一級Bloom Filter 所需的Finger Print 和二級Bloom Filter 所需的Finger Print的大小。初步計算100GB的存儲數(shù)據(jù)需要大約25MB的內存空間，其中hash函數(shù)的個數(shù)為8個。計算如下：100GB / 8KB （原數(shù)據(jù)）= 12.5 * 10^9（個數(shù)據(jù)塊），12.5 * 10^9 * 2 * 8（bit） = 25 MB（內存空間）內存空間也就是一級fingerprint的大小。經過一級bloom filter計算以后，”假陽性”錯誤率減少至少60%，所以二級bloom filter還需1 / 3的fingerprint的大小。

3.4 Hash函數(shù)的個數(shù)與“假陽性錯誤率”的關系

Bloom Filter要靠多個哈希函數(shù)將集合映射到位數(shù)組中，那么應該選擇幾個哈希函數(shù)才能使元素查詢時的錯誤率降到最低呢？這里有兩個互斥的理由：如果哈希函數(shù)的個數(shù)多，那么在對一個不屬于集合的元素進行查詢時得到0的概率就大；但另一方面，如果哈希函數(shù)的個數(shù)少，那么位數(shù)組中的0就多。本系統(tǒng)將設置幾組hash函數(shù)進行實驗，分別計算出各組hash函數(shù)對“假陽性”錯誤率的影響，從而選擇最有hash函數(shù)的個數(shù)。分別為一級bloom filter設置4個hash函數(shù)、6個、8個hash函數(shù)進行實驗。除次之外，“假陽性”錯誤率還與位向量長度和filter里的keys的數(shù)量有關。

3.5 Hash映射函數(shù)的設計

判斷一個元素是否存在于一個指定集合中，可能并不需要把所有集合元素的原始信息都保存下來，我們只需要記住“存在狀態(tài)”即可，這往往僅僅需要幾個bit就可表示。Hash函數(shù)可將一個元素映射成一個位數(shù)組中一個點，為了降低碰撞率可采用多個hash函數(shù)將元素映射成多個點。這樣一來，只要看看幾個位點是0或1 就可以判斷某個元素是否存在于集合當中。既不能無限制的增加hash函數(shù)的個數(shù)以減少碰撞率，所以各個hash映射函數(shù)的設計是個重要的問題，如果幾個hash函數(shù)不是均勻分布，那么只會增加查詢的開銷，反而降低插入或刪除的效率，降低性能。

在原fingerprint的基礎上建立一級fingerprint和二級fingerprint，相當于經過三級fingerprint的計算來減少假陽性錯誤率的發(fā)生。一個hash函數(shù)設計如下：

一級fingerprint的輸入N = MD5計算的結果 = 128Bit = 27，

一級fingerprint的長度 = 128Bit，二級fingerprint的長度 = 25MB，這里分配225Byte = 32MB的大小空間，也就是需要內存的空間。

過程描述：

1）取一級128位的MD5_KEY的前7位，取其值的結果將一級fingerprint的相應那一位置“1”。

2）若一級fingerprint的某一位已經置“1”，那么將MD5_KEY置“1”的那一位開始的25的值計算出來作為二級fingerprint的映射位，并把二級fingerprint相應的那一位置“1”，如果取MD5_KEY的25位時取到末尾仍不夠25位，那么從MD5_KEY開始部位繼續(xù)取，直到取到25位。如：前7位二進制表示為：1100111其值為103，那么如果從第103位取到第127位正好是25位，所以當前7位的值大于等于103時，將從開始處取M位（0 <= M <= 25）。

3）Hash的擴展，將前7位從0位開始變成從n位，n >= 0，這樣會產生N個hash函數(shù)?；蛘邚牡?27位向前取，相當于取MD5_KEY的質數(shù)再進行一級、二級bloom算法。

4 結束語

本文討論了bloom算法在重復數(shù)據(jù)刪除技術中的應用，通過高效率的散列函數(shù)的計算得到數(shù)據(jù)指紋，當有新數(shù)據(jù)要查找時，直接在指紋映射表中進行，很大程度上減少了內存的消耗，提高了檢索的效率，但面對很大數(shù)量級的數(shù)據(jù)，不同數(shù)據(jù)塊的指紋會出現(xiàn)“碰撞”，我們通過設計多級哈希函數(shù)來映射指紋，經過多層fingerprint的過濾，最后一層出現(xiàn)的“碰撞”的幾率已經很少，然后再通過數(shù)據(jù)塊之間的逐位的比較，從根本上消除了“碰撞”，保證了用戶數(shù)據(jù)的安全性。

參考文獻：

[1] 敖莉，舒繼武，李明強.重復數(shù)據(jù)刪除技術[J].軟件學報， 2010，21（5）.

[2] Bloom B H..Space/time trade-offs in hash coding with allowable errors[C].Commun. ACM， 1970，13（7）：422–426.

[3] 謝鯤，閔應驊，張大方，等.分檔布魯姆過濾器的查詢算法[J].計算機學報，2007，30 （4） ：597-607.