事务

数据库事务是DBMS执行过程中的一个逻辑单位,由一个有限的数据库操作序列构成。

事务必须要满足ACID四个特性。

  • Atomicity(原子性)

    也就是所谓的all-or-nothing。单个事务有一系列的操作,比如查找,增加,更新等。当事务提交之后事务中所有对数据库的操作必须反映到数据库上。但如果由于某些原因中断,那么所有对数据的操作必须恢复到这个事务开始之前。也就是事务对数据库的操作,要么全部执行,要么都不执行。

  • Consistency(一致性)

    事务开始之前数据满足的完整性约束,在事务结束之后也需要满足。其实也就是事务得到了正确的执行。

  • Isolation(隔离性)

    每个事务之间是相互独立的。有点类似于进程的概念。因为事务是并发执行的,所以事务之间不能相互影响不然就有可能破坏一致性

  • Durability(持久性)

    已被提交的事务对数据库的修改应该永久保存在数据库中。这里的关键应该在于永久二字,也就是说即使系统崩溃、硬盘损坏等不可控因素发生,也要保证数据仍然存在数据库中。所以备份很重要啊。

并发控制

考虑一下当多个事务并发执行的情况,是否能保证ACID。如果完全不加控制,因为系统的线程调度是无法预知的,那么多个事务之间的执行顺序也不可控,即破坏了隔离性,随之而来的一致性也无法满足,比如事务可能写入脏数据破坏完整性约束。原子性持久性需要靠恢复系统来保证,这篇文章不过多讨论恢复系统

最简单的能想到的保持隔离性的方式即一次只运行一个事务,也就是说没有并发,串行调度,一个接一个。完全不需要并发控制,可是很明显不现实,因为效率极低。当事务并发执行时,任何调度顺序都是可能的。并发控制的任务是让并发的事务执行结果与串行调度的执行结果相同。这种调度称为可串行化

并发控制的目标即可串行化

可串行化

如何检测调度是否为可串行化?有很多方法,这里只说一种冲突可串行化(conflict serializability)

先定义冲突,即假设不同事务的两种操作访问同一个对象,如果交换他们的操作顺序,会得到不同的结果,则冲突

考虑事务最本质的两种操作,readwrite,则总共有四种情况。

很明显,只要涉及到write冲突。那么当交换调度中未冲突操作的顺序,能得到串行的调度,那么原先的调度则称为冲突可串行化

好的,那么如何检测冲突可串行化,当然选择去交换未冲突的操作然后判断是否串行,但效率不高。比较高效的做法是通过优先图检测。维护一个,当符合特定规则时,放入。假设有两个事务Ti/Tj,一个对象A,规则如下。

  1. Ti在Tj之前读或者写A
  2. Ti在Tj读A之前写A

有些拗口。若无环,则是冲突可串行化,有环则不是,实例如下。

可恢复与无级联

考虑下面一种情况

上面这个调度的问题在于,事务2在读取了事务1的数据之后提交了,然而事务2因为某些原因终止了,那么事务2就要进行回滚。但是事务1已经提交了,提交意味着,数据已经被写入磁盘,原有的数据被覆盖,回滚会出错。这种调度则称为不可恢复的调度。若要实现可恢复的调度,则必须让事务2等待事务1提交之后,再进行提交。

所以可恢复调度即是指,若某事务A读取事务B写入的内容,则需在事务B提交之后,再提交。

可恢复调度同时会带来一定的问题,即级联问题。若T2读了T1写的数据,T3读了T2写的数据,T4读了T3写的数据,以此类推,假设这时T1终止,则需要回滚一系列事务。这样效率是很低的。所以我们希望的是无级联调度,能避免这种情况。

无级联调度即是指,若事务A读取事务B写入的内容,那么事务B需要在事务A读操作之前提交。注意这里的区别,把事务提交提前了。

并发控制希望做到可串行化可恢复无级联无级联调度必定是可恢复调度

两阶段封锁(Two phase locking)

Two phase locking是一种可以实现可串行化的协议。此协议把事务分成两个阶段,增长阶段以及缩减阶段增长阶段是获得锁的阶段,而缩减阶段则反之,是释放锁的阶段。也就说当一个事务一旦释放了一个锁之后就不能继续加锁了。具体定义如下。

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

两阶段封锁最主要的作用是推迟了锁的释放时间。可以试想下如果在中间就释放锁,那则有可能调度给其他事务读到脏数据。

两阶段封锁可以保证可串行化,这是可以证明的。但是两阶段封锁不保证死锁,所以需要额外的工作来检测或者预防死锁

两阶段封锁无法保证无级联,我们可以通过严格两阶段封锁来保证,即在两阶段封锁的前提下,约束在事务提交之前不得释放排他锁。也就是说如果事务不提交的话,他写的数据,别的事务就没法读,符合无级联的定义。

另个一个变种是强两阶段封锁在严格的基础上更进一步,约束事务在提交之前不得释放任何锁。

还有个问题,假如某个数据在之前很长一段时间都是只读的,到最后才需要写,如果按照目前的规则,事务在一开始就要获得对数据的排他锁,但是之前数据是只读的,这样影响了一定的效率。我们采取了锁升级的策略。可以先获得共享锁,直到需要写入时再获取排他锁,大大提高并发效率。

Reference

mit 6.830 lec12
《数据库系统概念》