Skip to content

Latest commit

 

History

History
188 lines (111 loc) · 12.2 KB

7. 隔离性的概念.md

File metadata and controls

188 lines (111 loc) · 12.2 KB
Raw

隔离性的引入

  • 并发控制第一法则：并发执行不应导致程序的失效
  • 并发控制第二法则：相比于串行执行，并发执行不应有更低的吞吐量和更长的响应时间

隔离性的依赖模型

理解隔离性结果最简单的方式，是根据事务的输入和输出来理解。把事务看作是对系统对象的一组读写操作。

两个事务对同一个对象的读操作不会破坏一致性，因为读操作不会改变对象的状态（假定其初始状态是一致的）。因此，==只有写操作有可能带来问题==。同一事务对同一个对象的两个写操作也不会违反一致性，因为 ACID 特性假定了事务知道它正在干什么。==ACID 特性假定，如果事务隔离地运行，最终会正确地变换系统状态==。因此，只有两个并发事务之间同写操作有关联的交叉操作才可能造成不一致或违反隔离性。

==如果事务集 {Ti} 中任一事务的输出同其余事务的输入以及输出无交集，则事务集可以无并发异常地并行执行==。

静态分配和动态分配

静态分配的问题是很难在事务运行前计算其输入和输出。

动态分配系统中，每一个事务都被看作是一系列的操作行为而不是输入-输出集，每个操作的请求否在其出现时按需调度。

事务依赖

对动态分配模型的一个更机械的看法是，事务是一系列在对象上运行的操作（action）。一个特定的对象一次只接受一个操作，每个事务的操作要么是读对象要么是写对象。

对象在被这些写操作修改后，便形成一连串的版本。读不会改变对象的版本，但是每次写一个对象时，它就获得了一个新的版本，如果事务读一个对象，事务依赖于该对象的版本。如果事务写一个对象，导致对象版本依赖于写事务。当一个事务终止或是被撤销时，所有的写操作都被撤销。这就导致对象得到新-新版本（即撤销看起来更像平常的更新）。

==对象模型是思考并发性的一种优雅的方式。它认为任何事务都是不变的，变化的只不过是其产生的新的对象的版本而已。==

下图显示了一个事务的依赖图：

image-20220117005424331

一个依赖图可以看作是一个时间序列，==如果事务 T1 到事务 T2 有一条边，那么 T1 访问的对象随后会被 T2 访问，并且这些访问中至少有一个产生一个新的版本==。在这种意义上，T1 和 T2 之前运行。在事务的纯顺序执行中，即运行 T1 至结束，再运行 T2 至结束，所有的依赖箭头都是从 T1 指向 T2。但是在并发执行中，依赖箭头可以形成一个任意的图。

隔离定理的主要结论是：==任何一个没有环的依赖图都暗示了事务的一种隔离执行方式==。另一方面，如果依赖图有环，则事务不是以隔离的方式执行的。这一点很明显：如果依赖图没有环，那么事务可以按 ==拓扑排序== 产生等价的执行顺序，这里每一个事务串行执行，一个事务结束后另一个事务开始；这暗示了事务是隔离运行的，好似没有并发运行一样；这里同样也隐含这没有并发异常。如果有环，这样的一个排序是不可能的，因为至少有两个事务 T1 和 T2，使得既有 T1 在 T2 前运行，又有 T2 在 T1 前运行。

三种有害的依赖⭐

image-20220117010404513

  • ==丢失更新 (Lost update)==：事务 T1 的写被事务 T2 所忽略，事务 T2 直接在对象的初始值 <o,1> 上写。
  • ==脏读 (Dirty read)==：T1 在 T2 写之前读了一对象，接着 T2 又对该对象做了修改。T1 读的版本可能不一致，因为它不是 T2 所产生的最终（提交）值。
  • ==不可重复读 (Unrepeatable read)==：T1 读了某对象 2 次，一次在 T2 更新该对象之前，一次在 T2 完成更新操作提交事务之后。这两次读操作返回的是该对象不同的值。

这三种不一致的基本形式覆盖了所有的情况，如果可以防止它们发生，那么将不会有并发异常，事务将表现为隔离运行的状态。

隔离性：应用程序的观点

隔离性：用户定义 1

事务处理系统可以并发地运行事务，但它的结果如同顺序执行一样，系统行为等价于事务的 ==某种== 串行执行。

隔离性：用户定义 2

  1. T 不会重写其他事务的脏数据
  2. T 所写的数据，在 T 提交（COMMIT WORK）之前，不会被其他事务读或者写
  3. T 不会读其他事务的脏数据
  4. T 在提交之前，其他事务不会写 T 所要读的（脏）数据。

条件 0 和 1 排除了丢失更新，2 防止了读脏数据，3 防止了不可重复读。

隔离性定理

规范事务与两阶段事务⭐

一个事务是 ==规范== (well-formed) 的，如果事务中所有的 READ、WRITE、UNLOCK 操作都由锁覆盖着，且如果每一个封锁动作的后面最终都有一个相应的 UNLOCK 操作。

一个事务是 ==两阶段== (two-phzse) 的，如果其所有的 LOCK 操作都在 UNLOCK 操作之前。一个两阶段事务 T 有一个成长的阶段，T[1],…,T[j]，在此阶段获得封锁；以及一个收缩阶段，T[j+1],…,T[n]，此阶段释放锁。

image-20220117012517041

事务的调度⭐

一组事务的所有操作序列，在保持各自顺序的情况下，任意归并成一个单一序列，我们称之为这组事务的一个 ==调度== (history)。

最简单的调度是首先运行一个事务的所有操作，然后再运行另外一个事务的所有操作，如此下去。这样的 “一次一个事务” 的调度成为 ==串行调度== (serial history)。很明显，串行调度不会出现由并发导致的不一致性，事务也不会有脏数据。

合法调度和锁的相容性

==遵守封锁限制规则的调度称为 合法 (legal) 的调度==。下表定义了锁请求和锁类型的相容性：

image-20220117013043964

图 7-4 显示了三个代表性的调度，

  • 第一个调度是串行的
  • 因为 T1 和 T2 并发执行，所以第二个是非串行的，但是合法的
  • 第三个调度也是一个并发调度，但是不合法，因为 T1 和 T2 同时对对象 B 加了排他锁。

image-20220117013228911

版本、依赖、依赖图

如果调度 H 中事务 T 读或写已经被 T^'^ 写过的数据，或者是 T 写已经被 T^'^ 读过的对象，我们就说调度 H 中一个事务 T ==依赖== (depend) 另一个事务 T^'^。

如果两个调度有相同的依赖，那么这两个调度中，事务读同样的输入，写同样的输出，因此使得这两个事务是等价的。

等价的和隔离的调度：BEFORE、AFTER 和 Wormholes

每个调度都定义了一种依赖关系。如果基于同一个事务集的两个调度具有相同的依赖关系（DEP(H)=DEP(H^'^)），那么称这两个调度是==等价== (equivalent) 的。

如果一个调度等价于一个串行调度，那么称之为==隔离的== (isolated)。

一个调度的依赖定义了事务的一个时间序列。这个时序用符号 <<<H 或 <<< 来标价，BEFORE 和 AFTER 定义如下：

​ $BEFORE(T)={T^{\prime}|T^{\prime}&lt;&lt;&lt;T}$

​ $AFTER(T)={T^{\prime}|T&lt;&lt;&lt;T^{\prime}}$

事务 T^'^ 即在另一事务 T 的 BEFORE 中又在其 AFTER 中，即 $T^{\prime} \in BEFORE(T^{\prime}) \cap AFTER(T)$ 这样的事务叫做虫洞事务。

虫洞事务不具有隔离性

如果依赖图存在环（回路），那么这个调度不可能等价于一个串行调度，因为存在某个事务即在另外一个事务之前运行又在它之后运行。

image-20220117015732033

定义小结⭐

  • 如果事务的每个 READ、WRITE、UNLOCK 都被相应的锁覆盖，且所有的锁都是在事务结束时释放，那么我们称这样的事务是==规范的 (well-formed)==。
  • 如果一个事务可以分成两个阶段，只请求封锁的扩展阶段和只释放封锁的收缩阶段，那么我们称之为==两阶段 (two-phzse) 事务==。
  • ==调度 (history)== 是一组事务的操作某种合并的结果
  • 如果调度中的事务是一次只运行一个事务，则称之为==串行 (serial)== 的
  • 一个调度是==合法 (legal)== 的，如果同一时间没发生两个不同事务的锁冲突
  • 每个调度都定义了一个==依赖关系 (dependency relation)==，它刻画了事务之间的数据流
  • 如果两个调度具有相同的依赖图，则称它们是==等价 (equivalent)== 的
  • 如果一个调度等价于某个串行的调度，那么我们说该调度是==隔离 (isolated)== 的（注：又称为可串行化）
  • ==虫洞 (wormhole)== 是一个调度中的事务对，其中 T 在 T^'^ 之前运行，而 T^'^ 在 T 之前运行

虫洞定理：一个调度是隔离的，当且仅当它没有虫洞事务

封锁定理：==如果所有的事务是规范的且是两阶段的，那么任何一个合法的调度将是隔离的==。⭐

封锁定理（逆定理）：如果一个事务不是规范的或不是两阶段的，那么可以构造出另外一个事务与之组成虫洞

回滚定理：一个先 UNLOCK 后又 ROLLBACK 的更新事务，不是两阶段的。

隔离性的级别

隔离级别的定理

用户定义的 4 个隔离级别为：

  • 0 级 不会重写高一级别事务的脏数据
  • 1 级 不会有==丢失更新==
  • 2 级 既不会有==丢失更新==也==没有脏读==
  • 3 级 没有==丢失更新==且==可重复读==（其中隐含了==没有脏读==）

对应 4 个隔离级别的封锁协议如下：

  • 0 级 封锁协议对==写操作==是规范的（写加锁）
  • 1 级 封锁协议对==排他锁==是两阶段的，对==写操作==是规范的（写加锁）
  • 2 级 封锁协议对==排他锁==是两阶段的，对==读写操作==是规范的（读写都加锁）
  • 3 级 封锁协议是两阶段的，对读写操作是规范的

SQL 与隔离级别

隔离级别越低，事务请求的锁越少或保持锁的时间越短。支持 2 级别隔离，事务可以扫描数据库而不会封锁太多对象，因此不会影响其他事务。考虑 SQL 代码片段：

select count(*) from emp where eyes = 'blue' and hard = 'red';

这个查询可能会扫描整个 EMP 表来寻找记录，结果可能找不到一个。使用 3 级隔离，当他扫描完成时，将会加成千上万个记录锁或一个表锁。有些 SQL 系统会在读完记录或表后，默认情况下自动释放共享锁。

确切地说，SQL 系统实现的是一个比纯粹的 2 级别更好的形式，差异之处就在于提供了游标稳定性。一个基于游标的记录 FETCH，跟着一个独立的更新或一个基于游标的更新（Update where current of cursor），如图 7-8 所示，为了防止丢失修改，大多数 SQL 系统对当前游标指向的记录始终保持一个共享锁。

image-20220119004409189

本书定义的 4 种隔离级别与 ANSI SQL 4 种隔离级别的关系:

  • RU — 1
  • RC — 2
  • RR — 2.9999999
  • SERIAZABLE — 3

Tips:

  • MySQL 的 RR 实际上保证了快照读的情况下是没有幻读的（当前读仍然有幻读）
  • Degree Consistency 并不不能和 ANSI SQL Isolation 完全对应。

参考：“A Critique of ANSI SQL Isolation Levels,” Proc. ACM SIGMOD 95, pp. 1-10, San Jose, CA, June 1995, © ACM.

Reference

  1. Gray, Jim, and Andreas Reuter. Transaction processing: concepts and techniques. Elsevier, 1992.
  2. A Critique of ANSI SQL Isolation Levels,” Proc. ACM SIGMOD 95, pp. 1-10, San Jose, CA, June 1995, © ACM.