Locking and leader election

A system that uses single-leader replication needs to ensure that there is indeed only one leader, not several (split brain). One way of electing a leader is to use a lock: every node that starts up tries to acquire the lock, and the one that succeeds becomes the leader [ 14 ]. No matter how this lock is implemented, it must be linearizable: all nodes must agree which node owns the lock; otherwise it is useless.

使用单主副本的系统需要确保确实只有一个领导者而不是多个(分离脑). 选举领导者的一种方法是使用锁：每个启动的节点都尝试获得锁，成功的节点成为领导者[14]. 无论如何实现这个锁，它必须是线性化的：所有节点必须同意哪个节点拥有锁；否则它是无用的。

Coordination services like Apache ZooKeeper [ 15 ] and etcd [ 16 ] are often used to implement distributed locks and leader election. They use consensus algorithms to implement linearizable operations in a fault-tolerant way (we discuss such algorithms later in this chapter, in “Fault-Tolerant Consensus” ). ⁱⁱⁱ There are still many subtle details to implementing locks and leader election correctly (see for example the fencing issue in “The leader and the lock” ), and libraries like Apache Curator [ 17 ] help by providing higher-level recipes on top of ZooKeeper. However, a linearizable storage service is the basic foundation for these coordination tasks.

类似Apache ZooKeeper和etcd这样的协调服务通常用于实现分布式锁和领导者选举。它们使用共识算法以容错方式实现线性化操作（我们在本章后面“容错共识”中讨论这些算法）。实现正确的锁和领导者选举仍然存在许多微妙的细节（例如在“领导者和锁”中的栅栏问题），Apache Curator等库提供了在ZooKeeper之上提供更高级别的配方来帮助。然而，线性化存储服务是这些协调任务的基础。

Distributed locking is also used at a much more granular level in some distributed databases, such as Oracle Real Application Clusters (RAC) [ 18 ]. RAC uses a lock per disk page, with multiple nodes sharing access to the same disk storage system. Since these linearizable locks are on the critical path of transaction execution, RAC deployments usually have a dedicated cluster interconnect network for communication between database nodes.

分布式锁定还在某些分布式数据库中以更细粒度的级别使用，例如Oracle Real Application Clusters（RAC）[18]。 RAC每页磁盘使用一个锁，多个节点共享对同一磁盘存储系统的访问。由于这些可线性化锁定在事务执行的关键路径上，因此RAC部署通常具有专用的群集互连网络，用于数据库节点之间的通信。

Constraints and uniqueness guarantees

Uniqueness constraints are common in databases: for example, a username or email address must uniquely identify one user, and in a file storage service there cannot be two files with the same path and filename. If you want to enforce this constraint as the data is written (such that if two people try to concurrently create a user or a file with the same name, one of them will be returned an error), you need linearizability.

在数据库中，唯一性约束是很常见的：例如，用户名或电子邮件地址必须唯一地标识一个用户，在文件存储服务中不能有两个具有相同路径和文件名的文件。如果您想在写入数据时强制执行此约束（例如，如果两个人尝试同时创建具有相同名称的用户或文件，则其中一个将返回错误），则需要线性化。

This situation is actually similar to a lock: when a user registers for your service, you can think of them acquiring a “lock” on their chosen username. The operation is also very similar to an atomic compare-and-set, setting the username to the ID of the user who claimed it, provided that the username is not already taken.

这种情况实际上类似于一把锁：当用户注册您的服务时，您可以将其视为获得所选择的用户名的“锁定”。操作也非常类似于原子比较和设置，将用户名设置为声明它的用户ID，前提是该用户名尚未被占用。

Similar issues arise if you want to ensure that a bank account balance never goes negative, or that you don’t sell more items than you have in stock in the warehouse, or that two people don’t concurrently book the same seat on a flight or in a theater. These constraints all require there to be a single up-to-date value (the account balance, the stock level, the seat occupancy) that all nodes agree on.

如果您想确保银行账户余额从不为负，或者仓库存货不会超售，或者两个人不会同时预订同一架飞机或剧院的座位，就会出现类似的问题。所有这些限制都需要有一个最新的值（账户余额、库存水平、座位占用率）得到所有节点的一致认可。

In real applications, it is sometimes acceptable to treat such constraints loosely (for example, if a flight is overbooked, you can move customers to a different flight and offer them compensation for the inconvenience). In such cases, linearizability may not be needed, and we will discuss such loosely interpreted constraints in “Timeliness and Integrity” .

在实际应用中，有时候处理这些约束条件可以放宽一些（举个例子，如果一个航班过度预订，可以把乘客安排到另一个航班，并提供赔偿来安抚），在这种情况下，就不需要线性化，我们将在“及时性和完整性”中探讨这些宽松解释的约束条件。

However, a hard uniqueness constraint, such as the one you typically find in relational databases, requires linearizability. Other kinds of constraints, such as foreign key or attribute constraints, can be implemented without requiring linearizability [ 19 ].

然而，像关系数据库中通常发现的硬独特性约束一样，需要线性化。其他类型的约束，如外键或属性约束，可以在不需要线性化的情况下实现[19]。

Cross-channel timing dependencies

Notice a detail in Figure 9-1 : if Alice hadn’t exclaimed the score, Bob wouldn’t have known that the result of his query was stale. He would have just refreshed the page again a few seconds later, and eventually seen the final score. The linearizability violation was only noticed because there was an additional communication channel in the system (Alice’s voice to Bob’s ears).

请注意图9-1中的一个细节：如果Alice没有大声喊出比分，Bob就不会知道他的查询结果已经过期了。他只会在几秒钟后再次刷新页面，并最终看到最终比分。只有因为系统中有一个额外的通信渠道（Alice的声音传到Bob的耳朵），才会注意到线性一致性的违规行为。

Similar situations can arise in computer systems. For example, say you have a website where users can upload a photo, and a background process resizes the photos to lower resolution for faster download (thumbnails). The architecture and dataflow of this system is illustrated in Figure 9-5 .

类似的情况也会在计算机系统中出现。例如，假设您有一个网站，用户可以上传照片，而一个后台进程会调整照片的分辨率以便更快地下载（缩略图）。此系统的体系结构和数据流程如图9-5所示。

The image resizer needs to be explicitly instructed to perform a resizing job, and this instruction is sent from the web server to the resizer via a message queue (see Chapter 11 ). The web server doesn’t place the entire photo on the queue, since most message brokers are designed for small messages, and a photo may be several megabytes in size. Instead, the photo is first written to a file storage service, and once the write is complete, the instruction to the resizer is placed on the queue.

图片调整器需要明确指示执行调整工作，此指示通过消息队列（见第11章）从Web服务器发送到调整器。Web服务器不会将整个照片放入队列中，因为大多数消息代理都设计用于小型消息，而一张照片可能有几兆字节。相反，照片首先被写入文件存储服务，一旦写入完成，就将调整器的指示放置在队列上。

Figure 9-5. The web server and image resizer communicate both through file storage and a message queue, opening the potential for race conditions.

If the file storage service is linearizable, then this system should work fine. If it is not linearizable, there is the risk of a race condition: the message queue (steps 3 and 4 in Figure 9-5 ) might be faster than the internal replication inside the storage service. In this case, when the resizer fetches the image (step 5), it might see an old version of the image, or nothing at all. If it processes an old version of the image, the full-size and resized images in the file storage become permanently inconsistent.

如果文件存储服务是可线性化的，那么系统应该可以正常工作。如果它不是可线性化的，就存在竞争条件的风险：消息队列（图9-5中的步骤3和4）可能比存储服务内部复制更快。在这种情况下，当调整大小程序获取图像（步骤5）时，它可能会看到旧版本的图像，或者根本什么都看不到。如果处理旧版本的图像，则文件存储中的全尺寸和调整大小后的图像将永久不一致。

This problem arises because there are two different communication channels between the web server and the resizer: the file storage and the message queue. Without the recency guarantee of linearizability, race conditions between these two channels are possible. This situation is analogous to Figure 9-1 , where there was also a race condition between two communication channels: the database replication and the real-life audio channel between Alice’s mouth and Bob’s ears.

这个问题的产生是因为Web服务器和调整器之间存在两个不同的通信渠道：文件存储和消息队列。没有线性化的新近性保证，两个渠道之间可能存在竞争条件。这种情况类似于图9-1，其中也存在两个通信渠道之间的竞赛条件：数据库复制和Alice的嘴和Bob的耳朵之间的现实音频通道。

Linearizability is not the only way of avoiding this race condition, but it’s the simplest to understand. If you control the additional communication channel (like in the case of the message queue, but not in the case of Alice and Bob), you can use alternative approaches similar to what we discussed in “Reading Your Own Writes” , at the cost of additional complexity.

线性一致性并不是避免这种竞争条件的唯一方法，但是它是最容易理解的方法。如果你控制了额外的通信渠道（就像在消息队列的情况下，但不是在Alice和Bob的情况下），你可以使用类似于我们在“读取您自己的写入”的讨论中所讨论的替代方法，但这需要额外的复杂性。

Linearizability and quorums

Intuitively, it seems as though strict quorum reads and writes should be linearizable in a Dynamo-style model. However, when we have variable network delays, it is possible to have race conditions, as demonstrated in Figure 9-6 .

直觉上，严格的法定人数读写应该在Dynamo风格模型中是可线性化的。但是，当我们有可变的网络延迟时，可能会出现竞争条件，如图9-6所示。

Figure 9-6. A nonlinearizable execution, despite using a strict quorum.

In Figure 9-6 , the initial value of x is 0, and a writer client is updating x to 1 by sending the write to all three replicas ( n = 3, w = 3). Concurrently, client A reads from a quorum of two nodes ( r = 2) and sees the new value 1 on one of the nodes. Also concurrently with the write, client B reads from a different quorum of two nodes, and gets back the old value 0 from both.

在图9-6中，x的初始值为0，并且写入客户端通过向所有三个副本（n=3，w=3）发送写操作来将x更新为1。同时，客户端A从两个节点的仲裁中读取（r=2），并在其中一个节点上看到新的值1。同时进行写入，客户端B从不同的两个节点的仲裁中进行读取，并从两个节点中获取旧值0。

The quorum condition is met ( w + r > n ), but this execution is nevertheless not linearizable: B’s request begins after A’s request completes, but B returns the old value while A returns the new value. (It’s once again the Alice and Bob situation from Figure 9-1 .)

达到了法定人数条件（w + r > n），但该执行仍然不是可线性化的：B的请求开始在A的请求完成之后，但B返回了旧值，而A返回了新值。 （这又是图9-1中的爱丽丝和鲍勃情况。）

Interestingly, it is possible to make Dynamo-style quorums linearizable at the cost of reduced performance: a reader must perform read repair (see “Read repair and anti-entropy” ) synchronously, before returning results to the application [ 23 ], and a writer must read the latest state of a quorum of nodes before sending its writes [ 24 , 25 ]. However, Riak does not perform synchronous read repair due to the performance penalty [ 26 ]. Cassandra does wait for read repair to complete on quorum reads [ 27 ], but it loses linearizability if there are multiple concurrent writes to the same key, due to its use of last-write-wins conflict resolution.

有趣的是，Dynamo式环境下的法定人数可以在牺牲性能的前提下实现线性化: 读者必须在同步执行读修复之后才能返回结果给应用程序进行读修复(见“读修复和反熵”），而写者则必须在发送其写入之前读取节点法定人数的最新状态。然而，Riak由于性能惩罚不执行同步读修复。Cassandra会等待法定人数读完成读修复，但是由于使用了最后一次写决定冲突解决方法，如果有多个并发写入同一键，则会失去线性化。

Moreover, only linearizable read and write operations can be implemented in this way; a linearizable compare-and-set operation cannot, because it requires a consensus algorithm [ 28 ].

此外，仅有可线性化的读写操作可以以这种方式实现；线性化的比较和交换操作则不行，因为这需要共识算法 [28]。

In summary, it is safest to assume that a leaderless system with Dynamo-style replication does not provide linearizability.

总的来说，最安全的做法是假设一个没有领导的系统，采用Dynamo风格的复制，不能提供线性可序性。

The CAP theorem

This issue is not just a consequence of single-leader and multi-leader replication: any linearizable database has this problem, no matter how it is implemented. The issue also isn’t specific to multi-datacenter deployments, but can occur on any unreliable network, even within one datacenter. The trade-off is as follows: ^v

这个问题不仅仅是单领导者和多领导者复制的结果：任何线性化数据库都会有这个问题，无论它是如何实现的。这个问题也不是针对多数据中心部署的，但是可能发生在任何不可靠的网络上，甚至在一个数据中心内部也是如此。权衡如下：

• If your application requires linearizability, and some replicas are disconnected from the other replicas due to a network problem, then some replicas cannot process requests while they are disconnected: they must either wait until the network problem is fixed, or return an error (either way, they become unavailable ).

  如果您的应用程序需要线性可操作性，而某些副本由于网络问题与其他副本断开连接，则某些副本在断开连接时无法处理请求：它们必须等待网络问题修复，或返回错误（无论哪种方式，它们都变得不可用）。

• If your application does not require linearizability, then it can be written in a way that each replica can process requests independently, even if it is disconnected from other replicas (e.g., multi-leader). In this case, the application can remain available in the face of a network problem, but its behavior is not linearizable.

  如果您的应用程序不需要线性化，那么可以编写以使每个副本可以独立处理请求的方式，即使它与其他副本断开连接（例如，多领导者）。在这种情况下，应用程序可以在网络问题的情况下保持可用，但其行为不是线性的。

Thus, applications that don’t require linearizability can be more tolerant of network problems. This insight is popularly known as the CAP theorem [ 29 , 30 , 31 , 32 ], named by Eric Brewer in 2000, although the trade-off has been known to designers of distributed databases since the 1970s [ 33 , 34 , 35 , 36 ].

因此，不需要线性化的应用程序可以更容忍网络问题。这个洞见被称为CAP定理[29，30，31，32]，由Eric Brewer在2000年命名，尽管这种权衡已经为分布式数据库的设计者所知道自1970年代开始[33，34，35，36]。

CAP was originally proposed as a rule of thumb, without precise definitions, with the goal of starting a discussion about trade-offs in databases. At the time, many distributed databases focused on providing linearizable semantics on a cluster of machines with shared storage [ 18 ], and CAP encouraged database engineers to explore a wider design space of distributed shared-nothing systems, which were more suitable for implementing large-scale web services [ 37 ]. CAP deserves credit for this culture shift—witness the explosion of new database technologies since the mid-2000s (known as NoSQL).

CAP最初被提出时作为一个经验性的规则，并没有精确的定义，旨在开始一场关于数据库中权衡的讨论。当时，许多分布式数据库都专注于在共享存储的机群上提供可线性化的语义[18]，而CAP鼓励数据库工程师探索更广阔的分布式共享无关系统设计空间，这更适合实现大规模的Web服务[37]。 CAP应该得到这种文化转变的认可，这也证明了自2000年代中期以来新数据库技术的爆炸式增长（称为NoSQL）。

The CAP theorem as formally defined [ 30 ] is of very narrow scope: it only considers one consistency model (namely linearizability) and one kind of fault ( network partitions , ^vi or nodes that are alive but disconnected from each other). It doesn’t say anything about network delays, dead nodes, or other trade-offs. Thus, although CAP has been historically influential, it has little practical value for designing systems [ 9 , 40 ].

CAP 定理在正式定义上非常狭窄[30]，只考虑了一种一致性模型（即线性一致性）和一种故障（网络分割、或节点之间无法连接）。它并未涉及网络延迟、宕机等其他权衡方面。因此，尽管 CAP 在历史上具有影响力，但它对于设计系统几乎没有实际价值[9，40]。

There are many more interesting impossibility results in distributed systems [ 41 ], and CAP has now been superseded by more precise results [ 2 , 42 ], so it is of mostly historical interest today.

在分布式系统中还有许多更有趣的不可能性结果[41]，而CAP理论现在已被更精确的结果[2,42]所取代，因此它今天主要是具有历史意义的。

Linearizability and network delays

Although linearizability is a useful guarantee, surprisingly few systems are actually linearizable in practice. For example, even RAM on a modern multi-core CPU is not linearizable [ 43 ]: if a thread running on one CPU core writes to a memory address, and a thread on another CPU core reads the same address shortly afterward, it is not guaranteed to read the value written by the first thread (unless a memory barrier or fence [ 44 ] is used).

尽管线性化是一个有用的保证，但实际上很少有系统是线性化的。例如，即使是现代多核CPU上的RAM也不是线性化的[43]：如果一个运行在一个CPU核心上的线程写入一个内存地址，另一个CPU核心上的线程短时间后读取相同的地址，则不能保证读取第一个线程写入的值（除非使用了内存屏障或栅栏[44]）。

The reason for this behavior is that every CPU core has its own memory cache and store buffer. Memory access first goes to the cache by default, and any changes are asynchronously written out to main memory. Since accessing data in the cache is much faster than going to main memory [ 45 ], this feature is essential for good performance on modern CPUs. However, there are now several copies of the data (one in main memory, and perhaps several more in various caches), and these copies are asynchronously updated, so linearizability is lost.

这种行为的原因是每个CPU核心都有自己的内存缓存和存储缓冲区。默认情况下，内存访问首先进入缓存，并且任何更改都会异步写入主内存。由于在缓存中访问数据比访问主内存要快得多，[45]，因此这个功能对于现代CPU的良好性能至关重要。然而，现在数据有了几个副本（一个在主内存中，可能还有几个在各种缓存中），这些副本会异步更新，因此失去了线性化。

Why make this trade-off? It makes no sense to use the CAP theorem to justify the multi-core memory consistency model: within one computer we usually assume reliable communication, and we don’t expect one CPU core to be able to continue operating normally if it is disconnected from the rest of the computer. The reason for dropping linearizability is performance , not fault tolerance.

为什么要做出这种折衷？使用CAP定理来证明多核内存一致性模型是毫无意义的：在一台计算机内，我们通常假定通信可靠，而且如果一个CPU核心与其余部分断开连接，我们不指望它能继续正常操作。放弃线性化的原因是为了性能，而不是容错性。

The same is true of many distributed databases that choose not to provide linearizable guarantees: they do so primarily to increase performance, not so much for fault tolerance [ 46 ]. Linearizability is slow—and this is true all the time, not only during a network fault.

许多分布式数据库选择不提供线性化保证，主要是为了提高性能，而不是为了容错性[46]。线性化会降低速度，而且这种情况始终存在，不仅仅是在网络故障期间。

Can’t we maybe find a more efficient implementation of linearizable storage? It seems the answer is no: Attiya and Welch [ 47 ] prove that if you want linearizability, the response time of read and write requests is at least proportional to the uncertainty of delays in the network. In a network with highly variable delays, like most computer networks (see “Timeouts and Unbounded Delays” ), the response time of linearizable reads and writes is inevitably going to be high. A faster algorithm for linearizability does not exist, but weaker consistency models can be much faster, so this trade-off is important for latency-sensitive systems. In Chapter 12 we will discuss some approaches for avoiding linearizability without sacrificing correctness.

我们能否找到更高效的可线性化存储实现呢？看起来答案是否定的：Attiya和Welch在[47]中证明，如果你想要线性化，读写请求的响应时间至少与网络延迟的不确定性成比例。在延迟高度变化的网络中，像大多数计算机网络一样（见“超时和无界延迟”），线性化读写的响应时间不可避免地会很高。更快的线性化算法不存在，但弱一致性模型可以更快，因此这种折衷对于延迟敏感的系统非常重要。在第12章中，我们将讨论一些避免线性化而不牺牲正确性的方法。

The causal order is not a total order

A total order allows any two elements to be compared, so if you have two elements, you can always say which one is greater and which one is smaller. For example, natural numbers are totally ordered: if I give you any two numbers, say 5 and 13, you can tell me that 13 is greater than 5.

全序允许比较任意两个元素，所以如果你有两个元素，总能判断哪个更大哪个更小。例如，自然数是全序的：如果我给你任意两个数字，比如5和13，你可以告诉我13比5大。

However, mathematical sets are not totally ordered: is { a , b } greater than { b , c }? Well, you can’t really compare them, because neither is a subset of the other. We say they are incomparable , and therefore mathematical sets are partially ordered : in some cases one set is greater than another (if one set contains all the elements of another), but in other cases they are incomparable.

数学集合并不完全有序：{a，b}是否比{b，c}大？由于它们互不包含，因此实际上无法进行比较。我们称它们是不可比较的，因此数学集合是部分有序的：在某些情况下，一个集合比另一个集合更大（如果一个集合包含另一个集合的所有元素），但在其他情况下，它们是不可比较的。

The difference between a total order and a partial order is reflected in different database consistency models:

全序和偏序之间的区别反映在不同的数据库一致性模型中：

Linearizability

In a linearizable system, we have a total order of operations: if the system behaves as if there is only a single copy of the data, and every operation is atomic, this means that for any two operations we can always say which one happened first. This total ordering is illustrated as a timeline in Figure 9-4 .

在线性化系统中，我们有操作的总序列：如果系统的行为就像只有一个数据副本一样，并且每个操作都是原子操作，这意味着对于任何两个操作，我们都可以确定哪个操作先发生。这个总序列被展示在图9-4中的时间轴上。

Causality

We said that two operations are concurrent if neither happened before the other (see “The “happens-before” relationship and concurrency” ). Put another way, two events are ordered if they are causally related (one happened before the other), but they are incomparable if they are concurrent. This means that causality defines a partial order , not a total order: some operations are ordered with respect to each other, but some are incomparable.

如果两个操作相互独立，那么我们称它们是并行的（参见“‘先于’关系和并发性”）。换句话说，如果两个事件是有因果关系的（一个事件在另一个事件之前发生），那么它们是有序的，但是如果它们是并发的，则它们是无法比较的。这意味着因果关系定义了部分顺序，而不是完全顺序：一些操作是有序的，而一些操作是无法比较的。

Therefore, according to this definition, there are no concurrent operations in a linearizable datastore: there must be a single timeline along which all operations are totally ordered. There might be several requests waiting to be handled, but the datastore ensures that every request is handled atomically at a single point in time, acting on a single copy of the data, along a single timeline, without any concurrency.

因此，根据这个定义，在一个可线性化的数据存储中不存在并发操作：必须存在一个时间轴，沿该时间轴所有操作都被完全排序。可能有几个请求正在等待处理，但数据存储确保每个请求在单一时间点以原子方式处理，作用于单一数据副本，沿单一时间轴，不包含任何并发。

Concurrency would mean that the timeline branches and merges again—and in this case, operations on different branches are incomparable (i.e., concurrent). We saw this phenomenon in Chapter 5 : for example, Figure 5-14 is not a straight-line total order, but rather a jumble of different operations going on concurrently. The arrows in the diagram indicate causal dependencies—the partial ordering of operations.

并发意味着时间线分支和再次合并 - 在这种情况下，不同分支上的操作是不可比较的（即并发）。我们在第5章中看到了这种现象：例如，图5-14不是一条直线总序，而是一堆不同的操作并发进行。图中的箭头表示因果依赖关系 - 操作的部分排序。

If you are familiar with distributed version control systems such as Git, their version histories are very much like the graph of causal dependencies. Often one commit happens after another, in a straight line, but sometimes you get branches (when several people concurrently work on a project), and merges are created when those concurrently created commits are combined.

如果您熟悉分布式版本控制系统，如Git，它们的版本历史记录非常类似于因果依赖关系的图形。通常一个提交发生在另一个提交之后，呈直线状态，但有时会出现分支(当几个人同时在一个项目上工作时)，并且当同时创建的提交合并时也会创建分支。

Linearizability is stronger than causal consistency

So what is the relationship between the causal order and linearizability? The answer is that linearizability implies causality: any system that is linearizable will preserve causality correctly [ 7 ]. In particular, if there are multiple communication channels in a system (such as the message queue and the file storage service in Figure 9-5 ), linearizability ensures that causality is automatically preserved without the system having to do anything special (such as passing around timestamps between different components).

什么是因果关系和可线性化之间的关系？答案是线性化意味着因果关系：任何可线性化的系统都会正确地保留因果关系。特别是，在系统中存在多个通信通道（如图9-5中的消息队列和文件存储服务），线性化确保因果关系自动保留，而不需要系统做任何特殊的事情（例如在不同组件之间传递时间戳）。

The fact that linearizability ensures causality is what makes linearizable systems simple to understand and appealing. However, as discussed in “The Cost of Linearizability” , making a system linearizable can harm its performance and availability, especially if the system has significant network delays (for example, if it’s geographically distributed). For this reason, some distributed data systems have abandoned linearizability, which allows them to achieve better performance but can make them difficult to work with.

线性化确保因果关系是使线性化系统易于理解和吸引人的原因。然而，如“线性化成本”所讨论的那样，使系统线性化可能会损害其性能和可用性，特别是如果系统存在重要的网络延迟（例如，如果它地理分布）。因此，一些分布式数据系统已经放弃了线性化，这使它们可以实现更好的性能，但可能使它们难以使用。

The good news is that a middle ground is possible. Linearizability is not the only way of preserving causality—there are other ways too. A system can be causally consistent without incurring the performance hit of making it linearizable (in particular, the CAP theorem does not apply). In fact, causal consistency is the strongest possible consistency model that does not slow down due to network delays, and remains available in the face of network failures [ 2 , 42 ].

好消息是有一个中间地带是可能的。 线性一致性并不是保持因果关系的唯一方法 - 还有其他方法。 一个系统可以在不招致线性一致性的性能损失的情况下保持因果一致性（特别是CAP定理不适用）。 实际上，因果一致性是最强大的一致性模型，它不会因网络延迟而变慢，并且在网络故障时仍然可用[2,42]。

In many cases, systems that appear to require linearizability in fact only really require causal consistency, which can be implemented more efficiently. Based on this observation, researchers are exploring new kinds of databases that preserve causality, with performance and availability characteristics that are similar to those of eventually consistent systems [ 49 , 50 , 51 ].

许多情况下，表面上需要线性化的系统实际上只需要因果一致性，这可以更有效地实现。基于这一发现，研究人员正在探索保留因果关系的新型数据库，其性能和可用性特性类似于最终一致性系统。

As this research is quite recent, not much of it has yet made its way into production systems, and there are still challenges to be overcome [ 52 , 53 ]. However, it is a promising direction for future systems.

由于这项研究相对较新，尚未在生产系统中得到广泛应用，仍然存在一些挑战 [52, 53]。然而，这是未来系统发展的一个有前途的方向。

Capturing causal dependencies

We won’t go into all the nitty-gritty details of how nonlinearizable systems can maintain causal consistency here, but just briefly explore some of the key ideas.

我们不会在这里详细讨论非线性系统如何维持因果一致性的所有细节，但只是简要探讨一些关键的思想。

In order to maintain causality, you need to know which operation happened before which other operation. This is a partial order: concurrent operations may be processed in any order, but if one operation happened before another, then they must be processed in that order on every replica. Thus, when a replica processes an operation, it must ensure that all causally preceding operations (all operations that happened before) have already been processed; if some preceding operation is missing, the later operation must wait until the preceding operation has been processed.

为了保持因果关系，你需要知道哪个操作在哪个操作前发生。这是部分顺序：并发操作可以以任何顺序进行处理，但如果一个操作在另一个操作之前发生，则它们必须在每个副本上以那个顺序进行处理。因此，当副本处理操作时，它必须确保所有因果关系前面的操作（所有已发生的操作）都已经被处理了；如果缺少某个前一操作，则后续操作必须等待前一操作已经被处理。

In order to determine causal dependencies, we need some way of describing the “knowledge” of a node in the system. If a node had already seen the value X when it issued the write Y, then X and Y may be causally related. The analysis uses the kinds of questions you would expect in a criminal investigation of fraud charges: did the CEO know about X at the time when they made decision Y?

为了确定因果依赖关系，我们需要描述系统中节点的“知识”的一些方式。如果节点在发出写入Y时已经看到了值X，则X和Y可能存在因果关系。分析使用了诈骗指控刑事调查中所期望的问题类型：CEO在做出决策Y时是否知道X的存在？

The techniques for determining which operation happened before which other operation are similar to what we discussed in “Detecting Concurrent Writes” . That section discussed causality in a leaderless datastore, where we need to detect concurrent writes to the same key in order to prevent lost updates. Causal consistency goes further: it needs to track causal dependencies across the entire database, not just for a single key. Version vectors can be generalized to do this [ 54 ].

确定哪个操作在哪个其他操作之前发生的技术与我们在“检测并发写入”中讨论过的类似。该部分讨论了在无领导数据存储中的因果关系，我们需要检测对同一关键字的并发写入，以防止丢失更新。 因果一致性更进一步：它需要跟踪整个数据库的因果依赖关系，而不仅仅是单个关键字。 版本向量可以推广到这样做。

In order to determine the causal ordering, the database needs to know which version of the data was read by the application. This is why, in Figure 5-13 , the version number from the prior operation is passed back to the database on a write. A similar idea appears in the conflict detection of SSI, as discussed in “Serializable Snapshot Isolation (SSI)” : when a transaction wants to commit, the database checks whether the version of the data that it read is still up to date. To this end, the database keeps track of which data has been read by which transaction.

为了确定因果关系的顺序，数据库需要知道应用程序读取了哪个数据版本。因此，在图5-13中，先前操作的版本号在写入时传递回数据库。类似的想法出现在SSI的冲突检测中，如“可序列化快照隔离（SSI）”所讨论的那样：当一个事务想要提交时，数据库会检查它所读取的数据版本是否仍然是最新的。为此，数据库跟踪哪些事务已读取了哪些数据。

Noncausal sequence number generators

If there is not a single leader (perhaps because you are using a multi-leader or leaderless database, or because the database is partitioned), it is less clear how to generate sequence numbers for operations. Various methods are used in practice:

如果没有单个领导者（可能是因为使用了多个领导者或无领导者数据库，或者因为数据库被分区），则如何生成操作的序列号就不太清楚了。实践中使用各种方法：

• Each node can generate its own independent set of sequence numbers. For example, if you have two nodes, one node can generate only odd numbers and the other only even numbers. In general, you could reserve some bits in the binary representation of the sequence number to contain a unique node identifier, and this would ensure that two different nodes can never generate the same sequence number.

  每个节点可以生成自己独立的序列号集合。例如，如果有两个节点，则一个节点可以仅生成奇数，另一个节点仅生成偶数。通常，您可以保留序列号的二进制表示中的一些位来包含唯一的节点标识符，这将确保两个不同的节点永远不会生成相同的序列号。

• You can attach a timestamp from a time-of-day clock (physical clock) to each operation [ 55 ]. Such timestamps are not sequential, but if they have sufficiently high resolution, they might be sufficient to totally order operations. This fact is used in the last write wins conflict resolution method (see “Timestamps for ordering events” ).

  可以为每个操作附加一个来自时钟的时间戳（物理时钟）[55]。这些时间戳不是连续的，但如果它们具有足够高的分辨率，则可能足以完全有序操作。这个事实被用于最后写入赢得冲突解决方法（请参阅“时间戳用于事件排序”）。

• You can preallocate blocks of sequence numbers. For example, node A might claim the block of sequence numbers from 1 to 1,000, and node B might claim the block from 1,001 to 2,000. Then each node can independently assign sequence numbers from its block, and allocate a new block when its supply of sequence numbers begins to run low.

  你可以预分配一段序列号的块。例如，节点A可以声称从1到1,000的序列号块，而节点B可以声称从1,001到2,000的块。然后，每个节点可以独立地从其块中分配序列号，并在其序列号供应开始变得不足时分配一个新块。

These three options all perform better and are more scalable than pushing all operations through a single leader that increments a counter. They generate a unique, approximately increasing sequence number for each operation. However, they all have a problem: the sequence numbers they generate are not consistent with causality .

这三个选项都比通过单个领袖推送所有操作并增加计数器更有效，且更具可扩展性。它们为每个操作生成唯一的、近乎递增的序列号。然而，它们都存在一个问题：它们生成的序列号与因果关系不一致。

The causality problems occur because these sequence number generators do not correctly capture the ordering of operations across different nodes:

因果关系问题的发生是因为这些序列号生成器无法正确捕捉不同节点之间操作的顺序。

• Each node may process a different number of operations per second. Thus, if one node generates even numbers and the other generates odd numbers, the counter for even numbers may lag behind the counter for odd numbers, or vice versa. If you have an odd-numbered operation and an even-numbered operation, you cannot accurately tell which one causally happened first.

  每个节点可能每秒处理不同数量的操作。因此，如果一个节点生成偶数，另一个生成奇数，偶数计数器可能落后于奇数计数器，反之亦然。如果你有一个奇数操作和一个偶数操作，你不能准确地判断哪一个先发生了。

• Timestamps from physical clocks are subject to clock skew, which can make them inconsistent with causality. For example, see Figure 8-3 , which shows a scenario in which an operation that happened causally later was actually assigned a lower timestamp. ^viii

  物理时钟的时间戳受到时钟偏差的影响，可能与因果关系不一致。例如，参见图8-3，它展示了一个场景，在该场景中，一个因果上更晚发生的操作实际上被分配了一个较低的时间戳。

• In the case of the block allocator, one operation may be given a sequence number in the range from 1,001 to 2,000, and a causally later operation may be given a number in the range from 1 to 1,000. Here, again, the sequence number is inconsistent with causality.

  在块分配器的情况下，一个操作可能被分配一个序列号，范围从1,001到2,000，后续操作可能被分配一个编号范围在1到1,000之间。在这种情况下，序列号与因果关系不一致。

Lamport timestamps

Although the three sequence number generators just described are inconsistent with causality, there is actually a simple method for generating sequence numbers that is consistent with causality. It is called a Lamport timestamp , proposed in 1978 by Leslie Lamport [ 56 ], in what is now one of the most-cited papers in the field of distributed systems.

尽管刚才描述的三个序列号生成器与因果关系不一致，但实际上有一种简单的方法可以生成序列号，该方法与因果关系一致。这被称为Lamport时间戳，是由Leslie Lamport在1978年提出的，现在是分布式系统领域中最受引用的论文之一。

The use of Lamport timestamps is illustrated in Figure 9-8 . Each node has a unique identifier, and each node keeps a counter of the number of operations it has processed. The Lamport timestamp is then simply a pair of ( counter , node ID ). Two nodes may sometimes have the same counter value, but by including the node ID in the timestamp, each timestamp is made unique.

Lamport时间戳的使用如图9-8所示。每个节点都有一个唯一的标识符，并且每个节点都保留着它已处理的操作数的计数器。 Lamport时间戳只是一个（计数器，节点ID）的对。两个节点有时可能具有相同的计数器值，但通过在时间戳中包含节点ID，每个时间戳都变得唯一。

Figure 9-8. Lamport timestamps provide a total ordering consistent with causality.

A Lamport timestamp bears no relationship to a physical time-of-day clock, but it provides total ordering: if you have two timestamps, the one with a greater counter value is the greater timestamp; if the counter values are the same, the one with the greater node ID is the greater timestamp.

Lamport时间戳与实际日历时间无关，但它提供了全局排序：如果你有两个时间戳，拥有更大计数器值的时间戳更大；如果计数器值相同，则拥有更大节点ID的时间戳更大。

So far this description is essentially the same as the even/odd counters described in the last section. The key idea about Lamport timestamps, which makes them consistent with causality, is the following: every node and every client keeps track of the maximum counter value it has seen so far, and includes that maximum on every request. When a node receives a request or response with a maximum counter value greater than its own counter value, it immediately increases its own counter to that maximum.

目前，这个描述与上一节中描述的奇偶计数器基本相同。 Lamport时间戳的关键思想是使它们与因果关系一致的：每个节点和每个客户端都会跟踪迄今为止看到的最大计数器值，并在每个请求中包括该最大值。当节点收到具有大于自己计数器值的最大计数器值的请求或响应时，它立即将自己的计数器增加到那个最大值。

This is shown in Figure 9-8 , where client A receives a counter value of 5 from node 2, and then sends that maximum of 5 to node 1. At that time, node 1’s counter was only 1, but it was immediately moved forward to 5, so the next operation had an incremented counter value of 6.

这在图9-8中所示，客户端A从节点2接收了计数器值5，然后将最大值5发送到节点1。当时，节点1的计数器仅为1，但它立即向前移动到5，因此下一个操作的计数器值为6。

As long as the maximum counter value is carried along with every operation, this scheme ensures that the ordering from the Lamport timestamps is consistent with causality, because every causal dependency results in an increased timestamp.

只要每次操作都携带最大计数器值，此方案将确保Lamport时间戳的顺序符合因果关系，因为每个因果依赖都会导致时间戳增加。

Lamport timestamps are sometimes confused with version vectors, which we saw in “Detecting Concurrent Writes” . Although there are some similarities, they have a different purpose: version vectors can distinguish whether two operations are concurrent or whether one is causally dependent on the other, whereas Lamport timestamps always enforce a total ordering. From the total ordering of Lamport timestamps, you cannot tell whether two operations are concurrent or whether they are causally dependent. The advantage of Lamport timestamps over version vectors is that they are more compact.

Lamport时间戳有时会与版本向量混淆，我们在“检测并发写入”中已经看到了。虽然有一些相似之处，但它们有不同的目的：版本向量可以区分两个操作是否并发或是否彼此因果相关，而Lamport时间戳始终强制执行完全排序。从Lamport时间戳的完全排序中，您无法确定两个操作是否并发或是否彼此因果相关。与版本向量相比，Lamport时间戳的优点在于它们更紧凑。

Timestamp ordering is not sufficient

Although Lamport timestamps define a total order of operations that is consistent with causality, they are not quite sufficient to solve many common problems in distributed systems.

虽然Lamport时间戳定义了与因果一致的操作总顺序，但它们并不足以解决许多分布式系统中的常见问题。

For example, consider a system that needs to ensure that a username uniquely identifies a user account. If two users concurrently try to create an account with the same username, one of the two should succeed and the other should fail. (We touched on this problem previously in “The leader and the lock” .)

例如，考虑一个需要确保用户名唯一标识用户账户的系统。如果两个用户同时尝试使用相同的用户名创建账户，其中一个应该成功，另一个应该失败。（我们之前在“领导者和锁”中提到过这个问题。）

At first glance, it seems as though a total ordering of operations (e.g., using Lamport timestamps) should be sufficient to solve this problem: if two accounts with the same username are created, pick the one with the lower timestamp as the winner (the one who grabbed the username first), and let the one with the greater timestamp fail. Since timestamps are totally ordered, this comparison is always valid.

乍一看，似乎全面排序操作（例如使用 Lamport 时间戳）足以解决此问题：如果创建了两个具有相同用户名的帐户，请选择时间戳较低的帐户作为获胜者（第一个占用用户名的人），并让时间戳较大的帐户失败。由于时间戳是完全有序的，因此此比较始终有效。

This approach works for determining the winner after the fact: once you have collected all the username creation operations in the system, you can compare their timestamps. However, it is not sufficient when a node has just received a request from a user to create a username, and needs to decide right now whether the request should succeed or fail. At that moment, the node does not know whether another node is concurrently in the process of creating an account with the same username, and what timestamp that other node may assign to the operation.

这种方法适用于事后确定胜者：一旦您收集了系统中所有的用户名创建操作，就可以比较它们的时间戳。但是，当一个节点刚刚收到用户创建用户名的请求，并且需要立即决定请求是成功还是失败时，这种方法是不够的。在那一刻，该节点不知道另一个节点是否正在同时创建具有相同用户名的帐户，以及另一个节点可能为该操作分配的时间戳。

In order to be sure that no other node is in the process of concurrently creating an account with the same username and a lower timestamp, you would have to check with every other node to see what it is doing [ 56 ]. If one of the other nodes has failed or cannot be reached due to a network problem, this system would grind to a halt. This is not the kind of fault-tolerant system that we need.

为确保没有其他节点同时使用相同的用户名和较低的时间戳创建帐户，您需要与每个其他节点检查其正在做什么[56]。 如果其中一个其他节点失败或由于网络问题无法访问，则该系统将停止工作。这不是我们所需的容错系统。

The problem here is that the total order of operations only emerges after you have collected all of the operations. If another node has generated some operations, but you don’t yet know what they are, you cannot construct the final ordering of operations: the unknown operations from the other node may need to be inserted at various positions in the total order.

问题在于只有在收集了所有操作后，操作的总顺序才会出现。如果另一个节点已经生成了一些操作，但您还不知道它们是什么，您不能构建操作的最终顺序：来自其他节点的未知操作可能需要被插入到总顺序的各个位置。

To conclude: in order to implement something like a uniqueness constraint for usernames, it’s not sufficient to have a total ordering of operations—you also need to know when that order is finalized. If you have an operation to create a username, and you are sure that no other node can insert a claim for the same username ahead of your operation in the total order, then you can safely declare the operation successful.

为了实现像用户名唯一性约束这样的东西，仅仅拥有一种操作的完全排序是不够的 - 你还需要知道什么时候这个排序被最终确定。如果你有一个操作来创建一个用户名，并且你确信没有其他节点能在全序中在你的操作之前插入相同的用户名声明，那么你可以安全地声明该操作成功。

This idea of knowing when your total order is finalized is captured in the topic of total order broadcast .

这种在整个订单结束时知道的想法被称为总订单广播的话题所涵盖。

Using total order broadcast

Consensus services such as ZooKeeper and etcd actually implement total order broadcast. This fact is a hint that there is a strong connection between total order broadcast and consensus, which we will explore later in this chapter.

共识服务如ZooKeeper和etcd实际上实现了完全有序广播。这个事实提示完全有序广播和共识之间存在着很强的联系，在本章后面我们将会探讨这一点。

Total order broadcast is exactly what you need for database replication: if every message represents a write to the database, and every replica processes the same writes in the same order, then the replicas will remain consistent with each other (aside from any temporary replication lag). This principle is known as state machine replication [ 60 ], and we will return to it in Chapter 11 .

“全序广播”是数据库复制所需的关键因素：如果每条消息代表对数据库的写入，并且每个副本以相同的顺序处理相同的写入，则各个副本将保持一致（除了任何短暂的复制延迟）。这个原则被称为状态机复制[60]，我们将在第11章中回到它。”

Similarly, total order broadcast can be used to implement serializable transactions: as discussed in “Actual Serial Execution” , if every message represents a deterministic transaction to be executed as a stored procedure, and if every node processes those messages in the same order, then the partitions and replicas of the database are kept consistent with each other [ 61 ].

类似地，全序播送可以用于实现可串行化事务：如同“实际串行执行”中所讨论的，如果每个消息代表一个要作为存储过程执行的确定性事务，且每个节点按相同顺序处理这些消息，则数据库的分区和副本保持一致。

An important aspect of total order broadcast is that the order is fixed at the time the messages are delivered: a node is not allowed to retroactively insert a message into an earlier position in the order if subsequent messages have already been delivered. This fact makes total order broadcast stronger than timestamp ordering.

全序广播的一个重要方面是消息在传递时顺序固定：如果后续消息已经被传递，节点就不允许将消息反向插入到早期位置。这个事实使得全序广播比时间戳排序更加强大。

Another way of looking at total order broadcast is that it is a way of creating a log (as in a replication log, transaction log, or write-ahead log): delivering a message is like appending to the log. Since all nodes must deliver the same messages in the same order, all nodes can read the log and see the same sequence of messages.

另一种理解全序广播的方式是将其视为创建日志的一种方式（例如复制日志、事务日志或预写式日志）：传递消息就像附加到日志中一样。由于所有节点必须按照相同的顺序传递相同的消息，因此所有节点可以读取日志并查看相同的消息序列。

Total order broadcast is also useful for implementing a lock service that provides fencing tokens (see “Fencing tokens” ). Every request to acquire the lock is appended as a message to the log, and all messages are sequentially numbered in the order they appear in the log. The sequence number can then serve as a fencing token, because it is monotonically increasing. In ZooKeeper, this sequence number is called zxid [ 15 ].

全序广播还可用于实现提供围栏令牌的锁定服务（请见“围栏令牌”）。每个请求获取锁都将作为一个消息附加到日志中，并按照它们在日志中出现的顺序进行顺序编号。这个序列号可以作为围栏令牌，因为它是单调递增的。在ZooKeeper中，这个序列号称为zxid [15]。

Implementing linearizable storage using total order broadcast

As illustrated in Figure 9-4 , in a linearizable system there is a total order of operations. Does that mean linearizability is the same as total order broadcast? Not quite, but there are close links between the two. ^x

如图9-4所示，在可线性化的系统中存在操作的总序。这是否意味着线性化与总序广播相同？并非完全如此，但两者之间存在密切联系。

Total order broadcast is asynchronous: messages are guaranteed to be delivered reliably in a fixed order, but there is no guarantee about when a message will be delivered (so one recipient may lag behind the others). By contrast, linearizability is a recency guarantee: a read is guaranteed to see the latest value written.

总订单广播是异步的：保证消息按照固定顺序可靠地传送，但不保证何时传送消息（因此一个收件人可能会落后于其他人）。相比之下，线性一致性是最新性保证：读取保证可以看到最新写入的值。

However, if you have total order broadcast, you can build linearizable storage on top of it. For example, you can ensure that usernames uniquely identify user accounts.

然而，如果您拥有完全有序的广播，则可以在其上构建可线性化的存储。例如，您可以确保用户名唯一地标识用户帐户。

Imagine that for every possible username, you can have a linearizable register with an atomic compare-and-set operation. Every register initially has the value null (indicating that the username is not taken). When a user wants to create a username, you execute a compare-and-set operation on the register for that username, setting it to the user account ID, under the condition that the previous register value is null . If multiple users try to concurrently grab the same username, only one of the compare-and-set operations will succeed, because the others will see a value other than null (due to linearizability).

假设对于每个可能的用户名，您可以拥有一个具有原子比较和设置操作的可线性化寄存器。每个寄存器最初值为 null（表示该用户名尚未被占用）。当用户想要创建用户名时，您执行对该用户名的寄存器的比较和设置操作，在先前的寄存器值为 null 的条件下将其设置为用户帐户 ID。如果多个用户尝试并发获取相同的用户名，则只有一个比较和设置操作将成功，因为其他人将看到一个不为 null 的值（由于可线性化性）。

You can implement such a linearizable compare-and-set operation as follows by using total order broadcast as an append-only log [ 62 , 63 ]:

您可以通过使用全序广播作为仅限追加日志来实现这样的可线性比较和设置操作。[62，63]：

1. Append a message to the log, tentatively indicating the username you want to claim.

   向日志中追加一条消息，暂时指示您想要声明的用户名。

2. Read the log, and wait for the message you appended to be delivered back to you. ^xi

   阅读日志，等待回传给您的消息。

3. Check for any messages claiming the username that you want. If the first message for your desired username is your own message, then you are successful: you can commit the username claim (perhaps by appending another message to the log) and acknowledge it to the client. If the first message for your desired username is from another user, you abort the operation.

   检查是否有任何声称使用您所需用户名的消息。如果您所需用户名的第一条消息是您自己的消息，则您已经成功：您可以提交用户名声明（可能通过将另一条消息附加到日志中）并向客户确认。如果您所需用户名的第一条消息来自另一个用户，则应中止操作。

Because log entries are delivered to all nodes in the same order, if there are several concurrent writes, all nodes will agree on which one came first. Choosing the first of the conflicting writes as the winner and aborting later ones ensures that all nodes agree on whether a write was committed or aborted. A similar approach can be used to implement serializable multi-object transactions on top of a log [ 62 ].

由于日志条目以相同顺序传递到所有节点，如果有多个并发写入，则所有节点将就哪个写入先到达达成一致。选择冲突写入中的第一个作为赢家并放弃后续写入，确保所有节点都同意写入是成功还是中止。类似的方法可用于在日志之上实现可串行化的多对象事务。

While this procedure ensures linearizable writes, it doesn’t guarantee linearizable reads—if you read from a store that is asynchronously updated from the log, it may be stale. (To be precise, the procedure described here provides sequential consistency [ 47 , 64 ], sometimes also known as timeline consistency [ 65 , 66 ], a slightly weaker guarantee than linearizability.) To make reads linearizable, there are a few options:

尽管此过程确保了可线性化的写入，但并不保证可线性化的读取。如果您从记录异步更新的存储器中读取，它可能是过时的。为了使读取可线性化，有几个选择：（要精确，请注意此处描述的过程提供了“顺序一致性”，有时也称为“时间线一致性”，这是比线性一致性稍微弱一些的保证。）

• You can sequence reads through the log by appending a message, reading the log, and performing the actual read when the message is delivered back to you. The message’s position in the log thus defines the point in time at which the read happens. (Quorum reads in etcd work somewhat like this [ 16 ].)

  通过附加消息、读取日志并在消息被发送回您时执行实际读取操作，您可以通过日志对读取进行排序。因此，消息在日志中的位置定义了读取发生的时间点。（etcd 中的 Quorum 读取有些类似这种方式 [16]）。

• If the log allows you to fetch the position of the latest log message in a linearizable way, you can query that position, wait for all entries up to that position to be delivered to you, and then perform the read. (This is the idea behind ZooKeeper’s sync() operation [ 15 ].)

  如果日志允许您以线性化的方式获取最新日志消息的位置，您可以查询该位置，等待所有条目到达该位置，然后执行读取操作。（这就是ZooKeeper的sync()操作的背后思想）

• You can make your read from a replica that is synchronously updated on writes, and is thus sure to be up to date. (This technique is used in chain replication [ 63 ]; see also “Research on Replication” .)

  你可以从一个同步更新写操作的副本中阅读，因此保证它是最新的。这种技术在链式复制中被使用（参见“复制研究”）。

Implementing total order broadcast using linearizable storage

The last section showed how to build a linearizable compare-and-set operation from total order broadcast. We can also turn it around, assume that we have linearizable storage, and show how to build total order broadcast from it.

上一节展示了如何从全序广播构建可线性化的比较和交换操作。我们也可以反过来，假设我们拥有可线性化存储，并展示如何从中构建全序广播。

The easiest way is to assume you have a linearizable register that stores an integer and that has an atomic increment-and-get operation [ 28 ]. Alternatively, an atomic compare-and-set operation would also do the job.

最简单的方式就是假设有一个可以存储整数的可线性化寄存器，并且拥有原子的增加和获取操作[28]。 另一种选择是使用原子的比较并设置操作。

The algorithm is simple: for every message you want to send through total order broadcast, you increment-and-get the linearizable integer, and then attach the value you got from the register as a sequence number to the message. You can then send the message to all nodes (resending any lost messages), and the recipients will deliver the messages consecutively by sequence number.

算法很简单：对于想要通过总序传播发送的每一条消息，你需要递增并获取线性化整数，然后将你从寄存器中获取的值作为序列号附加到消息上。接着你可以将消息发送到所有节点（重新发送任何丢失的消息），收件人将按照序列号依次传递消息。

Note that unlike Lamport timestamps, the numbers you get from incrementing the linearizable register form a sequence with no gaps. Thus, if a node has delivered message 4 and receives an incoming message with a sequence number of 6, it knows that it must wait for message 5 before it can deliver message 6. The same is not the case with Lamport timestamps—in fact, this is the key difference between total order broadcast and timestamp ordering.

请注意，与Lamport时间戳不同，从递增线性寄存器获得的数字形成一个没有间隙的序列。因此，如果节点已经传送了消息4并接收到序列号为6的传入消息，则它知道在传送消息6之前必须等待消息5。对于Lamport时间戳来说，情况并非如此——实际上，这是总序列广播和时间戳排序之间的关键区别。

How hard could it be to make a linearizable integer with an atomic increment-and-get operation? As usual, if things never failed, it would be easy: you could just keep it in a variable on one node. The problem lies in handling the situation when network connections to that node are interrupted, and restoring the value when that node fails [ 59 ]. In general, if you think hard enough about linearizable sequence number generators, you inevitably end up with a consensus algorithm.

“使用原子增量和获取操作来生成可线性化的整数会有多难呢？通常情况下，如果不会出现故障，那么这非常容易实现：在一个节点上将其保留在一个变量中即可。问题在于当与该节点的网络连接中断时，如何处理并在该节点发生故障时恢复该值[59]。一般情况下，如果您足够努力地思考线性序列号生成器，最终会使用共识算法。”

This is no coincidence: it can be proved that a linearizable compare-and-set (or increment-and-get) register and total order broadcast are both equivalent to consensus [ 28 , 67 ]. That is, if you can solve one of these problems, you can transform it into a solution for the others. This is quite a profound and surprising insight!

这不是巧合：可以证明，可线性化的比较并设置（或增量并获取）寄存器和全序广播都等价于共识[28，67]。也就是说，如果你可以解决其中一个问题，你可以将其转化为其他问题的解决方案。这是一个相当深刻和令人惊讶的见解！

It is time to finally tackle the consensus problem head-on, which we will do in the rest of this chapter.

到了终于直面共识问题的时候了，我们将在本章的其余部分来解决它。

From single-node to distributed atomic commit

For transactions that execute at a single database node, atomicity is commonly implemented by the storage engine. When the client asks the database node to commit the transaction, the database makes the transaction’s writes durable (typically in a write-ahead log; see “Making B-trees reliable” ) and then appends a commit record to the log on disk. If the database crashes in the middle of this process, the transaction is recovered from the log when the node restarts: if the commit record was successfully written to disk before the crash, the transaction is considered committed; if not, any writes from that transaction are rolled back.

针对在单个数据库节点执行的交易，通常由存储引擎来实现原子性。当客户端要求数据库节点提交交易时，数据库会将交易写入持久化存储（通常是写前日志；参见“使B树可靠”），然后在磁盘上附加提交记录。如果数据库在此过程中崩溃，则节点重新启动时从日志中恢复交易：如果提交记录在崩溃之前成功写入磁盘，则认为交易已提交；否则，来自该交易的任何写操作都将回滚。

Thus, on a single node, transaction commitment crucially depends on the order in which data is durably written to disk: first the data, then the commit record [ 72 ]. The key deciding moment for whether the transaction commits or aborts is the moment at which the disk finishes writing the commit record: before that moment, it is still possible to abort (due to a crash), but after that moment, the transaction is committed (even if the database crashes). Thus, it is a single device (the controller of one particular disk drive, attached to one particular node) that makes the commit atomic.

因此，在单个节点上，事务的提交关键取决于数据持久写入磁盘的顺序：首先是数据，然后是提交记录。确定事务提交或中止的关键决定时刻是磁盘完成写入提交记录的时刻：在此之前，由于崩溃可能仍然可以中止，但在此之后，即使数据库崩溃，事务也已提交。因此，它是单个设备（连接到一个特定节点的一个特定磁盘驱动器的控制器）使提交具有原子性。

However, what if multiple nodes are involved in a transaction? For example, perhaps you have a multi-object transaction in a partitioned database, or a term-partitioned secondary index (in which the index entry may be on a different node from the primary data; see “Partitioning and Secondary Indexes” ). Most “NoSQL” distributed datastores do not support such distributed transactions, but various clustered relational systems do (see “Distributed Transactions in Practice” ).

然而，如果涉及多个节点的交易怎么办？例如，在分区数据库中可能有多个对象事务，或者在术语分区的二级索引中（其中索引条目可能位于与主数据不同的节点上；请参阅“分区和二级索引”）。大多数“NoSQL”分布式数据存储不支持这样的分布式事务，但各种集群关系系统都支持（请参阅“实践中的分布式事务”）。

In these cases, it is not sufficient to simply send a commit request to all of the nodes and independently commit the transaction on each one. In doing so, it could easily happen that the commit succeeds on some nodes and fails on other nodes, which would violate the atomicity guarantee:

在这些情况下，简单地向所有节点发送一个提交请求并在每个节点上独立提交交易是不够的。这样做可能会导致提交成功于某些节点，但在其他节点上失败，这将违反原子性保证。

• Some nodes may detect a constraint violation or conflict, making an abort necessary, while other nodes are successfully able to commit.

  一些节点可能会检测到约束违规或冲突，需要进行中止，而其他节点能够成功提交。

• Some of the commit requests might be lost in the network, eventually aborting due to a timeout, while other commit requests get through.

  有些提交请求可能会在网络中丢失，最终由于超时而中止，而其他提交请求则得以通过。

• Some nodes may crash before the commit record is fully written and roll back on recovery, while others successfully commit.

  有些节点在提交记录完全写入之前可能会崩溃并在恢复时回滚，而其他节点则可顺利提交。

If some nodes commit the transaction but others abort it, the nodes become inconsistent with each other (like in Figure 7-3 ). And once a transaction has been committed on one node, it cannot be retracted again if it later turns out that it was aborted on another node. For this reason, a node must only commit once it is certain that all other nodes in the transaction are also going to commit.

如果某些节点提交事务但其他节点中止它，则节点彼此不一致（如图7-3所示）。一旦事务在一个节点上提交，如果后来发现它在另一个节点上被中止，它就不能被撤回。因此，节点必须在确信所有其他节点也将提交后才能提交。

A transaction commit must be irrevocable—you are not allowed to change your mind and retroactively abort a transaction after it has been committed. The reason for this rule is that once data has been committed, it becomes visible to other transactions, and thus other clients may start relying on that data; this principle forms the basis of read committed isolation, discussed in “Read Committed” . If a transaction was allowed to abort after committing, any transactions that read the committed data would be based on data that was retroactively declared not to have existed—so they would have to be reverted as well.

提交的交易必须是不可撤销的——一旦事务提交后，您不允许更改想法或撤消交易。这个规则的原因是，一旦数据已经提交，它就会被其他交易可见，因此其他客户端可能会开始依赖这些数据；这个原则构成了"读已提交隔离"的基础，见“读已提交”。如果一个交易在提交后允许被中止，任何读取已提交数据的交易都将基于事后宣布不存在的数据——因此它们也必须被回滚。

(It is possible for the effects of a committed transaction to later be undone by another, compensating transaction [ 73 , 74 ]. However, from the database’s point of view this is a separate transaction, and thus any cross-transaction correctness requirements are the application’s problem.)

一项已提交的事务的影响可以被另一个补偿性事务撤销[73，74]。然而，从数据库的角度来看，这是一个分开的事务，因此任何跨事务的正确性要求都是应用程序的问题。

Introduction to two-phase commit

Two-phase commit is an algorithm for achieving atomic transaction commit across multiple nodes—i.e., to ensure that either all nodes commit or all nodes abort. It is a classic algorithm in distributed databases [ 13 , 35 , 75 ]. 2PC is used internally in some databases and also made available to applications in the form of XA transactions [ 76 , 77 ] (which are supported by the Java Transaction API, for example) or via WS-AtomicTransaction for SOAP web services [ 78 , 79 ].

两阶段提交是一种算法，用于实现跨多个节点的原子事务提交-即确保所有节点都提交或所有节点都中止。这是分布式数据库中经典的算法。2PC在某些数据库中被内部使用，并以XA事务（例如Java事务API支持的方式）或通过WS-AtomicTransaction供应用程序使用，以用于SOAP Web服务。

The basic flow of 2PC is illustrated in Figure 9-9 . Instead of a single commit request, as with a single-node transaction, the commit/abort process in 2PC is split into two phases (hence the name).

2PC的基本流程如图9-9所示。与单节点事务不同的是，2PC的提交/撤销过程分为两个阶段（因此得名）。

Figure 9-9. A successful execution of two-phase commit (2PC).

2PC uses a new component that does not normally appear in single-node transactions: a coordinator (also known as transaction manager ). The coordinator is often implemented as a library within the same application process that is requesting the transaction (e.g., embedded in a Java EE container), but it can also be a separate process or service. Examples of such coordinators include Narayana, JOTM, BTM, or MSDTC.

2PC使用了一种在单节点交易中通常不出现的新组件：协调员（也称事务管理器）。协调员通常作为同一应用程序过程中的库来实现（例如嵌入在Java EE容器中），但它也可以是一个单独的进程或服务。这些协调员的示例包括Narayana、JOTM、BTM或MSDTC。

A 2PC transaction begins with the application reading and writing data on multiple database nodes, as normal. We call these database nodes participants in the transaction. When the application is ready to commit, the coordinator begins phase 1: it sends a prepare request to each of the nodes, asking them whether they are able to commit. The coordinator then tracks the responses from the participants:

2PC事务始于应用读取和写入多个数据库节点上的数据，就像平常一样。我们将这些数据库节点称为事务的参与者。当应用准备提交时，协调者开始第一阶段：向每个节点发送一个准备请求，询问它们是否能够提交。然后，协调者跟踪参与者的响应。

• If all participants reply “yes,” indicating they are ready to commit, then the coordinator sends out a commit request in phase 2, and the commit actually takes place.

  如果所有参与者都回复 “是”，表示他们已准备好承诺，那么协调员会在第二阶段发送承诺请求，并且实际承诺会发生。

• If any of the participants replies “no,” the coordinator sends an abort request to all nodes in phase 2.

  如果任何参与者回答“否”，协调员将向第2阶段中的所有节点发送中止请求。

This process is somewhat like the traditional marriage ceremony in Western cultures: the minister asks the bride and groom individually whether each wants to marry the other, and typically receives the answer “I do” from both. After receiving both acknowledgments, the minister pronounces the couple husband and wife: the transaction is committed, and the happy fact is broadcast to all attendees. If either bride or groom does not say “yes,” the ceremony is aborted [ 73 ].

这个过程有点像西方文化传统的婚礼仪式：牧师单独问新郎和新娘是否希望嫁娶对方，通常两人都会回答“是的”。在获得双方确认后，牧师宣布他们成为夫妻：交易得以进行，这个喜悦的事实会向所有出席者广播。如果新娘或新郎有任何人没有回答“是”，婚礼仪式就会被取消 [73]。

A system of promises

From this short description it might not be clear why two-phase commit ensures atomicity, while one-phase commit across several nodes does not. Surely the prepare and commit requests can just as easily be lost in the two-phase case. What makes 2PC different?

从这个简短的描述中可能不清楚为什么双阶段提交确保原子性，而跨多个节点的单阶段提交则不是。在两阶段情况下，准备和提交请求同样容易丢失。是什么让2PC不同呢？

To understand why it works, we have to break down the process in a bit more detail:

要理解为什么它起作用，我们必须更详细地分解该过程：

1. When the application wants to begin a distributed transaction, it requests a transaction ID from the coordinator. This transaction ID is globally unique.

   当应用程序想要开始一个分布式事务时，它会向协调者请求一个事务ID。这个事务ID是全局唯一的。

2. The application begins a single-node transaction on each of the participants, and attaches the globally unique transaction ID to the single-node transaction. All reads and writes are done in one of these single-node transactions. If anything goes wrong at this stage (for example, a node crashes or a request times out), the coordinator or any of the participants can abort.

   应用程序在每个参与者上开始一个单节点事务，并将全局唯一的事务ID附加到单节点事务。所有读写操作都在这些单节点事务中完成。如果在此阶段出现任何问题（例如，节点崩溃或请求超时），协调者或任何参与者都可以中止。

3. When the application is ready to commit, the coordinator sends a prepare request to all participants, tagged with the global transaction ID. If any of these requests fails or times out, the coordinator sends an abort request for that transaction ID to all participants.

   当应用准备执行时，协调者会向所有参与者发送一个带有全局事务ID标记的准备请求。如果其中任何一个请求失败或超时，协调者会向所有参与者发送一个有关该事务ID的中止请求。

4. When a participant receives the prepare request, it makes sure that it can definitely commit the transaction under all circumstances. This includes writing all transaction data to disk (a crash, a power failure, or running out of disk space is not an acceptable excuse for refusing to commit later), and checking for any conflicts or constraint violations. By replying “yes” to the coordinator, the node promises to commit the transaction without error if requested. In other words, the participant surrenders the right to abort the transaction, but without actually committing it.

   当参与者接收到准备请求时，它确保在所有情况下都能够确定地提交该事务。这包括将所有事务数据写入磁盘（崩溃、停电或磁盘空间不足不是拒绝稍后提交的合理理由），并检查是否存在任何冲突或约束违规。通过回复“是”给协调者，节点承诺在请求时能够提交事务而不出现错误。换句话说，参与者放弃了终止事务的权利，但并没有实际提交它。

5. When the coordinator has received responses to all prepare requests, it makes a definitive decision on whether to commit or abort the transaction (committing only if all participants voted “yes”). The coordinator must write that decision to its transaction log on disk so that it knows which way it decided in case it subsequently crashes. This is called the commit point .

   当协调员接收到所有准备请求的回复后，它会对事务作出最终的决定，即是提交还是中止事务（只有所有参与者都投票“是”才能提交）。协调员必须将该决定写入其磁盘上的事务日志，以便在随后发生崩溃时知道其决定的方向。这就是所谓的提交点。

6. Once the coordinator’s decision has been written to disk, the commit or abort request is sent to all participants. If this request fails or times out, the coordinator must retry forever until it succeeds. There is no more going back: if the decision was to commit, that decision must be enforced, no matter how many retries it takes. If a participant has crashed in the meantime, the transaction will be committed when it recovers—since the participant voted “yes,” it cannot refuse to commit when it recovers.

   一旦协调者的决定已被写入磁盘，提交或中止请求将发送给所有参与者。如果该请求失败或超时，协调者必须永远重试，直到成功。没有回头路：如果决定是提交，那么无论需要多少次重试，该决定都必须执行。如果参与者在此期间崩溃，那么当其恢复时，交易将被提交，因为参与者投了“是”票，因此在恢复时不能拒绝提交。

Thus, the protocol contains two crucial “points of no return”: when a participant votes “yes,” it promises that it will definitely be able to commit later (although the coordinator may still choose to abort); and once the coordinator decides, that decision is irrevocable. Those promises ensure the atomicity of 2PC. (Single-node atomic commit lumps these two events into one: writing the commit record to the transaction log.)

因此，该协议包含两个至关重要的“无回头点”：当参与者投票“是”，它承诺它肯定能够稍后提交（虽然管理员仍可能选择放弃）; 一旦协调员做出决定，该决定就是不可撤销的。这些承诺确保了2PC的原子性。（单节点原子提交将这两个事件合并为一个：将提交记录写入事务日志。）

Returning to the marriage analogy, before saying “I do,” you and your bride/groom have the freedom to abort the transaction by saying “No way!” (or something to that effect). However, after saying “I do,” you cannot retract that statement. If you faint after saying “I do” and you don’t hear the minister speak the words “You are now husband and wife,” that doesn’t change the fact that the transaction was committed. When you recover consciousness later, you can find out whether you are married or not by querying the minister for the status of your global transaction ID, or you can wait for the minister’s next retry of the commit request (since the retries will have continued throughout your period of unconsciousness).

回到婚姻的类比， 在说“我愿意”之前，你和你的新娘/新郎有自由地通过说“绝不！”或者其他类似的话终止交易。 但是，一旦你说了“我愿意”，你就不能收回。 如果在说“我愿意”之后你晕倒了，没有听到牧师说“你现在成为夫妻了”，这并不会改变交易已经完成的事实。 当你恢复意识后，你可以通过查询牧师的全局交易ID的状态来了解你是否结婚了，或者你可以等待牧师下一次重试提交请求（因为在你失去意识的期间，重试将一直进行）。

Coordinator failure

We have discussed what happens if one of the participants or the network fails during 2PC: if any of the prepare requests fail or time out, the coordinator aborts the transaction; if any of the commit or abort requests fail, the coordinator retries them indefinitely. However, it is less clear what happens if the coordinator crashes.

如果在两阶段提交期间，参与者或网络出现故障，我们已经讨论了出现的情况：如果任何一方的准备请求失败或超时，协调者将中止事务；如果提交或中止请求失败，协调者将无限重试。然而，如果协调者崩溃，会发生什么就不那么清楚了。

If the coordinator fails before sending the prepare requests, a participant can safely abort the transaction. But once the participant has received a prepare request and voted “yes,” it can no longer abort unilaterally—it must wait to hear back from the coordinator whether the transaction was committed or aborted. If the coordinator crashes or the network fails at this point, the participant can do nothing but wait. A participant’s transaction in this state is called in doubt or uncertain .

如果协调器在发送准备请求之前失败，参与者可以安全地中止交易。但是，一旦参与者收到准备请求并投票“是”，它就不能再单方面中止交易了——它必须等待协调器回复交易是已提交还是已中止。如果此时协调器崩溃或网络失败，则参与者除了等待外无能为力。这种情况下参与者的交易被称为不确定或不确定状态。

The situation is illustrated in Figure 9-10 . In this particular example, the coordinator actually decided to commit, and database 2 received the commit request. However, the coordinator crashed before it could send the commit request to database 1, and so database 1 does not know whether to commit or abort. Even a timeout does not help here: if database 1 unilaterally aborts after a timeout, it will end up inconsistent with database 2, which has committed. Similarly, it is not safe to unilaterally commit, because another participant may have aborted.

情况如图9-10所示。在这个特殊例子中，协调器实际上决定提交，数据库2接收到提交请求。然而，在协调器发送提交请求到数据库1之前，协调器崩溃了，所以数据库1不知道是要提交还是要中止。即使超时也无法解决这个问题：如果数据库1在超时后单方面中止，它将与已经提交的数据库2不一致。同样地，单方面提交也不安全，因为另一个参与者可能已经中止。

Figure 9-10. The coordinator crashes after participants vote “yes.” Database 1 does not know whether to commit or abort.

Without hearing from the coordinator, the participant has no way of knowing whether to commit or abort. In principle, the participants could communicate among themselves to find out how each participant voted and come to some agreement, but that is not part of the 2PC protocol.

如果没有听到协调员的消息，参与者就没有办法知道是要继续还是中止。原则上，参与者可以相互沟通，了解每个人的投票情况并达成共识，但这不是2PC协议的一部分。

The only way 2PC can complete is by waiting for the coordinator to recover. This is why the coordinator must write its commit or abort decision to a transaction log on disk before sending commit or abort requests to participants: when the coordinator recovers, it determines the status of all in-doubt transactions by reading its transaction log. Any transactions that don’t have a commit record in the coordinator’s log are aborted. Thus, the commit point of 2PC comes down to a regular single-node atomic commit on the coordinator.

2PC只能等待协调者恢复才能完成。这就是为什么在向参与者发送提交或中止请求之前，协调者必须将其提交或中止决策写入磁盘上的事务日志中的原因：当协调者恢复时，它通过读取其事务日志确定所有存疑事务的状态。在协调者的日志中没有提交记录的任何事务都会被中止。因此，2PC的提交点归结为协调者上的常规单节点原子提交。

Three-phase commit

Two-phase commit is called a blocking atomic commit protocol due to the fact that 2PC can become stuck waiting for the coordinator to recover. In theory, it is possible to make an atomic commit protocol nonblocking , so that it does not get stuck if a node fails. However, making this work in practice is not so straightforward.

两阶段提交被称为阻塞原子提交协议，因为2PC可能会被卡住，等待协调者恢复。理论上，可能会使原子提交协议非阻塞，这样即使节点失败也不会被卡住。然而，在实践中使其正常工作并不那么简单。

As an alternative to 2PC, an algorithm called three-phase commit (3PC) has been proposed [ 13 , 80 ]. However, 3PC assumes a network with bounded delay and nodes with bounded response times; in most practical systems with unbounded network delay and process pauses (see Chapter 8 ), it cannot guarantee atomicity.

作为 2PC 的替代方案，提出了一种称为三阶段提交（3PC）的算法[13, 80]。然而，3PC 假设网络具有有限延迟和节点具有有限响应时间；在大多数具有无界网络延迟和进程暂停的实际系统中（请参见第 8 章），无法保证原子性。

In general, nonblocking atomic commit requires a perfect failure detector [ 67 , 71 ]—i.e., a reliable mechanism for telling whether a node has crashed or not. In a network with unbounded delay a timeout is not a reliable failure detector, because a request may time out due to a network problem even if no node has crashed. For this reason, 2PC continues to be used, despite the known problem with coordinator failure.

一般而言，非阻塞原子提交需要完美的失效检测器[67，71]，即可靠的机制来判断节点是否已经崩溃。在延迟无限制的网络中，超时并不是可靠的故障检测器，因为由于网络问题，请求可能超时，即使没有节点崩溃。因此，尽管协调员故障是已知的问题，但2PC仍然被使用。

Exactly-once message processing

Heterogeneous distributed transactions allow diverse systems to be integrated in powerful ways. For example, a message from a message queue can be acknowledged as processed if and only if the database transaction for processing the message was successfully committed. This is implemented by atomically committing the message acknowledgment and the database writes in a single transaction. With distributed transaction support, this is possible, even if the message broker and the database are two unrelated technologies running on different machines.

异构分布式事务使得不同的系统可以强大地集成在一起。例如，只有在成功提交处理消息的数据库事务后，消息队列中的消息才能被确认已处理。这是通过原子地在单个事务中提交消息确认和数据库写入来实现的。即使消息代理和数据库是运行在不同机器上的两种不相关技术，分布式事务支持也可以实现这一点。

If either the message delivery or the database transaction fails, both are aborted, and so the message broker may safely redeliver the message later. Thus, by atomically committing the message and the side effects of its processing, we can ensure that the message is effectively processed exactly once, even if it required a few retries before it succeeded. The abort discards any side effects of the partially completed transaction.

如果消息传递或数据库事务中任一一个失败，这两个都会被取消，因此消息中间件可以安全地稍后重发消息。因此，通过原子地提交消息和其处理的副作用，我们可以确保该消息被有效处理一次，即使在成功之前需要进行几次重试。中止会丢弃已部分完成事务的任何副作用。

Such a distributed transaction is only possible if all systems affected by the transaction are able to use the same atomic commit protocol, however. For example, say a side effect of processing a message is to send an email, and the email server does not support two-phase commit: it could happen that the email is sent two or more times if message processing fails and is retried. But if all side effects of processing a message are rolled back on transaction abort, then the processing step can safely be retried as if nothing had happened.

如果事务受影响的所有系统都能够使用相同的原子提交协议，那么这样的分布式事务才有可能实现。例如，假设处理消息的一个副作用是发送电子邮件，而邮件服务器不支持两阶段提交：如果消息处理失败并重试，则可能发送两次或更多次电子邮件。但如果在事务中断时回滚处理消息的所有副作用，就可以安全地重试处理步骤，就像什么也没发生一样。

We will return to the topic of exactly-once message processing in Chapter 11 . Let’s look first at the atomic commit protocol that allows such heterogeneous distributed transactions.

我们将在第11章回到确保仅有一次消息处理的话题。首先让我们看一下允许这样异构分布式事务的原子提交协议。

XA transactions

X/Open XA (short for eXtended Architecture ) is a standard for implementing two-phase commit across heterogeneous technologies [ 76 , 77 ]. It was introduced in 1991 and has been widely implemented: XA is supported by many traditional relational databases (including PostgreSQL, MySQL, DB2, SQL Server, and Oracle) and message brokers (including ActiveMQ, HornetQ, MSMQ, and IBM MQ).

X/Open XA（扩展架构）是一种跨异构技术实现两阶段提交的标准 [76, 77]。它于1991年引入，并得到广泛应用：XA受到许多传统关系数据库（包括PostgreSQL、MySQL、DB2、SQL Server和Oracle）和消息代理（包括ActiveMQ、HornetQ、MSMQ和IBM MQ）的支持。

XA is not a network protocol—it is merely a C API for interfacing with a transaction coordinator. Bindings for this API exist in other languages; for example, in the world of Java EE applications, XA transactions are implemented using the Java Transaction API (JTA), which in turn is supported by many drivers for databases using Java Database Connectivity (JDBC) and drivers for message brokers using the Java Message Service (JMS) APIs.

XA不是一个网络协议，它只是一个用于与事务协调器进行接口交互的C API。其他语言中也存在这个API的绑定；例如，在Java EE应用程序世界中，XA事务是使用Java事务API（JTA）实现的，而Java数据库连接（JDBC）和Java消息服务（JMS）API的许多数据库驱动程序和消息代理驱动程序都支持JTA。

XA assumes that your application uses a network driver or client library to communicate with the participant databases or messaging services. If the driver supports XA, that means it calls the XA API to find out whether an operation should be part of a distributed transaction—and if so, it sends the necessary information to the database server. The driver also exposes callbacks through which the coordinator can ask the participant to prepare, commit, or abort.

XA 假定您的应用程序使用网络驱动程序或客户端库来与参与者数据库或消息服务进行通信。如果该驱动程序支持 XA，则表示它会调用 XA API 来确定操作是否应是分布式事务的一部分，如果是，则向数据库服务器发送必要的信息。该驱动程序还通过回调公开回调功能，协调器可以请求参与者准备、提交或中止。

The transaction coordinator implements the XA API. The standard does not specify how it should be implemented, but in practice the coordinator is often simply a library that is loaded into the same process as the application issuing the transaction (not a separate service). It keeps track of the participants in a transaction, collects partipants’ responses after asking them to prepare (via a callback into the driver), and uses a log on the local disk to keep track of the commit/abort decision for each transaction.

事务协调器实现XA API。标准并未规定它应如何实现，但实际上，协调器通常只是一个库，加载到发出事务的应用程序的相同进程中（而不是一个单独的服务）。它跟踪事务中的参与者，在请求它们准备（通过驱动程序回调）后收集参与者的响应，并使用本地磁盘上的日志来跟踪每个事务的提交/中止决策。

If the application process crashes, or the machine on which the application is running dies, the coordinator goes with it. Any participants with prepared but uncommitted transactions are then stuck in doubt. Since the coordinator’s log is on the application server’s local disk, that server must be restarted, and the coordinator library must read the log to recover the commit/abort outcome of each transaction. Only then can the coordinator use the database driver’s XA callbacks to ask participants to commit or abort, as appropriate. The database server cannot contact the coordinator directly, since all communication must go via its client library.

如果应用程序崩溃，或运行应用程序的计算机死机，协调器也将失效。任何准备好但未提交的事务参与者此时就会陷入疑惑。由于协调器日志存储在应用服务器的本地磁盘上，因此必须重新启动该服务器，并且协调器库必须读取日志以恢复每个事务的提交/中止结果。只有这样，协调器才能使用数据库驱动程序的XA回调来要求参与者提交或中止。数据库服务器无法直接联系协调器，因为所有通信都必须通过其客户端库。

Holding locks while in doubt

Why do we care so much about a transaction being stuck in doubt? Can’t the rest of the system just get on with its work, and ignore the in-doubt transaction that will be cleaned up eventually?

为什么我们如此关注一笔交易是否被搁置在疑问当中？难道系统的其他部分不可以继续工作，而忽略最终会被清理的搁置交易吗？

The problem is with locking . As discussed in “Read Committed” , database transactions usually take a row-level exclusive lock on any rows they modify, to prevent dirty writes. In addition, if you want serializable isolation, a database using two-phase locking would also have to take a shared lock on any rows read by the transaction (see “Two-Phase Locking (2PL)” ).

问题出在锁定上。如在“读取已提交”中所讨论，数据库事务通常会对其修改的任何行进行行级独占锁定以防止脏写操作。此外，如果您想要可串行化的隔离级别，则使用两阶段锁定的数据库还必须对事务读取的任何行进行共享锁定（请参见“两阶段锁定（2PL）”）。

The database cannot release those locks until the transaction commits or aborts (illustrated as a shaded area in Figure 9-9 ). Therefore, when using two-phase commit, a transaction must hold onto the locks throughout the time it is in doubt. If the coordinator has crashed and takes 20 minutes to start up again, those locks will be held for 20 minutes. If the coordinator’s log is entirely lost for some reason, those locks will be held forever—or at least until the situation is manually resolved by an administrator.

数据库在事务提交或中止前无法释放这些锁定（如图9-9中的阴影区所示）。因此，在使用两阶段提交时，事务必须在有疑问的情况下一直保持锁定。如果协调者崩溃并需要20分钟才能重新启动，则这些锁定将被保持20分钟。如果由于某种原因协调者的日志完全丢失，则这些锁将永远保持，或者至少直到管理员手动解决该情况。

While those locks are held, no other transaction can modify those rows. Depending on the database, other transactions may even be blocked from reading those rows. Thus, other transactions cannot simply continue with their business—if they want to access that same data, they will be blocked. This can cause large parts of your application to become unavailable until the in-doubt transaction is resolved.

当这些锁定被保留时，没有其他交易可以修改这些行。根据数据库，其他交易甚至可能被阻止阅读这些行。因此，其他交易不能简单地继续业务 - 如果他们想访问相同的数据，他们将被阻止。这可能导致您的应用程序的大部分部分变得不可用，直到未决交易解决。

Recovering from coordinator failure

In theory, if the coordinator crashes and is restarted, it should cleanly recover its state from the log and resolve any in-doubt transactions. However, in practice, orphaned in-doubt transactions do occur [ 89 , 90 ]—that is, transactions for which the coordinator cannot decide the outcome for whatever reason (e.g., because the transaction log has been lost or corrupted due to a software bug). These transactions cannot be resolved automatically, so they sit forever in the database, holding locks and blocking other transactions.

从理论上讲，如果协调者崩溃并重新启动，它应该从日志中清晰地恢复自己的状态并解决任何不确定的事务。然而，在实践中，孤立的不确定事务确实会发生[89, 90]--即无论出于什么原因（例如，由于软件漏洞而导致事务日志丢失或损坏），协调者无法决定结果的事务。这些事务无法自动解决，因此它们会永远停留在数据库中，持有锁并阻塞其他事务。

Even rebooting your database servers will not fix this problem, since a correct implementation of 2PC must preserve the locks of an in-doubt transaction even across restarts (otherwise it would risk violating the atomicity guarantee). It’s a sticky situation.

即使重新启动数据库服务器也不会解决此问题，因为正确实现2PC必须保留不确定事务的锁甚至跨越重启 (否则它会冒失违反原子性保证)。这是一个棘手的情况。

The only way out is for an administrator to manually decide whether to commit or roll back the transactions. The administrator must examine the participants of each in-doubt transaction, determine whether any participant has committed or aborted already, and then apply the same outcome to the other participants. Resolving the problem potentially requires a lot of manual effort, and most likely needs to be done under high stress and time pressure during a serious production outage (otherwise, why would the coordinator be in such a bad state?).

唯一的解决方法是由管理员手动决定提交还是回滚交易。管理员必须检查每个不确定的事务的参与者，确定是否已经有任何参与者提交或中止，然后将相同的结果应用于其他参与者。解决这个问题可能需要大量的手动工作，很可能需要在严重的生产中断期间，在高压和时间压力下完成（否则，为什么协调者会处于如此糟糕的状态？）。

Many XA implementations have an emergency escape hatch called heuristic decisions : allowing a participant to unilaterally decide to abort or commit an in-doubt transaction without a definitive decision from the coordinator [ 76 , 77 , 91 ]. To be clear, heuristic here is a euphemism for probably breaking atomicity , since it violates the system of promises in two-phase commit. Thus, heuristic decisions are intended only for getting out of catastrophic situations, and not for regular use.

许多XA实现都有一个紧急逃生方法，称为启发式决策：允许参与者在未从协调者得到明确定论决策的情况下单方面决定中止或提交一个未确定的事务[76，77，91]。需要指出的是，在这里，“启发式”是破坏原子性的委婉说法，因为它违反了两阶段提交的承诺系统。因此，启发式决策仅适用于紧急情况，而非常规情况下的使用。

Limitations of distributed transactions

XA transactions solve the real and important problem of keeping several participant data systems consistent with each other, but as we have seen, they also introduce major operational problems. In particular, the key realization is that the transaction coordinator is itself a kind of database (in which transaction outcomes are stored), and so it needs to be approached with the same care as any other important database:

XA事务解决了保持多个参与方数据系统相互一致的真正重要问题，但正如我们所看到的，它们也引入了重大的操作问题。特别是，关键的认识是事务协调器本身就像是一个数据库（其中存储着事务结果），因此需要像任何其他重要数据库一样小心对待。

• If the coordinator is not replicated but runs only on a single machine, it is a single point of failure for the entire system (since its failure causes other application servers to block on locks held by in-doubt transactions). Surprisingly, many coordinator implementations are not highly available by default, or have only rudimentary replication support.

  如果协调器未被复制，而只在单台机器上运行，那么整个系统都存在单点故障（因为它的故障会导致其他应用服务器因为维护不确定事务持有的锁而被阻塞）。令人惊讶的是，许多协调器实现默认情况下并非高可用性的，或者只有基本的复制支持。

• Many server-side applications are developed in a stateless model (as favored by HTTP), with all persistent state stored in a database, which has the advantage that application servers can be added and removed at will. However, when the coordinator is part of the application server, it changes the nature of the deployment. Suddenly, the coordinator’s logs become a crucial part of the durable system state—as important as the databases themselves, since the coordinator logs are required in order to recover in-doubt transactions after a crash. Such application servers are no longer stateless.

  许多服务器端应用程序采用无状态模型（正如HTTP所支持的），所有持久状态都存储在数据库中，这样的好处是应用程序服务器可以随意添加和删除。但是当协调器成为应用服务器的一部分时，它改变了部署的性质。突然间，协调器的日志成为了持久系统状态的关键部分，和数据库本身一样重要，因为在崩溃后需要使用协调器的日志来恢复未确定的事务。这样的应用程序服务器不再是无状态的。

• Since XA needs to be compatible with a wide range of data systems, it is necessarily a lowest common denominator. For example, it cannot detect deadlocks across different systems (since that would require a standardized protocol for systems to exchange information on the locks that each transaction is waiting for), and it does not work with SSI (see “Serializable Snapshot Isolation (SSI)” ), since that would require a protocol for identifying conflicts across different systems.

  由于XA需要与各种数据系统兼容，因此它必然是最低公共分母。例如，它无法在不同系统之间检测死锁（因为这需要标准化协议来交换有关每个事务正在等待的锁的信息），并且它不能与SSI（参见“可串行快照隔离（SSI）”）一起工作，因为这需要一个用于识别不同系统之间冲突的协议。

• For database-internal distributed transactions (not XA), the limitations are not so great—for example, a distributed version of SSI is possible. However, there remains the problem that for 2PC to successfully commit a transaction, all participants must respond. Consequently, if any part of the system is broken, the transaction also fails. Distributed transactions thus have a tendency of amplifying failures , which runs counter to our goal of building fault-tolerant systems.

  对于数据库内部分布式事务（非XA事务），限制并不是很大，例如可以实现分布式的SSI版本。然而，仍然存在一个问题，就是为了使2PC成功提交一个事务，所有参与者都必须做出响应。因此，如果系统的任何部分出现故障，事务也会失败。分布式事务因此具有放大故障的趋势，这与我们构建容错系统的目标相悖。

Do these facts mean we should give up all hope of keeping several systems consistent with each other? Not quite—there are alternative methods that allow us to achieve the same thing without the pain of heterogeneous distributed transactions. We will return to these in Chapters 11 and 12 . But first, we should wrap up the topic of consensus.

这些事实是否意味着我们应该放弃所有希望让多个系统保持一致？并非如此——有替代方法可以让我们在不进行异构分布式事务的痛苦情况下实现相同的目标。我们将在第11和12章回到这些方法。但首先，我们应该结束共识主题。

Consensus algorithms and total order broadcast

The best-known fault-tolerant consensus algorithms are Viewstamped Replication (VSR) [ 94 , 95 ], Paxos [ 96 , 97 , 98 , 99 ], Raft [ 22 , 100 , 101 ], and Zab [ 15 , 21 , 102 ]. There are quite a few similarities between these algorithms, but they are not the same [ 103 ]. In this book we won’t go into full details of the different algorithms: it’s sufficient to be aware of some of the high-level ideas that they have in common, unless you’re implementing a consensus system yourself (which is probably not advisable—it’s hard [ 98 , 104 ]).

最为知名的容错共识算法包括Viewstamped Replication (VSR)[94, 95]、Paxos[96, 97, 98, 99]、Raft[22, 100, 101]和Zab[15, 21, 102]。这些算法有许多相似之处，但并非完全相同[103]。在本书中，我们不会详细介绍不同算法的细节：只需要了解它们在高级别想法方面的某些共性即可，除非你正在实现一个共识系统（这可能并不明智——很难[98, 104]）。

Most of these algorithms actually don’t directly use the formal model described here (proposing and deciding on a single value, while satisfying the agreement, integrity, validity, and termination properties). Instead, they decide on a sequence of values, which makes them total order broadcast algorithms, as discussed previously in this chapter (see “Total Order Broadcast” ).

大多数这些算法实际上并没有直接使用描述在这里的形式化模型（提出并决定单个值，同时满足协议、完整性、有效性和终止性属性）。相反，它们决定一个值的序列，使它们成为总排序广播算法，就像在本章之前讨论的那样（请参见“总排序广播”）。

Remember that total order broadcast requires messages to be delivered exactly once, in the same order, to all nodes. If you think about it, this is equivalent to performing several rounds of consensus: in each round, nodes propose the message that they want to send next, and then decide on the next message to be delivered in the total order [ 67 ].

全序广播要求所有消息被恰好传输一次，且顺序相同，发送到所有节点。如果你仔细想一想，这等同于进行多轮共识：在每一轮中，节点都会提出他们要发送的消息，然后决定下一个要传输到全序中的消息。

So, total order broadcast is equivalent to repeated rounds of consensus (each consensus decision corresponding to one message delivery):

因此，全局订单广播等同于重复的共识轮次（每个共识决策对应一条消息传递）。

• Due to the agreement property of consensus, all nodes decide to deliver the same messages in the same order.

  由于共识属性的协议，所有节点决定以相同顺序传递相同的消息。

• Due to the integrity property, messages are not duplicated.

  由于完整性属性，消息不会重复。

• Due to the validity property, messages are not corrupted and not fabricated out of thin air.

  由于有效性特性，消息不会被损坏或虚构出来。

• Due to the termination property, messages are not lost.

  由于终止属性，消息不会丢失。

Viewstamped Replication, Raft, and Zab implement total order broadcast directly, because that is more efficient than doing repeated rounds of one-value-at-a-time consensus. In the case of Paxos, this optimization is known as Multi-Paxos.

视图共识复制、Raft和Zab直接实现了总序播，因为它比重复一次只传递一个值的共识更高效。在Paxos的情况下，这种优化被称为多Paxos。

Single-leader replication and consensus

In Chapter 5 we discussed single-leader replication (see “Leaders and Followers” ), which takes all the writes to the leader and applies them to the followers in the same order, thus keeping replicas up to date. Isn’t this essentially total order broadcast? How come we didn’t have to worry about consensus in Chapter 5 ?

在第5章，我们讨论了单领导副本复制(参见“领导者和追随者”)，它将所有写入操作发送到领导者并按照相同的顺序应用到追随者上，因此保持副本最新。这不是本质上的总序广播吗?为什么我们在第5章不必担心共识问题?

The answer comes down to how the leader is chosen. If the leader is manually chosen and configured by the humans in your operations team, you essentially have a “consensus algorithm” of the dictatorial variety: only one node is allowed to accept writes (i.e., make decisions about the order of writes in the replication log), and if that node goes down, the system becomes unavailable for writes until the operators manually configure a different node to be the leader. Such a system can work well in practice, but it does not satisfy the termination property of consensus because it requires human intervention in order to make progress.

答案取决于领导者是如何被选择的。如果领导者是由您的运营团队人工选择和配置的，那么您实际上拥有一种“独裁式”的共识算法：只允许一个节点接受写入（即决定复制日志中写入顺序的节点），如果该节点故障，则系统变得不可用，直到操作员手动配置一个不同的节点成为领导者。这样的系统在实践中可以很好地工作，但它并不满足共识的终止属性，因为它需要人为干预才能取得进展。

Some databases perform automatic leader election and failover, promoting a follower to be the new leader if the old leader fails (see “Handling Node Outages” ). This brings us closer to fault-tolerant total order broadcast, and thus to solving consensus.

一些数据库执行自动领导选举和故障转移，如果旧领导者失败，则晋升一个跟随者成为新领导者（参见“处理节点故障”）。这使我们更接近容错的完全排序广播，从而解决共识问题。

However, there is a problem. We previously discussed the problem of split brain, and said that all nodes need to agree who the leader is—otherwise two different nodes could each believe themselves to be the leader, and consequently get the database into an inconsistent state. Thus, we need consensus in order to elect a leader. But if the consensus algorithms described here are actually total order broadcast algorithms, and total order broadcast is like single-leader replication, and single-leader replication requires a leader, then…

然而，存在一个问题。我们先前讨论了分裂大脑的问题，并说所有节点需要达成一致，以确定领导者，否则两个不同的节点都可能认为自己是领导者，从而使数据库进入不一致状态。因此，在选举领导者时，我们需要共识。但是，如果这里描述的共识算法实际上是总序广播算法，而总序广播就像单领导者复制，单领导者复制需要领导者，那么...

It seems that in order to elect a leader, we first need a leader. In order to solve consensus, we must first solve consensus. How do we break out of this conundrum?

似乎为了选举一位领袖，我们需要首先有一位领袖。为了解决共识问题，我们必须首先解决共识问题。我们如何打破这个困境？

Epoch numbering and quorums

All of the consensus protocols discussed so far internally use a leader in some form or another, but they don’t guarantee that the leader is unique. Instead, they can make a weaker guarantee: the protocols define an epoch number (called the ballot number in Paxos, view number in Viewstamped Replication, and term number in Raft) and guarantee that within each epoch, the leader is unique.

迄今为止讨论的所有共识协议内部都以某种形式使用领导者，但他们并不保证该领导者是唯一的。相反，它们可以提供一个较弱的保证：该协议定义了一个时代号（在Paxos中称为投票号，在Viewstamped Replication中称为视图号，在Raft中称为任期号），并且保证在每个时代内，领导者是唯一的。

Every time the current leader is thought to be dead, a vote is started among the nodes to elect a new leader. This election is given an incremented epoch number, and thus epoch numbers are totally ordered and monotonically increasing. If there is a conflict between two different leaders in two different epochs (perhaps because the previous leader actually wasn’t dead after all), then the leader with the higher epoch number prevails.

每当当前领导人被认为已经死亡时，节点之间就开始投票选举新领导人。此次选举将被赋予一个增加的时代号码，因此时代号码是完全有序和单调递增的。如果在两个不同时代中存在两个不同的领导者之间的冲突（也许是因为前任领导者实际上并未死亡），那么具有较高时代号码的领导者将占上风。

Before a leader is allowed to decide anything, it must first check that there isn’t some other leader with a higher epoch number which might take a conflicting decision. How does a leader know that it hasn’t been ousted by another node? Recall “The Truth Is Defined by the Majority” : a node cannot necessarily trust its own judgment—just because a node thinks that it is the leader, that does not necessarily mean the other nodes accept it as their leader.

领导想要做出决策，必须先检查是否有更高时期号的另一位领导可能做出冲突的决定。领导如何知道自己没有被其他节点取代？回想一下“真理由大多数定义”：节点不能必然信任自己的判断——仅仅因为一个节点认为自己是领导，这并不意味着其他节点也承认它是领导。

Instead, it must collect votes from a quorum of nodes (see “Quorums for reading and writing” ). For every decision that a leader wants to make, it must send the proposed value to the other nodes and wait for a quorum of nodes to respond in favor of the proposal. The quorum typically, but not always, consists of a majority of nodes [ 105 ]. A node votes in favor of a proposal only if it is not aware of any other leader with a higher epoch.

相反，它必须从节点配额中收集投票（请参见“读写的配额”）。 对于领导者想要做出的每个决策，它必须将提议的值发送给其他节点，并等待配额中的节点赞同提议。 配额通常（但并不总是）由大多数节点组成[105]。 仅当节点不知道任何具有较高时期的其他领导者时，节点才投赞成票。

Thus, we have two rounds of voting: once to choose a leader, and a second time to vote on a leader’s proposal. The key insight is that the quorums for those two votes must overlap: if a vote on a proposal succeeds, at least one of the nodes that voted for it must have also participated in the most recent leader election [ 105 ]. Thus, if the vote on a proposal does not reveal any higher-numbered epoch, the current leader can conclude that no leader election with a higher epoch number has happened, and therefore be sure that it still holds the leadership. It can then safely decide the proposed value.

因此，我们有两轮投票：第一次选举领导人，第二次投票表决领导人的提案。关键在于这两个投票的法定人数必须重叠：如果对提案的投票成功，至少投票支持者中的一个节点也必须参与了最近的领导人选举 [105]。因此，如果对提案的投票没有显示出任何更高的时期编号，现任领导人就可以得出结论，没有任何比当前更高时期编号的领导人选举发生过，因此可以确定仍然持有领导权。然后可以安全地决定建议的价值。

This voting process looks superficially similar to two-phase commit. The biggest differences are that in 2PC the coordinator is not elected, and that fault-tolerant consensus algorithms only require votes from a majority of nodes, whereas 2PC requires a “yes” vote from every participant. Moreover, consensus algorithms define a recovery process by which nodes can get into a consistent state after a new leader is elected, ensuring that the safety properties are always met. These differences are key to the correctness and fault tolerance of a consensus algorithm.

这个投票过程表面上看起来类似于两阶段提交。最大的区别在于，2PC中没有选举协调员，而容错一致性算法仅需要来自大多数节点的投票，而2PC要求每个参与者都投赞成票。此外，共识算法定义了恢复过程，使节点能够在选举新领导者后进入一致的状态，确保始终满足安全属性。这些差异对共识算法的正确性和容错性至关重要。

Limitations of consensus

Consensus algorithms are a huge breakthrough for distributed systems: they bring concrete safety properties (agreement, integrity, and validity) to systems where everything else is uncertain, and they nevertheless remain fault-tolerant (able to make progress as long as a majority of nodes are working and reachable). They provide total order broadcast, and therefore they can also implement linearizable atomic operations in a fault-tolerant way (see “Implementing linearizable storage using total order broadcast” ).

共识算法是分布式系统的重大突破：它们为一切不确定的系统带来了具体的安全属性（协议、完整性和有效性），并且它们依然具备容错性（只要大部分节点正常工作并且可达就可以实现进步）。它们提供总序列广播，因此也可以通过容错方式实现可线性操作（详见“使用总序列广播实现可线性存储”）。

Nevertheless, they are not used everywhere, because the benefits come at a cost.

然而，它们并非到处都被使用，因为好处需要付出代价。

The process by which nodes vote on proposals before they are decided is a kind of synchronous replication. As discussed in “Synchronous Versus Asynchronous Replication” , databases are often configured to use asynchronous replication. In this configuration, some committed data can potentially be lost on failover—but many people choose to accept this risk for the sake of better performance.

节点在决策之前对提案进行投票的过程属于同步复制的一种。如“同步与异步复制”所述，数据库通常被配置为使用异步复制。在此配置中，一些已提交的数据可能会在故障转移时丢失 - 但许多人选择为了更好的性能而接受这种风险。

Consensus systems always require a strict majority to operate. This means you need a minimum of three nodes in order to tolerate one failure (the remaining two out of three form a majority), or a minimum of five nodes to tolerate two failures (the remaining three out of five form a majority). If a network failure cuts off some nodes from the rest, only the majority portion of the network can make progress, and the rest is blocked (see also “The Cost of Linearizability” ).

共识系统总是需要严格的多数来运作。这意味着你需要至少三个节点才能容忍一个故障（三个中的两个形成多数），或者至少五个节点来容忍两个故障（五个中的三个形成多数）。如果网络故障将一些节点从其余部分中隔离开来，则只有网络的多数部分才能取得进展，其余部分将被阻塞（也请参见“线性一致性成本”）。

Most consensus algorithms assume a fixed set of nodes that participate in voting, which means that you can’t just add or remove nodes in the cluster. Dynamic membership extensions to consensus algorithms allow the set of nodes in the cluster to change over time, but they are much less well understood than static membership algorithms.

大多数共识算法假定参与投票的节点集是固定的，这意味着您不能只是添加或移除集群中的节点。动态成员扩展共识算法允许集群中的节点集随时间变化，但它们比静态成员算法不太容易理解。

Consensus systems generally rely on timeouts to detect failed nodes. In environments with highly variable network delays, especially geographically distributed systems, it often happens that a node falsely believes the leader to have failed due to a transient network issue. Although this error does not harm the safety properties, frequent leader elections result in terrible performance because the system can end up spending more time choosing a leader than doing any useful work.

共识系统通常依靠超时来检测故障节点。在具有高度可变网络延迟的环境中，特别是分布式系统中，往往会发生节点错误地认为领导者由于短暂的网络问题而失败的情况。尽管这种错误不会损害安全性能，但频繁的领导人选举会导致可怕的性能问题，因为系统最终可能会花费更多时间选择一个领导者而不是执行任何有用的工作。

Sometimes, consensus algorithms are particularly sensitive to network problems. For example, Raft has been shown to have unpleasant edge cases [ 106 ]: if the entire network is working correctly except for one particular network link that is consistently unreliable, Raft can get into situations where leadership continually bounces between two nodes, or the current leader is continually forced to resign, so the system effectively never makes progress. Other consensus algorithms have similar problems, and designing algorithms that are more robust to unreliable networks is still an open research problem.

有时，共识算法特别敏感于网络问题。例如，Raft已经被证明有不愉快的边缘情况 [106]: 如果整个网络除了一个特定的网络链接出现问题以外都正常，Raft会陷入领导者不断在两个节点间跳转，或当前领导者被迫不断辞职的情况，因此系统实际上无法进展。其他共识算法也有类似的问题，设计更加适应不可靠网络的算法仍然是一项开放的研究问题。

Allocating work to nodes

One example in which the ZooKeeper/Chubby model works well is if you have several instances of a process or service, and one of them needs to be chosen as leader or primary. If the leader fails, one of the other nodes should take over. This is of course useful for single-leader databases, but it’s also useful for job schedulers and similar stateful systems.

ZooKeeper/Chubby 模型运作良好的一个例子是，如果您有几个进程或服务的实例，并且需要选择其中一个作为领导者或主节点。如果领导者失败，另一个节点应该接管。当然，这对于单领导数据库非常有用，但对于工作调度程序和类似的有状态系统也非常有用。

Another example arises when you have some partitioned resource (database, message streams, file storage, distributed actor system, etc.) and need to decide which partition to assign to which node. As new nodes join the cluster, some of the partitions need to be moved from existing nodes to the new nodes in order to rebalance the load (see “Rebalancing Partitions” ). As nodes are removed or fail, other nodes need to take over the failed nodes’ work.

当您拥有一些分区资源（数据库、消息流、文件存储、分布式应用程序系统等），并且需要决定将哪个分区分配给哪个节点时，另一个例子就会出现。随着新节点加入群集，一些分区需要从现有节点移动到新节点，以便重新平衡负载（请参见“重新平衡分区”）。当节点被移除或失败时，其他节点需要接管失败节点的工作。

These kinds of tasks can be achieved by judicious use of atomic operations, ephemeral nodes, and notifications in ZooKeeper. If done correctly, this approach allows the application to automatically recover from faults without human intervention. It’s not easy, despite the appearance of libraries such as Apache Curator [ 17 ] that have sprung up to provide higher-level tools on top of the ZooKeeper client API—but it is still much better than attempting to implement the necessary consensus algorithms from scratch, which has a poor success record [ 107 ].

这些任务可以通过在ZooKeeper中谨慎使用原子操作、临时节点和通知来实现。如果正确地执行，这种方法允许应用程序在没有人为干预的情况下自动从故障中恢复。尽管出现了像Apache Curator [17]这样的库，为ZooKeeper客户端API提供了更高级别的工具，但这并不容易——但它仍然比尝试从头开始实现必要的一致性算法要好得多，后者的成功记录很差[107]。

An application may initially run only on a single node, but eventually may grow to thousands of nodes. Trying to perform majority votes over so many nodes would be terribly inefficient. Instead, ZooKeeper runs on a fixed number of nodes (usually three or five) and performs its majority votes among those nodes while supporting a potentially large number of clients. Thus, ZooKeeper provides a way of “outsourcing” some of the work of coordinating nodes (consensus, operation ordering, and failure detection) to an external service.

一个应用程序最初可能只在一个节点上运行，但最终可能会扩展到数千个节点。尝试在这么多节点上执行多数投票将非常低效。相反，ZooKeeper 在固定数量的节点上运行（通常为三个或五个），并在这些节点上执行其多数投票，同时支持潜在的大量客户端。因此，ZooKeeper 提供了一种将协调节点的一些工作（共识、操作排序和故障检测）“外包”给外部服务的方式。

Normally, the kind of data managed by ZooKeeper is quite slow-changing: it represents information like “the node running on 10.1.1.23 is the leader for partition 7,” which may change on a timescale of minutes or hours. It is not intended for storing the runtime state of the application, which may change thousands or even millions of times per second. If application state needs to be replicated from one node to another, other tools (such as Apache BookKeeper [ 108 ]) can be used.

通常，ZooKeeper 管理的数据类型变化非常缓慢：例如，“运行在 10.1.1.23 的节点是分区 7 的领导者”，这类信息的变化可能在几分钟或几小时内发生。它并不适用于存储应用程序的运行时状态，因为应用程序状态可能每秒钟甚至每毫秒都会发生数千次或数百万次的变化。如果需要将应用程序状态从一个节点复制到另一个节点，则可以使用其他工具（例如 Apache BookKeeper [108]）。

Service discovery

ZooKeeper, etcd, and Consul are also often used for service discovery —that is, to find out which IP address you need to connect to in order to reach a particular service. In cloud datacenter environments, where it is common for virtual machines to continually come and go, you often don’t know the IP addresses of your services ahead of time. Instead, you can configure your services such that when they start up they register their network endpoints in a service registry, where they can then be found by other services.

ZooKeeper、etcd 和 Consul 也常用于服务发现，即查找连接到特定服务所需的 IP 地址。在云数据中心环境中，由于虚拟机经常出现并消失，你通常无法提前知道服务的 IP 地址。因此，你可以配置服务，在它们启动时注册其网络端点到服务注册表中，在那里其他服务可以找到它们。

However, it is less clear whether service discovery actually requires consensus. DNS is the traditional way of looking up the IP address for a service name, and it uses multiple layers of caching to achieve good performance and availability. Reads from DNS are absolutely not linearizable, and it is usually not considered problematic if the results from a DNS query are a little stale [ 109 ]. It is more important that DNS is reliably available and robust to network interruptions.

然而，服务发现是否真的需要共识尚不太清楚。DNS是查找服务名称的IP地址的传统方法，它使用多层缓存来实现良好的性能和可用性。DNS的读取绝对不是线性化的，如果DNS查询的结果有点过时，通常不会被认为是有问题的。更重要的是，DNS可靠可用且能够抵御网络中断。

Although service discovery does not require consensus, leader election does. Thus, if your consensus system already knows who the leader is, then it can make sense to also use that information to help other services discover who the leader is. For this purpose, some consensus systems support read-only caching replicas. These replicas asynchronously receive the log of all decisions of the consensus algorithm, but do not actively participate in voting. They are therefore able to serve read requests that do not need to be linearizable.

虽然服务发现不需要共识，但领导者选举需要。因此，如果您的共识系统已经知道领导者是谁，那么使用该信息来帮助其他服务发现领导者是有意义的。为此，一些共识系统支持只读缓存副本。这些副本异步接收所有共识算法决策的日志，但不参与投票。因此，它们能够为不需要线性化的读取请求提供服务。

Membership services

ZooKeeper and friends can be seen as part of a long history of research into membership services , which goes back to the 1980s and has been important for building highly reliable systems, e.g., for air traffic control [ 110 ].

ZooKeeper和它的伙伴们可以被视为研究成员服务的悠久历史的一部分，这始于20世纪80年代，对于构建高度可靠的系统非常重要，例如空中交通管制[110]。

A membership service determines which nodes are currently active and live members of a cluster. As we saw throughout Chapter 8 , due to unbounded network delays it’s not possible to reliably detect whether another node has failed. However, if you couple failure detection with consensus, nodes can come to an agreement about which nodes should be considered alive or not.

会员服务确定当前哪些节点是集群的活动成员。就像我们在第8章中看到的那样，由于无限制的网络延迟，不可能可靠地检测另一个节点是否失败。但是，如果将故障检测与共识结合起来，节点可以就应认为是活动或非活动状态达成一致。

It could still happen that a node is incorrectly declared dead by consensus, even though it is actually alive. But it is nevertheless very useful for a system to have agreement on which nodes constitute the current membership. For example, choosing a leader could mean simply choosing the lowest-numbered among the current members, but this approach would not work if different nodes have divergent opinions on who the current members are.

可能仍然会发生共识错误地宣布某个节点已经死亡，即使它实际上是活着的。但是对于系统来说，达成关于哪些节点构成当前成员的一致性是非常有用的。例如，选择一个领导者可能意味着只需选择当前成员中编号最低的，但是如果不同节点对当前成员有不同的看法，这种方法就行不通了。