并发控制概览

进行一个控制级别的复习

并发：在同一时间间隔内有多个事件或者活动发生。

隔离级别 脏读 不可重复读 幻读
读未提交 允许 允许 允许
读已提交 不允许 允许 允许
可重复读 不允许 不允许 允许
可串行化 不允许 不允许 不允许

解决冲突的思想

  • 悲观并发控制技术：事前控制，避免冲突发生 两阶段锁 基于图的协议
  • 乐观并发控制技术：事后控制，冲突发生后再处理 时间戳排序协议 乐观并发控制协议

悲观并发控制技术

悲观并发控制技术

锁

概念：数据的访问权限，只有持有锁才可访问数据项。

共享锁（shared lock S锁）

多个事务可以在一个数据项上加多个共享锁

加锁事务只能读取不能修改

互斥锁（exclusive lock X锁）

对于一个数据项，只有一个事务可以加互斥锁，其他事务共享锁盒互斥锁都不能加

加锁事务事务可以修改可以读取

使用方式

事务访问数据项前先加锁

  • 只读取：申请共享锁
  • 要读写：申请互斥锁

授予锁的条件

  • 数据项没锁，允许加锁
  • 数据项被加锁，根据锁的相容性处理（相容可授，反之不行）

释放锁的状态

  • 执行期间显式地释放锁
  • 在终止时释放锁，包括事务撤销和完成提交。

锁饿死现象

例子：一个事务想要互斥锁，但其他事务连续接力共享锁，则一直无法获得

解决方法：同时考虑相容性和事务到来顺序，先来先得。

锁数据结构

锁表：对应了数据项和若干个锁信息项（锁信息项用链表连在一起）

锁信息项：锁的类型和请求的事务

普通锁不能解决可串行化调度问题

可串行化调度要求事务的并发执行顺序能够等价于某一串行执行的顺序。

但普通锁机制主要在于处理对于多个读写问题之间的合理调度，导致读写不会出现问题，但事务之间的顺序，并不能保证。

对于事务A：R(A) W(A) R(B) W(B)

在普通锁眼里，相当于两个事务，这不能保证事务的原子性。

两阶段锁

两阶段锁指的是对于锁的获取和释放一共分为两阶段：扩展和收缩

意思就是事务对锁的处理数量可以分成两块连续的部分，第一块部分是获取锁，第二块部分是释放锁。

此时，这个事务就有一体的性质。

两阶段锁能解决可串行化调度问题

在非严格两阶段锁认为，收缩阶段可以提前释放锁。

但可能不可恢复：（脏读）

可恢复的调度：

若事务T读取过事务T′修改后的数据，那么事务T只能在事务T′提交后再提交

不可恢复调度产生的问题：

级联回滚，一个事务的回滚引发若干关联事务的回滚

由于一个事务的某个锁如果提前释放，其他事务使用了这个脏读数据项，并提交。此时第一个事务并没有完成，T1如果回滚，就会导致T2读取的数据项是无效的。这是不可恢复的。

避免不可恢复：

为了避免这种不可恢复的情况，数据库系统通常采用严格两阶段锁协议（Strict 2PL）或强制两阶段锁协议（Rigorous 2PL）：

  • 在严格两阶段锁协议中，事务在提交或回滚之前不会释放排他锁，这样其他事务无法读取未提交的数据，保证了可恢复性。
  • 强制两阶段锁协议进一步要求，事务在提交或回滚之前不会释放任何类型的锁（不仅仅是排他锁，甚至共享锁也不能释放），从而提供更强的隔离性。

S2PL相比SS2PL可以提前释放共享锁，得到更高的读并发效率

数据库系统一般采用S2PL

  • 保证可串行化调度
  • 保证可恢复调度，无级联回滚
  • 提前释放共享锁，提升并发性能

隔离级别

  • 给数据表加锁

避免脏写、脏读、不可重复读、幻读问题，实现了可串行化调度，会使事务等待锁的时间很长，影响并发度

  • 给数据项（记录、属性值、索引key）加锁

避免脏写、脏读、不可重复读问题，不能避免幻读 为了解决幻读问题，实现可串行化调度，可以使用多粒度锁和意向锁。基本思想是加谓词锁，即对查询的范围加锁，不允许其他并发事务在查询范围内添加、删除数据

死锁

事务彼此都持有锁又同时在等待对方释放所需要的锁，不能继续执行并因此陷入了持续的等待状态。

死锁预防

在协议设计上保证数据库不会进入死锁状态

建立事务时间戳，保证我们能知道事务的先后顺序

两种协议：

  • Wait-Die 等待死亡（只能旧事务等待新事务）
  • Wound-Wait 伤害等待（只能新事务等待旧事物）

具体行为：

有事务T1和事务T2，T2更新

Wait-Die（等待-死亡）协议：

  • 若事务T2持有锁，T1申请加锁时，T1会等待。
  • 若事务T1持有锁，T2申请加锁时，T2会被撤销并重启。重启后，T2的时间戳保持为原始值。

Wound-Wait：（反过来）

  • 若事务T1持有锁，T2申请加锁时，T2会等待。
  • 若事务T2持有锁，T1申请加锁时，T1会被撤销并重启。重启后，T1的时间戳保持为原始值。

死锁检测与恢复

允许死锁的发生，但能够及时地意识到死锁的发生并进行处理

使用一个图（等待图 wait-for graph WFG）

当事务Ti等待Tj，则添加一条i 到 j的有向边。

每隔一段时间去找环，如果有环则代表有死锁。

处理方法：

选择一个牺牲的事务，撤销一个

选择依据：

  • 事务开始运行的时间戳
  • 事务已经执行的SQL语句数量
  • 事务已经加锁的数据项的数量

注意回滚程度：全部回滚/部分回滚

避免事务饿死。

锁超时重启

设置事务最长等待时间

  • 如果申请加锁的事务在该时间结束时仍未获得锁，即事务超时，那么此时将该事务回滚并重启
  • 当事务之间确实存在死锁时，该方法会让死锁中的一个或者多个事务回滚并重启，而其他事务继续执行，解决了死锁问题

适用场景

  • 事务执行时间都比较短
  • 事务长时间的等待大多都是死锁造成的

问题：难以合理设置等待时间

基于图的锁协议

要求：

  • 避免死锁
  • 冲突可串行化调度
  • 数据项按照某种偏序关系构成有向无环图

偏序关系指：当A指向BC，必须要先到B再到C 或者 先到C再到B。

树形协议

将数据项进行层级处理，处理成数据项树形图。

  • Ti可以对任何数据项进行第一次加锁
  • 之后如果Ti要对数据项X加锁，需要拥有X父节点数据项的锁
  • Ti可以释放任意持有的锁，释放后不能再加锁

优点：

  • 冲突可串行化且不产生死锁
  • 较早释放锁，减少等待时间增加并发度

缺点

  • 不能保证可恢复性、可能存在级联回滚 （事务结束前不允许释放互斥锁可解决）
  • 事务可能会给不需要访问的数据项也加上锁
  • 数据项的访问顺序难以事先知晓
  • 事先不知道需要加锁的数据项时，需对根节点加锁，降低并发度

锁的粒度

数据项的粒度：

属性，元组，页面，表，整个数据库

锁的粒度：

就像上面的层级关系，就是根据粒度进行上锁。

粒度越大，数据项越小，管理锁的开销越小，冲突越大并发越低。

粒度越小，开销越大，并发度越大。

多粒度锁

多粒度锁是一种锁机制，用于在并发控制中提供更细粒度的锁定能力，以提高系统的并发性和效率

  • 数据库中的所有对象按照大小的不同构成了一棵多粒度树
  • 多粒度树中的每一个节点可以独立地加锁
  • 对某个节点加锁表示对该节点的后代节点加同类型的锁

两种加锁状态

  • 显式锁：该数据项被直接加上的锁（直接检查）
  • 隐式锁：没有被直接加锁，由于祖先加锁变为加锁状态（检查祖先锁）

意向锁

意向锁是一种锁机制，对多粒度树中任一节点加锁时，需要先对其所有祖先点加意向锁。

意向锁的目的是在检测锁兼容的时候可以少一些判断：如果这个节点没有意向锁，那么它下面的数据都没有锁。

行为：

  • 如果要对某个数据项加共享锁，就要对所有祖先节点加意向共享锁（IS锁）
  • 如果要对某个数据项加互斥锁，就要对所有祖先节点加意向互斥锁（IX锁）
  • 共享意向互斥锁，记为SIX锁，表示共享锁+IX锁。对某数据项加SIX锁，表示在对该数据项显式加共享锁的同时加IX锁。

检查行为：

  • 检查自身数据项锁是否相容
  • 检查祖先节点锁是否相容
  • 不需要检查后代节点

兼容关系：

锁类型 共享锁 互斥锁 意向共享锁 意向互斥锁 共享意向互斥锁
共享锁 相容 不相容 相容 不相容 不相容
互斥锁 不相容 不相容 不相容 不相容 不相容
意向共享锁 相容 不相容 相容 相容 相容
意向互斥锁 不相容 不相容 相容 相容 不相容
共享意向互斥锁 不相容 不相容 相容 不相容 不相容

以上两种锁，在粒度低的时候可能会出现幻读。

为了避免幻读，通常需要采用更高的事务隔离级别或者其他锁定机制：

如谓词锁，索引区间锁。

谓词锁

谓词锁（Predicate Lock）是一种锁定机制，用于在数据库系统中锁定满足特定条件的所有对象，而不仅仅是某一具体的数据行或表。这种锁机制对于防止幻读尤其有效。例如Sage > 17的谓词锁作用于所有满足该条件的元组。

行为：

  • 如果事务 A 想读取满足某谓词的对象，必须获取相应的谓词锁。如果此时事务 B 持有满足该谓词的某对象的互斥锁，事务 A 需要等待事务 B 释放该锁才能继续查询。
  • 当事务 A 提交或回滚时，会释放所有持有的谓词锁。若事务 A 想插入、更新或删除对象，则需要检查这些对象的旧值和新值是否与现有的谓词锁匹配。如果匹配，事务 A 需等待这些谓词锁释放后才能继续执行。

谓词锁导致较大的加锁和锁检查开销，影响系统性能。

索引区间锁

  • 如果谓词包含的属性上有索引，则给该索引加锁。
  • 本质是扩大谓词锁锁住的范围，减少锁的数量。

例如：

事务T根据谓词Sage > 17 AND Sno > 2021310722做范围查询。 Sno属性上有索引。可以使用索引区间锁锁住 Sno > 2021310722的元组。

性能分析：

  • 在执行插入、更新或删除操作时，事务需要更新索引，并检查索引区间锁，因此索引区间锁的检查与更新同步，开销较小。
  • 然而，索引区间锁会扩大锁的范围，导致更多的锁冲突和等待。
  • 这是一个折衷的方法。

适用性：

  • 对于某些事务，如果谓词中的属性没有索引，则无法使用索引区间锁，此时可以对整个表进行锁定。

闩锁

与并发控制的锁无关，和事不相关。

在更底层，负责保证写入的时候，只有一个线程对同一内存数据块进行写操作。

它使用CAS指令，这些指令都是原子操作，原子性由CPU保证。

输入参数：

  • 内存中数据（V）：表示要操作的内存地址（或数据），即需要进行比较和更新的共享变量。
  • 已记录的旧值（E）：表示线程期望该内存地址的当前值。这个值通常是在执行操作之前读取的。
  • 新值（N）：表示当内存中的数据与旧值匹配时要写入的新值。

自旋锁

多线程环境中，获得共享资源的访问权限。

未获得锁的线程将在保持CPU占用的状态下，一直循环等待，即通过自旋（自我循环，不释放CPU资源）的方式来获得锁。

悲观并发控制技术缺点

  • 锁的开销大
  • 有死锁情况，解决死锁
  • 回滚开销大
  • 很多场景高并发低竞争，浪费太多锁资源。