阅读 MapReduce 的笔记总结

<!--more-->

# 摘要

MapReduce 架构的程序能够在大量的普通配置的计算机上**实现并行化**处理。**这个系统在运行时只关心：如何分割输入数据，在大量计算机组成的集群上的调度，集群中计算机的错误处理，管理集群中计算机之间必要的通信。**

# 1 介绍

## 背景

1. Google 要处理海量的原始数据（文档抓取、日志分析等）
2. 可接受的时间内完成数据的处理

## 需求

- 设计一个抽象模型，只需要表达想执行的简单运算就行
- 不必关注并行、容错、数据分布等细节

## 灵感来源

- Lisp 以及许多函数式语言的 Map Reduce 原语
- 大多数运算都可被抽象为：
    1. 原始输入数据应用可以得到一个中间产物 key/value  集合
    2. 相同 key 的 value 上使用 Reduce 操作，进行合并操作，得到一个想要的结果。

# 2 编程模型

## 基本原理

利用一个输入 key/value pair 集合来产生一个输出的 key/value pair 集合。

MapReduce 库的用户用两个函数表达这个计算：Map 和 Reduce。

 用户自定义的 Map 函数接受一个输入的 key/value pair 值，然后产生一个中间 key/value pair 值的集合。

MapReduce 库把所有具有相同中间 key 值 I 的中间 value 值集合在一起后传递给 reduce 函数。

用户自定义的 Reduce 函数接受一个中间 key 的值 I 和相关的一个 value 值的集合。Reduce 函数合并这些 value 值，形成一个较小的 value 值的集合。

一般的，**每次 Reduce 函数调用只产生 0 或 1 个输出 value 值**。

通常我们通过一个迭代器把中间 value 值提供给 Reduce 函数，这样我们就可以处理无法全部放入内存中的大量 的 value 值的集合。

​ 这一计算模型的优势在于**非常利于并行化**,map 的过程可以在多台机器上而机器之间不需要相互协调。reduce 的执行同样不需要协调，没有相互依赖可并行执行。所有的依赖性和协调过程都被隐藏在 map 与 reduce 函数的数据分发之间。因此这里有一个很重要的细节就是 **map 和 reduce 都是可以各自并行执行，但 reduce 执行的前提条件是所有的 map 函数执行完毕**。

作为一个编程模型，mapreduce 如此工作 但是这一过程想要落地就必须要考虑工程上的永恒问题 **可靠性** 与 **性能**。大规模的机器产生局部性的失败是一种必然现象，因此如果 mapreduce 分散在多台机器上执行，其中一个 map 任务失败导致整个处理过程都需要重新计算这是不可接受的。因此 对于大规模分布式程序来说 能够应对局部性失败的容错性 与性能同等重要。这是一个必要的问题，**分布式的容错性本质上就是如何在不可靠的硬件之上构建可靠的软件。**

所以 作为一个成熟的工业级实现 MapReduce 就是一个 **利用普通机器组成的大规模计算集群进行并行的，高容错，高性能的数据处理函数框架。**

## 例子

例如，计算一个大的文档集合中每个单词出现的次数，下面是伪代码段：

```go
// 自定义的中间产物的数据结构 译者自己修改
type KeyValue struct {
 Key string 
 Value string
}

func map(key,value string)[]KeyValue{
 // key: document name
 // value: document contents
  // 文档内容解析为单词
  words := parseWord(value)
 for w range words:
  EmitIntermediate(w, "1")
}
func reduce(key string ,values []string) string{
 // key: a word
 // values: a list of counts
 int result = 0;
 for each v in values:
  result += ParseInt(v);
 Emit(AsString(result));
}
```

Map 函数输出文档中的每个词、以及这个词的出现次数 (在这个简单的例子里就是 1)。

Reduce 函数把 Map 函数产生的每一个特定的词的计数累加起来。

## 具体的例子

分布式的 Grep：Map 函数输出匹配某个模式的一行，Reduce 函数是一个恒等函数，即把中间数据复制到输出。

计算 URL 访问频率：Map 函数处理日志中 web 页面请求的记录，然后输出 (URL,1)。Reduce 函数把相同 URL 的 value 值都累加起来，产生 (URL，记录总数) 结果。 （译者注：和单词计数类似）

倒转网络链接图：Map 函数在源页面（source）中搜索所有的链接目标（target）并输出为 (target,source)。Reduce 函数把给定链接目标（target）的链接组合成一个列表，输出 (target,list(source))。

每个主机的检索词向量：检索词向量用一个 (词，频率) 列表来概述出现在文档或文档集中的最重要的一些 词。Map 函数为每一个输入文档输出 (主机名，检索词向量)，其中主机名来自文档的 URL。Reduce 函数接收给定主机的所有文档的检索词向量，并把这些检索词向量加在一起，丢弃掉低频的检索词，输出一个最终的 (主机名，检索词向量)。

倒排索引：Map 函数分析每个文档输出一个 (词，文档号) 的列表，Reduce 函数的输入是一个给定词的所有（词，文档号），排序所有的文档号，输出 (词，list（文档号）)。所有的输出集合形成一个简单的倒排索引，它以一种简单的算法跟踪词在文档中的位置。

分布式排序：Map 函数从每个记录提取 key，输出 (key,record)。Reduce 函数不改变任何的值。

# 3 实现