分布式数据库.

分布式数据库1分布式数据库系统概论2分布式数据库系统的设计3查询处理和优化4分布式系统中的死锁处理分布式数据库系统概论1.分布式数据库系统概论1.1分布式数据库系统1.2分布式数据库系统的特点1.3分布式数据库系统的体系结构1.4分布式数据库管理系统1.1分布式数据库系统–分布式数据库系统，通俗地说，是物理上分散而逻辑上集中的数据库系统。–分布式数据库系统使用计算机网络将地理位置分散而管理和控制又需要不同程度几种的多个逻辑单位连接起来，共同组成一个统一的数据库系统。因此，分布式数据库系统可以看成是计算机网络与数据库系统的有机结合。1.1分布式数据库系统图1一个分布式数据库系统［例1］如图1所示1.1分布式数据库系统—区分一个系统是若干集中式数据库的简单连网还是分布式数据库系统的技术要点在于：系统是否支持全局应用—一个典型的例子是银行转账从一个分行的账户(设在DB1数据库)中转移若干金额到另一个分行的账户(设在DB3数据库)中去•要同时更新两个结点上的数据库1.1分布式数据库系统图2一个多处理机系统(SN并行结构)［例2］如图2所示1.1分布式数据库系统–多处理机系统(SN并行结构)•没有局部应用–分布式数据库不仅要求数据的物理分布，而且要求这种分布是面向处理、面向应用的1.2分布式数据库系统的特点•（1）数据独立性–逻辑独立性–物理独立性–数据分布独立性(分布透明性)•用户的应用程序书写起来就如同数据没有分布一样分布式数据库系统概论•（2）集中与自治相结合的控制结构–数据共享：•(1)局部共享•(2)全局共享–控制机制：•集中•自治分布式数据库系统概论•（3）适当增加数据冗余度–提高系统的可靠性、可用性–提高系统性能•（4）全局的一致性、可串行性和可恢复性–局部数据库要保证ACID–全局数据库也要保证ACID1.3分布式数据库系统的模式结构图3分布式数据库系统的模式结构1.3分布式数据库系统的模式结构•分布式数据库系统增加的模式级别–(1)全局外模式(GlobalExternalSchema)是全局应用的用户视图，所以也称全局视图。分布式数据库的全局视图不是从某一个具体站点的局部数据库中抽取，而是从一个由各局部数据库组成的逻辑几何中抽取，即全局外模式是全局概念模式的子集。然而，对全局用户而言，都可以认为在整个分布式数据库系统的各个站点上所有数据库如同在本站点上一样，只关心他们自己所使用的那部分数据。–(2)全局概念模式(GlobalConceptualSchema)–全局概念模式描述分布式数据库中全局数据的逻辑结构和数据特性。1.3分布式数据库系统的模式结构–(3)分片模式(FragmentationSchema)–描述全局数据的逻辑划分；描述数据分片或定义分片，以及全局关心与片段之间的映像。这种映像是一对多的，即一个全局关系可对应多个片段，而一个片段只能来自一个全局关系。–(4)分布模式(AllocationSchema)•定义片段的存放地点1.4分布式数据库管理系统1.4.1分布式数据库管理系统的功能•分布式数据库管理系统(DistributedDataManagementSystem，D-DBMS)是分布式数据库系统的核心，负责实现分布式数据库的建立、查询、更新、复制和维护等功能，同时还包括提供分布透明性，查询优化、协调全局事务的执行，协调各局部DBMS共同完成全局应用，保证数据库的全局一致性，执行并发控制，实现更新同步和全局恢复等功能。1.4分布式数据库管理系统DDBMS除了提供集中式DDBMS所提供的功能外，还必须能够提供一下集中式DDBMS所不能提供的功能。1）数据跟踪：具有能够通过扩展DDBMS日志来记录数据分布、分片和复制的能力。2）分布式查询处理：具有能够通过通信网络存取远程站点的数据，以及在不同站点间传输请求和数据的能力。3）分布式事务管理：具有能够为需要从多个站点存取数据的查询和事务执行策略的能力，以及将分布式数据的存取和整个数据库完备性的维持保持同步的能力。1.4分布式数据库管理系统4）复制数据的管理：具有能够把数据库从单个站点故障和新类型故障中恢复的能力5）安全性：分布式事务的执行必须具有适当的数据安全管理，以及用户授权/存取权限的安全管理。6）分布式目录管理：目录包含了数据库中有关数据的信息，它对整个分布式数据库来说是全局的，对于每个站点来说又是局部的。1.4分布式数据库管理系统•1.4.2分布式数据库管理系统的结构•根据分布式数据库系统的特点，可以将分布式数据库管理系统的结构分为以下四个功能模块：1.查询处理模块查询分析优化处理2.完整性处理模块该模块主要负责维护数据库的完整性和一致性，检查完整性规则，处理多副本数据的同步更新等。1.4分布式数据库管理系统•3.调度处理模块•调度处理模块就负责向有关的站点发出命令，使相应站点的DBMS执行这些局部处理。•4.可靠性处理模块•分布式数据库系统基于计算机网络，自然就会增加产生故障的因素。可靠性处理模块负责不断地监视系统的各个部分是否有故障出现。当故障修复后，可靠性处理模块负责将该部分重新并入系统，使之继续有效地运行，并保持数据库的一致性状态。分布式数据库系统的设计•2分布式数据库系统的设计•2.1分布式数据库系统的设计方法•2.2数据分片•2.3分布透明性2.1分布式数据库系统的设计方法•（1）自顶向下设计方法•设计集中式数据库的一般方法包括四个阶段：需求分析、概念设计、逻辑设计和物理设计。分布式数据库设计在这四个阶段的基础上要增加一个新的阶段，称作分布设计，它位于逻辑设计与物理设计之间，以一个全局的、与站点无关的模式作为输入，以产生分布式数据库各站点的子模式作为结果输出。包括数据的分片设计和片段的位置分配设计。2.1分布式数据库系统的设计方法•（2）自底向下设计方法•自底向下设计方法的重点是把现有的各种不同的数据库模式作为全局模式。所谓集成就是把公用数据定义整合起来，并解决同一数据不同表示方法之间的冲突。2.2数据分片•数据分片–有利于按照用户的需求较好地组织数据的分布–有利于控制数据的冗余度•数据分片的方式–水平分片–垂直分片–混合分片–导出分片2.2数据分片•水平分片–按一定的条件将关系按行(水平方向)分为若干不相交的子集，每个子集为关系的一个片段。•垂直分片–指将关系按列(垂直方向)分为若干子集。–每个片段通常都包含关系的码2.2数据分片•导出分片–是指导出水平分片，即水平分片的条件不是本身属性的条件而是其他关系的属性的条件。2.2数据分片[例]学生选课关系SC(Sno，Cno，Grade)，按照学生年龄＞18岁和≤18岁分片(学生年龄是学生关系Student的属性)–年龄＞18岁的学生选课片段由下面的查询结果组成：SELECTSno，Cno，GradeFROMS，SCWHERES.Sno＝SC.SnoANDS.Sage＞18；–年龄≤18岁的片段SC_B由下面的查询结果组成：SELECTSno，Cno，GradeFROMS，SCWHERES.Sno＝SC.SnoANDS.Sage≤18；2.2数据分片•混合分片–是指按上述三种分片方式得到的片段继续按另一种方式分片。•例如，先按垂直分片再按水平分片方式继续分片。•例如，先按水平分片得到的某一片段再进行垂直分片。2.2数据分片•分片应满足的条件–完全性各片段定义中的谓词的集合必须是完整的，即至少是它们允许值的集合。例如：SEX={'M'，'F'}季节={春，夏，秋，冬}–不相交性如果谓词集合是互斥的，它们的片段必不相交–可重构性如果谓词集合是完整的，则通过并操作总能重构全局关系2.3分布透明性•分片透明性–最高层次–用户或应用程序只对全局关系进行操作而不必考虑关系的分片•位置透明–下一层次–用户或应用程序不必了解片段的存储场地，当存储场地改变了，由于分片模式到分布模式的映像(映像3)，应用程序不必改变•局部数据模型透明性–较低层次–是指用户或用户程序不必了解局部场地上使用的是哪种数据模型，模型的转换以及数据库语言的转换均由映像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分布透明性•情况1系统具有分片透明性Scanf(“%s”,Snumber)；EXECSQLSELECTSname,SageINTO:NAME,:AGEFROMStudentWHERESno＝：Snumber；Printf(%s，%d，NAME，AGE)；程序变量2.3分布透明性•情况2系统具有位置透明性，但不具有分片透明性Scanf(%s“,Snumber);EXECSQLSELECTSname,SageINTO:NAME,:AGEFROMS_AWHERESno＝:Snumber;If(!FOUND)｛EXECSQLSELECTSname,SageINTO:NAME,:AGEFROMS_BWHERESno＝:Snumber;｝Printf(%s,%d“,NAME,AGE)；2.3分布透明性•情况3系统只具有局部数据模型透明性，不具有位置透明性Scanf(%s“,Snumber);EXECSQLSELECTSname,SageINTO:NAME,:AGEFROMS_AATSite1WHERESno＝:Snumber;If(!FOUND){EXECSQLSELECTSname,SageINTO:NAME,:AGEFROMS_BATSite2WHERESno＝:Snumber;}Printf(“%s,%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字节长。•查询：求供应红色零件的、北京的供应商号SELECTS.SnoFROMS，P，SPWHERES.City='北京'ANDSP.Pno=P.PnoANDP.Color='红色'3.1一个实例•估算值(某些中间结果的元组数)红色零件数=10北京供应商的装运单数=105•对通信系统的假定数据传输速度=104字节/秒传输延迟=1秒3.1一个实例•6种可能的查询存取策略，对每种i分别计算通信时间T[i]：T[i]＝总传输延迟+总数据量/数据传输速度(单位：b/s)•策略1把关系P传送到场地A，在A地进行查询处理。T[1]=1+105×100/104=103秒(16.7分)3.1一个实例•策略2把关系S、SP传到场地B，在B地执行查询处理T[2]=2+(104+106)×100/104≈10100秒(2.8小时)3.1一个实例•策略3在场地A连接关系S和SP，选出城市为北京的元组(105个)，然后对这些元组中的每个元组的Pno，询问场地B，看此零件是否红色。共问答105次，由于不是传送数据，只是消息的问答，所以T[3]=2×105s(2.3天)3.1一个实例•策略4在场地B选出红色零件的元组(10个)，然后对每一个元组逐一检查场地A，看北京供应商的装运单中是否有这个零件装运单(若有则选出S#)。每做这样一次检查包括2次消息，共问一答10次，所以T[4]=2×10=20秒3.1一个实例•策略5在场地A选出北京的供应商的装运单把结果送到场地B，在场地B完成最后处理，所以T[5]=1+(105×100)/104≈1000秒(16.7分)3.1一个实例•策略6在场地B的