并发控制协议

并发控制协议是调度并发事务的方法——包括加锁、时间戳排序、乐观验证和多版本——以使结果等同于串行执行。

Definition

并发控制协议是一套规则集，用于管理并发事务如何获取数据访问权限，以使每个允许的调度都是可串行化的（或满足所选的较弱隔离级别），从而在不强制事务逐个运行的情况下保持隔离性。

Scope

本主题涵盖了在并发下强制实现可串行性的协议：两阶段锁及其严格变体，包括死锁检测和预防；时间戳排序协议；具有读-验证-写阶段的乐观并发控制；以及多版本并发控制，包括快照隔离。它阐述了每种协议如何保证正确的调度，以及阻塞、中止和吞吐量之间的权衡。它不包括可串行性本身的定义以及补充并发控制的恢复机制。

Core questions

• 两阶段锁如何保证可串行化调度？
• 如何检测、预防或解决死锁？
• 时间戳排序和乐观协议与加锁有何不同？
• 多版本并发控制如何让读取者避免阻塞写入者？
• 悲观和乐观方法在吞吐量方面有哪些权衡？

Key concepts

• 两阶段锁
• 严格和强两阶段锁
• 共享锁和排他锁
• 死锁检测与预防
• 时间戳排序
• 乐观并发控制
• 多版本并发控制
• 快照隔离

Key theories

两阶段锁

如果每个事务在释放任何锁之前获取所有锁（一个增长阶段后跟一个收缩阶段），则所有生成的调度都是冲突可串行化的；严格两阶段锁还会将写锁保持到提交，以确保可恢复性。

乐观并发控制

事务在没有加锁的情况下执行，并在提交时根据并发事务进行验证；冲突事务会被中止并重试，这在争用较低时表现良好。

多版本并发控制

通过保留每个数据项的多个版本，系统允许读取访问一致的快照而不会阻塞写入；快照隔离是一种广泛使用的多版本方案，尽管它可能允许某些不可串行化的异常。

Clinical relevance

并发控制协议决定了数据库在负载下的行为：加锁虽然健壮但可能导致死锁和争用，乐观和多版本方法能够实现高读取并发性，协议选择直接影响高流量事务系统的吞吐量和延迟。

History

两阶段锁和谓词锁由Eswaran及其同事于1976年在System R中形式化；Kung和Robinson于1981年引入了乐观并发控制；Bernstein、Hadzilacos和Goodman于1987年的专著统一了该理论。多版本方法和快照隔离后来因其对读取友好的行为而在广泛使用的数据库系统中占据主导地位。

Debates

快照隔离与可串行性

快照隔离通过让读取者看到一致的快照来提供高并发性，但它允许写偏斜等完整可串行性所禁止的异常；实践者们争论其较弱的保证何时可以接受，以及何时需要可串行化变体。

Key figures

• Jim Gray
• Philip Bernstein
• H. T. Kung

Seminal works

• eswaran1976
• kung1981
• bernstein1987

Frequently asked questions

什么导致死锁以及如何处理？

当两个或多个事务各自持有所需的锁，导致都无法继续时，就会发生死锁。系统通过检测（构建等待图，发现循环，并中止一个受害者事务）或通过预防方案（排序锁的获取或使用时间戳来决定哪个事务等待或中止）来处理死锁。

什么时候乐观并发控制是好的选择？

当冲突很少时，乐观方法表现出色，因为事务在没有加锁开销的情况下运行，并且只有偶尔会验证失败并重试。在高争用下，它们会因中止和重试而浪费工作，因此对于写密集、易冲突的工作负载，通常更倾向于悲观加锁或多版本方法。