MapReduce-osdi04 Paper Read
MapReduce: 大规模集群上的简化数据处理
- 原始论文
摘要
用户侧
map函数:处理键值对,生成一组中间键值对reduce函数:合并与同一中间键关联的所有中间值
特性
- 自动并行化,适于在大型机器集群上执行。
- 运行时系统负责处理输入数据的分区、跨机器集合调度程序执行、处理机器故障以及管理所需机器间通信。提供了一种方法,封装了分布式系统的复杂性。
- 具有高扩展性,可以适配多种分布式程序任务
方案背景
MapReduce框架的出现,是为了解决,大量数据如何在大型分布式系统上实现并行化计算、分布数据和故障处理等,复杂的并发细节(该问题导致原来设计的简单计算任务代码,为了满足分布式系统的并发需求,而增加了大量的并发复杂性)
MapReduce在计算任务与分布式系统之间设计了一种新的抽象,将简单计算与复杂并发细节相分离。
MapReduce库的抽象设计受到Lisp及许多函数式语言中的 map 与 reduce 原语的启发。对输入的每个输入逻辑应用 map 操作,计算一组中间键值对,对共享相同键的值应用 reduce 操作,以适当的合并派生数据。将函数式的 map 与 reduce 的实现交由用户制定,库只需要提供并行化方法,使用户轻松实现程序并行化。该库将重新执行作为容错的主要机制。
map 与 reduce
- map 映射
- reduce 归约
Lisp语系的视角
map
1 | ; racket |
- 将列表
lst中的每一个元素应用proc操作进行处理 - 多表映射 若传入多个列表,则从每个列表中各取一个元素作为参数,即针对所有列表的相应元素应用
proc操作进行处理 - 作用:给定一个函数和多个列表,将函数依次应用到每个元素上,将所有返回值收集为一个 新列表 进行返回
- 核心思想: 变换数据的形状或内容,而不关心遍历细节
reduce
1 | ; Common Lisp |
- 作用: 给定一个二元函数(归约函数)和一个列表,从左到右(从右向左)将函数累积地应用到元素上,最终将整个列表 聚合为一个结果
- 核心思想: 用一个操作将数据“折叠”,提取出单一的汇总信息
map 与 reduce的协同作用
- 告别显式循环 直接声明针对列表中各元素的操作
- 组合能力强
mapreduce函数可以嵌套、串联,形成流水线(MapReduce) - 函数式编程核心 两个原语分别对应了两大递归模式 映射(map) 折叠(fold) ,可以实现大量遍历操作
本文的 map reduce 处理视角
从Lisp原语含义转向本文视角
map将列表的形态进行转换,仅更新列表元素- (接受一组输入对,产生一组中间键值对)
reduce将列表转化为一个值,将列表中的所有值,按一定规则进行规约- (将具有相同中间键K对应的一组值合并为更小的集合)
如,使用以下racket程序,将map处理过的奇数,由foldl处理,连接为一个列表(利用了 map 与 reduce 的嵌套)
1 | (foldl |
MapReduce系统下的语义与Lisp语系的差别
map处理一个个键值对 (k0, v0) 输出一组中间键值对 (k1, v1)- (k0, v0) -> list((k1, v1)…)
- 将具有相同中间键的值进行排列,该 分组/洗牌阶段,交由该框架处理
- 默认将同一中间键的值 按字典序进行排序
- 封装了按键分组中的众多分布式难题,仅暴露值迭代器(Iterator values)
- (key, Iterator values)
reduce函数通过调用 emit(k, v) 产生任意条输出记录,这些记录最终追加到该 reduce 分区的输出文件中- reduce (k1, list(v1)) -> list(v1)
- 操作形式并非 Lisp语系 中的reduce
- Lisp折叠 –> MapReduce合并
- 中间键对应的值列表由迭代器提供给用户的reduce函数
- 处理 key -> Iterator values
- 将由
map生成的各个具有相同中间键的中间值合并为一个可能更小的集合- 可以是类似于Lisp中的累积归约(如论文中的 Word Count 例子)
- 也可以是对于该集合元素的去重
- …
- 不同reduce之间无顺序依赖
- 多个reduce并行执行,不同reduce任务间无顺序关系
- 容错由重执行实现,无全局状态
- 具有函数式的无副作用性质
- 无共享状态,重试更加安全
实现
执行概述
将输入数据自动区分为一组 M个分片
Reduce 调用通过使用分区函数(如hash(key) mod R)将中间键空间划分为R个片段来分布
分区的数量(R)和分区函数由用户进行指定
- 用户程序中的 MapReduce 先将输入文件分为 M个片段。然后,在集群机器上启动程序的许多副本。
- 由一个程序副本作为 master(主节点) 为各个 worker(工作节点) 分配工作。
- master 将 M个map任务 和 R个reduce任务 分配给空闲的worker
- map worker 读取相应输入分片的内容。从数据中解析出键值对,将每个对传递给 用户定义的Map 函数。Map函数产生的中间键值对缓冲在内存中
- 缓冲的对定期写入本地磁盘,通过分区函数 划分为R个区域。这些被持久化的缓冲对在本地磁盘上的位置被传回 master,由master将这些位置转发至 reduce worker。
- reduce worker 被 master 通知这些中间键值对的存储位置时,使用远程过程调用从 map worker 的本地磁盘读取缓冲的数据。当 reduce worker 读取了所有中间数据后,按中间键对数据进行排序,将相同键的所有出现分组在一起。
- 排序是必要的,通常许多不同的键被映射到一个reduce任务。
- 对于中间数据量过大的情况,使用外部排序
- 排序作为框架的强制性措施,是为了让reduce对中间键值对进行流式的连续处理,而不必将所有中间键同时加载到内存中,使key连续到达进行集中处理
- reduce worker 遍历排序后的中间数据,对于遇到的每个唯一中间键,将键和相应的中间值传递给 用户定义的Reduce 函数。该Reduce函数的输出被追加到该reduce分区的最终输出文件中
- 当所有的map与reduce任务都完成后, master 唤醒用户程序。此时,用户程序中的MapReduce调用返回用户代码
程序完成后,mapreduce执行的输出在R个(每个reduce一个)输出文件中可用。通常不需要将这R个文件进行合并,而是 作为另一个MapReduce调用的输入 或 另一个能够处理分区为多个文件输入的分布式应用程序中使用
Master 数据结构
- 存储 map 与 reduce 的任务状态
- 空闲
- 进行中
- 已完成
- master作为map任务传播到reduce任务的通道
- 存储map任务产生的R个中间文件的位置与大小
容错
worker 故障
master 定期ping每个worker,当worker无法响应,则被标记为失败,任务被重置为空闲的初始状态,以供其他worker进行调度。
已完成的map任务在故障时需要重新执行,因为其输出的数据存储在故障机器的本地磁盘上,无法访问。
已完成的reduce任务不需要重新执行,它们的输出存储在全局文件系统中。
当一个map任务首先由workerA执行,然后由workerB执行(A失败),所有执行reduce任务的worker都会收到重新执行的通知。任何尚未从workerA读取数据的reduce任务将从workerB中读取数据
中间数据置于本地磁盘而非全局文件系统(GFS)中,是为了避免网络往返,但故障后需要进行冗余的重跑
- map 输出是中间数据,量大且只被 reduce 消费一次,放本地磁盘避免网络带宽浪费。
- reduce 输出是最终结果,需要持久可靠,且可能被下游直接读取,所以放 GFS。
- 代价是 map 失败后必须重跑 map,且通知所有相关 reducer 重读新位置。
master 故障
进行单点控制,简化一致性处理,但是由于作为map与reduce任务间的桥梁,将成为系统的容量瓶颈与单点故障点,仅由检查点进行恢复
让master定期的写入master数据结构的检查点。若master任务终止,可以从最后一个检查点状态启动一个新副本,手动恢复。
优化
Combiner 函数
用户可以定义一个可选的 Combiner 函数,在数据通过网络发送前对其进行部分合并,将在reduce中需要进行的合并操作提前至map中,优化reduce函数执行过程
Combiner函数在每个执行map任务的机器上执行
- Combiner函数仅对结合率与交换律成立的计算才安全
- reduce函数的输出写入最终的输出文件
- Combiner函数的输出发送至reduce任务的中间文件,在语义上可以与reduce进行互换