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

宋桂平

（河南測繪職業學院，河南 鄭州 451464）

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

1 重復數據刪除技術

1.1 重復數據刪除的基本流程

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

1.2 重復數據檢測技術

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

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

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

2.1 重復數據刪除系統設計

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

圖1 重復數據刪除系統架構圖

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

2.2 系統功能模塊設計

2.2.1 客戶端

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

2.2.2 數據存儲節點

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

2.3 系統數據分配策略

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

3 重復數據刪除系統應用測試

3.1 測試環境

該系統測試環境配置如下：使用Ubuntu12.2 系統，內核為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個字節，然后再使用3 種算法進行備份。測試第二次備份時各算法的性能與重刪率。其中，重刪率（f）的計算公式：

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

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

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

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

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

4 結束語

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

3.2.2 系統備份和恢復性能

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

圖4 單機備份和恢復性能

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

圖5 多機備份和恢復性能