首页 cmu 15-445

MVCC 多版本并发控制 (multi-version concurrency control)

数据库中对于每个数据,记录他的版本

当一个txn更新一个数据时,不止记录更改后的数据,还要记录原版本内容,其他txn来查询时,能够查询到历史版本

写不会阻塞人去读他的历史版本,读也不会去阻塞有人去写他的历史版本

只读的txn能够不加锁读一个快照,用时间戳实现

能够实现查看三分钟之前长什么样

snapshot isoation 快照隔离,有一个事务状态表

image-20220306084256226.png

研究列表:

  • concurrency control protocol 并发控制手段
  • version storage 版本存储
  • garbage collection 垃圾回收
  • index management 索引的管理
  • deletes 删除

concurrency control protocol

  • timestamp ordering T/O
  • optimistic concurrency control OCC
  • two-phase locking 2PL

version storage

数据库用记录的指针,实现链表,来存储不同版本,b+tree根节点指向链表的头结点

三种存储方法:

  • append-only storage 简单追加
  • time-travel storage 时间旅行存储
  • delta storage 增量存储

append-only storage

image-20220306090247566.png
两种思路:

  • oldest-to-newset (O2N)
  • newest-to-oldest (N2O)

就是新版本放到链表末尾还是链表开头

time-travel storage

主表只存最新数据,历史版本放到历史表中

image-20220306090555463.png

delta storage

上一个是存数据,这个是存储过程,能够节约存储大小,但是做恢复要重新计算,想看A1要先恢复成A2,才能变成A1

image-20220306090712023.png

garbage collection

如果历史版本不进行删除,就会产生大量冗余数据

  • 任何版本都看不到这个历史版本了,那就能删了(SI 隔离等级)
  • 里面的某一个版本回滚了,那这个版本也是无用的

两个问题

  • 怎么发现这些历史版本
  • 什么时候删除历史版本

解决方式

  • tuple-level 以行记录的垃圾回收,也有两个方案:background vacuuming & cooperative cleaning
  • transaction-level 以txn的垃圾回收,每个事务记录历史版本

tuple-level background vacuuming 后台清理

去后天查看,比现存事务的时间戳小的数据都要进行后台清理,不优化就是扫描全历史表,但是只有被更新过的页才能出现垃圾数据,所以只用扫描被更新过的历史表就可以了

cooperative cleanig 合作清理

在sql查询的时候顺便去查看数据有没有用

txn-level 事务去记录修改了那些数据,数据库去决定那些版本无用了

index management 索引管理

主键索引指向那个槽就可以了,但是讲数据修改主键,要先删除再插入

secondary indexes 辅助索引

两个流派

  • logical pointers 记录主键的值,或者记录行id,要所有记录要回表查询
  • physical pointers 但是如果修改,那么所有的辅助索引都要进行修改

一个键可能有多个值指向多个版本,所以要多余的逻辑去处理这个问题

mvcc deletes

要看每个数据在什么时刻真正的被删除了

  • deleted flag 加标志位告诉已经删掉了
  • tombstone tuple 加一个新的版本,告诉前面版本都是被删掉的



文章评论