数据库管理系统并发控制：锁定和基于时间戳的协议
菲奥娜·布朗
什么是并发控制？
并发控制 数据库管理系统中的并行处理程序用于管理并发操作，避免它们之间相互冲突。它确保数据库事务能够并发且准确地执行，从而产生正确的结果，同时又不破坏相应数据库的数据完整性。
如果所有用户都只是读取数据，那么并发访问就很容易实现，因为他们之间不会互相干扰。然而，任何实际的数据库都同时包含读取和写入操作，因此并发就成了一个挑战。
数据库管理系统（DBMS）的并发控制用于解决此类冲突，这些冲突大多发生在多用户系统中。因此，并发控制是数据库正常运行的关键要素之一，尤其是在两个或多个事务同时执行并需要访问相同数据的情况下。它与……协同工作。 交易管理它定义了并发控制必须安全交错执行的工作单元。
并发的潜在问题
如果没有适当的数据库管理系统并发控制，您可能会遇到以下一些问题：
- 丢失更新 当多个事务选择同一行并根据所选值更新该行时，就会发生这种情况。
- 未提交的依赖项 （脏读）是指第二个事务选择了一个已被另一个尚未提交的事务更新的行。
- 不可重复读 当第二个事务多次访问同一行并每次读取不同的数据时，就会发生这种情况。
- 摘要错误 当一个事务对重复数据项的所有实例的值进行汇总，而另一个事务更新其中的几个实例时，就会发生这种情况。最终的汇总结果无法反映正确的结果。
为什么要使用并发方法？
在数据库管理系统中使用并发控制方法的原因：
- 通过相互排斥的方式隔离冲突的交易。
- 解决读写冲突和写写冲突问题。
- 通过不断强制执行执行约束来保持数据库一致性。
- 为了控制并发事务之间的交互，可以使用并发控制方案来实现。
- 为了确保可串行化。
例如：
假设两个人同时到电子售票亭购买同一部电影、同一场次的电影票。
然而，剧院里那场电影只剩最后一个座位了。如果没有并发控制，两位观众都有可能买到票。并发控制会阻止这种情况发生。两位观众仍然可以访问电影座位数据库中的信息，但并发控制只会将票发放给第一个完成交易流程的购票者。
并发控制协议
不同的并发控制协议在允许的并发量和带来的开销之间提供了不同的权衡。数据库管理系统中的主要并发控制技术包括：
- 基于锁的协议
- 两阶段锁定协议
- 基于时间戳的协议
- 基于验证的协议
下面将依次对每种协议进行考察，首先考察使用最广泛的基于锁的协议。
基于锁的协议
基于锁的协议 在数据库管理系统中，有一种机制规定，事务必须先获取相应的锁才能读取或写入数据项。基于锁的协议通过将特定数据项锁定或隔离到单个事务中，有助于消除并发问题。
锁是与数据项关联的数据变量，它指示可以对其执行哪些操作。锁有助于并发事务同步对数据库项的访问。所有锁请求都向并发控制管理器发出，事务只有在锁请求获得批准后才能继续执行。
二进制锁： 对数据项的二进制锁可以处于锁定状态或未锁定状态。
共享/独家： 这种锁定机制根据锁的用途对其进行分类。如果获取锁是为了执行写操作，则称为排他锁。
1、共享锁（S）： 共享锁也称为只读锁。使用共享锁，数据项可以在事务之间共享，因为任何事务都没有更新该数据的权限。例如，如果两个事务都在读取某人的账户余额， 数据库 通过设置共享锁，它们可以读取余额。如果另一个交易想要更新该余额，共享锁会阻止该操作，直到读取完成。
2.排他锁（X）： 使用独占锁，数据项既可以读取也可以写入。它是排他性的，不能同时对同一数据项持有多个锁。使用 lock-x 指令请求独占锁。例如，当一个事务需要更新账户余额时，可以通过放置独占锁来允许该事务进行操作；这样，第二个想要读取或写入该数据的事务就会被阻止。
3. 简易锁定协议： 这样，事务可以在开始操作之前获取每个对象的锁。事务可以在写入操作完成后解锁数据项。
4. 预先锁定： 该协议评估操作并创建开始执行所需的数据项列表。当所有锁都被授予后，事务执行；事务完成后，所有锁将被释放。
饥饿： 饥饿是指事务无限期地等待获取锁的情况。其原因包括锁定项的等待机制管理不善、资源泄漏，或者同一事务反复被选为受害者。
僵局： 死锁是指两个或多个进程互相等待对方释放资源，形成循环链的情况。
两相锁定（2PL）协议
此 两阶段锁定协议也称为 2PL，是一种并发控制方法，它通过对事务数据应用锁来确保可串行化，从而阻止其他事务同时访问相同的数据。
两阶段锁定协议允许每笔交易分两步发出锁定或解锁请求：
- 生长期： 在此阶段，交易可能会获得锁，但可能不会释放任何锁。
- 收缩阶段： 在此阶段，交易可能会释放锁，但可能不会获得任何新锁。
2PL确实提供了可串行化特性。然而，它并不能保证不会发生死锁。在上图中，局部和全局死锁检测器会查找死锁，并通过将事务恢复到初始状态来解决死锁。
严格两阶段锁定方法
严格2PL与2PL几乎相同。唯一的区别在于，严格2PL在使用锁后不会释放它。它会一直持有所有锁直到提交点，并在进程结束时一次性释放所有锁。
集中式 2PL
在集中式 2PL 模式下，单个站点负责锁管理流程。整个数据库管理系统只有一个锁管理器。
主副本 2PL
在主副本双向锁机制中，多个锁管理器分布在不同的站点，每个锁管理器负责管理一组数据项的锁。当主副本更新时，更改会传播到从副本。
分布式 2PL
在这种机制中，锁管理器分布在所有站点，负责管理该站点的数据锁。如果没有数据复制，则等效于主副本2PL。分布式2PL的通信成本远高于主副本2PL。
基于时间戳的协议
此 基于时间戳的协议 在数据库管理系统中，时间戳算法使用系统时间或逻辑计数器作为时间戳来串行化并发事务的执行。它确保所有冲突的读写操作都按照时间戳顺序执行。
在这种方法中，较早的事务始终优先执行。它使用系统时间来确定事务的时间戳，是最常用的并发协议。基于锁的协议在冲突事务执行时管理它们的顺序；而基于时间戳的协议则在操作创建之初就处理冲突。
计费示例：
Suppose there are three transactions T1, T2, and T3. T1 has entered the system at time 0010 T2 has entered the system at 0020 T3 has entered the system at 0030 Priority will be given to transaction T1, then T2 and lastly T3.
优点：
- 调度程序是可序列化的，就像 2PL 协议一样。
- 无需等待交易完成，从而消除了死锁的可能性。
缺点： 如果同一事务不断重启和中止，则可能发生饥饿现象。
基于验证的方案
此 基于验证的方案 在数据库管理系统（DBMS）中，乐观并发控制（也称为积极并发控制技术）是一种避免事务并发冲突的方法。该协议更新的是事务数据的本地副本，而不是数据本身，从而减少了执行过程中的干扰。
基于验证的方案分三个阶段执行：
- 读取阶段
- 验证阶段
- 写入阶段
读取阶段
在读取阶段，事务可以读取数据值，但写入操作或更新仅应用于本地数据副本，而不是实际数据库。
验证阶段
在验证阶段，检查数据以确保应用更新不会违反可序列化性。
写入阶段
在写入阶段，如果验证成功，则将更新应用到数据库；否则，将丢弃更新并回滚事务。
并发控制协议比较
这四种协议族对事务实际发生冲突的频率有不同的预期。下表总结了每种协议族的适用范围。
| 协议 | 途径 | 僵局 | 最佳时间 |
|---|---|---|---|
| 基于锁定的 | 悲观主义者，访问前会锁定 | 可能存在 | 冲突频发 |
| 两相锁定 | 悲观、增长和萎缩阶段 | 可能存在 | 需要可串行化 |
| 基于时间戳 | 按时间戳排序 | 无死锁 | 排序很重要，等待代价高昂。 |
| 基于验证的 | 乐观，写之前先验证 | 无死锁 | 冲突很少发生 |
简而言之，基于锁的协议和 2PL 协议假定冲突很常见，并预先防止冲突发生；而时间戳协议和验证协议假定冲突很少见，并且仅在冲突出现时才解决冲突。
优秀并发协议的特征
理想的并发控制机制应具备以下目标：
- 它必须能够应对站点和通信故障。
- 它允许并行执行事务以实现最大的并发性。
- 其存储机制和计算方法应该适度，以尽量减少开销。
- 它必须对事务的原子操作结构施加一些限制。
