MyBlog
0%

MapReduce笔记

发表于 更新于 分类于

MapReduce 笔记

http://nil.csail.mit.edu/6.824/2020/papers/mapreduce.pdf

1 编程模式

1.1 基本组成

  • Map 将输入处理为中间 key-value 集合，MapReduce 框架将相同 key I 的值聚合起来传递给 Reduce 函数
  • Reduce 函数接受中间 key I 和该 key 的值的集合，将这些值聚合起来组成一个更小的值的集合

1.2 数据结构

  • Map (k1, v1) -> list(k2, v2)
  • Reduce (k2, list(v2)) -> list(v2)

2 执行概览

2.1 整体流程

image-20200812235617912

  • 把输入文件分成 M 份，通常 16-64 MB 每一份
  • 共有 M 个 map 任务和 R 个 reduce 任务
  • 被分配了 map 任务的 worker 读分割文件中的内容，拿到 key-value 并传给 Map 函数，得到的中间 key-value 缓存在内存中
  • 缓存的键值对写入本地内存中，被分割函数分为 R 个区域
    • 中间 key 被分割函数划分到 R 个 Reduce 任务中，如 hash(key) mod R
  • worker 被分配给 reduce 任务后，读本地磁盘中的缓存数据。读取所有的数据后，按中间 key 排序，使相同 key 的对排在一起。如果缓存数据在内存中排序的总量过大，则需要额外的排序
  • 将排序后的中间 key-value 集传给 Reduce 函数，其输出被合并为最终的输出文件（有时不需要合并，可以作为下一个 MapReduce 调用的输入）
  • 当所有的 map 和 reduce 任务都完成时，master 唤醒用户程序

2.2 Master 的数据结构

  • 对于每个 map 和 reduce 任务都存储了任务的状态（空闲、进行中、完成）和其 worker 机器的唯一标示

  • 对于每个完成的 map 任务，master 存储了其生成的 R 个中间文件的位置和大小，不断从完成的任务获取并更新并发送给开始的 reduce 任务

2.3 容错

2.3.1 Worker 故障

master 定时给每个 worker 发送心跳，如果一段时间没有收到某个任务的心跳或者任务失败就标记其为空闲，开始重新调度

已经完成的 map 任务如果再次被执行会导致失败因为其输出存储在本地磁盘；同理完成的 reduce 任务不需要被再次执行因为其输出存储在 gfs 中

如果一个 map 任务被 worker A 执行失败后又被 worker B 执行，所有执行 reduce 任务的 worker 都会被通知并且重新执行。还没开始从 worker A 读数据的 reduce 任务会从 worker B 读数据

2.3.2 Master 故障

Master 会写入描述 master 数据结构的 checkpoints 来保证当其故障时其副本会从 checkpoints 的状态起起来

2.3.3 考虑故障的语义

当 map 任务完成时，worker 发送给 master 一条包括 R 个中间文件名的信息，若 master 已经从已完成的任务接受过完整的信息则忽略，反之将其记录在 master 的数据结构中

依赖底层文件系统的原子的重命名操作来保证最终文件系统只包含一次 reduce 任务的执行结果

2.4 定位

master 得到输入文件的位置信息，会尝试调度一个有输入数据的副本的机器去执行 map 任务；如果不成功的话会尝试调度临近输入数据副本的机器去执行（如与有副本数据的机器在同一个交换机）

2.5 任务粒度

M 和 R 应该大于 worker 机器的数量才能保证动态的负载均衡和恢复速度

2.6 候补任务

当 MapReduce 操作接近完成时，master 会调度候补执行仍然在运行中的任务，原生或者候补执行完成任务都被标记为完成，可以提高效率。

3 改进

3.1 分割函数

默认分割函数使用哈希 hash(key) mod R

3.2 顺序保证

框架保证提供给定分割函数的话，中间 key-value 对会以增序排列

3.3 Combiner 函数

可选的 combiner 函数数据从网络发出之前会调用

Reduce 函数和 Combiner 函数的唯一区别在于 MapReduce 框架如何处理函数的输出：reduce 函数的输出写入最终输出文件，combiner 函数的输出写入即将传给 reduce 任务的中间文件

3.4 输入和输出类型

输入类型只需实现 reader 接口，则不仅可以从文件读数据、也可以从数据库、内存等读数据

3.5 副作用

生成辅助文件时，依赖 writer 来使得副作用原子和幂等，如写入中间文件，当它完全生成后再将其原子重命名

3.6 跳过坏记录

有时可以接受忽略一些记录，框架提供一个模式当 MapReduce检测到一些记录造成确定的异常时跳过它们

每个 worker 安装一个可以捕捉段错误的信号 handler，当用户代码生成了一个信号时，handler 发送一个包含序列号的 last gasp UDP 包给 master，当 master 在特定的记录收到大于一个错误时，标记该记录应该被跳过

3.7 本地执行

框架提供 debug 模式能让 MapReduce 中的所有的工作都在本地机器执行

3.8 状态信息

提供一个状态 web 页面展示计算的进程

3.9 Counter

框架提供一个 counter 功能来统计事件，类似打点功能，在检查 MapReduce 操作时 Counter 十分有效