分布式技术之分布式计算MR模式

什么是分而治之？

• 分而治之（Divide-and-Conquer），是计算机处理问题的一个很重要的思想，简称为分治法。顾名思义，分治法就是将一个复杂的、难以直接解决的大问题，分割成一些规模较小的、可以比较简单的或直接求解的子问题，这些子问题之间相互独立且与原问题形式相同，递归地求解这些子问题，然后将子问题的解合并得到原问题的解。

• 在分布式领域，适合分治法的问题具有哪些特征吧。

  • 问题规模比较大或复杂，且问题可以分解为几个规模较小的、简单的同类型问题进行求解；
  • 子问题之间相互独立，不包含公共子问题；
  • 子问题的解可以合并得到原问题的解。

• 采用分治法解决问题的核心步骤是：

  1. 分解原问题。将原问题分解为若干个规模较小，相互独立，且与原问题形式相同的子问题。
  2. 求解子问题。若子问题规模较小且容易被解决则直接求解，否则递归地求解各个子问题。
  3. 合并解，就是将各个子问题的解合并为原问题的解。

分治法的原理

• 分布式原本就是为处理大规模应用而生的，所以基于分布式系统，如何分而治之地处理海量数据就是分布式领域中的一个核心问题。Google 提出的 MapReduce 分布式计算模型（Hadoop MapReduce 是 Google 的开源实现），作为分治法的典型代表，最开始用于搜索领域，后来被广泛用于解决各种海量数据的计算问题。下面以 MapReduce 为例，了解分治法的抽象模型、工作原理和实践应用。

抽象模型

• MapReduce 分为 Map 和 Reduce 两个核心阶段，其中 Map 对应“分”，即把复杂的任务分解为若干个“简单的任务”执行；Reduce 对应着“合”，即对 Map 阶段的结果进行汇总。
  
• 在第一阶段，也就是 Map 阶段，将大数据计算任务拆分为多个子任务，拆分后的子任务通常具有如下特征：
  • 相对于原始任务来说，划分后的子任务与原任务是同质的。并且，子任务的数据规模和计算规模会小很多。
  • 多个子任务之间没有依赖，可以独立运行、并行计算。
• 第二阶段，也就是 Reduce 阶段，第一阶段拆分的子任务计算完成后，汇总所有子任务的计算结果，以得到最终结果。

MapReduce 工作原理

• MapReduce 的组件结构
  
• MapReduce 主要包括以下三种组件：
  • Master，也就是 MRAppMaster，该模块像一个大总管一样，独掌大权，负责分配任务，协调任务的运行，并为 Mapper 分配 map() 函数操作、为 Reducer 分配 reduce()函数操作。
  • Mapper worker，负责 Map 函数功能，即负责执行子任务。
  • Reducer worker，负责 Reduce 函数功能，即负责汇总各个子任务的结果。
• 基于这三种组件，MapReduce 的工作流程如下所示：
  
• 程序从 User Program 开始进入 MapReduce 操作流程。其中图中的“step1，step2，…，step6”表示操作步骤。
  • step1：User Program 将任务下发到 MRAppMaster 中。然后，MRAppMaster 执行任务拆分步骤，把 User Program 下发的任务划分成M 个子任务（M 是用户自定义的数值）。假设，MapReduce 函数将任务划分成了 5 个，其中 Map 作业有 3 个，Reduce 作业有 2 个；集群内的 MRAppMaster 以及 Worker 节点都有任务的副本。
  • step2：MRAppMaster 分别为 Mapper 和 Reducer 分配相应的 Map 和 Reduce 作业。Map 作业的数量就是划分后的子任务数量，也就是 3 个；Reduce 作业是 2 个。
  • step3：被分配了 Map 作业的 Worker，开始读取子任务的输入数据，并从输入数据中抽取出 <key, value> 键值对，每一个键值对都作为参数传递给 map() 函数。
  • step4：map() 函数的输出结果存储在环形缓冲区 kvBuffer 中，这些 Map 结果会被定期写入本地磁盘中，被存储在 R 个不同的磁盘区。这里的 R 表示 Reduce 作业的数量，也是由用户定义的。在这个案例中，R=2。此外，每个 Map 结果的存储位置都会上报给MRAppMaster。
  • step5：MRAppMaster 通知 Reducer 它负责的作业在哪一个分区，Reducer 远程读取相应的 Map 结果，即中间键值对。当 Reducer 把它负责的所有中间键值对都读过来后，首先根据键值对的 key 值对中间键值对进行排序，将相同 key 值的键值对聚集在一起，从而有利于 Reducer 对 Map 结果进行统计。
  • step6：Reducer 遍历排序后的中间键值对，将具有相同 key 值的键值对合并，并将统计结果作为输出文件存入负责的分区中。
• 从上述流程可以看出，整个 MapReduce 的工作流程主要可以概括为 5 个阶段，即：Input（输入）、Splitting（拆分）、Mapping（映射）、Reducing（化简）以及 FinalResult（输出）。
• 所有 MapReduce 操作执行完毕后，MRAppMaster 将 R 个分区的输出文件结果返回给User Program，用户可以根据实际需要进行操作。比如，通常并不需要合并这 R 个输出文件，而是将其作为输入交给另一个 MapReduce 程序处理。

知识扩展：Fork-Join 计算模式是什么意思呢？
Fork-Join 是 Java 等语言或库提供的原生多线程并行处理框架，采用线程级的分而治之计算模式。它充分利用多核 CPU 的优势，以递归的方式把一个任务拆分成多个“小任务”，把多个“小任务”放到多个处理器上并行执行，即 Fork 操作。当多个“小任务”执行完成之后，再将这些执行结果合并起来即可得到原始任务的结果，即 Join 操作。虽然 MapReduce 是进程级的分而治之计算模式，但与 Fork-Join 的核心思想是一致的。因此，Fork-Join 又被称为 Java 版的 MapReduce 框架。
MapReduce 和 Fork-Join 之间有一个本质的区别：Fork-Join 不能大规模扩展，只适用于在单个 Java 虚拟机上运行，多个小任务虽然运行在不同的处理器上，但可以相互通信，甚至一个线程可以“窃取”其他线程上的子任务。MapReduce 可以大规模扩展，适用于大型计算机集群。通过 MapReduce 拆分后的任务，可以跨多个计算机去执行，且各个小任务之间不会相互通信。

你知道的越多，你不知道的越多。