一種改進的CDP快照方法

黎婷婷 李 赟

(四川大學(xué)計算機學(xué)院 成都 610065) (2294054102@qq.com)

持續(xù)數(shù)據(jù)保護(continuous data protection, CDP)技術(shù)的出現(xiàn)改變了傳統(tǒng)數(shù)據(jù)保護技術(shù)只能周期性備份的缺點，可以達到恢復(fù)點目標(biāo)(recovery point object, RPO)等于零，保證數(shù)據(jù)零丟失.在實際的CDP系統(tǒng)中，恢復(fù)數(shù)據(jù)時需要遍歷元數(shù)據(jù)記錄，為了縮短遍歷時間，通常需要定期插入快照[1-2].在CDP系統(tǒng)中傳統(tǒng)的快照機制實現(xiàn)如下[3]：首先CDP存儲庫中保存了一份受保護卷的完全拷貝，稱為初始卷；每一次的變化數(shù)據(jù)塊都存儲在日志卷上，并打上時間戳生成一條元數(shù)據(jù)記錄存入元數(shù)據(jù)文件；同時系統(tǒng)中實時維護一張映射表，其中每一項是每個數(shù)據(jù)塊的最新變化數(shù)據(jù)塊在日志卷上的位置；在每次需要打快照時將該時刻的映射表保存下來即可[4].這種快照機制實現(xiàn)簡單，但是映射表所占存儲空間比較大.假設(shè)現(xiàn)在需要對1 TB的卷進行持續(xù)數(shù)據(jù)保護，數(shù)據(jù)塊大小為4 KB，則有256 MB個數(shù)據(jù)塊，即映射表有256 MB項，對于64 b的邏輯地址，映射表的大小為2 GB.針對這個問題，本文提出了一種改進的CDP快照方法，可以顯著地減少打快照時需要保存的數(shù)據(jù)量.

1 MS-CDP快照方法

在本文提出的CDP快照機制中，映射表中維護的是每個數(shù)據(jù)塊的最新變化數(shù)據(jù)塊對應(yīng)的元數(shù)據(jù)記錄的位置.為了在打快照時盡可能減少保存的數(shù)據(jù)量，可以想到的是只保留某些關(guān)鍵的元數(shù)據(jù)記錄[5-6].

1.1 用語說明

為了更好地闡述本文提出的MS-CDP快照方法，需要進行以下說明：

定義1. 數(shù)據(jù)塊(data block).對受保護卷按照固定大小進行分塊，以數(shù)據(jù)塊為單位來記錄數(shù)據(jù)變化.每個數(shù)據(jù)塊以塊號block_no來標(biāo)識，block_no=vol_offblock_size，其中vol_off為數(shù)據(jù)塊在受保護卷上的位置偏移，block_size為分塊的固定大小[7].

定義2. 初始卷(initial volume).是受保護卷最初始數(shù)據(jù)狀態(tài)的一份完全拷貝，存儲于CDP服務(wù)端，用于恢復(fù)時的基準(zhǔn)參考數(shù)據(jù)[8].

定義3. 日志卷(log volume).保存的是每一個變化數(shù)據(jù)塊.

定義4. 元數(shù)據(jù)文件(metadata file).存儲的是元數(shù)據(jù)記錄，每條元數(shù)據(jù)記錄表示每一個變化數(shù)據(jù)塊的相關(guān)信息，其結(jié)構(gòu)為

meta_record〈order_no,time_stamp,block_no,log_offset,front_pointer,back_pointer〉,

其中，order_no為順序索引號，time_stamp為時間戳，block_no為塊號，log_offset為變化數(shù)據(jù)塊在日志卷中的位置偏移，front_pointer為前項指針，back_pointer為后項指針.對于塊號為K的數(shù)據(jù)塊，前項指針指向塊號為K-1的數(shù)據(jù)塊最近一次修改的元數(shù)據(jù)記錄位置，后項指針指向塊號為K+1的數(shù)據(jù)塊最近一次修改的元數(shù)據(jù)記錄位置.

定義5. 映射表(mapping table).CDP系統(tǒng)中實時維護一張映射表，映射表中的每一項存儲的是每個數(shù)據(jù)塊最近一次修改的元數(shù)據(jù)記錄位置，初始時用一個特殊值-1來表示數(shù)據(jù)塊在初始卷上.

定義6. 極值點集合(extremum set).保存當(dāng)前時刻的關(guān)鍵數(shù)據(jù)塊的塊號，需要打快照時根據(jù)極值點集合中的塊號查找映射表對應(yīng)項并保存.

1.2 MS-CDP快照機制的原理及其實現(xiàn)

MS-CDP快照機制的實現(xiàn)依賴于數(shù)學(xué)函數(shù)的極值概念，如果函數(shù)在某點的值大于(小于)在該點附近任何其他點的函數(shù)值，則稱函數(shù)在該點的值為函數(shù)的“極大值(極小值)”，該點也稱為極值點.

在系統(tǒng)實時維護的映射表中，保存的是每個塊號的最新元數(shù)據(jù)記錄的位置，每個元數(shù)據(jù)記錄對應(yīng)元數(shù)據(jù)文件中的一個順序索引號，每一個順序索引號對應(yīng)著一個時間戳，那么如果將時間戳看作塊號的函數(shù)，則函數(shù)極大值點的意義在于：在這個塊號的某個鄰域內(nèi)，所有其他塊號的最后一次修改時間都比這個塊號的最后一次修改時間早.由于操作系統(tǒng)的一次寫操作可能會修改多個數(shù)據(jù)塊，所以可能存在多個變化數(shù)據(jù)塊的時間戳相同的情況，因此，給每一個變化數(shù)據(jù)塊的元數(shù)據(jù)記錄分配一個順序索引號order_no作為唯一索引，順序索引號從0開始計數(shù).這樣，將順序索引號看作塊號的函數(shù)，一定存在極值點.

根據(jù)上述的極值點的概念，系統(tǒng)需要實時維護一個極值點集合，因為順序索引號與元數(shù)據(jù)記錄一一對應(yīng)，因此極值點集合中保存的就是元數(shù)據(jù)記錄的位置.在需要打快照時，將當(dāng)前時刻的極值點集合保存下來即可.

1.2.1插入元數(shù)據(jù)記錄算法

CDP服務(wù)端接收到一個塊號為BLKn(假設(shè)數(shù)據(jù)塊塊號從BLKs開始，以BLKe結(jié)束)的變化數(shù)據(jù)塊時，先將數(shù)據(jù)塊存入日志卷中，然后構(gòu)建一條元數(shù)據(jù)記錄存入元數(shù)據(jù)文件，算法如下.

算法1. 插入元數(shù)據(jù)記錄.

1) 構(gòu)造變化數(shù)據(jù)塊對應(yīng)的元數(shù)據(jù)結(jié)構(gòu)：

① 依次寫入順序索引號、時間戳、塊號以及變化數(shù)據(jù)塊在日志卷中的偏移位置.

② 構(gòu)造前項指針：

IFBLKn!=BLKsTHEN

front_pointer=location(BLKn-1)；

ELSE

front_pointer=-1；

END IF

③ 構(gòu)造后項指針：

IFBLKn!=BLKsTHEN

back_pointer=location(BLKn+1)；

ELSE

back_pointer=-1；

END IF

其中l(wèi)ocation(BLKn)表示數(shù)據(jù)塊BLKn的當(dāng)前最新修改數(shù)據(jù)的元數(shù)據(jù)記錄位置；

④ 將構(gòu)造好的元數(shù)據(jù)記錄插入元數(shù)據(jù)文件；

2) 更新映射表：將插入的元數(shù)據(jù)記錄的位置信息更新到映射表BLKn的對應(yīng)表項中即可；

3) 更新當(dāng)前的極值點集合Exp：

① 將本次寫入的變化數(shù)據(jù)塊的塊號BLKn加入極值點集合Exp.

② 刪除前項中可能的極值點；

IFBLKn-1inExpTHEN

Exp←Exp-{BLKn-1};

END IF

③ 刪除后項中可能的極值點；

IFBLKn+1inExpTHEN

Exp←Exp-{BLKn+1};

END IF

1.2.2生成快照算法

當(dāng)需要對當(dāng)前時刻生成快照時，只需要根據(jù)極值點集合中的塊號，查找映射表中的對應(yīng)項并保存在一個快照文件SNAP中即可.

算法2. 生成快照.

FOREACHExpDO

findBLKninmapping_fileTHEN

savelocation(BLKn) inSNAP;

END FOREACH

1.2.3恢復(fù)快照算法

算法3. 恢復(fù)快照.

恢復(fù)時刻T的快照，即重建時刻T的映射表TAB.首先初始化一張映射表，表中的每一項初始化為-1，表示對應(yīng)數(shù)據(jù)塊在初始卷上，然后遍歷時刻T的快照文件SNAP，對文件中的每一個極值點LOi(LOi代表第i條元數(shù)據(jù)記錄)進行以下操作：

1) 將該極值點的值寫入映射表TAB的對應(yīng)表項.

2) 在元數(shù)據(jù)文件中進行前項遍歷，將經(jīng)過的每一條元數(shù)據(jù)記錄的位置寫入映射表的對應(yīng)表項：

WHILEfront_pointer(LOi) !=-1

&&time(LOi,front_pointer(LOi)) DO

TAB←front_pointer(LOi)；

LOi←front_pointer(LOi)；

END WHILE

3) 在元數(shù)據(jù)文件中進行后項遍歷，將經(jīng)過的每一條元數(shù)據(jù)記錄的位置寫入映射表的對應(yīng)表項：

WHILEback_pointer(LOi) !=-1

&&time(LOi,back_pointer(LOi)) DO

TAB←back_pointer(LOi)；

LOi←back_pointer(LOi)；

END WHILE

其中，time(a,b)表示第a條元數(shù)據(jù)記錄的時間晚于第b條元數(shù)據(jù)記錄的時間；在前(后)項遍歷中，如果當(dāng)前這條記錄的前(后)項指針為-1，或者本條記錄的時間早于前(后)項記錄的時間，則本次遍歷結(jié)束，否則將前(后)項記錄的位置寫入映射表TAB的對應(yīng)表項中；

4) 當(dāng)所有極值點的前項和后項遍歷結(jié)束后，映射表TAB即是需要的快照映射表，其中值為-1的表項表示該數(shù)據(jù)塊在初始卷上，從未修改過.

2 實 驗

本實驗采用對比方式，目的是比較MS-CDP方法與傳統(tǒng)快照方法在相同備份環(huán)境下所占用的存儲空間的大小.

2.1 實驗環(huán)境

測試環(huán)境由1臺CDP客戶機和1臺CDP服務(wù)器組成，可以實現(xiàn)基本的CDP備份和恢復(fù)功能，具體配置如表1所示：

表1 實驗環(huán)境

2.2 實驗數(shù)據(jù)

對CDP客戶機上的一塊32 GB硬盤進行數(shù)據(jù)備份，備份過程中隨機寫入變化數(shù)據(jù)，每隔1 h打一次快照，本文中設(shè)定的數(shù)據(jù)塊分塊大小為4 096 B，日志卷大小為100 GB，為映射表的每項分配4 B的存儲空間，具體數(shù)據(jù)如表2所示：

表2 備份數(shù)據(jù)

2.3 實驗結(jié)果

本文實驗分別使用MS-CDP方法和傳統(tǒng)快照方法每隔1 h打一次快照，并記錄2種方法占用的存儲空間，實驗數(shù)據(jù)記錄如表3所示：

表3 快照存儲空間

2.4 結(jié)果分析

本文實驗受保護卷的大小為32 GB，數(shù)據(jù)塊分塊大小為4 KB，所以映射表一共有8 MB項，日志卷大小為100 GB，則最多能存儲25 MB個數(shù)據(jù)塊，映射表的每一項為4 B用于保存元數(shù)據(jù)記錄的位置.

將表3的實驗結(jié)果繪制成折線圖，如圖1所示：

圖1 快照存儲空間對比

傳統(tǒng)快照方法由于要完全保存映射表，所以每個時刻的映射表大小是一致的，即需要保存32 MB(8 MB×4 B=32 MB)的數(shù)據(jù)量.而MS-CDP方法，只需要保留映射表中某些關(guān)鍵表項，所以保存的快照大小會根據(jù)實際寫入的數(shù)據(jù)量而改變.由圖1可知，當(dāng)寫入的變化數(shù)據(jù)較多時，MS-CDP方法需要保留的數(shù)據(jù)增多，假設(shè)在極端情況下，MS-CDP方法最多需要保存所有的映射表表項，退化為傳統(tǒng)的快照方法，當(dāng)然這種情況實際上是不可能發(fā)生的.由對比實驗和理論驗證可知，本文提出的MS-CDP快照方法需要存儲的快照數(shù)據(jù)量遠低于傳統(tǒng)快照方法，極端情況下最多退化成傳統(tǒng)快照方法，因此MS-CDP方法更優(yōu).

3 小 結(jié)

本文在研究現(xiàn)有CDP系統(tǒng)中的快照機制上，提出了一種改進的快照方法MS-CDP.通過理論分析和實驗驗證，本文提出的MS-CDP快照機制可以顯著減少保存的快照數(shù)據(jù)量，減輕了CDP系統(tǒng)服務(wù)端的存儲壓力.在恢復(fù)快照時，MS-CDP方法比傳統(tǒng)快照方法恢復(fù)映射表的時間更長.但是由于MS-CDP方法所占用的存儲空間明顯減少，因此可以更為頻繁地在系統(tǒng)中保存不同時刻的快照，總體上加快了CDP系統(tǒng)恢復(fù)操作的時間，而如何加快快照恢復(fù)速度正是本方法今后的研究重點.

[1]Yang J, Cao Q, Xie C S, et al. Snapshots in TRAP for continuous data protection[J]. IEEE Trans on Computers, 2012, 61(6): 753-766

[2]Hao W U, Liu X, Luo P. TRAP-4 based continuous data protection system[J]. Journal of Computer Applications, 2014, 34(1): 54-57

[3]Ju D P, Wang D S, He J Y, et al. TH-CDP: An efficient block level continuous data protection system[C]Proc of the Int Conf on Networking, Architecture, and Storage. Los Alamitos, CA: IEEE Computer Society, 2009: 395-404

[4]蔡亮節(jié). 面向低帶寬的遠程鏡像系統(tǒng)設(shè)計與實現(xiàn)[D]. 南京: 南京理工大學(xué), 2014

[5]李紅艷. 塊級連續(xù)數(shù)據(jù)保護系統(tǒng)元數(shù)據(jù)管理方法[J]. 計算機應(yīng)用, 2012, 32(8): 2141-2145, 2149

[6]武媛媛. 基于塊級的連續(xù)數(shù)據(jù)保護系統(tǒng)的研究與實現(xiàn)[D]. 北京: 北京郵電大學(xué), 2014

[7]張也, 劉曉潔, 鄧健. 一種遠程備份數(shù)據(jù)虛擬重構(gòu)方法[J]. 四川大學(xué)學(xué)報: 自然科學(xué)版, 2015, 52(5): 1014-1020

[8]王曉. 混合存儲系統(tǒng)高效快照技術(shù)研究[D]. 北京: 北京理工大學(xué), 2015

黎婷婷

碩士研究生，主要研究方向為容災(zāi)抗毀、網(wǎng)絡(luò)安全.

2294054102@qq.com

李赟

碩士研究生，主要研究方法為容災(zāi)抗毀、網(wǎng)絡(luò)安全.

1127259111@qq.com