V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
magicshui
V2EX  ›  程序员

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

  •  
  •   magicshui · 2012-01-17 22:48:42 +08:00 · 5468 次点击
    这是一个创建于 4705 天前的主题,其中的信息可能已经有所发展或是发生改变。
    一直听到这个名词,也搜索了相关文章,但是还是不明白mapreduce具体的应用场景,请懂的童鞋指点一下,最好能够有一个生动活泼的例子,恩恩,谢谢
    13 条回复    1970-01-01 08:00:00 +08:00
    clowwindy
        1
    clowwindy  
       2012-01-17 23:24:48 +08:00
    比方说现在存了一亿个网页,key是URL,value是网页内容。
    map(映射)的时候把网页内容拆成词,按照key是词,value是URL和其它meta信息的方式输出。
    在reduce(化简)函数中可以得到一个key(词)对应的所有value(URL,meta)。再做进一步处理,比方说根据词频排个序,然后输出。
    这样就得到了词->URL的对应关系。
    muxi
        2
    muxi  
       2012-01-17 23:35:22 +08:00   ❤️ 1
    例子很多的,举个简单的例子

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

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

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

    那么就MAP REDUCE吧
    具体怎么做,就解释了,你就思考上面的需求,如果你用你自己方法能有效解决也可以,上面是30天的数据,如果把时间放大到300天(300T数据,几千亿条记录)呢?
    Livid
        3
    Livid  
    MOD
       2012-01-17 23:44:10 +08:00
    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
        4
    virushuo  
       2012-01-17 23:47:29 +08:00
    简单的说如果有一个任务可以拆开成很多部分,分别执行,并且可以分别组合起来,最终合并成最终的结果,那么就适合map reduce。

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

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

    而实际上map reduce这个概念是从FP来的,这个不展开说了。你问的使用场景应该是上面描述的这种状况。
    reus
        5
    reus  
       2012-01-18 04:18:51 +08:00 via Android
    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
        6
    est  
       2012-01-18 08:01:25 +08:00
    在大量元素中,map是自我变形,reduce是幂等关联运算。这两者是正交的可以构成任何运算。
    magicshui
        7
    magicshui  
    OP
       2012-01-20 01:16:24 +08:00
    @est @reus @virushuo @virushuo @Livid @muxi @clowwindy 嘿嘿,谢谢各位的指导,大概懂得了,自己平时还真的没有用到过这些,明天动手操作实践一下
    Platinum
        8
    Platinum  
       2012-01-20 18:00:04 +08:00
    bhuztez
        9
    bhuztez  
       2012-01-20 19:05:49 +08:00
    @muxi 这个例子举得很不好耶。数据库是一种软件,MapReduce只是一种运算。RDBMS在查询的时候也会用到MapReduce运算的。
    lychee
        10
    lychee  
       2012-01-26 21:29:11 +08:00
    对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
        11
    ggshiney  
       2012-01-26 22:48:27 +08:00
    @lychee 这个算某班平均分的例子:

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

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

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

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

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

    最后教务主任直接到二楼,每个教室门口收一张写有平均分的小纸条。教务主任表示对此工作很满意。
    magicshui
        12
    magicshui  
    OP
       2012-01-27 00:03:33 +08:00
    @virushuo
    有个想法,用自己的语言表达了,嘿嘿:
    任务分拆以后,map操作多线程独立操作,而reduce是单线程,那reduce的最早开工时间取决于map中的最晚完工的那个线程?如果有一个线程阻塞了,那reduce是不是一直要等待?
    virushuo
        13
    virushuo  
       2012-01-27 01:03:02 +08:00
    @magicshui reduce一般不会设计成单线程的。map/reduce本身思想并没什么复杂的,如何正确设计模型才是难点。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3666 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 04:19 · PVG 12:19 · LAX 20:19 · JFK 23:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.