《An Empirical Evaluation of In-Memory Multi-Version Concurrency Control》学习笔记

Motivation

多版本并发控制（Multi-version concurrency control，MVCC）目前是现代数据库管理系统（DBMS）中最热门的事务管理策略。在处理事务时，维护数据的多个版本以在不牺牲串行性的同时提高并行性。但是在多核和内存中扩展 MVCC 并非易事：当有大量线程并行运行时，同步带来的开销可能超过多版本带来的好处。

为了理解在现代的硬件配置下处理事务时 MVCC 如何执行，论文对 MVCC 的 4 个关键设计决策进行了大量研究：并发控制协议、版本存储、垃圾回收、和索引管理。

背景

MVCC 的基本想法是，DBMS 为数据库中的每个逻辑对象维护多个物理版本，让只读的事务访问元组的旧版本，而不会阻止读写事务在同时生成新的版本。

实现方式有多种：

Append-only
Time-travel
Delta

无论实现方式如何，MVCC DBMS 都会维护用于事务和数据库元组的通用的元数据。

事务： 当事务 $T$ 首次进入 DBMS 系统时，DBMS 会为该事务分配一个唯一、单调递增的时间戳作为它的标识符( $T_{id}$ )。并发控制协议使用这种标识符来标记事务访问的元组的版本。一些协议还用它作为事务串行的顺序。

元组： 每个 “物理” 版本在它的头部中都包括 4 个元数据字段，DBMS 用它来协调并发事务的执行

+----------------------------------------------------------------------------+
| txn-id | begin-ts | end-ts | pointer | ... |            columns            |
+----------------------------------------------------------------------------+
|<--               header                 -->|<--          Content        -->|

txn-id 用作版本的写入锁。如果 tuple 没有被锁定，那么该字段会被置零。当 txn-id != 0 && txn-id != self.txn-id，该事务会被打断
begin-ts: 该版本的起始时间戳
end-ts：该版本的结束时间戳

并发控制协议

是否允许某个事务访问或修改一个特定的 tuple Version
是否允许某个事务提交修改
![[concurrency-control-protocols.png]]

Timestamp Ordering

使用事务标识符 $T_{id}$ 来预计串行顺序，其 Version header 中还额外保存了最后一次读取它的事务的标识符 (read-ts)。

如果读取的 tuple 的 read-ts 小于 $T_{id}$ ，就更新该 read-ts。
写入时，要求没有活跃的事务持有锁，并且 $T_{id} > read-trs$ （不能写入未来读取过的数据）。如果更新成功，创建一个新版本，并设置 $begin\_ts = T_{id}, end\_ts = INF$ ，并更新被更新版本的 $end\_ts = T_{id}$

MVTO 只会更新最新版本的数据

Optimistic Concurrency Control

OCC 的动机是假设事务不太可能会产生冲突，所以不需要获取锁，在提交时再检查是否有冲突，因此 OCC 将事务划分为三个阶段：

read phase: 找到一个能够访问的版本，
validation phase: DBMS 给事务赋予一个 $T_{commit}$ 时间戳来表明事务的串行执行顺序，然后判断失误的 read set 是否已经被其他事务更新过了
write phase：如果 validation phase 通过了所有检查，就可以将更新的版本设置为可见了( $begin\_ts = T_{commit}, end\_ts = INF$ )

注意，事务只能更新最新版本的 tuple

可能导致长期运行的只读事务饥饿

Two-parse Locking

每个事务在读取或者修改前需要获取锁，在记录磁盘的数据库中锁不需要落库，所以一般会与 tuple 分开存储。但是在基于内存的数据中，可以将锁存储到 tuple 的 header 中。（txn-id for write, read-cnt for read)

需要访问数据时，找到一个版本 $begin\_ts \lt T_{id} \lt end\_ts$

读取，查看 tuple 的 txn-id 是否为 0，如果为 0，增加 read-ts
写入，查看 tuple 的 txn-id 是否为 0，并且 read-ts 也要为 0。如果都为 0，就可以更新一个新的版本
提交时，将新创建的版本的 tuple 的 begin-ts 修改为新指定的 $T_{commit}$ 并释放所有的锁

2PL 的一个问题就是会造成死锁，论文中说 no-wait 是可伸缩性最高的一种方法，即一旦遇到锁冲突，事务就会被终止

Serialization Certifiier

维护一个串行图来检测并移除 “dangerous structures"。在若隔离级别之上使用基于认证的方法从而提供更好的性能

SSI(Serializable snapshot isolation)，通过避免写偏斜(write-skew) 来确保串行性以提供快照隔离级别。SSI 使用事务标识符来查找 tuple 可见的版本，只有当 tuple 的 txn-id 为 0 时事务才能更新该版本

TODO

Version Storage

tuple 的 pointer 属性形成了一个版本链(version chain)，允许事务超找到想要访问的版本。这个链表的 head 要么是最新的版本，要么是最老的版本。

Append-only Storage

一个 table 的所有 tuple Version 存储在同一个 space 中，Postgres 采用这种方式。更新时获取一个 empty slot，然后将当前版本复制到该 slot，然后将修改应用到该 slot 对应的版本中

关键点是如何组织版本链的顺序：

Oldest-to-Newest(O2N)，版本链的头部是最老的版本，可能对所有活跃事务不可见。
- 优点是当 tuple 更新时，不需要修改 head 和索引(索引指向 head)
- 但是需要遍历链表找到最新版本，污染 CPU 缓存
Newest-to-Oldest(N2O)，版本连的头部是最新的版本。
- 查找最新版本速度快，
- 缺点是每次 tuple 修改时都需要改变版本链的 head，然后更新该表的所有索引。 ➡️ 提供最新版本到物理地址的映射，索引执行映射的 entry 而不是物理地址

Append-only Storage 的另一个问题是如何处理 non-inline attribute(e.g. BLOB)，因为会产生复制开销（即便更新的不是 BLOB，也需要复制）➡️ 允许同一个 tuple 的不同物理版本指向相同的 non-inline data

Time-Travel Storage

与 Append-only Storage 类似，区别是旧版本存储在另一个 space，在 main table 中只存储最新的版本(SQL Server)或最老版本(SAP HANA)(会对 GC 造成影响)。下面只针对前者讨论

更新时，需要先在 time-travel table 中获取一个 slot，然后将 main 中的版本复制到该 slot，然后修改 main table 中的版本。注意：索引不会受到影响，因为他们总是执行 master Version

Time-Travel Storage 同样也有处理 non-inline attribute 的问题

Delta Storage

与 Time-Travel Storage 类似，不过 time-travel table(delta storage) 中并不存储完整的 Version，只存储修改属性原来的值。在 MySQL 和 Oracle 中这部分指向了 rollback segment

对更新操作友好，减少了内存消耗。但是对读密集型负载会产生更高的负载（需要遍历版本链找到需要的每一个属性）

Discussion

Append-only Storage 在执行大规模扫描的分析查询中表现更好（因为不同版本在内存中连续存储，减少 CPU 缓存 miss，并且适合硬件 prefetch）。但是访问旧版本的查询开销更高。并且会将物理版本暴露给索引，这会造成额外的索引管理开销

这些策略都需要 DBMS 在 centralized data structures 中为每个事务分配内存，会导致 contention。➡️ 为每个中央数据结构分别维护单独的内存空间，并以固定大小的增量扩展它们。随后每个工作线程将获取单独的内存空间。这本质上是对数据库分区，从而消除集中地争用点。

GC

如果一个版是无效的版本（即由被打断的事务创建）或对任何活动的事务都不可见( $endts \lt \min(T_{id}$ )，那么 DBMS 会认为该版本是过期的。DBMS 会维护一个中央数据结构来追踪 end-ts 是否比所有活跃事务的 $T_{id}$ 都小，但是这会在多核系统中成为可伸缩性的一个瓶颈

内存式的 DBMS 可以通过粗粒度的（coarse-grained）基于 epoch（epoch-based）的内存管理来追踪被事务创建的版本已解决这一问题。该方法中，系统中有一个活跃的 epoch 和一个 epoch FIFO 队列。

一定时间后，DBMS 会将当前活跃的 epoch 移动到 epoch 队列中，并创建一个新的活跃 epoch。
DBMS 将新事务注册到活跃的 epoch 中。
每个 epoch 都记录分配给它的事务的数量。注册事务时计数器增加，事务完成时从 epoch 中移除（可能不是当前活跃的 epoch），并减小其计数器。
如果一个非活跃的 epoch 的计数器变为零（即事务都不活跃了）且其之前的 epoch 没有活跃的事务了，那么可以安全地回收在这个 epoch 中被更新的版本。
epoch 的变换可以由后台线程执行，也可以由 DBMS 的工作线程以协作的方式执行。

Tuple-level GC

后台清理（Background Vaccuuming，VAC）： 使用后台线程定期扫描数据库以查找过期的版本。

协同清理（Cooperative Cleaning，COOP）： 当执行事务时，遍历版本链时识别过期的版本并将它们记录在全局数据结构中。只适用于 O2N 的仅追加存储。如果事务不遍历某个元组的版本链，那么系统永远都不会移除其过期的版本。

Transaction-level GC

如果某个事务锁生成的 Version 对与所有活跃事务来说都是不可见的，那么就可以认为该 Version 是过期的，是可以被删除的。当 epoch结束时，该 epoch 中所有该事务的 Version 就可以清除了（注意是两点要求：1. version 属于该 epoch；2. version 属于该事务）

缺点：需要跟踪每个 epoch 中事务的读写集合（无法利用 epoch 中的计数器）