数据库系统(9):事务管理

        DBMS应该具备的功能中,有三个密切相关的功能,用以保证数据库的可靠性和一致性,即事务支持、并发控制服务和恢复服务。它们之间是相互依赖的。并发控制和恢复主要用于保护数据库,避免数据库发生数据不一致或者数据丢失。许多DBMS都允许用户对数据库进行并发操作。如果对这些操作不加控制,对数据库的访问将互相干扰,使得数据库出现不一致的情况。为了解决这个问题,DBMS实现了并发控制 ( $concurrency\ \ control$ ) 协议,来阻止数据库访问之间的相互干扰。数据库恢复 ( $Database\ \ recovery$ ) 是指在故障以后将数据库还原到正确状态的过程。

1. 支持事务处理

        事务 ( $Transaction$ ) 是由单个用户或者应用程序执行的,完成读取或者更新数据库内容的一个或者一串操作。事务是数据库的逻辑操作单位 ( $logical\ \ unit\ \ of\ \ work$ ) 。它可以是整个程序、部分程序或者一条命令,也可以是涉及数据库的任意多个操作。从数据库的角度来看,应用程序的一次执行就是一个事务或者多个事务,若看成多个事务,在事务与事务之间只会出现非数据库操作。复杂的事务由很多操作构成。若并非所有操作都被执行,那么可能会出现不一致状态 ( $inconsistent\ \ state$ ) 。在事务处理过程中,尽管我们允许数据库的一致性遭到暂时破坏,但是事务应该总是能将数据库从一种一致的状态转移到另一种一致的状态。
        事务可能有以下两种结果中的一种。如果执行成功,也就是说事务最终被提交 ( $committed$ ),数据库也将到达一种新的一致状态。另一种情况下,事务没有执行成功,则会被撤销 ( $aborted$ )。如果事务被撤销,则数据库必须要还原到事务开始之前的一致的状态。我们称这样的事务被回滚 ( $rolled\ \ back$ ) /撤销 ( $undone$ )。已经提交的事务无法撤销。如果发现已提交的事务存在错误,必须执行另一个补偿事务 ( $compensating\ \ transaction$ ) 来消除该事务已经产生的影响。
        DBMS无法得知哪些更新操作将被组合在一起以构成一个独立的逻辑事务。因此很多数据操作语言中都使用关键字 $BEGIN$, $TRANSACTION$, $COMMIT$, $ROLLBACK$ 来划定界限。如果不使用,通常会将整个程序视为一个事务。

事务的状态转移图

1.1 事务的性质

  1. 原子性 ( $Atomicity$ ):事务是一个不可分割的单元,要么全执行,要么全不执行。事务的原子性由DBMS的恢复子系统负责保证。
  2. 一致性 ( $Consistency$ ):事务必须将数据库从一种一致的状态转换到另一种一致的状态。事务的一致性是由DBMS和应用程序的开发者共同保证的。DBMS可以通过强制实施所有在数据库模式中定义的约束(如完整性约束和企业自定义约束)来保证一致性。
  3. 隔离性 ( $Isolation$ ):事务的执行是相互独立的,即未完成事务的中间结果对其他事务来说应该是不可见的。事务的隔离性由并发控制子系统负责保证。
  4. 持久性 ( $Durability$ ):成功完成的事务的结果要永久地记录在数据库中。事务的持久性由恢复子系统负责保证。

1.2 数据库体系结构

DBMS事务子系统

        事务管理器 ( $Transaction\ \ manager$ ) 代表应用程序协调事务的处理。事务管理器与调度 ( $scheduler$ ) 模块进行通信,后者负责实现某种并发控制策略。如果并发控制协议指的是基于锁机制的并发控制协议,则调度程序有时候也被看成是锁管理器 ( $lock\ \ manager$ )。调度程序的目标是在不允许并发事务互相干扰的前提下最大限度地提高事务的并发度,当然要牺牲一些完整性或一致性。如果事务在处理过程中发生故障,恢复管理器 ( $recovery\ \ manager$ ) 负责将数据库恢复到事务开始前的状态,使得数据库重新处于一致状态。最后,缓冲区管理器 ( $buffer\ \ manager$ ) 负责在磁盘存储器和主存间高效地传输数据。

2. 并发控制

        并发控制 ( $Concurrency\ \ control$ ) 是管理数据库上的并发操作以使之互不冲突的过程。

2.1 并发控制的必要性

        并发数据库的一个主要目标就是使得多个用户能够并发地访问共享数据。这个目标和多用户计算机系统的目标类似。系统执行第一个事务,进行到I/O操作时,CPU挂起第一个事务并开始执行第二个事务的操作,此时第一个事务的I/O操作由子系统执行。当第二个事务也进行到I/O操作时,CPU控制返回第一个事务,从之前被挂起的地方起执行,如此重复。通过这种方法,两个事务的操作互相重叠 ( $interleaved$ ),并发执行,提高了系统吞吐量 ( $throughput$ ) ,即在给定时间间隔内完成的工作量。
        虽然两个事务各自执行时是完全正确的,但是这种重叠方式却可能产生不正确的结果。可能导致三种问题:丢失更新问题 ( $lost\ \ update\ \ problem$ )、未提交依赖问题 ( $uncommitted\ \ dependency\ \ problem$ ) 和不一致分析问题 ( $inconsistent\ \ analysis\ \ problem$ )。

2.1.1 丢失更新问题

        一位用户的更新操作已经完成,结果却被另一位用户取代了,这就是丢失更新问题。假设存在两个事务,这两个事务都对 $A$ 执行读写操作。$T_1$, $T_2$ 在读取 $A$ 之后进行了一系列操作,最终依次写入。但实际上最终 $A$ 的值是只经过了后者操作的值,即 $T_1$ 的操作被忽略了。该问题可以通过锁机制避免。

2.1.2 未提交依赖问题

        如果允许一个事务看到另外一个未提交事务的中间结果,就会出现未提交依赖问题。假设存在两个事务,前者被撤销,但是在被撤销之前,后者读取到了前者中间过程的数据,就会产生未提交依赖问题。读取到的数据被称为脏数据 ( $dirty\ \ data$ ),该问题也因此被称为污读问题 ( $dirty\ \ read\ \ problem$ )。

2.1.3 不一致分析问题

        上述两个问题都发生在事务试图更新数据库,并且它们在操作上互相干扰的情况。然而即使是对数据库进行只读操作的事务也可能产生不正确的结果。当某事务从数据库中读取多个数据的值时,另一个事务在读取过程中修改了某些数据的值,就会出现不一致分析问题。这个问题有时也被称为不可重 ( $nonrepeatable$ )/模糊 ( $fuzzy$ ) 问题。还有一种类似问题,如果事务执行某一次查询,稍后再执行这次查询,却发现这次查询的集合中包含了其他幻象 ( $phantom$ ) 元组,即另一个事务插入的元组。这个问题有时也被称为幻读 ( $phantom\ \ read$ )。

2.2 可串行性与可恢复性

        并发控制协议的目标就是以一种避免事务之间相互干扰的方式对事务进行调度,从而防止前一节讲述的各种问题的发生。调度 ( $Schedule$ ) 是一组并发事务操作的序列,对于其中每个事务来说,该序列保留了该事务的所有操作的先后次序。调度 $S$ 由 $n$ 个事务组成,对于其中的每一个事务来说,其操作的先后次序与它们出现在 $S$ 的先后次序一样。串行调度 ( $Serial\ \ schedule$ ) 每一个事务的操作都按顺序执行且各事务之间的操作没有任何交叉的调度。非串行调度 ( $Nonserial\ \ schedule$ ) 是一组并发事务的操作相互交叉执行的调度。串行执行能够避免以上三个问题的出现。不管先择哪一种串行调度,都不会使数据库出现不一致状态。所有的串行执行都被认为是正确的。可串行性 ( $serializability$ ) 的目标就是寻找既能使事务并发执行又互不干扰的非串行调度,从而产生一个能由串行执行产生的数据库状态。
        如果一组事务并发执行,当且仅当(非串行)调度能够产生和某些串行执行相同的结果时,调度才是正确的,这样的调度就被称为可串行化 ( $serializable$ ) 的。为了避免由事务相互冲突产生的不一致性,必须保证并发事务的可串行化。在可串行化问题中,读写操作的次序非常重要:

等价调度

        调度 $S_3$ 是串行调度,而 $S_1$, $S_2$ 与 $S_3$ 等价,所以它们都是可串行化的调度。这种类型的可串行化被称为冲突可串行化 ( $conflict\ \ serializability$ ) 。冲突可串行调度中所有冲突操作的执行次序与其在某些串行调度中的执行次序相同。
        冲突可串行化的检测,在限定写规则下,总能产生一个优先图 ( $precedence\ \ graph$ ) 或称串行化图 ( $serialization\ \ graph$ ),用于检测调度是否为冲突可串行的。对于调度 $S$ ,其优先图是一个有向图 $G = (N, E)$,$G$ 由节点的集合 $N$ 和有向边的集合 $E$ 构成,构造方法如下:

        如果存在 $T_i \rightarrow T_j$ 的边,则在任何与 $S$ 等价的串行调度中, $T_i$ 都必须出现在 $T_j$ 之前。如果 $S$ 中有环存在,则调度非冲突可串行。
        假设调度中每一个事务都不失败,则可串行化就标识出那些能够维护数据库一致性的调度。从另一方面看,我们还需对调度中的事务的可恢复性进行分析。如果事务失败,事务的原子性要求我们必须撤销事务对数据库造成的所有影响。而持久性要求一旦提交后,事务对数据库的所有修改不能被撤销。可恢复调度 ( $Recoverable\ \ schedule$ ) 指的是如果 $T_j$ 读取了由 $T_i$ 修改过的数据项,那么事务 $T_i$ 的提交操作应该在事务 $T_j$ 的提交操作之前。若调度中的每一对事务 $T_i$ 和 $T_j$ 都能满足上述要求,则该调度称为可恢复调度。
        串行化可以通过多种方法实现。允许事务安全地并发执行并且满足某些约束的并发控制技术主要有两种:加锁和时间戳方法。这两个方法本质上是保守 ( $conservative$ )/悲观 ( $pessimistic$ ) 方法。相反的,也存在乐观 ( $optimistic$ ) 方法,但都基于冲突出现的概率很小的前提下。

2.3 加锁方法

        加锁 ( $Locking$ ) 用来控制并发访问数据的过程。当一个事务正在访问数据库时,可以用锁拒绝其他事务的访问请求,从而避免产生不正确的结果。加锁是使用最广泛的、能够保证并发事务可串行化的方法。基本特征是在事务对数据库进行读写操作时必须获取一个共享 ( $shared$ ) (读)锁或者互斥 ( $exclusive$ ) (写)锁。 ( $Lock$ ) 可以阻止其他事务修改该事务正在操作的数据项。如果在数据上加了共享锁,则事务只能读不能写。如果事务在数据项上加了互斥锁,则事务可以读写。
        所有的数据项,包括数据库,都能被加锁。数据项的范围决定了锁的细度,即粒度 ( $granularity$ )。多个事务可以同时拥有同一数据项的共享锁。但当一个事务拥有了互斥锁时,其他事务都无法对数据进行读写。
        为了保证可串行化,必须遵循两段锁 ( $two-Phase\ \ phase$, $2PL$ ) 协议。2PL要求事务中所有的加锁操作都出现在第一个解锁操作之前。根据该规则,每个事务可以分为两个阶段:扩展阶段 ( $growing\ \ phase$ ) 和收缩阶段 ( $shrinking\ \ phase$ )。在扩展阶段,事务可以获取全部需要的锁,不能释放锁。在收缩阶段,事务可以释放所有锁,不能获取锁。从共享锁升级 ( $upgrade$ ) 为互斥锁必须进行在扩展阶段,从互斥锁降级 ( $downgrade$ ) 为共享锁必须进行在收缩阶段。
        当存在多个事务之间互相相关,即之前事务中修改的某个值要用于之后的事务时,由于一个事务引发的一连串回滚的现象被称为级联回滚 ( $cascading\ \ rollback$ )。级联回滚意味着大量的工作被撤销,因此需要设计一种协议进行避免。在2PL中,可以通过将收缩阶段放在事务的最后,这种方式称为严格 ( $rigorous$ ) 2PL。若事务遵循严格2PL,则事务按其提交的顺序被串行化。弱严格 ( $Strict$ ) 2PL2PL的另一种变形,只要求互斥锁在最后释放。大多数数据库系统实现的是这两种中的一种。
        还有一种与加锁机制有关的问题即死锁 ( $deadlock$ ) 问题。如果两个事务互相等待对方持有的数据项上的锁,则会产生死锁问题。事务也可能处于活锁 ( $livelock$ ) 状态,即未出现死锁仍无限等待的状态。这时等待算法不公平产生的问题,可以通过优化优先级系统解决。

2.4 死锁

        死锁是两个(或多个)事务互相等待对方释放自己已经占有的锁。一旦发生死锁,相关应用程序并不能解决。唯一一种打破死锁的方法就是撤销其中一个或者多个事务。常用的死锁处理技术有三种:超时、死锁预防与死锁检测和修复。

2.4.1 超时

        超时 ( $Timeouts$ ) 是指每个请求加锁的事务的等待时间都有一个上限。如果在这个上限时间内没有获得锁,则请求超时,事务会被撤销,并自动重启。

2.4.2 死锁预防

        死锁预防 ( $Deadlock\ \ prevention$ ) 是指DBMS总是提前判断是否有事务会引发死锁,与其他方法相比,它的难度要大得多。这种方法为每个事务加上了时间戳。有两种死锁预防算法。第一种为 $Wait-Die$ ,它只允许一个较老的事务等待一个较新的事务,否则事务被撤销,以相同的时间戳启动。最终该事务会变成最老的事务,并且不会再被撤销。第二种算法是 $Wound-Wait$ ,它只允许一个较新的事务等待一个较老的事务,否则新事物会被撤销。
        保守的 ( $conservative$ ) 2PL也能预防死锁。事务在开始时必须获得全部锁,否则就进入等待状态。但问题是事务在启动前并不能知道要获取哪些锁,因此该协议没有得到应用。

2.4.3 死锁检测

        死锁检测 ( $Deadlock\ \ detection$ ) 是指DBMS允许死锁,但是能够发现和打破死锁。死锁检测通常通过构造显示事务之间依赖关系的等待图 ( $Wait-For\ \ Graph$, $WFG$ ) 进行。WFG是一个有向图 $G = (N, E)$ ,由一组节点和一组有向边构成。构造规则如下:

        当且仅当WFG中有环时才会发生死锁。死锁检测算法可以周期性地生成等待图并检测环的存在。周期可以固定,也可以动态设置:当未检测到死锁时,周期增大,反之减小。

2.5 数据项的粒度

        粒度指的是受到保护的数据项的大小,是并发控制协议中受到保护的基本单位。粗粒度是指较大数据项,细粒度是指比较小的数据项。数据项的粒度越粗,并发程度越低。另一方面,粒度越细,则锁的信息越多。最佳大小应根据事务性质决定。

2.5.1 粒度的层次

        我们可以用层次结构表示锁的粒度。

加锁的层次图

        每个节点代表一种数据项的大小,根节点代表整个数据库。当一个节点被加锁时,其所有子节点都被锁住。通过层次图,DBMS可以清除地知道能不能满足某一事务的加锁请求。
        为了减少对子孙节点加锁情况的搜索,DBMS采用另外一种称为多粒度加锁 ( $multiple-granularity\ \ locking$ ) 的专门的加锁策略。该策略使用了意向锁 ( $intention\ \ lock$ )。当一个节点被加锁时,该节点的所有祖先节点就都被加了意向锁。意向锁可以是共享的或者互斥的。另外,事务也可以拥有共享意向互斥锁,这与同时拥有一个共享锁和一个意向互斥锁在逻辑上是等价的,与所有共享锁和意向互斥锁冲突的锁冲突。

3. 数据库恢复

        数据库恢复 ( $Database\ \ recovery$ ) 指的是在发生故障时,将数据库还原到正确状态的过程。

3.1 恢复的必要性

        通常有四种存储介质:主存、磁盘、磁带和光盘。主存是易失性 ( $volatile$ ) 存储器,若系统崩溃,则数据会丢失。磁盘属于联机非易失 ( $online\ \ nonvolatile$ ) 存储器。但是与主存相比,速度要慢。磁带是一种非联机非易失 ( $offline\ \ nonvolatile$ ) 存储介质,但只能串行访问。光盘比磁带更可靠,而且能随机访问。主存通常被称为一级存储器 ( $primary\ \ storage$ ),磁盘和磁带通常被称为二级存储器 ( $secondary\ \ storage$ )。稳定存储 ( $Stable\ \ storage$ ) 是指已被复制到许多非易失的、具有独立故障模式的存储介质(通常指磁盘)上的信息。
        影响数据库处理的故障有许多种,每一种故障的处理方法都不同。故障的原因包括:

3.2 事务和恢复

        事务是数据库系统进行恢复的基本单位。故障发生时,由恢复管理器负责保证事务 ACID 特性中的原子性和持久性。恢复管理器必须保证在故障恢复之后,某事务的操作要么全部都被永久记录,要么全部不记。由于写非原子操作,因此可能会出现事务已经提交但未记录的情况。
        数据库缓冲区位于内存,用于在内存和二级存储器之间传输数据。只有缓冲区的数据被刷新 ( $flushed$ ) 到二级存储器中,更新操作才被视为是永久性的。缓冲区到二级存储器的显示写被称为强制写 ( $force-writing$ )。如果在写缓冲区和将缓冲区数据写到二级存储器之间发生了故障,恢复管理器必须确定当前正在执行写操作事务的状态。如果事务已提交,则为了持久性,恢复管理器必须重做 ( $redo$ ) 该事务对数据的所有修改操作,也称为向前滚 ( $rollforward$ )。另一方面,如果事务未提交,则恢复管理器必须撤销 ( $undo$ ) 即回滚 ( $rollback$ ) 该事务已做的修改,以保证事务的原子性。如果只有一个事务需要撤销,则称为部分撤销 ( $partial\ \ undo$ )。当所有活跃的事务都必须被撤销时,称为全局撤销 ( $global\ \ undo$ )。

3.3 恢复机制

3.3.1 备份机制

        数据库的备份可以在数据库被损坏或者被毁坏时使用。备份可以是对整个数据库的复制,也可以是递增备份,只包含最近一次完全备份或者递增备份以后被修改的数据。

3.3.2 日志文件

        日志 ( $Log$ ),也称为日记 ( $journal$ ) 或流水账,其中记录了对数据库的所有更新信息。日志可能包含下列数据:

        除了帮助系统进行恢复以外,日志还可以用于性能监测和审计。在这种情况下,需要在日志文件中添加额外信息(数据库读、用户登录、注销等)。

某日志文件的一段

        由于事务的日志文件的重要性,日志需要成倍的复制。在某些情况下,每天会产生大量的日志信息,因此不可能总是将所有日志信息都联机保存。对于较小的故障恢复,可以将日志联机保存。对于较大的故障,需要访问大量日志文件,可以等待脱机存储介质的日志文件读到联机存储介质上。一种处理日志文件脱机存储的方法是,将联机的日志文件分成两个独立的随机访问文件。日志记录被写入第一个文件,直到某个上限,比如总信息量的 $70%$ 。然后打开第二个文件,将新事务的所有日志记录都写入该文件,并写到脱机存储介质上。这种方法简化了对单个事务恢复的处理,该事务的所有日志记录要么都在联机存储介质上,要么都在脱机存储介质上。写日志文件的速度对于整个数据库系统的性能至关重要。

3.3.3 检查点

        根据日志文件中的信息,在数据库发生故障时进行恢复。在应用这种机制时的一个难点是:当故障发生时,我们不知道在日志文件中向前搜索多远才可以不用重做那些已经安全地写到数据库的事务。为了限制搜索范围以及对日志文件进行后续处理的工作量,我们采用了一种称为检查点 ( $checkpointing$ ) 的技术。检查点是数据库与事务日志文件之间的同步点,在该点上所有的缓冲区都被强制写到二级存储器。
        DBMS在预定义的时刻设置检查点,并执行以下操作:

        若事务串行执行,当故障发生时,检查日志文件,找到在最近一个检查点前启动的最后一个事务。之后,重做在检查点时刻活跃以及在该事务之后启动并且其开始和提交记录都出现在日志中的那些事务。如果当故障发生时,一个事务仍处于活跃状态,则该事务必须被撤销。如果事务并发执行,那么应该重做所有在最近检查点以后提交的事务,并且撤销所有在故障发生时仍处于活跃状态的事务。

3.4 恢复技术

        恢复程序的执行依赖于数据库受损的程度。有两种情况:

        针对第二种情况的技术有两种:延迟修改 ( $deferred\ \ update$ ) 和立即修改 ( $immediate\ \ update$ )。此外还有一种称为影像页 ( $shadow\ \ paging$ ) 的技术。

3.4.1 采用延迟修改的恢复技术

        采用延迟修改恢复协议时,直到事务提交以后,修改结果才会被写到数据库。然而,对已提交事务的修改操作有必要重做,因为这些修改可能还未被写入数据库。在这种情况下,按下述方式可利用日志文件恢复系统故障:

        当故障发生时,需要检查日志文件,找到故障发生时正在执行的所有事务。从最后一项开始回溯到最近一个检查点记录:

3.4.2 影像页技术

        影像页在事务的生存期中维持了两张页表:当前页表和影像页表。当事务启动时,两张页表相同。此后,影像页表不再变化,用于在系统故障时恢复数据库。在事务执行过程中,当前页表记录数据库的更新,完成后转化为影像页表。与日志相比,它不用维持日志文件,无需撤销或者重做,而且恢复速度也很快。然而它也有缺点,比如数据分裂以及需要周期性地进行无用单元回收,以回收那些不再被访问的块。

数据库系统(9):事务管理