分布式系统中的线性一致性

前言

分布式一致性指的是在同一个系统中，不同客户端操作看到的数据之间的关系。
这里重点关注的是网络键值存储系统中的一致性模型。

首先为什么这有可能出现问题呢？主要是来源于分布式系统中特有的问题，包括：

• 并发读/写
• 副本
• 缓存
• 故障、恢复
• 重传
• …

这些问题就有可能导致系统出现意想不到的场景，比如如下是一个简单的生产者代码：

put("result", 27)
put("done", true)

下面是一个消费者代码：

while get("done") != true
    pause
v = get(result)

在分布式系统中，如果不清楚系统的一致性模型，那么v的值实际上也是难以确认的，因为消费者在读取的时候可能是在一个副本上读取，而生产者在写入的时候可能是在另一个副本上写入，这样就有可能出现v的值不是27的情况。

线性一致性（linearizability）

在线性一致性模型中每个操作似乎都在调用和响应之间的某个时刻以原子方式即时执行。
它是一种强一致性模型，它符合程序员的直觉，但是也会导致排除掉一些可能的优化机会。

如图1所示是一个多客户端并发操作的例子，注意每个方框的最左边是操作开始的时刻，最右边是操作成功获得相应的时刻。

这段历史是线性一致的，因为如图2中的橙色所示，我们可以在每个操作中找到一个可能执行的时间点，组成这样的正确的顺序历史：Put(“x”, “0”), Get(“x”) -> “0”, Put(“x”, “1”), Get(“x”) -> “1”。

而相反的下面图3这个就不是一个线性一致的历史，因为无法找到一个正确的顺序历史。

对于由于网络等因素导致的重传，如下：

C1: |--------Wx1---------| （由于重传）
C2：|-Wx2-| 
C3：|-Rx1-| |-Rx2-| |-Rx1-|

这理论上是可能存在的，但是如果系统表现成这样，那么这个系统就不是线性一致的。所以这也就要求了线性一致性系统中必须要处理重传的重复请求。

线性一致性系统的主要优点在于：

1. 客户端读取到的都是最新的值
2. 所有的客户端看到的都是相同的数据
3. 所有客户端以相同的顺序看到数据的更改

如何实现线性一致性呢？主要是需要依赖于一个不会奔溃的串行服务器，让它来为所有童虎到达的客户端请求选择执行的顺序，并按顺序依次执行，一次一个，在开始下一个之前回复每一个请求。

但是如果想要容错就需要备份了，所有请求都发送到主服务器，选择串行顺序，然后转发到备份，备份以相同的顺序执行，主服务器仅在备份都执行后才回复客户端。

事实上由于请求都发往主服务器，而不能利用备份服务器的能量，所以主服务器可能会成为瓶颈。

线性一致性测试

对系统进行线性一致性的检查是一个NP难的问题。
对其NP难的证明可以从一个子集问题出发进行说明，如下是一个系统的代码：

class Adder:
    def __init__(self):
        self._total = 0

    def add(self, value):
        self._total += value

    def get(self):
        return self._total

考虑如图4所示的历史：

那么这个线性检测的问题就转化为了一个集合S={s₁, s₂, …, s_n}，是否存在一个子集S’，使得S’的和等于目标值t。
当且仅当子集和问题的答案为“是”时，该历史才可线性化。即系统中存在于这个子集中的Add操作在Get操作之前执行，其余的Add操作在Get操作之后执行。

由于存在这种NP难的特性，对于一个分布式系统中的测试往往是通过多样化的执行、故障注入来完成的。即在进行了一系列的操作后，记录历史日志，然后对历史日志进行线性化检测，看是否存在一个合理的操作顺序。

其他一致性模型

除了线性一致性外，还有其他一致性模型，比如：

1. Eventual Consistency（最终一致性）：
   在最终一致性模型中，系统保证如果没有新的更新操作发生，那么最终所有节点都会收敛到相同的值。这意味着系统可能会在一段时间内出现不一致状态，但最终会达到一致状态。最终一致性通常用于分布式系统中为了提高性能而牺牲一致性的情况。
2. Causal Consistency（因果一致性）：
   因果一致性是相对于事件发生的因果关系来保证的一致性模型。如果事件 A 在事件 B 之前发生，那么任何观察到事件 B 的节点都必须也能够观察到事件 A。因此，因果一致性要求对于有因果关系的事件必须保持一致性，而对于无因果关系的事件则允许并发。
3. Fork Consistency（分支一致性）：
   分支一致性是一种介于最终一致性和因果一致性之间的模型。它允许系统中的分支出现，即允许有多个不同的历史状态。在分支一致性中，系统保证对于单个分支内部的一致性，并且最终所有分支都会收敛到一致状态。
4. Serializability（串行化一致性）：
   串行化一致性是指系统保证所有并发执行的操作按照某种顺序执行时，产生的结果与它们依次顺序执行时的结果相同。这意味着系统能够模拟所有操作按照某个全局顺序执行的效果，从而保证了强一致性。
5. Sequential Consistency（顺序一致性）：
   顺序一致性是一种强一致性模型，要求系统中的所有操作必须按照它们发生的顺序进行执行。即使是在分布式系统中，对于每个节点来说，所有操作的执行顺序也必须与它们在全局中发生的顺序相一致。

参考资料

1. 测试分布式系统的线性化
2. 6.5840 2023 Lecture 9: Consistency, Linearizability