事务管理 Transactions
重要考纲
主要内容：
事务是数据库管理系统进行并发控制和恢复的基本单位。讲解事务的基本概念、事务的ACID性质、事务并发执行（日志记录规则）的好处和潜在问题，以及并发事务的可串行性和可恢复性。
课外学习
1）事务的并发执行有哪些好处？
2）如果不进行恰当的并发控制，多个事务并发执行可能产生哪些潜在的问题？
知识点的学习
事务是访问数据项、并可能更新数据项的程序执行单元。
- 事务的ACID属性
- atomicity原子性：要么事务的所有操作都正确反映在数据库中，要么没有。
- consistency 一致性：在隔离状态下执行事务，可以保证数据库的信息一致性。保证数据库内容的正确性。
- isolation 隔离性：尽管有多个事务同时执行，但每个事务必须不知道其他同时执行的任务。必须对其他并发执行的事务隐藏中间的事务结果。即一个事务不会被另一个事务所影响。
- durability 持久性：事务成功完成后，即使系统出现故障，事务对数据库的影响也应当永久存在。
满足隔离性，最理想的情况就是一个事务执行完毕后再执行下一个事务。但是出于性能上的考虑，往往实际上是多个事务并发执行。这就要求事务执行的过程中，不受并行执行的事务影响。例如，不能读取到另一个还没有commit的事务写入的值。
- 事务通过两种操作访问数据
- read
- write
每个事务，都有一个工作空间。工作空间中有该事务需要访问到的数据。这些数据，在某些内存块的里面。如果是write，修改好了这些数据以后，会再写回到内存中去
通过转账记录进行说明：
上述操作，在T1事务没有提交的时候，就进行T2事务的话，就会得到A+B的总和为150的结果，从而不符合隔离性的要求
- 事务状态转移
active：事务在正常执行的状态。
partially committed：如果事务的操作，已经执行了最后一条语句，就进入准备提交阶段。
failed：事务提交失败。
committed：事务已经提交，那么就要保持它的持久性。
aborted：事务提交失败后，进入失败状态，要将该事务进行过的所有操作全部清空。
- 并发执行中的异常
- 丢失修改
- 读脏数据
- 不可重复读
- 幽灵问题
- 不可重复读是针对一个数据的前后两次读取值不一致的情况，这个数据本身就是存在于数据库中的。
- 而幽灵问题是指前后两次相同的查询，会多出一些记录，或者少掉一些记录来。
对数据库的多次修改，最终产生的结果只有最后一次修改，称为丢失修改问题
一个事务读取了另一个事务中写入的，还没有提交的脏数据。假设另一个事务最终没有提交那个脏数据，而是产生回滚，那么读取脏数据的事务对数据库产生的修改将是不正确的
在事务T2没有提交的时候，T1就进行读取。这样，由于隔离性的要求是：在一个事务没有提交时，其他的任何事务都不会影响这个事务。但是，此时T2事务却影响了T1事务读取数据的结果，不满足数据库隔离性的要求。
同样，在事务T2没有提交的时候，T1就又进行了一次查询。此时T2的插入操作，影响了T1在一个事务当中的查询结果，使前后两次查询结果不一致，因此产生幽灵问题，不满足隔离性的要求。
幽灵问题和不可重复读问题的区别是：
不可重复读问题比较好解决，只需要在事务T1第一次对数据A进行读取时，加上一个S锁即可。那么事务T2将不能对A进行更改。
但是幽灵问题解决起来比较困难，代价比较高
- 引入事务执行的调度 Schedules
- 一组事务执行的顺序。
- 这两个事务完全是串行执行的，这是串行调度。
- serial schedule一定满足隔离性
- 也是一个串行调度，交换了顺序。
- 显而易见，串行调度一定是满足隔离性的。
- 通过上述变化，最终结果中，A+B仍然是200。这是由于，二者在时间上交错的部分都是不矛盾的，也就是说，交错的部分进行互换，是不影响结果的。因此，这就等价于例1。
- 同样，这个事务的调度满足隔离性要求。
- 隔离性是指一个事务不会被另一个事务所影响。
- 下面的两个事务之间存在着丢失修改的问题
事务T1的write(A)在事务T2的write(A)之后，且无法交换。
访问相同的数据时，Read和Read操作可以交换，Read和Write操作、Write和Write操作均不能交换。
- serializability 可串行化
- 如果一个（可能是并发执行的）计划（事务集合），可以等同为一个串行的计划，那么这个计划称为可串行化的。
- 分类
- 冲突可串行化
- 视图可串行化
- 冲突可串行化 conflict serializability
- 视图可串行化 view serializability
- 一个交叉调度是视图可串行化的，必要条件之一是：假设其对应的串行调度中的事务Ti执行了Read（Q）操作，并且Q的值是由串行调度中的事务Tj产生的，那么这个交叉调度中，事务Ti执行了Read（Q）操作，Q的值也应当是对应的事务Tj产生的。
- 一个交叉调度是视图可串行化的，必要条件之一是：这个交叉调度与其对应的串行调度之间，写入各个数据的终末值的是同一些事务。
指从冲突操作的角度考虑，是可串行化的。例如Schedule 3中，将交叉执行的两个事务转化为串行执行的两个事务的过程中，两两进行交换的操作，没有产生前后依赖关系（即冲突）的，最终转化称为两个串行执行的事务，这就叫做冲突可串行化。
此外，如果一个交叉调度是冲突可串行化的，那么串行化以后事务的顺序是由其中一对冲突的操作的先后次序决定的。哪一个事务的冲突操作在前，哪一个事务串行化以后的先后次序就在前。
不是冲突可串行化的例子
判断冲突可串行化的算法
通过考察所有冲突的操作对，画出一个有向图。
如果事务Ti有一个操作和Tj的某个操作冲突，如果Ti的这个操作在Tj的对应冲突的操作之前，那么Ti这个节点就和Tj这个节点之间，存在一条Ti指向Tj的有向边。
如果有向图存在环，那么这些事务将不是冲突可串行化的。如果有向图不存在环，那么这些事务将是冲突可串行化的，并且串行化以后这些事务的执行顺序是对有向图进行拓扑排序的顺序。
条件如下：
1. 一个交叉调度是视图可串行化的，必要条件之一是：这个交叉调度与其对应的串行调度之间，读到各个数据的初始值的是同一些事务。
上面这个交叉调度不是冲突可串行化的，因为T27与T28之间存在环。
但是，上面这个交叉调度是视图可串行化的。它串行化得到的串行调度是T27->T28->T29。
这个交叉调度的该串行调度满足上述视图可串行化的三个条件
重要结论：每一个冲突可串行化的调度，都是视图可串行化的。反之未必。
有些视图，不是冲突可串行化的，也不是视图可串行化的，但是它是可串行化的。
加减操作可以
- 可恢复调度 recoverable schedule
如果在一个调度中，事务B读取了事务A先前写入的数据，那么事务A的提交操作，出现在事务B之前，这就称为可恢复调度。
T9读取了T8写入的数据，然而，T9的提交操作在T8之前。如果之后T8进行了回滚，那么T9事务将向用户显示了不一致的数据库状态。这就会产生“读脏数据”的问题。
因此，数据库必须保证调度是可恢复的。
- cascading rollback
上面这个例子中，T11读取了T10写入的值（脏数据），T12又读取了T11写入的值（脏数据）。
因此，T10发生回滚后，T11也要发生回滚，过后T12也要发生回滚。
- 非级联调度（Cascadeless Schedules）
① 级联回滚必须不能发生。
② 对于任意一对事务A与B，如果事务B读取了事务A之前写入过的数据，那么事务A的提交操作一定发生在事务B的提交操作之前。
- 数据库必须提供一种机制
- 冲突或视图可序列化
- 可恢复的，最好是非级联调度的
- 并发控制协议
- 并发控制协议允许并发调度，但是要确保并发调度是冲突（或视图）可序列化的，并且是可恢复也是无级联回滚的）
- 弱一致性水平
- 一些应用程序愿意接受较弱级别的一致性，允许部分不可序列化的调度，以减少代价。 例如，想要获得所有账户的大致总余额的只读交易；又例如，为查询优化计算的数据库统计数据可能是近似的。
- 数据库中的隔离级别
- 最高：串行化
- 意味着四种问题（幽灵问题、不可重复度、读脏数据、丢失修改）都不能存在。
- 次高：可重复读（不关心幽灵问题）
- 再次：读提交（不关心幽灵问题，也不关心不可重复读问题，但要保证不读脏数据）
- 最低：读非提交
三种问题会被解决，除了幽灵问题。
只读别的事务已经提交的数据。
别的事务未提交的更改过的数据也可以读（连脏数据也允许读）。
事务的并发控制协议
考试范围
主要内容：
并发控制保证多个事务并发执行如同串行调度一样获得正确的运行结果。讲解基于锁的并发控制协议的主要思想、两阶段封锁协议（2PL）、死锁及解决办法、多粒度锁, 以及数据删除和插入情况下的并发控制。什么是死锁预防，什么是死锁避免
课外学习：
1）事务的并发执行有哪些好处？
2）如果不进行恰当的并发控制，多个事务并发执行可能产生哪些潜在的问题？
3）证明2PL是保证事务调度冲突可串行性的充分条件，而非必要条件。
重要的知识点
- 每个并发事务都自觉遵守这个协议，那么就会自发形成一种相互等待关系，形成一种调度，而这种调度可以证明都是可串行的、可恢复的。
- 基于锁的协议
- 共享锁（读锁）（S锁）
- 独占锁（写锁）（X锁）
- 基于时间戳的协议
事务执行的时候，都给事务一个时间戳。越早产生的事务，越排在串行事务的前面。
- 基于验证的协议
- 对并发控制保持乐观态度。
- 访问数据，或者修改数据后，在要提交的时候，验证一下和其他事务是否冲突。（在partially committed阶段）
- 所有正在做的事务都放在内存中，不影响数据库。
- 基于锁的并发控制
- 访问数据之前，要申请相应的锁。
- 排他锁：（X）
- 共享锁：（S）
写数据时，需要申请排他锁。
读数据时，需要申请共享锁
- 一个事务可以分为两个阶段。
前一个阶段称为锁的增长阶段。
后一个阶段称为锁的释放阶段。
- lock point
锁的增长阶段的结束点；
也是最后一个锁已经被申请获得了的时间点。
- 一些事务可以按照其lock point的顺序，进行冲突可串行化的调度
- 证明：如果在前驱图中Ti对Tj有一条指向的有向边，那么Ti的lock point一定小于Tj的lock point。因为，如果Ti对Tj有一条指向的有向边，那么Ti和Tj之间肯定有一对冲突的操作访问相同的数据。
- 只有Ti将这个数据的锁放掉后，Tj才可以给这个数据加锁。由于lock point过后，事务不会再加锁，因此此时Ti放锁一定处于Ti lock point之后，Tj加锁一定处于Tj lock point之前。因此，Ti的lock point 一定小于Tj的lock point。
- 因此这些事务的前驱图中一定没有环。因此这些事务可以进行冲突可串行化的调度（按照拓扑排序的顺序）。
- 基本两阶段封锁 basic tow-phase locking
- 刚刚所述的两阶段封锁协议就是基本两阶段封锁，分为加锁阶段和放锁阶段。
- 严格两阶段封锁 strict two-phase locking
- X锁加的时间更长，X锁要到事务即将提交或者即将回滚的时候再放开，以防止读脏数据的问题。
- 好处：保证可恢复性，防止读脏数据的问题
- 坏处：代价是X锁的时间更长，其他事务等待的时间变长，会降低并发度
- 强两阶段封锁：rigorous two-phase locking
- 所有锁都要加到即将提交或者即将回滚的时候再放开。
下面需要说明的是：
两阶段封锁协议，不是冲突可串行化的必要条件，也就是说，有些冲突可串行化的事务，并不满足两阶段封锁协议。
这些事务的前驱图是
因此，这些事务可以按照T3->T1->T2进行冲突可串行化的调度。
这些事务的加锁与放锁操作如下：
T1事务放锁之后，又进行了加锁操作
因此，T1事务不满足两阶段封锁协议
因此，事务满足两阶段封锁协议，是可以进行冲突可串行化调度的充分条件，而不是必要条件。
也就是说，满足两阶段封锁协议，那么一定是冲突可串行化调度
但是如果是冲突可串行化调度，不一定会满足两阶段封锁协议
- 带有锁转换的两阶段封锁协议：
有些时候，访问数据库数据时，我们需要先读数据，再修改数据。
如果我们读取数据加上S锁，修改数据先放掉S锁，再加上X锁，就不满足两阶段封锁协议，导致事务之间可能不能冲突可串行化。
假如一开始就加上X锁，又会降低并发度。
因此，解决方案是：一开始加上S锁，等到要修改数据时，将S锁升级为X锁。
- 现在两阶段封锁协议变为：
第一阶段可以进行加锁操作，也可以进行锁升级操作。
第二阶段可以进行放锁操作，也可以进行锁降级操作。
带有锁转换的两阶段封锁协议，也可以保证事务按照lock point排序，是可以实现冲突可串行化调度的。
- 数据库中实现锁的机制：
基于锁的并发控制容易造成的问题：死锁
假如下面两个事务都要遵守两阶段封锁协议：
事务T1: write(A), write(B)
事务T2：write(B), write(A)
加锁放锁的流程图如下：
由于要遵循两阶段封锁协议，因此T1给A加锁了以后，在没有给B加锁之前，不会将A的锁放掉；T2给B加锁了以后，在没有给A加锁之前，不会将这B的锁放掉；
产生了互相等待，然而此时T1不会把A的锁放掉，T2也不会把B的锁放掉，从而互相等待是无限循环。
1. Deadlock Prevention（死锁预防）
定义： 死锁预防协议确保系统永远不会进入死锁状态。
预防策略：
- 要求每个事务在开始执行之前锁定其所有数据项（预声明）。
- 解释： 这一策略确保在事务执行之前，事务已经声明了它需要的所有资源，防止在事务执行过程中因为等待资源而造成死锁。
- 对所有数据项进行部分排序，并要求事务只能按照指定的部分顺序锁定数据项（基于图的协议）。
- 解释： 这一策略通过对资源进行部分排序，确保资源的获取顺序是固定的，从而避免了环路依赖的产生，从而防止死锁。
2. Timeout-Based Schemes（基于超时的方案）
定义： 在这种方案中，事务只等待锁定一段指定的时间。
详细说明：
- 事务只等待锁一段指定的时间。 超过这个时间后，等待超时，事务回滚。
- 解释： 通过设置一个等待时间，如果事务在这段时间内未能获取锁，它将放弃当前操作并回滚，重新尝试或选择其他操作。
- 因此，死锁是不可能的。
- 解释： 由于没有事务会无限期等待锁，因此死锁不会发生。
- 实现简单，但可能出现饥饿。
- 解释： 尽管这种方法实现起来比较简单，但可能会导致某些事务总是无法获取所需资源，从而长期处于等待状态，即饥饿。
- 确定超时间隔的最佳值也很困难。
- 解释： 设置合适的超时值是一项挑战，因为值设得太短可能导致频繁回滚，而设得太长则可能无法有效防止死锁。
- Deadlock Detection（死锁检测）
死锁描述：
- 死锁可以用一个等待图（wait-for graph）来描述，该图包含一个对 (G = (V, E))：
- V 是顶点集合（系统中的所有事务）。
- E 是边集合，每个元素是一个有序对 Ti -> Tj。
等待图中的边（Edge in the Wait-for Graph）：
- 如果 Ti -> Tj 在 E 中，那么存在一条从 Ti 到 Tj 的有向边，这意味着 Ti 正在等待 Tj 释放一个数据项。
边的插入和删除（Insertion and Removal of Edges）：
- 当 Ti 请求一个当前由 Tj 持有的数据项时，Ti -> Tj 被插入到等待图中。只有当 Tj 不再持有 Ti 需要的数据项时，这条边才会被删除。
表示的内容是Ti等待Tj，然后Ti→Tj，表示一个等待图
死锁状态（Deadlock State）：
- 如果且仅当等待图中存在环（cycle）时，系统处于死锁状态。
- 解释： 环的存在意味着有一组事务互相等待对方释放资源，导致所有这些事务都无法继续执行。
死锁检测算法（Deadlock-Detection Algorithm）：
- 必须定期调用死锁检测算法来查找环。
- 解释： 死锁检测算法通过分析等待图来识别是否存在环，从而确定系统是否处于死锁状态。
- 如何避免无限循环
- 一个事务要进行，申请的锁要么全部给这个事务，让这个事务进行，要么一个都不给这个事务，让这个事务不要进行，防止与其他事务形成死锁。
- 对数据的访问规定一种次序（偏序集）（有向无环图），那么就不会产生死锁（循环等待）。
- 下面是一个例子
例如，假设有两个事务：
T1: A-50 B+50
T2: B-10 A+10
我们可以执行作：
T1: A-50 B+50
T2: A+10 B-10
这样，可以降低出现死锁的概率
- 死锁检测：
每隔一定时间，数据库后台会有一个进程定期检查数据库中是否出现死锁。
在数据库中，死锁的检查利用了“等待图”。
等待图中，箭头表示，Ti在等待Tj事务的锁。
如果在等待图中存在环，表示出现了死锁
- 练习题
上面是一个Lock Table的例子。存在六个事务，存在七个需要被访问的数据。事务和事务之间的箭头表示等待的关系。已经获得锁的事务用实心框表示，还在等待的事务用空心框表示。
(a)哪些事务产生了死锁？
作出等待图，查看环。（T1/T2/T6）
(b)为了解决死锁问题，哪个事务需要被roll back？（假如要求为：回滚掉的事务，需要释放出最多的锁）
在环中选择一个事务进行回滚。(T2)
- 有没有不满足两阶段封锁协议的方式，同样使得事务之间满足冲突可串行化？
假如我们知道，数据库中数据的访问是按照某种偏序关系进行的（如上图），那么不满足两阶段封锁协议，也有可能能够使事务之间满足冲突可串行化。
- 更简单的一种基于图的协议：树协议
- 只有一种锁：X锁
- 第一个锁可以加在树结构的任意一个结点上。
但是，后面要在某一个结点上加锁的前提是，父节点已经被锁住了。
- 一个结点上的锁，在数据访问完毕后，可以在任何时候放掉。
树协议的性质：虽然不是两阶段封锁协议，但是保证冲突可串行化的，同时，又是不存在死锁的。
树协议的好处：一个数据的访问的锁，访问完毕就可以释放，因此可以提高并发度，降低锁上面的等待时间。并且，不会产生死锁。
树协议的缺点：不能保证可恢复性，允许读脏数据。因此，基于锁的并发控制协议中，为了保证可恢复性，一个事务如果读取了另一个事务写入的数据，那么这个事务的commit操作，一定要在另一个事务之后。
- 多粒度
一个锁可以将一条记录锁起来，也可以直接把整个表格锁起来。
数据库里面的数据项，根据其大小可以分为粗粒度和细粒度。
- 粗粒度：例如，DataBase层面、Table层面等。
- 细粒度：例如，记录、属性层面。
其中S锁、X锁可以加到细粒度的层面上，也可以加到粗粒度的层面上
那么，有一个问题：粗粒度上面的锁和细粒度上面的锁如何进行有效的判断？细粒度上假如已经加了一个S锁或X锁，那么粗粒度上加锁是否冲突？
为了解决上述问题，在粗粒度上，引入了三种锁：IS锁、IX锁、SIX锁。
如果一个事务，要在某一个细粒度数据（如记录）上面加上S锁，那么这个事务必须要在这个细粒度数据的父节点（如表）这一粗粒度数据上加上IS锁。
如果一个事务，要在某一个细粒度数据（如记录）上面加上X锁，那么这个事务必须要在这个细粒度数据的父节点（如表）这一粗粒度数据上加上IX锁。
SIX锁，是S锁和IX锁的结合。例如，一个表的某些记录需要直接读取，有些记录可能产生更改，就在表层级上加上SIX锁，这样表中需要读的记录不用再加上S锁了，表中需要写的记录需要加上X锁。
如果粗粒度（如表）上已经加了IX锁，表示表的子节点的某条记录加上 X锁。此时如果想对整个表加上S锁，那么S锁会和IX锁产生冲突。
事务T用如下规则锁定结点Q:
- 必须遵守锁的兼容性矩阵。
- 首先，要锁定树的根，即最粗的粒度，可以以任何方式进行锁定。假如只读，就加上S锁，如果要进行修改，就加上X锁。
- 如果要在一个结点Q上加上S或者IS锁，那么其父节点一定要加上IX锁或者IS锁。
- 如果要在一个结点Q上加上X锁、SIX锁或IX锁，那么其父节点一定要加上IX锁或SIX锁。
- 事务T遵循两阶段封锁协议
- 解锁结点Q的时候，必须保证Q没有孩子正在被锁定。
直观来说，上锁是从根节点向下上锁的，放锁是从叶子结点一层层向上放锁的。
先在根节点上加上IX锁，表明下面的结点可能会产生修改
再在左子节点上加上IX锁，表明下面的结点可能会产生修改。
然后，在表这个粒度上，对表Fa加上SIX锁，表明要读取整个表的信息，同时可能对表中某些记录产生更改。
最后，在记录这个细粒度上，对某些记录上加上X锁，表示要更改这条记录
对于加了X锁的这条记录，可以去更改；但是对于其他的记录，不用再加上S锁了，可以直接去读。
- 对上面的兼容性矩阵的理解
- S和X是对当前粒度加锁，表示所有子粒度全部加当前的锁。
- IS和IX表示子粒度中有些加上了S或者X锁。
- SIX表示当前粒度加S锁，子粒度有些加上了X锁，也就是所有子粒度都加上S锁，部分加上X锁。
- 如果要在一个结点Q上加上S锁或者是IS锁，那么其父节点一定要加上IX锁或者是IS锁👇
- 如果要在一个结点Q上加上X锁、SIX锁或IX锁，那么其父节点一定要加上IX锁或SIX锁
例如，同一个结点上，SIX锁为什么和S锁冲突？
因为SIX锁表明这个结点有些孩子加了X锁，但是这个结点加S锁表明这个结点的所有孩子都加上S锁。因此孩子中，加S锁会和加X锁产生冲突。因此，同一个父节点不可能同时申请到SIX锁和S锁。
那么父节点不可能加S锁，因为S锁会加在父节点的更低层级。此时，父节点只能加IS锁或者IX锁。
如果要在一个结点Q上加上X锁、SIX锁或者IX锁，表示这个结点的全部子节点或者部分子节点上加X锁。那么父节点不可能加X锁，因为X锁会加在父节点的更低层级。此时，父节点只能加上IX锁或者SIX锁。
数据恢复
考试范围
主要内容：
数据库管理系统确保在系统发生各种故障的情况下，数据库能恢复到正常状态。讲解各种故障类型、基于日志的恢复策略、提高恢复效率的checkpoint方法,以及业界采用的ARIES恢复算法。不同的阶段（Phase）意义;脏表更新和checkpoint的关系；每一个phase的buffer里面存什么
课外学习
： ARIES算法如何在DBMS恢复效率和系统正常运行时效率两方面取得平衡？
主要内容
记录日志实现数据恢复
① 先记录日志，再修改数据库。
② 重演历史，然后进行Undo操作。
Stable Storage
理想的存储介质，现实中并不存在。任何故障中，都不会丢失数据。可以近似实现为：利用多个存储介质进行备份。
在这里，我们假设日志都会记录到Stable Storage中，不会丢失。
基本两阶段封锁协议可以保证冲突可串行化，但是无法保证数据可恢复性
因为假如事务A和事务B保持基本两阶段封锁协议，那么假如A要进行数据写入，会在写入之后立马放开X锁，那么事务B就有可能读取A的脏数据。假设B先提交，A再回滚，那么B提交的数据将不可恢复
在这里我们假设，事务采取严格两阶段封锁协议，即X锁要保持到事务提交的时候再放开。