MVCC and Snapshot Isolation

MVCC: Multi-version concurrency control。

事务处理系统中,为了使得多个事务能够并发执行并得到正确结果,需要采用一定的并发控制协议。一类最常见的并发控制协议就是Lock-Based Protocol,其中我最熟悉的就是立即更新悲观上锁,其实现方式如下:

  1. 当需要读/写一个item的时候,获取对应的锁,一直持有到commit或abort。
  2. 所有的更新操作是立即修改对应数据,修改发生之前会试图把这个item的前像(pre-image)存下来,如果已存在则不用了。
  3. 如果发生rollback,利用前像恢复到事务开始之前的状态。
  4. 如果成功commit,那么丢弃所有前像。

MVCC则是另一类并发控制协议。其基本思想是:每个事务在提交时,这个时刻该数据库的所有已提交数据构成一个快照,每个快照对应一个版本号。每个事务工作在一个特定的版本上,也就是这个事务开始时数据库的版本,提交时再把它所修改的数据与数据库当前版本进行合并,不成功则retry。

前面所说的“并发执行并得到正确结果”是个很模糊的说法,准确来说,并发控制的目的是为了达到特定的隔离度。SQL-92标准定义了4种隔离度:READ UNCOMMITTED、READ COMMITTED、REPEATABLE READ、SERIALIZABLE。最初,大多数数据库都是在这4种隔离度的定义下设计并实现的,但是现在又多了一种,Snapshot Isolation。最早是Oracle先整出来的,MS SQL Server从2005版开始加入这个。 MySQL InnoDB没有明确的把snapshot作为一个隔离度提出来,它声称提供了SQL92标准的全部4种隔离度,但是其实拿着snapshot、mvcc在里面混水摸鱼,搞的四不像。InnoDB的repeatable read isolation其实要比SQL92标准中规定的强,例如一个transaction反复执行select * from tableA;另一个往tableA里面插入数据。那么第二个尽管已经提交了,但是第一个还是看不到,也就是说他的repeatable read是没有幻影的(Phantom),它是用next-key locking去除了phantom。

我觉得归根结底,隔离度的分类不是从理论出发的而是从实现出发的。单从理论讲,只要一种就够了啊,我就要Serializable,只要你能实现,那么最好了。我认为SQL-92的那4种隔离度是站在Lock-Based Protocol的实现上划分的。当出于效率和死锁的考虑,商业数据库实现的时候都尽量避开Serializable Isolation的时候,MVCC就火了起来。换个位子,从理论上来说,MVCC能实现3种隔离度

  1. Serializable
  2. Consistent Read 这其实是InnoDB中主要使用的隔离度
  3. Snapshot Isolation

Serializable Isolation是有严格定义的,但是对于MVCC是否能产生Serializable Isolation,我至今保持质疑。Philip M. Lewis在《数据库与事务处理》一书中讲到了Read-only Multi-Version Concurrency Control,说它比较容易实现并且可以产生可串行化的调度,但是书上给的证明和解释实际上是含糊的、有问题的。这种MVCC的实现是这样的:首先,所有的transaction可分为两类:read-only和非read-only。非read-only是指至少包含一个写操作。这个协议的实现如下:

  1. 非read-only的transaction采用立即更新悲观上锁的方式做并发控制。
  2. read-only的transaction采用事务开始时的数据库的版本来满足它的所有读取需求,故而可以达到事务级读一致性。

此处书上的原话是:“如果读/写型事务可以串行执行,那么所有的事务都可以提供事务级读一致性。在这种情况下,只读型和读/写型事务的组合调度是可串行化的”。可稍微前面一些明明又说过“然而,事务级读一致性未必能确保可串行性”。

对于Snapshot Isolation,直观上的理解就是:在transaction开始的时候,对已提交的数据做一个snapshot(这个操作是原子的),之后这个transaction的所有计算都是在这个snapshot上进行的。提交时采用的是乐观锁的First Commit Wins模式,只对已修改的item做版本检查(是不是最新的),未修改的item不影响事务是否能提交成功。Snapshot Isolation的最大好处是对于read-only transactions是可以立即执行的,不用等待其它transaction完成。

提这样一个问题:假设在某个执行序列中,所有的非只读的transaction存在可串行化的调度,那么是否这个执行序列中所有的transaction都是可串行化的?这个答案是否定的,paper是04年发表在SIGMOD上。paper中举了一个很有意思的例子:假设A和B是夫妻,各有一张信用卡但是实际结算是一起的。银行有个规定,如果他俩透支了(A的账户金额+B的账户金融<0),那么要按透支金额立即收取10%的费用。

即:

/**
* 从A的账户中取钱。
*/
void withdrawalMoney(Account A,Account B,int money){
  int total = A.money + B.money;
  if(total - money <0) {
     A.money -= money + (total – money) * 0.1;
  } else {
     A.money -= money;
  }
}

假设,现在两个人刚办完信用卡,卡上都没有钱,账户金额为0。现在有三个操作,

T1:往B的账户加20块钱。
T2:从A的账户中取10块钱。
T3:把A、B的账户的钱打印出来。

那么很显然,T1、T2涉及修改操作,T3是只读的。假设采用的是Snapshot Isolation,并且实际执行序列如下:

  1. T2读A、B的账户余额。都为0 。
  2. T1读B的账户余额,加入20,提交。
  3. T3读A、B的账户余额,打印出来。结果是A=0,B= 20。提交。
  4. T2扣款。从A的账户扣10块钱。因为是在之前的snapshot的基础上计算的,所以结果是A的账户应该是-11。提交。

因为最终的结果是A=-11并且B=20。所以如果存在可串行化的调度,那么必然是T2早于T1。但是T3给出的结果意味着T1早于T2。所以前面提的那个假设被否定了。但是,如果对非只读的transaction采用立即更新悲观上锁,那么上述的调度是不存在的。

很明显,可串行化的隔离度对程序员来说更容易接受更容易被理解。但是MVCC相比传统的Lock-Based concurrency control更具实用价值。

我的计划:

  1. 搞清楚这两种隔离度之间到底有哪些差别?
  2. 实现一个MVCC的key-value数据库。
  3. 把它用在一个项目中。

睡觉!

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥