一種改進的CDP快照方法

黎婷婷 李 赟

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

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

1 MS-CDP快照方法

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

1.1 用語說明

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

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

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

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

定義4. 元數據文件(metadata file).存儲的是元數據記錄，每條元數據記錄表示每一個變化數據塊的相關信息，其結構為

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

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

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

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

1.2 MS-CDP快照機制的原理及其實現

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

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

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

1.2.1插入元數據記錄算法

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

算法1. 插入元數據記錄.

1) 構造變化數據塊對應的元數據結構：

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

② 構造前項指針：

IFBLKn!=BLKsTHEN

front_pointer=location(BLKn-1)；

ELSE

front_pointer=-1；

END IF

③ 構造后項指針：

IFBLKn!=BLKsTHEN

back_pointer=location(BLKn+1)；

ELSE

back_pointer=-1；

END IF

其中location(BLKn)表示數據塊BLKn的當前最新修改數據的元數據記錄位置；

④ 將構造好的元數據記錄插入元數據文件；

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

3) 更新當前的極值點集合Exp：

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

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

IFBLKn-1inExpTHEN

Exp←Exp-{BLKn-1};

END IF

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

IFBLKn+1inExpTHEN

Exp←Exp-{BLKn+1};

END IF

1.2.2生成快照算法

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

算法2. 生成快照.

FOREACHExpDO

findBLKninmapping_fileTHEN

savelocation(BLKn) inSNAP;

END FOREACH

1.2.3恢復快照算法

算法3. 恢復快照.

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

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

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

WHILEfront_pointer(LOi) !=-1

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

TAB←front_pointer(LOi)；

LOi←front_pointer(LOi)；

END WHILE

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

WHILEback_pointer(LOi) !=-1

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

TAB←back_pointer(LOi)；

LOi←back_pointer(LOi)；

END WHILE

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

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

2 實 驗

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

2.1 實驗環境

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

表1 實驗環境

2.2 實驗數據

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

表2 備份數據

2.3 實驗結果

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

表3 快照存儲空間

2.4 結果分析

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

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

圖1 快照存儲空間對比

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

3 小 結

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

[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]蔡亮節. 面向低帶寬的遠程鏡像系統設計與實現[D]. 南京: 南京理工大學, 2014

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

[6]武媛媛. 基于塊級的連續數據保護系統的研究與實現[D]. 北京: 北京郵電大學, 2014

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

[8]王曉. 混合存儲系統高效快照技術研究[D]. 北京: 北京理工大學, 2015

黎婷婷

碩士研究生，主要研究方向為容災抗毀、網絡安全.

2294054102@qq.com

李赟

碩士研究生，主要研究方法為容災抗毀、網絡安全.

1127259111@qq.com