Aione's blog

一起快乐摸鱼吧🐳

  1. 1. 执行流程
  2. 2. Falut Tolerance
    1. 2.1. Worker Failure
    2. 2.2. Master Failure
  3. 3. Semantics in the Presence of Failures
  4. 4. Locality
  5. 5. Backup Tasks
  6. 6. Reference

重读 mapreduce,在实现 mapreduce demo 之后。

论文里最重要的部分就是这张图了,可以说 mapreduce 的精髓就在这里。从这张图就可以勾勒出 mapreduce 的整体架构和数据处理流程。

overview

执行流程

首先,输入数据会被自动分成 M 片,然后并行的在不同的机器上执行,执行 map 的时候根据 key 不同分配到不同的 reduce 进行处理。

  1. 首先 mapreduce 库把输入文件分成 M 块大小在 16-64mb 的文件。
  2. master 节点向 workers 节点分发 map/reduce 任务。
  3. map 节点读取对应的任务切片然后交给 map 函数处理。得到的中间 kv 对存放在缓存。
  4. 缓存会被分成 R 片定期写入 worker 的本地磁盘,本地磁盘的地址最后会返回给 master。
  5. 当 reduce 节点被 master 通知中间 kv 对的地址时,会通过 rpc 调用读取 kv 对到本地磁盘,只有当 reduce 节点读取到所有的 kv 对后,首先对 kv 对进行排序,这里就完成了 list(k2, v2) -> (k2, list(v2)) 的转变。

注:对于 M 个分片,会产生 M * R 个中间文件,reduce 节点需要读到 M 个中间文件才算读取完毕。

  1. 遍历所有的 (k2, list(v2))k2, list(v2) 丢到 reduce 函数处理,得到的结果添加到当前 reduce 结果的末尾。
  2. 当所有的 map 任务和 reduce 任务完成后,master 节点唤醒用户程序并返回。

Falut Tolerance

Worker Failure

master 节点会使用心跳包机制检查 worker 是否存活,如果一段时间内检测到某个 worker 死亡,会把 worker 当前执行的任务交由其他 worker 处理。当 map task 失败的时候,会把该任务重新调度到其他 worker 执行,任何正在执行和当前 map task 相关的 reducer worker 会重新执行,并从新的 map worker 读取数据。

Master Failure

由于当前只有一个 Master,可以采用定时做 checkpoint ,并用 GFS 来保证由多个主机有 Master 文件的备份,即使 Master 挂掉也可以从其他机器上进行恢复。

Semantics in the Presence of Failures

保证在 mapreduce 执行过程中,即使发生了错误,也和没有发生错误时的结果一致。

举个例子,当某个 map 任务失败当时候,该任务被调度到其他 worker 执行,不能让当前 map 任务的失败影响到后续执行。

当 map 任务完成当时候,worker 会向 master 节点发送包含 r 个咋临时文件文件名当信息,master 检测到是否在数据结构中,然后添加,这样保证了,即使 map 失败,由于 master 数据结构修改到原子性,master 没有包含该文件的信息。后续 reduce 也不会读到这些文件。

当 reduce 任务完成的时候,采用原子改名策略,只有当任务完成才会对文件进行改名。

Locality

局部性原理,因为 mapreduce 基于 GFS,可以利用 GFS 每个文件有三个副本的特性,当需要调度任务的时候会优先将任务调度到目标文件已经存在到机器上,减小网络数据传输到开销。

Backup Tasks

当整个任务接近完成当时候,可能因为某些主机的软/硬件错误导致部分任务执行过长影响结束时间,这时候会采取 backup tasks 策略,即接近完成当时候,每个任务会被同时放到两台主机上运行,如将 mr-0-1 放到 worker 1 worker 2 执行,任何一个 worker 结束时即表示完成。

Reference

  1. mapreduce

Author : Aione
本文使用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议
Link to this article : https://aione.space/2020/06/01/mapreduce/

This article was last updated on days ago, and the information described in the article may have changed.