算法002 MapReduce, TeraSort

MapReduce通常用于处理大于1TB的数据, 比如说Word Count

Input, Split, Map, Shuffle, Reduce 和 Finalize

Split: 把数据以任务的形式, 分配给不同的机器，这一步非常简单

Map: 把需要统计的数据存起来

Reduce: 对已有的数据进行统计，简单的代码如下

Shuffle: Map Reduce中最关键的一步, 要把Map中的值统计在一起，分到制定的Reducer中

这里Shuffle通常可以由 Hash Partition来做，把每个单词Hash后，均匀地分布在不同的Worker中，然后根据Hash的值再找到Worker来Reduce. 这样的好处是给每个Worker的分布比较均匀。

相关问题：

1.找出1TB data中，2 sum的对数。

在这里, Shuffle的时候可以将能够组成target value的pair直接map到同一个reducer上，然后每个reducer做local two sum。

比如： A + B = target, 其中有一个一定小于 2/target, 那么, A的hashcode就是自己，而B的hashcode是target - B == A, 那么就会被分配到同一个Reducer中.

假设A = 49，那么A / 50 = 49, 而B的HashCode则是(100 - 51) / 50 = 49,那么两个数就被分到同一个Reducer中去了

2.Inverted Index:

根据字母的来进行hash

3.Group Anagrams

把所有的单词按照字母重排，找出anagrams，然后把anagrams进行hash

TeraSort之后再讲吧
https://blog.csdn.net/trend_h/article/details/95625381