211

除了“如何使用 MapReduce 计算长文本中的单词”任务之外,我想不出任何好的例子。我发现这并不是让其他人了解该工具的强大功能的最佳示例。

我不是在寻找代码片段,实际上只是“文本”示例。

4

4 回答 4

311

Map reduce 是一个为高效处理大量数据而开发的框架。例如,如果我们在数据集中有 100 万条记录,并且它以关系表示形式存储 - 派生值并对这些值执行任何类型的转换都是非常昂贵的。

例如,在 SQL 中,在给定出生日期的情况下,要找出一百万条记录中有多少人的年龄 > 30 岁将需要一段时间,而且当查询的复杂性增加时,这只会按数量顺序增加。Map Reduce 提供基于集群的实现,其中数据以分布式方式处理

这是一篇维基百科文章,解释了map-reduce所有内容

另一个很好的例子是通过 map reduce 找朋友可以成为理解这个概念的一个强有力的例子,也是一个很好的用例。

就个人而言,发现这个链接对于理解这个概念非常有用

复制博客中提供的解释(以防链接失效)

寻找朋友

MapReduce 是最初由 Google 开发的框架,允许跨多个域轻松进行大规模分布式计算。Apache Hadoop 是一个开源实现。

我将忽略细节,但归结为定义两个函数:map 函数和 reduce 函数。map 函数接受一个值并输出键:值对。例如,如果我们定义一个 map 函数,它接受一个字符串并输出单词的长度作为键,输出单词本身作为值,那么 map(steve) 将返回 5:steve 而 map(savannah) 将返回 8:savannah . 您可能已经注意到 map 函数是无状态的,只需要输入值来计算它的输出值。这允许我们针对值并行运行 map 函数,并提供了巨大的优势。在我们进入 reduce 函数之前,mapreduce 框架通过键将所有值组合在一起,因此如果 map 函数输出以下键:值对:

3 : the
3 : and
3 : you
4 : then
4 : what
4 : when
5 : steve
5 : where
8 : savannah
8 : research

它们被分组为:

3 : [the, and, you]
4 : [then, what, when]
5 : [steve, where]
8 : [savannah, research]

然后,这些行中的每一行都将作为参数传递给 reduce 函数,该函数接受一个键和一个值列表。在这种情况下,我们可能会试图找出存在多少特定长度的单词,因此我们的 reduce 函数将只计算列表中的项目数并输出具有列表大小的键,例如:

3 : 3
4 : 3
5 : 2
8 : 2

减少也可以并行完成,再次提供了巨大的优势。然后我们可以查看这些最终结果,发现我们的语料库中只有两个长度为 5 的单词,等等……

mapreduce 最常见的例子是计算语料库中单词出现的次数。假设您有一份互联网副本(我很幸运能够在这种情况下工作),并且您想要一份互联网上每个单词的列表以及它出现的次数。

您解决此问题的方法是标记您拥有的文档(将其分解为单词),并将每个单词传递给映射器。然后,映射器会将单词连同1. 分组阶段将获取所有键(在本例中为单词),并列出 1。然后,reduce 阶段获取一个键(单词)和一个列表(每次该键出现在 Internet 上时的 1 列表),并对列表求和。然后reducer 输出这个词,以及它的计数。当一切都说完后,您将拥有互联网上每个单词的列表,以及它出现的次数。

容易,对吧?如果您曾经读过 mapreduce,那么上面的场景并不是什么新鲜事……它是 mapreduce 的“Hello, World”。因此,这是一个真实世界的用例(Facebook 可能会或可能不会实际执行以下操作,这只是一个示例):

Facebook 有一个朋友列表(请注意,朋友在 Facebook 上是双向的。如果我是你的朋友,你就是我的)。他们也有大量的磁盘空间,每天处理数亿个请求。他们决定在可能的情况下预先计算计算以减少请求的处理时间。一个常见的处理请求是“你和乔有 230 个共同的朋友”功能。当您访问某人的个人资料时,您会看到您的共同好友列表。该列表不会经常更改,因此每次访问配置文件时都重新计算它会很浪费(当然您可以使用不错的缓存策略,但是我将无法继续为这个问题写关于 mapreduce 的文章)。我们将使用 mapreduce 以便我们可以计算每个人 s 共同的朋友每天一次并存储这些结果。稍后它只是一个快速查找。我们有很多磁盘,很便宜。

假设好友存储为 Person->[List of Friends],那么我们的好友列表为:

A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D

每行都是映射器的参数。对于好友列表中的每个好友,映射器都会输出一个键值对。关键将是与此人一起的朋友。该值将是朋友列表。密钥将被排序,以便朋友按顺序排列,导致所有朋友对都去同一个减速器。这很难用文字来解释,所以让我们这样做,看看你是否能看到模式。在所有映射器运行完毕后,您将拥有如下列表:

For map(A -> B C D) :

(A B) -> B C D
(A C) -> B C D
(A D) -> B C D

For map(B -> A C D E) : (Note that A comes before B in the key)

(A B) -> A C D E
(B C) -> A C D E
(B D) -> A C D E
(B E) -> A C D E
For map(C -> A B D E) :

(A C) -> A B D E
(B C) -> A B D E
(C D) -> A B D E
(C E) -> A B D E
For map(D -> A B C E) :

(A D) -> A B C E
(B D) -> A B C E
(C D) -> A B C E
(D E) -> A B C E
And finally for map(E -> B C D):

(B E) -> B C D
(C E) -> B C D
(D E) -> B C D
Before we send these key-value pairs to the reducers, we group them by their keys and get:

(A B) -> (A C D E) (B C D)
(A C) -> (A B D E) (B C D)
(A D) -> (A B C E) (B C D)
(B C) -> (A B D E) (A C D E)
(B D) -> (A B C E) (A C D E)
(B E) -> (A C D E) (B C D)
(C D) -> (A B C E) (A B D E)
(C E) -> (A B D E) (B C D)
(D E) -> (A B C E) (B C D)

每行将作为参数传递给减速器。reduce 函数将简单地与值列表相交,并输出与相交结果相同的键。例如,reduce((AB) -> (ACDE) (BCD)) 将输出 (AB) : (CD) 并表示朋友 A 和 B 有 C 和 D 作为共同朋友。

减少后的结果是:

(A B) -> (C D)
(A C) -> (B D)
(A D) -> (B C)
(B C) -> (A D E)
(B D) -> (A C E)
(B E) -> (C D)
(C D) -> (A B E)
(C E) -> (B D)
(D E) -> (B C)

现在当 D 访问 B 的个人资料时,我们可以快速查找(B D)并看到他们有三个共同的朋友,(A C E)

于 2012-09-11T18:37:24.077 回答
27

类 Hadoop 的 MapReduce 实现的最佳示例之一

请记住,尽管它们仅限于 MapReduce 思想的基于键值的实现(因此它们的适用性受到限制)。

于 2012-09-11T20:57:16.243 回答
5

您可以在 MapReduce 中执行的一组熟悉的操作是一组正常的 SQL 操作:SELECT、SELECT WHERE、GROUP BY 等。

另一个很好的例子是矩阵乘法,你传递一行 M 和整个向量 x 并计算 M * x 的一个元素。

于 2012-09-11T18:36:51.690 回答
3

我不时向人们展示 MR 概念。我发现人们熟悉的处理任务,然后将它们映射到 MR 范例。

通常我会做两件事:

  1. 分组依据/聚合。在这里,洗牌阶段的优势是显而易见的。洗牌也是分布式排序的解释+分布式排序算法的解释也有帮助。

  2. 连接两个表。使用 DB 的人熟悉这个概念及其可伸缩性问题。展示如何在 MR 中完成。

于 2012-09-12T09:49:12.220 回答