数据保护背景下,安全团队引入了哪些新技术进行防控升级?点击学习案例 了解详情
写点什么

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

  • 2020 年 5 月 26 日
  • 本文字数:4430 字

    阅读完需:约 15 分钟

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

本篇文章选自数据库内核杂谈系列文章。


上一篇文章我们介绍了事务的 ACID 属性和数据库针对事务的不同隔离级别,本文我们将继续讨论实现事务的不同方法。


与教科书直接列出实现方法不同,本文将会由浅入深地介绍加锁实现机制和时间戳机制这两种不同实现方法的形成过程。


加锁实现机制(Lock-based protocols)

实现事务隔离的最简单方法就是在对任何数据进行读写时,都保证互斥性,即当一个事务在读写数据时,保证其他事务不能对数据进行修改。最常见的实现就是对数据进行加锁(lock)。


假设,我们对数据库设置了一把唯一的全局锁:任何事务需要执行时,都需要获取这把锁。那么,全局锁就保证了事务之间的有序性,从而保证了 ACID 属性。因此,从正确性角度考虑, 全局锁是可行的方法。但全局锁的缺点也显而易见,事务之间,即使读写的数据完全无关,也没有任何并行,这对性能的影响不言而喻。


有什么办法可以改进吗?一个方法是把锁的粒度变细,即仅对要读写的数据加锁而非全局锁。通过加锁来确保在同一时间,只有获得锁的事务可以对数据进行处理。


另一个方法是定义不同类型的锁。因为并不是所有的事务对数据都是写操作,如果两个事务同时对某一数据进行读操作,它们之间并不需要互斥。因此,我们可以通过定义不同类型的锁,以及它们之间的兼容程度来获得更细粒度的控制。


通常,我们定义两种类型的锁:1)共享锁(share-mode lock; S-lock),即当事务获得了某个数据的共享锁,它仅能对该数据进行读操作,但不能写,共享锁有时候也被称为读锁。2)独占锁(exclusive-mode lock; X-lock),即当事务获得了某个数据的独占锁,它可以对数据进行读和写操作,独占锁也常被叫做写锁。共享锁和独占锁的兼容模式如下:


S-lockX-lock
S-lock兼容不兼容
X-lock不兼容不兼容


仅 S-lock 之间互相兼容,只有当多个事务同时持有共享锁时才能同时对数据进行读操作。


定义了锁之后,在事务中对数据的操作必须持有相应的锁。但是问题又来了,什么时候该加锁,什么时候又该释放锁呢?是否应该在事务的开始就对所有的数据都加锁?(这显然不是一个高效的办法,甚至在事务开始的时候,我们可能并不知道要操作哪些数据)。


我们可以先从简单的情况来尝试,比如只在读取和修改数据的时候申请相对应的锁。如下图所示:



(图 1:T1)



(图 2: T2)


图 1 和图 2 分别显示了两个事务对账号 A 和 B 进行操作(假设 A 初始值是 100;B 是 200),事务 T1 用了 X-lock,因为需要对数据进行修改, 而 T2 仅需要使用 S-lock,因为只是读取数据。乍看之下,好像没有问题。无论是 T1 先执行,还是 T2 先执行,T2 中 display(A+B)都会是 300。但是,如果 T1 和 T2 的执行顺序如下:



(图 3:T1 + T2)


这时候,T2 中的 display(A+B)的值就是 250,这是错误的数据。问题出在哪呢?T1 中释放对 B 的 X-lock 过早,使得 T2 获得了一个不正确的数值。既然原因是释放过早,那能不能通过延迟释放锁来解决这个问题。我们把 T1 和 T2 分别改写为 T3 和 T4(唯一的区别就是延缓了锁的释放到最后),如下图所示



(图 4: T3 + T4)


经过验证,这种情况下,无论 T3 和 T4 如何交互,都不再会出现 display(A+B)等于 250 的错误了。把释放锁放在事务的最后是否就解决了所有问题呢?答案是否定的。它确实解决了数据读取不正确的问题,但也同时引入了新问题。



(图 5: T3 + T4)


T3 和 T4 分别获取了对 B 和对 A 的锁并且相互请求对 A 和对 B 的锁。相信大家都看出来了,这导致了死锁(dead lock)。这里就不具体介绍死锁的检查和破坏机制了(详情参见操作系统课),你只需要知道,数据库系统是可以发现死锁的。解决方法也简单,选择其中一个参与的事务,回滚并放弃执行(如果一个不行,就两个)。相对于错误的数据,死锁显然是我们更愿意接受的,所谓两害取其轻。


我们引入了第一个加锁实现:两阶段加锁机制(Two-phase locking protocol)。它要求事务在加锁的过程中遵循下面两步:


1)获取锁阶段(growing phase):在这个过程中,事务只能不断地获取新的锁,但不能释放锁。


2)释放锁阶段(shrinking phase):在这个过程中,事务只能逐渐释放锁,并且无权再获取新的锁。


重要的事情说三遍:千万不要和两阶段提交(Two-phase commit (2PC))搞混;千万不要和两阶段提交搞混;千万不要和两阶段提交搞混。两阶段提交是针对分布式事务的概念,我会在以后的文章中详细讲。


上述的 T3 和 T4 就是遵循两阶段加锁机制,因此数据的正确性是可以保证的。但就像上述所说,两阶段加锁不能避免死锁,依然需要数据系统来检测并破坏死锁。并且,基本款的两阶段提交还会遇到连锁回滚(cascading rollback)。



(图 6: T5 + T6 + T7)


当 T5 执行到 bad thing happen 时,导致出错,那 T6 和 T7 都会需要被回滚。为了避免连锁回滚,我们可以引入两阶段提交的升级版:严格的两阶段加锁(strict two-phase locking protocol)。**除了需要遵循加锁和释放锁的两阶段外,它还规定,对于独占锁(X-lock)必须等到事务结束时才释放。这个规定避免了其他事务对未提交的数据进行读写操作,因此也避免了连锁回滚。另一个更严格的升级本叫做更严格的两阶段加锁(rigorous two-phase locking protocol),**规定了所有获得的锁都得等到事务结束时才释放。


以上就是关于加锁的实现,如果我们总结一下,主要是介绍了这些内容:


1)引入共享锁(S-lock)和独占锁(X-lock)来获得对数据细粒度的控制;


2)引入两阶段加锁(Two-phase locking protocol)来保证数据的正确性;


3)两阶段加锁不能避免死锁,依然需要数据库系统来检查并破坏死锁,破坏死锁可以通过回滚相关的事务来进行;


4)两阶段加锁的两个升级版本:(更)严格的两阶段加锁(rigorous/strict two-phase locking)通过规定把释放锁等到事务结束来避免连锁回滚(cascading rollback)。


时间戳机制(Timestamp-based protocols)

加锁实现是通过比较哪个事务先获得锁来决定事务执行的顺序,以此来保证事务之间的有序性。那除了锁之外,有没有其他方式来衡量先后呢?大家可能都已经想到了,时间戳(Timestamp)。如果每个事务开启的时候,系统可以记录这个事务开启的时间 TS(Ti),记为事务 Ti 的时间,通过比较不同事务的时间戳,我们就能给事务排序了。


如果两个事务的时间戳一模一样呢?其实,有个方法来避免这种情况,通过一个统一的事务管理机制来分发时间戳:每一个事务,不能自行根据执行时间来得到时间戳,而是必须调用一个方法(这个方法可以是由单个线程或者进程管理的)来获得。这个线程就能够保证事务之间的时间戳总有先后关系。


如果你还要考虑极限情况,例如某个方法性能特别高,可以在一个纳秒里面连续发送两个时间戳。面对这种极限情况,我们的解决方法是不必用真实的时间来表示时间戳,可以用数字计数(logical counter)来表示相对时间。管理线程只需维护一个计数,在分发计数的同时不断自增即可。


我们可以通过比较事务的时间戳来保证事务之间的有序性。假定 Ti 和 Tj 的时间戳分别为 TS(Ti)及 TS(Tj)。如果 TS(Ti)<TS(Tj),数据库系统就需要保证无论如何调度实现,都和序列化执行 Ti 然后 Tj 一致。


如何实现呢?首先,我们引入两个概念:


1)W-timestamp(A): 记录对于数据 A,最近一次被某个事务修改的时间戳。


2)R-timestamp(A): 记录对于数据 A,最近一次被某个事务读取的时间戳。


一旦有一个更新的事务成功地对数据进行读取,相对应的读写时间戳就会被更新。


下面,我们给出用时间戳机制实现事务的定义:


对于事务 Ti 要读取数据 A read(A):


  1. 如果 TS(Ti) < W-timestamp(A),说明 A 被一个 TS 比 Ti 更大的事务改写过,但 Ti 只能读取比自身 TS 小的数据。因此 Ti 的读取请求会被拒绝,Ti 会被回滚。

  2. 如果 TS(Ti) > W-timestamp(A),说明 A 最近一次被修改小于 TS(Ti),因此读取成功,并且,R-timestamp(A)被改写为 TS(Ti)。


对于事务 Ti 要修改数据 A write(A):


  1. 如果 TS(Ti) < R-timestamp(A),说明 A 已经被一个更大 TS 的事务读取了,Ti 对 A 的修改就没有意义了,因此 Ti 的修改请求会被拒绝,Ti 会被回滚。

  2. 如果 TS(Ti) < W-timestamp(A),说明 A 已经被一个更大 TS 的事务修改了,Ti 对 A 的修改也没有意义了,因此 Ti 的修改请求会被拒绝,Ti 会被回滚。

  3. 其他情况下,Ti 的修改会被接受,同时 W-timestamp(A)会被改写为 TS(Ti)。


一旦一个事务因为任何原因被回滚,再次重新执行时,会被系统分配一个新的 TS。


通过上述规则,系统就可以保证对于任意 Ti 和 Tj,如果 TS(Ti)<TS(Tj),Ti 比 Tj 先运行完。我们通过一个示例来看时间戳是如何运行的。


假定下面两个事务 T1 和 T2,并且 TS(T1) < TS(T2)。



(图 7: T1 + T2)


那么如下的调度根据时间戳机制就是合理的调度



(图 8: T1 + T2 调度)


两边的 display(A+B)都会返回正确的数据。时间戳机制保证了有序性,因为读写都会根据事务的时间戳进行比较再回滚。这种机制同时也避免了死锁,虽然有可能导致饥饿(starvation):某些运气不好的长事务因为不停地失败被回滚然后重试。


有什么方法能够让时间戳机制进一步提高并发性?



(图 9: T3 + T4)


我们假定 TS(T3) < TS(T4)。首先,T3 的 read(A)会成功。其次,T4 的 write(A)也会成功,因为 T4 的时间戳大于 T3。最后,当 T3 试图 write(A)时会失败,因为 TS(T3) < W-timestamp(A) = TS(4)。因此根据时间戳机制,T3 的 write(A)会失败并被回滚。但事实上,即使不回滚 T3 也不会有问题。因为 T4 已经修改了 A 的值,那么 T3 的修改从时间戳角度来看,已经没有意义,因为不会被其他事务读取:任何 TS 小于 T4 对 A 的读取都会被拒绝然后回滚(因为 TS(Ti) < W-timestamp(A) = TS(T4));而任何 TS 大于 T4 对 A 的读取都会读取 T4 修改后的 A 值。利用这个发现,我们可以改进时间戳机制来使得无意义的修改操作可以直接被忽略。


这个改进策略被称为托马斯的修改规则(Thomas’ write rule): 假设 Ti 要 write(A):


  1. 如果 TS(Ti) < R-timestamp(A),说明 A 已经被一个更大 TS 的事务读取了,Ti 对 A 的修改就没有意义了,因此 Ti 的修改请求会被拒绝,Ti 会被回滚。

  2. 如果 TS(Ti) < W-timestamp(A),说明 Ti 的修改没有意义,因此这个修改操作会被忽略。

  3. 其他情况下,Ti 的修改会被接受,同时 W-timestamp(A)会被改写为 TS(Ti)。


可见,仅第二条规则被改进了。


总结

这篇文章主要介绍了两类对事务隔离的实现,分别是加锁实现机制和时间戳机制。


在加锁实现机制中,介绍了两阶段加锁(Two-phase locking protocol),通过将事务划分成获取锁阶段和释放锁阶段来保证数据的正确性。同时引入了改进机制,严格的两阶段加锁(rigorous/strict two-phase locking protocol)来避免连锁回滚。两阶段加锁虽然能够保证正确性,却无法避免死锁。因此,需要数据库系统能够检查并破坏死锁。


时间戳机制是通过对每个事务定义时间戳,以及对读写数据记录时间戳来保证正确性。时间戳机制本身也避免了死锁,托马斯的修改规则可以进一步优化时间戳机制。但这两种机制并不是目前常见的实现,下一篇文章,我们会介绍更主流的多版本并发控制(MVCC)。


2020 年 5 月 26 日 16:304767

评论 9 条评论

发布
用户头像
两阶段加锁机制升级版

两阶段提交的升级版

2022 年 01 月 25 日 14:12
回复
用户头像
作者留言: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
回复
有个图挂了,能补一下吗

2021 年 11 月 08 日 11:58
回复
用户头像
通过上述规则,系统就可以保证对于任意 Ti 和 Tj,如果 TS(Ti)
这里是不是应该说是操纵相同数据的事务 Ti 和 Tj
2020 年 09 月 30 日 11:49
回复
用户头像
当 T5 执行到 bad thing happen 时,导致出错,那 T6 和 T7 都会需要被回滚。为了避免连锁回滚,我们可以引入两阶段提交的升级版:严格的两阶段加锁 (strict two-phase locking protocol)。

这里是不是写错了,应该是两阶段锁吧
2020 年 09 月 30 日 11:29
回复
用户头像
有个图挂了。
2020 年 09 月 03 日 12:18
回复
用户头像
作者来留个言,最近有点忙,因为到half结尾了,roadmap planning, performance review等工作特别忙。外加疫情愈发严重。。。心情很是沉重。 有点拖更了。但是,新的一期已经在写作中,请期待,谢谢。
2020 年 07 月 17 日 03:54
回复
读完了每一篇,写得太好了。作者加油呀
2020 年 07 月 20 日 00:23
回复
没有更多了
发现更多内容

芝士就是力量!蒙牛2021年报笑出大大的CHEESE

科技新消息

教你三步实现CDH到星环TDH的平滑迁移

星环科技

国产数据库

龙蜥社区&龙蜥开发者获CSDN 2021年度技术影响力「年度开源项目」奖和「年度社区之星」

OpenAnolis小助手

开发者 开源项目 龙蜥社区 年度影响力 社区之星

制造业企业数据平台建设最佳实践分享

华为云开发者联盟

数字化转型 数据平台 制造业 华为工业云平台 数据应用

领域驱动设计入门与实践[下]

LigaAI

团队管理 DDD 领域驱动设计思想 LigaAI

天翼云新一代V5云主机,Kvm之生,Xen之死!

天翼云开发者社区

每周更新 | Verilog测试用例及波形展示图功能上线

ShowMeBug

【网络安全】网络安全堡垒机多少钱?有什么用?

行云管家

网络安全 信息安全 数据安全 堡垒机 企业安全

PolarDB-X 正式发布2.1.0版本,Paxos 重磅开源

阿里云数据库开源

数据库 阿里云 开源 分布式 PolarDB-X

整机生产制造头部厂商雷神科技加入龙蜥社区

OpenAnolis小助手

Linux 开源 整机

专属云资源包计算规格探秘

天翼云开发者社区

夯实领军者地位 奶酪业务协同发展领先赛道

科技新消息

Linux 管道操作符详解

CRMEB

打造中国优质奶源基地 筑牢高质量发展基石

科技新消息

易观分析:海外业务亮眼,研发+IP运营助力中手游持续增长

易观分析

IP 中手游

天翼云分布式缓存服务(Redis)的几个核心概念

天翼云开发者社区

61%!产品+渠道创新 蒙牛冰淇淋业绩收录有史高增长

科技新消息

爆款国民冰淇淋原来是这样“凝冻”出来的

科技新消息

墨天轮访谈 | 腾讯张铭:带你揭秘王者荣耀背后的游戏数据库 TcaplusDB

墨天轮

数据库 TcaplusDB 国产数据库

把一整个生态圈藏进大沙漠 看蒙牛如何在每一滴奶中藏进玄机

科技新消息

设计消息队列存储消息数据的 MySQL 表格

唐尤华

架构实战营

蒙牛2021年报:数智化大脑为乳业插上腾飞翅膀

科技新消息

再论ORACLE上云通用技术方案

天翼云开发者社区

使用 Amazon Cloud WAN 构建您的全球网络

亚马逊云科技 (Amazon Web Services)

Builder 专栏

自动化运维发展趋势以及好用工具推荐

行云管家

运维 IT运维 自动化运维

java培训浅谈程序员怎么避免面试过程中碰壁

@零度

面试 JAVA开发

人工智能融合赋能平台,赋能智慧城市智能化升级

脑极体

天翼云分布式缓存服务(Redis)的应用场景(干货)

天翼云开发者社区

TypeScript 之 any:哪里可以用?哪里不能用?

杨成功

4月月更

4k/8k超高清时代,如何利用媒体处理技术加速数字化升级

4k/8k超高清时代,如何利用媒体处理技术加速数字化升级

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