l744 计算机学报 011年 模机群在现实中是较难实现的.因而,对异构硬件的 3并行数据库 支持能力影响了其扩展性;(3)并行数据库若做到大 规模可扩展,其代价将会较高(需基于高端硬件来保 并行数据库起源于20世纪80年代,当前主流证可靠性需购买昂贵的软件系统),从而限制了其 的并行数据库都同早期的Gamm和 grace!等扩展性;(4根据CAP理论,在分布式系统中数 并行数据库类似.这些数据库都支持标准SQL,并据一致性( Consistency)、可用性( A vailability)、子 且实现了数据库界过去30年提出的许多先进技术.网可分解性( Network Part itioning)不可同时兼得, 其主要采用 shar hing结构,将关系表在节点选择其中任两项,便会损害另一项.并行数据库追求 间横向划分,并且利用优化器来对执行过程进行调的是数据一致性和系统的可用性,从而影响了它的 度和管理.其目标是高性能和高可用性. 扩展能力 并行数据库的最大优势在于性能.这主要得益 此外,如L2节所讨论的,基于并行数据库实现 于数据库界近几十年的研究成果——许多先进的技的传统数据仓库借助于外围工具(ETL工具、OLAP 术手段及算法,如索引、数据压缩、物化视图、结果缓产品、B报表工具、统计分析软件等)来完成数据的 冲、O共享、优化的数据连接等但是在大数据时预处理和分析展现任务,导致其数据处理及分析过 代如前言所述,数据移动的实现方式将影响其程涉及大量的数据迁移和计算,分析延迟往往较高 性能. 并行数据库通过SQL向外提供数据访问服务,4 Mapreduce SQL因其简单易用的特点而被广泛使用.因此,大 多BI工具都支持基于标准SQL的数据交互方式 M maPreduce是2004年由Gogl提出的面向 使得关系数据库能较好地兼容当前多数BI工具.某大数据集处理的编程模型,起初主要用作互联网数 些数据库,如 IBM DB2还针对一些BI工具进行了据的处理,例如文档抓取、倒排索引的建立等.但由 优化.但在大数据分析面前,SQL接口面临巨大挑于其简单而强大的数据处理接口和对大规模并行执 战SQL的优势源于其对底层数据访问的封装,但行、容错及负载均衡等实现细节的隐藏该技术一经 封装在一定程度上影响了其开放性.而且并行数据推出便迅速在机器学习、数据挖掘、数据分析等领域 库提供的用户自定义函数大都是基于单数据库实例得到广泛应用 设计的,从而不能在机群上并行执行,也即意味着传 M maPreduce将数据处理任务抽象为一系列的 统的实现方式不适合大数据的处理及分析而且,在Map(映射- Reduce(化简)操作对Map主要完成数 并行数据库中实现用户自定义函数往往需要经过复据的过滤操作, Reduce主要完成数据的聚集操作 杂的系统交互,甚至要熟悉数据库的内部结构及系输入输出数据均以4ey, value格式存储.用户在使 统调用等,从而难以使用 用该编程模型时,只需按照自己熟悉的语言实现 并行数据库在扩展性、容错性、成本、对异构环Map函数和 Reduce函即可, M maPreduce框架会自 境的支持等几项上有所欠缺这几项实际是相互影动对任务进行划分以做到并行执行 响的,我们以其最大问题—扩展性为主线展开讨 下面本文将以基于 M maPreduce的开源实现 论.并行数据库大多支持有限扩展,一般可扩至数百 H ado op为主,对其主要特性进行介绍 节点的规模,尚未有数千节点规模的应用案例.并行 M apReduce是面向由数千台中低端计算机组 数据库扩展性有限主要因为如下几点:(1)并行数成的大规模机群而设计的,其扩展能力得益于其 据库软件级容错能力较差并行数据库基于高端硬 shared nothing结构、各个节点间的松耦合性和较 件设计,并且假设査询失败属于稀有事件.因此当查强的软件级容错能力:节点可以被任意地从机群中 询失败时,一般采取重做查询的方式而在大规模机移除,而几乎不影响现有任务的执行.该技术被称为 群环境下,查询失败将会变为一个普通事件极端情RAIN( Redundant/ Reliable Array of Independent 况下,并行数据有可能出现不停重做查询的局面;( and Inex pensive) Nodes). MapReduce卓越的扩展 (2)并行数据库对异构硬件的支持非常有限,且对能力己在工业界(Goge、 Facebook、 Baidu、 Taobao 于处理较慢的节点反应敏感,容易出现“木桶效应 如第2中所论述的完舍基同构硬件搭建木规blishing②:该理论目种尚有设servedhttp:/www.cnki.net3 并行数据库 并行数据库起源于 20 世纪 80 年代, 当前主流 的并行数据库都同早期的 Gamma [ 6] 和 Grace [ 7] 等 并行数据库类似. 这些数据库都支持标准 SQL, 并 且实现了数据库界过去 30 年提出的许多先进技术. 其主要采用 shar ed-nothing 结构, 将关系表在节点 间横向划分, 并且利用优化器来对执行过程进行调 度和管理. 其目标是高性能和高可用性. 并行数据库的最大优势在于性能. 这主要得益 于数据库界近几十年的研究成果) )) 许多先进的技 术手段及算法, 如索引、数据压缩、物化视图、结果缓 冲、I/ O 共享、优化的数据连接等. 但是在大数据时 代, 如前言所述, 数据移动的实现方式将影响其 性能. 并行数据库通过 SQL 向外提供数据访问服务, SQ L 因其简单易用的特点而被广泛使用. 因此, 大 多 BI 工具都支持基于标准 SQL 的数据交互方式, 使得关系数据库能较好地兼容当前多数 BI 工具. 某 些数据库, 如 IBM DB2 还针对一些 BI 工具进行了 优化. 但在大数据分析面前, SQL 接口面临巨大挑 战. SQL 的优势源于其对底层数据访问的封装, 但 封装在一定程度上影响了其开放性. 而且并行数据 库提供的用户自定义函数大都是基于单数据库实例 设计的, 从而不能在机群上并行执行, 也即意味着传 统的实现方式不适合大数据的处理及分析. 而且, 在 并行数据库中实现用户自定义函数往往需要经过复 杂的系统交互, 甚至要熟悉数据库的内部结构及系 统调用等, 从而难以使用. 并行数据库在扩展性、容错性、成本、对异构环 境的支持等几项上有所欠缺. 这几项实际是相互影 响的, 我们以其最大问题) )) 扩展性为主线展开讨 论. 并行数据库大多支持有限扩展, 一般可扩至数百 节点的规模, 尚未有数千节点规模的应用案例. 并行 数据库扩展性有限主要因为如下几点: ( 1) 并行数 据库软件级容错能力较差. 并行数据库基于高端硬 件设计, 并且假设查询失败属于稀有事件. 因此当查 询失败时, 一般采取重做查询的方式. 而在大规模机 群环境下, 查询失败将会变为一个普通事件. 极端情 况下, 并行数据有可能出现不停重做查询的局面; ( 2) 并行数据库对异构硬件的支持非常有限, 且对 于处理较慢的节点反应敏感, 容易出现/ 木桶效应0. 如第 2 节中所论述的, 完全基于同构硬件搭建大规 模机群在现实中是较难实现的. 因而, 对异构硬件的 支持能力影响了其扩展性; ( 3) 并行数据库若做到大 规模可扩展, 其代价将会较高( 需基于高端硬件来保 证可靠性, 需购买昂贵的软件系统) , 从而限制了其 扩展性; ( 4) 根据CAP理论①[ 8] , 在分布式系统中, 数 据一致性( Consistency ) 、可用性( Availability ) 、子 网可分解性( Netwo rk Partitioning ) 不可同时兼得, 选择其中任两项, 便会损害另一项. 并行数据库追求 的是数据一致性和系统的可用性, 从而影响了它的 扩展能力. 此外, 如 11 2 节所讨论的, 基于并行数据库实现 的传统数据仓库借助于外围工具( ET L 工具、OLAP 产品、BI 报表工具、统计分析软件等) 来完成数据的 预处理和分析展现任务, 导致其数据处理及分析过 程涉及大量的数据迁移和计算, 分析延迟往往较高. 4 MapReduce M apReduce [ 5] 是 2004 年由 Go ogle 提出的面向 大数据集处理的编程模型, 起初主要用作互联网数 据的处理, 例如文档抓取、倒排索引的建立等. 但由 于其简单而强大的数据处理接口和对大规模并行执 行、容错及负载均衡等实现细节的隐藏, 该技术一经 推出便迅速在机器学习、数据挖掘、数据分析等领域 得到广泛应用[ 9] . M apReduce 将数据处理任务抽象为一系列的 M ap( 映射)-Reduce( 化简) 操作对. M ap 主要完成数 据的过滤操作, Reduce 主要完成数据的聚集操作. 输入输出数据均以〈key, value〉格式存储. 用户在使 用该编程模型时, 只需按照自己熟悉的语言实现 M ap 函数和 Reduce 函即可, M apReduce 框架会自 动对任务进行划分以做到并行执行. 下面本文将以基于 M apReduce 的开源实现 Hado op [ 10] 为主, 对其主要特性进行介绍. M apReduce 是面向由数千台中低端计算机组 成的大规模机群而设计的, 其扩展能力得益于其 shared-nothing 结构、各个节点间的松耦合性和较 强的软件级容错能力: 节点可以被任意地从机群中 移除, 而几乎不影响现有任务的执行. 该技术被称为 RA IN ( Redundant/ Reliable Arr ay of Independent ( and Inex pensive) No des) . MapReduce 卓越的扩展 能力已在工业界( Go ogle、Facebook、Baidu、Taobao 1744 计 算 机 学 报 2011 年 ① 该理论目前尚存争议