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

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

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

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

从单个指标到系统目标

可用性、性能与降级

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

Ass=MTTFMTTF+MTTRA_{ss}=\frac{\mathrm{MTTF}}{\mathrm{MTTF}+\mathrm{MTTR}}

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

Ass=μλ+μA_{ss}=\frac{\mu}{\lambda+\mu}

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

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

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

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

为可靠性付出的开销

冗余和恢复机制消耗资源。若原方案占用资源 C0C_0,新方案额外增加 CrC_r,开销率为相对于原方案的比率,可写成 Cr/C0C_r/C_0。Triple Modular Redundancy(TMR)仅计算三份执行单元时,额外开销是原方案的 200%200\%

checkpoint 则主要带来时间和 I/O 开销。若每次有效计算持续 TeT_e,保存 checkpoint 耗时 TckT_{ck},在暂不考虑故障时,每轮总耗时 Te+TckT_e+T_{ck}。相对原计算时间的增加比例为 Tck/TeT_{ck}/T_e,而总时间中用于 checkpoint 的比例为 Tck/(Te+Tck)T_{ck}/(T_e+T_{ck})

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

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

可靠性框图(Reliability Block Diagram,RBD)把服务成功表示为从入口到出口至少存在一条由正常组件组成的路径。

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

qseries=∏i=1nqi,qparallel=1−∏i=1n(1−qi)q_{\mathrm{series}}=\prod_{i=1}^{n}q_i, \qquad q_{\mathrm{parallel}}=1-\prod_{i=1}^{n}(1-q_i)

这里的 qiq_i 可以是任务期间的可靠性 Ri(t)R_i(t),也可以是某一时刻的可用性 Ai(t)A_i(t);选定后应在整张图中保持一致

桥式结构与条件分解

复杂框图未必能直接化成简单的串并联,例如下面的桥式结构

含交叉连接的桥式可靠性框图
含交叉连接的桥式可靠性框图

选择组件 BB,按它是否正常分解系统成功事件 SS:

Pr⁡(S)=Pr⁡(B)Pr⁡(S∣B)+[1−Pr⁡(B)]Pr⁡(S∣¬B)\Pr(S)=\Pr(B)\Pr(S\mid B) +\bigl[1-\Pr(B)\bigr]\Pr(S\mid\neg B)

在图中,BB 正常时可将其视为导通,得到 (A∥F)(A\parallel F)、(C∥E)(C\parallel E) 与 DD 串联;BB 失效时将其断开,得到 AEAE、FCFC 两条串联支路并联后,再与 DD 串联

这种条件分解可以反复使用,但逐个枚举所有组件状态的成本会迅速上升。RBD 适合描述静态成功路径;故障发生顺序、修复和重配置需要状态模型

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

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

单台可修复服务器

设服务器从正常到失效的速率为 λ\lambda,从失效到正常的修复速率为 μ\mu。令 pU,pDp_U,p_D 分别为稳态下正常和失效的概率。正常与失效之间的概率流量平衡,再加上概率和为 11:

pUλ=pDμ,pU+pD=1p_U\lambda=p_D\mu, \qquad p_U+p_D=1

所以

pU=μλ+μ,pD=λλ+μp_U=\frac{\mu}{\lambda+\mu}, \qquad p_D=\frac{\lambda}{\lambda+\mu}

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

三台主动/被动服务器

进一步考虑三台服务器,任一时刻最多一台处理请求,活动服务器故障后立即切换到正常的备用服务器。假设活动与备用服务器都独立地以速率 λ\lambda 失效,一名维修人员以速率 μ\mu 逐台修复。令状态 kk 表示仍有 kk 台正常服务器,服务在 k≥1k\geq1 时可用

三服务器的失效与修复状态转换
三服务器的失效与修复状态转换

图中用对应的稳态概率 pkp_k 标记各状态。向左的总失效率为 kλk\lambda,向右的修复速率为 μ\mu,相邻状态满足

pk kλ=pk−1μ,pk=(μ/λ)kk!p0p_k\,k\lambda=p_{k-1}\mu, \qquad p_k=\frac{(\mu/\lambda)^k}{k!}p_0

由 ∑k=03pk=1\sum_{k=0}^3p_k=1,得到

p0=[∑k=03(μ/λ)kk!]−1,Ass=1−p0p_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 从“怎样失败”组织模型,二者对相同静态逻辑可以得到一致的概率

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

pstop=1−(1−p1)(1−p2)(1−p3)p_{\mathrm{stop}}=1-(1-p_1)(1-p_2)(1-p_3)

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

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

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

M/M/1 的稳态分布

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

pnλ=pn+1μp_n\lambda=p_{n+1}\mu

设 ρ=λ/μ\rho=\lambda/\mu。只有 ρ<1\rho<1 时,概率才能归一化为稳态分布:

pn=(1−ρ)ρn,n=0,1,2,…p_n=(1-\rho)\rho^n, \qquad n=0,1,2,\ldots

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

E[N]=ρ1−ρ,E[W]=E[N]λ=1μ−λE[N]=\frac{\rho}{1-\rho}, \qquad E[W]=\frac{E[N]}{\lambda}=\frac{1}{\mu-\lambda}

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

SPN 与 SAN:表达并发和组合行为

Petri net 用 place 表示条件或资源,用 token 表示当前数量,用 transition 表示事件。transition 从输入 place 消耗 token,并向输出 place 放入 token;只有输入条件满足时,transition 才处于 enabled 状态。这种表示法适合描述多个事件并发发生

Stochastic Petri Net(SPN)为部分 transition 赋予随机等待时间,常见设定是指数分布。enabling 与 firing 之间的时间差可以表达请求处理、组件失效或修复;扩展形式还允许 immediate transition 和 guard。给定初始 marking 和速率后,纯指数型 SPN 的可达 marking 可映射为连续时间 Markov 链,再用数值方法求解;marking 数量也可能很大

公共队列与独立队列

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

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

Stochastic Activity Networks(SAN)进一步扩展 SPN:activity 可以有更一般的启用与完成规则、非指数等待时间、instantaneous activity,以及按概率选择不同的结果;input gate 和 output gate 可以读取或修改更复杂的状态。它能表达更丰富的系统行为,但也更依赖数值求解和离散事件仿真。对 Markov 链、SPN、SAN 都可附加 reward model,为状态或 transition 分配收益,累计有用工作、处理请求数或停机代价

如何选模型

问题 优先考虑的模型 关键假设或代价
组件怎样组合才能提供服务 RBD 静态成功路径,独立性需检查
哪些基本事件会造成顶层失效 FTA 静态逻辑,重复事件需去重
故障、修复和切换怎样随时间变化 Markov 链 状态定义清楚,等待时间满足 Markov 假设
请求拥塞、等待与利用率 排队模型 到达、服务、容量和调度假设需匹配
并发事件与共享资源 SPN 可达状态可能迅速增多
复杂 guard、概率分支与一般延迟 SAN 表达力强,通常需要数值或仿真求解

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


© 2024 本网站由 renxiaodaifu 使用 Stellar主题 创建
总访问 次 | 本页访问 次

共 12 篇博客 · 共 89 篇 wiki · 总计 32.1k 字