线性一致性

所谓的线性一致性(Linearizability)，也称为原子一致性（Atomic Consistency）、强一致性（Strict Consistency）、强一致性（strong consistency）、立即一致性（immediate consistency）或外部一致性（external consistency）。在一个线性一致的系统中，只要一个客户端成功完成写操作，所有客户端从数据库中读取数据必须能够看到刚刚写入的值。线性一致性对多副本的系统能够对外表现地像只有单个副本一样，即系统能保障读到的值是最近的、最新的而不是来自过时的缓存或副本。换言之，线性一致性是一个新鲜度保证（recency guarantee）。下图即使某个非线性一致性系统的例子：

Alice 和 Bob 正坐在同一个房间里，都盯着各自的手机，关注着 2014 年 FIFA 世界杯决赛的结果。在最后得分公布后，Alice 刷新页面，看到宣布了获胜者，并兴奋地告诉 Bob。Bob 难以置信地刷新了自己的手机，但他的请求路由到了一个落后的数据库副本上，手机显示比赛仍在进行。如果 Alice 和 Bob 在同一时间刷新并获得了两个不同的查询结果，也许就没有那么令人惊讶了。因为他们不知道服务器处理他们请求的精确时刻。然而 Bob 是在听到 Alice 惊呼最后得分之后，点击了刷新按钮（启动了他的查询），因此他希望查询结果至少与爱丽丝一样新鲜。但他的查询返回了陈旧结果，这一事实违背了线性一致性的要求。综上所述，线性一致性对一致性的要求两个：

• 任何一次读都能读到某个数据的最近一次写的数据。
• 系统中的所有进程，看到的操作顺序，都和全局时钟下的顺序一致。

强一致性要求无论数据的更新操作是在哪个副本上执行，之后所有的读操作都要能够获取到更新的最新数据。对于单副本的数据来说，读和写都是在同一份数据上执行，容易保证强一致性，但对于多副本数据来说，若想保障强一致性，就需要等待各个副本的写入操作都执行完毕，才能提供数据的读取，否则就有可能数据不一致，这种情况需要通过分布式事务来保证操作的原子性，并且外界无法读到系统的中间状态。显然这强一致性对全局时钟有非常高的要求。强一致性，只是存在理论中的一致性模型，比它要求更弱一些的，就是顺序一致性。

什么使得系统线性一致？

线性一致性背后的基本思想很简单：使系统看起来好像只有一个数据副本。然而确切来讲，实际上有更多要操心的地方。为了更好地理解线性一致性，让我们再看几个例子。下图显示了三个客户端在线性一致数据库中同时读写相同的键 x。在分布式系统文献中，x 被称为寄存器（register），例如，它可以是键值存储中的一个键，关系数据库中的一行，或文档数据库中的一个文档。

每个柱都是由客户端发出的请求，其中柱头是请求发送的时刻，柱尾是客户端收到响应的时刻。因为网络延迟变化无常，客户端不知道数据库处理其请求的精确时间，只知道它发生在发送请求和接收响应的之间的某个时刻。在这个例子中，寄存器有两种类型的操作：

• $read(x)⇒v$ 表示客户端请求读取寄存器 x 的值，数据库返回值 v。

• $write(x,v)⇒r$ 表示客户端请求将寄存器 x 设置为值 v，数据库返回响应 r（可能正确，可能错误）。

x 的值最初为 0，客户端 C 执行写请求将其设置为 1。发生这种情况时，客户端 A 和 B 反复轮询数据库以读取最新值。A 和 B 的请求可能会收到怎样的响应？

• 客户端 A 的第一个读操作，完成于写操作开始之前，因此必须返回旧值 0。
• 客户端 A 的最后一个读操作，开始于写操作完成之后。如果数据库是线性一致性的，它必然返回新值 1：因为读操作和写操作一定是在其各自的起止区间内的某个时刻被处理。如果在写入结束后开始读取，则必须在写入之后处理读取，因此它必须看到写入的新值。
• 与写操作在时间上重叠的任何读操作，可能会返回 0或1，因为我们不知道读取时，写操作是否已经生效。这些操作是并发（concurrent）的。

但是，这还不足以完全描述线性一致性：如果与写入同时发生的读取可以返回旧值或新值，那么读者可能会在写入期间看到数值在旧值和新值之间来回翻转。这不是我们所期望的仿真“单一数据副本”的系统。为了使系统线性一致，我们需要添加另一个约束：

在一个线性一致的系统中，我们可以想象，在 x 的值从 0 自动翻转到 1 的时候（在写操作的开始和结束之间）必定有一个时间点。因此，如果一个客户端的读取返回新的值 1，即使写操作尚未完成，所有后续读取也必须返回新值。上图中的箭头说明了这个时序依赖关系，客户端 A 是第一个读取新的值 1 的位置。在 A 的读取返回之后，B 开始新的读取。由于 B 的读取严格在发生于 A 的读取之后，因此即使 C 的写入仍在进行中，也必须返回 1。除了读写之外，还增加了第三种类型的操作：

• $cas(x, v_{old}, v_{new})⇒r$ 表示客户端请求进行原子性的比较与设置操作。如果寄存器 $x$ 的当前值等于 $v_{old}$，则应该原子地设置为 $v_{new}$ 。如果 $x≠v_{old}$，则操作应该保持寄存器不变并返回一个错误。$r$ 是数据库的响应（正确或错误）。

下图中每个操作都在我们认为执行操作的时候用竖线标出（在每个操作的条柱之内）。这些标记按顺序连在一起，其结果必须是一个有效的寄存器读写序列（每次读取都必须返回最近一次写入设置的值）。线性一致性的要求是，操作标记的连线总是按时间（从左到右）向前移动，而不是向后移动。这个要求确保了我们之前讨论的新鲜性保证：一旦新的值被写入或读取，所有后续的读都会看到写入的值，直到它被再次覆盖。

• 第一个客户端 B 发送一个读取 x 的请求，然后客户端 D 发送一个请求将 x 设置为 0，然后客户端 A 发送请求将 x 设置为 1。尽管如此，返回到 B 的读取值为 1（由 A 写入的值）。这是可以的：这意味着数据库首先处理 D 的写入，然后是 A 的写入，最后是 B 的读取。虽然这不是请求发送的顺序，但这是一个可以接受的顺序，因为这三个请求是并发的。也许 B 的读请求在网络上略有延迟，所以它在两次写入之后才到达数据库。

• 在客户端 A 从数据库收到响应之前，客户端 B 的读取返回 1，表示写入值 1 已成功。这也是可以的：这并不意味着在写之前读到了值，这只是意味着从数据库到客户端 A 的正确响应在网络中略有延迟。

• 此模型不假设有任何事务隔离：另一个客户端可能随时更改值。例如，C 首先读取 1，然后读取 2，因为两次读取之间的值由 B 更改。可以使用原子比较并设置（cas）操作来检查该值是否未被另一客户端同时更改：B 和 C 的 cas 请求成功，但是 D 的 cas 请求失败（在数据库处理它时，x 的值不再是 0）。

• 客户 B 的最后一次读取（阴影条柱中）不是线性一致性的。该操作与 C 的 cas 写操作并发（它将 x 从 2 更新为 4）。在没有其他请求的情况下，B 的读取返回 2 是可以的。然而，在 B 的读取开始之前，客户端 A 已经读取了新的值 4，因此不允许 B 读取比 A 更旧的值。

这就是线性一致性背后的直觉。正式的定义更准确地描述了它。通过记录所有请求和响应的时序，并检查它们是否可以排列成有效的顺序，测试一个系统的行为是否线性一致性是可能的（尽管在计算上是昂贵的）。

线性一致性与可序列化

线性一致性容易和可序列化相混淆，因为两个词似乎都是类似“可以按顺序排列”的东西。但它们是两种完全不同的保证，区分两者非常重要：

• 可序列化：可序列化（Serializability）是事务的隔离属性，每个事务可以读写多个对象（行，文档，记录）。它确保事务的行为，与它们按照某种顺序依次执行的结果相同（每个事务在下一个事务开始之前运行完成）。这种执行顺序可以与事务实际执行的顺序不同。

• 线性一致性：线性一致性（Linearizability）是读取和写入寄存器（单个对象）的新鲜度保证。它不会将操作组合为事务，因此它也不会阻止写偏差等问题，除非采取其他措施（例如物化冲突）。

一个数据库可以提供可串行性和线性一致性，这种组合被称为严格的可串行性或强的单副本强可串行性（strong-1SR）。基于两阶段锁定的可串行化实现或实际串行执行通常是线性一致性的。但是，可序列化的快照隔离不是线性一致性的：按照设计，它可以从一致的快照中进行读取，以避免锁定读者和写者之间的争用。一致性快照的要点就在于它不会包括比快照更新的写入，因此从快照读取不是线性一致性的。

线性一致性的案例

锁定和领导选举

一个使用单主复制的系统，需要确保领导真的只有一个，而不是几个（脑裂）。一种选择领导者的方法是使用锁：每个节点在启动时尝试获取锁，成功者成为领导者。不管这个锁是如何实现的，它必须是线性一致的：所有节点必须就哪个节点拥有锁达成一致，否则就没用了。诸如 Apache ZooKeeper 和 etcd 之类的协调服务通常用于实现分布式锁和领导者选举。它们使用一致性算法，以容错的方式实现线性一致的操作。还有许多微妙的细节来正确地实现锁和领导者选择，而像 Apache Curator 这样的库则通过在 ZooKeeper 之上提供更高级别的配方来提供帮助。但是，线性一致性存储服务是这些协调任务的基础。

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

约束和唯一性保证

唯一性约束在数据库中很常见：例如，用户名或电子邮件地址必须唯一标识一个用户，而在文件存储服务中，不能有两个具有相同路径和文件名的文件。如果要在写入数据时强制执行此约束（例如，如果两个人试图同时创建一个具有相同名称的用户或文件，其中一个将返回一个错误），则需要线性一致性。这种情况实际上类似于一个锁：当一个用户注册你的服务时，可以认为他们获得了所选用户名的“锁定”。该操作与原子性的比较与设置非常相似：将用户名赋予声明它的用户，前提是用户名尚未被使用。

如果想要确保银行账户余额永远不会为负数，或者不会出售比仓库里的库存更多的物品，或者两个人不会都预定了航班或剧院里同一时间的同一个位置。这些约束条件都要求所有节点都同意一个最新的值（账户余额，库存水平，座位占用率）。在实际应用中，处理这些限制有时是可以接受的（例如，如果航班超额预订，你可以将客户转移到不同的航班并为其提供补偿）。在这种情况下，可能不需要线性一致性。然而，一个硬性的唯一性约束（关系型数据库中常见的那种）需要线性一致性。其他类型的约束，如外键或属性约束，可以在不需要线性一致性的情况下实现。

跨信道的时序依赖

例如，假设有一个网站，用户可以上传照片，一个后台进程会调整照片大小，降低分辨率以加快下载速度（缩略图）。图像缩放器需要明确的指令来执行尺寸缩放作业，指令是 Web 服务器通过消息队列发送的。Web 服务器不会将整个照片放在队列中，因为大多数消息代理都是针对较短的消息而设计的，而一张照片的空间占用可能达到几兆字节。取而代之的是，首先将照片写入文件存储服务，写入完成后再将缩放器的指令放入消息队列。该系统的架构和数据流如下图所示。

如果文件存储服务是线性一致的，那么这个系统应该可以正常工作。如果它不是线性一致的，则存在竞争条件的风险：消息队列（步骤 3 和 4）可能比存储服务内部的复制更快。在这种情况下，当缩放器读取图像（步骤 5）时，可能会看到图像的旧版本，或者什么都没有。如果它处理的是旧版本的图像，则文件存储中的全尺寸图和略缩图就产生了永久性的不一致。出现这个问题是因为 Web 服务器和缩放器之间存在两个不同的信道：文件存储与消息队列。没有线性一致性的新鲜性保证，这两个信道之间的竞争条件是可能的。线性一致性并不是避免这种竞争条件的唯一方法，但它是最容易理解的。如果你可以控制额外信道，则可以使用在“读己之写”讨论过的备选方法，不过会有额外的复杂度代价。

实现线性一致的系统

我们已经见到了几个线性一致性有用的例子，让我们思考一下，如何实现一个提供线性一致语义的系统。由于线性一致性本质上意味着“表现得好像只有一个数据副本，而且所有的操作都是原子的”，所以最简单的答案就是，真的只用一个数据副本。但是这种方法无法容错：如果持有该副本的节点失效，数据将会丢失，或者至少无法访问，直到节点重新启动。

单主复制（可能线性一致）

在具有单主复制功能的系统中，主库具有用于写入的数据的主副本，而追随者在其他节点上保留数据的备份副本。如果从主库或同步更新的从库读取数据，它们可能（protential）是线性一致性的。然而，并不是每个单主数据库都是实际线性一致性的，无论是通过设计（例如，因为使用快照隔离）还是并发错误。对单领域数据库进行分区（分片），以便每个分区有一个单独的领导者，不会影响线性一致性，因为线性一致性只是对单一对象的保证。

从主库读取依赖一个假设，你确定领导是谁。正如在“真理在多数人手中”中所讨论的那样，一个节点很可能会认为它是领导者，而事实上并非如此——如果具有错觉的领导者继续为请求提供服务，可能违反线性一致性。使用异步复制，故障切换时甚至可能会丢失已提交的写入，这同时违反了持久性和线性一致性。

共识算法（线性一致）

共识算法与单领导者复制类似。然而，共识协议包含防止脑裂和陈旧副本的措施。由于这些细节，共识算法可以安全地实现线性一致性存储。例如，Zookeeper 和 etcd 就是这样工作的。

多主复制（非线性一致）

具有多主程序复制的系统通常不是线性一致的，因为它们同时在多个节点上处理写入，并将其异步复制到其他节点。因此，它们可能会产生冲突的写入，需要解析。这种冲突是因为缺少单一数据副本人为产生的。

无主复制（也许不是线性一致的）

对于无领导者复制的系统，有时候人们会声称通过要求法定人数读写（$w + r> n$）可以获得“强一致性”。这取决于法定人数的具体配置，以及强一致性如何定义（通常不完全正确）。直觉上在 Dynamo 风格的模型中，严格的法定人数读写应该是线性一致性的。但是当我们有可变的网络延迟时，就可能存在竞争条件：

上图中 $x$ 的初始值为 0，写入客户端通过向所有三个副本（$n = 3, w = 3$）发送写入将 $x$ 更新为 1。客户端 A 并发地从两个节点组成的法定人群（$r = 2$）中读取数据，并在其中一个节点上看到新值 1 。客户端 B 也并发地从两个不同的节点组成的法定人数中读取，并从两个节点中取回了旧值 0 。

仲裁条件满足（$w + r> n$），但是这个执行是非线性一致的：B 的请求在 A 的请求完成后开始，但是 B 返回旧值，而 A 返回新值。有趣的是，通过牺牲性能，可以使 Dynamo 风格的法定人数线性化：读取者必须在将结果返回给应用之前，同步执行读修复，并且写入者必须在发送写入之前，读取法定数量节点的最新状态。然而，由于性能损失，Riak 不执行同步读修复。Cassandra 在进行法定人数读取时，确实在等待读修复完成；但是由于使用了最后写入为准的冲突解决方案，当同一个键有多个并发写入时，将不能保证线性一致性。而且，这种方式只能实现线性一致的读写；不能实现线性一致的比较和设置操作，因为它需要一个共识算法。总而言之，最安全的做法是：假设采用 Dynamo 风格无主复制的系统不能提供线性一致性。