（计算机软件与理论专业论文）文件系统备份中目录树处理算法设计与实现.pdf

中山大学硕士学位论文 文件系统各份中目录树处理算法设计与实现 文件系统备份中目录树处理算法设计与实现 计算机软件与理论 硕士生姓名：肖克辉 指导老师：李磊教授 倪德明副教授 摘要 文件系统备份过程有一组算法或模块要对目录树进行迭代或递归处理，主要 包括：一、将被备份的目录树同步到备份服务器中去作为备份索引，以简化g u i 开发，并支持在介质离线情况下对备份索引的访问：二、在数据实际拷贝前根据 用户定义的一棵选择树和文件系统当前目录树生成一个待备份的文件列表：三、 在增量备份时，合并当前备份索引和历史备份索引，以便用户根据时间点来进行 恢复。这些算法或模块基本上可以归纳为树的存储、树的模式匹配和树的合并等 问题。 由于实际文件系统文件数目往往很大，在实现上述算法时必须考虑到内存空 间使用上的问题：如果算法按照树结构递归，则会导致内存消耗过大，会直接影 响到软件的现实可用性。针对上述问题，本文研究对树结构按照结点顺序进行流 式处理的技术，以降低内存开销。 在实际实现中，考虑到目录数据索引结构要易于共享和表现，目录树及各个 结点的属性以x m l 格式表示。在算法上，迭代处理模式和流式处理模式分别对 应为基于d o m 的模式和基于s a x 的模式。本文设计并实现了两种模式的算法， 并比较了各自的优缺点。 关键词：数据各份、文件系统、流式处理、目录树、s a x 中山丈学硕士学位论文文件系统备份中目录树处理算法设计与实现 d e s i g na n d r e a l i z a t i o no ft h ep r o c e s s i n ga l g o r i t h m so f c a t a l o gt r e eb a s e do nt h eb a c k l l po f l i i es y s t e m c 叩u t e rs o f l w a r ea n dt h e o r y n 锄e ：x i a 0 k e h l l i s u p e i s o r ：p r o f l i ，l c i ；a s s o c i a t ep r o f n i d 锄i n g a b s t l 。a c t t h e r ee x i s t sag m l l po fa l g o r i t l l m sa n dm o d m e sw l l i c ha r eu s e dt oi t e r a t ea 1 1 d p r o c e s st h ec a t a l o g 订e er c c u r s i v e l y ，1 1 l e yi n c l u d ea sf o l l o w s ：f i r s n y ，w es y n c h m l l i z e t l l ec a t a l o gt r c eo fb a c k u pt 0b a c k u ps e r v e r ，t h e nu s ei t 踮b a c k u pc 削o gt os i m p l i 匆 t h ed e v e l o p m e mo fg u i ，s ow ec 蛆a c c e s s 山eb a c k u pc a t a l o gu n d e r 也ec i r c u m s t a ：n c e o fo 搏l h l c ；s e c o n d l y ，w ep r o d u c em e1 i s tw h i c hi n c l u d e st h ef i l e sa n dd i m 妇 e s 谢l l b eb a c k u pb a s e do nt 1 1 es e l e c t i o n 订e ew h i c hi sd e f i n c db yu s e rb e f o r et l l ea c t i o no f c o p ya n d 协ep r e s e mc a t a l o gt r e eo fn l es y s t e m ；m i r d l y ，i nt h ep r o c e s so fi 蝌锄e 删 b a c k u p ，w em e r 胪也ep r e s e n tb a c k u pc a 协l o ga n d 也ep r 州i o u so n c ，b y 也i sw a y 、1 s e r c a i lr e c o v e rd a t aa c c o r d i n gt 0t h e 岫ep o in l t h ea i g o r i m m sa n dm o d u l e sa b o v ec a n b ei n d u c e da st h es t o r a g e0 ft r e e t l l ep a t t e mm a t c h j n go f 打e ea n dt l l em e 删n ga c t i o n o f t r e e b e c a u s eo fl a r g ea i i l o u n t so ft l l en l e sa i i dd i r e c t o r i e si nm en l es y s t e m ，、em u s t c o n s i d e r ( h eo c c u p a “c yo fm e m o r yi nt h er e a i i z a 主i o no f 也ed i g o r i t h r n s i fw el l s et h e r e c u r s i v ca l g o 小h m so f 仃e e ，i t 谢l lr e s u ni nt h el a r g ec o n s u m p t i o no fm e m o r ya n d a 眠t 也ea v a i l a b i l i t yo f l eb a c k u ps y s t c i n i no r d e rt or e s o l v e1 l l ea b o v ep r o b l e m s ， t h i sp a p e rr e s e a r c h e sm a i l l l yo n 也es i n gt e c h n i q u e so f 订e ea c c o r d i n gt o 血e s e q u e n c eo f i t sn o d e s ，i tc a i ld e c r e 舔et l l eo c c u p a n c yo f m c m o ， 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 c o n s i d e r i n go f 1 ca c c e s s i b i l i t i e so fs h a r ea n de x p r e s s i o n ，w er e p r c 8 e n tt h e c a 协l o g 缸a l l dt l l ea t 啊b u t e so fe 哪n o d ea st l l ef o l m a to f x m ld l 】r i n gr e a l i 蹦t i o n i n 沪e c to fa l g o r 油m ，i t e r a t i v ep a n e mo fp r o c e 8 s i n g 锄ds 廿e 锄i n gp a n e mo f p r o c e s s i n gc o r r e s p o n dt ot h cp a t t e mb a s e do nd 0 ：ma n dt l l ep a t t e mb 船e do ns a x r c s p e c t i v e ly i nt 1 1 i sp a p e r ，w er e a l i z e1 1 1 ea l g o d l m so ft l l e s et w op a 始m s ，a n dt 1 i e n 趾a l y z et h e i ra d v a n t a g e sa i l dd i s a d v a n t a g e sr e s p e c t i v e l y k e y w o r d ： d a t ab a c k u p ，f i l es y s t e m ，s 仃e 锄p r o c e s s i n g ，c a 伽o g 订e e ，s a x 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 第l 章引言 1 1 数据备份与恢复概述 本节作为本文研究结果的应用项目背景概述，简要地介绍数据备份与恢复的 概念、数据备份的重要性和可行性等相关内容。 1 1 1 数据备份与恢复的概念 随着信息技术的迅猛发展，人们对计算机信息系统的依赖型越来越强，如何 管理好计算机系统中的各种数据，对实际的应用至关重要。因此，人们对数据的 备份与恢复技术的发展和利用也越来越重视。 目前，数据备份技术得到了充分发展，但对数据备份只有基于实际应用背景 的定义。例如，o r a c l e 公司在其数据库文档【1 】中将备份定义为：备份就是数 据的复制，可以复制数据库中的数据文件、控制文件和日志文件等，备份的目的 是用来防止不能预料到的数据丢失，备份后的数据可以用来进行恢复。i b m 公 司在其备份软件t i v o i it s m 的文档【2 】中将备份定义为：备份就是离线存储系统 中在线数据的拷贝，如果发生在线存储设备失效，数据出现错误或有人意外的删 除了文件。该数据的离线拷贝将会被恢复到在线存储系统中。w - c u n i sp 瞅i t o n 在其著作u n i x b a c k u p a n dr e c o v e r y 【3 】中提出，备份= 复制+ 管理。在n e t b u i l k e r 的实现思路【4 】中，将备份描述为：备份= 复制+ 变换+ 传输+ 存储+ 管理。在 计算机词典【5 】中，b a c k u p 被解释为：为了防止原始数据丢失或者损坏，对文件、 文件系统或其他需要使用的资源进行备用复制，通常是将这些资源复制到磁带机 或者可移动存储设备上。 在本文中，根据数据备份的本质，从实际应用出发，将备份定义为一个过程， 这个过程将一组指定的数据按照一定的规则、采取一定的措施复制到指定的目标 地点，并对复制后的数据进行组织和管理，方便以后恢复时使用。一次备份被认 为是一个作业。 同样，将恢复也定义为一个过程，这个过程按照一定的规则、采取一定的措 施，将指定的已备份的数据从指定的源地点复制到指定的目标地点，并使被复制 7 ! 些查堂堡主兰堡垒苎塞壁墨竺鱼堡主! 墨塑竺翌苎鲨堡盐兰塞墨 的文件在目标地点能具有与备份之前相同的状态供用户使用。一次恢复被认为是 一个作业。 从前面提到的数据备份的定义，我们可以知道，数据备份的目的是将数据加 以保护，以便在系统遭到破坏或者按照某种特定需要将数据进行恢复，使得系统 能正常工作。 其次，数据备份也是历史数据归档的一种方式。将历史数据按照计划进行备 份，既可以防止数据意外丢失，也可以为我们对历史数据进行查询、统计以及分 析等工作提供保障。 1 1 2 数据备份的分类 按照备份数据的文件组成方式，可分为基于文件的备份和基于设备的备份 【6 】 7 】。基于文件的备份，即通过文件系统来定位文件的页，然后将整个文件直 接地拷贝到备份设备上，这样的备份方法有利于单个文件的恢复。由于存储在磁 盘上的文件页并不一定是连续的，就会造成在文件恢复过程中磁盘不断地定位操 作，增加了磁盘的负载，降低了磁盘的吞吐率。基于设备的备份，也叫做物理备 份，它忽略了文件的结构而直接将磁盘上的块拷贝到备份媒介上。因为它不需要 通过文件系统定位文件页，因而可以有效地提高备份的性能。为了保持文件和目 录与存储在备份媒介上数据的对应关系，基于设备的备份需要保存包含这种关系 的文件( 称为元数据文件) 。但是对于单个文件来说，文件页并不是连续地存储 在备份媒介上，造成了恢复比较复杂，速度也很慢。另一个比较复杂的问题是数 据的一致性，即基于设备的备份是将磁盘上的块顺序地拷贝到设备上，而数据的 更新若采用写回的方式，备份的数据有可能与最新的数据不一样。 按照备份操作的方式划分，备份可分为完全备份和增量各份，差分备份 【6 】【7 】。完全备份是对整个需要备份的系统进行备份，包括服务器操作系统和应 用程序生成的数据。这种备份方式的特点就是备份的数据最全面、最完接。当发 生数据丢失的灾难时，只要用一盘磁带就可以恢复全部的数据。其不足之处在于， 由于是对整个服务器系统进行备份，因此数据量非常大，占用备份的磁带设备比 较多，备份时间比较长。如果每天进行这种完全备份，则在备份数据中会有大量 内容是完全重复的，会增加成本。这种备份方式通常只是在备份的最开始、两 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 天采用。增量备份是指每次备份的数据只是相当于上一次备份后增加的和修改过 的数据。其优点在于：没有重复的备份数据，节省磁带空间，又缩短了备份时间。 缺点在于当发生灾难时，恢复数据比较麻烦。这种备份方式适用于进行了完全备 份后的后续备份。差分备份是指每次备份的数据是相对于上一次全备份之后新增 加的和修改过的数据。差分备份无需每天都做系统完全备份，因此备份所需时间 短，并节省磁带空间，它的灾难恢复也很方便，系统管理员只需两盘磁带，即系 统全备份的磁带与发生灾难前一天的备份磁带，就可以将系统完全恢复。这种备 份方式也适用于进行了完全备份后的后续备份。 按照备份数据对现有应用产生的影响程度，可分为离线备份和在线备份 6 】。 离线备份( 0 岳1 i n eb a c k u d ，它是在进行备份操作时，服务器不再接受来自用户 或应用对数据的更新。离线备份可以很好地解决在备份过程中数据的完整性的问 题，是防止破坏、敌意病毒袭击、应用失误等的有效方式。，在线备份( 0 n 1 i n e b a c k u p ) ，就是用户和应用正在更新数据时系统能够进行备份。在线各份最大的 难点是如何保持数据的完整性。为了保护数据的完整性，可以采用两种技术：锁 和快照。锁技术就是系统在备份某一文件时拒绝对该文件和目录的任何修改命 令，因而锁技术会对数据可用性产生一定的影响，在应用持续的同时进行各份不 可避免地降低了系统性能。快照是通过内存作为缓冲区( 快照c a c h e ) ，由软件提 供系统磁盘存储的即时数据映像。目前，在线备份大多采用快照技术。 根据备份数据所处的位置可分为本地备份和远程备份【7 】。本地备份，即通 过存储网络将数据备份在局域网范围内的备份。这种方式可利用现有的各种资源 和技术来达到高速的备份。它的性能可以很好地满足实际需要，如数据一致性、 容错等要求，而且性能是最高的。远程备份，在数据高可用性的网络环境中，异 地数据备份是一个必不可少的手段。当本地应用受到灾难性破坏时，通过远程备 份和容灾，来保护和恢复数据，使损失降低到最小。在远程备份过程中，数据传 输要跨越校园网、城域网甚至广域网，这时，网络的传输速度对备份性能的影响 是关键的因素。延迟也是影响远程备份性能的重要因素，特别是广域网的数据库 备份，可以通过异步的方式来解决。另外，在远程备份中还要解决数据的完整性 和一致性问题，解决这个问题比较成熟的技术是采用快照和镜像【5 】相结合的方 法。 9 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 1 1 3 已有的数据备份产品简介 目前，最主要的备份软件有v c d t a s 公司嘲的n 哪a c k u p ，c a 公司【8 】的 a r c s e n r c r ，i b m 公司【l o 】的砸v o l it s m ，l e g a t o 公司 1 1 】的n e t w j r k e r 和b a k b o n e 公司【1 2 】的n e t v 撕h 等。 v e r i t a s 公司的n 曲a c k u p 和l e g a t o 公司的n e t w o r k e r 均采用无服务器备份 技术。在无服务器备份中，服务器只需通过操作系统的文件分配表建立需要备份 的文件和设备、数据块之间相互对应关系的文件列表，通过备份代理将文件列表 传送给发出请求的备份进程来实现数据的备份。这样，服务器不必利用内存将数 据通过系统总线和存储接口进行两次复制，只负责一些必要的通信，处理器的负 载明显降低，而且对于数据移动和文件系统转换的管理也简化了许多。 c a 公司产品a r c s e “e r 提供了一个完整的解决备份方案，具备自动化的排 程设定、资源的安全性和完整性、自动化磁带管理及支持各种备份数据( 如数据 库、文件系统) 等特点。能够跨平台整合w i n d a 娜、n o v e un e t l a r e 与u n i ) 【之 间作业系统的备份功能。 i b m 公司的砸v o l it s m 依靠存储备份以及离线存储的数据拷贝有效地保护 数据，同时可保护上百台运行不同操作系统的计算机，包括笔记本电脑和大型机， 通过互联网、w a n 、l a n 、存储管理器的集中化管理、快速数据转移、存储技 术等相互连接，协同工作，从而最小化数据保护的成本，对计算机和网络产生巨 大的影响。 另外，商业领域的存储备份产品中很多采用了快照技术阴，主要有：e m c 公司的t i m e 弼n d e r ( s y m m e 砸x ) 和s n 印e wa n dm i n d r v i c w 软件；h i 诅c h i 公司的 1 1 1 s t a m s p l i tf o rs h a d o w i m a g e ；h p 公司的s u r e s t o r eb u s i n e s sc o p “x p ) ；s u n 公 司的s t o r e d g el n s t a n ti m a g e ；d a t a c o r e 公司的s a n s y n l p h o n ys n a p s h o to p t i o n ； f a l c o n s t o r 公司的i p s t o rs n a p s h o tc o p y0 p t i o n ；s t 叫c a g e 公司的m u l t i e w 。 1 2 问题描述 基于以上对数据备份与恢复知识的理解和对现有国内外备份系统的分析比 较，本文在实际应用研究的基础上，对文件系统备份过程中的目录树处理策略等 1 0 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 相关问题进行分析和讨论，并给出切实可行的解决方案。 ( 1 ) 备份数据相关信息的存储方式。备份文件系统时，为了便于恢复，我 们需要将文件和文件夹的相关信息即备份索引，如文件属性等也进行备份，但是 它和文件内容是不同的。文件内容以流式的处理方式直接被存放在介质中，而文 件属性等信息则需要在备份服务器的数据库中进行保存，以保证在介质服务器离 线的情况下对备份索引的正常访问。而存储的方式我们在下文中会进行详细地比 较分析。 ( 2 ) 在备份实施的过程中，根据用户定义的资源选择树和文件系统当前目 录树生成备份文件列表，以提供给备份程序进行备份。这对诸如t a r 等命令行备 份程序是一个很大改进，让用户和备份程序能“所看即所备份”。 ( 3 ) 增量备份时的资源树处理策略。增量备份时，由于要判断那些文件和 文件夹需要备份，所以在资源树处理策略的实现过程中，需要合并当前备份索引 和历史备份索引，以便用户根据时间点进行恢复。 ( 4 ) 目录树的合并、匹配等操作的实现方式。由于实际的备份和恢复过程 中，文件系统的文件和文件夹数目往往很大，所以在算法实现上要考虑时间和空 间复杂度上的问题，对树结构进行流式处理。对目录树的处理策略，具体的算法 实现时分迭代模式和流式模式，即基于d o m 的模式和基予s a x 的模式。 1 3 下文结构 本文以下内容，第2 章介绍本文所依附的相关研究技术背景及其现状描述； 第3 章、第4 章和第5 章是本论文的核心部分，是本文贡献的集中体现，第3 章介绍备份与恢复的相关数据处理策略以及对该策略的性能评价，第4 章着重介 绍备份与恢复过程中的资源树处理策略，并给出算法描述和分析以及通用处理模 型，第5 章主要讨论备份归档文件通用结构与索引重建技术；第6 章对本文的研 究成果给出具体的实现示例，并给出综合分析；第7 章为总结和展望。本文的所 有工作以中山大学软件研究所与广州威腾网络科技有限公司合作项目商业 数据备份系统n e t b u n k e r 为研究和应用背景。 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 第2 章相关研究技术背景及现状描述 2 1x m l 文档语法与结构 2 1 1x m l 简介 x m i ，_ 一可扩展标记语言【1 3 】( s i b l em a r l a l p g u a g c ) ，是一种可以 用来创建自己的标记的标记语言。它由万维网协会( w 3 c ) 创建，用来克服h 刑l ( 超文本标记语言h y p _ e r f e 哪m a 凼叩l a n g u a g e ，它是所有网页的基础) 的局限性。 和 r r m l 1 4 1 一样，讧l 基于s g m l 1 5 1 标准通用标记语言( s t a n d a r d g e n e r a l i z e dm a r k u pl a i i g l l a g e ) 。 订l 语言提供一种描述结构数据的格式，这有助于更精确地声明内容，方 便跨越多种平台的更有意义的搜索结果。工。简化了数据交换，并且支持智能 代码和智能搜索。此外，m 。将起用新一代的基于w 曲的数据查看和处理应用 程序。订l 提供可以广泛执行并易于配置的数据的结构表示。m 。确保结构数 据是一致的，并独立于应用程序或供应商。x m l 提供可以编码各种情况( 从简 单至复杂) 的内容、语义和架构的数据标准，可被用于标注以下对象： 普通文档。 诸如约会记录或采购定单之类的结构记录。 具有数据和方法的对象，如j a v a 对象或a c t i v e x 控件的持续型表 单。 数据记录，如查询的结果集。 有关w 曲站点的元内容，如“频道定义格式( c d f ) 1 6 】”。 图形表示，如应用程序的用户界面。 标准架构实体和类型。 2 1 2 文档语法与结构 格式有效的) ( 1 l 文档须遵守w 3 c 的x m l l 0 1 7 】推荐标准的自描述语法要 求，以下为一个简单的格式有效的x m l 文档示例： 1 2 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 t b v e r e m i n d e r d o n 、f o r g e tm e t l l i sw e e k e n d ! t 拈o d y n o t e 帆文档标记语法【1 8 】： 字符：x m l 指定的可以使用的字符均在1 6 位的u n i c o d e2 1 字符集中。 合法的x m l 字符包括三个a s c i ic o 控制符、所有的a s c n 可以的显示 字符以及所有其他统一代码字符值。 命名：所有的x m l 命令都必须以字符、下划线或冒号开头，后面跟着有 效命令字符。有效命令字符除了合法的儿字符外，还包括数字、连字 符和句号。但是在实际应用中只有在用作命名空间分隔符是才使用冒号。 x m l 标记对大小写是敏感的。 订l 文档结构【1 8 】： 一个格式有效的x m l 文档由三个部分组成： 可选的序言：包括x m l 文档类型、声明、处理命令、注释或空格。 文档的主体：由一个或多个元素组成，是一个树形结构。元素是儿标 记的基本组成部分。元素使用标记进行分隔，每一个元素都必须由一个 起始标记和一个结束标记隔开，中间可以包含其他元素、字符数据、字 符应用、实体应用、注释和c d a r a 等。 可选的结尾：包括注释、处理命令或空格。 在上述的x m l 文档示例中， 属于序言， 属于文档主体。 2 2 数据流式处理 流式处理是一种传送数据的方法。当前，流式处理较多的应用于大规模的多 媒体数据文件，如图形图像、声音等在网络的传输过程中，以节省传输带宽，提 中山大学硕士学位论文文件系统各份中目录树处理算法设计与实现 高数据的处理效率。 常用的w i n d o 、sm e d i ap l a y e r 【1 9 】是一种流式处理多媒体数据的工具，用于流 式地播放视频播放多媒体视频和音频文件。研究领域内，对流式处理的应用也较 多的用在多媒体数据的处理上。在二十世纪八十年代，d j ，舢l e n o n 等人对二维 图像的流式处理有过深入研究，曾介绍了一种二维图像的空间转换的流式处理算 法【2 0 】，该算法对二维图像的每一个象素进行处理，使输入的高分辨率图像在经 过过滤之后对应一个低分辨率的输出图像，并且图像的失真度低。对网络中的多 媒体数据的处理，文献 2 1 】中给出一种多层次的内存预取结构，在存储器芯片的 内外两个层次上实现对多媒体数据的预取，以节省网络带宽；文献 2 2 】中，根据 多媒体文件的内容，在流式处理时进行对数据进行预记录，保证数据传输和播放 的连续性。 当然，除了多媒体数据之外，流式处理的思想还可以用于处理其他类型的数 据，如数据备份中的备份选择集数据，可以是数据库中的数据，文件系统中的文 件和文件夹等。 2 3 咀。的d o m 处理模型 文档对象模型( d o m ，d o c 啪e n to 巧e c tm o d e l ) 【2 3 】为x m l 文档的已解析 版本定义了一组接口。解析器读入整个文档，然后构建一个驻留内存的d o m 树 结构，然后编写的代码就可以使用d o m 接口来操作这个树结构。可以遍历该树 结构以了解原始文档包含了什么，也可以删除树的某个部分，还可以重新排列树 的结构以及添加新的分支等。 使用d o m 时，数据以树结构的形式被装入内存中。同一文档将被表示为结 点，如图2 1 所示。矩形框表示元素结点，椭圆形表示文本结点。d o m 使用根 结点和父子关系。例如，在本例中，s 啪p l e s 将是带有五个子结点的根结点：三 个文本结点( 空白) 和两个元素结点s e n ，e r 和m 0 1 1 i t o r 。实际上，s e r 、啊和m o n i t o r 有n u l l 值。相反，它们有子文本结点c o l o r 和u n i x 。 1 4 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 图2 - 1 采用d o m 解析x m l 文档时，需要在内存中构建驻留整个文档的d o m 树， 如果文档很大，就会要求有极大的内存。d o m 创建表示原始文档中每个东西的 对象，包括元素、文本、属性和空格。如果只需关注原始文档的一小部分，那么 创建那些永远不被使用的对象是极其浪费的。d o m 解析器必须在代码取得控制 权之前读取整个文档。对于非常大的文档，这会引起显著的延迟。这些仅仅是由 文档对象模型的设计引起的问题，撇开这些问题，d o m 是解析咀。文档非常 实用的方法。 2 4 讧l 的s a x 处理模型 s a x 是s i r n p l ea p if o rx m l 【2 4 】的缩写，它并不是由w 3 c 官方所提出的标 准，可以说是“民间”的事实标准。实际上，它是一种社区性质的讨论产物。虽 然如此，在“l 中对s a x 的应用丝毫不比d o m 少，几乎所有的x m l 解析器 都会支持它。 与d o m 比较而言，s a x 是一种轻量型的方法。我们知道，在处理d o m 的 时候，我们需要读入整个的x m l 文档，然后在内存中创建d o m 树，生成d o m 树上的每个结点( n o d e ) 对象。当文档比较小的时候，这不会造成什么问题， 但是一旦文档大起来，处理d o m 就会变得相当费时费力。特别是其对于内存的 中山大学硕士学位论文文件系统备份中目录树处理算法设计与实现 需求，也将是成倍的增长，以至于在某些应用中使用d o m 是一件很不划算的事 ( 比如在a 即l e t 中) 。这时候，一个较好的替代解决方法就是s a x 。 s a x 在概念上与d o m 完全不同。首先，不同于d o m 的文档驱动，它是事 件驱动的，也就是说，它并不需要读入整个文档，而文档的读入过程也就是s a x 的解析过程。所谓事件驱动，是指一种基于回调( c a l l b a c k ) 机制的程序运行方 法。订l r 船d e r 接受x m l 文档，在读入m 。文档的过程中就进行解析，也就 是说读入文档的过程和解析的过程是同时进行的，这和d o m 区别很大。解析开 始之前，需要向x m i 瓜e a d c r 注册一个c o m e n t h a n d l e r ，也就是相当于一个事件 监听器，在c o n t c n t h a n d i c r 中定义了很多方法，比如s t a n d o c u m e 叫) ，它定制了 当在解析过程中，遇到文档开始时应该处理的事情。当x m l r 眈d e r 读到合适的 内容，就会抛出相应的事件，并把这个事件的处理权代理给c 0 m e n t h a l l d l e r ，调 用其相应的方法进行响应。而且，s a x 是基于流式处理思想的，对数据量较大 的讧l 进行解析的时候，其优势之处显而易见。 图2 2 具体来说，用s a x 处理x m l 文档主要涉及以下几步： 创建事件处理程序。 创建s a x 解析器。 将事件处理程序分配给解析器。 对文档进行解析，将每个事件发送给处理程序。 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 这种s a x 处理方案的好处类似于流介质的好处：可以立即开始解析，而不 是必须等待所有要处理的数据。同样，由于应用程序简单地检查经过s a x 解析 器的数据，所以不需要将数据存储在内存里。当遇到大文档时，这是一个突出的 优势。一般来讲，s a x 比文档对象模型d o m 的处理速度要快，而且资源使用率 较低。另一方面，由于应用程序不以任何方式存储数据，所以，使用s a x 时， 不能“返回”至数据流中前面的数据，不能对已处理过的数据进行更改。 2 5 文件系统备份 很多文件系统中，都提供有备份和恢复的操作命令。较早的d o s 操作系统中， 提供了文件系统备份命令b a c k l j p 以及恢复命令r e s t o r e 。b a c k i j p 命令通 过设置不同的参数，提供了完全备份、增量备份、差分备份三种备份方式。通常， b a c k u p 和r e s t o r e 命令不是同时进行的，当备份和恢复时的操作系统版本 不同时，恢复将会失败。w i n d o w s 系列操作系统中，提供有文件备份命令和a p i 函数，如c o p y 命令、b a c k u p r 黯d 函数。在w i n d o w s 2 0 0 0 中，命令n t b a c k u p 提 供了命令行和g u i 界面两种方式进行备份和恢复，它只针对系统本身的文件备 份和恢复，不能跨平台工作。在u m x 系统中，有许多方法可以实现从硬盘向磁 带等介质备份文件，主要有：使用d d 命令：使用裸设备访问命令c p i o ；使用t a r 命令。这些命令是文件系统本身自带的，不方便进行跨平台操作，只是命令行格 式，没有g u i 界面。l i n l l ) 【文件系统中也提供t a r 等备份和恢复命令。 研究领域中，对文件系统备份的研究工作是数据备份与恢复的一部分，也就 是说在数据备份和恢复的研究中，文件系统是一种数据源，与其他数据源如数据 库等是一并处理的。 韩国的j a i l g s e u n g h i 等人在文献【2 5 】中讨论了u n 文件系统中在线备份的 问题以及策略，提出了一种内核级高速在线备份系统的框架，比较和分析了传统 的备份系统和该文献提出的高速备份系统的优缺点。该备份系统的思想是基于 “设备对设备的在线备份”的，例如硬盘到磁带机的备份，克服了传统备份方式 的通过内存缓冲区来进行备份的缺点，提高了备份效率和资源的共享度。文件系 统备份的策略是跟随数据备份策略发展的，而对文件系统备份中目录树等处理方 式并未有详细地讨论结果公布。国内，对文件系统备份的相关研究是和数据存储 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 联系在一起的，例如存储区域网( s a n ) ，网络附加存储( n a s ) 等。对目录树 在备份过程中的处理方式也未曾见有文献予以讨论。 商业领域中的备份软件如前文所述的n e t v a u l t 等备份系统，在其产品资料中 并未对任何备份和恢复的实现过程如备份信息的存储方式、目录树的处理策略等 给以具体描述，所以我们对此不得而知。 2 6 小结 本文主要讨论文件系统备份过程中备份信息的存放方式、备份资源树的表示 以及处理策略、备份资源树在备份和恢复过程中的合并处理策略等问题。这之中， 涉及到的有订l 数据格式、d o m 处理模型、s a x 流式处理等技术知识，本章 对这些技术以及研究现状给出一个简单的介绍，以作为本文的技术背景。在此基 础上，本文研究对文件系统备份过程中的一些实际问题的处理方式，并给出相应 的理论结论和应用实现。 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 第3 章备份与恢复的相关数据处理策略 文件系统备份的过程中，对备份信息的存放问题，也即对备份索引的处理方 式会直接影响到备份系统的性能以及备份数据的可用性。特别是在增量备份时， 我们需要根据文件和文件夹的瑚瞄m e 属性等备份信息进行判断以决定是否备份。 本章对该问题分两种处理方式进行讨论，一种是将备份信息直接写入数据库的表 中，另一种是将备份信息先写入x m l 文档然后将该文档内容作为一个字段写入 数据库的表中，对这两种方式分别给出相应的实现并进行分析和评价，对文件系 统备份信息的存放方式提供切实可行的方案。 3 1 备份与恢复数据字典定义 下面，对本文中使用到的相关备份与恢复的数据字典进行定义和描述 2 6 】。 备份( b a c k u p ) ：备份是一个过程，该过程将一组指定的数据按照一定的 规则、采取一定的措施复制到指定的目标地点，并对复制后的数据进行 组织和管理，方便以后恢复时使用。 恢复( r e c o v e r y ) ：恢复是一个过程，这个过程按照一定的规则、采取一 定的措施，将指定的已备份的数据从指定的源地点复制到指定的目标地 点，并使被复制的文件在目标地点能具有与备份之前相同的状态供用户 使用。 备份选择集( b a c k u ps e l e c c i o ns c t ) ：需要备份的数据列表的集合，可以将 数据分成多个备份集( b a c k u ps e t ) 进行备份。用户可以将经常选择的数 据保存在一个选择集中，便于在以后的备份过程中重用这个选择集，而 不需要重新选择数据。 备份选项集( b a c k l l po p t i o ns e t ) ：备份时，不同的备份代理要配置不同的 选项集，备份程序通过选项集来完成不同代理类型的数据备份，例如文 件系统备份时要指定增量备份还是完全备份。将常用的备份选项配置好 并保存在一个选项集中，用户可以在以后的备份过程中重用这个选项集， 而不用重新配置。 调度集( s c h e d u l es e t ) ：调度集用来设置作业运行的时间和方式( 立即执 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 行、只执行一次、重复执行、由命令触发) 。将常用的调度策略配置好并 保存在一个调度集中，用户可以在以后的备份过程中重用这个调度集， 而不用重新配置。 目标地点集( t a 唱e ts e t ) ：目标地点集用于设置备份数据所存放的目标地 点。将常用的备份数据存放地点配置好并保存在一个目标集中，用户可 以在以后的备份过程中重用这个目标集，而不用重新配置。 保存集( s a v es e t ) ：己备份数据的集合，个保存集代表一组备份的数据。 可以从保存集中有选择的恢复数据。每次恢复只能对一个保存集进行操 作。一个保存集可以存放在多个介质上，一个介质也可以存放多个保存 集，主要取决于保存集和介质的大小。 备份片( b a c k u pp i e c e ) ：是备份集的基本单位，一个备份集由多个备份片 组成。一个备份片不大于介质服务器上一个逻辑卷的大小。 备份集( b a c k u ps e t ) ：一个选择集的数据可以分成多个备份集，一个备份 集对应一棵资源子树。在备份过程中备份程序将一个备份集分成多个备 份片进行传输。一个备份片只属于一个备份集。 备份索引( b a c k u pc a t a l o g s ) ：备份索引是记录数据备份日志的目录库， 是备份系统中所要处理的一种数据，包括如文件系统中文件和文件夹的 属性，数据库中的控制文件、日志文件等。备份索引和备份系统中的其 他基础数据一起，构成系统设计实现的基础。 真前缀( p r o p e rp r c f i x ) ：资源树结构的真前缀表达式，用来描述资源树的 一个子集。 介质( m e d i a ) ：存储数据的载体，如：磁带、光盘、磁盘阵列等。 3 2 备份信息写入数据库 在文件系统备份过程中，我们为需要备份的文件定义一个文件属性表，然后 将备份文件的各种属性信息记录到p o s t g r e s q l 数据库的表中，n t f s 文件系统对 应表f i l e - n t f s ( 表3 - 1 ) ，l i n u x 文件系统对应表f i l e - e x t f s ( 表3 - 2 ) 。在 p o s t g r e s q l 数据库中，与写入文件系统备份相关信息的表还有a r c h i v e ( 备份 归档属性表) ，和r e s o u r c e ( 备份资源属性表) 。 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 表3 - 1f i l en t f s ( n t f s 文件属性表) - 一 文件所在归档标识( i d ) a r c i d c h a “3 6 ) 备份源标识( i d ) r e s i d c k 畎3 6 ) 文件属性 a t t f i b u t e i n t e g e f 文件创建时间c n m e t i m e s t a m p ( o ) 最后访问时间 a t l m e t h n e s t 啪p ( o ) 最后修改时间 m t i m e t i m e s t m “o ) 文件在归档中的偏移 。妇备e t b i 百m 文件在归档中所占大小 s l z e b i g i m 文件或目录的标识，r ( 文件) 或d ( 目录) t y p e 妇 校验码 c h k s 啪 c h 越3 2 ) a r c i d i n l e g e r 归档标识( i d ) ，唯一标识一次备份 r e s i d i n t e g e r 资源标识( i d ) ，唯一标识备份的文件或目录 l i n k p a c hv a r c l l a r ( 4 0 9 6 )若文件为符号或硬连接，保存连接名 t y p ev 砌a r ( 1 0 ) 文件类型 m o d e i m e g e r文件的属性位，s l - m o d e 的值 u i d i n t q 薛r 文件所属用户的标识( u s 日i d ) u n a r n e v a r c l l a r ( 2 5 6 )文件所属用户的用户名，恢复到不同系统时使用 g i d i n l e g e r 文件所属组的组标识( g r o u pj d ) g 尬m e v a r c h a r ( 2 5 6 ) 文件所属组的组名 d e a j o rl m e g e r若文件为设备文件，则保存主设备号 d e v m i n o r i n l e g e r 若文件为设备文件，则保存次设备号 a t l m e t i m e s i ；瑚p 最近访问时间 m t i m e t i m e s t a m p 最近修改时间 c t i m e t i m e s t a m p 文件创建时间 中山大学硕士学位论文 文件系统备份中目录树处理算法设计与实现 。脚f b 蜮n t 文件在归档中的起始位置，若不是常规文件则为1 s l z e b i g i n t 文件大小。若不是常规文件则为- 1 c h e c k s u m v a r c h a “1 2 8 )文件的校验字符串，若不是常规文件则为空字符串 首先给出将备份信息写入数据库的情况下，数据备份和恢复的基本过程。 备份过程： 1 写a r c h i v e 表，生成并填写a r c i d 。 2 写r e s o u r c e 表，生成并填写r e s i d ，若对应文件已存在，则直接取得对 应的r e s i d 。 3 找到f i l en t f s ( f i l ee x t f s ) 表中r e s i d 相同的所有备份，再在这些 各份其中找到最近次的低级别的备份，若没找到则转5 。 4 检查对应文件的m d m e 是否晚于最近一次低级别各份的n m m e ，若是贝继 续，否则转2 。 5 获取文件属性，根据a r c i d 和r c s i d 写入f i l en r f s ( f 1 l e - e x s ) 表。 6 发送文件 7 重复2 ，到所有文件备份完成。 备份过程流程图： 图3 3 恢复过程： 1 客户给出r e s i d 和a r c i