【QCon】精华内容上线92%,全面覆盖“人工智能+”的典型案例!>>> 了解详情
写点什么

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

评论 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
回复
没有更多了
发现更多内容

「代码舞者」2023开放原子开发者大会——开源大侠秘闻

开放原子开源基金会

开源 开发者 算法

融云观察:给 ChatGPT 加上声音和脸庞,AI 社交的多模态试验

融云 RongCloud

AI 设计 API 社交 ChatGPT

浅析 ArrayList

不在线第一只蜗牛

Java 开发语言

【第七在线】服装企业商品部关注的关键问题与解决策略

第七在线

如何区分纯代码、低代码、无代码三者的关系?

这我可不懂

软件开发 低代码 无代码 JNPF

博睿数据参与支持2023年度证券期货业标准研究课题获评“优秀”

博睿数据

Navicat Premium for Mac(多协议数据库管理工具) 16.3.4中文破解激活版

mac

数据库管理工具 苹果mac Windows软件 Navicat Premium 16

2024年市场上最好的免费开源工单管理系统六强

PingCode

开源 工单管理

速度与稳定性的完美结合:深入横测ToDesk、TeamViewer和AnyDesk

阿Q说代码

远程办公 ToDesk TeamViewer AnyDesk

权威认可,天翼云云原生一体机iStack斩获“2023云原生企业TOP50”第一名

编程猫

Metasequoia 4 for Mac v4.8.6b激活版

iMac小白

每日一题:LeetCode-240. 搜索二维矩阵 II

半亩房顶

Go 面试 算法 矩阵 LeetCode

华为云Astro,让业务专家秒变“技术大拿”

华为云PaaS服务小智

低代码 华为云

“基于inBuilder低代码平台开源社区版的应用开发”创新赛获奖队伍公示

inBuilder低代码平台

SecureFX for Mac(ftp文件传输工具)附注册码 v9.4.3破解激活版

mac

苹果mac Windows软件 SecureFX 文件传输客户端

React高手都会用的useMemo有什么用的?

互联网工科生

性能优化 React useMemo

【案例】第七在线商品组合计划赋能安德玛每一个加盟商精准计划

第七在线

Integrity Plus for Mac:数据完整性校验的得力助手

iMac小白

item_get-1688商品详情在跨境电商中的营销策略创新

技术冰糖葫芦

API

海外云手机在跨境外贸中的作用

Ogcloud

云计算 跨境电子商务 跨境电商 电子商务

热热热!开放原子开发者大会议题征集火爆!

开放原子开源基金会

Java 开源 程序员 开发者 算法

Tower for Mac注册激活版下载(强大的Git客户端)

iMac小白

Visio Viewer for Mac激活版 查看和编辑Visio文件

iMac小白

【第七在线】媒介投产分析 Colony Brands每一个宣传画册运营产出收益

第七在线

天猫商品评论数据接口(Tmall.item_review)

tbapi

天猫API接口 天猫商品评论接口 天猫评论接口 天猫商品评论内容接口 天猫评论API接口

使用TikTok云手机轻松拓展全球市场

Ogcloud

云计算 TikTok 手机云服务

虾皮商品评论接口(Shopee.item_review)|虾皮API接口指南

tbapi

shopee API 虾皮商品评论接口 虾皮商品评价接口 虾皮评论接口 shopee 商品评论接口

mac右键助手 MouseBoost Pro 3.3.4破解版

iMac小白

【第七在线】国际市场扩张与商品计划:跨越地域的挑战与机会

第七在线

MongoDB中的分布式集群架构

EquatorCoco

分布式 索引 db 集群架构

现在大火的低代码是什么?有哪些优势?

高端章鱼哥

低代码开发 应用程序 JNPF

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