網絡備份中重復數據消重技術研究

鄭軻　俞婷

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

關鍵詞：重復數據；消重；變長塊；元數據；客戶端；服務端

1 概述

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

2 消重技術

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

2.1 重復數據劃分

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

2.2 數據指紋算法

目前文件內部重復數據檢測普遍用Hash算法：首先對數據進行哈希，從而得到唯一的哈希值，哈希函數以MD5和SHA1算法最為流行，MD5生成一個128位的哈希值，SHA1生成一個160位的哈希值，在相同的硬件條件下，MD5的計算速度是227MB/S，而SHA1的計算速度是83MB/S，應根據實際的應用環境來選取適當的哈希函數。

2.3 數據塊劃分

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

3 消重技術難點

重復數據刪除主要有三方面指標：重刪率，擴展性和吞吐率。重刪率說明軟件能挖掘出多少重復數據；擴展性是重刪系統能否擴展到超大規模的數據量；吞吐率是系統處理數據的速度。這三個指標都很重要，同時優化其中兩個比較容易，但優化三個標準很困難。

3.1 變長分塊算法研究

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

3.2 元數據塊檢索

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

3.3 客戶端與服務端交互

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

4 消重應用領域

4.1 網絡備份系統

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

4.2 歸檔存儲系統

由于參考數據數量不斷增長，而法規遵從要求數據在線保留的時間更長，理想的歸檔存儲系統應能滿足長期保存歸檔數據的需求，并且總擁有成本要低于生產環境，重復數據刪除技術通過消除冗余實現高效率的歸檔存儲，從而實現最低成本。

4.3 異地容災

在遠程災備系統中，需要將大量的數據遷移到異地系統中，隨著數據量的不斷增長，數據傳輸的壓力越來越大，通過重復數據刪除技術在數據傳輸前檢測并刪除重復的數據，可以有效減少傳輸的數據量，提高傳輸數據速度。

5 結束語

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

參考文獻

[1]顏軍.重復數據刪除帶來集群架構革命[J].計算機世界，2008.

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

[3]什么是重復數據刪除技術[EB/OL].重慶：賽迪網.2008.

作者簡介：鄭軻，嘉興學院講師，主要研究方向：數據安全。

俞婷（1988-），女，浙江嘉興人，嘉興學院助教，研究方向：網絡教育，數據挖掘。