Distributed Systems — Fall 2026, University of Illinois at Urbana-Champaign

基于 UIUC CS 425 / ECE 428 公开课程资料整理，以分布式算法实现与正确性论证为核心 配套：可运行的 Python 实现 · 算法伪代码 · 安全性/活性论证 · 复杂度分析 · 真实系统案例

第一部分：课程概览

1. 这门课在教什么

CS 425 / ECE 428 是 UIUC 的分布式系统核心课程。用课程讲义自己的话说，它关心四件事：

1. Distributed Systems —— 分布式系统是什么样的系统
2. How to design algorithms for them —— 如何为它们设计算法
3. How to design these systems —— 如何设计系统
4. How they work in real life / How to build real distributed systems —— 它们在真实世界中如何工作、如何真正构建出来

这不是一门”介绍各种云产品”的课，而是一门讲原理、讲算法、讲正确性的课。整门课的主线是：

在自治、可编程、异步、易故障的实体集合之上，通过不可靠的通信介质， 如何设计出可扩展、容错、且行为可被证明正确的系统？

课程的三个层次贯穿始终：

2. 课程的目标定义（本课程的”工作定义”）

课程给出的、贯穿全学期的工作定义是：

A distributed system is a collection of entities, each of which is autonomous, programmable, asynchronous and failure-prone, and which communicate through an unreliable communication medium.

这个定义值得逐词拆解，因为它直接决定了后面每一讲算法的假设：

课程同时给出了 Lamport 那个著名的、带着黑色幽默的定义：

“A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.” —— Leslie Lamport

以及几个”看起来不错但对设计者不够用”的经典定义：

• Tanenbaum：a collection of independent computers that appear to the users of the system as a single computer.
• Schroeder：several computers doing something together，因此有三个主要特征：multiple computers、interconnections、shared state。
• FOLDOC：A collection of (probably heterogeneous) automata whose distribution is transparent to the user so that the system appears as one local machine.

课程明确说这些定义”unsatisfactory“，原因是它们只描述了外观（透明性），而没有描述内部——而本课程恰恰关心 internal 的 design and implementation、maintenance、和 algorithmics（protocols / distributed algorithms）。这是理解整门课立场的关键。

3. 课程范围

根据官方 Syllabus，课程主题包括（但不限于）：

MapReduce、peer-to-peer systems、failure detectors、synchronization、election、consensus、 inter-process communication、gossiping、concurrency control、replication、key-value stores、 NoSQL、security、probabilistic protocols、stream processing、measurements

这些主题被放在真实的、已部署的系统背景下讨论：云与数据中心、数据库、P2P 系统、集群。

课程明确不涵盖的内容：计算机网络与路由的细节、无线/移动计算（这些由 CS 438/439 等课程覆盖）。这是一个重要的边界——CS 425 从”网络已经提供了某种传输能力”开始，专注于在传输层之上构建分布式系统。

4. 先修要求

课程反复强调：This course assumes knowledge of fundamentals in both OS and networking. 虽然 CS 240/241 名义上是 co-requisite，但实际按”已修完”对待。

5. 课程基本信息

教学团队：主讲 Aishwarya Ganesan、Ram Kesavan；Lead TA：Nishant Sheikh；On-campus TAs：Rafid Murshed、Wei Zhang、Tianyi Zhong、Weidong Wang、Yaqi Qiao；MCS Online TAs：Xinying Zheng（Lead MCS Online TA 兼 Deputy Lead TA）、Soham Chakraborty。

6. 教材

主教材（推荐，非必需）

Coulouris, G., Dollimore, J., Kindberg, T., and Blair, G. Distributed Systems: Concepts and Design, Addison-Wesley, 5th Edition, 2011. ISBN: 0132143011

课程的一条硬性规定：所有章节号、小节号、习题号只以第 5 版为准。使用旧版本的学生需自行负责编号的转换（讲义原文：no excuses）。

主教材第 5 版的章节结构（本课程的主要对应关系）：

补充教材

1. Ghosh, S. Distributed Systems: An Algorithmic Approach, CRC Press, 2006, ISBN 1584885645. （UIUC 图书馆可在线免费访问；算法视角，与 Coulouris 的系统视角互补）
2. Tanenbaum, A. & van Steen, M. Distributed Systems: Principles and Paradigms, Prentice Hall, 2nd Ed., 2005, ISBN 0132392275.
3. Lynch, N. Distributed Algorithms: Concepts and Design, Morgan-Kaufmann, 1996, ISBN 1558603484. （分布式算法的理论经典）
4. Coulouris 等，第 4 版（可在 Grainger 图书馆查阅）

课程指定论文（Reading）

7. 评分与作业

学生分三类（Section）

分数构成（tentative）

评分是相对评分（curve），本科生与研究生分开 curve，3cr 与 4cr 分开 curve。官方说明：过去几年各组的中位数成绩在 B+/B。4cr 的 CS 425 满足院系的 team project / one-term capstone 要求（编程项目占比至少 30%）。

政策要点

• Best 3 of 4 Homeworks：4 次 HW 各 10 分，只取最高 3 次计入（最多 30 分）。适用于所有学生。但课程警告：不要因此完全放弃某次 HW，否则会丢失期中/期末所需的知识。
• HW：全部个人独立完成，必须提交打字版（手写不收）。每次 HW 的新题从新的一页开始。截止时间是美国中部时间 23:59（硬性，无延期）。
• MP（仅 4cr on-campus/Chicago）：必须 2 人一组（1 人、3 人及以上都不接受）。共 4 次，每次需要 2-4 周工作量，包含报告 + 现场 demo（Chicago 学生通过 Zoom）。所有组可获得 CS VM Farm 集群的访问权限。编程语言自选。
• 考试：期中 10/8（课堂内，75 分钟，闭卷闭笔记，允许计算器，不允许 cheatsheet 与任何电子设备），范围 Lectures 1-12 + HW1-2。期末 3 小时，范围 Lectures 1-29 + HW1-4。补考/冲突考试需提前 2 周申请，且不因旅行、面试、课程冲突批准。
• 学术诚信：所有提交必须是本人/本组从零到完成的原创。HW/MP 只能使用提供的课程材料。明确禁止使用 LLM/ChatGPT/Gemini 等 AI 工具（讲义原文：trust us, they will give you wrong solutions）。在 Piazza 上泄露解答即视为违规。首次违规该次作业 0 分，第二次违规整门课 F。
• Regrade：成绩返回后 1 周内在原提交系统中提交，TA 的决定是最终决定（不能再对 regrade 结果 regrade）。

⚠️ 笔记使用声明：本笔记是为学习和理解而整理的知识材料。由于课程禁止使用 AI 工具完成 HW/MP，本笔记中的任何代码不应用于作业提交。笔记的目的是帮助你建立分布式系统的知识体系与直觉。

8. 课程日程（Fall 2026，共 29 讲）

作业时间线

9. 本笔记的组织方式

本笔记按上面 29 讲的顺序组织，共 27 章（Lecture 14 为考试，无笔记；部分内容相近的讲座合并为一章）：

用户需求主题 → 章节对应表

每章统一结构

每章严格遵循以下 8 段式结构，以便横向对照学习：

1. 概述 —— 本讲核心问题与在课程中的位置
2. 核心概念与分布式机制图解 —— 概念定义 + 直观类比 + ASCII 机制图 + 系统模型假设
3. 算法伪代码与正确性分析 —— 假设与系统模型 → 伪代码 → 算法逻辑解说 → 安全性/活性论证 → 复杂度
4. 代码示例与分布式实现 —— 可运行的 Python 实现 + “代码做什么” + “分布式机制透视” + “与理论的对应”
5. 性能与可扩展性分析 —— 时间/消息/空间复杂度、容错能力、真实系统表现
6. 关键要点 —— 3-6 条”分布式系统黄金法则”
7. 常见陷阱与注意事项 —— 学生最易犯的错误与正确做法
8. 思考题（带答案） —— 概念题 + 计算推演题 + “错在哪里”类问题

第二部分：课程公开资料获取记录

10. 资料抓取范围与方法

本笔记的所有技术内容均来自以下公开可访问的课程资料。抓取范围与方法如下：

10.1 公开可访问并已抓取的资源

10.2 Fall 2026 学期已发布的讲义（公开）

重要说明：Fall 2026 学期在进行中，课程表上 lectures.html 对每讲的幻灯片都给出了 [ppt] [pdf] 链接，但只有上述 7 份 PDF 实际可下载。其余讲次的幻灯片页面标注为 “Tentative” 且文件尚未上传（HTTP 404），这是学期进度导致的正常现象，不是访问限制。

10.3 为保证笔记完整性而补充的同等资料（公开）

由于 FA2026 仅发布了前 6 讲的讲义，本笔记同时抓取了同一门课程 Fall 2025 的完整讲义集（/cs425/fa2025/）。选择 FA2025 的理由：

• 同一课程代码、同一课程体系、同一教材（Coulouris 5th Ed.），讲义内容与 FA2026 高度一致（FA2026 的前几讲与 FA2025 逐页对应）
• FA2025 的 29 讲全部幻灯片均已公开，是本课程最完整的公开技术资料来源
• FA2026 的讲座主题序列与 FA2025 基本一一对应

合计 28 份讲义、1142 页、约 19 MB。

补充取自 FA2025 的 Spark 讲义（L26.B.FA25.pdf，17 页）—— FA2026 课程表规定所有学生必须观看 Spark 视频（在考试范围内），因此该主题的讲义内容以 FA2025 版本为准。

10.4 课程站公开的指定论文

⚠️ 一处课程网站链接错标的记录：lectures.html 在 Lecture 23 的 “DRF Paper” 标签下指向 http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-259.pdf，但该 PDF 的实际内容是 《Discretized Streams: A Fault-Tolerant Model for Scalable Stream Processing》（Zaharia et al., UCB/EECS-2012-259, 2012 年 12 月），即 Spark Streaming 的原始论文，而非 DRF（Dominant Resource Fairness）论文。DRF 的原始论文是 Ghodsi et al., Dominant Resource Fairness: Fair Allocation of Multiple Resource Types, NSDI 2011，课程站未提供该 PDF。本笔记在 Lecture 21 章节中已如实标注这一差异：Spark Streaming 的容错细节依据该 Berkeley 技术报告，DRF 部分依据讲义口径与 NSDI 2011 的四条公理。

10.5 受限资源（仅记录名称，未抓取内容）

以下资源需要 UIUC netid、课程注册或付费订阅，本笔记不包含其内容，仅如实记录其存在与访问条件：

结论：课程的知识框架完全可以通过公开资料重建——讲座主题序列（lectures.html）、教材章节结构（Syllabus + 教材目录）、以及 28 份完整讲义幻灯片（FA2025）共同构成了足够的技术基础。受限的主要是作业题、考试成绩、讨论区互动和录播视频，这些属于教学管理资源而非知识内容。

11. 公告记录（Announcements）

课程主页的公告栏（Oldest First，最新公告移至 Piazza）：

关键信息：从 8/25 起，所有后续公告都只在 Piazza 发布。这意味着课程主页的公告栏不会继续更新，重要信息（如考试地点、截止日期变更、MP 澄清、Piazza pinned post 中的说明）需要通过 Piazza 获取。这是本笔记无法覆盖的部分。

12. 课程政策全文要点

12.1 学术诚信政策（原文要点）

课程遵循 CS 学术诚信政策。核心条款：

It is the course policy that all of the work you submit for grading, or in support of graded material, as an individual or project group, shall be your own product, from inception to completion. The only resources you can avail of in your HWs and MPs are the provided course materials (slides, textbooks, etc.), and communication with instructor/TA via newsgroup and email.

• 与他人只能讨论课程材料和 HW/MP 的题目本身，不能讨论解法或思路
• 禁止在 Piazza 上泄露解答（包括代码或书面解答）——视为学术诚信违规
• 明确禁止 AI 工具：You cannot use any AI tools like LLMs, ChatGPT, Gemini, etc.
• 考试闭卷闭笔记（除非另有说明）
• 每一份 HW 与 MP（含代码）都会被严格检查违规

违规后果（原文）：

• 第一次违规：该次 HW/MP 得 0 分
• 第二次违规：整门课程 F
• 课程说明：过去我们抓到了几乎所有作弊的学生

12.2 反种族主义 / 反偏见 / 反微侵犯政策

Grainger 工程学院承诺建设反种族主义的包容性社区。课程声明遵循学院的 Anti-Racism and Inclusivity Stance，并鼓励学生向 BART（Bias Assessment and Response Team, https://bart.illinois.edu/） 报告歧视、微侵犯或其他冒犯行为。课程也遵循 CS CARES 与 CS Values and Code of Conduct。

12.3 心理健康声明

课程提供 UIUC 的心理健康资源：

• Counseling Center：217-333-3704，610 East John Street, Champaign, IL 61820
• McKinley Health Center：217-333-2700，1109 South Lincoln Avenue, Urbana, IL 61801
• University Wellness Center

12.4 校园紧急情况

遵循校园的 Run, Hide, Fight 应急指引。

12.5 其他重要政策

• 注册与 waitlist：院系不维护 waitlist，不能授予超出容量的 override。请按时提交 HW 和 MP（即使尚未注册成功）。若 9/30 前仍无法注册，联系课程 staff。
• 3cr 转 4cr：前几周通常会有空位。请先按 4cr 提交 MP；若 9/30 前无法转入 4cr，联系 staff。
• 时间冲突 override：由于班级规模，拒绝需要为期中/期末提供冲突考试的请求。若你的另一门课保证没有冲突考试且你愿意放弃参与分（participation points），可以在邮件中明确说明后申请。
• 本科生注册研究生 section：注册哪个 section 对将来把课程转入硕士学分没有影响（只要该课程未被用于本科学位）。
• 无补考政策：补考只在极少数非学术情形（通常需要 Dean’s office 批准）下提供。因面试、旅行、其他课程 deadline 的延期申请一律不接受。
• DRES 学生：需在考试前至少 2 周（建议 3 周）邮件通知 instructors，并在 DRES 考试中心预约与校内考试同一天同一时间的场次。课程视频已在 DRES 的闭路字幕列表中，幻灯片也会提前发布。

13. 从资料中提炼的”课程精神”

从讲义与 syllabus 的行文中可以提炼出本课程反复强调的几条立场，它们解释了为什么这门课要这样组织：

1. “内部机制”比”外部定义”重要。课程批评经典定义”太短、太不充分”，因为它关心的是 insides：design and implementation、maintenance、algorithmics。

2. AI 时代更需要基础。Lecture 1 专门用一页讲”Computer Science in the time of AI”：

   AI is a capability multiplier: But, 0 × 1000 = 0; if your understanding of concepts, systems, and algorithms is zero, then you’ll produce zero! Prompts express intent, but true engineering is about trade-offs, performance, maintenance, and architectural taste.

3. 必须写代码、调试代码。课程明确说 fundamentals “requires deep engagement with the material; best gained by writing, reading, and debugging code”，并推荐”写并调试你的 MP”。

4. 算法正确性只在特定系统模型下有定义。同一算法在同步模型下可解，在异步模型下可能不可能（FLP）。这是课程把”系统模型”（Ch.3）放在所有算法之前的原因。

5. 权衡（trade-off）是分布式系统的核心语言。一致性 vs 可用性、状态 vs 通信、透明性 vs 性能、简单 vs 高效——每一讲最后都归结为一个取舍。

接下来进入各讲详细笔记。

第三部分：各讲详细笔记

Lecture 1: Introduction — 分布式系统概述与设计目标

讲义对应：CS 425 FA2026 Lecture 1（L1.FA26.txt，44 页）；补充：FA2025 Lecture 1（L1.FA25.txt，48 页） 教材对应：Coulouris, Dollimore, Kindberg & Blair, Distributed Systems: Concepts and Design, 5th Ed., Ch. 1（Characterization of Distributed Systems） 阅读材料：Chapter 1 相关小节；RFC 1945（HTTP/1.0）、RFC 2068（HTTP/1.1）；本讲 PPT 属”全局地图”性质，所有名词后面各有专章

1.1 概述

本讲回答一个看似幼稚、实则极难的问题：什么是分布式系统？ 课程先给出若干”字典式定义”（Lamport、FOLDOC、Tanenbaum、Schroeder），再指出它们对想看清内部机制的人都不够用，最后给出本课程的工作定义：分布式系统是一组自治、可编程、异步、易故障的实体，它们通过不可靠的通信介质通信。这五个形容词就是整门课的公理集——后面所有算法（逻辑时钟、快照、组播、共识、互斥、选举、复制控制）都是这五个前提下的必然产物。

本讲同时绘制两张地图：系统地图（互联网结构、intranet/LAN/WAN/ISP/backbone、协议栈中”分布式系统协议”的位置、HTTP 客户端-服务器模型）与问题地图（异构性、开放性、安全性、可扩展性、故障处理、并发、透明性、QoS 这八大设计目标及其相互冲突）。它在整门课中的位置是”悬念集”：讲义承认这一讲的内容是故意让人困惑的，最后一讲会回到同一批问题。

必须钉死一个判断：分布式系统的本质困难来自异步 + 不可靠通信 + 部分故障的叠加，而不是”机器数量多”。共享内存多处理器同样多机并行，却近似同步模型（延迟有上界、无部分故障），算法世界截然不同——这是全课的钥匙（见 1.2.8）。

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

1.2.1 这门课到底在讲什么（What This Course Is Really About）

• 定义与目的：课程的四条主线是：(1) 分布式系统本身是什么；(2) 如何为它设计算法（distributed algorithms / protocols）；(3) 如何设计系统（体系结构、工程实现）；(4) 它们在真实世界里如何运作、如何真正构建起来。
• 直观解释：把这门课想象成”当一个程序的零件无法被同一个操作系统、同一块内存、同一个时钟管理时，你还能对它有多少掌控力“。单机程序员的三件法宝——共享内存、全局时钟、原子性——在分布式系统里全部失效，课程就是重建这三件法宝的替代品：共享内存 → 复制与一致性协议；全局时钟 → 逻辑时钟与因果序；原子性 → 事务与共识。
• 机制图解：课程知识结构可画成如下”三层视角”：

        ┌──────────────────────────────────────────────────────────────────┐
        │  真实系统 (real distributed systems)                             │
        │  Cloud, P2P, Hadoop, KV store/NoSQL, DFS, 图计算, 流处理, ML      │
        ├──────────────────────────────────────────────────────────────────┤
        │  经典问题 (distributed algorithmics)                             │
        │  failure detection │ asynchrony │ snapshots │ multicast          │
        │  consensus │ mutual exclusion │ election │ logical time          │
        ├──────────────────────────────────────────────────────────────────┤
        │  并发与复制 (concurrency & replication)                          │
        │  RPC │ concurrency control │ replication control │ Paxos │ Raft   │
        ├──────────────────────────────────────────────────────────────────┤
        │  安全 (security)                                                 │
        │  ACL │ capabilities │ 认证 / 授权 / 加密                          │
        └──────────────────────────────────────────────────────────────────┘
                     ↑ 全部建立在同一个底座之上 ↓
        autonomous entities + asynchronous + failure-prone + unreliable links

• 关于 AI 时代的一点说明（讲义强调）：不要因为 “AI 能写代码” 就跳过自己写与调试 MP 的过程。理由是一个乘法比喻：AI 是能力放大器，但 $0 \times 1000 = 0$——对概念、系统、算法的理解为零，放大之后仍然是零。提示词表达的是意图，而真正的工程是权衡、性能、可维护性与架构品味，这些只能靠亲手写、读、调试代码获得。

1.2.2 经典定义及其不完备性（Classical Definitions and Their Inadequacy）

课程先走一条”从操作系统定义出发”的类比路线：问”什么是操作系统”，FOLDOC 的回答是”处理外围硬件、调度任务、分配存储、并在没有应用程序运行时向用户呈现默认界面的底层软件“。这个定义是”功能罗列式“的，它描述 OS 做什么，而不是 OS 为什么难。分布式系统的经典定义有同样的毛病。

• 直观解释：这些定义像”用餐厅的外观定义一顿饭“——”看起来像餐厅”“有多张桌子”“有共享厨房”都能描述外观，对要做菜的人却毫无指导意义。唯有 Lamport 的定义从”你凌晨两点被叫醒”的角度描述问题：它不说系统是什么，而说系统会怎样伤害你。
• 为什么对”想看内部机制的人”不够用：课程给出三条理由，正对应课程关心的三类工作：设计与实现（不告诉你状态放哪、复制几份、要不要中心节点）、维护（不告诉你故障如何定位、恢复、升级）、算法学（不告诉你延迟无界意味着什么、在什么假设下能达成共识）。
• 一个精妙的旁注（FA2025 补充）：讲义引用了美国最高法院大法官 Potter Stewart 关于”什么是淫秽”的著名说法——”I know it when I see it“（我看到就知道）。这正是”分布式系统”这个词的处境：它更像一个家族相似概念，而非可判定谓词。所以本课程不纠缠定义之争，而是给出一个可操作的工作定义。
• 课堂思考题素材（FA2025）：”(A) Facebook 的人类社交网络图 与 (B) Gnutella 点对点文件共享系统，哪个是分布式系统？”答案是 (B)：(A) 只是被建模成图的数据结构，其”边”是人际关系而非通信链路，不存在”自治实体 + 通信介质”；而 (B) 的每个节点是进程（entity），节点间的 TCP 连接是通信介质。“有图的形状”不等于”是分布式系统”。

1.2.3 本课程的工作定义（A Working Definition）

A distributed system is a collection of entities, each of which is autonomous, programmable, asynchronous and failure-prone, and which communicate through an unreliable communication medium.

分布式系统是一组实体，其中每一个都是自治的、可编程的、异步的、易发生故障的，并且它们通过不可靠的通信介质进行通信。

配套术语（讲义原文口径）：

• Entity = a process on a device（实体 = 某台设备上的一个进程）。设备可以是 PC、PDA/移动设备、服务器、传感器。
• Communication Medium = wired or wireless network（通信介质 = 有线或无线网络）。
• 课程的兴趣点：design and implementation（设计与实现）、maintenance（维护）、algorithmics（算法学/协议）。

逐词解剖：五个形容词分别约束了什么

• 直观解释：把这五个词想成一场用对讲机指挥的救援行动：每个队员有自己的判断（autonomous）；无法保证他们都受过正确训练（programmable 的双刃剑）；对讲机延迟可能是 1 秒也可能永不（asynchronous）；队员可能中途昏倒而其他人照常继续（failure-prone + partial failure）；对讲机还会吞字、重复播放（unreliable）。单机里”理所当然”的东西，这里一条都不成立。
• 课堂追问（讲义原题）：”我们的工作定义适用于 HTTP Web 吗？适用，而且逐条对得上。”下面这张对照表建议牢记，考试与作业中常需要它：

• 关键假设与系统模型：本课程默认的系统模型即由此定义导出——异步消息传递系统（asynchronous message-passing system）+ 允许崩溃故障（crash），通道可能丢消息。这是一个最弱、因而最难（也最通用）的模型。多处理器/共享内存并行系统属于同步模型（synchronous system model）：总线/互连的通信延迟有明确上界、处理器共享同一个物理时钟、通常不存在”部分故障”（要么整机歇工）。讲义把这一对比反复强调，因为它决定了整整两类算法世界：

  同步模型 (multiprocessor / parallel system)        异步模型 (distributed system)
  ───────────────────────────────────────────        ──────────────────────────────────────────
   | P1 |══| P2 |   共享内存/总线/NoC                | P1 |~~( lossy, unbounded delay )~~| P2 |
   通信延迟有上界 Δ，处理速度有上界                   无延迟上界、无速度上界
   同一个物理时钟可被所有处理器读取                    每个实体有自己的时钟，偏移与漂移无人修正
   "部分故障"基本不存在（共享内存一坏全坏）            部分故障是常态：一半活着，一半死了
   => 超时可以精确判定故障                            => 超时只能"怀疑"（false suspicion 不可避免）
   => 共享变量 + 锁 + 屏障 + 原子指令                  => 消息传递 + 重传 + 冗余 + 协商
   => 复杂度常用"轮数"衡量                            => 复杂度必须考虑消息数与消息大小

这个对比是理解整门课的钥匙：Lecture 12 讲”为什么需要逻辑时钟”、Lecture 17 讲”FLP 不可能性（在一个异步系统中，即使只有一个进程可能崩溃，也不存在既保证安全性又保证活性的确定性共识算法）”——它们的根源都是”异步 + 部分故障”这两个前提。换句话说：如果我们的系统是同步的，本课程一大半内容都不用学了。

1.2.4 分布式系统的实例分类（A Taxonomy of Examples）

课堂提问”Can you name some examples of distributed systems?”的完整答案清单，以及每一类所突出的设计要点（这张表在后续各讲会被反复引用）：

• 直观解释：分类的判据从来不是”用了什么技术”，而是回到工作定义的三问：实体是什么？介质是什么？自治与故障体现在哪里？ 例如 Gnutella：实体是参与者的进程，介质是邻居之间维护的 TCP 连接所构成的覆盖网（overlay），自治体现在没有服务器告诉你该连谁；数据中心：实体是服务器上的进程，介质是多层交换网络，自治体现在每台机器的故障必须被系统而非管理员掩盖。
• 机制图解（P2P overlay 与底层物理网的关系）：

   物理网络 (underlay):            [A]────────[B]              [C]───────[D]
                                     │  ╲       │                │  ╲
   覆盖网 (overlay, 逻辑链路):        │   ╲      │                │   ╲
                                    [A]───[D]  [B]              [C]───[A]
   每个节点只认识自己的邻居；一条"逻辑链路"实际穿过若干物理跳
   → 覆盖网可自由选择拓扑：环 / 网格 / DHT / 随机图
   → 这是"自治实体 + 不可靠介质"下能做的最重要工程手段之一：用逻辑结构换取可控性

• 关键假设与系统模型：不同实例的故障模型差别极大。云服务里”机器崩溃”是常态（因此要设计成 stateless + 复制）；IoT 里”节点长时间失联”是常态（因此要设计成间歇连接容忍）；Blockchain 里参与者可能是恶意的（因此需要 Byzantine 容错，见 Lecture 19）。先确定故障模型，再选算法，这是本课程的一条纪律。

1.2.5 互联网结构复习（The Internet: A Refresher）

讲义强调：互联网是许多分布式系统赖以运行的基础设施（underlies many distributed systems）。它是一个”由多种类型的计算机网络互连而成的庞大集合“。核心词汇：

• 直观解释：把互联网想成小区内部道路 + 城市主干道 + 城际高速 + 门禁：LAN = 小区内路（延迟低、拓扑稳），intranet = 整个园区，ISP = 接入运营商，backbone = 城际高速（带宽极大），MAN = 城市主干工程（Google Fiber、UC2B），firewall = 门禁。一个 HTTP 请求可能穿过全部层级，每一层都是延迟与故障的来源。
• 机制图解（一个典型 intranet 上运行的分布式系统）：

                  +--------- the Internet (WAN) ------------------------+
                  | ISPs, backbone fiber/satellite, MANs                |
                  +==========================+==========================+
                                             |  WAN link (ISP modem)
                                             |
                                  +---------------------+
                                  | router / firewall   |
                                  +----------+----------+
                                             |
    +----------------------------------------+------------------------------+
    | LAN backbone: Ethernet / WiFi switch fabric                           |
    +-----+--------------+--------------+--------------+--------------+-----+
          |              |              |              |              |
    +-----------+  +-----------+  +-----------+  +-----------+  +-----------+
    | Desktop   |  | Web       |  | File      |  | Email     |  | Print &   |
    | clients   |  | server    |  | server    |  | server    |  | servers   |
    +-----------+  +-----------+  +-----------+  +-----------+  +-----------+

Notes:  * intranet = this whole subnetwork, run by one company/org;
        * the firewall filters in/out messages by configurable rules;
        * over this intranet runs a distributed file system (e.g. NFS).

这张图能直接回答讲义的两个提问：”实体（nodes）是什么？通信介质（links）是什么？“——实体是五个方框里各自的进程（客户端进程、Web 服务器进程、文件服务器进程、邮件服务器进程、打印服务进程）；介质是 LAN backbone 上的一条条链路（有线以太网/无线 WiFi），再往外经 router/firewall 接入 WAN，最终接入互联网。同一个 intranet 上同时跑着多个分布式系统（分布式文件系统 NFS、邮件系统、Web 服务），它们的通信介质和安全边界是共享的——这就是为什么”一个你甚至不知道存在的机器”的故障会拖垮你的服务（回到 Lamport 的定义）。

• 关键假设与系统模型：真实互联网不满足任何”延迟上界”承诺（本质异步），且其拓扑会变化、存在多管理域（multi-domain，没有单一管理员）、链路带宽跨度极大。讲义给出的量化区间值得记住：

1.2.6 网络协议栈与”分布式系统协议”的层次（Networking Stacks）

讲义用一张”应用层协议 ↔ 传输层协议”的对照表引出全课程最重要的分层定位：分布式系统协议运行在传输层之上、应用层之中。

    +---------------------------------------------------------------------+
      Distributed System Protocols   <-- CS 425 / ECE 428 lives HERE
    +---------------------------------------------------------------------+
      naming, replication, consistency, consensus, group membership, ...
    +---------------------------------------------------------------------+
                     ^                      ^
                     |  built on top of the layers below
    +---------------------------------------------------------------------+
      APPLICATION LAYER PROTOCOLS  (one per application)
        e-mail   remote   Web      file     stream   remote   internet
                 term.             xfer     multim.  file     teleph.
        smtp     telnet   http     ftp      prop.    NFS      prop.
        RFC821   RFC854   RFC2068  RFC959
    +---------------------------------------------------------------------+
      TRANSPORT LAYER PROTOCOLS   (reached via the sockets API)
        TCP      TCP      TCP      TCP      TCP or   TCP or   typical
                                            UDP      UDP      UDP
    +---------------------------------------------------------------------+
      NETWORK LAYER:   IP   (addressing + routing)
    +---------------------------------------------------------------------+
      LINK / PHYSICAL: Ethernet, WiFi, fiber, satellite, ...
    +---------------------------------------------------------------------+

讲义给出的完整对照关系（务必记住 TCP/UDP 的分工差异）：

• 直观解释：分层就像寄快递——快递公司（TCP/IP）承诺把箱子送到，但完全不理解箱子里的东西；”分布式系统协议”是箱子里的业务规则（怎么编号、丢了怎么补、重复送达怎么办、多个仓库如何对账）。注意 TCP 只保证连接内的可靠有序，超时、重传、去重仍要应用层操心（Lecture 5、6）。
• 关键假设与系统模型：分层带来两个必须警惕的推论：
  1. TCP 不等于”可靠通信介质”。TCP 提供的是字节流抽象，它的”可靠”是在连接存活的前提下成立的；一次 RPC 调用被 TCP 确认了，但应答可能在返回途中丢失，调用者无法区分”服务器没执行”与”执行了但应答丢了”。这正是 at-least-once 与 at-most-once 语义问题的根源。
  2. 分布式系统协议无法通过”换一个更好的传输层”来消灭异步性。物理定律决定的延迟上界不存在，协议层再”可靠”也无法让超时变成故障的证明。

1.2.7 HTTP：Web 的客户端-服务器模型（The HTTP Standard）

• 定义与目的：HTTP = HyperText Transfer Protocol，是 WWW 的应用层协议，采用客户端/服务器模型：
  • 客户端（client）：浏览器，负责请求、接收并”展示”WWW 对象；
  • 服务器（server）：托管网站的 WWW 服务器，按请求返回对象。
  • 版本：http1.0 = RFC 1945；http1.1 = RFC 2068，其关键改进是复用同一条连接来下载图片、脚本等对象（persistent connection）。
• 直观解释：HTTP 是”一次一次地点菜“。HTTP/1.0 是”每点一道菜就重开一次餐厅大门”（每个对象一条 TCP 连接，每个连接至少一个 RTT 的握手成本）；HTTP/1.1 是”坐下之后同一张桌子连续上菜”（persistent connection 复用同一条 TCP 连接）。这个改进是纯工程权衡：它用”服务器要维护连接状态（资源占用）”换”客户端少付握手 RTT”。
• 机制图解（一次典型的 HTTP 交互）：

        BROWSER (http client)                           HTTP SERVER (Apache)
        PC running Chrome                               host www.cs.illinois.edu
        |                                               |

        |----------------------------------------------->  1a. initiate a TCP connection to port 80 (creates a socket)
        |                                               |

        |----------------------------------------------->  2.  GET /index.html HTTP/1.1      <- application-layer message

        <-----------------------------------------------|  3.  response: index.html  (references 10 JPEG images)
        |                                               |

        |<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>  4.  close the TCP connection   [HTTP/1.0: 1 object per connection]

        |----------------------------------------------->  5.  steps 1-4 repeat for each JPEG -> 11 TCP handshakes in total
           (HTTP/1.1 reuses ONE connection and pipelines all 11 objects)
        |                                               |

  time   v    (messages flow downwards)

• 协议细节：① 客户端主动发起到服务器端口 80 的 TCP 连接（创建 socket）；② 服务器接受（accept）该连接；③ 双方交换 http 消息（应用层协议消息）；④ 关闭 TCP 连接。其中 非持久连接（non-persistent） 为每个对象建一条连接（某些浏览器并行开多条，每对象一条），持久连接（persistent） 则在同一条 TCP 连接内传完多个对象。
• “http 是无状态的（stateless）”：服务器不保存任何关于过去客户端请求的信息。讲义特意追问”为什么？“并给出理由链：维护会话状态的协议是复杂的——(1) 必须保存并更新历史（状态）；(2) 如果服务器或客户端崩溃，双方对”状态”的认知可能不一致，因而必须进行协调（reconcile）。这正是”RESTful 协议是无状态的“这一设计原则的来源。注意这条链路与本课程主线的呼应：状态 = 一致性负担；一旦引入状态，就必须处理”崩溃后状态不一致”这一分布式系统核心难题（参见 Lecture 15、16 的事务与复制控制）。
• 动手练习（FA2025 补充）：用 telnet www.google.com 80 打开到端口 80 的 TCP 连接，键入 GET /index.html（可能需回车两次），即可看到服务器返回的原始 HTTP 报文——应用层协议不过是一串约定格式的文本。
• 关键假设与系统模型：HTTP 是请求-应答（request-response）式的同步 RPC 风格交互，其底层依赖 TCP 的可靠有序字节流；但 HTTP 本身不提供任何”调用恰好发生一次”的保证——网络中断后重试可能让服务器执行两次（例如重复下单）。这就是为什么真实系统需要幂等键（idempotency key）、请求去重等机制。

1.2.8 系统模型：异步 vs 同步 —— 全课的钥匙

把 1.2.3 的结论单独提出来强调，因为它决定了后面每一讲的算法长什么样。

• 定义：
  • 异步系统模型（asynchronous system model）：不假设消息延迟上界，也不假设进程相对速度上界。消息可以任意晚到达，进程可以在任意长时间内不被调度。
  • 同步系统模型（synchronous system model）：存在已知常数 $\Delta$（消息延迟上界）与 $\Phi$（进程步长上界），使得一个消息必在 $\Delta$ 内送达、一个进程每 $\Phi$ 时间至少执行一步。
• 本课程的核心前提 = 异步 + 不可靠通信，其后果是链式的：

   前提：异步 + 不可靠通信 + 部分故障
        │
        ├─► 没有全局时钟，无法用物理时间判断因果序 ──► 需要逻辑时钟 / happens-before
        │                                              （Lecture 12：Lamport 时钟、向量时钟）
        │
        ├─► 超时不是故障证明：慢、丢消息、崩溃不可区分 ──► 故障检测器不可能完美
        │                                              （只能给出"怀疑"，且会有 false suspicion）
        │
        ├─► "等一会儿再决定"没有意义 ──────────────► 共识在异步下不可能同时保证安全性与活性
        │                                              （Lecture 17：FLP 不可能性）
        │
        └─► 那么工程上如何前进？───────────────────► 用"部分同步"假设 / 随机化 / 多数派法定人数
                                                        （Paxos、Raft = 安全优先，活性靠假设）

• 直观解释：同步系统像”有统一上课铃的学校“——铃响 5 分钟之内所有人必然到齐，所以”某人没来”是可判定的；异步系统像”靠写信联系的笔友“——信可能明天到、可能明年到，所以你永远不能说对方”没回信”就是”不存在”。
• 关键假设与系统模型（对比表）：

• 务必记住的结论：”多核编程不是分布式系统编程“。你在多核上写 std::atomic、pthread_mutex、OpenMP barrier 得到的正确性论证，无法迁移到分布式环境，因为那套论证依赖”有界延迟 + 共享时钟 + 无部分故障”。反过来，本课程学到的偏序关系、法定人数、副本一致性推理，在单机并发里也同样成立（而且更有用）。这就是为什么”分布式系统”这门课在很多学校被当作”并发与容错的进阶课”。

1.2.9 讲义列出的”重要问题”（Important Distributed Systems Issues）

讲义用一页列出分布式系统的”物理现实”，可作为性能与容错的核对表：没有全局时钟，不存在单一的、全局认可的”正确时间”（asynchrony）；组件故障不可预测——可能是 fail-stop（进程停止），也可能在停止后恢复（crash-recovery），而且”没有响应”的三种成因（网络组件故障、网络路径断开、主机崩溃）不可区分，这正是最难之处；带宽高度可变（16 Kbps 的慢速调制解调器 → Gbps 的 Internet2 → 同一大公司数据中心之间的 Tbps）；延迟可能很大且高度可变（几毫秒到若干秒）；主机数量跨度极大（2 台到数百万台）。

1.2.10 分布式系统的核心挑战与设计目标（Design Goals）

讲义给出了一份典型设计目标清单（Common Goals），Coulouris 教材第 1 章给出的是另一份特征/挑战清单。两者是同一件事的两种切法，下表给出对应关系与完整展开。

（一）讲义版九条目标 + Coulouris 版对照

（二）异构性（Heterogeneity）

• 挑战：异构发生在网络、计算机硬件、操作系统、编程语言、以及不同开发者实现的同一标准这五个层面。
• 应对：中间件（middleware）——一层位于操作系统与应用程序之间的软件，提供统一的编程抽象（如统一的 RPC、统一的命名与安全机制），把底层的差异掩盖起来。Web 浏览器/服务器、RPC 机制本身都是”异构屏蔽器”。还有移动代码（mobile code）、虚拟化等手段。
• 讲义提问的实质：”can the system handle a large variety of types of machines and devices?”——它问的不是”能不能跑起来”，而是在混合环境中是否仍然只有一套语义。

（三）开放性（Openness）

• 挑战：开放意味着关键接口被发布（published）、使用标准表示与协议，从而不同厂商的组件可以互操作；并且可以被增补新服务而不破坏已有服务。
• 应对：发布接口定义（IDL、标准协议如 HTTP/DNS）、可扩展的机制（如允许新增服务/新增属性而不修改既有客户端）。
• 反面教材：私有二进制协议 + 私有数据格式 → 生态封闭，任何新功能都要改动所有使用者。

（四）安全性（Security）

• 挑战：系统天然暴露于窃听、伪装、拒绝服务、消息篡改之下，必须同时保证机密性、完整性、可用性。
• 难点：安全机制必须覆盖所有组件（一个组件被攻破即整体失效），必然带来性能与复杂度开销，且系统内部存在信任边界。
• 应对：加密、认证与授权（ACL、capabilities）、审计、沙箱、最小权限。

（五）可扩展性（Scalability）

• 挑战：讲义用具体数字提问——能否支撑 1 亿节点？60 亿？Coulouris 把”规模”拆成三维：规模可扩展性（用户与资源数增长）、地理可扩展性（距离增长，延迟是主要敌人）、管理可扩展性（跨多个独立管理域）。
• 扩展失败的三个根源：集中式服务、集中式数据、集中式算法（决策需要全局信息）。
• 四种主要技术及其代价：

• 量化直觉：单副本可用性 $a$、$N$ 个副本的可用性为 $A_{sys}=1-(1-a)^N$；$a=0.99,N=3$ 时 $A_{sys}=1-10^{-6}$（从”三个九”跳到”六个九”）。但这只在故障独立时成立——同一机架/电源/软件 bug 会让有效 $N$ 退化为 1，公式给出的是虚假的安全感。

（六）故障处理（Failure Handling）

这是分布式系统与其它领域最本质的区别，讲义用四条手段总结：

• 冗余是容错的唯一武器，而冗余的代价是一致性。讲义明确指出：故障在异步系统下无法被完美检测（”no response”可能源于网络组件失败、路径断开或主机崩溃），因此所有故障检测器都只提供怀疑，必然存在误判（false suspicion）。

（七）并发（Concurrency）

• 挑战：”can the server handle multiple clients simultaneously?” 并发在分布式环境下带来两个额外难度：(1) 真正的物理并行（不是时间片轮转），因此竞态是真随机发生的；(2) 并发单元分散在多台机器上，没有全局锁。
• 应对：服务端并发模型（进程/线程/事件驱动）、并发控制（锁、乐观并发控制、MVCC）、复制控制（顺序化、Paxos/Raft）。

（八）透明性（Transparency）与它的八种类型

• 术语警示（讲义原话）：“warning: term means the opposite of what the name implies!” ——英语里 “transparent” 通常意味着”你能看穿它”，但在分布式系统里，透明性意味着隐藏内部细节，让使用者看不见分布。”access transparency” 不是”访问是透明的（可见的）”，而是”访问方式上的差异被隐藏“。这个术语陷阱在考试与论文阅读中都会造成误读。
• Coulouris 定义的八种透明性（这是本讲最需要背下来的表）：

• 一个关键判断：透明性不是越高越好。它是有代价的设计选择，并且常常与性能、可观测性、正确性冲突——这正是 1.3 节要系统分析的内容。

（九）服务质量（Quality of Service, QoS）

• 定义：系统满足非功能性需求的能力；Coulouris 强调 QoS 适用于操作系统、网络与分布式系统三个层次，并把质量维度分为四类：

• 工程含义：要”保证”QoS，系统必须能指定（specify）→ 协商（negotiate）→ 监控与执行（police），手段包括资源预留、准入控制、流量整形、优先级调度——与”尽力而为（best-effort）”形成对比。

（十）效率（Efficiency）

讲义问的是”服务是否足够快？是否用满了 100% 的资源？”。两个陷阱：“用满资源”未必是目标——排队论下利用率趋近 1 时排队延迟迅速发散；效率必须包含通信开销（消息数与消息大小），而不仅是本地 CPU。

1.3 系统设计目标的权衡分析

本讲没有核心算法，取而代之的是本课程最重要的思维方式：设计目标的权衡（trade-off analysis）。讲义本身也反复暗示这些目标互相冲突（”如果到目前为止的内容让你困惑，你是对的，这是刻意的”），下面把它系统化。

1.3.1 为什么设计目标必然冲突：目标冲突矩阵

八条目标两两之间并非都独立。下表给出定性冲突关系：✗ 直接冲突、~ 有条件冲突（取决于实现与负载）、 基本正交或协同。用”透明性”作为例子读第一行：它对访问/位置透明是”免费”的，但一旦要做到故障透明，就必然与性能（重试/超时开销）、可观测性（故障被隐藏）、乃至安全性（隐藏了攻击痕迹）产生张力。

冲突的共同根源只有一个：任何”隐藏复杂性”或”增加能力”的机制，都需要额外的信息、额外的通信或额外的协调，而这三样东西在分布式系统里都是有限且昂贵的。下面把最有代表性的几对冲突展开。

1.3.2 冲突对一：透明性 vs 性能与可观测性

冲突根源：位置透明性要求访问一个资源时不需要知道它在哪，这必然引入间接层（indirection）——查表、代理、重定向。每多一层间接，就多一跳通信、多一次失败机会。

量化推演（尾延迟放大，tail amplification）：设某服务单次调用的”慢”概率为 $p=1\%$。若一个用户请求需要顺序访问 $n=10$ 个这样的服务（每个都必须等待前一个），则用户请求”至少命中一次慢”的概率是

也就是说：十个”P99 = 慢阈值”的服务组合起来，用户看到的 P90 就已经越过了该阈值。如果再叠加故障透明（自动重试），重试会让尾延迟进一步放大：一次请求最多重试 $k$ 次时，最坏延迟接近 $k$ 倍，且重试流量会在拥塞时形成正反馈（重试风暴）。

1.3.3 冲突对二：可扩展性 vs 一致性（CAP 的初步张力）

冲突根源：要扩展到数百万节点，只能分片（partition）加复制（replicate）。而一旦数据分布在多台机器上，任何”需要全局唯一答案”的操作就变成了协调问题。

• 分片的直接收益：单分片负载降为 $1/N$，吞吐近似线性增长。
• 分片的直接代价：跨分片操作。一个跨 $k$ 个分片的事务需要 $2k$ 条以上消息与两阶段提交（2PC），延迟与失败概率都随 $k$ 上升。
• 复制的直接代价：写操作必须落到多个副本。用法定人数（quorum）读写：$N$ 个副本，写需 $W$ 个确认，读需 $R$ 个应答，则

因此读到的至少有一个副本携带最近一次写入的值，配合版本号（如 $v’ > v$）即可保证读到不早于该次写的数据。极端取值对应两种系统：

补充说明：CAP 猜想由 Brewer 于 2000 年提出、Gilbert 与 Lynch 于 2002 年给出形式化证明：在存在网络分区的异步模型中，无法同时保证一致性（linearizability）与可用性。本课程将在共识与复制部分（Lecture 15–18）完整展开，此处只需建立”分区一出现就必须二选一”的直觉。

可扩展性本身的分类（前文 1.2.10（五））与四种扩展技术给出一张综合对照：

1.3.4 冲突对三：故障处理 vs 效率，以及并发 vs 一致性

1.3.5 一个权衡决策流程（可直接套用的推理框架）

导论课没有算法，但”如何在冲突目标中做决策”本身可以写成一个明确的决策过程。以下流程把抽象原则变成可复用的检查清单：

输入：一个待设计的功能 F，以及它的使用场景 S

(1) 确定故障模型与系统模型（这是唯一不能妥协的一步）
    if S 跨越不可靠网络 or 多台独立机器:
        assume 异步 + 可能丢消息 + crash-recovery 故障        # 本课程默认模型
    else:
        assume 同步模型（可用超时精确判故障）                  # 例如单机多线程、共享内存多核
    note: 模型假设错了，后面所有推理都是无效的

(2) 列出 F 涉及的状态，并标记每一份状态的重要性等级
    for each state item x:
        classify(x) in {可丢失(可重算), 必须持久, 必须全局唯一}

(3) 对"必须全局唯一"的状态，必须选一个协调方案（不能靠缓存解决）
    if 允许在分区时拒绝服务:
        选 强一致（多数派法定人数 / Paxos / Raft），并把 W 设为多数派
    else:
        选 最终一致 + 冲突解决策略（LWW / CRDT / 应用层合并），并显式声明冲突语义

(4) 对"可丢失/可重算"的状态，优先用缓存与复制换性能，但必须定义失效策略
    TTL = 可接受的陈旧度上界；写穿(write-through) or 回写(write-back)

(5) 检查透明性的每一类是否值得开启
    对每一类 T ∈ {access, location, migration, relocation,
                  replication, concurrency, failure, persistence}:
        if 开启 T 会让 故障诊断 或 尾延迟 不可接受:
            关闭 T，把分布显式暴露给调用者（很多真实系统主动这么做）

(6) 计算代价并验证不是"虚假的可扩展性"
    写放大 = 副本数 N；读放大 = 一次逻辑读打到的副本数
    if 有效副本数受相关性故障（同机架/同软件）影响而退化为 1:
        重做冗余布局（跨机架、跨 DC、跨版本）

(7) 用最坏情况倒推（而不是平均情况）
    P(至少一次慢) = 1 - (1-p)^n        # n = 串行依赖调用数
    可容忍的最坏时间 = deadline；若重试会让最坏时间超过 deadline，则重试必须有预算(budget)

输出：一份"目标优先级 + 显式假设 + 代价清单"，而不是一句"我们要高可用、高一致、可扩展"

该流程的可操作性来自第 (7) 步：绝大多数系统设计事故不是”选错了目标”，而是没有把目标之间的冲突写下来，导致在实现阶段用平均情况糊弄过去。

1.3.6 一个完整推演：无状态服务端 vs 有状态服务端

用讲义中 HTTP 的 “stateless” 讨论做一次完整推演（这道题在整门课中反复出现）：

结论（即讲义追问 “RESTful protocols are stateless. Why?” 的答案）：状态是分布式系统的债务。把状态推给客户端换来自由扩展与简单恢复，代价是请求上下文更大、服务端无法利用历史优化。”状态放在哪里”是后续 GFS、KV 存储、Paxos/Raft 反复出现的同一道题。

1.4 代码示例与分布式实现

本讲的代码目标不是实现某个算法，而是亲手把工作定义的五个形容词变成可运行的东西，从而对后续算法”为什么必须这样写”建立直觉。示例一在 localhost 上用 UDP 实现一个最小的键值服务系统，示例二用最小代码演示异步模型与”没有全局时钟”这两个前提。

1.4.1 示例一：最小的分布式键值系统（自治 + 不可靠介质 + 并发）

下面两段代码拼成一个文件 minimal_dist.py（第一段是服务端与”不可靠介质”层，第二段是客户端与主流程），直接 python3 minimal_dist.py 即可运行。

代码段 A：不可靠通信介质 + 并发幂等的服务端

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
minimal_dist.py -- 最小的分布式系统原型（UDP 键值服务）

覆盖本课程工作定义中的三个特征：
  1) 自治实体   : 每个客户端线程独立发起请求、独立重传、独立超时
  2) 不可靠通信 : UDP + 显式丢包/重复投递模拟
  3) 并发       : 服务端 thread-per-request，客户端多线程并发访问
"""

import json
import random
import socket
import threading
import time

HOST = "127.0.0.1"
PORT = 50517

LOSS_RATE = 0.10          # 单向丢包率（请求与应答都会丢）
DUP_RATE = 0.05           # 重复投递率
CLIENT_TIMEOUT = 0.15     # 客户端等待应答的超时（秒）
MAX_RETRY = 20            # 最大重传次数

N_CLIENTS = 4
OPS_PER_CLIENT = 25


class UnreliableChannel:
    """把 UDP socket 包一层，显式模拟"不可靠通信介质"。"""

    def __init__(self, sock, loss_rate=LOSS_RATE, dup_rate=DUP_RATE, seed=0):
        self.sock = sock
        self.loss_rate = loss_rate
        self.dup_rate = dup_rate
        self.rng = random.Random(seed)
        self.lock = threading.Lock()
        self.sent = 0
        self.dropped = 0
        self.duplicated = 0

    def sendto(self, payload, addr):
        with self.lock:
            self.sent += 1
            if self.rng.random() < self.loss_rate:
                self.dropped += 1
                return False
            self.sock.sendto(payload, addr)
            if self.rng.random() < self.dup_rate:
                self.duplicated += 1
                self.sock.sendto(payload, addr)
            return True


class KVServer:
    """并发、幂等的键值服务端：状态 = 字典 + 版本号 + 已处理请求 id 集合。"""

    def __init__(self, host=HOST, port=PORT):
        self.addr = (host, port)
        self.data = {}            # 客户端写入的键值
        self.counters = {}        # 服务端原子自增计数器
        self.version = 0
        self.applied = set()      # 幂等去重表（只对写操作）
        self.lock = threading.Lock()
        self.handled = 0          # 已处理请求数（本应是共享状态，必须加锁）
        self.dups = 0             # 被去重表拦下的重复请求数
        self.sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
        self.sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
        self.sock.bind(self.addr)
        self.sock.settimeout(0.2)
        self.channel = UnreliableChannel(self.sock, seed=7)
        self.stop = threading.Event()
        self.workers = []

    def execute(self, req):
        """在锁的保护下原子地执行一个请求 —— 服务端的并发控制。"""
        op, key, req_id = req["op"], req["key"], req["id"]
        with self.lock:
            self.handled += 1
            if op != "GET":                       # 写操作必须去重
                if req_id in self.applied:
                    self.dups += 1
                    return {"id": req_id, "status": "DUP", "value": None}
                self.applied.add(req_id)
            if op == "PUT":
                self.data[key] = req["value"]
                self.version += 1
                return {"id": req_id, "status": "OK", "value": req["value"]}
            if op == "INCR":
                self.counters[key] = self.counters.get(key, 0) + 1
                self.version += 1
                return {"id": req_id, "status": "OK", "value": self.counters[key]}
            if op == "GET":
                return {"id": req_id, "status": "OK", "value": self.data.get(key)}
            return {"id": req_id, "status": "ERR", "value": None}

    def handle(self, payload, peer):
        """thread-per-request：每个请求一个工作线程。"""
        try:
            req = json.loads(payload.decode())
        except Exception:
            return
        resp = self.execute(req)
        self.channel.sendto(json.dumps(resp).encode(), peer)

    def run(self, stop_event):
        while not stop_event.is_set():
            try:
                payload, peer = self.sock.recvfrom(4096)
            except socket.timeout:
                continue
            except OSError:
                break
            w = threading.Thread(target=self.handle, args=(payload, peer), daemon=True)
            w.start()
            self.workers.append(w)

代码段 B：自治的客户端（自带重传与超时）+ 主流程与校验

def client(client_id, stat, stop_event):
    """一个自治实体：自己决定发什么、自己重传、自己超时。"""
    sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
    channel = UnreliableChannel(sock, seed=1000 + client_id)
    stat.update({"put_ok": 0, "incr_ok": 0, "dup": 0, "retries": 0,
                 "issues": 0, "timeouts": 0, "put_keys": set()})

    def rpc(op, key, value, req_id):
        stat["issues"] += 1
        payload = json.dumps({"id": req_id, "op": op,
                              "key": key, "value": value}).encode()
        for attempt in range(1, MAX_RETRY + 1):
            if attempt > 1:
                stat["retries"] += 1
            channel.sendto(payload, (HOST, PORT))
            deadline = time.time() + CLIENT_TIMEOUT
            while True:
                left = deadline - time.time()
                if left <= 0:
                    break
                sock.settimeout(left)
                try:
                    raw, _ = sock.recvfrom(4096)
                except socket.timeout:
                    break
                resp = json.loads(raw.decode())
                if resp.get("id") == req_id:      # 忽略过期/串包的应答
                    return resp
        stat["timeouts"] += 1
        return {"id": req_id, "status": "TIMEOUT", "value": None}

    for j in range(OPS_PER_CLIENT):
        if stop_event.is_set():
            break
        key = "k%d_%d" % (client_id, j)
        value = "v%d_%d" % (client_id, j)
        resp = rpc("PUT", key, value, "c%d-p%d" % (client_id, j))
        if resp["status"] == "OK":
            stat["put_ok"] += 1
            stat["put_keys"].add((key, value))
        elif resp["status"] == "DUP":
            stat["dup"] += 1
        # 所有客户端并发自增同一个共享计数器
        resp = rpc("INCR", "shared_counter", None, "c%d-i%d" % (client_id, j))
        if resp["status"] == "OK":
            stat["incr_ok"] += 1
        elif resp["status"] == "DUP":
            stat["dup"] += 1


def main():
    server = KVServer()
    stop_event = threading.Event()
    srv = threading.Thread(target=server.run, args=(stop_event,), daemon=True)
    srv.start()
    time.sleep(0.2)                      # 等 bind 完成

    results = [{} for _ in range(N_CLIENTS)]
    threads = [threading.Thread(target=client, args=(i, results[i], stop_event))
               for i in range(N_CLIENTS)]
    t0 = time.time()
    for t in threads:
        t.start()
    for t in threads:
        t.join()
    elapsed = time.time() - t0
    stop_event.set()
    srv.join(timeout=2.0)
    for w in server.workers:
        w.join(timeout=1.0)

    print("=" * 62)
    print("服务端状态：keys=%d  counter=%d  version=%d"
          % (len(server.data), server.counters.get("shared_counter", 0), server.version))
    print("服务端计数：handled=%d  被去重的重复请求=%d" % (server.handled, server.dups))
    print("介质统计  ：服务端发出 %d 包，丢 %d，重复 %d"
          % (server.channel.sent, server.channel.dropped, server.channel.duplicated))
    print("-" * 62)
    total_put_ok = total_incr_ok = total_retries = total_timeouts = total_dup = 0
    for i, r in enumerate(results):
        print("client%d: put_ok=%2d incr_ok=%2d dup=%2d retries=%2d timeout=%d"
              % (i, r["put_ok"], r["incr_ok"], r["dup"],
                 r["retries"], r["timeouts"]))
        total_put_ok += r["put_ok"]
        total_incr_ok += r["incr_ok"]
        total_retries += r["retries"]
        total_timeouts += r["timeouts"]
        total_dup += r["dup"]
    print("-" * 62)
    print("客户端合计：put_ok=%d incr_ok=%d retries=%d 重复应答=%d 超时=%d 耗时=%.2fs"
          % (total_put_ok, total_incr_ok, total_retries, total_dup,
             total_timeouts, elapsed))

    # ---- 校验 1：不可靠介质确实造成了重传，去重表确实发挥了作用 ----
    assert total_retries > 0, "没有发生重传，说明丢包模拟没生效"
    assert server.dups > 0, "没有重复请求被拦截，去重机制未被验证"

    # ---- 校验 2：一致性（服务器状态与客户端认知不冲突）----
    counter = server.counters.get("shared_counter", 0)
    issued = N_CLIENTS * OPS_PER_CLIENT
    assert total_incr_ok <= counter <= issued, \
        "计数器 double counting %d 超出已发出的不同请求数 %d" % (counter, issued)

    # ---- 校验 3：每个被确认的 PUT 都必须真的在服务器上，且值正确 ----
    for i, r in enumerate(results):
        for key, value in r["put_keys"]:
            assert server.data.get(key) == value, "键 %s 的值丢失或被覆盖" % key

    print("-" * 62)
    print("校验通过：counter=%d，客户端发出 INCR 请求数=%d（重复请求未重复计数）"
          % (counter, issued))
    print("校验通过：%d 个已确认写入全部可在服务端读回" % total_put_ok)
    if total_timeouts == 0:
        print("EXACT: 无超时，counter == 发出的 INCR 请求数 == %d" % issued)
    print("=" * 62)


if __name__ == "__main__":
    main()

实际运行输出（一次典型运行的完整输出；由于线程调度，各客户端的重传次数会小幅波动，但断言恒成立）：

==============================================================
服务端状态：keys=100  counter=100  version=200
服务端计数：handled=227  被去重的重复请求=27
介质统计  ：服务端发出 227 包，丢 18，重复 14
--------------------------------------------------------------
client0: put_ok=22 incr_ok=22 dup= 6 retries=13 timeout=0
client1: put_ok=24 incr_ok=22 dup= 4 retries=15 timeout=0
client2: put_ok=23 incr_ok=25 dup= 2 retries= 7 timeout=0
client3: put_ok=24 incr_ok=23 dup= 3 retries=12 timeout=0
--------------------------------------------------------------
客户端合计：put_ok=93 incr_ok=92 retries=47 重复应答=15 超时=0 耗时=2.27s
--------------------------------------------------------------
校验通过：counter=100，客户端发出 INCR 请求数=100（重复请求未重复计数）
校验通过：93 个已确认写入全部可在服务端读回
EXACT: 无超时，counter == 发出的 INCR 请求数 == 100
==============================================================

【代码做什么？】

1. 建立介质：UnreliableChannel 包装 UDP socket，sendto() 以 LOSS_RATE=10% 的概率吞掉数据报（丢包），以 DUP_RATE=5% 的概率发两次（重复投递）；请求与应答都经过它，故上下行都会丢。
2. 启动服务端：KVServer 绑定 127.0.0.1:50517，主循环 recvfrom，每收到一个请求就新建工作线程处理（thread-per-request 并发）。
3. 处理请求：execute() 在 self.lock 保护下原子地读改写；写操作（PUT/INCR）先查 applied 去重表，已处理过的 req_id 返回 DUP 而不重复执行；GET 天然幂等，允许重复执行。
4. 并发访问：4 个客户端线程各自独立做 25 轮操作——一个私有键 PUT k{c}_{j} 加一次共享键 INCR shared_counter。
5. 自治容错：客户端 rpc() 自己维护 deadline（CLIENT_TIMEOUT=0.15s），超时后在同一 req_id 下重发，最多 20 次；收到应答先校验 resp["id"] == req_id，不匹配的迟到应答直接丢弃并继续等待。
6. 汇总校验：主线程 join 全部客户端后打印服务端状态、介质统计与各客户端统计，并执行三条断言。

【分布式机制透视】

• 自治实体：代码里没有任何全局调度器——4 个客户端各有自己的 socket、随机种子与重传状态，服务端只被动应答，这就是 “entity = a process on a device” 的字面实现。
• 不可靠介质：用真实 UDP 并叠加显式丢包/重复注入，让”消息可能永远不到”从口号变成每次运行都能观测到的事实（retries、被去重）。
• 并发：服务端 thread-per-request，处理真正交错，故 execute() 必须加锁（self.handled += 1 这类读-改-写无锁即为竞态）；4 个客户端争用 shared_counter，其正确性由服务端的锁与去重表保证，不靠客户端自觉。
• 真实系统对应物：req_id + applied = 幂等键/去重缓存（使 at-least-once 的重传呈现 exactly-once 效果，见 Lecture 5、6）；deadline + 重传 = RPC 的 at-least-once 语义；resp["id"] 校验 = 请求匹配（HTTP/2 的 stream id）；sent/dropped 计数 = 可观测性（1.3.2 中”故障透明 vs 诊断”的折中手段）。

【与理论的对应】

本讲没有算法伪代码，但代码与 1.3.5 的决策流程、1.2.3 的工作定义逐条对应：

其中第 2 行值得单独强调：代码故意没有写”如果 0.15 秒没回就认定服务端挂了”这样的逻辑，因为那在异步模型下是错误的。它只能重传（把不确定性交给幂等性处理），而不能”判定”任何东西。这就是 1.2.8 那张因果链在本示例中的具体体现，也是 Lecture 17（FLP）将要证明其不可能性的那个问题的入口。

1.4.2 示例二：异步模型与”没有全局时钟”的最小演示

第二个示例只需 60 余行，把 1.2.8 的两个根本前提变成可以直接观察的输出。

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
sync_vs_async.py -- 本课程两个根本前提的最小演示
  1) 异步模型：不存在延迟上界，"慢"与"崩溃"在观察上不可区分
  2) 没有全局时钟：本地物理时间戳无法判断因果顺序
"""

import queue
import threading
import time


def p1_rpc(rid, req_q, rep_q, timeout):
    """P1 发起一次 RPC，超时则怀疑 P2。"""
    t0 = time.perf_counter()
    req_q.put((rid, t0))
    try:
        rep_q.get(timeout=timeout)
        return "OK      ", time.perf_counter() - t0
    except queue.Empty:
        return "SUSPECT ", time.perf_counter() - t0


def p2_loop(req_q, rep_q, delay, alive, trace):
    """P2：delay 秒后应答；alive=False 模拟 crash-stop（进程不再响应）。"""
    while True:
        item = req_q.get()
        if item is None:
            return
        rid, _ = item
        if not alive:
            trace.append("DROPPED")
            continue
        time.sleep(delay)
        rep_q.put(rid)
        trace.append("REPLIED")


def scenario(tag, name, delay, alive, timeout, skew=-0.5):
    req_q, rep_q, trace = queue.Queue(), queue.Queue(), []
    t = threading.Thread(target=p2_loop,
                         args=(req_q, rep_q, delay, alive, trace), daemon=True)
    t.start()
    verdict, elapsed = p1_rpc("r1", req_q, rep_q, timeout)
    req_q.put(None)
    t.join(timeout=1.0)

    # 假设 P1 的本地时钟为 1.000，P2 的本地时钟比 P1 慢 0.5 秒（skew = -0.5s）
    t_send = 1.000
    if "REPLIED" in trace:
        t_recv = t_send + elapsed + skew
        p2_field, note = "P2_recv=%.3f" % t_recv, ""
        if t_recv < t_send:                      # P2 的本地时间反而更早
            note = "   <-- P2 本地时钟显示：先接收，后发送！"
    else:
        p2_field, note = "P2_recv=  n/a", "   <-- P2 从未应答，无法取得时间戳"
    print("%s %-28s verdict=%s elapsed=%.3fs  P1_send=%.3f  %s%s"
          % (tag, name, verdict, elapsed, t_send, p2_field, note))


def main():
    T = 0.10
    print("=" * 104)
    print("前提 1：异步模型中不存在【延迟上界】，P1 只能用超时猜测 P2 的状态")
    print("-" * 104)
    scenario("[r1]", "P2 alive, delay=0.02s < T", 0.02, True, T)
    scenario("[r2]", "P2 alive, delay=0.30s > T", 0.30, True, T)
    scenario("[r3]", "P2 crashed", 0.00, False, T)
    print("-" * 104)
    print("观察结论：r2 与 r3 的外部观察完全相同（都是 SUSPECT）。")
    print("          即【慢】与【崩溃】不可区分；要能判定崩溃，必须额外假设一个延迟上界")
    print("          —— 那个假设就叫同步模型（synchronous system model）。")
    print()
    print("前提 2：本地物理时钟无法给事件排列因果顺序（时钟偏移 skew = -0.5s）")
    print("-" * 104)
    scenario("[r4]", "causally: P1 sends -> P2 receives", 0.02, True, T)
    print("观察结论：P1 记录的发送时刻 1.000 大于 P2 记录的接收时刻 0.520，")
    print("          而事实上接收发生在发送之后。物理时钟不能充当逻辑顺序。")
    print("=" * 104)


if __name__ == "__main__":
    main()

实际运行输出：

========================================================================================================
前提 1：异步模型中不存在【延迟上界】，P1 只能用超时猜测 P2 的状态
--------------------------------------------------------------------------------------------------------
[r1] P2 alive, delay=0.02s < T    verdict=OK       elapsed=0.020s  P1_send=1.000  P2_recv=0.520   <-- P2 本地时钟显示：先接收，后发送！
[r2] P2 alive, delay=0.30s > T    verdict=SUSPECT  elapsed=0.100s  P1_send=1.000  P2_recv=0.600   <-- P2 本地时钟显示：先接收，后发送！
[r3] P2 crashed                   verdict=SUSPECT  elapsed=0.100s  P1_send=1.000  P2_recv=  n/a   <-- P2 从未应答，无法取得时间戳
--------------------------------------------------------------------------------------------------------
观察结论：r2 与 r3 的外部观察完全相同（都是 SUSPECT）。
          即【慢】与【崩溃】不可区分；要能判定崩溃，必须额外假设一个延迟上界
          —— 那个假设就叫同步模型（synchronous system model）。

前提 2：本地物理时钟无法给事件排列因果顺序（时钟偏移 skew = -0.5s）
--------------------------------------------------------------------------------------------------------
[r4] causally: P1 sends -> P2 receives verdict=OK       elapsed=0.020s  P1_send=1.000  P2_recv=0.520   <-- P2 本地时钟显示：先接收，后发送！
观察结论：P1 记录的发送时刻 1.000 大于 P2 记录的接收时刻 0.520，
          而事实上接收发生在发送之后。物理时钟不能充当逻辑顺序。
========================================================================================================

【代码做什么？】

1. 两个实体：P2 由 p2_loop 在一个独立线程里运行，从 req_q 取请求；alive=False 时它取走消息但不回复（这正是”崩溃的进程”从外部看的样子——消息进入黑洞）。
2. P1 的 RPC：p1_rpc 发送请求后最多等 timeout=0.10s。收到应答 → OK；queue.Empty 超时 → SUSPECT。注意 P1 拿不到任何额外信息，它只有这两种输出。
3. 三个场景：r1 延迟 0.02s（小于 T）→ OK；r2 延迟 0.30s（大于 T，但 P2 完全健康）→ SUSPECT；r3 P2 真崩溃 → SUSPECT。r2 与 r3 的输出逐字符相同。
4. 时钟偏移场景：r4 里假设 P1 本地时钟读数为 1.000，P2 本地时钟比 P1 慢 0.5 秒（skew = -0.5）。P2 实际在发送之后才收到消息，但它的本地时间戳 0.520 小于 P1 的发送时间戳 1.000。

【分布式机制透视】

• 消息通道：queue.Queue 在这里充当通信介质。它是可靠的（不会丢），但演示的目的恰恰是去掉”延迟有上界”这个假设——time.sleep(delay) 把延迟变成一个不受 P1 控制的任意值。
• 进程状态与”部分故障”：alive 开关就是 crash-stop 故障模型的最小实现。关键观察是：系统整体仍在运行（P1 还在跑、还在打印），只有 P2 这一个组件失效——这就是部分故障，也是分布式系统区别于单机系统的分水岭。
• 并发与时序：r2 和 r3 的区别不在”外部可观测量”，而在”内部状态”。P1 无法观测内部状态，这就是异步模型下故障检测器（failure detector）不可能完美的根本原因。
• 真实系统对应物：心跳超时判主机存活（r2 就是”GC 停顿 300ms 导致的假死”）、Kubernetes 的 liveness probe 误杀慢容器、TCP 重传超时的指数退避（RTO 只能估计，无法证明）、微服务熔断器的误触发。

【与理论的对应】

1.5 性能与可扩展性分析

本讲没有算法，因此这里分析的是 1.4.1 那个原型系统的可扩展性瓶颈——请把它当作”如果这是一次 MP，你会在哪里撞墙”的预演。表中每一项都在后续课程里有对应解法。

1.5.1 原型的瓶颈清单

1.5.2 复杂度量化对照

1.6 关键要点

1. 工作定义是整门课的公理集：自治 + 可编程 + 异步 + 易故障 + 不可靠介质。异步（无延迟上界）与部分故障的组合是全部困难的根源；换成同步模型（共享内存多处理器），本课程一半以上的算法问题都会消失。
2. 经典定义都只描述外观。Lamport 的定义（你不知道的机器的故障能让你的机器不可用）最有信息量，因为它直指部分故障这一独有痛处；Tanenbaum/FOLDOC/Schroeder 在”用户视角”上正确，对算法设计却无用。
3. 透明性有八种，且术语反直觉（访问、位置、迁移、重定位、复制、并发、故障、持久性）：transparency 意为”隐藏“而非”看得见”；而且它不是越高越好——故障透明与可观测性、位置透明与延迟直接冲突。
4. 八大设计目标（异构性、开放性、安全性、可扩展性、故障处理、并发、透明性、QoS）两两冲突，共同根源是：任何”隐藏复杂性”或”增强能力”的机制都要消耗额外信息、额外通信或额外协调。设计者的工作是排出优先级并写下代价，而不是宣称全部满足。
5. 可扩展性的敌人是集中式：集中式服务、集中式数据、集中式算法。四种扩展手段各自欠债——分布欠跨片事务，复制欠一致性，缓存欠陈旧读，隐藏延迟欠交互性。
6. “用满 100% 资源”不是目标：高利用率必然带来高尾延迟，而尾延迟会沿调用链放大（$1-(1-p)^n$），因此必须按最坏情况倒推而不是按平均情况设计。

1.7 常见陷阱与注意事项

1. 把超时当作故障判定（timeout ≠ crash）。
   • 为什么错：异步模型中没有延迟上界，一个”慢”的进程与一个”崩溃”的进程在外部观察上完全等价（见 1.4.2 的 r2/r3）。据此做出的决定会产生 false suspicion，进而误杀健康节点、误触发主备切换，可能引发脑裂。
   • 正确做法：把超时输出当作怀疑（suspect）而非判决；用多数派/法定人数来稀释误判（要求”多数派都怀疑”才采取行动）、用租约（lease）与 fencing token 防止旧主继续写、并区分”暂时失联”与”确认失效”两类状态。
2. 把物理时钟当作逻辑顺序的依据。
   • 为什么错：时钟存在偏移（skew）与漂移（drift），NTP 只能把差距压到毫秒量级，还会因闰秒、虚拟机暂停、GC 停顿而跳变；于是”接收时间戳早于发送时间戳”这种因果倒置会真实发生（见 1.4.2 的 r4）。用墙上时钟给事件排序会得出违反因果的结论。
   • 正确做法：用逻辑时钟（Lamport 时钟定序、向量时钟捕捉并发；见 Lecture 12）；若必须用物理时间，用区间时钟/HLC 并接受不确定性区间。
3. 以为 “transparency”（透明性）意味着”用户能看见”。
   • 为什么错：”透明”容易被理解成”可见、公开”，而这里的透明性恰恰相反——隐藏分布。理解反了会推出整张透明性表的错误结论。
   • 正确做法：记成”透明 = 用户察觉不到差别“；并记住每类透明性都有代价，必要时主动放弃透明（暴露分片、暴露失效域）换取性能与可诊断性。
4. 以为”副本越多越可靠、越一致”。
   • 为什么错：$A_{sys}=1-(1-a)^N$ 只在故障独立时成立。同一机架、同一电源、同一交换机、同一份软件 bug 会让有效副本数退化为 1，而写放大、协调开销、冲突概率却随 $N$ 真实增长。多副本降低了写吞吐并提高了一致性成本。
   • 正确做法：把副本放到不同的失效域（机架/可用区/地域），并明确每份数据所需的 $R/W$ 法定人数；对写密集数据慎用高 $N$；在成本敏感场景考虑纠删码。
5. 认为”单机上跑通了，分布式就一定对”。
   • 为什么错：单机测试通常只有一种时序（本地延迟极低、无丢包、无并发交错），而分布式系统中的 bug 需要特定的消息交错 + 特定故障时刻才能触发。这类 bug 在实验室里”跑一万次没事”，在生产环境第一次网络抖动时爆发。非确定性（nondeterminism）是分布式系统的固有属性，不是测试不够努力的问题。
   • 正确做法：主动注入故障（丢包、延迟、乱序、崩溃并重启），把不确定性变成可复现的测试；用确定性重放/模型检验工具；对关键不变量写断言（就像 1.4.1 代码里的三条 assert）。
6. 重复踩”分布式计算的八个谬误”（补充）。
   • 为什么错：以下八条假设全部为假，但初学者（以及很多成熟系统）在无意识中依赖它们：① 网络是可靠的；② 延迟为零；③ 带宽无限；④ 网络是安全的；⑤ 拓扑不会变化；⑥ 只有一个管理员；⑦ 传输成本为零；⑧ 网络是同构的。（这是 Peter Deutsch 等人总结、被广泛引用的”Fallacies of Distributed Computing”。）
   • 正确做法：把每一条都翻译成设计问题——不可靠 → 幂等与重传；延迟非零 → 异步与批量；带宽有限 → 压缩与增量；不安全 → 认证与加密；拓扑可变 → 动态成员管理；多管理员 → 跨域策略；传输有成本 → 数据本地化；网络异构 → 中间件与能力协商。
7. 把”无状态（stateless）”理解为”系统里没有状态”。
   • 为什么错：HTTP 的 stateless 说的是服务器不保存跨请求的会话状态；请求本身当然带状态（URL、cookie、body），系统底层当然也有状态（TCP 连接、缓存、日志）。混淆两者会导致”无状态系统不需要一致性”这种错误推论。
   • 正确做法：把”状态在谁那里”当作一个显式的设计决策：状态放客户端 → 易扩展、难优化；放服务端 → 易优化、难恢复（见 1.3.6 的对比表）。

1.8 思考题（带答案）

Q1（计算／推演题）：某服务由 $n=10$ 个串行依赖的后端调用组成，每个后端在 $1\%$ 的请求上会发生”慢事件”（超过 P99 阈值），且各后端相互独立。 (a) 用户请求至少命中一次慢事件的概率是多少？ (b) 若为了让用户”看不到”慢事件，系统对每次慢调用自动重试一次（重试也会以 $1\%$ 概率慢），用户侧最坏延迟大约是原来的几倍？请说明这为什么是”故障透明”的代价。

答： (a) 各后端独立，用户请求”全都不慢”的概率为 $0.99^{10} \approx 0.9044$，因此 \(P(\text{至少一次慢}) = 1 - 0.99^{10} \approx 9.56\%\) 即约 9.6% 的用户请求会命中至少一个慢后端——所以这个接口的 P90 就已经超过慢阈值，即使每个后端都宣称自己只有 1% 的慢请求。

(b) 慢事件需要重试，一次请求的延迟上界变为 $2 \times$ 慢阈值（重试成功）甚至更长（多次重试）；同时重试本身会再以 $1\%$ 概率慢，且重试流量在拥塞时形成正反馈（重试风暴）。这正是”故障透明”的代价：为了让用户看不到故障，系统自动重试，于是把”后端 1% 的慢”转换成”用户侧 9.6% 的可见延迟波动 + 2 倍的最坏延迟 + 额外的网络负载”。透明性没有消除故障，只是把它从”错误”重新包装成了”延迟”——而且这个包装在链路变长（$n$ 增大）时会迅速恶化。正确做法是给重试设置预算与退避，并把 deadline 传播到下游，必要时主动降级（返回不完整但快的结果）而不是无限重试。

Q2（概念应用题）：用本课程的工作定义（autonomous / programmable / asynchronous / failure-prone / unreliable medium）逐一分析以下三个候选，判断哪些是分布式系统：(1) 一台 8 核机器上用 OpenMP 写的多线程矩阵乘法；(2) DNS 系统；(3) 一个区块链网络。

答：(1) 不是。8 核机上的多线程程序共享同一块内存与同一个物理时钟，线程间通信经缓存一致性协议，延迟有上界、无部分故障，属于同步/共享内存模型——这正是讲义强调”多处理器是同步模型”的用意；它有自己的难题（竞态、内存序），但那是本课程的前置知识。(2) 是。实体 = 递归解析器/权威服务器/根服务器进程；autonomous = 各自决定答什么、缓存多久；programmable = 任何人都能部署权威服务器；asynchronous = 无延迟上界；failure-prone = 宕机、记录过期、缓存投毒；unreliable = UDP 查询会丢，靠重传与多服务器尝试。它是”用分层命名与缓存解决位置透明性”的教科书案例。(3) 是，且最严苛。实体 = 全节点/矿工进程，介质 = P2P 覆盖网；参与者可能是恶意的，因此需要 Byzantine 容错（$3f+1$ 才能容忍 $f$ 个恶意节点，见 Lecture 19）；出块时间不可预测、节点随时上下线、区块传播延迟导致分叉。区块链把”不可信参与者”引入设计空间，这是工作定义中 programmable 一词最深刻的后果。

Q3（”直观但错误的想法”题）：某同学说：”既然 TCP 已经保证了可靠通信，我们写分布式系统时就不需要再操心丢包、重复和乱序了，直接把 TCP 当成本地函数调用就行。” 请指出这段话错在哪里（至少三点），并说明正确的做法。

答：

• 错误一：TCP 的”可靠”只在连接存活期间成立。连接一旦因超时、路由变化、中间设备重启而断开，连接内已发送但未被确认的数据就可能丢失；调用者得到的是”连接错误”，无从区分“请求没被服务器执行”和”服务器执行了但应答在返回途中丢失”。因此逻辑上的 RPC 语义仍然需要应用层设计：at-most-once（不重试但可能没执行）、at-least-once（重试但可能执行多次）、以及通过服务端去重达到 exactly-once 效果。这正是 1.4.1 中 req_id + applied 去重表存在的原因。
• 错误二：把远程调用当本地调用忽略了”延迟与故障的部分性”。本地函数调用要么返回要么抛异常，且耗时纳秒级；远程调用可能耗时几百毫秒、可能”无限期”悬挂、可能在对方已经执行之后失败。这就是”分布式计算的谬误”中”延迟为零”“网络可靠”两条的具体体现。正确做法是把远程调用显式地当作有 deadline、有重试预算、可能不确定结果的操作来设计（幂等键、客户端超时、服务端去重、断路器）。
• 错误三：TCP 不解决”跨进程的并发与顺序”。TCP 保证的是单条连接内的字节有序，两条连接之间的消息顺序没有任何保证；而分布式系统的正确性往往依赖跨客户端的全局顺序（例如两个客户端同时对同一计数器自增）。这需要服务端的并发控制与序列化，而不是传输层能提供的东西——1.4.1 中 shared_counter 的正确性完全来自服务端的锁与去重表，与 TCP 无关。
• 正确做法汇总：把传输层视为”尽力而为的字节管道“，在它之上自己定义消息语义（请求 id、序号、幂等性、超时与重试预算、deadline 传播），并假设最坏情况会发生。

Q4（设计／权衡题）：你要设计一个”校园食堂实时排队长度”服务：全校约 5 万名学生，每个食堂门口有一个传感器每 5 秒上报一次排队人数；学生手机 App 查询某个食堂的实时队伍长度。请排出设计目标的优先级，指出你会主动牺牲哪个目标以及为什么，并说明你把”状态放在哪里”。

答：优先级：① 可用性 / 可扩展性（查询量远大于上报量，且”查不到”比”数字略旧”更糟）；② 读延迟（QoS）；③ 异构性与开放性（多厂商传感器、iOS/Android 客户端、未来新增食堂）；④ 安全性（至少认证上报，防止伪造”空队”）；⑤ 一致性。

主动牺牲：强一致性与部分”故障透明”。排队长度是天然时效性数据，5 秒前的数字与 500 毫秒前的几乎无差别；为了强一致而让查询在传感器抖动时失败，是典型的”为不重要的目标牺牲重要的目标”。因此选最终一致，并以”3 秒前更新”的形式向用户暴露数据新鲜度（即主动放弃一部分故障透明），换取可用性与延迟。

状态放在哪里：传感器最新读数可以丢失（丢了等下一次上报），放内存缓存即可，无需每 5 秒持久化；为支撑 5 万学生的读，把读数复制/缓存到边缘（CDN/区域缓存，TTL 取 5–10 秒）——这正是 1.3.3 中”缓存换延迟、欠下陈旧读的债”；只有历史数据（趋势与报表）需要持久化，批量异步落盘（write-behind）即可，失败重试不影响在线服务。

防陷阱（对照 1.7）：查询路径不做重试放大（读天然幂等）；上报路径用传感器 id + 序号去重，防止网络重传导致”人数翻倍”；对异常数字做服务端合理性校验（一次上报 500 人可能是故障而非真实排队）。

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$）；内层循环最多 $

  P

  \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（一致性模型）要展开的取舍。

Lecture 3: System Models — 分布式系统模型（物理模型、体系结构模型、基础模型）

讲义对应：CS 425 的课程表把”系统模型”分散在各讲中介绍。本讲综合了以下讲义内容：L1.FA26（分布式系统的工作定义与核心问题）、L2.FA26（云与三层体系结构、数据中心物理形态）、L6.FA25（Failure Detection and Membership，含故障模型与检测器性质）、L12.FA25（Time and Ordering，含异步系统模型的正式说明与事件排序问题）、L15.A.FA25（Impossibility of Consensus，含同步/异步模型的对照与 FLP）、L17.FA25（Leader Election，含超时与不可能性的关系）。 本讲定位：Lecture 3 是由上述讲义内容与 Coulouris 教材 Ch.2 的结构综合而成的”系统模型”专题，不是某一次课的逐页内容。凡属教材结构、而非课程讲义原文的部分，文中均以「补充说明」明确标注。 教材对应：Coulouris, Dollimore, Kindberg & Blair, Distributed Systems: Concepts and Design, 5th Ed., Ch.2 System Models（2.1 Physical Models / 2.2 Architectural Models / 2.3 Fundamental Models）；Ch.1 的工作定义与设计目标。 阅读材料：L1.FA26、L2.FA26、L6.FA25、L12.FA25、L15.A.FA25；Chandra & Toueg, Unreliable Failure Detectors for Reliable Distributed Systems（JACM 1996）；Fischer, Lynch & Paterson, Impossibility of Distributed Consensus with One Faulty Process（JACM 1985）。

3.1 概述

写任何分布式算法之前，必须先回答一个前置问题：我们在一个什么样的世界里写算法？这个世界就是系统模型（System Model）——一组关于”进程如何通信、时间如何流逝、组件如何失效、谁能攻击谁”的显式假设。本讲把课程中散落的直觉形式化：先用物理模型描述系统长什么样（bus-based 到超大规模 ULS 的演进），再用体系结构模型描述软件元素怎么摆、怎么通信（client-server、多层、proxy/cache、P2P、中间件、移动代码），最后用基础模型回答”算法能假设什么”——即交互模型（同步 / 异步 / 部分同步）、故障模型（遗漏 / 时序 / 任意故障）与安全模型（窃听 / 冒充 / 篡改 / 重放 / 拒绝服务）。

本讲在整门课中处于”公理层”：Lecture 12 的逻辑时钟之所以必要，是因为异步模型下物理时钟无法给出跨进程的事件顺序；Lecture 15/17 的 FLP 不可能性之所以成立，是因为异步模型没有任何时间上界；Lecture 19 的 Paxos/Raft 之所以把安全性建立在”多数派交集”、活性建立在”最终有界”之上，是因为它们工作在部分同步模型下。同一个问题，换一个模型，可解性就从”可解”变成”不可能”——这是本讲最需要记住的事情。

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

3.2.1 课程的工作定义，以及它如何”长出”三类模型

课程给出的工作定义（L1.FA26，这是本课程的口径，务必逐字记住）是：

A distributed system is a collection of entities, each of which is autonomous, programmable, asynchronous and failure-prone, and which communicate through an unreliable communication medium. （分布式系统是一组实体，其中每个实体都是自主的、可编程的、异步的、易故障的，并且它们通过不可靠的通信介质相互通信。） —— 其中 Entity = 一台设备（PC、移动设备）上的一个进程；Communication Medium = 有线或无线网络。

它之所以”短得让人不安”，是因为只描述边界、不描述内容；但四个形容词加一个介质，恰好一一对应本讲的模型维度：

课程同时给出的两条重要旁注值得一起记住：Lamport 的调侃定义——”A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.“（分布式系统就是一台你根本不知道存在的计算机坏了，会让你自己的机器没法用）；以及课程列出的核心议题：no global clock / no single global notion of the correct time、unpredictable failures（”no response”可能来自网络组件故障、链路中断、或机器崩溃，三者难以区分）、带宽从 16Kbps 到 Tbps、延迟从几毫秒到几秒、主机数从 2 台到几百万台。本讲的全部内容，就是把这些旁注精确化。

「补充说明」：Coulouris 教材把系统模型分为三类——physical models（描述性的）、architectural models（规定软件元素的组织方式）、fundamental models（规定算法可依赖的属性）。本讲的 A/B/C 三部分即对应这三类。

3.2.2 物理模型（Physical Models）：从共享总线到超大规模系统

• 定义与目的：物理模型从最抽象的硬件层次描述一个分布式系统——有哪些节点（nodes）、它们由哪些连接通道（links）相连、规模多大、耦合多紧。它回答”这个世界长什么样”。
• 直观解释（”它是什么？”）：物理模型像一张城市地图。地图告诉你城市里有多少街区、道路怎么连、人口多少，但它不告诉你交通规则——红绿灯该多久切换、救护车能不能逆行。写算法需要的是交通规则，不是地图。这是物理模型最关键的局限，也是为什么还需要后两类模型。
• 机制图解：

     1950s-70s              1980s             1990s-2000s           2000s-10s            2010s-now
  +--------------+     +--------------+     +--------------+     +--------------+     +--------------+
  | bus-based    |     | LAN / MP     |     | Internet /   |     | cluster /    |     | ULS / cloud  |
  | shared bus   |     | cluster      |     | Web / Grid   |     | datacenter   |     | + edge       |
  | one room     | --> | building     | --> | federated    | --> | single site  | --> | planet-wide  |
  | Cray / SMP   |     | NOW, 1994    |     | Globus, P2P  |     | GFS, Hadoop  |     | serverless   |
  +--------------+     +--------------+     +--------------+     +--------------+     +--------------+
     10s nodes            100s nodes           10^6 hosts           10^4-10^5           10^6+ nodes
       单机房             单楼/园区            跨机构广域            同址万级             全球规模

逐代特征如下，其中时间轴口径取自课程 L2.FA26 的 “A Cloudy History of Time” 与 L6.FA25 的 Grid 部分：

1. 总线模型（bus-based）：1950s–1970s。所有处理器挂在同一条共享总线上，共享内存或共享介质，通信是”广播 + 仲裁”。典型系统：早期的 ENIAC/ORDVAC/ILLIAC 风格的大型机、Cray 类超级计算机、多核 SMP。关键性质：有共同的物理时钟、延迟上界极短且稳定、总线上任何消息都能被所有人看到（天然的可靠广播）。因此这一代系统天然满足同步模型——课程 L15.A 直接以”A collection of processors connected by a communication bus, e.g., a Cray supercomputer or a multicore machine”作为同步分布式系统的例子。
2. 局域网 / 多处理器集群：1980s。楼宇/园区内的以太网，Berkeley NOW（Network of Workstations）把一批工作站连成集群取代大型机。通信从”共享介质广播”变成”交换式点对点”，不再有共享时钟，但延迟仍小且有界。
3. 互联网 / Web / 网格（Grid）：1990s–2000s。跨机构、跨管理域，节点数量从 10³ 跃到 10⁶。网格的代表是 Globus Toolkit（GridFTP 做广域批量数据传输、GRAM5 做作业提交与取消、RLS 做副本位置解析、GSI 做安全基础设施）与站点内的 HTCondor/PBS 两级调度；SETI@Home、Folding@Home 是周期窃取（cycle scavenging）类系统。关键性质：联邦制（federated）——没有任何单一实体控制整个基础设施，因此安全与信任模型变得复杂；同时延迟第一次变得无上界。
4. 集群 / 数据中心：2000s–2010s。课程 L2.FA26 给出的单站点云形态是：计算节点（按机架分组）+ 交换机 + 分层网络拓扑（Clos/fat-tree）+ 后端存储节点 + 前端/负载均衡器，其中”前端/负载均衡 (1)、计算节点 (2)、存储节点 (3)”三者构成经典的三层体系结构；再加上云控制平面（供给、调度、监控、认证）与软件服务。地理分布形态则是 Server → Rack → Datacenter → AZ → Region → Global，其中 AZ 被设计为独立的故障域（failure domain）。典型系统：Google 的 GFS/MapReduce、Hadoop、NoSQL（Cassandra）。
5. 超大规模系统（Ultra-Large-Scale, ULS）与云 + 边缘：2010s 至今。节点数 10⁶ 量级（课程数据：Google 2011 年约 90 万台，2016 年传闻 250 万台；Facebook 从 2009 年的 3 万台增长到 2012 年的 18 万台；Meta 有 12.5 万块 H100 GPU）。规模本身带来了质变：不再有全局视图、不再能停机维护、故障是常态而不是异常。课程 L6.FA25 给了一个极有说服力的算术：若单机故障率是平均 10 年一次（120 个月），那么 120 台机器时”下一台机器故障”的平均时间（MTTF）是 1 个月，12000 台机器时 MTTF 约 7.2 小时；软崩溃（soft crash）与性能故障还要频繁得多。在 ULS 尺度下，”无故障”不是可以假设的默认状态。

• 物理模型的局限：它是描述性（descriptive）的。知道”我有 12000 台机器、跑在 fat-tree 上、跨 3 个 AZ”，推不出”我可以给消息延迟设 50ms 超时”。不同物理形态暗示了不同的时间/故障性质（总线→同步，互联网→异步），但这些性质必须被显式声明为假设才能被算法使用。于是需要：体系结构模型（软件元素如何组织，决定故障与延迟如何被放大或缓解）与基础模型（把时间、故障、安全假设写成算法可直接引用的公理）。

3.2.3 体系结构元素（Architectural Elements）

「补充说明」：Coulouris Ch.2 把体系结构模型拆成四个元素，这是理解一切”系统架构图”的骨架：

1. 通信实体（Communicating Entities）：参与通信的最小单位，从低到高是进程 → 线程 → 对象 → 组件 → Web 服务。粒度越粗，抽象越好、异构性屏蔽越彻底，但并发与性能越不可控。在云里实体通常是容器 / Pod；在 MP 里就是你自己 fork 出来的进程。
2. 通信范式（Communication Paradigms），分三大类：
   • 进程间通信（Interprocess Communication, IPC）：socket、消息传递（send/receive），最低层，直接暴露”不可靠介质”。
   • 远程调用（Remote Invocation）：RPC / RMI，把跨进程调用伪装成本地过程调用。课程 L19-20 强调：本地调用（LPC）有 exactly-once 语义，而 RPC 在故障下无法保证 exactly-once——请求消息丢了、应答消息丢了、被调用进程在”执行前/执行后”崩溃，这四种情况调用方无法区分；RPC 因此只能在 at-least-once（可能重复执行） 与 at-most-once（可能一次都没执行） 之间选一个。
   • 间接通信（Indirect Communication）：发送方不直接指定接收方。包括组播（group multicast）、发布-订阅（publish-subscribe）、消息队列（message queue）、元组空间（tuple space）、分布式共享内存（DSM）。间接通信带来时间解耦（发送者与接收者不必同时在线）与空间解耦（不必互相知道地址），代价是投递语义更难界定。
3. 角色与职责（Roles and Responsibilities）：谁发起、谁等待、谁负责状态。两大范式是 client-server 与 peer-to-peer（见 3.2.4 与 3.2.6）。
4. 放置（Placement）：服务（service）与数据放在哪里。基本手段有 proxy（代理）、cache（缓存）、mobile code（移动代码）；现代形态则是云/边缘的放置决策（见 3.2.7）。

3.2.4 客户端-服务器模型与它的弱点

• 定义与目的：client 主动发起请求并等待应答；server 被动监听、处理请求、返回应答。它是最自然的非对称分工，也是课程 L1.FA26 中 HTTP/1.0/1.1（RFC 1945 / RFC 2068）的组织方式：浏览器是 client，Apache 是 server，client 主动建立 TCP 连接（socket）到 80 端口，交换应用层消息后关闭连接。
• 直观解释：像餐厅——顾客（client）点菜，厨房（server）做菜。分工清晰，但厨房只有一间；客人多了就得排队，厨房着火全店停业。
• 机制图解（与三层、P2P 的对比，见下图）。服务器实现有迭代服务器（iterative，一次处理一个请求）与并发服务器（concurrent，多线程/多进程/事件循环）之分；课程 L1 还强调 http 是 stateless 的（服务器不保存过去请求的信息），并且特意问了一句”Why?”：因为保持会话状态（state）的协议是复杂的——历史状态必须被维护和更新，一旦 server/client 崩溃，双方对 state 的看法可能不一致，必须做对账（reconciliation）。这也是 RESTful 协议选择无状态的原因。
• 弱点（课程 L1 的设计目标清单可以直接用来”打靶”）：
  • 可扩展性与可用性：服务器是瓶颈（负载随客户端数线性增长）与单点故障（single point of failure）——服务器不可用则整个服务不可用，只能靠垂直升级或加一层负载均衡。
  • 位置耦合：client 必须知道 server 地址（DNS/IP:port），移动性差，server 地址变更会牵动所有客户端。
  • 安全边界与成本：所有请求汇聚到同一入口，入口被打穿则全盘失守（也正因如此，入口是部署防火墙与 ACL 的天然位置）；同时所有算力集中在服务器侧，客户端算力被浪费。

这些弱点正好解释了后面每一个体系结构变体的动机：三层解决可扩展性与可用性，proxy/cache 解决延迟与带宽，P2P 解决中心化成本与控制权，中间件解决异构与编程复杂性。

3.2.5 多层（Multi-tier / 3-tier）体系结构

• 定义与目的：把功能按层（tier）切开，每层只依赖下一层的接口，从而让每一层独立地水平扩展。云的标准三层是：
  • 表示层（presentation tier）：前端页面/API 网关/负载均衡器。负责协议终结、TLS、限流、会话粘性。
  • 应用逻辑层（application logic tier）：无状态的业务计算服务。因为是”无状态”的，所以可以随意加减副本、随时重启（对应 L2.FA26 的”计算节点按机架分组”）。
  • 数据层（data tier）：有状态的存储。用分片（sharding）解决容量与写吞吐，用复制（replication）解决故障与读吞吐——而”复制”立刻把问题推回到共识与一致性的模型假设上（这正是 Lecture 15–20 的主题）。
• 直观解释：餐厅的进化——领位台 + 多间厨房 + 中央仓库。领位台只负责分配（表示层），厨房可以多开几间且互不依赖（应用层），仓库才是真正”唯一”的、需要小心保护的部分（数据层）。
• 机制图解（三层与 C/S、P2P 的并排对比）：

+----------------------+   +-------------------------------+   +--------------------------+
| CLIENT-SERVER 两层   |   | 3-TIER 三层（云的标准形态）   |   | PEER-TO-PEER 对等        |
|   client --> server  |   |   presentation（前端/LB）     |   |   每节点既是 client      |
|   简单、易实现       |   |   application logic（无状态） |   |   又是 server            |
|   服务器是瓶颈与单点 |   |   data（有状态，分片+复制）   |   |   无中心、可扩展、难管理 |
|                      |   |                               |   |                          |
|   [C] [C] [C]        |   |   [C] [C] [C]                 |   |   +---+     +---+        |
|        |  |  |       |   |        |  |  |                |   |   | P |-----| P |        |
|        v  v  v       |   |        v  v  v                |   |   +---+     +---+        |
|      +--------+      |   |   +-------------+             |   |     |   \ /   |          |
|      | SERVER |      |   |   | LOAD BAL.   |             |   |     |    X    |          |
|      +--------+      |   |   +-------------+             |   |     |   / \   |          |
|           |          |   |      |       |                |   |   +---+     +---+        |
|           v          |   |      v       v                |   |   | P |-----| P |        |
|      [  DATA  ]      |   |   +------+ +------+           |   |   +---+     +---+        |
+----------------------+   |   | APP1 | | APP2 |           |   +--------------------------+
                           |   +------+ +------+           |
                           |      |       |                |
                           |      v       v                |
                           |   +----------------+          |
                           |   | DATA (shards)  |          |
                           |   +----------------+          |
                           +-------------------------------+

• 关键假设与系统模型：三层体系结构的”可扩展性”是条件性的，条件是：应用层真的无状态（状态外置到数据层或缓存），数据层的复制协议能在部分同步模型下保证一致性。若应用层偷偷在内存里缓存了用户状态，水平扩展立刻变成正确性事故。

3.2.6 代理与缓存（Proxy & Cache）在体系结构中的角色

• 定义与目的：proxy 是一个代表别人行事的中介——客户端以为在跟服务器说话，实际在跟代理说话；cache 是”最近使用过的数据的副本”，用来把重复访问的代价从远端拉回本地。
• 直观解释：proxy 像前台/翻译（替你转达请求，还能顺手做安检与限流），cache 像冰箱（把常吃的东西放在手边，代价是要判断”过期了没有”）。
• 机制图解：

  client ---> [ PROXY / CACHE ] ---> server
                 |         |
                 |         +-- 命中(hit)  : 直接返回副本，延迟 ~0，带宽 ~0
                 +------------ 未命中(miss): 转发给 server 并把结果存下来
  层次: 浏览器缓存 -> 组织内代理 -> CDN 边缘节点 -> 源站

• 关键假设与系统模型：缓存把一致性变成了必须显式处理的问题——缓存副本可能过期（stale）。需要失效（invalidation）或验证（validation）协议（例如 HTTP 的 ETag/If-None-Match 与 Cache-Control）。注意一个结构性事实：缓存的一致性强度是可以被协商的，这是缓存之所以能大规模使用的原因；而持久数据的一致性强度不能（那是 Lecture 19 的领域）。
• 在现代体系结构中的位置：CDN 边缘节点、API 网关缓存、数据库前面的 Redis，本质都是”proxy + cache”的组合；把缓存推到离用户最近的地方，就是边缘计算的体系结构动机。

3.2.7 Peer-to-Peer 体系结构：overlay network 与 super-peer

• 定义与目的：每个实体既是 client 又是 server，资源与负载分散在所有对等节点上，不依赖中心服务器。P2P 系统在应用层自建一张逻辑图，称为覆盖网络（overlay network）——它独立于物理拓扑，边的含义是”我知道你的地址且愿意转发消息”。
• 直观解释：C/S 像图书馆（书都在一个地方，好管理，但闭馆就全没了），P2P 像朋友之间的借书网络（书分散在每个人手里，永不停摆，但你得靠”认识谁”去找书）。
• 机制图解（课程 L7-8 的三种形态）：

+------------------------------------+------------------------------------+------------------------------------+
| 集中式目录 (Napster)               | 完全分散 (Gnutella)                | super-peer (混合)                  |
+------------------------------------+------------------------------------+------------------------------------+
|   [C] [C]                          |   [P]---[P]---[P]                  |   [P]  [P]  [P]                    |
+------------------------------------+------------------------------------+------------------------------------+
|     \  /                           |    |   X   |   X                   |     \  |  /                        |
+------------------------------------+------------------------------------+------------------------------------+
|   +---------+                      |   [P]---[P]---[P]                  |    +--------+                      |
+------------------------------------+------------------------------------+------------------------------------+
|   | INDEX   |                      |    flooding + TTL                  |    | SUPER  |                      |
+------------------------------------+------------------------------------+------------------------------------+
|   | SERVER  |                      |    power-law 拓扑                  |    | PEER   |                      |
+------------------------------------+------------------------------------+------------------------------------+
|   +---------+                      |                                    |    +--------+                      |
+------------------------------------+------------------------------------+------------------------------------+
|     /  |  \                        |                                    |         |                          |
+------------------------------------+------------------------------------+------------------------------------+
|   [P] [P] [P]  <- 文件仍在 peer 上 |                                    |    +--------+                      |
+------------------------------------+------------------------------------+------------------------------------+
|                                    |                                    |    | SUPER  |                      |
+------------------------------------+------------------------------------+------------------------------------+
|                                    |                                    |    +--------+                      |
+------------------------------------+------------------------------------+------------------------------------+

• 课程口径的三代设计（详见 Lecture 7–8）：Napster 用集中式索引服务器保存”文件名 → peer 指针”，文件本身仍在对等节点上（仍是单点）；Gnutella 完全分散，用 Ping/Pong/Query/QueryHit 五类消息 + flooding + TTL 搜索，找不到就”give up”，其拓扑被观测到服从幂律分布（power-law），少数高连接度节点承担大部分带宽；结构化 P2P（Chord/DHT） 用一致性哈希把 key 映射到环上的节点，实现 O(log N) 的可预测路由。
• 与 client-server 的对比：