内容简介:搞架构的人,Google的架构论文是必看的,但好像大家都不愿意去啃英文论文。故把自己的读书笔记,加入自己的思考,分享给大家。
搞架构的人,Google的架构论文是必看的,但好像大家都不愿意去啃英文论文。故把自己的读书笔记,加入自己的思考,分享给大家。
《 MapReduce到底解决什么问题? 》做了简介,这是 第二篇,Google MapReduce优化启示(中)。
什么是MapReduce?
MapReduce这个编程模型解决什么问题?
Google MapReduce是Google产出的一个编程模型,同时Google也给出架构实现。它能够解决“ 能用分治法解决的问题 ”。
同时,前文以“统计大量文档中单词出现的个数”为例,例举了如何“先分再合”的撰写map与reduce来解决实际问题。
画外音,强烈建议回顾一下前情提要:
《 MapReduce到底解决什么问题? 》。
MapReduce的 核心思路 是:
-
并行
-
先分再合
下图简述了MR计算“词频统计”的过程。
从左到右四个部分,分别是:
-
输入文件
-
分:M个并行的map计算实例
-
合:R个并行的reduce计算实例
-
输出结果
先看最后一步,reduce输出最终结果。
可以看到,R个reduce实例并发进行处理,直接输出最后的计数结果。
实例1输出: (a, 256)(able, 128)(emacs, 1)
实例2输出: (f*ck, 32768) (coding, 65535)
实例3输出: (vim,65535)(x, 16)(zero, 258)
画外音:这就是总结果,可以看到vim比emacs受欢迎很多。
需要理解的是,由于这是业务计算的最终结果, 一个单词的计数不会出现在两个实例里 。即:如果(a, 256)出现在了实例1的输出里,就一定不会出现在其他实例的输出里。
画外音:否则的话,还需要合并,就不是最终结果了。
再看中间步骤,map到reduce的过程。
可以看到, M个map实例的输出,会作为R个reduce实例的输入 。
潜在问题一 :每个map都有可能输出(a, 1),而最终结果(a, 256)必须由一个reduce输出,那 如何保证每个map输出的同一个key,落到同一个reduce上去呢?
这就是“分区函数”的 作用 。
什么是分区函数?
分区函数,是使用MapReduce的用户需所实现的,决定map输出的每一个key应当落到哪个reduce上的函数。
画外音:如果用户没有实现,会使用默认分区函数。
以词频统计的应用为例,分区函数可能是:
(1) 以[a-g]开头的key落到第一个reduce实例;
(2) 以[h-n]开头的key落到第二个reduce实例;
(3) 以[o-z]开头的key落到第三个reduce实例;
画外音:有点像数据库水平切分的“范围法”。
分区函数实现要点是什么?
为了保证每一个reduce实例都能够差不多时间结束工作任务,分区函数的 实现要点 是: 尽量负载均衡 。
画外音:即数据均匀分摊。
上述词频统计的分区函数,就不是负载均衡的,有些reduce实例处理的单词多,有些reduce处理的单词少,这样就可能出现,所有reduce实例都处理结束, 最后等待一个长尾reduce 的情况。
对于词频统计,负载更为均衡的分区函数为:
hash(key) % 3
画外音:有点像数据库水平切分的“哈希法”。
潜在问题二 :每个map都有可能输出 多个 (a, 1),这样无形中增大了网络带宽资源,以及reduce的计算资源, 有没有办法进行优化呢?
这就是“合并函数”的作用。
什么是合并函数?
有时,map产生的 中间key的重复数据 比重很大,可以提供给用户一个自定义函数, 在一个map实例完成工作后,本地就做一次合并 ,这样网络传输与reduce计算资源都能节省很多。
合并函数在每个map任务结束前都会执行一次,一般来说,合并函数与reduce函数是一样的,区别是:
-
合并函数 执行map实例 本地数据合并
-
reduce函数 执行最终的合并,会收集 多个map实例的数据
对于词频统计应用,合并函数可以将:
一个map实例的多个(a, 1)合并成一个(a, $count)输出。
最后看第一个个步骤,输入文件到map的过程。
潜在问题三 : 如何确定文件到map的输入呢?
随意即可,只要负载均衡,均匀切分输入文件大小就行,不用管分到哪个map实例。
画外音:无论分到那个map都能正确处理。
结论
Google MapReduce实施了一系列的优化。
-
分区函数 :保证不同map输出的相同key,落到同一个reduce里
-
合并函数 :在map结束时,对相同key的多个输出做本地合并,节省总体资源
-
输入文件到map如何切分 :随意,切分均匀就行
希望大家对MapReduce的优化思路有一个了解, 思路比结论更重要 。
下章,讲Google MapReduce的工程架构实现。
架构师之路-分享 可落地 的技术文章
相关推荐:
《 GFS架构启示 》
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Pro Django
Marty Alchin / Apress / 2008-11-24 / USD 49.99
Django is the leading Python web application development framework. Learn how to leverage the Django web framework to its full potential in this advanced tutorial and reference. Endorsed by Django, Pr......一起来看看 《Pro Django》 这本书的介绍吧!