用JavaScript阐述MapReduce原理
谷歌在2003到2006年间连续发表了三篇非常有影响力的文章,分别是2003年在SOSP上发布的GFS,2004年在OSDI上发布的MapReduce,以及2006年在OSDI上发布的BigTable。GFS是文件系统相关的,其对后来的分布式文件系统设计具有指导意义;MapReduce是一种并行计算的编程模型,用于作业调度;BigTable是一个用于管理结构化数据的分布式存储系统,构建在GFS、Chubby、SSTable等Google技术之上。相当多的Google应用使用了这三种技术,比如Google Search、Google Earth和Google Analytics等等。因此这三种技术并称为谷歌技术”三宝”。今天,D瓜哥班门弄斧,对MapReduce来个”庖丁解牛”!
MapReduce简介
MapReduce是一个编程模型,也是一个处理和生成超大数据集的算法模型的相关实现。用户首先创建一
个Map函数处理一个基于key/value pair的数据集合,输出中间的基于key/value pair的数据集合;然后
再创建一个Reduce函数用来合并所有的具有相同中间key值的中间value值。
一图胜千言,下面我们用一张图来说明一下MapReduce:
编程实践
常言道:”实践出真知” 。是骡子是马,拉出来遛遛才知道。所以,如果真的想搞懂这个原理,还是亲自写代码实践一下才是硬道理。
最近和几个朋友一起学习JavaScript,所以就比较关注JavaScript。昨天上网瞎逛时,惊奇地发现,竟然有牛人使用JavaScript实现了MapReduce算法。然后转过来和大家分享,同时再加上我自己的一些狗尾续貂的介绍,希望有助于大家理解MapReduce。具体代码实现如下:
01 | var Job = { |
02 | //待处理的数据 |
03 | data : [ |
04 | "We are glad to see you here. This site is dedicated to" , |
05 | "poetry and to the people who make poetry possible" , |
06 | "poets and their readers. FamousPoetsAndPoems.com is" , |
07 | "a free poetry site. On our site you can find a large" , |
08 | "collection of poems and quotes from over 631 poets" , |
09 | "Read and Enjoy Poetry" , |
10 | "I, too, sing America" , |
11 | "I am the darker brother" , |
12 | "They send me to eat in the kitchen" , |
13 | "When company comes" , |
14 | "But I laugh" , |
15 | "And eat well" , |
16 | "And grow strong" , |
17 | "Tomorrow" , |
18 | "Ill be at the table" , |
19 | "When company comes" , |
20 | "Nobodyll dare" , |
21 | "Say to me" , |
22 | "Eat in the kitchen" , |
23 | "Then" , |
24 | "Besides" , |
25 | "Theyll see how beautiful I am" , |
26 | "And be ashamed" , |
27 | "I, too, am America" |
28 | ], |
29 | |
30 | //将数据中的每行字符串用空格分隔开, |
31 | //并"重组"成诸如{key: 单词, value: 1}格式的对象,返回对象数组 |
32 | map : function (line) { |
33 | var splits = line.split( " " ); |
34 | var temp = []; |
35 | for ( var i=0; i<splits.length; i++) { |
36 | temp.push({key : splits[i], value : 1}); |
37 | } |
38 | return temp; |
39 | }, |
40 | |
41 | //计算每个单词在"数据"(data)中出现的次数 |
42 | reduce : function (allSteps) { |
43 | var result = {}; |
44 | for ( var i=0; i<allSteps.length; i++) { |
45 | var step = allSteps[i]; |
46 | result[step.key] = result[step.key] ? (result[step.key] + 1) : 1; |
47 | } |
48 | return result; |
49 | }, |
50 |
51 | //初始化,同时是运行的入口。 |
52 | init : function () { |
53 | var allSteps = []; |
54 | for ( var i=0; i<Job.data.length; i++) { |
55 | //如果这里能多线程调用Job.map函数就更逼真了。?? |
56 | allSteps = allSteps.concat(Job.map(Job.data[i])); |
57 | } |
58 | //美中不足,这里不能多线程调用Job.reduce函数?? |
59 | var result = Job.reduce(allSteps) |
60 | console.log(JSON.stringify(result)); |
61 | } |
62 |
63 | }; // Job |
64 |
65 | //开始执行 |
66 | Job.init(); |
复制这些代码,直接粘贴到浏览器的控制台(Console)中,或者放到一个HTML文件中,用浏览器打开,就可以在控制台输出中,看到效果如下:
1 | {"631":1,"We":1,"are":1,"glad":1,"to":5,"see":2,"you":2,"here.":1,"This":1,"site":2,"is":2,"dedicated":1,"poetry":3,"and":4,"the":5,"people":1,"who":1,"make":1,"possible":1,"poets":2,"their":1,"readers.":1,"FamousPoetsAndPoems.com":1,"a":2,"free":1,"site.":1,"On":1,"our":1,"can":1,"find":1,"large":1,"collection":1,"of":1,"poems":1,"quotes":1,"from":1,"over":1,"Read":1,"Enjoy":1,"Poetry":1,"I,":2,"too,":2,"sing":1,"America":2,"I":3,"am":3,"darker":1,"brother":1,"They":1,"send":1,"me":2,"eat":2,"in":2,"kitchen":2,"When":2,"company":2,"comes":2,"But":1,"laugh":1,"And":3,"well":1,"grow":1,"strong":1,"Tomorrow":1,"Ill":1,"be":2,"at":1,"table":1,"Nobodyll":1,"dare":1,"Say":1,"Eat":1,"Then":1,"Besides":1,"Theyll":1,"how":1,"beautiful":1,"ashamed":1} |
美中不足
这篇文章发布出来之后,就有网友“咆哮”:“一个连多线程都没有的js 搞什么MapReduce啊?”其实,这个问题,D瓜哥也发现了。在看到这个代码的解释后,D瓜哥就纳闷JavaScript不是单进程吗?怎么还能模拟MapReduce?在认真阅读代码,单步调试之后,更加印证了D瓜哥的看法。(关于D瓜哥的疑问已经在代码中注释出来。)
不过,再想一下,这些并不影响我们去理解MapReduce的原理。这只是个单进程,最基础的版本。先理解了这个,再去整个多线程的也许就更容易理解了。
未完待续
其实,D瓜哥现在考虑在这个例子的基础上,用Java实现一个多线程版本,那样模拟的MapReduce更逼真。等D瓜哥把一些问题思考清楚之后,就把代码发出来。敬请期待!
特别鸣谢:
感谢网友“上海-听说”(扣扣昵称)的质疑,让D瓜哥有更大的兴趣把MapReduce更深入的研究下去。同时,也希望有更多的网友提出问题,促使我们更深入广泛地去讨论、学习和理解MapReduce。
参考资料:
- Simple MapReduce with Javascript
- Google三大论文(中文版)下载链接
- 维基百科上对MapReduce的解释
- 谷歌技术”三宝”之MapReduce
- 谷歌技术”三宝”之BigTable
- 谷歌技术”三宝”之谷歌文件系统
原文链接:https://wordpress.diguage.com/archives/75.html
版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。
Maybe you’ve seen a lot of articles, but you can’t miss this one.
D瓜哥,好文章要及时分享哦!当然更支持原创,呵呵,即使不是原创也要加入自己的理解想法!支持
放心,有东西就会和大家分享。只是担心,东西不好,“不堪入目”;更怕误人子弟!所以,有啥问题和不妥,一定要留言指出。谢谢!哈哈
瓜哥总是很给力
弱弱的问一下,用多进程实现行不?
JavaScript不支持多线程。以后用Java实现一下多线程版的吧。
Very impressive:)
用worker不是可以实现多线程吗?