宋桂平

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 客戶端

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

2.2.2 數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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