分布式系统 ... 13.1 简介; 13.2 事务; 13.3 嵌套事务; 13.4 锁; 13.5 乐观并发控制; 13.6 时间戳排序; 13.7 并发控制方法的比较; 13.8 小结. 2 ... 创建和管理事务 ..... 向前验证在处理冲突时比较灵活; 向后验证将较大的读集合和较早事务的写集合进行比较 ...

Daniel发布于2018/06/02 00:00

注脚

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) 事务U: 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

30.13.4 锁 互斥锁是一种简单的事务串行化实现机制 事务访问对象前请求加锁 若对象已被其它事务锁住,则请求被挂起,直至对象被解锁 使用示例 30

31.13.4 锁 31 事务 T balance = b.getBalance() b.setBalance(bal*1.1) a.withdraw(bal/10) 事务 U balance = b.getBalance() b.setBalance(bal*1.1) c.withdraw(bal/10) 操作 锁 操作 锁 openTransaction bal = b.getBalance() 锁住 B b.setBalance(bal*1.1) openTransaction a.withdraw(bal/10) 锁住 A bal = b.getBalance() 等待事务 T 在 B 上的锁 closeTransaction 对 A,B 解锁 锁住 B b.setBalance(bal*1.1) c.withdraw(bal/10) 锁住 C closeTransaction 对 B,C 解锁 …

32.13.4 锁 两阶段 加锁( two-phrase locking ) 目的:保证两个事务的所有的冲突操作对必须以相同的次序执行 增长阶段:不断获取新锁 收缩阶段:释放锁 严格的两阶段 加锁 (strict two-phrase locking) 目的:防止事务放弃导致的脏数据读取、过早写入等问题 方法:所有在事务执行过程中获取的新锁必须在事务提交或放弃后才能释放 32

33.13.4 锁 读锁和写锁 目的:提高并发度 支持多个并发事务同时读取某个对象 允许一个事务写对象 事务的操作冲突规则 如果事务 T 已经对某个对象进行了读操作,那么并发事务 U 在事务 T 提交或放弃前不能写该对象。 如果事务 T 已经对某个对象进行了写操作,那么并发事务 U 在事务 T 提交或放弃前不能写或读该对象。 读锁和写锁的兼容性 33

34.13.4 锁 34 对某一对象 被请求的锁 read write 已设置的锁 none OK OK read OK wait write 等待 等待

35.13.4 锁 35 1. When an operation accesses an object within a transaction: (a) If the object is not already locked, it is locked and the operation proceeds. (b) If the object has a conflicting lock set by another transaction, the transaction must wait until it is unlocked. (c) If the object has a non-conflicting lock set by another transaction, the lock is shared and the operation proceeds. (d) If the object has already been locked in the same transaction, the lock will be promoted if necessary and the operation proceeds. (Where promotion is prevented by a conflicting lock, rule (b) is used.) 2. When a transaction is committed or aborted, the server unlocks all objects it locked for the transaction. Figure 16.16 Use of locks in strict two-phase locking

36.13.4 锁 锁的实现 锁的授予通常由服务器上一个对象实现 — 锁管理器 每个锁都是 Lock 类的一个实例    - 被锁住对象的标示符   - 当前拥有该锁的事务的标示符   - 锁的类型 36

37.13.4 锁 37 public class Lock { private Object object ; // the object being protected by the lock private Vector holders; // the TIDs of current holders private LockType lockType ; // the current type public synchronized void acquire( TransID trans, LockType aLockType ){ while (/*another transaction holds the lock in conflicing mode*/) { try { wait(); }catch ( InterruptedException e){/*...*/ } } if( holders.isEmpty ()) { // no TIDs hold lock holders.addElement (trans); lockType = aLockType ; } else if (/*another transaction holds the lock, share it*/ ) ){ if (/* this transaction not a holder*/) holders.addElement (trans); } else if (/* this transaction is a holder but needs a more exclusive lock*/) lockType.promote (); } }

38.13.4 锁 38 public synchronized void release( TransID trans ){ holders.removeElement (trans); // remove this holder // set locktype to none notifyAll (); } }

39.13.4 锁 锁的实现 ( 续 ) LockManager 类   所有的事务要求加锁和解锁的请求都被送往类 LockManager 的某个实例。 39

40.13.4 锁 40 public class LockManager { private Hashtable theLocks ; public void setLock (Object object , TransID trans, LockType lockType ){ Lock foundLock ; synchronized(this){ // find the lock associated with object // if there isn’t one, create it and add to the hashtable } foundLock.acquire (trans, lockType ); } // synchronize this one because we want to remove all entries public synchronized void unLock ( TransID trans) { Enumeration e = theLocks.elements (); while( e.hasMoreElements ()){ Lock aLock = (Lock)( e.nextElement ()); if (/* trans is a holder of this lock*/ ) aLock.release (trans); } } }

41.13.4 锁 嵌套事务的加锁需求 嵌套事务集    - 要求:不能观察到其它嵌套事务集的部分效果   - 实现方法:父事务继承子事务的所有锁,锁的继承从底层向高层传递。 嵌套事务集中的事务 - 要求:不能观察到同一事务集中其它事务的部分效果   - 实现方法:父事务不允许和子事务并发运行;同层次的事务可并发执行。 41

42.13.4 锁 嵌套事务的加锁规则 ( 一 ) 获得读锁   如果子事务获取了某个对象的读锁,那么其它活动事务不能获取该对象的写锁,只有该子事务的父事务们可以持有该写锁。 获得写锁    如果子事务获取了某个对象的写锁,那么其它活动事务不能获取该对象的写锁或读锁,只有该子事务的父事务们可以持有该写锁或读锁。 42

43.13.4 锁 嵌套事务的加锁规则 ( 二 ) 提交   子事务提交时,它的所有锁由父事务继承,即允许父事务保留与子事务相同模式的锁。 放弃   子事务放弃时,它的所有锁都被丢弃。如果父事务已经保留了这些锁,那么它可以继续保持这些锁。 43

44.13.4 锁 死锁 ( 一 ) 死锁场景示例  两个事务都在等待并且只有对方释放锁后才能继续执行 44 事务 T 事务 U 操作 锁 操作 锁 a.deposit(100); 给 A 加锁 b.deposit(200) 给 B 加写锁 b.withdraw(100) 等待事务 U a.withdraw(200); 等待事务 T 在 B 上的锁 在 A 上的锁

45.13.4 锁 死锁 ( 二 ) 定义   死锁 是一种状态,在该状态下一组事务中的每一个事务都在等待其它事务释放某个锁。 等待 图 ( wait-for graph )  表示事务之间的等待关系。 45 B A 等待 持有 持有 T U U T 等待

46.13.4 锁 死锁 ( 三 ) 复杂等待图示例    - 事务 T 、 U 和 V 共享 对象 C 上的读锁   - 事务 W 拥有对象 B 上的写锁    - 事务 T 、 W 请求对象 C 上的 写锁    - V 对象 C 上的 写锁 46 C T U V 持有 持有 持有 T U V W W B 持有 等待

47.13.4 锁 预防死锁 每个事务在开始运行时锁住它要访问的所有对象    - 一个简单的原子操作   - 不必要的资源访问限制    - 无法预计将要访问的对象 预定次序加锁    - 过早加锁 - 减少并发度 更新锁 避免死锁 在数据项上加更新锁的事务可以读该数据项,但该锁与加在同一数据项上的更新相冲突 。 47

48.13.4 锁 死锁检测 维护等待图 检测等待图中是否存在环路 若存在环路,则选择放弃一个事务 锁超时 :解除死锁最常用的方法之一 每个锁都有一个时间期限 超过时间期限的锁成为可剥夺锁 若存在等待可剥夺锁保护的对象,则对象解锁 使用超时解除死锁示例 48

49.13.4 锁 49 事务 T 事务 U 操作 锁 操作 锁 a.deposit(100); 给 A 加写锁 b.deposit(200) 给 B 加写锁 b.withdraw(100) 等待事务 U 在 a.withdraw(200); 等待事务 T 在 A 上的锁 B 上的锁 ( 超时 ) T 在 A 上的锁 变成可剥夺的 , 释放 A 上的锁, 放弃 T a.withdraw(200); 给 A 加写锁 释放 A , B 上的锁

50.13.4 锁 在加锁机制中增加并发度 双版本加锁 层次锁 双版本加锁 读 / 写操作    - 写操作对象可为临时版本   - 读操作对象为提交版本 读锁、写锁和提交锁 - 读锁:在读操作前为对象设置读锁   - 读锁:在写操作前为对象设置写锁    - 提交锁:收到提交事务请求后,将写锁转换为提交锁  锁的相容性 50

51.13.4 锁 双版本加锁 ( 续 ) 锁的相容性 51 对某个对象 要设置的锁 read write commit 已设置的锁 none OK OK OK read OK OK 等待 write OK 等待 commit 等待 等待

52.13.4 锁 层次锁 混合粒度的层次锁 每个事务按需要锁住部分数据  锁的拥有者能显式访问该节点并隐式访问它的子节点 给子节点加锁时,需要在父节点和祖先节点设置试图 锁 在每一层,设置父锁与设置等价的子辈锁具有相同的效果 锁的相容性 52

53.13.4 锁 53 对某个对象 要设置的锁 read write I-read I-write 已设置的锁 none OK OK OK OK read OK 等待 OK 等待 write 等待 等待 等待 等待 I-read OK 等待 OK OK I-write 等待 等待 OK OK

54.13.4 锁 层次锁示例 54 星期 星期一 星期二 星期三 星期四 星期五 9:00–10:00 时间段 10:00–11:00 11:00–12:00 12:00–13:00 13:00–14:00 14:00–15:00 15:00–16:00

55.13.5 乐观 并发 控制 锁机制的缺点 维护开销大 会引起死锁 并发度低 乐观策略 基于事实:在大多数应用中,两个客户事务访问同一个对象的可能性很低。 方法 - 访问对象时不作检查操作   - 事务提交时检测冲突    - 若存在冲突,则放弃一些 事务 55

56.13.5 乐观 并发 控制 事务的三个阶段 工作阶段   - 每个事务拥有所修改对象的临时版本 - 每个事务维护访问对象的两个集合:读集合和写集合 验证阶段 - 在收到 closeTransaction 请求,判断是否与其它事务存在冲突。 更新阶段 - 提交通过验证的事务 56

57.13.5 乐观 并发 控制 事务的验证 事务号   - 每个事务在进入验证阶段前被赋予一个事务号 - 事务号是整数,并按升序分配   - 事务按事务号顺序进入验证阶段 - 事务按事务号提交 冲突规则   - 事务 T v 的验证测试   - T i 和 T v 之间的存在冲突 57

58.13.5 乐观 并发 控制 事务 T v 对事务 T i 而言是可串行化 的: 58 T v T i 规则 write read 1. T i 不能读取 T v 写的对象 read write 2. T v 不能 读取 T i 写 的对象 write write 3. T i 不能写 T v 写的对象 , 并且 T v 不能写 T i 写的对象

59.13.5 乐观并发控制 向后验证 检查它的读集是否和其它较早重叠事务的写集是否重叠 算法   - startTn : T v 进入工作阶段时已分配的最大事务号码   - finishTn : T v 进入验证阶段时已分配的最大事务号码 验证失败后,冲突解决方法   放弃当前进行验证的 事务 59 Boolean valid = true For ( int T i = startT n +1; T i <= finishT n ; T i ++) { if (read set of T v intersects write set of T i ) valid = false }

60.13.5 乐观并发控制 向后验证 ( 续 ) 事物的验证过程   - T 1 、 T 2 、 T 3 是较早开始的事务 - T 1 在 T v 开始之前提交   - T 2 、 T 3 在 T v 完成其工作阶段前提交 - startTn+1=T 2 , finishTn =T 3 60

61.13.5 乐观并发控制 61 较早提交的事务 工作阶段 验证阶段 更新阶段 T 1 T v 正在验证的事务 T 2 T 3 以后的活动事务 active 1 active 2 向后验证过程必须比较 T v 的读集和 T 2 、 T 3 的写集

62.13.5 乐观并发控制 向前验证 比较 Tv 的写集合和所有重叠的活动事务的读集合 算法   - 设活动事务具有连续的事务标示符 active 1 ~active N 验证失败后,冲突解决方法   - 放弃当前进行验证事务 - 推迟验证   - 放弃所有冲突的活动事务,提交已验证事务 62 Boolean valid = true for ( int T id = active 1 +1; T id <= active n ; T id ++){ if (write set of T v intersects read set of T id ) valid = false }

63.13.5 乐观并发控制 向前验证 ( 续 ) 事物的验证过程   - active 1 、 active 2 是较 T v 晚开始 的事务 63

64.13.5 乐观并发控制 64 较早提交的事务 工作阶段 验证阶段 更新阶段 T 1 T v 正在验证的事务 T 2 T 3 以后的活动事务 active 1 active 2 向前验证过程必须比较 T v 的写集和 active 1 、 active 2 的读集

65.13.5 乐观并发控制 向前验证和向后验证的比较 向前验证在处理冲突时比较灵活 向后验证将较大的读集合和较早事务的写集合进行比较 向前验证将较小的写集合和活动事务的读集合进行比较 向后验证需要存储已提交事务的写集合 向前验证不得不允许在验证过程中开始新事务 饥饿 由于冲突,某个事务被反复放弃,阻止它最终提交的现象。 利用信号量,实现资源的互斥访问,避免事务饥饿 65

66.13.6 时间戳排序 基本思想 时间戳   - 每个事务在启动时被赋予一个唯一的时间戳 - 时间戳定义了该事务在事务时间序列中的位置   - 不会引起死锁 冲突规则   - 写请求有效: 对象的最后 一次读访问或写访问由一个较早的事务执行 - 读请求有效:对象的最后一次写访问由一个较早的事物执行 66

67.13.6 时间戳排序 基于时间戳的并发控制 临时版本   - 写操作记录在对象的临时版本中   - 临时版本中的写操作对其它事务不可见 写时间戳和读时间戳   - 已提交对象的写时间戳比所有临时版本都要早 - 读时间戳集用集合中的最大值来代表 - 事务的读操作作用于时间戳小于该事务时间戳的 最 大写 时间戳的对象版本上 67

68.13.6 时间戳排序 基于时间戳的并发控制 ( 续 ) 操作冲突 68 规则 T c T i 1. write read 如果 T i >T c ,那么 T c 不能写被 T i 读过的对象, 这要求 T c ≥ 该对象的最大读时间戳 2. write write 3. read write 如果 T i >T c ,那么 T c 不能写被 T i 写过的对象, 这要求 T c ≥ 已提交对象的写时间戳 如果 T i > T c ,那么 T c 不能读被 T i 写过的对象, 这要求 T c ≥ 已提交对象的写时间戳

69.13.6 时间戳排序 时间戳排序的写规则 是否接受事务 T c 对对象 D 执行的写操作 示例 69 if ( T c ≥ D 的最大读时间戳 && T c > D 的提交版本上的写时间戳 ) 在 D 的临时版本上执行写操作,写时间戳置为 T c else /* 写操作太晚了 * / 放弃事务 T c

70.13.6 时间戳排序 70 c) T 3 写操作 时事务 Ti 产生的对象 ( 写时间戳为 Ti) T 1 <T 2 <T 3 <T 4 时间 之前 之后 T 2 T 2 T 3 时间 之前 之后 T 2 T 2 T 3 T 1 T 1 时间 之前 之后 T 1 T 1 T 4 T 3 T 4 时间 Transaction aborts 之前 之后 T 4 T 4 临时版本 提交版本 T i T i 图例 a) T 3 写操作 d) T 3 写操作 b) T 3 写操作

71.13.6 时间戳排序 时间戳排序的读规则 是否接受事务 T c 对对象 D 执行的读操作 示例 71 if ( T c ≥ D 提交版本的写时间戳 ) 设 D selected 是 D 的具有最大写时间戳的版本 ≤ T c ; if ( D selected 已提交 ) 在 D selected 版本上完成读操作 else 等待直到形成版本的事务提交或放弃,然后重新应用读规则; } else 放弃事务 T c

72.13.6 时间戳排序 72 时间 读操作执行 被选中 T 2 时间 读操作执行 被选中 T 2 T 4 时间 读操作等待 被选中 T 1 T 2 时间 事务中止 T 4 图例: 临时版本 提交版本 T i T i ( a) T 3 读操作 ( c) T 3 读操作 ( d) T 3 读操作 ( b) T 3 读操作 时事务 Ti 产生的对象 ( 写时间戳为 Ti) T 1 <T 2 <T 3 <T 4

73.13.6 时间戳排序 73 对象的不同版本及其时间戳 T U A B C RTS WTS RTS WTS RTS WTS {} S {} S {} S openTransaction bal = b.getBalance() { T} openTransaction b.setBalance(bal*1.1) bal = b.getBalance() wait for T a.withdraw(bal/10) commit T T bal = b.getBalance() b.setBalance(bal*1.1) c.withdraw(bal/10) S , U T , U S , T S , T { U}

74.13.6 时间戳排序 多版本 时间戳排序 基本思想   - 每个对象维护一个已提交版本列表   - 过迟到达的读操作从提交版本中获取信息 冲突规则   - T c 不能写事务 T i 读过的对象,其中 T i > T c 写规则 示例 74 if ( D maxEarlier 的读时间戳 ≤ T c ) 在 D 的临时版本上完成写操作,并标记上写时间戳 T c else 放弃事务 T c

75.13.6 时间戳排序 75 时间 T 4 write; T 5 read; T 3 write; T 3 read; T 2 T 3 T 5 T 1 T 3 T 1 < T 2 < T 3 < T 4 < T 5 图例 : 临时版本 提交版本 T i T i T k T k 事务 T i 产生的对象 ( 写时间戳为 T i 且读时间戳为 T k )

76.13.7 并发控制方法的比较 时间戳排序 静态地决定事务之间的串行顺序 对 读操作占优的事务而言,优于两阶段加锁机制 冲突规则 两阶段加锁 动态决定事务之间的串行顺序 对更新操作占优的事务而言,优于时间戳排序 时间戳排序和两阶段加锁均属采用悲观方法 76

77.13.7 并发控制方法的比较 乐观方法 并发事务之间的冲突较少时,性能较高 放弃 事务时,需要重复大量工作 悲观方法 简单 并发度低 77

78.13.8 小结 事务 嵌套事务 子事务可并发执行 子事务可独立提交和放弃 并发控制 准则:串行等价性 两个问题:更新丢失和不一致检索 事务放弃时的恢复 78

79.13.8 小结 并发控制方法 两阶段加锁 时间戳排序 乐观方法 79

80.Question? 80

user picture

相关文档

  • 大规模实践基于Docker的MySQL私有云平台。集成高可用、快速部署、自动化备份、性能监控、故障分析、过载保护、扩容缩容等多项自动化运维功能。数据库高可用是不容忽视的,在Docker容器分配时如何保障主从不在同一宿主机上呢?我们通过自研Docker容器调度平台,自定义Docker容器的分配算法。实现了MySQL的高密度、隔离化、高可用化部署。同时结合我们自研的数据库中间件,支持了分片集群及无感知的高可用切换功能。截止目前平台支撑了目前总量90%以上的MySQL服务(实际数量超过2000个),资源利用率提升30倍,数据库交付能力提升70倍。并且经受住了十一黄金周、春节票务业务高峰期的考验。未来将致力于数据库自动化向智能化的推进。

  • 在云时代的今天,企业数据库面临着复杂的选择,数据库异构迁移往往达不到预期效果,樊文凯想大家分享了ADAM数据库和应⽤用迁移(Advanced Database & ApplicationMigration, 以下简称ADAM),ADAM是阿里云结合阿里巴巴多年年内部业务系统数据库和应⽤用异构迁移的经验(去IOE),⾃自主研发的、迁移ORACLE数据库和应⽤用⾄至阿⾥里里云相关云产品的专业产品,分享了ADAMA的结构、高性能、数据库割接、智能分析、所用的生态工具等,典型的数据库中出现的痛点。

  • 主要介绍阿里云MongoDB服务使用上的一些最佳实践,以及对MongoDB的部署、参数调优

  • Lindorm 是新一代面向在线海量数据处理的分布式数据库,阿里的技术专家通过分享这些多种场景下的数据存储技术实践,帮助企业更好地理解各种数据存储技术的特点,针对自己的业务发展对数据存储技术进行选择和组合。