姜 濤，劉曉潔

（四川大學(xué) 計算機(jī)學(xué)院，四川 成都610065）

0 引 言

遠(yuǎn)程備份作為一種重要的數(shù)據(jù)保護(hù)手段，其通過將應(yīng)用系統(tǒng)中的數(shù)據(jù)備份到異地來實現(xiàn)容災(zāi)。由于備份數(shù)據(jù)存儲在遠(yuǎn)端，當(dāng)本地發(fā)生災(zāi)難導(dǎo)致數(shù)據(jù)丟失時可以通過備份的數(shù)據(jù)可靠地進(jìn)行恢復(fù)。然而研究發(fā)現(xiàn)，應(yīng)用系統(tǒng)所保存的數(shù)據(jù)中高達(dá)60%是冗余的，而且隨著時間的推移越來越多［1］。傳統(tǒng)的遠(yuǎn)程備份并沒有分析系統(tǒng)全局的數(shù)據(jù)冗余，如Rsync［2－3］備份只會消除單個文件增量備份不同版本之間的冗余，對于整個備份系統(tǒng)中所有文件之間的數(shù)據(jù)冗余就無能為力了。這樣會導(dǎo)致備份過程中傳輸大量冗余的數(shù)據(jù)，并且浪費存儲空間。

為了解決上述問題，本文提出了一種基于重復(fù)數(shù)據(jù)刪除的遠(yuǎn)程備份系統(tǒng)。系統(tǒng)對備份文件進(jìn)行分塊，識別相同的數(shù)據(jù)塊，只傳輸和存儲不重復(fù)的數(shù)據(jù)塊。由于相同數(shù)據(jù)塊的去重是系統(tǒng)全局的，這樣就大大節(jié)約了備份中心數(shù)據(jù)的存儲空間，并且有效地減少了網(wǎng)絡(luò)流量。

1 系統(tǒng)架構(gòu)

整個系統(tǒng)采用客戶／服務(wù)器架構(gòu)，即由備份客戶端和備份中心構(gòu)成。備份客戶端存放了需要備份的數(shù)據(jù)源，同時包括備份系統(tǒng)運行所需的必要組件。而備份中心則是存儲備份數(shù)據(jù)的地方，它同樣包含了備份系統(tǒng)相關(guān)組件。一個備份中心可以同時服務(wù)多個備份客戶端。圖1為系統(tǒng)的總體架構(gòu)。

備份客服端包括文件篩選模塊，文件分塊及指紋計算模塊，文件備份模塊，通信模塊4個部分：

（1）文件篩選模塊：篩選出實際需要備份的文件。

（2）文件分塊及指紋計算模塊：對需要備份的文件進(jìn)行分塊并計算每個數(shù)據(jù)塊的指紋值。

（3）文件備份模塊：利用文件的分塊及指紋信息，與備份中心通信，找出備份中心已經(jīng)存在的數(shù)據(jù)塊，并將新增的數(shù)據(jù)塊傳輸?shù)絺浞葜行摹?/p>

（4）通信模塊：負(fù)責(zé)處理與備份中心底層通信。

備份中心包括數(shù)據(jù)塊判重模塊，數(shù)據(jù)塊存儲模塊，通信模塊3個部分。

（1）數(shù)據(jù)塊判重模塊：判斷數(shù)據(jù)塊在備份中心是否已經(jīng)存在。

（2）數(shù)據(jù)塊存儲模塊：負(fù)責(zé)存儲和管理備份文件的數(shù)據(jù)塊。

（3）通信模塊：負(fù)責(zé)處理與備份客戶端底層通信。

圖1 系統(tǒng)總體架構(gòu)

2 系統(tǒng)設(shè)計與實現(xiàn)

2.1 備份文件篩選

在一個備份客戶端進(jìn)行多次備份時，有可能備份的目錄中只有少數(shù)文件發(fā)生了改變。如果不加以區(qū)分，在備份文件非常多的時候處理目錄中所有的文件顯然是不明智的。為了避免這種情況本文系統(tǒng)引入了一種單詞查找樹［4］的變形來篩選真正需要備份的文件。將該結(jié)構(gòu)命名為目錄查找樹，參見定義1。

定義1 目錄查找樹 單詞查找樹的變形，其存儲的是一個目錄中文件和子目錄的信息，其節(jié)點對應(yīng)文件系統(tǒng)目錄樹中的一個節(jié)點，其中包括路徑和時間信息。

在每次備份時生成目錄查找樹，通過比較待備份文件列表和上次備份的目錄查找樹可以快速篩選出實際需要備份的文件。目錄查找樹的結(jié)構(gòu)如圖2所示，根節(jié)點對應(yīng)最上層目錄，即需要備份的目錄。目錄查找樹的節(jié)點包含兩項內(nèi)容：當(dāng)前節(jié)點對應(yīng)的文件或目錄在文件系統(tǒng)中的路徑，當(dāng)前節(jié)點對應(yīng)的文件或目錄的修改時間。其中目錄的修改時間為它所包含的所有文件和目錄中最后修改時間。由此可知，當(dāng)修改一個文件后，這不僅改變了該文件的修改時間，并且可能影響其上所有父目錄的修改時間。利用這一原理就可以在備份的時候比較這次和上次備份的同一文件或目錄的修改時間，如果修改時間相同則跳過這一部分文件的后續(xù)處理，這樣可以快速篩選出真正需要備份的文件。在多次備份大量文件并且其中只有少部分文件改變的情況下，這一處理過程可以大大提高備份的效率。

圖2 目錄查找樹結(jié)構(gòu)

2.2 文件的分塊及指紋計算

文件分塊分為定長分塊算法和變長分塊算法［5］。定長分塊算法計算簡單，但對于文件的內(nèi)容不敏感，相同數(shù)據(jù)塊的識別率較低，而變長分塊算法能較好地感知文件間的重復(fù)內(nèi)容。所以本文系統(tǒng)采用了一種基于Rabin指紋［6］的變長分塊算法［7］進(jìn)行文件的分塊。該算法對文件應(yīng)用滑動窗口，計算各個窗口的Rabin值，當(dāng)其值符合某一特征時，就將該窗口所在的位置定為數(shù)據(jù)塊的邊界。根據(jù)Rabin函數(shù)的特性，該方法能夠有效地識別出文件之間的重復(fù)內(nèi)容，因為只有在文件內(nèi)容不一樣的地方，Rabin函數(shù)計算出的值才不一樣，而其他內(nèi)容重復(fù)的部分則會算出相同的值，從而生成相同的數(shù)據(jù)塊。

文件分塊后需要根據(jù)數(shù)據(jù)塊的內(nèi)容計算每個數(shù)據(jù)塊的指紋，該指紋將用于識別已經(jīng)備份的相同數(shù)據(jù)塊。系統(tǒng)用數(shù)據(jù)塊內(nèi)容的SHA1值作為其指紋值。SHA1算法［8］是一種廣泛應(yīng)用的散列算法，其抗沖突性較好。SHA1算法對于兩個不同的數(shù)據(jù)塊自然產(chǎn)生沖突的概率是非常低的，其能夠有效地區(qū)分不同的數(shù)據(jù)塊。

2.3 文件備份

根據(jù)文件內(nèi)容對文件分塊并計算數(shù)據(jù)塊指紋后，備份客戶端需要確定一個文件中哪些數(shù)據(jù)塊是不需要備份的，即這些數(shù)據(jù)塊在備份中心已經(jīng)存在，這樣就能夠只傳輸備份中心不存在的數(shù)據(jù)塊，其步驟如下：

（1）備份客戶端將文件的分塊信息，即文件中所有數(shù)據(jù)塊的長度和SHA1值發(fā)往備份中心。

（2）備份中心收到了該文件數(shù)據(jù)塊的信息后，用這些數(shù)據(jù)塊的SHA1值在索引中查找。如果一個數(shù)據(jù)塊的SHA1值在索引中找到，則說明該數(shù)據(jù)塊已經(jīng)存在，直接從索引中取得該數(shù)據(jù)塊存儲位置，同時標(biāo)記該數(shù)據(jù)塊是重復(fù)的。如果在索引中無法找到該SHA1值，則說明該數(shù)據(jù)塊是備份中心沒有的，根據(jù)傳過來的數(shù)據(jù)塊的長度，為該數(shù)據(jù)塊分配一塊新的空間，并將其信息插入索引中，標(biāo)記該數(shù)據(jù)塊是新增的。

（3）備份中心將數(shù)據(jù)塊是否存在的判斷結(jié)果發(fā)回備份客戶端。

（4）備份客戶端收到數(shù)據(jù)塊判斷結(jié)果后，新建一個空的差分文件。遍歷數(shù)據(jù)塊判斷結(jié)果，如果一個數(shù)據(jù)塊在備份中心已經(jīng)存在，則將其丟棄，否則將該數(shù)據(jù)塊的內(nèi)容寫入差分文件中。

（5）備份客戶端將生成好的差分文件發(fā)送到備份中心。

（6）備份中心接收差分文件后，將備份文件數(shù)據(jù)塊的元信息寫入相應(yīng)配置文件。同時對于備份文件中每一個新增的數(shù)據(jù)塊，利用傳過來的差分文件，將其內(nèi)容寫入相應(yīng)的備份數(shù)據(jù)存放位置。

至此一個文件的備份完成。

2.4 數(shù)據(jù)塊判重

SHA1值的長度為20字節(jié)，加上數(shù)據(jù)塊的存儲信息，一個索引大約需要占用28字節(jié)的空間。另外考慮一個數(shù)據(jù)塊的期望大小為8KB，則在備份中心存儲4TB的數(shù)據(jù)至少需要14GB的索引存儲空間，無法將索引完全放在內(nèi)存中，所以需要一個高效的磁盤索引結(jié)構(gòu)來進(jìn)行數(shù)據(jù)塊判重。本文系統(tǒng)采用了 Google的 Bigtable［9］和 Leveldb［10］的索引算法，并作了一定的簡化，加上了布隆過濾器［11］來改善重復(fù)數(shù)據(jù)塊的查詢效率。

這個索引算法結(jié)構(gòu)如圖3所示。當(dāng)插入一條索引時，操作信息首先寫入重做日志中，然后將其存儲在一個被稱為memtable的內(nèi)存緩存中。memtable是一顆按索引的鍵組織的紅黑樹［12］，所以其是按索引的鍵有序的。當(dāng)memtable超過一定大小限制后，其被整個刷新到名為sstable的文件中。這樣對于索引的插入操作將會有極高的效率，因為在插入操作中無論是寫日志文件還是其后將memtable的內(nèi)容寫到sstable文件中都是對磁盤的順序?qū)?。隨著sstable文件的增多，它們組織成一個層次結(jié)構(gòu)。內(nèi)存中有一個sstable的索引可以定位每一層sstable文件的數(shù)據(jù)范圍。在查詢操作時，通過sstable索引找到相應(yīng)的sstable文件，再與當(dāng)前的mmtable結(jié)合以進(jìn)行數(shù)據(jù)查詢。

圖3 數(shù)據(jù)塊查詢索引結(jié)構(gòu)

為了進(jìn)一步提高查詢效率，在該索引結(jié)構(gòu)的上層加入了布隆過濾器。布隆過濾器中記錄了所有存在的指紋值，該結(jié)構(gòu)可以極大地節(jié)約存儲空間，所以可將其全部放入內(nèi)存中。但布隆過濾器有一定誤判率，即一個本來沒有的指紋值可能被布隆過濾器判為已經(jīng)存在。但如果一個指紋值在布隆過濾器中不存在，則它一定不存在。利用此原理在查詢指紋值的時候先查詢其在布隆過濾器中是否存在，若存在則進(jìn)一步查詢其下層的索引。但如果在布隆過濾器中不存在，則可斷定該指紋值一定不存在，從而直接將其插入下層索引中。由于下層索引對于插入操作有很高的效率，這就提高了整個系統(tǒng)查詢數(shù)據(jù)塊的效率。另外為了防止宕機(jī)事故，布隆過濾器中的內(nèi)容需要定期寫入一個文件中進(jìn)行持久化。

2.5 數(shù)據(jù)塊存儲

備份中心的存儲架構(gòu)如圖4所示。

圖4 備份中心存儲架構(gòu)

備份中心可以服務(wù)于多個備份客戶端，所以一個備份客戶端對應(yīng)的備份元信息單獨存儲在一個目錄下。實際備份的數(shù)據(jù)塊則放在一個公共的目錄下，其存儲在一系列的容器文件中。此外，公共目錄下還有持久化的布隆過濾器文件和數(shù)據(jù)塊索引的sstable文件。

存放數(shù)據(jù)塊的容器文件有一定大小限制，當(dāng)其中的數(shù)據(jù)超過文件容量時，系統(tǒng)會新建一個容器文件用于存儲以后的數(shù)據(jù)塊。在容器文件中，一個數(shù)據(jù)塊包括三項：該數(shù)據(jù)塊的長度，該數(shù)據(jù)塊的引用計數(shù)和數(shù)據(jù)塊實際的內(nèi)容。引入引用計數(shù)是為了能夠回收數(shù)據(jù)的存儲空間，避免存儲空間無限增大。初始插入一個數(shù)據(jù)塊時其引用次數(shù)為1，當(dāng)重復(fù)備份一次該數(shù)據(jù)塊時其引用次數(shù)加1。當(dāng)刪除一個備份文件時，該文件對應(yīng)的所有數(shù)據(jù)塊的引用次數(shù)都減1。一個后臺進(jìn)程會定期查看每個容器文件，當(dāng)某個容器文件的每個數(shù)據(jù)塊的引用次數(shù)都為0時，則回收該容器文件。

一個備份客戶端可以備份多次，這樣形成了多個備份時間點。一個備份時間點的備份信息主要由兩個文件記錄：FileInfo和ChunkInfo。FileInfo中記錄了本次所有備份文件信息，包括每個文件的路徑，文件的數(shù)據(jù)塊信息在ChunkInfo文件中的偏移，以及文件組成的數(shù)據(jù)塊個數(shù)。而ChunkInfo中記錄了FileInfo中對應(yīng)文件的數(shù)據(jù)塊信息，包括每個數(shù)據(jù)塊所在的容器文件序號，數(shù)據(jù)塊在容器文件中的偏移，數(shù)據(jù)塊的大小。這樣在恢復(fù)備份文件的時候，只需要通過FileInfo找到ChunkInfo中該文件對應(yīng)的數(shù)據(jù)塊信息，再根據(jù)此信息從容器文件中讀出相應(yīng)的數(shù)據(jù)塊，就能完全恢復(fù)該文件。

3 實驗與分析

實驗分別對多個相似的數(shù)據(jù)集進(jìn)行完全備份和對一個數(shù)據(jù)集進(jìn)行多次增量備份來驗證本系統(tǒng)的效能。測試數(shù)據(jù)集采用解壓之后的Linux內(nèi)核源代碼，如表1所示。

表1 測試數(shù)據(jù)集

實驗環(huán)境如下：備份客戶端操作系統(tǒng)為Ubuntu 10.04 Desktop，配置為CPU Intel（R）Core（TM）Duo E7500，內(nèi)存2GB。備份中心操作系統(tǒng)為CentOS 5.5，配置為CPU Intel（R）Core（TM）i5－2300，內(nèi)存4GB。100Mb／s網(wǎng)絡(luò)環(huán)境。

3.1 相似數(shù)據(jù)集完全備份

實驗方法：用本文系統(tǒng)分別備份表1中5個相似的數(shù)據(jù)集，查看每次備份的網(wǎng)絡(luò)流量和增加的存儲空間。

表2為以上5次備份實驗結(jié)果。通過圖5可以清楚地看出本文系統(tǒng)對于多個相似的數(shù)據(jù)集的完全備份，可以有效地刪除其中的重復(fù)數(shù)據(jù)，從而減少備份的網(wǎng)絡(luò)流量和存儲空間。

表2 5個數(shù)據(jù)集完全備份實驗結(jié)果

圖5 每次備份容量，網(wǎng)絡(luò)流量及增加存儲空間對比

3.2 數(shù)據(jù)集增量備份

實驗方法：分別用本文系統(tǒng)和Rsync備份表1中的數(shù)據(jù)集3，而后隨機(jī)修改該備份集下少量文件，再用本文系統(tǒng)和Rsync備份該數(shù)據(jù)集，比較此次增量備份的網(wǎng)絡(luò)流量。

表3是修改數(shù)據(jù)集中不同文件個數(shù)下本文系統(tǒng)和Rsync備份的實驗結(jié)果。通過圖6可知，在對同一數(shù)據(jù)集進(jìn)行增量備份時，當(dāng)每次增量變化較小時，本文系統(tǒng)比起Rsync備份網(wǎng)絡(luò)流量更少。這是由于本文系統(tǒng)相對于Rsync傳輸?shù)膫浞菰畔⑤^少。但本文系統(tǒng)數(shù)據(jù)塊的判重粒度比Rsync大，當(dāng)增量備份變化較大時，傳輸較少的備份元信息不足以補(bǔ)償增多的增量備份數(shù)據(jù)。因此用本文系統(tǒng)進(jìn)行變化較大的增量備份時，效率就不如Rsync了。

表3 本文系統(tǒng)和Rsync增量備份實驗結(jié)果

圖6 本文系統(tǒng)和Rsync增量備份網(wǎng)絡(luò)流量對比

4 結(jié)束語

在傳統(tǒng)遠(yuǎn)程備份中，應(yīng)用系統(tǒng)中的大量冗余數(shù)據(jù)會導(dǎo)致備份效率低下，浪費大量帶寬和存儲空間。針對此問題，本文設(shè)計并實現(xiàn)了一個基于重復(fù)數(shù)據(jù)刪除的遠(yuǎn)程備份系統(tǒng)。該系統(tǒng)在備份文件的時候能夠找出文件中已經(jīng)備份了的重復(fù)數(shù)據(jù)，從而只備份文件中新增的數(shù)據(jù)，有效地減少了備份網(wǎng)絡(luò)流量并且節(jié)約了備份數(shù)據(jù)的存儲空間。實驗結(jié)果表明采用本文系統(tǒng)進(jìn)行遠(yuǎn)程備份能夠有效去除系統(tǒng)中的重復(fù)數(shù)據(jù)，從而提高備份效率。

［1］McKnight J，Asaro T，Babineau B.Digital archiving：end－user survey ＆ market forecast 2006－2010 ［EB／OL］.http：／／www.enterprisestrategygroup.com／2006／03／digital－archiving－end－user－survey－market－forecast－2006－2010／，2006.

［2］HAO Yan，Irmak U，Suel T.Algorithms for low－latency remote file synchronization［C］.The 27th Conference on Computer Communications，Phoenix，AZ，2008：156－160.

［3］Ghobadi A，Mahdizadeh E H，Yong L K，et al.Pre－processing directory structure for improved RSYNC transfer performance［C］.13th International Conference on Advanced Communication Technology，2011：1043－1048.

［4］Tanbeer S K，Ahmed C F，Jeong B S，et al.Efficient singlepass frequent pattern mining using aprefix－tree［J］.Information Sciences，2009，179 （5）：559－583.

［5］Bobbarjung D R，Jagannathan S，Dubnicki C.Improving duplicate elimination in storage systems［J］.ACM Transactions on Storage（TOS），2006，2 （4）：424－448.

［6］LIANG Zhengyou，ZHANG Lincai，Duplicated URL detection based on Rabin s fingerprint method ［J］.Journal of Computer Applications，2008，28 （z2）：185－186 （in Chinese）.［梁正友，張林才.基于Rabin指紋方法的URL去重算法 ［J］.計算機(jī)應(yīng)用，2008，28 （z2）：185－186.］

［7］AO Li，SHU Jiwu，LI Mingqiang.Data deduplication techniques ［J］.Journal of Software，2010，21 （5）：916－929 （in Chinese）.［敖莉，舒繼武，李明強(qiáng).重復(fù)數(shù)據(jù)刪除技術(shù) ［J］.軟件學(xué)報，2010，21 （5）：916－929.］

［8］ZHAO Yu，ZHOU Yujie.IP design and speed optimization of SHA1［J］.Information Security and Communications Privacy，2006 （12）：125－127 （in Chinese）. ［趙宇，周玉潔.SHA1IP的設(shè)計及速度優(yōu)化 ［J］.信息安全與通信保密，2006（12）：125－127.］

［9］CHANG F，Dean J，Ghemawat S，et al.Bigtable：A distributed storage system for structured data［J］.ACM Transactions on Computer Systems（TOCS），2008，26 （2）：4：1－4：26.

［10］Dean J，Ghemawat S.Leveldb：A fast and lightweight key／value database library ［EB／OL］.http：／／code.google.com／p／leveldb／，2011.

［11］Kirsch A，Mitzenmacher M.Less hashing，same performance：Building a better bloom filter［J］.Random Structures ＆ Algorithms，2008，33 （2）：187－218.

［12］Cormen T H，Leiserson C E，Rivest R L，et al.introduction to algorithms ［M］.3rd ed.The MIT Press，2009.