MapReduce 是一种编程模型,将大型数据集视为键值对集合进行处理,同时也是一种将工作分配到多台计算机上的执行方式。程序员提供一个生成中间键值对的 **map(映射)**函数,以及一个处理每个中间键所关联值的 **reduce(归约)**函数。执行框架负责任务调度、数据传输、分组,以及从多种工作节点故障中恢复。2004 年,谷歌介绍了其 MapReduce 实现,此后,MapReduce 成为分布式计算和大数据处理领域中一种具有重要影响的方法。
编程模型
MapReduce 计算将应用逻辑与实现并行计算所需的大量底层机制分离开来。程序员不必显式协调工作节点之间的通信,只需描述如何转换单条记录,以及如何合并具有相同键的记录。
核心函数可表示为:
方括号表示值或键值对的集合,并不要求将所有值都实际存放在内存中。许多实现通过迭代器提供归约函数的输入。
输入、中间处理和输出阶段的键类型和值类型可以不同。一次 map 调用可以不输出键值对,也可以输出一个或多个键值对。同样,一次 reduce 调用可以生成零条或多条输出记录。
在这两个函数之间,框架会执行一项关键操作:收集属于同一个键的所有中间值,并将它们交给同一次 reduce 调用。这种数据分组与移动通常称为 shuffle(混洗)。
因此,MapReduce 并不只是对整个数据集先独立执行映射,再独立执行归约。其本质特征在于这两个阶段之间按键重新分配数据。
词频统计示例
一个经典示例是统计文档集合中各个单词出现的次数。对于每篇文档,映射器输出由单词和整数 1 组成的键值对。框架将相同的单词分组,归约器则将其计数相加。
map(document_id, text):
for each word in text:
emit(word, 1)
reduce(word, counts):
emit(word, sum(counts))
对于以下输入:
red blue red
blue green
中间分组在概念上为:
blue → [1, 1]
green → [1]
red → [1, 1]
输出包含 blue → 2、green → 1 和 red → 2。这些分组的排列顺序并不是模型的本质要求。
实际的词频统计还取决于如何识别单词,包括如何处理标点、大小写和语言差异。这些规则属于应用本身,而非 MapReduce 模型。
执行流程
MapReduce 作业通常经过多个阶段。具体实现因系统而异,但以下结构较为常见。
输入切分与映射
输入被划分为若干逻辑分片,每个分片作为一个映射任务的输入。输入读取器将分片转换为适合 map 函数处理的记录。
分片不一定与物理存储块或整个文件完全对应。记录读取器可以处理边界问题,避免将一条逻辑记录(例如一行文本)不恰当地拆分到不同的 map 调用中。
映射任务可以独立运行。调度器将这些任务分配给可用的工作节点,并可能将任务安排在靠近其输入数据的位置。
分区、混洗与排序
每个中间键都会被分配到一个归约分区。一种常见的分区规则使用哈希函数:
其中, 为归约分区的数量。
所有比较结果相等的键都必须分配到同一分区。否则,它们的值可能由不同的归约器处理,从而破坏预期的分组语义。
映射器的输出通常会先进入缓冲区,随后可能经过排序并溢写到本地存储。归约器从映射任务所在的工作节点拉取分配给自己的分区数据。这些传输构成了混洗阶段的大部分工作。
实现通常会按键对中间记录排序,并在归约前合并拉取到的数据段。排序是实现分组的一种技术,也可支持要求键有序的应用。不过,多份分别排好序的归约器输出,并不会自动构成一个全局有序的序列。
归约与输出
每个归约器处理分配给自己的键及其关联值,然后通过输出格式机制写出结果。
即使集群可同时运行任务的执行槽位较少,一个作业也可以包含大量映射任务和归约任务。工作节点分批执行这些任务。一些框架还支持纯映射作业:当每条输入记录都可以独立处理时,省略混洗和归约阶段。
混洗可以与映射任务的执行重叠进行,但对一个完整键分组的归约必须涵盖所有相关的映射输出。因此,不应将 MapReduce 理解为各个阶段必然严格依次运行、在时间上互不重叠。
合并器与聚合
**合并器(combiner)**可以在映射器输出经网络传输之前,对其进行可选的本地聚合。在词频统计中,映射器可以将多个形如 (word, 1) 的键值对替换为一个局部计数。
无论调用次数和记录分组方式如何变化,正确的合并器都必须保持最终结果不变。在常见实现中,合并器可能不运行,也可能运行一次或多次。应用不能依赖合并器一定会执行。
满足结合律和交换律的运算,例如整数加法,天然适合进行本地合并。更一般地说,计算可以采用一种能够合并的中间表示。
例如,当各组包含的观测值数量不同时,直接对各组平均值再求平均通常是不正确的。正确做法是让每组输出由总和与数量组成的数对:
最终平均值为:
reduce 函数本身并不总是需要满足结合律或交换律。当部分结果需要合并或重新排序时,这些性质才变得重要。浮点数加法也需要谨慎处理:由于有限精度下的舍入,不同聚合顺序可能产生略有差异的数值结果。
分布式执行与容错
MapReduce 框架面向集群计算而设计;在作业执行期间,集群中的个别机器或进程可能发生故障。
数据局部性
早期的大规模实现强调数据局部性:将计算安排在存有所需输入数据的机器上,或安排在其附近。这样做是将代码移到数据所在处,而不是将每条输入记录传给任意一个工作节点,从而减少网络流量。
分布式文件系统可以在多台机器上存储数据块副本,并向调度器提供这些副本的位置信息,以支持这种方式。局部性的作用取决于部署架构;使用远程存储的系统可能更重视网络带宽,以及存算分离架构下的资源管理。
任务重新执行
一种常见的恢复策略是重新运行失败的任务。输入数据始终保存在持久化存储中,而中间数据可以通过重新执行生成它们的映射任务来重建。
在谷歌最初的设计中,映射输出存储在工作节点的本地磁盘上,而已完成的归约输出则写入分布式文件系统。因此,即使某个映射任务此前已经完成,其所在工作节点的丢失仍可能导致相应的中间输出需要重新生成。
确定性的任务函数使这类恢复更容易分析。外部副作用则需要额外的保障措施:如果重试的任务会发送消息或修改外部数据库,这些操作就可能重复发生。框架的输出提交机制并不会自动保证任意外部操作都恰好执行一次。
慢任务与推测执行
少量异常缓慢的任务通常称为拖尾任务,它们可能拖延一个原本已接近完成的作业。有些实现会在其他工作节点上为慢任务启动额外的执行尝试,并采用其中一次成功执行的结果。
这种技术称为推测执行。如果任务缓慢是由某台机器造成的,它可以缩短完成时间。但如果任务缓慢是因为其分区确实包含远多于其他分区的工作量,这种技术的效果就较为有限。
仅有工作节点故障恢复机制,并不能消除所有单点故障。系统可用性还取决于协调器、存储服务和作业元数据管理的设计。
历史与实现
map 和 reduce 这两个名称源于函数式编程中常见的操作。MapReduce 将相关思想与分布式执行、按键分组、自动调度,以及集群规模的故障恢复结合起来。
杰弗里·迪恩和桑杰·格马瓦特在 2004 年发表于操作系统设计与实现研讨会的论文《MapReduce:简化大规模集群上的数据处理》中介绍了谷歌的系统。该论文记录了谷歌用于大规模数据处理的框架,其用途包括与网页索引相关的任务。
随后,Apache Hadoop 以开源软件的形式推动了 MapReduce 的广泛应用。Hadoop 将 MapReduce 执行框架、Hadoop 分布式文件系统,以及不断扩展的数据处理工具生态结合起来。
早期 Hadoop 使用 JobTracker 和 TaskTracker 协调执行。后来,Hadoop 的 YARN 架构将集群资源管理与应用专用的协调机制分离。此后,Hadoop MapReduce 可以作为应用框架,在共享集群基础设施上运行。
MapReduce 并不等同于 Hadoop。它指的是一种编程模型和一类执行技术;Hadoop MapReduce 则是其中一种具体实现。同样,Hadoop 的存储和资源管理组件也可以支持 MapReduce 之外的处理引擎。
应用
MapReduce 尤其适合处理规模大、边界明确的数据集,并且要求在按键聚合之前,有大量工作可以独立完成。常见应用包括:
- **日志处理:**计算请求次数、流量汇总,以及分组事件统计。
- **搜索索引:**构建将词项映射到文档的倒排索引,这是信息检索中的一种重要结构。
- **数据准备:**为数据工程工作流筛选、转换、去重和重组记录。
- **关系数据处理:**实现分组、聚合及某些连接策略。
- **大规模分析:**计算直方图、频率分布,以及其他描述性统计学指标。
- **机器学习准备:**构建特征并处理训练数据。
实现连接的一种方式是:让两个数据集的记录以相同的连接键输出,标记其来源,然后在归约器中进行匹配。如果其中一个数据集足够小,可以分发给各工作节点,或者输入数据已经具有兼容的分区方式,则可以采用其他策略,避免完整的混洗。
一些机器学习算法和图算法可以表示为一系列 MapReduce 作业。这种方式是否高效,取决于通信量、中间结果的大小,以及需要反复遍历数据的次数。
性能与局限
通信与存储成本
映射阶段可能具有良好的扩展性,但混洗阶段可能成为瓶颈。大型中间数据集会消耗网络带宽、排序资源和本地存储。
性能不仅取决于处理器速度或渐近计算复杂性,还取决于数据量、序列化、分区、压缩和存储吞吐量。增加工作节点数量并不一定能带来同比例的加速。
数据倾斜
一个高频出现的键可能将过多工作集中到某个归约器。由于该键的所有值通常属于同一个逻辑分组,增加归约器数量并不能自动解决这种负载不均。
应用有时会将高负载键拆分成临时子键,再在另一个阶段合并部分结果。只有计算本身允许这种分解时,这种方法才可行。
迭代工作负载
传统 MapReduce 系统通常会在作业之间,将作业输出实际写入持久化存储。对于迭代优化、图遍历和交互式分析,反复写入并重新读取相同的数据可能带来高昂开销。
Apache Spark 等数据流引擎支持更灵活的执行图,并能将可复用数据保留在内存中。它们适用于难以通过反复执行映射—混洗—归约作业来高效处理的工作负载,但仍受到通信成本和内存容量的限制。
延迟与流处理
MapReduce 主要用于批处理。任务启动、调度、混洗和输出管理都会引入开销,使传统实现不太适合小型交互式请求或持续更新的结果。
流处理系统引入了事件时间、窗口和持续维护的状态等概念。这些并不属于基本 MapReduce 模型。
表达能力与优化
MapReduce 可以通过多个作业表达广泛的计算,但能够表达并不意味着使用方便或执行高效。复杂工作流可能需要大量中间数据和人工协调。
在关系数据库中,声明式的 SQL结构化查询语言查询允许优化器利用关系运算的相关知识,在不同执行计划之间做出选择。任意编写的 map 和 reduce 函数可能使框架无法了解应用语义,从而限制某些形式的自动优化。构建在分布式处理引擎之上的高层系统通过显式表示各项操作,重新获得了其中一部分信息。
MapReduce 仍是一种有助于理解分区计算、分组聚合,以及通过重新执行来实现恢复的抽象。它在实践中是否适用,取决于工作负载从这些特性中获得的收益,能否超过混洗成本、作业边界和反复将数据写入存储所带来的限制。