intro

ACID

恢复系统：保证原子性和持久性

并发控制系统：保证隔离性

事务原子性和持久性

调度

可串行化调度

• 至少两个不同事务在相同的数据项上的操作，并且其中至少有一个是操作时，我们说二者是冲突的。
• 冲突等价：如果调度S可以经过一系列非冲突指令交换转换成S'，我们称二者是冲突等价的。
• 冲突可串行化：若一个调度与一个串行调度冲突等价，则将称之为冲突可串行化。
• 确定调度是否冲突可串行化。

构造一个有向图，称为优先图。该图由两部份组成G＝（V, E），其中V是顶点集，E是边集，顶点集由所有参与调度的事务组成，边集由满足下列三个条件之一的边Ti->Tj组成。

• 在Tj执行read(Q)之前，Ti执行write(Q)
• 在Tj执行write(Q)之前，Ti执行read(Q)
• 在Tj执行write(Q)之前，Ti执行write(Q)

如果优先图中存在边Ti->Tj，则在任何等价于S的串行调度S’中，Ti必出现在Tj之前。
如果调度S的优先图有环，则调度S是非冲突可串行化的，如果优先图无环，则调度S是冲突可串行化的。

事务隔离性与原子性

可恢复调度

无级联调度

事务隔离性级别

• 可串行化： 保证可串行化调度。
• 可重复读： 只允许读取已提交数据，而且一个事务两次读取一个数据项期间，其他事务不得更新该数据。但该事务不要求与其他事务可串行化。
• 已提交读：只允许读取已提交数据，但不要求可重复读。
• 未提交读：允许读取未提交数据。

以上都不允许脏写。

可串行化例子： 飞机机票同时选座，可以不需要串化，做权衡。

隔离性级别的实现

锁

确保可串行化的两阶段封锁协议：第一个阶段只获得锁但不释放锁，第二个阶段只释放锁但是不获得锁。

共享锁：用于事务读的数据项

排他锁：用于事务写的数据项

两种锁模式加上两阶段封锁协。

时间戳

为每个事务分配一个时间戳。

读时间戳：记录读该数据项的事务的最大时间戳。

写时间戳：写入时覆盖。

用来确保在访问冲突情况下，事务按照事务时间戳的顺序来访问数据项。当不可能访问时，违例事务将会中止，并且分配一个新的时间戳重新开始。

多版本和快照隔离

通过维护数据项的多个版本。广泛应用的称为快照隔离。

并发控制

确保隔离性

最常见的机制有两阶段封锁和快照隔离。

基于锁的协议

锁的概念

共享锁和排他锁。

事务只有在并发控制管理器授予所需锁后才能继续其操作。

可以多个事务访问读取一个数据项，但是限制同时只能有一个事务进行写操作。

死锁：类似操作系统。

如果为了避免不一致状态而采取封锁，则死锁是随之而来的必然产物。产生死锁显然比产生不一致状态要好，因为它们可以回滚事务加以解决。而不一致状态可能引起现实中的问题，这是DB不能处理的。

要求系统中的每个事务遵从称为封锁协议的一组规则。

封锁协议：规定事务何时对数据项们进行加锁、解锁。封锁协议限制了可能的调度数目。这些调度组成的集合是所有可能的可串行化的调度的一个真子集。

锁的授予

避免饿死的，当事务Ti申请对数据项Q加M型锁时，加锁的条件：

1. 不存在在数据项Q上持有与M型锁冲突的其他事务
2. 不存在等待对数据项Q加锁且先于Ti申请加锁的事务

两阶段封锁协议

保证可串行性的协议。要求每个事务分两个阶段提出加锁和解锁申请：

1. 增长阶段：事务可以获得锁，但不能释放锁。
2. 缩减阶段：事楞可以释放锁，但不能获得新锁。

两阶段封锁协议可以保证冲突可串行化，但是并不保证不会发生死锁（可能两个事务都处在增长阶段，互相持有对方的锁）。

加强为 严格两阶段封锁协议 避免级联回滚。
另外要求，事务持有的所有排他锁必须在事务提交后方可释放。这个保证未提交的事务所写的任何数据在该事务提交以前均以排他方式加锁，防止其他事务读这些数据。

另一个变体为 强两阶段封锁协议。它要求事务提交之前不得释放任何锁。

可以再加以修改，支持锁转换。在增长阶段允许锁升级，在缩减阶段允许锁降级。

封锁的实现

锁管理器：目前已加锁的每个数据项维护一个链表，每一个请求为链表中一条记录，按请求到达的顺序排序。可以实现为哈希表。

还应该维护一个基于事务标识符的索引，这可用效地确定给定事务持有的锁集。

基于图的协议

死锁处理

两种主要的方法：死锁预防和死锁检测/恢复

如果系统进入死锁状态的概率相对较高，通常就使用死锁预防机制； 反之，使用检测恢复。

死锁预防

两种方法：

1. 通过对加锁请求进行提成序或要求同时获得所有的锁来保证不会发生循环等待。
2. 每当等待有可能导致死锁时，进行事务回滚而不是等待加锁。

第一种方法有两个主要的缺点：1）在事务开始很难预知哪些数据项需要封锁。
2）数据项使用率可能很低。

第二种方法使用抢占与事务回滚。使用时间戳控制抢占。两种机制：

1. wait-die机制基于非抢占技术。仅当一个事务的时间戳比另一个小时，才允许等待，否则回滚。
2. wound-die机制基于抢占。与上种做法相反。

另一种方式是锁超时。申请锁的事务等待一定时间后没有被授予锁，则超时，自己回滚并重启。然而很难判定超时等待时间 。

死锁检测与恢复

周期性地判断有无死锁发生。

实现机制:

1. 维护当时将数据项分配给事务的有关信息，以及任何尚未解决的数据项请求信息
2. 提供一个使用这些信息判断系统是否进入死锁状态的算法
3. 当检测算法判定存在死锁时，从死锁中恢复

死锁检测

使用等待图的有向图精确描述。当且仅当等待图包含环时，存在死锁。

死锁恢复

1. 选择牺牲者：最小代价
2. 回滚：彻底回滚还是部份回滚
3. 饿死：避免同一事务总是被选为牺牲者

多级粒度

各种大小的数据项定义数据粒度的层次结构，可以图形化为树。树中的每个结点都可以单独加锁。当事务对一个结点加锁，它的全部后代结点将被隐式封锁。

意向锁

意向锁：如果一个结点加上了意向锁，则它的全部祖先结点均加上了意向锁。事务不必搜索整棵树就能判定能否成功地给一个结点加锁。

多粒度封锁协议

多粒度协议要求加锁自上而下，释放自下而上。

基于时间戳的协议

事务的时间戳决定了串行化的顺序。

时间戳排序协议

每个数据项Q有W-TS（Q）和R-TS（Q）两个TS

运行方式：

1. 事务Ti发Read(Q),TS（Ti）要大于等于W-TS（Q），并且修改R-TS（Q）
2. 事务Ti发Write（Q）

A. 若TS（Ti）< R-TS(Q)，则Ti产生的Q值是先前所需要的值 ，因此回滚
B. 若TS（Ti）< W-TS(Q)，则Ti试图写入的Q已过时，也回滚
C. 其他情况，执行W操作，修改W-TS

基于有效性检查的协议

要求每个Ti在其生命周期中按两个或两个阶段执行。

1. 读阶段。将各数据项读入并保存在事务Ti的局部变量中。
2. 有效性检查阶段。判定是否可以执行write操作而不违反可串行性。如果失败，则终止这个事务。
3. 写阶段。若事务Ti通过有效性检查，则保存任何写操作结果的临时局部变量值。

有效性检查

三个TS：

Start(Ti)、 Validation(Ti)、Finish(Ti)

令TS(Ti) = Validation(Ti)

任何满足TS（Tk）< TS(Ti)的事务Tk必须满足两条件之一：

1. Finish(Tk) < Start(Ti)
2. Tk所写的数据集与Ti所读数据项集不相交，并且 Start(Ti) < Finish(Tk) < Valiation(Ti)

也称为乐观的并发控制

多版本机制（MVCC）

多版本时间戳排序

每个数据项Q，存在一个版本序列，每个版本包含三个字段：内容，读TS,写TS.

可串行性。

1. 写操作，返回对应的版本的内容。
2. 读操作，若事务的时间戳 < 对应读的TS，回滚该事务。若事务的TS＝对应版本的写TS，覆盖；否则创建新版本。

多版本两阶段封锁

区分只读事务与更新事务。

更新事务执行强两阶段封锁阶段，即它们持有全部锁直到事务结束。

详细见书。

快照隔离

在事务开始执行时给它数据库的一份”快照“。

两种变种用来防止更新丢失。分别为 先提交者获胜 和 先更新者获胜。

快照隔离不能保证可串行化。

插入操作、删除操作与谓词读

事务没有访问相关的数组，但是依然可能会出现冲突。称为幻象现象。

索引封锁。

谓词锁。

实践中的弱一致性级别

索引结构中的并发

蟹行协议：

• 当查找一个码值时，蟹行协议首先用共享模式锁住根结点。沿树向下遍历，它在子结点上获得一个共享锁，以便向更远处遍历，在子结点上获得锁以后，它释放父结点上的锁。它重复该过程直至叶结点。
• 当插入或删除一个码值时，如下：

1. 采取与查找相同的协议直至希望的叶结点，到此为止，它只获得（和释放）共享锁。
2. 它用排它锁封锁该叶结点，并且插入或删除码值
3. 如果需要分裂一个结点或者它与兄弟结点合并，或者在兄弟结点之间重新分配码值，蟹行协议用排他锁封锁父结点，在完成这些操作之后，它释放该结点和兄弟结点上的锁。如果父结点需要分裂、合并或者重新分布码值，该协议保留父结点上的锁，以同样的方式传播得更远。

B-link树封锁协议

使用B-link树避免在获取另一个结点的锁还占有一个结点的锁，获得更多的并发性。
B-link树要求每个结点维护一个指向右兄弟结点的指针。

B-link树封锁协议：

• 查找
• 插入与删除
• 分裂
• 合并