用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不是可以实现多线程吗？