【翻译】运用MapReduce找到社交媒体中的共同朋友

原文：http://stevekrenzel.com/finding-friends-with-mapreduce
关于MapReduce的运用，最近阅读到的一篇文章，写的很不错，搬过来分享下。

MapReduce是一种编程模型，用于大数据（>1TB）的并行运算。对于原理可以简化为两个步骤：map（映射）方法和reduce（归约）方法。Map方法是将一个值输出为key-value的对应。比如统计一篇英文文章中某个长度有几个单词。具体思路是输入一个目标句子，那么输出就可以是以目标字符串中的一个单词长度为key，单词本身为value的map。这个map的方法没什么其它的依赖，只需要输入一个单词就可以完成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方法，即一个特定长度的key会对应一个value的list。再往深入点，我们可能会计算每个特定长度的词有多少个，于是reduce方法将会整理出如下对应关系：
3：3
4：3
5：2
8：2
综上所述就是map方法和reduce方法都可以分N个机器进行并行运算，这样在时间上的优势是很大的。经过以上步骤就分析出某个长度的词汇在文章中出现的次数了。

另一个关于MapReduce的类似例子是统计词语在文章中出现的次数。
首先要做的就是将文章中的词汇逐个转成map，key是这个词汇本身，value默认为1。然后进行分组整理，此时key还是这个词语本身，value是次数为1的集合（list），最后的reduce要做的就是合计value，即将所有的1相加，最终的输出结果就是词语-次数的map。
看起来好像很容易，以上的例子就是MapReduce的“Hello World”。来说说现实生活中的运用MapReduce的例子吧：

社交平台（例如Facebook）会有一个好友的列表（假设这个朋友关系是双向的，即A是B的好友，那么B也必须是A的好友）。平台的优势是大公司不差钱存储空间多，平台每天有几百万次的点击量，所以他们决定提前计算，从而减少请求的时间。比如你和Joe有230个共同好友，当Joe访问你的主页时，他可以看到一个共同好友的列表，这个列表可能不经常改动，所以如果每次访问都实时统计一遍实属浪费资源和时间（当然另一种解决方案是Cache）。这时候可以用mapreduce每天计算朋友之间的共同朋友，并保存下来，这样每次请求的时候就特别方法，虽然占用空间，但便宜。

Assume the friends are stored as Person->[List of Friends], our friends list is then:
假投朋友关系存储是按key-value：某个人->[朋友集合]，如下：
A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D

每一行都是一个mapper，但是上面的键值是一个朋友的List，而我们要的是两个好友之间的共同朋友，所以基于这个需求，需要将值重新拆成单个key-value的配对（当前这个人与他朋友之间的两两配对），这样就可以变成某个人和特定的朋友之间的关系了。这个健值是有顺序的（便于双向访问的时候用同一个键值，即A访问B的时候是(A B)，B访问A的时候也是(A B)），按这个逻辑来重新组合，就变成了如下结果：
For map(A -> B C D) :
(A B) -> B C D：具体说下意思：(A B) -> B C D的意思是A和B是共同好朋友->A的所有的好朋友，下同。
(A C) -> B C D
(A D) -> B C D
For map(B -> A C D E) : (注意键值是有顺序的，即A在B的前面)
(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

在将结果交给reducer进行reduce前，我们先把以上值进行分组（group）：
(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方法就是取两个集合中的交集。比如reduce((A B) -> (A C D E) (B C D))将输出(A B) : (C D)，这意味着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)。


参考：
维基百科MapReduce主页 https://en.wikipedia.org/wiki/MapReduce