设计数据密集型应用（10-11）：大数据的批处理和流处理

第 10 章和第 11 章，介绍“大数据”的处理，分两个大类：

1. 批处理（Batch Processing），用于处理大规模离线任务。“大规模”体现在：每次处理输入的数据量大；每次处理运行的时间长（可能几分钟～几天）。
2. 流处理（Stream Processing），用于处理半离线、准实时任务。流处理系统每次处理的数据一般是一个刚刚生成的“数据”/“事件（event）”。

大数据处理，主要要解决三个问题：

1. 数据挖掘。
2. 扩展性。
3. 容错性。

批处理系统和流处理系统主要解决 2 和 3 两个问题。

批处理

谈大数据批处理，绕不过的就是 MapReduce。MapReduce 是大数据处理的老祖宗了。

2004 年 Google 发表了一篇论文 MapReduce: Simplified Data Processing on Large Clusters。论文介绍了 MapReduce 的历史，API 的设计和实现，以及 Google 内部使用了 MapReduce 的一些生产案例，但是没有开源代码。后来，开源社区参考这篇论文自己撸了一个 MapReduce 框架配合 HDFS 使用。

MapReduce 的基本思想是提供一套非常简洁的数据处理 API —— 用户只需要实现一个 map 函数和一个 reduce 函数。剩下的繁琐的扩展性和容错系统问题由 MapReduce 框架负责处理。

Map 函数的输入是「一条记录」，然后经过处理，输出 0～N 个 key-value。Mapper 的输出是 Reducer 的输入。

Reduce 函数的输入是「key + key 相同的所有 value」，输出是本次 MapReduce 任务的结果。

一次 MapReduce 的执行流程如下：

1. Map 阶段：
   1. 将 Mapper 任务调度到文件分片所在的机器。
   2. 读取文件，解析数据，然后调用 map 函数，得到输出，根据 key 进行分片（分片数量和 Reducer 的数量一致），写入到文件。
   3. 对得到的每个文件根据 key 进行排序。
2. Reduce 阶段：
   1. 拉取要处理的文件，进行一次合并，得到一个根据 key 排序的文件。
   2. 读取文件，解析数据，然后调用 reduce 函数，得到输出，写入结果文件。

举个例子进行说明：WordCount - 计算文件（一行一个单词）中每个单词出现的次数。

Map 函数：

map(String key, String value) :
  // key: file name
  // value: file content
  for each word w in value :
    EmitIntermediate(w, "1");

Reduce 函数：

reduce(String key, Interator values) :
  // key: a word
  // value: a list of counts
  int result = 0;
  for each v in values :
    result += ParseInt(v);
    Emit(AsString(result));

1. Map 阶段 —— 将文件内容拆成一个个单词：
   1. 将 Mapper 任务调度到文件分片所在的机器。
   2. 读取文件，解析数据，然后调用 map 函数，得到一个个 「word, "1"」的输出。根据单词进行哈希分片，写入到文件。
   3. 对得到的每个文件根据 key 进行排序。这样可以保证同一个单词的 key-value 都在文件中相邻的位置。
2. Reduce 阶段 —— 对每个单词出现的次数进行统计：
   1. 拉取要处理的文件，进行一次合并，得到一个根据 key 排序的文件。
   2. 读取文件，解析数据，然后调用 reduce 函数，得到输出，写入结果文件。

MapReduce 的优点是理解起来简单，实现起来也不难。但是由于 MapReduce 的编程模型过于简单，导致表达能力限制太大，单个 MapReduce 任务并不能完成大量实际上的业务需求。一些比较复杂的系统可能需要 50 ～ 100 个 MapReduce 任务进行组合，这会产生很多中间数据需要写入到分布式文件系统，严重影响执行性能和效率。同时，太多的 MapReduce 任务组合提高了系统的维护难度。

关于 MapReduce 的更多细节，建议阅读论文。

流处理

说到流处理，自然不得不提 Apache Spark 和 Apache Flink（其实我也是在网上道听途说，这两个系统我都不怎么了解……）。

Spark 在 2009 年左右诞生于加州大学伯克利分校的著名 AMPLab。最开始的 Spark 其实是个批处理系统，其能成名的原因是它能够经常在内存执行大量的计算工作，直到作业的最后一步才写入磁盘，性能上比 MapReduce 要好不少。后来，Spark Streaming 的出现，Spark 才开始有了能支持流处理的能力。不过，Spark Streaming 是通过 micro-batch（多个记录/事件） 来模拟 stream 的。从 Spark 最近的版本更新看，Spark Streaming 应该是要被新搞出来的 Structured Streaming 代替了。

和 Spark 不同，Flink 处理流的时候是 per-event 的（一个记录/事件）。打个不太严谨的比方，洗头冲水的时候有两种方式：

1. 拿一个杯子在水龙头接水，再冲到头上 => 这是 Spark 流处理的模式。
2. 直接再水龙头下面冲水 => 这是 Flink 流处理的模式。

小结

最后，推荐一篇论文：Google 在 VLDB2015 发表的：The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing。这篇论文提供了一种统一批处理和流处理的 dataflow 模型。

coredump