数据库系统概论第十四章.ppt

第十四章分布式数据库系统,概述,分布式数据库系统是数据库技术和网络技术两者相互渗透和有机结合的结果,分布式数据库和分布式数据库系统,定义分布式数据库是由一组数据组成的，这组数据分布在计算机网络的不同计算机上，网络中每个结点具有独立处理的能力（称为场地自治），可以执行局部应用（只对本结点数据进行存取的应用），同时每个结点也能通过网络通讯支持全局应用（指存取两个或两个以上的结点的数据库应用）。分布式数据库强调场地自治性（局部应用）以及自治场地之间的协作性（全局应用）。,分布式数据库和分布式数据库系统,分布式数据库具有以下两个特点：分布性分布性有两层含义，一是指数据库中的数据不是都存储在同一结点（更确切的讲，不存储在同一计算机的存储设备上），而是分布在多个结点上；二是指各结点具有独立的数据库处理能力，能够有效地支持局部应用。逻辑整体性分布在各结点的数据不是孤立的，而是相互联系的，是一个逻辑整体，能够支持存取多个结点数据的全局应用。,分布式数据库和分布式数据库系统,分布式数据库系统是在集中式数据库系统技术的基础上发展起来的，但不是简单地把集中式数据库分散的实现，它丰富和发展了集中式数据库的许多概念和技术，具有自己独特的特征和性质。具体来说，它具有以下特点：数据独立性数据独立性在分布式数据库系统中具有了更多的含义，它不仅包括数据的逻辑独立性和物理独立性以外，还包括数据的分布独立性（也称分布透明性）。分布透明性指用户不必关心数据的逻辑分片，不必关心数据物理位置分布的细节，不必关心重复副本（冗余数据）一致性问题，也不必关心局部结点上数据库支持哪种数据模型。,分布式数据库和分布式数据库系统,集中与自治相结合的控制机构在分布式数据系统中，数据的共享有两个层次：一是局部共享，即在局部数据库中存储局部结点各用户的共享数据；二是全局共享。即在分布式数据库系统的各个结点也存储供其他结点的用户共享的数据，支持系统的全局应用。因此，相应的控制机构也具有两个层次：集中和自治。分布式数据库系统常常采用集中和自治相结合的控制机构。各局部的DBMS可以独立的管理局部的数据库，具有自治功能。同时系统又设有集中控制机构，协调各局部DBMS的工作，执行全局应用。,分布式数据库和分布式数据库系统,适当增加数据冗余在分布式数据库系统中适当的增加了冗余数据，在不同的结点存储同一数据的多个副本，其原因是：一提高系统的可靠性、可用性，当某一结点出现故障时，系统可以对另一结点的相同副本进行操作，不会因为一处故障而造成整个系统的瘫痪；二是提高系统性能，系统可以选择用户最近的数据副本来进行操作，减少通信代价，改善整个系统的性能。,分布式数据库和分布式数据库系统,全局的一致性、可串行性和可恢复性分布式数据库系统中各局部数据库应满足集中式数据库的一致性、并发事务的可串行性和可恢复性。除此之外还应保证数据库的全局一致性、全局并发事务的可串行性和系统全局的可恢复性。这是因为在分布式数据库系统中全局应用要涉及两个以上结点的数据，全局事务可能由不同结点上的多个操作组成。,分布式数据库和分布式数据库系统,分布式数据库系统的目标适应部门分布的组织结构，降低费用使用数据库的单位在组织上常常是分布的，在地理上也是分布的。分布式数据库系统的结构符合上述分布的组织结构，允许各个部门将自己常用的数据存储在本地，降低了通信代价，提高了响应速度。提高系统的可靠性和可用性将数据分布于多个结点，并适当增加冗余度，可以提供更好的可靠性。,分布式数据库和分布式数据库系统,充分利用数据库资源，提高现有集中式数据库的利用率当在一个大企业内部和大部门中已经建成若干个数据库后，为了利用相互的资源，开发全局应用可以在现有各局部数据库的基础上做一定的修改和重构，建立一个分布式数据库系统。逐步扩展处理能力和系统规模相对于集中式数据库系统，分布式数据库系统能够方便地将一个新结点纳入系统，而不影响现有系统的结构和系统的正常运行，提供了逐步扩展系统能力的较好途径。,分布式数据库的体系结构,映像1,映像2,映像3,映像4,分布式数据库的体系结构,全局外模式全局应用的用户视图，是全局概念模式的子集。全局概念模式定义分布式数据库中数据的整体逻辑结构，使得数据如同没有分布一样。分片模式每一个全局关系可以分为若干互不相交的部分，每一部分称为一个片段。分片模式定义片段以及全局关系到片段的映像。分布模式定义片段的存放结点。,分布式数据库的体系结构,分布（网络）透明性分片透明性用户或应用程序只对全局关系进行操作而不必考虑关系的分片。如果分片模式改变了，通过调整全局模式与分片模式之间的映象关系来保持全局模式不变。位置透明性用户或应用程序不必了解片段的存储位置。局部数据模型透明性用户或应用程序不必了解局部场地上使用的是哪种数据模型。,分布式数据库的体系结构,示例：设有全局关系S，它被划分为两个片段S-A（本科生），S-B（研究生），S-B有两个副本。,分布式数据库设计,数据在分布式数据库中的存储途径数据的重复存储系统在两个或两个以上结点维护关系R的几个完全相同的副本。如果系统的每个结点都存储R的一个副本，则称这种重复存储为完全重复存储。数据重复存储具有以下几个优点：可用性强 如果某个存储R的结点出了故障，系统仍然可以使用其它结点上的副本继续处理用户查询，使系统正常运行。增强并行性 由于R的重复存储，可以使更多的用户并行地查询R。数据的重复存储也会带来一些问题，如增加了更新操作的开销，加大了并行控制的难度,分布式数据库设计,分片存储关系被划分为几个片段，各个片段存储在不同的结点上。将数据分片，使数据存放的单位不是关系而是片段，这既有利于按照用户的需求较好地组织数据的分布，也有利于控制数据的冗余度。分片时必须遵循以下原则：完全性：被划分关系中的每个元组必须属于一个片段。不相交性：同一个关系的片段互不相交。可重构性：如果R被划分为片段R1、R2、Rn，则R能从R1、R2、Rn恢复出来。,分布式数据库设计,分片方式水平分片垂直分片导出分片混合分片,分布式数据库设计,水平分片将关系r依照一定条件按行分为不相交的若干子集r1，r2，rn，每个子集ri称为一个水平片段。一个水平片段可以看成是关系上的一个选择。ri=P（i）（r）如C_S=DNO=D08（S）关系的重构可以通过并运算来实现。r=r1 r2rn,分布式数据库设计,垂直分片将关系r按列分为若干属性子集r1，r2，rn，每个子集ri称为一个垂直片段。一个垂直片段可以看成是关系上的一个投影。ri=Ri（r）其中Ri是r的一个属性子集。如P_S=PNO，SAL（P）关系的重构可以通过连接运算来实现。r=r1 r2 rn所有分片都包括关系的键,分布式数据库设计,导出分片导出水平分片，分片的条件不是关系本身属性条件，而是其它关系的属性条件。如SC（SNO，CNO，G）按学生系别分片。混合分片关系按某种方式分片后，得到的片段再按另一种方式继续分片。如SC（SNO，CNO，G）按学生系别分片，再对每个片段按成绩（及格，不及格）分片。,分布式数据库设计,组合存储这种方法是重复存储和分片存储相结合的方法。关系被划分为几个片段，系统为每个片段维护几个副本，每个副本存放于不同的结点上。,分布式数据库设计,命名和局部自治性每个数据项（关系、副本、片段）必须有唯一的名字，在分布式数据库系统中必须保证在不同的结点上不会用同一个名字来代表不同的数据项。途径1：名字服务器所有名字都在名字服务器中注册，每个名字对应一个数据项。缺陷：名字服务器成为名字解析的瓶颈；其故障将影响整个系统的运行；局部自治性降低。,分布式数据库设计,途径2：将结点标识作为前缀加到该结点数据项的名字前面。使用这一方法，能够保证名字的唯一性，不须中央控制，局部自治性提高；但不能保证网络透明性。,分布式数据库管理系统概述,D-DBMS由四个部分组成：LDBMS，局部场地上的DBMS，主要功能是建立和管理局部数据库，提供场地自治能力，执行局部应用以及全局查询的子查询。GDBMS，全局数据库管理系统，主要功能是提供分布透明性，协调全局事务的执行，协调各局部DBMS以完成全局应用，保证数据库的全局一致性，执行并发控制，实现更新同步，提供全局恢复等功能。,分布式数据库管理系统概述,全局数据字典，存放全局概念模式、分片模式、分布模式等的定义，以及各模式之间的映像定义，存放有关用户存取权限的定义、完整性约束的定义等。通信管理，在分布式数据库各场地之间传送消息和数据，完成通信功能。,分布式数据库管理系统概述,D-DBMS的分类按全局控制发生分类全局控制集中的DDBMS全局数据库器和全局数据字典集中于某一结点，其优点是控制简单，容易实现更新一致性，但该结点容易成为系统的瓶颈，系统也较脆弱。,分布式数据库管理系统概述,全局控制分散的DDBMS全局数据库器和全局数据字典分散在网络上的每一个结点上，每个结点都能完成全局事务的协调和局部数据库事务的控制功能。每个结点既是全局事务的参与者，也是全局事务的协调者。其优点是结点独立，自治性强，但全局控制的协调机制和一致性维护都比较困难。全局控制部分分散的DDBMS介于上述两者之间，根据应用的需要将全局数据库管理器和全局数据字典分散在某些结点上。,分布式数据库管理系统概述,按局部DBMS的类型分类同构型DDBMS每个结点的局部数据库具有相同的DBMS。异构型DDBMS各结点的局部数据库具有不同的DBMS,分布式查询处理,在分布式数据库系统中，数据分布在网络上的多个结点之中，其查询需要由多个结点利用网络协作完成。在集中式数据库中，查询优化的目标是产生最小磁盘I/O数，在分布式数据库中还要考虑网络的传输时间和各结点的并发执行。因此，分布式查询处理较集中式数据库复杂。,分布式查询处理,在分布式数据库系统中，查询可分为三类：局部查询，远程查询，全局查询。局部查询和远程查询只涉及单个结点的数据（本地的或远程的），可以采用集中式数据库的处理技术；二全局查询涉及到多个结点的数据，因此相对复杂的多。,分布式查询处理,分布式查询处理的过程包括：查询变换 将用户查询转换为析取范式或合取范式，并进行语义分析，检查查询的正确性等工作。,分布式查询处理,数据定位 数据定位的目的是把用户定义在全局概念模式上的查询转换为定义在局部概念模式上的查询。由于它定义在片段上，也称为片段查询。设查询Q中包含关系R1、R2、Rn，而且对于1in，Ri已经被划分为m个片段Ri1、Ri2、Rim，Ri=F(Ri1、Ri2、Rim)。Q的数据定位包括两步。第一步，对于1in，用Ri=F(Ri1、Ri2、Rim)代替Q中的Ri，得到一个等价的片段查询FQ。第二步，进一步加工FQ，产生一个与FQ等价并且效率更高的片段查询。,分布式查询处理,全局查询优化 无论是集中式数据库还是分布式数据库其查询策略的选择都是以执行查询的预期代价为依据的。在集中式数据库中，查询执行的开销主要是：I/O+CPU代价。而在分布式数据库中查询执行的开销为：I/O+CPU代价+通信代价。因此在全局查询优化时需要选择执行操作的顺序，降低网络通信的开销。,分布式查询处理,局部查询优化 局部查询优化的目的是为每个局部查询选择优化的执行计划，其方法与集中式数据库的查询优化策略和方法相同。,分布式查询处理,假定每条元组100bit大小求供应红色零件的、北京的供应商号码select S.S#from S,P,SPwhere S.CITY=北京 and S.S#=SP.S#and SP.P#=P.P#and P.COLOR=红色,分布式查询处理,传送时间T=总传输延迟+总数据量/传输速度 1.把关系P从B站传送到A站，在A站进行查询传送时间T=1+105 100/104=103s,分布式查询处理,2.把关系S，SP从A站传送到B站，在B站进行查询传送时间T=2+(104+106)100/104104s,分布式查询处理,在A站连接S与SP，选出城市为北京的元组（假定有105个），然后对其中每个元组的P#，询问B站，看其是否为红色。传送时间T=2 105s,分布式查询处理,在B站选出红色零件（假定有10个），然后对每个元组询问A站，看北京的供应商是否供应此零件。传送时间T=2 10=20s,问,分布式查询处理,5.在A站选出北京的供应商（105个），传送到B站，在B站完成查询。传送时间T=1+105100/104=103s,分布式查询处理,在B站选出红色零件（10个），把结果传送到A站，在A站完成查询。传送时间T=1+10100/104=1.1s,分布式查询处理,半连接运算定义半连接R S=R（R S）,=,分布式查询处理,半连接作用找出R中能够与S中元组相连接的元组来，类似于在连接之前先做选择和投影。R S=（R S）SR S=（S R）R半连接的非对称性R S（S R）,分布式查询处理,半连接在分布式数据库中的应用R与S位于不同结点S1，S2上，其属性组分别为R1，R2，要在S1结点求R和S的连接结果。在S1结点对R做投影，将R缩减为R，R=R1R2（R）将R 送往结点S2。在S2结点完成S与R的半连接操作，将S缩减为S，S=S R将S送回结点S1。在S1结点完成R与S的连接操作，R S=R S,分布式查询处理,通讯代价模型TC（X）=C0+X*C1其中X为数据传输量。C0为两结点初始化一次传输所花费的开销。C1为传输率，即单位数据传输所花费的时间。采用半连接的通讯代价：CSJ=2C0+(size(R)*card(R)+size(S)*card(S)*C1不采用半连接的通讯代价：CJN=C0+size(S)*card(S)*C1当S中参与连接的元组足够少时采用半连接策略是有利的。,分布式数据库系统的事务处理,分布式事务数据的分布导致事务具有了分布性。一个全局事务的执行被划分为在许多结点上子事务的执行。系统不但要保证每个子事务的原子性，还要保证全局事务的原子性。这不是哪一个局部DBMS能够完成的，而是需要在结点间进行协调。,分布式数据库系统的事务处理,示例：银行在两个帐户之间转帐。对集中式数据库，单个事务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+100T5：结果返回给用户,分布式数据库系统的事务处理,分布式事务处理器事务管理器TM：管理那些访问存储在一个局部结点中的数据的事务。事务可以是局部事务，也可以是全局事务的一部分。事务协调器TC：协调该结点上发起的各事务（局部的或全局的）的执行。,分布式数据库系统的事务处理,事务管理器功能维护一个用于恢复的日志。参与适当的并发控制模式，以协调在该结点上执行的事务的并发执行。事务协调器功能启动事务的执行。将事务分解为若干子事务，并将子事务分派到适当的结点上去执行。协调事务的终止，保证事务在所有的结点上都提交或都中止。一个全局事务的各个子事务要么全部执行，要么全部中止。,分布式数据库系统的事务处理,事务两阶段提交协议假定事务T在结点Si发起，阶段1：事务协调器TCi向日志中加入一条记录，并强制该日志写入稳定存储器中。TCi将消息发送到执行T的所有结点上。当某结点接受到上述消息时，该结点的TM回答确定是否提交T中属于它的那部分，若否，则TM将记录加入到日志中，并向TCi发送消息。若是，则TM将记录加入到日志中，并将日志强制写入稳定存储器中，并向TCi发送消息。,分布式数据库系统的事务处理,阶段2：当TCi收到所有结点对消息的回答时，或等待响应的时间已过，TCi决定事务T是提交还是中止。如果TCi 收到的都是消息，事务就可以提交，否则事务必须被中止。根据结果的不同向日志中写入 或者，并强制将日志写入稳定存储器中。向所有参与的结点发送消息或。结点收到此消息后，就把该消息记入日志中。（向TCi发送消息；TCi收到该消息后，将记录加入到日志中）。,分布式并发控制技术,分布式锁技术若分布式数据库中没有重复存储的数据，可以采用如下的分布式锁技术：每个结点保留一个局部锁管理器，处理对存储在本地的数据加锁和释放锁的请求。当事务T希望对结点Si上的数据项Q加锁时，T简单的向结点上的锁管理器发出一个加锁请求。分布式锁技术具有实现简单的特点，它处理一个加锁请求需要两次通信，处理释放锁请求需要一次通信。但其死锁处理较为复杂。,分布式并发控制技术,集中式锁技术集中式锁技术仅有一个锁管理器，这个锁管理器位于唯一一个结点（如Si）上。所有的加锁和释放锁的请求都在该结点上处理。集中式锁技术具有以下优点：实现简单 加锁请求需要两次通信，释放锁请求需要一次通信。死锁处理简单 可按照集中式数据库的方法进行处理集中式锁技术具有以下缺点：瓶颈问题 Si是一个锁管理瓶颈脆弱性 如果Si出现故障，系统无法正常运行。,分布式并发控制技术,混合锁技术混合锁技术是集中式和分布式锁技术的折中。这种技术设置多个锁管理器，每个锁管理器管理一组数据的加锁和释放锁的请求。每个锁管理器位于不同的结点上。,分布式并发控制技术,以多为主的锁协议系统在每个结点上有一个锁管理器。在任何结点Si上的锁管理器管理存储在Si上的所有数据项副本的加锁和释放锁的请求。当事务T请求对数据项Q加锁时，如果n个结点存储Q的副本，则T要向n/2以上的存储Q副本的结点发出加锁请求。,分布式并发控制技术,区分锁类型的锁协议每个结点上有一个锁管理器。每个锁管理器管理所在结点上存储的数据的加锁和释放锁的请求。共享锁和互斥锁采用不同的方式进行处理。当事务T需要在数据项加共享锁时，T直接向一个存储该数据项副本的结点的锁管理器发出加锁请求。当事务T需要在数据项上加互斥锁时，T要向所有包含该数据项副本的结点的锁管理器发出加锁请求。,分布式并发控制技术,主副本锁协议在数据项Q具有多个副本的情况下，选择一个节点上的副本作为数据主副本，此节点称为该数据项Q的主节点。当有事务请求对数据项Q的封锁时，它仅需要向Q的主节点发出一个加锁请求。优点：简单缺点：对主节点依赖大，如果主节点不可用，则数据项的其他副本也不可用。,分布式死锁处理技术,结点1,T4,T2,T3,结点2,分布式死锁处理技术,集中式方法 在集中式方法中，全局等待图（局部等待图的并集）被保存在一个称为死锁检测器的特殊结点上。全局等待图在下列事件发生时被构造或更新：某个局部等待图被加入一条新边或删除一条边。局部等待图发生了较大改变。协调器需要触发死锁检测算法。当死锁检测器被触发时，协调器检查它的全局等待图。如果发现一个环，就选择要放弃的事务解决死锁。协调器需通知所有结点放弃的是哪个事务，使其他结点也放弃该事务。,分布式死锁处理技术,分布式方法在分布式方法中，所有结点对于死锁检测具有相同的职责。每个结点都根据系统的动态行为构造一个全局等待图的子等待图。子等待图必须满足：如果有死锁存在，则至少一个子等待图中出现环。局部等待图中增加了一个结点Tex，用以表示外结点与本结点发生等待关系的子事务。如果局部等待图中含有一个不包含Tex的环，表明系统处于死锁状态。如果存在一个包含Tex的环，需要通过分布式死锁检测算法确定是否出现死锁。,分布式死锁处理技术,如果结点Si的局部等待图中有一个包含Tex的环：Tex Tk1 Tk2 Tkn Tex，说明Si上的事务Tkn正在等待其他结点（如Sj）上的数据项。则结点Si向Sj发送含有这个环的死锁检测信息。结点Sj根据这一信息修改自己的局部等待图，搜索是否存在一个不含有Tex的环，若有则发生死锁。如果存在一个含有Tex的环，则继续上述过程，直到确定是否存在死锁。,分布式死锁处理技术,