数据库的并发控制与恢复机制：为什么要有？解决什么场景的问题？

在数据库管理系统（DBMS）的设计中， 并发控制（Concurrency Control）和恢复（Recovery）机制是核心且无处不在的组件 。它们贯穿整个数据库架构，是构建一个能够正确运行事务并确保数据安全的数据库系统的最后两个关键环节。

为什么需要它们？

核心原因在于，现代数据库系统需要支持 多用户并发访问和操作数据 ，同时还要 应对可能发生的系统故障 。如果缺乏这些机制，将会出现严重的数据不一致和数据丢失问题。

并发操作导致的竞态条件（Race Condition）和数据不一致：

• 场景示例： 两个线程同时尝试更新同一条记录。例如，A和B各拥有1000美元，事务T1从A转100美元到B，同时事务T2给所有账户增加6%的利息。
• 问题： 如果操作随意交错，可能会导致“ 丢失更新 (Lost Updates) ”。例如，T1取走了A的100美元，但T2在T1将钱存入B之前计算了利息，可能导致最终账户总额不正确，银行凭空“丢失”了钱。
• 目标： 确保即使操作交错，最终结果也等同于事务按某种串行顺序执行的结果。

系统故障导致的数据丢失和不完整：

• 场景示例： 您从您的银行账户转账100美元到另一个账户，但在钱完全转入之前，数据中心遭遇雷击，机器崩溃或断电。
• 问题： 当系统恢复时，数据库应该处于什么状态？钱是还在您的账户里，还是已经到了对方账户，抑或是凭空消失了？ 不完整事务导致的永久性不一致 是我们需要极力避免的。
• 目标： 确保一旦事务被提交并得到确认，即使发生系统故障，其所有更改也必须是 持久（Durable） 的，不会丢失。

由于这些机制的复杂性，应用程序开发者通常不应该尝试在应用层自行实现它们，因为这很容易出错，导致数据丢失或不正确。相反，应该 依赖高质量的数据库系统软件来处理这些关键功能 。

事务是什么？

事务（Transaction） 是数据库管理系统中的 “逻辑工作单元” 。它是一系列对数据库的操作（例如，SQL查询，包括读写操作），共同完成某个 更高层级的功能 。

数据操作逻辑上的包：

• 事务是DBMS中 “改变的基本单位” 。这意味着一个事务内的所有操作要么全部发生并被保存，要么全部不发生，即 不允许部分事务存在 。
• 示例： 经典的银行转账例子——从账户A取100美元并存入账户B。这在高层级上是一个“转账”操作，但在数据库内部，它分解为多个低层操作：检查余额 -> 从A扣钱 -> 向B加钱。如果中间任何一步失败（如断电），则整个转账操作都应被撤销，就像从未发生过一样。

SQL中的事务操作 ，即在SQL标准中，事务通过特定的关键字来管理：

• BEGIN：显式地开始一个新的事务。
• COMMIT：尝试提交事务。如果用户调用了COMMIT，DBMS会尝试保存所有更改并返回成功确认。但 即使应用调用了COMMIT，数据库系统也可能因为冲突等原因拒绝提交并将其终止（abort） 。
• ABORT（或 ROLLBACK）：终止事务。如果事务被终止，自BEGIN以来所做的所有更改都将被撤销，数据库恢复到事务开始前的状态，就好像事务从未运行过一样。

ACID 代表什么？

ACID 是数据库事务正确性的四个基本属性的缩写，是保证数据库事务可靠性的核心概念。

A (Atomicity) - 原子性： "All or Nothing" (要么全做，要么全不做)

定义：事务中的所有操作要么作为一个整体全部成功执行并持久化到数据库中，要么全部不执行，不存在中间状态。

保障机制：

• 主流手段：日志记录（Logging），特别是预写日志（Write-Ahead Logging / WAL）

原理： DBMS会记录所有对数据库的更改，包括被覆盖的旧值（称为“undo records”）。这些记录保存在内存和磁盘上。如果事务中止或系统崩溃，DBMS可以使用这些记录将数据库回滚到事务开始前的状态，从而保证原子性。

比喻： 类似于飞机上的黑匣子，记录了所有操作，以便在发生故障时回溯和恢复。

额外好处： 日志不仅用于恢复，还能提高性能（通过将随机写入转换为顺序写入），并提供 审计追踪（Audit Trail） ，记录了应用的所有操作，对金融等需要合规审计的行业至关重要。

WAL要点： 为了保证数据持久，必须先将日志记录写入磁盘，才能将对应的数据页写入磁盘（“先写日志，后写数据”）。

• 另一种方法：影子分页（Shadow Paging）

原理： 事务不是直接修改原始数据库文件，而是操作数据库文件或单个页面的副本（“影子副本”）。只有当事务成功提交时，DBMS才会将指向新副本的指针“翻转”，使其成为新的主版本。

缺点： 这种方法非常慢且管理复杂，容易导致磁盘碎片和数据无序，因此 今天很少有系统使用 （仅CouchDB和LMDB等少数系统采用）。与多版本并发控制（MVCC）有相似之处，但MVCC通常在更细粒度（如元组）上进行复制。

C (Consistency) - 一致性： "It looks correct to me..." (看起来是对的)

定义：如果数据库在事务开始前处于一致状态（例如，满足所有预定义的完整性约束），且事务本身是“一致的”（即它是一个正确的程序），那么当事务完成时，数据库也必须保持一致状态。

理解： 数据库的一致性是指它 准确地反映了真实世界 ，并遵循预设的 完整性约束 。

两个层面：

• 数据库一致性： 由DBMS通过 完整性约束（Integrity Constraints） 来保证（例如，年龄不能小于0；外键引用必须存在）。DBMS会阻止违反这些约束的操作。此外，它还保证未来执行的事务能看到过去已提交事务所做的 正确更改 。这在分布式数据库中更为重要（强一致性 vs 最终一致性）。
• 事务一致性：这更多是应用层的责任 。DBMS无法理解应用程序的 高层级业务逻辑 或 人类的价值判断 。例如，如果应用程序规定“修读这门课的学生不能拥有某个账户”，但数据库无法访问学生是否选课的信息，那么即使该操作在业务逻辑上不一致，DBMS也无法阻止它。因此，事务本身的“正确性”和“一致性”由应用程序开发者负责，DBMS只能保证其原子性、隔离性和持久性。

I (Isolation) - 隔离性： "As if Alone" (如同单独运行)

定义：并发执行的事务之间互不干扰，每个事务都感觉自己是系统中唯一运行的事务， 即使其他事务同时在运行，它也应该看不到这些中间的、未提交的更改 。

重要性： 隔离性为应用程序提供了一个 更简单的编程模型 。开发者无需担心其他并发事务的临时数据，可以像编写单线程代码一样编写事务逻辑。

挑战： 尽管隔离的理想是串行执行，但为了最大化硬件利用率、提高吞吐量和响应时间，DBMS必须 交错执行 多个并发事务的操作。如何在交错操作的同时，依然维持“如同单独运行”的错觉，这是 并发控制协议（Concurrency Control Protocol） 需要解决的核心问题，也是 ACID中最具挑战性的部分 。

区分锁（Locks）和闩锁（Latches）：

• 闩锁（Latches）： 保护数据库内部数据结构（如索引树、哈希表）的正确性，用于同步对内存数据结构的访问。
• 锁（Locks）： 保护数据库对象（如元组、页面、表）的正确性，用于保证事务的隔离性。锁是流量警察，决定哪些操作可以进行，哪些必须等待或中止。

D (Durability) - 持久性： "Survive Failures" (能够抵御故障)

定义：一旦事务成功提交并收到DBMS的确认，其所有修改都必须 永久地 保存在数据库中，即使发生系统崩溃、断电、操作系统崩溃等任何类型的故障，这些更改也 不会丢失 。

保障机制： 持久性主要通过 日志记录（Logging） 来实现。日志记录保证了即使内存中的数据丢失，磁盘上的日志也能在系统重启时用于恢复数据库到最新提交的状态。影子分页也能提供持久性，但如前所述，其应用有限。

如何确保调度是正确的？让并行事务效果是串行执行的一样

为了在允许多个事务交错执行的同时，仍然保持数据库的正确性，DBMS需要一套形式化的标准来判断一个 调度（Schedule） 是否有效。这个标准就是： 一个交错执行的调度，其最终结果必须等同于这些事务以某种串行顺序（即一个接一个，无交错）执行的结果 。

• 串行调度（Serial Schedule）： 不交错不同事务操作的调度。
• 等价调度（Equivalent Schedules）： 对于任何数据库状态，执行第一个调度的效果与执行第二个调度的效果完全相同。
• 可串行化调度（Serializable Schedule）： 与某个串行执行等价的调度。这是并发控制的 “黄金标准” ，提供了几乎所有能想到的保护。

冲突操作（Conflicting Operations） 是判断调度是否可串行化的关键。当以下三个条件同时满足时，两个操作被认为是冲突的：

1. 它们由 不同 的事务执行。
2. 它们操作 相同的对象 （数据项，如A或B）。
3. 至少其中一个操作是 写操作（Write） 。

（注意：读-读操作（Read-Read）不会冲突，因为它们不会改变数据，也不会互相影响）。

并发执行可能导致的异常（Interleaved Execution Anomalies）：

• 读-写冲突（Read-Write Conflicts / R-W）- 不可重复读（Unrepeatable Reads）： 事务T1读取了数据A，然后事务T2修改了A并提交，接着T1再次读取A时，发现A的值变了。在T1看来，两次读取同一数据得到不同值，这破坏了它“单独运行”的错觉。
• 写-读冲突（Write-Read Conflicts / W-R）- 脏读（Dirty Reads）： 事务T1修改了数据A，但尚未提交。此时事务T2读取了A的这个未提交的新值。如果随后T1因某种原因中止（回滚），那么T2读取到的A是一个从未真实存在过的“脏数据”。
• 写-写冲突（Write-Write Conflicts / W-W）- 覆盖未提交数据/丢失更新（Overwriting Uncommitted Data/Lost Updates）： 事务T1写入数据A，但尚未提交。此时事务T2也写入了数据A（覆盖了T1的写入），并且可能先于T1提交。这导致T1的写入被覆盖而“丢失”，或者出现两个数据项被不同事务“撕裂式”更新的情况。

可串行化两种类型

冲突可串行化（Conflict Serializability）：

定义：如果一个调度可以通过 交换连续的非冲突操作 （来自不同事务的操作且不冲突）来转换为某个串行调度，那么它就是冲突可串行化的。

判断方法：

• 交换法： 如定义所示，通过一系列的非冲突操作交换，尝试将调度重组为串行形式。
• 依赖图（Dependency Graph）/前趋图（Precedence Graph）：

为调度中的每个事务创建一个节点。

如果事务Ti的某个操作与事务Tj的某个操作发生冲突，并且Ti的操作在调度中先于Tj的操作发生，则从Ti到Tj画一条边。

判断准则：如果依赖图是无环的（Acyclic），则该调度是冲突可串行化的；否则，它不是 。

• 实际应用： 冲突可串行化是 大多数DBMS在实际中支持的可串行化级别 （例如，SQL中的SERIALIZABLE隔离级别）。它提供了严格的正确性保证，并且可以高效地实现。

视图可串行化（View Serializability）：

定义：一个更弱、更宽松的可串行化概念。它不仅允许所有冲突可串行化调度，还允许一些包含 盲写（Blind Writes） （即不先读取数据就直接写入）的调度。

判断标准： 两个调度是视图等价的，如果它们满足特定的读写模式一致性（例如，如果事务T1在S1中读取了A的初始值，那么它在S2中也必须读取A的初始值；如果T1在S1中读取了T2写入的A，那么在S2中也必须如此；如果T1在S1中写入了A的最终值，那么在S2中也必须如此）。

实际应用： 视图可串行化虽然理论上允许更大的并发度，但 在实践中很难高效实现 。因为它需要DBMS理解应用程序的 高层级语义和逻辑 （即事务的“意图”），而DBMS通常只能看到低层级的读写操作。因此，它目前 仅停留在理论层面 。

两种并发控制协议思想/方法详细介绍

并发控制协议是DBMS决定如何交错多个事务操作以保证隔离性的核心机制。它们可以大致分为两类：

悲观并发控制（Pessimistic Concurrency Control）

思想：假设事务之间会经常发生冲突 ，因此在问题发生之前就加以预防。

实现方式：要求事务在执行任何操作之前就获取所需的锁 。如果一个事务需要访问某个数据对象，它必须先获得该对象的锁。如果该对象已经被其他事务锁定，当前事务就必须等待。

典型协议：两阶段锁（Two-Phase Locking / 2PL） 。这是最广泛使用的悲观协议之一，将在下一次课程中详细讲解。

• 优点： 能够有效防止并发冲突和异常的发生，保证数据强一致性。
• 缺点：

性能影响： 频繁的锁请求和等待可能导致事务 停滞（stall） ，降低系统并行度，影响整体吞吐量和响应时间。

死锁（Deadlock）： 多个事务相互等待对方释放锁，导致所有事务都无法继续执行。DBMS需要额外的机制来检测和解决死锁。

乐观并发控制（Optimistic Concurrency Control）

思想：假设事务之间的冲突是罕见的 。

实现方式： 允许事务在没有任何显式锁的情况下自由运行。事务在本地进行所有更改。 只有在事务尝试提交时，DBMS才会检查是否存在冲突 。

冲突处理： 如果检测到冲突，发生冲突的事务（通常是后提交的事务）会被 中止（abort）并回滚 ，然后由应用程序 重试 。

典型协议：基于时间戳排序（Timestamp Ordering） 。这个协议在CMU的1980年代被发明，也是下一次课程会涉及的内容。

优点： 在冲突率较低的环境下，可以实现 更高的并发度 和更好的系统吞吐量，因为事务不需要等待锁。

缺点：

• 回滚开销： 如果冲突频繁，事务反复中止和重试的开销会非常大，导致性能下降。
• 饥饿（Starvation）： 某些事务可能因为频繁冲突而始终无法成功提交。