问题：MapReduce计算均衡难题解决方法

当前现状：
当前MapReduce的实现可能会发生将大量的KEY聚合到一起，结果是在reduce时导致大量数据压向其中少数节点，破坏了reduce节点间的均衡性，当数据量达到一定程度时，reduce节点将无法完成计算任务，从而导致整个Job失败，而且需要人工干预去恢复集群的正常运行。
改进方案：
针对目前的，核心改进可聚焦到map->reduce过程中，怎样保证map的输出到reduce是均衡或合理的。要做到再均衡，前提条件是要了解KEY的分布情况，而单个map节点的分布情况是不够的，所以必须有JobTracker参与，所有map节点的KEY分布情况都上报给JobTracker，由JobTracker来剖析KEY的分布情况，并对KEY分布情况进行调整，然后才发起Reduce操作。

回复 1# hadoopor
改进方法带来的一个：同一个job的reduce和map将无法并行，而按目前的方式，reduce过程中的数据下载是可以和map并行的，而且有些job的reduce和map可并行，所无状态的计数类job。

我先提几点:
1 直接利用KEY值分布，如果key比较长比如点击流日志中的一段，比较起来不是非常麻烦么，效率会很低的。
2 可以利用现有hadoop的研发思路来解决，因为从0.20.0开始客户端程序已经不允许设置map的数量了，完全是根据自身的分割和其他参数的设置来决定map的数量，paritition也一样不再提供给外部设置接口就好了，运用默认的partition类。
3 partition类的改造，这个算法再议吧。

在map处理完之后的数据分割之前由于每个数据的计数是完全未知的，我们采取啥样的预处理措施都是有漏洞的

比如key=“qiang” key等于这个值的数据有多少条完全未知，当第一条key="qiang"的key/value对写到partition某台机器那么以后的每次partition是肯定要分割在这台机器上的，如果他有5w条,其他的才5条，我们做了这个优化也没有意义啊。

回复 4# alexanderdai
如果不了解KEY的分布情况，是没法去修改partitioner的。新引入的缺陷确实如上所述，必须等所有map完成之后才可以，但这个代价是值得的，因为实际中，我们需要提高所有job的响应时间，这样多JOB并行时，这个缺陷就不是了。而计算KEY的分布也是有技巧的，因为KEY数量可能非常庞大，所以可以只取前几个大的KEY，大实际优化时肯定会比我说的复杂，需要好的算法去做这事，不能误判。上报给JobTracker的KEY分布信息，也不是说要上报所有KEY的，这样是不现实的。

回复 5# alexanderdai
实际优化时，肯定比我阐述的要复杂，我们得考虑你所提出的，但是基于上面的思路应当是可以将些一一解决的。

用多重hash，一定程度上可以避免skewness
比如用三个不同hash function的和 再来hash一遍 ，这样下来的hash value一定程度上可以均匀一些

回复 8# sigmod
这个确实也是一个办法，但应用场景有限，可以用来解决不同KEY个数多，但单一HASH结果聚集的，对于不同KEY个数少仍无法解决。

本帖最后由 sigmod 于 2009-12-2 15:43 编辑
回复 9# hadoopor
对于不同key少，但仍有skyness的：
1. 如果应用场景的aggregation是distributive （比如 sum, avg）的，可以利用Combine做local aggregation，这样Map-Reduce之间的I/O开销就会大幅减小
2. 如果应用场景的aggregation是holistic的 (比如 求高手中值)，  理论上说 没有改进的可能，同一个key的 reduce操作必须在同一个节点上运行