Concurrency Control Theory

引入

回顾本课程的路线图:

在前面的课程中介绍了 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% 的利息

// 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

执行过程如下图所示:

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

Example 1 (Good)

Example 2 (Bad)

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

  • A = A - 100 => R(A), W(A)

  • ...

如何判断一种重叠的 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

Write-Read Conflicts/Reading Uncommitted Data/Dirty Reads

Write-Write Conflicts/Overwriting Uncommitted Data

从以上例子可以理解 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

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

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

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

因此 S 为 conflict serializable。

例 2:S 无法转化成 serial schedule

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

Faster Algorithms To Test Serializability

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