论文笔记 [SOSP '13] Speedy Transactions in Multicore In-Memory Databases

比较广义的分类型的话，总共有两种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