MapReduce： 大规模集群上的简化数据处理【摘要】 MapReduce是一个“与处理以及生成大量数据集相关联的”程序模型 用户通过定义一个map函数，处理键值对以生成一个中间键值对的集合， 以及一个叫做reduce的函数用以合并所有先前map过后的有相同键的中间量现实世界中的许多任务在这个模型中得到了很好的表达，如下文所述 程序员用这种风格的程序写出的代码可以自动并行以及在商用极其上大规模的处理数据运行时系统关注输入数据的分区，通过一系列机器的集合来规划程序的执行， 处理程序失效以及把控必要的系统内部交互这个框架的优势在于使得程序员无需任何并行与分布式系统的经验就可以容易的掌控大型分布式系统的资源 我们的MapReduce的实现是运行在商用机器的大规模集群之上，且拥有高可扩展性：一个典型的MapReduce运行场景是在数千台机器上处理TB级数据程序与系统易于使用：数百个MapReduce程序实施了数千份的MapReduce的每天都运行于谷歌集群之上job1.说明 在过去的五年里， 作者以及其它许多谷歌人开发出了大量的用于特定目的的处理大规模原始数据的程序，诸如网页请求日志等等计算不同类型的派生数据，这些派生数据有网络文件的迥异的图形结构，每个主机的页面数，某一天所提出的最高频率问题等等。
大多数这种计算在概念上是想当容易把握的然而，输入的数据通常是大规模的且计算不得不分布在数百甚至上千太的机器以在一个合理的时间内得出计算结果 有关如何并行计算，分布数据，处理失效则大大增加了原初直观问题的难度这就需要复杂的大量的代码来处理这些问题 作为对复杂性的反应，我们设计了一个全新的抽象模型允许表达简洁的且为我们所需要的计算，同时该抽象模型屏蔽了大量底层并行细节，容错处理， 数据分布，负载平衡（将这些设计细节放置于库中）我们的抽象模型的map 和 reduce最初灵感是来自于lisp这样的诸多函数式编程语言我们认识到绝大多数的计算关涉到“之于每一输入逻辑记录用于操作下一步的临时键值对的map操作”，这些计算的下一步就是运用reduce操作操作所有共享同一个键的变量，以恰当的合并分布数据我们使用用户定义的map和reduce函数模型，这一点使得我们得以对大规模计算并行化，同时重新执行重要的容错处理机制.该抽象模型的主要工作是形成了一个简单而强有力的接口，该接口允许并行自动化以及使得分布在通用PC之上的大尺度集群计算成为可能. 第二部分描述了基础的编程模型并给出了数个例子第三部分描述了合适我们集群计算环境的MapReduce接口实现。
第四部分给出了数个精巧的我们认为有用的程序模型第五部分是各种不同任务下的性能测试第六部分探索了运用MapReduce重写谷歌产品检索系统的情况第七部分给出相关的讨论以及未来的工作2.程序模型 计算任务是这样描述的：有一个键值对的集合作为输入，以及另外一个键值对的集合作为输出MapReduce 库的使用者将计算抽象表达为两种功能：Map和Reduce.Map由用户书写， 将键值对的一个集合作为输入，同时产出一个作为中间状态的键值对MapReduce库将所有拥有相同的键( 键I)的中间状态键合并起来传递到Reduce功能Reduce功能同样是由用户书写的，它接收一个中间键( 键I)以及有关这个键的键值集合，将这些值进行归并 merge以形成可能的更小的值集合典型的场景是每一个Reduce操作所唤起的只是0个或者1个最终输出值（键值）中间值是由用户的reduce功能使用的迭代器来支持的这就允许我们对相对于内存来说过大的值队列进行处理2.1例子 考虑这样一个问题：以一大堆文档为单位查找某个词语出现的词频用户可能象下面一样书写伪代码：map(String key, String value):// key: document name// value: document contentsfor each word w in value:EmitIntermediate(w, "1");reduce(String key, Iterator values):// key: a word// values: a list of countsint result = 0;for each v in values:result += ParseInt(v);Emit(AsString(result));map功能就产出单词，并对其出现的次数统计。
伪代码中的EmitIntermediate(w, "1")指的是出现1次，这里是特例Reduce功能统计每一个特定单词的出现次数 用户首先在mapreduce特定对象中结合输入输出文件编写代码，调整参数；其后唤醒MapReduce 功能， 将特定对象传递给它用户代码是和MapReduce库相绑定的（由C++ 语言实现）附录A包含了2.1例子的完整程序文本2.2类型 即便前例伪代码展示的是输入输出字符串，概念上由用户定义的map和reduce功能还支持以下类型：map (k1,v1) -> list(k2,v2)reduce (k2,list(v2)) -> list(v2)也既，输入的键值是从相对于输出键值的不同域中提取，进一步的，中间键值同输出键值都是来自于同一个域我们用C++实现了用户定义功能下的任意的字符串，并将置于用户代码的管辖，方便在string和任意类型之间转换2.3 更多的例子 这里展示了更多的简单程序，这些小程序很清晰易懂的表达了MapReduce的计算分布式grep: map 功能在匹配一给定模式时会产生一行同时reduce 功能是一种身份拣选机制，将中间键值对拷贝操作后转化为输出键值对。
URL接触词频统计：map功能处理网页日志请求以及输出 reduce 功能将所有属于同一个URL的值进行叠加并输出 三元组逆转网络链接图：map功能为每一个在命名了资源的页中能链接至target 的URL输出键值对reduce功能将所有关联于一给定的target URL的源URL列表进行拼接并产出键值对每主机的词汇向量：一个词汇/向量总结了出现在一个文档中的最重要单词，或者总结了出现在一个文档集合中的最重要单词，这个文档集合被表示成 列表map功能对每个输入的文档产生键值对（这里的主机名hostname是从输入文档的URL中提取的）reduce 功能被传递了“对给定主机的所有的前文档词汇向量”它将这些词汇变量加总起来，丢弃非高频词汇并最终产生键值对反转索引：map功能解析每一个文档， 同时产出的一个序列。
reduce 功能接收对一给定单词的所有键值对，对相应的文档ID排序，同时产生键值对 所有输出的键值对的集合形成了简单的反转索引通过追踪单词的位值，这种计算是容易增加的（augment）分布式排序：map功能将每个键从记录中提取出来，产生 键值对reduce 功能产生所有未经改变过的键值对这种计算是依赖与4.1节所述之设备分区，以及4.2节所述次序属性3.实现 MapReduce 接口的多种不同实现是可能的依赖于环境作出正确的接口实现选择比如， 其中一种MapReduce 接口可能的实现适用于小型共享内存机器， 另一种MapReduce 接口实现则适用于多处理器NUMA, 还有可能的一种MapReduce 接口的适用情况是大规模网络机器的集合 这一节描述了以谷歌内广泛使用的计算环境为背景的一种MapReduce 接口实现：由转换以太网链接起来的商用PC组成的大规模集群1. 典型的单台机器硬件环境是x86双核处理器，2到4GB内存，操作系统为linux2. 商用网络硬件典型在机器级别为100M/s 或1G/s， 但均值通常明显低于带宽的一半。
3. 一个集群由由数百或数千台机器构成，这种架构必然带来机器失效failure的情况4. 存储设备由不怎么昂贵的IDE磁盘组成（同台式电脑）一个谷歌内部开发的分布式系统[8]用于管理存储于这些机器磁盘上的数据5. 用户将作业job提交至排产系统(scheduling system)每一个作业由一系列任务集合组成( Each job consists of a set of tasks), 这些作业的每一个都由排产系统通过映射放于一个集群的可用机器集合中3.1 MapReduce鸟瞰 map的调用是通过自动将输入数据分区到M分裂(M splits) 集合，从而得以分布在多台机器之上分裂后的输入可由多台机器并行运算Reduce的调用是通过将中间键值对分区到R片(R pieces)来分散处理的，这种R片分区功能的例子如 hash(key) mod R 图一显示了MapReduce 操作的全局概览（我们所实现的MapReduce接口方式） 当用户程序调用MapReduce 时， 以下序列的动作依次发生（图一中的 数字记号与之对应）:（1）用户程序的MapReduce 库首先将输入文件分割成M个小片，典型的小片大小从16M到64M不等（由用户通过参数进行行配置。
然后在一集群上开启许多个分割程序拷贝2）上述的多个分割程序中的一个称之为 master. 其余的拷贝由Master赋予work. 有称之为M的 map任务和称之为R的Reduce任务master将唤醒空闲状态的work线程，并赋予其map任务或Reduce任务3）被赋予了map任务的工作线程读取相应的输入分割文件的内容，改工作线程解析输入文件的键值对并将其结果传送到用户在map功能中定义的键值对之中有map功能产生的中间键值对被缓存在内存当中4）被缓存的键值对周期性的写到本地磁盘之上， 由分区程序分块到R 个区域在本地磁盘上缓存着的键值对的地址被传递回master, 这个master主管着将上述地址传递给reduce工作线程5）一旦reduce工作线程被master通知到这些地址，它就用远程程序调用(remote procedure calls)读取本地磁盘上的map工作线程产生的缓存数据一旦reduce工作线程读取所有的中间数据， 它就对这些中间键值对按照键进行排序，一个自然的结果就是所有相同的group在一起了排序是必要的，因为许多不同的键将映射到相同的reduce任务如果这种排序对于内存中排序过大的话，就采用外部排序。
6） reduce 线程对经过排序的中间数据进行迭代遍历，将其遇到的每一个唯一中间键传送给用户定义的reduce功能，附带传送该键所对应的值的集合7）当所有的map任务和reduce任务全部结束， master 将唤醒用户程序就在此时，用户程序中的“MapReduce调用”返回用户代码 在成功的结束后， mapreduce的输出存在于R 输出文件中（每个reduce任务对应一个输出R文件，文件名由用户定义）典型情况下， 用户无需将R输出文件合并为一个文件， 他们通常将输。