第七篇分布式系统中容错技术.ppt

第七章 分布式系统中容错技术 7.4 分布式检查点算法 同步检查点 Chandy-Lamport(CL)算法： 建立检查点的过程可由任一个进程pc发起，pc进程停止运行，并向与其所在机器直接相连的机器上的进程广播报文Mb，然后进程pc建立局部检查点； 进程p接收到报文Mb后，若进程p还未开始建立检查点，则进程p停止运行并立即向与其所在机器直接相连的机器上的进程广播报文Mb，然后进程p建立局部检查点； 进程p开始建立检查点后，若接收到其他进程发送的非检查点控制报文m，则保存报文m； 第七章 分布式系统中容错技术 7.4 分布式检查点算法 同步检查点 Chandy-Lamport(CL)算法： 当进程p完成局部检查点的建立，并且接收到与其所在机器直接相连的机器上的所有进程发送的报文Mb后，进程p向pc进程发送报文Ms； 当进程pc接收到所有进程发送的报文Ms后，pc进程向所有进程发送报文Me，并删除本进程旧的检查点，进程pc继续执行； 其他进程p接收到报文Me后，删除本进程旧的检查点，继续执行。 在恢复过程中，CL算法在回卷到当前检查点重新执行的同时还必须重发过程(3)中保存的报文m。与SNS算法相比，CL算法减少了两次全局同步的开销。CL算法的缺点是其控制报文的数目与机器间的拓扑结构有关。 第七章 分布式系统中容错技术 7.4 分布式检查点算法 混合检查点 其基本思想是在一个较长的时间段中使用同步检查点，而在较短的时间段内使用异步检查点。也就是说，在一个同步时间段里，会有若干个异步时间段。因此，我们可以有一个可以控制的回卷，从而保证不会在建立检查点的过程中引入过多的开销。 例如：准同步检查点。这个方法允许每个进程异步地设置检查点，从而保证了进程的独立性。同时，对恢复线的扩展采用发起通信的检查点协调方法，从而可以限制恢复过程中回卷的传播。 第七章 分布式系统中容错技术 7.4 分布式检查点算法 报文日志 报文日志：为了减少回卷时撤销的计算工作量，所有接收的和发送的报文都可以记录下来。前者叫做接收者日志，后者叫做发送者日志。 当Pj的检查点被恢复到一个没有孤儿报文，而且所有要发送的报文都已经发送的一致状态的时候，可以用Pj的接收者日志减少回卷工作量，即只需要将Pj所收到的报文重新向Pj发送一遍即可。 第七章 分布式系统中容错技术 7.4 分布式检查点算法 报文日志 如果进程Pj记录了报文m的接收者日志，那么Pi和Pj的当前检查点集合就可以看作是一致的。一旦由于Pj由于失效回卷到当前检查点重新执行的时候，报文m就可以通过Pj的接收者日志重新发送给进程Pj，不会引起进程Pi的任何回卷。 第七章 分布式系统中容错技术 7.4 分布式检查点算法 报文日志 如果Pi在发送完报文m后失效，那么当进程Pi恢复到当前检查点后，它会根据发送者日志的纪录知道曾经发送过报文m，这样就没有必要再发送一次了。如果接收者Pj失效，而且没有接收者日志，它仍然可以根据从发送者日志中得到的报文正确恢复。 第七章 分布式系统中容错技术 7.4 分布式检查点算法 报文日志 Alvisi和Marzullo的报文日志方案 报文格式：每个报文m包含有一个报文头用于存放重发这个报文和正确处理这个报文所必需的一些信息，例如，该报文的发送者和接收者，用于识别报文重复的序列号，另外还有一个传输号用于决定何时该报文需要传递给接收进程。 坚固的报文：如果一个报文不再会丢失，则称这个报文是坚固的，例如当一个报文已经被写入到坚固存储器中，就可以说这个报文是坚固的。坚固的报文可以重新发送给失效后重新恢复的进程。 第七章 分布式系统中容错技术 7.4 分布式检查点算法 报文日志 Alvisi和Marzullo的报文日志方案 进程集合DEP(m) 的组成：一个报文m对应于一个进程集合DEP(m) ，该集合包含了与报文m传输有关的所有进程。 DEP(m)包含了所有接收该报文m的进程； 如果另外一个报文m’和报文m有因果依赖性关系，并且m’是传递给进程Q的，那么DEP(m)集合中应该包含进程Q。 因果依赖性关系：如果m’和m是由同一个进程发送的，并且m的发送先于m’的发送，则说m’和报文m的传输有因果依赖性关系。同样地，如果m”和m’有因果依赖性关系，m’和m有因果依赖性关系，则说m”和m有因果依赖性关系。 第七章 分布式系统中容错技术 7.4 分布式检查点算法 报文日志 Alvisi和Marzullo的报文日志方案 进程集合COPY(m) 的组成：如果一个进程有报文m的一个拷贝，但是这个拷贝还没有写入到它的局部坚固存储器中的话，该进程就属于集合COPY(m)。当一个进程发送了报文m，它也属于集合COPY(m)。值得注意的