分布式：MapReduce

发表于 | 分类于

最近在看MIT的分布式课程Distributed Systems Engineering，把老师讲的一些东西记下来～

背景

在很大的数据集上处理耗时很久的计算

比如数千个应用程序构成的搜索索引的情况，有了MR之后，程序员只需要定义Map和Reduce函数，而不需要考虑分布式的实现细节，MR来负责具体的实现，比如怎么在很多机器上运行，对外只暴露接口。

整体介绍

工作流程

Example: word count
image
输入被分为M个文件，每个文件都调用Map()方法，产生key-value集合（Intermediate data），对于每一个特定的key，MR收集所有情况，传给Reduce()方法，最后输出结果。
上图整个称为一个job，一个job由很多Map Task和很多Reduce Task构成。

伪代码：

1
2
3
4
5
6
Map(k, v)
  split v into words
  for each word w
    emit(w, "1")
Reduce(k, v)
  emit(len(v))

特点

1. MapReduce scales well:

N个工作计算机可以获得Nx的吞吐量（throughput）
Map()s和Reduce()s都可以并行运行，因此可通过扩展计算机的数量来获得更多的吞吐量

2. MapReduce hides many details:

  • 发送代码到服务器
  • 追踪哪些任务完成
  • 将数据从Maps发送到Reduces
  • 平衡服务器的负载
  • 从错误中恢复

3. However, MapReduce limits what apps can do:

  • 无交互或状态（通过中间输出除外）。
  • 没有迭代，没有多级管道（piplelines）。
  • 没有实时处理或流处理。

GFS在MapReduce中有着重要作用

GFS：Google File System

  • 将数据存在很多服务器上，Maps可以并行读，Reduces可以并行写。
  • GFS也可以实现复制（replicates）

MapReduce的现在

Hugely influential (Hadoop, Spark, &c).
Probably no longer in use at Google.
Replaced by Flume / FlumeJava (see paper by Chambers et al).
GFS replaced by Colossus (no good description), and BigTable.