从单词统计看MapReduce算法内聚合

对MapReduce统计单词出现次数在从单词统计看MapReduce一文中已经做了简单的介绍。对此给出了一个较为简单的统计算法:

Map函数

输入:(key：文档a，value：文档内容d)

输出:(key：单词t，value：单词t在文档d中出现的次数c)

H<--new ASSOCIATIVEARRAY

for all term t∈doc d do

    H{t}=H{t}+1

for all term t∈H do

    输出（t，H{t}）

这是一个最简单的算法，这个算法：

好处是简单明了；

其缺点是通信量比较大，输入中的每个单词都对应一次键值对通信。

为减少通信开销。可以添加一个combiner在不同的位置。如果加在map后面，相当于在map之后增加一个combiner，把相同单词的计数加到一起，这就可以减小通信量，减小通信开销。相当于不用传递一个单词加一个1，而是传递一个词和一个count。聚合之我们需要通过网络传输文档中全部单词所对应的键值对，聚合后中间结果的数量减少为文档中单词种类数。这样我们就得到了一个优化的版本。

其reducer部分与从单词统计看MapReduce文中的算法一样，但map实现稍微不同。在map里面使用了一个数组H，用于用每一个出现的单词计数一次。当某个单词在文档中出现一次时，它在H当中对应的项就加一。当统计结束以后，对于H当中的每一个单词w，map函数把w和w在H中对应的计数传输给reducer

进一步优化

在MapReduce中mapper/reducer运行中，对于每个map任务，都会创建一个mapper对象，在执行这个mapper对象之前，会先调用mapper对象的初始化代码，这为定义自己的预处理代码和close代码提供了途径。

考虑去掉combiner。把H变成一个全局变量，直到mapper所有的工作都结束的时候才输出H。为了说明该过程，这里分别写出了INTIALIZE函数、MAP函数和CLOSE函数。中间的步骤和算法7-2相同，仍然是对于文档中每个单词，H当中对应一项加一。

 Classs MAPPER

    Method INTIALIZE

        H=new ASSOCIATIVEARRAY

    Method MAP（文档ida，文档内容d）

        for 每个t∈d do

            H{t}=H{t}+1

    Method CLOSE

        for 每个单词t∈H do

            输出（1，H{t}）

这样，combiner的工作在mapper里面已经完成，同一个mapper对应的数据能聚合的已经聚合结束。本地聚合这种设计模式，相当于在mapper内进行聚合，可以聚合同一个mapper中多次调用map函数的计算结果。

优缺点比较

和独立的combiner相比，使用mapper内聚合有如下优点：

• 首先，它使得我们可以控制局部聚合操作的执行时间以及执行步骤

• 其次，效率更高。这是因为mapper内聚合并没有使得mapper的输出结果有什么变化，仅仅是聚合了中间结果，而mapper运行过程中产生的那些键值对的生成和销毁又是需要时间的

不过，mapper内聚合也会有以下缺点：

• 首先，mapper内聚合需要在map函数中或者Mapper类中使用中间状态，这破坏了函数式设计的准则。使用状态信息就使得运行结果可能跟数据的输入顺序有关，这可能导致隐藏的危险

• 其次，使用mapper内聚合要求可以在内存中存储mapper产生的所有中间结果，而这可能导致规模瓶颈的出现。解决这个问题的办法可以是周期性地将内存数据保存到磁盘中

在MapReduce算法设计中，局部聚合可以产生多大收益取决于中间结果键空间的规模、键本身的分布规律以及每个mapper处理的键值对数量。从本质上来说，局部聚合能产生收益是因为很多键值对的键是一样的。在上述例子中，combiner之所以可以产生收益也是因为单词可能在文本中多次出现。combiner有助于解决reducer的数据偏斜问题，它在一定程度上使得键空间分布更为匀。

更多内容可前往公众号免费获取