锁

在数据库系统中，为了允许多个事务并发执行，同时保证数据库的一致性和隔离性，需要使用并发控制机制。加锁（Locking）是一种常用的并发控制方法，它通过控制事务对数据项的访问权限来协调它们的执行顺序。

主要的锁分类如下：

1. 排他锁（Exclusive Lock, X）

   • 目的： 用于需要修改（写入）数据项的操作。一个事务在对数据项 A 进行写操作之前，必须获得其排他锁 l_X(A)（或简写为 l(A)）[29, 51]。
   • 兼容性： 排他锁是最高级别的锁。当一个事务持有了数据项的排他锁时，任何其他事务都不能再获得该数据项的任何其他类型的锁（包括共享锁或排他锁本身）[31, 54, 55, 79]。排他锁与任何其他锁都不兼容 [55, 79]。

2. 共享锁（Shared Lock, S）

   • 目的： 用于需要读取数据项的操作。一个事务在对数据项 A 进行读操作之前，通常需要获得其共享锁 l_S(A) [49, 51]。
   • 兼容性： 共享锁允许多个事务同时读取同一个数据项。因此，一个事务持有的共享锁与其他事务请求的共享锁是兼容的 [49, 54, 55, 79]。但是，共享锁与排他锁不兼容 [54, 55, 79]。

3. 更新锁（Update Lock, U）

   • 目的： 教材中提到更新锁是为了处理事务先读取数据（可能需要 S 锁），之后再修改数据（需要 X 锁）时可能发生的特定死锁问题 [62, 63]。当事务知道它可能稍后会写数据时，会请求更新锁而不是共享锁 [63]。
   • 兼容性： 根据教材中的兼容矩阵 [64, 65]，更新锁 l_U(A) 的兼容性描述如下（请求者 vs 持有者）：
     • 请求 S 锁：持有 S (T), 持有 X (F), 持有 U (F)
     • 请求 X 锁：持有 S (F), 持有 X (F), 持有 U (F)
     • 请求 U 锁：持有 S (T), 持有 X (F), 持有 U (F) 这表明，一个事务请求 U 锁时，只要数据项上只有 S 锁（由其他事务持有），就可以获得 U 锁 [63]。但一旦某个事务获得了 U 锁，其他任何事务就不能再获得 S, X, 或 U 锁 [64, 65]。U 锁可以升级为 X 锁 [63]。

4. 意向锁（Intention Locks）

   • 背景： 意向锁用于支持多粒度锁定（Multiple Granularity），即数据项被组织成一个层次结构（例如，数据库包含表，表包含页面，页面包含元组）[73, 74]。事务可以在不同粒度的级别上请求锁。为了在粗粒度（如表）和细粒度（如元组）之间协调，引入了意向锁。
   • 目的： 意向锁被设置在层次结构的较高层，用于通知其他事务，有事务打算在层次结构的较低层锁定该节点的一部分 [75]。
   • 分类及兼容性（根据教材兼容矩阵 [78, 79]）：
     • 意向共享锁 (Intention Shared, IS): 表示事务打算在较低级别获得共享锁。IS 锁兼容 IS, IX, S, SIX 锁，但不兼容 X 锁 [79]。
     • 意向排他锁 (Intention Exclusive, IX): 表示事务打算在较低级别获得排他锁。IX 锁兼容 IS, IX 锁，但不兼容 S, SIX, X 锁 [79]。
     • 共享意向排他锁 (Shared Intention Exclusive, SIX): 表示事务在该节点本身需要共享锁，并打算在较低级别获得排他锁。SIX 锁只兼容 IS 锁，不兼容 IX, S, SIX, X 锁 [79]。

5. 增量锁（Increment Lock） [58, 59] 作为一种特殊类型的锁，用于特定的原子增量操作。

这些不同类型的锁以及它们之间的兼容性规则是数据库管理系统实现并发控制（尤其是基于锁的两阶段锁协议）的基础，它们帮助系统在允许多个事务并发执行的同时，维护数据的一致性和隔离性。

这些锁通常用于多粒度锁定（如行级、页级、表级），其中 IS 和 IX 是“意向锁”，表示某个事务打算在更低的粒度上加 S 或 X 锁。

锁的兼容矩阵

共享锁（S）、排他锁（X）和增量锁（I）的兼容矩阵

这个矩阵通常描述在同一数据项上，请求某个锁的事务是否能与当前持有某种锁的事务兼容。

当前持有锁 \ 请求锁	S (共享)	X (排他)	I (增量)
S (共享)	✅	❌	❌
X (排他)	❌	❌	❌
I (增量)	❌	❌	✅

共享锁（S）、排他锁（X）和更新锁（U）的兼容矩阵

这个矩阵通常描述在同一数据项上，请求某个锁的事务是否能与当前持有某种锁的事务兼容。

当前持有锁 \ 请求锁	S (共享)	X (排他)	U (更新)
S (共享)	✅	❌	✅
X (排他)	❌	❌	❌
U (更新)	✅	❌	❌
解释：

• S vs S (✅): 多个事务可以同时持有同一数据项的共享锁，以便并发读取。
• S vs X (❌): 持有共享锁时，不能授予排他锁。
• S vs U (✅): 持有共享锁时，可以授予更新锁（一个事务持有 U 锁，其他事务可以同时持有 S 锁，但不能有其他 U 或 X 锁）。
• X vs 任何锁 (❌): 持有排他锁时，任何其他锁请求都不被允许。
• U vs S (✅): 持有更新锁时，可以授予共享锁。
• U vs X (❌): 持有更新锁时，不能授予排他锁。
• U vs U (❌): 任何时候，只能有一个事务持有同一数据项的更新锁。

意向锁（IS, IX, SIX）、共享锁（S）和排他锁（X）的兼容矩阵

这个矩阵通常描述在多粒度锁定层次结构中，请求某个锁的事务是否能与当前持有某种锁的事务在同一节点上兼容。

当前持有锁 \ 请求锁	IS (意向共享)	IX (意向排他)	S (共享)	SIX (共享意向排他)	X (排他)
IS (意向共享)	✅	✅	✅	✅	❌
IX (意向排他)	✅	✅	❌	❌	❌
S (共享)	✅	❌	✅	❌	❌
SIX (共享意向排他)	✅	❌	❌	❌	❌
X (排他)	❌	❌	❌	❌	❌
解释：

• X vs 任何锁 (❌): 持有排他锁时，任何其他锁请求都不被允许。
• S vs S (✅): 兼容并发读取。
• S vs X (❌): 不兼容读写冲突。
• S vs IS (✅): 持有 S 锁不妨碍其他事务在子节点上设置 IS。
• S vs IX (❌): 持有 S 锁会阻止其他事务在子节点上设置 IX（因为最终会在子节点请求 X 锁）。
• S vs SIX (❌): 持有 S 锁会阻止其他事务在子节点上设置 SIX。
• IX vs IS (✅): 持有 IX 锁不妨碍其他事务在子节点上设置 IS。
• IX vs IX (✅): 多个事务可以在子节点上设置 IX。
• IX vs S, SIX, X (❌): 持有 IX 锁会阻止其他事务在当前节点或其子节点上获取 S, SIX, X 锁。
• IS vs 任何意向锁或 S, SIX (✅): 持有 IS 锁不妨碍其他事务在子节点上获取 IS, IX, S, SIX 锁。
• IS vs X (❌): 持有 IS 锁会阻止其他事务在当前节点获取 X 锁。
• SIX vs IS (✅): 持有 SIX 锁不妨碍其他事务在子节点上设置 IS。
• SIX vs IX, S, SIX, X (❌): 持有 SIX 锁会阻止其他事务在当前节点或子节点上获取 IX, S, SIX, X 锁。

教材中还提到了增量锁 (I) [58, 59]，并指出 INi(A), INj(A) 不冲突，意味着 I 锁与 I 锁是兼容的 [59]。但教材未提供 I 锁与 S, X, U, IS, IX, SIX 锁的兼容性信息，因此无法在此处列出完整的包含 I 锁的兼容矩阵。

指向原始笔记的链接

加锁协议

以下几种加锁协议结合特定的规则来保证调度是冲突可串行化的：

1. 共享锁 (Shared Lock) 和排他锁 (Exclusive Lock) 与两阶段锁协议 (2PL)

   • 协议规则： 这是标准的关系数据库管理系统中最常用的 2PL 版本。
     • 良好形式的事务: 事务 Ti 在读取数据项 A 之前，必须获得 A 的共享锁 l-Si(A)；在写入数据项 A 之前，必须获得 A 的排他锁 l-Xi(A)。所有锁最终都需要释放 [51]。事务如果先读后写同一数据项，可能需要将共享锁升级为排他锁 [53]。
     • 合法的调度器: 调度器必须根据 锁的兼容矩阵 来授予锁 [54, 55]。共享锁 (S) 与其他共享锁 (S) 兼容，但不与排他锁 (X) 兼容。排他锁 (X) 与任何其他锁 (S 或 X) 都不兼容 [55]。只有当事务请求的锁模式与数据项上当前所有已持有的锁模式都兼容时，才能授予锁 [66]。
   • 保证冲突可串行化的机制： 教材中明确指出，遵循 Shared/Exclusive 锁规则和两阶段锁协议的调度，其结果是冲突可串行化的 [56]。证明思路与基本排他锁的 2PL 类似 [57]，核心仍然是 2PL 特性确保了基于锁释放顺序的前趋关系是无环的，从而保证了优先图无环。共享锁的引入提高了并发度（多个事务可以同时读取同一数据项），但冲突的定义和 2PL 保证无环的原理保持不变。

2. 树协议 (Tree Protocol)

   • 协议规则 (教材主要描述排他锁版本): 假设数据库中的数据项组织成一个树形结构。
     • 事务 Ti 获得的第一个锁可以是树中的任何数据项。
     • 之后，事务 Ti 只能锁定节点 Q 当且仅当 Ti 已经持有了 Q 的父节点 parent(Q) 的锁。这意味着加锁操作是沿着树结构向下进行的。
     • 事务可以随时释放锁。注意： 与 2PL 不同，树协议不强制存在一个只释放锁的收缩阶段。
     • 事务释放某个数据项的锁后，不能再次锁定该数据项。
   • 保证冲突可串行化的机制：
     • 教材提出树协议可以保证 冲突可串行化。尽管树协议不遵循 2PL，允许在增长阶段释放锁，但其通过限制加锁的方式（必须先锁父节点才能锁子节点）来防止优先图中出现环。如果事务 Ti 和 Tj 冲突，它们必然在某个共同祖先节点（可能就是冲突数据项 A 本身）上产生了依赖。树协议强制事务从根（或某个入口点）向下加锁，这种结构化的加锁顺序本身就足以防止形成依赖环。
     • 例如，如果 Ti 锁定了 A 之前锁定了 parent(A)，而 Tj 后来也需要锁定 A，Tj 必须等待 Ti 释放 A。如果在 Tj 释放 A 后 Ti 又想锁定 A，它必须重新从根开始向下加锁（或从某个已锁定的祖先节点），但根据规则 4，它不能再次锁定 A。这种规则组合起来，确保了事务之间的冲突依赖不会形成循环。

3. 验证并发控制（Validation concurrency control），也称为乐观并发控制（optimistic concurrency control），是一种用于管理数据库事务并发执行的机制。

   • 它的核心思想是将事务的执行分为三个阶段:
     1. 读阶段 (Read Phase)：事务读取数据库需要的数据，并将所有写操作记录在临时存储中，而不是直接修改数据库。在这个阶段通常不使用锁。
     2. 验证阶段 (Validate Phase)：这是一个原子操作阶段。系统检查当前事务到目前为止的执行是否与已提交事务的调度可串行化。验证的顺序（例如 T1, T2, T3…）决定了最终等价的串行执行顺序。
     3. 写阶段 (Write Phase)：如果验证成功，系统将临时存储中的写操作应用到数据库中。如果验证失败，事务将被中止并回滚。
   • Validation 并发控制的主要优点在于其乐观性，即假设冲突很少发生。它允许事务在读阶段自由地执行，只在验证阶段才检查冲突。这种方法适用于冲突率较低、系统资源充足或有实时性要求的场景 。
   • 它的规则旨在防止并发事务之间的读写冲突，例如一个事务在验证时，会检查它读取的数据是否被在此之前已验证成功的其他事务修改过，或者它修改的数据是否会与之前已验证成功但尚未完成写操作的事务发生冲突。

指向原始笔记的链接