> For the complete documentation index, see [llms.txt](https://yangsx95.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yangsx95.gitbook.io/notes/distributed/yi-zhi-xing/yi-zhi-xing-mo-xing.md).

# 一致性模型

从一般意义上，分布式一致性是指分布式系统中的多个服务节点，给定一系列操作，在约定协议的保障下，使他们对处理结果达成某种程度的一致。理想情况下，各服务节点遵循相同的协议，构成相同的处理状态机，给定相同的初始状态和输入序列，可以保障每个节点在处理过程中每个环节的结果都是相同的。

从分布式集群对外表现出的**宏观特性**来看，或者从Client的角度来看，可以把分布式系统的一致性分为**强一致性和弱一致性**(文献1)。

在强一致集群中，对任何一个节点发起请求都会得到相同的回复，但将产生相对高的延迟。而在弱一致集群中，对不同节点发起请求，可能会得到不同的回复(可能是不相同的或者未定义的值)。在排除并发写的情况下，如果存在一个时刻（不是立刻）可以让系统达到强一致的状态，这种弱一致性也叫做**最终一致性,** 关于最终一致性以及一致性、可用性、性能权衡取舍的原则，在[http://Amazon.com](https://link.zhihu.com/?target=http%3A//Amazon.com)首席技术官Werner的经典博文中有详细讨论(文献2)。

而从分布式系统中事件顺序(时钟顺序或者逻辑顺序)的“**微观角度**”来看，或者从Server端的内视角度看，分布式一致性可以有更加详细的分类。下面详细介绍如下3种一致性，他们的一致性约束由强到弱。

* ***线性一致性 Linearizability:*** read must see the latest write, where latest is defined in relation to the global wall clock. 
* ***顺序一致性 Sequential Consistency***: the global order of read and write is consistent with the program order at each node.
* ***因果一致性 Causal Consistency***: only causality (or partial order) among events is preserved.

## 服务端角度

### 顺序一致性 Sequential Consistency

顺序一致性由Leslie Lamport在1979年提出(文献3)，以多处理器对本机寄存器的操作为例进行描述，可以扩展到分布式系统。顺序一致性是一种较强的约束，需要满足两点要求：

1. 所有进程看到的全局执行顺序(total order)是一致的。
2. total order中，每个进程的执行顺序与实际发生的顺序(local order)一致。

在下例中，有两个分布式节点，分别在各自的存储介质中设置x=1和y=4。\
如果集群中的所有节点看到的全局顺序都是total order1或者都是total order2，那么集群满足顺序一致性。如果集群中节点看到的全局顺序是不一致的（比如p1节点看到的是order1，而p2节点看到的是order2）或者所有节点看到的全局顺序都是total order3(全局顺序中p2的执行顺序与实际不一致)，那么集群不满足顺序一致性。

![](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-9a584304f7319b70ada9c6bb24218975b4cd3275%2FPasted%20image%2020240414111721.png?alt=media)

注意顺序一致性实际上是限制了各线程(或者分布式节点)内指令的偏序关系，但不会按照实际物理时间进行全局排序。

**顺序一致性典型的使用场景是读写分离、主从同步**。集群中事件发生的顺序由主节点唯一确定，从节点按照事件顺序各自在本地进行回放，从而达成一致性。假设上例集群在时刻T，p1、p2节点都完成了y=4的set操作，那么在时刻T之后向该集群发起y值的查询，将得到一个强一致的结果；否则是弱一致的。我们可以看到顺序一致性是集群强一致的一个必要条件，而非充要条件，要实现强一致还需要leader机制、租约机制、ACK机制等等的工程设计。

### 线性一致性 Linearizability

线性一致性，也叫原子一致性或严格一致性，由Maurice P. Herlihy和Jeannette M. Wing在1990年共同提出(文献4)，是对顺序一致性的加强。需要满足两点要求：

1. 所有线程看到的全局执行顺序是一致的。除了顺序一致性中要求的线程内部操作时序不变之外，线程间的操作执行先后顺序也需要保持不变。
2. 全局执行顺序中，对每一个对象的操作顺序是合法的。

实际上所有操作都包括一个调用(invocation)事件和一个返回(response)事件，如果操作A的返回事件先于操作B的调用事件发生，就认为操作A和操作B是线性的，并且A在B之前。如果A不在B之前并且B也不在A之前，那么A和B就是并行的。下图中红色连线表示的线性关系需要在全局执行顺序中保留。而**对于并行操作(比如op2和op6)在全局执行顺序的先后是不确定的,但要受到合法性的约束**。下图中order1,2,3都是可选的全局执行顺序。

![](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-b666486a1a244129f8f96effbb80a689cf15d408%2FPasted%20image%2020240414111957.png?alt=media)

关于合法性，不同类型的对象有不同的顺序性说明(Sequential specification), 顺序性说明描述了一个对象所有可能的顺序行为，即合法顺序。比如对于一个栈类型的对象，出栈操作先于入栈操作就是一个非法顺序。而对于一个value读写系统而言，操作顺序的合法性要求是：

1. 在并发场景下，一个线程对共享变量的操作能立即被其他线程感知。
2. 任何一个读操作返回新值后，所有后续读操作也必须返回新值。

如例2中，由于读操作op2,4,5和写操作op6是并发操作，所以读到的值是不确定的，但如果op4读到的值是1，op2读到的是0，op5读到又是1，就不满足合法性要求，造成这种情况的原因是操作是持续性(非原子性)的，并且操作的并发的。不难发现，我们只要保证操作是原子和瞬时的，就可以保证操作顺序的合法性。所以在**value读写系统中，线性一致性可以被特化为**：

1. 全局有序；
2. 任何操作都需要在调用和返回之间原子和瞬间执行。

线性一致性是分布式系统中最严格的一致性定义。全局有序的约束实际上是隐含了要求系统中有一个全局时钟。全局时钟要么用高精度的硬件计时器实现，要么使用复杂度比较高的算法来实现全局逻辑时钟，整体上实现成本很高。但是同时线性一致性系统具备locality和nonblocking的特点，可以大大简化模块设计和开发的工作。

### 因果一致性 Causal Consistency

因果一致遵守以下条件：因果相关的写操作应对所有线程可见，且顺序一致。而因果条件下的并发写操作在不同线程看来顺序可能是不同的。一般用happen-before关系来指代因果关系，happen-before关系是Leslie Lamport在1978提出的（文献5）。所谓**happen-before关系**是指：

1. 如果a和b是同一个线程中的事件，并且a在b之前发生，则a-> b
2. a事件是一个线程发送请求，b事件是另一个线程接收请求，则a-> b
3. 如果a->b并且b-> c，则a->c，即偏序的传递性

happen-before关系可以构成一个执行路径，如下图中的c(1,p1)->c(2,p2)->c(3,p2)。如果无法找到一个路径连接两个点，则这个两个点是并发关系，比如例3中的c(2,p1)和c(3,p2)以及c(4,p2)和c(4,p3)。

happen-before关系描述的是一个信息传递关系，和物理时钟没有直接关系。比如c(2,p1)在时间上早于c(3,p2)发生，但是在happen-before意义下他们是并行的。和顺序一致性一样，因果一致性也是一种偏序关系，但是在**因果一致性系统不存在全局执行顺序**，各线程中观察到的存在happen-before关系的事件先后顺序是一致的，但不保证并行事件的顺序。比如例3中所有线程都能够观察到op1发生在op4和op5之前，但是不同线程观察到的op4和op5的顺序可能不一致。

![](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-8f6c9344082efde18b7acc4483523acc2a1de482%2FPasted%20image%2020240414112944.png?alt=media)

具体可以采用递增ID来表示因果顺序：

1. 每个线程内的事件ID是递增的，新发生的事件ID大于当前本线程内所有ID。如例3中p1线程内的ID号是1，2，5，6。
2. 接收到其他线程的消息后，在本线程内生成一个消息接收事件，接收事件的ID要大于发送事件的ID。比如例3中线程p2接收到了来自p1的消息op1。p2中接收消息的事件ID为2，大于p1中发送消息的事件ID 1。
3. 当接收到来自不同线程的但是事件ID相同的消息后，需要在本地对消息进行排序。

**因果一致性系统常用于问答或者评论系统中，要求问先于答，原文先于评论**。我们把例3中的p1,2,3设想为三个IDC，独立的为本地域的用户提供服务。p1 IDC的用户提出了一个问题op1，p2和p3 IDC的用户独立进行了回答，所有IDC的用户一定可以先看到问题，但是看到回答的顺序是不确定的，而从业务的角度回答的顺序也并不重要。

## 客户端角度

除了面向服务端的一致性模型以外，还有 **面向客户端的一致性模型**：它们是从单个客户端的视角出发，要求系统对同一个客户端先后发起的读写操作提供特定的一致性保证。

面向客户端的一致性模型包括 4 种：

* 单调读一致（Monotonic Reads）：客户端后续发起的 **读操作** 能够感知到先前 **读取**到的或更新的版本
* 写读一致（Read Your Writes）：客户端后续发起的 **读操作** 能够感知到先前 **写入** 的或更新的版本
* 读写一致（Writes Follow Reads）：客户端后续发起的 **写操作** 能够感知到先前 **读取**到或更新的版本
* 单调写一致（Monotonic Writes）：客户端后续发起的 **写操作** 能够感知到先前 **写入**的或更新的版本

## 参考和摘录

* [分布式一致性概述](https://zhuanlan.zhihu.com/p/653908186)
* [分布式一致性模型介绍](https://mr-dai.github.io/consistency-models/)