并行与分布式数据库

1、第22章 并行与分布式数据库22.1简介n集中式数据库管理系统数据在独立的站点进行管理，顺序地进行事物处理。n并行数据库系统通过并行实现各种数据操作，如数据载入、索引建立、数据查询等，可以提高系统的性能。n分布式数据库系统数据分布存储于若干场地，并且每个场地由独立于其它场地的DBMS进行数据管理。并行与分布技术特点：n增强的可用性：当存储某个关系的场地系统崩溃时，可继续使用存储在别的场地的复本。n数据的分布访问：企业数据可以分布于若干城市，分析时可能需要访问不同场地的数据，但通常在访问模式中得到数据存储的局部性（如银行经理通常是查询本地支行的顾客账户），这种局部性可用来分布数据。n分布数据的分

2、析：企业越来越需要分析所有可用的数据，即使这些数据存储在不同场地和不同的数据库系统中。22.2 并行数据库系统的可用结构（一）实现并行DBMS的三种硬件结构：（1）共享内存系统（2）共享磁盘系统（3）无共享资源系统（一）实现并行DBMS的三种硬件结构：连接网络全局共享内存DDD（1）共享内存系统：多个cpu通过连接网络进行通信，并能访问公共的主存。 MMM连接网络DDD（2）共享磁盘系统：每个cpu拥有自己的私有内存，并通过连接网络直接访问所有磁盘。冲突问题随着cpu数目的增加，由于内存访问的冲突增加、网络通信带宽有限，cpu性能下降。（一）实现并行DBMS的三种硬件结构：连接网络MMMDDD

3、（3）无共享资源系统：每个cpu拥有自己的内存和磁盘空间，并无公共区域，cpu之间所有通信通过连接网络来完成。大型并行数据库系统的最优结构(二)加速比和可扩展性加速比曲线表明对于固定的数据库大小，通过增加cpu数目，每秒能处理更多的事物。 无共享资源的并行结构具有近似线性加速比（随cpu数目增加，各种操作所需时间减少。）(二)加速比和可扩展性无共享资源的并行结构无共享资源的并行结构具有线性可扩展性（cpu和磁盘数目随着数据量的增加而按比例增加时，系统性能保持不变）可扩展曲线表明，通过增加系统资源，系统能处理更大规模的问题。数据库大小与可扩展性每秒处理事务数与可扩展性22.3 并行查询处理l多个

4、查询并行执行l单个查询并行执行 （1）并行处理多个操作-查询的执行计划可用关系代树表达式树表示，其中操作都可并行执行 （2）并行处理单个操作-查询计划中的单个操作饿能够并行处理22.3 并行查询处理n流水线并行技术并行处理多个操作。当一个操作需要另一个操作的输出数据时，即在产生部分操作输出数据的同时立即进行随后的操作。n阻塞操作如果一个操作必须在得到所有输入数据后才能产生输出数据，该操作称为阻塞操作。阻塞操作不能用流水线技术。n基于数据划分的并行处理对查询计划的单个操作的并行处理。首先对并行操作所需要的数据进行划分，然后并行地处理每个分片，最后再将结果合并。n无共享资源的并行数据库的查询处理都

5、使用基于数据划分的并行查询处理方法。22.3.1数据划分n将大数据集水平划分到多个磁盘上，可以通过并行读写有效地利用多磁盘的I/O带宽。n将关系水平划分方法：（1）轮转划分法如果系统有n个cpu，将第i条记录划分到第i mod n 处理器的方法称为轮转划分方法。（2）哈希划分法使用特定的哈希函数，作用于选定的属性，将记录划分到不同的处理机。（3）区域划分法首先对记录进行排序，然后按照排序码将其划分成n个区域，使每个区域中近似含有相同数目的记录，处于第i个区域的记录分布于处理机i。22.3.1数据划分n优势劣势：（1）轮转法可有效应用于需要访问整个关系的查询处理，当需要访问部分记录时，哈希法和区

6、域法更优。（2）区域法可能会导致数据偏斜，也就是不同分片含有的记录数目差别很大。数据偏斜会造成存有大片数据分片的处理机的性能瓶颈问题。（3）哈希法优点是：即使数据随时间增加或减少，也能保持均匀分布。22.3.2并行化顺序数据操作处理程序n并行DBMS软件结构能够将现有的关系操作顺序处理程序快速并行化。n该方法的基本思想使用并行数据流技术n 数据流（来自不同的磁盘或者其它操作的输出）在需及时进行归并以产生关系操作的输入，并且在必要时进行分裂以便于随后的并行处理。一个并行查询处理计划是关系操作以及归并和分裂操作共同组成的数据流网络。 Split- Merge 实现并行查询技术22.4数据操作的并行

7、化n假设：（1）无共享资源的并行结构（2）关系都水平划分到若干磁盘上分布式DBMS的数据存储n水平划分每个分片是原始关系所有数据行的子集合n垂直划分每个分片是原始关系所有数据列的子集合Idnameaddressagephone12322.4.1 扫描A读一个关系R的整个内容B仅读出R中满足谓词的元组n定位R中基本元组的方法：a.表扫描 b.索引扫描n扫描并行化如果关系被划分到若干磁盘上，可以首先按页并行读入，然后归并得到所需的记录。2.4.2 排序n简单方法：每个cpu先对本地磁盘上的记录进行排序，然后归并有序记录集合，并行程度受归并阶段的影响。2.4.2 排序n更好方法：a.用区域划分法先将

8、关系的所有记录重新分布再进行排序。例：employee按属性salary排序 ，salary的取值范围从10210，处理机数目20 1020的所有记录分布于处理机1 2130 2 20021020 b.每个cpu使用排序算法对分配给它的记录排序。每个处理机得到分配给它的所有记录的有序序列。 c.通过按照区域划分的对应次序访问处理机得到完整的有序关系。n难点：如何进行区域划分来使得每个处理机分布的记录数目近似相等。否则，对具有大量记录的处理机排序时将产生性能瓶颈，从而限制并行排序的可扩展性。2.4.3连接n假设：对关系A和B进行划分时，连接属性为age，关系初始分布在若干磁盘上，但不是基于连接属

9、性分布的。n方法：对关系A和B重新划分：把连接属性age的取值分成k个区域 假设10个处理机，age取值范围0100 记录按照相应的age值进行分布 0=age1 处理机110=age20 处理机2 90=age100 处理机10l缺点：产生由对数据偏斜不同分片的记录数目差别很大 并行连接操作的数据流网络合并 分离分离分离合并分离合并合并扫描扫描扫描扫描AB A”B”连接连接 AiBiAjBj存储关系A与B的处理机 处理连接的处理机 并行连接操作的数据流网络（1）扫描A 划分A Ai 0=age50 Aj 50=age100 扫描B 划分B Bi 0=age50 Bj 50=age100 （2

10、）将第i个分片的记录发给处理机i（3）归并归并所有来自A（B）的记录（4）每个处理机将分配给它的A和B的记录进行连接（5）归并22.6 分布式数据库简介n分布式数据库数据分布存储于若干个场地上，每个场地都由独立运行的DBMS进行数据管理。n分布式数据库系统的特点： (1)分布数据的独立性：用户无需提供关系或关系副本的存储地点，就可以对数据进行查询。 (2)分布式事物的原子性：用户可以提交事物访问或者修改若干个场地上的数据，涉及多个场地的事物具有原子性。分布式数据库系统的类型 n同步分布式数据库系统同步分布式数据库系统数据分布在各个场地，但各场地上运行相同的DBMS。n异步分布式数据库系统异步分

11、布式数据库系统（多数据库系统）数据分布在各个场地，不同场地运行不同的DBMS。22.7分布式DBMS体系结构（1）客户/服务器（2）协同服务器（3）中间件22.7 1 客户/服务器系统n客户/服务器系统拥有一个或多个客户进程，一个或多个服务器进程，并且客户进程可以向任一服务器进程提交查询。客户进程负责和用户进行交互，服务器进程负责管理数据并进行事物处理。客户进程可运行在个人计算机上，将查询提交给大型主机上的服务器进程执行。n缺点：不能处理涉及多个服务器的单个查询，因此客户进程必须将查询分解成合适的子查询，分别在不同场地执行，然后将各个子查询的结果组合起来得到最终查询结果。客户进程将变得非常复杂

12、。22.7 2 协同服务器n系统中的数据库服务器，每个都能够处理本地事务，并能协同执行涉及多个服务器的事务。n当服务器收到的查询需要访问其它服务器的数据时，将产生合适的子查询，提交给其它服务器，得到结果组合产生原始查询的最终结果。22.7.3 中间件系统n中间件系统允许提交涉及多个服务器的单个查询，并且数据库服务器不需要都具有多场地查询执行能力。该方法对于集成很难扩展的若干遗留系统非常有效。n基本上，只需要一个服务器有能力处理涉及多个服务器的查询或者事物就可以了，其余的服务器只需要处理本地的查询和事物。n中间件将协同执行涉及多服务器的查询或事物的特殊服务器看成一个软件层。中间件本身并不维护数据

13、，但能够对来自其它服务器的数据进行连接和其他关系操作。22.8分布式DBMS的数据存储n分布式DBMS，关系可以存储于若干场地。将经常使用的数据存储于本地，并且将使用频率较高的关系数据复制存储于每个场地。22.8.1 划分n划分将关系分离成若干个小关系或者分片，每个分片存储于不同场地。（1）水平划分每个分片是原始关系所有数据行的子集合。（2）垂直划分每个分片是原始关系所有数据列的子集合。22.8.1 划分Idnamecityagesal001JonesMadra233000002SmithChicago254500003MaryChicago195000004JakcBombay3580000

14、05MadaBombay469800垂直划分可用得到. id，name水平划分可以用得到 例：来自同一个城市的雇员位于一个分片将Chicago数据存储于场地Chicago 。相当多的查询是本地查询22.8.2 复制 n复制同时存储关系或者关系分片的若干个版本。一个完整的关系可以在一个或多个场地进行复制与存储。同样，关系分片也可以复制存储于若干场地。 例：关系划分成R1，R2，R3三个分片，可以只存储R1的一个副本，复制存储R2的多个副本，在所有场地复制存储R3的副本。n复制的作用：n增加数据的可用性：当存储数据的某个场地的系统发生故障时，可以在其他场地找到数据。快速的查询处理：使用本地副本代替

15、访问远程数据，减少了访问远程场地的数据将导致额外的传输代价，能加快查询的执行速度。22.9分布式目录管理n跟踪分布到多个场地的数据，保存关系进行划分以及进行复制的信息，即关系分片如何分布到若干个场地以及分片副本存储在哪里。 22.9.1 命名对象n关系进行了划分和复制后，要对之命名以唯一地识别每个分片的每个副本。nn本地名（load-name），关系所在场地生成的名字。同一场地两个对象不能同名。产生场地名（birth-site），用于标识关系产生的场地，以及对关系的所有分片和副本的信息进行维护的场地。22.9.2目录结构n场地目录：n描述该场地存储的所有分片和副本本场地产生的关系的副本的分布情

16、况22.10 分布式查询处理nSailors（sid:integer,sname:string,rating:integer,age:real）nReserves(sid:integer,bid:integer,day:date,rname:string)SELECT AVG(S.age)FROM Sailors SWHERE S.rating3 AND S.rating722.10.1分布式DBMS中无连接的查询nSailors 水平划分：水平划分：rating=5存在Tokyo必须在两个场地分别计算SUM（age），COUNIT（age）（记录数） 再利用上述信息计算 AVG（age）如果

17、WHERE子句只有一个条件S.rating6,只需在一个场地Tokyo查询处理n Sailors垂直划分：垂直划分： 场地shanghai存储sid和rating 场地Tokyo 存储sanme和age 有损分解两个字段无公共字段两个分片加额外标识字段（id）存储于两个场地，才能合并两个分片得到原关系。22.10.1分布式DBMS中无连接的查询nSailors同时存储于场地shanghai和Tokyo选择哪个场地进行查询？n取决于：n将查询结果传输到查询提交场地的代价在场地shanghai或Tokyo执行查询的代价22.10.2分布式DBMS中的连接操作LONDON PARIS Sailors

18、Reserves每条记录50字节每页存80条记录总共有500页每条记录40字节每页有100条记录总共有1000页记录 D从磁盘读取（写）页数据所需的时间 S传输一页数据（从一个场地到另一个场地）所需的时间 不同执行策略：不同执行策略：（1）需要时取得数据（2）传输到一个场地（3）半连接和布鲁连接不同执行策略的执行代价：（1）需要时取得数据n在场地London做基于页的嵌套循环连接，Sailors作为外关系，则对于Sailors的每页数据，都需要从场地Paris得到Reserves的所有数据，并进行连接。 代价：500D+500*1000（D+S）n如果查询不是在场地London提交的，查询的处

19、理代价还需要加上将查询结果传输到查询提交场地的传输代价，这个取决于查询结果的大小。n如果查询场地不再London也不在Paris，传输查询结果的代价将大于将关系Sailors和Reserves都传到查询场地的代价。 所以应将两个关系传输到查询场地，再执行连接操作。n可以在场地London使用索引嵌套循环连接方法，对于关系Sailors的每条记录，只访问关系Reserves中合适的记录。 对关系Reserves建立基于属性sid哈希索引。n都需要从远程场地取得数据，传输代价所占比重大。不同执行策略的执行代价：（2）传输到一个场地n可将Sailors从London传到Paris，然后在Paris执

20、行连接。500（2D+S）+4500Dn可将Reservs从Paris传到London，连接 1000（2D+S）+4500Dn将两个关系都传到查询提交的场地，在那里连接不同执行策略的执行代价（3）半连接和布鲁连接n例：将Reserves传到London并连接n实际上Reserves的部分记录并不能和Sailors的记录进行连接，事先确定哪些记录和Sailors不能进行连接，可避免传输这些记录，从而可减少传输Reserves记录的数目。半连接：（1）在场地London对关系Sailors进行投影得到连接字段sid，将结果传到场地Paris（2）在场地Paris，将London传来的投影结果和关

21、系Peserves进行自然连接。 连接的结果就称为Reserves的一个基于关系Sailors的约减。 只有约减的Reserves记录能和Sailors的记录进行连接。 所以约减后的Reserves传输到场地London（3）在场地London，对约减后的Reserves和Sailors进行连接 代价：200S+6500D l半连接的传输代价小，但总代价可能比传输整个关系要大布鲁连接（1）传送位向量，不是Sailors的投影。 位向量长度为k，关系Sailors的每条记录（使用属性sid）通过哈希函数映射到区域0k-1，如果记录的哈希值为i，则向量的第i位设为1，否则为0。（2）对关系Rese

22、rves进行约减时，使用相同的哈希函数将Reserves的每个记录（使用属性sid）映射到区域0k-1，对于哈希值为i的记录，如果向量的第i位值为0，表示没有哈希值为i的Sailors记录，即没有Sailors可进行连接，忽略该Reserves中的记录。Sailors Reservessid： sid： h（sid）=1，2k-1 0 1 2 3 4 k-1 0 1 1 0 01*位向量传输代价低，更有效。22.11分布式数据的更新n同步复制在更新事物提交时，同步更新数据的所有副本n异步复制关系的副本只需要定期更新; 因此一个事物读取每个关系的不同副本结果可能不同 异步复制危害了分布数据的独立性，但比同步复制能更有效地实现。22.11.1同步复制1）投票技术事物在修改每个对象时写该对象的大多数副本，并且在读时要读足够数量的副本来保证其中之一为当前副本 例：总共有10个副本，更新事物写了其中7个副本，那么至少应该读4个副本。 *很多应用中，读数据比更新数据频繁，所以应提高了读的性能，所以此技术没吸引力 2）读任意写全部技术事物可以读对象的任一个副本，但写时需要