高品质的音视频能力是怎样的? | Qcon 全球软件开发大会·上海站邀请函 了解详情
写点什么

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

  • 2020-08-17
  • 本文字数:3501 字

    阅读完需:约 11 分钟

数据库内核杂谈(十二):事务、隔离、并发(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-08-17 17:274637

评论 9 条评论

发布
用户头像
perfect
2022-09-14 19:56 · 江苏
回复
用户头像
此处事务T1和T2有共享状态,二者根本就不应该同时执行!

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

2022-09-13 18:54 · 北京
回复
用户头像
作者留言:2022年1月1日,祝大家新年快乐。不知不觉,数据库内核杂谈又陪伴大家一年(虽然。。还是不可避免地拖更了)。今年的new year resolution,希望创建一个群,和大家一起交流。加我微信 81211430(请备注数据库内核杂谈,谢谢),我会建群。期待和大家交流。
2022-01-01 12:30
回复
用户头像
作者来留个言,一言难尽的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
回复
都是sharding,就是是哪一层来做了,分布式数据库就是数据库来做,反之就是业务层来做。业务层做还有很多其他缺点..
2022-07-05 19:48
回复
没有更多了
发现更多内容

理解Python协程的本质

Justfly

Python 协程 异步 Async 异步编程

mongodb 源码实现系列 - command 命令处理模块源码实现二

杨亚洲(专注MongoDB及高性能中间件)

MySQL mongodb 分布式数据库 源码刨析 分布式数据库mongodb

Newbe.ObjectVisitor 0.4.4 发布,模型验证器上线

newbe36524

.net core ASP.NET Core dotnet

构师训练营 - 第七周课后练习

joshuamai

谷燕西:不需要银行的银行业务

CECBC

移动互联网

CloudIDE插件开发实战:教你如何调试代码

华为云开发者联盟

ide 开发 Cloud

揭秘 VMAF 视频质量评测标准

阿里云视频云

视频 图像处理

Linux角度仰视Goroutine的GMP

ninetyhe

Java Linux 多线程与高并发 Go 语言

前端开发还可以这么玩?元数据实践分享

华为云开发者联盟

大前端 元数据 组件 ROMA 业务流

2. Spring早期类型转换,基于PropertyEditor实现

YourBatman

Spring Framework 类型转换 PropertyEditor

甲方日常 64

句子

工作 随笔杂谈 日常

WebRTC SDP 详解和剖析

阿里云视频云

阿里云 音视频 WebRTC 视频云 流媒体传输

深度学习在物理层信号处理中的应用研究

华为云开发者联盟

学习 模型 物理层

基于有限状态机与消息队列的三方支付系统补单实践

Java架构师迁哥

王者级别的Java多线程技术笔记,我愿奉你为地表最强!

Java架构师迁哥

数字经济跨越五个融合发展阶段,区块链正成为基础支撑结构

CECBC

数字经济

百篇已过,又是一个新篇章,谈谈感受吧

良知犹存

代码人生

多活/多机房的几种实现方式与重点

Justfly

高可用 跨机房 数据同步 异地多活容灾

流动性挖矿系统APP开发|流动性挖矿软件开发

系统开发

《Web自动化》基础知识脑图

清菡软件测试

Web

《Python深度学习》第二版重磅来袭——(Keras之父亲自编写)

计算机与AI

构师训练营 - 第七周学习总结

joshuamai

告别“效率内卷化”,华为用一年时间让职场人支棱起来

脑极体

国家计算机网络与信息安全管理中心官员:数字货币的风险仍需关注

CECBC

信息安全

S型曲线不止关乎身材?|技术人应知的创新思维模型(2)

Alan

创新 思维模型

工商银行基于 Dubbo 构建金融微服务架构的实践-服务发现篇

阿里巴巴云原生

云原生 dubbo 中间件 案例分享 CloudNative

云原生架构:容器资源限制及资源可见性

云原生实验室

云原生

Windows下MySQL无法启动万能解决方案

MySQL从删库到跑路

MySQL

数据库内核杂谈(十二):事务、隔离、并发(3)_数据库_顾仲贤_InfoQ精选文章