Skip to content

无级联事务调度

Cascadeless transaction schedule · Cascadeless schedule · ACA schedule

只允许事务读取已经提交事务产生的版本,从源头消除因脏读引发的级联中止。

条目类型
定义

形式陈述

事务调度 S 中,若 rj(x) 读取 wi(x) 产生的值且 ij,无级联条件要求

wi(x)<Sci<Srj(x).

因此读者只能消费已提交版本。若写者中止,就不会有其他事务因读过该写而需要跟随中止;这也是 avoid cascading aborts(ACA)名称的来源。读取调度开始前的初值、读取自己的写不受这条跨事务限制。

由于事务内部读发生在自身提交前,条件立即给出 ci<rj(x)<cj。所以每个无级联调度都是 可恢复事务调度,但反向不成立:可恢复性允许先脏读,只把消费者的 commit 延后。

无级联只约束读。另一个事务是否可在 Ti 结束前覆盖 Ti 的未提交写,不由这一定义排除;阻止这种 dirty write 需要更强的严格调度。

定义还隐含 writer 的正常提交。若 wi(x) 后出现 ai,任何声称从该写读取的 rj(x) 都违反无级联,因为不存在满足 ci<rj(x) 的提交事件。恢复系统不能通过事后给中止事务补一个“虚构提交”来挽救调度。

直觉

可恢复调度允许先借未兑现支票,只要求借款人晚些承诺;无级联调度干脆等支票兑现后才交给下游。这样一个事务中止时,影响停在本事务,不会沿读取链把一串工作推倒。

代价是等待或旧版本。单版本锁系统让读者阻塞到写者结束;多版本系统可以让读者选择更早的已提交版本。二者都能无级联,却呈现不同延迟与可见性。

所以“读没有阻塞”不否定无级联。关键是读到的版本是否已提交,而不是当前是否另有写者。版本链让活跃写者与旧版读者并存,单版本实现则更可能把同一条件表现为等待。

例子与边界

调度

text
w1(x,20); c1; r2(x)->20; c2

满足无级联条件。若 T1c1 前中止,T2 尚未读到它的值;若 T2 已读,则 T1 的提交决定已经固定。与之相比,w1(x);r2(x);c1;c2 虽可恢复,却仍让 T2T1 abort 时被迫回滚。

下面的调度没有任何跨事务读,因而无级联条件真空成立:

text
w1(x,1); w2(x,2); c2; c1

T2 覆盖了 T1 尚未提交的写,所以它不是 严格事务调度。这个反例说明“不会级联中止”不能改写成“任何人都不接触未提交数据”。

在 MVCC 中,T2 可能在 T1 活跃时读取更老的已提交版本。物理上两者并发访问同一键,逻辑 reads-from 却不指向 T1;判断应跟随版本来源,而不是仅看键名和墙钟重叠。

无级联也不禁止事务根据旧的已提交值作决定。若业务要求读取“当前最新”,还需定义快照时点或串行顺序;本性质只排除未提交来源,不能保证数据新鲜,也不能阻止长事务持续读取很老的合法版本。

推论与应用

无级联执行让事务 abort 的逻辑影响局部化,显著简化恢复与客户端错误处理。许多数据库通过严格锁、提交可见性规则或多版本读视图实现这一性质,但各机制还会附带不同串行性与阻塞保证。

它不消除死锁,也不保证提交事务可串行化。两个事务可以只读已提交旧值,分别写不同数据项并共同破坏约束;避免脏读与排除 write skew 属于不同历史条件。

恢复层可以利用这一性质缩小 abort 影响集:中止事务无需遍历读依赖去寻找跟随者。但写写冲突仍需保留足够 before-image,串行化控制仍需检查跨项依赖。无级联只删去一类恢复责任,不是完整恢复算法。

实际 trace 审计应为每次读记录版本创建事务与其 commit LSN,再验证提交先于读事件。只记录“读值等于 20”会在不同事务写出相同数值时丢失来源,无法证明 ACA 条件。

参考资料
  • Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman, Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987, Ch. 6。
  • Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1992, Ch. 10。
  • Abraham Silberschatz, Henry F. Korth, and S. Sudarshan, Database System Concepts, 7th ed., McGraw-Hill, 2019, Ch. 19。
关系图谱6 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

下位 / 直接特例