多版本并发控制

1.简介¶

MVCC指的是对数据进行多版本控制，避免事务并发时因为锁而导致的阻塞，从而优化事务的并发性能。

对于一个数据库中的逻辑对象来说，它拥有多个版本。其中，当事务对对象进行写的时候，就会创建一个该对象的最新版本；若事务对对象进行读的时候，他会读到事务创建时存在的最新版本。

MVCC的核心思想是写不阻塞读，读不阻塞写。即在一个事务读到数据库中的对象时，是允许另一个事务去修改该对象的。在之前的并发控制中，另一个要去修改该对象的事务要么会获取不到锁（2PL），要么会使得一方放弃（OCC）。

但MVCC仍有写写冲突，发生的时候就需要借助之前的并发控制协议了。

因此，MVCC主要有四方面的内容：

其中并发控制协议的选择在之前的文章中已经提到了，在这里不重复介绍。

主要是关于数据库如何存储一个tuple的不同版本，以及如何去寻找旧版本。有三种主要的方式，它们基本都是通过链表实现的：

Append-Only Storage:一个Table中存储多个版本的tuple，其中对于同一个tuple的不同版本，有一个指针指向其最新或最旧版本，且其中的不同版本根据版本时间排序，由指针串联。
Time-Travel Storage：维护两个table，main table存储最新版本的tuple，指向time-travel（旧版本table）的上一个版本，且time-travel的同一tuple不同版本根据时间排序串联。
Delta Storage：也是维护两个table，包括最新版本的main table，区别是另一个table为delta storage segment，记录了该tuple的历史变化。

若指针指向的是最旧版本，在不需要记录一段时间内版本的情况下，垃圾回收十分方便。

Append-Only Storage方案虽然需要更多空间，但是不需要对一个tuple进行类似回滚的操作，只需要找到需要的版本就可以了。而Delta Storage虽然占用空间更少，但是若需要找到某一个特定版本，需要利用变化的记录进行回滚。

除了特定场景需要记录一段时间的Version以外，对于没有事务会用到的过于旧的版本是可以被清除掉的，否则随着时间的增加，占用的空间会越来越多。

Garbage有两种方式：

Tuple-Level：一个后台线程定期进行全表扫描，对比活跃的事务看看该tuple是否还有事务可能会使用。
Transaction-level：事务维护read set和write set，在事务提交的以后就可以根据read set和write set查看哪些事务不会再被使用了。

Primary Key索引需要总是指向最新版本的tuple。当事务更新tuple的时候，事务对该Primary key索引执行DELETE tuple，然后再执行INSERT tuple完成更新。

Secondary index的维护更加复杂，有两种方案：

Logical Pointers：类似存储层的Storage Manager，通过唯一的tuple_id（page_id+offset）唯一映射到物理层面上的tuple。此时，index只需要存有tuple_id即可，更新都在这个中间的转接层即可。
Physical Pointers：直接指向物理层面的tuple，若采用这种方式，更新版本的时候需要更新所有的索引。

当然对于回表的Secondary index，由于它总是指向Primary index，因此无需更新。