5. Transaction and ACID DB

ACID 准则

在讨论支持并发的文件系统 (包括 482 p4 NFS, DBMS 等) 的时候, 我们往往会提到一个非常核心的准则: ACID 准则.

Atomicity (原子性): 事务是一个不可分割的工作单位, 要么全部完成, 要么全部不做;
Consistency (一致性): 事务的执行必须使数据库从一个一致性状态转变到另一个一致性状态;
Isolation (隔离性): 并发执行的事务彼此之间是隔离的, 一个事务的中间状态对其他事务不可见;
- 两个事务并发的时候不能互相冲突
Durability (持久性): 一旦事务提交, 它对数据库的修改就是永久性的, 即使系统崩溃也不会丢失.
- 更多是从 recovery 恢复角度来讲的, 也就是尽量能在任何崩溃情况下都不丢数据;具体看 [Logging](#Log 日志结构) 章节和 Recovery 章节

并发控制的数据库系统

并发控制与隔离性的基础

事务 (Transaction): 事务是 DBMS 中变化的基本单位;它是在数据库上执行的一系列操作(如 SQL 查询), 以完成某种高级功能;
- 事务的抽象视图是读取和写入操作序列(例如 R(A),W(B),…);
- 事务始于 BEGIN 命令, 止于 COMMIT(保存所有更改)或 ABORT(撤销所有更改, 如同从未执行过);
并发的动机: 允许独立事务并发执行是一种(潜在地)更好的方法;
- 目标是为了减少用户的响应时间和提高资源利用率/吞吐量;
隔离性 (Isolation): 是 ACID 属性之一, 要求事务的执行必须表现得像是单独运行一样(“as if alone”);
- DBMS 通过交错事务的动作(对数据库对象的读/写)来实现并发;
并发的挑战: 操作的任意交错可能导致永久不一致性(这是不好的);
II. 调度的形式化与正确性标准
调度 (Schedule) 的正确性标准: 判断调度的正确性在于它是否等价于某种串行执行;
串行调度 (Serial Schedule): 不交错不同事务动作的调度;
等价调度 (Equivalent Schedules): 对于任何数据库状态, 执行第一个调度的效果与执行第二个调度的效果是相同的;
可串行化调度 (Serializable Schedule): 等价于某些串行执行的调度;
- 如果每个事务都保持一致性, 则每个可串行化调度也保持一致性;
- 可串行化提供了 DBMS 在调度操作时额外的灵活性, 而更大的灵活性意味着更好的并行性;
并发控制协议: 这是 DBMS 决定来自多个事务的操作的正确交错方式的机制;
- 协议分为悲观 (Pessimistic)(事先防止问题)和乐观 (Optimistic)(假设冲突罕见, 事后处理)两类;

冲突与冲突可串行化 Conflict Serializable

冲突操作 (Conflicting Operations): 实现高效等价性的形式化概念依赖于"冲突"操作;
- 两个操作冲突必须满足三个条件: 它们来自不同的事务; 它们作用于同一个对象; 并且其中至少有一个是写入操作;
交错执行异常 (Interleaved Execution Anomalies):
- 读-写冲突 (R-W Conflicts): 例如, 不可重复读 (Unrepeatable Reads);
- 写-读冲突 (W-R Conflicts): 例如, 读取未提交数据(“脏读”, Dirty Reads);
- 写-写冲突 (W-W Conflicts): 例如, 覆盖未提交数据 (Overwriting Uncommitted Data);
冲突等价 (Conflict Equivalent): 两个调度冲突等价, 当且仅当它们涉及相同事务的相同动作, 并且每对冲突动作的排序方式相同;
冲突可串行化 (Conflict Serializability): 调度 S 如果与某个串行调度冲突等价, 则 S 是冲突可串行化的;
- 直观上, 如果可以通过交换不冲突的连续操作将调度 S 转换为串行调度, 则 S 是冲突可串行化的;
- 大多数 DBMS 尝试支持冲突可串行化;

依赖图与视图可串行化 Precedence Graph

前驱图 (Precedence Graph): 用于快速判断冲突可串行化的算法;
- 图中的每个事务是一个节点;
- 判定规则: 一个调度是冲突可串行化的, 当且仅当它的依赖图是无环的 (acyclic);图中的环揭示了问题;
视图可串行化 (View Serializability): 可串行化的另一种(较弱的)概念;
- 视图等价 (View Equivalent): 需满足三个条件: 1. 事务读取的初始值保持不变; 2. 事务读取的由另一个事务写入的值保持不变; 3. 事务写入的最终值保持不变;
- 视图可串行化允许比冲突可串行化略多的调度, 包括"盲写 (blind writes)";
- 实践限制: 视图可串行化难以高效地强制执行;来源指出, 没有 DBMS 可以支持视图可串行化;

二相锁 2 Phase Locking (2PL)

Log 日志结构

恢复 Recovery

Non-Fuzzy Checkpointing

也就是最基本的 checkpointing 机制, 其步骤如下:

暂停所有事务的执行, 确保没有活动事务在进行中;
等待所有正在进行的事务完成;
将所有修改过的数据页从缓冲区写回磁盘, 确保磁盘上的数据是最新的;

Fuzzy Checkpointing

为了让 checkpointing 过程不阻塞系统的正常运行, 在这里我们要用到两个机制来辅助我们:

Active Transaction Table (ATT): 记录所有当前正在运行的事务及其状态;
Dirty Page Table (DPT): 记录所有被修改但尚未写回磁盘的数据页的信息;

ATT

也就是维护每个活跃的 transaction 的活动到一个表中, 主要包含以下字段:

txnID: 事务的唯一标识符;
status: 事务的当前状态 (R: Running, C: Committing, U: Candidate for Undo);
lastLSN: 事务的最后一个日志序列号 (Log Sequence Number);

这些 entry/tuple 会在写入 TXN-END 之后被删除.

DPT

记录所有写过的且没有被刷盘的脏页，recLSN 字段会记录该页第一次被修改时对应的 LSN. 也就是说这个记录了第一个导致这个页变脏的日志位置.

恢复流程

恢复的时候，我们可以通过 log 和 ckpt 获取有限的信息:

(fuzzy) ckpt 会存储最新的 ATT 和 DPT;
在 ckpt 后会有更新的数据被写在 log 中;

我们的目的，是对已经 commit 的所有事务执行 Redo, 对所有没有执行完的事务执行 Undo.
这里的执行流程分成 3 个阶段:

分析 (Analysis Phase)

这个阶段的目标是通过 log 和 ckpt 恢复出最新的 ATT 和 DPT, 以及确定哪些事务需要 redo 和 undo.
可以理解为把 ckpt 的时间点直接推到 crash 发生的时间点.