Follower failure: Catch-up recovery

On its local disk, each follower keeps a log of the data changes it has received from the leader. If a follower crashes and is restarted, or if the network between the leader and the follower is temporarily interrupted, the follower can recover quite easily: from its log, it knows the last transaction that was processed before the fault occurred. Thus, the follower can connect to the leader and request all the data changes that occurred during the time when the follower was disconnected. When it has applied these changes, it has caught up to the leader and can continue receiving a stream of data changes as before.

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

Leader failure: Failover

Handling a failure of the leader is trickier: one of the followers needs to be promoted to be the new leader, clients need to be reconfigured to send their writes to the new leader, and the other followers need to start consuming data changes from the new leader. This process is called failover .

处理领导人失败更加棘手：需要提升一个跟随者成为新的领导者，客户端需要重新配置以将其写入发送到新的领导者，其他跟随者需要开始从新的领导者消耗数据更改。此过程称为故障切换。

Failover can happen manually (an administrator is notified that the leader has failed and takes the necessary steps to make a new leader) or automatically. An automatic failover process usually consists of the following steps:

故障转移可以手动进行（管理员会被通知领导者发生失败并采取必要措施使新的领导者），也可以自动进行。自动故障转移过程通常包括以下步骤：

1. Determining that the leader has failed. There are many things that could potentially go wrong: crashes, power outages, network issues, and more. There is no foolproof way of detecting what has gone wrong, so most systems simply use a timeout: nodes frequently bounce messages back and forth between each other, and if a node doesn’t respond for some period of time—say, 30 seconds—it is assumed to be dead. (If the leader is deliberately taken down for planned maintenance, this doesn’t apply.)

   确定领导者已失败。有很多事情可能会出错：崩溃，停电，网络问题等等。没有绝对可靠的方法来检测出问题所在，因此大多数系统只是使用时间限制：节点之间经常反弹消息，如果某个节点在一段时间内没有响应，比如30秒，就被认为已经死亡。（如果领导者是因计划维护而被故意关闭，则不适用。）

2. Choosing a new leader. This could be done through an election process (where the leader is chosen by a majority of the remaining replicas), or a new leader could be appointed by a previously elected controller node . The best candidate for leadership is usually the replica with the most up-to-date data changes from the old leader (to minimize any data loss). Getting all the nodes to agree on a new leader is a consensus problem, discussed in detail in Chapter 9 .

   选择新领导。这可以通过选举过程（领导者由剩余副本的大多数选择）或由先前选举的控制器节点任命新领导者来完成。领导的最佳人选通常是来自旧领导者最新的数据更改的副本（以最小化任何数据丢失）。让所有节点对新领导达成共识是一个共识问题，详细讨论在第9章中进行。

3. Reconfiguring the system to use the new leader. Clients now need to send their write requests to the new leader (we discuss this in “Request Routing” ). If the old leader comes back, it might still believe that it is the leader, not realizing that the other replicas have forced it to step down. The system needs to ensure that the old leader becomes a follower and recognizes the new leader.

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

Failover is fraught with things that can go wrong:

故障切换充满了可能会出错的事情:

• If asynchronous replication is used, the new leader may not have received all the writes from the old leader before it failed. If the former leader rejoins the cluster after a new leader has been chosen, what should happen to those writes? The new leader may have received conflicting writes in the meantime. The most common solution is for the old leader’s unreplicated writes to simply be discarded, which may violate clients’ durability expectations.

  如果使用异步复制，新领导者在旧领导者失败之前可能没有收到所有写入。如果前领导者在新领导者被选出后重新加入集群，那么这些写入应该怎么处理呢？在此期间，新的领导者可能已经接收到了冲突的写入。最常见的解决方案是旧领导者的未复制写入被简单地丢弃，这可能会违反客户端的耐久性期望。

• Discarding writes is especially dangerous if other storage systems outside of the database need to be coordinated with the database contents. For example, in one incident at GitHub [ 13 ], an out-of-date MySQL follower was promoted to leader. The database used an autoincrementing counter to assign primary keys to new rows, but because the new leader’s counter lagged behind the old leader’s, it reused some primary keys that were previously assigned by the old leader. These primary keys were also used in a Redis store, so the reuse of primary keys resulted in inconsistency between MySQL and Redis, which caused some private data to be disclosed to the wrong users.

  如果数据库外部的其他存储系统需要与数据库内容协调，那么丢弃写入操作尤其危险。例如，在GitHub的一次事件中，一个过时的MySQL从属数据库被提升为主库。数据库使用一个自增计数器来分配新行的主键，但由于新主库的计数器落后于旧主库，它重用了一些旧主库已经分配的主键。这些主键也用于Redis存储，因此主键的重用导致MySQL和Redis之间的不一致，从而导致某些私人数据被泄露给错误的用户。

• In certain fault scenarios (see Chapter 8 ), it could happen that two nodes both believe that they are the leader. This situation is called split brain , and it is dangerous: if both leaders accept writes, and there is no process for resolving conflicts (see “Multi-Leader Replication” ), data is likely to be lost or corrupted. As a safety catch, some systems have a mechanism to shut down one node if two leaders are detected. ⁱⁱ However, if this mechanism is not carefully designed, you can end up with both nodes being shut down [ 14 ].

  在某些故障情况（见第8章）下，可能会出现两个节点都认为自己是领导者的情况。此情况称为“脑裂”，它是危险的：如果两个领导者都接受写入，并且没有解决冲突的过程（见“多领导者复制”），数据很可能会丢失或损坏。为了安全起见，有些系统有机制在检测到两个领导者时关闭其中一个节点。然而，如果这个机制设计不当，你可能会导致两个节点都关闭[14]。

• What is the right timeout before the leader is declared dead? A longer timeout means a longer time to recovery in the case where the leader fails. However, if the timeout is too short, there could be unnecessary failovers. For example, a temporary load spike could cause a node’s response time to increase above the timeout, or a network glitch could cause delayed packets. If the system is already struggling with high load or network problems, an unnecessary failover is likely to make the situation worse, not better.

  正确的超时时间是多少才能宣布领袖死亡？更长的超时时间意味着在领袖失效的情况下需要更长的恢复时间。然而，如果超时时间太短，可能会出现不必要的故障转移。例如，暂时的负载峰值可能会导致节点的响应时间超过超时时间，或者网络故障可能会导致数据包延迟。如果系统已经面临高负载或网络问题，不必要的故障转移很可能会使情况更糟，而不是更好。

There are no easy solutions to these problems. For this reason, some operations teams prefer to perform failovers manually, even if the software supports automatic failover.

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

These issues—node failures; unreliable networks; and trade-offs around replica consistency, durability, availability, and latency—are in fact fundamental problems in distributed systems. In Chapter 8 and Chapter 9 we will discuss them in greater depth.

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

Statement-based replication

In the simplest case, the leader logs every write request ( statement ) that it executes and sends that statement log to its followers. For a relational database, this means that every INSERT , UPDATE , or DELETE statement is forwarded to followers, and each follower parses and executes that SQL statement as if it had been received from a client.

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

Although this may sound reasonable, there are various ways in which this approach to replication can break down:

虽然这听起来很合理，但这种复制方法可能会出现各种问题：

• Any statement that calls a nondeterministic function, such as NOW() to get the current date and time or RAND() to get a random number, is likely to generate a different value on each replica.

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

• If statements use an autoincrementing column, or if they depend on the existing data in the database (e.g., UPDATE … WHERE <some condition> ), they must be executed in exactly the same order on each replica, or else they may have a different effect. This can be limiting when there are multiple concurrently executing transactions.

  如果语句使用自增列，或者依赖于数据库中现有数据（例如，UPDATE...WHERE <某些条件>），则它们必须在每个副本上以完全相同的顺序执行，否则它们可能会产生不同的效果。当有多个正在执行的事务时，这可能会受限。

• Statements that have side effects (e.g., triggers, stored procedures, user-defined functions) may result in different side effects occurring on each replica, unless the side effects are absolutely deterministic.

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

It is possible to work around those issues—for example, the leader can replace any nondeterministic function calls with a fixed return value when the statement is logged so that the followers all get the same value. However, because there are so many edge cases, other replication methods are now generally preferred.

可以采用解决这些问题的方法——例如，领导可以在记录语句时将任何非确定性函数调用替换为固定的返回值，以便跟随者都获得相同的值。但由于存在很多特殊情况，现在通常更喜欢使用其他复制方法。

Statement-based replication was used in MySQL before version 5.1. It is still sometimes used today, as it is quite compact, but by default MySQL now switches to row-based replication (discussed shortly) if there is any nondeterminism in a statement. VoltDB uses statement-based replication, and makes it safe by requiring transactions to be deterministic [ 15 ].

在MySQL 5.1版本之前，基于语句的复制曾被使用。尽管这种方式非常紧凑，但现在默认情况下MySQL会切换到基于行的复制（稍后讨论），如果一个语句存在任何不确定性。VoltDB使用基于语句的复制，并通过要求事务具有确定性来使其安全。[15]。

Write-ahead log (WAL) shipping

In Chapter 3 we discussed how storage engines represent data on disk, and we found that usually every write is appended to a log:

在第三章中，我们讨论了存储引擎如何在磁盘上表示数据，我们发现通常每次写入都会附加到日志中。

• In the case of a log-structured storage engine (see “SSTables and LSM-Trees” ), this log is the main place for storage. Log segments are compacted and garbage-collected in the background.

  在采用日志结构化存储引擎的情况下（见“SSTables和LSM树”），这个日志是主要的存储地点。日志段在后台进行压缩和垃圾回收。

• In the case of a B-tree (see “B-Trees” ), which overwrites individual disk blocks, every modification is first written to a write-ahead log so that the index can be restored to a consistent state after a crash.

  在B树（参见“B树”）的情况下，会覆盖单个磁盘块，因此每次修改都会首先写入写前日志，以便在崩溃后恢复索引到一致状态。

In either case, the log is an append-only sequence of bytes containing all writes to the database. We can use the exact same log to build a replica on another node: besides writing the log to disk, the leader also sends it across the network to its followers. When the follower processes this log, it builds a copy of the exact same data structures as found on the leader.

在任何情况下，日志都是一系列字节的附加序列，包含对数据库的所有写入。我们可以使用完全相同的日志在另一个节点上构建副本：除将日志写入磁盘外，领导者还将其发送到其追随者之间的网络。当追随者处理此日志时，它将构建与领导者上发现的完全相同的数据结构的副本。

This method of replication is used in PostgreSQL and Oracle, among others [ 16 ]. The main disadvantage is that the log describes the data on a very low level: a WAL contains details of which bytes were changed in which disk blocks. This makes replication closely coupled to the storage engine. If the database changes its storage format from one version to another, it is typically not possible to run different versions of the database software on the leader and the followers.

此复制方法适用于PostgreSQL和Oracle等数据库。其主要缺点是日志记录数据级别非常低：WAL包含哪些磁盘块中的哪些字节被更改的详细信息。这使得复制与存储引擎密切相关。如果数据库从一个版本更改其存储格式到另一个版本，通常不可能在Leader和Follower上运行不同版本的数据库软件。

That may seem like a minor implementation detail, but it can have a big operational impact. If the replication protocol allows the follower to use a newer software version than the leader, you can perform a zero-downtime upgrade of the database software by first upgrading the followers and then performing a failover to make one of the upgraded nodes the new leader. If the replication protocol does not allow this version mismatch, as is often the case with WAL shipping, such upgrades require downtime.

这可能看起来像一个微小的实现细节，但它可能会对操作产生重大影响。如果复制协议允许从者使用比领导者更新的软件版本，那么您可以通过首先升级从者，然后执行故障转移使升级后的节点成为新的领导者，从而执行零停机升级数据库软件。如果复制协议不允许这种版本不匹配，通常在WAL传送中出现这种情况，则此类升级需要停机时间。

Logical (row-based) log replication

An alternative is to use different log formats for replication and for the storage engine, which allows the replication log to be decoupled from the storage engine internals. This kind of replication log is called a logical log , to distinguish it from the storage engine’s ( physical ) data representation.

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

A logical log for a relational database is usually a sequence of records describing writes to database tables at the granularity of a row:

关系数据库的逻辑日志通常是描述对数据库表进行行级写操作的记录序列：

• For an inserted row, the log contains the new values of all columns.

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

• For a deleted row, the log contains enough information to uniquely identify the row that was deleted. Typically this would be the primary key, but if there is no primary key on the table, the old values of all columns need to be logged.

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

• For an updated row, the log contains enough information to uniquely identify the updated row, and the new values of all columns (or at least the new values of all columns that changed).

  更新的行，在日志中包含足够的信息来唯一识别更新的行，并且包含所有列的新值（或者至少包含所有修改的列的新值）。

A transaction that modifies several rows generates several such log records, followed by a record indicating that the transaction was committed. MySQL’s binlog (when configured to use row-based replication) uses this approach [ 17 ].

一项修改多行的交易会产生多个此类日志记录，最后会有记录表明该交易已提交。当配置为使用基于行的复制时，MySQL的binlog使用此方法。

Since a logical log is decoupled from the storage engine internals, it can more easily be kept backward compatible, allowing the leader and the follower to run different versions of the database software, or even different storage engines.

由于逻辑日志与存储引擎内部解耦，因此可以更轻松地保持向后兼容性，允许领导者和追随者运行不同版本的数据库软件，甚至是不同的存储引擎。

A logical log format is also easier for external applications to parse. This aspect is useful if you want to send the contents of a database to an external system, such as a data warehouse for offline analysis, or for building custom indexes and caches [ 18 ]. This technique is called change data capture , and we will return to it in Chapter 11 .

逻辑日志格式也更容易被外部应用程序分析。如果您想将数据库内容发送到外部系统（例如用于离线分析的数据仓库），或用于构建自定义索引和缓存，这个方面会很有用 [18]。这个技术称为变更数据捕获，在第11章中我们将回到它。

Trigger-based replication

The replication approaches described so far are implemented by the database system, without involving any application code. In many cases, that’s what you want—but there are some circumstances where more flexibility is needed. For example, if you want to only replicate a subset of the data, or want to replicate from one kind of database to another, or if you need conflict resolution logic (see “Handling Write Conflicts” ), then you may need to move replication up to the application layer.

迄今为止所描述的复制方法是由数据库系统实现的，不涉及任何应用程序代码。在许多情况下，这是您想要的，但还有一些情况需要更多的灵活性。例如，如果您只想复制数据子集，或者想要从一种数据库复制到另一种数据库，或者如果您需要冲突解决逻辑（请参见“处理写入冲突”），那么您可能需要将复制向应用程序层移动。

Some tools, such as Oracle GoldenGate [ 19 ], can make data changes available to an application by reading the database log. An alternative is to use features that are available in many relational databases: triggers and stored procedures .

一些工具，例如Oracle GoldenGate，可以通过读取数据库日志将数据更改提供给应用程序。另一种选择是使用许多关系数据库可用的功能：触发器和存储过程。

A trigger lets you register custom application code that is automatically executed when a data change (write transaction) occurs in a database system. The trigger has the opportunity to log this change into a separate table, from which it can be read by an external process. That external process can then apply any necessary application logic and replicate the data change to another system. Databus for Oracle [ 20 ] and Bucardo for Postgres [ 21 ] work like this, for example.

触发器允许您注册自定义应用程序代码，当数据库系统中发生数据更改（写入事务）时自动执行。触发器可以将此更改记录到单独的表中，外部进程可以读取该表。然后，外部进程可以应用任何必要的应用程序逻辑并将数据更改复制到另一个系统。例如，Databus for Oracle和Postgres的Bucardo工作方式如此。

Trigger-based replication typically has greater overheads than other replication methods, and is more prone to bugs and limitations than the database’s built-in replication. However, it can nevertheless be useful due to its flexibility.

基于触发器的复制通常比其他复制方法有更高的开销，且比数据库内置的复制更容易出现错误和限制。 然而，由于其灵活性，它仍然可以是有用的。

Multi-datacenter operation

Imagine you have a database with replicas in several different datacenters (perhaps so that you can tolerate failure of an entire datacenter, or perhaps in order to be closer to your users). With a normal leader-based replication setup, the leader has to be in one of the datacenters, and all writes must go through that datacenter.

想象一下，你有一个数据库，它在几个不同的数据中心中有副本（可能是为了能够容忍整个数据中心的故障，或者可能是为了更加接近你的用户）。在普通的基于领导者的复制设置中，领导者必须在其中一个数据中心中，而所有写操作必须经过该数据中心。

In a multi-leader configuration, you can have a leader in each datacenter. Figure 5-6 shows what this architecture might look like. Within each datacenter, regular leader–follower replication is used; between datacenters, each datacenter’s leader replicates its changes to the leaders in other datacenters.

在多领导者配置中，您可以在每个数据中心都拥有一位领导者。图5-6显示了这种架构可能的外观。在每个数据中心内，使用常规的领导者-跟随者复制；在数据中心之间，每个数据中心的领导者将其更改复制到其他数据中心的领导者。

Figure 5-6. Multi-leader replication across multiple datacenters.

Let’s compare how the single-leader and multi-leader configurations fare in a multi-datacenter deployment:

让我们来比较单领导者和多领导者配置在多数据中心部署中的表现：

Performance

In a single-leader configuration, every write must go over the internet to the datacenter with the leader. This can add significant latency to writes and might contravene the purpose of having multiple datacenters in the first place. In a multi-leader configuration, every write can be processed in the local datacenter and is replicated asynchronously to the other datacenters. Thus, the inter-datacenter network delay is hidden from users, which means the perceived performance may be better.

在单个领导者配置中，每个写操作都必须通过互联网传输到具有领导者的数据中心。这可能会增加写入的延迟，并可能违反首先拥有多个数据中心的目的。在多领导者配置中，每个写操作可以在本地数据中心中处理，并异步复制到其他数据中心。因此，数据中心之间的网络延迟对用户来说是隐藏的，这意味着感知性能可能更好。

Tolerance of datacenter outages

In a single-leader configuration, if the datacenter with the leader fails, failover can promote a follower in another datacenter to be leader. In a multi-leader configuration, each datacenter can continue operating independently of the others, and replication catches up when the failed datacenter comes back online.

在单个领导者配置中，如果具有领导者的数据中心失败，故障转移可以将另一个数据中心中的追随者晋升为领导者。在多个领导者配置中，每个数据中心都可以独立运行，而且当失败的数据中心恢复线上时，复制会追赶上来。

Tolerance of network problems

Traffic between datacenters usually goes over the public internet, which may be less reliable than the local network within a datacenter. A single-leader configuration is very sensitive to problems in this inter-datacenter link, because writes are made synchronously over this link. A multi-leader configuration with asynchronous replication can usually tolerate network problems better: a temporary network interruption does not prevent writes being processed.

数据中心之间的流量通常通过公共互联网进行传输，这可能比数据中心内部的本地网络不够可靠。单主配置非常敏感于此数据中心间的链接问题，因为写入是通过此链接同步进行的。使用异步复制的多主配置通常可以更好地容纳网络问题：暂时的网络中断不会阻止写入被处理。

Some databases support multi-leader configurations by default, but it is also often implemented with external tools, such as Tungsten Replicator for MySQL [ 26 ], BDR for PostgreSQL [ 27 ], and GoldenGate for Oracle [ 19 ].

一些数据库默认支持多主配置，但也经常通过外部工具实现，例如 MySQL 的 Tungsten Replicator [26]，PostgreSQL 的 BDR [27]，以及 Oracle 的 GoldenGate [19]。

Although multi-leader replication has advantages, it also has a big downside: the same data may be concurrently modified in two different datacenters, and those write conflicts must be resolved (indicated as “conflict resolution” in Figure 5-6 ). We will discuss this issue in “Handling Write Conflicts” .

虽然多领导者复制具有优点，但也有一个很大的缺点：同样的数据可能会在两个不同的数据中心中被同时修改，这些写冲突必须被解决（在图5-6中被表示为“冲突解决”）。我们将在“处理写冲突”中讨论这个问题。

As multi-leader replication is a somewhat retrofitted feature in many databases, there are often subtle configuration pitfalls and surprising interactions with other database features. For example, autoincrementing keys, triggers, and integrity constraints can be problematic. For this reason, multi-leader replication is often considered dangerous territory that should be avoided if possible [ 28 ].

由于多主复制在许多数据库中是一项后期配置功能，因此通常存在微妙的配置陷阱和与其他数据库功能的惊人相互作用。例如，自增键、触发器和完整性约束可能存在问题。因此，多主复制通常被认为是危险领域，如果可能应该避免 [28]。

Clients with offline operation

Another situation in which multi-leader replication is appropriate is if you have an application that needs to continue to work while it is disconnected from the internet.

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

For example, consider the calendar apps on your mobile phone, your laptop, and other devices. You need to be able to see your meetings (make read requests) and enter new meetings (make write requests) at any time, regardless of whether your device currently has an internet connection. If you make any changes while you are offline, they need to be synced with a server and your other devices when the device is next online.

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

In this case, every device has a local database that acts as a leader (it accepts write requests), and there is an asynchronous multi-leader replication process (sync) between the replicas of your calendar on all of your devices. The replication lag may be hours or even days, depending on when you have internet access available.

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

From an architectural point of view, this setup is essentially the same as multi-leader replication between datacenters, taken to the extreme: each device is a “datacenter,” and the network connection between them is extremely unreliable. As the rich history of broken calendar sync implementations demonstrates, multi-leader replication is a tricky thing to get right.

从建筑的角度来看，这个设置实际上与数据中心之间的多领导者复制基本相同，达到了极限：每个设备都是一个“数据中心”，它们之间的网络连接非常不可靠。正如破碎的日历同步实现的丰富历史所证明的那样，多领导者复制是一个很棘手的事情。

There are tools that aim to make this kind of multi-leader configuration easier. For example, CouchDB is designed for this mode of operation [ 29 ].

有些工具旨在使这种多领导者配置更加容易。例如，CouchDB是为此模式设计的[29]。

Collaborative editing

Real-time collaborative editing applications allow several people to edit a document simultaneously. For example, Etherpad [ 30 ] and Google Docs [ 31 ] allow multiple people to concurrently edit a text document or spreadsheet (the algorithm is briefly discussed in “Automatic Conflict Resolution” ).

实时协作编辑应用程序可以让多人同时编辑一个文档。例如，Etherpad [30] 和 Google Docs [31] 允许多人同时编辑文本文档或电子表格（算法已在“自动冲突解决”中简要讨论）。

We don’t usually think of collaborative editing as a database replication problem, but it has a lot in common with the previously mentioned offline editing use case. When one user edits a document, the changes are instantly applied to their local replica (the state of the document in their web browser or client application) and asynchronously replicated to the server and any other users who are editing the same document.

我们通常不将协作编辑视为数据库复制问题，但它与先前提到的离线编辑用例有很多共同点。当一个用户编辑文档时，更改会立即应用于他们的本地副本（即在其Web浏览器或客户端应用程序中的文档状态），并异步地复制到服务器和任何其他正在编辑同一文档的用户。

If you want to guarantee that there will be no editing conflicts, the application must obtain a lock on the document before a user can edit it. If another user wants to edit the same document, they first have to wait until the first user has committed their changes and released the lock. This collaboration model is equivalent to single-leader replication with transactions on the leader.

如果您想保证没有编辑冲突，应用程序必须在用户进行编辑之前获取文档的锁定。如果另一个用户想要编辑同一份文档，他们必须等待第一个用户提交更改并释放锁定。这种协作模型相当于在领导者上具有事务的单一领导者复制。

However, for faster collaboration, you may want to make the unit of change very small (e.g., a single keystroke) and avoid locking. This approach allows multiple users to edit simultaneously, but it also brings all the challenges of multi-leader replication, including requiring conflict resolution [ 32 ].

然而，为了更快的协作，您可能想要将更改的单元变得非常小（例如，一个单一的按键），并避免锁定。这种方法允许多个用户同时编辑，但也带来了多个领导者复制的所有挑战，包括需要冲突解决。

Synchronous versus asynchronous conflict detection

In a single-leader database, the second writer will either block and wait for the first write to complete, or abort the second write transaction, forcing the user to retry the write. On the other hand, in a multi-leader setup, both writes are successful, and the conflict is only detected asynchronously at some later point in time. At that time, it may be too late to ask the user to resolve the conflict.

在单个领导者数据库中，第二个写入者将要么阻塞并等待第一个写入完成，要么中止第二个写入事务，强制用户重试写入。另一方面，在多个领导者设置中，两个写入都成功，冲突仅在稍后异步检测到。这时，可能已经太晚要求用户解决冲突。

In principle, you could make the conflict detection synchronous—i.e., wait for the write to be replicated to all replicas before telling the user that the write was successful. However, by doing so, you would lose the main advantage of multi-leader replication: allowing each replica to accept writes independently. If you want synchronous conflict detection, you might as well just use single-leader replication.

原则上，您可以将冲突检测设置为同步 - 即在向用户报告写入成功之前，等待复制到所有副本。然而，这样做会丧失多主复制的主要优势：允许每个副本独立接受写入。如果您想要同步的冲突检测，那么您也可以使用单主复制。

Conflict avoidance

The simplest strategy for dealing with conflicts is to avoid them: if the application can ensure that all writes for a particular record go through the same leader, then conflicts cannot occur. Since many implementations of multi-leader replication handle conflicts quite poorly, avoiding conflicts is a frequently recommended approach [ 34 ].

避免冲突的最简单策略是避免它们：如果应用程序能够确保特定记录的所有写入都通过同一领导者进行，则冲突就不会发生。由于许多多领导者复制的实现处理冲突非常糟糕，避免冲突是一种经常推荐的方法[34]。

For example, in an application where a user can edit their own data, you can ensure that requests from a particular user are always routed to the same datacenter and use the leader in that datacenter for reading and writing. Different users may have different “home” datacenters (perhaps picked based on geographic proximity to the user), but from any one user’s point of view the configuration is essentially single-leader.

例如，在一个用户可以编辑自己数据的应用程序中，您可以确保来自特定用户的请求始终路由到同一数据中心，并使用该数据中心的领导者进行读写操作。不同的用户可能有不同的“家庭”数据中心（可能是基于地理距离选择的），但从任何一个用户的角度来看，配置基本上是单主导的。

However, sometimes you might want to change the designated leader for a record—perhaps because one datacenter has failed and you need to reroute traffic to another datacenter, or perhaps because a user has moved to a different location and is now closer to a different datacenter. In this situation, conflict avoidance breaks down, and you have to deal with the possibility of concurrent writes on different leaders.

然而，有时你可能想要更改被指定的记录领导者——可能是因为一个数据中心已经失效，你需要将流量重新路由到另一个数据中心，或者因为用户已经移动到不同的位置，更靠近其他数据中心。在这种情况下，冲突避免就会失败，你必须面对不同领导者上相互写入的可能性。

Converging toward a consistent state

A single-leader database applies writes in a sequential order: if there are several updates to the same field, the last write determines the final value of the field.

单主数据库按顺序应用写操作：如果对同一字段进行了多个更新，则最后一次写入确定字段的最终值。

In a multi-leader configuration, there is no defined ordering of writes, so it’s not clear what the final value should be. In Figure 5-7 , at leader 1 the title is first updated to B and then to C; at leader 2 it is first updated to C and then to B. Neither order is “more correct” than the other.

在多领导者配置中，写入的顺序没有定义，因此不清楚最终的值应该是什么。在图5-7中，领导者1首先将标题更新为B，然后更新为C；在领导者2中，它首先更新为C，然后更新为B。没有一种顺序比另一种“更正确”。

If each replica simply applied writes in the order that it saw the writes, the database would end up in an inconsistent state: the final value would be C at leader 1 and B at leader 2. That is not acceptable—every replication scheme must ensure that the data is eventually the same in all replicas. Thus, the database must resolve the conflict in a convergent way, which means that all replicas must arrive at the same final value when all changes have been replicated.

如果每个副本只是按照看到的写入顺序应用写入操作，数据库将最终处于不一致的状态：Leader1的最终值将是C，而Leader2的最终值将是B。这是不可接受的-每个复制方案必须确保最终所有副本中的数据相同。因此，数据库必须以收敛方式解决冲突，这意味着所有副本在复制所有更改后必须到达相同的最终值。

There are various ways of achieving convergent conflict resolution:

有许多实现协调解决冲突的方法：

• Give each write a unique ID (e.g., a timestamp, a long random number, a UUID, or a hash of the key and value), pick the write with the highest ID as the winner , and throw away the other writes. If a timestamp is used, this technique is known as last write wins (LWW). Although this approach is popular, it is dangerously prone to data loss [ 35 ]. We will discuss LWW in more detail at the end of this chapter ( “Detecting Concurrent Writes” ).

  给每个写入一个唯一的ID（例如，时间戳，长随机数，UUID或键值的哈希），选择具有最高ID的写入为赢家，并且丢弃其他写入。如果使用时间戳，这种技术被称为最后写入赢（LWW）。尽管此方法很流行，但极易丢失数据[35]。我们将在本章末尾“检测并发写入”中更详细地讨论LWW。

• Give each replica a unique ID, and let writes that originated at a higher-numbered replica always take precedence over writes that originated at a lower-numbered replica. This approach also implies data loss.

  给每个副本分配唯一的ID，并允许来自较高编号的副本发起的写操作始终优先于来自较低编号的副本的写操作。这种方法也意味着数据丢失。

• Somehow merge the values together—e.g., order them alphabetically and then concatenate them (in Figure 5-7 , the merged title might be something like “B/C”).

  以某种方式将值合并在一起 - 例如，按字母顺序排列它们，然后将它们连接起来（在5-7图中，合并后的标题可能是“B / C”之类的东西）。

• Record the conflict in an explicit data structure that preserves all information, and write application code that resolves the conflict at some later time (perhaps by prompting the user).

  将冲突记录在显式数据结构中，以保留所有信息，并编写应用程序代码以在以后的某个时间解决冲突（可能通过提示用户）。

Custom conflict resolution logic

As the most appropriate way of resolving a conflict may depend on the application, most multi-leader replication tools let you write conflict resolution logic using application code. That code may be executed on write or on read:

由于解决冲突的最适当方式可能取决于应用程序，因此大多数多领导者复制工具可以使用应用程序代码编写冲突解决逻辑。该代码可以在写入或读取时执行。

On write

As soon as the database system detects a conflict in the log of replicated changes, it calls the conflict handler. For example, Bucardo allows you to write a snippet of Perl for this purpose. This handler typically cannot prompt a user—it runs in a background process and it must execute quickly.

当数据库系统检测到复制更改日志中的冲突时，它会调用冲突处理程序。例如，Bucardo允许您编写一个Perl片段来处理此类冲突。此处理程序通常无法提示用户-它在后台进程中运行，并且必须快速执行。

On read

When a conflict is detected, all the conflicting writes are stored. The next time the data is read, these multiple versions of the data are returned to the application. The application may prompt the user or automatically resolve the conflict, and write the result back to the database. CouchDB works this way, for example.

当检测到冲突时，所有冲突的写操作都被存储。下一次数据被读取时，这些数据的多个版本将返回到应用程序中。应用程序可以提示用户或自动解决冲突，并将结果写回到数据库。例如，CouchDB就是这样工作的。

Note that conflict resolution usually applies at the level of an individual row or document, not for an entire transaction [ 36 ]. Thus, if you have a transaction that atomically makes several different writes (see Chapter 7 ), each write is still considered separately for the purposes of conflict resolution.

需要注意的是，冲突解决通常适用于单个行或文档级别，而不是整个事务[36]。因此，如果您有一个原子地进行多个不同写入的事务（见第7章），则每个写入仍然被单独考虑用于冲突解决的目的。

What is a conflict?

Some kinds of conflict are obvious. In the example in Figure 5-7 , two writes concurrently modified the same field in the same record, setting it to two different values. There is little doubt that this is a conflict.

一些冲突是显而易见的。在图5-7的例子中，两个写操作同时修改了同一条记录中的同一字段，将其设置为两个不同的值。毫无疑问，这是一种冲突。

Other kinds of conflict can be more subtle to detect. For example, consider a meeting room booking system: it tracks which room is booked by which group of people at which time. This application needs to ensure that each room is only booked by one group of people at any one time (i.e., there must not be any overlapping bookings for the same room). In this case, a conflict may arise if two different bookings are created for the same room at the same time. Even if the application checks availability before allowing a user to make a booking, there can be a conflict if the two bookings are made on two different leaders.

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

There isn’t a quick ready-made answer, but in the following chapters we will trace a path toward a good understanding of this problem. We will see some more examples of conflicts in Chapter 7 , and in Chapter 12 we will discuss scalable approaches for detecting and resolving conflicts in a replicated system.

这个问题没有快速现成的答案，但是在接下来的章节中，我们会追溯一条路径，以便更好地理解这个问题。在第七章中，我们将看到更多的冲突示例，在第十二章中，我们将讨论检测和解决复制系统中冲突的可扩展方法。

Read repair and anti-entropy

The replication scheme should ensure that eventually all the data is copied to every replica. After an unavailable node comes back online, how does it catch up on the writes that it missed?

复制方案应确保最终所有数据都被复制到每个副本。当一个不可用的节点重新联机后，它如何追赶它错过的写入呢？

Two mechanisms are often used in Dynamo-style datastores:

通常在 Dynamo 风格的数据存储中使用了两种机制：

Read repair

When a client makes a read from several nodes in parallel, it can detect any stale responses. For example, in Figure 5-10 , user 2345 gets a version 6 value from replica 3 and a version 7 value from replicas 1 and 2. The client sees that replica 3 has a stale value and writes the newer value back to that replica. This approach works well for values that are frequently read.

当客户端并行从多个节点读取时，它可以检测到任何过时的响应。例如，在图5-10中，用户 2345 从复制品 3 获取版本 6 的值，并从副本 1 和 2 中获取版本 7 的值。客户端发现复制品 3 有一个过时的值，然后将更新的值写回该复制品。这种方法适用于频繁读取的值。

Anti-entropy process

In addition, some datastores have a background process that constantly looks for differences in the data between replicas and copies any missing data from one replica to another. Unlike the replication log in leader-based replication, this anti-entropy process does not copy writes in any particular order, and there may be a significant delay before data is copied.

此外，一些数据存储具有后台进程，不断查找副本之间数据的差异，并将任何缺失的数据从一个副本复制到另一个副本。与基于领导者的复制中的复制日志不同，此反熵过程不按任何特定顺序复制写入，并且数据复制可能会有显着延迟。

Not all systems implement both of these; for example, Voldemort currently does not have an anti-entropy process. Note that without an anti-entropy process, values that are rarely read may be missing from some replicas and thus have reduced durability, because read repair is only performed when a value is read by the application.

并非所有的系统都实现了这两种方法，例如目前 Voldemort 就没有一个反熵过程。请注意，如果没有反熵过程，很少被读取的值可能会在某些副本中丢失，从而降低了其耐用性，因为只有在应用程序读取一个值时才会进行读取修复。

Quorums for reading and writing

In the example of Figure 5-10 , we considered the write to be successful even though it was only processed on two out of three replicas. What if only one out of three replicas accepted the write? How far can we push this?

在图5-10的示例中，即使仅在三个副本中处理了两个，我们仍考虑写操作是成功的。如果只有三个副本中的一个接受了写入，我们可以推到多远？

If we know that every successful write is guaranteed to be present on at least two out of three replicas, that means at most one replica can be stale. Thus, if we read from at least two replicas, we can be sure that at least one of the two is up to date. If the third replica is down or slow to respond, reads can nevertheless continue returning an up-to-date value.

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

More generally, if there are n replicas, every write must be confirmed by w nodes to be considered successful, and we must query at least r nodes for each read. (In our example, n = 3, w = 2, r = 2.) As long as w + r > n , we expect to get an up-to-date value when reading, because at least one of the r nodes we’re reading from must be up to date. Reads and writes that obey these r and w values are called quorum reads and writes [ 44 ]. ^vii You can think of r and w as the minimum number of votes required for the read or write to be valid.

一般来说，如果有n个副本，每次写入必须得到w个节点的确认才能被视为成功，每次读取时我们必须查询至少r个节点。(在我们的例子中，n=3，w=2，r=2）。只要w+r>n，我们预计在读取时能得到最新的值，因为我们至少会从r个节点中得到一个最新值。遵守这些r和w值的读写称为"quorum reads and writes"[44]。你可以把r和w看作读写操作所需的最小投票数，以确定其是否有效。

In Dynamo-style databases, the parameters n , w , and r are typically configurable. A common choice is to make n an odd number (typically 3 or 5) and to set w = r = ( n + 1) / 2 (rounded up). However, you can vary the numbers as you see fit. For example, a workload with few writes and many reads may benefit from setting w = n and r = 1. This makes reads faster, but has the disadvantage that just one failed node causes all database writes to fail.

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

The quorum condition, w + r > n , allows the system to tolerate unavailable nodes as follows:

法定人数条件w+r>n允许系统在以下情况下容忍不可用节点：

• If w < n , we can still process writes if a node is unavailable.

  如果w < n，即使节点不可用，我们仍然可以处理写操作。

• If r < n , we can still process reads if a node is unavailable.

  如果 r < n，即使节点不可用，我们仍然可以处理读取。

• With n = 3, w = 2, r = 2 we can tolerate one unavailable node.

  当n = 3，w = 2，r = 2时，我们可以容忍一个不可用节点。

• With n = 5, w = 3, r = 3 we can tolerate two unavailable nodes. This case is illustrated in Figure 5-11 .

  当n = 5，w = 3，r = 3时，我们可以容忍两个不可用的节点。此情况在图5-11中说明。

• Normally, reads and writes are always sent to all n replicas in parallel. The parameters w and r determine how many nodes we wait for—i.e., how many of the n nodes need to report success before we consider the read or write to be successful.

  通常情况下，读写操作总是并行发送到所有的n个副本。参数w和r决定我们等待多少个节点——即多少个n个节点需要报告成功，我们才认为读写操作成功。

Figure 5-11. If w + r > n , at least one of the r replicas you read from must have seen the most recent successful write.

If fewer than the required w or r nodes are available, writes or reads return an error. A node could be unavailable for many reasons: because the node is down (crashed, powered down), due to an error executing the operation (can’t write because the disk is full), due to a network interruption between the client and the node, or for any number of other reasons. We only care whether the node returned a successful response and don’t need to distinguish between different kinds of fault.

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

Monitoring staleness

From an operational perspective, it’s important to monitor whether your databases are returning up-to-date results. Even if your application can tolerate stale reads, you need to be aware of the health of your replication. If it falls behind significantly, it should alert you so that you can investigate the cause (for example, a problem in the network or an overloaded node).

从操作角度看，监视数据库是否返回最新结果非常重要。即使您的应用程序可以容忍陈旧的读取，您也需要了解复制的健康状况。如果它落后很多，它应该向您发出警报，以便您可以调查原因（例如，在网络中出现问题或节点超载）。

For leader-based replication, the database typically exposes metrics for the replication lag, which you can feed into a monitoring system. This is possible because writes are applied to the leader and to followers in the same order, and each node has a position in the replication log (the number of writes it has applied locally). By subtracting a follower’s current position from the leader’s current position, you can measure the amount of replication lag.

针对基于领导者的复制，数据库通常公开用于复制滞后度的度量标准，您可以将其输入监控系统。这是可能的，因为写入按照相同顺序应用于领导者和关注者，并且每个节点在复制日志中都有一个位置（它已经本地应用的写入数量）。通过从关注者的当前位置减去领导者的当前位置，您可以测量复制滞后的量。

However, in systems with leaderless replication, there is no fixed order in which writes are applied, which makes monitoring more difficult. Moreover, if the database only uses read repair (no anti-entropy), there is no limit to how old a value might be—if a value is only infrequently read, the value returned by a stale replica may be ancient.

然而，在没有领导的复制系统中，写入应用的顺序是没有固定的，这使得监视更加困难。此外，如果数据库仅使用读修复而没有反熵机制，则值可能非常陈旧 - 如果一个值很少被读取，那么由过时副本返回的值可能已经过时。

There has been some research on measuring replica staleness in databases with leaderless replication and predicting the expected percentage of stale reads depending on the parameters n , w , and r [ 48 ]. This is unfortunately not yet common practice, but it would be good to include staleness measurements in the standard set of metrics for databases. Eventual consistency is a deliberately vague guarantee, but for operability it’s important to be able to quantify “eventual.”

已经进行了一些研究，用于在无领导副本复制的数据库中测量副本陈旧度，并根据参数n、w和r [48] 预测期望的陈旧读取百分比。不幸的是，这还不是普遍的做法，但将陈旧度测量包括在数据库的标准指标集中将是很好的。最终一致性是一种故意模糊的保证，但为了操作能力，量化“最终”非常重要。

Multi-datacenter operation

We previously discussed cross-datacenter replication as a use case for multi-leader replication (see “Multi-Leader Replication” ). Leaderless replication is also suitable for multi-datacenter operation, since it is designed to tolerate conflicting concurrent writes, network interruptions, and latency spikes.

我们之前讨论了跨数据中心复制作为多领袖复制的用例（参见“多首领复制”）。 无领导复制也适用于多数据中心操作，因为它被设计为容忍冲突的并发写入，网络中断和延迟波动。

Cassandra and Voldemort implement their multi-datacenter support within the normal leaderless model: the number of replicas n includes nodes in all datacenters, and in the configuration you can specify how many of the n replicas you want to have in each datacenter. Each write from a client is sent to all replicas, regardless of datacenter, but the client usually only waits for acknowledgment from a quorum of nodes within its local datacenter so that it is unaffected by delays and interruptions on the cross-datacenter link. The higher-latency writes to other datacenters are often configured to happen asynchronously, although there is some flexibility in the configuration [ 50 , 51 ].

Cassandra和Voldemort在常规无领导模式下实现了它们的多数据中心支持：副本数n包括所有数据中心的节点，并且在配置中可以指定要在每个数据中心中拥有多少个n副本。每个客户端的写操作都发送到所有副本，而不管数据中心，但客户端通常只等待其本地数据中心内的节点数量达到法定人数以获得确认，因此才不会受到跨数据中心链接的延迟和中断的影响。对于其他数据中心的高延迟写操作通常配置为异步执行，尽管在配置中还有一定的灵活性[50，51]。

Riak keeps all communication between clients and database nodes local to one datacenter, so n describes the number of replicas within one datacenter. Cross-datacenter replication between database clusters happens asynchronously in the background, in a style that is similar to multi-leader replication [ 52 ].

Riak将客户端与数据库节点之间的所有通信都保持在一个数据中心内，因此n描述了一个数据中心内的副本数量。不同数据中心之间的数据库集群之间的交叉数据中心复制会以类似于多个领导者复制的方式在后台异步进行。

Last write wins (discarding concurrent writes)

One approach for achieving eventual convergence is to declare that each replica need only store the most “recent” value and allow “older” values to be overwritten and discarded. Then, as long as we have some way of unambiguously determining which write is more “recent,” and every write is eventually copied to every replica, the replicas will eventually converge to the same value.

达到最终收敛的方法之一是声明每个副本只需存储最“新”的值，允许“旧”的值被覆盖和丢弃。然后，只要我们有一种明确确定哪个写入更“新”的方法，并且每个写入最终都复制到每个副本，副本最终将收敛到相同的值。

As indicated by the quotes around “recent,” this idea is actually quite misleading. In the example of Figure 5-12 , neither client knew about the other one when it sent its write requests to the database nodes, so it’s not clear which one happened first. In fact, it doesn’t really make sense to say that either happened “first”: we say the writes are concurrent , so their order is undefined.

由于“recent”周围的引号，这个想法实际上是非常具有误导性的。在图5-12的例子中，当它发送写请求到数据库节点时，两个客户端都不知道对方的存在，因此不清楚哪个首先发生。事实上，说其中任何一个先发生都没有意义：我们说写操作是并发的，因此它们的顺序是未定义的。

Even though the writes don’t have a natural ordering, we can force an arbitrary order on them. For example, we can attach a timestamp to each write, pick the biggest timestamp as the most “recent,” and discard any writes with an earlier timestamp. This conflict resolution algorithm, called last write wins (LWW), is the only supported conflict resolution method in Cassandra [ 53 ], and an optional feature in Riak [ 35 ].

尽管写入没有自然的顺序，我们可以强制在它们上面施加任意的顺序。例如，我们可以为每个写入连接一个时间戳，选择最大的时间戳作为最“近期”的，丢弃任何具有较早时间戳的写入。这个冲突解决算法叫做最后写入获胜（LWW），是Cassandra中唯一支持的冲突解决方法[53]，也是Riak中的可选功能[35]。

LWW achieves the goal of eventual convergence, but at the cost of durability: if there are several concurrent writes to the same key, even if they were all reported as successful to the client (because they were written to w replicas), only one of the writes will survive and the others will be silently discarded. Moreover, LWW may even drop writes that are not concurrent, as we shall discuss in “Timestamps for ordering events” .

LWW可实现最终收敛目标，但以耐用性为代价：如果有多个并发写入相同的键，即使它们都被报告给客户端（因为它们被写入w个副本），只有一个写入将生存，而其他写入将被静默丢弃。此外，LWW甚至可能会删除不并发的写入，如我们将在“用于排序事件的时间戳”中讨论的那样。

There are some situations, such as caching, in which lost writes are perhaps acceptable. If losing data is not acceptable, LWW is a poor choice for conflict resolution.

在某些情况下，如缓存中，一些丢失的写入也许是可以接受的。如果数据丢失是不可接受的，LWW 是一个冲突解决的劣选择。

The only safe way of using a database with LWW is to ensure that a key is only written once and thereafter treated as immutable, thus avoiding any concurrent updates to the same key. For example, a recommended way of using Cassandra is to use a UUID as the key, thus giving each write operation a unique key [ 53 ].

使用LWW和数据库的唯一安全方式是确保一个键只被写入一次，然后被视为不可变，以避免任何并发更新相同的键。例如，建议使用Cassandra的一种方法是使用UUID作为键，从而为每个写操作提供一个唯一的键[53]。

The “happens-before” relationship and concurrency

How do we decide whether two operations are concurrent or not? To develop an intuition, let’s look at some examples:

我们如何确定两个操作是否并发？为了发展直觉，让我们来看几个例子：

• In Figure 5-9 , the two writes are not concurrent: A’s insert happens before B’s increment, because the value incremented by B is the value inserted by A. In other words, B’s operation builds upon A’s operation, so B’s operation must have happened later. We also say that B is causally dependent on A.

  在图5-9中，两个写操作不是并发的：A的插入操作发生在B的递增操作之前，因为B递增的值是A插入的值。换句话说，B的操作建立在A的操作上，因此B的操作必须是后发生的。我们还可以说B在因果上依赖于A。

• On the other hand, the two writes in Figure 5-12 are concurrent: when each client starts the operation, it does not know that another client is also performing an operation on the same key. Thus, there is no causal dependency between the operations.

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

An operation A happens before another operation B if B knows about A, or depends on A, or builds upon A in some way. Whether one operation happens before another operation is the key to defining what concurrency means. In fact, we can simply say that two operations are concurrent if neither happens before the other (i.e., neither knows about the other) [ 54 ].

如果B知道A，或者依赖于A，或者以某种方式建立在A之上，则操作A发生在另一个操作B之前。一个操作是否在另一个操作之前发生是定义并发的关键。实际上，我们可以简单地说，如果两个操作都不知道对方，则它们是并发的（也就是说，都不知道对方） [54]。

Thus, whenever you have two operations A and B, there are three possibilities: either A happened before B, or B happened before A, or A and B are concurrent. What we need is an algorithm to tell us whether two operations are concurrent or not. If one operation happened before another, the later operation should overwrite the earlier operation, but if the operations are concurrent, we have a conflict that needs to be resolved.

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

Capturing the happens-before relationship

Let’s look at an algorithm that determines whether two operations are concurrent, or whether one happened before another. To keep things simple, let’s start with a database that has only one replica. Once we have worked out how to do this on a single replica, we can generalize the approach to a leaderless database with multiple replicas.

让我们来看一个算法，确定两个操作是并发的还是一个发生在另一个之前。为了保持简单，让我们从只有一个副本的数据库开始。一旦我们弄清楚了如何在单个副本上执行此操作，我们就可以将其推广到具有多个副本的无领导数据库。

Figure 5-13 shows two clients concurrently adding items to the same shopping cart. (If that example strikes you as too inane, imagine instead two air traffic controllers concurrently adding aircraft to the sector they are tracking.) Initially, the cart is empty. Between them, the clients make five writes to the database:

图5-13展示了两个客户端同时向同一个购物车中添加物品的情境。（如果这个例子听起来太无聊了，那么你可以想象一下两个空管员同时添加他们正在追踪的飞机到区域中。）初始时，购物车是空的。两个客户端总共在数据库上进行了五次写操作。

1. Client 1 adds milk to the cart. This is the first write to that key, so the server successfully stores it and assigns it version 1. The server also echoes the value back to the client, along with the version number.

   客户端1将牛奶添加到购物车中。这是对该键的第一次写入，因此服务器成功存储并分配版本1。服务器还将值回显到客户端，同时附带版本号。

2. Client 2 adds eggs to the cart, not knowing that client 1 concurrently added milk (client 2 thought that its eggs were the only item in the cart). The server assigns version 2 to this write, and stores eggs and milk as two separate values. It then returns both values to the client, along with the version number of 2.

   客户端2将鸡蛋添加到购物车中，不知道客户端1同时添加了牛奶（客户端2认为它的鸡蛋是购物车中唯一的物品）。服务器将版本2分配给此写入，并将鸡蛋和牛奶存储为两个单独的值。然后将这两个值与版本号2一起返回给客户端。

3. Client 1, oblivious to client 2’s write, wants to add flour to the cart, so it thinks the current cart contents should be [milk, flour] . It sends this value to the server, along with the version number 1 that the server gave client 1 previously. The server can tell from the version number that the write of [milk, flour] supersedes the prior value of [milk] but that it is concurrent with [eggs] . Thus, the server assigns version 3 to [milk, flour] , overwrites the version 1 value [milk] , but keeps the version 2 value [eggs] and returns both remaining values to the client.

   客户端1不知道客户端2的写入操作，想向购物车添加面粉，因此它认为当前购物车内容应该是[牛奶，面粉]。它将这个值与服务器之前给客户端1的版本号1一起发送到服务器。从版本号可以看出，[牛奶，面粉]的写入操作取代了以前的值[牛奶]但与[鸡蛋]并发。因此，服务器将版本3分配给[牛奶，面粉]，覆盖版本1的值[牛奶]，但保留版本2的值[鸡蛋]并将两个剩余的值返回给客户端。

4. Meanwhile, client 2 wants to add ham to the cart, unaware that client 1 just added flour . Client 2 received the two values [milk] and [eggs] from the server in the last response, so the client now merges those values and adds ham to form a new value, [eggs, milk, ham] . It sends that value to the server, along with the previous version number 2. The server detects that version 2 overwrites [eggs] but is concurrent with [milk, flour] , so the two remaining values are [milk, flour] with version 3, and [eggs, milk, ham] with version 4.

   与此同时，客户2想要将火腿添加到购物车中，不知道客户1只是添加了面粉。客户2在上次响应中从服务器接收到了两个值[milk]和[eggs]，所以客户现在合并这些值并添加火腿来形成一个新值[eggs，milk，ham]。它将该值发送到服务器，以及先前的版本号2。服务器检测到版本2覆盖了[eggs]，但与[milk，flour]并发，因此剩下的两个值是[milk，flour]版本3和[eggs，milk，ham]版本4。

5. Finally, client 1 wants to add bacon . It previously received [milk, flour] and [eggs] from the server at version 3, so it merges those, adds bacon , and sends the final value [milk, flour, eggs, bacon] to the server, along with the version number 3. This overwrites [milk, flour] (note that [eggs] was already overwritten in the last step) but is concurrent with [eggs, milk, ham] , so the server keeps those two concurrent values.

   最终，客户端1想要加入培根。它之前从版本3的服务器上收到了[牛奶，面粉]和[鸡蛋]，于是它合并了这些值并添加了培根，最终发送值[milk，flour，eggs，bacon]以及版本号3到服务器。这将覆盖[milk，flour]（请注意，[eggs]已经在上一步被覆盖了），但与[eggs，milk，ham]并发，因此服务器保留这两个并发的值。

Figure 5-13. Capturing causal dependencies between two clients concurrently editing a shopping cart.

The dataflow between the operations in Figure 5-13 is illustrated graphically in Figure 5-14 . The arrows indicate which operation happened before which other operation, in the sense that the later operation knew about or depended on the earlier one. In this example, the clients are never fully up to date with the data on the server, since there is always another operation going on concurrently. But old versions of the value do get overwritten eventually, and no writes are lost.

图5-13中操作之间的数据流在图5-14中以图形化的方式呈现。箭头表示哪一个操作发生在另一个操作之前，即后面的操作知道或依赖于前面的操作。在这个例子中，由于总是有另一个操作在同时进行，所以客户端从未完全更新服务器上的数据。但是旧版的值最终会被覆盖，且没有写操作会丢失。

Figure 5-14. Graph of causal dependencies in Figure 5-13 .

Note that the server can determine whether two operations are concurrent by looking at the version numbers—it does not need to interpret the value itself (so the value could be any data structure). The algorithm works as follows:

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

• The server maintains a version number for every key, increments the version number every time that key is written, and stores the new version number along with the value written.

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

• When a client reads a key, the server returns all values that have not been overwritten, as well as the latest version number. A client must read a key before writing.

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

• When a client writes a key, it must include the version number from the prior read, and it must merge together all values that it received in the prior read. (The response from a write request can be like a read, returning all current values, which allows us to chain several writes like in the shopping cart example.)

  当客户端写入一个键时，它必须包含先前读取的版本号，并将先前读取的所有值合并在一起。(写请求的响应可以像读取一样返回所有当前值，这使我们可以像购物车示例中那样链接几个写操作。)

• When the server receives a write with a particular version number, it can overwrite all values with that version number or below (since it knows that they have been merged into the new value), but it must keep all values with a higher version number (because those values are concurrent with the incoming write).

  当服务器接收到特定版本号的写操作时，它可以覆盖所有该版本号及以下的值（因为它知道它们已被合并到新值中），但必须保留所有高版本号的值（因为这些值与传入的写操作并发）。

When a write includes the version number from a prior read, that tells us which previous state the write is based on. If you make a write without including a version number, it is concurrent with all other writes, so it will not overwrite anything—it will just be returned as one of the values on subsequent reads.

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

Merging concurrently written values

This algorithm ensures that no data is silently dropped, but it unfortunately requires that the clients do some extra work: if several operations happen concurrently, clients have to clean up afterward by merging the concurrently written values. Riak calls these concurrent values siblings .

这个算法确保不会静默丢失任何数据，但不幸的是，它要求客户做一些额外的工作：如果有几个操作同时发生，客户必须通过合并并发写入的值来清理。Riak称这些并发值为“同胞”。

Merging sibling values is essentially the same problem as conflict resolution in multi-leader replication, which we discussed previously (see “Handling Write Conflicts” ). A simple approach is to just pick one of the values based on a version number or timestamp (last write wins), but that implies losing data. So, you may need to do something more intelligent in application code.

合并兄弟节点的值本质上与多个领导者复制中的冲突解决问题相同，我们之前讨论过（请参见“处理写入冲突”）。一个简单的方法是基于版本号或时间戳选择一个值（最后一个写入者获胜），但这意味着会丢失数据。因此，在应用程序代码中，您可能需要做一些更智能的处理。

With the example of a shopping cart, a reasonable approach to merging siblings is to just take the union. In Figure 5-14 , the two final siblings are [milk, flour, eggs, bacon] and [eggs, milk, ham] ; note that milk and eggs appear in both, even though they were each only written once. The merged value might be something like [milk, flour, eggs, bacon, ham] , without duplicates.

在购物车的示例中，合并兄弟节点的合理方法是取并集。在图5-14中，最终的两个兄弟节点是[milk，flour，eggs，bacon]和[eggs，milk，ham]；请注意，牛奶和鸡蛋出现在两者中，即使它们仅被写入一次。合并后的值可能类似于[milk，flour，eggs，bacon，ham]，不包括重复项。

However, if you want to allow people to also remove things from their carts, and not just add things, then taking the union of siblings may not yield the right result: if you merge two sibling carts and an item has been removed in only one of them, then the removed item will reappear in the union of the siblings [ 37 ]. To prevent this problem, an item cannot simply be deleted from the database when it is removed; instead, the system must leave a marker with an appropriate version number to indicate that the item has been removed when merging siblings. Such a deletion marker is known as a tombstone . (We previously saw tombstones in the context of log compaction in “Hash Indexes” .)

然而，如果您希望允许用户从购物车中删除物品，而不仅仅是添加物品，则合并兄弟节点的并集可能不会产生正确的结果：如果合并了两个兄弟购物车，并且有一项物品仅在其中一个购物车中被删除，则已删除的物品将重新出现在兄弟节点的并集中[37]。为了避免这个问题，当一个物品被移除时，不能只是从数据库中简单地删除它；相反，系统必须留下一个带有适当版本号的标记，以指示该物品已被移除当合并兄弟节点时。这样的删除标记被称为tombstone。（我们在“哈希索引”中曾经看到过tombstone在日志压缩的上下文中的应用。）

As merging siblings in application code is complex and error-prone, there are some efforts to design data structures that can perform this merging automatically, as discussed in “Automatic Conflict Resolution” . For example, Riak’s datatype support uses a family of data structures called CRDTs [ 38 , 39 , 55 ] that can automatically merge siblings in sensible ways, including preserving deletions.

由于在应用程序代码中合并兄弟节点很复杂且容易出错，因此有一些努力设计数据结构，可以自动执行此合并，正如“自动冲突解决”所讨论的那样。例如，Riak 的数据类型支持使用称为 CRDTs 的一系列数据结构 [38，39，55]，可以以明智的方式自动合并兄弟节点，包括保留删除操作。

Version vectors

The example in Figure 5-13 used only a single replica. How does the algorithm change when there are multiple replicas, but no leader?

当有多个副本但没有领导者时，图5-13中的示例仅使用单个副本。算法如何发生改变？

Figure 5-13 uses a single version number to capture dependencies between operations, but that is not sufficient when there are multiple replicas accepting writes concurrently. Instead, we need to use a version number per replica as well as per key. Each replica increments its own version number when processing a write, and also keeps track of the version numbers it has seen from each of the other replicas. This information indicates which values to overwrite and which values to keep as siblings.

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

The collection of version numbers from all the replicas is called a version vector [ 56 ]. A few variants of this idea are in use, but the most interesting is probably the dotted version vector [ 57 ], which is used in Riak 2.0 [ 58 , 59 ]. We won’t go into the details, but the way it works is quite similar to what we saw in our cart example.

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

Like the version numbers in Figure 5-13 , version vectors are sent from the database replicas to clients when values are read, and need to be sent back to the database when a value is subsequently written. (Riak encodes the version vector as a string that it calls causal context .) The version vector allows the database to distinguish between overwrites and concurrent writes.

像图5-13中的版本号一样，当值被读取时，版本向量从数据库副本发送到客户端，并在随后写入值时需要发送回数据库。(Riak将版本向量编码为称为因果上下文的字符串。)版本向量允许数据库区分覆盖写和并发写。

Also, like in the single-replica example, the application may need to merge siblings. The version vector structure ensures that it is safe to read from one replica and subsequently write back to another replica. Doing so may result in siblings being created, but no data is lost as long as siblings are merged correctly.

同样地，就像在单副本示例中一样，应用程序可能需要合并兄弟节点。版本向量结构确保从一个副本中读取并随后写回另一个副本是安全的。这样做可能会导致创建兄弟节点，但只要正确合并兄弟节点，就不会丢失任何数据。