并发控制
[TOC]
事务并发执行可能会存取和存储不正确的数据，破坏事务的隔离 性和数据库的一致性。
挑战
并发操作的潜在不一致性：
丢失修改（lost update）：事务1与事务2从数据库中读入同 一数据并修改，事务2的提交结果破坏了事务1 提交的结果，导致事务1的修改被丢失。
读“脏”数据（dirty read）：事务1修改某一数据，并将其写回磁盘。事务2读取同 一数据后，事务1由于某种原因被撤消，这时事务1已 修改过的数据恢复原值，事务2读到的数据就与数据 库中的数据不一致，是不正确的数据，又称为“脏” 数据。
不可重复读（non-repeatable read）：事务1读取数据后，事务2执行更新操作并提交，使事务1无法再现前一次读取结果。包括三种如下，后两种不可重复读有时也称为幻影现象（phantom row）或者Phantom read (幻影读）：
事务2对其做了修改，当事务1再次读该数据时，得到与前一次不同的值。
事务2删除了部分记录，当事务1再次读取数据时， 发现某些记录神秘地消失了。
事务2插入了一些记录，当事务1再次读取数据时，发现多了一些记录。
事务隔离级别
The levels from low to high are:
Read uncommitted (未提交读）：可以读其他事务未提交但已经修改的数据，存在读“脏”数据问题等问题。
Read committed (己提交读） ：可以读其他事务已经提交的数据，存在不可重复读问题。
Repeatable read (可重复读）：某事务读取的数据不允许被其他事务修改。存在幻影读问题。
Serializable (序列化)：就像串行执行事务。
四个层级都不允许多个事务同时修改数据，所以丢失修改问题在这四个层级都不会出现。
锁
锁类型：
Shared lock (共享锁)，或者读锁。
eXclusive lock (排它锁)，或者写锁。
协议类型：
First level lock protocol (一级封锁协议)：没有读锁，写锁在修改数据前加，事务结束后释放。存在读“脏”数据问题等问题。
Second level lock protocol (二级封锁协议）：读锁在读数据前加，读完释放。写锁在修改数据前加，事务结束后释放。存在不可重复读问题。
Third level lock protocol (三级封锁协议）：读锁在读数据前加，事务结束后释放。写锁在修改数据前加，事务结束后释放。
数据库管理系统通常使用two-phase locking（两段锁）protocol，即一个事务可以看成两个阶段，第一个阶段只请求锁，第二个阶段只释放锁。
一次性封锁（下一部分提到）是两段锁协议的子集。
死锁
Livelock(活锁）：数据库课程的活锁和操作系统的活锁不太一样，这里指的是优先级低导致的饥饿问题。可以通过老化解决。
Deadlock (死锁）
处理死锁方法：
deadlock prevention (死锁预防）：One-time block (一次性封锁）和Ordering block (顺序封锁）。
deadlock detection and deadlock recovery scheme (死锁诊断与解除)：数据库的常用方法，如果等待图有环则出现死锁，选择回滚一个或多个事务来解除死锁。
并发调度
Serializability (可串行性) 是并发调度的唯一评价标准。即，两个并发的事务，如果并发结果与串行结果一样（T1T2，或者T2T1），则具有可串行性。
具体来说，对于事务i和j，如果通过等价转换能让i的所有操作移到一边，j在另一边，则说这个调度是conflict serializable schedule (冲突可串行化调度），那它一定也是有可串行性的。
等价转换的原则是，不能交换Conflict operations (冲突操作），例如：
对于同一个数据x，$R_i(x)$ and $W_j ( x )$ are conflict operations
对于同一个数据x，$W_i(x)$ and $W_j ( x )$ are conflict operations
对于不同数据的操作不冲突。
例子：
粒度
有时加锁时不必要对整个数据库加锁，只对行加锁就足够，这种程度的区别叫做粒度（granularity）。
Multiple granularity tree (多粒度树)表示这种粒度的差别：
扩展的锁类型：
Intention-Shared (IS) Lock (意向共享锁）
Intention-Exclusive (IX) Lock (意向排他锁）
Shared and Intention-Exclusive (SIX) Lock (共享意向排他锁，S+IX）
这种意向指只有部分更细粒度的对象会被加显示锁（S和X）
如上图，左侧时兼容表，右侧是锁的严格等级。
几个例子：
IS对IS，都是读，没事。
IS对IX，读的部分和写的部分可能不重叠，没事。
IX对IX，写的部分可能不重叠，没事。
SIX对SIX，两者都要读所有部分，即使部分修改也一定会冲突，不兼容。
在加锁时：
Ti must lock the root of the tree first in any mode
Ti can lock a node in S or IS mode only if Ti currently has the parent of Q locked in IS mode.
Ti can lock a node Q in X, SIX, or IX mode only if Ti currently has the parent of Q locked in either IX or SIX mode.
在释放锁时：
Ti can lock a node only if Ti has not previously unlocked any node (that is, two phase locking).
Ti can unlock a node Q only if Ti currently has none of the children of Q locked (that is , bottom-up order).
最后更新于
