MapReduce作业执行模型：Mapper、排序混洗与Reducer

MapReduce把[[Unix工具批处理排序与内存聚合的权衡]]中日志分析管道的四个步骤（读记录→提取键值→按键排序→按键归并处理）固化成一个可分布式并行执行的框架，对应两个由开发者实现的回调函数：Mapper对每条输入记录调用一次，独立提取任意数量的键值对，不保留跨记录状态；Reducer接收某个键的所有值（已排序、以迭代器形式给出），可以产出任意数量的输出记录。并行化基于分区：输入文件的每个分块对应一个Map任务，调度器尽量让Mapper运行在存有对应数据的机器上；Reducer任务数量由作业作者配置，框架用键的哈希值决定某个键值对该送去哪个Reducer。排序在这里不是可选步骤而是MapReduce隐含实现的：每个Mapper先按Reducer分区把输出写到本地磁盘（用到与[[SSTable按键排序换来高效合并与稀疏内存索引]]类似的技术），一旦某个Mapper读完输入、写完排序后的输出，调度器就通知对应的Reducer来下载自己的分区——这一整套”分区、排序、跨机器复制数据”的过程被称为混洗（shuffle）。Reducer把从各个Mapper收到的文件合并、保持有序，从而让同一个键的记录在Reducer输入中彼此相邻。

结构图：

flowchart LR
    subgraph Map阶段
    I1[输入分块1] --> M1[Mapper1]
    I2[输入分块2] --> M2[Mapper2]
    I3[输入分块3] --> M3[Mapper3]
    end
    M1 --> S[混洗: 按键哈希分区+本地排序+跨机器复制]
    M2 --> S
    M3 --> S
    S --> R1[Reducer1]
    S --> R2[Reducer2]
    R1 --> O1[输出文件]
    R2 --> O2[输出文件]