Lecture13第十一章并发控制

Lecture13·第十一章并发控制数据库系统概论·事务管理与并发调度核心技术Contents课程目录第十一章·并发控制01并发控制概述02封锁机制03封锁协议04活锁与死锁05并发调度的可串行性06两段锁协议与多粒度封锁CHAPTER01并发控制概述理解事务并发操作带来的数据不一致性问题及其控制必要性CHAPTER11·LECTURE13并发控制的基本概念并发控制是DBMS的核心功能之一，其本质是在多事务并发存取数据库时，通过调度机制保证事务的隔离性和一致性，防止因并发操作导致数据不一致。事务是并发控制的基本单位，封锁机制是最主要的并发控制技术。数据库服务器机房—并发控制的物理运行环境01事务调度：事务是并发控制的基本单位，DBMS需要对并发操作进行正确调度以保证事务的ACID特性02隔离性保障：保证事务隔离性（Isolation），防止多事务同时操作同一数据时产生数据不一致03技术路径：主流并发控制技术包括封锁、时间戳、乐观控制法和多版本并发控制（MVCC）04封锁机制：数据库系统中最经典、应用最广泛的并发控制方法，通过加锁实现对数据对象的访问控制ConcurrencyControl·并发异常丢失修改（LostUpdate）丢失修改是并发操作中最典型的数据不一致性问题：两个事务T1和T2同时读入同一数据并分别修改，T2的提交结果破坏了T1的提交结果，导致T1的修改被覆盖丢失，数据库最终状态不能反映所有已完成事务的全部修改。01场景—甲售票点T1和乙售票点T2同时读出某航班机票余额A=16，两个事务各自卖出一张票后分别将A修改为15写回02过程—T1执行A←A-1得到15并写回，T2同样执行A←A-1得到15并写回，T2的写回覆盖了T1的结果03后果—实际卖出两张机票，但数据库中余额仅减少1，T1对数据的修改被T2的修改完全覆盖，造成数据不一致04本质原因—两个事务在同一数据上的写-写冲突未被控制，后提交的事务覆盖了先提交事务的修改结果T₁（甲售票点）T₂（乙售票点）读A=16同时读A=16A←A-1=15各自A←A-1=15写回A=15先后写回A=15RESULTA=15卖出2张，余额仅减1→应为A=14CONCURRENTANOMALIES不可重复读与读脏数据不可重复读和读脏数据是并发操作破坏事务隔离性的两种重要表现形式。不可重复读导致同一事务内两次读取结果不同，破坏了数据的一致性视图；读脏数据则使事务读取到未提交且最终被回滚的临时数据，基于错误数据做出决策。不可重复读（Non-repeatableRead）01事务T1读取数据B=100后，T2修改B=200并写回，T1重读B发现值已改变，无法再现前一次读取结果02不可重复读还包括幻读现象：T1按条件查询后，T2插入或删除数据行，T1再查发现数据集合发生变化读脏数据（DirtyRead）01事务T1将C修改为200并写回，T2读取到C=200，但T1随后被撤销、C恢复原值100，T2读到的即为"脏"数据02脏数据的本质：T2读取了T1未最终提交的临时修改，该修改被回滚后T2的数据视图与数据库实际状态不一致CHAPTER02封锁机制掌握排它锁与共享锁的概念、特性及锁相容矩阵CONCURRENCYCONTROL·LOCKS封锁的概念与基本类型封锁是事务在操作数据对象前向系统申请的控制权限，通过加锁机制实现对并发访问的限制。两种基本封锁类型——排它锁（X锁/写锁）和共享锁（S锁/读锁）——分别对应写操作和读操作的并发控制需求，二者在权限范围和互斥程度上存在本质差异。排它锁（X锁/写锁）事务T对数据对象A加X锁后，只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁X锁保证在T释放A上的锁之前，其他事务既不能读取也不能修改A，实现对写操作的完全独占控制Exclusive独占控制共享锁（S锁/读锁）事务T对数据对象A加S锁后，T可以读A但不能修改A，其他事务只能再对A加S锁，不能加X锁S锁允许多个事务同时读取同一数据对象，但阻止任何事务在S锁存在期间对该对象进行写操作Shared并发读取ConcurrencyControl锁相容矩阵锁相容矩阵定义了不同封锁类型之间的共存规则：X锁与任何锁都不相容，体现写操作的完全独占性；S锁之间相互相容，支持多事务并发读取；S锁与X锁不相容，防止读写冲突。锁相容矩阵（T1已持有vsT2请求）T1已持有的锁T2请求X锁T2请求S锁T2不加锁X锁N（不相容）N（不相容）Y（相容）S锁N（不相容）Y（相容）Y（相容）无锁（—）Y（相容）Y（相容）Y（相容）X锁完全独占，与任何锁不相容；S锁之间相容但排斥X锁；无锁状态允许任意加锁请求N不相容Y相容Chapter03封锁协议三级封锁协议如何逐级解决丢失修改、读脏数据和不可重复读问题LOCKINGPROTOCOL·LEVEL1一级封锁协议一级封锁协议要求事务在修改数据前必须加X锁直到事务结束，通过写-写互斥防止丢失修改，但无法防止读脏数据和不可重复读。01核心规则事务T在修改数据R之前必须先对其加X锁，且该X锁直到事务结束（提交或回滚）才释放X锁持有至事务结束02防止丢失修改X锁之间互不相容，杜绝了两个事务同时修改同一数据的写-写冲突写-写互斥03不能防止读脏数据读操作不需要加锁，事务可以读取到其他事务已修改但尚未提交的临时数据读操作不加锁04不能防止不可重复读两次读取之间其他事务可以修改数据并提交，导致前后读取结果不一致读取结果不一致CONCURRENCYCONTROL·L2PROTOCOL二级封锁协议二级封锁协议在一级基础上增加了"读前加S锁、读完即释放"的规则，通过在读取瞬间阻止其他事务的写操作来防止读脏数据。但S锁的短暂持有意味着同一事务后续重读时数据可能已被修改，不可重复读问题仍然存在。核心规则在一级封锁协议基础上，事务T在读数据R前必须先加S锁，读完后即可释放S锁。S锁（共享锁）允许多个事务同时读取同一数据，但阻止任何事务加X锁进行修改。S-Lock防止读脏数据S锁与X锁不相容，读取期间其他事务无法加X锁修改数据，有效阻止脏读。当事务读取正在被其他事务修改的数据时，S锁机制确保只能看到已提交的版本。NoDirtyRead不可重复读未解S锁读完即释放，其他事务可加X锁修改数据，T重读时可能得到不同结果。这种"不可重复读"现象意味着同一事务内两次读取同一数据可能返回不一致的值。Non-Repeatable协议层级提升从仅保护写操作扩展到保护读操作的瞬间一致性，并发控制保障级别提高。二级协议在并发度与一致性之间取得平衡，是构建更高级封锁协议的重要基础。LevelUpChapter11·ConcurrencyControl三级封锁协议与对比总结三级封锁协议要求读操作前加S锁并持续到事务结束，通过在整个事务生命周期内阻止其他事务对被读数据的写操作，从根本上解决了不可重复读问题。三级协议层层递进，保障级别逐级提升，代价是对并发度的限制也越来越严格。三级封锁协议对比协议级别写操作规则读操作规则防丢失修改防读脏数据防不可重复读一级修改前加X锁，事务结束释放不加锁✓✗✗二级修改前加X锁，事务结束释放读前加S锁，读完释放✓✓✗三级修改前加X锁，事务结束释放读前加S锁，事务结束释放✓✓✓三级封锁协议逐级增强保护能力：一级防丢失修改，二级增加防读脏数据，三级进一步防不可重复读CHAPTER04活锁与死锁封锁机制的副作用及其预防、诊断与解除策略ConcurrencyControl·LockManagement活锁（Livelock）活锁是指事务虽然没有被阻塞或死锁，但由于不断被其他事务抢占资源而永远无法获得所需锁，始终处于等待状态。活锁的本质是资源调度不公平，通过先来先服务（FCFS）的排队策略即可有效解决。01现象描述事务T1请求对数据A加X锁，但由于不断有新事务对A请求S锁并获得批准，T1始终无法获得X锁，永远处于等待状态。StarvationPattern02本质原因锁请求的调度策略不公平——新到达的S锁请求因为与已有S锁相容而总是被优先满足，导致排队的X锁请求持续被"插队"。UnfairScheduling03解决方案采用先来先服务（FCFS）策略，按请求到达时间排队，保证每个事务最终都能获得所需的锁，从根本上消除调度不公平。FCFSQueue04与死锁的区别活锁中事务并未被其他事务循环等待所阻塞，而是因为调度不公平导致持续被"插队"；死锁则是事务间的循环等待依赖。Livelock≠DeadlockConcurrencyControl死锁（Deadlock）死锁是两个或多个事务互相等待对方释放锁而形成的循环等待僵局，所有涉及的事务都无法继续执行。死锁是封锁机制的固有副作用，与活锁不同，死锁中的事务确实被阻塞了，且仅靠调度策略无法自行解决，必须由系统主动干预。01经典场景T1持有A的X锁并请求B的X锁，T2持有B的X锁并请求A的X锁，形成T1→T2→T1的循环等待T1→T2→T102必要条件互斥条件、占有并等待、不可剥夺、循环等待——四个条件同时满足时死锁必然发生4Conditions03与活锁的本质区别死锁是事务之间形成了循环依赖链，仅靠排队策略无法解决，必须由系统主动检测并干预CircularDependency04应对策略三个层面：死锁预防（避免发生）、死锁诊断（检测存在）、死锁解除（打破状态）Prevent·Detect·ResolveConcurrencyControl·并发控制死锁的预防方法死锁预防通过破坏死锁产生的必要条件来避免死锁发生，主要有一次封锁法和顺序封锁法两种策略。但两种方法都因实际限制而难以完美应用：一次封锁法难以预知全部数据且降低并发度，顺序封锁法维护成本高且难以适应数据动态变化。因此大多数DBMS采用诊断+解除的策略而非预防。一次封锁法要求每个事务必须一次性对所有将要使用的数据全部加锁，否则不继续执行，消除了"占有并等待"条件Limit事务执行前难以准确预知需要访问的全部数据，且一次性大量加锁严重降低系统并发度破坏条件占有并等待顺序封锁法预先对所有数据对象规定一个全局加锁顺序，所有事务严格按此顺序申请锁，消除循环等待条件Limit数据库中数据对象庞大且动态变化，维护全局顺序成本极高，实际系统中难以实现破坏条件循环等待CONCURRENCYCONTROL死锁的诊断与解除大多数DBMS采用"诊断+解除"而非预防的策略应对死锁。超时法简单但可能误判，等待图法通过检测有向图中的回路精确识别死锁。一旦检测到死锁，系统选择处理代价最小的事务进行撤销回滚，释放其持有的所有锁以打破循环等待，使其他事务恢复执行。超时法事务等待时间超过阈值即判定为死锁，实现简单但存在误判风险和检测延迟问题阈值判定等待图法系统维护事务等待有向图，定期检测图中是否存在回路，回路存在则确认死锁发生回路检测牺牲者选择选择处理代价最小（已执行工作量最少）的事务作为牺牲者进行撤销回滚最小代价锁释放恢复被撤销事务释放其持有的所有锁，打破循环等待链，其余事务得以继续正常运行打破循环Chapter05并发调度的可串行性判断并发事务调度正确性的理论准则——可串行化与冲突可串行化第十一章·并发控制可串行化调度可串行化调度是并发事务正确性的唯一准则：多个事务并发执行的结果，如果与按某一次序串行执行的结果相同，则称该调度为可串行化调度。串行执行保证了事务之间的完全隔离，因此可串行化的并发调度也被认为是正确的。定义多个事务并发执行是正确的，当且仅当其结果与按某一次序串行执行的结果相同，称为可串行化调度。可串行化核心意义可串行性是并发事务正确调度的准则，只有可串行化的调度才能保证数据库的一致性状态。一致性串行正确性串行执行时每个事务独占数据库资源，事务之间互不干扰，天然保证隔离性和一致性。完全隔离并发权衡完全串行保证正确性但并发度最低，DBMS需在保证可串行性的前提下尽可能提高并发度。并发度CONCURRENCYCONTROL冲突可串行化调度冲突可串行化是可串行化的充分条件（非必要条件），通过交换相邻不冲突操作可将并发调度转化为串行调度。READ-WRITE冲突操作定义不同事务对同一数据的读-写和写-写操作称为冲突操作，读-读操作和不同数据上的操作不冲突。冲突操作不能随意交换次序，这是判定可串行化的核心依据。SWAPADJACENT判定方法保证冲突操作次序不变，若通过交换相邻不冲突操作能将并发调度转化为串行调度，则为冲突可串行化。这是实际系统中常用的判定策略。SUFFICIENT与可串行化的关系冲突可串行化是可串行化的充分非必要条件，冲突可串行化一定可串行化，反之不成立。存在可串行化但非冲突可串行化的调度实例。DBMSTHEORY实际意义冲突可串行化的判定比可串行化更易实现，是DBMS并发控制机制设计的主要理论依据，广泛应用于两阶段锁等经典算法。CHAPTER06两段锁协议与多粒度封锁保证可串行化调度的实用协议与灵活的封锁粒度管理机制Lecture13·并发控制两段锁协议（Two-PhaseLocking）两段锁协议要求事务分为扩展阶段和收缩阶段两个连续阶段操作锁，是可串行化调度的充分条件，但不是必要条件，且仍可能发生死锁。01扩展阶段事务可以申请获得任何数据项上的任何类型锁，但不能释放任何已持有的锁。GrowingPhase02收缩阶段事务可以释放已获得的锁，但不能申请任何新锁，加锁和解锁严格分两阶段执行。ShrinkingPhase03充分条件性质所有事务遵守两段锁协议时，并发调度一定是可串行化的，但该条件不是必要的。充分非必要04死锁风险遵守两段锁协议的事务仍可能发生死锁，因为多个事务在扩展阶段仍可能形成循环等待。DeadlockRiskConcurrencyControl·LockGranularity封锁的粒度封锁粒度选择面临并发度与系统开销的权衡：大粒度管理开销小但并发度低，小粒度并发度高但开销大。多粒度封锁允许事务按需灵活选择。LARGEGRANULARITY大粒度封锁（如锁表）系统管理开销小、加锁解锁效率高，但并发度低，大量事务可能因等待而阻塞。低并发·低开销SMALLGRANULARITY小粒度封锁（如锁行）并发度高、事务冲突概率小，但系统需管理大量锁对象，内存和管理开销显著增加。高并发·高开销MULTI-GRANULARITY多粒度灵活选择支持数据库、表、页、行等多种粒度共存，事务根据操作范围（单行修改vs全表扫描）灵活选择。DB→Table→Page→RowINTENTIONLOCK意向锁协调机制引入意向锁高效协调不同粒度锁之间的相容性判断，避免逐级检查子节点的高昂开销。相容性判断ConcurrencyControl·Locking意向锁（IntentionLock）意向锁是多粒度封锁中协调不同粒度锁相容性的关键机制，通过在上级节点标记加锁意图，使系统无需逐级检查所有子节点即可快速判断相容性，极大降低了管理开销。01·三种意向锁类型IS意向共享锁表示事务意图在该节点的某些后代节点上加S锁，用于标记共享读操作意图IX意向排它锁表示事务意图在该节点的某些后代节点上加X锁，用于标记排它写操作意图02·意向锁的作用机制自顶向下加锁协议事务对子节点加锁前，先对所有祖先节点加意向锁，系统在判断相容性时只需检查直接父节点的锁状态SIX共享+意向排它对当前节点加S锁的同时标记将在后代节点加X锁，支持读全表但修改部分行的场景Lecture13·第