讲座总结|解读大数据世界中MapReduce的前世今生


(suibiantell) #1

讲座嘉宾:Tim

讲座链接:【太阁直播】解读大数据世界中MapReduce的前世今生

讲座总结:6Kunnnnn

何为MapReduce?网络上很多官方的定义都过于抽象难懂了,希望通过以下的讲解,可以让大家能更简单地理解MapReduce的含义。

1. 背景:web检索的简单工作流程

MapReduce其实起源于web检索,我们常见的web检索可以简单分为两部分:获取网页内容并建立索引,和根据网页索引来处理查询关键词。

第一,获取网页内容并建立索引。这一步的实现需要用到两种程序,分别是:

  1. Crawler,别名Spider,网页爬虫程序,用来爬取互联网上的网页内容

  2. Indexer,索引器,对爬取下来的web内容建立索引,变成searchable content,这样网页就能被搜索了

需要解释一下,什么叫做索引器Indexer。我们可以简单理解为,互联网上每一个网页就是一个document,每个document都包含了不同的word,而我们针对每一个word,建立一个word出现在哪些document的table。

如下图,假设有document分别为1、2、3,里面分别有abc、xyz、def等词汇。而最终的Indexer结果就是将哪些word出现在哪些document ID中的映射保存下来,每一个word对应一个sorted list用来存储document ID。

![](data:image/svg+xml;utf8,)

第二,根据网页索引来处理查询关键词。如下图,当索引器被建立好了之后,每当有网页查询query进来,就需要利用这些索引,来处理query的关键词,找出那些同时含有这些关键词的文档。比如一个query里面同时有abc和bbb,那么含有这两个关键字的文档就是document 2。

![](data:image/svg+xml;utf8,)

2. MapReduce解决分布式web检索问题

自从互联网被创造后,被创建的网页和网站变的越来越多,数量极为庞大。像Google这样的web检索巨头如何保证能对互联网上大部分的web进行检索?答案就是并行parallel,或理解为数据量达到单机很难处理的程度,迫使采用运行多台机器来进行分布式计算。

![](data:image/svg+xml;utf8,)

如上图,我们横向上来看,每一台单机执行Crawler和Indexer任务,生成local index,最后汇总成global index。但是如果纵向上来看,Crawler和Indexer其实可以被分为两个独立的部分(因为他们的输入输出不同),而它们的中间联系就是,Crawler的输出其实就是Indexer的输入(web pages)。

所以如下图,对于每一个web获取+建立索引的任务(Job),我们把其中从web page到local index的部分当作是Map阶段,从local index汇聚到global index的部分当作是Reduce阶段。

![](data:image/svg+xml;utf8,)

所以我们可以简单理解为:MapReduce就是把复杂的分布式处理任务,简化分解成Map和Reduce两个阶段。

这样的programming model好处就是,我们能更简单的进行分布式程序的设计和实现了。但是,虽然有很多的好处,在MapReduce中,我们还需解决分布式系统的常见问题。比如网络问题,磁盘问题,程序本身问题,而且如果分布式系统出了问题也会很难解决恢复。因此,也就有了上述图片中的master的概念。简单说,Master是一个专门用来管理这些分布式系统的机器。那么,Master是如何进行分布式计算的管理呢?如下图:

![](data:image/svg+xml;utf8,)

在一个分布式计算集群(cluster)中,实际运行任务的是Slave机器,也被称之为DataNode(因为需要处理的data被存在了这些机器上),而Master机器负责任务的调度,也被称之为NameNode,之所以这样是因为它知道应该将哪个Task分配到哪个Slave机器上边运行(知道Slave和Task的name)。具体细节,Master中有一个Task queue,存储待执行的任务,每一个Slave有若干Task slots用来接收Master分配来的任务并执行。Master的Job Tracker和Slave的Task Tracker,用来监督每个Task执行情况,如果出现问题比如网络连接失败,或者程序出错,Master和Slave会有相应的措施来解决这些问题并恢复之前的任务进度。

所以,通过以上的任务调度方法,MR的厉害之处,就是把分布式系统的编程分成Map和Reduce两部分,同时解决了头疼的分布式计算问题。好处就是,开发者可以更多的注重程序的开发,而不需要太花时间解决分布式计算的种种问题。

当然,在MapReduce出现前互联网web检索还有别的解决方法,比如可以使用一台超级计算机来当作是super indexer,用来接受web pages作为输入,来建立global index,或理解为“shipping data to software”。这样做不是不行,但是把数量庞大的web pages传送到super indexer那里,仅仅是数据的传送就需要花费大量的时间。相比之下,MapReduce的方法可以理解为“shipping software to data”,也就是,DataNode负责存储数据,而NameNode负责将Task(software)传送给DataNode来执行。这样的方法,速度能提升好几个数量级,何况和一台超级计算机相比,购买很多个普通商用计算机来进行分布式计算要划算得多,扩展性也强。如下图:

![](data:image/svg+xml;utf8,)

此外,MapReduce更适合用来作non-Transactional的数据分析,也就是数据内容基本保持不变,而相比Transactional或者Real-time的数据就会持续的更新,每次数据分析都是按batch process,一次大量时间长。

3. MapReduce和HDFS

HDFS,Hadoop Distributed File Systems,是根据Google著名的GFS的论文实现的开源项目,其实Hadoop也是Google另外一篇MapReduce论文的具体实现。所以我们可以理解为Hadoop就是HDFS和MapReduce

![](data:image/svg+xml;utf8,)

简单说,HDFS解决了分布式系统很多问题,特别是数据副本replication和恢复recovery问题,它类似于UNIX系统,提供了很多文件系统的抽象接口,这样广大熟悉UNIX系统的人能够很快上手。那么MapReduce是如何与HDFS配合的呢?如下图:

![](data:image/svg+xml;utf8,)

首先,在Map阶段之前,Map程序的输入需要进行一些操作。HDFS在存储文件的时候,并没有把一个文件当做一个整体,而是利用按照一定大小(默认为64MB)的chunk来保存文件,每一个chunk可能有一个或者多个文件,比如chunk1含有文件1、2和3的一部分,chunk2含有文件3的另一部分,以及其他文件。所以在从chunk读入输入文件之前,需要对这些chunk里面的文件进行split,即将同一文件在不同chunk中的部分split到一起,再通过RecordReader来将文件读成Key Value Pair的输入交给Map程序。

之后,得到了每一台机器上的Map程序的输出,需要将这些机器的输出结果shuffling到不同机器的Reduce程序上进一步运算。首先一步就是进行Partition,或者理解为将不同台机器的输出数据Group-By-Key,在对同一Key中所有数据Sort,之后的结果会被分配到不同机器上的Reduce程序中,这样会进一步加快Reduce程序的速度。

4. MapReduce的扩展延伸

我们之前所讨论的内容,实际上是第一代的MapReduce,基本是基于Google的论文实现的。在1.0中,Master负责了任务调度的全部工作,这样的后果就是Master会很臃肿(功能太多),以及在同一个集群cluster上Master只能负责MapReduce相关的分布式计算的调度,无法负责别的程序。而现在更流行的是MapReduce 2.0,在1.0的基础上进行了不少的改动,最大的变化就是YARN的引入。YARN全称为Yet Another Resource Negotiator,主要功能就是替代NameNode的任务调度功能,主要的好处就是简化了Master的工作量使得其不再过与臃肿,另一方面就是除了MapReduce之外,还可以在同一个集群上运行别的application,比如现在很流行的Spark。

而Spark,大家都说比MapReduce快很多,但是其底层的实现还是类似于MapReduce分布式的计算方式,但更多的是做出了很多的性能优化,特别就是RDD(Resilient Distributed Dataset)的引入,一种对分布式数据的抽象。传统的MapReduce需要大量的磁盘读写操作和网络的传输,比如Split、RR、Partition等等,都会涉及将中间计算结果在不同机器之间网络传输并存到disk上作为之后pipeline的输入的操作。但是Spark之所以快,是因为Spark采取的更多的是将RDD,也就是分布式数据保存到Memory里进行计算,而且是一种lazy evaluation计算方式,也就是必要的时候一口气将内存中的某个计算过程pipeline执行完毕,而不是像MapReduce一样,一步一步计算、每步都将中间结果保存到磁盘上、之后下一步再读入的方式来进行,这样会节省大量的disk IO时间。如果pipeline的某一个中间步骤失败了,Spark有一个RDD的workflow图,用来找回之前失败的RDD从新计算,即便从新计算也很可能比磁盘IO的开销要小很多,毕竟内存要比disk快很多。

但是Spark也并不一定能完全替代MapReduce,相比于MapReduce,Spark更适合real-time的数据处理,因为需要较快的响应速度,或者iterative算法比如K-means,即不断地对同一组数据进行同一个算法的迭代处理,然而MapReduce更适合于数据量非常大的batch process,因为Spark对内存要求的确是比较的高。当然Spark并不一定需要依赖于HDFS上边运行,也可以在别的distributed storage layer上。

总之,MapReduce从第一代,到第二代再到之后其他类似平台的发展,可以看出MapReduce的生命力,以及对分布式处理的巨大贡献。而希望读完这篇文章,大家也对MapReduce的前世今生有了大致的理解。

其它细节补充

对于互联网crawler程序,之所以又叫做爬虫spider,因为程序就好像在爬(traverse)互联网。但存在一些独立的网页无法检索到(比如公司内部网络)。而且爬网站需要选好seed网站,比如新浪门户,因为有很多链接指向外部网络,但是百度可能就不适合爬网站的seed网站,因为缺少外部的链接。

分布式数据库的CAP理论,针对不同领域需要有不同的取舍。比如银行转账,需要保证一个cluster中,各个机器node之间银行数据信息是consistent的,比如无论访问哪个node的银行账单数据,结果都需要是一样的,否则用户可能得到错误账单。然而search engine更强调available,就是要有在一定时间内有结果返回,不要让用户等待太久,虽然每次查询的结果可能不都是consistent的数据。

BitTiger近期课程,火热报名,免费试听:

如何设计实现一个实时PokemonGo小精灵地图?

互联网公司职场进阶不可不知的那些事儿

更多精彩,尽在硅谷高端线上教育社区BitTiger:请猛戳我

公众号:论码农的自我修养

微博:@太阁BitTiger

今日头条:太阁BitTiger