MapReduce

1. 引言（Introduction） 我们意识到，我们的大部分计算都涉及对输入中的每个逻辑 “记录” 应用 map 操作，以便计算一组中间键 / 值对，然后将 reduce 操作应用于共享同一键的所有值，以便适当地组合派生数据。我们使用具有用户指定 map 和 reduce 操作的函数模型，使我们能够轻松地并行化大型计算，并使用重新执行作为容错的主要机制。 这项工作的主要贡献是一个简单的和强大的接口，可实现自动并行化和大规模计算的分布，结合起来使用此接口的实现大型商用PC集群上的高性能。 2. 编程模型（Programming Model） Map 和 Reduce 的定义与功能 Map（映射）：是由用户编写的函数，它接受一个输入键值对，然后对输入数据进行处理，产生一组中间键值对。例如在单词计数的例子中，Map 函数会读取文档内容（值），将文档中的每个单词作为键，“1” 作为值，输出一系列 < 单词，“1”> 这样的中间键值对，表示每个单词出现了一次。其作用是将大规模数据的处理分解为对每个独立数据块（逻辑 “记录”）的操作，为后续的合并处理提供基础数据。 Reduce（归约）：同样由用户编写，它接受一个中间键以及与该键相关联的一组值。Reduce 函数的主要任务是将具有相同键的值进行合并处理，通常是将这些值进行某种计算（如求和、连接等），最终生成可能更小的一组值，一般每个 Reduce 调用产生零个或一个输出值。以单词计数为例，Reduce 函数会接收一个单词（键）和该单词对应的所有计数（值的列表），然后将这些计数相加，得到该单词的总出现次数，输出 <单词，总次数> 这样的键值对。Reduce 操作实现了对中间数据的合并和聚合，从而得到最终想要的结果形式。 Map 和 Reduce 函数共同构成了 MapReduce 编程模型的核心，通过这种分而治之的方式，能够在大规模集群上高效地处理海量数据。 典型使用案例（如单词计数） 大型文档集合中每个单词的出现次数的问题 // key: document name // value: document contents map(String key, String value): for each word w in value: EmitIntermediate(w, "1"); // key: a word // values: a list of counts 迭代器，用于遍历与该单词相关联的所有计数 reduce(String key, Iterator values): int result = 0; for each v in values: result += ParseInt(v); Emit(AsString(result)); map: 遍历文档内容中的每个单词w。对于每个单词，使用EmitIntermediate(w, "1")发出一个中间键值对，其中键是单词w，值是字符串"1"。这表示该单词在当前文档中出现了一次（以简单的计数为 1 来表示每次出现）。...