MapReduce大数据处理平台与算法研究进展宋杰 , 孙宗哲 , 毛克明 , 鲍玉斌 , 于戈.pdf

上善若水

164

30页

1次

2022-05-20

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2017,28(3):514−543 [doi: 10.13328/j.cnki.jos.005169] http://www.jos.org.cn

MapReduce 大数据处理平台与算法研究进展

∗

宋

杰

孙宗哲

毛克明

鲍玉斌

于

戈

(东北大学软件学院,辽宁沈阳 110819)

(东北大学计算机科学与工程学院,辽宁沈阳 110819)

通讯作者: 宋杰, E-mail: songjie@mail.neu.edu.cn

摘要: 综述了近年来基于 MapReduce 编程模型的大数据处理平台与算法的研究进展.首先介绍了 12 个典型的

基于 MapReduce 的大数据处理平台,分析对比它们的实现原理和适用场景,抽象其共性;随后介绍基于 MapReduce

的大数据分析算法,包括搜索算法、数据清洗/变换算法、聚集算法、连接算法、排序算法、偏好查询、最优化算

法、图算法、数据挖掘算法,将这些算法按照 MapReduce 实现方式分类,分析影响算法性能的因素;最后,将大数据

处理算法抽象为外存算法,并对外存算法的特征加以梳理,提出了普适的外存算法性能优化方法的研究思路和问题,

以供研究人员参考.具体包括优化外存算法的磁盘 I/O、优化外存算法的局部性以及设计增量式迭代算法.现有的大

数据处理平台和算法研究多集中在基于资源分配和任务调度的平台动态性能优化、特定算法并行化、特定算法性

能优化等领域,所提出的外存算法性能优化属于静态优化方法,是现有研究的良好补充,为研究人员提供了广阔的研

究空间.

关键词: 大数据;MapReduce;外存算法;大数据处理;算法性能优化

中图法分类号: TP311

中文引用格式: 宋杰,孙宗哲,毛克明,鲍玉斌,于戈.MapReduce 大数据处理平台与算法研究进展.软件学报,2017,28(3):

514−543. http://www.jos.org.cn/1000-9825/5169.htm

英文引用格式: Song J, Sun ZZ, Mao KM, Bao YB, Yu G. Research advance on mapreduce based big data processing platforms

and algorithms. Ruan Jian Xue Bao/Journal of Software, 2017,28(3):514−543 (in Chinese). http://www.jos.org.cn/1000-9825/

5169.htm

Research Advance on MapReduce Based Big Data Processing Platforms and Algorithms

SONG Jie

, SUN Zong-Zhe

, MAO Ke-Ming

, BAO Yu-Bin

, YU Ge

(Software College, Northeastern University, Shenyang 110819, China)

(School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China)

Abstract: This paper introduces the research advance on MapReduce based big data processing platforms. Frist, twelve typical

MapReduce based data processing platforms are descripted, their implementation principles and application areas are compared, and their

commonalities are concluded. Second, the MapReduce based big data processing algorithms, including search algorithms, data

cleansing/transformation algorithms, aggregation algorithms, join algorithms, sorting algorithms, optimization algorithms, preference

query algorithms, graph algorithms, and data mining algorithms, are studied. These algorithms are classified by their MapReduce

implementations, and the factors that affect their performance are analyzed. Finally, big data processing algorithms are abstracted as the

out-of-core algorithms whose performance features are well analyzed. The considerations, ideas and challenges of universal optimizations

on the performance of out-of-core algorithms are proposed as references for researchers. These optimizations include optimizing

algorithms’ I/O cost and locality, and designing incremental iterative algorithms. Comparing the current topics, such as resource allocation

∗ 基金项目: 国家自然科学基金(61672143, 61433008, 61402090, 61502090)

Foundation item: National Natural Science Foundation of China (61672143, 61433008, 61402090, 61502090)

收稿时间: 2016-08-01; 修改时间: 2016-09-14; 采用时间: 2016-11-01; jos 在线出版时间: 2016-11-29

CNKI 网络优先出版: 2016-11-29 13:35:10, http://www.cnki.net/kcms/detail/11.2560.TP.20161129.1335.011.html

宋杰等:MapReduce 大数据处理平台与算法研究进展

515

and task scheduling based dynamic optimizations on platform, parallelization for specific algorithms, and performance optimizations on

iterative algorithms, the proposed static optimizations serve as complements that highlight new areas for the researchers.

Key words: big data; MapReduce; out-of-core algorithm; big data processing; performace optimization on algorithms

近年来,伴随着信息技术、互联网和物联网技术的不断发展,数据采集终端迅猛增加,人们步入信息爆炸的

大数据时代.正如麦肯锡所说:“数据,已经渗透到当今每一个行业和业务职能领域,成为重要的生产因素.人们对

于海量数据的挖掘和运用,预示着新一波生产率增长和消费者盈余浪潮的到来.”在大数据时代,商业、经济及其

他领域中的决策将不再基于经验和直觉,而是基于大数据分析结果,因此,大数据分析处理技术已经成为一个重

要的研究和应用领域.同时,业界对于该技术的急切需求以及云计算技术的成熟,促使各种基于大规模分布式系

统的大数据处理平台和处理算法如雨后春笋般涌现

[1]

.大数据处理采用分治法,将大数据问题分解成规模较小

的子问题求解,然后合并子问题的解,从而得到最终解.基于此,Google 公司研发的 MapReduce 是一种专门处理

大数据的编程模型和实现框架,具有简单、高效、易伸缩以及高容错性等特点

[2]

Google MapReduce 在设计之初致力于通过大规模廉价服务器集群实现大数据的并行处理,它优先考虑系

统的伸缩性和可用性,用于处理互联网中海量网页内容数据,通过存储、索引、分析以及可视化等处理步骤,实

现用户对网页内容的搜索和访问

[2]

.MapReduce 在一个简单的库中隐藏分布式执行、容错、数据分发、任务调

度以及负载均衡等难点,隐藏远程数据访问、节点失效和任务间通信等细节.而 MapReduce 之所以能够迅速成

为大数据处理的主流计算平台,得力于其自动并行、自然伸缩、实现简单和支持商用硬件等特性

[3]

.现如今,

MapReduce 已是成熟的 TB/PB 级大数据处理平台广泛地应用于社交网络、科学数据分析、传感器数据处理、

医疗和电子商务应用中,并拥有各种不同版本的实现.本文第 1 节将分析和对比典型 MapReduce 大数据处理平

台,介绍其优劣势以及适用范围.

大数据处理平台是一种计算平台,计算平台泛指支持算法执行的硬件系统、操作系统和运行库

[4]

,那么大数

据处理平台则泛指可以支持大数据处理算法执行的平台.MapReduce 平台广泛地支持大数据处理算法,包括数

据清洗、排序、统计分析、连接查询、图分析、PageRank、分类、聚类、最优化、机器学习、自然语言处理

算法等.MapReduce 为上述算法提供了编程模型和分布式并行的运行环境

[5]

.大数据处理算法是以大数据为输

入,在给定资源约束内处理数据,并计算出给定问题结果的算法

[6]

.大数据处理算法读写数据时间长、数据难以

放入内存、待处理的数据无法存储在一台机器上,因此多为外存算法

[7]

.外存算法是指算法所处理的数据过大而

无法一次放入内存,必须借助外存反复读写数据的算法.外存算法不再基于无限大内存这一假设,不采用随机读

写内存的数据访问方式,而通过传输大规模连续的数据块来平摊巨大的 I/O 代价

[8]

.大数据处理算法的研究现在

仍旧处于初始阶段,现有研究多集中在如何采用 MapReduce 改写传统算法、特定算法的优化这类问题上,对算

法自身的、且具有一定普适性的优化研究较少

[8,9]

.本文第 2 节将基于 MapReduce 编程模型,按 Maps 算法、

Reduces 算法和迭代算法这 3 种分类来例举大数据处理算法,并分析影响算法性能的因素.本文第 3 节总结外存

算法模型,并提出此类算法的优化思路,重点从算法磁盘 I/O、算法局部性和增量式迭代算法这 3 个角度阐述.

综上所述,基于 MapReduce 技术,大数据处理平台采用集群系统作为硬件环境,分布式中间件作为数据存储

和计算平台.采用无共享体系结构,数据处理程序部署在每个节点之上.数据保存在分布式文件系统中.而大数

据处理算法以大数据作为输入,在大数据处理平台上执行.在算法执行阶段,平台将算法分解为一种或多种类型

的任务,任务的实例会分发到多个节点上并行执行,多节点上并行执行的实例相互独立,实例间不存在远程调

用.实例会访问本地或远程节点的数据.大数据处理算法分解为多种任务,每种任务都视为一个外存算法,每个

节点上运行的实例都视为执行态的外存算法.本文将综述基于 MapReduce 的大数据处理平台和大数据处理算

法,分析它们的性能特征;与传统的优化任务间逻辑关系、资源分配、数据布局、任务调度等动态优化方法不

同,本文将从外存算法角度提出静态的算法性能优化思路和挑战.

of 30

免费下载

软件学报计算机技术

关注

评论