樹形高效數據庫備份管理模型

周文瑾，胡曉勤，李自尊，鄧 亮

（四川大學 計算機學院，四川 成都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.］