整理数据库事务概念的笔记
教材1上给出“事务”的定义为：访问并可能更新各种数据项的一个程序执行单元。另外这里也给出一个更好理解的事务定义：A transaction is the execution of a sequence of one or more operations (e.g., SQL queries) on a database to perform some higher-level function.
事务需要具备 ACID 性质：
- 原子性（Atomicity）：一个事务中的操作要么在数据库中全部反映，要么全部不反映（All or None Law）
- 一致性（Consistency）:隔离执行事务时保持数据库的一致性。（教材原文，果然我还是读不懂）
- 隔离性（Isolation）：对于并发执行的事务，执行的结果都要与某种串行调度相等，即事务 A 在执行时，它不能看到其他事务执行中的数据，要么看到的是其他事务执行前的数据，要么是执行后的结果。
- 持久性（Durability）：事务完成后，它对数据库的修改必须是永久的。
如何保证原子性
可通过以下两种方式来实现事务的原子性：
- 日志记录（Logging）。在一项写操作应用到数据库之前，先把该记录的旧值和新值以及修改位置记录到日志里，如果事务 abort 或者因故障没有完成提交，则通过日志将该记录恢复到写入之前的状态；
- 影子分页（Shadow Paging）。对于事务将要修改的页面，先在日志中拷贝一份进行修改，当事务提交之后才将这些修改的页面写入数据库文件。如果事务 abort 则直接丢弃这些 page；若事务因故障而未完成，则这些 page 自然不会出现在数据库中。
如何保证一致性
// TODO：DBMS cannot control this.
如何保证隔离性
通过并发访问控制机制实现，目前大约有以下几种：
- 基于锁的悲观并发控制，如两阶段锁协议：每个事务由增长阶段和缩减阶段构成，增长阶段只允许申请锁，缩减阶段只允许释放锁。
基于锁的并发控制需要处理出现死锁的情况；- 死锁预防：可以允许事务抢占锁、可以为所有锁规定一个获取顺序要求所有事务按照该顺序申请锁、可以要求事务在执行前申请到全部需要的锁否则放弃执行等
- 死锁检测：定时构建 wait-for graph，图中出现环则说明出现死锁，选择构成环的（一些）事务回滚来解除死锁
- 基于时间戳的悲观并发控制；
- 基于有效性验证的乐观并发控制；
- MVCC和Snapshot Isolation的并发控制；
我理解并发控制机制是为了让事务调度能够等价于一个串行调度来保证数据库的一致性，可串行化调度意味着并发执行这些调度效果等价于单线程串行执行。 教材1给出了一些关于可串行化的定义：
- 调度：若干事务的按某个顺序执行，称之为调度(schedule)，如调度 S1：<T1, T2, T3>，S2：<T4, T6, T5>
- 冲突：操作 I 和 J 是不同事务在相同数据项上的操作，并且其中至少一个是 write 指令时，我们说 I 与 J 是冲突的。若 I 与 J 是属于不同事务的指令且不冲突，则可以交换 I 与 J 的顺序得到一个新的调度。
- 冲突等价（conflict equivalent）：如果调度 S1 经过一系列非冲突指令的交换得到 S2，我们说 S1 和 S2 是冲突等价的。
- 冲突可串行化（conflict serializable）：若调度 S 与一个串行调度冲突等价，那么称调度 S 是冲突可串行化的。
上述概念可以合并记忆为：如果一个调度 S 经过交换非冲突的指令能够得到一个串行化调度，那么 S 就是可串行化的。可以使用优先图来判断 schedule 是否为冲突可串行化，如果事务T1和T2之间存在冲突指令，若T1先执行冲突指令，那么T1存在一条边指向T2。由此构造出一个优先图之后，若使用DFS/拓扑排序检测到图中存在环，则该调度不是可串行化的。
事务隔离等级
降低隔离等级可以获得更高的并发吞吐，隔离等级由高到低可分为以下四个等级：
- 可串行化（serializable）：保证可串行化，是最高隔离等级
- 可重复读（repeatable read）：允许读取已提交数据，一个事务两次读取同一个数据项期间，其他事务不得更新该数据。该隔离等级比起可串行化，可能会出现幻象问题。
- 已提交读（read committed）：允许读已提交数据，但不要求可重复。因此可能一个事务多次读取一个数据项会得到不同的值（这期间被其他事务修改了）
- 未提交读（read uncommitted）：允许读取未提交数据，最低隔离等级。
若使用两阶段锁并发控制协议，不同的隔离等级可以通过改变加锁的时机来完成。如可串行化需要在strict 2PL下加上索引锁才能保证；如果把索引锁取消，则隔离等级就变为可重复读；如果获取共享锁后立刻释放，则为已提交读；如果把共享锁取消，则变为未提交读。
如何实现持久性
日志恢复系统既保证事务的原子性，也保证持久性。
The End