Winnowing指紋串匹配的重復(fù)數(shù)據(jù)刪除算法

王青松，葛 慧

(遼寧大學(xué) 信息學(xué)院，沈陽(yáng) 110036)

0 引言

目前數(shù)據(jù)激增問題使數(shù)據(jù)中心處理的數(shù)據(jù)量呈現(xiàn)爆炸式增長(zhǎng)，數(shù)據(jù)存儲(chǔ)、備份和恢復(fù)所需的時(shí)間和容量也隨之增大，給存儲(chǔ)系統(tǒng)帶來(lái)了沉重的負(fù)擔(dān)。由于數(shù)據(jù)來(lái)源不同，許多數(shù)據(jù)被反復(fù)存儲(chǔ)，造成了大量的數(shù)據(jù)冗余，尤其在備份系統(tǒng)中更加突出[1]。重復(fù)數(shù)據(jù)刪除技術(shù)[2-3]的出現(xiàn)引起了研究者的關(guān)注，它不僅能夠減少存儲(chǔ)和處理的數(shù)據(jù)量，節(jié)約數(shù)據(jù)的管理和存儲(chǔ)成本，同時(shí)提高了網(wǎng)絡(luò)通信的速度，成為降低數(shù)據(jù)中心冗余數(shù)據(jù)量的有效手段。

為了在存儲(chǔ)系統(tǒng)中充分利用重復(fù)數(shù)據(jù)刪除技術(shù)，減少數(shù)據(jù)的最終積累量，縮短消除冗余數(shù)據(jù)的時(shí)間，許多經(jīng)典的重復(fù)數(shù)據(jù)刪除算法被提出。EB(Extreme Binning)算法[4]利用文件相似性，使用最小塊簽名作為文件的特征，只在內(nèi)存中保存文件的代表塊ID，有效減小了內(nèi)存占用。然而，最小塊ID作為主索引，一方面重刪率相對(duì)較低，另一方面數(shù)據(jù)分塊算法影響最小塊簽名，不同的分塊算法所產(chǎn)生的最小塊可能不同，從而影響重刪的準(zhǔn)確性。Bloom filter算法[5]利用K個(gè)Hash函數(shù)將數(shù)據(jù)塊MD5值映射到m位的向量V中，減少頻繁的I/O操作，但存在假正例(False Positives)誤識(shí)別率，并且無(wú)法從Bloom Filter集合中刪除元素，在需要數(shù)據(jù)修改的場(chǎng)景下不能使用。張滬寅等[6]提出了用戶感知的重復(fù)數(shù)據(jù)刪除算法，根據(jù)用戶相關(guān)度，以用戶為單位，減少了數(shù)據(jù)空間局部性，但對(duì)于非人為產(chǎn)生的數(shù)據(jù)，其相似性計(jì)算準(zhǔn)確度較低。

以上算法在數(shù)據(jù)分塊時(shí)均采用了可變長(zhǎng)度分塊(Content-Defined Chunking, CDC)算法，相對(duì)于以文件為粒度，數(shù)據(jù)塊級(jí)粒度能夠檢測(cè)到文件內(nèi)部的重復(fù)數(shù)據(jù)，因此，目前大多數(shù)重復(fù)數(shù)據(jù)刪除算法均采用數(shù)據(jù)塊為粒度。然而，在現(xiàn)有的許多塊級(jí)重復(fù)數(shù)據(jù)刪除算法中，存在著數(shù)據(jù)分塊效果較差[7]的問題。數(shù)據(jù)的分塊大小很難控制，并且需要預(yù)先設(shè)置大量的參數(shù)，指紋計(jì)算和對(duì)比的開銷較大，分塊邊界條件也難以滿足，而這些問題往往會(huì)影響重刪操作的性能和準(zhǔn)確性。因此，目前大多數(shù)數(shù)據(jù)分塊算法都不能使重復(fù)數(shù)據(jù)刪除算法達(dá)到理想的效果。

本文針對(duì)分塊算法中以上幾點(diǎn)不足，提出了一種Winnowing指紋串匹配的重復(fù)數(shù)據(jù)刪除算法(Deduplication algorithm based on Winnowing Fingerprint Matching, DWFM)，對(duì)基于內(nèi)容的可變長(zhǎng)度分塊(CDC)算法進(jìn)行了改進(jìn)。實(shí)驗(yàn)結(jié)果表明，本文算法能夠?qū)?shù)據(jù)流進(jìn)行合理分塊，指紋計(jì)算和對(duì)比開銷較小，克服了現(xiàn)有許多分塊算法中的不足。

1 可變長(zhǎng)度分塊算法

數(shù)據(jù)分塊[8]是重復(fù)數(shù)據(jù)刪除算法的前提，其性能的優(yōu)劣直接影響將來(lái)重復(fù)數(shù)據(jù)刪除算法的好壞。數(shù)據(jù)分塊通常有兩種類型：固定長(zhǎng)度分塊(Fixed-Sized Partitioning, FSP)[9]和可變長(zhǎng)度分塊(CDC)[10]。FSP將數(shù)據(jù)分成長(zhǎng)度固定的數(shù)據(jù)塊，以同樣大小的數(shù)據(jù)塊為單位進(jìn)行重刪，F(xiàn)SP算法對(duì)數(shù)據(jù)修改很敏感，在數(shù)據(jù)經(jīng)常變化時(shí)效果較差；而CDC根據(jù)Rabin指紋算法[11]通過(guò)一個(gè)特殊大小的滑動(dòng)窗口依次分割數(shù)據(jù)，其分塊大小隨著數(shù)據(jù)內(nèi)容的變化而變化，并且修改只會(huì)影響到修改數(shù)據(jù)周圍的少量數(shù)據(jù)，適用于數(shù)據(jù)經(jīng)常修改的情況[10]。

CDC算法使用一個(gè)特定寬度w的滑動(dòng)窗口，從數(shù)據(jù)的開始處以字節(jié)長(zhǎng)度滑動(dòng)，當(dāng)w大小的數(shù)據(jù)被裝載完畢后，計(jì)算其指紋(Hash)。算法預(yù)先給定兩個(gè)參數(shù)D和r,且r

然而，應(yīng)用場(chǎng)景不同，待檢測(cè)的源數(shù)據(jù)有很大的區(qū)別[12]：可能是文本數(shù)據(jù)或圖像數(shù)據(jù)，也可能是結(jié)構(gòu)化數(shù)據(jù)或非結(jié)構(gòu)化數(shù)據(jù)，還可能是壓縮數(shù)據(jù)或無(wú)壓縮數(shù)據(jù)等；并且源數(shù)據(jù)中重復(fù)部分的數(shù)量和分布也有很大差別，不重復(fù)內(nèi)容、少量重復(fù)的內(nèi)容和大量重復(fù)的內(nèi)容共存，使分塊大小難以選擇；而且目前的大多數(shù)分塊算法對(duì)所有場(chǎng)景均使用相同的分塊策略，使其在面對(duì)大規(guī)模復(fù)雜類型數(shù)據(jù)時(shí)性能往往不理想，通常表現(xiàn)出以下幾點(diǎn)不足：

1)滑動(dòng)窗口w的大小難以選擇。w的大小直接影響分塊的大小，由于重復(fù)數(shù)據(jù)刪除的數(shù)量和所需的時(shí)間與塊大小呈負(fù)相關(guān)，在實(shí)際的應(yīng)用環(huán)境中，使用較小分塊大小來(lái)提高重刪率是不可行的。

2)需要預(yù)先人工設(shè)定參數(shù)D和r,選取不當(dāng)將導(dǎo)致分塊效果較差。

3)指紋計(jì)算和對(duì)比開銷較大。CDC算法使用Rabin算法進(jìn)行數(shù)據(jù)分塊時(shí)，滑動(dòng)窗口每滑動(dòng)一字節(jié)，需要復(fù)雜多項(xiàng)式取模一次來(lái)計(jì)算指紋，邊界條件取模一次來(lái)確定塊邊界，并且產(chǎn)生大量的無(wú)用指紋，嚴(yán)重影響了重復(fù)數(shù)據(jù)刪除的性能。

4)分塊邊界條件難以滿足。fmodD=r的分塊邊界條件會(huì)因?yàn)閰?shù)設(shè)定和待檢測(cè)數(shù)據(jù)的特征而出現(xiàn)很難滿足條件的情況，直接造成分塊過(guò)大而使用硬分塊，嚴(yán)重時(shí)甚至退化為FSP，或者出現(xiàn)大量細(xì)碎分塊，加大元數(shù)據(jù)和索引的開銷。

2 算法設(shè)計(jì)

本文算法針對(duì)CDC算法的以上不足，首先利用分塊大小預(yù)測(cè)模型，得出最佳分塊大??；然后設(shè)計(jì)了編碼指紋代替Rabin指紋；最后，在確定分塊邊界條件時(shí)，提出了指紋字符串匹配的分塊算法來(lái)代替CDC算法中利用參數(shù)邊界條件的方式，并使用Winnowing算法計(jì)算文件整體指紋時(shí)的方法快速選擇指紋對(duì)比模式串。算法不僅解決了分塊大小難以控制的問題，同時(shí)不用設(shè)置參數(shù)，計(jì)算開銷較小，本文算法的結(jié)構(gòu)如圖1所示。

圖1 本文算法整體框架 Fig. 1 Framework of the proposed algorithm

2.1 分塊大小預(yù)測(cè)模型

本文針對(duì)CDC算法分塊大小的局限性，引入了預(yù)測(cè)模型。許多研究發(fā)現(xiàn)，現(xiàn)有的眾多分塊技術(shù)在選擇平均分塊大小時(shí)都是基于幾何分布[13]的。王龍翔等[14]論證了內(nèi)容分塊算法中預(yù)期分塊長(zhǎng)度對(duì)重復(fù)數(shù)據(jù)刪除率的影響。Hirsch等[15]提出了一種以自然方式控制塊大小分布的方法。實(shí)驗(yàn)結(jié)果證明，該算法的均值和標(biāo)準(zhǔn)偏差非常接近于常數(shù)變化，對(duì)于變量概率，標(biāo)準(zhǔn)偏差要小得多，大多數(shù)值均接近平均值。應(yīng)用于不同截止條件的分布圖呈刺猬形，并且?guī)в幸粋€(gè)基本的高斯鐘形曲線。因此算法能夠較準(zhǔn)確地預(yù)測(cè)平均分塊大小，本文算法使用該分塊模型預(yù)測(cè)預(yù)期分塊大小，過(guò)程如下。

1)設(shè)L表示給定塊的長(zhǎng)度，是一個(gè)隨機(jī)變量，它的期望值即為預(yù)期分塊大小。得到塊大小L(L≥M)的概率是第一次M實(shí)驗(yàn)失敗的概率，l表示指數(shù)范圍內(nèi)當(dāng)前塊大小M的上界，M滿足以下關(guān)系：

(1)

2)當(dāng)L≥M時(shí)的概率可以用以下公式求出：

(2)

3)從中可以得到當(dāng)L=M時(shí)的概率：

Pr(L=M)=Pr(L≥M)-Pr(L≥M-1)

(3)

4)則使用以下公式來(lái)計(jì)算給定條件時(shí)的預(yù)期塊大小w:

(4)

通過(guò)該分塊預(yù)測(cè)模型獲得的預(yù)期大小w,避免了參數(shù)設(shè)置的人為干涉，一定程度上解決了CDC算法中分塊大小難以控制的問題。

2.2 Winnowing指紋算法

針對(duì)CDC算法使用Rabin算法計(jì)算數(shù)據(jù)塊指紋時(shí)的計(jì)算開銷較大等問題，引入了Winnowing算法[16]。該算法在2003年由Schleimer等提出，經(jīng)常用于檢測(cè)文件或網(wǎng)頁(yè)中的相同內(nèi)容，來(lái)判斷抄襲[17]等行為。本文使用Winnowing算法來(lái)計(jì)算指紋是因?yàn)樵撍惴ㄒ詳?shù)字ASCII/文字Unicode編碼作為指紋，計(jì)算開銷非常小，并且指紋的構(gòu)成簡(jiǎn)單，便于以后的指紋對(duì)比操作。DWFM中在映射指紋時(shí)，使用w單位大小對(duì)待檢測(cè)數(shù)據(jù)進(jìn)行分組，其中w是由2.1節(jié)中分塊預(yù)測(cè)模型計(jì)算所得到的預(yù)期分塊大小，使用Winnowing算法計(jì)算數(shù)據(jù)塊指紋的過(guò)程如下。

1)設(shè)待檢測(cè)數(shù)據(jù)流D(D中含有n個(gè)字符)，使用預(yù)測(cè)大小w對(duì)D中所有長(zhǎng)度為w的塊進(jìn)行指紋映射，如塊C1(C1包含字符1至w)可映射為Hash(C1)，同樣地，C2(C2包含字符2至w+1)可映射為Hash(C2)，則共產(chǎn)生了n-w+1個(gè)指紋，Hash(C1),Hash(C2),…,Hash(Cn-w+1)。其中指紋Hash(Ci)(i=1,2,…,n-w+1)與塊Ci{i,i+1,…,s+w-1}相對(duì)應(yīng)。

2)將n-w+1個(gè)子塊用以a為基數(shù)的整數(shù)表示，映射為以a為參數(shù)的整數(shù)x(0≤x≤bk)，設(shè)Code(C1)是數(shù)據(jù)塊C1的ASCII/Unicode編碼值，即為C1的指紋值Hash(C1)，則數(shù)據(jù)塊C1的指紋值Hash(C1)可用以下公式計(jì)算：

Hash(C1)=Code(C[1])aw-1+Code(C[2])aw-2+…+Code(C[w])=Hash(C[1])+Hash(C[2])+…+Hash(C[w])

(5)

3)C2的指紋值Hash(C2)可以通過(guò)以下公式由C1的指紋值直接求得：

Hash(C2)=(Hash(C1)-C[1]aw-1)a+

Code(C[w+1])

(6)

4)將n-w+1個(gè)指紋Hash(C1),Hash(C2),…,Hash(Cn-w+1)組成指紋序列Hc,通過(guò)公式可發(fā)現(xiàn)，后一個(gè)塊的Hash值與前一塊的Hash值的相似性較大。這是由于后一塊的指紋值是由前一塊向后滑動(dòng)一個(gè)字節(jié)得到的，且僅需要在前一塊Hash值的基礎(chǔ)上通過(guò)兩次加法和兩次乘法得到。相比Rabin算法通過(guò)兩個(gè)復(fù)雜多項(xiàng)式取模運(yùn)算來(lái)得到Hash指紋，Winnowing算法使用ASCII/Unicode作為指紋較好地降低了計(jì)算開銷。

2.3 模式串Pw的設(shè)計(jì)

本文算法設(shè)計(jì)了底層指紋字符串匹配的分塊算法確定塊邊界，代替了CDC算法中利用Rabin參數(shù)取模來(lái)進(jìn)行分塊的方式，因此需要設(shè)置模式串Pw。由于Winnowing算法確定全文件指紋的過(guò)程是基于文件內(nèi)容的，并且是從指紋組合中選擇指紋信息，其選擇結(jié)果體現(xiàn)了數(shù)據(jù)的本身特性，有利于將來(lái)的分塊與檢測(cè)。因此將此過(guò)程引入到模式串選取的過(guò)程中，設(shè)計(jì)了模式串Pw的選取規(guī)則，使Pw的選擇更加符合重復(fù)數(shù)據(jù)刪除算法的要求。在選擇Pw過(guò)程中對(duì)Hc進(jìn)行分組時(shí)，使用預(yù)期分塊大小w為分組大小基數(shù)，使Pw的選擇遵從最佳分塊場(chǎng)景，具體的選取規(guī)則如圖2所示。

圖2 模式串Pw的選取過(guò)程 Fig. 2 Selection of pattern string Pw

1)對(duì)于待檢測(cè)數(shù)據(jù)流D{1,2,…,n}的Hash值序列Hc,以w大小的滑動(dòng)窗口長(zhǎng)度沿著Hc滑動(dòng)，得到指紋分組h1,h2,…,hi；

2)對(duì)于每一個(gè)指紋組hm(m=1,2,…,i,i為指紋組個(gè)數(shù))，取其組內(nèi)最小的哈希值作為該組的代表，若連續(xù)的多個(gè)塊具有相同的最小值，則選擇最右側(cè)的一組；

3)將最小值組成長(zhǎng)度為w的序列，作為下一步分塊時(shí)的模式串Pw,算法描述如下。

算法1 模式串選取算法(Pattern String Selection Algorithm, PSSA)。

輸入 待檢測(cè)數(shù)據(jù)流D;

輸出 模式串Pw。

1)

BEGIN

2)

將D使用預(yù)測(cè)分塊大小w進(jìn)行分塊

3)

FOR eachCido

//對(duì)于每一個(gè)字塊Ci

4)

Hash(Ci)=getCode(Ci);

//對(duì)每個(gè)長(zhǎng)度為w的塊取其編碼值作為Hash值

5)

Hc=add(Hash(Ci));

//生成指紋字符串序列Hc

6)

將Hc使用w大小進(jìn)行分組;

7)

FOR eachHashwdo

//對(duì)每個(gè)指紋分組Hashw

8)

hmin(i)=getMinhi();

//找出每組指紋Hashw中的最小值hmin(i)

9)

Pw=add(hmin(i));

//將所有最小值指紋組合形成長(zhǎng)度為w模式串

10)

END

2.4 Winnowing指紋串匹配分塊算法

CDC算法進(jìn)行數(shù)據(jù)分塊時(shí)，基本原理和最大的弊端都是需要預(yù)先設(shè)定參數(shù)D和r,當(dāng)指紋值f與D進(jìn)行模運(yùn)算后結(jié)果等于r時(shí)才建立分塊。然而，一方面參數(shù)選擇依據(jù)和準(zhǔn)確性很難確定；另一方面邊界條件在實(shí)際應(yīng)用中常常會(huì)因?yàn)閰?shù)選擇不當(dāng)?shù)葐栴}出現(xiàn)長(zhǎng)時(shí)間不能滿足的情況，只能在最大可容忍范圍Cmax處進(jìn)行硬分塊，甚至退化成FSP算法。且應(yīng)用場(chǎng)景不同，其數(shù)據(jù)的特性也相差很多，為不同類型的數(shù)據(jù)使用相同的參數(shù)選取策略是不嚴(yán)謹(jǐn)?shù)摹?/p>

而Rabin指紋算法尋找分塊邊界時(shí)最底層原理是字符串匹配問題[18]。因此本文算法從其底層原理出發(fā)，摒棄設(shè)置參數(shù)和分塊條件等，將數(shù)據(jù)分塊問題轉(zhuǎn)化為指紋字符串的匹配問題，設(shè)計(jì)了指紋串匹配分塊算法。結(jié)合上述求出的數(shù)據(jù)塊指紋Hash(Ci)(i=1,2,3,…,n-w+1)，使用模式串Pw,進(jìn)行塊指紋和模式串Pw的匹配。DWFM在映射指紋、選擇Pw和滑動(dòng)窗口大小時(shí)均使用預(yù)測(cè)大小w作為基準(zhǔn)，是為了使分塊大小和結(jié)果都體現(xiàn)最佳分塊大小時(shí)的特性。

當(dāng)某一塊Ci(i=1,2,3,…,n-w+1)的指紋Hash(Ci)與模式串Pw的指紋值Hash(Pw)匹配成功時(shí)，在此塊的右側(cè)邊界創(chuàng)建一個(gè)分塊。若超過(guò)分塊大小上界Cmax都未能匹配成功，則在Cmax處創(chuàng)建分塊。

在匹配過(guò)程中，可以使用Sunday[19]等字符串匹配算法來(lái)加速匹配，當(dāng)匹配失敗時(shí)，能夠盡量多地跳過(guò)不可能匹配的字符，Sunday匹配過(guò)程如圖3所示。

圖3 Sunday算法匹配過(guò)程 Fig. 3 Matching process of Sunday algorithm

Rabin算法在分塊時(shí)每滑動(dòng)一字節(jié)需要模運(yùn)算判斷一次，不滿足分塊條件時(shí)也不能跳過(guò)數(shù)據(jù)；相比之下，本文的分塊算法不僅無(wú)需設(shè)置參數(shù)，而且處理速度較快。指紋串匹配分塊算法描述如下。

算法2 指紋串匹配分塊算法(Chunking Algorithm based on Fingerprint Matching, CAFM)。

輸入 數(shù)據(jù)塊指紋序列Hc;

輸出 分塊序列Cki。

1)

BEGIN

2)

d=0；

//d代表當(dāng)前滑動(dòng)窗口所滑過(guò)的字符長(zhǎng)度

3)

WHILE(d≤Cmax&&窗口內(nèi)的字符長(zhǎng)度等于w)

//當(dāng)d的長(zhǎng)度小于分塊上界Cmax

//w代表滑動(dòng)窗口的大小即預(yù)期分塊大小

4)

sliding window, matching fingerprints use Sunday;

//使用Sunday算法進(jìn)行指紋串匹配

5)

IFHash(Ci) ==Hash(Pw) THEN;

//當(dāng)數(shù)據(jù)塊Ci的指紋等于模式串Pw的指紋

6)

create a new chunkCki;

//若塊指紋與模式串指紋匹配成功，則建立分塊

7)

window come toCkinext position;

//滑動(dòng)窗口來(lái)到塊Cki的下一個(gè)位置

8)

d=0;

//將d的長(zhǎng)度置為零

9)

ELSE

10)

skip characters not possible to match;

//向右滑過(guò)盡可能多的不匹配字節(jié)

11)

d=d+skip.length;

//d的長(zhǎng)度變化為d的長(zhǎng)度加上滑過(guò)的長(zhǎng)度skip.length

12)

IFd>CmaxTHEN;

13)

Ci==Cmax;

//Cmax范圍內(nèi)沒有匹配成功，則在Cmax處進(jìn)行硬分塊

14)

creatCki

//其中i=1,2,…,k,k代表分塊個(gè)數(shù)

15)

window come toCkinext position;

16)

d=0;

17)

END

2.5 指紋串匹配的重復(fù)數(shù)據(jù)刪除算法

對(duì)待檢測(cè)數(shù)據(jù)D使用CAFM算法進(jìn)行分塊后，設(shè)計(jì)了Winnowing指紋串匹配的重復(fù)數(shù)據(jù)刪除算法(DWFM)。使用MD5算法[20]為每一個(gè)數(shù)據(jù)塊生成一個(gè)獨(dú)一無(wú)二的指紋，由于MD5指紋具有唯一性，且無(wú)論任何人對(duì)數(shù)據(jù)作了任何修改，即使是很小的改動(dòng)，其MD5值也會(huì)發(fā)生很大變化，因此MD5值能夠準(zhǔn)確檢測(cè)數(shù)據(jù)塊是否重復(fù)，保證重復(fù)數(shù)據(jù)塊檢測(cè)結(jié)果的正確性。

在進(jìn)行重復(fù)數(shù)據(jù)刪除時(shí)，將每一個(gè)待檢測(cè)塊的指紋值MD5(Di)(i=1,2,…,k)與存儲(chǔ)或備份系統(tǒng)中的數(shù)據(jù)塊進(jìn)行指紋對(duì)比。若待檢測(cè)數(shù)據(jù)塊Di的指紋與系統(tǒng)中某一塊的指紋完全相同，則說(shuō)明Di為重復(fù)數(shù)據(jù)塊，直接刪除不予存儲(chǔ)，并更新索引表，將該塊的引用次數(shù)加1；否則，說(shuō)明系統(tǒng)中沒有與Di內(nèi)容重復(fù)的數(shù)據(jù)塊，則將Di存儲(chǔ)到系統(tǒng)中，并在元數(shù)據(jù)表中維護(hù)一條Di的信息。

3 算法實(shí)驗(yàn)分析和結(jié)果

實(shí)驗(yàn)使用Java語(yǔ)言實(shí)現(xiàn)了DWFM，測(cè)試在Windows環(huán)境下進(jìn)行，操作系統(tǒng)為Windows 7 Ultimate，硬件環(huán)境為Intel Pentium CPU G3200 @ 3.00 GHz處理器，4 GB內(nèi)存容量，500 GB的SAS硬盤，千兆以太網(wǎng)。實(shí)驗(yàn)?zāi)M構(gòu)建了一個(gè)客戶端和一個(gè)服務(wù)器節(jié)點(diǎn)，為了檢驗(yàn)對(duì)不同的文件類型采用不同的分塊策略下的算法性能，實(shí)驗(yàn)采用了多種類型的真實(shí)數(shù)據(jù)集，包括：TXT、DOC、HTML、PPT、PDF、VMDK等。其中，TXT、DOC、PPT、PDF類型數(shù)據(jù)由AWS、Google以及Twitter數(shù)據(jù)平臺(tái)獲取，包括大量的用戶狀態(tài)、影評(píng)和公開信息；HTML數(shù)據(jù)集從微博中爬取，信息的多次轉(zhuǎn)發(fā)具有重復(fù)性；VMDK數(shù)據(jù)集采用ubuntu8.04與14.04兩個(gè)版本。獲取的不同類型數(shù)據(jù)集的大小和數(shù)量相近，方便對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)一化分析。另外，同一類型數(shù)據(jù)的內(nèi)容為同一領(lǐng)域，保證了數(shù)據(jù)之間具有相似性和重復(fù)性。實(shí)驗(yàn)數(shù)據(jù)集如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab. 1 Datasets of experiment

實(shí)驗(yàn)具體內(nèi)容：在服務(wù)器端存放由表1中數(shù)據(jù)集組成的文件集合A,每次實(shí)驗(yàn)分別使用FSP、CDC和CAFM分塊算法對(duì)A進(jìn)行分塊，形成原始數(shù)據(jù)。改變A的內(nèi)容存放在客戶端，使其與A有重復(fù)率r,形成待檢測(cè)數(shù)據(jù)集B。隨機(jī)連續(xù)地從客戶端向服務(wù)器端發(fā)送文件，并采用與服務(wù)器端相同的分塊算法分塊后進(jìn)行重復(fù)數(shù)據(jù)刪除。實(shí)驗(yàn)驗(yàn)證了不同分塊算法對(duì)不同類型數(shù)據(jù)重刪率的影響，以及不同重復(fù)率r時(shí)的算法時(shí)間。

為了驗(yàn)證重復(fù)數(shù)據(jù)刪除算法的效果，實(shí)驗(yàn)設(shè)置了重復(fù)刪除率：R=重復(fù)刪除數(shù)據(jù)量/原始數(shù)據(jù)總量，重刪率實(shí)驗(yàn)結(jié)果如圖4所示。無(wú)論采用哪種分塊的重復(fù)數(shù)據(jù)刪除算法都能在一定程度上減少數(shù)據(jù)的最終存儲(chǔ)量；除VMDK類型外，對(duì)于所有類型的文件，DWFM的重刪率都要高于FSP與CDC算法。例如對(duì)TXT數(shù)據(jù)，DWFM重刪率高于FSP算法13.557%，高于CDC算法10.289%。由于DWFM對(duì)數(shù)據(jù)進(jìn)行分塊預(yù)測(cè)，根據(jù)數(shù)據(jù)自身的類型和特性來(lái)選擇合適的分塊大小，因此其分塊效果更加符合重復(fù)數(shù)據(jù)刪除的邊界條件，使得算法的重刪率較其他兩種算法高出很多。三種重復(fù)數(shù)據(jù)刪除算法對(duì)TXT、DOC、HTML和VMDK類型的文件重刪效果都較好，而對(duì)PPT和PDF類型的數(shù)據(jù)相對(duì)較差，這主要是因?yàn)镻PT類型中的數(shù)據(jù)形式多變，且位置隨意，需要對(duì)數(shù)據(jù)進(jìn)行嚴(yán)格的預(yù)處理，因此影響了重刪率。

圖4 不同文件類型的算法重刪率對(duì)比 Fig. 4 Comparison of deduplication rates for different file types

為了驗(yàn)證不同重復(fù)率r以及重復(fù)分布情況對(duì)重復(fù)數(shù)據(jù)刪除性能的影響，對(duì)TXT數(shù)據(jù)集進(jìn)行了相同數(shù)據(jù)集、不同重復(fù)率下的處理時(shí)間實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖5所示。DWFM處理時(shí)間較短，且處理時(shí)間隨r的增加呈下降趨勢(shì)，逐漸趨近于FSP。當(dāng)重復(fù)率r為0.7時(shí)，DWFM相對(duì)CDC算法改進(jìn)最大，處理時(shí)間縮短了15.6 min，算法性能提升了18.31%。

圖5 不同重復(fù)率r時(shí)的算法時(shí)間對(duì)比 Fig. 5 Algorithm time comparison at different rate r

結(jié)合理論分析和實(shí)驗(yàn)結(jié)果，對(duì)DWFM的復(fù)雜度進(jìn)行全面分析，結(jié)果如表2所示，DWFM所消耗的時(shí)間復(fù)雜度包括以下幾點(diǎn)：

1)CAFM在進(jìn)行數(shù)據(jù)分塊之前，需要通過(guò)預(yù)測(cè)模型選取最佳分塊大小，由預(yù)測(cè)算法公式可得，其時(shí)間復(fù)雜度為Tw=O(n)；

2)使用Winnowing算法計(jì)算待檢測(cè)數(shù)據(jù)流D中每個(gè)長(zhǎng)度為w的子塊的指紋值，其時(shí)間復(fù)雜度為Th=O(n-w+1)，其中n為D中的字符數(shù)；

3)選擇模式串Pw的時(shí)間復(fù)雜度Tp=O(i+w-1)，其中i代表指紋組個(gè)數(shù)；

4)使用CAFM和Sunday算法進(jìn)行分塊的時(shí)間復(fù)雜度Tc=O(n)；

5)MD5指紋計(jì)算與對(duì)比等重復(fù)數(shù)據(jù)檢測(cè)操作的時(shí)間復(fù)雜度為Td=O(m)，其中m表示需要對(duì)比的數(shù)據(jù)塊個(gè)數(shù)。

因此，DWFM總的時(shí)間復(fù)雜度T為：

T=Tw+Th+Tp+Tc+Td=2O(n)+O(m)+

O(n-w+1)+O(i+w-1)

(7) 表2 算法復(fù)雜度對(duì)比Tab. 2 Algorithm complexity comparison

由表2可得，F(xiàn)SP算法采用固定分塊大小，只需分塊后計(jì)算MD5指紋即可判斷是否為重復(fù)數(shù)據(jù)，因此算法時(shí)間最短；但由于無(wú)法檢測(cè)到文件內(nèi)部重復(fù)，因此在實(shí)際中應(yīng)用較少。而CDC算法首先需要使用Rabin算法計(jì)算指紋，然后利用參數(shù)取模條件來(lái)尋找分塊邊界，最后計(jì)算MD5指紋來(lái)判斷重復(fù)，且在分塊和指紋比對(duì)過(guò)程中無(wú)法跳過(guò)數(shù)據(jù)，只能按字節(jié)依次進(jìn)行判斷，因此產(chǎn)生了大量的無(wú)用指紋，增加了指紋開銷和算法時(shí)間。DWFM在分塊前需要預(yù)測(cè)分塊大小，產(chǎn)生一定的時(shí)間復(fù)雜度，但在分塊時(shí)使用ASCII/Unicode指紋，而非Rabin指紋，計(jì)算開銷較小；而且利用指紋字符串匹配的方式來(lái)確定分塊邊界，在匹配失敗時(shí)能跳過(guò)盡可能多的字符，較顯著地減少了指紋計(jì)算次數(shù)。綜上對(duì)比，DWFM擁有更好的應(yīng)用前景。

4 結(jié)語(yǔ)

本文算法將Winnowing算法引入重復(fù)數(shù)據(jù)刪除來(lái)減少指紋計(jì)算開銷，在分塊時(shí)無(wú)需預(yù)先設(shè)置參數(shù)，而是根據(jù)Rabin的底層原理，設(shè)計(jì)了指紋串匹配的分塊算法。該算法特別適合用來(lái)解決數(shù)據(jù)塊級(jí)重復(fù)數(shù)據(jù)刪除時(shí)的復(fù)雜分塊問題，尤其是在待檢測(cè)數(shù)據(jù)類型多變、重復(fù)內(nèi)容分布不均的情況時(shí)，能夠得出更合理的分塊大小，在文件內(nèi)部檢測(cè)到更多的重復(fù)數(shù)據(jù)。通過(guò)實(shí)驗(yàn)與FSP和CDC算法相比，本文算法分塊大小更加準(zhǔn)確，計(jì)算和對(duì)比開銷較小，且重復(fù)檢測(cè)沒有誤判率，擁有更好的應(yīng)用前景。

參考文獻(xiàn)(References)

[1] SUN Y, ZENG C Y, CHUNG J, et al. Online data deduplication for in-memory big-data analytic systems [C]// Proceedings of 2017 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2017:1-7.

[2] ZHENG Y, DING W X, YU X X, et al. Deduplication on encrypted big data in cloud [J]. IEEE Transactions on Big Data, 2016, 2(2): 138-150.

[3] 熊金波,張媛媛,李鳳華,等.云環(huán)境中數(shù)據(jù)安全去重研究進(jìn)展[J].通信學(xué)報(bào),2016,37(11):169-180.(XIONG J B, ZHANG Y Y, LI F H, et al. Research progress on secure data deduplication in cloud [J]. Journal on Communications, 2016, 37(11): 169-180.)

[4] BHAGWAT D, ESHGHI K, LONG D D E, et al. Extreme binning: scalable, parallel deduplication for chunk-based file backup [C]// Proceedings of 2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems. Piscataway, NJ: IEEE, 2009: 1-9.

[5] LI Z B, HE K J, LIN F N, et al. Deduplication of files in cloud storage based on differential bloom filter [C]// Proceedings of 2016 7th IEEE International Conference on Software Engineering and Service Science. Piscataway, NJ: IEEE, 2016: 111-114.

[6] 張滬寅,周景才,陳毅波,等.用戶感知的重復(fù)數(shù)據(jù)刪除算法[J].軟件學(xué)報(bào),2015,26(10):2581-2595.(ZHANG H Y, ZHOU J C, CHEN Y B, et al. User-aware de-duplication algorithm [J]. Journal of Software, 2015, 26(10): 2581-2595.)

[7] WIDODO R N S, LIM H, ATIQUZZAMAN M. A new content-defined chunking algorithm for data deduplication in cloud storage [J]. Future Generation Computer Systems, 2017, 71: 145-156.

[8] WANG G P, CHEN S Y, LIN M W, et al. SBBS: a sliding blocking algorithm with backtracking sub-blocks for duplicate data detection [J]. Expert Systems with Applications, 2014, 41(5): 2415-2423.

[9] 鄧雪峰,孫瑞志,張永瀚,等.基于數(shù)據(jù)位圖的滑動(dòng)分塊算法[J].計(jì)算機(jī)研究與發(fā)展,2014,51(Suppl.):30-38.(DENG X F, SUN R Z, ZHANG Y H, et al. Sliding blocking algorithm based on data bitmap [J]. Journal of Computer Research and Development, 2014, 51(Suppl.): 30-38.)

[10] ZHANG Y C, HONG J, DAN F, et al. AE: an asymmetric extremum content defined chunking algorithm for fast and bandwidth-efficient data deduplication [C]// Proceedings of 2015 IEEE Conference on Computer Communications. Washington, DC: IEEE Computer Society, 2015: 1337-1345.

[11] SU H N, ZHENG D, ZHANG Y H. An efficient and secure deduplication scheme based on Rabin fingerprinting in cloud storage [C]// Proceedings of 2017 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC). Piscataway, NJ: IEEE, 2017: 833-836.

[12] 閻芳,李元章,張全新,等.基于對(duì)象的OpenXML復(fù)合文件去重方法研究[J].計(jì)算機(jī)研究與發(fā)展,2015,52(7):1546-1557.(YAN F, LI Y Z, ZHANG Q X, et al. Object-based data de-duplication method for OpenXML compound files [J]. Journal of Computer Research and Development, 2015, 52(7): 1546-1557.)

[13] MIN J, YOON D, WON Y. Efficient deduplication techniques for modern backup operation [J]. IEEE Transactions on Computers, 2011, 60(6): 824-840.

[14] 王龍翔,董小社,張興軍,等.內(nèi)容分塊算法中預(yù)期分塊長(zhǎng)度對(duì)重復(fù)數(shù)據(jù)刪除率的影響[J].西安交通大學(xué)學(xué)報(bào), 2016,50(12):73-78.(WANG L X, DONG X S, ZHANG X J, et al. Influence of expected chunk size on deduplication ratio in content defined chunking algorithm [J]. Journal of Xi’an Jiaotong University, 2016, 50(12): 73-78.)

[15] HIRSCH M, KLEIN S T, SHAPIRA D, et al. Controlling the chunk-size in deduplication systems [C]// Proceedings of the 2015 Prague Stringology Conference. Prague: PSC, 2015: 78-89.

[16] SCHLEIMER S, WILKERSON D S, AIKEN A. Winnowing: local algorithms for document fingerprinting [C]// Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2003: 76-85.

[17] LULU L, BELKHOUCHE B, HAROUS S. Overview of fingerprinting methods for local text reuse detection [C]// Proceedings of the 2016 International Conference on Computing and Network Communications. Piscataway, NJ: IEEE, 2016:1-6.

[18] MEYER D T, BOLOSKY W J. A study of practical deduplication [J]. ACM Transactions on Storage, 2012,7(4):1-20.

[19] 朱永強(qiáng),秦志光,江雪.基于Sunday算法的改良單模式匹配算法[J].計(jì)算機(jī)應(yīng)用,2014,34(1):208-212.(ZHU Y Q, QIN Z G, JIANG X. Improved single pattern matching algorithm based on Sunday algorithm [J]. Journal of Computer Applications, 2014, 34(1): 208-212.)

[20] CHO E M, KOSHIBA T. Big data cloud deduplication based on verifiable hash convergent group signcryption [C]// Proceedings of 2017 IEEE 3rd International Conference on Big Data Computing Service and Applications. Piscataway, NJ: IEEE, 2017: 265-270.

This work is partially supported by the National Natural Science Foundation of China (61502215).

WANGQingsong, born in 1974, M. S., associate professor. His research interests include big data, data mining.

GEHui, born in 1991, M. S. candidate. Her research interests include deduplication.