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

介绍

MVCC是目前最流行的并发控制协议，本文是论文原文的翻译，省略掉实验部分，感兴趣的同学可以去参照论文原文。这篇论文从4个方面分析了MVCC设计取舍，包括如下:

  • concurrency control protocol
  • version storage
  • garbage collection
  • index management

简介

MVCC概述

MVCC最大的优点是能够让数据库有更大的并发量，例如一个使用MVCC的数据库管理系统(DBMS)可以同时让一个事务读取一条数据的老版本而另一个事务更新同一条数据。MVCC的这些优点让它成为了近几年数据库的最佳选择，下表(表1)总结了近三十年来数据库MVCC的一些实现。

DBMS元数据

MVCC DBMS为事务以及元组维护着一些相似的元数据。

  • 每一个事务都有一个全局唯一且递增的事务Tid，并发控制协议会使用Tid标识被访问的元组。

  • 每一个元组的头部有四个元数据字段，如图1。txn-id是元组的write-lock，如果一个元组没有被write-locked，那么这个字段就为0。

    当一个事务T(Tid)更新元组时，DBMS会检查该元组是否为0，如果为0，那么DBMS使用原子性操作设置txn-id为Tid。任何事务尝试更新一个txn-id不为0或不等于Tid的元组时都会被DBMS abort掉。begin-ts和end-ts表示元组的生命周期，这两个字段的初始值都为0。当元组被删除掉后，DBMS会设置begin-ts为INF。最后一个字段pointer存储着下一个版本元组的地址。

concurrency control protocol

每一个DBMS都包含并发控制协议，并发控制协议起着控制事务访问特定元组，事务是否能提交的作用。

Timestamp orderding(MVTO)

MVTO除了表1元组所有的字段外，MVTO还包含了一个额外的字段read-ts，这个字段表示最后一个读取该元组的事务。

当事务在元组A发起一个读操作，DBMS会查找begin-ts <= Tid <= end-ts*的元组，如下图(a)，如果元组Ax的写锁(*txn-id == 0 || txn-id == Tid)没有被其他事务获取到，那么事务T被允许访问Ax，MVTO不允许事务read uncommitted。如果事务不能访问Ax，那么就只能访问Ax的老版本数据。

MVTO总是更新元组的最新的版本，如果没有活跃的事务获取到Bx的写锁并且Tid比Bx的read-ts大，事务T会新建一个版本Bx+1，设置Bx+1的txn-id为Tid，当T提交的时候，DBMS分别设置Bx+1的begin-ts和end-ts为Tid和INF，Bx的end-ts为Tid。

Optimistic concurency control(MVOCC)

乐观并发控制的(OCC)的初衷在于DBMS假设事务之间冲突很少，因此事务不需要锁来协调访问控制，这就减少了事务持有锁的时间。

MVOCC协议分为三个阶段。当一个事务开始时，事务处于read phase，在这个阶段里面，事务可以对元组读写操作，和MVTO一样，当事务读一个元组时，DBMS会搜索该事务可见的版本(begin-ts <= Tid <= end-ts)。当事务写一个元组时，只有write-lock没有被其他事务获取到才行，例如事务T更新Bx时，DBMS会新建一个Bx+1版本的元组并且设置Bx+1的txn-id为Tid。

image-20191029111315549

当事务提交时候，事务进入validate phase，DBMS会验证事务的read-set是否被其他事务更新过，如果事务通过了validate phase的检查，那么事务就进入到write phase，DBMS会把事务写的数据写到文件，并且把元组的begin-ts设置到Tid，end-ts设置为INF。MVOCC和MVTO相比，MVOCC把事务分成了三个阶段，其中的validate phase就是检查事务的元组是否已经被其他事务写过了，MVTO并没有这个阶段，取而代之的是用read-ts来标识事务的顺序，保证了事务的隔离性。

Two-phase Locking(MV2PL)

两阶段加锁有两个阶段，第一个阶段是膨胀阶段，在这个阶段里面，事务只能获取锁，不能释放锁，第二个阶段是收缩阶段，在这个阶段里面事务只能释放锁不能获取锁。MV2PL的写锁是txn-id，读锁是read-cnt，read-cnt表示当前读取这个元组的活跃事务。当事务读一个元组时，DBMS会搜索事务可见的版本，当这个版本是可见时，如果该版本的txn-id为0，事务会增加read-cnt。同样的，只有txn-id为0并且read-cnt为0时，事务才能进行写操作。

image-20191029112911934

2PL协议的关键点在于对死锁的处理上，之前的研究表明no-wait策略是扩展性最强的策略。当事务发现不能获取到锁时，事务直接abort，因为事务从不等待，那么我们也就不需要一个后台线程来探测死锁了。

Serialization Certifier

这个策略我没有过深入的研究，不过有一篇PostgreSQL的论文是和这个主题相关的(Serializable Snapshot Isolation in PostgreSQL)，论文主要是依靠检测事务之间的依赖来实现隔离性的，如果事务之间的依赖有问题，那么DBMS会通过一些策略abort掉一些事务。

Version storage

版本存储具体说明了系统是如何存储元组的版本以及每个版本都包含哪些信息。DBMS采用元组的pointer字段形成了版本数据的链表，这个链表允许定位对事务可见的版本。链表的头可以是最新的版本，也可以是最老的版本，论文主要偏向于UPDATE操作时的取舍，因为UPDATE操作才会增加新版本数据。

Append-only storage

在这种存储结构中，事务更新数据时首先会从表中获取一个空的slot，然后把之前的版本数据复制到这个空的slot，最后把要更新的数据更新到这个slot中。Append-only storage设计的关键点在于如何管理版本链表的顺序，这个顺序隐含着事务更新索引的频率。

Oldest-to-Newest

在O2N这种顺序中，链表头部是最老版本的数据，如下图。O2N的优点在于不需要在更新数据的时候调整索引的指针，但是缺点也很显然，DBMS需要遍历一个长链表才能到达最新的数据。

image-20191031113148916
Newest-to-Oldest

在N2O这种顺序中，链表头部是最新版本的数据，如下图。大多数DBMS都会访问最新版本的数据，因此N2O不需要遍历一个长链表，但是N2O的缺点是不论何时链表的头部发生了变化，DBMS都会去更新所有的索引去指向最新的链表头部。在下面的章节里面，我们会讨论引入一个间接的映射层来提供索引到间接层，间接层到物理数据的映射，索引指向间接层而不是直接的物理地址。

image-20191031114538968
Time-travel storage

Time-travel strorage类似于上面的append-only storage，不同点在于老版本数据存储在分开的表中。DBMS存储了一个主版本在主表中以及一些其他的版本在另外一个分开的表中。time-travel storage引入了一些GC中的消耗，当进行GC时，DBMS需要把time-travel storage表中的数据拷贝到主表中。为了简单起见，论文只考虑了主表中是主版本的情况。

当更新一个元组时，DBMS在time-travel表中首先获取到一个空的slot，然后从主表中拷贝数据到这个空的slot中，然后再更新数据的主版本。索引总是指向数据的主版本，所以索引数据不用修改。

WX20191107-135056@2x
Delta storage

在delta storage中，数据库主版本在主表中，增量修改的版本在delta table中。当更新一个元组时，DBMS并不会拷贝整个元组而是只把被修改的字段拷贝到delta table中。只更新元组的部分字段时，这种方案特别适合，但是在读占大多数请求的时，这种方案带来的消耗很大，因为读一行数据需要DBMS遍历版本链表多个字段的多个版本(读放大)。

讨论

没有一种方案是通用的，数据库的不同负载，不同方案有最优的表现。append-only方案对于large scan的分析查询很合适，因为数据都是连续存放在内存中，这减少了cpu的cache miss，数据都连续在内存中也是硬件进行prefetch的理想条件。但是当访问老版本的数据时，DBMS必须遍历版本链表才能定位到一个合适的版本，append-only方案也直接暴露了数据的物理地址给索引，引入了额外的索引管理消耗。

所有的存储方案都需要在DBMS中集中分配数据，多线程访问会导致访问竞争。一种解决方案是DBMS维护一块额外的内存区域使用并且每次增长的大小固定，每个工作线程都从一个地方获取内存，这也是一种分区的方案，因此也减少了访问竞争。

Garbage Collection

MVCC在更新数据时会新增数据，如果不及时清理掉废弃的数据那么磁盘空间肯定会使用完，在访问数据的时候，DBMS会遍历版本链表，如果链表过长，也会影响数据库的性能，所以数据库的性能和GC有着密切的关系。

GC步骤被分为三步：

  • 检测过期的版本
  • 把版本数据从相关链表以及索引中unlink
  • 回收掉数据的存储空间

DBMS认为如果数据是无效的(比如由abort的事务生成)或者数据对现有的活跃事务不可见，那么数据就是过期的，对于不可见的版本，需要满足条件是版本end-ts < Tid。

目前有两种MVCC GC实现，不同的地方是他们如何检测过期的版本。第一种是tuple level GC，DBMS会去检查单个元组的可见性。第二种transaction-level GC会去检测完成事务的创建数据的版本是否可见。需要注意的是不是每一种GC方式都与所有的存储方案兼容。

Tuple-level Garbage Collection
Backgroup Vacuuming(VAC)

DBMS中有一个后台线程定期扫描数据库来找到过期的版本。在上面的表1中可以看出这是最常见的方式，实现很容易并且可以和所有的版本存储访问兼容。但是这种方式的扩展性不好，一种更好的扩展性方式在论文SpeedyTransactionsin Multicore In-Memory Databases中，在GC过程中还有另外一种优化，用一个bitmap来标记出脏的数据块。

Cooperative Cleaning(COOP)

事务执行的时候，DBMS会遍历整个版本链表来找到可见的版本，把过期的数据注册到一个全局的数据结构中。因为没有专门的GC线程，所以这种方式扩展性良好，但是COOP只适用于O2N存储。COOP的一个缺点是如果数据没有被访问到，那么过期的版本数据就不会被清理到，在SQL Server Hekaton中，这被称为dusty corner。DBMS可以和VAC一样定期来一次complete GC来克服这个缺点。

image-20191107151059457
Transaction-level Garbage Collection

在这种GC机制中，数据进行GC的粒度是事务。DBMS认为当一个事务创建数据所有的版本对当前活跃事务不可见时，事务是过期的。当epoch结束时，属于这个epoch的事务生成数据的版本都是过期的，可以安全的删除掉。这种方式的缺点是DBMS得追踪事务的read/write set而不仅仅是使用epoch。

image-20191107151710062
讨论

Tuple-level gc是最常见的GC方式，在上面两种方式中，增加GC线程的数目都可以加速GC。数据库性能会在长事务情况下下降，这是因为在长事务情况下产生的数据不会及时被回收掉。

索引管理

所有的MVCC DBMS都独立于版本信息管理索引。因此，在索引中存在一个key意味着在数据库中存储着某个版本的数据，但是索引并不知道到底是哪个版本存储着的数据匹配。定义index entry为key/value对，key是指向元组的被索引字段，value是指向对应的元组。DBMS会根据value的指针遍历版本链表来找到可见的元组。