你在使用哪种编程语言?快来投票,亲手选出你心目中的编程语言之王 了解详情
写点什么

数据库内核杂谈 (十二):事务、隔离、并发(3)

2020 年 8 月 17 日

数据库内核杂谈(十二):事务、隔离、并发(3)

之前的文章,我们分别介绍了锁和时间戳机制来管理并发控制,这篇文章我们将介绍最被广泛使用的方法——多版本并发控制 Multi-Version Concurrency Control (MVCC)。


为什么多版本并发控制更受欢迎呢?因为锁和时间戳机制都是通过阻塞或者回滚冲突的事务来确保事务的有序性。比如,一个读操作可能被迫回滚,因为它要读取的数据已经被另一个更新的事务修改了。但是,如果我们把每个数据的所有历史版本都记录下来,就可以避免上述这种情况发生。这也正是多版本控制的由来:对于每个数据 Q,每次写操作 write(Q)都会给 Q 建立一个新版本;而对于读操作 read(Q),会根据事务的先后关系选择一个正确的版本去读取,来保证事务的有序性。多版本控制能够很好地解决这类读写冲突,尤其是长时间的读操作饿死写操作问题。


插一个能够提升格调的小知识,MVCC 最早出现于 1978 年 Dr. Reed 的博士毕业论文“ Concurrency Control in Distributed Database Systems ”中( https://en.wikipedia.org/wiki/David_P._Reed),有兴趣的同学可以去看一下。


下面,我们介绍两种多版本并发控制的实现:多版本时间戳和多版本两阶段加锁。


多版本时间戳(Multi-Version Timestamp Ordering)

把时间戳和多版本控制结合就形成了多版本时间戳机制。对于每个事务 Ti,系统都会设置相应的事务时间 TS(Ti)。对于每个数据单元 Q,系统会保存一系列的版本数据 Q1,Q2,Q3,… Qn。其中,每个版本 Qx 保存以下信息:


  1. 当前版本的数据值

  2. W-TS(Qx): 当 Qx 被某个事务 Ti 创建的时间戳,即 TS(Ti)

  3. R-TS(Qx): 由于一个版本的数据可以被多个事务读取,这里存储的是最大的事务时间戳:最近一次被某个事务 Tj 读取成功的时间戳,即 TS(Tj)


当一个事务 Tx 创建了数据 Q 版本 Qk,Qk 会保存 Tx 所写入的数据值,同时,系统会把 W-TS(Qk)和 R-TS(Qk)都初始为 TS(Tx);当有另一个事务 Ty 并且 TS(Ty) > TS(Tx)读取 Qk,系统会更新 R-TS(Qk)至 TS(Ty)。


现在介绍详细的操作机制:给定当前事务 Ti 对数据 Q 发起了一个读操作 read(Q)或者写操作 write(Q)。并假定,版本 Qk 是 Q 的所有版本中持有最大的但小于或等于 TS(Ti)的 W-TS 的时间戳。则:


  1. 如果 Ti 是读操作,则读取成功,返回 Qk 中的值给 Ti。

  2. 如果 Ti 是写操作,则需要判断,如果 TS(Ti) < R-TS(Qx),即说明有一个更新的事务已经读取了数据,因此系统判定更新失败,回滚 Ti。如果 TS(Ti) = W-TS(Qx),系统可以直接将 Ti 的值覆盖 Qk 的原值;如果 TS(Ti) > R-TS(Qx),则创建一个新的版本 Q。


规则一很容易理解,一个事务可以读取到在它看来最新的数据。规则二则保证了一个事务被需要被撤销,如果已经有更新的事务读取了某个版本。


多版本时间戳机制的一大好处在于,一个读取数据的事务永远不会失败也不需要等待。在一个读多写少的场景下,相比于先前介绍的两种机制,会有很好的性能提升。


当然,它也是有缺点的。首先,就是在读取操作的事务中,也需要更新相应的 R-TS(Qk),并且读取数据,这就导致可能产生两次磁盘操作,而非只读一次。另外,当写操作发生冲突时,它会要求回滚失败的事务,相比起等待,回滚操作可能更昂贵一些。下面介绍的另一种的实现可以解决这个问题。


多版本两阶段加锁(Multi-Version Two-Phase Locking)

多版本两阶段加锁机制,相比于上文介绍的多版本时间戳机制,是要集多版本控制和两阶段加锁之所长。它会区分对待只读操作的事务和有更新操作的事务。


有更新数据的事务会遵守两阶段加锁的规则,即事务需要持有所有的锁直至事务结束。这样,这些事务就能够保证有序性(在介绍 两阶段加锁的时候已经讲解过)。这样做的好处在于不同的写事务可以等待并且按照顺序依次完成而不需要回滚后重试。对于只读操作,和上文介绍的多版本时间戳机制一样。不同的是,在多版本两阶段加锁中,事务的时间不再是时间戳,而是表现相对时序的事务计数 TS-Counter。这个 TS-Counter 在每次事务提交时被更新。


对于只读操作的事务 Ti,数据库系统会把 TS(Ti)赋于当前 TS-Counter 的值,这样 Ti 读取数据就和上面介绍的多版本时间戳一样,会读取到最大的但小于或等于 TS(Ti)的 Q 版本的值。对于有更新操作的事务,如果要读取一个数据,首先,它会获取这个数据的共享锁,并且读取最新版本的数据。当事务需要写数据时,首先要获取数据的独占锁并且创建一个新的版本,并把版本的时间戳设置为无穷大,当这个事务要被提交时,把它锁创建的所有数据的新版本的时间戳设置为 TS-Counter+1,并且同时更新系统的 TS-Ccounter,也变为 TS-Counter+1。


多版本并发控制的缺陷

天下没有免费的午餐,我们来讨论它有什么缺陷。


  1. 额外的存储和计算资源支出:首先,需要额外存储历史版本数据,并且在执行时,每个事务要快速定位到正确的版本,并且对于更新的事务,通常情况会复制一份或者创建一个新的版本来暂存数据,这些都是需要消耗存储和计算资源的。当然,数据库系统可以定期对老的数据版本进行清理来释放存储空间。

  2. 多线程竞争时间戳分配:由于需要保证不同事务的有序性,因此需要有一个共享的时间戳实现来分配(无论是用时间,还是相对的 counter),免不了不同的事务线程需要去竞争时间戳。

  3. 有些情况下,会导致频繁的事务回滚:特别当事务之间存在大量竞争的时候,会造成频繁的事务回滚。


总结一下,我们介绍了两种具体的多版本并发控制的实现,多版本时间戳机制和多版本两阶段加锁,两者都保证了对于只读操作的事务,不会失败也不会被等待。区别在于写操作的事务,多版本时间戳机制会回滚“迟到”的写事务,而多版本两阶段加锁通过共享和独占锁来对多个写操作事务排序。同时,我们也讨论了一些多版本并发控制的缺陷。但是,瑕不掩瑜,它依然是最常见的并发控制实现。


回忆一下在第十期介绍的隔离级别:读未提交;读提交;可重复读和可有序化。那用多版本并发控制实现了哪个隔离级别呢?读者可能会觉得,应该是可有序化。但其实不然,它实现了一个新的隔离级别叫做 Snapshot Isolation(快照隔离)。


快照隔离(Snapshot Isolation)

快照隔离可以看作是对每一个事务,分配了一个独有的数据库快照。事务可以安心地读取这个快照中的数据而不需要去担心其他事务(因此只读事务是不会失败也不会被等待的)。同理,事务对数据的更新也首先暂存在这个独有的快照中,只有当事务提交的时候,这些更新才会试图被写回真正的数据库版本里。当一个事务准备提交时,它依然要确保没有其他事务更新了它所更新过的数据,否则,这个事务会被回滚。


那为什么说快照隔离是一个单独的隔离级别而不是可有序化呢?问题就在于,它提供了“太多”的隔离性(英语中用 too much!貌似更形象一些)。我想借用 CMU 数据库教授 Andy Pavlo 课里举过的一个非常贴切的例子,我们现在假设数据就是围棋的棋子,一部分是黑子,一部分是白子。现在同时有两个更新事务:T1: 把所有的白子变成黑子(写成 SQL 语句可以看作是这样的: UPDATE color = ‘black’ FROM marbles WHERE color = ‘white’ )。T2:把所有的黑子变成白子。执行这两个操作会怎么样呢?由于快照隔离(多版本并发控制)机制,这两个事务更新的数据不一样,因此都会视为成功。这就导致了最终,白子和黑子的颜色互换。见下图示例。



(Credit to https://15721.courses.cs.cmu.edu/spring2020/slides/03-mvcc1.pdf)


但是,根据可有序化的定义,要确保不同的事务最终是可以沿着时间线排成一溜执行,因此无论是 T1 先执行还是 T2 先执行,最终的颜色应该全是黑色或是白色,如下图所示。



(Credit to https://15721.courses.cs.cmu.edu/spring2020/slides/03-mvcc1.pdf)


上述的示例被称为 Write Skew Anomaly。因此,快照隔离是一个区别于可有序化的隔离级别,如果把它安插在我们介绍过的隔离级别,应该如下图所示。



(Credit to https://15721.courses.cs.cmu.edu/spring2020/slides/03-mvcc1.pdf)


大部分的数据库都支持快照隔离。Orcale 和 PostgreSQL 数据库其实是使用快照隔离机制来实现可有序化机制。因此,在极端小概率情况下,数据库的状态是有可能“非有序化”的。


总结

至此,事务、隔离和并发就全部介绍完毕。我们分别介绍了事务的 ACID 属性以及不同的隔离级别,再依次介绍了不同的并发控制实现,两阶段加锁,时间戳机制,和多版本并发控制。


对于单机的数据库系统就介绍得差不多了。下一篇文章,我们聊一个非常有意思的话题:假设给你一个单机的数据库系统实现,要求在这个基础上把它扩建成分布式数据库系统,你会怎么做?这个问题还有个小故事。很久很久以前,在原来公司参与系统设计面试的时候,候选人和我说,我原本准备的面试题另一个面试官已经问过了(当时我的内心是崩溃的…)。这是我临时想出来的面试题,留给大家做思考题。


2020 年 8 月 17 日 17:273372

评论 5 条评论

发布
用户头像
作者来留个言,一言难尽的2020终于过去了,新年快乐,希望2021对所有人,都充满惊喜。数据库内核杂谈也已经更新到第十四期了,再次感谢各位的关注。如果你是内核杂谈的真粉丝,觉得内核杂谈对你有收获,愿意听我多扯扯,欢迎加入我的知识星球:Dr.ZZZ 聊技术和管理:https://t.zsxq.com/VrZbeAE(由于不知道能输出多少,也不知道有多少粉丝,所以还是先免费吧)
2021 年 01 月 01 日 02:44
回复
用户头像
作者来留个言。。。抱歉。。又拖更了。。最近实在太忙了。。 马上这边感恩节了,终于可以放假了。一定补上。谢谢大家。
2020 年 11 月 09 日 07:24
回复
用户头像
边学15445边看博主的文章,写的太好了
2020 年 09 月 03 日 20:37
回复
用户头像
楼主加油!催更(手动狗头
2020 年 09 月 03 日 12:24
回复
用户头像
一口气读到这里了,作者千万顶住,继续往下写呀,感觉把自己学到的数据库只是整个串了一遍,印象更深刻了。对于,分布式数据库,我理解现在有两种方式,一种是在多个基础数据库如myql之上抽象一层出来,把sql打散分发下去再汇总,如利用sharding-jdbc或者cat这样的中间件。一种是现在云数据库,把计算存储利用云进行分离。
2020 年 08 月 25 日 16:26
回复
没有更多了
发现更多内容

卧薪尝胆30天!啃透京东大牛的高并发设计进阶手册,终获P7意向书

云流

Java 程序员 架构 面试 高并发

如何基于MindSpore实现万亿级参数模型算法?

华为云开发者社区

算法 mindspore 万亿级参数 大模型

jenkins-01 | 安装

Python测试和开发

持续集成 jenkins CI/CD

2021斩获45K月薪的Spring全家桶:文档+面试题+学习笔记+思维导图

Crud的程序员

Java spring springboot SpringCloud

ipfs前景怎么样?ipfs有什么运用价值?

投资矿机v:IPFS1234

IPFS有什么运用价值 ipfs前景怎么样

微服务到底是什么?spring cloud在国内中小型公司能用起来吗?

Java架构师迁哥

在windows上用Nginx做正向代理

Python测试和开发

网络 Proxy 正向代理

面试官问我:如何减少客户对交付成果的质疑

华为云开发者社区

Scrum 敏捷开发 项目 用户故事 研发

中国政府大数据市场,我们又是第一

浪潮云

云计算

K8S调试利器:telepresence2使用文档

互联网架构师小马

强化学习 | COMA

行者AI

人工智能

吹爆!阿里新产Spring Boot高级笔记,肝完变秃也变强

神奇小汤圆

Java 架构 面试 微服务

双非渣硕,开发两年,苦刷算法47天,四面字节斩获offer

云流

Java 程序员 架构 面试 算法

面试官:Spring@Transaction注解是如何执行事务的?

Java王路飞

Java spring 源码 架构 面试

从零开始学习3D可视化之物体选择

森友小锘

前端 可视化 程序媛 3D可视化 数字孪生

最新大厂Android校招面试经验汇总,看完没有不懂的

欢喜学安卓

android 程序员 面试 移动开发

接口全面重构TypeScript ,让uni-app 具备出色的基础音视频能力

ZEGO即构

typescript uni-app 音视频开发

bzz分币系统开发,矿机挖矿系统搭建,云算力挖矿平台开发

WX13823153201

搭建企业私有GIT服务

IT视界

git

最新阿里+头条+腾讯大厂Android笔试真题,附详细答案

欢喜学安卓

android 程序员 面试 移动开发

情指勤一体化实战平台建设解决方案,公安情指勤系统开发

WX13823153201

年中面试经历:美团2面+字节3面+阿里4面+腾讯Java面经,终入字节

云流

Java 程序员 架构 面试

联邦学习—金融数据壁垒和隐私保护的解决之道

索信达控股

金融科技 联邦学习 金融 数据隐私 大数据平台

熬夜复习90天,4面阿里Java研发成功上岸定级P6,分享我的面试过程

菜菜山

Java 编程 程序员 架构 面试

ipfs项目是真实的吗?ipfs和http的区别在哪里?

v:IPFS456

ipfs项目是真实的吗? ipfs和http的区别在哪里?

阿里P8大佬码出25大后端面试指南,2000道面试题解析助力金九银十

Crud的程序员

Java spring 编程 架构

奇亚节点分币系统搭建,Bzz节点分币APP搭建

13823153121

冷门科普类自媒体如何才能脱颖而出

石头IT视角

ipfs矿机目前可以投资吗?ipfs矿机值得投资吗?

投资矿机v:IPFS1234

ipfs矿机目前可以投资吗 ipfs矿机值得投资吗

为了不写接口文档,我肝了个 IDEA 插件

程序员小毕

Java 程序员 架构 面试 开发工具

🌏【架构师指南】分布式技术知识点总结(中)

李浩宇/Alex

分布式架构 架构师技能 分布式技术 6月日更 6 月日更

围绕“三个问题”开展的网易云音乐数据基础建设

围绕“三个问题”开展的网易云音乐数据基础建设

数据库内核杂谈(十二):事务、隔离、并发(3)-InfoQ