分布式系统中的检查点与回滚恢复算法解析

### 分布式系统中的检查点与回滚恢复算法解析 在分布式系统中，故障是不可避免的。为了确保系统的可靠性和稳定性，检查点和回滚恢复机制显得尤为重要。本文将详细介绍两种重要的算法：Manivannan–Singhal准同步检查点算法和Peterson–Kearns基于向量时间的算法。 #### 1. 检查点与消息处理基础 在深入了解具体算法之前，我们先了解一些基本概念。在检查点和回滚恢复过程中，消息的处理至关重要。存在一条恢复线（recovery line），恢复线左侧发送的消息携带的化身编号（incarnation number）为0，右侧发送的消息携带的化身编号为1。 为避免消息丢失，当一个进程回滚时，必须重放其日志中接收操作被撤销但发送操作未被撤销的所有消息。也就是说，进程只需重放那些源自恢复线左侧且传递到恢复线右侧的消息。消息重放规则如下： - **消息重放规则**：进程 $P_j$ 回滚到检查点 $C$ 后，仅当消息 $M$ 在 $C$ 之后被接收且 $M.sn$（消息序列号）小于恢复线编号时，才会重放该消息。 当进程 $P_j$ 接收消息 $M$ 时，若此时 $P_j$ 正在从消息日志中重放消息，则会将消息 $M$ 缓冲，直到重放完成后再处理。若不这样做，可能会出现以下三种情况： | 情况 | 描述 | 处理规则 | | ---- | ---- | ---- | | 情况1：$M$ 是延迟消息 | 相对于恢复线，延迟消息的化身编号小于接收进程的化身编号。发送该消息的进程在发送时未意识到恢复过程。 | 若 $M.sn < rec\_line_j$，则先将 $M$ 记录到消息日志中再处理；否则，丢弃该消息。 | | 情况2：$M$ 在当前化身中发送 | 若 $inc_j = M.inc$，且 $M.sn < sn_j$，则在处理 $M$ 之前必须将其记录到消息日志中。 | 消息记录规则：若 $M.inc < inc_j$ 且 $M.sn < rec\_line_j$ 或 $M.inc = inc_j$ 且 $M.sn < sn_j$，则将消息记录到消息日志中。 | | 情况3：消息 $M$ 在未来化身中发送 | $M.inc > inc_j$。 | $P_j$ 将 $rec\_line_j$ 设置为 $M.rec\_line$，将 $inc_j$ 设置为 $M.inc$，然后回滚到序列号 $\geq rec\_line_j$ 的最早检查点。回滚后，按情况2处理消息 $M$。 | #### 2. Manivannan–Singhal准同步检查点算法 Manivannan–Singhal准同步检查点算法具有以下几个有趣的特点： - **通信诱导检查点**：智能地引导检查点活动，消除“无用”的检查点，确保每个检查点都位于一致的检查点上。 - **低消息开销**：检查点过程中没有额外的消息开销，仅在应用消息上附带一个标量。 - **恢复线一致性**：始终确保存在一条与任何进程的最新检查点一致的恢复线，有助于限制回滚恢复期间的回滚深度。 - **无多米诺效应**：失败的进程回滚到其最新检查点，并请求其他进程回滚到一致的检查点，避免多米诺效应。 - **垃圾回收**：进程建立恢复线后，可以删除该线之前的所有检查点，有助于垃圾回收。 - **综合优势**：结合了无协调检查点的简易性和低开销，以及协调检查点的恢复时间优势。 下面通过mermaid流程图来展示该算法的大致流程： ```mermaid graph TD; A[开始] --> B[进程运行]; B --> C{是否发生故障}; C -- 是 --> D[进程回滚到最新检查点]; D --> E[重放消息]; E --> F[处理接收消息（按三种情况）]; F --> G[恢复正常运行]; C -- 否 --> B; ``` #### 3. Peterson–Kearns基于向量时间的算法 Peterson–Kearns算法基于乐观回滚，使用向量时间来捕获因果关系，以识别失败进程回滚时成为孤立事件和消息。 ##### 3.1 系统模型 假设系统中有 $N$ 个处理器，逻辑上配置成一个环。每个处理器上运行一个进程，分别表示为 $P_0, P_1, P_2, \cdots, P_{N - 1}$，其中 $P_{(i + 1) \bmod N}$ 是 $P_i$ 的后继进程。 每个进程 $P_i$ 有一个向量时钟 $V_i[j]$（$0 \leq j \leq N - 1$）。进程在每次事件发生前会增加向量时钟的第 $i$ 个分量，并在每条消息中发送当前时间戳向量以更新接收进程的时钟。进程会定期对进程状态进行检查点操作，并在稳定存储上维护消息日志，同时定期记录传入消息的接收情况。 相关符号说明如下： - $e_i^j$：$P_j$ 上的第 $i$ 个事件。 - $s$：底层计算的发送事件。 - $\epsilon(s)$：发送事件 $s$ 发生的进程。 - $\pi(s)$：与发送事件 $s$ 匹配的接收事件发生的进程。 - $f_i^j$：$P_j$ 上的第 $i$ 次故障。 - $ck_i^j$：$P_j$ 上的第 $i$ 个状态检查点。 - $rs_i^j$：$P_j$ 上的第 $i$ 次重启事件。 - $rb_i^j$：$P_j$ 上的第 $i$ 次回滚事件。 - $LastEvent(f_i^j) = e'$ 当且仅当 $e' \prec rs_i^j$。 在回滚协议中，每个进程至少需要被联系一次，以指示发生了故障并发送恢复所需的信息。这一过程通过一系列的轮询波（polling wave）来实现。 ##### 3.2 算法的非正式描述 当进程 $P_i$ 在故障 $f_m^i$ 后重启时，会从稳定存储中检索其最新检查点（包括向量时钟值 $V_i(Latest\_ck(f_m^i))$），并回滚到该检查点。然后重放消息日志，直到日志耗尽。重放消息时，会相应地更新恢复进程的时钟值。 重放完成后，进程执行重启事件 $rs_m^i$，发起一个包含 $rs_i^m$ 向量时间戳的令牌消息，并将其发送给后继进程。进程 $P_i$ 会缓冲所有传入的应用消息，直到令牌返回，然后恢复正常执行。 令牌在环上的所有进程中循环。当令牌到达进程 $P_j$