可靠计算系统设计分析与验证课程笔记 2，内容对应 Sessions 3–5：Analytical Modeling，讨论可靠性与性能的联合指标，以及可靠性框图、Markov 链、故障树、排队模型、随机 Petri 网和 SAN

解析建模：把故障行为变成可计算的系统指标

上一篇定义了可靠性、可用性、失效率和修复率。本篇关注系统设计问题：组件以特定方式连接后，整体有多大概率提供服务；发生失效和恢复后，性能又会如何变化

解析模型必须先约定三件事：什么状态算服务成功，组件之间是否独立，以及研究的是某一时刻、整个任务期间，还是长期稳态。缺少其中任何一项，同一张系统图都可能得出不同的数值

从单个指标到系统目标

可用性、性能与降级

若平均正常运行时间为 $\mathrm{MTTF}$、平均修复时间为 $\mathrm{MTTR}$，在可重复的运行—修复周期下，长期可用性为

$$A_{ss}=\frac{\mathrm{MTTF}}{\mathrm{MTTF}+\mathrm{MTTR}}$$

在故障时间和修复时间分别服从指数分布、对应速率为 $\lambda,\mu$ 时，也可写成

$$A_{ss}=\frac{\mu}{\lambda+\mu}$$

例如“五个 9”即 $A_{ss}=0.99999$，若一年按 $365.25$ 天计算，期望停机时间约为 $365.25\times24\times60\times(1-0.99999)=5.26$ 分钟。这个数是长期平均值，不能单独说明一次中断会持续多久

系统正常运行时还要观察执行时间、吞吐量、请求延迟、网络抖动、丢包率和资源利用率。组件失效后，服务也可能继续运行但变慢，例如缓存失效导致请求延迟增加。为了同时描述可靠性与性能，定义阈值 $L$ 下的 performability：

$$P(L,t)=\Pr\{\text{时刻 }t\text{ 的系统性能}\geq L\}$$

阈值必须对应具体指标，如“吞吐量至少为每秒 $1000$ 次请求”；只看进程是否存活会遗漏已经无法满足业务要求的降级状态

为可靠性付出的开销

冗余和恢复机制消耗资源。若原方案占用资源 $C_0$，新方案额外增加 $C_r$，空间开销率可写成 $C_r/C_0$。三模冗余（TMR）仅计算三份执行单元时，额外开销是原方案的 $200\%$，投票器及其连接还会继续增加成本

检查点则主要带来时间和 I/O 开销。若每次有效计算持续 $T_e$，保存检查点耗时 $T_{ck}$，在暂不考虑故障时，每轮总耗时 $T_e+T_{ck}$。相对原计算时间的增加比例为 $T_{ck}/T_e$，而总时间中用于检查点的比例为 $T_{ck}/(T_e+T_{ck})$。两种分母不同，比较方案时应明确采用哪一个

发生故障后，还要考虑 RPO（可接受的数据回退时间）和 RTO（可接受的恢复耗时）。对定期检查点与回滚，若两次检查点间的有效计算间隔为 $T_e$，最坏情况下可能丢失接近 $T_e$ 的进度；RTO 则包括检测、读取检查点和恢复运行所需的时间。缩短间隔可以改善 RPO，却会增加常态开销

可靠性框图：组合静态成功条件

可靠性框图（Reliability Block Diagram，RBD）把服务成功表示为从入口到出口至少存在一条由正常组件组成的路径。框图中的“串联”和“并联”描述成功条件，未必是设备的物理布线

设各组件独立，$q_i$ 是组件在研究时间点成功的概率。串联系统要求全部组件正常，并联系统只要求至少一个正常，因而

$$q_{\mathrm{series}}=\prod_{i=1}^{n}q_i, \qquad q_{\mathrm{parallel}}=1-\prod_{i=1}^{n}(1-q_i)$$

这里的 $q_i$ 可以是任务期间的可靠性 $R_i(t)$，也可以是某一时刻的可用性 $A_i(t)$；选定后应在整张图中保持一致。若组件失效相关，两个乘积公式通常不能直接使用

一个有共享底层设备的例子

讲义中的服务依次经过同一物理机上的三台虚拟机 $V_1,V_2,V_3$，并可从两个端口中的任意一个进入。令 $A_H$ 为物理机可用性，$A_{V_i}$ 为虚拟机在主机正常条件下的可用性，$A_{P_j}$ 为端口在主机正常条件下的可用性。在这些条件事件相互独立的简化模型中

$$A_{\mathrm{service}} =A_H A_{V_1}A_{V_2}A_{V_3} \bigl[1-(1-A_{P_1})(1-A_{P_2})\bigr]$$

物理机是共同前提，不能把它当成三台虚拟机各自独立的底层条件而重复相乘。主机故障也可能同时影响两个端口，因此实际使用公式时还要确认端口的失效独立性

桥式结构与条件分解

复杂框图未必能直接化成简单的串并联。任选一个组件 $B$，按它是否正常分解系统成功事件 $S$：

$$\Pr(S)=\Pr(B)\Pr(S\mid B) +\bigl[1-\Pr(B)\bigr]\Pr(S\mid\neg B)$$

给 $B$ 固定状态后，原图往往更容易简化。这一招可以反复使用，但组件数增加时，逐个枚举所有状态的成本会迅速上升。RBD 适合描述静态成功路径；故障发生顺序、修复和重配置需要状态模型

Markov 链：把失效和修复写成状态转换

连续时间 Markov 链用状态表示当前系统状况，用转移速率表示状态变化。Markov 性质要求已知当前状态后，未来演化不再依赖更早的历史。常失效率、常修复率的指数等待时间满足这一要求

单台可修复服务器

设服务器从正常到失效的速率为 $\lambda$，从失效到正常的修复速率为 $\mu$。令 $p_U,p_D$ 分别为稳态下正常和失效的概率。正常与失效之间的概率流量平衡，再加上概率和为 $1$：

$$p_U\lambda=p_D\mu, \qquad p_U+p_D=1$$

所以

$$p_U=\frac{\mu}{\lambda+\mu}, \qquad p_D=\frac{\lambda}{\lambda+\mu}$$

$p_U$ 就是稳态可用性。这个两状态模型与上一节的 MTTF、MTTR 公式相符，其中 $\mathrm{MTTF}=1/\lambda$、$\mathrm{MTTR}=1/\mu$

三台主动／被动服务器

讲义进一步考虑三台服务器，任一时刻最多一台处理请求。活动服务器故障后立即切换到正常的备用服务器；一名维修人员以速率 $\mu$ 修复一台故障服务器。令状态 $k$ 表示仍有 $k$ 台正常服务器，则 $k\to k-1$ 的速率为 $k\lambda$，$k\to k+1$ 的速率为 $\mu$。服务在 $k\geq1$ 时可用

设 $p_k$ 为稳态处于状态 $k$ 的概率。相邻状态满足

$$p_k\,k\lambda=p_{k-1}\mu, \qquad p_k=\frac{(\mu/\lambda)^k}{k!}p_0$$

由 $\sum_{k=0}^3p_k=1$，得到

$$p_0=\left[\sum_{k=0}^{3}\frac{(\mu/\lambda)^k}{k!}\right]^{-1}, \qquad A_{ss}=1-p_0$$

这个模型显式表达了“几台已坏”“是否仍能服务”和“维修人员一次只能修一台”。若切换有延迟、维修人员有多名，或故障会同时影响多台机器，状态与转移速率都必须相应改变。Markov 链能刻画动态行为，但列出所有组件状态可能遇到状态爆炸

故障树：从顶层失效追溯原因

故障树分析（Fault Tree Analysis，FTA）从一个顶层失效事件出发，用 AND、OR 门逐层展开可能原因。RBD 从“怎样成功”组织模型，FTA 从“怎样失败”组织模型，二者对相同静态逻辑可以得到一致的概率

例如汽车不能行驶可能由爆胎、丢钥匙或电池没电导致。若三个基本事件独立，概率分别为 $p_1,p_2,p_3$，顶层 OR 门的概率为

$$p_{\mathrm{stop}}=1-(1-p_1)(1-p_2)(1-p_3)$$

若顶层失效必须由两个独立事件同时出现，AND 门的概率为 $p_1p_2$。分析时要特别注意重复的基本事件和共同原因：同一事件出现在不同分支里，不能把两个分支当作独立事件相乘。故障树适合整理静态故障组合，单独使用时不表达故障发生顺序和修复过程

排队模型：可靠系统还要处理请求

服务没有停机，并不代表用户请求能及时完成。排队模型研究到达、处理和等待之间的关系，常写为 $A/B/c/N/K$：到达间隔分布、服务时间分布、并行服务器数、系统容量和潜在请求源规模。其中 $M$ 表示指数间隔，$D$ 表示确定时间，$E_k$ 表示 $k$ 阶 Erlang 分布，$G$ 表示一般分布

M/M/1 的稳态分布

最基本的 M/M/1 模型假设请求以速率 $\lambda$ 到达，一台服务器以速率 $\mu$ 处理请求，系统容量无限。令 $N$ 表示系统中正在处理和等待的请求总数，$p_n=\Pr(N=n)$，相邻状态的平衡式为

$$p_n\lambda=p_{n+1}\mu$$

设 $\rho=\lambda/\mu$。只有 $\rho<1$ 时，概率才能归一化为稳态分布：

$$p_n=(1-\rho)\rho^n, \qquad n=0,1,2,\ldots$$

由几何级数可得到服务器利用率 $\rho$、系统内平均请求数 $E[N]$ 和平均停留时间 $E[W]$：

$$E[N]=\frac{\rho}{1-\rho}, \qquad E[W]=\frac{E[N]}{\lambda}=\frac{1}{\mu-\lambda}$$

当 $\lambda$ 接近 $\mu$ 时，即使服务仍然可用，平均等待时间也会迅速上升。容量规划还可利用 $\Pr(N\geq K)=\rho^K$ 估计系统中同时积压至少 $K$ 个请求的频率。有限容量、多个服务器或其他调度策略需要换用相应的排队模型

随机 Petri 网与 SAN：表达并发和组合行为

Petri 网用库所表示条件或资源，用令牌表示当前数量，用变迁表示事件。变迁从输入库所消耗令牌，并向输出库所放入令牌；只有输入条件满足时，变迁才被启用。这种表示法适合描述多个事件并发发生

随机 Petri 网（SPN）为部分变迁赋予随机等待时间，常见设定是指数分布。启用与真正触发之间的时间差可以表达请求处理、组件失效或修复；扩展形式还允许立即变迁和守卫条件。给定初始标识和速率后，纯指数型 SPN 的可达标识可映射为连续时间 Markov 链，再用数值方法求解；标识数量也可能很大

公共队列与独立队列

讲义用三台服务器比较两种组织方式。在公共队列中，请求共享一个队列，由可用服务器处理，能够更充分利用处理能力，但公共队列本身是单点故障。在独立队列中，每台服务器有自己的队列，一个队列失效不直接使其他队列失效，但请求可能集中在繁忙队列，造成资源利用不均

SPN 可以同时描述请求到达、排队、处理、丢弃、服务器失效和修复。为比较两种设计，可在处理变迁上累计已完成请求数 $N_{\mathrm{done}}$，在到达变迁上累计总请求数 $N_{\mathrm{arrive}}$，再观察 $N_{\mathrm{done}}/N_{\mathrm{arrive}}$。这个比值把可靠性和吞吐结果连接起来，比单独报告服务器可用性更接近用户体验

随机活动网络（SAN）进一步扩展 SPN：活动可以有更一般的启用与完成规则、非指数等待时间、即时活动，以及按概率选择不同的结果；输入门和输出门可以读取或修改更复杂的状态。它能表达更丰富的系统行为，但也更依赖数值求解和离散事件仿真。对 Markov 链、SPN、SAN 都可附加奖励模型，为状态或变迁分配收益，累计有用工作、处理请求数或停机代价

案例：大规模超算的协同检查点

讲义最后用 SAN 研究大规模超算的全局协同检查点。系统包含计算节点、I/O 节点与存储，多个并行任务同步推进；当计算节点失效时，所有任务回滚到最近一次完成的检查点。检查点不能覆盖尚未成功提交的上一份副本，否则一次保存失败会破坏恢复基础

评估时使用两个指标：有用工作比例是时间中真正推进任务、且未来不因回滚而重做的部分；总有用工作等于有用工作比例乘以计算处理器数量。增加处理器一方面提高并行计算能力，另一方面也增加系统遇到故障的机会，因此总有用工作未必单调上升

在讲义给定的示例参数下，每节点 MTTF 为 $1$ 年、系统恢复时间为 $10$ 分钟、检查点间隔为 $30$ 分钟，约 $128\mathrm K$ 个处理器时总有用工作达到峰值。该场景的有用工作比例低于 $50\%$，超过一半的时间用于检查点、恢复和故障造成的重复计算。这是特定模型与参数下的结果，不能直接当作所有超算的通用阈值

模型还比较了两类相关故障。恢复过程中的错误传播在所研究场景下影响较小，因为恢复时间短于计算间隔；共同原因故障则可能显著降低有用工作，并限制可扩展规模。这个区别说明，简单地把每个节点视为独立失效，会高估大规模系统的收益

如何选模型

建模时先写清服务成功条件和目标指标，再选择能表达必要行为的最简单模型。若模型中使用独立故障、指数等待时间或瞬时切换等假设，最后的结论也应明确限定在这些假设下