一致性模型

复制带来了高可用性和高性能，但也带来了多个副本如何保持数据一致性的问题，尤其是写操作在何时以何种方式更新到所有副本，决定了分布式系统付出怎样的性能代价。

一致性模型是指，在并发编程中，系统和开发者之间的一种约定，如果开发者遵循某些规则，那么开发者执行读操作或写操作的结果是可预测的。

• 可预测保证了程序的正确性。如果一个系统执行读写操作却无法返回可预测的结果，这样的系统是很难用的
• 系统可以时分布式系统，也可以是单台计算机的内存或寄存器。多线程对内存变量进行并发读写，也会存在可预测的问题
• 一致性模型本质上定义了写操作的顺序和可见性，即并发写操作执行的顺序是怎样的，写操作的结果何时能够被别的进程看见。

线性一致性

线性一致性 Linearizable Consistency 是最强的一致性模型，也叫 强一致性 Strong Consistency，严格一致性Strict Consistency。

线性一致性其实是并发编程领域的概念，不止用于分布式系统。

非严格定义

分布式系统中的所有操作看起来都是原子的，而整个分布式系统看起来只有一个节点。

线性一致性必须强调原子性。在单台计算机上为了实现一致性，硬件会提供一些底层原语（内存屏障等），操作系统也会根据底层原语封装一些常用的同步原语，最后大部分编程语言都实现了同步原语和原子变量，方便开发者实现线性一致性。

严格定义

给定一个执行历史，执行历史根据并发操作可以扩展为多个顺序历史，只要从中找到一个合法的顺序历史，那么该执行历史就是线性一致性的。

并发操作之间有三种关系：

• 一个操作明显在另一个操作前发送，这两个操作是顺序关系
• 两个操作之间有重叠，这两个操作就是并发关系
• 一个操作包含另一个操作，也是并发关系

在将执行历史转变为顺序历史的过程中

• 如果两个操作是顺序关系，那么它们的先后关系必须保持相同
• 如果两个操作是并发关系，它们可以按任意顺序排列

线性一致性主要有两个约束条件：

• 顺序记录中，任何一次读必须读到最近一次写入的数据
• 顺序记录要跟全局时钟下的顺序一致

线性一致性代价

最困难的是需要一个全局时钟，这样才能知道每个时间发生的时间和全局顺序，但分布式系统中准确的全局时钟是难以实现的。

如何实现线性一致

在单机多线程并发编程中，通常使用编程语言提供的互斥锁保护临界区，实现线性一致性。

• 使用锁实现对临界区的串行访问
• 底层的内存屏障指令保证多核的可见性

分布式系统中，可以使用共识算法实现线性一致性。

• 并不是说实现了共识算法就是实现了线性一致性
• Raft是一种分布式系统共识算法，本身不提供线性一致性，但是可以在Raft基础上，限制对读写操作的实现，来使系统达到线性一致性。

顺序一致性

顺序一致性Sequential Consistency是一种比线性一致性弱一些的一致性模型，由Lamport提出。顺序一致性的提出时间其实要早于线性一致性。

顺序一致性同样允许对并发操作历史进行重新排列，但它的约束比线性一致性弱。

• 顺序一致性只要求同一个客户端的操作在排序前后保持先后顺序不变
• 不同客户端之间的先后顺序是可以任意改变的。

顺序一致性没有全局时间的限制，不要求不同客户端之间的操作顺序一致，只关注局部的顺序。

因果一致性

因果一致性Causal Consistency是一种比顺序一致性要求更弱的一致性模型，同样不依赖全局顺序。因果一致性要求

• 必须以相同的顺序看到因果相关的操作
• 对于没有因果关系的并发操作，可以被不同进程以不同的顺序观察到。

因果一致性的关键是体现了Happens-Before关系，通常使用逻辑时钟来维持因果顺序。

最终一致性

最弱的一致性模型之一，在最终状态下，只要不再执行写操作，读操作将返回相同的、最新的结果。

• 许多追求高性能的分布式存储系统都是使用最终一致性模型

以客户端为中心的一致性模型

以数据为中心的一致性模型常考虑多个客户端时的系统状态，而以客户端为中心的一致性模型聚焦于单个客户端观察到的状态。

• 单调读
  • 如果客户端读到关键字x的值为v，那么该客户端对于x任何后续的读操作，都只能返回v或比v更新的值，即保证客户端不会读到旧值。
• 单调写
  • 同一个客户端的写操作，在所有副本上都是以同样的顺序执行，即保证客户端的写操作是串行的
• 读你所写/读己之写
  • 客户端完成写操作后，再在同一个副本或其他副本上的读操作，必须能读到写入的值，注意必须是同一个客户端。
• PRAM
  • 由单调读、单调写和读你所写三个一致性模型组成
  • 同一个客户端的多个写操作，将被所有的副本按照同样的执行顺序被观察到
  • 不同客户端发出的写操作，可以以不同的执行顺序被观察到
• 读后写
  • 同一个客户端对于数据项x，如果先读到了写操作w1的结果v，那么后面的写操作w2保证基于v或者更新的值
  • 看起来和因果一致性相似，只不过以单客户端为视角，也叫会话因果Session Causality一致性

隔离级别

隔离级别Isolation Level定义了并行系统中事务的结果何时、以何种方式对其它并发事务可见。隔离性Isolation属于事务ACID四个属性之一。

几种常见的隔离级别：

• 串行化 Serializability
• 可重复读 Repeatable Read
• 快照隔离 Snapshot Isolation
• 读已提交 Read Committed
• 读未提交 Read Uncommitted

隔离级别定义了，在当前级别下，出现哪些问题是不被允许的。并发事务可能发生的问题：

• 脏写
  • 解决：写操作对记录加锁
• 脏读
  • 解决：ReadView
• 不可重复读
  • 解决：ReadView实现快照隔离
• 幻读
  • 解决：MySQL中使用MVCC和Gap锁解决
• 更新丢失
  • 两个事务读取同一个值，然后都试图将其更新为新的不同值
  • 解决
    • 原子操作
    • 显示上锁select .. for update
    • 自动检测更新丢失冲突
• 读偏斜 Read Skew
  • 读到了数据一致性被破坏的数据
  • 假如数据约束为X+Y=100，并发事务B一开始读到X=50，同时事务A将X和Y分别修改为30和70，接着事务B读取Y值为70，B发现不满足一致性约束
  • 解决：ReadView实现快照隔离
• 写偏斜 Write Skew
  • 两个并发事务都读到了相同的数据集，随后各自修改了不相干的数据，导致数据一致性约束被破坏
  • 解决：加锁

分类

• 单个对象并发更新导致的问题：更新丢失、脏写
• 多个对象并发更新导致的问题：写偏斜，幻读

关于快照隔离级别SI：

• 标准的快照隔离级别引入时间戳参数，可以解决幻读，参考 快照隔离级别原理
• MySQL MVCC也是快照隔离的一种实现，但没有使用时间戳参数，因此存在当前读时的幻读问题（如UPDATE其它并发事务插入的新记录）
• SI级别上可以高效的实现更新丢失的检测，因此SI级别没有更新丢失问题
• 由于没有加锁，SI级别存在写偏斜问题

关于可重复读RR：

• 概念上的可重复读采用对记录加锁实现，因此没有更新丢失和写偏斜问题，但有幻读的问题
• MySQL的RR级别快照读是MVCC；当前读情况下才加锁，并且使用Gap锁解决幻读问题