（计算机软件与理论专业论文）面向文件集流式处理的事务模型及其应用.pdf

面向文件集流式处理的事务模型及其应用摘要 论文题目：面向文件集流式处理的事务模型及其应用 专业：计算机软件与理论 硕士生：韦邕 指导老师：倪德明副教授 摘要 对文件集进行流式处理，是将具有树状结构的文件集合转化为线性结构的数 据块序列进行处理，这包括对树状结构的后续遍历和对单个文件的流式处理。这 种方式非常适合于对数据进行一系列预定义运算的应用，例如数据压缩、加密、 索引、统计和数据同步。然而，在一个包含大量文件的处理任务被意外中断后， 流式处理无法做到从中断点附近接着运行该任务，而是必须从头开始。我们希望 流式处理能从中断时刻前最近的一个文件开始，恢复执行任务。 在流式处理过程中，一份独立的文件会被分割成多个更小的数据块来进行处 理，这些数据块有次序地快速通过若干处理单元；当最后一个数据块以及它之前 的所有数据块都被处理完毕时，该独立文件才算被处理完毕。这个过程与数据库 中事务的处理过程类似。一个独立的事务由多个串行执行的操作组成，该事务执 行成功，当且仅当其包含的最后一个操作以及它之前的所有操作都执行成功。通 过事务机制，数据库系统可以处理对数据的操作被中断的情况，并维持数据的一 致性和可用性。因此，本文将数据库中的事务机制引入流式处理模型，通过将数 据处理任务“事务化，即把对一个独立文件的处理作为一个事务看待，使得流 式处理模型能够恢复执行被中断的任务。 本文先简单介绍了文件集流式处理的应用现状，接着通过半形式化方法，给 出一个已有的文件集流式处理系统的模型s p m f s 模型的详细描述，并分析 了它在处理被中断任务时的不足；然后，将数据库中的事务概念引入到文件集的 流式处理中，改进s p m f s 模型，提出了一个支持事务功能、可以恢复执行被中 断任务的文件集流式处理模型t s p m f s 模型；最后由t s p m f s 模型得到一 个新的流式处理系统，并展示了该系统在备份领域的一个应用。 面向文件集流式处理的事务模型及其应用摘要 关键词：文件集流式处理，任务中断，事务机制，恢复执行 面向文件集流式处理的事务模型及其应用 a b s t r a e t t i t l e ：t r a n s a c t i o n a ls t r e a m i n gp r o c e s s i n gm o d e lo ff i l es e ta n di t s a p p li c a t i o n m a j o r ： n a m e ： c o m p u t e rs o f t w a r ea n dt h e o r y w e iy o n g 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 t r e a m i n gp r o c e s s i n go ff i l es e ti so n ek i n do fd a t ap r o c e s s i n gt h a tt r a n s f e r st h e t r e e s t r u c t u r ef i l es e tt oal i n e a rs e q u e n c eo fd a mb l o c k sa n dd e a l sw i t hi t i ti n c l u d e s b o t l lt h et r a n s f o r m a t i o no fd a t af r o mt r e e - s t r u c t u r et ol i n e a rs e q u e n c ea n ds t r e a m i n g p r o c e s s i n go fas i n g l ef i l e s t r e a m i n gp r o c e s s i n go ff i l es e ti sag o o ds t r u c t u r ef o r a p p l i c a t i o n st h a tc a r r yo u tp r e d e f i n e dc o m p u t a t i o n so nd a t a ，f o re x a m p l e ，d a t a c o m p r e s s i o n ，d a t ae n c r y p t i o n ，i n d e x i n g ，s t a t i s t i c sa n dd a t as y n c h r o n i z a t i o n h o w e v e r , w h e nr e s t o r i n gp r o c e s s i n gat a s ko fl a r g ea m o u n to fd a t af r o mu n e x p e c t e di n t e r r u p t i o n ， s t r e a m i n gp r o c e s s i n go ff i l es e tc a n n o tg oo nr u n n i n gf r o mw h e r ei tw a ss t o p p e d i n s t e a d ，t h et a s kh a st os t a r ta l lo v e ra g a i n ，a n dal o to f t i m ei sw a s t e d d u r i n gt h ec d u r s eo fs t r e a m i n gp r o c e s s i n g ，af i l ei sd i v i d e di n t os e v e r a ls m a l l e r d a t ab l o c k s t h e s eb l o c k sg ot h o u g hs e v e r a lp r o c e s s i n gu n i t sq u i c k l ya n ds e q u e n t i a l l y t h ep r o c e s s i n gc o u r s eo ft h ef i l ei sn o tf i n i s h e du n t i li t sl a s tb l o c ka n db l o c k sb e f o r e t h el a s to n ea r ef i n i s h e dp r o c e s s i n g i ti sv e r ys i m i l a rt ot h ec o u r s eo fat r a n s a c t i o ni n d a t a b a s e w i t h i nat r a n s a c t i o n ，t h e r ec a nb eo n eo rm o r es m a l l e ro p e r a t i o n sw h i c ha r e e x e c u t e ds e q u e n t i a l l y at r a n s a c t i o ni sn o tf i n i s h e du n t i li t sl a s to p e r a t i o na n d o p e r a t i o n sb e f o r et h el a s to n ea r ef i n i s h e d a sar e s u l t ，w ei n t r o d u c et h et r a n s a c t i o n m e c h a n i s mf r o md a t a b a s et ot h em o d e lo fs t r e a m i n gp r o c e s s i n go ff i l es e t ，w en o w c o n s i d e rt h ep r o c e s s i n go fas i n g l ef i l ea sat r a n s a c t i o n ，w h i c he n a b l e st h em o d e lo f s t r e a m i n gp r o c e s s i n go ff i l es e tt or e s t o r ep r o c e s s i n ga ni n t e r r u p t e dt a s kf r o mw h e r ei t w a ss t o p p e d 1 1 1 面向文件集流式处理的事务模型及其应用 a b s t r a c t f i r s to fa l l ，t h i sa r t i c l ei n t r o d u c e st h es i t u a t i o no fa p p l i c a t i o n so fs t r e a m i n g p r o c e s s i n go ff i l es e t ，a n dt h e n i td e s c r i b e st h em o d e lo fa ne x i s t e ds y s t e mo f s t r e a m i n gp r o c e s s i n go ff i l es e t ( s p m f sm o d e l ) b yas e m i f o r m a l i z a t i o n a lw a y , w e c a ns e ef r o mt h e s ed e s c r i p t i o n sw h yt h es p m f sm o d e lc a n n o td e a lw i t hi n t e r r u p t e d m i s s i o n s s e c o n d l y , w ei n t r o d u c et h ec o n c e p to f ”t r a n s a c t i o n ”f r o md a t a b a s et o m o d i f ys p m f sm o d e l ，a sar e s u l t ，w ep r e s e n tan e wm o d e lc a l l e dt s p m f sm o d e l ， w h i c hc a nr e s t o r e sp r o c e s s i n go fi n t e r r u p t e dm i s s i o n s t h i r d l y , w ed e m o n s t r a t ea n a p p l i c a t i o nb a s e do nt h et s p m - f sm o d e li nt h ef i e l do fd a t ab a c k u p k e yw o r d s ：s t r e a m i n gp r o c e s s i n go ff i l es e t ，i n t e r r u p t e dm i s s i o n ，t r a n s a c t i o nm e c h a n i s m ， p r o c e s s i n gr e s t o r a t i o no fi n t e r r u p t e dm i s s i o n i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中己经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：串嘭 日期：冲年月弓i e t 导师签名：他诬明 日期：抽年6 月 面向文件集流式处理的事务模型及其应用第一章绪论 1 1 研究背景 第一章绪论弟一早珀比 进入2 l 世纪后，信息技术以日新月异的速度向前发展，由此而来的信息化 进程使得计算机巧 = ，) ，那么，关系数据库的事务机制可用下图说明 ( 图3 1 ) ： 图3 - 1 事务机制示意图 在图3 1 中，d b 组件中存放数据库数据，d b e x e c 组件接收事务请求并对 d b 组件进行操作( 读、写) ，t e x e c 组件执行事务功能，l o g r 组件存储事务玩 的日志。 系统正常运行时，多个事务并发执行。在事务开，完成其所有子操作并提交 1 9 面向文件集流式处理的事务模型及其应用第三章流式处理任务的事务化 后，数据库系统才将它的( 局部) 结果更新至数据库内，此时其它事务才能看见 矾的结果；在耽执行期间，数据库系统会记录与它相关的信息。 假设，时刻，数据库状态为d s i ( 一致状态) ，此时正要开始执行的事务为玩 一一为简单起见，我们假设同一时刻只有一个事务在运行；在经过，时间后，数 据库系统发生崩溃，此时事务乃，仅执行到步骤o p 括，数据库状态为d s o + j ) ( 不一 致状态) 。当系统重启后，为了清除未完成事务乃，对数据库的更新，将数据库状 态从d s ( t + j ) 恢复到d s t ，事务组件会执行回滚操作，这包括：“提取最近一次未完 成事务信息”、“确定需执行撤销操作的范围、“执行撤销操作”三个步骤( 表格 3 3 ) 。 表格3 - 3 简单的回滚操作步骤 而当系统崩溃后执行前滚操作时，数据库系统对日志中记录的已提交、但是 更新未写入数据库的事务执行“重新执行”操作，次序与原执行次序一致，这一 般只涉及靠近崩溃点的前几个事务，开销较小。 3 2 流式处理任务向事务的映射1 2 】【1 3 】【1 4 1 通过“事务”的概念，数据库系统把对数据的操作序列划分为一个个原子单 元、使之满足a c i d 性，并保存关于事务执行的日志，使得数据库系统具备将数 据从系统崩溃中恢复的能力。在恢复过程中，数据库系统只需要处理靠近系统崩 溃点的几次事务对数据的更新，开销较小，避免了由于一次崩溃而导致数据不可 用，实际上保护了数据库内容从建立到当前时刻所执行的绝大部分操作的效果 面向文件集流式处理的事务模型及其应用第三章流式处理任务的事务化 ( a c i d 性质中的持久性) 。 反观s p m f s 模型，它处理的数据对象是流式数据，是一个高速、连续、没 有组织结构的数据块序列。也正是因为数据块的散乱性、孤立性，该模型对数据 块的到达情况和进度无法进行标识和记录，也就意味着处理任务的进度无法被标 识和记录。 3 2 1 流式处理事务 事务是对操作序列的一种组织和管理手段，它使得系统的任务对象易于被管 理。我们知道，s p m f s 模型将一份独立文件分为若干更小的数据块进行处理。 假设有一段流式数据岛，岛= 触，如，彬，它们属于文件e 。s p m f s 模型 在处理过程中，无法注意到该流式数据段的逻辑起始( 数据块西和磊的到来) 。 我们通过一些方法( 例如添加元数据块) 对眈进行标识，使之成为粒度更大一 级的数据单元( 最小粒度的数据为数据块) ( 图3 2 ) ，并把s p m f s 模型对数据 的敏感度也提升一级，使它能够把对岛的处理操作o p l ，o p 2 , o p q 当作一个整体 来对待。 属于文擘t - e i 的数据块 属于文乍t - e i + 2 的数据块 ，“6 、广、厂一一、- 、 口口豳口口口口l 口口口口| | 口口0 0 0 口卜- 口口口 k k ，。，k - ， 属于文件e i + 的数据块 图3 2 对流式数据进行组织 【定义3 - 1 1 流式处理事务。一个流式处理事务是一个集合，它的元素是对文 件e 的数据块进行处理的操作( 图3 3 ) 。我们用符号s t r 代表流式处理事务，有 s t r = 陆o p l ，o p 2 , o p j ，q 为正整数。“流式处理事务”可简称为“流式事务 。 2 l 面向文件集流式处理的事务模型及其应用第三章流式处理任务的事务化 居 于 文 件 e 的 数 据 块 处 理 文 件 吟南 事 务 s t r 图3 - 3 流式处理任务 s p m f s 模型中的大函数c 包含多个算子，它对文件e 的一块数据讲的处理 印，可能包含对若干算子的使用。有了流式事务的概念，s p m f s 模型处理的任务 单元从数据块变为事务，它将以事务为单位进行调度、管理和信息记录，它将对 输入数据拥有更好的管理和掌控，因此，文件集流式处理变为对文件集流式事务 的处理。 【定义3 - 2 1 事务流。s p m f s 模型处理的是高速产生、连续不断且无法预知其 边界的流式事务序列，这个序列称为事务流( 图3 4 ) ，我们用符号s t rs t r e a m 代表事务流。 s 仉 s r r 2 s 7 r 舸 回国- 圃o o o o 吟 i 口o o 口h 口口口口1 | 匹 _ _ - - - - _ - _ - _ _ - - 一- _ _ - _ _ _ - - _ _ ，1 - _ 一 图3 4 事务流 口口口口口口 显然，事务流也是流式数据，它的数据元素是流式事务，它也具备一般流式 数据的性质。 3 2 2 流式事务的a c i d 性质 在关系数据库中，事务的a c i d 性质保证了数据库数据在被事务修改后的一 致性；那么在文件集流式处理中，流式事务的a c i d 性质也必须能保证结果文件 的一致性和可用性。下面，我们对比表格3 1 来讨论在文件集流式处理中，流式 面向文件集流式处理的事务模型及其应用第三章流式处理任务的事务化 事务a c i d 性质的具体内容。 i 定理3 - 1 1 流式事务的原子性( a ) ：对于一个流式事务s t r ，要么其所有操 作哪都执行成功这里的“成功”指操作o p ，中使用的每一个算子乃的执行 也都成功、并且它们的更新已经追加至结果集否则即使只有个操作o p , 没 有执行成功，其它操作对结果的更新也不会被保留，结果集仍然保持事务s t r 开 始执行时的状态。 【定理3 2 】流式事务的一致性( c ) ：在流式事务s t r 开始执行时，结果集的 状态是一致的；在s t r 执行结束时，不管它是否对结果集产生更新，这些结果仍 然保持一致。结果集的一致性是指结果文件本身结构的完整性。 【定理3 3 】流式事务的隔离性( i ) ：由于文件集流式处理是串行地处理数据 块，因此也是串行地处理流式事务，每一时刻只有一个事务在运行，自然地满足 隔离性。 【定理3 4 1 流式事务的持久性( d ) ：一个成功执行的流式事务，它的结果作 为输出文件的一部分存在，并不会因为系统崩溃而丢失。 3 3t s p m f s 模型 在前面，我们介绍了事务机制，并完成了“流式处理任务”向“流式事务” 的转变，替换了s p m f s 模型处理的数据类型。由于有了流式事务的概念，原本 散乱的流式数据有了新的组织方式，它们更加易于被管理；对于s p m f s 模型来 说，在为添加事务功能打下基础的同时，也要求自身进行扩展以适应新的数