数据库并发控制：锁粒度与无锁策略

### 数据库并发控制：锁粒度与无锁策略 #### 1. 锁粒度 在数据库系统中，锁粒度是一个重要的概念。部分数据库系统允许程序员覆盖选择锁粒度的默认机制。例如，Microsoft SQL Server 允许用户使用关键字 `PAGLOCK` 选择页级锁而非表级锁；IBM 的 DB2 UDB 支持显式的表级锁。当在某个粒度上获得了一定数量的锁后，系统可能会开始获取更高粒度的锁（例如页级），这一过程被称为锁升级。 #### 2. 无锁并发控制 虽然锁是数据库管理系统（DBMS）中最广泛使用的并发控制方法，但并非唯一的方法。以下将介绍几种替代方法。 ##### 2.1 乐观并发控制 - **基本原理**：乐观并发控制的基本前提是大多数事务之间不会发生冲突，因此尽可能允许事务自由执行。事务执行分为三个阶段： 1. **读取阶段**：事务执行，从数据库读取值并写入私有工作空间。 2. **验证阶段**：如果事务决定提交，DBMS 会检查该事务是否可能与其他并发执行的事务发生冲突。若存在可能的冲突，事务将被中止，其私有工作空间被清空并重新启动。 3. **写入阶段**：如果验证确定没有可能的冲突，事务在私有工作空间中对数据对象所做的更改将被复制到数据库中。 - **性能分析**：如果冲突较少且验证能够高效完成，这种方法的性能应优于基于锁的方法。但如果冲突频繁，重复重启事务会浪费大量工作，显著影响性能。 - **验证条件**：每个事务 `Ti` 在验证阶段开始时会被分配一个时间戳 `TS(Ti)`，验证标准会检查事务的时间戳顺序是否为等效的串行顺序。对于每对事务 `Ti` 和 `Tj`（`TS(Ti) < TS(Tj)`），必须满足以下验证条件之一： 1. `Ti` 在 `Tj` 开始之前完成（所有三个阶段）。 2. `Ti` 在 `Tj` 开始写入阶段之前完成，且 `Ti` 不会写入 `Tj` 读取的任何数据库对象。 3. `Ti` 在 `Tj` 完成读取阶段之前完成其读取阶段，且 `Ti` 不会写入 `Tj` 读取或写入的任何数据库对象。 - **操作步骤**： 1. 为每个事务维护读取和写入的对象列表。 2. 在验证一个事务时，不允许其他事务提交，以避免遗漏冲突。 3. 验证通过的事务的写入阶段必须完成，其效果在私有工作空间外可见后，才能验证其他事务。 4. 可以使用临界区等同步机制确保任何时候最多只有一个事务处于验证/写入阶段。 - **优化冲突解决**：早期的乐观并发控制使用的三个验证条件往往过于保守，会不必要地中止和重启事务。可以使用更细粒度的冲突解决机制，类似于锁机制。具体操作如下： 1. 每个事务在读取阶段告知 DBMS 它正在读取的项目。 2. 当事务 `Ti` 提交时，DBMS 检查 `Ti` 写入的任何项目是否正在被其他（尚未验证）的事务 `Tj` 读取。 3. 可以选择“死亡策略”（允许 `Tj` 在验证时发现冲突）或“杀死策略”（立即杀死并重启 `Tj`）。 - **具体操作细节**： 1. 事务 `T` 在读取数据项之前，在哈希表中输入一个访问条目，包含事务 ID、数据对象 ID 和修改标志（初始设置为 false），条目根据数据对象 ID 进行哈希处理。 2. 获取包含该条目的哈希桶上的临时排他锁，并在将读取的数据项从数据库缓冲区复制到事务的私有工作空间时持有该锁。 3. 在验证 `T` 时，再次以排他模式锁定 `T` 访问的所有数据对象的哈希桶，检查 `T` 是否遇到任何数据冲突。如果访问条目中的修改标志设置为 true，则表示遇到冲突。 4.