MapReduce
MapReduce 与分布式文件系统
MapReduce 就像分布在上千台机器上的 Unix 工具。
- MapReduce 作业通常不会修改输入，除了输出外没有任何副作用。
- MapReduce 作业在分布式文件系统上读写。（Unix 工具 stdin、stdout），如 HDFS（Hadoop Distributed File System)等（GlusterFS、QFS、Amazon S3、Azure Blob 和 OpenStack Swift）。
MapReduce 作业执行
MapReduce 是一个编程框架，可以使用它编写代码处理 HDFS 等分布式文件系统中的大型数据集。
要创建 MapReduce 作业需要实现两个回调函数： mapper 和 reducer （另请参阅 MapReduce 查询）:
Mapper: 每个输入记录都会调用一次，从输入记录提取任意数量的关键字和值（可以为空），不保留任何状态，可以独立处理。Reducer: MapReduce 框架使用Mapper生成的键值对，收集同一个关键字的所有值，并使用迭代器调用 reducer 以使用该值的集合。 Reducer 可以生成输出记录。
MapReduce 分布式执行
参见 Hadoop 的 MapReduce 的分布式执行。
MapReduce 工作流
将 MapReduce 作业链接到工作流是非常普遍的，作业的输出作为下一个作业的输入。通过目录名隐式的完成：
- 第一个作业必须配置将其输出写入 HDFS 中指定目录；
- 第二个作业必须配置读取相同的目录名作为输入。
目前已经开发了处理依赖管理的 MapReduce 工作流调度器。
Reduce 端的 join 与分组
批处理的背景下讨论 join，主要解决数据集内存在关联的所有事件。 假设 join 两张表：用户和活动事件。
排序-合并 join
次级排序：reducer 会首先看到用户数据库的记录，然后按照时间戳顺序查看活动事件。
基于次级排序 reducer 可以很容易的执行 join：为每个用户 ID 调用一次 reducer 函数。
- 第一个值是来自用户数据库的出生日期记录，并存储在局部变量。
- 然后使用相同的用户 ID 遍历活动事件。
- 进行聚类。
reducer 每次处理一个特定用户 ID 的所有记录。
将相关数据放在一起
分组
处理数据倾斜
数据抽样探测热键，使用算法进行补偿。缺点是需要进行数据复制。
Hive 需要在表格元数据中明确指定热键，并将与这些键相关记录与其余文件分开存放。
Map 端 join 操作
广播哈希 join
把小数据集加载到内存哈希表中，mapper 的时候直接读取哈希表进行数据补全。
“广播”：每个分区的 mapper 读取整个小数据集到内存哈希表。
分区哈希 join
将加载到内存哈希表的数据缩小独立作用于每个分区。
Hive 中称为 bucketed map join。
map 端合并 join
按关键字升序增量读取两个输入文件，并且匹配具有相同关键字的记录。
具有 map 端 join 的 MapReduce 工作流
批处理工作流的输出
生成搜索索引
批处理输出键值
批处理输出的哲学
对比 Hadoop 与分布式数据库
参见 对比分布式数据库。
相关文章
超越 MapReduce
中间状态实体化
- 数据流引擎：Spark、Flink、Tez
- 容错：Spark 使用 弹性分布式数据集 跟踪数据的祖先，Flink 对运算符状态建立检查点来从故障中恢复。
数据流对 MapReduce 的改进是：不需要自己将所有中间状态写入文件系统。
图与迭代处理
- Pregel 处理模型
高级 API 和语言
Hive、Pig、Cascading 和 Crunch。Tez 可以将这些高级语言移植到新的数据流执行引擎。