https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=456546&page=2
这里主要描述的是MapReduce 系统的构建，因为我简历里面写了MapReduce，之前在网上也看了挺多比如如何用mapreduce解决排序这样的问题，后来一次面试的时候挂在了讨论如何设计MapReduce系统中的master，然后就意识到了，还是要了解系统构建的，毕竟以后的工作可能是自己给MapReduce写client方或者Server方的API这样的工作，而不是用MapReduce跑数据。
在这之前先看一下我们（或者面试官）可能关注的点：
1.Implement： 如何用多线程和Remote procedure call 来实现功能
2.Performance：如何衡量并提高系统的performance，比如scaling，问题的关键是要找出系统的bottleneck在哪里
3.Fault Tolerance： 如果某个机器挂了怎么办, 如果数据挂了怎么办
4.Consistency：如何保证replica都是一样的，如何保证log和内存和disk是一样的。很难保证100%的consistency，那样performance会很差，但是可以满足weak consistency。
然后来看MapReduce：
MapReduce想要做的事情，就是用distribute的思想来处理大数据，举个例子：
input: 一个文件，100行，文件可以是NoSQL的key-value形式
key value
a 1
b 2
c 3
a 31
… …
output：一个按照key排好序的文件
key value
a 1
a 2
a 31
… …
如果我的计算机内存只能读取10行，但是有无限个计算机，怎么做？
最简单的distributed思想是，先把文件分成10个，每个文件10行，然后用10个计算机排序（每个计算机时间是O(10log10)）然后输出10个排序好的文件，最后用第11个计算机，来一个10路归并（时间 O(100log(10))），同时输出成最后的output。所以在这个算法里，bottleneck是最后那个10路归并。
MapReduce的处理方法是这样的：
首先分成10个文件，然后输出的不是10个文件，而是260个，比如第一个计算机输出的26个文件是xxx_1_a.txt,xxx_1_b.txt … 分别对应key开头字母为a, b,c ..
最后merge的时候，用26台计算机，比如第一个台专门处理key开头字母为a的那些file：xxx_1_a.txt,xxx_2_a.txt …这样以来bottleneck就被解决了
MapReduce工作流
1.把数据分成M个小文件(每块大概16M-64M),然后把map-reduce的程序copy给workers和 master
2.Master管理workers来执行map，reduce。以map为例子，master有一个map workers pool，还有一个map taskspool，workers pool里找到worker，来执行map task，worker完成任务之后回收到pool里等待被分配下一个task
3.Map worker 收到一个文件还有map function， 开始执行mapfunction，比如sort，然后把结果存在bufferedmemory中，每隔一段时间，再按照reduce的key 分类规则写入到local disk（比如abcd字母开头，这是一种规则）。完成之后，把这些文件的地址返回给master
4.Master确认所有map tasks pool中任务都被执行了之后，建立reducetasks pool，从reduce workers pool中分配机器来完成reduce任务
5.Reduce worker 通过RPC收到file list，还有 reduce function， 根据intermeidatekey排序这些files （外排序），并且写入到最终文件
6.当所有的Reduce tasks被完成之后，Master向user 汇报完成任务
然后我们按照之前说过的点一个一个看：
Implement： MapReduce系统实现
Master:
数据结构：
-Mutex 进程锁
-string workers[]: workers RPC address
-string files[]: input files
-int nReduce: reduce的数量
-int stats[]
functions:
+Register: worker call register来汇报自己状态，同时存储这个worker到worker pool
+newMaster: initial 一个 master
+killWorker
+run:从worker pool里选择worker来执行task
Worker：
数据结构：
+map
+reduce
-name
-nTasks
-nConcurrent
functions:
+run
+register
+shutdown
Performance：
提高performance最重要的是找到系统的bottleneck，对于mapreduce，bottleneck就是 RPC的网速带宽。intermediatedata是存放在local disk，但是input 和 output是在GFS上进行的。这里的解决办法是，因为GFS上每个file都有3份replica，所以Master会根据3份replica的地址选择map worker，理想情况下，map worker处理的这个input正好在这个disk上，相当于从local读取数据
Faulttolerance：
Master挂了：换个master整个重新做
Worker挂了： master每隔一段时间就ping一下works，如果一段时间没回应就是挂了
Mapworker：可能是replica出了问题，也可能是worker出了问题，所以换一个replica，同时换一个worker重新执行
Reduceworker：如果任务已经finish了，重启就行了；如果任务没有finish，那么把挂掉的worker设置成idle，重新选一个worker执行这个任务
Consistency：
Itis a deterministic system. So the consistency should be good.
如果两个worker同时做一个map，会生成两个file，reduce只读其中一个
如果两个worker同时做一个reduce，在GFS中只会有一个可见
总结：
MapReduce适用于离线大数据分析
不适合iterative任务，因为每次要写入读出到GFS
不适合小数据，以及低延迟的系统