浅谈MapReduce设计模式

浅谈Map/Reduce设计模式概述MapReduce是一个基于Hadoop的算法框架。本文将从Hadoop开始介绍，然后重点讲述可用于Hadoop上的Map/Reduce设计模式。Hadoop简介Hadoop历史Hadoop最早起源于ApacheNutch，该项目始于2002年，是ApacheLucence的子项目之一。该项目的出现源于两篇论文，一篇是2003年发表的“关于谷歌分布式文件系统”（NDFS：NutchDistributedFileSystem），描述了谷歌搜索引擎网页相关数据存储架构，解决Nutch遇到的网页抓取和索引过程中产生的超大文件存储需求问题。一篇是2004年发表的“关于谷歌分布式计算框架MapReduce”，描述了谷歌内部最重要分布式计算框架，该框架可用于处理海量网页索引问题。由于NDFS和MapReduce在Nutch引擎中有着良好的应用，所以它们于2006年2月被分离出来成为一套独立的软件，命名为Hadoop。Hadoop功能与优势近年来，随着现代社会信息的飞速增长，大数据与云计算的概念已经越来越火。预计到2020年，互联网中产生的数字信息将会有三分之一的内容驻留在云平台中交由云平台处理。如何高效的存储和管理这些数据就成为了我们亟需解决的问题，这时Hadoop系统的优势就体现出来了。Hadoop通过三个方面高效的解决了云平台数据存储与管理的问题。一、它采用分布式存储方式HDFS（HadoopDistributedFileSystem）来提高读写速度和扩大存储容量；二、它采用MapReduce计算框架，分割数据进行分发到分布式文件系统中进行处理，然后再把处理过后的数据进行整合，保证了数据处理的高速；三、它采用存储冗余数据的方式来保证数据的安全性。用户可以轻松的架构并使用Hadoop系统，它主要具有四个优点：高可靠性、高扩展性、高效性、高容错性。Hadoop的构成经过多年发展，hadoop已经成为以MapReduce和HDFS为核心的很多个项目的集合，包括Common、Avro、Chukwa、Hive、HBase等都对hadoop提供了互补性服务或在核心层上提供了更高层的服务。在主要讲解MapReduce之前，让我们先简要的看一下各项目的功能。Core：一套分布式文件系统以及支持Map-Reduce的计算框架；Avro：定义了一种用于支持大数据应用的数据格式，并为这种格式提供了不同的编程语言的支持；HDFS：Hadoop分布式文件系统；Map/Reduce：是一个使用简易的软件框架，基于它写出来的应用程序能够运行在由上千个商用机器组成的大型集群上，并以一种可靠容错的方式并行处理上T级别的数据集；ZooKeeper：是高可用的和可靠的分布式协同（coordination）系统；Pig：建立于HadoopCore之上为并行计算环境提供了一套数据工作流语言和执行框架；Hive：是为提供简单的数据操作而设计的下一代分布式数据仓库。它提供了简单的类似SQL的语法的HiveQL语言进行数据查询；Hbase：建立于HadoopCore之上提供一个可扩展的数据库系统。Map/Reduce简介MapReduce是Google公司的核心计算模型，它将运行于大规模集群上的复杂的并行计算过程高度地抽象为两个函数：Map和Reduce。Hadoop中的MapReduce是一个使用简易的软件框架，基于它写出来的应用程序能够运行在由上千台商用机器组成的大型集群上，并以一种可靠容错的方式并行处理上T级别的数据集，实现了Hadoop在集群上的数据和任务的并行计算与处理。一个Map/Reduce作业（Job）通常会把输入的数据集切分为若干独立的数据块，由Map任务（Task）以完全并行的方式处理它们。框架会先对Map的输出进行排序，然后把结果输入给Reduce任务。通常作业的输入和输出都会被存储在文件系统中。整个框架负责任务的调度和监控，以及重新执行已经失败的任务。通常，Map/Reduce框架和分布式文件系统是运行在一组相同的节点上的，也就是说，计算节点和存储节点在一起。这种配置允许框架在那些已经存好数据的节点上高效地调度任务，这样可以使整个集群的网络带宽得到非常高效的利用。Map/Reduce框架由一个单独的MasterJobTracker和集群节点上的SlaveTaskTracker共同组成。Master负责调度构成一个作业的所有任务，这些任务分布在不同的slave上。Master监控它们的执行情况，并重新执行已经失败的任务，而Slave仅负责执行由Master指派的任务。在Hadoop上运行的作业需要指明程序的输入/输出位置（路径），并通过实现合适的接口或抽象类提供Map和Reduce函数。同时还需要指定作业的其他参数，构成作业配置（JobConfiguration）。在Hadoop的JobClient提交作业（JAR包/可执行程序等）和配置信息给JobTracker之后，JobTracker会负责分发这些软件和配置信息给slave及调度任务，并监控它们的执行，同时提供状态和诊断信息给JobClient。Map/Reduce计算模型在Google发表论文时，MapReduce的最大成就是重写了Google的索引文件系统。而现在，谁也不知道它还会取得多大的成就。MapReduce被广泛地应用于日志分析、海量数据排序、在海量数据中查找特定模式等场景中。但是，我们终究不得不承认，MapReduce终究不是万能的，它有自身使用的特定场景。JOBSHadoopMapReduceJobs可以切分成一系列运行于分布式集群中的map和reduce任务，每个任务只运行全部数据的一个指定的子集，以此达到整个集群的负载平衡。Map任务通常加载，解析，转换，过滤数据，每个reduce处理map输出的一个子集。Reduce任务会去map任务端获取中间数据来完成分组，聚合。用这样一种简明直接的范式，从简单的数值聚合到复杂的join操作和笛卡尔操作。INPUTMapReduce的输入是hdfs上存储的一系列文件集。在hadoop中，这些文件被一种定义了如何分割一个文件成分片的inputformat来分割，一个分片是一个文件基于字节的可以被一个map任务加载的一个块。MAP每个map任务被分为以下阶段：recordreader，mapper，combiner，partitioner。Map任务的输出叫中间数据，包括keys和values，发送到reduce端。运行map任务的节点会尽量选择数据所在的节点。这种情况下，不会出现网络传输，在本地节点就可以完成计算。RecordreaderRecordreader会把根据inputfromat生成输入分片翻译成records。Recordreader的目的是把数据解析成记录，而不是解析数据本身。它把数据以键值对的形式传递给mapper。通常情况下键是偏移量，值是这条记录的整个字节块。MapMap阶段，会对每个从recordreader处理完的键值对执行用户代码，这些键值对又叫中间键值对。键和值的选择不是任意的，并且对MapReducejob的成功非常重要。键会用来分组，值是reducer端用来分析的数据。这本书会在设计模式方面提供大量的细节去解释键值对的选择。设计模式之间一个主要的区别是键值对的语义。CombinerCombiner是一个map阶段聚合数据的部件，相当于一个局部reducer，它是可选的。它根据用户提供的方法在一个mapper范围内根据中间键去聚合值。例如：数的总和是各个部分数量的和，你可以先计算中间的数目，最后再把所有中间数目加起来。很多情况下，这样能减少数据的网络传输量。发送（helloworld，1）三次很显然要比发送（helloworld，3）需要更多的网络传输字节量。Combiners可以被广泛的模式替换。很多Hadoop开发者忽视combiner，但能获得更好的性能。我们需要指出的是哪一种模式用combiner有好处，哪一种不能用combiner。Combiner不会保证总会执行，所以它是一个整体逻辑。PartitionerPartitioner会获取从mapper（或combiner）来的键值对，并分割成分片，每个reducer一个分片。默认用哈希值，典型使用md5sum。然后partitioner根据reduce的个数执行取余运算：key.hashCode()%(numberofreducers)。这样能随即均匀的根据key分发数据到reduce，但仍然要保证不同mapper的相同key要到同一个reduce。Partitioner也可以自定义，使用更高级的样式，例如排序。然而，更改partitioner很少用。Partitioner的每个map的数据会写到本地磁盘，并等待对应的reducer检测，拿走数据。REDUCEReduce任务分为以下阶段：shuffle，sort，reduce，outputformat。ShuffleandsortReduce任务开始于shuffle和sort阶段。这一阶段获取partitioner的输出文件，并下载到reduce运行的本地机器。这些分片数据会根据key合并，排序成一个大的数据文件。排序的目的是让相同的key相邻，方便在reduce阶段值得迭代处理。这一阶段不能自定义，由框架自动处理。需要做的只是key的选择和可以自定义个用于分组的比较器。ReduceReduce任务会把分组的数据作为输入并对每个key组执行reduce方法代码。方法会传递key和可以相关的所有值得迭代集合。很多的处理会在这个方法里执行，也就会有很多的模式。一旦reduce方法完成，会发送0或多个键值对到outputformat。跟map一样，不同的reduce依据不同的逻辑情形而不同。OutputformatOutputformat会把reduce阶段的输出键值对根据recordwriter写到文件里。默认用tab分割键值对，用换行分割不同行。这里也可以自定义为更丰富的输出格式，最后，数据被写到hdfs，你可以自定义输出格式。Map/Reduce设计模式从上一章描述的mapreduce计算模型可以看出，mapreduce主要接受的是键值对，对大型键值对进行排序聚合等操作。下面让我们来看看有哪些模型可以应用于mapreduce。SummarizationPatterns（摘要模式）随着每天都有更多的数据加载进系统，数据量变得很庞大。这一章专注于对你的数据顶层的，概括性意见的设计模式，从而使你能扩展思路，但可能对局部数据是不适用的。概括性的分析都是关于对相似数据的分组和执行统计运算，创建索引，或仅仅为了计数。通过分组数据集计算聚合排序是一种快速获取结果的好方法。例如,你可能想按某种规则计算出所存的钱的总数，或者按人口计算人们在互联网花费的平均时长。对于新的数据集，你可以开始用这些分析类型帮你计算出数据中什么东西有趣或唯一，和哪些需要仔细研究。摘要模式主要有数值聚合、反向索引、用计数器计数三种具体的表现形式。数值聚合模式数值聚合模式是一个用于计算细节上的数据的统计值的通用模式。数值聚合模式使用所需条件：处理数值类型数据或做计数。数据能根据指定字段分组数值聚合模式各组件功能图：用法案例：1、Wordcount。这也是讲解mapreduce被用到的最多的一个例子。通常的使用方式就是统计出现的单词的频率，相同类型单词聚合计数等。2、Recordcount。一种常用的根据特定时间周期（周，日，时等）获取数据流量规律的分析方法。3、Min/max/count。一种计算最小，最大值，或特定事件总和的分析。例如，用户第一次发帖时间，最后一次发帖时间，和一段时间内发帖的总数。反向索引模式反向索引即根据数据集生成索引，用于快速搜索或数据的富集能力。反向索引模式使用所需条件：反向索引用在搜索查询时需要快速响应的情况下。查询的结果需要能被预先处理并放入数据库。反向索引模式各组件功