（计算机软件与理论专业论文）基于有向图的通用恢复模型的设计与应用.pdf

魑十甫向刚的通用恢复模型的设计畸成j i 中山人学顾| 。学位论文2 0 0 6 5 基于有向图的通用恢复模型的设计与应用 计算机软件与理论 硕士生：王增智 指导教师：倪德明副教授 摘要 恢复模块在备份系统中占有举足轻重的地位。恢复模块的设计既要求考虑 到通用性，又要求能够适应千差万别的流程。所以在设计企业级的备份软件时， 恢复代理程序的开发工作量非常巨大，繁琐且容易出错。本文针对备份恢复领 域的这一问题，建立了一个基于有向图的通用恢复模型，从而大大提高了恢复 模块设计的通用性，并极大的减轻了恢复代理程序开发的工作量。 首先，本文以实际的备份系统n e tb u n k e r 为基础，对现有的工作加以总结， 并在分析了o r a c l e ，s q ls e r v e r ，l i n u x 文件系统等恢复过程之后，归纳出其 在数学上的性质，对恢复过程的诸多常见的概念，术语给出了形式化定义，从 而为恢复流程建立了一个基于有向图的通用理论模型，进而在此模型上讨论了 恢复的状态迁移方程。 随后在两个方面对该模型进行了扩展：l ，通过引入故障树的方法，并在分 析了恢复流程故障诊断与传统故障诊断的差异之后，总结出恢复流程的故障诊 断就是一个基于有向图和故障树进行回溯的过程；2 基于有向图模型建立了一 个有穷自动状态机，为自动恢复与模型的实现提供了理论基础。 最后以备份恢复代理接口的设计等实际问题为例，阐述了一个建立在 a c e ( a d a p t i v ec o m m u n i c a t i o ne n v i r o n m e n t ) 基础上的有限状态机的代码框架， 从而实现了有向图模型和故障诊断。此外，在此框架的基础上，给出了通用恢 复代理的详细设计，包括了代理的组成，运行环境，：i 二作机制等，并将其应用 到了n e t b u n k e r 系统中，使得先前阐述的问题在一定程度上得到了解决。 关键词：有向图，恢复，有穷状态机，备份代理，通用模型 基十囱向幽的通用恢复模型的世h - i i 应用 中山人学坝i 。学位论义2 0 0 65 d e s i g na n da p p l i c a t i o no f t h eg e n e r a lr e c o v e r y m o d e lb a s e do nt h ed i r e c t e d g r a p h c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：z e n g z h iw a n g s u p e r v i s o r ：a s s o c i a t ep r o f d e m i n gn a b s t r a c t t h er e c o v e r ym o d e lh o l d sas i g n i f i c a n ta n di n f l u e n t i a lp l a c ei nt h eb a c k u p s y s t e m ，a n dt h ed e s i g no far e c o v e r yw s t e md e m a n d sb o t hac o n s i d e r a t i o na b o u ti t s u n i v e r s a l i t ya n di t sa d a p t a t i o nt ov a r i o u sf l o w s t h e r e f o r e w h i l ed e s i g n i n gab a c k u p s o f t w a r ef o ra ne n t e r p r i s e ，i ti se a s yt om a k em i s t a k e sb e c a u s eo fi t st e d i o u sa n d m a s s i v ea m o u n t so fw o r ki nd e v e l o p i n gt h er e c o v e r i n ga g e n tp r o c e d u r e f o c u s i n go n t h ep r o b l e m si nt h ef i e l do fb a c k u pr e c o v e r y , t h i st h e s i sc o n s t r u c t sag e n e r a lr e c o v e r y m o d e lb a s e do nt h ed i r e c t e d g r a p h ，t h u se n h a n c i n gg e n e r a l i t yo ft h er e c o v e r y m o d e l sd e s i g nt oal a r g ee x t e n t ，a n dr e d u c i n gg r e a t l yt h ew o r k l o a di nd e v e l o p i n gt h e r e c o v e r y a g e n tp r o c e d u r ea sw e l l b a s e do nt h ea c t u a lb a c k u ps y s t e mo fn e tb u n k e r , t h i st h e s i sf i r s ts u m su pt h e c u r r e n tw o r k i n gs i t u a t i o na n di n d u c e st h em a t h e m a t i c a lq u a l i t yo fs u c hr e c o v e r i n g s y s t e m sa so r a c l e ，s o ls e r v e r , a n dl i n u xs y s t e ma f t e rh a v i n ga n a l y z e dt h e i r r e s t o r i n gp r o c e s s e s w h a t sm o r e ，as e r i e so ff o r m a l i z e dd e f i n i t i o n sh a v eb e e ng i v e n t om a n yc o m m o nc o n c e p t sa n dt e r m si nt h ef i e l d so ft h er e c o v e r i n gp r o c e s s a n di n s od o i n g ，ag e n e r a lt h e o r ym o d e lb a s e do nad i r e c t e d g r a p hi se s t a b l i s h e df o rt h e r e s t o r i n gw o r kf l o w , a n dad i s c u s s i o no v e rt h es t a t e t r a n s f e r r i n ge q u a t i o no ft h e r e c o v e r i n gp r o c e s si sh e l do nt h en e w l ye s t a b l i s h e dm o d e l f u r t h e r m o r e ，t h i sm o d e li se x p a n d e di nt w oa s p e c t s ：o nt h eo n eh a n d ，t h m u 曲 t h ei n t r o d u c t i o no ft h et h e o r yo ft h ef a u l tt r e e ，t h i st h e s i sa n a l y z e st h ed i f f e r e n c e b e t w e e nt h ef a u l t d i a g n o s i si nt h er e c o v e r i n gf l o wa n dt h a t i nt h et r a d i t i o n a lf l o w ， t h u sc o n c l u d i n gt h a tt h ef a u l t d i a g n o s i si nt h er e c o v e r i n gf l o wi sj u s tat r a c i n g - b a c k p r o c e s so ft h ed i r e c t e d g r a p ha n dt h ef a u l tt r e e ；o nt h eo t h e rh a n d ，af i n i t e 1 1 摧于有向幽的通用恢复模型的设计! ，鹰册中f j 人学硕学位论文 2 0 0 6 - - 5 s e l f - r e s t o r i n g s t a t em a c h i n ei sc o n s t r u c t e do nt h ed i r e c t e d g r a p hm o d e l ，t h u s p r o v i d i n gt h et h e o r e t i c a lb a s i sf o rt h er e a l i z a t i o no ft h ea u t o r e c o v e r ym o d e l f i n a l l y , t a k i n gs o m ep r a c t i c a lp r o b l e m ss u c ha st h ed e s i g no ft h eb a c k u pw h i c h i su s e dt or e s t o r et h ea g e n t si n t e r f a c ea si n s t a n c e s ，t h i st h e s i se l a b o r a t e sac o d e f l a m ef o r t h ef i n i t es t a t em a c h i n eo nt h eb a s i so ft h ea c e ( a d a p t i v e c o m m u n i c a t i o ne n v i r o n m e n t ) ，t h u sr e a l i z i n gt h ed i r e c t e d g r a p hm o d e la n dt h e f a u l t d i a g n o s i s a d d i t i o n a l l y ，b a s e do nt h ee s t a b l i s h e df r a m e ，t h i st h e s i sa l s os h o w sa d e t a i l e dd e s i g nf o rt h eg e n e r a lr e c o v e r i n ga g e n t ，i n c l u d i n gt h ec o m p o n e n to ft h e a g e n t ，i t so p e r a t i n ge n v i r o n m e n ta n di t sw o r k i n gm e c h a n i s m w h a ti sm o r e ，t h i s t h e s i si l l u s t r a t e st h ea p p l i c a t i o no ft h em o d e li nt h en e tb u n k e rs y s t e m ，t h u ss o l v i n g t h ep r o b l e m sm e n t i o n e da b o v et os o m ee x t e n t k e y w o r d s ：d ir e t t e dg r a p h ，r e c o v e r y ，f i n i l es t a t em a c h i n e ，b a c k u pa g e n t g e h e r a lm o d e l 1 1 数据备份概述 第1 章引言 1 1 1 数据备份的定义 数据备份技术是伴随着计算机的发展而发展起来的，可以l 龅计算机的发展史 就是一部数据备份的发展史。从字面上理解，数据备份就是对数据进行的复制。 但是，就数据备份作为信息安全领域的一个重要分支来讲，具有更加丰富的内涵， 复杂性远远不至如此。目前，对数据备份来说虽已有很长的一段发展过程，但在 国际上对数据备份仍然没有个统一的定义。例如，互联网上英文计算机词典里 给出的定义为：一个文件或文件系统或者是其它资源的一个多余的复制以防止原 先的出错或丢失：备份通常用来指对计算机磁盘上的所有文件的周期性所做的一 份复制并把它存放到磁带上或其它可移动的介质上 0 1 1 。l y o n s 羊l l a l a n 在1 9 9 6 年给出的定义为：数据备份就是仅仅对数据所作的后备存储，以便公司员工能够 去曾经备份过的灾难发生地点还原文件和应用软件，能够如什么也没发生过一样 地继续商业活动【0 2 】。o r a c l e 公司在数据库文档中给出的定义为：备份就是 数据的份复制，这份复制可以包括数据库的多个重要部分譬如控制文件和数据 文件等，备份是防止未预料到的数据丢失和应用性错误的安全措施，如果丢失了 原来的数据，那么可以通过备份来重新构建 0 3 】。数据备份专家w c u r t i sp r e s t o n 在其专著u n i x 备份与恢复 0 4 】中提出：备份= 拷贝+ 管理。 经过对数据备份系统的一段时间的开发研究，我们在综合了研究中遇到的各 类问题和解决方式的基础上提出备份的定义为【0 5 ： 备份= 拷贝+ 转换+ 传输+ 存储+ 管理 换句话说，备份就是对各种需要备份的资源使用对应的方式进行拷贝，然后根据 需要对原始数据进行一系列的压缩、加密等数据转换，通过不同层次的网络传输 协议和通道技术传输到介质，最后以适当的存储结构存储在选定的介质上，并且 整个过程以及相关的资源都处于一个备份中心的管理调度之下。 1 - 1 2 数据备份的意义 在当今社会环境中，信息技术扮演着越来越重要的角色，计算机更广泛地被 应用于开发、分析和存储公司的数据，这样，可以随时随地快速制定计划，进行 决策。在现代，数据已成为财富，这是大家的共识。如果公司的数据被破坏并且 没有备份，将会造成巨大的损失，若重新创建这些数据，须花大量的时问和成 本。据美国国家计算机安全卧会的统计，重新创建2 0 m 数据所需的时间和成本， 市场部门和工程部门分别是1 9 个工作日、1 7 0 0 0 美元和4 2 个工作日、9 80 0 0 美 元 0 6 。 在维护公司业务运作的信息安全体系中，核心的部分是数据，它是信息系统 中最重要的资产，系统安全的最终目的就是要保护数据。数据各份在保障公司信 息安全中起着重要作用。通过数据备份将重要的历史数据、日常数据备份到多种 介质上，以便在系统遭遇到像人为误操作、硬件损毁、电脑病毒、断电或是地震 火灾等事件时，能快速、有效地恢复系统数据，保证系统正常运行。从更广义的 角度上讲，数据各份为业务提供了持续增长的保障。因此，为了妥善管理和保护 公司运营的任何数据，对信息数据进行备份是十分必要的。 1 1 3 数据备份的发展历程 数据备份技术是伴随着计算机技术的发展而发展的，备份的含义也随着其技 术的丰富而丰富。所以要准确地体会备份的含义需要先了解备份技术的发展历 史，我们可以将数据备份技术的发展简要地概括为以下阶段： 备份的初始阶段：计算机网络尚未出现，可选的存储数据的介质种类非常有 限。备份的方式通常就是将要备份的文件复制到硬盘的另一个位置或者软盘上， 数据得不到有效的保护。 备份的中期发展阶段：局域网已经出现，备份面向的数据扩大到网络中整个 企业的数据。介质以磁带为主，但依然足系统管理员的手工作业，通常是通过备 份工具或是备份命令脚本进行人机交互执行，效率不高。还没有出现商业化的备 份软件，学术领域开始出现对备份系统的研究。 进一步地，随着计算机网络的发展和普及，又出现了基于i n i e r n e t i n t r a n e t 的 应用网络环境下的备份，这一阶段网络应用复杂化，计算模式由c s 至b s 到 p e e r - t o p e e r 复杂多变。 相比以前的单机备份，网络备份呈现出以下特点： f 1 )数据量剧增，备份工作量增大。在网络环境下，由于存在多种应用， 大量数据需要备份，比如用l o t u sn o t e s 数据库组建的办公自动化系统每年 就会产生g b 数量级的数据 0 7 1 。 ( 2 )数据种类增加，异种数据库、多种文件系统和操作平台分布在不同 的服务器和应用软件上，数据备份往往要通过网络跨平台完成。 ( 3 ) 存储介质的管理更加困难。随着计算机技术的发展，用来存储数据 的介质种类越来越多。在一定的应用需要的情况下，各种不同系统使用不同 的介质，如：软盘、光盘、磁带、磁盘等，介质的多样性会给管理带来很大 的麻烦。如果介质中没有电子标签，一旦外部标签脱落，想要知道介质上数 据内容就会很困难 o s l 。 目前，网络备份已经成为了现代备份系统研究的主流，它的发展进一步丰富 了数据备份的内涵。 1 2 备份系统领域研究成果概览 1 2 1 研究领域的备份系统 在当前的备份研究领域中，以研究文件系统备份者居多，研究数据库备份的 相对较少。而前者中又多数是研究u n i x 平台下的文件系统备份。下面对这些系 统加以简单介绍： o n i t r e e 0 9 是一个u n i x 环境下的分等级的大容量存储管理系统，它最初是 由l a w r e n c el i v e r m o r e 国家实验室开发的。该系统支持文件在不同的存储层次中 的自动移植和连续备份方式，并且提供包括事务日志在内的数据库的恢复。a f s 1 0 1 1 】的核心思想是将文件组织为卷，当然也包括了文件的备份和恢复数据。 一个卷就是一系列文件和目录的集合，一个卷完全驻留于一个磁盘的分区上，但 是个磁盘分区可能包含多个卷。备份时首先生成一个称为备份卷的克隆卷，它 包含了原来的卷中的文件的连接，然后使用完全或增量备份策略将该卷转储到磁 带上。完成之后，可以删除备份卷或者将它保留起来以便支持列前一个数据版本 的在线只读访问，可视为一个数据的快照。加n a m d a 网络备份管理器【1 2 】，由马罩 兰大学的p a r k 学院开发，它使用标准u n i x 备份程序比如d u m p 和t a r 等，来简 化网络上多u n i x 工作站的并行备份。为了得到最佳的备份性能，a m a n d a 将多 个备份集并行地写到一个临时的磁盘里，之后再以最大速度把数据以数据流的方 式写到磁带上。p s t o r e 1 3 是一个基于p e e r _ t o p e e r 网络的可靠的支持增量备份方 式的分布式备份系统。它使用大块的复制技术，各种加密技术和一个经过改编的 翻译算法来达到它的三大设计目的：可靠、安全和资源有效性。e l i e z e r l e v y 和 a b r a h a ms i l b e r s c h a t z 研究主存数据库的恢复方案 1 4 1 。他们提出了一个日志驱动 的备份系统，并设计了一个辅助处理器来专门读取日志记录。该处理器还要负责 将日志中记录下来的更新运用到磁盘数据库上，这样就可以在不用再访问主存数 据库的情况下完成恢复任务。 1 2 2 商业领域的备份系统 在国际上，目前有成熟的企业级备份软件，有相当多大规模的独立软件供应 商，而且从事备份软件研发的公司和机构组织也有很多。目前备份软件市场主要 被c a 、v e r i t a s 、l e g a t o 三大公司所占领，另外还有i b m 、h p 、c o m p a r e 这些硬件厂商也推出了自己的备份软件。其中c a 、v e r i t a s 、l e g a t o 和i b m 四 家公司的备份系统在目前来说占有了辛日当大钓市场份额。现对它们逐一做个简单 介绍：( 1 ) c a 公司的产品主要有两个系列：a r c s e r v e l t 系列和b r i 曲t s t o r e 系列。 这两个系列提供高性能、易于管理性和卓越的可靠性。 r 2 ) v e r i t a sn e t b a c k u p 软件是一个功能强大的企业级数据备份管理软件，它为w i n d o w sn t 、u n i x 和 n e t w a r e 环境提供了完整的数据保护机制，具有保护企业中从工作组到企业级服 务器的所有数据的能力。o ) l e g a t o 研制开发的n e t w o r k e r 数据存储管理系统提 供了c s 体系结构下的网络数据存储管理解决方案。( 4 ) i b m 的t i v o l i 管理环境是 个用于网络计算管理的集成的产品家族。它可以将数据的备份和归档拷贝存放 在离线的存储介质上，从而保护组织的数据免受硬件故障和其它错误操作的破 坏。 而在国内，相比之下还没有哪家公司推出了自主开发的具有一定的市场占有 率的备份软件，除了一些自由软件之外，大部分企业都选择前述的三大公司的备 份软件产品。国内在该领域的软件大部分都是一些小公司制作的备份系统，优势 和强度以及技术含量并不明显。 第2 章研究现状及存在的问题 2 1 国外研究现状 目前对备份技术的研究大致可以归为以下三类： 一类是研究在线( o n 1 i n e ) l , ! 备份技术的如，文献【1 5 提出了在u n i x 系统下研 究高速在线备份的方法。这一类的研究无论在商业领域还是研究领域都是目前研 究的热点。 另一类是研究备份策略( b a c k u ps t r a t e g y ) 酐l o l l ，h k a w a i 和h s a n d o h 提出 了根据两个条件来制定备份时间的策略 1 6 1 。这一类的研究相对独立。 还有一类是研究备份所存储的介质的如，文献【1 7 研究压缩技术以及如何在 磁盘上存储冗余信息。该文研究了使用磁盘作为存储介质的备份系统，并利用磁 盘的随机存取性质，研究了不同版本的数据的冗余存储技术以及归档的高效压缩 技术，并且实现了一个原型系统“a b a c k u ps y s t e m ”。 美国乔治亚大学的a n n l c h e r v e n a k 等人对当今比较经典的各种文件系统备 份技术作了详尽的调查和分析，并列一些主流的研究性质和商业性质的备份系统 按照各种标准进行分类。这些标准包括：基于设备的备份模式和基于文件的备份 模式，完全备份和增量备份模式以及数据压缩的可选性。他们还讨论了在线备份 的技术，这些技术有：文件系统加锁和快照备份技术。最后他们提出晟具有发展 前景的文件系统备份技术有可能是同时兼具支持增量备份，在线备份，数据压缩 和基于设备的备份模式 1 8 。 加拿大英哥伦比亚大学( u b c l 的n o r m a nc h u t c h i n s o n 等人对文件系统备份 的两种最基本方法，物理备份和逻辑备份进行深入的分析，讨论了两种方法各自 的优缺点。并且通过在一个特定的文件系统w 虹l 中进行两种方法的对比试 验，说明了物理备份的性能更优于逻辑备份f 1 9 1 。但是这一结论只适用于在该特 定的文件系统中。 德国的p e t e re i t e l 就网络环境下的备份提出了c s 结构的备份体系 2 0 。该 体系可以支持装有各利- 操作系统的p c 做客户端。并设计了m e d i ap o o l 以管理和 支持各种类型的介质，此外还提出了g u l 没计方案和网络管理方案。但是这个 备份体系只能对文件系统进行备份。 e m c 的d a v i da l o w 研究了针剥不同的数据源( 他称之为混合数据对象) 的 备份。提出了分布式环境下面向对象的备份模型【2 1 】。文中举例指明了一个备份 系统应具有的结构和组成部分，并且描述了该模型中的各种功能函数。但是，该 文未能对备份的数据源进行结构分析和形式化定义。在文中只提出了一个模型， 没有实现原型系统，而且这一模型的基础局限于采用o m g 开发的标准( 其标准 本身也在发展中) ，影响其通用性和指导性。 2 2 国内研究现状 目前国内对数据备份方面的研究还处于起步状态，专门研究数据备份的学术 机构很少。 y o n gz h u 和j i a n gl i n gz h a n g 提出了一个在分布式环境下基于k q m l 和 c o r b a 的完成数据存储任务的多a g e n t 交互的系统的模型【2 2 。系统中分层次设 计了存储设备代理，y o 代理，文件系统代理，资源管理和处理调度代理以及用 户交互代理。但是该文仅仅给出了一个模型的蓝图，即只对几个代理的职能作了 简单介绍，和i d l 描述。有关备份的技术细节和过程实现都没有涉及和讨论， 更谈不上系统的实现和性能分析。而且该模型只能针对文件系统的备份，虽然具 各分布式的特点但是不能满足跨平台的通用性，这也是不能满足现今应用的需求 的。 西北工业大学的李战怀教授带领的研究组的主要研究的是针对l i n u x 平台 下的数据备份。研究的内容包括逻辑卷的复制技术，异步主从式设备复制协议， 和远程数据复制系统的状态机的研究与设计。具体内容可参见参考文献【2 3 】【2 4 】。 2 3 目前备份领域存在的问题 通过以上对研究现状的分析，我们可以看出备份软件系统是一个复杂的分布 式系统，尤其是在网络环境下，备份软件而i 临着跨平台，插件化等诸多问题。例 如： 1 ) 恢复对象种类繁多 不同于单机备份软件系统的是，网络数据备份软件考虑的备份对象包括： w i n d o w s 文件系统f a t 3 2 ，n t f s 等；l i n u x 文件系统v f s ，e x t 2 ，e x t 3 ， n f s 等；数据库包括：o r a c l e 数据库系统，s o l s e r v e r 数据库系统，s y b a s e ， d b 2 等，以及其它应用级数据。 2 1 恢复过程与存储介质密切相关 由于存储技术的飞速发展，新技术层出0 ：穷，因此新旧设备共存的现象随处 可见，如：磁盘，r a i d 阵列，磁带库，光盘等。这些存储介质所带来的存 储格式不一问题将更加令人头疼。而在考虑数据的恢复时，不得不考虑到该 数据所存放的介质，在程序设计时不得不做大量的工作来从某种介质读取数 据。 3 ) 恢复时要考虑各种可能出现的问题，使得恢复过程越来越复杂 任何一个恢复的过程都是一个复杂的过程，除了恢复客户的参与之外，还有 介质服务器，备份服务器等，在整个过程中，可能发生网络中断，某个恢复 操作失败等情况，这些问题大大增加了程序设计的复杂性。 4 ) 恢复数据源的多样性，导致了恢复过程的多样性 正如第一点所描述的那样，有如此多的恢复数据源，每种数据源的恢复过程 都大不相同，比如o r a c l e 的恢复利用了r m a n ( r e c o v e r ym a n a g e r ) i 具，而 s q l s e r v e r 的恢复利用了v d i ( v i r t u a ld e v i c ei n t e r f a c e ) 接口，正因为如此，使 得开发与维护的难度大大增加了。 5 1 恢复程序难以插件化 正是由于恢复代理很难总结出公共的接口，使得恢复程序无法无缝地嵌入系 统。在目前大部分的备份系统中，恢复程序都足以硬编码的形式加入系统中 的，在进行系统升级时很不方便，必须替换整个程序。 6 ) 恢复过程不可控制 在恢复的过程中，比如与恢复客户( 如o r a c l e ，s o ls e r v e r 等) 进行多次交互， 而每次交互都可能成功或者失败，整个过程难以控制。而同前的系统一般是 采用大量的判断语句来进行恢复流程控制，由于交互过程的叠加，使得判断 语句成级数增长，这使得程序设计过程复杂并且难以维护。 7 ) 恢复需求千差万别 恢复需求不仅与恢复对象有关，而且与具体的业务有关。例如，对o r a c l e 数据库的恢复需求与对l i n u x 文件系统的恢复需求就不一样，o r a c l e 数据库 的数据文件有任何一个恢复失败，则数据库不能扣+ 开，处于不可用状态；而 对于l i n u x 文件系统来讲，丢失一个文件并不会导致系统瘫痪。从具体业务 的角度讲，银行，电信的7 x 2 4 小时运行的数据库系统，与校园网新闻发布 系统的恢复功能需求截然不同。 因此，面对如此众多的问题，首先建立高度抽象的数学模型进行分析，显得 十分必要再由模型出发，自上而下，设计出的备份软件系统设计方案，以使得 软件系统具有可扩展性强，思路清晰，行为严谨等优点。 2 4 前期的研究工作 中山大学软件研究所数据备份项目小组于2 0 0 3 年成立，对数据备份领域内 的问题和系统实现技术进行研究。研究的主要内容包括：建立理论模型，调度策 略和算法，备份代理技术，应用级的通讯协议，流式文本过滤技术，数据通道技 术，介质访问技术和网络安全和认证等。 前期的主要研究工作有： ( 1 ) 研究了在备份系统的研制中所遇到的关键技术问题，建立了基于测度概 念的理论模型，并给出了一个周期性各份的性能评估模型 2 5 】。 ( 2 ) 研究了数据备份系统的备份索引，重点的研究内容是备份结点生长树同 步映射的备份索引的表示和设计方法，克服了现有的备份索引表达能力 弱，适应性不强的缺点 2 6 1 。 ( 3 ) 基于x m l 的跨平台g u i 的研究，解决了对应于各种不同的备份资源的 界面插件化动态更新的问题1 2 7 1 。 ( 4 ) 对异构系统中的存储模型的研究【2 8 】。 2 5 本文的主要内容 2 5 1 本文贡献 论文正是以前期的研究为基础，根据在项目组中的实际设计和开发经验，并 在分析了o r a c le ，s q ls e i v e r ，l i n u x 文件系统等恢复过程之后，归纳出其在数 学上的性质，为恢复流程建立了基于有向图的通用理论模型，进而在此模型上讨 论恢复的详细过程，达到了澄清问题，帮助软件设计实践的作用。 然后在此模型的基础上，对通用模型进行了扩展，引入故障树的理论来对恢 复流程进行分析，从而实现了恢复流程的故障诊断。随后提出了一个恢复的自动 状态机，实现了自诊断恢复的过程。 在本文的最后，结合n e t b u n k e r 的实际开发情况，提出了基于有向图的通用 恢复模型的设计方案，包括了代理的组成部分，各部分功能及通用接口和类设计， 并基于a c e 实现了一个有限状态机的框架。在母后，以文件系统的恢复为例说明 了恢复代理工作过程。 本文提出的模型在一定程度上解决了之前提出的问题，并达到了以下目标： a 、恢复过程的通用性： b 、恢复过程的可控制性； c 、恢复介质无关性： d 、恢复代理程序的插件化。 2 5 2 主要内容及写作结构 通过对目前备份研究领域的分析，在研究开发实际的备份系统的基础上，针 对2 3 节所列举的问题，对备份概念做出归纳，研究分析各种备份源的恢复流程， 抽象出其统一的特征，提出了基于有向图的通用恢复模型。随后对模型进行了扩 展，对基于该模型的故障树与自恢复状态机进行了讨论，最后介绍了文件系统代 理的实现，解决了目前在恢复流程研究中缺乏统一的模型及通用性的问题。 本论文后续的写作如f 安排，第3 章提出了一个基于有向图的通用恢复流程 模型，第4 章对该模型进行了扩展，第5 章的内容是n e t b u n k e r 系统的介绍和该 模型在此系统中的应用，第6 章是总结和对未来工作的展望。 基于有向目的通用恢复模型的殴计与应用中山大学坝卜学位论文 2 0 0 65 3 1引言 3 1 1 恢复简介 第3 章模型的建立 恢复由两个过程组成：还原( r e s t o r e ) 和恢复( r e c o v e r ) 还原指使用备份集( 全备份或者增量备份) 来重建特定时刻的一个备份对象。 恢复指应用重做日志来改变还原操作生成的备份对象，使之可以成为符合用 户要求的特定时刻的数据版本。被应用的重做日志应该记录了自前面备份集生成 时刻后的改变。 显然，还原与恢复的顺序不可颠倒。通常，我们指的恢复只是指严格意义上 的还原阶段。 根据恢复对象的范围，我们把恢复类型分成： 全数据集的恢复 顾名思义，指对全部数据集进行恢复，而不是只恢复某一部分数据集。例如， 在o r a c l e 数据库中的恢复一个数据库，恢复一个实例；在l i n u x 文件系统 中的恢复根目录( ”) 文件系统等。 部分数据集的恢复 与全数据集的恢复意义相反，它只对某一部分数据进行恢复。例如，在o r a c l e 数据库中的恢复一个表空间，恢复一个数据文件：在l i n u x 文件系统中的恢 复某一个非根目录的文件系统，目录，或者文件等。 根据恢复事务的完整性，我们把恢复类型分成： 完全恢复 顾名思义，指用户所有作的修改都被更新了，数掘处于最新的一致性的 状态。例如，在o r a c l e 数据库中所有无需r e s e t l o g s 的恢复；存l i n u x 1 ， 文件系统中，就是指把用户数据恢复到最新状态，虽然l i n u x 系统中并 未明确定义该操作。 不完全恢复 与完全恢复的意义相反，恢复动作并没有让用户数据回到最新状态就停 止了。例如，在0 r a c l e 数据库中的基于时间点的恢复，基于c a n c e l 的 恢复，基于s e n 的恢复：在l i n u x 文件系统中的所有有用户数据损失的 文件或目录的恢复。 根据恢复对象的受破坏程度，我们把恢复类型分成： 灾难性恢复 顾名思义，指不仅用户的普通数据( c d ) 需要恢复，元数据( m d ) 也需要恢 复。例如，在o r a c l e 数据库中，用管理树的观点来看，需要恢复的元数 据可能是：硬件类型，操作系统环境，环境变量设置，控制文件等：在 l i n u x 文件系统中，需要恢复的元数据可能包括：机器型号，磁盘分区 状况，目录结构等。 非灾难性恢复 指所有灾难恢复以外的情况。在此就不一一举例说明了。 3 1 2 模型概述 在分布式的网络环境下，由于有多种数据源的存在和用户的多种需求，使得 恢复的过程非常复杂，这样大大增加了代理程序的设计及实现，也严重影响了代 理的插件化。针对以上问题的分析，对各种恢复的过程进行了抽象，将整个恢复 过程抽象成了一个有向图，把恢复过程抽象成对这个图的遍历，从而将恢复过程 统一了起来。 3 2 基本定义 定义1 设g = ( v ，e ) 是有向图，v 、e 中的元素分别表示图的节点和弧，e = ( u ， v ) e ( g ) ，则称u 为e 的起点或尾，v 为e 的终点或头，又称u 为v 的前驱，v 为u 的后继，前驱域为r 一( v ) ，后继域为r + ( vo 2 9 定义2 给定一个有向图g = ( v ，e ) ，在v 中指定了一点为发点vs ，另一点为 收点v t ，其余是中问点，对于每一个弧( v i ，v j ) e ，列应有一个c ( v i ，vj ) 0 ，称为弧的容量。通常把这样的g 称为网络，记做g = ( v ，e ，c ) 。 2 9 定义3 在有向图中，存在一个结点，它的前驱域r 。( v ) 为空集，那么称该结 点为有向图的起始结点。 定义4 在有向图中，存在一个结点k ，它的后继域r + ( v ) 为空集，那么称该结 点为有向图的终止结点。 定义5 设g 是有向图，g 中顶点和边交替的序列r 。、a j , v d h 气勺称飞到0 的路 径。 定义6 从起始结点到终止结点之问的一条路径称为恢复路径。 定义7 若g 是一个有向图，则映射m ：y _ 称为一个状态。对v k 若呶v ) = k ， 则称结点p 标记的权重为女。 定义8 在系统的有向图中，一条有向边称为一个迁移，代表着系统的状态变迁， 有向边的方向，称为迁移的方向。 定义9 若存在某个结点v ，v 是至少两个迁移的输入结果，则、，称为冲突，决策或 者选择。 定义1 0 在有向图中，任意个结点矿代表着某个状态改变的结果，称任意结点矿 为结果，或变量。 定义1 1 一个恢复的有向图模型由五个部分组成g = 似ze 形m 以其中： v 是结果( r e s u l t ) l 掣3 有限集合； z 是迁移( t r a n s i t i o n ) 的有限集合； 矿几t ：m y u 丁中： ec ( v x ur v x t ) 是有向弧的集合： w ? e 4 + 是弧的权函数； m o ：矿+ 是初始状态。 定义1 2 若弧( v ，t ) e e 量v x 2 ；则称v 是f 的输入结果：而若弧( f ，v ) e 生v x t , 则称v 是t 的输出结果。对( v ，t ) e 或( f ，y ) e ，w ( v ，r ) 或w ( f ，p ) 称为对应弧的权。 状态迁移规则：设m ：y + 是有向图g 的一个状态，t t 。 ( 1 ) 迁移f 称为在状态肘下有效的( v a l i d a t e ) ，如果对f 的任何输入结果v ，有 m ( v ) = w ( v ，f ) 。 ( 2 ) 设迁移f 在状态m 下为有效的，m 是如下定义的状态：对v k m ( v ) = m ( v ) w ( v ， 1 ) m ( v )+ w ( t ，v ) m ( v ) 若v 是t 的输入结果 若v 是t 的输出结果 若v 为其它结果 则称t 被触发，且系统从状态m 迁移到状态m 。，记为肌。 3 3 备份和恢复的定义 在参考了前人对备份和恢复的认识之后，并在n e t b u n k e r 系统的实际开发过 程中不断升华，我的师兄张金波同学在他的毕业论文中总结女1 1 t 3 0 ： 定义1 3 【备份对象】( b a c k u p0 b j e c i ) 备份程序( 备份代理或备份引擎) 所 作用的对象，在备份软件系统中也指备份客户，从资源管理的角度来讲，任何有 备份需求的，可备份的实体，如，一个企业网中的某个o r a c l e 域等，都是备份对 象，汜做b o 。 定义1 4 【数据集l ( d a t as e t _ 卜备份对象的一种，特指一个系统中数据的集 合，也即本文所关注的备份对象。我们用符号d 来表示数据集。 定义1 5 【最小备份单元】( m i nb a c k u pu n i t 卜数据集的基本组成单位，数 据集的变化将以最小备份单元为单位发生变化，我们以后也将简称为备份单元 ( b a c k u pu n i t ) 。我们用符号“来表示一个备份单元，最小备份单元与备份对象的 关系如下图所示。 厂一一一一一 l 图3 - 1 虽小备份单元示意图 则d 为可以表示为如下一非空集形式，“为集合中的元素，设总共有n 个备 份单元： d = 扣 “au 3 , a 。“0 定义1 6 【备份】( b a c k u p l 一对数据集的全部或者部分进行复制以及压缩， 变换，移动等操作，生成另外一个数据集的实体。 定义1 7 【备份集】( b a c k u ps e t 卜_ 对数据集进行备份所生成的新的实体。 我们用符号曰。来表示。 定义1 8 【各份列】f b a c k u p q u e u e ) 一由一系列备份集所组成的集合。我们 用b 来表示备份列。 b = f 口i tb n ，2 ，b 吐， 定义1 9 【恢复】( r e s t o r e ) _ 一通过应用备份集，把数据集还原成荣一特定的 状态。 3 4 恢复有向图模型的一些重要性质的讨论 1 无环性 任何一个模型图都应该是无环图，这样才不会出现死循环的过程。即对于任 意过程变量v i ，不会存在路径v i v i l v i 2 v 。v j 。这样就保证对于任意的迁移 序列，不会出现死锁。 2 可达性 设g = ( k 司是一个有向网。一个迁移序列s = t l 加是状态和迁移的序列： m o t l m l t 2 m 2 t n m n g2 ( k 司的所有可能的迁移序列的集合记为三( g ) 。 若5 t o t lm 1t 2 m 2 k 厶，则称状态m n 可由肘。通过s 到达，并记为肘o s m n 。 所有可从肘。到达的状态的全体记为月( g ) 。 3 可覆盖性 有向图g = ( k e ) 称为可覆盖的，如果在起始状态m 下，通过适当的迁移序列 后，每个状态最终都可以被到达。 3 5 统一恢复公式 基于以上定义，提出一个统一的恢复公式如下： r e s t o r e ：yxb_x 其中y 过程变量集合，b 是备份列，x 是恢复目标集。 3 6 恢复流程中的状态迁移方程 在考虑方程时我们假定有向图不存在输入输出结果都相同的迁移( 称为个 自回路) 。这并不是个严重的限制，因为任何自回路都可以通过增加一个结果和 迁移化解为回路，如下图所示 图3 2 有向图中自回路的化解 设有向图g 有n 个迁移和m 个变量，即：t = t l ，如) ，v = v l ，v m 。 对i = 1 ，n ，= 1 ，m ，令： 日；= w ( v f ，t j ) ，口i = w tj ，v f )