1、第六部分第六部分 分布式数据库及相关技术分布式数据库及相关技术的讨论的讨论（第（第8-118-11章内容）章内容）一一 分布式数据库概述分布式数据库概述产生和发展产生和发展概念和分类概念和分类体系结构体系结构模式结构及独立性。模式结构及独立性。二二 分布式数据库系统中存在的技术问题分布式数据库系统中存在的技术问题分布式分布式DBDB的设计的设计分布式分布式DBDB的查询的查询分布式分布式DBDB的事务管理及并发。的事务管理及并发。一一 分布式数据库概述分布式数据库概述I I 分布式数据库的产生及发展分布式数据库的产生及发展a a 经济的发展经济的发展b b 计算机硬件环境及网络的发展计算机硬件
2、环境及网络的发展发展历程：产生于发展历程：产生于2020世纪世纪7070年代末期，成长于年代末期，成长于8080年代年代 第一个分布式数据库系统第一个分布式数据库系统SDD-1SDD-1是美国计算机公司是美国计算机公司（CAACAA）于）于19761976年年-1978-1978年设计，年设计，7979年在年在DEC-10/20DEC-10/20上实上实现。现。德国斯图加特大学研制的德国斯图加特大学研制的porelporel系统系统美国美国IBMIBM的的R R*和和system Rsystem R美国加大学伯克利分校的美国加大学伯克利分校的IngresIngres法国法国INRAINRA研制
3、的研制的SIRIUS-DELTASIRIUS-DELTA。19871987年：年：C.J DateC.J Date提出了完全的，真正的分布式提出了完全的，真正的分布式DBSDBS应应遵循的遵循的1212条规则：条规则：本地自治性本地自治性不依赖于中心站点不依赖于中心站点可连续操作可连续操作位置独立性位置独立性数据分片独立性数据分片独立性数据复制独立性数据复制独立性分布式查询独立性分布式查询独立性分布式事务管理分布式事务管理硬件独立性硬件独立性操作系统独立性操作系统独立性网络独立性网络独立性DBMSDBMS独立性独立性II II 分布式数据库系统的定义及分类分布式数据库系统的定义及分类1 1 分
4、布式数据库的定义：分布式数据库的定义：分布式数据库是一个数据集合，这些数据分布在由计算分布式数据库是一个数据集合，这些数据分布在由计算机网络连接起来的若干节点上，每个节点可以管理本地机网络连接起来的若干节点上，每个节点可以管理本地的数据应用，也可以参与全局数据应用。同时这些数据的数据应用，也可以参与全局数据应用。同时这些数据在逻辑上形成一个整体，由统一的数据库管理系统进行在逻辑上形成一个整体，由统一的数据库管理系统进行管理。（管理。（DDBMSDDBMS）注：几个基本的概念注：几个基本的概念站点：站点：计算机连接的一个逻辑单位，称为一个站点。计算机连接的一个逻辑单位，称为一个站点。本地（或称：
5、局部）用户、本地应用：本地（或称：局部）用户、本地应用：一个用户或应用一个用户或应用只访问他所注册的那个站点。只访问他所注册的那个站点。全局用户、全局应用：全局用户、全局应用：一个用户访问涉及两个或两个以一个用户访问涉及两个或两个以上的站点中的数据。上的站点中的数据。全局数据库（全局数据库（GDBGDB）、局部数据库（）、局部数据库（LDBLDB）：。）：。2.2.分布式数据库系统的基本特点：分布式数据库系统的基本特点：A A 结构特点：物理分布，逻辑相关。结构特点：物理分布，逻辑相关。B B 应用特点：站点自治。应用特点：站点自治。多处多处理机理机系统系统C.数据分布透明性：数据的物理独立性
6、内容更丰富，增加了数据分布透明性。-数据的逻辑分片、数据的物理位置分布、数据的复制，对用户透明。D.集中与自治兼备的数据库系统控制机制.-两个层次的数据共享：局部/全局数据共享。E.增加数据冗余度。-利用数据冗余提高系统可靠性、可用性和系统性能。F.事务管理的分布性。-分布环境下，维护事务的原子性、一致性、隔离性和持久性。3.3.分布式数据库系统的模式结构分布式数据库系统的模式结构4.4.分布式数据库系统的分类分布式数据库系统的分类A 按局部DBMS的数据模型分类：-同构型：数据模型相同同构型：数据模型相同 *同质同构：数据模型相同且局部同质同构：数据模型相同且局部DBMSDBMS相同。相同。
7、*异质同构：数据模型相同外交部局部异质同构：数据模型相同外交部局部DBMSDBMS不同。不同。SDD-1SDD-1和和DDM 美国美国CCACCA公司公司 SYSTEM R SYSTEM R*美国美国IBMIBM公司公司 POREL POREL 德国斯图加特大学德国斯图加特大学 -异构型异构型 ：数据模型不同：数据模型不同 MULTIBASE MULTIBASE 美国美国CCA1981CCA1981研制研制 IMADAS:H IMADAS:H 佛罗里达大学佛罗里达大学19841984研制研制 DDTS HONEYWELL DDTS HONEYWELL公司公司19801980年研制年研制。B 按
8、全局控制系统类型分类：-全局控制集中型DDBS DDBS的全局控制机制及数据字典位于一个中心站点，由中心站点完成全局事务的协调和局部数据库的转换等所有控制功能。-全局控制分散型DDBS DDBS的全局控制机制及数据字典分散在网络的各个站点上，每个站点都能完成全局事务的协调和局部数据转换。-全局控制可变型（主从型）将站点分成两组，一组都包含全局控制机制和数据字典，另一组为辅助站点，只包含自己的数据应用。4.4.分布式数据库管理系统的功能结构：分布式数据库管理系统的功能结构：除了具有集中式DBMS具有的功能外，还要有如下附加 的功能：*数据跟踪*分布式查询处理能力*分布式事务管理的能力*复制数据的
9、能力*安全性*分布式目录管理二二.分布式数据库系统中存在的技术问题：分布式数据库系统中存在的技术问题：1 分布式数据库系统的设计 -全局模式的设计 -数据分片，分布 2 分布式数据库的查询处理 3 分布式数据库的事务管理及并发控制 4 分布式数据库的可靠性 5 异构数据库的连接 6 安全性 7 目录管理1.1.分布式数据库设计分布式数据库设计一 方法：根据设计是基于现存的数据系统还是构造一个全新的数据库系统，有两种方法创建分布式数据库：组合法：基于现有的系统，建立一个协调管理系统。-采用自底向上的方式构建 重构法：创建全新的数据库系统 -自顶向下的方式构建自顶向下的方式构建二 分布式数据库设计
10、的内容：1.1.数据库设计基础-需求分析 1 1）数据需求 2 2）应用需求 应用的原发站点：发出应用请求的站点 应用在站点被激活的频率 应用对数据对象访问次数、类型和分布统计2.2.数据库设计（设计的核心任务）全局模式设计 局部数据库设计 数据分片设计 片段的位置分配设计三 分布式数据库设计的目标：确保数据库数据和应用具有最大程度的本地性。分布式数据的可用性和可靠性 工作负荷分布 存储的能力和费用四四 自顶向下的方式构建分布式数据库自顶向下的方式构建分布式数据库需需求求分分析析全全局局概概念念模模型型全全局局逻逻辑辑模模型型分分片片设设计计系系统统实实现现试试运运行行及及维维护护分分布布设设
11、计计局局部部逻逻辑辑设设计计物物理理设设计计1 1 设计的步骤：设计的步骤：2 2 数据库的分片设计数据库的分片设计（1 1）.什么叫什么叫“片段片段”？指在分布式数据库系统中，某一站点上存储的数据集合。指在分布式数据库系统中，某一站点上存储的数据集合。（2 2）.分片设计的目的？分片设计的目的？产生全局数据的一个合理的划分，从而使每个站点只获得它所产生全局数据的一个合理的划分，从而使每个站点只获得它所需要的数据，最大可能保证应用的本地性。需要的数据，最大可能保证应用的本地性。（3 3）分片应遵循的一般规则：设：）分片应遵循的一般规则：设：R=R1,R2,Rn R=R1,R2,Rn 1 1）完
12、整性）完整性 即，即，tR,tR,则，必有则，必有t Ri(i=1,2,n)t Ri(i=1,2,n)2 2）可重构性）可重构性 即，即，R=Ri(i=1,2,n)R=Ri(i=1,2,n)或或R=R=Ri(i=1,n)Ri(i=1,n)3 3）不相交性）不相交性 即，即，Ri Rj=(i,j=1,n,Ri Rj=(i,j=1,n,且且i ji j）或或Ri Rj=Ri Rj=主码属性主码属性(i,j=1,n,(i,j=1,n,且且i ji j）（4 4）分片的基本类型和方法）分片的基本类型和方法 水平分片，垂直分片，混合分片水平分片，垂直分片，混合分片A A 水平分片：对全关系进行选择操作，
13、把具有相同性质的元组进水平分片：对全关系进行选择操作，把具有相同性质的元组进行分组，构成若干不相交的子集。初级分片和导出分片行分组，构成若干不相交的子集。初级分片和导出分片 初级分片：以关系自身属性性质分组初级分片：以关系自身属性性质分组例1 S(S#,Sname,Age,Sex)1 S(S#,Sname,Age,Sex)define fragment S1 asdefine fragment S1 asselect select*from S where Sex=M from S where Sex=M；define fragment S2 asdefine fragment S2 asse
14、lect select*from S where Sex=F from S where Sex=F；导出分片：用其它关系的属性对某一全关系进行分组例2 2 设：全局关系 SC(S#,C#,Grade)SC(S#,C#,Grade)S(S#,Sname,Age,Sex)S(S#,Sname,Age,Sex)设计需求：按S S的“性别”属性（SexSex）去划分SCSCDefine fragment SC1 asDefine fragment SC1 as select SC.S#,C#,Grade select SC.S#,C#,Grade from SC,S from SC,S where S
15、C.S#=S.S#where SC.S#=S.S#and S.Sex=M and S.Sex=MDefine fragment SC2 asDefine fragment SC2 as select SC.S#,C#,Grade select SC.S#,C#,Grade from SC,S from SC,S where SC.S#=S.S#where SC.S#=S.S#and S.Sex=F and S.Sex=F B 垂直分片：利用投影操作把全关系的属性分成若干组，目标是把频繁使用的属性聚集在一起，且各片段只在键属性下重叠。例3 3 设：全局关系EMP(E#,Name,Dept,Job
16、,Sal,tel)EMP(E#,Name,Dept,Job,Sal,tel)Key=E#Key=E#垂直分片：EMP1(E#,Name,Sal,tel)EMP1(E#,Name,Sal,tel)EMP2(E#,Dept,Job)EMP2(E#,Dept,Job)3 3 数据库片段位置分配的设计数据库片段位置分配的设计两种方式：两种方式：非冗余分配：一个片段映射到一个站点非冗余分配：一个片段映射到一个站点 冗余分配：一个片段映射到多个站点冗余分配：一个片段映射到多个站点非冗余“最佳适应”分配法：计算：Bij=Bij=k(Fkj k(Fkj*Nki)Nki)即，计算所有的应用在站点j j上访问片段
17、i i 的总次数。对所有站点j j确定j j,使得BijBij=max(Bij)=max(Bij)即，把片段RiRi分配到有最大访问次数的站点j j。i-i-片段序号片段序号j-j-站点序号站点序号k-k-应用序号应用序号Fkj-Fkj-应用应用k k在站点在站点j j上激活的频率上激活的频率Rki-Rki-应用应用k k对片段对片段i i 进行检索访问的次数进行检索访问的次数(Read)(Read)Uki-Uki-应用应用k k对片段对片段i i 进行更新访问的次数进行更新访问的次数Nki=Rki+Uki-Nki=Rki+Uki-应用应用k k对片段对片段i i进行访问的总次数进行访问的总次
18、数冗余分配比较复杂，一般采用下列方法之一进行估算：-所有得益站点法：-附加复制法（1 1）“所有得益站点”法对所有站点确定非冗余分配方案。从全部结点中选择一组站点，使得给这组站点分配片段RiRi的一个拷贝所得到的检索效益，大于从其它站点对RiRi实施更新的代价。把片段RiRi拷贝分配给该组站点（2）附加拷贝附加拷贝法对所有站点确定非冗余分配方案。计算把片段RiRi分配给所有站点所能得到的总效益fifi（以及一个站点分得RiRi所得到的效益）从分得片段RiRi能够获取最大益处的站点起，对各站点依次附加片段RiRi的一个拷贝，直到增加片段RiRi不能使系统得到明显效益（或者说效益增大“接近”fi”
19、fi）为止。总结：数据库片段及位置分配的设计所需要 的参数均从应用需求中得来，总结这些参数可用如下三个表表达：A 频率表：各站点每一应用激活的次数B 划分表：各实体的潜在水平分片规则C 极化表：给定站点发出一给定应用访问一给定片段的概率需需求求分分析析全全局局概概念念模模型型全全局局逻逻辑辑模模型型分分片片设设计计系系统统实实现现试试运运行行及及维维护护分分布布设设计计局局部部逻逻辑辑设设计计物物理理设设计计频率表 划分表极化表分布式数据库设计的一个例子分布式数据库设计的一个例子订票系统维护分布在三个网络站点（与机场1 1，2 2，3 3处于同一地理区域）上的数据库。数据库存储机场规程、班机起
20、降和旅客订票等数据。（1）概念设计-全局概念模式（E-RE-R图）（2）收集数据与其最相关的应用知识-用操作模式表示a 订票:用于旅客预订机票。b 登记:用于旅客登机登记任务记录。c 起飞应用:查询即将从一个机场起飞的30个班机信息。（3）在操作模式的基础上，对每一实体估算应用的定量数据，建立逻辑访问表例“班机”实体逻辑访问表（4）分布需求分析a.a.频率表：调研并给出在三个站点上使用各个应用的频率（激活的次数）b.b.划分表：分析各个实体各种可能的分片方式及其选择性*基本划分*导出划分注释表：c.c.极化极化表：调研并给出从一个站点发出一个应用所需要访问某片段的概率。（5）飞机订票系统的分布
21、式设计a.为各个实体选择合适的分片,原则:满足本地性，不造成应用困难。对本例来予，各个实体采用水平分片：“机场”由基于区域的基本水平分片（片段(F1(F1F3)F3)：机场1 1，机场2 2，机场3 3）“班机”由基于起飞机场区域的导出水平分片（片段(A1(A1A3)A3)：班机1 1，班机2 2，班机3 3）“旅客”由基于旅客订票涉及的班机起飞机场所在区域的导出水平分片（片段(P1(P1P7)P7)：旅客1 1，旅客2 2，旅客3 3，旅客7 7）b.进行片段的非冗余分配：1 1）站点1 1：机场1 1，班机1 1，旅客1 12 2）站点2 2：机场2 2，班机2 2，旅客2 2 旅客4 4
22、，旅客6 6，旅客7 73 3）站点3 3：机场3 3，班机3 3，旅客3 3 旅客旅客5 5根据频率表和极化表c.进行片段的冗余分配：根据应用可以将旅客4.5.6分配在两个站点上，旅客7分配在三个站点上。（6）重构局部模式本节要点1.1.理解分布式数据库系统的基本概念及特征，理解分布式数据库系统的基本概念及特征，总结分布式数据库分片设计方法。熟练掌握使用SQLSQL语句，定义全局关系模式的分片方法。2.2.总结“自顶向下”设计分布式数据库的方法。掌握从设计全局设计模式到各站点上局部模式的分布设计方法。3.3.理解分布式数据库片段分配设计方法的思想。2.2.分布式数据库查询处理分布式数据库查询
23、处理一、分布式查询处理的步骤查询分析若该查询属于局部查询，则执行局部查询处理后，即可结束。查询分解把全局查询或远程查询转换成定义在全局关系上的关系代数表达式，并优化该表达式。查询本地化把一个全局关系上的查询，转化为对片段的局部查询。全局查询优化：找出对各个片段局部查询结果之间的最佳操作次序，使得代价最小。其重点在连接运算和并运算的优化局部优化：由确定的片段所在站点执行二、分布式查询处理的代价QC估算：QC=I/O+通信代价T*通信代价T估算T=T=传输次数（每次传输延迟时间+每次传输数据量/数据传输速率）=传输次数（C0+X/DC0+X/D）三、分布式查询策略的重要性：例设：教学数据库中：S(
24、S#,Sname,Age,Sex)10,000S(S#,Sname,Age,Sex)10,000个元组，存放在A A站点（男/女各一半）SC(S#,C#,Grade)1,000,000SC(S#,C#,Grade)1,000,000个元组，存放在A A站点（每人选课100100门）C(C#,Cname,Teacher)100,000C(C#,Cname,Teacher)100,000个元组，存放在B B站点假设：每个元组的长度为100 bit;100 bit;通信系统传输速率为10,000bit/0,000bit/秒；每次通信延迟时间为1 1秒。查询：选修课名查询：选修课名Maths Math
25、s 的男生的学号和姓名的男生的学号和姓名对于本例，C0=1秒，D=10,000 bit/秒解：SQLSQL语句是：SELECT S.S#,Sname SELECT S.S#,Sname FROM S,SC,C FROM S,SC,C WHERE S.S#=SC.S#WHERE S.S#=SC.S#AND SC.C#=C.C#AND SC.C#=C.C#AND SEX=M AND SEX=M AND Cname=Maths AND Cname=Maths策略1 1：把关系C C传到A A站点；在A A站点进行处理。T1=1+(100,000 T1=1+(100,000*100)/10,000 1
26、00)/10,000 16.7(16.7(分)策略2 2：先在A A站点找出男生选课情况（每人平均选100100门课），再根据C#C#向B B站点核查这些男生的选课是否是MathsMaths。(结果在A A站点)T3=2 T3=2*500,000 500,000*1 1秒 11.6(11.6(天)策略3 3：先在B B站点找出MathsMaths元组（假设最多有1010门），再把查找结果传到A A站点，在A A站点继续执行查询处理。T6=1+10T6=1+10*100/10,000 100/10,000 1 1秒四、基于关系代数等价变换的查询优化例1 S(S#,Sname,Age,Sex)1
27、S(S#,Sname,Age,Sex)SC(S#,C#,Grade)SC(S#,C#,Grade)其中，其中，S S 和和SCSC都采取水平分片：都采取水平分片：用户查询：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.a.对于水平分片，检查选择运算（）与水平分片的条件（谓词）。b.b.对于垂直分片，注意消去不提供连接运算后所需要属性
28、的分支。例2 2 设：全局关系:EMP(E#,Ename,Sal,Dept,Dname)EMP(E#,Ename,Sal,Dept,Dname)现采取垂直分片：查询问题：SELECT Ename,SalSELECT Ename,SalFROM EMPFROM EMP查询关系代数表达式Ename,SalEname,Sal(EMP)(EMP)五 基于半连接算法的全局查询优化1、半连接运算:由投影和连接操作导出的一种关系代数操作。设：关系R R和S S在在属性R.A=S.B上的半连接操作记为：RA=BS=R R(R(RA=BS)(B B(S)(S)=R=RA=BSA=BR=S S(S(SA=BR)(
29、A A(R)(R)=S=SA=B或者:2、利用半连接运算实现连接运算S=S=R RA=B(RA=BS)A=BS(SA=BR)A=BR或者:S=S=R RA=B3.采用半连接运算实现连接运算的代价及优化令：tuple(R)tuple(R)表示关系R R的元组数 size(B)size(B)表示属性B B的数据长度现假设，用户希望在站点2 2上得到R R 与与 S S自然连接自然连接的结果RS网络站点1站点2RS网络站点1站点2(1)B(S)(2)传送B(S)(3)R=RB(S)B(4)传送R(5)RSB总代价：T半=2C0+C1*size(B)*tuple(B(S)+size(R)*tuple(
30、R)采用半连接操作优化的原理：两个关系进行连接操作之前，去掉无用的无组，减少数据传输量。采用直接连接运算的总代价：T=C0+C1 T=C0+C1*size(R)size(R)*tuple(R)tuple(R)选择半连接实现连接运算的原则：经半连接操作产生少量元组。4.4.查询优化策略1 1）计算各种半连接运算的代价。2 2）计算直接连接运算的代价。3 3）比较并选出最优者。六 基于直接连接算法的查询优化1 1、利用站点依赖信息的连接算法、利用站点依赖信息的连接算法R1R2=F11F21(F12F22)其成立的条件是什么?条件：A A(F11)(F11)A A(F12)=(F12)=A A(F2
31、1)(F21)A A(F22)=(F22)=A A(F11)(F11)A A(F22)=(F22)=A A(F12)(F12)A A(F21)=(F21)=站点依赖：设：R Ri iAA、R Rj jAA、S Si iA A、S Sj jAA分别表示关系R R、S S在站点i i、j j的A A属性上的取值。若对于i i j,j,有：R Ri iA A S Sj jA=A=,则称关系R R和S S在属性A A上站点依赖。性质：若关系R R和S S在属性A A上站点依赖，则：i iRS=(RiSi)推论：*如果R R和S S在属性A A上站点依赖，B B A,A,则，R R和S S在属性B B上
32、站点依赖。*如果R R和S S在属性A A上站点依赖，S S和T T在属性B B上站点依赖，则：RS=(RiSiTi iTi）使用站点依赖算法实现直接连接运算的优点:1 1）无数据传送2）可进行并行计算3 3）可利用本地索引在查询优化过程中，可以判断什么时候使用站点依赖算法（P87）2 2、分片和复制算法、分片和复制算法当查询不能在无数据传送方式下处理，可采用分片和复制算法，算法的原理：选择一组站点，将查询中的某一个关系的所有片段分布到这些站点上，然后把查询中的其余关系复制到每一个选定的站点上。优点：1 1）可进行并行计算 2 2）在一定程度上可利用本地索引选择方法：从假定某一关系分片，其余关
33、系复制，计算代价，然后再选择另一关系为分片，最后从中选择代价最小的方案。本节重点1.总结分布式数据库查询优化的主要步骤，并与集中式数据库查询优化相比较。2.总结利用半连接算法实现直接连接运算的全局查询优化方法特点。在什么条件下可以利用半连接算法实现直接连接运算？3.3.分布式事务管理及恢复的讨论分布式事务管理及恢复的讨论一、分布式事务概述一、分布式事务概述1.事务的特点分布式数据库的事务称为全局事务。一个全局事务在执行时分解为由若干与相应站点有关的操作序列组成的“子事务”。1.1.原子性 2.2.一致性（或可串行性）3.3.隔离性 4.4.持久性 5.5.系统效率6.6.系统可用性：分布式事务
34、既不能影响本站点上事务的执行，也不能影响其它站点上事务的执行Begin Transaction Begin Transaction 开始事务T1T1T2T2TnTnCommit/Abort(Commit/Abort(或Rollback)Rollback)结束事务子事务或操作序列子事务或操作序列全局全局事务事务3 3 分布式事务代理执行机制分布式事务代理执行机制2.2.分布式事务的结构事务代理的概念：一个事务代理就是一个站点上的一个进程事务代理的概念：一个事务代理就是一个站点上的一个进程应用请求应用请求（源站点（源站点总代理根代理）RollbackCommit总代理（根代理）子事务1失败子事务1
35、成功子事务代理n子事务代理1Begin Transaction子事务n失败子事务n成功例银行转帐事务：把帐号FROM_ACCFROM_ACC上数量为AMOUNTAMOUNT的资金，转入帐号TO_ACCTO_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_TABLEse
36、t 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-
37、AMOUNT 0then abortelse beginupdate ACCOUNT_TABLEset BALANCE=BALANCE-AMOUNTwhere ACCOUNT_NO=FROM_ACC;create AGENT;send to AGENT(AMOUNT,TO_ACC);waittingcommit/abortendAGENT（子代理）:begin transactionreceive from ROOT_AGENT(AMOUNT,TO_ACC);update ACCOUNT_TABLEset BALANCE=BALANCE+AMOUNTwhere ACCOUNT_NO=TO_AC
38、C;send to ROOT_AGENT(SUCCESS/FAIL)waittingcommit/abort二二.分布式事务的两阶段提交协议分布式事务的两阶段提交协议2-PC:Two-Phase Commitment Protocal2-PC:Two-Phase Commitment Protocal协调者日志参与者。参与者参与者日志日志日志两阶段提交协议的活动机制：两阶段提交协议的活动机制：初始初始协调者协调者写写end of transend of trans到日志到日志初始初始参与者参与者写写begin transactionbegin transaction等待等待准备提交准备提交写写
39、readyready到日志到日志有要求撤消的？有要求撤消的？写写abortabort到日志到日志提交提交撤消撤消就绪就绪消息类型消息类型?撤消撤消提交提交准备准备撤消撤消提交提交全局撤消全局撤消全局提交全局提交写写abortabort到日志到日志nono写写commitcommit到日志到日志nono写写abortabort到日志到日志abortabort写写commitcommit到日志到日志commitcommit两阶段提交协议的执行过程：两阶段提交协议的执行过程：1 1）表决阶段：对当前事务形成一个决定。协调者：写“开始事务”日志；向各个参与者发出“准备”命令；进入等待状态。对于每一个参
40、与者 参与者接收“准备”消息；参与者检查子事务，确定是否提交子事务：Case1:Case1:可以提交子事务：参与者写“就绪”日志；向协调者发“建议提交”消息；参与者进入“就绪”状态。Case2:Case2:不可以提交子事务：参与者写“撤消”日志；向协调者发“建议撤消”消息；参与者进入“撤消”状态。协调者接收到所有参与者的回答后，作出决定：协调者接收到所有参与者的回答后，作出决定：Case1:Case1:若所有参与者发出若所有参与者发出“建议提交建议提交”的消息，则，的消息，则，协调者作出提交全局事务的决定。协调者作出提交全局事务的决定。协调者写提交日志；协调者写提交日志；协调者发出协调者发出“
41、全局提交全局提交”消息；消息；协调者进入协调者进入“提交提交”状态。状态。Case2:Case2:若发现某参与者发出若发现某参与者发出“建议撤消建议撤消”的消息，的消息，则，协调者作出撤消全局事务的决定。则，协调者作出撤消全局事务的决定。协调者写撤消日志；协调者写撤消日志；协调者发出协调者发出“全局撤消全局撤消”消息；消息；协调者进入协调者进入“撤消撤消”状态。状态。“一票否决一票否决”制！制！2 2）执行阶段）执行阶段 对于每一个处于“就绪”状态的参与者：参与者根据协调者发出的全局事务处理指令，或者撤消子事务，或者提交子事务 参与者发出参与者发出“确认确认”(ACK)”(ACK)收到全局事务
42、处理指令消息。收到全局事务处理指令消息。参与者进入参与者进入“撤消撤消”或或“提交提交”状态。状态。协调者写协调者写“结束事务结束事务”日志。日志。两阶段提交协议的特点：两阶段提交协议的特点：参与者有权单方面撤消事务。参与者有权单方面撤消事务。参与者作出参与者作出“建议提交建议提交”或或“建议撤消建议撤消”决定之决定之后，不能后，不能“翻悔翻悔”。处于处于“就绪就绪”状态的参与者可能进入提交状态，或撤消状态。状态的参与者可能进入提交状态，或撤消状态。协调者和参与者可能进入互相等待状态。协调者和参与者可能进入互相等待状态。1.试比较集中式、分布式事务的特点。2.总结分布式数据库2-PC的特点，并
43、指出它所存在的问题。本节重点4.4.分布式数据库并发控制机制分布式数据库并发控制机制一、分布式并发控制概述一、分布式并发控制概述1 分布式并发控制的目的：为并发执行的全局事务，产生一个分布式并发控制的目的：为并发执行的全局事务，产生一个可串行化调度。可串行化调度。2 局部调度：每个站点上的调度称为局部调度局部调度：每个站点上的调度称为局部调度3 全局调度：数据库系统全局事务的调度。全局调度：数据库系统全局事务的调度。4全局调度的可串行性全局调度的可串行性局部调度的可串行性！局部调度的可串行性！局部调度的可串行性：局部调度的可串行性：全局调度的可串行性？全局调度的可串行性？问题：一个数据对象问题
44、：一个数据对象x x，可能存在多个副本，可能存在多个副本x1,x2,xnx1,x2,xn。T1:Read(y);y:=y 15;Write(y);Commit;T2:Read(y);y:=y*2;Write(y);Commit;站点站点1 1 调度调度S1=R1,W1,C1,R2,W2,C2 S1=R1,W1,C1,R2,W2,C2 站点站点2 2 调度调度S2=R2,W2,C2,R1,W1,C1 S2=R2,W2,C2,R1,W1,C1 设：站点设：站点1 1，站点站点2 2上都有上都有y y的副本，且的副本，且都执行事务都执行事务T1,T2T1,T2。全局调度不可串行！全局调度不可串行！5
45、.5.全局调度的冲突可串行性应满足的条件全局调度的冲突可串行性应满足的条件:单副本控制协议单副本控制协议1)1)每一个局部调度是冲突可串行化的。每一个局部调度是冲突可串行化的。2)2)任意两个冲突操作在它们同时出现的各个局部调度中，必任意两个冲突操作在它们同时出现的各个局部调度中，必须有相同的执行顺序。须有相同的执行顺序。二、并发控制法二、并发控制法并发控制算法并发控制算法悲观法悲观法乐观法乐观法封锁法封锁法时标排序法时标排序法混合法混合法加锁法加锁法时标排序法时标排序法集中式加锁集中式加锁主副本加锁主副本加锁分布式加锁分布式加锁基本时标排序法基本时标排序法多版本时标排序多版本时标排序保守时标
46、排序保守时标排序1 1）集中式加锁法）集中式加锁法:网络中某一个站点被指定为主站点，用于存放网络中某一个站点被指定为主站点，用于存放整个分布式数据库的加锁表，负责整个系统事务的加锁整个分布式数据库的加锁表，负责整个系统事务的加锁.2 2）主副本加锁法：每个数据对象指定一个主副本，不同数据）主副本加锁法：每个数据对象指定一个主副本，不同数据对象的主副本放在不同站点上。对象的主副本放在不同站点上。算法：对主副本加锁；执行更新操作；开锁算法：对主副本加锁；执行更新操作；开锁3 3）分布式加锁算法：锁的管理由各个站点调度器参与、协调，）分布式加锁算法：锁的管理由各个站点调度器参与、协调，本地调度器负责
47、本站数据加锁。本地调度器负责本站数据加锁。算法：对全部副本加锁；执行更新操作；开锁算法：对全部副本加锁；执行更新操作；开锁三、分布式数据库并发控制的加锁技术三、分布式数据库并发控制的加锁技术1.分布式数据库加锁准则 读，锁一个；写，锁全部读，锁一个；写，锁全部(ROWA(ROWA协议协议)。遵守锁的相容性规则遵守锁的相容性规则 遵守两段锁协议（遵守两段锁协议（Two Phase Locking-2PL)Two Phase Locking-2PL)持有持有X X锁的事务，必须到结束事务才能开锁。锁的事务，必须到结束事务才能开锁。2 2、死锁管理、死锁管理1 1）全局死锁：）全局死锁：分布式数据库
48、中，涉及多个站点的死锁称为全分布式数据库中，涉及多个站点的死锁称为全局死锁。局死锁。站点站点A站点站点B事务事务T1持有持有对对X的锁的锁事务事务T2持有持有对对Y的锁的锁事务事务T2请求请求对对X的锁的锁事务事务T1请求请求对对Y的锁的锁T2等待等待T1完成释放完成释放对对X的锁的锁T1等待等待T2完成释放完成释放对对Y的锁的锁2 2）全局等待图（）全局等待图（GWFGGWFG）站点站点A:A:拥有拥有x x、y y的副本；的副本；T1:read(x),write(y)T1:read(x),write(y)站点站点B:B:拥有拥有y y、z z的副本；的副本；T2:read(y),write
49、(z)T2:read(y),write(z)站点站点C:C:拥有拥有z z 的副本；的副本；T3:read(z),write(x)T3:read(z),write(x)T1T2T3Xyz3 3）死锁的检测）死锁的检测A A 集中式死锁检测法集中式死锁检测法 指定某站点上的锁管理器作为全局死锁检测器指定某站点上的锁管理器作为全局死锁检测器 其余站点周期地向全局死锁检测器发送其余站点周期地向全局死锁检测器发送LWFGLWFG 全局死锁检测器产生全局死锁检测器产生GWFGGWFG，并检测有无回路，并检测有无回路B 分布式死锁检测法分布式死锁检测法 每个站点都有死锁检测器，负责检测本地可能的死锁。每个
50、站点都有死锁检测器，负责检测本地可能的死锁。每个站点按照一定规则，向相关站点发送潜在的死锁回路每个站点按照一定规则，向相关站点发送潜在的死锁回路图。图。4 4）死锁的解决）死锁的解决原则：撤消并恢复代价最小的事务。原则：撤消并恢复代价最小的事务。撤消并恢复年轻的事务。撤消并恢复年轻的事务。撤消并恢复占用资源较少的事务。撤消并恢复占用资源较少的事务。撤消并恢复具有最短运行时间的事务。撤消并恢复具有最短运行时间的事务。四四 并发控制的时标技术并发控制的时标技术1.1.时标时标:唯一识别一个事务，并用于对事务进行排序的标识符。唯一识别一个事务，并用于对事务进行排序的标识符。2.2.时标的构成：时标的
