分布式计算模式：MapReduce

什么是分治法？

分治法是将一个复杂、难以直接解决的大问题，分割成一些规模小、可以比较简单或者直接求解的子问题，这些子问题之间相互独立且与原问题形式相同，递归的求解这些子问题，然后将子问题的解合并得到原问题的解。

适合采用分治法的问题有以下特征：

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

采用分治法的核心步骤：

1. 分解原问题
2. 求解子问题
3. 合并解

什么是MapReduce？

Google提出的MapReduce分布式计算模型，是分治法的典型代表，它一开始被应用于搜索领域，后来被广泛应用到解决各种海量数据的计算问题。

MapReduce分为Map和Reduce两个核心阶段，其中Map对应”分“，即把复杂的任务分解为若干”简单的任务“来执行，Reduce对应着”合“，即对Map阶段的结果进行汇总。

MapReduce拆分后的任务具有以下特征：

1. 相对于原始任务来说，拆分后的子任务和原任务是同质的。
2. 多个子任务之间没有依赖，可以独立运行、并行计算。

MapReduce包括三大组件：

1. Master，负责分配任务、协调任务，并未Mapper分配map()函数操作、为Reducer分配reduce()函数操作。
2. Mapper worker，负责Map函数功能，执行子任务。
3. Reducer worker，负责Reduce函数功能，汇总各个子任务的结果。

整个MapReduce的工作流程可以以分为5个阶段：输入、拆分、映射、化简和输出。

什么是Fork-Join模式？

Fork-Join是Java等语言或者库提供的原生多线程并行处理框架，采用线程级的分而治之的计算模式，充分利用多核CPU的优势，以递归的方式把一个任务拆分成多个“小任务”，把多个“小任务”放在多个处理器上运行，即Fork操作，当多个“小任务”执行完成后，在将这些直结果合并起来即可得到原始任务的结果，即Join操作。

Fork-Join模式不能大规模扩展，只适用于在单个Java虚拟机运行，多个小任务虽然运行在不同的处理器上，但是可以互相通信。