好的MapReduce示例

Question

除了"如何使用MapReduce计算长文本中的单词"任务之外,我想不出任何好的例子.我发现这不是给别人一个关于这个工具有多强大的印象的最好例子.

我不是在寻找代码片段,实际上只是"文本"示例.

Answer 1

Map reduce是一个开发用于有效处理大量数据的框架.例如,如果我们在数据集中有100万条记录,并且它存储在关系表示中 - 那么导出值并对它们执行任何类型的转换都是非常昂贵的.

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

这是一篇维基百科文章,解释了什么是关于什么的map-reduce

另一个很好的例子是通过地图查找朋友减少可以是理解概念的一个有力的例子,以及一个很好用的用例.

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

http://stevekrenzel.com/finding-friends-with-mapreduce

复制博客中提供的说明(如果链接失效)

寻找朋友

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阶段取一个键(单词)和一个列表(每次键出现在互联网上时列表为1),并对列表求和.然后减速器输出该字以及它的计数.完成所有操作后,您将获得互联网上每个单词的列表,以及它出现的次数.

容易,对吗？如果您曾经读过有关mapreduce的内容,那么上面的场景并不是什么新东西......它是mapreduce的"Hello,World".所以这是一个真实世界的用例(Facebook可能会或可能不会实际执行以下操作,它只是一个示例):

Facebook有一个朋友列表(注意朋友在Facebook上是双向的.如果我是你的朋友,你就是我的朋友).它们还拥有大量磁盘空间,每天为数亿个请求提供服务.当他们能够减少请求的处理时间时,他们决定预先计算计算.一个常见的处理请求是"你和乔有230个朋友的共同点"功能.当您访问某人的个人资料时,您会看到一个您有共同点的朋友列表.此列表不会经常更改,因此每次访问配置文件时重新计算它都是浪费(确保您可以使用适当的缓存策略,但我不能继续为此问题编写mapreduce).我们将使用mapreduce,以便我们可以每天计算一次所有人的共同朋友并存储这些结果.稍后它只是一个快速查找.我们有很多磁盘,价格便宜.

假设朋友存储为人物 - > [朋友列表],我们的朋友列表则是:

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)

每一行都将作为参数传递给reducer.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).

Answer 2

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

请记住,它们仅限于基于键值的MapReduce创意实现(因此它们在适用性方面受到限制).

Answer 3

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

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