分布式数据库及相关问题.ppt

第六部分 分布式数据库及相关技术的讨论（第8-11章内容）,一 分布式数据库概述产生和发展概念和分类体系结构模式结构及独立性。二 分布式数据库系统中存在的技术问题分布式DB的设计分布式DB的查询分布式DB的事务管理及并发。,一 分布式数据库概述,I 分布式数据库的产生及发展,a 经济的发展b 计算机硬件环境及网络的发展,发展历程：产生于20世纪70年代末期，成长于80年代 第一个分布式数据库系统SDD-1是美国计算机公司（CAA）于1976年-1978年设计，79年在DEC-10/20上实现。德国斯图加特大学研制的porel系统美国IBM的R*和system R美国加大学伯克利分校的Ingres法国INRA研制的SIRIUS-DELTA。,1987年：C.J Date提出了完全的，真正的分布式DBS应遵循的12条规则：本地自治性不依赖于中心站点可连续操作位置独立性数据分片独立性数据复制独立性分布式查询独立性分布式事务管理硬件独立性操作系统独立性网络独立性DBMS独立性,II 分布式数据库系统的定义及分类,1 分布式数据库的定义：分布式数据库是一个数据集合，这些数据分布在由计算机网络连接起来的若干节点上，每个节点可以管理本地的数据应用，也可以参与全局数据应用。同时这些数据在逻辑上形成一个整体，由统一的数据库管理系统进行管理。（DDBMS）,注：几个基本的概念站点：计算机连接的一个逻辑单位，称为一个站点。本地（或称：局部）用户、本地应用：一个用户或应用只访问他所注册的那个站点。全局用户、全局应用：一个用户访问涉及两个或两个以上的站点中的数据。全局数据库（GDB）、局部数据库（LDB）：。,2.分布式数据库系统的基本特点：,A 结构特点：物理分布，逻辑相关。,B 应用特点：站点自治。,多处理机系统,C.数据分布透明性：数据的物理独立性内容更丰富，增加了数据分布透明性。-数据的逻辑分片、数据的物理位置分布、数据的复制，对用户透明。,D.集中与自治兼备的数据库系统控制机制.-两个层次的数据共享：局部/全局数据共享。,E.增加数据冗余度。-利用数据冗余提高系统可靠性、可用性和系统性能。,F.事务管理的分布性。-分布环境下，维护事务的原子性、一致性、隔离性和持久性。,3.分布式数据库系统的模式结构,4.分布式数据库系统的分类,A 按局部DBMS的数据模型分类：-同构型：数据模型相同*同质同构：数据模型相同且局部DBMS相同。*异质同构：数据模型相同外交部局部DBMS不同。SDD-1和DDM 美国CCA公司 SYSTEM R*美国IBM公司 POREL 德国斯图加特大学-异构型：数据模型不同 MULTIBASE 美国CCA1981研制 IMADAS:H 佛罗里达大学1984研制 DDTS HONEYWELL公司1980年研制。,B 按全局控制系统类型分类：-全局控制集中型DDBS DDBS的全局控制机制及数据字典位于一个中心站点，由中心站点完成全局事务的协调和局部数据库的转换等所有控制功能。-全局控制分散型DDBS DDBS的全局控制机制及数据字典分散在网络的各个站点上，每个站点都能完成全局事务的协调和局部数据转换。-全局控制可变型（主从型）将站点分成两组，一组都包含全局控制机制和数据字典，另一组为辅助站点，只包含自己的数据应用。,4.分布式数据库管理系统的功能结构：,除了具有集中式DBMS具有的功能外，还要有如下附加 的功能：*数据跟踪*分布式查询处理能力*分布式事务管理的能力*复制数据的能力*安全性*分布式目录管理,二.分布式数据库系统中存在的技术问题：,1 分布式数据库系统的设计-全局模式的设计-数据分片，分布 2 分布式数据库的查询处理 3 分布式数据库的事务管理及并发控制 4 分布式数据库的可靠性 5 异构数据库的连接 6 安全性 7 目录管理,1.分布式数据库设计,一 方法：根据设计是基于现存的数据系统还是构造一个全新的数据库系统，有两种方法创建分布式数据库：组合法：基于现有的系统，建立一个协调管理系统。-采用自底向上的方式构建 重构法：创建全新的数据库系统-自顶向下的方式构建,二 分布式数据库设计的内容：1.数据库设计基础-需求分析 1）数据需求 2）应用需求 应用的原发站点：发出应用请求的站点 应用在站点被激活的频率 应用对数据对象访问次数、类型和分布统计,2.数据库设计（设计的核心任务）全局模式设计 局部数据库设计 数据分片设计 片段的位置分配设计,三 分布式数据库设计的目标：确保数据库数据和应用具有最大程度的本地性。分布式数据的可用性和可靠性 工作负荷分布 存储的能力和费用,四 自顶向下的方式构建分布式数据库,1 设计的步骤：,2 数据库的分片设计,（1）.什么叫“片段”？指在分布式数据库系统中，某一站点上存储的数据集合。,（2）.分片设计的目的？产生全局数据的一个合理的划分，从而使每个站点只获得它所需要的数据，最大可能保证应用的本地性。,（3）分片应遵循的一般规则：设：R=R1,R2,Rn 1）完整性 即，tR,则，必有t Ri(i=1,2,n)2）可重构性 即，R=Ri(i=1,2,n)或R=Ri(i=1,n)3）不相交性 即，Ri Rj=(i,j=1,n,且i j）或Ri Rj=主码属性(i,j=1,n,且i j）,（4）分片的基本类型和方法 水平分片，垂直分片，混合分片,A 水平分片：对全关系进行选择操作，把具有相同性质的元组进行分组，构成若干不相交的子集。初级分片和导出分片,初级分片：以关系自身属性性质分组,例1 S(S#,Sname,Age,Sex),define fragment S1 asselect*from S where Sex=M；,define fragment S2 asselect*from S where Sex=F；,导出分片：用其它关系的属性对某一全关系进行分组,例2 设：全局关系 SC(S#,C#,Grade)S(S#,Sname,Age,Sex),设计需求：按S的“性别”属性（Sex）去划分SC,Define fragment SC1 as select SC.S#,C#,Grade from SC,S where SC.S#=S.S#and S.Sex=M,Define fragment SC2 as select SC.S#,C#,Grade from SC,S where SC.S#=S.S#and S.Sex=F,B 垂直分片：利用投影操作把全关系的属性分成若干组，目标是把频繁使用的属性聚集在一起，且各片段只在键属性下重叠。,例3 设：全局关系EMP(E#,Name,Dept,Job,Sal,tel)Key=E#,垂直分片：EMP1(E#,Name,Sal,tel)EMP2(E#,Dept,Job),3 数据库片段位置分配的设计,两种方式：非冗余分配：一个片段映射到一个站点 冗余分配：一个片段映射到多个站点,非冗余“最佳适应”分配法：计算：Bij=k(Fkj*Nki)即，计算所有的应用在站点j上访问片段i 的总次数。对所有站点j确定j,使得Bij=max(Bij)即，把片段Ri分配到有最大访问次数的站点j。i-片段序号j-站点序号k-应用序号Fkj-应用k在站点j上激活的频率Rki-应用k对片段i 进行检索访问的次数(Read)Uki-应用k对片段i 进行更新访问的次数Nki=Rki+Uki-应用k对片段i进行访问的总次数,冗余分配比较复杂，一般采用下列方法之一进行估算：-所有得益站点法：-附加复制法,（1）“所有得益站点”法,对所有站点确定非冗余分配方案。,从全部结点中选择一组站点，使得给这组站点分配片段Ri的一个拷贝所得到的检索效益，大于从其它站点对Ri实施更新的代价。,把片段Ri拷贝分配给该组站点,（2）附加拷贝法,对所有站点确定非冗余分配方案。计算把片段Ri分配给所有站点所能得到的总效益fi（以及一个站点分得Ri所得到的效益）从分得片段Ri能够获取最大益处的站点起，对各站点依次附加片段Ri的一个拷贝，直到增加片段Ri不能使系统得到明显效益（或者说效益增大“接近”fi）为止。,总结：数据库片段及位置分配的设计所需要 的参数均从应用需求中得来，总结这些参数可用如下三个表表达：A 频率表：各站点每一应用激活的次数B 划分表：各实体的潜在水平分片规则C 极化表：给定站点发出一给定应用访问一给定片段的概率,频率表,划分表,极化表,分布式数据库设计的一个例子,订票系统维护分布在三个网络站点（与机场1，2，3处于同一地理区域）上的数据库。数据库存储机场规程、班机起降和旅客订票等数据。,（1）概念设计-全局概念模式（E-R图）,（2）收集数据与其最相关的应用知识-用操作模式表示,a 订票:用于旅客预订机票。,b 登记:用于旅客登机登记任务记录。,c 起飞应用:查询即将从一个机场起飞的30个班机信息。,（3）在操作模式的基础上，对每一实体估算应用的定量数据，建立逻辑访问表,例“班机”实体逻辑访问表,（4）分布需求分析,a.频率表：调研并给出在三个站点上使用各个应用的频率（激活的次数）,b.划分表：分析各个实体各种可能的分片方式及其选择性,*基本划分,*导出划分,注释表：,c.极化表：调研并给出从一个站点发出一个应用所需要访问某片段的概率。,（5）飞机订票系统的分布式设计,a.为各个实体选择合适的分片,原则:满足本地性，不造成应用困难。,对本例来予，各个实体采用水平分片：,“机场”由基于区域的基本水平分片（片段(F1F3)：机场1，机场2，机场3）,“班机”由基于起飞机场区域的导出水平分片（片段(A1A3)：班机1，班机2，班机3）,“旅客”由基于旅客订票涉及的班机起飞机场所在区域的导出水平分片（片段(P1P7)：旅客1，旅客2，旅客3，旅客7）,b.进行片段的非冗余分配：,1）站点1：机场1，班机1，旅客12）站点2：机场2，班机2，旅客2 旅客4，旅客6，旅客7,3）站点3：机场3，班机3，旅客3 旅客5,根据频率表和极化表,c.进行片段的冗余分配：根据应用可以将旅客分配在两个站点上，旅客7分配在三个站点上。,（6）重构局部模式,本节要点,1.理解分布式数据库系统的基本概念及特征，总结分布式数据库分片设计方法。熟练掌握使用SQL语句，定义全局关系模式的分片方法。2.总结“自顶向下”设计分布式数据库的方法。掌握从设计全局设计模式到各站点上局部模式的分布设计方法。3.理解分布式数据库片段分配设计方法的思想。,2.分布式数据库查询处理,一、分布式查询处理的步骤,查询分析,若该查询属于局部查询，则执行局部查询处理后，即可结束。,查询分解,把全局查询或远程查询转换成定义在全局关系上的关系代数表达式，并优化该表达式。,查询本地化,把一个全局关系上的查询，转化为对片段的局部查询。,全局查询优化：,找出对各个片段局部查询结果之间的最佳操作次序，使得代价最小。其重点在连接运算和并运算的优化,局部优化：,由确定的片段所在站点执行,二、分布式查询处理的代价QC估算：QC=I/O+通信代价T,*通信代价T估算,T=传输次数（每次传输延迟时间+每次传输数据量/数据传输速率）=传输次数（C0+X/D）,三、分布式查询策略的重要性：,例设：教学数据库中：,S(S#,Sname,Age,Sex)10,000个元组，存放在A站点（男/女各一半）SC(S#,C#,Grade)1,000,000个元组，存放在A站点（每人选课100门）C(C#,Cname,Teacher)100,000个元组，存放在B站点假设：每个元组的长度为100 bit;通信系统传输速率为10,000bit/秒；每次通信延迟时间为1秒。,查询：选修课名Maths 的男生的学号和姓名,对于本例，C0=1秒，D=10,000 bit/秒,解：SQL语句是：SELECT S.S#,Sname FROM S,SC,C WHERE S.S#=SC.S#AND SC.C#=C.C#AND SEX=M AND Cname=Maths,策略1：把关系C传到A站点；在A站点进行处理。,T1=1+(100,000*100)/10,000 16.7(分),策略2：先在A站点找出男生选课情况（每人平均选100门课），再根据C#向B站点核查这些男生的选课是否是Maths。(结果在A站点),T3=2*500,000*1秒 11.6(天),策略3：先在B站点找出Maths元组（假设最多有10门），再把查找结果传到A站点，在A站点继续执行查询处理。,T6=1+10*100/10,000 1秒,四、基于关系代数等价变换的查询优化,例1 S(S#,Sname,Age,Sex)SC(S#,C#,Grade)其中，S 和SC都采取水平分片：,用户查询：SELECT distinct Sname FROM S,SC WHERE S.S#=SC.S#and Sex=M and Grade 90,转成关系代数表达式：,Sname(Sex=M Grade 90(S.S#=SC.S#(S SC),把关系代数表达式转换成查询树并优化,从全局查询到片段查询的转换,优化片段查询树,a.对于水平分片，检查选择运算（）与水平分片的条件（谓词）。b.对于垂直分片，注意消去不提供连接运算后所需要属性的分支。,例2 设：全局关系:EMP(E#,Ename,Sal,Dept,Dname)现采取垂直分片：,查询问题：,SELECT Ename,SalFROM EMP,查询关系代数表达式,Ename,Sal(EMP),五 基于半连接算法的全局查询优化,1、半连接运算:由投影和连接操作导出的一种关系代数操作。,设：关系R和S在属性R.A=S.B上的半连接操作记为：,或者:,2、利用半连接运算实现连接运算,或者:,3.采用半连接运算实现连接运算的代价及优化,令：tuple(R)表示关系R的元组数 size(B)表示属性B的数据长度,现假设，用户希望在站点2上得到R 与 S自然连接的结果,(1)B(S),(2)传送B(S),(4)传送R,总代价：T半=2C0+C1*size(B)*tuple(B(S)+size(R)*tuple(R),采用半连接操作优化的原理：两个关系进行连接操作之前，去掉无用的无组，减少数据传输量。,采用直接连接运算的总代价：,T=C0+C1*size(R)*tuple(R),选择半连接实现连接运算的原则：经半连接操作产生少量元组。,4.查询优化策略,1）计算各种半连接运算的代价。,2）计算直接连接运算的代价。,3）比较并选出最优者。,六 基于直接连接算法的查询优化,1、利用站点依赖信息的连接算法,其成立的条件是什么?,条件：A(F11)A(F12)=,A(F21)A(F22)=,A(F11)A(F22)=,A(F12)A(F21)=,站点依赖：设：RiA、RjA、SiA、SjA分别表示关系R、S在站点i、j的A属性上的取值。若对于i j,有：RiA SjA=,则称关系R和S在属性A上站点依赖。,性质：若关系R和S在属性A上站点依赖，则：,推论：,*如果R和S在属性A上站点依赖，B A,则，R和S在属性B上站点依赖。,*如果R和S在属性A上站点依赖，S和T在属性B上站点依赖，则：,使用站点依赖算法实现直接连接运算的优点:,1）无数据传送,2）可进行并行计算,3）可利用本地索引,在查询优化过程中，可以判断什么时候使用站点依赖算法（P87）,2、分片和复制算法,当查询不能在无数据传送方式下处理，可采用分片和复制算法，算法的原理：选择一组站点，将查询中的某一个关系的所有片段分布到这些站点上，然后把查询中的其余关系复制到每一个选定的站点上。,优点：1）可进行并行计算 2）在一定程度上可利用本地索引,选择方法：从假定某一关系分片，其余关系复制，计算代价，然后再选择另一关系为分片，最后从中选择代价最小的方案。,本节重点,1.总结分布式数据库查询优化的主要步骤，并与集中式数据库查询优化相比较。2.总结利用半连接算法实现直接连接运算的全局查询优化方法特点。在什么条件下可以利用半连接算法实现直接连接运算？,3.分布式事务管理及恢复的讨论,一、分布式事务概述,1.事务的特点,分布式数据库的事务称为全局事务。一个全局事务在执行时分解为由若干与相应站点有关的操作序列组成的“子事务”。,1.原子性 2.一致性（或可串行性）3.隔离性 4.持久性 5.系统效率6.系统可用性：分布式事务既不能影响本站点上事务的执行，也不能影响其它站点上事务的执行,Begin Transaction 开始事务,T1T2Tn,Commit/Abort(或Rollback)结束事务,子事务或操作序列,全局事务,3 分布式事务代理执行机制,2.分布式事务的结构,事务代理的概念：一个事务代理就是一个站点上的一个进程,应用请求（源站点,总代理根代理）,Rollback,Commit,总代理（根代理）,子事务1失败,子事务1成功,子事务代理n,子事务代理1,Begin Transaction,子事务n失败,子事务n成功,例银行转帐事务：把帐号FROM_ACC上数量为AMOUNT的资金，转入帐号TO_ACC。,全局应用事务：,read(AMOUNT,FROM_ACC,TO_ACC);begin transactionselect BALANCE into FROM_AMOUNTfrom ACCOUNT_TABLEwhere ACCOUNT_NO=FROM_ACC;if FROM_AMOUNT-AMOUNT 0then abortelse beginupdate ACCOUNT_TABLEset BALANCE=BALANCE-AMOUNTwhere ACCOUNT_NO=FROM_ACC;update ACCOUNT_TABLEset BALANCE=BALANCE+AMOUNTwhere ACCOUNT_NO=TO_ACC;commitend,设：转出帐户在源站点上。,ROOT_AGENT:,read(AMOUNT,FROM_ACC,TO_ACC);begin transactionselect BALANCE into FROM_AMOUNTfrom ACCOUNT_TABLEwhere ACCOUNT_NO=FROM_ACC;if FROM_AMOUNT-AMOUNT 0then abortelse beginupdate ACCOUNT_TABLEset BALANCE=BALANCE-AMOUNTwhere ACCOUNT_NO=FROM_ACC;create AGENT;send to AGENT(AMOUNT,TO_ACC);waittingcommit/abortend,AGENT（子代理）:,begin transactionreceive from ROOT_AGENT(AMOUNT,TO_ACC);update ACCOUNT_TABLEset BALANCE=BALANCE+AMOUNTwhere ACCOUNT_NO=TO_ACC;send to ROOT_AGENT(SUCCESS/FAIL)waittingcommit/abort,二.分布式事务的两阶段提交协议2-PC:Two-Phase Commitment Protocal,两阶段提交协议的活动机制：,写end of trans到日志,两阶段提交协议的执行过程：,1）表决阶段：对当前事务形成一个决定。协调者：写“开始事务”日志；向各个参与者发出“准备”命令；进入等待状态。对于每一个参与者 参与者接收“准备”消息；参与者检查子事务，确定是否提交子事务：Case1:可以提交子事务：参与者写“就绪”日志；向协调者发“建议提交”消息；参与者进入“就绪”状态。Case2:不可以提交子事务：参与者写“撤消”日志；向协调者发“建议撤消”消息；参与者进入“撤消”状态。,协调者接收到所有参与者的回答后，作出决定：Case1:若所有参与者发出“建议提交”的消息，则，协调者作出提交全局事务的决定。协调者写提交日志；协调者发出“全局提交”消息；协调者进入“提交”状态。Case2:若发现某参与者发出“建议撤消”的消息，则，协调者作出撤消全局事务的决定。协调者写撤消日志；协调者发出“全局撤消”消息；协调者进入“撤消”状态。“一票否决”制！,2）执行阶段,对于每一个处于“就绪”状态的参与者：参与者根据协调者发出的全局事务处理指令，或者撤消子事务，或者提交子事务,参与者发出“确认”(ACK)收到全局事务处理指令消息。参与者进入“撤消”或“提交”状态。协调者写“结束事务”日志。,两阶段提交协议的特点：参与者有权单方面撤消事务。参与者作出“建议提交”或“建议撤消”决定之后，不能“翻悔”。处于“就绪”状态的参与者可能进入提交状态，或撤消状态。协调者和参与者可能进入互相等待状态。,1.试比较集中式、分布式事务的特点。,2.总结分布式数据库2-PC的特点，并指出它所存在的问题。,本节重点,4.分布式数据库并发控制机制,一、分布式并发控制概述,1 分布式并发控制的目的：为并发执行的全局事务，产生一个可串行化调度。,2 局部调度：每个站点上的调度称为局部调度,3 全局调度：数据库系统全局事务的调度。,4全局调度的可串行性局部调度的可串行性！,局部调度的可串行性：全局调度的可串行性？,问题：一个数据对象x，可能存在多个副本,x1,x2,xn。,T1:Read(y);y:=y 15;Write(y);Commit;,T2:Read(y);y:=y*2;Write(y);Commit;,站点1 调度S1=R1,W1,C1,R2,W2,C2,站点2 调度S2=R2,W2,C2,R1,W1,C1,设：站点1，站点2上都有y的副本，且都执行事务T1,T2。,全局调度不可串行！,5.全局调度的冲突可串行性应满足的条件:单副本控制协议,1)每一个局部调度是冲突可串行化的。,2)任意两个冲突操作在它们同时出现的各个局部调度中，必须有相同的执行顺序。,二、并发控制法,并发控制算法,悲观法,乐观法,封锁法,时标排序法,混合法,加锁法,时标排序法,集中式加锁,主副本加锁,分布式加锁,基本时标排序法,多版本时标排序,保守时标排序,1）集中式加锁法:网络中某一个站点被指定为主站点，用于存放整个分布式数据库的加锁表，负责整个系统事务的加锁.,2）主副本加锁法：每个数据对象指定一个主副本，不同数据对象的主副本放在不同站点上。算法：对主副本加锁；执行更新操作；开锁,3）分布式加锁算法：锁的管理由各个站点调度器参与、协调，本地调度器负责本站数据加锁。算法：对全部副本加锁；执行更新操作；开锁,三、分布式数据库并发控制的加锁技术,1.分布式数据库加锁准则,读，锁一个；写，锁全部(ROWA协议)。,遵守锁的相容性规则,遵守两段锁协议（Two Phase Locking-2PL),持有X锁的事务，必须到结束事务才能开锁。,2、死锁管理,1）全局死锁：分布式数据库中，涉及多个站点的死锁称为全局死锁。,站点A,站点B,事务T1持有对X的锁,事务T2持有对Y的锁,事务T2请求对X的锁,事务T1请求对Y的锁,T2等待T1完成释放对X的锁,T1等待T2完成释放对Y的锁,2）全局等待图（GWFG）,站点A:拥有x、y的副本；T1:read(x),write(y)站点B:拥有y、z的副本；T2:read(y),write(z)站点C:拥有z 的副本；T3:read(z),write(x),3）死锁的检测,A 集中式死锁检测法,指定某站点上的锁管理器作为全局死锁检测器 其余站点周期地向全局死锁检测器发送LWFG 全局死锁检测器产生GWFG，并检测有无回路,B 分布式死锁检测法,每个站点都有死锁检测器，负责检测本地可能的死锁。每个站点按照一定规则，向相关站点发送潜在的死锁回路图。,4）死锁的解决,原则：撤消并恢复代价最小的事务。,撤消并恢复年轻的事务。撤消并恢复占用资源较少的事务。撤消并恢复具有最短运行时间的事务。,四 并发控制的时标技术,1.时标:唯一识别一个事务，并用于对事务进行排序的标识符。,2.时标的构成：“本地计数器值，站点标识符,3.时标的创建：一个事务Ti 初始化时，事务管理器给该事务分配一个时标ts(Ti),4.时标排序（TO）规则：,已知Qi和Qj是分别属于事务Ti和Tj冲突操作。,若ts(Ti)ts(Tj),则Qi在Qj之前执行。,5、基本时标法,规则：1）每个事务在本地站点开始时被赋以一个全局唯一的时标。3）事务的每个读或写操作都有该事务的时标。2）如果事务被重新启动，则被赋予新的时标。4）在事务结束之前，不对数据库进行物理操作。5）对于数据库每个数据对象x，记录对它进行读操作和写操作的最大时标RTM(x)和WTM(x),基本时标法的执行过程：1）设TS是对数据对象x进行读操作的当前时标。若TS WTM(x)，则，拒绝该操作；并使发出该操作的事务用新时标重新启动；否则，执行读操作，且使：RTM(x)=max（RTM(x),TS）,2）设TS是对数据对象x进行写操作的当前时标。若TS RTM(x)OR TS WTM(x)，则，拒绝该操作；并使发出该操作的事务用新时标重新启动；否则，执行写操作，且使：WTM(x)=max（WTM(x),TS）,6、保守时标法,特点：采用缓冲区缓冲“年轻”操作，以便尽量消除“拒绝操作”，避免了事务重新启动。,规则：（1）每个事务只在一个站点执行。不激活远程程序，只能向远程站点发出读/写操作请求。（2）每个站点必须按照时标时间的顺序发送读/写数据的请求。对于每个事务的更新操作，必须做到对同一数据对象先读后写。,（3）每个站点都开辟一个缓冲区，用于保存其它站点发来的读/写操作。,保守时标法的执行过程,一旦某个站点上的各个缓冲区队列都不空，即，每个站点至少向该站点发送了一个读和一个写，就停止接收，转入处理缓冲区队列上的操作。,例站点i上缓冲区队列情况如下：,站点1 站点2 站点n,R11R12R13W11,R21R22R23R24W21W22,Rn1Rn2Wn2,读队列,写队列,站点i 上处理缓冲区队列上的操作算法：,重复执行如下步骤，直到没有满足执行条件的 Rij 和Wij，或者至少出现一个读/写队列为空，此时RT/WT=0：,1）令：RT=min(Rij),WT=min(Wij)i：站点序号；j：读/写操作的序号,2）按下列原则处理缓冲区内各个站点读/写队列：*扫描读队列若各队列存在若干个Rij WT,则，按时标顺序逐一执行Rij，并使Rij出队列*扫描写队列若各队列存在若干个Wij RT,则，按时标顺序逐一执行Wij，并使Wij出队列,五 并发控制的乐观方法,乐观方法的特点：1）任何事务在写一个数据项之前，必须首先读该数据项。2）事务在读/计算阶段，在读取一个数据项之后，接着只是做了对该数据项进行写操作所需新值的“准备”，实际上并没有执行物理写盘操作！,读/计算阶段在本站点上：从数据库读入数据；进行计算；准备写数据库的数据新值；形成事务更新表。更新表的内容：1）所有读数据对象及其时标 2）所有写数据对象的新值。3）事务本身的时标。,2.验证阶段：检测事务对数据库的更新是否会导致破坏数据库的一致性。步骤：1）源站点向相关站点发送更新表。2）各站点进行表决，并把表决结果回送源站点。3）源站点作出最终裁决，并把结果通知各站点。,3.写阶段：如果验证获得通过，则提交该事务，否则重新启动事务。,各站点表决原则：,如果更新表中每一个读数据对象的时标，与本站点上同一数据对象的时标都相等，则，该站点投肯定票。/说明两者之间没有发生过其他更新操作！否则，该站点投否定票。,本节重点,1.总结分布式数据库加锁法的特点。,2.总结基本时标法和保守时标法控制并发事务的过程。,3.分析、比较并发控制的时标技术与乐观方法的特点。,