线性一致性

所谓的线性一致性(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风格无主复制的系统不能提供线性一致性。