分布计算系统笔记——第六章 容错技术

错误分为暂时性、间歇性、永久性

容错建立在冗余上 ​

坚固存储器 ​

磁盘镜像：一对磁盘

RAID（廉价磁盘冗余阵列）：位交错技术将数据分布到多个磁盘中

故障-停止处理器 ​

当一个处理器失效，最可能的是它不进行任何不正确的操作，并且简单地停止运行，这样的处理器被称为故障—停止处理器，一个故障—停止处理器由多个处理器组成。

原子操作 ​

要么一套操作全做完，要么一个都不要做

向前式恢复和向后式恢复 ​

向前式恢复假定可以完全准确地得到系统中的故障和损失的性质，这样就有可能去掉这些故障从而使得系统继续向前执行

向后式恢复定时地存储系统的状态，这样当失效导致系统处于不一致的状态时，系统可以恢复到从前没有发生故障的状态，在此状态下重新执行。

向后式恢复 ​

恢复到检查点，检查点是进程保存的正确的状态

检查点的保存： ​

1. 每一个检查点被组播到每一个备份模块；
2. 每个检查点被存储在它的本地坚固存储器中。

当进程正确地从一个旧的检查点运行到一个新的检查点时，旧的检查点就要被新的检查点替换（原子更新）。当进程执行到两个检查点之间时发生错误，那么进程应该卷回到旧的检查点处重新执行。

基于影像页面技术的恢复方案： ​

在基于影像页面技术的方案中，当进程需要修改一个页面时，系统复制该页并保留在坚固存储器中。系统中每个页面都有两个拷贝，当进程在执行的过程中，只有其中的一个拷贝被进程修改，另一个拷贝就作为影像页面。如果进程失效，则丢弃被修改的拷贝，系统根据影像页面进行恢复。如果进程成功运行，则每一份影像页面被相应的修改后的页面替换。

向前式恢复 ​

两个进程X和Y均运行一个进程的同一个版本。在每一个检查点之前，需要对它们的结果进行比较并确认是否正确。S是一个后备处理器，对两个间隔 $l_i$ 和 $l_{i+1}$ 进行验证。有以下四种可能的情况

1. 没有并发重试。如果X和Y都正确运行，那么所得的结果是相同的，S不进行并发重试。
2. 有非回卷的并发重试。在 $l_i$ 中X或Y有一个除了错误，表现为其中一个和S一样，另一个不一样，那么系统判断和S一样的是正确的
3. 在一次并发重试的间隔后进行回卷。XYS都不一样，也就是说有至少两个错的，那就在一次并发重试的间隔后进行回卷。系统卷回到 $l_i$ 的开始处。
4. 在并发重试的两次间隔之后回卷。该情况下在检查点间隔 $l_{i+1}$ 处出现了一个额外的错误， $l_i$ 中和S一样的那个在 $l_{i+1}$ 又不一样了。可以确定间隔 $l_i$ 中哪个进程是正确的，但是不能确定间隔 $l_{i+1}$ 中哪个进程是正确的。系统卷回到间隔 $l_{i+1}$ 的起始处。

检查点算法 ​

全局状态：一种全局状态的定义是一系列局部状态的集合，这里的局部状态就是一个进程的检查点，每个局部进程有一个局部状态

局部检查点可能组成如下两种不一致的全局状态：

1. 丢失报文。进程i的检查点状态显示它给进程j发送了报文m，但是进程j并没有关于该报文的纪录。
2. 孤儿报文。进程j的检查点状态显示它收到了一个来自进程i的报文m，但是进程i的状态显示它没有向进程j发送过报文m。

多米诺效应 ​

i崩溃了，返回检查点，这下m成孤儿报文了，j也回退，完啦，n也成孤儿了

一个强一致(strongly consistent)的检查点集合是由一系列的没有孤儿报文和没有丢失报文局部检查点组成。

一个一致的检查点集合是由一系列没有孤儿报文的局部检查点组成。

显然一个强一致的检查点集合包括一系列局部检查点，在这些检查点之间，进程之间没有报文传送。如果每个进程都在发送一个报文之后生成一个检查点，那么最近的检查点集合将永远是一致的

恢复线和切割线 ​

异步检查点 ​

异步检查点算法中程序中检查点状态的保存过程较为简单，程序中各进程周期性地相互独立地保存自己的运行状态，程序各进程之间不需要相互协商。

在恢复过程中，各进程之间则需要相互协商通过复杂的回卷算法各自回卷到合适的检查点时刻以使整个程序的各个进程恢复到最近的一个一致的全局状态。

一致检查点的检测方法：

1. 比较发送的和接收的报文数量来检测孤儿报文的存在。如果接收到的报文数目和任何发送报文的进程发送的报文的数目是一致的，那么就可以认为找到了一个局部检查点的一致集合。
2. 使用间隔依赖图来进行检测。如果每个进程i的向量时钟是LCi，一个检查点集合是一致的，当且仅当不存在i和j满足LCi＜LCj。

2是什么意思？？？？？？

优缺点：

优点是允许分布式程序的各个进程拥有最大程度的自治性，因而算法的延迟较小。

缺点之一是由于每个进程需要保存若干时刻的检查点信息，空间开销较大；
缺点之二是在恢复过程中可能会重复回卷，甚至出现多米诺效应，使程序一直回卷到初始状态。

同步检查点 ​

各相关的进程协调它们的局部检查点的建立行为，以保证所有的最近的检查点都是一致的。在同步检查点中，只有最近的一致的检查点集合才需要被维护和保存。

优缺点：

由于使用同步检查点算法，各进程的局部检查点组成的集合是一个全局一致的状态，所以在恢复时各个进程只需要简单地从检查点处重新开始执行。

同步检查点算法的优点是每个进程只需保存最近时刻的检查点信息，空间开销较小，且在恢复的时候没有多米诺效应。

其缺点是，在建立检查点时，各进程间的同步使程序运行中止时间较长，且牺牲了分布式程序的自治性

Sync-and-Stop(SNS)算法 ​

1. pc向所有进程广播检查点开始报文Mb(第一次同步开始)；
2. 任一个进程接收到报文Mb后停止运行，并在自己所发送的报文全部到达接收者后向pc进程发送报文Ms1；
3. pc接收到所有进程发送的报文Ms1后，即意味着第一次同步结束。pc向各进程广播报文Mchk，第二次同步开始；
4. 任一个进程接收到报文Mchk后，立即作局部检查点，检查点建立完成之后向pc发送报文Ms2；
5. pc接收到所有进程发送的报文Ms2后，意味着第二次同步结束。pc向所有进程广播报文Me；
6. 各进程接收到报文Me后，删除旧的检查点，仅保留新的检查点，然后继续执行。SNS算法的恢复过程十分简单，只需回卷到检查点处继续执行。

经过第一次同步之后，任何进程所发送的报文都已经被对应的接收进程接收到，任何进程之间不会存在孤儿报文，满足一致性的要求。

Chandy-Lamport(CL)算法 ​

1. 建立检查点的过程可由任一个进程pc发起，pc进程停止运行，并向与其所在机器直接相连的机器上的进程广播报文Mb，然后进程pc建立局部检查点；
2. 进程p接收到报文Mb后，若进程p还未开始建立检查点，则进程p停止运行并立即向与其所在机器直接相连的机器上的进程广播报文Mb，然后进程p建立局部检查点；
3. 进程p开始建立检查点后，若接收到其他进程发送的非检查点控制报文m，则保存报文m；
4. 当进程p完成局部检查点的建立，并且接收到与其所在机器直接相连的机器上的所有进程发送的报文Mb后，进程p向pc进程发送报文Ms；
5. 当进程pc接收到所有进程发送的报文Ms后，pc进程向所有进程发送报文Me，并删除本进程旧的检查点，进程pc继续执行；
6. 其他进程p接收到报文Me后，删除本进程旧的检查点，继续执行。

在恢复过程中，CL算法在回卷到当前检查点重新执行的同时还必须重发过程c)中保存的报文m。与SNS算法相比，CL算法减少了两次全局同步的开销。CL算法的缺点是其控制报文的数目与机器间的拓扑结构有关

混合检查点 ​

在一个较长的时间段中使用同步检查点，而在较短的时间段内使用异步检查点。在一个同步时间段里，会有若干个异步时间段。因此有一个可以控制的回卷，从而保证不会在建立检查点的过程中引入过多的开销。

准同步检查点。这个方法允许每个进程异步地设置检查点，从而保证了进程的独立性。同时，对恢复线的扩展采用发起通信的检查点协调方法，从而可以限制恢复过程中回卷的传播。

报文日志 ​

如果进程Pj记录了报文m的接收者日志，那么Pi和Pj的当前检查点集合就可以看作是一致的。一旦由于Pj由于失效回卷到当前检查点重新执行的时候，报文m就可以通过Pj的接收者日志重新发送给进程Pj，不会引起进程Pi的任何回卷。

如果Pi在发送完报文m后失效，那么当进程Pi恢复到当前检查点后，它会根据发送者日志的纪录知道曾经发送过报文m，这样就没有必要再发送一次了。如果接收者Pj失效，而且没有接收者日志，它仍然可以根据从发送者日志中得到的报文正确恢复。

可靠的组通信 ​

发给组内的报文必须确保传给了每一个成员

基本方案 ​

发送反馈报文，收到了发ACK，发现跳了一个序号就发NAK

可靠的组播通信的可扩展性 ​

简单方案 ​

只有发现丢失了才发反馈报文

问题：

1. 多个接收者丢失报文时，仍然会出现反馈报文拥塞的情况 ；
2. 在理论上讲，发送者必须在其历史缓冲区中长时间保存它发送的每一个广播报文。

非层级式反馈控制 ​

丢失发的反馈报文不仅发给发送者，还发给组内其他进程，这样同一个丢失报文只会有一个反馈报文

问题：

1. 需要对所有接收者的反馈报文精确调度，在广域网中十分困难
2. 组播反馈报文会对成功接收到报文的其他进程产生干扰。

层级式反馈控制 ​

进程组进一步划分为子进程组，形成树形结构。每个子进程组任命一个本地协调者，负责处理重发请求。本地协调者有自己的历史缓冲区。

原子组播 ​

一个进程在发送报文m的进程失效的时候，进程组的其他进程要么都收到报文m，要么所有的其他进程都忽略报文m，具有这种性质的可靠的组播被称为是虚同步的组播。

组播分类 ​

1. 无序组播。可靠的无序组播是一个虚同步组播，它不保证不同的接收进程对不同的组播报文的接收顺序
2. FIFO顺序组播。保证同一进程发送报文的顺序，不同进程有不同接收顺序
3. 因果关系顺序组播。按报文因果关系排序。无因果关系的报文顺序可以不同。
4. 全局顺序组播。不同的接收者必须按完全相同的顺序接收所有的报文

虚同步的实现 ​

问题：发送者可能在完成发送之前失效，造成有些进程收到报文，有些没有

解决方法：每一个获得报文的进程保存一份报文，直到该进程确定其他进程都收到了该报文。如果报文被所有进程收到，这个报文就是坚定的（stable）。只有坚定的报文才能被进程实际接收。为了确保坚定性，选择任何一个可操作的进程要求它将报文发送给所有其他的进程。