在大量的数据处理需求下,程序是分布式运行的,但是每个业务如果都需要针对雷同的问题各自做出雷同的处理,效率太低。
例子
假设一个 number 数组中,我们希望统计出数值大于 5 的那些数向上取整的和。这个问题很简单,常规的写法自然是遍历整个数组,写一个 if-else 判断出大于 5 的数,然后用一个变量做累计求和。但是这个写法引入了状态,在循环里你既需要关心 filter 的逻辑,又要关心累计求和的逻辑,不够清晰。
但是如果这样写:
function(arr) {
arr
.filter(a => a > 5)
.map(a => Math.ceil(a))
.reduce((acc, i) => acc + i);
}
通过三个原语区分开控制逻辑和计算逻辑。
map&reduce如果我们把输入数据表示成一个键值对KEY/VALUE。输出也是。
那么我们只需要做两种操作就可以完成大部分的变化。
- map:对kv进行某种变换,得到和输出集合一样的集合x。这个集合x,既可以作为输出,也可以作为其他需求的中间步骤。
- reduce:进行合并计算,合并一些key不同,但是value相同组合,从而得到一个size比原来数据小的集合。
上面的例子有三种操作:
- 向上取整:进行map
- 过滤5以上的数,进行reduce,得到一个比原来小的集合
- 求和:也是reduce,函数就是简单的加法,但是能得到一个原来一半大小的集合。
除了以上例子:还有很多场景:
- 分布式 Grep 程序,可以用于对大量数据的模式匹配,比如查询日志中某些模式出现的数量。
- 统计 URL 访问频数,把所有的访问记录用 map 函数处理成 (url, 1),再用 reduce 函数对 url 相同的记录,累计计数。
- 网络连接逆向,把 (source, target) map 为 (target, source) ,再用 reduce 把 target 相同的记录中的 source,合并成列表,得到 (target, list(source))。
- 倒排索引,把文本分词,得到 (word, document) 的集合,并对同样的词进行 reduce 操作,得到(word, list(document)),这样就可以用来给搜索引擎加速查询。
几个原则:
- 把数据分区,交给不同的机器执行
- 在要汇总的时候也需要有办法进行数据的汇总
- 并且要有一定应对故障的能力。
整个 MapReduce 系统是要有一套全局共享的存储系统的,这就是谷歌鼎鼎大名的三驾马车中的另一架 GFS(Google File System)的作用,MapReduce 也是建立在这个存储系统之上的。
执行步骤:- 程序先把输入文件分成m个数据段,每个段大小通常是16MB。
- 然后集群快速分发需要计算的任务。我们会让众多进程中的一个成为 master 进程,由它来进行任务的调度,其他进程都是 worker 进程,进行实际的计算任务。master 会把 M 个 map 任务和 R 个 reduce 任务分配给空闲的进程。
- map:worker读取数据之后进行map计算,输出结果缓存在内存中,然后worker通过分区函数,把一些中间temp结果定期落盘,分离在r个区域,这些区域信息传递给master,以便后续reduce使用。
- reduce:worker收到map存的中间temp结果,通过rpc读取。由于reduce需要按key进行聚合,所以读取完数据要做排序。最后进行reduce函数计算结果,结果被分区追加到对应的文件中。
- 两者都执行完,就可得到最后的计算结果。
- 大规模的部署来提高计算能力和稳定性
- 服务也需要长时间在线,不能每次出现故障都由管理员手动恢复。
worker故障:通过master定时ping操作
master 会周期性地给 worker 发送 ping 请求,如果 worker 正常就会回复,所以如果 master 一段时间没有收到回复,会把这个 worker 标记为失效 worker,相关的任务也会被设置为空闲状态,进而分配给其他空闲的 worker。
这里又区分开
map woker任务异常:由于map的结果存在本地节点中,异常节点需要重新执行该节点上所有已经完成的任务
reduce worker任务异常:因为正常完成的直接传输到全局文件中了,没有完成的异常任务是确定的最近的一个,所以只需要重新执行这一个异常的任务即可
master故障:
- 周期性的把 master 相关的状态信息保存到磁盘中,形成一个个检查点。如果master节点任务失败了,就从最近的一个检查点恢复。然后redo之后的操作。
- 对 master 引入 backup 节点,如果一个节点挂了,我们马上把备份的节点拿来当新的主节点使用
ps:但谷歌工程师偷懒,master挂了直接让这个程序挂掉,让用户重新提交任务。
总结所有分布式计算框架比如 Hadoop、Spark、Flink 等等都是建立在 Google MapReduce 工作的基础上的。
系统设计,非常重要的一点就是对容灾能力的支持,主要就要分为故障检测和故障恢复两个步骤。
- 检测:引入一个控制节点对其他节点进行监控是一个非常有效的手段,通过定时的心跳(即我们刚才的ping操作),控制节点就很容易发现其他节点的异常;
- 故障恢复:一个有效手段就是定时设置 checkpoint,定期记录下运行正确时系统的状态,这样异常发生的时候就可以快速恢复,重新执行需要的计算。



