cmu 15445 并发控制理论 -ACID

ARCHITECTURE

MOTIVATION 动机

• 丢失更新用并发控制

• 持久化用恢复手段

CONCURRENCY CONTROL&RECOVERY

• ACID 的基础

TRANSACTIONS 事务

• 事务是对数据库执行一系列一个或多个操作（例如，SQL查询）以执行一些更高级别的功能。

• 它是DBMS中的基本变化单位：不允许部分事务！

EXAMPLE

• 一条 sql 语句也算一个事务

STRAWMAN SYSTEM 想当然的系统

• 复制出来临时文件

• 修改成功写回

• 修改失败删除

PROBLEM STATEMENT

• 临时不一致 可接受

• 永久不一致 不可接受

• 我们需要有个标准来判断这样的交错是否有效

DEFINITIONS

• 不关心外部数据

• 只关注读写本身

• 简化分析问题的模型

• 数据库只关心数据本身，不关注索引

• 事务只关注读写

• 事务开始 begin

• 结束 commit or abort

CORRECTNESS CRITERIA:ACID 正确性标准

• 原子性：要么都执行，要么不执行

• 一致性：事务结束后，数据保持一致性。a b 转钱问题，钱不能多。

• 隔离性：事务之间保持隔离。理想情况。

• 持久性：如果txn提交，其效果将持续存在。

AGENDA

ATOMICITY OF TRANSACTIONS 原子性

• 执行txn的两种可能结果：
• 完成所有动作后提交。
• 执行某些操作后中止（或被DBMS中止）

• DBMS保证txns是原子的。
• 从用户的角度来看：txn总是要么执行其所有操作，要么根本不执行任何操作。

EXAMPLE

• 场景1：
• 我们从林的账户中扣除了100美元，但在我们转账之前，DBMS中止了txn。

• 场景2：
• 我们从林的账户里扣除了100美元，但是在我们转账之前停电了。

MECHANISMS FOR ENSURING ATOMICITY 手段

• 方法1：日志
• 记录DBMS记录所有操作，以便它可以撤消中止事务的操作。
• 维护内存和磁盘上的撤消记录。 undo log
• 把这想象成飞机上的黑匣子…
• 几乎每个DBMS都使用日志记录。
• 审计跟踪 危险操作 普通日志
• 提高性能 例如 wal

• 方法2：影子分页 （影分身）
• DBMS制作页面的副本，而txns对这些副本进行更改。只有当txn提交时，页面才对其他人可见。
• 最初来自System R。
• 很少有系统这样做
• CouchDB
• LMDB（OpenLDAP）

CONSISTENCY 一致性

• 数据库所代表的“世界”在逻辑上是正确的。所有关于数据的问题都得到了逻辑上正确的答案。

• 一致性又分为数据库一致性

• 事务一致性

DATABASE CONSISTENCY

• 数据库准确地模拟现实世界并遵循完整性约束。

• 未来的事务会看到过去在数据库内提交的事务的影响。

TRANSACTION CONSISTENCY 业务去负责

• 如果数据库在事务开始（单独运行）之前是一致的，那么之后也是一致的。

• 事务一致性是应用程序的责任。DBMS无法控制这一点。
• 我们不会进一步讨论这个问题…

ISOLATION OF TRANSACTIONS 隔离性 重点！

• 用户提交txn，每个txn就像它自己运行一样执行。
• 更容易推理的编程模型。方便业务程序更容易实现，不必考虑事务的相交

• 但是DBMS通过交错txns的操作（读取/写入DB对象）来实现并发。

• 我们需要一种方法来交错txns，但仍然让它看起来像是一个一个地运行。

MECHANISMS FOR ENSURING ISOLATION 隔离性方法

• 并发控制协议是DBMS如何决定来自多个事务的操作的正确交织。 两类协议：

• 悲观：一开始就不要让问题出现。

• 乐观：假设冲突很少发生，在冲突发生后处理。

EXAMPLE

• 首先假设A和B各有1000美元。
• T1 把100美元从A的账户转到B的账户
• T2以6%的利息贷记两个账户。

• 运行T和T2的可能结果是什么？ 很多！但是A+B应该是：
• 2000美元*1.06=2120美元

• 不能保证T1会先执行 T2或反之亦然，如果两者一起提交。 但是净效应必须等效于这两个事务以某种顺序串行运行。

• 正确的两种输出

• 下面是详细的顺序图

SERIAL EXECUTION EXAMPLE 顺序的执行

INTERLEAVING TRANSACTIONS 交错的执行 ！better

• 我们交错txns以最大化并发。
• 慢速磁盘 / 网络I/O。
• 多核CPU。

• 当一个txn由于资源（例如，页面错误）而停顿时，另一个txn可以继续执行并取得进展。

EXAMPLE GOOD

EXAMPLE BAD

• A先减少 100 有 100 快的利息少算了

DB VIEW 数据库视角看这个不好的例子

• 读写的角度来看作了什么操作

• 自然引出 需要有什么机制保证数据库能识别这种顺序不正确的情况

CORRECTNESS 怎么保证正确呢

• 寻找一种等效于串行执行的计划

FORMAL PROPERTIES OF SCHEDULES 等效的概念

• 真串行计划
• 不交错不同事务的操作的计划。

• 等效计划
• 对于任何数据库状态，执行第一个计划的效果与执行第二个计划的效果相同。
• 不管算术运算是什么！

• 可串行化计划 和真串行计划是等效的，可转换成真串行
• 等效于事务的某些串行执行的计划。
• 如果每个事务都保持一致性，则每个可串行化的调度都会保持一致性。

• 与txn启动时间或提交顺序相比，可串行化是一个不太直观的正确性概念，但它为DBMS在调度操作方面提供了额外的灵活性。简而言之就是可串行化比真串行强。

• 更多的灵活性意味着更好的并行性。

CONFLICTING OPERATIONS 冲突操作的概念

• 我们需要一个正式的等价概念，它可以基于“冲突”操作的概念有效地实现

• 两个操作冲突，如果：
• 它们是不同的事务，
• 它们的操作 作用在同一个对象身上，其中至少有一个是写。

INTERLEAVED EXECUTION ANOMALIES 交错执行的异常

• 三种冲突

• 读写

• 写读

• 写写

READ-WRITE CONFLICTS 不可重复读

• 不可重复读
• 我重复读发现数据不一样了

WRITE-READ CONFLICTS 脏读 也叫 读未提交

• 脏读 （读未提交）

• 我写了 但我没提交

• 另一个事务拿我写了的去做别的事去了

• 最后我回滚。。

WRITE-WRITE CONFLICTS

• 复写未提交数据

FORMAL PROPERTIES OF SCHEDULES

• 鉴于这些冲突，我们现在可以理解可串行化意味着什么。
• 这是为了检查调度计划是否正确。
• 这不是如何生成正确的调度。

• 有不同的可串行性：
• 基于冲突的可串行化 大部分是用这个
• 基于观察的可串行化

CONFLICT SERIALIZABLE SCHEDULES 冲突等效概念

• 两个调度计划是冲突等效的，如果：
• 它们涉及相同交易的相同行为，
• 并且每一对冲突的动作都以相同的方式排序。

• 如果：S 是 冲突序列化，
• 则 S 是冲突等效的对于某些真串行计划。

CONFLICT SERIALIZABILITY INTUITION

• 歌词大意就是你 swap 事务图上的读写操作

初始状态

滑动操作

等效成串行执行

• 滑动 操作

• 直到 T1 所有操作等效成比 T2 所以动作先发生

• 为什么可以滑动 可交换的动作之间 没有之前提到的三种冲突

• R (A) R (B) 滑动 读 A 和 读 B 没涉及到同一 obj ,读读无冲突

• W (A) W(B) 滑动 写 A 和写 B 没涉及同一 obj，写写无冲突

• W (B) R(A) 滑动 写 B 和 读 A 也没涉及同一数据，写读无冲突

• 反例 这个是第三种冲突 写写冲突 提交前写重复

• 读写也有冲突 R(A)和 W(A)

• 交换操作对应两个事务可以简单分析

• 但是很多事务开销就巨大了

• 自然引出了新算法

DEPENDENCY GRAPHS

• 节点代表事务

• 如果冲突的时候 Ti 比 Tj 先发生

• 就用一条边来指示事务之间的冲突

• 如果几个事务的图有环，就代表永远达不到等效串行化

EXAMPLE

• 有环，永远无法通过滑动操作来达到等效串行化

• T1 的 W(A) 永远要在 T2 的 R(A) 之前发生

• T2 的 W(B) 永远要在 T1 的 R(B) 之前发生

• 所以 T1 T2 互相依赖

• 不能等效成串行化的

• T2 可以无脑往上 最上

• T1 次之

• T3 最低

• 用户真实的事务状态顺序可以转化为可串行化的执行过程

• 就说明了这样的事务顺序是合理的

• 依赖图的特例

• 虽然依赖，但是这个业务场景是 ok 的

VIEW SERIALIZABILITY 基于观察的

• 不重要直接举例

EXAMPLE

• 基于冲突 有环 不能等效串行化

• 但观察业务发现能转

• 基于观察能发现依赖图有一定的局限性，会错杀一些

SERIALIZABILITY 总结

• 与基于冲突串行化相比，观察串行化允许（稍微）更多的计划。
• 但很难有效执行。人脑比机器聪明能观察出来业务

• 不能靠这两个方法简单的判断所有计划都是可串行的，比如错杀的情况。
• 这是因为他们不理解操作或数据的含义（回忆示例3）

• 在实践中，Comflict Serializability是系统支持的，因为它可以有效地执行。

• 为了允许更多的并发，一些特殊情况在应用程序级别单独处理。

• 大多数系统，只读是不进行任何判断的

UNIVERSE OF SCHEDULES

• 基于冲突的可串行化判断是严格的

• 可能错杀

TRANSACTION DURABILITY 持久性

• 没有一半的更新。

• 失败的事务没有变化。

• DBMS可以使用日志记录或影子分页来确保所有更改都是持久的。

• 更多关于隔离级别的在 cmu 15721 会有介绍

• 另外附上实习小伙伴的对于 SI 的介绍

快照隔离级别原理 | StoneDB 技术分享 #1

这篇文章我们介绍了快照隔离级别 SI 以及和 RR 的区别，SI 是对四种常见隔离级别的补充，能够有效解决幻读的问题，是对 SQL 标准的重要补充。

https://mp.weixin.qq.com/s/3flKQtgC6CLCGGU40Zjpbw

ACID PROPERTIES

CONCLUSION

• 并发控制和恢复是DBMS提供的最重要的功能之一。

• 并发控制是自动的，数据库自动操作
• 系统自动插入锁定/解锁请求并安排不同txns的操作。
• 确保结果执行等效于按某种顺序一个接一个地执行txns。

• Spanner:Google's Globally-Distributed Datahase

• TiDB 的思想来源

• 建议使用数据库的事务功能