数据库隔离级别
本节主要介绍了ANSI SQL隔离级别的定义、不足以及其他隔离级别如Cursor Stability、SI等。
隔离级别的定义
Serializability相关概念
transaction事务：聚合一系列操作（Action）的集合，把数据库从一个一致性状态转换到另外一个一致性状态。
history运行历史：把一系列交叉执行的事务集重整为这些事务所有操作集的线性顺序排列，比如对特定Data Item（数据项）的读写操作（如插入、删除、更新等）。
Data Item数据项: 这是一个广义的概念，可能是一个元组、一个页面甚至是整个关系。
conflict冲突：history中如果存在不同的事务在同一个Data Item上执行操作，其中一个是写操作，这种现象我们称为冲突。冲突可发生在一组由predicate lock覆盖的Data Item上面。
dependency graph：一个特定的history产生了依赖图，该依赖图定义了事务之间按时间顺序流动的数据流。已提交事务的操作在图中以节点显示，如果操作op1与op2冲突，则op1和op2两个节点存在一条由op1指向op2的有向边（op1在op2之前）。
equivalent等价性：如果不同的history有相同的事务以及相同的依赖图，那么我们说这些history是等价的。
serial history：我们说history是可串行化的，当且仅当该history与serial history是等价的。
形式化语言
读写操作
w1[x],r2[y]
其中w和r分别表示写和读，1和2分别表示事务T1和T2，x和y表示Data Item。
事务操作
c1,a2
c表示commit提交，c1表示事务T1提交
a表示abort回滚，a2表示事务T2回滚
谓词
r1[P],w2[P]
表示事务T1读满足谓词P的结果集和事务T2写满足谓词P的结果集。
ANSI SQL隔离级别
ANSI SQL隔离级别通过Phenomena现象定义（除此之外还可以通过锁、数据流图定义）：
P1(Dirty Read，脏读)：T1更新了数据，T2读到了该数据。
形式化语言表示：P1-->w1[x]...r2[x]...(a1 & c2 in either order)
A1-->w1[x]...r2[x]...((c1 or a1) and (c2 or a2) in any order)
P2(Non-repeatable/Fuzzy Read，脏读)：T2更新/删除数据，T1无法重复读。
形式化语言表示：P2-->r1[x]...w2[x]...c2...r1[x]...c1/
A2-->r1[x]...w2[x]...((c1 or a1) and (c2 or a2) any order)
P3(Phantom Read，幻读)：T2插入/删除满足谓词P的数据，T1重新执行读，结果不同
形式化语言表示：P3-->r1[P]...w2[y in P]...c2...r1[P]...c1
A3-->r1[P]...w2[y in P]...((c1 or a1) and (c2 or a2) any order)
锁（locking）
2PL两阶段锁：两个阶段，获取锁和释放锁，获取锁期间不释放锁，释放锁期间不获取锁。
读锁：Share locks
写锁：Exclusive locks
长期锁：持有直至事务结束（提交或回滚）
短期锁：持有至操作结束
通过锁来定义隔离级别：
| 隔离级别 | 读锁 | 写锁 |
|---|---|---|
| Degree 0 | 不需要 | 不需要 |
| Degree 1 = Read Uncommitted | 不需要 | 长期写锁 |
| Degree 2 = Read Commmitted | 短期读锁 | 长期写锁 |
| Cursor Stability | 1.当前游标上的读锁 2.短期读谓词锁 | 长期写锁 |
| Repeatable Read | 1.长期Data Item读锁 2.短期读谓词锁 | 长期写锁 |
| Degree 3 = Serializable | 长期读锁 | 长期写锁 |
ANSI隔离级别分析
P0(Dirty Write，脏写)：T1更新了data item，T2在T1提交或回滚前更新了相同的data item
形式化语言表示：w1[x]...w2[x]...c2...a1...
P1
H1: r1[x=50]w1[x=10]r2[x=10]r2[y=50]c2 r1[y=50]w1[y=90]c1
H1没有违反P1/P2/P3
P1的正确定义：
P1: w1[x]...r2[x]...((c1 or a1) and (c2 or a2) in any order)
P3
H3: r1[P] w2[insert y to P] r2[z] w2[z] c2 r1[z] c1
H3没有违反P3，但违反了业务约束
使用宽泛定义
P3: r1[P]...w2[y in P]...((c1 or a1) and (c2 or a2) any order)
重新定义ANSI的现象
P0: w1[x]...w2[x]...(c1 or a1) (Dirty Write)
P1: w1[x]...r2[x]...(c1 or a1) (Dirty Read)
P2: r1[x]...w2[x]...(c1 or a1) (Fuzzy or
Non-Repeatable Read)
P3: r1[P]...w2[y in P]...(c1 or a1) (Phantom)
其他隔离级别
Cursor Stability
Cursor Stability隔离级别用于阻止Lost Update现象。
P4（Lost Update）：T1读取了某个data item，接着T2更新了该data item，然后T1更新了data item并提交事务
形式化语言定义：r1[x]...w2[x]...w1[x]...c1
例如：
H4: r1[x=100] r2[x=100] w2[x=120] c2 w1[x=130] c1
在H4中，就算T2提交了，T2的更新也会丢失（T1，增加30，T2增加20，最终结果只是T1增加30，T2的更新丢失）。
禁止P2可以禁止P4，原因是w2[x]在r1[x]之后c1之前,w1[x]时会发现x已经变化（出现不可重复读现象），因此P4可用于区分Read Committed和Repeatable Read。
Cursor Stability隔离级别扩展了读已提交级别，从游标FETCH数据时增加了读动作并且在游标的当前位置（ITEM）上加锁，该锁一直持有直至游标移动或者关闭。
通常来说，从游标提取数据时可能会更新行，在这种情况下会持有锁直至事务提交（即使游标移动也是如此）。
在此隔离级别下，以下现象被禁止：
P4C: rc1[x]...w2[x]...w1[x]...c1 (Lost Update)
其中rc表示read cursor（读游标），相应的wc表示write cursor（写游标）。
显然：
READ COMMITTED « Cursor Stability « REPEATABLE READ
Snapshot Isolation
First-committer-wins先提交者胜：Start(T1)表示事务T1的开始时间，Commit（T1）表示事务T1的提交时间，
如果T1在提交的时候发现在[Start(T1),Commit(T1)]这个时间段内其他事务如T2的写数据集与T1的有交集，则T1会回滚。
形式化语言来表示：[Start(T1),Commit(T1)]∩[Start(T2),Commit(T2)] ≠ ∅，且wset(T1)∩wset(T2) ≠ ∅，如果T2已提交，则T1必须回滚。
单版本的history转换为多版本：
H1.SI: r1[x0=50] w1[x1=10] r2[x0=50] r2[y0=50] c2 r1[y0=50] w1[y1=90] c1
等价于
H1.SI.SV: r1[x=50] r1[y=50] r2[x=50] r2[y=50] c2 w1[x=10] w1[y=90] c1
SI不能保证非可串行化，比如下面的history：
业务约束是x + y > 0，但H5的结果是x + y < 0
H5: r1[x=50] r1[y=50] r2[x=50] r2[y=50] w1[y=-40] w2[x=-40] c1 c2
其依赖关系是T1--->T2--->T1
A5A Read Skew：r1[x]...w2[x]...w2[y]...c2...r1[y]...(c1 or a1)
T1读到了T2写入的y的新值，而x是旧值
A5B Write Skew：r1[x]...r2[y]...w1[y]...w2[x]...(c1 and c2 occur)
x和y之间满足某种业务约束，上述操作后可能会导致违反约束。
禁止P2可以避免A5A和A5B，因此A5A和A5B仅可用于区分可重复读隔离级别以下的级别。
从强度来看，SI比读已提交要隔离等级要高，READ COMMITTED « Snapshot Isolation，原因是SI可禁止P0、P1和A5A，而读已提交只能禁止P0和P1而不能禁止A5A。
小结
隔离级别汇总（通过禁止的异象描述）：
| 隔离级别 | P0 Dirty Write | P1 Dirty Read | P4C Cursor Lost Update | P4 Lost Update | P2 Fuzzy Read | P3 Phantom | A5A Read Skew | A5B Write Skew |
|---|---|---|---|---|---|---|---|---|
| Read Uncommitted | Not Possible | Possible | Possible | Possible | Possible | Possible | Possible | Possible |
| Read Committed | Not Possible | Not Possible | Possible | Possible | Possible | Possible | Possible | Possible |
| Cursor Stability | Not Possible | Not Possible | Not Possible | Sometimes Possible | Sometimes Possible | Possible | Possible | Sometimes Possible |
| Repeatable Read | Not Possible | Not Possible | Not Possible | Not Possible | Possible | Not Possible | Not Possible | |
| Snapshot | Not Possible | Not Possible | Not Possible | Not Possible | Not Possible | Sometimes Possible | Not Possible | Possible |
| ANSI SQL Serializable | Not Possible | Not Possible | Not Possible | Not Possible | Not Possible | Not Possible | Not Possible | Not Possible |
