简单解释MapReduce？

Question

与我的CouchDB问题有关.

任何人都可以用麻栗可以理解的方式解释MapReduce吗？

Answer 1

一直到Map and Reduce的基础知识.

Map是一种功能,它将某种列表中的项目"转换"为另一种项目,并将它们放回到同一种列表中.

假设我有一个数字列表:[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)执行map函数后,你会得到[2,4,6].

Reduce是一个"收集"列表中的项目并对所有项目执行一些计算的函数,从而将它们减少到单个值.

查找总和或查找平均值都是reduce函数的实例.比如如果你有一个数字列表,比如说[7,8,9],你想要总结一下,你会写一个像这样的循环

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

但是,如果您可以访问reduce函数,则可以像这样编写它

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 2

MapReduce是一种并行处理大量数据的方法,无需开发人员编写除映射器之外的任何其他代码并减少函数.

的地图函数接受数据和批量地生产出的结果,这是在一个屏障保持.此函数可以与大量相同的map任务并行运行.然后可以将数据集缩减为标量值.

所以如果你把它想象成一个SQL语句

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

我们可以使用map来获得薪水> 1000的员工子集,这些员工将映射排放到组大小桶中.

减少将对每个组进行求和.给你你的结果集.

刚刚从我的大学学习笔记中摘录了这篇论文

Answer 3

1. 拿一堆数据
2. 执行某种转换,将每个数据转换为另一种数据
3. 将这些新数据合并到更简单的数据中

第2步是Map.第3步是减少.

例如,

1. 在路上的一对压力表上获得两次冲动之间的时间
2. 根据仪表的距离将这些时间映射到速度
3. 将这些速度降低到平均速度

MapReduce在Map和Reduce之间拆分的原因是因为不同的部分可以很容易地并行完成.(特别是如果Reduce具有某些数学属性.)

有关MapReduce的复杂但良好的描述,请参阅:Google的MapReduce编程模型 - 重访(PDF).

Answer 4

MAP和REDUCE是人类杀死最后一只恐龙时的旧Lisp功能.

想象一下,您有一个城市列表,其中包含有关姓名,居住人数和城市规模的信息:

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

现在您可能想要找到人口密度最高的城市.

首先,我们使用MAP创建城市名称和人口密度列表:

(map 'list
     (lambda (city)
         (list (first city)
               (/ (getf (rest city) :people)
                  (getf (rest city) :size))))
     *cities*)

=>   ((A 500) (B 2000/3) (C 5000/7))

使用REDUCE,我们现在可以找到人口密度最大的城市.

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

然后我们可以将MAP REDUCE代码编写为:

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

 =>   (C 5000/7)

它调用MAP和REDUCE(评估在里面),所以它被称为map reduce.

Answer 5

我们以Google论文为例.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

在那之外,你将有一个主程序,它将在"分裂"中对文档集进行分区,这些文档将在Map阶段并行处理.发出的值由worker在特定于worker的缓冲区中写入.一旦通知缓冲区已准备好处理,主程序就会委托其他工作人员执行Reduce阶段.

每个工作者输出(作为Map或Reduce工作者)实际上是存储在分布式文件系统(GFS for Google)或CouchDB的分布式数据库中的文件.

Answer 6

有关MapReduce的简单,快速和"傻瓜"介绍,请访问:http://www.marcolotz.com/？ p = 67

发布一些内容:

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

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

什么是MapReduce的真正优势？

可以说MapReduce魔术基于Map和Reduce函数应用程序.我必须承认配偶,我强烈不同意.使MapReduce如此受欢迎的主要特点是它具有自动并行化和分发的能力,并结合了简单的界面.这些因素与大多数错误的透明故障处理相加,使得这个框架如此受欢迎.

在论文上更深入一点:

MapReduce最初是在Google论文(Dean&Ghemawat,2004 - 链接此处)中提到的,作为使用并行方法和商品计算机集群在大数据中进行计算的解决方案.与用Java编写的Hadoop相比,Google的框架是用C++编写的.该文档描述了并行框架如何使用函数编程中的Map和Reduce函数来处理大型数据集.

在这个解决方案中,将有两个主要步骤 - 称为Map和Reduce - 在第一个和第二个之间有一个可选步骤 - 称为Combine.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]].在reducer中,它将对键区的所有值求和,并将以下键值作为输出:[house,[3]].

这是一个在MapReduce框架中看起来如何的图像:

作为MapReduce应用程序的一些其他经典示例,可以说:

•URL访问频率计数

•反向Web链接图

•分布式Grep

•每个主机的术语向量

为了避免过多的网络流量,本文描述了框架应该如何尝试维护数据局部性.这意味着它应该始终尝试确保运行Map作业的计算机将数据存储在其内存/本地存储中,从而避免从网络中获取数据.旨在通过放置映射器来减少网络,使用前面描述的可选组合器步骤.Combiner在给定机器中的映射器输出之前执行计算,然后将其发送到Reducers(可能在另一台机器中).

该文档还描述了框架的元素在出现故障时应该如何表现.本文中的这些元素称为工人和主人.它们将在开源实现中分为更具体的元素.由于Google仅描述了本文中的方法而未发布其专有软件,因此创建了许多开源框架以实现该模型.作为示例,可以说MongoDB中的Hadoop或有限的MapReduce功能.

运行时应该处理非专业程序员的细节,比如分区输入数据,在大型机器上安排程序执行,处理机器故障(当然是以透明的方式)和管理机器间通信.有经验的用户可以调整这些参数,如输入数据将如何在工作者之间进行分区.

关键概念:

• 容错:必须优雅地容忍机器故障.为了执行此操作,主人定期对工人进行打击.如果主人在确定的时间间隔内没有收到给定工人的回复,则主人将该工作定义为失败.在这种情况下,故障工作人员完成的所有地图任务都将被丢弃并提供给另一个可用工作人员.如果工作人员仍在处理地图或减少任务,则会发生类似情况.请注意,如果工作人员已经完成了reduce部分,则所有计算在失败时已经完成,不需要重置.作为主要故障点,如果主站发生故障,则所有作业都会失败.出于这个原因,可以为主服务器定义周期性检查点,以便保存其数据结构.在最后一个检查点和主故障之间发生的所有计算都将丢失.

• 位置:为了避免网络流量,框架会尝试确保所有输入数据在本地可用于要对其执行计算的计算机.在原始描述中,它使用Google文件系统(GFS),复制因子设置为3,块大小为64 MB.这意味着64 MB的同一块(组成文件系统中的文件)将在三台不同的计算机上具有相同的副本.主人知道块的位置,并尝试在该机器中安排地图作业.如果失败,则主设备尝试在任务输入数据的副本(即数据机的同一机架中的工作机器)附近分配机器.

• 任务粒度:假设每个地图阶段被分成M个部分并且每个Reduce阶段被分成R个部分,理想情况是M和R比工人机器的数量大很多.这是因为执行许多不同任务的工作人员可以改善动态负载平衡.除此之外,它还可以在工作人员失败的情况下提高恢复速度(因为它完成的许多地图任务可以分散在所有其他机器上).

• 备份任务:有时,Map或Reducer工作程序的行为可能比群集中的其他工作程序慢得多.这可以保持总处理时间并使其等于该单个慢速机器的处理时间.原始文件描述了一种称为备份任务的备选方案,当MapReduce操作接近完成时由主服务器安排.这些是由正在进行的任务的主计划的任务.因此,MapReduce操作在主要或备份完成时完成.

• 计数器:有时人们可能希望计算事件发生次数.因此,计算创建的位置.每个工作程序中的计数器值会定期传播到主服务器.然后,主人聚合(Yep.看起来像Pregel聚合器来自这个地方)成功的map和reduce任务的计数器值,并在MapReduce操作完成时将它们返回给用户代码.主状态中还有一个当前计数器值,因此观察该过程的人可以跟踪它的行为方式.

好吧,我想上面提到的所有概念,Hadoop对你来说都是小菜一碟.如果您对原始MapReduce文章或任何相关内容有任何疑问,请告诉我们.

Answer 7

如果您熟悉 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_1maps[1, 2, 3]和thread_2maps [4, 5, 6]，两个线程的最终结果仍然是，[2, 4, 6, 8, 10, 12]但我们已经将处理时间减半。对于reduce 操作也是如此，这也是MapReduce 在并行计算中工作的本质。