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：若无冲突，则将修改的部分写入数据库。反之则终止或重启。