容错计算和恢复

1.容错的基础概念：

(1).容错的三个阶段
错误检测–评估损坏程度–错误恢复以消除错误并重新启动

(2).前向错误恢复:
当前正在执行的进程从某一点继续，并对损坏和丢失的数据进行补偿

• 可以准确评估导致检测和造成损害的精确错误条件
• 可以消除流程（系统）状态中的错误
• 流程可以向前推进

(3).后向错误恢复：
当前进程被回滚到某个无错误的点，并重新执行进程的损坏部分，从而继续相同的请求服务

• 故障的性质是无法预见的，流程（系统）状态中的错误在不重新执行的情况下无法消除
• 可以恢复到系统的先前无错误状态

2.前向和后向错误恢复的比较：

前向：
a.优势：开销比较低
b.劣势：无法为特定系统的恢复设计提供通用机制，并且需要损伤评估和预测

后向：
a.优势：独立于损害评估，即能够从任意损害中恢复
b.劣势：

• 性能损失-恢复进程状态的开销可能相当大
• 不保证重复处理时错误不会持续，例如永久性故障、软件设计错误
• 系统状态的某些组件可能不可恢复

3.检查点（Checkpoint)和回滚(Rollback)

适用条件

• 允许时间冗余
• 针对瞬态硬件和许多软件设计故障
• 适用于非冗余和冗余体系结构
• 保证检查点是可行的

检查点

定义：定期维护\保存精确的系统状态或“快照”

• 快照间隔可以小到一条指令
• 通常，检查点间隔包括多条指令
• 当存在大量错误检测延迟时，可能不理想

回滚恢复

• 将进程回滚（或恢复）到保存状态，即检查点
• 重新启动计算

4.Checkpoint和Rollback必须的条件

适当的错误检测机制

• 应用程序内部：各种自检机制（如数据完整性、控制流检查、验收测试）
• 应用程序外部：信号（如异常终止）、丢失心跳、监视器计时器

确定要检查的数据-进程状态

(1).易失性状态:

• 程序堆栈（局部变量、函数调用返回指针）
• 程序计数器、堆栈指针、打开文件描述符、信号处理程序
• 静态和动态数据段

(2).持久状态：
与当前程序执行相关的用户文件（是否在进程状态中包含持久状态取决于应用程序，例如，持久状态通常是长期运行应用程序的重要部分）

(3).将检查点数据存储在稳定的存储器中

(4).确定要记录和重播的事件：

• 消息Messages
• 事件Events
• 事务Transactions

(5).Checkpoint的确定

• 消逝时间
• 接收或发送的消息，例如并行或分布式应用程序
• 脏状态的数量，例如数据库应用程序
• 关键函数调用

(6).提供重新启动计算的程序
(7).提供处理持久性错误的方法

5.分布式系统中的恢复

(1).流程通过交换信息来协作完成任务:

• 消息传递
• 共享内存

(2).一个进程的回滚可能需要其他进程也回滚到较早的状态

(3).所有合作进程都需要建立恢复点

6.网络化/分布式系统：本地状态

1.对于站点（计算机、进程）$S_i$，其在给定时间的本地状态$L{S}_i$由分布式应用程序的本地上下文定义:

$send(m_{ij})$ - 对应“将消息$m_{ij}$从$S_i$ 传送到 $S_j$”这一事件
$rec(m_{ij})$ - 对应 "$S_j$收到从$S_i$传送的消息$m_{ij}$"这一事件
$time(x)$ - 记录状态x的时间

2.transit和inconsistent消息：
(1)当$time(send(m_{ij}))<time(L{S}_i)$时，$send(m_{ij})\in L{S}_i$
(2)当$time(rec(m_{ij}))<time(L{S}_j)$时，$rec(m_{ij})\in L{S}_j$

即在LS状态之前发生的send和rec，都属于状态LS，不是一个点，而是从开始到LS这一段时间

(3)为站点$S_i$和$S_j$定义了两组消息：

• t r a n s i t ( L S i , L S j ) = { m i j ∣ s e n d ( m i j ) ∈ L S i ∧ r e c ( m i j ) ∉ L S j } transit(LS_i, LS_j) = \lbrace m_{ij} | send(m_{ij}) \in LS_i \wedge rec(m_{ij}) \notin LS_j \rbrace transit(LSi​,LSj​)={mij​∣send(mij​)∈LSi​∧rec(mij​)∈/LSj​}
  

• i n c o n s i s t e n t ( L S i , L S j ) = { m i j ∣ s e n d ( m i j ) ∉ L S i ∧ r e c ( m i j ) ∈ L S j } inconsistent(LS_i, LS_j) = \lbrace m_{ij} | send(m_{ij}) \notin LS_i \wedge rec(m_{ij}) \in LS_j \rbrace inconsistent(LSi​,LSj​)={mij​∣send(mij​)∈/LSi​∧rec(mij​)∈LSj​}

7.网络化/分布式系统：全局状态

(1)系统的全局状态（GS）是其站点的局部状态的集合，即 G S = { L S 1 ， L S 2 ， … ， L S n } GS=\lbrace LS_1，LS_2，…，LS_n \rbrace GS={LS1​，LS2​，…，LSn​}，其中n是系统中站点的数量

(2)三种全局状态：

• 一致全局状态(Consistent global state)：$\forall i,\forall j:1\le i,j\le n::inconsistent(L{S}_i,L{S}_j)=\Phi$

• 无传输全局状态(Transitless globle state):$\forall i,\forall j:1\le i,j\le n::transit(L{S}_i,L{S}_j)=\Phi$

• 强一致全局状态(Strongly consistent global state)：一致且无传输的全局状态

…待更新

整理自Fault-Tolerant Computer System Design