Consistency Models

因为对共享的内存寄存器的操作是允许出现重叠的，因此我们需要定义明确的语义来说明，在一个极小的间隔中存在多个客户端对不同的数据副本进行了读取跟修改的操作时会发生什么。这个问题并没有一个唯一的正确答案，因为他们的语义在不同的应用中是不一样的，而这些就是我们在一致性模型的上下文中需要学习的。

一致性模型提供了不同的语义跟保证，你可以将这个模型想象成所有参与者之间的约定：每个副本都需要满足语义所提的要求以及用户在进行读取跟写入操作时的期望。

一致性模型描述了用户在存在多个数据副本跟存在并发访问时，对返回结果的期望。在本节中讨论 single-operation 单个操作的一致性模型。

每个模型描述的是我们所期望的系统的行为跟系统的行为或者正常情况的差距。他能够帮助我们区分出 相互交错的操作的 All possible histories 所有可能的历史记录跟允许在模型 X 中产生的历史记录，这让我们能够极大的简化了对系统状态变化的可见性的解释。

我们可以从 State 状态的视角来思考一致性，描述状态的哪些不变量是可以接受的，以及建立数据在不同副本上的多个复制间能够允许的关系。另一个选择是我们可以考虑操作的一致性，这让我们可以对系统有一个跟数据存储的无关的视角，描述了操作跟他们执行的顺序的限制条件。

在不使用全局时钟的情况下，很难去给分布式的操作定义一个清晰可确认的顺序。就像一个特殊的关于数据的理论：所有的参与者都会有他自己关于状态跟时间的视角。

理论上，我们在需要对系统状态进行变更时获取一个系统级别的锁，但这种做法比较不切实际，事实上，我们会使用一系列的规则、定义跟限制来限制可能产生的历史记录跟结果的数量。

一致性模型在我们之前讨论的 Infamous CAP 上添加了另外一种维度，现在我们需要去决定的不只是一致性跟可用性了，还需要考虑一致性所带来的同步的成本。同步的成本可能会包括了延迟、因为执行额外操作的 CPU 成本、用来持久化恢复信息的磁盘 I/O 成本、加大等待的时间、网络 I/O 跟其他原本不需要同步时可以避免的成本。

首先我们会关注操作结果的可见性及传播，回到并发读写的示例中，我们能够通过定位互相依赖的写操作并安排他们的顺序或定义新的值在哪个时间点进行传播，来限制可能产生的历史记录数量。

我们会从对数据库状态不断产生读取跟写入操作的客户端的角度来讨论一致性模型。因为会在复制数据的上下文中来讨论一致性，我们会假设数据库也可以存在多个副本。

Strict Consistency

严格的一致性相当于完全的副本机制：任何处理器的所有写入操作都可以立即在集合中的所有副本中被任意的处理器读取到。这需要一个全局时钟的概念，并且如果在 t~1~ 时刻存在一个 write(x, 1) ，所有发生在其之后的 t~x~ > t~1~ 的读取操作都要返回新的值 1.

不幸的是，这只是一个无法实现的理论上的模型，因为用来构建分布式系统的物理上法则限制了这种方式的效率。

Linearizability

Linearizability 可线性化是一个具有最强的 Sigle-Object 单对象、Single-Operation 单操作的一致性模型。在这个模型中，在某个具体的时间点之间，写操作会立即对所有的读取者可见，并且不会有用户能够察觉这个写操作所产生的状态的转变、部分的结果 (比如未完成的、传输中的) 、未完成的结果 (比如在完成之前被中断)。

并发的操作被表示为能够其中一个保持可见性属性可能的顺序历史记录。可线性化还存在一些不确定性，就是时间可能会存在不止一种的排序方式。

如果两个操作重叠了，他们可能会以任意顺序生效。所有发生在写入完成之后的读操作都能够观察到这次操作的结果。在其中一个读取操作返回一个指定的值的同时，所有在其之后的读取操作至少要返回跟他一样新的结果。

对于全局的历史记录来说，他们在并发情况下发生的顺序是具有一定的灵活性的，但这些历史记录不能被进行重排。操作的结果在操作开始前不能产生任何副作用，除非这个操作能够先预测出下一个操作是什么。与此同时，结果必须在操作完成前确认，否则的话我们就无法去确定这个可线性化的时间点了。

可线性化同时遵守处理器本地的处理顺序以及处理器之间并发之执行的操作顺序，并对这些事件做出了 Total Order 全序的定义。

这些顺序应该是保持一致的，这意味着所有对同一个共享值的读取操作都应该返回这个共享值在读取之前的最新值，或者是跟这个读取操作重叠的写操作的值。线性化的对一个共享变量的写操作同样暗示了他是具有排他性的：两个并发的写操作只有一个能够先执行。

尽管操作是可以并发跟有重叠的，但他们的执行结果的可见性应该是线性呈现的。没有操作的结果能够立即呈现，但他们仍然是具有原子性的。

我们来考虑下面的执行历史：

Process 1:    Process 2:    Process 3:
write(x, 1)   write(x, 2)   read(x)
													  read(x)
													  read(x)

在 Figure 11-2 中，我们有三个处理器，其中两个正在对寄存器 x 执行写操作，这个寄存器的值最初是被初始化为 ∅。读取操作可能会以下面的三种方式之一观察到该寄存器的值：

• a) 第一个读取操作会返回 1, 2 或是 ∅ (即初始化的值)，因为两个写入操作这时还没执行。第一个读取会排在两个写之前，两个写之间或是两个写入之后。
• b) 第二个读取操作可能会返回 1 或者 2, 因为第一个写入在这时已经完成了，但是第二个写入还未返回
• c) 第三个读取只能够返回 2，因为第二个写入是排在了第一个之后

Linearization Point

可线性化的其中一个最重要的特性就是他的可见性：如果一个操作完成了，所有人都必须能够观察到，系统不会产生 时间回溯 的错觉导致某些节点恢复或者观察不到这个值。换个说法就是，线性化禁止读取到脏数据并要求读取是单调的。

对这个一致性模型最好的解释是原子性操作 (即无法被中断、不可被分割) 。操作不需要是瞬时的 (也因为并不存在这样的东西)，但他们的效果需要在某个时间点中呈现，以此表现出一种瞬时完成的错觉。这个时间点我们将其称为 Linearization Point 线性化点。

传递这个写操作的线性化点 (换句话说就是这个值对于其他的处理器可见的时间点)