《数据密集型计算和模型》第四章

《数据密集型计算和模型》第四章的有关内容。主要有MapReduce模型简介、概念及原理、工作机制、优缺点；基于MapReduce模型的实现，改进等。

文章目录

• 一、MapReduce模型简介
• • 1. MapReduce模型概念及原理
  • 2. MapReduce工作机制
  • • （1）MapReduce作业的工作机制
    • • 主节点（master）
      • 数据分片（Data split）
      • Map端
      • Shuffle&Sort
      • Reduce端
    • （2）容错机制
    • • 工作节点容错
      • 主节点容错
      • 任务语义容错
    • （3）负载平衡
    • • 作业调度
      • 任务本地调度
      • 任务备份
      • 计数器
  • 3. MapReduce模型的优缺点
  • • （1）优点
    • （2）缺点
• 二、基于MapReduce模型的实现
• • 1. Hadoop
  • • （1）hadoop简介
    • • 基于Hadoop的项目主要包括：
      • Hadoop优点（*）：
    • （2）HDFS
    • • HDFS概念
      • 文件操作
    • （3）Hadoop工作流
    • （4）hadoop的容错
    • • 任务失败
      • JobTracker失败
      • TaskTracker失败
  • 2. Phoenix
  • 3. 其他实现
• 三、MapReduce模型的改进
• • 1.Spark
  • • （1）Spark概念及架构
    • （2）Spark抽象组成
    • • 弹性分布式数据集（RDD）
      • 并行操作
      • 共享变量
  • 2. Data Freeway 和 Puma
  • • （1）优化数据通道
    • （2）优化数据的处理系统
    • • Puma2
      • Puma3
  • 3. Storm
  • • （1）Storm概念及原理
    • （2）Storm组件
    • • Topologies
      • Streams
      • Stream Groupings
  • 4. Nephele/PACTs
  • 5. 其他改进工作
  • • （1）Barrier-less MapReduce
    • （2）Map-Reduce-Merge
    • （3）KPNs
    • （4）Oivos
• 例子理解

一、MapReduce模型简介

将待解决的数据集分解 成若干个可以继续并行处理的小数据集，使分布式并行程序的编写变得更加简单。

1. MapReduce模型概念及原理

• map：分解
• reduce：组合

最初的设计方案是：将MapReduce模型运行在一个低端的计算机组成的集群上。集群中每台计算机包含一个工作节点（Worker）、一个较快的主内存和一个辅助寄存器。

• 工作节点：用于数据的处理
• 主内存：用于暂存工作节点的输出数据
• 辅助寄存器：组成了集群的全局共享存储器，用于存储全部的初始数据和工作节点的输出数据。
• 并且计算机之间可以通过底层网络实现辅助存储器的同步远程互访。

• 一个MapReduce作业由map和reduce两个阶段组成。
• 每一个阶段包括 数据输入、计算处理 、 数据输出 三个步骤。

2. MapReduce工作机制 （1）MapReduce作业的工作机制 主节点（master）

MapReduce模型将MapReduce作业（job）分成若干个任务（task）来执行。其中，MapReduce作业作为客户端执行的一个工作单元，主要包括 输入数据、MapReduce程序和配置信息。任务主要包括Map和Reduce两类。

• 主节点对每一个Map任务和Reduce任务的状态（空闲、工作中或完成）和工作节点（非空闲任务）的标志进行存储，并负责将Map任务产生的中间数据存储区域的位置信息传递到Reduce。
• 另外，主节点内部含有一个HTTP服务器，用于输出MapReduce执行的状态报告。

数据分片（Data split）

在文件被处理之前，MapReduce库首先将输入文件划分为M片，然后将每个数据片保存在多个节点上，在集群中形成多份拷贝。

MapReduce支持的几种格式输入：

1. 输入分片与记录
2. 文本输入
3. 二进制输入
4. 多种输入
5. 数据库输入
6. KeyValueInputFormat

Map端

数据划分结束后，MapReduce作业首先为每一个分片构建一个map任务（Map任务的数量由数据分片数量所决定，将数据分片成一一对应或多对一的关系）

然后由该任务执行使用者定义的Map函数

Map的工作流程：

1. 数据输入：工作节点执行Map任务时，首先读取分片数据，从输入数据中抽取对；然后将每个对作为参数传递给Map函数。
2. Partition：根据key或value及Reduce的数量来解决当前的 对的归属问题（即要放到哪个reduce里）
3. 数据溢出写（Data split）：当Map任务的输出结果超出内存的存储能力时，需要在一定条件下将缓冲区中的数据临时写入磁盘，然后重新利用这块缓冲区。（超出内存后溢出才写入磁盘）
4. 聚合（Merge）阶段：在任务完成之前，将溢出写文件合并成一个已经分区且排序的输出文件，使Map任务最终只输出一个溢出写文件。（任务执行结束后可以会产生多个溢出写文件，故需要合并增加速度）
5. 写入本地存储器：最后，Map任务将其输出结果临时写入本地磁盘。作业完成后Map的输出结果将被删除（因为是MapReduce的中间结果）

Shuffle&Sort

Shuffle&Sort主要描述数据从Map任务输出到Reduce任务输入的过程，并确保每个Reduce任务的输入都按键排序。

• Shuffle&Sort过程需要保证数据完整地从Map端传输到Reduce端，并且在跨节点读取数据时，尽可能地减少对带宽的不必要消耗，同时还要减少磁盘I/O 对任务执行的影响。

Reduce端

1. 复制阶段：Reduce进程启动数据Copy线程并行获取Map任务的输出文件（Map任务已结束，这些文件存储在本地磁盘中）。
2. 聚合（Merge）阶段：当所有的Map输出被复制完成后，Reduce任务进入排序阶段。如果Map输出小于内存，输出结果被复制到Reduce工作节点的内存，否则被复制到磁盘。
   1. 聚合的三种形式：内存到内存、内存到磁盘、磁盘到磁盘
3. Reducer的输入文件：经过多次聚合后生成一个存储于磁盘后内存中的文件，默认存放在磁盘中。
4. 写入输出文件：最后，执行Reducer将输出结果直接写到分布式文件系统上。

（2）容错机制 工作节点容错

• 主节点周期性地ping每个工作节点，如果在约定的时间范围内未接受到工作节点的返回信息，此工作节点将被主节点标记为失效。
• 当一个Map任务首先被工作节点A执行，之后由于工作节点A失效被调度到工作节点B执行，“重新执行”的信息会被发送到所有执行Reduce任务的工作节点，将需要从工作节点A读取数据的Reduce任务转向从工作节点B读取。

主节点容错

• 主节点会周期性地将其数据写入磁盘，并建立检查点，如果主节点任务失效，可从最后一个检查点启动另一个主节点进程。
• 目前采用的方法是，如果主节点失效，立即中止MapReduce运算，使用者通过此状态信息重新执行MapReduce操作。

任务语义容错

• 由于Map和Reduce任务的输出是原子提交，并且每个作业中的任务将它的输出写到私有临时文件中（每个Map任务生成R个此类文件，每个Reduce任务生成一个此类文件）
• 当一个Map任务完成时，工作节点向主节点发送一个包含R个临时文件名的完成消息。
• 当Reduce任务完成时，Reduce工作节点进程以原子的方式把临时文件重命名为最终输出文件。

（3）负载平衡 作业调度

采用作业调度器管理使用者提交的多个作业，可最大限度实现使用者之间资源分配的公平性。

1. FIFO先进先出：实现简单，集群调度开销较少，最大的缺点是在MapReduce模型中存在大作业情况下小作业响应时间较长。
2. HOD：hadoop on Demand，改善对小作业的响应时间，但是较差的数据本地化和较低的资源利用率。
3. 公平调度算法：最大限度的保证每个使用者都获得相等的资源份额
4. 能力调度：针对多使用者调度，采用多个队列组成集群。

任务本地调度

• 主节点在调度Map任务时，首先判断输入文件的位置信息，优先将Map任务分配到包含其输入数据拷贝的节点上执行。
• 如果失败，主节点将尝试在存有其输入数据拷贝的节点的附近机器上执行。

任务备份

MapReduce模型将作业分解成多个可并行执行的任务。

当MapReduce代码的执行效率变慢时，会触发**“推测执行”机制**

推测执行机制的过程：

• 首先，启动某一作业的所有任务，等待作业运行一段时间后判断任务的平均进度
• 然后，重复启动一个比平均进度慢的任务作为推测任务
• 最后，当有一个任务成完成后，任何正在运行的重复任务都将被中止，如果原任务在推测任务之前完成，推测任务将被中止，否则，原任务被中止。

计数器

计数器是一种收集作业统计信息的有效手段。

• 第一，用于统计不同事件发生的次数
• 第二，对操作的完整性进行检查。
• 在累加计数器值时，主节点首先检查重复运行的Map或者Reduce任务，避免重复累加。

3. MapReduce模型的优缺点 （1）优点

1. 硬件要求低
2. 接口化
3. 编程语言多样化
4. 扩展性强
5. 数据分析低延迟

（2）缺点

1. 无法达到数据实时处理
2. 程序员负担增加
3. I/O代价较高

二、基于MapReduce模型的实现 1. Hadoop

Hadoop是一个开源的可运行在大型分布式集群上的并行计算框架，主要由HDFS和MapReduce模型组成，其编程语言包括java、c、c++、Python、shell、PHP、ruby等

（1）hadoop简介 基于Hadoop的项目主要包括：

1. Common：一组分布式文件系统和通用I/O的组件与接口。
2. Avro：一种支持高效、跨语言的RPC以及永久存储数据的序列化系统。
3. Pig：一种数据流语言和运行环境，运行在MapReduce和HDFS的集群上。
4. Hive：一个分布式、按列存储的数据仓库，管理HDFS中存储的数据，并提供SQL的查询语言用于查询数据
5. Hbase：一个分布式、按列存储的数据库，使用HDFS作为底层存储，同时支持MapReduce的批量式计算和点查询（随机读取）
6. ZooKeeper：一个分布式、可用性高的协调服务。
7. Sqoop：一个在数据库和HDFS之间高效传输的数据工具。

Hadoop优点（*）：

1. 高可靠性
2. 高扩展性
3. 高效性
4. 高容错性

（2）HDFS HDFS概念

HDFS是hadoop的分布式文件系统，与MapReduce结合使用。

• hadoop主要采用HDFS系统对文件进行创建、删除、移动以及重命名等操作。
• HDFS架构由一个NameNode和大量DataNode组成，并且其内部通信采用标准的TCP/IP 协议。

NameNode

• NameNode是一个运行在单独机器上的软件，负责管理文件系统命名空间，维护系统内的所有文件和目录。

DataNode

• DataNode是一个运行在单独机器上的软件，通常以机架的形式进行组织，并且机架通过一个交换机将所有系统连接起来。
• DataNode主要用于响应来自HDFS客户机的读写请求和NameNode对块的创建、删除和复制命令。

文件操作

hadoop的本质是一个批处理系统，数据被引入HDFS并分发到各个节点进行处理。

（3）Hadoop工作流

hadoop工作流由客户端、JobTracker、TaskTracker、HDFS四个独立部分控制。

1. 提交作业
2. 复制资源
3. 作业初始化
4. 任务分配
5. 执行任务
6. 更新进度和状态
7. 完成作业

（4）hadoop的容错 任务失败

1. 子任务失败
2. 流任务失败
3. 子进程失败
4. 任务挂起

JobTracker失败

一旦JobTracker失败整个任务需要人为重新启动

TaskTracker失败

如果一个TaskTracker由于崩溃或运行过于缓慢而失败，将停止向JobTracker发送“心跳”，并且当TaskTracker超过时间间隔没有向JobTracker汇报心跳时，JobTracker则视之为死亡。

2. Phoenix 3. 其他实现

1. MapReduce.NET
2. Cell MapReduce
3. Skynet
4. GridGain
5. Misco
6. Mars
7. FPMR
8. Ussop

三、MapReduce模型的改进 1.Spark （1）Spark概念及架构

Spark是一种基于MapReduce算法的分布式计算框架。

它不仅支持内存中数据集的保存和恢复，而且Spark启用了内存分布式数据集，除了能提供交互式查询外，还可以优化迭代工作的负载，实现MapReduce的迭代计算。

1. 数据分布式管理
2. 运行平台包括本地运行、Standalong、Mesoes、YARN等
3. ·抽象组成。弹性分布式数据集和并行操作。
4. Spark关联系统。

（2）Spark抽象组成

Spark主要为并行计算提供了两个抽象的概念： 弹性分布式数据集 和 并行操作。

弹性分布式数据集（RDD）

弹性分布式数据集是一个对象划分的只读集合，在弹性分布式数据集的处理过程中，如果节点失败，可对丢失的数据集合进行成重建。

Spark构建弹性分布式数据集合的方式有以下几种：

1. 将文件输入一个共享文件系统（如HDFS）进行创建
2. 通过在驱动程序中并行化一个scala集合，将集合进行切片划分，并发送到多个节点
3. 通过转化现有弹性分布式数据集，利用flatmap将一种类型元素组合的数据集转换成另一种元素组合的数据集。
4. 改变现有弹性分布式数据集的持久性。（默认情况下，弹性分布式数据集具有惰性和短暂性）

改变持久性的两个过程：

1. cache改变数据集的惰性
2. Save评估数据集合并将它们写入分布式文件系统。

并行操作

RDDs上的并行操作主要包括：

1. Reduce
2. Collect
3. Foreach

共享变量

【广播变量】

Spark使程序员创建一个广播变量对象可以包装数据值，并且确定一次性分配给每一个工作节点。

【累加器】

工作节点可用 其统计关联操作，而且其参数值只有驱动程序可以访问。

2. Data Freeway 和 Puma （1）优化数据通道

优化后的数据通道为Data Freeway，它包含 Scribe、 Calligraphus、 Continuous Copier、 PTail 四个组件。

（2）优化数据的处理系统 Puma2

• 首先，PTail将数据以流的方式传递给Puma2
• 然后，Puma2以聚合的方式并且以时间为序列对流消息进行操作
• 最后，Puma2为处理后的每一条消息发送“增加”操作到Hbase，并将数据存储到Hbase。

Puma2的优点：

• 架构简单易于维护
• 采用的对称结构易于集群的扩展和故障处理

Puma2的缺点：

• Hbase的“增加”操作开销大
• Hbase不支持复杂的聚合操作
• 在故障时会产生少量的重复数据。

Puma3

改进：

• 聚合操作由Hbase转向本地内存
• 通过聚合key符puma3中的数据进行分片，用于支持内存中的聚合操作。
• Hbase只作为持久化存储

3. Storm （1）Storm概念及原理

Storm是一个分布式实时计算系统，对外提供了一系列用于批处理的组件，可有效的应用于信息流处理、连续计算和分布式远程过程调用。

• Hadoop集群运行MapReduce Job ，而Storm运行Topologies。
• Job和Topologies存在的差异主要是，MapReduce Job最终会被完成，而Topologies进程将一直运行，除非该进程被“杀死”。

（2）Storm组件 Topologies Streams Stream Groupings 4. Nephele/PACTs

• Nephele使用专用协议保证各项功能的效率，通过通信、同步和容错机制将PACT程序转换成Nephele数据流，进而实现不同类型数据流的优化处理。
• Nephele计算模型的思想是为某一个作业分配合适的资源，而不是为某个固定的资源分配任务。

5. 其他改进工作 （1）Barrier-less MapReduce （2）Map-Reduce-Merge （3）KPNs （4）Oivos 例子理解