Timestamp Ordering(T/O)

比较广义的分类型的话,总共有两种Concurrency Control Protocol

  1. Two Phase Locking(悲观)

    假设事务会冲突,提前加上锁。会有死锁的可能

  2. Timestamp Ordering(乐观)

    假设事务冲突比较少,执行阶段不加锁,在commit阶段才会检查冲突,若冲突则abort

T/O定义的比较广泛,总之就是根据timestamp来确定事务顺序的,都归于T/O,包括basic T/O, Optimistic Concurrency Control(OCC), MVCC都属于T/O。

OCC

这篇文章主要写一下OCC。basic T/O和OCC的区别就是在事务一开始就分配timestamp了,然后根据timestamp来确定顺序,比较简单,好像也没有数据库这么用。

OCC主要分三个阶段。

  • Read phase

    事务复制tuple到一个独立的工作空间,执行读写操作。(虽然叫read phase,但依然有写操作,叫excute phase 其实更合理)

  • Validation phase

    从这个阶段开始意味着执行阶段结束,进入commit。dbms需要检查其他所有事务是否和当前事务的改动冲突。一般是所有事务并行检查,最粗暴的做法是一个大锁,一次只能检查一个事务,当然效率也低。分成如下两种检查。

    • Backward Validation

      检查当前事务的改动是否和目前已提交的事务冲突。(read-after-write)

    • Forward Validation

      检查当前事务的改动是否和当前仍然还在执行中的事务的冲突(write-after-read)

  • Write phase

    将当前事务在独立工作空间的改动,写到真正的全局数据库中。

Timestamp Allocation

时间戳分配是OCC的关键。有很多种分配的方式

  • Mutex

    全局的逻辑时间戳,用锁来递增。性能最差

  • Atomic Addition

    CAS更新时间戳,比较高效,但是多核情况下需要invalid cache line是bottleneck

  • Batched Atomic Addition

    每个线程一次性获取多个时间戳,用完了再用CAS更新全局时间戳。这种方式用的较多,比上一种更高效

  • Hardware Clock/Counter

    cpu硬件上支持,目前未实现

Silo OCC

Silo DBMS是一个单机OLTP数据库,用OCC实现了Serializable隔离级别。Silo的实现基于Masstree,OCC的实现比较有趣的地方在于TID和epoch。

Silo基于一个全局的number epoch E来分割时间周期,有一个特定的线程去递增E,根据论文的设定是每40ms增加一次。

TID是一个64 bit的integer,被分成几个部分来表示不同的含义。最高的几个位次代表当前事务提交时的epoch E。中间位次表示基于当前epoch算出来的timestamp。最低的三个bit代表lock bit,lastest-version bit,absent bit。Tid是直接写到tuple里的。

Commit Protocol

每个事务维护两个独立的私有集合,read-set, write-set。所有在write-set中的tuple也在read-set中。

  • Phase 1

    将所有在write-set中的tuple,在全局数据库上锁。也就是把这些tuple中tid的lock bit设为1。然后获取当前最新的epoch E。这里需要刷新缓存,保证拿到的是最新的。

  • Phase 2

    遍历read-set中的所有tuple。如遇到如下两种情况,则事务abort。

    1. 全局数据tuple的tid与read-set中的tid不同或latest bit为0。(被其他已经提交的事务修改,Backward Validation)
    2. locked bit为1且该tuple不属于当前事务的write-set。(被其他正在进行的事务锁定,Forward Validation)

    这里还有一个防止幻读(phantom)的检查是需要检查所有b+tree的叶子节点的version。

    全部检查都过了之后,才会根据epoch,生成新的tid。

  • Phase 3

    将所有write-set的tuple和新生成的tid写入全局数据库。并且unlock tuple。

注意只读事务是不需要修改全局数据库的。具体算法见下图。

另外生成的tid需要满足如下三个条件。

  1. 大于所有当前事务read-set和write-set中tuple的tid
  2. 大于当前工作线程最近生成的tid
  3. tid最高位设为当前的epoch

论文还有很多细节这里略过。

Reference

[1] Speedy Transactions in Multicore In-Memory Databases. SOSP ‘13
[2] CMU 15721