《分布式7分布式系统事务和并发控制》由会员分享，可在线阅读，更多相关《分布式7分布式系统事务和并发控制（83页珍藏版）》请在金锄头文库上搜索。
1、1,分布式与并行计算-分布式系统的事务和并发控制,计算机科学与技术学院 2014.10,第6讲 事务和并发控制,简介 事务 嵌套事务 锁 乐观并发控制 时间戳排序 并发控制方法的比较 小结,2,简介,事务和并发控制在服务器管理共享对象时的应用 事物定义了一个服务器操作序列 嵌套事务定义了若干事务之间的嵌套结构，在分布式系统中可以具有更高的并发度 所有的并发控制协议都是基于串行相等的标准，起源于用于解决操作间冲突的规则： 锁用于在多个事务访问同一个对象时，根据这些操作访问同一对象的先后顺序给事务排序 乐观并发控制不会阻塞事务运行，只是在提交时通过检查来确定已执行的操作是否存在冲突 时间戳排序利用
2、时间戳将访问同一对象的事务根据其起始时间进行排序,3,简介,事务的目标 在多个事务访问对象以及服务器面临故障的情况下，保证所有由服务器管理的对象始终保持一个一致的状态。 并发控制 增强可靠性 可恢复对象,在服务器崩溃后恢复的对象 利用持久存储保存状态信息,4,简介,银行事务事例,deposit(amount) /向帐户存amount数量的钱 withdraw(amount) /从帐户中取amount数量的钱 getBalance() - amount /返回帐户中余额 setBalance(amount) /将帐户余额设置成amount,create(name) - account /用给定的
3、用户名创建一个新帐户 lookUp(name) - account /根据给定的用户名查找帐户，并返回该帐户的一个引用 branchTotal() - amount /返回支行中所有帐户余额的总和,Branch接口中的操作,5,简介,简单的同步机制(无事务) 服务器上的原子操作 - 使用多线程可提高服务器的性能 - 采用锁机制保证线程同步 - 原子操作：免受其它线程中执行的并发操作干扰的操作 通过服务器操作的同步加强客户的协同 - 互斥 - 生产者消费者 - Java中的wait和notify方法,6,简介,事务的故障模型Lampson模型 对持久性存储的写操作可能发生故障 - 写操作无效或写
4、入错误的值 - 文件存储可能损坏 - 读数据时可根据校验和发现损坏数据 服务器可能偶尔崩溃 - 进程崩溃后，根据持久存储中的信息恢复 - 服务器不会产生随机故障 消息传递可能有任意长时间的延迟 - 消息可丢失、重复或者损坏 - 接收方能够检测受损消息,7,第八章 事务和并发控制,简介 事务 嵌套事务 锁 乐观并发控制 时间戳排序 并发控制方法的比较 小结,8,事务,事务的概念 以原子方式执行的一系列操作，即 1. 它们不受其它并发客户操作的干扰 2. 所有操作或者全部成功完成，或者服务器出现故障时，对所有操作不产生任何影响 银行事务示例,Transaction T: a.withdraw(10
5、0); b.deposit(100); c.withdraw(200); b.deposit(200);,9,事务,事务的起源 数据库的操作 将数据库的数据由一个一致性状态转化到另一个一致性状态 全有或全无：或者完全成功，或者不留下任何效果 故障原子性 即使服务器崩溃，事务的效果也是原子的。 持久性 一旦事务完成，它的所有效果将被保存到持久存储中 隔离性 每个事务的影响不受其它事务的影响,10,事务,为了支持故障原子性和持久性，对象必须是可恢复的 支持事务的服务器必须有效地对操作进行同步以保证事务之间的隔离性 任何支持事物的服务器的目标：最大化并发度,11,事务,使用一个事务 事务协调者 -
6、作用 创建和管理事务 - 示例,openTransaction() - trans; 开始一个新事务，并返回该事务的唯一TID， TID用于事务的其它操作。 closeTransaction(trans) - (commit, abort); 结束事务：若返回commit，则成功提交；否则返回abort，标示放弃。 abortTransaction(trans); 放弃事务。,12,事务,事务的执行历史 成功执行：close结束 执行失败 客户放弃 服务器放弃 服务进程崩溃 新的替代服务器放弃所有未完成的事务，恢复到最新提交后的事务的状态 客户等待超时，或继续事务时收到动作异常通知,13,事务
7、,14,事务,并发控制(一) 更新丢失问题 初值：帐户A、B、C分别为$100、$200、$300 操作：两次转帐(A、CB)，每次转帐金额为B当前帐户余额的10% 期望结果：B的终值应为$242,15,事务,16,事务,并发控制(二) 不一致检索 初值：帐户A、B分别为$200、$200 操作：转帐+查询银行所有帐户的总余额 期望结果：总余额为$400,17,事务,并发控制(三) 串行等价性 - 多事务正确运行效果推断 若每个事务知道它单独执行的正确效果，则可以推断出这些事务按某种次序一次执行一个事务的效果。 - 串行等价的交错执行 并发事务交错执行操作的效果等同于按某种次序一次执行一个事务
8、的效果。 - 使用串行等价性作为并发执行的判断标准，可防止更新丢失和不一致检索问题。,18,事务,19,事务,20,事务,并发控制(三) 冲突操作 - 冲突 两个操作的执行效果和它们的执行次序相关 - Read和Write操作的冲突规则,21,事务,并发控制(三) 冲突操作(续) - 串行等价性 两个事务串行等价的充要条件是，两个事务中所有的冲突操作都按相同的次序在它们访问的对象上执行。,22,事务,非串行等价地执行事务示例 事务T：x=read(i); write(i,10); write(j,20)； 事务U：y=read(j); write(j,30); z=read(i)； 事务T、事
9、务U串行等价需满足下列条件之一： 事务T在事务U之前访问i，并且事务T在事务U之前访问j 事务U在事务T之前访问i，并且事务U在事务T之前访问j,23,事务,并发控制(四) 并发控制协议 - 依据 串行等价性 - 目的 将访问对象的并发事务串行化 - 方法 锁 乐观并发控制 时间戳排序,24,事务,事务放弃时的恢复(一) 脏数据读取 某个事务读取了另一个未提交事务写入的数据,事务T放弃时的脏数据读取,25,事务,事务放弃时的恢复(二) 事务可恢复性 策略：推迟事务提交，直到它读取更新结果的其它事务都已提交。 连锁放弃 - 某个事务的放弃可能导致后续更多事务的放弃 - 防止方法：只允许事务读取已
10、提交事务写入的对象,26,事务,事务放弃时的恢复(三) 过早写入 - 一些数据库在放弃事务时，将变量的值恢复到该事务所有wtrite操作的“前映像”。 - 为了保证使用前映像进行事务恢复时获得正确的结果，write操作必须等到前面修改同一对象的其它事务提交或放弃后才能进行。,27,事务,事务放弃时的恢复(四) 事务的严格执行 - 严格执行：read和write操作都推迟到写同一对象的其它事务提交或放弃后进行 - 可以真正保证事务的隔离性 临时版本 - 目的：事务放弃后，能够清除所有对象的更新 - 方法 事务的所有操作更新将值存储在自己的临时版本中 事务提交时，临时版本的数据才会用来更新对象,2
11、8,第八章 事务和并发控制,简介 事务 嵌套事务 锁 乐观并发控制 时间戳排序 并发控制方法的比较 小结,29,嵌套事务,嵌套事务 允许事务由其他事务组成 顶层事务和子事务 嵌套事务间：启动关系 嵌套事务的并发和故障处理 子事务对父事务是原子的 同一层次的事务可以并发，公共对象的访问是串行的 每一个子事务可独立的出现故障 子事务放弃时，父事务可选择其他子事务完成,30,嵌套事务,31,嵌套事务,优点 并发度高 子事务可并发运行 健壮性强 子事务可以独立提交和放弃 提交规则 事务在它的子事务完成以后，才能提交或放弃 子事务完成后，可独立决定是暂时提交或放弃 父事务放弃时，所有的子事务都被放弃 若
12、子事务放弃，则父事务可以决定是否放弃 若顶层事务提交，则所有暂时提交的事务将最终提交,32,第八章 事务和并发控制,简介 事务 嵌套事务 锁 乐观并发控制 时间戳排序 并发控制方法的比较 小结,33,锁,互斥锁是一种简单的事务串行化实现机制 事务访问对象前请求加锁 若对象已被其它事务锁住，则请求被挂起，直至对象被解锁 使用示例,34,锁,35,锁,两阶段加锁 目的：保证两个事务的所有的冲突操作对必须以相同的次序执行 增长阶段：不断获取新锁 收缩阶段：释放锁 严格的两阶段加锁 目的：防止事务放弃导致的脏数据读取、过早写入等问题 方法：所有在事务执行过程中获取的新锁必须在事务提交或放弃后才能释放,
13、36,锁,读锁和写锁 目的：提高并发度 支持多个并发事务同时读取某个对象 允许一个事务写对象 事务的操作冲突规则 如果事务T已经对某个对象进行了读操作，那么并发事务U在事务T提交或放弃前不能写该对象。 如果事务T已经对某个对象进行了写操作，那么并发事务U在事务T提交或放弃前不能写或读该对象。 读锁和写锁的兼容性,37,锁,38,锁,锁的实现 Lock类的一个实例 - 被锁住对象的标示符 - 当前拥有该锁的事务的标示符 - 锁的类型,39,锁,public class Lock private Object object; / the object being protected by the
14、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.i
15、sEmpty() / 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(
16、); ,40,public synchronized void release(TransID trans ) holders.removeElement(trans); / remove this holder / set locktype to none notifyAll(); ,锁,锁的实现(续) LockManager类 所有的事务要求加锁和解锁的请求都被送往类LockManager的某个实例。,41,锁,public class LockManager private Hashtable theLocks; public void setLock(Object object, TransID trans, LockType lockType) Lock foundLock; synchronized(this) / find the lock associated wi
