劉靖宇，楊雷，趙秀平，李娟，武優(yōu)西

（河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401）

DeduBS：一種基于Hash匹配的數(shù)據(jù)消重遠(yuǎn)程備份系統(tǒng)

劉靖宇，楊雷，趙秀平，李娟，武優(yōu)西

（河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401）

數(shù)據(jù)備份規(guī)模的不斷增大，網(wǎng)絡(luò)帶寬成為了遠(yuǎn)程數(shù)據(jù)備份系統(tǒng)的瓶頸．針對(duì)這個(gè)問題，本文提出了一種基于Hash匹配的數(shù)據(jù)消重遠(yuǎn)程備份系統(tǒng)：DeduBS系統(tǒng)．DeduBS系統(tǒng)通過數(shù)據(jù)消重，避免了在數(shù)據(jù)備份過程中傳輸重復(fù)數(shù)據(jù)，有效地提高了網(wǎng)絡(luò)傳輸效率．DeduBS系統(tǒng)在源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)建立Hash庫存儲(chǔ)數(shù)據(jù)塊的Hash值，數(shù)據(jù)傳輸前通過比對(duì)Hash值判斷其是否為重復(fù)數(shù)據(jù)，只傳輸重復(fù)數(shù)據(jù)的Hash值和非重復(fù)數(shù)據(jù)，對(duì)于重復(fù)數(shù)據(jù)接收端通過Hash庫恢復(fù)數(shù)據(jù)．實(shí)驗(yàn)數(shù)據(jù)表明，DeduBS系統(tǒng)可以減少網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量，在降低成本、節(jié)省能耗的同時(shí)，提高數(shù)據(jù)備份的效率．

備份；數(shù)據(jù)消重；Hash值；網(wǎng)絡(luò)傳輸

數(shù)據(jù)備份系統(tǒng)，也稱為容災(zāi)系統(tǒng)或?yàn)?zāi)難恢復(fù)系統(tǒng)，指通過特定的數(shù)據(jù)備份恢復(fù)機(jī)制，能夠在因?yàn)?zāi)難發(fā)生而導(dǎo)致數(shù)據(jù)丟失時(shí)，仍然能夠最大限度地保障提供正常應(yīng)用服務(wù)的計(jì)算機(jī)信息系統(tǒng)，即通過在異地建立和維護(hù)一個(gè)備份存儲(chǔ)系統(tǒng)，利用地理上的分離來保證系統(tǒng)和數(shù)據(jù)對(duì)災(zāi)難性事件的抵御能力，是數(shù)據(jù)保持高可用性的最后一道防線[1]．

按照數(shù)據(jù)備份恢復(fù)功能實(shí)現(xiàn)的距離遠(yuǎn)近，數(shù)據(jù)備份系統(tǒng)可以分為遠(yuǎn)程數(shù)據(jù)備份恢復(fù)系統(tǒng)和本地?cái)?shù)據(jù)備份恢復(fù)系統(tǒng)．本地?cái)?shù)據(jù)備份恢復(fù)系統(tǒng)僅對(duì)人為操作失誤、軟件錯(cuò)誤等有效，無法應(yīng)對(duì)自然災(zāi)害，如火災(zāi)、地震，甚至恐怖襲擊，因此對(duì)于數(shù)據(jù)依賴程度較高的場合，即使使用了本地?cái)?shù)據(jù)備份恢復(fù)系統(tǒng)，仍然需要進(jìn)行遠(yuǎn)程數(shù)據(jù)備份．

遠(yuǎn)程數(shù)據(jù)備份是數(shù)據(jù)容災(zāi)的一種重要手段，通過將本地?cái)?shù)據(jù)復(fù)制到異地來保證數(shù)據(jù)的安全，本地存儲(chǔ)系統(tǒng)稱為源節(jié)點(diǎn)，遠(yuǎn)程存儲(chǔ)系統(tǒng)稱為目標(biāo)節(jié)點(diǎn)．遠(yuǎn)程數(shù)據(jù)備份面臨的一個(gè)主要問題是網(wǎng)絡(luò)帶寬的限制．通過光纖網(wǎng)絡(luò)可以很好的解決網(wǎng)絡(luò)帶寬問題，但是，遠(yuǎn)程數(shù)據(jù)備份通常部署在不同建筑里，甚至兩個(gè)不同的城市，使用光纖網(wǎng)絡(luò)極大的提高了遠(yuǎn)程數(shù)據(jù)備份的成本．普通IP網(wǎng)絡(luò)雖然成本很低，但是隨著數(shù)據(jù)量的飛速增長，普通IP網(wǎng)絡(luò)的帶寬很難滿足備份系統(tǒng)的要求，往往會(huì)因?yàn)榫W(wǎng)絡(luò)延遲或阻塞造成數(shù)據(jù)丟失，網(wǎng)絡(luò)成為了遠(yuǎn)程數(shù)據(jù)備份的瓶頸．

因此，需要深入研究如何提高普通網(wǎng)絡(luò)的帶寬效果，在不增加成本的情況下，滿足系統(tǒng)要求．

研究表明[2]，在存儲(chǔ)系統(tǒng)中，往往存在著大量的重復(fù)數(shù)據(jù)，最高可達(dá)數(shù)據(jù)總量的800%，在雙機(jī)熱備系統(tǒng)中，無論是主-從方式還是雙主機(jī)方式，都需要保證兩個(gè)節(jié)點(diǎn)間的數(shù)據(jù)一致性，因此不能直接利用重復(fù)數(shù)據(jù)刪除技術(shù)刪除冗余數(shù)據(jù)，而備份這些重復(fù)數(shù)據(jù)會(huì)造成嚴(yán)重的網(wǎng)絡(luò)資源浪費(fèi)．為解決遠(yuǎn)程數(shù)據(jù)備份系統(tǒng)中的網(wǎng)絡(luò)瓶頸，本文提出1種利用數(shù)據(jù)去重技術(shù)避免重復(fù)數(shù)據(jù)傳輸?shù)倪h(yuǎn)程數(shù)據(jù)備份系統(tǒng)（Remote Data Backup System Based on Data Deduplicaion for Eliminating Duplicate Transmission，DeduBS）．

1 研究現(xiàn)狀

隨著信息技術(shù)的發(fā)展，數(shù)據(jù)信息在社會(huì)生活的各個(gè)方面都扮演者至關(guān)重要的角色，數(shù)據(jù)信息的安全性也日益重要．

RAID通過設(shè)置冗余來提高數(shù)據(jù)的安全性，但是RAID只能處理因硬件故障引起的數(shù)據(jù)丟失．一般情況下，RAID只能容忍1到2個(gè)磁盤同時(shí)出現(xiàn)故障．對(duì)于因操作錯(cuò)誤、病毒和自然災(zāi)害等因素引起的數(shù)據(jù)丟失，RAID就無能為力了．因此除RAID外，大量數(shù)據(jù)保護(hù)技術(shù)得到廣泛應(yīng)用，其中主要有寫前拷貝（copy-onwrite）、軟件快照技術(shù)（snapshot）[3]、鏡像技術(shù)[4]、連續(xù)數(shù)據(jù)保護(hù)[5]（continuous data protection，CDP）等．

數(shù)據(jù)備份系統(tǒng)有3種備份方式：完全備份，增量備份和差量備份[6]．完全備份（FullBackup）是指對(duì)整個(gè)系統(tǒng)或用戶指定的所有文件數(shù)據(jù)進(jìn)行一次全面的備份．其優(yōu)點(diǎn)是數(shù)據(jù)恢復(fù)簡單，不足之處是備份過程較長，而且會(huì)產(chǎn)生大量冗余數(shù)據(jù)，浪費(fèi)存儲(chǔ)空間．增量備份（IncrementalBackup）只備份相對(duì)于上一次備份操作創(chuàng)建或者更新過的數(shù)據(jù)，節(jié)省了磁帶空間并且縮短了備份時(shí)間，但是數(shù)據(jù)恢復(fù)時(shí)操作復(fù)雜，而且每次備份對(duì)前一次備份數(shù)據(jù)的依存度大，導(dǎo)致增量備份的可靠性很差．差分備份（DifferentialBackup）只備份上一次完全備份后新產(chǎn)生和更新的數(shù)據(jù)．差分備份有效避免了前兩種方法的缺點(diǎn)而保留了其優(yōu)點(diǎn)，應(yīng)用比較廣泛．

數(shù)據(jù)存儲(chǔ)驚人的增長速度意味著數(shù)據(jù)中心需要海量的存儲(chǔ)空間，為了緩解存儲(chǔ)系統(tǒng)的空間增長問題，縮減數(shù)據(jù)占用空間，節(jié)省網(wǎng)絡(luò)帶寬資源，降低成本，重復(fù)數(shù)據(jù)刪除技術(shù)大量應(yīng)用于存儲(chǔ)備份和歸檔系統(tǒng)中[7-8]．

重復(fù)數(shù)據(jù)刪除的目的在于節(jié)省存儲(chǔ)空間和網(wǎng)絡(luò)帶寬資源，可以通過數(shù)據(jù)縮減率（Data Elimination Ratio，DER）來衡量重復(fù)數(shù)據(jù)刪除的效果，數(shù)據(jù)縮減率是指重復(fù)數(shù)據(jù)刪除之前的數(shù)據(jù)量（ByteIn）與經(jīng)過重復(fù)數(shù)據(jù)刪除之后的數(shù)據(jù)量（ByteOut）之比[9]，公式表示為

重復(fù)數(shù)據(jù)刪除可以實(shí)現(xiàn)在文件層次上，也可以實(shí)現(xiàn)在塊層次上，甚至實(shí)現(xiàn)在位層次上．為達(dá)到更高的數(shù)據(jù)縮減率，需要尋找恰當(dāng)?shù)臄?shù)據(jù)劃分策略和劃分粒度．常采用的劃分策略包括：全文件劃分、靜態(tài)劃分、基于內(nèi)容分塊、基于應(yīng)用分塊[10-11]和Delta編碼．

應(yīng)用在備份領(lǐng)域的重復(fù)數(shù)據(jù)刪除技術(shù)主要由兩類：基于目標(biāo)數(shù)據(jù)和基于源數(shù)據(jù)．基于目標(biāo)數(shù)據(jù)的重復(fù)數(shù)據(jù)刪除，是數(shù)據(jù)在經(jīng)過網(wǎng)絡(luò)傳輸后進(jìn)行重復(fù)數(shù)據(jù)刪除，便于實(shí)現(xiàn)并且可以獲得較高的數(shù)據(jù)縮減率；而基于源數(shù)據(jù)的重復(fù)數(shù)據(jù)刪除，則是在數(shù)據(jù)備份前進(jìn)行重復(fù)數(shù)據(jù)的刪除工作，能夠節(jié)省網(wǎng)絡(luò)帶寬，但數(shù)據(jù)縮減率不高．

2 基于數(shù)據(jù)消重的遠(yuǎn)程備份系統(tǒng)

針對(duì)遠(yuǎn)程數(shù)據(jù)備份系統(tǒng)的網(wǎng)絡(luò)瓶頸，本文提出一種利用數(shù)據(jù)去重技術(shù)避免重復(fù)數(shù)據(jù)傳輸?shù)倪h(yuǎn)程數(shù)據(jù)備份系統(tǒng)（RemoteDataBackupSystemBasedonDataDeduplicaionforEliminating DuplicateTransmission，DeduBS），系統(tǒng)結(jié)構(gòu)如圖1所示．

圖1中，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)通過普通IP網(wǎng)絡(luò)互連，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)結(jié)構(gòu)對(duì)稱，數(shù)據(jù)備份時(shí)采用基于Hash值的數(shù)據(jù)消重算法，可以大量減少網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量．

DeduBS系統(tǒng)中數(shù)據(jù)分為2部分：一部分是由用戶或應(yīng)用程序產(chǎn)生的正常數(shù)據(jù)，存儲(chǔ)在大規(guī)模存儲(chǔ)系統(tǒng)里，通常是由磁盤組成的磁盤陣列；另一部分是數(shù)據(jù)的Hash值，存儲(chǔ)在SSD固態(tài)盤中．

DeduBS系統(tǒng)采用塊級(jí)數(shù)據(jù)消重算法，在Hash庫中為每個(gè)數(shù)據(jù)塊創(chuàng)建1個(gè)Hash值．劃分?jǐn)?shù)據(jù)塊大小可采用不同的粒度．粒度劃分越細(xì)，數(shù)據(jù)消重率越高，消重效果越明顯，但是服務(wù)器計(jì)算量也越大，會(huì)加重CPU負(fù)載；粒度劃分越粗，雖然服務(wù)器計(jì)算量減少，但是消重效果也會(huì)顯著降低．在實(shí)際應(yīng)用中，可根據(jù)系統(tǒng)環(huán)境調(diào)整數(shù)據(jù)塊劃分粒度．

Hash值所占空間很小，但訪問比較頻繁，因此Hash庫存儲(chǔ)在隨機(jī)讀寫性能高的固態(tài)盤中．

數(shù)據(jù)塊的大小可以根據(jù)系統(tǒng)環(huán)境和不同應(yīng)用設(shè)為4 kB、8 kB、16 kB等不同大?。?dāng)數(shù)據(jù)塊以4 kB大小劃分時(shí)，采用MD5算法計(jì)算的Hash值編碼為16個(gè)字節(jié)，所占存儲(chǔ)空間僅占原始數(shù)據(jù)的1/256．

存儲(chǔ)系統(tǒng)中的每個(gè)數(shù)據(jù)塊都有1個(gè)Hash值存放在Hash庫中，Hash庫結(jié)構(gòu)如圖2所示．

圖1 DeduBS系統(tǒng)結(jié)構(gòu)圖Fig.1DeduBS Architecture

DeduBS系統(tǒng)屬于熱備份，目的在于對(duì)數(shù)據(jù)實(shí)現(xiàn)實(shí)時(shí)備份，使源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的數(shù)據(jù)同步更新，保持一致性．當(dāng)源節(jié)點(diǎn)接收到1個(gè)數(shù)據(jù)塊（目標(biāo)塊）的寫請(qǐng)求后，將數(shù)據(jù)寫入到目標(biāo)塊，并計(jì)算數(shù)據(jù)塊的Hash值，對(duì)比Hash庫中的Hash值．

如果Hash庫中沒有相匹配的Hash值，源節(jié)點(diǎn)將數(shù)據(jù)通過網(wǎng)絡(luò)傳送到目標(biāo)節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)接收數(shù)據(jù)并將其寫入存儲(chǔ)系統(tǒng)．

圖2 Hash庫結(jié)構(gòu)Fig.2Hash Repository

當(dāng)本次寫請(qǐng)求中某個(gè)數(shù)據(jù)塊或某幾個(gè)數(shù)據(jù)塊的Hash值在Hash庫中找到匹配項(xiàng)后，說明在存儲(chǔ)系統(tǒng)中已經(jīng)存儲(chǔ)了相同內(nèi)容的數(shù)據(jù)塊，可判定該數(shù)據(jù)塊為重復(fù)數(shù)據(jù)．由于源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的數(shù)據(jù)同步，因此，目標(biāo)節(jié)點(diǎn)中也存在著和該數(shù)據(jù)塊內(nèi)容相同的數(shù)據(jù)．這時(shí)，源節(jié)點(diǎn)不再將此數(shù)據(jù)塊傳送給目標(biāo)節(jié)點(diǎn)，而是只傳送數(shù)據(jù)塊的Hash值．因?yàn)镠ash值的大小相對(duì)于數(shù)據(jù)塊來說要小很多，所以傳送Hash值所需的網(wǎng)絡(luò)帶寬和時(shí)間要比傳送數(shù)據(jù)塊要少很多，可以充分節(jié)省網(wǎng)絡(luò)資源．

例如，源節(jié)點(diǎn)接收到一個(gè)寫請(qǐng)求，將數(shù)據(jù)塊A寫入到存儲(chǔ)系統(tǒng)，相應(yīng)的，數(shù)據(jù)塊A應(yīng)通過網(wǎng)絡(luò)傳輸?shù)侥繕?biāo)節(jié)點(diǎn)．源節(jié)點(diǎn)在與目標(biāo)節(jié)點(diǎn)建立連接后通過以下步驟完成寫操作和數(shù)據(jù)傳輸：

1）將數(shù)據(jù)塊A寫入到目標(biāo)塊；

2）計(jì)算數(shù)據(jù)塊A的Hash值；

3）將數(shù)據(jù)塊A的Hash值與Hash庫對(duì)比；

4）如果沒有匹配項(xiàng)，直接將數(shù)據(jù)塊A通過網(wǎng)絡(luò)傳送給目標(biāo)節(jié)點(diǎn)；

5）如果發(fā)現(xiàn)Hash庫有相匹配的Hash值，源節(jié)點(diǎn)將數(shù)據(jù)塊A的Hash值傳送給目標(biāo)節(jié)點(diǎn)；

6）數(shù)據(jù)塊A的Hash值寫入Hash庫．

目標(biāo)節(jié)點(diǎn)通過以下步驟完成寫操作：

1）判斷接收的內(nèi)容為數(shù)據(jù)還是數(shù)據(jù)的Hash值；

2）如果接收的為數(shù)據(jù)，直接將數(shù)據(jù)寫入存儲(chǔ)系統(tǒng)；

3）計(jì)算數(shù)據(jù)塊的Hash值并寫入Hash庫；

4）如果接收的為Hash值，跟據(jù)Hash值在Hash庫中查找匹配項(xiàng)；

5）根據(jù)Hash庫中查找到的相匹配的Hash值，確定數(shù)據(jù)塊所在位置，假設(shè)為數(shù)據(jù)塊B；

6）將數(shù)據(jù)塊B復(fù)制到數(shù)據(jù)塊A的存儲(chǔ)空間；

7）將數(shù)據(jù)塊A的Hash值寫入Hash庫；

8）向源節(jié)點(diǎn)發(fā)送“完成”信號(hào)．

傳送過程中，為區(qū)分?jǐn)?shù)據(jù)和數(shù)據(jù)的Hash值，在傳送的數(shù)據(jù)包中加入標(biāo)識(shí)符，如圖3所示．如果傳送的是數(shù)據(jù)，將標(biāo)識(shí)符清“0”，如果傳送的是數(shù)據(jù)的Hash值，將標(biāo)識(shí)符置“1”．

當(dāng)寫入數(shù)據(jù)塊為重復(fù)數(shù)據(jù)時(shí)，DeduBS系統(tǒng)只傳輸數(shù)據(jù)的Hash值，節(jié)約了網(wǎng)絡(luò)帶寬，系統(tǒng)性能得到了極大的提升．例如，數(shù)據(jù)塊的劃分粒度為4KB，寫1個(gè)大小為8MB的文件，文件被分成了2048個(gè)數(shù)據(jù)塊．假設(shè)其中50%的數(shù)據(jù)塊為重復(fù)數(shù)據(jù)，則DeduBS系統(tǒng)需要向目標(biāo)節(jié)點(diǎn)傳送1024個(gè)數(shù)據(jù)塊和1024個(gè)數(shù)據(jù)塊的Hash值，相當(dāng)于傳送4MB的數(shù)據(jù)和4KB的Hash值，實(shí)際傳送數(shù)據(jù)量遠(yuǎn)遠(yuǎn)低于原數(shù)據(jù)8 MB．

圖3 DeduBS系統(tǒng)數(shù)據(jù)傳輸格式Fig.3DeduBS Network Package

3 數(shù)據(jù)恢復(fù)

當(dāng)源節(jié)點(diǎn)出現(xiàn)故障后，需要從目標(biāo)節(jié)點(diǎn)將數(shù)據(jù)復(fù)制到源節(jié)點(diǎn)，進(jìn)行數(shù)據(jù)恢復(fù)．這時(shí)，由于目標(biāo)節(jié)點(diǎn)和源節(jié)點(diǎn)的數(shù)據(jù)一致性被破壞，無法直接使用第3節(jié)中方法傳送數(shù)據(jù)．?dāng)?shù)據(jù)恢復(fù)時(shí)，需要在目標(biāo)節(jié)點(diǎn)創(chuàng)建1個(gè)臨時(shí)Hash庫．在目標(biāo)節(jié)點(diǎn)向源節(jié)點(diǎn)傳送數(shù)據(jù)塊的同時(shí)，將數(shù)據(jù)塊的Hash值寫入臨時(shí)Hash庫．從傳送第2個(gè)數(shù)據(jù)塊開始，將數(shù)據(jù)塊的Hash值與臨時(shí)Hash庫中的Hash值對(duì)比，查找匹配項(xiàng)．目標(biāo)節(jié)點(diǎn)在與源節(jié)點(diǎn)建立后通過以下步驟完成數(shù)據(jù)傳輸：

1）創(chuàng)建臨時(shí)Hash庫；

2）讀取第1個(gè)數(shù)據(jù)塊，將數(shù)據(jù)塊通過網(wǎng)絡(luò)傳送到源節(jié)點(diǎn)；并將該數(shù)據(jù)塊的Hash值寫入臨時(shí)Hash庫；

3）讀取下一個(gè)數(shù)據(jù)塊的Hash值，在臨時(shí)Hash庫中查找匹配值；

4）如果存在匹配項(xiàng)，將Hash值傳送到源節(jié)點(diǎn)；

5）如果沒有匹配項(xiàng)，直接將數(shù)據(jù)塊傳送到源節(jié)點(diǎn)；

6）更新臨時(shí)Hash庫；

7）判斷數(shù)據(jù)是否傳送完，如傳送未完成，轉(zhuǎn)到步驟3）繼續(xù)執(zhí)行；

8）傳送完成，結(jié)束數(shù)據(jù)恢復(fù)．

源節(jié)點(diǎn)首先需要修復(fù)失效設(shè)備故障，然后同目標(biāo)節(jié)點(diǎn)建立連接進(jìn)行數(shù)據(jù)恢復(fù)，源節(jié)點(diǎn)通過以下步驟接收數(shù)據(jù)：

1）判斷接收的內(nèi)容為數(shù)據(jù)，還是數(shù)據(jù)的Hash值；

2）如果接收的是數(shù)據(jù)，直接將數(shù)據(jù)寫入存儲(chǔ)設(shè)備；

3）計(jì)算接收數(shù)據(jù)的Hash值并更新Hash庫；

4）如果接受的是Hash值，跟據(jù)Hash值在Hash庫中查找匹配項(xiàng)；

5）根據(jù)Hash庫中查找到相匹配的Hash值，確定數(shù)據(jù)塊所在位置；

6）復(fù)制數(shù)據(jù)塊；

7）更新Hash庫；

8）向目標(biāo)節(jié)點(diǎn)發(fā)送“完成”信號(hào)．

需要說明的是，無論是在數(shù)據(jù)備份過程中，還是在數(shù)據(jù)恢復(fù)過程，為保證數(shù)據(jù)傳輸效率，數(shù)據(jù)發(fā)送后并不等待對(duì)方應(yīng)答信號(hào)，而是直接發(fā)送下一個(gè)數(shù)據(jù)塊，只是在一定時(shí)間后沒有收到應(yīng)答信號(hào)，再重新發(fā)送該數(shù)據(jù)塊．另外，在雙機(jī)熱備系統(tǒng)中，無論是主-從方式還是雙主機(jī)方式，都需要保證兩個(gè)節(jié)點(diǎn)間的數(shù)據(jù)一致性．因此，盡管DeduBS系統(tǒng)中的數(shù)據(jù)消重技術(shù)與傳統(tǒng)的重復(fù)數(shù)據(jù)刪除技術(shù)在原理和方式上類似，但是DeduBS系統(tǒng)的目的并不是利用重復(fù)數(shù)據(jù)刪除技術(shù)減少數(shù)據(jù)存儲(chǔ)量，而是通過數(shù)據(jù)傳輸過程中的消重減少網(wǎng)絡(luò)數(shù)據(jù)的傳送量，在提高網(wǎng)絡(luò)利用率的同時(shí)，仍能保證兩個(gè)節(jié)點(diǎn)間的數(shù)據(jù)一致性．

4 系統(tǒng)測試

測試平臺(tái)由2臺(tái)服務(wù)器組成，存儲(chǔ)系統(tǒng)為Linuxkernel2.6.35.32，2臺(tái)服務(wù)器配置相同，分別作為源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，服務(wù)器CPU為IntelXeon（R）X3220，內(nèi)存4GB；SeagateST3500630AS硬盤，容量500GB；Crucial CT128M4SSD2固態(tài)盤，容量128 GB；網(wǎng)絡(luò)帶寬4 Mbps．

Hash值計(jì)算采用MD5算法，Hash庫占用2 GB的存儲(chǔ)空間．隨著存儲(chǔ)容量的增大，Hash所占空間也會(huì)隨之增大，128 GB固態(tài)盤可以存放約32 TB數(shù)據(jù)的Hash值．

數(shù)據(jù)縮減率測試結(jié)果如圖4所示．

由圖4可知，當(dāng)數(shù)據(jù)塊劃分越小時(shí)，數(shù)據(jù)縮減率越高，反之，數(shù)據(jù)塊劃分越大，數(shù)據(jù)縮減率就越低．?dāng)?shù)據(jù)塊劃分大小為4 KB時(shí)，50 G、100 G和200 G數(shù)據(jù)中，數(shù)據(jù)縮減率分別為13%、19%和27%；數(shù)據(jù)塊劃分大小為8KB時(shí)，數(shù)據(jù)縮減率分別為8%、11%和17%；數(shù)據(jù)塊劃分大小為16 KB時(shí)，數(shù)據(jù)縮減率分別為4%、7%和11%．可見，隨著數(shù)據(jù)量的最大，重復(fù)率越來越高，在大規(guī)模數(shù)據(jù)存儲(chǔ)系統(tǒng)中，數(shù)據(jù)縮減率最高能達(dá)到60%以上．

圖5為數(shù)據(jù)傳輸時(shí)間測試結(jié)果．

與圖4中的實(shí)驗(yàn)結(jié)果相符，當(dāng)數(shù)據(jù)塊劃分粒度細(xì)時(shí)，由于數(shù)據(jù)縮減率高，因此數(shù)據(jù)傳輸時(shí)間較短，數(shù)據(jù)塊大小為4 KB、8KB和16KB時(shí)，傳輸50GB數(shù)據(jù)分別需要36.8h、41.4 h和41.2h，傳輸100GB數(shù)據(jù)分別需要76.5h、80.1h和80h，傳輸50GB數(shù)據(jù)分別需要137.3h、149.4h和153.1h．以數(shù)據(jù)塊大小為4KB的傳輸時(shí)間為標(biāo)準(zhǔn)，數(shù)據(jù)塊增大后，數(shù)據(jù)傳輸速率比理論計(jì)算值要稍低一些，這是因?yàn)榫W(wǎng)絡(luò)傳輸大數(shù)據(jù)塊要比傳輸小數(shù)據(jù)塊的效率要高．

通過實(shí)驗(yàn)結(jié)果可以看出，當(dāng)數(shù)據(jù)量增大時(shí)，重復(fù)數(shù)據(jù)率也隨之增加，對(duì)于遠(yuǎn)程數(shù)據(jù)備份系統(tǒng)來說，傳輸這些重復(fù)數(shù)據(jù)會(huì)浪費(fèi)大量網(wǎng)絡(luò)資源和能耗．DeduBS系統(tǒng)利用基于Hash值的數(shù)據(jù)去重技術(shù)，避免了傳輸重復(fù)數(shù)據(jù)，提高了遠(yuǎn)程數(shù)據(jù)備份系統(tǒng)的效率，節(jié)省網(wǎng)絡(luò)資源和運(yùn)行成本．

圖4 DeduBS系統(tǒng)數(shù)據(jù)縮減率Fig.4DeduBS Data Reduction Rate

圖5 DeduBS系統(tǒng)數(shù)據(jù)備份時(shí)間Fig.5DeduBS Data Backup Time

5 小結(jié)

本文針對(duì)遠(yuǎn)程數(shù)據(jù)備份系統(tǒng)的網(wǎng)絡(luò)瓶頸問題，提出了一種利用數(shù)據(jù)消重避免重復(fù)數(shù)據(jù)傳輸?shù)倪h(yuǎn)程備份系統(tǒng)：DeduBS系統(tǒng)，實(shí)現(xiàn)了基于普通IP網(wǎng)絡(luò)的遠(yuǎn)程數(shù)據(jù)實(shí)時(shí)備份．在源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)建立Hash庫，存儲(chǔ)所有數(shù)據(jù)的Hash值．當(dāng)源節(jié)點(diǎn)數(shù)據(jù)更新后，需要向目標(biāo)節(jié)點(diǎn)傳遞更新數(shù)據(jù)，通過計(jì)算數(shù)據(jù)的Hash值，比對(duì)Hash庫，如果存在與之相匹配的Hash值，則說明在源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)均已存在與更新數(shù)據(jù)相同的數(shù)據(jù)塊．這時(shí)，只需向目標(biāo)節(jié)點(diǎn)傳送數(shù)據(jù)的Hash值即可，而不是傳輸數(shù)據(jù)本身．目標(biāo)節(jié)點(diǎn)接收到數(shù)據(jù)的Hash值，在本地Hash庫中找到匹配項(xiàng)，通過Hash值可以找到存儲(chǔ)在本地的相同數(shù)據(jù)，直接從本地復(fù)制數(shù)據(jù)到目的數(shù)據(jù)塊即可．在大規(guī)模存儲(chǔ)系統(tǒng)中，存在著大量的重復(fù)數(shù)據(jù)，因此，利用數(shù)據(jù)去重技術(shù)實(shí)現(xiàn)遠(yuǎn)程數(shù)據(jù)備份，可以提高網(wǎng)絡(luò)利用率，節(jié)省網(wǎng)絡(luò)資源．同時(shí)，由于傳輸?shù)臄?shù)據(jù)量減少，也降低了系統(tǒng)能耗．

實(shí)驗(yàn)數(shù)據(jù)表明，隨著備份數(shù)據(jù)集的增大，DeduBS系統(tǒng)的傳輸數(shù)據(jù)量較原始數(shù)據(jù)明顯減少，傳輸時(shí)間縮短，是一種基于普通IP網(wǎng)絡(luò)、高效、節(jié)能的遠(yuǎn)程數(shù)據(jù)備份系統(tǒng)．

[1]楊天明．網(wǎng)絡(luò)備份中重復(fù)數(shù)據(jù)刪除技術(shù)研究[D]．武漢：華中科技大學(xué)，2010．

[2]Brain Babineau，Jonh Mcknight．Digital archiving：end-user surevey and market forecast[EB/OL]．http：//www.esg-global.com/default/assets/ File/ESG%20Research%20Report%20Digital%20Archive%20Market%20Forecast%20Abstract.pdf，[2013-2-25]．

[3]Yang Jing，Cao Qiang，Li Xu，et al．ST-CDP：Snapshots in TRAP for continuous data protection[J]．IEEE Transactions on Computers，2012，61（6）：753-766．

[4]YangQing，XiaoWeijun，RenJin．TRAP-array：adiskarrayarchitectureprovidingtimelyrecoverytoanypoint-in-time[J]．ComputerArchitecture News，2006，34（2）：289-300．

[5]LiuJingning，YangTianming，LiZuoheng，etal．TSPSCDP：atime-stampcontinuous dataprotectionapproachbasedonpipelinestrategy．Japan-China Joint Workshop on Frontier of Computer Science and Technology[C]//Nagasahi：IEEE 2008：96-102．

[6]Qian Cunhua，Huang Yingyan，Zhao Xufeng，et al．Optimal backup interval for a database system with full and periodicincremental backup[J]．Journal of Computers，2010，5（4）：557-564．

[7]敖莉，舒繼武，李明強(qiáng)．重復(fù)數(shù)據(jù)刪除技術(shù)[J]．軟件學(xué)報(bào)，2010（5）：916-929．

[8]付印金，肖儂，劉芳．重復(fù)數(shù)據(jù)刪除關(guān)鍵技術(shù)研究進(jìn)展[J]．計(jì)算機(jī)研究與發(fā)展，2012（1）：12-20．

[9]楊義先，姚文斌，陳釗．信息系統(tǒng)災(zāi)備技術(shù)綜論[J]．北京郵電大學(xué)學(xué)報(bào)，2012，4（30）：1-6．

[10]MuthitacharoenA，ChenB，Mazieres D．A low-bandwidth network file system[J]．ACM SIGOPS OperatingSystems Review，2002，35（5）：174-187．

[11]Liu C，Lu Y，Shi C，et al．ADMAD：Application-driven metadata aware de-duplication archival storage system．The Fifth IEEE International Workshop on Storage Network Architecture and Parallel I/Os（SNAPI）[C]//Baltimore，MD：IEEE，2008：29-35．

[責(zé)任編輯 田豐夏紅梅]

DeduBS:a duplicate eliminating remote backup system based on hash matching

LIU Jingyu，YANG Lei，ZHAO Xiuping，LI Juan，WU Youxi

(School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China)

With data increasing,network bandwidth has become a bottleneck in remote data backup system.A new duplicate eliminating remotebackup systemisproposedbasedonHash matching:DeduBS.DeduBS improvestheefficiency of network transmission by deduplication.In DeduBS,a Hash library is established in both the source node and the destination node to store alldata blocks Hash value.Before being transferred,the data will bejudged whetherit is duplication or not by its Hash value.Only the non-duplicate and the Hash value of duplicate are transferred in DeduBS.Experiment shows thatthe DeduBS can transfer less data and save the cost and energy of backup system,thus improving network utilization.

backup;duplicate eliminating;Hash;network transmission

TP309.3

A

1007-2373(2015)04-0032-06

10.14081/j.cnki.hgdxb.2015.04.007

2014-09-05

河北省教育廳青年基金（QN2014192）；河北省自然科學(xué)基金（F2013202138）；河北省教育廳重點(diǎn)項(xiàng)目（ZH2012038）

劉靖宇（1976-），男（漢族），講師，博士．通訊作者：武優(yōu)西（1974-），男（漢族），教授，博士．

數(shù)字出版日期：2015-06-17

數(shù)字出版網(wǎng)址：http://www.cnki.net/kcms/detail/13.1208.T.20150617.1536.003.html