论文笔记 [VLDB '17] An Empirical Evaluation of In-Memory Multi-Version Concurrency Control

MVCC天生是属于SI隔离级别的。SI表示每个事务开始的时候看到的是一个独立的snapshot，在提交的时候如果write未冲突即成功。在SI下会有write skew的异常情况。

write skew可以用白球黑球的例子来说明。比如说现在有一堆球，一半是黑的，一半是白的。现在执行两个事务txn1，txn2。

• txn1把黑球变成白球
• txn2把白球变成黑球

如果是SERIALIZABLE隔离级别的，那就相当于事务顺序执行, 最后的结果肯定是全黑或者全白。但如果是SI，两个事务都看到相同的snapshot，并在这基础上修改，就很有可能出现还是一半黑一半白的情况。

只要在range scan的情况下会出现write skew, point update不会有这种情况。

Multi-version Concurrency Control (MVCC)

MVCC是目前最流行事务并发管理的方式。根据字面含义，DBMS会创建多个物理的tuple版本，根据事务版本选择对应的tuple版本返回给当前的事务。MVCC有很多优势，如下。

• writer do not block reader.

  需要注意的是，MVCC并不意味只不上锁。比如一个事务t1在写某一个tuple A1，会先对A1上锁，然后生成A2。这个时候假如事务t2要读A1是不行的，只能读A1之前的版本，因为此时t1还没有提交。所以这里的读写互不阻塞指的是事务级别的，写事务不阻塞读事务，不必像2PL那样等到别的事务提交之后才能拿到锁继续执行。

• Read-only transactions can read a consistent snapshot without acquiring locks.

  consistent指的是所有已提交的事务所做的修改。

• Easily support time-travel queries.

  很容易追溯过去的版本

一般MVCC的单个tuple含有txn-id(tid), begin-ts, end-ts, pointer这几个字段，不同算法会略有不同。

MVCC涉及到很多数据库设计方式。比如MVCC需要和别的Concurrency Control ptotocol搭配使用，例如T/O, OCC, 2PL等 。主要有四个关键的设计决策。

• Concurrency Control ptotocol
• Version Storage
• Garbage Collection
• Index Management

另外这篇文章不考虑range scan，没有phantoms，所以下面描述的算法都是serializable isolation。该文主要讨论的是in-memory database, 和disk-based DBMS有很多区别，比如write-lock 是直接内嵌在tuple上的，当有事务修改tuple时，会将该tuple的txn-id设置为事务的tid，相当于上了锁，事务提交后将txn-id设为0。

下面是一张论文对现有数据库设计的调研结果。

Concurrency Control ptotocol

1. Timestamp Ordering(MVTO)

   MVTO使用tid来预先定义事务执行的顺序。tuple中额外增加一个read-ts字段，用来保存最后事务读取该tuple的tid。

   • read需要检查当前事务的tid是否落在begin-ts和end-ts之间，并且该tuple没有被别的事务锁定，即txn-id=0或等于tid。如果可以读的话，将read-ts设置为tid。
   • write需要检查该tuple没有被其他事务锁定，并且tid大于当前tuple的read-ts。如果满足条件则创建新的tuple。

2. Optimistic Concurrency Control(MVOCC)

   OCC在事务执行时不做检查。在事务提交的时候，进入Validation Phase之后，会分配一个timestamp，根据这个时间戳判断事务的先后顺序，如不符合则abort。OCC是假设事务冲突的次数会比较少。MVOCC和原始的OCC不同的是，不再维护私有的工作空间，而是生成真正的物理上tuple。具体OCC的算法可以看上一篇博客occ。

   对长事务最后又abort的这种情况不友好。

3. Two-phase Locking(MV2PL)

   事务需要在对tuple执行操作之前获取锁。write-lock就还是之前txn-id，read-lock额外增加一个字段read-cnt，代表当前读取该tuple的数量。

   • read也是需要根据tid找到一个落在begin-ts和end-ts直接的tuple版本，如果该tuple的txn-id为0的话（其他事务没有获取这个tuple的互斥锁）, 则递增read-cnt
   • write只有在read-cnt和txn-id都为0的情况下，才能创建新的tuple版本。

   和常规2PL一样，关键在于如何处理死锁。

Version Storage

MVCC利用pointer将所有版本的tuple串成一个链表管理。索引总是指向链表表头。

1. Append-only Storage

   所有版本的tuple存在同一个表上。每次write的时候，往同一个表的empty slot中添加。这种方式的区别在于链表链接的顺序。

   • Oldest-to-Newest(O2N)

     head指向oldest tuple，每次查找都需要从旧往新搜索一遍整个链表。

   • Newest-to-Oldest(N2O)

     head指向newest tuple。插入tuple的时候，需要更新index的指向，但是不需要搜索整个链表。可以让index指向一个逻辑的间接节点，避免频繁更新index。

   更适合分析性查询和大块的遍历，因为大部分tuple都连在一起。

2. Time-Travel Storage

   和Append-only的区别就是将older tuple存到不同的表上。

   • 每次更新的时候，copy当前版本的tuple到time-travel table上
   • 然后修改main table中的master version为最新的内容，并更新指针指向旧的tuple

3. Delta Storage

   这种方式和TIme-Travel的不同在于，每次copy的时候，仅仅copy被修改了的字段。如果需要旧的版本，DBMS需要遍历链表重建tuple。适合write-intensive的workloads，对read-intensive的事务不友好。

Garbage Collection

DBMS需要定期清理无用的tuple来提高查询效率和节省空间。满足以下两个条件，则这个版本的tuple可以被清理。

1. 当前所有在运行的事务都看不到这个版本的tuple。
2. 这个tuple是由被abort的事务创造的

GC可以分成两种力度

1. Tuple Level

   • Background Vacuuming(VAC)

     开一个额外的线程，搜索所有tuple，找出无效的tuple。这种方式最常见，比较容易。也可以用bitmap来优化，追踪那些dirty block，所以vacuum线程就不需要查找所有的block。

   • Cooperative Cleaning(COOP)

     不开额外的线程。在正常事务执行过程中，遍历tuple链表的时候，同时也判断tuple是否过期，只对O2N有效。这种方式可能会带来额外消耗和漏网之鱼，一般还是会再定期开个线程遍历全表检查一下。

2. Transaction Level

   用这种方式事务需要自己管理它们旧版本的tuple，由DBMS来决定已经结束的事务所产生的tuple是无效的（no longer visible to other txns）。

Index Management

主键索引当然永远指向version chain的head。关键在于secondary index的设计。secondary index的叶子节点的value可以指向一个间接的逻辑节点，也可以直接指向tuple的地址。

1. Logical Pointer

   这种方式不需要经常修改index，因为它的指向永远是固定。比如说指向主键，但是需要再用主键通过primary index找到对应的tuple，这是额外的消耗。或者指向tupleid，另外维护一个数据结构将tupleid对应到物理的tuple地址。适合write-intensive。

2. Physical Pointer

   直接指向物理的tuple地址。不需要再搜索一次，但需要频繁变更index。适合read-intensive。

Conclusion

最后论文里测出来的结果Version Storage的格式对数据库性能有很大的影响，而不是传统认为的concurrency control protocols。而concurrency control protocols中，MVTO的效果最均衡，但是生产环境中居然没有数据库用这种算法。GC算法表现最好的是transaction-level GC。索引管理方面，logical pointer总是表现的更好。具体的workloads和测试方法可以看论文。

Reference

[1] An Empirical Evaluation of In-Memory Multi-Version Concurrency Control. VLDB ‘17