背景
Google发表了MapReduce计算范型及其框架的论文。MapReduce和并行数据库系统(MPP)各有优劣并且两者有一定的互补和学习。与传统MPP架构相比，MapReduce更适合非结构化数据的ETL处理类操作，并且可扩展性和容错性占优，但是单机处理效率较低。
DAG计算模型是MapReduce计算机制的一种扩展。MapReduce对于子任务之间复杂的交互和依赖关系缺乏表达能力，DAG计算模型可以表达复杂的并发任务之间的依赖关系。
Spark本质上是DAG批处理系统，其最能发挥特长的领域是迭代式机器学习。
MapReduce计算模型与架构
计算模型
MapReduce计算任务的输入是Key/Value数据对，输出也以Key/Value数据对方式表示。开发者要根据业务逻辑实现Map和Reduce两个接口函数内的具体操作内容，即可完成大规模数据的并行批处理任务。
实例一:单词统计
map(String key, String value):
//key: 文档名
//value: 文档内容
for each word in value:
Emit Intermedia(w, "1");
reduce(String key, Iterator values):
//key: 单词
//value: 出现次数列表
int result = 0;
for each v in values:
result += ParseInt(v);//累加values值
Emit(AsString(result));
实例二: 链表反转
map(String source_url, Iterator outlinks):
//key: 网页url
//value: 出链列表
for each outlink o in outlinks:
Emit Intermedia(o, source_url)
reduce(String target_url, Iterator source_urls):
//key: target网页url
//values: source网页url
list result = [];
for each v in source_urls:
Result.append(v);
Emit(AsString(result));
实例三: 页面点击统计
map(String tuple_id, String tuple):
Emit Intermedia(url, "1");
reduce(String url, Iterator list_tuples):
int result = 0;
for each v in list_tuples:
result += ParseInt(v);
Emit(AsString(result));
系统架构
处理流程:
- MapReduce框架将应用的输入数据切分成M个模块，典型的数据块大小为64MB，然后可以启动位于集群中不同机器上若干程序。
- 全局唯一的主控Master以及若干个Worker，Master负责为Worker分配具体的Map任务或Reduce任务并做一些全局管理。
- Map任务的Worker读取对应的数据块内容，从数据块中解析一个个Key/Value记录数据并将其传给用户自定义的Map函数，Map函数输出的中间结果Key/Value数据在内存中缓存
- 缓存的Map函数产生的中间结果周期性写入磁盘，每个Map函数中间结果在写入磁盘前被分割函数切割成R份，R是Reduce个数。一般用key对R进行哈希取模。Map函数完成对应数据块处理后将R个临时文件位置通知Master，Master再转交给Reduce任务的Worker
- Reduce任务Worker接到通知时，通过RPC远程调用将Map产生的M份数据文件pull到本地。(只有所有Map函数完成，Reduce才能执行)。Reduce任务根据中间数据的Key对记录进行排序，相同key的记录聚合在一起
- Reduce任务Worker遍历有序数据，将同一个Key及其对应的多个Value传递给用户定义的Reduce函数，reduce函数执行业务逻辑后将结果追加到Reduce对应的结果文件末尾
- 所有Map、Reduce任务完成，Master唤醒用户应用程序
为了优化执行效率，MapReduce计算框架在Map阶段还可以执行Combiner操作。
hadoop的MapReduce运行机制基本与google的类似。
不同的是，hadoop采用https协议来进行数据传输，并采用归并排序对中间结果进行排序。
Google的MapReduce框架支持细粒度的容错机制。Master周期性Ping各个Worker，如果Worker没有响应，则认为其已经发生故障。
如果Master故障则单点失效，重新提交任务。
MapReduce不足
- 无高层抽象数据操作语言
- 数据无Schema及索引
- 单节点效率低下
- 任务流描述方法单一
优势:
- 数据吞吐量高
- 支持海量数据处理的大规模并行处理
- 细粒度容错
但是不适合对时效性高的应用场景，比如交互查询或流处理，也不适合迭代计算类的机器学习及数据挖掘类应用。
由于:
- 启动时间长
- 多处读写磁盘及网络传输
DAG计算模型
有向无环图的简称。在大数据处理领域,DAG计算模型是将计算任务在内部分解成若干子任务，这些子任务之间由逻辑关系或运行先后顺序等因素被构建成有向无环图结构。
DAG计算系统三层结构
- 最上层是应用表达层，通过一定手段将计算任务分解成若干子任务形成的DAG结构
- 最下层是物理机集群，由大量物理机器搭建的分布式计算环境
- 中间层是DAG执行引擎层，将上层以特殊方式表达的DAG计算任务通过转换和映射，将其部署到下层的物理机集群中运行
Dryad
微软DAG计算系统，dryad在实现时以共享内存、TCP连接以及临时文件的方式进行数据传输
Dryad整体架构
job manager负责将逻辑形式存在的DAG描述映射到物理机。NS负责维护集群中当前可以的机器资源。Daemon守护进程作为JM在计算节点上的代理，具体负责子任务的执行和监控。
FlumeJava和Tez
- FlumeJava构建了java库，本质上是在MapReduce基础上的DAG计算系统，图中每个节点可以看作单个MapReduce子任务。
- Tez使用Map任务或者Reduce任务作为DAG的图节点，图节点的有向边是数据传输通道。Tez消除Map阶段中间文件输出到磁盘过程以及引入Reduce-Reduce结构改进措施提升执行效率