郭玉劍，曾志浩

(湖南工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 株洲 412000)

一種用于重復(fù)數(shù)據(jù)刪除的非對(duì)稱最大值分塊算法研究

郭玉劍，曾志浩

(湖南工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 株洲412000)

分塊是一種將文件劃分成更小文件的過(guò)程，該方法被廣泛應(yīng)用在重復(fù)數(shù)據(jù)刪除系統(tǒng)中。針對(duì)傳統(tǒng)的基于內(nèi)容分塊(CDC)中面臨的高額計(jì)算開銷問(wèn)題，提出了一種稱為非對(duì)稱最大值的分塊算法(CAAM)。采用字節(jié)值代替哈希值來(lái)聲明切點(diǎn)，利用固定大小窗口和可變大小窗口來(lái)查找作為切點(diǎn)的最大值，并且允許在保留內(nèi)容定義分塊(CDC)屬性的同時(shí)進(jìn)行較少的計(jì)算開銷。最后將CAAM與現(xiàn)有的基于散列和無(wú)哈希的分塊算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明，CAAM算法比其他算法具有更低的計(jì)算開銷和更高的分塊吞吐量。

重復(fù)數(shù)據(jù)刪除；非對(duì)稱窗口；內(nèi)容定義分塊；無(wú)哈希分塊；切點(diǎn)

0 引言

根據(jù)國(guó)際數(shù)據(jù)公司(IDC)的調(diào)查研究，2013年全球數(shù)字信息產(chǎn)生量約為4.4 ZB，到2020年將達(dá)到44 ZB[1]，如何有效地存儲(chǔ)和傳輸如此海量的數(shù)據(jù)對(duì)技術(shù)人員提出了巨大的挑戰(zhàn)。然而，最近的研究表明數(shù)據(jù)倉(cāng)庫(kù)中存在大量的重復(fù)數(shù)據(jù)[2]。因此，一種高效的降低存儲(chǔ)冗余的無(wú)損壓縮技術(shù)——重復(fù)數(shù)據(jù)刪除，成為解決這一難題的重要方法之一。由于顯著的數(shù)據(jù)縮減率，塊級(jí)去重被應(yīng)用于各種領(lǐng)域，例如存儲(chǔ)系統(tǒng)[3-4]、文件傳輸系統(tǒng)[5]和遠(yuǎn)程文件系統(tǒng)[6]。

基于塊級(jí)的重復(fù)數(shù)據(jù)刪除方案是將數(shù)據(jù)流分解成多個(gè)數(shù)據(jù)塊，并且散列每個(gè)塊，其中使用散列函數(shù)生成各個(gè)數(shù)據(jù)塊的指紋，在新的數(shù)據(jù)流進(jìn)入存儲(chǔ)系統(tǒng)之前，先通過(guò)分塊算法將其分解成多個(gè)數(shù)據(jù)塊，然后通過(guò)對(duì)比新數(shù)據(jù)塊的數(shù)據(jù)指紋來(lái)確定是否存儲(chǔ)。從這個(gè)過(guò)程中可以看出，重復(fù)數(shù)據(jù)刪除必經(jīng)過(guò)四個(gè)階段，即分塊、指紋、索引和寫入。而分塊作為重復(fù)數(shù)據(jù)刪除的第一個(gè)關(guān)鍵階段，如何選擇有效的分塊算法成為重復(fù)數(shù)據(jù)刪除中一個(gè)重要難題。

基于Rabin指紋的內(nèi)容定義分塊(CDC)算法[7]是最著名的分塊算法之一。這種方法使用Rabin滾動(dòng)哈希來(lái)尋找切割點(diǎn)，它解決了固定長(zhǎng)度分塊中關(guān)于字節(jié)移位的問(wèn)題。但是由于滾動(dòng)哈希是在滑動(dòng)窗口移動(dòng)過(guò)程中計(jì)算哈希值，因此這種算法在散列過(guò)程中需要消耗大量時(shí)間計(jì)算哈希值。不同于Rabin分塊算法，BJ?RNER N等人提出的局部最大算法(LMC)[8]是利用文件和滑動(dòng)窗口的字節(jié)值來(lái)確定切割點(diǎn)，雖然這種方法不需要哈希計(jì)算，但是它需要比較每個(gè)字節(jié)來(lái)進(jìn)行分塊。文獻(xiàn)[9]中提出的基于非對(duì)稱極值(AE)的內(nèi)容分塊算法，使用固定窗口和可變大小的窗口來(lái)確定切割點(diǎn)，其中極值位于兩個(gè)窗口之間。不同于局部最大算法，AE算法不需要使用滑動(dòng)窗口來(lái)確定切割點(diǎn)，因此該算法只需要很少的字節(jié)比較。盡管相對(duì)于LMC算法來(lái)說(shuō)AE算法的比較次數(shù)較少，但是仍然需要高額的計(jì)算量。

針對(duì)分塊中需要大量計(jì)算開銷的問(wèn)題，本文提出了一個(gè)基于非對(duì)稱最大的分塊算法(CAAM)。該算法與AE算法類似，使用兩個(gè)窗口：固定長(zhǎng)度窗口和可變長(zhǎng)度窗口。與AE算法不同，CAAM算法對(duì)窗口使用了不同的位置。窗口位置從固定長(zhǎng)度窗口開始，然后是可變大小的窗口和最大的字節(jié)。切割點(diǎn)位于塊的末尾。這種配置一定程度上減少了比較次數(shù)，而且在重復(fù)數(shù)據(jù)刪除吞吐量方面也優(yōu)于AE算法。

1 背景與挑戰(zhàn)

1.1背景

大部分?jǐn)?shù)據(jù)壓縮技術(shù)都是采用分塊，例如，重復(fù)數(shù)據(jù)刪除、遠(yuǎn)程差分壓縮。重復(fù)數(shù)據(jù)刪除的工作原理就是利用這種方法來(lái)消除文件與文件之間的重復(fù)數(shù)據(jù)。在重復(fù)數(shù)據(jù)刪除中，分塊算法是實(shí)現(xiàn)高去重率的一種重要方法。通過(guò)選擇正確的分塊算法，可以節(jié)省消重時(shí)間和硬件空間。

分塊可以被分成兩類：(1)基于文件的分塊；(2)基于數(shù)據(jù)塊的分塊?；谖募姆謮K意味著將整個(gè)文件視為一個(gè)數(shù)據(jù)塊，而基于數(shù)據(jù)塊的分塊是將文件劃分成多個(gè)塊。當(dāng)文件被分割成塊時(shí)，塊大小可以是固定長(zhǎng)度大小，也可以是可變長(zhǎng)度大小。固定長(zhǎng)度分塊具有分塊速度優(yōu)勢(shì)，但是當(dāng)數(shù)據(jù)流有n個(gè)字節(jié)插入時(shí)，之后的所有數(shù)據(jù)都會(huì)偏移n個(gè)字節(jié)。在進(jìn)行數(shù)據(jù)分塊時(shí)，這n字節(jié)之后的數(shù)據(jù)塊就會(huì)變成新的數(shù)據(jù)塊，這樣必然大大降低重復(fù)數(shù)據(jù)刪除率?；趦?nèi)容的分塊(CDC)是通過(guò)將文件分成可變大小的數(shù)據(jù)塊來(lái)解決字節(jié)移位問(wèn)題的，該算法通過(guò)利用文件內(nèi)部的特征來(lái)找到切點(diǎn)，因此當(dāng)文件移位時(shí)，只有幾個(gè)塊受影響。CDC與固定長(zhǎng)度分塊相比，具有更高的消重率。

CDC允許使用任何根據(jù)文件內(nèi)部特征條件來(lái)發(fā)現(xiàn)切割點(diǎn)。例如在基于散列的分塊算法中，它是根據(jù)滑動(dòng)窗口和散列函數(shù)來(lái)發(fā)現(xiàn)切割點(diǎn)。而文獻(xiàn)[8-9]提出的算法都是根據(jù)字節(jié)值來(lái)尋找切割點(diǎn)。除了利用散列和字節(jié)來(lái)確認(rèn)切割點(diǎn)，神經(jīng)網(wǎng)絡(luò)和機(jī)器學(xué)習(xí)也被用來(lái)尋找切割點(diǎn)，但是它們的計(jì)算開銷遠(yuǎn)高于利用散列和字節(jié)的方法來(lái)找到切割點(diǎn)。

分塊算法在重復(fù)數(shù)據(jù)刪除系統(tǒng)中具有決定性的作用，但是塊管理也是重復(fù)數(shù)據(jù)刪除中的一個(gè)重要環(huán)節(jié)，當(dāng)數(shù)據(jù)塊逐步增多時(shí)，塊的索引也將成為一大難題。近年有許多關(guān)于塊索引的研究，其中主要集中在利用緩存[10-11]、布隆過(guò)濾器[12]或者布谷鳥過(guò)濾器[13]等來(lái)減少數(shù)據(jù)塊搜索時(shí)間。

1.2挑戰(zhàn)

相較于固定大小分塊，CDC分塊擁有更多的優(yōu)點(diǎn)。然而，CDC分塊算法在處理數(shù)據(jù)流程中稍微消耗時(shí)間，特別是對(duì)于處理能力相對(duì)較小的設(shè)備，例如移動(dòng)設(shè)備和物聯(lián)網(wǎng)服務(wù)等。在之前的工作中，一般采用的是基于Rabin的分塊算法來(lái)消除重復(fù)數(shù)據(jù)。但這種方法在移動(dòng)應(yīng)用時(shí)需要大量的處理時(shí)間。

在討論和評(píng)價(jià)各個(gè)分塊算法性能時(shí)，需要聲明三個(gè)用于評(píng)價(jià)算法的標(biāo)準(zhǔn)：

(1)內(nèi)容依賴：分塊算法應(yīng)該根據(jù)文件內(nèi)容的內(nèi)在特征來(lái)定義切點(diǎn)。這樣可以抵抗字節(jié)移位，而且可以在海量數(shù)據(jù)消除更多重復(fù)數(shù)據(jù)。

(2)較低的塊大小差異：依據(jù)算法產(chǎn)生的塊需要有較低的塊大小差異，因?yàn)閴K大小差異很大程度上影響著重刪率。為了限制塊大小差異，需要限制塊的最大或者最小值。然而，這樣做卻影響了算法基于內(nèi)容依賴的屬性，并且也不能有效抵抗字節(jié)移位。

(3)高吞吐量和重復(fù)檢測(cè)：分塊算法應(yīng)該在重復(fù)數(shù)據(jù)刪除效率和計(jì)算開銷兩者中保持良好的平衡。

2 基于非對(duì)稱最大分塊算法設(shè)計(jì)

為了實(shí)現(xiàn)低計(jì)算開銷和字節(jié)移位抗性算法的目標(biāo)，在AE算法的基礎(chǔ)上提出了基于非對(duì)稱最大算法(CAAM)。與AE算法類似，CAAM也使用兩個(gè)窗口：固定大小窗口和可變大小窗口。但是窗口的放置位置和AE算法不同。在CAAM算法中固定窗口位于塊的開始處，然后是可變窗口和最大字節(jié)值。

CAAM算法首先在固定窗口中尋找最大字節(jié)值，如果緊接固定窗口的字節(jié)比固定窗口所有值都要大，則該值便作為最大值字節(jié)，同時(shí)切點(diǎn)也被確定。否則，算法繼續(xù)移動(dòng)到下個(gè)字節(jié)，直到找到最大值為止。因此算法的最小塊的大小是w+1，其中w是固定窗口大小。查找切點(diǎn)的偽代碼具體如下：

輸入：input string,Str;length of the string,L;

輸出：cut-point I;

Predefinedvalued:window size,w;

FunctionCAAMChunkning (Str,L)

i=1;

while(ilt;L)

if Str[i].valuegt;=max.value then

if igt;w then

return i

end if

max.value=Str[i].value

max.position=i

end if

i=i+1

end while

end function

在上述算法中詳細(xì)說(shuō)明了CAAM算法中的分塊細(xì)節(jié)。從該算法可以看出，CAAM通過(guò)在固定窗口中尋找到最大值來(lái)減少計(jì)算時(shí)間。而AE算法是需要先通過(guò)尋找最小值，然后再計(jì)算切點(diǎn)的位置，在此過(guò)程中就需要更多的計(jì)算開銷。

為了更好地展示每個(gè)算法是如何工作的，通過(guò)圖1中的示例來(lái)詳細(xì)說(shuō)明。其中規(guī)定使用相同的字節(jié)流，定義總字節(jié)數(shù)為14，窗口大小設(shè)定為5位?；赗abin的分塊算法中滑動(dòng)窗口從塊的開始處向后開始滑動(dòng)，如圖1(a)所示。在該示例的開頭，滑動(dòng)窗口的內(nèi)容為0×89504EA10D。如果窗口的哈希值與預(yù)定值不匹配，則左移窗口，滑動(dòng)到下個(gè)字節(jié)，直到窗口的哈希值與預(yù)定值匹配為止。在圖1(a)的示例中，0×0D0A1AEA48的哈希值與預(yù)定值相匹配，從而最終確定切點(diǎn)位置為0×48右側(cè)。

LMC算法和基于Rabin的分塊算法類似，同樣使用滑動(dòng)窗口，如圖1(b)所示。其中滑動(dòng)窗口是由兩個(gè)固定大小窗口組成的，當(dāng)發(fā)現(xiàn)位于兩個(gè)窗口中間的字節(jié)大于窗口中所有字節(jié)時(shí)，切點(diǎn)位置便是窗口中間最大值的位置。

表1 測(cè)試中使用的數(shù)據(jù)集

與LMC算法不同，AE算法需要掃描每個(gè)字節(jié)來(lái)找到切點(diǎn)，如圖1(c)所示。在AE算法中，固定窗口始終位于待掃描字節(jié)的右側(cè)。AE算法從字節(jié)流的左側(cè)依次往右開始掃描，并將掃描的字節(jié)值與固定窗口中的所有字節(jié)進(jìn)行比較。當(dāng)字節(jié)大小大于固定窗口中的所有字節(jié)時(shí)，則確定切點(diǎn)。由此可見，當(dāng)?shù)谝粋€(gè)字節(jié)滿足條件時(shí)，可變窗口的值是0字節(jié)。在圖1(c)的示例中，算法從0×89掃描到0×EA時(shí)發(fā)現(xiàn)切點(diǎn)，因?yàn)?×EA大于固定窗口中的任何字節(jié)。其中確認(rèn)切點(diǎn)位于固定窗口的右側(cè)。

圖1 Rabin、LMC、AE和CAAM算法的工作示意圖

CAAM算法也需要逐字掃描每個(gè)字節(jié)與窗口中的最大值相比較。CAAM通過(guò)查找到固定窗口中的最大值來(lái)啟動(dòng)。在圖1(d)中可以看出，固定窗口中的最大值是0×A1。等到算法掃描完固定窗口后，將窗口后的每個(gè)字節(jié)與窗口中的最大值相比較。當(dāng)掃描到的某個(gè)字節(jié)大于固定窗口中的最大字節(jié)時(shí)，則說(shuō)明找到切點(diǎn)。從圖中可以看出，0×EA是切割點(diǎn)。

表2 被發(fā)現(xiàn)的重復(fù)數(shù)據(jù)量

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

3.1實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)將基于Rabin的分塊算法、LMC算法、AE算法和CAAM算法做比較，評(píng)估CAAM算法的分塊吞吐量和重刪率。硬件環(huán)境：主機(jī)為CPU Intel i7 6700 3.6 GHz，4核8線程，12 GB DDR4,2 133 MHz和三星850 Evo 256GB SSD。SSD通過(guò)SATA3接口連接。實(shí)驗(yàn)采用三種不同形式的數(shù)據(jù)集，第一個(gè)數(shù)據(jù)集是由多個(gè)Linux發(fā)行版的編譯，它們?cè)诿總€(gè)文件中的不同位置都有大量的重復(fù)數(shù)據(jù)。第二個(gè)數(shù)據(jù)集是由10個(gè)23 min的H.264編碼視頻組成的。第三個(gè)數(shù)據(jù)集是來(lái)自網(wǎng)絡(luò)的轉(zhuǎn)儲(chǔ)文件。詳細(xì)信息如表1所示。

3.2分塊吞吐量對(duì)比

本節(jié)通過(guò)分塊吞吐量和每秒保存的字節(jié)(BSPS)來(lái)評(píng)估三個(gè)算法之間的分塊性能。分塊吞吐量是根據(jù)原始數(shù)據(jù)集的大小與分塊時(shí)間的比值得到的，而每秒保存的字節(jié)是根據(jù)被找到的重復(fù)數(shù)據(jù)除以原始數(shù)據(jù)集，最后乘以分塊吞吐量得到的。具體公式如下：

通過(guò)實(shí)驗(yàn)結(jié)果表明，與其他算法相比，CAAM算法具有更高的吞吐量。雖然在三種數(shù)據(jù)集中發(fā)現(xiàn)重復(fù)數(shù)據(jù)的數(shù)量上，CAAM算法要略低于AE算法，如表2所示。但是CAAM算法在分塊吞吐量上要比AE算法高出42%～49%，如圖2、3所示。而且從數(shù)據(jù)集的處理時(shí)間上來(lái)看，CAAM算法也要優(yōu)于其他算法，如表3所示?？傮w而言，CAAM在吞吐量方面要優(yōu)于其他算法。

表3 不同數(shù)據(jù)集處理時(shí)間

圖2 四種算法的分塊吞吐量

圖3 四種算法在不同數(shù)據(jù)集下每秒保存的字節(jié)數(shù)

4 結(jié)論

本文分別討論了Rabin算法、LMC算法和AE算法三種算法的分塊過(guò)程，并分析了它們的分塊性能。針對(duì)它們?cè)诜謮K吞吐量上的低效率問(wèn)題，提出了一種新的分塊算法——基于非對(duì)稱的最大值分塊算法(CAAM)。本文利用三種不同類型的數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)證明，與其他分塊算法相比，CAAM具有更低的計(jì)算開銷和高分塊吞吐量。本方法還有一些未解決的問(wèn)題，例如：在分塊之前如何確定固定窗口的大小，研究固定窗口大小對(duì)分塊的影響將是接下來(lái)的工作之一。

[1] VERNON T. The digital universe of opportunities: rich data and the increasing value of the internet of things[EB/OL].(2014-04-10)[2017-02-14] https://www.emc.com/leadership/digital-universe/2014iview/executive-summary.htm.

[2] QUINLAN S,DORWARD S. Awarded best paper!-venti: a new approach to archival data storage[C].Proceedings of the 1st USENIX Conference on File and Storage Technologies. USENIX Association, 2002:89-101.

[3] Zhang Xuecheng, Deng Mingzhu. An Overview on Data Deduplication Techniques[M].Berlin: Springer International Publishing, 2017.

[4] 孫虎威, 靳嘉偉, 張晶,等. 重復(fù)數(shù)據(jù)刪除算法在VTL系統(tǒng)中的應(yīng)用研究[J]. 微型機(jī)與應(yīng)用, 2013, 32(6):82-85.

[5] 顧瑜, 劉川意, 孫林春,等. 帶重復(fù)數(shù)據(jù)刪除的大規(guī)模存儲(chǔ)系統(tǒng)可靠性保證[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2010(5):739-744.

[6] SANADHYA S, SIVAKUMAR R, KIM K H, et al. Asymmetric caching: improved network deduplication for mobile devices[C].International Conference on Mobile Computing and Networking. ACM, 2012:161-172.

[7] RABIN M O. Fingerprinting by random polynomials[J]. Center for Research in Computing Technology, 1981,15(81): 15-18.

[8] BJ?RNER N, BLASS A, GUREVICH Y. Content-dependent chunking for differential compression, the local maximum approach[J]. Journal of Computer amp; System Sciences, 2010, 76(3):154-203.

[9] Zhang Yucheng, Feng Dan, Jiang Hong, et al. A fast asymmetric extre-mum content defined chunking algorithm for data deduplication in backup storage systems[J]. IEEE Tran-sactions on Computers,2017,66(2):199-211.

[10] DUTTA P,PATTNAIK P, SAHU R K. Brushing—an Algorithm for data deduplication[M]. Information Systems Design and Intelligent Applications. Springer India, 2016.

[11] Zhou Bing, Wen Jiangtao. Metadata feedback and utilization for data deduplication across WAN[J]. Journal of Computer Science and Technology, 2016, 31(3): 604-623.

[12] 張宗華,屈英, 葉志佳,等. 基于多特征匹配和Bloom filter的重復(fù)數(shù)據(jù)刪除算法[J]. 深圳大學(xué)學(xué)報(bào)(理工版), 2016, 33(5):531-535.

[13] BEHLING M, LAVERGNE J. Lubuntu[CP/OL]. (2016-10-15)[2016-10-20]http://lubuntu.net/.

[14] VINET J, GRIFFIN A, Arch Linux[CP/OL]. (2016-10-15)[2016-10-20]https://www.archlinux.org/download/.

[15] Google. Chromium OS[CP/OL].(2016-10-15)[2016-10-20]https://www.chromium.org/chromiumos.

[16] SHUTTLEWORTH M. Ubuntu[CP/OL].(2016-10-15)[2016-10-20]https://www.ubuntu.com/download/desktop。

2017-04-30)

郭玉劍(1991-)，通信作者，男，碩士，主要研究方向：大數(shù)據(jù)處理技術(shù)及應(yīng)用。E-mail:1436066470@qq.com。

曾志浩(1975-)，男，博士，講師，主要研究方向：面向Web服務(wù)的軟件開發(fā)方法、大數(shù)據(jù)處理技術(shù)。

Research on an asymmetric maximum chunking algorithm for deduplication

Guo Yujian, Zeng Zhihao

(College of Computer Science, Hunan University of Technology, Zhuzhou 41200, China)

Chunking is a process of spilting files into smaller files, which is widely used in deduplication systems. Aiming at the problem of high computational overhead in traditional content-based chunking (CDC), a new chunking algorithm called asymmetric maximum (CAAM) is proposed. Instead of using hashes,CAAM uses the byte value to declare the cut points. The algorithm utilizes the fixed size window and the variable size window to find the maximum value which is cut points. The algorithm allows less computation overhead while keeping the CDC property. Finally, the CAAM algorithm is compared with the existing hash-based and hash-less. The experimental results show that the CAAM algorithm has lower computational cost and higher chunking throughput than other algorithms.

deduplication; asymmetric window; content-defined chunking; hash-less chunking; cut points

TP391

A

10.19358/j.issn.1674- 7720.2017.22.009

郭玉劍，曾志浩.一種用于重復(fù)數(shù)據(jù)刪除的非對(duì)稱最大值分塊算法研究J.微型機(jī)與應(yīng)用，2017,36(22)：30-33.