MapReduce：Simplified Data Proessing on Large Clusters 阅读记录

本文是对论文《MapReduce：Simplified Data Proessing on Large Clusters》的记录. 这篇论文是Google的关于大数据的三篇论文之一, 主要介绍了一种新的编程模型, 即MapReduce模型. MapReduce模型也是之后开源的大数据处理系统Hadoop的主要实现基础.

前言

这是我真正意义上第一次阅读英文的论文, 本以为在语言方面可能会遇到一些问题, 然而实际阅读表明, 这篇论文的单词和语句难度大概只有英语四级水平, 因此这篇论文在阅读方面并不会有太多问题.

网络上关于这篇论文的介绍和中文翻译已经很多了, 本文主要介绍我在阅读过程中的一些见解和结论.

概述

MapReduce是一种编程模型, 用户（使用此编程模型的程序员）指定一个map函数将一系列的原始的键值对转化为中间状态的键值对, 之后用户再指定一个reduce函数, 将中间结果合并, 产生最终的结果.

很多操作都可以转化为MapReduce操作, 而且使用MapReduce模型之后, 系统就可以自动的将操作进行并行化, 从而充分利用分布式系统的资源. 根据论文, MapReduce的抽象灵感源于一种古老的函数式语言Lisp.

在Lisp语言中, map函数指定的操作运用到一个或多个列表之上, 从而获得一个新的列表, reduce函数将指定的操作依次作用到列表的各个元素上, 从而获得运算结果. 对比MapReduce模型中的map函数和reduce函数, 可见两者确实有一定的相似性.

在编程语言的发展历史之中, 由于函数式的语言特性的实现对机器性能的开销大, 因此很长一段时间内都没有投入实际的使用, 仅仅是“实验室”的产物. 然而随着并行计算的需要, 函数式语言天然的并行性使得其再一次被人们重视.

词频统计举例

WordCount在MapReduce中的地位就如同Hello World在编程中的地位, 是很多人写的第一个MapReduce程序. 因此下面从分析WordCount来讲解MapReduce的过程.

WordCount的任务是给定一个文本, 统计其中每个词出现的次数. 而且对于输入的文本系统会按照行自动进行切分. 例如给定如下的文本

1 2	Hello World Hello LiZeC Bye Hadoop Bye LiZeC

那么经过系统的处理以后, 会得到如下的两个原始键值对

1 2	<1,Hello World Hello LiZeC> <2, Bye Hadoop Bye LiZeC>

其中key为行号, value为每一行具体的内容. 那么对于map函数, 则可以有如下的操作(伪代码)

map(Object key,String value){
    // key代表行号
    // value代表每一行的值
    for each word w in value:
        EmitIntermediate(w,"1"); 
}

即对于每个词, 产生一个1的标记, 从而可以得到下面的一系列中间结果键值对

1	<Hello,1>,<World,1>,<Hello,1>,<LiZeC,1> ...

在reduce阶段之前, 系统会将所有相同的key合并到一起, 形成类似<key,<value1,value2,value3,...>> 的形式, 那么对于reduce函数有

reduce(String key,Iterator values){
    // key表示一个词
    // values表示所有统计值的列表
    int sum = 0;
    for each v in values:
        sum += v;
    Emit(key,sum);
}

即将所有键值对中的值累加起来, 从而获得最后的结果键值对

1	<Hello,2>, <World,1>, <LiZec,2>, ...

其他应用举例

在论文中给出了一些Google的实际应用, 以下介绍两个比较特殊的实现方案.

Distributed Grep

此操作的任务是给定一个正则表达式, 返回所满足条件的行.

在map阶段, 对于每一行, 如果匹配表达式, 则写入此行. 在reduce阶段不需要额外操作, 直接将中间结果写入即可.

Reverse Web-Link Graph

对于一个网页, 可以很容易的获得从此网页指向其他网页的关系图, 而Reverse Web-Link Graph任务反转这个关系图, 获得指向此网页的其他网页的关系图.

在map阶段, 对于每个网页source, 记录所有指向的其他页面target, 从而写入若干<target,source>的键值对. reduce阶段合并结果, 得到<target, list(source)>

错误处理

由于MapReduce是架构在大量设备之上的, 因此需要容忍部分机器出现故障. 故障可以分成工作节点故障, 主节点故障

工作节点故障

主节点会周期性的检测各个工作节点的状态, 如果工作节点在指定的时间内没有回应, 则主节点将此工作节点标记为故障状态, 并且自动将运行在上面的任务分配给其他机器执行.

论文中提到, 有一次对网络维修的时候, 导致80个节点同时从正在运行MapReduce的集群脱离, 但通过这种重新分配机制使得任务并没有受到影响.

主节点故障

主节点可以通过checkpoint技术, 周期的保存主节点的状态, 从而使得主节点故障时, 备份节点能从checkpoint恢复主节点的状态.

其他问题

Locality

MapReduce集群的底层文件系统是Google File System(GFS). GFS通常会将其中的数据冗余存储3份. 因此在分配map任务的时候, 会尽量将map任务分配到含有需要读取的数据的节点上, 从而执行任务时可以尽量从本地读取数据, 减少网络的消耗.

使用这一策略必然会导致某些存储了较多重要数据的节点计算任务变多, 因此后续可能还涉及到资源平衡的问题, 将经常使用的资源分布到不同的机器上, 从而均衡各个节点的任务强度.

Backup Tasks

根据论文, Google实现的MapReduce系统在处理即将结束时, 对于一些尚未完成分配的任务的机器, 会将相关机器上的任务重新分配到其他机器上同时执行, 根据相关的实验结果, 不使用这一操作的集群执行同样的任务多消耗44%的时间.

根据Google的分析, 导致这一现象的原因是部分机器的的性能降低, 降低的原因可能是磁盘故障, 机器被分配其他任务导致CPU可用时间减少, 或者代码错误等. 通过把相关的任务分配其他机器上重新执行, 可以减少上述问题导致的部分任务迟迟无法结束, 进而导致的总时间的延长.

实际上这一问题并不能直观的从理论上发现, 只能通过实际的运行才会发现. 而这种通过增加资源消耗来节省时间的策略也非常的具有工程师的特色了.

总结

严格的编程模型使得并行化和错误更加容易被处理
网络带宽资源是稀缺资源, 应该尽量减少网络传输
冗余的执行可以减少因为部分执行速度慢的设备导致的时间延长

最后更新： 2024年04月18日 13:26

原始链接： https://lizec.top/2018/08/09/%E8%AE%BA%E6%96%87MapRudece/

LiZeC的博客

通用性的代价是抽象