（计算机软件与理论专业论文）备份系统中流式处理的行为分析及其插件化实现.pdf

备份系统中流式处理的行为分析及其插件实现 计算机软件与理论 硕士生：张巍 指导老师：倪德明副教授 摘要 随着用户对数据安全和数据有效利用的要求不断提高，备份系统对数据的 处理已经不再是简单的数据拷贝，而是存在大量种类繁多、功能各异的数据处 理。目前现有的备份系统虽然功能强大，但是系统结构复杂、数据处理功能基 本都是固化于系统中。系统缺乏具有通用性的备份模型和架构，导致软件设计 复杂，复用率低。关于数据处理功能，目前绝大多数备份系统存在如下几个缺 陷：修改现有的数据处理和添加新的数据处理都是很复杂的；不支持第三方扩 展研发；无法支持细粒度的数据处理。 在备份领域中，待处理的数据和数据处理过程是有如下特性的：待处理的 数据是海量的、呈树状嵌套结构；数据处理的方式必须是流式的，低内存消耗 的，数据处理的过程是多种多样的。各种处理过程可以划归为一个统一的处理 操作。同时，各数据处理过程之间的业务处理功能相对比较独立，可以以松耦 合的方式实现。因此，本文考虑将插件的思想应用于备份系统中，即将每一个 数据处理看作一个遵循相同接口的插件，实现对备份系统中的各数据处理过程 提供诸如动态插拔、动态配置等管理功能。 本文从流式数据处理系统研发中的具体问题出发，首先以半形式化的方法 分析和归纳了备份系统中数据的结构、数据处理的行为，得到了一个流式处理 模型；然后由该模型映射得到一个软件部件，即一种可复用的流式插件结构， 每个数据处理操作是一个插件。接着使用纯c + + 语言实现了该插件系统。同时 我们重点讨论了系统实现过程中的几个关键问题。最后，对比了当前系统与现 中山人学硕一l ：学位论文备份系统中流式处理的行为分析及其插件实现 有备份系统在框架和性能上的优劣，并总结了当前系统的不足。当前流式模型 和插件系统结构对类似流式处理领域有一定的理论性和工程性借鉴意义。 关键词：备份，插件，流式，数据变换，软件配置管理 i i 中山大学硕：卜学位论文备份系统中流式处理的行为分析及】e 捅件实现 r e s e a r c ho fd a t at r a n s f o r m i n ga n d p l u g i ni m p l e m e n t a t i o n o fb a c k u ps y s t e m 一一 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 h a n gw e i s u p e r v i s o r ：a s s o c i a t ep r o f n id e m i n g a b s t r a c t s i n c eu s e r sa r ep a y i n gm o r ea n dm o r ea t t e n t i o nt od a t as e c u r i t ya n de f f e c t i v e u s eo fa r c h i v e s ，t h ed a t at r a n s f o r m i n gi nb a c k u ps y s t e m sc o n t a i n sn ol o n g e rj u s t c o p y , b u tl o t so fd i f f e r e n td a t at r a n s f o r m i n g n o w a d a y sm o s tb a c k u ps y s t e m sa r e p o w e r f u l ，b u ta l s oc o m p l i c a t e d t h e f u n c t i o n so fe v e r yd a t a p r o c e s s i n ga r e i m p l e m e n t e di nt h ec o d eo ft h es y s t e m o w i n gt ol a c ko fau n i v e r s a lb a c k u pm o d e l a n ds y s t e ma r c h i t e c t u r e ，t h ed e s i g na n di m p l e m e n t a t i o no fb a c k u ps y s t e m sa r e e x h a u s t i n g ，a n d i t s v e r yh a r dt o r e u s et h e m c o n s i d e r i n gt h es y s t e m sd a t a t r a n s f o r m i n gf u n c t i o n s ，m o s tb a c k u ps y s t e m sh a v et h ef o l l o w i n gm a i nd r a w b a c k s ： b o t hu p d a t i n ga l le x i s t i n gd a t at r a n s f o r m i n ga n da d d i n gan e wd a t at r a n s f o r m i n ga r e v e r yd i f f i c u l t ；t h e r ei sn os u p p o r tf o rt h i r d - p a r t y sr & d ；w ec a n tc h a n g et h ee f f e c t l e v e lo fad a t at r a n s f o r m i n g i nb a c k u pa r e a ，d a t aa n dd a t at r a n s f o r m i n gh a v et h ef o l l o w i n gf e a t u r e s ：t h ed a t a t ob et r a n s f o r m e da r eh u g ea n dt h e yh a v ean e s t e dt r e es t r u c t u r e ；e v e r yd a t a p r o c e s s i n gs h o u l db ei nt h ef o r mo fs t r e a m i n ga n dc o n s u m el i m i t e dm e m o r y ；b e s i d e s t h e r ea r em a n yd i f f e r e n tk i n d so fd a t ap r o c e s s i n g t h ep r o c e s so fd a t at r a n s f o r m i n g c a nb ec o n c l u d e dt oau n i f i e df o r m e a c hd a t ap r o c e s s i n gi sr e l a t i v e l yi n d e p e n d e n t ， a n dc a nb el o o s e l yi m p l e m e n t e d s oi nt h i sa r t i c l e ，w et r yt oc o n s i d e re a c hd a t a t r a n s f o r m i n ga sap l u g i n ，w h i c hi m p l e m e n t st h es a m ei n t e r f a c e i nt h i sm a n n e r , w e i i i 中山大学硕士学位论文 箭份系统中流，处理的行为分忻及j e 插件实现 c a l lo f f e rb a c k u ps y s t e m st h ea b i l i t yt om a n a g ea l lo ft h es y s t e m sd a t at r a n s f o r m i n g f u n c t i o n s t h i sa r t i c l ei sb a s e do nm a n ys p e c i f i cp r o b l e m sw h i c hu s u a l l yo c c u rd u r i n gt h e d e v e l o p m e n to fb a c k u ps y s t e m f i r s tw ei n t r o d u c ea n da n a l y s et h es t r u c t u r eo ft h e d a t aa n dt h ep r o c e s so fd a t at r a n s f o r m i n gi nb a c k u pa r e a ，i nas e m i f o r m a lm e t h o d t h e nw eg e tam o d e lo fs t r e a m i n gd a t at r a n s f o r m i n g u n d e rt h eg u i d eo ft h i sm o d e l ， w ed e s i g na ni n t e r f a c ef o re v e r ys t r e a m i n gd a t at r a n s f o r m i n g a f t e rt h a t ，w e i m p l e m e n tap l u g i ns y s t e mi np u r ec + + l a n g u a g e t h e nw ed i s c u s ss o m ek e y t e c h n o l o g i e sd u r i n gt h ei m p l e m e n t a t i o no ft h ep l u g i ns y s t e m f i n a l l y , w ec o m p a r e t h i ss y s t e mw i t hs o m ep o p u l a rb a c k u ps y s t e m s ，i nb o t hf u n c t i o n sa n de f f i c i e n c e t h e a n a l y s i so fs t r e a m i n gd a t at r a n s f o r m i n g ，a n dt h er & d o ft h ep l u g - i nb a c k u ps y s t e m c a nb ew i d e l ye m p l o y e di ns o m es i m i l a rf i e l d s k e yw o r d s ：d a t ab a c k u p ，p l u g i n i n ，s t r e a m i n g ，d a t at r a n s f o r m ，s c m i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：芗魄 f t 期：扫铝年芗月二7e t 使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学位 论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅， 有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方 法保存学位论文。 学位论文作者签名：弗巍 日期：幻昭年岁月2 7 日 导师签名：陀雹碉 日期：加8 年乡月z 7 日 中山人学硕士学位论文备份系统中流式处理的行为分析及e 捅件实现 第1 章引言 1 1备份还原系统中的数据处理 数据备份专家形c u r t i sp r e s t o n 在其专著u n i x 备份号恢复中提出：备 份= 拷贝+ 管理【l 】。通常，备份不只是对数据进行简单的拷贝，而且需要对数 据进行一定转换。例如，为了减少备份后数据的大小，会要求对数据进行压缩； 为了提高安全性，会要求对数据进行加密。因此，我们可以认为备份= 转换+ 管 理。 备份中，数据转换有如下特性2 】： 1 ) 数据是流式的。 2 ) 对数据的转换处理也是流式的。 3 ) 转换处理的行为是多种多样的。 被转化的数据是海量的、连续的。因此它经过转换处理过程时，程序无法 缓存下所有数据。这就要求转换处理只能扫描一遍数据，数据一旦流过就不能再 次访问了。 备份中的管理是指对备份集进行统一管理，这部分功能与数据转换的关系 不大。撇开管理功能，备份系统的备份和恢复过程可以简化如图1 1 所示。 彳 厂 召 g 图1 1 备份和恢复示意图 其中，4 为备份源，即待备份的数据。丑为备份集，即备份后的档案文件。 中山大学硕士学位论文备份系统中流式处理的行为分析及j e 插件实现 为备份时的数据转换，即正向操作。g 为恢复时的数据转换，即逆向操作。 玩是流式处理，它们处理的数据是一个数据块序列。数据块序列按时问先后 顺序逐个输入给数据处理过程，数据处理过程经运算依次得到一个输出数据块序 列。对于数据块序列中的每一块数据，流式处理的过程可以看作图1 2 所示的情 况。 图1 2 流式处理 流式处理厂接收到一个输入数据块d ，经过处理后，得到一个输出数据块t 。 备份源彳中数据呈树状结构，树中结点是流式传给数据处理过程饱，同时 结点又是由更下一级单元构成的。例如，备份文件系统时，彳为一个目录中的所 有文件和目录。显然，彳是树状结构的，彳中的每一个结点是一个文件或目录。 在n t f s 文件系统中，文件目录又是由若干流组成。直接打开文件，看到的是文 件的主流，同时文件还存在安全流、自定义流等。由此，可见结点是由若干更小 的单元构成。结点的数据是流式地传给或g 的。 数据源a 从层次来看是分若干级的。例如，文件系统中，数据源可以分为三 级d a t a s e t - n o d e s e g m e n t 。具体而言，可以将待备份的目录看作为一个整体即 是一个d a t a s e t 。而将里面的文件和目录叫作n o d e ，因此d a t a s e t 是由若干n o d e 递归组成。而陋y 文件中的多个流，我们把每个流称为一个s e g m e n t 。因此d 比 又是由若干s e g m e n t 构成的。 从数据转换角度来看，当前备份系统存在如下几个问题： 1 ) 缺乏具有通用性的备份模型和系统架构，导致软件设计复杂，复用率低。 备份系统中，数据处理与一般数据处理不同，是流式的，实现起来更复杂一 些。数据处理过程一旦被写死了，要想更新或新增功能都是很麻烦的。 备份系统是复杂而重要的，但是用户对系统的需求并不是千篇一律的。对于 现有的功能，他们经常会提出自己特殊的需求。例如，军方使用备份系统时为了 2 中山大学硕士学位论文备份系统中流j 处理的行为分析及其捅件实现 增加数据的安全性，希望使用自己的加密算法；用户不同的应用场合，对压缩算 法提出了不同的需求。由于各模块之间千丝万缕的联系，对于这类需求变更开发 商很难快速有效地响应。同时开发商并没有提供有效机制，使得用户能方便地对 现有系统进行二次研发。 2 ) 不支持第三方扩展。 备份系统中，数据处理过程的种类是繁多的。随着时间的变化、应用场景的 不同，提出的数据处理功能也不尽相同。例如，随着备份领域的发展，用户对归 档文件的集中管理需求增强。当备份大量邮件后，用户希望能按内容搜索这些邮 件；当用户只是想查看备份集的结构时，不应该花费大量时间去恢复整个归档文 件，即备份系统应提供预览归档文件结构的功能。 如果备份系统想支持在系统研发时并不知道的数据处理功能，那么就需要提 供一个有利于第三方扩展研发的机制。遗憾的是，目前备份系统很少能支持第三 方扩展，因此数据处理的功能就被大大限制了。 3 ) 恢复时，无法只对备份集的一个子集进行恢复。 目前，备份系统( 例如v e n t i , v e r i t a s 等) 都只支持恢复整个备份集。即如果 我们只想从b 中取得4 的一个子集是很困难的。目前，存储设备中应用比较广 泛的是磁带、磁带库、磁盘阵列和光盘、光盘塔或光盘库几大类3 1 。而对于海量 数据，为了降低存储成本，一般是采用磁带存储的。但是，磁带只能顺序读写， 倒带将是一件很费时的工作，这使得备份系统的复杂程度大大提高。 4 ) 无法支持细粒度的数据处理。 当前备份系统的数据处理，都是作用于整个d a t a s e t 级别的。例如对整个待 备份的数据进行压缩或加密。但是，实际过程中，我们需要更细粒度的处理。例 如，索引时将整个待备份的目录当作是一个整体来进行索引是完全没有意义的。 我们只有将索引操作作用于n o d e 级别，对单个文件进行索引，这样搜索时才能 告知用户待搜索的数据存在于哪些文件中。因此，我们需要有能力指定数据处理 作用于哪个级别的能力。 中山人学钡i j 学位论上备份系统中流式处理的行为分析及其插件实现 1 2本文的工作和内容 首先，本文着重分析了备份时待处理数据的结构特性，通过半形式化方法 描述了流式转换的行为特性。提炼出转换处理过程的共同行为，定义了一套运行 接口和通讯协议。希望对流式处理领域的数据存储、流式变换有一定的借鉴意义。 其次，结合插件技术，实现了一个转换行为以插件方式实现的通用备份还原系统， 以此为备份领域提供一个代码级可复用的模型。 全文分为六章。第一章为引言部分。从数据转换角度，分析当前备份还原 系统存在的问题。第二章，分析备份还原系统中，待处理数据的结构组成。对于 数据转换过程提供了半形式化的定义。第三章，结合备份领域的具体功能要求， 分析了流式数据转换( 本文称作算子) 的行为特性。第四章，由前两章的数学分 析，将模型映射到软件部件。结合插件系统，设计并实现了一个通用备份还原系 统。着重介绍了插件系统的几个关键部分：插件接口、插件内核、数据流控制、 变量传递等。第五章，通过大量测试和分析，对比了该系统与现有备份还原系统 的优劣。第六章，总结了当前系统的不足，并提出了一些改进意义。当前系统是 基于备份领域的，但是它对类似的流式处理领域也是有一定的借鉴意义。 4 中山人学硕十学位论文 备份系统中流式处理的行为分析及其插件实现 第2 章数据源与流式处理 2 1数据源 备份中，数据源是多种多样的。文件系统、邮件系统、网站系统、数据库 系统等都可能是数据源。数据源是由若干结点组成的，而每个结点是又是由更低 级的数据构成的。每个结点的数据是流式传给数据处理的，即在数据处理看来这 些数据是流数据。 2 1 1数据源的结构 备份源彳中数据成树状结构，数据源是由若干结点组成的，而每个结点又 是由更低一级的数据构成的。数据是流式传给数据处理过程他的。 这里，我们把待备份的数据看作是一个整体，并称之为d a t a s e t 。而备份源 d a t a s e t 是由若干结点组成的，我们把这些结点称为n o d e 。结点又是由更小的单 位组成，我们把这个单位称为s e g m e n t 。 在文件系统中，备份源是呈树状结构的，如图2 - 1 所示。 ( ) 根文件糸统件 厂八一、 b i n s b i n h o m e u s r m n t o p t d e v b o o t 厂人 b i n l i b r f i n p u t 图2 1 文件系统( w i n d o w s 和l i n u x 的) 中的树状结构 七 珏 t e 一一 眦 一 一 一n一如 始 中山犬学硕j 二学位论文备份系统中流式处理的行为分析及】e 插件实现 图2 1 左侧，d a t a s e t ( d ：i t e m p ) 由若干结点n o d e ( t e m p t x t , f f , i n d e x 等等) 构成。在巩，文件系统中，文件目录又是由若干流构成。直接打开文件，看到 的是文件的主流，同时文件还存在安全流、自定义流等。例如，t e m p t x t 中存在 如下备用流。m e s 的多流结构表明，文件是由若干流构成。而我们定义中d 如 是由若干s e g m e n t 构成。巩，的多流即对应我们这里的s e g m e n t 。 葛勰曼塞全。摘要 标题哩) ： ：t 。：0 图2 2 ? s 文件系统中的多流结构 在邮件系统中，我们备份某个账户下的邮件。该账户的全部邮件资料可以 看作为一个d a t a s e t 。把收件箱，发件箱，草稿箱等邮件系统的目录结构和所有 邮件等看作为n o d e 。每封邮件n o d e ，是由标题、正文、附件等组成的，这些部 分可以看作为s e g m e n t 。因此，邮件系统的备份源也是满足我们上面约定的层次 结构的。 定义2 1 备份源的级别：备份源是一个i i 级的数据。1 1 级数据是由1 2 级数 据构成，1 2 级数据是由1 3 级数据构成，而1 3 级数据是由字节流构成。特别的，我 们规定1 0 级数据是字节流数据，即一个l o 级数据就是一个字节。 在实际应用中，任何有结构的数据最终都是由字节流构成的。同理，任何一 级f f 的数据最终都是由级数据( 即字节流) 构成。 中山大学硕士学位论文备份系统中流式处理的行为分析及j e 捅件实现 为了讨论方便，我们将，称为d a t a s e t 级别，易称为n o d e 级别，l s 称为s e g m e n t 级别。 备份源即一个，级别( d a t a s e t 级别) 的数据。而，级另1 ( d a t a s e t 级别) 数据又是 由若干如级另i ( n o d e 级别) 数据构成；而易级7 s 1 ( n o d e 级别) 数据又是由若干1 3 级 另o ( s e g m e n t 级别) 数据构成。同时，任何一级的数据最终都是由字节流构成的。 2 1 2 归档文件的结构 由图1 1 ，我们知道，备份即数据源a 经过转换操作厂变成归档文件b ，恢 复即归档文件b 经过逆转换操作g 还原成a 。 由上一节的分析知，彳是由t e 级别的元素以树状结构构成的。我们对数据源 彳进行处理，最终会转化为对易级别的元素的逐一访问。 访问时，满足如下特点： 1 ) 所有树中结点被访问且只被访问一次。 2 ) 树的叶结点为最终要处理的数据，树的分支结点表示结点之间父子关 系。 【定义2 2 】数据源的偏序关系：数据源彳可以看作一个由若干易级别的元素 组成的集合。集合中元素存在两个二元关系，p 似和s 似一。p 似表示x 是y 的父亲。s “表示x 是y 的哥哥。特别规定关系p 似砂和关系s 阢矽是成立的。 图2 3 数据源示例 假设图2 3 是一个文件系统数据源的信息。数据源由爿、b ，c ，d 和e 这五 7 中山人学硕1 ：学位论文备份系统中流式处理的行为分析及其插件实现 个文件目录组成。c 是d 的父亲，故p 似驯。d 是e 的兄弟。备份数据源时， 结点是逐个备份的，因此d 和e 访问存在先后关系，不妨假设先访问d ，后访 问e 。故有关系s 何目成立。 值得注意的是，我们对数据源1 2 级的兄弟结点的访问是有先后顺序的，即兄 弟结点之间是有序的。 二元关系p 阮是偏序的。由定义知p 满足自反性。如果p 伍y ) a p ( y , 砂， 即x 是y 的父亲，同时y 是x 的父亲，显然石可，故关系p 是反对称的。如果p 阢 a p ( y , 矽，即z 是y 的父亲，y 是z 的父亲，由树状结构可以看出z 是z 的父亲， 因此p 阮矽成立，即p 关系满足传递性。综上，p 似是偏序关系。 二元关系5 阮是偏序的。由定义知s 满足自反性。如果s 阮a s ( y , 砂，即 x 是y 的哥哥，同时y 是石的哥哥，显然x 可，故关系s 是反对称的。如果j 伍 a s ( y , 矽，即x 是y 的哥哥，y 是z 的哥哥。因此五力z 有共同的父亲。 v x , y 副，j 似，那么存在3z 酬，使得p 伍砂和p 亿力成立。 从集合的角度来看，备份相当于，a - - ) b 。而恢复相当于g ：b - - ) a 。 性质2 1 归档文件b 的格式要满足保序关系。v 五y e a ，p 阮，那么 p 讯x ) 文y ) 鼓j 立ov x , y a 。s ( x y ) 。郡么s 纸x ) 文y ) ) 成立。 对数据源么的树状结构进行先序遍历，可以得到一个1 2 级所有元素的排列。 如果b 按该顺序存放数据，那么映射后b 对于偏序关系s 佴仍然是成立的。 图2 4 树状数据源转化为扁平结构的归档格式 至于映射后如何保证父子关系，大致有两种解决方法：1 ) 父亲记住所有孩 中山人学硕l 学位论文备份系统中流式处理的行为分析及其插件实现 子的长度。2 ) 在孩子的起止位置打上开始和结束标签。 由于归档文件要求能存储在磁带中，因此它对b 的存储结构提出了更高的 要求，导致上两种方法在实现时存在一些棘手的难题。但是，我们可以假定存在 一种归档结构，使得数据源彳经过转换后得到的归档文件b 对于关系ps 仍然满 足保序关系。 2 1 3流数据 【定义2 3 】流数据：是指由连续高速产生的、没有边界的大量数据元素所组 成的序列【4 1 。 流数据出现在许多应用中，诸如股市交易、网络检测、电话通信、传感器 网络等等。多媒体应用方面存在实时海量数据，包括视频流、音频流和通信数据 流等 5 1 。而流技术是多媒体领域中对远程媒体流实现实时播放的技术【6 1 。 令t 表示任一时间戳，a ，表示在该时间戳到达的数据，流数据可以表示成厂， a t _ ，a ，a t + h ，。区别于传统应用模型，流数据模型具有以下4 点共性：( 1 ) 数据实 时到达；( 2 ) 数据到达次序独立，不受应用系统所控制；( 3 ) 数据规模宏大且不能 预知其最大值；( 4 ) 数据一经处理，除非特意保存，否则不能被再次取出处理， 或者再次提取数据代价昂贵1 7 1 。 由于上述特性，流数据的处理只能扫描一遍数据。即数据一旦流过就不能 再次访问了。 备份中，数据源彳中结点的数据大小既可能很小，也可能很大。例如，文 件系统中，一个视频文件可能有几g 。显然，对这些数据处理时，我们没有办法 将数据一次性传给转换处理f o 假定，待处理结点d 十分大，以至于无法一次性加载入内存。因此，需要 将d 进行一次划分，得到一组先后有序的序列力，如九，z 为非负整数。显然， d = - d 玉磊。因此，d 的数据就组成了一个流数据。对于转换操作万它们是流 式地传进来的。从厂看来，每个数据么传入且仅传入一次，而传入数据块的个数 厂是无法预知的。 9 中山大学硕j ：学位论文 备份系统中流式处理的行为分析及其插件实现 【定义2 4 数据的划分：一块大数据d 经过一个划分，得到一个数据块序列 d 如一以，n 为非负整数。这个数据块序列即组成了一个流数据。 划分后的数据块西 数据d 图2 5 数据的划分 划分的标准可以是数据大小，也可以是结构信息，还可以是其它标准。例 如，可以按照一个固定大小( 1 k ) 将大数据切分成一个数据块序列；对于n t f s 文件，按照文件的不同流( 正文流、安全流、属性流和备用流等) 将这个大数据 切分成一个数据块序列：或者两个标准并用，即先按结构将大数据进行一个切分， 结构内按固定大小再进行切分由此得到一个新的数据块序列。 2 2流式处理 2 2 1 流式处理简述 定义2 5 】流式处理是一种特殊的数据处理，数据不断地流入该处理过程， 该处理过程不断地将处理后的数据流出，传给下一个流式处理。 流式处理有其特殊性，如： 1 ) 迭代性：大部分流式数据处理模块都要将整个数据集划分为一个个的数 据块，模块的每次调用处理一个数据块，对整个流的处理迭代完成。 2 ) 可逆性：许多算法都有还原算法或近似还原算法，即逆处理。 3 ) 孤立性：各个变换算法模块独立工作，很少调用其它变换算法模块。 4 ) 参数简单性：算法参数往往是一些简单数据结构，这些数据结构不依赖 于主控模块的数据结构，如很少使用内存指针。 流式处理需要满足如下要求【2 】： 1 0 中山大学硕上学位论文备份系统中流处理的行为分析及j e 插件实现 1 ) 在数据处理过程中，数据元素至多只能被处理一遍。即某一块数据一旦 流经该数据处理过程，就不会重复流入该数据处理。 2 ) 尽管传入处理过程的数据可能无穷无尽，但在数据处理过程中，对内存 的使用是有限的。 备份领域中，流式处理的输入数据是经过预处理的数据，这些处理包括【2 】： 1 ) 根据选择集、选项集、调度集、目标集和高级选项集等集合中的数据定 义得到精确的要备份的数据内容( 称为资源树) 的定义。 2 ) 读取这些数据，加上一些描述数据内容和性质的元数据，对数据进行包 裹。 3 ) 进行序列化处理，生成数据流。 如果不考虑系统性能，如安全性、传输速率等因素，这些数据可以直接传 输到存储介质，因为他们已经包含了基本备份恢复所需要的数据。本文所述的流 式处理，其目的是为了提高系统性能、增强系统功能特性。对于一个实用的软件 系统，系统性能和功能完整性，有着很重要的作用。 定义2 6 】连接操作：设某个流式处理的过程为，依次流经厂的数据序列为 d ，如磊，i t 为非负整数。记该处理过程为何，+ 以+ 圳。其中，”+ ”称为 连接操作。 记号厂似+ 击l 表示数据块d 和比依次传递给厂进行处理。 假定数据d 存在两个划分，分别得到两个数据块序列d ，如, t 3 ，和西，也西。 厂对第一个划分的流式处理为厂似j , t 2 + 圳，第二个为似，+ 而圳。 在不引起歧义的情况下，我们可以把连接操作“+ ”省略。r p f ( d ，比) 和厂p ，+ 以夕 的含义相同。 性质2 2 】划分等效性：d 是某个流式处理厂要处理的所有数据，d 通过两 个划分得到两个数据块序列，和口。其中，为d l , , t 2 ，磊，以为非负整数，为 和t l ，t 2 ，t m ，m 为非负整数。朋，+ 西+ g o = f ( t ，+ 幻+ 纠。 由此可知，朋，+ a 2 ) = f ( a d 2 ) 。肋+ 动表示d 被划分成两个数据块西和面， 分两次传给数据处理二而f ( a ：1 2 ) 表示两个数据d ，和如一次性传给数据处理乒 f ( a ，d 2 ) 相当于数据划分时只得到一个数据块。由切分的等效性，我们知道两者最 中山人学硕：i ：学位论文 备份系统中流式处理的行为分析及e 捅件实现 终的功效是一样的。故朋，+ d 2 ) = f ( d i d 2 ) 。 【定义2 7 子数据：有两个数据d 和d 。如果把d 和d 看作为两个字节流 组成的序列，而d 对应的序列是d 的子序列。这时，我们称d 是d 的子数据。 一 。i 数据d 图2 - 6 于数据 如果d 是d 的子数据，那么对于d 和d 分别存在一个划分，使得d 和d 得到两个数据块序列，和，并且是口的子集。 定义2 8 d 上的关系c ，c = f ， i 若西经过内存处理区域的时间 早于彤。特别的，规定d i c d i 。 由定义知，c 是自反的；若西c 碣，e jc d k ，则d i 先于吗经过内存处理区域， 碣先于巩经过内存处理区域，所以盔必先于以经过内存处理区，所以西c d k ， 故c 满足传递性；若d i c d j ，且d j c d i ，则西和弓一定是同一个数据块，即f 可， 故c 是反对称的。综上，d 中的关系c 是偏序。 集合d 是良序集合：d 中任意两个数据西，西以习) 不可能存在于内存处理 区域，否则它们是同一块数据。故d i 和西经过内存处理区域的时间必有先后关 系，故必有西c 西或e j c d i 。所以，c 同时也是全序关系，又数据序列是有限的， 故集合d 是良序集合。 性质2 3 流式处理中，数据块的独立性：厂是某个流式处理，d 是它要处理 的所有数据。d 经过一个划分得到一个流数据d ，d 2 磊，z 为非负整数。厂在处 理数据块西时，既不需要知道前面4 的全部数据，也不需要知道后面破的全部 数据。其中，f 刀，也可能聊 ”。 3 1 2 算子的基本操作 算子是一个数据处理的过程。显然，任何数据处理过程都需要使用一些资 源，例如消耗内存、使用设备等；同时任何数据处理过程都是需要使用一些变量 的。我们可以假定在进行真正数据处理之前存在一个初始化步聚，在这个步聚中， 它申请资源；在数据处理之后存在一个结束步聚，在这个步聚中，它释放资源。 因此任何数据处理过程，可以定义成图3 4 的三个步聚。 图3 4 数据处理的基本步聚 我们定义”初始化”步聚的目的是想将”数据处理”过程中需要的资源在”数据 处理”之前一次性地申请。当然，也可能存在只能在”数据处理”过程之中才能申 请到的资源。对于这种情况，我们可以将这些资源看作是”数据处理”过程中在该 步骤内自己维护的资源。因此，它并不影响我们的讨论。 显然，我们可以将算子的操作分解成”初始化”、”数据处理”和”结束”三个部 1 7 中山人学硕i ：学位论文备份系统中流处理的行为分析及】插件实现 分。即图3 5 所表示的意思。 一- - v h _ 。一。- h 数据处理 图3 5 算子的基本操作流程 在图3 5 中，我们对算子的运行做了如下假设：算子没有输入数据块时，数 据处理过程就宣告结束。这个假设对除读算子外的其它算子都是成立的。 读算子在没有输入数据块的情况下，自己也会有输出数据块。因此读算子 的数据处理结束是在数据读完的时候，即没有输出数据块之时。 n 图3 6 读算子的基本操作流程 对于读算子，它的操作流程应该是图3 - 6 所示的情况。读算子是一种十分特 中山大学硕上学位论文备份系统中流式处理的行为分析及其插件实现 殊的算子，但是它的特殊性并不会影响到我们对算子的分析。本节在没有特殊指 明的情况下，算子指的是非读算子的其它种类算子。 “算子的基本操作流程”这个图所表达的意思如下文。 假设有一个算子，算子级别仞= f 。d 为f j 级的一个数据。d 经过一个划 分后得到一个流数据d l , d 2 , 磊，n 为非负整数。我们将d 流式地传给厂得到了 一个流数据f 厶如t m , ，m 为非负整数。 厂的输入序列西，d e , 磊中，d l 是第一块输入数据，磊是最后一块数据数 据。从算子的基本操作流程中，我们注意到：我们在厂处理第一个数据块d l 之前 调用”初始化”步骤，为算子厂申请所需要的资源，如果可以的话。然后对于输入 的所有数据块依次调用”数据处理”步骤。在最后一个数据块磊处理完之后，我 们调用”结束”步骤，释放申请的资源。 算子厂在进行数据处理时都可能需要一个内存空间来存放输出的数据块。我 们不妨将这- - + 块内存叫作算子厂的输出缓冲区。 如果将算子厂看作是一个程序，该程序被其它程序调用来进行数据的流式处 理。那么算子厂的输出缓冲区，可能在厂所在的程序内部申请，也可能是在调用 程序中申请之后再传给厂使用。从内存管理的角度来看，前一种方式可能演化为 内存管理在被调程序中自己管理，后一种方式可能演化为内存管理由调用程序进 行集中管理。不管是两种方式中的哪一种方式，我们都可以认为该内存资源是在” 初始化”步骤中申请的，在”结束”步骤中释放的。 当算子处理最后一个输入数据块矗后，算子厂可能还有缓存的数据要输出， 即在”结束”步骤之前还存在一个输出数据块。在流式解压中存在这种情况。 为了更清楚地说明这一个”额外”输出数据块，我们不妨看下面这个例子。 假定某个算子厂待处理数据d ，经过一个划分后得到两个数据块d d 2 ，其中 d j 和以的大小分别是6 ，3 。假定算子厂每次能处理的最大数据块的大小为4 。那 么，对于输入数据块西显然有两个单元的数据被算子厂缓存起来了。当输入最后 一个数据块时，算子厂将缓存的两个单元数据与输入数据中两个单元的数据进行 拼接，并处理后得到一个输出数据块。显然，在最后一个数据块西传入给算子厂 得到一个输出数据块后，算子f 自身还缓存了一个单元的输入数据。对于这一个 1 9 中山大学硕士学位论文 备份系统中流式处理的行为分忻及j e 捅件实现 单元的输入数据当然可能处理后得到一个输出数据块，即出现我们所说的”额外” 数据块。 由此看来，图3 - 6 “算子的基本操作流程”中，还漏掉了一个操作。在最 后一个数据块处理完之后，我们还需要提供一个操作，让算子厂将缓存的数据处 理完后输出。即让算子厂有机会输出那个”额外”数据。 综上，我们可以将算子( 除读算子外) 的基本操作定义为图3 7 所示的操作。 n 1r 结束 图3 7 扩展后，算子的基本操作流程 定义3 1 】算子的基本操作：由上文的分析知，算子的基本操作有初始化、 数据处理、处理缓存的数据和结束这四个基本操作。为了方便讨论，我们将这四 个基本操作分别命名为i n i t ，f u n ，f i n a l i z e ，f i n i s h 四个操作。 四个基本操作的功能可以总结如下：操作i n i t 的功能是初始化算子，申请算 子需要的资源；操作f u n 和f i n a l i z e 是数据处理部分，对于输入的数据块进行处 理后得到输出数据块；f i n i s h 操作是结束算子，释放算子占用的资源。 这四个基本操作的运行顺序可由图3 8 的状态图表示出来。 2 0 中山人学顾。i j 学位论文备份系统中流式处理的行为分析及j e 插件实现 图3 8 算子的基本操作状态图 3 1 3 基本操作的若干性质 假定，算子厂对于每一个输入数据块d i ( i 一 i 西i ，即p 吲。 假定有一个备份系统，备份源么的数据流式地经过了一系列算子乃， 正以，得到归档文件b 。由于，备份系统最起码需要对数据进行拷贝，即一 定存在读取数据和写回数据这两个功能，即存在读算子和写算子。故m 2 。 的时间复杂度= d ( 歹( d ) ) = d 们俐+ o o e e ( d ) ) + + d 以仁缈d 俐+ d 编缈 i d i + i d i = 2 i d i 。 3 3 2 空间特性 设依次流入算子厂的数据序列为d ，d e , 如n 为非负整数。记厂的内存消耗 为c 记d = d 1 d 2 d 。 o 算子厂的数据处理操作p r o c e s s 所占用的空间c 由两部分组成：算法和数据 中山大学硕上学位论文备份系统中流式处理的行为分析及其插件实现 结构消耗的空间，、算子输出缓冲区占用的空间。西是算法和数据结构处理的 对象，因此，空间，的大小一般- 与1 4 1 有关。空间口存放着处理后的输出数据块。 由上一章对流数据的介绍，我们知道流数据是海量的。即流式处理输入的 数据块总长度i d i 是极大的。因此，空间复杂度m 必须小于i d l 。 由于i d l 理论上是可以无穷大的。如果m 随着l d i 的增大而增大，那么很快算 子厂将消耗完系统的所有可用内存资源。因此i d i 趋向无穷大时，m 不应该也趋向 无穷大。即存在一个正数，使得m = h 。 性质3 6 算子厂对d 的数据处理的时间复杂度m ，满足如下关系：m i d ， 且l i m m 存在。 i d i “ 算子厂消耗的内存空间大小远小于流数据d 的总长度，并且有一个合理的最 大值。一般而言，i l o l l 越大m 越大。如果某个数据处理过程不满足上述空间性 能要求，那么是不能被备份系统所使用的。 对于上一节中的备份系统，空间复杂度胙蚴，其中，尬为算子石的空 i = l 间复杂度。 3 3 3非流式处理转化为流式处理 数据处理有流式和非流式两种。非流式处理时，处理的数据是以一个整体的 形式传入的。常见的文件级的彳肼都是非流式。例如，对文件进行加密、压缩、 索引等。 非流式处理过程g 转化为流式处理过程厂的好处在于，减少数据处理过程中 的内存资源消耗。因为转化后待处理的数据不再是一个整体，而是经过一个划分 后的数据块序列。借用分而治之的思想，流式处理过程逐个处理数据块序列d j ， 以磊，而非流式处理过程g 则一次应对整个数据d 。 3 2 中山大学硕士学位论文备份系统中流处理的行为分析及j 捅件实现 相比非流式处理过程，流式处理过程存在一些缺点：1 ) 程序结构和控制流程 更复杂。由上文论述可知，流式处理过程p r o c e s s 是有状态的。它的实现增加了 开发人员的难度。2 ) 流式处理需要占用额外的空间资源。当流式处理厂在处理数 据