DDIA

DDIA第十章: 一致性共识

核心主题：探讨在分布式系统中如何处理故障，特别是通过一致性模型和共识算法来保证系统的正确性和可靠性，即使在网络延迟、分区、节点崩溃等故障发生时也能工作。

引言

  • 问题背景: 分布式系统充满挑战（网络问题、时钟问题、节点崩溃 - 详见第八章）。
  • 简单处理: 故障时服务失效，返回错误。
  • 更好方案: 容错（Fault Tolerance） - 即使部分组件失败，服务仍能正常运行。
  • 方法: 寻找带有实用保证的通用抽象，实现一次，供应用依赖。
    • 类比事务（ACID）：隐藏崩溃、并发、存储故障。
  • 本章核心抽象: 共识（Consensus） - 让所有节点对某件事达成一致。
  • 共识应用:
    • 领导选举 (Leader Election)：单主复制中，选举唯一的新主库，避免**脑裂 (Split Brain)**导致数据丢失。
  • 本章结构:
    1. 一致性保证（特别是线性一致性，以及其他模型）。
    2. 事件顺序（因果关系、全序）。
    3. 分布式事务与共识算法（2PC、Paxos、Raft等）。

一、一致性保证 (Consistency Guarantees)

  • 背景: 复制延迟导致副本间数据可能不一致（第五章）。
  • 最终一致性 (Eventual Consistency):
    • 定义：若停止写入，所有副本最终会收敛到相同的值。
    • 保证很弱：不保证收敛时间，收敛前读取可能返回任何值（包括旧值，如“读己之写”问题）。
    • 对开发者挑战大：与单线程变量行为差异大，易出错，难测试。
  • * 其他一致性模型 (谱系):
    • 现实中存在一个一致性模型的谱系，强度介于最终一致性和线性一致性之间：
      • 读己之写 (Read-Your-Writes): 保证用户能读到自己刚写入的数据。
      • 会话一致性 (Session Consistency): 在单个用户会话内保证读己之写、单调读等。
      • 单调读 (Monotonic Reads): 保证用户不会读到“回退”的数据（即读到新数据后又读到旧数据）。
      • 一致前缀读 (Consistent Prefix Reads): 保证读取的操作序列是某个有效全局序列的前缀（防止读到乱序的因果事件，如先看到答案再看到问题）。
    • 理解这些模型有助于根据业务场景选择最合适且代价最小的保证。
  • 目标: 寻求更强的一致性模型，让应用开发更容易，但可能牺牲性能/可用性。
  • 与事务隔离的区别:
    • 事务隔离：主要处理并发事务间的竞态条件。
    • 分布式一致性：主要处理副本间状态在延迟和故障下的协调。

二、线性一致性 (Linearizability)

  • 目标: 让系统看起来好像只有一个数据副本，所有操作都是原子性的。提供“单一副本”的假象。
  • 别名: 原子一致性 (Atomic Consistency), 强一致性 (Strong Consistency), 立即一致性 (Immediate Consistency), 外部一致性 (External Consistency)。
  • 核心: 新鲜度保证 (Recency Guarantee) - 读取操作必须返回最近的、已成功完成的写入值。
  • 例子 (图 9-1): Alice看到世界杯最终比分，告诉Bob。Bob刷新（在Alice看到结果之后），却看到旧的“进行中”状态。这违反了线性一致性，因为Bob的读取发生在一个返回新值的读取（Alice的）之后，却读到了旧值。 图 9-1 这个系统是非线性一致的，导致了球迷的困惑
  • 正式定义要点 (图 9-2, 9-3, 9-4):
    1. 每个操作（读/写/CAS）都在其调用和返回之间的某个时间点原子地生效 (takes effect)。
    2. 所有操作生效的顺序必须构成一个有效的序列（读必须返回最近写入的值）。
    3. 这个操作生效的顺序必须与操作的实际时间顺序一致：如果操作 A 在操作 B 开始前完成，那么在序列中 A 必须在 B 之前生效。
    4. 关键约束 (图 9-3): 一旦某个读取返回了新值，所有后续的读取（即使在写入完成前开始，但在该读取完成后开始）也必须返回新值。
    5. 原子操作 (CAS - Compare-and-Set) 也需要线性一致。
  • 线性一致性 vs 可串行化 (Serializability):
    • 可串行化: 事务隔离属性，保证事务效果等同于某个串行顺序，涉及多个对象，不保证实时性。每个事务在下一个事务开始之前运行完成。例如，事务A可能在事务B开始前提交，但可串行化允许调整顺序，只要结果符合某个串行执行
    • 线性一致性: 单个对象（寄存器）的新鲜度保证，保证操作实时有序。
    • 组合: 严格可串行化 (Strict Serializability) 或 强单副本可串行化 (Strong-1SR) = 线性一致性 + 可串行化。（2PL、真串行通常满足）
    • SSI 不满足: 快照隔离从历史快照读，不保证读到最新值。
  • 线性一致性的应用场景:
    • 锁定和领导选举: 必须所有节点就谁持有锁/谁是领导者达成一致。协调服务 (ZooKeeper, etcd) 提供此功能。
    • 约束和唯一性保证: 用户名唯一、库存不为负、防止超卖。需要所有节点对最新值有一致看法。
    • 跨信道的时序依赖 (图 9-5): Web服务器写文件存储 -> 发消息给缩放器 -> 缩放器读文件存储。如果存储非线性一致，消息队列可能比存储复制快，导致缩放器读到旧/空文件。需要线性一致性来保证“写后读”的因果关系。
  • 实现线性一致性的系统:
    • 单副本: 简单，但无容错。
    • 单主复制:
      • 可能线性一致：如果从主库或同步从库读。
      • 实际挑战: 领导者身份不确定性（脑裂）、异步复制的故障切换可能丢失写入（违反持久性和线性一致性）、并发错误、使用快照隔离。
    • 共识算法 (Paxos, Raft, Zab):
      • 可以安全实现线性一致性。包含防止脑裂和陈旧副本的机制。(ZooKeeper, etcd)
    • 多主复制:
      • 通常非线性一致：并发写入，异步复制，产生冲突。
    • 无主复制 (Dynamo风格):
      • 通常非线性一致。
      • 即使 W+R>N (严格法定人数) 也可能非线性一致 (图 9-6, 因网络延迟)。 图 9-6 非线性一致的执行，尽管使用了严格的法定人数
      • LWW（最后写入胜利）基于时钟 -> 非线性一致 (时钟偏斜)。
      • 宽松法定人数 -> 非线性一致。
      • 理论上 可通过同步读修复 + 写入前读法定人数实现，但性能差，且不支持线性一致的 CAS。
  • 线性一致性的代价:
    • 性能: 为了保证最新，可能需要跨节点同步通信，增加延迟。Attiya & Welch 证明线性一致操作的响应时间至少与网络延迟不确定性成正比。
      • 类比：多核 CPU 内存也不是默认线性一致的（因缓存），需要内存屏障，牺牲性能。
    • 可用性 (CAP 定理相关):
      • 场景 (图 9-7): 网络分区导致副本间通信中断。
      • 权衡:
        • 若要线性一致性 (C): 分区一侧的节点无法处理请求（或返回错误），牺牲可用性 (A)。服务不可用
        • 若要可用性 (A): 分区两侧节点独立处理请求，牺牲线性一致性 (C)。如多主复制
      • CAP 定理:
        • 最初表述：一致性 (C)、可用性 (A)、分区容错性 (P) 三选二。
        • 误导性: 分区容错 (P) 不是选项，是现实。
        • 更好表述: 网络分区发生时，必须在一致性 (特指线性一致性) 和可用性之间选择。
        • 局限性: 定义狭隘（只考虑线性一致性、网络分区），对系统设计帮助有限，已被更精确结果取代。
        • * CAP 实际意义与误区: CAP 迫使我们思考分区时的抉择，但这通常是关于降级策略（如提供部分可用性或陈旧数据）而非简单的二选一。
        • * PACELC 定理: 扩展了CAP，指出在没有分区 (P) 时 (Else)，系统需要在延迟 (L) 和一致性 (C) 之间权衡，更贴合实际性能考量。

三、顺序保证 (Ordering Guarantees)

  • 顺序的重要性:
    • 单主复制：主库确定写入顺序。
    • 可串行化：事务等效于某种顺序执行。
    • 时间戳/时钟：尝试给事件排序。
  • 顺序与因果关系 (Causality):
    • 因果关系: 事件间的依赖关系（因 -> 果）。
    • 例子: 问题 -> 回答；创建 -> 更新；写后读；事务读写依赖。
    • 因果一致性 (Causal Consistency): 系统必须按因果关系定义的顺序处理事件。如果读取了某个结果，必须也能读取导致该结果的原因。快照隔离提供因果一致性。
    • 全序 vs 偏序:
      • 全序 (Total Order): 任何两个元素都可比较 (如数字)。线性一致性强制所有操作进入一个全序。单一时间线。
      • 偏序 (Partial Order): 某些元素无法比较 (如集合)。因果关系定义了偏序。并发操作无法比较。分叉和合并的时间线。
    • 线性一致性 => 因果一致性: 线性一致性是更强的保证。
    • 因果一致性的优势:
      • 可能在不牺牲因果性的前提下，获得比线性一致性更好的性能和可用性。
      • 可能是网络延迟不敏感且分区时可用的最强一致性模型。
      • 研究方向：Bolt-on、COPS 等数据库。
    • 捕获因果关系:
      • 需要知道“什么发生在什么之前 (happens-before)”。
      • 类似“检测并发写入”中的版本向量，但需跟踪整个数据库。
      • 需要跟踪读操作的版本，以确定写操作的因果依赖。
  • 序列号顺序 (Sequence Number Ordering):
    • 动机: 显式跟踪所有因果关系开销大。
    • 方法: 使用逻辑时钟（如自增计数器）为操作分配序列号/时间戳，提供全序。
    • 目标: 生成**与因果一致 (consistent with causality)**的全序（若 A happens-before B，则 seq(A) < seq(B)）。
    • 单主: 简单，主库递增计数器即可。
    • 多主/无主/分区下的序列号生成:
      • 每个节点生成独立序列（奇偶、节点ID位）。
      • 物理时钟时间戳 (LWW)。
      • 预分配序列号区块。
      • 问题: 这些方法生成的序列号不一定与因果一致（节点处理速度不同、时钟偏斜、区块分配顺序）。
    • 兰伯特时间戳 (Lamport Timestamp):
      • 格式: (计数器, 节点ID)。提供唯一全序（先比计数器，再比节点ID）。
      • 机制: 每个节点维护本地计数器。节点和客户端都跟踪遇到的最大计数器值。请求和响应中携带最大计数器。收到更大的计数器时，节点立即更新本地计数器到 max(本地, 收到) + 1。
      • 保证: 产生的全序与因果一致。
      • 与版本向量区别: Lamport提供全序，但无法区分并发与因果依赖；版本向量可以区分，但不是全序且更占空间。
      • 图 9-8 Lamport 时间戳提供了与因果关系一致的全序。
    • * 时间与顺序的深层联系: 理解逻辑时钟（如 Lamport）和物理时钟（如 LWW）的局限性，以及它们如何与一致性模型交互（例如 LWW 因时钟偏斜导致非因果顺序），对于理解分布式系统行为至关重要。
    • 光有时间戳排序还不够:
      • 例子: 用户名唯一性约束。
      • 问题: 节点需要立即决定操作成功/失败。它无法知道其他节点是否正在并发执行冲突操作，也无法知道这些操作的（未来）时间戳。
      • 结论: 仅有操作的全序是不够的，还需要知道这个全序何时尘埃落定 (finalized/stable)。需要知道在我的操作之前，不会再有其他冲突操作插入。引向全序广播。

四、全序广播 (Total Order Broadcast)

  • 别名: 原子广播 (Atomic Broadcast)。
  • 目标: 在节点间可靠地、按相同顺序、恰好一次地传递消息。
  • 安全属性:
    1. 可靠交付 (Reliable Delivery): 消息不丢失，传递给一个节点就传递给所有节点。
    2. 全序交付 (Totally Ordered Delivery): 消息以相同顺序传递给每个节点。
  • 重要特性: 顺序在送达时固化，不允许后续插入。比时间戳排序更强。
  • 应用:
    • 状态机复制 (State Machine Replication): 数据库复制的基础。每个消息是写操作，按相同顺序应用 -> 副本一致。
    • 可串行化事务: 每个消息是确定性事务，按相同顺序执行 -> 分区/副本一致。
    • 锁服务/防护令牌: 追加获取锁请求到日志，日志顺序号 = 防护令牌 (如 ZK 的 zxid)。
  • 使用全序广播实现线性一致存储:
    • 线性一致写 (如 CAS):
      1. 追加操作意图到日志。
      2. 等待消息被读回（送达）。
      3. 检查日志中第一个声明该资源的消息。若是自己的，则成功；否则失败。
    • 线性一致读:
      • 将读操作追加到日志，等待其送达再执行读。
      • 获取最新日志位置，等待该位置前所有消息送达，再执行读 (ZK sync())。
      • 从同步更新的副本读取 (链式复制)。
  • 使用线性一致存储实现全序广播:
    • 需要线性一致的自增并返回 (increment-and-get) 或 CAS 寄存器。
    • 算法:
      1. 发送消息前，原子地对线性一致寄存器执行 “自增并返回”。
      2. 将获得的值作为序列号附加到消息。
      3. 广播消息。
      4. 接收节点按序列号顺序交付消息，等待填补空缺（因为序列号无间隙）。
    • 关键: 线性一致的原子操作保证序列号的全局一致性和无间隙性。
  • 等价关系: 线性一致CAS/自增 <==> 全序广播 <==> 共识 (Consensus)。

五、分布式事务与共识 (Distributed Transactions and Consensus)

  • 共识 (Consensus):
    • 目标: 让几个节点就某事达成一致，并且这个决定不可撤销。
    • 重要性: 分布式计算中最基本的问题之一。
    • 应用场景:
      • 领导选举: 避免脑裂。
      • 原子提交 (Atomic Commit): 跨多节点/分区的事务，要么全成功，要么全失败。
  • 原子提交:
    • 动机: 保证 ACID 中的原子性，尤其在多对象/多节点事务中。防止部分成功部分失败的不一致状态。
    • 单节点原子提交: 依赖写入 WAL 的顺序（先写数据，再写提交记录）。提交点是提交记录落盘。
    • 分布式原子提交挑战: 某些节点成功，某些失败（约束违反、网络丢失、节点崩溃）。需要协调。
    • 两阶段提交 (2PC):
      • 组件: 协调者 (Coordinator)、参与者 (Participants)。
      • 流程 (图 9-9):
        1. 阶段 1 (准备 Prepare): 协调者向所有参与者发送准备请求。参与者检查是否能提交（写日志、检查约束），若能则回复"是"（承诺提交），否则回复"否"。
        2. 阶段 2 (提交/中止 Commit/Abort):
          • 若所有参与者回复"是": 协调者决定提交，将决定写入自己日志（提交点），然后向所有参与者发送提交请求。
          • 若有参与者回复"否"或超时: 协调者决定中止，向所有参与者发送中止请求。
        • 图 9-9 两阶段提交（2PC）的成功执行
      • 关键: 参与者投票"是"后不能单方面反悔；协调者做出决定后不能更改。如果这个请求失败或超时，协调者必须永远保持重试，直到成功为止。没有回头路
      • 协调者失效 (图 9-10):
        • 若在 Prepare 前失效: 参与者超时中止。
        • 若在收到 “是” 之后、发送决定前失效: 参与者处于存疑 (in doubt) 状态，必须等待协调者恢复(什么都做不了)。 2PC 是阻塞协议。
        • 恢复: 协调者重启后读日志，将决定告知存疑的参与者。
        • 图 9-10 参与者投赞成票后，协调者崩溃。数据库 1 不知道是否提交或中止
      • 三阶段提交 (3PC): 非阻塞，但依赖有界网络延迟和响应时间，实践中不可靠。
      • * 非阻塞原子提交的困难: 真正实用的非阻塞原子提交协议非常难以设计，通常需要对系统模型做更强假设（如可靠故障检测器），或接受在极端故障下可能阻塞。
    • 分布式事务实践:
      • 类型:
        • 数据库内部事务 (同构)。
        • 异构事务 (跨不同技术，如 DB + 消息队列)。
      • 应用: 恰好一次 (Exactly-once) 消息处理 (原子提交 DB 操作 + 消息确认)。
      • XA (X/Open Architecture): 异构 2PC 的标准 API。
        • 架构: 应用通过 XA 驱动与参与者通信，协调者 (通常是库) 通过驱动回调控制参与者。
        • 问题:
          • 协调者单点故障 (SPOF) (若未高可用)。
          • 协调者日志使应用服务器有状态。
          • 存疑期间持有锁: 导致其他事务阻塞，严重影响可用性。
          • 孤立事务: 协调者日志丢失/损坏，需要管理员启发式决策 (手动提交/回滚，破坏原子性)。
          • 最小公分母: 无法利用高级特性（如跨系统死锁检测、SSI）。
          • 放大故障: 任何参与者失败都会导致事务失败。

XA 不是一个网络协议 —— 它只是一个用来与事务协调者连接的 C API。其他语言也有这种 API 的绑定；例如在 Java EE 应用的世界中，XA 事务是使用 Java 事务 API（JTA, Java Transaction API） 实现的，而许多使用 Java 数据库连接（JDBC, Java Database Connectivity） 的数据库驱动，以及许多使用 Java 消息服务（JMS） API 的消息代理都支持 Java 事务 API（JTA）。 XA 假定你的应用使用网络驱动或客户端库来与 参与者（数据库或消息服务）进行通信。如果驱动支持 XA，则意味着它会调用 XA API 以查明操作是否为分布式事务的一部分 —— 如果是，则将必要的信息发往数据库服务器。驱动还会向协调者暴露回调接口，协调者可以通过回调来要求参与者准备、提交或中止。

事务协调者需要实现 XA API。标准没有指明应该如何实现，但实际上协调者通常只是一个库，被加载到发起事务的应用的同一个进程中（而不是单独的服务）。它在事务中跟踪所有的参与者，并在要求它们 准备 之后收集参与者的响应（通过驱动回调），并使用本地磁盘上的日志记录每次事务的决定（提交 / 中止）。

如果应用进程崩溃，或者运行应用的机器报销了，协调者也随之往生极乐。然后任何带有 准备了 但未提交事务的参与者都会在疑虑中卡死。由于协调程序的日志位于应用服务器的本地磁盘上，因此必须重启该服务器，且协调程序库必须读取日志以恢复每个事务的提交 / 中止结果。只有这样，协调者才能使用数据库驱动的 XA 回调来要求参与者提交或中止。数据库服务器不能直接联系协调者，因为所有通信都必须通过客户端库。

许多 XA 的实现都有一个叫做 启发式决策（heuristic decisions） 的紧急逃生舱口：允许参与者单方面决定放弃或提交一个存疑事务，而无需协调者做出最终决定【76,77,91】。要清楚的是，这里 启发式 是 可能破坏原子性（probably breaking atomicity） 的委婉说法，因为它违背了两阶段提交的系统承诺。因此，启发式决策只是为了逃出灾难性的情况而准备的，而不是为了日常使用的。

  • 容错共识 (Fault-Tolerant Consensus):

    • 形式化定义:

      • 节点可以提议 (propose) 值，算法决定 (decide) 一个值。
      • 属性:
        1. 一致同意 (Uniform Agreement): 没有两个节点决定不同的值。
        2. 完整性 (Integrity): 没有节点决定两次。
        3. 有效性 (Validity): 决定的值必须是某个节点提议的。
        4. 终止 (Termination): 所有未崩溃节点最终都决定一个值 (活性属性)。

    • FLP 不可能性: 在纯异步系统模型中（无时钟/超时），若有节点可能崩溃，则不存在保证总是能终止的共识算法。

    • 现实: 实际系统使用超时（部分同步模型）或随机化，可以解决共识。

    • 容错性: 算法通常能容忍少于一半的节点故障 (f < n/2，即需要多数节点存活)。即使多数节点故障，安全属性（一致同意、完整性、有效性）通常仍保持。

    • 拜占庭故障: 假设节点不会恶意或随意偏离协议。处理拜占庭故障需要更复杂算法，容忍少于 1/3 的拜占庭节点。

    • 共识算法与全序广播:

      • 常见算法 (VSR, Paxos, Raft, Zab) 通常直接实现全序广播（决定值的序列），这比重复单值共识更高效。
      • 全序广播 ≈ 多轮共识。
      • * 共识算法的实现复杂性: 这些算法极其困难，需要处理各种并发边缘情况和组合故障（节点崩溃、消息丢失/重复/乱序、分区、时钟漂移），需要严谨证明和大量测试 (如 Jepsen)。即使是 Raft，工业级实现也充满挑战。
      • 全序广播相当于重复进行多轮共识（每次共识决定与一次消息传递相对应）：
        • 由于 一致同意 属性，所有节点决定以相同的顺序传递相同的消息。
        • 由于 完整性 属性，消息不会重复。
        • 由于 有效性 属性，消息不会被损坏，也不能凭空编造。
        • 由于 终止 属性，消息不会丢失。

    • 单主复制与共识:

      • 手动选择主库：是独裁，非容错共识。
      • 自动故障切换：需要共识来选举领导者。
      • 循环依赖？: 选主需共识，共识算法又依赖主？
      • 解决方案:
        • 纪元编号 (Epoch Number) (或 term/view/ballot): 保证每个纪元内领导者唯一。单调递增。
        • 法定人数 (Quorum): 领导者做决策前需获得法定人数（通常是多数）节点的投票。
        • 重叠法定人数: 领导者选举的法定人数与提议表决的法定人数必须重叠。确保领导者能知道是否有更高纪元的选举发生。
graph TD
    subgraph "纪元 N (Epoch N)"
        L_N(领导者 L_N)
        P_N(提案 P_N)
        L_N -- 提议 --> P_N
        P_N -- 需法定人数 Q_prop_N 批准 --> P_N_Approved(P_N 被批准)
    end

    subgraph "节点集合 (Nodes)"
        N1(节点1)
        N2(节点2)
        N3(节点3)
        N4(节点4)
        N5(节点5)
        style N1 fill:#lightgrey
        style N2 fill:#lightgrey
        style N3 fill:#lightgrey
        style N4 fill:#lightgrey
        style N5 fill:#lightgrey
    end

    subgraph "过渡/选举 (Epoch N+1 选举)"
        Trigger((怀疑 L_N 失败
或网络分区))
        Trigger --> Election{开始选举: 纪元 N+1}
        Election -- 寻求选票 --> N1
        Election -- 寻求选票 --> N2
        Election -- 寻求选票 --> N3
        Election -- 寻求选票 --> N4
        Election -- 寻求选票 --> N5

        N1 -- 投票给候选者 --> Quorum_Election[选举法定人数 Q_elect]
        N2 -- 投票给候选者 --> Quorum_Election
        N3 -- 投票给候选者 --> Quorum_Election
        N4 -- (可能未投票或投给别人) --> Election
        N5 -- (可能未投票或投给别人) --> Election

        Quorum_Election -- 选举出 --> L_Np1(新领导者 L_N+1
针对纪元 N+1)

        note1["例如: Q_elect = {N1, N2, N3}
多数为 3/5"]
        Quorum_Election -- 包含 --> note1
        style Quorum_Election fill:#lightblue,stroke:#333,stroke-width:2px
    end

    subgraph "纪元 N+1 (Epoch N+1)"
        L_Np1 -- 提议 P_N+1 --> Proposal_Np1{提案 P_N+1}
        Proposal_Np1 -- 寻求批准 --> N1
        Proposal_Np1 -- 寻求批准 --> N2
        Proposal_Np1 -- 寻求批准 --> N3
        Proposal_Np1 -- 寻求批准 --> N4
        Proposal_Np1 -- 寻求批准 --> N5

        N2 -- 同意提案 P_N+1 --> Quorum_Proposal[提案法定人数 Q_prop]
        N3 -- 同意提案 P_N+1 --> Quorum_Proposal
        N4 -- 同意提案 P_N+1 --> Quorum_Proposal
        N1 -- (可能拒绝或未响应) --> Proposal_Np1
        N5 -- (可能拒绝或未响应) --> Proposal_Np1

        note2["例如: Q_prop = {N2, N3, N4}
多数为 3/5"]
        Quorum_Proposal -- 包含 --> note2
        style Quorum_Proposal fill:#lightgreen,stroke:#333,stroke-width:2px

        Quorum_Proposal -- 批准 --> P_Np1_Approved(P_N+1 被批准
L_N+1 确认领导地位)

        OverlapNode((法定人数重叠
Q_elect 与 Q_prop 必须有交集
示例交集: N2, N3))
        style Overlap fill:#yellow,stroke:#f00,stroke-width:2px,stroke-dasharray: 5 5

        Quorum_Election -.-> Overlap
        Quorum_Proposal -.-> Overlap
    end

    %% 强调重叠节点
    style N2 fill:#aaccaa,stroke:#000,stroke-width:2px  
    style N3 fill:#aaccaa,stroke:#000,stroke-width:2px  

      %% 流程关系 (移除了链接上的注释)
    L_N --> Trigger
    P_N_Approved --> Trigger

    %% 注释 (使用标准 %% 注释)
    %% P_N_Approved --> Trigger: 这个链接表示旧纪元提案被批准后也可能触发新纪元选举（例如，网络恢复后发现领导者已更换）
    linkStyle default interpolate basis

  1. 节点集合: 我们有 5 个节点 (N1 到 N5)。法定人数（Quorum）通常是多数，这里是 3 个节点。

  2. 纪元 N: 存在一个领导者 L_N，它可能成功提出并批准了一些提案 (P_N)。

  3. 过渡/选举 (Epoch N+1 选举):

    • 触发: 某个时刻，节点们怀疑 L_N 挂了（或网络分区导致 L_N 无法有效工作），于是触发新一轮领导者选举。

    • 选举过程: 节点们进入纪元 N+1 的选举。候选者（可能就是某个节点）需要争取选票。

    • 选举法定人数 (Q_elect): 一个候选者必须获得法定人数的选票才能成为纪元 N+1 的领导者 (L_N+1)。在此例中，假设 N1, N2, N3 投票给了 L_N+1，达到了 3 票的法定人数。Q_elect = {N1, N2, N3} (图中浅蓝色区域代表参与选举投票的节点集合)。

  4. 纪元 N+1 (Epoch N+1):

    • 新领导者 L_N+1: L_N+1 现在是纪元 N+1 的领导者。

    • 提案过程: L_N+1 想要决定一个值（提案 P_N+1），它将这个提案发送给其他节点请求批准。

    • 提案法定人数 (Q_prop): 为了让提案 P_N+1 被接受，L_N+1 必须获得法定人数的节点的同意。在此例中，假设 N2, N3, N4 同意了提案。Q_prop = {N2, N3, N4} (图中浅绿色区域代表参与提案投票的节点集合)。

    • 批准: 收到法定人数的同意后，L_N+1 就可以认为提案 P_N+1 被批准了。

  5. 关键：法定人数重叠 (Overlap):

    • 观察: 选举法定人数 Q_elect = {N1, N2, N3} 和提案法定人数 Q_prop = {N2, N3, N4} 必须重叠。在这个例子中，重叠的节点是 N2 和 N3 (图中黄色虚线框强调，并且 N2, N3 节点背景色变为特殊色)。

    • 意义: 这是安全保证的核心。当 L_N+1 收到来自 Q_prop ({N2, N3, N4}) 的批准时，它知道这个批准集合中至少有一个节点 (N2 或 N3) 也参与了最近的（即纪元 N+1 的）领导者选举，并且投票选了 L_N+1（或者至少知道 L_N+1 是当前纪元的领导者）。

    • 安全检查: 如果在 L_N+1 发起提案 P_N+1 之后，发生了更高纪元（例如 N+2）的选举，并且那个选举也成功获得了法定人数（例如 Q_elect’），那么根据法定人数必须重叠的规则，Q_prop 和 Q_elect’ 也必须有重叠。这意味着 Q_prop 中至少会有一个节点知道存在一个更高纪元的领导者。这个节点在收到 L_N+1 的提案 P_N+1 时，就不会投赞成票，因为它知道 L_N+1 已经“过时”了。

    • 结论: 因此，如果 L_N+1 成功从 Q_prop 收集到了足够的赞成票，它就可以安全地推断：在 Q_prop 中的所有节点（包括那些参与了选举投票的重叠节点 N2, N3）都没有观察到任何高于 N+1 的纪元。这给了 L_N+1 信心，确认自己仍然是有效的领导者，可以安全地决定 P_N+1 的值。

共识的局限性: * 性能: 节点在做出决定之前对提议进行投票的过程是一种同步复制，延迟较高。通常数据库会配置为异步复制模式。在这种配置中发生故障切换时，一些已经提交的数据可能会丢失 —— 但是为了获得更好的性能，许多人选择接受这种风险。 * 多数要求: 至少 3 节点容忍 1 故障，5 节点容忍 2 故障。分区时少数派阻塞。 * 成员变更: 静态成员假设常见，动态成员变更复杂。 * 超时依赖: 对网络延迟敏感，可能因误判导致频繁选主，性能下降。

  • * 无共识的设计模式 (Consensus-Free Design Patterns):
    • 并非所有问题都需要强共识。有时可以通过以下方式避免全局协调：
      • 幂等性 (Idempotency): 操作重复执行结果相同。
      • CRDTs (Conflict-free Replicated Data Types): 特殊的数据结构，并发修改可自动合并且保证最终一致。
      • Sagas (补偿事务): 通过一系列本地事务加补偿操作来模拟分布式事务的回滚。
    • 这些模式与多主/无主复制的设计哲学一致，适用于对一致性要求稍低但对可用性/性能要求高的场景。
  • 成员与协调服务 (Membership and Coordination Services):
    • 例子: ZooKeeper (Zab), etcd (Raft), Consul。
    • 定位: 不是通用数据库，是容错的协调服务。存储少量关键元数据。
    • 核心: 内部使用共识算法实现全序广播。
    • 提供功能:
      • 线性一致原子操作: CAS 用于锁、选举等。
      • 操作全序: 提供单增 ID (zxid) 用于防护令牌等。
      • 失效检测: 客户端会话 + 心跳 + 临时节点 (Ephemeral Nodes)。当会话超时时（ZooKeeper 称这些节点为 临时节点，即 ephemeral nodes），会话持有的任何锁都可以配置为自动释放。
      • 变更通知 (Watches): 监听数据变化，避免轮询。
    • * 角色和限制:
      • 它们是基础设施，非直接业务存储。
      • 写入性能有限: 共识开销大，不适合高频写入。
      • 简单数据模型: 功能不如通用数据库。
      • “外包共识”: 应用依赖它们处理协调复杂性，但需理解其原语的正确用法。应用最初只能在单个节点上运行，但最终可能会增长到数千个节点。试图在如此之多的节点上进行多数投票将是非常低效的。相反，ZooKeeper 在固定数量的节点（通常是三到五个）上运行，并在这些节点之间执行其多数票，同时支持潜在的大量客户端。因此，ZooKeeper 提供了一种将协调节点（共识，操作排序和故障检测）的一些工作 “外包” 到外部服务的方式。
    • 典型用途:
      • 领导选举。
      • 配置管理。
      • 服务发现 (也就是找出你需要连接到哪个 IP 地址才能到达特定的服务，尽管 DNS 也能做，且不需共识)。
      • 分布式锁/信号量。
      • 集群成员管理 (哪些节点当前活跃)。
    • 优势: 将协调的复杂性（共识、故障检测）外包给专门服务。
    • 运行模式: 通常部署在少数几个节点 (3 或 5)，服务大量客户端。
    • 数据特性: 数据量小，变化不频繁。

mysql的二阶段提交：

Redo Log 的持久化由参数 innodb_flush_log_at_trx_commit 控制：

  • 0：事务提交时不主动刷盘，依赖后台线程每秒刷盘（可能丢失 1 秒数据） 
  • 1（默认）：每次事务提交时强制将 Redo Log 从 Buffer 写入磁盘（fsync），确保崩溃后数据不丢失 
  • 2：仅写入操作系统的 Page Cache，不立即刷盘（依赖操作系统刷盘策略）
  • 其他触发刷盘的情况：
    • Redo Log Buffer 使用过半时触发写盘（仅 write，不 fsync） 
    • 并行事务提交时可能连带刷盘
  • Binlog 是逻辑日志，用于主从复制和数据恢复。其刷盘由参数 sync_binlog 控制：
    • 0：依赖操作系统刷盘（可能丢失多个事务） 
    • 1（默认）：每次事务提交时强制刷盘（fsync） 
    • N（N>1）：累积 N 个事务后刷盘（性能和可靠性折中） 
  • Binlog 写入分两步：
    • write：写入文件系统的 Page Cache（内存）。
    • fsync：持久化到磁盘 两阶段提交（2PC）
  • Prepare 阶段：将 Redo Log 标记为 prepare 状态并刷盘 
  • Commit 阶段：
    1. 写入 Binlog 并刷盘（若 sync_binlog=1）。
    2. 将 Redo Log 标记为 commit 状态（无需再次 fsync） 
  • 崩溃恢复逻辑：
    • 若 Redo Log 处于 prepare 但 Binlog 未提交，事务回滚。
    • 若 Redo Log 处于 prepare 且 Binlog 已提交，事务自动提交 刷盘前宕机的影响
  • Buffer Pool 未刷盘：内存中的修改丢失，但通过 Redo Log 恢复 
  • Redo Log 未刷盘：若事务未提交，数据丢失；若已提交但未刷盘，通过 Binlog 和两阶段提交恢复 
  • Binlog 未刷盘：事务视为未提交，回滚

六、本章小结

  • 回顾了线性一致性 (简单但慢/可用性差) 和因果一致性 (更弱但更快/更可用)，以及其他一致性模型谱系。
  • 强调了共识的重要性：解决节点间就某事达成唯一、不可撤销的决定。
  • 许多分布式问题等价于共识：线性一致 CAS(寄存器需要基于当前值是否等于操作给出的参数，原子地 决定 是否设置新值)、原子提交( 数据库必须 决定 是否提交或中止分布式事务)、全序广播(消息系统必须 决定 传递消息的顺序)、锁(当几个客户端争抢锁或租约时，由锁来 决定 哪个客户端成功获得锁)、成员服务(给定某种故障检测器（例如超时），系统必须 决定 哪些节点活着，哪些节点因为会话超时需要被宣告死亡)、唯一约束(当多个事务同时尝试使用相同的键创建冲突记录时，约束必须 决定 哪一个被允许，哪些因为违反约束而失败)。
  • 单领导者简化了问题，但领导者变更需要共识。
  • 处理领导者故障的三种方式：阻塞等待、人工切换、共识算法自动切换。
  • 共识算法 (Paxos, Raft, Zab) 提供了容错的基础保证，但实现复杂。
  • 协调服务 (ZooKeeper, etcd) 将共识能力封装为服务，供应用使用，但有其局限性。
  • 并非所有系统都需要共识；存在无共识的设计模式（幂等性、CRDT、Sagas）。
  • 理论研究对理解分布式系统的可能性和限制至关重要。
  • * 实践中的选择: 没有“最好”的一致性模型或共识算法，只有最适合特定需求的。选择时需要综合考虑：业务对数据新鲜度和一致性的要求、系统对性能（延迟、吞吐量）的要求、系统对可用性和分区容错性的要求、开发和运维的复杂度及成本。 如果你发现自己想要解决的问题可以归结为共识，并且希望它能容错，使用一个类似 ZooKeeper 的东西是明智之举。