map reduce 与 MapReduce

昨天一个偶然的机会跟同事讨论了MapReduce这个产品和函数式编程中最出名的两个函数map和reduce/...



昨天一个偶然的机会跟同事讨论了MapReduce这个产品和函数式编程中最出名的两个函数map和reduce/fold之间的关系。是仅仅的名字巧合吗？还是存在着某种关系？Wikipedia对两者的关系有明确的解释：

The model is inspired by the map and reduce functions commonly used in functional programming,[6] although their purpose in the MapReduce framework is not the same as in their original forms.[7] The key contributions of the MapReduce framework are not the actual map and reduce functions, but the scalability and fault-tolerance achieved for a variety of applications by optimizing the execution engine once.

意思是说，MapReduce的名字受函数式编程中的map和reduce两个函数的名字启发，但是在MapReduce中，”map”和”reduce”不是函数式编程中的map和reduce的本意。

我们也讨论到MapReduce其实是一个Divide and Conquer的算法，那么它为什么不叫DivideConquer这个名呢？个人认为，就针对这个产品而言，DivideConquer这个名字比MapReduce逊色很多。要了解MapReduce的命名，我们需要从了解函数式编程中的map和reduce(或fold)两个函数入手。

函数式编程中的map和reduce

map和reduce是函数式编程中两个最出名，最重要的高阶函数(High Order Function)。什么是高阶函数？它和初中时学的高次（高阶）方程同属一个概念。简单来说，一个函数能被称为高阶函数，它应具备下列2个要素中的至少一点：

1. 它能接受另外一个函数作为参数
2. 它的返回值可以是另外一个函数

毫无疑问，map和reduce函数都能满足上述两点。这里又引出了另外一个概念：函数是一等公民(First-class Function)。此处“一等公民”并非指社会地位高下的概念，而是指First-class Function要求编程语言支持把函数作为参数传递或能作为另外一个函数的返回值。因此，函数式编程语言支持First-class Function，而高阶函数的整套体系是构建在其基础之上的。

那么为什么高阶函数是函数式编程的一个核心概念？因为高阶提供了高层次的抽象，而抽象是解决复杂问题（比如软件问题）的强有力工具。

世间函数千千万，那么为什么唯独map，reduce两个函数如此与众不同？这就需要我们去关注一下函数所操作的数据对象，大致可以分为两类：个体或少量几个数据；某类数据的一个集合。对于个体或少量数据，能应用于它们的函数通常各不相同，共性比较少；而可应用于集合类数据的函数，大多具有通用的模式：

• 模式一：对集合内每一个数据做某种转换处理，返回具有同等数量的不同类型集合
• 模式二：对集合内数据做累积操作，返回一个数据或另外一个不同数量的集合

很明显的，模式一可以归纳出一个名字叫”map”，即把某种“转换处理”应用到集合中的每一个元素去。而这种“转换处理”有无数种可能，因此我们把“转换处理”这个函数以参数的形式传给map这个高阶函数。

同理，模式二可以归纳出一个名字叫”reduce”，即把某种“累积操作”逐步应用到集合中的每一个元素去，并最后把累加结果返回。而这种“累积操作”有无数种可能，因为我们把函数以参数的形式传给reduce这个高阶函数。

MapReduce的命名为何对map和reduce函数情有独钟？

MapReduce是一个基于计算机集群的并行、分布式计算框架。它在很大程度上受函数式编程语言中的map和reduce所启发，对分布式计算进行高阶抽象，去除变化的部分，保留不变的框架。它认为：大多数分布式计算可以归纳为下列两种操作的多种组合：

• 对所有数据块（分布于多台计算机上）进行“某种操作”
• 对局部或所有数据块做数据“汇总操作”

看！这是多么的美妙！完全符合之前提到的两个模式。

Hadoop充分吸纳了map，reduce两个函数的精华：在集群机器间移动数据是很耗费资源的，因此它们选择移动函数，函数是一等公民的绝妙应用！

为什么是MapReduce而不是”DivideConquer”?

从本质上来说MapReduce框架属于Divide Conquer的一种。然而针对这个产品，“DividerConquer” 这个命名比MapReduce逊色很多，主要有两点：

• Divider conquer明确提出了“分而治之”的思路，却没有明确提出“汇总“这个在MapReduce产品中占1/2的思想
• MapReduce更加具体地描述了产品的工作流，属于准确的抽象—既有抽象的高可用性，又不失抽象的准确性与实用性。

打开另一个世界的大门

如果您对本文的理解存在困难，我强烈您阅读一些函数式编程的书籍和文章。相信我，一旦您掌握了它，您就打开了一扇通往另一个编程世界的大门（假如面向对象和面向过程是您已经打开的两扇大门）。门的另一侧，是一个美轮美奂的世界。

如果从来没了解过函数式编程，那么我建议您从最纯正的函数语言Haskell开始。

Learn You a Haskell for Great Good!一书妙语连珠，妙趣横生，深入浅出，有趣有料。作者自己画的插画更是生动活泼！我一直坚信：会画画的程序员是非常有前途的！(这个以后详细展开来说)。

如果您想找一本更加系统详实的Haskell书，那么看Real World Haskell吧。它介绍了Haskell语言的每一个细节，当然你要有足够的耐心和毅力。

如果您想偏理论角度地研究一下为什么高阶函数很重要，那么我推荐您看一下这篇学术文章：High Order + Polymorphic = Reuse: http://citeseerx.ist.psu.edu/showciting?cid=577419

如果您想理论性地研究一下函数式编程，那么我推荐您看一下这篇神作，神作，神作：Theorems for free：http://ecee.colorado.edu/ecen5533/fall11/reading/free.pdf 在这篇文章里您可以学到如何用lambda组合子（或Y Combinator）来实现匿名函数的递归。《黑客与画家》的作者成立的创业孵化公司Y Combinator的名字就是来源于函数式编程。（想想吧，这又是一个美妙的名字)

好吧，如果您对函数式编程的纯理论性研究感兴趣，这完全超出我的能力了，但您去看Lambda Caculus一准儿是没错的了。

    关注 代码技术与思考