Chapter 7 —— 数据库事务处理技术

事务及事务处理技术

什么是事务？

· 事务（Transaction）是用户定义的一个数据库操作序列，用人话说就是把一堆SQL操作封装起来，这些操作只能被完全执行或完全不执行，是一个不可分割的单位。

· 举个例子，假设领导要给小李转500块，那就涉及到领导先少500，小李再多500，如果在领导少了500后数据库发生异常，那小李就没多500，这不是我们希望看到的，所以我们可以把这个转钱的过程封装为一个事务：

· 需要注意的是，事务和程序是两个概念，在关系数据库中，事务可以是一条SQL语句、多条SQL语句或整个程序；而一个程序通常可以包含多个事务。

· 事务是恢复和并发控制的基本单位。

· 事务的创建语法如下：

BEGIN TRANSACTION;
    SQL 1;
    SQL 2;
    ...
COMMIT; # 提交事务，全部执行

BEGIN TRANSACTION;
    SQL 1;
    SQL 2;
    ...
ROLLBACK; # 回滚事务，全部不执行

· 还是上面转钱的例子：

· 一个正确的事务，应该具有ACID四种特性。

正确事务的ACID特性

· 原子性（Atomicity）：事务中包括的操作，要么全做，要么全不做。

· 一致性（Consistency）：事务执行的结果必须是从一个一致性状态转向另一个一致性状态。

· 隔离性（Isolation）：一个事务的执行不能被其它事务干扰。一个事务内部的操作和使用的数据对其他并发的事务是隔离的；并发执行的各个事务之间不能相互干扰；也不能相互查看其它事务未提交的数据。

· 持久性（Durability）：持久性也称为永久性（Permanence），一个事务一旦提交，它对数据库中的数据改变就应该是永久的，接下来的其它操作或故障都不应该对已提交的结果有影响。

· 可以发现，其它三个特性都是为了一致性服务的。

· 为了保证ACID特性，DBMS提供了两大类的事务处理技术：

1. 并发控制：保证一致性和隔离性。

2. 数据库恢复：保证原子性和持久性。

多事务执行

· 多事务执行可以分为多用户数据库系统、串行执行、交叉并发和同时并发。

多用户数据库系统

· 顾名思义，允许多个用户同时使用数据库系统。

· 在同一时刻并发运行的事务数可达数百上千个，如订票系统、银行系统。

串行执行

· 每个时刻只有一个事务运行，其他事务必须等到这个事务结束以后方能运行。

· 假设有事务T1：A给B转50元；T2：A转10%的余额给B；初始状态A=100，B=200，A+B=300，如果先T1再T2：

· 当然，也可以先T2再T1，但这样结果肯定是不一样的。故N个事务有N!种不同的串行执行计划。

· 很明显，一个一个执行无法充分利用系统资源，发挥数据库共享资源的特点。

交叉并发

· 对于单核系统，并行执行其实是事务中的操作交叉轮流执行。

· 因此，单核系统中的并行事务并没有真正的并行运行，只是很快地交叉执行，看上去像是并行了，但它确实能减少处理机对空闲时间，提高系统效率。

· 还是上面的例子，但现在是交叉轮流执行了：

· 可以发现，结果和串行执行是一样的，所以交叉并发和串行执行计划是等价的。

同时并发

· 在多核系统中，就能实现真正意义上的并发了，每一个核（处理机）可以运行一个事务，多个核可以同时运行多个事务。

· 这是最理想的并发方式，但是受限于硬件环境，同时也需要实现更复杂的并发机制。

并发执行可能导致的问题

· 如果两个事务没有很好地隔离开来，相互受到了影响，就会造成最后的结果和开始的状态不一致。

· 还是刚刚那个例子：

· 可以看到，在T1更新了A之后，还没写入A，T2就读了A了，这样就导致读到了错的A；除此之外，在T1写完了B并提交之后，T2又写了一次B又提交，这样就覆盖了上一步的修改。

· 这样，事务的隔离性和一致性都遭到了破坏，很明显DBMS不能允许这样的事务执行。

· 像上面这种覆盖造成的错误，我们分了两类：

1. 一类丢失更新（First Lost Update）：一个事务撤销回滚，导致已提交的另一个事务的数据

   被覆盖，我们也把它称为撤销覆盖。

   

2. 二类丢失更新（Second Lost Update）：一个事务提交时，把另一个事务提交的数据

   给覆盖了，我们也把它称为提交覆盖。

   

· 像上面提到的，B读了A没提交的数据，而A又回滚了，称为脏读（Dirty Read）：

· 还有别的读取错误的情况，如不可重复读（Non-repeatable Read），即B读，A修改了数据并提交，B再读，值变了，找不回最初的值：

· 还有一种，称之为幻读（Phantom Read），即B读，A增加或减少了数据并提交，B再读，发现数量不一样了，产生了幻觉：

· 注意区分不可重复读和幻读，不可重复读侧重于描述已存在的数据被修改，而幻读描述的是有数据被添加或删除。

· 既然出现了问题，我们就需要有解决方案。主流的DBMS会提供4种事务的隔离等级：

1. 读未提交（Read Uncommited）：可以读到其它事务未提交的数据。

2. 读已提交（Read Commited）：只能读到其它事务已经提交的数据。

3. 可重复读（Repeatable Read）：同一事务范围内读取到的数据是一致的。

4. 可串行化（Serialization）：可以将所有的事务串行执行。

   

并发控制技术

· 那么这些隔离等级要如何实现呢？使用封锁技术！

· 封锁是实现并发控制（Concurrency Control）的其中一种重要技术。

· 事务在对某对象进行操作时，先对这个对象加锁，这样别的事务在锁没释放前都不能碰这个对象，只能等待。

· 一般来说我们会使用两种锁：

1. 读锁，又称共享锁（Share Lock），简称S锁。若T给对象O加S锁，则T对O只能读不能写。

2. 写锁，又称排它锁（Exclusive Lock），简称X锁。若T给对象O加X锁，则T对O又能读又能写。

   

封锁协议

· 在使用锁的时候，我们需要约定一些规则，这些规则称为封锁协议（Locking Protocol）。

· 这些协议需要定义何时申请S或X锁、持续时间、何时释放。

· 一级封锁协议：防止丢失修改。

· 事务T在修改数据A之前必须先给A加上X锁，直到事务结束（COMMIT或ROLLBACK）才能释放。

· 一级封锁协议可防止丢失修改，即我们前面提到的一类和二类丢失更新，并保证了事务T是可恢复的。

· 需要注意的是，在一级封锁协议中，如果只读数据而不修改，是不需要加锁的，因此无法保证可重复读和不脏读。

· 二级封锁协议：不脏读。

· 在一级封锁协议的基础上，要求事务T在读取数据R之前必须给数据R加上S锁，并且读完即可释放。

· 二级封锁协议可以防止丢失修改和脏读，但是因为读完就立刻释放S锁，所以无法保证可重复读。

· 三级封锁协议：可重复读。

· 在一级封锁协议的基础上，要求事务T在读取数据R之前必须给数据R加上S锁，并且事务结束才能释放。

· 三级封锁协议可防止丢失修改、脏读和不可重复读。

· 可以发现，三种封锁协议最主要的区别是何时申请锁以及锁持续时间。协议级别越高，一致性程度就越高。

死锁和活锁

· 产生死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对已为其他事务封锁的数据对象加锁，从而出现死等待。

· 预防死锁有两种办法：

1. 一次封锁法：每个事务必须一次性将所有要使用的数据全部加锁，否则就不能继续执行。

   

   可以看到，T1要使用R1和R2，因此一次申请完了，这样T2就要一直等待T1完成才能获得资源。

2. 顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。但它难以维护且实现困难。

· 既然死锁会出现，那我们也要有相应的诊断方法：

1. 超时法：如果一个事务的等待时间超过了规定的时限，就认为发生了死锁，缺点是有可能误判。

2. 等待图法：若T1等待T2，则T1，T2之间划一条有向边，从T1指向T2，有环则死锁。

   

· 当发现了死锁，那肯定要给它解锁，一般来说选择一个处理死锁代价最小的事务，将其撤消以释放此事务持有的所有的锁，使其它事务能继续运行下去。

可串行化调度

· 我们知道，对于并发事务的不同调度方式有可能产生不同的结果。

· 可串行化调度：串行调度是正确的，且执行结果等同于串行调度的调度，被称为可串行化调度。

· 可串行化是最高的隔离等级，但是性能最低。

· 可串行性：并发事务正确调度的准则。给定的调度是可串行化的，才认为是正确的。

· 那要如何判断一个调度是不是可串行化的呢？

· 首先，定义两种冲突操作：

1. Ri(x) 和 Wj(x) ：事务i读x，事务j写x。即读写冲突，很明显，如果互换两种操作的顺序，那结果会改变。

2. Wi(x) 和 Wj(x) ：事务i写x，事务j写x。即写写冲突，很明显，如果互换两种操作的顺序，那结果会改变。

· 定义：一个调度S如果可以在保持冲突操作顺序不变的情况下，通过交换两个事务不冲突操作的次序，可以得到一个串行调度S’的话，则称调度S是冲突可串行化的。

· 有点抽象，我们看一个例子：

· 这是一个调度，我们来分析T1和T2的冲突操作，顺序如下；

1. R1(A) - W1(A)

2. W1(A) - R2(A)

3. W1(A) - W2(A)

4. R1(B) - W2(B)

5. W1(B) - R2(B)

6. W1(B) - W2(B)

· 然后我们通过不断交换不冲突的操作的次序，得到：

· 分析最后得到的串行调度冲突操作顺序，发现和原来的是一样的，因此原来的调度就是一个可串行化的调度。

· 再来看个例子：

· 分析冲突操作顺序如下：

1. R1(A) - W2(A)

2. W1(A) - W2(A)

3. R1(B) - W2(B)

4. W1(B) - R2(B)

5. W1(B) - W2(B)

· 同理，我们来交换不冲突操作的次序：

· 最后别忘了检查冲突操作的次序，发现和原来的一样，所以原来的调度也是一个可串行化调度。

两段锁协议

· 两段锁协议（Two-phase Locking Protocol, 2PL）是DBMS普遍采用的用于实现并发调度可串行性的方法，从而保证调度的正确性。

· 两段锁协议指的是所有事务必须分两个阶段对数据项进行加锁和解锁。

· 首先，在对任何数据进行读写之前，事务要先对该数据进行加锁，然后，在释放任何一个锁之后，事务不再申请和获得其它加锁。

· 可以看到，第一阶段是扩展阶段，即加锁；第二阶段是收缩阶段，即解锁。

· 如果并发执行的所有事务均遵守2PL，那么这些事务的任何并发调度策略都是可串行化的（充分不必要条件）。

· 值得注意的是，一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议。

· 但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁。

多粒度封锁

· 多粒度封锁指的是系统支持不同“粒度”的数据项的锁定。

· 粒度其实就是对象的大小或级别，一般分为：

1. 数据库级别：整个数据库。

2. 文件或区段级别：数据库中的一个文件或数据区段。

3. 页级别：文件中的单个页。

4. 记录级别：页中的单条记录。

5. 字段级别：记录中的单个字段。

· 封锁粒度与系统的并发度和并发控制的开销密切相关，封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小；封锁的粒度越小，并发度较高，但系统开销也就越大。

· 在多粒度封锁中，上层节点被加锁后，下层节点也会被加锁。

· 上层节点主动加的锁称为显式锁，下层节点自动加的锁称为隐式锁。

· 因此，在给数据对象加锁的时候要检查显式锁是否冲突，显式锁和上层节点封锁造成的隐式锁是否冲突，下级节点的将会具有隐式锁，和他们本身的显式锁冲突。

· 很麻烦，因此为了提高效率，引入意向锁。

· 对一个结点加意向锁，则该结点的下层结点正在被加锁；要给一个结点加锁，先给他上层加意向锁，这样只需检查上层的各种锁和新的意向锁是否冲突即可。

多版本并发控制

· 多版本并发控制（Multi-Version Concurrency Control，MVCC）的核心思想是为每一个读操作提供一致性的数据快照，而不是在实际数据上操作。

· 可以看到，上面的例子中T1写完了A后，MVCC创建了一个快照A‘，T2要读A的时候就只能读A’而不能直接读A。

· 显然，MVCC很好的确保了数据的一致性。

· 事务的隔离性除了使用锁机制，还会使用MVCC来实现。一般来说写写隔离通过锁，读写隔离通过MVCC。

数据库恢复概述

· 事务运行的时候，故障是不可避免的，例如计算机硬件故障、软件错误、人为失误、恶意破坏等。

· 运行事务的非正常中断，会影响数据库中数据的正确性，甚至可能破坏数据库，全部或部分丢失数据。

· 因此，数据库的恢复技术就尤为重要了，DBMS必须具有把数据库从错误状态恢复到某一已知的正确状态（亦称为一致状态或完整状态）的功能，这就是数据库的恢复管理系统对故障的对策。

· 串行事务在DBMS中的数据流动如下，若要写入数据，则要从主内存先写入缓存，再写入磁盘，同理读取数据也要先经过缓存。所有事务共用一个缓存页，但是串行使用。

故障发生的地方

· 事务可能在系统内部发生故障：

1. 逻辑错误：事务由于一些内部原因无法完成，导致回滚。如转账余额不足。

2. 系统错误：由于死锁、运算溢出、未达到预期终点等原因导致DBMS必须终止事务的运行。

3. 主动撤销：不影响其他的事务运行的情况下，回滚事务，撤销事务对数据的更改。

· 可能发生系统级别的故障（软故障），即造成系统停止运转的任何事件，使得系统要重新启动：

1. CPU故障。

2. 操作系统故障。

3. DBMS错误。

4. 突然断电。

· 甚至可能发生介质级别的故障（硬故障），对物理硬件造成破坏，概率小但破坏性大：

1. 磁盘损坏。

2. 磁头碰撞。

3. 强磁场干扰。

· 我们来分析一下这几类故障会造成的影响：

· 既然出现了故障，DBMS就要想办法处理故障，处理的办法就是恢复。

· 恢复：把数据库从当前的不正确状态恢复到已知为正确的某一状态。

· 恢复需要保证事务的原子性和持久性；可以通过重做事务（Redo）和撤销事务（Undo）来恢复故障。

· 重做事务可以保证已提交事务的持久性，撤销事务可以消除未提交事务的影响。

数据库恢复技术

· 我们知道恢复是应对错误的办法，那要如何实现恢复呢？

· 恢复操作的基本原理是冗余，即利用系统存储在别处的冗余数据来重建数据库中已被破坏或不正确的数据。

系统故障的恢复：运行日志

· 要恢复系统级别的故障，如断电等造成的突然停机，需要用到运行日志。

· 运行日志：DBMS维护的一个文件，该文件以流水方式记录了每一个事务对数据库的每一次操作及操作顺序，运行日志直接写入介质存储，会保持正确性，当事务对数据库进行操作时，先写运行日志，写成功后，再与数据库缓冲区进行信息交换。

· 如下图，事务T1想把数据y1写入磁盘的之前，要先写入运行日志。

· 现在我记录了很多天的日志，如果故障发生了，应该从哪个地方恢复呢？答案是检查点（Check Point）。

· DBMS会周期性的去设置检查点，设置了检查点之后，日志缓冲区的日志记录都会被写入磁盘，同时当前在缓冲区内的记录也会写入磁盘，然后在日志上写入检查点记录，在此过程中，不会发生事务更新操作。

· 这样，我们就可以通过检查点来判断一个事务是应该被重做还是应该撤销了。

· 规则：检查点之前结束的不用重做，检查点之后结束的重做，没结束的撤销。

· 可以看到，T1在Tc之前结束了，它没问题，啥也不用做；T2在检查点之后、故障之前结束，此时从检查点到结束那一部分，无法保证数据的完整性，因此需要重做；T3一直到故障发生都还在运行，必然是需要撤销的，T5同理；T4整体在检查点和故障之间，也是重做即可。

· 需要注意的是，日志存入磁盘的频率比数据高得多，所以可以理解为日志其实就是写入磁盘内的，虽然他有个缓冲区，但是写入磁盘内的频率很高！

介质故障点恢复：数据转储

· 转储：为了防止磁盘寄了，那肯定是用另一个磁盘完整地进行备份啦，没开玩笑噢！

· 我们需要设置一个时间点来进行转储，这个点称为转储点。设置转储点的时候需要注意：

1.  过频，影响系统工作效率；过疏，会造成运行日志过大，也影响系统运行性能。

2. 备份转储周期与运行日志的大小密切相关，应注意防止衔接不畅而引起的漏洞。

   

· 对于转储，我们也有两种方式进行：

1. 海量转储：顾名思义，每次都全部转储，特点是恢复时很方便。

2. 增量转储：即只转储上一次转储后更新的数据，适用于数据库很大、事务很繁杂的时候使用。

· 同时，我们还可以规定转储的时候的状态：

1. 静态转储：系统中无事务运行时进行转储，转储期间不允许任何修改或存取活动，特点是操作简单，数据一定一致。

2. 动态转储：转储期间允许对数据库进行存取或修改，特点是数据库可用性高，但难以保证正确有效。并且必须建立日志文件来记录转储期间各事务对数据库进行的修改活动。

   

数据缓冲区的策略

· 不同的缓冲区策略会影响事务的持久性。

· 有如下4种缓冲区策略：

1. Force：内存中的数据最晚在commit的时候写入磁盘。

2. No Steal：不允许把uncommitted事务内存中的数据写入磁盘。

3. No Force：内存中的数据可以一直保留，在commit之后过一段时间再写入磁盘。(此时在系统崩溃的时候可能还没写入到磁盘)

4. Steal：允许把uncommitted事务内存中的数据写入磁盘。(此时若系统在commit之前崩溃时，已经有数据写入到磁盘了，要恢复到崩溃前的状态）

· 可以发现，Steal/No Steal决定了磁盘是否包含uncommitted的数据；Force/No Force决定了磁盘上会不会不包含已经committed的数据。

· 所以磁盘和缓冲区内的内容不一定是一致的！

· 因此，缓冲区的策略会影响我们的恢复策略：

日志

· 日志按顺序记录了事务对数据库的更新操作的文件，文件内包含事务的开始、内容、结束，内容包含哪个事务，哪个对象，旧值，新值（针对增、删、改操作，log不一样）等。

· 注意，永远都是先写日志，再改数据库。

· UNDOLog——撤销日志

· 撤销日志会把<事务、对象、旧值>写入日志，把新值写入磁盘，提交或撤销事务，只保留旧值。

· 要求将事务改变的数据写入磁盘前，不能提交事务。

· 撤销日志的恢复策略如下：

1. 先确定撤销谁：已commit的不管；有start没commit，撤销；有start有rollback，已结束但未完成，撤销；

2. 进行撤销操作：从尾部往前扫描，撤销未完成的事务更改。

   

   如上例子，错误发生在commit前，故整个事务需要撤销，最重要把A和B在磁盘内的值重置为8。

· 撤销日志也需要设置检查点来防止回溯整个日志，有两种设置方法：

1. 静态检查点：周期性设置，设置期间停止接收新的事务，等到所有当前活跃事务提交或终止，并在日志中写入了COMMIT或ROLLBACK记录后，将日志刷新到磁盘，写入日志记录<CKPT>，并再次刷新日志。

2. 非静止检查点：在设置的时候允许新事务的进入，会往日志内写入一条<START CKPT(T1,…,Tk)>，其中T1,…,Tk 是所有活跃的未结束的事务，然后继续正常操作，直到T1...Tk都完成时写入<END CKPT>。

   

· REDOLog——重做日志

· 重做日志会把事务T对数据x的更新v<T,x,v>写入日志，然后把<commit T>写入日志。

· 与UNDOLog的区别：重做日志保留的是新的值。并且是先提交日志，再写入磁盘。

· 重做日志的恢复策略如下：

1.  先确定要重做谁：start了又commit了，重做；start了没commit，不管；start了又rollback，不管。

2. 进行重做操作：从头往后扫描，重做已完成的事务的更改。

· 举个例子，若commit后发生故障，很明显没往磁盘里写东西，那就要重做整个事务，然后把结果写入磁盘。

· 当然，重做日志也是要设置检查点的，我们使用非静止检查点来进行设置，恢复策略如下：

· UNDO/REDOLog——结合型LOG

· 这种Log结合了重做和撤销日志，首先将事务T对数据x从值u到值v的更新<T,x,u,v>写到日志，然后可以选择：

1. 先<commit, T>到日志，再把新的x写入磁盘。

2. 先把新的x写入磁盘，再<commit, T>到日志。

   

   注意上图不是提交两次，是在两个地方都可以提交，但选一个的意思！

· 结合型Log的恢复策略其实还是那样：

1. 先判断对谁动手：有start有commit，已完成就重做；有start无commit，未完成就撤销；有start有rollback，结束但没完成也要撤销。

2. 进行恢复操作：然后从尾部往前扫描，进行恢复即可。

· 我们通过下面的例子来熟悉混合Log：

1. 若整个过程没发生错误，则最后x1，x2，x3的值分别为？

   事务T1T2都对x1做了修改，故最后x1为v0->v1->v2，v2。

2. 若在<ROLLBACK T3>后发生错误，谁要重做，谁要撤销？

   在T3回滚后发生错误，此时T1T2都已经提交，故要重做，T3回滚了，要撤销。

3. 若在<COMMIT T2>后发生错误，谁要重做，谁要撤销？

   在T2提交后发生错误，那T2完成了故重做，T1和T3都未完成，要撤销。

4. 若在<T2, x2, k0, k1>后发生错误，谁要重做，谁要撤销？

   在T2把x2修改后发生错误，此时T1和T2都没提交，未完成，故撤销，但T3根本没开始，故不管。

· 最后我们看一个课本的习题，思路是一样的：