MapReduce解读

MapReduce

分布式系统系列

    MapReduce，学习分布式系统必读的经典佳作，写在本系列的开篇。文章按该paper的思路解析Map Reduce编程模型核心思想和关注点、案例及其实现

MapReduce简介

    Google搜索引擎每天处理大量的原始数据，网络爬虫、Web请求日志等，以计算各种派生数据，反向索引、Web文档的图形结构、页面数量摘要、热词集。概念上来说这类计算很简单直观，然而输入数据集通常很大，计算必须被分布在跨数百或数千台机器上进行，以便在合理的时间内完成。如何并行化计算、分发数据、处理故障，共同构成大量复杂的代码来解决这些原始简单直观的计算问题

    为应对这种复杂性而设计出一个新的抽象，允许表达我们试图执行的简单运算，隐藏库中并行化、容错、数据分布和负载平衡的混乱细节。抽象的灵感来源于Lisp和其他函数式语言的map和reduce原语

    Google公司于2004年发表的论文 -- MapReduce:Simplified Data Processing on Large Clusters(原著地址 https://static.googleusercontent.com/media/research.google.com/zh-CN//archive/mapreduce-osdi04.pdf)，是一种用于处理和生成大规模数据集的编程模型及其相关实现。用户指定Map函数和Reduce函数，Map函数用于处理键/值对以生成一组中间键/值对的映射，Reduce函数合并所有被相同中间键关联的中间值。该模型可以表达许多现实世界的任务

    以这种函数风格编写的程序可以自动化并行地在大规模商用机器集群上执行。运行时系统负责输入数据分区的细节，调度程序跨集群机器集执行，处理集群故障，管理机器之间的通信请求。使得没有任何并行和分布式系统经验的程序员可以很容易地利用大型分布式系统的资源

   MapReduce是一个简单而强大的接口，可实现大规模自动并行化和分布式计算，并结合此接口的实现，在大规模商用PC机集群上实现程序高性能且具有高度可扩展性运行

MapReduce抽象模型及Examples

    这种计算方式以一个键/值对集合作为输入，产生一个键/值对作为输出。用户的MapReduce库将计算表达为两个函数: Map和Reduce

    Map函数，由用户编写，采用一个输入对然后产生一个中间键/值对集合。MapReduce库将所有与相同中间键K相关的中间值传递给Reduce函数

    Reduce函数，也由用户编写，接收中间键K和这个K键关联的一组值。它将这些值合并在一起形成一组可能较小的值。通常一次Reduce调用只产生零个或一个输出值。中间值通过迭代器提供给用户的Reduce函数，这允许我们处理太大而不适合内存的值列表

MapReduce抽象视图

MapReduce APImap(k1, v1) -> list(k2, v2)reduce(k2, list(v2)) -> list(k2, v3)​# 输入被f分割成 M 个分片 Map生成 K-V 对的行，Reduce按列消耗Input1 -> Map -> (a, 1), (b, 1), (c, 1)Input2 -> Map ->         (b, 1)Input3 -> Map -> (a, 1),         (c, 1)                  |        |      |                   |        |       --> Reduce -> (c, 2)                  |         ---------> Reduce -> (b, 2)                   ------------------> Reduce -> (a, 2)# 对每一个输入 MR 调用 Map()生成 (k2,v2) 中间键/值对集合，每一个 Map()调用都是一个 Task# 对于给定的 k2, MR 收集所有与中间键 k2 相关的 v2,将它们传递给Reduce调用# 最终，Reduce输出一个 <k2, v3> 集合存储在输出文件 R 中

Examples: 计算大量文档中每个单词出现的次数

# 输入是数千个文本文件Map(string key, string value)  // key 文档名  // value 文档内容  split value into words;  // 对文本内容v进行分词  for each word w    EmitIntermediate(w, "1");Reduce(string key, Iterator values)  // key 一个单词  // values 计数列表  int result = 0;  for each v in values:    result += ParseInt(v);  Emit(AsString(result));

More Examples

Distributed Grep​Count of URL Access Frequency​Reverse Web-Link Graph​Term-Vector per Host​Inverted Index​Distributed Sort

实现目标及核心关注点

MapReduce 实现流程图

MapReduce接口可能有多种不同的实现方式，需根据具体的计算环境来选择

以Google的常用计算环境为例

1.机器配置 Linux dual-process x86 2-4GB Memory

2.网络硬件 100/1000 MB/s, 平均整体二分带宽少很多

3.集群 由数百、数千台机器组成，机器故障很常见

4.存储由连接到每个机器的廉价IDE磁盘提供，它们内部开发的分布式文件系统用于管理这些磁盘上的数据。文件系统使用副本在不可靠的硬件之上提供可用性和可靠性

5.用户提交Job到调度系统，每个Job由一组Tasks组成，并由调度器将每个Task映射到机器中一组可用计算机上执行

MapReduce实现流程

Map调用被分布在多台机器，输入数据被自动划分为M个分割，输入分割之间没有交互，可以在不同机器上并行处理。使用分区函数(e.g. hash(key) mod R)，将中间键空间划分为R个片段分发给Reduce并行调用，分区函数和分区数由用户指定。用户调用MapReduce函数的系列操作如下

1.Split Input FIles 将输入文件按指定大小S(16~64MB,用户通过可选参数指定)划分为M个分割文件，然后在集群中启动多个副本程序

2.Assign Tasks Master挑选空闲Worker节点并为其分配一个map task或reduce task

3.Parses K/V 被分配map task的worker读取相关分割的内容,从输入内容中解析键/值对并生成中间键/值对缓存于内存中

4.Written to Local Disk 缓存的中间键/值对，通过分区函数划分为R个区域，定期写到本地磁盘并将其相对位置返回给Master，Master再将这些位置信息传给Worker

5.RPC Read and Sort 当Master将位置信息通知到Reduce Worker, Reduce Worker使用远程过程调用从Map Worker的磁盘读入缓存数据。当Reduce Worker读入所有的中间数据按key排序，如果中间数据过大不适合在内存运算，可考虑使用外部排序

6.Iterates and Appended Reduce Worker对已排序的中间数据进行迭代，对于每一个唯一的中间键，它将与之对应的中间值集传递给用户的Reduce函数。将Reduce函数的输出Append到这个reduce分区的最终输出文件

7.Completed 完成所有map和reduce任务后master唤醒用户程序

代码实现的核心关注点

1.关于容错

Master Failure

    定期checkpoint,备份Master数据结构信息,副本可以从checkpoints快速恢复

Worker Failure

    Master定期ping每一个worker,如果在一个确定的时段内没有收到worker的响应,master标志该worker状态为failed.该节点上所有 completed map tasks 和 in progress reduce tasks 重置为初始idle状态,调度器可以将它们调度到其他worker节点.map task的输出数据存储在本地磁盘,因此Failed Worker上已完成的map tasks必须被重新执行;completed reduce tasks不需要被重新执行,因为它的输出文件保存在GFS

Semantics Failures

    依靠原子提交Map和Reduce任务的输出来保证non-faulting sequential.对于已完成的Map任务,Worker向Master发送包含R个临时文件的消息,如果Master接收到一个完整的消息则忽略之,否则在Master的数据结构中记录这R个文件的名字;当一个Reduce任务完成,reduce worker对临时输出文件原子性地重命名为最终文件

2.本地/就近调度,减少网络开销

3.任务粒度

    假设Map阶段产生M个片段、Reduce阶段产生R个分片,M和R应该远远大于集群中worker的数量.实现动态负载均衡...

4.备份任务

    在执行一个MapReduce操作时，可能会存在一些落后者拉长整个任务的完成时间。针对这个问题的优化方法是: 当一个MapReduce操作接近完成时，Master调度器备份仍然处于in-progress状态的tasks，将它们标注为completed。这个调优机制提升44%左右的计算资源使用率

小结

    MapReduce编程模型被成功应用于许多不同场景，总结其成功的几个原因: 第一，易于使用，它隐藏了并行、容错、本地优化、平衡负载等细节，即使没有任何分布式和并行编程经验的程序员也容易上手; 第二，很多问题容易被MapReduce模型表示; 第三，已实现MapReduce模型(e.g. Hadoop)用于上千台机器的集群计算