王樹鵬，吳廣君，吳志剛，云曉春

(1.中國科學(xué)院 計算技術(shù)研究所，北京 100190；2. 災(zāi)備技術(shù)國家工程實驗室，北京 100876；3. 北京郵電大學(xué) 網(wǎng)絡(luò)技術(shù)研究院，北京 100876)

1 引言

各種災(zāi)難事件、突發(fā)事件通常會引起數(shù)據(jù)的丟失或者不可訪問，為企業(yè)、部門甚至個人都會帶來巨大的經(jīng)濟損失[1,2]。國標GB/T 20988-2007《信息安全技術(shù) 信息系統(tǒng)災(zāi)難恢復(fù)規(guī)范》中將災(zāi)難定義為：由于人為或自然等原因，造成信息系統(tǒng)運行嚴重故障或癱瘓，使信息系統(tǒng)支持的業(yè)務(wù)功能停頓或服務(wù)水平不可接受。根據(jù)上述標準，典型的災(zāi)難事件包括自然災(zāi)害，如火災(zāi)、洪水、地震、颶風(fēng)等；人為錯誤，如管理員誤操作、病毒攻擊等。數(shù)據(jù)的備份和恢復(fù)技術(shù)便成為數(shù)據(jù)安保，恢復(fù)癱瘓系統(tǒng)的最后一道防線。

多版本塊數(shù)據(jù)備份技術(shù)通常在邏輯卷層次或磁盤驅(qū)動器層次實現(xiàn)與應(yīng)用無關(guān)的數(shù)據(jù)復(fù)制，支持任意歷史版本的數(shù)據(jù)恢復(fù)。常見的備份技術(shù)如圖 1所示，隨著數(shù)據(jù)復(fù)制時間粒度的提高，數(shù)據(jù)保護性能會越好。目前通常使用在線數(shù)據(jù)復(fù)制技術(shù)支持細粒度多版本數(shù)據(jù)的備份與恢復(fù)。在線數(shù)據(jù)復(fù)制技術(shù)主要包括以COW（copy-on-write）技術(shù)為代表的寫時舊版本數(shù)據(jù)復(fù)制技術(shù)和 ROW (redirect-on-write)技術(shù)為代表的寫時新版本數(shù)據(jù)復(fù)制技術(shù)。COW 技術(shù)在發(fā)生寫操作時首先復(fù)制出舊版本數(shù)據(jù)，按序存儲各個歷史版本序列。在數(shù)據(jù)恢復(fù)時從當前時間點開始依次恢復(fù)之前版本的備份數(shù)據(jù)，實現(xiàn)歷史狀態(tài)的回滾。這類技術(shù)廣泛存在于多版本文件系統(tǒng)中，如Elephant[3], Ext3cow[4]，CVFS[5]等。但是COW技術(shù)具有如下2個缺點。1) COW具有明顯的寫延遲。COW 技術(shù)需要把原始系統(tǒng)中的一次寫操作變?yōu)樽x舊數(shù)據(jù)，存儲舊數(shù)據(jù)，最后執(zhí)行寫入的3次操作。盡管舊版本數(shù)據(jù)的轉(zhuǎn)存，新版本數(shù)據(jù)的寫入可以并發(fā)執(zhí)行[6]，但是仍然具有明顯的延遲。2) COW無法實現(xiàn)系統(tǒng)級別的全量恢復(fù)，僅能恢復(fù)由于誤操作導(dǎo)致的局部數(shù)據(jù)污染[7]。ROW技術(shù)直接復(fù)制寫數(shù)據(jù)流或數(shù)據(jù)塊，寫入到新分配的存儲空間。ROW技術(shù)可以應(yīng)用在數(shù)據(jù)復(fù)制頻率較高的場合，如CDP（continuous data protection）等。結(jié)合快照備份數(shù)據(jù)，ROW技術(shù)可以實現(xiàn)系統(tǒng)級別的全量恢復(fù)，但是隨著數(shù)據(jù)復(fù)制頻率的增加和數(shù)據(jù)保存時間的延長，備份數(shù)據(jù)版本數(shù)目會不斷增長，形成版本之間相互依賴的版本鏈條，使得數(shù)據(jù)管理越來越復(fù)雜，直接影響著數(shù)據(jù)的可恢復(fù)性和恢復(fù)效率。

圖1 數(shù)據(jù)保護技術(shù)的分類

文獻[8～10]中通過專用系統(tǒng)或硬件實現(xiàn)增量備份數(shù)據(jù)版本序列的管理，但是無法管理分離存儲的備份數(shù)據(jù)。為了提高備份數(shù)據(jù)管理效率，降低數(shù)據(jù)備份恢復(fù)成本，目前迫切需要建立獨立于主端系統(tǒng)的第三方備份數(shù)據(jù)管理中心[11]。TRAP[12,13]把實時復(fù)制的更新數(shù)據(jù)塊單獨保存在 CDP數(shù)據(jù)盤中，實現(xiàn)持續(xù)數(shù)據(jù)保護。但是TRAP在檢索目標版本數(shù)據(jù)時通過按序掃描版本序列，檢索時間隨著版本序列長度線性增長。文獻[14]和文獻[15]在定長的版本序列中插入全量鏡像數(shù)據(jù)或快照數(shù)據(jù)，加速版本鏈的檢索過程。但是頻繁的產(chǎn)生系統(tǒng)級別的鏡像數(shù)據(jù)或全量快照數(shù)據(jù)不僅增加主端系統(tǒng)的備份負擔，而且產(chǎn)生的周期備份數(shù)據(jù)與已經(jīng)存儲的版本序列存在版本冗余現(xiàn)象：即內(nèi)容相同的數(shù)據(jù)塊保存在多個版本中。如何利用存儲端存儲的備份數(shù)據(jù)版本序列構(gòu)建出任意歷史時間點的全量快照備份數(shù)據(jù)，是提高細粒度多版本條件下備份系統(tǒng)效率的主要途徑。

本文基于上述背景，提出塊備份數(shù)據(jù)多版本融合方法，通過版本序列的融合構(gòu)建出任意歷史時間點的全量快照備份數(shù)據(jù)，避免主端系統(tǒng)頻繁產(chǎn)生快照備份數(shù)據(jù)而降低系統(tǒng)性能。在具體實現(xiàn)中，本文結(jié)合塊備份數(shù)據(jù)的分布特點，以版本序列中邏輯地址連續(xù)的數(shù)據(jù)塊，作為版本融合單位，降低了版本融合帶來的計算負擔；最后文章給出了版本融合技術(shù)在多版本備份數(shù)據(jù)管理中的應(yīng)用案例和性能分析。

2 塊備份數(shù)據(jù)版本融合原理

多版本塊備份數(shù)據(jù)是通過加載在主端的備份代理結(jié)合在線數(shù)據(jù)復(fù)制技術(shù)而產(chǎn)生的。塊數(shù)據(jù)復(fù)制技術(shù)本質(zhì)是復(fù)制一定時間保護粒度(T)，邏輯地址空間(x)內(nèi)的變化的數(shù)據(jù)，可使用寫密度函數(shù) wT(x)抽象表達二者關(guān)系，如式(1)所示。由寫密度函數(shù)產(chǎn)生的數(shù)據(jù)量(d)可以表示為式(2)，其中，Length是每個邏輯地址單元對應(yīng)的數(shù)據(jù)塊長度。式(3)和式(4)進一步給出在整個邏輯地址空間和備份數(shù)據(jù)生命周期內(nèi)產(chǎn)生的備份數(shù)據(jù)總量，公式具體含義在文獻[16]中有詳細分析。

其中，[0, N]表示一個邏輯卷的地址空間；[0, H]表示備份數(shù)據(jù)的生命周期，超過生命周期的備份數(shù)據(jù)直接刪除或做進一步的歸檔處理。

通過式(4)和式(5)可以得出，在備份數(shù)據(jù)生命周期內(nèi)，備份數(shù)據(jù)量的版本序列長度(M)隨著數(shù)據(jù)復(fù)制時間粒度的減小(T)而增加。

為了進一步描述多版本序列與主端系統(tǒng)之間的對應(yīng)關(guān)系，引入 Markov轉(zhuǎn)換過程表示。如圖 2所示，給出了在一定數(shù)據(jù)復(fù)制頻率下主端的數(shù)據(jù)狀態(tài)和備份數(shù)據(jù)版本序列之間的狀態(tài)轉(zhuǎn)換關(guān)系。其中，D表示主端的數(shù)據(jù)狀態(tài)，Δ表示增量備份數(shù)據(jù)。不同版本的數(shù)據(jù)狀態(tài)使用版本號i進行區(qū)分，Di表示版本號為i數(shù)據(jù)狀態(tài)。版本序列和數(shù)據(jù)狀態(tài)之間通過版本號進行關(guān)聯(lián)，如由數(shù)據(jù)狀態(tài)Di產(chǎn)生更新數(shù)據(jù)Δi,i+1后變化到數(shù)據(jù)狀態(tài)Di+1。

圖2 基于Markov過程的數(shù)據(jù)狀態(tài)轉(zhuǎn)換過程

利用Markov過程中的狀態(tài)轉(zhuǎn)換可以表示多版本條件下，數(shù)據(jù)恢復(fù)過程中目標版本的檢索過程，比如要恢復(fù)早期數(shù)據(jù)狀態(tài)，需要利用某一個版本的數(shù)據(jù)狀態(tài)點作為起點，結(jié)合增量備份數(shù)據(jù)版本序列轉(zhuǎn)換到目標版本數(shù)據(jù)狀態(tài)。傳統(tǒng)方法是通過數(shù)據(jù)備份產(chǎn)生數(shù)據(jù)狀態(tài)點，并結(jié)合增量備份數(shù)據(jù)版本序列實現(xiàn)數(shù)據(jù)狀態(tài)轉(zhuǎn)換；一種更優(yōu)化的方法是通過把多個增量版本序列融合，利用產(chǎn)生的融合版本加快狀態(tài)之間轉(zhuǎn)換。如圖D1到D4的狀態(tài)轉(zhuǎn)換可以通過Δ1,2+Δ2,3+Δ3,4版本之間的融合，實現(xiàn)數(shù)據(jù)狀態(tài)之間的轉(zhuǎn)換。塊備份數(shù)據(jù)版本融合過程可以形式化定義為

定義1 版本融合。設(shè) 2個相鄰版本的塊備份數(shù)據(jù) Δi={(x, d)|x∈Ni, d∈D}；Δi+1={(x', d')|x'∈Ni+1, d'∈D'}；其中，N表示塊數(shù)據(jù)的邏輯地址空間，D, D'表示邏輯地址空間內(nèi)的數(shù)據(jù)，把Δi與Δi+1合并成一個新融合版本Δ′，構(gòu)成Δ′的數(shù)據(jù)塊集合可以表示為式(6)，這一過程稱為版本融合。

版本融合的基本思想是根據(jù)塊備份數(shù)據(jù)邏輯地址的相對關(guān)系，通過塊數(shù)據(jù)的替換產(chǎn)生新版本的備份數(shù)據(jù)。版本融合可以在相鄰的多個版本構(gòu)成的版本序列依次使用，于是得出如下引理。

引理 1 多版本塊備份數(shù)據(jù)構(gòu)成的版本序列中，可以把版本相鄰的序列，融合成一個版本，這一過程可以通過式(7)表示。

根據(jù)版本融合定義，容易證明上述定理，具體的證明過程不再詳述。利用定理1可以把一個增量備份數(shù)據(jù)版本序列融合為一個版本，進而縮短版本鏈的長度，加快版本鏈的檢索過程。

3 塊備份數(shù)據(jù)版本融合算法

文獻[17]中分析了磁盤數(shù)據(jù)局部訪問特性，由此產(chǎn)生的備份數(shù)據(jù)版本序列是由一系列邏輯地址相對連續(xù)的數(shù)據(jù)塊集合構(gòu)成，本文根據(jù)數(shù)據(jù)塊分布的特征提出一種變長數(shù)據(jù)塊版本融合方法。在變長數(shù)據(jù)塊版本融合操作中，需要根據(jù) 2個版本數(shù)據(jù)塊的相對關(guān)系進行匹配。設(shè)新版本中，數(shù)據(jù)塊r的一個連續(xù)邏輯地址空間為[a, b], a≤b；舊版本中，數(shù)據(jù)塊R的一個連續(xù)邏輯地址空間為[A, B],A≤B；則數(shù)據(jù)塊r與R的匹配關(guān)系可以描述成如下6種情況。

定義 2 左獨立。if(b＜A)，則新版本數(shù)據(jù)塊 r相對于舊版本R左獨立，如圖3中的①，簡稱左獨立，記為Left-Independent。

圖3 r和R的6種區(qū)間匹配關(guān)系

定義 3 左重疊。if(a＜A and b≥A and b≤B)，則稱新版本數(shù)據(jù)塊 r相對于舊版本數(shù)據(jù)塊 R左重疊，如圖 3中的②，簡稱左重疊，記為 Left-Overlapping；

定義 4 包含。if(a＞A and b＜B)，則稱新版本數(shù)據(jù)塊r包含于舊版本數(shù)據(jù)塊R中，如圖3中的③，簡稱包含，記為Included；

定義 5 右重疊。if(a≥A and a≤B and b＞B)，則稱新版本數(shù)據(jù)塊 r相對于舊版本數(shù)據(jù)塊 R右重疊，如圖 3中的④，簡稱右重疊，記為Right-Overlapping；

定義 6 右獨立。if(a＞B)，則稱新版本數(shù)據(jù)塊r相對于舊版本數(shù)據(jù)塊R右獨立，如圖3中的⑤，簡稱右獨立，記為Right-Independent；

定義 7 覆蓋。if(a≤A and b≥B)，則稱新版本數(shù)據(jù)塊r相對于舊版本數(shù)據(jù)塊R滿足覆蓋關(guān)系，如圖3中的⑥，簡稱覆蓋,記為Overlapping。

在系統(tǒng)軟件和磁盤調(diào)度算法中通常使用起始地址加數(shù)據(jù)長度記錄RAW Data的分布，但是所記錄的數(shù)據(jù)塊之間都滿足獨立的關(guān)系，如圖3中的①和⑤所示，r全部在R的左側(cè)或右側(cè)。在版本融合過程中 2個數(shù)據(jù)塊會發(fā)生重疊情況，如Left-Overlapping、Included以及 Right-Overlapping等情況，需要進行預(yù)處理，把舊版本數(shù)據(jù)塊進行分割，分割后的子區(qū)間滿足獨立或覆蓋的關(guān)系。數(shù)據(jù)塊區(qū)間分割方法包括如下2種方法。

定義 8 區(qū)間疊加。在滿足Overlapping關(guān)系條件下，即r覆蓋R時，R中任意一點在r中都有與之對應(yīng)的部分，使用r替代R的過程稱為區(qū)間疊加，記為：r+R；

定義 9 區(qū)間分割。在區(qū)間關(guān)系左重疊，包含以及右重疊等條件下，把R進行分割，產(chǎn)生的區(qū)間子項 Ra、Rb、Rc，其中，r與 Ra具有 Right-Independent的區(qū)間關(guān)系；r與 Rb具有 Overlapping關(guān)系，r與Rc具有Left-Independent的區(qū)間關(guān)系，把這一過程稱為區(qū)間分割，記為：R/r。

結(jié)合上述基本定義和描述，可以給出變長數(shù)據(jù)塊版本融合基本算法描述。設(shè)每個版本內(nèi)的數(shù)據(jù)塊集合記為F。多次復(fù)制過程中產(chǎn)生的版本序列記為：{F1, F2, …, Fn}，版本融合算法如下所示。

算法1 版本融合算法：VersionMerge (Fr, FR)

輸入：Fr, FR

輸出：Ft

Fr表示新版本數(shù)據(jù)塊集合；FR表示舊版本數(shù)據(jù)塊集合；Ft表示融合后的數(shù)據(jù)塊集合；假設(shè)FR, Fr集合內(nèi)的所有數(shù)據(jù)塊都是按照邏輯地址遞增的順序排列；

VersionMerge (Fr, FR){

1) i=1, k=1；//i為Fr內(nèi)的數(shù)據(jù)塊的標示；k為FR內(nèi)的數(shù)據(jù)塊標示；

2) for(each ri∈Fr, Rk∈FR){

3) if(Frand FR都沒有結(jié)束){

4) switch(compare(ri, Rk)；) {

5) case Left-Independent:

6) add rito Ft；i++；break；

7) case Left-Overlapping or Included or Right-Overlapping：

8) Rk/ ri→Ra,Rb,Rc；

9) if(Ra≠NULL) add Rato Ft；

10) if(Rb≠NULL) {

11) ri/Rb→ra, rb, rc；

12) if(ra≠NULL) add rato Ft；

13) if(rb≠NULL) add rbto Ft；

14) if(rc≠NULL) rc→ri；}

15) if(Rc≠NULL) Rc→Rk；

16) break；

17) case Right-Independent：

18) add Rkto Ft；

19) k++；break；

20) case Overlapping:

21) k++；break；}}}

22) if (Fr尚未處理結(jié)束) 把Fr沒有處理的部分直接加入到Ft中；

23) if (FR尚未處理結(jié)束) 把FR沒有處理的部分直接加入到Ft中；

24) return Ft；}

算法1給出2個版本融合的具體實現(xiàn)過程，在變長數(shù)據(jù)塊分割算法中, 具有重疊關(guān)系的數(shù)據(jù)塊可能會被頻繁分割處理，這部分數(shù)據(jù)塊的長度在融合版本中會逐漸趨近于磁盤寫操作的最小分配單元，如sector長度。版本融合過程使用算符“⊕”表示，也稱為版本的疊加，算法1可以表示為Ft=Fr⊕ FR。

4 版本融合在多版本備份數(shù)據(jù)管理中的應(yīng)用

4.1 基于版本融合的快照檢索方法

快照備份數(shù)據(jù)描述一個時間點的瞬時數(shù)據(jù)鏡像，對保證數(shù)據(jù)的可恢復(fù)性，加快多版本檢索過程具有重要意義。結(jié)合算法 1，在備份數(shù)據(jù)版本序列中，從目標版本開始, 逆序融合每個版本, 直到最近的全量備份數(shù)據(jù)為止, 這一過程可以使用算法 2表示，記為SnapshotSearch (i, S)。

算法 2在版本序列中循環(huán)利用版本融合算法,獲取時間點為 i的全量快照備份數(shù)據(jù), 可以使用式(8)表達這一檢索過程。

算法2 快照融合算法： SnapshotSearch(i, S)

i：待檢快照版本號；S: 版本序列；Fi：第i個版本；FVFullSnapshot: 結(jié)果快照數(shù)據(jù)塊集合；

輸入：i, S(1≤i≤n)

輸出：FVFullSnapshot

版本序列的融合操作可以在備份系統(tǒng)空閑時發(fā)起，并保存融合后的結(jié)果版本加速后期的版本檢索過程。基于版本融合，可以進一步實現(xiàn)多版本序列的刪除操作。對于超過備份數(shù)據(jù)生命周期的版本序列可以利用版本融合技術(shù)，融合成一個新版本的備份數(shù)據(jù)，起到版本序列刪除的作用。

4.2 多版本差異恢復(fù)模式

備份數(shù)據(jù)主要用于數(shù)據(jù)恢復(fù)。根據(jù)第2部分的分析，以ROW技術(shù)為代表的分離存儲系統(tǒng)中，數(shù)據(jù)恢復(fù)過程通常選擇距離目標時間點最近的全量數(shù)據(jù)作為數(shù)據(jù)的一致性狀態(tài)，然后再結(jié)合更新數(shù)據(jù)版本序列，逐次前向恢復(fù)到目標時間點。在分離存儲的備份系統(tǒng)中，需要恢復(fù)的數(shù)據(jù)量是影響恢復(fù)效率的主要因素。利用版本融合技術(shù)，結(jié)合算法2可以直接計算出版本序列中目標時間點的全量快照數(shù)據(jù)，結(jié)合校驗技術(shù)可以快速判斷當前的主端系統(tǒng)的數(shù)據(jù)狀態(tài)與歷史數(shù)據(jù)狀態(tài)實際發(fā)生變化的數(shù)據(jù)，通過僅恢復(fù)變化數(shù)據(jù)提高恢復(fù)效率。這一數(shù)據(jù)恢復(fù)過程稱為多版本差異恢復(fù)，記為 Diffdo，利用算法3表示。

算法3 多版本差異恢復(fù)過程：Diffdo(T)

T：待恢復(fù)的版本號，1Tn≤≤；

1) 存儲端根據(jù)算法2，計算版本號為T的全量快照數(shù)據(jù)FVFullSnapshot(T)：

FVFullSnapshot(T)=FT⊕FT-1⊕…⊕F1

2) 存儲端根據(jù) FVFullSnapshot(T)計算快照數(shù)據(jù)的校驗文件：CheckFile(T)，并發(fā)送到主端；CheckFile(T)包括校驗規(guī)則和校驗值：

Check(FVFullSnapshot(T)) →CheckFile(T)

3) 主端根據(jù)CheckFile(T)計算本地磁盤當前數(shù)據(jù)塊的校驗值，并與 CheckFile(T)中對應(yīng)的校驗值比對，記錄校驗不一致的數(shù)據(jù)塊對應(yīng)的邏輯地址，生成CheckErrorFile(T)，并發(fā)送到存儲端：

CheckFile(T)→CheckErrorFile(T)

4) 存儲端根據(jù)CheckErrorFile(T)和FVFullSnapshot(T)檢索備份數(shù)據(jù)，計算差異恢復(fù)索引文件DiffdoLog(T)，并根據(jù)DiffdoLog(T)進行差異數(shù)據(jù)恢復(fù)：

CheckErrorFile(T)+FVFullSnapshot(T)→DiffdoLog(T)

Diffdo利用版本融合技術(shù)，構(gòu)建版本序列中目標時間點的全量快照數(shù)據(jù)，可以直接與主端系統(tǒng)當前數(shù)據(jù)狀態(tài)進行比對，只恢復(fù)實際發(fā)生變化的數(shù)據(jù)塊，通過減少恢復(fù)數(shù)據(jù)量提高恢復(fù)效率。

5 實驗與結(jié)果分析

本文采用標準 trace和具體備份系統(tǒng)相結(jié)合的方法展開實驗分析。首先利用HP cello99 trace分析在持續(xù)數(shù)據(jù)保護背景下使用版本融合技術(shù)和定期產(chǎn)生快照備份數(shù)據(jù) 2種技術(shù)產(chǎn)生的備份數(shù)據(jù)量比較。然后結(jié)合具體系統(tǒng)，給出版本融合技術(shù)在多版本備份數(shù)據(jù)管理中的效率分析。

5.1 版本融合后產(chǎn)生的數(shù)據(jù)量分析

Cello99 trace是HP實驗室記錄UNIX服務(wù)器全年的磁盤I/O trace。實驗中選取cello99-03-03的I/O trace進行分析。本文回放連續(xù)24h的磁盤I/O操作，分析2種技術(shù)產(chǎn)生的備份數(shù)據(jù)量關(guān)系。圖4中給出了實驗結(jié)果。實驗中選取每次寫操作作為一個版本，快照周期選取版本序列長度為：40、80、120、160、200產(chǎn)生快照備份數(shù)據(jù)。實驗結(jié)束時，使用版本融合技術(shù)比周期快照技術(shù)少產(chǎn)生備份數(shù)據(jù)量43.4%左右。實驗中進一步發(fā)現(xiàn)隨著快照周期內(nèi)版本序列長度的增加產(chǎn)生的快照備份數(shù)據(jù)量會有所減少，這一現(xiàn)象主要是由于磁盤具有寫局部性造成的，一個快照周期內(nèi)邏輯地址相同的數(shù)據(jù)塊會發(fā)生重復(fù)寫操作，如果能夠統(tǒng)計重復(fù)寫的比率，進而控制融合版本序列的長度，會進一步提高版本融合的效率。

圖4 版本融合技術(shù)產(chǎn)生的備份數(shù)據(jù)量比較

5.2 變長數(shù)據(jù)塊索引技術(shù)效率分析

本文進一步通過實際的數(shù)據(jù)備份恢復(fù)系統(tǒng)分析版本融合具體的性能。備份系統(tǒng)中主端選取 XP操作系統(tǒng)的PC機，具體配置為Intel(R) Core(TM)2 CPU 1.8GHz/1.79GHz, 1GB內(nèi)存，NTFS文件系統(tǒng),目標邏輯卷為20GB。存儲端由4臺存儲服務(wù)器構(gòu)成的存儲集群，具體配置為Inter(R) Core(TM)2 Duo CPU2.2GHz/2.19GHz，1GB 內(nèi)存；Realtek 100M(2)；Inter(R) Core(TM)2 Duo CPU 2.2GHz/2.19GHz，2GB內(nèi)存，Realtek 100M(2)。實驗中利用磁盤過濾驅(qū)動技術(shù)，監(jiān)控主端目標邏輯卷，產(chǎn)生周期性的增量備份數(shù)據(jù)。備份周期為10～30min，共產(chǎn)生50個版本的備份數(shù)據(jù)。

圖5給出了定長數(shù)據(jù)塊與變長數(shù)據(jù)塊在多版本數(shù)據(jù)管理中的索引量比較。索引數(shù)據(jù)量直接與數(shù)據(jù)塊的分割方式有關(guān)，版本融合技術(shù)中以邏輯地址連續(xù)的數(shù)據(jù)塊作為多版本管理單位，可以比靜態(tài)數(shù)據(jù)塊多版本管理方法減少 2～3個數(shù)量級的索引數(shù)據(jù)量，為降低版本融合計算復(fù)雜度提供基礎(chǔ)。圖6給出了利用變長數(shù)據(jù)塊融合方法檢索全量快照備份數(shù)據(jù)的時間消耗。變長數(shù)據(jù)塊版本融合的時間消耗明顯低于定長數(shù)據(jù)塊多版本管理方法。

圖5 索引數(shù)據(jù)量的比較

圖6 全量快照檢索時間比較(圖中使用雙y軸，靜態(tài)分割4kB的索引技術(shù)使用左側(cè)的y軸，另外3種技術(shù)使用右側(cè)的y軸)

5.3 數(shù)據(jù)恢復(fù)效率分析

備份數(shù)據(jù)恢復(fù)效率通常使用RTO(recovery time objective)表示[18]。在分離存儲模式下，數(shù)據(jù)恢復(fù)時間消耗主要包括從發(fā)生數(shù)據(jù)丟失一直到業(yè)務(wù)重新啟動的時間間隔，可以表示為

T檢測：表示從災(zāi)難發(fā)生到檢測到數(shù)據(jù)丟失的時間；

T檢索：表示在存儲端按照一定的恢復(fù)模式, 檢索待恢復(fù)備份數(shù)據(jù)的時間；

T傳輸：表示備份數(shù)據(jù)由存儲端傳輸?shù)街鞫说臄?shù)據(jù)傳輸時間；

T重啟：表示數(shù)據(jù)成功恢復(fù)后, 重新啟動業(yè)務(wù)的時間；

T檢測、T重啟與具體的業(yè)務(wù)相關(guān)，在本文中忽略不計，于是RTO可以表示為

T檢索與存儲端的備份數(shù)據(jù)組織方式有關(guān)，T傳輸與待恢復(fù)的備份數(shù)據(jù)量和傳輸帶寬相關(guān)，在傳輸帶寬一定的條件下，T傳輸由恢復(fù)數(shù)據(jù)量決定。為了進一步描述T檢索和T傳輸?shù)南鄬﹃P(guān)系，引入檢索時間占有率因子α,如式(11)所示：

α表示在存儲端檢索備份數(shù)據(jù)的時間占全部數(shù)據(jù)恢復(fù)時間的比率；α主要由備份數(shù)據(jù)的索引結(jié)構(gòu)和版本序列的組織方式?jīng)Q定。α值越大表示存儲端的計算開銷越大。

本文主要比較Redo，Diffdo的恢復(fù)效率，同時也測試了 COW 數(shù)據(jù)復(fù)制下通常使用的回滾恢復(fù)（Undo）效率，3種恢復(fù)方式的具體含義如下：

Undo：是指通過回滾方式, 陸續(xù)恢復(fù)前一個版本數(shù)據(jù)實現(xiàn)數(shù)據(jù)恢復(fù)；

Redo：是指首先恢復(fù)到距離目標時間點最近的全量數(shù)據(jù)，通過恢復(fù)全鏡像數(shù)據(jù)和更新數(shù)據(jù)版本序列實現(xiàn)數(shù)據(jù)恢復(fù)；

Diffdo：是指本文提出的基于多版本管理技術(shù)的差異恢復(fù)模式。

圖7給出了不同恢復(fù)模式下恢復(fù)效率的比較。不同恢復(fù)模式下，需要恢復(fù)的數(shù)據(jù)量以及備份數(shù)據(jù)的檢索方式不同，導(dǎo)致α有很大的差別。實驗中首先選取傳輸帶寬為2MB/s，在Redo恢復(fù)模式下，由于恢復(fù)的數(shù)據(jù)量大，RTO值最大。Undo恢復(fù)模式由于只恢復(fù)變化的數(shù)據(jù)，恢復(fù)的數(shù)據(jù)量少，RTO值最小。Diffdo恢復(fù)的數(shù)據(jù)量與Undo相同，但是由于引入了數(shù)據(jù)校驗過程，RTO值介于二者之間。在實驗環(huán)境下，Diffdo模式的RTO值是Redo恢復(fù)模式的1/4到1/5左右。圖8中進一步給出不同恢復(fù)模式下檢索時間的占有率情況分析。Redo模式下，數(shù)據(jù)傳輸時間占RTO的主要部分，α值很小，占1%左右；但是在Undo和Diffdo恢復(fù)模式下需要檢索全量快照α值較大。由于Diffdo增加了數(shù)據(jù)的校驗過程，α值最大。根據(jù)實驗結(jié)果可以得出，Diffdo可實現(xiàn)基于時間點的完整數(shù)據(jù)恢復(fù)，是一種適用于低帶寬，大數(shù)據(jù)量的數(shù)據(jù)恢復(fù)場合。

6 結(jié)束語

在增量備份數(shù)據(jù)版本序列中利用版本融合技術(shù)可以計算出目標版本全量快照數(shù)據(jù)，避免通過備份產(chǎn)生全量快照數(shù)據(jù)。為了降低版本融合的計算負擔，本文以邏輯地址連續(xù)的數(shù)據(jù)塊作為版本融合單位，可加快版本的融合過程。利用版本融合技術(shù)可以實現(xiàn)多種有現(xiàn)實意義的具體應(yīng)用，如快照檢索，多版本差異恢復(fù)等操作。但是版本融合技術(shù)是建立在所有版本數(shù)據(jù)的正確性得到保證的條件下實現(xiàn)的，否則任意一個版本數(shù)據(jù)出現(xiàn)錯誤都會擴散到融合版本中，為此確保備份數(shù)據(jù)的可靠性，成為進一步研究的主要方向。

[1] MCKNIGHT J, ASARO T, BABINEAU B. Digital Archiving:End-user Survey and Market Forecast 2006–2010[R]. The Enterprise Strategy Group, 2006.

[2] KEETON K, SANTOS C, BEYER D. Designing for disasters[A].Proceedings of 3rd Conference on File and Storage Technologies[C].USENIX Association, 2004. 59-72.

[3] SANTRY D S, FREELY M J, HUCHINSON N C, et al. Deciding when to forget in the elephant file system[J]. Operating Systems Review, 1999, 33(5): 110-123.

[4] PETERSON Z, BURNS R C. Ext3cow: a time-shifting file system for regulatory compliance[J]. ACM Transactions on Storage, 2005, 1(2):190-212.

[5] SOULES C A, GOODSON G R, STRUNK J D, et al. Metadata efficiency in versioning file systems[A]. Proceedings of the 2nd Usenix Conference on File and Storage Technologies (Fast'03)[C]. Usenix Association, 2003. 43-58.

[6] LIU J N, YANG T M, LI Z H. TSPSCDP: a time-stamp continuous data protection approach based on pipeline strategy[A]. Japan-China Joint Workshop on Frontier of Computer Science and Technology(FCST '08)[C]. 2008. 96-102.

[7] XIAO W J, YANG Q. Can we really recover data if storage subsystem fails?[A]. Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS 2008)[C]. Beijing: China,2008.597-604.

[8] HITZ D, LAU D, MALCOLM M. File system design for an NFS file server appliance[A]. Proceedings of the USENIX Winter Technical Conference[C]. USENIX Association, 1994. 235-245.

[9] PATTERSON H, MANLEY S, FEDERWISCH M. SnapMirror (R):file system based asynchronous mirroring for disaster recovery[A].Proceedings of the Conference on File and Storage Technologies(Fast'02)[C]. Usenix Association , 2002. 117-129.

[10] FLOURIS M D, BILAS A. Clotho: transparent data versioning at the block I/O level[A]. Proceedings of the 21st IEEE Conference on Mass Storage Systems and Technologies/12th NASA Goddard Conference on Mass Storage Systems and Technologies (MSST’04)[C]. IEEE Computer Society, 2004.315-328

[11] 楊朝紅, 宮云戰(zhàn), 桑偉前等. 基于主從異步復(fù)制技術(shù)的容災(zāi)實時系統(tǒng)研究與實現(xiàn)[J]. 計算機研究與發(fā)展, 2003, 40(7): 1104-1109.YANG Z H, GONG Y Z, SANG W Q, et al. A primary-backup lazy replication system for disaster tolerance[J]. Journal of Computer Research and Development, 2003, 40(7): 1104-1109.

[12] YANG Q, XIAO W J, REN J. TRAP-array: a disk array architecture providing timely recovery to any point-in-time[A]. Proceedings of the 33rd Annual International Symposium on Computer Architecture(ISCA’06:)[C]. 2006. 289-300.

[13] XIAO W J, REN J, YANG Q. A case for continuous data protection at block level in disk array storages[J]. IEEE Transactions on Parallel and Distributed Systems, 2009, 20(6): 898-911.

[14] AGUILERA M K, KIMBERLY K, MERCHANT A, et al. Improving recoverability in multi-tier storage systems[A]. Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks(DSN '07)[C]. 2007. 677-686.

[15] 李旭, 謝長生, 楊靖. 一種改進的塊級連續(xù)數(shù)據(jù)保護機制[J]. 計算機研究與發(fā)展, 2009, 46(5): 762-769.LI X, XIE C S, YANG J, et al. An improved block-level continuous data protection mechanism[J]. Journal of Computer Research and Development, 2009,46(5): 762-769.

[16] 吳廣君, 云曉春, 方濱興. HCSIM: 一種長期高頻Block-Level快照索引技術(shù)[J]. 計算機學(xué)報, 2009, 32(10): 2080-2090.WU G J, YUN X C, FANG B X, et al. HCSIM: an indexing method for long-lived frequent block-level snapshot[J]. Chinese Journal of Computers, 2009, 32(10): 2080-2090.

[17] RUEMMLER C, WILKES J. Unix disk access patterns[A]. Proceedings of the Winter 1993 Usenix Conference[C]. USENIX Association,1993. 405-420.

[18] KEETON K, SANTOS C, BEYER D, et al. Designing for disasters[A].Proceedings of the 3rd USENIX Conference on File and Storage Technologies[C]. USENIX Association, 2004.59-72.