锁的实现 - 复旦大学

1 .分布式系统 Distributed Systems 第 13 讲 事务 和并发 控制 Lecture 13 TRANSACTIONS AND CONCURRENCY CONTROL 王晓阳、张 奇 复旦大学 计算机科学技术学院 1

2 .目录 13.1 简介 13.2 事务 13.3 嵌套 事务 13.4 锁 13.5 乐观 并发控制 13.6 时间 戳排序 13.7 并发 控制方法的比较 13.8 小结 2

3 .13.1 简介 事务的目标 在 多个事务访问对象 以及 服务器面临故障 的情况下，保证所有由服务器管理的对象始终保持一个一致的状态 。 并发控制 增强可靠性 可恢复对象 利用持久存储保存状态信息 事务是由客户定义的针对服务器对象的一组操作，它们组成一个不可分割的单元，由服务器执行。 3

4 .13.1 简介 银行事务事例 deposit(amount) // 向帐户存 amount 数量的钱 withdraw(amount) // 从帐户中取 amount 数量的钱 getBalance () -> amount // 返回帐户中余额 setBalance (amount) // 将帐户余额设置成 amount create(name) -> account 　　　 　　 // 用给定的用户名创建一个新帐户 lookUp (name) -> account 　 　　 // 根据给定的用户名查找帐户，并返回该帐户的一个引用 branchTotal () -> amount 　 // 返回支行中所有帐户余额的总和 Branch 接口中的操作 4

5 .13.1 简介 简单的同步机制 ( 无事务 ) 服务器上的原子操作 　 - 使用多线程可提高服务器的性能 　 - 采用锁机制保证线程同步 　 - 原子操作：免受其它线程中执行的并发操作干扰的操作 通过服务器操作的同步加强客户的协同 - 互斥 　 - 生产者－消费者 　　 Java 中的 wait 和 notify 方法 5

6 .13.1 简介 事务的故障模型 ——Lampson 模型 对持久性存储的写操作可能发生故障 　 - 写操作无效或写入错误的值 　 - 文件存储可能损坏 　 - 读数据时可根据校验和发现损坏数据 服务器可能偶尔崩溃 - 进程崩溃后，根据持久存储中的信息恢复 　 - 服务器不会产生随机故障 消息传递可能由任意长时间的延迟 - 消息可丢失、重复或者损坏 　 - 接收方能够检测受损消息 6

7 .13.2 事务 事务的概念 　 以原子方式执行的一系列操作，即 1. 它们不受其它并发客户操作的干扰 　 2. 所有操作或者全部成功完成，或者不产生任何影响 银行事务示例 7 Transaction T: a.withdraw (100); b.deposit (100); c.withdraw (200); b.deposit (200);

8 .13.2 事务 全有或全无：或者完全成功，或者不留下任何效果 故障原子性 　即使服务器崩溃，事务的效果也是原子的。 持久性 　一旦事务完成，它的所有效果将被保存到持久存储中 隔离性 每个 事务的影响不受其它事务的影响 8

9 .13.2 事务 使用一个事务 事务协调者 　 - 作用 　　创建和管理事务 　 - 示例 9 openTransaction () -> trans; 开始一个新事务，并返回该事务的唯一 TID ， TID 用于事务的其它操作。 closeTransaction (trans) -> (commit, abort); 结束事务：若返回 commit ，则成功提交；否则返回 abort ，标示放弃。 abortTransaction (trans); 放弃事务。

10 .13.2 事务 使用一个事务 ( 续 ) 事务的完成通常需要一个客户程序、若干可恢复对象和一个协调者之间的合作 事务 执行结果 　 - 完全成功 　 - 放弃事务 客户放弃事务 服务器放弃事务 事务执行历史示例 10

11 .13.2 事务 11 成功执行 被客户放弃 被服务器放弃 openTransaction openTransaction openTransaction 操作 操作 操作 操作 操作 操作 服务器 放弃事务 操作 操作 向客户报告 ERROR closeTransaction abortTransaction

12 .13.2 事务 并发控制 ( 一 ) 更新丢失问题 　初值：帐户 A 、 B 、 C 分别为 $100 、 $200 、 $300 　操作：两次转帐 (A → B 、 C → B) ，每次转帐金额为 B 当前帐户余额的 10% 期望结果： B 的终值应为 $242 12

13 .13.2 事务 13 事务 T: balance = b.getBalance(); b.setBalance(balance*1.1); a.withdraw(balance/10) 事务 U: balance = b.getBalance(); b.setBalance(balance*1.1); c.withdraw(balance/10) balance = b.getBalance(); $200 balance = b.getBalance(); $200 b.setBalance(balance*1.1); $220 b.setBalance(balance*1.1); $220 a.withdraw(balance/10) $80 c.withdraw(balance/10) $280

14 .13.2 事务 并发控制 ( 二 ) 不一致检索 　初值：帐户 A 、 B 分别为 $200 、 $200 　操作：转帐 + 查询银行所有帐户的总余额 期望结果：总余额为 $400 14

15 .13.2 事务 15 事务 V: a.withdraw(100) b.deposit(100) 事务 W: aBranch.branchTotal() a.withdraw(100); $100 total = a.getBalance() $100 total = total+b.getBalance() $300 total = total+c.getBalance() b.deposit(100) $300

16 .13.2 事务 并发控制 ( 三 ) 串行等价性 多事务正确运行效果推断 若 每个事务知道它单独执行的正确效果，则可以推断出这些事务按某种次序一次执行一个事务的效果。 串 行等价 的交错执行 并发 事务交错执行操作的效果等同于按某种次序一次执行一个事务的效果。 使用 串行等价性作为并发执行的判断标准，可防止更新丢失和不一致检索问题。 16

17 .13.2 事务 17 事务 T: balance = b.getBalance() b.setBalance(balance*1.1) a.withdraw(balance/10) 事务Ｕ： balance = b.getBalance() b.setBalance(balance*1.1) c.withdraw(balance/10) balance = b.getBalance() $200 b.setBalance(balance*1.1) $220 balance = b.getBalance() $220 b.setBalance(balance*1.1) $242 a.withdraw(balance/10) $80 c.withdraw(balance/10) $278

18 .13.2 事务 18 事务 V: a.withdraw(100); b.deposit(100) 事务 W: aBranch.branchTotal() a.withdraw(100); $100 b.deposit(100) $300 total = a.getBalance() $100 total = total+b.getBalance() $400 total = total+c.getBalance() ...

19 .13.2 事务 并发控制 ( 三 ) 冲突操作 　 - 冲突 　　两个操作的执行效果和它们的执行次序相关 　 - Read 和 Write 操作的冲突规则 19 不同事务的操作 是否冲突 原因 read read 否 由于两个 read 操作的执行效果不依赖这 两个操作的执行次序 read write 是 由于一个 read 操作和一个 write 操作的执 行效果依赖于它们的执行次序 write write 是 由于两个 write 操作的执行效果依赖于这 两个操作的执行次序

20 .13.2 事务 并发控制 ( 三 ) 冲突操作 ( 续 ) 　 - 串行等价性 两 个事务串行等价的充要条件是，两个事务中所有的冲突操作都按相同的次序在它们访问的对象上执行。 　 - 非串行等价地执行事务示例 　　事务 T ： x=read( i ); write(i,10); write(j,20) ； 事务 U ： y=read(j); write(j,30); z=read( i ) ； 20

21 .13.2 事务 21 事务 T: 事务 U: x = read(i) write(i, 10) y = read(j) write(j, 30) write(j, 20) z = read (i)

22 .13.2 事务 并发控制 ( 四 ) 并发控制协议 依据 串行 等价性 目的 将 访问对象的并发事务串行化 方法 锁 乐观并发控制 时间戳排序 　　　　 22

23 .13.2 事务 事务放弃时的恢复 ( 一 ) 脏数据读取 　某个事务读取了另一个未提交事务写入的数据 23 事务 T: a.getBalance() a.setBalance(balance + 10) 事务 U: a.getBalance() a.setBalance(balance + 20) balance = a.getBalance() $100 a.setBalance(balance + 10) $110 balance = a.getBalance() $110 a.setBalance(balance + 20) $130 commit transaction abort transaction 事务 T 放弃时的脏数据读取

24 .13.2 事务 事务放弃时的恢复 ( 二 ) 事务可恢复性 　策略：推迟事务提交，直到它读取更新结果的其它事务都已提交。 连锁放弃 　　 - 某个事务的放弃可能导致后续更多事务的放弃 　 - 防止方法：只允许事务读取已提交事务写入的对象 24

25 .13.2 事务 事务放弃时的恢复 ( 三 ) 过早写入 　　 - 一些数据库在放弃事务时，将变量的值恢复到该事务所有 write 操作的“前映像”。 　 - 为了保证使用前映像进行事务恢复时获得正确的结果， write 操作必须等到前面修改同一对象的其它事务提交或放弃后才能进行 。 25 事务 T: a.setBalance(105) 事务 U: a.setBalance(110) $100 a.setBalance(105) $105 a.setBalance(110) $110

26 .13.2 事务 事务放弃时的恢复 ( 四 ) 事务的严格执行 　 - 严格执行： read 和 write 操作都推迟到写同一对象的其它事务提交或放弃后进行 　 - 可以真正保证事务的隔离性 临时版本 　　 - 目的：事务放弃后，能够清除所有对象的更新 　 - 方法 事务的所有操作更新将值存储在自己的临时版本中 事务提交时，临时版本的数据才会用来更新对象 26

27 .13.3 嵌套事务 概念 嵌套事务：允许事务由其它事物构成 顶层 事务（ Top-Level ） 子 事务 (Sub-transaction) 示例 27

28 .13.3 嵌套事务 28 T : 顶层事务 T 1 = openSubTransaction T 2 = openSubTransaction openSubTransaction openSubTransaction openSubTransaction openSubTransaction T 1 : T 11 : prov.commit prov. commit abort prov. commit prov. commit prov. commit commit T 2 : T 12 : T 21 : T 211 :

29 .13.3 嵌套事务 优点 并发度高 　　子事务可并发运行 健壮性强 　　子事务可以独立提交和放弃 提交规则 事务在它的子事务完成以后，才能提交或放弃 子事务完成后，可独立决定是暂时提交或放弃 父事务放弃时，所有的子事务都被放弃 若子事务放弃，则父事务可以决定是否放弃 若顶层事务提交，则所有暂时提交的事务将最终提交 29