事务是访问并可能更新各种数据项的一个程序执行单位
ACID: 原子性, 一致性, 隔离性, 持久性
数据库并发控制管理部件负责处理并发控制机制

原子性和持久性

[1] 保持原子性的基本思路: 在磁盘日志记录要执行写操作的数据项的旧值

[2] 达到持久性:

• 事务做的更新在事务结束前已经写入磁盘
• 事务已执行的更新信息写到磁盘, 数据库在系统出现故障后重新启动时重新构造更新

[3] 事务的状态: 活动, 部分提交, 失败, 中止, 提交
中止事务对数据库所做的任何改变必须撤销, 此外:

• 如果引起中止的是硬件错误或者不是内部逻辑产生的软件错误, 采用重启新的事务
• 如果引起中止的是内部逻辑错误/输入错误/所需数据没有在数据库中找到, 采用杀死事务

隔离性和可串行化

[1] 事务的并发执行

• 提高事务吞吐量和系统利用率: I/O和CPU并行运作, 给定时间内执行事务数增加, 处理器和磁盘利用率提高
• 减少事务等待时间: 共享CPU周期和磁盘存取, 减少一个事务从提交到完成所需要的平均响应时间

[2] 多个事务并发执行, 数据一致性可能不再维持, 但是事务的串行执行能保证一致性

[3] 调度捕获影响事务并发执行的关键操作(read/write), 忽略事务执行的内部细节
调度的执行效果等价于按照某种串行执行的效果——可以通过并发控制机制保证可串行化
不是所有的串行调度相互之间都冲突等价

[4] 通过为调度构造优先图, 搜索是否无环判断是否冲突可串行化
有环: 非冲突可串行化
深度优先搜索检测环是否存在: n^2数量级, 其中n为事务数

可恢复调度和无级联调度

[1] T2读取T1写入的值——T2依赖于T1
T1提交前发生故障, 但是T7已提交, 不能终止, 因此不可恢复
只有T1比T2先提交, 才是可恢复调度
调度必须可恢复: 若a看到b的影响, b中止时a也要中止

[2] 调度最好无级联: 通过只允许事务读取已提交数据保证, 不会由于一个事务中止引起其他事务级联中止
每一个无级联调度都是可恢复调度

隔离性级别及其实现

[1] 隔离性级别

[2] 并发控制机制: 延迟一个操作或者中止发出该操作的事务

锁

[1] 共享锁(S): T可以读但不能写Q
排他锁(X): T既可以读也可以写Q

[2] 让事务在对数据项最后一次访问后立即释放锁未必可去, 因为有可能不能保证可串行性

[3] 如果有连续的共享锁, 那么将一直不能在该数据项加排他锁, 导致饿死
避免方法:当事务T申请对数据项Q加M型锁时, 并发控制管理器授权加锁的条件是:

• 不存在Q上持有与M冲头的锁的其他事务
• 不存在等待对Q加锁, 且先于T申请加锁的事务

两阶段封锁协议

[1] 增长阶段: 事务可以获得锁, 但不能释放锁
缩减阶段: 事务可以释放锁, 但不能获得新锁

[2] 严格两阶段封锁协议要求事务持有的所有排他锁必须在事务结束时才释放 (保证结果调度的可恢复性和无级联性)
强两阶段封锁协议要求事务持有的所有锁必须在事务结束时才释放

[3] 锁转换

• 升级: 共享转化为排他, 只能发生在增长阶段
• 降级: 排他转化为共享, 只能发生在缩减阶段

[4] 广泛使用的机制

1. 事务进行read操作, 系统产生lock-S指令在read前
2. 事务进行write操作, 检查T是否已经在Q上有共享锁, 有则upgrade / 否则lock-X在write前
3. 事务提交或中止后, 所有锁都被释放

[5] 锁管理器: 针对锁请求消息返回授予锁消息, 或者发生死锁时要求事务回滚
针对解锁消息返回确认, 并触发为其他等待事务的授予锁消息

[6] 锁表为每一个数据项维护一个链表, 每一个请求为链表中的一条记录, 按照请求到达的顺序排序
使用数据项名称为索引的散列表查找链表中的数据项
记录: 提出请求的事务, 请求锁的类型, 是否已经授予锁, 基于事务标识符的索引(用于确认给定事务持有的锁集)

基于图的协议/树形协议

[1] 前提: 访问数据项的顺序

[2] 使用有向无环图/树

1. 首次加锁可以对任意数据项进行, 解锁可以随时进行
2. T对Q加锁的前提是持有Q的父项的锁
3. 数据项被T加锁并解锁后, T不能再对数据项加锁

[3] 保证可恢复性和无级联回滚: 将协议修改为在事务结束前不允许释放排他锁——降低并发性

[4] 只保证可恢复性: 为每一个发生未提交写操作的数据项, 记录哪个事务最后对它执行了写操作
事务T执行了对未提交数据项的读操作, 就在(最后对该数据项执行了写操作的)事务上记录一个T的提交依赖
在有T的提交依赖的所有事务完成之前, T不得提交; 如果任何一个事务中止, T也必须中止

[5] 优点: 不会产生死锁, 因此不需要回滚; 可以在较早的时候释放锁, 减少等待时间, 增加并发性

[6] 缺点: 可能必须给根本不访问的数据项加锁, 导致封锁开销增加, 造成额外等待时间, 引起并发性降低
如果没有得到哪些数据项需要加锁, 必须给树根加锁

死锁处理

[1] 防止

• 使用数据项的一种顺序, 并且按照这个顺序申请加锁
  一旦一个事务锁住了某个特定数据, 就不能申请顺序中位于该数据签名的数据项上的锁
• 给每个事务赋予唯一时间戳用于决定事务等待还是会滚, 从而控制抢占
  如果事务回滚, 重启时保持原有的时间戳
  wait-die: 非抢占技术, 当且仅当Ti老于Tj允许Ti等待, 否则Ti回滚死亡
  wound-wait: 抢占技术, 当且仅当Ti比Tj年轻允许Ti等待, 否则Tj回滚
• 锁超时: 申请锁的事务最多等待一定时间, 否则自己回滚并重启
  但是等待时间太长会导致不必要的延迟, 等待时间太短会引起事务回滚造成资源浪费, 也可能产生饿死

[2] 检测和恢复: 等待图包含环即为死锁, 通过回滚一个或多个事务解除死锁
牺牲者的回滚代价:

• 事务已经计算了多久, 再完成任务之前还要计算多长时间
• 已经使用多少数据项, 还需要使用多少数据项
• 回滚牵涉多少事务
• 回滚次数(让事务被选为牺牲者的次数有限且较少, 防止饿死)

彻底回滚: 中止该事务, 然后重新开始
部分回滚: 记录锁的申请/授予序列和事务执行的更新

多粒度

[1] 给大粒度显式加锁, 则给属于它的记录隐式加锁

[2] 意向锁: 在树的较低层显示加锁
在一个结点显式加锁之前, 该结点所有祖先全部加意向锁
好处: 事务不需要搜索整棵树就能判断能否成功给一个结点加锁; 给结点Q加锁的事务必须遍历从根到Q的路径, 并给各结点加上意向锁

• 共享型意向锁IS: 较低层显式封锁, 但只能加共享锁
• 排他型意向锁IX: 较低层显式封锁, 可以加排他锁或者共享锁
• 共享排他型意向锁SIX: 结点子树显式加共享锁, 更低层显式加排他锁

[3] 多粒度封锁协议:

1. 锁类型相容函数
2. T必须先封锁根结点, 并且可以加任意类型的锁
3. 仅当T对Q的父结点有IX或IS时, T对Q可以加S或IS
4. 仅当T对Q的父结点有IX或SIX时, T对Q可以加X、SIX或IX
5. 仅当T未曾对任何结点解锁时, 才能对结点加锁(T为两阶段)
6. 仅当T不持有Q子结点的锁时, T可对Q解锁

[4] 封锁: 从根结点到叶结点的顺序进行, 解锁: 从叶结点到根结点到顺序进行

时间戳

[1] W-timestamp成功执行write的所有事务的最大时间戳
R-timestamp成功执行read所有事务的最大时间戳

[2] 时间戳排序协议:
T发出read:

1. 若TS(T) < W-timestamp, T需要读入的值已被覆盖, read操作被拒绝, T回滚
2. 若TS(T) >= W-timestamp, 执行read, R-timestamp设置为max{T-timestamp, TS(T)}

T发出write:

1. 若TS(T) < R-timestamp, T产生Q事先前需要的值, 系统已假定该值不会再产生, write操作被拒绝, T回滚
2. 若TS(T) < W-timestamp, T试图写入Q值已过时, write操作被拒绝, T回滚
3. 否则系统执行write, 将W-timestamp设置为TS(T)

回滚后系统赋予T新的时间戳并重新启动

[3] 可能会饿死长事务——解决方案: 如果事务反复重启, 与之冲突的事务应当暂时阻塞

[4] 可能产生不可恢复的调度——解决方案:

• 在事务末尾的写操作执行过程中任何事物都不许访问已写完的任何数据项——可恢复, 无级联
• 使用受限的封锁形式, 对未提交数据项的读操作被推迟到更新该数据项的事务提交之后——可恢复, 无级联
• 跟踪未提交写操作, 如果T读取了其他事务所写的数据, 只有当其他事务都提交之后, T才可以提交——可恢复

[5] Thomas写规则, T发出write:

1. 若TS(T) < R-timestamp, T产生Q式先前需要的值, 系统已假定该值不会再产生, write操作被拒绝, T回滚
2. 若TS(T) < W-timestamp, T试图写入Q值已过时, write操作被忽略 (删除事务发出的过时的write操作来使用视图可串行性)
3. 否则系统执行write, 将W-timestamp设置为TS(T)

视图可串行化

[1] 视图等价:

1. 对于每一个Q, 若事务T在调度S中读取了Q的初始值, 那么S’中T也必须读取Q的初始值
2. 对于每一个Q, 若S中事务T执行了read并且读取的值是由Tj执行write产生的, 那么S’中T的read读取的值也必须是由Tj的同一个write操作产生的 (1和2保证两个调度中每个事务都读取相同的值, 从而进行相同的计算)
3. 对于每一个Q, 若在S中有事务执行了最后的write操作, 则在S’中该事务也必须执行最后的write操作 (保证两个调度得到相同的最终系统状态)

[2] 冲突可串行化调度都是视图可串行化

[3] 没有read的write是盲目写操作, 存在于任何非冲突可串行化的视图可串行化调度中

有效性检查

[1] 大部分事务为只读事务, 可以使用有效性检查协议, 是一种监控系统的机制

[2] 把事务T划分为两个或三个阶段执行:

1. 读阶段: 数据项值读入并保存在T的局部变量中, 写操作对局部临时变量进行, 不对数据库进行真正更新
2. 有效性检查阶段: 判断是否可以执行write不违反可串行行; 失败则中止这个事务
3. 写阶段(只读事务忽略这个阶段): 把局部临时变量的值复制到数据库中

[3] 三个时间戳:

• Start: 开始执行的时间
• Validation: 作为事务T的时间戳, 因为在冲突品读很低的情况下可以有更快的响应时间
• Finish: 完成写阶段的时间

[4] 有效性测试: Tk < Ti满足两个条件之一:

• Finish(Tk) < Start(Ti), Tk在Ti开始之前完成执行
• Start(Ti) < Finish(Tk) < Validation(Ti), Tk所写数据与Ti不相交, 且Tk的写阶段在Ti开始有效性检查之前完成, 保证Tk与Ti的写不重叠

[5] 自动预防级联回滚

[6] 可能会饿死长事务——解决方案: 如果事务反复重启, 与之冲突的事务暂时阻塞

乐观的并发控制: 事务乐观的执行, 假定它们能够完成执行并且最终有效
悲观的并发控制: 封锁和时间戳排序, 因为检测到冲突时强迫等待或回滚, 即使调度可能是冲突可串行化的

多版本

[1] 每个版本Qk包含三个数据字段:

• Content: Qk版本的值
• W-timestamp: 创建Qk版本的事务的时间戳
• R-timestamp: 成功读取Qk版本的事务的最大时间戳

[2] 多版本时间戳排序机制:

1. 事务Ti发出read, 返回Qk的内容
2. 事务Ti发出write, 若TS(Ti) < R-timestamp(Qk), 则系统回滚事务Ti (写操作太迟会被强迫中止)
   若TS(Ti) = W-timestamp(Qk), 则系统覆盖Qk内容
   若TS(Ti) > R-timestamp(Qk), 创建Q的一个新版本

[3] 优点: 读请求从不失败且不必等待

[4] 缺点: 产生两次潜在的磁盘访问(读取数据项邀请更新R-timestamp字段); 事务间的冲突通过回滚而不是等待解决

[5] 不保证可恢复性和无级联性——解决方案同基本时间戳排序机制:

• 在事务末尾的写操作执行过程中任何事物都不许访问已写完的任何数据项——可恢复, 无级联
• 使用受限的封锁形式, 对未提交数据项的读操作被推迟到更新该数据项的事务提交之后——可恢复, 无级联
• 跟踪未提交写操作, 如果T读取了其他事务所写的数据, 只有当其他事务都提交之后, T才可以提交——可恢复

多版本两阶段封锁

[1] 更新事务: 执行强两阶段封锁协议, 即它们持有全部锁直到事务结束
数据项的每一个版本有一个时间戳: 计数器(ts_counter), 这个计数器在事务提交时增加计数

[2] 当更新事务读取一个数据项时, 它在获得该数据项上的共享锁后, 读取该数据项最新版本的值
当更新事务写一个数据项时，它首先要获得该数据项上的排它锁, 然后为此数据项创建一个新的版, 写操作在新版本上进行 (新版本的时间戳最初值为∞, 大于任何可能的时间戳)
当更新事务完成其任务后, 事务将它新创建版本的时间戳设为ts_counter+1, 完成事务提交并释放锁

[3] 只读事务开始执行前, 系统读取ts_counter的当前值来作为该事务的时间戳, 并依照ts_counter读取数据版本
该版本是数据当前的最新版本, 事务在整个处理过程中都只参照数据的这个版本

[4] 在ts_counter增加之后启动的只读事务, 将看到被更新事务更新后的ts_counter值
在增加之前就启动的只读事务, 将看到被更新事务更新之前的ts_counter值
只读事务均不必等待加锁, 访问并只允许访问所看到ts_counter值对应的数据版本

[5] 可恢复、无级联

快照隔离

[1] 事务开始时给它数据库快照, 事务在快照操作, 与其他事务隔离
事务将更新写入数据库之前, 处理与其他并发更新事务的潜在冲突
允许事务提交时, 事务变为提交状态, 对数据库所有写操作必须作为一个原子操作执行

[2] 与T并发: 从T开始到执行这个检查之间任何时刻, 该事务是活跃的活着部分提交的

[3] 先提交者获胜: T进入部分提交状态, 以下操作作为一个原子操作:

1. 检查是否有与T并发执行的事务, 且对于T打算写入的数据已经更新写入数据库
2. 有则中止T
3. 否则T提交并将更新写入数据库

[4] 先更新者获胜: 仅用于更新操作

1. Ti试图更新数据项时, 请求一个写锁
2. 如果没有其他并发事务拥有该锁: 如果数据项已经被任何并发事务更新, T中止; 否则T执行操作并提交
3. 否则Ti不能执行, 等待直到这个事务Tj中止或提交
   如果Tj中止, 锁被释放且Ti可以获得锁, 执行前面的更新检查(检查是否有与T并发执行的事务, 且对于T打算写入的数据已经更新写入数据库; 有则中止T; 否则T提交并将更新写入数据库)
   如果Tj提交, 则Ti必须中止

[5] 不能保证可串行化

[6] 写偏斜: 一对事务中每一个都读取对方写的数据, 但是不存在两者同时写的数据

[7] 由数据库强制执行的完整性约束(例如主键和外键约束), 不能再快照上进行检查——数据库系统必须在数据库的当前状态下检查约束, 作为提交时有效性检验的一部分
否则将有可能有两个并发事务同时插入主键相同的记录
或者一个事务插入一个外键值, 另一个并发事务从引用的表中删除该值

插入、删除与谓词读

[1] 删除

• 两阶段封锁协议: 仅当要删除元组的事务在元组上有排他锁时, 才能执行删除操作
• 时间戳排序协议: T发出delete:
  1. 若TS(T) < R-timestamp, T将要删除Q的值已经被读取, delete操作被拒绝, T回滚
  2. 若TS(T) < W-timestamp, T将要删除Q值已被写过, delete操作被拒绝, T回滚
  3. 否则系统执行delete

[2] 插入

• 两阶段封锁协议: Ti执行insert操作, 在新创建的数据项Q上授予Ti的排他锁
• 时间戳排序协议: Ti执行insert操作, 把R-timestamp与W-timestamp值设置为TS(Ti)

[3] 插入操作可能导致幻象现象, 尽管插入和查询没有存取共同元组, 也可能发生逻辑冲突
仅仅封锁访问的元组不够, 还要封锁用来找出(事务访问的)元组的信息——可以通过将数据项与关系关联在一起实现

• 读取关系中有哪些元组这一信息的事务, 必须以共享模式封锁对应于该关系的数据项
• 更新关系中有哪些元组这一信息的事务, 必须以排他模式封锁对应于该关系的数据项

让事务在真实的数据项上发生冲突而不是在幻想上发生冲突

[4] 使用索引来检索元组的事务必须封锁索引本身
索引封锁技术: 对某些索引结点加锁, 避免封锁整个索引

• 只有首先在关系的一个或多个索引上找到元组后, 事务T才能访问关系上的这些元组。全表扫描看作一个索引上所有叶结点的扫描
• 进行查找的事务T必须在它要访问的所有索引叶结点上获得共享锁
• 没有更新关系上的所有索引之前, T不能插入、删除或更新关系中的元组。该事务必须获得插入、删除或更新所影响的所有索引叶结点的排他锁
  对于插入与删除, 受影响的叶结点是插入后包含或删除前包含元组搜索码值的叶结点
  对于更新, 受影响的叶结点是修改前包含搜索码旧值的叶结点, 以及修改后包含搜索码新值的叶结点
• 元组照常获得锁; 必须遵守两阶段封锁协议规则

[5] 不关注索引内部结点的并发控制问题

实践中的弱一致级别

查询结果的一致性不是至关重要, 使用可串行性会对事务处理起反作用

二级一致性和游标稳定性

[1] 二级一致性 (已提交读水平), 可以防止发生级联中止
共享锁可以在任何时候释放, 锁可以在任何时间获得
排他锁只有在事务提交或中止后才能释放——没有事务可以读取未提交值
读不是可重复读

[2] 游标稳定性是二级一致性的一种形式
利用游标对关系中的元组进行迭代的程序, 不封锁整个关系

跨越用户交互的并发控制

[1] 可见的外部写: 写到用户屏幕
实现: 在非易失性存储设备中临时写下与外部写相关所有数据, 然后在事务进入提交状态后执行真正的写操作
如果事务进入提交状态而外部写未完成时系统出现故障, 可以在重启后用存储在非易失性设备中的数据执行外部写操作

[2] 应用程序采用元组中存储的版本号验证写操作的机制, 提供弱可串行化水平(不保证可串行化), 实现在数据库顶层应用层, 无需修改数据库
将涉及用户交互的事务划分成两个或更多事务, 使得没有事务跨越用户交互

[3] 机制

1. 每个关系模式中添加一个额外版本号属性/时间戳, 创建元组时初始化为0
2. 一个事务第一次读取(它试图更新的)一个元组时, 记录元组的版本号
3. 读操作时独立的数据库事务, 任何获得的锁立即释放
   更新操作本地完成, 作为提交过程的一部分拷贝到数据库中:
   对于每个更新的元组, 检查当前版本号是否等于第一次读取事务时的版本号
   • 匹配则执行数据库中该元组的更新, 版本号+1
   • 不匹配则事务中止, 回滚执行的所有更新

[4] 类似快照隔离的先提交者获胜规则, 但是读操作不对应一个快照
与有效性检验协议相比, 读操作不进行检验——不做读有效性检查的乐观并发机制

索引结构中的并发

只要维护索引的准确性, 对索引进行非可串行化并发存取是可以接受的
对B+树进行非可串行化访问, 但保证B+树结构是正确的, 保证对数据库本身存取是可串行化的
[1] 蟹行协议

1. 查找: 首先用共享模式锁住根结点, 沿树向下遍历
   在子结点获得一个共享锁, 释放父结点的锁, 直到叶结点

2. 插入或删除: 首先找到叶结点(到此为止只获得和释放共享锁)
   用排他锁锁住叶结点, 插入或删除码值
   如果需要分裂或合并, 用排他锁锁住父结点, 完成操作后释放该结点和兄弟结点的锁

可能引起死锁——解决方法: 让搜索操作释放锁, 然后从树根重启

[2] B-link树封锁协议: 要求每个结点维护一个指向右兄弟结点的指针

1. 查找: 每个结点访问之前加共享锁, 非叶结点上的锁应该在对B+树其他任何结点发出加锁请求前释放
   结点分裂与查找同时发生: 搜索码值在兄弟结点代表的访问内, 系统循着指向右兄弟的指针找到该兄弟的结点
   叶结点封锁遵循两阶段封锁协议——避免幻象现象
2. 插入与删除: 定位到要进行插入或删除的叶结点
   该结点共享锁升级为排他锁, 然后插入或删除
   插入与删除遵循两阶段封锁协议——避免幻象现象
3. 分裂: 创建新结点作为原结点的右兄弟, 设置原结点和新结点的右兄弟指针
   事务释放原结点的排他锁, 然后对父结点增加排他锁, 以便插入指向新结点的指针
   不需要对新结点加锁或解锁; 如果是叶结点要遵守两阶段封锁协议
4. 合并: 将与之合并的结点加排他锁, 合并后对父结点加排他锁, 以便删除要删除的结点
   事务释放已合并结点的锁; 除非父结点也要合并, 不然释放其锁

查找和插入不会引起死锁, 删除可能回归引起不一致性

[3] 下一码封锁: 每一次索引查找不仅封锁查找范围内多个码, 而且封锁下一个码值; 每一次插入不仅封锁要插入的值, 而且包括下一个码值(一个事务试图插入一个值到另一个事务的索引查找范围内时, 在插入码值的下一个码值上冲突); 删除必须封锁删除值的下一个码值