零基础入门分布式系统 7.3 Eventual consistency

线性一致性是分布式系统中非常方便的一致性模型，因为它保证系统的行为像只有一个数据副本一样，即使系统实际上是多副本的。这使得应用程序可以忽略与分布式系统合作的一些复杂问题。然而，这种强力的保证也是有代价的，因此，线性一致性并不适合所有的应用。

一部分代价是由于性能：ABD算法和基于全序广播的线性一致化CAS算法都需要在网络上发送大量的消息，并且由于网络延迟而需要大量的等待。另一部分代价是可扩展性：所有更新都需要通过一个领导者来排序，如Raft，领导者可能成为一个瓶颈，限制了每秒钟可以处理的操作数量。

也许线性一致性的最大问题是，每一个操作都需要与quorum个副本进行通信。如果一个节点暂时无法与足够多的副本通信，它就不能执行任何操作。即使该节点可能正在运行，但这样的通信故障使它实际上不可用。

作为一个例子，你可以在大多数手机、平板电脑和电脑上找到的日历应用程序。我们希望这个应用中的预约和安排能在所有设备上同步；换句话说，我们希望它能被复制，使每个设备都是一个副本。此外，我们希望能够查看、修改和添加日历事件，即使设备处于离线状态（比如移动网络覆盖不佳时）。如果日历应用程序的复制协议是线性一致化的，这就不可能实现，因为一个离线的设备不能与quorum个副本进行通信。

相反，日历应用程序允许即使设备离线，用户也能在他们的日历中读取和写入事件。他们可以在稍后的某个有网的时候，在设备之间同步更新。

这种trade-off权衡被称为CAP定理（consistency一致性，availability可用性，partition tolerance 分区容忍度）：如果一个系统中有一个网络分区，我们必须在以下两者中选择一个[Gilbert and Lynch, 2002]:

1. 我们可以选择线性一致性，但在这种情况下，一些副本将无法响应请求，因为它们无法与quorum沟通。不能响应请求使得这些节点实际上不可用。
2. 我们可以允许副本响应请求，即使它们不能与其他副本通信。在这种情况下，它们仍然是可用的，但我们不能保证线性一致性。

有时CAP定理被表述为"三选二"的选择，但这种提法具有误导性。只要不存在网络分区，一个系统就可以既是线性一致的，又是可用的。只有在存在分区的情况下，才会被迫作出选择[Kleppmann, 2015]。

上图说明了，节点C无法与节点A和节点B通信。 在分区的A和B那边，线性一致的操作可以正常进行，因为A和B构成了一个quorum。然而，如果C想读取x的值，它必须等待（可能是无限期的），直到网络分区被修复，或者它必须返回其本地的x值，这并不反映分区另一侧的A之前写的值。

日历应用程序选择了选项2：它放弃了线性一致，而允许用户在设备离线时继续执行操作。许多其他系统出于各种原因也同样做出了这种选择。

允许每个副本只根据其本地状态来处理读和写，而不等待与其他副本的通信，这种方法被称为optimistic replication 乐观复制。人们为乐观复制系统提出了各种一致性模型，其中最著名的是eventual consistency 最终一致性。

最终一致性被定义为：如果一个对象没有新的更新，最终所有的读取都会返回最后的更新值[Vogels, 2009]。这是一个非常弱的定义：如果对一个对象的更新永远不会停止，那么声明的前提就永远不会成真，这要怎么办？上图给出了一个稍强的一致性模型称为strong eventual consistency强最终一致性，通常更合适 [Shapiro et al., 2011]。它是基于这样的想法：当两个复制体进行通信时，它们会向相同的状态converge收敛。

在最终一致性和强最终一致性中，都有可能出现不同的节点同时更新同一个对象的情况，从而导致冲突。人们已经开发了各种算法来自动解决这些冲突[Shapiro et al., 2011]。

上图总结了我们所见过的模型的一些关键属性，按照它们对系统模型进行最小强度假设的递减顺序排列。

原子提交具有最强力的假设，因为它必须等待与参与交易的所有节点（可能是系统中的所有节点）进行通信。共识、全序广播和线性一致算法的假设稍弱，因为它们只需要等待与quorum通信，所以它们可以承受一些不可用的节点。FLP不可能原理向我们表明，共识和全序广播需要部分同步。可以证明，一个线性一致的CAS操作等同于共识[Herlihy, 1991]，因此也需要部分同步。另一方面，线性一致的get/set的ABD算法是异步的，因为它不依赖任何时钟或超时。最后，最终一致性和强最终一致性做出了最弱的假设：操作可以在不等待与其他节点的任何通信的情况下被处理，并且没有任何时间假设。同样地，在因果广播和较弱形式的广播中（FIFO，reliable，等等），一个节点广播一个消息可以立即传递给自己，而不需要等待与其他节点的通信；这相当于一个副本立即处理自己的操作而不需要等待与其他副本的通信。