Map Reduce

Map Reduce 的意义

集群

在传统的单节点模型中,CPU从内存读取数据,当内存空间不够时,再从磁盘读取数据,当磁盘空间不够了呢?

即使磁盘空间足够,磁盘带宽是50MB/sec,若从磁盘读取200TB数据,大约需要46+天,完全没法接受呀!

需要这样一个集群……

IMG

优点(解决困难)

节点故障(node failures)

如果单个服务器能坚持3年(1000天),1000台服务器的集群平均每天大概发生1次故障,1M台服务器的集群平均每天大概发生1000次故障。节点故障时亟须解决的问题:

  • 如何存储数据,即使节点故障时仍可用?
  • 若正在进行大规模计算,如果节点发生故障该如何处理?

Map Reduce在多个节点冗余存储,保证数据持久存储和获取。

网络瓶颈(network bottleneck)

Map Reduce的计算靠近数据端,减少数据移动。

分布式程序编写困难

Map Reduce简单的编程模型,隐藏了复杂的细节。

Map Reduce 简介

冗余存储架构

冗余存储架构采用分布式文件系统(distributed file system),例如:Google GFS、Hadoop HDFS。典型的应用是处理大文件,一次存储多次读取追加更新。

IMG

数据分块(chuck)存储在多台服务器。如上图所示,一个大文件分割成C0~C5共6块,每块在多台服务器存储备份。每台存储服务器也做计算用,使得计算靠近存储端。

计算模型

1
2
3
4
5
6
7
8
9
输入:key-value对的集合 

- Map(k,v) —> <k’, v’>*
- 输入一个key-value对,输出多个key-value对;
- 对所有的(k,v)对,只有一个Map函数。

- Reduce(k’, <v’>*) —> <k’, v”>
- 所有的具有相同k’的v’都被reduce到一起;
- 对同一个k’,只有一个Reduce函数。

Map-Reduce的计算模型分为Map和Reduce两步,Map分布式处理任务,Reduce合并任务。

IMG

上图展示了用Map-Reduce统计超大规模文件中单词出现次数,红色横线将不同节点的实现分割开。对于Map节点,所有相同单词都输出到同一个节点,比如the都在第二个节点。为了保证效率,Map-Reduce都采用的是顺序读取。

调度与数据流

IMG

Map-Reduce的数据流:

  • 输入输出存储在分布式文件系统;
  • 中间结果存储在本地文件系统;
  • 输出通常再输入到另一个Map-Reduce任务。

IMG

上图是Map-Reduce分布式系统的并行实现,Partition Function部分采用Hash算法,将相同key的value映射到同一节点。

Map-Reduce环境的主要任务:

  • 分割输入数据;
  • 多机之间程序调度;
  • 执行按key分组操作;
  • 处理节点故障;
  • 处理多机间通信。

Map Reduce的实现分为Master节点、Map节点和Reduce节点,Master节点的任务:

  • 管理每个任务状态:空闲(idle,等待处理)、处理中(in-progress)、completed(结束);
  • 将空闲任务安排到可用节点;
  • 当Map任务结束,向Master发送其R中间文件(存放在本地文件系统中)的位置和大小,每个reducer一个中间文件;
  • Master推送信息到Reducer;
  • Master周期性ping检测节点是否出故障。

Map Reduce系统有M个Map任务和R个Reduce任务,M比集群中的节点数目大得多,R通常比M小。

Map Reduce 的改进

合并操作

IMG

通常在一个Map任务中会产生多个相同key的(k,v)对,在Map节点合并这些相同的key可有效降低网络流量,如上图所示。合并函数通常与Reduce函数相同。

合并时需要注意Reduce函数是否支持在Map节点的合并操作,也就是合并操作会不会改变Reduce的结果。

改写分割函数

例如:系统采用的默认分割函数hash(key) mod R可以改写为hash(hostname(URL)) mod R,使同一个主机的url输出到相同的文件。



本文链接: http://home.meng.uno/articles/25d9ef10/ 欢迎转载!

© 2018.02.08 - 2020.10.14 Mengmeng Kuang  保留所有权利!

UV : | PV :

:D 获取中...

Creative Commons License