分布式数据库中文参考课件ddb

1、第十章 分布式数据库发展趋势概述DDBS环境站点：网络中每个站点是即运行应用程序又运行DDBMS的通用计算机网络：WAN与LAN数据模型：RDBMS新应用需求高性能工作站(专用工作站)并行计算机CAD/CAM, OIS, AI 数据服务器(1)70年代的数据库机, 现代的数据服务器数据管理功能从主机的CPU任务中剥离数据服务器的优势功能专一专用OS, DBMS与OS紧耦合, 提高DBMS的总体性能适于现实世界的分布环境充分利用先进的硬件体系结构缺点额外的通信开销 因此要求服务器提供较高层次的接口, 关系模型操作是面向集合的操作, 所以成为服务器模型的首选用户用户接口查询处理与数据库服务器接口与

2、应用服务器接口数据库功能用户DBDB应用服务器数据服务器网络通信信道数据服务器方案数据服务器(2)集中式服务器结构明确分工, 减少工作站与服务器之间的通信工作站对语言预处理(完整性检查, 安全控制)工作站能访问数据目录服务器管理和更新目录, 工作站只读目录优化DBMS和OS（软方法）, 或者使用多处理机（硬方法）解决服务器瓶颈问题接口数据库功能DBDB数据服务器逻辑通信网络集中式服务器结构工作站数据服务器(3)分布式服务器结构两种查询处理方式数据查询先提交到本地服务器，由其负责所有的分布查询处理每个应用服务器上也都可以有分布式查询处理器和数据目录操作器，直接访问远程数据服务器数据服务器(4)数

3、据服务器专门用于分布式和集中式数据库管理在传统机器结构上，在分布式OS之上执行DBMS和分布式DBMS基于特定计算机系统结构实现分布式数据库操作系统DBDB数据服务器1逻辑通信网络分布式服务器结构工作站分布式DBMS局部管理功能接口DBDB数据服务器n分布式DBMS局部管理功能接口并行数据服务器(1)冯.诺依曼型计算机结构的局限应用中存在内在的可并行处理特性关系操作本身的可并行性, JOIN中的多个子查询, 单个查询中的多步操作数据库管理性能受到I/O瓶颈的影响内存速度比硬盘速度快1000倍增加带宽提高磁盘存取的并行性使用并行可存取的多个小磁盘并行数据服务器(2)多处理机结构通过高速通信介质连

4、接多个可独立处理的单元通过分配，查询 操作和子操作到不同的处理单元, 以并行执行方式完成互连查询, 内部查询, 及各种内部操作并行数据服务器(3)类型完全共享资源结构对每个数据项的存取都要经过公共通信线路，引起通信瓶颈类似于集中式DBMS,差别是数据库操作可以并行处理完全不共享资源结构高功能计算机系统可以由多个较小的系统替代每个站点都要实现全局数据目录，分布数据定义和控制，分布查询处理和分布式事务管理站点不能运行应用程序处理机1处理机n高速互联总线磁盘1磁盘n内存1内存n完全共享资源系统结构处理机1处理机n高速互联总线磁盘1磁盘n内存1内存n完全不共享资源系统结构并行数据服务器(4)并行数据服

5、务器数据定位类似于分布式数据库中的数据片段定位分簇(Declustering) 数据的水平分片提高响应速度和内存查询并行度聚簇(Clustering) 聚集关系的片段综合查询或减少系统总体运行代价程序应在数据存储的站点上运行DDBS中DBA根据对片段的使用情况检测, 进行调整, 包括移动片段和重组并行数据服务器(5)并行数据服务与DDBS的不同应用目标不同并行中用户不专门使用某个站点, 所以不要求最大化本地性处理实现方式不同站点间高速网互连, 传输代价小, 可以调节站点间工作负载各站点地位不同不存在全局应用和局部应用各站点完全不独立, 处理时只能发挥协同作用, 无局部应用并行数据服务器(6)数

6、据定位方法全分簇 片段分布到系统中所有有磁盘的站点散列算法分片 查询时, 与选择属性精确匹配的子查询得以在一个站点上处理, 所有其它子查询在其他站点处理, 适于大范围多用户工作负载 复杂查询(多个连接)时, 聚簇方法较好可变分簇 依据“分簇度”对关系分片, 分簇度是关系数据分片的站点数量, 是关系大小和存取频率的函数 并行数据服务器(7)关联查询传统关联存取是由查询处理器在编译时利用数据目录完成并行系统中, 采用“全局索引”复制到每一个站点全局索引能确定关系在各站点分布的二级索引主聚簇 关于关系名次聚簇 关于关系中的某些属性基于散列法或B树实现并行数据服务器(8)例: 工程数据库 E(ENO,

7、 ENAME, DEPT, TITLE) S(TITLE, SAL) J(JNO, JNAME, BUDGET) G(ENO, JNO, RESP, DUR)全局索引(查询ENO=E5)第一级关于关系名索引映射到E关系的ENO属性索引第二级索引进一步映射值E5到站点j关于关系名的索引PEG关系E中关于ENO的索引站点1(E1至E2)站点j(E3至E6)站点n(E7至E8)全局索引例子并行数据服务器(9)本地索引(次簇索引) 映射一个关系到站点的一组磁盘块上类似于全局索引第一级关于关系名第二级关于属性索引(映射簇值E5到91磁盘块)实验结果短事务负载下, 分簇数量增加, 事务吞吐量增加多连接复杂

8、事务负载下, 太细分簇降低吞吐量关于关系名的索引PEG关系E中关于ENO的索引磁盘块24(E3至E4)磁盘块91(E5至E6)在站点j上的本地索引例子并行数据服务器(10)并行操作处理关系代数操作的并行化是通过建立必要的并行查询处理子模块实现Select 与 Join 的并行算法分簇数据分布Select 同分片的分布DB精确匹配谓词在单一站点执行复杂谓词, 在关系分簇所在的所有站点上执行范围查询, 只在存储相关数据的站点上执行并行数据服务器(11)Join操作高速网络环境的分布Join算法并行嵌套循环(PNL)算法并行关联(PAI)算法并行散列连接(PHJ)算法三个主要构造sendreceiv

9、edo-in-parallel For I from 1 to n do in parallel action A并行数据服务器(12)并行算法的代价Cost(Alg) = (Alg) + Cpro(Alg)PNL算法 (PNL) = m n msg(card(R)/m)Cpro(PNL) = n Cloc(card(R), card(S)/n)PAL算法 (PAL) = m n msg(card(R)/(m n)Cpro(PAL) = n Cloc(card(R)/m, card(S)/n)PHJ算法 (PHJ)= mpmsg(card(R)/(m p) + npmsg(card(S)/(n

10、 p)Cpro(PHJ) = n Cloc(card(R)/m, card(S)/n)并行数据服务器(13)举例R JOIN SR 分簇到 m 个 Site, 即有(R1, R2, , Rm)S 分簇到 n 个 Site, 即有(S1, S2, , Sn)JOIN 结果在 S 的n个站点上的片段 T1, T2, , Tn 算法 PNLinput: R1,R2,Rm: fragments of relation R; S1,S2,Sn: fragments of relation S; JP: join predicateoutput: T1,T2,Tn: result fragmentsbeg

11、in for i from 1 to m do in parallel send Ri to each node containing a fragment of S end _for for j from 1 to n do in parallel begin RiRi i=1,2,m receive Ri from R-nodes; R is fully replicated on each nodes of S TjJOIN(R, Sj, JP) JOIN is generic function end _forend. PNLR站点S站点站点1站点2站点3站点4R1R2S1 S2(PN

12、L)并行嵌套循环例子R JOIN S = Ui (R JOIN Si) i = 1, 2, , m算法 PAJinput: R1,R2,Rm: fragments of relation R; S1,S2,Sn: fragments of relation S; JP: join predicateoutput: T1,T2,Tn: result fragmentsbegin we assume that JP is R.A=S.B and relation S is fragmented according to function h(B) for i from 1 to m do in p

13、arallel send R associatively to each S-node begin Rijapply h(A) to Ri(j = 1,2,n) for j from 1 to n do Send Rijto the node stroing Sj end _for end _for for j from 1 to n do in parallel perform the join at each S-node begin RiRij i=1,2,m receive only the useful subset of R TjJOIN(R, Sj, JP) JOIN is ge

14、neric function end _forend. PAJR站点S站点站点1站点2站点3站点4R1R2S1 S2(PAJ) 并行关联连接算法例子input: R1,R2,Rm: fragments of relation R; S1,S2,Sn: fragments of relation S; JP: join predicateoutput: T1,T2,Tn: result fragmentsbegin we assume that JP is R.A=S.B and h is a hash function that returns an element of 1,p for i

15、from 1 to m do in parallel begin Rijapply h(A) to Ri(j = 1,2,n) for j from 1 to n do Send Rijto the node j end _for end _for for j from 1 to n do in parallel hash S on the join attribute begin Sijapply h(B) to Si(j = 1,2,n) for j from 1 to n do Send Sijto the node j end _for end _for for j from 1 to

16、 n do in parallel perform the join at each S-node begin RJiRij (i=1,2,p) receive from R-nodes SJiSij (i=1,2,p) receive from S-nodes TjJOIN(Ri, Sj, JP) end _forend. PHJ算法PHJR1站点R2站点S1站点S2站点站点1站点2(PHJ)并行散列连接算法例子input: prof(R), prof(s): relation profiles; JP:join predicateoutput: JA: join algorithmbegi

17、n if JP is equijoin then if on relation is declustered according to join attribtute then JAPAJ else if Cost(PNL) 150 于是Engine 分为Engine1 和 Engine2两个段分布式面向对象数据库(4)复杂属性 使用对象间的联系(如Owner-Member)信息分段简单Method 当简单属性时, 对象分段按简单属性方法分, Method在编译时确定, 若对象被该Method使用则Method与该对象分在同一段, 以获取极大化本地相关访问复杂Method 要使用子类联系, 聚集联系, Method调用联系等来处理, 产生多个分段, 然后再使用基于亲和力的方法来合并某些段 分布式面向对象数据库(5)垂直分段比水平分段更复杂, 要考虑元类和分段类的