数据库原理-并发控制与恢复

为了保持事务的隔离性,系统必须对并发事务之间的相互作用加以控制,这个机制就是并发控制

本文主要基于期末考试的考纲进行复习,书上的基于时间戳和快照隔离的封锁协议就先不整理了,等寒假整理八股文的时候再好好看看,或者直接看Mysql的实战

1. 基于锁的协议

确保隔离性的方法之一就是要求数据项以互斥的方式进行访问。实现该需求的最常用的方法就是只允许事务访问该事务持有锁(lock)的数据项

1.1 锁

• 共享锁(shared):如果事务Ti获得了数据项Q上的共享型锁(shared-mode lock)(记为S),那么Ti就是可读但不能写这个Q
• 排他锁(exclusive):如果事务Ti获得了数据项Q上的排他型锁(exclusive-mode lock)(记为X),那么Ti就是可读又可写Q的

我们要求每个事务都要根据自己对数据项Q进行的操作类型申请(request)适当的锁,该事务将请求发送给并发控制管理器,事务只有在并发控制管理器授予(grant)所需要的锁之后才能继续其操作。

共享读锁和排他写锁的操作能够保证多个事务读取一个数据项但是限制同时只能有一个事务进行写操作

• 如果数据项Q上存在B类型的锁,但是事务Ti可以立即获得数据项上的锁,那么我们就说A类型锁和B类型锁是相容(compatible)的

lock-S(Q)//申请数据项Q上的共享锁
lock-X(Q)//申请数据项Q上的排它锁
unlock(Q)//释放数据项Q上的锁

要访问一个数据项,Ti必须首先给该数据项加锁,如果该数据项已经被另一个事务加上了不相容的锁,那么在所有其他事务持有的不相容的锁被释放之前,并发控制管理器不会授予Ti关于这个数据项的锁,这个时候,事务Ti就进入了等待(wait)的状态,直到所有其他事务持有的不相容类型的锁被释放

注意,这里是等待而非阻塞状态,那么很有可能在实现原理上是采用乐观锁也就是CAS轮询的机制进行并发控制的,当然不排除实际的执行引擎会采用悲观锁的机制强制阻塞,这里的话留个印象就好

事务Ti可以释放先前加载某个数据项上的锁,一个事务只要还在访问数据项,那么它就必须拥有该数据项上的锁。

此外,让事务在对数据项作最后一次访问(写或者读)后马上释放该数据项上的锁也未必是可取的,因为有可能无法保证可串行性

举一个例子:有如下两个事务:

假设账户A有100而B有200,如果这两个事务串行地执行,以T1、T2或者T2、T2的顺序执行,那么事务T2将会得到300的结果

但是如果两个事务是并发地执行的话,那么就有可能出现以下调度

在这种情况下,T2将会显示出一个错误的结果250,出现这种错误的原因是由于事务T1过早地释放掉了数据项B上的锁,从而导致事务T2看到了一个不一致的状态

这里的话好好读一下这个图,因为考试会考

首先是T1要对B进行read&write,因此申请对B的排他锁,然后并发控制管理器发现你这个B上没有和readB所需要的锁类型不相容的锁,所以直接授权给了T1关于B的排他

然后就执行相关操作,执行完毕后就释放掉这个排他锁

然后是T2要对A执行读操作,因此申请共享锁,然后管理器授权锁

然后是T2要对B执行读操作,因此申请共享锁,然后管理器授权锁

T2执行完之后就释放掉A和B的锁了

然后T1要执行转账操作的下半部分,然后继续申请排他锁,然后授权锁,最终将锁释放。

这个调度显示了事务执行的动作以及并发控制器授权加锁的时刻,申请加锁的事务在并发控制管理器授权加锁之前不能够执行下一个动作。锁的授予必然是在事务申请锁操作与事务的下一动作的间隔内

既然涉及到锁的授予机制,那么就有可能陷入死锁(deadlock),当死锁发生之后,系统必须回滚两个事务中的一个,一旦某个事务回滚了,那么事务锁住的数据项就被解锁了,其他事务就可以访问这些数据项,继续征集的执行。

如果我们不使用封锁或者对数据项进行读写之后立即解锁,那么就有可能导致数据库进入不一致的状态。

如果我们不对当前锁住的数据项解锁,那么就有可能发生死锁。

然而,产生死锁显然比产生不一致的状态要好,因为它们可以通过回滚事务加以解决,而不一致的状态可能引起现实中的问题,这是数据库系统所不能够处理的。

**我们将要求在系统中的每一个事务遵从称为封锁协议(locking protocol)**的一组规则,这些规则规定事务什么时候对数据项进行加锁、解锁。封锁协议限制了可能的调度数目。这些调度组成的集合是所有可能的可串行化调度的一个真子集

书本上这里给出一个定义:

如果有一个事务集中有这些事务{T0,T1,...,Tn}是参与调度S的一个事务集,如果存在数据项Q使得Ti在Q上有一个A型锁,而在之后(注意持有锁的时机),Tj在Q上持有一个B型锁,而且A和B是不相容的,那么我们就说在调度S中,Ti先于(precede)Tj,记录为Ti->Tj,如果Ti->Tj,那么也就意味着在任何等价的串行调度中,Ti必须先出现在Tj之前,和之前检测是否可串行化的方法是类似的。指令之间的冲突对应于锁之间的不相容性

如果调度S是那些遵从封锁协议规则的事务集的可能调度之一,我们就说调度S在给定的封锁协议下是合法的。

当且仅当所有合法的调度为冲突可串行化的时候,我们称一个封锁协议保证冲突的可串行性

1.2 锁的授予

当事务申请对一个数据项加某一个类型的锁的时候,而且没有其他事务在该数据项上加上了与此类型相冲突的锁,那么就可以授予锁。然而,这种锁的授予机制是不确定的,不确定每个事务都能在合适的时候获得锁

类似于读者写者问题中的写者饥饿问题,如果一直有源源不断的读者进入,那么写者就会在很长一段时间内获得不了锁,就会导致写者饥饿

避免事务饥饿的方式:当事务Ti申请对数据项Q加M型锁的时候,并发控制管理器授权加锁的条件是

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

这个就相当于一个控制时序的办法先来先服务,但是缺点也很明显,但事务执行的长短明显的时候,会导致事务的执行效率降低,比如说T1是一个长事务,T2是短事务,T1有10000条语句,T2只有1条语句,T2比T1晚到,所以要等T1执行完才能执行,这个执行效率是很低下的。

1.3 两阶段的封锁协议

保证可串行性的一个协议是两阶段封锁协议(two-phase locking protocol),该协议要求每个事务分为两个阶段提出加锁和解锁申请

• 增长阶段(growing phase):事务可以获得锁,但是不能释放锁
• 缩减阶段(shrinking phase):事务可以释放锁,但是不能获得新锁

对于任何事务,在调度中该事务获获得其最后加锁的位置(增长阶段结束的点)这个点就叫做事务的封锁点(lock point),这样的话,多个事务可以根据它们的封锁点进行排序,实际上,这个顺序就是事务的一个可串行化调度

严格的两阶段封锁协议(strict two-phase locking protocol):这个协议除了要求封锁是两阶段的之外,还要求事务持有的排他锁必须在事务提交之后才可以释放。这个要求保证了未提交事务所写的任何数据在事务提交之前均以排他方式加锁,防止其他事务读这些数据。

严格的两阶段封锁协议的作用主要是为了防止级联回滚。

强两阶段封锁协议(rigorous two-phase locking protocol):它要求事务提交之前不得释放任何锁。在这个协议下,事务可以按照其提交的顺序串行化

例子

如果我们采用的是两阶段封锁协议,那么T8必须对a1加一个排他锁,因此两个事务的任何并发执行方式都相当于串行执行(因为排他锁与其他所不相容),然而这个事务只有在事务结束的时候才执行写操作,于是一种优化思路就是在T8开始要对a1读的时候加一个共享锁,只要在要对a1进行写的时候才变成排他锁,在这样的情况下我们就可以获得更高的并发度,因为这时候T9也可以访问a1了。

锁转换(lock conversion):提供一种将共享锁升级为排他锁以及将排他锁降级为共享锁的机制

• 锁升级(upgrade):表示从共享锁到排他锁的转换
• 锁降级(downgrade):表示从排他锁到共享锁的转换

锁的转换是不能够随意进行的,锁的升级只能发生在增长阶段而锁的降级只能发生在缩减阶段

值得注意的是,锁的转换同样是需要约束的,当另外一个事务对Q持有不相容的锁的时候会导致强制等待。

目前常见的锁申请的过程

• 当事务Ti进行read(Q)的操作时候,系统就会产生一条lock-S(Q),该read(Q)指令紧随其后
• 当事务Ti进行write(Q)的操作的时候,系统先检查Ti是否已经持有一个共享锁了,如果有的话就发出一个upgrade(Q)的指令,后面接一个write(Q)指令,否则系统发出lock-X(Q)指令,后面接write(Q)指令
• 当一个事务提交或者终止之后,该事务持有的所有锁都被释放

1.4 封锁的实现

锁管理器(lock manager)可以实现为一个过程(procedure),它从事务接收消息并反馈消息,它的过程针对锁清秋返回授予锁的消息,或者要求事务回滚的消息(当发生死锁的时候),解锁消息只需要一个确认回答,其后可能会引发其他等待事务额授予锁消息。

锁管理器的数据结构

锁管理器为目前已经加锁的每个数据项维护一个链表,每一个请求就是链表中的一个记录,按照请求到达的顺序排序,它使用一个以数据项名称为索引的散列表来查找链表中的数据项,这个表就叫做锁表(lock table)

这个数据结果其实就是HashMap,哈希表也是基于数组+链表进行实现的,因此Java中对于HashMap的优化对于锁表来说也是可以的,可以将链表转化为红黑树。

数据项的内容:一个数据项的链表中的每一条记录表示由哪个事务提出的请求,以及它请求什么类型的锁,该记录还表示该请求是否以及授予了锁

锁表采用的是溢出表,所谓溢出表,就是当哈希冲突的时候,将同一个数据项插在同一个索引下组织的链表上,而不是重新计算哈希(类似布隆过滤器)的那种操作。每一个数据项下,又有一条链表,这个链表中记录的是已授予锁或者等待授予锁的事务列表

如图所示,已经授予锁的事务用深色阴影方块来进行表示,等待授予锁的事务就用浅色阴影的方块进行表示。

简述锁管理器是如何处理事务请求获得锁的过程

• 当一条锁的请求消息到达的时候,如果相应的数据项的链表存在,那么就在链表末尾增加一个记录,否则就新建一个仅包含该请求记录的链表

在当前没有加锁的数据项上总是授予第一次加锁请求,但是如果事务向已经被加锁的数据项加锁的时候,只有当请求与当前持有的锁相容的时候而且先前所有的请求都已经被授予锁的情况下,锁管理器才为该请求授予锁,否则请求等待

• 当锁管理器收到一个事务的解锁消息的时候,它将与该事务相对应的数据项链表中的记录删除掉,然后检查随后的记录,如果有,那么就看该请求能否被授权,如果能,锁管理器授权该请求并处理其后的记录,如果还有,类似地一个接一个地处理。就是说当解锁了一个数据项之后,检查关于这个数据项的下一个请求,如果这个请求可以授权,那么就授权,否则就继续等待。
• 如果一个事务终止了,那么锁管理器将会删除该事务产生的正在等待加锁的所有请求。

2. 多粒度

某些情况下需要把多个数据项聚集为一组,将它们作为一个同步单元进行处理更好,如果事务Ti需要访问整个数据库,使用的是一种封锁协议,则事务Ti必须给数据库中的每个数据项都加锁,很显然这是很费时的。

但是如果能够只发出单次请求,也就是发出单个封锁整个数据库的加锁请求。

换个角度,如果事务Tj只需要存取少量的数据项,那么我们就不应该要求给真个数据库加锁,否则并发性就会很弱

---

我们需要的是一种允许系统定义多级粒度(granularity)的机制,这通过允许各种大小的数据项并定义数据粒度的层次结构,其中的小粒度数据项嵌套在大粒度数据项中来实现。

这种层次结构可以图形化为树,如图所示,我们看这个图首先要知道,叶子节点放的是真正的单元数据项,而非叶子节点存放的是一种关系,这种关系表示了与其后代相联系的数据。

对于这个图,它由4层节点组成,最高层是DB表示是整个数据库,下面是area类型的节点,数据库恰好就由这些区域组成。然后area之下的是file类型的节点作为子节点,每个区域恰好由作为子节点的文件节点组成,每个文件节点专属于一个区域,而没有任何一个文件处于一个以上的区域中。最后,每个文件由record类型的节点组成。

树中的每个结点都可以单独加锁,正如我们在两阶段封锁协议中所做的那样,我们将使用共享shared锁和排他exclusive锁,当事务对一个节点进行加锁的时候,这个事务也以同样类型的锁隐式地封锁这个节点的全部后代节点。

比如说,有一个事务Ti给Fb显式explicit lock地加排他锁,则事务Ti也给所有属于该文件的记录隐式(implicit lock)地加排他锁,而没有必要显式地给Fb中的每个子节点的单条记录逐个加锁。

加锁的过程

假设现在有一个事务T1,T1希望封锁Fb,因此这时候T1被显式地加锁,而rbn是被隐式地加锁的,然后现在有一个T2,T2希望对Fb下的一条记录rbn进行加锁,这时候,系统会如何判定T2是否能够封锁rbn呢?T2必须从DB到rbn进行遍历,如果发现这个路径上的某个节点的锁与要加的锁类型不相容,那么Tj必须延迟。

注意,这个路径并非全部的路径,而是说是从根节点到目标节点的路径,只要这条路径上任意一个节点的锁和要加的锁的类型不相容,那么必须等待,比如说,T2去封锁rbn的时候,这时候它就会发现路径上一定会经过一个点Fb,这个Fb已经被显式地上了锁了,而且不相容,那么T2就等待

但是这样有没有问题呢?就是说我的初衷是为了减小搜索和遍历的程度,但是现在我要遍历整棵树,这样的话在最坏情况下效率可能还不如原来逐个记录加锁的机制

于是,一种更加有效的方法就是使用意向锁(intention lock mode),如果一个节点加上了意向锁,那么就意味着要在树的较低层进行显式的加锁,这也就是说,以更小的粒度进行加锁。

在一个节点显式加锁之前,该节点的全部祖先节点都加上了意向锁,因此事务不必搜索整棵树就能够判定能否成功地给一个节点加锁,如果希望给某个节点加锁的事务必须遍历从根到Q的路径,在遍历树的过程中,该事务给各节点加上意向锁

与共享锁相关联的是一种意向锁,与排他锁相关联的则是另外一种意向锁

• 如果一个节点加上了共享型意向锁(intention-shared(IS)Mode)锁,那么将在树的较低层进行显式封锁。但是只能加共享锁

• 如果一个节点加上了排他型意向锁(intention-exclusive(IX)Mode)锁,那么也只是数的较低层进行显式封锁,可以在排他锁或者共享锁。

• 如果一个节点加上了共享排他型意向锁(shared and intention-exclusive(SIX)Mode),那么以该节点为根的子树就显式地加了共享锁,并且在树的更底层加排他锁。

这三种意向锁,前面两种锁很好理解,其实就是在节点上加对应的锁,只不过排他型的意向锁可以对于底层节点多一种选择而已(可以联想前面的锁转换机制)

第三种意向锁比较绕,如果一个节点还有子节点的话,那么加上第三种锁的话就是把这一整颗树(以加上共享锁,然后这棵树的底层加上一个排他锁。

多粒度封锁协议(multiple-granularity locking protocol):采用这些锁类型保证可串行性,每个事务按照以下规则对Q进行加锁

1. 事务必须遵从相容性矩阵
2. 事务必须首先封锁数的根节点,然后加任意类型的锁
3. 仅当事务对Q的父节点具有IX锁或者IS锁的时候,事务才能对节点Q加S锁或者IS锁,如果持有父节点的意向排他锁/共享锁,那么肯定可以上共享锁,或者上一个意向共享锁
4. 仅当事务对Q的父节点具有IX或者SIX锁的时候,事务可以对Q上排他锁、意向排他锁、意向排他共享锁
5. 仅当事务未曾对任何节点解锁的时候,事务才可以对节点进行加锁(这个事务要遵循两阶段的封锁协议)
6. 仅当事务不持有Q的子节点的锁的时候,才可以对节点Q解锁

多粒度封锁协议要求加锁按照自顶向下的顺序(由根到叶子),而对于锁的释放那么就要按照自底向上的顺序进行回放(由叶子到根)

为什么要这样做?

这是为了提高性能以及避免错误,首先梳理一下加锁的过程

我们假设上第一把锁,对记录rb1进行上排他锁,然后这时候就会从根节点出发,首先给根节点上一个意向排他锁,然后对路径上的area上一个意向排他锁，然后对路径上的file上一个意向排他锁,最终到子节点上一个排他锁,然后这时候就可以开始对数据进行操作了。

加锁的这个过程是自顶向上的,这时候如果来了第二把锁,想对我们刚才路径上的file上一个排他锁/共享锁,然后它走到file的时候,发现已经上了意向排他锁了,所以的话就压根不用走到记录的那一层就知道这个上锁肯定是失败的。因此提高了性能。

然后操作完成之后,就要开始解锁,解锁的过程是自底向上的,这是为了防止意向锁的约束被破坏,比如说,事务A要对记录rb1上一个共享锁,然后这时候同时地会对路径上的file和area都上意向共享锁,在这个情况下,事务A又来一个操作,想要对file上一个共享锁,这个上锁是可以成功的。

但是在后来的解锁中,我们只是想要解file的共享锁,我们假设我们自顶向下解锁,这时候就会把area和DB的意向锁都排除掉了,这样的话如果后面有人想对file比如上排他锁之类的也能上的,这时候就会导致错误。

但是这时候会有个问题,如果这样的话,子节点的锁不释放,父节点的锁也不能释放,这样不会导致并发度降低吗?这是会的,然而为了并发控制的安全,这个必须要做。否则的话会产生数据的不一致。

3. 故障的分类

• 事务故障(transaction failure)
  • 逻辑错误(logical error):事务由于某些内部条件而无法继续正常执行,如非法输入等
  • 系统错误system error:系统进入一种不良的状态(如死锁),结果事务无法继续正常执行,但是该事务可以在以后的某个时间重新执行
• 系统崩溃(system crash):硬件故障,数据库软件或者操作系统的漏洞,导致易失性存储器内容的丢失,并使得事务处理停止了,而非易失性存储依然完好无损
• 磁盘故障(disk failure):在数据传送过程中,由于磁头损坏或者故障造成磁盘块上的内容丢失

4.稳定存储器的实现

需要在多个非易失性存储介质(通常是磁盘)上以独立的故障模式复制所需要的信息,并且以受控的方式更新信息,以保证数据传送过程中发送的故障不会破坏所需要的信息。

• 成功完成(successful completion):传送的信息安全地到达目的地
• 部分失败(partial failure):传送过程中发生故障,目标块有不正确的信息
• 完全失败(total failure):传送搓成中故障发生地足够早,目标块完好无缺

为了达到稳定性存储的要求,系统必须为每个逻辑数据库块维护两个物理块

• 将信息写入第一个无物理块
• 当第一次写成功完成的时候,将相同信息写入第二个物理块
• 只有对第二次写成功完成的时候,输出才算完成

5. 数据访问

数据库系统常驻于非易失性存储器(通常为磁盘),在任何时刻都只有数据库的部分内容存在主存中。

数据库分成称为块(block)的定长存储单位,块是磁盘数据传送的单位,可能包含有多个数据项。

事务由磁盘向主存输入信息,任何再将信息输出回去磁盘,输入和输出的操作以块为单位完成

• 位于磁盘上的块叫做物理块(physical block)
• 内存中用于临时存放块的区域叫做磁盘缓冲区(disk buffer)

磁盘和主存间的块移动是由下面两个操作引发的

• input(B):传送物理块B到主存中
• output(B):传送缓冲块到磁盘中,并替换磁盘上相应的物理块

在概念上,每个事务Ti都具有一个私有的工作区,用于保存Ti所访问以及更新的所有的数据项的拷贝,这个工作区在事务初始化的时候由系统创建,在事务提交或者终止的时候由系统删除,事务Ti的工作区中保存的每一个数据项X记为xi,事务Ti通过在其工作区和系统缓冲区之间传送数据,与数据库系统进行交互

这个私有工作区就很像JMM中的工作区的概念

• read(X):将数据项X的值赋予局部变量xi
  • 如果X所在块Bx不在主存中,则就发指令input(Bx)
  • 将缓冲区块中的X的值赋予xi
• write(X):将局部变量xi的值赋予缓冲块中的数据项X
  • 若X所在块不在主存中,那么就发指令input(Bx)
  • 将xi的值赋予缓冲块Bx中的X

注意以上的两个操作都可能需要将块从磁盘中传送到主存中,但是它们都没有特别指明需要从块传送到磁盘中

缓冲块最终写到磁盘上要么是因为缓冲区管理处于其他用途需要内存空间,要么是因为数据库系统将B的变化反映到磁盘上,如果数据库系统发指令执行output(B),那么我们就说数据库系统对缓冲块B进行强制输出

当事务第一次需要访问X的时候,必须执行read(X),然后此后的操作都是基于私有工作区做的。

对X所在的缓冲块Bx的output(Bx)不需要在write(X)执行后立即执行,因为块Bx可能包含有其他依然在被访问的数据项,因此可能在一段时间后才真正执行输出.

注意在write(X)操作执行后但在output(Bx)操作执行前崩溃,X的新值没有写入磁盘,于是就丢失了X的新值。

6. 恢复与原子性

对于的事务的工作流程,我们希望Ti对数据库的所有修改,要么都不执行,但是如果Ti执行多处的数据库修改,就可能需要多个输出操作,并且故障可能发生在某些修改完成后而全部修改完成前。

为了保持原子性的目标,我们必须在修改数据库本身之前,首先向稳定存储器输出信息,描述要做的修改。这种信息能够帮助我们已提交事务所做的所有修改都反映到数据库中(或者在故障后的恢复过程反映到数据库中),这种信息还能帮助我们确保中止事务所做的任何修改都不会持久存在于数据库中。

6.1 日志记录

日志是日志记录(log record)的序列,它记录了数据库中的所有更新活动

更新日志记录(update log record)描述一次数据库写操作,具有如下的几个字段

• 事务标识(transaction identifier):执行write操作事务的唯一标识
• 数据项标识(data-item identifier):是所写数据项的唯一标识。通常是数据项在磁盘上的位置.包括数据项所驻留的块的块标识和块内偏移量
• 旧值(old value):是数据项的写前值
• 新值(new value):是数据项的写后值

将一个更新日志记录表示为<Ti,Xj,V1,V2>表明事务Ti对数据项Xj执行了一个写操作,写操作前Xj的值是V1,写操作后Xj的值是V2。其他专门的日志记录用于记录事务处理过程中的重要事件,比如说事务的开始以及事务的提交或者中止,以下是一些日志记录类型

• <Ti start>:事务Ti开始
• <Ti commit>:事务Ti提交
• <Ti abort>:事务Ti中止

每次事务执行写操作的时候,必须要在数据库修改前建立该次写操作的的日志记录并把它加入到日志中,一旦日志记录已经存在了,就可以根据需要将修改输出到数据库中,并且我们有能力撤销已经输出到数据库中的修改,这是利用日志记录中的旧值字段来做的。

为了从系统故障和磁盘故障中恢复时能使用日志记录,日志必须存放在稳定存储器中。

假设每一个日志记录创建后立即写入稳定存储器中的日志尾部,那么在这种情况下日志就包含了所有的数据库活动的完整记录,因此日志中存储的数据量会非常大

6.2 数据库修改

日志记录使得系统在事务必须中止的情况下能够对事务所做的修改进行撤销,并且在事务已经提交但是在修改已存放到磁盘上的数据库中之前，系统崩溃的情况下能够对事务所做的修改进行重做。

• 事务在主存中对自己私有的部分执行某些计算
• 事务修改主存中磁盘缓冲区中包含该数据项的数据块
• 数据库系统执行output操作,将数据块写到磁盘中

如果一个事务执行了对磁盘缓冲区或者磁盘自身的更新,我们就说这个事务修改了数据库,而对事务在主存中对自己私有的部分进行的更新不算数据库的修改。

• 如果一个事务直到它提交的时候都没有修改数据库,我们就说它采用了延迟修改(deferred-modification)。
• 如果数据库修改在事务仍然活跃的时候发生,我们就说它采用了立即修改(immediate-modification)

延迟修改所付出的开销是,事务必须创建更新过的所有数据项的本地拷贝,如果一个事务读它更新过的数据项,它必须从自己的本地拷贝中读取。也就是说在从私有工作区中创建一份拷贝,这份拷贝存在本地主存中。

恢复算法必须考虑的因素

• 有可能一个事务已经提交了,虽然它所做的某些数据库修改还仅仅存在于主存的磁盘缓冲区中,而不在磁盘上的数据库上
• 有可能处于活动状态的一个事务已经修改了数据库,而作为后来发生的故障的结果,这个事务必须要终止

由于所有的数据库修改之前必须建立日志记录,因此系统有数据项修改前的旧值和要写给数据项的新值可以用,这就使得系统能够执行适当的undo和redo操作

• undo:使用一个日志记录,将该日志记录中指明的数据项设置为旧值
• redo:使用一个日志记录,将该日志中记录中指明的数据项设置为新值

6.3 并发控制和恢复

如果并发控制允许一个事务T1修改过的数据项X在T1提交之前,由另一个事务T2修改了这个数据项,那么通过将X重置为它的旧值(也就是T1更新X之前的那个值),来撤销T1的这一次对X的操作,那么顺带就会把T2这个事务的修改也给撤销掉。基于这个情况考虑,在事务提交或者中止前不允许其他事务修改这个数据项

这个需求的实现方式有:

• 严格的两阶段协议
• 在更新数据项之前获取排他锁
• 快照隔离技术

6.4 事务的提交

当一个事务的commit日志记录表明这是该事务的最后一个日志记录输出到了稳定存储器之后了,这个时间点就说这个事务提交了。

如果系统崩溃发生在日志记录<Ti commit>输出到稳定存储器之前,那么事务Ti即将回滚,这样,包含commit日志记录的块的输出是单个原子动作, 这样的话就能够保证并发的安全,最终事务就提交上去了。

6.5 使用日志来重做和撤销事务

考虑事务T0和,T1描述如下

T0:
read(A);
A:= A-50;
write(A);
read(B);
B: B+50;
write(B);
T1：
read(C);
C:= C-100;
write(C);

一个可能的日志记录信息如下

<T0 start>#事务起始标志
<T0,A,1000,950>#更新日志,事务T0对数据项A进行操作,旧值为1000,新值是950
<T0,B,2000,2050>#更新日志,事务T0对数据项B进行操作,旧值为2000,新值是2050
<T0 commit>#日志记录输出到稳定存储器
<T1 start>#事务起始标志
<T1,C,700,600>#更新日志,事务T1对数据项C进行操作,旧值为700,新值为600
<T1 commit>#事务提交

• redo(Ti):将事务Ti更新过的所有数据项的值都修改为新值

通过redo来执行更新的顺序是很重要的,当从系统崩溃中恢复的时候,如果对于一个特定数据项的多个更新的执行顺序,不同于它们原来的执行顺序,那么这个数据项的最终状态就是一个错误的值。

恢复算法通常是这样做的,对日志进行一次扫描,在扫描的过程中每遇到一个redo日志就执行redo动作,这种方法能够确保更新的顺序。

• undo(Ti):将事务Ti更新过的所有与数据项都恢复成旧值

undo操作不仅将数据项恢复成它的旧值,而且作为撤销过程的一个部分,它本身这个操作还需要写日志记录下来记录所更新的数据, 这些日志记录是特殊的redo-only日志记录,因为它们不需要包含所更新的数据项的旧值

当事务Ti的undo操作完成后,它会写一个<Ti abort>日志记录,表明撤销完成了

系统查阅日志为保证原子性,需要对哪些事务进行重做,对哪些事务进行撤销

• 如果日志包含了<Ti start>记录,但是不包含<Ti commit>,也不包含<Ti abort>记录,那么就需要对事务Ti进行撤销
• 如果日志包含了<Ti start>记录以及<Ti commit>或者<Ti abort>记录,那么就需要对事务Ti进行重做,如果日志包含有<Ti abort>记录的话,还要进行重做。这其实是一种冗余,因为如果这样的这样干脆不做不就好了吗?但是实际情况是这样的,为了做到日志处理算法的统一性,简化恢复算法,干脆就对于这种情况一视同仁,把它看作是普通的重做日志,这是因为日志中会有undo操作所写的那些redo-only日志记录。最终这种情况会导致Ti所做的修改会被撤销。

我们回到上面所说的那个例子,我们假设崩溃恰好发生在事务T0的write(B)

步骤的日志记录已经写到了稳定存储器之后,当系统重新启动的时候,它在日志中找到记录<T0 start>但是没有相应的<T0 commit>或者<T0 abort>的记录,这样的话事务T0必须撤销,于是执行undo(T0),其结果是,磁盘上账户A和账户B的值分别恢复

<T0 start>#事务起始标志
<T0,A,1000,950>#更新日志,事务T0对数据项A进行操作,旧值为1000,新值是950
<T0,B,2000,2050>#更新日志,事务T0对数据项B进行操作,旧值为2000,新值是2050
#缺少了commit或者abort!需要撤销这个事务,于是根据日志做undo(T0)

假设崩溃恰好发生在事务T1的write(C)

这时候的日志体现为

<T0 start>#事务起始标志
<T0,A,1000,950>#更新日志,事务T0对数据项A进行操作,旧值为1000,新值是950
<T0,B,2000,2050>#更新日志,事务T0对数据项B进行操作,旧值为2000,新值是2050
<T0 commit>#日志记录输出到稳定存储器
<T1 start>#事务起始标志
<T1,C,700,600>#更新日志,事务T1对数据项C进行操作,旧值为700,新值为600

在这个情况下,T0有完整的start和commit,而T1没有,因此对T0做redo而对T1做undo

假设崩溃恰好发生在事务T1记录<T1 commit>之后,那么

<T0 start>#事务起始标志
<T0,A,1000,950>#更新日志,事务T0对数据项A进行操作,旧值为1000,新值是950
<T0,B,2000,2050>#更新日志,事务T0对数据项B进行操作,旧值为2000,新值是2050
<T0 commit>#日志记录输出到稳定存储器
<T1 start>#事务起始标志
<T1,C,700,600>#更新日志,事务T1对数据项C进行操作,旧值为700,新值为600
<T1 commit>#事务提交

这时候我们发生T1和T0的要素都是键全的,因此直接做redo

6.6 检查点(checkpoint)

当系统故障发生的时候,我们必须检查日志,决定哪些事务需要重做,哪些事务需要撤销,为了降低这种开销,引入了检查点,检查点的生成特点:

• 在执行检查点操作的过程不允许执行任何的更新
• 在执行检查点的过程中将所有更新过的缓冲块都输出到磁盘

检查点的执行过程

• 将当前位于主存的所有日志记录输出到稳定存储器
• 将所有修改的缓冲块输出到磁盘
• 将一个日志记录<checkpoint L>输出到稳定存储器,其中L是执行检查点时正活跃的事务的列表

在系统发生崩溃的之后,系统检查日志然后找到最后一条checkpoint L记录,这可以通过从尾端开始反向搜索日志来进行,知道遇到第一条checkpoint L的日志

然后我们只需要对L中的事务,以及<checkpoint L>记录写到日志之后才开始执行的事务进行undo或者redo操作。将这个事务集合称为T

• 对T中的所有事务Tk，如果日志中没有commit或者abort,那么就执行undo
• 对T中的所有事务Tk,如果有commit/abort,那么就执行redo

注意:要找出事务集合T中是否含有commit或者abort出现在日志中,只需要从最后一条checkpoint日志记录开始的部分开始找即可

7.恢复算法

7.1 事务是怎么回滚的?

考虑正常操作的时候的事务回滚,执行过程:

对于Ti的每一个形如<Ti,Xj,V1,V2>

• 值V1被写入到数据项Xj中
• 往日志中写一个特殊的只读(read-only)日志记录<Ti,Xj,V1>,其中V1是在本次回滚中数据项Xj恢复成的值,有时候这种日志叫做补偿日志记录(compensation log record),这样的日志记录不需要undo,因此我们看到这个日志没有记录旧值,因为们不会需要撤销这样的undo操作
• 一旦发现了<Ti,start>的日志记录,就停止从后往前的扫描,然后往日志的尾部写入一个<Ti,abort>

这个过程中,事务所做的或者我们为事务所做的每一个更新动作,包括将数据项恢复成其旧值的动作都记录到日志中了

7.2 系统崩溃之后是怎么恢复的?

恢复节点分为两阶段

重做阶段

系统通过从最后一个检查点开始正向地扫描日志来replay所有的事务的更新,replay的日志记录包括在系统崩溃之前已回滚的事务的日志记录和在系统崩溃发生的时候还没有提交的事务的日志记录

扫描日志的过程所做的具体步骤

• 将要回滚的事务的列表undo-list初始化设定为<checkpointL>日志记录中的L列表
• 一旦遇到形如<Ti,Xj,V1,V2>的正常日志记录或者形如<Ti,Xj,V2>的read-only日志记录,那么重做这个操作,也就是说将值V2赋给数据项Xj
• 一旦发现形如<Ti,start>的日志记录,就把Ti加到undolist中
• 一旦发现形如<Ti,abort>或者<Ti,commit>的日志记录,就把它从undo-list中删除掉

在redo阶段的末尾,undo-list包括有在系统崩溃之前还没有完成的所有事务,然后就要把这些事务给撤销掉

撤销阶段

撤销将会回滚在上一阶段留下来的所有事务,这时候从尾端开始反向扫描日志执行回滚

• 一旦发现属于undo-list中的事务的日志记录,就会执行undo操作
• 当系统发现undo-list中的事务Ti的<Ti,start>的记录,那么它就往日志中写一个<Ti,abort>,表明事务回滚完成,然后把Ti从undo-list中删除
• 一旦undo-list称为空表,那么撤销阶段结束

例子