every step

Map Reduce

January 12, 2022 • ☕️ 6 min read

按照下面的顺序即可完成：

  1. worker 通过 rpc 获取 task ，随后执行 task 。
  2. 首先是 map task ，执行完后通过 rpc 通知 Coordinator ，Coordinator 更新状态。
  3. 所有 map task 都执行完毕后再分发 reduce task 。
  4. worker 执行 reduce task ，完成后更新更新状态，所有 reduce task 都执行完毕后整个流程结束。
  5. 设置超时时间，超过 10s 重新分配 task 。

Map Reduce 的重要意义是实现了计算的水平扩展，主要分为三部分：map 过程，reduce 过程，容错。worker 从 master 处获取 map 任务，执行完毕后通知 master 。需要设计一个结构体，用来表示 task 。如果用一个 task 表示 map 或 reduce 那么就需要一个字段来表示 task 类型，也可以分开设计。

worker 通过 rpc 从 master 处获取 task 随后处理这个 task 。整体分为两阶段，先执行 map task 再执行 reduce task。执行完 map task 后通知 master 任务执行完毕，master 更新对应 task 的状态，随后 worker 获取新的任务继续执行。worker 如果长时间没有响应，例如 10s 就需要撤销任务，所以可以设置一个时间间隔，判断 worker 是否正在做任务。

1. worker 获取任务是主动还是被动？

在分布式计算框架中，如 MapReduce，关于任务（task）分配给工作节点（worker）的机制，存在两种基本策略：工作节点主动获取任务（worker-initiated）和协调者主动分发任务（coordinator-initiated）。两种策略各有优势和适用场景，选择哪一种取决于系统设计的目标、复杂性和可扩展性要求。

worker 节点主动获取任务

在这种模式下，工作节点（worker）定期向协调者（coordinator）发出请求，询问是否有可用的任务。协调者根据当前的任务队列状态分配任务给请求的工作节点。

优点：

  • 简单性：协调者不需要跟踪各个工作节点的状态，只需响应请求并分配任务。
  • 灵活性：工作节点可以根据自身的处理能力和当前负载来决定何时请求新的任务，从而更灵活地管理工作量。
  • 容错性：如果某个工作节点失败，它将停止请求新的任务，不会影响到系统的其他部分。系统可以设计为重新分配未完成的任务给其他节点。

限制：

  • 效率问题：可能会有很多空闲的工作节点频繁地向协调者请求任务，而在某些时刻可能没有足够的任务可供分配，造成网络和协调者的负载增加。

coordinator 主动分发任务

在这种模式下，协调者主动将任务分配给工作节点。这通常需要协调者维护一个工作节点的状态和能力信息，以便智能地分配任务。

优点：

  • 高效性：协调者可以根据工作节点的能力和当前状态来优化任务分配，减少空闲时间，提高整体的处理速度。
  • 更好的负载均衡：协调者可以实现更复杂的负载均衡策略，确保所有工作节点均匀地分担工作负载。

限制：

  • 复杂性：实现协调者主动分发任务的系统通常更复杂，需要协调者跟踪每个工作节点的状态和通信。
  • 容错性问题：如果协调者分配了任务给一个突然变得不可用的工作节点，可能需要额外的机制来检测这种情况并重新分配任务。

使用场景

  • 工作节点主动获取任务适用于那些具有大量短暂任务的场景，这些任务可以快速分配并执行，以及在工作节点的数量和能力可能有很大变化的环境中。
  • 协调者主动分发任务更适合于任务执行时间较长，需要精细调度以优化资源利用率和处理速度的场景。

在实际应用中，系统设计者需要根据具体的应用场景、性能要求、可用资源以及容错性需求来决定采用哪种策略。例如，Google 的 MapReduce 和 Apache Hadoop 通常采用工作节点主动获取任务的模式，因为它简化了系统设计，易于扩展和管理。

2. 为什么需要 map task 全部做完后才能做 reduce task ？

因为 map task 没有做完 worker 就开始执行 reduce task ，这个 reduce task 的数据不是完整的情况。也就是需要保证 worker 在执行 map 任务所产生的中间文件存在对所有 reduce 任务产生影响的可能。所以需要 map task 全部完成后才能执行 reduce task 。

3. map 任务产生中间文件的命名方式和 reduce 任务读取中间文件的逻辑是什么？

map 过程会将产生的中间文件对 reduce 任务个数取余，这样做是为了将数据均匀分散，避免某个 reduce 任务负担过重。即遍历 N 个 reduce 任务将其写入中间文件中。reduce 过程是反过来的，需要遍历 reduce id 对应的所有的 map 任务产生的中间文件，所以需要记录 map 任务的总个数。

4. 文件存放在哪里？

如果用单机多进程来模拟，因为都在同一台机器上，所以不用考虑这个问题。但是如果在不同物理机上执行就需要一个全局的文件系统了，文章中用的是 GFS 。

5. 下面是两个具体执行过程中的例子。

Map 函数处理键值对并生成中间的键值对，Reduce 函数将所有键相同的中间的键值对合并起来。这两个函数都是暴露给用户，由用户来提供具体的处理逻辑。以词频统计为例，Map 函数负责构造键值对，其中 Key 是 word ，Value 是 1 。reduce 负责将 Key 相同的 Value 累加起来。以 URL 访问频数为例，Key 是 URL，Value 则是访问访问次数。