第 6 章 复制

一件可能出错的事情，与一件绝不可能出错的事情，二者之间最大的区别在于：当那件绝不可能出错的事情真的出错时，你往往再也无从接近、无从修复。

—— Douglas Adams，《大致无害》（1992）

复制指的是把同一份数据保存在多台通过网络相连的机器上。正如第 19 页"分布式系统与单节点系统"所讨论的，复制数据的理由主要有几种：

• 让数据在地理上更贴近用户（从而降低访问延迟）；
• 让系统在部分组件失效时仍能继续工作（从而提高可用性与持久性）；
• 横向扩展处理读取查询的机器数量（从而提升读吞吐）。

本章假定数据集足够小，每台机器都能保存一份完整副本。第 7 章会放宽这一假设，讨论数据集过大、单机装不下时所采用的分片（partitioning）。后续章节还会探讨复制式数据系统可能出现的各种故障及其应对之道。

如果所复制的数据从不变化，复制就很简单：把数据复制到每个节点一次即可。复制真正棘手的地方在于如何处理被复制数据的变更，这也是本章的主题。我们会介绍三类用于在节点之间复制变更的算法：单主（single-leader）、多主（multi-leader）和无主（leaderless）复制。几乎所有的分布式数据库都采用其中一种，每种各有利弊，下面逐一展开。

复制涉及不少取舍——例如该用同步还是异步、失效副本如何处理等等。这些通常是数据库的配置选项，细节因数据库而异，但大多数实现的总体原则是相通的。本章将讨论这些选择带来的后果。

数据库复制是个老话题。自 1970 年代起就有人研究 [1]，由于网络的根本约束没变，原理也几乎没变。尽管如此，"最终一致性"（eventual consistency）这类概念至今仍常常让人摸不着头脑。第 209 页"复制延迟带来的问题"一节会更准确地讨论最终一致性，并谈到"读己之写"（read-your-writes）、"单调读"（monotonic reads）等保证。

备份与复制

你也许会问：有了复制，还需要备份吗？答案是肯定的，因为两者的用途不同——副本会很快把一个节点上的写入反映到其他节点，而备份保存的是数据的旧快照，让你能"回到过去"。要是不小心删了数据，复制救不了你，因为删除操作同样会传播到所有副本；要恢复被删数据，只能靠备份。

实际上，复制和备份往往是互补的。备份有时本身就是搭建复制的一环，第 201 页"建立新的从节点"会看到这一点；反过来，对复制日志做归档也可以成为备份过程的一部分。

有些数据库会在内部维护过去状态的不可变快照，作为一种内部备份。但这样一来，旧版本数据与当前状态就保存在同一存储介质上。一旦数据量很大，把旧数据备份放到针对低频访问优化的对象存储里、主存储只保留当前状态，反而更便宜。

单主复制

每个保存数据库副本的节点都叫做副本（replica）。只要存在多个副本，就避不开一个问题：如何让所有数据最终都出现在所有副本上？

每一次写入数据库的操作都必须由每个副本处理，否则副本之间的数据就会不一致。最常见的方案叫做基于主节点的（leader-based）、主备（primary-backup）或主动/被动（active/passive）复制，工作方式如下（见图 6-1）：

1. 其中一个副本被指定为主节点（leader，也叫 primary 或 source [2]）。客户端要写入数据库时，必须把请求发给主节点，主节点先把新数据写入本地存储。
2. 其他副本叫做从节点（follower，也叫 read replica、secondary 或 hot standby）。每当主节点把新数据写入本地存储，它也会把这条数据变更作为复制日志（replication log）或变更流（change stream）的一部分发给所有从节点。每个从节点从主节点取到日志后，按主节点处理写入的相同顺序，依次把这些写入应用到本地副本上。
3. 客户端要读取数据时，可以查询主节点，也可以查询任意从节点。但写入只能由主节点接受（在客户端看来，从节点只读）。

图 6-1. 单主复制将所有写入定向到指定的主节点，主节点再向各从节点副本发送变更流。 数据库一旦分片（见第 7 章），每个分片都有自己的主节点。不同分片的主节点可分散在不同节点上，但每个分片有且仅有一个主节点。第 215 页"多主复制"一节会讨论另一种模型：同一分片可同时拥有多个主节点。

单主复制的应用极广。它是许多关系型数据库的内置特性，例如 PostgreSQL、MySQL、Oracle Data Guard [3] 与 SQL Server 的 Always On 可用性组 [4]；一些文档数据库（如 MongoDB、DynamoDB [5]）、消息代理（如 Kafka）、复制块设备（如 DRBD）以及部分网络文件系统也采用了它。许多共识算法——如 CockroachDB [6]、TiDB [7]、etcd 和 RabbitMQ 仲裁队列所采用的 Raft——同样基于单主，且能在原主节点失效时自动选出新主（共识详见第 10 章）。

在较老的文档里，你可能会见到 master–slave replication（主-奴复制）这个说法。它与基于主节点的复制是同一个意思，但因被普遍认为带有冒犯性，应当避免 [8]。

同步复制与异步复制

复制系统中有个重要细节：复制是同步还是异步进行（关系型数据库通常可配置，其他系统则常常硬编码为其中一种）。

设想图 6-1 的场景：某网站的用户更新了自己的头像。某一时刻，客户端把更新请求发给主节点；不久之后，主节点收到请求，把数据变更转发给各从节点，并通知客户端更新成功。图 6-2 给出了一种可能的时序。

图 6-2. 基于主节点的复制——一个同步从节点和一个异步从节点。 例子中，到从节点 1 的复制是同步的：主节点要等从节点 1 确认收到该写入后，才会向用户报告写入成功，并让其对其他客户端可见。到从节点 2 的复制则是异步（或非阻塞）的：主节点把消息发出后并不等待从节点的响应。

图中可见，从节点 2 处理消息前有明显延迟。一般来说复制相当快，大多数数据库系统都能在一秒内把变更应用到从节点。但并不总能保证。在某些情形下，从节点可能落后主节点几分钟甚至更久——例如从节点正在从故障中恢复、系统接近容量上限运行，或节点之间出现网络问题。

同步复制的好处是：从节点必然拥有与主节点完全一致的最新副本。一旦主节点突然失效，我们可以确信数据仍能在从节点上找到。坏处是：一旦同步从节点没有响应（也许是崩溃、网络故障，或其他原因），写入就无法处理。主节点必须阻塞所有写入，直到该同步副本恢复可用。

正因如此，让所有从节点都同步复制并不现实：任何一个节点宕机都会让整个系统停摆。实践中，数据库声称提供"同步复制"时，往往意味着只有一个从节点是同步的，其余皆为异步。一旦那个同步从节点变慢或不可用，就把另一个异步从节点改成同步。这样至少有两个节点拥有最新数据：主节点和一个同步从节点。这种配置有时也叫半同步（semisynchronous）。

在某些系统里，多数派副本（例如五个中的三个，含主节点）采用同步更新，少数派则异步更新。这是法定人数（quorum）的一种形式，第 231 页"用 quorum 进行读写"还会再讨论。多数派 quorum 常见于最终一致性系统，或那些用共识协议自动选主的系统。第 10 章会再回到这些系统。

主从复制有时也会配置为完全异步。这种情况下，主节点失效又无法恢复，所有尚未复制到从节点的写入就都会丢失。也就是说，即便已向客户端确认写入成功，数据也未必真的持久。完全异步的好处是：即便所有从节点都落后了，主节点仍能继续处理写入。

削弱持久性听上去是个糟糕的取舍，但异步复制仍被广泛使用，尤其是从节点数量众多、或跨地理区域分布时 [9]。第 209 页"复制延迟带来的问题"会再回到这个话题。

建立新的从节点

时不时地，你需要新建从节点——也许是为了增加副本数，也许是为了替换失效的节点。怎样才能让新从节点拥有主节点数据的精确副本？

简单地把数据文件从一个节点复制到另一个节点通常不够用：客户端时刻在写入数据库，数据持续变化，普通的文件复制会看到数据库不同部分处于不同时刻的状态，结果可能毫无意义。

你也可以通过锁住数据库（让它无法写入）来让磁盘上的文件保持一致，但这与"高可用"的目标背道而驰。好在新建从节点通常无需停机。大体上的过程如下：

1. 在某个时刻对主节点数据库做一次一致快照——尽量别锁住整个数据库。大多数数据库都具备这项能力，因为备份也要用到。某些场景下还得借助第三方工具，例如 MySQL 的 Percona XtraBackup。
2. 把快照复制到新的从节点上。
3. 从节点连上主节点，请求自快照拍摄之后发生的所有数据变更。这要求快照与主节点复制日志中的某个精确位置一一对应。这个位置在不同系统里叫法不同——PostgreSQL 叫日志序列号（log sequence number），MySQL 则有 binlog 坐标和全局事务标识符（GTID）两套机制。
4. 从节点把自快照以来积压的所有数据变更处理完之后，就算"赶上"了主节点，此后即可像普通从节点一样持续接收主节点的数据变更。

新建从节点的具体步骤因数据库而异。某些系统里它是全自动的；另一些系统里则是一套需要管理员手动执行、相当晦涩的多步流程。

你也可以把复制日志连同对整个数据库的周期快照一并归档到对象存储中。这既是数据库备份与灾难恢复的好做法，新建从节点时也能直接从对象存储下载这些文件来完成上述第 1、2 步。例如 WAL-G 就为 PostgreSQL、MySQL 和 SQL Server 实现了这一点，Litestream 也为 SQLite 提供了类似能力。

由对象存储支持的数据库

对象存储能做的远不止归档数据。许多数据库正开始使用 Amazon S3、Google Cloud Storage、Azure Blob Storage 等对象存储为线上查询提供数据。把数据库数据存放在对象存储中有许多好处：

• 相比其他云存储选项，对象存储便宜得多。这让云数据库可以把访问较少的数据放在更便宜、延迟更高的存储上，同时让工作集（working set）由内存、SSD 和 NVMe 提供。
• 对象存储提供多可用区、双区域或多区域的复制，并具有极高的持久性保证。这也让数据库可以绕过跨可用区的网络流量费用。
• 数据库可以利用对象存储的条件写入（conditional write）特性——本质上就是一次比较并设置（compare-and-set，CAS）操作——来实现事务和主节点选举 [10, 11]。
• 把多个数据库的数据存放在同一对象存储中可简化数据集成（见第 135 页"云数据仓库"），尤其当使用 Parquet、Iceberg 等开放格式时。

把事务、主节点选举和复制的职责都转移给对象存储后，数据库架构因此大幅简化。

不过，采用对象存储做复制的系统也必须直面一些取舍。最显著的是：对象存储的读写延迟远高于本地磁盘或 Amazon EBS 等虚拟块设备；许多云厂商还按 API 调用次数收费，迫使系统把读写批量化以降低成本，而批量化又会进一步增大延迟。对象通常是不可变的，要在大对象内做随机写入会非常耗资源。最后，许多对象存储不提供标准的文件系统接口，没有对象存储集成的系统就无从利用它。FUSE（filesystem in userspace）这类接口允许把对象存储桶挂载为文件系统，让应用无须知道数据其实存在对象存储中也能使用它。但许多对象存储的 FUSE 接口缺少 POSIX 特性（例如非顺序写入或符号链接），而某些系统恰恰依赖这些特性。

不同系统应对这些权衡的方式各异。一些引入了分层存储（tiered storage）架构：访问较少的数据放在对象存储上，新数据或频繁访问的数据则放在 SSD、NVMe 这类更快的存储设备上甚至内存中。还有一些系统把对象存储作为主要存储层，但用 Amazon EBS 或 Neon 的 Safekeepers [12] 这类低延迟存储来保存 WAL。最近一些系统更进一步，采用零盘架构（zero-disk architecture，ZDA）：所有数据都持久化到对象存储中，磁盘和内存仅用作缓存。这让节点可以没有持久状态，运维大为简化。WarpStream、Confluent Freight、Buf's Bufstream 和 Redpanda Serverless 都是基于零盘架构构建的 Kafka 兼容系统。几乎所有现代云数据仓库都采用了这种架构，Turbopuffer（一种向量搜索引擎）和 SlateDB（一种云原生 LSM 存储引擎）也是如此。

处理节点宕机

系统里任何节点都有可能宕机：可能因故障意外停机，也可能因计划维护（例如重启机器以安装内核安全补丁）而停机。能在不停机的前提下重启单个节点，是运维上的一大优势。因此我们的目标是让系统在个别节点失效时整体仍能继续运转，把单点宕机的影响降到最低。

那么，基于主节点的复制如何实现高可用？

从节点失效：追赶式恢复

每个从节点都会在本地磁盘上保留一份它从主节点收到的数据变更日志。从节点崩溃后重启，或主从之间一度网络中断，都很容易恢复：从本地日志中就能知道故障发生前最后处理的事务是哪一个，然后连接主节点请求中断期间发生的全部数据变更，应用完后就"追上了"主节点，可像往常一样继续接收数据变更流。

从节点恢复在概念上很简单，但在性能上可能并不轻松。如果数据库写入吞吐很高，或者从节点离线时间较长，需要追赶的写入会非常多。追赶过程中，正在恢复的从节点与主节点（要给从节点补发积压的写入）都会承受很高的负载。

主节点可以在所有从节点都确认处理完某条日志后再删除它，但如果某个从节点长时间不可用，主节点就得做出取舍：要么保留日志直到那个从节点恢复并赶上（代价是主节点磁盘可能耗尽），要么删掉该从节点尚未确认的部分（这样它就无法靠日志恢复，必须在重新上线时从备份恢复）。

主节点失效：故障转移

处理主节点失效要棘手得多：必须把某个从节点提升为新主，让客户端重新把写入发往新主，其他从节点也得开始消费来自新主的数据变更。这个过程叫做故障转移（failover）。

故障转移既可以人工触发（管理员收到主节点失效的通知，再按必要步骤选出新主），也可以自动进行。自动故障转移通常包含以下几步：

1. **判定主节点已失效。**原因有很多：崩溃、断电、网络问题等等。判断究竟出了什么事并没有万无一失的办法，所以大多数系统干脆用超时：节点之间频繁互发消息，若某节点在一段时间内（例如 30 秒）没回应，就认定它已"死亡"。（若是因计划维护而主动下线主节点，则另当别论，因为主节点可以在关闭前主动把领导权安全交接出去。）
2. 选出新的主节点。可以通过选举（由剩余副本的多数派选出新主），也可以由事先指定的控制器节点（controller node）任命 [13]。最佳候选人通常是从旧主同步到的数据最新的那个副本（这样能尽量减少数据丢失）。让所有节点就新主达成一致是一个共识问题，详见第 10 章。
3. **重新配置系统以使用新主节点。**客户端从此要把写请求发给新主（详见第 265 页"请求路由"）。如果旧主重新上线，它可能仍以为自己是主节点，没察觉其他副本已经把它"罢免"。系统必须确保旧主乖乖回到从节点的角色，并承认新主的地位。

故障转移过程中可能出岔子的地方有很多：

• 如果用的是异步复制，新主节点可能还没收到旧主失效前的全部写入。一旦原主在新主当选后又重新加入集群，那些"丢失"的写入该如何处置？新主在此期间可能已经接到了相互冲突的写入。最常见的做法是：直接丢弃旧主没复制出去的那部分——也就是说，你以为已经提交的写入其实并不持久。
• 当数据库内容需要与其他外部存储系统协调时，丢弃写入尤其危险。例如 GitHub 一次事故中 [14]，一个落后的 MySQL 从节点被提升为新主。该数据库用自增计数器为新行分配主键，但新主的计数器落后于旧主，于是把旧主已分配过的一些主键又分配了一遍。这些主键还被用在 Redis 中，结果 MySQL 与 Redis 之间出现不一致，让一些用户的私密数据泄露给了错的人。
• 在某些故障场景下（见第 9 章），两个节点都会以为自己是主节点。这种情况叫脑裂（split brain），非常危险：如果两个主节点都接受写入又没有解决冲突的机制（见第 215 页"多主复制"），数据很可能丢失或损坏。一些系统作为兜底，一旦检测到两个主节点就关掉其中一个 [15]；但这个机制若设计不当，可能把两个节点都关掉。而等到脑裂被发现、旧节点被关掉时，损坏可能已经发生。
• 在宣布主节点死亡之前，超时该设多长也是个难题。超时越长，主节点失效后的恢复就越慢；超时太短又会引发不必要的故障转移。例如瞬时负载尖峰会让节点响应时间超过超时，瞬时网络抖动会让数据包姗姗来迟；若系统本就处于高负载或网络异常状态，不必要的故障转移更可能让情况雪上加霜，而非缓解。

通过限制或关停旧主节点来防止脑裂的做法叫做 fencing（围栏机制），第 373 页"分布式锁与租约"会进一步讨论。然而这些问题没有简单的答案。正因如此，一些运维团队即便软件支持自动故障转移，也宁愿手动执行。

故障转移最关键的一件事，是挑一个数据最新的从节点来做新主。如果用的是同步或半同步复制，那就挑旧主在确认写入前曾等过响应的那个从节点；如果用的是异步复制，就挑日志序列号最大的从节点。这样可以把故障转移期间丢失的数据降到最低：丢一点不到一秒的写入或许还能接受，挑了一个落后好几天的从节点，后果可能是灾难性的。

这些问题——节点故障、网络不可靠，以及围绕副本一致性、持久性、可用性、延迟的种种取舍——其实正是分布式系统的根本难题。第 9、10 章会更深入地讨论它们。

复制日志的实现

基于主节点的复制在底层究竟是怎么实现的？实践中有几种常用做法，下面逐一简介。

基于语句的复制

最简单的做法是：主节点记录每一条它执行的写请求（语句，statement），把语句日志发给从节点。对关系型数据库而言，这意味着每条 INSERT、UPDATE 或 DELETE 都会被转发给从节点，每个从节点解析并执行该 SQL 语句，就好像它直接收到了来自客户端的请求。

这一思路听起来合理，但在多种情形下会失灵：

• 任何调用了不确定函数的语句——例如用 NOW 取当前时间、用 RAND 取随机数——都很可能在每个副本上得到不同的值。
• 如果语句使用了自增列，或依赖数据库中已有的数据（例如 UPDATE ... WHERE <某些条件>），就必须在每个副本上按完全相同的顺序执行，否则结果可能不同。这在并发执行多个事务时是个限制。
• 有副作用的语句（例如触发器、存储过程、用户自定义函数）可能在不同副本上产生不同的副作用，除非这些副作用绝对是确定性的。

当然也有变通办法——例如主节点在记录语句时把任何不确定函数调用替换为一个固定的返回值，让所有从节点得到相同结果。"在固定顺序下执行确定性语句"的思路，与第 101 页"事件溯源与 CQRS"中讨论的事件溯源模型类似，也叫状态机复制（state machine replication），其理论会在第 433 页"使用共享日志"中介绍。

MySQL 在 5.1 之前用的是基于语句的复制。今天它偶尔仍会用到，因为日志相当紧凑；但默认情况下，只要语句中有任何不确定性，MySQL 就会改用基于行的复制（稍后讨论）。VoltDB 也用基于语句的复制，并通过强制事务必须是确定性的来保障安全 [16]。然而实践中确定性很难保证，所以许多数据库更偏好其他复制方法。

预写日志（WAL）传送

第 4 章已经看到，B 树存储引擎要稳健就离不开预写日志：所有修改都先写入 WAL，以便崩溃后把树恢复到一致状态。既然 WAL 已经包含了把索引和堆恢复到一致状态所需的全部信息，那就可以拿同一份日志去另一个节点上构建副本：主节点除了把日志写入磁盘，还通过网络发给从节点。从节点处理这份日志后，就能构造出与主节点完全相同的文件。

PostgreSQL、Oracle 等系统采用的就是这种复制方法 [17, 18]。它的主要缺点是：日志描述的数据非常底层——WAL 会详细记录哪些字节在哪些磁盘块上发生了变化。这让复制与存储引擎紧密耦合。一旦数据库的存储格式从一个版本变到另一个版本，通常就没法让主从节点跑不同版本的数据库软件。

这看似只是个小细节，运维上的影响却很大。如果复制协议允许从节点跑比主节点更新的软件版本，就可以零停机升级数据库：先升级所有从节点，然后做一次故障转移，让一个已升级的节点成为新主。如果复制协议不允许这种版本不一致——WAL 传送通常如此——升级就只能停机进行。

逻辑（基于行的）日志复制

另一种做法是为复制与存储引擎使用不同的日志格式，让复制日志与存储引擎内部彻底解耦。这种复制日志叫做逻辑日志（logical log），以区别于存储引擎那种（物理）数据表示。

关系型数据库的逻辑日志通常是一组以行为粒度描述写入的记录：

• 对插入的行，日志会记录所有列的新值。
• 对删除的行，日志要包含足以唯一标识被删行的信息。通常是主键，若表上没主键，就得记录所有列的旧值。
• 对更新的行，日志要包含足以唯一标识被更新行的信息，再加上所有列的新值（或至少所有发生变化的列的新值）。

一个修改多行的事务会生成多条这样的日志记录，并以一条"事务已提交"的记录收尾。MySQL 配置为基于行的复制时，会在 WAL 之外另存一份独立的逻辑复制日志，叫 binlog。PostgreSQL 则通过把物理 WAL 解码成行级插入/更新/删除事件来实现逻辑复制 [19]。

由于逻辑日志已经与存储引擎内部解耦，它更容易保持向后兼容，让主从节点跑不同版本的数据库软件，进而让零停机升级到新版本变得可行 [20]。

逻辑日志格式对外部应用也更友好。如果你想把数据库内容送到外部系统——例如用于离线分析的数据仓库，或用于构建定制索引和缓存的专用系统——这一点尤其有用 [21]。这种技术叫做变更数据捕获（change data capture），第 12 章会再讨论。

复制延迟带来的问题

容忍节点故障只是采用复制的理由之一。正如第 19 页"分布式系统与单节点系统"所述，其他理由还包括可扩展性（处理超过单机能力的请求量）和延迟（让副本在地理上更贴近用户）。

主从复制要求所有写入都经由唯一的主节点，但只读查询可以发往任何副本。对以读为主、写得很少的负载（在线服务常常如此），有一种很有吸引力的方案：搭起一批从节点，把读请求分散到这些从节点上。这能减轻主节点的压力，让就近的副本去处理读请求。

在这种读扩展（read-scaling）架构里，只要增加从节点就能扩展只读请求的处理能力。然而这种做法其实只有异步复制才行得通——若试图同步复制到所有从节点，单个节点故障或网络中断都会让整个系统无法写入。从节点越多，至少一个不可用的概率就越大，因此完全同步的配置非常不可靠。

不巧的是，从异步从节点读取的应用在从节点落后时可能看到过时信息。这会让数据库表现出明显的不一致：在主节点和从节点上跑同一个查询，结果可能不同，因为并非所有写入都已反映到从节点。这种不一致只是暂时的——只要停止写入并稍等片刻，从节点最终会赶上主节点。也正因为如此，这种现象叫做最终一致性（eventual consistency）[22]。

"最终一致性"一词由 Douglas Terry 等人提出 [23]，由 Werner Vogels 推广 [24]，后来成了许多 NoSQL 项目的口号。但最终一致并非 NoSQL 数据库的专利；异步复制的关系型数据库的从节点同样有这一特性。

"最终"二字刻意含糊；一般来说，副本能落后到多远并无理论上限。正常运行下，"主节点写入"到"从节点反映出该写入"之间的延迟——也就是复制延迟（replication lag）——可能不到一秒，实践中察觉不到。但只要系统接近容量上限，或网络出现问题，延迟就会轻松涨到几秒甚至几分钟。

延迟一大，由此带来的不一致就不再只是纸上谈兵，而是应用必须面对的真实问题。本节会列举三种因复制延迟而常见的问题，并大致谈谈相应的解决思路。

读己之写

很多应用允许用户先提交一些数据，再去查看自己刚刚提交的内容。可能是客户数据库里的一条记录、讨论串里的一条评论，或者类似的东西。新数据提交时必须发往主节点，但用户查看时可以从从节点读取。这种模式对"读得多、写得少"的数据特别合适。

但在异步复制下问题就来了，如图 6-3 所示：用户刚写完没多久就去看自己写下的内容，新数据可能还没到达副本。在用户看来，自己提交的数据"丢了"，难免恼火。

图 6-3. 用户写入后从过期副本读取，可能出现不一致。 这种情况下，我们需要读后写一致性（read-after-write consistency），也叫读己之写一致性（read-your-writes consistency）[23]。它给出的保证是：用户重新加载页面时，总能看到自己提交过的更新。它对其他用户不做承诺：别人的更新可能要等一会儿才能看到。但它至少让用户放心，自己的输入已经正确保存了。

在主从复制系统里怎么实现读后写一致性？办法有不少，下面举几个例子：

• 读取可能被用户自己改过的内容时，就从主节点或同步更新的从节点读；否则就从异步从节点读。这要求你能在不查询的情况下判断"某条数据是否可能被某位用户改过"。例如社交网站上的用户个人资料通常只能由本人编辑，于是一条简单规则就是：用户自己的资料始终从主节点读，他人的资料从从节点读。
• 一旦应用中大多数内容都可能被用户改动，这种方法就行不通了——大部分数据都得走主节点读，读扩展的好处也被抵消殆尽。这时可以换个判据来决定是否走主节点。例如记录最后一次更新的时间，在更新后的一分钟内让所有读取都走主节点 [25]；也可以监控从节点的复制延迟，对落后超过一分钟的从节点禁用查询。
• 客户端可以记住自己最近一次写入的时间戳，系统则保证为该用户读取的副本至少已反映出这个时间戳所对应的更新。若所选副本还不够新，要么换一个副本来处理本次读取，要么等该副本追上再读 [26]。这里的时间戳可以是逻辑时间戳（例如日志序列号），也可以是真实的系统时钟（此时时钟同步就至关重要；见第 358 页"不可靠时钟"）。
• 如果副本分布在多个区域（出于就近接入、可用性或持久性的考虑），就还会引入额外的复杂度。任何需要主节点服务的请求都必须路由到主节点所在的区域。

同一个用户从多台设备（比如桌面浏览器加移动 App）访问服务时，问题又复杂一层。这时你可能要提供跨设备的读后写一致性：用户在一台设备上输入信息，再到另一台设备上查看，应当能看到刚才输入的内容。

这里还有一些额外难题：

• 依赖"记录用户最后一次更新时间戳"的方法变得更难，因为一台设备上跑的代码并不知道另一台设备发生过什么。这类元数据得集中管理。
• 如果副本分布在多个区域，没法保证不同设备的连接都被路由到同一个区域（例如桌面电脑用家庭宽带、手机走蜂窝数据，路由完全可能不一样）。如果你的方案要求从主节点读，可能得先让同一用户在所有设备上的请求都被路由到同一区域。

区域与可用区

我们用区域（region）来指位于同一地理位置的一个或多个数据中心。云厂商在同一地理区域内会布置多个数据中心，每个数据中心称为一个可用区（availability zone，简称 zone）。因此一个云区域由多个可用区构成，每个可用区都是一座独立的物理设施，拥有自己的电源和制冷，是一个独立的数据中心。

同区域内的可用区之间用高速网络相连，延迟低到足以让多数分布式系统跨多个可用区运行，体验上和在单个可用区里没多大差别。多可用区配置可以让分布式系统在某个可用区下线时仍能存活，但抵御不了整个区域故障——也就是区域内所有可用区都不可用的情形。要扛得住区域级故障，分布式系统必须跨区域部署，代价是更高的延迟、更低的吞吐量和更贵的云网络费用。第 218 页"多主复制拓扑"会进一步讨论这些取舍。眼下只需记住：这里所说的"区域"，指的是位于同一地理位置的一组可用区/数据中心。

单调读

从异步从节点读取时，第二种可能出现的异常是：用户会看到时间倒流。

如果用户对不同副本各做了一次读取，就可能出现这种情况。例如图 6-4 中，用户 2345 两次发起同一查询：第一次发到延迟很小的从节点，第二次发到延迟更大的从节点（用户一刷新网页，每次请求被随机路由到不同服务器时就很容易这样）。第一次查询返回了用户 1234 最近添加的一条评论，第二次查询却什么都没返回，因为延迟更大的从节点还没收到这条写入。结果就是：第二次查询观察到的系统状态比第一次更"早"。如果第一次查询本来就什么也没返回，那还不算太糟，因为用户 2345 多半也不知道用户 1234 刚加过评论；但要是用户 2345 先看到了评论，刷新一下又不见了，那就非常令人困惑。

单调读（monotonic reads）[22] 提供的就是这样一种保证：上述异常不会发生。它比强一致性弱，比最终一致性强。读取数据时你仍可能读到旧值；单调读真正承诺的是：同一用户连续多次读取时，不会"看到时间倒流"——也就是说，已经读到较新数据之后，就不会再读到更旧的数据。

实现单调读的一种办法是让每个用户的读取始终来自同一副本（不同用户可以读不同副本）。例如可按用户 ID 的哈希值选副本，而不是随机挑。一旦该副本失效，该用户的查询就要重新路由到另一个副本。

图 6-4. 用户先从较新副本读取，再从过期副本读取，看起来时间倒流。

一致前缀读

复制延迟异常的第三个例子涉及因果关系的违反。设想 Poons 先生与 Cake 太太之间这段简短对话：

Poons 先生：Cake 太太，你能看到多远的未来？

Cake 太太：通常约 10 秒，Poons 先生。

这两句话之间存在因果依赖：Cake 太太听到了 Poons 先生的提问，并作出了回答。

现在设想第三个人通过从节点听到这段对话。Cake 太太的话经由一个延迟很小的从节点传到他那里，Poons 先生的话却经过一个延迟更大的从节点（见图 6-5）。这个观察者听到的就成了：

Cake 太太：通常约 10 秒，Poons 先生。

Poons 先生：Cake 太太，你能看到多远的未来？

在他看来，仿佛 Cake 太太还没等 Poons 先生问出口就已答上。这种"通灵"能力固然令人惊叹，但确实让人困惑 [27]。

图 6-5. 如果某些分片复制慢于其他分片，观察者可能在看到问题之前就看到答案。 防止此类异常需要另一种保证：一致前缀读（consistent prefix reads）[22]。它说的是：若一组写入按某种顺序发生，那么读到这些写入的人也应按相同顺序看到它们。

这是分片（分区）数据库特有的问题，第 7 章会讨论。如果数据库始终按相同顺序应用写入，读取时永远看到一致的前缀，这种异常就不会出现。然而在许多分布式数据库里，不同分片各自独立运转，并不存在写入的全局顺序。用户读取数据库时，可能看到一部分数据处于较旧状态，另一部分数据处于较新状态。

一种解法是把任何有因果关系的写入都放到同一个分片——但在某些应用里这无法高效实现。还有一些算法会显式跟踪因果依赖，这一话题在第 238 页"happens-before 关系与并发"会再讨论。

复制延迟的解决方案

用最终一致性系统时，值得想一想：如果复制延迟涨到几分钟甚至几小时，应用会变成什么样？如果答案是"没问题"，那挺好；但如果结果是糟糕的用户体验，就得在系统层面提供更强的保证（例如读后写一致性）。明明是异步复制却假装同步，相当于在给后续问题埋雷。

如前所述，应用代码可以提供比底层数据库更强的保证——例如让特定类型的读取走主节点或同步更新的从节点。然而在应用代码层面处理这些问题既复杂又容易出错。

对应用开发者来说，最省心的编程模型是选用一种既能为副本提供强一致性保证（例如线性一致性，见第 10 章）、又支持 ACID 事务（见第 8 章）的数据库。这样你基本可以忽略复制带来的麻烦，把数据库当作单节点来用。2010 年代初，NoSQL 运动一度主张这些特性会限制可扩展性，大规模系统不得不接受最终一致性。

不过自那以后，许多数据库一边提供分布式数据库的容错、高可用、可扩展优势，一边也提供强一致性和事务支持。正如第 67 页"关系型 vs. 文档模型"中所提到的，这一趋势被称为 NewSQL，与 NoSQL 相对（不过它的核心其实更多是新的可扩展事务管理思路，并不严格围绕 SQL）。

虽然现在已经可以选用既可扩展又强一致的分布式数据库，但仍有充分理由让某些应用选用一致性较弱的复制方式。它们在网络中断面前往往更具韧性，开销也比基于事务的系统更低。本章其余部分会继续探讨这些方法。

多主复制

到目前为止，本章只讨论过用单一主节点的复制架构。这是常见做法，但并非唯一选择。

单主复制有一大缺点：所有写入都必须经由这唯一的主节点。一旦因任何原因（比如你与主节点之间的网络中断）连不上主节点，就没法向数据库写入。

对单主复制模型的一种自然扩展是：允许多个节点都接受写入。复制仍按同样的方式进行——每个处理写入的节点都得把该数据变更转发给所有其他节点。这种设置叫做多主（multi-leader）配置（也叫主动/主动或双向复制）。在这种配置下，每个主节点同时也是其他主节点的从节点。

与单主复制一样，多主复制也可选同步或异步。假设你有两个主节点 A 和 B，向 A 写入。如果 A 到 B 是同步复制，又恰逢两节点之间网络中断，那连接恢复前都没法写 A。这样的同步多主，其实跟单主复制非常接近——例如让 B 当主节点，A 把所有写入转给 B 执行。

因此本节不再深入讨论同步多主复制，而把它视为与单主复制等同。剩下的篇幅聚焦于异步多主复制：任何主节点都可处理写入，哪怕它与其他主节点之间的连接断了。

跨地理区域部署

在单一区域内做多主部署通常意义不大，收益往往抵不过额外的复杂度。但在某些场景下，这种配置确实合理。

假设你的数据库副本分布在多个区域（也许为了能扛住整个区域故障，也许为了贴近用户）。这种配置叫地理分布（geographically distributed），也常简称 geo-distributed 或 geo-replicated。单主复制下，主节点必须位于某一个区域，所有写入都得经过该区域。

图 6-6. 跨多区域的多主复制。 而多主配置下，每个区域都可以有自己的主节点。图 6-6 展示了这种架构的大致样貌：每个区域内部用常规的主从复制（从节点也许位于与主节点不同的可用区）；区域之间则由每个区域的主节点把变更复制给其他区域的主节点。

下面比较一下单主和多主在多区域部署里的表现：

性能

单主配置下，每次写入都要跨越互联网到达主节点所在区域。这会大幅增加写入延迟，可能让"做多区域部署"的初衷大打折扣。多主配置下，每次写入都由本地区域处理，再异步复制到其他区域。跨区域的网络延迟因此对用户透明，感知性能更好。

对区域级故障的容忍

单主配置下，主节点所在区域不可用时，故障转移会把另一区域的某个从节点提升为主节点。多主配置下，每个区域都能独立运转，等失联区域恢复后再追上复制即可。

对网络问题的容忍

即便有专线，跨区域流量通常也比同区域不同可用区之间、或单可用区内部的流量更不可靠。单主配置对跨区域链路上的问题极其敏感：某区域的客户端要向另一区域的主节点写入时，请求必须走这条链路过去、再等响应回来才能完成。

异步复制的多主配置则能更好地容忍网络问题：网络一时中断期间，每个区域的主节点都能独立继续处理写入。

一致性

单主系统能提供强一致性保证，例如可串行化事务（详见第 8 章）。多主系统最大的缺点正是它能达到的一致性要弱得多。例如，你无法保证某个银行账户不会变成负数，或某个用户名是唯一的；不同主节点完全可能各自处理一些单独看都没问题的写入（比如分别从账户里取钱、各自注册同一个用户名），合在一起就违反了约束。

这其实是分布式系统的一个根本局限 [28]。如果你需要强制执行此类约束，最好选单主系统。不过正如下文第 222 页"处理写入冲突"所讨论的，多主系统仍能提供一些有用的一致性属性，对许多无需此类约束的应用已经够用。

多主复制不如单主复制常见，但仍有不少数据库支持，例如 MySQL、Oracle、SQL Server、YugabyteDB。某些情况下它是外接特性，例如 Redis Enterprise、EDB Postgres Distributed 和 pglogical [29]。

由于多主复制在许多数据库里是后来补上的特性，配置上常有一些隐蔽陷阱，与其他数据库特性的交互也容易出人意料。例如自增键、触发器、完整性约束都可能出问题。正因如此，多主复制常被视作"危险地带"，能避则避 [30]。

多主复制拓扑

复制拓扑（replication topology）描述写入在节点之间传播所走的通信路径。只有两个主节点时（如图 6-6），合理的拓扑只有一种：主 1 把所有写入发给主 2，反之亦然。一旦超过两个主节点，可选的拓扑就有不少，图 6-7 给出了几种例子。

图 6-7. 多主复制的三种示例拓扑：(a) 环形拓扑；(b) 星形拓扑；(c) 全互联拓扑。 最一般的是全互联（all-to-all）拓扑，见图 6-7(c)：每个主节点都把自己的写入发给其他所有主节点。也存在一些受限拓扑。例如环形拓扑（图 6-7(a)）中，每个节点从一个节点接收写入，再把这些写入（连同自己的写入）转给另一个节点。星形拓扑（图 6-7(b)）也很常见：由一个指定的根节点把写入转发给所有其他节点。星形拓扑还可以推广为树形。

这里的星形网络拓扑与第 77 页"星型与雪花：分析模式"中讨论的星型模式毫无关系，后者描述的是一种数据模型结构。

在环形和星形拓扑中，写入可能要经过多个节点才能到达所有副本，因此节点必须转发收到的数据变更。为了避免无限的复制循环，每个节点都被赋予一个唯一标识符；复制日志里每条写入都打上它一路经过的所有节点的标识 [31]。某节点一旦收到一条变更、发现其中已含自己的标识，就直接忽略——因为它知道自己已经处理过。

不同拓扑的问题

环形与星形拓扑有一个问题：只要某个节点失效，其他节点之间的复制消息流就会中断、无法互通，直到该节点修复为止。当然可以重新配置拓扑来绕开失效节点，但在大多数部署里这种重配置都要人工完成。连接更密的拓扑（如全互联）容错性更好，消息可以走不同路径，从而避免单点故障。

不过全互联拓扑也有自己的问题。其中之一是不同网络链路速度可能不一致（比如有的链路出现拥塞），结果导致一些复制消息"超车"——见图 6-8。

图 6-8 中，客户端 A 向主 1 上的某张表插入了一行；客户端 B 在主 3 上更新了同一行。但主 2 收到这两条写入的顺序可能恰好反过来：它可能先收到更新（在它看来，这是在更新数据库里并不存在的一行），稍后才收到本应先发生的插入。

图 6-8. 在多主复制下，写入到达某些副本时可能顺序错乱。 这是一个因果关系问题，与第 213 页"一致前缀读"中遇到的情况类似。更新依赖于先发生的插入，所以我们必须保证所有节点都先处理插入再处理更新。仅给每个写入加上时间戳是不够的，因为时钟未必同步得足够好，没法让主 2 正确排序这些事件（见第 9 章）。

要正确排序这些事件，可以借助一种叫做版本向量（version vector）的技术，第 237 页"检测并发写入"会讨论。然而许多多主复制系统在更新排序上并没有用上足够好的技术，因此非常容易碰到图 6-8 这样的问题。要是你正在使用多主复制，了解这些问题、仔细读文档、把数据库彻底测一遍，确认它真能提供你以为的保证——这些功课都值得做。

同步引擎与本地优先软件

如果你的应用需要在与互联网断开时仍能继续工作，多主复制同样合适。例如手机、笔记本等设备上的日历应用：无论设备是否联网，你都需要能查看（读请求）和录入（写请求）日程。离线时做的修改，必须在设备下次联网时与服务器以及你的其他设备同步。

在这种情形下，每台设备上都有一个本地数据库副本充当主节点（接受写请求），各设备上的日历副本之间通过异步多主复制（也就是"同步"）保持一致。复制延迟可能从几个小时到几天不等，取决于何时能联网。

从架构上看，这与跨区域多主复制相当类似，只是更极端：每台设备都自成一个"区域"，设备之间的网络连接又极不可靠。

实时协作、离线优先与本地优先应用

许多现代 Web 应用都提供实时协作功能，例如 Google Docs 与 Sheets（文本与表格）、Figma（图形）以及 Linear（项目管理）。这些应用之所以响应迅捷，是因为用户输入会立刻反映在 UI 上，无需等待网络往返服务器，而协作者也能以极低延迟看到彼此的编辑 [32, 33, 34]。

由此又自然演化出一种多主架构：每个打开了共享文件的浏览器标签页都是一个副本，你对文件做的任何更新都会异步复制到其他打开同一文件的用户设备上。即便应用不允许离线继续编辑，仅"多个用户可以不等服务器响应就编辑"这一点，就已经让整体架构成了多主。

离线编辑和实时协作所需的复制基础设施是相似的。应用要捕捉用户对文件做的任何修改，要么立即发给协作者（在线时），要么先存在本地、稍后再发（离线时）。与此同时，应用还要接收协作者的修改、合并到用户本地副本里，并相应更新 UI 以反映最新版本。多人同时修改文件时，可能还需要冲突解决逻辑来合并这些修改。

承担这一职责的软件库叫做同步引擎（sync engine）。这一概念存在已久，但这个术语近年才走红 [35, 36, 37]。允许用户离线继续编辑文件的应用（往往借助同步引擎实现）称为离线优先（offline-first）[38]。本地优先（local-first）软件 [39] 不仅离线优先，还追求"即使作者关停了所有线上服务，应用照样能继续工作"。要做到这一点，可以让同步引擎搭配开放标准的同步协议，让多家服务商都能支持 [40]。例如 Git 就是一个本地优先的协作系统（虽然不支持实时协作），因为你可以通过 GitHub、GitLab 或其他仓库托管服务来同步。

同步引擎的优劣

如今构建 Web 应用的主流方式是：客户端只保留极少的持久状态，每当要显示新数据或更新数据时就向服务器发请求。相比之下，使用同步引擎时，客户端持有持久状态，与服务器的通信则移到后台进程里。同步引擎这种做法有几大好处：

• 数据放在本地，UI 的响应速度可以远胜那些必须等服务调用取数据的方式。有些应用追求在图形系统的下一帧就把用户输入反映出来，也就是要在 60 Hz 显示器上 16 ms 内完成渲染。
• 让用户离线时也能继续工作很有价值，对网络时断时续的移动设备尤其如此。有了同步引擎，应用就不必再做单独的"离线模式"——离线只不过相当于网络延迟特别大。
• 相比在应用代码里显式调用各种服务，同步引擎简化了前端应用的编程模型。每次服务调用都得做错误处理（参见第 183 页"远程过程调用的问题"）；例如服务器更新数据失败时，UI 必须以某种方式把错误体现出来。同步引擎让应用对本地数据进行读写，这些操作几乎不会失败，从而走向一种更具声明性的编程风格 [41]。
• 要实时显示其他用户的编辑，需要收到这些编辑的通知并据此高效更新 UI。把同步引擎与响应式编程模型结合起来是个不错的实现方式 [42]。

同步引擎只有在"用户可能需要的所有数据都能事先下载、并持久保存在客户端"时才效果最好。这样需要的时候离线也能访问数据；但也意味着用户能访问的数据若极其庞大，同步引擎就不太合适。例如下载一个用户自己创建的所有文件通常没问题（个人产生的数据通常不大），但下载一家电商网站的整个商品目录就不现实。

同步引擎由 1980 年代的 Lotus Notes 首创 [43]（虽然当时不叫这个名字），针对特定应用（例如日历）的同步也由来已久。如今则有许多通用同步引擎可用，一些用专有后端服务（如 Google Firestore、Realm、Ditto），另一些有开源后端、适合用于本地优先软件（如 PouchDB/CouchDB、Automerge、Yjs）。

多人在线游戏也有类似需求：要立刻响应玩家的本地操作，再把异步收到的其他玩家的动作与之协调。在游戏开发的术语里，承担同步引擎之责的东西叫 netcode。netcode 用的技术非常贴合游戏的特殊需求 [44]，难以直接迁移到其他类型的软件，因此本书不再深入。

处理写入冲突

无论是跨地理区域的服务端数据库，还是端侧设备上的本地优先同步引擎，多主复制最大的问题都一样：不同主节点上的并发写入可能产生冲突，必须设法解决。

例如，假设两位用户同时编辑同一个 wiki 页面，如图 6-9 所示。用户 1 把页面标题从 A 改为 B，用户 2 也独立地把标题从 A 改为 C。两位用户的改动都已在各自本地的主节点上提交成功；但当变更异步复制出去时，冲突便会被检测出来。这种情形不会出现在单主数据库中。

图 6-9. 两个主节点同时更新同一记录引发的写入冲突。

图示文字描述： 我们称图 6-9 中的两次写入是并发（concurrent）的，因为发起写入时谁都没"意识到"另一次写入的存在。两次写入是否在物理上同时发生其实并不重要——若是离线状态下做的，它们甚至可能相隔一段时间。真正重要的是：发起一次写入时，另一次写入是否已经生效。 第 237 页"检测并发写入"会讨论数据库如何判断两次写入是否并发。眼下姑且假定冲突可以被检测出来，先思考解决冲突的最佳方式。

冲突避免

应对冲突的一种策略是从根本上避免冲突。如果应用能保证同一条记录的所有写入都发往同一个主节点，那么即便整体上是多主，冲突也不会出现。对于离线状态下也会写入的同步引擎客户端而言，这条路走不通；但对跨区域复制的服务端系统而言，有时是可行的 [30]。

例如，在用户只能编辑自己数据的应用中，可以让同一用户的请求始终路由到同一区域，写入该区域的主节点。不同用户可能对应不同的"主"区域（也许根据用户的地理位置就近选择），但就单个用户而言，整套配置实质上就是单主。

但有时你也会希望切换某条记录指定的主节点——也许某区域不可用、流量需要转移；也许某用户搬了家、现在离另一个区域更近。这就带来一种风险：用户可能在主节点切换的过程中执行了写入，从而引发冲突，最终仍得借助下面的某种办法来解决。所以一旦允许更换主节点，"避免冲突"就不再靠得住。

再看一个避免冲突的例子：假设要给新插入的记录基于自增计数器分配唯一 ID。如果有两个主节点，可以让一个只生成奇数、另一个只生成偶数，这样就不会出现两边把同一个 ID 分给不同记录的情况。第 417 页"ID 生成器与逻辑时钟"会讨论其他 ID 分配方案。

后写胜出（丢弃并发写入）

既然冲突无法避免，最简单的解决办法就是给每次写入打上时间戳，始终采用时间戳最大（最新）的那个值。例如图 6-9 中，假设用户 1 写入的时间戳比用户 2 的更大，那么两个主节点都会判定页面新标题应为 B，并丢弃把标题设为 C 的那次写入。若两次写入恰好时间戳相同，可以拿值本身来比较以选出胜者（例如字符串取字母序在前的那个）。

这种方法叫做后写胜出（last write wins，LWW），即把时间戳最大的写入视为"最后一次"。这个名字其实有点误导：两次写入若是并发的（如图 6-9），谁"更晚"本无定义，并发写入之间的时间戳顺序本质上就是随机的。

所以 LWW 真正的含义是：同一条记录在不同主节点上被并发写入时，系统会随机挑一次写入作为胜者，其余写入则被悄悄丢弃——哪怕它们都已在各自的主节点上成功提交。这样所有副本最终会收敛到一致状态，代价就是数据丢失。

如果你能彻底避免冲突——例如只用唯一键插入新记录、从不更新——那么 LWW 没什么问题。但如果会更新已有记录，或者不同主节点可能用相同键插入记录，就要判断丢失更新对应用是否可以接受；如果不行，就必须改用下面介绍的其他方案。

LWW 还有一个隐患：若以真实时钟（如 Unix 时间戳）作为写入时间戳，系统会对时钟同步极其敏感。假设某节点的时钟跑得比别的节点快，而你想覆盖该节点上的值，你这次写入很可能被忽略——因为它的时间戳反而更小，尽管它显然发生得更晚。这个问题可以用逻辑时钟解决，第 417 页"ID 生成器与逻辑时钟"会讨论。

人工解决冲突

如果"随机丢写"不可接受，下一种选择是让人工来解决冲突。你或许已在 Git 这类版本控制系统中见过这种做法：如果两个分支上的提交改动了同一文件的同一行，合并这两个分支时就会出现合并冲突，必须先解决冲突再完成合并。

在数据库里，让冲突阻塞整个复制过程、等人来处理是不现实的。通常的做法是保存某条记录的所有并发写入值——例如把图 6-9 中的 B 和 C 都留下来，这些值有时叫做兄弟（siblings）。下次查询该记录时，数据库会一次性返回所有这些值，而不仅是最新值。之后你可以任意决定如何解决冲突——既可以在应用代码里自动处理（例如把 B 和 C 拼成 "B/C"），也可以让用户来选。最后再把解决后的新值写回数据库。

CouchDB 等系统就采用了这种冲突解决方式。但它也有几个问题：

• 数据库的 API 变了——wiki 页面的标题原本就是一个字符串，如今变成了一个字符串集合：通常只有一个元素，冲突时则可能包含多个。这让数据在应用代码里变得难以处理。
• 让用户去人工合并兄弟值要费很大力气——应用开发者要搭建冲突解决 UI，用户还得去完成合并（用户可能根本搞不清自己被要求做什么、为什么要做）。许多时候，自动合并比打扰用户更好。
• 自动合并兄弟值若不够仔细，可能产生出人意料的行为。例如 Amazon 的购物车曾允许并发更新，再通过把所有兄弟里出现过的商品取并集来合并（即把购物车并起来）。其后果是：若客户在某个兄弟里删掉了一件商品，而另一个兄弟里仍保留了该商品，已删除的商品就会莫名其妙地重新出现 [45]。图 6-10 中，设备 1 从购物车中删除 Book，设备 2 同时删除 DVD，但合并兄弟之后，两件商品都死灰复燃。
• 如果多个节点同时察觉并解决了同一冲突，解决过程本身又可能引入新的冲突，结果甚至彼此不一致——比如一个节点把 B 与 C 合并为 B/C，另一个节点若排序不细致则合并为 C/B。再去解决 B/C 与 C/B 之间的冲突时，可能得到 B/C/C/B 这种叫人摸不着头脑的结果。

图 6-10. Amazon 购物车异常的例子——若通过取并集来合并冲突，被删除的商品可能重新出现。

自动冲突解决

对许多应用而言，最佳的冲突处理方式是用某种算法把并发写入自动合并到一致状态。自动冲突解决要保证所有副本收敛到同一状态——也就是说，只要处理过相同的写入集合，无论到达顺序如何，所有副本最终都将拥有相同状态。最终一致性加上这种收敛保证，就是所谓的强最终一致性（strong eventual consistency）[46]。

LWW 只是冲突解决算法中一个最简单的例子。针对不同类型的数据，业界已发展出更精细的合并算法，目标是尽可能保留所有更新的预期效果，避免数据丢失：

• 若数据是文本（例如 wiki 页面的标题或正文），可以记录从一个版本到下一版本插入或删除了哪些字符。合并结果会保留任何兄弟中做过的所有插入与删除；用户若在同一位置并发插入文本，可按某种确定性顺序排序，让所有节点得到相同结果。
• 若数据是一组项（像待办列表那样有序，或像购物车那样无序），可仿照文本采取类似做法：记录插入与删除。要避免图 6-10 中的购物车问题，算法会记住 Book 与 DVD 已被删除，因此合并结果是 Cart = {Soap}。
• 若数据是可加可减的整数计数器（例如社交媒体的点赞数），合并算法可以分别统计每个兄弟上发生过多少次加减，再正确相加，结果既不重复计数也不漏掉更新。
• 若数据是键值映射，可对同一键下的值套用上述某种冲突解决算法；不同键之间的更新则相互独立。

自动冲突解决也有它的边界。例如，要保证某列表最多 5 项，但多人并发添加导致总数超过 5，那么唯一的办法就是丢掉一部分新加入项。尽管如此，自动冲突解决依然足以撑起许多有用的应用。要构建协作式的离线优先或本地优先应用，冲突解决在所难免，自动化往往是最佳出路。

无冲突复制数据类型与操作变换

实现自动冲突解决常用的算法有两大类：无冲突复制数据类型（conflict-free replicated data types，CRDT）[46] 和操作变换（operational transformation，OT）[47]。两者在设计思路和性能特性上各有不同，但都能为上述各种数据类型提供自动合并能力。

图 6-11 展示了 OT 与 CRDT 是如何合并对同一段文本的并发更新的。假设有两个副本，初始状态都是文本 ice。一个副本在前面加上 n，得到 nice；与此同时另一个副本在后面加上感叹号，得到 ice!。

图 6-11. 两次并发的字符串插入分别由 OT 和 CRDT 合并的过程。 合并结果 nice! 由这两类算法以不同方式得到：

OT

记录字符插入或删除时所在的索引：n 在索引 0 处插入，! 在索引 3 处插入。两个副本随后交换彼此的操作。"在索引 0 插入 n"可以原样应用，但若把"在索引 3 插入 !"直接套到状态 nice 上，会得到 nic!e，是错的。因此每个操作的索引都要变换一下，以反映已应用过的并发操作。这里把"在索引 3 插入 !"变换为"在索引 4 插入 !"，用来补偿前面插入了 n。

CRDT

大多数 CRDT 给每个字符分配一个唯一且不可变的 ID，并以这些 ID（而非索引）来确定插入或删除的位置。例如图 6-11 中把 ID 1A 赋给字符 i、2A 赋给 c，依此类推。插入感叹号时，操作里会带上新字符的 ID（4B）以及紧挨它前面的那个已有字符的 ID（3A）。要在字符串开头插入字符，就把 nil 视作前一个字符的 ID。同一位置的并发插入则按字符 ID 排序，由此确保各副本无需变换即可收敛。

许多算法都是这些思路的变体。把"字符"换成"列表元素"，列表与数组也可以照样支持；键值映射等其他数据类型也很容易加进来。OT 与 CRDT 各有性能与功能上的权衡，把两者长处糅合到一种算法里同样可行 [48]。

OT 最常用于实时协作文本编辑，例如 Google Docs [32]；CRDT 则可以在 Redis Enterprise、Riak、Azure Cosmos DB [49] 等分布式数据库中见到。JSON 数据的同步引擎既能用 CRDT 实现（如 Automerge、Yjs），也能用 OT 实现（如 ShareDB）。

冲突的种类

有些冲突一目了然。图 6-9 中两次写入并发地把同一记录的同一字段设成不同值，显然是冲突。

另一些冲突则更难察觉。比如有一个会议室预订系统，记录哪一段时间、哪个会议室、由谁预订。这种系统并不通过更新某个字段来登记预订，而是为每次预订插入一条新记录。应用必须保证同一时段同一会议室只能被一组人预订（即同一会议室不能出现时间重叠的预订）。在这种场景下，如果有人同时为同一会议室创建两次预订，就可能产生冲突。即使应用在允许预订前会检查可用性，只要两次预订发生得足够接近、双方都看到会议室空着，冲突仍然会出现。

对此并没有什么现成的速效药，但接下来的章节会一步步带你看清这一问题。第 8 章会讨论更多冲突的例子，第 13 章会探讨如何在复制系统中以可扩展的方式检测和解决冲突。

无主复制

本章迄今讨论的两种复制方式——单主与多主——都建立在同一思路上：客户端把写请求发给某个节点（主节点），由数据库系统负责把该写入复制到其他副本。主节点决定写入按什么顺序处理，从节点再按相同顺序应用这些写入。

也有一些数据存储采取了截然不同的做法：彻底抛弃"主节点"概念，允许任何副本直接接受来自客户端的写入。早期的一些复制式数据系统就是无主的 [1, 50]，但在关系型数据库统治天下的年代，这一思路基本被遗忘。直到 2007 年亚马逊在其内部 Dynamo 系统中重新启用，它才在数据库领域重新流行起来。Riak、Cassandra 和 ScyllaDB 都是受 Dynamo 启发的开源数据存储，因此这类数据库也被称作 Dynamo 风格。

最初那套 Dynamo 系统的架构记录在一篇论文里 [45]，但从未在亚马逊之外公开发布。同名的 DynamoDB 是亚马逊较新的一款云数据库，架构完全不同：它基于 Multi-Paxos 共识算法，采用单主复制 [5, 51]。

某些无主实现里，客户端直接把写入发给多个副本；另一些实现里则由一个协调者节点代替客户端去做这件事。但与基于主节点的数据库不同，这个协调者并不强制写入按某种特定顺序执行。我们会看到，这一设计差异对数据库的使用方式有深远影响。

节点宕机时仍能写入数据库

假设你有一个三副本的数据库，其中一个副本暂时不可用——也许正在为了系统更新而重启。在单主配置下，要继续处理写入可能需要执行故障转移（见第 204 页"处理节点宕机"）。

而在无主配置下根本没有故障转移这回事，因为所有副本都对等，并没有主节点。图 6-12 展示了具体过程。

图 6-12. 写入多数副本，从多数副本读取，并把最新值转发给写入期间不可用的副本。 客户端（用户 1234）并行地把写入发给三个副本，两个可用副本接受了这次写入，那个不可用副本则错过了。假设三个副本中有两个确认就足够算写入成功；用户 1234 收到两个 OK 回复后，就视作写入成功——客户端干脆不去管那个错过这次写入的副本。

现在那个不可用节点又重新上线了，客户端开始从它读取。它在宕机期间错过的所有写入一个也没有。因此从该节点读取时，得到的响应可能是陈旧（stale，过时）的。

为解决这个问题，客户端从数据库读取时不只向一个副本发请求：读请求也并行发往多个节点。客户端可能从不同节点收到不同响应——例如一个节点返回最新值，另一个返回陈旧值。每个值都要标上版本号或时间戳，与第 224 页"后写胜出（丢弃并发写入）"类似。客户端收到读响应后会取版本号最大的那个（即使这个值只由一个副本返回，而其他副本都返回较旧的值）。详见第 237 页"检测并发写入"。

追上错过的写入

复制系统应当保证最终把所有数据复制到每个副本。当不可用节点恢复上线后，它该如何追上错过的写入？Dynamo 风格存储常用以下几种机制：

读修复（Read repair）

客户端从多个节点并行读取时，能发现哪些响应是陈旧的。例如图 6-12 中，用户 2345 从副本 3 拿到版本 6 的值，从副本 1、2 拿到版本 7 的值。客户端察觉副本 3 的值过期了，就把较新的值写回这个副本。这种方法对读取频繁的值效果不错。

提示移交（Hinted handoff）

某个副本不可用时，可由另一个副本以提示（hint）的形式临时替它存写入。等本应接收这些写入的副本恢复后，存有提示的副本会把这些提示发给它，然后删掉提示。这套移交机制能让副本回到最新状态，对那些从未被读到、因而读修复也派不上用场的值同样适用。

反熵（Anti-entropy）

此外，还有一个后台进程会周期性比对副本之间的数据差异，把任何缺失的数据从一个副本复制到另一个。与基于主节点复制中的复制日志不同，这一反熵过程并不按特定顺序复制写入，复制延迟也可能相当明显。

用 quorum 进行读写

在图 6-12 的例子里，即便写入只在三个副本中的两个上完成，我们也算它成功。那么只在一个副本上被接受呢？还能再低吗？

只要每次成功的写入都至少落在三个副本中的两个上，那么至多只有一个副本是过期的。因此只要从至少两个副本读，就能保证其中至少有一个是最新的——哪怕第三个副本宕机或响应迟缓，读取仍能返回最新值。

更一般地：如果共有 n 个副本，每次写入必须得到 w 个节点确认才算成功，每次读取至少要查询 r 个节点。（在我们的例子里 n = 3，w = 2，r = 2。）只要 w + r > n，读取时就有把握拿到最新值——因为 r 个被读节点中至少有一个必然是最新的。遵循这种 r 与 w 取值的读写称为 quorum 读写 [50]。可以把 r 与 w 看作让读或写生效所需的最小投票数。

在 Dynamo 风格数据库中，n、w、r 通常都是可配置的。常见做法是把 n 设为奇数（一般是 3 或 5），并令 w = r = (n + 1) / 2（向上取整）。当然也可以视需要调整。例如读多写少的负载可以把 w 设为 n、r 设为 1，让读取更快——代价是只要一个节点失效，所有写入都会失败。

集群里的节点总数可能多于 n，但任意给定值只存放在 n 个节点上。这让数据集可以分片，从而支撑超过单机容量的规模。第 7 章会再讲分片。

quorum 条件 w + r > n 让系统能容忍若干节点不可用：

• 若 w < n，则即便有节点不可用，写入仍可继续。
• 若 r < n，则即便有节点不可用，读取仍可继续。
• 若 n = 3，w = 2，r = 2，可容忍 1 个节点不可用，如图 6-12。
• 若 n = 5，w = 3，r = 3，可容忍 2 个节点不可用，见图 6-13。

图 6-13. 若 w + r > n，至少有一个被读取的副本一定看到了最新一次成功写入。 通常读写都会并行发往全部 n 个副本。参数 w 与 r 决定要等多少节点——也就是 n 个节点中要有多少个回报成功，读或写才算成功。

如果可用节点少于所需的 w 或 r，写入或读取就会返回错误。节点不可用的原因五花八门：宕机（崩溃、断电）、执行过程中出错（如磁盘满写不下）、客户端到节点的网络中断，等等。我们只关心节点是否回复了成功，无需区分具体的故障种类。

理解 quorum 一致性的局限

假设有 n 个副本，并选了满足 w + r > n 的 w 与 r，一般情况下你都能指望每次读取返回某个键最新写入的值。原因是写入的节点集合与读取的节点集合必然有交集——也就是说，读到的节点里至少有一个拥有最新值（如图 6-13）。

通常会把 r 与 w 都选为多数派（大于 n / 2）：这样既能保证 w + r > n，又能容忍最多 n / 2 个节点失效（向下取整）。但 quorum 并不非得是多数派——关键在于读写所用的节点集合至少存在一个交集。其他 quorum 分配方式同样可行，这给分布式算法的设计留出了灵活空间 [52]。

你也可以把 w 与 r 设得小一些，让 w + r ≤ n（即不满足 quorum 条件）。这种情况下，读写请求依旧发往全部 n 个节点，只是所需的成功响应更少。

w 与 r 越小，越可能读到陈旧值，因为这次读取更可能没把含有最新值的节点纳入进来。但好处是延迟更低——尤其与同步（阻塞）复制相比，优势明显。这种配置在可用性上也更高：哪怕网络中断、多副本不可达，读写仍能继续。只有当可达副本数低于 w 或 r 时，数据库才会变得不可写或不可读。

不过即使 w + r > n，某些边界情形下一致性表现仍可能令人困惑。例如：

• 若某节点带着新值失效，其数据由带旧值的副本恢复，存有新值的副本数可能掉到 w 以下，从而破坏 quorum 条件。
• 在再均衡过程中，数据从一个节点搬到另一个节点（见第 7 章），各节点对"哪些节点应当持有某值的 n 个副本"可能看法不一，导致读写 quorum 不再相交。
• 若读取与写入并发，读取可能看见也可能看不到这次并发写入的结果。具体而言，可能出现一次读看到新值、紧接着另一次读看到旧值的情形，详见第 411 页"实现线性一致系统"。
• 若一次写入在部分副本上成功、在另一部分上失败（例如某些节点磁盘已满），整体上成功的副本数不到 w，那么已成功副本上的写入并不会回滚。也就是说，即便系统报告本次写入失败，后续读取仍可能返回也可能不返回这次写入的值 [53]。
• 若数据库以真实时钟的时间戳来判断哪次写入更新（例如 Cassandra 与 ScyllaDB），那么只要另一个节点的时钟跑得更快、又对同一个键写过，写入就可能被悄悄丢弃——这正是第 224 页"后写胜出（丢弃并发写入）"中见过的问题。第 362 页"依赖同步时钟"会更细致地讨论。
• 若两次写入并发，可能在一个副本上先处理其中一个、在另一个副本上先处理另一个，从而引发冲突，情形与多主复制类似（见第 222 页"处理写入冲突"）。第 237 页"检测并发写入"会再回到这一话题。

由此可见，quorum 看似能保证读取返回最新写入的值，实践中却没那么简单。Dynamo 风格数据库一般针对能容忍最终一致性的场景做了优化。参数 w 与 r 让你调节读到陈旧值的概率 [54]，但最好别把它们当成绝对的保证。

监控陈旧度

从运维角度讲，监控数据库返回的结果是不是最新十分重要。即便应用能容忍陈旧值，你也得心里有数：复制是否健康。一旦明显落后，就应该告警，便于排查原因（如网络问题或节点过载）。

基于主节点的复制通常会暴露复制延迟指标，可以直接接入监控系统。这之所以可行，是因为写入按相同顺序应用到主节点和从节点上，每个节点在复制日志里都有一个位置（即它本地已应用的写入数）。用主节点的当前位置减去从节点的当前位置，就可以衡量复制延迟。

然而在无主复制系统里，写入并没有固定的应用顺序，监控起来就难得多。某副本替别的副本代存的提示数可作为系统健康度的一项指标，但很难有效解读 [55]。最终一致性本就是一种刻意模糊的承诺，但从可运维性看，能把"最终"二字量化是重要的事。

单主与无主复制的性能对比

基于单主的复制系统能提供一些强一致性保证，这些是无主系统难以乃至无法做到的。但正如第 209 页"复制延迟带来的问题"所言，单主复制在从异步更新的从节点读取时，也会返回陈旧值。

从主节点读取能确保响应是最新的，代价却是若干性能问题：

• 读吞吐受限于主节点的处理能力（这与读扩展相对——读扩展把读请求分散到异步更新的副本上，可能读到陈旧值）。
• 主节点失效时，必须等待故障检测和故障转移完成，才能继续处理请求。即便故障转移过程极快，用户也会因为短暂的响应时间上涨有所察觉；如果耗时较长，系统在此期间就不可用。
• 系统对主节点上的性能问题异常敏感。一旦主节点变慢（如过载或资源争用），用户响应时间会立刻受到影响。

无主架构在这些方面更具韧性。它根本没有故障转移这回事，请求本就并行发往多个副本，一个副本变慢或不可用对响应时间影响很小；客户端用最先返回的那批响应即可。这种"用最快响应"的做法叫做请求对冲（request hedging），能显著压低长尾延迟 [56]。

无主系统的韧性在本质上来自它不区分正常态与故障态。这在应对灰故障（gray failure）时尤其有用——节点并未彻底宕机，却处于异常缓慢的退化状态 [57]，或者只是过载（例如节点离线一阵后靠提示移交恢复时，会承受大量额外负载）。基于主节点的系统必须判断这种情况是否糟糕到值得故障转移（而故障转移本身可能再带来更大扰动），无主系统压根不必问这个问题。

不过无主系统也有自己的性能短板：

• 即便不需要故障转移，仍要由某个副本去发现另一个副本不可用，并替它代存错过的写入。等不可用副本恢复后，移交过程还要把提示发过去——这都会在系统已经吃紧的时候给副本压上额外负载 [55]。
• 副本越多，quorum 越大，请求完成前要等的响应也越多。即便只等最快的 r 或 w 个副本回应、并行发起请求，r 或 w 越大，撞上慢副本的概率也越高，整体响应时间会随之上升（见第 41 页"响应时间指标的使用"）。实践中 quorum 很少超过 7 取 4 或 9 取 5。
• 一场大范围的网络中断把客户端与大量副本切断后，可能让 quorum 凑不齐。有些无主数据库提供了开关，允许任何可达副本接受写入，哪怕它并非该键的常规副本（Riak 和 Dynamo 把这叫做草率 quorum（sloppy quorum）[45]，Cassandra 与 ScyllaDB 称之为一致性级别 ANY）。这并不能保证后续读取一定能看到该写入的值，但在某些应用里总比直接写入失败要好。

多主复制在抗网络中断方面甚至比无主复制还要稳健：读写只需与一个主节点通信，而主节点又可以与客户端就近部署。但由于一个主节点的写入要异步传给其他主节点，读取拿到的数据可能任意陈旧。Quorum 读写则提供了折中：容错性不错，又能以高概率读到最新数据。

多区域运行

前面提过，跨区域复制是多主复制的一种典型用例（见第 215 页"多主复制"）。无主复制同样适合跨区域运行，因为它本就是为了容忍并发写入冲突、网络中断和延迟尖峰而设计的。

在 Cassandra 与 ScyllaDB 中，要做跨区域写入的客户端会先在本地区域里选一个节点，称为协调者节点（coordinator node），把写入发给它。协调者节点会把写入转发给本区域的所有副本，并发给其他每个区域里的一个副本，再由该副本把写入转发给其所在区域内的其他副本。这样就避免了多次跨区域请求。

写入的成功与否要等多少响应，可以从若干一致性级别中选择。例如，可以要求所有区域的副本凑成一个 quorum，也可以让每个区域各自凑 quorum，或者只要本地区域里凑齐 quorum。本地 quorum 不必等跨区域的慢响应，但更可能返回陈旧结果。

Riak 则把客户端与数据库节点之间的所有通信都限制在同一个区域内，因此 n 描述的是单个区域内的副本数。区域之间的复制以异步、后台方式进行，风格与多主复制类似。

检测并发写入

与多主复制一样，无主数据库也允许并发写入同一个键，由此产生需要解决的冲突。这些冲突有时在写入时就能被发现，但并非总是如此：它们也可能要到读修复、提示移交或反熵过程里才浮现出来。

问题出在这里：由于网络延迟参差、部分故障频出，事件到达不同节点的顺序可能不同。例如图 6-14 中，两个客户端 A 和 B 同时写入三节点存储里的键 X：

• 节点 1 收到了 A 的写入，但因瞬时故障始终没收到 B 的写入。
• 节点 2 先收到 A 的写入，再收到 B 的写入。
• 节点 3 先收到 B 的写入，再收到 A 的写入。

如果每个节点收到客户端写请求就直接覆盖某键的值，节点之间将长期不一致，如图 6-14 末尾的 get 请求所示：节点 2 认为 X 的最终值是 B，其他节点则认为是 A。

图 6-14. Dynamo 风格存储中的并发写入：没有明确定义的顺序。 要达成最终一致，副本必须收敛到同一个值。可以采用第 222 页"处理写入冲突"中讨论过的任何冲突解决机制——例如 LWW（Cassandra 与 ScyllaDB 采用）、人工解决或 CRDT（Riak 采用）。

LWW 实现起来很简单。每次写入都打上时间戳，时间戳大的值总会覆盖时间戳小的。但仅凭时间戳，无从判断两个值究竟是真的冲突（并发写入），还是先后写入。如果想显式解决冲突，系统就得用更细致的方式去检测并发写入。

happens-before 关系与并发

如何判断两个操作是否并发？先看几个例子，建立直觉：

• 图 6-8 中，两次写入并不并发：A 的插入先发生（happens before）于 B 的自增，因为 B 自增的那个值正是 A 插入的值。换句话说，B 的操作建立在 A 之上，所以必然发生得更晚。我们也说 B 因果依赖于 A。
• 反过来，图 6-14 中的两次写入是并发的：每个客户端发起操作时都不知道另一个客户端正在对同一个键操作，因此两次操作之间不存在因果依赖。

只要操作 B 知道 A、依赖于 A，或在某种意义上建立在 A 之上，我们就说操作 A 先发生于操作 B。一个操作是否先发生于另一个，是定义并发含义的关键。事实上，可以简单地这样说：如果两个操作互不先发生，那它们就是并发的 [58]。

因此，对任意两个操作 A 与 B，只有三种可能：A 先发生于 B、B 先发生于 A，或者 A 与 B 并发。我们需要一种算法来判断两个操作是否并发。如果其中一个先发生于另一个，那后发生者就应覆盖先发生者；若两者并发，则存在一个需要解决的冲突。

并发、时间与相对论

直觉上似乎应该把"同时发生"的两个操作叫做并发——但其实两者是否在时间上真的重叠并不重要。由于分布式系统里的时钟充满坑，要判断两件事是否真正同时发生本身就相当困难，第 9 章会详细讨论。

为定义并发，具体时间并不重要。我们只是把互相都不知晓对方存在的两个操作称为并发，至于物理时刻几何并不在意。人们有时会把这一原则与物理学中的狭义相对论 [58] 联系起来：相对论指出，信息传播速度不能超过光速。因此在空间上相距一定距离发生的两个事件，若间隔时间短于光跨越该距离所需的时间，就不可能彼此影响。

在计算机系统里，即便两个操作原则上完全来得及通过光速通信，它们仍可能是并发的。比如网络此刻缓慢或中断，两个操作即便相隔一段时间发生，也仍然是并发的，因为网络问题让一方无从得知另一方。

捕捉 happens-before 关系

下面看一种算法，它能判定两个操作是否并发，或者其中一个是否先发生于另一个。为简化讨论，先从只有一个副本的数据库说起；理解了单副本的做法，再推广到带多副本的无主数据库。

该算法的工作方式如下：

• 服务器为每个键维护一个版本号，每次写入该键就把版本号加一，并把新的版本号与新值一起保存。
• 客户端读取某个键时，服务器会返回所有兄弟值（即所有未被覆盖的值）以及最新版本号。客户端在写入前必须先读一次。
• 客户端写入某个键时，必须带上上次读取拿到的版本号，并把上次读到的所有值合并起来（例如用 CRDT 合并或借助用户输入）。写请求的响应同样会返回所有兄弟值，让我们可以一步步把多次写入串起来（与第 222 页"处理写入冲突"中购物车的做法相同）。
• 服务器收到带有某个版本号的写入时，可以覆盖所有版本号不大于该版本号的值（它知道这些值已被合并进新值），但必须保留所有版本号更高的值（这些值与本次写入并发）。

注意：服务器仅凭版本号就能判断两个操作是否并发，无需解释值本身，因此值可以是任意数据结构。

写入时附带的版本号告诉我们这次写入基于哪种先前状态。若写入未附版本号，它就与所有其他写入并发，因而不会覆盖任何东西——它将作为后续读取返回的值之一保留下来。图 6-15 展示了该算法的运作。

图 6-15. 捕捉两个客户端并发编辑购物车时的因果依赖。 例子中两个客户端并发地往同一购物车里加东西（如果觉得购物车太琐碎，可以想成两位空管员并发地往各自跟踪的扇区里加飞机）。最初购物车为空。两位客户端期间共向数据库做了五次写入：

1. 客户端 1 把 milk 加入购物车。这是该键的首次写入，服务器成功保存并赋予版本 1，再把这个值连同版本号一起回传给客户端。
2. 客户端 2 把 eggs 加入购物车，并不知道客户端 1 已并发地加了 milk（在它看来，购物车里只有 eggs）。服务器把版本 2 分配给这次写入，并将 eggs 与 milk 作为两个独立值（兄弟）保存下来，然后把这两个值连同版本号 2 一并返回给客户端。
3. 客户端 1 不知道客户端 2 的写入，想往购物车里加 flour，以为最终内容会是 [milk, flour]。它把这个值连同此前服务器给它的版本号 1 一起发回。服务器一看版本号就明白 [milk, flour] 取代了原本的 [milk]，但与 [eggs] 是并发的。于是服务器把版本号 3 分配给 [milk, flour]，覆盖 [milk]，但保留版本 2 的 [eggs]，再把这两个值一起返回客户端。
4. 与此同时，客户端 2 想加 ham，并不知道客户端 1 刚加了 flour。客户端 2 上一步从服务器拿到 [milk] 与 [eggs] 两个值，便合并它们再加上 ham，组成新值 [eggs, milk, ham]，连同先前的版本号 2 一起发回服务器。服务器发现版本 2 覆盖了 [eggs]，但与 [milk, flour] 并发，因此剩下两个值：版本 3 的 [milk, flour] 与版本 4 的 [eggs, milk, ham]。
5. 最后客户端 1 想加 bacon。它在版本 3 时拿到了 [milk, flour] 和 [eggs]，便合并它们再加上 bacon，把最终值 [milk, flour, eggs, bacon] 连同版本号 3 发回服务器。这次写入覆盖了 [milk, flour]（注意 [eggs] 在上一步已被覆盖），但与 [eggs, milk, ham] 并发，因此服务器把这两个并发值都留下来。

图 6-15 中操作之间的数据流在图 6-16 中以图示展示。箭头表示哪个操作先发生于哪个操作——后者知晓或依赖前者。本例中，客户端始终没赶上服务器的最新状态，因为总有另一个并发操作正在进行；但旧版本的值最终都被覆盖，没有写入丢失。

图 6-16. 图 6-15 中因果依赖关系的图示。

版本向量

图 6-15 的例子只用了一个副本。如果有多个副本但没有主节点，算法该如何调整？

图 6-15 用单个版本号来刻画操作间的依赖，但多个副本并发接受写入时，单个版本号就不够用了。我们需要为每个副本和每个键各自维护一个版本号。每个副本处理写入时把自己的版本号加一，并跟踪它从其他副本看到的版本号。这些信息合在一起，就决定了哪些值该覆盖、哪些值该保留为兄弟。

来自所有副本的版本号集合称为版本向量（version vector）[59]。这一思路有多种变体，其中最有意思的或许是 Riak 2.0 [62, 63] 采用的点分版本向量（dotted version vector）[60, 61]。这里就不深入细节了，其工作方式与购物车例子相当相似。

与图 6-15 中的版本号一样，版本向量在客户端读取值时由数据库副本发给客户端，并要在客户端写回新值时随之发回。（Riak 把版本向量编码成字符串，称为因果上下文，causal context。）有了版本向量，数据库就能区分覆盖与并发写入。

版本向量也保证了"从一个副本读取、再写回另一个副本"是安全的。这样做可能产生兄弟，但只要兄弟被正确合并，就不会丢数据。

版本向量与向量时钟

版本向量（version vector）有时也被叫做向量时钟（vector clock），但两者并不完全相同。区别相当微妙 [61, 64, 65]，详见参考文献；简单来说，比较副本状态时，版本向量才是合适的数据结构。

小结

本章我们考察了复制这个问题。复制可以服务于多种目的——

高可用性

即便一台机器（乃至若干机器、整个可用区或一整个区域）宕机，系统仍能继续运行。

持久性

即便整台机器（乃至一整个区域）永久失效，也确保数据不丢。

离线运行

让应用在网络中断时也能继续工作。

延迟

把数据放到地理上贴近用户的地方，让交互更快。

可扩展性

通过把读请求分摊到多个副本上，处理超过单机能力的读取量。

虽然思路看起来很简单——把同一份数据保留在多台机器上——复制其实出乎意料地棘手。它要求我们仔细考量并发、各种可能出错的状况，以及如何应对这些故障的后果。至少要处理好节点不可用与网络中断（这还没算上那些更阴险的故障，比如软件 bug 或硬件错误造成的静默数据损坏）。

本章讨论了三种主要的复制方法：

单主复制

客户端把所有写入发给同一个节点（主节点），由主节点向其他副本（从节点）发送数据变更事件流。读取可以发往任何副本，但从节点上的读取可能是陈旧的。

多主复制

客户端把每次写入发给多个主节点中的一个，任何主节点都能接受写入。各主节点之间以及向所有从节点都会发送数据变更事件流。

无主复制

客户端把每次写入发给多个节点，再并行从多个节点读取，以发现并修正持有陈旧数据的节点。

各种方法各有优劣。单主复制因为易于理解、能提供强一致性而广受欢迎。多主与无主复制在节点故障、网络中断、延迟尖峰面前更稳健，代价是要处理冲突解决，且只能提供较弱的一致性保证。

复制既可以是同步的，也可以是异步的，这在出故障时对系统行为有深远影响。系统平稳运行时异步复制速度很快，但一旦复制延迟变大、服务器失效又会怎样——这是必须事先想清楚的事。一旦主节点失效，又把一个异步更新的从节点提升为新主，最近提交的数据就可能就此丢失。

我们看了几种由复制延迟引出的奇怪效果，并讨论了几种一致性模型，帮助我们决定应用在复制延迟下应当如何表现：

读后写一致性

用户应当始终能看到自己刚提交过的数据。

单调读

用户在某一时刻看到了某份数据后，不应在之后又看到更早时刻的数据。

一致前缀读

用户看到的数据应当处于具有因果意义的状态——例如先看到问题再看到回答。

最后，我们讨论了多主与无主复制如何让所有副本最终收敛到一致状态：用版本向量或类似算法检测哪些写入是并发的，再用 CRDT 等冲突解决算法把并发写入的值合并起来。LWW 与人工解决冲突也是可选项。

本章假设每个副本都存有整个数据库的完整副本，但这对大数据集并不现实。下一章我们会讨论分片（sharding），它让每台机器只存储数据的一部分。

参考文献

[1] B. G. Lindsay, P. G. Selinger, C. Galtieri, J. N. Gray, R. A. Lorie, T. G. Price, F. Putzolu, I. L. Traiger, B. W. Wade. "Notes on Distributed Databases." IBM Research, Research Report RJ2571(33471), July 1979. 归档于 perma.cc/EPZ3-MHDD

[2] Kenny Gryp. "MySQL Terminology Updates." dev.mysql.com, July 2020. 归档于 perma.cc/S62G-6RJ2

[3] Oracle Corporation. "Oracle (Active) Data Guard 19c: Real-Time Data Protection and Availability." White Paper, oracle.com, March 2019. 归档于 perma.cc/P5ST-RPKE

[4] Microsoft. "What Is an Always On Availability Group?" learn.microsoft.com, September 2024. 归档于 perma.cc/ABH6-3MXF

[5] Mostafa Elhemali, Niall Gallagher, Nicholas Gordon, Joseph Idziorek, Richard Krog, Colin Lazier, Erben Mo, Akhilesh Mritunjai, Somu Perianayagam, Tim Rath, Swami Sivasubramanian, James Christopher Sorenson III, Sroaj Sosothikul, Doug Terry, Akshat Vig. "Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service." 见 USENIX Annual Technical Conference (ATC), July 2022.

[6] Rebecca Taft, Irfan Sharif, Andrei Matei, Nathan VanBenschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, Paul Bardea, Amruta Ranade, Ben Darnell, Bram Gruneir, Justin Jaffray, Lucy Zhang, Peter Mattis. "CockroachDB: The Resilient Geo-Distributed SQL Database." 见 ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2020. doi:10.1145/3318464.3386134

[7] Dongxu Huang, Qi Liu, Qiu Cui, Zhuhe Fang, Xiaoyu Ma, Fei Xu, Li Shen, Liu Tang, Yuxing Zhou, Menglong Huang, Wan Wei, Cong Liu, Jian Zhang, Jianjun Li, Xuelian Wu, Lingyu Song, Ruoxi Sun, Shuaipeng Yu, Lei Zhao, Nicholas Cameron, Liquan Pei, Xin Tang. "TiDB: A Raft-Based HTAP Database." Proceedings of the VLDB Endowment, volume 13, issue 12, pages 3072–3084, August 2020. doi:10.14778/3415478.3415535

[8] Mallory Knodel, Niels ten Oever. "Terminology, Power, and Inclusive Language in Internet-Drafts and RFCs." IETF Internet-Draft, August 2023. 归档于 perma.cc/5ZY9-725E

[9] Buck Hodges. "Postmortem: VSTS 4 September 2018." devblogs.microsoft.com, September 2018. 归档于 perma.cc/ZF5R-DYZS

[10] Gunnar Morling. "Leader Election with S3 Conditional Writes." www.morling.dev, August 2024. 归档于 perma.cc/7V2N-J78Y

[11] Vignesh Chandramohan, Rohan Desai, Chris Riccomini. "SlateDB Manifest Design." github.com, May 2024. 归档于 perma.cc/8EUY-P32Z

[12] Stas Kelvich. "Why Does Neon Use Paxos Instead of Raft, and What's the Difference?" neon.tech, August 2022. 归档于 perma.cc/SEZ4-2GXU

[13] Dimitri Fontaine. "An Introduction to the pg_auto_failover Project." tapoueh.org, November 2021. 归档于 perma.cc/3WH5-6BAF

[14] Jesse Newland. "GitHub Availability This Week." github.blog, September 2012. 归档于 perma.cc/3YRF-FTFJ

[15] Mark Imbriaco. "Downtime Last Saturday." github.blog, December 2012. 归档于 perma.cc/M7X5-E8SQ

[16] John Hugg. "'All In' with Determinism for Performance and Testing in Distributed Systems." 见 Strange Loop, September 2015.

[17] Hironobu Suzuki. "The Internals of PostgreSQL." interdb.jp, 2017. 归档于 archive.org

[18] Amit Kapila. "WAL Internals of PostgreSQL." 见 PostgreSQL Conference (PGCon), May 2012. 归档于 perma.cc/6225-3SUX

[19] Amit Kapila. "Evolution of Logical Replication." amitkapila16.blogspot.com, September 2023. 归档于 perma.cc/F9VX-JLER

[20] Aru Petchimuthu. "Upgrade Your Amazon RDS for PostgreSQL or Amazon Aurora PostgreSQL Database, Part 2: Using the pglogical Extension." aws.amazon.com, August 2021. 归档于 perma.cc/RXT8-FS2T

[21] Yogeshwer Sharma, Philippe Ajoux, Petchean Ang, David Callies, Abhishek Choudhary, Laurent Demailly, Thomas Fersch, Liat Atsmon Guz, Andrzej Kotulski, Sachin Kulkarni, Sanjeev Kumar, Harry Li, Jun Li, Evgeniy Makeev, Kowshik Prakasam, Robbert van Renesse, Sabyasachi Roy, Pratyush Seth, Yee Jiun Song, Benjamin Wester, Kaushik Veeraraghavan, Peter Xie. "Wormhole: Reliable Pub-Sub to Support Geo-Replicated Internet Services." 见 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI), May 2015.

[22] Douglas B. Terry. "Replicated Data Consistency Explained Through Baseball." Microsoft Research, Technical Report MSR-TR-2011-137, October 2011. 归档于 perma.cc/F4KZ-AR38

[23] Douglas B. Terry, Alan J. Demers, Karin Petersen, Mike J. Spreitzer, Marvin M. Theher, Brent B. Welch. "Session Guarantees for Weakly Consistent Replicated Data." 见 3rd International Conference on Parallel and Distributed Information Systems (PDIS), September 1994. doi:10.1109/PDIS.1994.331722

[24] Werner Vogels. "Eventually Consistent." ACM Queue, volume 6, issue 6, pages 14–19, October 2008. doi:10.1145/1466443.1466448

[25] Simon Willison. Reply to: "My thoughts about Fly.io (so far) and other newish technology I'm getting into." news.ycombinator.com, May 2022.

[26] Nithin Tharakan. "Scaling Bitbucket's Database." atlassian.com, October 2020. 归档于 perma.cc/JAB7-9FGX

[27] Terry Pratchett. Reaper Man: A Discworld Novel. Victor Gollancz, 1991. ISBN: 9780575049796

[28] Peter Bailis, Alan Fekete, Michael J. Franklin, Ali Ghodsi, Joseph M. Hellerstein, Ion Stoica. "Coordination Avoidance in Database Systems." Proceedings of the VLDB Endowment, volume 8, issue 3, pages 185–196, November 2014. doi:10.14778/2735508.2735509

[29] Yaser Raja, Peter Celentano. "PostgreSQL Bi-Directional Replication Using pglogical." aws.amazon.com, January 2022. 归档于 perma.cc/BUQ2-5QWN

[30] Robert Hodges. "If You *Must* Deploy Multi-Master Replication, Read This First." scale-out-blog.blogspot.com, April 2012. 归档于 perma.cc/C2JN-F6Y8

[31] Lars Hofhansl. "HBASE-7709: Infinite Loop Possible in Master/Master Replication." issues.apache.org, January 2013. 归档于 perma.cc/24G2-8NLC

[32] John Day-Richter. "What's Different About the New Google Docs: Making Collaboration Fast." drive.googleblog.com, September 2010. 归档于 perma.cc/5TL8-TSJ2

[33] Evan Wallace. "How Figma's Multiplayer Technology Works." figma.com, October 2019. 归档于 perma.cc/L49H-LY4D

[34] Tuomas Artman. "Scaling the Linear Sync Engine." linear.app, June 2023.

[35] Amr Saafan. "Why Sync Engines Might Be the Future of Web Applications." nilebits.com, September 2024. 归档于 perma.cc/5N73-5M3V

[36] Isaac Hagoel. "Are Sync Engines the Future of Web Applications?" dev.to, July 2024. 归档于 perma.cc/R9HF-BKKL

[37] Sujay Jayakar. "A Map of Sync." stack.convex.dev, October 2024. 归档于 perma.cc/82R3-H42A

[38] Alex Feyerke. "Designing Offline-First Web Apps." alistapart.com, December 2013. 归档于 perma.cc/WH7R-S2DS

[39] Martin Kleppmann, Adam Wiggins, Peter van Hardenberg, Mark McGranaghan. "Local-First Software: You Own Your Data, in Spite of the Cloud." 见 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!), October 2019. doi:10.1145/3359591.3359737

[40] Martin Kleppmann. "The Past, Present, and Future of Local-First." 见 Local-First Conference, May 2024.

[41] Conrad Hofmeyr. "API Calling Is to Sync Engines as jQuery Is to React." powersync.com, November 2024. 归档于 perma.cc/2FP9-7WJJ

[42] Peter van Hardenberg, Martin Kleppmann. "PushPin: Towards Production-Quality Peer-to-Peer Collaboration." 见 7th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC), April 2020. doi:10.1145/3380787.3393683

[43] Leonard Kawell, Jr., Steven Beckhardt, Timothy Halvorsen, Raymond Ozzie, Irene Greif. "Replicated Document Management in a Group Communication System." 见 ACM Conference on Computer-Supported Cooperative Work (CSCW), September 1988. doi:10.1145/62266.1024798

[44] Ricky Pusch. "Explaining How Fighting Games Use Delay-Based and Rollback Netcode." words.infil.net and arstechnica.com, October 2019. 归档于 perma.cc/DE7W-RDJ8

[45] Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, Werner Vogels. "Dynamo: Amazon's Highly Available Key-Value Store." 见 21st ACM Symposium on Operating Systems Principles (SOSP), October 2007. doi:10.1145/1323293.1294281

[46] Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. "Conflict-Free Replicated Data Types." 见 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), October 2011. doi:10.1007/978-3-642-24550-3_29

[47] Chengzheng Sun, Clarence Ellis. "Operational Transformation in Real-Time Group Editors: Issues, Algorithms, and Achievements." 见 ACM Conference on Computer Supported Cooperative Work (CSCW), November 1998. doi:10.1145/289444.289469

[48] Joseph Gentle, Martin Kleppmann. "Collaborative Text Editing with Egwalker: Better, Faster, Smaller." 见 20th European Conference on Computer Systems (EuroSys), March 2025. doi:10.1145/3689031.3696076

[49] Dharma Shukla. "Azure Cosmos DB: Pushing the Frontier of Globally Distributed Databases." azure.microsoft.com, September 2018. 归档于 perma.cc/UT3B-HH6R

[50] David K. Gifford. "Weighted Voting for Replicated Data." 见 7th ACM Symposium on Operating Systems Principles (SOSP), December 1979. doi:10.1145/800215.806583

[51] Marc Brooker. "Dynamo, DynamoDB, and Aurora DSQL." brooker.co.za, August 2025. 归档于 perma.cc/XG3C-ALDQ

[52] Heidi Howard, Dahlia Malkhi, Alexander Spiegelman. "Flexible Paxos: Quorum Intersection Revisited." 见 20th International Conference on Principles of Distributed Systems (OPODIS), December 2016. doi:10.4230/LIPIcs.OPODIS.2016.25

[53] Joseph Blomstedt. "Bringing Consistency to Riak." 见 RICON West, October 2012. 归档于 archive.org

[54] Peter Bailis, Shivaram Venkataraman, Michael J. Franklin, Joseph M. Hellerstein, Ion Stoica. "Quantifying Eventual Consistency with PBS." The VLDB Journal, volume 23, issue 2, pages 279–302, April 2014. doi:10.1007/s00778-013-0330-1

[55] Colin Breck. "Shared-Nothing Architectures for Server Replication and Synchronization." blog.colinbreck.com, December 2019. 归档于 perma.cc/48P3-J6CJ

[56] Jeffrey Dean, Luiz André Barroso. "The Tail at Scale." Communications of the ACM, volume 56, issue 2, pages 74–80, February 2013. doi:10.1145/2408776.2408794

[57] Peng Huang, Chuanxiong Guo, Lidong Zhou, Jacob R. Lorch, Yingnong Dang, Murali Chintalapati, Randolph Yao. "Gray Failure: The Achilles' Heel of Cloud-Scale Systems." 见 16th Workshop on Hot Topics in Operating Systems (HotOS), May 2017. doi:10.1145/3102980.3103005

[58] Leslie Lamport. "Time, Clocks, and the Ordering of Events in a Distributed System." Communications of the ACM, volume 21, issue 7, pages 558–565, July 1978. doi:10.1145/359545.359563

[59] D. Stott Parker Jr., Gerald J. Popek, Gerard Rudisin, Allen Stoughton, Bruce J. Walker, Evelyn Walton, Johanna M. Chow, David Edwards, Stephen Kiser, Charles Kline. "Detection of Mutual Inconsistency in Distributed Systems." IEEE Transactions on Software Engineering, volume SE-9, issue 3, pages 240–247, May 1983. doi:10.1109/TSE.1983.236733

[60] Nuno Preguiça, Carlos Baquero, Paulo Sérgio Almeida, Victor Fonte, Ricardo Gonçalves. "Dotted Version Vectors: Logical Clocks for Optimistic Replication." arXiv:1011.5808, November 2010.

[61] Giridhar Manepalli. "Clocks and Causality—Ordering Events in Distributed Systems." exhypothesi.com, November 2022. 归档于 perma.cc/85REU-KVLQ

[62] Sean Cribbs. "A Brief History of Time in Riak." 见 RICON, October 2014. 归档于 perma.cc/7U9P-6JFX

[63] Russell Brown. "Vector Clocks Revisited Part 2: Dotted Version Vectors." riak.com, November 2015. 归档于 perma.cc/96QP-W98R

[64] Carlos Baquero. "Version Vectors Are Not Vector Clocks." haslab.wordpress.com, July 2011. 归档于 perma.cc/7PNU-4AMG

[65] Reinhard Schwarz, Friedemann Mattern. "Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail." Distributed Computing, volume 7, issue 3, pages 149–174, March 1994. doi:10.1007/BF02277859