设为首页 - 加入收藏 信阳站长网 (http://www.0376zz.com)- 国内知名站长资讯网站,提供最新最全的站长资讯,创业经验,网站建设等!
热搜: 产品 数据 谷歌 或将
当前位置: 首页 > 运营中心 > 网站设计 > 教程 > 正文

MapReduce:大型集群上的简化数据处理

发布时间:2019-11-08 19:23 所属栏目:[教程] 来源:数据科学家姜兴琪
导读:摘要: MapReduce是一个编程模型,以及处理和生成大型数据集的一个相关实现,它适合各种各样的现实任务。用户指定计算的map和reduce函数。底层运行系统自动地将大规模集群机器间的计算并行化,处理机器故障,以及调度机器间通信以充分利用网络和磁盘。程序

摘要:

MapReduce是一个编程模型,以及处理和生成大型数据集的一个相关实现,它适合各种各样的现实任务。用户指定计算的map和reduce函数。底层运行系统自动地将大规模集群机器间的计算并行化,处理机器故障,以及调度机器间通信以充分利用网络和磁盘。程序员会发现这个系统很好使用:在过去的去年中,超过一万个不同的MapReduce程序已经在Google内部实现,平均每天有十万个MapReuce作业在Google集群上被执行,每天总共处理20PB以上的数据。

1 简介

在MapReduce开发之前,作者和其他许多的Google员工实现了数以百计的处理大量原始数据(如抓取到的文档、Web请求日志等等)的专用计算方法,以计算各种导出的数据,如倒排索引、Web文档图结构的各种表示、每个host抓取到的页面数的总结、某一天最频繁的一组查询。大多数这样的计算在概念上是非常简单的,然而它们的输入数据量通常非常大。为了在合理的时间内完成这些计算,它们必须分布到成百上千的机器上。如何并行化计算,分发数据,以及处理故障,这些问题结合起来,往往会让程序员使用大量复杂代码来处理,而掩盖了原本简单的计算。

为了应对这一复杂性,我们设计了一个新的抽象,它允许我们表达试图执行的简单计算,但将并行化、容错、数据分布和负载均衡等凌乱的细节隐藏到了库中。这个抽象的灵感来源于出现在Lisp和许多其他函数式语言中的map和reduce原语。我们实现了大部分的计算,包括为输入的每一个逻辑记录应用一个map操作以计算一组中间键值对,然后对所有共享同一个键的值应用一个reduce操作以恰当地结合导出的数据。此函数式模型支持用户自定义map和reduce操作,使我们能非常容易地并行处理大型计算,和使用再执行(reexecution)作为主要的容错机制。

这项工作的主要贡献就是一个简单而强大的接口,它完成自动并行化、大规模分布计算,结合该接口的一个实现在大型商用PC集群上获得了很高的性能表现。该编程模型还可以用于同一台机器上多个核心间的并行计算。

第2部分描述了基本的编程模型并给出几个例子。第3部分描述了MapReduce接口专门针对基于集群的计算环境的一个实现。第4部分描述了我们发现的这个编程模型的几个很有用的改进(refinements)。第5部分描述了对各种不同任务的实现的性能度量。第6部分探索了MapReduce在Google中的应用,包括使用它作为重写我们的生产索引系统的基础的一些经验。第7部分讨论了相关和未来的工作。

2 编程模型

这个计算需要一组输入键/值对,并生成一组输出键/值对。MapReduce库的使用者将计算表达为两个函数:map和reduce。

map,由用户编写,需要一对输入并生成一组中间键/值对。MapReduce库将所有与相同键值 I 相关联的值组合到一起,并将它们传递给reduce函数。

Reduce函数,同样由用户编写,接受中间键 I 和这个键的一组值。它将这些值合并以形成一组可能更小的值。通常每次reduce调用只生成0个或1个输出值。中间值靠一个迭代器提供给用户的reduce函数。这使我们能够处理大量太大以至于不能装入内存的值列表。

2.1 例子

考虑一下在一个巨大的文档集合中统计每个单词出现次数的问题。使用者会编写与下面伪代码类似的代码:

  1. map(String key, String value);  
  2. // key: document name  
  3. // value: document contents  
  4. for each word w in value:  
  5.  EmitIntermediate(w, "1");  
  6.   
  7.  
  8. reduce(String key, String values);  
  9. // key: a word  
  10. // values: a list of counts  
  11. int result = 0;  
  12. for each v in values:  
  13.  result += ParseInt(v);  
  14. Emit(AsString(result)); 

map函数发出每个单词加一个相关的出现次数(count)(在这个简单例子中仅为1)。reduce函数对发给一个单词的所有数(count)求和。

此外,用户编写代码将输入和输出文件名以及可选的调优参数填入mapreduce规范对象中。然后调用MapReduce函数,将它传递给规范对象。用户的代码与MapReduce库(C++实现)相连接。我们最初的MapReduce资料中有这个例子的完整程序【8】。

2.2 类型

尽管前面的伪代码是按照输入输出字符串形式编写的,概念上由用户提供的map和reduce函数是有相关类型的。

  1. map (k1, v1) --> list(k2, v2)  
  2. reduce (k2, list(v2)) --> list(v2) 

也就是说,输入键和值与输出键和值来自不同的域。此外,中间键和值与输出键和值来自同一个域。

3 实现

MapRedue接口的许多不同实现都是可能的。正确的选择取决于环境。例如,一种实现可能适合一个小型的共享内存的机器,另外一种可能适合一个大型的NUMA多处理器,而另外一种可能适合一个更大的联网计算机集合。在我们最初的文章发表以后,已经发展出了很多MapReduce的开源实现【1, 2】,MapReduce在各种问题领域的适用性也得到了研究【7, 16】。

这一部分描述了我们的一种MapReduce实现,其目标是目前广泛应用在Google中的计算环境:由交换千兆以太网连接在一起的大型PC集群【4】。在该环境中,机器通常运行Linux系统,有双核 x86 处理器以及4-8GB内存。个别机器拥有1GB/s的网络带宽,但每台机器等分的带宽远远低于1GB/s。一个计算集群包含了成千上万台机器,因此机器故障是很常见的。存储由直接附在单独机器上的廉价IDE磁盘提供。GFS,Google内部开发的一个分布式文件系统【10】,用来管理存储在这些磁盘上的数据。文件系统使用复制来提供不可靠的硬件之上的可用性与可靠性。

使用者提交 jobs 给调度系统。每个 job 包含一组任务,且由调度程序映射(mapped)到集群间的一组可用的机器上。

3.1 执行概述

【免责声明】本站内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。

网友评论
推荐文章