（转载）hadoop mapreduce算法设计
class Mapper2: method Initialize3: H = new AssociativeArray4: method Map(docid a; doc d)5: for all term t in doc d do6: H{t} = H{t} + 1 . //Tally counts across documents7: method Close8: for all term t in H do9: Emit(term t; count H{t})1: class Reducer2: method Reduce(term t; counts [c1; c2; : : :])3: sum = 04: for all count c in counts [c1; c2; : : :] do5: sum = sum + c6: Emit(term t; count sum)
从上面使用“In-Mapper Combining”的伪码中可以看出，Mapper中的不只是有map 一个方法，而是增加了Initialize 和Close 方法。即我们之前说的每个Mapper执行过程中在开始和结束都可以有一段程序自定义代码，来确定每个Mapper 和Reducer 在执行之前和结束后的动作。这里对应Hadoop 中的方法是：setup 和 cleanup 方法。
下面对该算法分析：在每个Mapper 启动的时候会有一个关联数组的产生。在执行每个Map方法执行完时，并不直接写回磁盘，而是将单词加入到关联数组中，在整个Mapper执行完后才将所有单词写回磁盘(Close方法完成)。对应数单词的例子来说，每个Mapper不是在每篇文档处理完后写回磁盘的，而是每个Spiltter 的10篇文档处理完后，才一次性写回磁盘。这样中间结果相比直接使用Combiner就更少。
1.2 Combiner 和 in-Mapper Combining的优缺点[u][/u]
In-Mapper Combining 虽然比Combiner 有更少的中间结果。但是它有几个缺点。首先它破坏了MapReduce 编程模式的基础，因为保存中间结果跨越了多个Key/Value。如果说为了效率，我们不刻意的去追求模式。但是对于一些特定的算法它是不合适使用，比如某些算法要求对Map方法处理的Key/Value的中间结果先后有要求，那么这种In-Mapper Combining 是不适应的。另一个重要的缺点是In-Mapper Combining 对拓展性提出了挑战。以数单词为例，假设Mapper处理的10篇文档很大设计到很多的单词，这样关联数组势必会非常大，又可能大到一个JVM不能完全存储这个关联数组。这样拓展性会遇到挑战。
对于第二个缺点，我可以采用定期写回磁盘的方法来解决。
Combiner 和In-Mapper Combining 有除了减少中间结果外，还可以减小分布的倾斜度。比如在数单词的例子中，一些常用的单词，可能会有很多的中间结果，以至于处理这些常用单词的Reducer 会比其他的Reducer 慢很多，这种Reducer拖后腿的现象在MapReducer经常出现，而Combiner 和In-Mapper Combining的使用有助于减少这种情况。
