【学习笔记5】数据库中的并发控制

1 并发控制的功能定位

数据库的模型主要如图1所示。SQL查询进过查询分析和优化以后，进行查询执行动作。在执行阶段通过某种访问方式对缓存于Buffer Pool的数据进行操作。

数据库系统要并发处理请求的原因是提高数据库系统的吞吐：

  1. 使IO密集型查询让出CPU，提升OS资源利用率
  2. 更好的利用服务器多核架构
  3. 较少查询请求的等待时间
图1 数据库中并发控制的功能

2 并发概念定义

2.1 事务（transaction）

事务是一系列逻辑操作单元的集合，事务是并发控制的基本目标单元，并发控制机制要保证事务在并发时的正确性。

2.2 ACID（事务并发正确性的定义）

ACID定义了事务并发的正确性，也就是什么样的事务才是并发正确的。符合一下四种性质的事务即为并发正确的。

  • atomicit：事务中的操作集合要么全部成功执行，要么全部未执行。

  • consistency：事务的一致性可以理解为两个方面：数据库系统一致性以及事务逻辑一致性。数据库系统一致性即数据库在事务执行后，数据中存储的数据仍然符合该database relation schema中数据完整性约束。事务逻辑性一致更多需要由应用来保证，数据库系统只能保证数据库读写操作的正确性，上层逻辑超出来数据库的能力。

  • isolation：事务执行过程中，以事务的视角其应该是唯一在执行的事务。数据库标准中有四种隔离级别，隔离强度由高到低依次是

    隔离级别 Dirty read Unrepeatable read Phantom phnomenon
    serializabe No No No
    repeatable read No No Maybe
    read committed No Maybe Maybe
    read uncommitted Maybe Maybe Maybe

  • durability：持久性，提交的事务不会随着系统或者硬件的crash而消失。

符合ACID的事务即可认为是在数据库系统中正确执行的任务。

保证durabilty两种方法：（1）在事务提交时刷盘 （2）使用logging，由此需要一套recovery system

保证atomicity也有两种方法：（1）shadow paging （2）logging recovery system

而事务的consistency和isolation则由并发控制机制来保证。

3 并发控制概念定义

并发控制机制（concurrency control scheme）的目标是对多个并发执行的事务进行调度管理，使得并发的事务在执行结束以后数据库系统的状态和这些事务按照某种顺序串性执行后的状态是一致的。模型化此种目标描述可以为：冲突可串性化（conflict serializability）或者视图可串性化（view serializability）。视图可串性化能评判的并发控制调度更多（如图2，定义可见《Database System Concepts 7th》Page 867），但是其难以实现，是NP-hard的，所以不做详细讨论。


view serializability, conflict serializability与serializability

并发控制机制的设计要考虑三个目标：

目标 作用
conflict serializability 事务并发正确性
recoverability 可恢复性，使得事务在系统crash时或者事务所依赖（dependant）的事务回滚时，得到的结果是正确的
cascadeless 无级联性，更严格要求的recoverability，一个事务的回滚不会引起级联依赖关系的事务回滚，级联回滚的代价高昂，应该避免
phantom phenomenon 解决幻读，符合上述三种特性的调度对于只包含READ和WRITE操作的事务是完善的，但是要保证对并发的insert、delete、update控制，要解决幻读。通常使用index-locking或者predicate-locking

3.1 冲突可串性化

冲突可串性化用于定义一个并发调度是否是可串性化的。（在只考虑WRITE和READ操作时）记事务操作I和J分别是事务T1和事务T2的操作

3.1.1 定义：操作冲突

如果I和J都操作访问同一个数据对象（可以是DB、relation或者tuple等任意数据库数据对象），且两者至少有一个是WRITE操作，则I和J是冲突的。也就是说对两个事务对同一个数据对象操作时，除非I=READ，J=READ，否则I和J都是冲突的。

不冲突的两个操作，在调度S中是可以随意调换上下顺序的。

3.1.2 定义：冲突等价

如果调度S可以通过将不冲突的操作进行一系列顺序调换得到另一个调度S'，则称S与S'是冲突等价的。

3.1.3 定义：冲突可串性化

如果一个调度S和一个串性调度是冲突等价的，则称调度S是冲突可串性化的调度。

3.1.4 冲突可串性化检测算法

可以使用优先图（precedence graph）来检测一个调度S是否是冲突可串性化的。优先图（precedence graph）是一个有向图。图中的一个节点表示一个事务。图中的边表示两个事务之间有冲突操作I（T1）和J（T2），其中边的方向表示事务间冲突操作的先后关系。源事务中，操作I在调度S里先于冲突操作J执行。这样形成的优先图有向边表示，在任何和调度S冲突等价的串性调度S'中，事务T1都必须先于事务T2执行。

检测算法：如果在调度S的优先图中，没有环，则调度S是冲突可串性化的；反之，调度S是冲突不可串性化的。

如果优先图是无环的（DAG），通过对优先图进行拓扑排序，可以得到一种线性序列，该序列可以作为一种可能的事务串性化执行顺序。

3.2 并发控制可恢复性

3.2.1 定义：依赖，dependant

如果一个事务T1 READ了一个由事务T2 commit前WRITE的数据对象A，则称事务T1 依赖于事务T2 。（attention：提交前写的数据，提交后不是。也就是说，事务T1 读了事务T2 未提交数据，因此而产生依赖关系）

3.2.2 定义：可恢复性

当事务T1 READ了事务T2 WRITE的未提交数据（也就是事务T1 依赖于T2 ）时，如果事务T2先于事务T1 提交，则称这样的调度是可恢复的。

实现可恢复性的一种方案是不可脏读，在此隔离级别上（>= Read Committed），事务T1 永远不可能读取到未提交的数据。可恢复性，使得事务在系统crash时或者事务所依赖（dependant）的事务回滚时，得到的结果是正确的。

3.3 并发控制无级联性

定义：对于并发的事务T1、T2、T3，对于任意一组事务对，该事务对都是可恢复的，则称此调度是无级联性的。无级联性是一种更严格要求的recoverability，一个事务的回滚不会引起级联依赖关系的事务回滚。级联回滚的代价高昂，数据库系统应该采取一定的策略避免此种情况的发生。

3.4 并发控制中的幻读

在上述讨论的并发控制模型中，事务操作的数据对象是进行并发控制的一个参数，且上述只讨论了对数据对象的控制。在事务只包含READ和WRITE操作时，满足冲突可串性化、可恢复和无级联的并发控制机制是完备的。但是，如果考虑复杂的update、insert、delete操作事务，当这些事务的操作数据对象是满足另一个事务的‘选择’操作谓词时，可能导致该事务错读或者漏读。这样的现象成为幻读（Phantom Phenomenon）。幻读现象出现的\color{SeaGreen}{本质原因}是上述的模型假设是并发控制机制对事务进行调度时，事务的操作对象集合是并发控制机制可知的参数（数据对象集合是\color{SeaGreen}{offline}的）。然而在真实系统中，事务的操作对象是事务执行过程中根据‘选择’谓词动态获取的（数据对象集合是\color{SeaGreen}{online}的）。

解决方法：

  1. 索引加锁协议（index-locking）：完整的并发控制机制不仅要考虑事务要操作的数据对象，还要考虑对操作数据对象的元数据（例如索引）进行并发控制。
  2. 谓词加锁协议（predicate locking）：对该relation上正在执行事务的谓词进行检查，检查本事务的updata、insert或者delete是否和为此冲突。

4 二阶段锁协议--基于锁的并发控制协议

二阶段锁协议（Two Phase Locking Protool，2PL）是一种悲观并发控制机制（Pessimistic Concurrency Control），其总是假设事务之间会存在冲突。后文讲述二阶段锁协议如何实现并发调度的冲突可串性化、可恢复性、无级联性以及解决phantom phenomenon的技术。

2PL的优点是简单，不需要事务的其他信息，不需要额外增加数据结构（timestamp ordering、multiple version、snapshot isolation）或者对数据库中数据对象进行排序（graph-based protocol，例如tree protocol）。

4.1 概念

4.1.1 锁类型：

  1. shared lock，共享锁
  2. exclusive lock，排它锁

4.1.2 锁兼容（compatibility）

如果事务T1可以无视事务T2加在数据对象A上的锁而加上其需求的锁，则称两事务的锁是兼容的。

4.1.3 锁兼容矩阵

Shared Exclusive
Shared true false
Exclusive false false

4.1.4 锁协议

事务遵从一系列的规则对数据库对象进行加锁、解锁操作，这个规则集合称为锁协议。如果并发事务依据此协议而得到所有并发调度都是冲突可串性化的，则称此锁协议是合法的（legal）。

4.2 简单2PL

在2PL中，每个事务有两个阶段：

  1. Growing Phase：事务在此阶段只能对数据对象进行加锁请求，不能产生任何解锁请求。
  2. Shrinking Phase：事务在此阶段只能对数据对象执行解锁请求，不能产生任何加锁请求。

事务在Growing阶段，获得其最后一个请求的锁的时间点称为lock point。2PL并发调度机制中的所有事务串性化顺序可以根据lock point排序得到。

4.3 Strict 2PL--无级联回滚性的2PL

原始的2PL并发调度器是冲突可串性化的，但是可能产生级联回滚。2PL的变种，严格的二阶段锁协议：在原始2PL的基础上，事务在Growing阶段获得的排它锁保持到事务提交才释放。

另一变种是rigorous 2PL，在原始2PL的基础上，所有锁保持到事务提交时才释放。

采用strict/rigorous 2PL可以避免级联回滚，以及事务undo重放。

4.4 2PL优化--锁转化（lock conversions）

在事务执行过程中对共享锁和排它锁进行转换，符合2PL的锁转换方式：

  1. 锁升级（upgrade）：由共享锁转化排它锁，只能发生在2PL的growing阶段。
  2. 锁降级（downgrade）：由排它锁转化为共享锁，只能发生在2PL的shrinking阶段。

4.5 真实系统中，一般2PL模式

  1. 事务T1发起对数据对象Q的READ请求时，DB系统产生losk-S(Q)+READ(Q)的组合调度。
  2. 事务T1发起对数据对象Q的WRITE请求时，DB系统检查事务T1是否有对Q的贡献锁，
    • 如果有，DB则产生uprade(Q)+WRITE(Q)的调度
    • 反之，DB产生lock-X(Q)+WRITE(Q)的调度
  3. 事务T1提交或者回滚后，事务T1所有持有的锁释放

上述的实际使用模型可以看出是一种带有锁转化的Rigorous 2PL协议。

4.6 锁管理器

锁管理对系统中所有的锁进行管理，相应系统对锁的请求。当引入锁到系统中时，有两个问题需要阻止：死锁（deadlock）和锁饿死（starvation）。在数据库系统中，锁管理器不需要是持久化的。

4.6.1 锁饿死的解决方案

  1. 当锁请求的锁类型和锁的持有类型是兼容时，向请求者响应授权。
  2. 所有未响应的锁请求排队。（锁排队）

4.6.2 死锁解决方案

死锁产生的原因：

  • 互斥条件：进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源（不兼容的锁不可授予）
  • 请求和保持条件：进程获得一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但该进程不会释放自己已经占有的资源（锁等待）
  • 不可剥夺条件：进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放（锁不可抢占）
  • 环路等待条件：进程发生死锁后，必然存在一个进程-资源之间的环形链（环）

死锁的解决策略有两种，死锁预防（deadlock prevention）以及死锁检测恢复（deadlock detection and recovery）

4.6.2.1 死锁预防
  • 方案1：一次性获取所有锁，需要知道所有的访问数据对象，难以实现。
  • 方案2：锁排序，按顺序加锁。需要在事务开始前确定所有要访问的数据对象，然后依排序后依次加锁--Graph-based Protocol，例如tree protocol（没有什么实用性，详情可见《Database System Concepts 7th》18.1.5）。
  • 方案3：抢占式+回滚式死锁预防：
    • wait-die死锁预防模式：事务T1对被T2锁住的数据对象Q加不兼容锁时，如果T1的时间戳小于T2，则T1等待，否则T1回滚。
    • wound-wait死锁预防模式：事务T1对被T2锁住的数据对象Q加不兼容锁时，如果T1的时间戳小于T2，则T1抢占Q的锁且T2回滚，否则T1等待。
  • 方案4：锁超时，事务等待锁授权一定时间，否则事务就回滚。
4.6.2.2 死锁检测与恢复
  • 步骤一：通过一个wait-for graph维持系统当前执行事务的锁持有和请求信息
  • 步骤二：wait-for graph中检测是够存在环，如果存在即存在死锁；否则不存在死锁
  • 步骤三：死锁恢复

死锁恢复步骤：

  • 选则回滚事务，metrics：
    • 事务运行时间，或
    • 事务数据使用规模，或
    • 事务完成进度，或
    • 事务回滚级联牵连影响面
  • 事务回滚
    • total rollback
    • partial rollback，系统需要维护事务额外信息
  • 可能造成事务饿死（在统一个metric下，同一个事务被不断选为回滚事务），需要维持额外信息限制一个事务不断被死锁混滚的次数；（事务死锁回滚后仍然使用其原来的优先级/时间戳）

4.7 多粒度版本的二阶段锁协议（multiple-granularity）

如果对2PL中的加锁数据对象进行粒度划分，例如DB、relation、tuple等，将数据对象进行分组管理，可以得到更高的并行度。通过将数据对象组织为不同层级架构（hierachy），上层级的数据对象是下层数据对象的集合。在此架构下，对层级中一个数据对象的显示锁也可以表示出对下层数据结构的隐式锁。对一个数据对象加锁要求，必须先对该目标的父节点加锁，由此使得数据对象层级中根节点称为两性能瓶颈。为了提高并发性能，引入新的锁模式--意向锁模型。如果一个层级节点是意向锁模式，则其下一层级的节点必须被加上显示锁。意向锁模式的主要作用是可以在不用检查高层节点所有后代节点持锁情况下对高层节点加共享锁或者排它锁。意向锁的本质是通过事务加锁时加不同的锁来告诉其他事务一些其工作模式hints这种方式进而提高并发性能

4.7.1 意向锁模式（Intention Lock Model）

意向锁模型中一共有五种锁：

锁名称 作用
Intention-shared mode 下层级数据对象必须且只能被加显示共享锁
Intention-exclusive mode 下层级数据对象必须被加显示共享锁或者显示互斥锁
shared 显示共享锁
shared and intention-exclusive mode 以当前节点为根的子层级节点都加显示共享锁，但是这些节点的下层级节点必须将被加显示排它锁
exclusive 显示排它锁

4.7.2 意向锁兼容矩阵

IS IX S SIX X
IS \color{green}{true} \color{green}{true} \color{green}{true} \color{green}{true} \color{red}{false}
IX \color{green}{true} \color{green}{true} \color{red}{false} \color{red}{false} \color{red}{false}
S \color{green}{true} \color{red}{false} \color{green}{true} \color{red}{false} \color{red}{false}
SIX \color{green}{true} \color{red}{false} \color{red}{false} \color{red}{false} \color{red}{false}
X \color{red}{false} \color{red}{false} \color{red}{false} \color{red}{false} \color{red}{false}

4.7.3 多粒度二阶段锁内容

  1. 锁授予符合意向锁兼容矩阵
  2. 对数据对象层级中一个节点加锁必须先对其父节点加锁
  3. 对一个节点加显示共享锁或者意向共享锁时，事务必须至少获得该节点父节点的意向共享锁
  4. 对一个节点加显示排它锁或意向排它锁或者SIX时，事务必须至少获得该节点父节点的意向排它锁
  5. 加锁解锁符合2PL
  6. 事务对一个节点解锁时，事务必须对该节点的所有子节点都解锁

4.7.4 多粒度二阶段锁优化 -- lock escalation

在使用数据对象层级的数据库系统中，如果SQL请求包含对大量小数据的大规模数据锁请求，当数据库系统在生成SQL执行计划时，可以进行锁放大（lock escalation）。SQL请求直接请求上一层级的粗粒度锁。虽然锁放大会导致事务锁住部分无用的对象，但是可以极大减少频繁的小锁请求负载，从而提升系统的总体性能。

总结而言，多粒度二阶段锁协议适用于访问极少量数据的短事务和访问大规模文件数据的长事务混合场景（亦即OLTP、OLAP混合），因此有很高的实用性。

5 Phantom Phenomenon，幻读

如前文所述，无论是2PL、T/O还是其衍生品协议，它们都是在事务数据对象offline清形进行并发控制，他们呢的并发正确冲突可串性化正确性建立在数据操作对象已知的基础上，这导致了幻肢现象的产生。

原因第一层：insert、update、delete操作数据对象和另一事务的谓词匹配
原因第二层：并发控制协议基础是事务操作对象集合已知
原因第三层：本质是因为SQL是声明性语言，只能提供对数据的描述（predicate），在predicate和数据对象集合有一个映射（这就是数据库系统，如图2），然而就是这个映射的并发处理导致了幻读现象的产生。

为了实现完整的事务并发控制，有两种解决方法：

  1. index-locking protocol
  2. predicate-locking protocol
图2 index-locking与predicate locking

5.1 index-locking protocol

前置条件：relation含有索引；通过将幻肢问题转化为索引加锁冲突来解决问题。
协议内容：

  • 事务T1通过索引来查询其计划访问的数据
  • 索引查找对索引加共享锁
  • 事务对tuple的update、insert、delete必须获得索引的排它锁，在先完成索引的更新后再对page中的tuple数据进行对应操作
  • 加锁机制要符合二阶段锁协议
  • 按照并发控制机制来实现对tuple的更新

index-locking就是使用2PL来对索引数据对象进行并发控制，然后对索引进行事务的更新。在更新完成后，才能进行tuple数据的更新（tuple数据对象的并发控制又是单独的另一套机制）。本质就是规定来两个并发控制机制的顺序来保证完整的并发事务控制。

index-locking的锁粒度是index page，在B+树中就是叶节点。如果锁的粒度是叶节点中的K/V对，则就是key-value locking protocol。优化改进的key-value locking：next-locking protocol

5.2 predicate locking

谓词锁就是在图2中，在insert、update、delete事务并发控制时不对索引结构加锁。而是事务对当前relation中正在执行任务的谓词进行加锁检查，检查当前insert、update、delete事务的操作数据tuple是否匹配其中的谓词。如果匹配则说明有幻读冲突，事务等待谓词锁释放，这样就避免来幻读。

noting：我觉得在数据库中，即使没有索引并发控制，也需要对索引进行并发保护，因此只要事务在操作索引时符合2PL协议就行。如果采用predicate locking，则需要额外的信息维护，更加麻烦。

6. Timestamp Ordering Protocol -- 基于时间戳的并发控制协议

基于锁的并发控制协议在事务集合运行过程中，根据事务对数据对象的加锁顺序动态决定事务pair中事务调度顺序。而基于时间戳的并发控制协议则根据事务的时间戳事先决定事务的调度顺序。

6.1 概念

每个事务有一个时间戳TS(Ti)，时间戳的实现方式：

  • 系统时钟
  • 逻辑计数器

在基于时间戳的并发控制协议中，时间戳决定了事务的调度顺序，决定了事务对同一个冲突数据对象的访问顺序，每个数据对象也有两个时间戳：

  • W-timestamp(Q)：最近完成对Q写的事务的时间戳
  • R-timestamp(Q)：最近完成对Q读的事务的时间戳

6.2 T/O协议内容

  1. 事务的READ(Q)读操作：
    • 如果TS(Ti) < W-timestamp(Q)，说明数据已经被更新的事务覆写，当前事务回滚。
    • 如果TS(Ti)>= W-timestamp(Q)，说明当前读的数据对象是合法的，读操作执行，然后置R-timestamp(Q)=max(R-timestamp(Q)，TS(Ti) )
  2. 事务的WRITE(Q)写操作：
    • 如果TS(Ti) < R-timestamp(Q)或者TS(Ti) < W-timestamp(Q)，说明有更性的事务对Q进行了读或写操作，因此当前事务被回滚
    • 反之，则当前事务写执行成功，并将W-timestamp(Q)设置为TS(Ti)。

事务回滚后，系统将给事务重新分配时间戳。

T/O协议可以避免死锁的产生（破环了死锁的请求和等待条件），但是可能导致事务饿死（长执行时间事务被不断回滚）。需要采取额外的措施避免事务饿死。

原始的T/O并发控制协议是冲突可串性化的调度，但是不能保证可恢复性和无级联性。扩展T/O协议支持：

  • 可恢复性：追踪事务所有访问对象，当所有对事务读对象进行修改的事务提交后再进行提交（困难）
  • 无级联性：事务所有写操作归集到事务末尾执行 或者 事务对未提交数据的读延迟至对该数据写事务完成提交。

6.3 性能改进的T/O协议--Thomas' Write Rule

主要思想，旧时间戳事务的写操作在特定场景下被忽略掉，可以视为此事务的写被其他事务覆盖写了。

协议在原生T/O协议的基础上，修改事务的写操作WRITE(Q)逻辑：

  1. 如果TS(Ti) < R-timestamp(Q)，说明旧值被新事务读取，因此当前事务写操作不可执行，事务被回滚。
  2. TS(Ti) < W-timestamp(Q)，说明有新事务对值进行写，因此当前事务的写操作可以被忽略。
  3. 此时，TS(Ti) >= R-timestamp(Q)且TS(Ti) >= W-timestamp(Q)，因此事务可以执行WRITE(Q)操作，并且置W-timestamp(Q)=TS(Ti)

2PL和T/O协议是两种基本的并发控制协议，许多的并发控制协议都是基于两者的变种改进。

7. Optimistic Concurrency Protocol（Validation-based Protocol）

Optimistic Concurrency Protocol（OCC）又称基于验证的乐观控制协议，是Timestamp Ordering协议的一个变种。乐观并发在冲突少的场景下有优秀的性能，但是如果冲突发生，处理冲突的代价相对较高。

7.1 OCC协议内容

本协议中事务执行有三个阶段，有点类似read-copy-update（RCU）的并发同步。

  1. Read Phase：事务在此阶段读取所有其所需要的数据对象到事务的私有临时工作空间中。然后事务在其私有临时空间中执行事务逻辑，数据结果仍然保存在私有临时空间中。
  2. Vaidation Phase：系统根据验证机制（后续描述）判断事务是否能够进入第三阶段的Write Phase。
  3. Write Phase：在此阶段，事务将其私有临时空间中的数据写入到数据库系统中。只读事务没有此阶段。

7.2 OCC验证机制

OCC利用时间戳来对事务进行验证管理。每个事务有三个时间戳：

  1. StartTS(Ti)：事务TSi开始执行时间
  2. ValidationTS(Ti)：事务TSi结束Read阶段，开始Validation阶段的时间
  3. FinishTS(Ti)：事务TSi结束Write阶段的时间

OCC产生的冲突可串性化调度器的串性顺序等价于事务的ValidationTS(Ti)排序顺序。在OCC中，以ValidationTS(Ti)作为事务Ti的时间戳，亦即TS(Ti)=ValidationTS(Ti)。
事务Ti的验证机制规则为，对于任意先于事务Ti的事务Tk，事务Tk必须满足下列两个条件之一：

  • FinishTS(Tk) < StartTS(Ti)：也就是事务Tk在事务Ti开始之前已经结束，因此串性正确性必然得到保障
  • StartTS(Ti) < FinishTS(Tk) < VlaidationTS(Ti)，并且事务Ti的读数据集合与事务Tk的写数据项集合没有交集。此项规则保证来事务Ti的写不会影响事务Tk的读（Ti写时，Tk已经完成）；保证了事务Tk的写不影响Ti的读，因为Ti不读Tk所写的任何数据项。

无级联性：由于实际写发生在事务提交以后，因此自动防止了事务的级联回滚。
事务饿死：长事务可能由于一些列短事务而导致频繁重启。

OCC适用于读多写少，不同事务访问不同数据集合的场景。（冲突概率小，且数据交集小）
OCC的瓶颈在于一个集中的事务冲突检测验证中心，当事务并发高时，其速度会限制吞吐。

为了减少数据集的交集冲突，可以将数据库分为多个分区（partition）。
数据库系统只需要检测运行在同一个分区中的事务的冲突，减少集中有效性验证的负担。

7.3 PARTITION-BASED T/O

每个分区由一个锁保护，事务在其需要需要的分区队列中排队，只要当事务获取到所有其需要的分区锁时才开始事务的执行。

图3 PARTITION-BASED T/O

分区的T/O并发控制协议适用于：

  1. 事务待访问分区可知
  2. 大部分事务只访问同一分区中的数据

8. Multi-version Concurrency Control--多版本并发控制机制

Multi-verison Concurrency Control(MVCC)通过保存一个逻辑tuple的多个物理时间版本来增加数据库系统的并发性。在OCC协议中，每个事务也有一个该事务的数据版本。但是OCC的数据版本是事务私有的，只有本事务才能感知到该私有版本。在MVCC中，数据对象的版本是公开的，每个事务都能查看到一个逻辑数据对象的多版本数据，但是事务会根据MVCC协议选择合适的版本作为该事务“看见的”逻辑数据对象。通常在MVCC中，

  • 事务发出WRITE(Q)请求时，写请求对逻辑数据对象Q创建一个新的数据版本。
  • 事务发出READ(Q)请求时，读请求基于某种方式选择合适版本的数据对象作为事务可视的逻辑数据对象。

MVCC的有点是writer和reader不会相互阻塞。可以支持时间漫游的数据查询需求。

MVCC通常需要一个图4所示的事务状态表记录数据库系统中正在执行事务的状态（功能作用原理）。

图4 MVCC事务状态表

MVCC更多是一种并发控制的模式，在该模式中，具体的并发控制行为可以根据2PL或者T/O来实现。因此有：

  • multi-version two phase locking：在对数据进行读写前，对物理数据版本加锁
  • multi-version timestamp ordering
  • optimistic concurrency control（with validation）

8.1 多版本数据的存储

DBMS在每个tuple的pointer字段保存一个逻辑tuple的version chain。

version chain中数据存储的顺序：

  1. oldest-to-newest（O2N）：index中的索引指针指向了最旧的tuple，新创建的版本依次相连形成链表。
  2. newest-to-oldest（N2O）：index中的索引指针指向了最新的tuple，因此每次创建新的版本时需要更新索引的指针内容

version chain中版本数据的存储内容和存储位置实现有三种方式：

  1. append-only storage：图5是append模式的一个示例，postgreSQL采用来这种模式


    图5 append-only

  2. time-travel storage：index中指针稳定指向逻辑tuple的地址。每个逻辑tuple会指向一个额外的time-travel table。该表用以存储逻辑数据的多物理版本。


    图6 time-travel

  3. delta storage：每次拷贝原始数据生成新版本数据时，系统中只存储事务对该数据对象修改的字段。这种方式在写操作时可以减少数据拷贝量，能加强写性能。但是在读数据时，每次都需要动态构建新版本的数据，因此读性能受影响。Oracle和MySQL使用了delta存储，而PostgreSQL使用append only存储。


    图7 delta storage

8.2 Multi-version Timestamp Ordering

每个数据项Q包含一系列的版本<Q1, Q2, Q3, ..., Qm>。每个版本Qk包含三个元数据段：

  • content：版本Qk的值
  • W-timestamp(Qk)：创建Qk的事务的时间戳
  • R-timestamp(Qk)：成功读取Qk的所有事务的最大时间戳

当事务Ti创建一个新版本Qk时，置W-timestamp(Qk)=R-timestamp(Qk)=TS(Ti)；
当事务Ti读Qk时，R-timestamp(Qk) = max{R-timestamp(Qk)，TS(Ti)}。

令Qk表示Q的具有小于或等于TS(Ti)的最大写时间戳的版本。

  1. 若事务Ti产生READ(Q)请求，则所返回版本Qk的内容。
  2. 若事务产生WRITE(Q)请求，
    1. 若TS(Ti) < R-timestamp(Qk) ，则事务Ti回滚
    2. 若TS(Ti) = W-timestamp(Qk) ，则Qk的内容被覆盖
    3. 否则，创建Q的一个新版本

Multi-version T/O的优点是READ操作从不等待，总能成功。缺点是：

  • READ操作产生对Qk的R-timestamp写操作
  • WRITE的回滚操作高昂

Multi-verison T/O是冲突可串性化的调度，但是缺乏可恢复性和无级联性。可以采用T/O协议的可恢复和可级联扩展方式来使Multi-verison T/O满足可恢复性和无级联性。

8.3 Multi-version Two Phase Locking

多版本两阶段封锁协议将事务分为只读事务和更新事务两种类型。

只读事务开始执行前通过读取ts-counter为当前事务赋予一个时间戳ts，事务READ只读时间戳小于ts的最新数据。

更新事务Ti在执行过程中获得读锁和写锁，遵循rigorous 2PL协议（将所有锁保持到事务提交），对读的数据加共享锁，对写的数据加排它锁。每个更新事务的WRITE(Q)创建一个新版本的Qk，Qk的时间戳设置为∞。事务Ti完成后，提交commit。事务Ti从ts-counter获得时间戳值ts，然后将其创建的Qk的时间戳设置为ts+1，然后将ts-counter的计数值加1。

对于更新事务Ti，在Ti commit之前的只读事务只能看到Ti之前的旧值，而在Ti commit之后的只读事务只能看到Ti更新的值。通过这样的串性调度，保证了multi-version 2PL满足可恢复性和无级联回滚性。

8.4 Multi-version Garbage Collection -- 旧版本数据回收

旧版本删除条件：如果W-timestamp(Qj) < W-timestamp(Qk) < TS(Toldest)，则Qj可以被删除。也就是说如果数据对象Q有两个版本的时间戳小于当前系统的最老事务时间戳，则两版本中更旧的版本可以被删除。

GC有两种方案：

  • Tuple-level GC
  • Transaction-level GC

8.4.1 Tuple-level GC

Tuple-level旧版本数据回收有两种方法：

  • 后台回收（Background Cleaning）：使用一个后台线程周期性检查可回收的版本数据
  • 合作回收（Cooperative Cleaning）：只能使用于oldest-to-newset的version chain中，工作线程在执行事务的遍历version chain的过程中，查找可以被回收的版本数据（几乎没有BDMS使用此种方案）

8.4.2 Transaction-level GC

每个事务追踪其读写数据集合。由DBMS决定哪些完成事务的读写数据集版本是可视的。

8.5 MVCC中的索引管理

在MVCC中，一个逻辑数据对象有多个物理版本，因此在进行tuple插入和删除时，需要额外对index进行操作。Secondary Index的情况更加复杂。

解决方案：

  1. 物理指针：索引中的指针指向version chain的header

  2. 逻辑指针：将指针指向逻辑tuple不会改变的identifier，如图8（MySQL采用）和图9是两种方案。


    图8 Secondary Index使用primary key进行中间转换
图9 使用一个hash表进行映射

通用数据库MVCC实现对比：


图10 通用数据库MVCC实现

9. 快照隔离 -- Snapshot isolation

在快照隔离中，事务获取到数据库的一个快照（形成一个私有空间，类似Optimistic Concurrency Control），。在snapshot isolation中，只读事务不需要等待，每个快照中只包含已提交事务提交的数据值。事务在快照中执行事务操作，然后快照待系统验证后再与数据库系统合并。在验证过程中需要处理事务与其它并发事务的冲突，事务的验证+merge组合操作需要是原子操作，以确保其它事务的快照要么包含本事务所有更新数据，要么不包含任何更新数据。

9.1 Snapshot有效性验证

在snapshot isolation中使用有限性验证机制来解决丢失更新问题（lost update，两个事务都提交对同一数据对象的更新操作时，倒是又一个事务值被覆盖），两种方案：

  • 先提交者获胜（first committer wins）：原子检查是否有并发的事务已经提交对目标数据对象的更新，有则终止，否则本事务提交。
  • 先更新者获胜（fisrt updater wins）：
    • 事务T更新Q时对Q加排它锁
    • 如果获取排它锁，T检查更新操作的有效性。如果Q已经被另一个并发事务更新，则T回滚，否则进行Q更新
    • 如果没有获取排它锁，事务T等待并发事务T'终止或提交

9.2 快照隔离不能保证冲突可串性化

可行的解决方案：

  • 扩展版本的serializable snapshot isolation(SSI)
  • 在数据库系统中允许不同隔离级别的事务同时执行
  • 应用端使用for update语句辅助保证串性性

10. 其他并发控制技术

10.1 几种弱一致性

弱一致性 描述
Degree-Two Consistency 一种read committed的一致性；用以避免事务级联回滚；使用共享锁和排它锁，但是共享锁可以随时释放和重获取，排它锁保持到事务结束；有不可重复度和幻肢问题
Cursor Stability 是Degree-Two Consistency的一种。为使用游标的宿主语言设计，不是锁整个关系，只对游标当前处理的远足加共享锁，读取完毕就释放。对更新的事务就X锁，并保持到事务完成。在relation被频繁存取的场景下可以提高并发度，改善系统性能。

10.2 Online Index Creation -- 在线索引创建

步骤：

  1. 创建relation的快照，index创建基于此快照。同时，所有事务对relation的更新操作记录在日志文件中。
  2. 基于快照的索引创建完成后，读取日志文件中对relation的更新，将日志里的操作在索引中对应更新。
  3. 对relation加共享锁，将步骤二期间的relation更新操作应用到在线创建的索引中。因为加了共享锁，步骤三期间的relation更新操作将被阻塞，但是阻塞的时间很短。

目的：当在线创建relation索引时，仍然允许事务对relation的操作。

10.3 索引高并发操作

B+树：

  1. crabbing protocol
  2. B-link Tree

10.4 考虑操作类型的并发控制

increment lock：用于对数据对象进行增量操作（详情可见《Database System Concepts 7th》Section 18.10.5）

锁兼容矩阵：

shared lock exclusive lock increment lock
shared lock \color{green}{true} \color{red}{false} \color{red}{false}
exclusive lock \color{red}{false} \color{red}{false} \color{red}{false}
increment lock \color{red}{false} \color{red}{false} \color{green}{true}

参考：

CMU 15-445/645 16
CMU 15-445/645 17
CMU 15-445/645 18
CMU 15-445/645 19
《Database System Concepts 7th editon》

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,732评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,496评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,264评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,807评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,806评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,675评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,029评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,683评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 41,704评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,666评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,773评论 1赞 332
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,413评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,016评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,978评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,204评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,083评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,503评论 2赞 343

推荐阅读更多精彩内容

  • 数据库并发控制技术总结
    1.数据库并发控制的作用 1.1 事务的概念 在介绍并发控制前，首先需要了解事务。数据库提供了增删改查等几种基础操...
    AnotherWonder阅读 401评论 0赞 0
  • 2018-07-18 先发影响力
    推荐指数： 6.0 书籍主旨关键词：特权、焦点、注意力、语言联想、情景联想 观点： 1.统计学现在叫数据分析，社会...
    Jenaral阅读 5,700评论 0赞 5
  • 汽车追尾以后
    昨天，在回家的路上，坐在车里悠哉悠哉地看着三毛的《撒哈拉沙漠的故事》，我被里面的内容深深吸引住了，尽管上学时...
    夜阑晓语阅读 3,777评论 2赞 9
  • 正则表达式
    一。匹配。 判断一个字符串是否符合我们制定的规则？ 二…捕获 字符串中符合我们正则表达式，规则的，内容捕获到。 三...
    时修七年阅读 973评论 2赞 0
  • 我的城，死于一场没有归来的等待
    城空了，有树长出来 我的城死了 铸起它的人，杀死它的人 不愿因为这件事而骄傲 一座城的终结 永远因为终结这件事而显...
    于十六阅读 2,847评论 6赞 17