第5章并行数据库.ppt

练习 对于流水线并行，即使在有许多处理器可用时，在一个单独的处理器上用一个流水线来执行多个操作通常比较好。 解释原因 如果所使用的机器采用共享内存体系结构，上述说法正确吗？为什么？ 对于独立并行，上述说法正确吗？（即使在不将操作组织到流水线中，而且有许多处理器可用的情况下，将几个操作放在同一个处理器中执行是否仍然是个好主意呢？） 思考 对关系采用哈希划分和范围划分时，哪些因素会导致偏斜？可以采取什么措施？ 对下面的每一种运算，给出一种好的并行化方法 差运算 Count Count distinct * * 第7章 并行数据库 并行数据库系统概念 硬件体系结构 数据分片技术 并行性种类 并行连接 并行排序 7.1 并行数据库系统概念 为什么并行存取数据？ 7.1 并行数据库系统概念 为什么并行存取数据？ 数据密集型(data-intensive)应用，如决策支持系统、在线处理分析(OLAP)、数据仓库(data warehouse)、知识和数据发现(KDD)等 并行数据库系统设计的研究问题：并行I/O、并行查询优化、并行性数据库操作等 7.1 并行数据库系统概念 并行数据库系统的评价参数： speedup：对于某个固定的计算任务，1倍计算资源系统所完成的时间与n倍计算资源所完成时间之比；理想的speedup曲线为线性加速 scaleup：1倍计算任务在1倍计算资源系统所完成的时间与n倍计算任务在n倍计算资源系统所完成时间之比，理想的scaleup曲线为y=1 7.1 并行数据库系统概念 影响并行数据库系统性能的三个因素 启动代价(startup)：启动一个并行操作的代价 干扰(interference)：共享资源之间的相互干扰 倾斜(skew)：一个操作或一个查询可以被分解为若干个可并行执行的子操作或子查询，执行时间最长的子操作或子查询的响应时间决定该并行操作的响应时间 7.1 并行数据库系统概念 实现并行的2种基本技术 管道 一个操作的输出是另一个操作的输入 分片 多台机器在不同的数据分片上做相同的事情 7.2 硬件体系结构 共享内存(SM, SE) 在SM体系结构中，处理机和磁盘可以通过一个总线或互联网络来访问一个公共的内存，即所有资源均是共享的 处理机间通讯可通过共享内存来进行,比通过通讯机制进行通讯要快得多 32或64节点以内并行算法speedup很好 超过32或64节点以后scaleup很坏，因为所有资源均是共享的，总线或互联网络就变成了一个瓶颈。超过这个点后增加处理机节点个数没有任何用处，因为处理机不得不花更多的时间来等待总线并访问内存和磁盘 P P P P P M 7.2 硬件体系结构 共享磁盘(SD) 所有处理机可以直接通过总线或互联网络访问磁盘,但每个处理机有自己的私有内存 由于每个处理机有自己的内存，存储器的总线不会成为瓶颈 提供一定的容错能力，若某处理机或它的内存出问题了，其它处理机可以接管它的任务，因为数据库驻留在所有处理机可以直接访问的磁盘上。磁盘子系统本身的容错问题可以通过使用RAID来解决 尽管不存在内存共享，共享磁盘仍然成为SD系统可扩展性问题的障碍，共享的磁盘子系统的互联成为性能可扩展的瓶颈。SD不能解决可扩展性问题，仅仅缓解了SM系统的可扩展性问题 P M P M P M P M P M 7.2 硬件体系结构 无共享资源体系结构(SN) 每个节点由一个处理机、内存和一个或多个磁盘构成 处理机之间通过高速互联网进行通讯 SN结构克服了SD结构必须通过一个总线进行I/O操作的缺点，仅仅是对非局部磁盘的存取才通过网络来进行。 SN体系结构具有很好的可扩展性，有的甚至可以扩展到成千上万个节点 主要缺点是通讯代价和非局部磁盘的存取代价比较昂贵 P M P M P M P M P M 7.2 硬件体系结构 层次体系结构(COW, NOW) 结合了SN、SM、SD体系结构的特点，在高层看是一个SN体系结构，但每个节点是由一个SM体系结构所构成的。当然每个节点也可是一个SD体系结构 在这种体系结构中代码的编写是非常复杂的，降低编程复杂度的一种很好的办法是分布式虚拟存储器体系结构 P M P P P P P M P P P P P M P P P P User 节点A Client Server 磁盘映射 内存映射 共享虚拟堆 客户共享虚拟空间 服务器共享虚拟空间 页面读/写 User 节点B Client Server 磁盘映射 内存映射 共享虚拟堆 客户共享虚拟空间 服务器共享虚拟空间 页面读/写 DSVM 映射 7.3 数据分片技术 Round-robin：对于关系r中的第i个元组分配到第(i mod n)个磁盘上。该方法保证了每个磁盘上具有相同数目的元组数。 哈希分片：关系r中的一个或多个属性作为分