MapReduce设计模式

版权信息

书名：MapReduce设计模式

ISBN：978-7-115-36094-6

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

•　著　　　　[美] Donald Miner Adam Shook

　 译　　　　徐 钊　赵重庆

　 责任编辑　杨海玲

•　人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

　 邮编　100164 　电子邮件　315@ptpress.com.cn

　 网址　http://www.ptpress.com.cn

•　读者服务热线：(010)81055410

　 反盗版热线：(010)81055315

内容提要

MapReduce作为一种分布式海量数据处理的编程框架，已经得到业界的广泛关注。随着Hadoop的普及，MapReduce目前已经成为海量数据处理的最基础但也是最重要的方法之一。

这是一本关于设计模式的书，为读者提供解决问题的模板或通用指南。书中主要介绍编程模式，即如何利用MapReduce框架解决一类问题，重在提供解决问题的方法和思路。作者花大量篇幅介绍各种模式的原理及实现机制，并给出相应的应用实例，让读者对每种模式能有更直观的理解。

由于本书不会过多涉及底层框架及MapReduce API，所以希望读者阅读本书之前，能够对Hadoop系统有所了解，知道如何编写MapReduce程序，并了解MapReduce程序框架的工作原理。本书面向中高级MapReduce开发者，涵盖了绝大部分MapReduce编程可能面对的场景，相信初学者和专家同样可以在本书中得到一些启示。

版权声明

Copyright ©2013 by O’Reilly Media, Inc.

Simplified Chinese Edition, jointly published by O’Reilly Media, Inc. and Posts & Telecom Press, 2014. Authorized translation of the English edition, 2014 O’Reilly Media, Inc., the owner of all rights to publish and sell the same.

All rights reserved including the rights of reproduction in whole or in part in any form.

本书中文简体版由O’Reilly Media, Inc.授权人民邮电出版社出版。未经出版者书面许可，对本书的任何部分不得以任何方式复制或抄袭。

版权所有，侵权必究。

O'Reilly Media，Inc.介绍

O’Reilly Media通过图书、杂志、在线服务、调查研究和会议等方式传播创新知识。自1978年开始，O’Reilly一直都是前沿发展的见证者和推动者。超级极客们正在开创着未来，而我们关注真正重要的技术趋势——通过放大那些“细微的信号”来刺激社会对新科技的应用。作为技术社区中活跃的参与者，O’Reilly的发展充满了对创新的倡导、创造和发扬光大。

O’Reilly为软件开发人员带来革命性的“动物书”；创建第一个商业网站（GNN）；组织了影响深远的开放源代码峰会，以至于开源软件运动以此命名；创立了《Make》杂志，从而成为DIY革命的主要先锋；公司一如既往地通过多种形式缔结信息与人的纽带。O’Reilly的会议和峰会集聚了众多超级极客和高瞻远瞩的商业领袖，共同描绘出开创新产业的革命性思想。作为技术人士获取信息的选择，O’Reilly现在还将先锋专家的知识传递给普通的计算机用户。无论是通过书籍出版、在线服务或者面授课程，每一项O’Reilly的产品都反映了公司不可动摇的理念——信息是激发创新的力量。

业界评论

“O’Reilly Radar博客有口皆碑。”

——Wired

“O’Reilly凭借一系列（真希望当初我也想到了）非凡想法建立了数百万美元的业务。”

——Business 2.0

“O’Reilly Conference是聚集关键思想领袖的绝对典范。”

——CRN

“一本O’Reilly的书就代表一个有用、有前途、需要学习的主题。”

——Irish Times

“Tim是位特立独行的商人，他不光放眼于最长远、最广阔的视野并且切实地按照Yogi Berra的建议去做了：‘如果你在路上遇到岔路口，走小路（岔路）。’回顾过去Tim似乎每一次都选择了小路，而且有几次都是一闪即逝的机会，尽管大路也不错。”

——Linux Journal

译者序

自2003年Google论文发布后，MapReduce作为一种分布式海量数据处理的编程框架，得到业界的广泛关注。近年来，随着Hadoop的普及，MapReduce目前已经成为海量数据处理的最基础但也是最重要的方法之一。

虽然随着Hadoop生态圈的持续发展，在MapReduce之上，已经有多种更高层次抽象的语言或工具供开发者选择，如Hive和Pig，它们使得开发者不用直接面对MapReduce程序，提升了开发效率，同时也降低了大数据分析和处理的门槛。但是，在实际的生产环境中，出于性能或其他方面的一些考虑，有时我们可能还得重新编写MapReduce代码。另外，在了解相关底层原理之后，也能让我们编写的上层应用更加高效。

本书主要介绍的是编程模式，即如何利用MapReduce框架解决一类问题，重在提供解决问题的方法和思路，避免读者在实际的工作中走弯路。其中，会花大量篇幅介绍各种模式的原理及实现机制，并会有相应的应用实例，让读者对每种模式能有更直观的理解。本书涵盖了绝大部分MapReduce编程可能面对的场景，是一本不可多得的好书。

我们希望，读者在学习本书之前对Hadoop系统有所了解，知道如何编写MapReduce程序，并了解MapReduce程序框架的工作原理。因为本书不会过多涉及底层框架及MapReduce API。

由于本书涉及的许多术语目前尚无固定译法，译者经过反复推敲、讨论，尽量选择一个简洁达意的译法，但仍然难免词不达意。由于译者水平有限，译文中的不当之处在所难免。译文中的错误应当由译者负责，我们真诚地希望同行和读者们不吝赐教，我们将不胜感谢。最后特别感谢本书的编辑杨海玲老师，是她的支持和鼓励才让本书的中译版可以与读者见面。最后感谢我们的家人和朋友在本书的翻译过程中对我们的无限宽容与支持。

徐钊 赵重庆

于深圳，腾讯数据平台部

前言

欢迎阅读《MapReduce设计模式》！这是一本既独特又熟悉的书。首先，这显然是一本关于设计模式的书，为大家提供解决问题的模板或通用指南。我们看了一些以前出版的有关设计模式的书，特别是Gamma等人（1995）编著的《Design Patterns: Elements of Reusable Object-Oriented Software》（通常称为“四人组”的书），从中汲取了灵感。在每个模式的描述中，读者都会看到一个我们反复使用的模板，这个模板基本是基于他们这本书的。重复看到类似的模板可以帮助读者获取所需的特定信息。这在以后使用这本书当参考书时特别有用。

这本书相对于“cookbook”类的书要更开放一些，因为本书不是面向解决具体问题的。但与cookbook类的书相似的是，本书涉及的内容同样都是简短的、分门别类的。要解决你所面临的问题需要付出比复制、粘贴我们的代码更多的努力，但是我们希望你可以找到一个模式帮助你解决掉90%的问题。

这本书主要是关于Hadoop或MapReduce的数据分析层面的。我们特意尽量不去引入过多有关Hadoop或MapReduce如何工作的细节，也没有长篇大论地说明我们使用的API。这些主题在互联网和相关出版物中已经有不少的涉及，因此我们决定把重点放在分析上。

考虑到在风格上与其他书籍有所不同，所以我们将在前言里说明如何更好地阅读本书。

目标读者

我们编写这本书的动机是为了填补在许多新的MapReduce开发者身上看到的空白。他们已经了解如何使用Hadoop系统，并且熟悉编写MapReduce程序的基本方法，但由于缺乏经验，不能更好地完成工作。这本书的意图是通过学习专家解决MapReduce问题的方法来帮助开发者在实践中避免出错。因此从某些方面来说，这是一本面向中高级MapReduce开发者的书，但我们相信初学者和专家同样也可以在本书中得到一些启示。

本书同样也适合于希望学习MapReduce范型的读者。通过对MapReduce示例代码的深入讲解和对MapReduce系统内部工作原理的详细解释，可以帮助软件工程师完成MapReduce的开发分析工作。另外，本书会有比较多的篇幅讨论一些模式的动机及它们的常见用例，这对那些希望了解像Hadoop这样的系统能做什么的工程师也会很有吸引力。

为了充分利用本书，我们建议读者有一些Hadoop方面的基础知识，因为所有的示例代码都是基于Hadoop（平台）的，并且许多模式的讨论都是在Hadoop环境下进行的。我们将会在第1章给出简短的相关背景知识介绍，同时也会给出更多的阅读材料供读者参考。

模式格式

为了方便连续阅读，本书中的模式都遵循同一个模板格式。需要注意的是，一些模式会忽略某些对于模式上下文来说没有意义的部分。

目的

这一部分主要对模式需要解决的问题进行简短的描述。

动机

这一部分主要解释问题发生的原因或者问题可能会出现的场景。通常会对一些用例做简要的讨论。

适用场景

这一部分给出了解决问题的特定模式需要满足的一系列准则。有些是特定模式的设计限制，有些则是为了帮助你确认当前模式是否适合你（问题）的情况。

结构

这一部分解释了MapReduce作业本身的设计。它会解释map阶段和reduce阶段的功能，同时指出是否需要特定的分区函数、合并函数或者输入格式。这是模式的“肉”，解释了如何解决对应的问题。

结果

这一部分很简短，只介绍了模式的输出是什么样的。这也是这个模式产生的最终输出目标。

类似用法

对于有一些SQL或者Pig相关经验的读者，这一部分会给出这些语言在解决相似问题时的类比。读者甚至可以通过直接阅读这一部分来确认模式的适用场景。

有时，有些应用是MapReduce特有的，这时我们会省略SQL、Pig或者二者。

已知应用

这一部分概述了这个模式的一些常见用例。

性能分析

这一部分将解释模式的性能剖析。理解这一点非常重要，因为每个MapReduce分析都需要正确的调整和配置，才能最大限度地提高性能。如果缺乏MapReduce程序对集群计算资源占用的相关知识，将很难做到这一点。

本书中的示例

本书中的所有示例代码都是基于Hadoop v1.0.3版本编写的。虽然当前有众多的开源和商用系统都支持MapReduce，但为了使我们的示例统一，易于学习，我们必须选择一个系统来做示例，因此我们选择了Hadoop。选择Hadoop是一种必然，因为Hadoop的应用更为广泛。但我们希望那些使用MongoDB的MapReduce以及其他MapReduce实现的开发者可以将本书中的示例扩展到相应的平台上。

通常，我们都会尝试使用新的mapreduce API来实现我们的示例，而摒弃已经不推荐使用的mapred API。请注意，由于新旧API是不兼容的，请不要将本书的示例代码与不少用户还在使用的旧式mapred API的代码混用。

我们的示例普遍省略了出错处理部分，主要是为了使代码更简洁。在真实的大数据系统中，你可以预料到数据都是不规则的，你会想在分析中积极主动地处理这些情况。

我们在本书中贯穿使用了相同的数据集：来自StackOverflow的数据库备份文件。StackOverflow是一个非常流行的网站，软件工程师可以在上面就任何编码主题（包括Hadoop）提出问题、解答问题。之所以选择这个数据集是因为它的数据量合适，它没有大到无法在单机处理的程度。这个数据集还包含了人类产生的自然语言文本，以及“结构化的”元素，像用户名和日期。

贯穿本书示例，我们通过抽取数据集的解析逻辑作为辅助函数，以明确地区分什么代码是这个数据集特有的，哪些代码是通用的并且是模式的一部分。因为XML是非常简单的，所以在我们的Java代码中，我们通常避免使用成熟的XML解析器，只用简单的字符串操作来对其进行解析。

这个数据集包含5个表，我们只使用其中的3个，即评论、帖子以及用户。所有数据都符合XML标准，并且每行包含一条记录。

我们在本书中使用如下三个StackOverflow的表。

评论

<row Id="2579740" PostId="2573882" Text="Are you getting any results? What
are you specifying as the command text?" CreationDate="2010-04-04T08:48:51.347"   
UserId="95437" />

评论是网站用户可以留在帖子上的跟进问题或者建议（即问题或者答案）。

帖子

<row Id="6939296" PostTypeId="2" ParentId="6939137"   
CreationDate="2011-08-04T09:50:25.043" Score="4" ViewCount=""   
Body="&lt;p&gt;You should have imported Poll with &lt;code&gt;   
from polls.models import Poll&lt;/code&gt;&lt;/p&gt;&#xA;"   
OwnerUserId="634150" LastActivityDate="2011-08-04T09:50:25.043"   
CommentCount="1" />

<row Id="6939304" PostTypeId="1" AcceptedAnswerId="6939433"   
CreationDate="2011-08-04T09:50:58.910" Score="1" ViewCount="26"   
Body="&lt;p&gt;Is it possible to gzip a single asp.net 3.5 page? my?  
site is hosted on IIS7 and for technical reasons I cannot enable gzip   
compression site wide. does IIS7 have an option to gzip individual pages or   
will I have to override OnPreRender and write some code to compress the   
output?&lt;/p&gt;&#xA;" OwnerUserId="743184"   
LastActivityDate="2011-08-04T10:19:04.107" Title="gzip a single asp.net page"   
Tags="&lt;asp.net&gt;&lt;iis7&gt;&lt;gzip&gt;"  
AnswerCount="2" />

帖子包含网站上的问题和答案。用户可以发布问题，之后其他用户可以自由地发表针对这个问题的答案。问题和答案可以被投票支持或者投票反对，这取决于你是否觉得这个帖子是有助益的。为了方便对问题进行分类，问题的创建者可以指定一系列的“标签”，来标记这个帖子的内容。在上面的示例中，我们可以看到这个帖子是关于asp.net、iis和gzip的。

有一点需要注意的是，帖子的内容主体是转义的HTML。这使得解析工作更具挑战性，但对于已有的工具来说这不是很难解决。大多数问题以及许多的答案的长度都是非常长的！

帖子的情况有些复杂，因为其中问题和答案混杂在一起。问题的PostTypeId为1，而答案的PostTypeId为2。答案通过ParentId字段（问题不包含这个字段）来指向其对应的问题。而问题中包含的是Title和Tags。

用户

<row Id="352268" Reputation="3313" CreationDate="2010-05-27T18:34:45.817"   
DisplayName="orangeoctopus" EmailHash="93fc5e3d9451bcd3fdb552423ceb52cd"   
LastAccessDate="2011-09-01T13:55:02.013" Location="Maryland" Age="26"   
Views="48" UpVotes="294" DownVotes="4" />

用户表包含了StackOverflow账户持有者的全部数据。大部分的信息都展示在用户档案中。

StackOverflow的用户都有一个声望值。当一个用户在这个网站上提交的问题或者答案得到其他用户的投票支持时，这个用户的声望值就会上升。

想进一步了解数据集的话，可以下载README.txt文件，参考其中的相关信息。

在示例中，我们使用了自己编写的辅助函数来解析数据集。这个辅助函数读取一行StackOverflow数据，返回一个HashMap。这个HashMap将标签存储为键，将实际数据存储为值。

package mrdp.utils;  

import java.util.HashMap;  
import java.util.Map;  

public class MRDPUtils {  
  // This helper function parses the stackoverflow into a Map for us.  
  public static Map<String, String> transformXmlToMap（String xml）{  
    Map<String, String> map = new HashMap<String, String>();  
    try {  
      // exploit the fact that splitting on double quote_  
      // tokenizes the data nicely for us_  
      String[] tokens = xml.trim().substring（5, xml.trim().length()- 3） 
        .split（"\""）;  

      for（int i = 0; i < tokens.length - 1; i += 2）{  
        String key = tokens[i].trim();  
        String val = tokens[i + 1];  

        map.put（key.substring（0, key.length()- 1）, val）;  
      }  
    } catch（StringIndexOutOfBoundsException e）{  
      System.err.println（xml）;  
    }  
    return map;  
  }  
}

本书中使用的排版约定

本书中使用了如下几种排版约定。

• 斜体字：表示新术语、URL、电子邮件地址、文件名以及文件扩展名。
• 等宽字体：表示程序清单，以及段落中引用的程序元素，如变量或者函数名称、数据库、数据类型、环境变量、语句和关键字。
• 加粗的等宽字体：表示需要用户进行输入的命令或者其他文本。

斜的等宽字体：表示需要使用用户提供的值或者根据上下文确定的值来替换的文本。

这个图标表示这是一个提示、建议或者一般性的注记。

这个图标表示这是警告或者警示。

代码示例的使用

本书的目的是帮助用户完成工作。通常情况下，你可以在自己的程序和文档中使用本书中的代码，不需要联系我们获取许可，除非你明显复制了大部分代码。例如，写程序时使用几个本书中的代码片段是不需要获得许可的。但是，如果要销售或者传播O'Reilly图书中的示例光盘就必须要获得许可。在回答问题时引用到本书或以本书中的例子为引证时不需要获得许可。但是，如果要在你的产品文档中用到本书中的大量示例代码就需要获得许可。

虽然并非是必需的，但如果可以注明出处，我们将非常感谢。出处一般包括标题、作者、出版商和ISBN。例如：“MapReduce Design Patterns by Donald Miner and Adam Shook（O'Reilly）. Copyright 2013 Donald Miner and Adam Shook, 978-1-449-32717-0.”

如果你觉得你对代码示例的使用超出了合理使用的范围或者超出了上述许可的范围，那么请随时与我们联系：permissions@oreilly.com。

如何联系我们

如果你想就本书发表评论或有任何疑问，敬请联系出版社。

美国：

O'Reilly Media Inc.

1005 Gravenstein Highway North

Sebastopol, CA 95472

中国：

北京市西城区西直门南大街2号成铭大厦C座807室（100035）

奥莱利技术咨询（北京）有限公司

我们还为本书建立了一个网页，其中包含了勘误表、示例和其他额外的信息。你可以通过http://oreil.ly/mapreduce-design-patterns访问该网页。

关于本书的技术性问题或建议，请发邮件到bookquestions@oreilly.com。

欢迎登录我们的网站（http://www.oreilly.com），查看更多我们的书籍、课程、会议和最新动态等信息。

我们的其他联系方式如下。

Facebook：http://facebook.com/oreilly

Twitter：http://twitter.com/oreillymedia

YouTube：http://www.youtube.com/oreillymedia

致谢

O'Reilly出版的书永远是一流的，现在我们终于知道这是为什么了。支持人员，特别是我们的编辑Andy Oram，在引导我们完成本书创作的过程中给予了很大的帮助。他们给予作者充分的自由来表述信息，同时以我们需要的任何方式为我们提供帮助。

在这里要特别感谢那些阅读本书并给出有用解释和评论的Tom Wheeler、Patrick Angeles、Tom Kulish和Lance Byrd。同时感谢Jeff Gold给了我们最初的鼓励和意见。我们非常感谢Eric Sammer在寻找审阅者的过程中给予的帮助，并预祝他的新书《Hadoop Operations》成功。

贯彻本书的StackOverflow数据集是在Creative Commons的许可下免费获得的。如果有读者愿意花时间发布这个数据集，我们会很高兴，那样的话，类似的项目就可以使用这个内容。这对社区也将是非常好的贡献。

Don非常感谢他在Greenplum的同事们给予的支持，在工作的时间安排上给予了很大的帮助，提供了精神支持及技术建议。Greenplum的同事们都以某种方式帮助过我，不管他们是否意识到，感谢Ian Andrews、Dan Baskette、Nick Cayou、Paul Cegielski、Will Davis、Andrew Ettinger、Mike Goddard、Jacque Istok、Mike Maxey、Michael Parks和Parham Parvizi。同时，感谢Andy O'Brien在与Postgres相关的章节给予的帮助。

Adam要感谢他的家人、朋友和咖啡。

第1章　设计模式与MapReduce

MapReduce是处理数据分布在数百台机器上的计算框架，近些年来，随着其在Google、Hadoop及其他一些系统中的应用而越来越流行起来。这个计算框架超乎寻常地强大，但它并不是一种针对“大数据”问题的通用解决方案，因此，虽然可以很好地适用于一些问题，但对有些问题来说，解决起来还是非常具有挑战性的。本书将介绍哪些问题适合使用MapReduce计算框架来解决，以及如何高效地使用MapReduce计算框架。

很多初步了解MapReduce的开发者可能没有意识到，MapReduce不仅仅是一个工具，更是一个框架。我们必须拿问题解决方案去适配框架的map和reduce过程，在很多情况下，这个适配过程将非常具有挑战性。MapReduce更多的是一种约束，而不是一个单独的功能。

这使得问题的解决变得既简单又复杂。简单的一面在于，框架给出了关于可以做什么、不可以做什么的清晰界限，因此相对于过去所用的其他编程模型需要考虑的可选项要少很多。复杂的一面在于，在框架的约束下，找到解决问题的方案将会非常有难度。

初学MapReduce更像是在学习递归过程：寻找问题的递归解决方案会比较有挑战性，但一旦找到了问题的解决方案，问题将变得清晰、精准和优雅。在很多情况下，需要关注MapReduce作业所需要的系统资源，尤其是集群内部网络资源的使用情况。这是MapReduce框架在设计上的取舍，是在需要考虑并发、容错、扩展性以及其他挑战与只关注数据的分布式处理之间的平衡。但是，独特的系统加上独特的问题使解决方案产生了独特的设计模式。

什么是MapReduce设计模式？它是使用MapReduce模型来解决数据处理问题的通用模板。模式不是只针对如文本处理或者图像分析等特定领域的，它更像是解决问题的一种通用方法。使用设计模式是通过使用在实践中被尝试和验证过的一些原则来帮助我们构建更好的软件。

设计优秀的软件要面临一系列的挑战，设计并实现一个优秀的MapReduce程序同样也需要面临相似的挑战。就像缺乏优秀的设计会导致一个优秀的开发者写出差的软件一样，优秀的开发者也有可能实现出不够好的MapReduce算法。在MapReduce程序中，我们不仅要关注代码的简洁和可维护性，同时还要考虑到任务会在数百台机器的共享集群上处理TB级甚至PB级的数据，任务性能也需要格外地重视。同时，该作业与共享集群的机器上数以百计的任务存在竞争关系。一个好的设计可以带来几个数量级的性能提升，因此选择正确的设计来实现MapReduce算法就显得尤为重要。在深入讲解后面章节中的MapReduce设计模式之前，我们先来解释一下为什么将设计模式和MapReduce框架结合起来使用可以帮助我们解决问题，以及是如何得到这些启示的。

1.1　设计模式

近些年来，设计模式使开发者的工作变得更轻松。这些设计模式为解决问题提供了可复用的通用方法，开发者在遇到问题时可以花更少的时间来思考解决问题的策略，从而有更多的时间用来迎接新的挑战。与此同时，开发者积累的丰富经验也有了简洁的方式传递给新入门的开发者。

在软件工程的设计模式领域中，有一个重要里程碑，即《Design Patterns：Elements of Reusable Object-Oriented Software》一书（由Gamma等人所著），通常也被称为“四人组”（Gang of Four）的书。这本畅销书中没有一种模式是新发明的，而且很多模式都是使用了多年的。这本书经久不衰的秘诀在于，作者花了大量的时间记录和整理面向对象编程中最重要的设计模式。因为这本书出版于1994年，所以整理和收录的设计模式都来自于开发者之间口口相传、会议和杂志，以及当时还不太流行的互联网。

设计模式经受了时间的验证，并展示了正确的抽象层次：既避免了太具体，使得细节过于繁杂，从而难以裁剪来满足问题的需要，又不至于太泛泛，使得解决问题的一种模式需要包含大量的工作。这个层面的抽象产生的更大益处是，为开发者在日常交流和代码层面的交互提供了公共语言。简单地引用“抽象工厂”要比一遍遍地解释抽象工厂的原理更便于交流。而且，在读过他人实现的抽象工程代码后，也能同时领会到作者的意图。

MapReduce设计模式同样也是为问题和解决方案之间搭建桥梁的。MapReduce设计模式通过提供通用框架来解决数据计算问题，而不局限于特定领域。经验丰富的MapReduce开发者可以借此将积累的知识传授给新入门的开发者。这一点非常重要，因为MapReduce是一个正在快速成长的新技术，每天都会有新的开发者加入进来。MapReduce设计模式可以成为一起工作的团队之间的通用语言。建议其他开发者使用“reduce端连接”（reduce-side join）代替“map端复制连接”（map-side replicated join），要比分别解释两种机制的底层原理更加简洁与方便。

MapReduce设计模式的现状就像1994年以前设计模式在面向对象语言领域的情况一样。MapReduce设计模式的相关资料目前已经广泛分布在博客、类似StackOverflow的网站、技术类书籍以及世界各地的高级技术团队中。本书的目的不是提供全新的问题解决方案，而是将目前已经广泛应用的模式汇总整理起来，以方便大家分享。

即使已经了解了设计模式，在真实的问题解决实践中，还需要仔细考虑设计模式所适用的场景。当尝试使用从本书或其他地方学到的设计模式来解决新的问题之前，请仔细考量该设计模式的“适用场景”。

在通常情况下，本书涉及的MapReduce设计模式是与平台无关的。MapReduce框架最初是在Google的论文中提出的，但其对应的代码并没有开源。目前已经有多个独立的系统（如Hadoop、Disco和Amazon Elastic MapReduce）实现了MapReduce框架，另外一些大型系统的查询语言（如MongoDB、Greenplum DB和Aster Data）也已经内置了对MapReduce的支持。虽然设计模式的初衷是通用性，但是本书中的MapReduce主要面向的是Hadoop平台。由于各个MapReduce实现都使用了相同的概念架构，因此很多设计模式可以应用在其他的MapReduce系统（如MongoDB）中。然而，各个MapReduce系统实现之间的细节差异也是不容忽视的。“四人组”书中的设计模式是使用C++语言编写的，但是开发者会发现这些概念在其他现代编程语言（如Ruby和Python）中也适用。本书中的设计模式也可以应用在Hadoop之外的其他MapReduce系统中。你可以参考本书中的示例代码来完成你的代码开发工作。

1.2　MapReduce简史

是什么触动我们写一本MapReduce设计模式的书呢？当前，社区的发展势头和广泛使用的设计模式已经积累到了一个关键点，使得汇总整理一份设计模式清单供开发者分享成为可能。在前几年，Hadoop的发展初期，还没有足够的这方面的经验积累。但MapReduce的发展速度超乎寻常。从2004年Google公开发布MapReduce的论文开始，到2012年为止，Hadoop已经成长为了被广泛采用的分布式数据处理的业界标准。

MapReduce的真实起源是存在争议的，但引领我们走向这个旅程的是2004年Jeffrey Dean和Sanjay Ghemawat发表的论文《MapReduce：Simplified Data Processing on Large Clusters》。这篇论文此后被广泛引用，它描述了Google如何通过拆分、处理和聚合来处理他们那些大到令人难以置信的数据集。

在这篇论文发表后不久，开源软件领域的先行者Doug Cutting开始为他的Nutch系统实现其分布式的MapReduce框架，Nutch系统的目标是实现一个开源的搜索引擎。随着时间的推移以及后续Yahoo!的持续投入，Hadoop从Nutch中独立出来，并最终成为Apache Foundation的顶级项目。时至今日，大量的独立开发者和组织都加入到了Hadoop社区，并为其贡献代码，这些使得每一个Hadoop新版本的发布都有新增功能和性能提升。

此外，基于Hadoop的一些开源系统也在蓬勃发展。其中比较著名的包括Pig、Hive、HBase、Mahout和ZooKeeper。Doug Cutting和Hadoop社区的专家多次提到，Hadoop已经成为分布式处理中分布式操作系统的核心部件。在本书中，我们将以Hadoop生态系统中Java版的MapReduce为基础，来解释我们的示例。在某些章节中，我们还会将MapReduce设计模式与相似的Pig或Hive SQL实现进行比较。

1.3　MapReduce和Hadoop简介

本节主要向读者简单介绍Hadoop中的MapReduce框架，因为本书的示例代码都是基于Hadoop的。想要更加深入地了解Hadoop的读者可以参考Tom White的《Hadoop：The Definitive Guide》一书以及Apache Hadoop的官方网站。这些资料将帮助你简单地部署一个开发环境或生产环境来验证本书的示例代码。

Hadoop MapReduce作业被分成一系列运行在分布式集群中的map任务和reduce任务。每个任务都工作在被指定的小的数据子集上，因此负载是遍布集群中各个节点上的。map任务主要负责数据的载入、解析、转换和过滤。每个reduce任务负责处理map任务输出结果的一个子集。然后，reducer任务从mapper任务处复制map任务的中间数据，进行分组和聚合操作。从简单的数值聚合到复杂的关联操作以及笛卡儿积操作，MapReduce通过如此简洁的架构来解决范围广泛的诸多问题，这确实让人难以置信。

MapReduce作业的输入是一系列存储在Hadoop分布式文件系统（Hadoop Distributed File System，HDFS）上的文件。在Hadoop中，这些文件通过输入格式（input format）被分成了一系列的输入split（input split）。输入split可以看作是文件在字节层面的分块表示，每个split由一个map任务负责处理。

Hadoop中的每个map任务可以细分成4个阶段：record reader、mapper、combiner和partitioner。map任务的输出被称为中间键和中间值，会被发送到reducer做后续处理。reduce任务可以分为4个阶段：混排（shuffle）、排序（sort）、reducer和输出格式（output format）。map任务运行的节点会优先选择在数据所在的节点，因此，一般可以通过在本地机器上进行计算来减少数据的网络传输。

record reader

record reader通过输入格式将输入split解析成记录。record reader的目的是将输入数据解析成记录，但不负责解析记录本身。它将数据转换为键/值（key/value）对的形式，并传递给mapper处理。通常键是数据在文件中的位置，值是组成记录的数据块。定制record reader已经超出了本书的讨论范围，因此我们假设读者已经有合适的record reader来解析需要处理的数据。

map

在mapper中，用户定义的map代码通过处理record reader解析的每个键/值对来产生0个或多个新的键/值对结果。键/值的选择对MapReduce作业的完成效率来说非常重要。键是数据在reducer中处理时被分组的依据，值是reducer需要分析的数据。如何选择键/值对的更多细节会在本书后面的设计模式中进行详细解释。两个不同的MapReduce设计模式之间的一个重要区别就在于键/值对的语义。

combiner

combiner是一个可选的本地reducer，可以在map阶段聚合数据。combiner通过执行用户指定的来自mapper的中间键对map的中间结果做单个map范围内的聚合。例如，一个聚合的计数是每个部分计数的总和，用户可以先将每个中间结果取和，再将中间结果的和相加，从而得到最终结果。在很多情况下，这样可以明显地减少通过网络传输的数据量。在网络上发送一次（hello world，3）要比三次（hello world，1）节省更多的字节量。因为combiner的应用广泛，所以我们将在后续的模式中对其进行更深入的讲解。很多新Hadoop代码开发者可能会忽视combiner，但通常combiner可以产生特别大的性能提升，并且没有副作用。我们将在后续的章节中指出哪些模式可以通过使用combiner得到优化，以及哪些模式是不能使用combiner的。combiner不能保证执行，因此不能作为整个算法的一部分。

partitioner

partitioner的作用是将mapper（如果使用了combiner的话就是combiner）输出的键/值对拆分为分片（shard），每个reducer对应一个分片。默认情况下，partitioner先计算目标的散列值（通常为md5值）。然后，通过reducer个数执行取模运算key.hashCode()%（reducer的个数）。这种方式不仅能够随机地将整个键空间平均分发给每个reducer，同时也能确保不同mapper产生的相同键能被分发至同一个reducer。用户可以定制partitioner的默认行为，并可以使用更高级的模式，如排序。当然，一般情况下是不需要改写partitioner的。对于每个map任务，其分好区的数据最终会写入本地文件系统，等待其各自的reducer拉取。

混排和排序

reduce任务开始于混排和排序这一步骤。该步骤主要是将所有partitioner写入的输出文件拉取到运行reducer的本地机器上，然后将这些数据按照键排序并写到一个较大的数据列表中。排序的目的是将相同键的记录聚合在一起，这样其所对应的值就可以很方便地在reduce任务中进行迭代处理。这个过程完全不可定制，而且是由框架自动处理的。开发人员只能通过自定义Comparator对象来确定键如何排序和分组。

reduce

reducer将已经分好组的数据作为输入，并依次为每个键对应分组执行reduce函数。reduce函数的输入是键以及包含与该键对应的所有值的迭代器。在后文介绍的模式中，我们将看到在这个函数中有很多种处理方法。这些数据可以被聚合、过滤或以多种方式合并。当reduce函数执行完毕后，会将0个或多个键/值对发送到最后的处理步骤——输出格式。和map函数一样，因为reduce函数是业务处理逻辑的核心部分，所以不同作业的reduce函数也不相同。

输出格式

输出格式获取reduce函数输出的最终键/值对，并通过record writer将它写入到输出文件中。每条记录的键和值默认通过tab分隔，不同记录通过换行符分隔。虽然一般情况下可以通过自定义实现非常多的输出格式，但是，不管是什么格式，最终的结果都将写到HDFS上。和record reader一样，如何定制输出格式不在本书的讨论范围，因为那是对I/O的简单处理。

1.4　Hadoop示例：单词计数

在介绍完MapReduce的整个处理过程之后，让我们来看一个简单的示例：单词计数（Word Count）。“单词计数”程序是一个典型的MapReduce示例，因为它既简单，又很适合使用MapReduce高效地处理。很多人会抱怨说“单词计数”作为示例已经被用过太多次了，希望本书后面的内容能弥补这一点！

在这个特定的示例中，我们将对StackOverflow网站上用户提交的评论进行单词计数。网页中Text域的内容将被抽取出来并做一些预处理，然后我们再计算每个词出现的次数。这个数据集中的示例记录如下：

<row Id="8189677" PostId="6881722" Text="Have you looked at Hadoop?" 
CreationDate="2011-07-30T07:29:33.343" UserId="831878" />

这条记录是StackOverflow的第8 189 677条评论，帖子数为6 881 722，用户数是831 878。PostId的数量和UserId数量作为外键可以和数据集中的其他部分数据进行关联。我们将在本书的第5章介绍如何实现这种关联。

我们分析的第一块代码是驱动程序（driver）部分。驱动程序的作用将MapReduce作业的所有组件组合起来然后提交执行。这些代码一般都是通用的并且被作为“通用模板”。在后面介绍的编程模式中你会看到，我们大部分的驱动程序都是相同的。

下面这些代码演变自Hadoop Core代码中的“Word Count”示例。

import java.io.IOException;   
import java.util.StringTokenizer;   
import java.util.Map;  
import java.util.HashMap;  

import org.apache.hadoop.conf.Configuration;   
import org.apache.hadoop.fs.Path;  
import org.apache.hadoop.io.IntWritable;   
import org.apache.hadoop.io.Text;  
import org.apache.hadoop.mapreduce.Job;  
import org.apache.hadoop.mapreduce.Mapper;  
import org.apache.hadoop.mapreduce.Reducer;  
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;   
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;  
import org.apache.hadoop.util.GenericOptionsParser;   

import org.apache.commons.lang.StringEscapeUtils;   

public class CommentWordCount {  

  public static class WordCountMapper  
      extends Mapper<Object, Text, Text, IntWritable> {  
           ...   
  }  

  public static class IntSumReducer  
      extends Reducer<Text, IntWritable, Text, IntWritable> {  
            ...   
  }  
  public static void main(String[] args) throws Exception {   
    Configuration conf = new Configuration();  
    String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs();   
    if (otherArgs.length != 2) {  
      System.err.println("Usage: CommentWordCount <in><out>";
      System.exit(2);  
    }  

    job job = new Job(conf, "StackOverflow Comment Word Count");   
    job.setJarByClass(CommentWordCount.class);   
    job.setMapperClass(WordCountMapper.class);   
    job.setCombinerClass(IntSumReducer.class);   
    job.setReducerClass(IntSumReducer.class);   
    job.setOutputKeyClass(Text.class);   
    job.setOutputValueClass(IntWritable.class);   
    FileInputFormat.addInputPath(job, new Path(otherArgs[0]));   
    FileOutputFormat.setOutputPath(job, new Path(otherArgs[1]));   
    System.exit(job.waitForCompletion(true) ? 0 : 1);  
  }   
}

驱动程序的作用是协调整个任务。main函数中的前几行代码都是在解析命令行输入参数。然后，开始设置job对象的参数，包括计算过程中用到的类以及输入、输出路径。这就是驱动程序的全部！最重要的一点是要确保设置的类名和你编写的类名是一致的，并且输出的键、值类型和mapper定义的一致。

在后面介绍的不同模式中，上述代码里唯一会变化的是job.setCombinerClass方法。某些情况下，因为reducer的特性，combiner将不会被用到。在另外一些情况下，combiner类将不同于reducer类。不过在“单词计数”程序中，使用combiner会非常高效，并且启用起来非常简单。

接下来看mapper代码是如何解析和准备文本的。当标点符号和随机文本被清理掉后，文本字符串将被分割成一个单词列表。然后，产生的中间键是每个单词，其对应的值为“1”，这表示这个单词已出现过一次。即使一个单词在一条记录中出现了两次，输出的依然是键=该单词、值=1，不过会有两个这样的键/值对，这些键/值对将在后面处理。最终，所有这些键对应的值汇总求和就能得到每个单词出现的总次数。

public static class WordCountMapper  
      extends Mapper<Object, Text, Text, IntWritable> {  
  private final static IntWritable one = new IntWritable(1);  
  private Text word = new Text();  

  public void map(Object key, Text value, Context context)   
              throws IOException, InterruptedException {  
    // Parse the input string into a nice map  
    Map<String, String> parsed = MRDPUtils.transformXmlToMap(value.toString());   

    // Grab the "Text" field, since that is what we are counting over  
    String txt = parsed.get("Text");  

    // .get will return null if the key is not there  
    if (txt == null) {   
       // skip this record  
          return;   
    }  

    // Unescape the HTML because the data is escaped.  
    txt = StringEscapeUtils.unescapeHtml(txt.toLowerCase());  

    // Remove some annoying punctuation  
    txt = txt.replaceAll("'", ""); // remove single quotes (e.g., can't)   
    txt = txt.replaceAll("[^a-zA-Z]", " "); // replace the rest with a space  

    // Tokenize the string by splitting it up on whitespace into   
    // something we can iterate over,  
    // then send the tokens away  
    StringTokenizer itr = new StringTokenizer(txt);  
    while (itr.hasMoreTokens()) {  
      word.set(itr.nextToken());   
      context.write(word, one);  
    }   
  }  
}

第一个函数MRDPUtils.transformXmlToMap是一个辅助函数，它按照通用的方式逐条解析StackOverflow数据。我们后面的示例中会经常用到它。其基本原理是读入一条StackOverflow的XML（这是一种很容易预测的格式）文件中的记录，然后将XML的属性和其值保存在一个Map中。

接下来，请注意WordCountMapper类。这部分代码会比驱动程序稍微复杂些。我们会看到大部分工作是在mapper中完成的，因此，第一个需要重点关注的就是它的父类类型：

Mapper<object,Text,Text,IntWritable>

4个输入分别对应于输入键、输入值、输出键以及输出值的类型。在本示例中，我们并不关注输入键，故将其类型定义为Object。由于数据是按行从文本文档中读入的，因此，输入值的类型是Text（Hadoop中一种特殊的String类型）。因为我们是把单词作为键，出现次数作为值，所以输出键和输出值的类型被分别定义成Text和IntWritable。

mapper输入的键、值数据类型是在作业配置的FileInputFormat中定义的。默认实现是TextInputFormat。TextInputFormat的键是LongWritable对象，表示截至目前从文件中读入的字节数；其值是Text对象，表示从文本中读入的一行记录。如果使用不同的输入格式，那么很可能需要改变这些键/值的数据类型。

直到调用StringTokenizer之前，所做的事情都是清理字符串。首先，由于原始数据中的字符串是按照XML的格式存储的，因此需要先将字符串提取出来。然后，再剔除那些无用的标点符号。例如，Hadoop!和Hadoop?应该等同于Hadoop。最后，对于每一个token（即记号），将会输出该记号和数字1，即表明该记号出现了1次。框架将会接下来对这些键/值对进行混排和排序，然后交由reduce任务处理。

最后，我们来分析reducer代码，这部分代码相对简单。对于每个键分组都会调用reduce函数，在本例中键为单词。然后，reduce函数将迭代处理该键对应的所有值，即将值进行求和，在本例中值为单词的出现次数。得到的结果就是该单词出现的总次数。

public static class IntSumReducer  
      extends Reducer<Text, IntWritable, Text, IntWritable> {  
  private IntWritable result = new IntWritable();  

  public void reduce(Text key, Iterable<IntWritable> values,   
          Context context) throws IOException, InterruptedException {  
    int sum=0;  
    for (IntWritable val : values) {  
       sum += val.get();  
    }  

     result.set(sum);  
     context.write(key, result);  
  }  
}

在本例的mapper中，输入、输出类型是通过父类模板定义的。和mapper一样，reducer定义中也包括以下四个类型：输入键、输入值、输出键和输出值。输入键和输入值的数据类型必须和mapper的输出键及输出值类型一致。输出键、输出值数据类型必须和作业配置的FileOutputFormat一致。在本例中，使用默认的TextOutputFormat格式，TextOutputFormat可以把任意两个Writable对象作为输出。

reduce函数的很多签名有别于map函数：reduce函数有一个Iterator（迭代器），它包含的是所有的值，而不是单个值。这意味着你可以通过迭代的方式处理一个键所对应的所有值，而不是一次只能处理一个。对于绝大部分MapReduce作业中的reducer来说，键通常都是非常重要的，但mapper中的输入键则不然。

所有传给context.write的数据最终都会写到一个输出文件中。每个reducer将创建一个文件，因此，如果想要把结果合并到一起，则还需要在最后增加一个合并它们的处理步骤。

现在我们已经掌握了一个简单的示例，下面让我们深入学习一些设计模式！

1.5　Pig和Hive

在Hadoop生态系统中有了Hive和Pig这类工具，对MapReduce设计模式没有太强烈的需求。但我们还是想借本书的开始部分解释为什么MapReduce设计模式依然如此重要。

Pig和Hive是对MapReduce更高层次的抽象。虽然它们提供的接口与“map”和“reduce”无关，但实际上它们会将较高级的语言翻译成一组MapReduce作业。就像关系型数据库管理系统（RDBMS）中的查询计划器（query planner）会将SQL语句解析成对数据的实际操作一样，Hive和Pig也是将它们各自的语言翻译成MapReduce操作。

在本书相关章节中可以看到，相对于用Java写的原生Hadoop实现，使用Pig和SQL（或HiveQL）将更为简洁。例如，用Java实现一个全排序，可能要写上几页代码，但用Pig只需要几行。

既然Hadoop提供了像Pig和Hive这样的工具给我们选择，为什么还要用Java去实现MapReduce？为什么用几行代码就能实现的功能，本书作者要花时间解释如何用几百行代码实现？目的是什么？这里有两个核心原因。

首先，对于像MapReduce这样的系统，了解其底层的工作原理具有理论价值。如果开发者知道Pig是如何执行reduce端连接操作的，那么在使用时将会做出更明智的选择。不理解MapReduce原理，只知道如何使用Pig和Hive，在某些情况下可能会导致危险情况的发生。尽管你得益于高层次的接口，但这并不意味着你可以忽视底层的细节。大规模的MapReduce集群就像重型机械一样，需要得到足够的重视。

其次，Pig和Hive在功能的完整性以及成熟度上目前还有所欠缺（截至2012年）。很显然，它们还没有完全发挥出自己的潜能。目前，它们根本不能像Java写的MapReduce那样解决所有的问题。随着时间的推移，伴随着bug的修复、新特性的增加以及重要版本的发布，这种现状将会改变。假设，基于Pig v0.6，你所在的机构可用Pig实现50%的分析工作。那么，基于Pig v0.9，这个比例将增加到90%。随着一个个新版本的发布，会有越来越多的工作可以通过高级抽象方法实现。但是在软件工程中有一个有趣的趋势：不能通过高级抽象方法解决的最后10%的问题，有可能是最关键的和最具挑战性的。此时，像Java这样的工具是解决这些问题最好的选择。就像在有些时候依然必须使用汇编语言一样！

如果可以，请使用Pig或Hive编写你的MapReduce。使用这种高级抽象语言写MapReduce的主要好处在于可读性、可维护性、开发时间及自动调优方面。然而对于常见的性能下降问题，我们很少会考虑Pig和Hive的间接影响。Pig和Hive的分析是按批处理的方式运行，本身就需要耗费好几分钟，那么，耗费的一两分钟真的不重要吗？在大部分情况下，Pig或Hive的查询计划优化器在优化代码上会比你做得更好。但在小部分情况下，因为Pig和Hive多消耗的几分钟十分重要，此时应该使用Java写MapReduce。

Pig和Hive对MapReduce设计模式的影响可能比其他工具更大。它们需要的新特性，有可能成为一种MapReduce设计模式。同时，随着越来越多MapReduce设计模式的开发，一些流行的模式也将在高层次抽象中成为重要操作。

Pig和Hive有自己的模式，并且随着更多问题被解决，专家们记录的模式也会越多。虽然Hive从发展了几十年的SQL模型中获得了益处，但是并不是所有的SQL模式都适用于Hive，反之亦然。当然，如果这些平台越来越受欢迎，相关的手册和设计模式书籍就会出现。