（计算机应用技术专业论文）面向服务的系统悔改恢复技术的研究与实现.pdf

哈尔滨t 稃，i 学硕十学伊论文 摘要 随着计算机网络技术的应用越来越广泛，各种网络中的应用服务也变得 越来越复杂，其运行变得脆弱而不可靠，与网络服务相关的故障变得司空见 惯。而目前在这些引起系统故障的因素中，人为错误已经超越了软、硬件失 效成为最主要的原因，因此，如何解决由人为错误引起的系统故障问题又摆 在了人们的面前。本文研究的重点即是使用系统级的悔改( u n d o ) 恢复技术将 服务系统从人为错误所造成的故障中快速恢复出来。系统级的悔改机制为操 作者提供了宽松的容错环境和回溯修复的能力，大大降低了系统日常管理维 护期间故障恢复的难度和代价，减小了m t t r ，并最终提高了服务系统的可 靠性。 本文首先对面向服务的系统级u n d o 机制进行了深入的分析，包括了与 u n d o 机制相关的基本概念和u n d o 系统的设计方法，然后在此基础上提出了 一个基于3 r 模型的通用u n d o 系统结构，并对其中关键的功能单元进行了设 计与实现。此外本文又在此基本框架之上针对分布式服务系统进行了结构和 功能上的扩展，重点对交互日志结构和交互域重放算法的改进进行了初步探 讨。在总结了相关研究的基础上，本文从面向u n d o 的服务设计准则和通用 的服务设计准则两个方面分别展开讨论，提出了一系列可u n d o 系统的设计 准则，为设计可u n d o 服务提供了一定依据。最后本文以在线拍卖服务为目 标系统对u n d o 系统进行了具体实现，并通过相关测试对其进行了验证。 关键词：悔改；回溯修复；人为错误；3 r 模型 哈尔滨t 程大学硕士学伊论文 a b s t r a c t w i t ht h ea p p l i c a t i o no fc o m p u t e rn e t w o r kt e c h n o l o g ym o r ew i d e l y , v a r i o u s n e t w o r ks e r v i c e sh a v eb e c o m ei n c r e a s i n g l yc o m p l e xa n df r a g i l e ，a n dt h ef a i l u r e s r e l a t e dt on e t w o r ks e r v i c e sh a v eb e c o m ec o m m o n p l a c e a tp r e s e n t ，h u m a ne r r o r h a sg o n eb e y o n ds o f t w a r ea n dh a r d w a r ef a i l u r et ob e c o m et h em o s ti m p o r t a n t f a c t o rw h i c hl e a d st os y s t e mf a i l u r e s ，t h e r e f o r e ，h o wt os o l v et h es y s t e mf a i l u r e s c a u s e db yh u m a ne r r o rh a sl a i na h e a do fp e o p l e t h u s ，s y s t e m - w i d eu n d o t e c h n i q u e sa r ep r e s e n t e dt or e s t o r es e r v i c es y s t e mf r o mf a i l u r e sc a u s e db yh u m a n e r r o r r a p i d l y s y s t e m - w i d eu n d o m e c h a n i s mp r o v i d e s o p e r a t o r s ar e l a x e d f a u l t - t o l e r a n te n v i r o n m e n ta n d a b i l i t y t o r e t r o a c t i v e l yr e p a i r , s i g n i f i c a n t l y r e d u c i n gt h ed i f f i c u l t ya n dc o s to ff a i l u r e sr e c o v e r yd u r i n gt h ed a i l ys y s t e m m a n a g e m e n ta n dm a i n t e n a n c e ，d e c r e a s i n gt h em t t r ，u l t i m a t e l yi m p r o v i n gt h e d e p e n d a b i l i t yo fs e r v i c es y s t e m f i r s t l y , a l li n - d e p t ha n a l y s i s o fs e r v i c e o r i e n t e d s y s t e m - w i d e u n d o m e c h a n i s mi sm a d e ，i n c l u d i n gb a s i cc o n c e p t sr e l a t e dt ou n d om e c h a n i s ma n d d e s i g nm e t h o d o l o g yo fu n d os y s t e m ，a n do nt h i sb a s i sag e n e r a lu n d os y s t e m a r c h i t e c t u r eb a s e do n3 rm o d e li sp u tf o r w a r d ，i nw h i c ht h ek e ym o d u l e sa r e d e s i g n e da n dr e a l i z e d f u r t h e r m o r e ，a ne x p a n s i o no ft h eb a s i cf r a m e w o r kf o r d i s t r i b u t e ds e r v i c e ss y s t e mi sr e s e a r c h e d ，w i t ht h ei m p r o v e m e n to fi n t e r a c t i v el o g s t r u c t u r e sa n dr e p l a ya l g o r i t h md i s c u s s e dp r e l i m i n a r i l y b a s e do nt h ec o n c l u s i o n o fr e l e v a n tr e s e a r c h e sas e r i e so fg u i d e l i n e sf o ru n d o a b l es y s t e md e s i g na r e p r e s e n t e d ，i n c l u d i n gu n d o - s p e c i f i cs e r v i c ed e s i g ng u i d e l i n e sa n dg e n e r a ls e r v i c e d e s i g ng u i d e l i n e s f i n a l l y , a ni m p l e m e n t a t i o nm e t h o do fu n d os y s t e mt a r g e t e da t o n l i n ea u c t i o ns e r v i c ei sd i s c u s s e d ，a n di sv e r i f i e db yr e l e v a n tt e s t s k e y w o r d s ：u n d o ；r e t r o a c t i v e l yr e p a i r ；h u m a ne r r o r ；, 3 rm o d e l 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：扩7 赴 日期：沙舸1 年；月y 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、 作者( 签字) ：忿 e l 期：一年7 月r e t 期：1 年月7 导师( 签- 7 - ) 坪；月 哈尔滨t 秤7 j 学硕十学伊论文 1 1 课题目的和意义 第1 章绪论 随着数字信息的存储、处理和传播逐渐成为现代社会生活不可或缺的部 分，计算机系统的应用已经越来越广泛，并且逐渐向分布式、异构型的方向 发展。e m a i l ，电子商务，万维网等应用服务都建立在一系列大规模、复杂 的互联系统之上，然而这也给系统的设计者和管理者带来了前所未有的压力 今天的服务系统必须要求保持2 4 7 小时的稳定运行。一旦系统出现故 障，企业和客户的损失将是十分严重的：有研究表明每小时停机将使像 a m a z o n c o r n 和e b a y 这样的电子商务网站付出几十万美元的代价，而给依靠 信息系统运行的证券公司则带来上百万美元的经济损失 1 】。因此，提高计算 机系统的可靠性成为了现代网络应用的迫切需要。 然而长期以来，人们一直将大量的研究工作集中在了提高计算机系统的 软件和硬件的可靠性上，而忽视了系统可靠性中的另一个至关重要的因素一 一人类操作者【2 】。因为目前几乎所有的大型系统都离不开人类的管理与维护， 如软、硬件的配置与升级，以及故障的诊断与修复等，然而，众所周知的是， 人类也会犯错误，即使是经过高度训练的专业人员，也会由于种种原因而不 可避免地犯错误【3 】 4 1 。有研究表吲5 1 ，人为错误已经成为目前引起服务系统停 机的最主要原因( 如图1 1 所示) 。因此，如何解决由人为错误带来的系统失 效问题又摆在了人们的面前。 本课题研究的重点就是使用系统级的悔改恢复技术对由人为操作失误所 造成的服务系统故障进行快速恢复。有研究表明【6 】，操作者在犯错误后可以 立即自检出其中7 0 到8 3 的错误，因此悔改机制为操作者在发现错误后能 立即对错误进行重新修正提供了可能性。而面向服务系统的悔改机制则又为 操作者提供了一个宽松的容错环境和回溯修复的能力，使操作者( 如系统管 哈尔滨工程大学硕士学位论文 理员) 可以对系统日常管理维护( 如系统升级、重配置或抵御外部痛毒、黑 客攻击等) 期间发生的人为操作失误，甚至是也可以对由软件b u g 或硬件引 起的系统服务状态故障进行修复，并且这种修复并不局限于程序的框架下， 而是允许操作者在系统范围内通过改变过去的状态来对现有的问题进行修 复，从而大大降低系统恢复的难度和代价，简化操作者的维护工作，最终降 低m t t r ，提高服务系统的可靠性。 图1 1i n t e m e t l 务中各种停机故障的原因及其修复时间比例图 1 2 国内外研究现状 悔改( u n d o ) 技术在应用程序领域( 如文字处理、电子表格以及计算机 辅助设计软件等) 【卫嘲和专用系统领域( 如数据库系统管理和分布式系统容错 设计等) 1 的应用己相对成熟，但其实际应用都存在着不同程度的局限性 不是对系统状态的故障无能为力，就是只是一种有针对性的内部恢复工 具，并不能对人为错误进行纠正。除此之外，现有的系统级u n d o 技术多为 桌面系统设计，如r o x i o 的g o b a e k e “】，i b m x p o i n t 的r a p i dr e s t o r e ”】， m i c r o s o f 【w i n d o w s 的s y s t e mr e s t o r e l l 卅以及v m w r r e 的s n a p s h o t m a n a g e r ! 等，这些工具大多仅是简单地将系统状态恢复到先前的某个状态， 因此用户在此期间所做的工作都将会丢失，这对于桌面系统的个人用户来说 可能是可以接受的，而对于存在众多用户的服务系统来说，由于系统操作者 的u n d o 操作而使其他终端用户的工作状态丢失则是不可接受的。 t 哈尔滨t 程久学硕十学位论文 在国外，来自斯坦福大学和加利福尼亚大学伯克利分校的一个研究小组 叫o c ( r e c o v e r y o r i e n t e dc o m p u t i n g ) 项目组己对服务系统的u n d o 技术 作了较为深入的研究【1 5 】【1 6 】【1 7 1 。面向恢复的u n d o 机制的目的就是为操作者提 供在检查到错误后能够进行回溯修复的能力，为此r o c 研究人员设计了“3 r 模型：回卷( r e w i n d ) 、修复( r e p a i r ) 、重放( r e p l a y ) - - - 阶段模型。在回卷阶段 所有的系统状态( 从操作系统到上层应用) 都回退到先前的一个状态上，在 修复阶段由操作员对系统状态进行必要的改动，在最后重放阶段修正后的系 统把记录下的用户操作重放，从而达到系统恢复的目的。 研究人员在理论研究的基础上设计了一个e m a i l 系统的原型机【1 7 】【1 8 】，该 系统可为操作者提供了系统级u n d o 功能。如图1 2 所示，u n d o 功能作为外 层包围着一个现有的、未经修改的基于l m a p 和s m t p 的邮件服务器，u n d o 代理负责截获用户与e m a i l 服务之间的协议层的交互，并记录相关日志信息； 另外在服务下方的非覆盖写存储层( n o n o v e r w r i t i n gs t o r a g e ) 负责保存用于回 卷的系统物理硬状态。由此结合“3 r ”模型，就可以使操作者在发现故障后 能够尽快修复系统，从而有效降低m t t r ，提高系统可靠性。 u n d ol a y e r 图1 2 具有u n d o 功能的e m a i l 系统结构 哈尔滨t 程大学硕十学何论文 国内近几年虽然已有若干r o c 技术相关的文献【1 9 】【2 0 】【2 l 】，但多是以引述 和介绍为主，尤其是其中的系统级u n d o 技术，尚且未有深入的理论及应用 研究。 1 3 论文的主要工作和组织结构 本文在对系统级悔改技术深入研究的基础上设计并实现了一个通用的面 向服务的u n d o 系统，并对实现此u n d o 系统所涉及的关键技术进行了深入而 详细的讨论，此外还将u n d o 系统在分布式系统领域中作了初步扩展。最后 本文为可u n d o 系统的设计提出了一系列评价准则，这些准则对可u n d o 系统 的设计起到了一定的指导和辅助作用。 论文的结构安排如下： 第2 章简要介绍了u n d o 机制空间模型的三要素和3 r 模型，然后对3 r 模型中不一致性问题的产生做了重点介绍。 第3 章首先对u n d o 系统的设计点进行了分析和假设，并据此提出了一 个通用的u n d o 系统结构。然后重点对u n d o 系统设计中涉及的关键技术进行 了详细的阐述。 第4 章在先前提出的u n d o 系统结构的基础上，针对分布式服务系统进 行了扩展。本章重点对交互域的结构进行了扩展，并对交互日志的结构和交 互域的重放算法进行了初步的改进。 第5 章从面向u n d o 的服务设计准则和通用的服务设计准则两个方面分 别展开讨论，提出了一系列可u n d o 系统的设计准则。这些服务设计准则为 设计可u n d o 服务提供了依据，除此之外也可以对现有服务的u n d o 功能做出 评价。 第6 章以r u b i s 拍卖服务为目标系统，为其设计实现一个u n d o 系统。 本章主要是以先前提出的u n d o 基本结构为基础对r u b i s 系统中的交互谓词 和外部一致性策略进行了设计和实现，并通过相关测试对其进行了验证，最 后对测试结果进行了分析。 4 哈尔一只- - 仟r n 人学硕十学伊论文 第2 章面向服务的u n d o 机制与3 r 模型 2 1u n d o 机制的空间模型 u n d o 机制的空间模型共包含三个最基本的要素：时序模型、状态模型和 外部成员模型，其中每个要素都包含多种可选择的属性，从这些属性中，可 以找到一个u n d o 机制的最理想定位( 如图2 1 所示) ，每种要素及其属性将 在后面作具体解释。 基于命令 混合方式 基于状态 忽略 不一致性 不 不_ 致眭 、 图2 1u n d o 机制的空间模型及理想定位图 型、堕 哈尔滨1 ：稃夕：学硕十学伊论文 2 1 1时序模型 时序模型描述u n d o 系统中的历史记录的时间顺序结构，也就是时间轴 ( t i m e l i n e ) 的结构。最简单的时间轴结构就是单点( s i n g l e - p o i n t ) 结构，即时间轴 上仅能保存一个历史记录，在新记录产生时，上一次记录就会被覆盖。其次 是线一 生( 1 i n e a r ) 结构，即所有历史记录在给定时间内都是呈线性排列，也就是 说所有记录都在一条时间轴上。而最复杂的则是多分支( b r a n c h i n g ) 结构，即 所有历史记录呈树状排列，也就是说每个记录都可能存在于若干条不同的时 间轴上。此外，每种结构还可根据时间轴上的历史记录是否是可更改的，即 可以对时间轴上的历史记录进行添加、删除、编辑或调序等操作，从而分为 可编辑类型和不可编辑类型【2 2 】。最理想的结构就是支持多分支可编辑类型的 时间轴结构，因为这为操作者解决各种不常见的异常或问题提供了方便 多分支结构可以给操作者提供了尝试多种方案的能力，而可编辑性则可使操 作者对时间轴的控制更加灵活。 2 1 2 状态模型 状态模型描述u n d o 模型如何表现( 记录) 系统状态的改变。一种方式 是基于命令( c o m m a n d b a s e d ) 的方式，即记录改变系统状态的逻辑命令或操 作，另一种方式是基于状态( s t a t e b a s e d ) 的方式，即对系统状态进行物理记录， 可以是存储整个系统状态的完全拷贝，也可以是仅存储上次历史记录状态中 改变的部分。最理想的方式则是混合型( h y b r i d ) 歹y 式2 3 1 ，即既有基于命令的方 式，又有基于状态的方式，而且每种方式都有不同的用途：使用基于命令的 方式可以让操作者对历史记录中的具体事件一目了然，但用于u n d o 过程中 则会产生许多限制( 如必须存在相应逆向操作等) ，因此更适用于r e d o 过程； 而基于状态的方式则可以使操作者忽略系统状态改变的细节，从而不用考虑 操作或命令本身的正确性，因此适用于u n d o 而不适用于r e d o 过程。由此可 见，混合方式集基于命令的方式和基于状态的方式两者优点于一身，是最理 哈尔演t 稃了：学硕+ 学位论文 想的状态记录方式。 2 1 3 外部成员模型 外部成员模型描述处理外部成员可见的不一致性问题的方式。与应用级 u n d o 不同，系统级u n d o ( 尤其是在服务系统中) 还有一个不可忽略的因素 外部成员。无论是在应用程序中，还是在服务系统中，每个u n d o 系统 都有一个对应的u n d o 埘1 8 】( 如图2 2 所示) ，这个u n d o 域限定了u n d o 系统 的作用范围：在界限以内，是服务系统内部的时间域，状态域，以及操纵时 间域和状态域的内部成员，如系统管理员；在界限之外，服务系统外的时间 域，状态域，以及其对应的外部成员，如终端用户，或其他与其交互的独立 系统。 ( a ) 应用程序的u n d o 域( b ) 服务系统的u n d o 域 图2 2 应用程序和服务系统的u n d o 域 在应用程序的u n d o 域中，不存在外部成员问题，因为其外部成员与内 部成员是相同的，即程序的操作者与观察者是同一个人都是用户本身， 因此操作者清楚地把握着u n d o 域内外当前所处的状态，不会对u n d o 过程的 结果产生疑惑。而对于服务系统的u n d o 域来说，分别处于u n d o 域的内部和 哈尔滨t 程大学硕十学位论文 外部的系统管理员和终端用户都有着各自独立的时间轴，而且处于外部的终 端用户完全不能察觉内部的管理员对系统所做的u n d o 操作，以及由此引发 的时间轴偏差和状态不一致问题。 对于此外部成员可见的不一致性问题，最简单的处理方式就是直接忽略 这种不一致性，即不考虑外部成员。但这种方式仅适用于外部成员对不一致 性要求极为宽松的环境下，因此不适用于系统级u n d o 模型。另一种方式则 是阻止不一致性，即阻止任何将会产生不一致性问题的u n d o 操作，但使用 这种方式的结果是使系统仅能u n d o 到最近一次与终端用户交互的位置，因 此这将大大限制u n d o 系统的实际作用。最理想的方式就是管理这种不一致 性，即在u n d o 过程中，u n d o 系统对是否产生了外部成员可见的不一致进行 检测，一旦发现有不一致问题产生，就对外部成员采取相应处理措施，如对 终端用户进行补偿，或对与其交互其他u n d o 系统进行u n d o 传播。 2 23 r 模型与不一致 生问题 如前所述，系统级u n d o 机制同应用级u n d o 机制最大的区别就在于其 u n d o 域外存在不可忽视的外部成员，如图1 2 所示。为了方便描述，要对图 1 2 ( b ) 的u n d o 域进行进一步细化将外部成员同系统交互所产生的状态和 数据从系统状态中分离开来。如图2 3 所示，原来单独的u n d o 域被分为两层， 形成一种嵌套式的u n d o 域，其中内层的u n d o 域在逻辑上包含着服务系统中 的外部成员的交互状态，而外层的u n d o 域则包含着系统状态以及内层的 u n d o 域。外部成员透过外层u n d o 域直接同内层u n d o 域中的应用服务进行 交互，而系统管理员则同时与两层u n d o 域进行控制。 哈尔演t 稃大学硕十学伊论文 图2 3嵌套u n d o 域 现在在此嵌套u n d o 域的基础之上，就可以利用3 r 模型一一回卷 ( r e w i n d ) 、修复( r e p a i r ) $ d 重放( r e p l a y ) - - - 阶段模型来对整个恢复过程进行描 述： 回卷阶段：在故障发生后，系统管理员将嵌套u n d o 域中的内层和外 层状态全部回滚到一个先前正确的状态，这个状态既包括系统级状态 如操作系统、应用服务以及配置文件等，又包括应用级状态如外部成 员的数据等。 修复阶段：系统管理员可以有选择的进行任何需要的修复工作。这一 阶段给操作者提供了尽可能宽松的环境，以保证在调整系统时的灵活 性：除了直接对先前的错误操作进行更正，如修正错误的配置，重试 不成功的升级操作等，此外还可以对先前管理员的操作记录进行调 整，修改错误的操作序列，然后利用基于命令的r e d o 进行来完成修 复工作。 重放阶段：在系统修复之后，所有外部成员同内层u n d o 域的交互都 哈尔演t 稃大学硕十学伊论文 会按照时间轴日志中记录的操作重新执行。因此，先前在回卷阶段因 随系统状态一并回卷而丢失的外部成员状态都会在操作重新执行后 得到恢复，从而完成整个修复过程。 所有的这三个阶段都为了达到有效地将操作者的错误进行回溯修复的目 的，任何一个环节都不能缺失：若没有回卷阶段，那么由错误引发的状态改 变就不能撤销，因此系统也将无法恢复；若没有修复阶段，则错误将无法纠 正，因为如果没有人为纠正，错误不可能自己消失；同样若没有重放阶段， 则外部成员在回卷前的状态都将会丢失。 由此看来，3 r 模型给操作者提供了可回溯修复的能力，即允许操作者改 变系统过去的状态来对现有的问题进行修复，并通过重新执行来将修复的结 果向前传播从而消除先前错误对系统状态造成的影响。 然而，就在3 r 模型为操作者提供方便的回溯修复能力的同时，也引出 了一个不可避免的问题：如果系统状态由于修复操作或仅仅是因为回卷就发 生了足够大的变化，那么在重放阶段就可能发生执行失败或者产生原先执行 不同的结果。这种情况就被称为不一致性问题【i8 1 。 产生不一致性问题的原因是由于系统在修复阶段内的状态改变影响了其 对外部成员交互的处理，使内层u n d o 域的时间轴在重放过程中向一个不同 于原先执行期间的时间分支发展。如果这种问题未经处理就被直接输出，则 会将这种不一致性外部化，如图2 4 所示，系统在t = 3 的时刻向外部成员发 送一次消息，在t = 6 的时刻之后，系统状态回卷到了t = l 的时刻，在进行必 要的修复后，开始重放过程，然而重新执行后的时间轴并没有按照原来的方 向发展，而是产生了不同的新数据，并在t = 7 的时刻发送给了外部成员，因 此外部成员就会看到与先前t = 3 的时刻完全不同的输出结果。 1 0 哈尔滨t 程大学硕十学伊论文 内 图2 4 不一致性问题的产生及外部化 处理不一致性问题是设计系统级u n d o 模型所要解决的最大难题。由于 3 r 模型给操作者提供了可回溯修复的能力，并允许其在修复阶段对系统做任 意的修改，因此在这种情况下，不一致性问题是不可避免的。解决不一致性 问题最适合的方法就是对这种不一致性进行管理，即在这种不一致性暴露于 外部成员时，通过一定的补偿( c o m p e n s a t i n g ) 动作【2 4 j 来消除或减轻由不一致所 造成的影响。补偿动作的执行如下：在重放过程开始后，相关执行模块从历 史记录( 如日志) 中读取已被统一封装处理的交互操作信息，然后调用一个 一致性判定方法来比较重放过程的执行结果和原始执行结果，如果比较结果 是一致的，则输出这个结果；如果是不一致的，则将调用补偿方法。补偿方 法将对检测到的不一致按照定义的补偿策略进行包括忽略不一致，采取相关 动作减轻不一致，和采用直接或间接的方法来解释不一致等补偿动作。另外， 如果这个产生不致性的操作与随后记录中的操作有相关性，即后者的执行 依赖于前者，这时就需要调用压制方法来改变其后操作的执行，这种改变包 括取消原有操作的执行，重构原有操作意图并执行一个新的操作等。需要注 哈尔演t 干早大学硕十学伊论文 意的是，补偿动作中的补偿方法和压制方法都是针对具体服务的，因此对于 不同服务的不同应用协议，在设计时需要考虑相应的补偿动作和策略。 2 3 面向独立服务与面向分布式服务的u n d o 系统 独立服务系统是指一类可以完全由一个单独的u n d o 域包围且其外部成 员仅由人类终端用户组成的服务系统，如图2 5 所示。这类系统包括面向通 信的服务，如e m a i l 服务、消息服务以及新闻组等；商业相关的服务如网上 拍卖、集中式网上商店等；以及大多数信息检索服务，如搜索引擎，档案检 索和新闻传播服务等。在此类系统中，外部成员是以请求响应方式与系统交 互，系统的外部输出仅为响应外部成员请求。在u n d o 过程中产生的外部不 一致问题可以通过事先定义好的补偿动作来解决，然而由于独立服务系统的 外部成员仅由人类组成，导致了补偿动作的一些特殊性人类不同于计算 机系统，一旦有不一致性问题产生，不可能通过补偿动作来抹除先前已暴露 于人类用户的信息，但另一方面，人类却有强于计算机系统的内在的逻辑容 忍性，可以接受并不是严格一致的信息。因此，面向人类终端用户的补偿策 略就会相对宽松灵活：针对不同的不一致情况，既可以使用完整的补偿动作， 也可仅用引导性的说明来帮助人类用户进行自我调整。 图2 5 独立服务系统f l 勺u n d o 域示意图 哈尔滨t 程大学硕十学伊论文 分布式服务系统是指类通过几种运行在独立节点的服务相互协作，来 完成一个更复杂更强大的服务的系统。其中每个服务节点都包含其各自的物 理硬状态，维护着各自的时间轴状态，并且拥有各自独立的u n d o 功能，即 拥有各自独立的u n d o 域，如图2 6 所示。因此个服务节点的u n d o 行为势 必会对服务系统中的其他节点造成影响，从而影响整个系统状态的一致性。 针对分布式服务系统u n d o 过程中产生的不一致问题，有以下两种解决方案： 一种是针对具有明显补偿关系的u n d o 域节点：在一个节点进行u n d o 操作之后，向其他受影响的节点发送补偿信息，这些受影响的节点在 接到补偿信息之后，将按照预先定义的不一致性补偿方式进行调整， 即将收到的补偿信息作为前一节点u n d o 过程的结果来处理，此方式 称为非协调式( u n c o o r d i n a t e d ) j b 偿。这种方法与独立服务系统中的补 偿方法类似，优点是除了u n d o 节点，其他节点不需要进行回卷和重 放操作，因此代价很小；缺点是与其交互的节点必须要能够忍受宽松 的一致性补偿策略条件的定义。 另一种方式是针对不具有明显补偿关系的u n d o 域节点：在一个节点 进行u n d o 操作后，其他受影响的节点要将时间轴重新同步到与前一 节点产生不一致的时刻，在新的状态下再进行重放来消除不一致问 题，此方式称为协调式( c o o r d i n a t e d ) = i ；b 偿。这种方法的优点是没有需 要忍受补偿策略条件的限制，因此适用范围更加广泛；缺点是此方法 可能会产生潜在的“多米诺”效应【1o ，大大增加了系统恢复的开销。 哈尔演t 稃大学硕+ 学伊论文 2 4 本章小结 图2 6 分布式服务系统的u n d o 域示意图 本章首先介绍了u n d o 机制空间模型的三要素，包括时序模型，状态模 型和外部成员模型，并给出了一个u n d o 模型的理想定位。然后利用嵌套u n d o 域对3 r 模型进行了详细描述，并且对由此引出的不一致性问题的产生做了 重点介绍。最后对u n d o 系统的目标系统进行了分类，并对每一类系统的特 点做出了简要介绍。 1 4 哈尔演丁程大学硕十学伊论文 第3 章基于3 r 模型的u n d o 系统设计 3 1 设计前提与假设 系统级u n d o 机制的主要目的是给服务系统的操作者( 管理者) 提供回 溯修复的能力，而且这种恢复主要是针对影响系统硬状态( 其中硬状态主要 是指在磁盘等稳定存储上的持久状态，包括用户数据、应用程序和系统配置 文件、系统二进制文件等) 的问题，包括诸如错误的配置更改，意外的数据 删除，存储重组失败导致的数据错误，病毒或外部黑客攻击导致的系统故障， 应用服务或系统的升级或修补失败，以及可在系统硬状态中反映出来的软件 b u g 等等。 因此，u n d o 系统的3 r 模型比较适合于解决影响系统硬状态的问题，而 并不适合恢复那些仅影响软状态的故障。这一类型的故障可以通过一种基于 重启的方式来对受到影响的系统进行恢复，微重启技术【2 5 】正是从这个方面来 处理这些软状态问题的。另外，3 r u n d o 恢复机制并不是面向终端用户的， 而是面向系统管理者的。因为由终端用户误操作导致的故障，一般仅会影响 此用户，而不会影响整个系统状态，因此对整个系统进行回卷与重放显然是 不合适的。若要解决这个问题，则可以通过在此基础上添加更为细粒度的 u n d o 机制来实现。 3 1 1自包含服务 自包含服务是u n d o 系统设计中的一个重要设计前提，对于自包含服务 定义如下：对于给定的一个服务，能确定其u n d o 域的边界范围，即请求流 入和数据流出的地方，并且要能够截获这些流入流出信息来定义与服务的交 互，并且这些交互要能够进行重放。首先，这里假设这种终端用户与服务交 互的协议是一种请求响应协议，而且流出u n d o 域的信息仅是作为到终端用 哈尔滨t 稃大学硕十学位论文 户的响应。此假设与大多数服务的用户交互模式相符，但对其中使用“推” 模式的服务情况则比较特殊：对于服务主动向终端用户推送数据的情况，是 不符合此假设的，而对于主动向服务推送输入的这种情况，可将其视为一系 列无响应的请求，故而可以认为是符合这种假设的。 另一点假设是服务的协议在整个u n d o 循环中是稳定的。如果协议发生 了改变或扩展，那么u n d o 系统就需要进行相应的改动来接受新的协议，否 则，u n d o 系统就可能无法成功重放终端用户的交互，因此也就可能丢失用户 的工作。比如一个服务在升级后加入了一个新的类型的交互，然而随后认为 这次升级是有缺陷的，并用u n d o 系统进行了回卷，此时u n d o 系统就不能重 放任何新类型的交互，除非这些新类型的交互可以用一系列原有交互类型来 重新表达。 最后一点假设是服务的硬状态( 存储) 是集中且独立的，不能与其他服 务的状态混合，也就是说必须要能够确定终端用户向服务发出请求所影响的 状态的边界范围。如果不能确定这个边界，那么就无法定义u n d o 域，也就 无法提供一致的回卷和重放。 3 1 2 黑盒方式 u n d o 系统将其所附着的系统视为一个黑盒：u n d o 系统包围于服务系统 外部，u n d o 系统不需要了解服务内部实现的具体细节，而且服务本身也不因 添加u n d o 功能而修改。采用黑盒方式最大的好处就是最大程度的利用现有 系统，无需修改即可在其上部署u n d o 系统。 采用黑盒方式而不是将u n d o 功能集成于服务系统自身还有另外一个好 处，就是允许对系统进行大范围无限制的修复，如升级、更换操作系统或应 用程序等操作，只要协议自身不改变，就允许对其进行重放。这种允许无限 制修复的能力对于系统级可靠性问题恢复来说是一个关键因素。 此外，采用黑盒方式还使u n d o 系统具有了可重用性。u n d o 系统对于某 种服务协议进行一次实现后，就可以针对此协议的不同实现加以重用。这对 1 6 哈尔滨t 程大学硕十学伊论文 于增强系统可靠性方面是一个重要的考虑，因为任何由u n d o 系统所引入的 复杂性都可能会增加如软件b u g 导致的可靠性问题。如果复杂的u n d o 机制 能够以通用方式建立一次，并且将其加入到每种新服务时都可以进行重用， 那么u n d o 机制中的b u g 就可以尽量消除，就会比每次建立一个新的u n d o 机制的系统要强壮、稳定的多。 然而，黑盒方式也有其缺点：一方面这种方式要求协议能够暴露足够的 信息来处理不一致问题，因此就需要对某些服务协议进行修改以使其具有 u n d o 特性，这将在第5 章中详细讨论。另一方面这种方式增加了u n d o 系统 的性能负担，因为所有用户交互的记录与重放都需要通过服务外的u n d o 系 统来完成。 3 1 3 故障模型 黑盒方式的上述特点实现了u n d o 系统与服务系统的分离，此外这种方 式还实现了u n d o 系统与其保护的服务系统间的故障隔离，使服务系统中的 故障不会影响到u n d o 系统中。因此对于服务系统的故障模型的限制是相当 宽松的：一个是不通过非协议方式产生外部输出，另一个是在系统修复后能 够接受己定义的协议命令。前一个限制是为了保证能够截取所有的外部输出 以便于不一致性检测，后一个限制是用来保证能够在修复后重放所有的用户 交互。这种宽松的故障模型在一定程度上限制了形式化分析u n d o 过程的能 力，但却是将系统从种种不同原因( 如错误操作、软件b u g 、有缺陷的补丁 或升级包) 导致的故障中恢复的关键所在。 与之相反，u n d o 系统对其自身的故障模型的限制是比较严格的。简单地 说就是要假设u n d o 系统是无b u g 的并且是一直运行良好的。这是一个重要 的假设，因为任何恢复机制要么是可靠的，要么就被更进一层的恢复机制所 保护，显然像3 r u n d o 这样的系统级恢复机制就很难再被另一层更为广泛的 恢复机制所包围。当然也可以在实现u n d o 系统时加上某种保护技术，使其 在发生故障时的行为仍然是可控制的。 哈尔滨t 程，：学硕十学伊论文 3 2u n d o 系统的结构与工作流程 3 2 1u n d o 系统的基本结构 系统级u n d o 技术的恢复过程主要通过3 r 循环来描述，包括回卷 f r e w i n d ) ，即在故障发生后，系统管理员先将可明确定界的服务系统状态回 滚到先前某个正确的状态；修复( r e p a i r ) ，即在回卷阶段结束后，系统管理员 可以就已发现问题对系统采取任何必要的修复措施；重放( r e p l a y ) ，即在系统 修复之后，要将先前己回卷时间段内的所有用户与系统的交互操作重新执行， 从而使因同系统状态一并回卷而丢失的用户状态和数据得到恢复，从而完成 整个恢复过程。 为实现上述恢复过程，这里设计并实现了一个通用的系统级u n d o 模块， 基本结构如图3 1 所示。此模块主要包括5 个基本功能单元：u n d o 控制器， 负责整个u n d o 恢复过程的控制，以及u n d o 系统中其他功能模块的管理；检 查点管理器，负责目标系统检查点的设置以及回卷阶段的系统硬状态备份恢 复；排序器，负责将用户交互进行恰当排序；日志管理器，负责将用户交互 生成交互日志，并在重放阶段提取对应日志；一致性管理器，负责对重放过 程中产生不一致的交互谓词进行检测和补偿。 哈尔滨t 千n ，：学硕十学何论文 图3 1u n d o 系统的基本结构图 3 2 2u n d o 系统的工作流程 u n d o 系统的工作流程主要涵盖两个阶段：系统正常运行阶段和系统故障 恢复阶段。其中系统正常运行阶段是指目标系统并未发生故障，u n d o 系统与 目标系统正常并行运行的阶段；系统故障恢复阶段是指目标系统发生故障( 如 人为误操作引起的故障) ，由u n d o 系统对目标系统进行恢复的阶段。 在系统正常运行阶段，终端用户与系统的正常交互在到达服务之前，先 哈尔滨t 程了：学硕十学伊论文 由u n d o 系统外围的u n d o 代理截获并将截获到的用户交互生成交互谓词交付 给u n d o 系统。u n d o 系统首先将交互谓词交由排序器进行处理，排序器将接 收到的交互谓词逐个执行相应测试进行排序，这包括三种测试，分别是：可 交换性测试，独立性测试和首选排序测试。其中可交换性测试是用来检测两 个交互谓词以不同的顺序执行是否能产生相同的外部可见结果，独立性测试 是用来进一步检测两个交互谓词是否能安全地并行执行( 在可交换性测试通 过后) ，首选排序测试是用来在两个交互谓词独立性测试失败时返回一个较佳 的首选执行顺序。经过排序后的交互谓词由排序器交付给同志管理器。日志 管理器在收到排序后的交互谓词后，将其按序记录到交互日志数据库中，记 录后的交互谓词再交由u n d o 代理发送到服务执行。此部分工作流程如图3 2 所示。 哈尔滨t 程大学硕十学位论文 图3 2u n d o 系统日志记录流程图 在上述过程进行的同时，u n d o 系统中的检查点管理器按照检查点生成策 2 l 哈尔滨t 程大。t - 硕十学位论文 ii i i 略对当前服务系统创建系统状态检查点并存储于检查点存储器上，若检查点 存储器空间已满，则淘汰当前检查点记录中最老的检查点，同时通知日志管 理器丢弃交互日志中对应部分的记录，此部分工作流程如图3 3 所示。 图3 3u n d o 系统检查点生成流程图 哈尔滨t 稗：学硕十学伊论文 在系统故障恢复阶段，在系统发生故障之后，管理员由u n d o 控制器的 回卷接口向系统发出回卷指令，并通过回卷接口向检查点管理器请求所需恢 复的检查点。检查点管理器在收到回卷请求后，在检查点存储器上查找对应 的检查点，并将当前故障系统的状态恢复为此检查点所在的正常状态，这个 状态既包括系统级状态如操作系统、应用服务以及配置文件等，又包括应用 级状态如系统终端用户的数据等。此后系统管理员对系统进行必要的修复， 且这种修复并无过多限制，以保证在调整系统时的灵活性：除了可以直接对 先前的错误操作进行更正，如修正错误的配置，重试不成功的升级操作等， 此外还可以通过u n d o 控制器的修复接口对交互日志进行查询与编辑操作， 进行必要的修改和调整来完成修复工作。完成系统修复之后，系统管理员通 过重放接口向日志管理器发出重放指令，日志管理器按照重放请求从日志数 据库中查找对应的交互日志，并向一致性管理器发送日志中交互谓词的历史 记录序列，由一致性管理器对产生不一致的交互谓词进行处理，此处理由三 个过程组成，分别是：判定过程，用于比较一个交互谓词的原始外部输出记 录同重放产生的输出是否一致；补偿过程，用于在检测到不一致性后调用相 应的补偿动作来对不一致进行补偿；压制过程，用于改变与产生不一致的交 互谓词有依赖关系的交互谓词的执行。一致性管理器首先调用判定过程来比 较交互谓词在重放过程的执行结果和原始执行结果，如果比较结果是一致的， 则输出这个结果；如果是不一致的，则判断产生了不一致，立即调用补偿过 程进行补偿。补偿过程将对检测到的不一致按照定义的补偿策略进行补偿， 这种补偿策略