宋桂平

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

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

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

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

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

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

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

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

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

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

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

圖1 重復(fù)數(shù)據(jù)刪除系統(tǒng)架構(gòu)圖

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

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

2.2.1 客戶端

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

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

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

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

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

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

3.1 測試環(huán)境

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

3.2 測試內(nèi)容及結(jié)果

3.2.1 分塊算法性能測試

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

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

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

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

結(jié)合圖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ù)據(jù)塊并不需要寫入磁盤，因此他們的吞吐率也要略高。

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

4 結(jié)束語

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

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

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

圖4 單機備份和恢復(fù)性能

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

圖5 多機備份和恢復(fù)性能