数据一致性
目录
1 问题定义
- 线性一致性和顺序一致性是什么意思，有什么区别？
- 脏读、脏写、幻读、重复读、读已提交，都是什么含义？
- 事务有哪些隔离级别？
2 顺序一致性与线性一致性
2.1 顺序一致性(Sequential Consistency)
- 顺序一致性不要求线程间保序；
- 线程间无序()；
- 没有可组合性(Not Compositional)；
// Books: The Art of Multiprocessor Programming // 3.4 Sequential consistency // Not acceptable for violation program order r.write(7) r.write(-3) r.read(7) |-----------| |-----------| |-----------| // Two possible sequential order that can justify this execution. Thread1 q.enq(x) q.deq(y) |-----------| |-----------| Thread2 q.enq(y) q.deq(x) |-----------| |-----------| // The follow p and q are each sequential consistency, // But p and q as a whole is not sequential consistency. Thread1 p.enq(x) q.enq(x) p.deq(y) |-----------| |-----------| |-----------| Thread2 q.enq(y) p.enq(y) q.deq(x) |-----------| |-----------| |-----------|
2.2 线性一致性(Linearizability)
- 全局保序（多线程保序）；
- 满足组合性(Compositional)；
- 线性一致性一定满足顺序一致性，反之则不然；
摘自The Art of Multiprocessor Programming的描述：
The usual way to show that a concurrent object implementation is linearizable is to identify for each method a linearization point where the method takes effect. For lock-based implementations, each method’s critical section can serve as its linearization point. For implementations that do not use locking, the linearization point is typically a single step where the effects of the method call become visible to other method calls. For example, let us recall the single-enqueuer/single-dequeuer queue of Fig. 3.3. This implementation has no critical sections, and yet we can identify its linearization points. Here, the linearization points depend on the execution. If it returns an item, the deq() method has a linearization point when the head field is updated (Line 18). If the queue is empty, the deq() method has a lineariza- tion point when it throws Empty Exception (Line 16). The enq() method is similar.
- 理解
- 并发对象实现线性化的常规方式是为每种方法，确定方法生效的线性化点；
- 基于锁的实现，每个方法的临界区都可以做为线性化点；
- 对于无锁实现，线性化点通常是使得该方法效果对外可见的单步操作；
- 考虑3.3(本文前图)队列出入操作，线性化点依赖执行。如果返回一个元素，deq()方法具备一个线性化点，这个点更新了head成员；如果队列是空的，deq()方法的线性化点是抛出异常的点；// 因此，同一方法的多次执行，线性化点可以是程序的不同位置；
- 因此必须具备边界效应（Side effect），即状态的改变；
- 可以基于非阻塞方法实现（Non-blocking，即Atomic操作）；
3 事务可见性
3.1 基本概念
- 事务将多个读写操作捆绑形成一个逻辑操作单元。即事务中的所有读写是一个执行的整体，整个事务要么成功（提交），要么失败（中止或回滚）。如果失败，应该可以安全重试。
- ACID
- Atomicity(原子性): 出错时终止事务，并将部分完成的写入全部丢弃；可终止性；
- Consistency(一致性): 应用借助原子性和隔离性，以及应用本身的逻辑正确性，才可达成一致性；
- 隔离性(Isolation): 并发执行的多个事务相互隔离，互不干扰。最好的隔离级别是可串行化(Serializability)，意味着系统要确保事务提交时，其结果与串行执行一致。为了性能优化，很多数据库放松了这个约束。例如，Oracle 11g实现快照隔离；
- 持久性(Durability): 写入到持久存储。
3.2 弱隔离级别(Weak Isolation Levels)
- 读已提交：最弱的隔离级别，保证：
- 只能看到已提交的数据，不会有脏读；
- 写入时，只覆盖已提交的数据，不会有脏写；
- Oracle 11g, PostgreSQL, SQL Server 2012, MemSQL的默认配置;
- 什么是脏读：某个事务已部分写入，但没有提交或终止，如果部分写入的数据被其他事务看到，即为脏读；
- 什么是脏写：某个事务已部分写入，但没有提交或终止，如果部分写入的数据被其他事务的写入所覆盖，即为脏写；
- 行锁防止脏写，维护旧值与当前数值防止脏读；
- 快照级别隔离与可重复读(Snapshot Isolation and Repeated Read)
- 不可重复读/读倾斜：对多个对象操作，看到了部分对象已更新，部分对象未更新；
- 行锁隔离写，MVCC提供读；
- MVCC数据，通过事务ID，决定哪些可见，哪些不可见；
- 以下两个条件成立时，该数据对象对事务可见：
- 事务开始时，创建该数据对象的事务已经完成提交；
- 事务开始时，数据对象未被删除，或者删除该数据对象的事务还未提交；
- 串行化(Serializability)
- 写倾斜和幻读问题：并发的事务，违背了逻辑约束，或者触发了实体化冲突；
- 事务可能会并行执行，但保证并行执行的结果，与串行执行的结果一致；
- VoltDB/H-Store，Redis，Datamic采用串行方式执行事务；
- 2阶段加锁：2PL(2 Phase Locking)
- 事务A读取了某个对象，事务B要写该对象，则必须等到事务A结束（提交或终止）；
- 事务A修改了某个对象，事务B要读该对象，则必须等到事务A结束（提交或终止）；
- MYSQL，SQL Server 串行化隔离实现使用2PL实现；基本思路如下：
- 事务要读取对象，先加读锁（共享锁）；
- 事务要修改对象，加写锁（互斥）；
- 事务先读取对象，后修改对象，则要升级读锁为写锁；
- 事务拿到锁后，持续到事务结束才释放锁；
- 2PL意思是，第一阶段事务执行前加锁，第二阶段事务结束时释放所有锁；
- 性能优化：Predicate Locks, Index-range Locks, 悲观锁与乐观锁;
4 一致性与共识
5 References
- The art of Multiprocessor Programming: https://github.com/yygcode/books/blob/master/cs/cs-computer-the-art-of-multiprocessor-programming.pdf
- How to Make a Correct Multiprocess Program https://github.com/yygcode/papers/blob/master/cs/cs-how-to-make-a-correct-multiprocess-program.pdf
- A Critique of ANSI SQL Isolation Levels: https://github.com/yygcode/papers/blob/master/db/db-a-critique-of-ANSI-SQL-isolation-levels.pdf