Map reduce的使用场景介绍，请懂这门手艺的童鞋指点

[magicshui]

一直听到这个名词，也搜索了相关文章，但是还是不明白mapreduce具体的应用场景，请懂的童鞋指点一下，最好能够有一个生动活泼的例子，恩恩，谢谢

[clowwindy]

比方说现在存了一亿个网页，key是URL，value是网页内容。
map（映射）的时候把网页内容拆成词，按照key是词，value是URL和其它meta信息的方式输出。
在reduce（化简）函数中可以得到一个key（词）对应的所有value（URL，meta）。再做进一步处理，比方说根据词频排个序，然后输出。
这样就得到了词->URL的对应关系。

[muxi]

例子很多的，举个简单的例子

例如淘宝这样的网站，每天有各种页面浏览几十亿次，每次浏览实际上web服务器（比如apache、Nginx）之类都会产生一个请求日志，主要包括了浏览者的浏览器信息，IP，文本发送长度，URL信息之类的，这么多页面浏览，每天产生的日志体积会超过1T，为了简单起见，一个月算30T吧

现在有一个需求：请在30天数据中找出访问次数最多10000个IP

这么多数据你怎么处理？如果你写一个程序去解析日志，然后存到数据库，做分组统计？几百亿条记录哦

那么就MAP REDUCE吧
具体怎么做，就解释了，你就思考上面的需求，如果你用你自己方法能有效解决也可以，上面是30天的数据，如果把时间放大到300天（300T数据,几千亿条记录）呢?

[Livid]

MapReduce 是一种在很多语言里都存在的编程方式，比如 Python 里就有。

http://docs.python.org/library/functions.html

http://mikecvet.wordpress.com/2010/07/02/parallel-mapreduce-in-python/

而 Google 的 MapReduce 是这种编程方式在大规模服务器群集上的一个实现。

开源的 MapReduce 实现有由 Yahoo 赞助的 Hadoop：

http://hadoop.apache.org/

你可以自己下载并安装 Hadoop 然后按照教程实践几个例子就明白了，比如在巨大的文章库里统计每个单词的出现频率，就是非常典型的 MapReduce 应用。

[virushuo]

简单的说如果有一个任务可以拆开成很多部分，分别执行，并且可以分别组合起来，最终合并成最终的结果，那么就适合map reduce。

当然实际处理起来有些是io密集有些是计算密集有些是两者都有，那么处理的方法就会有一些不同。

如果制造一个应对于这一类问题的通用编程模型，那么就是你所问的map reduce。

而实际上map reduce这个概念是从FP来的，这个不展开说了。你问的使用场景应该是上面描述的这种状况。

[reus]

map和reduce都是对集合的操作。
map是将一个集合映射成另一个集合，两个集合的元素数目相等。
reduce是依次将集合里的元素送入一个处理过程，得到一个值。
比如一个数列，1 2 3 4 5，每个元素都乘以二，得到 2 4 6 8 10，这是map操作
再比如一个集合，apple facebook v2ex，取每个元素的创始人，就得到 jobs z_ livid这个新的集合，这是map操作
reduce也是对集合的操作，它有一个初始的状态，和一个处理函数，这个函数的参数是当前的状态和输入的元素，返回的是下一个状态。集合里的每一个元素都会依次输入这个函数，最后得到的状态就是reduce操作的结果。
比如用reduce操作来计算1 2 3 4 5的和
第零步，初始状态是0，因为什么都没加
第一步，输入的是1，当前状态是0，因为是求和，所以把这两个数相加，得到1，这个结果作为新的状态
第二步，输入的是2，当前状态是1，相加得到新状态3
第三步，输入的是3，当前状态是3，相加得到新状态6
第四步，输入的是4，当前状态是6，相加得到新状态10
最后一步，输入的是5，当前状态是10，相加得到15
这个15就是最终的状态了，也就是这个集合的和，也就是这个reduce操作的结果
如果不是要计算和，而是要计算积，只需要把上面的步骤里的相加改为相乘，把初始状态改成1
所以一个集合的reduce操作，就是使用不同的初始状态和处理函数（相加，相乘或者其他更复杂的操作），来得到想要的结果，和或者积或者其他统计结果
map操作是可以并行进行，因为每个元素的映射结果只和它自己有关，所以大规模的map操作可以用集群并发处理。reduce就不行，因为每次输入元素都可能导致状态产生变化，最后的状态和元素输入的顺序有关，所以不是所有的reduce操作都能并行（加法和乘法可以，统计也可以，因为顺序无关）
综上，map和reduce小程序可以用，大系统也可以用

[est]

在大量元素中，map是自我变形，reduce是幂等关联运算。这两者是正交的可以构成任何运算。

[magicshui]

@est @reus @virushuo @virushuo @Livid @muxi @clowwindy 嘿嘿，谢谢各位的指导，大概懂得了，自己平时还真的没有用到过这些，明天动手操作实践一下

[Platinum]

http://www.aqee.net/can-your-programming-language-do-this/

[bhuztez]

@muxi 这个例子举得很不好耶。数据库是一种软件，MapReduce只是一种运算。RDBMS在查询的时候也会用到MapReduce运算的。

[lychee]

对MapReduce基本上完全没了解，不过根据楼上各位的解释，举一个自己认为算是MapReduce的简单易懂的例子：

某学校进行了一次期末考。以数学考试为例，共收到考卷1000份，有数学老师10人。

Map：因为每份考卷是独立的，所以所得分数也是独立的，那么我们可以让每个老师批阅100份，10个老师同时批阅（并行处理），加快处理速度。

Reduce：上一项操作得到了成绩表，然后例如我们要得出某班级的平均分，可以按 @reus 所说的：

比如用reduce操作来计算1 2 3 4 5的和
第零步，初始状态是0，因为什么都没加
第一步，输入的是1，当前状态是0，因为是求和，所以把这两个数相加，得到1，这个结果作为新的状态
第二步，输入的是2，当前状态是1，相加得到新状态3
第三步，输入的是3，当前状态是3，相加得到新状态6
第四步，输入的是4，当前状态是6，相加得到新状态10
最后一步，输入的是5，当前状态是10，相加得到15
这个15就是最终的状态了，也就是这个集合的和，也就是这个reduce操作的结果


得出总分，再除以人数就得到了平均分。

[ggshiney]

@lychee 这个算某班平均分的例子：

教务主任决定让学校的两个楼层负责这个任务：一楼（Map）负责批阅卷子的分数；二楼（Reduce）负责算各班平均分。

（Map阶段）
一大堆试卷送到学校的一楼，一楼每个教室里一个老师批阅卷子，老师每批阅完一份试卷后就把这份试卷的班号、分数分别写到一个小卡片的正面和反面上（班号:Key / 分数:Value）。把这个小卡片放到教室的门口。

这样对于一楼来说，进来一大堆试卷，出来一大堆写有成绩的小卡片。一楼的老师很高兴，由于免去了计算平均分的工作，今天可以提早下班回家了。

（Reduce阶段）
这些小卡片被送到二楼，按照小卡面正面的班号（Key）送到二楼的对应的教室里。这样每个教室里收到的有成绩的小卡片就都只属于这一个班（Key）。二楼每个教室里的老师就把这些卡片收集好以后计算总分、平均分。老师把这个平均分写到一个小卡片上放到门口。

对于二楼的每个教室里的老师，其工作量由于只面向于一个班级，因此工作量得以大大减轻，纷纷欢呼雀跃。

最后教务主任直接到二楼，每个教室门口收一张写有平均分的小纸条。教务主任表示对此工作很满意。

[magicshui]

@virushuo
有个想法，用自己的语言表达了，嘿嘿：
任务分拆以后，map操作多线程独立操作，而reduce是单线程，那reduce的最早开工时间取决于map中的最晚完工的那个线程？如果有一个线程阻塞了，那reduce是不是一直要等待？

[virushuo]

@magicshui reduce一般不会设计成单线程的。map/reduce本身思想并没什么复杂的，如何正确设计模型才是难点。