Lecture 2: Introduction to Cloud Computing — 云计算与数据中心

目录 · ← l1 · l3 →

Lecture 2: Introduction to Cloud Computing — 云计算与数据中心

讲义对应：CS 425 FA2026 Lecture 2（L2.FA26.txt，38 页）；补充：FA2025 Lecture 2-3（L2-3.FA25.txt）、Grids 专题（L6.b.FA26.txt） 教材对应：Coulouris, Dollimore, Kindberg & Blair, Distributed Systems 5th Ed. Ch. 1（分布式系统特征与设计目标）、Ch. 2（系统模型） 阅读材料：本讲讲义；Lecture 1 中”分布式系统的工作定义”与”典型设计目标”两页；补充阅读 Barroso, Clidaras & Hölzle, The Datacenter as a Computer

2.1 概述

本讲回答一个看似简单的问题：“云到底是什么？” 答案是三层叠加的结构——它既是一段演进史（分时 → 集群 → 网格 → P2P → 云的合流），也是一套资源抽象（按需、池化、计量、弹性的 utility computing），更是一堆用商品化硬件堆起来的物理机架。本讲把这三层串起来，并给出全课程最重要的一个事实前提：在数据中心的规模下，故障是常态而不是例外（12,000 台服务器、单机 10 年一坏，则平均 7.2 小时就有一台机器挂掉）。

这个事实决定了整门课的走向。Lecture 3 之后的所有机制——故障检测与成员管理（Lecture 5-6）、复制与一致性（Lecture 12 之后的系列）、共识（Lecture 15）、调度与资源管理（Lecture 23）——都可以看作对”硬件不可靠、规模巨大、按需计费”这一组约束的回应。本讲还会把”把 VM 放到哪台物理机上”这一调度问题形式化为向量装箱（vector bin packing），并用可运行代码量化 first-fit / best-fit / worst-fit 的差距。

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

2.2.1 云的史前史：分布式系统的六代演进（”A Cloudy History of Time”）

云不是凭空出现的。它站在六代分布式系统的肩膀上，其中分时产业与数据处理产业（1960-70 年代）留下的遗产最多。

 1940          1950         1960        1970           1980          1990          2000         2010s
 |             |            |           |              |             |             |            |
 mainframe     timesharing  data        PC and         cluster       grid          P2P          cloud and
 ENIAC         industry     processing  workstations   (Berkeley     (Globus,      (Gnutella,   datacenters
 ORDVAC        (Multics:    industry    (NOT           NOW,          GriPhyN,      BitTorrent,  (AWS, Azure,
 ILLIAC        "computing   1968 $70M   distributed!)  server farms  OSG,          SETI@home)   GCP, ...)
 vacuum tubes  like a       -> 1978                    e.g. Oceano)  Lambda Rail)
               utility")    $3.15B

逐代的驱动力与”留给云的东西”：

技术趋势的量化（讲义给出的历史倍增周期）：存储容量 12 个月翻倍、网络带宽 9 个月翻倍、CPU 计算能力 18 个月翻倍（最后一条即 Moore 定律的通俗表述）。但要提醒的是，这些趋势并没有无限延续：2005 年前后 Dennard scaling 与频率缩放终止，单核频率不再自动上涨，于是业界转向多核与横向扩展——这恰恰是”用更多廉价机器而不是更快的单机”这一云范式在物理层面被迫成立的原因。

横向对比同样惊人：1985 年美国全国链路大多还是 56 Kbps，今天 Tbps 级骨干已很普遍。用户需求也在爆炸：1990 年生物学家还在跑单分子模拟，今天 CERN 的 LHC 每年产生多个 PB 数据。

集群 / 网格 / 云的三方对比（云的”个性”正是在与集群、网格的差异中定义的，详见 Lecture 6 的 Grids 部分）：

一句话总结这个对比：网格是”把别人的机器借来用”，云是”向一家公司租机器”。Lecture 6 留下了开放问题：Grids/HPC 正在向云收敛吗？（可对比 OpenStack 与 Globus。）

2.2.2 云计算的定义与本质特征（What Exactly IS a Cloud?）

定义与目的：云是一组通过按需、自助、计量方式提供给多租户共享使用的计算与存储资源池，它对外表现为一个可编程的弹性资源接口。讲义用最能记住的一句话概括：Cloud = Lots of storage + compute cycles nearby（把大量存储与算力放在离你很近的地方）。

直观解释（”它是什么？”）：租云就像打车，自建机房就像买车。买车要先付一大笔钱、要买保险、要保养、要停车位，而且车 90% 的时间停在车库里；打车则按里程付费、随叫随到、不用管保养。企业自建服务器要提前数月采购、上架、装系统、配网络，而且资源常年闲置在三成左右；云让你为”实际用到的那一段”付费。更深一层的类比来自 Multics：计算应当成为像电力和自来水一样的公用事业（utility）——你从墙上插座取电，不需要知道发电厂在哪台机组上。

讲义给出的”今天云的四点新东西”：

1. 巨大规模（Massive Scale）。单集群/单公司的机器数量达到数十万台，Facebook 从 2009 年的 3 万台 → 2010 年 6 万台 → 2012 年 18 万台；Microsoft 在 2008 年就有 15 万台（并以每月 1 万台的速度增长，其中 8 万台跑 Bing），2013 年 Cosmos 有 11 万台（4 个站点）；Yahoo! 有 10 万台（切成 4,000 台一个的集群）；AWS EC2 在 2009 年约 4 万台（每台 8 核）；eBay 2012 年 5 万台；HP 2012 年 38 万台分布在 180 个数据中心；Google 在 2011 年约 90 万台，2016 年据传 250 万台。今天各大云厂商已不再公开确切服务器数量，只能估计为全球数百万台量级；Meta 一家就部署了 12.5 万块 H100 GPU。
2. 按需访问（On-demand Access）：pay-as-you-go，无预付承诺，而且任何人都能买到（不再需要 grant 或审批）。
3. 数据密集（Data-intensive Nature）：需求单位从 MB 变成 TB、PB、XB，日常日志、取证数据、Web 数据都属于此类。讲义用”人类的数据麻木”提醒量级感：整个 Wikipedia 压缩后才约 10 GB。
4. 新的云编程范式（New Cloud Programming Paradigms）：MapReduce/Hadoop、NoSQL（Cassandra/MongoDB）等，强调高可编程性与开源生态。

叠加标准定义（补充说明）：业界通常引用 NIST 的五大本质特征，它把”云”与”只是把机器放到别处”区分开来：

机制图解：云的四大新特征会组合出”新的、尚未解决的分布式计算问题”——例如”规模 + 按需”要求调度器在几百毫秒内完成放置决策；”规模 + 数据密集”要求计算尽可能靠近数据；”按需 + 数据密集”要求存储本身是弹性的。讲义的原话是：这几个特征的任意组合都催生了云中全新的分布式计算问题。

关键假设与系统模型：

• 资源是商品化（commodity）异构机器构成的同构逻辑池（物理上型号可能不同，逻辑上通过虚拟化统一）；
• 资源获取是异步、按需、可能失败的（申请 VM 可能因容量不足而被拒绝）；
• 计费模型是线性可加的（时间 × 单价 + 存储量 × 单价），因此系统设计必须把”资源消耗”当成一等公民（见 2.2.10）。

2.2.3 服务模型：SaaS / PaaS / IaaS 与 XaaS 光谱

定义与目的：服务模型回答”谁负责哪一层“。抽象层次越高，用户要管的越少，但可控性也越弱。

直观解释（”它是什么？”）：把云想成餐饮的三种形态。IaaS 是租一间毛坯厨房（灶台、水电都给你，菜谱和买菜你自己来）；PaaS 是租一间备好炉具与调料的中央厨房（你只写菜谱）；SaaS 是直接点外卖（你只管吃）。层级越往上，你让渡的控制权越多，但上手越快。

机制图解：责任分层栈（自下而上，YOU = 租户自负，CP = 云提供商负责）：

+-------+------------------------------------------------------+------+------+------+
| Layer | Component  (bottom -> top)                           | IaaS | PaaS | SaaS |
+-------+------------------------------------------------------+------+------+------+
|   L6  | Application / Data  (business logic, user data)      | YOU  | YOU  |  CP  |
|   L5  | Runtime / Middleware  (JVM, DBMS, MQ, app server)    | YOU  |  CP  |  CP  |
|   L4  | Guest OS  (kernel + system libraries)                | YOU  |  CP  |  CP  |
|   L3  | Virtualization  (hypervisor / container runtime)     |  CP  |  CP  |  CP  |
|   L2  | Servers / Storage / Network  (rack, ToR, Clos, LB)   |  CP  |  CP  |  CP  |
|   L1  | Facility  (building, power, cooling, security)       |  CP  |  CP  |  CP  |
+-------+------------------------------------------------------+------+------+------+

XaaS 光谱与真实例子：

几个来自讲义的补充要点：

• HaaS 不总是好主意，因为安全风险大——裸机上没有 hypervisor 兜底，多租户共享时隔离完全取决于用户自己。IaaS 常被认为包含了 HaaS。
• SaaS 常被认为包含了 SOA（Service Oriented Architecture）——把”服务”作为交付单位的思想在 SaaS 里被推到了极致。
• 价格锚点（讲义口径）：EC2 从约 $0.005/小时 的 t3.nano（2 vCPU、0.5 GiB）到约 $761.904/小时 的 u-p6e（72 块 B200 GPU）；S3 Standard 约 2.3¢/GB-月。同一”云”内部跨 5 个数量级的价差说明”按需”必须配合”按需选择规格”才有意义。

关键假设与系统模型：服务模型并不改变底层分布式系统的故障模型（机器仍会坏），它只改变故障的可见性——IaaS 下 VM 挂了用户要自己重启，SaaS 下用户只感觉到一次请求失败。

2.2.4 部署模型：Public / Private / Hybrid / Community

定义与目的：部署模型回答”这台机器归谁、谁能用“。

直观解释：公有云像共享办公空间（谁付钱谁能进，但每个工位有锁）；私有云像公司自己的办公楼（只有员工能进，往往空置率高）；社区云像几家医院合建的中心实验室（共同出资、共同使用、服务特定群体）；混合云像公司既租共享办公位、又保留自己的总部，把敏感数据放总部、把弹性业务放共享空间。

      OWNED BY ONE ORG          SHARED BY SEVERAL ORGS       OPEN TO ANYONE
   +---------------------+   +-------------------------+   +-------------------+
   |   Private cloud     |   |   Community cloud       |   |   Public cloud    |
   |   (only employees)  |   |  (banks / hospitals /   |   |  (paying customer)|
   |                     |   |   research consortium)  |   |                   |
   +---------------------+   +-------------------------+   +-------------------+
                \                       |                          /
                 \                      |                         /
                  +---------------------+-------------------------+
                  |     Hybrid cloud: unified orchestration         |
                  +-------------------------------------------------+

• Public cloud（公有云）：向任何付费客户提供服务。今天的企业市场份额大致为 AWS 28%、Microsoft Azure 20%、Google Cloud 15%，其余由阿里云、Oracle、IBM、腾讯云等瓜分，此外还出现了边缘云与”新云”。
• Private cloud（私有云）：只对公司员工开放。讲义引用的一个真实收益案例：Sybase 的 CIO Jim Swartz 表示，公司数据中心内部的虚拟服务器私有云自 2006 年起每年节省近 200 万美元，原因是可以在服务器之间共享计算与存储资源。
• Hybrid cloud（混合云）：私有与公有统一编排，通常用于数据分级（敏感数据留在私有侧）。
• Community cloud（社区云）：由若干有共同诉求的组织共同拥有和运营（如银行、医院、科研联合体）。
• 学术云：Emulab（Utah 大学，已故 Jay Lepreau 教授创建，约 500 台服务器，用户可获得 root 权限并自行指定网络拓扑）、CloudLab、Chameleon Cloud（HaaS + OpenStack）——”在真实硬件上造自己的云”的入口。

关键假设与系统模型：公有云下故障域与信任域都跨越了组织边界——你的 VM 与陌生租户共享物理机、机架、交换机和供电；私有云下信任域收敛，但代价是规模小、利用率低、无法享受 economies of scale。

2.2.5 数据中心的层级结构：Region → AZ → Cluster → Rack → Server → VM

定义与目的：单站点云（single-site cloud，即”数据中心”）由计算节点、连接机架的交换机、层次化网络拓扑、后端存储节点、前端/负载均衡器、云控制面与软件服务组成。地理分布的云则把这些站点按故障域组织成树。

直观解释（”它是什么？”）：这是一棵故障域树（failure-domain tree）。树的每一层代表”哪些东西会一起坏”。要记住的不是名字，而是“越往上，一次故障打掉的机器越多”这一单调性——副本必须放在树的不同分支上，否则复制只是浪费空间。

机制图解：

Region  us-east-1                           <- L0 地理区域; 跨州/跨国, 由高容量 WAN 骨干互联
  |
  +-- AZ  us-east-1a                        <- L1 可用区: 独立供电/制冷/网络 -> 被设计为独立故障域
  |     |
  |     +-- Cluster  dc-a1                  <- L2 单站点数据中心 (single-site cloud)
  |     |     |
  |     |     +-- Rack  rack-07             <- L3 机架: 20~40 台服务器 + 1 台 ToR 交换机 + 1 路 PDU
  |     |     |     |
  |     |     |     +-- Server  srv-0731    <- L4 物理机/计算节点: 多核 + 内存 + 本地 SSD/HDD
  |     |     |     |     |
  |     |     |     |     +-- VM  vm-4f2c   <- L5 租户工作单元: VM/Container, 由 hypervisor 隔离
  |     |     |     |     +-- VM  vm-9c11   <- 与 vm-4f2c 同机 -> 多租户共享同一台物理机
  |     |     |     |     +-- ...
  |     |     |     +-- Server  srv-0732
  |     |     |     +-- ...  (20~40 servers/rack)
  |     |     +-- Rack  rack-08
  |     |     +-- ...  (30~80 racks/cluster)
  |     +-- Cluster  dc-a2
  |     +-- ...
  +-- AZ  us-east-1b                        <- 同一 Region 的第二个 AZ: 与 1a 物理隔离 (跨 AZ 复制 = 容灾)
  +-- ...
Region  us-west-2                           <- 另一个 Region: 地理冗余 + 就近接入 (latency)

命名约定：Server → Rack → Datacenter → AZ → Region → Global；AZ 用形如 us-east-1a、us-east-1b 的标识，Region 用 us-east-1，跨区用 us-east / us-west。AZ 被有意设计成独立的故障域——独立的供电、制冷和网络接入，因此”跨 AZ 部署副本”是云上最基本的容灾手段。

单站点内部的三层架构（three-tier architecture）：

              client requests / jobs
                       |
          +------------+------------+
          |  1. Front-end / LB       |          <- 第 1 层 前端: 负载均衡、API 网关, 请求入口
          +------------+------------+
                       |
   +-------------------+--------------------+
   |  2. Compute nodes (grouped into racks) |   <- 第 2 层 计算: 机架内商品化服务器, 跑租户 VM/容器
   |   [rack0]  [rack1]  [rack2]  ...       |   <- 机架间由 ToR -> Agg -> Core 互联
   +-------------------+--------------------+
                       |
          +------------+------------+
          |  3. Backend storage nodes |         <- 第 3 层 存储: 对象存储 / 分布式文件系统 / 块存储
          +-------------------------+
                       |
          [ Cloud control plane ]               <- 跨全部三层的控制面: 供给/调度/监控/认证/计费

云控制面（Cloud Control Plane）是云区别于普通集群的关键：它负责资源供给、调度、监控、认证授权、镜像与配额管理，并且自身必须是一个高可用分布式系统——它自己也会坏，而且是全局性故障源。

关键假设与系统模型：层级越高的故障域，故障越罕见但影响面越大，且相关性故障（correlated failure）占比越高——见 2.2.9。

2.2.6 网络拓扑：ToR 交换机与 fat-tree / Clos

定义与目的：把几万台机器的网络做成”任意两台机器之间的带宽不随规模衰减”的结构。讲义给出的样例拓扑就是 Clos/fat-tree 拓扑。

直观解释（”它是什么？”）：传统树形网络像一棵主干细、枝叶粗的树——越往上越拥堵（超售）。Fat-tree（胖树）则像一棵上下一样粗的树：上行带宽与下行带宽相等，因此称为”胖”。它用一堆便宜的同构交换机拼出等价于大型非阻塞交叉开关（crossbar）的效果——又一个”商品化硬件 + 规模化设计”的范例。

机制图解（k = 4 端口交换机组成的 fat-tree，共 16 台主机）：

    +---+            +---+            +---+            +---+
    | C0|            | C1|            | C2|            | C3|
    +---+            +---+            +---+            +---+
      |                |                |                |
===+==+===+=========+==+===+=========+==+===+=========+==+===+=====
   |      |         |      |         |      |         |      |
 +---+  +---+     +---+  +---+     +---+  +---+     +---+  +---+
 | A0|  | A1|     | A2|  | A3|     | A4|  | A5|     | A6|  | A7|
 +---+  +---+     +---+  +---+     +---+  +---+     +---+  +---+
   |      |         |      |         |      |         |      |
 +---+  +---+     +---+  +---+     +---+  +---+     +---+  +---+
 | E0|  | E1|     | E2|  | E3|     | E4|  | E5|     | E6|  | E7|
 +---+  +---+     +---+  +---+     +---+  +---+     +---+  +---+
  0  1   2  3      4  5   6  7      8  9  10 11     12 13  14 15
 [== Pod 0 ==]    [== Pod 1 ==]    [== Pod 2 ==]    [== Pod 3 ==]

图中 ===+=== 那一条代表核心层与汇聚层之间的全互联二分图（Clos 交叉开关）：每台 Core 交换机的 k 个端口分别下连到 k 个 Pod 中各一台 Agg，而不是一条共享总线。

k 元 fat-tree 的精确参数（C = Core，A = Aggregation，E = Edge/ToR）：

代入 $k=48$（当时最常见的商品化交换机端口数）：$576$ 台 Core、$1{,}152$ 台 Agg、$1{,}152$ 台 Edge，共 $2{,}880$ 台交换机即可支撑 $48^3/4 = 27{,}648$ 台主机（补充说明：这组数字来自 fat-tree 的原始设计论文，讲义只给出”Clos/fat-tree”这一结论）。对比传统”接入-汇聚-核心”树形网络的典型 5:1 到 20:1 超售比，fat-tree 让跨 Pod 通信不再成为瓶颈——这对 MapReduce 这类”全集群随机打散”的负载至关重要。

关键假设与系统模型：拓扑假设同构交换机 + 等成本多路径；一旦核心层或某台 Agg 故障，容量按比例下降而非完全中断——故障的影响是容量降级而非分区。

2.2.7 电力、冷却与商品化硬件：PUE / WUE

定义与目的：数据中心的成本与可靠性有很大一部分不在服务器里，而在供电与制冷上。

直观解释：把数据中心想成一台巨大的电暖器——你花 1 度电算数据，还要额外花一部分电把算数据产生的热搬走。PUE 就是”为计算付的电费倍率”。

机制图解与关键公式：

   Off-site power                       On-site power
   (utility grid contract)              (UPS battery + diesel genset + switchgear)
        |                                     |
        +----------------> [ PDU / bus ] <---+
                                 |
                    +------------+------------+
                    |    IT equipment         |   <- 服务器、交换机、存储 (公式分子)
                    |    (in the numerator)   |
                    +------------+------------+
                                 |
      cooling loop: hot air drawn from the top -> water purified -> mist sprayed
                    into the air -> evaporative cooling (15 fan motors per bank)

两者都是越低越好。PUE 的理论下限是 1.0（所有电都进了 IT 设备），讲义给出的标杆值是 Google ≈ 1.1；WUE 衡量每消耗 1 kWh 的 IT 电能要蒸发多少升水。

关键假设与系统模型：工程约束会反向决定系统设计——(1) 电费与制冷是运营成本的固定大头，所以提高单机利用率就是省钱（催生了 2.2.8 的 overcommit 与 2.4 的装箱）；(2) 制冷与供电故障是整机架/整 AZ 级别的相关故障，属于最高等级的故障域；(3) 离线批处理作业可被调度到电价低的时段或 Region。

2.2.8 虚拟化：Hypervisor、VM vs Container、Live Migration 与 Overcommit

定义与目的：虚拟化是 IaaS 的实现手段：把一台物理机切分成多个互相隔离的执行环境，从而 (1) 支持多租户（multi-tenancy）共享；(2) 提供资源隔离与配额；(3) 允许弹性伸缩与在线迁移。

直观解释（”它是什么？”）：hypervisor 就像一栋公寓的二房东——房东（物理硬件）只有一栋楼，二房东把它隔成许多间独立公寓（VM），每户有自己的门锁（隔离）、水表电表（配额），互不干扰；某户搬走时，二房东可以把整间公寓连同家具一起搬到另一栋楼（live migration）。容器则更像一栋大房子里的合租室友：共用同一套水电管线（宿主内核），靠门牌号和规矩（namespace + cgroups）区分彼此——更轻更快，但一旦有人撬开承重墙（内核漏洞），所有人都受影响。

机制图解（Type 1 vs Type 2 hypervisor）：

   Type 1 (bare-metal)                 Type 2 (hosted)
   +---------------------+             +---------------------+
   | Guest VM | Guest VM |             | Guest VM | Guest VM |
   |  App+OS  |  App+OS  |             |  App+OS  |  App+OS  |
   +---------------------+             +---------------------+
   |   Hypervisor (VMM)  |             |   Hypervisor (VMM)  |
   +---------------------+             +---------------------+
   |      Hardware       |             |  Host OS (Linux/Win)|
   +---------------------+             +---------------------+
                                       |      Hardware       |
                                       +---------------------+
   e.g. Xen, ESXi, Hyper-V, KVM        e.g. VirtualBox, VMware Workstation
   (KVM 以 Linux 内核模块形式实现, 语义上接近 Type 1)

VM 与 Container 的详细对比：

Live Migration（在线迁移）是实现弹性的关键机制。pre-copy 的做法是：

1. 把源 VM 的内存页全量拷贝到目标机；
2. 源 VM 继续运行，hypervisor 用脏页位图（dirty page bitmap）跟踪被写过的页；
3. 迭代地把脏页增量拷过去，直到”剩余脏页集合能在给定停机窗口内拷完”；
4. 短暂停机（stop-and-copy）：暂停源 VM、拷完最后一批脏页与 CPU 状态、在目标机恢复运行。 若脏页产生速率持续高于拷贝速率（写密集负载），则退化为 post-copy（先传 CPU 状态并立即在目标机运行，缺页时按需从源机拉取），代价是源机在迁移完成前不能释放资源。

Overcommit（超卖）：物理机上的 vCPU 总量可以大于物理核数（例如 4:1），内存也可以通过 ballooning（气球驱动回收 guest 空闲页）、页共享（KSM）与 swap 来超额分配。这既是提高利用率、降低成本的核心手段，也是尾延迟（tail latency）爆炸的根源——所有租户同时忙碌时，vCPU 排队，p99 延迟飙升。因此真实系统必须为不同 SLA 等级的租户设置不同的 overcommit 比例与 QoS 上限。

关键假设与系统模型：虚拟化把”物理机故障”转化为”VM 故障 + 可在别处重启”，但不消除故障，只是把恢复从”换硬件（数小时到数周）”变为”重新放置（数秒到数分钟）”。这正是云容错设计的基本杠杆。

2.2.9 商品化硬件 + 大规模：故障从”例外”变成”常态”

这是本讲最重要的一节，也是整门课所有容错技术的动机来源。

定义与目的：用商品化（commodity）硬件换取低成本，用大规模冗余 + 快速恢复换取可靠性——即”规模出可靠性（reliability through scale）“。代价是：单机故障从罕见事件变成持续发生的背景噪声。

直观解释（”它是什么？”）：一个 10 年一坏的零件，放进 12,000 台的集群里，就变成平均 7.2 小时坏一台。这不是”可靠性变差了”，而是“故障率被放大了 12,000 倍”——即使每台机器都很好，群体层面也一定会持续有机器在坏。就像一座 1,200 万人口的城市，即使人均寿命 80 岁，每天也一定会有人去世。

机制图解与讲义给出的定量模型：

    假设: 单台机器 (OS / 磁盘 / 主板 / 网络等) 平均每 10 年 = 120 个月故障一次

    机器数        计算                 集群 MTTF (下一次机器故障的平均间隔)
    ----------    -----------------    --------------------------------------
           120    120 / 120          =  1 个月
         1,200    120 / 1,200        =  0.1 个月  = 3 天
        12,000    120 / 12,000       =  0.01 个月 = 7.2 小时    <-- 讲义给出的数字
       900,000    120 / 900,000      =  0.000133 个月 = 5.8 分钟 => 每天约 246 台

    ----------------------------------------------------------------------
    讲义强调: 软崩溃与软故障 (soft crashes / fail-recover) 比这还要频繁!

再把磁盘单独算一遍：若一台机器有 8 块盘、单盘年故障率（AFR）取业界常见的 2%（补充说明：该 AFR 量级来自业界公开的硬盘故障统计，讲义只给出了”整机 10 年一坏”这一前提），则 12,000 台机器共有 96,000 块盘，每年约 1,920 次盘故障 = 每天约 5.3 次，相当于每 4.5 小时坏一块盘。

规模带来的五类挑战：

为什么”相关故障”比独立故障危险得多？ 若 3 副本落在 3 个独立故障域，单机年故障率 1% 时同一数据块在一年内 3 副本全失的概率约为 $0.01^3 = 10^{-6}$ 量级。但如果 3 个”副本”其实在同一个机架、共享同一台 ToR 和同一条 PDU，它们的失效就退化为一个事件：故障概率不是 $10^{-6}$，而是与单点相同的 1%。这就是”复制不等于容错，复制到不同故障域才等于容错“的严格含义，也是 2.2.5 中那棵故障域树存在的理由。

关键假设与系统模型：故障模型通常是 crash-stop（或 crash-recover）而非 Byzantine——机器不会”说谎”，只会停止响应。Lecture 1 已经指出：无响应可能来自网络组件故障、路径中断或计算机崩溃，三者从外部不可区分，这是分布式系统故障检测的根本困难（Lecture 5-6 展开）。

2.2.10 云的经济学：Economies of Scale、按需付费与成本取舍

定义与目的：经济学不只是”多少钱”，它直接决定系统设计（讲义的措辞是：Cloud economics dictates system design）。

直观解释：云提供商的优势来自规模经济（economies of scale）：大规模采购的硬件折扣、把 PUE 压到 1.1 的定制机房、自研服务器与网络设备、统一的自动化运维（1 admin / 100 机器）、把上百万台机器的利用率摊薄——即使加上云厂商的利润，单位算力价格仍可能低于自建。

机制图解（盈亏平衡分析）：讲义给了一个中等规模组织的实例：要跑一个服务 M 个月，需要 128 台服务器（1024 核）和 524 TB 存储（规模与 UIUC 2009 年购置的 CCT 云站点相同，现已退役）。

• 外包（AWS，2009 年价格）：存储 $0.12/GB-月，算力 $0.10/CPU-小时 \(\text{存储} = 0.12 \times 524 \times 1000 \approx \$62\\text{K},\\qquad \\text{总计} = 62\\text{K} + 0.10 \\times 1024 \\times 24 \\times 30 \\approx \\$136\text{K} \text{（每月）}\)
• 自建：存储约 $\$349\text{K}/M$；总计约 $$1{,}555\text{K}/M + 7.5\text{K}$（含每 100 节点 1 名系统管理员），采用硬件:电力:网络 = 0.45:0.4:0.15 的成本结构与 3 年硬件折旧期。

  monthly cost
   (USD K)
   300 |
   250 |       *
   200 |            *
   150 |.................*.......................................  136K/month (Outsource)
   100 |                      *    *    *
    50 |                                     *    *
       +-----------------------------------------------------> M (months)
              6    9    12   15   18   21   24   27
                        ^
                        breakeven M ~ 12 months
  * = 自建 (Own): y = 1555K/M + 7.5K   . = 外包 (Outsource): y = 136K (flat)

• 存储维度：$349\text{K}/M < 62\text{K}$ → $M > 5.55$ 个月
• 整体维度：$1555\text{K}/M + 7.5\text{K} < 136\text{K}$ → $M > 12$ 个月

结论：租期/规模越长越大，越应该自建；越短越小，越应该上云——这就是”创业公司大量使用云”和”云提供商最赚钱的业务其实是存储”这两个现象的由来。

真实收益案例（讲义引用）：

• Eli Lilly 的 Dave Power：内部部署一台服务器原本要 7.5 周，用 AWS 3 分钟；64 节点 Linux 集群从 3 个月缩短到 5 分钟。
• GlaxoSmithKline 的 Ingo Elfering：IT 运营成本降低约 30%。
• 硅谷数百家创业公司无需自购机器即可获得大规模算力。

市场规模的量级感：Forrester 在 2010 年预测市场会从 407 亿美元（2010）增长到 2,410 亿美元（2020）。今天（Grand View Research 报告，讲义引用）：2025 年约 9,436 亿美元，2026 年预计 1.1 万亿美元，2033 年预计 3.34 万亿美元（CAGR 约 16.0%）——实际增速远超当年的预测。

经济学如何”倒逼”系统设计（讲义给出的两个例子）：

1. 把小写入批量合并后再写 S3——因为按请求数计费时，1000 次 1 KB 的 PUT 比 1 次 1 MB 的 PUT 贵得多；
2. 用 S3 做容错，而不是在应用层自己复制——因为存储的每 GB-月单价远低于维持副本服务器的成本，”用存储换可靠性”在云上比”用计算换可靠性”便宜。

关键假设与系统模型：按需付费把”容量规划”转成了”定价模型优化”。但 elasticity 不等于免费：弹性只对无状态、可快速启动、流量可预测的负载有效；有状态服务扩容要迁移数据，缩容要处理数据保留——这就是 over-provisioning（为峰值预留）与 elasticity（按需伸缩）之间的核心取舍。

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

本讲没有给出命名算法，但”把 VM 放到哪台物理机上”可以严格形式化为向量装箱（Vector Bin Packing, VBP）。下面给出离线的 FFD 与在线的准入控制两个算法。

算法 2.3.1：首次适应递减（First-Fit Decreasing, FFD）向量装箱

假设与系统模型

• 同步/离线：所有 VM 的需求在调度前已知（离线装箱）；调度器拥有全部物理机的容量视图。
• 故障模型：本算法不处理故障（无崩溃）；作为上层机制的一次”快照决策”。
• 资源维度：$d = 2$（CPU 与内存），物理机容量向量 $C = (C_{cpu}, C_{mem})$，第 $i$ 个 VM 的需求向量 $r_i = (r_{i,cpu}, r_{i,mem})$。
• 通道假设：集中式，无消息丢失问题。
• 规模：$n$ 台 VM，$m$ 台物理机。

伪代码

Input : VM 集合 V = {v_1, ..., v_n}, 每台需求 r_i; 物理机容量 C
Output: 放置方案 place: V -> PM, 以及使用的物理机集合 P

1  // 归一化负载 (标量化键): 用"各维占用比例之和"作为排序键
2  for each v_i in V:
3      key(v_i) <- r_i.cpu / C.cpu + r_i.mem / C.mem
4  sort V in decreasing order of key              // "Decreasing" 步
5  P <- empty list                                // 已打开的物理机, 按打开顺序编号
6  for each v_i in V:                             // 按降序逐个放置
7      target <- NULL
8      for each p in P:                           // "First-Fit" 步: 第一个装得下的
9          if p.free_cpu >= r_i.cpu and p.free_mem >= r_i.mem then
10             target <- p ; break
11     if target = NULL then                      // 没有现成机器可用
12         target <- new PM(|P|)                  // 打开一台新物理机
13         append target to P
14     place[i] <- target                         // 提交放置
15     target.free_cpu <- target.free_cpu - r_i.cpu
16     target.free_mem <- target.free_mem - r_i.mem
17 return (place, P)

算法逻辑解说

走一个具体的数值小例子。物理机容量 $C=(8, 32)$（8 vCPU、32 GiB）；4 台 VM 的需求为 $v_1=(4,4)$、$v_2=(6,4)$、$v_3=(4,24)$、$v_4=(2,8)$。

50 归一化键：$key(v_1)=4/8+4/32=0.625$，$key(v_2)=0.875$，$key(v_3)=0.5+0.75=1.25$，$key(v_4)=0.25+0.25=0.5$。降序为 $v_3, v_2, v_1, v_4$。

51 放置过程：$v_3$ 放不下任何已开机（$P$ 为空）→ 开 PM0，PM0 剩 $(4,8)$；$v_2$ 需求 $(6,4)$ 放不进 PM0（CPU 不够）→ 开 PM1，PM1 剩 $(2,28)$；$v_1$ 需求 $(4,4)$ 放不进 PM0（CPU 只剩 4，恰好放得下！）→ 放在 PM0，PM0 剩 $(0,4)$；$v_4$ 需求 $(2,8)$：PM0 的 CPU 已满，PM1 剩 $(2,28)$ 恰好放得下 → 放在 PM1。

52 结果：用 2 台物理机，PM0 = $\{v_3, v_1\}$（CPU 8/8，内存 28/32），PM1 = $\{v_2, v_4\}$（CPU 8/8，内存 12/32）。容量下界是 $\lceil 16/8 \rceil = 2$，所以这是最优解。

53 注意 PM1 的内存利用率只有 37.5%——这就是后面 2.4 代码里要量化的“搁浅资源”（stranding）：CPU 已满导致剩余的 20 GiB 内存永远无法被利用。

正确性论证

• 安全性 Safety（容量不变量不被破坏）：算法只在第 9 行两个维度都满足时才把 $v_i$ 放入 $p$，并在第 15-16 行立即扣减可用量；第 12 行新建物理机的容量为满，也必然满足 $r_i \le C$（否则任何方案都不可行，应触发准入拒绝）。由于每个 $v_i$ 只被提交一次（第 6 行的循环遍历 $V$ 恰好一次），归纳可得：任意时刻任意物理机上所有 VM 的需求之和不超过其容量。
• 安全性（放置合法性）：每个 $v_i$ 恰好被赋一个物理机（第 14 行），无重复放置、无遗漏。依赖假设：$V$ 是集合而非多重集。
• 活性 Liveness（必然终止且全部放置）：外层循环执行 $n$ 次（有限集合 $V$）；内层循环最多 $\vert P\vert \le n$ 次；第 12 行保证”最坏情况总能开一台新物理机”，因此 target 永远不为 NULL，不会出现无法放置的死循环。故算法在 $O(n^2)$ 次迭代内终止，且所有 $n$ 台 VM 都被放置（假设单台 VM 的需求不超过单台物理机容量——这个假设必须显式成立，否则第 12 行会创建一个装不下的物理机，安全性与活性同时失效）。
• 近似比（这是算法质量的保证，不是正确性）：FFD 的紧确界是

即 FFD 使用的物理机数不超过最优解的约 1.222 倍再加一个常数（该紧确界由 Dósa 证明，见 Tight absolute bound for First Fit Decreasing bin-packing）。推理链：FFD 把每个”大项”（$> C/2$）单独成箱并两两配对，配对失败时新开箱；剩下的”小项”用 First Fit 填充既有的空隙，通过计数论证可以证明小项需要的箱子数不超过大项箱子数的 $1/9$ 量级……这个论证的关键依赖是一维性：只有在一维下”大项”才构成全序，”配对”才可数。多维情况下该证明完全失效——这正是 2.4 代码要演示的反例。

• 最优性的下界（为什么不能做得更好）：向量装箱是 NP-hard（见 2.5），并且任何多项式时间近似算法都不可能达到优于 $3/2$ 的近似比，除非 P = NP。推理链：取 Partition 问题实例 $\{a_1,\dots,a_n\}$，令 $\sum a_i = 2B$，构造容量为 $B$ 的箱子与大小为 $a_i$ 的项，则”存在 2 个箱子的装箱方案”$\iff$”存在和为 $B$ 的子集划分”。若 OPT = 2 则该实例答案为 YES，若 OPT = 3 则为 NO，两者比值 $3/2$。因此 $(3/2-\epsilon)$-近似算法将能在多项式时间内判定 Partition，而 Partition 是 NP-complete。故 $3/2$ 是多项式近似的天然屏障。

复杂度

• 时间：键计算与排序 $O(n \log n)$；放置阶段最坏 $O(n \cdot m) \le O(n^2)$；总计 $O(n^2)$（实践中因 $m \ll n$、且 first-fit 的线性扫描常提前 break 而接近 $O(n \log n + n\bar{k})$，$\bar{k}$ 是平均扫描的机器数）。
• 空间：$O(n + m)$（存需求向量与每台机器的剩余容量）。
• 消息复杂度：$O(1)$（集中式离线算法，无消息）。

算法 2.3.2：在线放置 + 准入控制 + 迁移合并（两阶段）

假设与系统模型

• 异步：VM 到达/离开的时间不可预知，调度器不能等待”看到全部需求”。
• 故障模型：物理机 crash-stop（心跳超时即判死）；VM 可能因抢占而被杀（fail-stop 后可在别处重启）。
• 通道假设：调度器与每台物理机之间是可靠但可能延迟的消息通道；心跳可能丢失，因此”超时”只是怀疑而非确定（Lecture 5-6 主题）。
• 进程数：1 个全局调度器（RM）、$m$ 台物理机（NM），$n$ 个 VM 请求。
• 约束：每台 VM 有需求向量 $r_i$ 与租户标识；同一租户的 VM 不互相反亲和，不同副本必须落在不同故障域（反亲和集合 $A_i$）。

伪代码

State at Scheduler (RM):
    PM[1..m]      // 每台: free_cpu, free_mem, alive, domain_id, vms
    pending       // 等待资源的 VM 请求队列 (按优先级排序)
    epoch[1..m]   // 每台机器的心跳代次

upon event <Request, vm_i> from tenant T:
    if forall p in alive(PM): not fits(p, vm_i) then
        if priority(vm_i) is low and exists running vm_j of lower priority then
            send <Preempt, vm_j> to host(vm_j)          // 抢占低优先级作业
            push vm_j into pending
            goto RETRY
        else
            send <Reject, vm_i, reason="no capacity"> to T
            return
RETRY:
    candidates <- { p in alive(PM) :
                    fits(p, vm_i)
                    and domain_id(p) not in A_i
                    and score(p, vm_i) is minimal }
    if candidates is empty then
        push vm_i into pending ; return
    p* <- the candidate with minimal score              // score = 剩余容量 / 亲和罚分 / 能耗罚分
    send <Start, vm_i> to p*
    reserve(p*, vm_i)                                   // 先预留, 收到 ACK 才真正扣减
    epoch[vm_i] <- current_epoch

upon event <StartAck, vm_i, p*> from p*:
    commit(p*, vm_i)                                    // 确认后提交, 防止"预留泄漏"
    remove vm_i from pending

upon event <NodeFailure, p_f> from detector:            // 心跳超时 -> 仅"怀疑"
    mark p_f as suspected ; start suspicion timer
upon event <SuspicionTimeout, p_f>:
    mark p_f as dead ; alive(PM) <- alive(PM) \ {p_f}
    for each vm_i on p_f:
        push vm_i into pending                          // 重新进入调度队列 (FIFO 保序)
    trigger Consolidate()

upon event <Heartbeat, p, e> from p:
    if e > epoch[p] then epoch[p] <- e ; mark p alive   // 代次回退的旧心跳被丢弃

procedure Consolidate():                                // 用 live migration 回收碎片化的机器
    loop:
        used <- [p in alive(PM) if p.vms is not empty]
        sort used by (cpu_used/C_cpu + mem_used/C_mem) ascending
        for victim in used:
            moves <- []
            for vm_i in victim.vms:
                dst <- first p in used \ {victim} with fits(p, vm_i) and domain ok
                if dst = NULL then rollback(moves) ; continue with next victim
                migrate(vm_i, victim -> dst)            // pre-copy + 短暂停机
                moves.append((vm_i, dst))
            if victim.vms is empty then
                shut_down(victim) ; freed <- freed + 1 ; continue loop
        return                                          // 没有可回收的机器

算法逻辑解说

请求路径：租户提交 $vm_i$ → 调度器先尝试在存活机器里找一个满足容量与反亲和约束、且打分最小的机器；找不到就尝试抢占一个低优先级的运行中 VM（这就是”抢占”，见 2.5），或者把请求放入 pending 队列（延迟放置）而不是立刻拒绝——延迟放置让系统能够吸收突发流量，是”弹性”的实现方式。找到机器后先预留，收到 StartAck 才提交，避免”调度器以为成功、机器其实没起来”造成容量泄漏。

故障路径：心跳超时只把机器标记为怀疑（suspected）并启动计时器；只有计时器过期才判定为死亡。这个”怀疑 + 计时器”的两段式设计是为了避免误判（false positive）——网络拥塞导致心跳迟到，若立刻判死就会引发不必要的迁移风暴。判定死亡后，该机上所有 VM 重新进入 pending 队列，由调度器在别处重建。

整理路径：Consolidate() 反复尝试把负载最低的物理机上的 VM 全部迁走，成功后关闭该机器。这是”churn 之后必须整理”的机制：租户退租后机器会变得碎片化（每台都半满），此时虽然”利用率”看起来很低，但机器数并没有减少，成本也没有下降。

正确性论证

• 安全性 Safety 1（不超卖）：reserve() 在调度器侧扣减可用量，commit() 与 rollback() 成对出现，且 Start 消息在 p* 上还会被 fits() 二次校验（乐观并发中的”校验-提交”）。因此任何时刻 $\sum_{vm \in p} r_{vm} \le C_p$。依赖假设：预留有超时；否则预留泄漏会让容量永久不可用（这是真实系统的经典 bug）。
• 安全性 Safety 2（反亲和约束）：候选过滤条件显式排除了 domain_id(p) in A_i 的机器。因此同一反亲和组的 VM 不会落在同一故障域。注意：这个不变量只在”放置时”成立；若故障域拓扑发生变化（例如某台 ToR 被替换后 AZ 划分改变），必须重新校验，否则不变量被静默破坏。
• 安全性 Safety 3（不重复运行）：判定 $p_f$ 死亡后，其上的 VM 被重新放置——如果 $p_f$ 其实没死（误判为死），同一 VM 可能同时在新旧两台机器上运行（脑裂）。防护手段是 fencing：新实例启动前，调度器必须先确保旧实例无法继续写共享资源（撤销租约、递增 epoch、让存储层拒绝旧 epoch 的写）。这是纯粹的分布式系统问题，无法靠单机机制解决。
• 活性 Liveness 1（被接受的请求最终运行）：pending 队列是 FIFO（或优先级队列且严格有序），每次有资源释放或 Consolidate 成功，都会重新扫描 pending；且算法保证只要存在”所有需求都不超过单机容量”的 VM，就能通过开新机（保留容量）来满足。依赖假设：容量最终会被释放（VM 会终止）；若租户持续提交且不退租，则 pending 无限增长——此时正确的行为是拒绝并告知，而不是无限等待。故活性必须表述为”要么最终运行，要么最终被显式拒绝“。
• 活性 Liveness 2（Consolidate 终止）：每一次成功迁移都会把一台机器的 VM 数变为 0 并关闭它（机器总数严格减少）；每一次失败回滚都会把系统恢复到迁移前的状态。由于机器数有下界（至少 1 台），算法最多执行 $m$ 轮，必然终止。

复杂度

• 一次放置决策：朴素扫描 $O(m)$；用按剩余容量索引的结构（如 bin-ordered list、平衡树）可降到 $O(\log m + k)$（$k$ 为候选数）。
• 抢占：需要找到”可被抢占的最低优先级 VM”，复杂度 $O(n)$ 或 $O(\log n)$（按优先级堆）。
• Consolidate：每轮 $O(m \cdot \bar{v})$（$\bar{v}$ 为每台机器平均 VM 数），最坏 $O(m^2 \bar v)$；每次迁移的网络开销是 $\Theta(\text{VM 内存大小} \times \text{脏页率} \times \text{迭代次数})$。
• 消息复杂度：每机每心跳周期 1 条心跳，共 $O(m)$/周期；每次迁移至少 2 条控制消息 + 全量内存传输。

2.4 代码示例与分布式实现

#!/usr/bin/env python3
"""CS 425 Lecture 2: 数据中心 VM 放置模拟器 (vector bin packing)。
对比 first/best/worst-fit 及 decreasing 版本, 输出机器数/利用率/碎片/搁浅资源,
再用 churn + 热迁移合并回收。仅标准库, 可直接运行。"""
import random
from dataclasses import dataclass, field

PM_CPU, PM_MEM = 64, 256                      # 单台物理机容量: 64 vCPU / 256 GiB


@dataclass
class VM:
    vid: int
    cpu: int
    mem: int
    tenant: str = "t0"


@dataclass
class PM:
    pid: int
    cpu_cap: int = PM_CPU
    mem_cap: int = PM_MEM
    vms: list = field(default_factory=list)
    cpu_used: int = 0
    mem_used: int = 0

    def fits(self, vm):                       # 二维容量约束: 两维都不能越界
        return self.cpu_used + vm.cpu <= self.cpu_cap and self.mem_used + vm.mem <= self.mem_cap

    def place(self, vm):
        assert self.fits(vm), "capacity invariant violated"
        self.vms.append(vm); self.cpu_used += vm.cpu; self.mem_used += vm.mem

    def evict(self, vm):
        self.vms.remove(vm); self.cpu_used -= vm.cpu; self.mem_used -= vm.mem

    def free_cpu(self): return self.cpu_cap - self.cpu_used
    def free_mem(self): return self.mem_cap - self.mem_used

    def stranded(self):                       # 一维已满 -> 另一维剩余容量被"搁浅"
        return (self.free_cpu() if self.free_mem() == 0 else 0,
                self.free_mem() if self.free_cpu() == 0 else 0)


def place_all(vms, strategy):
    """strategy: first_fit | best_fit | worst_fit | first_fit_dec | best_fit_dec"""
    offline, base = strategy.endswith("_dec"), strategy.replace("_dec", "")
    order = sorted(vms, key=lambda v: -(v.cpu / PM_CPU + v.mem / PM_MEM)) if offline else vms
    pms = []
    for vm in order:                          # VM 逐台到达即决定归属 (在线风格)
        target, best = None, None
        for pm in pms:
            if not pm.fits(vm):
                continue
            resid = (pm.free_cpu() - vm.cpu) / PM_CPU + (pm.free_mem() - vm.mem) / PM_MEM
            if base == "first_fit":
                target = pm; break
            key = resid if base == "best_fit" else -resid
            if best is None or key < best:
                target, best = pm, key
        if target is None:                    # 现有机器都放不下 -> 开新机 (elasticity)
            target = PM(len(pms)); pms.append(target)
        target.place(vm)
    return pms


def consolidate(pms, rounds=300):
    """反复用 live migration 腾空最空的物理机, 返回被下线 (关闭) 的台数。"""
    freed = 0
    for _ in range(rounds):
        used = sorted([p for p in pms if p.vms],
                      key=lambda p: p.cpu_used / PM_CPU + p.mem_used / PM_MEM)
        if len(used) < 2:
            break
        done = False
        for victim in used:
            others, moves = [p for p in used if p is not victim], []
            for vm in list(victim.vms):
                dst = next((p for p in others if p.fits(vm)), None)
                if dst is None:
                    break
                victim.evict(vm); dst.place(vm); moves.append((dst, vm))
            if not victim.vms:                # 腾空成功: 关机省电 / 退租省钱
                pms.remove(victim); freed += 1; done = True; break
            for dst, vm in moves:             # 腾空失败则回滚, 绝不丢 VM
                dst.evict(vm); victim.place(vm)
        if not done:
            break
    return freed

def metrics(pms):
    used = [p for p in pms if p.vms]; n = len(used)
    cu = sum(p.cpu_used for p in used) / (n * PM_CPU)
    mu = sum(p.mem_used for p in used) / (n * PM_MEM)
    sc, sm = sum(p.stranded()[0] for p in used), sum(p.stranded()[1] for p in used)
    return dict(pms=n, cpu=cu, mem=mu, frag=1.0 - max(cu, mu), sc=sc / (n * PM_CPU), sm=sm / (n * PM_MEM))

def gen_vms(n, seed=425, skew=0.0):
    """skew=0: 均衡机型 (mem = 4*cpu); skew>0: 混入 CPU 重 / 内存重的偏斜机型。"""
    random.seed(seed)
    bal, skw = [(2, 8), (4, 16), (8, 32), (16, 64)], [(2, 64), (32, 16), (8, 128), (2, 4)]
    out = []
    for i in range(n):
        cpu, mem = random.choice(skw if random.random() < skew else bal)
        out.append(VM(i, cpu, mem, "t%d" % random.randrange(4)))
    return out


def check(pms, vms):
    placed = [v.vid for p in pms for v in p.vms]
    assert sorted(placed) == sorted(v.vid for v in vms), "some VM lost or duplicated"
    assert all(p.cpu_used <= p.cpu_cap and p.mem_used <= p.mem_cap for p in pms), "overcommit!"


STRATS = ("first_fit", "best_fit", "worst_fit", "first_fit_dec", "best_fit_dec")


def table(title, vms):
    lb = max(-(-sum(v.cpu for v in vms) // PM_CPU), -(-sum(v.mem for v in vms) // PM_MEM))
    print("\n=== %s ===" % title)
    print("VMs=%d demand=%d vCPU/%d GiB | PM cap=%d/%d | capacity LB=%d PMs" % (len(vms),
          sum(v.cpu for v in vms), sum(v.mem for v in vms), PM_CPU, PM_MEM, lb))
    print("%-13s %5s %8s %8s %7s %10s %10s %7s" % ("strategy", "#PMs", "cpuUtil",
          "memUtil", "frag", "strandCpu", "strandMem", "vsLB"))
    res = {}
    for s in STRATS:
        pms = place_all(vms, s); check(pms, vms); res[s] = dict(p=pms, m=metrics(pms))
        m = res[s]["m"]
        print("%-13s %5d %7.1f%% %7.1f%% %6.1f%% %9.1f%% %9.1f%% %6.2fx" % (s, m["pms"],
              100 * m["cpu"], 100 * m["mem"], 100 * m["frag"], 100 * m["sc"], 100 * m["sm"],
              m["pms"] / lb))
    return res


if __name__ == "__main__":
    A, B = gen_vms(240, 425, 0.0), gen_vms(240, 425, 0.30)
    ra, rb = table("workload A: 均衡机型 (mem = 4*cpu)", A), table("workload B: 30% 偏斜", B)
    assert ra["first_fit_dec"]["m"]["pms"] <= ra["first_fit"]["m"]["pms"]
    print("\n[结论1] 一维直觉在 A 上成立: FFD(%d) <= FF(%d); worst_fit(%d) 摊薄负载最费机器"
          % (ra["first_fit_dec"]["m"]["pms"], ra["first_fit"]["m"]["pms"], ra["worst_fit"]["m"]["pms"]))
    print("[结论2] 多维装箱下 FFD 反而不优: FF(%d) vs FFD(%d), strandedCpu %.1f%% vs %.1f%%"
          % (rb["first_fit"]["m"]["pms"], rb["first_fit_dec"]["m"]["pms"],
             100 * rb["first_fit"]["m"]["sc"], 100 * rb["first_fit_dec"]["m"]["sc"]))
    print("        标量排序把 CPU 重的 VM 提前, 两台就塞满 CPU 而内存剩大半 (搁浅)")
    random.seed(7)                            # 40% 的 VM 退租, 机器变碎片化
    pms, allv = rb["first_fit_dec"]["p"], B
    drop = set(random.sample([v.vid for v in allv], int(len(allv) * 0.4)))
    for p in pms:
        for v in list(p.vms):
            if v.vid in drop:
                p.evict(v)
    m0 = metrics(pms)
    freed = consolidate(pms)
    check(pms, [v for v in allv if v.vid not in drop])
    m1 = metrics(pms)
    print("\n[结论3] churn 后仍占 %d 台 (在用 %d) -> 热迁移关闭 %d 台 -> 剩 %d 台; cpuUtil"
          " %.1f%% -> %.1f%%, 回收 %.1f%% 的机器 (直接对应云账单)" % (len(pms) + freed, m0["pms"],
          freed, len(pms), 100 * m0["cpu"], 100 * m1["cpu"], 100.0 * freed / (len(pms) + freed)))
    print("\n[OK] 断言通过: VM 无丢失/重复, 物理机无超卖, 结果可复现")

实际运行输出（python3 直接运行，random.seed 已固定，结果可复现）：

=== workload A: 均衡机型 (mem = 4*cpu) ===
VMs=240 demand=1782 vCPU/7128 GiB | PM cap=64/256 | capacity LB=28 PMs
strategy       #PMs  cpuUtil  memUtil    frag  strandCpu  strandMem    vsLB
first_fit        28    99.4%    99.4%    0.6%       0.0%       0.0%   1.00x
best_fit         28    99.4%    99.4%    0.6%       0.0%       0.0%   1.00x
worst_fit        30    92.8%    92.8%    7.2%       0.0%       0.0%   1.07x
first_fit_dec    28    99.4%    99.4%    0.6%       0.0%       0.0%   1.00x
best_fit_dec     28    99.4%    99.4%    0.6%       0.0%       0.0%   1.00x

=== workload B: 30% 偏斜 ===
VMs=240 demand=1950 vCPU/9048 GiB | PM cap=64/256 | capacity LB=36 PMs
strategy       #PMs  cpuUtil  memUtil    frag  strandCpu  strandMem    vsLB
first_fit        38    80.2%    93.0%    7.0%      19.1%       5.1%   1.06x
best_fit         39    78.1%    90.6%    9.4%      18.3%       6.1%   1.08x
worst_fit        39    78.1%    90.6%    9.4%      10.7%       2.6%   1.08x
first_fit_dec    42    72.5%    84.2%   15.8%      27.0%      14.7%   1.17x
best_fit_dec     42    72.5%    84.2%   15.8%      27.0%      14.7%   1.17x

[结论1] 一维直觉在 A 上成立: FFD(28) <= FF(28); worst_fit(30) 摊薄负载最费机器
[结论2] 多维装箱下 FFD 反而不优: FF(38) vs FFD(42), strandedCpu 19.1% vs 27.0%
        标量排序把 CPU 重的 VM 提前, 两台就塞满 CPU 而内存剩大半 (搁浅)

[结论3] churn 后仍占 42 台 (在用 37) -> 热迁移关闭 14 台 -> 剩 28 台; cpuUtil 45.9% -> 73.8%, 回收 33.3% 的机器 (直接对应云账单)

[OK] 断言通过: VM 无丢失/重复, 物理机无超卖, 结果可复现

【代码做什么？】

1. VM / PM 两个数据类刻画需求与容量：VM 带 (cpu, mem, tenant) 三维属性，PM 带容量、已用量与 VM 列表。多租户通过 tenant 字段体现（生成时随机分配给 4 个租户，同一台物理机上会混住不同租户——这就是 multi-tenancy）。
2. PM.fits() 实现二维容量不变量；PM.place() 在提交前用 assert 再校验一次，等价于真实系统里”调度器预留 + 物理机二次校验”的双重检查。
3. PM.stranded() 计算搁浅资源：若内存已满，则剩余 CPU 永远无法被利用；反之亦然。这是多维装箱特有的浪费形式，一维装箱里不存在。
4. place_all() 是核心：first_fit 取第一个装得下的机器；best_fit 取”放完后剩余量最小”的机器；worst_fit 取剩余量最大的机器；带 _dec 后缀的版本先把 VM 按归一化负载降序排序（离线/Decreasing 变体）。三种打分都归一化到 $[0,1]$，避免 CPU（64）与内存（256）量纲不可比。
5. metrics() 输出机器数、CPU/内存利用率、碎片率（$1 - \max(U_{cpu}, U_{mem})$，以瓶颈维度衡量）与两维的搁浅率；table() 还把结果与容量下界 $\max(\lceil \sum cpu / C_{cpu}\rceil, \lceil \sum mem / C_{mem}\rceil)$ 比较，得到 vsLB 倍数。
6. 两组负载：A 是”均衡机型”（内存 = 4×CPU，与物理机 64:256 的比例一致）；B 混入 30% 的偏斜机型（(2,64) 内存重、(32,16) CPU 重、(8,128)、(2,4)），用来制造多维装箱的困难。
7. consolidate() 模拟热迁移合并：按负载升序挑最空的机器作为 victim，尝试把它的 VM 全部迁到别的机器；全部成功就关闭该机器（freed += 1），任一失败就回滚已经搬走的 VM（保证不丢 VM）。
8. __main__ 最后模拟 churn：随机让 40% 的 VM 退租，再调用 consolidate()，观察”碎片化 → 整理 → 回收机器”的全过程。
9. check() 在每个阶段后断言两条不变量：无 VM 丢失或重复、无物理机超卖。

【分布式机制透视】

• 谁是”分布式系统”里的实体？ PM 对象就是数据中心里的计算节点，VM 是运行其上的租户负载，place_all() 扮演全局调度器（Resource Manager）+ 每机 Node Manager 的合成角色。真实系统中这三者是通过网络通信的独立进程，这里的函数调用是消息传递的本地化替身。
• 状态在哪里？ 每个 PM 自己维护 cpu_used / mem_used / vms，这正是”每台物理机是本机容量的权威来源”这一真实设计的映射。调度器的视角在真实系统中可能滞后（心跳间隔导致的陈旧信息），代码里为了让结论可复现而假设了完美信息——这是一个被有意简化的假设，2.5 会讨论它对真实调度器的影响。
• 哪些是并发的来源？ consolidate() 里的”迁移→回滚”模式对应真实系统里”迁移失败必须恢复原状”的事务语义；victim 的选择顺序（按负载升序）模拟了”先整理最空的机器”这一常见策略。
• 故障在哪里？ 代码本身没有模拟故障——这是刻意的，它只解决”放置”这一个纯优化问题。真实系统还要处理：心跳超时（误判）、迁移过程中源机崩溃、被抢占任务的重新放置、以及”调度器自己挂了”。这些属于 Lecture 3（YARN 的 RM/NM/AM 与故障处理）和 Lecture 5-6（故障检测与成员管理）的内容。
• 弹性（elasticity）体现在哪？ if target is None: 打开新物理机 这一行：在真实云里它就是”向资源池申请一台新机器并开机”，耗时从数十秒（裸机）到数分钟（含镜像与启动），而不是零成本。代码里它是瞬时的，所以代码给出的利用率是乐观上界。
• churn 与租户生命周期：40% 的 VM 退租模拟了”弹性”的另一半——缩容。真实云的难点是缩容后把散落各处的负载重新聚拢，这正是 consolidate() 存在的原因。

【与理论的对应】

• 代码的 place_all() 逐行对应算法 2.3.1 的伪代码：第 5-6 行（排序与遍历）↔ 伪代码第 4、6 行；if base == "first_fit": target = pm; break ↔ 伪代码第 8-10 行；if target is None: PM(len(pms)) ↔ 伪代码第 11-13 行；target.place(vm) 里的 assert ↔ 伪代码第 15-16 行与安全性论证。
• workload A 验证了近似比理论的”良性区”：所有策略都达到或接近容量下界 28 台（vsLB = 1.00x），说明在需求与容量比例一致时，FFD 的 11/9 上界在实践中远未被触及。
• workload B 验证了”多维性使一维证明失效”：FFD 用 42 台，比 First Fit 的 38 台多 10.5%，搁浅 CPU 从 19.1% 升到 27.0%。这直接驳斥了”FFD 一定不差于 FF”的一维直觉，也说明 2.3.1 中 11/9 证明里”大项配对”这一步不可搬到多维。
• worst_fit 的表现验证了”摊薄负载 = 浪费机器”：在两组负载上它都用了最多的机器（30 台 vs 28 台；39 台 vs 38 台）。原因很直观：worst-fit 刻意把每台机器都留得半空，导致需要更多机器来容纳同样的总量。（补充说明：一维装箱的经典分析给出该家族的整体上界为 2，worst-fit 是该家族中表现最差的成员；这里观察到的是它在多维、且带容量下界比较下的具体表现。）
• consolidate() 验证了活性论证 2：每次成功都严格减少机器数（42 → 28），失败必回滚，因此算法必然终止；同时它把 cpuUtil 从 45.9% 提升到 73.8%，量化了”整理碎片”的经济价值——回收 33.3% 的机器就是省下 1/3 的账单。

2.5 性能与可扩展性分析

装箱问题的复杂度与近似比

关键结论：离线比在线好（1.222 vs 1.7），但离线也拿不到最优（3/2 的天然屏障）。

为什么是 NP-hard

判定版本：”给定项集合与箱子容量 $C$，是否存在使用不超过 $B$ 个箱子的装箱方案？”是 NP-complete。归约来自 Partition：给定 $\{a_1,\dots,a_n\}$ 与 $\sum a_i = 2B$，把每项 $a_i$ 作为物品、$B$ 作为箱子容量；则”存在 2 箱方案”$\iff$”存在和为 $B$ 的子集”。因为 $\mathrm{OPT}=2$ 与 $\mathrm{OPT}=3$ 的比值是 $3/2$，任何 $(3/2-\epsilon)$-近似算法都能判定 Partition，从而 $P = NP$。

多维更糟：经典的标量装箱本来就是 NP-hard，而 $d$ 维向量装箱（VBP）在 $d \ge 2$ 时是 APX-hard——不存在多项式时间近似方案（PTAS），除非 P = NP（补充说明：该结论来自 Woeginger 关于多维装箱不可近似性的经典工作）。这意味着：

• 加一维（CPU + 内存）不是”变难一点”，而是从”可以任意逼近”变成”存在无法逾越的常数比下界”；
• 真实调度器从不追求”最优放置”，而是追求足够好 + 可解释 + 可抢占可迁移。

真实系统怎么绕过这个难题：分层调度 + 抢占

可扩展性瓶颈与实际表现

2.6 关键要点

1. 云不是新发明，而是六代分布式系统的合流——分时（共享与计量）、数据处理（大规模批处理）、集群（商品化硬件 + 集中调度）、网格（两级调度与联邦安全）、P2P（大规模成员管理）依次贡献了云的零部件；真正”新”的只有规模、按需访问、数据密集与新编程范式四点。
2. 云的本质是”按需、池化、计量、弹性”的资源抽象，虚拟化只是实现手段。判断一个东西是不是云，看它是否同时具备五大特征，而不是看它有没有 hypervisor——裸机云、容器云、Serverless 都是云。
3. 数据中心是一棵故障域树（VM → Server → Rack → AZ → Region）：每个分叉都代表”一次故障会同时打掉哪些机器”。副本、反亲和与容灾本质上是在这棵树上选择互不相交的分支，而不是简单地”多放几份”。
4. 商品化硬件 + 大规模把故障从例外变成了常态（12,000 台、单机 10 年一坏 ⇒ 7.2 小时一次机器故障；96,000 块盘、AFR 2% ⇒ 每天约 5 次盘故障）。这是整门课容错技术的唯一动机：既然硬件不可靠，可靠性就必须由软件（复制、检测、恢复、迁移）提供，而不是靠提高单机 MTTF。
5. 放置/调度本质是向量装箱，因而 NP-hard，多维下连近似都很难（离线近似比下界 3/2，在线下界 1.5403，多维 APX-hard）。真实系统的答案是工程化的：分层调度 + 抢占 + 迁移 + 延迟放置，用”可撤销的决策”替代”一次做对”。
6. 云经济学直接决定系统设计：按需付费让”用存储换容错”（把容错外包给 S3）、”批量化小写入”成为正确选择；盈亏平衡点（本讲实例约 12 个月）让初创公司用云、长期稳定的重负载自建。

2.7 常见陷阱与注意事项

1. 把”云 = 虚拟化”划等号。 为什么错：虚拟化是 IaaS 的一种实现手段；裸机云（HaaS）、容器云、Serverless 都没有传统意义上的 hypervisor，但都满足云的五大特征。 正确做法：用”按需自助、广泛网络访问、资源池化、快速弹性、可计量”五条来判断，虚拟化只是其中一条实现路径。

2. 把集群、网格、云混为一谈。 为什么错：三者的资源所有权、耦合度、调度模型、作业粒度、计费模式都不同——网格是”多个组织把自己的机器借给你”（联邦、无中心、免费/配额），云是”一家公司把机器租给你”（中心化、按需、计费）。混淆会导致错误的设计假设，例如在云上假设”同一个管理域”。 正确做法：设计前先明确所有权、信任域、计费模型与故障模型（见 2.2.1 的对比表）。

3. 只看 CPU 利用率，忽略多维资源与搁浅。 为什么错：本讲代码的 workload B 里，first-fit 的 CPU 利用率 80.2%、内存 93.0% 看起来都不错，但仍有 19.1% 的 CPU 因为内存先满而被永久搁浅。只盯一个维度会得出”还有 20% 空闲”的错误结论。 正确做法：同时跟踪每个维度的利用率、碎片率（以瓶颈维度衡量）与搁浅率（因另一维已满而不可用的容量），并以瓶颈维度做容量规划。

4. 假设”故障是例外”，写出”重试就好”的代码。 为什么错：在 12,000 台的规模下平均 7.2 小时就有一次机器故障，重试是常态路径而非异常路径；不设退避（backoff）与上限的重试会引发重试风暴，把小故障放大成全局雪崩。 正确做法：把故障当成一等公民设计——指数退避 + 抖动、幂等操作、熔断、以及”重试预算”（retry budget）；同时用冗余而非重试来吸收硬件级故障。

5. 把 AZ 当成”多机房”就以为高枕无忧。 为什么错：AZ 之间的隔离是物理层面的（供电/制冷/网络），但控制面往往仍然共享（IAM、DNS、镜像仓库、发布系统）。一次错误的配置推送、一次全局配额服务故障或一次证书过期，会同时打掉所有 AZ——这就是相关故障。 正确做法：区分”数据面故障域”与”控制面故障域”，对控制面也做爆炸半径控制（分区域灰度、限流、可回滚），并做真实的跨 AZ/跨 Region 故障演练（参见 Lecture 28 数据中心灾难）。

6. 把 overcommit 当免费午餐。 为什么错：CPU 超卖在租户同时忙碌时产生排队，尾延迟（p99）会远早于平均利用率见顶而爆炸；内存超卖会导致 ballooning、swap 抖动甚至 OOM，且可能误杀其他租户的进程。 正确做法：按 SLA 分级设置 overcommit 比例与 QoS 上限（cgroups/CPU shares/内存硬限额），监控”资源争抢”而非”资源占用”，并为延迟敏感型负载保留专用核或使用限频策略。

7. 用平均利用率评估成本与容量。 为什么错：成本由峰值（或某个百分位）决定，不是平均值；弹性只对无状态、可快速启动、流量可预测的负载有效，有状态服务的缩容要做数据迁移。 正确做法：按 P95/P99 负载做容量规划，区分”可弹性部分”与”必须预留的部分”（预留实例、预热池），并把迁移与冷启动成本计入弹性收益。

8. 去求装箱问题的最优解。 为什么错：向量装箱 NP-hard，多维下 APX-hard；在毫秒级的在线决策窗口里求最优在原理上就不可能，工程上也无收益——真实系统更在意决策延迟、可解释性与可抢占性。 正确做法：用贪心启发式（FFD/BFD 变体、按主导资源排序、dot-product/norm-based 打分）+ 定期整理（迁移合并）+ 抢占兜底，并度量决策质量（利用率、碎片、搁浅）而非追求最优。

2.8 思考题（带答案）

Q1（计算题） 某云厂商的一个集群有 12,000 台服务器，另有 3 个可用区（每区 4,000 台）。假设单台服务器平均每 10 年发生一次故障；每台服务器有 8 块硬盘，单盘年故障率（AFR）为 2%。 (a) 该集群中”下一台机器故障”的平均间隔是多少？ (b) 整个集群平均每天发生多少次磁盘故障？ (c) 若某键值存储使用 3 副本，副本在集群内完全随机放置，则一块盘故障直接导致某个键的数据丢失的概率大约是多少？如果副本被放在同一个机架上（假设每机架 40 台机器，故障后整架不可用），结论会怎样变化？ (d) 由 (c) 能得到什么设计原则？

答案 (a) 单机 MTTF = 120 个月。12,000 台机器的集群 MTTF = $120/12000 = 0.01$ 个月 $= 0.01 \times 30 \times 24 = 7.2$ 小时。这就是讲义给出的数字：平均每 7.2 小时就有一台机器坏掉。 (b) 总盘数 $= 12000 \times 8 = 96{,}000$。年故障次数 $= 96000 \times 0.02 = 1920$ 次，平均 $1920/365 \approx 5.26$ 次/天，即约每 4.6 小时一次盘故障。 (c) 3 副本分布在 3 台不同机器上，一次盘故障最多打掉一个副本，不可能丢数据——丢数据需要同一键的 3 个副本在”副本重建完成之前”同时失效。 把重建窗口取为 1 天：一块指定盘在 1 天内失效的概率约为 $0.02/365 \approx 5.5\times10^{-5}$。三个副本各自所在的盘在窗口内同时失效的概率约为 $(5.5\times10^{-5})^3 \approx 1.7\times10^{-13}$，可以忽略。 若 3 个副本放在同一机架（40 台机器、320 块盘），故障粒度就从”一块盘”升级为”一个机架”：一次机架级事件（ToR 交换机故障、机架配电故障、或冷却事故）会把 3 个副本一起打掉，可用性退化为”机架本身可靠”——机架级 MTTF 约为 $120/40 = 3$ 个月。也就是说，同样的 3 副本，跨机器放置的失效率约 $10^{-13}$ 量级，同机架放置则约 $4\times10^{-1}$/年（3 个月一次）——相差 12 个数量级。 (d) 设计原则：副本必须跨故障域放置（反亲和 / anti-affinity），而且要对齐到”物理上真正独立”的层级——跨机器 < 跨机架 < 跨 AZ < 跨 Region，隔离等级越高，相关故障概率越低，但跨域带宽与延迟的成本也越高。复制因子只是分子，故障域上的分布才是分母。

Q2（”直觉错误”类） 有同学认为：”一维装箱里 FFD 的近似比是 11/9，远好于 First Fit 的 1.7，所以在云里只要把 VM 按 CPU+内存的加权和降序排好，再用 first-fit 放置，就一定比不排序的 first-fit 用更少物理机。”这个推理错在哪里？本讲的代码给出了什么证据？

答案：错误在于把一维结论直接推广到多维。FFD 的 11/9 证明依赖于两个一维特有的性质：(i) 需求是标量，因此存在全序，”大项”这个概念才有意义；(ii) 大项（$>C/2$）必然两两不能共处一箱，因此可以”配对计数”。在多维下，$r_i$ 是向量，没有全序——按标量和排序会得到一个与任何单一维度都不一致的顺序：CPU 重型 VM（如 (32,16)）的标量和可能大于内存重型 VM（如 (16,64)），于是它们被排到最前面，两两配对后CPU 立刻占满而内存只用掉很小一部分，第三台同类型 VM 再也放不进去。

代码的证据：在 workload B（30% 偏斜机型）上，first_fit 用 38 台物理机，first_fit_dec 用 42 台（多 10.5%），并且 CPU 搁浅率从 19.1% 升到 27.0%。也就是说”排序”这个动作在多维下反而变差了。

正确做法：(1) 用主导资源份额（dominant resource share）排序——$key(v) = \max(cpu/C_{cpu},\ mem/C_{mem})$，让”在两个维度上都很突出”的 VM 排前面，而不是让”某一维极端的 VM”排前面；(2) 按维度分别装箱（把 CPU 重型与内存重型 VM 混搭，让两个维度同时被消耗）；(3) 使用向量装箱的专用启发式（dot-product、norm-based、分层打包）；(4) 在真实系统中靠 overcommit + 定期迁移整理来兜底——不要指望初始放置就做对。

Q3（概念/判断类） 某公司在 AWS EC2 上购买虚拟机，自己在上面安装 MySQL、自己打补丁、自己做备份、自己在上面部署用 Python 写的业务代码。请回答：(a) 这属于 SaaS、PaaS 还是 IaaS？(b) 该公司与 AWS 各自负责 2.2.3 责任栈的哪几层？(c) 如果他们改用 AWS RDS（托管数据库）和 Elastic Beanstalk（托管应用平台），责任边界如何移动？(d) 如果换成 Gmail，边界又在哪里？

答案 (a) IaaS。他们租到的只是”虚拟化的计算与存储基础设施”（L3 及以下），其余全部自负。判断依据是：EC2 交付的是虚拟机，而不是运行时或应用。 (b) AWS 负责 L1（机房/电力/冷却）、L2（服务器/存储/网络）、L3（虚拟化/容器运行时）；该公司负责 L4（guest OS 与内核补丁）、L5（MySQL、Python 运行时与中间件）、L6（应用的业务逻辑与数据）。 (c) 换成 RDS 后，数据库的安装、补丁、备份、主从复制与故障切换都由 AWS 负责，L5 的数据库部分上升为 CP。若同时使用 Elastic Beanstalk，则应用服务器、运行时、负载均衡、自动扩缩也由 AWS 管理，L5 与 L4 大部分上升为 CP；此时他们只剩 L6（应用代码与数据），已经跨入 PaaS。 (d) Gmail：SaaS。客户只负责数据内容与账号，L1-L5 与 L6 的应用逻辑全部由提供商负责，客户连”选什么数据库”的权力都没有。

Q4（推演/设计类） 某团队要在 3 个可用区部署一个 3 副本的存储系统，同时系统还要在”硬件持续故障”的环境下保持可用。已知：单机年故障率 1%，单 AZ 年故障率（供电/制冷/网络整体失效）0.1%。请回答：(a) 在”副本按 AZ 分布（每区 1 个）”与”3 个副本都在同一个 AZ”两种方案下，数据完全不可用的年概率分别是多少（假设故障独立）？(b) 为什么”规模出可靠性”这个说法要求软件层必须做三件事？(c) 如果 AZ 之间的复制是同步的，跨 AZ 写入延迟会带来什么后果？

答案 (a) 先明确”可用”的定义：假设系统采用多数派仲裁，3 个副本中只要有 2 个可读写就算可用。

• 方案一（跨 AZ，每区 1 个副本）：不可用需要 ≥2 个 AZ 同时失效。在独立假设下年概率为 $\binom{3}{2}p^2 = 3\times(10^{-3})^2 = 3\times10^{-6}$。（机器级故障只会拿走 1 个副本，不影响多数派。）
• 方案二（3 个副本都在同一个 AZ）：一次 AZ 故障就打掉全部 3 个副本，年不可用概率 $= 10^{-3} = 0.1\%$。
• 结论：跨 AZ 把年不可用概率从 $10^{-3}$ 降到 $3\times10^{-6}$，改善约 330 倍（约 2.5 个数量级）。
• 反例提醒：如果系统要求”3 个副本全部在线”才能服务（没有仲裁机制），那么跨 AZ 反而更差——任一 AZ 故障都导致不可用，年概率 $\approx 3\times10^{-3}$，是”全放一个 AZ”（$10^{-3}$）的 3 倍。“跨 AZ 部署”必须配合”多数派仲裁”才有效，这是很多人踩过的坑。
• 另一个提醒：0.1% 的 AZ 年故障率意味着约每 1,000 年会有一次两区同时故障。在”多年运营 × 数百个租户 × 数千个数据分片”的尺度下，这个概率被放大了成千上万倍，所以还需要跨 Region 的异步复制兜底。 (b) “规模出可靠性”不是自动的，它依赖软件层做三件事：
  1. 复制（replication / erasure coding）：让数据可靠性不依赖任何单块盘或单台机器；关键是副本落在不同故障域（见 Q1）。
  2. 快速检测 + 快速恢复：既然故障必然发生，重要的是 MTTR 而不是 MTBF——失效检测（心跳/gossip/SWIM）、成员管理、自动重建副本、自动重启或迁移 VM。可用性 $\approx \text{MTTF}/(\text{MTTF}+\text{MTTR})$，恢复越快需要的冗余度越低。
  3. 故障域隔离与爆炸半径控制：反亲和放置、跨机架/跨 AZ 拓扑感知、灰度发布、限流熔断，避免相关故障把冗余一次性吃掉。 一句话：商品化硬件把”单机可靠性”转化成了”系统级冗余与恢复速度”问题，而这只有在软件层主动完成时才成立。 (c) 同步跨 AZ 复制的代价是：每次写入都要等待跨 AZ 往返（同一 Region 内通常 1-2 ms，跨 Region 可达数十毫秒）。后果是：(i) 写延迟显著上升（p99 更明显，因为要等最慢的那个副本）；(ii) 可用性与延迟直接耦合——任一 AZ 网络抖动都会拖慢全部写入；(iii) 因此很多系统采用”同 AZ 内同步 + 跨 AZ 异步“的分层复制（例如 quorum 只在同 AZ 内做，跨 AZ 做异步流复制），在延迟与容灾之间取折中。这正是 Lecture 21（复制控制）与 Lecture 22-24（一致性模型）要展开的取舍。