`
ssxxjjii
  • 浏览: 950467 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Google Map Reduce简介

 
阅读更多

http://www.cnblogs.com/xuqiang/archive/2011/05/28/2060854.html

<1>.并行计算简介 

计算机的早期阶段,程序都是serial(连续的),类似于批处理程序。

并行计算的程序中,进程将一个任务分割成多个部分parts,每个“部分“都是能够并行处理的,每个“部分”可以同时运行在不同的cpu上,这些cpus可以是同一台机器上,也可以是通过网络运行在不同机器的cpu上。

如果一个程序想要通过并行来实现,第一步的工作是需要将待处理的工作分割成一系列的任务task,并且这些任务是能够并行的运行在处理器上,当然一些情况下,待处理的工作是没有办法分割成这样的一些列的任务的,例如对于计算Fibonacci这个工作:

Fk+2 = Fk + Fk+1

该工作是不能被分割为这样的一系列的任务的,因为每个计算的值是需要依赖上次计算的结果的。

下面给出一个能够被“并行”的例子:

如果有大量的数据需要被处理,如果这些数据能够被分割为等大小的小块(partitions)。更加具体话的说,对于下面的数组:

如果我们需要对于上面数组的每个元素都进行处理,并且每个计算是相对独立的话,任务之间不需要交互,这是一个使用master/worker的基本实现:

Master:

  1. 初始化该数组,并且将该数组分割成各个部分subarray
  2. 将每个subarray发送到各个worker
  3. 如果各个worker完成了对于数组元素的计算的话,master将接受各个worker的计算结果

Worker:

  1. 接受subarray
  2. 处理该subarray
  3. 将计算结构传递给master

<2>.What is MapReduce? 

在lisp语言中,map作为一个输入函数接受一个序列,然后处理每个序列中value值,然后reduce将最终的map计算出来的结果整理成最终程序输出。这就是MapReduce最初的思想来源,通过用户定义的map函数将输入分割成key/value对,然后处理该数据,最终通过Reduce函数将处理完成的记过合并。

下面是一个简单的示例程序:

map(String key, String value):
// key: document name 
// value: document contents 
for each word w in value:
EmitIntermediate(w, "1");
reduce(String key, Iterator values):
// key: a word
// values: a list of counts
int result = 0;
for each v in values:
result += ParseInt(v);
Emit(AsString(result));

<3>. MapReduce是如何运行的? 

1. MapReduce Library首先将输入文件切割成多个小片的文件pieces,然后MapReduce Library将启动复制操作,将用户程序复制到各个a cluster of machines上。

2. 在这些a cluster of machines中,其中一个比较特殊称之为master,其他的machine被称之为worker,master选择空闲的worker并将任务(map任务或者是reduce任务)分配给这些空闲的worker任务。

3. 一个worker如果被master分配了map任务的话,该worker首先读取该key/value对,然后执行用户定义的map函数,这些处理完成的key/value对被缓存到内存中。

4. 然后,将这些key/value对写入本地磁盘,然后worker通知master。

5. 如果master接收到了worker在第4步的通知之后,master将这个信息传递给reduce worker,该reduce worker通过远程系统调用的形式读取该worker磁盘上存储的处理完的数据。

如果reduce worker读取完了所有的数据的话,然后该reduce worker将读取到的数据排序,如果数据量比较大的话,无法全部放在内存中,那么排序将使用外部排序来实现。

6. Reduce worker遍历已排序的数据,然后将数据传递到用户定义的Reduce函数。

7. 当所有的map和reduce完成之后,然后master唤醒用户程序。

通过整个程序的运行过程,我们可以看出用户程序仅仅需要编写Map函数和Reduce函数即可,MapReduce库首先通过调用用户自定义的Map函数,将输入文件分割,如果数据处理完成,将调用Reduce函数将结果合并起来。

 

分享到:
评论

相关推荐

    Google Map Reduce 中文版 论文

    MapReduce的核心思想来源于函数式编程语言中的map和reduce操作。 Map阶段是用户定义的一个函数,它接收输入键值对(key-value pairs),并生成一系列中间键值对。在这个例子中,输入可能是文档的名称(key)和文档...

    a java map reduce framework

    Reduce阶段接收来自多个Map任务的中间键值对,对每个键执行一次Reduce函数。Reduce函数的主要任务是对一组键值对进行聚合操作,生成新的键值对作为输出。这一步骤通常用于计算汇总信息,例如求和、计数等。 五、...

    google map reduce论文中文版

    MapReduce的核心思想是将复杂的大规模数据处理任务分解为“Map(映射)”与“Reduce(归约)”两个阶段,以此来简化程序员的工作,使他们无需深入了解分布式系统就能编写处理大规模数据的应用程序。 #### 引言 ...

    Map/Reduce:大规模集群上的简化数据处理

    该模型的核心思想是将复杂的并行和分布式计算过程简化为两个主要步骤:Map 和 Reduce。Map 阶段将原始数据拆分成键值对,应用用户自定义的映射函数,生成中间键值对;Reduce 阶段则将具有相同中间键的值聚合,通过...

    最高气温 map reduce hadoop 实例

    【标题】:“最高气温 map reduce hadoop 实例” 在大数据处理领域,Hadoop是一个不可或缺的开源框架,它专为分布式存储和处理大量数据而设计。本实例将介绍如何使用Hadoop MapReduce解决一个实际问题——找出给定...

    Google三大核心技术 pdf big_data map reduce gfs

    标签中的“pdf”、“big_data”、“map reduce”进一步强调了这些技术在大数据处理领域的应用,而“google_cloud”可能指的是Google Cloud Platform,Google提供的云服务,其中就包含了对这些核心技术的支持和使用。...

    使用Map-Reduce对大规模图进行排名和半监督分类

    标题中的“使用Map-Reduce对大规模图进行排名和半监督分类”是指利用MapReduce编程模型处理大规模图数据,实现图的排序(如PageRank)和半监督学习中的分类任务。MapReduce是由Google提出的一种分布式计算框架,适用...

    map-reduce.pdf

    ### Map-Reduce 模型详解 #### 一、Map-Reduce 平行处理框架与云计算 Map-Reduce 是一种高效的数据处理模型,尤其适用于大规模数据集的并行处理。它最初由 Google 提出,并被广泛应用于搜索引擎、大数据分析等领域...

    Map Reduce

    Map Reduce 编程模型和算法实现 MapReduce 是一个编程模型,也是一个处理和生成超大数据集的算法模型的相关实现。用户首先创建一个 Map 函数处理一个基于 key/value pair 的数据集合,输出中间的基于 key/value ...

    gfs+BigTable+map reduce 三合一.zip

    “map reduce 中文.doc”和“GFS中文.doc”、“BigTable中文.doc”则可能是对这些原始英文论文的中文翻译,便于不熟悉英文的读者理解。这些文档对于学习和掌握这三大核心技术非常有帮助,可以帮助读者了解它们如何...

    基于Map/Reduce的分布式搜索引擎研究

    Google的Map/Reduce是一个分布式计算框架,能够有效地在大型集群中处理大规模数据。其核心优势在于: - **高效处理能力**:通过将数据处理任务分解到多个节点上并行执行,极大地提高了数据处理的速度。 - **可扩展...

    谷歌三大论文(GFS,big Table,map reduce)

    它将复杂计算任务分解为两个阶段:Map(映射)和Reduce(规约)。 - 映射阶段:将输入数据拆分为键值对,然后分发到各个工作节点进行并行处理。 - 归约阶段:收集并整合映射阶段的结果,执行聚合操作,生成最终...

    hadoop中map/reduce

    MapReduce的设计理念源于Google的同名论文,它通过将大规模数据处理任务分解为两个阶段:Map(映射)和Reduce(化简),使得海量数据能够在多台计算机上并行处理,极大地提高了数据处理效率。 Map阶段是数据处理的...

    第02节:hadoop精讲之map reduce原理及代码.pdf

    首先,MapReduce模型由两个主要操作构成:Map(映射)和Reduce(归约)。用户编写Map函数和Reduce函数,然后交给Hadoop框架进行处理。Map函数处理输入的键值对数据,生成中间键值对数据;Reduce函数再将这些中间键值...

    map-reduce实现分布式爬虫

    **MapReduce** 是Google提出的一种用于大规模数据处理的计算模型,它将复杂的数据处理任务拆分为两个阶段:Map(映射)和Reduce(规约)。Map阶段将原始数据切分成多个小块,分别进行处理,而Reduce阶段则负责汇总...

Global site tag (gtag.js) - Google Analytics