MVCC 多版本并发控制 (multi-version concurrency control)
数据库中对于每个数据,记录他的版本
当一个txn更新一个数据时,不止记录更改后的数据,还要记录原版本内容,其他txn来查询时,能够查询到历史版本
写不会阻塞人去读他的历史版本,读也不会去阻塞有人去写他的历史版本
只读的txn能够不加锁读一个快照,用时间戳实现
能够实现查看三分钟之前长什么样
snapshot isoation 快照隔离,有一个事务状态表
研究列表:
- 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
两种思路:
- oldest-to-newset (O2N)
- newest-to-oldest (N2O)
就是新版本放到链表末尾还是链表开头
time-travel storage
主表只存最新数据,历史版本放到历史表中
delta storage
上一个是存数据,这个是存储过程,能够节约存储大小,但是做恢复要重新计算,想看A1要先恢复成A2,才能变成A1
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 加一个新的版本,告诉前面版本都是被删掉的
