数据库概论.陈立军.07.并发控制(4)

Posted on Edited on In Views:
并发控制

并发控制

  • 传统的数据库，Oracle、SQL Server 都是基于封锁来实现的，但是也有其他的并发控制方式

基于时间戳的协议

  • 时间戳
    • 每个事务 Ti 进入系统被分配一个时间戳 TS(Ti)
    • 如果 Tj 晚于 Ti 进入系统，TS(Ti)<TS(Tj)
    • 回滚的事务重新启动，分配新的时间戳
  • 时间戳顺序决定了串行化顺序，回滚违反发出串行性操作的事务
    • 整个调度必须和按照他们的时间戳顺序的串行调度等价
    • 检测冲突，一旦检测到冲突，则按照上述规则回滚某个事务
  • 每个数据项Q有两个时间戳与之联系
    • 数据项上的读写时间戳，数据项上的读写时间戳是所有操作该数据项的事务中最大的时间戳
    • WT(Q)：执行 write(Q) 的事务中最大的时间戳
    • RT(Q)：执行 read(Q) 的事务中最大的时间戳

问题

可能的脏读

  • start1, w1(R), start2, r2(R), abort_t1
  • T1 事务回滚了，T2 事务读到的 R 是 T1 写的 R，是脏读（不是正确的数据项）
  • 解决方案：为每一个数据项设置一个提交位
    • 提交位 C(R)：拥有 R 上写时间戳的事务是否提交
    • r2(R) 发现 R 上的提交位没有被设置为 1（尚未被提交），此时等待

跳过的写

  • start1, start2, w2(R), w1(R)
    • 与时间戳顺序等价的串行调度为：start1, start2, w1(R), w2(R)
    • 于是最后会检测到 w1(R) 不满足时间戳的协议，回滚掉事务 T1
  • 实际上我们没有必要回滚事务 T1，把 w1(R) 忽略掉即可
    • 满足时间戳的串行调度，w1(R) 在前面也会被覆盖，因此只需要把 w1(R) 忽略即可
Thomas 写规则
  • 写操作在更晚的写操作已经发生时可以跳过

执行时间戳协议

读操作

  • 假定事务 Ti 发出 read(Q)
过晚的读
  • 本来应该是在别人写之前读，但是别人写完你才读
  • 如果 TS(Ti)<WT(Q)，则 Ti 需读入的值已经被覆盖，read 操作被拒绝，回滚 Ti
  • start1, start2, w2(R), r1(R)
    • 此时 r1(R) 已经违反了时间戳协议，回滚事务 T1
正常的读
  • 正常的读 TS(Ti) \(\ge\) WT(Q)
  • 若 C(Q) 为真则执行 read 操作，RT(Q) = max(RT(Q),TS(Ti))，若为假则推迟到 C(Q) 为真或写 Q 的事务中止
  • start2, start1, w2(R), r1(R)

写操作

  • 假定事务 Ti 发出 write(Q)
过晚的写
  • 本来应该是在别人读之前写，但是别人读完你才写
  • 如果 TS(Ti)<RT(Q)，则 Ti 产生的 Q 值是先前所需要的值，write 操作被拒绝，回滚Ti
  • start1, start2, r2(R), w1(R)
    • 此时 w1(R) 不满足时间戳协议，回滚事务 T1
正常的写
  • 正常的写：TS(Ti) > RT(Q)
  • TS(Ti) > RT(Q)，并且 TS(Ti) > WT(Q)，执行write操作，WT(Q)＝TS(Ti)
  • start1, start2, start3, r1(R), w2(R), w3(R)
忽略的写
  • Thomas 写规则
  • TS(Ti) > RT(Q)，但是TS(Ti) < WT(Q)，跳过 write 操作
  • start1, start2, start3, w2(R), r3(R), w1(R)
  • 跳过 w1(R) 操作

一个例子

T1 T2 T3 A B C
200 150 175 RT=0
WT=0		 RT=0
WT=0		 RT=0
WT=0
r1(B) RT=200
r2(A) RT=150
r3(C) RT=175
w1(B) WT=200
w1(A) WT=200
w2(C) RT=0 过晚的写
回滚T2
中止
w3(A) 忽略的写

有效性检查协议

  • 把事务的过程分为 3 个阶段
    • 读阶段、有效性检查阶段、写阶段

三阶段

读阶段

  • 事务 Ti 在这一阶段中执行

  • 各数据项值被读入并保存在 Ti 的局部变量中

  • 所有 write 操作都是对局部临时变量进行的，并不对数据库进行真正的更新

有效性检查阶段

  • Ti 进行有效性检查，通过与其他事务的读写集合进行比较，来判定是否可以将 write 操作所更新的临时局部变量值拷入数据库而不违反可串行性

写阶段

  • 若 Ti 通过有效性检查，则进行实际的数据库更新，否则 Ti 回滚

三个时间戳

  • 每个事务 Ti 有 3 个时间戳与之联系
    • Start(Ti)：Ti 开始执行的时间
    • Validation(Ti)：Ti 进入其有效性检查阶段的时间
    • Finish(Ti)：Ti 完成其写阶段的时间
  • 令TS(Ti) = Validation(Ti)，等价的串行顺序与有效性确认时间戳一致

违反串行性的情况

规则 1

  • \({\color{red}\mathrm{if}}\;\mathrm{finish(U)>start(T)}\;{\color{red}\mathrm{then}}\;\mathrm{RS(T)\bigcap WS(U)=\Phi}\)
  • 避免过早地读

规则 2

  • \({\color{red}\mathrm{if}}\;\mathrm{finish(U)>validation(T)}\;{\color{red}\mathrm{then}}\;\mathrm{WS(T)\bigcap WS(U)=\Phi}\)
  • 避免过早的写

一个有效性检查的例子

  • 确认T2：在T1完成写入之前开始，可能先于T1的写入进行读写，需要判断T1的写集合与T2读集合的相交性，同时判断T1的写集合与T2的写集合的相交性
    • 写判断，防止 T2 的写在 T1 之前
  • 确认T3：在T1完成写入之后开始，不需要判定T3和T1的相交性；在T2完成写入之前开始，需要判断T2的写集合与T3读集合的相交性；T2在T3确认前完成，不需要判定T3的写集合和T2的写集合的相交性

例子2

  • 确认 U
    • 最早的确认，通过
  • 确认 T
    • U 写、T 读：通过
    • U 写、T 写：通过
  • 确认 V
    • U 写、V 读：通过
    • T 写、V 读：通过
    • T 写、V 写：通过
  • 确认 W
    • W 读之前，U 已经 finish，不需要比较
    • T 写、W 读：未通过
    • V 写、W 写：通过
    • V 写、W 读：未通过

MVCC

  • MVCC：Multiple Version Concurrent Control
  • 以下是 MySQL 对于 MVCC 的实现

MySQL 一致性非锁定读

  • 一致性非锁定读（consistent nonlocking read）
  • 多版本实现的并发控制

说明

  • 在 read committed 和 repeatable read 下 InnoDB 使用非锁定的一致性读
  • read committed 的非一致性读总是读取被锁定行的最新一份快照数据
    • 语句开始的版本
  • repeatable read 的非一致性读总是读取事务开始时的行数据版本

三个隐藏列

  • InnoDB 为每行数据增加三个隐藏列用于实现 MVCC
  • DB_TRX_ID
    • 插入或更新行的最后一个事务的事务标识符（删除视为更新，将其标记为已删除）
  • DB_ROLL_PTR
    • 写入回滚段的撤消日志记录（若行已更新，则撤消日志记录包含在更新行之前重建行内容所需的信息）
    • 将所有的老版本通过一个指针串起来
  • DB_ROW_ID：行标识（隐藏单调自增id）
  • 快照存放在日志 undo 段中
  • InnoDB 新版本的数据是叶子结点的值，老版本的数据则通过 UNDO 记录存储在回滚段（Rollback Segment）中

可见性算法

  • read-view：事务在进行快照读的时候会创建一个读视图
  • 在执行读操作的时候，基于读视图判定当前行对于读操作是否可见
  • 一些数据段
    • alive_trx_list：读视图生成时刻系统中正在活跃的事务 id
    • up_limit_id：记录上面的 alive_trx_list 中的最小事务 id（最老的事务）
    • low_limit_id：读视图生成时刻，目前已出现的事务 ID 的最大值 +1
  • 判定
    • 判断这条记录的 DB_TRX_ID 是否是小于 up_limit_id 或者等于当前事务 id
      • 若是，则当前事务能看到这条记录
    • 判断这条记录的 DB_TRX_ID 是否大于等于 low-limit-id
      • 如果大于等于则说明此事务无法看见该条记录
    • 判断该条记录的 DB_TRX_ID 是否在活跃事务的数组中
      • 如果在则说明这条记录还未提交，对于当前操作的事务是不可见的
      • 如果不在则说明已经提交，则是可见的
        • 这种情况是当前事务一开始之后很短的时间内，开始后很快就提交了

  • 对于 read committed 来说，每读一次都会生成新的读视图
  • 对于 repeatable read 来说，读视图时是事务一开始就确定不变的

PG 与 MySQL 写操作的不同

  • PG 对写操作也是乐观并发控制
    • 在表中保存同一行数据记录的多个不同版本，每次写操作，都是创建，而回避更新
      • PG 有表膨胀的问题
      • MySQL 把老版本放在回滚段里
    • 在事务提交时，按版本号检查当前事务提交的数据是否存在写冲突，抛异常告知用户，回滚事务
  • innodb 只对读无锁，写操作仍是上锁的悲观并发控制
    • 每行数据只在表中保留一份，在更新数据时上行锁，同时将旧版数据写入 undo log
    • 表和 undo log 中行数据都记录着事务 ID，在检索时，只读取来自当前已提交的事务的行数据

SQL Server 中查看多版本

  • tempdb

1
2
3
4
5
6
7
8
alter database ljchen
set allow_snapshot_isolation on

update faculty
set salary=salary*1.01

select COUNT(*)
from sys.dm_tran_version_store

MVCC 论文

  • An Empirical Evaluation of In-Memory Multi-Version Concurrency Control
  • 设计要点
    • 并发控制 (ConcurrencyControl)
    • 版本存储 (VersionStorage)
    • 垃圾回收 (GarbageCollection)
    • 索引管理 (Indexmanagement)

MySQL 一致性锁定读

1
2
3
4
5
/* 对读取的行加 X 锁 */
select ... for update

/* 对读取的行加 S 锁 */
select ... lock in share mode