400-685-0732

WJMonitor舆情之声

企业大数据智能舆情监测管理解决方案

全网监测海量数据按需发布监测预警

实时把握舆情动态精准追溯信息源头

获取验证码
企业采购 个人使用
当前位置: 首页 > SEO博客 > 分布式并发计算模型MapReduce解析

分布式并发计算模型MapReduce解析

时间:2012-01-07 10:31:07
背景

每天,社会化媒体网站,诸如Facebook、Twitter及新浪微博等,会有上亿条非结构化和半结构化的数据被插入到数据库,而且每年的数据量还在呈指数级增长的态势,面对如此增长的大数据,企业是如何面对的?如何有效的对这些大数据进行高效地存储,以及利用这些大规模数据进行实时的计算和分析,是一个非常核心的技术课题。

为了解决这一行业难题,Google 在2004年提出了一个重要的分布式并发计算模型:MapReduce 。由于MapReduce拥有良好的易用性和可扩展性,在工业界和学术界的得到了广泛的支持。

定义

在维基百科中,MapReduce是这样定义的:

MapReduce是Google提出的一个软件架构,用于大规模数据集(大于1TB)的并行运算。概念"Map(映射)"和"Reduce(化简)",和他们的主要思想,都是从函数式编程语言借来的,还有从矢量编程语言借来的特性。

英文定义:

MapReduce is a framework for processing highly distributable problems across huge datasets using a large number of computers (nodes), collectively referred to as a cluster (if all nodes use the same hardware) or a grid (if the nodes use different hardware). Computational processing can occur on data stored either in a filesystem (unstructured) or in a database (structured).

算法

MapReduce 以函数方式提供了 Map 和 Reduce 来进行分布式计算。Map 相对独立且并行运行,对存储系统中的文件按行处理,并产生键值(key/value)对。Reduce 以 Map 的输出作为输入,相同 key 的记录汇聚到同一 reduce,reduce 对这组记录进行操作,并产生新的数据集。所有 Reduce 任务的输出组成最终结果。MapReduce算法流程图如下:

mapreduce处理流程

 

形式化描述如下:
Map: (k1,v1) -> list(k2,v2)
Reduce:(k2,list(v2)) ->list(v3)
MapReduce 对任务的处理流程主要分为以下几步:

1,用户提交 MapReduce 程序至主控节点,主控节点将输入文件划分成若干分片(split)。主控节点 Master 和工作节点 worker 启动相应进程;

2,主控节点根据工作节点实际情况,进行 map 任务的分配;

3,被分配到 map 任务的节点读取文件的一个分片,按行进行 map 处理,将结果存在本地。结果分成 R 个分片进行存储,R 对应的是 Reduce 数目;

4,Map 节点将存储文件的信息传递给 Master 主控节点,Master 指定 Reduce 任务运行节点,并告知数据获取节点信息;

5,Reduce 节点根据 Master 传递的信息去 map 节点远程读取数据。因为 reduce 函数按分组进行处理,key 相同的记录被一同处理,在 reduce 节点正式处理前,对所有的记录按照 key 排序;

6,Reduce 将处理结果写入到分布式文件系统中。

特性

1,分布式和可靠性

MapReduce通过把对数据集的大规模操作分发给网络上的每个节点实现可靠性;每个节点会周期性的把完成的工作和状态的更新报告回来。如果一个节点保持沉默超过一个预设的时间间隔,主节点(类同Google档案系统中的主服务器)记录下这个节点状态为死亡,并把分配给这个节点的数据发到别的节点。每个操作使用命名文件的不可分割操作以确保不会发生并行线程间的冲突;当文件被改名的时候,系统可能会把他们复制到任务名以外的另一个名字上去。

2,可扩展性

在硬件架构上,每增加一个服务器节点,采用MapReduce就能将新的计算能力接入到集群中去,使得其具有较高的可扩展性。

应用实现

Hadoop。Hadoop 由 Apache Software Foundation 公司于 2005 年秋天作为 Lucene 的子项目 Nutch 的一部分正式引入。它受到最先由 Google Lab 开发的 MapReduce 和 Google File System 的启发。2006 年 3 月份,MapReduce 和 Nutch Distributed File System (NDFS) 分别被纳入称为 Hadoop 的项目中。Hadoop作为一个分布式系统基础架构,用户可以在不了解分布式底层细节的情况下,开发分布式程序,充分利用集群的威力高速运算和存储。

应用领域

在Google,MapReduce用在非常广泛的应用程序中,包括“分布grep,分布排序,web连接图反转,每台机器的词矢量,web访问日志分析,反向索引构建,文档聚类,机器学习,基于统计的机器翻译……”值得注意的是,MapReduce实现以后,它被用来重新生成Google的整个索引,并取代老的ad hoc程序去更新索引。MapReduce会生成大量的临时文件,为了提高效率,它利用Google档案系统来管理和访问这些文件。2011年,Google发表Snappy压缩函式库开源项目;Snappy是Google MapReduce的一部分,以减少Network I/O 或 Disk I/O提升效能。

缺点

1,缺乏当前DBMS基本都拥有的大多数特性

2,和DBMS用户已经依赖的所有工具都不兼容

参考资料

1,中文维基百科:http://zh.wikipedia.org/wiki/MapReduce

2,英文维基百科:http://en.wikipedia.org/wiki/MapReduce

3,Hadoop百度百科:http://baike.baidu.com/view/908354.htm

4,MapReduce 编程模型在日志分析方面的应用:http://www.ibm.com/developerworks/cn/java/java-lo-mapreduce/index.html
分享按钮