MapReduce

MapReduce原理

MapReduce程序分成了一个master和多个worker，master负责分配和调度任务，worker负责执行被分配的Map和Reduce任务。

1. Split input

将输入拆分成多个部分，每一块被称作一个split或则shard。对于M个worker，通常希望有M个拆分块，以便每一个worker都有工作要做。

2. Fork processes

该过程会创建一个master和多个worker。

3. Map

每个Map任务读入分片，并返回键值对。

4. Map worker:Partition

每个worker生成的键值对数据会被分区函数划分为R个分区，分区函数可能会决定哪一个Reduce worker工作与特定的键，但通常只是简单的key % R的哈希。

5. Reduce: Sort (Shuffle)

当所有的map worker完成工作后，master通知reduce worker开始工作。reduce worker通过远程调用(RPC通信)获取键值对，然后再按键排序。排序是非常必要的。排序后，所有出现的相同键都被分组在一起，以便轻松获取与单个键相关联的所有数据。这个过程也被叫做洗牌阶段。

6. Reduce function

使用按键排序的数据，调用用户的 Reduce 函数。 reduce worker 为每个唯一键调用一次 Reduce 函数。该函数传递两个参数：键和与键关联的中间值列表。

整体过程如下：

Lab1实现

任务分析

实验初始代码提供了单进程串行版本，需要我们实现单机多线程并行的版本。任务概述如下：

• 整个 MR 框架由一个 Coordinator 进程及若干个 Worker 进程构成
• Coordinator 进程与 Worker 进程间通过本地 Socket 进行 Golang RPC通信
• 由 Coordinator 协调整个 MR 计算的推进，并分配 Task 到 Worker 上运行
• 在启动 Coordinator 进程时指定 输入文件名 及 Reduce Task 数量
• 在启动 Worker 进程时指定所用的 MR APP 动态链接库文件
• Coordinator 需要留意 Worker 可能无法在合理时间内完成收到的任务（Worker 卡死或宕机），在遇到此类问题时需要重新派发任务
• Coordinator 进程的入口文件为 main/mrcoordinator.goWorker 进程的入口文件为 main/mrworker.go
• 我们需要补充实现 mr/coordinator.go、mr/worker.go、mr/rpc.go 这三个文件