回顾本课程的路线图：
在前面的课程中介绍了 DBMS 的主要模块及架构，自底向上依次是 Disk Manager、Buffer Pool Manager、Access Methods、Operator Execution 及 Query Planning。但数据库要解决的问题并不仅仅停留在功能的实现上，它还需要具备：
- 满足多个用户同时读写数据，即
Concurrency Control。? 两个用户同时写入同一条记录 - 面对故障，如宕机，能恢复到之前的状态，即
Recovery。? 你在银行系统转账时，转到一半忽然停电
Concurrency Control 与 Recovery 都是 DBMSs 的重要特性，它们渗透在 DBMS 的每个主要模块中。而二者的基础都是具备 ACID 特性的 Transactions，因此本节的讨论从 Transactions 开始。
1 Transactions
transaction 是在数据库上执行一个或多个操作 (例如 SQL 查询) 的序列，是 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 利用率、吞吐量，减少用户的响应时间。但要利用 CPU 的多核计算能力，这难度也是显而易见的，获得种种好处的同时必须保证数据库的正确性和 transactions 之间的公平性。 显然我们无法让 transactions 的执行过程在时间线上任意重叠，因为这可能导致数据的永久不一致。于是我们需要一套标准来定义数据的正确性。
2 Definitions
Database: 一组固定的数据对象 (e.g., A, B, C, ...)
Transaction: 一序列读写操作 (e.g., R(A), W(B), ...)
事务的结果是 COMMIT 或 ABORT。
- 若是 COMMIT，事务的所有修改都被保存到数据库中。
- 若是 ABORT，事务的所有修改都会被撤销，就像从未发生过一样。Abort 可以是自己造成的，也可以是由DBMS造成的。
transaction 的正确性标准称为 ACID：
- 原子性（Atomicity）：事务中的所有动作都发生，或者不发生。
- 一致性（Consistency）: 如果每个事务是一致的，DB开始时也是一致的，那么它结束时也是一致的。
- 隔离性（Isolation）: 一个事务的执行与其他事务的执行是隔离的。
- 持久性（Durability）:如果一个事务被
commit，则它的效果将保持不变。
实际上各家数据库所实现的ACID并不尽相同。例如围绕着“隔离性”就存在很多含糊不清的争议。所以当听到一个系统声称自己“兼容ACID”时，其实你无法确信它究竟能提供了什么样的保证，现在的ACID更像是一个市场营销用语。
3 ACID: Atomicity
DBMS 要保证事务的原子性，事务的所有操作要么都被执行，要么都未被执行。
原子性 需要保证在出错时中止事务，并将部分完成的写入全部丟弃。需要注意的是，这里的原子性并不关心多个操作的并发性，它并没有描述多个线程试图访问相同的数据会发生什么情况，后者其实是由 ACID 的隔离性所定义。
保证原子性的两种方法：
Shadow Paging：事务执行前，DBMS 会复制相关的 page，然后让事务修改这些复制的数据。当事务被 Commit 后，这些 page 才对外部可见。- 现代系统中采用该方式的不多 (CouchDB, LMDB)。
Logging：DBMS 在 log 中按顺序记录所有 actions 信息，然后 undo 所有 aborted transactions 中已经执行的 actions，- 出于审计和效率的原因，几乎所有现代系统都使用这种方式。
4 ACID: Consistency
一致性是指系统从一个正确的状态（当前的状态满足预定的约束），迁移到另一个正确的状态。
? A 要向 B 支付 100 元，但是 A 的账户中只有 90 元。如果我们给账户余额这一列的约束是不能小于 0，那么很明显这条事务执行会失败。在这个例子中，支付之前我们数据库里的数据都是符合约束的，但是如果事务执行成功了，我们的数据库数据就破坏约束了。因此这里事务不能成功，也就是说事务提供了一致性的保证。? 再比如说，A 要向 B 支付 100 元，而 A 的账户中只有 90 元。我们的账户余额列没有任何约束，但是我们业务上不允许账户余额小于 0。因此我们的事务会执行成功，但之后我们会检查 A 的账户余额，发现余额小于 0 了，于是我们就会进行事务的回滚。这个例子中，我们的事务会执行成功，因为它没有破坏数据库的约束。但是它破坏了我们应用层的约束，不过事务的回滚保证了我们的应用层约束不被破坏，因此也可以说事务提供了一致性保证。
原子性，隔离性和持久性是数据库自身的属性，而 ACID 中的一致性更多是应用层的属性。应用程序可能借助数据库提供的原子性和隔离性，以达到一致性，但一致性本身并不源于数据库。因此，字母 C 其实并不应该属于 ACID (Joe Hellerstein 曾经在文献中评论，字母 C 只是为了使 ACID 这个缩略词听起来更为顺口，当时并非觉得这是件很重要的事情。)
5 ACID: Isolation
经典的数据库教材把隔离定义为可串行化，这意味着可以假装它是数据库上运行的唯一事务 (虽然实际上它们可能同时运行)，但数据库系统要确保当事务提交时，其结果与串行执行 (一个接一个执行) 完全相同。为了达到这个效果，DBMS需要限制数据的访问顺序 (并发调度)。
然而实践中，很多时候我们并不需要这么高的隔离性，同时为了更好的性能可以容忍某些问题的存在。因此SQL引入了多种隔离级别以供应用者选择。
隔离性意味着并发执行的多个事务相互隔离，互不影响。
但对 DBMS 来说，为提高各方面性能，需要恰如其分地向不同的事务分配计算资源，使得执行又快又正确。—— 并发控制
并发控制协议：DBMS 如何认定多个事务的重叠执行方式是正确的 (不破坏数据库的一致性)。总体上看，有两种并发控制协议：
- Pessimistic：不让问题出现，将问题扼杀在摇篮之中
- Optimistic：假设问题很罕见，一旦问题出现了再行处理
我们希望并发事务执行的最终状态，和在单线程中按照顺序执行这些事务所得到的结果相同。
? 假设 A, B 账户各有 1000 元，有以下两个 transactions，T1、T2 发生后，可能的合理结果应该是怎样的？
-- T1: 从 A 账户转账 100 元到 B 账户 --
BEGIN
A = A - 100
B = B + 100
COMMIT
-- T2: 给 A、B 账户存款增加 6% 的利息 --
BEGIN
A = A * 1.06
B = B * 1.06
COMMIT
尽管有很多种可能，但 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
当一个事务在等待资源 (page fault、disk/network I/O) 时，或当 CPU 存在其它空闲的 Core 时，其它事务可以继续执行，因此我们需要将事务的执行重叠 (interleave) 起来。
DBMS 执行操作的顺序被称为 执行调度 (execution schedule)。我们想通过重叠执行事务来最大程度地提高并发性，同时保证输出的正确性。并发控制协议的目标是产生一个相当于串行执行 (serial execution) 的执行调度，也就是可串行化调度 (Serializable Schedule):：
- 串行调度 (Serial Schedule): schedule 中的不同事务间没有重叠。(并没有并发)
- 等价调度 (Equivalent Schedule): 对于任意数据库起始状态，若两个 schedules 分别执行所到达的数据库最终状态相同，则称这两个 schedules 等价。
- 可串行化调度 (Serializable Schedule): schedule 与事务之间的某种串行执行 schedule 的效果一致。(不同串行执行可能会有不同的结果，但都是正确的)
5.1 Conflict
如果两个操作是针对不同的事务，它们在同一个对象上执行，并且至少有一个是写操作的，那么这两个操作之间就会发生 冲突。我们通过检测是否存在冲突，来检查 schedule 是否正确。冲突有三种类型：
- 读写冲突 (不可重复读)：一个事务在多次读取同一对象时无法获得相同的值。
- 写读冲突 (脏读)：一个事务在一个不同的事务提交其更改之前就看到了该事务的写入效果。
- 写写冲突(丢失更新)： 一个事务覆盖了另一个并发事务的未提交的数据。
5.2 Serializability
可串行化 (serializability) 有两种不同的级别：
冲突可串行化(Conflict Serializability)，是多数 DBMS 支持的SERIALIZABLE隔离级别视图可串行化(View Serializability)，没有 DBMS 能做到
Conflict Serializability
- 冲突等价：两个 schedules 在 transactions 中有相同的 actions，且每组 conflicting actions 按照相同顺序排列。
- 若一个 schedule S 与某个串行执行计划是冲突等价的，则称 S 是冲突可串行化的。
- 如果通过交换不同 transactions 中连续的 non-conflicting operations 可以将 S 转化成串行执行计划，则称 S 是冲突可串行化的
上文所述的交换法在检测两个 transactions 构成的 schedule 很容易，但要检测多个 transactions 构成的 schedule 是否 serializable 则显得别扭。有没有更快的算法来完成这个工作？—— 依赖图 (dependence graphs)
- 每个事务表示一个节点
- 若事务 \(T_i\) 和 \(T_j\) 存在冲突操作 \(O_i\) 和 \(O_j\)，\(O_i\) 早于 \(O_j\) 发生则添加 \(T_i\) 指向 \(T_j\) 的箭头
如果一个 schedule 的依赖图是无环的，则它是冲突可串行化的。
View Serializability
视图可串行化是较弱的可串行化级别，允许所有冲突可串行化的 schedules 和 “盲写 (blind writes)” 即在不先读值的情况下进行写入。因此它比冲突可串行化允许更多的 schedules，但难以有效执行。
若符合以下条件则认为 schedule \(S_1\) 与 schedule \(S_2\) 是视图等价的：
- \(T_1\) 读了 \(S_1\) 中 A 的值，\(T_1\) 也读了 \(S_2\) 中 A 的值
- \(T_1\) 读了 \(S_1\) 中被 \(T_2\) 写入的 A 的值，\(T_1\) 也读了 \(S_2\) 中被 \(T_2\) 写入的 A 的值
- \(T_1\) 写了 \(S_1\) 中 A 的终值，\(T_1\) 也写了 \(S_2\) 中 A 的终值
View Serializability 比 Conflict Serializability 允许更多的 schedules，但难以有效执行。
View Serializability 和 Conflict Serializability 都无法允许我们认为可串行化的所有 schedules。因为它们不理解操作或数据的实际含义。为了允许更多的并发性，一些特殊情况可在应用程序级别单独处理。
Universe of Schedules：\(SerialSchedules ⊂ ConflictSerializableSchedules ⊂ V iewSerializableSchedules ⊂ AllSchedules\)
6 ACID: Durability
隔离性表示：已提交事务的所有更改都应该是持久的。
- 没有进行一半的更新。
- 失败的 transaction 不会导致任何变化。
DBMS 可以使用 logging 或 shadow paging 来确保所有更改都是持久的。
数据库系统本质上是提供一个安全可靠的地方来存储数据而不用担心数据丢失等。持久性就是这样的承诺，它保证一旦事务提交成功，即使存在硬件故障或数据库崩溃，事务所写入的任何数据也不会消失。
对于单节点数据库，持久性通常意味着数据已被写入非易失性存储设备。在写入执行过程中，通常还涉及预写日志等，这样万一磁盘数据损坏可以进行恢复。
而对于支持远程复制的数据库，持久性则意味着数据已成功复制到多个节点。为了实现持久性的保证，数据库必须等到这些写入或复制完成之后才能报告事务成功提交。不过实际上其实并不存在完美的持久性。例如，所有的硬盘和所有的备份如果都同时被人为销毁了，那么数据库也无能为力。
- Concurrency Lecture Control Theory 15concurrency lecture control theory multi-version concurrency lecture control concurrency lecture control index concurrency timestamp ordering lecture multi-version concurrency control version concurrency control project数据库 concurrency题目project control theory concurrency bzm-concurrency