一种改进的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