时隔多日又把MapReduce这篇paper看了一遍,发现用过Python的map和reduce之后再看真是恍然大悟啊(各位Lisp/Haskell/Erlang帝就不要BS我了……)

这篇paper虽然有十几页,但组织地非常连贯清晰,一个小时就能看完。它讲的就是怎么把一个大规模计算任务分配到一群小计算机上来并行地算。基本动作只有两个:map和reduce。

啥叫map?下面这个程序就是map:

#!/usr/bin/python2

a = [1, 2, 3, 4, 5]
m = lambda x : x * x
l = map(m, a)

print list(l)
Output:
[1, 4, 9, 16, 25]

啥叫reduce?下面这个程序就是reduce:

#!/usr/bin/python2

a = [1, 2, 3, 4, 5]
r = lambda x, y : x + y
s = reduce(r, a)

print s
Output:
15

知道了这两个简单的概念,MapReduce的过程就可以用以下两个式子来说明:

\[ \text{map: } (k1, v1) \rightarrow list(k2, v2) \] \[ \text{reduce: } (k2, list(v2)) \rightarrow list(v2) \]

也就是说,map是把输入分解为一系列的key-value pair,然后有相同key的key-value pair被合并之后形成(k2, list(v2)),交给reduce形成最终的输出。

Note. 其实我觉得最初的k1和最后的list(v2)不太好理解,不如写成(仅个人看法):

\[ \text{map: } input \rightarrow list(k2, v2) \] \[ \text{reduce: } (k2, list(v2)) \rightarrow (k2, result) \]

好处是啥呢?是map和reduce分别可以并行。有一个master节点负责统一规划,它先把输入分割成若干块,交给不同的mappers进行map。在map的时候形成的key-value pair会按照一个关于key的划分函数(类似于hash(key))决定由哪个reducer进行reduce。map完毕之后reducers从mappers那里取得中间结果,sort一下,然后进行reduce。由于不同的reducers负责不同的key(指k2),所以reduce也是可以并行的。

作为最终用户,完全不必care分布式计算的细节,例如fault-tolerance, locality什么的,这些都隐含在MapReduce里面了。最终用户只需要实现map和reduce这两个函数就可以了。而MapReduce的最神奇之处就在于作者意识到多数任务都可以利用map+reduce的方式来实现。

举例说,词频统计的map和reduce就可以这样写:

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

map把整个文本拆成了一个个键值对<word, 1>,然后reduce按照word把这些1一个一个加起来,就这么简单。如果你要说这么一个一个加的话reducers到mappers那里去取数据的过程不是很浪费带宽?这作者也有考虑到,可以指定一个combiner函数在map到reduce中间先部分合并一下。combiner和reducer基本就是一样的,只是输出行为不同。

还有一些其他的优化就不说了,中文翻译总不如original好。

光棍节看MapReduce我也是醉了。。。

Links: