数据库管理系统-从基本原理到系统构建 课件 08 并发控制

数据库系统—并发控制1清华大学计算机系李国良第8章并发控制2并发控制数据库系统—并发控制3数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录4数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录5并发控制概览并发：在同一时间间隔内有多个事件或活动发生多个事务相继到来：数量少，间隔久

-->依次执行数量多，间隔短-->并发控制考虑要素事务、语句的执行顺序数据对象的共享和保护数据库系统—并发控制6并发控制概览写写冲突

丢失更新写读冲突

脏读读写冲突

不可重复读、幻读数据库系统—并发控制T1T2startcommitR(A)W(A)startcommitR(A)W(A)T1T2start

abortW(A)startcommitR(A)T1T2startcommitR(A)R(A)startcommitW(A)T1T2startcommitcount(*)count(*)startcommitInsert(A)写写冲突

丢失更新写读冲突

脏读读写冲突

不可重复读读写冲突

幻读7并发控制概览评价并发控制技术的指标：

数据库系统—并发控制隔离级别脏读不可重复读幻读读未提交允许允许允许读已提交不允许允许允许可重复读不允许不允许允许可串行化不允许不允许不允许②调度可恢复性①隔离级别8并发控制概览解决冲突的思想悲观并发控制技术：事前控制，避免冲突发生两阶段锁基于图的协议乐观并发控制技术：事后控制，冲突发生后再处理时间戳排序协议乐观并发控制协议数据库系统—并发控制多版本机制保存数据项的多个版本，通过空间复用提升并发度与悲观、乐观并发控制技术相结合多版本两阶段锁协议多版本时间戳排序协议多版本乐观并发控制协议9数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录10数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录锁两阶段锁死锁基于图的锁协议锁的粒度闩锁11数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录锁两阶段锁死锁基于图的锁协议锁的粒度闩锁12锁锁：数据项的访问权限只有持有锁才可访问数据项锁的类型共享锁（shared

lock，S锁）:如果某事务在数据项上加了共享锁,则该事务只能读取该数据项但不能对其进行修改此时其他事务可在该数据项上加上共享锁，但不能加互斥锁互斥锁（exclusive

lock，X锁）如果某事务在数据项上加了互斥锁，则该事务既能读取该数据项也能对其进行修改此时其他事务既不能在该数据项上加共享锁，也不能加互斥锁数据库系统—并发控制13锁

数据库系统—并发控制共享锁互斥锁共享锁相容不相容互斥锁不相容不相容14锁基本使用方式事务访问数据项前应先加锁只进行读取操作则申请共享锁要进行读写操作则申请互斥锁授予锁的条件数据项未被加锁，则可允许当前加锁请求数据项已被加锁，根据相容性处理可授予相容的共享锁拒绝不相容的加锁请求，申请加锁事务应当等待当前持有锁的事务释放锁事务释放锁的两种方式在执行期间显式地释放锁在终止时释放锁，包括事务撤销或者完成提交数据库系统—并发控制15锁带来的问题

数据库系统—并发控制16锁带来的问题避免饿死同时考虑相容性和事务到来顺序先来先服务：优先满足先来的事务数据库系统—并发控制17锁的数据结构锁表（哈希表）键：数据项值：若干个锁信息项锁信息项锁的类型请求的事务数据库系统—并发控制18普通锁不能解决可串行化调度问题数据库系统—并发控制T1:

R(A)

W(A)

R(B)

W(B)T2:

R(A)

R(B)T1:

R(A)

W(A)

R(B)

W(B)T2:

R(A)

R(B)T1T21Read(A)

2Read(A)3A=A+1

4Write(A)5Read(B)6Read(B)7A+B8Commit9B=B-110Write(B)11CommitT1T21X-Lock(A)

2Read(A)

3

S-Lock(A)4Write(A)5Unlock(A)

6Read(A)7S-Lock(B)8X-Lock(B)9Read(B)10Unlock(A)11Unlock(B)12Read(B)Commit13Write(B)14Unlock(B)15Commit事务调度不可串行化19两阶段锁能解决可串行化调度问题数据库系统—并发控制T1:

R(A)

W(A)

R(B)

W(B)T2:

R(A)

R(B)T1:

R(A)

W(A)

R(B)

W(B)T2:

R(A)

R(B)T1T21Read(A)

2Read(A)3A=A+1

4Write(A)5Read(B)6Read(B)7A+B8Commit9B=B-110Write(B)11CommitT1T21X-Lock(A)

2Read(A)

3

S-Lock(A)4Write(A)5X-Lock(B)

6Unlock(A)

7Read(A)8S-Lock(B)9Read(B)10Write(B)11Unlock(B)12CommitRead(B)13Unlock(A)14Unlock(B)15Commit事务调度可串行化但可能

不可恢复20严格两阶段锁能解决可串行化调度问题数据库系统—并发控制T1:

R(A)

W(A)

R(B)

W(B)T2:

R(A)

R(B)T1:

R(A)

W(A)

R(B)

W(B)T2:

R(A)

R(B)T1T21Read(A)

2Read(A)3A=A+1

4Write(A)5Read(B)6Read(B)7A+B8Commit9B=B-110Write(B)11CommitT1T21X-Lock(A)

2Read(A)

3

S-Lock(A)4Write(A)5X-Lock(B)

6Read(B)

7Write(B)8Commit9Unlock(A)10Unlock(B)Read(A)11S-Lock(B)12Read(B)13Commit14Unlock(A)15Unlock(B)可串行化也可恢复事务调度21目录数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较锁两阶段锁死锁基于图的锁协议锁的粒度闩锁22两阶段锁

数据库系统—并发控制23两阶段锁事务的两个阶段：增长阶段（growingphase）事务可以获得所需的锁，但不能释放锁收缩阶段（shrinkingphase）事务可以释放已获得的锁，但不能申请新的锁数据库系统—并发控制24两阶段锁

数据库系统—并发控制25两阶段锁

数据库系统—并发控制26两阶段锁：不可恢复和级联回滚

数据库系统—并发控制27两阶段锁：S2PL和SS2PL支持可恢复调度，避免级联回滚：严格两阶段锁协议（strict2PL，S2PL）左图事务在提交后才可以释放所有互斥锁，但可以提前释放共享锁强两阶段锁协议（strongstrict2PL/rigorous2PL，SS2PL）右图所有锁都必须在事务提交后才释放数据库系统—并发控制28两阶段锁：S2PL和SS2PLS2PL相比SS2PL可以提前释放共享锁，得到更高的读并发效率。数据库系统一般采用S2PL保证可串行化调度保证可恢复调度，无级联回滚提前释放共享锁，提升并发性能数据库系统—并发控制29两阶段锁：隔离级别两种加锁方式给数据表加锁避免脏写、脏读、不可重复读、幻读问题，实现了可串行化调度会使事务等待锁的时间很长，影响并发度给数据项（记录、属性值、索引key）加锁避免脏写、脏读、不可重复读问题，不能避免幻读为了解决幻读问题，实现可串行化调度，可以使用多粒度锁和意向锁（第8.2.6节介绍）。基本思想是加谓词锁，即对查询的范围加锁，不允许其他并发事务在查询范围内添加、删除数据数据库系统—并发控制30数据库系统—并发控制目录01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较锁两阶段锁死锁基于图的锁协议锁的粒度闩锁31死锁死锁事务彼此都持有锁又同时在等待对方释放所需要的锁不能继续执行并因此陷入了持续的等待状态数据库系统—并发控制32死锁处理方法死锁预防在协议设计上保证数据库不会进入死锁状态死锁检测与恢复允许死锁的发生，但能够及时地意识到死锁的发生并进行处理锁超时重启设置事务最长等待时间数据库系统—并发控制33死锁预防事务时间戳：确定事务顺序两种算法：等待死亡Wait-Die（旧事务等待新事务）伤害等待Wound-Wait（新事务等待旧事务）数据库系统—并发控制Wait-DieWound-Wait34死锁预防

数据库系统—并发控制35死锁预防数据库系统—并发控制等待顺序Wait-DieWound-Wait

Wait36死锁预防等待关系两个算法都只允许一种类型的等待存在Wait-Die

旧事务等待新事务Wound-Wait

新事务等待旧事务事务间的等待关系不会构成环，因此可以防止死锁的发生。数据库系统—并发控制Wait-DieWound-Wait37死锁检测与恢复

数据库系统—并发控制38死锁检测与恢复数据库系统—并发控制

39死锁检测与恢复检测频率间隔太短，死锁又不经常发生，则会造成资源浪费间隔太久，出现死锁要较长时间才被检测到，影响数据库效率动态改变检测间隔死锁恢复：撤销一个或多个事务以打破死锁合理选择“牺牲者”，即需要撤销的事务：事务开始运行的时间戳事务已经执行的SQL语句数量事务已经加锁的数据项的数量事务回滚的程度：全部回滚/部分回滚避免事务饿死数据库系统—并发控制40锁超时重启设置事务最长等待时间如果申请加锁的事务在该时间结束时仍未获得锁，即事务超时，那么此时将该事务回滚并重启当事务之间确实存在死锁时，该方法会让死锁中的一个或者多个事务回滚并重启，而其他事务继续执行，解决了死锁问题适用场景事务执行时间都比较短事务长时间的等待大多都是死锁造成的问题：难以合理设置等待时间数据库系统—并发控制41数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录锁两阶段锁死锁基于图的锁协议锁的粒度闩锁42基于图的锁协议

数据库系统—并发控制43树形协议

数据库系统—并发控制44树形协议

数据库系统—并发控制45树形协议

数据库系统—并发控制46树形协议优点保证冲突可串行化不会产生死锁只有一种等待关系：持有父节点锁，等待子节点锁较早释放锁减少了其他事务等待时间，增加了并发度数据库系统—并发控制47树形协议

数据库系统—并发控制48数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录锁两阶段锁死锁基于图的锁协议锁的粒度闩锁49锁的粒度数据项的粒度：属性、元组、页面、表、整个数据库锁的粒度：基于数据项的粒度粒度越大，数据项越少，管理锁的开销越小；事务之间发生冲突的可能性越大，并发度越低粒度越小，系统开销越大，并发度越高使用锁时，需要权衡并发度和系统开销提出多粒度锁数据库系统—并发控制50多粒度锁多粒度锁数据库中的所有对象按照大小的不同构成了一棵多粒度树

多粒度树中的每一个节点可以独立地加锁对某个节点加锁表示对该节点的后代节点加同类型的锁数据库系统—并发控制51多粒度锁数据项的两种加锁状态：显式锁：该数据项被直接加上的锁隐式锁：该数据项没有被直接加锁，由于其祖先节点被加锁而变为加锁状态对数据项加锁情况的检查显式锁：直接检查隐式锁：检查祖先节点上的锁（可能导致当前节点加上隐式锁）检查后代节点上的锁（当前节点的加锁会为后代节点加上隐式锁）检查隐式锁开销较大，提出意向锁，加速对隐式锁的检查数据库系统—并发控制52意向锁对多粒度树中任一节点加锁时，需要先对其所有祖先点加意向锁意向共享锁：如果要对某个数据项加共享锁，先对其祖先点加意向共享锁（记为IS锁）意向互斥锁：如果要对某个数据项加互斥锁，先对其祖先点加意向互斥锁（记为IX锁）共享意向互斥锁，记为SIX锁，表示共享锁+IX锁。对某数据项加SIX锁，表示在对该数据项显式加共享锁的同时加IX锁数据库系统—并发控制53意向锁意向锁相容性矩阵数据库系统—并发控制共享锁互斥锁意向共享锁意向互斥锁共享意向互斥锁共享锁相容不相容相容不相容不相容互斥锁不相容不相容不相容不相容不相容意向共享锁相容不相容相容相容相容意向互斥锁不相容不相容相容相容不相容共享意向互斥锁不相容不相容相容不相容不相容54意向锁使用意向锁后，对数据项加锁情况的检查检查数据项自身的锁是否相容检查数据项的祖先节点的锁是否相容不需要检查后代节点数据库系统—并发控制55隔离级别的支持为了提升系统性能，尽量给较小的数据粒度上锁涉及插入、更新、删除数据的操作时，使用多粒度锁会引发幻读问题数据库系统—并发控制SnoSnameSage2021310721李博172021310722赵宇192021310723张敏1856隔离级别的支持幻读问题主要有两种解决方法谓词锁SELECT*FROM<table>

WHERE<qualification>

FORUPDATE;索引区间锁数据库系统—并发控制Postgres:FORSHAREMySQL:LOCKINSHAREMODE57谓词锁

数据库系统—并发控制58谓词锁示例：左图：不使用谓词锁，有幻读右图：使用谓词锁，无幻读数据库系统—并发控制59索引区间锁

数据库系统—并发控制60索引区间锁性能分析：当事务做插入、更新或删除操作时，需要更新索引，同时检查索引区间锁。由此可知，索引区间锁的检查与索引更新同步，开销较小索引区间锁扩大了锁的范围，导致更多锁冲突和等待是一种折衷的方法适用性：对于某些事务，其谓词中的属性上没有索引，无法使用索引区间锁，可以给整个表上锁数据库系统—并发控制61数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录锁两阶段锁死锁基于图的锁协议锁的粒度闩锁62闩锁

数据库系统—并发控制63闩锁闩锁与并发控制中锁的比较数据库系统—并发控制

锁闩锁隔离级别事务线程保护对象数据项内存中的数据结构存在周期整个事务活动中临界区段模式共享锁、互斥锁等读、写死锁情况可能出现，需要处理不会出现死锁处理死锁预防，检测与恢复等代码规范存在场所锁管理器所保护的数据结构64自旋锁在多线程环境中，获得共享资源的访问权限未获得锁的线程将在保持CPU占用的状态下，一直循环等待，即通过自旋（自我循环，不释放CPU资源）的方式来获得锁数据库系统—并发控制65两阶段锁的隔离级别数据库系统—并发控制脏写不加任何锁脏读隔离级别技术脏写脏读不可重复读幻读无隔离要求不加锁是是是是读未提交仅写加锁，写完释放锁否是是是读已提交写加行锁，事务提交完释放锁；读加读行锁，读完一次释放否否是是可重复读写加行锁，事务提交完释放锁；读加读行锁，所有读完释放否否否是可串行化写加表锁，提交完释放锁；读加读锁，读完释放写加行锁，提交完释放锁；读加谓词锁，读完释放否否否否66数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录67数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录时间戳时间戳排序协议乐观并发控制协议68数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录时间戳时间戳排序协议乐观并发控制协议69乐观并发控制技术悲观并发控制技术的缺点：管理锁的开销大需要解决死锁可能回滚，开销大一些应用场景是高并发低竞争的两种并发控制协议：时间戳排序协议：每次读写数据时都检查是否满足调度隔离级别，如果不满足则回滚乐观并发控制协议：将数据拷贝到私有工作区，全部处理结束后，再集中检查是否满足调度隔离级别，如果不满足则回滚数据库系统—并发控制70数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录时间戳时间戳排序协议乐观并发控制协议71时间戳

数据库系统—并发控制72数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录时间戳时间戳排序协议乐观并发控制协议73时间戳排序协议

数据库系统—并发控制74时间戳排序协议

数据库系统—并发控制

过晚读75时间戳排序协议

数据库系统—并发控制

过晚写过晚写76时间戳排序协议

数据库系统—并发控制77时间戳排序协议

数据库系统—并发控制0000

1000

2000

2220

2200

2220

78时间戳排序协议数据库系统—并发控制T1T2startcommitR(A)

W(A)R(B)W(B)startcommitR(A)W(A)R(B)W(B)objectR-TSW-TSA00B00TS(T1)=1TS(T2)=2objectR-TSW-TSA11B00objectR-TSW-TSA22B00objectR-TSW-TSA22B11objectR-TSW-TSA22B22Success

79时间戳排序协议数据库系统—并发控制T1T2startR(A)

W(A)R(B)W(B)startcommitR(A)W(A)R(B)W(B)objectR-TSW-TSA00B00TS(T1)=1TS(T2)=2objectR-TSW-TSA11B00objectR-TSW-TSA22B00objectR-TSW-TSA22B22objectR-TSW-TSA22B22abort80时间戳排序协议数据库系统—并发控制T1T2T3T41R(X)2R(Y)3R(Y)4W(Y)5W(Z)6R(Z)7R(X)8R(X)9W(Z)10W(Y)11W(Z)1R-TSW-TSX40Y00Z002R-TSW-TSX40Y20Z003R-TSW-TSX40Y20Z004R-TSW-TSX40Y23Z005R-TSW-TSX40Y23Z036R-TSW-TSX40Y23Z437R-TSW-TSX40Y23Z438R-TSW-TSX40Y23Z439R-TSW-TSX40Y23Z4310R-TSW-TSX40Y24Z4311R-TSW-TSX40Y24Z4481时间戳排序协议：托马斯写规则

数据库系统—并发控制

82时间戳排序协议：托马斯写规则数据库系统—并发控制基本时间戳协议不允许：(TS(T1)<TS(T2))R2(X)W1(X)W2(X)R1(X)W2(X)W1(X)允许

：所有T1

在T2之前的操作R2(X)R1(X)Thomas写规则不允许：(TS(T1)<TS(T2))R2(X)W1(X)W2(X)R1(X)允许

：所有T1

在T2之前的操作R2(X)R1(X)过时写:W2(X)W1(X)83时间戳排序协议：托马斯写规则数据库系统—并发控制T1T2startcommitR(A)

W(A)W(B)startcommitR(A)W(A)R(B)W(B)abortT1T2startcommitR(A)

W(A)W(B)startcommitR(A)W(A)R(B)W(B)Skip

W(B)

and

okThomasBasic84时间戳排序协议-隔离级别通过时间戳来支持不同的隔离级别，包括读已提交、可重复读和可串行化支持可重复读：缓存第一次读取的数据，避免不可重复读解决幻读问题：修改时间戳，避免读取新插入和新删除的数据（即忽略时间戳大于事务时间戳的数据项）时间戳排序协议不使用锁，可以提升系统的并发度，同时消除了使用锁带来的开销数据库系统—并发控制85时间戳排序协议-问题

数据库系统—并发控制

86时间戳排序协议-问题为了保证可恢复调度和无级联回滚，可以修改时间戳排序协议：支持可恢复调度：如果事务T读取了其他事务所写的数据项，那么只有在T依赖的其他写事务提交之后，事务T才能提交。这样可以保证可恢复调度，但不是保证无级联回滚支持无级联回滚：如果事务T要读取其他未提交事务所写的数据项，那么T必须阻塞，必须等待写该数据项的事务提交后才能读取。这样可以保证可恢复调度和无级联回滚，需要锁机制才能阻塞T，因此要结合其他技术数据库系统—并发控制87严格时间戳排序协议-解决调度可恢复问题

数据库系统—并发控制//托马斯写如果isCommit(X)为真，忽略此操作；如果isCommit(X)为假，则等待;直到为真时，重新再执行该写操作88时间戳排序协议-问题问题二：饿死一系列短事务与某个开始较早但执行时间较长的事务冲突时，长事务不断的重启而饿死。解决办法为调整事务重启策略：如果某个事务反复重启，则暂停与之冲突的其他事务，使该事务正常完成。数据库系统—并发控制89数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录时间戳时间戳排序协议乐观并发控制协议90乐观并发控制协议如果事务冲突较少、执行时间较短，可采用乐观并发控制（OCC）三个阶段读阶段：从数据库中读取需要的数据项，存放于事务私有工作区；在工作区进行写操作ReadSet(T)和WriteSet(T)：事务T读数据项集合（读集）和写数据项集合（写集）验证阶段：有效性检查测试是否满足所需的隔离级别。若检测失败，终止事务，然后重启；否则进入写阶段对于读操作：事务读取值

=

当前数据库中的值对于写操作：事务提交写操作结果后，数据库仍处于一致的状态写阶段：将私有工作区中的更新数据刷新到数据库里。私有工作区保证调度是可恢复的、无级联回滚的。数据库系统—并发控制91乐观并发控制协议——验证阶段

数据库系统—并发控制92乐观并发控制协议——验证阶段有效性验证方法（以反向验证为例）每个事务有五个时间戳:StartTime(T)：事务开始执行的时间ReadTime(T)：读阶段开始时间ValidationTime(T)：验证阶段开始的时间WriteTime(T)：写阶段开始的时间CommitTime(T)：写阶段结束时间，即事务结束后提交的时间由于事务可能重启，在验证阶段才真正决定事务执行的先后顺序，因此一般将事务进入验证阶段时间作为事务的时间戳，即TS(T)=ValidationTime(T)。对于读操作，只需要验证事务读取值

=

当前数据库中的值对于写操作，需要校验当前事务𝑇是否与已经提交的事务𝑇′存在读写（𝑇′先写𝑇后读）、写读（𝑇′先读𝑇后写）、写写冲突数据库系统—并发控制93乐观并发控制协议——验证阶段有效性验证方法中对写操作的验证：以下四条规则中，至少满足一条即可保证当前事务𝑇与已经提交的事务𝑇′没有写操作冲突（1）𝑇′的提交时间CommitTime(𝑇′)小于𝑇的读阶段开始时间ReadTime(T)。由于𝑇开始读阶段前，𝑇′已经结束。因此𝑇′肯定和𝑇没有冲突，校验通过数据库系统—并发控制94乐观并发控制协议——验证阶段

数据库系统—并发控制95乐观并发控制协议——验证阶段

数据库系统—并发控制96乐观并发控制协议——验证阶段

数据库系统—并发控制97乐观并发控制协议——验证阶段

数据库系统—并发控制98乐观并发控制协议验证阶段保证调度可串行化单独的工作区保证调度是可恢复的两种乐观并发控制方法对比：时间戳排序协议：事务每做一个操作（读操作/写操作）就会根据协议规则进行一次判断，使事务回滚或继续运行。不可恢复的。乐观并发控制协议：一个事务执行完所有操作后，再根据规则判断事务提交或回滚。这减少了判断次数，减小判断开销。同时导致一些事务完整执行完后被回滚，开销大。更适合事务执行时间短、并发冲突少的场景。可恢复的。两者都因为频繁事务重启而导致某些事务饿死。数据库系统—并发控制99数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较目录100数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较多版本时间戳排序协议多版本两阶段锁协议多版本乐观并发控制协议版本存储版本删除多版本机制中的索引管理多版本机制的实际应用目录101数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较多版本时间戳排序协议多版本两阶段锁协议多版本乐观并发控制协议版本存储版本删除多版本机制中的索引管理多版本机制的实际应用目录102多版本机制数据库系统—并发控制多版本并发控制：对于一个数据项，保存多个物理版本，供不同的事务使用前面介绍的方法通过时间复用实现并发控制，多版本机制通过空间复用实现高效并发控制基本原则：事务对数据项进行写操作时，产生该数据项的一个新版本事务对数据项进行读操作时，读取事务开始时该数据项的最新版本优点：事务的读操作无需等待其他事务的写操作事务的写操作无需等待其他事务的读操作103多版本机制数据库系统—并发控制数据项A有多个版本，表示小明的银行卡余额。每个版本的数据内容不同，且有效的开始时间和结束时间前后连续。最开始，小明有1500元，随后通过勤工俭学收入了300元变为1800元，然后他又花了50元充值网费，还剩1750元版本内容时间戳15000180010175011104数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较多版本时间戳排序协议多版本两阶段锁协议多版本乐观并发控制协议版本存储版本删除多版本机制中的索引管理多版本机制的实际应用目录105多版本时间戳排序协议数据库系统—并发控制

106多版本时间戳排序协议数据库系统—并发控制

107多版本时间戳排序协议数据库系统—并发控制

108多版本时间戳排序协议数据库系统—并发控制示例

00

1022

10109多版本时间戳排序协议数据库系统—并发控制

110数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较多版本时间戳排序协议多版本两阶段锁协议多版本乐观并发控制协议版本存储版本删除多版本机制中的索引管理多版本机制的实际应用目录111多版本两阶段锁协议数据库系统—并发控制

112多版本两阶段锁协议数据库系统—并发控制

113多版本两阶段锁协议数据库系统—并发控制方法一的隔离级别：满足读已提交（只允许读已提交的版本）、可重复读（多次读取的时间戳一致），也可以避免幻读（不读取事务时间戳之后的删除和添加的数据），但不满足传统的可串行化。

114多版本两阶段锁协议数据库系统—并发控制这种多版本机制满足的隔离级别一般称为快照隔离（snapshot

isolation）。快照隔离就是为每个事务的读准备一个快照（一个时间戳的版本），这个快照一旦建立就不会再被修改，从而在这个快照上达到了隔离的作用。但是当不同事务在快照上存在读写冲突时，可能造成不满足串行化为了满足可串行化，有可串行化快照隔离，其在快照隔离的基础上来检测该调度是否满足可串行化，如果不满足就回滚。感兴趣的同学可以查阅论文SerializableIsolationforSnapshotDatabases（SIGMOD2008）了解如何实现可串行化快照隔离115多版本两阶段锁协议数据库系统—并发控制对于更新事务的方法二：读写操作都加严格两阶段锁。为了解决方法一不满足可串行化的问题，对读操作加共享锁，对写操作加互斥锁，从而实现可串行化。为了实现这一机制，将读操作分为两种快照读，即根据时间戳来读取小于事务时间戳的最新版本。快照读一般只用于只读事务、对读写没有影响的事务、或者不需要可串行化调度的场景当前读，即读取最新版本并加锁来实现并发读写。加锁分为共享锁（select）和互斥锁（update，insert，delete语句）。如果根据读写操作简单的加共享锁和互斥锁就退化成了基于两阶段锁的并发控制协议。为了解决这一问题，一些数据库通过添加两类SQL语法来对select操作指定共享锁还是互斥锁。这需要SQL开发者了解数据访问需要加共享锁还是互斥锁，选用合适的select语法，从而提升事务处理的性能。116多版本两阶段锁协议数据库系统—并发控制Select语句分为以下三种selectforshare语法：指定共享锁，用于读取一些数据并防止这些数据被其他事务中间修改（防止读写冲突）写法：select*fromStudentswhereSID=“2021310721”forshare例：一个航空公司的规则是如果会员积分超过1万积分则将其设置为金牌会员。这个事务需要首先选取出积分大于1万的会员，然后将其改成金牌会员，而在此事务操作中不允许更改（消费）积分来防止积分中途小于1万。采用当前读，读取最新的数据项，并对这些数据项加共享锁selectforupdate语法：指定互斥锁，用于读取一些数据并防止这些数据被其他事务中间修改（防止写写冲突）写法：select*fromStudentswhereSID=“2021310721”forupdate例：抢票时，读取剩余票数并将剩余票数减1，需要加互斥锁防止剩余票数被其他事务修改采用当前读，读取最新的数据项，并对这些数据项加互斥锁对于普通的select语句采用快照读，而且不加锁117多版本两阶段锁协议数据库系统—并发控制示例：版本计数器初始值为0

R_TSW_TS00

00

R_TSW_TS00

R_TSW_TS001122

118数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较多版本时间戳排序协议多版本两阶段锁协议多版本乐观并发控制协议版本存储版本删除多版本机制中的索引管理多版本机制的实际应用目录119多版本乐观并发控制协议数据库系统—并发控制将多版本的思想与乐观并发控制机制结合可串行化调度恢复性事务时间戳：BeginTS：开始执行时得到的时间戳CommitTS：提交时得到的时间戳数据项版本的时间戳：begin-ts：起始时间戳end-ts：终止时间戳协议三阶段：读阶段、验证阶段、写阶段120多版本乐观并发控制协议数据库系统—并发控制读阶段：记录事务读取的数据项（读集）、写入的数据项（写集）和多次进行的扫描（扫描集）完成事务中的数据操作，获得一个结束时间戳验证阶段：在结束时间戳时刻，验证读集中数据项的版本是否仍然可见，避免脏读、不可重复读问题重新执行扫描集，检查结果是否相同，避免幻读问题验证通过后，获得CommitTS进行下一阶段，否则撤销并重启121多版本乐观并发控制协议数据库系统—并发控制写阶段：创建写集中数据项的新版本，该版本的begin-ts为该事务的CommitTS，将新版本写回数据库删除写集中数据项的有效的旧版本，即使旧版本的end-ts为该事务的CommitTS写写冲突：如果多个事务在同一数据项上进行更新操作，那么第一个获得写入权限的事务进行更新，其他事务被撤销并重启122多版本乐观并发控制协议数据库系统—并发控制

数据项begin-tsend-ts000数据项begin-tsend-ts04400

123数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较多版本时间戳排序协议多版本两阶段锁协议多版本乐观并发控制协议版本存储版本删除多版本机制中的索引管理多版本机制的实际应用目录124版本存储数据库系统—并发控制每个逻辑行拥有版本链表，存储若干个版本不同存储策略：存储位置仅追加存储回滚段存储存储方式差异存储全纪录存储

125版本存储位置数据库系统—并发控制仅追加存储所有版本存储在一个表空间中，插入版本链表中组织版本链表的两种顺序：从旧到新：新版本追加到链表尾部；查找新版本时需要遍历链表。索引指针始终指向第一个版本，不需要更新索引指针从新到旧：新版本插入链表头部，同时更新索引指针；查找新版本时不需要遍历链表缺点：将多版本信息存储在原数据空间中，数据一直增长。淘汰老版本数据时，需要遍历数据，造成性能不平稳126版本存储位置数据库系统—并发控制回滚段存储将老版本信息移动到一个单独的空间存储，最新版本存储在原数据空间索引始终指向逻辑行地址每个逻辑行有一个指针指向其回滚段表空间，该回滚段表空间存储若干个旧版本产生新版本时，将旧版本复制到回滚段表空间，同时将最新版本存储在当前空间中127版本存储方式数据库系统—并发控制差异存储一条记录可能包含多个属性，一次数据更新可能只修改一小部分属性。上述两种策略需要将所有属性的数据存在老版本中，造成了空间浪费差异存储在产生新版本时，将数据项修改的部分内容存储到差异存储表中，同时更新主表减少写操作时的数据复制量，提高系统的写性能读旧版本数据时，通过差异内容得到，降低读性能128数据库系统—并发控制01并发控制概览02悲观并发控制技术03乐观并发控制技术04多版本机制05并发控制协议比较多版本时间戳排序协议多版本两阶段锁协议多版本乐观并发控制协议版本存储版本删除多版本机制中的索引管理多版本机制的实际应用目录129版本删除数据库系统—并发控制

130版本删除数据库系统—并发控制垃圾回收的两种方案：行级别回收：针对行直接进行垃圾回收后台回收：后台定期查找可回收的版本，适用于所有版本储存策略合作回收：在遍历版本链表时找过期的版本数据并删除，只可用于从旧到新的版本储存策略事务级别回收：每个事务记录