可靠计算系统设计分析与验证课程笔记 6：从硬件冗余与投票出发，推导 TMR、任务可靠性和切换覆盖率，再讨论鲁棒数据结构、N 版本程序设计、恢复块、进程对与在线升级

硬件与软件容错

故障注入可以告诉我们错误怎样传播，以及检测和恢复在哪一步失效。接下来的问题是：怎样安排冗余、检测和状态恢复，使系统在故障出现后仍能提供符合要求的服务？

容错设计需要回答三件事：依靠什么判断结果可信，发生错误后由谁继续执行，以及继续执行时使用什么状态。硬件投票、软件多样性、恢复块和主备进程，对这三个问题采用了不同的组织方式

硬件冗余的三种基本形式

Triple Modular Redundancy（TMR，三模冗余）是典型的屏蔽冗余。三个副本执行相同功能，由多数表决决定输出，一个副本错误时仍可维持正确服务

备用冗余把资源留给接管过程，需要发现当前模块失效并完成切换。混合冗余则在暂时屏蔽错误的同时，用备件恢复冗余度，避免系统长期停留在保护能力已经降低的状态

串联、并联与 M-out-of-N 模型

以下公式均针对给定任务时间 $t$，并先假设组件失效相互独立。用 $R_i(t)$ 表示第 $i$ 个组件在任务期间正确工作的概率

串联与并联

串联系统要求所有组件都正确工作，因此

$$R_{\mathrm{series}}(t)=\prod_{i=1}^nR_i(t)$$

并联系统只要求至少一个组件可提供所需服务，因此

$$R_{\mathrm{parallel}}(t)=1-\prod_{i=1}^n(1-R_i(t))$$

这里的“并联”是一种成功条件：存在可用分支就能获得正确服务。实际系统是否满足这一条件，还取决于能否识别和使用正确分支，以及共享接口和资源是否正常

M-out-of-N 系统

若 $N$ 个独立同分布的模块中至少有 $M$ 个正确工作，系统就成功，则

$$R_{M/N}(t)=\sum_{k=M}^{N}\binom NkR(t)^k(1-R(t))^{N-k}$$

TMR 的模块部分对应 $2$-out-of-$3$。对于普通多数表决，$M$ 还需要构成严格多数，并且正确副本必须对同一个逻辑输入产生一致结果。一般的 $M$-out-of-$N$ 成功条件，并不都由一个多数投票器实现

TMR 的可靠性及其适用范围

把投票器也计入模型

设三个模块独立，可靠性均为 $R$；投票器可靠性为 $R_v$，并与模块独立。按“至少两个正确模块加上正确投票器”的成功模型，有

$$\begin{aligned} R_{\mathrm{TMR}} &=R_v\left[R^3+3R^2(1-R)\right]\\ &=R_v(3R^2-2R^3) \end{aligned}$$

其中 $R^3$ 对应三个模块都正确，$3R^2(1-R)$ 对应恰有两个正确。若投票器完美，即 $R_v=1$，则

$$R_{\mathrm{TMR}}-R=R(1-R)(2R-1)$$

所以对 $0<R<1$，只有 $R>1/2$ 时 TMR 才比单模块更可靠。副本的可靠性已经很低时，多数表决并不能保证改进

投票器也会影响结论。例如 $R=0.99$ 时，完美投票器下的结果为 $0.999702$；若 $R_v=0.99$，则整体只有约 $0.989705$，已经低于单模块的 $0.99$

为什么任务可靠性提高，MTTF 却可能降低

假设每个模块寿命服从速率为 $\lambda$ 的指数分布，系统不维修，投票器完美，则单模块可靠性为

$$R_{\mathrm{simplex}}(t)=e^{-\lambda t}$$

代入 TMR 公式，得到

$$R_{\mathrm{TMR}}(t)=3e^{-2\lambda t}-2e^{-3\lambda t}$$

对非负寿命，平均失效前时间为可靠性函数的积分，因此

$$\mathrm{MTTF}_{\mathrm{simplex}} =\int_0^\infty e^{-\lambda t}\,dt=\frac1\lambda$$

$$\boxed{ \mathrm{MTTF}_{\mathrm{TMR}} =\frac3{2\lambda}-\frac2{3\lambda} =\frac5{6\lambda}<\frac1\lambda }$$

这与短时间内的改进并不矛盾。由 $e^{-\lambda t}=1/2$，得到交点

$$t_0=\frac{\ln2}{\lambda}$$

TMR与单模块的可靠性曲线

横轴为无量纲时间 $\lambda t$。在 $0<t<t_0$ 时，TMR 的任务可靠性较高；超过交点后，单模块的可靠性较高

在短任务中，TMR 要累积到两个模块失效才失去多数；在长时间无维修运行中，冗余逐渐耗尽，系统仍要求至少两个模块存活。MTTF 把整个时间轴都积分进去，因此会得到不同于短任务可靠性的比较

对于固定时长的任务，应直接比较该时间内的 $R(t)$；对于可维修服务，应建立包含检测、维修和重配置的模型。允许重配置为单模块继续运行的系统，也已经不是上述静态 TMR 模型

多级冗余与投票器设计

整机复制与逐级投票

假设原系统由 $n$ 个串联阶段组成，各阶段可靠性均为 $R$。可以把整个系统复制三份，最后投票，也可以在每一阶段分别设置 TMR

在所有基本模块独立、投票器完美的简化模型下，两种结构分别为

$$R_{\mathrm{whole}}=3(R^n)^2-2(R^n)^3$$

$$R_{\mathrm{stage}}=(3R^2-2R^3)^n$$

逐级投票能够在阶段边界消除单路错误。例如第一阶段的 A 路与第二阶段的 B 路分别故障时，逐级投票仍可能保住每一阶段的多数；整条执行链复制则可能已经损失两条完整链

代价是更多投票器与互连。若每级投票器的独立可靠性均为 $R_v$，逐级模型中还要乘入 $R_v^n$，因此实际设计需要同时考虑隔离效果和新增部件

投票器的职责不止输出多数值

投票系统通常还需要比较器和分析逻辑，判断哪个输入与其他输入不一致，为隔离、告警和重配置提供依据

Tandem Integrity 的一个设计把投票器分成多数生成部分和投票分析部分，并复制投票逻辑进行比较，以检测投票逻辑自身的异常。对外部 I/O，则在各 CPU 上进行分布式的本地多数表决

多个投票器可以减少对单个投票部件的依赖，但仍需分析它们共享的输入、互连、电源以及后续输出边界。把“模块加投票器”合成一个可靠性单元时，也要检查单元之间是否确实满足独立性假设

软件投票还需要对齐输入

硬件可以使用锁步或一定程度的同步机制组织投票。网络化软件副本的执行速度和通信延迟则可能不同，投票前需要确认收到的结果属于同一请求、同一轮次和相容的状态

否则，某个副本的上一轮结果可能与另一个副本的当前结果被错误地比较。超时同样需要权衡：过早放弃会误判慢副本，等待过久则可能超过服务期限

对于浮点结果，还需要定义比较规则。容差范围、异常值处理以及决策算法本身，都属于容错机制的一部分

备用系统：覆盖率决定冗余能否被用上

一个备用模块的简化模型

考虑主模块和一个备用模块。设主模块满足任务的概率为 $R_1$，备用模块满足接管需求的概率为 $R_2$，检测并完成接管的条件成功概率为 $c$，在相应独立性假设下

$$R_{\mathrm{sys}}=R_1+c(1-R_1)R_2$$

其中 $c$ 是覆盖率：故障确实发生且需要接管时，系统能够正确发现、定位并恢复服务的概率。它可以包括检测器漏检、切换失败和状态恢复失败的影响，具体含义必须在模型中固定

这个表达式把接管结果压缩成一次概率事件。若要分析冷备用的寿命，应根据失效时刻计算备用模块接管后的剩余任务时间，并区分待机与工作状态下的失效率

为什么备件越多，收益仍会饱和

进一步使用一个顺序尝试的简化模型：总共有 $n$ 个候选模块，每个成功概率均为 $R_m$，每次遇到一个失败模块后，成功转向下一个的条件概率均为 $c$，各步骤按模型相互独立

前 $i$ 个模块都失败、每次转换成功、第 $i+1$ 个模块成功的概率为

$$R_m[c(1-R_m)]^i$$

因此

$$R_n=R_m\sum_{i=0}^{n-1}[c(1-R_m)]^i =R_m\frac{1-[c(1-R_m)]^n}{1-c(1-R_m)}$$

当 $R_m>0$ 时，令 $n\to\infty$，得到

$$R_\infty=\frac{R_m}{1-c(1-R_m)}$$

若 $c=1$，这个极限为 $1$；若 $c<1$ 且 $R_m<1$，它严格小于 $1$。只增加模块数量，无法消除转换环节中的失败概率

例如固定 $R_m=0.7$：

覆盖率较低时，改进检测、状态准备和接管协议，可能比继续增加备件更有效。上一篇的故障注入，正可以用于测量这些环节的条件成功率

高可用集群中的冗余与状态

物理上的副本数量只是起点。集群是否能持续服务，还取决于副本的状态组织和故障域划分

共享存储与应用级复制是不同的状态组织方式。共享存储方便接管访问同一份数据，但存储本身需要保护；各副本独立存储时，则需要明确复制和恢复协议

副本应位于能够支撑故障假设的不同故障域。仅把两个虚拟机放在不同名称下，无法隔离共同宿主机、电源或网络故障

对于主备系统，还要避免网络分区后两个节点同时对外写入。接管除了“认为旧主失效”，还需要确保旧主不能继续执行冲突操作，例如通过隔离旧主的 I/O 权限来维护单一写入者

软件容错为什么需要多样性

软件缺陷通常由某类输入、状态或执行交错激活。同一个程序的两个副本如果接收相同输入，并以相同方式到达缺陷位置，可能同时产生同样的错误

因此，复制软件可以帮助应对进程、机器或某些运行环境的失效，但要容忍共同的软件设计缺陷，还需要考虑不同实现、不同算法、不同运行路径或恢复环境

软件保护可以分为几个互相补充的方向：

• 鲁棒性：检查非法输入和异常条件，拒绝、修正或降级处理
• 错误遏制：通过模块边界、断言和资源隔离，限制错误传播
• 恢复与替代执行：恢复可信状态，使用备用实现或备用进程完成任务

这些机制仍依赖一个可以判定的服务要求。降级输出是否可接受，需要由规格决定，而不是把任何继续运行都算作成功

鲁棒数据结构：用结构冗余发现损坏

结构完整性与语义完整性

数据结构有两类不同的正确性：

• 结构完整性：指针、计数、节点类型和连接关系符合表示规则
• 语义完整性：数据表示的业务含义正确，例如余额、资源归属或排序关系符合要求

冗余指针和节点计数能够帮助保护结构，但一个连接关系完全正确的链表，仍可能存放错误的业务数值

从普通单链表到带检查信息的链表

普通单链表只保存 next 指针，并用空指针表示结束。如果头指针被错误改成空指针，系统可能把原本非空的链表误认为空表；缺少额外信息时，很难判断这是否为合法状态

可以加入以下冗余：

1. 节点类型或身份标识，用于判断当前指针是否指向预期节点
2. 头节点中的节点数量，供遍历结果核对
3. 尾节点指回头节点，形成可检查的结束条件

这样，计数损坏可能通过遍历长度发现，指针损坏可能表现为数量不匹配、错误节点类型或无法按预期回到头节点。遍历检查本身也需要处理非法地址和异常循环，避免检查过程再次挂起

这些措施为检测提供了额外证据，但发现计数不一致后，仍需要判断是计数错误还是链路缺失，不能仅凭两者不同就确定原始结构

双向指针提供恢复信息

双向链表额外保存 prev。对于带头节点的循环双向链表，正常状态满足

$$\operatorname{prev}(\operatorname{next}(x))=x$$

$$\operatorname{next}(\operatorname{prev}(x))=x$$

如果一个方向的指针集合保持完整，就可以沿该方向遍历，重建另一个方向的连接关系。恢复能力依赖于可信的头节点、节点存活情况、损坏位置，以及能否判定哪一组信息正确

例如 x.next.prev 与 x 不一致时，错误可能在 x.next，也可能在目标节点的 prev。若两套指针同时损坏，单纯增加一个反向指针就不足以保证恢复

结构冗余也会增加更新复杂度。插入节点需要同步修改多个指针和计数，如果更新代码本身有缺陷，可能同时破坏多个字段；并发检查还需要避开合法的更新中间状态，或通过同步机制获得一致观察

N 版本程序设计：用不同实现交叉检查

N-version programming（NVP）为同一功能开发多个实现，在相同输入下运行，再由决策算法比较结果

对于三个版本，可以使用多数表决；对于两个版本，比较通常只能发现不一致，要决定哪个正确，还需要额外检查或可信参考

开发多样性如何组织

可以让不同开发团队采用不同算法、语言、实现结构或工具链，同时依据共同的功能规格工作。执行环境负责分发输入、控制版本运行、收集输出并执行决策

目标是减少版本之间相同的缺陷，而独立开发的流程本身并不证明失效在概率上独立。多个团队可能同时误解同一个边界条件，也可能共同受到规格遗漏的影响

多数失效概率不是所有版本同时失效的概率

设三个版本在某一输入分布下各自失效的概率均为 $p$，先假设相互独立。在“两个及以上版本错误就判为系统失败”的二取三模型中

$$P_{\mathrm{fail}}=3p^2(1-p)+p^3=3p^2-2p^3$$

$p^3$ 只表示三个版本同时失效，遗漏了两个版本失效的情况。实际投票还需要定义错误输出是否相同、没有多数时如何处理，以及决策器是否会失败

共同规格缺陷则可能让多个版本在同一输入上输出相同的错误结果。这时投票器看到了完全一致的答案，却没有正确答案可以保留

历史上的 PODS 多样化软件实验就观察到了由需求遗漏和歧义引起的共同错误。多样性可以有价值，但其效果需要用相同测试输入下的联合失效行为来评估

决策算法也属于可信基础

NVP 可以减少顺序重试带来的延迟，但仍有多版本执行、结果同步和投票开销。比较浮点值、处理超时与异常输出、决定无法形成多数时的行为，都需要明确规则

不同版本如果复用相同的关键库、配置和外部依赖，也可能重新引入共同失效来源。因此，多样性需要覆盖真正影响失效的因素

恢复块：检查失败后回退并尝试替代实现

恢复块（Recovery Block，RB）把一个功能组织成主实现、若干替代实现和一个验收测试。进入恢复块时建立恢复点，先执行主实现；若验收失败，则恢复入口状态，再尝试下一个实现

恢复块的顺序重试与NVP的并行决策

左侧的恢复块在验收失败后选择下一种实现，右侧的 NVP 汇集并行执行的结果后决策。恢复块的每次尝试都必须先回到同一个可信入口状态，避免前一次修改污染后续执行；所有替代实现均失败时，向外报告恢复失败

验收测试检查什么

验收测试判断结果是否满足规定的可接受条件，可以检查输出范围、状态不变量、结构完整性或业务约束

例如排序结果的验收可以包括：输出有序，并且输出保留输入的元素多重集。只检查有序性，会错误接受一个有序但遗漏元素的结果

验收测试不一定能完整证明算法正确，其覆盖率和运行开销需要一起评估。它通常应围绕输出与块外可见状态设计，而不是依赖某个实现特有的局部变量

测试本身还应避免留下影响后续尝试的副作用。例如测试修改了一个状态标志，使下一个实现未经真正验证就被接受，就会破坏恢复块的逻辑

恢复缓存怎样减少复制成本

每进入一个恢复块就复制整个系统状态，成本往往过高。恢复缓存可以记录恢复范围内首次被修改变量的旧值，在失败时按记录恢复

它主要关注退出恢复块后仍然可见的状态，以及其他必须保持一致的受管资源。嵌套恢复块则需要区分各层恢复点，使内层回退不会破坏外层所需的信息

内存回退无法自动撤销已经发出的消息、写入外部系统的数据或真实设备动作。可以在验收前缓存输出、使用事务提交，或设计补偿操作，把这些副作用纳入恢复协议

替代实现可以提供受约束的降级

替代实现不一定追求与主实现相同的性能。主算法失败后，可以使用较慢但结构更简单的算法，或者在规格允许时提供精度较低、功能较少的服务

旧版本也可能被用作替代实现，但它可能共享同一个缺陷。选择替代方案时仍要分析故障相关性，以及降级结果能否通过同一组服务要求

多进程恢复：Conversation

单进程只需恢复自己的状态。多个进程已经交换消息后，单独回退一个进程可能产生不一致：接收方保留了某条消息的影响，而发送方回退到尚未发送该消息的状态

Conversation 将一组会相互作用的进程纳入共同恢复范围：

1. 各参与进程进入时建立 checkpoint
2. 在该范围内，通信限于参与者之间，外部交互需要被隔离或延后
3. 任一参与者检测到错误，所有参与者恢复到各自的入口状态
4. 各进程执行相应的替代方案
5. 所有参与者都通过验收后，才能共同完成这次 conversation

这种方法把状态恢复与进程之间的依赖一起处理。嵌套 conversation 允许较小的交互范围先完成局部恢复，但边界和参与者必须保持一致

如果不协调通信依赖，一个进程的回退可能迫使其他进程继续回退，再触发更早的回退，形成多米诺效应。恢复边界的作用，就是约束错误及回退需要影响的范围

恢复块、NVP 与自检查组件怎样比较

还有一种组织方式是并行运行多个自检查组件。每个组件可以是一份实现加验收测试，也可以是两份实现加比较器，再由上层选择检查通过的结果

它把“判断本组件结果是否可接受”和“从可用组件中选择结果”分开，常称为 N self-checking programming（NSCP）

从组织方式看，恢复块类似备用切换，NVP 类似静态模块冗余，自检查组件则结合了并行执行与动态选择。硬件和软件机制之间有这种结构对应，但软件的共同设计缺陷仍需要单独分析

恢复块特别适合能保存状态、构造验收测试且允许重试的任务；NVP 更适合需要并行得到结果、能够对齐输出并承担多版本开发成本的任务。两者都需要对共同规格错误和外部依赖建立保护

进程对：主进程服务，备用进程保留恢复基础

进程对（Process Pairs）在不同处理器上运行主进程和备用进程。通常只有主进程向外提供服务，主进程定期向备用发送 checkpoint；主进程失效后，备用根据保存的状态接管

这种方法适合松耦合、消息通信的系统，尤其适合能够明确事务边界和请求状态的服务。它通过运行环境和故障域的冗余来恢复执行，不要求像 NVP 那样开发多个功能版本

Fail-fast 假设为什么重要

进程对通常依赖组件在发现不可恢复错误后尽快停止，避免继续传播错误状态。操作系统检测到严重错误时终止处理器或进程，其他节点通过存活消息和状态通知触发接管

如果主进程已经产生错误业务数据，却继续将其作为正常 checkpoint 发给备用，备用就可能复制同一份损坏状态。因此，检测覆盖率和 checkpoint 的可信性是进程对的关键条件

相同软件在改变后的环境中重新执行，有机会绕开瞬态故障或与时序有关的触发条件。但若错误由确定性的输入缺陷引起，备用使用相同输入执行相同代码，也可能再次失败

Tandem Guardian 的组织方式

在 Tandem Guardian 的进程对机制中，主进程在另一处理器上启动备用，并向其传送恢复所需的数据、文件状态和程序位置等信息。文件活动配合镜像或相应的副本机制维护

备用接收 checkpoint 并更新恢复状态，当系统报告主处理器失效，或存活检测触发接管时，备用继续执行。运行中的主进程也检查备用是否存在，必要时重新建立备用，使系统恢复冗余能力

这里要分别验证三个层次：进程内存是否同步，文件或外部数据是否同步，以及客户端是否知道某次请求已经完成。只恢复内存无法自动解决后两者

事务重试：完成了请求却没有收到确认

考虑客户端发送一次写请求，服务端已经完成写入，但在返回结果前崩溃。客户端超时后会重试，如果新主把它当成全新请求执行，就可能造成重复效果

一种处理方式是为请求分配序列号，并将请求状态和已完成结果一起纳入恢复信息

请求序列号与主备checkpoint的时序

对已经完成的重复请求，服务端应返回保存的结果；对尚未完成的请求，则按事务状态决定继续执行、回退或重新执行。这里的请求标识应能区分客户端和请求，不能仅靠多个客户端都从零开始的本地计数

序列号需要与提交状态一起持久化

只保存序列号仍然不够。假如数据已经写入，但“请求已完成”的记录尚未保存就发生崩溃，备用仍可能无法判断是否需要再次执行

因此，数据效果、请求完成记录和结果之间需要一致的提交协议，例如使用事务日志协调，或把操作设计为按同一请求标识重复执行也不会改变最终效果

这可以把接管验证具体化为几个故障窗口：

• 请求被接收，但尚未写入数据
• 数据已经改变，但完成记录尚未持久化
• 完成状态已经同步，但响应尚未发出
• 响应已经发出，但客户端尚未保存完成状态

上一篇的定向故障注入可以分别命中这些窗口，验证恢复后既不丢失已经承诺的结果，也不重复产生业务效果

在线软件升级：把计划内变化组织成受控切换

容错结构也可以支持在线升级。对于主备或 Active-Passive 组织，可以保留旧进程服务，同时准备新的升级进程

一种事务边界上的切换流程是：

1. 启动并初始化升级进程，准备所需状态
2. 升级进程报告准备完成
3. 旧进程停止接收新的事务，入口队列暂存后续请求
4. 旧进程完成已经开始的事务，双方同步最终状态
5. 确认切换条件满足，移交服务职责
6. 升级进程开始处理队列中的新事务

准备阶段失败时，可以保持旧进程继续服务，并重新安排升级。成功移交后，也需要重新建立备用，使升级后的服务不长期处于缺少保护的状态

版本变化带来新的状态相容问题

旧版本和新版本可能使用不同的数据布局、协议或不变量。升级进程“已经启动”，并不代表它已经能够解释旧进程留下的全部状态

因此切换条件应包含状态转换完成、事务边界明确以及接口相容性。若计划保留回退能力，还要考虑新版本写出的状态能否被旧版本读取，或是否存在可靠的反向转换

在线升级的服务目标也应说明是否允许短暂排队、连接重建或延迟增加。把中断压缩到很小，与完全没有可见服务波动，是不同的验收条件

用同一组问题检查容错方案

不同机制最后都需要落实到故障模型、状态和时间约束：

TMR 的短任务优势、备用系统的覆盖率上限、NVP 的相关错误，以及进程对的提交窗口，都表明冗余的效果取决于具体机制和假设。解析模型描述预期行为，故障注入检查这些行为是否真正实现，现场数据再帮助发现遗漏的故障条件，三者共同支持容错设计