第七章分布式数据库系统数据库系统外部体系结构集中式数据库系统Ｃ／Ｓ数据库系统三层数据库系统并行数据库系统分布式数据库系统§7.1基本概念基本定义D-DBS的特点D-DBS的优点D-DBS的体系结构§7.1基本概念背景数据库系统+计算机网络§7.1基本概念基本特性分布性：数据存储在不同场地上。与集中式数据库不同。逻辑整体性：数据逻辑上是相互联系的一个整体。与分散在计算机网络不同站点上的一组没有相互联系的本地数据库区别开来。定义描述定义：D-DBS是一个数据集合，这些数据在逻辑上属于同一个系统，但在物理上分布在计算机网络的不同结点上。§7.1基本概念精确定义：D-DBS是一个数据集合，这些数据，分布在计算机网络的不同计算机上，网络中每个结点具有独立处理的能力，可以执行局部应用，同时每个结点也能通过网络通讯支持全局应用。 分布式数据库强调场地自治性（局部应用）以及自治场地之间的协作性（全局应用）。“在自治的结点之间协同工作”二、D-DBS的特点数据独立性 D-DBS除了集中式DBS的物理独立性及逻辑独立性，还有数据分布的独立性，也称分布透明性，即用户不必关心数据物理位置的分布。集中与自治相结合的控制结构集中式DBS中，控制是集中的，统一由DBA维护。D-DBS中，控制是分层的： 全局DBA：管理整个数据库 本地DBA：管理本地数据库适当增加数据冗余集中式DBS中，尽可能减少数据冗余以避免不一致性及节省存储空间。D-DBS中，适当增加冗余，在不同场地存储同一数据的多个副本。提高系统可靠性、可用性：一场地发生故障，可存取另一场地同一副本。提高系统性能：存取距离最近的数据副本，减少通讯代价。全局的一致性、可串行性、可恢复性 涉及多个结点。经济上和组织上的理由数据库的使用单位组织上、地理上是分布的既有数据库互连历史继承；数据资源共享系统规模逐步扩展增加结点，不影响现有系统运行减少通讯开销提高应用的本地化提高系统的可靠性与可用性多副本机制分布式数据库系统体系结构G-外模式 全局应用的用户视图。G-概念模式 定义D-DBS中数据的整体逻辑结构，数据如同没有分布一样。分片模式 每一个关系可以分为若干互不相交的部分，每一部分称为一个片段。分布模式 定义片段的存放地点。一、数据在分布式数据库的存储途径复制 系统维护关系的几个完全相同的副本，这些副本存储在不同的结点上。分片 关系被划分为几个片段，各个片段存储在不同的结点上。复制+分片 关系被划分为几个片段，系统为每个片段维护几个副本。二、数据复制优点可用性增加并行度缺点一致性维护结论有利于只读事务，增加更新事务开销。三、数据分片优点将关系分片，有利于按用户需求组织数据的分布。如产品→（内销产品，出口产品）。分片方式水平分片垂直分片导出分片混合分片水平分片 将关系r按行分为若干子集r1，r2，…，rn，每个子集ri称为一个水平片段。 一个水平片段可以看成是关系上的一个选择。ri=?P（i）（r） 如C_S=?DNO=D08（S） 关系的重构可以通过并运算来实现。r=r1∪r2∪…∪rn垂直分片 将关系r按列分为若干属性子集r1，r2，…，rn，每个子集ri称为一个垂直片段。 一个垂直片段可以看成是关系上的一个投影。ri=∏Ri（r） 其中Ri是r的一个属性子集。 如P_S=∏PNO，SAL（P） 关系的重构可以通过连接运算来实现。r=r1r2…rn 所有分片都包括每个元组的唯一标识码tuple_id。导出分片导出水平分片，分片的条件不是关系本身属性条件，而是其它关系的属性条件。如SC（S#，C#，G）按学生系别分片。混合分片关系按某种方式分片后，得到的片段再按另一种方式继续分片。如SC（S#，C#，G）按学生系别分片，再对每个片段按成绩（及格，不及格）分片。分片透明性 用户或应用程序只对全局关系进行操作而不必考虑关系的分片。如果分片模式改变了，通过调整全局模式与分片模式之间的映象关系来保持全局模式不变。位置透明性 用户或应用程序不必了解片段的存储位置。局部数据模型透明性 用户或应用程序不必了解局部场地上使用的是哪种数据模型。示例：设有全局关系S，它被划分为两个片段S-A（本科生），S-B（研究生），S-B有两个副本。写一个查询，输入学号，输出学生姓名。⒈系统具有分片透明性 scanf(“%s”,S_NO); EXECSQLselectSN into：S_NAME fromS whereSNO=:S_NO; printf(“%d,%s”,S_NO,S_NAME);⒉系统具有位置透明性，但不具有分片透明性 scanf(“%s”,S_NO); EXECSQLselectSNinto：S_NAME fromS_A whereSNO=:S_NO; if(!FOUND) EXECSQLselectSNinto：S_NAME fromS_B whereSNO=:S_NO; printf(“%d,%s”,S_NO,S_NAME);⒊系统具有局部模型透明性，但不具有位置透明性 scanf(“%s”,S_NO); EXECSQLselectSNinto：S_NAME fromS_AatSite_1 whereSNO=:S_NO; if(!FOUND) EXECSQLselectSNinto：S_NAME fromS_BatSite_2(或Site_3) whereSNO=:S_NO; printf(“%d,%s”,S_NO,S_NAME);五、数据项的命名每个数据项（关系、副本、片段）必须有唯一的名字，在分布式数据库系统中必须保证在不同的结点上不会用同一个名字来代表不同的数据项。途径1：名字服务器所有名字都在名字服务器中注册，每个名字对应一个数据项。缺陷：名字服务器成为名字解析的瓶颈；依赖性大。途径2：将结点标识作为前缀加到该结点数据项的名字前保证唯一性，不须中央控制；不能保证网络透明性。途径3：别名用户使用简单的别名，别名被系统翻译成完整的名字。别名到真实名字的映射形成一张别名表被存储在系统的每一个结点上。当用户引用别名时，系统通过查找别名表找到实际的数据项。对照路由表。假定每条元组100bit大小求供应红色零件的、北京的供应商号码 selectS.S#fromS,P,SP whereS.CITY=‘北京’andS.S#=SP.S# andSP.P#=P.P#andP.COLOR=‘红色’⒈把关系P从B站传送到A站，在A站进行查询 传送时间T=1+105?100/104=103s⒊在A站连接S与SP，选出城市为北京的元组（假定有105个），然后对其中每个元组的P#，询问B站，看其是否为红色。 传送时间T=2?105s⒋在B站选出红色零件（假定有10个），然后对每个元组询问A站，看北京的供应商是否供应此零件。 传送时间T=2?10=20s⒌在A站选出北京的供应商（105个），传送到B站，在B站完成查询。 传送时间T=1+105?100/104=103s⒍在B站选出红色零件（10个），把结果传送到A站，在A站完成查询。 传送时间T=1+10?100/104=1.1s一、半连接运算定义 半连接RS=?R（RS） 半连接作用 找出R中能够与S中元组相连接的元组来，类似于在连接之前先做选择和投影。RS=（RS）SRS=（SR）R半连接的非对称性RS?（SR）半连接在分布式数据库中的应用 R与S位于不同场地S1，S2上，其属性组分别为R1，R2，要在S1场地求R和S的连接结果。 ⒈在S1场地对R做投影，将R缩减为R''，R''=?R1?R2（R） ⒉将R''送往场地S2。 ⒊在S2场地完成S与R''的半连接操作，将S缩减为S''，S''=SR'' ⒋将S''送回场地S1。 ⒌在S1场地完成R与S''的连接操作，RS=RS''二、通讯代价模型TC（X）=C0+XC1其中X为数据传输量。C0为两结点初始化一次传输所花费的开销。C1为传输率，即单位数据传输所花费的时间。采用半连接的通讯代价：CSJ=2C0+(size(R'')card(R'')+size(S)card(S''))C1 不采用半连接的通讯代价：CJN=C0+size(S)card(S'')C1当S中参与连接的元组足够少时采用半连接策略是有利的。一、分布式事务数据的分布导致事务具有了分布性。一个全局事务的执行被划分为在许多场地上子事务的执行。示例：银行在两个帐户之间转帐。 对集中式数据库，单个事务T：A：=A-100，B：=B+100 对于分布式数据库，假定A在S1,S2各有一副本，B在S3,S4各有一副本，用户请求在S5发出，则分布事务T由T1,T2,T3,T4,T5构成： T1,T2：A：=A-100 T3,T4：B：=B+100 T5：结果返回给用户二、事务管理模型三、系统故障分布式系统故障结点故障，消息丢失，通信链路故障，网络分割。网络拓扑性能指标：安装开销，通讯开销，可用性。四、事务两阶段提交协议 假定事务T在结点Si发起阶段1：事务协调器TCi向日志中加入一条记录，并强制该日志写入稳存中。TCi将消息发送到执行T的所有结点上。当某结点接受到上述消息时，该结点的TM回答确定是否提交T中属于它的那部分，若否，则TM将记录加入到日志中，并向TCi发送消息。若是，则TM将记录加入到日志中，并将日志强制写入稳存中，并向TCi发送消息。阶段2：当TCi收到所有结点对消息的回答时，或等待响应的时间已过，TCi决定事务T是提交还是中止。如果TCi收到的都是消息，事务就可以提交，否则事务必须被中止。根据结果的不同向日志中写入或者，并强制将日志写入稳存中。向所有参与的结点发送消息或。结点收到此消息后，就把该消息记入日志中。（向TCi发送消息；TCi收到该消息后，将记录加入到日志中）。一、单一锁管理器模式系统维护位于单一节点（Si）上的单一锁管理器。如果有事务欲封锁某一数据项，它向Si发送锁请求，Si决定是否可以立即满足该请求。是，向请求节点发送消息。否，推迟发送消息直至锁能够被授予。读数据可以从存在数据副本的任一个节点读取，写数据时所有包含该数据副本的节点都必须参与到写操作中。优点：实现简单，死锁处理简单。缺点：锁管理器节点可能成为系统瓶颈；对锁管理器节点依赖大，系统脆弱性大。二、多数协议每个节点维护自己的局部锁管理器。当一节点欲封锁另一节点Si上的且未被复制的数据库项Q时，它向Si发送一条锁请求消息；如果Q被施加了不相容锁，则请求被推迟直至被满足，然后Si向请求节点发送消息。如果Q在n个不同的节点上有副本，则锁请求消息被发送到这n个节点，必须获得多数副本上的封锁后，事务才能开始对Q的操作。优点：分散控制。缺点：消息传递太多，死锁处理复杂。三、主本协议选择一个节点上的副本作为数据主副本，此节点称为该数据项的主节点。当有事务请求对数据项Q的封锁时，它向Q的主节点发出请求。优点：简单缺点：对主节点依赖大，如果主节点不可用，则数据项的其他副本也不可用。四、有偏协议局部锁管理器类似于多数协议。但对共享锁和排它锁的处理不同。共享锁：事务需要封锁数据项Q时，只需向包含Q的副本的一个节点上的锁管理器发送请求。排它锁：事务需要封锁数据项Q时，需要向包含Q的副本的所有节点上的锁管理器发送请求。优点：读操作的封锁开销小。§7.3DDBMS的功能及组成接受用户的请求，并判定把它送到哪里，或必须访问那些计算机才能满足该要求。访问网络数据字典，了解如何请求和使用其中的信息。如果目标数据存储于系统的多个计算机上，就必须进行分布式处理。通信接口功能。在用户、局部DBMS和其他计算机的DBMS之间进行协调。在一个异构型分布式处理环境中，还需要提供数据和进程移植的支持。这里的异构型是指各个场地的硬件、软件之间存在着差别。二、DDBMS的功能§7.3DDBMS的功能及组成在DDBS中，数据分布于整个网络的各个场地上，当用户请求一个查询时，往往会引起数据的传输，这需要花费相当高的代价。因此，需要尽可能采用最佳优化算法，以减少传输费用，提高传输效率。查询处理模块由两部分组成，一是查询分析，对查询语句进行分析、检查，弄清楚查询请求所使用的资源；二是优化处理，以尽可能小的代价完成一次查询。三、DDBMS的组成查询处理模块：§7.3DDBMS的功能及组成三、DDBMS的组成该模块主要负责维护数据库的完整性和一致性，检查完整性规则，处理多副本数据的同步更新等。该模块有以下两个功能：一是确定使用的数据副本，当查询处理模块分析出要使用的数据后，它根据网络数据目录计算出使用不同副本的代价，进一步确定供查询使用的数据副本及该副本所在的场地，并且尽可能使这一代价极小化；二是维护数据库的完整性，提高并发控制的能力。完整性处理模块：§7.3DDBMS的功能及组成一旦确定了查询处理的策略，就要进行一些局部处理和数据传输，这时调度处理模块就负责向有关场地发布命令，使相应场地的DBMS执行这些局部处理；同时发布命令在相应场地之间进行必要的传输；最后，完成查询并把结果传送回发送该查询的场地。三、DDBMS的组成调度处理模块：§7.3DDBMS的功能及组成可靠性高是DDBS的一个主要优点。由于数据具有多个副本，当系统局部出现故障时，所需要的数据可从其它场地获得。可靠性处理模块负责不断地监视系统的各个部分是否有故障出现。当故障修复后，可靠性处理模块负责将该部分重新并入系统，使之继续有效地运行，并保持数据库的一致性状态。三、DDBMS的组成可靠性处理模块：§7.3DDBMS的功能及组成三、DDBMS的组成DDBMS的一般功能结构实际的数据错误对网络的监视信息需要的数据分布策略数据局部处理命令用户查询查询分析优化算法调度处理模块计算机LDBMSDB查询处理模块网络完整性处理模块可靠性处理模块系统DB数据定位§7.4分布式查询处理半连接运算通讯代价模型Site-ASite-BS(S#,CITY)104个元组SP(S#,P#)106个元组P(P#,COLOR)105个元组网络传输速度104bps传输延迟1s§7.4分布式查询处理S,SPP传P 传送时间T=总传输延迟+总数据量/传输速度§7.4分布式查询处理⒉把关系S，SP从A站传送到B站，在B站进行查询 传送时间T=2+(104+106)?100/104?104sS,SPP传S,SP§7.4分布式查询处理S,SPP问答§7.4分布式查询处理S,SPP问答§7.4分布式查询处理S,SPP传?(S)SP§7.4分布式查询处理S,SPP传?(P)§7.4分布式查询处理=§7.4分布式查询处理§7.4分布式查询处理§7.4分布式查询处理§7.4分布式查询处理§7.5分布式事务模型分布式事务事务管理模型系统故障两阶段提交协议§7.5分布式事务模型TC1TM1TCnTMn事务管理器TM：管理那些访问存储在一个局部结点中的数据的事务。事务可以是局部事务，也可以是全局事务的一部分。事务协调器TC：协调该结点上发起的各事务（局部的或全局的）的执行。§7.5分布式事务模型事务管理器功能维护一个用于恢复的日志。参与适当的并发控制模式，以协调在该结点上执行的事务的并发执行。事务协调器功能启动事务的执行。将事务分解为若干子事务，并将子事务分派到适当的结点上去执行。协调事务的终止，保证事务在所有的结点上都提交或都中止。一个全局事务的各个子事务要么全部执行，要么全部中止。§7.5分布式事务模型ABCDABCDABCDABCDABCDE§7.5分布式事务模型§7.5分布式事务模型§7.5分布式事务模型单一锁管理器模式多数协议主本协议有偏协议§7.6并发控制§7.6并发控制§7.6并发控制§7.6并发控制§7.6并发控制本章主要内容基本概念分布式数据存储DDBMS的功能及组成分布式查询处理分布式事务模型并发控制DB1DB1DB1计算机1计算机1计算机1通讯网络北京重庆上海银行系统一、基本定义一、基本定义一、基本定义§7.1基本概念§7.1基本概念§7.1基本概念三、D-DBS的优点G-外模式G-外模式G-概念模式分片模式分布模式L-概念模式L-概念模式L-内模式L-内模式L-DBL-DBG-DBMSG-DBMS§7.1基本概念§7.1基本概念四、D-DBS的体系结构数据在分布式数据库的存储途径数据复制数据分片分布透明性数据项的命名§7.2分布式数据存储§7.2分布式数据存储§7.2分布式数据存储§7.2分布式数据存储§7.2分布式数据存储§7.2分布式数据存储§7.2分布式数据存储§7.2分布式数据存储四、分布（网络）透明性SS-AS-BS-AS-BS-BSite-1Site-2Site-3全局关系片段物理存储§7.2分布式数据存储§7.2分布式数据存储§7.2分布式数据存储§7.2分布式数据存储§7.2分布式数据存储§7.2分布式数据存储§7.3DDBMS的功能及组成DDBS的组成DDBMS的功能DDBMS的组成§7.3DDBMS的功能及组成在集中式DBS中，除了计算机系统本身的硬件和软件外，主要组成成分有：DB、DBMS和用户（包括一般用户和DBA）。DDBS在此基础上作了扩充：一、DDBS的组成DB分为局部DB（LDB）和全局DB（GDB）；DD分为局部DD（LDD）和全局DD（GDD）；DBMS分为局部DBMS(LDBMS)和全局DBMS（GDBMS）；用户也有局部用户和全局用户之分；DBA也有局部DBA和全局DBA之分。§7.3DDBMS的功能及组成全局用户GDDGDB局部用户LDDLDB计算机GDBMSLDBMS计算机GDBMSLDBMS局部用户LDDLDB全局用户GDDGDB计算机GDBMSLDBMS全局用户GDDGDB局部用户LDDLDB网络DDBS的组成框架
A B a1 b1 a2 b1 a2 b3 a2 b4 a3 b3
B C b1 c1 b2 c2 b5 c1 b5 c2 b6 c4 b7 c2 b8 c3
A B a1 b1 a2 b1
|
|
