鄭軻　俞婷

摘 要：隨著信息化建設(shè)的深入，數(shù)據(jù)信息量呈幾何級(jí)增長(zhǎng)，為解決數(shù)據(jù)大量重復(fù)而導(dǎo)致存儲(chǔ)空間浪費(fèi)，文章將重點(diǎn)研究重復(fù)數(shù)據(jù)消重的問題。文章首先給出了數(shù)據(jù)消重技術(shù)的原理，并對(duì)數(shù)據(jù)消重類別，數(shù)據(jù)指紋和數(shù)據(jù)劃分進(jìn)行了闡述，接著重點(diǎn)分析了數(shù)據(jù)消重領(lǐng)域中的變長(zhǎng)分塊算法，元數(shù)據(jù)索引和客戶端與服務(wù)端交互等。

關(guān)鍵詞：重復(fù)數(shù)據(jù)；消重；變長(zhǎng)塊；元數(shù)據(jù)；客戶端；服務(wù)端

1 概述

科技的飛速發(fā)展正在加速產(chǎn)生大量高價(jià)值數(shù)據(jù)，雖然數(shù)據(jù)呈爆炸性增長(zhǎng)，但重復(fù)數(shù)據(jù)存在信息處理和存儲(chǔ)的各個(gè)環(huán)節(jié)。傳統(tǒng)的數(shù)據(jù)保護(hù)技術(shù)如周期性備份、版本文件系統(tǒng)等更能加速重復(fù)數(shù)據(jù)的增長(zhǎng)。為了抑制數(shù)據(jù)過快增長(zhǎng)，重復(fù)數(shù)據(jù)刪除已成為一個(gè)備受關(guān)注的研究課題。

2 消重技術(shù)

數(shù)據(jù)消重技術(shù)原理是將一個(gè)文件或多個(gè)文件分割成很多小塊，利用一定的算法計(jì)算這些小塊的數(shù)據(jù)指紋，數(shù)據(jù)指紋相同則說明數(shù)據(jù)塊內(nèi)容相同，存儲(chǔ)時(shí)只需存儲(chǔ)相同數(shù)據(jù)塊的一份。

2.1 重復(fù)數(shù)據(jù)劃分

重復(fù)數(shù)據(jù)刪除通過重復(fù)數(shù)據(jù)檢測(cè)技術(shù)來確定存儲(chǔ)系統(tǒng)中重復(fù)的文件和數(shù)據(jù)塊，重復(fù)數(shù)據(jù)刪除主要有兩種：（1）文件級(jí)重復(fù)數(shù)據(jù)刪除；（2）數(shù)據(jù)塊級(jí)重復(fù)數(shù)據(jù)刪除，可以更進(jìn)一步在文件內(nèi)部搜索相同的數(shù)據(jù)塊，保證數(shù)據(jù)塊的唯一實(shí)例存儲(chǔ)。重復(fù)數(shù)據(jù)消重框架圖如圖1所示，首先將文件切分成小塊，并用SHA1算法計(jì)算每個(gè)小塊的數(shù)據(jù)指紋，若數(shù)據(jù)指紋存在于指紋索引中，則刪除該指紋對(duì)應(yīng)的數(shù)據(jù)塊，否則將數(shù)據(jù)塊寫到存儲(chǔ)設(shè)備中。

2.2 數(shù)據(jù)指紋算法

目前文件內(nèi)部重復(fù)數(shù)據(jù)檢測(cè)普遍用Hash算法：首先對(duì)數(shù)據(jù)進(jìn)行哈希，從而得到唯一的哈希值，哈希函數(shù)以MD5和SHA1算法最為流行，MD5生成一個(gè)128位的哈希值，SHA1生成一個(gè)160位的哈希值，在相同的硬件條件下，MD5的計(jì)算速度是227MB/S，而SHA1的計(jì)算速度是83MB/S，應(yīng)根據(jù)實(shí)際的應(yīng)用環(huán)境來選取適當(dāng)?shù)墓：瘮?shù)。

2.3 數(shù)據(jù)塊劃分

基于文件內(nèi)容數(shù)據(jù)塊劃分粒度小，它的切割長(zhǎng)度在4-24K之間，數(shù)據(jù)分塊算法主要有定長(zhǎng)切分和CDC切分。定長(zhǎng)分塊算法優(yōu)點(diǎn)是簡(jiǎn)單，但它對(duì)數(shù)據(jù)插入和刪除敏感，處理低效。CDC變長(zhǎng)分塊可將文件或數(shù)據(jù)流分割成長(zhǎng)度大小不等的數(shù)據(jù)塊，實(shí)現(xiàn)變長(zhǎng)分塊需要滑動(dòng)窗口，滑動(dòng)窗口對(duì)文件數(shù)據(jù)計(jì)算數(shù)據(jù)指紋，如果指紋滿足某個(gè)條件，則把窗口位置作為塊的邊界。

3 消重技術(shù)難點(diǎn)

重復(fù)數(shù)據(jù)刪除主要有三方面指標(biāo)：重刪率，擴(kuò)展性和吞吐率。重刪率說明軟件能挖掘出多少重復(fù)數(shù)據(jù)；擴(kuò)展性是重刪系統(tǒng)能否擴(kuò)展到超大規(guī)模的數(shù)據(jù)量；吞吐率是系統(tǒng)處理數(shù)據(jù)的速度。這三個(gè)指標(biāo)都很重要，同時(shí)優(yōu)化其中兩個(gè)比較容易，但優(yōu)化三個(gè)標(biāo)準(zhǔn)很困難。

3.1 變長(zhǎng)分塊算法研究

盡管變長(zhǎng)分塊對(duì)數(shù)據(jù)序列不太敏感，但由于數(shù)據(jù)塊邊界點(diǎn)比較消耗CPU資源，從而影響重復(fù)數(shù)據(jù)刪除性能。在實(shí)際中并不期望數(shù)據(jù)塊劃分得過大或過小，因此對(duì)基于滑動(dòng)窗口技術(shù)的變長(zhǎng)分塊算法進(jìn)行一些優(yōu)化，讓滑動(dòng)窗口從數(shù)據(jù)塊最小值地方開始滑動(dòng)，如果滑動(dòng)到數(shù)據(jù)塊最大值地方還沒有找到數(shù)據(jù)塊的邊界點(diǎn)，便硬性規(guī)定此處為數(shù)據(jù)塊的一個(gè)邊界點(diǎn)。對(duì)文件或數(shù)據(jù)流的劃分用到一個(gè)48字節(jié)的滑動(dòng)窗口，計(jì)算函數(shù)如下：

3.2 元數(shù)據(jù)塊檢索

重復(fù)數(shù)據(jù)刪除的索引是最難設(shè)計(jì)的，好的索引必須有高擴(kuò)展性，高吞吐率和高刪重率，但現(xiàn)實(shí)情況中很難實(shí)現(xiàn)以上三個(gè)目標(biāo)。在這里采用漸進(jìn)式抽樣索引，每T個(gè)指紋抽樣一個(gè)指紋，這樣索引就縮小到原來的1/T，這樣做導(dǎo)致索引的命中率就減小到1/T，但是考慮到數(shù)據(jù)流的局部性：如果上一次備份A和B是連續(xù)出現(xiàn)的，那么這一次備份A/B非?？赡苋允沁B續(xù)的，如果每次命中抽樣指紋，就將該抽樣指紋所屬的容器里所有指紋讀到緩存，那么接下來接收到的指紋雖然在索引未命中，但大多數(shù)會(huì)出現(xiàn)在緩存中，這就非常有效地提升了重刪率。

3.3 客戶端與服務(wù)端交互

在一個(gè)典型的C/S架構(gòu)中，即使解決了索引問題，端到端的性能仍然會(huì)受限于客戶端。典型的客戶端按照以下順序進(jìn)行：（1）讀取文件數(shù)據(jù)；（2）分塊和計(jì)算指紋；（3）發(fā)送指紋到服務(wù)器，等待服務(wù)器的查詢結(jié)果；（4）發(fā)送服務(wù)器未查詢到的數(shù)據(jù)塊。最后一點(diǎn)網(wǎng)絡(luò)也非常可能成為全局性的瓶頸，為了滿足性能需求，用TCP實(shí)現(xiàn)的RPC協(xié)議會(huì)保持多個(gè)TCP連接，為減少來回開銷和提高吞吐率，所有RPC請(qǐng)求都異步。

4 消重應(yīng)用領(lǐng)域

4.1 網(wǎng)絡(luò)備份系統(tǒng)

重復(fù)數(shù)據(jù)刪除技術(shù)為數(shù)據(jù)保護(hù)領(lǐng)域帶來革命性的突破，有效改善磁盤數(shù)據(jù)保護(hù)的成本效益?，F(xiàn)在基于磁盤的數(shù)據(jù)保護(hù)方案被廣泛使用，并且在未來會(huì)繼續(xù)增長(zhǎng)，人們所要備份的數(shù)據(jù)越來越多，重復(fù)數(shù)據(jù)刪除技術(shù)的出現(xiàn)，為存儲(chǔ)容量最小化找到有效方法。

4.2 歸檔存儲(chǔ)系統(tǒng)

由于參考數(shù)據(jù)數(shù)量不斷增長(zhǎng)，而法規(guī)遵從要求數(shù)據(jù)在線保留的時(shí)間更長(zhǎng)，理想的歸檔存儲(chǔ)系統(tǒng)應(yīng)能滿足長(zhǎng)期保存歸檔數(shù)據(jù)的需求，并且總擁有成本要低于生產(chǎn)環(huán)境，重復(fù)數(shù)據(jù)刪除技術(shù)通過消除冗余實(shí)現(xiàn)高效率的歸檔存儲(chǔ)，從而實(shí)現(xiàn)最低成本。

4.3 異地容災(zāi)

在遠(yuǎn)程災(zāi)備系統(tǒng)中，需要將大量的數(shù)據(jù)遷移到異地系統(tǒng)中，隨著數(shù)據(jù)量的不斷增長(zhǎng)，數(shù)據(jù)傳輸?shù)膲毫υ絹碓酱?，通過重復(fù)數(shù)據(jù)刪除技術(shù)在數(shù)據(jù)傳輸前檢測(cè)并刪除重復(fù)的數(shù)據(jù)，可以有效減少傳輸?shù)臄?shù)據(jù)量，提高傳輸數(shù)據(jù)速度。

5 結(jié)束語

重復(fù)數(shù)據(jù)刪除的關(guān)鍵是找到文件或數(shù)據(jù)流中的所有重復(fù)數(shù)據(jù)，以保證系統(tǒng)只存儲(chǔ)元數(shù)據(jù)的唯一實(shí)例，這是消重系統(tǒng)的目標(biāo)，但為了保證消重系統(tǒng)的高擴(kuò)展性和高吞吐率，三方面的指標(biāo)很難達(dá)到一個(gè)平衡點(diǎn)。一旦數(shù)據(jù)擴(kuò)充到很大，系統(tǒng)的消重率，擴(kuò)展性和吞吐率也將隨之下降，為了提升一方面指標(biāo)，必定會(huì)降低另一個(gè)或兩個(gè)指標(biāo)，文章在變長(zhǎng)分塊算法，元數(shù)據(jù)檢索和客戶端與服務(wù)端等方面做了一定的研究。

參考文獻(xiàn)

[1]顏軍.重復(fù)數(shù)據(jù)刪除帶來集群架構(gòu)革命[J].計(jì)算機(jī)世界，2008.

[2]廖海生，趙躍龍.基于MD5算法的重復(fù)數(shù)據(jù)刪除技術(shù)的研究與改進(jìn)[J].計(jì)算機(jī)測(cè)量與控制，2010.

[3]什么是重復(fù)數(shù)據(jù)刪除技術(shù)[EB/OL].重慶：賽迪網(wǎng).2008.

作者簡(jiǎn)介：鄭軻，嘉興學(xué)院講師，主要研究方向：數(shù)據(jù)安全。

俞婷（1988-），女，浙江嘉興人，嘉興學(xué)院助教，研究方向：網(wǎng)絡(luò)教育，數(shù)據(jù)挖掘。