MapReduce _生活百科

文章插图
MapReduce【MapReduce】MapReduce是一种编程模型，用于大规模数据集（大于1TB）的并行运算。概念"Map（映射）"和"Reduce（归约）"，是它们的主要思想，都是从函式式程式语言里借来的，还有从矢量程式语言里借来的特性。它极大地方便了编程人员在不会分散式并行编程的情况下，将自己的程式运行在分散式系统上。当前的软体实现是指定一个Map（映射）函式，用来把一组键值对映射成一组新的键值对，指定并发的Reduce（归约）函式，用来保证所有映射的键值对中的每一个共享相同的键组。
基本介绍外文名：MapReduce
本质：一种编程模型
用途：大规模数据集的并行运算
特点：分布可靠
思想来源：Google的几篇论文
套用：大规模的算法图形处理、文字处理
定义MapReduce是面向大数据并行处理的计算模型、框架和平台，它隐含了以下三层含义：1）MapReduce是一个基于集群的高性能并行计算平台（Cluster Infrastructure）。它允许用市场上普通的商用伺服器构成一个包含数十、数百至数千个节点的分布和并行计算集群。2）MapReduce是一个并行计算与运行软体框架（Software Framework）。它提供了一个庞大但设计精良的并行计算软体框架，能自动完成计算任务的并行化处理，自动划分计算数据和计算任务，在集群节点上自动分配和执行任务以及收集计算结果，将数据分布存储、数据通信、容错处理等并行计算涉及到的很多系统底层的複杂细节交由系统负责处理，大大减少了软体开发人员的负担。3）MapReduce是一个并行程式设计模型与方法（Programming Model & Methodology）。它藉助于函式式程式设计语言Lisp的设计思想，提供了一种简便的并行程式设计方法，用Map和Reduce两个函式编程实现基本的并行计算任务，提供了抽象的操作和并行编程接口，以简单方便地完成大规模数据的编程和计算处理。由来MapReduce最早是由Google公司研究提出的一种面向大规模数据处理的并行计算模型和方法。Google公司设计MapReduce的初衷主要是为了解决其搜寻引擎中大规模网页数据的并行化处理。Google公司发明了MapReduce之后首先用其重新改写了其搜寻引擎中的Web文档索引处理系统。但由于MapReduce可以普遍套用于很多大规模数据的计算问题，因此自发明MapReduce以后，Google公司内部进一步将其广泛套用于很多大规模数据处理问题。到目前为止，Google公司内有上万个各种不同的算法问题和程式都使用MapReduce进行处理。2003年和2004年，Google公司在国际会议上分别发表了两篇关于Google分散式档案系统和MapReduce的论文，公布了Google的GFS和MapReduce的基本原理和主要设计思想。Hadoop的思想来源于Google的几篇论文，Google的那篇MapReduce论文里说：Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional languages 。这句话提到了MapReduce思想的渊源，大致意思是，MapReduce的灵感来源于函式式语言（比如Lisp）中的内置函式map和reduce 。函式式语言也算是阳春白雪了，离我们普通开发者总是很远。简单来说，在函式式语言里，map表示对一个列表（List）中的每个元素做计算，reduce表示对一个列表中的每个元素做叠代计算。它们具体的计算是通过传入的函式来实现的，map和reduce提供的是计算的框架。不过从这样的解释到现实中的MapReduce还太远，仍然需要一个跳跃。再仔细看，reduce既然能做叠代计算，那就表示列表中的元素是相关的，比如我想对列表中的所有元素做相加求和，那幺列表中至少都应该是数值吧。而map是对列表中每个元素做单独处理的，这表示列表中可以是杂乱无章的数据。这样看来，就有点联繫了。在MapReduce里，Map处理的是原始数据，自然是杂乱无章的，每条数据之间互相没有关係；到了Reduce阶段，数据是以key后面跟着若干个value来组织的，这些value有相关性，至少它们都在一个key下面，于是就符合函式式语言里map和reduce的基本思想了。这样我们就可以把MapReduce理解为，把一堆杂乱无章的数据按照某种特徵归纳起来，然后处理并得到最后的结果。Map面对的是杂乱无章的互不相关的数据，它解析每个数据，从中提取出key和value，也就是提取了数据的特徵。经过MapReduce的Shuffle阶段之后，在Reduce阶段看到的都是已经归纳好的数据了，在此基础上我们可以做进一步的处理以便得到结果。这就回到了最初，终于知道MapReduce为何要这样设计。2004年，开源项目Lucene（搜寻索引程式库）和Nutch（搜寻引擎）的创始人Doug Cutting发现MapReduce正是其所需要的解决大规模Web数据处理的重要技术，因而模仿Google MapReduce，基于Java设计开发了一个称为Hadoop的开源MapReduce并行计算框架和系统。自此，Hadoop成为Apache开源组织下最重要的项目，自其推出后很快得到了全球学术界和工业界的普遍关注，并得到推广和普及套用。MapReduce的推出给大数据并行处理带来了巨大的革命性影响，使其已经成为事实上的大数据处理的工业标準。儘管MapReduce还有很多局限性，但人们普遍公认，MapReduce是到目前为止最为成功、最广为接受和最易于使用的大数据并行处理技术。MapReduce的发展普及和带来的巨大影响远远超出了发明者和开源社区当初的意料，以至于马里兰大学教授、2010年出版的《Data-Intensive Text Processing with MapReduce》一书的作者Jimmy Lin在书中提出：MapReduce改变了我们组织大规模计算的方式，它代表了第一个有别于冯·诺依曼结构的计算模型，是在集群规模而非单个机器上组织大规模计算的新的抽象模型上的第一个重大突破，是到目前为止所见到的最为成功的基于大规模计算资源的计算模型。映射和化简简单说来，一个映射函式就是对一些独立元素组成的概念上的列表（例如，一个测试成绩的列表）的每一个元素进行指定的操作（比如前面的例子里，有人发现所有学生的成绩都被高估了一分，它可以定义一个“减一”的映射函式，用来修正这个错误。）。事实上，每个元素都是被独立操作的，而原始列表没有被更改，因为这里创建了一个新的列表来保存新的答案。这就是说，Map操作是可以高度并行的，这对高性能要求的套用以及并行计算领域的需求非常有用。而化简操作指的是对一个列表的元素进行适当的合併（继续看前面的例子，如果有人想知道班级的平均分该怎幺做？它可以定义一个化简函式，通过让列表中的元素跟自己的相邻的元素相加的方式把列表减半，如此递归运算直到列表只剩下一个元素，然后用这个元素除以人数，就得到了平均分。）。虽然他不如映射函式那幺并行，但是因为化简总是有一个简单的答案，大规模的运算相对独立，所以化简函式在高度并行环境下也很有用。分布可靠MapReduce通过把对数据集的大规模操作分发给网路上的每个节点实现可靠性；每个节点会周期性的返回它所完成的工作和最新的状态。如果一个节点保持沉默超过一个预设的时间间隔，主节点（类同Google File System中的主伺服器）记录下这个节点状态为死亡，并把分配给这个节点的数据发到别的节点。每个操作使用命名档案的原子操作以确保不会发生并行执行绪间的冲突；当档案被改名的时候，系统可能会把他们複製到任务名以外的另一个名字上去。（避免副作用）。化简操作工作方式与之类似，但是由于化简操作的可并行性相对较差，主节点会儘量把化简操作只分配在一个节点上，或者离需要操作的数据儘可能近的节点上；这个特性可以满足Google的需求，因为他们有足够的频宽，他们的内部网路没有那幺多的机器。用途在Google，MapReduce用在非常广泛的应用程式中，包括“分布grep，分布排序，web连线图反转，每台机器的词矢量，web访问日誌分析，反向索引构建，文档聚类，机器学习，基于统计的机器翻译...”值得注意的是，MapReduce实现以后，它被用来重新生成Google的整个索引，并取代老的ad hoc程式去更新索引。MapReduce会生成大量的临时档案，为了提高效率，它利用Google档案系统来管理和访问这些档案。在谷歌，超过一万个不同的项目已经採用MapReduce来实现,包括大规模的算法图形处理、文字处理、数据挖掘、机器学习、统计机器翻译以及众多其他领域。其他实现Nutch项目开发了一个实验性的MapReduce的实现，也即是后来大名鼎鼎的hadoopPhoenix是史丹福大学开发的基于多核/多处理器、共享记忆体的MapReduce实现。主要功能MapReduce提供了以下的主要功能：1）数据划分和计算任务调度：系统自动将一个作业（Job）待处理的大数据划分为很多个数据块，每个数据块对应于一个计算任务（Task），并自动调度计算节点来处理相应的数据块。作业和任务调度功能主要负责分配和调度计算节点（Map节点或Reduce节点），同时负责监控这些节点的执行状态，并负责Map节点执行的同步控制。2）数据/代码互定位：为了减少数据通信，一个基本原则是本地化数据处理，即一个计算节点儘可能处理其本地磁碟上所分布存储的数据，这实现了代码向数据的迁移；当无法进行这种本地化数据处理时，再寻找其他可用节点并将数据从网路上传送给该节点（数据向代码迁移），但将儘可能从数据所在的本地机架上寻找可用节点以减少通信延迟。3）系统最佳化：为了减少数据通信开销，中间结果数据进入Reduce节点前会进行一定的合併处理；一个Reduce节点所处理的数据可能会来自多个 Map节点，为了避免Reduce计算阶段发生数据相关性，Map节点输出的中间结果需使用一定的策略进行适当的划分处理，保证相关性数据传送到同一个 Reduce节点；此外，系统还进行一些计算性能最佳化处理，如对最慢的计算任务採用多备份执行、选最快完成者作为结果。4）出错检测和恢复：以低端商用伺服器构成的大规模MapReduce计算集群中，节点硬体（主机、磁碟、记忆体等）出错和软体出错是常态，因此 MapReduce需要能检测并隔离出错节点，并调度分配新的节点接管出错节点的计算任务。同时，系统还将维护数据存储的可靠性，用多备份冗余存储机制提高数据存储的可靠性，并能及时检测和恢复出错的数据。主要技术特徵MapReduce设计上具有以下主要的技术特徵： 1）向“外”横向扩展，而非向“上”纵向扩展即MapReduce集群的构建完全选用价格便宜、易于扩展的低端商用伺服器，而非价格昂贵、不易扩展的高端伺服器。对于大规模数据处理，由于有大量数据存储需要，显而易见，基于低端伺服器的集群远比基于高端伺服器的集群优越，这就是为什幺MapReduce并行计算集群会基于低端伺服器实现的原因。2）失效被认为是常态MapReduce集群中使用大量的低端伺服器，因此，节点硬体失效和软体出错是常态，因而一个良好设计、具有高容错性的并行计算系统不能因为节点失效而影响计算服务的质量，任何节点失效都不应当导致结果的不一致或不确定性；任何一个节点失效时，其他节点要能够无缝接管失效节点的计算任务；当失效节点恢复后应能自动无缝加入集群，而不需要管理员人工进行系统配置。MapReduce并行计算软体框架使用了多种有效的错误检测和恢复机制，如节点自动重启技术，使集群和计算框架具有对付节点失效的健壮性，能有效处理失效节点的检测和恢复。3）把处理向数据迁移传统高性能计算系统通常有很多处理器节点与一些外存储器节点相连，如用存储区域网路（Storage Area，SAN Network）连线的磁碟阵列，因此，大规模数据处理时外存档案数据I/O访问会成为一个制约系统性能的瓶颈。为了减少大规模数据并行计算系统中的数据通信开销，代之以把数据传送到处理节点（数据向处理器或代码迁移），应当考虑将处理向数据靠拢和迁移。MapReduce採用了数据/代码互定位的技术方法，计算节点将首先儘量负责计算其本地存储的数据，以发挥数据本地化特点，仅当节点无法处理本地数据时，再採用就近原则寻找其他可用计算节点，并把数据传送到该可用计算节点。4）顺序处理数据、避免随机访问数据大规模数据处理的特点决定了大量的数据记录难以全部存放在记忆体，而通常只能放在外存中进行处理。由于磁碟的顺序访问要远比随机访问快得多，因此 MapReduce主要设计为面向顺序式大规模数据的磁碟访问处理。为了实现面向大数据集批处理的高吞吐量的并行处理，MapReduce可以利用集群中的大量数据存储节点同时访问数据，以此利用分布集群中大量节点上的磁碟集合提供高频宽的数据访问和传输。5）为套用开发者隐藏系统层细节软体工程实践指南中，专业程式设计师认为之所以写程式困难，是因为程式设计师需要记住太多的编程细节（从变数名到複杂算法的边界情况处理），这对大脑记忆是一个巨大的认知负担，需要高度集中注意力；而并行程式编写有更多困难，如需要考虑多执行绪中诸如同步等複杂繁琐的细节。由于并发执行中的不可预测性，程式的调试查错也十分困难；而且，大规模数据处理时程式设计师需要考虑诸如数据分布存储管理、数据分发、数据通信和同步、计算结果收集等诸多细节问题。MapReduce提供了一种抽象机制将程式设计师与系统层细节隔离开来，程式设计师仅需描述需要计算什幺（What to compute），而具体怎幺去计算（How to compute）就交由系统的执行框架处理，这样程式设计师可从系统层细节中解放出来，而致力于其套用本身计算问题的算法设计。6）平滑无缝的可扩展性这里指出的可扩展性主要包括两层意义上的扩展性：数据扩展和系统规模扩展性。理想的软体算法应当能随着数据规模的扩大而表现出持续的有效性，性能上的下降程度应与数据规模扩大的倍数相当；在集群规模上，要求算法的计算性能应能随着节点数的增加保持接近线性程度的增长。绝大多数现有的单机算法都达不到以上理想的要求；把中间结果数据维护在记忆体中的单机算法在大规模数据处理时很快失效；从单机到基于大规模集群的并行计算从根本上需要完全不同的算法设计。奇妙的是，MapReduce在很多情形下能实现以上理想的扩展性特徵。多项研究发现，对于很多计算问题，基于MapReduce的计算性能可随节点数目增长保持近似于线性的增长。案例：统计词频如果想统计下过去10年计算机论文出现最多的几个单词，看看大家都在研究些什幺，那收集好论文后，该怎幺办呢？方法一：我可以写一个小程式，把所有论文按顺序遍历一遍，统计每一个遇到的单词的出现次数，最后就可以知道哪几个单词最热门了。这种方法在数据集比较耗时，是非常有效的，而且实现最简单，用来解决这个问题很合适。方法二：写一个多执行绪程式，并发遍历论文。这个问题理论上是可以高度并发的，因为统计一个档案时不会影响统计另一个档案。当我们的机器是多核或者多处理器，方法二肯定比方法一高效。但是写一个多执行绪程式要比方法一困难多了，我们必须自己同步共享数据，比如要防止两个执行绪重複统计档案。方法三：把作业交给多个计算机去完成。我们可以使用方法一的程式，部署到N台机器上去，然后把论文集分成N份，一台机器跑一个作业。这个方法跑得足够快，但是部署起来很麻烦，我们要人工把程式copy到别的机器，要人工把论文集分开，最痛苦的是还要把N个运行结果进行整合（当然我们也可以再写一个程式）。方法四：让MapReduce来帮帮我们吧！MapReduce本质上就是方法三，但是如何拆分档案集，如何copy程式，如何整合结果这些都是框架定义好的。我们只要定义好这个任务（用户程式），其它都交给MapReduce 。MapReduce伪代码实现Map和Reduce两个函式Map函式和Reduce函式是交给用户实现的，这两个函式定义了任务本身。Map函式接受一个键值对（key-value pair），产生一组中间键值对。MapReduce框架会将map函式产生的中间键值对里键相同的值传递给一个reduce函式。ClassMappermethodmap(String input_key, String input_value):// input_key: text document name// input_value: document contentsfor eachword w ininput_value:EmitIntermediate(w, "1");Reduce函式接受一个键，以及相关的一组值，将这组值进行合併产生一组规模更小的值（通常只有一个或零个值）。ClassReducermethod reduce(String output_key,Iterator intermediate_values):// output_key: a word// output_values: a list of countsintresult = 0;for each v in intermediate_values:result += ParseInt(v);Emit(AsString(result));在统计词频的例子里，map函式接受的键是档案名称，值是档案的内容，map逐个遍历单词，每遇到一个单词w，就产生一个中间键值对<w, "1">，这表示单词w咱又找到了一个；MapReduce将键相同（都是单词w）的键值对传给reduce函式，这样reduce函式接受的键就是单词w，值是一串"1"（最基本的实现是这样，但可以最佳化），个数等于键为w的键值对的个数，然后将这些“1”累加就得到单词w的出现次数。最后这些单词的出现次数会被写到用户定义的位置，存储在底层的分散式存储系统（GFS或HDFS）。工作原理