Locking in B+Tree

使用2PL在index上效果会很差,因为每次使用索引时都会lock root,导致其他事务无法访问。Index一般使用Lock crabbing

Basic Lock Crabbing

  1. search
    • 获取parent的S lock
    • 接着到下一层获取child的S lock
    • 释放上一层parent的S lock,如此循环。
  2. insert/delete
    • 获取parent的X lock
    • 到下一层,获取child的X lock
    • 如果安全的话则释放parent的X lock。安全即是指child没有分裂或者合并。也就是说有足够的空间插入,或者足够多的节点删除。不然继续到一层,如此循环。

在删除或者插入的情况下,如果节点都满或者都不够的话很有可能整条链上都有锁,一直到leaf节点才会逐级向上释放,并发性比较差,由此引入一种优化的方案。

Optimistic Lock Coupling

基本思想就是在插入或者删除的时候和查找一样获取S lock,直到叶子节点时,如果需要分裂或者合并再采用上面的算法重来一遍。也就是先假设合并或者分裂比较少见。若真发生了再上X锁。

Timestamp Ordering Concurrency Control

通过时间戳来确定事务的先后顺序而不是采用锁。

在事务启动前,分配时间戳。若TS(T1)<TS(T2)则DBMS必须确保执行顺序与T1在T2之前的串行调度一样。

BASIC T/O

  1. Read X
    • 如果TS(Ti) < W-TS(X),则违法了顺序,也就是Ti希望去读在Ti之后的事务写的数据了。这种情况下需要中上事务,或者重启
    • 若相反,则可以读,并且需要更新R-TS(X) = max(R-TS(X), TS(Ti))。也就是将最大的读事务的timestamp记录下,当写的时候可以用来比较。
  2. Write X
    • 若果TS(Ti) < R-TS(X) 或者 TS(Ti) < W-TS(X),与上面一样,也是违法了顺序。则终止或重启。
    • 如相反,则允许写,并且更新W-TS(X) = Ti

这里有一种优化方法,也就是时TS(Ti) < W-TS(X),忽略写,让事务继续。因为反正Ti的write都会之后的事务覆盖。这种方法叫Thomas Write Rule

Optimistic Concurrency Control (OCC)

与悲观锁相反,假设冲突发生的情况比较少,不加锁,直到冲突发生后,再重试。当每个事务运行的时候都会copy一份内容作为private workspace。事务的所有的操作都在private workspace中,只有等提交时才会写到真正的数据库中。具体的实施如下。

  • Read phase:将需要写的那部分数据copy到private workspace
  • Validation phase: 当事务提交的事务,检查是否与其他事务冲突。
  • Write phase:若无冲突,则将修改的部分写入数据库。反之则终止或重启。