零基础入门分布式系统 7.2 Linearizability

原子承诺协议是在面对故障时，通过确保事务的所有参与者要么commit要么abort，来保证跨副本一致性的。然而，当多个节点同时并发读写共享数据时，确保所有节点commit或abort是不够的。我们还必须对并发活动中产生的交互进行推断。

在这一节中，我们将介绍并发系统中一种特殊一致性模型，它被称为linearizability 线性一致性。人们在提到线性化时有时会说strong consistency强一致性，但 "强一致性"的概念是相当模糊的。我们使用linearizability 线性一致性这个术语，它有一个精确定义的含义。

多个节点同时访问多副本数据时，我们该如何界定一致性？

• 线性一致性的非正式定义是：每个操作在开始到结束的某个时间点上原子性生效。
• 所有操作都和在单一数据副本上执行一样（虽然事实上可能有多个副本）。
• 每个操作都会返回"当前最新"的值，满足"强一致性"。
• 不仅仅是在分布式系统中，在共享内存并发中也是如此（多核CPU上的内存默认是不可线性化的）

注：线性一致性 ≠ 可串行性

可线性一致不仅出现在分布式系统中，在单台机器上的共享内存并发背景下也会出现。有趣的是，在具有多个CPU核心的计算机上（比如几乎现在所有的服务器、笔记本电脑和智能手机），内存访问默认情况下是不可线性化的。这是因为每个CPU核都有自己的缓存，单个核的更新不会立即反映在另一个核的缓存中。因此，即使是单台计算机也会有点像一个多副本的系统。

不要把linearizability线性一致性和serializability可串行性混为一谈，尽管这两个词看起来都是"可以被排列成一个连续的执行顺序"的意思。Serializability可串行性表示按照某些顺序执行事务会带来相同的效果，但它并没有定义该顺序应该是什么。Linearizability线性一致性定义了操作必须返回的值，这取决于这些操作的并发性和相对执行顺序。一个系统有可能同时提供线性一致性和可串行性，称为strict serializability严格可串行性或one-copy serializability单拷贝可串行性。

线性一致性的主要目的是保证节点在 "最新"的状态下观察系统；也就是说，它们不会读取stale陈旧（过时）的值。我们之前在读写一致性的背景下看到过这种读取"最新"值的概念。读写一致性只定义了同一节点所做的读写一致性模型，线性一致性将这一概念泛化为不同节点并发进行的操作。

从客户端的角度来看，每个操作都需要一定的时间。我们说，一个操作从应用程序请求的那一刻starts 开始，到操作结果返回给应用程序时finishes 结束。在开始和结束之间，可能会发生各种网络通信步骤；例如，如果使用了quorums，当客户端收到来自quorum副本的响应时，一个操作就可以认为结束。

上图中，我们将客户端视角的一个get/set操作表示为一个矩形，它涵盖了一个操作从开始到结束的时间段。在矩形内，我们写出操作的效果：set(x,v)表示用值v更新x，get(x) → v表示读取x返回v。

线性一致性是独立于系统实现和通信协议的：真正重要的是每个操作开始和结束的时间，以及操作的结果。因此，我们可以撇开所有的复制和消息发送箭头，只从客户端的角度来看待系统的行为。

线性一致性的关键是一个操作是否在另一个操作开始之前完成，而不关心它们发生在哪个节点上。上图中，两个get操作都是在set操作完成后开始的，因此我们希望get操作能返回set写入的v1。

另一张图上，get和set操作在时间上是重叠的：在这种情况下，我们确定操作生效的顺序。get可能会返回set写入的值v1，或者x之前的值v0，两种结果都可能。

注意，"操作A在操作B开始之前完成"与"A在B之前发生"是不同的。happens-before关系是用发送和接收的消息来定义的；有可能有两个操作在时间上不重叠，但是根据 happens-before关系仍然是并发的，因为这些操作之间没有发生通信。另一方面，线性一致性是以实时性real time来定义的：比如说一个可以即时看到所有节点状态的全局观察者（或者，每个节点上有一个完全同步的时钟）来确定每个操作的开始和结束时间。在现实中，这样的全局观察者或完全同步的时钟在具有可变网络延迟的系统中并不存在，但我们还是可以用这样一个假设的观察者来定义线性一致性。这样做的好处是，如果我们证明一个系统是线性一致的，我们就可以确定无论是否发生了通信，系统的一致性都是保证成立的。

线性一致性不仅是指一个get操作与之前的set操作的关系，而且还可以将一个get操作与另一个get操作联系起来。上图显示了一个使用quorum读写的系统的例子，但仍然是不可线性一致化的。在这里，client 1将x设置为v1，由于网络颠簸，副本A更新很快发生，但副本B和C的更新延迟了。client 2从quorum {A, B}中读取，收到响应{v0, v1}，并根据附加的时间戳确定v1是较新的值。在client 2的读取完成后，client 3开始从quorum {B, C}中读取，从两个副本中接收v0，并返回v0（因为它不知道v1）。

因此，client 3比client 2观察到的是一个更旧的值，违背了操作的实时顺序要求：client 3的读到一个不比客户端2的结果旧的值。这种行为违背了线性一致性。

幸运的是，可以使用quorum读写来使get和set操作线性一致化。首先，为了简单起见，假设set操作只由一个指定的节点执行（我们将在后面删除这个假设）。在这个模型中，set操作并没有改变：和以前一样，他们把更新发送到所有的副本，并等待来自quorum副本的确认。

对于get操作，需要另一个步骤。客户端必须首先向副本发送获取请求，并等待来自quorum响应。如果一些响应值包含更新的值（根据时间戳判断），那么客户端必须将最新值写回给所有尚未返回最新值的副本，就像read repair读取修复一样。只有在客户端确定已经有quorum个副本上存有最新的值之后，get操作才会结束：也就是说，要等到quorum副本对读修复的响应ok，或者一开始就回复了最新的值。

这种方法被称为ABD算法，作者Attiya、Bar-Noy和Dolev[Attiya et al. , 1995]。它确保了线性一致化的读写，因为每当get和set操作完成后，我们知道所读或所写的值存在于quorum个副本上，因此任何后续的quorum读取都能保证观察到该值（或更新的值）。

为了将ABD算法推广到多个节点可能执行set操作的环境中，我们需要确保时间戳反映操作的实时顺序。假设操作set(x, v1)的时间戳为t1，操作set(x, v2)的时间戳为t2，并且第一个操作在第二个操作开始之前完成：那么我们必须确保t1 < t2。

让每个set操作首先从每个副本中请求最新的时间戳并等待quorum响应（比如在get操作中）是一个可行方案。set操作的逻辑时间戳是从quorum中收到的最大时间戳加一。对于具有相同时间戳的两个操作，我们根据执行操作的节点的ID来打破平局。由于quorum保证包含至少一个观察到已完成set操作的副本，我们可以得到所需的时间戳排序。这种算法保证了在任何数量的节点上线性一致化的get和set操作[Cachin et al. , 2011, Lynch and Shvartsman, 1997]。

ABD算法确保线性一致化的set操作被称为blind write盲写（unconditional write）：它只是覆盖了一个数据项的值，而不考虑它之前的值。如果多个客户端同时写入同一个项目，它将使用last-writer-wins最后写入者获胜的策略冲突解决。也就是说，其中一个写法将最终成为 "赢家"，其他的值将被默默地丢弃。

在某些应用中，我们希望决策更加谨慎，同时只在一个值没有被另一个节点修改的情况下才覆盖它。这可以通过一个atomic compare-and-swap (CAS)操作来实现。问题是我们如何在一个分布式多副本系统中实现线性一致化的CAS操作？

回顾一下，线性化的目的是使一个系统表现得像只有一个数据副本，并且对它的所有操作都是原子性的，即使系统实际上是多副本的。这使得CAS成为在线性一致化语境下自然需要支持的操作。

ABD算法无法实现CAS，因为不同的副本可能会以不同的顺序观察到操作，从而对某一CAS操作是否成功得出不一致的结论。然而，使用全序广播可以实现线性一致化且多副本的CAS操作。我们简单地广播每一个我们想要执行的操作，并在操作被递交时执行。这种算法可以确保一个操作在每个副本上有相同的作用和结果，就像在状态机副本中一样。