快照隔离级别原理 | StoneDB 技术分享 #1

设计：小艾

审核：丁奇

编辑：宇亭

作者：罗中天（花名：德里克）
浙江大学在读硕士、StoneDB 内核研发实习生

ANSI SQL-92 标准中规定了四种事务隔离级别和三种异象：读未提交（Read Uncommitted）、读已提交（Read Committed，简称 RC）、可重复读（Repeatable Read，简称 RR）和串行化（Serializable），其中读已提交解决了脏读，可重复读解决了脏读和不可重复读，串行化解决了脏读、不可重复读和幻读。上述这些内容是为人所熟知的，故不是本文的主角。本文的主角是快照隔离级别（Snapshot Isolation，简称 SI），同时引入新的异象写偏斜（Write Skew）。SI 不属于 SQL 标准的一部分，是对 SQL 标准的补充。

在将 SI 考虑进去以后，可以得到如下表格中的内容

注意，上表中的读已提交、可重复读中的部分内容和 innodb 中的有些不符，原因是 innodb 中的 RC 和 RR 包括快照读和当前读两种情况，具体会在下面进行分析。

接下来本文主要围绕 SI，阐述 SI 的实现方式 MVCC、SI 的异象写偏斜、将 SI 和 RR 混在一起的“罪魁祸首”——Innodb 中的 RR 等内容。

SI 的实现方式

一般而言，SI 是用多版本并发控制（Multi-Version Concurrency Control，简称 MVCC）实现的。MVCC 本身有多种实现方式，并不是所有的 MVCC 都能实现理论上的 SI，比如 Innodb 中的 MVCC 其实就没有完全实现 SI，因为它没有完全解决幻读，关于 Innodb 中的 MVCC 的具体分析请见本文下面的小节。除了 MVCC 之外，SI 中的每个事务需要分配 2 个时间戳，一个在事务开始的时候分配，一个在事务结束的时候分配。

一个完整的 MVCC 协议包括并发控制协议、多版本的存储、垃圾回收和索引管理四个部分。本文主要对并发控制协议进行阐述。

记录元数据

一种并发控制协议的实现方式

在上图的记录元数据的基础上新增 READ-TS 字段表示读取这条记录最大的事务 ID。

对于读来说，事务 读取没加写锁（TRX-ID 为 0）且满足 的记录，显然这样的记录最多只有一条，如果 READ-TS 小于 ，就 CAS 将 READ-TS 变成 ，如果 CAS 失败，继续比较，如果还是小于，继续 CAS，如果大于的话，就可以结束了。

对于写来说，事务 找到最新的记录，如果不可见，就 abort，否则，如果该记录没加写锁（TRX-ID 为 0）且 大于等于 READ-TS，就将 TRX-ID CAS 为 ，即加写锁，然后生成新的版本，新版本 BEGIN-TS 设为 ，将 END-TS 设为无穷大，然后将加锁版本（旧版本）的 END-TS 改为 （原来为无穷大）。在事务提交的时候，会为事务新分配一个时间戳，将新记录版本的 BEGIN-TS 和旧记录版本的 END-TS 修改为该时间戳，最后释放锁。
为什么写的时候会有 大于等于 READ-TS 的条件？这是为了 ID 更大的事务的快照的前后一致性。这个条件表示已经有 ID 更大的事务读取了该条记录，如果事务 生成了新的版本，那么原来那个版本的 END-TS 就会被改为 ，如果 ID 为 READ-TS 的事务再次读取这个记录，那么读到的记录就会变成最新版本的了（根据范围），前后就不一致了。、

发生写写或者读写冲突后会发生事务的回滚（也有可能是阻塞），在上层的应用中可以进行自旋重试的操作。

SI 的异象

从文章开头的表格中可以看出 SI 会出现写偏斜的异象，并且解决了幻读，这里可能会有一些反常识，至于为什么有些人会产生 SI 没有解决的 MVCC 的误解，我们会在下一小节中进行分析。

写偏斜

如上图所示，事务 1 想要将所有的球变黑，它会先查询出有哪些球是白的，然后更新这些球为黑球，事务 2 想要将所有的球变白，它会先查询出哪些球是黑的，然后更新这些球为白球，由于两个事务都是基于快照进行修改的，所以最后的结果不是串行化能形成的状态（全黑或者全白）中的任意一个，这就是写偏斜的异常。用更加 hign level 的语言来表述的话，写偏斜是指两个事务并发读取一个数据集，然后各自利用读到的信息修改数据集中不相交的数据项，最后并发提交事务。

如何解决的幻读

假设有两个事务 A 和 B，当前事务 A 已经进行了一个范围的查询，之后按顺序会发生事务 B 进行一次插入操作，事务 A 进行一次同样条件的查询操作，由于事务 B 的插入操作涉及的记录的 BEGIN-TS 会在事务 B 提交的时候被改为为事务 B 的结束时间戳，那么该时间戳肯定大于事务 A 的 trx_id（在事务 A 开始的时候分配），所以事务 B 的插入对事务 A 是不可见的。

SI 和 RR 的主要区别

大家总是会将 SI 和 RR 搞混，甚至认为这两个是相同的东西，这背后的罪魁祸首是 Innodb（其实 Postgress 也是，但在互联网行业中 Innodb 还是占比更重的那一位），具体的原因是 Innodb 的 RR 包括了快照读和当前读两种方式。

快照读

Innodb 中的普通读（select ...）就是快照读，通过 MVCC 的方式实现。

Innodb 中的 MVCC

版本链

innodb 中的 undo log 被分为两大类，TRX_UNDO_INSERT 和 TRX_UNDO_UPDATE。其中 TRX_UNDO_UPDATE 类型的 undo log 有一个 roll pointer 字段，指向该条记录上一次修改对应的 undo log。同时每条数据记录也有一个 roll pointer 的隐藏字段，指向该条记录上一次修改对应的 undo log。这样通过 roll pointer，每条记录都能形成一个版本链。另外，每条记录和 undo log 里都存着造成这次修改的 trx id。每条数据记录是最新的，顺着版本链，可以追溯到之前的修改版本，以及每次修改对应的事务 id。

ReadView

查询流程

顺着版本链依次进行判断

1. 如果被访问版本的 trx_id 和 ReadView 中的 creator_trx_id 相同，就查询到当前版本
2. 如果被访问版本的 trx_id 小于 ReadView 中的 min_trx_id，该版本可以被当前事务访问
3. 如果被访问版本的 trx_id 大于等于 ReadView 中的 max_trx_id，该版本不可以被当前事务访问
4. 如果如果被访问版本的 trx_id 大于等于 ReadView 中的 min_trx_id，且小于 ReadView 中的 max_trx_id，需要判断 trx_id 是否在 m_ids 中，如果在的话，该版本不可以被当前事务访问，否则，可以访问
5. 如果该版本不可以被当前事务访问，顺着版本链继续判断下一个

快照读不是 SI

Innodb 中的快照读不是 SI，因为快照读引入了部分的幻读问题，而 SI 按前面所讲，不会有幻读的问题，但是有写偏斜的问题。

引入部分幻读

在上图所示的情况下会引入幻读，因为在第三步的时候会讲 id=5 的那条记录的 trx_id 修改为事务 A 的事务 id，所以在第四步的时候会根据上面查询流程中的第一条，即访问版本的 trx_id 和 ReadView 中的 trx_id 相同，所以会“无中生有”地查到 id=5 的这条记录。
这里可能读者会有一个疑问，那么如果在上面分析 SI 的 MVCC 解决幻读的那个例子中也加入事务 A update 的这个操作，会怎么样？在 SI 的 MVCC 中，事务在生成新版本的时候的时间戳一定要比旧版本更大才行，由于事务 A 看不到事务 B 插入的记录，所以将无法执行 update 操作。

本质原因

在 innodb 中 ：

1. 事务只有一个 trx_id，没有开始和结束都分配一个时间戳。
2. 版本链按从新到就来看，它的时间戳（或者 trx_id）不是从大到小的（innodb 这样设计的原因个人认为是为了减少事务的阻塞和回滚，如果按 SI 中的 MVCC 来看，可能会出现不少这种读写冲突的情况）

当前读

Innodb 中的 update、select...for share mode、select...for update 等语句是当前读。当前读不走 MVCC 的逻辑，而是通过两阶段锁（Two Phase Lock，简称 2PL）的方式实现 RR，其实如果抛开快照读，Innodb 的 RR 其实就是串行化，通过间隙锁的方式解决了幻读的问题。

2PL

Innodb 中的 2PL 是强两阶段锁（strong 2PL），即所有锁（包括 X 锁和 S 锁）的释放都需要放到事务提交之后，这样就可以解决脏读和不可重复读的问题。

间隙锁

Innodb 通过间隙锁解决了幻读的问题，所以 2PL+间隙锁解决了所有的异象，也就是 Innodb 串行化的实现方式。
间隙锁虽然是锁住前后两条记录之间的间隙的，但是在实现上将其归于后面那条记录。间隙锁也分为 X 锁和 S 锁，间隙锁与间隙锁之间，无论是 X 锁还是 S 锁，都不会阻塞，但在插入一条记录的时候，如果存在间隙锁，就会生成一个插入意向锁，并阻塞。

小结

这篇文章我们介绍了快照隔离级别 SI 以及和 RR 的区别，SI 是对四种常见隔离级别的补充，能够有效解决幻读的问题，是对 SQL 标准的重要补充。更多精彩硬核技术，欢迎关注StoneDB开源社区，我们后续会更新更多技术研发干货~

参考资料

Schedule - CMU 15-721 :: Advanced Database Systems (Spring 2020)^[1]

事务隔离级别是怎么实现的？^[2]

Reference

[1]

Schedule - CMU 15-721 :: Advanced Database Systems (Spring 2020): https://15721.courses.cs.cmu.edu/spring2020/schedule.html

[2]

事务隔离级别是怎么实现的？: https://xiaolincoding.com/mysql/transaction/mvcc.html#read-view-%E5%9C%A8-mvcc-%E9%87%8C%E5%A6%82%E4%BD%95%E5%B7%A5%E4%BD%9C%E7%9A%84

加入StoneDB社区

Github：https://github.com/stoneatom/stonedb

Gitee：https://gitee.com/StoneDB/stonedb

社区官网：https://stonedb.io/

哔哩哔哩：https://space.bilibili.com/1154290084

Twitter：https://twitter.com/StoneDataBase

Linkedin：https://www.linkedin.com/in/stonedb/

微信公众号 - StoneDB（StoneDB2021）。