一種面向容災(zāi)存儲系統(tǒng)的重復(fù)數(shù)據(jù)刪除方法

◆彭 剛

?

一種面向容災(zāi)存儲系統(tǒng)的重復(fù)數(shù)據(jù)刪除方法

◆彭 剛

（四川大學(xué)計算機(jī)學(xué)院 四川 610065）

針對海量數(shù)據(jù)的存儲和備份存在大量的冗余數(shù)據(jù)，造成存儲空間的巨大浪費問題，本文分析了現(xiàn)有的重復(fù)數(shù)據(jù)檢測和刪除技術(shù)，提出了一種面向容災(zāi)存儲系統(tǒng)的重復(fù)數(shù)據(jù)刪除方法——FWinnowing（Fast Winnowing ）。FWinnowing采用改進(jìn)后的Winnowing動態(tài)分塊算法對數(shù)據(jù)進(jìn)行分塊，使用MD5計算各個分塊的數(shù)據(jù)指紋值，通過檢索指紋庫來判斷指紋值是否已經(jīng)存在，從而判斷出該塊所對應(yīng)的數(shù)據(jù)是否重復(fù)，最終達(dá)到重復(fù)數(shù)據(jù)檢測和刪除的目的。本文對FWinnowing進(jìn)行了實驗驗證，結(jié)果表明該方法相比較現(xiàn)有的重復(fù)數(shù)據(jù)檢測和刪除方法，有效地降低了網(wǎng)絡(luò)傳輸流量并提高了重復(fù)數(shù)據(jù)檢測率。

容災(zāi)備份；重復(fù)數(shù)據(jù)；FWinnowing

0 引言

市場調(diào)研機(jī)構(gòu)IDC預(yù)計，未來全球數(shù)據(jù)總量年增長率將維持在50%左右，55%的數(shù)據(jù)需要進(jìn)行容災(zāi)備份并且應(yīng)用系統(tǒng)中有60%的數(shù)據(jù)是冗余的[1]。為了節(jié)省存儲資源，降低網(wǎng)絡(luò)數(shù)據(jù)傳輸帶寬重復(fù)刪除技術(shù)已成為一個熱門的研究課題?；谀壳霸擃I(lǐng)域的研究成果，比較知名的重復(fù)數(shù)據(jù)刪除技術(shù)應(yīng)用有基于全文件檢測的Windows2000單實例存儲系SIS、基于定長分塊檢測的歸檔存儲系統(tǒng)Venti、基于文件內(nèi)容（不定長分塊）檢測的低帶寬網(wǎng)絡(luò)系統(tǒng)LBFS等[2]。以上各應(yīng)用采取的文件分塊算法存在不同程度的缺陷。為此，本文設(shè)計并實現(xiàn)一種面向容災(zāi)備份存儲系統(tǒng)的更為有效的重復(fù)數(shù)據(jù)刪除方法——FWinnowing。

1 方法應(yīng)用場景

圖1 災(zāi)備系統(tǒng)網(wǎng)絡(luò)拓?fù)鋱D

如圖1所示，該圖為災(zāi)備系統(tǒng)網(wǎng)絡(luò)拓?fù)鋱D。當(dāng)備份發(fā)起時，裝有災(zāi)備代理的客戶端需要將不同時間點產(chǎn)生的備份文件進(jìn)行分塊，并且計算各個分塊的MD5值作為各個分塊的指紋值，并將各個分塊指紋信息發(fā)送給服務(wù)器。服務(wù)器通過檢索指紋庫查找該指紋值是否存在。如果存在，表明該塊數(shù)據(jù)為重復(fù)數(shù)據(jù)，僅需要將該數(shù)據(jù)塊的索引記錄到文件的元數(shù)據(jù)信息中；如果不存在，則需要將該數(shù)據(jù)塊上傳至服務(wù)器，并更新文件的元數(shù)據(jù)信息和數(shù)據(jù)塊索引信息。當(dāng)需要對文件進(jìn)行恢復(fù)時，只需要找到文件的元信息，根據(jù)文件元信息并通過數(shù)據(jù)塊索引文件找到指定的數(shù)據(jù)塊進(jìn)行文件重構(gòu)即可恢復(fù)已經(jīng)備份到服務(wù)器的文件。

2 方法采用的文件分塊算法

文件分塊算法按分塊粒度大小主要分為：定長分塊、可變長分塊和滑塊分塊。定長分塊算法對數(shù)據(jù)的插入和刪除非常敏感，不能解決比特偏移問題，冗余數(shù)據(jù)刪除率低；滑塊分塊算法會產(chǎn)生不定長的數(shù)據(jù)碎片[3]。因此，重復(fù)數(shù)據(jù)檢測和刪除技術(shù)通常采用可變長分塊算法，實際應(yīng)用中主要有CDC（Content-Defined Chunking）和Winnowing兩種算法。

2.1CDC算法原理

CDC是由麻省理工學(xué)院的BenjieChen等人發(fā)表的論文《A Low-Bandwidth Network File System》中提出，主要解決了固定長度分塊方法對插入位置敏感問題，并在重復(fù)數(shù)據(jù)刪除領(lǐng)域得到廣泛應(yīng)用。CDC的定義：給定一個Rabin指紋算法f,選取滑動窗口長度為w，并選取兩個正整數(shù)d和r(d

圖2 CDC數(shù)據(jù)分塊示意圖

CDC可變分塊重復(fù)數(shù)據(jù)檢測技術(shù)已應(yīng)用在P2P文件系統(tǒng)Pasta、Pastiche備份系統(tǒng)、Deep Store 歸檔存儲系統(tǒng)。但是，該算法存在一定的局限性：滑動窗口指紋值不符合條件時（f（w）mod d的值始終不等于r），會導(dǎo)致分塊過大，重復(fù)數(shù)據(jù)檢測率很低；d和r設(shè)置的太小，導(dǎo)致額外存儲分塊信息的開銷很大。

2.2 Winnowing算法原理

Winnowing算法在2003年由美國伊利諾斯大學(xué)的一位知名教授Saul Schleimer提出。該算法廣泛用于檢測兩個文件中是否有相同的內(nèi)容和是否存在剽竊現(xiàn)象。Winnowing算法首先設(shè)定參數(shù)k和w（k指進(jìn)行哈希的字節(jié)數(shù)，w指滑動窗口的大?。⑽臋n分成很多個長度為k的連續(xù)子串；其次，對文件每個子串通過公式（1）映射成一個整數(shù)，最終得到一個離散化的數(shù)值序列。

（b為基數(shù)，Tk表示滑動窗口中第k個字符，asc(Tk)表示該字符的ASCII值）

最后，使用滑動窗口掃描該數(shù)值序列，選取每個窗口內(nèi)最小的哈希值，將其對應(yīng)數(shù)據(jù)塊在文件中得偏移量作為文件的分割點。該算法的示例圖如圖3：

圖3 Winnowing算法示例圖

Winnowing有效地克服了對數(shù)據(jù)的插入敏感問題，并且相對于傳統(tǒng)的基于文件內(nèi)容分塊算法具有較好的穩(wěn)定性[3]。但是仍然存在一定的不足：當(dāng)基數(shù)b取值偏大時，可能造成基本數(shù)據(jù)溢出，此時需要構(gòu)建新的存儲結(jié)構(gòu)，造成計算復(fù)雜度大降低計算性能；選取最小散列值時，如果選取策略不當(dāng)可能會增加算法延時。

2.3FWinnowing算法原理

基于Winnowing算法的基礎(chǔ)上，本文對Winnowing算法所采用的哈希值計算和最小散列值選取策略兩方面加以改進(jìn)，得到一種更加高效的FWinnowing算法，并應(yīng)用于備份文件分塊中。具體改進(jìn)如下：

（1）哈希值計算方法的改進(jìn)

首先對公式（1）加以改進(jìn)，取基數(shù)b為2,并使用移位運算代替復(fù)雜乘法運算，提高算法運算效率，得到公式（2）如下：

根據(jù)哈希值計算規(guī)律發(fā)現(xiàn)，后一個子串哈希值計算可以在前一個哈希值的基礎(chǔ)上進(jìn)行兩次移位運算和兩次加法計算得到，如公式（3）所示：

改進(jìn)后的哈希值計算方法，在公式（1）的基礎(chǔ)上，大大降低了計算復(fù)雜度，節(jié)省了計算時間。

（2）最小散列值選取策略的改進(jìn)

Winnowing算法中關(guān)于數(shù)據(jù)塊分界點的選取只是提到選取滑動窗口中最小值作為數(shù)據(jù)塊的分界點，但是對于每個滑動窗口中的數(shù)據(jù)都要經(jīng)過整體排序找出最小值的話，這會增大時延，降低算法的執(zhí)行效率。對此本文改進(jìn)如下圖4所示：

圖4 FWinnowing最小散列值選取策略示例圖

經(jīng)過對Winnowing算法在哈希值計算和散列值選取策略兩方面的改進(jìn)后最終得到FWinnowing算法。FWinnowing的算法流程如圖5所示：

圖5 FWinnowing算法流程圖

3 實驗分析

3.1實驗數(shù)據(jù)集

本文實驗過程中，災(zāi)備客戶端和災(zāi)備服務(wù)端采用雙機(jī)直連的連接方式和100Mb/s網(wǎng)絡(luò)環(huán)境。實驗分別對多個相似數(shù)據(jù)集進(jìn)行備份，通過統(tǒng)計不同重復(fù)數(shù)據(jù)刪除方法在數(shù)據(jù)分塊所消耗的時間以及數(shù)據(jù)傳送過程中所產(chǎn)生的流量大小來驗證方法的效能。實驗數(shù)據(jù)集采用不同版本的Tomcat源碼解壓后的文件集，并對該文件集進(jìn)行處理（消除空白行、大量空格等），具體如表1所示：

表1 實驗數(shù)據(jù)集

3.2實驗數(shù)據(jù)分析

本文對實驗數(shù)據(jù)集進(jìn)行備份，通過統(tǒng)計將備份數(shù)據(jù)上傳至服務(wù)端所消耗的網(wǎng)絡(luò)流量來衡量各個方法的重復(fù)數(shù)據(jù)檢測和刪除的執(zhí)行效率。

圖6是在設(shè)定備份文件分塊大小區(qū)間（介于128B和1024B之間）情況下，比較CDC方法和FWinowing方法的重復(fù)數(shù)據(jù)檢測率實驗對比數(shù)據(jù)數(shù)據(jù)，結(jié)果顯示FWinnow方法相比較CDC方法具有更好的重復(fù)數(shù)據(jù)檢測率。圖7是對備份數(shù)據(jù)經(jīng)過CDC和FWinnowing兩種不同方法的重復(fù)數(shù)據(jù)檢測和刪除后上傳至災(zāi)備中心產(chǎn)生的網(wǎng)絡(luò)流量對比數(shù)據(jù)。實驗結(jié)果顯示FWinnowing方法相對于CDC方法具有較低的網(wǎng)絡(luò)流量。

圖6 重復(fù)數(shù)據(jù)塊檢測率對比數(shù)據(jù)

圖7 數(shù)據(jù)傳輸網(wǎng)絡(luò)流量對比數(shù)據(jù)

4 結(jié)束語

本文從災(zāi)備存儲系統(tǒng)對重復(fù)數(shù)據(jù)檢測的需求現(xiàn)狀出發(fā)，分析了現(xiàn)有的重復(fù)數(shù)據(jù)檢測方法存在的不足，將Winnowing算法改進(jìn)后得到的FWinnowing算法并應(yīng)用在文件分塊上，通過對比實驗驗證了FWinnowing方法相比較現(xiàn)有的方法擁有較低的網(wǎng)絡(luò)流量和較好的重復(fù)數(shù)據(jù)檢測率。因此，本文提出的重復(fù)數(shù)據(jù)刪除方法為后續(xù)該領(lǐng)域的研究提供了有益的探索和借鑒。

[1]敖莉, 舒繼武, 李明強(qiáng).重復(fù)數(shù)據(jù)刪除技術(shù)[J].Journal of Software, 2010.

[2]畢朝國, 徐小龍.一種云存儲系統(tǒng)中重復(fù)數(shù)據(jù)刪除機(jī)制[J].計算機(jī)應(yīng)用研究, 2014.

[3]許艷艷, 雷迎春, 龔奕利.基于可變長分塊的分布式文件設(shè)計與實現(xiàn)[J].體系結(jié)構(gòu)與軟件技術(shù), 2016.

[4]馬曉旭.基于云存儲的災(zāi)難備份與恢復(fù)技術(shù)研究[D].四川大學(xué), 2012.

[5]Bobbarjung DR, Jagannathan S, Dubnicki C. Improving duplicate elimination in storage systems. ACM Trans. on Storage, 2006.