一種基于源端數(shù)據(jù)重刪的數(shù)據(jù)備份和恢復(fù)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

王興虎,何安元

(1.南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 南京 211106) (2.南京航空航天大學(xué)信息化技術(shù)中心,江蘇 南京 211106)

近年來(lái),信息技術(shù)的快速發(fā)展和傳統(tǒng)行業(yè)的信息化轉(zhuǎn)型加快導(dǎo)致了數(shù)據(jù)量的飛速增長(zhǎng). 數(shù)據(jù)占用了越來(lái)越多的存儲(chǔ)空間,企業(yè)的數(shù)據(jù)管理和存儲(chǔ)成本逐年上升,大量的存儲(chǔ)花費(fèi)與嚴(yán)峻的數(shù)據(jù)安全問(wèn)題給傳統(tǒng)企業(yè)帶來(lái)了巨大的經(jīng)濟(jì)壓力. 文獻(xiàn)[1]研究報(bào)告表明,47%的企業(yè)主管擔(dān)心企業(yè)的預(yù)算被用于不必要的存儲(chǔ),42%的主管擔(dān)心高昂的存儲(chǔ)成本. 文獻(xiàn)[2]研究表明,日常存儲(chǔ)的業(yè)務(wù)數(shù)據(jù)中存在60%的冗余業(yè)務(wù)數(shù)據(jù),冗余數(shù)據(jù)的存在造成了存儲(chǔ)資源的浪費(fèi). 為了解決數(shù)據(jù)冗余問(wèn)題,重復(fù)數(shù)據(jù)刪除技術(shù)[3-4]成為了近年來(lái)的研究熱點(diǎn). 重復(fù)數(shù)據(jù)刪除技術(shù)可以有效地刪除數(shù)據(jù)存儲(chǔ)中的冗余數(shù)據(jù),確保數(shù)據(jù)存儲(chǔ)中同樣的數(shù)據(jù)信息只有一份,大大減少了備份時(shí)間和存儲(chǔ)空間,在備份、歸檔和數(shù)據(jù)容災(zāi)恢復(fù)方面[5]應(yīng)用廣泛. 當(dāng)前在國(guó)際上比較知名的數(shù)據(jù)備份與恢復(fù)產(chǎn)品有基于源端數(shù)據(jù)的EMC Avaram,基于目標(biāo)端的Data Domain、IBM的Diligent以及Commvault的Simpana.

重復(fù)刪除技術(shù)會(huì)消耗系統(tǒng)大量的計(jì)算資源,為了有效提高重刪系統(tǒng)的性能,學(xué)者提出了一些有效的解決辦法:如避免重刪系統(tǒng)中的磁盤(pán)瓶頸技術(shù)[6]以及基于相似的搜索技術(shù)[7]、基于集群的增量壓縮技術(shù)[8]. Sun等[9]設(shè)計(jì)了基于分布式系統(tǒng)的重刪方案,即解決NP-Hard問(wèn)題. 設(shè)計(jì)新的文件分區(qū)算法,通過(guò)增量來(lái)記錄有效訪問(wèn),Chu等[10]使用分塊技術(shù)減少了相同塊的重復(fù)對(duì)比,提出了Dis-Dedup的分配策略;Xue Yua等[11]在多域架構(gòu)的基礎(chǔ)上提出了云存儲(chǔ)中的重刪技術(shù)EPCDD. 在綜合參考現(xiàn)有技術(shù)的基礎(chǔ)上,本文設(shè)計(jì)和實(shí)現(xiàn)了基于源端數(shù)據(jù)重刪技術(shù)的數(shù)據(jù)備份與恢復(fù)系統(tǒng),通過(guò)在客戶端建立預(yù)處理并行計(jì)算模塊和在服務(wù)端建立高效的緩存模型,有效地提高整體備份效率.

1 備份與恢復(fù)系統(tǒng)結(jié)構(gòu)

根據(jù)文件系統(tǒng)執(zhí)行源端重復(fù)數(shù)據(jù)刪除的存儲(chǔ)節(jié)點(diǎn)位置的不同,目前主要有源端重復(fù)數(shù)據(jù)刪除技術(shù)和目標(biāo)端重復(fù)數(shù)據(jù)刪除技術(shù). 源端重復(fù)數(shù)據(jù)刪除直接在文件系統(tǒng)內(nèi)實(shí)現(xiàn),少部分的數(shù)據(jù)通過(guò)網(wǎng)絡(luò)傳輸;目標(biāo)端重復(fù)數(shù)據(jù)刪除中的所有數(shù)據(jù)需要通過(guò)網(wǎng)絡(luò)傳輸?shù)竭h(yuǎn)端存儲(chǔ)節(jié)點(diǎn)進(jìn)行重刪操作,它會(huì)占用大量網(wǎng)絡(luò)帶寬. 在現(xiàn)有重刪技術(shù)中,基于源端數(shù)據(jù)重刪技術(shù)的數(shù)據(jù)備份具體過(guò)程為:根據(jù)分塊算法對(duì)數(shù)據(jù)流進(jìn)行分塊,然后對(duì)分好的塊計(jì)算哈希(Hash)指紋[12],即對(duì)每個(gè)數(shù)據(jù)塊生成檢索指紋,用來(lái)標(biāo)識(shí)其唯一性;把指紋發(fā)送服務(wù)端進(jìn)行比對(duì),在已存在的數(shù)據(jù)庫(kù)指紋索引表中查找確認(rèn),確定數(shù)據(jù)塊是否已經(jīng)存在備份設(shè)備中,根據(jù)比對(duì)的結(jié)果把新數(shù)據(jù)發(fā)送到服務(wù)端保存起來(lái),已有的數(shù)據(jù)就不再發(fā)送,以達(dá)到節(jié)省帶寬并節(jié)省存儲(chǔ)的目的. 在基于源端數(shù)據(jù)重刪的技術(shù)中,由于客戶端的分塊、計(jì)算指紋需要大量時(shí)間,服務(wù)端存放數(shù)據(jù)時(shí),指紋離散高,頻繁操作數(shù)據(jù)塊耗時(shí)大,從而整體流程耗時(shí)較高. 為了減少耗時(shí),本文提出一個(gè)基于源端數(shù)據(jù)重刪的備份與恢復(fù)系統(tǒng),系統(tǒng)的結(jié)構(gòu)如圖1所示.

該數(shù)據(jù)備份與恢復(fù)系統(tǒng)包含客戶端與服務(wù)端兩部分,客戶端主要包括數(shù)據(jù)流預(yù)處理、數(shù)據(jù)分塊、計(jì)算指紋與索引信息建立,其中預(yù)處理模塊可將輸入數(shù)據(jù)流提前分段并存儲(chǔ),便于之后的并行計(jì)算. 服務(wù)端包括布隆過(guò)濾器(Bloom filter)[13-14]、多級(jí)緩存模型、數(shù)據(jù)庫(kù)與容器(Container). 布隆過(guò)濾器與多級(jí)緩存模型負(fù)責(zé)存儲(chǔ)容器,對(duì)比客戶端傳來(lái)的指紋,便于減少訪問(wèn)數(shù)據(jù)庫(kù)的頻率. 容器負(fù)責(zé)存儲(chǔ)數(shù)據(jù)塊與索引信息,提高緩存工作的效率. 服務(wù)端負(fù)責(zé)指紋對(duì)比、數(shù)據(jù)塊的存儲(chǔ)與檢索功能.

客戶端與服務(wù)端之間通過(guò)SAN網(wǎng)絡(luò)傳輸數(shù)據(jù)塊、索引信息與指紋. 在備份過(guò)程中客戶端將指紋發(fā)送至服務(wù)端進(jìn)行對(duì)比,依據(jù)對(duì)比結(jié)果將沒(méi)有指紋的數(shù)據(jù)塊與索引信息送至服務(wù)端備份,服務(wù)端將接收到的數(shù)據(jù)塊與指紋按位置依次存放在容器中. 恢復(fù)數(shù)據(jù)時(shí),客戶端通過(guò)讀取索引文件把索引信息發(fā)至服務(wù)端,服務(wù)端依據(jù)索引信息找到數(shù)據(jù)塊返回到客戶端.

該體系結(jié)構(gòu)中,客戶端利用數(shù)據(jù)流分段并對(duì)每段數(shù)據(jù)并發(fā)執(zhí)行分塊和指紋計(jì)算,服務(wù)端用獨(dú)立線程進(jìn)行存儲(chǔ)數(shù)據(jù),并借助布隆過(guò)濾器與多級(jí)緩存模型,有效縮短時(shí)間,提高備份效率.

2 客戶端設(shè)計(jì)

客戶端包含預(yù)處理模塊、數(shù)據(jù)分塊、指紋計(jì)算與索引信息建立、緩存. 在備份過(guò)程中客戶端主要實(shí)現(xiàn)重刪功能,將新增數(shù)據(jù)塊發(fā)送至服務(wù)端,并更新數(shù)據(jù)寫(xiě)入結(jié)果. 在恢復(fù)過(guò)程中,客戶端通過(guò)讀取索引文件中對(duì)應(yīng)數(shù)據(jù)塊的索引信息發(fā)送至服務(wù)端并將服務(wù)端發(fā)送來(lái)的數(shù)據(jù)塊放在緩存中,重復(fù)整個(gè)流程直到恢復(fù)所有對(duì)應(yīng)的數(shù)據(jù)塊.

2.1 預(yù)處理模塊

預(yù)處理模塊主要是先通過(guò)對(duì)數(shù)據(jù)流進(jìn)行分段得到多個(gè)數(shù)據(jù)段,再并行處理多個(gè)數(shù)據(jù)段,對(duì)每個(gè)數(shù)據(jù)段進(jìn)行分塊,并計(jì)算每個(gè)數(shù)據(jù)塊的指紋.

(1)數(shù)據(jù)流分段

將待備份的文件以數(shù)據(jù)流的方式傳輸?shù)娇蛻舳?客戶端對(duì)數(shù)據(jù)流可以根據(jù)需求設(shè)定分段大小,例如以20MB為標(biāo)準(zhǔn)對(duì)數(shù)據(jù)流分段,即每個(gè)數(shù)據(jù)段為20MB,尾段可能不滿20MB. 分段的目的是為了方便之后的并行計(jì)算.

(2)并行處理

為了實(shí)現(xiàn)對(duì)多個(gè)數(shù)據(jù)段進(jìn)行并行處理,在客戶端建立一個(gè)預(yù)處理環(huán)形隊(duì)列,此預(yù)處理環(huán)形隊(duì)列用來(lái)存儲(chǔ)數(shù)據(jù)段. 將數(shù)據(jù)段存入預(yù)處理環(huán)形隊(duì)列的具體存放過(guò)程為:若預(yù)處理環(huán)形隊(duì)列中有空間存放傳進(jìn)來(lái)的數(shù)據(jù)段,則將此數(shù)據(jù)段按順序存放在預(yù)處理環(huán)形隊(duì)列的相應(yīng)位置;若預(yù)處理環(huán)形隊(duì)列中沒(méi)有足夠的空間存放,則等待預(yù)處理環(huán)形隊(duì)列中存放的數(shù)據(jù)段處理完、釋放空間后再把傳入的數(shù)據(jù)段存入.

預(yù)處理環(huán)形隊(duì)列中每個(gè)元素即是一個(gè)數(shù)據(jù)段,每個(gè)數(shù)據(jù)段有各自獨(dú)立的線程,對(duì)隊(duì)列中所存放的數(shù)據(jù)段進(jìn)行并行處理,隊(duì)列長(zhǎng)度可以根據(jù)客戶端的CPU并行計(jì)算能力進(jìn)行配置,并行處理多個(gè)數(shù)據(jù)段可充分利用CPU的性能,提高指紋計(jì)算的整體性能.

2.2 數(shù)據(jù)分塊

數(shù)據(jù)分塊是數(shù)據(jù)重刪的關(guān)鍵技術(shù),一般來(lái)說(shuō)對(duì)數(shù)據(jù)流的分塊技術(shù)主要有:定長(zhǎng)分塊[15]技術(shù)(Fix-sized partition,FSP)、變長(zhǎng)分塊[16]技術(shù)(Content-defined chunking,CDC)、滑動(dòng)塊切分[17]技術(shù). 在FSP技術(shù)中,提供一個(gè)預(yù)先定義好的塊,然后所有文件依據(jù)定義好的塊的大小進(jìn)行劃分,通過(guò)哈希算法給劃分后的數(shù)據(jù)塊一個(gè)指紋值,再將指紋值與存儲(chǔ)中的塊指紋值對(duì)比,刪除相同的值. FSP技術(shù)能夠有效減少數(shù)據(jù)占用的存儲(chǔ)空間,降低通過(guò)網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量,但是處理插入與刪除問(wèn)題效率很低. CDC技術(shù)通過(guò)計(jì)算窗口Rabin指紋[18],將文件劃分成長(zhǎng)度不同的塊,再根據(jù)文件內(nèi)容進(jìn)行塊的劃分. CDC算法流程如圖2所示.

從數(shù)據(jù)流頭開(kāi)始,滑動(dòng)窗口中的數(shù)據(jù)流根據(jù)Rabin算法分成若干數(shù)據(jù)塊,圖2中垂直虛線是塊的邊界,當(dāng)數(shù)據(jù)塊的長(zhǎng)度大于預(yù)設(shè)的最大數(shù)據(jù)塊或者滑動(dòng)窗口中的rabin指紋值滿足了預(yù)設(shè)要求時(shí),把此時(shí)窗口位置作為塊的邊界. 然后劃分出的每個(gè)塊用hash函數(shù)(MD5[19],SHA-1[20])計(jì)算指紋值并與已經(jīng)存儲(chǔ)的數(shù)據(jù)塊對(duì)比,如果出現(xiàn)相同的指紋值,就刪除代表的數(shù)據(jù)塊,否則存儲(chǔ)新的數(shù)據(jù)塊. 滑動(dòng)窗口大小固定,每次向后滑動(dòng)一個(gè)字節(jié),直到達(dá)到預(yù)定要求為止. CDC算法可以有效地提高重刪率,重刪率越高,節(jié)省的磁盤(pán)空間越大. 缺點(diǎn)是變長(zhǎng)分塊計(jì)算相對(duì)定長(zhǎng)分塊相對(duì)耗時(shí),并且正常變長(zhǎng)分塊對(duì)于數(shù)據(jù)流都是順序分塊,因?yàn)槊總€(gè)數(shù)據(jù)塊的長(zhǎng)度不固定,在不破壞每一塊的情況下無(wú)法從多個(gè)位置用不同的線程去分塊. 滑塊分塊技術(shù)結(jié)合了固定分塊與可變分塊技術(shù)的優(yōu)點(diǎn). 首先固定塊的大小,用校驗(yàn)函數(shù)(Checksum)計(jì)算分塊后數(shù)據(jù)塊的弱校驗(yàn)值. 弱校驗(yàn)值匹配先前的值,如果匹配不成功則滑動(dòng)數(shù)據(jù)塊,如果匹配成功則進(jìn)一步采用SHA-1算法對(duì)塊進(jìn)行哈希計(jì)算得到強(qiáng)校驗(yàn)值,若強(qiáng)校驗(yàn)值匹配成功,則認(rèn)定該數(shù)據(jù)塊重復(fù);若不匹配則繼續(xù)滑動(dòng)數(shù)據(jù)塊.

研究表明[16],當(dāng)數(shù)據(jù)量較大時(shí),CDC算法具有較好的表現(xiàn),故在本系統(tǒng)中采用CDC分塊. 由于數(shù)據(jù)流通過(guò)預(yù)處理模塊已經(jīng)分段存儲(chǔ)在環(huán)形隊(duì)列中,因此本系統(tǒng)在采用CDC分塊的同時(shí)實(shí)現(xiàn)了在不破壞每一塊的情況下從多個(gè)位置用不同線程分塊.

2.3 指紋計(jì)算與索引信息

數(shù)據(jù)指紋用來(lái)唯一標(biāo)識(shí)數(shù)據(jù)塊的特征,一般選擇抗沖突加密Hash值作為特征,目前MD5、SHA1和Rabin是應(yīng)用最廣泛的HASH算法,具有計(jì)算速度快、節(jié)省存儲(chǔ)空間的優(yōu)勢(shì),本文采用Rabin算法.

(1)指紋計(jì)算

Rabin算法是基于對(duì)系數(shù)為Z2的不可約多項(xiàng)式進(jìn)行模運(yùn)算的算法. 令S=[a1,a2,…,an],S為二進(jìn)制字符串,S(t)是與字符串S關(guān)聯(lián)的n-1項(xiàng)多項(xiàng)式,多項(xiàng)式系數(shù)為Z2,有

S(t)=a1tn-1+a2tn-2+…+an-1t+an.

(1)

令P(t)=btk+b2tk-1+…+bkt+bk+1為Z2的k階不可約多項(xiàng)式,在確定P的形式后,可將Rabin指紋計(jì)算的形式定義為

r(t)=S(t)modp(t),

(2)

定義連續(xù)字符串[X1X2,…,Xω,Xω+1,Xω+2,…],其中每個(gè)字符串為8位的二進(jìn)制字符. 使用寬度大小為ω的滑動(dòng)窗口. 假設(shè)窗口中字符起點(diǎn)為Xi,由多項(xiàng)式Xi(t)表示. 整個(gè)連續(xù)字符串[X1X2,…,Xω,Xω+1,Xω+2,…]在窗口中的Rabin指紋值為

(3)

其中每一ri對(duì)應(yīng)1個(gè)塊. 塊由Bi表示,i=1,2,…,n. 則數(shù)據(jù)塊Bi的指紋值f(Bi)為

f(Bi)=Hash(Bi).

(4)

(2)索引信息

索引信息由按順序記錄每個(gè)數(shù)據(jù)塊的起始位置、長(zhǎng)度和指紋信息組成,供數(shù)據(jù)恢復(fù)時(shí)查找.

2.4 緩存

在數(shù)據(jù)恢復(fù)過(guò)程中,根據(jù)索引信息整理好需要從服務(wù)端獲取數(shù)據(jù)塊的指紋,在客戶端建立一個(gè)16MB的緩存,用于緩存數(shù)據(jù),緩存的大小可以根據(jù)具體情況確定,這么做的目的是為了防止每次讀取較小的數(shù)據(jù)時(shí)客戶端頻繁地向服務(wù)端要數(shù)據(jù),從而在一定程度上減少訪問(wèn)數(shù)據(jù)庫(kù)的頻率.

3 服務(wù)端設(shè)計(jì)

服務(wù)端主要有布隆過(guò)濾器、多級(jí)緩存模型、數(shù)據(jù)庫(kù)與容器,在數(shù)據(jù)備份過(guò)程中服務(wù)端負(fù)責(zé)接收客戶端傳來(lái)的指紋與數(shù)據(jù)庫(kù)中存儲(chǔ)的指紋進(jìn)行比對(duì),并存儲(chǔ)客戶端傳來(lái)的數(shù)據(jù)塊與索引信息. 在數(shù)據(jù)恢復(fù)過(guò)程中,服務(wù)端根據(jù)客戶端發(fā)來(lái)的索引信息查找相應(yīng)數(shù)據(jù)塊,并將數(shù)據(jù)塊按照索引順序拼接起來(lái)返回給客戶端.

3.1 布隆過(guò)濾器

布隆過(guò)濾器本質(zhì)上為概率型數(shù)據(jù)結(jié)構(gòu),具有高速查詢與插入的特點(diǎn). 使用布隆過(guò)濾器的目的是快速過(guò)濾不存在的指紋,數(shù)據(jù)塊的指紋在使用Hash算法計(jì)算時(shí)會(huì)在布隆過(guò)濾器中留下一個(gè)標(biāo)記,如果一個(gè)指紋經(jīng)過(guò)hash算法計(jì)算后在布隆過(guò)濾器中沒(méi)有找到對(duì)應(yīng)的標(biāo)記,則說(shuō)明該指紋是一個(gè)新的指紋,對(duì)應(yīng)的數(shù)據(jù)塊也是一個(gè)新的數(shù)據(jù)塊,如果指紋經(jīng)過(guò)hash算法計(jì)算后在布隆過(guò)濾器中能找到對(duì)應(yīng)的標(biāo)記,則說(shuō)明該指紋可能已經(jīng)存在,需要經(jīng)過(guò)后面的指紋比對(duì)過(guò)程繼續(xù)確認(rèn).

在布隆過(guò)濾器中,存在假陽(yáng)性的情況,即待索引的指紋雖然不在集合中,但經(jīng)過(guò)k個(gè)Hash函數(shù)映射后布隆過(guò)濾器所對(duì)應(yīng)的位置可能為1,從而誤認(rèn)為該指紋已經(jīng)在集合里了. 布隆過(guò)濾器中把發(fā)生假陽(yáng)性的可能性稱為假陽(yáng)性概率(False positive probability),簡(jiǎn)稱為誤判率(Error rate). 誤判率由以下公式計(jì)算得出,即

fBF=(1-(1-1/m)kn)k≈(1-e-kn/m)k.

(5)

集合的指紋個(gè)數(shù)為n、位向量長(zhǎng)度為m和Hash函數(shù)的個(gè)數(shù)為k.

假設(shè)m和n已知,此時(shí)令q=k·ln(1-(1-1/m)kn),則fBF=eq,而且fBF和q極值點(diǎn)相同,再令p=(1-1/m)kn,則可推導(dǎo)出

(6)

在本系統(tǒng)中,采用分段型布隆過(guò)濾器(Segemented Bloom filter),分段型布隆過(guò)濾器的k個(gè)哈希函數(shù)分別映射到k個(gè)長(zhǎng)度為m/k的不相交的位段,將布隆過(guò)濾器的查詢復(fù)雜度達(dá)到O(1),假陽(yáng)性概率為

f′BF=(1-(1-k/m)n)k≈(1-e-kn/m)k.

(7)

盡管f′BF稍大于fBF,由于m與n較大,誤差可忽略不計(jì).

3.2 多級(jí)緩存模型

多級(jí)緩存模型由一級(jí)緩存與二級(jí)緩存組成. 一級(jí)緩存用于同步的更新命中的容器,布隆過(guò)濾器中能找到的指紋,需要在指紋比對(duì)的后續(xù)流程繼續(xù)確認(rèn)是否真的存在,如果在一級(jí)緩存和二級(jí)緩存中都沒(méi)有找到對(duì)應(yīng)的指紋記錄,并且在數(shù)據(jù)庫(kù)的指紋表中找到該指紋,那么通過(guò)數(shù)據(jù)庫(kù)中的記錄找到該指紋存放的容器,把容器中的所有指紋更新到一級(jí)緩存中. 二級(jí)緩存的作用是在一級(jí)緩存更新找到容器的同時(shí),找到該容器id臨近的下一個(gè)容器,找到把容器id對(duì)應(yīng)的容器,并把該容器內(nèi)指紋更新到二級(jí)緩存中. 布隆過(guò)濾器與多級(jí)緩存模型一同組成高效緩存模型,如圖3所示.

在高效緩存模型中,每個(gè)指紋對(duì)比流程為:約定指紋存在則標(biāo)記為1(對(duì)于標(biāo)記為1的說(shuō)明數(shù)據(jù)塊已經(jīng)在服務(wù)端有了,客戶端不需要再發(fā)送),不存在標(biāo)記為0. 首先去布隆過(guò)濾器里查找,若沒(méi)有此指紋則標(biāo)記為0,流程結(jié)束,若有此指紋(根據(jù)布隆過(guò)濾器特性上面已經(jīng)說(shuō)明,布隆過(guò)濾器中能查到的指紋不一定存在,需要走后面的流程繼續(xù)確認(rèn))則去一級(jí)緩存中查找,一級(jí)緩存中若有則標(biāo)記為1,流程結(jié)束,若沒(méi)有則進(jìn)一步去二級(jí)緩存中查找,二級(jí)緩存中若有則標(biāo)記為1,流程結(jié)束,二級(jí)緩存中若還沒(méi)有則去數(shù)據(jù)庫(kù)中查找,數(shù)據(jù)庫(kù)中若還沒(méi)有,則標(biāo)記為0,流程結(jié)束,若有則標(biāo)記為1,并把該指紋對(duì)應(yīng)的容器同步更新到一級(jí)緩存中,下一個(gè)容器異步的更新到二級(jí)緩存中.

3.3 容器

采用基于流的塊排列技術(shù)(Stream-Informed Segment Layout,SISL),SISL技術(shù)主要特點(diǎn)是面對(duì)同一個(gè)數(shù)據(jù)流,將新數(shù)據(jù)塊存放在一起,塊描述符也存放在一起,即數(shù)據(jù)塊在磁盤(pán)的物理空間上盡可能地連續(xù)存儲(chǔ),并且其對(duì)應(yīng)的指紋也連續(xù)存儲(chǔ). 本系統(tǒng)服務(wù)端通過(guò)設(shè)立容器實(shí)現(xiàn)SISL技術(shù). 服務(wù)端先把客戶端傳來(lái)的數(shù)據(jù)塊放到緩存隊(duì)列,然后順序放到容器中,這樣就能保證臨近數(shù)據(jù)存放的位置也是臨近的,以容器為單位的緩存能大大提高緩存的命中率,降低訪問(wèn)數(shù)據(jù)庫(kù)的次數(shù),這樣在指紋比對(duì)和恢復(fù)數(shù)據(jù)時(shí)都能有比較高的效率. 容器是一段數(shù)據(jù)組合的概念,其固定大小為4MB的一段數(shù)據(jù). 它的數(shù)據(jù)組織結(jié)構(gòu)是前24KB存放指紋及數(shù)據(jù)塊的起始位置和長(zhǎng)度信息,從4MB-24KB的位置開(kāi)始存放數(shù)據(jù)塊. 一個(gè)容器一般可以放800個(gè)左右的數(shù)據(jù)塊,由于數(shù)據(jù)塊的長(zhǎng)度不固定,因此這個(gè)數(shù)量也不固定.

當(dāng)服務(wù)端接收到數(shù)據(jù)塊與索引信息時(shí),將每塊數(shù)據(jù)存儲(chǔ)至容器的步驟如下:

(1)服務(wù)端將傳過(guò)來(lái)的新數(shù)據(jù)塊放到容器中,數(shù)據(jù)塊按照容器中存放數(shù)據(jù)塊的位置依次存放,數(shù)據(jù)塊的指紋按照容器中存放指紋的位置依次存放,并在數(shù)據(jù)庫(kù)中記錄該指紋對(duì)應(yīng)的容器id;

(2)容器寫(xiě)滿后把容器放到文件中,并在數(shù)據(jù)庫(kù)中記錄該容器對(duì)應(yīng)的文件id. 然后創(chuàng)建新的容器,過(guò)程為:清空當(dāng)前容器中的數(shù)據(jù)(當(dāng)前容器中的數(shù)據(jù)已經(jīng)保存在文件中了),容器id加1,并將容器的信息記錄到數(shù)據(jù)庫(kù)中.

(3)文件放在磁盤(pán)上并在數(shù)據(jù)庫(kù)中記錄文件對(duì)應(yīng)的磁盤(pán)位置. 這樣就可以根據(jù)數(shù)據(jù)庫(kù)中的指紋記錄一層層地找到對(duì)應(yīng)的數(shù)據(jù)塊.

系統(tǒng)中每個(gè)文件最大為1 GB,一個(gè)數(shù)據(jù)文件放滿了,才會(huì)生成一個(gè)新的文件存放容器,一個(gè)文件可以放256個(gè)容器. 文件放滿容器后會(huì)創(chuàng)建新的文件,并把文件的信息記錄到數(shù)據(jù)庫(kù)中.

4 數(shù)據(jù)備份與恢復(fù)流程

本數(shù)據(jù)備份與恢復(fù)系統(tǒng)克服現(xiàn)有技術(shù)中的不足,提供一種基于源端數(shù)據(jù)重刪的數(shù)據(jù)備份與恢復(fù)方法,解決了現(xiàn)有備份與恢復(fù)技術(shù)中數(shù)據(jù)的重刪效率低、計(jì)算指紋耗時(shí)長(zhǎng)、頻繁操作數(shù)據(jù)庫(kù)耗時(shí)的問(wèn)題. 下面分別介紹數(shù)據(jù)的備份流程與數(shù)據(jù)的恢復(fù)流程.

4.1 數(shù)據(jù)備份流程

數(shù)據(jù)備份流程如圖4所示.

(1)在客戶端,對(duì)數(shù)據(jù)流進(jìn)行分段得到多個(gè)數(shù)據(jù)段;

(2)并行處理多個(gè)數(shù)據(jù)段,對(duì)每個(gè)數(shù)據(jù)段進(jìn)行分塊,并計(jì)算每個(gè)數(shù)據(jù)塊的指紋;

(3)順序?qū)⒅讣y發(fā)送服務(wù)端進(jìn)行對(duì)比,并將對(duì)比結(jié)果返回至客戶端;

(4)客戶端根據(jù)對(duì)比結(jié)果,將沒(méi)有的數(shù)據(jù)塊發(fā)送至服務(wù)端進(jìn)行保存?zhèn)浞?服務(wù)端將數(shù)據(jù)塊存放狀態(tài)返回給客戶端.

4.2 數(shù)據(jù)恢復(fù)流程

數(shù)據(jù)恢復(fù)流程如圖5所示.

(1)客戶端從索引文件中讀取一段待恢復(fù)文件的索引,把索引信息發(fā)送到服務(wù)端.

(2)服務(wù)端根據(jù)索引信息找到數(shù)據(jù)塊返回客戶端,其具體步驟為:解析每個(gè)數(shù)據(jù)塊的索引信息,根據(jù)索引信息中的指紋先到一級(jí)讀緩存中查找,若找到則讀取數(shù)據(jù)塊,繼續(xù)找下一數(shù)據(jù)塊;若找不到則去二級(jí)讀緩存中查找,若二級(jí)讀緩存中能找到,讀取數(shù)據(jù)塊,繼續(xù)找下一數(shù)據(jù)塊,若找不到則去數(shù)據(jù)庫(kù)中找,在數(shù)據(jù)庫(kù)中根據(jù)指紋找到對(duì)應(yīng)的容器,根據(jù)容器id找到對(duì)應(yīng)的文件,從文件中讀出對(duì)應(yīng)的容器更新到一級(jí)讀緩存中,并把對(duì)應(yīng)容器的下個(gè)容器異步更新到二級(jí)讀緩存中;將讀到的每個(gè)數(shù)據(jù)塊按照索引順序拼接起來(lái)返回給客戶端.

(3)循環(huán)執(zhí)行以上兩步直到獲取文件所對(duì)應(yīng)的所有數(shù)據(jù)塊,恢復(fù)出完整的文件.

恢復(fù)過(guò)程中用到一級(jí)讀緩存和二級(jí)讀緩存和備份過(guò)程中用到一級(jí)緩存和二級(jí)緩存邏輯上類似,不同的地方在于在備份過(guò)程中用到的一級(jí)緩存和二級(jí)緩存只需要緩存指紋即可,而恢復(fù)過(guò)程中用到一級(jí)緩存和二級(jí)緩存除了緩存指紋還要緩存指紋對(duì)應(yīng)的數(shù)據(jù)塊. 恢復(fù)中用的緩存和備份中用的緩存是各自獨(dú)立的.

5 系統(tǒng)仿真實(shí)驗(yàn)

本系統(tǒng)為基于源端的數(shù)據(jù)重刪與備份系統(tǒng),系統(tǒng)采用C/S架構(gòu),基于Java語(yǔ)言. 在系統(tǒng)仿真實(shí)驗(yàn)中,建立測(cè)試服務(wù)器與測(cè)試機(jī)進(jìn)行多線程的備份與恢復(fù)測(cè)試,測(cè)試服務(wù)器配置如表1所示,測(cè)試機(jī)配置如表2所示.

表2 測(cè)試機(jī)的配置Table 2 Configuration of test machine

表1 測(cè)試服務(wù)器的配置Table 1 Configuration of test server

在Windows環(huán)境下,對(duì)同一個(gè)數(shù)據(jù)樣本進(jìn)行兩次文件備份測(cè)試,數(shù)據(jù)樣本由ghost的鏡像文件與windows的系統(tǒng)目錄文件組成,共13.2GB. 文件樣本分別基于本系統(tǒng)的數(shù)據(jù)備份恢復(fù)產(chǎn)品與傳統(tǒng)的數(shù)據(jù)備份恢復(fù)系統(tǒng)中測(cè)試,測(cè)試備份系統(tǒng)的數(shù)據(jù)備份速度與重刪率,其中重刪率為備份集實(shí)際大小與存儲(chǔ)大小之間差值占實(shí)際大小的百分比,即系統(tǒng)在進(jìn)行重刪時(shí)刪掉的重復(fù)數(shù)據(jù)所占百分比. 備份的實(shí)驗(yàn)結(jié)果如表3,4所示.

表4 現(xiàn)有的數(shù)據(jù)備份系統(tǒng)實(shí)驗(yàn)結(jié)果Table 4 Experimental result for the present date backup system

表3 本文數(shù)據(jù)備份系統(tǒng)實(shí)驗(yàn)結(jié)果Table 3 Experimental results for the proposed data backup system

表5 數(shù)據(jù)恢復(fù)結(jié)果
Table 5 Experimental results for data recovery

本文的數(shù)據(jù)備份恢復(fù)系統(tǒng)現(xiàn)有數(shù)據(jù)備份恢復(fù)系統(tǒng)恢復(fù)總時(shí)間3 min 45 s4 min 2 s備份集實(shí)際大小/GB13.213.2平均恢復(fù)速度/(Mb·s-1)60.0755.73

備份速度為源數(shù)據(jù)除以時(shí)間. 改進(jìn)后的備份系統(tǒng)與現(xiàn)有備份系統(tǒng)的備份速度對(duì)比如圖6所示.

由表中數(shù)據(jù)可以明顯發(fā)現(xiàn),與采用傳統(tǒng)源端數(shù)據(jù)重刪技術(shù)的現(xiàn)有產(chǎn)品相比,盡管雙方在重刪率上十分接近(這是由于在重刪中當(dāng)前主要采用CDC分塊技術(shù),故大家的重刪率才會(huì)十分接近),但在備份速度方面無(wú)論是初次備份還是第2次備份,基于本系統(tǒng)的數(shù)據(jù)備份恢復(fù)產(chǎn)品對(duì)比現(xiàn)有的數(shù)據(jù)備份恢復(fù)產(chǎn)品在速度上有明顯優(yōu)勢(shì). 在數(shù)據(jù)恢復(fù)方面,實(shí)驗(yàn)結(jié)果如表5所示.由表5可見(jiàn),該系統(tǒng)在進(jìn)行數(shù)據(jù)恢復(fù)時(shí)也能保持較高的恢復(fù)速度.

6 結(jié)論

針對(duì)傳統(tǒng)基于源端數(shù)據(jù)重刪的數(shù)據(jù)備份與恢復(fù)技術(shù)中,因?yàn)橹貏h導(dǎo)致耗時(shí)過(guò)長(zhǎng)、服務(wù)端存放數(shù)據(jù)頻繁操作數(shù)據(jù)庫(kù)耗時(shí)所產(chǎn)生的問(wèn)題,本文設(shè)計(jì)了一種改進(jìn)后基于數(shù)據(jù)重刪的數(shù)據(jù)備份與恢復(fù)的系統(tǒng),對(duì)于重刪耗時(shí)過(guò)長(zhǎng)的問(wèn)題,本文通過(guò)在客戶端對(duì)數(shù)據(jù)流分段并存放至預(yù)處理環(huán)形隊(duì)列,實(shí)現(xiàn)將重刪功能塊分布執(zhí)行、減少重刪的耗時(shí),在服務(wù)端針對(duì)存儲(chǔ)數(shù)據(jù)的耗時(shí)問(wèn)題,設(shè)立布隆過(guò)濾與多級(jí)緩存模型進(jìn)行指紋對(duì)比,減少訪問(wèn)數(shù)據(jù)庫(kù)頻率,并基于塊排列技術(shù),將數(shù)據(jù)與指紋存放在容器中,提高在對(duì)比指紋時(shí)指紋的命中率. 結(jié)果表明,相比于現(xiàn)有的基于源端數(shù)據(jù)重刪的數(shù)據(jù)備份與恢復(fù)系統(tǒng),本系統(tǒng)在數(shù)據(jù)備份與恢復(fù)方面具有良好的表現(xiàn).