树形高效数据库备份管理模型

周文瑾，胡晓勤，李自尊，邓 亮

（四川大学 计算机学院，四川 成都610065）

0 引 言

数据库备份是容灾备份系统中重要的组成部分。传统的备份点管理模型［1－4］以数据库最近备份点为核心，将备份点按照备份时间与策略关系组织为线性结构，采用单链条方式对其进行成组管理。但在实际应用中，多样化的备份策略使得备份点间将存在多种形式的关联，即多链条式的关联特点，从而导致传统的备份点管理模型具有下述的问题：单备份链管理，历史时间点需要手动管理与归档；灾难恢复后需要做一次全备份，初始化相应数据结构后，才能应用多样化备份策略，耗费时间且数据库风险期长；自动删除策略不够灵活、磁盘空间利用率较低。

针对传统数据库备份点管理模型的不足，本文提出了一种基于备份链的数据库备份管理模型 （backup－chainbased database backup management model，BCBM）。BCBM根据数据逻辑关系将备份点以备份链为单位进行管理，并将多条备份链组织为树形结构，从而将数据库的备份与恢复操作转化为等效的树形操作。与传统管理模型相比，本模型具有以下优点：具有多备份链管理能力；避免了数据库恢复后的全备份窗口规划过程；自动删除与合并策略的实现更加灵活，可有效提高系统的磁盘空间利用率。

1 相关知识

1.1 系统体系

一个典型的数据库备份系统如图1所示，主要是由业务数据服务器和数据备份中心组成［4－6］。其中，业务数据服务器与数据备份中心呈多对一关系。

图1 数据库系备份系统体系结构

业务数据服务器上部署了企业的业务数据库，其上将安装备份系统的备份代理，用以执行用户所设置的备份任务及恢复任务。数据备份中心则部署了数据库备份与恢复系统的管理服务端，用于管理与存储从业务数据服务器上备份而来的备份点数据及其备份点信息。备份点信息则主要包含数据库备份点的备份链信息，数据备份中心将根据该信息对备份点数据进行管理、指挥完成对数据库的灾难恢复，因此，备份链信息的管理方式及其组织灵活度将在很大程度上决定数据备份中心对于备份点数据的管理能力与效率。

1.2 相关概念

（1）数据库辨识信息iα：在数据库α系统表中生成的作为数据库唯一标志的数据，其取值为随机长整型数字、GUID或类似的随机字符串。

（2）备份点B：数据库备份文件，其格式为

式中：i——数据库辨识信息；t——备份时刻，为时间描述字符串；d——备份点自描述信息，如备份文件存储路径、备份文件大小及其校验值等与恢复相关的必要内容，取值为大段的带格式文本。

（4）备份链：一条备份链C为备份数据记录连续的n个备份点所构成的有序序列。由于连续增量备份会延长备份链，而完全备份与累积增量备份都会扩展出新的备份链，因此应用多样化备份策略所生成的备份链将呈现为森林结构。若每三天做一次完全备份F，每天半夜做一次1级累积增量备份D，每天正午与傍晚做一次连续增量备份L，则第4天正午时备份管理系统中将会生成如图2形式的具有4条备份链的森林结构 （方框中的备份点即构成了其中的一条备份链）。

2 备份管理模型

2.1 树形备份管理

2.1.1 SNT模型

图2 多备份链形成的森林结构

为适应树形备份管理功能的要求，本文设计了简化前序遍历树 （simplified nested tree，SNT）模型，用于在数据表中存储备份链信息。它基于前序遍历树模型精简与优化而来，仅保留其插入与删除节点的功能［7］。对森林G＝＜V，E＞而言，每一个树的节点可以用下述格式进行表达

式中：tid——树序号，用以对森林中不同的树进行区分，其取值为正整数；树中每一个节点记录一个左值lid和右值rid，左值为树节点前序遍历序号，为以1为起始值递增的正整数；右值为树节点范围序数，取值为：若节点为叶节点，则取值即等于左值；若节点不为叶节点，则取值为以该节点为根节点的子树中深度为1的节点中最大的右值。

树的增删即对树序号的增删；而树节点的增删则需要相应的插入与删除法则。

若待添加节点的父节点树序号为t、左值为n，则添加操作实现为：

（1）对所有v.tid＝t且v.lid＞n的节点v，更新其v.lid＝v.lid＋1；

（2）对所有v.tid＝t且v.rid≥n的节点，更新其v.rid＝v.rid＋1；

（3）加入节点v＝＜t，n＋1，n＋1＞。

删除操作只在左值连续且都位于同一棵树的节点上进行，且要求节点的度全为1。若树序号为t，待删除节点的左值范围为n到m （n≤m），则删除操作实现为：

（1）删除所有v.tid＝t、v.lid≥n 且v.lid≤m 的节点v；

（2）对所有v.tid＝t且v.lid＞n的节点v，更新其v.lid＝v.lid－m＋n－1；

（3）对所有v.tid＝t且v.rid＞n的节点v，更新其v.rid＝v.rid－m＋n－1。

2.1.2 备份管理数据结构

通过SNT模型对备份点相关数据进行存储，其数据表结构可用元组表述如下

式中：bkid——自增型无符号整型变量，用以唯一标志备份点；dbid——数据库辨识信息；bkinfo＿备份点自描述信息，以CLOB类型存放大对象文本数据；bktime——备份时刻，是定长字符串；tid，lid，rid——SNT模型中的树序号、左值与右值；flag用于自动删除策略的待删除标记，取值为正整数。

2.2 数据库备份

当出现系统崩溃或因灾难而出现设备毁损时，数据库的恢复将会进行数据库运行环境的重建工作，因此在恢复时数据库辨识信息与结构信息也会同时进行重建，这将导致系统无法将新数据库与原数据库建立逻辑关联。因此传统的备份点管理模型在灾难恢复完成后需要对该数据库做一次全备份才能应用多样化的备份策略进行备份。树形备份管理则通过使用SNT模型记录备份链信息的方式来解决上述问题。由于在树形结构中，仅在灾难恢复后才会出现一个备份点的数据库辨识信息与其父节点的数据库辨识信息不同的情况，因此可基于该情况按灾难恢复方式建立数据库间的逻辑关联，从而能正确处理数据库相关的差异、增量或日志备份点的恢复序列，消除数据库恢复后的一次全备份［8－10］。

若某备份点其数据库辨识信息为iμ，备份时刻为tn，备份点自描述信息为d，则它在通过向表Backup插入一行以注册备份点

并不妨设其bkid自增为k，然后分别在管理系统中的记录方式如下：

（1）完全备份点：

1）向表Forest插入行

其中t′＝ MAX（tid）＋1；

2）更新表Locate的定位信息：①若主键iμ存在，则更新该记录l属性值l.tid＝t＇，l.lid＝1；②若不存在，则插入新记录

（2）增量备份点：

1）以主键iμ查询表Locate？Forest，有唯一记录：

2）搜索表Forest中f.tid＝t＇、f.lid≤lx且f.rid≥rx的所有记录f，以f.lid升序排列，若备份点为差异或累积备份点，不妨设其累积增量等级为n，则取集合中第n个元素；若备份点为连续增量，则取集合中最后的元素，并设取出的元素为

3）按SNT模型的插入法则在表Forest中插入新的叶节点

4）以主键iμ查询表Locate，有唯一的记录l，更新其l.lid＝ln＋1。

2.3 数据库恢复

数据库的恢复分为两步：先是恢复序列的生成，后是数据库信息更新操作。

（1）恢复序列的生成：不妨设该恢复时间点t的备份点在表Forest中的定位信息如下

则搜索表Forest中所有f＇.tid＝t＇、f＇.lid≤ln且f＇.rid≥rn的节点f＇，并将结果集中所有元素按f＇.lid升序排列，即为数据库的恢复序列。

（2）数据库信息更新：若备份链中末元的bkid为kn，则灾难恢复后更新操作为：

1）搜索表Forest中所有f.bkid＝kn节点

2）生成一个新的辨识信息iω；

3）向表Locate中插入

2.4 自动删除策略

自动删除策略实现为树的剪枝与压缩，它们分别以树的宽度与高度作为限定条件来对备份点进行筛选。

（1）剪枝：以数据库α中某待删除备份链为例，若该备份链叶节点在表 Forest有vn＝ （t′，ln，kn，0），则其标记剪枝流程为：

1）搜索表Forest中所有f.tid＝t＇、f.lid＜ln且f.rid≥rn的节点f并按f.lid降序排列形成节点集合Vn；

2）记di为第i个元素在Vn中的以1为初始值的降序排列的正整数序号。依次检查在Vn中的每个元素vi，①若满足vi.lid＝ln－di且vi.rid＝rn，则更新其vi.flag＝1；②若不满足，则本次剪枝流程完成。

（2）压缩：压缩型删除策略需要用到数据库增量合并技术［11－12］。若以数据库α中某一条备份链为例，限制数据库某备份链长度为正整数p，且该备份链叶节点在表Forest有：

则其压缩流程为：

1）搜索表 Forest中所有f.tid＝tid、f.lid≤ln且f.rid≥rn的节点f，并按f.lid升序排列形成节点集合Vn，若Vn元素数量小于等于p，则本次压缩结束；

2）记li、ri为第i个元素的左、右值。从序号为1的元素开始依次检查在Vn中的每个元素vi，若vi.lid＝vi.rid或已经处理了p－i个节点，则本次压缩结束；

3）①若vi满足vi.lid＝li＋1－1且vi.rid＝ri＋1，则将vi备份文件合并入vi＋1备份文件，更新vi.flag＝2；②若不满足，则跳过该节点不做任何处理。

（3）保留最近点：该策略即结合前述的剪枝与压缩策略来实现。若策略设置为仅保留数据库α最近的x个备份点，其取值为正整数，则实现如下：

1）搜索表Backup中所有b.dbid＝iα的节点b，并将上述集合中元素以b.bktime降序排列，取前x个元素组成待标记叶节点集合Vb；

3）对Vb中第i个元素bi与Vw中第j个元素lfj而言，若bi.lid≤lfj.lid且bi.rid≥lfj.rid，则更新 mj＝mj－1；

4）对Vw中第i个元素lfi，若mi＝ci，则对lfi进行剪枝；若mi＜ci且mi＞0，则设置备份链长度限制值p＝ci－mi，对lfi进行压缩；若上述条件都不满足，则跳过lfi不做任何处理

再按SNT模型的删除法则删除表Forest中所有f.flag≠0的节点f，以及表 Backup中所有b.bkid＝f.bkid的记录b，删除该节点在文件系统中的备份点数据。

3 对比实验

3.1 实验环境

测试环境按图1的体系结构进行配置，各部分如表1所示：主机1配置为业务数据服务器，其上安装Microsoft SQL Server 2008R2数据库；主机2配置为数据备份中心，其上架设DFS文件服务器，用以存放主机1上的备份数据。主机间通过互联网进行连接。

表1 实验环境

3.2 实验方法

在主机1上分别部署BCBM系统、康孚Galaxy（CVG）后，先对数据库做一次完全备份，用该完全备份点恢复新数据库后对其进行差异备份 （等效为1级累积增量），同时记录备份与恢复的运行时间并记录主机2上磁盘空间占用变化，从而测试在消除了数据库恢复所需的一次全备份之后，备份系统的效率提升；

再在主机1上分别部署BCBM系统、赛门铁克Net－Backup（NBU）和康孚Galaxy（CVG）后，并设置本文管理系统与CVG保留最近六个备份点，然后对数据库做一次完全备份，修改部分数据后做一次差异备份 （等效为1级累积增量），之后每修改部分数据一次便执行一次增量备份（等效为连续增量），同时记录主机2上磁盘空间占用变化，从而将传统的链条式管理策略与本文的树形备份点管理策略进行对比，测试备份系统的效率提升。

3.3 实验结果

消除数据库恢复所需全备份后的效率对比结果如图3所示。

图3 消除数据库恢复所需全备份后的效率对比

不同管理策略下磁盘空间占用量对比结果如图4所示。

图4 不同管理策略下磁盘空间占用量对比

从图3中可以看出，BCBM系统由于减少了恢复后所需的一次全备份，因此在相当程度上节省了维持相同备份时间点所需的磁盘空间，使相同磁盘空间中能容纳下更多的备份时间点，从而提升了磁盘空间的利用率，这也同时大幅缩减了恢复后的系统的风险期，使恢复后的系统尽快纳入了备份管理系统的保护之中，降低了数据丢失的风险。

在图4中，NBU不支持增量合并，占用空间量持续加大；而CVG的合并全备份基于整条备份链［13］，在做第12次、第17次备份时，整条备份链上的时间点才脱离最近6个备份点的约束条件，才能对它们进行合并，因此CVG系统自动合并策略占用空间量的图线存在波形；而BCBM系统的合并策略通过剪枝与压缩进行实现，对于脱离最近6个备份点约束条件的备份点可以立即制定相应合并或删除的方法，因此整条占用空间量的图线到达最大值后就基本保持不变，表明树形备份点管理策略相对传统的链条式管理策略更好地控制了差异与增量备份点对磁盘空间的占用，从而在保留相同数量的备份时间点时降低了所需要的磁盘空间，提升了磁盘空间的利用率。

4 结束语

容灾备份系统在信息社会中，对于个人与企业用户的重要性越来越显著。本文提出了一种高效的数据库备份管理模型，将备份点以备份链为管理单位、通过SNT模型进行组织，实现了对备份点更为高效的管理。实验表明：采用本文方法，能够进行对多备份链的管理，消除了灾难恢复时要求的一次完全备份，自动删除策略也更加灵活，能更有效地利用备份系统中数据备份中心的资源，降低数据库备份系统的建设成本。

［1］WANG Changxu，XU Rongsheng.Analysis and research of data backup system in corporation ［J］.Computer Applications and Software，2008，25 （10）：121－123 （in Chinese）. ［王昌旭，许榕生.企业数据备份系统分析与研究 ［J］.计算机应用与软件，2008，25 （10）：121－123.］

［2］ZHANG Yan.Research and realization of disaster backup and recovery techniques for information systems ［D］.Chengdu：Sichuan University，2006 （in Chinese）. ［张艳.信息系统灾难备份和恢复技术的研究与实现 ［D］.成都：四川大学，2006.］

［3］YANG Yixian，YAO Wenbin，CHEN Zhao.Review of disaster backup and recovery technology of information system ［J］.Journal of Beijing university of posts and telecommunications，2010，33 （2）：1－6 （in Chinese）. ［杨义先，姚文斌，陈钊.信息系统灾备技术综论 ［J］.北京邮电大学学报，2010，33（2）：1－6.］

［4］LI Tao，LIU Xiaojie，ZENG Jinquan.The theory and application of information system disaster backup and recovery ［M］.Beijing：Posts ＆ Telecom Press，2007 （in Chinese）. ［李涛，刘晓洁，曾金全，等.信息系统容灾抗毁原理与应用 ［M］.北京：人民邮电出版社，2007.］

［5］LI Mian.Research of business continuity and disaster recovery technology ［D］.Shanghai：Shanghai Jiaotong University，2010（in Chinese）.［李勉.业务连续性与灾难备份技术的研究［D］.上海：上海交通大学，2010.］

［6］FANG Jianfeng.Research of the application and implementation of disaster backup technology ［D］.Shanghai：East China Normal University，2010 （in Chinese）. ［方剑峰.灾难备份技术的应用研究与实现 ［D］.上海：华东师范大学，2010.］

［7］Joe Celko.Joe Celko＇s trees and hierarchies in SQL for smarties［M］.2nd ed.USA：Morgan Kaufmann Publishers Inc.，2012.

［8］Jeffrey D Ullman，Hector Garcia－Monlina.Database systems：The complete book ［M］.2nd ed.USA：Prentice Hall，2008.

［9］Kalen Delaney，Paul S Randal，Kimberly L Tripp，et al.Microsoft SQL server 2008internals ［M］.USA：Microsoft Press，2009.

［10］Thomas Kyte.Expert oracle database architecture：Oracle database 9i，10g，and 11g programming techniques and solutions［M］.USA：Apress Inc，2010.

［11］ZHANG Hu，DONG Xiaoshe，WU Weiguo，et al.A data synchronization mechanism based on log－merging optimization［J］.Mini－micro Systems，2006，27 （12）：2183－2188 （in Chinese）.［张虎，董小杜，伍卫国，等.一种基于日志合并优化的数据同步机制 ［J］.小型微型计算机系统，2006，27（12）：2183－2188.］

［12］ZHANG Chunling，LV Zhenyu，LIU Zunfeng.Data synchronization solution based on virtual log compression ［J］.Computer Engineering，2010，36 （18）：67－69 （in Chinese）. ［张春玲，吕震宇，刘遵峰.基于虚拟日志压缩的数据同步方案［J］.计算机工程，2010，36 （18）：67－69.］

［13］CommVault.CommVault common technology engine （Version 7.0） ［M］.Beijing：CommVault，2007 （in Chinese）.［Comm－Vault，CommVault通用技术引擎快速指南 （Version 7.0）［M］.北京：CommVault，2007.］