数据库系统概论chp分布式数据库.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,数据库系统概论,An Introduction to Database System,第十四章 分布式数据库,第十四章 分布式数据库,14.1 概述,14.2 分布式数据库系统的体系结构,14.3 查询处理和优化,14.4 分布事务管理,14.5 小结,14.1 概述,14.1.1 分布式数据库系统,14.1.2 分布式数据库系统的特点,14.1.1 分布式数据库系统,什么是分布式数据库？,分布式数据库由一组数据组成，这些数据物理上分布在计算机网络的不同结点(亦称场地)上，逻辑上是属于同一个系统。,分布性,逻辑整体性,分布式数据库系统(续),图14.1 一个分布式数据库系统,例,1,如图,所示,分布式数据库系统(续),区分一个系统是若干集中式数据库的简单连网还是分布式数据库系统的技术要点在于：,系统是否支持全局应用,一个典型的例子是 转账,从一个分行的账户(设在DB1数据库)中转移若干金额到另一个分行的账户(设在DB3数据库)中去,要同时更新两个结点上的数据库,分布式数据库系统(续),图14.2 一个多处理机系统(SN并行结构),例,2,如图,所示,分布式数据库系统(续),多处理机系统(SN并行结构),没有局部应用,分布式数据库不仅要求,数据的物理分布,，而且要求这种,分布是面向处理、面向应用的,分布式数据库系统(续),分布式数据库：,分布式数据库是由一组数据组成的，这组数据分布在计算机网络的不同计算机上，网络中的每个结点具有独立处理的能力(称为场地自治)，可以执行局部应用。同时，每个结点也能通过网络通信子系统执行全局应用。,场地自治性,自治场地之间的协作性,14.1 概述,14.1.1 分布式数据库系统,14.1.2 分布式数据库系统的特点,分布式数据库系统的特点(续),一、数据独立性,逻辑独立性,物理独立性,数据分布独立性(分布透明性),用户的应用程序书写起来就如同数据没有分布一样,分布式数据库系统的特点(续),二、集中与自治相结合的控制结构,数据共享：,(1)局部共享,(2)全局共享,控制机制：,集中,自治,分布式数据库系统的特点(续),三、适当增加数据冗余度,提高系统的可靠性、可用性,提高系统性能,四、全局的一致性、可串行性和可恢复性,局部数据库要保证ACID,全局数据库也要保证ACID,第十四章 分布式数据库,14.1 概述,14.2 分布式数据库系统的体系结构,14.3 查询处理和优化,14.4 分布事务管理,14.5 小结,14.2 分布式数据库系统的体系结构,14.2.1 分布式数据库系统的模式结构,14.2.2 数据分片,14.2.3 分布透明性,14.2.4 分布式数据库管理系统,14.2.1 分布式数据库系统的模式结构,图14.3 分布式数据库系统的模式结构,分布式数据库系统的模式结构(续),分布式数据库系统增加的模式级别,(1)全局外模式(Global External Schema),(2)全局概念模式(Global Conceptual Schema),(3)分片模式(Fragmentation Schema),片段(Fragment),定义片段以及全局关系到片段的映象,(4)分布模式(Allocation Schema),定义片段的存放地点,14.2 分布式数据库系统的体系结构,14.2.1 分布式数据库系统的模式结构,14.2.2 数据分片,14.2.3 分布透明性,14.2.4 分布式数据库管理系统,14.2.2 数据分片,数据分片,有利于按照用户的需求较好地组织数据的分布,有利于控制数据的冗余度,数据分片的方式,水平分片,垂直分片,混合分片,导出分片,数据分片(续),水平分片,按一定的条件将关系按行(水平方向)分为若干不相交的子集，每个子集为关系的一个片段。,垂直分片,指将关系按列(垂直方向)分为若干子集。,每个片段通常都包含关系的,码,数据分片(续),导出分片,是指导出水平分片，即水平分片的条件不是本身属性的条件而是,其他关系的属性的条件,。,数据分片(续),例学生选课关系SC(Sno，Cno，Grade)，按照学生年龄18岁和18岁分片(学生年龄是学生关系Student的属性),年龄18岁的学生选课片段由下面的查询结果组成：,SELECT Sno，Cno，Grade,FROM S，SC,WHERE AND,S.Sage18,；,年龄18岁的片段SC_B由下面的查询结果组成：,SELECT Sno，Cno，Grade,FROM S，SC,WHERE S.SnoSC.Sno AND S.Sage18；,数据分片(续),混合分片,是指按上述三种分片方式得到的片段继续按另一种方式分片。,例如，先按垂直分片再按水平分片方式继续分片。,例如，先按水平分片得到的某一片段再进行垂直分片。,数据分片(续),分片应满足的条件,完全性,不相交性,可重构性,垂直分片：连接,水平分片：并操作,14.2 分布式数据库系统的体系结构,14.2.1 分布式数据库系统的模式结构,14.2.2 数据分片,14.2.3 分布透明性,14.2.4 分布式数据库管理系统,14.2.3 分布透明性,分片透明性 最高层次,用户或应用程序只对全局关系进行操作而不必考虑关系的分片,位置透明 下一层次,用户或应用程序不必了解片段的存储场地，当存储场地改变了，由于分片模式到分布模式的映像(映像3)，应用程序不必改变,局部数据模型透明性 较低层次,是指用户或用户程序不必了解局部场地上使用的是哪种数据模型，模型的转换以及数据库语言的转换均由映像4完成,分布透明性(续),例1设在分布式数据库系统中有全局关系,Student(Sno，Sname，Sdept，Sage),Student关系被划分为两个片段S_A和S_B。,S_A代表理学院的学生，S_B代表文学院的学生。,S_A存储在场地1(Site1)，S_B冗余地存储在场地2和场地3上。,分布透明性(续),要求,从终端读入一个学号，查找该学号的学生姓名、年龄，并把它们显示在屏幕上。,设应用程序是用嵌入SQL语句的C语言写的。现给出查询部分的算法思想。,分布透明性(续),情况1系统具有分片透明性,Scanf(“%s”,Snumber)；,EXEC SQL SELECT Sname,Sage INTO:NAME,:AGE,FROM Student,WHERE Sno：Snumber；,Printf(%s，%d，NAME，AGE),；,程序变量,分布透明性(续),情况2系统具有位置透明性，但不具有分片透明性,Scanf(%s“,Snumber);,EXEC SQL SELECT Sname,Sage INTO:NAME,:AGE,FROM S_A,WHERE Sno:Snumber;,If(!FOUND),EXEC SQL SELECT Sname,Sage INTO:NAME,:AGE,FROM S_B,WHERE Sno:Snumber;,Printf(%s,%d“,NAME,AGE)；,分布透明性(续),情况3系统只具有局部数据模型透明性，不具有位置透明性,Scanf(%s“,Snumber);,EXEC SQL SELECT Sname,Sage INTO:NAME,:AGE,FROM S_A AT Site1,WHERE Sno:Snumber;,If(!FOUND),EXEC SQL SELECT Sname,Sage INTO:NAME,:AGE,FROM S_B AT Site2,WHERE Sno:Snumber;,Printf(“%s,%d”,NAME,AGE);,14.2 分布式数据库系统的体系结构,14.2.1 分布式数据库系统的模式结构,14.2.2 数据分片,14.2.3 分布透明性,14.2.4 分布式数据库管理系统,14.2.4 分布式数据库管理系统,分布式数据库管理系统,(Distributed Data Management System，D-DBMS),建立、管理和维护分布式数据库的一组软件,分布式数据库管理系统(续),D-DBMS的结构,分布式数据库管理系统的结构,分布式数据库管理系统(续),D-DBMS由四部分组成：,(1)局部数据库管理系统LDBMS(Local DBMS),(2)全局数据库管理系统GDBMS(Global DBMS),(3)全局数据字典(Global Data Directory，GDD),(4)通信管理(Communication Management，CM),分布式数据库管理系统(续),一、按全局控制方式分类,1.全局控制集中的D-DBMS,全局控制成分GDBMS集中在某一结点上，全局数据字典只有一个，也存放在该结点上。,2.全局控制分散的D-DBMS,全局控制成分GDBMS分散在网络的每一个结点上，全局数据字典也在每个结点上存放一份。,根据应用的需要将GDBMS和全局数据字典分散在某些结点上。,分布式数据库管理系统(续),二、按局部DBMS的类型分类,同构型D-DBMS,每个结点的局部数据库具有相同的DBMS即使操作系统和计算机硬件并不相同,异构型D-DBMS,各结点的局部数据库具有不同的DBMS,第十四章 分布式数据库,14.1 概述,14.2 分布式数据库系统的体系结构,14.3 查询处理和优化,14.4 分布事务管理,14.5 小结,14.3 查询处理和优化,14.3.1 一个实例,14.3.2 查询处理和优化要解决的问题,14.3.3 查询优化的目标,14.3.4 连接查询的优化,14.3.1 一个实例,数据库：简化了的供应商和零件数据库,S(Sno，City)10,4,个元组，存放在场地A；,P(Pno，Color)10,5,个元组，存放在场地B；,SP(Sno，Pno)16,6,个元组，存放在场地A；,设每个关系的元组均为100字节长。,查询：求供应红色零件的、北京的供应商号,FROM S，P，SP,WHERE S.City=北京 AND,SP.Pno=P.Pno AND,P.Color=红色,一个实例(续),估算值(某些中间结果的元组数),红色零件数=10,北京供应商的装运单数=10,5,对通信系统的假定,数据传输速度=10,4,字节/秒,传输延迟=1秒,一个实例(续),6种可能的查询存取策略，对每种,i,分别计算通信时间T,i,：,T,i,总传输延迟+总数据量/数据传输速度(单位：b/s),策略1 把关系P传送到场地A，在A地进行查询处理。,T1=1+10,5,100/10,4,=10,3,秒(),一个实例(续),策略2 把关系S、SP传到场地B，在B地执行查询处理,T2=2+(10,4,+10,6,)100/10,4,10100秒(),一个实例(续),策略3 在场地A连接关系S和SP，选出城市为北京的元组(105个)，然后对这些元组中的每个元组的Pno，询问场地B，看此零件是否红色。,共问答105次，由于不是传送数据，只是消息的问答，所以,T3=210,5,s(),一个实例(续),策略4 在场地B选出红色零件的元组(10个)，然后对每一个元组逐一检查场地A，看北京供应商的装运单中是否有这个零件装运单(若有则选出S#)。,每做这样一次检查包括2次消息，共问一答10次，所以,T4=210=,20秒,一个实例(续),策略5 在场地A选出北京的供应商的装运单把结果送到场地B，在场地B完成最后处理，所以,T5=1+(10,5,100)/10,4,1000秒(),一个实例(续),策略6 在场地B的关系 P 中选出红色的元组(10个)，把结果送到场地A完成最终处理。所以,T6=1+(10100)/104,1秒,一个实例(续),表14.1 分布环境下查询策略实例比较,策 略,通信时间,方 法,1,16.7分,把P传到场地A,2,2.8小时,把S，SP传到场地B,3,2.3天,对每一北京的装运单，检查相应零件是否红色,4,20秒,对每一红色零件，检查北京供应商中是否有人供应,5,16.7分,把北京供应商的装运单传送到场地B,6,1秒,把红色零件传送到场地A,一个实例(续),(1)不同的存取策略通信时间相差很大，达多个数量级！-,优化,。,(2)不同策略，不同的考虑方式,有些策略中数据传输速度和传输延迟都要考虑,有些策略中(如策略3、策略4)主要考虑传输延迟,有些策略中(如策略1、策略2、策略5)数据传输量大，主要考虑传输时间,14.3 查询处理和优化,14.3.1 一个实例,14.3.2 查询处理和优化要解决的问题,14.3.3 查询优化的目标,14.3.4 连接查询的优化,14.3.2 查询处理和优化要解决的问题,分布式数据库系统中的三类查询：,局部查询,远程查询,全局查询,局部查询和远程查询优化,采用的技术是集中式数据库的查询优化技术(代数优化和非代数优化),查询处理和优化要解决的问题(续),全局查询处理和优化涉及的问题,14.3 查询处理和优化,14.3.1 一个实例,14.3.2 查询处理和优化要解决的问题,14.3.3 查询优化的目标,14.3.4 连接查询的优化,14.3.3 查询优化的目标,集中式数据库的查询开销,I/O代价+CPU代价,分布式数据库的查询开销,I/O代价+CPU代价+通信代价,查询优化首要目标：,通信代价最省,查询优化的目标(续),通信代价可以用下面的公式粗略计算：,TC(X)C,0,+X*C,1,X：数据传输量，这里以b(位)为单位计算；,C,0,：两结点之间初始化一次传输所花费的开销，它由通信系统决定，近似为一个常数，单位为s(秒)；,C,1,：单位数据(b)传输的代价，单位为(s/b)。,14.3 查询处理和优化,14.3.1 一个实例,14.3.2 查询处理和优化要解决的问题,14.3.3 查询优化的目标,14.3.4 连接查询的优化,14.3.4 连接查询的优化,两种优化方法,半连接：缩减关系（或片段）进而节省传输开销,直接连接,14.3.4 连接查询的优化（续）,半连接,R S R (,B,(S),用半连接实现的连接运算,R S=(R S)S,A=B,A=B,A=B,A=B,A=B,14.3.4 连接查询的优化（续）,设关系R和S分别存放在结点r和s上,结点r,R,结点s,S,B,(S),R S R,R,1.在结点s作关系S的投影,2.把投影 送到结点r，代价为,C,0,C,1,size(B),val(BS),3.在结点r计算半连接，结果为R，,R=R S,4.把R从结点r送到结点s，代价为,C,0,C,1,size(R),card(R),5.在结点s执行连接操作,B,(S),B,(S),A=B,14.3.4 连接查询的优化（续）,半连接方案的总代价,C,sj,2C,0,C,1,(size(B)val(B(S)+size(R)card(R),直接连接代价,C,jn,=,C,0,C,1,size(R)card(R),C,sj,C,jn,时采用半连接。,14.3.4 连接查询的优化（续）,直接连接,R*系统(IBM SanJose研究室研制),嵌套循环,排序-合并,两种传输方式,整体传输,按需传输,第十四章 分布式数据库,14.1 概述,14.2 分布式数据库系统的体系结构,14.3 查询处理和优化,14.4 分布事务管理,14.5 小结,(1)全局外模式(Global External Schema),对写操作，要申请所有副本的X锁；,例学生选课关系SC(Sno，Cno，Grade)，按照学生年龄18岁和18岁分片(学生年龄是学生关系Student的属性),1 分布式数据库系统的模式结构,对每一北京的装运单，检查相应零件是否红色,1 分布环境下查询策略实例比较,City=北京 AND,1 分布式数据库系统,SP(Sno，Pno)166个元组，存放在场地A；,分布式数据库系统的特点(续),查询优化首要目标：通信代价最省,D-DBMS由四部分组成：,2 分布式数据库系统的体系结构,多处理机系统(SN并行结构),S(Sno，City)104个元组，存放在场地A；,14.4 分布事务管理,14.4.1 分布事务的恢复,14.4.2 并发控制,14.4 分布事务管理,事务分布执行,分布事务的原子性,组成该事务的所有子事务要么一致地全部提交，要么一致地全部回滚,分布事务的可串行性,14.4.1 分布事务的恢复,故障和错误,各场地和集中式数据库相同,通信网络中信息丢失、长时间延迟、网络线路中断等,恢复策略,局部事务管理器：保证子事务完整性,局部管理器之间相互协调,FROM Student,分布式数据库管理系统(续),SP.,分布式数据库的查询开销,二、集中与自治相结合的控制结构,EXEC SQL SELECT Sname,Sage INTO:NAME,:AGE,WHERE Sno:Snumber;,Scanf(%s“,Snumber);,情况2系统具有位置透明性，但不具有分片透明性,通信网络中信息丢失、长时间延迟、网络线路中断等,通信代价可以用下面的公式粗略计算：,Cjn=C0 C1 size(R)card(R),把红色零件传送到场地A,数据库：简化了的供应商和零件数据库,提高系统的可靠性、可用性,1 分布式数据库系统,If(!FOUND),1 分布环境下查询策略实例比较,14.4.1 分布事务的恢复（续）,两段提交协议(2-Phase-Commitment Protocol),协调者：一个,做出提交还是撤销的,最后,决定,参与者：所有其他,管理相应,子事务,的执行,14.4.1 分布事务的恢复（续）,第一阶段,协调者发出“准备提交”信息,参与者回答“就绪”或“撤销”信息,协调者作出提交或撤销的决定,第二阶段,协调者把决定信息写入日志，并发给所有参与者,参与者把收到的决定信息写入日志，并发送“应答”信息,协调者收到所有应答信息后，事务执行到此结束,14.4.1 分布事务的恢复（续）,紧致一致性(Tight Consistency),各结点完全同步,缺点,全局事务可靠性低,系统效率低下,松散一致性(Loose Consistency),数据各副本的修改是异步的,更加灵活，提高系统的可用性,14.4.2 并发控制,集中式数据库封锁机制,锁的类型：共享锁(SLock)、排它锁(XLock),封锁对象：表、记录,规则：遵守锁的相容性,遵守两段锁协议,分布式数据库,支持多副本,由于事务的分布执行，封锁会引起全局死锁,14.4.2 并发控制（续）,多副本,几种解决方案,对写操作，要申请所有副本的X锁；对读操作，只要申请对某个副本的S锁。,无论读还是写都要对多数(大于半数)副本申请X或S锁,规定主副本，所有操作均申请对主副本的封锁,T,1,在场地1,XLock(d,site1,),T,2,在场地2,XLock(d,site2,),14.4.2 并发控制（续）,死锁,全局死锁：包括两个以上场地上的死锁,检测方法：分布等待图,预防方法：对事务按某一标准排序，只允许事务沿这一次序单向等待,第十四章 分布式数据库,14.1 概述,14.2 分布式数据库系统的体系结构,14.3 查询处理和优化,14.4 分布事务管理,14.5 小结,14.5 小结,分布式数据库系统,基本概念,以集中式数据库系统技术为基础,丰富了集中式数据库的概念和技术内容,主要问题,查询优化,事务管理,