DDIA

DDIA 笔记：第六章 - 复制

核心思想： 在多台机器上保存相同数据的副本，以实现高可用性、低延迟和可伸缩性。本章重点讨论 数据变更 的复制以及相关的挑战和算法。

本章假设： 数据集足够小，可以放在单台机器上。分区（Sharding）将在下一章讨论。

复制的原因：

  1. 高可用性 (High Availability): 单个节点（或整个数据中心）故障时，系统仍能继续工作。
  2. 降低延迟 (Reduced Latency): 数据副本靠近用户地理位置，减少访问时间。
  3. 提高读吞吐量 (Increased Read Throughput): 读请求可以分散到多个副本上，实现读扩展。

复制的核心挑战： 如何处理复制数据的 变更 (Change)。

三种主要的复制算法：

  1. 单领导者（Single Leader）
  2. 多领导者（Multi-Leader）
  3. 无领导者（Leaderless）

一、 领导者与追随者 (Leader-Based Replication)

也称为 主/从 (Master/Slave) 或 主动/被动 (Active/Passive) 复制。 图 5-1 基于领导者的（主/从）复制

工作原理 (图 5-1)：

  1. 领导者 (Leader/Master/Primary): 指定一个副本作为领导者。所有 写请求 必须发送给领导者。领导者首先将新数据写入其本地存储。
  2. 追随者 (Follower/Read Replica/Slave/Secondary/Hot-Standby): 其他副本。领导者将数据变更（复制日志/变更流）发送给所有追随者。
  3. 追随者应用变更: 每个追随者按照与领导者 相同的顺序 应用写操作，更新本地副本。
  4. 读请求: 可以发送给领导者或 任何 追随者（追随者通常是只读的）。

应用场景： 关系型数据库 (PostgreSQL, MySQL, SQL Server AlwaysOn, Oracle Data Guard)、非关系型数据库 (MongoDB, RethinkDB)、分布式消息队列 (Kafka, RabbitMQ HA Queues)。

1. 同步复制 vs. 异步复制

图 5-2 基于领导者的复制：一个同步从库和一个异步从库

  • 同步 (Synchronous): 领导者等待 至少一个 同步追随者确认收到写入后，才向客户端报告成功。
    • 优点: 追随者有与领导者一致的最新数据副本。如果领导者失效，数据能保证在同步追随者上。
    • 缺点: 如果同步追随者未响应（宕机、网络问题），领导者 必须阻塞 所有写入，影响可用性。
    • 实践: 通常只有一个追随者是同步的（半同步/Semi-Synchronous），其他是异步的。如果同步追随者失效，会将一个异步追随者提升为同步。
  • 异步 (Asynchronous): 领导者发送变更消息给追随者，不等待 响应。
    • 优点: 即使所有追随者都落后，领导者也能继续处理写入，可用性高。
    • 缺点: 如果领导者失效且不可恢复，尚未复制到追随者的写入会 丢失。写入的 持久性 (Durability) 被削弱。
    • 实践: 非常常用，尤其是在追随者众多或地理分布广泛时。

2. 设置新追随者

目标： 在不停止服务的情况下，让新追随者拥有领导者数据的精确副本。

步骤：

  1. 获取快照: 在某个时间点获取领导者的一致性快照（通常无需锁库，备份功能）。
  2. 复制快照: 将快照拷贝到新追随者节点。
  3. 连接与拉取: 追随者连接到领导者，请求快照点 之后 发生的所有数据变更（通过日志序列号 LSN 或 binlog 坐标定位）。
  4. 追赶: 处理完积压的变更后，追随者 “赶上 (caught up)” 领导者，之后持续同步。

3. 处理节点宕机

目标： 即使个别节点失效，也能保持系统运行。

  • 追随者失效 (Follower Failure): 追赶恢复 (Catch-up Recovery)
    • 追随者记录已处理的变更日志。
    • 重启后，从日志知道最后处理的事务。
    • 连接领导者，请求断开期间的变更，追赶上来。
  • 领导者失效 (Leader Failure): 故障切换 (Failover)
    • 过程:
      1. 确认失效: 通常使用 超时 (Timeout)。节点间心跳检测，一段时间无响应则认为失效。
      2. 选举新领导者: 通过选举过程（剩余副本多数投票）或由 控制器节点 指定。通常选择拥有最新数据的追随者。这是一个 共识 (Consensus) 问题 (Ch9)。
      3. 重新配置:
        • 客户端将写请求发送给新领导者。
        • 其他追随者从新领导者拉取变更。
        • 旧领导者恢复后，需降级为追随者。
    • 潜在问题:
      • 异步复制的数据丢失: 新领导者可能没有老领导者最后的写入。常见做法是 丢弃 这些未复制的写入，破坏持久性承诺。
      • 主键冲突: 如果使用自增 ID，落后的追随者成为新主后，可能重用已被老主分配的 ID (GitHub 事故例子，导致数据不一致和泄露)。
      • 脑裂 (Split Brain): 两个节点都认为自己是领导者。如无冲突解决机制，会导致数据丢失/损坏。需要 屏障 (Fencing) / STONITH 机制（强制关闭一个）。
      • 超时配置: 过长则恢复慢，过短则可能因瞬时负载/网络抖动导致不必要的切换，加剧问题。
    • 结论: 自动故障切换复杂且有风险，运维有时倾向于手动切换。

4. 复制日志的实现

  • 基于语句的复制 (Statement-Based Replication):
    • 领导者记录执行的 INSERT/UPDATE/DELETE 语句，发送给追随者执行。记录的是操作语句（如 UPDATE users SET balance=200 WHERE id=1）。日志体积小（一条语句可能影响多行）。
    • 问题:
      • 非确定性函数: NOW(), RAND() 在不同副本上可能产生不同结果。
      • 依赖顺序/数据的语句: 自增列、UPDATE...WHERE... 必须按 完全相同 顺序执行，并发事务下困难。
      • 副作用: 触发器、存储过程、UDF 可能产生不同效果。
    • 使用: MySQL 5.1 前，现在仍可选但有风险。VoltDB 要求事务确定性。因为它相当紧凑，现在有时候也还在用。但现在在默认情况下，如果语句中存在任何不确定性，MySQL 会切换到基于行的复制。 主节点上多个事务可能并发执行，但最终提交顺序由主节点决定，并记录在二进制日志中。从节点必须严格按此顺序重放语句。 主节点：两个事务更新同一行：-- 事务1（先执行） UPDATE accounts SET balance = balance + 100 WHERE user_id = 1; -- balance 从 100 → 200 -- 事务2（后执行） UPDATE accounts SET balance = balance * 2 WHERE user_id = 1; -- balance 从 200 → 400 从节点：如果语句重放顺序颠倒：-- 事务2 先执行 UPDATE accounts SET balance = balance * 2 WHERE user_id = 1; -- balance 从 100 → 200 -- 事务1 后执行 UPDATE accounts SET balance = balance + 100 WHERE user_id = 1; -- balance 从 200 → 300 从节点：如果语句重放顺序颠倒：– 事务2 先执行 UPDATE accounts SET balance = balance * 2 WHERE user_id = 1; – balance 从 100 → 200 – 事务1 后执行 UPDATE accounts SET balance = balance + 100 WHERE user_id = 1; – balance 从 200 → 300 解决方案：
      1. 单线程重放：从节点强制单线程执行日志（牺牲性能）。
      2. 基于行的复制（RBR）：直接复制数据变更结果（如行变化后的值），而非语句，避免顺序依赖。
      3. 混合模式：对非确定性语句使用 RBR，其他使用 SBR。
  • 传输预写式日志 (Write-Ahead Log, WAL Shipping):
    • 领导者将 WAL (物理日志，记录磁盘块变更) 发送给追随者。记录的是存储引擎对磁盘块的具体修改（如“将第 100 号页的偏移量 200 处写入值 0xFF”）。mysql-redo log
    • 优点: 精确复制，与主库结构一致，数据一致性高。- 性能较高（直接记录物理操作，无需解析 SQL）。
    • 缺点: 与存储引擎 紧密耦合。主从库通常需要运行 相同版本 的软件，增加 零停机升级 的难度。- 外部系统无法直接解析（日志内容为二进制物理操作）。
    • 使用: PostgreSQL, Oracle。
  • 逻辑日志复制 (Logical Log Replication / Row-Based Replication):
    • 使用与存储引擎 解耦 的日志格式，描述行级别的数据变更。- 记录的是数据变更的结果（如“插入一行数据 (id=1, name='Alice')”）。
      • Insert: 包含所有列的新值。
      • Delete: 包含唯一标识被删行所需的信息（通常是主键，或所有列旧值）。
      • Update: 包含唯一标识被更新行所需的信息，以及所有列的新值（或至少是变化列的新值）。
    • 优点: 向后兼容更容易（主从可不同版本/引擎），易于外部系统解析（变更数据捕获 / Change Data Capture, CDC - Ch11）。
    • 使用: MySQL 二进制日志（配置为 row 格式）-binlog。
  • 基于触发器的复制 (Trigger-Based Replication):
    • 使用数据库触发器（或存储过程）在数据变更时执行自定义代码，将变更写入单独的日志表。外部程序读取此表进行复制。
    • 优点: 灵活性高（复制子集、异构数据库复制、自定义冲突解决）。
    • 缺点: 开销高、易出错、限制多。
    • 使用: Oracle GoldenGate (日志读取型，类似思想), Databus for Oracle, Bucardo for Postgres。

二、 复制延迟问题 (Problems with Replication Lag)

背景： 读扩展架构依赖 异步 复制。追随者可能落后于领导者，导致 最终一致性 (Eventual Consistency)。

最终一致性： 不一致是暂时的，如果停止写入，副本最终会达到一致状态。“最终” 时间无上限，延迟可能从毫秒级到分钟级甚至更长。

由复制延迟引发的问题：

1. 读己之写 (Reading Your Own Writes)

  • 问题: 用户写入数据（到领导者），然后立即读取（可能从落后的追随者），看不到刚刚提交的数据，以为丢失了 (图 5-3)。
  • 需要: 写后读一致性 (Read-after-write / Read-your-writes Consistency) —— 保证用户总能看到 自己 提交的更新。
  • 实现方法:
    • 读主: 用户 可能修改过 的内容（如个人资料）总是从领导者读取。总是从主库读取用户自己的档案，如果要读取其他用户的档案就去从库。如果应用中的大部分内容都可能被用户编辑，那这种方法就没用了
    • 时间窗口: 上次更新后的一段时间内（如1分钟内）从领导者读取。
    • 监控延迟: 不查询延迟过大的追随者。
    • 版本/时间戳跟踪: 客户端记住写入版本/时间戳，读取时确保副本已达到该进度。如果当前从库不够新，则可以从另一个从库读取，或者等待从库追赶上来。
    • 跨设备一致性: 更复杂，需要中心化元数据记录更新时间/版本，并可能需要将用户所有设备的请求路由到同一数据中心/副本。（同一位用户从多个设备（例如桌面浏览器和移动 APP）请求服务的时候）

2. 单调读 (Monotonic Reads)

  • 问题: 用户先后进行两次读取（可能命中不同延迟的追随者），第二次读取看到了比第一次读取 更旧 的数据，如同 时光倒流 (图 5-4)。 图 5-4 用户首先从新副本读取，然后从旧副本读取。时间看上去回退了。为了防止这种异常，我们需要单调的读取。

  • 需要: 单调读保证 —— 用户进行多次读取时，不会看到时间回退（后续读取不会得到比之前读取更旧的数据）。

  • 实现方法:

    • 确保 同一用户 的读取总是定向到 同一副本（例如基于用户 ID 哈希）。如果副本失效，需要重新路由。

3. 一致前缀读 (Consistent Prefix Reads)

  • 问题: 存在因果关系的写入序列（如问题A -> 回答B），由于不同分区的复制延迟不同，观察者可能先看到回答B，再看到问题A，违反 因果关系 (图 5-5)。 图 5-5 如果某些分区的复制速度慢于其他分区，那么观察者可能会在看到问题之前先看到答案。
  • 需要: 一致前缀读保证 —— 如果一系列写入按特定顺序发生，任何人读取这些写入时，也会看到它们以同样的顺序出现。
  • 场景: 在 分区/分片 (Partitioned/Sharded) 数据库中尤为重要 (Ch6)。
  • 实现方法:
    • 确保因果相关的写入进入 同一分区（不总可行）。
    • 使用显式跟踪 因果依赖 的算法 (后续讨论)。

4. 复制延迟的解决方案

在使用最终一致的系统时，如果复制延迟增加到几分钟甚至几小时，则应该考虑应用程序的行为。

  • 应用层处理: 接受最终一致性，或者在应用代码中实现更强保证（如读主库、写后读）。但这复杂且易错。
  • 数据库事务: 提供更强的保证，简化应用开发。单节点事务成熟，分布式事务更复杂 (Ch7, Ch9)。
  • 重要性: 不要假设异步复制是同步的。要考虑延迟增加时的系统行为。

三、 多主复制 (Multi-Leader Replication)

也称 多领导者、主-主 (Master-Master) 或 主动-主动 (Active/Active) 复制。

核心思想： 允许 多个 节点接受写请求。每个主库同时也是其他主库的追随者。

1. 应用场景

  • 运维多个数据中心 (图 5-6)

    • 在每个数据中心内使用常规的主从复制；在数据中心之间，每个数据中心的主库都会将其更改复制到其他数据中心的主库中。
    • 对比单主:
      • 性能: 写入可在本地数据中心处理，跨数据中心异步复制，用户感知延迟低。
      • 容忍数据中心停机: 每个数据中心可独立运行，故障恢复后自动同步。
      • 容忍网络问题: 对跨数据中心网络抖动更具韧性。
    • 主要缺点: 两个不同的数据中心可能会同时修改相同的数据，写冲突 (Write Conflicts) 必须解决。
    • 实现: 某些数据库内置，或使用外部工具 (Tungsten Replicator for MySQL, BDR for PostgreSQL, Oracle GoldenGate)。
    • 风险: 配置复杂，易与数据库其他特性（自增键、触发器、约束）冲突，常被认为危险。 图 5-6 跨多个数据中心的多主复制

  • 需要离线操作的客户端 (Offline Operation)

    • 场景：日历应用等，设备离线时仍需读写。
    • 架构：每个设备是一个“数据中心”，本地数据库是主库，上线后与其他设备/服务器进行多主异步同步。复制延迟可能很长。
    • 工具：CouchDB 为此设计。

  • 协同编辑 (Collaborative Editing)

    • 场景：Google Docs, Etherpad 等允许多人同时编辑。
    • 架构：本地副本立即应用更改，异步复制到服务器和其他用户。
    • 如果避免锁定，允许多用户并发编辑，就需要处理多主复制的挑战，尤其是冲突解决。

2. 处理写入冲突

多主复制的最大问题。

  • 例子: 两人同时编辑同一维基页面标题 (图 5-7)。 图 5-7 两个主库同时更新同一记录引起的写入冲突

  • 冲突检测时机: 通常是 异步 检测（否则失去多主优势）。冲突在写入成功后才被发现。

  • 避免冲突:

    • 最简单策略：确保特定记录的所有写入通过 同一个主库（如按用户ID路由）。
    • 局限性：数据中心故障切换、用户迁移时可能失效。

  • 收敛至一致状态 (Convergence):

    • 目标：所有副本最终必须达到 相同 的最终值。
    • 冲突合并解决 (Conflict Resolution) 方法:
      • 最后写入胜利 (Last Write Wins, LWW): 基于时间戳/唯一ID，保留最新/ID最大的写入，丢弃 其他写入。极易丢失数据。
      • 副本ID优先: 基于副本ID大小决定胜者。同样 丢失数据。
      • 合并值: 将冲突值组合（如字符串拼接 “B/C”）。
      • 记录冲突: 保留所有冲突版本，编写应用程序代码（可能提示用户）来解决。

  • 自定义冲突解决逻辑:

    • 写时执行: 数据库检测到冲突时调用处理程序（后台运行，需快速，不能交互）。如 Bucardo。
    • 读时执行: 检测到冲突时存储所有版本，读取时返回给应用，由应用解决（可交互）并写回。如 CouchDB。
    • 粒度: 通常是行/文档级别，而非事务级别。

  • 自动冲突解决 (研究方向):

    • CRDTs (Conflict-free Replicated Datatypes): 自动合并的数据结构（集合、映射、计数器等）。(Riak 2.0 实现)
    • 可合并的持久数据结构: 跟踪历史（类似Git），使用三向合并。
    • 操作转换 (Operational Transformation, OT): 用于协同编辑中文本等有序列表。

  • 冲突的复杂性: 除了直接修改同一字段，还可能存在更微妙的冲突（如会议室预订例子中的约束冲突）。

3. 多主复制拓扑 (图 5-8)

图 5-8 三种可以在多主复制中使用的拓扑示例。 描述节点间通信路径。

  • 全部到全部 (All-to-All): 每个主库发送给所有其他主库。容错性好，但可能因网络延迟导致 消息乱序 (图 5-9)。 **图 5-9 使用多主复制时，写入可能会以错误的顺序到达某些副本
  • 环形 (Circular): A->B->C->A。MySQL 默认。
  • 星形 (Star): 一个中心节点转发给其他节点。
  • 环形/星形问题: 单点故障可能中断复制流。需要 转发 机制和 环路检测（基于节点ID）。
  • 乱序问题 (Causality): 更新可能先于插入到达某节点。需要 因果排序 (Causal Ordering)。版本向量 (Version Vectors) (后述) 可解决，但很多系统实现不完善（如 BDR 缺乏，Tungsten 不检测冲突）。需谨慎测试。

四、 无主复制 (Leaderless Replication)

放弃主库概念，任何副本 都可以直接接受客户端写请求（或通过 协调者 (Coordinator) 节点转发，协调者不决定顺序）。

代表: Amazon Dynamo 及其衍生品 (Riak, Cassandra, Voldemort) - Dynamo 风格。

1. 当节点故障时写入数据库 (图 5-10)

图 5-10 法定写入，法定读取，并在节点中断后读修复。

  • 写入: 客户端并行发送写入到 n 个副本。等待 w 个副本确认成功即可认为写入成功。忽略失败/超时的副本。
  • 读取: 客户端并行发送读取到 n 个副本。等待 r 个副本响应。可能收到不同版本的值，使用 版本号 确定最新值。

2. 读修复 (Read Repair) 和 反熵 (Anti-Entropy)

用于使落后的副本赶上。

  • 读修复: 客户端读取时发现不同版本，将最新值写回持有旧值的副本。适用于 频繁读取 的数据。
  • 反熵过程: 后台进程持续扫描副本间差异，并复制缺失数据。处理 不频繁读取 的数据。非所有系统都实现（如 Voldemort 无）。

3. 读写的法定人数 (Quorums)

  • n = 副本数
  • w = 写入成功所需的最小确认数 (Write Quorum)
  • r = 读取成功所需的最小响应数 (Read Quorum)
  • 法定人数条件: w + r > n
    • 保证: 读取操作至少能命中一个包含了最新成功写入的节点 (图 5-11)。
    • 容错性:
      • 如果 $w < n$，节点不可用时仍可写入。
      • 如果 $r < n$，节点不可用时仍可读取。
      • 例子: $n=3, w=2, r=2$ 可容忍 1 个节点失效。$n=5, w=3, r=3$ 可容忍 2 个节点失效。
    • 常见配置: n 为奇数, $w = r = (n+1)/2$ （多数法定人数）。
    • 灵活配置: 可调整 w, r 以适应读/写负载（如写少读多：$w=n, r=1$）。
    • 操作: 请求发往所有 n 个副本，等待 w 或 r 个成功响应。 **图 5-11 如果 $w + r > n$，读取 r 个副本，至少有一个副本必然包含了最近的成功写入。

4. 法定人数一致性的局限性

w + r > n 并不绝对保证读到最新值。 可能返回陈旧值的 边缘情况：

  • 宽松法定人数 (Sloppy Quorum): (见下) 写入和读取的节点集可能不重叠。
  • 并发写入: LWW 可能因时钟偏差丢失 “后” 写入。合并是更安全的方案。
  • 并发读写: 读取可能刚好发生在写入只完成一部分副本时。
  • 写入失败但部分成功: 写入操作整体失败，但成功的副本 未回滚，后续读取可能读到失败的值。
  • 节点故障与恢复: 持有新值的节点挂掉，从持有旧值的副本恢复，导致新值副本数 < w。
  • 时序问题: (Ch9 细讲)

结论: Dynamo 风格优化可用性和分区容忍性，通常提供 最终一致性。不能假设强一致性保证（如读写、单调读等）。

监控陈旧度: 很重要但困难（无固定写入顺序）。需要量化“最终”。

5. 宽松法定人数 (Sloppy Quorum) 与 提示移交 (Hinted Handoff)

  • 问题: 网络分区可能使客户端无法连接到足够数量的“主”副本以满足法定人数 w 或 r。
  • 宽松法定人数: 即使无法联系到足够的“主”副本，只要总共联系到 w 或 r 个 任何 可达副本，就认为操作成功。写入会临时存放在这些非“主”节点上。
  • 提示移交: 网络恢复后，临时持有写入的节点将数据 移交 给正确的“主”副本。
  • 优点: 提高 写入可用性 (只要有 w 个节点可用即可写)。
  • 缺点: 进一步削弱一致性。即使 $w+r>n$，读取也 不保证 看到最新值，直到提示移交完成。
  • 配置: 在 Riak 中默认开启，Cassandra/Voldemort 中默认关闭。

6. 运维多个数据中心 (无主复制)

  • 适用性: 天然适合，能容忍并发写入、网络中断和延迟。
  • 实现方式:
    • Cassandra/Voldemort: n 包含所有数据中心节点。客户端通常等待本地数据中心的法定人数响应，跨数据中心复制异步进行。
    • Riak: n 是单个数据中心内的副本数。跨数据中心复制在后台异步进行（类似数据中心间的多主复制）。

7. 检测并发写入

并发写入（来自客户端，或读修复/提示移交）不可避免，需要解决冲突以实现 收敛 (Convergence)。

  • 问题: 事件可能以不同顺序到达不同节点 (图 5-12)，简单覆盖导致永久不一致。 图 5-12 并发写入 Dynamo 风格的数据存储：没有明确定义的顺序。

  • 最后写入胜利 (Last Write Wins, LWW):

    • 基于时间戳（需要良好同步的时钟，Ch8 讨论问题）或任意唯一 ID。
    • 选择“最新”的写入，默默丢弃 其他并发写入。
    • 缺点: 极易丢失数据，即使写入报告成功。（以 持久性 为代价：如果同一个键有多个并发写入，即使它们反馈给客户端的结果都是成功的（因为它们被写入 w 个副本），也只有一个写入将被保留，而其他写入将被默默地丢弃。此外，LWW 甚至可能会丢弃不是并发的写入）
    • 安全用法: 仅当键写入一次后即 不可变 (Immutable) 时（如用 UUID 作键）。
    • 使用: Cassandra (唯一方式), Riak (可选)。

  • “此前发生” (Happens-Before) 关系和并发:

    • 定义:
      • A happens-before B：如果 B 知道/依赖/构建于 A。
      • A 和 B 并发 (Concurrent)：如果 A 不 happens-before B，且 B 也不 happens-before A。（它们互相不知道对方）
    • 目标: 需要算法判断操作是顺序的（后者覆盖前者）还是并发的（需要解决冲突）。

  • 捕获 Happens-Before 关系 (单副本示例 - 图 5-13, 图 5-14)

    • 版本号 (Version Number): 服务器为每个键维护版本号，写入时递增。
    • 读: 返回所有未覆盖的值 + 最新版本号。
    • 写: 客户端必须包含 上次读取的版本号 (V_prev)，并将读取到的所有值合并后写入。
    • 服务器处理写 (Value’, V_prev):
      • 覆盖所有版本号 <= V_prev 的值。
      • 保留所有版本号 > V_prev 的值（视为并发）。
      • 分配新版本号 V_new 给写入的值。
      • 返回所有未覆盖的值（包括新写入的）给客户端。
    • 结果: 不丢失数据，但客户端需要 合并并发值 (Siblings)。

  1. 初始状态 购物车为空，版本号为0。

  2. 客户端1写入牛奶（版本1） 客户端1首次添加牛奶，服务器分配版本号1，存储牛奶，返回版本1。此时购物车内容为：[牛奶] (v1)。

  3. 客户端2写入鸡蛋（版本2） 客户端2尝试添加鸡蛋，携带版本号0（认为购物车为空）。服务器发现当前版本为1，将鸡蛋视为并发写入，分配版本号2。此时购物车保留两个并发值：

    • [牛奶] (v1)
    • [鸡蛋] (v2) 收到所有并发值（牛奶v1、鸡蛋v2）和最新版本号v2。

  4. 客户端1写入面粉（版本3） 客户端1基于版本1的牛奶添加面粉，合并为[牛奶，面粉]。服务器接受此写入（版本1存在），覆盖牛奶，分配版本号3。此时购物车保留：

    • [鸡蛋] (v2)（未被覆盖）
    • [牛奶，面粉] (v3) 收到所有并发值（鸡蛋v2、牛奶面粉v3）和版本号v3

  5. 客户端2写入火腿（版本4） 之前收到牛奶v1和鸡蛋v2，合并为[牛奶, 鸡蛋]）添加火腿，合并为[鸡蛋，牛奶，火腿]。服务器接受此写入（版本2的鸡蛋存在），覆盖鸡蛋，分配版本号4。此时购物车保留：

    • [牛奶，面粉] (v3)（未被覆盖）
    • [鸡蛋，牛奶，火腿] (v4) 客户端2收到所有并发值（牛奶面粉v3、牛奶鸡蛋火腿v4）和版本号v4

  6. 客户端1写入培根（版本5） - 客户端1的视角：

    • 之前收到鸡蛋v2（已过期）和牛奶面粉v3。

    • 合并为[牛奶, 面粉, 鸡蛋]（假设客户端自动合并过期值）。

    • 添加培根，发送[牛奶, 面粉, 鸡蛋, 培根]，并携带版本号v3。

    • 服务器处理：

      • 检查版本号v3是否存在，发现牛奶面粉v3未被覆盖。
      • 覆盖牛奶面粉v3，生成新值[牛奶, 面粉, 鸡蛋, 培根] (v5)。
      • 保留其他并发分支（牛奶鸡蛋火腿v4）：
        • [牛奶, 鸡蛋, 火腿] (v4)
        • [牛奶, 面粉, 鸡蛋, 培根] (v5)，覆盖它，分配版本号5。此时购物车保留：

    • [鸡蛋，牛奶，火腿] (v4)（未被覆盖）

    • [牛奶，面粉，鸡蛋，培根] (v5) 图 5-13 在同时编辑购物车时捕获两个客户端之间的因果关系。 图 5-14 图 5-13 中的因果依赖关系图。 核心逻辑总结

  • 版本号递增：每次写入递增全局版本号，无论是否冲突。
  • 覆盖规则：只能覆盖直接依赖的旧值，无法覆盖其他并发分支。
  • 客户端合并责任：客户端需主动合并所有已知并发值（包括过期值），服务器不自动合并。

  • 合并并发写入的值:

    • 与多主冲突解决类似。
    • LWW 是简单但有损的方法。
    • 应用层逻辑：如购物车例子中的 集合求并集。
    • 处理删除：需要 墓碑 (Tombstone) 标记，避免删除项在合并时“复活”。
    • 自动合并：CRDTs 可简化应用开发。

  • 版本向量 (Version Vectors):

    • 将单版本号扩展到 多副本、无主 场景。
    • 每个副本维护自己的计数器，形成一个向量（[副本ID -> 版本号]）。版本向量与键关联。
    • 客户端读时获取版本向量，写时 必须 传回。
    • 数据库使用版本向量比较来判断 happens-before 或 concurrency。
    • 优点: 区分覆盖和并发，保证跨副本读写安全，避免数据丢失。
    • 缺点: 客户端仍可能需要合并并发值（兄弟）。
    • 变体: 虚线版本向量 (Dotted Version Vectors) (Riak 2.0 使用)。
    • 注: 版本向量与向量时钟 (Vector Clocks) 概念相似但有细微差别。

本章小结

  • 复制是分布式数据系统的基础，服务于高可用、低延迟、读扩展。
  • 核心挑战是处理变更和并发，以及应对故障。
  • 三种主要方法：单主（简单，无冲突）、多主（容错性好，需冲突解决）、无主（高可用，需冲突解决，一致性弱）。
  • 同步 vs. 异步复制是关键权衡，影响一致性和可用性。
  • 复制延迟会导致问题（读己之写、单调读、一致前缀读），需要理解和应对。
  • 多主和无主复制需要冲突解决机制（LWW 有损，合并/CRDTs/版本向量更优）。
  • 理解 Happens-Before 和并发是处理冲突的基础。
  • 没有完美的复制方法，需要根据应用需求权衡。