分布式数据库复习重点

分布式数据库系统及其应用通过本课程的学习，使得同学们对分布式数据库学科的重要技术不仅知其然，更要知其所以然。掌握分布式数据库系统的理论、结构、技术和方法。了解实现分布式数据库的关键和难点。认清数据库学科的发展趋势和前景。为今后从事分布式数据库研究和应用打下良好的专业基础。课程目标课程内容（1）第1章分布式数据库系统概述第2章分布式数据库系统的设计第3章分布式数据库中的查询处理和优化第4章分布式数据库中的事务管理和恢复第5章分布式数据库中的并发控制第6章分布式数据库中的可靠性第7章分布式数据库的安全性与目录管理第8章分布式数据库与客户机/服务器模式第9章分布式数据库与WWW数据库和移动数据库第10章分布式数据库系统的发展趋势●

课程讲授（32学时）教材：邵佩英：《分布式数据库系统及其应用》（第2版），科学出版社，北京，2005

考核方式1.大作业之实验报告（40%）2.最后闭卷考试（60%）选修了分布式数据库的小伙伴们请注意啦：1.选择文献分析类型的，以个人为单位。电子版提交：作业报告；纸质版提交：作业报告2.选择项目类型的，组队不能多于5个人，要做与分布式数据库相关的项目。电子版提交：作业报告和代码；纸质版提交：作业报告3.请于14周之前提交大作业,电子版发送至2215489878@（标明是分布式数据库大作业），纸质版交到我的工位1-062（没有人在的情况下请放在桌子显眼处）4.1

分布式数据库的定义和特点4分布式数据库系统的定义和分类分布式数据库定义（P.4）：物理上分散而逻辑上集中的系统，它使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位（通常是集中式数据库系统）连接起来，共同组成一个统一的数据库系统。分布式数据库系统可以看成是计算机网络和数据库系统的有机结合。分布式数据库系统的特点（P.4~5）物理分布性：数据不是存放在一个站点上逻辑整体性：是与分散式数据库系统的区别站点自治性：是与多处理机系统的区别数据分布透明性集中与自治相结合存在适当的数据冗余度事务管理的分布性4.1

分布式数据库的定义和特点4分布式数据库系统的定义和分类DB1DB2DB3全局用户1局部用户1全局用户2局部用户2全局用户3局部用户3网络DDBMSDBMS1DDBMSDBMS2DDBMSDBMS3分布式数据库系统示意图（P.6）4.2

分布式数据库的分类4分布式数据库系统的定义和分类按局部DBMS的数据模型分类（P.7）同构型DDBS同构同质型同构异质型异构型DDBS按DDBS的全局控制类型分类（P.8）全局控制集中型DDBS：全局控制机制和全局数据词典位于中心站点全局控制分散型DDBS：全局控制机制和全局数据词典分散在网络的各个站点上。全局控制可变型DDBS：也称主从型DDBS。分成两组站点，一组包含全局控制机制和全局控制词典，另外一组不包含。5.1

分布式数据库系统的体系结构5分布式数据库系统的体系结构和组成成分分布式数据库系统的体系结构（P.9）GDBMSLDBMSLDD全局用户局部用户网络CMLDBGDDGDB全局用户GDDGDB局部用户GDBMSLDBMSLDDCMLDBGDBMSLDBMSCM全局用户GDDGDB局部用户LDDLDB数据（P.9）分布式数据库的主体局部数据：只提供本站点的局部应用所需要的数据。全局数据：虽然物理上存储在个站点上，但是参与全局应用。数据目录（P.9）数据结构的定义、全局数据的分片、分布、授权、事务恢复等描述局部数据目录：局部站点上的数据词典全局数据目录：提供全局数据的描述和管理相关信息5.2

分布式数据库系统的组成成分5分布式数据库系统的体系结构和组成成分数据分片（P.10）又称数据分割、数据分段，局部数据库是由全局数据库分割而成水平分片（对全局关系施加选择运算）垂直分片（对全局关系施加投影运算）混合分片（两种方法的混合）数据分片要准守的原则：完备性原则：要把所有的数据映射到各个片断中可重构原则：关系分片后的各个片断可重构整个关系不相交原则：关系分片后的各个片断不能重叠5.3DDBS中数据的分片与分布5分布式数据库系统的体系结构和组成成分分布式数据库的模式结构（P.12）5.4

分布式数据库的模式结构5分布式数据库系统的体系结构和组成成分全局外模式全局概念模式分片模式分配模式局部概念模式局部内模式DB局部概念模式局部内模式DB全局外模式全局外模式全局DBMS局部DBMS

分布式数据库特有的集中式数据库也有的映象1映象3映象2映象4良好的可靠性和可用性（P.34）提高系统效率，降低通信费用（P.34）较大的灵活性和可伸缩性（P.35）经济性和保护投资（P.35）适应组织的分布式管理和控制（P.35）数据分布具有透明性和站点具有较好的自治性（P.35）7.1DDBS的优点7DDBS的优点和存在的技术问题最重要的问题是通信网络速度问题如何控制数据的分片、分布与冗余度（P.35）如何实现异构数据库的互联（P.36）如何优化分布式数据库的查询处理（P.36）如何更好地实现分布式数据库的更新处理（P.36）如何实现分布式数据库的并发控制机制（P.36）如何实现分布式数据库的恢复控制机制（P.36）如何实现目录管理（P.36）7.2DDBS中存在的技术问题7DDBS的优点和存在的技术问题分布式数据库设计概述1创建方法1.1

组合法剖析网络功能剖析原有数据库系统解决数据的一致性、完整性和可靠性难度较大

通常是异构或者同构异质DDBS用户1用户2用户n分布式协调管理系统DBMS1DBMS2DBMSm

网络分布式数据库设计概述1DDBS创建方法1.1

重构法根据实现环境和用户需求按照DDBS的设计思想和方法从总体设计做起，包括LDBS,重新建立一个DDBS可有效解决数据一致性、完整性和可靠性问题。

通常是同构异质或同构同质DDBS用户1用户2用户n分布式数据库管理系统

网络2.1

步骤和内容2自顶向下设计DDB需求分析概念设计视图设计分布设计物理设计观察与监视系统需求全局概念模式访问模式外部模式定义局部概念模式物理模式用户输入视图集成用户输入反馈反馈自顶向下设计过程假若有全局关系R被分片为子关系(片段)集合R={R1,R2,…,Rn},则R满足完整性xR,RiR必有xRi，i=1,2,…,n可重构性存在函数g使得R=g(R1,R2,…,Rn)即，R=∪Ri(水平分片）,R=∞Ri（垂直分片）不相交性Ri∩Rj=空集,i≠j,i,j=1,2,…,n(水平分片)Ri∩Rj=主键属性,i,j=1,2,…,n(垂直分片)2.2

数据的分片设计2自顶向下设计DDB

分片原则基本水平分片以关系自身的属性性质为基础，执行“选择”操作，将关系分割成若干个不相交的片段。

R={R1,R2}R1=

loc=Sa(E)R2=

loc=Sb(E)2.2

数据的分片设计2自顶向下设计DDB

基本水平分片若R={R1,R2,…,Rn},则完整性对于每一个元组

t

R,RiR使得

tRi

不相交性对

tRi,Rj

使得

tRj,ij可重构性操作是∪

(可以忽略,因为完整性就蕴含着)R=

∪{R1,R2,…,Rn}P={p1,p2,…,pn}是一简单谓词集合，为保证分片的正确性，P必须是：完整的：同一分片中的任意两个元组被应用同样概率访问。最小的：集合P中的所有谓词与应用密切相关。(不同分片中的元组被访问的概率是不同的)具有完整性和最小性不是必要条件,但是对于简化分配问题有好处2.2

数据的分片设计2自顶向下设计DDB

基本水平分片例子EMP(E#,NAME,DEPT,JOB,SAL,TEL,…)DEPT={1,2}JOB={‘P’,‘-P’}假定，应用经常查询的内容是属于部门1且是程序员的职员。则可能有的水平分段限定

P={DEPT=1}（不是完整的）

P={DEPT=1,JOB=‘P’}（是完整的、最小的）

P={DEPT=1,JOB=‘P’,SAL>500}（完整的，不是最小的）2.2

数据的分片设计2自顶向下设计DDB

基本水平分片如何保证分片原则“手工”检查! e.g.,R1=

loc=‘Sa’E;R2=

loc=‘Sb’E生成具有满足分段原则的限定谓词2.2

数据的分片设计2自顶向下设计DDB

基本水平分片设有关系E(e#,name,Loc,sal,A,…),查询使用的简单谓词（Ai

Value）是:A<10,A>5,Loc=Sa,Loc=Sb下一步: -生成“小项”谓词

-消除无用谓词给定简单谓词集Pr={p1,p2,..pn},则“小项”谓词（mintermpredicate）形式:

p1*

p2*…pn*

这里pk*是pk

或是¬pk2.2

数据的分片设计2自顶向下设计DDB

谓词生成举例(1)A<10

A>5

Loc=SA

Loc=SB(2)A<10

A>5

Loc=SA

¬(Loc=SB)(3)A<10

A>5

¬(Loc=SA)

Loc=SB(4)A<10

A>5

¬(Loc=SA)

¬(Loc=SB)(5)A<10

¬(A>5)

Loc=SA

Loc=SB(6)A<10

¬(A>5)

Loc=SA

¬(Loc=SB)(7)A<10

¬(A>5)

¬(Loc=SA)

Loc=SB(8)A<10

¬(A>5)

¬(Loc=SA)

¬(Loc=SB)2.2

数据的分片设计2自顶向下设计DDB小项谓词选择(9)¬(A<10)

A>5

Loc=SA

Loc=SB(10)¬(A<10)

A>5

Loc=SA

¬(Loc=SB)(11)¬(A<10)

A>5

¬(Loc=SA)

Loc=SB(12)¬(A<10)

A>5

¬(Loc=SA)

¬(Loc=SB)(13)¬(A<10)

¬(A>5)

Loc=SA

Loc=SB(14)¬(A<10)

¬(A>5)

Loc=SA

¬(Loc=SB)(15)¬(A<10)

¬(A>5)

¬(Loc=SA)

Loc=SB(16)¬(A<10)

¬(A>5)

¬(Loc=SA)

¬(Loc=SB)2.2

数据的分片设计2自顶向下设计DDB小项谓词选择R2: 5<A<10

Loc=SA

R3: 5<A<10

Loc=SB

R6: A

5

Loc=SA

R7: A

5

Loc=SB

R10: A

10

Loc=SA

R11: A

10

Loc=SB

分片结果2.2

数据的分片设计2自顶向下设计DDB注:无用段的消除依赖于应用的语义e.g.:

如果LOC可以是

SA,SB,则最终分段集合应该加上R4: 5<A<10

LocSA

LocSB

R8: A

5

LocSA

LocSB

R12: A

10

LocSA

LocSB2.2

数据的分片设计2自顶向下设计DDB导出分片从另一个关系的属性性质或水平分片推导出来例子

SC(S#,C#,GRADE)S(S#,SNAME,AGE,SEX)要求：将SC划分为男生各门课成绩和女生的各门成绩2.2

数据的分片设计2自顶向下设计DDB

导出水平分片按S的属性导出

DefinefragmentSC1asSelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘M’DefinefragmentSC2asSelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘F’按S的水平分片（SF/SM）导出DefinefragmentSC1asSelect*FromSCWhereS#in(SelectSF.SfromSF)DefinefragmentSC2asSelect*FromSCWhereS#in(SelectSM.SfromSM)

2.2

数据的分片设计2自顶向下设计DDB

导出水平分片例子通过“投影”操作把一个全局关系的属性分成若干组，基本目标是将使用频繁的属性聚集在一起全局关系R={Ri},i=1,2,…,n如果属性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=Ap,i≠j，Ap为R的码或元组标识符，则称{Ri},i=1,2,…,n}是关系R的一个垂直分片。如果属性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=（Ap,A-p),i≠j，A-p为R的一个或多个非码属性时，称{Ri},i=1,2,…,n}是关系R的一个垂直群集。2.2

数据的分片设计2自顶向下设计DDB

垂直分片和垂直群集EMP(E#,NAME,SAL,TEL,MAGNUM,DEPT)假定Key:E#主要应用:Sa站点查询NAME,SAL,TEL;Sb站点查询NAME,MAGNUM,DEPT垂直分片:EMP1(E#,NAME,SAL,TEL)EMP2(E#,MAGNUM,DEPT)垂直群集:EMP1(E#,NAME,SAL,TEL)EMP2(E#,NAME,MAGNUM,DEPT)2.2

数据的分片设计2自顶向下设计DDB

垂直分片/垂直群集例子2.2

数据的分片设计2自顶向下设计DDBE1EE2

垂直分片例子

例子: E1(#,NM,LOC) E2(#,SAL)E(#,NM,LOC,SAL) E1(#,NM) E2(#,LOC) E3(#,SAL)2.2

数据的分片设计2自顶向下设计DDB

垂直分片设计非键属性A1,A2,…,An应用Q1,Q2,….,Qmfreq(Qi)=Qi

的访问频率2.2

数据的分片设计2自顶向下设计DDB

属性的亲和关系7578021A47975400A540974845A3024810050A201455096A1

A5A4A3A2A1R1[K,A1,A2,A3]R2[K,A4,A5]2.2

数据的分片设计2自顶向下设计DDB

属性和矩阵穷举属性亲和矩阵的列排列行与列要同时调整发现好的“分割点”极大化每个分割内的亲合力（affinity）,极小化跨分割的访问2.2

数据的分片设计2自顶向下设计DDB垂直分片算法

单个片段F站点S1,…Sm

变量X1,…,Xm0如果F不在Sj上存储

1如果F在Sj上存储

Totalcost=ReadCost+WriteCost+ StorageCost

确定Xj的值,1jm,使总代价极小Xj=2.3

数据的分配设计2自顶向下设计DDB分配的简化模型班机机号日期可用座位出入口座位图延期班机机号日期可用座位机型座位图班机班机1班机2机号日期可用座位座位图出入口延期机型5.2构造全局模式设计问题5自底向上设计分布式数据库5.3识别相似性和识别冲突5自底向上设计分布式数据库识别相似性模式命名相似性模式结构相似性不同Site上有相似应用,使用各自DB的数据副本,则这两Site之间有某些相似点.识别冲突命名冲突：同物异名（EMP,EMPLOYEE），异物同名域差异定标差异：计量单位不同(天、小时、分钟、秒）结构差异：同一对象有的用实体描述,有的用属性描述.处理操作期间不一致的数据策略（5种，p64-65）从到机场登记起飞时间到达时间符号城市权力区域安全规则座位号检查行李班机订票旅客机号日期可用座位进入口座位图延期种类名字电话系统A概念模式5.4自底向上综合的一个例子5自底向上设计分布式数据库站点1站点2站点3站点3站点2站点1A1R1A3R2A2R3A1R1,R2A3A2R2,R3方案A方案B读取更新10101055实现步骤和方法转换一：查询问题——〉关系代数表达式转换二：关系代数表达式——〉查询树转换三：全局查询树分拆成片段查询树优化：利用关系代数等价变换规则的优化算法，优化查询树，进而优化查询4.1

基本原理和实现方法4基于关系代数等价变换的查询优化处理4.2

查询优化处理举例4基于关系代数等价变换的查询优化处理全局关系S(S#,SNAME,AGE,SEX)和SC(S#,C#,GRADE)被水平分片hhSSCS1:SEX=‘M’男学生全体S2:SEX=‘F’女学生全体SC1：C#<=20课程号<=20SC2：C#>20课程号>20查询问题：查找至少有一门功课成绩在90分以上的男生姓名

SNAME(SEX=‘M’andGRADE>90(S.S#=SC.S#(S×SC)))4.2

查询优化处理举例4基于关系代数等价变换的查询优化处理

SNAMES.S#=SC.S#S.S#=SC.S#

S#,SNAME

S#,SNAME

GRADE>90

GRADE>90

SNAME

SEX=‘M’

SSC

SEX=‘M’US1[SEX=‘M’]S2[SEX=‘F’]USC1[C#

‘C20’]SC1[C#>’C20’](a)全局关系上的查询树(b)对应片段上的查询树

变换∞∞4.2

查询优化处理举例4基于关系代数等价变换的查询优化处理

SNAMES.S#=SC.S#S.S#=SC.S#

S#,SNAME

S#,SNAME

GRADE>90

SNAME

SEX=‘M’USC1[C#

‘C20’（c）把投影和选择下移后的查询树(d)一个简化的查询树产生矛盾去掉一支

S#,SNAME

GRADE>90S2[SEX=‘F’]

SEX=‘M’SC1[C#

‘C20’]SC2[C#

‘C20’]S1[SEX=‘M’]SC2[C#

‘C20’S1[SEX=‘M’]UUGRADE>90]GRADE>90]∞∞4.2

查询优化处理举例4基于关系代数等价变换的查询优化处理水平分片的查询优化的基本思想：尽量把选择条件下移到分片的限定关系处再把分片的限定关系与选择条件进行比较去掉它们之间存在矛盾的相应片断如果最后剩下一个水平片断，则重构全局关系的操作中，就可去掉“并”操作（至少可以减少“并”操作的次数）4.2

查询优化处理举例4基于关系代数等价变换的查询优化处理全局关系EMP(EMP#,ENAME,SALARY,DEPT#,DNAME)垂直分片：E1(EMP#,DEPT#,DNAME)EMP2(EMP#,ENAME,SALARY)vSE1E2:查询问题：雇员的姓名和工资情况

ENAME,SALARY(EMP)4.2

查询优化处理举例4基于关系代数等价变换的查询优化处理ENAME,SALARY

ENAME

EMP#,DEPT#,

EMP#,ENAME,

DEPTNAMESALARYENAME,SALARY

EMP#,ENAME,

SALARYENAME,SALARY

EMPE2:EMP#,ENAME,SALARY去掉无关的片段

移植到片段上去掉连接E1：E2：E1.EMP#=E2.EMP#∞∞4.2

查询优化处理举例4基于关系代数等价变换的查询优化处理垂直分片的查询优化的基本思想：把垂直分片所用到的属性集，与查询条件中的投影操作所涉及的属性相比较，去掉无关的垂直片断如果最后只剩下一个垂直片断与查询有关时，去掉重构全局关系的“连接”操作（至少可以减少“连接”操作的次数）假定有两个关系R,S,在属性R.A=S.B上做半连接操作，可表示为：R∝A=BS=

R(R∞A=BS)=R∞A=B(B(S))S∝A=BR=

S(S∞A=BR)=S∞A=B(A(R))用半连接表示连接操作R∞A=BS=(R∝A=BS)∞A=BS=（R∞A=B(B(S))∞A=BSS∞A=BR=(S∝A=BR)∞A=BR=(S∞A=B(A(R))∞A=BR5.1

半连接操作5基于半连接算法的查询优化处理例子1:R∝S

A B

2 a10 b25 c30 d25 w3 x10 y15 z32 x

A

(R)=[2,10,25,30]R∝SS∝R=AC10y25wA=AA=AA CSR10 b25 c

A B

5.2

半连接表示连接的代价估算5基于半连接算法的查询优化处理RS网络

站点1站点2(1)

B(S)(3)R’=R∝A=B

B(S)(2)

B(S)(4)R’=R∝A=B

B(S)(5)R’∞A=BS设c=Val(B[S]),m=Val(B[R]),r=Card(S),n=Card(R)c=(n,m,r)=r,当r<m/2c=(n,m,r)=(r+m)/3,当m/2≤r<2mc=(n,m,r)=m,当r≥2m代数操作对关系概貌的影响连接操作

T=R∞S

Card(T)=(Card(R)*Card(S))/Val(A[R])Size(T)=Size(R)+Size(S)Val(A[T])Min(Val(A[R]),Val(B[S]))A是连接属性

Val(A[T])Val(A[R])+Val(B[S])A不是连接属性半连接

T=R∝Sρ=Val(A[S])/Val(Dom(A))Card(T)=ρ*Card(R)Size(T)=第一个操作数Size（R）

Val(A[T])=ρ*Val(A[R])5.2

半连接表示连接的代价估算5基于半连接算法的查询优化处理代价公式：T=C0+C1*X在站点2上做投影

B(S)把B(S)传到站点1上，代价为：C0+C1*size(B)*val(B[S])在站点1上计算半连接，R’=R∝A=BS把R’从站点1传到站点2的代价为：C0+C1*size(R’)*card(R’)在站点2上执行连接操作：R’∞A=BS采用半连接的总代价T半R=2C0+C1*(size(R’)*card(R’)+size(B)*val(B[S]))T半S=2C0+C1*(size(S’)*card(S’)+size(A)*val(A[R]))比较T半R

与T半S,取最优者5.2

半连接表示连接的代价估算5基于半连接算法的查询优化处理基本原理通常有两次传输但是传输的数据量和传输整个关系相比，要远远少一般有：T半<<T全半连接的得益：当card（R）>>card（R’），可减少站点间的数据传输量半连接的损失：传输

B(S)=C0+C1*size(B)*val(B[S])基本原理是在传到另一个站点做连接前，消除与连接无关的数据，减少做连接操作的数据量，从而减小传输代价采用半连接优化算法的步骤计算每种半连接方案的代价，并从中选择一种最佳方案选择传输代价最小的站点，计算采用全连接的方案的代价比较两种方案，确定最优方案5.3

半连接算法优化原理和步骤5基于半连接算法的查询优化处理事务概念事务是访问或更新各种数据项的最小逻辑工作单位。它是一个操作序列它可以使数据库从一个一致状态到另外一个一致状态事务必须保证数据库的一致性事务执行期间数据库可能不一致1.1

分布式事务定义和特性1分布式事务概述

当事务提交（commit）时数据库必须是一致的事务T开始事务T结束事务T的执行数据库一致数据库一致数据库可能临时不一致1.1

分布式事务定义和特性1分布式事务概述事务概念分布式事务集中式事务和操作数据在一个站点上不存在传输费用分布式操作数据分布在不同的站点上事务也在多个站点上执行分布式事务是集中式事务的扩充站点和通信链路故障都可能导致错误发生分布式事务的恢复要比集中式事务复杂的多1.1

分布式事务定义和特性1分布式事务概述

事务分类:全局事务通常由一个主事务和在不同站点上执行的子事务组成主事务：负责事务的开始、提交和异常终止子事务：完成对相应站点上的数据库的访问操作局部事务仅访问或更新一个站点上的数据的事务1.1

分布式事务定义和特性1分布式事务概述分布式数据库中的事务ACID特性原子性（Atomicity）事务的操作要么全部执行，要么全部不执行，保证数据库一致性状态。一致性（Consistency）事务的正确性，串行性，并发执行的多个事务，其操作的结果应与以某种顺序串行执行这几个事务所得的结果相同。持久性（Durability）当事务提交后，其操作的结果将永久化，而与提交后发生的故障无关。1.1

分布式事务定义和特性1分布式事务概述分布式事务特性隔离性（Isolation）

虽然可以有多个事务同时执行，但是单个事务的执行不应该感知其他事务的存在，因此事务执行的中间结果应该对其他并发事务隐藏。此外，分布式数据库系统中还要考虑数据传送、通信原语和控制报文等。全局事务的主事务和子事务全部成功提交，才能改变数据库状态，有一个失败，其他子事务操作都要撤销。1.1

分布式事务定义和特性1分布式事务概述分布式事务特性分布式事务管理目标目的：事务能有效、可靠、并发的执行除了策略之外，效率的几个重要方面CPU和主存的使用控制报文响应时间可用性目标维护事务的ACID性质获得最小的主存和CPU开销，降低报文数目，加快响应时间获得最大限度的可靠性和可用性1.3

分布式事务管理的问题和目标1分布式事务概述事务管理LTM功能保证本地事务的ACID特性维护一个用于恢复的日志，代替DTM把分布事务的执行与恢复信息记入日志参与适当的并发控制模式，以协调在该站点上执行的事务的并发执行。接收并遵从本Site上DTM发来的Log原语，记入Log并执行之Log原语：

LocalBegin-Trans,Local-Commit,Local-Abort2.1

分布式事务管理的抽象模型2分布式事务的执行与恢复基本思想将本地原子性提交行为的效果扩展到分布式事务,保证了分布式事务提交的原子性,并在不损坏Log的情况下,实现快速故障恢复,提高DDB系统的可靠性.第一阶段：表决阶段第二阶段：执行阶段两类代理协调者(Coordinator)：提交和撤销事务的决定权，一般是总代理参与者(Participants)：负责在本地数据库中执行写操作，并且向协调者提出提交和撤销子事务的意向3.1

基本思想和内容3两阶段提交协议初始写begin_commit到日志等待有要求撤消的？写commit到日志提交写end_of_transt到日志初始准备提交？写ready到日志就绪消息类型？写abort到日志写commit到日志提交撤消撤消写abort到日志写abort到日志协调者参与者nonoabortcommit准备撤消提交全局撤消全局提交ACKACK两阶段提交协议的活动2PC协议的重要特点允许参与者单方面撤销事务一旦参与者确定了提交或撤销协议，它就不能再更改它的提议当参与者处于就绪状态时，根据协调者发出的消息种类，它可以转换为提交状态或者撤销状态协调者根据全局提交规则做出全局终止决定协调者和参与者可能进入互相等待对方消息的状态，使用定时器，保证退出消息等待状态3.1

基本思想和内容3两阶段提交协议集中式通讯只发生在协调者和参与者之间，参与者之间不交换信息分层式协调者是在树根的DTM代理者，协调者与参与者之间的通讯不用直接广播的方法进行，而是使报文在树中上下传播。每个DTM代理是通信树的一个内部节点，它从下层节点处收集报文或向它们广播报文。线性参与者之间可以互相通信。系统中的站点间要排序，消息串行传递。支持没有广播功能的网络分布式允许所有参与者在第一阶段相互通信，从而可以独立做出事务终止决定。3.2

通信结构3两阶段提交协议23451234511协调者参与者协调者协调者参与者第一阶段第二阶段准备建议撤消/提交全局撤消/提交提交/撤消集中式34251511协调者参与者协调者协调者参与者第一阶段第二阶段准备建议撤消/提交全局撤消/提交提交/撤消23422分层式1234n第一阶段第二阶段准备建议提交/撤消建议提交/撤消建议提交/撤消全局提交/撤消全局提交/撤消全局提交/撤消全局提交/撤消线性式1n4324321n……协调者协调者协调者+参与者第一阶段准备建议撤消/提交全局撤消/提交可独立做决定分布式站点故障a>

参与者在将“Ready”记录入Log之前故障此时协调者(C)达到超时，Abort发生。站点（P）恢复时，重启动程序将执行Abort，不必从其他站点获取信息。b>

当将“Ready”写入Log后，站点故障此时所有运行的站点都将正常结束事务（Commit/Abort)。P恢复时，因为P已Ready，所以不可判定C的最终决定。因此恢复时，重启动程序要询问C或其他站点。c>当C将“Prepare”写入Log，但“G-commit”/”G-abort”还没有写入前故障所有回答“Ready”的P等待C恢复。C重启动时，将重开提交协议，重发“Prepare”，于是P要识别重发。d>C在将“G-commit”/”G-abort”写入Log后，“Complete”没有写入前故障收到命令的P正常执行，C重启动程序必须再次向所有P重发命令。以前没有收到命令的P也必须等待C恢复，P要识别两次命令。e>“Complete”写入Log后故障无任何动作发生3.2

两阶段提交协议和故障恢复3两阶段提交协议2.报文丢失a>从P发出的“Ready”/“Abort”报文丢失C达到超时，整个事务执行“G-abort”。该故障仅能被C识别，此时C认为P故障，但P并无故障，不需执行重启动程序。b>“Prepare”报文丢失P等待，C得不到回答，结果同2.a>c>“G-commit”/”G-abort”报文丢失P处于不确定状态。回答“Abort”的可以确定其工作，回答“Ready”的不行。此时可以修改加入计时器，超时则申请重发命令。d>“Ack”报文丢失C超时，可重发“G-commit”/”G-abort”命令，P无论是否有活动，都重发“Ack”报文3.2

两阶段提交协议和故障恢复3两阶段提交协议网络分割站点假设分成两组：协调者组和参与者组。一组是协调者，一组是参与者。于是从协调者看是参与者组故障，结果同1.a>,1.b>。从参与者组看是协调者站点故障，动作如1.c>,1.d>。3.2

两阶段提交协议和故障恢复3两阶段提交协议初始写begin_commit到日志等待有要求撤消的？写commit到日志提交写Complete到日志初始准备提交？写ready到日志就绪消息类型？写abort到日志写commit到日志提交撤消撤消写abort到日志写abort到日志协调者参与者nonoabortcommit2.b>

准备2.a>撤消2.a>

提交2.c>全局撤消全局提交ACKACK1.c>1.d>1.e>1.a>1.b>2.d>主文本更新思想：指定主副本,修改只对主副本进行,修改辅助副本时,也按在主副本上执行的更新顺序执行问题修改传播必须在短时间内完成,否则将获得“过时”数据主副本不可用,引得其他副本也不可用4.2

主文本更新4分布式数据库中的数据更新4.2

主文本更新4分布式数据库中的数据更新网络站点AX主文本站点B2X辅文本站点B1X辅文本站点B3X辅文本站点B5X辅文本站点B4X辅文本T1T2未连通T1在T2之前移动主文本法若初次更新在辅文本上进行，然后再把更新引向该数据的主站点如果主站点此时尚未连通，则另选一个辅站点中的辅文本为该数据新的主文本进行更新待原主文本站点连通后，系统将自动把它改为辅文本，并按记录要求执行更新如果初次更新在主文本上进行，但主文本站点与网络未接通，则此次更新操作失败，事务被撤销，因为无法传播更新移动文本法的问题网络分割成很多部分时，更新处理会不一致网络分割成W1,W2，W1中X更新为R,W2中X更新为S,网络连通时，使用R还是S来恢复X呢？4.2

主文本更新4分布式数据库中的数据更新例子

DefineSnapshotHP-BookasSELECT*FROMBookWHEREPrice>$100REFRESHEveryday特点快照不考虑数据的辅助副本,只关心主文本和这个主本上定义的多个快照快照与视图一样可以定义为一个或多个主副本的部分或全部快照可以完成复杂的查询,但又不阻止更新查询操作可使用快照，也可使用主文本，对更新操作还是在主文本上进行4.3

快照方法4分布式数据库中的数据更新5.2

冗余数据的一致性5分布式事务增强数据库一致性分布式数据库冗余设计的理由提高系统的可用性和可靠性如果用户由于某种原因无法访问某个成员数据库，它可以访问另外一个成员数据库上的相同片断提高“读”事务的本地性降低通信成本例如，一个片断存放在该事务的原发站点中，则就免除了传输请求和返回结果的花费但是，如果事务包含对片断的更新，则其所有副本也必须做同样的更新，这时反而增加而不是降低通信成本事务TiTi={

i,<i}其中：

i:操作符集合：{Ri(x),Wi(x)}U{Ai,Ci}Ai,Ci

是最后的操作符，只能是其一<i:(冲突)操作有序执行，Ri(x)<iWi(x)或Wi(x)<iRi(x)1.2

事务可串行化理论1并发控制的概念和理论操作符集读Ri(x)和写Wi(x)动作序列冲突动作

R1(A)

W2(A)W1(A) W2(A)

R1(A)W2(A)一个调度事务的一个操作序列称为一个调度，一般用S表示比如，S:R1(x),R2(y),W2(y),R2(x),W1(x),W2(x)1.2

事务可串行化理论1并发控制的概念和理论T1

T21 (T1)a

X 5 (T2)c

X2 (T1)X

a+100 6 (T2)X

2c3 (T1)b

Y 7 (T2)d

Y4 (T1)Y

b+100 8 (T2)Y

2d先序关系例子已知：站点1有数据X，站点2有数据Y约束：X=Y1.2

事务可串行化理论1并发控制的概念和理论 (X站点) (Y站点)1 (T1) a

X 2 (T1)X

a+100 5 (T2)c

X 3(T1)b

Y 6 (T2)X

2c 4(T1)Y

b+100 7(T2)d

Y 8(T2)Y

2d

初值:X=Y=0,结果:X=Y=200调度S1事务内

事务间令T={T1,T2,…,Tn}是一组事务.T上的调度S是具有如下顺序关系<T的偏序，即S={

T,<T}

:(1)

T=

Ti(2)<T

<i(3)对于任意一组冲突操作p,qS,存在p<q或q<p关系并发调度定义i=1NNi=11.2

事务可串行化理论1并发控制的概念和理论调度一组事务的调度必须包含这些事务的所有操作调度中某个事务的操作顺序必须保持与该事务原有的顺序相同串行调度

一个事务的第一个动作是在另一个事务的最后一个动作完成后开始.即调度中事务的各个操作不会交叉,每个事务相继执行.一致性调度调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度1.2

事务可串行化理论1并发控制的概念和理论调度等价S1与S2等价,也就是说,对于冲突操作,<Oi,Oj>,Oi<Oj在S1中成立,同时Oi<Oj

在S2中也成立可串行化调度如果一个调度等价于某个串行调度，则该调度称为可串行化调度。也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度1.2

事务可串行化理论1并发控制的概念和理论例子两个事务，定义如下：T1:Read(x）x=x+10Write(x)Read(y)y=y-15Write(y)commit1.2

事务可串行化理论1并发控制的概念和理论T2:Read(x）x=x-20Write(x)Read(y)y=y*2Write(y)commit五种调度：S1={R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1,R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2}S2={R1(x),x=x+10,W1(x),R2(x),x=x-20,W2(x),R1(y),y=y-15,W1(y),C1,R2(y),y=y*2,W2(y),C2}S3={R1(x),x=x+10,W1(x),R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2,R1(y),y=y-15,W1(y),C1}S4={R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2,R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1}S5={R2(x),x=x-20,W2(x),R1(x),x=x+10,W1(x),R2(y),y=y*2,W2(y),C2,R1(y),y=y-15,W1(y),C1}1.2

事务可串行化理论1并发控制的概念和理论如果将事务提交延迟到两个事务操作完成之后执行，有：调度S1和S4是串行调度调度S2和S1的冲突操作具有相同的顺序，因此是等价调度；S2是可串行化调度，也是一致性调度调度S3虽是一致调度，但是它不与S1或S4等价，所以S3不是可串行化调度调度S5和S4等价，所以S5是一致调度，也是可串行化调度1.2

事务可串行化理论1并发控制的概念和理论有以下推论：一个可串行化调度必定与某个串行调度等价，且是一致性调度一致性调度不一定是可串行化调度同一事务集几个可串行化调度，他们的结果未必相同1.2

事务可串行化理论1并发控制的概念和理论优先图P(S)调度S的优先图是一个有向图G(N,E)，其中N:一组节点N={T1T2,…,Tn},S中的事务E:一组有向边E={e1,e2,…,en},Ti

Tj

是图中的一条边，当且仅当pTi,qTj

使得p,q冲突，并且p<Sq1.3

分布式事务的可串行化调度测试1并发控制的概念和理论测试调度S的可串行化对于调度S中的事务Ti，在图中创建一个节点Ti对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的R(X)操作，则在优先图中创建一条边（Ti→Tj）对于每一种这样的情形：如果S中的在Ti执行了R(X)操作后执行Tj的W(X)操作，则在优先图中创建一条边（Ti→Tj）对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的W(X)操作，则在优先图中创建一条边（Ti→Tj）当且仅当优先图中没有闭环时，调度S是可串行化的1.3

分布式事务的可串行化调度测试1并发控制的概念和理论测试调度S的可串行化优先图中存在环路，说明调度是不可串行化的，否则是可串行化的。环路是指有向图中每条边的起始节点（第一条边除外），都与前一条边的终止节点连接，而第一条边的起始节点于最后一条边的终止节点连接，即事务序列是以同一个节点作为开始和结束的调度S中事务Ti在事务Tj之前，与S等价的调度中Ti也必须在Tj之前某项数据导致了调度中的一条边的生成，就把数据项标注到优先图中这条边的旁边如果调度S中不存在环路，则就可能存在若干个与S等价的串行调度1.3

分布式事务的可串行化调度测试1并发控制的概念和理论1.3

分布式事务的可串行化调度测试1并发控制的概念和理论S1的优先图S2的优先图S3的优先图S4的优先图S5的优先图XYXYXYXYXY存在环路举例考虑如下3个事务：

T1:Read(x);Write(x);Commit;T2:Write(x);Write(y);Read(z);Commit;T3:Read(x);Read(y);Read(z);Commit;

这3个事务的一个调度：S={W2(x),W2(y),R2(z),C2,R1(x),W1(x),C1,R3(x),R3(y),R3(z),C3}

优先图：

T2T1T3无环，S是串行调度。1.3

分布式事务的可串行化调度测试1并发控制的概念和理论另外一个调度S’:S={W2(x),R1(x),W1(x),C1,R3(x),W2(y),R3(y),R2(z),C2,R3(z),C3}

先序图：

T2T1T3无环，是可串调度。1.3

分布式事务的可串行化调度测试1并发控制的概念和理论可串性理论扩展可串性理论可以直接扩展到无重复副本的分布式数据库中。事务在每个站点上的执行调度称作局部调度如果数据库无重复副本的分布式数据库，并且每个局部调度都是可串调度，只要这些局部调度的顺序一致，则它们的并（全局调度）也是可串调度但是有副本的情况下，就比较复杂。可能局部调度是可串行化的，而全局调度不是可串行化的。1.3

分布式事务的可串行化调度测试1并发控制的概念和理论并发控制算法悲观法乐观法加锁法集中式加锁分布式加锁时标排序法混合法加锁法时序排序法主副本加锁基本时标排序保守时标排序多版本时标排序并发控制算法的分类封锁法事务的同步化是通过对数据库的片断或者数据项进行物理或逻辑封锁来实现的封锁对象的大小通常称为封锁粒度封锁方法的类型可以根据在哪里进行封锁来进一步细分封锁法分类集中式封锁方法一个站点被指定为主站点，存放对整个数据库的封锁表，并且负责对全系统事务进行封锁主副本封锁法：主副本所在站点封锁分布式封锁法：网络中的站点共享锁的管理1.4

并发控制机制的常用方法及其分类1并发控制的概念和理论基本思想和概念基本思想事务访问数据项之前要对该数据项封锁，如果已经被其他事务锁定，就要等待，直到那个事务释放该锁为止锁的粒度锁定数据项的范围数据项层次数据库记录中的一个字段值一条数据库记录一个磁盘块（页面）一个完整的文件整个数据库2.1

基于封锁的并发控制方法概述2分布式数据库系统并发控制机制的封锁技术基本思想和概念粒度对并发控制的影响大多数DBMS缺省设置为记录锁或页面锁粒度小，并发度高，锁开销大数据项比较多，锁也多，解锁和封锁操作多，锁表存储空间大（如存储读写时间戳）粒度大，并发度低，锁开销小如果是磁盘块，封锁磁盘块中的一条记录B的事务T必须封锁整个磁盘块而另外一个事务S如果要封锁记录C,而C也在磁盘块中，由于磁盘块正在封锁中，S只能等待如果是封锁粒度是一条记录的话，就不用等待了2.1

基于封锁的并发控制方法概述2分布式数据库系统并发控制机制的封锁技术基本思想和概念如何来确定粒度取决于参与事务的类型如果参与事务都访问少量的记录，则选择一个记录作为粒度较好如果参与事务都访问同一文件中大量的记录，则最好采用块或者文件作为粒度2.1

基于封锁的并发控制方法概述2分布式数据库系统并发控制机制的封锁技术开始加锁点结束事务执行过程获得锁释放锁两阶段封锁协议2.2

基本2PL协议2分布式数据库系统并发控制机制的封锁技术基本2PL协议实现的难点锁管理器必须要知道事务的锁点位置级联撤销(cascadingaborts)如果事务在开始释放Lock后又Abort时,将引起级联撤销(cascadingaborts)（其他访问这个数据项的事务也被撤销）保守2PL要求事务在开始执行之前就持有所有它要访问的数据项上的锁事务要预先声明它的读集和写集大多数2PL调度器实现的是严格2PL(S2PL)事务在提交或者撤销之前，绝对不释放任何一个写锁事务结束时（提交或者撤销），同时释放所有的锁2.22PL协议2分布式数据库系统并发控制机制的封锁技术严酷2PL事务T在提交或撤销之前，不能释放任何一个锁（写锁或者读锁），因此它比严格2PL更容易实现保守2PL与严酷2PL之间的区别前者，事务必须在开始之前封锁它所需要的所有数据项，因此，一旦事务开始就处在收缩阶段后者,直到事务结束（提交或者撤销）后才开始解锁，因此，事务一直处于扩张阶段，直到结束2.22PL协议2分布式数据库系统并发控制机制的封锁技术开始结束事务执行阶段获得锁释放锁

严格2PL(StrictTwo-phaseLocking)协议数据项使用2.22PL协议2分布式数据库系统并发控制机制的封锁技术并发控制子系统可以负责产生读锁和写锁操作（以严格2PL协议为例）当事务T发出read_item(x)操作请求时，系统会代表T调用read_lock(x)操作如果Lock(x)的状态是被另外一个事务T’持有写锁，则系统会把T放到数据项X的等待队列中；否则，系统同意read_lock(x)的请求，从而允许事务T执行read_item(x)操作另外一个方面，如果事务T发出write_item（x）操作请求时，系统会代表T调用write_lock(x)操作如果Lock(x)的状态是被另外一个事务T’持有读锁或写锁，则系统会把T放到数据项X的等待队列中；如果Lock(x)的状态是读锁，并且事务T本身就是持有x上的读锁的唯一事务，则系统将该锁升级为写锁，并且允许T执行write_item(x)操作如果Lock(x)的状态是没有锁，则系统同意write_lock(x)的请求，进而允许事务T执行write_item(x)操作2.22PL协议2分布式数据库系统并发控制机制的封锁技术多粒度封锁封锁的粒度不是单一的一种粒度，而是有多种粒度可以定义多粒度树，根节点是整个数据库，叶节点表示最小的封锁粒度直接封锁事务对要进行读/写的数据对象直接申请加锁分层封锁DB中各数据对象从大到小存在一种层次关系,例如划分为DB,段,关系,元组,字段等当封锁了外层数据对象时,蕴含着也同时封锁了它的所有内层数据对象数据项的显式封锁和隐式封锁2.4

多粒度封锁与意向锁2分布式数据库系统并发控制机制的封锁技术T2T1YYYYYY-YNNYNNSIXYNYYNNIXYYYYNYISYNNNNNXYNNYNYS-SIXIXISXSXSIXSIXISY=yes，表示相容的请求N=no，表示不相容的请求(a)数据锁的相容矩阵(b)锁的强度的偏序关系

锁的相容矩阵2.4

多粒度封锁与意向锁2分布式数据库系统并发控制机制的封锁技术锁的强度：对其它锁的排斥程度多粒度封锁协议的规则必须遵守锁的相容性规则必须首先封锁树的根节点，可以用任何一种方式的锁只有当节点N的父节点已经被事务T以IS或IX方式封锁后，节点N才可以被T以S或者IS方式封锁只有当节点N的父节点已经被事务T以IX或SIX方式封锁后，节点N才可以被T以X,IX或者SIX方式封锁只有当事务T还没有释放任何节点时，T才可以封锁一个节点只有当事务T当前没有封锁节点N的任何子节点时，T才可以为节点N解锁。2.4

多粒度封锁与意向锁2分布式数据库系统并发控制机制的封锁技术总结具有意向锁的多粒度加锁方法中，任意事务T要对一个数据对象加锁，必须先对它的上层节点加意向锁申请封锁时应该按自上而下的次序进行释放锁时则应该按自下而上的次序进行具有意向锁的多粒度加锁方法提高了系统的并发度,减少了加锁和释放锁的开销它已经在实际的DBMS系统中广泛应用，例如Oracle中2.4

多粒度封锁与意向锁2分布式数据库系统并发控制机制的封锁技术集中式死锁检测选择一个站点负责整个系统的死锁检测,死锁检测器放到这个站点每个站点的锁管理器周期性地将本站点的LWFG传送给死锁检测器,死锁检测器构造GWFG,并在其中寻找回路或者，其它每个站点上的锁管理器周期性地把记录本站点上事务的开始时间，对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站点，由它维护一张全局封锁动态表，形成GWFG,并在其中寻找回路如果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢复，释放资源，使得其它事务继续进行选择的标准是尽可能使撤销并恢复的代价最小，如撤销年轻的事务，撤销占有较少资源的事务，撤销具有最短运行时间的事务，撤销具有最长运行时间的事务等，视系统情况而定3.3

死锁的检测和解决方法3分布式数据库系统中的死锁处理层次式死锁检测的步骤树叶是各站点的局部死锁检测器，在本站点建立局部等待图本站点的死锁检测器找出本站点局部等待图中的任何回路，并把有关潜在全局回路的信息发送给上一层死锁检测器每个非本地死锁检测器只对它所涉及的紧挨下层进行死锁检测，合并这些接收到的有关潜在全局回路的信息，并找出任何回路如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路这样，逐层检测，直到最高层。3.3

死锁的检测和解决方法3分布式数据库系统中的死锁处理分布式检测每个站点的检测死锁责任相同,站点之间交换信息(LWFG)，是为了确定全局死锁EX是指的本地事务正在等待的其他事务所在的还不确定的站点例子站点1站点2T1T2T4T3EXEX3.3

死锁的检测和解决方法3分布式数据库系统中的死锁处理信息传递方向此处规定一种,以避免多次重复传递EX等待的事务号>等待EX的事务号分布式死锁检测算法使用局部信息建造LWFG,该LWFG包含EX节点对每次接收到的信息,执行如下对LWFG的修改对报文中的每个事务,若LWFG中不存在,则将其加入从EX节点开始,按照报文所给的信息,建立一个到下一个事务的边在新的LWFG中寻找不含EX的Loop,若存在,则检测到死锁在新的LWFG中找到含有EX的Loop,于是有潜在的死锁,再按规定向外传送信息3.3

死锁的检测和解决方法3分布式数据库系统中的死锁处理基本概念 不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现时标是用来唯一识别每个事务并允许排序的标识如果ts(T1)<ts(T2)…<ts(Tn),则调度器产生的序是:T1,T2,...Tn规则如果T1的操作O1(x)和T2的操作O2(x)是冲突操作,则,O1在O2之前执行,当且仅当ts(T1)<ts(T2)4.1

基于时标的并发控制方法4分布式数据库系统并发控制的时标技术时标分配方法 全局时标使用全局的单调递增的计数器全局的计数器维护是个难题局部时标每个站点基于其本地计数器自治地指定一个时标标识符由两部分组成：〈本地计数器值，站点标识符〉站点标识符是次要的，主要是本地计数器值可以使用站点系统时钟来代替计数器值4.1

基于时标的并发控制方法4分布式数据库系统并发控制的时标技术时标法思想 每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行如果发生冲突，是通过撤销并重新启动一个事务来解决的事务重新启动时，则赋予新的时标优点是没有死锁，不必设置锁封锁和死锁检测引起的通信开销也避免了但要求时标在全系统中是唯一的4.1

基于时标的并发控制方法4分布式数据库系统并发控制的时标技术时标性质唯一性单调性全局唯一时间的形成与调整每个站点设置一个计数器,每发生一个事务,计数器加一发送报文时包含本地计数器值,近似同步各站点计数器4.1

基于时标的并发控制方法4分布式数据库系统并发控制的时标技术4.1

基于时标的并发控制方法4分布式数据库系统并发控制的时标技术

计数器X初值X=0计数器Y初值Y=10

站点1站点2

时标AD时标

TS(A)=<1,1>TS(D)=<11,2>

因为X<YETS(E)=<12,2>

改X=Y+1=11BTS(B)=<11,1>F因为Y>XTS(C)=<12,1>CTS(F)=<13,2>

本地计数器本地计数器

(或时钟)(或时钟)报文1报文2计数器站点基本时标法规则每个事务在本站点开始时赋予一个全局唯一时标在事务结束前，不对数据库进行物理更新事务的每个读操作或写操作都具有该事务的