读书笔记：深入理解分布式系统

分布式系统模型、数据复制、一致性、共识、事务与时间

https://book.douban.com/subject/35794814/

• 是什么（What）：
  • 理解分布式系统的基础知识框架：从故障与时间模型出发，连接数据分区、复制、一致性、共识、事务
  • 分布式系统不是许多机器组成的系统这么简单，而是一组独立节点通过不可靠网络协作，并对外提供某种统一语义的系统
• 为什么（Why）：
  • 分布式带来容量、性能、可用性和地理扩展能力，也把网络延迟、部分失效、时钟偏差和并发竞争变成正常情况
  • 只有先明确系统模型与语义承诺，才能判断一个方案在什么条件下正确，以及用延迟、可用性和复杂度换来了什么
• 怎么做（How）：
  • 先定义故障模型、网络模型和时间假设，再选择分区、复制、一致性、共识和事务机制
  • 用不变量、状态机和消息交互分析协议；分别验证安全性与活性，不用正常路径上的测试代替故障推理
  • 从 GFS、ZooKeeper、Bigtable、Dynamo、Cassandra、Spanner、MapReduce 和 Flink 等案例中学习机制如何组合

核心观点：

分布式系统设计的本质，是在无法可靠区分节点故障、网络故障和响应缓慢的环境中，仍然对外提供明确且可验证的数据与操作语义。

算法和架构都建立在系统模型之上。模型越强，算法越容易；现实越接近异步和部分失效，系统就越需要超时、重试、幂等、仲裁与共识来弥补不确定性。

• 先建模，再讨论正确性：

  • 网络可能丢包、重复、乱序和分区；节点可能崩溃、暂停、遗漏消息，甚至产生任意行为
  • 同步模型假设处理和通信有已知上界，异步模型不提供时间上界，部分同步模型则允许系统最终进入有界状态
  • 超时只是故障检测的线索，不是事实：没有收到响应，无法证明对方没有执行请求
  • 消息传递通常只能直接实现至多一次或至少一次；所谓精确一次，需要去重、幂等、事务或端到端协议共同提供业务效果

• 分区与复制解决不同问题，也制造不同问题：

  • 分区把数据和负载拆到多个节点，解决容量与吞吐问题；范围分区利于区间扫描但容易形成热点，哈希分区更均匀但削弱范围查询
  • 复制用冗余换取读扩展和容错，却引入副本滞后、写冲突、故障切换和一致性问题
  • 单主复制简化写入顺序，多主复制支持多地写入但必须解决冲突，无主复制依靠 Quorum 协调读写并修复副本
  • 分片后的重平衡、热点、路由和跨分片操作，与复制后的选主、追赶和冲突处理一样，都是设计的一部分

• 一致性描述可观察的数据语义，不等于共识，也不等于隔离级别：

  • 线性一致性要求每个操作像在调用瞬间原子生效，并尊重真实时间顺序；顺序一致性只要求所有进程看到相同全序
  • 因果一致性保留 happened-before 关系，允许并发事件以不同顺序出现；最终一致性只承诺停止写入后副本最终收敛
  • 读己之写、单调读和一致前缀读等客户端保证，可在弱一致系统中提供更符合用户直觉的体验
  • 一致性约束多个副本或操作的可见结果；隔离级别约束并发事务互相能观察到什么，两者不能混用
  • CAP 讨论网络分区发生时，一致性和可用性无法同时保证；PACELC 进一步提醒，即使没有分区，也要在延迟和一致性之间权衡

• 共识把多个副本变成一台可恢复的确定性状态机：

  • 共识要求节点对同一个值达成不可撤回的决定；安全性要求不能决定冲突值，活性要求最终能够做出决定
  • FLP 表明纯异步系统中，只要允许一个节点崩溃，就不存在保证终止的确定性共识算法；工程实现通过超时、领导者和最终同步假设获得活性
  • Paxos 通过编号提案和多数派交集保证已选值不会被后续提案覆盖；Multi-Paxos 用稳定领导者把单值共识扩展为复制日志
  • Raft 把问题拆成领导者选举、日志复制和成员变更，以任期和日志匹配规则维护状态机安全性
  • 多数派的关键不只是票数过半，而是任意两个多数派必有交集，使新一轮决策能够继承旧一轮已经形成的事实
  • 共识日志提交不自动等于线性一致服务；客户端去重、线性一致读、成员变更和快照恢复仍需要单独设计

• 分布式事务同时处理原子提交和并发控制：

  • 原子提交回答所有参与者是否一起提交，并发控制回答并发事务如何等价于某个合法执行；二者是正交问题
  • 两阶段提交由协调者收集 prepare 结果后统一决定 commit 或 abort，可以保证原子性，但协调者失效时可能阻塞
  • 2PC 不是共识：它依赖所有参与者对单次事务投票，而共识能在部分节点失效时由多数派持续复制决定
  • 两阶段锁、乐观并发控制和 MVCC 分别以阻塞、提交时验证和多版本空间处理竞争，选择取决于冲突率、读写比例和隔离需求
  • Saga 把长事务拆成一系列本地事务和补偿动作，换取可用性与松耦合，但不提供自动回滚和完整隔离
  • Percolator 展示了如何组合 2PC、MVCC 和快照隔离，在分布式存储之上构建跨行事务

• 时间不能直接充当分布式系统中的真相：

  • 墙上时钟可能偏移或回拨，适合表示日期；单调时钟适合测量本机时间间隔，但不能跨机器直接比较
  • Lamport 时钟保证若 (a \rightarrow b)，则 (L(a) < L(b))，但不能根据时间戳反推出因果关系
  • 向量时钟能够判断两个事件存在因果关系还是并发关系，代价是元数据随参与节点数量增长
  • Chandy–Lamport 分布式快照在系统继续运行时记录一个一致的全局切面，是检查点、故障恢复和流处理精确一次语义的基础
  • 物理时钟只有连同误差边界一起使用才可信；Spanner 的 TrueTime 正是把不确定性暴露为时间区间，再通过等待换取外部一致性

章节脉络：

1. 认识分布式系统：理解使用多机的收益，以及网络延迟、部分失效和时钟问题为何无法通过普通异常处理消除
2. 系统模型：用两将军和拜占庭将军问题建立边界，明确链路、节点、时间和消息语义假设
3. 分布式数据：从分区与复制进入 CAP、一致性模型和事务隔离，厘清最容易混淆的术语
4. 分布式共识：从 FLP 到 Paxos、Multi-Paxos、Raft 和 PBFT，理解复制状态机如何保持安全并争取活性
5. 分布式事务：把原子提交与并发控制拆开，再通过 2PC、Saga、MVCC 和 Percolator 看它们如何组合
6. 时间和事件顺序：区分物理时间与逻辑顺序，用逻辑时钟、向量时钟和分布式快照表达系统历史
7. 案例研究：观察经典系统如何针对访问模式、故障模型和语义目标选择并组合基础机制

经典系统的设计取舍：

启发点（关键洞察）：

1. 协议正确性依赖假设：任何不会脑裂 不会丢数据的结论，都必须补全节点故障、网络分区、持久化和时钟假设
2. 超时不会消除不确定性：超时后重试意味着原请求可能执行零次、一次或多次，业务接口应携带幂等键并保存去重结果
3. 安全性和活性要分开分析：系统宁可暂时不可用也不能产生两个领导者的冲突决定，这是共识协议常见的取舍
4. 多数派交集是 Quorum 的真正力量：它让不同轮次能够传递已确认的信息；只写W + R > N而不分析读写与故障流程是不够的
5. 强语义必须端到端成立：底层日志有序，不代表 API 线性一致；消息只投递一次，也不代表外部副作用只发生一次
6. 协调应只用于维护真正的不变量：若业务允许交换顺序、合并冲突或补偿，就不必为所有操作支付全局排序成本
7. 时间戳不是天然顺序：跨机器的 last-write-wins 可能因时钟偏差静默丢数据，必须明确这是业务接受的冲突解决策略
8. 经典系统不是机制清单：优秀设计从负载和目标出发，主动放弃不需要的通用能力，再组合最少的分布式机制

行动：

1. 设计分布式协议前固定写出：节点故障类型、网络假设、持久化边界、成员关系，以及安全性和活性目标
2. 对每个远程写操作检查请求成功但响应丢失场景，明确幂等键、去重状态保存周期和重试上限
3. 评审复制方案时分别回答：写入何时确认、读哪个副本、领导者如何切换、旧领导者如何隔离、落后副本如何追赶
4. 选择一致性级别时从业务异常反推：脏读、旧读、丢失更新、重复扣款和顺序颠倒分别是否可接受
5. 涉及跨分片或跨服务事务时，把原子性、隔离性、可用性和补偿能力分别列出，不用支持事务一句话代替
6. 对使用物理时间排序或生成版本的代码，检查时钟回拨、闰秒、漂移和同时间戳冲突；测量间隔一律使用单调时钟
7. 阅读或选型一个分布式系统时，用目标 → 系统模型 → 核心不变量 → 机制 → 失败模式 → 代价的顺序拆解

金句：

1. 分布式系统最难处理的不是完全失效，而是只有一部分组件失效，且其他节点无法确定发生了什么。
2. 超时只能让系统停止等待，不能告诉系统之前的操作是否已经发生。
3. 一致性是对使用者的语义承诺，共识是副本形成共同决定的机制，隔离级别是并发事务之间的可见性规则。
4. 多数派不是魔法；真正提供安全性的是多数派之间必然相交。
5. 精确一次通常不是消息系统的单点能力，而是从输入、状态到外部副作用的端到端效果。
6. 没有脱离系统模型的正确算法，也没有不付出代价的强一致性。

links

1. http://www.broadview.com.cn/book/7175
2. https://github.com/tangwz/DistSysDeepDive
3. https://raft.github.io/raft.pdf
4. https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
5. https://research.google/pubs/the-google-file-system/
6. https://research.google/pubs/bigtable-a-distributed-storage-system-for-structured-data/
7. https://research.google/pubs/dynamo-amazons-highly-available-key-value-store/
8. https://research.google/pubs/spanner-googles-globally-distributed-database/