乐观并发控制技术

时间戳

由数据库创建的用于标识事务串行化顺序的标识符，用TS(T)表示事务T的时间戳。

可以使用物理时钟和逻辑时钟（计数器类似于LSN）

事务和数据项都有时间戳

时间戳排序协议

是一种并发控制协议，主要用于数据库系统中的事务管理。其核心思想是通过给每个事务分配一个时间戳，并根据时间戳的顺序来决定事务操作的执行顺序，从而确保事务的正确性和一致性。

对于任意事务(按照所在事务的时间戳排序执行)：

  • 只能读 之前事务 写的数据
  • 只能写 之前事务 读写的数据
  • 时间戳排序协议可以产生冲突可串行化调度

每当一个事务对某个数据项进行写操作时，这个数据项的时间戳会被更新为该事务的时间戳。即，数据项的时间戳始终反映最后修改该数据项的事务的时间顺序。

  • W_TS(X)：对 X 成功执行写操作的所有事务的最大时间戳
  • R_TS (X)：对 X 成功执行读操作的所有事务的最大时间戳

具体行为

读操作，当事务T开始读取

  • 若TS(T) < W_TS(X)：即事务T要读取的X值被 未来事务 修改（被新值覆盖）。避免脏读，回滚事务T。
  • 若TS(T) ≥ W_TS(X)：即事务T要读取的X值没有被覆盖过，可读取，并更新R_TS(X)数据项的时间戳，R_TS(X) = max(R_TS(X), TS(T))

写操作，当事务T开始写入

  • 若TS(T) < R_TS(X)：则数据项X的当前值已经被其他 未来事务 读取过，会导致 不可重复读，回滚
  • 若TS(T) ≥ R_TS(X)
    • 若TS(T) < W_TS(X)：当前数据项X是 被其他 未来事务 修改过，写入会导致 旧值覆盖新，回滚。
    • 若TS(T) ≥ W_TS(X)：当前数据项X可以写入，更新W_TS(X) 更新为 TS(T)

回滚操作，回滚事务T（需要记录修改之前的时间戳和值）

  • T读的数据项X（满足TS(T) = R_TS(X) 的数据项X）：恢复读之前的R_TS(X)。
  • T写的数据项X（满足TS(T) = W_TS(X) 的数据项X）：恢复写之前的R_TS(X)，恢复X值。

缺陷

时间戳排序协议中因无效写操作而产生的不必要回滚问题。

盲写： 是指一个事务在没有读取数据项当前值的情况下直接对其进行写操作。

盲写在时间戳协议中也是会被回滚的，然而实际上是没有必要的。因此引入托马斯写规则。

托马斯写规则

托马斯写规则通过允许忽略那些无效的写操作（即时间戳较小的写操作覆盖了已被后续事务修改的数据项），从而避免了不必要的回滚。

写规则行为

写操作，当事务T开始写入

  • 若TS(T) < R_TS(X)：则数据项X的当前值已经被其他 未来事务 读取过，会导致 不可重复读，回滚
  • 若TS(T) ≥ R_TS(X)
    • 若TS(T) < W_TS(X)：当前数据项X是 被其他 未来事务 修改过，直接忽略这次写操作
    • 若TS(T) ≥ W_TS(X)：当前数据项X可以写入，更新W_TS(X) 更新为 TS(T)

满足视图可串行化，证明：

托马斯写规则规定，如果一个事务T1尝试对数据项X进行写操作，而T1的时间戳小于当前已经发生的写操作的时间戳，那么T1的写操作会被丢弃。只有当T1的时间戳大于当前最新的写操作的时间戳时，T1的写操作才会生效。

为什么丢弃的写操作不会影响读操作：

丢弃的写操作意味着该事务T1的写操作在当前时间点并没有产生任何实际的数据库状态改变。这是因为按照时间戳顺序，后续有事务T2已经对X进行了有效的写操作，因此T1的写操作“被视为无效”或“不会影响数据库状态”。

当事务T2进行读操作时，T2会读取数据库中数据项X的最新值，而这个最新值是按照时间戳顺序计算的。即使T1的写操作被丢弃，只要T1的写操作的时间戳小于T2的时间戳（即它是被丢弃的），T2会读取到一个由T2或更早的事务所写入的值。

隔离级别

通过时间戳来支持不同的隔离级别，包括读已提交、可重复读和可串行化：

  • 支持可重复读：缓存第一次读取的数据，避免不可重复读
  • 解决幻读问题：修改时间戳，避免读取新插入和新删除的数据（即忽略时间戳大于事务时间戳的数据项。

问题

产生不可恢复调度和级联回滚问题：

不可恢复调度是指当一个事务已经提交，而它依赖的数据却由另一个还未提交的事务所产生时，这会导致数据不一致的风险。

  • 原因：在时间戳排序协议中，事务的读操作可以基于时间戳直接访问数据项，而不考虑其他事务是否已经完成。例如，事务T2可能读取了事务T1写入的数据项，但如果T1最终因为冲突而被中止或回滚，T2读取的数据就变成了无效数据（脏读）。
  • 举例：假设T1写入了数据项X，然后T2读取了X的值。随后T1由于某种原因回滚了，但T2却已经提交了，这样T2的结果基于一个不存在的或已撤销的数据版本，从而导致不一致的状态。

级联回滚指的是一个事务的回滚可能导致多个依赖该事务的其他事务也必须回滚，从而引发一连串的回滚操作。

  • 原因：时间戳排序协议允许事务立即读取数据项的最新版本，而不等待写入操作的提交，这就导致了潜在的依赖关系。例如，如果事务T1写入数据项X后被回滚，而事务T2和T3都读取了T1写入的X，那么T1的回滚将迫使T2和T3也要回滚，因为它们读取了无效的数据。
  • 举例：假设T1写入了数据项X，然后T2、T3相继读取了X的值。如果T1因为冲突而回滚，那么T2和T3的数据基于已撤销的X，也必须回滚。这样，T1的回滚会引发T2和T3的回滚，造成级联回滚。

解决：

为了保证可恢复调度和无级联回滚，可以修改时间戳排序协议：

  • 支持可恢复调度：如果事务T读取了其他事务所写的数据项，那么只有在T依赖的其他写事务提交之后，事务T才能提交。这样可以保证可恢复调度，但不是保证无级联回滚
  • 支持无级联回滚：如果事务T要读取其他未提交事务所写的数据项，那么T必须阻塞，必须等待写该数据项的事务提交后才能读取。这样可以保证可恢复调度和无级联回滚，需要锁机制才能阻塞T，因此要结合其他技术

严格时间戳排序协议

是一种基于时间戳的并发控制协议，它对事务操作顺序进行了更为严格的控制，以保证数据库系统的一致性和事务的隔离性。

与普通时间戳排序协议不同，严格时间戳排序协议要求所有事务的操作（读和写）都必须遵循时间戳顺序，严格禁止事务发生“过早的读”或“过晚的写”现象。

具体行为

读操作，当事务 T 开始读取数据项 X 时：

  • 若 TS(T) < W_TS(X)：即事务 T 要读取的数据项 X 的值被未来事务修改，可能会导致脏读。事务 T 被回滚。
  • 若 TS(T) ≥ W_TS(X)：即事务 T 要读取的数据项 X 的值未被未来事务修改，可以读取数据，并更新 R_TS(X) 数据项的时间戳为 max(R_TS(X), TS(T))，表示此读操作的时间戳。

写操作，当事务 T 开始写入数据项 X 时：

  • 若 TS(T) < R_TS(X)：即数据项 X 的当前值已经被其他未来事务读取过，写操作可能会导致不可重复读。事务 T 被回滚。
  • 若 TS(T) ≥ R_TS(X)：
    • 若 TS(T) < W_TS(X)：即当前数据项 X 已被其他未来事务修改，写操作会覆盖新值，导致冲突，事务 T 被回滚。
    • 若 TS(T) ≥ W_TS(X)：即当前数据项 X 可以进行写操作，更新 W_TS(X) 为 TS(T)，表示此事务已经成功写入数据项 X。

回滚操作，回滚事务 T 时：

  • 对于事务 T 读的数据项 X（满足 TS(T) = R_TS(X) 的数据项 X）：恢复读操作之前的 R_TS(X)。
  • 对于事务 T 写的数据项 X（满足 TS(T) = W_TS(X) 的数据项 X）：恢复写操作之前的 W_TS(X)，并恢复 X 的值。

严格时间戳排序协议的特性

  • 严格时间戳排序协议通过对事务操作的严格顺序控制，确保了数据库的冲突可串行化。
  • 通过比较事务的时间戳，确保了所有的事务都按照时间顺序进行操作，禁止了任何可能导致不一致的读写行为。
  • 相比普通时间戳排序协议，严格时间戳排序协议对事务的控制更加严格，以避免出现更多可能导致事务冲突的情况。

事务提交与回滚

  1. 事务 T 提交：
    • 对于事务 T 提交的所有数据项 X，更新 isCommit(X) 为真，表示这些数据项已提交。
    • 通知等待该数据项 X 的其他事务继续进行。
  2. 事务 T 回滚：
    • 对于事务 T 回滚的所有数据项 X，设置 isCommit(X) 为假，表示这些数据项未提交。
    • 根据回滚后的事务状态，通知等待该数据项 X 的其他事务继续执行。

存在的问题：

饿死：短事务与某个较早但执行时间长事务冲突，长事务不断重启导致饿死。

如果某个事物反复重启就暂停冲突的其他事务，先让这个事务完成。

乐观并发控制协议

验证阶段保证调度可串行化

单独的工作区保证调度是可恢复的

适用于事务冲突较少，执行时间较短。

一共将事务分成三个阶段：

  • 读阶段：这个阶段，当数据需要读取数据时，将数据库中的数据进行拷贝到自己隔离的事务工作区，在自己的副本上进行修改和读取。
  • 验证阶段：看自己的工作区副本修改是否与数据库当前满足所需的隔离级别关系，如果不满足，则事务重做，否则进入写阶段
  • 写阶段：将私有工作区中的副本更新到数据库中（私有工作区保证调度是可恢复的、无级联回滚的）

乐观并发控制协议通过让事务“拷贝”数据进行修改，再通过验证冲突的方式来避免并发冲突，从而减少了传统锁机制带来的开销。

验证阶段

以下详解验证阶段：

  • 反向验证：验证当前事务与已提交的事务是否存在冲突
  • 正向验证：验证当前事务是否与未提交的事务之间存在冲突

验证方法：

每个事务有5个时间戳，两个区间：

  • StartTime(T)：事务开始执行的时间。
  • ReadTime(T)：读阶段开始的时间，即事务开始读取数据的时刻。
  • ValidationTime(T)：验证阶段开始的时间。在此时，系统检查事务是否与其他事务发生冲突，并决定事务是否可以提交。
  • WriteTime(T)：写阶段开始的时间，即事务开始将修改后的数据写入数据库的时刻。
  • CommitTime(T)：事务结束并提交的时间，即写阶段结束并将事务数据提交到数据库的时刻。
  • WriteSet(T)：写阶段的数据项集合
  • ReadSet(T)：读阶段的数据项集合

事务的时间戳通常取为验证阶段开始的时间。TS(T) = ValidationTime(T) （因为事务可能会在验证阶段发生重启，因此真正决定事务执行的先后顺序通常是根据验证阶段的开始时间来确定的。）

读操作验证：验证事务读取值 = 当前数据库值

写操作验证：当前事务T是否与已经提交的事务T‘存在读写（T’先写T后读）、写读（T’先读T后写）、写写冲突见下方。

有效性验证方法对写操作的验证：

四条规则，满足一条则没有写写冲突

  1. 事务 T’ 提交时间小于事务 T 读阶段的开始时间
    • CommitTime(T’) < ReadTime(T)
    • 意义：如果事务 T’ 已经提交，并且它的提交时间早于事务 T 开始读取数据的时间，说明事务 T’ 对数据的修改早于事务 T 读取数据。因此，不会发生写写冲突，事务 T’ 对数据的修改已经被“消化”，事务 T 不会读取到未提交的修改，验证通过。
  2. T’所写的数据项不会被T读取且T’在T开始写入阶段前已完成写入
    • WriteSet(T’) ∩ ReadSet(T) = ∅ and CommitTime(T’) < WriteTime(T)
    • 意义：第一个条件保证不存在 T 读取 T′ 写入数据的情况，第二个条件保证不存在 T′ 读取 T 写入数据的情况。
  3. T’所写的数据项不会被T读取也不会被T写入，且T’在T完成读阶段前完成读阶段
    • WriteSet(T’) ∩ ReadSet(T) = ∅ and WriteSet(T’) ∩ WriteSet(T) = ∅ and ValidationTime(T’) < ValidationTime(T)
    • 意义：T’和T没有读写和写写冲突（条件1）没有写读冲突（条件2）
  4. T′ 所写的数据项和 T 读写的数据项没有交集且 T 所写的数据项和 T′ 读写的数据项没有交集
    • WriteSet(T’) ∩ ReadSet(T) = ∅ and WriteSet(T’) ∩ WriteSet(T) = ∅ and ReadSet(T’) ∩ WriteSet(T) = ∅
    • 意义：两者没有读写，写写，写读冲突。

乐观并发协议控制对比

  • 时间排序协议：事务每做一个操作，就会根据协议规则进行一次判断，使事务回滚或者继续运行，不可恢复的。
  • 乐观控制并发协议：一个事务执行完所有操作后，再根据规则判断事务提交或回滚，减少判断此时，减少开销，导致一些完整执行的事务被回滚，开销大，适合事务短，冲突少。
  • 两者都会事务饿死（频繁重启）

多版本机制

概述

多版本并发控制：对一个数据项保存多个物理版本，供不同的事务使用

  • 事务对数据项进行写操作时，产生该数据项的一个新版本
  • 事务对数据项进行读操作时，读取事务开始时该数据项的最新版本

不同点

  • 乐观并发控制技术使用时间复用并发控制
  • 多版本机制通过空间复用实现高并发控制

优点

  • 事务的读操作无需等待其他事务的写操作
  • 事务的写操作无需等待其他事务的读操作

多版本时间戳排序协议

每个事务在开始执行前有唯一的时间戳TS(Ti)

每个数据有多个物理版本，X0, X1, X2 … Xm。每个版本有三个数据：

  • 版本值
  • W_TS(Xi)：产生该版本的事务时间戳
  • R_TS(Xi)：成功读取该版本的事务的最大时间戳

具体行为

  • 当事务T对X进行成功写操作：数据库产生该数据项的新版本Xm+1，记录新值，初始化其W_TS和R_TS为事务T的时间戳
  • 当事务T成功读取Xm，且R_TS(Xm) < TS(T)，则更新R_TS为T的时间戳。
  • 每个事务T对于数据项X，不超过T时间戳的最大X创建时间为最新版本。

协议规则

以下定义X为对于事务T的最新数据项版本：

如果事务T读X数据项：返回最新版本的值

如果事务T写X数据项：

  • TS(T) < R_TS(X) ，事务T回滚
  • TS(T) = W_TS(X)，允许覆盖X的值
  • TS(T) > R_TS(X)，产生新版本X‘，并初始化版本三字段。

说明：

  • 如果时间戳大的事务已经读取过该版本X了，如果事务T对X进行修改，会造成时间戳小的事务在时间戳大的事务之后修改数据项，会违反可串行化调度。如果时间戳大的事务再次读取该数据项X会造成不可重复读。
  • X数据项版本就是由T产生的
  • 检查在W_TS(X)和TS(T)，中是否有其他事务修改X。没有则写成功，否则回滚。

优势

  • 读操作无需等待，必定成功
  • 写操作新建版本，不堵塞其他事务读取，提高并发

劣势

  • 读会更新R_TS，两次磁盘读写
  • 冲突通过回滚解决，开销大
  • 同时间戳排序，不保证可恢复性

多版本两阶段锁协议

集合多版本思想和两阶段锁机制思想：多版本提高读的并发，锁解决写写冲突。

数据定义

版本有两个值：

  • 版本值
  • 产生版本时间戳

事务包含时间戳，分两类：

  • 只读事务：只有读操作
  • 更新事务：有写操作

协议规则

对于只读事务，根据时间戳读取事务开始的最新版本，不需要锁机制。

对于更新事务，介绍两种方法。

更新事务协议一

读操作不加锁，写操作加严格两阶段锁。对事务T和数据项X，设X为时间戳不超过T时间戳的最大版本。

  • 如果事务T对数据项X只进行读操作，则数据库返回数据项X的值
  • 如果事务T对数据项X进行写操作，为X创建一个新版本，并对其加互斥锁，即同时只能创建一个新版本。如果事务T成功提交，则将该新版本时间戳设置为TS(T)；如果事务回滚，删除该新版本。

不满足可串行化，隔离级别为快照隔离。快照一旦建立不会修改，起隔离作用。

更新事务协议二

读写操作都加严格两阶段锁。为了解决方法一不满足可串行化的问题，对读操作加共享锁，对写操作加互斥锁，从而实现可串行化。

  • 快照读：根据时间戳找到小于事务时间戳的最新版本，快照读一般用于只读事务，对读写无影响的事务。
  • 当前读：读取最新版本并加锁来实现并发读写。有共享锁和互斥锁。
  • 如果根据读写操作简单的加共享锁和互斥锁就退化成了基于两阶段锁的并发控制协议。为了解决这一问题，一些数据库通过添加两类SQL语法来对select操作指定共享锁还是互斥锁。这需要SQL开发者了解数据访问需要加共享锁还是互斥锁，选用合适的select语法，从而提升事务处理的性能

select for share：指定共享锁

select for update：指定互斥锁

select：快照读，不加锁

多版本乐观并发控制协议

结合了多版本思想和乐观并发控制机制

事务：

  • BeginTS：开始执行得到的时间戳
  • CommitTS：提交时得到的时间戳

数据项：

  • begin-ts：起始时间戳
  • end-ts：终止时间戳

读阶段

  • 记录事务读取的数据项（读集）、写入的数据项（写集）和多次进行的扫描（扫描集）
  • 完成事务中的数据操作，获得一个结束时间戳

验证阶段

  • 在结束时间戳时刻，验证读集中数据项的版本是否仍然可见，避免脏读、不可重复读问题
  • 重新执行扫描集，检查结果是否相同，避免幻读问题
  • 验证通过后，获得CommitTS进行下一阶段，否则撤销并重启

写阶段

  • 创建写集中数据项的新版本，该版本的begin-ts为该事务的CommitTS，将新版本写回数据库
  • 删除写集中数据项的有效的旧版本，即使旧版本的end-ts为该事务的CommitTS
  • 写写冲突：如果多个事务在同一数据项上进行更新操作，那么第一个获得写入权限的事务进行更新，其他事务被撤销并重启

版本存储

每个逻辑行拥有版本链表，存储若干个版本

仅追加存储

所有版本存储在一个表空间中，一个数据项拥有一个链表，所有的数据项版本在一个表，同一个数据项通过链表指针连接在一起。

组织版本链表的两种顺序：

  • 从旧到新：记录最早版本，每次从头结点找到目标版本。
  • 从新到旧：一边插入一边更新索引指针。

缺点：多版本信息被存储，一直增长，老版本数据淘汰时要遍历数据。

回滚段存储

老版本移动到一个单独的空间存储，新版本存储在原数据空间。

索引指向逻辑行地址。每个逻辑行有一个指针指向回滚段表空间，其存储若干个旧版本。

产生新版本时，将旧版本复制到回滚段段表空间，同时将最新版本存储在当前空间中。

差异存储

一条记录可能包含多个属性，一次数据更新可能只修改一小部分属性。上述两种策略需要将所有属性的数据存在老版本中，造成了空间浪费

差异存储在产生新版本时，将数据项修改的部分内容存储到差异存储表中，同时更新主表

减少写操作时的数据复制量，提高系统的写性能

读旧版本数据时，通过差异内容得到，降低读性能

版本删除

物理删除

释放占用的物理空间

  • 对于数据项X的两个版本X1和X2，其创建时间W_TS(X1) < W_TS(X2) ，且都小于当前系统中最老的事务时间戳，可删除X1
  • 删除已撤销的事务产生的版本

逻辑删除

标记已删除的数据项

  • 删除标识：用标识表示数据项被逻辑删除，该标识存放于行的头部或单独的一列中
  • 墓碑数据：产生一个空的版本来表示数据项被逻辑删除。实际中，在版本链表的指针中用一个特殊的比特位来表示墓碑数据以节省空间

行级别回收

针对行直接进行垃圾回收

  • 后台回收：后台定期查找可回收的版本，适用于所有版本存储策略
  • 合作回收：在遍历版本链表时找过期的版本数据并删除，只可用于从就到新的版本存储策略。

事务级别回收

每个事务记录其读取和写入的数据版本。数据库系统判定已完成事务产生的版本何时不再有效，并进行回收

多版本机制中的索引管理

  • 逻辑指针：为每行设置一个识别标识，存储该行对应的主键信息。通过此标识获取主键索引。主键索引保存了指向版本链表的物理指针，因此间接得到该行对应的版本。
  • 物理指针：直接存储指向版本链表的物理指针

1.png

多版本机制的实际应用

数据库 并发控制协议 版本存储 垃圾回收 索引
Oracle MV2PL 回滚段, 差异存储 后台回收 逻辑索引
Postgres MV2PL/MVTO 追加存储 后台回收 物理索引
MySQL-InnoDB MV2PL 回滚段, 差异存储 后台回收 逻辑索引
Hekaton MVOCC 仅追加存储 合作回收 物理索引
MemSQL MVOCC 仅追加存储 后台回收 物理索引
SAP HANA MV2PL 回滚段存储 混合 逻辑索引
NuoDB MV2PL 仅追加存储 后台回收 逻辑索引
HyPer MVOCC 差异存储 事务级别回收 逻辑索引
GaussDB MV2PL 回滚段存储 混合 逻辑索引

并发控制协议比较

2.png

  • 基于悲观锁的协议：当事务冲突时，通过锁等待读写的资源，可以实现各种隔离级别，不会饿死长事务，但可能存在死锁问题。其中2PL调度不可恢复，而S2PL和SS2PL调度可恢复，因此数据库一般采用S2PL。该协议适合事务冲突较多的场景。
  • 基于时间戳的协议：当事务冲突时，通过回滚事务解决冲突，可以实现各种隔离级别。由于频繁回滚会饿死长事务，不会存在死锁问题。存在不可恢复、级联回滚问题。
  • 基于乐观锁的协议：当事务冲突时，通过重启事务解决冲突，可以实现各种隔离级别。由于频繁回滚会饿死长事务，不会存在死锁问题。该协议适合事务冲突较少的场景。
  • 基于多版本的协议：通过空间复用的多版本信息缓解读写冲突，再结合上述三种协议可以提升事务并发处理效率。