（计算机软件与理论专业论文）基于索引的准同步检查点协议研究.pdf

硕士学位论文 摘要 分布式系统在互联网高速发展的今天，已经被广泛应用于客户一服务器系统、 事务处理、万维网以及科学计算等多个领域。由于分布式程序的广泛应用，分布 式系统的容错问题就变得越来越重要，许多技术被用来提高系统的稳定性和可靠 性，其中包括回卷恢复技术。 回卷恢复技术的容错是通过在无错执行期间周期性地保存进程的状态来实现 的。一旦发生错误，出错的进程就从保存的状态处重新开始执行，从而减少出错 带来的计算上的损失。每一个这种保存的状态称为一个检查点。在分布式系统中 设置检查点时，除了要考虑在单进程应用程序中所存在的减少检查点开销，优化 检查点时间间隔等问题外，还要考虑分布式系统中由于进程之间相互发送消息而 导致的进程状态间的相互依赖关系。这是分布式系统中的检查点技术主要复杂的 地方。怎样保证形成全局一致性检查点，避免多米诺效应，同时尽量减少由于引 入检查点而带来的额外开销，是分布式系统中的检查点设置技术所要考虑的主要 问题。 分布式检查点技术目前主要分为三种类型，即异步检查点方式，同步检查点 方式以及准同步检查点方式。本文着重介绍了对基于索引的准同步检查点协议的 研究。本文首先介绍了分布式检查点协议中的一些重要的定义和定理以及当前国 内外一些主要的基于索引的准同步检查点协议，然后在这些协议的基础上提出两 种自己的改进方案，从而提出一种新的改进的协议，称之为i b q s c 协议。通过模 拟实验证明，i b q s c 协议在性能上的确能够取得明显的提高。之后，将介绍目前 国际上针对基于索引的准同步检查点协议的性能比较的研究，介绍一些重要的结 论，并对这些结论中的问题提出自己的见解。 关键词：软件容错；分布式计算；检查点；多米诺效应；全局一致性检查点 基于索引的准同步检查点协议研究 d i s t r i b u t e ds y s t e m st o d a ya r ew i d e l ya p p l i c a b l e ，i n c l u d i n gc l i e n t - s e r v e rs y s t e m s ， t r a n s a c t i o np r o c e s s i n g ，w o r l dw i d ew e b ，a n ds c i e n t i f i cc o m p u t i n g ，a m o n gm a n y o t h e r s f a u l tt o l e r a n c eo ft h e s es y s t e m si sm a i n l yf o c u s e da n dm a n yt e c h n i q u e sh a v e b e e nd e v e l o p e dt oi m p r o v er e l i a b i l i t ya n dh i g ha v a i l a b i l i t yo fd i s t r i b u t e ds y s t e m s r o l l b a c kr e c o v e r yi so n eo ft h e m f a u l tt o l e r a n c eo fr o l l b a c kr e c o v e r yi sa c h i e v e db yp e r i o d i c a l l yu s i n gs t a b l e s t o r a g et o s a v et h ep r o c e s s e s s t a t e sd u r i n gf a i l u r e f r e ee x e c u t i o n u p o naf a i l u r e ，a f a i l e dp r o c e s sr e s t a r t sf r o mo n eo fi t ss a v e ds t a t e s ，t h e r e b yr e d u c i n gt h ea m o u n to f l o s tc o m p u t a t i o n e a c ho ft h es a v e ds t a t e si sc a l l e dac h e c k p o i n t t h eo p t i m i z i n g s c h e m e ss u c ha sr e d u c i n gt h ec o s to fc h e c k p o i n t i n g ，f i n d i n ga no p t i m a li n t e r v a lo f c h e c k p o i n t sa n ds oo n ，w h i c ha r ep r e s e n t e di nu n i p r o c e s s o r sc h e c k p o i n t i n gc a nb e a d o p t e di nt h ed i s t r i b u t e dc h e c k p o i n t i n g f u r t h e r m o r e ，d i s t r i b u t e ds y s t e m sc o m p l i c a t e r o l l b a c k r e c o v e r y b e c a u s em e s s a g e si n d u c e i n t e r p r o c e s sd e p e n d e n c i e sd u r i n g f a i l u r e f r e eo p e r a t i o n i ti sd e s i r a b l et or e d u c et h eo v e r h e a do fc h e c k p o i n t i n ga n d ，a t t h es a m et i m e ，k e e pt h ed o m i n o - e f f e c tf r e e d o ma n de n s u r et h ec o n s i s t e n tg l o b a l c h e c k p o i n t s d i s t r i b u t e dc h e c k p o i n t i n gc a nb eb r o a d l yc l a s s i f i e di n t ot h r e ec a t e g o r i e s ，t h a ti s ， a s y n c h r o n o u s ，s y n c h r o n o u s ，a n dq u a s i s y n c h r o n o u s i n t h i s p a p e r ，t h es t u d yo f i n d e x b a s e d q u a s i s y n c h r o n o u sc h e c k p o i n t i n g i si n t r o d u c e d s o m e i m p o r t a n t d e f i n i t i o n sa n dt h e o r e m sa r er e v i e w e da n dt h ep r e v a i l i n gi n d e x b a s e dc h e c k p o i n t i n g p r o t o c o l sa r ep r e s e n t e da tf i r s t t h e nt w oi m p r o v e ds c h e m e sb a s e do nt h ep r e v i o u s p r o t o c o l sa r ep r o p o s e da n dt h u sf o r ma n e wp r o t o c 0 1 t h es i m u l a t i o nr e s u l t sa r eg i v e n t os h o wt h a tt h en e wp r o t o c o lc a na c h i e v ep e r f o r m a n c ei m p r o v e m e n t s ，c o m p a r e dt o t h et r a d i t i o n a lo n e s a f t e rt h a t ，t h ec o m p a r i s o na p p r o a c ha b o u tt h ei n d e x b a s e d c h e c k p o i n t i n gp r o t o c o l si sp r e s e n t e dw i t hs o m ei m p o r t a n tc o n c l u s i o n s ，w h e r e a s a d i f f e r e n to p i n i o no fu si si n t r o d u c e da tt h es a m et i m e k e yw o r d s ：s o f t w a r ef a u l tt o l e r a n c e ；d i s t r i b u t e dc o m p u t a t i o n ；c h e c k p o i n t ；d o m i n o e f f e c t ；c o n s i s t e n tg l o b a lc h e c k p o i n t i i 硕士学位论文 插图索引 2 1 全局一致性系统状态6 2 2 不一致系统状态6 2 3z 一路径和z 一环7 2 4m r s 模型一1 0 3 1 不同情况下l a z y b c s 的索引值的设置1 6 3 2a f t e r s e n d 策略1 7 3 3b q f 协议1 9 3 4h m n r 协议2 0 4 1s k i p 策略2 3 4 2 重新计时策略2 4 4 3 实验1 的实验结果一2 6 4 4 实验2 的实验结果1 2 7 4 5 实验2 的实验结果2 2 8 4 6 实验2 的实验结果3 2 9 5 1 不对称情况l 3 2 5 2 不对称情况2 3 2 5 3 由于不对称导致回卷中的“不公平”情况3 2 5 4 减少不对称情况下的开销一3 3 5 5 回卷中“不公平”情况的避免3 3 5 6 模拟实验l 性能比较结果3 6 5 7 模拟实验1 主动同步策略的额外开销3 7 5 8 主动同步方案在网络延迟较大的情况下无效3 8 5 9 模拟实验2 实验结果3 9 5 1 0t 簇略的有效区域3 9 6 1h m n r l 协议性能优于l a z y h m n r l 协议的情况4 1 6 2h m n r 2 协议采用l a z y i n d e x i n g 策略4 2 6 3l a z y h m n r l 与h m n r 2 在不对称情况下的性能比较4 3 图图图图图图图图图图图图图图图图图图图图图图图图图图图 基于索引的准同步检查点协议研究 表4 1 表4 2 表4 3 表4 4 表5 1 附表索弓 实验2 的实验结果1 实验2 的实验结果2 实验2 的实验结果3 进程检查点在程序无错执行时的影响 模拟实验1 性能比较结果 押勰凹如 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 日期：泐多年夕月乙日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密曰。 ( 请在以上相应方框内打“4 ”) 作者签名：黔蕴，日期川$ 年f 月沈日 导师签名：。闳应孑簪 日期：埘年厂月况日 硕士学位论文 1 1 研究背景 第1 章绪论 随着互联网技术的高速发展，人们运用计算机进行工作和交流突破了地域的 限制，不再局限于单个计算机的工作环境，而是向着互相协调、大规模的相互合 作的模式扩展。分布式系统在传统的单机系统的基础上，提供了各种有用的功能， 满足了不同用户相互协同、相互合作完成各种复杂任务的要求。分布式系统，是 一组同构或者异构的计算机或者处理器，这些计算机或处理器通过网络连接起来， 整组机器紧密配合工作，完成一个共同的目标。分布式系统是单机系统的扩展， 把异构的单机系统通过网络连接起来，形成统一的全局视图，作为一个整体看待， 统一分配和利用资源，具有单机系统难以达到的计算能力。分布式系统已经被广 泛应用于客户一服务器系统、事务处理、万维网以及科学计算等多个领域。但是 由于分布式系统与单机系统相比，对于各种人为的或者非人为的故障的抵抗力较 差，从而导致分布式计算潜在的计算能力受到了限制，难以发挥。最典型的如分 布式科学计算程序，为了提高计算速度，充分利用各种资源，往往把一个大程序 分割成许多互相关联的小程序在一个分布式系统中的多台机器上运行。对于较大 型的科学计算程序，往往要运行数十小时，几天，几个星期甚至更长。如果没有 采取适当的容错措施，一旦参与计算的某台计算机发生错误，就可能会导致整个 系统的工作出现问题，必须重新开始执行，从而丢失之前所有的有效计算。这样 带来的损失是巨大的，有时甚至导致无法顺利完成任务。又如文献 1 中提到的， 每年病毒和骇客对全球金融领域造成的损失高达几十亿美元。因此提高分布式系 统的可信性和可用性，是一个需要特别重视的问题，目前已有各种技术用来实现 这一目的，其中就有回卷恢复技术。 1 2 容错回卷技术介绍 容错系统一般采用冗余来满足系统高可靠性的要求，冗余可以划分为时间冗 余和空间冗余两类。时间冗余是指出现故障时通过将程序卷回到一个无错的执行 点，采用同种方法或不同方法再试的手段得到正确结果：空间冗余通常指由多个 相同组件并行执行，通过将各自执行结果比较或者表决的方法来检测错误或者得 到正确结果。空间冗余代价大，成本高，主要应用于特殊领域。时间冗余不仅开 基于索引的准同步检查点协议研究 销小，而且行之有效，文献 2 提出8 0 到9 0 的软件错误都可通过时间冗余的方 法来解决。时间冗余方法中最常用的是回卷恢复技术。 回卷恢复技术把分布式系统看作一个应用程序进程的集合，这些进程通过网 络通信。回卷恢复技术的容错是通过在无错执行期间周期性地保存进程的状态来 实现的。旦发生错误，出错的进程就从保存的状态处重新开始执行，从而减少 出错带来的计算上的损失。每一个这种保存的状态称为一个检查点( c h e c k p o i n t ) 。 通过设置检查点能够保存和恢复程序的运行状态，因此它在许多领域都有重 要的应用1 3 5 】： 1 ) 进程迁移。目前大多数操作系统不能提供进程迁移功能，利用检查点可以 保存进程在某台机器的运行状态，然后在其他机器上恢复进程的运行以实现进程 迁移。进程迁移可以使得税群负载平衡，从而提高计算速度和机菥两羽膈 2 ) 容错。分布式系统的故障率随系统机器数的增加而增加，长时间运行的作 业若在每次出现机器故障时都从头开始执行，该作业将很难被执行完毕。因此， 利用检查点实现多机系统容错成为人们日益关心的热点。 3 ) 卷回调试。在程序调试过程中，利用检查点保存程序在多个时刻的运行状 态。当错误发生时，把程序卷回到保存的某一时刻的状态重新向下运行，以再次 产生相同的错误来查找错误发生条件的调试方法称为卷回调试。分布式程序包含 较多的不确定成份，当发现运行错误重新运行程序查找错误原因时，同样的错误 很可能难以再次出现。利用卷回调试在很大程度上提高错误再次发生的概率。 1 3 国内外研究现状 根据检查点算法的使用范围可以把目前的回卷恢复协议分为两类：单进程程 序检查点算法以及分布式程序检查点算法。单进程程序检查点算法是容错回卷技 术的基础，目前国内外的研究已经比较成熟，并且已有一些产品问世【5 】【“，而随 着分布式系统的推广，分布式系统中的检查点协议也逐渐成为了研究的热点【“3 1 】。 目前国际上对容错回卷技术的研究主要集中在u n i x 系统【3 2 l 和w i n d o w s 操作系统 【3 3 】上。其中对于u n i x 系统，这方面的研究已经比较成熟了，但是对于w i n d o w s 操作系统，相对来说还比较缺乏。由于w i n d o w s 操作系统的广泛使用，尤其是基 于w i n d o w sn t 的操作系统在个人用户p c 机和大型工作站机群上的广泛应用，对 于怎样在基于w i n d o w sn t 的操作系统上实现透明的容错回卷也变得重要起来。在 国内对这方面的研究也逐渐增多。在 3 4 中，实现了在w i n d o w sn t 系统上对单进 程的透明的检查点技术。在 3 5 中，实现了一个在w i n d o w sn t 系统上对分布式应 用程序进行透明地多线程检查点的工具集( w i n d a r ) 。这个软件是基于m p i c h n t 的，对于n t 系统中的任何基于m p i ( 消息传递接口) 的应用程序，该软件都能实 现基于消息同志方式的透明的检查点。 硕士学位论文 1 4 本文的主要工作 检查点技术在移动计算，容错，卷回调试等方面都有广泛应用。而随着分布 式计算地迅速发展，分布式系统的容错问题也变得越来越重要。检查点技术通过 在分布式程序运行过程中按照事前的设定，在程序运行的某些时刻把程序的即时 状态保存下来，使程序出错后可以回卷到所保存的状态处，以免丢失之前所有有 效的计算，从而减少出错带来的计算上的损失。在分布式系统计算中怎样避免多 米诺效应，形成全局一致性检查点，同时尽量减少由于引入检查点而带来的额外 开销，是分布式系统中的检查点设置技术所要考虑的主要问题。通信诱导检查点 协议【8 。1 8 ，2 3 , 2 5 1 属于分布式检查点协议中的一种，又可分为基于模型的协议 1 7 , 1 8 , 2 3 , 2 5 1 和基于索引的协议【1 0 。1 t 4 】两种类型一基子模型的协议通赶避免某种特定的模型的出 现来避免多米诺效应，同时尽量减少强制检查点的数目；而基于索引的协议则是 通过l a m p o r t 逻辑时钟来达到进程间的松散的同步，以避免多米诺效应。有研究 表明1 8 , 1 s ，基于索引的协议与基于模型的协议相比往往能取得更好的性能。通过 改进已有的基于索引的协议，我们可以进一步减少检查点带来的开销，并且对各 种协议进行比较，研究各种协议的性能和特性，从而为这些协议的具体应用提供 一些依据。 本文的主要工作分为两部分： 1 对基于索引的准同步检查点协议的研究 主动同步策略： 在不对称的情况下，基于索引的准同步检查点协议的开销显著增加，为了减 少开销，本文介绍了一种主动同步策略，并通过模拟试验证明，这种策略能够有 效减少不对称情况下基于索引的准同步检查点协议的开销。 重新计时策略： 为了实现同步，保证全局一致性检查点的存在，基于索引的准同步检查点协 议引入了强制检查点。强制检查点是每个进程除了周期性的做基本检查点之外所 做的额外的检查点。由于强制检查点的引入导致了分布式计算的额外开销增加。 本文引入一种重新计时策略，本质上是把强制检查点与基本检查点同等对待，从 而减少基于索引的准同步检查点协议的开销。 形成新的检查点协议： 在已有的检查点协议的基础上，结合上面的两种改进策略，本文提出一种新 的基于索引的准同步检查点协议。通过模拟试验证明，该协议与传统协议相比， 可以显著减少系统因引入分布式检查点算法而导致的额外开销。 2 对于基于索引的准同步检查点协议的比较方法的研究 对于不同的基于索引的检查点协议的性能进行比较，在不同的情况下可能有 基于索引的准同步检查点协议研究 不同的结果，文献【8 】【“】从理论上给出了一套完整的比较方法。本文仅通过一个例 子，来证明这套方法中的一个小错误。 1 5 论文结构 本文第一章介绍了分布式系统中的检查点技术的概念，研究背景以及国内外 目前的研究现状；第二章介绍了分布式系统中的检查点协议的系统模型，重要术 语，相关定义和定理以及性能评价标准及分类；第三章介绍目前主要的基于索引 的准同步检查点协议；第四章介绍了一种重新计时策略；第五章在第四章的基础 上进一步提出一种新的基于索引的准同步检查点协议；第六章介绍对基于索引的 准同步检查点协议的比较方法，并指出其中的错误。最后是全文的总结。 基于索引的准同步检查点协议研究 不同的结果，文献【8 l 【1 6 】从理论上给出了一套完整的比较方法。本文仅通过一个例 子，来证明这套方法中的一个小错误。 1 5 论文结构 本史第一章介绍了分布式系统中的检查点技术的概念，研究背景以及国内外 目前的研究现状；第二章介绍了分布式系统中的检查点协议的系统模型，重要术 语，相关定义和定理以及性能评价标准及分类；第三章介绍目前主要的基于索引 的准同步检查点协议；第四章介绍了一种重新计时策略；第五章在第四章的基础 上进一步提出一种新的基于索引的准同步检查点协议；第六章介绍对基于索引的 准同步检查点协议的比较方法。并指出其中的错误。最后是全文的总结。 准同步检查点协议的比较方法，并指出其中的错误。最后是全文的总结。 硕士学位论文 第2 章分布式系统中的检查点协议 2 1 系统模型 一个分布式计算由n 个进程的集合组成( p o ，p 1 ，p n - 1 ，进程间只通过交 换消息来通信和同步。c i ，i 表示进程i 的第j 个检查点。假设任何一对进程之间都 通过可信的、直接的逻辑渠道相连，并存在不可预计的但是有限的延迟。进程服 从出错停止的模式。进程执行过程包含三种状态，分别是内部状态，发送状态以 及接收状态，分别对应有三种事件，即内部事件，发送事件以及接收事件。进程 在没有进行通信时执行于内部状态，检查点事件属于内部事件。消息发送和接收 事件分别发生在发送状态和接收状态，分别用s e n d ( m ) 和r e c e i v e ( m ) 来表示。同一 个进程中两个相继的基本检查点之间的时间间隔称为基本检查点间隔，用i 表示。 2 2 相关定义和定理 在分布式检查点协议中，一个进程的检查点保存的是该进程的一个局部状态， 所有参与分布式计算的进程的单个局部状态以及通信渠道状态的集合构成了系统 的一个全局状态。而分布式系统中的检查点算法需要做的，是保证全局一致性检 查点，即全局一致性状态的存在。对于系统的某个全局状态，如果组成该全局状 态的任何一个进程的局部状态反映了已经接收到了一条消息，那么相应的，发送 消息的进程的局部状态也反映了已经发送了该消息，就称此全局状态为全局一致 性系统状态【8 , 9 , 1 9 , 2 1 , 3 0 , 3 1 】，而相应的组成此全局状态的，保存各进程局部状态的检 查点的集合称为全局一致性检查点。如图2 1 所示。 在图2 1 中，p o ，p 1 和p 2 表示分布式计算中的三个进程，从左到右的箭头表 示进程的执行过程，m t 和m 2 两个箭头表示进程间发送的消息，矩形a 、b 、c 表示 进程的局部检查点，用虚线把这三个局部检查点连接起来表示这三者构成的全局 检查点。时间从左至右增加( 如无特殊说明，在本文余下的章节中都采用以上定 义) 。图2 1 中a 所保存的系统状态反映了消息m l 已经发送，b 没有反映m ，已经 接收，表示m ，仍在传送过程中，存在于通信子网上，我们称之为中途消息【8 】。a 、 b 、c 三个检查点可以构成全局一致性系统状态。相反，图2 2 中表示的则是不一 致的系统状态。 基于索引的准同步检查点协议研究 图2 1 全局一致性系统状态 不一致系统 图2 2 不一致系统状态 在图2 2 中，检查点c 反映了已经接受了消息m 2 ，但是b 则没有反映已经发 送了m 2 ，这样两者状态之间就存在矛盾。这种不一致状态会导致系统出现无法预 料的错误。这些局部检查点不能形成全局一致性检查点，因此不能用来达到容错 的目的，当分布式计算出错后，系统必须不断回卷，直到找到全局一致性检查点 从而形成全局一致性状态。但是在某些最坏的情况下，系统一直找不到全局一致 性检查点，所有进程就可能一直回卷到系统最初执行的时刻，丢失之前所有的有 效计算，这样检查点技术就失去了容错的意义。这种情况称为分布式检查点协议 中的多米诺效应。多米诺效应，就是在分布式计算出错后，在寻找全局一致性检 查点的过程中，出现的一种无限制的，层叠的回卷现象 8 】【。多米诺效应会导致 系统丢失大量有效计算，使分布式检查点技术失去容错的效果，是应该避免的。 为了避免多米诺效应，保证全局一致性检查点的存在，国内外对此进行了深入的 研究，提出了一套完整的理论。下面介绍一些重要的定义和定理。 如果p i 发送了消息m ，并且s e n d ( m ) 在做检查点c i 。之前发生，则表示为 s e n d ( m ) c i 同理，如果p 接收了消息 l ，并且r e c e i v e ( m ) 在做检查点c j ，。之前 发生，则表示为r e c e i v e ( m ) c m 。 定义1 一个全局检查点g c ，g c 一 c o j n 0 ，c 1j n l ，cn _ 1 。n _ 1 ) ，称为一个全局 一致性检查点 8 , 9 , 1 9 , 2 1 , 3 0 , 3 1 】，当且仅当对任意消息m ，有r e c e i v e ( m ) c i , m i - - s e n d ( m ) 硕士学位论文 c j ，m j ，c i ，m i g c ，c j ，m i g c ，0 三i 薹n - 1 ，0 兰j 堇n 一1 。 定义2l a m p o r t 超前发生关系【3 6 , 3 7 】：如果事件a 在事件b 之前发生，称为a 超前发生于b ，表示为a b ，有以下结论： 1 如果两个事件a 和b 在同一个进程中发生，它们之间的次序是它们被观察 到的次序，即如果a 在b 之前到来，有a b 。 2 如果a 是发送事件s e n d ( m ) 而b 是接收事件r e c e i v e ( m ) ，那么a b 。也就 是说，不能在消息发送之前接收到它。 3 超前发生关系具有传递性。如果有a b 且b c ，那么有a c 。 任何不具备超前发生关系的一对事件都是并发的，并发的事件没有先后关系。 推论1 对于一个全局检查点g c = c o ，。0 ，c 1 ，。1 ，c n 1 ，。n 1 ) ，如果是全局一 致性检查点，当且仅当对任意两个检查点c i ，g c ，c j ，y g c ，c i ，；一c j ，y 不成立。 定义3 z - - 路径【1 9 ，2 1 ，3 0 ，3 1 】给定两个进程检查点c i ，和c j ，y ，在c i , x 和c j ，y 之 间存在一条z 一路径，当且仅当下列条件之一成立： 1 x y 且i = j ；或者 2 存在一个消息序列【n l o ，m l ，i l l 。】，n 量0 ，并且满足： c i 。一5 e n 西向一； v l s nt h e n s n = = m s n ；t a k eaf o r c e dc h e c k p o i n t d e l i v e rt h em e s s a g e 3 2m s 协议 在文献【1 2 】中，介绍了m s 协议。m s 检查点协议的基本思想与b c s 协议本质 上是一致的。只不过文献【1 2 1 是第一个完整的阐述基于索引的准同步检查点算法的 协议。除了介绍了与b c s 协议相似的思想外，还介绍了相应的回卷算法，垃圾收 集算法，以及对中途消息的处理。由于该协议提出的算法比较完善，所以在以后 的文献中提出的新的基于索引的检查点协议，大多仅关注于对做基本检查点与强 制检查点的算法进行改进，而没有再介绍回卷算法及垃圾收集等问题。在本文接 下来介绍的各种协议中，也不再讨论回卷算法与垃圾收集算法的问题，仅在本节 中简要介绍这些算法的思想。以下是m s 协议的伪代码： 基本检查点及强制检查点算法 t a k eb a s i cc h e c k p o i n t sp e r i o d i c a l l yw i t hs ni n c r e m e n t ； w h e nr e c e i v ea m e s s a g em ： i fm s n s nt h e n s n = = m s n ；t a k eaf o r c e dc h e c k p o i n t d e l i v e rt h em e s s a g e 回卷恢复算法 r e c o v e r yi n i t i a t e db yp r o c e s sp ia f t e rf a i l u r e r e s t o r et h el a t e s tc h e c k p o i n t ； s e n dr o l l b a c km e s s a g er b mw i t hs n ip i g g y b a c k e do ni t ； 基于索引的准同步检查点协议研究 w h e nr e c e i v ear o l l b a c km e s s a g e i fr b _ m s n i s nt h e n s n = = r b _ m s n i ；t a k ea c h e c k p o i n t e l s ef i n dt h ee a r l i e s tc h e c k p o i n tcw i t hc s n 至r b _ m s n i ； s n = = c s n r e s t o r ec h e c k p o i n tc ； d e l e t ea l lt h ec h e c k p o i n t sb e y o n dc ； 由以上伪代码可知： 1 出错的进程只要回卷到该进程最近一次的检查点即可。 2 当出错的进程回卷之后，还要向其它进程发送回卷消息通知它们回卷；在 发送回卷消息的