Multi-Version Concurrency Control
多版本并发控制（MVCC）是一个比并发控制协议更大的概念。它涉及数据库管理系统设计和实现的所有方面。MVCC是数据库管理系统中应用最广泛的方案。在过去10年中，几乎每一个新的DBMS都使用了它。甚至一些不支持多语句事务的系统（如NoSQL）也使用它。
通过MVCC，DBMS在数据库中维护单个逻辑对象的多个物理版本。当事务写入对象时，DBMS将创建该对象的新版本。当事务读取对象时，它读取事务启动时存在的最新版本。
MVCC的基本概念 /好处是writers不会阻塞writers，readers也不会阻塞readers。这意味着一个事务可以修改对象的同时其他事务可以读取旧版本。
使用MVCC的一个优点是只读事务可以读取数据库的一致快照，而无需使用任何类型的锁。此外，多版本DBMS可以轻松支持time-travel查询，这是基于数据库在其他时间点的状态的查询（例如，像3小时前一样对数据库执行查询）
MVCC有4大方面的设计考虑:
- 并发控制协议
- 版本存储
- 垃圾收集
- 索引管理
并发协议的选择是在前面讲座中讨论的方法（两阶段锁定、时间戳排序、乐观并发控制）之间进行的。
Version Storge
Version Storge是DBMS如何存储逻辑对象的不同物理版本，以及事务如何找到对其可见的最新版本。
DBMS使用元组的指针字段为每个逻辑元组创建一个版本链【version chain】，它本质上是一个按时间戳排序的版本链表。这允许DBMS在运行时找到特定事务可见的版本。索引始终指向链的“头”，这是最新或最旧的版本，具体取决于实现。线程遍历链，直到找到正确的版本。不同的存储方案决定了每个版本的存储位置和内容。
Approach #1 Append-Only Storage
逻辑元组的所有物理版本都存储在相同的表空间中。
版本被混合地存放在表中，每次更新只是将元组的新版本追加到表中，并更新版本链。
version chain有两种排序方法，一种是oldest-to-newest（O2N），这需要在查找时进行遍历。另一种是newest-to-oldest（N2O），这需要为每个版本更新索引指针
Approach #2 Time-Travel Storage
DBMS维护一个单独的表，称为时间旅行表，该表存储元组的旧版本。每次更新时，DBMS都会将元组的旧版本复制到时间旅行表中，并用新数据覆盖主表中的元组。主表中的元组指针指向时间旅行表中的过去版本。
Approach #3: Delta Storage
与时间旅行存储一样，DBMS只存储增量，而不是整个过去的元组，或者元组之间的变化，称为增量存储段。然后，事务可以通过迭代增量来重新创建旧版本。这导致写入速度比时间旅行存储更快，但读取速度较慢。
Garbage Collection
DBMS需要随着时间的推移从数据库中删除可回收的物理版本。
回收的两种情况：
- 该版本对当前所有的活动事务中都不可见
- 该版本是由中止的事务创建的
Approach #1: Tuple-level GC
通过元组级垃圾收集，DBMS通过直接检查元组来查找旧版本。
- Background Vacuuming：单独的线程定期扫描表并查找可回收的版本。这适用于任何版本的存储方案。一个简单的优化是维护一个“脏页位图”【dirtypage bitmap】，该位图跟踪自上次扫描以来修改的页面。这允许线程跳过未更改的页面
- Cooperative Cleaning：工作线程在遍历版本链时标识可回收版本。这仅适用于O2N的version chain
Approach #2: Transaction-level GC
在事务级垃圾收集下，每个事务负责跟踪自己的旧版本，这样DBMS就不必扫描元组。每个事务都维护自己的读/写集。当事务完成时，垃圾收集器可以使用它来标识要回收的元组。DBMS确定由完成的事务创建的所有版本何时不再可见。
Index Management 索引管理
所有主键索引始终指向version chain head
DBMS更新pkey索引的频率取决于更新元组时系统是否创建新版本。如果事务更新pkey属性，则这将被视为先删除后插入。
管理二级索引的方法有两种：
- Logical Pointers：DBMS对每个元组使用固定的标识符，该标识符不变。这需要额外的间接层，将逻辑id映射到元组的物理位置。然后，对元组的更新可以只更新间接层中的映射。
- Physical Pointers：DBMS使用版本链头的物理地址。这需要在更新版本链头时更新每个索引。