CMU DB Concurrency Control Theory

并发控制主要是为了实现事务,在实现上分为悲观和乐观控制两种方式:悲观假设所有的事务会相互冲突,实现出来支持的吞吐量不搞;乐观假设事务是不会相互冲突的,可以同时执行,直到发生实际冲突。

里面提到了调度的两种serializability: conflict & view. 好像课程上也没有谈到这两个的区别。看提纲里面的说明是,view sz除了满足conflict sz之外还允许blind write, 所以满足view sz的schedules数量会更多。但是鉴于事务管理其实不知道具体的操作的语义,所以现在大部分DBMS都是实现了conflict sz. conflict sz的意思是,对于每个tx里面的operations按照某种serial order执行,如果两个op存在冲突的话,可以尝试更换顺序,找到合理的schedules. 不过我的理解是,这些都是理论上的东西,都是在离线地寻找满足某种sz的schedules, 现实的OLTP可是在线系统,做不了这许多事情。

cmudb-cct-schedules.png

接下来就是CC的实现方式了:two-phase locking(两阶段锁,2PL,大部分DBMS都实现了), timestamp ordering(时间序,我理解spanner可能属于这个范畴),multi-version (多版本)。

2PL有两个阶段:growing & shrinking. 第一个阶段不断地拿到锁,第二个阶段不断地释放锁。基本的2PL实现可能会存在cascading aborts,tx1的abort会导致tx2 abort(考虑一下如果tx2 读取了 tx1的写入,但是tx1最终abort的情况)。cascading aborts回滚实现起来比较麻烦,所以为了避免它,可能对2PL施加更强的限制(strong strict 2PL),就是只在事务结束的时候释放锁。 2PL的最大问题就在于并发性不好。

2PL基本的锁有两个read/write lock,但是在事务里面通常叫做shared lock(S), exclusive lock(X). 但是仅仅有这两个lock还是不够的,设想起来如果要对table scan,那么我们要对上面所有的tuples做S-Lock,这个量有点大。我们需要有更大粒度的锁,所以就有了Intention lock:Intention-Shared(IS), Intention-Exclusive(IX), shared+intention-exclusive(SIX),关于这三个锁的用途可以看下面:增加了这些锁之后,锁的获取判断就复杂了,关于这点我还没有完全搞明白。

TO有两种实现:Basic和OCC的,先从Basic的开始说起。Basic的实现方式是,对于每个txn都会分配一个ts(timestamp),每次对对象读写都会更新这个时间戳(单调递增)。如果TS(t) < W-TS(x)的话,那么t是不允许去读取这个x对象的,那么t只能abort. 如果TS(t) < R-TS(x) 或者是 < W-TS(x)的话,那么t也不允许去更新这个对象。总之就是,如果有更高时间戳的txn更新了某个对象的话,那么旧的txn再想操作这个对象是不行的了。操作成功之后需要维护一个local copy以便执行repeat reads. Basic TO还有个优化,就是Thomas Write Rule, 就是如果Write不成功的话,其实完全可以忽略它,因为其他副本也不会读到这个Write值,而本身这个txn是有个local copy的。Basic TO还有个问题就是,就是schedule不是recoverable的,不过好像也不是什么大问题。以下图说明调度不是recoverable的:R(A)读取了T1的W(A),但是T1 abort了。想让T2成功,必须重启T1。可是如果重启T1的话,TS(T1)就变了导致W(A)也会失败。这种情况只能类似使用cascading abort,将T2去abort.

cmudb-cct-recoverable-schedules.png

OCC TO实现和Basic TO实现非常类似,差别在于txn每次更新并不是去更新global table,而是更新每个txn内部的local table. 然后在最后提交的时候,进行validate & write. 只有在最后validate & write阶段是串行的,期间每个txn都是各自进行自己的工作,不会类似Basic TO一样去看global table上的TS. TS分配也从txn开始阶段,后移到了validate阶段。validate阶段主要就是进行冲突处理,有好几种情况,这样就不写了。

前面提到的都是已经存在的tuple的read/write. 我们可以对这些tuple进行local copy,或者是在table上增加intention lock. 可是如果txn里面包含了insert/delete的话,允许对tuple进行增加和删除,那么可能就会看到某个之前不存在的值,这就是phantom problem. 这个问题出现的本质,还是因为锁的粒度不够引起的,如果对整个table加一个大锁,肯定不会出现phantom problem.

cmudb-cct-phantom.png

有好几种办法解决phantom problem: re-scan(cost太高), predicate locking(cost也太高,需要判断insert/delete是否会落在predicate上), index locking(cost还能接受,如果没有index的话,就只能回退到table lock)上。

根据读数据的几种情况,可以得到下面几种隔离级别:

  1. 如果允许脏读,那么就是read uncommitted,否则就要read committed
  2. 如果读值之后不能改变,那么就要使用repeatable read
  3. 如果不能出现phantom value, 那么只能选择serializable

cmudb-cct-isolation-levels.png