每周学点大数据 | No.37字数统计

No.37期

字数统计

Mr. 王：我们来看几个 MapReduce 应用的实际例子，这样更有助于你对它的认识。

小可：我也迫不及待地想试试 MapReduce 的应用了。

Mr. 王：先讲一个最基本的应用——字数统计。这个例子与前面的字母计数是非常相似的，只不过这里要统计的是单词数目。现在我们来更具体地说说，它的 Map 和 Reduce 是如何进行设计的。

Mr.王拿出一块白板，在上面写下了一段代码，说：这里有一段代码，它实现的就是字数统计的 Map 和 Reduce，它并不复杂。

可以看出，这个 Map 函数的输入是文档编号和相应的文档； Reduce 函数的输入是文档中出现的某一个单词和其频度统计。在这个算法中， Map 和 Reduce 的执行逻辑其实也是很简单的。

Map 函数将一个文档打开，每遇到一个单词，就发送 < 单词 ,1> 这样的一个元组。也就是说，每当 Map 函数发现了某个单词时，它就报告自己发现的这个单词是什么，同时希望 Reduce 函数在这个单词的计数上加 1。

而 Reduce 函数将整理来自所有 Map 的结果，并将相同的单词对应的这些“ 1”进行累和，输出该单词和统计频度。

你来说说，这个算法的缺陷在哪里？

小可看了看面前的白板，说：我觉得这个 Map 函数太简单了，发现一个单词就传输一个 1出去，这样就会有大量的时间都消耗在了传输这些 1 上面，每有一个单词就要传输一次，效率太差了。

Mr. 王：应怎么改进？

小可：能不能让 Mapper 在内部对某个单词的频度进行一个统计，使其可以存储一些中间结果，而不是急着把它们发送出去呢？

Mr. 王开始擦除白板上的算法，说：我们来看一个改进版本。

小可：这个改进版本多了一个数组 H，可以对单词 t 进行内部统计，在输出结果之前，将相同的单词在这篇文章里出现的次数进行了合并。

原来是出现 100 次单词就要发送 100 条记录，现在只需要发送 1 条记录就可以了，这样的确极大地减小了在网络中传输的数据量。

Mr. 王：这里有一个问题，当我们采用了这个改进版本的 Mapper 时，是不是还需要使用combiner 呢？

小可：我觉得不需要了吧，统计工作已经由 Mapper 做了。

Mr. 王：不对， combine 依然是需要的。我们注意看这个版本 Mapper 的描述，它中间有一句是“ for all term t ∈ doc d”，这意味着它运行时虽然会将来自一个文档的相同词汇及时合并。

但是一个 Mapper 可能会去处理很多个文档，而我们定义的这个 Mapper 是不能将来自多个文档的相同词汇进行合并的，比如在 doc1 中，我们发现单词 t 出现了 100 次，在 doc2 中出现了200 次，这个 Mapper 就会发出 2 条记录。

不难发现，对于一个单词 t 最终还是发出多条记录，当文档非常多时，发出的记录也就非常多，这对于通信来说依然会造成很大的力。

所以我们还要继续改进：

Mr. 王：我们来看看这个最终版本，这里有什么不同呢？ Mapper 把数组声明成了一个全局的量， Mapper 在其整个运行过程中，不论它在处理哪一个文档，都能访问到这个数组。

也就是说，在 Mapper 运行的过程中，只要对应的是一个单词，不论它来自哪一个文档，都可以将其加入到单词在数组中的频度记录中去，这就实现了 Mapper 在其处理的所有文档中对单词统计量的合并。

最后，当 close 函数被执行时， Mapper 会将整理好的数据发送出去。

小可：那么这个时候，是不是可以彻底地取消 combiner 了呢？

Mr. 王：是的。此时 combine 操作的所有工作都已经被 Mapper 实现了，能聚集的已经被Mapper 都聚集了。这种设计模式叫作本地聚合，或者叫作 In-Mapper。

这种做法就是希望将combine 操作都集成到 Mapper 中去，它保持了多个 Mapper 调用中的状态。

这样做的好处就是，如果 Mapper 不去做这种 In-Mapper 化处理，而是直接将大量的 <term,1> 输出出去，指望着 combiner 去完成聚合工作，那么每一个 Mapper 就会有大量的数据输出。

可以想象，这个数据量会非常大，是很容易超过内存缓冲区大小的，一旦内存空间被占满，数据就不得不被缓冲到磁盘上，当 combiner 要调用这部分内容时，就要从磁盘上把这部分缓冲数据取出来，这就造成了两次磁盘 I/O。

我们也知道，磁盘 I/O 的速度相比内存读写慢得太多了，这是非常影响系统运行效率的。通过引入这种 In-Mapper 模式，可以有效地将工作转变为内存操作，相比初始的版本效率高了很多。

小可：不过设计一个好的 In-Mapper 也是挺需要设计者功夫的啊。

内容来源：灯塔大数据