（计算机软件与理论专业论文）数据备份系统大型资源树存访模型的研究和应用.pdf

数据备份系统大型资源树存访模型的研究和应用 中山人学硕士生学位论文 数据备份系统大型资源树存访模型的研究和应用 专业：计算机软件与理论 硕士生：吉嘉 指导老师：倪德明副教授 摘要 备份系统中的资源树，是在备份过程中将所备份数据的目录结构和相关信息 ( 如文件节点在整个备份集中的偏移量，节点长度等) 以树状结构储存在备份集 中的一种数据结构。 在备份过程中建立资源树，其目的主要是为了在还原数据时提供资源预览和 针对性的还原备份集的子集，这就要求资源树具有以下几方面的特性：首先，资 源树的建立必须符合备份系统的数据处理特性( 基于文件还是基于数据流) ；其 次，由于大备份集的资源树的节点很多，结构复杂，所以构造和解析资源树时必 须控制内存占用；最后，利用资源树能快速的定位和解析出子树，返回必要的信 息给主控程序去进行还原。 本文以解决在实际研发过程中遇到的问题为出发点，在分析相关领域的研究 现状的基础上，半形式化的剖析了资源树的特性，提出了流式数据备份系统中大 型资源树的建立和分层遍历模型，叙述了模型的原理，简要地给出了资源树模型 从概念到具体类的设计过程，最后成功的在实际的项目中加以应用。 关键词：备份系统，资源树，针对性还原 数据备份系统人型资源树存访模型的研究和应用中山大学硕i ：生学位论文 r e s e a r c ha n da p p l i c a t i o no fs t o r a g ea n da c c e s sm o d e lo f l a r g e - s c a l er e s o u r c e 1 1 r e ei nd a t ab a c k u ps y s t e m m a j o r ：c o m p u t e rs o 胁a r ea n dn e o r y n 锄e ：j i aj i s u p e r 啊s o r ：a s s o c i a t ep r o d e m i n gn i a b s t r a c t t h er e s o l l r c et r e ei nt h eb a c l 叩s y s t 锄i sad a t as t n l c t u r es t o r e di nt h eb a c i 呻s e t t 1 1 a tm a d et 1 1 ec a t a l o gs 仃u c t u r ea n dr e l a t e di n f o m a t i o n ( e g t h eo 僚；e to ft h ef i l en o d e i nt h ew h o l eb a c k u ps e t ，1 e n g t ho fn o d ea n ds oo n ) i n t ot r e e - s t m c t u r ei n l ew h 0 1 e b a c k u pp r o c e s s t h em a i np u 巾o s eo fe s t a b l i s h i n gb a c k u pr e s o u r c e st 1 e ei nm eb a c l ( u pp r o c e d u r ei s t oo f f hm ep r e v i e wo fb a c l 呻r e s o u r c ea n dp e r t i n e n td a t ar e s t o r a t i o n ，w h i c hc a l l sf o r t h ef 0 1 l o w i n gc h a r a c t 谢s t i c so fr e s o u r c et r e e ：f i r s to fa l l ，t 1 1 ee s t a b l i s h m e n to fr e s o u r c e 仃e e 舢s tb ec 0 n s i s t e n tw i mt h ed a t ap r o c e s s i n gc h a r a c t e r i s t i c so fb a c k u ps y s t e m ( b a s e do nt h ed o c u m e l l to rb a s e do nt 1 1 ed a t af l o w ) s e c o n d ly ，a st l l en o d es t m c t u r eo f l a r g e s c a l er e s o u i c et i e ei sv e 巧c o m p l e xa n dl m g e ，m ep e d o m l a n c eo fb a c l ( u ps y s t e m ， p a n i c u l 砌yt l l em e m o 巧p e r f i o m a l l c e ，i n u s tb et a l ( e i li n t oa c c o u n tw h e nc r e a t i n ga i l d p a r s i n gt h er e s o l l r c e 仃e e f i n a l l y ，t h es u b s e to ft h eb a c k u ps e tc a nb er a p i d l yl o c a t e d a n dp e r t i n e n t l yr c s t o r e dw i mt h eh e l po ft h er e s o u r c et r e ei nd a t ar e s t o r a t i o n 1 1 1 i sp a p e rs e t st h es t a r t i n gp o i n to fr e s o l v i n gt 1 1 ep r o b l e m se n c o u n t e r e di nm e r e s e a r c ha 1 1 dd e v e l o p m e n to fb a c k u ps y s t e m a r e ra n a l y z i n gt h es t a m sq u oo ft h e r e s e a r c hi nr e l e v a l l td o m a i na n dm ec h a r a c t 耐s t i c so fr e s o u r c et r e e ，t h ep 印e rp u t s f o r w a r da i le s t a b l i s h m e n ta 1 1 d1 1 i e r a r c h i c a lt i a v e r s a lm o d e lo fl a 唱e - s c a l er e s o u r c et r e e i nb a c k u ps y s t 锄o fd a t as t r e 锄o n 衄sb a s i s ，m em o d e l i sd e s i 盟e d 仃o ma b o v et o b e l o w 舶mah i 曲- 1 e v e lc o n c 印t i o nv i e wt oc l a s s f i n a l l y ，ap r o t o t y p ei ss u c c e s s 如1 l y 数据各份系统人型资源树存访模型的研究和应用中山人学硕上生学位论文 a p p l i e di np r a c t i c a lp r o j e c t s k e y 、r d s ：b a c l ps y s t e m ，r e s o u r c e 仃e e ，p e r t i n e n tr e s t o r a t i o n 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名屯岳 日期：知口缉s 月妒日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即： 学校有权保留学位论文并向国家主管部门或其指定机构送交论文的 电子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许 论文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编 入有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论 文。 学位论文作者签名：焉磊导师签名：偬隍硎 日期：如。譬年s 月冲日日期：跏g 年s 月净日 数据备份系统大型资源树存访模型的研究和应用中山人学硕i ：生学位论文 1 1 数据备份系统概述 第1 章引言 数据是信息时代的一大特征，信息化社会中，数据是政府和企事业单位的命 脉。在网络和信息化高速发展的今天，数据备份系统中处理的数据，有下列特点： 1 ) 数据量激增。 2 ) 数据类型复杂多样。 3 ) 数据的结构化。 4 ) 数据集中化。 数据备份的实质是，备份= 拷贝+ 管型1 1 ，对网络数据备份系统我们给出更 加详细和准确的定义【2 ，3 1 ，即： 备份= 拷贝+ 变换+ 传输+ 存储+ 管理 换句话说，备份系统的功能就是对各种需要备份的资源使用对应的方式进行 拷贝，然后根据需要对原始数据进行一系列数据变换，通过不同层次的网络传输 协议和通道技术传输到介质，最后以适当的存储结构存储在选定的介质上，并且 整个流程以及相关的资源都处于备份中心的集中管理调度之下。 1 2 数据备份系统的相关概念 1 2 1 备份对象和备份集 备份对象泛指网络环境中任何需要保存的信息。如一个局域网子网中的所有 文件服务器，一台p c 机的文件系统，一个服务器上的某个表空间等。本文是指 备份客户中所有需要备份的数据【4 1 。 备份对象可分为三类： 数据备份系统人型资源树存访模型的研究和应用 中山人学硕士生学位论文 ( 1 ) 元数据对象( m e t a d a t ao b j e c t ) ：实体属性对象。记录了实体数据，日 志数据的各种属性：如位置，大小，最后修改时间，任意两个对象之间 的关系等。 ( 2 ) 实体数据对象( e n t i t yd a t ao b j e c t ) ：实体对象。是用户真正所关心的数 据，需要备份的数据。 ( 3 ) 日志数据对象( l o gd a t ao b j e c t ) ：记录了所有元数据，实体数据的所有 改变信息。 在数据备份系统中，我们把对一个备份对象进行一次备份得到的一个结构集 叫做一个备份集。备份集是对备份对象进行选择，移动，格式转换等操作之后得 到的目标对象集，是运行备份命令生成的物理文件的逻辑组合【5 】。例如，对一个 磁盘所有文件进行备份，得到一个归档文件，我们称这个归档文件为一个备份集。 对备份集的管理，是数据备份系统中十分重要的一环。为了对备份集进行集 中管理，我们需要在归档结构中记录此次备份的信息。例如，差备还是全备，备 份时间等等。其次，我们需要记录当前备份运行的参数信息，便于系统在零配置 的情况下，对备份集进行恢复操作。最后，为了达到若干目的，譬如，恢复时选 择备份集的子集进行维护，对备份集进行搜索等等，我们需要在备份集中追加一 些辅助文件。 1 2 2 备份对象资源树 备份对象资源树是备份集中一种重要的辅助文件，属于元数据对象。资源树 就是将备份数据源的目录结构层次化的记录到特定格式的文件中，以方便用户查 看备份集的目录结构和提供针对性地恢复某一个备份子集的功能。 对于流式数据备份系统来说，资源树的构造或访问一般来说是和数据备份和 还原过程同步的，若将这种类型的数据备份系统应用到网络上，考虑到网络数据 备份软件受到备份数据介质类型和网络条件限制比较大，就更加要求构造和访问 资源树时要在不损失数据备份特性和数据处理特性的前提下尽可能的提高时间 和空间效率。 所谓数据备份特性，是指数据源的数据存访特性( 比如是磁带式单向存访还 数据备份系统人型资源树存访模型的研究和应用中山大学硕：l 生学位论文 是磁盘式随机存访) ，以及备份系统数据处理特性( 比如是基于文件的还是基于 数据流的) 。而提高数据资源树构造和访问的时间和空间效率，是指在待备份数 据源文件数目非常大( 如几百万个文件) 时，怎样既能在备份时快速建立资源树 和在还原时快速的访问资源树，同时又能将建立和访问的磁盘和内存开销降到数 据备份可以接受的程度。 综上所述，对于数据备份，希望在对资源树操作时能达到以下特点： 1 不损失数据备份特性 2 与备份、还原操作同步 3 高效存访，低时间和空间开销 1 3 本文背景和写作内容 广州威腾网络科技公司( v i t o n ) 是国内专业的网络备份管理软件供应商， 多年来专注于网络数据备份管理软件的开发，提供高性能的网络数据备份软件产 品和专业的服务。 本文是作者在参与该公司的p r o r e c o v e r y 数据备份软件的设计研发的过程 中，根据网络数据备份系统面临的实际问题和产品研发中的具体需求，提出的备 份系统大型资源树的建立和分层遍历模型，对该模型进行研究和分析，并在此基 础上，设计并实现了它的一个原型。 全文共分六章。第一章对数据备份系统及数据资源树进行概述，并说明本文 写作背景和写作内容。第二章通过分析数据备份特性，说明数据备份系统对自组 织结构的需求，然后点出资源树在备份系统自组织结构中的作用，接着分析了国 内外相同相似领域的研究和发展概况，最后简要介绍了p r o r e c o v e r ) r 备份系统的 运行框架。第三章首先通过分析，指出了在数据备份系统中传统的d o m 和s a x 模型在处理x m l 文件时的不足，兼之考虑到数据备份系统对x m l 资源树的处 理特性，故提出了在节点先序有序的前提下在外存中流式建立资源树文件的模 型，并通过对两种方案的分析和对比，最终选择了其中一种较优模型，之后又对 模型的存储效率做了一定的优化，以使模型的性能达到比较好的水平。第四章在 第三章的基础上，讨论了在数据还原时的资源树分层遍历方法，提出分层遍历的 3 数据得份系统大型资源树1 竽访模型的研究和应用中山人学硕： ：生学位论文 概念并实现了一个方法的原型，然后将原型应用到资源树的预览界面上，并对界 面从用户角度进行改进，最后将模型与s a x 模型进行提取资源子树的性能对比， 并对比较结果做了详细的分析。第五章从备份集管理的资源树合并需求出发，首 先明确了资源树外存合并算法的前提，接着定义了两个偏序关系，提出了虚拟归 并树的概念来解决节点偏移量重置问题，最后阐述了外存合并算法的原理并用实 例加以说明。第六章总结与展望。 4 数据备份系统人型资源树存访模型的研究和应用 中山大学硕上生学位论文 第2 章备份系统的自组织结构需求及应用举例 2 1 自组织结构的相关概念 2 1 1 自组织结构 数据的自组织结构，是指将数据按照一定的结构进行封装，包装后的数据本 身就包含了元数据和实体数据，使得该数据能独立于应用系统进行有序树的构造 和数据的重构。 例如，本文后面将要涉及到的x m l 可扩展标记语言就是一种自组织的数据 结构语言【6 1 。x m l 文档通常包含一个文档类型声明，因而x m l 文档是自描述的。 不仅人能读懂x m l 文档，计算机也能处理。x m l 表示数据的方式真正做到了 独立于应用系统，并且数据能够重用。x m l 文档被看作是文档的数据库化和数 据的文档化。 2 1 2 备份系统对自组织结构的需求 数据备份系统的处理对象是数据库中的数据，所谓备份，就是把数据库复制 到转储设备的过程。其中，转储设备是指用于放置数据库拷贝的磁带或磁盘。通 常也将存放于转储设备中的数据库的拷贝称为原数据库的备份或转储。 敦据库转储设备 图2 1 数据的备份 5 数据备份系统大型资源树存访模型的研究和应用 中山人学硕i ：生学位论文 o r a c l e 公司在对备份概念的定义中，将备份分为物理备份和逻辑备份两种。 物理备份是将实际组成数据库的操作系统文件从一处拷贝到另一处的备份过程， 通常是从磁盘到磁带 7 1 。可以使用操作系统命令进行数据库的物理备份。逻辑备 份是利用s o l 语言从数据库中抽取数据并存于二进制文件的过程。数据库逻辑 备份是物理备份的补充。 然而，不管是哪种备份，其备份结果备份集的数据结构都是固定的，不论 备份系统怎样更新升级，它在还原时都是通过固定接口去读取备份集结构，解析 出其中的信息进行还原。而自组织结构将元数据与实体数据按照一定的结构进行 封装，应用到备份系统中，可以使备份集独立于系统，让使用者能后开发出各种 不同的程序去处理这些备份集。 还原程序$ 还 还原 还原挫序 图2 2 数据集的独立性 此外，在恢复时，根据不同的需求，用户可能会进行数据的完全还原或者针 对性还原。所谓完全还原，就是将指定的备份集中的全部数据完全拷贝到需要还 原的数据库中，而针对性还原，是用户从备份集结构树中选择一棵子树进行部分 数据的恢复。两种还原模式都需要从备份集中得到数据实体的结构信息，( 比如 各个节点在备份集中的偏移量) ，针对性还原更是需要在数据恢复前得到备份集 资源树的部分或完全预览，这些都需要从备份集结构的元信息中取得。 数据备份系统人型资源树存访模型的研究和应用中山大学硕上生学位论文 备份集 图2 3 完全恢复和针对性恢复 解析备份集 还原的数据 因此，我们可以看出，数据备份系统需要其备份集具有完善的自描述功能。 本文正是从这种需求出发，提出数据备份系统在对大数据集备时的大型资源树的 建立和遍历模型，该模型可以帮助数据备份系统建立一种完善的自组织备份集结 构，并在不损失备份特性的前提下较大程度地优化了备份和恢复的性能。 2 2 资源树模型的研究及应用现状 现在已经应用成熟的数据处理软件，如w i n z i p 和w i n r a r ，资源树的应用已 比较普遍。z i p 格式中，在文件末尾位置有一个压缩文件的t o c ( 1 a b l eo f c o n t e n t ) 表，所谓t o c 表，是在电子文件里由结构化数据构成的一张表，它的目的是为 了快速定位【8 】：如果想找文件中的某一内容，可以先查t o c ，知道感兴趣的内容 在文件的什么位置，直接跳过去就行了。在z i p 格式中，通过这个t o c 表，z i p 文件可以实现快速定位文件，实现了随机访问功能。此外，t o c 表还应用于运 用a v i 、i 洲等多媒体格式，当用户拖动进度条时，程序就会通过t o c 去定位 数据。 r a r 格式原本没有t o c 的结构【9 】，原来的毗啵格式是顺序存访的。其随机 访问能力不如z i p 格式。而现在，在一些比较成熟的r a r 格式软件中( 如 w i n r a r ) ，已经加入了类似于t o c 的结构，并对用户可见。 数据备份系统大型资源树存访模型的研究和应用中山人学坝： ：生学位论文 文件命令。工具收微q ) 嘲帮助咀) 9 国蓟幽国国 添加解压到潮试查看删除查找 国自翟雪v 信息 端瘸毒 注释傈护 穆 自解压格式 漕一1 川r u 滢b t r u 2 r i n a e rt x t 为r a “et 】【t 国c h 吣e l 。x m l 2 2 5 8 “81 ，t 8 钆3 6 tt i i i 丑 r 压缩文件 4 1 3 8 4 趁4 1 3 5 ，瞄f i l i 矗地压缩文件 1 7 6 文本文档 约s 2 3 5 文本文档 32t2瑚ld o c m e n t 2 0 一4 一1 9t 2 0 0 8 一1 9i 2 0 一卜2 01 2 0 0 t 一9 5i l ：1 4 约一1 一1 91 图2 4w in r a r 的资源目录结构 比较于以上两个数据压缩软件，p r o r e c o v e r y 的资源树除了能实现和t o c 一 样快速定位和随机访问功能，还通过分层遍历实现了类似于w i n d o w s 资源管理 器浏览界面，相对于w i i 亿i p 的全文件显示和w i n r a r 的单层目录显示，这样的 显示模式显然更加符合用户的习惯，也更加直观易用。 2 3p r o r e c o v e r y 简介 p r o r e c o v e r y 数据备份软件是广州威腾网络科技公司( v i t o n ) 自主研发， 独立定义了备份数据存储结构和一套算子运行框架的数据备份软件，可应用于本 地和网络数据备份。该软件最大的特点是把数据备份和还原操作插件化，插件接 口协议化，提供了一部分数据处理功能，实现了算子的升级和校验。 2 3 1p r o r e c o v e r y 系统运行框架 本文的研究对象是基于p r 0 r e c o v e r y 数据备份系统的，所以，有必要先介绍 一下该系统的体系结构和运行框架，是本文的研究对象特征更清晰。 数据备份系统大型资源树存访模型的研究和应用 中山大学硕士生学位论文 撺程序 算子链 写算子 介质服务器 确一一督构 图2 5p r o r e c o v e r y 运行框架 p r 0 r e c o v e 巧是一个基于单数据流多指令机制的数据备份系统，所谓单数据 流多指令机制，是指备份系统的处理对象是一条数据流，数据流由读算子从数据 源读出，经过主控程序的规划，依次流过数据处理算子链，受到算子的数据处理 “指令”，数据经过处理后成为一个备份集，最后由写算子写入备份介质的一种 机制。 下图反映了p r o r e c o v e 巧系统的主控协作过程。 p t u g t n i n t t 图2 6 主控协作图 2 3 2p r o r e c o v e r y 备份系统的备份集结构 写 p r 0 r e c o v e 巧系统的数据备份集结构叫做u d s ( u n i v e r s a ld a t as 仃u c t l l r e ) 结 构【1 0 】，简单来说，u d s 结构就是备份集的数据结构，其结构图如下： 燃醅 数据备份系统大型资源树存访模型的研究和应用中山人学硕士生学位论文 | ghd a t af | ， 删明gt 图2 7u d s 结构示意图 如图所示，一个完整的备份集由g h ，d a t a 和g t 组成，其中，g h 代表 u d s 的头结构，存放用于备份恢复代理和变换模型需要的数据；备份恢复代理 在调用变换模型的时候，填充好代理相关的元数据部分，而与变换模型相关的部 分，由变换模型根据相关信息进行填充。具体说来，与变换模型相关的元数据包 括：所使用的算子的名称、版本号、参数，加载算子的顺序等。 d a t a 是实体数据，是指那些描述数据流信息和变换处理信息的数据，实体 数据是备份恢复的数据对象本身，是无结构的流序列。 g t 表示尾结构，用于变换模型，主要存放算子处理后的结果信息，包括副 作用数据和一些统计信息等。尾结构在算子对数据块进行处理后，由变换模型填 写。 g h 和g t 统称为元数据，元数据使数据流在一定程度上实现自描述，他的 最主要作用是恢复数据时的索引重建。而本文所讨论的资源树，就位于u d s 的 g t 部分。 2 3 3 资源树模型在p r o r e c o v e r y 中的应用 本文所讨论的资源树模型，是基于x m l 语言的。总的来说，资源树就是将 备份的目录信息以x m l 文件的形式保存下来，同时在x m l 文件中加上一些节 点信息( 如节点在备份集中的偏移量，节点文件长度等等) 和节点之间的层次 关系信息，用于还原时重构有序树。 p r o r e c o v e r y 在备份数据时数据是流式处理的，所以资源树模型的x m l 资源 文件也是流式建立的，在数据流流过资源树算子时一次性写入文件内容，而不会 对资源树的节点进行任何事后的添加删除操作，即对资源树不进行维护，这是因 为资源树的建立本身也是由备份系统中一个算子完成的，所以算子的数据处理模 式要符合整个系统的备份特性。 算子建立好资源树文件后，主控程序会将文件追加到u d s 的g t 部分。还原 1 0 数据备份系统人型资源树存访模型的研究和应用中山大学硕- 上生学位论文 时，主控程序会首先定位到资源树文件，将文件解析为一个目录树，返回给u i 界面，从而提供给用户一个资源预览。用户可以将资源树从根节点以类似于 w i n d o w s 资源管理器的方式逐层展开，随机访问树节点。 资源树预览功能让用户可以选定子树进行还原操作，资源数模型会利用一个 迭代器将还原所需要的子树根节点偏移量和长度信息返回给主控程序，主控程序 再调用其他逆算子进行数据的迭代还原。 同时，考虑到对于一个大型备份集，其资源树有数目巨大的节点，若将资源 树的处理全部放入内存，对于网络数据备份系统或一些服务器，其内存占用量是 不可接受的。p r 0 r e c o v e 巧数据备份系统也不例外，在p r o r e c o v e d ，中，为了尽 可能提高内存使用效率，绝大部分资源树的建立和遍历操作被放到外存中进行。 2 4 总结 通过这一章，可以初步总结出，本文所讨论的资源树模型，需要达到以下几 个要求： 资源树基于x m l 格式 符合备份系统的流式备份特性。 外存流式建立资源树，不对资源树节点进行维护 能实现资源树节点的随机访问( 跳访) 。 支持还原前的资源树预览 控制和降低备份、还原时系统的内存开销。 考虑到备份集的管理需要，要求模型支持资源树合并。 在接下来几章里，本文将详细论述资源树的建立及分层遍历模型，并对不同 的方案进行多方面的比较，从而较大限度的优化模型。最后，本文将会实现一个 模型的原型。 数据备份系统大型资源树存访模型的研究和应用中山人学硕士生学位论文 第3 章利用x m l 资源树存访模型建立大型资源树 3 1x m l 资源树存访模型概述 通过以上一章的论述可知，本文所探讨的x m l 资源树存访模型，希望能够 做到以下几点： 1 基于通用的x m l 语言 2 符合数据备份的流式特性，资源树流式建立，对资源树节点不进行维护。 3 支持节点随机访问，支持资源树预览，支持资源树合并。 4 低内存资源消耗。 x m l 是现在最流行的通用标记语言，用x m l 作为资源树的模型语言，使得 资源树文件具有很强的通用性，利用现在很流行的x m l 解析工具，可以很方便 的解析资源树文件。 低内存资源消耗和高效率存访是本文探讨的模型的亮点。与传统的利用 d o m 建立x m l 文件形成鲜明对比，本文在文件节点有序的前提条件下，将会 提出外存的x m l 资源文件建立方法，并利用文件指针回写在资源树节点中保存 节点关系。这样一来，不仅降低了系统内存资源消耗，在解析资源树文件时也可 以通过文件偏移量跳转实现资源树节点的随机访问。 在接下来的几章里，本文将围绕低内存资源消耗和高效率存访两大技术要 点，以分析比对的形式论述资源树存访模型，同时简要的给出模型的实现。 3 2x m l 简介 本文讨论的模型是基于) ( m l 语言格式的，有必要先简要介绍一下x m l 语 x m l = e x t e n s i b l em a r l ( u pl a n g u a g e 可扩展标记语言，由万维网协会 数据备份系统人型资源树存访模型的研究和应用中山大学硕j ：生学位论文 w 3 c ( w b r l dw i d ew 曲c o n s o n i u m ，1 9 9 4 1 0 成立，由w 曲的发明者t i m b e m e r s - l e e 领导) 于1 9 9 8 年制定的一种基于文本的数据描述语言的语法通用标 准，可用来定义数据的结构、种类、属性和内容的具体规范。x m l 被誉为因特 网上的世界语，其主要应用领域有：数据交换、w 曲发布和分布式计算等，是新 万维网w 曲的基础【l l 】。 3 2 1 l 的先进特性 x m l 同h t m l 一样，都来自s g m l ( 标准通用标记语言) 。s g m l 是一种在 w 曲发明之前就早已存在的用标记来描述文档资料的通用语言。但s g m l 十分 庞大且难于学习和使用。鉴于此，人们提出了h t m l 语言。但近年来，随着w 曲 应用的不断深入，h t m l 在需求广泛的应用中已显得捉襟见肘，有人建议直接使 用s g m l 作为w 曲语言。但是s g m l 太庞大了，学用两难尚且不说，就是全面 实现s g m l 的浏览器也非常困难。于是w 曲标准化组织w 3 c 建议使用一种精 简的s g m l 版本- x m l 。x m l 与s g m l 一样，是一个用来定义其他语言的 元语言。与s g m l 相比，x m l 规范不到s g m l 规范的1 1 0 ，简单易懂，是一门 既无标签集也无语法的新一代标记语言。 x m l 继承了s g m l 的许多特性，其主要先进特性有： 可扩展性。x m l 允许使用者创建和使用他们自己的标记而不是h t m l 的有 限词汇表，用户可自定义元素、属性和其他文档成分，伸缩灵活。企业可以用 ) a l 为电子商务和供应链集成等应用定义自己的标记语言，甚至特定行业一起 来定义该领域的特殊标记语言，作为该领域信息共享与数据交换的基础。 灵活性。h t m l 很难进一步发展，就是因为它是格式、超文本和图形用户界 面语义的混合，要同时发展这些混合在一起的功能是很困难的。而x m l 数据文 档( 卡x m l ) 和显示设置( c s s f o ) ( s l t + h t m l ) 彻底分离。易进行数据管理和 内容检索，而且同一数据可以有多个视图。 第三是自描述性。基于文本，自带( 定义文档结构和数据类型的) d t d 或 s c h 锄a 。x m l 被设计用来描述数据，重点描述什么是数据以及如何存放数据等； 而h t m l 是被设计用来显示数据的，重点显示数据以及如何更好地显示数据； 1 3 数据备份系统大型资源树存访模型的研究和应用中山大学硕士生学位论文 h t m l 与显示信息相关，x m l 则与描述信息相关 1 2 】。 除了上述先进特性以外，x m l 还具有简明性。它只有s g m l 约2 0 的复杂 性，但却具有s g m l 功能的约8 0 。x m l 比完整的s g m l 简单得多，易学、 易用并且易实现。x m l 支持世界上几乎所有的主要语言，并且不同语言的文本 可以在同一文档中混合使用，应用x m l 的软件能处理这些语言的任何组合。所 有这一切将使x m l 成为数据表示的一个开放标准，这种数据表示独立于机器平 台、供应商以及编程语言。它将为网络计算注入新的活力，并为信息技术带来新 的机遇。目前，许多大公司和开发人员已经开始使用x m l ，包括b 2 b 在内的许 多优秀应用已经证实了x m l 将会改变今后创建应用程序的方式。 从1 9 9 8 年开始，x m l 被引入许多网络协议，以便于为二个软件提供相互通 信的标准方法。简单对象访问协议( s o a p ) 和x m l i 冲c 规范为软件交互提供了 独立于平台的方式，从而为分布式计算环境打开了大门。几乎所有主要的软件厂 商都支持s o a p 。s o a p 的快速成功史无前例地提高了软件的互操作潜力。当今， w e b 服务革命正在兴起，而s o a p 正是其基础协谢2 5 1 。 正是由于x m l 语言的这些先进特性，将x m l 语言作为模型的语言是非常 好的选择。 3 2 2 传统x m l 处理模型 在利用x m l 处理数据时，选用何种处理模型是一个非常重要的问题，实际 上，长久以来，人们主要在d o m ( d o c u m e n tc i b j e c tm o d e l ) 模型和s a x ( s i m p l e a p if o rx m l ) 模型之间选择。 d o m 模型 d o m 模型是文档驱动的，在处理d o m 的时候，我们需要读入整个的l 文档，然后在内存中创建d o m 树，生成d o m 树上的每个n o d e 对象。d o m 模 型让使用者可以随机的访问x m l 树上的某一个节点，也可以很方便的添加和删 除节点。 但是，d o m 的缺点也是非常明显的，d o m 解析器会把所有的x m l 文档全 部加载到内存中，如果x m l 文件非常庞大，那么这样的解析器会耗尽内存，导 1 4 数据备份系统大型资源树存访模型的研究和心用 中山大学硕士生学位论文 致内存益处异常。 s a x 模型 s a x 在概念上与d o m 完全不同。首先，不同于d o m 的文档驱动，它是事 件驱动的，也就是说，它并不需要读入整个文档，而文档的读入过程也就是s a x 的解析过程。所谓事件驱动，是指一种基于回调( c a l l b a c k ) 机制的程序运行方 法。s a x 解析一个节点后回调一个方法，把该节点相关信息传送个调用者，然 后丢弃这些信息，继续解析下一个节点。正是这样一个机制，使得s a x 占用内 存很少，它不会预存储整个x m l 文档，也不会在解析后保存任何解析结果。 但是，在这种基于事件的驱动模式下，s a x 只提供给使用者层次遍历的方式， 也不允许对v i l 文件随机存取，如：当前解析到第3 个e 1 e m e n t ，此时程序无 法得到第5 个e l e i i l e m 的信息，因为还没有解析到第5 个e l e m e n t ；同样也无法 得到第1 个e 1 e n l e i l t 的信息，因为已经丢失了。当然可以通过声明变量保存解析 过的数据，但这如同手动在内存中构造了某种数据结构，一般都是树型结构。 由此可以看出，d o m 和s a x 模型在处理x m l 时的特点是互补的，但是都 不太适合数据备份系统中的x m l 资源树的处理，原因有两点：第一，数据备份 系统处理的数据集一般都是很大的，其资源树的节点很多，结构复杂，不可能全 部放入内存处理；第二，数据备份系统需要在还原时为了提供资源预览和子树提 取，需要在资源树上不断的进行节点的随机访问。因此，想要建立一种既能使随 机访问节点时资源消耗降低也能实现较高的访问效率的模型，必须重新考虑其他 途径。 3 3 备份时利用x m l 资源树存访模型构造资源树 3 3 1 常用x m l 文件创建方法的对比分析 先介绍一下在创建一个x m l 文件时常用的几种方式： 1 ) 利用d o m ： d o m 的主要功能是访问和维护l 文件13 1 ，但它也可以用来建立x m l 文件，具体方法是先利用d o m 模型的m l d o m d o c u m e n t 构造一个根节 数据备份系统大型资源树存访模型的研究和应用中山大学硕上生学位论文 点，然后根据外部节点信息不断的生成节点，调用m l d o m n o d e 或 m l d o m e l e m e n t 的插入方法将节点插入到d o m 树上，最后在内存中构造 出一棵x m l 树。 2 ) 利用x m l w r i t e r ： x m l w d t e r 类是n e tf r 锄e w o r k2 o 中的一个抽象基类，提供只进、只 写、非缓存的方式来生成x m l 流，可以用于构建符合w 3 c 可扩展标记语 言( x m l ) 1 0 ( 第二版) 【1 4 1 建议和x m l 中的命名空间建议【1 5 1 的x m l 文 档。 与d o m 模型不同，利用该类提供的w 订t e s t a r t e l e m e n t ( ) ， 、n t e e n d e l e m e n t ( ) ，w n t e s t a i t a t t m u t e ( ) ，、h t e e n d a t t r i b u t e ( ) 等接口，可以以 只进方式在外存中构造x m l 树，由于是非缓存的，所以l t e r 不支持 文件的回写。 3 ) 利用文件指针 既然x m l 是一种纯文本格式的文件，那么当然也可以直接使用文件流 书写x m l 文件，可以定义函数，根据输入外部节点的信息和层次关系，按 照x m l 的格式用文件指针书写x m l 文件。与x m l 州t e r 不同的是，文件流 支持查找定位功能，可以让文件指针在文件中定位到任何位置，也就是说， 文件指针支持数据的回写。 前面已经讨论过，数据备份系统处理的数据集通常是很大的，其对应的资源 树文件也很大( 一个有几百万个文件的备份集，其资源树文件可能达到几个g b 的大小) ，不能忍受将这么巨大的资源树装载到内存进行处理，而d o m 模型的 x m l 树构造过程完全在内存中进行，所以，d o m 模型不适合用来建立备份资源 树。 另一个方面，由3 1 小节讨论的资源树存访模型的特点3 可以知道，要实现 节点的随机访问和资源树的合并功能，就必须在建立资源树时，在资源树节点中 加入节点的层次关系信息，但是，并不是任何关系信息都能在写入节点的同时确 定( 比如，一个节点的兄弟位置只能在它的兄弟被写入文件后才能得出) ，所以， 要求模型或方法在建立资源树时能随时回到前面的节点进行一些信息的更新，即 支持回写。由此得知，x m l t e r 类也不适合用来建立备份资源树。 数据备份系统大型资源树存访模型的研究和应用 中山人学硕十生学位论文 文件流指针不仅能在外存中建立x m l 文件，而且支持回写，故而，本文选 用了这种方式来建立x m l 资源树。 3 3 2 外存构造x m l 资源树的前提条件 因为本文的模型是基于l 的，所以首先有必要分析一下l 语言的格 式。下面是一个完整x m l 文件的例子： a 2 3 3 4 2 s i c h u a j l t x t p o d d o c c d p i c p d f b 1 6 7 9 3 m i n o k i c h i a v i p i c a 6 5 7 9 j p g w w w s i n a c o m d o c x 数据备份系统人型资源树存访模型的研究和应用中山人学硕士生学位论文 可以看出，一个完整的x m l 文件由文件头的文件处理命令p i ( p r o c e s s i n g i n s t m c t i o n s ) 和文件实体( b o d y 或e l e m e n t ) 组成，文件处理命令可以包含x m l 的 版本信息，处理的字符集( e n c o d i n 曲等文件处理信息。p i 不是本文讨论的范围， 故只简单介绍一下。 x m l 的核心是文件的实体( b o d y 或e l e m e n t ) ，可以清楚地看到，订l 文件 从头到尾可以看成一棵有序树【1 6 】，利用元素的开始和结束标签，l 描述出了 树上各个节点之间的层次关系，因此，一个x m l 文件可以映射到唯一的一棵树 ( 以下简称x m l 树) 。 同时，注意到如果把x m l 文件从头到尾遍历一次，对应的x m l 树的遍历 方式正好是先序遍历【1 7 1 。从这一点可以想到，若要建立一个x m l 树，如果能以 先序遍历的方式得到其节点信息，则可以一次性的完成x m l 文件的写操作而不 需要进行节点的插入删除等操作。 综上，只要节点顺序是先序有序的，x m l 的建立过程就完全可以在外存中 完成，而另一方面，将x m l 资源树文件的建立过程放到外存实现，无疑大大降 低了内存开销，这个特点对数据备份软件处理大型数据集是十分有利的。 3 3 3 数据备份时的文件节点顺序 在p r o r e c o v e w 系统中，对数据源节点的访问满足以下特点： 所有节点都会被访问且只被访问一次 树的叶结点为最终要处理的数据，树的分支结点表示结点之问父子关系。 在此前提下，我们若对数据源的树状结构进行先序遍历，会得到一个先序遍 历的节点序列。例如，对下图的数据源树状结构进行先序遍历，得到的节点序列 如下： 数据备份系统大型资源树存访模型的研究和应用 中山大学硕士生学位论文 ( a ( b ( c ，d ( f ) ，e ) ) ，c ( h ( i ，j ) ) ) 图3 1 先序遍历得到的节点序列 到此，我们就明确了在p r o r e c o v e r y 数据备份系统中的节点访问是先序有序 的。即对两个相邻的节点来说，后处理的节点一定是先前处理节点的孩子或者兄 弟。同时，注意到先序遍历的节点序列可以看成一个节点流，可以流式的传递给 资源树算子，完全符合3 3 1 中的结论，故而在外存流式的建立) ( 1 l 资源树是 完全可行的。 3 3 4 节点的闭包 资源树文件是x m l 格式的，自然地，文件中会涉及到各个节点的闭包如何 处理的问题。 由于数据备份是文件节点是先序有序的，即：对任意彳、bcs ( 么，b 相邻且 为文件节点d d e ，s 为删黝舾丁) ，假设4 在b 之前处理，则只存在两种情 况： b c4 ，即b 为爿的孩子 召cn m f ( 彳) ，即曰为彳的兄弟 在x m l 文件对应结构中，彳的实体部分总是出现在b 的实体部分之前，对 第一种情况，b 在彳之前闭包，对于第二种情况，曰在彳之后闭包。 所以可以看出，资源树模型在写x m