前情回顾
Google MapReduce到底解决什么问题？
Google MapReduce是Google产出的一个编程模型，同时Google也给出架构实现，它能够解决“能用分治法解决的问题”。
----
Google MapReduce有啥巧妙优化？
- 分区函数：保证不同map输出的相同key，落到同一个reduce里
- 合并函数：在map结束时，对相同key的多个输出做本地合并，节省总体资源
- 输入文件到map如何切分：随意，切分均匀就行
画外音：看懂了这个流程，对工程架构的理解，会容易很多。
上述执行流程，Google MapReduce通过怎样的工程架构实现的呢？
先看下总体架构图，有个直观的印象。
用户使用GoogleMR系统，必须输入的是什么？
输入数据，必选
画外音：否则系统处理啥。
map函数，必选
reduce函数，必选
画外音：分治法，分与合的业务逻辑。
分区函数，必选
画外音：保证同一个key，在合并阶段，必须落到同一个reduce上，系统提供默认hash(key)法。
合并函数，可选
画外音：看用户是否需要在map结束阶段进行优化。
用户提供各个输入后，GoogleMR的执行流程是什么？
画外音：
不妨假设，用户设置了M个map节点，R个reduce节点；例如：M=500，R=200
(1) 在集群中创建大量可执行实例副本(fork)；
(2) 这些副本中有一个master，其他均为worker，任务的分配由master完成， M个map实例和R个reduce实例由worker完成；
(3) 将输入数据分成M份，然后被分配到map任务的worker，从其中一份读取输入数据，执行用户的map函数处理，并在本地内存生成临时数据；
(4) 本地内存临时数据，通过分区函数，被分成R份，周期性的写到本地磁盘，由master调度，传给被分配到reduce任务的worker；
(5) 负责reduce任务的worker，从远程读取多个map输出的数据，执行用户的reduce函数处理，处理结果写入输出文件；
画外音：可能对key要进行外部排序。
(6) 所有map和reduce的worker都结束工作后，master唤醒用户程序，MapReduce调用返回，结果被输出到了R个文件中。
GoogleMR系统里的master和worker是啥？
(1) master：单点master会存储一些元数据，监控所有map与reduce的状态，记录哪个数据要给哪个map，哪个数据要给哪个reduce，掌控全局视野，做中控；
画外音：是不是和GFS的master非常像？
(2) worker：多个worker进行业务逻辑处理，具体一个worker是用来执行map还是reduce，是由master调度的；
画外音：是不是和工作线程池非常像？这里的worker是分布在多台机器上的而已。
master的高可用是如何保证的？
一个简单的方法是，将元数据固化到磁盘上，用一个shadow-master来做高可用。
画外音：GFS不就是这么干的么？
然而现实情况是：没有将元数据固化到磁盘上，元数据被存放在master的内存里用以提高工作效率，当master挂掉后，通知用户“任务执行失败”，让其选择重新执行。
画外音：
(1) 单点master，掌控全局视野，能让系统的复杂性降低非常多；
(2) master挂掉的概率很小；
(3) 不做高可用，能让系统的复杂性降低非常多；
worker的高可用是如何保证的？
master会周期性的ping每个worker，如果超时未返回，master会把对应的worker置为无效，把这个worker的工作任务重新执行：
如果重新执行的是reduce任务，不需要有额外的通知
如果重新执行的是map任务，需要通知执行reduce的worker节点，输入数据换了一个worker
随时都可能有map或者reduce挂掉，任务完成前重新被执行，会不会影响MR的最终结果？
在用户输入不变的情况下，MR的输出一定是不变的，这就要求MR系统必须具备幂等性：
对相同的输入，不管哪个负责map的worker执行的结果，一定是不变的，产出的R个本地输出文件内容也一定是不变的
对于M个map，每个map输出的R个本地文件，只要这些输入不变，对应接收这些数据的reduce的worker执行结果，一定是不变的，输出文件内容也也一定是不变的
长尾效应怎么解决？
一个MR执行时间的最大短板，往往是“长尾worker”。
导致“长尾worker”的原因有很多：
(1) 用户的分区函数设计得不合理，导致某些reduce负载不均，要处理大量的数据；
画外音：
最坏的情况，所有数据最终都落到一个reduce上，分布式并行处理，转变为了单机串行处理；
所以，分区函数的负载均衡性，是用户需要考虑的。
(2) 因为系统的原因，worker所在的机器磁盘坏了，CPU有问题，也可能导致任务执行很慢；
GoogleMR有一个“备用worker”的机制，当某些worker的执行时间超出预期时，会启动另一个worker执行相同的任务，以尝试解决长尾效应。
总结
Google MapReduce架构，提现了很多经典架构实践：
单点master简化系统复杂度
单点master不高可用，简化系统复杂度
master对worker的监控以及重启，保证worker高可用
幂等性，保证结果的正确性
多个worker执行同一个任务优化长尾问题
架构师之路-分享可落地的技术文章
