Books Notes Graph Series Tags

mit6.824

📅 2026-04-10 ✏️ 2026-04-10 CS

1 · MIT 6.824 分布式系统#

课程主页：https://pdos.csail.mit.edu/6.824/

笔记参考：https://timilearning.com/tags/mit-6.824/

S 构建大规模互联网服务，单机在性能、容量、可用性上都有瓶颈 C 多台机器协同工作后，面临网络不可靠、节点故障、数据一致性等复杂问题 Q 如何在不可靠的基础设施上构建可靠、高性能、一致的分布式系统？ A 通过容错复制、一致性协议、分布式事务等技术，逐一攻克；课程围绕经典论文展开

相关笔记：分布式系统

1.1 · 课程主线

课程围绕三个核心主题展开，所有论文都在回答这些问题：

  1. 容错（Fault Tolerance）：节点随时可能挂，如何保证系统继续工作？→ 复制
  2. 一致性（Consistency）：多副本之间如何保持数据一致？→ 共识算法、一致性模型
  3. 性能（Performance）：分布式带来的开销如何降低？→ 分区、缓存、批处理

1.2 · Lecture 1: MapReduce#

论文：MapReduce: Simplified Data Processing on Large Clusters (2004)

S 谷歌需要处理 TB 级数据（网页索引、日志分析），单机跑不动 C 手写分布式程序太复杂——分区、容错、调度、网络，每次都要重新造轮子 Q 能不能提供一个通用框架，让程序员只写业务逻辑，框架负责分布式细节？ A Map + Reduce 两阶段抽象，框架处理分区、调度、容错（worker 挂了重跑任务）

核心设计：

  • Map：输入 → 一组 (key, value) 中间结果
  • Reduce：按 key 聚合中间结果 → 最终输出
  • Master 负责调度，worker 挂了由 master 重新分配任务
  • 输入输出都在 GFS 上，中间结果写本地磁盘
  • 容错靠重新执行：Map/Reduce 是纯函数，幂等可重跑

局限：

  • 两阶段模型不适合迭代计算（如机器学习），每次迭代都要读写磁盘
  • 后来被 Spark 等框架取代

1.3 · Lecture 2: RPC and Threads#

编程模型基础，Go 实现

S 分布式系统中节点通过网络通信，需要并发处理请求 C 并发编程容易出错（竞态、死锁），网络调用可能失败 Q 如何安全地编写并发程序？RPC 失败了怎么办？ A 线程 + 锁/channel 处理并发；RPC 语义：at-least-once vs at-most-once vs exactly-once

RPC 语义：

  • at-least-once：失败就重试，但操作必须幂等
  • at-most-once：服务端去重（记录已处理的请求 ID）
  • exactly-once：最理想但最难实现，通常需要事务支持

相关笔记：concurrency Go concurrency pattern

1.4 · Lecture 3: GFS#

论文：The Google File System (2003)

S 谷歌需要存储海量数据，普通文件系统容量和吞吐都不够 C 大文件 + 追加写为主的工作负载；硬件故障是常态而非异常 Q 如何设计一个支持大文件、高吞吐、自动容错的分布式文件系统？ A 单 Master + 多 Chunkserver；大块（64MB chunk）+ 三副本；放松一致性换取简单性和性能

核心设计：

  • 单 Master：存元数据（文件→chunk 映射、chunk 位置），不存数据本身
  • Chunkserver：存实际数据，每个 chunk 64MB，三副本
  • 追加写优化：record append 是原子的，GFS 保证 at-least-once
  • 一致性模型：放松了——同一 chunk 的不同副本可能不完全一致（defined vs consistent）
  • Master 是单点——后来成为瓶颈，促成了 Colossus 的诞生

1.5 · Lecture 4: VMware FT#

论文：The Design of a Practical System for Fault-Tolerant Virtual Machines (2010)

S 关键服务需要高可用，单台机器故障不能导致服务中断 C 备份机器需要和主机保持完全一致的状态，任何不确定性都会导致分叉 Q 如何让备份机器和主机保持完全同步，主机挂了备份能无缝接管？ A 复制状态机（Replicated State Machine）：通过 VMware 虚拟机层面复制所有输入（指令级别），主备执行相同操作序列

核心设计：

  • Primary-Backup 架构，共享磁盘
  • 通过 logging channel 传输确定性操作日志
  • 不确定事件（中断、时钟读取）由 Primary 记录并传给 Backup
  • 主机挂了，Backup 提升为 Primary（go live）
  • 输出规则：Primary 在 Backup 确认收到日志前，不向客户端发送输出——保证切换后不丢数据

局限：

  • 指令级复制开销大，只能单核
  • 现代系统更多使用应用级别的状态机复制（如 Raft）

1.6 · Lecture 5: Go, Threads, and Raft#

实践课：用 Go 实现 Raft 的编程模式

关键模式：

  • 用 sync.Mutex 保护共享状态
  • 用 sync.Cond 等待条件变化
  • 用 channel 做事件通知
  • 后台 goroutine 做定时任务（心跳、选举超时）
  • 注意：持有锁时不要做 RPC 调用（会死锁或阻塞太久）

1.7 · Lecture 6 & 7: Raft#

论文：In Search of an Understandable Consensus Algorithm (2014)

S 分布式系统需要多副本容错，副本之间需要就操作顺序达成共识 C Paxos 太难理解和实现，工程中容易出错 Q 能否设计一个和 Paxos 等价但更易理解的共识算法？ A Raft：将共识问题拆解为 Leader Election + Log Replication + Safety 三个子问题

详见 raft

1.8 · Lecture 8: ZooKeeper#

论文：ZooKeeper: Wait-free coordination for Internet-scale systems (2010)

S 分布式应用需要协调服务（配置管理、服务发现、分布式锁、领导选举） C 每个应用自己实现协调逻辑，重复造轮子且容易出错 Q 能否提供一个通用的分布式协调服务？如何在保证正确性的同时提升性能？ A ZooKeeper：提供类似文件系统的 API（znode 树），读请求可在任意副本处理，写请求通过 ZAB 协议（类 Raft）保证全序

核心设计：

  • 数据模型：znode 树，每个 znode 可存少量数据
  • API：create, delete, exists, getData, setData, getChildren
  • 临时节点（ephemeral）：客户端断开后自动删除——用于服务发现、分布式锁
  • 顺序节点（sequential）：自动递增编号——用于领导选举
  • Watch 机制：客户端注册监听，znode 变化时通知——避免轮询
  • 一致性保证：
    • 写操作：线性一致（通过 leader 全序广播）
    • 读操作：非线性一致（可能读到旧值），但保证同一客户端的单调读
    • sync 操作：强制读最新值

性能取舍：读请求在 follower 本地处理（不经过 leader），加副本 = 加读吞吐；代价是读可能不是最新的

相关笔记：etcd（etcd 是 ZooKeeper 的现代替代）

1.9 · Lecture 9: CRAQ#

论文：Object Storage on CRAQ (2009)

S Chain Replication（链式复制）提供强一致性，但读请求只能打到 tail 节点，吞吐受限 C 想要强一致性 + 高读吞吐，两者通常矛盾 Q 能否在保持强一致性的同时，让读请求分散到所有节点？ A CRAQ：任何节点都可以处理读请求；如果节点上的数据版本是 clean（已提交），直接返回；如果是 dirty（未提交），向 tail 查询最新已提交版本

对比 Raft 的复制方式：

  • Raft：leader 广播给所有 follower（星型）
  • Chain Replication：head → node1 → node2 → … → tail（链式）
  • CRAQ 改进了 Chain Replication 的读吞吐瓶颈

1.10 · Lecture 10: Aurora#

论文：Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases (2017)

S 传统数据库在云环境中，存储和计算紧耦合，扩展和容错都受限 C 数据库写入涉及大量 I/O（数据页、WAL、double-write buffer），跨 AZ 复制放大写入量 Q 如何为云环境设计一个高吞吐、高可用的关系数据库？ A “日志即数据库”：只把 redo log 发给存储节点，存储节点自己重放日志生成数据页

核心设计：

  • 计算层（单写多读）和存储层（6 副本，跨 3 个 AZ）分离
  • 写入时只发 log record 给存储层（网络 I/O 减少到传统方式的 1/6）
  • Quorum：写入 4/6 成功即可，读取 3/6（保证读到最新）
  • 存储节点异步重放 log 生成数据页
  • 读副本（Read Replica）共享存储层，几乎零延迟

1.11 · Lecture 11: Frangipani#

论文：Frangipani: A Scalable Distributed File System (1997)

S 分布式文件系统需要共享访问，每个工作站有本地缓存提升性能 C 多个工作站缓存同一文件，一个修改了，其他的缓存就过期了 Q 如何在有缓存的分布式文件系统中保持一致性？ A 分布式锁 + write-back 缓存：修改文件前先拿锁，锁被收回时把脏数据写回

核心设计：

  • 底层存储 Petal（虚拟磁盘），上层 Frangipani（文件系统语义）
  • 每个工作站有本地缓存，使用分布式锁服务协调
  • 锁的回收（revoke）时，持有者必须先 flush 脏数据
  • 崩溃恢复：每个工作站有自己的 WAL（写在 Petal 上），其他节点可以重放

1.12 · Lecture 12: 分布式事务#

2PC (Two-Phase Commit)

S 事务操作涉及多个节点上的数据（跨分区） C 部分节点成功、部分失败——要么全提交，要么全中止 Q 如何在多节点上实现原子提交？ A 2PC：协调者先 prepare（所有参与者锁住资源并投票），再 commit/abort

详见 分布式系统 中的”提交”部分

2PC 的核心问题：

  • 参与者投了 YES 后必须等协调者决定——阻塞
  • 协调者挂了 → 参与者永远等
  • 解决方案：让协调者自身用 Raft 复制（Paxos Commit）

1.13 · Lecture 13: Spanner#

论文：Spanner: Google’s Globally-Distributed Database (2012)

S 谷歌需要一个全球分布的数据库，支持跨数据中心的分布式事务 C 分布式事务需要全序，但跨数据中心的时钟不同步 Q 如何在全球分布的数据库中实现外部一致性（线性一致性 + 可串行化）？ A TrueTime API：用 GPS + 原子钟给出时间置信区间 [earliest, latest]，事务提交时等待不确定性窗口过去

核心设计：

  • 数据按 key range 分片，每个分片用 Paxos 复制
  • 读写事务：2PC + Paxos，每个分片的 Paxos leader 是 2PC 的参与者
  • 只读事务：快照读，不需要锁，选一个时间戳读所有分片的对应版本
  • TrueTime：TT.now() 返回 [earliest, latest]
    • 提交时取 s = TT.now().latest，然后 等到 TT.now().earliest > s 才提交
    • 这保证了不同事务的时间戳不会交叉——实现外部一致性
  • 代价：每次写事务都要等几毫秒（不确定性窗口），谷歌用原子钟把窗口压缩到 ~7ms

1.14 · Lecture 14: FaRM#

论文：No compromises: distributed transactions with consistency, availability, and performance (2015)

S 分布式事务通常很慢（2PC + Paxos，多轮网络往返） C 想要强一致性（严格可串行化）+ 高性能，传统方案做不到 Q 能否利用新硬件（RDMA + 非易失内存）来大幅提升分布式事务的性能？ A FaRM：用 RDMA 绕过 CPU 直接读写远程内存，用**乐观并发控制（OCC）**减少冲突

核心设计：

  • RDMA（Remote Direct Memory Access）：网卡直接读写远程内存，不经过远程 CPU
  • OCC 四阶段：
    1. Execute：读取数据（RDMA one-sided read），本地缓存修改
    2. Lock：锁定要写的记录
    3. Validate：验证读取的记录没被修改（版本号检查）
    4. Commit & Truncate：写入修改并释放锁
  • 非易失内存保证崩溃恢复不丢数据
  • 性能：比 Spanner 快几个数量级（微秒 vs 毫秒），但局限于单数据中心

1.15 · Lecture 15: Spark#

论文：Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing (2012)

S MapReduce 对迭代计算（如机器学习、图计算）效率低——每次迭代都要读写磁盘 C 想把中间结果放内存，但内存中的数据怎么容错？ Q 如何实现一个支持内存计算、容错的分布式计算框架？ A RDD（Resilient Distributed Dataset）：不可变的分区数据集，记录**血统（lineage）**而非数据本身；丢了就从血统重算

核心设计：

  • RDD 是逻辑上的不可变数据集，支持 map、filter、join 等转换
  • 惰性求值：转换操作只记录血统图，action 触发时才真正计算
  • 容错：数据丢了按血统从头重算（窄依赖只需重算一个分区）
  • 持久化：可选择把 RDD 缓存到内存，避免重复计算
  • 比 MapReduce 快 10-100 倍（迭代场景）

1.16 · Lecture 16: Memcache at Facebook#

论文：Scaling Memcache at Facebook (2013)

S Facebook 面临巨大的读请求量（数十亿用户），数据库扛不住 C 加缓存后，缓存一致性问题：数据库更新了，缓存还是旧值 Q 如何在全球规模下使用 Memcached 作为缓存，同时尽量保证一致性？ A 多层级架构：Web Server → Memcache（look-aside cache）→ MySQL；数据库更新后主动 invalidate 缓存

核心设计：

  • Look-aside 缓存模式：
    • 读：先查 Memcache，miss 则查 DB 并填充缓存
    • 写：先更新 DB，再 delete 缓存（不是 update）
  • Regional Pool：同一区域多个 Memcache 集群共享一个后端 DB
  • 跨区域：主区域写 DB，从区域通过 MySQL 复制 + McSqueal（监听 binlog 发 invalidation）
  • Lease 机制：防止 thundering herd（缓存失效后大量请求同时打到 DB）
  • Gutter 服务器：Memcache 节点挂了，请求打到 gutter（临时缓存），避免 DB 雪崩

取舍：最终一致性，但在实践中”足够好”

1.17 · Lecture 17: COPS#

论文：Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage (2011)

S 强一致性（线性一致性）延迟高，最终一致性太弱（因果倒置） C 能否找到一个中间地带：不需要全局排序，但保证因果顺序？ Q 什么是”不牺牲可用性的最强一致性”？如何实现？ A 因果一致性（Causal+ Consistency）：保证因果相关的操作有序，并发操作可以无序；加上收敛（+）保证冲突最终一致

核心设计：

  • 每个数据中心内线性一致，跨数据中心因果一致
  • 用 依赖追踪 表示因果关系：每次写操作携带它依赖的操作列表
  • 远程数据中心收到写操作后，等其所有依赖都到了才应用
  • 收敛：用 last-writer-wins 或应用自定义合并函数
  • 性能：读写都在本地数据中心完成，低延迟

1.18 · Lecture 18: Certificate Transparency#

论文：Certificate Transparency (2013)

S Web 安全依赖 CA（证书颁发机构）签发 TLS 证书，但 CA 可能被攻破或误签证书 C 恶意签发的证书无法被及时发现——用户和网站都不知道 Q 如何让证书签发过程可审计，恶意证书能被快速发现？ A 把所有签发的证书记录到公开的、只能追加的日志中（Merkle Tree），任何人都可以验证

核心设计：

  • Append-only Log：基于 Merkle Tree，不可篡改
  • Monitor：定期检查日志，发现异常证书
  • Auditor：验证日志的一致性（没有被篡改）
  • 不阻止恶意签发，但让恶意行为可检测

1.19 · Lecture 19: Bitcoin#

论文：Bitcoin: A Peer-to-Peer Electronic Cash System (2008)

S 在线支付依赖银行等中心化可信第三方 C 去中心化场景下，没有可信第三方，如何防止双花（double spending）？ Q 如何在互不信任的节点之间就交易顺序达成共识？ A 区块链 + 工作量证明（PoW）：矿工通过计算难题竞争记账权，最长链 = 共识

核心设计：

  • 交易通过公钥加密签名，UTXO 模型
  • 区块包含多笔交易 + 前一个区块的哈希 → 形成链
  • PoW：找到一个 nonce 使得 hash(block) < target，约 10 分钟一个块
  • 最长链规则：分叉时选最长链，攻击者需要超过全网 50% 算力
  • 激励：出块奖励 + 交易费

与传统共识（Raft/Paxos）的对比：

  • Raft：封闭成员、快速确认、确定性
  • Bitcoin：开放成员、概率性确认（等 6 个块）、高延迟

1.20 · Lecture 20: Blockstack#

论文：Blockstack: A New Internet for Decentralized Applications (2017)

S 中心化互联网应用（Facebook、Google）控制用户数据 C 用户没有数据主权，隐私和安全依赖平台 Q 能否构建去中心化应用，让用户拥有和控制自己的数据？ A Blockstack：用区块链做命名系统（域名→公钥绑定），用户数据存在用户自己选择的存储后端（如 S3、Dropbox）

1.21 · 课程主题脉络

容错                    一致性                 性能
│                       │                      │
├─ MapReduce (重跑)     ├─ GFS (放松一致性)    ├─ MapReduce (并行)
├─ GFS (3副本)          ├─ Raft (强一致)       ├─ Spark (内存计算)
├─ VMware FT (主备)     ├─ ZooKeeper (读放松)  ├─ Memcache (缓存)
├─ Raft (多数派)        ├─ Spanner (外部一致)  ├─ FaRM (RDMA)
├─ ZooKeeper            ├─ COPS (因果一致)     ├─ Aurora (log=DB)
├─ CRAQ (链式复制)      ├─ 2PC (原子提交)      ├─ CRAQ (读分散)
└─ Aurora (Quorum)      └─ Bitcoin (概率性)    └─ ZooKeeper (读副本)

1.22 · Labs#

Lab内容核心能力
Lab 1MapReduce分布式计算、容错
Lab 2Raft共识算法实现
Lab 3KV Server on Raft在 Raft 上构建线性一致的 KV
Lab 4Sharded KV分片、配置变更、数据迁移
  1. https://pdos.csail.mit.edu/6.824/schedule.html
  2. https://timilearning.com/tags/mit-6.824/
  3. https://www.youtube.com/channel/UC_7WrbZTCODu1o_kfUMq88g (课程录像)
  4. https://thesquareplanet.com/blog/students-guide-to-raft/