复制

可能出错的事物与不可能出错的事物之间的主要区别在于，当不可能出错的事物出错时，通常会发现很难接触到或修复它。

道格拉斯·亚当斯，《大部分无害》（1992）

复制意味着在通过网络连接的多台机器上保留相同数据的副本。如“分布式与单节点系统”中所讨论的，您可能希望复制数据的原因有几个：

• 为了将数据地理上靠近用户（从而减少访问延迟）

• 为了允许系统在某些部分发生故障时仍然继续工作（从而提高可用性）

• 为了扩展可以处理读取查询的机器数量（从而提高读取吞吐量）

在本章中，我们将假设您的数据集足够小，以至于每台机器可以保存整个数据集的副本。在第 7 章中，我们将放宽这一假设，并讨论对于单台机器来说过大的数据集的分片（分区）。在后面的章节中，我们将讨论在复制数据系统中可能发生的各种故障，以及如何处理这些故障。

如果您正在复制的数据不会随时间变化，那么复制就很简单：您只需将数据复制到每个节点一次，便完成了。复制的所有困难都在于处理复制数据的变化，这正是本章的主题。我们将讨论三类算法，用于在节点之间复制变化：单主节点、多主节点和无主节点复制。几乎所有分布式数据库都使用这三种方法中的一种。它们各有优缺点，我们将详细探讨。

在复制中需要考虑许多权衡：例如，是否使用同步或异步复制，以及如何处理失败的副本。这些通常是数据库中的配置选项，尽管细节因数据库而异，但一般原则在许多不同的实现中是相似的。我们将在本章中讨论这些选择的后果。

数据库的复制是一个古老的话题——自 1970 年代以来，原则没有太大变化，因为网络的基本限制一直保持不变。尽管如此，像最终一致性这样的概念仍然会引起混淆。在“复制延迟的问题”一章中，我们将更准确地讨论最终一致性，并讨论诸如读取你的写入和单调读取保证等内容。

实际上，复制和备份通常是相辅相成的。备份有时是设置复制过程的一部分，正如我们将在“设置新跟随者”中看到的那样。相反，归档复制日志也可以是备份过程的一部分。

一些数据库内部维护不可变的过去状态快照，这些快照作为一种内部备份。然而，这意味着将旧版本的数据与当前状态存储在同一存储介质上。如果数据量很大，将旧数据的备份存储在针对不常访问数据优化的对象存储中，可能会更便宜，而将数据库的当前状态仅存储在主存储中。

单主节点复制

每个存储数据库副本的节点称为副本。随着副本数量的增加，必然会出现一个问题：我们如何确保所有数据都能出现在所有副本上？

每次对数据库的写入都需要由每个副本处理；否则，副本将不再包含相同的数据。最常见的解决方案称为基于主节点的复制、主备复制或主动/被动复制。其工作原理如下（见图 6-1）：

其中一个副本被指定为主节点（也称为主副本或源副本¹）。当客户端想要写入数据库时，必须将请求发送给主节点，主节点首先将新数据写入其本地存储。

其他副本被称为跟随者（只读副本、次级副本或热备份）。每当主节点将新数据写入其本地存储时，它还会将数据更改作为复制日志或变更流发送给所有跟随者。每个跟随者从主节点那里获取日志，并相应地更新其本地数据库副本，按照与主节点处理时相同的顺序应用所有写入。

当客户端想要从数据库中读取数据时，可以查询主节点或任何一个跟随者。然而，写入操作仅在主节点上被接受（从客户端的角度来看，跟随者是只读的）。

如果数据库是分片的（见第 7 章），每个分片都有一个主节点。不同的分片可以在不同的节点上有它们的主节点，但每个分片必须仍然有一个主节点节点。在“多主节点复制”中，我们将讨论一种替代模型，在这种模型中，系统可以在同一时间对同一个分片有多个主节点。

单主节点复制被广泛使用。它是许多关系数据库的内置功能，例如 PostgreSQL、MySQL、Oracle Data Guard² 和 SQL Server 的 Always On 可用性组³。它也被一些文档数据库使用，如 MongoDB 和 DynamoDB⁴，消息代理如 Kafka，复制块设备如 DRBD，以及一些网络文件系统。许多共识算法，如 Raft，广泛用于 CockroachDB⁵、TiDB⁶、etcd 和 RabbitMQ 仲裁队列（等），也基于单一主节点，并在旧主节点失败时自动选举新主节点（我们将在[链接待更新]中更详细地讨论共识）。

同步与异步复制

一个复制系统的重要细节是复制是同步进行还是异步进行。（在关系数据库中，这通常是一个可配置的选项；而其他系统通常被硬编码为其中之一。）

想想图 6-1 中发生的情况，网站的用户更新他们的个人资料图片。在某个时刻，客户端将更新请求发送给主节点；不久之后，主节点接收到该请求。在某个时刻，主节点将数据更改转发给跟随者。最终，主节点通知客户端更新成功。图 6-2 展示了时间安排可能如何运作的一种方式。

在图 6-2 的示例中，跟随者 1 的复制是同步的：主节点在跟随者 1 确认收到写入之前，不会向用户报告成功，也不会让其他客户端看到该写入。跟随者 2 的复制是异步的：主节点发送消息，但不等待跟随者的响应。

该图表明，跟随者 2 处理消息之前存在显著的延迟。通常，复制速度相当快：大多数数据库系统在不到一秒的时间内将更改应用到跟随者。然而，无法保证所需的时间。某些情况下，跟随者可能会落后于主节点几分钟或更长时间；例如，如果跟随者正在从故障中恢复，如果系统在接近最大容量运行，或者如果节点之间存在网络问题。

同步复制的优点在于，跟随者可以保证拥有与主节点一致的最新数据副本。如果主节点突然故障，我们可以确保数据仍然在跟随者上可用。缺点是，如果同步跟随者没有响应（因为它崩溃了，或者网络故障，或其他任何原因），写入操作将无法处理。主节点必须阻止所有写入，并等待同步副本再次可用。

因此，让所有跟随者都保持同步是不可行的：任何一个节点的故障都会导致整个系统停滞不前。在实践中，如果一个数据库提供同步复制，通常意味着其中一个跟随者是同步的，而其他的则是异步的。如果同步跟随者变得不可用或变慢，则会将一个异步跟随者变为同步。这保证了您在至少两个节点上拥有最新的数据副本：主节点和一个同步跟随者。这种配置有时也被称为半同步。

在某些系统中，大多数（例如，5 个副本中的 3 个，包括主节点）副本是同步更新的，而其余少数则是异步的。这是一个法定人数的例子，我们将在“读取和写入的法定人数”中进一步讨论。多数法定人数通常用于使用共识协议进行自动主节点选举的系统，我们将在[链接待补充]中回到这个话题。

有时，基于主节点的复制被配置为完全异步。在这种情况下，如果主节点失败且无法恢复，则尚未复制到跟随者的任何写入都会丢失。这意味着即使写入已确认给客户端，也不能保证其持久性。然而，完全异步的配置有一个优点，即主节点可以继续处理写入，即使所有跟随者都落后了。

削弱持久性听起来像是一个糟糕的权衡，但异步复制仍然被广泛使用，特别是在有许多跟随者或它们地理分布广泛的情况下⁸。我们将在“复制延迟的问题”中回到这个问题。

设置新跟随者

不时地，您需要设置新的跟随者——可能是为了增加副本的数量，或者替换故障节点。您如何确保新的跟随者拥有主节点数据的准确副本？

仅仅将数据文件从一个节点复制到另一个节点通常是不够的：客户端不断地向数据库写入数据，数据始终处于变化中，因此标准的文件复制会在不同的时间点看到数据库的不同部分。结果可能没有任何意义。

您可以通过锁定数据库（使其无法写入）来使磁盘上的文件保持一致，但这将违背我们高可用性的目标。幸运的是，设置跟随者通常可以在不宕机的情况下完成。从概念上讲，过程如下：

1. 在某个时间点对主节点的数据库进行一致性快照——如果可能的话，不对整个数据库进行锁定。大多数数据库都有这个功能，因为这也是备份所需的。在某些情况下，需要第三方工具，例如 MySQL 的 Percona XtraBackup。

2. 将快照复制到新的跟随节点。

3. 跟随者连接到主节点，并请求自快照拍摄以来发生的所有数据更改。这要求快照与主节点的复制日志中的确切位置相关联。该位置有多种名称：例如，PostgreSQL 称之为日志序列号；MySQL 有两种机制，分别是二进制日志坐标和全局事务标识符（GTID）。

4. 当跟随者处理完自快照以来的数据更改积压时，我们说它已经赶上。它现在可以继续处理来自主节点的实时数据更改。

设置跟随者的实际步骤因数据库而异。在某些系统中，该过程是完全自动化的，而在其他系统中，它可能是一个相对复杂的多步骤工作流程，需要管理员手动执行。

您还可以将复制日志归档到对象存储中；结合对象存储中整个数据库的定期快照，这是一种实现数据库备份和灾难恢复的好方法。您还可以通过从对象存储中下载这些文件来执行设置新跟随者的步骤 1 和步骤 2。例如，WAL-G 为 PostgreSQL、MySQL 和 SQL Server 执行此操作，而 Litestream 为 SQLite 执行等效操作。

处理节点故障

系统中的任何节点都可能出现故障，可能是由于意外故障，也可能是由于计划中的维护（例如，重启机器以安装内核安全补丁）。能够在不造成停机的情况下重启单个节点对运营和维护来说是一个很大的优势。因此，我们的目标是使整个系统在个别节点故障的情况下仍然运行，并尽量将节点故障的影响降到最低。

如何通过基于主节点的复制实现高可用性？

跟随者故障：追赶恢复

每个跟随者在其本地磁盘上保留一份从主节点接收到的数据变更日志。如果一个跟随者崩溃并重新启动，或者主节点与跟随者之间的网络暂时中断，跟随者可以相对容易地恢复：从其日志中，它知道故障发生前处理的最后一笔交易。因此，跟随者可以连接到主节点并请求在跟随者断开连接期间发生的所有数据变更。当它应用了这些变更后，它就追赶上了主节点，并可以继续像以前一样接收数据变更流。

尽管追随者恢复在概念上很简单，但在性能方面可能会面临挑战：如果数据库的写入吞吐量很高，或者追随者离线时间较长，可能会有大量的写入需要赶上。在这个赶上的过程中，恢复中的追随者和主节点（需要将积压的写入发送给追随者）都会面临很大的负载。

一旦所有追随者确认已处理完日志，主节点可以删除其写入日志，但如果某个追随者长时间不可用，主节点面临一个选择：要么保留日志，直到追随者恢复并赶上（这有可能导致主节点的磁盘空间耗尽），要么删除该不可用追随者尚未确认的日志（在这种情况下，追随者将无法从日志中恢复，必须在恢复时从备份中恢复）。

主节点故障：故障转移

处理主节点故障的过程更为复杂：需要提升其中一个跟随者为新的主节点，客户端需要重新配置以将写入请求发送到新的主节点，其他跟随者需要开始从新的主节点那里获取数据变更。这个过程称为故障转移。

故障转移可以手动进行（管理员被通知主节点已故障并采取必要步骤以指定新的主节点）或自动进行。自动故障转移过程通常包括以下步骤：

1. 确定主节点已故障。可能出现许多问题：崩溃、停电、网络问题等等。没有万无一失的方法来检测出了什么问题，因此大多数系统简单地使用超时机制：节点之间频繁地相互发送消息，如果某个节点在一段时间内没有响应——比如说 30 秒——则假定该节点已死。（如果主节点是为了计划维护而故意关闭，则不适用此情况。）

2. 选择新主节点。这可以通过选举过程来完成（主节点由剩余副本的多数选出），或者可以由先前建立的控制节点任命新主节点¹¹。通常，最佳的主节点候选人是拥有来自旧主节点的最新数据变更的副本（以最小化数据丢失）。让所有节点就新主节点达成一致是一个共识问题，详细讨论见[链接待补充]。

3. 重新配置系统以使用新主节点。客户端现在需要将写请求发送给新主节点（我们在“请求路由”中讨论此问题）。如果旧主节点重新上线，它可能仍然认为自己是主节点，而没有意识到其他副本已迫使其下台。系统需要确保旧主节点成为跟随者并认可新主节点。

故障转移充满了可能出错的事情：

• 如果使用异步复制，新主节点在旧主节点失败之前可能没有接收到所有的写入。如果前任主节点在新主节点被选出后重新加入集群，这些写入应该如何处理？在此期间，新主节点可能已经接收到了冲突的写入。最常见的解决方案是简单地丢弃旧主节点未复制的写入，这意味着你认为已提交的写入实际上并没有持久化。

• 丢弃写入尤其危险，如果数据库外部的其他存储系统需要与数据库内容进行协调。例如，在 GitHub 的一个事件中，一个过时的 MySQL 从属被提升为主节点。该数据库使用自增计数器为新行分配主键，但由于新主节点的计数器落后于旧主节点，因此它重新使用了一些之前由旧主节点分配的主键。这些主键也在 Redis 存储中使用，因此主键的重用导致 MySQL 和 Redis 之间的不一致，导致一些私密数据被错误地披露给了不正确的用户。

• 在某些故障场景中（见[链接待补充]），可能会发生两个节点都认为自己是主节点的情况。这种情况被称为“分脑”，是非常危险的：如果两个主节点都接受写入，并且没有解决冲突的过程（见“多主节点复制”），数据很可能会丢失或损坏。作为一种安全措施，一些系统有机制在检测到两个主节点时关闭一个节点。然而，如果这个机制设计不当，可能会导致两个节点都被关闭。此外，还有一个风险是，当分脑被检测到并且旧节点被关闭时，可能已经为时已晚，数据已经被损坏。

• 在宣布主节点死亡之前，合适的超时时间是多少？较长的超时时间意味着在主节点失败的情况下恢复所需的时间更长。然而，如果超时时间过短，可能会导致不必要的故障转移。例如，暂时的负载激增可能导致节点的响应时间超过超时，或者网络故障可能导致数据包延迟。如果系统已经在高负载或网络问题中挣扎，不必要的故障转移可能会使情况变得更糟，而不是更好。

这些问题没有简单的解决方案。因此，一些运维团队更倾向于手动执行故障转移，即使软件支持自动故障转移。

故障转移中最重要的事情是选择一个最新的跟随者作为新的主节点——如果使用的是同步或半同步复制，那么这个跟随者就是旧主节点在确认写入之前等待的跟随者。使用异步复制时，可以选择具有最大日志序列号的跟随者。这可以最小化故障转移期间丢失的数据量：丢失几分之一秒的写入可能是可以接受的，但选择一个落后几天的跟随者可能会造成灾难性后果。

这些问题——节点故障；不可靠的网络；以及关于副本一致性、持久性、可用性和延迟的权衡——实际上是分布式系统中的基本问题。在[链接即将到来]和[链接即将到来]中，我们将更深入地讨论这些问题。

复制日志的实现

基于主节点的复制在底层是如何工作的？在实践中使用了几种不同的复制方法，因此让我们简要看一下每一种。

基于语句的复制

在最简单的情况下，主节点记录它执行的每个写请求（语句），并将该语句日志发送给其跟随者。对于关系数据库，这意味着每个 INSERT 、 UPDATE 或 DELETE 语句都会转发给跟随者，每个跟随者解析并执行该 SQL 语句，就好像它是从客户端接收到的一样。

尽管这听起来合理，但这种复制方法可能会以各种方式出现问题：

• 任何调用非确定性函数的语句，例如 NOW() 获取当前日期和时间或 RAND() 获取随机数，可能会在每个副本上生成不同的值。

• 如果语句使用自增列，或者依赖于数据库中现有的数据（例如， UPDATE …​ WHERE <some condition> ），则必须在每个副本上以完全相同的顺序执行，否则可能会产生不同的效果。当存在多个并发执行的事务时，这可能会造成限制。

• 具有副作用的语句（例如，触发器、存储过程、自定义函数）可能会导致每个副本上发生不同的副作用，除非这些副作用是绝对确定的。

可以绕过这些问题——例如，主节点可以在记录语句时将任何非确定性函数调用替换为固定的返回值，以便所有跟随者都获得相同的值。以固定顺序执行确定性语句的想法类似于我们之前在“事件溯源和 CQRS”中讨论的事件溯源模型。这种方法也被称为状态机复制，我们将在[链接即将到来]中讨论其背后的理论。

在 MySQL 5.1 之前，使用的是基于语句的复制。尽管现在有时仍会使用这种方法，因为它相当紧凑，但默认情况下，如果语句中存在任何非确定性，MySQL 现在会切换到基于行的复制（稍后讨论）。VoltDB 使用基于语句的复制，并通过要求事务是确定性的来确保其安全性¹²。然而，在实践中，保证确定性可能很困难，因此许多数据库更倾向于其他复制方法。

预写日志（WAL）传输

在第 4 章中，我们看到需要预写日志来使 B 树存储引擎稳健：每次修改首先写入 WAL，以便在崩溃后可以将树恢复到一致状态。由于 WAL 包含恢复索引和堆到一致状态所需的所有信息，我们可以使用完全相同的日志在另一个节点上构建副本：除了将日志写入磁盘，主节点还通过网络将其发送给跟随者。当跟随者处理此日志时，它构建出与主节点上找到的完全相同的文件副本。

这种复制方法在 PostgreSQL 和 Oracle 等数据库中使用¹³¹⁴。主要缺点是日志以非常低的级别描述数据：WAL 包含了哪些字节在什么磁盘块中被更改的详细信息。这使得复制与存储引擎紧密耦合。如果数据库在不同版本之间更改其存储格式，通常无法在主节点和从节点上运行不同版本的数据库软件。

这看起来可能是一个次要的实现细节，但它可能会对操作产生重大影响。如果复制协议允许从节点使用比主节点更新的软件版本，您可以通过先升级从节点，然后进行故障转移使其中一个升级节点成为新的主节点，从而实现数据库软件的零停机时间升级。如果复制协议不允许这种版本不匹配，正如 WAL 传输中常见的那样，这种升级就需要停机。

逻辑（基于行）日志复制

一种替代方案是为复制和存储引擎使用不同的日志格式，这样可以将复制日志与存储引擎的内部实现解耦。这种复制日志称为逻辑日志，以区别于存储引擎的（物理）数据表示。

关系数据库的逻辑日志通常是一系列记录，描述以行的粒度对数据库表的写入操作：

• 对于插入的行，日志包含所有列的新值。

• 对于删除的行，日志包含足够的信息以唯一标识被删除的行。通常这将是主键，但如果表中没有主键，则需要记录所有列的旧值。

• 对于更新的行，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少所有更改列的新值）。

一个修改多个行的事务会生成多个这样的日志记录，随后是一个指示事务已提交的记录。MySQL 除了 WAL（在配置为使用基于行的复制时）外，还保留一个单独的逻辑复制日志，称为 binlog。PostgreSQL 通过将物理 WAL 解码为行插入/更新/删除事件来实现逻辑复制¹⁵。

由于逻辑日志与存储引擎内部解耦，因此可以更容易地保持向后兼容，允许主节点和从节点运行不同版本的数据库软件。这反过来使得以最小的停机时间升级到新版本成为可能¹⁶。

逻辑日志格式也更容易被外部应用解析。如果您想将数据库的内容发送到外部系统，例如用于离线分析的数据仓库，或用于构建自定义索引和缓存，这一点非常有用¹⁷。这种技术称为变更数据捕获，我们将在[链接待补充]中回到这个话题。

复制延迟的问题

能够容忍节点故障只是希望进行复制的一个原因。如“分布式与单节点系统”中提到的，其他原因包括可扩展性（处理比单台机器能处理的更多请求）和延迟（将副本地理上更靠近用户）。

基于主节点的复制要求所有写操作都通过单个节点，但只读查询可以发送到任何副本。对于主要由读取操作组成且只有小部分写操作的工作负载（这在在线服务中通常是情况），有一个吸引人的选择：创建多个跟随者，并将读取请求分配到这些跟随者。这减轻了主节点的负担，并允许附近的副本处理读取请求。

在这种读扩展架构中，您可以通过添加更多的从节点来增加处理只读请求的能力。然而，这种方法实际上只适用于异步复制——如果您尝试对所有从节点进行同步复制，单个节点故障或网络中断将使整个系统无法进行写入。而且，节点越多，出现故障的可能性就越大，因此完全同步的配置将非常不可靠。

不幸的是，如果一个应用程序从异步从节点读取数据，可能会看到过时的信息，如果该从节点落后了。这会导致数据库中出现明显的不一致：如果您同时在主节点和从节点上运行相同的查询，您可能会得到不同的结果，因为并非所有的写入都已在从节点上反映出来。这种不一致只是一个暂时状态——如果您停止对数据库的写入并等待一段时间，从节点最终会赶上并与主节点保持一致。因此，这种现象被称为最终一致性¹⁸。

“最终”这个词故意模糊：一般来说，副本落后的程度没有限制。在正常操作中，主节点上发生写入与在跟随者上反映之间的延迟——复制延迟——可能只有几分之一秒，在实践中并不明显。然而，如果系统在接近容量的情况下运行，或者网络出现问题，延迟很容易增加到几秒钟甚至几分钟。

当延迟如此之大时，它引入的不一致性不仅仅是一个理论问题，而是应用程序的一个实际问题。在本节中，我们将强调在存在复制延迟时可能发生的三个问题的例子。我们还将概述一些解决这些问题的方法。

读取您自己的写入

许多应用程序允许用户提交一些数据，然后查看他们提交的内容。这可能是客户数据库中的一条记录，或是讨论线程上的一条评论，或其他类似的内容。当提交新数据时，必须将其发送到主节点，但当用户查看数据时，可以从从节点读取。如果数据经常被查看但仅偶尔被写入，这种方式尤其合适。

在异步复制中存在一个问题，如图 6-3 所示：如果用户在写入后不久查看数据，新数据可能尚未到达副本。对用户来说，看起来他们提交的数据丢失了，因此他们会感到不满。

在这种情况下，我们需要读后写一致性，也称为读你所写一致性¹⁹。这保证了如果用户重新加载页面，他们将始终看到自己提交的任何更新。它对其他用户没有任何承诺：其他用户的更新可能在稍后的时间才可见。然而，它向用户保证他们自己的输入已被正确保存。

我们如何在基于主节点的复制系统中实现读后写一致性？有多种可能的技术。举几个例子：

• 在读取用户可能已修改的内容时，从主节点或同步更新的跟随者读取；否则，从异步更新的跟随者读取。这要求你有某种方式知道某些内容是否可能已被修改，而不实际查询它。例如，社交网络上的用户个人资料信息通常仅由个人资料的拥有者编辑，而不是其他人。因此，一个简单的规则是：始终从主节点读取用户自己的个人资料，从跟随者读取其他用户的个人资料。

• 如果应用程序中的大多数内容都可能被用户编辑，那么这种方法将无效，因为大多数内容必须从主节点读取（这抵消了读取扩展的好处）。在这种情况下，可以使用其他标准来决定是否从主节点读取。例如，您可以跟踪最后一次更新的时间，并在最后一次更新后的 1 分钟内，所有读取都来自主节点²¹。您还可以监控从节点的复制延迟，并防止对任何落后于主节点超过 1 分钟的从节点进行查询。

• 客户端可以记住其最近一次写入的时间戳——然后系统可以确保为该用户提供读取的副本至少反映到该时间戳的更新。如果副本没有及时更新，可以由另一个副本处理读取，或者查询可以等待直到副本赶上²²。时间戳可以是逻辑时间戳（指示写入顺序的内容，例如日志序列号）或实际系统时钟（在这种情况下，时钟同步变得至关重要；请参见[即将到来的链接]）。

• 如果您的副本分布在不同地区（为了与用户的地理接近性或可用性），则会增加额外的复杂性。任何需要由主节点服务的请求必须路由到包含主节点的区域。

当同一用户从多个设备访问您的服务时，例如桌面网页浏览器和移动应用程序，另一个复杂性就出现了。在这种情况下，您可能希望提供跨设备的写后读一致性：如果用户在一个设备上输入了一些信息，然后在另一个设备上查看，他们应该看到他们刚刚输入的信息。

在这种情况下，还有一些额外的问题需要考虑：

• 需要记住用户最后一次更新的时间戳的方法变得更加困难，因为在一个设备上运行的代码并不知道另一个设备上发生了什么更新。这些元数据需要集中管理。

• 如果您的副本分布在不同的区域，则无法保证来自不同设备的连接会被路由到同一区域。（例如，如果用户的台式计算机使用家庭宽带连接，而他们的移动设备使用蜂窝数据网络，则这些设备的网络路由可能完全不同。）如果您的方法需要从主节点读取数据，您可能需要先将所有用户设备的请求路由到同一区域。

单调读取

我们第二个例子是，当从异步跟随者读取时，可能会出现的异常是用户可能会看到时间向后移动的情况。

如果用户从不同的副本进行多次读取，就可能发生这种情况。例如，图 6-4 显示用户 2345 进行了两次相同的查询，第一次查询发送到一个延迟较小的跟随者，第二次查询发送到一个延迟较大的跟随者。（如果用户刷新网页，每个请求被路由到随机服务器，这种情况是相当可能的。）第一次查询返回了用户 1234 最近添加的评论，但第二次查询没有返回任何内容，因为延迟的跟随者尚未接收到该写入。实际上，第二次查询观察到的系统状态比第一次查询早。这并不会太糟糕，如果第一次查询没有返回任何内容，因为用户 2345 可能不知道用户 1234 最近添加了评论。然而，如果用户 2345 首先看到用户 1234 的评论出现，然后又看到它消失，这对他们来说就非常困惑。

单调读取¹⁸ 是一种保证，确保这种异常不会发生。它的保证程度低于强一致性，但高于最终一致性。当你读取数据时，可能会看到旧值；单调读取仅意味着如果一个用户连续进行多次读取，他们不会看到时间倒退——即，他们在之前读取了较新数据后，不会再读取较旧的数据。

实现单调读取的一种方法是确保每个用户始终从同一个副本进行读取（不同用户可以从不同副本读取）。例如，可以根据用户 ID 的哈希值选择副本，而不是随机选择。然而，如果该副本发生故障，用户的查询将需要重新路由到另一个副本。

一致前缀读取

我们关于复制延迟异常的第三个例子涉及因果关系的违反。想象一下普恩斯先生和凯克夫人之间的以下简短对话：

普恩斯先生： 凯克夫人，您能看到多远的未来？

凯克夫人： 通常大约十秒，普恩斯先生。

这两句话之间存在因果依赖关系：凯克夫人听到了普恩斯先生的问题并作出了回答。

现在，想象有第三个人通过跟随者在听这个对话。凯克夫人所说的话通过一个跟随者传递时延很小，但普恩斯先生所说的话则有更长的复制延迟（见图 6-5）。这个观察者会听到以下内容：

凯克夫人： 通常大约十秒，普恩斯先生。

普恩斯先生： 凯克夫人，您能看到多远的未来？

对观察者来说，凯克夫人似乎在普恩斯先生甚至还没问出问题之前就已经回答了这个问题。这种超能力令人印象深刻，但也非常令人困惑²³。

防止这种异常需要另一种保证：一致前缀读取¹⁸。这个保证意味着，如果一系列写操作以某种顺序发生，那么任何读取这些写操作的人都会看到它们以相同的顺序出现。

在分片（分区）数据库中，这是一个特别的问题，我们将在第 7 章讨论。如果数据库始终以相同的顺序应用写操作，读取操作总是看到一致的前缀，因此这种异常就不会发生。然而，在许多分布式数据库中，不同的分片独立操作，因此没有全局的写操作顺序：当用户从数据库中读取时，他们可能会看到数据库的某些部分处于较旧的状态，而某些部分处于较新的状态。

一种解决方案是确保任何因果相关的写操作都写入同一个分片——但在某些应用中，这样做效率不高。还有一些算法明确跟踪因果依赖关系，这是我们将在“发生在前的关系与并发”中回到的话题。

复制延迟的解决方案

在处理最终一致性系统时，值得考虑如果复制延迟增加到几分钟甚至几小时，应用程序的表现会如何。如果答案是“没问题”，那很好。然而，如果结果是用户体验不佳，那么设计系统以提供更强的保证是很重要的，例如读后写。假装复制是同步的，而实际上它是异步的，这将导致后续出现问题。

如前所述，应用程序可以提供比底层数据库更强的保证，例如，通过在主节点或同步更新的跟随者上执行某些类型的读取。然而，在应用程序代码中处理这些问题是复杂的，容易出错。

对于应用程序开发人员来说，最简单的编程模型是选择一个为副本提供强一致性保证的数据库，例如线性化（见[链接待补充]）和 ACID 事务（见第 8 章）。这使您可以在很大程度上忽略由复制引发的挑战，并将数据库视为只有一个节点。在 2010 年代初，NoSQL 运动提倡这种观点，认为这些特性限制了可扩展性，而大规模系统必须接受最终一致性。

然而，自那时以来，许多数据库开始在提供强一致性和事务的同时，还提供分布式数据库的容错、高可用性和可扩展性优势。如“关系模型与文档模型”中提到的，这一趋势被称为 NewSQL，以与 NoSQL 形成对比（尽管这与 SQL 本身关系不大，更是关于可扩展事务管理的新方法）。

尽管现在可扩展的、强一致性的分布式数据库已经可用，但仍然有充分的理由让一些应用选择使用提供较弱一致性保证的不同形式的复制：它们在面对网络中断时可以提供更强的弹性，并且与事务系统相比，开销更低。我们将在本章的其余部分探讨这些方法。

多主节点复制

到目前为止，我们在本章中只考虑了使用单主节点复制架构。虽然这是一种常见的方法，但还有一些有趣的替代方案。

单主节点复制有一个主要缺点：所有写入都必须通过一个节点。如果由于某种原因无法连接到节点，例如由于您与节点之间的网络中断，您将无法写入数据库。

单主节点复制模型的自然扩展是允许多个节点接受写入。复制仍然以相同的方式进行：每个处理写入的节点必须将该数据更改转发给所有其他节点。我们称之为多主配置（也称为主动/主动或双向复制）。在这种设置中，每个主节点同时充当其他主节点的跟随者。

与单主节点复制一样，可以选择将其设置为同步或异步。假设你有两个主节点，A 和 B，并且你试图向 A 写入。如果写入从 A 同步复制到 B，并且两个节点之间的网络中断，则在网络恢复之前，你无法向 A 写入。因此，同步多主节点复制为你提供了一个与单主节点复制非常相似的模型，即如果你将 B 设为主节点，A 只是将任何写请求转发给 B 执行。

因此，我们不会进一步探讨同步多主节点复制，而是将其视为与单主节点复制等效。本节的其余部分集中于异步多主节点复制，在这种情况下，即使与其他主节点的连接中断，任何主节点也可以处理写入。

地理分布式操作

在单个区域内使用多主节点设置通常没有意义，因为其带来的好处往往无法抵消增加的复杂性。然而，在某些情况下，这种配置是合理的。

想象一下，您有一个在多个不同区域中有副本的数据库（也许是为了容忍整个区域的故障，或者为了更接近您的用户）。这被称为地理分布式、地理分布或地理复制的设置。在单主节点复制中，主节点必须位于某个区域，所有写入都必须经过该区域。

在多主节点配置中，您可以在每个区域拥有一个主节点。图 6-6 显示了这种架构可能的样子。在每个区域内，使用常规的主节点-跟随者复制（跟随者可能位于与主节点不同的可用区）；在区域之间，每个区域的主节点将其更改复制到其他区域的主节点。

让我们比较一下单主节点和多主节点配置在多区域部署中的表现：

性能

在单一主节点配置中，每次写入必须通过互联网发送到主节点所在的区域。这可能会给写入带来显著的延迟，并可能违背设置多个区域的初衷。在多主节点配置中，每次写入可以在本地区域内处理，并异步复制到其他区域。因此，区域间的网络延迟对用户是隐藏的，这意味着感知的性能可能更好。

对区域故障的容忍

在单一主节点配置中，如果主节点所在的区域变得不可用，故障转移可以提升另一个区域的跟随者为主节点。在多主节点配置中，每个区域可以独立于其他区域继续操作，当离线区域重新上线时，复制会赶上。

对网络问题的容忍

即使有专用连接，不同区域之间的流量也可能不如同一区域内或单个区域内的流量可靠。单主配置对这种区域间链接的问题非常敏感，因为当一个区域的客户端想要向另一个区域的主节点写入时，它必须通过该链接发送请求，并在完成之前等待响应。

具有异步复制的多主配置可以更好地容忍网络问题：在暂时的网络中断期间，每个区域的主节点可以独立继续处理写入操作。

一致性

单一主节点系统可以提供强一致性保证，例如可串行化事务，我们将在第 8 章中讨论。多主节点系统最大的缺点是它们能够实现的一致性要弱得多。例如，你无法保证一个银行账户不会变为负数，或者用户名是唯一的：不同的主节点可以处理各自独立的写入（支付账户中的部分资金，注册特定用户名），但当与另一个主节点的写入结合时，可能会违反约束。

这只是分布式系统的一个基本限制。如果你需要强制执行这样的约束，那么单一主节点系统更为合适。然而，正如我们将在“处理冲突写入”中看到的，多主节点系统仍然可以实现一些在不需要这些约束的广泛应用中有用的一致性特性。

多主节点复制不如单主节点复制常见，但许多数据库仍然支持它，包括 MySQL、Oracle、SQL Server 和 YugabyteDB。在某些情况下，它是一个外部附加功能，例如在 Redis Enterprise、EDB Postgres Distributed 和 pglogical 中²⁴。

由于多主节点复制在许多数据库中是一个经过改造的功能，因此通常会存在微妙的配置陷阱和与其他数据库功能的意外交互。例如，自增键、触发器和完整性约束可能会出现问题。因此，多主节点复制通常被认为是一个危险的领域，如果可能的话，应该避免使用²⁵。

多主节点复制拓扑

复制拓扑描述了写入从一个节点传播到另一个节点的通信路径。如果你有两个主节点，如图 6-9 所示，只有一种合理的拓扑：主节点 1 必须将其所有写入发送到主节点 2，反之亦然。对于超过两个主节点的情况，可能会有多种不同的拓扑。一些示例在图 6-7 中进行了说明。

最一般的拓扑是全连接拓扑，如图 6-7(c)所示，其中每个主节点将其写入发送给其他所有主节点。然而，也使用更受限制的拓扑：例如，循环拓扑，其中每个节点从一个节点接收写入，并将这些写入（加上它自己的任何写入）转发给另一个节点。另一种流行的拓扑呈星形：一个指定的根节点将写入转发给所有其他节点。星形拓扑可以推广为树形拓扑。

在环形和星形拓扑中，写入可能需要经过多个节点才能到达所有副本。因此，节点需要转发它们从其他节点接收到的数据更改。为了防止无限复制循环，每个节点都被赋予一个唯一标识符，并且在复制日志中，每个写入都标记有它经过的所有节点的标识符。当一个节点接收到标记有其自身标识符的数据更改时，该数据更改会被忽略，因为该节点知道它已经被处理过。

不同拓扑的问题

环形和星形拓扑的问题在于，如果仅有一个节点发生故障，它可能会中断其他节点之间的复制消息流，使它们无法通信，直到该节点修复。拓扑可以重新配置以绕过故障节点，但在大多数部署中，这种重新配置必须手动进行。更密集连接的拓扑（例如全连接）的容错性更好，因为它允许消息沿不同路径传输，避免了单点故障。

另一方面，全对全拓扑也可能存在问题。特别是，一些网络链接可能比其他链接更快（例如，由于网络拥堵），导致某些复制消息可能会“超越”其他消息，如图 6-8 所示。

在图 6-8 中，客户端 A 在主节点 1 上插入一行数据，而客户端 B 在主节点 3 上更新该行。然而，主节点 2 可能以不同的顺序接收写入：它可能首先接收到更新（从它的角度来看，这是对数据库中不存在的行的更新），然后才接收到相应的插入（应该在更新之前）。

这是一个因果关系的问题，类似于我们在“一致前缀读取”中看到的情况：更新依赖于先前的插入，因此我们需要确保所有节点首先处理插入，然后再处理更新。仅仅给每个写入附加时间戳是不够的，因为时钟不能被信任为足够同步，以正确排序主节点 2 上的这些事件（见[链接待补充]）。

为了正确地排序这些事件，可以使用一种称为版本向量的技术，我们将在本章后面讨论（见“检测并发写入”）。然而，许多多主节点复制系统并没有使用良好的更新排序技术，使它们容易受到如图 6-8 所示的问题。如果您正在使用多主节点复制，值得注意这些问题，仔细阅读文档，并彻底测试您的数据库，以确保它确实提供您所相信的保证。

同步引擎和本地优先软件

多主节点复制适用的另一种情况是，如果您有一个需要在与互联网断开连接时继续工作的应用程序。

例如，考虑一下您手机、笔记本电脑和其他设备上的日历应用。您需要能够随时查看会议（进行读取请求）并输入新会议（进行写入请求），无论您的设备当前是否有互联网连接。如果您在离线时进行任何更改，这些更改需要在设备下次在线时与服务器和其他设备同步。

在这种情况下，每个设备都有一个本地数据库副本，充当主节点（它接受写请求），并且在您所有设备的日历副本之间存在一个异步多主节点复制过程（同步）。复制延迟可能是几个小时甚至几天，具体取决于您何时可以访问互联网。

从架构的角度来看，这种设置与区域之间的多主节点复制非常相似，甚至可以说是极端化：每个设备都是一个“区域”，而它们之间的网络连接极不可靠。

实时协作、优先离线和优先本地的应用程序

此外，许多现代网络应用程序提供实时协作功能，例如用于文本文件和电子表格的 Google Docs 和 Sheets、用于图形的 Figma，以及用于项目管理的 Linear。这些应用程序之所以如此响应迅速，是因为用户输入会立即反映在用户界面中，而无需等待与服务器的网络往返，且一个用户的编辑会以低延迟显示给他们的协作者²⁶²⁷。

这再次导致了一个多主节点架构：每个打开共享文件的网页浏览器标签都是一个副本，您对文件所做的任何更新都会异步复制到其他打开同一文件的用户的设备上。即使应用程序不允许您在离线时继续编辑文件，多个用户可以在不等待服务器响应的情况下进行编辑，这一事实已经使其成为多主节点。

离线编辑和实时协作都需要类似的复制基础设施：应用程序需要捕捉用户对文件所做的任何更改，并立即将其发送给合作者（如果在线），或将其存储在本地以便稍后发送（如果离线）。此外，应用程序需要接收来自合作者的更改，将其合并到用户的本地文件副本中，并更新用户界面以反映最新版本。如果多个用户同时更改了文件，可能需要冲突解决逻辑来合并这些更改。

支持此过程的软件库称为同步引擎。尽管这个想法存在已久，但这个术语最近引起了关注²⁸²⁹。一个允许用户在离线状态下继续编辑文件的应用程序（可以使用同步引擎实现）被称为离线优先³⁰。本地优先软件一词指的是不仅是离线优先的协作应用程序，而且即使开发该软件的开发者关闭所有在线服务，也能继续工作的应用程序³¹。这可以通过使用具有开放标准同步协议的同步引擎来实现，多个服务提供商可用 ³²。例如，Git 是一个本地优先的协作系统（尽管它不支持实时协作），因为您可以通过 GitHub、GitLab 或任何其他代码托管服务进行同步。

同步引擎的优缺点

如今构建网络应用的主要方式是尽量减少客户端的持久状态，并在需要显示新数据或更新某些数据时依赖向服务器发起请求。相比之下，使用同步引擎时，客户端有持久状态，和服务器的通信被移入后台进程。同步引擎的方法有许多优点：

• 本地拥有数据意味着用户界面可以比等待服务调用获取数据时更快地响应。一些应用程序旨在在图形系统的下一个帧中响应用户输入，这意味着在 60 Hz 刷新率的显示器上需要在 16 毫秒内完成渲染。

• 允许用户在离线时继续工作是非常有价值的，尤其是在连接不稳定的移动设备上。使用同步引擎时，应用程序不需要单独的离线模式：离线就等同于具有非常大的网络延迟。

• 同步引擎简化了前端应用的编程模型，相比于在应用代码中执行显式的服务调用。每个服务调用都需要错误处理，如“远程过程调用（RPC）的问题”中所讨论的：例如，如果更新服务器上数据的请求失败，用户界面需要以某种方式反映该错误。同步引擎允许应用对本地数据进行读写，这几乎从不失败，从而导致更具声明性的编程风格³³。

• 为了实时显示其他用户的编辑，您需要接收这些编辑的通知并有效地相应更新用户界面。将同步引擎与反应式编程模型结合起来是实现这一目标的好方法³⁴。

同步引擎在用户可能需要的所有数据提前下载并持久存储在客户端时效果最佳。这意味着数据在需要时可以离线访问，但这也意味着如果用户访问的数据量非常大，同步引擎就不适合使用。例如，下载用户自己创建的所有文件可能是可以的（一个用户通常不会生成那么多数据），但下载整个电子商务网站的目录显然没有意义。

同步引擎由 Lotus Notes 在 1980 年代首创³⁵（当时并未使用该术语），而针对特定应用程序（如日历）的同步也已经存在很长时间。如今，有许多通用的同步引擎，其中一些使用专有的后端服务（例如，Google Firestore、Realm 或 Ditto），而一些则拥有开源后端，使其适合创建以本地为先的软件（例如，PouchDB/CouchDB、Automerge 或 Yjs）。

多人视频游戏同样需要立即响应用户的本地操作，并将其与通过网络异步接收到的其他玩家的操作进行协调。在游戏开发术语中，等同于同步引擎的称为网络代码（netcode）。网络代码中使用的技术非常特定于游戏的需求³⁶，并不直接适用于其他类型的软件，因此我们在本书中将不再进一步讨论它们。

处理冲突写入

多主节点复制的最大问题——无论是在地理分布的服务器端数据库中，还是在终端用户设备上的本地优先同步引擎中——是不同主节点上的并发写入可能导致需要解决的冲突。

例如，考虑一个同时被两个用户编辑的维基页面，如图 6-9 所示。用户 1 将页面标题从 A 更改为 B，而用户 2 独立地将标题从 A 更改为 C。每个用户的更改都成功应用于他们的本地主节点。然而，当这些更改被异步复制时，检测到冲突。这个问题在单主数据库中不会发生。

在“检测并发写入”中，我们将探讨数据库如何确定两个写入是否是并发的。现在我们假设可以检测到冲突，并希望找出解决冲突的最佳方法。

冲突避免

解决冲突的一种策略是避免它们的发生。例如，如果应用程序能够确保对特定记录的所有写入都通过同一个主节点进行，那么即使整个数据库是多主节点的，冲突也不会发生。在同步引擎客户端离线更新的情况下，这种方法是不可行的，但在地理复制的服务器系统中，有时是可能的²⁵。

例如，在一个用户只能编辑自己数据的应用程序中，可以确保来自特定用户的请求始终路由到同一区域，并使用该区域的主节点进行读写。不同的用户可能有不同的“主”区域（可能根据与用户的地理接近度来选择），但从任何一个用户的角度来看，配置本质上是单主节点的。

然而，有时您可能想要更改记录的指定主节点——可能是因为某个区域不可用，您需要将流量重新路由到另一个区域，或者因为用户已移动到不同的位置，现在更接近另一个区域。此时存在风险，即用户在指定主节点更改过程中执行写入操作，导致冲突，必须使用以下方法之一来解决。因此，如果允许更改主节点，冲突避免机制就会失效。

另一个冲突避免的例子：想象一下，您想插入新记录并基于自增计数器为它们生成唯一 ID。如果您有两个主节点，您可以将它们设置为一个主节点只生成奇数，另一个只生成偶数。这样，您可以确保两个主节点不会同时将相同的 ID 分配给不同的记录。或者，您可以使用通用唯一标识符（UUID）或分布式 ID 生成方案，例如 Snowflake³⁷。

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

如果无法避免冲突，解决冲突的最简单方法是为每次写入附加一个时间戳，并始终使用时间戳最大的值。例如，在图 6-9 中，假设用户 1 的写入时间戳大于用户 2 的写入时间戳。在这种情况下，两个主节点都会判断页面的新标题应该是 B，并且他们会丢弃将其设置为 C 的写入。如果写入恰好具有相同的时间戳，则可以通过比较值来选择赢家（例如，在字符串的情况下，选择字母表中较早的那个）。

这种方法被称为最后写入胜出（LWW），因为具有最大时间戳的写入可以被视为“最后”的写入。然而，这个术语具有误导性，因为当两个写入是并发的，如图 6-9 所示，哪个是较旧的，哪个是较新的并没有定义，因此并发写入的时间戳顺序本质上是随机的。

因此，LWW 的真正含义是：当同一条记录在不同的主节点上同时被写入时，会随机选择其中一个写入作为赢家，而其他写入则会被静默丢弃，即使它们在各自的主节点上成功处理。这实现了最终所有副本达到一致状态的目标，但代价是数据丢失。

如果你能避免冲突——例如，仅插入具有唯一键（如 UUID 或 Snowflake ID）的记录，并且从不更新它们——那么 LWW 就没有问题。但如果你更新现有记录，或者不同的主节点可能插入具有相同键的记录，那么你必须决定丢失更新是否对你的应用程序构成问题。如果丢失更新不可接受，你需要使用下面描述的冲突解决方法之一。

另一个与 LWW 相关的问题是，如果使用实时时钟（例如 Unix 时间戳）作为写入的时间戳，系统对时钟同步变得非常敏感。如果一个节点的时钟比其他节点快，而你试图覆盖该节点写入的值，你的写入可能会被忽略，因为它的时间戳可能较低，即使它显然发生在之后。这个问题可以通过使用逻辑时钟来解决，我们将在[链接即将到来]中讨论。

手动冲突解决

如果随机丢弃一些写入不是一个理想的选择，下一种选择是手动解决冲突。你可能对 Git 和其他版本控制系统中的手动冲突解决有所了解：如果两个不同分支上的提交编辑了同一文件的相同行，并且你尝试合并这些分支，你将会遇到一个合并冲突，需要在合并完成之前解决。

在数据库中，冲突不应阻止整个复制过程，直到有人解决它。因此，数据库通常会存储给定记录的所有并发写入值——例如，图 6-9 中的 B 和 C。这些值有时被称为兄弟值。下次查询该记录时，数据库会返回所有这些值，而不仅仅是最新的一个。然后，您可以以任何您想要的方式解决这些值，可以在应用程序代码中自动处理（例如，您可以将 B 和 C 连接成“B/C”），或者通过询问用户来解决。然后，您将一个新值写回数据库以解决冲突。

这种冲突解决方法在一些系统中使用，例如 CouchDB。然而，它也存在许多问题：

• 数据库的 API 发生了变化：例如，之前维基页面的标题只是一个字符串，现在变成了一组字符串，通常包含一个元素，但在发生冲突时可能包含多个元素。这可能使得在应用程序代码中处理数据变得尴尬。

• 要求用户手动合并兄弟项对应用开发者（需要构建冲突解决的用户界面）和用户（可能对他们被要求做什么以及为什么感到困惑）来说都是一项繁重的工作。在许多情况下，自动合并比打扰用户要好。

• 如果不小心，自动合并兄弟项可能会导致意想不到的行为。例如，亚马逊的购物车曾允许并发更新，然后通过保留出现在任何兄弟项中的所有购物车商品来合并（即，取购物车的集合并）。这意味着如果客户在一个兄弟项中从购物车中移除了一个商品，但另一个兄弟项仍然包含那个旧商品，那么被移除的商品会意外地重新出现在客户的购物车中³⁸。图 6-10 展示了一个例子，其中设备 1 从购物车中移除了书籍，而设备 2 同时移除了 DVD，但在合并冲突后，这两个商品都重新出现。

如果多个节点观察到冲突并同时解决它，冲突解决过程本身可能会引入新的冲突。这些解决方案甚至可能不一致：例如，如果不小心按顺序处理，一个节点可能将 B 和 C 合并为 “B/C”，而另一个节点可能将它们合并为 “C/B”。当 “B/C” 和 “C/B” 之间的冲突被合并时，可能会导致 “B/C/C/B” 或其他类似令人惊讶的结果。

自动冲突解决

对于许多应用程序，处理冲突的最佳方法是使用一种算法，自动将并发写入合并为一致的状态。自动冲突解决确保所有副本收敛到相同的状态——即，所有处理相同写入集的副本具有相同的状态，无论写入到达的顺序如何。

LWW 是一个简单的冲突解决算法示例。为了不同类型的数据，已经开发出更复杂的合并算法，旨在尽可能保留所有更新的预期效果，从而避免数据丢失：

• 如果数据是文本（例如，维基页面的标题或正文），我们可以检测从一个版本到下一个版本插入或删除了哪些字符。合并结果将保留任何兄弟节点中所做的所有插入和删除。如果用户在同一位置同时插入文本，可以以确定性方式进行排序，以便所有节点获得相同的合并结果。

• 如果数据是一组项目（像待办事项列表那样有序，或像购物车那样无序），我们可以通过跟踪插入和删除来类似于文本进行合并。为了避免图 6-10 中的购物车问题，算法跟踪了书籍和 DVD 被删除的事实，因此合并结果为 Cart = {Soap}。

• 如果数据是一个表示计数器的整数，可以递增或递减（例如，社交媒体帖子上的点赞数），合并算法可以知道每个兄弟节点上发生了多少次递增和递减，并正确地将它们加在一起，以确保结果不会重复计算，也不会丢失更新。

• 如果数据是一个键值映射，我们可以通过对该键下的值应用其他冲突解决算法来合并对同一键的更新。对不同键的更新可以相互独立地处理。

冲突解决的可能性是有限的。例如，如果您想强制列表中不超过五个项目，而多个用户同时向列表中添加项目，导致总数超过五个，您唯一的选择就是丢弃一些项目。尽管如此，自动冲突解决足以构建许多有用的应用程序。如果您从构建一个协作的离线优先或本地优先应用程序的需求出发，那么冲突解决是不可避免的，自动化通常是最佳方法。

CRDTs 和操作转换

两类算法通常用于实现自动冲突解决：无冲突复制数据类型（CRDTs）³⁹ 和操作转换（OT）⁴⁰。它们具有不同的设计理念和性能特征，但都能够对上述所有类型的数据执行自动合并。

图 6-11 展示了 OT 和 CRDT 如何合并对文本的并发更新的示例。假设你有两个副本，它们都以文本“ice”开始。一个副本在前面添加字母“n”，变成“nice”，而另一个副本则同时在后面添加感叹号，变成“ice!”。

这两种算法以不同的方式实现合并结果“nice!”：

OT

我们记录字符插入或删除的索引：“n”在索引 0 处插入，“!”在索引 3 处插入。接下来，副本交换它们的操作。在索引 0 处插入“n”可以直接应用，但如果将索引 3 处的“!”插入应用于状态“nice”，我们会得到“nic!e”，这是不正确的。因此，我们需要转换每个操作的索引，以考虑已经应用的并发操作；在这种情况下，“!”的插入被转换为索引 4，以考虑在早期索引处插入的“n”。

CRDT

大多数 CRDT 为每个字符分配一个唯一的、不可变的 ID，并使用这些 ID 来确定插入/删除的位置，而不是使用索引。例如，在图 6-11 中，我们将 ID 1A 分配给“i”，将 ID 2A 分配给“c”，等等。当插入感叹号时，我们生成一个操作，其中包含新字符的 ID（4B）和我们希望插入的现有字符的 ID（3A）。要在字符串的开头插入，我们将“nil”作为前一个字符的 ID。对同一位置的并发插入按字符的 ID 进行排序。这确保了副本在不进行任何转换的情况下收敛。

基于这些思想的变体有许多算法。列表/数组可以类似地支持，使用列表元素而不是字符，其他数据类型如键值映射也可以很容易地添加。OT 和 CRDT 之间存在一些性能和功能的权衡，但可以在一个算法中结合 CRDT 和 OT 的优点⁴¹。

OT 最常用于文本的实时协作编辑，例如在 Google Docs 中²⁶，而 CRDT 则可以在分布式数据库中找到，如 Redis Enterprise、Riak 和 Azure Cosmos DB⁴²。JSON 数据的同步引擎可以使用 CRDT（例如，Automerge 或 Yjs）和 OT（例如，ShareDB）来实现。

什么是冲突？

某些类型的冲突是显而易见的。在图 6-9 的示例中，两个写操作同时修改了同一记录中的同一字段，将其设置为两个不同的值。毫无疑问，这就是一个冲突。

其他类型的冲突可能更难以检测。例如，考虑一个会议室预订系统：它跟踪哪个房间在什么时间被哪个团体预订。该应用程序需要确保每个房间在任何时候只能被一个团体预订（即，同一房间不能有重叠的预订）。在这种情况下，如果在同一时间为同一房间创建了两个不同的预订，就可能会出现冲突。即使应用程序在允许用户进行预订之前检查可用性，如果两个预订是在两个不同的主节点上进行的，也可能会发生冲突。

没有快速现成的答案，但在接下来的章节中，我们将探讨通向对这个问题良好理解的路径。我们将在第 8 章看到更多冲突的例子，在[链接即将到来]中，我们将讨论在复制系统中检测和解决冲突的可扩展方法。

无主节点复制

我们在本章中讨论的复制方法——单主节点和多主节点复制——基于这样的理念：客户端将写请求发送到一个节点（主节点），数据库系统负责将该写操作复制到其他副本。主节点确定写操作应处理的顺序，跟随者按照相同的顺序应用主节点的写操作。

一些数据存储系统采取了不同的方法，放弃了主节点的概念，允许任何副本直接接受来自客户端的写入。一些最早的复制数据系统是无主节点的⁴³⁴⁴，但在关系数据库主导的时代，这一理念大多被遗忘。2007 年，亚马逊在其内部的 Dynamo 系统中使用了这一理念，使其再次成为数据库的流行架构³⁸。Riak、Cassandra 和 ScyllaDB 是受 Dynamo 启发的无主节点复制模型的开源数据存储，因此这种数据库也被称为 Dynamo 风格。

在一些无主节点的实现中，客户端直接将写入请求发送到多个副本，而在其他情况下，协调节点代表客户端执行此操作。然而，与主节点数据库不同的是，该协调节点并不强制执行写入的特定顺序。正如我们将看到的，这种设计上的差异对数据库的使用方式产生了深远的影响。

当节点宕机时写入数据库

想象一下，你有一个包含三个副本的数据库，其中一个副本当前不可用——可能是因为正在重启以安装系统更新。在单主节点配置中，如果你想继续处理写入请求，可能需要进行故障转移（参见“处理节点故障”）。

另一方面，在无主节点配置中，故障转移不存在。图 6-12 展示了发生的情况：客户端（用户 1234）并行地将写入请求发送给所有三个副本，两个可用副本接受了写入请求，但不可用副本错过了该请求。假设三个副本中只需两个确认写入即可：在用户 1234 收到两个确认响应后，我们认为写入成功。客户端简单地忽略了一个副本错过写入的事实。

现在想象一下，那个不可用的节点重新上线，客户端开始从它那里读取。在节点宕机期间发生的任何写入在该节点上都是缺失的。因此，如果你从该节点读取，可能会得到过时的（陈旧的）值作为响应。

为了解决这个问题，当客户端从数据库读取时，它不仅仅将请求发送给一个副本：读取请求还会并行发送到多个节点。客户端可能会从不同的节点获得不同的响应；例如，从一个节点获得最新值，而从另一个节点获得过时值。

为了判断哪些响应是最新的，哪些是过时的，每个写入的值都需要标记版本号或时间戳，类似于我们在“最后写入胜出（丢弃并发写入）”中看到的。当客户端在读取时收到多个值时，它会使用时间戳最大的那个值（即使该值仅由一个副本返回，而其他几个副本返回的是较旧的值）。有关更多详细信息，请参见“检测并发写入”。

赶上错过的写入

复制系统应确保最终所有数据都复制到每个副本。在一个不可用的节点重新上线后，它如何赶上错过的写入？在 Dynamo 风格的数据存储中使用了几种机制：

读取修复

当客户端从多个节点并行读取时，它可以检测到任何过时的响应。例如，在图 6-12 中，用户 2345 从副本 3 获取了版本 6 的值，从副本 1 和副本 2 获取了版本 7 的值。客户端看到副本 3 有一个过时的值，并将更新的值写回该副本。这种方法对于经常被读取的值效果很好。

提示转交

如果一个副本不可用，另一个副本可以以提示的形式代表其存储写入。当原本应该接收这些写入的副本恢复后，存储提示的副本将其发送给恢复的副本，然后删除这些提示。这个转交过程有助于使副本保持最新，即使是那些从未被读取的值，因此不受读取修复的处理。

反熵

此外，还有一个后台进程定期检查副本之间数据的差异，并将任何缺失的数据从一个副本复制到另一个副本。与基于主节点的复制中的复制日志不同，这个反熵过程并不按照特定顺序复制写入，并且在数据被复制之前可能会有显著的延迟。

读取和写入的法定数

在图 6-12 的例子中，我们认为写入是成功的，即使它只在三个副本中的两个上处理。那么如果只有三个副本中的一个接受了写入呢？我们能将这个推得多远？

如果我们知道每个成功的写入保证至少在三个副本中的两个上存在，这意味着最多只有一个副本可能是过时的。因此，如果我们从至少两个副本读取，我们可以确保这两个副本中的至少一个是最新的。如果第三个副本宕机或响应缓慢，读取仍然可以继续返回最新的值。

更一般地说，如果有 n 个副本，每次写入必须由 w 个节点确认才能被视为成功，并且我们必须查询至少 r 个节点以进行每次读取。（在我们的例子中，n = 3，w = 2，r = 2。）只要 w + r > n，我们期望在读取时获得最新的值，因为我们读取的 r 个节点中至少有一个必须是最新的。遵循这些 r 和 w 值的读取和写入被称为法定读取和写入⁴⁴。你可以将 r 和 w 看作是读取或写入有效所需的最小投票数。

在 Dynamo 风格的数据库中，参数 n、w 和 r 通常是可配置的。一个常见的选择是将 n 设置为奇数（通常为 3 或 5），并将 w = r = (n + 1) / 2（向上取整）。然而，你可以根据需要调整这些数字。例如，写入较少而读取较多的工作负载可能会从设置 w = n 和 r = 1 中受益。这使得读取更快，但缺点是仅一个节点故障就会导致所有数据库写入失败。

法定条件 $w + r > n$ 允许系统容忍不可用节点，具体如下：

• 如果 $w < n$，当一个节点不可用时，我们仍然可以处理写入。

• 如果 $r < n$，当一个节点不可用时，我们仍然可以处理读取。

• 当 $n = 3, w = 2, r = 2$ 时，我们可以容忍一个不可用节点，如图 6-12 所示。

• 当 $n = 5, w = 3, r = 3$ 时，我们可以容忍两个不可用节点。此情况在图 6-13 中进行了说明。

通常，读取和写入总是并行发送到所有 $n$ 个副本。参数 $w$ 和 $r$ 决定我们等待多少个节点——即，在我们认为读取或写入成功之前，需要有多少个 $n$ 节点报告成功。

如果可用的节点少于所需的 w 或 r 节点，写入或读取将返回错误。节点可能因多种原因不可用：因为节点宕机（崩溃、断电），由于执行操作时发生错误（无法写入因为磁盘已满），由于客户端与节点之间的网络中断，或出于其他多种原因。我们只关心节点是否返回了成功的响应，而不需要区分不同类型的故障。

法定一致性的局限性

如果你有 n 个副本，并且选择 w 和 r 使得 w + r > n，通常可以期望每次读取都返回某个键的最新值。这是因为你写入的节点集合和你读取的节点集合必须重叠。也就是说，在你读取的节点中，必须至少有一个节点具有最新的值（如图 6-13 所示）。

通常，r 和 w 被选择为大多数（超过 n/2）节点，因为这确保了 w + r > n，同时仍然可以容忍多达 n/2（向下取整）个节点故障。但法定人数不一定是大多数——只要读写操作使用的节点集合至少有一个节点重叠就可以。其他法定人数的分配也是可能的，这为分布式算法的设计提供了一些灵活性⁴⁵。

您也可以将 w 和 r 设置为较小的数字，以便 w + r ≤ n（即法定人数条件不满足）。在这种情况下，读写操作仍将发送到 n 个节点，但成功响应的数量要求较少，操作仍然可以成功。

使用较小的 w 和 r，您更有可能读取到过时的值，因为您的读取操作更可能没有包含最新值的节点。好的一面是，这种配置允许更低的延迟和更高的可用性：如果发生网络中断并且许多副本变得不可访问，您仍然有更高的机会继续处理读取和写入。只有当可访问的副本数量降到 w 或 r 以下时，数据库才会分别变得不可用于写入或读取。

然而，即使 w + r > n，仍然存在一些边缘情况，使得一致性属性可能会令人困惑。一些场景包括：

• 如果一个携带新值的节点发生故障，并且其数据从一个携带旧值的副本恢复，则存储新值的副本数量可能会降到 w 以下，从而破坏法定条件。

• 在重新平衡进行中（某些数据从一个节点移动到另一个节点，见第 7 章），节点可能对哪些节点应该持有特定值的 n 个副本有不一致的看法。这可能导致读取和写入法定不再重叠。

• 如果读取操作与写入操作并发进行，读取可能会看到或不看到并发写入的值。特别是，可能会出现一个读取看到新值，而后续读取看到旧值的情况，正如我们将在[链接待补充]中看到的。

• 如果某些副本上的写入成功而在其他副本上失败（例如，因为某些节点的磁盘已满），并且总体上在少于 w 个副本上成功，则在成功的副本上不会回滚。这意味着如果写入被报告为失败，后续读取可能会或可能不会返回该写入的值⁴⁶。

• 如果数据库使用来自实时时钟的时间戳来确定哪个写入是更新的（例如 Cassandra 和 ScyllaDB），如果另一个时钟更快的节点已写入同一键，则写入可能会被静默丢弃——这是我们之前在“最后写入胜出（丢弃并发写入）”中看到的问题。我们将在[链接待补充]中更详细地讨论这一点。

• 如果两个写操作同时发生，其中一个可能在一个副本上先被处理，而另一个可能在另一个副本上先被处理。这会导致冲突，类似于我们在多主节点复制中看到的情况（参见“处理冲突写入”）。我们将在“检测并发写入”中回到这个话题。

因此，尽管法定人数似乎保证读取返回最新写入的值，但实际上并非如此简单。Dynamo 风格的数据库通常针对可以容忍最终一致性的用例进行优化。参数 w 和 r 允许您调整读取过时值的概率⁴⁷，但明智的做法是不要将它们视为绝对保证。

监控数据陈旧性

从操作的角度来看，监控您的数据库是否返回最新结果是很重要的。即使您的应用程序可以容忍过时读取，您也需要关注复制的健康状况。如果它显著落后，应该提醒您以便您可以调查原因（例如，网络问题或节点过载）。

对于基于主节点的复制，数据库通常会暴露复制延迟的指标，您可以将其输入到监控系统中。这是可能的，因为写入操作是按照相同的顺序应用于主节点和跟随者的，并且每个节点在复制日志中都有一个位置（它在本地应用的写入数量）。通过将跟随者的当前位置信息减去主节点的当前位置，您可以测量复制延迟的量。

然而，在无主节点复制的系统中，写入操作没有固定的应用顺序，这使得监控变得更加困难。副本为交接存储的提示数量可以作为系统健康状况的一种衡量标准，但很难进行有用的解释⁴⁸。最终一致性是一个故意模糊的保证，但为了可操作性，能够量化“最终”是很重要的。

单主节点复制与无主复制性能

基于单一主节点的复制系统可以提供强一致性保证，而这些保证在无主节点系统中是难以或不可能实现的。然而，正如我们在“复制延迟的问题”中看到的，在基于主节点的复制系统中，如果在异步更新的跟随者上进行读取，也可能返回过时的值。

从主节点读取可以确保最新的响应，但它存在性能问题：

• 读取吞吐量受限于主节点处理请求的能力（与读取扩展相对，后者将读取分散到可能返回过时值的异步更新副本上）。

• 如果主节点发生故障，您必须等待故障被检测到，并在故障转移完成后才能继续处理请求。即使故障转移过程非常快速，用户也会注意到，因为响应时间会暂时增加；如果故障转移耗时较长，系统在此期间将不可用。

• 系统对主节点的性能问题非常敏感：如果主节点响应缓慢，例如由于过载或某些资源争用，增加的响应时间会立即影响用户。

无主节点架构的一个大优势是它对这些问题更具弹性。因为没有故障转移，并且请求无论如何都会并行发送到多个副本，所以一个副本变得缓慢或不可用对响应时间几乎没有影响：客户端只需使用其他响应更快的副本的响应。使用最快的响应被称为请求对冲，它可以显著减少尾部延迟⁴⁹）。

一个无主节点系统的韧性核心在于它不区分正常情况和故障情况。这在处理所谓的灰色故障时尤其有用，在这种情况下，一个节点并没有完全宕机，而是处于一种降级状态，处理请求的速度异常缓慢⁵⁰，或者当一个节点仅仅是过载时（例如，如果一个节点已经离线一段时间，通过提示转交进行恢复可能会造成额外的负载）。基于主节点的系统必须决定情况是否严重到需要故障转移（这本身可能会导致进一步的干扰），而在无主节点系统中，这个问题根本不会出现。

尽管如此，无主节点系统也可能存在性能问题：

• 即使系统不需要执行故障转移，一个副本仍然需要检测另一个副本何时不可用，以便它可以存储关于不可用副本错过的写入的提示。当不可用的副本恢复时，转交过程需要将这些提示发送给它。这在系统已经承受压力的时候给副本带来了额外的负载⁴⁸。

• 副本越多，法定人数的规模就越大，完成请求之前需要等待的响应也就越多。即使你只等待最快的 r 或 w 副本的响应，并且即使你并行发出请求，增大的 r 或 w 也会增加你遇到慢副本的机会，从而增加整体响应时间（参见“响应时间指标的使用”）。

• 大规模的网络中断可能会使客户端与大量副本断开连接，从而无法形成法定人数。一些无主节点数据库提供了一个配置选项，允许任何可达的副本接受写入，即使它不是该键的常规副本之一（Riak 和 Dynamo 称之为松散法定人数³⁸；Cassandra 和 ScyllaDB 称之为一致性级别 ANY）。虽然不能保证后续读取会看到写入的值，但根据应用的不同，这可能仍然比写入失败要好。

多主节点复制相比无主节点复制可以提供更强的网络中断韧性，因为读取和写入只需与一个主节点进行通信，而该主节点可以与客户端共存。然而，由于一个主节点上的写入是异步传播到其他主节点的，因此读取可能会任意过时。法定读取和写入提供了一种折衷方案：良好的容错能力，同时也有很高的读取最新数据的可能性。

多区域操作

我们之前讨论了跨区域复制作为多主节点复制的一个用例（见“多主节点复制”）。无主节点复制同样适合多区域操作，因为它被设计为能够容忍冲突的并发写入、网络中断和延迟峰值。

Cassandra 和 ScyllaDB 在正常的无主节点模型中实现了多区域支持：客户端将写入直接发送到所有区域的副本，您可以选择多种一致性级别，以确定请求成功所需的响应数量。例如，您可以请求跨所有区域的法定人数、每个区域的单独法定人数，或仅在客户端本地区域的法定人数。本地法定人数避免了等待其他区域慢请求的时间，但也更可能返回过时的结果。

Riak 保持客户端与数据库节点之间的所有通信局限于一个区域，因此 n 描述了一个区域内的副本数量。数据库集群之间的跨区域复制在后台异步进行，方式类似于多主节点复制。

检测并发写入

与多主节点复制一样，无主数据库允许对同一键进行并发写入，从而导致需要解决的冲突。这些冲突可能在写入发生时出现，但并不总是如此：它们也可能在后续的读取修复、提示转交或反熵过程中被检测到。

问题在于，由于网络延迟和部分故障的变化，事件可能以不同的顺序到达不同的节点。例如，图 6-14 显示了两个客户端 A 和 B 同时向三节点数据存储中的键 X 写入数据：

• 节点 1 接收了来自 A 的写入，但由于暂时的故障，未能接收到来自 B 的写入。

• 节点 2 首先接收了来自 A 的写入，然后接收了来自 B 的写入。

• 节点 3 首先接收到来自 B 的写入，然后接收到来自 A 的写入。

如果每个节点在接收到来自客户端的写入请求时简单地覆盖某个键的值，节点将会永久不一致，如图 6-14 中的最终获取请求所示：节点 2 认为 X 的最终值是 B，而其他节点认为该值是 A。

为了最终达到一致性，副本应该趋向于相同的值。为此，我们可以使用之前在“处理冲突写入”中讨论的任何冲突解决机制，例如最后写入胜出（Cassandra 和 ScyllaDB 使用）、手动解决或 CRDT（在“CRDT 和操作转换”中描述，并由 Riak 使用）。

最后写入胜出很容易实现：每次写入都带有时间戳，时间戳较高的值总是会覆盖时间戳较低的值。然而，时间戳并不能告诉你两个值是否实际上存在冲突（即，它们是同时写入的）或没有冲突（它们是一个接一个写入的）。如果你想显式地解决冲突，系统需要更加小心地检测并发写入。

“发生在之前”的关系和并发

我们如何决定两个操作是否并发？为了培养直觉，让我们看一些例子：

• 在图 6-8 中，这两个写入不是并发的：A 的插入发生在 B 的增量之前，因为 B 增量的值是 A 插入的值。换句话说，B 的操作建立在 A 的操作之上，因此 B 的操作必须发生在后面。我们也说 B 在因果上依赖于 A。

• 另一方面，图 6-14 中的两个写操作是并发的：当每个客户端开始操作时，它并不知道另一个客户端也在对同一个键执行操作。因此，这些操作之间没有因果依赖关系。

如果操作 A 发生在操作 B 之前，则 B 知道 A，或依赖于 A，或以某种方式建立在 A 之上。一个操作是否发生在另一个操作之前是定义并发含义的关键。实际上，我们可以简单地说，如果两个操作都不发生在另一个操作之前（即，彼此都不知道对方），那么这两个操作就是并发的⁵¹。

因此，每当你有两个操作 A 和 B 时，有三种可能性：要么 A 发生在 B 之前，要么 B 发生在 A 之前，要么 A 和 B 是并发的。我们需要一个算法来告诉我们两个操作是否并发。如果一个操作发生在另一个操作之前，则后一个操作应该覆盖前一个操作，但如果操作是并发的，我们就会有一个需要解决的冲突。

捕获发生在前的关系

让我们来看一个算法，它确定两个操作是否是并发的，或者一个操作是否发生在另一个操作之前。为了简单起见，我们先从只有一个副本的数据库开始。一旦我们弄清楚如何在单个副本上做到这一点，我们就可以将这种方法推广到一个没有主节点的多个副本的数据库。

图 6-15 显示了两个客户端同时向同一个购物车添加商品。（如果这个例子让你觉得太无聊，可以想象两个空中交通管制员同时向他们正在跟踪的区域添加飞机。）最初，购物车是空的。在它们之间，客户端对数据库进行了五次写入：

1. 客户端 1 将 milk 添加到购物车。这是对该键的第一次写入，因此服务器成功地存储了它并将其分配为版本 1。服务器还将该值连同版本号回显给客户端。

2. 客户端 2 将 eggs 添加到购物车，而不知道客户端 1 同时添加了 milk （客户端 2 认为它的 eggs 是购物车中唯一的物品）。服务器将此写入分配为版本 2，并将 eggs 和 milk 存储为两个独立的值（兄弟）。然后，它将这两个值连同版本号 2 返回给客户端。

3. 客户端 1 对客户端 2 的写入毫不知情，想要将 flour 添加到购物车，因此它认为当前购物车的内容应该是 [milk, flour] 。它将该值发送给服务器，并附上服务器之前给客户端 1 的版本号 1。服务器可以从版本号判断 [milk, flour] 的写入优先于之前的值 [milk] ，但与 [eggs] 是并发的。因此，服务器将版本 3 分配给 [milk, flour] ，覆盖版本 1 的值 [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 中以图形方式进行了说明。箭头指示了哪个操作在另一个操作之前发生，从这个意义上说，后一个操作知道或依赖于前一个操作。在这个例子中，客户端从未完全与服务器上的数据保持同步，因为总是有其他操作同时进行。但旧版本的值最终会被覆盖，并且不会丢失任何写入。

请注意，服务器可以通过查看版本号来确定两个操作是否是并发的——它不需要解释值本身（因此值可以是任何数据结构）。算法的工作原理如下：

• 服务器为每个键维护一个版本号，每次写入该键时递增版本号，并将新版本号与写入的值一起存储。

• 当客户端读取一个键时，服务器返回所有兄弟项，即所有未被覆盖的值，以及最新的版本号。客户端必须在写入之前读取一个键。

• 当客户端写入一个键时，必须包含先前读取的版本号，并且必须将先前读取中收到的所有值合并在一起，例如使用 CRDT 或询问用户。写入请求的响应类似于读取，返回所有兄弟项，这使我们能够像购物车示例中那样链接多个写入。

当服务器接收到带有特定版本号的写入时，它可以覆盖所有具有该版本号或更低版本号的值（因为它知道这些值已合并为新值），但必须保留所有具有更高版本号的值（因为这些值与传入的写入是并发的）。

当写入包含先前读取的版本号时，这告诉我们该写入基于哪个先前状态。如果您在写入时不包含版本号，则它与所有其他写入是并发的，因此不会覆盖任何内容——它只会作为后续读取中的一个值返回。

版本向量

图 6-15 中的示例仅使用了一个副本。当有多个副本但没有主节点时，算法如何变化？

图 6-15 使用单一版本号来捕捉操作之间的依赖关系，但当有多个副本同时接受写入时，这并不足够。相反，我们需要为每个副本以及每个键使用一个版本号。每个副本在处理写入时会递增自己的版本号，并且还会跟踪它从其他副本看到的版本号。这些信息指示哪些值需要被覆盖，哪些值需要保留为兄弟。

所有副本的版本号集合称为版本向量⁵²。这个想法有几个变体在使用，但最有趣的可能是点状版本向量⁵³⁵⁴，它在 Riak 2.0 中使用⁵⁵⁵⁶。我们不会深入细节，但它的工作方式与我们在购物车示例中看到的非常相似。

如图 6-15 中的版本号所示，版本向量在读取值时从数据库副本发送到客户端，并在随后写入值时需要发送回数据库。（Riak 将版本向量编码为它称之为因果上下文的字符串。）版本向量使数据库能够区分覆盖写入和并发写入。

版本向量还确保从一个副本读取数据后再写回另一个副本是安全的。这样做可能会导致兄弟节点的产生，但只要兄弟节点正确合并，就不会丢失数据。

总结

在本章中，我们探讨了复制的问题。复制可以服务于多个目的：

高可用性

即使一台机器（或多台机器、一个区域，甚至整个地区）出现故障，系统仍然可以继续运行。

断开连接的操作

允许应用在网络中断时继续工作

延迟

将数据地理上靠近用户，以便用户可以更快地与之互动

可扩展性

能够处理比单台机器更高的读取量，通过在副本上执行读取

尽管这是一个简单的目标——在几台机器上保留相同数据的副本——但复制实际上是一个相当棘手的问题。它需要仔细考虑并发性以及所有可能出错的情况，并处理这些故障的后果。至少，我们需要处理不可用的节点和网络中断（这还不包括更隐蔽的故障类型，例如由于软件错误或硬件故障导致的静默数据损坏）。

我们讨论了三种主要的复制方法：

单主节点复制

客户端将所有写操作发送到单个节点（主节点），该节点将数据更改事件的流发送到其他副本（跟随者）。可以在任何副本上进行读取，但从跟随者读取的数据可能是过时的。

多主节点复制

客户端将每个写操作发送到多个主节点中的一个，任何主节点都可以接受写操作。主节点之间以及向任何跟随者节点发送数据更改事件的流。

无主复制

客户端将每次写入发送到多个节点，并从多个节点并行读取，以便检测和纠正数据过时的节点。

每种方法都有其优缺点。单主节点复制因其相对容易理解且提供强一致性而受到欢迎。多主节点和无主节点复制在存在故障节点、网络中断和延迟峰值时可能更具鲁棒性——但代价是需要冲突解决并提供较弱的一致性保证。

复制可以是同步的或异步的，这对系统在故障时的行为有深远的影响。尽管在系统运行顺利时，异步复制可以很快，但重要的是要弄清楚当复制延迟增加和服务器故障时会发生什么。如果一个主节点失败并且你将一个异步更新的跟随者提升为新的主节点，最近提交的数据可能会丢失。

我们观察了一些可能由复制延迟引起的奇怪现象，并讨论了一些在决定应用程序在复制延迟下应如何行为时有帮助的一致性模型：

写后读一致性

用户应该始终看到他们自己提交的数据。

单调读取

在用户看到某一时刻的数据后，他们不应该再看到某个早期时刻的数据。

一致前缀读取

用户应该看到在因果上合理的数据状态：例如，看到问题及其回复的正确顺序。

最后，我们讨论了多主和无主复制如何确保所有副本最终收敛到一致状态：通过使用版本向量或类似算法来检测哪些写入是并发的，并通过使用冲突解决算法（如 CRDT）来合并并发写入的值。最后写入胜出和手动冲突解决也是可能的。

本章假设每个副本都存储整个数据库的完整副本，这对于大型数据集来说是不现实的。在下一章中，我们将讨论分片，这允许每台机器仅存储数据的一个子集。

参考文献

Footnotes

1. Kenny Gryp. MySQL Terminology Updates. dev.mysql.com, July 2020. Archived at perma.cc/S62G-6RJ2 ↩

2. Oracle Corporation. Oracle (Active) Data Guard 19c: Real-Time Data Protection and Availability. White Paper, oracle.com, March 2019. Archived at perma.cc/P5ST-RPKE ↩

3. Microsoft. What is an Always On availability group? learn.microsoft.com, September 2024. Archived at perma.cc/ABH6-3MXF ↩

4. 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, and Akshat Vig. Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service. At USENIX Annual Technical Conference (ATC), July 2022. ↩ ↩²

5. 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, and Peter Mattis. CockroachDB: The Resilient Geo-Distributed SQL Database. At ACM SIGMOD International Conference on Management of Data (SIGMOD), pages 1493–1509, June 2020. doi:10.1145/3318464.3386134 ↩

6. 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, and Xin Tang. TiDB: a Raft-based HTAP database. Proceedings of the VLDB Endowment, volume 13, issue 12, pages 3072–3084. doi:10.14778/3415478.3415535 ↩

7. Mallory Knodel and Niels ten Oever. Terminology, Power, and Inclusive Language in Internet-Drafts and RFCs. IETF Internet-Draft, August 2023. Archived at perma.cc/5ZY9-725E ↩

8. Buck Hodges. Postmortem: VSTS 4 September 2018. devblogs.microsoft.com, September 2018. Archived at perma.cc/ZF5R-DYZS ↩

9. Gunnar Morling. Leader Election With S3 Conditional Writes. <www.morling.dev>, August 2024. Archived at perma.cc/7V2N-J78Y ↩

10. Stas Kelvich. Why does Neon use Paxos instead of Raft, and what’s the difference?. neon.tech, August 2022. Archived at perma.cc/SEZ4-2GXU ↩

11. Dimitri Fontaine. An introduction to the pg_auto_failover project. tapoueh.org, November 2021. Archived at perma.cc/3WH5-6BAF ↩

12. John Hugg. ‘All In’ with Determinism for Performance and Testing in Distributed Systems. At Strange Loop, September 2015. ↩

13. Hironobu Suzuki. The Internals of PostgreSQL. interdb.jp, 2017. ↩

14. Amit Kapila. WAL Internals of PostgreSQL. At PostgreSQL Conference (PGCon), May 2012. Archived at perma.cc/6225-3SUX ↩

15. Amit Kapila. Evolution of Logical Replication. amitkapila16.blogspot.com, September 2023. Archived at perma.cc/F9VX-JLER ↩

16. Aru Petchimuthu. Upgrade your Amazon RDS for PostgreSQL or Amazon Aurora PostgreSQL database, Part 2: Using the pglogical extension. aws.amazon.com, August 2021. Archived at perma.cc/RXT8-FS2T ↩

17. 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, and Peter Xie. Wormhole: Reliable Pub-Sub to Support Geo-Replicated Internet Services. At 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI), May 2015. ↩

18. Douglas B. Terry. Replicated Data Consistency Explained Through Baseball. Microsoft Research, Technical Report MSR-TR-2011-137, October 2011. Archived at perma.cc/F4KZ-AR38 ↩ ↩² ↩³

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

20. Werner Vogels. Eventually Consistent. ACM Queue, volume 6, issue 6, pages 14–19, October 2008. doi:10.1145/1466443.1466448 ↩

21. Simon Willison. Reply to: “My thoughts about Fly.io (so far) and other newish technology I’m getting into”. news.ycombinator.com, May 2022. Archived at perma.cc/ZRV4-WWV8 ↩

22. Nithin Tharakan. Scaling Bitbucket’s Database. atlassian.com, October 2020. Archived at perma.cc/JAB7-9FGX ↩

23. Terry Pratchett. Reaper Man: A Discworld Novel. Victor Gollancz, 1991. ISBN: 978-0-575-04979-6 ↩

24. Yaser Raja and Peter Celentano. PostgreSQL bi-directional replication using pglogical. aws.amazon.com, January 2022. Archived at <https://perma.cc/BUQ2-5QWN> ↩

25. Robert Hodges. If You Must Deploy Multi-Master Replication, Read This First. scale-out-blog.blogspot.com, April 2012. Archived at perma.cc/C2JN-F6Y8 ↩ ↩²

26. John Day-Richter. What’s Different About the New Google Docs: Making Collaboration Fast. drive.googleblog.com, September 2010. Archived at perma.cc/5TL8-TSJ2 ↩ ↩²

27. Evan Wallace. How Figma’s multiplayer technology works. figma.com, October 2019. Archived at perma.cc/L49H-LY4D ↩

28. Amr Saafan. Why Sync Engines Might Be the Future of Web Applications. nilebits.com, September 2024. Archived at perma.cc/5N73-5M3V ↩

29. Isaac Hagoel. Are Sync Engines The Future of Web Applications? dev.to, July 2024. Archived at perma.cc/R9HF-BKKL ↩

30. Alex Feyerke. Designing Offline-First Web Apps. alistapart.com, December 2013. Archived at perma.cc/WH7R-S2DS ↩

31. Martin Kleppmann, Adam Wiggins, Peter van Hardenberg, and Mark McGranaghan. Local-first software: You own your data, in spite of the cloud. At ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!), October 2019, pages 154–178. doi:10.1145/3359591.3359737 ↩

32. Martin Kleppmann. The past, present, and future of local-first. At Local-First Conference, May 2024. ↩

33. Conrad Hofmeyr. API Calling is to Sync Engines as jQuery is to React. powersync.com, November 2024. Archived at perma.cc/2FP9-7WJJ ↩

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

35. Leonard Kawell, Jr., Steven Beckhardt, Timothy Halvorsen, Raymond Ozzie, and Irene Greif. Replicated document management in a group communication system. At ACM Conference on Computer-Supported Cooperative Work (CSCW), September 1988. doi:10.1145/62266.1024798 ↩

36. Ricky Pusch. Explaining how fighting games use delay-based and rollback netcode. words.infil.net and arstechnica.com, October 2019. Archived at perma.cc/DE7W-RDJ8 ↩

37. Ryan King. Announcing Snowflake. blog.x.com, June 2010. Archived at archive.org ↩

38. Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon’s Highly Available Key-Value Store. At 21st ACM Symposium on Operating Systems Principles (SOSP), October 2007. doi:10.1145/1323293.1294281 ↩ ↩² ↩³ ↩⁴

39. Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. A Comprehensive Study of Convergent and Commutative Replicated Data Types. INRIA Research Report no. 7506, January 2011. ↩

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

41. Joseph Gentle and Martin Kleppmann. Collaborative Text Editing with Eg-walker: Better, Faster, Smaller. At 20th European Conference on Computer Systems (EuroSys), March 2025. doi:10.1145/3689031.3696076 ↩

42. Dharma Shukla. Azure Cosmos DB: Pushing the frontier of globally distributed databases. azure.microsoft.com, September 2018. Archived at perma.cc/UT3B-HH6R ↩

43. Bruce G. Lindsay, Patricia Griffiths Selinger, C. Galtieri, J.N. Gray, R.A. Lorie, T.G. Price, F. Putzolu, I.L. Traiger, and B.W. Wade. Notes on Distributed Databases. IBM Research, Research Report RJ2571(33471), July 1979. Archived at perma.cc/EPZ3-MHDD ↩

44. David K. Gifford. Weighted Voting for Replicated Data. At 7th ACM Symposium on Operating Systems Principles (SOSP), December 1979. doi:10.1145/800215.806583 ↩ ↩²

45. Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. Flexible Paxos: Quorum Intersection Revisited. At 20th International Conference on Principles of Distributed Systems (OPODIS), December 2016. doi:10.4230/LIPIcs.OPODIS.2016.25 ↩

46. Joseph Blomstedt. Bringing Consistency to Riak. At RICON West, October 2012. ↩

47. Peter Bailis, Shivaram Venkataraman, Michael J. Franklin, Joseph M. Hellerstein, and Ion Stoica. Quantifying eventual consistency with PBS. The VLDB Journal, volume 23, pages 279–302, April 2014. doi:10.1007/s00778-013-0330-1 ↩

48. Colin Breck. Shared-Nothing Architectures for Server Replication and Synchronization. blog.colinbreck.com, December 2019. Archived at perma.cc/48P3-J6CJ ↩ ↩²

49. Jeffrey Dean and 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 ↩

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

51. 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 ↩ ↩²

52. D. Stott Parker Jr., Gerald J. Popek, Gerard Rudisin, Allen Stoughton, Bruce J. Walker, Evelyn Walton, Johanna M. Chow, David Edwards, Stephen Kiser, and 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 ↩

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

54. Giridhar Manepalli. Clocks and Causality - Ordering Events in Distributed Systems. exhypothesi.com, November 2022. Archived at perma.cc/8REU-KVLQ ↩ ↩²

55. Sean Cribbs. A Brief History of Time in Riak. At RICON, October 2014. Archived at perma.cc/7U9P-6JFX ↩

56. Russell Brown. Vector Clocks Revisited Part 2: Dotted Version Vectors. riak.com, November 2015. Archived at perma.cc/96QP-W98R ↩

57. Carlos Baquero. Version Vectors Are Not Vector Clocks. haslab.wordpress.com, July 2011. Archived at perma.cc/7PNU-4AMG ↩