投稿
  1. 首页
  2. 随笔

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

滴答铃声 • 2022-12-17 • 随笔 • 阅读 25

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

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

《数据密集型计算和模型》第四章的有关内容。主要有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抽象组成
        • d性分布式数据集（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. ·抽象组成。d性分布式数据集和并行 *** 作。
  4. Spark关联系统。
（2）Spark抽象组成

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

d性分布式数据集（RDD）

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

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

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

改变持久性的两个过程：

  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 例子理解

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5690629.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
滴答铃声 滴答铃声 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存