分布式系统的一致性模型

在一个分布式系统里面，按照数据的一致性从强到弱排序，我们有以下的一致性模型：

严格一致（Strict Consistency）
线性一致（Linearizability)
序列一致（Sequential Consistency）
因果一致（Causal Consistency）
FIFO一致（FIFO Consistency）

严格一致（Strict Consistency）

严格一致性（Strict Consistency）要求对于一个分布式系统的读写交错序列（按照实时时钟排序），如果在某一时刻t对变量x做了一个写操作write(x:=10),那么对于在这个t之后的t’时刻 (t’>t) 的对于此变量x的读操作（并且在下一次的对于x的写操作之前），都会有结果read(x)=10。严格一致性保证了一个集群系统对任何客户端来说看起来都像是一个单机系统。严格一致性在单机单线程程序上是可以满足的，但是在一个分布式系统上却非常难以实现，因为它要求对于所有的节点，一旦x发生了更改，那么此更改可以即时同步到所有的节点上面，但是我们知道，节点之间通过网络进行通信，而且网络通信是有延时的，要做到所有节点即时同步是做不到的。

线性一致（Linearizability)

线性一致性（Linearizability）要求对于一个分布式系统的读写交错的序列（按照实时时钟排序），如果对于任何一个变量x的读操作read(x)，读到的值都是在此读操作之前最后一次写操作write(x)更新的值。
严格一致性和线性一致性的区别是严格一致性要求对于一个变量x的写操作在所有的节点副本上是实时更新的，而线性一致性并不要求实时更新这一点。
要实现线性一致性，所有的读写操作都要使用一个全序多播（Total ordering multicast）来完成。

对于以下图1：

按照线性一致性，则有：

Read_A1(x)=10
Read_A2(x)=20
Read_A3(x)=20
Read_B(x)=20
Read_C1(x)=20
Read_C2(x)=20

序列一致（Sequential Consistency）

序列一致性（Sequential Consistency）要求对于一个分布式系统的读写交错序列（按照实时时钟排序），必须满足：

对于同一个节点发起的读写序列，对于任何一个变量x的读操作read(x)，读到的值都是在此读操作之前最后一次此进程发起的写操作write(x)更新的值；
对于整个读写交错序列，所有节点看到的写操作序列必须保证一致。

要实现序列一致性：

对于写操作，使用一个全序多播（Total ordering multicast);
对于读操作，立即返回本节点上对应变量的值。

对于图1，除了线性一致性中的返回值情况，以下返回值也满足序列一致：

Read_A1(x)=10
Read_A2(x)=10
Read_A3(x)=20
Read_B(x)=20
Read_C1(x)=10
Read_C2(x)=10

但是以下的Read_C1(x)和Read_C2(x)却不满住序列一致性:

Read_{C1_(x)=20}
Read_{C2_(x)=10}

因果一致（Causal Consistency）

因果一致性（Causal Consitency）要求对于分布式系统里的每一个节点，对于所有的有因果关系的写操作，进程都以相同的顺序执行这些写操作，而读操作读出来的值必须反应出这个更新顺序，所以对于读操作：

对于同一个节点发起的读写序列，对于任何一个变量x的读操作read(x)，读到的值都是在此读操作之前最后一次此进程发起的写操作write(x)更新的值；
对于没有因果关系的写操作，其他节点的读操作可以按任意顺序返回值。

要实现因果一致性：

对于写操作，使用基于矢量时钟的多播（Vector clock multicast）来完成所有节点的更新操作；
对于读操作，立即返回本节点上对应变量的值。

对于图1，如果Write_A(x=10)和Write_B(x=20)之间有因果关系，以下返回值满足因果一致：

Read_A1(x)=10
Read_A2(x)=10
Read_A3(x)=20
Read_B(x)=20
Read_C1(x)=10
Read_C2(x)=20

但是以下的Read_C1(x)和Read_C2(x)却不满住因果一致性:

Read_C1(x)=20
Read_C2(x)=10

如果WriteA(x=10)和WriteB(x=20)之间没有因果关系，以下返回值满足也因果一致：

Read_A1(x)=10
Read_A2(x)=10
Read_A3(x)=20
Read_B(x)=20
Read_C1(x)=20
Read_C2(x)=10

FIFO一致（FIFO Consistency）

FIFO一致性（FIFO Consistency）是最弱的一致性，它仅仅要求：对于同一个进程执行的读写序列，对于任何一个变量x的读操作read(x)，读到的值都是在此读操作之前最后一次此进程发出的写操作write(x)更新的值。而对于不同节点发出的写序列，其他节点的读操作可以按任意顺序返回值。