> 这期依然没有 Andy，我好怀念他
## 前言
### 多版本并发控制
(资料图)
多版本并发控制，是构建系统的一种方式，即通过维护多版本数据来做到并发执行事务
多版本并发控制的思路和乐观并发控制的思路很类似，它维护的是这些对象的不同物理版本，而不是为每个事务创建一个私有空间
对于全局数据库里面的部分数据，会有若干个版本，那么需要明确的是，是否需要将某个版本的数据对某一个特定的事务可见?
### MVCC 历史
在 MVCC 中，writer 不会阻塞 reader，reader 不会阻塞 writer
当有 2 个事务同时要对同一个对象尝试做写入操作时，就得退一步，使用某种并发控制协议，比如 两阶段锁或者使用时间戳
对于只读事务来说，MVCC 很有用，因为 SQL dialect 允许声明该事务是否是只读事务，那么数据库系统就不会去获取任何 Lock 或者维护 read set/write set。而因为它有一个一致的 snapshot，就只会看到该事务开始时就存在的那些修改，这就使得只读事务变得非常高效，而且执行速度也很快
本质上来讲，它就是在维护一个版本信息表之类的东西
MVCC 也支持 Time-Travel Query，通过这种查询，可以知道数据库之前的状态是什么
但是支持这种 feature，就永远不能将老版本的数据扔掉，永远不做垃圾回收，而随着时间的流逝，事务提交的数量会越来越多，磁盘空间很快就会满了
### MVCC 例子
MVCC 不依赖并发控制协议
在上图中的 Version 字段中，有一个值是 A0，说明对象 A 的版本号是 0
Begin 和 End 字段里面放的都是时间戳，它们的值始终增加
当一个新事务到达时，要去查看 T1 和 T2，当 T1 到达时，分配时间戳 1 给它
T1 执行 R(A)，这个时候要去查看表，通过弄清楚当前时间戳处于开始时间和结束时间中的哪个位置，来决定哪个 tuple 对它是可见的
此时 T1 的时间戳是 1，开始时间是 0，时间戳 1 是在 0 和无穷大之间，那么将 A 的版本号设置为 A0
T2 执行 W(A)，这里给 T2 分配的时间戳是 2，但是此时要创建 A 的一个全新版本，即 A1，这里要做的只是去增加版本号计数器
然后在 T2 中，要将 A0 的 end timestamp 设置为 2
整个过程中需要用到的就是事务状态表
但是如果这些事务被中止，那么就需要回过头去，将这些时间戳恢复原样
此时 T1 再执行 R(A)，那么此时 T1 要读取到的 A 版本是什么呢
是 A0，因为它的时间戳依然是在 begin timestamp 和 end timestamp 之间
例子 2
首先 T1 执行 R(A)，此时很明显，要读取的版本是 A0
然后 T1 执行 W(A)，更新 database
然后需要到 A0 这里，将它的 end timestamp 设置为 T1 的当前时间戳，即 1
然后开始执行 T2，那么此时 T2 执行 R(A)，要读取的是 A 的哪个版本呢?
是 A0，为什么?
其实这里取决于选择的隔离级别，它选择的可能是 A0 或者 A1，但假设它的隔离级别是 Serializable，此时它需要读取 A0，因为 A1 还没有被提交
然后 T2 执行 W(A)，这里遇上了 写写冲突，假设这里用的是两阶段锁，T2 必须等到 T1 提交后才能继续执行
切换回 T1，执行 R(A)
T1 会读取它上次刚修改过的版本，即 A1，然后做提交
此时再回到 T2，这个时候就要去创建 A 的新版本，即 A2，它的值是 789，然后将 A2 的 begin timestamp 设置为 2，end timestamp 设置为无穷大。然后将 A1 的 end timestamp 设置为 2
有非常多的数据库用到了 MVCC 这个技术
## MVCC 设计决策
### 并发控制协议
这些都是前面学过的，就不笔记了
### 版本存储
需要弄清楚某个 tuple 的哪个版本是可见的
假设要对整个 table 进行循序扫描，那就要知道应该在哪里找，才能找到想要的哪个版本的 tuple
如何实现这个功能?
去维护一个 internal pointer 的字段，那么就可以通过这个字段，找到该 tuple 的前一个版本或者下一个版本
可以把这个看作是一个链表，索引指向的始终是该链表的头节点
而版本存储主要有 3 个方案
#### Append-Only Storage
每当创建某个数据的新版本时，只需要复制该 tuple 的老版本，并将该副本作为 table 空间中的一个新的物理 tuple，并对其进行更新
例子
每个物理版本其实就是 Main table 中的一个新 tuple
假设现在有一个新事务，它要去更新对象 A，首先要做的是在这个 table 空间中找到一个空的 slot，然后它会去复制 A 的当前值，即 A1，并将这个值放入 table 这个空的 slot 中
然后 A2 也是，它会将这个修改后的值放入表中这个 slot 中
更新指针，让它指向当前插入的最新版本数据
这个由指针串联起来的链表，就有 2 种排序方式，从新到旧或者从旧到新
#### Time-Travel Storage
在这种方案中，有一个 master version table，这个里面保存的始终是对象或者 tuple 的最新版本
然后，将这些老版本数据复制到一个单独的 table 上，这个 table 就是 Time-Travel table，此时需要维护的就是 master version table 中指向 Time-Travel table 的指针
当数据库中的 tuple 被修改时，要将旧版本数据复制到这个表上，并维护这些旧版本的数据
更新过程就是如上图，假如现在要更新 A3，Time-Travel table 中有 A1 和 A2，A2 是新的，它用一个指针指向那个旧的 A 的值即 A1
最后需要更新指针，将指向 A3 的指针指向刚在 Time-Travel 表中插入的 A2
#### Delta Storage
最佳方案，可以类比成 git 里面的 diff，这样就不用每次都去复制这些老版本的数据，然后在它们的副本上进行更新了，只需要维护那些对前一个版本所做的修改就好了
每次要更新时，只需要将那些修改过的值复制到这个单独的 Delta Storage Segment 中即可
为了更新 A，要将这个值复制到右边的表上，表中的 delta 值存放的时该 tuple 中实际被修改过的属性值
然后在 Main table 中更新实际的值
类似的，插入新的值
这里只对该 tuple 的一小部分属性进行修改，也就没必要复制整个 tuple
Delta Storage 的缺点在于，必须要重新演算这些 Delta 值，以此来将 tuple 变回原来正确的值
## 垃圾回收
当事务在执行和结束时，所有老版本的数据都会积累在一起
在某个时候，某个特定版本的数据不会对其他任何活跃的事务可见，也就是说，在这些老版本数据的 begin timestamp 和 end timestamp 范围之内，没有活跃事务的时间戳
所以这个时候，这些数据都是占空间的，需要回收，以此来释放空间
那么该如何查找那些过期的版本数据呢?
如何及时回收这些数据才是安全的呢?
(15-721 会讲)
垃圾回收级别有 2 种，tuple 级别和事务级别
tuple 级别: 对 table 进行循序扫描，通过使用版本时间戳和那些活跃的事务来确定这些版本是否过期，如果过期，就清楚掉(需要查看内存中的 page 里的那些数据，还需要查看那些交换到磁盘上的那些 page)
事务级别: 当这些事务提交时，事务会去维护它们的 read set 和 write set
### tuple 级别 GC
通过使用 background vacuuming , 在后台运行一些线程，它们会执行这种清理，定期对 table 进行全 table 扫描，看哪些版本时可以被清理的，主要还是通过查看当前事务的时间戳
在上图的例子中，从这 2 个事务中拿到了 2 个时间戳，即 12 和 25，然后去查看数据版本的 begin timestamp 和 end timestamp
A100 和 B100 的时间戳范围时 1 到 9，而 12 和 25 不属于这个范围，所以它们不可见，那么就可以安全回收 A100 和 B100
### tuple 级别 GC 优化
为 dirty page 维护一个 bitmap，当更新数据时，可以翻转修改的那个 page 对应的 bit，以此来表示这个 page 变 dirty 了
所以在数据库中，会为其所有的 page 维护一个 bitmap
那么当 Vacuum 开始工作时，它立刻就能知道哪些 page 需要被清理，并将该 page 对应 bit 重置为 0
Cooperative Cleaning 这种方案是这样的，当线程在执行查询时，当它们遇到旧版本数据时，因为这些数据时不会再用的，所以它们会把这些数据清理掉
Cooperative Cleaning 这种方案，是否适用于从新到旧这种顺序呢
答案是 No
如果是按照从新到旧的顺序，就没办法查看那些旧事务了，因为这样就直接找到目标了，也就没有必要遍历其他数据了，那么其他旧数据的空间也没有办法做回收了
所以它的顺序只能是从旧到新
例子
假设 T1 要通过索引来找对象 A
它会落在 version chain 的头节点处，即 A 的最旧的那个值的地方
然后它会沿着这个对象的 version chain 进行扫描，来确定该数据的哪个版本是对其可见的
如果 T1 知道它正在遍历的某个版本对于其他事务来说是不可见的，那么这些版本就会被标记为 deleted ，并最终被回收
最后索引得到更新，让它指向这个 version chain 的新的头节点
在物理删除这些数据或者回收这些空间之前，可以先更新索引，让它指向 A2
### 事务级别 GC
只需要维护事务的 read/write set，通过它们来弄清楚哪些版本数据不再可用，然后再去回收这些空间
## 索引管理
要对索引进行更新，让它指向该 version chain 的新头节点
但在更新主键时，这会有点麻烦(主键索引指向的永远是 version chain 的头节点)
因为对于同一个逻辑 tuple 来说，是有可能会出现 2 个 version，即新的和之前旧的
比如，当要更新主键时，先执行 delete，紧接着再插入一个新的逻辑 tuple
### 非主键索引
1. 通过维护一个逻辑指针来确保索引反映了 version chain 中的正确值，而每个 tuple 都有一个唯一标识符，这个不会改变。同时也有一个间接层，就是将 tuple 的逻辑 id 映射到数据库中的物理位置，每当要更新 version chain 时，只需要更新这个间接层即可，无需更新每个索引
2. 使用物理指针
例子
使用主键查找 A，对于主键来说，它就是一个物理地址，它由 page id 和 offset 组成。通过 page id，可以知道这个对象在哪个 page 上，通过 offset，可以知道它在该 page 的哪个位置上
也可以使用物理地址来作为非主键索引使用，但是每当更新某个 tuple 时，也必须对非主键索引进行更新，让它也指向这条链的头节点
对于 OLTP 数据库来说，一个 table 上有多个非主键索引，所以每当要更新 version chain 时，就需要更新所有的非主键索引，所以这样成本就很高
所以与其在非主键索引中存物理地址，不如存逻辑指针
这里通过非主键索引来指向主键索引，所以如果现在要查一个数据，首先需要通过主键索引查找，而不是非主键索引
这样更新 tuple 和它对应的 version chain 的头节点时，可以只更新主键索引，也就自动更新了所有的非主键索引
另外一种方案是，有像 tuple id 那样的合成值，这个值通常是由一个计数器来弄出来的，然后有个 hash table，通过这个将 tuple id 映射到对应的物理地址上
现在，通过非主键索引来获取 tuple id，然后通过 tuple id 拿到对应的地址，就能够对数据进行访问了
这样也能做到，每次要更新 version chain 时，也能避免更新所有的非主键索引，唯一要去更新的就是那个映射地址的 hash table 和指针
## MVCC 实现
## 结论
关键词：
