◆彭 剛

?

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

◆彭 剛

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

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

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

0 引言

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

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

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

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

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

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

2.1CDC算法原理

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

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

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

2.2 Winnowing算法原理

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

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

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

圖3 Winnowing算法示例圖

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

2.3FWinnowing算法原理

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

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

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

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

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

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

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

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

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

圖5 FWinnowing算法流程圖

3 實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)數(shù)據(jù)集

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

3.2實(shí)驗(yàn)數(shù)據(jù)分析

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

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

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

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

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

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

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

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

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

[4]馬曉旭.基于云存儲(chǔ)的災(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.