用python辅助理解mapreduce的sort排序

概念简介

map 含义是映射，即把一个值A变成另一个值B，这里的是B往往是被压缩后的信息。
比如要从一组字符串中找出最长字符串，那么我需要先计算每个字符串的长度，那么这里的长度，就是把字符串（值A）变成整数表示的长度（值B）。
reduce 含义是归约，即把多个值合并在一起。比如第一步map得到了很多个单词的出现次数：apple 3, sugar 5, apple 4, fox 1，那么 reduce 就是进一步聚合为： apple 7, sugar 5, fox 1 这就是最后结果。

极简代码

以经典的 word counter 模型作为例子来展示一下 map reduce 的过程。这里用可读性很好的 python 语言来实现。

map 实现

#! /usr/bin/python3
"""map"""

import sys

for line in sys.stdin:
    line = line.strip()
    words = line.split()
    for word in words:
        print ('%s\t%s' % (word, 1))

从标准输入读数据，可以是一行或者多行。那么发生了什么映射呢？这里只是简单地把单词转成了个数，由于一个单词就是1个，因此这里每个单词都映射成了常量 1 。

reduce 实现

#!/usr/bin/python3

"""reduce"""

import sys
current_word = None
current_count = 0
word = None

for line in sys.stdin:
    line = line.strip()
    # 解析来自 map 的输出
    word, count = line.split('\t', 1)
    # 处理异常值，个数不是数字的忽略
    try:
        count = int(count)
    except ValueError:
        continue
    # 这里之所以用这种“游标”方式进行处理，下面会详细解释
    if current_word == word:
        current_count += count
    else:
        if current_word:
            print('%s\t%s' % (current_word, current_count))
        current_count = count
        current_word = word
if current_word == word:
    print ('%s\t%s' % (current_word, current_count))

仍然从标准输入读取数据。我们拿到 map 的形如 ('word', 1) 的输出后，对其进行聚合后输出。
一般情况，聚合一些键的做法是这样：

data = [('foo', 2), ('bar', 3), ('foo', 1), ('zoo', 5)]
result = {}
for key, value in data:
    if key not in result:
        result[key] = value
    else:
        result[key] += value
print(result)

这个做法对于小数据量很高效。但是这个有个判断 key 是否存在的过程。
也就是说，我需要临时保存所有的 key, value。如果我的键非常多，可能内存就装不下了。
如果放入硬盘，那么查询 key 是否存在的速度就太慢了。

因此 hadoop 采用了 sort 的方式解决这个问题。这样一来，只要 key 还是同一个，就只管加就好；直到 key 改变了，才输出另一个键。就忽略了判断 key 是否存在这一步。这里的代价就是排序本身也是需要耗资源的。

现在来测试一下我们的 map reduce 模型：

➜  echo 'foo bar foo foo zoo zoo' | ./map | ./reduce            
foo     1                                                             
bar     1                                                             
foo     2                                                             
zoo     2                                                             
➜  echo 'foo bar foo foo zoo zoo' | ./map | sort | ./reduce     
bar     1                                                             
foo     3                                                             
zoo     2

不难看出，如果没有 sort 这一步，reduce 的聚合就不够彻底了。

最后编辑于：2020.07.06 18:34:52