1、并行计算

并行计算或称平行计算是相对于串行计算来说的它是一种一次可执行多个指令的算法目的是提高计算速度及通过扩大问题求解规模解决大型而复杂的计算问题所谓并行计算可分为时间上的并行和空间上的并行 时间上的并行就是指流水线技术而空间上的并行则是指用多个处理器并发的执行计算。这个是多核处理器环境下的并行计算的定义，从宏观上来看，这个属于计算机应用服务器的垂直扩展，在这里我们就不展开讨论了。

分布式计算上的并行计算，首先要把任务进行拆分，对不同的任务要进行不同的拆分，拆分后进行计算，最终的计算数据进行汇总。

还是到年底了，要做很多的报表，领导把需要的报表安排下来，我和我的团队去做统计。异步计算并不能减少领导拿到最终结果的时间；我们要想办法，我作为调度系统，把需要的报表进行分拆，发现需要8组数据，我安排8位帅哥去获取这些数据，这8位攻城狮把数据提供给我，我按照规则把报表完成，并提供给领导。这个大概就是一个简单的并行计算模型了。

拆分和合并，是在分布式计算中的伟大的思想，这个也是Map/Reduce的思想。

2、Map/Reduce

Map/Reduce，它认为所有的计算任务都可以经历从拆分到汇总的两个过程，也就是说，只要用Map和Reduce就可以描述所有的计算任务，就好比用0和1就能存储所有的数据一样。

MapReduce通过把大工作分成不同的小工作再分发给不同的工作者来实现数据的可靠性。每一个单独的工作者处理分发的工作，然后把结果和状态返回给父节点。如果一个节点失效了，主节点会发现和记录这个失效的节点，把分配给这个节点的工作再分发给别的节点。

3、Map/Reduce执行过程：

1.Master 把输入文件分成M份，通常16M– 64M每份

2.Master选择处于Idle状态的worker，assign一份给他，此时worker的角色是map worker，assign的过程很简单，就是把这个task piece传输到worker上

3.Map worker拿到任务后读取task的内容，解析出key/value pairs，这些中间结果开始是存在worker的内存里面，周期性的写到map worker的本地磁盘上。但是map worker产生的中间结果不是写在一个文件里，而是由partition function分割成R个中间文件，尽量把相同的keykey/value对写在一个中间文件里。

4.当map完成task以后，会把这些partition文件在本地磁盘中的位置通知master。

5.Master接到任务完成的消息后，寻找idle状态的worker，通知他去reduce，此时的worker就是reduce worker（值得注意的是刚刚完成任务的 map worker可能会担当reduce worker的角色），reduce worker通过RPC读取map worker磁盘上的中间文件到本地磁盘，读完之后，reduce worker对其进行排序,如果中间文件太大，就要用外部排序。

Master并不是随便找一个worker来做reduce的，尽量让一个reduce worker做包含同样key的partition文件。

比如：map work1包含R个partition文件，key为K1，K2.。。。。。KR，master会把所有map works产生的partition文件含有K1的尽量交给同一个reduce worker，当然这里面也有个负载平衡的问题。

6.Reduce work把合并后的结果写入一个文件，因为一个reduce worker尽量处理同一个key的partition文件，所以当reduce worker合并完成之后，所有包含这个key的结果都在这个文件里了

7.Reduce work把合并的结果传回master

8.当所有的reduce workers都完成之后，master得到了R个结果文件（每个reduce worker一个），唤醒用户进程，把R个结果文件交给客户程序。

4、Map/Reduce优化

1.合并函数

Map往往会产生大量的key/value对，比如1万个{a,1}，这些都要被reduce来合并，可以在reduce工作之前有合并函数对map中的key/value对进行合并。看起来，合并函数和reduce函数一样，其实还是不同的，合并函数所合并的是map本地的key/value对，产生的结果写入map的本地buffer；reduce函数合并的是来自不同map的partition文件，产生的结果传回master。

2.容错处理

Cluster的庞大集群，机器出现故障是必然的，所以master要进行容错处理。在master上会记录所有集群内或者子群内worker的状态，不断获取正在工作的worker的心跳，如果worker死掉了，那么会把这个worker标记为down，把他上面执行的任务重新分配给另外的worker。但是如果master死掉了怎么办？因为集群内只有一个master，那么需要根据日志进行恢复（可参考分布式文件系统）。

分布式计算之并行计算