重復數(shù)據刪除技術在云存儲中的應用

宋桂平

（河南測繪職業(yè)學院，河南 鄭州 451464）

在大數(shù)據時代，要想整合數(shù)據資源、挖掘數(shù)據價值，首先要從海量數(shù)據中篩選、檢索出目標數(shù)據。為了減輕這一工作量，必須要進行“數(shù)據瘦身”。而重復數(shù)據刪除（De-duplication）就是一種常用的數(shù)據縮減技術。其中，數(shù)據塊分塊算法、指紋庫查詢等，都是重復數(shù)據刪除中的核心技術。雖然重復數(shù)據刪除技術已經得到廣泛應用，但是仍然有一定的缺陷，例如會導致元數(shù)據增加，誤刪除數(shù)據恢復難度較大等。在這一背景下，探究云存儲模式下重復數(shù)據刪除技術的優(yōu)化應用策略成為一項熱門研究課題。

1 重復數(shù)據刪除技術

1.1 重復數(shù)據刪除的基本流程

重復數(shù)據刪除大體包含5個步驟：第一步，選擇需要存儲或備份的文件，然后使用分塊算法將整個文件分解成若干個獨立的數(shù)據塊，并對每個數(shù)據塊進行命名、標記；第二步，使用哈希函數(shù)（hash）分別對各個數(shù)據塊進行計算、處理，得到對應的hash 值，即指紋。若兩個數(shù)據塊相同，則其指紋能夠完全匹配；第三步，將所得指紋與指紋庫中已存指紋進行配對，判斷該指紋是否存在。若不存在，則執(zhí)行第四步；若存在，則執(zhí)行第五步；第四步，將該指紋及其對應的數(shù)據塊存儲起來，同時更新元數(shù)據；第五步，直接更新元數(shù)據。從上述流程來看，重復數(shù)據刪除技術的核心在于重復數(shù)據的檢測、hash 指紋計算函數(shù)、指紋在指紋庫中的查詢。

1.2 重復數(shù)據檢測技術

重復數(shù)據檢測結果將會直接決定系統(tǒng)的重刪率，同時選擇不同的檢測技術還會產生不同的性能開銷。例如，選擇固定分塊算法，對系統(tǒng)性能要求不高，性能開銷較??；相反，內容分塊算法的重刪率更高，并且性能開銷的需求也更高。目前比較常用的重復數(shù)據檢測技術有兩大類，即相同數(shù)據檢測、相似數(shù)據檢測，具體又包含了若干技術，例如基于文件級分塊、基于內容分塊等。

本文主要使用到了固定長度分塊和滑動窗口分塊。其中，固定長度分塊是將一份文件切割成若干個長度相同的數(shù)據塊，其優(yōu)勢在于算法簡單、元數(shù)據管理方便，在數(shù)據備份中常用這種算法。但是其缺點也比較明顯，例如無法智能識別數(shù)據內容，對數(shù)據修改具有很高的敏感性，影響系統(tǒng)的重刪率?；瑒哟翱诜謮K是一種更高精度的重復數(shù)據檢測方法，它融合了固定長度分塊算法元數(shù)據易于管理的優(yōu)點和CDC 算法對數(shù)據修改不具有較強敏感性的優(yōu)點，綜合應用效果更好。

2 重復數(shù)據刪除技術在云存儲中的應用

2.1 重復數(shù)據刪除系統(tǒng)設計

基于云存儲特點，設計的重復數(shù)據刪除系統(tǒng)采用多數(shù)據節(jié)點的分布式系統(tǒng)，保證了數(shù)據重刪與恢復的同時進行，以及實現(xiàn)元數(shù)據分治，以便于增強系統(tǒng)整體性能和降低元數(shù)據管理成本。系統(tǒng)基本架構如圖1 所示。

圖1 重復數(shù)據刪除系統(tǒng)架構圖

如圖1 所示，該重復數(shù)據刪除系統(tǒng)中包含2 臺Nameserver、N 臺Dateserver。其中，Client（客戶端）與Nameserver 之間完成地址表信息交互，與Dateserver之間完成數(shù)據塊、指紋等信息的交互。主、備Nameserver 之間保持數(shù)據同步，這樣在主Nameserver 因故障停運或發(fā)生宕機后，可以直接從備Nameserver 中獲取數(shù)據，防止數(shù)據丟失、保證系統(tǒng)正常運行。Nameserver 通過心跳的方式檢測和Dateserver 的運行工況。

2.2 系統(tǒng)功能模塊設計

2.2.1 客戶端

客戶端的功能包括讀取文件信息、進行數(shù)據分塊，以及數(shù)據塊的hash 處理。由于每名用戶可備份若干文件，因此需要采用“用戶名+文件路徑名”的方式，對文件進行標記，所得文件的標識符記為File_ID。在客戶端備份的過程中，將讀取信息后的文件進行分塊。數(shù)據分塊將直接決定重復數(shù)據刪除系統(tǒng)的兩個關鍵指標，即“重刪率”和“吞吐率”。重刪率取決于分塊方式、分塊大小。通常來說數(shù)據塊期望越小，則重刪率越高。但是不同類型的文件適用的分塊方式也存在差異，例如小于10 MB 的圖片文件，可選擇固定分塊算法；而對于1 GB 以上的視頻文件，滑動窗口算法更為理想。

2.2.2 數(shù)據存儲節(jié)點

數(shù)據存儲節(jié)點（Dateserver）的主要功能有兩個：其一是存儲數(shù)據，其二是在指紋庫中對新的指紋進行配對，判斷有無重復?？紤]到指紋庫中存儲著海量的指紋信息，因此指紋查詢的速度也是決定重復數(shù)據刪除系統(tǒng)性能的一項關鍵指標。由于采用的是分布式系統(tǒng)，因而能夠以線性方式縮小單機指紋庫的大小。假設某重復數(shù)據刪除系統(tǒng)指紋庫總容量為500 G，安裝有200 臺Dateserver，則單機指紋庫容量僅為2.5 G，這樣就能快速完成指紋查詢任務。另外，在指紋庫設計上也采用了雙層結構，第一層是bioomfilter（布隆過濾器），本質上是一種高效的數(shù)據查詢模塊，主要用于快速判重；第二層是內存指紋cache，其作用是添加指紋計數(shù)器，簡化了將指紋放入指紋庫時的操作流程，提升系統(tǒng)性能。

2.3 系統(tǒng)數(shù)據分配策略

該系統(tǒng)中包含若干臺Dateserver，并且每一臺Dateserver 中存儲的數(shù)據都是相互獨立的。基于這一特點，在系統(tǒng)數(shù)據分配上選擇了一致性哈希算法。其分配原理是將Dateserver 中的數(shù)據盡量平均分配至每個節(jié)點上，以實現(xiàn)負載均衡。將Dateserver 中的數(shù)據值設定為a，則數(shù)據分配流程：基于hash 函數(shù)分別計算每一個數(shù)據塊對應的hash 值。沿著順時針的方向，將該數(shù)據塊分散到第一個大于該hash 值的a 對應的Dateserver上。由于一致性哈希擁有較好的可擴展能力，因此當系統(tǒng)中任意一個Dateserver 的增加或失效，只會影響到它相鄰的兩個節(jié)點，而不會對系統(tǒng)中其他節(jié)點產生影響。

3 重復數(shù)據刪除系統(tǒng)應用測試

3.1 測試環(huán)境

該系統(tǒng)測試環(huán)境配置如下：使用Ubuntu12.2 系統(tǒng)，內核為Linux3.5.0-17，Intel（R）Xeon（R）CPU E5-2603（4 核，主頻2.0 GHz），64 G 內存，1 TB 磁盤和1 Gpbs 網卡。

3.2 測試內容及結果

3.2.1 分塊算法性能測試

該部分采用了對比測試，選擇一個大小為20 M、內容無重復的文檔作為樣本，分別使用固定分塊算法、滑動窗口算法、改進的滑動窗口算法進行測試。測試內容分為兩項，第一是對原始文檔進行備份，測試一次備份情況下3 種算法的性能及重刪率。第二是在該文件中間隨機位置添加1個字節(jié)，然后再使用3 種算法進行備份。測試第二次備份時各算法的性能與重刪率。其中，重刪率（f）的計算公式：

式（1）中，Data1 為重復數(shù)據刪除前文件數(shù)據量，Data2為新增數(shù)據量。測試結果如圖2、圖3 所示。

圖2 文件無重復度情況下3 種算法比較

圖3 在文件中加入一個字節(jié)第二次備份3 種算法比較

結合圖2 可以發(fā)現(xiàn)，在文檔文件重刪率較低（接近于0）時，選擇滑動窗口算法的系統(tǒng)性能較差，吞吐率僅有0.9 MB/s。相比之下，選擇固定長度分塊算法，系統(tǒng)性能得到了明顯改善，吞吐率達到39.5 MB/s，兩者之間差距明顯。而改進后的滑動窗口算法性能一般，吞吐率為26.3 MB/s。而在圖3 中，隨著文檔文件重刪率的增加，3 種算法下系統(tǒng)性能差異逐漸縮小。在文檔修改度較小的情況下，第二次備份時運用改進的滑動窗口算法、滑動窗口算法，都能獲得較高的重刪率，后者甚至接近100%。另外，相比于固定長度分塊算法，在上述兩種算法下由于文件中大部分數(shù)據塊并不需要寫入磁盤，因此他們的吞吐率也要略高。

基于上述測試數(shù)據可得：在數(shù)據無重復或重復度很小的情況下，固定分塊算法性能表現(xiàn)較好，改進的滑動窗口算法性能一般，而滑動窗口算法性能較差；在數(shù)據重刪率較高的情況下，滑動窗口與改進的滑動窗口算法性能較好，并且兩者差距不明顯，固定分塊算法性能稍差。綜合來看，在重復數(shù)據刪除系統(tǒng)設計和運行中使用改進的滑動窗口算法效果最好。

4 結束語

本文設計的一種分布式重復數(shù)據刪除系統(tǒng)，可根據不同類型的文件選擇合適的分塊算法，其中基于滑動窗口的改進算法，在圖片、視頻等文件的重復數(shù)據刪除中均表現(xiàn)出較好的系統(tǒng)性能。當系統(tǒng)中多臺客戶端同時備份時，隨著數(shù)據節(jié)點的增加，系統(tǒng)吞吐率也隨之上升，重復數(shù)據刪除系統(tǒng)的性能得到改善。

3.2.2 系統(tǒng)備份和恢復性能

該測試的對象主要是指紋庫與多臺Dateserver。選擇一個4.1 GB 的視頻文件，重復度基本為0。測試分為兩部分，第一次選擇1 臺Client、1 臺Nameserver、1臺Dateserver，將視頻文件分割成若干1 MB 大小的數(shù)據塊，測試備份時系統(tǒng)性能及重刪率。第二次選擇6 臺Client，1 臺Nameserver，并分別在1、2、3、4 臺Dateserver下測試系統(tǒng)性能。結果如圖4、圖5 所示。

圖4 單機備份和恢復性能

在圖4 中，使用大數(shù)據塊固定長度分塊方式，系統(tǒng)針對視頻文件的備份性能與恢復性能均有良好表現(xiàn)。在圖5 中，使用1 臺Dateserver 時，受到網絡帶寬的限制，系統(tǒng)備份與恢復性能較差；當2 臺Dateserver 投入使用時，系統(tǒng)性能有明顯改善；當3 臺、4 臺Dateserver投入使用時，系統(tǒng)性能均依次提升。

圖5 多機備份和恢復性能