如何简单解释 MapReduce 算法

算法 MapReduce| 2014-11-07

在Hackbright做导师期间，我被要求向技术背景有限的学生解释MapReduce算法，于是我想出了一个有趣的例子，用以阐释它是如何工作的。

MapReduce算法例子

你想数出一摞牌中有多少张黑桃。直观方式是一张一张检查并且数出有多少张是黑桃。

MapReduce方法则是：

给在座的所有玩家中分配这摞牌
让每个玩家数自己手中的牌有几张是黑桃，然后把这个数目汇报给你
你把所有玩家告诉你的数字加起来，得到最后的结论

MapReduce算法背景

谷歌在2004年发表了可以分析大量数据的MapReduce算法。每当你听到“大数据”这个词时，它指的是因为太大而让仅仅一台机器难以有效存储或分析的问题。MapReduce通过把计算量分配给不同的计算机群，能够解决大部分和大数据有关的分析问题。Hadoop提供了最受欢迎的利用MapReduce算法来管理大数据的开源方式。现今MapReduce是主流。

所以通常来说，每当你听到“大数据”，那也许意味着Hadoop被用来存储数据，也通常意味着数据的抽取和检索是用的MapReduce。

拆分MapReduce算法

MapReduce合并了两种经典函数：

映射（Mapping）对集合里的每个目标应用同一个操作。即，如果你想把表单里每个单元格乘以二，那么把这个函数单独地应用在每个单元格上的操作就属于mapping。
化简（Reducing ）遍历集合中的元素来返回一个综合的结果。即，输出表单里一列数字的和这个任务属于reducing。

重新审视上面的MapReduce算法例子

重新审视我们原来那个分散纸牌的例子，我们有MapReduce数据分析的基本方法。友情提示：这不是个严谨的例子。在这个例子里，人代表计算机，因为他们同时工作，所以他们是个集群。在大多数实际应用中，我们假设数据已经在每台计算机上了 – 也就是说把牌分发出去并不是MapReduce的一步。（事实上，在计算机集群中如何存储文件是Hadoop的真正核心。）

通过把牌分给多个玩家并且让他们各自数数，你就在并行执行运算，因为每个玩家都在同时计数。这同时把这项工作变成了分布式的，因为多个不同的人在解决同一个问题的过程中并不需要知道他们的邻居在干什么。

通过告诉每个人去数数，你对一项检查每张牌的任务进行了映射。你不会让他们把黑桃牌递给你，而是让他们把你想要的东西化简为一个数字。

另外一个有意思的情况是牌分配得有多均匀。MapReduce假设数据是洗过的（shuffled）- 如果所有黑桃都分到了一个人手上，那他数牌的过程可能比其他人要慢很多。

如果有足够的人的话，问一些更有趣的问题就相当简单了 – 比如“一摞牌的平均值（二十一点算法）是什么”。你可以通过合并“所有牌的值的和是什么”及“我们有多少张牌”这两个问题来得到答案。用这个和除以牌的张数就得到了平均值。

对MapReduce算法的结论

MapReduce算法的机制要远比这复杂得多，但是主体思想是一致的 – 通过分散计算来分析大量数据。无论是Facebook、NASA，还是小创业公司，MapReduce都是目前分析互联网级别数据的主流方法。有趣的是，MapReduce在多于10PB数据时趋向于变慢，所以谷歌在他们今年的IO大会上报告称MapReduce已经不够他们用了。