【AICon】探索RAG 技术在实际应用中遇到的挑战及应对策略!AICon精华内容已上线73%>>> 了解详情
写点什么

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

  • 2020-05-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-05-26 16:306334

评论 11 条评论

发布
用户头像
图挂了
2023-01-13 17:29 · 北京
回复
用户头像
两阶段加锁机制升级版

两阶段提交的升级版

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

架构师训练营第7周总结

时来运转

JVM 类加载机制

Alex🐒

JVM 深入理解JVM

Phobos新变种藏身系统激活工具再掀勒索风暴,360安全大脑强力“截杀”

360安全卫士

Combine中@Published浅析

kingnight_pig

swift Combine Publisher

官宣了,英特尔并非断供浪潮而是属于内部供应链调整

Geek_116789

架构师课程第七周总结

dongge

创世 | 中国古神话

chaozh

神话

神国统治者 | 中国古神话

chaozh

Presto性能调优的五大技巧

华为云开发者联盟

大数据 数据 内存 存储 华为云

程序员面试必备战衣 | T恤衫 - 程序员穿搭

chaozh

GEEK

每个现代人都应该知道的包豪斯| 艺术

chaozh

腾讯的背水一战还是奋力一搏? | 互联网

chaozh

数据产品经理必备技能大纲

Jackchang234987

产品 产品经理 数据

创建有效DevOps测试策略的5大技巧

禅道项目管理

DevOps 测试 云安全

架构师训练营第7周作业

时来运转

彻底弄懂C++11右值引用 | 技术总结

chaozh

c++

深入Java Web技术内幕(一)浅析Web请求过程

itlemon

Java

女娲造物与补天 | 中国古神话

chaozh

人民自己创造的节日 | 经济

chaozh

第7周性能优化

架构师训练营第七周作业-性能测试

sunnywhy

优雅地利用c++编程从1乘到20 | 技术总结

chaozh

c++

如何挑选编程笔记本 | 数码产品

chaozh

JVM 对象内存布局

Alex🐒

JVM 深入理解JVM

极客时间架构师训练营week7作业

好名字

极客大学架构师训练营 作业

读梁宁产品30讲随笔(1)

Jackchang234987

产品 产品思维

Spring Cloud微服务技术栈:搭建高可用Eureka Server、服务注册与发现

itlemon

Spring Cloud

一文读懂数据库中的乐观锁和悲观锁和MVCC

X先生

数据库 乐观锁 悲观锁 并发控制

放下纠结,你就远离了拖延症

霍太稳@极客邦科技

创业 个人成长 企业管理

深入浅出开源监控系统Prometheus(上)

vivo互联网技术

监控 Prometheus

深入 Java Web 技术内幕(二)浅析DNS域名解析过程

itlemon

DNS 域名解析

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