Map-Reduce简单理解

这两天看了下map-reduce的论文，对map-reduce有了一个大概的了解。

为什么需要map-reduce?

通常情况下，当输入数据非常大时（通常是远大于机器内存时），我们不能时间进行类似sorting或者hash等操作。为了保证任务能在理想时间内完成，需要多台机器同时运算。map-reduce提供了这样一个计算模型。

map-reduce过程

首先我们有很多台机器，机器分为三类：

master: 只有一台机器为master（也可以有两台）
map worker: 进行map操作
reduce worker: 进行reduce操作

图1

例子：假设有很多个水果，我们需要计算每种水果出现的次数。
1. 如图1所示，master会把input 分成很多份，使单台机器能够操作。通常分成的份数M，能使每份数据大小在16-62MB。
2. Map worker会把得到的data 进行key/value处理。key/value是用户根据要求自定，在这个例子中，key就是水果名称，value就是次数。
3. 对于所有map worker处理完的的结果，会存在local disk上，同时会被分成R份（R的数量一般稍大于reduce worker的数量）。完成后map worker会向master汇报存储的位置和数据大小。
4. master 会把处理好的中间数据分配给reduce worker, reduce worker 会远程读取map上的数据。首先根据数据的key 进行sorting。这样的会使所有相同key的数据在一起。之后，reduce worker 遍历上面的数据，对相同key的数据value进行累加（根据不同的reduce方程，进行的操作也不一样，此例子为累加）。
5. 最后把每个reduce worker 的处理结果写进一个final output file.


下面为一个简单的map和reduce的程序：

public void map(K key, V value, OutputCollector<K,V> output, Reporter reporter) 
                throws IOException{
    String line = value.toString();
    StringTokenizer tokenizer = new StringTokenizer(line);
    while (tokenizer.hasMoreTokens()) {
        word.set(tokenizer.nextToken());
        output.collect(word, one);
    }
}

public void reduce(K key, Iterator<V> values, OutputCollector<K,V> output, 
    Reporter reporter) throws IOException {
    int sum = 0;
    while (values.hasNext()) {
        sum += values.next().get();
    }
    output.collect(key, sum);
}