鄭軻　俞婷

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

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

1 概述

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

2 消重技術(shù)

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

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

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

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

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

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

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

3 消重技術(shù)難點

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

3.1 變長分塊算法研究

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

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

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

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

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

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

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

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

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

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

4.3 異地容災(zāi)

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

5 結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

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