# Concurrency Control Theory

## 引入

回顾本课程的路线图：

![](/files/-LcutSsYRS0RJtIzvL_M)

在前面的课程中介绍了 DBMS 的主要模块及架构，自底向上依次是 Disk Manager、Buffer Pool Manager、Access Methods、Operator Execution 及 Query Planning。但数据库要解决的问题并不仅仅停留在功能的实现上，它还需要具备：

* 满足多个用户同时读写数据，即 Concurrency Control，如：
  * 两个用户同时写入同一条记录
* 面对故障，如宕机，能恢复到之前的状态，即 Recovery，如：
  * 你在银行系统转账时，转到一半忽然停电

Concurrency Control 与 Recovery 都是 DBMSs 的重要特性，它们渗透在 DBMS 的每个主要模块中。而二者的基础都是具备 ACID 特性的 Transactions，因此本节的讨论从 Transactions 开始。

## 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.

用一句白话说，transaction 是 DBMS 状态变化的基本单位，一个 transaction 只能有执行和未执行两个状态，不存在部分执行的状态。

一个典型的 transaction 实例就是：从 A 账户转账 100 元至 B 账户：

* 检查 A 的账户余额是否超过 100 元
* 从 A 账户中扣除 100 元
* 往 B 账户中增加 100 元

### Strawman/Simple System

系统中只存在一个线程负责执行 transaction：

* 任何时刻只能有一个 transaction 被执行且每个 transaction 开始执行就必须执行完毕才轮到下一个
* 在 transaction 启动前，将整个 database 数据复制到新文件中，并在新文件上执行改动
  * 如果 transaction 执行成功，就用新文件覆盖原文件
  * 如果 transaction 执行失败，则删除新文件即可

Strawman System 的缺点很明显，无法利用多核计算能力并行地执行相互独立的多个 transactions，从而提高 CPU 利用率、吞吐量，减少用户的响应时间，但其难度也是显而易见的，获得种种好处的同时必须保证数据库的正确性和 transactions 之间的公平性。\
显然我们无法让 transactions 的执行过程在时间线上任意重叠，因为这可能导致数据的永久不一致。于是我们需要一套标准来定义数据的正确性。

### Formal Definitions

Database: A fixed set of named data objects (e.g., A, B, C, ...)\
Transaction: A sequence of read and write operations (e.g., R(A), W(B), ...)

transaction 的正确性标准称为 ACID：

* Atomicity："all or nothing"
* Consistency: "it looks correct to me"
* Isolation: "as if alone"
* Durability: "survive failures"

### Atomicity

Transaction 执行只有两种结果：

* 在完成所有操作后 Commit
* 在完成部分操作后主动或被动 Abort

DBMS 需要保证 transaction 的原子性，即在使用者的眼里，transaction 的所有操作要么都被执行，要么都未被执行。回到之前的转账问题，如果 A 账户转 100 元到 B 账户的过程中忽然停电，当供电恢复时，A、B 账户的正确状态应当是怎样的？--- 回退到转账前的状态。如何保证？

#### Logging

DBMS 在日志中按顺序记录所有 actions 信息，然后 undo 所有 aborted transactions 已经执行的 actions，出于审计和效率的原因，几乎所有现代系统都使用这种方式。

#### Shadow Paging

transaction 执行前，DBMS 复制相关 pages，让 transactions 修改这些复制的数据，仅当 transaction Commit 后，这些 pages 才对外部可见。现代系统中采用该方式的不多，包括 CouchDB, LMDB。

### Consistency

如果 DBMS 在 transaction 开始之前是 consistent，那么在执行完毕后也应当是 consistent。Transaction consistency 是 DBMS 必须保证的事情。

### Isolation

用户提交 transactions，不同 transactions 执行过程应当互相隔离，互不影响，每个 transaction 都认为只有自己在执行。但对于 DBMS 来说，为了提高各方面性能，需要恰如其分地向不同的 transactions 分配计算资源，使得执行又快又正确。这里的 “恰如其分” 的定义用行话来说，就是 concurrency control protocol，即 DBMS 如何认定多个 transactions 的重叠执行方式是正确的。总体上看，有两种 protocols：

* Pessimistic：不让问题出现，将问题扼杀在摇篮之中
* Optimistic：假设问题很罕见，一旦问题出现了再行处理

举例如下：假设 A, B 账户各有 1000 元，当下有两个 transactions：

* T1：从 A 账户转账 100 元到 B 账户
* T2：给 A、B 账户存款增加 6% 的利息

```sql
// T1
BEGIN
A = A - 100
B = B + 100
COMMIT

BEGIN
A = A * 1.06
B = B * 1.06
COMMIT
```

那么 T1、T2 发生后，可能的合理结果应该是怎样的？

尽管有很多种可能，但 T1、T2 发生后，A + B 的和应为 2000 \* 1.06 = 2120 元。DBMS 无需保证 T1 与 T2 执行的先后顺序，如果二者同时被提交，那么谁先被执行都是有可能的，但执行后的净结果应当与二者按任意顺序分别执行的结果一致，如：

* 先 T1 后 T2：A = 954， B = 1166 => A+B = 2120
* 先 T2 后 T1：A = 960， B = 1160 => A+B = 2120

执行过程如下图所示：

![](/files/-LcvARiJ8r94h05pln1D)

当一个 transaction 在等待资源 (page fault、disk/network I/O) 时，或者当 CPU 存在其它空闲的 Core 时，其它 transaction 可以继续执行，因此我们需要将 transactions 的执行重叠 (interleave) 起来。

Example 1 (Good)

![](/files/-Ld2Z7ms19nsCGVkc6pk)

Example 2 (Bad)

![](/files/-Ld2ZH2NbX1aUNYulZzC)

从 DBMS 的角度分析第二个例子：

* A = A - 100 => R(A), W(A)
* ...

![](/files/-Ld2ZbHnJxKOA4xrREA9)

如何判断一种重叠的 schdule 是正确的？

> If the schedule is equivalent to some serial execution

这里明确几个概念：

* Serial Schedule: 不同 transactions 之间没有重叠
* Equivalent Schedules: 对于任意数据库起始状态，若两个 schedules 分别执行所到达的数据库最终状态相同，则称这两个 schedules 等价
* Serializable Schedule: 如果一个 schedule 与 transactions 之间的某种 serial execution 的效果一致，则称该 schedule 为 serializable schedule

#### Conflicting Operations

在对 schedules 作等价分析前，需要了解 conflicting operations。当两个 operations 满足以下条件时，我们认为它们是 conflicting operations：

* 来自不同的 transactions
* 对同一个对象操作
* 两个 operations 至少有一个是 write 操作

可以穷举出这几种情况：

* Read-Write Conflicts (R-W)
* Write-Read Conflicts (W-R)
* Write-Write Conflicts (W-W)

*Read-Write Conflicts/Unrepeatable Reads*

![](/files/-Ld2bdGLZFHxKn4j5jyu)

*Write-Read Conflicts/Reading Uncommitted Data/Dirty Reads*

![](/files/-Ld2byQOw-SjbrFm58nI)

*Write-Write Conflicts/Overwriting Uncommitted Data*

![](/files/-Ld2c5sHk911dFVCtMqg)

从以上例子可以理解 serializability 对一个 schedule 意味着这个 schedule 是否正确。serializability 有两个不同的级别：

* Conflict Serializability (Most DBMSs try to support this)：
  * 两个 schedules 在 transactions 中有相同的 actions，且每组 conflicting actions 按照相同顺序排列，则称它们为 conflict equivalent
  * 一个 schedule  S 如果与某个 serial schedule 是 conflict equivalent，则称 S 是 conflict serializable
  * 如果通过交换不同 transactions 中连续的 non-conflicting operations 可以将 S 转化成 serial schedule，则称 S 是 conflict serializable
* View Serializability (No DBMS can do this)

例 1：将 conflict serializable schedule S 转化为 serial schedule

![](/files/-LdCgSVEXsultXNNZFLA)

R(B) 与 W(A) 不矛盾，是 non-conflicting operations，可以交换它们

![](/files/-LdCgaTtPUzY__K0-n76)

![](/files/-LdCgfImzjYRRD9Emw86)

R(B) 与 R(A) 是 non-conflicting operations，交换它们

![](/files/-LdCgpJ4EgHsX5Tu0VNh)

依次类推，分别交换 W(B) 与 W(A)，W(B) 与 R(A) 就能得到：

![](/files/-LdChPSq4OxUpbUnFKTH)

因此 S 为 conflict serializable。

例 2：S 无法转化成 serial schedule

![](/files/-LdChnA4mnmOn4_514pc)

由于两个 W(A) 之间是矛盾的，无法交换，因此 S 无法转化成 serial schedule。

*Faster Algorithms To Test Serializability*

上文所述的交换法在检测两个 transactions 构成的 schedule 很容易，但要检测多个 transactions 构成的 schedule 是否 serializable 则显得别扭。有没有更快的算法来完成这个工作？


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/cmu-15-445-645-database-systems/concurrency-control-theory.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.