再见Hadoop MapReduce,

欢迎TupleMapReduce的到来

导读：这篇文章我们先回顾了Google设计的MapReduce并行编程模型，指出了其优缺点。然后，我们介绍了一种新的并行编程模型——Tuple MapReduce, 它是对传统MapReduce模型的扩展，克服了其不足。本文我们介绍了Tuple MapReduce的概念和特点，并用实例阐述了其优势，最后讨论了其实现问题。

为了解决大数据处理的并行计算问题，Google设计了MapReduce并行编程模型， 并于2004年发表论文：[“MapReduce： Simplified Data Processing on Large Clusters”]。 MapReduce来源于函数式编程的Map, Reduce概念，Map是映射，Reduce是归约。Hadoop用java开源实现了MapReduce模型。

如今，Hadoop、MapReduce已经成为许多公司、研究机构和高校广泛采用的开源工具。一方面，Hadoop的广泛应用使得许多相关的数据处理工具和应用如雨后春笋般地出现，形成了Hadoop生态系统。另一方面，这催生了一些专门培训程序员使用Hadoop的公司，例如Cloudera。 这些应用工具和公司成功的原因主要有两点，一是MapReduce模型具有较高的学习门槛，二是MapReduce和Hadoop框架从设计实现到解决实际问题还有很大一段距离。如果你作了实际的hadoop
MapReduce处理，你很快就会意识到手动编写MapReduce代码是多么痛苦的一件事情。

MapReduce

Google提出的MapReduce模型可以被定义为：

MapReduce并行计算模型使用Map方法来处理诸如(key,value)这样的数据，并生成中间形式的(key,value)对，然后再使用 Reduce方法合并所有相同key的中间(key,value)对生成最终结果。

“MapReduce的核心概念是把输入的数据分成不同的逻辑块，Map作业首先对每一块进行独立而并行的处理。这些独立的处理块的结果会被重新组合成不同的排序的集合，这些集合最后由Reduce作业进行处理。”

MapReduce不足

使用MapReduce来解决像“word count”这种经典的小问题是完全没有问题的。 但是，对于许多现实中的真实问题，利用MapReduce模型来编码解决是极其复杂的。关于这点，读者可以参看这篇文章“Hadoop MapReduce API的不足”。

“由于MapReduce被视为是一种低级范式， 一种克服 MapReduce不足的方式就是在它上层开发更直观、更易于使用的高级工具。而另一种解决 MapReduce不足的方式就是直接改写它。”

如果重新定义MapReduce模式，克服其最初设计的不足，那么很多问题就会迎刃而解了。建立在其上的高级工具也会相应的更容易设计实现了。

Tuple MapReduce

现在我们来看看MapReduce模型的一种扩展形式——Tuple MapReduce，它可以形式化地定义为：

其中，map方法处理输入的一组数据(i­₁,…,i_m)，并生成若干中间元组链表list((v­₁,…,v_n))，这些中间数据被分组合并后传递给reduce方法处理。中间元组由n个域组成，其中“g”个域用来分组，“s”个域用来排序得到新的元组链表。下图示意说明了排序与分组合并是怎样进行的：

在reduce方法中，其接收到的每个元组格式为：(用于分组的“g”个域(v­₁,…,v_g), 分组合并后按照“s”个域排序的链表list((v­₁,…,v_n))。例如，一个表需要按照原来数据的前面“g”个域来分组，分组的数据按照原来数据的前“s”个域排序。最后，reduce将处理这些分组合并后的元组，生成新元组作为最终结果list((j­₁,…,j_l))。

“为了能够处理任意个数域的数据，Tuple MapReduce扩展了MapReduce的思想。为了使reduce方法收到的元组仍具有特定的规则，它规定了如何排序和合并中间生成元组。在具有多数据域的数据处理应用场合，Tuple MapReduce简化了编程。”

实例

在Google的MapReduce论文中，我们只能找到像“word count”这些简单的特例的伪代码。但是，正如我们前面叙述的，如果采用MapReduce模型来解决实际问题是很困难的。很多实际问题比较复杂，经常会涉及到混合数据，像图表，或者需要按照某些特定方式来对数据进行合并和排序。我们来看个例子。

假设我们有一个日志，它记录了每个URL的访问记录——URL: [“url”, “date”, “visits”] 。 现在我们想根据这个日志来计算在某日期前的每个URL的访问次数。 基于MapReduce模型，用户可以写一个类似如下的伪代码程序：

但是，如果用户采用Tuple MapReduce模型来实现的话，程序就将简化为如下形式：

这里map方法相当简单：它直接发送出正在处理的记录就行了。因为不需要创建key和value， 直接生成一个多域 （3个数域）的元组很容易。 Tuple MapReduce模型将对访问数据根据“url，date”排序，根据“url”合并。因此，reduce接收到的每个URL的合并记录都是依据“date”排序的。

其中reduce方法为每个URL创建一个访问累加器。对于URL组内的每个记录，reduce对其的访问次数进行累加，然后返回这个URL到需要查询的“date”的累加访问次数。

“类似这个例子的应用还包括：计算连续间隔时间内的访问增长量， 计算移动平均数（例如某个日期前30天内的平均访问次数），计算不同时间段的访问次数（年，月，周）。 现在所有这些应用都相当普遍，而且也很难使用MapReduce来编码简单、易扩展的方案。在这个博文blog里，你可以看到关于这种复杂性的例子。”

Tuple-Join MapReduce

目前，我们知道并行数据处理中相当普遍的模式就是多个异构数据源的joining。这个问题并没有被经典MapReduce模型所解决。Tuple MapReduce与生俱来便支持多个异构数据源的join。就拿两个数据源举例，我们可以将Tuple MapReduce中的join定义为以下简化的方式：

对于多个异构数据源，多个map分别生成中间数据元组，然后对所有数据源生成的中间数据元组，依据前缀“g”个域来分组。reduce接收到的分组合并后的元组将包含多个数据源的链表：每个数据源一个链表list。这些链表将根据不同数据源自身定义的不同规则来排序。

普适化

我们可以认为TupleMapReduce是MapReduce模型的扩展。MapReduce可以看作是Tuple MapReduce的一种特例。只不过MapReduce只处理仅有两个域的元组，并限定依据元组的第一个域（“key”）来合并和排序。而Tuple MapReduce可以处理具有多个数据域的元组，并且可以根据不同个数的域来分组合并。

所以我们需要强调的是，TupleMapReduce可以做任何MapReduce能做的事情，并且可以大大简化我们对并行数据处理的理解和编码实现。

实现

基于目前任何形式的MapReduce架构，Tuple MapReduce都可以在其上很容易的实现，并且不涉及改变系统分布式处理和协作方式，仅仅只改变了用户与系统的交互方式。

结论

这篇文章中我们介绍了一种新的MapReduce模型——TupleMapReduce，并且我们阐述了其特点与优势。而且为了支持不同数据源之间的joins操作，我们将其普适化了。 Tuple MapReduce可以支持目前MapReduce的任何功能，并且简化了其学习和使用。

我们相信Tuple MapReduce不久就会被实现，并且它将代替原始MapReduce模型。目前，
Datasalt正在致力于实现Tuple MapReduce版的Hadoop，不久就会对社区开源。（邓维/编译）