MapReduce: 计算集群上的简化数据处理

摘要

• MapReduce -> 程序模型 + 实现 -> 大数据

  • map

    • 1(k, v) -> n(k, v)

  • reduce

    • n(k, v) -> 1(k, v)

• 自动并行化

  • 数据划分

  • 程序调度

  • 处理失败

  • 程序通信

1. Introduction

• simple, big scale

• map/reduce -> Lisp

2. Programming Model

• Problem: 统计文档中每个词语出现的频次

  • map: 1(doc, content) -> n(word, 1)

  • reduce: n(word, 1) -> m(word, count)

• 分布式grep

• 统计url访问频率

• term-vector 统计

• 倒排索引 (inverted index, 转置索引)

  • doc -> key word : forward

  • key word -> doc : inverted

• 分布式排序

3. Implementation

• 物理环境

  • 2核, 4g, x86, linux

  • 100/1000m either

  • 1000+ machines

  • individual disk using GFS

  • scheduling system

3.1 Executiong Overview

• inputs -> map -> intermediates -> reduce -> output

  • 将input分割成16m~64m的分片

  • master程序为空闲的worker分配map/reduce任务

  • map worker 读取input分片, 执行用户定义的map函数, 输出中间结果至memory

  • 中间结果被周期的持久化到硬盘, 并将位置传输给master

  • reduce worker 从master获取缓存结果的位置, 读取中间结果, 并根据key排序

  • reduce worker 遍历中间结果, 执行用户定义的reduce函数, 输出最终结果到output文件

  • 所有任务结束后, master将结果返回给用户

3.2 Master Data Structures

• task state

• id of worker machine for task

• location of intermediate file

3.3 Fault Tolerance

• Worker Failure

  • master 周期的 ping worker (心跳)

  • 失败的worker, task被重置

    • map任务被重置, 是因为中间结果保存在本地, 已经无法获取

    • reduce任务不需要重置, 因为reduce结果保存在全局文件系统

  • map任务被重置后, reduce任务会接到通知, 重新从另外一个map worker获取结果

• Master Failure

  • 周期的写 checkpoint, 有问题则从 checkpoint 恢复

  • 只有一台, 出错的概率低

• Semantics in the Presence of Failures

  • 如果 map/reduce 方法确定, 输出的结果也确定

  • 通过原子提交(atomic commit)

3.4 Locality

• GFS 每个分片有3个拷贝(64m)

• 尽量就近获取数据, 节省带宽

3.5 Task Granularity

• 任务粒度应该让任务数(M, R)远大于worker数, 以加速故障恢复

• M和R的上限取决于 O(M + R) 的调度决策和 O(M * R) 的状态保存

  • M 取决于 input 大小, 因为要让分片后每片大小在16m~64m, 以提高效率(局部性)

  • R 取决于 worker 数量, 一般是 worker 数量的一个小倍数, 如 2000 woker 对应 R 为 5000

3.6 Backup Tasks

• straggler 会导致整体任务执行变长 (木桶定律)

• 在复杂任务快要结束时, 为剩余的任务分配备份任务

• 主任务和备份任务无论哪个先执行完都可以提交

4. Refinements

• 使用新的分片函数, 满足用户的特殊输出需求

• 中间数据按照顺序排列

• Zipf分布 (长尾) 导致任务分配不均, 可以使用 combiner 提前进行一轮reduce

• 多种形式的输入和输出(文件, 数据库, 内存)

• MapReduce库会跳过错误的record

• master 上跑了一个http服务器, 显示状态信息

• 提供 counter 功能, 负责任务数据统计

5. Performance

6. Experience

7. Related Work

8. Conclusions