第11章 分布式数据管理

1、第11章 分布式数据管理分布式系统(十一) 08-062分布式数据库管理主要内容：n共享数据的并发访问控制（访问同步，即状态一致性）；（多个操作对一个数据对象）n分布式数据的复制和一致性（数据同步）；（一个操作对多个数据）n系统失败后的数据恢复（数据可靠性）。基本概念：nDB、DBMS、SQL、关系型、对象型n分布式数据库n不复制、部分复制、完全复制w复制的益处：改进响应、增强可靠性、减少目录管理、易实现负载均衡。分布式系统(十一) 08-063事务事务（Transaction）：一系列逻辑相关的对一个或多个数据对象的操作。n事务保证数据库的一致性，并在有限的时间内结束；n查询是只读事务，更新

2、是至少修改一个数据对象的事务。事务调度：分布式系统中，一组并发事务中操作的交错顺序。分布式系统(十一) 08-064事务有效的事务需要具有原子执行性：n“全或无”操作：要么全部完成，要么一个也不完成；n多个事务并发执行对结果的影响，和这些事务串行执行的效果一样。（合格的事务调度串行事务调度）多个不能满足原子执行性的事务并发操作时可能会产生冲突（不一致的结果状态）：n不一致的检索；n不一致的更新。分布式系统(十一) 08-065事务冲突例事务T1：(A帐户转帐$10到B帐户) begin1 read A (obtaining A_balance)2 read B (obtaining B_bal

3、ance)3 write A_balance - $10 to A4 write B_balance + $10 to B end事务T2：(B帐户取$5) begin1 read B (obtaining B_balance)2 write B_balance - $5 to B end初始：A_balance20， B_balance102个并发事务：分布式系统(十一) 08-066事务冲突例调度1（冲突，不可串行调度）：T1(1) read A (obtaining A_balance)T1(2) read B (obtaining B_balance)T1(3)write A_bala

4、nce - $10 to AT2(1)read B (obtaining B_balance)T2(2)write B_balance - $5 to BT1(4)write B_balance + $10 to B调度2（不冲突，可串行调度）：T1(1) read A (obtaining A_balance)T2(1)read B (obtaining B_balance)T2(2)write B_balance - $5 to BT1(2) read B (obtaining B_balance)T1(3)write A_balance - $10 to AT1(4)write B_ba

5、lance + $10 to B分布式系统(十一) 08-067事务冲突两个事务产生冲突的必要条件：它们在同时操作一个数据对象，且至少有一个操作是写操作。有三种事务冲突存在：nr-w（读-写）冲突nw-r（写-读）冲突nw-w（写-写）冲突分布式系统(十一) 08-068解决事务冲突解决冲突的一个方法是串行执行事务：即一个时刻只执行一个事务。从而确保从一个一致状态转移到另一个一致状态。对n个事务有n！种串行执行调度方案，所有这些方案最终到达同一个一致状态。显然，串行执行事务降低了系统的并发性。另一个方法是通过一个“好的”并发事务调度（即“好的”事务操作的交错顺序）实现串行执行事务同样的结果，这

6、样的调度称为可串行调度。分布式系统(十一) 08-069可串行性理论目标：检查并发事务调度是否为可串行调度，从而得到可串行调度的并发调度。rix、wix表示事务Ti对数据对象x的读和写操作，如：事务：T1=w1xw1yr1zT2=r2zr2yw2xT3=w3zr3zw3x调度：L1=w1xr2zr2yw2xw1yr1zw3zr3zw3x L2=w1xw1yr1zr2zr2yw2xw3zr3zw3x L3=w1xw1yr1zr2zw3zr2yr3zw2xw3x（其中L2是串行调度）分布式系统(十一) 08-0610可串行性理论等价调度的定义：如果调度L有两个操作wix和rjx，我们说rjx从wi

7、x读取当且仅当：（a）wixrjx；（b）没有wkx使wix wkxrjx。两个调度等价当且仅当：（1）两个调度中每个读操作读自同一个写操作；（2）两个调度有同样的最终写。如例中L2=w1xw1yr1zr2zr2yw2xw3zr3zw3xL3=w1xw1yr1zr2zw3zr2yr3zw2xw3x是等价调度。分布式系统(十一) 08-0611可串行性理论当一个并发调度等价于一个串行调度时，它就是可串行调度。利用串行化图检查调度可串行性的方法：一组事务T=T1,T2,Tn，对于一个给定调度L，串行化图定义如下：对某个数据对象x，或者rixwjx，或者wixrjx，或者wixv/2，为了确保读的时

8、候得到最新数据拷贝，需要满足r+wv。（其中v是选票总数，若每个站点的投票权重是1，则即站点总数）。显然对于单写/多读方法r=1，w=v。例：一个7个站点的系统，可以w=4，r=4，即每次写必须至少写4个拷贝，每次读必须至少读4个拷贝；也可以w=6，r=2等。分布式系统(十一) 08-0628选举协议这种方法的一个潜在问题是r、w票数随着v的增长而线性增长。通过分层树结构、多次选举的方法可以有效减少r、w的总数量：（类似于美国总统选举）根簇每层的r=2、w=3，总的r=4、w=9实际节点：叶子 需多次选举，但r、w的总数比一次选举少。分布式系统(十一) 08-0629网络分割的乐观方法：版本号

9、向量本方法首先确保在连通的子网中数据对象拥有最新的版本。网络分割后，不对事务作限制，当不连通子网连接时，比较子网间同一数据对象拷贝的一致性来作相互不一致性检测。版本号向量方法使用一个V=的版本号向量（n是总的站点数），来维护数据对象在子网中的最新版本号。定义：一个向量V支配另一个向量V，如果对所有i，vivi。即V记录的更新是V的一个子集。当不连通子网连接时，如果两个子网的版本号向量没有一个能支配另一个，就表示发生冲突（否则不发生冲突，使用支配地位的版本号向量作为连通后子网的版本号向量）分布式系统(十一) 08-0630版本号向量（例）三个站点A、B、CA,B,CA,B,CA,CBA,CAB,

10、CB,CA,B,C 冲突冲突不冲突不冲突分布式系统(十一) 08-0631网络分割的悲观方法：动态选举（P253）通过动态选举来预防版本号向量法中的冲突发生。分布式系统(十一) 08-0632分布式可靠性协议分布式可靠性技术包括提交、终止和恢复协议。提交协议确保事务在完成后将更新结果可靠地送到分布式数据库（即提交的原子性：要么完全送到，要么完全不送到、分布式事务取消）。通过两阶段提交来保证这种提交的原子性：易失性存储器数据库稳定存储器客户端服务端读取第一阶段提交（第一步复制）第二阶段提交（第二步复制）恢复日志重做日志*日志应该在将更新复制到稳定存储器前先写：恢复日志用于事务失败后的恢复；重做日

11、志用于事务成功、第一阶段提交失败后重做。分布式系统(十一) 08-0633分布式可靠性协议为了减少恢复、重做工作，在日志中使用检查点。检查点检查点故障T1T2T3T4T5T6T7在故障时，其中：子事务T1、T4、T5整个进行撤销（使用恢复日志），T2和T7在最后一个检查点后的操作进行重做（使用重做日志），T3整个进行重做（使用重做日志），T6不需要任何操作。分布式系统(十一) 08-0634集中式的两阶段提交协议分布式事务使用集中方法实现两阶段提交协议。这个协议中，事务的初始发起节点作为协调者（主），其它节点作为参与者（从）。不同之处在于协调者在正式提交前，需要所有分布式事务参与者的确认。n第

12、一阶段：在协调者：/* prec:初始状态(q) */协调者发出commit_request消息给每个参与者,并且等待所有参与者的回答。/* postc:等待状态(w) */在参与者：/*prec:初始状态(q) */接收到commit_request消息，参与者进行如下动作：如果事务在参与者的执行成功了，它写恢复日志和重做日志，发出yes消息给协调者；否则发no消息。/* postc:如果yes，进入等待状态(w)；如果no，进入取消状态(a) */分布式系统(十一) 08-0635集中式的两阶段提交协议n第二阶段：在协调者：/* prec:等待状态(w) */1)如果所有参与者返回yes，协调者向日志中写入commit记录，然后向所有参与者发出commit消息。否则，协调者向所有参与者发出abort消息。/* postc:如果commit，进入提交状态(c)；如果abort，进入取消状态(a) */ 2)如果所有确认在超时期间内收到，协调者向日志写入complete记录；否则发出commit/abort消息给那些没有确认的参与者。在参与者：/* prec:等待状态(w) */1)收到一个commit消息，参与者释放事务执行中的所有资源和锁，发出确认消息。/* postc:提交状态(c) */* prec:取消状态(a) 或者等待状态