分布式数据库.ppt

《分布式数据库.ppt》由会员分享，可在线阅读，更多相关《分布式数据库.ppt（67页珍藏版）》请在课桌文档上搜索。

1、分布式数据库,1 分布式数据库系统概论2 分布式数据库系统的设计3 查询处理和优化4 分布式系统中的死锁处理,分布式数据库系统概论,1.分布式数据库系统概论1.1 分布式数据库系统1.2 分布式数据库系统的特点1.3 分布式数据库系统的体系结构1.4 分布式数据库管理系统,1.1分布式数据库系统,分布式数据库系统，通俗地说，是物理上分散而逻辑上集中的数据库系统。分布式数据库系统使用计算机网络将地理位置分散而管理和控制又需要不同程度几种的多个逻辑单位连接起来，共同组成一个统一的数据库系统。因此，分布式数据库系统可以看成是计算机网络与数据库系统的有机结合。,1.1分布式数据库系统,图 1一个分布式

2、数据库系统,例1如图1所示,1.1分布式数据库系统,区分一个系统是若干集中式数据库的简单连网还是分布式数据库系统的技术要点在于：系统是否支持全局应用 一个典型的例子是银行转账 从一个分行的账户(设在DB1数据库)中转移若干金额到另一个分行的账户(设在DB3数据库)中去要同时更新两个结点上的数据库,1.1分布式数据库系统,图2 一个多处理机系统(SN并行结构),例2如图2所示,1.1分布式数据库系统,多处理机系统(SN并行结构)没有局部应用分布式数据库不仅要求数据的物理分布，而且要求这种分布是面向处理、面向应用的,1.2 分布式数据库系统的特点,（1）数据独立性逻辑独立性物理独立性数据分布独立性

3、(分布透明性)用户的应用程序书写起来就如同数据没有分布一样,分布式数据库系统概论,（2）集中与自治相结合的控制结构数据共享：(1)局部共享(2)全局共享控制机制：集中自治,分布式数据库系统概论,（3）适当增加数据冗余度提高系统的可靠性、可用性提高系统性能（4）全局的一致性、可串行性和可恢复性局部数据库要保证ACID全局数据库也要保证ACID,1.3 分布式数据库系统的模式结构,图 3 分布式数据库系统的模式结构,1.3 分布式数据库系统的模式结构,分布式数据库系统增加的模式级别(1)全局外模式(Global External Schema)是全局应用的用户视图，所以也称全局视图。分布式数据库的

4、全局视图不是从某一个具体站点的局部数据库中抽取，而是从一个由各局部数据库组成的逻辑几何中抽取，即全局外模式是全局概念模式的子集。然而，对全局用户而言，都可以认为在整个分布式数据库系统的各个站点上所有数据库如同在本站点上一样，只关心他们自己所使用的那部分数据。(2)全局概念模式(Global Conceptual Schema)全局概念模式描述分布式数据库中全局数据的逻辑结构和数据特性。,1.3 分布式数据库系统的模式结构,(3)分片模式(Fragmentation Schema)描述全局数据的逻辑划分；描述数据分片或定义分片，以及全局关心与片段之间的映像。这种映像是一对多的，即一个全局关系可对

5、应多个片段，而一个片段只能来自一个全局关系。(4)分布模式(Allocation Schema)定义片段的存放地点,1.4 分布式数据库管理系统,1.4.1 分布式数据库管理系统的功能 分布式数据库管理系统(Distributed Data Management System，D-DBMS)是分布式数据库系统的核心，负责实现分布式数据库的建立、查询、更新、复制和维护等功能，同时还包括提供分布透明性，查询优化、协调全局事务的执行，协调各局部DBMS共同完成全局应用，保证数据库的全局一致性，执行并发控制，实现更新同步和全局恢复等功能。,1.4 分布式数据库管理系统,DDBMS除了提供集中式DDBM

6、S所提供的功能外，还必须能够提供一下集中式DDBMS所不能提供的功能。1）数据跟踪：具有能够通过扩展DDBMS日志来记录数据分布、分片和复制的能力。2）分布式查询处理：具有能够通过通信网络存取远程站点的数据，以及在不同站点间传输请求和数据的能力。3）分布式事务管理：具有能够为需要从多个站点存取数据的查询和事务执行策略的能力，以及将分布式数据的存取和整个数据库完备性的维持保持同步的能力。,1.4 分布式数据库管理系统,4）复制数据的管理：具有能够把数据库从单个站点故障和新类型故障中恢复的能力5）安全性：分布式事务的执行必须具有适当的数据安全管理，以及用户授权/存取权限的安全管理。6）分布式目录管

7、理：目录包含了数据库中有关数据的信息，它对整个分布式数据库来说是全局的，对于每个站点来说又是局部的。,1.4 分布式数据库管理系统,1.4.2分布式数据库管理系统的结构根据分布式数据库系统的特点，可以将分布式数据库管理系统的结构分为以下四个功能模块：1.查询处理模块 查询分析 优化处理2.完整性处理模块 该模块主要负责维护数据库的完整性和一致性，检查完整性规则，处理多副本数据的同步更新等。,1.4 分布式数据库管理系统,3.调度处理模块调度处理模块就负责向有关的站点发出命令，使相应站点的DBMS执行这些局部处理。4.可靠性处理模块分布式数据库系统基于计算机网络，自然就会增加产生故障的因素。可靠

8、性处理模块负责不断地监视系统的各个部分是否有故障出现。当故障修复后，可靠性处理模块负责将该部分重新并入系统，使之继续有效地运行，并保持数据库的一致性状态。,分布式数据库系统的设计,2 分布式数据库系统的设计2.1分布式数据库系统的设计方法2.2 数据分片2.3分布透明性,2.1 分布式数据库系统的设计方法,（1）自顶向下设计方法 设计集中式数据库的一般方法包括四个阶段：需求分析、概念设计、逻辑设计和物理设计。分布式数据库设计在这四个阶段的基础上要增加一个新的阶段，称作分布设计，它位于逻辑设计与物理设计之间，以一个全局的、与站点无关的模式作为输入，以产生分布式数据库各站点的子模式作为结果输出。包

9、括数据的分片设计和片段的位置分配设计。,2.1 分布式数据库系统的设计方法,（2）自底向下设计方法 自底向下设计方法的重点是把现有的各种不同的数据库模式作为全局模式。所谓集成就是把公用数据定义整合起来，并解决同一数据不同表示方法之间的冲突。,2.2 数据分片,数据分片有利于按照用户的需求较好地组织数据的分布有利于控制数据的冗余度数据分片的方式水平分片垂直分片混合分片导出分片,2.2 数据分片,水平分片按一定的条件将关系按行(水平方向)分为若干不相交的子集，每个子集为关系的一个片段。垂直分片指将关系按列(垂直方向)分为若干子集。每个片段通常都包含关系的码,2.2 数据分片,导出分片是指导出水平分

10、片，即水平分片的条件不是本身属性的条件而是其他关系的属性的条件。,2.2 数据分片,例学生选课关系SC(Sno，Cno，Grade)，按照学生年龄18岁和18岁分片(学生年龄是学生关系Student的属性)年龄18岁的学生选课片段由下面的查询结果组成：SELECT Sno，Cno，Grade FROM S，SC WHERE S.SnoSC.Sno AND S.Sage18；年龄18岁的片段SC_B由下面的查询结果组成：SELECT Sno，Cno，Grade FROM S，SC WHERE S.SnoSC.Sno AND S.Sage18；,2.2 数据分片,混合分片是指按上述三种分片方式得到

11、的片段继续按另一种方式分片。,例如，先按垂直分片再按水平分片方式继续分片。,例如，先按水平分片得到的某一片段再进行垂直分片。,2.2 数据分片,分片应满足的条件完全性 各片段定义中的谓词的集合必须是完整的，即至少是它们允许值的集合。例如：SEX=M，F 季节=春，夏，秋，冬不相交性 如果谓词集合是互斥的，它们的片段必不相交可重构性 如果谓词集合是完整的，则通过并操作总能重构全局关系,2.3 分布透明性,分片透明性 最高层次用户或应用程序只对全局关系进行操作而不必考虑关系的分片位置透明 下一层次用户或应用程序不必了解片段的存储场地，当存储场地改变了，由于分片模式到分布模式的映像(映像3)，应用程

12、序不必改变局部数据模型透明性 较低层次是指用户或用户程序不必了解局部场地上使用的是哪种数据模型，模型的转换以及数据库语言的转换均由映像4完成,2.3 分布透明性,例1设在分布式数据库系统中有全局关系 Student(Sno，Sname，Sdept，Sage)Student关系被划分为两个片段S_A和S_B。S_A代表理学院的学生，S_B代表文学院的学生。S_A存储在场地1(Site1)，S_B冗余地存储在场地2和场地3上。,2.3 分布透明性,要求从终端读入一个学号，查找该学号的学生姓名、年龄，并把它们显示在屏幕上。设应用程序是用嵌入SQL语句的C语言写的。现给出查询部分的算法思想。,2.3

13、分布透明性,情况1系统具有分片透明性 Scanf(“%s”,Snumber)；EXEC SQL SELECT Sname,Sage INTO:NAME,:AGE FROM Student WHERE Sno：Snumber；Printf(%s，%d，NAME，AGE)；,程序变量,2.3 分布透明性,情况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 I

14、NTO:NAME,:AGE FROM S_B WHERE Sno:Snumber;Printf(%s,%d“,NAME,AGE)；,2.3 分布透明性,情况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,%

15、d”,NAME,AGE);,查询处理和优化,3 查询处理和优化3.1 一个实例3.2分布式查询的分类3.3 查询优化的目标3.4 连接查询的优化,3.1一个实例,数据库：简化了的供应商和零件数据库 S(Sno，City)104个元组，存放在场地A；P(Pno，Color)105个元组，存放在场地B；SP(Sno，Pno)166个元组，存放在场地A；设每个关系的元组均为100字节长。查询：求供应红色零件的、北京的供应商号 SELECT S.Sno FROM S，P，SP WHERE S.City=北京 AND SP.Pno=P.Pno AND P.Color=红色,3.1一个实例,估算值(某些中

16、间结果的元组数)红色零件数=10 北京供应商的装运单数=105对通信系统的假定 数据传输速度=104字节/秒 传输延迟=1秒,3.1一个实例,6种可能的查询存取策略，对每种i 分别计算通信时间Ti：Ti总传输延迟+总数据量/数据传输速度(单位：b/s)策略1 把关系P传送到场地A，在A地进行查询处理。T1=1+105100/104=103秒(16.7分),3.1一个实例,策略2 把关系S、SP传到场地B，在B地执行查询处理 T2=2+(104+106)100/10410100秒(2.8小时),3.1一个实例,策略3 在场地A连接关系S和SP，选出城市为北京的元组(105个)，然后对这些元组中的

17、每个元组的Pno，询问场地B，看此零件是否红色。共问答105次，由于不是传送数据，只是消息的问答，所以 T3=2105 s(2.3天),3.1一个实例,策略4 在场地B选出红色零件的元组(10个)，然后对每一个元组逐一检查场地A，看北京供应商的装运单中是否有这个零件装运单(若有则选出S#)。每做这样一次检查包括2次消息，共问一答10次，所以 T4=210=20秒,3.1一个实例,策略5 在场地A选出北京的供应商的装运单把结果送到场地B，在场地B完成最后处理，所以 T5=1+(105100)/1041000秒(16.7分),3.1一个实例,策略6 在场地B的关系 P 中选出红色的元组(10个)，

18、把结果送到场地A完成最终处理。所以 T6=1+(10100)/1041秒,3.1一个实例,表 分布环境下查询策略实例比较,3.1一个实例,(1)不同的存取策略通信时间相差很大，达多个数量级！-优化。(2)不同策略，不同的考虑方式 有些策略中数据传输速度和传输延迟都要考虑有些策略中(如策略3、策略4)主要考虑传输延迟有些策略中(如策略1、策略2、策略5)数据传输量大，主要考虑传输时间,3.2 查询优化的目标,集中式数据库的查询开销I/O代价+CPU代价分布式数据库的查询开销I/O代价+CPU代价+通信代价查询优化首要目标：通信代价最省,3.3 查询优化的目标,通信代价可以用下面的公式粗略计算：T

19、C(X)C0+X*C1 X：数据传输量，这里以b(位)为单位计算；C0：两结点之间初始化一次传输所花费的开销，它由通信系统决定，近似为一个常数，单位为s(秒)；C1：单位数据(b)传输的代价，单位为(s/b)。,3.3分布式查询的分类,分布式数据库系统中的三类查询：1）局部查询 局部查询只涉及本地、单个站点上的数据，所以查询优化技术与集中式数据库查询所采取的优化技术相同，如查询分解、关系代数表达式的等价变换、基于代价的估算等。2）远程查询 远程查询是指在网络中某个站点上执行查询，查询网络中另一个站点上存放的数据。3）全局查询 全局查询是指在网络中对个站点上执行查询，查询网络中多个站点上的数据，

20、最后汇总查询结果到发出查询的站点。,3.3分布式查询的分类,全局查询处理和优化涉及的问题 1.查询分解2.选择操作执行的次序3.选择执行操作的方法4.确定执行点,3.4 连接查询的优化,两种优化方法半连接：缩减关系（或片段）进而节省传输开销直接连接,3.4 连接查询的优化,3.4.1采用半连接方法表示连接操作1.半连接操作半连接操作是由投影和连接操作导出的一种关系代数操作。假定，由两个关系R和S，在属性R.A=S.B上做半连接操作可表示为 R S R(B(S)若采用半连接方法表示这两个关系R和S，在属性R.A=S.B上做连接操作，则有R S=(R S)S,A=B,A=B,A=B,3.4 连接查

21、询的优化,2.采用半连接方法表示连接操作的操作过程和代价估算设关系R和S分别存放在结点r和s上,1.在结点s作关系S的投影2.把投影 送到结点r，代价为 C0 C1 size(B)val(BS)3.在结点r计算半连接，结果为R，R=R S4.把R从结点r送到结点s，代价为C0 C1 size(R)card(R)5.在结点s执行连接操作,B(S),B(S),3.4 连接查询的优化,半连接方案的总代价Csj 2C0 C1(size(B)val(B(S)+size(R)card(R)直接连接代价Cjn=C0 C1 size(S)card(R)Csj Cjn 时采用半连接。,3.4 连接查询的优化,3

22、.4.2 直接连接在实际应用中，应根据环境条件考虑传输与局部处理的相对费用，直接连接操作的一般常用策略可以分为两种情形1.两个关系在同一站点（1）嵌套循环法（2）排序扫描法2.两个关系在不同站点（1）整体传输（2）按需传输,分布式系统中的死锁处理,4 分布式系统中的死锁处理4.1全局死锁与等待图4.2死锁的预防方法4.3死锁的检测和解决方法,4.1全局死锁与等待图,死锁发生的条件互斥条件：事务请求对资源的独占控制等待条件：事务已持有分配给它的资源,又去申请并等待别的资源非抢占条件：直到资源被持有它的事务释放前,不可能将资源强制从持有它的事务夺去循环等待条件：存在事务互相等待的等待圈死锁分类局部

23、死锁：仅在一个站点上发生的死锁全局死锁：涉及多个站点的死锁(即等待圈由多个站点组成),4.1全局死锁与等待图,相互等待引起的全局死锁,4.1全局死锁与等待图,4.1全局死锁与等待图,等待图一种用来表示事务之间相互等待关系的有向图,是分析死锁的有用工具节点表示事务带有箭头的有向边表示“等待”关系如果等待图有回路，就说明有死锁等待图分类局部等待图(LWFG)全局等待图(GWFG),4.1全局死锁与等待图,4.2 死锁的预防方法,解决死锁的方法死锁预防，使引起死锁的必要条件不成立所有资源排序,按资源序列申请将所有并发事务排序,按标识符或开始时间有死锁危险时，事务退出已占有的资源，有两种方法等待-死亡

24、(Wait-Die)：总是重启较年轻的事务(非占先权)受伤-等待(Wound-Wait)：年轻的等待年老的,较年轻的重启,而重启事务并不一定是目前正申请的事务(占先权),4.2 死锁的预防方法,等待-死亡模式如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年老时（TiTj），则Ti被终止并带有同一时间戳重新启动最好总是重新启动较年轻的事务允许较年老的事务去等待已持有资源的较年轻的事务但不允许较年轻的事务去等待较年老的事务受伤-等待模式如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年轻时（TiTj），才允许Ti等待否则，Ti比Tj年老（TiTj），则Tj被终止并

25、带有同一时间戳重新启动,而Ti得锁执行只有年轻的等待年老的,4.3 死锁的检测和解决方法,集中式死锁检测选择一个站点负责整个系统的死锁检测,死锁检测器放到这个站点每个站点的锁管理器周期性地将本站点的LWFG(局部等待图)传送给死锁检测器,死锁检测器构造GWFG（全局等待图）,并在其中寻找回路或者，其它每个站点上的锁管理器周期性地把记录本站点上事务的开始时间，对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站点，由它维护一张全局封锁动态表，形成GWFG,并在其中寻找回路如果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢复，释放资源，使得其它事务继续进行。选择的标准是尽可能使撤销

26、并恢复的代价最小，如撤销年轻的事务，撤销占有较少资源的事务，撤销具有最短运行时间的事务，撤销具有最长运行时间的事务等，使系统情况而定,4.3死锁的检测和解决方法,层次式死锁检测以层次方式组织成员DBMS中的死锁检测器死锁发生时,常常只涉及部分站点层次检测的层次结构与网络拓扑结构有关减少了对中心站点的依赖性，从而减少了传输开销,4.3 死锁的检测和解决方法,层次式死锁检测的步骤树叶是各站点的局部死锁检测器，在本站点建立局部等待图本站点的死锁检测器找出本站点局部等待图中的任何回路，并把有关潜在全局回路的信息发送给上一层死锁检测器每个非本地死锁检测器只对它所涉及的紧挨下层进行死锁检测，合并这些接收到

27、的有关潜在全局回路的信息，并找出任何回路如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路这样，逐层检测，直到最高层。,4.3 死锁的检测和解决方法,4.3 死锁的检测和解决方法,分布式检测每个站点的检测死锁责任相同,站点之间交换信息(LWFG)，是为了确定全局死锁EX（外部结点）是指本地事务正在等待的其他事务所在的还不确定的站点,4.3 死锁的检测和解决方法,分布式死锁检测算法使用局部信息建造LWFG,该LWFG包含EX节点对每次接收到的信息,执行如下对LWFG的修改对报文中的每个事务,若LWFG中不存在,则将其加入从EX节点开始,按照报文所给的信息,建立一个到下一个事务的边在新的LWFG中寻找不含EX的Loop,若存在,则检测到死锁在新的LWFG中找到含有EX的Loop,于是有潜在的死锁,再按规定向外传送信息,