Map Reduce

魔法师LQ

回顾

很多东西需要阅读获取。

中心的方法维护名字空间,聪明的客户端。

  • 对比,HDFS, GFS
  • 阅读源代码
  • 找工业界是如何根据实际需求来应用

分布式文件系统解决的是存储的问题,这节课解决的是计算的问题。

计算包含哪些功能,

将功能进行并行,就能够实现整体的并行计算

提纲

MapReduce基础

变成模型

分布式框架

算法和Hadoop

背景

处理很多数据

产生很多其他的数据

使用大量的计算资源(例如众核计算)

上面计算需要是简单的

典型的大数据问题(模式)

通常会在一段记录上反复地读写

抽出感兴趣的信息(例如模式匹配)

混洗,排序中间结果

整合汇聚中间结果

输出最终的结果

例如计算积分,搜索图片

大致抽象出来两个过程,这就是Map & Reduce

范式(paradigm)

时刻牢记有多机器并行,而不囿于单机运算

reduce将相同的k2合并

特性

MapReduce是一种编程模型来来处理数据集。

自动并行,自动分布

容错

状态监控

提供了精简的抽象

架构

计算密集

搭建在原来的I/O密集的基础设施上

过程

总体工作结构示意图

Step 1. 将数据文件切分成chunks

Step 2. 分支进程(fork processes)

分配给空闲的works以任务

  • map tasks
  • reduce tasks

Step 3. Map Task

Step 4. 创建中间文件

Step 4.a Partitioning

Step 4.b

Step 5. Recuce Task:sorting

远程通过远程调用

本地直接

所有具有相同的key的被group到一起

若排序,$O(nlog(n))$

否则shuffle输出

Step 6. Recuce Task:

Step 7: 返回给用户

以词频统计为例

  1. 分配程序(程序是一样的,喂的数据不同)
  2. 开谁最闲,分配map任务。能在本地拿到数据就本地处理,否则通分布式文件系统经过网络来获取
  3. map先存在内存中,内存不够写到中间文件中,写R个中间文件。本例子中R不确定
  4. 开始Reduce, 从第一个Reducer开始循环换:将要处理的数据拿过来,拿过来的数据按照partition funtion已经排好了
  5. 排序,按照k2排序,产生文件

分布式框架

一个job包含:

  • 一堆mappper和reducer

让数据和代码尽可能近

自己设计key

自己设计调度机制

  • copy m*r
  • reducer当所有mapper执行完

调度

  • 定制
  • task数量可能超过可用的服务器
  • 处理数据分布不均衡

FIFO 调度

可能短的任务一直等

FAIR

  • 对过个job汇合成一个pool

reduce汇合所有相同的key的数据

作业

提前看实验指导书

实现mapreduce