05-事务和并发控制

第5章事务和并发控制第5章事务和并发控制事务锁乐观并发控制时间戳排序并发控制方法的比较小结事务事务由客户定义的针对服务器对象的一组操作，它们组成一个不可分割的单元，由服务器执行。事务的目标在多个事务访问对象以及服务器面临故障的情况下，保证所有由服务器管理的对象始终保持一个一致的状态。事务的故障模型对持久性存储的写操作可能发生故障。服务器可能偶尔崩溃。消息传递可能有任意长的延迟。消息可能丢失、重复或者损害。事务能够处理进程的崩溃故障和通信的遗漏故障，但是不能处理拜占庭故障。事务的原子性对服务器的请求是原子的：1.不受其它并发客户的干扰---隔离性每个事务的影响不受其它事务的影响2.所有操作或者完全成功，或者不留下任何效果故障原子性--即使服务器崩溃，事务的效果也是原子的。持久性--一旦事务完成，它的所有效果将被保存到持久存储中ACID：原子性，一致性，隔离性，持久性事务的三种执行情况成功执行被客户放弃被服务器放弃openTransactionopenTransactionopenTransaction操作操作操作操作操作操作服务器放弃事务操作操作向客户报告ERRORcloseTransactionabortTransaction并发控制更新丢失问题初值：帐户A、B、C分别为$100、$200、$300操作：两次转帐(A、C→B)，每次转帐金额为B当前帐户余额的10%期望结果：B的终值应为$242银行示例函数Account接口中的操作Branch接口中的操作deposit(amount)//向帐户存amount数量的钱withdraw(amount)//从帐户中取amount数量的钱getBalance()-amount//返回帐户中余额setBalance(amount)//将帐户余额设置成amountcreate(name)-account//用给定的用户名创建一个新帐户lookUp(name)-account//根据给定的用户名查找帐户，并返回该帐户的一个引用branchTotal()-amount//返回支行中所有帐户余额的总和更新丢失问题事务T:账户A-账户Bbalance=b.getBalance();b.setBalance(balance*1.1);a.withdraw(balance/10)事务U:账户C-账户Bbalance=b.getBalance();b.setBalance(balance*1.1);c.withdraw(balance/10)balance=b.getBalance();$200balance=b.getBalance();$200b.setBalance(balance*1.1);$220b.setBalance(balance*1.1);$220a.withdraw(balance/10)$80c.withdraw(balance/10)$280并发控制不一致检索初值：帐户A、B分别为$200、$200操作：转帐+查询银行所有帐户的总余额期望结果：总余额为$400不一致检索问题事务V:a.withdraw(100)b.deposit(100)事务W:aBranch.branchTotal()a.withdraw(100);$100total=a.getBalance()$100total=total+b.getBalance()$300total=total+c.getBalance()b.deposit(100)$300串行等价串行等价性：如果并发事务交错执行操作的效果等同于按某种次序一次执行一个事务的效果，那么这种交错执行是一种串行等价的交错执行。使用串行等价性作为并发执行的判断标准，可防止更新丢失和不一致检索问题。串行等价避免更新丢失事务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()$200b.setBalance(balance*1.1)$220balance=b.getBalance()$220b.setBalance(balance*1.1)$242a.withdraw(balance/10)$80c.withdraw(balance/10)$278串行等价避免不一致检索事务V:a.withdraw(100);b.deposit(100)事务W:aBranch.branchTotal()a.withdraw(100);$100b.deposit(100)$300total=a.getBalance()$100total=total+b.getBalance()$400total=total+c.getBalance()...冲突操作冲突操作：如果两个操作的执行效果和他们的执行次序相关，称这两个操作相互冲突（conflict）。Read和Write操作的冲突规则不同事务的操作是否冲突原因readread否由于两个read操作的执行效果不依赖这两个操作的执行次序readwrite是由于一个read操作和一个write操作的执行效果依赖于它们的执行次序writewrite是由于两个write操作的执行效果依赖于这两个操作的执行次序两个事务串行等价的充要条件是：两个事务中所有的冲突操作都按相同的次序在它们访问的对象上执行。串行等价可作为一个标准用于生产并发控制协议。并发控制协议用于将访问的并发事务串行化。串行等价的充分必要条件三种并发控制方法并发控制并发控制协议都是基于串行相等的标准，源于用来解决操作冲突的规则。锁乐观并发控制时间戳排序非串行等价示例事务T:事务U:x=read(i)write(i,10)y=read(j)write(j,30)write(j,20)z=read(i)事务T：x=read(i);write(i,10);write(j,20)；事务U：y=read(j);write(j,30);z=read(i)；事务放弃时的恢复服务器必须保证事务放弃后，它的更新作用完全取消，而不影响其他事务。1.脏数据读取2.过早写入事务放弃时的恢复1.脏数据读取某个事务读取了另一个未提交事务写入的数据事务T:a.getBalance()a.setBalance(balance+10)事务U:a.getBalance()a.setBalance(balance+20)balance=a.getBalance()$100a.setBalance(balance+10)$110balance=a.getBalance()$110a.setBalance(balance+20)$130committransactionaborttransaction事务T放弃时的脏数据读取事务放弃时的恢复事务可恢复性策略：推迟事务提交，直到它读取更新结果的其它事务都已提交。连锁放弃-某个事务的放弃可能导致后续更多事务的放弃-防止方法：只允许事务读取已提交事务写入的对象事务放弃时的恢复过早写入：数据库在放弃事务时，将变量的值恢复到该事务所有write操作的“前映像”。U提交T放弃，余额应是110，但是T的前影像是100，最终的结果是100的错误值；类似如果T放弃，接着U放弃，余额应是100，由于U的前映像是105，最终的结果是105的错误值。事务T:a.setBalance(105)事务U:a.setBalance(110)$100a.setBalance(105)$105a.setBalance(110)$110事务放弃时的恢复为了保证使用前映像进行事务恢复时获得正确的结果，write操作必须等到前面修改同一对象的其它事务提交或放弃后才能进行。事务放弃时的恢复事务的严格执行-严格执行：read和write操作都推迟到写同一对象的其它事务提交或放弃后进行临时版本-目的：事务放弃后，能够清除所有对象的更新-方法事务的所有操作更新将值存储在自己的临时版本中事务提交时，临时版本的数据才会用来更新对象第5章事务和并发控制事务锁乐观并发控制时间戳排序并发控制方法的比较小结锁互斥锁是一种简单的事务串行化实现机制事务访问对象前请求加锁若对象已被其它事务锁住，则请求被挂起，直至对象被解锁使用示例锁事务Tbalance=b.getBalance()b.setBalance(bal*1.1)a.withdraw(bal/10)事务Ubalance=b.getBalance()b.setBalance(bal*1.1)c.withdraw(bal/10)操作锁操作锁openTransactionbal=b.getBalance()锁住Bb.setBalance(bal*1.1)openTransactiona.withdraw(bal/10)锁住Abal=b.getBalance()等待事务T在B上的锁closeTransaction对A,B解锁锁住Bb.setBalance(bal*1.1)c.withdraw(bal/10)锁住CcloseTransaction对B,C解锁…两阶段加锁为了保证两个事务的所有冲突操作必须以相同的次序执行，每个事务的第一阶段是一个“增长”阶段，事务不断地获取新锁；在第二个阶段，事务释放它的锁，这称为两阶段加锁(two-phaselocking).严格的两阶段加锁所有在事务执行过程中获取的新锁必须在事务提交或放弃后才能释放，称为严格的两阶段加锁。目的是防止事务放弃导致的脏数据读取、过早写入等问题。锁读锁和写锁目的：提高并发度支持多个并发事务同时读取某个对象允许一个事务写对象事务的操作冲突规则如果事务T已经对某个对象进行了读操作，那么并发事务U在事务T提交或放弃前不能写该对象。如果事务T已经对某个对象进行了写操作，那么并发事务U在事务T提交或放弃前不能写或读该对象。读锁和写锁的相容性锁对某一对象被请求的锁readwrite已设置的锁noneOKOKreadOKwrite等待等待等待锁死锁(一)死锁场景示例两个事务都在等待并且只有对方释放锁后才能继续执行事务T事务U操作锁操作锁a.deposit(100);给A加锁b.deposit(200)给B加写锁b.withdraw(100)等待事务Ua.withdraw(200);等待事务T在B上的锁在A上的锁锁死锁(二)定义死锁是一种状态，在该状态下一组事务中的每一个事务都在等待其它事务释放某个锁。等待图表示事务之间的等待关系。BA等待持有持有TUUT等待锁预防死锁每个事务在开始运行时锁住它要访问的所有对象-一个简单的原子操作-不必要的资源访问限制-无法预计将要访问的对象预定次序加锁-过早加锁-减少并发度更新锁避免死锁在数据项上加更新锁的事务可以读该数据项，但该锁与加在同一数据项上的更新相冲突。锁死锁检测维护等待图检测等待图中是否存在环路若存在环路，则选择放弃一个事务锁超时：解除死锁最常用的方法之一每个锁都有一个时间期限超过时间期限的锁成为可剥夺锁若存在等待可剥夺锁保护的对象，则对象解锁。第5章事务和并发控制事务锁乐观并发控制时间戳排序并发控制方法的比较小结乐观并发控制锁机制的缺点维护开销大会引起死锁并发度低乐观策略基于事实：在大多数应用中，两个客户事务访问同一个对象的可能性很低。方法-访问对象时不作检查操作-事务提交时检测冲突-若存在冲突，则放弃一些事务乐观并发控制事务的三个阶段工作阶段-每个事务拥有所修改对象的临时版本-每个事务维护访问对象的两个集合：读集合和写集合验证阶段-在收到closeTransaction请求，判断是否与其它事务存在冲突。更新阶