浅谈数据库并发控制 - 锁和 MVCC

在学习几年编程之后,你会发现所有的问题都没有简单、快捷的解决方案,很多问题都需要权衡和妥协,而本文介绍的就是数据库在并发性能和可串行化之间做的权衡和妥协 - 并发控制机制。

tradeoff-between-performance-and-serializability

tradeoff-between-performance-and-serializability

如果数据库中的所有事务都是串行执行的,那么它非常容易成为整个应用的性能瓶颈,虽然说没法水平扩展的节点在最后都会成为瓶颈,但是串行执行事务的数据库会加速这一过程;而并发(Concurrency)使一切事情的发生都有了可能,它能够解决一定的性能问题,但是它会带来更多诡异的错误。

引入了并发事务之后,如果不对事务的执行进行控制就会出现各种各样的问题,你可能没有享受到并发带来的性能提升就已经被各种奇怪的问题折磨的欲仙欲死了。

概述

如何控制并发是数据库领域中非常重要的问题之一,不过到今天为止事务并发的控制已经有了很多成熟的解决方案,而这些方案的原理就是这篇文章想要介绍的内容,文章中会介绍最为常见的三种并发控制机制:

pessimistic-optimistic-multiversion-conccurency-control

pessimistic-optimistic-multiversion-conccurency-control

分别是悲观并发控制、乐观并发控制和多版本并发控制,其中悲观并发控制其实是最常见的并发控制机制,也就是锁;而乐观并发控制其实也有另一个名字:乐观锁,乐观锁其实并不是一种真实存在的锁,我们会在文章后面的部分中具体介绍;最后就是多版本并发控制(MVCC)了,与前两者对立的命名不同,MVCC 可以与前两者中的任意一种机制结合使用,以提高数据库的读性能。

既然这篇文章介绍了不同的并发控制机制,那么一定会涉及到不同事务的并发,我们会通过示意图的方式分析各种机制是如何工作的。

悲观并发控制

控制不同的事务对同一份数据的获取是保证数据库的一致性的最根本方法,如果我们能够让事务在同一时间对同一资源有着独占的能力,那么就可以保证操作同一资源的不同事务不会相互影响。

pessimistic-conccurency-control

pessimistic-conccurency-control

最简单的、应用最广的方法就是使用锁来解决,当事务需要对资源进行操作时需要先获得资源对应的锁,保证其他事务不会访问该资源后,在对资源进行各种操作;在悲观并发控制中,数据库程序对于数据被修改持悲观的态度,在数据处理的过程中都会被锁定,以此来解决竞争的问题。

读写锁

为了最大化数据库事务的并发能力,数据库中的锁被设计为两种模式,分别是共享锁和互斥锁。当一个事务获得共享锁之后,它只可以进行读操作,所以共享锁也叫读锁;而当一个事务获得一行数据的互斥锁时,就可以对该行数据进行读和写操作,所以互斥锁也叫写锁。

Shared-Exclusive-Lock

Shared-Exclusive-Lock

共享锁和互斥锁除了限制事务能够执行的读写操作之外,它们之间还有『共享』和『互斥』的关系,也就是多个事务可以同时获得某一行数据的共享锁,但是互斥锁与共享锁和其他的互斥锁并不兼容,我们可以很自然地理解这么设计的原因:多个事务同时写入同一数据难免会发生各种诡异的问题。

lock-and-wait

lock-and-wait

如果当前事务没有办法获取该行数据对应的锁时就会陷入等待的状态,直到其他事务将当前数据对应的锁释放才可以获得锁并执行相应的操作。

两阶段锁协议

两阶段锁协议(2PL)是一种能够保证事务可串行化的协议,它将事务的获取锁和释放锁划分成了增长(Growing)和缩减(Shrinking)两个不同的阶段。

growing-to-shrinking

growing-to-shrinking

在增长阶段,一个事务可以获得锁但是不能释放锁;而在缩减阶段事务只可以释放锁,并不能获得新的锁,如果只看 2PL 的定义,那么到这里就已经介绍完了,但是它还有两个变种:

  1. Strict 2PL:事务持有的互斥锁必须在提交后再释放;
  2. Rigorous 2PL:事务持有的所有锁必须在提交后释放;

two-phase-locking

two-phase-locking

虽然锁的使用能够为我们解决不同事务之间由于并发执行造成的问题,但是两阶段锁的使用却引入了另一个严重的问题,死锁;不同的事务等待对方已经锁定的资源就会造成死锁,我们在这里举一个简单的例子:

deadlock

deadlock

两个事务在刚开始时分别获取了 draven 和 beacon 资源上面的锁,然后再请求对方已经获得的锁时就会发生死锁,双方都没有办法等到锁的释放,如果没有死锁的处理机制就会无限等待下去,两个事务都没有办法完成。

死锁的处理

死锁在多线程编程中是经常遇到的事情,一旦涉及多个线程对资源进行争夺就需要考虑当前的几个线程或者事务是否会造成死锁;解决死锁大体来看有两种办法,一种是从源头杜绝死锁的产生和出现,另一种是允许系统进入死锁的状态,但是在系统出现死锁时能够及时发现并且进行恢复。

deadlock-handling

deadlock-handling

预防死锁

有两种方式可以帮助我们预防死锁的出现,一种是保证事务之间的等待不会出现环,也就是事务之间的等待图应该是一张有向无环图,没有循环等待的情况或者保证一个事务中想要获得的所有资源都在事务开始时以原子的方式被锁定,所有的资源要么被锁定要么都不被锁定。

但是这种方式有两个问题,在事务一开始时很难判断哪些资源是需要锁定的,同时因为一些很晚才会用到的数据被提前锁定,数据的利用率与事务的并发率也非常的低。一种解决的办法就是按照一定的顺序为所有的数据行加锁,同时与 2PL 协议结合,在加锁阶段保证所有的数据行都是从小到大依次进行加锁的,不过这种方式依然需要事务提前知道将要加锁的数据集。

另一种预防死锁的方法就是使用抢占加事务回滚的方式预防死锁,当事务开始执行时会先获得一个时间戳,数据库程序会根据事务的时间戳决定事务应该等待还是回滚,在这时也有两种机制供我们选择,一种是 wait-die 机制:

deadlock-prevention-wait-die

deadlock-prevention-wait-die

当执行事务的时间戳小于另一事务时,即事务 A 先于 B 开始,那么它就会等待另一个事务释放对应资源的锁,否则就会保持当前的时间戳并回滚。

另一种机制叫做 wound-wait,这是一种抢占的解决方案,它和 wait-die 机制的结果完全相反,当前事务如果先于另一事务执行并请求了另一事务的资源,那么另一事务会立刻回滚,将资源让给先执行的事务,否则就会等待其他事务释放资源:

deadlock-prevention-wound-wait

deadlock-prevention-wound-wait

两种方法都会造成不必要的事务回滚,由此会带来一定的性能损失,更简单的解决死锁的方式就是使用超时时间,但是超时时间的设定是需要仔细考虑的,否则会造成耗时较长的事务无法正常执行,或者无法及时发现需要解决的死锁,所以它的使用还是有一定的局限性。

死锁检测和恢复

如果数据库程序无法通过协议从原理上保证死锁不会发生,那么就需要在死锁发生时及时检测到并从死锁状态恢复到正常状态保证数据库程序可以正常工作。在使用检测和恢复的方式解决死锁时,数据库程序需要维护数据和事务之间的引用信息,同时也需要提供一个用于判断当前数据库是否进入死锁状态的算法,最后需要在死锁发生时提供合适的策略及时恢复。

在上一节中我们其实提到死锁的检测可以通过一个有向的等待图来进行判断,如果一个事务依赖于另一个事务正在处理的数据,那么当前事务就会等待另一个事务的结束,这也就是整个等待图中的一条边:

deadlock-wait-for-graph

deadlock-wait-for-graph

如上图所示,如果在这个有向图中出现了环,就说明当前数据库进入了死锁的状态 TransB -> TransE -> TransF -> TransD -> TransB,在这时就需要死锁恢复机制接入了。

如何从死锁中恢复其实非常简单,最常见的解决办法就是选择整个环中一个事务进行回滚,以打破整个等待图中的环,在整个恢复的过程中有三个事情需要考虑:

deadlock-recovery

deadlock-recovery

每次出现死锁时其实都会有多个事务被波及,而选择其中哪一个任务进行回滚是必须要做的事情,在选择牺牲品(Victim)时的黄金原则就是最小化代价,所以我们需要综合考虑事务已经计算的时间、使用的数据行以及涉及的事务等因素;当我们选择了牺牲品之后就可以开始回滚了,回滚其实有两种选择一种是全部回滚,另一种是部分回滚,部分回滚会回滚到事务之前的一个检查点上,如果没有检查点那自然没有办法进行部分回滚。

在死锁恢复的过程中,其实还可能出现某些任务在多次死锁时都被选择成为牺牲品,一直都不会成功执行,造成饥饿(Starvation),我们需要保证事务会在有穷的时间内执行,所以要在选择牺牲品时将时间戳加入考虑的范围。

锁的粒度

top Created with Sketch.