第22章并行与分布式数据库

第22章并行与分布式数据库22.1简介集中式数据库管理系统——数据在独立的站点进行管理，顺序地进行事物处理。并行数据库系统——通过并行实现各种数据操作，如数据载入、索引建立、数据查询等，可以提高系统的性能。分布式数据库系统——数据分布存储于若干场地，并且每个场地由独立于其它场地的DBMS进行数据管理。并行与分布技术特点：增强的可用性：当存储某个关系的场地系统崩溃时，可继续使用存储在别的场地的复本。数据的分布访问：企业数据可以分布于若干城市，分析时可能需要访问不同场地的数据，但通常在访问模式中得到数据存储的局部性（如银行经理通常是查询本地支行的顾客账户），这种局部性可用来分布数据。分布数据的分析：企业越来越需要分析所有可用的数据，即使这些数据存储在不同场地和不同的数据库系统中。22.2并行数据库系统的可用结构（一）实现并行DBMS的三种硬件结构：（1）共享内存系统（2）共享磁盘系统（3）无共享资源系统（一）实现并行DBMS的三种硬件结构：连接网络全局共享内存DDD（1）共享内存系统：多个cpu通过连接网络进行通信，并能访问公共的主存。

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

（1）并行处理多个操作----查询的执行计划可用关系代树表达式树表示，其中操作都可并行执行（2）并行处理单个操作----查询计划中的单个操作也能够并行处理22.3并行查询处理流水线并行技术——并行处理多个操作。当一个操作需要另一个操作的输出数据时，即在产生部分操作输出数据的同时立即进行随后的操作。阻塞操作——如果一个操作必须在得到所有输入数据后才能产生输出数据，该操作称为阻塞操作。阻塞操作不能用流水线技术。基于数据划分的并行处理——对查询计划的单个操作的并行处理。首先对并行操作所需要的数据进行划分，然后并行地处理每个分片，最后再将结果合并。无共享资源的并行数据库的查询处理都使用基于数据划分的并行查询处理方法。22.3.1数据划分将大数据集水平划分到多个磁盘上，可以通过并行读写有效地利用多磁盘的I/O带宽。将关系水平划分方法：（1）轮转划分法——如果系统有n个cpu，将第i条记录划分到第imodn处理器的方法称为轮转划分方法。（2）哈希划分法——使用特定的哈希函数，作用于选定的属性，将记录划分到不同的处理机。（3）区域划分法——首先对记录进行排序，然后按照排序码将其划分成n个区域，使每个区域中近似含有相同数目的记录，处于第i个区域的记录分布于处理机i。22.3.1数据划分优势劣势：（1）轮转法可有效应用于需要访问整个关系的查询处理，当需要访问部分记录时，哈希法和区域法更优。（2）区域法可能会导致数据偏斜，也就是不同分片含有的记录数目差别很大。数据偏斜会造成存有大片数据分片的处理机的性能瓶颈问题。（3）哈希法优点是：即使数据随时间增加或减少，也能保持均匀分布。22.3.2并行化顺序数据操作处理程序并行DBMS软件结构能够将现有的关系操作顺序处理程序快速并行化。该方法的基本思想——使用并行数据流技术数据流（来自不同的磁盘或者其它操作的输出）在需要时进行归并以产生关系操作的输入，并且在必要时进行分裂以便于随后的并行处理。一个并行查询处理计划是关系操作以及归并和分裂操作共同组成的数据流网络。

Split- Merge 实现并行查询技术22.4数据操作的并行化假设：（1）无共享资源的并行结构（2）关系都水平划分到若干磁盘上分布式DBMS的数据存储水平划分——每个分片是原始关系所有数据行的子集合垂直划分——每个分片是原始关系所有数据列的子集合Idnameaddressagephone123…22.4.1扫描A．读一个关系R的整个内容B．仅读出R中满足谓词的元组定位R中基本元组的方法：a.表扫描

b.索引扫描扫描并行化——如果关系被划分到若干磁盘上，可以首先按页并行读入，然后归并得到所需的记录。2.4.2排序简单方法：每个cpu先对本地磁盘上的记录进行排序，然后归并有序记录集合，并行程度受归并阶段的影响。2.4.2排序更好方法：a.用区域划分法先将关系的所有记录重新分布再进行排序。例：employee按属性salary排序，salary的取值范围从10~210，处理机数目2010~20的所有记录分布于处理机121~30……………2

……

……200~210…………20b.每个cpu使用排序算法对分配给它的记录排序。每个处理机得到分配给它的所有记录的有序序列。

c.通过按照区域划分的对应次序访问处理机得到完整的有序关系。难点：如何进行区域划分来使得每个处理机分布的记录数目近似相等。否则，对具有大量记录的处理机排序时将产生性能瓶颈，从而限制并行排序的可扩展性。2.4.3连接假设：对关系A和B进行划分时，连接属性为age，关系初始分布在若干磁盘上，但不是基于连接属性分布的。方法：对关系A和B重新划分：把连接属性age的取值分成k个区域假设10个处理机，age取值范围0~100

记录按照相应的age值进行分布

0<=age<10处理机1

10<=age<20处理机2

……

……90<=age<100处理机10缺点：产生由对数据偏斜不同分片的记录数目差别很大并行连接操作的数据流网络合并

Ai分离分离分离合并分离合并合并扫描扫描扫描扫描A’B’AB

A”B”A连接连接

Ai∞BiAj∞BjAiAiAiAjAjAjAjBiBiBiBiBjBjBjBjB存储关系A与B的处理机处理连接的处理机并行连接操作的数据流网络（1）扫描A划分AAi 0<=age<50Aj 50<=age<100

扫描B划分BBi0<=age<50Bj50<=age<100

（2）将第i个分片的记录发给处理机i（3）归并——归并所有来自A（B）的记录（4）每个处理机将分配给它的A和B的记录进行连接（5）归并22.6分布式数据库简介分布式数据库——数据分布存储于若干个场地上，每个场地都由独立运行的DBMS进行数据管理。分布式数据库系统的特点：

(1)分布数据的独立性：用户无需提供关系或关系副本的存储地点，就可以对数据进行查询。

(2)分布式事物的原子性：用户可以提交事物访问或者修改若干个场地上的数据，涉及多个场地的事物具有原子性。分布式数据库系统的类型同步分布式数据库系统——数据分布在各个场地，但各场地上运行相同的DBMS。异步分布式数据库系统（多数据库系统）——数据分布在各个场地，不同场地运行不同的DBMS。22.7分布式DBMS体系结构（1）客户/服务器（2）协同服务器（3）中间件22.71客户/服务器系统客户/服务器系统——每个都能够处理本地事务，拥有一个或多个客户进程，一个或多个服务器进程，并且客户进程可以向任一服务器进程提交查询。客户进程负责和用户进行交互，服务器进程负责管理数据并进行事物处理。客户进程可运行在个人计算机上，将查询提交给大型主机上的服务器进程执行。缺点：不能处理涉及多个服务器的单个查询，因此客户进程必须将查询分解成合适的子查询，分别在不同场地执行，然后将各个子查询的结果组合起来得到最终查询结果。客户进程将变得非常复杂。22.72协同服务器系统中的数据库服务器，每个都能够处理本地事务，并能协同执行涉及多个服务器的事务。当服务器收到的查询需要访问其它服务器的数据时，将产生合适的子查询，提交给其它服务器，得到结果组合产生原始查询的最终结果。22.7.3中间件系统中间件系统允许提交涉及多个服务器的单个查询，并且数据库服务器不需要都具有多场地查询执行能力。该方法对于集成很难扩展的若干遗留系统非常有效。基本上，只需要一个服务器有能力处理涉及多个服务器的查询或者事物就可以了，其余的服务器只需要处理本地的查询和事物。中间件——将协同执行涉及多服务器的查询或事物的特殊服务器看成一个软件层。中间件本身并不维护数据，但能够对来自其它服务器的数据进行连接和其他关系操作。22.8分布式DBMS的数据存储分布式DBMS，关系可以存储于若干场地。将经常使用的数据存储于本地，并且将使用频率较高的关系数据复制存储于每个场地。22.8.1划分划分——将关系分离成若干个小关系或者分片，每个分片存储于不同场地。（1）水平划分——每个分片是原始关系所有数据行的子集合。（2）垂直划分——每个分片是原始关系所有数据列的子集合。22.8.1划分Idnamecityagesal001JonesMadra233000002SmithChicago254500003MaryChicago195000004JakcBombay358000005MadaBombay469800垂直划分——可用π得到.πid，name水平划分——可以用σ得到例：来自同一个城市的雇员位于一个分片将Chicago数据存储于场地Chicago。相当多的查询是本地查询22.8.2复制复制——同时存储关系或者关系分片的若干个版本。一个完整的关系可以在一个或多个场地进行复制与存储。同样，关系分片也可以复制存储于若干场地。例：关系划分成R1，R2，R3三个分片，可以只存储R1的一个副本，复制存储R2的多个副本，在所有场地复制存储R3的副本。复制的作用：增加数据的可用性：当存储数据的某个场地的系统发生故障时，可以在其他场地找到数据。快速的查询处理：使用本地副本代替访问远程数据，减少了访问远程场地的数据将导致额外的传输代价，能加快查询的执行速度。22.9分布式目录管理跟踪分布到多个场地的数据，保存关系进行划分以及进行复制的信息，即关系分片如何分布到若干个场地以及分片副本存储在哪里。22.9.1命名对象关系进行了划分和复制后，要对之命名以唯一地识别每个分片的每个副本。<load-name,birth-site>本地名（load-name），关系所在场地生成的名字。同一场地两个对象不能同名。产生场地名（birth-site），用于标识关系产生的场地，以及对关系的所有分片和副本的信息进行维护的场地。22.9.2目录结构场地目录：描述该场地存储的所有分片和副本本场地产生的关系的副本的分布情况22.10分布式查询处理Sailors（sid:integer,sname:string,rating:integer,age:real）Reserves(sid:integer,bid:integer,day:date,rname:string)SELECTAVG(S.age)FROMSailorsSWHERES.rating>3ANDS.rating<722.10.1分布式DBMS中无连接的查询Sailors水平划分：rating<5存在shanhai>=5存在Tokyo——必须在两个场地分别计算SUM（age），COUNIT（age）（记录数）再利用上述信息计算AVG（age）——如果WHERE子句只有一个条件S.rating>6,只需在一个场地Tokyo查询处理Sailors垂直划分：场地shanghai存储sid和rating场地Tokyo存储sanme和age

有损分解两个字段无公共字段两个分片加额外标识字段（id）存储于两个场地，才能合并两个分片得到原关系。22.10.1分布式DBMS中无连接的查询Sailors同时存储于场地shanghai和Tokyo选择哪个场地进行查询？取决于：将查询结果传输到查询提交场地的代价在场地shanghai或Tokyo执行查询的代价22.10.2分布式DBMS中的连接操作LONDONPARISSailorsReserves每条记录50字节每页存80条记录总共有500页每条记录40字节每页有100条记录总共有1000页记录D——从磁盘读取（写）页数据所需的时间

S——传输一页数据（从一个场地到另一个场地）所需的时间不同执行策略：（1）需要时取得数据（2）传输到一个场地（3）半连接和布鲁连接不同执行策略的执行代价：（1）需要时取得数据在场地London做基于页的嵌套循环连接，Sailors作为外关系，则对于Sailors的每页数据，都需要从场地Paris得到Reserves的所有数据，并进行连接。代价：500D+500*1000（D+S）如果查询不是在场地London提交的，查询的处理代价还需要加上将查询结果传输到查询提交场地的传输代价，这个取决于查询结果的大小。如果查询场地不再London也不在Paris，传输查询结果的代价将大于将关系Sailors和Reserves都传到查询场地的代价。所以应将两个关系传输到查询场地，再执行连接操作。可以在场地London使用索引嵌套循环连接方法，对于关系Sailors的每条记录，只访问关系Reserves中合适的记录。对关系Reserves建立基于属性sid哈希索引。都需要从远程场地取得数据，传输代价所占比重大。不同执行策略的执行代价：（2）传输到一个场地可将Sailors从London传到Paris，然后在Paris执行连接。500（2D+S）+4500D可将Reservs从Paris传到London，连接

1000（2D+S）+4500D将两个关系都传到查询提交的场地，在那里连接不同执行策略的执行代价（3）半连接和布鲁连接例：将Reserves传到London并连接实际上Reserves的部分记录并不能和Sailors的记录进行连接，事先确定哪些记录和Sailors不能进行连接，可避免传输这些记录，从而可减少传输Reserves记录的数目。半连接：（1）在场地London对关系Sailors进行投影得到连接字段sid，将结果传到场地Paris（2）在场地Paris，将London传来的投影结果和关系Peserves进行自然连接。连接的结果就称为Reserves的一个基于关系Sailors的约减。只有约减的Reserves记录能和Sailors的记录进行连接。所以约减后的Reserves传输到场地London（3）在场地London，对约减后的Reserves和Sailors进行连接代价：200S+6500D半连接的传输代价小，但总代价可能比传输整个关系要大布鲁连接（1）传送位向量，不是Sailors的投影。位向量长度为k，关系Sailors的每条记录（使用属性sid）通过哈希函数映射到区域0~k-1，如果记录的哈希值为i，则向量的第i位设为1，否则为0。（2）对关系Reserves进行约减时，使用相同的哈希函数将Reserves的每个记录（使用属性sid）映射到区域0~k-1，对于哈希值为i的记录，如果向量的第i位值为0，表示没有哈希值为i的Sailors记录，即没有Sailors可进行连接，忽略该Reserves中的记录。SailorsReservessid：sid：h（sid）=1，2……k-101234k-101100……1*位向量传输代价低，更有效。22.11分布式数据的更新同步复制——在更新事物提交时，同步更新数据的所有副本异步复制——关系的副本只需要定期更新;

因此一个事物读取每个关系的不同副本结果可能不同异步复制危害了分布数据的独立性，但比同步复制能更有效地实现。22.11.1同步复制1）投票技术——事物在修改每个对象时写该对象的大多数副本，并且在读时要读足够数量的副本来保证其中之一为当前副本例：总共有10个副本，更新事物写了其中7个副本，那么至少应该读4个副本。*很多应用中，读数据比更新数据频繁，所以应提高了读的性能，所以此技术没吸引力2）读任意写全部技术——事物可以读对象的任一个副本，但写时需要所有副本。和投票比较：读的速度快，写的速度慢读操作比写频繁时，此技术有吸引力。通常情况使用此技术来实现同步复制。22.11.2异步复制