阅读记录——DDIA Ch6 副本

为什么多副本#

• 数据地理上靠近用户（降低访问延迟）
• 让系统在部分组件出现故障时仍能继续运行（提高可用性）
• 为了扩展能够处理读查询的机器数量（提高读吞吐量）

副本需靠考虑的问题，数据变动时的副本同步，数据同步的规模。

本章讨论了小规模数据集下的数据变动的副本问题。包括三种在节点间复制变化的算法系列：单主节点、多主节点和无主节点副本。几乎所有分布式数据库都使用这三种方法

复制的权衡，错误处理，同步异步。

单主节点副本#

单主节点的复制机制如下：

• 一个集群中的一个节点被视为主节点，主节点负责与客户端通信，写入数据。
• 其他节点被视为从节点，每当主节点写入时，将数据变更（以日志的形式）发布给所有从节点，从节点获主节点的变更日志来进行变更。
• 当客户端想要从数据库读取数据时，它可以查询任何主从节点。但是只能通过主节点进行写入。
• 如果对数据库进行分片，那么每个分片都有一个主节点
• 如果主节点宕机则会自动选举新的主节点

单主节点复制被非常广泛地使用。它是许多关系型数据库的内置特性，例如 PostgreSQL、MySQL、Oracle Data Guard 和 SQL Server 的 Always On 可用性组。它也用于一些文档数据库，如 MongoDB 和 DynamoDB、消息代理如 Kafka、复制块设备如 DRBD 以及一些网络文件系统。许多共识算法，如 Raft（用于 CockroachDB、TiDB、etcd 和 RabbitMQ 多数队列等）的复制，也是基于单主节点的

同步与异步复制#

一个无法变更的事实是，复制需要时间。因此会出现多个从节点数据不一致的情况。

因此这时候对于数据变更而言，主节点无法可能无法等待所有从节点复制完成的情况下就提前返回。最终 从所有节点的复制确认可能要长达几分钟。

同步复制的优点是，主从节点有着较高的数据一致性。如果主节点突然失效，我们可以确信数据仍然在从节点上可用。
但其缺点也是，如果同步从节点没有响应（因为它崩溃了，或者存在网络故障，或者出于任何其他原因），写入操作就无法处理。主节点必须阻止所有写入操作，并等待同步副本再次可用。

因此，保持所有从节点完全同步是不现实的：“任何一个节点的故障都会导致整个系统停顿”。

实践上，通常采取半同步方案，也就是保证其中一个从节点是同步的，而其他从节点是异步的。如果同步从节点不可用或响应缓慢，会将其中一个异步从节点变为同步。这保证了至少有两个节点的数据是最新的：一个是主节点，另一个是同步从节点。

部分系统中，多数（例如，5 个副本中的 3 个，包括主节点）副本同步更新，而剩余的少数副本则异步更新。

但是，部分情况下，也会配置为完全异步。这时候如果主节点发生故障且无法恢复，就会出现数据丢失。唯一的优点就是快..

节点变化，数量增减#

为了响应变化，从节点的数量可能会增加。这时候需要将数据从主节点复制到新的从节点。

仅仅将数据文件从一个节点复制到另一个节点通常是不够的：客户端不断地向数据库写入数据，数据总是在不断变化中，所以一个标准的文件复制会在不同时间看到数据库的不同部分。结果可能毫无意义。

你可以通过锁定数据库（使其无法写入）来使磁盘上的文件保持一致，但这会违背我们高可用的目标。幸运的是，通常可以在不造成停机的情况下设置一个从节点。从概念上讲，这个过程看起来是这样的：

• 在某个时间点对主节点进行一致性快照 —— 如果可能的话，不锁定整个数据库。大部分数据库都具备此功能，因为它也是备份所必需的。在某些情况下，需要使用第三方工具，例如用于 MySQL 的 Percona XtraBackup。
• 将快照复制到新的从节点。
• 从节点连接到主节点，并请求自快照创建以来所有数据变更。这要求快照与主节点的复制日志中的确切位置相关联。PostgreSQL 称其为日志序列号；MySQL 有两种机制，即二进制日志坐标和全局事务标识符（GTIDs）
• 当从快照开始处理完所有积压的数据变更后，我们就说它已经追上进度了。现在它可以继续处理领导节点发生的数据变更。

不同数据库的从节点设置方式略有不同，有的可以完全自动化，而有的则需要 SRE 自行配置。

可以将复制日志归档到 S3 服务中，连同对象存储中数据库的定期快照，这是一种实现数据库备份和灾难恢复的好方法，也可以用于从节点设置。

对象存储不仅可用于数据归档。许多数据库开始使用 S3 作为存储后端，为实时查询提供数据。将数据库数据存储在对象存储中有许多好处：

• 成本低，代价是略微高的延迟，用内存， SSD / NVMe 进行补足。
• 自带跨区、双区或多区复制，并具有极高的持久性保障，数据库还可以绕过跨区域网络费用。
• 可以使用对象存储的条件写入功能（本质上是一种 CAS 操作）实现事务和主节点选举。
• 将多个数据库的数据存储在同一个对象存储中可以简化数据集成，尤其是结合 Apache Parquet 和 Apache Iceberg 等开放格式时效果更佳。

这些优势通过将事务、领导选举和复制等责任转移到对象存储，极大地简化了数据库架构。

采用对象存储进行复制的系统必须权衡一些利弊。值得注意的是，对象存储的延迟远高于本地磁盘或 EBS 等虚拟块设备。许多云服务提供商还按 API 调用次数收费，这迫使系统批量读写以降低成本。这种批量处理进一步增加了延迟。此外，许多对象存储不提供标准的文件系统接口。这阻碍了缺乏对象存储集成的系统利用对象存储。像用户空间文件系统（FUSE）这样的接口允许运维人员将对象存储桶挂载为文件系统，应用程序可以在不知数据存储在对象存储上的情况下使用这些文件系统。然而，许多 FUSE 对象存储接口缺乏 POSIX 特性，如非顺序写入或符号链接，系统可能依赖这些特性。

不同的系统以不同方式处理这些权衡。

分层存储架构：
一些系统引入了分层存储架构，将不常访问的数据放在对象存储上，而将新数据或常访问的数据保存在 SSD、NVMe 等更快的存储设备上，甚至内存中。

其他系统将对象存储作为其主要的存储层，但使用单独的低延迟存储系统（如亚马逊的 EBS 或 Neon 的 Safekeepers [12]）来存储其 WAL。

最近，一些系统甚至采用了零磁盘架构（ZDA）。基于 ZDA 的系统将所有数据持久化到对象存储，并严格将磁盘和内存用于缓存。

这使得节点无需持久化状态，从而大大简化了操作。WarpStream、Confluent Freight、Buf 的 Bufstream 和 Redpanda Serverless 都是使用零磁盘架构构建的 Kafka 兼容系统。

几乎每个现代云数据仓库都采用了这种架构，TurboPuffer（一个向量搜索引擎）和 SlateDB（一个云原生的 LSM 存储引擎）也是如此。

节点故障#

系统中的任何节点都可能宕机，可能是由于故障意外发生，但同样可能是因为计划内的维护（例如，重启一台机器来安装内核安全补丁）。能够在不造成停机的情况下重启单个节点，对运维来说是一个巨大的优势。因此，我们的目标是尽管个别节点发生故障，整个系统仍能继续运行，并尽可能减小节点故障的影响。

从节点故障

每个 follower 在其本地磁盘上保存一份日志，记录从 leader 接收到的数据变更。如果 follower 崩溃并重启，或者 leader 与 follower 之间的网络暂时中断，follower 可以通过其日志轻松恢复，它知道故障发生前处理的最后一个事务。因此，follower 可以连接到 leader 并请求在它断开连接期间发生的数据变更。当它应用这些变更后，就追赶上 leader，并可以像之前一样继续接收数据变更流。

尽管 follower 恢复在概念上很简单，但在性能方面可能具有挑战性：如果数据库具有高写入吞吐量，或者 follower 离线时间较长，可能需要追赶大量写入。

在追赶过程中，需要恢复的从节点和提供数据的主节点都将承受高负载。

主节点可以在所有从节点都确认他们已处理完日志后删除自己的写日志，但如果一个从节点长时间不可用，主节点面临选择：要么保留日志直到从节点恢复并赶上（主节点有磁盘空间耗尽的风险），要么删除那个不可用从节点尚未确认的日志（在这种情况下，从节点将无法从日志中恢复，并在其回来时需要从备份中恢复）。

主节点故障

处理领导者故障更为复杂：需要将可用从节点中的一个提升为主节点，客户端需要重新配置以将写入发送到新的主节点，其他从节点需要开始从新的主节点者处消费数据变更。这个过程称为故障转移。

故障转移可以是手动进行的（管理员被通知领导者已失败并采取必要步骤来选择新的领导者），也可以是自动进行的。自动故障转移过程通常包括以下步骤：

1. 确定主节点已失效。可能发生许多问题：崩溃、断电、网络问题等。没有万无一失的检测方法，因此大多数系统会使用心跳机制来判断节点是否失效。
2. 选择新的主节点。可以是自发的选举过程，也可以说控制节点重新分配。最适合担任主节点的副本通常是拥有最多来自旧主节点的最新数据变更的副本（以最小化任何数据丢失）。通过共识算法让所有节点就新的主节点达成一致。
3. 重新配置系统以使用新的主节点。客户端需要进行合适的请求路由，将写请求发送到新的主节点。如果旧主节点恢复，它可能仍然认为自己是主节点，系统需要确保旧主节点成为从节点并认可新的主节点。
   故障转移充满了可能出错的事情：

• 如果使用异步复制，新领导者可能在它失败之前没有收到旧领导者所有的写入。如果前任领导者在新领导者被选出后重新加入集群，这些写入应该怎么办？在此期间，新领导者可能已经收到了冲突的写入。最常见的解决方案是简单地丢弃旧领导者的未复制写入，这意味着你认为已提交的写入实际上并没有持久化。
• 丢弃写入如果数据库外部的其他存储系统需要与数据库内容进行协调，则特别危险。例如，在 GitHub 的一次事件中 [14]，一个过时的 MySQL 从属节点被提升为领导者。数据库使用自动递增计数器为新行分配主键，但由于新领导者的计数器落后于旧领导者，它重用了旧领导者之前分配的一些主键。这些主键也被用于一个 Redis 存储中，因此主键的重用导致 MySQL 和 Redis 之间出现不一致，导致一些私有数据被错误地披露给用户。
• 在某些故障场景下，可能会出现两个节点都认为自己是主节点的情况，这种情况被称为脑裂，并且很危险：如果两个领导者都接受写入，并且没有解决冲突的流程（参见 “多领导者复制”），数据很可能丢失或损坏。作为一种安全措施，一些系统有一种机制，在检测到两个领导者时关闭一个节点。然而，如果这种机制设计不当，你可能会最终关闭两个节点 [15]。此外，还有一个风险，即当检测到脑裂并关闭旧节点时，可能已经太晚了，数据已经损坏。
• 在领导者被宣告死亡之前，合适的超时时间应该是多久？超时时间越长，在领导者失败的情况下，恢复时间也会越长。然而，如果超时时间太短，可能会导致不必要的故障转移。例如，一个临时的负载峰值可能导致某个节点的响应时间超过超时时间，或者网络故障可能导致数据包延迟。如果系统已经在处理高负载或网络问题时，不必要的故障转移很可能使情况变得更糟，而不是更好。

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

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

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

日志复制的实现#

基于语句的复制#

一般情况下，主节点会记录它执行的每一个写请求，并将日志发送给从节点。对于关系型数据库来说，这意味着每一个 INSERT 、 UPDATE 或 DELETE 语句都会被转发给跟随者，并且每个跟随者都会像收到来自客户端一样解析并执行该 SQL 语句。

存在一些明显的问题

• 语句中可能存在非确定性的函数调用（如 NOW()，RAND()）
• 语句效果强依赖于现有数据（如使用自增列），这要求强顺序
• 语句带有副作用（如触发器、存储过程、用户定义函数），这要求副作用是完全确定的

一种思路是绕过：

• 对语句改写，将非确定性的函数调用替换为调用结果。
• 完全记录状态

MySQL 5.1 前采用这种方案。这种方案非常紧凑。但如果语句中存在任何非确定性，MySQL 现在默认会切换到基于行的复制。

VoltDB 使用基于语句的复制，并通过要求事务具有确定性来使其安全

基于 WAL 的实现（Oracle、PostgreSQL）#

WAL 机制让修改可以重放，WAL 包含了将索引和堆恢复到一致状态所需的所有信息。

主节点将 WAL 复制一份发送给从节点，这样就可以构建完全一致的内容。

问题在于 WAL 记录的层次较低（比如包含哪些字节在哪些磁盘块中发生了变化），这使得复制与存储引擎紧密耦合。这往往要求主从节点采用一样的数据库版本。而在数据库版本变更时（存储格式改变时），这是有风险的。

这种限制不利于系统数据库升级，如果复制协议允许从节点使用比主节点更新的版本，这样就可以先升级从节点，执行故障转移，将其中一个升级的节点设为新的主节点，从而实现数据库的零停机升级。而如果复制协议不允许这种版本不匹配，那么这种升级就需要一定的停机时间。

基于行的日志实现#

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

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

• 对于插入的行，日志中包含所有列的新值。
• 对于被删除的行，日志中包含足够的信息来唯一标识被删除的行。通常这会是主键，但如果表中没有主键，则需要记录所有列的旧值。
• 对于被更新的行，日志中包含足够的信息来唯一标识被更新的行，以及所有列的新值（或者至少是所有已更改列的新值）。
  修改多行的事务会生成多个这样的日志记录，随后会生成一个指示事务已提交的记录。MySQL 除了 WAL 外，还维护一个单独的逻辑复制日志，称为 binlog。

PostgreSQL 通过将物理 WAL 解码为行插入/更新/删除事件来实现逻辑复制。

由于逻辑日志与存储引擎内部实现解耦，它更容易保持向后兼容性。

一种逻辑日志格式也更容易被外部应用程序解析。如果需要将数据库与外部系统集成，比如用于离线分析的数据仓库，或用于构建自定义索引和缓存就很有用。这种技术称为变更数据捕获。

副本延迟#

副本的另一个好处是能在地理上更靠近用户，降低延迟。

基于主节点的复制要求所有写入操作必须通过单个节点进行，而只读查询可以发送到任何副本。

对于读多写少的场景（这在在线服务中很常见），一种常见的选择是：一主多从。可以减轻主节点的负载。

在这种架构中，只需简单的添加从节点就可以大幅提升服务的处理能力。不过这种方案只适用于异步复制，如果尝试对所有从节点进行同步复制，单点故障或网络中断会使整个系统无法进行写操作。而且节点越多，某个节点宕机的可能性就越大，因此完全同步的配置会非常不可靠。

这种架构下，如果应用同时在主从节点进行同样的查询，结果可能不同，可能短暂的看到不一致的信息，这就是最终一致性。

许多 NoSQL DB 都采用最终一致性，异步复制的 RDBMS 也是如此。

最终一致性的 “最终” 含义模糊，一般情况下，从节点与主节点的落后距离没有限制，正常操作中，主从的延迟通常在 1 秒内，实践中难以察觉。但是在高负载或者网络问题下，延迟很容易增加到秒级或分钟级

在这样高的延迟下，最终一致性中短暂的不一致就成为了要解决的显著问题。

读取自己的写入#

许多应用程序允许用户提交一些数据，然后查看他们已提交的内容。这可能是一条客户数据库中的记录，或是一个讨论线程中的评论，或类似的其他内容。
当提交新数据时，必须将其发送给领导者，但在用户查看数据时，可以从跟随者那里读取。如果数据经常被查看但只偶尔被写入，这种情况尤其适用。

不一致的情况可能会导致如下问题：
用户写入数据后立刻查看数据（写主节点，读从节点），新写入的数据未到达从节点，从用户视角看，数据丢失（很容易进行再次提交）

可以采取的一个策略是保证读后写一致性，也称为读自己写的一致性。保证用户能够立马读到自己的写入。但其他用户的更新可能需要更晚的时间才能可见。

几种方案如下：

• 当读取用户可能已修改的内容时，从主节点 / 同步更新从节点读取；这需要有一种方法在不进行实际查询的情况下判断某项内容是否可能已被修改。例如，社交网络上的用户资料通常只能由资料所有者编辑，其他人无法编辑。因此，一个简单的规则是：始终从领导节点读取用户自己的资料，从从节点读取其他用户的资料。
• 如果应用程序中的大多数内容都可能被用户编辑，那么那种方法将不会有效，因为大多数内容都需要从主节点读取（从而抵消了读取扩展的好处）。在这种情况下，可以使用其他标准来决定是否从主节点读取。例如，跟踪最后一次更新的时间，在最后一次更新的一分钟内，让所有读取都从主节点查询。监控从节点的延迟，并阻止任何落后于主节点超过一分钟的从节点的查询。
• 客户端可以记住其最近一次写入的时间戳 —— 然后系统可以确保为该用户服务的所有从节点都能超过这个时间戳。如果一个副本没有足够更新，要么可以让另一个副本处理读取，要么让查询等待该副本追赶上。这个时间戳可以是逻辑时间戳（例如表示写入顺序的日志序列号），或者是实际系统时钟（在这种情况下，时钟同步变得至关重要）。
• 如果副本分布在不同的区域（为了靠近用户或为了可用性），那么就会增加额外的复杂性。任何需要由主节点处理的请求都必须被路由到包含主节点的区域。

当同一用户从多个设备访问您的服务时，例如桌面网页浏览器和移动应用程序，就会产生另一个复杂问题。在这种情况下，需要提供跨设备的读后写一致性，一个设备上的更改能立马在另外一个设备上反映。

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

• 用户的最新更新时间这样的元数据不再能放在单一客户端，需要放在服务端管理。
• 如果副本跨区域，不同设备可能路由到不同的区域。如果特定方法需要从主节点读取数据，可能首先需要将所有用户的设备请求路由到同一个区域。

同一个区域内延迟低、速度快。要避免单区域故障，必须部署在多区域内，代价是高延迟、低吞吐量、高成本。

单调读#

第二个关于从异步从节点读取时可能出现的异常的例子用户可能会看到事情在时间上后移。

这种情况可能发生在用户从不同的副本进行多次读取时。例如，图 6-4 展示了用户 2345 对同一个查询进行了两次，第一次向延迟较小的副本发起，第二次向延迟较大的副本发起。（如果用户刷新网页，并且每次请求被随机路由到不同的服务器，这种情况很可能会发生。）

第一次查询返回了用户 1234 最近添加的评论，但第二次查询什么也没返回，因为延迟较大的副本尚未同步最新写入。

实际上，第二次查询观察到的系统状态比第一次查询早。

为了防止这种情况下出现，我们需要一种介于强一致性与最终一致性之间的一致性保证，称为单调读。
当你读取数据时，可能会看到一个旧值；单调读意味着如果某个用户依次进行多次读取，在读取了新数据之后，他们不会读取到更旧的数据。

一种思路是确保每个用户始终从同一个副本读取（不同用户可以从不同的副本读取）。例如，副本可以根据用户 ID 的哈希来选择。但当副本失效时，用户的查询需要被重新路由到另一个副本。

一致性前缀读取#

第三个副本延迟异常示例涉及因果关系的违反。

想象一下以下 Mr. Poons 和 Mrs. Cake 之间的简短对话：

• Mr. Poons：Mrs. Cake，你能看到多远的未来？
• Mrs. Cake：通常需要大约十秒钟，普恩斯先生。

这两句话之间存在因果关系：蛋糕夫人听到了普恩斯先生的问题并回答了它。

现在，想象一个第三方通过关注者来监听这场对话。Mrs. Cake说的话通过关注者几乎没有延迟，但Mr. Poons 说的话则有较长的复制延迟（见图 6-5）。这位观察者会听到如下内容：

• Mrs. Cake：通常需要大约十秒钟，普恩斯先生。
• Mr. Poons：Mrs. Cake，你能看到多远的未来？
  在观察者看来，Mrs. Cake似乎在Mr. Poons问出问题之前就已经回答。

防止这类异常需要另一种类型的保证：一致前缀读取。这种保证规定，如果一系列写入操作按特定顺序发生，那么用户读取时会看到它们以相同顺序写入的结果。

这在分片（分区）数据库中是一个特别的问题，我们将在第 7 章中讨论。如果数据库始终以相同的顺序应用写入操作，读取操作总是看到一个一致的前缀，因此这种异常不会发生。

但在许多分布式数据库中，不同的分片独立运行，因此写入操作没有确定的全局顺序：当用户从数据库读取时，他们可能会看到数据库的部分内容处于较旧状态，而另一部分处于较新状态。

一种解决方案是确保任何具有因果关系的写入操作都写入同一个分片 —— 但在某些应用中无法高效实现。还有一些算法明确跟踪因果依赖关系，这个话题我们将在 “'happens-before' 关系与并发” 中再次讨论。

解决复制延迟问题#

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

如前所述，应用程序可以通过在主节点或同步更新的从节点上执行某些类型的读取来提供比底层数据库更强的一致性保证。但在应用层中处理这些问题既复杂又容易出错。

对应用开发者来说，最简单的编程模型是选择一个为副本提供强一致性保证的数据库，例如串行化和 ACID 事务。这样就可以直接无视副本带来的问题。

在 2010 年代初，NoSQL 运动推广了这样一种观点，即这些功能限制了可扩展性，而大规模系统必须拥抱最终一致性。

一些 NewSQL 同时提供事务与强一致性，同时兼具分布式特性，但部分应用仍可出于别的考虑选择弱一致性（如开销，网络中断的弹性）

多主复制#

单主节点的明显缺点是所有写入操作都必须通过唯一的主节点进行。如果与主节点的连接中断，就无法写入。

一种很自然的拓展是允许多个节点接受写入。
仍然以相同的方式进行复制：每个处理写入的节点都必须将数据变更转发给所有其他节点。这种情况下，每个主节点与其他主节点互为主从。

与单主节点复制一样，可以选择同步或异步。
假设有 A，B 两个主节点。尝试写入 A，若 A / B 是同步复制，那么在 AB 连接中断时，外部就无法写入 A。
同步多主节点复制模型类似于单主节点复制模型，即如果 A / B 均为主节点，A 只需将所有写入请求转发给 B 执行。

地理分布式操作#

在单区域内使用多主节点意义不大，复杂性的增长往往不敌其能带来的好处。但在某些情况下，这种配置是合理的。

假设一个数据库，在多区域有副本（为了低延迟、高可用，也就是 geo 分布式）。在单主节点复制中，主节点必须位于其中一个区域，所有写入操作都必须通过该区域进行。

在多主节点中，每个区域可以有一个主节点。

区域内使用常规的主从复制，区域间主节点将更改复制给其他区的主节点。

在多区部署的情况下，单主节点与多主节点对比

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

由于多主复制在许多数据库中是一个相对后发的功能，因此往往存在一些微妙的配置陷阱以及与其他数据库功能的不兼容。如自增键、触发器和完整性约束可能会出现问题。因此，多主复制通常被视为危险地带，可能的话应尽量避免。

多主复制拓扑结构#

复制拓扑描述了写操作从一台节点传播到另一台节点的通信路径。如果你有两个主节点，那就只有一个合理的拓扑：主节点 1 必须将其所有写操作发送给主节点 2，反之亦然。

当有多于两个主节点时，有多种可能的拓扑。

• 全连接拓扑，每个主节点向所有其他主节点发送其写入数据。
• 环形拓扑，每个主节点只从一个主节点接受写入，然后转发向下一个主节点，构成一个环。
• 星形拓扑，一个指定的中心主节点将写入数据转发给所有其他节点。可进一步推广为树形拓扑

在环形和星型拓扑中，一个写操作可能需要经过多个节点才能到达所有副本。因此，节点需要转发它们从其他节点接收到的数据变更。

为了防止转发循环，每个节点都被分配了一个唯一标识符，在复制日志中，每个写操作都会被标记上它所经过的所有节点的标识符。当一个节点接收到一个带有自身标识符的数据变更时，该数据变更会被忽略。

环形和星形拓扑结构的问题在于，如果单个节点发生故障，可能会中断其他节点间的通信。
在大多数情况下，可能需要手动重新配置拓扑结构绕过故障节点。
连接更密集的拓扑结构（如全连接）具有更好的容错能力，因为消息可以通过不同的路径传输，避免了单点故障。

但全连接的问题在于某些网络链路可能比其他链路更快，导致部分复制消息可能会 “超过” 其他消息先到达目标节点。

在图 6-8 中，客户端 A 向主节点 1 的表中插入一行，一段时间后而客户端 B 在主节点 3 上更新该行。但主节点 2，可能先接收到 B 的更新事件，然后再接收到 A 的插入事件。

这是一个因果关系问题，类似于我们在 “一致性前缀读取” 中看到的问题：更新依赖于先前的插入，因此我们需要确保所有节点先处理插入操作，然后再处理更新操作。仅仅给每个写入操作附加时间戳是不够的，因为时钟无法保证足够同步以满足主节点 2 上的这些事件维持正确顺序。

为了正确排序这些事件，可以使用一种称为版本向量（version vectors）的技术。但许多多主复制系统没有使用良好的更新排序技术，所以会存在上面所述的问题，请务必仔细测试。

同步引擎和本地优先软件#

多主复制适用的另一种场景是离线应用，比如能够离线操作的在线编辑器、设备上的日历应用。

在离线状态下进行的更改，需要能在设备下次上线时与服务器和其他设备同步。

在这种情况下，每台设备都有一个充当主节点的本地数据库副本（接受写请求），并且在多设备上存在一个异步多主节点复制过程（sync）。复制延迟可能长达数小时甚至数天。

从架构角度来看，这种设置与跨区主节点复制非常相似，只是被推向了极致：每个设备都是一个 “区域”，而它们之间的网络连接极不可靠。

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

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

这也是多主节点架构：每个打开共享文件的 tab 页都是一个副本，你对文件的任何更新都会异步复制到打开相同文件的其他用户的设备上。

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

这样的功能称为同步引擎。允许用户在离线状态下继续编辑文件的应用（可能使用同步引擎实现）称为离线优先。术语本地优先软件指的是不仅离线优先，而且即使开发该软件的开发者关闭所有在线服务也能继续工作的协作应用。这可以通过使用具有开放标准同步协议的同步引擎实现，该协议有多个服务提供商可用。例如，Git 是一个本地优先的协作系统（尽管它不支持实时协作），因为你可以通过 GitHub、GitLab 或其他任何代码托管服务进行同步。

同步引擎的优缺点#

当今构建网络应用的主要方式是在客户端保持极少的持久状态，需要显示新数据或更新数据时依赖向服务器发起请求。相比之下，使用同步引擎时，客户端拥有持久状态，而与服务器之间的通信则被移入后台进程。同步引擎具有许多优势：

• 数据本地化意味着用户界面可以更快响应。

• 允许离线操作，应用不再需要单独的离线模式。

• 简化了前端应用的编程模型。在进行 RPC 调用时需要错误处理，而本地数据不需要进行 RPC，都是函数调用，同步引擎集中进行 RPC，可以将错误处理集中化。

• 为了实时显示其他用户的编辑内容，客户端需要接收这些更新并相应地展示在用户界面上。结合同步引擎和响应式编程模型是实现这一功能的好方法。

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

同步引擎由 Lotus Notes 在 20 世纪 80 年代首创（当时并未使用该术语），而特定应用（如日历）的同步功能也早已存在。如今存在多种通用同步引擎，其中一些使用专有后端服务（例如 Google Firestore、Realm 或 Ditto），另一些则采用开源后端，适合用于创建以本地优先的软件（例如 PouchDB / CouchDB、Automerge 或 Yjs）。

多人游戏也需要对用户操作进行协调。在游戏开发术语中，同步引擎的对应物称为netcode。但 netcode中使用的技术与游戏领域耦合较深，不能直接应用于其他类型的软件。

处理冲突写入#

多主复制最大的问题是不同主节点的并发写入会导致冲突，需要解决这些冲突。

冲突避免#

一种解决冲突的策略是避免冲突发生。例如，如果应用可以确保特定记录的所有写入都通过同一个领导者进行，那么即使整个数据库是多主节点模式也不会冲突。但这种方法在同步引擎客户端离线更新时不可行，但在多副本服务器系统中有时是可行的。

例如，在一个用户只能编辑自己数据的应用中，可以确保来自特定用户的请求始终被路由到同一个区域，并使用该区域的主节点进行读写操作。不同的用户可能有不同的 “home” 区域（可能基于用户地理位置选择），但从单用户的角度来看，这是一种单主节点的配置。

然而，有时可能需要更改记录的指定主节点 —— 也许是因为一个区域不可用，你需要将流量重定向到另一个区域，或者也许是因为用户搬到了不同的地方，现在离另一个区域更近。现在存在一个风险，即用户在指定主节点更改过程中执行写入操作，导致需要使用以下方法之一来解决冲突。

冲突避免是很脆弱的，如果允许更改主节点，冲突避免机制就会失效。

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

如果无法避免冲突，解决冲突最简单的方法是为每次写入附加一个时间戳，并始终使用具有最大时间戳的值。

这种做法称为最后写入者胜出（LWW）。但实际上，最后写入是不确定的，可能客户端 A 先发出请求，但实际上客户端 B 的请求先到达。

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

如果能避免冲突 —— 例如，只插入具有唯一键（如 UUID）的记录，并且从不更新它们 —— 那么 LWW（最后写入者胜出）就不是问题。但如果你要更新现有记录，或者如果不同的主节点可能会插入具有相同键的记录，那么必须评估丢失更新对应用的影响。

LWW 的另一个问题是，如果使用实时时钟（例如 Unix 时间戳）作为写入的时间戳，系统会变得非常敏感于时钟同步。这需要进一步引入一个统一的逻辑时钟。

手动冲突解决#

如果随机丢弃一些写入不可取，下一个选项是手动解决冲突。

你可能熟悉 Git 和其他版本控制系统中的手动冲突解决：如果两个不同分支修改了同一文件中的相同行，当你尝试合并这些分支时，就会产生一个需要解决合并冲突才能完成合并的情况。

在数据库中，等待人工结合冲突是不切实际的。相反，一种常用策略是存储冲突值（这些值有时被称为兄弟节点）。下次查询该记录时，数据库会返回所有这些值，而不是仅返回最新值。然后应用就可以在代码中 / 交给用户进行冲突处理。

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

• 数据库的 API 发生了变化：例如，以前维基页面的标题只是一个字符串，现在它变成了一组字符串，通常包含一个元素，但在存在冲突时可能会包含多个元素。这可能导致在应用代码中处理数据变得不便捷。
• 要求用户手动合并子节点是一项大量工作，UI / UX 体验直线下降。
  
• 自动合并可能会在不小心操作时导致出乎意料的行为。例如，亚马逊的购物车曾经允许并发更新，这些更新通过取所有子节点（即购物车）的并集。这意味着，如果客户在一个子节点中从购物车中删除了一个项目，但另一个子节点仍然包含那个旧项目。
• 如果多个节点都观察到冲突并同时解决它，冲突解决过程本身可能会引入新的冲突。这些解决方法甚至可能不一致：例如，如果你不小心按一致顺序进行合并，一个节点可能会将 B 和 C 合并为 “B/C”，而另一个节点可能会将它们合并为 “C/B”。当 “B/C” 和 “C/B” 之间的冲突被合并时，可能会得到 “B/C/C/B” 或类似令人惊讶的结果。

自动冲突处理#

对于许多应用来说，处理冲突的最佳方式是使用一个自动合并并发写入并达到一致状态的算法。自动冲突解决确保所有副本最终收敛到同一状态。

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

• 对于文本数据，可以检测出从一个版本到下一个版本中哪些字符被插入或删除了。合并结果会保留所有兄弟节点中做出的所有插入和删除操作。如果用户同时在同一位置插入文本，它可以被确定性地排序，以便所有节点都能得到相同的合并结果。
• 如果数据是列表项，我们可以像合并文本那样合并它，方法是跟踪插入和删除操作。为了避免图 6-10 中的购物车问题，算法会跟踪 Book 和 DVD 被删除的事实，因此合并后不包含被删除的项。
• 如果数据是一个表示计数器的整数，（例如社交媒体帖子上的点赞数），合并算法可以告诉每个子节点上发生了多少次递增和递减，并将它们正确地相加，以确保结果不会重复计算也不会丢失更新。
• 如果数据是键值对，可以通过将其他冲突解决算法应用于该键下的值来合并对相同键的更新。对不同的键的更新可以独立处理。

冲突处理也存在局限性。例如：如果你希望确保列表中不超过五项，而多个用户同时向列表中添加项目，导致总数超过五项，唯一的选项就是删除一些项目。尽管如此，自动冲突解决足以构建许多有用的应用程序。如果你从想要构建一个协作型离线优先或本地优先应用程序的需求出发，那么冲突解决是不可避免的，而自动化它通常是最佳方法。

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 中，我们将 “i” 分配 ID 1A，“c” 分配 ID 2A，以此类推。当插入感叹号时，我们生成一个操作，其中包含新字符的 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）

什么是冲突？#

有些冲突很明显。而有些冲突可能更难以检测。例如，一个会议室预订系统：它跟踪哪个房间被哪一组人在什么时间预订。这个应用需要确保每个房间在任何时间只能被一组人预订。在这种情况下，如果两个不同的预订在同一时间创建于同一个房间，就可能产生冲突。即使应用在允许用户预订前检查了可用性，如果这两个预订是在两个不同的主节点上创建的，仍然可能存在冲突。

 无主复制#

本章讨论的复制方法 —— 单主复制和多主复制 —— 都基于一个理念：客户端向一个主节点发送写请求，数据库系统负责将该写操作复制到其他副本。主节点决定写操作的顺序，而从节点以相同的顺序应用主节点的写操作。
有些数据存储系统采取了不同的方法，放弃了主从节点概念，任何副本都能直接接受来自客户端的写入。一些最早的数据复制系统是无领导的，但在关系型数据库主导的时代，这个想法基本上被遗忘了。在 2007 年亚马逊将其用于内部 Dynamo 系统后，它再次成为数据库的一种流行架构。Riak、Cassandra 和 ScyllaDB 是受 Dynamo 启发的无领导复制模型的开源数据存储，因此这种数据库也被称为 Dynamo 风格。

原始的 Dynamo 系统仅在论文中有所描述，但从未在亚马逊外部发布。同样命名的 DynamoDB 是 AWS 近期推出的一种云数据库，但其架构完全不同：它基于 Multi-Paxos 共识算法使用单主节点复制。

在某些无主实现中，客户端直接将其写入操作发送到多个副本，而在其他实现中，协调节点代替客户端执行此操作。然而，与主节点数据库不同，该协调节点不强制要求写入顺序。

当节点宕机时写入数据库#

假设一个三节点的数据库，其中一个宕机了，

在单主节点中，可能需要进行故障转移，而在无主配置中，不存在故障转移。

如图：

客户端（用户 1234）并行地向所有三个副本发送写入请求，两个可用的副本接受了写入，但不可用的副本错过了写入。假设三个副本中有两个确认写入就足够了：当用户 1234 收到两个 "ok" 响应后，我们认为写入成功。客户端简单地忽略了其中一个副本错过了写入的事实。

现在不可用的节点重新上线，客户端开始从它读取数据。该节点不知道在宕机期间发生的更新。如果从该节点读取数据，可能会收到旧值。

为了解决这个问题，当客户端从数据库读取数据时，它不会只向一个副本发送请求：读请求会并行发送到多个节点。客户端可能会从不同节点收到不同的响应

为了区分哪些响应是最新更新的，哪些已经过时，所有写入的值都需要带有版本号或时间戳。当客户端接收到多个响应于读取操作返回的值时，它会使用带有最大时间戳的那个值（即使该值仅由一个副本返回，而其他几个副本返回了较旧值）。

追补错过的写入#

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

• 读修复（Read repair）：客户端并行从多个节点读取时，它可以检测到过时响应。当同时获取新旧值时，用新值副本写回更新旧值副本。这种方法适用于频繁读取的值。
• 提示式交接（Hinted handoff）：如果一个副本不可用，另一个副本可以以 “提示” 的形式代表它存储写入信息。当应该接收这些写入的副本恢复时，存储 “提示” 的副本将它们发送给恢复的副本，然后删除 “提示”。这种交接过程有助于让从未处理读请求的副本也保持最新。
• 反熵（Anti-entropy）：一个后台进程会定期检查副本间的数据差异，并将一个副本中缺失的数据复制到另一个副本。与基于主节点复制的复制日志不同，这种反熵过程不会按特定顺序复制写入，并且数据复制前可能会有显著的延迟。

读写仲裁#

在图 6-12 的示例中，即使写入仅在三个副本中的两个上处理，我们也将其视为成功。如果只有一个副本接受了写入呢？我们能将这个范围推多远？
如果我们知道每个成功的写入都保证至少在三个副本中的两个上存在，这意味着最多只有一个副本可能过时。因此，如果我们从至少两个副本读取，我们可以确信其中至少有一个是最新的。如果第三个副本宕机或响应缓慢，读取仍然可以继续返回一个最新的值。

更一般地，如果有 n 个副本，每个写入必须由 w 个节点确认才能被视为成功，并且每次读取必须查询至少 r 个节点。只要 w + r > n，那么读取时至少有一个结果是最新值。遵守这些 r 和 w 值的读取和写入被称为仲裁读取和写入。你可以将 r 和 w 视为读取或写入有效的最小投票数。

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

集群中可能有超过 n 个节点，但任何给定值只存储在 n 个节点上。这让数据集分片支持大于单个节点可容纳的数据集。

仲裁条件 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 决定了等待多少节点的响应。如果可用的 w 或 r 节点少于所需数量，读写操作将返回错误。

多数一致性（Quorum Consistency）的局限性#

对于 n 个副本，并且选择 w 和 r 使得 w + r > n，可以预期每次读操作都会返回键的最新写入值（至少一个节点会返回最新值）。

通常情况下，r 和 w 被选择为多数（超过 n/2）的节点，这样可以确保 w + r > n，同时还能容忍高达 n/2 的节点故障。但仲裁值不一定是多数 —— 重要的是读写操作所使用的节点集至少在一个节点上重叠。其他仲裁分配也是可能的，这使得分布式算法设计中的某些灵活性。

你也可以将 w 和 r 设置为较小的数字，使得 w + r ≤ n（即仲裁条件不满足）。在这种情况下，读写操作仍然会发送到 n 个节点，但操作成功所需的成功响应数量较小。

当 w 和 r 较小时，有可能读到过期的值。但这种配置可以带来更低的延迟和更高的可用性，只有当可达副本的数量低于 w 或 r 时，数据库才会读（r）写（w）不可用。

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

• 如果一个携带新值的节点发生故障，并且其数据从携带旧值的副本中恢复，存储新值的副本数量可能会低于 w，从而破坏约定的条件。
• 在重新平衡过程中，数据从节点 A 迁移到节点 B，节点可能对哪些节点应该持有特定值的 n 个副本存在不一致的看法。这可能导致读和写节点不再有重叠。
• 如果一个读写并发进行，读操作可能会也可能不会看到并发写入的值。典型情况是一个读操作可能会看到新值，而随后的读操作可能会看到旧值。
• 如果一个写操作在一些副本上成功但在其他副本上失败（例如因为某些节点的磁盘已满），并且整体上成功写入的副本少于 w 个，那么在成功的副本上不会被回滚。这意味着如果写操作被报告为失败，随后的读操作可能会也可能不会返回该写操作的结果。
• 如果数据库使用实时时钟的时间戳来确定哪个写操作更新（例如 Cassandra 和 ScyllaDB 就是这样做的），如果另一个具有更快时钟的节点对同一个键进行了写入，写操作可能会被无声地丢弃
• 如果两个写入操作同时发生，其中一个可能会在某个副本上先被处理，而另一个可能会在另一个副本上先被处理。这会导致冲突。

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

从运营角度来看，监控你的数据库是否返回最新结果非常重要。即使你的应用可以容忍过时的读取，你也需要了解复制的健康状况。如果复制明显落后，它应该发出警报，以便你可以调查原因（例如，网络问题或节点过载）。

对于基于主节点的复制，数据库通常会暴露复制延迟的指标。但在无主复制体系中，写入应用的顺序不固定，这使得监控更加困难。副本存储的手动交接提示数量可以是一个衡量系统健康的指标，但很难进行有意义的解读。最终一致性是一个故意模糊的保证，但对于可操作性来说，能够量化 “最终” 是很重要的。

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

基于单主节点复制的系统可以提供无主节点系统难以或不可能实现的强一致性保证。
但是基于单主节点复制也可能返回过时的值。从主节点读取可确保获取最新响应，但存在性能问题：

• 读取吞吐量受限于主节点处理请求的能力。
• 如果主节点失效，必须等待故障被检测到，并等待故障转移完成才能继续处理请求。即使故障转移过程非常快，用户也会注意到，因为响应时间暂时增加；如果故障转移需要很长时间，系统在其期间将不可用。
• 系统对主节点的性能问题非常敏感：如果主节点响应缓慢，例如由于过载或某些资源争用，增加的响应时间会立即影响用户。

无主节点架构的一大优势在于它更能抵抗此类问题。由于不存在故障转移，并且请求无论如何都会并行发送到多个副本，因此一个副本变慢或不可用对响应时间的影响非常小：客户端只需使用那些响应更快的其他副本的响应。使用最快的响应称为请求折衷，它可以显著降低尾部延迟。

无主节点系统的弹性核心在于它不区分正常情况和故障情况。这在处理所谓的灰色故障时很有效：节点并未完全宕机，但运行在降级状态，处理请求异常缓慢，或者节点只是过载。基于主节点的系统必须决定情况是否严重到需要故障转移（这本身可能造成进一步中断），而在无主节点系统中，这个问题甚至都不会出现。

但无主系统也可能存在性能问题：

• 尽管系统不需要执行故障转移，但一个副本仍需检测另一个副本可用性，以便存储不可用副本遗漏的写入。当不可用的副本恢复时进行交接。这给副本增加了额外的负载，而此时系统已经承受着压力。
• 副本越多，仲裁团规模就越大，请求完成前需要等待的响应就越多。即使你只等待最快的 r 或 w 副本响应，并且并行发送请求，更大的 r 或 w 会增加遇到慢副本的几率，从而增加整体响应时间
• 大规模网络中断导致客户端与大量副本断开连接时，无法进行仲裁。一些无主数据库提供了一种配置选项，允许任何（即使不是该键的常规副本之一）可达的副本接收写入，（Riak 和 Dynamo 称其为宽松仲裁；Cassandra 和 ScyllaDB 称其为任何一致性级别）。后续读取不一定能看到写入的值，但根据应用情况，这可能比写入失败要好。

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

多区域操作#

无主复制也适用于多区域操作，因为它设计上用来容忍冲突的并发写入、网络中断和延迟峰值。

Cassandra 和 ScyllaDB 在其多区域支持中实现了常规的无主模型：客户端直接将其写入发送到所有区域的副本，并且可以选择多种一致性级别，这些级别决定了请求成功所需的响应数量。

例如，您可以请求跨所有区域副本的仲裁，每个区域单独的仲裁，或仅在客户端本地区域的仲裁。本地仲裁避免了等待其他区域的慢速请求，但也更有可能返回过时的结果。

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

检测并发写入#

类似于多主复制，无主数据库允许对相同键进行并发写入，因此需要解决冲突。这种冲突可能写入过程，读修复、提示转移或抗熵过程中被检测到。

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

• 节点 1 收到了来自 A 的写入请求，但由于临时故障，它从未收到来自 B 的写入请求
• 节点 2 先接收来自 A 的写入，然后接收来自 B 的写入。
• 节点 3 先接收来自 B 的写入，然后接收来自 A 的写入。

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

为了最终达到一致性，副本应该收敛到相同的值。因此需要进行冲突处理。

 并发与先后关系（“happens-before”）#

我们如何判断两个操作是否并发？

为了培养直觉，让我们看看一些例子：

• A 的插入发生在 B 的递增之前，因为 B 递增的值是 A 插入的值。换句话说，B 的操作建立在 A 的操作之上，所以 B 的操作必须发生在之后。我们也可以说 B 对 A 有依赖。
• 上图中的两个写操作是并发的：当每个客户端开始操作时，它不知道另一个客户端也在对同一个键执行操作。因此，这两个操作之间没有因果依赖。

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

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

看起来两个操作应该被称作并发，如果它们 “同时” 发生 —— 但实际上，它们是否在时间上真正重叠并不重要。由于分布式系统中时钟的问题，实际上很难判断两件事情是否正好在同一时间发生 —— 我们将在第 9 章中更详细地讨论这个问题。

对于并发性定义，精确时间并不重要：只要两个操作彼此不知晓，就称它们是并发的

检测 “happens-before” 关系#

我们来看一个用于判断两个操作是否并发的算法。

为了简化问题，我们首先考虑一个只有一个副本的数据库。一旦我们解决了单副本的情况，就可以将这种方法推广到无主数据库中的多个副本。

图 6-15 展示了两个客户端并发向同一个购物车添加商品。最初，购物车是空的。两个客户端共同向数据库写入了五次：

1. 客户端 1 将 milk 添加到购物车。这是对该键的第一个写入，因此服务器成功将其存储并分配版本 1。服务器还将该值连同版本号回显给客户端。
2. 客户端 2 将 eggs 添加到购物车，但不知道客户端 1 同时添加了 milk。服务器为这次写入分配了版本号 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 或询问用户。写入请求的响应类似于读取，返回所有兄弟节点，这使我们能够像购物车示例那样链式执行多个写入操作。
  当服务器接收到一个带有特定版本号的写入时，它可以覆盖所有该版本号或更低版本号的所有值（因为它知道这些值已经被合并到新值中），但它必须保留所有更高版本号的所有值（因为这些值与正在接收的写入是并发进行的）。

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

### Version vectors  版本向量#

图 6-15 中的示例仅使用了一个副本。当存在多个副本但没有领导者时，算法会如何变化？

图 6-15 使用单个版本号来捕获操作之间的依赖关系，但在多个副本并发接收写入时，这并不足够。相反，我们需要为每个副本和每个键使用各自的版本号。每个副本在处理写入时都会递增自己的版本号，并且还会跟踪从每个其他副本中看到的版本号。这些信息表明哪些值需要被覆盖，哪些值需要作为兄弟保留。

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

版本号如图 6-15 所示，当读取值时，版本向量会从数据库副本发送给客户端，当随后写入值时，需要将版本向量发送回数据库。（Riak 将版本向量编码为一个称为因果上下文的字符串。）版本向量允许数据库区分覆盖写入和并发写入。

版本向量还确保从某个副本读取后再写入另一个副本是安全的。这样做可能会创建兄弟副本，但只要正确合并兄弟副本，就不会丢失数据。

总结#

复制可以服务于多个目的：

• 高可用
• 离线操作
• 延迟
• 可拓展性

尽管目标看似简单 —— 在多台机器上保留相同数据的副本 —— 复制却是一个极其复杂的问题。它需要仔细考虑并发性以及所有可能出错的情况，并处理这些错误的后果。至少，我们需要应对不可用节点和网络中断（更不用说那些更隐蔽的故障类型，例如由于软件错误或硬件故障导致的数据损坏）。
复制方法：

• 单主复制：客户端将所有写入操作发送到一个主节点，该节点将数据变更事件流发送给其他从节点。读操作可以在任何副本上执行，但读取的数据可能过时。
• 多主复制：客户端将每个写入操作发送到多个主节点中的任意一个，任何主节点都可以接收写入操作。主节点将数据变更事件流发送给彼此以及任何从节点。
• 无主复制：客户端将每个写入操作发送到多个节点，并并行从多个节点读取数据，以检测和纠正包含过期数据的节点。
  每种方法都有其优势和劣势。单主复制之所以流行，是因为它相对容易理解，并且提供强一致性。多主和无主复制在面对故障节点、网络中断和延迟峰值时可能更健壮 —— 但代价是需要冲突解决，并提供较弱的 consistency 保证。

复制可以是同步或异步，这在出现故障时对系统行为有深远影响。虽然异步复制在系统运行平稳时可以很快，但重要的是要弄清楚当复制延迟增加且服务器故障时会发生什么。如果一个主节点失效而异步更新的从节点提升为新的主节点，最近提交的数据可能会丢失。

我们看到了一些由复制延迟引起的奇怪现象，并讨论了几个有助于决定应用程序在复制延迟下应如何行为的 consistency 模型：

• 读后写一致性：用户应该始终看到他们自己提交的数据。
• 单调读：用户在某个时间点看到数据后，不应该之后看到某个更早时间点的数据。
• 一致前缀读取：用户应该看到具有因果关系的有序数据：例如，按正确顺序看到问题和回答。

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

本章假设每个副本都存储整个数据库的完整副本，这对于大型数据集来说是不现实的。