事务和并发控制

1、事务和并发控制事务和并发控制事务和并发控制n事务事务n锁锁n乐观并发控制乐观并发控制n时间戳排序时间戳排序n并发控制方法的比较并发控制方法的比较n小结小结事务事务n事务事务由客户定义的针对服务器对象的一组操作，它们组成一个不可分割的单元，由服务器执行。 n事务的目标事务的目标 在多个事务访问对象以及服务器面临故障的情况下，保证所有由服务器管理的对象始终保持一个一致的状态。 并发控制并发控制n在多用户和网络环境下，数据库是一个共享资源，多个用户或应用程序同时对数据库的同一数据对象进行读写操作，这种现象称为对数据库的并发操作。n显然并发操作可以充分利用系统资源，提高系统效率n虽然如此，但是如果对并

2、发操作不进行控制会造成一些错误。对并发操作进行的控制称为并发控制。并发控制机制是衡量一个DBMS的重要性能指标之一事务事务n全有或全无：或者完全成功，或者不留下任何效果全有或全无：或者完全成功，或者不留下任何效果n故障原子性：事务中包括的诸操作要么都做，要么都不做，即使服务器崩溃，事务的效果也是原子的。n一致性：事务执行的结果必须使系统处于一个一致性状态。当系统中只包含成功事务提交的结果时，就说系统处于一致性状态n持久性一旦事务完成，它的所有效果将被保存到持久存储中n隔离性隔离性每个事务的影响不受其它事务的影响ACID：原子性，一致性，隔离性，持久性事务事务nAccount接口中的操作接口中的

3、操作nBranch接口中的操作接口中的操作deposit(amount) /向帐户存amount数量的钱withdraw(amount) /从帐户中取amount数量的钱getBalance() - amount /返回帐户中余额setBalance(amount) /将帐户余额设置成amountcreate(name) - account/用给定的用户名创建一个新帐户lookUp(name) - account /根据给定的用户名查找帐户，并返回该帐户的一个引用 branchTotal() - amount /返回支行中所有帐户余额的总和事务事务n并发控制并发控制协议都是基于串行相等的标准，

4、源于用来解决操作冲突的规则。n锁n乐观并发控制n时间戳排序事务：事务：并发操作不加以限制，会产生数据不一致性问题成功执行被客户放弃被服务器放弃 openTransaction openTransactionopenTransaction操作操作操作 操作操作操作 服务器放弃事务操作操作向客户报告ERRORcloseTransaction abortTransaction更新丢失更新丢失假设某产品库存量为50，现在购入该产品100个，执行入库操作，库存量加100；用掉40个，执行出库操作，库存量减40。分别用T1和T2表示入库和出库操作任务。同时发生入库（T1）和出库（T2）操作，这就形成并发操

5、作。T1读取库存后，T2也读取了同一个库存；T1修改库存，回写更新后的值；T2修改库存，也回写更新后的值。此时库存为T2回写的值，T1对库存的更新丢失。如表所示T1和T2的并发操作执行顺序，发生了“丢失更新”错误。更新丢失更新丢失顺序顺序 任务任务操作操作库存量库存量 1T1读库存量 502T2读库存量503T1库存量=50+100 4T2库存量=50-40 5T1写库存量 1506T2写库存量 10更新丢失更新丢失n更新丢失问题初值：帐户A、B、C分别为$100、$200、$300操作：两次转帐，事务T将资金由账户A转到账户B，事务U将资金由账户C转到账户B，两次转账的金额都是当前B账户余额

6、的10%) 期望结果：B的终值应为$242事务事务事务事务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();$200balance = b.getBalance();$200b.setBalance(balance*1.1);$220b.setBalance(balance*1.1);$

7、220a.withdraw(balance/10) $80c.withdraw(balance/10)$280事务事务- -并发控制并发控制n不一致检索初值：帐户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

8、()b.deposit(100)$300事务事务- -并发控制并发控制n串行等价性- 事务具有相同效果读操作返回相同的值，并且事务结束时，所有对象的实例变量也具有相同的值。 - 使用串行等价性作为并发执行的判断标准，可防止更新丢失和不一致检索问题。事务事务事务事务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.getB

9、alance()$200b.setBalance(balance*1.1)$220balance = b.getBalance()$220b.setBalance(balance*1.1)$242a.withdraw(balance/10) $80 c.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.

10、getBalance()$400total = total+c.getBalance().事务事务- -并发控制并发控制n冲突操作- 冲突两个操作的执行效果和它们的执行次序相关- Read和Write操作的冲突规则不同事务的操作是否冲突原因readread否由于两个read操作的执行效果不依赖这两个操作的执行次序 readwrite是由于一个read操作和一个write操作的执行效果依赖于它们的执行次序 writewrite是由于两个write操作的执行效果依赖于这两个操作的执行次序事务事务n冲突操作(续)- 串行等价性两个事务串行等价的充要条件是，两个事务中所有的冲突操作都按相同的次序在它们

11、访问的对象上执行。- 非串行等价地执行事务示例事务T：x=read(i); write(i,10); write(j,20)； 事务U：y=read(j); write(j,30); z=read(i)；事务事务事务事务T: 事务事务U: x = read(i)write(i, 10)y = read(j)write(j, 30)write(j, 20)z = read (i)事务事务n事务T对变量i的访问都在事务U对i的访问之前进行，事务U对变量J的访问都在事务T对j的访问之前进行n这样两个对象的冲突操作并未按照相同次序进行n串行等价性需满足以下之一： (1)事务T在事务U之前访问i,并且事

12、务T在事务U之前访问j (2)事务U在事务T之前访问i,并且事务U在事务T之前访问j事务事务- -事务放弃时的恢复事务放弃时的恢复n脏数据读取某个事务读取了另一个未提交事务写入的数据事务事务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) $13

13、0commit transactionabort transaction事务T放弃时的脏数据读取事务事务- -事务放弃时的恢复事务放弃时的恢复n事务可恢复性 如果某个事务访问了被放弃事务的更新结果，并且已经提交，那么服务器的状态就不可恢复。为了确保不发生这种情况，方法是：策略：推迟事务提交，直到它读取更新结果的其它事务都已提交。n连锁放弃- 某个事务的放弃可能导致后续更多事务的放弃 - 防止方法：只允许事务读取已提交事务写入的对象，为了保证这一点，读某对象的操作必须推迟到写该对象数据的事务被提交或放弃事务事务- -事务放弃时隐含的另一种结果事务放弃时隐含的另一种结果n过早写入- 一些数据库在放

14、弃事务时，将变量的值恢复到该事务所有write操作的“前映像”。 - 为了保证使用前映像进行事务恢复时获得正确的结果，write操作必须等到前面修改同一对象的其它事务提交或放弃后才能进行。事务事务T: a.setBalance(105)事务事务U: a.setBalance(110)$100a.setBalance(105)$105a.setBalance(110)$110事务事务- -事务放弃时的恢复事务放弃时的恢复n事务的严格执行 - 严格执行：read和write操作都推迟到写同一对象的其它事务提交或放弃后进行 - 可以真正保证事务的隔离性n临时版本- 目的：事务放弃后，能够清除所有对象

15、的更新 - 方法事务的所有操作更新将值存储在自己的临时版本中事务提交时，临时版本的数据才会用来更新对象第第5 5章章 事务和并发控制事务和并发控制n事务事务n锁锁n乐观并发控制乐观并发控制n时间戳排序时间戳排序n并发控制方法的比较并发控制方法的比较n小结小结锁锁n互斥锁是一种简单的事务串行化实现机制互斥锁是一种简单的事务串行化实现机制n事务访问对象前请求加锁n若对象已被其它事务锁住，则请求被挂起，直至对象被解锁n锁是并发控制的主要手段，有三个阶段锁是并发控制的主要手段，有三个阶段n申请加锁n获得锁n释放锁锁：锁：在在B B上使用锁有效地串行化了对上使用锁有效地串行化了对B B的访问的访问事务事

16、务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)操作锁操作锁openTransactionbal = b.getBalance()锁住Bb.setBalance(bal*1.1)openTransactiona.withdraw(bal/10)锁住Abal = b.getBalance()等待事务T在B上的锁 closeTransaction对A,B解锁 锁住Bb.setBa

17、lance(bal*1.1) c.withdraw(bal/10)锁住CcloseTransaction对B,C解锁 锁锁n一阶段加锁： 事务T在修改数据之前先加写锁，直到事务结束才释放，可以有效防止“丢失更新”问题。 但没有要求对读数据进行加锁，因此不能保证可重复读取和不读“脏“数据n两阶段加锁： 事务T对要修改的数据先加写锁，直到事务结束才释放写锁；对要读取的数据先加读锁，读完后释放读锁锁锁n两阶段加锁两阶段加锁n目的：保证两个事务的所有的冲突操作对必须以相同的次序执行n增长阶段：不断获取新锁n收缩阶段：释放锁n严格的两阶段加锁严格的两阶段加锁n目的：防止事务放弃导致的脏数据读取、过早写入

18、等问题n方法：所有在事务执行过程中获取的新锁必须在事务提交或放弃后才能释放(事务T在读取数据之前先加读锁，修改数据之前先加写锁，直到事务结束才释放所有锁。强调即使读完数据也不释放读锁，从而使得别的事务无法更改数据，因此可重复读)锁锁n读锁和写锁读锁和写锁n目的：提高并发度n支持多个并发事务同时读取某个对象n允许一个事务写对象n事务的操作冲突规则事务的操作冲突规则n如果事务T已经对某个对象进行了读操作，那么并发事务U在事务T提交或放弃前不能写该对象。n如果事务T已经对某个对象进行了写操作，那么并发事务U在事务T提交或放弃前不能写或读该对象。n读锁和写锁的相容性读锁和写锁的相容性锁锁对某一对象被请

19、求的锁 readwrite已设置的锁noneOKOKreadOKwrite等待等待等待锁锁n一阶段加锁可以避免更新丢失问题n两阶段加锁可以避免更新丢失和读”脏“数据问题n严格两阶段加锁可以避免更新丢失、读”脏“数据和不可重复读取问题锁锁n嵌套事务的加锁需求嵌套事务的加锁需求n嵌套事务集- 要求：不能观察到其它嵌套事务集的部分效果 - 实现方法：父事务继承子事务的所有锁，锁的继承从底层向高层传递。n嵌套事务集中的事务 - 要求：不能观察到同一事务集中其它事务的部分效果。 - 实现方法：父事务不允许和子事务并发运行；同层次的事务可并发执行。锁锁n嵌套事务的加锁规则嵌套事务的加锁规则(一一)n获得读

20、锁如果子事务获取了某个对象的读锁，那么其它活动事务不能获取该对象的写锁，只有该子事务的父事务们可以持有该写锁。n获得写锁如果子事务获取了某个对象的写锁，那么其它活动事务不能获取该对象的写锁或读锁，只有该子事务的父事务们可以持有该写锁或读锁。锁锁n嵌套事务的加锁规则嵌套事务的加锁规则(二二)n提交子事务提交时，它的所有锁由父事务继承，即允许父事务保留与子事务相同模式的锁。n放弃子事务放弃时，它的所有锁都被丢弃。如果父事务已经保留了这些锁，那么它可以继续保持这些锁。锁锁n死锁死锁(一一)n死锁场景示例两个事务都在等待并且只有对方释放锁后才能继续执行事务事务T事务事务U 操作操作锁锁操作操作锁锁 a

21、.deposit(100);给A加锁b.deposit(200)给B加写锁 b.withdraw(100)等待事务Ua.withdraw(200);等待事务T在B上的锁在A上的锁锁锁n死锁死锁(二二)n定义死锁是一种状态，在该状态下一组事务中的每一个事务都在等待其它事务释放某个锁。n等待图表示事务之间的等待关系。BA等待持有持有TUUT等待锁：锁：解决死锁问题，一靠预防，二允许发生死锁，再定期诊断解决死锁问题，一靠预防，二允许发生死锁，再定期诊断n预防死锁预防死锁n每个事务在开始运行时锁住它要访问的所有对象- 一个简单的原子操作 - 不必要的资源访问限制 -无法预计事务将访问哪些对象锁锁n死锁

22、检测死锁检测n维护等待图n检测等待图中是否存在环路n若存在环路，则选择放弃一个事务n锁超时锁超时：解除死锁最常用的方法之一n每个锁都有一个时间期限n超过时间期限的锁成为可剥夺锁n若存在等待可剥夺锁保护的对象，则对象解锁。第第5 5章章 事务和并发控制事务和并发控制n事务事务n锁锁n乐观并发控制乐观并发控制n时间戳排序时间戳排序n并发控制方法的比较并发控制方法的比较n小结小结乐观并发控制乐观并发控制n锁机制的缺点锁机制的缺点n维护开销大n会引起死锁n并发度低n乐观策略乐观策略n基于事实：在大多数应用中，两个客户事务访问同一个对象的可能性很低。n方法 - 访问对象时不作检查操作 - 事务提交时检测

23、冲突- 若存在冲突，则放弃一些事务乐观并发控制乐观并发控制n事务的三个阶段事务的三个阶段n工作阶段- 每个事务拥有所修改对象的临时版本 - 每个事务维护访问对象的两个集合：读集合和写集合n验证阶段 - 在收到closeTransaction请求，判断是否与其它事务存在冲突。n更新阶段 - 提交通过验证的事务乐观并发控制乐观并发控制n事务的验证事务的验证n事务号- 每个事务在进入验证阶段前被赋予一个事务号 - 事务号是整数，并按升序分配- 事务按事务号顺序进入验证阶段 - 事务按事务号提交n冲突规则- 事务Tv的验证测试- Ti和Tv之间的存在冲突 - 事务Tv对事务Ti而言是可串行化的 乐观并

24、发控制乐观并发控制TvTi规则writeread 1. Ti不能读取Tv写的对象readwrite 2. Tv不能读取Ti写的对象writewrite 3. Ti不能写Tv写的对象, 并且Tv不能写Ti写的对象与事务的工作阶段相比，由于验证和更新过程较短，每次仅允许一个事务处于验证和更新阶段。乐观并发控制乐观并发控制n向后验证向后验证n检查它的读集是否和其它较早重叠事务的写集是否重叠n算法- startTn: Tv进入工作阶段时已分配的最大事务号码- finishTn: Tv进入验证阶段时已分配的最大事务号码n验证失败后，冲突解决方法放弃当前进行验证的事务Boolean valid = tru

25、eFor ( int Ti = startTn +1; Ti = finishTn; Ti +) if (read set of Tv intersects write set of Ti) valid = false乐观并发控制乐观并发控制较早提交的事务工作阶段验证阶段更新阶段T1Tv正在验证的事务T2T3以后的活动事务active1active2向后验证过程必须比较向后验证过程必须比较Tv的读集和的读集和T2、T3的写集的写集向后验证需要维护已提交事务的多个写集合向后验证需要维护已提交事务的多个写集合n向后验证向后验证n事务的验证过程 - T1、 T2、T3是较早开始的事务 - T1在Tv

26、开始之前提交 - T2、T3在Tv完成其工作阶段前提交 - startTn+1=T2，finishTn=T3 乐观并发控制乐观并发控制n向前验证向前验证n比较Tv的写集合和所有重叠的活动事务的读集合n算法- 设活动事务具有连续的事务标示符active1activeNn验证失败后，冲突解决方法 - 放弃当前进行验证事务 - 推迟验证 - 放弃所有冲突的活动事务，提交已验证事务。Boolean valid = truefor ( int Tid = active1 +1; Tid Tc，那么Tc不能写被Ti读过的对象，这要求Tc该对象的最大读时间戳2.writewrite3.readwrite如果

27、TiTc，那么Tc不能写被Ti写过的对象，这要求Tc已提交对象的写时间戳如果TiTc，那么Tc不能读被Ti写过的对象，这要求Tc已提交对象的写时间戳时间戳排序时间戳排序n时间戳排序的写规则时间戳排序的写规则n是否接受事务Tc对对象D执行的写操作n示例if (Tc D的最大读时间戳 & Tc D的提交版本上的写时间戳) 在D的临时版本上执行写操作，写时间戳置为 Tcelse /* 写操作太晚了 */放弃事务 Tc时间戳排序时间戳排序c) T3写操作 时事务Ti产生的对象 (写时间戳为Ti) T1T2T3T4 时间之前之后T2T2T3时间之前之后T2T2T3T1T1时间之前之后T1T1T4T3T4时间Transacti