一、概述
过瘾！过瘾！过瘾！P4 真过瘾！写 P3 的博客时我说过“感觉自己在数据库方面真正成长了”，但写完 P4 之后最大的感受就是，我终于理解了 andy 在第一课说过的“我只在乎两件事情，一个是我老婆，另一个是数据库。”
从代码量、概念晦涩程度、思考深度等各方面综合考量，我认为 P4 是难于 P2 的，也可能我对手写 B+tree 所花（浪费）的时间太多而怨念太深哈哈哈。
最后这篇博客有两个目的：
- 记录我的学习心得，这个 project 涉及到并发控制、二阶段锁、事务及其隔离级别、死锁及其检测/预防等概念，需要"学而时习之"。
- 记录我的思考过程，完成 P4 需要对二阶段锁、隔离级别、事务之间相互暴露可能发生的问题这三大块之间的关系有深入的思考和清晰的理解。
二、事务相关概念回顾
1 transaction 事务
事务是访问或更新数据项的一系列操作的一个集合，简单来说就是一系列读写诶操作的集合。
transaction 的正确性标准称为 ACID：
- 原子性（Atomicity）：事务中的所有操作要么都发生，要么都不发生。
- 一致性（Consistency）: 四个特性中最抽象的一个，一个容易理解的描述就是：数据库描述的状态要和真实的物理世界保持一致，对数据的一组特定约束必须始终成立，比如转账事务T1 和查询两账户总额事务 T2，应该保证无论什么时候查询账户总额都是一样的。通过原子性、隔离性、持久性来维护这种一致的状态。
- 隔离性（Isolation）: 一个事务察觉不到他和其他事务是并发执行的。
- 持久性（Durability）:如果一个事务被
commit，则它对数据库的改变时永久的
2 如何确保四种特性
- 原子性：几乎所有现代系统都使用 logging 日志方式，DBMS 在 log 中按顺序记录所有 操作 信息，如果事务被 abort 需要回滚，就可以利用日志中的信息来实现。
- 一致性：通过原子性、隔离性、持久性来维护这种一致的状态。原子性，隔离性和持久性是数据库自身的属性，而 ACID 中的一致性更多是应用层的属性。
- 隔离性：通过并发控制机制实现。
- 持久性：和原子性一样，也是通过 logging 日志方式实现
3 多个事务交织的顺序-schedule
多个事务并发时，DBMS 执行操作的顺序被称为 执行调度 (execution schedule)，简称 schedule。并发控制机制的目标是产生一个相当于串行执行 (serial execution) 的执行调度，也就是可串行化调度 (Serializable Schedule)
-
串行调度 (Serial Schedule)：一个事务执行完另一个事务执行，不存在事务之间的交织
-
等效调度(Equivalent Schedule)：两种调度的结果是一样的话，这两种调度就是的等效的
-
可串行化的调度 (Serializable Schedule)：当一种调度和串行调度是等效的，这种调度就是可串行化的调度
以下面为例，图 1 中 schedule1 和 schedule2 是两种执行调度，schedule2 明显是串行调度，不存在事务之间的交织。schedule1 的执行结果和 schedule2 是一样的，所以 schedule 1 与 schedule2 是等效调度。与串行调度 schedule2 等效，所以schedule1 是可串行化的调度
冲突操作：如果两个操作位于不同的事务中，且操作同一个对象，且至少一个操作是写，那么这两个操作就是冲突操作，冲突操作包括：
- R-W 读写冲突 (导致 不可重复读)：一个事务在多次读取同一对象时无法获得相同的值。
- W-R 写读冲突 (导致 脏读)：一个事务在另一个的事务提交其更改之前就看到了该事务的写入效果。
- R-R 写写冲突(导致 丢失更新 或 脏写)： 一个事务覆盖了另一个并发事务的未提交的数据。
识别冲突操作的意义在于，如果位于两个事务中的两个连续操作不是冲突操作，他们可以交换顺序！以产生等效调度！如下图中的最左边的 schedule 和最右边的 schedule 是等效调度
- 冲突等效：一个调度 S 通过一系列非冲突指令的交换而转换成另一个调度S'，则这两个调度是冲突等效的
- 冲突可串行化（Conflict Serializabile）：如果一个调度 S 与一个串行化调度是冲突等效的，则调度 S 被称为是冲突可串行化的。
所以上图最左边的schedule 是冲突可串行化的。
以上是2 个事务的 schedule 可以使用交换顺序来识别一个 schedule 是否是冲突可串行化的，如果是多个事务，这样的交换会很复杂，所以 检测多个 transactions 构成的 schedule 是否 serializable 需要使用依赖图 (dependence graphs) / 优先图（precedence graph）