高级操作系统 第9章 分布式数据库系统

第9章分布式数据库系统1本章重要概念（一）（1）分布计算的三种形式：处理分布，数据分布，功能分布。（2）C/S系统，工作模式，技术特征，体系结构，两层、三层、多层C/S结构。（3）DDBS的定义、特点、优点、缺点和分类；分布式数据存储的两种形式（分片和分配）。

2本章重要概念（二）（4）DDB的体系结构：六层模式，分布透明性的三个层次，DDBS的组成，DDBMS的功能和组成。（5）分布式查询处理的查询代价，基于半连接的优化策略，基于连接的优化策略。（6）分布式数据库的并发控制和恢复中出现的问题，以及处理机制。

3前言 随着传统的数据库技术日趋成熟、计算机网络技术的飞速发展和应用范围的扩充，数据库应用已经普遍建立于计算机网络之上。这时集中式数据库系统表现出它的不足：数据按实际需要已在网络上分布存储，再采用集中式处理，势必造成通信开销大；应用程序集中在一台计算机上运行，一旦该计算机发生故障，则整个系统受到影响，可靠性不高；集中式处理引起系统的规模和配置都不够灵活，系统的可扩充性差。在这种形势下，集中式DB的“集中计算”概念向“分布计算”概念发展。分布计算主要体现在客户机／服务器模式和分布式数据库体系结构两个方面。本章将分别介绍这两种技术。49.1集中计算与分布计算（一）“集中计算”概念图9.1集中式DB的结构59.1集中计算与分布计算（二）“分布计算”概念处理分布数据分布功能分布69.1集中计算与分布计算（三）客户机／服务器系统的结构图9.2客户机/服务器系统的结构79.2客户机/服务器结构9.2.1C/S系统的计算模式C／S结构的工作模式C／S环境下应用成分的分布C／S主要技术特征8C／S结构的工作模式C／S结构的基本原理是将计算机应用任务分解成多个子任务，由多台计算机分工完成，即“功能分布”原则。客户端完成数据处理，数据表示、用户接口等功能；服务器端完成DBMS的核心功能；9客户机的主要任务管理用户界面接受用户数据处理应用逻辑生成数据库请求向服务器发出数据库请求从服务器接受结果格式化结果10服务器的主要任务接收来自客户机的数据库请求处理对数据库的请求格式化结果并传给客户机进行完整性检查维护数据字典、索引处理数据恢复优化查询/更新处理11C／S环境下应用成分的分布典型应用程序可分解成四个组成部分用户界面的显示逻辑：完成屏幕格式化、屏幕信息读写、窗口管理、键盘及鼠标管理等任务。应用逻辑：根据输入数据来完成业务处理和规则的应用代码。事务逻辑：完成程序中的事务处理。数据管理：由DBMS完成访问实际DB的程序。12C／S主要技术特征按功能划分：服务器是服务的提供者，客户机是服务的消费者。共享资源：一个服务器可以在同一时刻为多个客户机提供服务，并且服务器具有并发控制、封锁等能力协调多用户对于共享资源的访问。不对称协议：在客户机与服务器之间存在着一种多对一的主从关系。定位透明性：C/S系统应该向客户提供服务器位置透明性服务。透明性：是指一种实际存在的事务具有看起来好像不存在的性质。定位透明性：是指用户不必知道服务器的位置，就可以请求服务器的服务。基于消息的交换：客户机和服务器是一对耦合的系统，它们通过消息传递机制互相协作。可扩展性。C/S系统可以水平地或垂直地扩展。139.2.2C／S系统的体系结构服务器(提供服务)服务器要求提供大容量的存诸能力，强大的数据处理和管理能力，以及并发运行多个进行的能力。还应能提供包括通信、电子邮件和事务处理能力。客户机可以观察和体会到服务器提供的服务中间件（范指客户机与服务器之间的软件）DB中间件：基于SQL的异构数据库互连操作事务处理中间件：基于RPC（远程过程调用）等，共享不同服务资源组件中间件：电子邮件及LotusNotes等对象中间件：允许客户机调用驻留在远程服务器上的对象。149.2.3C／S结构的演变（一）两层C／S结构图9.5两层C/S结构15C/S结构的特点客户机主要负责用户界面的处理和显示、应用逻辑的处理，通过网络与服务器交互；服务器负责向客户机提供数据服务，实现事务逻辑和数据管理，有时也完成有限的应用逻辑。客户软件和服务器软件可以放在一台计算机上，但多数情况下放在网络中的不同计算机上。169.2.3C／S结构的演变（二）三层C／S结构图9.5WWW的三层C/S结构图9.6三层C/S结构表示层功能层数据层179.2.3C／S结构的演变（三）多层C／S结构前端的客户层：负责提供可以移植的表达逻辑中间的应用层：实现各类业务逻辑后端的数据管理与服务层：提供对专门服务的访问图9.8多层C/S结构189.2.4网络服务器的类型DB服务器文件服务器事务服务器文档服务器Web服务器电子邮件服务器其他应用服务器199.3分布式数据库系统概述 随着传统的数据库技术日趋成熟、计算机网络技术的飞速发展和应用范围的扩大，以分布式为主要特征的数据库系统的研究与开发受到人们的注意。分布式数据库是数据库技术与网络技术相结合的产物，在数据库领域已形成一个分支。分布式数据库的研究始于20世纪70年代中期。世界上第一个分布式数据库系统SDD-1是由美国计算机公司（CCA）于1979年在DEC计算机上实现。20世纪90年代以来，分布式数据库系统进入商品化应用阶段，传统的关系数据库产品均发展成以计算机网络及多任务操作系统为核心的分布式数据库产品，同时分布式数据库逐步向客户机／服务器模式发展。209.3.1从集中式、分散式到分布式随着数据库应用的不断发展，规模的不断扩大，逐渐感觉到集中式系统也有不便之处。如大型DBS的设计和操作都比较复杂，系统显得不灵活并且安全性也较差。因此，采用将数据分散的方法，把数据库分成多个，建立在多台计算机上，这种系统称为分散式系统。在这种系统中，数据库的管理、应用程序的研制等都是分开并相互独立，它们之间不存在数据通信联系。由于计算机网络通信的发展，有可能把分散在各处的数据库系统通过网络通信连接起来，这样形成的系统称为分布式数据库系统（DDBS）。DDBS兼有集中式和分散式的优点。这种系统有多台计算机组成，各计算机之间由通信网络相互连系着。219.3.2DDBS的定义分布式系统是用通信网络连接起来的结点（亦称为“场地”）的集合，每个结点都是拥有集中式数据库的计算机系统。定义9.1DDBS是物理上分散逻辑上集中的数据库系统，系统中的数据分布存放在计算机网络的不同场地的计算机中，每一场地都有自治处理（即独立处理）能力并能完成局部应用，而每一场地也参与（至少一种）全局应用，程序通过网络通信子系统执行全局应用。定义9.2DDB是计算机网络环境中各场地上数据库的逻辑集合。定义9.3DDBMS是DDBS中的一组软件，它负责管理分布环境下逻辑集成数据的存取、一致性和完备性。229.3.3DDBS的特点和优缺点（一）DDBS的基本特点物理分布性：数据不是存储在一个场地上，而是存储在计算机网络的多个场地上。逻辑整体性：数据物理分布在各个场地，但逻辑上是一个整体，它们被所有用户（全局用户）共享，并由一个DDBMS统一管理。场地自治性：各场地上的数据由本地的DBMS管理，具有自治处理能力，完成本场地的应用（局部应用）。场地之间协作性：各场地虽然具有高度的自治性，但是又相互协作构成一个整体。239.3.3DDBS的特点和优缺点（二）DDBS的其他特点数据独立性逻辑独立性、物理独立性、分布透明性分布透明性：是指用户或应用程序不必关心数据的逻辑分片，不必关心数据物理位置分配的细节，也不必关心各个场地上数据库的数据模式是哪种类型，可以像集中式数据库一样来操作物理是分散的数据库。集中与自治相结合的控制机制适当增加数据冗余度事务管理的分布性249.3.3DDBS的特点和优缺点（三）DDBS的优点具有灵活的体系结构适应分布式的管理和控制机构经济性能优越系统的可靠性高、可用性好局部应用的响应速度快可扩展性好，易于集成现有的系统259.3.3DDBS的特点和优缺点（四）DDBS的缺点系统开销较大，主要花在通信部分。复杂的存取结构（如辅助索引、文件的链接技术），在集中式DBS中是有效存取数据的重要技术，但在分布式系统中不一定有效。数据的安全性和保密性较难处理。269.3.4DDBS的分类同构同质型DDBS：各个场地都采用同一类型的数据模型（譬如都是关系型），并且是同一型号的DBMS。同构异质型DDBS：各个场地采用同一类型的数据模型，但是DBMS的型号不同，譬如DB2、ORACLE、SYBASE、SQLServer等。异构型DDBS：各个场地的数据模型的型号不同，甚至类型也不同。随着计算机网络技术的发展，异种机联网问题已经得到较好的解决，此时依靠异构型DDBS就能存取全网中各种异构局部库中的数据。279.4分布式数据存储9.4.1数据分片（一）水平分片：按一定的条件把全局关系的所有元组划分成若干不相交的子集，每个子集为关系的一个片段。垂直分片：把一个全局关系的属性集分成若干子集，并在这些子集上作投影运算，每个投影称为垂直分片。导出分片：又称为导出水平分片，即水平分片的条件不是本关系属性的条件，而是其他关系属性的条件。混合分片：以上三种方法的混合。可以先水平分片再垂直分片，或先垂直分片再水平分片，或其他形式，但他们的结果是不相同的。289.4.1数据分片（二）定义各类分片时必须遵守的规则完备性条件：必须把全局关系的所有数据映射到片段中，决不允许有属于全局关系的数据却不属于它的任何一个片段。可重构条件：必须保证能够由同一个全局关系的各个片段来重建该全局关系。对于水平分片可用并操作重构全局关系；对于垂直分片可用连接操作重构全局关系。不相交条件：要求一个全局关系被分割后所得的各个数据片段互不重叠（对垂直分片的主键除外）。299.4.2数据分配集中式：所有数据片段都安排在同一个场地上。分割式：所有数据只有一份，它被分割成若干逻辑片段，每个逻辑片段被指派在一个特定的场地上。全复制式：数据在每个场地重复存储。也就是每个场地上都有一个完整的数据副本。混合式：这是一种介乎于分割式和全复制式之间的分配方式。309.5分布式数据库的体系结构319.5.1体系结构（一）全局外模式是全局应用的用户视图，是全局概念模式的逻辑子集全局概念模式全局概念模式中定义了DDB中全局数据的逻辑结构，可用传统的集中式数据库中采用的方法定义。分片模式就是定义片段以及定义全局关系与片段之间的映象。这种映象是一对多的，即每一个片段来自一个全局关系，而一个全局关系可分成若干片段。329.5.1体系结构（二）分配模式就是根据选定的数据分配策略，定义各片段的物理存放场地。局部概念模式一个场地上的局部概念模式是该场地上所有全局概念模式在该场地上的物理映象。局部内部式是DDB中关于物理数据库的描述，类似于集中式DB中的内模式，但其描述的内容不仅包含本场地的数据的存储描述，还包括全局数据在本场地的存储描述。339.5.1体系结构（三）图9.11全局关系R的逻辑片段与物理映象349.5.1体系结构（四）数据分片和数据分配概念的分离，形成了“数据分布独立型”概念。数据冗余的显式控制。数据在各个场地的分配情况在分配模式中一目了然，便于系统管理。局部DBMS的独立性。这个特征也称为“局部映射透明性”。此特征允许我们在不考虑局部DBMS专用数据模型的情况下，研究DDB管理的有关问题。359.5.2分布透明性（一）图9.12DDB中的映象和数据独立性369.5.2分布透明性（二）分片透明性位置透明性局部数据模型透明性379.5.3分布式数据库管理系统（一）DDBS的组成框架图9.13DDBS的组成框架389.5.3分布式数据库管理系统（二）接受用户请求，并判定把它送到哪里，或必须访问哪些计算机才能满足该要求。访问网络数据字典，了解如何请求和使用其中的信息。如果目标数据存储于系统的多个计算机上，就必须进行分布式处理。通信接口功能。在用户、局部DBMS和其他计算机的DBMS之间进行协调。在一个异构型分布式处理环境中，还需提供数据和进程移植的支持。这里的异构型是指各个场地的硬件、软件之间存在着差别。399.5.3分布式数据库管理系统（三）图9.13DDBMS的一般功能结构409.6分布式查询处理419.6.1查询例子分析429.6.2基于半连接的优化策略439.6.3基于半连接的优化策略（一）数据在网络中传输时，都是以整个关系（也可以是片段）传输，显然这是一种冗余的方法。在一个关系传输到另一场地后，并非每个数据都参与连接操作或都有用。因此，不参与连接的数据或无用的数据不必在网络中来回传输。这个思想引出了基于半连接的优化策略。这个方法的基本原理是采用半连接操作，在网络中只传输参与连接的数据。449.6.3基于半连接的优化策略（二） 假设关系R在场地1，关系S在场地2，在场地2需要获得RS的结果。如果在场地2直接计算R⋈S的值，那么需要先把关系R从场地1传输到场地2，其执行示意图见图9.16。显然，传输R的数据量较大。 可以采用半连接方法计算连接操作的值。方法如下(设R和S的公共属性为B)：R⋈S=（R⋈πB（S））⋈S=（R⋉S）⋈S。等式右边的式子称为“半连接程序”。459.6.3基于半连接的优化策略（三）

图9.16基于半连接的执行示意图图9.15连接的执行示意图469.6.4基于连接的优化方法（一）两个关系在同一场地嵌套循环法：顺序扫描外层关系R，对R的每一个元组扫描内层关系S，查找在连接属性上一致的元组，把匹配的元组组合起来使之成为连接结果的一部分。这种方法要求扫描一次关系R和扫描card（R）次关系S（可见S的元组越少越好），以查找匹配的元组。排序扫描法：先把两个关系按连接属性进行排序，然后按照连接属性值的顺序扫描这两个关系，使匹配的元组成为连接结果的一部分。这种方法对两个关系都只扫描了一次。但增加了排序代价。479.6.4基于连接的优化方法（二）两个关系在不同场地整体传输：若有连接操作R⋈S，R为外层关系，S为内层关系。如果传送的是内层关系S，则在目的地必须把它存入一个临时关系中（因为S将被多次扫描，但传输量少）。如果传送的是外层关系R，则内层关系S可直接使用依次到来的R元组，而无需保存R（但传输量大）。按需传输：只传输所需连接的元组，一次一个元组，无需临时存储器。因为每次提取都要求交换一次信息，所以传输代价较高，只有在高速局部网络中才是合理的。489.7分布式数据库中的并发控件和恢复技术499.7.1DDB中的问题数据项的多拷贝问题：由于DDB存在着冗余，有可能一个数据存储在多个场地，因此并发控制方法和恢复方法都应保证这些拷贝间的一致性。单个场地的故障：当系统中一个或多个场地发生故障时，DDBMS应当继续和其他正在运行的场地一起工作。当一个场地得到恢复时，它的局部数据库必须在它与系统重连接之前保持和其他场地同步。通讯网络的故障：系统必须有能力处理一个或多个连接场地的通讯故障。这个问题的极端情况是发生网络分割，即将网络分割成若干分区，每个分区内的场地可以相互通讯，而不同分区内的场地不能通讯。分布式提交：如果某些场地在提交过程中发生故障时，提交用于访问存储在多个场地数据库的事务时也会产生问题。分布式死锁：死锁可能会在若干场地中发生，处理死锁的技术必须要扩充以考虑这种情况。509.7.2基于数据项识别拷贝的分布式并发控制主场地技术有备份场地的主场地技术主拷贝技术有备份场地的主拷贝技术发生故障时选择一个新的协调者场地技术519.8.3基于投票方法的分布式并发控制在投票方法中，没有识别拷贝，而封锁请求被发送到所有包含该数据项拷贝的场地上。每个拷贝维护它自己的锁并且可以授予或拒绝封锁。如果一个请求封锁的事务被大多数的拷贝授予锁的话，它将持有该锁并告知所有的拷贝它已经获得锁。如果一个事务在给定的间隔时间段中没有获得授予它锁的大部分投票的话，它将取消它的请求并把取消决定告知所有的场地。投票方法被认为是真正的分布式并发控制方法，因为决策的职责驻留在所有涉及到的场地上。经实验表明，投票方法在场地间产生的信息通信量比识别拷贝方法产生的要高。如果算法要考虑投票过程中可能的场地故障时，它就会变得很复杂了。52小结（一）“分布计算”概念突破了集中式DBS的框架，数据分布使系统走上分布式DB的道路，功能分布使系统走上C／S道路。这是DBS的两个发展。C／S系统包括一个计算机网络，通常用一个局域网连结。几乎在所有情况下，客户机都是微机；服务器有时用小型机或大型机，但多数情况下也使用微机或高档微机。应用程序在客户机上处理，DBMS和OS的数据管理分放在服务器上。53小结（二）C／S结构经历了从两层、三层到多层的演变过程。总的趋势是使客户机越来越“瘦”，变成浏览器；而服务器的种类越来越多，容易实现系统的组装。C／S系统使应用与用户更加贴近，为用户提供较好的性能和更复杂的界面。分布式系统是在集中式系统的基础上发展而来的。DDB是数据库技术与网络技术结合的产物。随着计算机网络技术的飞速发展，DDBS日趋成为数据库领域的主流方向。54小结（三）DDB具有数据分布性和逻辑整体性的特点。DDBS能够支持涉及多个场地的全局应用。DDB的数