批处理 (Batch Processing)

第 10 章开启第三部分"派生数据(Derived Data)",关于把数据从一处取出并转换到另一处的系统——索引、缓存、聚合、模型。它从批处理(batch processing)开始:取一个大的、有界输入,处理它,产生一个输出,不期待低延迟。Kleppmann 从底层构建想法——从朴实的 Unix 命令行工具开始,它们的设计哲学结果证明是 MapReduce 和驱动大规模分析的现代数据流引擎的概念祖先。

用 Unix 工具做批处理

Kleppmann 从一个看似简单的任务开始:找一个 web 服务器日志里最热门的五个页面。你能用一串标准 Unix 工具做它,而这个例子有出人意料的深度。

cat access.log |             # 流式读日志
  awk '{print $7}' |          # 抽取 URL 字段
  sort |                     # 把相同 URL 分组到一起
  uniq -c |                  # 计数每段重复
  sort -rn |                 # 按计数降序排
  head -n 5                  # 取前 5

魔法在 Unix 哲学:每个程序做好一件事、程序被预期组合、它们共享一个统一接口——stdin/stdout 上的文本流。那种统一正是为什么 sort 能喂 uniq 而两者都不知道对方。一个微妙但重要的细节:sort 通过把有序块溢出到磁盘并合并它们(外部归并排序)来处理大于内存的数据集——分布式系统在规模上用的同一技巧。

MapReduce 与分布式文件系统

MapReduce 在精神上是 Unix 管道铺到数千机器上。不读写本地文件,作业读写一个像 HDFS 的分布式文件系统——跨许多机器的 shared-nothing 磁盘池,文件被切成块、为容错复制。一个 MapReduce 作业有程序员写的两个回调和框架提供的一个步骤:

• Map——每条输入记录调一次;它抽取并 emit 键值对(如每行日志 emit (url, 1))。
• Shuffle——框架按 key 排序所有 emit 的对并分区,使给定 key 的每个值到达同一 reducer。这个排序和分组步骤是 MapReduce 的核心。
• Reduce——每个不同 key 带其所有值调一次;它产生输出(如把 1 求和得计数)。

单个 map-reduce 步骤有限,所以真实作业是工作流:MapReduce 作业的链,一个的输出成为下一个的输入,由 Oozie 或 Airflow 等工具拼在一起。

Join 与分组

把相关记录聚到一起——join——是大部分工程所在:

• Reduce 侧(sort-merge)join。两个输入都被 map 以 emit join key,shuffle 把同 key 的记录带到同一 reducer,reducer join 它们。完全通用,但付排序和 shuffle 所有数据的代价。
• Map 侧 join。尽可能避开 shuffle。广播哈希 join(broadcast hash join)把一个小输入完全加载进每个 mapper 的内存。分区哈希 join在两个输入已按 join key 同样分区时工作,所以每个 mapper 只需匹配的分区。
• 处理倾斜。一个"热"key(社交图里的名人)把大量数据发给一个 reducer,它成掉队者。倾斜/分片 join 等技术把热 key 的负载拆到几个 reducer。

MapReduce vs 分布式数据库

MapReduce 体现一种不同于 MPP(大规模并行处理)分析数据库的哲学。MPP 数据库想数据先加载进 schema 再跑优化 SQL。MapReduce(和 Hadoop 生态)拥抱读时 schema(schema-on-read):把原始数据倾倒进分布式文件系统,读它时再弄清它的结构,支持对同一原始数据的多样、演化的处理(SQL、ML、自定义代码)。这使 Hadoop 成为灵活的"数据湖",代价是 MPP 的查询优化。

输出与容错

批作业通常产生批量输出:构建搜索索引(Google 最初如何用 MapReduce)、训练推荐/ML 模型,或构造要加载进服务系统的只读键值存储。关键设计原则是输入不可变且作业无副作用——作业只读它的输入并写一个全新输出,从不原地修改输入。这几乎免费给出容错:若一个任务失败(机器崩溃),框架只是在另一台机器上重跑它,因为对同一不可变输入的确定计算产生同样结果。它也使实验安全——一个有 bug 的作业能被重跑而没损坏任何东西。

超越 MapReduce:数据流引擎

MapReduce 最大的低效:它在每个 map-reduce 步骤之间把中间状态物化到磁盘(分布式文件系统)。对许多步骤的工作流,这意味反复写和重读(并重复制)数 GB,且每个步骤在前一个完全结束前无法开始。数据流引擎——Spark、Tez、Flink——通过把整个工作流建模为一个连接算子的单一作业来修复这个:

• 它们避免不必要的物化,在算子之间流水线(pipelining)数据并尽可能保在内存。
• 它们把整个图一起调度,使算子能重叠、引擎能跨步骤边界优化。
• 排序(昂贵的 shuffle)只在实际需要处做,而非每个边界。

取舍是容错:没有可回退的物化中间状态,数据流引擎必须重算丢失的数据。Spark 跟踪每个数据集的血缘(lineage)(产生它的操作),这样它能只重算丢失的分区——前提是计算确定。对图和迭代算法(如 PageRank),Pregel 的"像顶点一样思考"方法等专门模型在迭代间于顶点之间传消息,比每遍重跑 MapReduce 高效得多。