好MapReduce的例子

除了“如何使用MapReduce来计算长文本中的文字”任务之外,我想不出任何好的例子。 我发现这不是给他人这个工具有多强大的印象的最好例子。

我不在寻找代码片段,真正的只是“文本”的例子。

Map Reduce是一个为高效处理大量数据而开发的框架。 例如,如果我们在一个数据集中有一百万条logging,并且它存储在一个关系表示中,那么派生值和执行任何types的转换都是非常昂贵的。

例如在给定出生date的SQL中,为了找出一百万条logging中有多less人年龄大于30岁需要一段时间,并且只有在查询复杂度增加时才会增加。 Map Reduce提供了一个基于群集的实现,其中数据以分布式方式进行处理

这是一个维基百科的文章,解释了map-reduce的全部内容

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

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

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

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

寻找朋友

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

我会详细介绍这些细节,但是可以定义两个函数:一个map函数和一个reduce函数。 map函数获取一个值并输出key:value对。 例如,如果我们定义一个map函数,它接受一个string并输出单词的长度作为关键字,单词本身作为值,那么map(steve)将会返回5:steve和map(savannah)会返回8:savannah 。 您可能已经注意到map函数是无状态的,只需要input值来计算它的输出值。 这使我们可以并行运行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] 

这些行中的每一行都将作为parameter passing给reduce函数,该函数接受一个键和一个值列表。 在这种情况下,我们可能试图找出有多less个特定长度的单词存在,所以我们的reduce函数只会计算列表中的项目数,并输出列表大小的关键字,如下所示:

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

减排也可以同时进行,同样提供了巨大的优势。 然后,我们可以看看这些最终结果,并看到在我们的语料库中只有两个长度为5的单词…

mapreduce最常见的例子是统计一个语料库中词的出现次数。 假设你有一个互联网副本(我已经有幸在这种情况下工作了),你想要一个互联网上的每一个单词的列表以及发生了多less次。

你会这样做的方式是标记你的文件(将其分解成单词),并将每个单词传递给映射器。 然后映射器会把这个词吐出来,并且值为1 。 分组阶段将采取所有的关键(在这个例子中的话),并列出1的列表。 然后,缩小阶段将一个关键字(单词)和一个列表(列表1(每次在互联网上出现关键字时)都列为1),并对列表进行求和。 减速器然后输出单词,以及它的数量。 当所有的事情都说完之后,你会看到互联网上每一个字的清单,以及它出现的次数。

很简单,对吧? 如果你曾经阅读过mapreduce,那么上面的场景并不是什么新东西……这是mapreduce的“Hello,World”。 所以这里是一个真实的世界用例(Facebook可能不会实际执行以下操作,只是一个例子):

Facebook有一个朋友列表(注意朋友是Facebook上的双向事物,如果我是你的朋友,那么你是我的朋友)。 他们也有很多磁盘空间,他们每天提供数以亿计的请求。 他们已经决定预先计算计算时间,以减less请求的处理时间。 一个常见的处理请求是“你和乔有230个共同的朋友”的特征。 当你访问某人的个人资料时,你会看到一个你有共同点的朋友列表。 这个列表并不经常改变,所以每次访问configuration文件时都要重新计算它是浪费的(当然,你可以使用一个像样的caching策略,但是我不能继续为这个问题写mapreduce)。 我们将使用mapreduce,以便我们每天计算每个人的共同朋友并存储这些结果。 稍后,这只是一个快速查找。 我们有很多的磁盘,很便宜。

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

 A -> BCD B -> ACDE C -> ABDE D -> ABCE E -> BCD 

每一行将是一个映射器的参数。 对于朋友列表中的每个朋友,映射器都会输出一个键值对。 关键将是与人一起的朋友。 该值将成为朋友的列表。 钥匙将被sorting,以便朋友按顺序,使所有的朋友对去相同的减速机。 这很难用文字解释,所以让我们来看看是否可以看到模式。 在完成所有映射器的运行后,您将拥有如下所示的列表:

 For map(A -> BCD) : (AB) -> BCD (AC) -> BCD (AD) -> BCD For map(B -> ACDE) : (Note that A comes before B in the key) (AB) -> ACDE (BC) -> ACDE (BD) -> ACDE (BE) -> ACDE For map(C -> ABDE) : (AC) -> ABDE (BC) -> ABDE (CD) -> ABDE (CE) -> ABDE For map(D -> ABCE) : (AD) -> ABCE (BD) -> ABCE (CD) -> ABCE (DE) -> ABCE And finally for map(E -> BCD): (BE) -> BCD (CE) -> BCD (DE) -> BCD Before we send these key-value pairs to the reducers, we group them by their keys and get: (AB) -> (ACDE) (BCD) (AC) -> (ABDE) (BCD) (AD) -> (ABCE) (BCD) (BC) -> (ABDE) (ACDE) (BD) -> (ABCE) (ACDE) (BE) -> (ACDE) (BCD) (CD) -> (ABCE) (ABDE) (CE) -> (ABDE) (BCD) (DE) -> (ABCE) (BCD) 

每行将作为parameter passing给reducer。 reduce函数将简单地与值列表相交并输出与交集结果相同的关键字。 例如,reduce((AB) – >(ACDE)(BCD))将输出(AB):( CD),意味着朋友A和B有C和D共同的朋友。

减less后的结果是:

 (AB) -> (CD) (AC) -> (BD) (AD) -> (BC) (BC) -> (ADE) (BD) -> (ACE) (BE) -> (CD) (CD) -> (ABE) (CE) -> (BD) (DE) -> (BC) 

现在当D访问B的configuration文件时,我们可以快速查找(BD) ,看到他们有三个共同的朋友(ACE)

Hadoop-like MapReduce实现的最好例子之一 。

请记住,它们仅限于MapReduce思想的基于键值的实现(所以它们在适用性上受到限制)。

在MapReduce中可以做的一组熟悉的操作是一组普通的SQL操作:SELECT,SELECT WHERE,GROUP BY等。

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

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

通常我会采取两件事情:

  1. 分组/聚合。 这里洗牌阶段的优势很明显。 洗牌也是分布式的解释+分布式sortingalgorithm的解释也有帮助。

  2. join两张表。 使用数据库的人员熟悉这个概念及其可伸缩性问题。 说明如何在MR中完成。