MapReduce的简单解释？

Question

与我CouchDB问题。

任何人都可以在用词上numbnuts能够理解解释的MapReduce？

Answer 1

1. 拿一堆数据
2. 的进行某种变换的每一个数据转换为另一种数据
3. 的结合这些新的数据到更简单的数据

第二步是地图。第3步是减少。在一对的压力米的道路上的两个脉冲之间

例如，

1. 得到的时间
2. 那些时间映射到基于米的距离速度
3. 减少这些速度到平均速度

MapReduce在Map和Reduce之间分割的原因是因为不同的部分可以很容易地并行完成。 （特别是，如果减少具有一定的数学属性。）

对于的MapReduce的复杂但很好的描述，见：Google's MapReduce Programming Model -- Revisited (PDF)。

Answer 2

让我们从Google paper的例子。 MapReduce的目标是能够有效地使用一些处理单元并行处理某些类型的算法。例如下面的例子：你想提取所有单词和它们的数量在一组文档中。

典型的实现：

for each document 
    for each word in the document 
     get the counter associated to the word for the document 
     increment that counter 
    end for 
end for 

的MapReduce实现：

Map phase (input: document key, document) 
for each word in the document 
    emit an event with the word as the key and the value "1" 
end for 

Reduce phase (input: key (a word), an iterator going through the emitted values) 
for each value in the iterator 
    sum up the value in a counter 
end for 

解决这个问题，你就会有一个主计划，将在将在处理“拆分”分区组文档并行的地图阶段。发出的值由工作人员在专用于该工作人员的缓冲区中写入。一旦通知缓冲区已准备好处理，主程序就会委派其他工作人员执行Reduce阶段。

每个工人产出（即地图或降低工人）实际上是存储在分布式文件系统（GFS为谷歌），或在CouchDB的分布式数据库中的文件。

Answer 3

MapReduce的是并行地处理数据的大量资金，而不需要开发人员编写比映射器之外的任何其它代码和减少功能的方法。

地图函数将数据带入并产生一个结果，并将结果保存在屏障中。此功能可以与大量的地图任务并行运行。数据集然后可以是减少为标量值。

所以，如果你觉得它像一个SQL语句

SELECT SUM(salary) 
FROM employees 
WHERE salary > 1000 
GROUP by deptname 

我们可以使用地图，让我们的员工的子集薪水> 1000 该地图发出的屏障进入组大小水桶。

Reduce将对这些组进行求和。给你你的结果集。

刚摘下这从谷歌纸

Answer 4

我university学习笔记走出一路下跌的基本知识为Map和Reduce。

---

地图是在某种列表的另一个项目种类，其“改造”项目，并把它们放回在同类列表的功能。

假设我有一个数字列表：[1,2,3]，我想每个数字加倍，在这种情况下，函数为“每个数字加倍”是函数x = x * 2.并且没有映射，可以写一个简单的循环，说

A = [1, 2, 3] 
foreach (item in A) A[item] = A[item] * 2 

和我不得不A = [2，4,6]，但代替书写循环，如果我有一个映射函数可以写

A = [1, 2, 3].Map(x => x * 2) 

x => x * 2是针对[1,2,3]中的元素执行的函数。会发生什么情况是程序需要每个项目，通过使x等于每个项目来执行（x => x * 2），并产生结果列表。

1 : 1 => 1 * 2 : 2 
2 : 2 => 2 * 2 : 4 
3 : 3 => 3 * 2 : 6 

所以与执行映射函数之后（X => X * 2）你必须[2，4,6]。

---

减少是列出了“收集”的项目，在他们的所有进行一些计算，从而减少他们对单个值的函数。

找到总数或找到平均值都是reduce函数的实例。比如，如果你有一个数字的列表，说[7，8，9]和你希望他们总结出来的，你会写这样的

A = [7, 8, 9] 
sum = 0 
foreach (item in A) sum = sum + A[item] 

环路但是，如果你有机会到降低功能，你可以这样写它

A = [7, 8, 9] 
sum = A.reduce(0, (x, y) => x + y) 

现在有点困惑，为什么有2个参数（0和函数与x和y）通过。为了使reduce函数有用，它必须能够取2个项目，计算某些东西并将2个项目“减少”到仅仅一个值，因此程序可以减少每个项目直到我们有一个值。

的执行将如下：

result = 0 
7 : result = result + 7 = 0 + 7 = 7 
8 : result = result + 8 = 7 + 8 = 15 
9 : result = result + 9 = 15 + 9 = 24 

但你不想开始用零所有的时间，所以第一个参数是有让你在第一result =指定的种子值特别是值线。

说你要总结2所列出，它可能是这样的：

A = [7, 8, 9] 
B = [1, 2, 3] 
sum = 0 
sum = A.reduce(sum, (x, y) => x + y) 
sum = B.reduce(sum, (x, y) => x + y) 

，或者您需要更可能在现实世界中找到一个版本：

A = [7, 8, 9] 
B = [1, 2, 3] 

sum_func = (x, y) => x + y 
sum = A.reduce(B.reduce(0, sum_func), sum_func) 

---

它在数据库软件中是一件好事，因为通过Map \ Reduce支持，您可以使用数据库而无需知道数据库如何存储在数据库中以使用它，这就是数据库引擎的用途。

您只需要能够通过向引擎提供Map或Reduce函数来“告诉”您需要的引擎，然后数据库引擎就可以找到数据，应用您的函数，然后出现结果你想都不知道它是如何遍历所有记录的。

有索引和键，连接和视图以及单个数据库可以容纳的许多东西，所以通过屏蔽数据实际存储的方式，使代码更易于编写和维护。并行编程也是如此，如果您只是指定想要对数据执行的操作，而不是实际实现循环代码，那么底层基础架构可以“并行化”并在并行循环中为您执行函数。

Answer 5

MAP和REDUCE是从人类杀死最后一只恐龙时开始的旧的Lisp函数。

试想一下，你有城市有关的名称，生活在那里的人数量和城市规模的信息列表：

(defparameter *cities* 
    '((a :people 100000 :size 200) 
    (b :people 200000 :size 300) 
    (c :people 150000 :size 210))) 

现在，你可能想找到城市与人口密度最高。

首先，我们创建一个使用MAP城市名和人口密度的列表：

​​

使用缩小，我们现在可以找到城市最多的人口密度。

(reduce (lambda (a b) 
      (if (> (second a) (second b)) 
      a 
      b)) 
     '((A 500) (B 2000/3) (C 5000/7))) 

=> (C 5000/7) 

结合，我们得到下面的代码两部分：

(reduce (lambda (a b) 
      (if (> (second a) (second b)) 
      a 
      b)) 
     (map 'list 
      (lambda (city) 
       (list (first city) 
        (/ (getf (rest city) :people) 
         (getf (rest city) :size)))) 
      *cities*)) 

让我们介绍的功能：

(defun density (city) 
    (list (first city) 
     (/ (getf (rest city) :people) 
      (getf (rest city) :size)))) 

(defun max-density (a b) 
    (if (> (second a) (second b)) 
      a 
      b)) 

然后，我们可以写我们的地图减少代码为：

(reduce 'max-density 
     (map 'list 'density *cities*)) 

=> (C 5000/7) 

它叫MAP和REDUCE（评价是从内到外），所以它被称为图减少。

Answer 6

我不想听起来陈词滥调，但是这帮助了我这么多，这是很简单的：

cat input | map | reduce > output 

Answer 7

一个真正容易，快速和“傻瓜”介绍MapReduce的可在：http://www.marcolotz.com/?p=67

发布它的一些内容：

首先，为什么最初创建MapReduce？

基本上Google需要一种解决方案，使大型计算作业易于并行化，从而允许数据分布在通过网络连接的多台计算机上。除此之外，它必须以透明的方式处理机器故障并管理负载平衡问题。

什么是MapReduce的真正优势？

有人可能会说MapReduce魔术是基于Map和Reduce功能的应用程序。我必须承认交配，我强烈反对。使MapReduce如此受欢迎的主要特征是它具有自动并行和分布功能，并结合简单的界面。这些因素与透明故障处理相结合，对于这个框架非常流行的大多数错误。

在纸张上更深入一点：

的MapReduce是在谷歌的纸最初提到的（院长&格玛沃特，2004年 - 点击这里）作为一种解决方案使用类似的办法，使在大数据计算和商品 - 计算机集群。与用Java编写的Hadoop相反，Google的框架是用C++编写的。该文件描述了一个并行框架如何使用Map函数和Reduce函数对大数据集进行函数式编程。

在这个解决方案，将有两个主要步骤： - 称为Map和Reduce - ， - 与所述第一和第二之间的可选的步骤： - 称为联合。 Map步骤将首先运行，在输入键值对中进行计算并生成新的输出键值。我们必须记住，输入键值对的格式不一定需要与输出格式对匹配。 Reduce步骤将汇集相同密钥的所有值，并对其执行其他计算。结果，最后一步将输出键值对。 MapReduce最普通的应用之一就是实现字数统计。

此应用程序的伪代码中，波纹管式给出：

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)); 

正如可以注意到，该地图读取所有词语的记录（在此情况下，记录可以是一个线）并将该单词作为关键字发出，数字1作为值发出。 稍后，reduce将对同一个键的所有值进行分组。举一个例子：假设“房子”这个词在记录中出现了三次。减速器的输入是[house，[1,1,1]]。在减速器中，它将总和关键房屋的所有值，并给出以下关键值：[house，[3]]。

这里是如何做到这一点看起来像一个MapReduce框架的图像：

由于MapReduce应用一些其他的典型例子，可以说：

•的URL访问计数频率

•反网络链接图

•分布式的grep

•每台主机

期限矢量为了避免过多的网络流量，本文介绍了该框架应如何尽量保持数据局部性。这意味着它应该始终尝试确保运行Map作业的机器在其内存/本地存储器中具有数据，避免从网络中获取数据。为了通过放置映射器来减少网络，使用之前描述的可选组合器步骤。组合器在给定机器中的映射器的输出上执行计算，然后将其发送到减速器 - 可能在另一台机器中。

该文件还描述了框架的元素如何在出现故障时的行为。这些元素在论文中被称为工人和主人。它们将在开源实现中分成更具体的元素。 由于Google只是在论文中描述了这种方法，而没有发布其专有软件，因此为了实现该模型而创建了许多开源框架。例如，可以说Hadoop或MongoDB中有限的MapReduce功能。

运行时应该处理非专业程序员的细节，例如对输入数据进行分区，在大量机器上安排程序执行，处理机器故障（当然是透明的方式）以及管理机器间通信。有经验的用户可能会调整这些参数，因为输入数据将如何在工作人员之间进行分区。

关键概念：

•容错：必须容忍摆好机器故障。为了执行此操作，主人定期对工作人员进行处理。如果主人在特定的时间间隔内没有收到给定工作人员的答复，则主人会将该工作定义为失败。在这种情况下，由有故障的工作人员完成的所有地图任务都会被丢弃，并被分配给其他可用的工作人员。如果工作人员仍在处理地图或减少任务，则会发生类似情况。请注意，如果工作人员已完成其缩减部分，则所有计算在失败时已经完成并且不需要重置。作为主要的失败点，如果主人失败，所有的工作都会失败。出于这个原因，可以为主设定定期检查点，以保存其数据结构。在最后一个检查点和主站故障之间发生的所有计算都会丢失。

•Locality：为了避免网络流量，该框架试图确保所有输入数据在本地可供计算机上的计算机使用。在原始描述中，它使用复制因子设置为3且块大小为64 MB的Google文件系统（GFS）。这意味着64 MB（构成文件系统中的文件）的相同块将在三台不同的机器中具有相同的副本。大师知道块在哪里，并尝试在该机器中安排地图作业。如果失败，主机会尝试在任务输入数据副本附近分配一台机器（即数据机器同一机架中的工作机）。

•任务粒度：假设每个映射阶段被分成M段，并且每个减少阶段分为r个，理想的将是M和R不是工人机的数量较大很多。这是因为执行许多不同任务的工作人员改进了动态负载平衡。除此之外，它还可以在工作人员失败的情况下提高恢复速度（因为已经完成的许多地图任务可以分散到所有其他机器中）。

•备份任务：有时，Map或Reducer工作人员的行为可能比集群中的其他人慢得多。这可以保持总处理时间并使其等于该单个慢速机器的处理时间。最初的论文描述了另一种称为“备份任务”的备选方案，当MapReduce操作接近完成时，由主方安排。这些是由正在进行的任务的主人安排的任务。因此，当主或备份完成时，MapReduce操作完成。

•计数器：有时可能需要计数事件发生次数。出于这个原因，计数创建。每个工人的计数器值会定期传播给主人。然后，主人在MapReduce操作完成时聚集（是的，看起来像Pregel聚合器来自这个地方）成功的映射的计数器值并减少任务并将它们返回给用户代码。在主状态中还有一个当前的计数器值，所以观察过程的人可以跟踪它的行为。

好吧，我想用上面的所有概念，Hadoop对你来说将是一块蛋糕。如果您对原始MapReduce文章或任何相关内容有任何疑问，请告诉我。

Answer 8

如果熟悉Python，以下是MapReduce的最简单的可能的解释：

In [2]: data = [1, 2, 3, 4, 5, 6] 
In [3]: mapped_result = map(lambda x: x*2, data) 

In [4]: mapped_result 
Out[4]: [2, 4, 6, 8, 10, 12] 

In [10]: final_result = reduce(lambda x, y: x+y, mapped_result) 

In [11]: final_result 
Out[11]: 42 

了解如何原始数据的每个段被单独地处理，在这种情况下，乘以2（地图 MapReduce的一部分）。基于mapped_result，我们得出结论：42（MapReduce的减少部分）。

该示例的一个重要结论是每个处理块都不依赖于另一个块。例如，如果thread_1映射为[1, 2, 3]和thread_2映射[4, 5, 6]，两个线程的最终结果仍然是[2, 4, 6, 8, 10, 12]，但我们有减半这个处理时间。减少操作也是如此，并且是MapReduce在并行计算中的工作原理。

Answer 9

这是我找到的最简单的MapReduce解释。

我解释画面较小，较简单的它仍然是。