An Empirical Evaluation of In-Memory Multi-Version Concurrency Control

引言

In-Memory的数据库也最近的一个研究的热点，此外，MVCC相对于其它存在的Concurrency Control方法，相对来说是最均衡的，新设计的In-Memory绝大部分采用的是MVCC的方法(OCC的缺点太明显了，write一多就abort)。基于MVCC的DBMS允许一个只读事务在读取一个较老版本的同时另外一个事务更新相同的一个对象，能获取更加好的并发程度。此外，如果DBMS没有移除对象的就版本，这个系统就可以支持读取过去一个时间点的快照。虽然有诸多的DBMS使用了MVCC，但是它们之间的MVCC的方式很多不同的地方。这篇论文主要分析不同MVCC在这些方面方面上的一个特点:

1. 并发控制协议；
2. 版本存储；
3. 垃圾回收；
4. 索引管理。

(更新)强烈推荐的一片论文。

MVCC Overview

表1给出了常见数据4个方面的对比:

ee-mvcc-compare

忽略其一些具体实现的差异，一个基于MVCC的DBMS一般有相同的一些用于事务和数据元组的元数据: Transactions: DBMS会赋予一个事务一个递增的时间戳作为事务id，用于表示这个事务。并发控制协议使用这个标识符标识一个事务可以访问的元组。Tuples: 一个物理上的版本的数据包含了4个元数据字段(具体的可能有些区别)，如下图所示:

+--------+-----------+---------+---------+------+-------------------------------+
|        |           |         |         |      |                               |
| txn-id | begain-ts |  end-ts | pointer | ...  |       cloumns...              |
|        |           |         |         |      |                               |
+--------+-----------+---------+---------+------+-------------------------------+
+                                               +                               +
| <----------------  Header  -----------------> | <--------- Content ---------> |
+                                               +                               +

txn-id字段作为这个版本的写锁，当一个元组没有被上写锁的时候，这个字段就是0。大部分的DBMS使用一个64bit的整形作为txn-id，这样就是可以使用一个CAS就可以原子地更新txn-id的值。如果一个事务T(事务id为T(id))，想要更新这个元组，它会先检查txn-id的值，如果是0，那么它就会使用CAS操作将txn-id设置为T(id)。当一个事务尝试更新一个txn-id字段不为0且不等于自身T(id)的时候，这个事务就是abort。Begain-ts和end-ts代表了这个元组的生存期，都被初始化为0，将begain-ts设置为INF代表一个事务将其删除。最后的pointer字段保存了相邻的的版本的地址。

Concurrency Control Protocol

Timestamp Ordering (MVTO)

MVTO是最初的MVCC的Concurrency Control Protocol(CCP)，tuple的header中还保存了最近的事务读取它的时间。MVTO其基本思路就是使用tid提前计算它们序列化的顺序。当一个txn尝试读取or更新一个已经上了write lock的一个版本，这个txn就会abort。当一个txn准备读取一个tuple时，会根据begin-ts和end-ts和tid来找到具体要读取的tuple的版本。

im-mvcc-to

上图中，tuple的txn-id为0 or这个txn自己的id时，代表没有被其它事务上write lock，可以正常操作。MVTO不允许读未提交，这里使用的方式就是一个txn读取一个tuple的时候，如何read-ts小于自己的tid，就将其设为tid，如果大于，则选择一个更旧的版本。MVTO中，txn总是更新最近的一个版本，当满足一个tuple: 1.没有其它事务获取了write lock，2.txn的tid大于tuple的read-ts，则可以更新一个新版本。在更新之后，tuple的txn-id设置为txn的tid，txn提交的时候，设置新的版本的begin-ts为tid，end-ts为无穷大，最近的一个旧的的版本的end-ts为txn的id。

Optimistic Concurrency Control (MVOCC)

从上面的表中可以发现，使用MVOCC的基本时内存数据库。MVOCC结合了MVCC和OCC的一些特点。

This reduces the amount of time that a transaction holds locks. There are changes to the original OCC protocol to adapt it for multi-versioning [27]. Foremost is that the DBMS does not maintain a private workspace for transactions, since the tuples’ versioning information already prevents transactions from reading or updating versions that should not be visible to them.

im-mvcc-occ

MVOCC将txn分为3个阶段:

  • read phase，MVOCC通过begin-ts 和 end-ts 来决定一个一个tuple的可见性。

  • alidation phase，在这个阶段，数据库会赋予txn一个时间差，叫做t-commit，使用这个时间戳来检查这个事务read-set中哪些tuples被提交更新了。

  • write phase ，如果第2步通过，进入第3步，更新一个新版本的数据，begin-ts设计为tid，end-ts设置为INF。

    <div class="highlighter-rouge">

    Transactions can only update the latest version of a tuple. But a transaction cannot read a new version until the other transaction that created it commits. A transaction that reads an outdated version will only find out that it should abort in the validation phase.