跳转至

Theory

Motivation

  • Lost Update Problem（Concurrency Control）：如何在并行更新数据时避免竞争情况的出现。

  • Durability Problem (Recovery)：如何保证在事故后保证数据状态的正确。

DBMS 的 Concurrency Control 和 Recovery 渗透到其整个架构的设计中。

Transactions

A transaction is the execution of a sequence of one or more operations (e.g., SQL queries) on a shared database to perform some higher-level function.

简单理解事务就是一系列的 sql 操作，这些操作要么全部成功，要不全部失败。最经典的转账例子：A 给 B 转账 100 元，要做以下三件事

  • 检查 A 是否有 100 元

  • A 账户 -100

  • B 账户 +100

三个操作会被封装为一个事务，要么全部成功，要么全部失败。

The Strawman System

处理事务的简单系统是使用单个 Worker 一次执行一个事务。为了执行事务，DBMS 会拷贝整个数据库文件到一个新的文件中，事务修改这个新的文件，如果事务执行成功了，这个新的文件作为新的数据库文件；如果失败了，则丢弃这个文件。

上述这个简单的 Strawman System 的缺点很明显，无法利用多核计算能力并行地执行相互独立的多个 transactions，从而提高 CPU 利用率、吞吐量，减少用户的响应时间。想要实现并行事务执行是困难的，获得种种好处的同时必须保证数据库的正确性和 transactions 之间的公平性。

显然我们无法让 transactions 的执行过程在时间线上任意重叠，因为这可能导致数据的永久不一致。于是我们需要一套标准来定义数据的正确性。

Definitions

从形式上讲，数据库可以表示为一组固定的命名数据对象（A、B、C、...）。这些对象可以是属性、元组、页面、表，甚至是数据库。

我们将讨论的算法适用于任何类型的对象，但所有对象都必须属于同一类型。

事务是对这些对象执行的一系列读写操作（即 R（A）、W （B））。为了简化讨论，此定义假定数据库是固定大小的，因此操作只能是读取和更新，而不能是插入或删除。

在 SQL 中，事务以 BEGIN 命令开始。事务的结果是 COMMIT 或 ABORT。对于 COMMIT，要么将事务的所有修改保存到数据库中，要么 DBMS 覆盖此修改并中止。对于 ABORT，事务的所有更改都将被撤消，因此就像事务从未发生过一样。中止可能是自己造成的，也可能是由 DBMS 引起的。

transaction 的正确性标准被称为 ACID：

  • Atomicity：原子性确保事务中的所有操作都发生，或者没有发生。

  • Consistency：一致性保证数据库在事务开始之前和事务结束之后都处于合法状态。也就是说，所有事务在执行后，数据库必须满足所有的完整性约束。

  • Isolation：隔离意味着当一个事务执行时，它应该有一种与其他事务隔离的错觉。隔离可确保事务的并发执行应具有与事务的串行执行相同的结果数据库状态。

  • Durability：如果事务提交，则其对数据库的影响应持续存在。

Atomicity

DBMS 保证事务是原子的。事务要么执行其所有操作，要么不执行任何操作。有两种方法可以做到这一点：

Logging

DBMS 会记录所有操作的日志，以便它可以在事务中止的情况下撤消这些操作。出于效率原因，几乎所有现代系统都使用日志记录。

Shadow Paging

DBMS 会创建由事务修改的页面的副本，事务会更改这些副本。仅当事务提交时，页面才可见。这种方法在运行时通常比基于日志记录的 DBMS 慢。但是，一个好处是，如果您只是单线程的，则不需要日志记录，因此当事务修改数据库时，对磁盘的写入较少。这也使恢复变得简单，因为您需要做的就是从未提交的事务中删除所有页面。但是，一般来说，更好的运行时性能比更好的恢复性能更可取，因此在实践中很少使用。

Consistency

笼统地说，一致性意味着数据库表示的 “世界” 在逻辑上是正确的。应用程序询问的有关数据的所有问题（即查询）都将返回逻辑正确的结果。一致性有两个概念：

数据库一致性：数据库准确表示它正在建模的真实世界实体，并遵循完整性约束。（例如，一个人的年龄不能不是负数）。此外，将来的事务应该在数据库内看到过去提交的事务的影响。

事务一致性：如果数据库在事务开始前是一致的，那么在事务开始之后也会保持一致。确保事务一致性是应用程序的责任。

Isolation

DBMS 为事务提供了它们在系统中单独运行的错觉。他们看不到并发事务的影响。这相当于交易按顺序执行的系统（即一次执行一个）。但为了实现更好的性能，DBMS 必须在保持隔离错觉的同时，交错并发事务的操作。

Concurrency Control

并发控制协议是 DBMS 在运行时决定来自多个事务的操作的正确交错的方式。并发控制协议分为两类：

  1. 悲观：DBMS 假设交易会发生冲突，因此它不会在第一时间让问题出现。

  2. 乐观：DBMS 假设事务之间的冲突很少见，因此它选择在事务提交后发生冲突时进行处理。

DBMS 执行操作的顺序称为执行计划。我们希望交错事务以最大限度地提高并发性，同时确保输出是 "correct" 的。并发控制协议的目标是生成一个等效于某些串行执行的执行计划，这里明确几个概念：

  • Serial Schedule（串行计划）：不交错不同交易的操作的计划

  • Equivalent Schedules（等价计划）：对于任何数据库状态，如果执行第一个计划的效果与执行第二个计划的效果相同，则两个计划是等效的。

  • Serializable Schedule（可序列化计划）：可序列化计划是等效于的任何串行计划的计划。不同的串行执行可能会产生不同的结果，但都被认为是“正确的”。

如果两个操作针对不同的事务，它们是对同一个对象执行的，并且至少有一个操作是写入操作，则会发生两个操作之间的冲突。冲突有三种变体：

  • Read-Write Conflicts（“Unrepeatable Reads”）：多次读取同一对象时，事务无法获得相同的值。

  • Write-Read Conflicts （“Dirty Reads”）：事务在事务提交其更改之前会看到其他事务的写入效果。

  • Write-Write 冲突（“Lost Updates”）：一个事务覆盖另一个并发事务的未提交数据。

Durability

在崩溃或重启后，提交事务的所有更改都必须是持久的（即持久的）。DBMS 可以使用日志记录或影子分页来确保所有更改都是持久的。这通常要求提交的事务存储在非易失性内存中。