Lecture 26: Datacenter Disasters — 真实数据中心故障案例研究（Datacenter Disasters: Case Studies）

目录 · ← l25 · l27 →

Lecture 26: Datacenter Disasters — 真实数据中心故障案例研究（Datacenter Disasters: Case Studies）

讲义对应：CS 425 FA2026 Lecture 26。本章对应课程 Lecture 28「Datacenter Disasters」（2026-12-03，Real Behaviors 模块），原始讲义为 L28.FA25.pdf（45 页：数据中心宕机原因竞猜、人为错误案例集、四个真实事故案例（AWS 2011 / Facebook 2010 / The Planet 2008 / AWS 2025）、经验教训总结）。背景素材：Lecture 2「Introduction to Cloud Computing」（L2.FA26.pdf：数据中心三层架构、机架/交换机/可用区/区域、故障域分层、云的经济学）与 Lecture 5-6「Failure Detection and Membership」（L5-6.a.FA26.pdf：故障是常态而非例外、MTTF 随规模线性变差、Completeness 与 Accuracy 不可兼得、误判与 Suspicion 机制）。 教材对应：Coulouris 5th Ed. Ch. 1–2（分布式系统特征、挑战与体系结构模型）、Sec 2.4.2（故障模型）、Ch. 12（分布式文件系统与容错）、Ch. 18（复制与可用性）；补充：Patterson 等 Recovery-Oriented Computing (ROC)（Berkeley, 2002）、Huang 等 Gray Failure: The Achilles’ Heel of Cloud-Scale Systems（Microsoft Research, HotOS 2017）、Basiri 等 Chaos Engineering（IEEE Software 2016）。 阅读材料：讲义引用的公开事故报告 —— AWS 2011-04-21 EBS 事故 post-mortem（aws.amazon.com/message/65648/）、Facebook 2010-09-23 宕机说明（Facebook Engineering Notes）、The Planet 2008-05-31 H1 Houston 机房爆炸事故分析（Availability Digest，data_center_outages-lessons.pdf）、AWS 2025-10-19/20 事故 post-mortem（aws.amazon.com/message/101925/）。本章中所有案例事实均来自上述讲义与讲义所引材料；讲义未覆盖、但为解释原理所需的通用概念，均以「补充」明确标注。

26.1 概述

前 25 讲我们一直在回答一个问题：如何设计一个”正确的”分布式系统——用复制获得容错，用 quorum 获得一致性，用逻辑时钟获得顺序，用 2PC 获得原子性，用故障检测获得”谁还活着”的近似答案。本章掉转方向，问一个更朴素、也更残酷的问题：真实的分布式系统为什么会失效？

讲义用一组真实事故回答它：一个工程师把某个路由器的流量切到了低容量的备用网络上，最后演变成持续 3.5 天、丢失 0.07% 数据的 AWS EBS 大规模故障；一次配置值写错，让 Facebook 的缓存服务器集体去猛查数据库，把整个网站逼下线；一次变压器短路起火，让 The Planet 的 9 千台服务器在 3 天内无法恢复；2025 年 10 月，两个自动化 DNS 程序之间的一次竞态，把 dynamodb.us-east-1.amazonaws.com 的 DNS 记录写成了空，进而让 EC2 的租约系统”充血性崩溃”了一整天。讲义开篇的课堂竞猜给出了一个数字：数据中心宕机的首要原因是人为错误，约占 70%。

本讲在整门课中的位置是反向收束：前面每一讲都在建立”故障模型—机制—正确性论证”的正向链条（crash-stop、Byzantine、分区、FLP、quorum、fencing），本章则把这些抽象放回真实机房，看它们在配置错误、软件 bug、竞态、静默数据损坏、运维失误、相关性故障面前如何失效。它的结论不是”理论没用”，而恰恰相反：真实事故几乎总是”某个理论假设被悄悄违反”的结果，而理解了假设，才能在事故报告的细节里看见根因。

本章的黄金法则（贯穿全章，并在 26.6 再次点题）：

真实系统的问题几乎从不是”崩溃”，而是”变慢”、”部分失败”和”配置错误”。所以设计的重点不是让系统永不故障，而是让故障的影响可隔离、可快速恢复、可被观测到——减少 MTTR 比增加 MTTF 更有效，而控制爆炸半径比重试更有效。

26.2 核心概念与分布式机制图解

26.2.1 为什么要研究真实故障（Why Study Outages）

• 定义与目的：事故复盘（postmortem / incident review）是对一次真实故障的系统性事后分析：时间线、影响面、根因、促成因素、以及防止复发的行动项。研究故障的目的不是追责，而是从真实系统中提取”设计假设在哪一环被打破”的知识，进而改进设计。

• 直观解释（”它是什么？”）：讲义把研究宕机的理由说得很直白——既”有趣”（幸灾乐祸式的围观），也真的有用：它让我们了解系统在真实世界里的实际行为，从而在未来设计出更好的系统。讲义特别强调两点态度：第一，目的不是评判哪家公司更差；事实上，经历过宕机的公司之后往往会建设出更稳健的基础设施——”杀不死你的会让你更强”（”What doesn’t kill you makes you stronger”，讲义引 Calvin 的爸爸的话：”It builds character”）。第二，宕机是不可避免的，因此值得研究的不是”如何不发生”，而是”发生后如何更快恢复、更少波及”。

• 核心论点（必须讲透）：

  1. 理论上的故障模型是抽象，真实故障往往是这些模型的错误组合。讲义中的四次事故没有一次是干净的 crash-stop：AWS 2011 里既有网络分区（primary 网络断开、secondary 网络被压垮）又有人为误操作又有竞态条件；Facebook 2010 里是配置错误 + 重试风暴；The Planet 2008 里是物理事故 + 电源/冷却容量不足；AWS 2025 里是并发控制缺失导致的元数据覆盖。真实故障是”分布式系统课程里所有故障类型的叠加态”。

  2. “理论上正确”不等于”实践中可靠”。任何正确性证明都建立在一组假设上：故障检测器不误判、时钟足够同步、消息不会损坏、代码没有 bug、配置是对的、没有人在凌晨三点敲错命令。这些假设在真实环境里迟早会被违反——而且违反的方式往往不在模型之内（配置错误、静默数据损坏、运维失误都属于”抽象之外的故障”）。Lecture 5-6 已经证明：在丢失消息的网络上，故障检测器的 Completeness（不漏报）与 Accuracy（不误报）不可兼得；一旦承认误判，凡是依赖”故障检测结果”的决策（切主、摘除节点、触发重平衡）就都可能做错。

  3. 故障是常态而非例外。Lecture 5-6 给出了数量级：若一台机器的故障率是平均 10 年一次（120 个月），那么 120 台服务器的数据中心里”下一台机器故障”的平均间隔就降到 1 个月，12000 台时降到 约 7.2 小时——而且软故障（soft crash / 性能退化）比硬故障更频繁。Lecture 2 又告诉我们，现代云是商品化硬件 + 大规模 + 按需租用的组合。二者相乘的结论只有一个：容错不是可选的加分项，而是设计的基本要求。

• 机制图解：从”抽象故障模型”到”真实故障”的落差。

   课程前 25 讲的故障模型                真实数据中心里实际发生的事
   ─────────────────────────            ──────────────────────────────────────
   crash-stop(进程干净地停)      <--    进程还活着, 但心跳还在、吞吐掉到 1/10  (灰色故障)
   Byzantine(任意错误行为)       <--    不是恶意, 而是"磁盘说写成功但数据是坏的"(静默损坏)
   network partition(网络分区)   <--    分区 + 非对称 + 抖动 + DNS 解析失败 + 健康检查抖动
   fail-recover(崩溃后可恢复)    <--    重启后缓存/配置/时钟/租约全都处于不一致状态
   独立故障假设(副本互不影响)    <--    同机架/同交换机/同电源/同版本/同配置 ==> 相关性故障
   无 bug 的代码                <--    只在"高并发 + 高负载"下才触发的竞态(AWS 2011 / 2025)
   正确的配置                   <--    配置文件写错一个值(Facebook 2010 / 1300 万德国网站)

• 关键假设与系统模型：本讲隐含的系统模型比前面任何一讲都”更弱”：故障可以是部分失败（partial failure）、间歇性（intermittent）、有相关性（correlated）的；系统管理员、自动化程序（agent/Enactor）、第三方依赖（DNS、认证、云 API）都是系统的一部分——它们也会失效。把这一条写进设计里，就是本章后半部分所有工程实践（ROC、混沌工程、渐进式发布、熔断、舱壁、可观测性）的共同出发点。

26.2.2 真实故障的分类学（A Taxonomy of Real-World Failures）

• 定义与目的：把真实故障按来源组件分类，是为了给每一类故障配上对应的检测手段与防护机制。讲义自身没有给出一张完整的分类表（它用案例来展示），下面这张分类树是把讲义四个案例、人为错误案例集与讲义”其他故障来源”（DoS、互联网中断、计划内停机）系统化整理的结果，并用【补充】标出课程外但必要的通用概念。

• 机制图解：故障分类树。

                                真实数据中心的故障
                                       |
   +-----------+-----------+-----------+-----------+-----------+-----------+
   |           |           |           |           |           |           |
 硬件        网络        软件       人为/运维    容量/负载     安全        依赖
   |           |           |           |           |           |           |
   |           |           |           |           |           |           |
 磁盘故障    链路中断    代码 bug    误删/误配   容量规划不足  DoS/DDoS    DNS
 静默损坏    网络分区    (边界/竞态) (讲义案例集) 热点/倾斜    内部威胁    认证服务
 内存位翻转  非对称分区  配置错误    流程缺陷    惊群/突增    供应链      云厂商 API
 CPU/网卡    丢包/乱序   版本回归    变更管理缺失 负载重分配   勒索/入侵   CDN
 电源故障    抖动/jitter 内存泄漏    监控盲区     次生过载                第三方 SaaS
 冷却故障    DNS 故障    死锁/活锁
 机架/机柜   BGP 泄露    重试风暴
 U PS/电池   路由劫持    级联失败
 火灾/水浸               控制面故障
                         (元数据/租约)
   |           |           |           |           |           |           |
   +-----------+-----------+-----------+-----------+-----------+-----------+
                                       |
                              共同的放大器: 相关性 + 重试 + 自动化 + 缺乏超时

• 分类要点与应对（每一类给出特征、真实例证与防护重点）：

• 【补充】静默数据损坏（Silent Data Corruption）：最阴险的一类硬件/软件故障——磁盘报告”写成功”，但读回来的数据是错的；内存的位翻转（bit rot、宇宙射线、Rowhammer）也会让校验逻辑或元数据悄悄变错。讲义本章未展开，Lecture 22 的分布式文件系统（GFS 等）正是用 chunk 级 checksum + 端到端校验 来对抗它：写入时算校验和，读取时验证，发现不一致就用其他副本修复；校验必须端到端（从客户端到磁盘），否则中间的任何一跳都可能悄悄改坏数据而无人发现。这是”崩溃可检测、损坏不可检测”的典型对照。

26.2.3 失效模式（Failure Modes）：从”崩溃”到”灰色故障”

• 定义与目的：把故障按表现形式（而不是按来源）分类，才能设计出正确的检测策略。关键认识是：越”干净”的故障越好处理，而真实世界的故障恰恰越来越”脏”。

• 对比表（必须掌握）：

• 灰色故障（Gray Failure）——必须讲透的一类【补充：概念来自 Microsoft Research 的 Gray Failure，讲义用”亚马逊控制面线程池被慢操作占满”“EC2 API 错误率与延迟升高”等现象印证了同类问题】：
  • 定义与目的：灰色故障指组件既不算”活着”也不算”死了”的状态：它能接受连接、能回心跳、CPU/内存指标都正常，但对一部分客户端表现为持续失败或极慢。它介于 crash（全黑）与健康（全白）之间的”灰色地带”。
  • 直观解释（”它是什么？”）：把它想成一个说话很清楚、但只会回答一部分问题的客服。电话永远能打通（心跳正常），但有的顾客等 30 秒得到答案，有的顾客永远被转接。监控室看到的是”在线率 100%”，顾客感受到的是”根本不能用”。
  • 三个致命性质：
    1. 相对性（relativity）：同一台服务器对不同客户端可能分别是”故障”和”正常”——因为故障藏在某条链路、某个交换机、某个副本对上（网络抖动、单条链路丢包、只对某些分片失败的磁盘）。讲义中 AWS 2011 的”多个 EBS primary 副本认为自己没有 backup”、AWS 2025 的”健康检查结果在 failed/healthy 之间来回翻转”都是这种相对性的体现。
    2. 难以检测（undetectability from inside）：服务器自己的指标（CPU、内存、进程存活、心跳）都正常，只有从客户端视角测量才看得见。这正是 AWS 2025 中 NLB 健康检查”翻转”却无法给出稳定判断的原因。
    3. 引发错误决策：由于故障检测器不认为它故障，流量会继续打到它身上——慢请求占住调用方的线程/连接，最终把调用方也拖垮（级联退化）。Lecture 5-6 里 gossip 故障检测的 Suspicion 机制（先”疑似”再”判死”）正是为了缓解”误判/漏判”的两难，但灰色故障连”疑似”都很难触发。
  • 机制图解：服务器视角 vs 客户端视角。

       服务器自己的视角 (What the server sees)          客户端视角 (What clients see)
   ┌──────────────────────────────────────────┐   ┌──────────────────────────────────┐
   │  进程存活        : OK                    │   │  客户端 A: 120 ms   (正常)        │
   │  心跳            : 每 100 ms 一次  OK    │   │  客户端 B: 3.2 s    (超时重试中)  │
   │  CPU / 内存      : 41% / 55%     OK      │   │  客户端 C: 8.0 s    (超时)        │
   │  自测健康检查    : PASS (端口能连)       │   │  客户端 D: 200 ms   (正常)        │
   │  "我很好"                                 │   │  客户端 E: 9.5 s    (超时)        │
   └──────────────────────────────────────────┘   └──────────────────────────────────┘
              |                                                  |
              |  监控面板上 "一切正常"                           |  真实的 p99 已经爆炸
              v                                                  v
   ┌───────────────────────────────────────────────────────────────────────────────┐
   │  后果: 负载均衡继续把流量打给这台机器 -> 慢请求占满调用方线程池 -> 级联失败   │
   │  对策: (1) 从客户端视角定义 SLI  (2) 跨层关联指标  (3) 主动合成探测/canary    │
   │        (4) 端到端延迟直方图(而不是平均值)  (5) 快速失败 + 熔断 + 舱壁          │
   └───────────────────────────────────────────────────────────────────────────────┘

• 检测手段【补充】：（a）从客户端视角测量——把 SLI 定义在”调用方看到的成功率/延迟”上，而不是被调用方自己报的健康度；（b）跨层关联——把网关、服务、数据库、网络的指标放在同一条时间轴上对齐，寻找”某一跳的延迟注入”；（c）主动探测（synthetic probe / canary request）——用真实业务路径的合成请求持续探测，而不是只探 TCP 端口；（d）慢请求采样与追踪——用分布式追踪记录每个慢请求卡在哪一跳。

26.2.4 相关性故障与故障域（Correlated Failure and Fault Domains）

• 定义与目的：相关性故障指多个”本应独立”的副本因同一根因同时失效；故障域（fault domain）指”会一起失效的一组组件”（同一机架、同一交换机、同一电源域、同一可用区、同一软件版本、同一次配置推送）。冗余的有效性完全取决于副本是否真的落在不同的故障域里。

• 直观解释（”它是什么？”）：Lecture 2 讲过数据中心的物理层次：服务器 → 机架 → 数据中心 → 可用区（AZ） → 区域（Region） → 全局，而且讲义明确指出”AZ 被设计为彼此独立的故障域“。相关性故障就是”你以为买了 3 份保险，其实 3 份保单是同一家保险公司开的、而且它们在同一次灾难里一起赔付”。

• 机制图解：同一批副本，三种放置方式，三种爆炸半径。

   场景 1: 3 副本塞在同一机架 (常见错误: 按"最小化网络跳数"或按编号贪心放置)
   ┌──────────────── 机架 R1 ────────────────┐  ┌──── 机架 R2 ────┐  ┌── R3 ──┐
   │   [副本 A]   [副本 B]   [副本 C]        │  │   (空)          │  │  (空)  │
   └─────────────────────────────────────────┘  └─────────────────┘  └────────┘
   一次机架断电/交换机重启  ==>  3/3 副本全丢  ==>  数据永久丢失 (爆炸半径 = 100%)

   场景 2: 3 副本跨机架, 但同一个可用区 (AZ-aware 缺失)
   ┌─────────────────────────── 可用区 us-east-1a ───────────────────────────┐
   │  ┌── R1 ──┐        ┌── R2 ──┐        ┌── R3 ──┐                          │
   │  │ [副本A]│        │ [副本B]│        │ [副本C]│                          │
   │  └────────┘        └────────┘        └────────┘                          │
   └──────────────────────────────────────────────────────────────────────────┘
   单机架故障 ==> 只丢 1/3 (仍有多数派, 可用)      ✅
   单可用区故障 ==> 3/3 全丢 ==> 数据永久丢失      ❌ (爆炸半径 = 整个 AZ)

   场景 3: 3 副本跨可用区 (正确的故障域隔离)
   ┌── AZ 1a ──┐        ┌── AZ 1b ──┐        ┌── AZ 1c ──┐
   │ [副本 A]  │        │ [副本 B]  │        │ [副本 C]  │
   └───────────┘        └───────────┘        └───────────┘
   单机架故障 ==> 丢 0~1/3     ✅        单可用区故障 ==> 只丢 1/3, 仍有多数派  ✅

   ┌───────────────────────────────────────────────────────────────────────────┐
   │ 相关性故障(同一软件版本 / 同一次配置推送 / 同一时间触发的定时任务 / 闰秒): │
   │   3 个副本, 3 个可用区, 3 套硬件 —— 全部同时失效。                        │
   │   ==> 任何"放置策略"都救不了, 唯一缓解是"多样化(diversity)"。             │
   └───────────────────────────────────────────────────────────────────────────┘

• 破除独立性假设的后果与防御：
  1. “有 3 个副本所以可靠”是幻觉：可靠性公式 $P(\text{全部故障}) = \prod_i P_i$ 只在”故障独立”时成立；一旦相关，乘积退化成一个共同故障概率。讲义里 AWS 2011 的 EBS 副本”每个卷有一个 primary 副本，若失步或节点故障就激进地重镜像“，在分区之后集体触发重镜像——这就是行为层面的相关性（同一个触发器 + 同一段代码 + 同一种策略 = 同时动作）。
  2. 防御手段：故障域隔离（跨机架/跨 AZ/跨区域）、反亲和性约束（anti-affinity）、多样化（版本、实现、供应商、网络路径异构）、渐进式发布（不让一个坏版本同时上所有副本）、抖动（jitter）（不让所有定时任务在同一毫秒触发）、重平衡退避。
  3. 代价：跨 AZ 复制带来更高的写延迟与跨区流量成本（Lecture 2 的云经济学：跨区数据传输是要付费的）；多样化带来运维复杂度。这是”可靠性 vs 成本/复杂度”的经典权衡——26.5 会给出定量分析。

26.2.5 失败放大（Failure Amplification）：小故障如何变成大事故

• 定义与目的：失败放大指系统自身的容错/运维机制（重试、心跳、重平衡、冷启动、缓存刷新）在故障发生时反过来增加负载，把一个”部分降级”放大成”全线崩溃”。讲义反复出现的”Cascading failures（级联失败）“、”重镜像风暴（re-mirroring storm）“、”数据库被每秒十万级查询压垮“、”重试没有退避（No back off）导致 rinse-n-repeat”都是失败放大。

• 直观解释（”它是什么？”）：超市收银台的类比——平时 5 个收银台开 2 个也够用。某个收银员动作变慢（灰色故障），他后面的队伍开始变长，长队伍堵住了通道，于是想去其他收银台的顾客也走不过去了，最后整个超市结账区瘫痪。如果此时经理的处理方式是”让每个顾客都去所有队伍各排一次”（重试），超市会彻底瘫痪。

• 机制图解：级联失败的时间线（本章最重要的图）。

 t = 0 ms    ┌────────────────────────────────────────────────────────────────┐
             │ 触发: db 变慢 (p99 10ms -> 200ms); 容量 1000/s -> 50/s          │
             └────────────────────────────────────────────────────────────────┘
                 |
 t ≈ +50 ms      v   调用方开始"等连接": 每个请求同步阻塞, 直到拿到 DB 连接
             ┌────────────────────────────────────────────────────────────────┐
             │ db 连接池(10 个) 全部被占用; 等待队列开始堆积: 10 -> 30 -> 50  │
             └────────────────────────────────────────────────────────────────┘
                 |
 t ≈ +250 ms     v   ★ 关键一步: 等连接的请求"占着"它的 svc 工作线程不放
             ┌────────────────────────────────────────────────────────────────┐
             │ svc 线程池(60 个) 被"正在等 db"的请求占满 -> 100% 占用          │
             │ 后果: 与 db 无关的健康请求(aux)也拿不到线程 —— 横向扩散         │
             └────────────────────────────────────────────────────────────────┘
                 |
 t ≈ +1 s        v   上游继续等: api 处理线程(120 个) 也被占满
             ┌────────────────────────────────────────────────────────────────┐
             │ api 池 100% 占用 -> 新请求只能在入口排队(积压 1 万级)          │
             │ 客户端开始超时 -> 用户看到大面积失败                            │
             └────────────────────────────────────────────────────────────────┘
                 |
 t ≈ +3~5 s      v   放大阶段: 客户端/网关重试 + 健康检查摘除 + 负载重分配
             ┌────────────────────────────────────────────────────────────────┐
             │ (a) 无退避重试: 入口负载 x2~x4, 下游调用放大 4 倍               │
             │ (b) 健康检查失败 -> 把实例从 LB 摘掉 -> 幸存者承受全部流量      │
             │ (c) 分区/失联的副本集体"激进重镜像" -> 重镜像风暴(占满网络)     │
             │ (d) 冷启动风暴: 大量实例同时重启, 同时抢配置/缓存/连接          │
             └────────────────────────────────────────────────────────────────┘
                 |
 t ≈ 分钟级      v   稳态灾难: 成功率跌到个位数, 延迟无界增长, 恢复依赖人工介入
             ┌────────────────────────────────────────────────────────────────┐
             │ 注意尺度: 从"一个依赖慢了 20 倍"到"全线不可用"只用了秒级时间。   │
             │ ==> 人工响应根本来不及, 必须靠自动化(超时/熔断/限流/丢弃)。      │
             └────────────────────────────────────────────────────────────────┘

• 重试放大的数学（讲义在 Facebook 案例里称之为”没有退避的重试、rinse-n-repeat”，并在经验教训中给出 Exponential backoff 作为解法）：

  情形 1: 客户端每个请求重试 r 次(失败就立刻重试)  ==> 下游负载放大 (1 + r) 倍
          1 个用户请求 ──> [尝试1]──失败──>[尝试2]──失败──>[尝试3]──失败──>[尝试4]
          下游看到的调用:  1         + 1        + 1        + 1       = 4 倍 (r = 3)

  情形 2: 每一层都重试 r 次 (L 层调用链)          ==> 放大 (1 + r)^L 倍
          L = 3 层, r = 3:  4 x 4 x 4 = 64 倍
          ┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
   用户 ──>│  网关    │──>│  服务    │──>│  存储    │──>│  数据库  │   64x 到达最底层
          └──────────┘   └──────────┘   └──────────┘   └──────────┘
               4x             4x             4x           (最脆弱的一环)

  情形 3: 无抖动 + 同步超时 ==> 惊群(thundering herd)
          所有客户端在同一时刻超时 ==> 所有客户端在同一时刻重试
          时间轴:  |---- 超时 1s ----|######## 重试洪峰 ########|---- 超时 ----|####...
          有抖动:  |---- 超时 1s ----|# #  #   #    #  #   #  # |--- 超时 ---|# # #
                   (重试被均匀打散, 峰值负载下降 ~ sqrt(客户端数) 量级)

  自我强化的循环:  下游变慢 -> 调用方超时 -> 调用方重试 -> 下游更慢 -> 更多超时
                  ==> 这就是讲义中 "rinse-n-repeat" 的机理

• 关键假设与系统模型：失败放大的前提是”系统有能力接收这些额外负载“。真正的危险在于：故障时刻系统的可用容量通常已经在下降（慢依赖占住了线程、重平衡占住了网络、重启中的节点不服务流量）。因此”重试”在容量充足时是提高成功率的手段，在容量不足时就变成分布式拒绝服务攻击（自己打自己）。这正是 26.2.15 里”重试必须有界 + 退避 + 抖动 + 预算”的原因。

26.2.6 关键指标：MTTF / MTTR / RPO / RTO / SLA / 爆炸半径

• 定义与目的：事故复盘与可靠性设计都需要一套可量化的语言。下面这张术语表是全章的度量基础，也是 26.3.6 定量论证的出发点。

• “几个 9”的直观换算表（按一年 8760 小时 / 一个月 730 小时计）：

要点：从三个 9 到五个 9，停机时间要缩小 100 倍（8.76 小时 → 5.26 分钟）。这 100 倍要么来自 MTTF 提高 100 倍，要么来自 MTTR 缩小 100 倍——26.3.6 会证明这两条路在数学上完全等价，而在工程上极不对称。

• 机制图解：可用性 $A=\frac{\text{MTTF}}{\text{MTTF}+\text{MTTR}}$ 的两条改进路径（纵轴为”9 的个数”，横轴为改进倍数 $k$）。

   9 的个数
     6 |                                        .......=============== 提高 MTTF k 倍(path B)
     5 |                            ....=======                       降低 MTTR k 倍(path A)
     4 |                  ....======
     3 |          ....====
     2 |....======
     1 |
       +------+------+------+------+------+------+------+------+----> 改进倍数 k
              2x     4x     8x    16x    32x    64x   128x   256x
   两条曲线完全重合(A = 1/(1 + MTTR/MTTF) 只取决于比值) ——
   但现实中: MTTF 受物理与规模限制(规模 x10 ==> 系统 MTTF /10),
             而 MTTR 是"设计变量": 自动切换、快速重启、可回滚变更、限流熔断。

• 关键假设与系统模型：这套指标隐含”服务是稳态的“假设——MTTF/MTTR 用长期均值刻画系统。真实事故往往是非稳态的（故障期间系统行为与平时完全不同，重试、重平衡、冷启动使系统进入另一种工作点），因此平均可用性 99.99% 与”某一次事故连续不可用 8 小时”完全可以并存：前者是统计意义上的，后者是用户真正记住的。讲义的 The Planet 案例就是典型：年度可用性数字可能还”过得去”，但一次 3 天的不可用足以让 7500 家企业客户流失。

26.2.7 案例一：AWS 2011-04-21 EBS/EC2 大规模故障（讲义案例 I）

（1）发生了什么（依据讲义与 AWS 事后报告）

• 事故发生在 2011 年 4 月 21 日，AWS 事后发布了 post-mortem；受影响的不只是 AWS 自己：Reddit、FourSquare 等大量使用 EC2 的公司同时下线，AWS 的状态面板显示 EC2 与其他存储服务异常。事故至少持续 3.5 天，并造成部分数据丢失。
• 背景（讲义给出的系统结构）：AWS 的 Region（区域） 是彼此独立的数据中心（如 us-east-1、us-west-1），每个 Region 由若干 可用区（AZ） 组成，同一 Region 内可以自动跨 AZ 复制数据——但并非所有客户都这么做。EBS（Elastic Block Storage）是挂载给 EC2 实例的存储卷；一个 EBS 卷运行在某个 AZ 内部；EBS 有两套网络：primary 网络承载 EC2 与 EBS 控制面流量，secondary 网络用于溢出，容量更低；控制信息跨 AZ 复制以保证可用性；每个卷有一个 primary 副本，若副本失步或节点故障，副本被设计为激进地重镜像（aggressive re-mirroring）数据。
• 时间线（讲义口径）：
  • 12:47 AM：US East 某 AZ 进行例行的 primary 网络容量升级，把若干 primary 路由器的流量切到其他 primary 路由器。关键错误：有人把其中一个路由器的流量切到了 secondary 网络的路由器上。 结果：多个 EBS 卷失去了可用的 primary 网络——primary 网络断开，而 secondary 网络容量低、瞬间被压垮；许多 primary 副本因此没有可用的备份。
  • 团队发现该错误并回滚。但由于网络分区，许多 primary 副本仍”认为自己没有 backup”，于是自动开始激进地重镜像：所有卷同时行动，空闲网络容量被瞬间用尽，副本陷入循环——重镜像风暴，波及 13% 的 EBS 卷。
  • 控制面（Control Plane）网络不可用：无法响应 EBS 的”创建卷（create volume）”API 请求；控制面操作的超时时间很长，请求开始积压；当线程池被填满后，控制面开始拒绝创建卷的请求。
  • 2:40 AM：团队禁用所有新的”创建卷”API 请求；2:50 AM：EBS API 的错误率与延迟开始恢复。
  • 但有两个因素让情况更糟：（a）寻找潜在副本的 primary 副本不做退避（did not back off）；（b）EBS 代码中存在一个竞态条件，只有高请求率才能触发——此时被触发了，导致更多节点失败。
  • 5:30 AM：错误率与延迟再次上升。重镜像本质上是 EC2 节点、EBS 节点与 EBS 控制面之间的协商（目的是保证”只有一个 primary”）；由于竞态条件，EBS 节点开始失败，协商速率上升，进而导致更多节点失败——如此循环，EBS API 功能进入“半死（brown-out）”状态。
  • 8:20 AM：团队开始切断受影响 AZ 内 EBS 集群与 EBS 控制面之间的所有通信；该 AZ 仍然不可用，但控制面开始缓慢恢复。
  • 11:30 AM：团队找到阻止该 AZ 内 EBS 服务器做无效重镜像的方法，受影响 AZ 开始缓慢恢复。
  • 客户直到中午仍在遭遇”新建 EBS 支撑的 EC2 实例”高错误率——因为另一个新上线的 EBS 控制面 API（用于把新 EC2 实例挂载到卷）的错误率被新错误”掩盖”了。中午：不再有新的卷卡住；但13% 的卷仍处于卡死状态。
  • 恢复的长尾：到 4 月 24 日中午，除 1.04% 之外的卷全部恢复；最终有 0.07% 的卷永远无法恢复、数据永久丢失。这次故障还影响了单 AZ 部署的 RDS（关系数据库服务）。

（2）根因分析

（3）它违反了哪个理论假设

• “分区是良性的”：分区不仅让节点无法通信，还让节点基于不完整信息自主做出激进决策（重镜像）。理论模型中分区只影响可用性；这里分区改变了系统的行为，产生了新的负载。
• “副本故障是独立的”：13% 的卷同时进入重镜像，是共同的触发器 + 共同的策略造成的相关性故障。
• “故障检测是准确的”（Lecture 5-6）：副本把”联系不上”解释为”对方没有备份”，即误判（false positive），并据此采取了破坏性动作。Completeness 得到了保证，Accuracy 被牺牲，代价是数据重镜像。
• “超时只是延迟问题”：控制面长超时把”慢”变成了”资源耗尽”（线程池被占满），直接导致拒绝服务——这正是 26.1 黄金法则里”问题往往不是崩溃而是变慢”的教科书例子。讲义在具体教训里明确写了”控制面操作超时很长，开始积压，线程池填满后开始拒绝请求“。

（4）暴露了哪些设计缺陷

1. 没有变更护栏（guardrail）：允许把生产流量切到容量低一个数量级的网络路径上，且没有自动化校验。
2. 重平衡/重镜像没有退避与限速：讲义的具体教训是”防止重镜像风暴：退避而不是激进重试“。
3. 没有隔离控制面与数据面：控制面线程池被慢操作占满后，连”创建卷”这种基本操作都无法服务；最终只能靠物理切断 AZ 与控制面的通信（8:20 AM）来止血——这说明系统缺少优雅降级开关。
4. 高负载路径上的竞态未被测试：竞态”只在高请求率下触发”，而日常测试从未跑到那个负载。
5. 恢复缺少长尾处理：13% 卡死的卷、最终 0.07% 永久丢失，说明数据修复路径（重建副本）本身也依赖已经受损的机制。

（5）教训与防御措施（讲义列出的具体改进）

• 审计网络配置变更流程，为升级制定一步步的协议（step-by-step protocol）。
• 提高 secondary 网络的容量。
• 防止重镜像风暴：退避（backing off）而不是激进重试。
• 修复竞态条件。
• 使用了多 AZ 的客户不受影响（讲义原话：把代码写成利用同一 Region 内多个 AZ 的客户没有受影响）——这是”故障域隔离有效”的正面证据。
• 更好的沟通工具与健康状态面板、给客户多日服务抵扣。

（6）从分布式系统原理角度应该如何防范

26.2.8 案例二：Facebook 2010-09-23 全站宕机（讲义案例 II）

（1）发生了什么（依据讲义与 Facebook 事后说明）

• 事故发生在 2010 年 9 月 23 日，Facebook 不可访问 2.5 小时（讲义称这是”过去 4 年最严重的一次”），Facebook 发布了 post-mortem。
• 背景：数据存在持久化存储（persistent store）与缓存（cache）中；持久化存储是很多台服务器，缓存是很多台服务器上运行的分布式缓存系统；缓存里也包含配置数据（configuration data）。Facebook 有一套自动化系统用于校验缓存中的配置值，并用存储中的新值替换无效值。
• 时间线：
  • 9 月 23 日，Facebook 对持久化副本中的某个配置做了一次修改——这个修改是无效的（invalid）。
  • 所有客户端（Facebook 的缓存服务器）都看到了这个无效值，于是全部尝试修复它，全部去查询数据库集群——数据库很快被每秒十万级的查询压垮。
  • 团队修复了那个无效配置。（但——”结束了吗？”）
  • 当客户端从数据库收到错误时，它把错误也解释为”值无效”，于是删掉缓存条目；数据库无法响应时，客户端制造更多查询；没有退避（No back off）；如此反复循环（rinse-n-repeat）——即级联失败。
  • Facebook 的解法：关掉整个 Facebook 网站，切断所有到数据库集群的流量，数据库恢复；然后缓慢地允许用户回来（让客户端慢慢重建缓存）；直到当天更晚整个站点才完全恢复。

（2）根因分析

• 直接根因：一次配置变更写入了无效值，而所有缓存客户端都被设计成”发现无效值就自动去源头修复”。这是一个”好的设计“（自愈）与”错误的触发条件“（配置错误）相乘的经典事故。
• 放大机制（三条）：
  1. 惊群（thundering herd）：所有客户端同时发现同一个无效值，同时去查数据库——负载从 0 瞬间变成每秒十万级。
  2. 语义混用：客户端把”数据库返回错误”也当成”缓存值无效”，于是继续删除缓存条目并继续查询——错误处理逻辑本身制造了更多负载。
  3. 无退避重试：讲义明确指出”没有退避”，形成”查询失败 → 再查询 → 更失败”的正反馈。
• 止血手段：牺牲可用性换取恢复——关站、切断数据库流量、再缓慢放量。这是 ROC 思想（先恢复、再优化）在极端场景下的应用：在”彻底不可用”与”部分可用但永远无法恢复”之间，Facebook 选择了前者。

（3）它违反了哪个理论假设

• “配置是正确的”：所有正确性证明、所有复制协议、所有一致性模型都假定输入是合法的。配置是系统的一部分，但通常没人给它做形式化验证——本章讲义把配置错误当作真实故障的头号来源之一。
• “客户端彼此独立”：所有客户端共享同一份配置、执行同一段代码、在同一时刻被触发 ⇒ 完美的相关性与同步性，等价于一次针对自己数据库的分布式拒绝服务。
• “错误处理是安全的”：客户端的降级/修复逻辑（删缓存 + 重查）在故障时变成负载放大器。理论上的”重试”是提高成功率的手段；这里它成了故障的燃料。
• “缓存能挡住后端压力”：缓存确实挡住了正常流量，但缓存失效时的”缓存击穿”把全部压力一次性导入后端（惊群）。

（4）暴露了哪些设计缺陷

1. 配置变更没有校验与灰度：一个无效值被写入持久化副本，没有”先小范围验证再全量”的流程。
2. “自动修复”缺少协调：所有客户端各自独立地做”修复”，没有协调机制（应由少数节点修复、其余节点退避等待）。
3. 失败处理没有退避、没有上限、没有熔断：把下游错误当作”可以继续猛打”的信号。
4. 配置与服务共用同一套依赖：修复配置需要访问数据库，而数据库又被这股修复流量压垮——用故障中的资源去修复故障。
5. 缺少全局开关：最终只能靠”关掉整个站点”这种最粗的开关来止血。

（5）教训与防御措施（讲义明确给出）

• 新的配置系统设计（Facebook 重做了配置系统）。
• 当无法访问资源时：不要激进重试，而要退避——”每次请求失败，就等待上一次的两倍时间“，这就是指数退避（Exponential Backoff）。
• 讲义特别提到：指数退避在 802.11 等网络协议中就被用来避免拥塞——即”这是分布式系统的通用手法，不是某个公司的技巧”。

（6）从分布式系统原理角度应该如何防范

26.2.9 案例三：The Planet 2008-05-31 H1 Houston 机房爆炸（讲义案例 III）

（1）发生了什么（依据讲义与 Availability Digest 分析）

• 事故发生在 2008 年 5 月 31 日。The Planet 是当时第四大网络托管公司，支持 2.2 万个网站，拥有 6 个数据中心（休斯顿 2 个、达拉斯 4 个）。这次事故打掉 9000 台服务器、影响 7500 家企业。
• 时间线：
  • 5:55 PM：休斯顿 H1 机房发生爆炸——变压器短路起火，进而引燃 UPS 备用电池组、喷出电池酸雾并发生爆炸（讲义标注：级联失败），炸穿了第一层的三面墙。
  • 没有任何服务器被损坏，但 9000 台服务器被停机。消防部门疏散大楼，并禁止开启备用发电机（出于消防风险）；由于存在火灾危险，工作人员直到晚上 10 点才被允许进入。
  • 据报道，The Planet 的员工不得不用皮卡把一些关键服务器物理搬运到其他机房——但又受限于其他机房的电力和冷却能力。
  • 6 月 2 日下午 5 点：二层恢复供电；6 月 4 日：一层的服务器逐个机架恢复。整个过程中，The Planet 每 15 分钟到 1 小时向客户通报进展。

（2）根因分析

• 物理层根因：变压器短路引发火灾，UPS 电池的化学物质参与二次爆炸——供电系统的单点故障演变成了物理灾难。
• 放大因素（关键，且不是软件问题）：
  1. 消防处置与设备恢复相冲突：断电是为了消防，但也意味着备用发电机不能启动，冗余电力路径被”安全流程”切断。
  2. 人员无法进场：从 5:55 PM 到 22:00 的物理不可达，使 MTTR 直接以小时计——这是 MTTR 中”检测之外的物理时间“的极端例子。
  3. 容量受限的异地接管：把服务器搬到其他机房是正确思路，但其他机房的电力与冷却余量不足——即”业务连续性计划”缺少容量验证（这正是讲义”总体教训”中说的：测试很重要——American Eagle 在灾难中才发现无法切换到备份机房）。
  4. 同一园区的两个休斯顿机房：从故障域角度看，同一城市、可能同一电力/网络入口的两个机房未必是独立故障域。

（3）它违反了哪个理论假设

• “副本/备份是安全的”：如果备份机房在同一电力域、同一城市、或容量不足以接管，那么”冗余”只是账面上的。
• “故障检测 + 自动切换就能恢复”：当故障是物理的、需要人进现场的，任何自动化都无济于事——MTTR 的下界由物理过程决定（消防、冷却、供电恢复、逐机架上电）。
• “故障域 = 网络拓扑”：真实故障域还包括电力、冷却、消防分区、人员可达性、供应商——比机架/AZ 的抽象更宽。

（4）暴露了哪些设计缺陷

1. 单一供应商边界内做冗余：讲义的经验教训直接点出：数据与服务应当跨数据中心备份，甚至跨不同提供商；但接着问了两个尖锐的问题：“业务连续性计划（Business Continuity Plans）”是谁的责任？是提供商还是客户？ 讲义承认对客户而言更难，因为要额外工作、并且存在跨提供商的数据锁定（data lock-in）问题——并提到 “Sky Computing”（UC Berkeley） 作为可能的解法方向。
2. 成本与保险的类比：讲义指出这类跨机房/跨提供商冗余会让客户花更多钱，并类比为保险费（insurance premiums）——可靠性是要付费购买的。
3. 容量余量未验证：接管机房的电力/冷却不足，等同于”备份存在但无法挂载”。

（5）教训与防御措施

• 把备份与业务连续性计划当作可测试的对象：定期做真实切换演练（讲义：American Eagle 在灾难中才发现无法切换到备份机房；”测试很重要“）。
• 明确责任边界：提供商保证什么（机房、电力、网络）、客户保证什么（跨机房/跨提供商复制、RTO/RPO 目标），并写进合同与 SLA。
• 容量预留：为接管场景预留电力/冷却/机架空间，而不是”先到先得”。
• 沟通即产品：The Planet 每 15–60 分钟更新进展保住了客户信任——讲义在多处强调”频繁更新 + 事后公开 post-mortem + 补偿”能增强客户信心。

（6）从分布式系统原理角度应该如何防范

26.2.10 案例四：AWS 2025-10-19/20 DNS 空记录与 EC2 租约雪崩（讲义案例 IV）

这是讲义中最新、也是与”元数据/控制面故障”最贴近的案例，它的根因只有一页，但后果横跨 DynamoDB、EC2、网络与负载均衡。

（1）发生了什么（依据讲义与 AWS 事后报告）

• 事故发生在 2025 年 10 月 19–20 日，大量 AWS 服务受影响：Netflix、Starbucks、United Airlines 下线，某些”智能床”夜里无法工作，Coursera 与 Piazza 也下线。AWS 发布了 post-mortem 与防止复发的措施。
• 背景：DNS 是服务的”目录”（把名字解析到端点/文件等）；DynamoDB 是 AWS 的 NoSQL 存储，它用 DNS 解析端点。本次事故中，服务区域端点 dynamodb.us-east-1.amazonaws.com 的 DNS 记录变成了空。
• 时间线：
  • 10 月 19 日 11:48 PM PDT：北弗吉尼亚（us-east-1）所有通过 DynamoDB 连接的系统陷入恐慌状态，无法连接 us-east-1 的”副本表（Replica tables）”（其他区域正常）。
  • 10 月 20 日 12:38 AM：工程师定位问题，1:15 AM 施以修复。
  • 2:25 AM：DNS 信息全部恢复，并在 2:32 AM 前复制到 3 个可用区。（”结束了吗？”——没有。）
  • EC2 的次生灾难：10 月 19 日 11:48 PM 到 10 月 20 日 1:50 PM，EC2 API 的错误率与延迟上升，新建实例返回 “request limit exceeded” 或 “insufficient capacity”。背景是 DropletWorkflow Manager（DWFM）管理”droplets”即 EC2 实例，而 DWFM 的检查依赖 DynamoDB，因此在 11:48 PM 起失效；11:48 PM–2:24 AM 期间 DWFM 与 droplet 之间的租约（lease）开始超时。
  • 2:25 AM：DynamoDB 恢复，但 DWFM 不认为已过期的租约可以被续约——于是需要为 us-east-1 的所有 droplet 重新建立租约，租约系统与 DWFM 被压垮，讲义称之为 “DWFM 的充血性崩溃（Congestive Collapse of DWFM）”。
  • 4:14 AM：工程师开始限流（throttle）进来的请求并做选择性重启；5:28 AM：DWFM 恢复。
  • 5:28 AM：新 droplet 租约的洪流开始传播，压垮了 EC2 的 “Network Manager”；6:21 AM：Network Manager 观测到延迟上升，拖慢了 EC2 实例；10:36 AM：延迟恢复正常；11:23 AM：工程师开始逐级放松此前施加的限流；1:50 PM：EC2（现有实例与新建实例）恢复正常。
  • 负载均衡器的次生灾难：5:30 AM–2:09 PM，新 EC2 实例的网络状态传播延迟影响了部分客户的 NLB（Network Load Balancer）。NLB 是自动扩缩的架构，把流量路由到端点（EC2 实例），并使用健康检查系统。健康检查发现 EC2 实例失败，于是结果在 “failed” 与 “healthy” 之间来回翻转（flip-flopping）：判失败就把实例从 DNS 摘掉（增加 DNS 负载），判健康就加回 DNS（又增加 DNS 负载）。连多 AZ 负载均衡器也受影响（延迟升高）。9:36 AM：工程师禁用了自动化健康检查系统；2:09 PM：EC2 恢复后重新启用。
• 根因（讲义给出的”空 DNS 记录”六步竞态）：加快 DNS 更新的自动化程序名叫 Enactor（每个 AZ 一个）。讲义用”老师让两个学生合写实验记录本”的比喻解释：学生 1 昏昏欲睡、被 TikTok 分心，偶尔醒来猛写一阵；学生 2 勤快、总想”修正”学生 1 写得慢的内容，于是删掉/重写学生 1 之前写的东西；等老师来检查时，本子是空的。

  步骤 1: 慢的 DNS Enactor 读取当前 plan 的时间戳         --> 看到的是 plan_old
  步骤 2: 它开始应用 plan_new
  步骤 3: ...与此同时, 快的 DNS Enactor 创建了 plan_newest
  步骤 4: ...快的 Enactor 用 plan_newest 替换了一切
  步骤 5: ...快的 Enactor 删除 plan_new, 因为它比 plan_newest 旧
  步骤 6: 慢的 Enactor 用 plan_new 覆盖 plan_newest
          (此时 plan_new 已因步骤 5 被删除 ==> 内容是空的),
          因为它只在步骤 1 检查过一次 plan 的新鲜度
  结果: DNS 记录为空 ==> 依赖它的服务全部解析失败

• 讲义总结的根因：假设你的程序”跑得足够快”、不会发生并发、因此不需要并发控制。讲义的语气很重：这是分布式系统课上教的最基本的东西——”asynchrony is a way of life（异步是一种生活方式）“，”更多构建分布式系统的工程师真的应该去上一门分布式系统的课“。

（2）根因分析（分层）

（3）它违反了哪个理论假设

• “程序执行足够快，不会并发”（最直接的违反）：这正是”异步系统中不存在全局时间”（Ch.11）与”check-then-act 必须原子”（Ch.19 并发控制）的直接后果。慢 Enactor 的过期读等价于一个陈旧的快照，它随后把陈旧数据写回，覆盖了更新的版本——丢失更新（lost update）问题。
• “元数据/控制面故障的影响是局部的”：DNS 是本案例中的全局隐藏单点。讲义反复强调的”控制面一崩，整个数据面瘫痪“，在这里表现为：DynamoDB 的 DNS 记录为空 ⇒ 依赖它的 EC2 租约系统崩溃 ⇒ EC2 API 报 “insufficient capacity” ⇒ NLB 健康检查抖动。
• “故障恢复后系统会自然回到正常”：恢复本身成了新的故障源（租约风暴、状态传播洪流、健康检查翻转）。这是”恢复风暴”（thundering herd on recovery）的经典形态，与 Lecture 3 里 MapReduce 的 straggler、Ch.5 的冷启动风暴同源。
• “健康检查反映真实健康”：健康检查在 EC2 抖动期间自身振荡，并通过修改 DNS 放大故障——监控/自动化系统在这里成了放大器而非稳定器。

（4）暴露了哪些设计缺陷

1. 并发控制缺失：对共享的 plan 数据没有版本/锁/CAS（compare-and-swap），也没有”新鲜度在写入前重新校验”。
2. 自动化缺少安全护栏（guardrails）：讲义明确指出：随着自动化（”agents”）增加，故障根因正在从人（70%）转向自动化程序，因此需要给与云基础设施交互的 agent 加安全检查和护栏。
3. 租约设计对”批量过期”不友好：恢复时所有租约必须重建，形成尖峰；应支持分批/错峰续约或惰性续约。
4. 健康检查与 DNS 更新耦合：健康检查结果直接改写 DNS，形成”抖动 → 更多 DNS 写入”的正反馈；应加去抖（debounce）/迟滞（hysteresis）与每分钟变更上限。
5. 限流是最后手段：讲义时间线显示，真正止血靠 throttle + 选择性重启（4:14 AM）与禁用健康检查自动化（9:36 AM）——即人工接管自动化。这提示我们：自动化必须有”总开关”（kill switch）。

（5）教训与防御措施（讲义的四条总结）

1. 根因是”假设程序跑得够快、没有并发、因而不需要并发控制“；”asynchrony is a way of life“；更多工程师应当真正学过分布式系统。
2. “级联的原因让故障一直持续”（Cascading causes keep the outage going） ⇒ 需要新的原则来打断依赖链，并类比”死锁检测已经是一个被解决的问题“——即我们应当为”依赖链/因果链”建立类似的理论与工具（【补充】今天的对应物是爆炸半径控制、依赖图分析、cell 架构与断路器等）。
3. 数据中心容错类似于今天的医学：最常见的病症（崩溃）已经被解决，但罕见病例（意外宕机）依然可怕——即”常见故障有成熟处方，罕见故障仍是疑难杂症”。
4. 自动化程度提高 ⇒ 根因从人转向 agent ⇒ 需要给 agent 加安全检查与护栏。

（6）从分布式系统原理角度应该如何防范

26.2.11 人为错误案例集与其他故障来源（讲义案例 0 与收尾）

讲义用两页幻灯片列出了一批人为错误（Human error）案例，并在课堂竞猜中给出结论：数据中心宕机的首要原因是人为错误，约占 70%。这些案例的共同教训是：再好的冗余设计也可能被”人的一次动作”同时破坏两个副本/两条路径。

方法论提醒：讲义强调”还有很多很多（And many more!）“。研究这些案例不是为了嘲笑谁——事实上经历过事故的公司之后往往建设得更稳健；真正的目的是把”人一定会犯错”作为设计前提，从而把系统设计成”让人难以犯下致命错误“（例如：危险操作需要双人确认、删除要有回收站与延迟生效、变更要能一键回滚、DNS 发布要能自动校验语法与内容完整性）。

此外，讲义在收尾部分列出了其他故障来源与”企业开放程度”的对比：

• 不是所有公司都像前三家那样透明：RIM 2007 年 4 月发生持续一整天的宕机，没有公布任何细节；Hostway 2007 年 7 月通知客户要把机房从迈阿密搬到坦帕、停机 12 小时，实际停了 3–7 天。
• 测试很重要：American Eagle 在灾难中才发现自己无法切换到备份数据中心。
• 升级失败是常见的宕机原因 ⇒ 必须有回退计划（fallback plan）。
• 数据可用性与恢复：BCP（业务连续性计划）、灾难容错、跨机房复制（由提供商做或由客户自己做）。
• 文档一致性：一次 Google AppEngine 故障被拖长，原因是运维人员不知道恢复时该用哪个版本文档；Google 的修复办法是把旧文档显式标记为 “deprecated”。
• 宕机永远是级联的一系列失败 ⇒ 需要更多打断链条的方法。
• 其他故障来源：抗 DoS 能力；互联网中断——海底光缆被切断、DNS 故障、政府通过 DNS 屏蔽互联网（讲义给的解法是备用 DNS 服务）。
• 很多故障是意外的，但也有计划内停机（例如内核升级）：计划内停机必须计划好、步骤文档化并严格执行、回退方案到位。

26.2.12 工程实践之一：面向恢复的计算（Recovery-Oriented Computing, ROC）【补充框架，讲义精神一致】

• 定义与目的：面向恢复的计算（ROC）主张把”快速恢复“而不是”永不故障“作为第一设计目标。讲义虽然没有出现 “ROC” 这个词，但它的每一处教训都指向同一件事：宕机不可避免（”Outages are inevitable”）、减少恢复时间、快速重建而不是精细修复（Facebook 关站再缓慢放量、AWS 2011 最终只能”物理切断 + 逐个恢复”、The Planet 逐个机架上电）。

• 直观解释（”它是什么？”）：传统容错像”给玻璃杯加厚“——期望它不碎；ROC 像”给杯子配一个拖把和一块备用杯“——承认它一定会碎，于是把”碎之后多久能继续喝水”做短。讲义中 The Planet 一边恢复一边每 15–60 分钟通报客户、AWS 事后主动给客户多日抵扣，都是 ROC 的运维面：恢复过程本身要可沟通、可预期。

• ROC 的设计原则：
  1. 快速重启优于复杂的状态恢复（”reboot is a good first step”）：绝大多数故障源于状态污染（内存损坏、连接泄漏、配置漂移），干净重启往往比原地诊断更快、更可靠。讲义中 AWS 2025 的止血手段之一正是”选择性重启（selective restarts）“。
  2. 减少 MTTR 比增加 MTTF 更有效：见 26.3.6 的定量论证。
  3. 假设每个组件都会失败，并为恢复而设计（design for recovery）：包括可丢弃的中间状态、幂等重放、快速重建缓存（Facebook 恢复时让客户端慢慢重建缓存，正是”缓存可丢弃”的体现）。
  4. 隔离与分区（isolation）：把系统切成互不影响的单元，限制爆炸半径（26.5 的 cell 架构）。
  5. 系统化重启优于部分手工修复：部分修复会留下”半坏”状态，导致后续更难诊断（讲义中 “13% 的卷卡死”与”0.07% 永久丢失”就是长尾手工修复的代价）。
  6. 主动故障注入（26.2.13）：让恢复路径在平时就被反复走通。
• ROC vs 传统容错的对照表：

26.2.13 工程实践之二：混沌工程（Chaos Engineering）【补充：Netflix 提出；讲义中”测试很重要”与”计划内停机要演练”的思想一致】

• 定义与目的：混沌工程是”在生产环境中主动、持续地注入故障，以发现系统性弱点“的学科。它把”等故障自己暴露”（被动）变成”主动做实验”（主动），因为真实系统的失效模式无法靠阅读代码或单元测试推断——讲义的四个案例里，没有一个弱点是通过代码审查提前发现的。

• 核心原则（必须列出）：
  1. 定义”稳态（steady state）”假设：先用可量化的业务指标（成功率、p99 延迟、吞吐）描述”正常是什么样”，而不是用”CPU 使用率”这类内部指标。
  2. 在真实流量上做实验：用生产流量验证假设，因为测试环境的流量分布永远与生产不同（讲义中 AWS 2011 的竞态”只在高请求率下触发“，就是测试环境跑不出生产的负载）。
  3. 在生产环境做实验，但控制爆炸半径：可以先从小范围的金丝雀/单个实例开始，再逐步扩大；必须有随时终止实验（abort）的开关。
  4. 自动化、持续运行：一次性的演练会随时间失效（系统在演进），因此要把实验做成常态化的流水线。
  5. 最小化影响范围：实验造成的业务损失必须可接受且可度量（有错误预算支撑）。
• 典型实验（实践谱系）：
  • Chaos Monkey：随机关闭生产环境中的实例——验证”单个实例消失时系统是否无感”。对应讲义中”12000 台机器时平均 7.2 小时就有一台故障”的常态。
  • Chaos Gorilla：模拟整个可用区（AZ）故障——对应 The Planet / AWS 2011 这类”整机房”事故，验证跨 AZ 冗余与接管容量（对应讲义”American Eagle 才发现无法切换备份机房”的教训）。
  • 延迟注入（latency injection）：人为给某个依赖加 200ms/2s 延迟——这是灰色故障最有效的复现手段，也是对本章代码实验 1 的直接工程化。
  • 网络分区注入：切断/丢弃两个 AZ 之间的部分流量，验证非对称分区下的行为（AWS 2011 的分区是真实发生的）。
  • 磁盘填满、CPU 饥饿、内存压力、DNS 故障、证书过期：覆盖资源类与配置类故障。

• 与”故障注入（fault injection）”的区别：故障注入通常是测试环境中的确定性注入（为了验证某个已知机制，例如”杀掉主节点看是否切换”）；混沌工程强调在生产环境、基于稳态假设、持续随机地实验，目的是发现未知的未知（unknown unknowns）。讲义中 AWS 2025 的教训”随着自动化增加，根因正在从人转向 agent“，正是混沌工程需要覆盖的新领域。

• 前置条件（否则混沌工程就是自毁）：必须已经具备基本的容错能力——自动故障转移、限流、熔断、幂等、可观测性。如果系统还没有这些就注入故障，只会把”已知会崩”变成”真的崩”。工程上通用的准则是：先能观测、再能止血、最后才敢主动破坏。

26.2.14 工程实践之三：渐进式发布与变更管理（Progressive Delivery & Change Management）

• 定义与目的：变更（配置、代码、网络、内核）是事故最常见的触发器：讲义的经验教训里明确写着”升级失败是常见的宕机原因 ⇒ 需要回退计划“，并提到 Google 因”不知道该用哪版恢复文档”而延长故障、1300 万德国网站因误传空 zone file 而消失、AWS 2011 因一次网络流量调整而开始 3.5 天的故障。渐进式发布就是把”一次性全量变更”改成”小步、可观测、可回滚”的变更。

• 主要手段：

• 机制图解：金丝雀发布 + 快速回滚的时间线（错误率随发布进度的变化）。

   错误率
     ^
 5%  |                                                    ***  <-- 若继续扩大就会全站爆发
     |                                                  **
 2%  |                                                **
     |                                               *
 1%  |                                              *
     |                                             *
0.5% |                                         ****
     |                                     ****
 0.1%|***************************** *******
     +------+--------+--------+--------+--------+--------+--------+-------> 时间
          T0       T1       T2       T3       T4       T5       T6
          |        |        |        |        |        |
       部署 1%  观察 10min 扩到 5%  扩到 25% 指标越界  自动/人工回滚
                        (指标平稳)         (错误率 0.5%->2%)   |
                                                             v
                                                    100% 流量回到旧版本
                                            总影响面: 全站的 5%, 持续 ~4 分钟
   ★ 关键: (1) 每一步都要有"自动刹车"的判据(错误率/延迟/饱和度);
          (2) 回滚时间 << 扩量时间;  (3) 配置/开关变更与代码变更一样走这套流程。

• 配置变更为什么是最危险的一类：代码变更通常有测试、有 review、有编译检查；配置变更往往直接生效、没有类型检查、没有回滚、且影响所有实例。讲义的两个案例（Facebook 的无效配置值、德国 1300 万网站的空 zone file）都是”一次配置写入 = 一次全站故障”。因此工程上把配置当作代码：版本化、评审、灰度、可回滚、有 schema 校验。

26.2.15 工程实践之四：限流、熔断、舱壁、超时、重试与降级

这是本章最实用的一组机制。它们共同回答一个问题：当某个依赖变慢或不可用时，如何让”故障”停留在局部，而不是吃掉整个系统？

（a）限流与负载丢弃（Rate Limiting / Load Shedding）

• 定义与目的：主动限制进入系统的请求量（或丢弃一部分请求），以保证被服务的请求获得可接受的延迟。核心认识是：过载时”对所有人变慢”比”给一部分人快速失败”更糟——前者会让所有人超时，后者至少保住了一部分用户。
• 实践要点：
  • 按优先级丢弃：优先丢低价值/可重试/后台类流量，保住支付、登录等核心路径（26.3.3 给出伪代码）。
  • 过载信号的选择：入口排队长度、连接池占用率、p99 延迟，比 CPU 利用率更早、更准（CPU 在”线程全在阻塞等 IO”时反而不高）。
  • 配合背压（backpressure）与队列上限：无界队列只是把过载推迟成”内存耗尽 + 延迟无界”。
• 讲义印证：AWS 2025 中工程师”开始限流进来的请求“是恢复的关键一步；AWS 2011 中”禁用所有新的创建卷 API 请求“是最有效的止血动作之一（2:40 AM 禁用，2:50 AM 错误率开始恢复）。

（b）熔断器（Circuit Breaker）

• 定义与目的：当下游错误率超过阈值时，快速失败（不再调用下游），从而保护调用方自己的线程/连接等资源；经过冷却后试探性放行少量流量，成功则恢复。三种状态：Closed（正常放行）→ Open（快速失败）→ Half-Open（试探）。
• 直观解释（”它是什么？”）：家里的空气开关。电路短路时它跳闸（Open），不是因为它能修电路，而是因为继续通电会烧掉整栋房子；过一会儿你手动合闸试试（Half-Open），如果还短路就继续跳闸。26.3.1 给出完整伪代码与正确性论证。
• 讲义印证：AWS 2011 中”控制面线程池被填满后开始拒绝请求“是一种”被动熔断”（没有主动熔断器，只能等资源耗尽）；AWS 2025 中工程师”禁用自动化健康检查系统“实质上是在人工执行熔断。

（c）舱壁隔离（Bulkhead）

• 定义与目的：为不同的下游依赖分配独立的资源池（线程池/连接池/队列），使一个依赖的故障不能耗尽所有资源。
• 直观解释（”它是什么？”）：轮船的隔水舱——一个舱进水，整条船还能浮着。软件上就是”不要用同一个线程池调用所有下游”。

   反例: 共享线程池 (一个慢依赖吃掉全部资源)          正例: 舱壁隔离 (每个依赖各自一个池)
   ┌───────────────────────────────────────┐     ┌──────────────┐  ┌──────────────┐
   │            共享线程池 (60)            │     │  池 A (42)   │  │  池 B (18)   │
   │ ┌────┐┌────┐┌────┐┌────┐┌────┐┌────┐ │     │ ┌────┐┌────┐ │  │ ┌────┐┌────┐ │
   │ │DB  ││DB  ││DB  ││DB  ││DB  ││DB  │ │     │ │DB  ││DB  │ │  │ │AUX ││AUX │ │
   │ └────┘└────┘└────┘└────┘└────┘└────┘ │     │ └────┘└────┘ │  │ └────┘└────┘ │
   │  ▲ DB 变慢 ==> 全部线程被 DB 调用占住 │     │  慢依赖只占  │  │  健康依赖完全 │
   │  健康依赖(aux)拿不到任何线程 ==> 全灭 │     │  自己的池子   │  │  不受影响     │
   └───────────────────────────────────────┘     └──────────────┘  └──────────────┘
   讲义印证: AWS 2011 "控制面线程池被填满" ==> 连"创建卷"都无法服务;
             AWS 2025 "DWFM 的检查依赖 DynamoDB" ==> DWFM 被拖垮(充血性崩溃)。

• 代价与陷阱：分池会降低资源利用率（每个池都要留余量），并引入”池大小调优”问题；分得太细会导致资源碎片化。实践上常用信号量（semaphore）限并发而不是物理分池。

（d）超时（Timeout）必须设置，而且必须传播

• 定义与目的：没有任何一次远程调用可以不设超时。超时的作用是给资源占用设上界：只要每个调用都能在有限时间内返回（成功或失败），线程/连接就能被回收，系统就不会被”慢”击垮。
• 讲义印证：AWS 2011 的根因链里，”控制面操作的超时时间很长“直接导致线程池被填满——如果超时合理，慢操作会被及时放弃，线程池不会被占满。因此超时不是”有没有”的问题，而是”设多长”的问题（默认值往往过长：本章实验 1 中”库默认 3 秒”与”容量规划后的 250 毫秒”造成了天壤之别）。
• 实践要点：超时要沿调用链传播（上游的剩余预算必须传给下游，即 deadline propagation），否则下游可能在”上游已经放弃”的情况下继续消耗资源；超时值要略大于 p99 延迟，并对不同重要级别的请求使用不同预算。

（e）重试（Retry）必须有界、退避、抖动，并有预算

• 定义与目的：重试能掩盖瞬时故障（偶发丢包、leader 切换的短暂不可用），但会放大持续故障的负载。因此在”故障”场景下，重试是双刃剑。
• 必须同时满足的四条：
  1. 有界：最多重试 $r$ 次（讲义 Facebook 案例的解法：不要激进重试）。
  2. 指数退避：讲义原话——”每次请求失败，就等待上一次的两倍时间“（Exponential Backoff，802.11 等协议就是这么做的）。
  3. 抖动（jitter）：避免所有客户端在同一时刻重试（惊群），26.3.2 给出数学分析。
  4. 重试预算（retry budget）：给重试流量设总量上限（例如”重试不得超过正常请求量的 10%”）或”下游错误率超过某阈值就不再重试”（本讲义代码实验 1 的 S6 场景即如此）。
• 额外要求：只重试幂等操作（Lecture 18：at-least-once 语义 + 幂等才能安全重试；讲义提到 Sun RPC 采用 at-least-once 语义，而在故障下保证 exactly-once 很困难）。

（f）降级（Graceful Degradation）

• 定义与目的：在依赖不可用时返回部分结果、缓存结果、默认值或简化功能，而不是完全失败。
• 讲义印证：Facebook 恢复期”慢慢允许用户回来、让客户端慢慢重建缓存“，本质是渐进式降级恢复；讲义最后也提到”很多故障是意外的“，因此系统需要有”降级态”的设计（例如：只读模式、关闭个性化推荐、返回稍旧的数据）。
• 要点：降级要显式设计并定期演练（否则第一次使用降级路径就是在真实事故中）；降级结果要对调用方可区分（不能把降级的旧数据当成最新数据，否则会破坏一致性假设）。

26.2.16 工程实践之五：可观测性（Observability）与监控

• 定义与目的：可观测性指”仅通过系统对外输出的数据，就能推断系统内部状态”的能力。事故复盘的第一步永远是把时间线还原出来——讲义对每个案例都给出了精确到分钟的时间线，这本身就是可观测性的产物。

• 三大支柱：
  1. 指标（Metrics）：随时间聚合的数值（QPS、错误率、延迟分位数、饱和度）。必须看分位数而不是平均值——平均值会把”1% 的用户等 10 秒”掩盖成”平均 100ms”。
  2. 日志（Logs）：带结构化字段的事件记录；事故时用于定位第一个异常。讲义中”某台 primary 副本认为没有 backup”这类判断，只能从日志里看出来。
  3. 分布式追踪（Traces）：记录一个请求在整条调用链上的因果路径与每跳耗时。【补充】这本质上是 Lecture 12 全局快照（Chandy-Lamport）思想的工程化：把”请求的因果链”记录下来，让”卡在哪一跳”变成可查询的事实，而不是靠猜。这也是检测灰色故障的关键手段。

• 黄金信号（Golden Signals）【补充：Google SRE】：延迟（Latency）、流量（Traffic）、错误（Errors）、饱和度（Saturation）。四个信号一起看，才能在”变慢但不报错”的灰色故障中发现问题。

• 告警质量：
  • 避免告警疲劳：告警必须可行动（actionable），否则值班工程师会忽略真正的告警。
  • 基于 SLO 的错误预算告警：不问”CPU 是否超过 80%”，而问”错误预算是否在被快速消耗“——因为前者与用户体验无关，后者直接对应业务损失。
  • 从客户端视角测量（26.2.3 灰色故障）：服务器自报的健康度会骗人，用户视角的成功率与延迟不会。
• 讲义印证：讲义在收尾时特别提到，AWS、Facebook、The Planet 都在事故中持续向用户通报进展，并运行实时状态面板（Google Apps status dashboard、AWS dashboard）；AWS 2011 的具体教训之一是”更好的沟通工具与健康状态（AWS Dashboard）“。可观测性同时服务于对内止血与对外沟通两个目的。

26.2.17 工程实践之六：冗余的正确做法（破除常见误解）

• 误解一：”有 3 个副本所以可靠。” —— 若 3 个副本在同一机架/同一 AZ/同一电源域，一次机房级事件就全灭（26.2.4）。副本数不等于可靠性，故障域数量才等于可靠性。
• 误解二：”加了冗余就没有单点。” —— 冗余本身会引入新的相关性：同一个配置管理系统、同一次发布、同一个 DNS、同一个认证服务、同一个打包镜像、同一个自动化 agent（AWS 2025 的 Enactor 就是”每 AZ 一个”的自动化冗余，却共享同一个 plan 数据）。要沿着”变更路径”和”控制面路径”找相关性，而不只是沿着网络拓扑找。
• 误解三：”冗余能防软件 bug。” —— 同一个 bug 会在所有副本上同时发作（同版本、同配置、同输入）。这正是 26.4.2 实验要说明的：任何放置策略都无法防御相关故障，唯一缓解是多样化（diversity）——版本异构、实现异构、供应商异构、路径异构。
• 冗余的代价（必须算清楚）：3 副本意味着 3 倍存储成本与约 3 倍的写入带宽/网络开销（讲义在 Lecture 2 的云经济学与 Lecture 22 的复制讨论中都涉及成本）；跨 AZ/跨区域复制还要付跨区流量费与更高写延迟。因此工程上常做分级：核心元数据 3 副本跨 AZ，冷数据用纠删码，缓存不做持久冗余。
• 主动-主动 vs 主动-被动：
  • 主动-主动（active-active）：所有副本都服务流量，故障时无切换时间（RTO≈0），但需要解决冲突处理（并发写同一份数据）与一致性模型选择（Lecture 10/Ch.10 的一致性模型谱系）。
  • 主动-被动（active-passive）：备用副本平时不服务，故障时切换；实现简单、无冲突，但 RTO 取决于检测 + 切换时间（这正是 MTTR 中最大的一块）。
• 正确做法清单：定义故障域层级 → 用反亲和性约束把副本铺到最顶层故障域 → 为每个故障域预留接管容量（$N+1$/$N+2$）→ 定期演练真实切换 → 对变更路径做多样化与灰度。

26.2.18 工程实践之七：事后分析（Postmortem）文化

• 定义与目的：事后分析是把一次事故转化为组织记忆的流程。讲义要求的动作很具体：公开的事后报告 + 频繁更新 + 对客户的补偿，并明确指出这些”都增强了客户信心“——事故处理得好，反而能提升信任。

• 无指责（blameless）原则：关注系统与流程的缺陷，而不是个人的过失。理由是工程性的，而不是道德性的：人一定会犯错（讲义竞猜：人为错误占 70%），如果复盘变成追责，信息就会被隐藏，组织就学不到东西。正确的问法不是”谁按错了按钮”，而是”为什么系统允许一次按钮操作造成全站故障“，以及”为什么这个错误没有被护栏拦住、没有被监控发现、没有被快速回滚“。

• 事后报告的内容清单：
  1. 时间线（精确到分钟，包含”我们当时以为发生了什么”）；
  2. 影响面（多少用户/多少请求/多少数据，以及没有受影响的范围）；
  3. 根因（root cause） 与 促成因素（contributing factors）——通常是多个，讲义反复强调”宕机永远是级联的一系列失败“；
  4. 哪些”侥幸”避免了更坏的结果（near misses），这一项最容易被忽略，却最有价值；
  5. 哪些机制起了作用（例如 AWS 2011：使用了多 AZ 的客户没有受影响——这是对”故障域隔离有效”的实证）；
  6. 行动项（action items）：必须具体、可验证、有优先级、有负责人与截止日期（”加强安全意识”不是行动项，”把控制面超时从 30s 降到 2s 并在 3 月 1 日前完成灰度”才是）。
• 共享与学习：讲义的四个案例之所以能进入课堂，正是因为 AWS、Facebook 公开了 post-mortem；讲义同时批评了不透明的公司（RIM 2007 宕机一天不公布细节、Hostway 承诺 12 小时实际停 3–7 天）。公开复盘是行业级的学习机制。
• 制度化：把”故障演练 + 复盘 + 行动项跟踪 + 错误预算”连成一个闭环：复盘产出的行动项必须进入待办并被执行，否则事故会以同样的形式再来一次（讲义：”宕机永远是级联的一系列失败 ⇒ 需要更多打断链条的方法”）。

26.3 算法伪代码与正确性分析

本节给出五份防护机制的伪代码与正确性论证，外加一份”用可用性公式做定量决策”的数学论证。它们共同构成上一节工程实践的可执行骨架：熔断器回答”何时不再尝试”，退避重试回答”如何尝试”，负载丢弃回答”放弃谁”，舱壁回答”资源怎么分”，放置算法回答”副本放哪里”，而 26.3.6 回答”为什么这些机制的价值主要不在提高 MTTF，而在压缩 MTTR“。

算法 26.3.1：熔断器（Circuit Breaker）

假设与系统模型

• 环境：异步系统。调用方 $C$ 通过远程调用访问依赖 $D$；一次调用可能成功、返回错误、或超时（超时按错误处理）。
• 故障模型：$D$ 可能变慢（灰色故障）、部分失败、完全不可用；$C$ 无法区分”$D$ 慢”与”$D$ 坏”。
• 通道假设：消息可能丢失、延迟、乱序（因此超时与错误必须同等对待）。
• 目标：保护调用方自身的资源（线程/连接），而不是修复 $D$；即把”$D$ 的故障”限制在”$D$ 自己的流量”范围内。
• 参数：统计窗口 $W$、最少样本数 $N_{\min}$、失败率阈值 $\theta$、冷却时间 $T_{\text{cool}}$、半开试探数 $K$。

机制图解：三状态机与转移条件。

                         窗口内样本数 >= N_min  且  失败率 > θ
        +-------------------+  (下游连续失败, 且被算作失败的超时也计入)  +-------------------+
        |                   |------------------------------------------>|                   |
        |      CLOSED       |                                           |       OPEN        |
        |  (正常: 放行全部)  |                                           | (保护: 立即失败)   |
        |                   |<------------------------------------------|                   |
        +-------------------+        半开期间 K 次试探全部成功           +-------------------+
                 ^                        (且无任何一次失败)                     |
                 |                                                               | 经过 T_cool
                 |                                                               | (不需要外部信号)
                 |                                                               v
                 |              +-----------------------------------+
                 +--------------|            HALF_OPEN              |
                   全部成功      |  (试探: 只放行 K 个, 其余立即失败) |
                                +-----------------------------------+
                                                 |
                                                 | 试探中只要有 1 次失败
                                                 v
                                        (回到 OPEN, 且重置冷却计时)
   副作用对照:  每次 CLOSED 失败 --> 写窗口   每次 OPEN 请求 --> O(1) 失败, 零网络流量
               每次试探调用   --> 超时按失败处理(否则会卡在 HALF_OPEN)

伪代码

变量（调用方 C 本地状态）:
    state ∈ {CLOSED, OPEN, HALF_OPEN}   ← CLOSED
    window: 环形缓冲, 记录最近 W 秒内每次调用的 (时刻, 结果)     ← 空
    opened_at: 时间戳                                            ← ⊥
    trials_left: 半开状态剩余试探配额                            ← 0
    trial_inflight: 已放行但未回报结果的试探数                   ← 0
    trial_failed: 半开期间是否已出现失败                         ← false

upon event ⟨request, op⟩ at C:
    if state = CLOSED:
        send ⟨call, op⟩ to D ;  return PENDING
    if state = OPEN:
        if now - opened_at ≥ T_cool:
            state ← HALF_OPEN ;  trials_left ← K
            trial_inflight ← 0 ;  trial_failed ← false
            # 落到下面的 HALF_OPEN 分支处理本次请求
        else:
            return FAIL_FAST            # 不产生任何网络流量, O(1) 返回
    if state = HALF_OPEN:
        if trials_left > 0:
            trials_left ← trials_left - 1
            trial_inflight ← trial_inflight + 1
            send ⟨call, op⟩ to D ;  return PENDING
        else:
            return FAIL_FAST

upon event ⟨reply, result⟩ at C:        # result ∈ {OK, ERROR}
    failed ← (result = ERROR)
    if state = HALF_OPEN:
        trial_inflight ← trial_inflight - 1
        if failed:
            trial_failed ← true ;  state ← OPEN ;  opened_at ← now
        else if trial_inflight = 0 and not trial_failed:
            state ← CLOSED ;  window ← 空
    else if state = CLOSED:
        window.append((now, failed))
        丢弃 window 中所有时刻 < now - W 的项
        if |window| ≥ N_min and failure_ratio(window) > θ:
            state ← OPEN ;  opened_at ← now
    return result to 调用方

upon event ⟨timeout, op⟩ at C:          # ★ 关键: 慢 = 失败
    treat as ⟨reply, ERROR⟩

算法逻辑解说

设 $\theta=0.5$、$N_{\min}=20$、$W=2\,\text{s}$、$T_{\text{cool}}=5\,\text{s}$、$K=3$。走一遍数值例子：

1. $t=0$ 起 $D$ 变慢，2 秒内发生了 20 次调用，其中 12 次超时（失败率 $0.6>0.5$，样本数 $20\ge N_{\min}$）⇒ 状态转为 OPEN，记录 opened_at。
2. $t=2\,\text{s}\sim 7\,\text{s}$：所有请求走 FAIL_FAST 分支，零网络流量、微秒级返回。调用方的线程/连接被立刻释放——上游因此不会跟着一起慢（这就是”打断级联链”）。
3. $t=7\,\text{s}$：冷却期满，转 HALF_OPEN，trials_left=3。此刻恰好来了一批请求：前 3 个被放行去试探（trial_inflight=3），其余全部 FAIL_FAST。
4. 3 个试探中 2 个成功、1 个超时 ⇒ trial_failed=true ⇒ 回到 OPEN，opened_at 重置为现在——冷却重新开始，试探流量被限制在”每 5 秒最多 3 个调用”。
5. 若 $t=20\,\text{s}$ 时 $D$ 真的恢复了：3 个试探全部成功，trial_inflight 归零且 trial_failed=false ⇒ 状态回 CLOSED，窗口清空，恢复正常放行。

正确性论证

• 安全性（Safety）——熔断器能防止级联失败：

  引理 1（在途调用数有上界）：在 $D$ 持续故障期间，$C$ 对 $D$ 的在途调用数不超过 $K$。 证明：状态机中只有 CLOSED 与 HALF_OPEN 会执行 send。在 HALF_OPEN 下，trials_left 单调递减且只在进入 HALF_OPEN 时被重置为 $K$；而进入 HALF_OPEN 必须经过至少 $T_{\text{cool}}$ 的 OPEN 期。因此在任一长度为 $T_{\text{cool}}$ 的窗口内，放行的试探调用数 ≤ $K$，且同时在途数 ≤ $K$。$\square$ 推论：$D$ 慢下来时，被 $D$ 吞噬的调用方资源与请求到达率解耦——这正是级联失败的反面。对比没有熔断器的情况：每个请求都要等到超时才释放，在途调用数 $\approx \lambda \cdot \tau_{\text{timeout}}$（随到达率线性增长），线程池必然被填满。

  引理 2（快速失败保证调用方可用）：OPEN 状态下每次请求的额外耗时是 $O(1)$（一次状态判断），不占用网络连接与下游超时预算。因此调用方对其他依赖的服务能力不受 $D$ 影响——这是”故障横向扩散”被阻断的形式化表述。 依赖的假设：（a）阈值 $\theta<1$ 且窗口样本足够，否则不会触发；（b）超时必须被计入失败，否则灰色故障（”全部成功但都很慢”）永远不会触发熔断。

  反例（阈值假设不可缺）：若只统计”显式错误”而不统计超时，则一个”接受了所有请求但每个都 30 秒才回”的依赖可以让熔断器长期停留在 CLOSED，调用方线程池被占满——即讲义中 AWS 2011 “控制面操作超时很长 ⇒ 线程池填满 ⇒ 开始拒绝请求”的机制。

• 活性（Liveness）——半开状态的必要性：

  定理 1（不会永久打开）：若状态为 OPEN，则当 $now - opened\at \ge T{\text{cool}}$ 时，下一次请求必然把它推进到 HALF_OPEN。该转移不需要任何外部事件（不依赖 $D$ 主动通知、不依赖运维介入），因此熔断器必然会在有限时间内重新试探。$\square$ 为什么必须有半开状态：如果没有 HALF_OPEN（只允许 CLOSED/OPEN 两态），那么一旦打开就只能靠外部信号（人工重置或健康检查通过）才能关闭；而”依赖恢复”这件事恰恰无法从调用方内部观测——于是熔断器要么永久打开（可用性永久损失），要么被迫用固定周期盲目全量重开（把恢复瞬间的流量一次性打回仍未稳定的依赖，制造二次故障）。HALF_OPEN 用”小额、限速、可失败“的试探同时解决了这两个问题。

  定理 2（恢复条件明确）：若 $D$ 已恢复，$K$ 次试探将全部成功 ⇒ trial_inflight=0 且 trial_failed=false ⇒ 转 CLOSED；若 $D$ 未恢复，至少一次试探失败 ⇒ 转 OPEN 并重置冷却 ⇒ 试探流量被限制在每 $T_{\text{cool}}$ 至多 $K$ 次。$\square$

  实现的隐含约束：若试探调用悬挂（既不成功也不失败），trial_inflight 永不归零，熔断器会卡在 HALF_OPEN。因此试探调用必须有超时（伪代码中”超时按 ERROR 处理”正是关闭该漏洞的必要条件）。

• 代价（诚实说明）：熔断器会放弃一部分本来可能成功的请求。本章 26.4.1 的实验数据显示：加了熔断器的场景中，”故障依赖这一类请求”的成功率从 16.8% 降到 13.8%——熔断器用”牺牲故障依赖的流量”换取”调用方与健康依赖的存活”（健康依赖的成功率从 32.2% 升到 56.8%，P95 从无熔断时的”长时间排队”变成快速失败）。这正是设计者需要明确接受的取舍。

复杂度

• 时间：每次调用 $O(1)$（窗口为环形缓冲，摊销 $O(1)$；滑动窗口也可用计数器分桶实现）。
• 空间：$O(N_{\min})$（窗口）+ $O(1)$（状态）。
• 网络开销：CLOSED 时与业务调用相同；OPEN 时 0；HALF_OPEN 时每 $T_{\text{cool}}$ 至多 $K$ 次调用。相对”无熔断 + 无限重试”，故障期间发往 $D$ 的流量从 $\Theta(\lambda)$ 降到 $O(K/T_{\text{cool}})$。

算法 26.3.2：带抖动的指数退避重试（Exponential Backoff with Jitter）+ 重试预算

假设与系统模型

• 环境：异步系统；$n$ 个相互独立的客户端并发访问同一服务 $S$。
• 故障模型：$S$ 可能返回瞬时错误（可重试）或持续错误/过载（重试有害）。
• 通道假设：消息可能丢失、重复、延迟——因此重试必须假设”上次调用可能已经执行”（需要幂等或去重）。
• 目标：在瞬时故障下提高成功率；在持续故障下不放大负载。
• 参数：最大重试次数 $r_{\max}$、退避基数 $b$、单次退避上限 $b_{\max}$、整请求截止时间 $D$、重试预算比例 $B$、预算窗口 $W_b$。

伪代码

参数: r_max, b, b_max, D(整请求截止时间), B(重试预算比例), W_b(预算窗口)

变量（客户端 i 本地）:
    budget_used ← 0                # 窗口 W_b 内已用掉的重试次数
    attempt ← 0

upon event ⟨call, op⟩ at client i:
    attempt ← 0
    loop:
        if now ≥ deadline:                 # ① 截止时间(上层 SLO)优先
            return FAIL_DEADLINE
        send ⟨call, op, key=idempotency_key(op)⟩ to S
        wait for ⟨reply⟩ with timeout T
        if ⟨reply = OK⟩:  return OK
        attempt ← attempt + 1
        if not idempotent(op):  return FAIL           # ② 非幂等: 绝不重试
        if attempt > r_max:     return FAIL           # ③ 有界
        if budget_used ≥ B · requests_sent_in(W_b):   # ④ 重试预算
            return FAIL_BUDGET
        budget_used ← budget_used + 1
        d ← min(b · 2^(attempt-1), b_max)             # ⑤ 指数退避
        sleep random_uniform(0, d)                    # ⑥ 全抖动(full jitter)
    end loop

算法逻辑解说

设 $b=100\,\text{ms}$、$r_{\max}=3$、$b_{\max}=2\,\text{s}$。三次重试的退避基准是 $d_1=100$、$d_2=200$、$d_3=400\,\text{ms}$；采用全抖动后，实际等待是 $[0,d_k]$ 上的均匀随机数（期望 $50/100/200\,\text{ms}$）。若使用无抖动的固定退避，那么”在 $t_0$ 同时失败的所有客户端”会在 $t_0+100$、$t_0+300$、$t_0+700\,\text{ms}$ 三个时刻同步发起重试——这三个人为的尖峰就是”重试风暴”，也正是 Facebook 2010 事故中”所有缓存服务器同时去查数据库、数据库被每秒十万级查询压垮”的成因。

正确性论证

• 安全性 1（不放大：重试量的硬上界）： 引理：对每个用户请求，客户端最多发出 $1+r_{\max}$ 次调用；若预算生效，则全局重试流量 ≤ $B \times$ 正常流量。 证明：attempt 单调递增且被 $r_{\max}$ 截断；budget_used 单调递增，且每次重试前都必须通过 $budget\used < B\cdot requests\_sent\_in(W_b)$ 的检查，因此在任意窗口内重试次数不超过正常请求数的 $B$ 倍。$\square$ *推论*：下游面对的最坏负载是 $(1+r{\max})$ 倍（单层）；若 $L$ 层各自重试，则最坏 $(1+r_{\max})^L$ 倍——这就是”重试放大”的数学形式，也是必须在多层同时设置预算的原因（不能只在客户端设）。

• 安全性 2（抖动打散惊群）： 命题：设 $n$ 个客户端在 $t_0$ 同时失败。无抖动时，第 $k$ 次重试在 $t_0+\sum_{j\le k} d_j$ 处形成幅度为 $n$ 的尖峰；全抖动时，第 $k$ 次重试时刻是 $[t_0+S_{k-1},\,t_0+S_k]$（$S_k=\sum_{j\le k} d_j$）上的独立均匀随机变量，因此在”每个 1 ms 时间槽内到达的请求数”这一度量上，期望峰值从 $\Theta(n)$ 降到 $\Theta(n/(1000\,d_k))$ 量级。 证明要点：$n$ 个独立同分布随机变量之和的集中程度由标准差控制（$\propto\sqrt{n}$），而不是像同步情形那样退化成”全部落在同一时刻”。$\square$ 实践含义：抖动不减少总重试次数，只是把同样的重试量摊平在时间上；它把”同步冲击”变成”可被排队系统吸收的平滑负载”。对排队系统而言，这意味着下游的有效利用率 $\rho=\lambda\bar{s}$ 的瞬时峰值被削掉，从而避免”过载 → 超时 → 重试 → 更过载”的正反馈。

• 活性（Liveness）： 定理：若故障是瞬时的（首次重试即成功），请求在 $\le 1+r_{\max}$ 次尝试内返回 OK；若故障持续，请求在 $\le r_{\max}$ 次尝试与截止时间 $D$ 之内必然终止（返回 FAIL 而非无限重试）。$\square$ 因此重试机制不会让请求无限悬挂——这一点对 MTTR 至关重要（无限悬挂 = 资源永不释放 = 级联失败）。

• 依赖的假设（必须明说）：
  1. 幂等性：重试的前提是”重复执行不产生额外副作用”（Lecture 18：at-least-once + 幂等 ≈ 实际效果上的 exactly-once）。非幂等操作（如”转账”而不带去重键）重试会造成重复副作用。
  2. 下游有吸收能力：$(1+r_{\max})(1+B)$ 倍的瞬时负载必须在下游容量之内。若下游已经饱和，任何重试策略都是有害的——这也是”熔断 + 负载丢弃”必须与重试同时存在的原因。
  3. 预算判据可观测：错误率/预算统计依赖可观测性（26.2.16）；判据失准时预算形同虚设。
• 反例（”重试能提高可用性”错在哪）：在”下游容量已经不足”的场景中，重试不改变下游的有效容量（容量与到达率的差决定成功量），只会增加队列长度与延迟。本章 26.4.1 的实验直接量化了这一点：加入无退避重试后，入口尝试次数放大到 1.42 倍，积压峰值从 11793 升到 15562，平均延迟从 443 ms 升到 478 ms，而成功率没有任何提升（16.7% → 16.7%）——这就是讲义 Facebook 案例”重试没有退避、rinse-n-repeat”的定量复现。

复杂度

• 时间：每次用户请求 $O(1+r_{\max})$ 次调用；累计等待 $\le \sum_{k=1}^{r_{\max}} \min(b\cdot 2^{k-1}, b_{\max})$（几何级数，$O(b\cdot 2^{r_{\max}})$，被 $b_{\max}$ 截断）。
• 空间：$O(1)$（每个请求），加客户端的预算计数器 $O(1)$。
• 消息复杂度：每次用户请求 $O(1+r_{\max})$ 条消息；全系统重试消息量 $\le B$ 倍正常量（预算生效时）。

算法 26.3.3：负载丢弃与优先级队列（Load Shedding with Priority Queue）

假设与系统模型

• 环境：单服务（或单个前端），请求到达率 $\lambda$ 可能超过服务能力 $\mu$（过载）。
• 故障模型：过载是”慢故障”——不是崩溃，而是排队长度与延迟同时发散。
• 请求模型：每个请求携带优先级 $p\in\{HIGH, MED, LOW\}$；超过延迟预算 $D$ 的结果对用户没有价值（超时的成功等于失败）。
• 目标：过载时保住高优先级请求的服务质量，而不是”让所有请求一起变慢”。
• 参数：并发上限 $C$、软阈值 $L_{\text{soft}}$、硬上限 $L_{\text{hard}}(\gg L_{\text{soft}})$、延迟预算 $D$、中优先级自适应准入概率 $p_{\text{admit}}$。

伪代码

变量（服务端本地）:
    Q: 按优先级出队的队列（同级 FIFO）      ← 空
    inflight: 正在被处理的请求数            ← 0
    p_admit: 中优先级准入概率（自适应）      ← 1.0

upon event ⟨request, req⟩ at server:
    # ① 硬上限：任何优先级都拒绝, 保护自身不 OOM
    if inflight + |Q| ≥ L_hard:
        return OVERLOADED                       # O(1) 返回, 不排队
    # ② 过载判定（用"排队长度"与"实测 p99"双信号）
    overloaded ← (|Q| ≥ L_soft) or (p99_latency > D)
    if overloaded:
        p_admit ← max(0.05, p_admit * 0.9)      # AIMD 式收缩
    else:
        p_admit ← min(1.0, p_admit + 0.05)      # AIMD 式恢复
    # ③ 分级准入
    if overloaded and req.priority = LOW:
        return SHED                             # 优先丢弃低优先级
    if overloaded and req.priority = MED and random() > p_admit:
        return SHED
    if req.priority = HIGH and inflight ≥ C:    # 高优先级也保护硬上限
        return SHED
    # ④ 入队 + 调度
    Q.insert(req)                               # 按优先级出队, 同级 FIFO
    schedule()

upon event ⟨done, r⟩ at server:
    inflight ← inflight - 1
    schedule()

procedure schedule():
    while inflight < C and Q is not empty:
        r ← Q.pop_max_priority()                # ★ 高优先级严格优先
        inflight ← inflight + 1
        启动 r 的处理（并给 r 设置剩余预算 D - 已等待时间）

算法逻辑解说

设 $C=120$、$L_{\text{soft}}=100$、$L_{\text{hard}}=10000$，请求分高（20%）、低（80%）两类。正常情况下 $\vert Q\vert <100$，overloaded=false，p_admit=1，所有请求照常排队执行。当流量涨到 6 倍（本讲义代码实验中的洪峰），$\vert Q\vert $ 突破 100 ⇒ overloaded=true：低优先级请求在入口就被丢弃（SHED，耗时 $O(1)$，不占用任何资源），中优先级按 $p_{\text{admit}}$ 概率丢弃，高优先级照常入队并在队列里被优先出队。结果是：同样的物理容量下，高优先级请求的等待时间不会随低优先级流量增长。

正确性论证

• 安全性 1（资源有界）：恒有 $inflight\le C$ 且 $\vert Q\vert \le L_{\text{hard}}$，因此内存与线程占用有界（不会 OOM），且被丢弃的请求不占用任何资源。$\square$ 对比：无准入控制的系统里，队列无界 ⇒ 内存耗尽 + 延迟无界增长（AWS 2011 中控制面”操作积压、线程池填满”就是资源无界的表现）。

• 安全性 2（优先级隔离）：设高优先级到达率 $\lambda_H$、其平均服务时间 $\bar{s}_H$，则高优先级子系统的利用率 $\rho_H=\lambda_H\bar{s}_H$。若 $\rho_H<1$，则高优先级队列的长度随机稳定（stable）：因为（a）高优先级请求总是优先出队，其等待时间只由”前面正在被服务的高优先级请求”与”队列中已有的高优先级请求”决定，与低优先级流量无关；（b）过载时低优先级在入口就被丢弃，不会进入队列与高优先级竞争。因此高优先级请求的成功率不会因为低优先级洪峰而下降——这就是优先级队列 + 丢弃策略要给出的保证。$\square$ 本章实验印证：在”超时 + 熔断 + 舱壁 + 有界重试 + 优先级丢弃”的完整配置（S6）下，高优先级成功率 47.8%、低优先级 16.4%；而在只缺”优先级丢弃”的配置（S5）下，两者分别是 27.9% 与 27.4%——优先级丢弃把”平均地一起变慢”变成了”明确地保住一类流量”。

• 活性（Liveness）： 定理：若 $\rho_H<1$，高优先级请求在有限时间内被服务（队列稳定）；若 $\rho_H \ge 1$，则任何调度策略都无法避免队列发散——此时唯一的正确做法是继续丢弃（或扩容），而不是排队（排队只会把”快速失败”变成”缓慢失败 + 资源耗尽”）。$\square$ 这也解释了为什么”高优先级也必须受硬上限 $L_{\text{hard}}$ 约束”：优先级只决定丢弃顺序，不改变容量守恒。

• 必须同时满足的假设：

  1. 优先级不可被伪造（否则攻击者/错误调用方全部标 HIGH，等于没有优先级）；
  2. 低优先级不能永久饿死：纯优先级队列在 $\rho_H$ 接近 1 时会让低优先级无限等待，工程上需要 aging（等待越久优先级越高） 或配额预留；
  3. 过载信号可观测：$\vert Q\vert $ 与实测 p99 必须真实可得（灰色故障下服务器自测指标可能”看起来正常”，见 26.2.3）；
  4. 丢弃语义要对客户端可见（返回 503/429 + Retry-After），否则客户端会立刻重试，把丢弃变成重试风暴。

复杂度

• 时间：入队/出队 $O(\log \vert Q\vert )$（堆）或 $O(1)$（分级桶/多队列）；准入判断 $O(1)$。
• 空间：$O(L_{\text{hard}})$（队列）+ $O(1)$（状态）。
• 消息：被丢弃的请求零下游消息（这本身就是它保护系统的原因）。

算法 26.3.4：舱壁隔离的资源池划分（Bulkhead）

假设与系统模型

• 环境：一个调用方需要访问 $k$ 个下游 $D_1,\dots,D_k$（例如数据库、认证、推荐、日志）。
• 故障模型：任一 $D_i$ 都可能独立地变慢或不可用；调用方资源（线程/连接/FD）总数有限 $C_{\text{total}}$。
• 目标：$\forall i$，$D_i$ 的故障不得降低 $\{D_j\}_{j\ne i}$ 的服务质量。
• 参数：各下游的配额 $C_i$（$\sum_i C_i\le C_{\text{total}}$）、各池队列上限 $Q_i$、各调用超时 $\tau_i$。

伪代码

配置: 为每个下游 D_i 分配独立资源池 pool_i(容量 C_i) 与等待队列 queue_i(上限 Q_i)
      Σ_i C_i ≤ C_total

upon event ⟨request, op_i⟩ （op_i 需要访问 D_i）:
    if inflight_i ≥ C_i:                     # ★ 配额截断: 故障依赖到此为止
        if |queue_i| < Q_i and waited_i < τ_i:
            queue_i.insert(op_i)             # 短暂排队(仍受配额与超时约束)
        else:
            return REJECT_i                  # 快速失败 / 走降级路径
    else:
        inflight_i ← inflight_i + 1
        用 pool_i 中的连接 send ⟨call, op_i⟩ to D_i with timeout τ_i

upon event ⟨done, _⟩ for D_i:
    inflight_i ← inflight_i - 1
    if queue_i not empty and inflight_i < C_i:
        r ← queue_i.pop_first();  inflight_i ← inflight_i + 1; 重新发送 r

upon event ⟨timeout, _⟩ for D_i:
    视为 ⟨done⟩（归还连接、递减计数）      # ★ 舱壁必须与超时配合

算法逻辑解说

设 $C_{\text{total}}=60$，两个下游：$D_{\text{db}}$（配额 42）与 $D_{\text{aux}}$（配额 18）。$D_{\text{db}}$ 变慢 20 倍后，所有需要 db 的请求都会逐渐占满 42 个配额，然后停在 42：第 43 个及之后的 db 请求要么在受控的小队列里短暂等待（且受超时约束），要么被 REJECT_db 快速失败。由于 aux 的 18 个槽位从不被 db 请求占用，$D_{\text{aux}}$ 的健康流量保持正常——这就是”隔水舱”。

正确性论证

• 隔离定理（Isolation）：$\forall i$，若 $D_i$ 持续故障，则 $inflight_i$ 单调上升到 $C_i$ 后保持不变，且此后 $inflight_j\ (j\ne i)$ 的上界仍为 $C_j$，即对任意时刻： \(\sum_{j\ne i} inflight_j \;\le\; C_{\text{total}} - C_i\) 因此 $\{D_j\}_{j\ne i}$ 的可用容量与 $D_i$ 的状态无关，其服务质量由自身的 $C_j$ 与 $\lambda_j$ 决定。$\square$ 证明：由伪代码，inflight_i 只在通过 inflight_i < C_i 检查后才递增，因此它对所有 $t$ 恒有 $inflight_i\le C_i$；又 $pool_i$ 彼此独立（不共享连接/线程），故 $j$ 的池不会因 $i$ 的占用而减少。$\square$ 本章实验印证：S5（超时 + 舱壁，无熔断）与 S3（仅超时）相比，健康依赖 aux 的成功率从 32.2% 升到 52.2%，P95 延迟从 620 ms 降到 860 ms 的紧致分布（而 S4 用熔断实现保护时 P95 反而有 4820 ms 的长尾——因为熔断器存在”半开试探突发”的抖动，而舱壁是稳态的资源切分）。

• 代价引理（利用率损失）：舱壁用”峰值隔离”换”平均利用率”。当仅有部分下游繁忙时，空闲配额不可挪用（除非实现”借还”机制），因此 \(\text{平均利用率} \;\le\; \frac{\sum_i \min(\lambda_i\bar{s}_i,\; C_i)}{C_{\text{total}}}\) 在流量倾斜严重时，这个上界可能远低于 1。这就是”隔离”必须付费的地方，也是实践上常用信号量限并发（可动态调整）而非物理分池的原因。

• 活性：池内请求仍可能排队，因此舱壁必须配超时：否则一个”永不返回”的下游会把 $C_i$ 个槽位永久占死（隔离仍在，但 $D_i$ 自身永远无法恢复）。伪代码中 timeout 事件按 done 处理，保证了槽位归还。

• 与熔断的关系（互补性）：舱壁限制横向扩散半径（资源维度：一个依赖最多能吃掉多少资源）；熔断限制时间维度与流量（一个依赖的失败被允许持续多久、允许多少试探）。二者叠加才是完整的”故障隔离”：ACL 里的 “bulkhead + circuit breaker” 组合正是本章 S6 配置。

复杂度

• 时间：准入 $O(1)$；池内出队 $O(1)$。
• 空间：$O(\sum_i Q_i)$（队列）+ $O(\sum_i C_i)$（连接/线程）。
• 配置复杂度：需要为每个下游选择 $C_i$（本讲义实验中按流量比例 70/30 分池），是运维复杂度而非算法复杂度。

算法 26.3.5：相关性故障感知的副本放置（Fault-Domain-Aware Placement）

假设与系统模型

• 环境：$N$ 个存储节点，组织成故障域树：叶节点 = 机器，父节点 = 机架，更高层 = 可用区（AZ），再上层 = 区域。同一故障域内的组件会一起失效。
• 故障模型：一个故障事件 $\mathcal{E}$ 命中某个故障域（即该域内全部节点失效），故障位置在域内均匀随机；此外可能存在跨域的相关故障（同一软件版本、同一次配置推送、同一次定时任务）。
• 复制与一致性：每个对象有 $R$ 个副本；读写使用多数派 quorum（$R=3$ 时为 2）。系统可用的条件是存活副本数 ≥ 多数派。
• 目标：最小化”单个顶层故障域失效 ⇒ 丢多数派”的概率，并且不因未知的拓扑相关性而集中副本。

伪代码

输入: 对象 o, 副本数 R, 故障域树 T, 顶层故障域集合 F (|F| ≥ R), 节点可用性谓词 alive(·), 负载谓词 free(·)

procedure place(o):
    for attempt = 1 to A_max:                 # 有界重试, 避免放置过程本身失败
        F' ← random_sample_without_replacement(F, R)      # ★ 关键: R 个互不相同的顶层故障域
        pos ← []
        for f in F':
            cand ← { n ∈ leaves(f) : alive(n) ∧ free(n) }  # 域内候选
            if cand = ∅:  break to next attempt            # 该域当前无可用节点
            pos.append(random_choice(cand))                # ★ 域内随机, 而非贪心选"最空"
        if |pos| = R:  return pos
    return PLACEMENT_FAILED                   # 触发告警: 可用域不足, 需要扩容

procedure repair(o, failed_replica):          # 副本修复路径
    f_bad ← top_domain(failed_replica)
    cand_domains ← F \ { f_bad } ∪ {f : f 内已有副本}
    f_new ← random_choice({ f ∈ cand_domains : 域内当前副本数 = 0, 若不存在则取副本数最少者 })
    n ← random_choice({ n ∈ leaves(f_new) : alive(n) ∧ free(n) })
    在 n 上重建副本, 并从多数派读取数据做校验(端到端 checksum)

算法逻辑解说

以讲义代码实验 2 的拓扑为例：3 个 AZ × 3 机架 × 3 节点 = 27 台机器，$R=3$，多数派 = 2。

• 随机放置（无感知）：从 27 个节点里随机取 3 个 ⇒ 有 2.5% 的概率”3 个副本中有 2 个落在同一个机架”（超几何分布），一次机架失效就丢多数派。
• 索引贪心：若按”编号最小的空闲机器”贪心放置（节点编号往往是机架连续的），3 个副本刚好落在同一机架的 3 台机器上 ⇒ 一次机架失效丢掉全部 3 个副本（实验测得：机架失效丢多数派概率 11.11%，且 11.11% 的情况下全部副本丢失）。
• 机架感知：先随机选 3 个不同机架，再在机架内随机选机器 ⇒ 机架失效丢多数派概率降为 0；但单 AZ 失效仍可能命中 2 个副本（实验测得 22.4%）。
• 可用区感知：先随机选 3 个不同 AZ ⇒ 单机架失效 0%，单 AZ 失效 0%。

正确性论证

• 定理 1（单故障域失效的安全性）：若 $R$ 个副本位于 $R$ 个互不相同且互不包含的顶层故障域，则任一顶层故障域失效至多影响 1 个副本，存活副本数 $\ge R-1$。 对 $R=3$：存活 $2 \ge \lceil 4/2\rceil = 2$ ⇒ 仍有多数派，读写在 quorum 下继续可用（Lecture 17 的 quorum 相交性保证一致性不破）。$\square$ 推论（故障域层级必须对齐）：把副本铺在”机架子域”上并不能防”AZ 级失效”——因为一个 AZ 包含多个机架。故障域隔离必须做到与”副本数”同级的域数：3 个副本就要 3 个互不相交的顶层域。实验数据正是这一点的量化：机架感知在单 AZ 失效下仍有 22.1% 的概率丢多数派。

• 定理 2（相关性故障下保证失效 —— 相关性故障的形式化）：设存在跨故障域的相关故障事件 $\mathcal{E}$（例如”所有运行版本 $v$ 的节点同时因该版本的 bug 崩溃”，或”一次配置推送同时作用于所有节点”），令 $\mathcal{S}$ 为受影响的节点集合。 若所有副本都满足 $n\in\mathcal{S}$（同版本、同配置、同数据格式），则无论放置策略如何，受影响副本数 $=R$ ⇒ 多数派丢失；若损坏不可恢复（如磁盘数据被错误写入），则数据永久丢失。 形式化对比：在独立故障假设下，$P(\text{全部副本失效})=\prod_{i=1}^{R}P_i$，$R$ 越大越安全；在完全相关下，$P(\text{全部失效})=P(\mathcal{E})$，与 $R$ 无关。因此 \(\text{冗余度 }R \;\perp\; \text{相关故障}\) 即：增加副本数对相关故障没有任何帮助。$\square$ 实践含义（唯一解药是多样化）：让副本在版本、实现、供应商、运行时上异构（例如：主实现 + 独立重写实现、不同大版本灰度共存、不同云厂商的对象存储），使得 $\mathcal{S}$ 不可能覆盖所有副本；同时用渐进式发布保证”同一时刻不是所有副本都运行新版本”。实验 3 的”相关性故障”一行显示：所有放置策略的丢多数派概率都是 100%——这是本章最刺痛、也最重要的一行结论。

• 命题（随机化优于贪心）：在未知的拓扑相关性下（机器编号与机架/交换机/电源域的对应关系不是放置算法所能确知的），确定性贪心放置会把”未知的相关性”原样保留（甚至放大：编号连续 ⇒ 同机架）；而随机化把未知相关性转化为已知的均匀分布，使”某故障域命中 ≥2 个副本”的概率恰好等于超几何分布给出的值： \(P(\text{命中}\ge 2) = \frac{\binom{m}{2}\binom{N-m}{R-2}+\binom{m}{3}\binom{N-m}{R-3}}{\binom{N}{R}}\quad(m=\text{该故障域的节点数})\) 这个概率不依赖于我们是否知道拓扑，因此随机化在信息不完整时是稳健（robust）的；而一旦拓扑已知（现代云都提供 AZ/机架标签），就应当用显式的反亲和约束取代随机——即”随机是拓扑信息缺失时的兜底，故障域感知是拓扑信息可用时的最优”。

• 机制图解：随机放置 vs 故障域感知放置的多数派存活概率对比（数据来自 26.4.2 的实验，3 副本，27 台机器，4000 次蒙特卡洛）。

   丢多数派的概率   (机架失效 = 3 台, 可用区失效 = 9 台, 相关故障 = 27 台全中)
   策略              单机架失效        单可用区失效       相关性故障(同版本/同配置)
   ----------------  ----------------  -----------------  ------------------------------
   A 随机(无感知)     2.5%  #           25.2% #######      100% ############################
   B 索引贪心(0,1,2) 11.1%  ###         33.3% #########    100% ############################
   C 机架感知         0.0%  .           22.4% ######       100% ############################
   D 可用区感知       0.0%  .            0.0% .            100% ############################
   ----------------  ----------------  -----------------  ------------------------------
   刻度:             0%           25%   0%          25%    0%                        100%
   读法:
     (1) D(可用区感知) 把"单域失效丢多数派"压到 0 —— 故障域层级必须与副本数对齐;
     (2) B(贪心) 比 A(随机) 更差 —— 确定性的贪心把"未知的拓扑相关性"原样放大;
     (3) 相关性故障那一列对所有策略都是 100% —— 冗余救不了相关故障, 只能靠多样化。
         (注: A 的"丢全部副本"概率在机架失效下为 0.04%, B 为 11.11%。)

复杂度

• 时间：单次放置 $O(R\cdot \log\vert F\vert )$（域抽样）+ 域内采样 $O(1)$；带重试 $O(A_{\max}\cdot R)$。
• 空间：每个对象 $O(R)$ 的位置元数据。
• 对比随机放置：多出的开销仅是”域选择”这一步，代价极小，收益是”单域失效不再丢多数派”。

26.3.6 定量论证：可用性的两条改进路径（$A=\dfrac{\text{MTTF}}{\text{MTTF}+\text{MTTR}}$）

模型与推导

一个”故障—修复”周期的长度是 $\text{MTTF}+\text{MTTR}$，其中不可用时间为 MTTR，因此长期平均可用性为 \(A=\frac{\text{MTTF}}{\text{MTTF}+\text{MTTR}}=\frac{1}{1+\rho},\qquad \rho=\frac{\text{MTTR}}{\text{MTTF}}\) 这是一个只依赖比值 $\rho$ 的函数。由此立刻得到三条结论：

结论 1（两条路径的精确等价）：把 MTTR 缩小 $k$ 倍与把 MTTF 提高 $k$ 倍，对 $\rho$ 的影响完全相同，因此对可用性的提升也完全相同。在数学上两条路完全对称。

结论 2（绝对量上的不对称）：对 $\rho$ 取对数微分：$\mathrm{d}\rho/\rho = \mathrm{d}\text{MTTR}/\text{MTTR} - \mathrm{d}\text{MTTF}/\text{MTTF}$。因此省下 1 小时 MTTR 等价于提高 $\dfrac{\text{MTTF}}{\text{MTTR}}$ 小时的 MTTF。 数值例子（$\text{MTTF}=10000$ h，$\text{MTTR}=10$ h）：

结论 3（规模效应让 MTTR 成为唯一可用杠杆）：$n$ 个组件构成的系统，其 MTTF 近似为 \(\text{MTTF}_{\text{sys}} \approx \frac{\text{MTTF}_{\text{unit}}}{n}\) 讲义给的数量级：单机平均 10 年（120 个月）出一次故障 ⇒ 120 台服务器时系统 MTTF ≈ 1 个月；12000 台时 ≈ 7.2 小时（Lecture 5-6 原话：”Failures are the norm, not the exception”）。于是规模每扩大 10 倍，MTTF 就缩短 10 倍；要保持可用性不变，MTTR 也必须缩短 10 倍。用本章代码实验 3 的数字：若单机 MTTF = 10 年，要把 12000 台的系统做到 99.99%，需要 MTTR ≤ 2.6 秒——人工响应绝无可能，只能靠自动故障转移 + 自动重启 + 自动回滚。而 10 万台规模下要求 MTTR ≤ 0.32 秒，只有”无人工介入的全自动切换”才能满足。

结论 4（从三个 9 到五个 9）：停机时间要从 8.76 小时/年（99.9%）压到 5.26 分钟/年（99.999%），需要 100 倍改善。要么 MTTR 缩小 100 倍（从 10 小时到 6 分钟：需要自动化检测 + 自动切换 + 一键回滚），要么 MTTF 提高 100 倍（在 12000 台规模下，等于要求单机 MTTF 达到 1.2 亿小时 ≈ 13700 年——物理上不可能）。

综上，ROC 的核心论据成立：

在”商品化硬件 + 大规模”的现实里，$\text{MTTF}_{\text{sys}}$ 会随规模线性恶化且不可控，而 MTTR 是设计变量（超时、熔断、负载丢弃、自动切换、快速重启、可回滚变更、混沌演练都在压缩它）。因此提高可用性的主杠杆是减少 MTTR，而不是追求零故障。 这也解释了为什么讲义中所有四个案例的”教训”都落在同一类动作上：更快地检测、更快地止血、更快地恢复、更快地回滚。

26.4 代码示例与分布式实现

三份代码都只用 Python 标准库、固定随机种子、可直接 python3 xxx.py 运行，并且输出即本章的定量证据：第一份把”级联失败如何发生、各种防护机制如何起作用”完整跑出来；第二份把”相关性故障与故障域隔离”变成概率表；第三份把”两条改进路径”变成可计算的数字。

26.4.1 实验 1：级联失败与六种防护机制的模拟器

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""CS 425 Lecture 26 / 代码 1: 级联失败与六种防护机制的对比模拟器

服务链(同步阻塞调用; 上游槽位在下游调用的整个过程中一直被占住 —— 这正是级联失败的机理):
    api(120 个前端处理线程) -> svc(60 个工作线程) -> db(10 连接) / aux(5 连接)
故障时间线:
    t = 15s : db 服务时间变成 20 倍 (容量 1000/s -> 50/s)
    t = 25s : 6 倍流量洪峰, 持续到 t = 40s
仅使用 Python 标准库; 固定随机种子; 可直接 python3 运行。
"""

import math
import random
from collections import deque
from itertools import islice

SEED = 425
DT = 0.01                       # 一个 tick = 10 ms
T_END = 60.0
DEGRADE_AT, DB_SLOWDOWN = 15.0, 20.0
SURGE_AT, SURGE_END, SURGE_X = 25.0, 40.0, 6.0
RATE = 400.0                    # 基础入口到达率 (req/s)
SLOTS = {"api": 120, "svc": 60, "db": 10, "aux": 5}
BULKHEAD = {"db": 42, "aux": 18}          # 舱壁: svc 线程按依赖分成两个独立池
MEAN_MS = {"api": 5.0, "svc": 10.0, "db": 10.0, "aux": 10.0}
DEP_PROB = 0.7                  # 70% 请求要访问 db, 30% 访问 aux
PRIO_HIGH = 0.2
DEFAULT_WAIT = 3.0              # 库默认超时(没人调过)
TUNED_WAIT = 0.25               # 按延迟预算规划过的超时
CLIENT_TO = 5.0                 # 客户端(用户)放弃的时限
BREAKER_WIN, BREAKER_MIN, BREAKER_ERR = 2.0, 20, 0.5
BREAKER_COOL, BREAKER_TRIALS = 5.0, 3
MAX_RETRIES = 3
RETRY_BASE = 0.05
RETRY_BUDGET_ERR = 0.9          # 重试预算: 下游错误率超过它就不再重试
SHED_HIGH, SHED_LOW = 100, 50   # api 排队 >100 丢弃低优先级, 回落到 50 才恢复
SLO_MS = 100.0                  # "好请求"的延迟预算
SCAN = 64                       # 每 tick 最多从队首扫多少个请求来分配槽位

CONFIGS = {
    "S1 无防护": dict(tuned=False, retry=False, breaker=False, bulkhead=False, shed=False),
    "S2 加重试": dict(tuned=False, retry=True, breaker=False, bulkhead=False, shed=False),
    "S3 加超时": dict(tuned=True, retry=False, breaker=False, bulkhead=False, shed=False),
    "S4 加熔断": dict(tuned=True, retry=False, breaker=True, bulkhead=False, shed=False),
    "S5 加舱壁": dict(tuned=True, retry=False, breaker=False, bulkhead=True, shed=False),
    "S6 全防护": dict(tuned=True, retry=True, breaker=True, bulkhead=True, shed=True),
}


class Req:
    __slots__ = ("rid", "prio", "dep", "born", "stage", "wait_from",
                 "retries", "q_layer", "cb")

    def __init__(self, rid, prio, dep, born):
        self.rid, self.prio, self.dep, self.born = rid, prio, dep, born
        self.stage, self.wait_from, self.retries, self.q_layer = 0, born, 0, None
        self.cb = False                     # 本次下游调用要不要向熔断器汇报结果


class Layer:
    """busy = 正在被服务; held = 已服务完本层但正在等下游(槽位仍被占住)"""
    def __init__(self, name, pools):
        self.name, self.pools = name, pools
        self.busy, self.held, self.queue = {}, {}, deque()
        self.cnt = {p: 0 for p in pools}    # 增量维护占用计数, 避免每次 O(n) 求和

    def free(self, pool):
        return self.pools[pool] - self.cnt[pool]

    def put_busy(self, rid, pool, rem):
        if rid not in self.busy:
            self.cnt[pool] += 1
        self.busy[rid] = (pool, rem)

    def pop_busy(self, rid):
        v = self.busy.pop(rid, None)
        if v is not None:
            self.cnt[v[0]] -= 1
        return v

    def busy_to_held(self, rid):
        v = self.busy.pop(rid, None)
        if v is not None:
            self.held[rid] = v[0]

    def pop_held(self, rid):
        v = self.held.pop(rid, None)
        if v is not None:
            self.cnt[v] -= 1

    def total_used(self):
        return len(self.busy) + len(self.held)

    def total_slots(self):
        return sum(self.pools.values())


class Breaker:
    """三状态熔断器: CLOSED -> OPEN -> HALF_OPEN -> CLOSED"""
    def __init__(self):
        self.state, self.calls, self.opened_at = "CLOSED", [], -1.0
        self.trials = self.inflight = 0
        self.failed_trial = False

    def allow(self):
        if self.state == "CLOSED":
            return True
        if self.state == "HALF_OPEN" and self.trials > 0:
            self.trials -= 1
            self.inflight += 1
            return True
        return False

    def record(self, now, failed):
        if self.state == "HALF_OPEN":
            self.inflight -= 1
            if failed:
                self.failed_trial = True
                self.state, self.opened_at = "OPEN", now
            elif self.inflight <= 0 and not self.failed_trial:
                self.state, self.calls = "CLOSED", []
            return
        if self.state == "OPEN":
            return
        self.calls.append((now, failed))
        self.calls = [c for c in self.calls if now - c[0] <= BREAKER_WIN]
        if len(self.calls) >= BREAKER_MIN:
            errs = sum(1 for _, f in self.calls if f)
            if errs / len(self.calls) > BREAKER_ERR:
                self.state, self.opened_at = "OPEN", now

    def tick(self, now):
        if self.state == "OPEN" and now - self.opened_at >= BREAKER_COOL:
            self.state, self.trials = "HALF_OPEN", BREAKER_TRIALS
            self.inflight, self.failed_trial = 0, False

    def err_ratio(self):
        if len(self.calls) < BREAKER_MIN:
            return 0.0
        return sum(1 for _, f in self.calls if f) / len(self.calls)


def poisson(lam):
    if lam <= 0:
        return 0
    if lam > 30:
        return max(0, int(random.gauss(lam, math.sqrt(lam))))
    l, k, p = math.exp(-lam), 0, 1.0
    while True:
        k += 1
        p *= random.random()
        if p <= l:
            return k - 1


class Sim:
    def __init__(self, cfg):
        self.cfg = cfg
        pools = {n: {"": SLOTS[n]} for n in SLOTS}
        if cfg["bulkhead"]:
            pools["svc"] = dict(BULKHEAD)
        self.layers = {n: Layer(n, pools[n]) for n in SLOTS}
        self.reqs, self.retry_q, self.born_q = {}, [], deque()
        self.breaker, self.now, self.rid = Breaker(), 0.0, 0
        self.arrived = self.attempts = self.ok = self.failed = 0
        self.dep_calls = self.fast_fail = 0
        self.reached = {}
        self.lat, self.good = [], 0
        self.prio = {0: [0, 0], 1: [0, 0]}
        self.cls = {"db": [0, 0], "aux": [0, 0]}
        self.buckets, self.rate, self.shedding = [], [], False
        self.t_q1k = self.t_q5k = None

    # ---------- 工具 ----------
    def names_of(self, stage):
        return ["api"] if stage == 0 else (["svc"] if stage == 1 else ["db", "aux"])

    def layer_of(self, stage, req):
        return self.layers["api" if stage == 0 else ("svc" if stage == 1 else req.dep)]

    def pool_of(self, stage, req):
        return req.dep if (self.cfg["bulkhead"] and stage == 1) else ""

    def service_ms(self, name):
        mean = MEAN_MS[name]
        if name == "db" and self.now >= DEGRADE_AT:
            mean *= DB_SLOWDOWN
        return random.expovariate(1.0 / mean)

    def wait_limit(self):
        return TUNED_WAIT if self.cfg["tuned"] else DEFAULT_WAIT

    def rate_now(self):
        return RATE * (SURGE_X if SURGE_AT <= self.now < SURGE_END else 1.0)

    # ---------- 请求生命周期 ----------
    def admit(self, prio, dep):
        self.arrived += 1
        self.attempts += 1
        self.prio[prio][1] += 1
        self.cls[dep][1] += 1
        req = Req(self.rid, prio, dep, self.now)
        self.rid += 1
        self.born_q.append((self.now, req.rid))
        if self.cfg["shed"]:
            q = len(self.layers["api"].queue)
            if self.shedding and q <= SHED_LOW:
                self.shedding = False
            elif q > SHED_HIGH:
                self.shedding = True
            if self.shedding and prio == 1:      # 过载时优先丢弃低优先级请求
                self.failed += 1
                return
        self.reqs[req.rid] = req
        self.enter(req, 0)

    def enter(self, req, stage):
        if stage == 2 and req.dep == "db" and self.cfg["breaker"] and not self.breaker.allow():
            self.fast_fail += 1                  # 熔断打开: 立刻失败, 不碰下游
            self.fail(req)
            return
        if stage == 2:
            self.dep_calls += 1                  # 真正到达下游的调用
            self.reached[req.rid] = True
            req.cb = self.cfg["breaker"]
        lay = self.layer_of(stage, req)
        pool = self.pool_of(stage, req)
        req.stage, req.wait_from = stage, self.now
        if lay.free(pool) > 0:
            lay.put_busy(req.rid, pool, self.service_ms(lay.name))
        else:
            lay.queue.append(req.rid)
            req.q_layer = lay.name

    def dispatch(self, stage):
        for name in self.names_of(stage):
            lay = self.layers[name]
            while lay.queue and lay.queue[0] not in self.reqs:
                lay.queue.popleft()              # 惰性删除: 清掉已经结束的请求
            while True:
                pick = None
                for rid in islice(lay.queue, SCAN):
                    r = self.reqs.get(rid)
                    if r is None or r.stage != stage or (stage == 2 and r.dep != name):
                        continue
                    p = self.pool_of(stage, r)
                    if lay.free(p) > 0:
                        pick = rid
                        break
                if pick is None:
                    break
                lay.queue.remove(pick)
                r = self.reqs[pick]
                r.q_layer = None
                lay.put_busy(pick, self.pool_of(stage, r), self.service_ms(name))

    def advance(self, stage):
        for name in self.names_of(stage):
            lay = self.layers[name]
            for rid in list(lay.busy):
                pool, rem = lay.busy[rid]
                r = self.reqs.get(rid)
                if r is None:
                    lay.pop_busy(rid)
                    continue
                rem -= DT * 1000.0
                if rem > 0:
                    lay.busy[rid] = (pool, rem)
                    continue
                lay.busy_to_held(rid)            # 槽位继续被占住, 直到下游调用结束
                if stage < 2:
                    self.enter(r, stage + 1)
                else:
                    self.success(r)
        self.dispatch(stage)

    def success(self, req):
        if req.cb:
            self.breaker.record(self.now, False)
            req.cb = False
        dt = self.now - req.born
        self.release(req)
        self.ok += 1
        self.lat.append(dt)
        if dt * 1000 <= SLO_MS:
            self.good += 1
        self.prio[req.prio][0] += 1
        self.cls[req.dep][0] += 1

    def fail(self, req, client_retry=True):
        """一次尝试失败: 释放全部资源; 客户端可选择重试(从入口重新发起)"""
        if req.cb:
            self.breaker.record(self.now, True)
            req.cb = False
        self.release(req)
        if client_retry and self.cfg["retry"] and req.retries < MAX_RETRIES:
            if not self.cfg["breaker"] or self.breaker.err_ratio() < RETRY_BUDGET_ERR:
                req.retries += 1
                delay = 0.0
                if self.cfg["breaker"]:          # S6: 指数退避 + 抖动
                    delay = RETRY_BASE * (2 ** req.retries) * random.uniform(0.5, 1.5)
                self.retry_q.append((self.now + delay, req))
                return
        self.failed += 1

    def release(self, req):
        for name in ("api", "svc", req.dep):
            lay = self.layers[name]
            lay.pop_busy(req.rid)
            lay.pop_held(req.rid)
        req.q_layer = None
        self.reqs.pop(req.rid, None)

    def check_timeouts(self):
        lim = self.wait_limit()
        for name in ("api", "svc", "db", "aux"):
            lay = self.layers[name]
            head = []
            for i, rid in enumerate(lay.queue):  # 只检查队首 8 项(排队基本按时间有序)
                if i >= 8:
                    break
                head.append(rid)
            for rid in head:
                r = self.reqs.get(rid)
                if r is not None and self.now - r.wait_from > lim:
                    lay.queue.remove(rid)
                    r.q_layer = None
                    self.fail(r)
        while self.born_q and self.now - self.born_q[0][0] > CLIENT_TO:
            _, rid = self.born_q.popleft()
            r = self.reqs.get(rid)
            if r is not None:
                self.fail(r, client_retry=False)   # 用户放弃: 不再重试

    # ---------- 主循环 ----------
    def run(self):
        for k in range(int(T_END / DT)):
            self.now = k * DT
            self.breaker.tick(self.now)
            for _ in range(poisson(self.rate_now() * DT)):
                self.admit(0 if random.random() < PRIO_HIGH else 1,
                           "db" if random.random() < DEP_PROB else "aux")
            if self.retry_q:
                due = [x for x in self.retry_q if x[0] <= self.now]
                self.retry_q = [x for x in self.retry_q if x[0] > self.now]
                for _, r in due:                 # 重试 = 从入口再发起一次完整尝试
                    self.attempts += 1
                    self.reqs[r.rid] = r
                    r.stage, r.wait_from = 0, self.now
                    self.enter(r, 0)
            for stage in (0, 1, 2):
                self.advance(stage)
            self.check_timeouts()
            if k % 200 == 0:
                self.sample()
        self.sample()
        self.analyze()

    def sample(self):
        for lay in self.layers.values():         # 惰性删除后压缩队列
            lay.queue = deque(rid for rid in lay.queue if rid in self.reqs)
        self.buckets.append(dict(
            arrived=self.arrived, ok=self.ok, failed=self.failed,
            api_q=len(self.layers["api"].queue), svc_q=len(self.layers["svc"].queue),
            db_q=len(self.layers["db"].queue),
            api_u=self.layers["api"].total_used() / SLOTS["api"],
            svc_u=self.layers["svc"].total_used() / SLOTS["svc"],
            db_u=self.layers["db"].total_used() / SLOTS["db"]))

    def analyze(self):
        prev_a = prev_o = 0
        for b in self.buckets:
            da, do = b["arrived"] - prev_a, b["ok"] - prev_o
            prev_a, prev_o = b["arrived"], b["ok"]
            self.rate.append(do / da if da else 1.0)
        for i, b in enumerate(self.buckets):      # 入口积压首破阈值(千/五千)的时刻
            if self.t_q1k is None and b["api_q"] > 1000:
                self.t_q1k = i * 2.0
            if self.t_q5k is None and b["api_q"] > 5000:
                self.t_q5k = i * 2.0


def chart(values, width=52, height=6, ymax=100.0, char="*"):
    n, grid = len(values), [[" "] * width for _ in range(height)]
    for c in range(width):
        lo, hi = int(c * n / width), max(int(c * n / width) + 1, int((c + 1) * n / width))
        v = sum(values[lo:hi]) / len(values[lo:hi])
        lvl = max(0, min(height - 1, int(round(v / ymax * (height - 1)))))
        grid[height - 1 - lvl][c] = char
    out = ["%5.0f%% |%s" % (ymax * (height - 1 - r) / (height - 1), "".join(grid[r]))
           for r in range(height)]
    out.append("       +" + "-" * width)
    marks = [" "] * width
    for t, sym in ((0, "0"), (15, "!"), (25, "S"), (40, "e"), (60, "6")):
        marks[min(width - 1, int(t / T_END * width))] = sym
    out.append("        " + "".join(marks) + "   ! DB变慢   S~e 洪峰期")
    return out


def pct(x, y):
    return 100.0 * x / y if y else 0.0


def summarize(s):
    lat = sorted(s.lat)
    return dict(
        ok=pct(s.ok, s.arrived), good=pct(s.good, s.arrived),
        lat_ms=(sum(s.lat) / len(s.lat) * 1000) if s.lat else 0.0,
        p95_ms=lat[int(len(lat) * 0.95)] * 1000 if lat else 0.0,
        amp=s.attempts / max(1, s.arrived), down_amp=s.dep_calls / max(1, s.arrived),
        qmax=max(b["api_q"] for b in s.buckets),
        svc_u=sum(b["svc_u"] for b in s.buckets) / len(s.buckets) * 100,
        hi=pct(*s.prio[0]), lo=pct(*s.prio[1]),
        db=pct(*s.cls["db"]), aux=pct(*s.cls["aux"]),
        fast=s.fast_fail, q1k=s.t_q1k, q5k=s.t_q5k)


def main():
    print("=" * 84)
    print("CS 425 L26 实验 1: 级联失败与六种防护机制")
    print("链路 api(120线程) -> svc(60线程) -> db(10连接)/aux(5连接);  入口 400 req/s")
    print("t=15s 数据库变慢 20 倍(容量 1000/s -> 50/s);  t=25~40s 六倍流量洪峰")
    print("=" * 84)
    res = {}
    for name, cfg in CONFIGS.items():
        random.seed(SEED)                        # 同一随机序列, 便于公平对比
        s = Sim(cfg)
        s.run()
        res[name] = s
        m = summarize(s)
        print("\n--- %s ---" % name)
        print("  成功率 %.1f%% (%d/%d 次尝试)   好请求率(成功且<=100ms) %.1f%%   失败 %d"
              % (m["ok"], s.ok, s.arrived, m["good"], s.failed))
        print("  平均延迟 %.0f ms   P95 %.0f ms   入口放大 %.2fx   下游调用放大 %.2fx   熔断快速失败 %d"
              % (m["lat_ms"], m["p95_ms"], m["amp"], m["down_amp"], m["fast"]))
        print("  高优先级成功率 %.1f%%   低优先级 %.1f%%   db 类 %.1f%%   aux 类 %.1f%%"
              % (m["hi"], m["lo"], m["db"], m["aux"]))

    s1 = res["S1 无防护"]
    print("\n" + "=" * 84)
    print("S1(无防护)时间线 —— 本章最重要的表: 一个依赖变慢如何吃掉调用方的资源")
    print("=" * 84)
    print("  时刻  api排队  svc排队  db排队   api占用  svc占用   db占用   该段成功率")
    prev_a = prev_o = 0
    for i, b in enumerate(s1.buckets):
        da, do = b["arrived"] - prev_a, b["ok"] - prev_o
        prev_a, prev_o = b["arrived"], b["ok"]
        if i % 2 or i * 2 < 13:
            continue
        print("  %4.0fs %7d %8d %7d    %5.0f%%   %5.0f%%   %5.0f%%     %6.1f%%"
              % (i * 2, b["api_q"], b["svc_q"], b["db_q"], b["api_u"] * 100,
                 b["svc_u"] * 100, b["db_u"] * 100, pct(do, da)))
    print("  结束时仍有 %d 个请求卡在系统里 (api 排队 %d, svc 排队 %d, db 排队 %d)"
          % (len(s1.reqs), len(s1.layers["api"].queue),
             len(s1.layers["svc"].queue), len(s1.layers["db"].queue)))

    print("\n" + "=" * 84)
    print("成功率演化 (每列约 1.15 s; !=DB变慢  S~e=洪峰)")
    print("=" * 84)
    for name, s in res.items():
        print("\n%s" % name)
        for line in chart([100 * r for r in s.rate]):
            print(line)

    print("\n" + "=" * 84)
    print("对比表")
    print("=" * 84)
    head = ("%-10s %7s %8s %8s %8s %8s %8s %8s %8s" %
            ("场景", "成功率", "好请求率", "平均延迟", "P95延迟", "入口放大",
             "积压峰值", "破千时刻", "svc占用"))
    print(head)
    print("-" * len(head))
    for name, s in res.items():
        m = summarize(s)
        t1 = ("%.0f s" % m["q1k"]) if m["q1k"] is not None else "  未破"
        t5 = ("%.0f s" % m["q5k"]) if m["q5k"] is not None else "未破"
        print("%-10s %6.1f%% %7.1f%% %6.0f ms %6.0f ms %7.2fx %8d %8s %7.0f%%"
              % (name, m["ok"], m["good"], m["lat_ms"], m["p95_ms"], m["amp"],
                 m["qmax"], t1, m["svc_u"]))
    print("\n  场景        高优先级成功率  低优先级成功率   db 类成功率   aux 类成功率   积压破五千")
    print("  " + "-" * 76)
    for name, s in res.items():
        m = summarize(s)
        t5 = ("%.0f s" % m["q5k"]) if m["q5k"] is not None else "未破"
        print("  %-10s %12.1f%% %13.1f%% %11.1f%% %12.1f%% %11s"
              % (name, m["hi"], m["lo"], m["db"], m["aux"], t5))
    print("\n注: 好请求率 = 成功且端到端延迟 <= %.0f ms 的比例;  入口放大 = 入口尝试次数/请求数;" % SLO_MS)
    print("    积压 = 卡在入口(api 层)排队等待处理线程的请求数;  破千时刻 = 积压首次超过")
    print("    1000 的时刻(秒), 可用来比较系统'被压垮'的速度。")


if __name__ == "__main__":
    main()

【代码做什么？】

1. 建立三层同步调用链：api（120 个前端处理线程）→ svc（60 个工作线程）→ 下游 db（10 个连接）/ aux（5 个连接）。70% 的请求要走 db，30% 走 aux（模拟”一个有问题的依赖 + 一个健康的依赖”）。
2. 关键建模：上游槽位在整个下游调用期间一直被占住（Layer.busy 是”正在被服务”，Layer.held 是”已服务完本层、但正在等下游”）。这一条是级联失败的全部机理所在——阻塞式调用会把下游的慢，转化为上游的资源耗尽。
3. 注入故障：第 15 秒起 db 的服务时间变成 20 倍（容量从 1000/s 掉到 50/s，而 db 类请求的到达率是 280/s）；第 25–40 秒叠加 6 倍流量洪峰（惊群/突增）。
4. 跑六个场景，每次只加一种机制：S1 无防护（只有库默认的 3 秒超时）→ S2 加无退避重试 → S3 把超时调成 250 ms → S4 加熔断器 → S5 加舱壁隔离 → S6 全防护（+ 指数退避抖动重试 + 重试预算 + 优先级丢弃）。
5. 统计并作图：成功率、好请求率（成功且 ≤100 ms）、平均/P95 延迟、入口放大倍数、下游调用放大倍数、积压峰值、池占用率；每个场景画一张成功率演化 ASCII 曲线，并打印 S1 的逐 2 秒时间线（排队长度 + 各层池占用）。
6. 对比表把所有指标并列，用同一随机种子（random.seed(425)）保证六个场景看到完全相同的请求到达序列，从而差异只来自防护机制本身。

【分布式机制透视】

• 消息传递的模拟：一次”请求”对象在 api → svc → db 之间移动，等价于三段同步 RPC；Layer.queue 就是连接池/线程池的等待队列，Layer.busy 是正在被服务的槽位，Layer.held 是”被阻塞的调用方线程”——真实系统中它就是那个卡在 socket.read() 上的工作线程。
• 并发与时序：整个模拟是离散时间步（每 tick 10 ms），时间推进由 Sim.run() 的循环驱动；请求的到达用泊松过程采样，服务时间用指数分布采样——这正是排队论里 M/M/c 模型的离散化版本。因此观察到的”池占用率 → 100%”与”队列发散”是排队系统的必然结果，而不是编码技巧。
• 分布式系统的对应物：api 池 = Web 服务器的处理线程；svc 池 = 业务逻辑的工作线程池；db/aux 池 = 数据库连接池；”入口排队 11793” = 客户端连上来但拿不到处理线程的请求（真实系统里表现为 LB 队列/accept backlog/客户端超时）。
• 熔断器、舱壁、负载丢弃都被实现为独立的可组合开关，从而可以测量”每一种机制单独贡献了多少”——这在真实系统里是做不到的（你没法在生产上做 A/B 故障实验），正是模拟器的价值。

【与理论的对应】

• 26.3.1 熔断器：class Breaker 逐行对应伪代码的 CLOSED/OPEN/HALF_OPEN 状态机（allow() 对应放行判断与试探配额预留、record() 对应结果回报、tick() 对应冷却到期转半开）。实验验证了引理 1：加了熔断器后，故障依赖的调用被限制为”每 5 秒最多 3 个试探”（熔断快速失败 13971 次调用没有产生任何网络流量），svc 池平均占用率从 76%（S1/S2）降到 56%（S4），健康依赖 aux 的成功率从 16.8%（S1）升到 56.8%（S4）——调用方被保住了。
• 26.3.2 退避 + 抖动 + 预算：S2 使用”失败立刻重试、最多 3 次”，实测 入口放大 1.42 倍、积压峰值 11793 → 15562（+32%）、平均延迟 443 ms → 478 ms，而成功率 16.7% 毫无提升——与讲义 Facebook 案例”没有退避、rinse-n-repeat、数据库被压垮”完全同构。S6 改为”指数退避 + 全抖动 + 重试预算（下游错误率 > 0.9 就不再重试）”，其下游调用放大仅 0.28 倍（S3 为 0.32，见预算的抑制作用）。
• 26.3.3 负载丢弃：S6 在入口积压超阈值时丢弃低优先级请求（优先级丢弃），结果 高优先级成功率 47.8% vs 低优先级 16.4%，而 S5（无丢弃）是 27.9% vs 27.4%——优先级隔离的定量证据。
• 26.3.4 舱壁：S5 把 svc 池按依赖切成 42/18 两个独立池，健康依赖 aux 的成功率从 S3 的 32.2% 升到 52.2%，且 P95 延迟保持在 860 ms（对比 S4 用熔断实现保护时有 4820 ms 的长尾）——资源维度的隔离比时间维度的隔离更”平滑”。
• 26.3.6 可用性：本实验的”成功率/积压/延迟”就是 MTTR 的构件：S1 的 p95 是 2250 ms 且积压破万，S6 的 p95 是 1870 ms 且积压峰值仅 951——同样的故障、同样的容量下，”恢复能力”决定了用户看到的是”灾难”还是”降级”。

运行输出（实际运行结果，节选）

====================================================================================
CS 425 L26 实验 1: 级联失败与六种防护机制
链路 api(120线程) -> svc(60线程) -> db(10连接)/aux(5连接);  入口 400 req/s
t=15s 数据库变慢 20 倍(容量 1000/s -> 50/s);  t=25~40s 六倍流量洪峰
====================================================================================

--- S1 无防护 ---
  成功率 16.7% (9094/54355 次尝试)   好请求率(成功且<=100ms) 12.4%   失败 44154
  平均延迟 443 ms   P95 2250 ms   入口放大 1.00x   下游调用放大 0.17x   熔断快速失败 0
  高优先级成功率 17.0%   低优先级 16.7%   db 类 16.7%   aux 类 16.8%

--- S2 加重试 ---
  成功率 16.7% (9057/54346 次尝试)   好请求率(成功且<=100ms) 12.4%   失败 43552
  平均延迟 478 ms   P95 1770 ms   入口放大 1.42x   下游调用放大 0.17x   熔断快速失败 0
  高优先级成功率 17.2%   低优先级 16.5%   db 类 16.8%   aux 类 16.5%

--- S3 加超时 ---
  成功率 21.5% (11613/54086 次尝试)   好请求率(成功且<=100ms) 16.5%   失败 42355
  平均延迟 146 ms   P95 620 ms   入口放大 1.00x   下游调用放大 0.32x   熔断快速失败 0
  高优先级成功率 21.8%   低优先级 21.4%   db 类 16.8%   aux 类 32.2%

--- S4 加熔断 ---
  成功率 26.8% (14532/54275 次尝试)   好请求率(成功且<=100ms) 16.1%   失败 39731
  平均延迟 404 ms   P95 4820 ms   入口放大 1.00x   下游调用放大 0.31x   熔断快速失败 13971
  高优先级成功率 26.8%   低优先级 26.8%   db 类 13.8%   aux 类 56.8%

--- S5 加舱壁 ---
  成功率 27.5% (14926/54227 次尝试)   好请求率(成功且<=100ms) 22.4%   失败 39218
  平均延迟 280 ms   P95 860 ms   入口放大 1.00x   下游调用放大 0.35x   熔断快速失败 0
  高优先级成功率 27.9%   低优先级 27.4%   db 类 16.9%   aux 类 52.2%

--- S6 全防护 ---
  成功率 22.6% (12170/53826 次尝试)   好请求率(成功且<=100ms) 17.3%   失败 41360
  平均延迟 270 ms   P95 1870 ms   入口放大 1.50x   下游调用放大 0.28x   熔断快速失败 0
  高优先级成功率 47.8%   低优先级 16.4%   db 类 17.0%   aux 类 35.8%

====================================================================================
S1(无防护)时间线 —— 本章最重要的表: 一个依赖变慢如何吃掉调用方的资源
====================================================================================
  时刻  api排队  svc排队  db排队   api占用  svc占用   db占用   该段成功率
    16s     214       60      50      100%     100%     100%       62.9%
    20s    1009       60      47       99%      98%     100%       18.1%
    24s     984       60      50      100%     100%     100%       16.9%
    28s    7033       60      48       98%      97%     100%        3.3%
    32s   11609       60      45       98%      97%     100%        3.5%
    36s   11753       60      50      100%     100%     100%        2.7%
    40s   11762       60      49      100%     100%     100%        3.0%
    44s    3670       60      49       99%      98%     100%       16.7%
    48s     967       60      49      100%     100%     100%       15.8%
    52s     991       60      49      100%     100%     100%       18.8%
    56s     948       60      49       99%      98%     100%       18.6%
    60s     987       60      50      100%     100%     100%       18.8%
  结束时仍有 1107 个请求卡在系统里 (api 排队 987, svc 排队 60, db 排队 50)

====================================================================================
成功率演化 (每列约 1.15 s; !=DB变慢  S~e=洪峰)
====================================================================================

S1 无防护
  100% |  ************                                      
   80% |                                                    
   60% |              **                                    
   40% |**                                                  
   20% |                ******              ****************
    0% |                      **************                
       +----------------------------------------------------
        0            !       S            e                6   ! DB变慢   S~e 洪峰期

S2 加重试
  100% |  ************                                      
   80% |                                                    
   60% |              **                                    
   40% |**                                                  
   20% |                ******              ****************
    0% |                      **************                
       +----------------------------------------------------
        0            !       S            e                6   ! DB变慢   S~e 洪峰期

S3 加超时
  100% |  ************                                      
   80% |                                                    
   60% |              **                                    
   40% |**              ******              *  ***  ** *****
   20% |                      **             **   **  *     
    0% |                        ************                
       +----------------------------------------------------
  ... (S4/S5/S6 的曲线形状: 数据库变慢后先落到 20%~40%, 洪峰期间被压到接近 0%,
       洪峰结束后恢复到约 40%; 完整输出可运行本程序复现) ...

====================================================================================

S1 无防护
  100% |  ************                                      
   80% |                                                    
   60% |              **                                    
   40% |**                                                  
   20% |                ******              ****************
    0% |                      **************                
       +----------------------------------------------------
        0            !       S            e                6   ! DB变慢   S~e 洪峰期

S2 加重试
  100% |  ************                                      
   80% |                                                    
   60% |              **                                    
   40% |**                                                  
   20% |                ******              ****************
    0% |                      **************                
       +----------------------------------------------------
        0            !       S            e                6   ! DB变慢   S~e 洪峰期

S3 加超时
  100% |  ************                                      
   80% |                                                    
   60% |              **                                    
   40% |**              ******              *  ***  ** *****
   20% |                      **             **   **  *     
    0% |                        ************                
       +----------------------------------------------------
        0            !       S            e                6   ! DB变慢   S~e 洪峰期

S4 加熔断
  100% |  ************                                      
   80% |                                    ***             
   60% |              **                       **           
   40% |**              ***  *                   ********** 
   20% |                   ** **  ***** ****               *
    0% |                        **     *                    
       +----------------------------------------------------
        0            !       S            e                6   ! DB变慢   S~e 洪峰期

S5 加舱壁
  100% |  ************                                      
   80% |              **                     **             
   60% |                                    *  **           
   40% |**              ******                   ***********
   20% |                      **                            
    0% |                        ************                
       +----------------------------------------------------
        0            !       S            e                6   ! DB变慢   S~e 洪峰期

S6 全防护
  100% |  ************                                      
   80% |              **                                    
   60% |                                                    
   40% |**               ****                **  ***       *
   20% |                *    ***            *  **   ******* 
    0% |                        ************                
       +----------------------------------------------------
        0            !       S            e                6   ! DB变慢   S~e 洪峰期

====================================================================================
对比表
====================================================================================
场景             成功率     好请求率     平均延迟    P95延迟     入口放大     积压峰值     破千时刻    svc占用
---------------------------------------------------------------------------------
S1 无防护       16.7%    12.4%    443 ms   2250 ms    1.00x    11793     20 s      76%
S2 加重试       16.7%    12.4%    478 ms   1770 ms    1.42x    15562     20 s      76%
S3 加超时       21.5%    16.5%    146 ms    620 ms    1.00x     9881     26 s      73%
S4 加熔断       26.8%    16.1%    404 ms   4820 ms    1.00x     8285     26 s      56%
S5 加舱壁       27.5%    22.4%    280 ms    860 ms    1.00x     9488     26 s      54%
S6 全防护       22.6%    17.3%    270 ms   1870 ms    1.50x      951       未破      54%

  场景        高优先级成功率  低优先级成功率   db 类成功率   aux 类成功率   积压破五千
  ----------------------------------------------------------------------------
  S1 无防护             17.0%          16.7%        16.7%         16.8%        28 s
  S2 加重试             17.2%          16.5%        16.8%         16.5%        28 s
  S3 加超时             21.8%          21.4%        16.8%         32.2%        30 s
  S4 加熔断             26.8%          26.8%        13.8%         56.8%        32 s
  S5 加舱壁             27.9%          27.4%        16.9%         52.2%        30 s
  S6 全防护             47.8%          16.4%        17.0%         35.8%          未破

注: 好请求率 = 成功且端到端延迟 <= 100 ms 的比例;  入口放大 = 入口尝试次数/请求数;
    积压 = 卡在入口(api 层)排队等待处理线程的请求数;  破千时刻 = 积压首次超过
    1000 的时刻(秒), 可用来比较系统'被压垮'的速度。

26.4.2 实验 2：相关性故障与故障域隔离

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""CS 425 Lecture 26 / 代码 2: 相关性故障与故障域感知的副本放置

拓扑(节点编号是机架连续的, 这正是真实数据中心的常见做法):
    3 个可用区(AZ) x 3 个机架(rack) x 3 个节点 = 27 台机器
    每个对象 3 个副本; 多数派 quorum = 2/3
故障事件: 单节点失效 / 单机架失效(3 台) / 单可用区失效(9 台) / 相关性故障(同版本软件或同配置, 27 台全中)
仅使用 Python 标准库; 固定随机种子; 可直接 python3 运行。
"""

import random

TRIALS = 4000
REPLICAS = 3
AZS, RACKS_PER_AZ, NODES_PER_RACK = 3, 3, 3
NODES = AZS * RACKS_PER_AZ * NODES_PER_RACK      # 27


def az_of(node):
    return node // (RACKS_PER_AZ * NODES_PER_RACK)


def rack_of(node):
    return node // NODES_PER_RACK


def place_random():
    return random.sample(range(NODES), REPLICAS)


def place_greedy_index():
    """按索引贪心: 挑编号最小的 3 台机器 —— 编号连续 = 同一机架"""
    return [0, 1, 2]


def place_rack_aware():
    """每个副本放在不同的机架"""
    racks = random.sample(range(AZS * RACKS_PER_AZ), REPLICAS)
    return [r * NODES_PER_RACK + random.randrange(NODES_PER_RACK) for r in racks]


def place_az_aware():
    """每个副本放在不同的可用区"""
    azs = random.sample(range(AZS), REPLICAS)
    return [az * (RACKS_PER_AZ * NODES_PER_RACK) + random.randrange(RACKS_PER_AZ * NODES_PER_RACK)
            for az in azs]


STRATEGIES = [
    ("A 随机放置(无感知)", place_random),
    ("B 索引贪心(0,1,2)", place_greedy_index),
    ("C 机架感知", place_rack_aware),
    ("D 可用区感知", place_az_aware),
]


def rack_failure_nodes(rack):
    return [rack * NODES_PER_RACK + i for i in range(NODES_PER_RACK)]


def az_failure_nodes(az):
    base = az * RACKS_PER_AZ * NODES_PER_RACK
    return list(range(base, base + RACKS_PER_AZ * NODES_PER_RACK))


def evaluate(strategy, event_sets):
    """对"故障位置在故障域内均匀随机"求期望: 平均所有可能的事故位置"""
    hit_q = hit_all = total = 0
    for nodes in event_sets:
        nodes = set(nodes)
        for _ in range(TRIALS):
            reps = strategy()
            hit = sum(1 for r in reps if r in nodes)
            hit_q += 1 if hit >= 2 else 0
            hit_all += 1 if hit == REPLICAS else 0
            total += 1
    return hit_q / total, hit_all / total


def pad(text, width):
    """按显示宽度补空格(中文字符占 2 列)"""
    w = sum(2 if ord(c) > 0x2E80 else 1 for c in text)
    return text + " " * max(0, width - w)


def bar(p, width=28):
    n = int(round(p * width))
    return "#" * n + "." * (width - n)


def main():
    random.seed(425)                 # 固定随机种子, 保证结果可复现
    print("=" * 86)
    print("CS 425 L26 实验 2: 相关性故障与故障域感知的副本放置")
    print("拓扑: 3 个可用区 x 3 个机架 x 3 个节点 = %d 台机器;  每个对象 %d 个副本;"
          % (NODES, REPLICAS))
    print("      多数派 quorum = 2/3;  每次实验 %d 次随机试验" % TRIALS)
    print("=" * 86)

    events = [
        ("单节点失效   (1 台机器)", [[n] for n in range(NODES)]),
        ("单机架失效   (3 台机器)", [rack_failure_nodes(r) for r in range(AZS * RACKS_PER_AZ)]),
        ("单可用区失效 (9 台机器)", [az_failure_nodes(a) for a in range(AZS)]),
        ("相关性故障   (27 台全中)", [list(range(NODES))]),
    ]
    rows = []
    for sname, fn in STRATEGIES:
        for ename, nodes in events:
            q, a = evaluate(fn, nodes)
            rows.append((sname, ename, len(nodes[0]), q, a))

    print("\n" + pad("放置策略", 20) + pad("故障事件", 26)
          + pad("丢多数派", 12) + pad("丢全部副本", 12) + "丢多数派概率")
    print("-" * 100)
    last = None
    for sname, ename, nn, q, a in rows:
        if last is not None and sname != last:
            print("-" * 100)
        last = sname
        print(pad(sname, 20) + pad(ename, 26)
              + pad("%.2f%%" % (q * 100), 12) + pad("%.2f%%" % (a * 100), 12) + bar(q))

    print("\n结论:")
    print("  1. 单节点失效: 任何策略都不会丢多数派(3 个副本本来就在 3 台不同机器上)。")
    print("  2. 索引贪心(副本落在连号的 0/1/2): 一旦失效的正好是那个机架(概率 1/9),")
    print("     3 个副本会全部丢失: 机器编号往往与拓扑相关(同机架连号), '看起来高效'的")
    print("     确定性放置正好把")
    print("     3 个副本塞进同一个故障域。这就是随机放置优于贪心的原因: 随机化把")
    print("     未知的相关性打散, 而贪心的确定性会把未知的相关性放大。")
    print("  3. 机架感知把'单机架失效丢多数派'降为 0, 但一个可用区里有 3 个机架,")
    print("     3 个副本虽落在不同机架、却仍可能有两个同处一个 AZ(概率约 22%), 于是")
    print("     单可用区失效仍可能丢多数派 —— 故障域的层级必须与副本数对齐。")
    print("  4. 只有可用区感知能把'单可用区失效丢多数派'降为 0 —— 故障域的层级必须")
    print("     与副本数对齐: 3 个副本就要有 3 个互不相交的顶层故障域。")
    print("  5. 相关性故障(同一软件 bug、同一次配置推送)对所有放置策略都是 100% 致命:")
    print("     冗余只能对抗'独立'故障, 对抗'相关'故障唯一的手段是多样化(版本/实现异构)。")


if __name__ == "__main__":
    main()

【代码做什么？】

1. 构造一个真实的拓扑：3 个可用区 × 3 个机架 × 3 个节点 = 27 台机器，节点编号按机架连续（node // 3 就是机架号——这正是现实中机柜内连号布线的常见做法）。
2. 实现四种放置策略：随机（无感知）、索引贪心（挑编号最小的 3 台 = 0/1/2）、机架感知（3 个不同机架）、可用区感知（3 个不同 AZ）。
3. 对四类故障事件（单节点 / 单机架 3 台 / 单 AZ 9 台 / 跨全部 27 台的相关性故障），遍历所有可能的故障位置并用 4000 次蒙特卡洛试验求平均，统计”丢掉多数派（≥2 个副本受影响）”与”丢掉全部副本”的概率。
4. 打印概率表与结论。

【分布式机制透视】

• 故障域被显式建模：拓扑的层次（AZ ⊃ 机架 ⊃ 节点）不是装饰，而是”哪些机器会一起挂”的定义。代码把”故障事件”实现为某个域内全部节点的集合，这恰好对应真实的机架断电、交换机重启、AZ 级网络故障。
• quorum 的可用性判据：hit >= 2 就是”多数派丢失”——与 Lecture 17 的 quorum 相交性直接对应：3 副本系统中，只要存活副本 ≥2，读写仍能保证一致性。
• 相关性故障用”事件集合”表示：第四个事件（27 台全中）建模的是”同一软件 bug / 同一次配置推送”，它不尊重任何拓扑边界，因此所有放置策略的结果都是 100%——这就是”相关性故障击穿冗余”的形式化演示。
• 随机化的作用：随机放置不是”随便放”，而是”在信息不完整时把未知相关性转化为均匀分布”；当拓扑信息可用时，用反亲和约束直接表达意图（机架感知/AZ 感知）。

【与理论的对应】

• 26.3.5 定理 1：机架感知在”单机架失效”上把丢多数派概率从随机放置的 2.48% 降到 0.00%，AZ 感知在”单 AZ 失效”上把 24.97% 降到 0.00%——正是”副本分布在 R 个互不相同的顶层故障域 ⇒ 单域失效不丢多数派”的实测。
• 26.3.5 命题（随机优于贪心）：索引贪心在单机架失效下丢多数派概率 11.11%，且这 11.11% 是全部副本一起丢（数据永久丢失），而随机放置只有 2.48%（丢全部副本 0.04%）。原因写在代码注释里：节点编号与故障域相关，贪心把这份未知的相关性放大成了灾难。
• 26.3.5 定理 2（相关性故障）：第四行数据是所有策略的 100%——增加副本数对相关故障毫无帮助，唯一解药是多样化（版本异构、实现异构、供应商异构）与渐进式发布。这一行也是讲义 AWS 2011”13% 的卷同时重镜像”、Facebook”所有缓存服务器同时去查库”的共同数学形态。
• 与 Lecture 22 的呼应：放置只解决”副本在哪里”，数据是否真的没坏还需要端到端校验和（GFS chunk checksum 思想）——放置防的是”物理一起丢”，校验防的是”静默损坏”。

运行输出（实际运行结果）

======================================================================================
CS 425 L26 实验 2: 相关性故障与故障域感知的副本放置
拓扑: 3 个可用区 x 3 个机架 x 3 个节点 = 27 台机器;  每个对象 3 个副本;
      多数派 quorum = 2/3;  每次实验 4000 次随机试验
======================================================================================

放置策略            故障事件                  丢多数派    丢全部副本  丢多数派概率
----------------------------------------------------------------------------------------------------
A 随机放置(无感知)  单节点失效   (1 台机器)   0.00%       0.00%       ............................
A 随机放置(无感知)  单机架失效   (3 台机器)   2.48%       0.04%       #...........................
A 随机放置(无感知)  单可用区失效 (9 台机器)   25.17%      2.74%       #######.....................
A 随机放置(无感知)  相关性故障   (27 台全中)  100.00%     100.00%     ############################
----------------------------------------------------------------------------------------------------
B 索引贪心(0,1,2)   单节点失效   (1 台机器)   0.00%       0.00%       ............................
B 索引贪心(0,1,2)   单机架失效   (3 台机器)   11.11%      11.11%      ###.........................
B 索引贪心(0,1,2)   单可用区失效 (9 台机器)   33.33%      33.33%      #########...................
B 索引贪心(0,1,2)   相关性故障   (27 台全中)  100.00%     100.00%     ############################
----------------------------------------------------------------------------------------------------
C 机架感知          单节点失效   (1 台机器)   0.00%       0.00%       ............................
C 机架感知          单机架失效   (3 台机器)   0.00%       0.00%       ............................
C 机架感知          单可用区失效 (9 台机器)   22.41%      1.16%       ######......................
C 机架感知          相关性故障   (27 台全中)  100.00%     100.00%     ############################
----------------------------------------------------------------------------------------------------
D 可用区感知        单节点失效   (1 台机器)   0.00%       0.00%       ............................
D 可用区感知        单机架失效   (3 台机器)   0.00%       0.00%       ............................
D 可用区感知        单可用区失效 (9 台机器)   0.00%       0.00%       ............................
D 可用区感知        相关性故障   (27 台全中)  100.00%     100.00%     ############################

结论:
  1. 单节点失效: 任何策略都不会丢多数派(3 个副本本来就在 3 台不同机器上)。
  2. 索引贪心(副本落在连号的 0/1/2): 一旦失效的正好是那个机架(概率 1/9),
     3 个副本会全部丢失: 机器编号往往与拓扑相关(同机架连号), '看起来高效'的
     确定性放置正好把
     3 个副本塞进同一个故障域。这就是随机放置优于贪心的原因: 随机化把
     未知的相关性打散, 而贪心的确定性会把未知的相关性放大。
  3. 机架感知把'单机架失效丢多数派'降为 0, 但一个可用区里有 3 个机架,
     3 个副本虽落在不同机架、却仍可能有两个同处一个 AZ(概率约 22%), 于是
     单可用区失效仍可能丢多数派 —— 故障域的层级必须与副本数对齐。
  4. 只有可用区感知能把'单可用区失效丢多数派'降为 0 —— 故障域的层级必须
     与副本数对齐: 3 个副本就要有 3 个互不相交的顶层故障域。
  5. 相关性故障(同一软件 bug、同一次配置推送)对所有放置策略都是 100% 致命:
     冗余只能对抗'独立'故障, 对抗'相关'故障唯一的手段是多样化(版本/实现异构)。

26.4.3 实验 3：可用性数学与 MTTR 敏感性分析

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""CS 425 Lecture 26 / 代码 3: 可用性数学与 MTTR 敏感性分析

    A = MTTF / (MTTF + MTTR)
定量回答: 提高可用性有两条路(提高 MTTF / 降低 MTTR), 为什么工程上通常
"减少恢复时间"更划算? 附带"几个 9"对应的停机时间表与规模效应。
仅使用 Python 标准库; 可直接 python3 运行。
"""

import math

HOURS_PER_YEAR = 365 * 24          # 8760
HOURS_PER_MONTH = 30 * 24          # 720


def availability(mttf_h, mttr_h):
    """A = MTTF / (MTTF + MTTR)"""
    return mttf_h / (mttf_h + mttr_h)


def downtime_hours_per_year(a):
    return (1.0 - a) * HOURS_PER_YEAR


def fmt_downtime(h):
    if h >= 24:
        return "%.2f 天" % (h / 24)
    if h >= 1:
        return "%.2f 小时" % h
    if h * 60 >= 1:
        return "%.2f 分钟" % (h * 60)
    return "%.2f 秒" % (h * 3600)


def mttr_for_target(mttf_h, target):
    """在 MTTF 固定时, 要把可用性做到 target, MTTR 必须是多少?"""
    return mttf_h * (1.0 - target) / target


def mttf_for_target(mttr_h, target):
    """在 MTTR 固定时, 要把可用性做到 target, MTTF 必须是多少?"""
    return mttr_h * target / (1.0 - target)


def nines_str(a):
    """把可用性写成 'N 个 9' 的直观形式"""
    n = -math.log10(max(1e-12, 1.0 - a))
    return "%.4f%%(%.0f个9)" % (a * 100, round(n))


def bar(v, vmax, width=34, ch="#"):
    n = int(round(v / vmax * width))
    return ch * max(0, min(width, n)) + "." * (width - max(0, min(width, n)))


def main():
    print("=" * 84)
    print("CS 425 L26 实验 3: 可用性 = MTTF/(MTTF+MTTR) 与两条改进路径")
    print("=" * 84)

    print("\n[1] '几个 9'对应的停机时间 (按一年 %d 小时 / 一个月 %d 小时计)"
          % (HOURS_PER_YEAR, HOURS_PER_MONTH))
    print("-" * 84)
    print("  可用性      每年停机        每月停机        说明")
    print("  " + "-" * 76)
    notes = {
        0.99: "两个 9: 单机、无自动化故障转移的典型水平",
        0.999: "三个 9: 有冗余但恢复主要靠人工",
        0.9999: "四个 9: 需要自动故障转移 + 严格的变更管理",
        0.99999: "五个 9: 需要多副本 + 秒级自动切换 + 变更零失误",
        0.999999: "六个 9: 只有极少数经过专门设计的系统能做到",
    }
    for target in (0.99, 0.999, 0.9999, 0.99999, 0.999999):
        d = downtime_hours_per_year(target)
        print("  %-12s %-14s %-14s %s"
              % (nines_str(target), fmt_downtime(d), fmt_downtime(d / 12), notes[target]))

    print("\n[2] 可用性对 MTTF / MTTR 的敏感性 (行=MTTF, 列=MTTR)")
    print("-" * 84)
    mttfs, mttrs = [1000.0, 10000.0, 100000.0], [0.1, 1.0, 10.0, 100.0]
    print("  " + "MTTF(h)".ljust(12) + "".join(("MTTR=%gh" % m).ljust(18) for m in mttrs))
    for m in mttfs:
        row = []
        for r in mttrs:
            a = availability(m, r)
            row.append("%.6f%% (%.1fh/y)" % (a * 100, downtime_hours_per_year(a)))
        print("  " + ("%8.0f" % m).ljust(12) + "".join(c.ljust(18) for c in row))

    print("\n[3] 两条路径的等价性: 减少 MTTR k 倍 ≡ 提高 MTTF k 倍")
    print("-" * 84)
    print("  因为 A = 1/(1 + MTTR/MTTF) 只取决于比值 MTTR/MTTF, 所以:")
    print("     把 MTTR 从 R 降到 R/k   ==>   等价于把 MTTF 提高 k 倍。")
    print("  数值例子(MTTF = 10000 小时):")
    mttf0 = 10000.0
    a10 = availability(mttf0, 10.0)
    a1 = availability(mttf0, 1.0)
    need = mttf_for_target(10.0, a1)
    print("     MTTR = 10 h  ->  可用性 %.4f%%  年停机 %s"
          % (a10 * 100, fmt_downtime(downtime_hours_per_year(a10))))
    print("     MTTR =  1 h  ->  可用性 %.4f%%  年停机 %s   (多出一个 9)"
          % (a1 * 100, fmt_downtime(downtime_hours_per_year(a1))))
    print("     若不动 MTTR(=10h), 想把可用性提到 %.4f%%, 需要 MTTF = %.0f h (提高 %.1f 倍)"
          % (a1 * 100, need, need / mttf0))

    print("\n[4] 规模效应: 系统 MTTF ≈ 单机 MTTF / n (讲义中的数据中心实测量级)")
    print("-" * 84)
    per_machine_years = 10.0                       # 一台机器平均 10 年出一次故障
    per_machine_h = per_machine_years * HOURS_PER_YEAR
    print("  单台机器 MTTF = %.0f 年 = %.0f 小时 (即平均每 120 个月出一次故障)"
          % (per_machine_years, per_machine_h))
    print("  机器数       系统 MTTF(平均多久出一次故障)      要做到 99.99% 所需的 MTTR")
    print("  " + "-" * 76)
    for n in (1, 120, 12000, 100000):
        sys_mttf = per_machine_h / n
        need_mttr = mttr_for_target(sys_mttf, 0.9999)
        print("  %-12d %-32s %s"
              % (n, "%.2f 小时" % sys_mttf if sys_mttf < 48 else "%.1f 天" % (sys_mttf / 24),
                 fmt_downtime(need_mttr)))

    print("\n  解读: 规模每扩大 10 倍, 系统 MTTF 就缩短 10 倍, 于是要保持同样的可用性,")
    print("        MTTR 也必须缩短 10 倍 —— 这就是'规模越大越要靠快速恢复'的数学根源。")

    print("\n[5] 从三个 9 到五个 9: 两条路各要付出多少?")
    print("-" * 84)
    for mttf in (10000.0, 1000000.0):
        mttr_now = mttr_for_target(mttf, 0.999)
        mttr_5n = mttr_for_target(mttf, 0.99999)
        print("  MTTF = %-9.0f h: 99.9%%  需要 MTTR = %-10s   99.999%% 需要 MTTR = %-10s  (改善 %.0f 倍)"
              % (mttf, fmt_downtime(mttr_now), fmt_downtime(mttr_5n), mttr_now / mttr_5n))
    print("  同样地, 若把 MTTR 固定在 10 小时, 99.9%% -> 99.999%% 需要把 MTTF 提高 %.0f 倍。"
          % (mttf_for_target(10.0, 0.99999) / mttf_for_target(10.0, 0.999)))

    print("\n[6] 用 ASCII 图看两条路径 (MTTF = 10000 h, 横轴 = MTTR, 对数刻度)")
    print("-" * 84)
    print("   MTTR      可用性        9 的个数")
    for r in (100.0, 30.0, 10.0, 3.0, 1.0, 0.3, 0.1, 0.03):
        a = availability(10000.0, r)
        nines = -math.log10(1.0 - a)
        print("   %6.2f h  %.6f%%   %s  (%.2f 个 9)"
              % (r, a * 100, bar(nines, 6.0, 24), nines))
    print("   说明: 横条长度 = 可用性的'9 的个数'(满格 6 个 9); MTTR 每缩小 10 倍就多约一个 9。")

    print("\n结论:")
    print("  1. 可用性只取决于比值 MTTR/MTTF, 所以两条路在数学上完全对称。")
    print("  2. 但在工程上不对称: MTTF 由硬件与软件质量决定, 在'商品化硬件 + 大规模'")
    print("     的前提下会随规模线性变差(10 万台机器时平均每几分钟就有一台故障);")
    print("     而 MTTR 由设计决定 —— 自动故障转移、快速重启、可回滚的变更、限流与熔断,")
    print("     这些都是可以工程化地把 MTTR 从小时级压到秒级的手段。")
    print("  3. 因此面向恢复的计算(ROC)主张: 追求'永不故障'不现实, 把 MTTR 做小才是")
    print("     提高可用性的主要杠杆; 冗余的作用也正是把'单机 MTTR'换成'系统切换时间'。")


def math_log10(x):
        return math.log10(x)


if __name__ == "__main__":
    main()