MVCC 和其实现

发表于 |

一些简单的笔记，记录一下 MVCC 以及实时更新的技术。

MVCC

多版本并发控制(Multi-Version Concurrency Control, MVCC)是相对于单版本的概念，而不是一种全新的并发控制方式。和单版本一样，MVCC有不同方式的实现，如基于锁的MV2PL，基于时间戳的MVTO，基于乐观并发控制的MVOCC。

MVCC 是一种解决读-写冲突的无锁并发控制方式。

根据 Wikipedia，MVCC 意图解决读写锁造成的多个、长时间的读操作饿死写操作问题。每个事务读到的数据项都是一个Snapshot并依赖于实现的隔离级别。写操作不覆盖已有数据项，而是创建一个新的版本，直至所在操作提交时才变为可见。快照隔离使得事务看到它启动时的数据状态。

具体来说：

  1. 当事务 Ti 读取对象 P 时，只有比 Ti 时间戳更早的最新对象版本是可见的。
  2. 当事务 Ti 写入对象 P 时，如果 Tk 要写同一对象，那么 Ti 必须早于 Tk 才能成功。

MVCC 的实现方案和相关技术

基于 Merge 的方案

多路归并是一种实现 MVCC 的方案。主要思路是读取 PK 和 MVCC 列，部分实现中还会读取 delmark 列。

  • TiFlash 中，对于每个 <pk, version> 行，并排存一个 delmark 列，表示是否已经被删除。
  • Hologre 中，说为了支持多版本，在 row tablet 中的数据会多加 del_bit 和 LSN 两列。后续又说 delete map 是一个 row tablet。说明 delete map 它可能是当做带版本数据一起存的。

延迟物化

根据 MVCC 列得到一个 MVCC bitmap，根据 filter 列得到一组 filter bitmap，将这几个 bitmap AND 起来，得到最终要读取的行。根据 projection 条件，读取所需的行的所需列。

Delete+Insert

StarRocks 的方案是对于每次写入的 RowSet，并排放一个 delVector。

  • 假如一开始写入了 1/2/3/4 这四个 Rowset 0，此时 delVector 都为 0。
  • 现在写入 Rowset 1，对 1/3/5 进行了变更。通过查询主键索引，可以得到原先这个记录的位置，在原来的位置生成 delVector。这样就构成了第二个版本。
  • 它应该不是在读取的时候，每个 Rowset 会 mask 自己的 delVector，从而得到自己需要贡献出来的数据。而是在写入的时候，就合并 delVector。

SR 的关键需要根据主键找到所有的版本，从而避免 merge 的开销。但这需要花内存去维护相应的结构。