写点什么

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

作者:StoneDB
  • 2023-07-19
    浙江
  • 本文字数:3628 字

    阅读完需:约 12 分钟

快照隔离级别原理 | 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/






发布于: 刚刚阅读数: 6
用户头像

StoneDB

关注

https://github.com/stoneatom/stonedb 2022-05-07 加入

MySQL高性能分析加速器。 企业级一体化实时HTAP开源数据库。 100%兼容MySQL,高性能高可用。 针对热数据、小数据和宽数据的分析加速器。

评论

发布
暂无评论
快照隔离级别原理 | StoneDB 技术分享 #1_MySQL_StoneDB_InfoQ写作社区