CMU15445课程笔记

多版本并发控制

多版本并发控制讲的是Mvcc。 即维护单个逻辑对象的多个物理版本， 这样当一个事务读取某个对象的时候不会阻塞其他事务写入该对象； 反之亦然。 但是Mvcc不保护写写冲突， 对于这种情况， 可能需要其两阶段锁之类的其他控制协议。

Mvcc可以实现： 只读事务并发时， 无需使用锁， 即可达成读层次的一致性快照； 并且在Mvcc中， 时间戳是用来确定某个对象的某个版本对于事务的可见性； 不带垃圾回收机制的Mvcc允许DBMS支持时间旅行查询（基于某个时间点的状态进行的查询)

时间旅行查询的一个例子： 比如对方想要查询这个表三星期前的某个数据， 现在我们只需要找到三星期前的时间戳， 然后读取即可。——这是在不做垃圾回收机制的情况下。 Postgres有一开始推崇时间旅行查询到砍掉这一机制的原因就是因为要支持垃圾回收机制， 因为如果不支持垃圾回收机制， 那么存储空间很快就会耗尽。

快照隔离

实现的基本思路是： 对于事务TS(1)和事务TS(2)。 然后对于对象A， 两个事务要对A做一系列操作如下：

      TS(1)             TS(2)
|     Begin      |                |       
|                |                |
|     R(A)       |                |
|     W(A)       |     Begin      |
|                |     R(A)       |
|                |     W(A)       |
|     R(A)       |                |
|                |                |
|     COMMIT     |                |

• 首先， TS(1)事务和TS(2)事务开始时， 要建立一个一致性视图， 视图有一个时间戳， TS(1)先Begin， 建立时间戳为1的视图。

• Database(Buffer Pool）中要维护一个对于A的版本链， 一开始版本A0， 开始时间戳begin-ts 为0， 结束时间戳end-ts为∞；

  •     A0 | 0 | ∞ |
    

• 然后， TS(1)进来了， 他一开始读取R(A), 对于A的版本链没有任何影响。

  •     A0 | 0 | ∞ |
    

• TS(1) 执行W(A), A被修改出新版本A1, A1的开始时间戳就是TS(1)的时间戳1， 并且因为A被修改了， 所以上一个版本， 也就是A0被限制了， 它的结束时间戳不再是无穷大了， 变成了版本A1出现的时间戳。

  •     A0 | 0 | 1 |A1 | 1 | ∞ |
    

  • begin-ts和end-ts就可以理解为某个版本所持续的时间。这就可以理解为如果没有人修改A， 那么最新的版本就是版本链的最后一个版本， 并且这个版本的有效性可以持续到无穷时间以后， 但是有人修改A了， 这个版本的持续时间就只存在于这一段时间了。

• 然后对于TS(2)， 他Begin了， 创建一致性视图， TS(2)的时间戳为2。 然后TS(2)此时想要读取A， 能否读取一个对象要看三个规则：

  • 自身携带的时间戳是否大于版本的end-ts， 如果大于， 则看不到。
  • 如果自身携带的时间戳处于begin-ts ~ end-ts之间， 那么观察一下active table（这也是一张表， 包含了当前正在活跃的事务） 中这个版本的begin-ts所在事务是否在活跃， 即没有提交。 如果提交了， 可以看到， 没提交， 看不到。
  • 如果自身携带的时间戳等于begin-ts, 即是这个版本的创建者， 可以看到。

• 所以这里TS(2)读取A得到了A0版本。 然后W(A)， 但是TS(1)此时正在持有锁， TS(2)要阻塞， 直到TS(1)提交。 当然， 中间TS（1）还有一次R(A), 但是因为TS(1)是A1的创建者， 则可以看到A1。然后提交。

• TS(2)获取写锁，W(A), 此时最新的版本变成了A2， begin-ts为2, end-ts为∞；A1则修改end-ts变成2，因为A1只存在于A1 ~ A2这段时间就被TS(2)写入A2逻辑上覆盖了。

  •     A0 | 0 | 1 |A1 | 1 | 2 |A2 | 2 | ∞ |
    

版本存储

对于版本控制有不同的版本控制方案。 版本控制总是一个类似链表的数据结构。 链表内存放了保存的逻辑元组， 以及连接到这个逻辑元组的下一个逻辑元组， 可以是单链表，也可以是双链表。

不同点是这个链表的头指针是新是旧， 遍历方式是从新到旧还是从旧到新， 亦或者这个逻辑元组里面存储的具体内容。

仅追加存储

仅追加存储就是每当更新新的版本， 就将旧的版本作为新元组追加到版本链中。

具体细节就是当来了一个新的元组， 然后就把他插入这张表中， 因为对于数据库中的每一张表， 都会被分配一个表空间存储这些元组。然后每次更新元组， 比如更新A， 那么就要跟新A的版本链， 让A的版本链中最新的节点指向新更新的节点。 这里的问题就是每次链接版本链， 都要从表中查找该数据的头节点。

并且版本链的排序也很重要， 因为如果是从新到旧， 那么插入新元组的时候直接找到版本链的头节点就可以了； 但是如果是从旧到新， 那么插入新元组的时候就不仅仅需要找到版本链的头节点， 还要遍历整个版本链。

另外对于从旧到新， 我们这里查找表头可能索引， 比如我利用索引查找到对应的记录ID，然后找到版本链的链头， 然后遍历整个链表， 根据节点的begin-ts和end-ts查找当前版本是否符合要求或者追加新节点。

对于从新到旧， 虽然让你我们查找到链头， 可以很快的查找到最新的节点， 但是这只是听起来很棒。 这只是查询， 如果我们要追加新节点， 那么我们因为维护大量了的索引。 就要更新所有指向这个头结点的索引， 确保他们都指向新的链头。

这里面有很多细节问题， 目前不知道， 比如： 这些跟踪索引利用索引键跟踪，如果索引键也修改了怎么办？ 为什么要有索引？ 如果没有索引， SeqScan不就更慢了吗？ （TODO）

时间旅行存储

本质上和仅追加存储一样。 只不过对于时间旅行存储将表划分为了主表和时间旅行表， 新元组不再是只追加到一张表中， 而是插入到指定的时间旅行表。

时间旅行存储并不比追加存储好， 只是它出现在了并没有那么多Mvcc设计的年代， 并且如果采用从旧到新的方式， 进行垃圾回收的时候， 要进行数据压缩， 版本新的Time-TravelTable称为新的Main Table。

增量存储（类似Git的版本控制）

增量存储要比前两种策略要好， 如果一个元组一共有1000列， 更新了其中的10列， 那么对于增量存储就只是存储这10列的信息， 而前两种方法要全部存储。

它的策略是： 假如一开始是111， 然后插入了新的数据222， 那么增量表中就要保存原始的A的被修改的列信息， 然后主表中的新元组指向它。 也就是新的修改总是在主表中的， 而历史的值是在增量表中的。这类似于LSMTree（TODO， 日志结构合并树）

垃圾回收

如果在快照隔离级别下一个版本没有事务可以看到它并且这个版本是因为事务终止创建的， 那么这个就可以移除它。这里有两个问题：

• 如何查找过期的版本？
• 如何确定何时可以安全的回收这些记录所占用的空间或存储呢？

元组级GC

遍历所有版本， 并尝试找到可以回收的版本。 —— 这个可以使用后台的worker线程进行； 也可以在扫描数据的同时清理，即协同清理。

对于使用后台的worker线程：

上图就是比如现在有两个事务， 事务12和事务25。 那么我们遍历整个表， 返现A100和B100不可见， 因为这里的A100和B100的生效时间段是1 ~ 9，所以对两个事务都不可见。 B101对事务1可见， 对事务2不可见。

对于协同清理：

这里不太理解， 大概的意思可能就是对于worker线程来说， 他知道哪些元组是对所有事务都不可见， 那么扫描到这个元组的时候，就把他删除。 (TODO)。

事务级别GC

事务级别GC就是需要跟踪所有事务以及他们修改的内容。 比如这里事务1， 修改了A， B。 然后记录下AB的旧版本。然后再COMMIT的时候获得一个新的事务ID。然后将这些OldVersions的信息传给vacuum进程。由vacuum进程判断一个最小时间戳， 任何小于这个最小时间戳的事务都可以删除了。

这里同样不太理解， 因为如果vacuum只处理单个事务的最小时间戳那么就不正确， 所以这里vacuum应该处理的是所有事物的最小时间戳。但是这样要一边修改一遍记录， 然后交给后台进程处理， 相当于元组GC的后台worker了。 (TODO)

索引管理

如果有二级索引， 他们指向的是什么， 即值指向的是什么。

逻辑指针

一种是逻辑指针， 工作是帮助我们找到链头的实际物理地址。这种方法最简单的是使用主键， 因为主键是现成的， 先使用二级索引找到主键， 然后利用主键索引去找到对应的物理地址。 另一种方法是合成ID， 但是这还需要重新维护一个合成ID到逻辑指针的索引， 并不划算。

物理指针

另一种就是直接存物理地址。 二级索引精确的指向了要访问的物理地址。

在数据库中可能有大量的二级索引， 这些二级索引都指向了版本链的头部。 此时就可以根据二级索引来找到具体的物理地址。但是如果更新元组， 即便不更新这个元素中二级索引所依赖的属性， 那么这个依旧要更新所有二级索引指向新链头。

Postgres这里采用了其他优化， 就是他们在索引中添加了一个新的条目， 如果新的版本和之前的版本在同一个页中， 他们不会选择更新链头， 而是直接在条目中显示：这个元组不是最新的版本， 最新的版本应该是那边的那个。

MySQL的处理方法就是二级索引提供主键， 然后利用主键找到对应物理地址，和上面的逻辑指针一样。

关于不同快照的重复键问题

这个问题是有一个场景：

就是假如一开始T1读取到了A， T2读取A， 然后删除了A。 并且T1读取的是A1， T2读取的是A2， 删除的也是自己可见的A2。 那么T3插入一个A, 他插入的应该是从时间戳30开始生效。 所以， 这里就要保证两个东西：

• 对于T1来说， 如果正在运行， 在T2删除的时候， 他应该仍能够看到A1。
• 对于时间戳30以后的事务， 他应该能看到A3。（图中的是笔误）

在这种情况下， 如果索引的版本链还是A1这一条。 要确保30以后的事务能够看到A3， 他在遍历版本链的时候， 可能直接就发现版本链运行结束后，也没有看到A3。所以就需要其他的信息来维护一种跳转功能， 能够在索引中存在相同值的时候（此时A的版本链有两条， 说明有相同值）， 能够正确跳转。

删除

删除就是利用墓碑。

删除标志

删除标志就是在元组的头部设置删除标记

墓碑元组

墓碑元组就是将元组设置成默认的“空“元组。