（计算机软件与理论专业论文）基于通用资源树模型的备份系统的设计与应用.pdf

中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 基于通用资源树模型的备份系统的 设计与应用 专业：计算机软件与理论 硕士生：杨志明 指导老师：倪德明副教授 摘要 近年来，随着企业业务的扩展，企业中应用数据的种类和数量都急剧增长， 对数据的保护变得越来越重要。数据备份是数据保护最重要的手段，因此对它的 研究具有重要的现实意义。 由于备份对象种类繁多，需求千差万别等，所导致的后果就是，在设计备份 软件的备份模块时，很难使得备份模块的通用化和可插件化，而且数据源的获取 是数据备份系统中的一个重要环节，由于数据源的多样性和获取数据源手段的多 样性，使得在备份系统的开发中，更难实现备份系统框架的通用性以及备份信息 展示接口的一致性，备份中操作的实现要与具体的备份源相关。 对此，本论文将解决以下几个问题，第一，对数据备份对象进行分析，研究 和抽象，将以资源树的形式来组织需备份的数据资源，设计出通用资源树模型和 基于此模型的备份处理模型，为备份操作和数据信息展示提供标准的接口，以实 现备份系统框架的通用性。第二，考虑到备份数据的海量、流式处理及传输等特 点，本论文还将实现大型资源树的动态生成以及迭代遍历。第三，本文还实现了 文件系统到m t f 格式的备份，从中我们可以看出，m t f 格式很好的符合了这种 通用资源树模型要求。 关键词：资源树，备份流程，通用模型 中山火学顾二仁学位论文 基于通用资源树模型的备份系统的设计与应用 d e s i g na n da p p l i c a t i o n0 ft h eg e n e r a lb a c k u pm o d e l b a s e do nr e s o u r c e t r e e m 司o r ： s o f 啊a r ea 1 1 dm e o r yo fc o n l p u t e rd c p a r h i l e l l t n 锄e ：y m gz h i m i n g s u p e i s o r ： a s s o c i a t ep r o n id 锄i n g a b s t r a c t w i t ht l l ee x p 锄s i o no f b u s i l l e s se v e l l t s ，t l l eq u 柚t i t i e s 锄ds 耐so f 廿l ea p p l i c a t i o n d a t aa r ei n c r e 嬲i n gc o n s e q u e i l t l ya n dr 印i d l mt l l ed a t ap r o t e c t i o nh a sb e c o m em o r e a n dm o r ci i n p o r t a n t t h e f e f o r e ，m er e s e a r c ho fm ed a t ab a c k u p ，m em o s ti m p o r t a n t m e m o df o rd a t ap r o t e c t i o n ，p o s s e s s e sg r e a ts i g i l i 6 c a i l c e t h e r ea r em 锄yp r o b l 锄sd l 】r i n gt l l eb a c h l p ，i n c l u d i i l ga g r e a tv a r i e t yo fr e s t o d n g o b j e c t s ，d i 丘i e 崩1 tt y p e so ft l l es t o m g ed e v i c e sa j l dd i s 衄c t i v ed i f f 打吼c e si 1 1 廿l en e e d s f o rb a c k u p a sar e s u l t ，t l l eb a c k u pm o d u l ew i l lb eh a r dt ob eu t i l i z e dg e n e r a l l y 锄d p l u g g e d i nf o ri t s1 a c ko fn l em e o r e t i c a lg u i d a i l c ea 1 1 d 内u n d a t i o nw h e l li ti sd e s i 弘e d f o rt l l ee n t e 印r i s e sb a c k u ps o f t 、) l ，a r e ，孤dm ew r h o l eb a c k u pp r o c e s sw i l lb ed i f 矗。r e l l tt 0 c o n 仃0 1 w h a t sm o r e ，d u et ot h ec l o s er e l c v 锄c eb e 帆e e nt h eb a c k u pp r o c e s sa l l d 也e s t o r a g em e d i u m 孤d l em a s s i v ea n db o r i n gw o r k ，j ti se a s yt 0m a k em i s t a k e sw h e n d e s i g i l i n gt t l eb a c k u p - r e s t o r i n gs o r w a r e s f o r l e s er e 嬲o n s ，t 1 1 i sn l e s i sw i l ls 0 1 v em ef o l l o w i n gp r o b l e m s ，a tf i r s t ，w ew i l l 西v ear 髓o u r c e - t b em o d e la n de s t a b l i s hag e l l e r a lb a c k 呻m o d e lb 鹤e do nt l l e r e s o u r c e - i r e em o d e l ，a n dc o n s i d e r i n gm ed a t a 、7 l 杜c hw i l lb eb a c k u p e di sh u g e ，w e 谢nb u i l dm er e s o u r c e - 1 k ea l l i m a t e d l y a l l d 丘n a l l yw ew i l li i n p l e m e n tt h i sm o d e lt o b a c h l pd a t a 五的mf i l es y s t e ma i l dm a i ls y s t 锄t om t ff o m a ta 1 1 d 丘o mm a t ，w e 、村n f i n d 1 a tm t fi sw e l lf i t 佑rt h em o d e l k e y w o r d s ：r e s o u 】r c e - t k e ，b a c l c u pf l o w ，g e n e r a lm o d d h 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：桷茗鲜) 日期：绗卵矽日 使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学位 论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅， 有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方 法保存学位论文。 学位论文作者签名：桷毛嘲 日期：加萨矿月刁日 导师签名： 降隍谓 日期川年厂月谚日 中山大学硕士学位论文 基于通用资源树模型的备份系统的设计与应用 ( 3 ) k g a t 0 研制开发的n e t w b r k e r 数据存储管理系统提供了c s 体系结构下的 网络数据存储管理解决方案。 在国内，还没有什么公司开发出了在市场上能占有一定份额的备份软 件，除了一些自由的软件之外，大部分的企业都选择前述的三大公司的备份 软件产品。国内大部分的备份软件都是一些小公司制作的备份系统，优势和 技术含量都不是很明显。 4 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 2 4 本文的主要内容 2 4 1 本文贡献 论文正是以前期的研究为基础，根据在项目组中的实际设计和开发经 验，并在分析了w i n d o w s 文件系统，邮件系统，s q ls e e r 等备份过程之后， 归纳出其在数学上的性质，从而为备份流程建立了资源树的通用理论模型， 对备份领域的诸多常见的概念，术语给出了形式化定义，进而在此模型上讨 论备份的详细过程，以达到澄清问题，帮助软件设计实现的目的。 进而在此模型的基础上，对备份处理模型进行了定义，并对备份过程进 行了分析和给出了形式化的定义。 在本文的最后，结合p r 0 r e c o v e r y 的实际开发情况，提出了基于资源树 的通用备份模型的设计方案，并且最后以w h d o w s 文件系统的备份恢复为例 实现了此模型。 2 4 2 主要内容及写作结构 通过对目前备份研究领域的分析，在研究开发实际的备份系统的基础 上，针对2 3 节所列举的问题，对备份概念做出归纳，研究分析各种备份源 的备份流程，抽象出其统一的特征，提出了基于资源树的通用备份模型。最 后介绍了基于文件系统和邮件系统的实现，在一定程度上解决了目前在备份 流程研究中缺乏统一的模型及通用性的问题。 本论文后续的写作如下安排，第3 、4 章提出了一个基于资源树的通用 备份流程模型并给出了实现，第5 章对该模型的储存模型进行了分析，第6 章的内容是该模型的应用，第7 章是介绍本论文的不足之处和对未来工作的 展望。 7 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 3 1 引言 第3 章通用资源树模型 随着计算机应用的发展，备份的资源的种类越来越多和越来越复杂。然 而目前的备份系统都是针对某一特定资源开发，如果资源交了，则需要从头 ， 开始，重新设计方法，开发新的备份系统。从开销，成本和软件重用的角度 来看，这都是非常不利的。研究如何忽略特定环境下的因素，抽象出备份要 求下各类备份数据资源具有的公共特质，显得非常必要，这也是建立通用的 备份的理论模型的前提。 本文通过对目前备份研究领域的分析，在研究开发实际的备份系统的基 础上，提出了通用备份资源树模型。 3 2 基本定义 定义3 1 【备份对象】各份程序所处理的对象，从资源管理的角度来讲， 任何有备份需求的，可备份的任何实体如，一个局域网子网中的所有主机， 或者一台p c 机的文件系统，都是备份对象，记做b 0 。 定义3 2 【数据集】属于备份对象的一种，用来特指一个备份系统中数 据的集合，我们用符号d 来表示数据集。 定义3 3 【最小备份单元】数据集的基本组成单位，数据集的变化将以 最小备份单元为单位发生变化，我们将其简称为备份单元( b a c k u pu i l i t ) ， 我们用符号“来表示一个备份单元，最小备份单元与备份对象的关系如下图 所示。 8 则d 为可以表示为如下一非空集形式，“；为集合中的元素，设总共有n 个备份单元： d = 扣西m 力“岛蚶 由定义我们知道，数据集d 是数据备份对象的一种，而数据集d 又是由 最小备份单元“组成的，鉴于本文建模的需要，以下将进一步对这些概念进 行讨论和分析。 备份对象我们可以从两个角度进行划分，空间的角度，也即：实际存在 的形式，还有逻辑的角度，也即：数据的组织形式。 空间的角度 我们可以根据备份资源的存在形式，把它划分成由一个个的e n t i t y 组成， 每个e n t i t y 代表实际存在的东西，以文件系统的备份为例，如图3 2 所示， 每个文件或文件夹都是一个e n t i t y ，它包含了这个文件或文件夹的全部信息， 比如，文件名，文件内容，文件的其它属性信息等。由此，从这个角度，我 们知数据集是由e n t i t y 组成的，且可以进一步的认为e n t i t y 为备份操作处理 的最小单元，也即：最小备份单元“为e n t i t y ，在本文中，也将从这个角度 建立起备份资源的树型模型。 逻辑的角度 理论上讲，所有的数据可以分为两类【1 9 】； 1 元数据对象( m e t ad a t ao b j e c t ) 2 普通数据对象( c o 咖o nd a t ao b j e c t ) 所有的普通数据对象又可以分成两类 9闪嚼 9x 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 定义3 4 【备份资源树】以树的形式组织起来的备份数据资源的集合叫做备 份资源树。 所谓备份资源树，指用树来反映一个待备份对象的内部层次关系。其核 心功能在于把备份对象分层，细化。备份资源树的概念是一个广泛意义上的， 一个例子如下图3 3 所示。 资源树中的结点为资源结点。某资源结点连同其所有后继结点所组成的 集合称为以该结点为根的资源子树。资源树可以使用真前缀的方式来表示。 关于对资源树的表示法以及更多真前缀的内容，具体可参见。 资源树有着非常重要的现实意义。事实上，树结构抽象出了一种非常普 遍的对象分类的方法。例如，如果把一个局域网视为树的根结点，则它的子 结点可以是局域网中的各台主机，而每一台主机的子结点则是主机上面的文 件系统或者数据库系统，进而每一个文件系统的子结点则是根目录下面的子 目录，以此类推，最终的叶子结点可能是文件，甚至可以是一个数据块，一 个字节，一条记录，一切看划分的粒度； 图3 3 一个资源树的示例 又例如，对于一个o r a c l e 数据库系统来讲，如果把一个o r a c l e 实例视 为树的根结点的话，则其子结点就是各个表空间，而每一个表空间的子结点 可能是下属的各个数据文件，或者是所属的各个对象如表，视图，索引，角 1 1 中山大学硕士学位论文 基于通用资源树模型的备份系统的设计与应用 色，同义词等等，这要看划分的粒度而定。 图3 4o r a c i e 数据库系统的资源树 把备份资源抽象为树状结构，对于发现问题的本质，提出通用，可扩展， 架构良好的设计方案有着指导性的意义。 3 4 资源树的结构及性质 图3 5 资源树结构 不管是一个0 r a c l e 数据库系统的资源树，还是基于局域网的资源树， 我们都可以抽象出以下结构，如图3 - 5 所示，图中，蛔是组成备份对象的基 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 本单位，我们可知b o = 6 d 。，6 d ：，幻，) ，也可以用数据集d 来表 示d = r “。，“：，h 3 ，“。，其中6 q = 魄，它们都是e n t i t y ，通用资源树 是从空间的角度来建立的。 通用资源树它是一个树型结构，它具有树型数据结构的所有性质，我们 也有子树的概念，不过我们这里把它称为资源子树。在备份的过程中，我们 知道，一定是按一定的顺序进行的，所以我们还将规定兄弟结点之间的顺序， 也即，通用资源树是一棵有序树，最左边的子树的根称为第一个孩子，最右 边的子树的根称为最后一个孩子，这点在后续章节还将会做更详细的讨论。 这里本文还将提出平均深度的概念，在数据结构中，有深度这个概念，平均 深度是对它的一个扩展。 平均深度也就是所有结点深度的平均值，在定的程度上它反应了树结 点元素在空间上的分布情况。在资源树中，每一个结点“；都有一条从根结点 到它的路径，记为，所有路径的集合记为： l2 l l ，t 2 ，t 3 ，t 。 路径的长度记为l ti ，则有集合： ij li = 彳i 厶l ，i 乞i ，i 乞i ，i 乙l 夕 平均深度i i = 三多l ti ，l 三l 一= 笔，它代表此棵资源树只有一条链， 以舒 z 而l 三k = 生兰，它说明此棵资源树只有一层，也就是树的深度为一，图3 5 的小等。 下面将对备份对象，也即数据集进行分析，首先，将对数据集中的元素 进行分类，d = l r “，“：，“，h 。，吩代表最小的备份单元，也就是一个 e n t i t y ，但对于备份来说，这还不够，不能给备份操作足够的语义，比如， 对于文件系统，d 包括所有的文件和文件夹，对于备份操作，对文件和文件 1 3 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 的信息，+ 如标准流、安全信息流等，我们给每个s e 鲫e n t 一个类型参数，使 我们能识别它所包含的信息类别。 下面将再以邮件系统为例，来进一步说明以上的分类方法，使之更易理 解。假设我们将要备份系邮件统，那么，我们可以画出资源树图，如图3 - 7 所示： 图3 - 7 邮件系统资源树结构 邮箱属于根结点，是n o d e 类型，后面还会更进一步的提出虚结点的概 念，而邮箱就是属于虚结点类型。收件夹，发件夹，草稿箱也都是属于d e 类型的结点，邮件是属于k a f 类型的结点，和文件系统的资源树一样，这里 s e 舯t 类型的结点在图中没有表现出来，如果说在文件系统中的s e 舯e n t 还有n r f s 的多流与之对应的话，那么这里的s e g m e n t 是纯虚拟的，是我们 从语义上定义的，我们这里把每封邮件的主题，附件，正文等，都定义为 s e 舯e n t 类型的结点，它是属于邮件结点的子结点。 3 5 资源树的访问模型 我们知道，资源树所有结点的集合就是数据集d ，既然它是一个集合， 下面本文将从集合的角度来更进一步讨论资源树的性质，并得到资源树的访 问模型。 对集合的讨论，一般就是在这个集合上提出一些关系，在对这个关系进 行分析，以达到分析集合特性的目的，本文也将如此，将提出两个关系，f 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 和s 。 定义3 5 ：设有数据集d = 扣。，“：，m ，h 。j ，定义关系f ，y ) ，如果x 为y 的父结点，并且规定f o ，z ) ，其中x ，y d 。 我们可以证明二元关系f 是偏序的，首先，由定义可知f 是满足自反性 的，即f o ，x ) ，如果f 0 ，y ) f ( y ，工) ，那么由f o ，y ) 知x 为y 的父结点，再 由f ( y ，x ) 知y 为x 的父结点，很显然) ，= x ，所以f 是具有反对称性的。如 果f o ，y ) f ( y ，z ) ，那么由f o ，y ) 知x 为y 的父结点，再由f ( y ，z ) 知y 为z 的父结点，由资源树的树状结构可以看出，x 为z 的父结点，即f o ，z ) ，所 以f 具有传递性，综上所述： 自反性：觇d ，f 0 ，z ) 反对称性：慨，y d ，i ff o ，y ) f ( y ，z ) t h 锄) ，= x 传递性：慨，) ，z d ，i ff ，) ，) f ( y ，z ) t h e nf o ，z ) 所以f 是在数据集d 上的偏序关系。 在前面提到，通用资源树是一棵有序树，也就是兄弟结点之间是有顺序 的，最左边的子树的根称为第一个孩子，最右边的子树的根称为最后一个孩 子，为此本文将定义一个二元关系s 。 定义3 6 ：设有数据集d = i r 。，“：，“，“。夕，定义关系s o ，y ) ，如果x 为) ，的兄弟结点且在有序树中，x 在) ，的前面，并且规定s o ，工) ，其中 x ，y d 。 同样我们可以证明二元关系s 是偏序的，首先，由定义可知s 是满足自 反性的，即s 0 ，z ) ，如果s 0 ，y ) s ( y ，z ) ，那么由s o ，) ，) 知x 为y 的左兄弟 结点，再由s ( y ，z ) 知y 为x 的左兄弟结点，很显然y = x ，所以s 是具有反 对称性的。如果s o ，) ，) s ( y ，z ) ，那么由s o ，) ，) 知x 为y 的左兄弟结点，再 由s ( ) ，z ) 知y 为z 的左兄弟结点，由资源树的树状结构可以看出，z 为z 的 1 6 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 左兄弟结点，即s ，z ) ，所以s 具有传递性，综上所述： 自反性：城d ，s o ，x ) 反对称性：觇，) ，d ，i fs o ，y ) s ( y ，x ) t h e ny = x 传递性：慨，) ，z d ，i fs o ，y ) s ( y ，z ) t h e ns ，z ) 所以s 是在数据集d 上的偏序关系。 在备份的过程中，对资源树的处理，主要是对资源树的遍历，而且整个 备份的过程中，只遍历一次，考虑到恢复操作，这里选择先序遍历。目前， 只考虑对资源树的访问，不考虑对其进行具体的备份操作，那么我们可以定 义一个函数g ：d 呻d ，它的作用就是把资源树打成扁平结构，我们知道， 考虑到恢复的需要，这个函数必须要求是保序的，如图3 8 所示： 图3 - 8 资源树访i 司图 图右边的结点系列，是图的左边资源树打成扁平以后存到介质上的示意 图，它保持了资源树的两个偏序特性，要维护这种特性，就必须把树状的结 构信息记录下来，这就要用一种具有自描述特性的格式对数据进行封装，本 文采用的是微软的标准磁带格式，这点将在后续章节做详细的讨论和分析。 前面提到函数g ：d 呻d 必须具有保序的特性，用数学上的语言就是， 如果f ，) ，) ，那么f ( g ) ，g ( y ) ) ，如果s ，) ，) ，那么s ( g o ) ，g ( y ) ) 。 3 6 模型的实现及相关类图 在前面几节中，对资源树的结构和性质进行了详细的分析，并给出了访 1 7 中山大学硕士学位论文 基于通用资源树模型的备份系统的设计与应用 图4 1 资源树结点分类图 这里s e g m e n t 我们用虚线表示，因为它一般是虚拟的。我们通过资源树 访问函数g ：d 呻d 得到的扁平结构如图4 2 ： ( 颚蔓麟蔓e 瞧) ，残蔓题) ( d 图4 2 资源树扁平结构图 在这个结构中，可见的还是结点，要使备份独立与数据源，那么我们还 要进一步转化，得到数据流图，如图4 3 ： 叵叵田卫羔田夏田! 叵田i 丑蔓i ：田霉 图4 3 资源树扁平数据流图 其中，单元格代表数据，每个单元格都与图禾2 中的结点对应，在备份 过程中，处理的就是这些框框组成的数据流，那么处理算法如何区分这些数 据呢? 并且要独立与数据源的，考虑到资源树的结构和处理算法的特性，提 出了数据源级别的概念，把图4 - 3 中的数据流按级别划分为各个段，记为 b l o c k ，简记为b 。如图4 4 所示： 图4 4 数据级别划分图 分成三个级别，第一个为数据集级别，也就是图中的d a t a s e t ，它代表整 个备份处理的数据，从备份的起始点到备份的结束点之间的数据总集。大家 注意看图4 4 ，发现l 变成了n ，这里把l 当着n 对待，具体通过标志位区 别，这是为了级别划分更清晰。第二个级别为n o d e 级别，这个d e 和资源 2 1 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 b 图4 6 标志位置位图 备份过程种可以检测这些标志位来决定备份处理流程。 4 2 2 算子 我们把备份中对数据流序列实施的具体处理的构件( 程序或算法) 称为算 子【2 2 1 ，比如，进行压缩处理的压缩算子，进行加密处理的加密算子等，我们 可以进一步把这些算子理解为具有特定功能的函数。从b l o c k 类型出发，可 以把算子分为三类，以d a t a s e t 为处理单位的算子，以d e 为处理单位的算 子和以s e 舯e n t 为处理单位的算子，可以表示为：厂：f _ f ，t 为类型， f p ，s ，注意，的定义域和值域都是，这是因为我们是从b l o c k 的角度去研究算子的，算子改变的只是b l o c k 中包含的数据，而不会改变 b l o c k 的类型，所以算子有个很重要的性质，那就是b l o c k 类型的不变性， 即：，p ) a 。 算子是一个极其重要的概念，它在处理模型中扮演着重要的角色，抽象 出了备份过程中的所有处理操作，把备份过程看成是由这些算子的组合构成 的，这可从下小节的讨论中可以看出。 4 2 3 备份集 对选择集备份后所生成的新的数据实体，描述了备份代理的一次执行备 份的所有内容，是恢复程序操作的备份集资源树。 中山大学硕士学位论文 基于通用资源树模型的备份系统的设计与应用 4 3 基于资源树的处理模型 在前面章节，我们给出了通用资源树模型和访问模型，下面将要在这个 基础给出备份的处理模型，从它可以看出，本模型给备份系统的设计提供了 一个通用的框架。 我们可以把备份定义为： 备份= 拷贝+ 转换+ 传输+ 存储+ 管理 也就是说，备份就是对需要备份的资源使用对应的方式进行拷贝，然后 根据实际的需要对原始数据进行一系列的数据转换，通过不同层次的网络传 输协议和通道技术传输到介质，最后以适当的存储结构存储在选定的介质 上，并且整个过程以及相关的资源都处于一个备份中心的管理调度之下。本 章将从实现的角度和以通用资源树模型为数据源出发，给出备份的处理模 型。 我们把备份过程定义为如图4 7 所示： 日洲怔乎换母处理圈 图4 7 备份处理流程图 首先，此过程是基于数据流的，不管是树结点系列，还是b l o c k 系列都 是数据流，他们隐含在数据流中，而数据流又是由他们构成的，他们是从左 向右流动，穿过每一个操作。从这个角度来看，属于数据流处理模型f 2 2 1 ，数 据流处理模型是一种新的数据处理模型，这种模型中数据不再是永久的关系 形式，而是大量的、连续的、快速的、随时间变化的数据流。数据流出现在 许多应用中，比如股市交易、网络检测、电话通信、传感器网络等等，本模 型将以数据流为基础建立来。 接下来，我们针对备份处理流程图中的各个操作，给出详细的分析： 访问指的是对通用资源树进行访问，把资源树打成扁平结构，产生树的 结点流，如图4 8 ： 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 日 ，歌蔓：题) ( 图4 8 资源树访问图 这个函数我们在资源树模型中已经分析过，它就是函数g ，还提到它具 有保序性，它是我们访问资源树的唯一途径，是资源树与处理模型联系的桥 梁。 变换是指把访问资源树时产生的树结点系列加上标志位，使之变成可以 识别的b l o c k 结构，只有得到可以识别的数据，后面的处理才能正常进行， 可以说它是这个模型的控制中心，图4 8 的结点系列处理后如图4 9 。 b 图4 9 变换后的数据流图 在模型中它是通过一个算子实现的，叫做b r e a d e f ，我们用函数r 表示， 算法如下： t o s e t ( b d s ) ；置标志位 w l l i l e ( ! ( n = g o ” 删断是否还有结点没有处理 s e t ( b n s ) ； w h i l e ( h 弱s e g m t ( 呦 判断结点是否还段没处理 s e t ( b s s ) ； p r o c c s s o ；对数据进行处理 s e t ( b s e ) ； c l s o ；清除标志位 ) 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 s e t ( b d e ) ； c l s o ； 】 s e t ( b d e ) ； c l s o ； ) 处理是指那些算子的调用，对流过的数据根据标志位的值，进行相应的 操作。在前面的定义中，我们把数据流看作一个时间轴，进一步把标志位值 的更改用时间来表示，对于每一个函数厂都可以形式定义一个函数： f 1 n ( f ) 5 1o l i f t 口稻s tst 占硒，五r 进行处理 其它时刻，五f 不处理 这样我们可以得到p o ( f ) ，p - ，p 2 0 ) ，p 。( f ) ，他们是属于业务上 的，如压缩算子，加密算子等等。整个的备份处理过程就是这些函数的调用， 我们可以用函数p o ) 来表示： 耶) 。u 乏a ( f )儡 由上面的分析，我们得到了函数g ，r 和p ，再加上资源树r t ，于是 我们这里可以把备份表示为一个四元组： b a c k u p = ( r 工g ，z ，尸) ，这个 构成了我们模型的核心，在此，我们把本文提出的通用资源树模型以及在此 基础上提出的处理模型简称为r 正g ，1 1 p 模型。 4 4 r t g t p 模型分析 我们知道，程序可以看成是由数据和对数据进行处理的操作构成的，在 r 卫g 即模型中，很好的遵循了这种划分，r t 属于数据部分，而g ，r ，p 则是属于操作部分，r 卫g ，r p 模型的流程图如图4 一1 0 所示： 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 第5 章m t f 格式在模型中的应用 5 1 引言 这一章要讨论的内容是前面提出的模型的存储模型。存储这一部分包含 了两个级别的内容【为l ：逻辑级和介质级。前者是本章所讨论的内容，它包含 了归档以及存储块的设计和实现。 我们把原始的资源树经过了一系列的变换之后，要存储到介质【2 4 1 当中的 数据称之为备份集。进一步，我们将备份集的存储结构称为归档( a r c l l i v e ) ， 归档指指的就是对原始的备份数据封装后将要存储到介质中的数据形式。 目前，与备份数据存储结构相关的比较典型的就是t 盯结构和m 邛。 t a r 【2 5 l 模恚 羹薹l蓊器鞘裂雀i冀酬；搿鐾薹霎叁酵m酿鹱i型羹季囔-丌耋墓篓霞； 湃差惩器鋈蓁鋈瀑遵强逛琵涩1月3；捌缀研暮谢翌盟珊矗；霪霆霾墓i审 施蓁； 将输出存储到设备，文件或者其他的程序中。肼( m i c r o s o f tt a p e f 0 珊a t ) f 2 6 l 是由微软公司提出的一种通用的数据存储格式。m t f 可以被用 于在存储管理或数据库操作的时候从可移动的存储设备中读写数据。这一存 储格式是与胛励政印应用程序中的数据格式是兼容的。由于t 盯结构的数 据结构繁多，结构相对比较复杂，而且不能用于其它的文件系统中。而 m 是一个线性的结构，m 邛功能丰富，在结构上和资源树模型的资源 树结构具有一定的同构性，因此这中存储形式适合我们设 计的备份系统模型。 中山大学硕士学位论文 基于通用资源树模型的备份系统的设计与应用 f i l e m a r k 被用来作为逻辑分隔符，在介质中提供更快的定位。 5 2 2 1 d b l k 结构 d b u 【是m t f 格式最重要的e l e m e n t ，它提供了控制信息，d b u ( 是一个 可变长的结构，它由四部分组成，如图5 2 所示： 图5 2d e s c r i p t o rb 1 0 c kl a y o u t 首先是通用头结构( c o m m o nb l o c kh e a d e r ) ，它是固定长度的，所有 d b l k 都含有这个结构而且必需含有，接下来是固定长度的与d b l k 相关的 信息，不同的d c s c r i p t o rb l o c k 是不同的，与特定的d b l k 有关，再接下来 是o p e r a t i l l gs y s t 锄s p e c i f i cd a t a ，它是与d b u 【类型和操作系统有关，最后 是一个可变长的结构，主要用来存储那些不能在前面的固定长度的d b u 瓣 m t f t 耸婚a 翻悖鲶 l4 呐 f i x e d1 e n g h td b l ks p e c i 行c i n f o r m a t i o n ( o p t l o n 叠l 、 f m t ft a p ea d d 嘴：4 翱，啪 6 删哪 ， h r r f t 却时a d d r e 褐 j4 啪 i 卸啪咖g 器；勰辩撕加砒。 一哪 i v 叠r i a b i el e n 口t hd b l ks p e c i 竹c x 啪b 一哪 l n f o r m a 玎o n ( o p t i o n 矗i 制o f l e n g l h x ：丫啪 f 沁o f ， 图5 3d e t a i l e dd e s 面p t o fb l o c k o n ea g n m e f a c t o rm a x i 辨 l 朗g m o f r s e tf l e i dn a m e t y p e s l z e o 矧，d b l kt y p eu i n t 3 24 b y f e s 4o 舳b l o c ka t t r i b u t e su i n t 3 24b y t e s 8o 肋 0 行s e lt of i f s te v e n lu l n t l 62b y t e s 1 0o o s du l n t 81b y t e 1 1 口鼬o sv e r s i o nu i n t 81b y t e 2o 铀 d i s p l a y a b i es i z e u i n t 6 48b y f e s 2 0f 铀f o r m a tl o g i c a la d d r e s su i n t 8 48b y t e s 2 8 铀r e s e n ，e df o fm 8 cu l n t l 62b _ y t e s 3 0f 勒r e s e r v e d6b y t e s 3 62 4 ，c o n t o lb l o c ki du i n t 3 2 4b 煅 4 02 a ，i r e s e n ，e d4b y t e s 4 毫! w 篓薹著耋! 謦警l 三写蠢要f ；囊主霪| 垂：毒霞翟每蓁季三奄喜娶曾 83 0 毒 翟鍪薹霎囊籼 螽i 董蚕鼋 i 髦雪襄 津套羹i 霎匿匿童毒i 匡塞霍 ! 霸霎差 星要塞娶塞 爹薰彝囊薹毒霎气话羹妻薹譬基l 匡甓i 霾 争 重要蓁 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 节是通用头结构，其它类型的d b l k 也是如此，接下来的字段是m f i l e d b u ( 自身所特有的信息，如：文件属性，修改日期，创建日期，备份日期， 文件名等等，这些是根据d b l k 的不同而不同的。 o f f s e t f l e n a m e t y p e s l z e oo c o m f l n o nb l o c kh e a 畦e r m t f d b h d r 5 2 艳s 5 23 4 ，fi l ea t r j b u f e su i n t 3 2 4 研t e s 5 63 8 bl a s tm o d i 靠c a t i o nd a t e m t f d a t e t i m e 5b y t e s 6 13 d 打c f e a t i o n0 a t e m t f d a t e t l m e 5b y t e s 6 64 舳 8 a c k u pd a t e m t f d a t e t l m e 5b y l e s 7 14 殆 l a s ta c c e s s 亡 a t e m t f d a t e t l m e 5b y t e s 7 64 翻 d l r e c 幻吖i d u l n t 3 2 4b y t e s 8 05 a 唧f i i el du i n t 3 2 4 埘l e s 8 45 4 j f i l en a m e m t f t a p e a d o r e s s 4b y t e s 5 2 2 2 数据流 图5 5m t ff i l ed b l k 数据流( d a t as t f e 锄s ) 也是m t f 的一个基础结构，它被用来封装数据， 被封装的数据一般是跟在d b u ( 的后面，我们知道d b u 【是用来包含控制 信息的，从这也可以看出d a t as t r e 锄s 是受前面的d b l k 控制的，d a t a s t r e 锄s 的结构如图5 6 所示： s 抛a mh e a 酏rs m 强m 秘e 蝴s t 陀a m 辩e a 哇甜 3 t r e a l i l c 秘e c k s u m e 0 s 1 - r e a mc h e c ( s t j 甜d 图5 6d a t as t r c 锄s d a t as 仃e 锄s 由两部分组成，数据流头部和流式数据，头部和d b i k 一 样，包含控制信息，流式数据是紧跟在其后的，它包含的是真正的数据，如 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 果拿文件系统的备份来说，它里面存放的是文件的内容。d a t as 仃e a m s 也有 很多种类，在s 骶锄h e a d e r 有一个字段可以区分它们的类型，类型可以分 为两类，一类就是和平台无关的，它包括s t a n ，c s u m ，s p a d 等，二就 是与平台有关的，与w i n d o w sn t 相关的有s n 埘，a d a t ，忙l 等。下 面我们给出d a t as 仃c a m s 的结构图，以帮助更好了解它，如图5 7 和图5 8 所示： o f f s e tc o n t e n t t y p e s l z e o o 打s t r e a ml du i n t 3 2 4b y t e s 44 ，s t r e a mf i i es y s t e ma t t r i b u t e su l n t l 62b y t e s 66 打s t r e a mm e d j af o f i n a ta t t r i b u t e su l n t l 62b y t e s 88 j s t r e a ml e n g t hu l n t 6 48b y t e s 1 6 ，舶d a t ae n c r y p t i o na l g o r i t h mu l n t l 62b y t e s 1 8f 2 d a t ac o m p r e s s i o na l g o n t h mu i n t l 62b y t e s 2 0 _ ，4 ，c h e c k s u mu i n t l 62b y t e s 图5 7s t r c 锄h e a d c r 洲s p a r 8 h e 甜n e 燃s 细b a mh e a a e r s t r e a l l s s p a r s e s p a r s m 翰煨秘e a 蕊篱 图5 8w i n d o w s9 5r e 舀s t r ys t r e a m 图5 7 是数据流的头部结构图，第一的字段i d 就是用来标识d a t as t r e 锄 的类型的，图5 8 是w i n d o w s9 5 下面的r e 百s t r ys t r e 锄的结构图，从这图 我们可以看出，他和标准流的结构差不多，就是它在s t r e 锄d a t a 部分还包 含了一个子结构而已。 5 2 2 3 文件标志 英文就是f i l e m a r k ，f i l e m a r k 主要用来作为逻辑分隔符，用于快速定位。 这里不做详细的讨论，下面给出它在整个数据集中的分布图，如图5 9 所 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 图5 1 1 资源树结点结构 从两幅图的对比中，我们可以看出它们之间存在同构性： 1 n o d e 专d l r bd b l k 2 k a f 专f i u 3 d b l k 3 s e 孕m n t 专d a t as t r e 锄 而且，d a t as t r e 锄有多种类型，这也正好和s e g m e n t 相吻合，在资源树中， s e g m e n t 也可能有多种类型，就拿全m f s 格式的文件系统来说，s e g m 胁t 就 有很多种，如：标准流，安全流，自定义流等等，由此可以看出，在结构上， m t f 格式很好的满足了我们的需要。从功能上，或者说从恢复的角度，前面 提到，我们必须保存打成扁平结构的资源树的结构信息，为恢复操作提供结 构信息，m t f 格式同样为我们提供了丰富的信息，这些信息被存放在 c o 姗o nb l o c kh e a d e r 和d b l k 的定长信息块中，下面从实现的角度来进一 步讨论m ，r f 格式的应用，这包括两个方面，第一就是把数据封装成m t f 格 式，第二就是从m ，r f 格式获得所要的数据，第一方面是通过m 1 1 礓n c o d e 算 子实现的。 5 3 1 m t f e n c o d e 这个算子的主要功能是把传来的数据封装成m t f 格式，如图5 1 2 所示： 中山大学硕士学位论文基于通用资源树模型的备份系统的设计与应用 据拉动则是根据操作来决定要什么数据，这两个词都很形象的表达了它们的 意思，对于m t f 这种比较大而且复杂的格式，我们本应把注意力放在操作 上，也就是更适合数据拉动的模式，但基于数据流的处理模式决定了要采用 数据推动的模式，这也就是为什么说