Google 三驾马车:MapReduce、GFS、Bigtable

MapReduce编程模型来自函数式编程,包含两个最基本的算子:map,reduce

将一个运算任务分解成大量独立正交的子任务,每个子任务通过map算子计算,得到中间结果,然后用reduce算子进行聚合,得到最终结果。

这两个算子有一个很重要的特征:确定性的纯过程调用(pure function),函数既不会修改输入,也不存在中间状态,也没有共享的内存。因此,输入一致的情况下,输出也是一致的,这大大方便了容错性设计。

系统中有两类主要的进程节点:master(单点),worker(多个)。其中,worker根据不同的计算任务,又分为map worker(对应上图中的Map phase)、reduce worker(对应上图中的Reduce phase)。

master是系统的中心节点,负责计算任务到worker节点的分配,同时监控worker节点的状态。如果某个worker计算太慢,或者宕机,master会将该worker进程负责的计算任务转移到其他进程。

map worker从GFS(google file system)中读取输入数据,然后将中间结果写到本地文件;reduce worker从master处得知中间结果的问题,通过rpc读取中间文件,计算之后将最终结果写入到可靠存储GFS。生产环境中,一个MapReduce过程的输出通常是另一个MapReduce计算的输入,类似Unix 的 pipeline,只不过unix pipeline通过stdin、stdout连接两个程序,而MapReduce使用GFS连接两个计算过程。

Scalability

由于计算任务的正交性,很容易通过增加map worker、reduce worker来处理计算任务的增长。Input file 到 Map phase这个阶段,使用了基于范围(range based)的分片方法,master作为元数据服务器会记录split到worker的映射关系。

Availability

系统对worker的容错性较好,但对master的容错性较差。

对于map worker,计算结果是写到本地文件,本地文件的位置需要通知到master,即使同一个task被多个map worker执行,单点的master只会采纳一份中间结果。而且上面提到了map function是pure function,所以计算结果也是一样的。

对于reduce worker,reduce task的计算结果会先写到临时文件(temporary file),task完成之后再重命名写入gfs,那么如果一个reduce task再多个reduce worker上计算,那么会不会有问题呢,答案是不会的

Performance

  1. data locality — 将任务调度到数据所在的节点进行计算,减少网络传输;

  2. backup task — master在发现某个worker上的task进展异常缓慢的时候,会将这个task调度到其他worker,以缩短这个任务(Job)的完成时间。

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章