如果数据库能够对上提供只有单个副本的假象，情况会不会大为简化呢？这样让每个客户端都拥有相同的数据视图，而不必担心复制滞后。这就是==可线性化==（也称为==原子一致性==，==强一致性==等）的思想。==其基本的想法是让一个系统看起来好像只有一个数据副本，且所有的操作都是原子的==。有了这个保证，应用程序就不需要关心系统内部的多个副本。
在一个可线性化的系统中，一旦某个客户端成功提交写请求，所有客户端的读请求一定都能看到刚刚写入的值。这种看似单一副本的假象意味着它可以保证读取最近最新值，而不是过期的缓存。换句话说，可线性化是一种就近的保证。为了解释该想法，我们先来看一个非线性化系统的例子。
图 9-1 是一个非线性化的体育网站。Alice 和 Bob 坐在同一个房间里各自观看自己的手机，焦急地等待 2014 年 FIFA 世界杯决赛的结果。刚刚宣布了最终比分之后，Alice 刷新了页面马上看到获胜者，然后兴奋地告诉 Bob。于是 Bob 马上在自己的手机上刷新页面，但他的请求发向了某个落后的数据库副本，结果却显示比赛还在进行之中。
如果 Alice和 Bob 几乎同时刷新页面得到两个不同的结果，他们也不清楚服务器端究竟何时接受、处理这些请求，因此可能并不会特别惊讶。然而，现在的情况却是 Bob 听到了 Alice 兴奋的比分之后再单击刷新，他希望至少是看到刚刚 Alice 播报的最近比分，但却读到过期的结果，这就违背了线性化规则。
可线性化背后的基本思想很简单：使系统看起来好像只有一个数据副本。然而，细究起来还有更多的含义。为了更好地理解可线性化，来看看更多的例子。
图 9-2 展示了三个客户端在线性化数据库中同时读写相同的 key x。在分布式语义下 x 被称为 register。
为简单起见，图 9-2 仅展示了客户端所观察到请求内容，而不是数据库内部。每条线代表一个客户端请求，虚线的开始表示发送请求的时间，结尾则是收到响应的时间。由于网络延迟不确定，==客户端并不清楚数据库具体何时处理请求，而只知道它是在发送之后、响应之前的某个中间时间点==。
在图 9-2 中，x 的初始值为 0，客户端 C 提交写请求将其设置为 1。同时，客户端 A 和 B 在反复轮询数据库以读取最新值。A 和 B 可能会分别读到什么样的返回值呢？
- 客户端 A 的第一个读取操作在写入开始之前已完成，因此返回的是旧值 0。
- 客户端 A 的最后一次读操作是在写操作完成之后才开始的，如果数据库是可线性化的，它肯定会返回新值 1。
- ==与写操作有时间重叠的任何读取操作则可能返回 0 或者 1 这是因为读写之间存在并发，无法确切知道在执行读取时，写入是否已经生效。==
然而，这还没有精确描述线性化：如果与写并发的读操作可能返回旧值或新值，那么在这个过程中，不同的读客户端会看到旧值和新值之间来回跳变的情况。这肯定不符合我们所期望的模拟 “单一数据副本”。
为使系统可线性化，我们需要添加一个重要的约束，如图 9-3 所示。
- ==一旦某个读操作返回了新值，之后所有的读（包括柜同或不同的客户端）都必须返回新值==。
在一个可线性化的系统中，在写操作的开始与结束之间必定存在某个时间点，x 的值发生了从 0 到 1 的跳变。如果某个客户端的读取返回了新值 1，即使写操作尚未提交，那么所有后续的读取也必须全部返回新值。
图 9-3 中的箭头表示时序依赖关系。客户端 A 首先读到新值 1，在 A 读取返回之后，B 开始读取，由于 B 的读取严格在 A 的读取之后发生，因此即使 C 的写入仍在进行之中，也必须返回 1。这和图 9-1 中 Alice 和 Bob 的情况类似，在 Alice 读取新值之后，Bob 也预期读取新值。
可以进一步细化时序图来可视化每步操作具体在哪个时间点生效，如图 9-4 所示。
在图 9-4 中，除了读写之外，我们引入了第三种类型的操作：CAS。
图 9-4 中的每个操作都有一条竖线，表示可能的执行时间点。这些标记以前后关系依次连接起来，最终的结果必须是一个有效的 register 读写顺序，即每个读操作须返回最近写操作所设置的值。
==可线性化要求，如果连接这些标记的竖线，它们必须总是按时间箭头（从左到右）向前移动，而不能向后移动。这个要求确保了之前所讨论的就近性保证：一旦新值被写入或读取，所有后续的读都看到的是最新的值，直到被再次覆盖==。
- 客户端 B 首先发送读 x 的请求，接下来客户端 D 发送请求将 x 置为 0，紧接着客户端 A 又发送请求将 x 置为 1，而最终返回给 B 的值为 1（A 所写入的值）。 这是可能的，它意味着数据库执行的顺序是：首先处理 D 的写入 0，然后是 A 的写入 1 最后是 B 的读取。虽然这并不是请求发送的顺序，但考虑到请求并发以及网络延迟等情况，例如或许 B 的读请求网络延迟更大，导致在两次写执行之后才到达数据库，因此这是一个合法的可接受的处理顺序。
- 客户端 A 在收到数据库写响应之前，客户端 B 即读到了值 1 这表明写入已成功。这是可能的，但它并不代表执行读发生在执行写之前，只是意味着很可能由于网络延迟而耽搁了客户端 A 接受响应。
- 模型没有假定事务间的隔离，即另一个并发客户端可能随时会修改值。例如，C 首先读取到 1 然后读到 2，原因是两次读取之间值被客户端 B 修改了。
- 客户 B 的最后一次读取（阴影的方框）不满足线性化。该操作与 C 的 cas 写操作同时发生，后者将 x 从 2 更新为 4。==在没有其他请求时，B 读取可以返回 2==。==但是在 B 读取开始之前，客户端 A 已经读取了新值 4，所以不允许 B 读到比 A 更老的值==。这一点与图 9-1 中的 Alice 和 Bob 的情况是一样的。
那什么情况下应该使用线性化呢？
主从复制的系统需要确保有且只有一个主节点，否则会产生脑裂。选举新的主节点常见的方法是使用锁：即每个启动的节点都试图获得锁，其中只有一个可以成功即成为主节点。不管锁具体如何实现，它必须满足可线性化：所有节点都必须同意哪个节点持有锁，否则就会出现问题。
唯一性约束在数据库中很常见。如果要在写入数据时强制执行这些约束（例如，如果两个人试图同时创建具有相同名称的用户或文件，其中一个必须返回错误），则也需要线性化。
这种情况本质上与加锁非常类似：用户注册等同于试图对用户名进行加锁操作。该操作也类似于原子比较和设置：如果当前用户名尚未被使用，就设置用户名与客户 ID进行关联。
请注意图 9-1中的一个细节：如果 Alice 没有高呼比分，Bob 可能就不会知道他的查询结果是过期的。或许他会在几秒之后再次刷新页面，然后看到最终的比分。线性化违例之所以被注意到，是因为系统中存在其他的通信渠道（例如，Alice 对 Bob 发出的声音来传递信息）。
计算机系统也会出现类似的情况。例如，用户可以上传照片到某网站，有一个后台进程将照片调整为更低的分辨率（即缩略图）以方便更快下载。该网站架构和数据流如图 9-5 所示。
这里需要明确通知图像调整模块来调整哪些图片，系统采用了消息队列将此命令从 Web 服务器发送到调整器。相反，照片会先写入文件存储服务，当写入完成后，把调整的命令放入队列。
如果文件存储服务是可线性化的，那么系统应该可以正常工作。否则，这里就会引入竞争条条件：消息队列（图 9-5 中的步骤 3 和步骤 4）可能比存储服务内部的复制执行更快。在这种情况下，当调整模块在读取图像（步骤 5）时，可能会看到图像的某个旧版本，或者根本读不到任何内容。如果它碰巧读到了旧版本的图像并进行处理，会导致文件存储中的全尺寸图片与调整之后图片出现永久的不一致。
线性化并非避免这种竞争的唯一方法，但却是最容易理解的。如果可以控制某一个通信通道（例如消息队列），可以尝试第 5 章的 “读自己的写“ 方法，但会引入额外的复杂性。
系统容错最常见的方法就是采用复制机制。我们再来回顾一下第 5 章所介绍的多种复制方案，看看那些满足可线性化：
-
主从复制：部分支持可线性化
- 如果从主节点或者同步更新的从节点上读取，则可以满足线性化但并非每个主从复制的具体数据库实例都是可线性化的，主要是因为它们可能采用了快照隔离的设计，或者实现时存在并发方面的 bug。
- 而从主节点上读取的前提是你确定知道哪个节点是主节点。正如在第 8 章 ”真相” 由多数决定中所讨论的，某节点可能自认为是主节点，但事实并非如此，这个 ”自以为是“ 的主节点如果对外提供服务，就会违反线性化。
-
共识算法：可线性化（稍后讨论）
-
多主复制：不可线性化
具有多主节点复制的系统通常无法线性化的，主要由于它们同时在多个节点上执行并发写入，并将数据异步复制到其他节点。因此它们可能会产生冲突的写入，需要额外的解决方案。
-
无主复制：可能不可线性化
例如基于墙上时钟（包括 Cassandra，参阅第 8 章 “依赖于同步的时钟”）的 “最后写入获胜“ 冲突解决方法几乎肯定是非线性化，因为这种时间戳无法保证与实际事件顺序一致（例如由于时钟偏移）。
直觉上，对于 Dynamo 风格的复制模型，如果读写遵从了严格 quorum，应该是可线性化的。然而如果遭遇不确定的网络延迟，就会出现竞争条件，如图 9-6 所示。
虽然满足了仲裁条件（w+r>n），但很明显这不是线性化的：B 的请求在 A 的请求完成之后才开始，A 返回了新值，但 B 却得到了旧值。这又类似图 9-1 中 Alice和 Bob 的情况。
基于多主复制的数据库，如果两个数据中心之间发生网络中断，每个数据中心内都可以继续正常运行：由于从一个数据中心到另一个数据中心的复制是异步，期间发生的写操作都暂存在本地队列，等网络恢复之后再继续同步。
对于主从复制系统，数据中心之间的网络一旦中断，连接到从数据中心的客户端无法再联系上主节点，也就无法完成任何数据库写入和线性化读取。从节点可以提供读服务，但内容可能是过期的（非线性化保证）。所以，如果应用程序要求线性化读写，则网络中断一定会违背这样的要求。
不仅仅是主从复制和多主复制才有上面的问题，无论如何实现，任何可线性化的数据库都有这样问题；事实上，这个问题也不局限于多数据中心部署的情况，即使在一个数据中心内部，只要有不可靠的网络，都会发生违背线性化的风险。我们可以做以下的权衡考虑：
- 如果应用要求线性化，但由于网络方面的问题，某些副本与其他副本断开连接之后无法继续处理请求，就必须等待网络修复，或者直接返回错误。无论哪种方式，结果是服务不可用。
- 如果应用不要求线性化，那么断开连接之后，每个副本可独立处理请求例如写操作（多主复制）。此时，服务可用，但结果行为不符合线性化。
CAP有时也代表一致性，可用性，分区容错性，系统只能支持其中两个特性。不过，这种理解存在误导性，网络分区是一种故障， 不管喜欢还是不喜欢，它都可能发生，所以无法选择或逃避分区的问题。
在网络正常的时候，系统可以同时保证一致性（线性化）和可用性。而一旦发生了网络故障，必须要么选择线性（一致性），要么可用性。因此，更准确的称呼应该是 “==网络分区情况下，选择一致还是可用=="。 高可靠的网络会帮助减少发生的概率，但无法做到彻底避免。
正式定义的 CAP 定理范围很窄， 它只考虑了一种一致性模型（即线性化）和一种故障（网络分区，节点仍处千活动状态但相互断开），而没有考虑网络延迟、节点失败或其他需要折中的情况。因此，尽管 CAP 在历史上具有重大的影响力，但对于一个具体的系统设计来说，它可能没有太大的实际价值。
虽然线性化是个很有用的保证，但实际上很少有系统真正满足线性化。例如，现代多核 CPU 上的内存甚至就是非线性化：如果某个 CPU 核上运行的线程修改一个内存地址，紧接着另一个 CPU 核上的线程尝试读取，则系统无法保证可以读到刚刚写入的值，除非使用了内存屏障或 fence 指令。
为什么这样呢？首先，CAP 理论不适用于当今的多核-内存一致性模型：在计算机内部，我们通常假设通信是可靠的，例如我们不会假定一个 CPU 核在与其他核断开之后还能安然工作。之所以放弃线性化的原因就是性能，而不是为了容错。
许多分布式数据库也是类似，它们选择不支持线性化是为了提高性能，而不是为了保住容错特性，无论是否发生了网络故障，线性化对性能的影响都是巨大的。
因果关系对所发生的事件施加了某种排序：发送消息先于收到消息；问题出现在答案之前等，或者就像在现实生活中一样，一件事情会导致另一件事情：一个节点根据读取的数据做出决定，然后写入结果，另一个节点读取写入的结果之后再写入新的内容，诸如此类。这些因果关系的依赖链条定义了系统中的因果顺序，即某件事应该发生另一件事情之前。
如果系统服从因果关系所规定的顺序，我们称之为==因果一致性==（ causally consistent）。例如，快照隔离提供了因果一致性：当从数据库中读数据时，如果查询到了某些数据，也一定能看到触发该数据的前序事件（假设期间没有发生删除操作）。
==全序==（total order）关系支持任何两个元素之间进行比较，即对于任意两个元素，总是可以指出哪个更大，哪个更小。例如，自然数符合全序关系，随便给出两个数字比如 5 和 13，都可以进行比较。
但是，有些集合并不符合全序，例如集合 {a, b} 大于集合 {b, c} 么？因为它们都不是对方的子集，所以无法直接比较它们。我们称之为不可比较（incomparable），数学集合只能是==偏序==（partially ordered）。某些情况下，一个集合可以包含另一个（如果该集合包含另一个集合的所有元素），否则则无法比较。
全序和偏序的差异也会体现在不同的数据库一致性模型中：
-
可线性化
在一个可线性化的系统中，存在全序操作关系。系统的行为就好像只有一个数据副本，且每个操作都是原子的，这意味着对于任何两个操作，我们总是可以指出哪个操作在先。这种全序排列序如图 9-4 中的时间线所示。
-
因果关系
如果两个操作都没有发生在对方之前，那么这两个操作是并发关系（参阅第 5 章 "Happens-before 关系与并发"）。换言之，如果两个事件是因果关系（一个发生在另一个之前），那么这两个事件可以被排序；而并发的事件则无法排序比较。这表明因果关系至少可以定义为偏序，而非全序。
因此，根据这个定义，==在可线性化数据存储中不存在并发操作，一定有一个时间线将所有操作都全序执行==。==可能存在多个请求处于等待处理的状态，但是数据存储保证了在特定的时间点执行特定的操作==，所以是单个时间轴，单个数据副本，没有并发。
并发意味着时间线会出现分支和合并，而不同分支上的橾作无法直接比较。第 5 章中我们给出了这种例子，如图 5-14 并非一条直线式的全序，而是多个不同的操作同时进行。图中的箭头表明这只是因果关系，即部分操作之间的偏序。
那么因果序和可线性化之间是什么关系呢？答案是可线性化一定意味着因果关系：==任何可线性化的系统都将正确地保证因果关系==。
可线性化可以确保因果性这一结论，使线性化系统更加简单易懂而富有吸引力。但是，正如在 ”线性化的代价“ 将要阐述的，线性化会显著降低性能和可用性，尤其是在严重网络延迟的情况下（例如多数据中心）。正因如此，一些分布式数据系统已经放弃了线性化，以换来更好的性能，但也存在可能无法正确工作的风险。
好消息是==线性化并非是保证因果关系的唯一途径，还有其他方法使得系统可以满足因果一致性而免于线性化所带来的性能问题==。事实上，因果一致性可以认为是，不会由于网络延迟而显著影响性能，又能对网络故障提供容错的最强的一致性模型。
==在许多情况下，许多看似需要线性化的系统实际上真正需要的是因果一致性，后者的实现可以高效很多==。
为保持因果关系，需要知道哪个操作发生在前。这里只需偏序关系，或许并发操作会以任意顺序执行，但如果一个操作发生在另一个操作之前，那么每个副本都应该按照相同的顺序处理。因此，当某个副本在处理一个请求时，必须确保所有因果在前的请求都已完成处理；否则，后面的请求必须等待直到前序操作处理完毕。
为了确定请求的因果依赖关系，我们需要一些手段来描述系统中节点所知道的 “知识”。
确定请求的先后顺序与第五章 “检测并发写” 中所讨论的技巧类似。后者针对的是无主复制中的因果关系，该场景需要去检测对同一个主键的并发写请求，从而避免更新丢失。因果一致性则要更进一步，它需要跟踪整个数据库请求的因果关系，而不仅仅是针对某个主键。版本向量技术可以推广为一种通用的解决方案。
为了确定因果关系，数据库需要知道应用程序读取的是哪个版本的数据。这就是为什么在图 5-13 中先前读操作的版本号在提交时要传回到数据库。SSI 的冲突检测也是类似想法，如第 7 章 “可串行化的快照隔离” 所介绍的：当事务提交时，数据库要检查事务曾经读取的数据版本现在是否仍是最新的。为此，数据库需要跟踪事务读取了哪些版本的数据。
虽然因果关系很重要，但实际上跟踪所有的因果关系不切实际。在许多应用程序中，客户端在写入之前会先读取大批数据，系统无法了解之后的写入究竟是依赖于全部读取内容，还是仅仅是其中一小部分。但很明显，显式跟踪所有巳读数据意味着巨大的运行开销。
这里还有一个更好的方法：我们可以使用序列号或时间戳来排序事件。时间戳不一定来自墙上时钟（或者物理时钟，但正如第 8 章所讨论的，物理时钟存在很多问题）。它可以只是一个逻辑时钟，例如采用算法来产生一个数字序列用以识别操作，通常是递增的计数器。
这样的序列号或时间戳非常紧凑（只有几字节的大小），但它们保证了全序关系。也就是说，每一个操作都有唯一的顺序号，并且总是可以通过比较来确定哪个更大（即操作发生在后）。
特别是，我们可以按照与因果关系一致的顺序来创建序列号：保证如果操作 A 发生在 B 之前，那么 A 一定在全序中出现在 B 之前（即 A 的序列号更小）。并行操作的序列可能是任意的。这样的全局排序可以捕获所有的因果信息，但也强加了比因果关系更为严格的顺序性。
如果系统不存在这样唯一的主节点（例如可能是多主或者无主类型的数据库，或者数据库本身是分区的），如何产生序列号就不是那么简单了。实践中可以采用以下方法：
- 每个节点都独立产生自己的一组序列号。例如，如果有两个节点，则一个节点只生成奇数，而另一个节点只生成偶数。
- 可以把墙上时间戳信息（物理时年中）附加到每个操作上。
- 可以预先分配序列号的区间范围。
上述三种思路都可行，相比于把所有请求全部压给唯一的主节点具有更好的扩展性。它们为每个操作生成一个唯一的、近似增加的序列号。不过，它们也都存在一个问题：所产生的序列号与因果关系并不严格一致。
刚才所描述的三个序列号发生器可能与因果关系存在不一致，但还有一个简单的方法可以产生与因果关系一致的序列号。它被称为兰伯特时间戳（Lamport timestamp）由 Leslie Lamport 于 1978 年提出。
图 9-8 给出了 Lamport 时间戳的示例。首先每个节点都有一个唯一的标识符，且每个节点都有一个计数器来记录各自己处理的请求总数。Lamport 时间戳是一个值对（计数器, 节点 ID）。两个节点可能会有相同的计数器值，但时间戳中还包含节点 ID 信息，因此可以确保每个时间戳都是唯一的。
Lamport 时间戳与物理墙上时钟并不存在直接对应关系，但它可以保证全序：给定两个 Lamport 时间戳，计数器较大那个时间戳大；如计数器值正好相同，则节点 ID 越大，时间戳越大。
到目前为止，该思路与上一节所描述的奇数/偶数计数器并无本质不同。但是 Lamport 时间戳的核心亮点在于使它们与因果性保持一致，具体如下所示：==每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值，并在每个请求中附带该最大计数器值。当节点收到某个请求（或者回复）时，如果发现请求内嵌的最大计数器值大于节点自身的计数器值，则它立即把自己的计数器修改为该最大值。==
如图 9-8 所示，客户端 A 从节点 2 收到计数器值 5，然后将最大值 5 发送到节点 1。此时，节点 1 的计数器仅为 1 但是它立即向前跳到 5，所以下一个操作将获得计数器值 6。
只要把最大计数器值嵌入到每一个请求中，该方案可以确保 Lamport 时间戳与因果关系一致，而请求的因果依赖性一定会保证后发生的请求得到更大的时间戳。
Lamport 时间戳有时会与版本向量发生混淆（第 5 章 “检测并发写“ 中介绍了版本向量)。虽然存在一些相似之处，但它们的目的不同：版本向量用以区分两个操作是并发还是因果依赖，而 Lamport 时间戳则主要用于确保全序关系。即使 Lamport 时间戳与因果序一致，但根据其全序关系却无法区分两个操作属于并发关系， 还是因果依赖关系。Lamport 时间戳优于版本向显之处在于它更加紧凑和高效。
虽然 Lamport 时间戳定义了与因果序一致的全序关系，但还不足以解决实际分布式系统中许多常见的问题。
例如，一个账户系统需要确保用户名唯一标识用户。即两个用户如果同时尝试使用相同的用户名创建账户时，确保其中一个成功，另一个必须失败。
乍看之下，似乎全序关系（例如使用 Lamport 时间戳）应该可以解决问题：如果有这样并发的操作，则选择时间戳较低的那个作为获胜者（先申请用户名的那个请求），而让时间戳大的请求失败。由于时间戳有序，所以这样的比较方法也应该是可行的。
但是，这种方法确定胜利者有这样一个前提条件：需要收集系统中所有的用户创建请求，然后才可以比较它们的时间戳。然而，当节点刚刚收到用户的创建请求时，它无法当时就做出决定该请求应该成功还是失败。此时，节点根本不知道是否有另一个节点在同时创建相同用户名（以及那个请求所附带的时间戳）。
而为了获得上述两点信息，系统就必须检查每个节点，询问它们在做什么。如果万一某个节点出现故障或者由于网络问题而无法连接，那么方法就无法正常运转。显然这不是我们所期望的容错系统。
这里问题的关键是，只有在收集了所有的请求信息之后，才能清楚这些请求之间的全序关系。如果另一个节点执行了某些操作，但你无法知道那是什么，就无法构造出最终的请求序列。也许，来自该未知操作确实需要插入到全序集合中才能正确评估出下一步。
总而言之，为了实现像用户名唯一性约束这样的目标，仅仅对操作进行全序排列还是不够的，还需要知道这些操作是否发生、何时确定等。假如能够在创建用户名时，已经确定知道了没有其他节点正在执行相同用户名的创建，你大可以直接安全返回创建成功。
要想知道什么时候全序关系已经确定就需要之后的 “全序关系广播”。
全序关系广播通常指节点之间交换消息的某种协议。下面是一个非正式的定义,它要求满足两个基本安全属性：
- 可靠发送：没有消息丢失，如果消息发送到了某一个节点，则它一定要发送到所有节点。
- 严格有序：消息总是以相同的顺序发送给每个节点。
即使节点或网络出现了故障，全序关系广播算法的正确实现也必须保证上述两条。当然，网络中断时是不可能发送成功的，但算法要继续重试，直到最终网络修复，消息发送成功（且必须以正确的顺序发送）。
像 ZooKeeper 和 etcd 这样的共识服务实际上就实现了全关系序广播。关系广播与共识之间有着密切联系，本章稍后会揭示这一点。
全序关系广播正是数据库复制所需要的：如果每条消息代表数据库写请求，并且每个副本都按相同的顺序处理这些写请求，那么所有副本可以保持一致（或许有些滞后）。该原则也被称为==状态机复制==（ state machine replication）。
可以使用全序关系广播来实现可串行化事务。如第 7 章 "实际串行执行" 所述，如果每条消息表示一个确定性事务并且作为存储过程来执行，且每个节点都遵从相同的执行顺序，那么可以保证数据库各分区以及各副本之间的一致性。
==全序关系广播另一个要点是顺序在发送消息时已经确定，如果消息发送成功，节点不允许追溯地将某条消息插入到先前的某个位置上==。这一点使得全序关系广播比基于时间戳排序要求更强。
理解全序关系广播的另一种方式是将其视为日志（如复制日志，事务日志或预写日志），传递消息就像追加方式更新日志。由于所有节点必须以相同的顺序发送消息，因此所有节点都可以读取日志并看到相同的消息序列。
全序关系广播对于提供 fencing 令牌的锁服务也很有用（参阅第 8 章的 "Fencing 令牌"）。每个获取锁的请求都作为消息附加到日志中，所有消息按照日志中的顺序依次编号。序列号还可以作为令牌，它符合单调递增要求。在 ZooKeeper 中，该序列号被称为 zxid。
如图 9-4 所示，在一个可线性化的系统中有全序操作集合。这是否意味着可线性化与全序关系广播是完全相同呢？不完全是，但两者之间有着密切的联系。
全序关系广播是基于==异步模型==：保证消息以固定的顺序可靠地发送，但是==不保证消息何时发送成功==（因此某个接收者可能明显落后于其他接收者）。而可线性化则强调就近性：读取时保证能够看到最新的写入值。
通常意义上，实现线性化读写 register 是一个更容易的问题。全序关系广播相当于共识，在异步的崩溃-中止模型中不存在确定性的解决方案，而线性化读写register 则能可以在该模型下得以实现。然而，如果进一步支持原子操作例如原子比较-设置，或者原子自增-读取，则它就升级等价于共识问题。
如果有了全序关系广播，就可以在其上构建线性化的存储系统。例如，确保用户名唯一标识一个用户。
设想一下，对于每一个可能的用户名，都可以有一个带有原子比较-设置操作的线性化 register。每个 register 初始值为空（表示尚未使用）。当用户创建一个用户名时，对该用户名的 register 执行比较设置操作：仅当 register 值为空时，将其设置为新的用户账号。如果多个用户试图同时获取相同的用户名，则只有一个原子比较-设置操作成功。
可以通过使用全序关系广播以追加日志的方式来实现线性化的原子比较-设置操作，步骤如下所示：
- 在日志中追加一条消息，并指明想要的用户名。
- 读取日志，将其广播给所有节点，并等待回复。
- 检查是否有任何消息声称该用户名已被占用。如果第一条这样的回复来自于当前节点，那么就成功获得该用户名，可以提交该获取声明（也许附加另一条消息到日志）并返回给客户端。反之，如果声称占用的第一条回复消息来自其他节点，则中止操作。
由于日志条目以相同的顺序发送到所有节点，而如果存在多个并发写入，则所有节点将首先决定哪个请求在先。选择第一个写请求作为获胜者，并中止其他请求，以确保所有节点同意一个写请求最终要么提交成功要么中止。
==虽然此过程可确保线性化写入，但它却无法保证线性化读取，即从异步日志更新的存储中读取数据时，可能是旧值==。具体来说，这里只提供了==顺序一致性==（sequential consistency），有时也称为时间线一致性（timeline consistency），它弱于线性化保证。为了同时满足线性化读取，有以下几个方案：
- ==可以采用追加的方式把读请求排序、广播，然后各个节点获取该日志，当本节点收到消息时才执行真正的读操作。==消息在日志中的位置已经决定了读取发生的时间点。etcd 的 quorum 读取和这个思路有相似之处。
- ==如果可以以线性化的方式获取当前最新日志中消息的位置，则查询位置，等待直到该位置之前的所有条目都已经发送给你，接下来再执行读取。==这 ZooKeeper 的 sync() 操作思路相同。
- 可以从同步更新的副本上进行读取，这样确保总是读取最新值。
前面一节介绍了如何基于全序关系广播来构建线性化的原子比较-设置操作。我们也可以反过来，假定已有了线性化的存储，在其上构建全序关系广播。
最简单的方法是假设有一个线性化的 register 来存储一个计数，然后使其支持原子自增-读取操作或者原子比较-设置操作。
解法思路很简单：对于每个要通过全序关系广播的消息，原子递增并读取该线性化的计数，然后将其作为序列号附加到消息中。接下来，将消息广播到所有节点（如果发生丢失，则重新发送），而接受者也严格按照序列化来发送回复消息。
请注意，与 Lamport 时间戳不同，==通过递增线性化 register 获得的数字不会存在任何间隙。因此，如果节点完成了消息 4 的发送，且接收到了序列化 6 的消息，那么在它对消息 6 回复之前必须等待消息 5==。Lamport 时间戳则不是这样，而这也是区别全序关系广播与基于时间戳排序的关键。
使用原子自增操作来创建线性化整数有多难呢？答案还是那样，如果不存在失效，就非常容易，甚至可以把它保存在某个节点的内存变量中。难点在于处理节点的网络中断，以及节点失效时如何恢复该值。事实上，如果对线性化的序列号发生器深思熟虑之后所得到的最终结果，往往亳无意外地指向了共识算法。
这并非巧合，可以证明，==线性化的原子比较-设置（或自增）register 与全序关系广播二者都等价于共识问题==。也就是说，如果你能解决其中的一个问题，那么就可以把方案用于解决其他问题