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

郭玉劍，曾志浩

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

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

郭玉劍，曾志浩

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

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

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

0 引言

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

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

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

針對分塊中需要大量計算開銷的問題，本文提出了一個基于非對稱最大的分塊算法(CAAM)。該算法與AE算法類似，使用兩個窗口：固定長度窗口和可變長度窗口。與AE算法不同，CAAM算法對窗口使用了不同的位置。窗口位置從固定長度窗口開始，然后是可變大小的窗口和最大的字節(jié)。切割點位于塊的末尾。這種配置一定程度上減少了比較次數(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ù)刪除的工作原理就是利用這種方法來消除文件與文件之間的重復(fù)數(shù)據(jù)。在重復(fù)數(shù)據(jù)刪除中，分塊算法是實現(xiàn)高去重率的一種重要方法。通過選擇正確的分塊算法，可以節(jié)省消重時間和硬件空間。

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

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

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

1.2挑戰(zhàn)

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

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

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

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

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

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

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

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

輸入：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ì)說明了CAAM算法中的分塊細(xì)節(jié)。從該算法可以看出，CAAM通過在固定窗口中尋找到最大值來減少計算時間。而AE算法是需要先通過尋找最小值，然后再計算切點的位置，在此過程中就需要更多的計算開銷。

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

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

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

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

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

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

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

3 實驗分析

3.1實驗環(huán)境

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

3.2分塊吞吐量對比

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

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

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

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

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

4 結(jié)論

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

[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]. 微型機與應(yīng)用, 2013, 32(6):82-85.

[5] 顧瑜, 劉川意, 孫林春,等. 帶重復(fù)數(shù)據(jù)刪除的大規(guī)模存儲系統(tǒng)可靠性保證[J]. 清華大學(xué)學(xué)報(自然科學(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é)報(理工版), 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ù)刪除的非對稱最大值分塊算法研究J.微型機與應(yīng)用，2017,36(22)：30-33.