浅谈MapReduce

MapReduce是一个抽象的分布式计算模型,主要对键值对进行运算处理。用户需要提供两个自定义函数:

  • map:用于接受输入,并生成中间键值对。
  • reduce:接受map输出的中间键值对集合,进行sorting后进行合并和数据规模的缩减,并进行期望信息的提取。
    用户通过map和reduce函数声明键值对的处理方式,而调度,并行计算和容灾等底层问题则是对用户透明的。

1、示例

1.1 词频统计

在这个案例中,目标是将文本作为输入,将其中的单词出现频率进行统计。 此时,map和reduce的伪代码如下:

map(String key, String value): 
    // key: document name
    // value: document contents 
    for each word w in value:
        EmitIntermediate(w, "1");
reduce(String key, Iterator values): 
    // key: a word
    // values: a list of counts
    int result = 0;
        for each v in values:
            result += ParseInt(v);
        Emit(AsString(result));

map函数通过接受文本(这里输入的是文本的名字)作为key,文本的内容作为value,并通过遍历文本中的单词来生成单词/出现频率的键值对。这里单个单词被遍历的时候,出现频率的贡献都为1。 在这过程中,相同的key会被整合到一起作为中间键值对交付给reduce。 reduce函数则接受中间键值对,单词作为key,一个列表作为value(实际上由于每个单词的贡献为1,因此列表的长度就为单词的出现频率)统计出来单词的出现频率。具体方法如上述伪代码,将每个word的出现频率相加。

golang实现版本如下
在这里插入图片描述

1.2 气象数据

在这个例子当中,要写一个关于气象数据的分析程序。分布在全球各地的很多气象传感器每隔一小时收集气象数据和大量日志数据,且这些数据按行并以ASCII格式存储,半结构化且按照记录方式存储,很适合用MapReduce来分析。

如下图,这是一行采样数据,其中重要字段添加了注释。这一行数据被分成很多行以突出每个字段,但实际是存储在一行中,没有分隔符的。
在这里插入图片描述

数据文件按照日期和气象站进行组织。从1901年到2001年,每一年都有一个目录,包含各个气象站该年气象数据的打包文件和说明文件。
在这里插入图片描述

现在,我们的目的是要提取出每一年的最高气温。 假设我们现在需要统计传统处理按行存储数据的工具是awk,如该脚本

#!/usr/bin/env bash
for year in all/*
do
    echo -ne `basename $year .gz`"\t"
    gunzip -c $year | \
    awk'{ temp = substr($0,88,5) + 0;
          q = substr($0,93,1);
          if(temp != 9999 && q ~ /[01459]/ && temp > max) max = temp}
        END {print max}'
    done

这个脚本遍历压缩文件,首先显示年份,然后使用awk处理每一个文件。 awk主要提取两个字段:气温和质量代码。气温+0后转换成整数,然后测试气温值是否有效。用9999代替NCDC数据中丢失的值。如果数据读取正确,那么就和目前的最大值进行比较。如果比目前的最大值大,那么替换最大值。 处理完所有行之后,再输出最大气温值。 如下是部分运行结果(这里的气温值被放大了十倍,1901年的最高温度是31.7度)
在这里插入图片描述

为了加快速度,我们需要并行数据分析。 同样还是两个阶段,map和reduce。map函数很简单,我们只对年份和气温感兴趣,因此将数据中的行作为输入,将气温和年份等提取出来。提取之后,将年份相同,也就是key相同的值聚合到一起,交付给reduce。reduce函数对每个key选出一个最大的气温值即可。 此处,我们假设一行中属性的偏移量是固定的,如下每一行的字体标粗部分分别为年份和气温
在这里插入图片描述

key是文件中的行偏移量,我们不需要因此忽略。我们只需要提取出来年份和气温即可,就有

(1950,0)
(1950,22)
(1950,-11)
(1949,111)
(1949,78)

reduce将相同key的键值对进行排序与整合,因此有

(1949,[111,78])
(1950,[22,0,-11])

最后,reduce遍历每一个键值对,将最大的值选出来,就是我们需要的数据。

(1949,111)
(1950,22)

从这个例子,我们可以看出来mapreduce的流程

  • input:将输入文件作为键值对进行输入
  • map:map函数将键值对的信息提取出来,生成中间键值对
  • shuffle:对中间键值对进行整合,聚合相同的key
  • reduce:遍历key,对每一个key选出我们需要的信息
  • output:输出
    在这里插入图片描述

2、 架构

MapReduce框架主要由三个部分组成

  • User Program
  • Master
  • Worker
    其中,User Program是用户的自定义程序。
    Master节点不对任务进行处理,而是对Worker进行任务调度和状态收集。
    Worker则是实际进行计算的节点,既可以进行Map也可以进行Reduce,取决于分配到的任务是什么。

在这里插入图片描述

传入Map的输入数据会被自动切分成M个数据片段,用于分布到多台机器上并行处理。 利用分区函数,将Map生成的中间键值对分成R个不同的分区,以此让R个reduce worker也并行地进行reduce工作。

分区数量R和分区函数由用户指定,以下是一个简单的实现

在这里插入图片描述

其中KeyValuePairs是经过调用了mapF生成的中间键值对。在下面的循环中,通过对键值对的key进行hash函数得到哈希值,然后再模nReduce得到分区位置。也就是hash(key)%nReduce 由user program调用MapReduce开始

  • 1.MapReduce库将输入文件分块,通常分成M份16到64MB。然后,他会在集群中启动多个程序副本。
  • 2.worker读入数据,解析并传入map函数。map函数生成的中间k/v对会被缓存在内存中。
  • 3.每隔一段时间,内存中的k/v对会被写到磁盘,并分区到R个区域内。这些区域的位置会告知master,然后master转发给reducer去消费这些数据。
  • 4.reducer被告知位置之后,它会采用RPC的方式读取保存了这些k/v对的磁盘。当一个reduce worker读取完所有中间键值对之后,该reducer会对这些键值对进行排序。这是因为,许多不同的key会映射到同一个reduce任务中。如果数据量太大而无法全部导入到内存中,则需要进行外部排序。
  • 5.reducer会对这些排序后的中间k/v对进行遍历,然后对于每个唯一的key的value集合传入reduce函数中,最后追加到reduce分区的输出文件中。
  • 6.完成后master唤醒用户程序,用户程序结束调用

2.1 简单的实现

首先,创建nReduce个文件,文件名则是通过一个函数来创建的,目的是方便reduce worker通过有规律的名字去寻找这些文件。 然后通过调用用户自定义的mapF函数,将输入文件拆分成键值对。 遍历键值对,利用ihash(kv.key)%nReduce计算得到文件下标,并将键值对附加到该文件上。

在这里插入图片描述

reduce通过reduceName约定的名字从文件中寻找自己消费的文件。 然后遍历中间键值对,利用sort对这些键值对进行排序(key相同的键值对都会被排到一起) 然后调用reduceF函数进行reduce,最后输出到文件当中。

在这里插入图片描述在这里插入图片描述

2.2 Master的数据结构

Master中保存了每个Map任务和每个Reduce任务的状态(闲置,正在运行,以及完成),以及非空闲任务的worker机器的ID。 Master的数据结构之所以要保存这些,是因为需要保证容灾能力。

2.3 容灾

2.3.1 Worker故障

Master对Worker进行心跳检测。如果一定时间内无法ping通该worker,它就会被标记成failed。所有由该worker完成的map或reduce任务都会重新设置为初始的闲置状态,然后将这些任务重新分配给其他worker。 如果是完成map的worker,由于输出结果保存在worker的磁盘之中无法访问,因此就要重新运行。 如果是reducer的worker,结果已经存储在全局的文件系统中了,因此无需再次执行

2.3.2 Master故障

上文中我们提到,Master中保存了每个Map任务和每个Reduce任务的状态(闲置,正在运行,以及完成),以及非空闲任务的worker机器的ID。 master周期性的将上文的数据结构写入磁盘备份,如果出错了,就可以从这些数据结构中恢复状态。

2.3.3 任务粒度

我们将map和reduce任务分别拆分成了M个和R个子任务。理想情况下,M和R应该远大于worker的数量。每个worker也会执行不同的许多任务,以此保证负载均衡的能力。同时,worker故障了的话,通过能够将该机器的任务发送到其他完好的worker上加快恢复的速度 但M和R的数量不应过多,因为master需要在内存中保存O(M*R)个状态,需要执行O(M+R)次调度。过大的M和R会加重master的负担。

2.4 网络

网络带宽在这个模型中是一个相对稀缺的资源,因此MapReduce尽量将输入数据存储在本地的硬盘中以节约网络资源。 其中输入和输出是不可避免的网络通信,一般会通过一个分布式存储系统进行输入和存储,如GFS。 Master调度任务的时候会考虑文件的位置,尽量在调度一个包含该输入数据副本的机器上执行。如果任务失败,则会调度到同样有该副本的较近的机器上执行。 一种优化形式是令运行着GFS的集群进行。MapReduce工作,那么Master可以将任务分配给已经拥有该数据的Worker中,从而直接从本地磁盘进行读取,减少网络通信。

3、 总结

从上述的信息来看,MapReduce主要的优点有

  • 1.易于编程,用户只需要自定义map和reduce函数即可。
  • 2.具有良好的扩展性,可以通过增加worker的数量来扩展计算能力。
  • 3.具有一定的容灾能力,master可以通过定期写入一些持久化信息进行进度的备份,保证master挂了之后可以读取这些信息恢复;而worker挂了的话,它负责的任务可以由master重新调度给其他worker进行作业。
  • 4.适合PB级别以上大数据的离线处理。
    缺点主要有:
  • 1.不能实时计算,MapReduce处理的是存储在磁盘上的离线数据。
  • 2.不能流式计算,MapReduce设计处理的数据源是静态的。
  • 3.难以DAG计算,即多个任务存在拓扑的依赖关系,前一个任务的输出是另一个任务的输入。解决方法有Apache的Tez计算框架。
    总的来说,从MapReduce的所有长处来看,它基本是一个批处理系统,并不适合交互式分析。
    MapReduce处理的是存储在磁盘上的离线数据。
  • 2.不能流式计算,MapReduce设计处理的数据源是静态的。
  • 3.难以DAG计算,即多个任务存在拓扑的依赖关系,前一个任务的输出是另一个任务的输入。解决方法有Apache的Tez计算框架。
    总的来说,从MapReduce的所有长处来看,它基本是一个批处理系统,并不适合交互式分析。
    典型情况下,执行查询需要几分钟或更多时间。同时,MapReduce设计处理的数据源是静态的,因此,MapReduce更适合没有用户在现场等待查询结果的离线引用场景。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/251958.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

linux下的strerror和perror处理错误函数

strerror和perror是C语言中用于处理错误信息的函数。 strerror函数: strerror函数用于将错误码转换为对应的错误消息字符串。它接受一个整数参数,通常是由系统调用或库函数返回的错误码,然后返回一个描述该错误的字符串。 函数原型&#xff1…

双指针训练

1.原理 双指针是一种解题常用方法,常用于将数组按照某种要求进行分块/划分,这里的指针对于数组来说,可以替换成下标(毕竟使用下标实际上就是用了指针)。 1.1.划分区间 通常将这两个指针命名位dest/cur(或…

AOP切入点表达式和使用连接点获取匹配到的方法信息

目录 第一种 execution(访问修饰符? 返回值 包名.类名.?方法名(方法参数) throws 异常?) 第二种 annotation(com.itheima.anno.Log 首先,自定义一个注解,可以自己随意命名: 第一种 execution(访问修饰符? 返回值 包名.类名.?方法名…

网络编程-认识套接字socket

文章目录 套接字概念端口号网络字节序 套接字类型流套接字数据报套接字 socket常见APIsocket函数bind函数listen函数accept函数connect函数sockaddr结构 套接字概念 socket套接字是进程之间一种通信机制,通过套接字可以在不同进程之间进行数据交流。在TCP/UDP中&…

【golang/g3n】3D游戏引擎G3N的windows安装与测试

目录 说在前面安装测试 说在前面 操作系统:win 11go version:go1.21.5 windows/amd64g3n版本:github.com/g3n/engine v0.2.0其他:找了下golang 3d相关的库,目前好像就这个比较活跃 安装 按照官方教程所说,…

Electron框架:构建跨平台桌面应用的终极解决方案

文章目录 一、Electron框架简介二、Electron框架的优势1. 开发效率高2. 跨平台性能好3. 易于维护4. 强大的原生能力 三、如何使用Electron框架快速开发跨平台桌面应用1. 安装Electron2. 创建项目文件夹3. 编写主进程代码4. 编写界面代码5. 运行应用 《Electron入门与实战》编辑…

nginx_rtmp_module 之 ngx_rtmp_mp4_module 的mp4源码分析

一:整体代码函数预览 static ngx_int_t ngx_rtmp_mp4_postconfiguration(ngx_conf_t *cf) {ngx_rtmp_play_main_conf_t *pmcf;ngx_rtmp_play_fmt_t **pfmt, *fmt;pmcf ngx_rtmp_conf_get_module_main_conf(cf, ngx_rtmp_play_module);pfmt ngx_ar…

极兔速递物流查询,用表格导出单号的每一条物流信息

批量查询极兔速递单号的物流信息,并以表格的形式导出单号的每一条物流信息。 所需工具: 一个【快递批量查询高手】软件 极兔速递单号若干 操作步骤: 步骤1:运行【快递批量查询高手】软件,第一次使用的朋友记得先注册…

HPV治疗期间如何预防重复感染?谭巍主任讲述具体方法

众所周知,人乳头瘤病毒(HPV)是一种常见的性传播疾病,感染后可能会引起生殖器疣、宫颈癌等疾病。在治疗期间,预防重复感染非常重要。今日将介绍一些预防HPV重复感染的方法。 1. 杜绝不洁性行为 在治疗期间,患者应该避免与感染HPV…

CT成像技术—20231210

本文要说的是扇束重排,对于扇束及锥束直接重建公式,可以看我做的PDF https://github.com/leslielee619/CTRec/blob/main/重建公式.pdf 在说重排之前,我还想对那个文件内容补充两点: 1、FDK算法或Feldkamp算法,出自Fel…

linux下开放端口的方法

为了辅助我们查看端口状态,本文采用nmap扫描端口 目标机:192.168.241.1,本文的目的是开启22端口 我们可以根据端口状态(filtered)看出,端口处于过滤状态,即防火墙过滤了该端口 PS:…

PCB设计规则中的经验公式_笔记

PCB设计规则中的经验公式 规则1 - 临界长度规则2 - 信号带宽与上升时间规则3- 时钟信号带宽规则4-信号传输速度规则5- 集肤 (效应) 深度规则6 - 50Ω传输线电容规则7 - 50Ω传输线电感规则8 - 回流路径电感规则9 - 地弹噪声规则10- 串行传输比特率与信号带宽规则11- PCB走线直流…

JAVA序列化(创建可复用的 Java 对象)

JAVA 序列化(创建可复用的 Java 对象) 保存(持久化)对象及其状态到内存或者磁盘 Java 平台允许我们在内存中创建可复用的 Java 对象,但一般情况下,只有当 JVM 处于运行时,这些对象才可能存在,即,这些对象的生命周期不…

Linux---文本搜索命令

1. grep命令的使用 命令说明grep文本搜索 grep命令效果图: 2. grep命令选项的使用 命令选项说明-i忽略大小写-n显示匹配行号-v显示不包含匹配文本的所有行 -i命令选项效果图: -n命令选项效果图: -v命令选项效果图: 3. grep命令结合正则表达式的使用 正则表达式说明^以指…

STM32_HAL库—IWDG看门狗

一、CubeMX设置 1、晶振配置(72M) 2、数据配置 超时时间 Tout prv / LSI * rlv (s) 其中prv是预分频器寄存器的值,rlv是重装载寄存器的值,而LSI值默认是40kHz,如下所示。 3、代码实现 int main(){while(1){HAL_IW…

gitlab ci pages

参考文章 gitlab pages是什么 一个可以利用gitlab的域名和项目部署自己静态网站的机制 开启 到gitlab的如下页面 通过gitlab.ci部署项目的静态网站 # build ruby 1/3: # stage: build # script: # - echo "ruby1"# build ruby 2/3: # stage: build …

docker入门小结

docker是什么?它有什么优势? 快速获取开箱即用的程序 docker使得所有的应用传输就像我们日常通过聊天工具文件传输一样,发送方将程序传输到超级码头而接收方也只需通过超级码头进行获取即可,就像一只鲸鱼拖着货物来回运输一样。…

pl_vio线特征·part II

pl_vio线特征part II 0.引言4.线段残差对位姿的导数4.1.直线的观测模型和误差4.2.误差雅克比推导4.3.误差雅可比求导简洁版(不含imu坐标系转换)4.4.相关代码 0.引言 pl_vio线特征part I 现在CSDN有字数限制了,被迫拆分为两篇文章。 4.线段残差对位姿的导数 这一小…

盛最多水的容器

给定一个长度为 n 的整数列表 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。 说明:你不能倾斜容器。 示例1&…

ARM I2C通信

1.概念 I2C总线是PHLIPS公司在八十年代初推出的一种串行的半双工同步总线,主要用于连接整体电路2.IIC总线硬件连接 1.IIC总线支持多主机多从机,但是在实际开发过程中,大多数采用单主机多从机模式 2.挂接到IIC总线上,每个从机设备都…