学到老Never too old to learn分享 http://blog.sciencenet.cn/u/tangchangjie

博文

Map-Reduce的直观解释--生活中的大数据技术 精选

已有 36676 次阅读 2015-8-4 08:53 |个人分类:科普札记|系统分类:科普集锦| 大数据, 阅卷, 登机牌, map-reduce, 映射归约

    原名:大数据技术就在生活中: 登机牌、阅卷与 Map-Reduce(唐常杰)

  映射-归约(Map-Reduce)是谷歌多年前推出的建立海量数据索引的方法,有人说它是里程碑性的技术。而理解“映射-约”,又是理解更时髦的Hadoop和Spark等大数据技术的基础。一位作管理的朋友说,虽看过一些大数据相关文章,但对“映射-约”的体验很不踏实,最先在网上,也曾在云里, 而今却在雾中;鼓励我写一篇科普文章,以便能让非计算机专业朋友了解梗概。

  其实,在谷歌之前,人们就不知不觉地用了映射-约技术,如机场分发登机牌,银行取号排队,流水作业阅卷,不过,要说清楚“映射向何方,约在何处”,还有一点挑战,Let me try。

  1 搜索引擎有多快  

   本文将三次用到飞机航班相关的实例,在百度(或谷歌)查询栏中输入”CA1209”,不到一秒钟,百度给出200个结果,分成20多页呈现,其中前几页是比较靠谱的,为后面叙述方便,不妨把这200个结果页面记为p1,p2,…,p200。

  image.png



  2 为什么快?养兵千日的倒排索引  

   搜索网站服务器中有这样一个索引,类似于规范的科技书籍之书末索引,其特点是一关键字对多个标号(或页码),又称为倒排表,其中航班“CA1209”这一项关键字,对应了百度列出的200条信息p1,p2,…,p200.

   百度在回答查询时,一秒钟送出这些现成的p1,p2,…..,p200。不过是小菜一碟的用兵一时。

  而这个倒排索引是由若干万台电脑(或CPU)以365×24方式,夜以继日做出来的结果,真是养兵千日。

关键字
包含关键字的页面队列
……

航班CA1209
P1,p2,…..,p200
…….
…….


  

  3 大数据环境下,倒排索引有多难 

   设某搜索引擎每天新增1亿篇网文,考虑到网文中有些太平凡的字词(停用词,Stop Word)不适合做关键字,如 “的”、“地”、“得”、“不但”、“而且”,等等,每个网页平均有效关键字按100估算,要做完一天新增网页的倒排表,用笨方法,需要读扫描1亿网页,写处理100亿词汇,然后记录下所有如下的对子:

                  <关键字,所在页面>

再加以整理,去重、合并、压缩,这需要用多少个CPU小时!需要多大的空间!

  谷歌在创业之初,提出了一个从海量文档中做倒排索引的聪明方法--Map-Reduce(映射-约),正是它,协调若干万台电脑,并行计算,完成了倒排表的构建与维护,使谷歌在求多求快的竞争中立于不败之地。

   下面用机场办理登机牌的例子来说明。    

 4 机场登机牌分发中的映射-

  乘客在首都机场办理登机手续时,会经过三次映射(三次映射的复合还是映射)和一次约。

  4.1 第一次映射,分而治之,进入首都机场候机大厅,乘客会看到如下的液晶屏:  

  这屏信息,提示乘客按航班分流,例如航班CA1209是在K0---K14号的15个值机台办理登机牌;分而治之,缩小了数据规模,这是古代政治家治理国家的经典策略,也是如今处理大数据朴素方法。

image.png

  

  4.2 第二次映射,把乘客分到值机台

     下图展示了首都机场K0--K14值机台办理登机牌的情况。为保护隐私,故意把图片做了模糊化处理。

image.png


  右边是乘客队列(相当于第3段例子中的每天新增的1亿个网页)。在中间,一位机场人员把乘客分成组(例如15人一组),一次进入一组,分到15个值机柜台,引导加上乘客趋短避长的心态,保证了各个小队列长度大致平衡。

    4.3 第三次映射,把乘客映射到《航班,座号》

  柜台处理包括验看证件,发放登机牌,把乘客分到了航班上,并给托运行李挂上航班标签。

  设在多个值机台的并行工作下,证件号为 1,3,5的乘客,分到了航班 CA1209,而证件号为 2,4,6的乘客,分到了航班 3U8882,于是,得到了下列《乘客,航班号,座号》三元组:

                   《1,CA1209,1排A》,  《3,CA1209,2排B》, 《3,CA1209,3排C》,

                   《2,3U8882,5排A》, 《4,3U8882,7排B》,  《6,3U8882,2排C》,

      至此,并行地完成了这6位乘客的第三次映射 。

    4.4  归约成为倒排表

         把上述映射的结果按航班合并、约简,成为便于使用的如下形式,即倒排表

关键字
乘客证件号及其座号 队列
……
……
航班CA1209
1(1排A),3(2排B),5(3排C)……
航班3U8882
2(5排A),4(7排B),6(2排C)……
……
……

  这一步骤,把同一航班的乘客归到一起,例如,1,3,5出现在倒排表中CA1208这一行右边,对乘客而言,是归类,对信息而言,是约简, 把这一动作称为归约(reduce),是再合适不过了。

      登机牌在该航班起飞前半小时将停办,对应倒排表停止变化,把乘客按某指标(通常关注重要程度)排序,被分发到该航班和机场、保险公司等相关部门。

     此外,用多个 单关键字的倒排索引作交集,可以得到多关键字的倒排索引。


  4.5 倒排表帮助改善服务  上述倒排索引能帮助机组人员知道登机人数与座位,改善服务,例如能叫出头等舱客户和金卡客户的姓名、且服务到座位,就显得格外温馨和谐。

  如有突发事件发生,作为“处突”依据,例如,马航官方能在突发事件后很快查出MH370的乘客信息。

  综上所述,办理登机牌的全过程可以表达为下列经典的Map-Reduce图,这个图大致反映了并行地映射-归约的流向,但未表达4.3节描述的归约细节,用于科普,勉强够了。

image.png


     从乘客组映射到值机台再映射到《航班,座号》,          《乘客,航班,座号》约到(航班 ,乘客1,乘客2,...)

  

     现在的互联网搜索引擎,倒排表中机理大致如上,但数量增大若干个数量级,相当于在上图中的乘客组有几千万,  值机台(CPU)有100万, 而航班(倒排索引项)是几万-几十万。

     需要说明,这只是为了说明‘映射-归约”机制而编的例子,真实的机场工作机制要复杂得多。


  5  安检时的映射-

  在首都机场,可以看到,在安检时,还有一次Map-Reduce过程, 源源不断的乘客乘坐扶梯下到安检大厅,

  Map: 一位安检人员指引乘客,分流到个安检口;

 Reduce:安检后,分成若干类:大部分归约为PASS 类,部分乘客有不合适行李,要做处理,自弃,留存,安检人员会对应机票,身份证作相应记录,….  

  6 流水作业方式阅卷中的映射

  真实的高考涉及若干政策问题,比较复杂;只有一个评阅人的阅卷有没有并行,不适合做映射-归约的用例。下面考虑一个学院中某一课程的期末考试试卷处理,为公平和高效,阅卷普遍采用流水作业方式,一位阅卷人评阅一组题,然后总计分数;要求给出如下的分数段倒排表:  

分数段
学号队列
90-100
S1,S2,...
80-89
 ...
70-79 ...
60-69
 ...
50-59 ...
0-49 ...


 映射阶段:把答卷片组分给承担任务的阅卷人,(就像把乘客组分到值机台)

  约预处理阶段:阅卷人阅承担的片段,汇总片段所得总分;(就像值机台把乘客分到航班,并发登机牌)

  约后处理阶段:与登机牌处理的不同点,约算法中适当地方,增加一道汇总试卷总分,并且约到分数段。写入倒排表。

  这个例子仅仅是为了说明,在人们熟悉的流水阅卷过程中,包含了Map-Reduce的深刻机理; 在这个意义上可以说,大数据技术也是源于生活,服务于生活的。


  7 小样启发思考,映射-约技术要点

  上面的例子在思路上还真是Map-Reduce(不仅仅是比喻),虽然还只是“小样”,但事不同而理同。能启发我们的思考。

  大数据中的映射-约有下列要点

  1. 目标:完成某一类计算,典型实例之一是生成某个关键字上的倒排索引;

  2. 对象:PB级的数据,例如来自云、来自分布式文件系统的文档。

  3. 并行处理,多个(几百—几十万个,甚至更多)处理单元(电脑,CPU,人员);

  4  有序:在机场,车站,当客户增加,仅仅增加服务台来做约(Reduce),常常不够有序,增加一个映射(Map)机制,把被处理对象分配到处理单元,是不可少的环节。春运中人们更体会到这一条。

  5 多层映射,多层约 ;在首都机场我们看到了映射有三层,第一次映射到值机台分区,分而治之;第二次次到值机台,第三次映射到《乘客,航班号,座号》三元组;根据实际情况,约也可以是多层次的。

  这里也要强调,小样和真实还有差距,量变超过了一定阈值,会引发质变,这一点在实践中必须注意。

  还有两个例子,根据经验,做为练习题效果更好,

习题1  大型会议接送VIP客人

        型会议中VIP客人(特邀报告人, 著名学者等)较多。接送小组把航班火车信息收集工作落实到人,一人包几位VIP,然后把接送任务分发给接送车辆司机,请画出映射-归约图。

    提示:对比登记牌例子,接送小组相当于中的值机台,而接送车辆相当于航班

习题2  大型会议报告分会安排
   大型会议有众多论文,按内容分类,需要在不同时间地点的不同分会报告,请画出映射-归约图。
提示    提示:对比登记牌例子,内容类别相当于值机台,分会相当于航班。


相关博文

 大数据 与 马航MH370-大数据杂谈之一

 看大牛们说大数据 –- 《海量数据分析前沿》读后感

  鸡叫与天亮:大数据中的关联与因果—大数据杂谈之二

 其他相关博文:

 网上流行云计算 --云计算漫谈之一
 天边飘来几朵计算的云 ---云计算漫谈之二

 假日聚会,戏说云物人海  

    其它系列博文的入口     唐常杰博客主页        学博客主页   



https://blog.sciencenet.cn/blog-287179-910302.html

上一篇:看大牛们说大数据 –- 《海量数据分析前沿》读后感
下一篇:数据科学家有一个梦
收藏 IP: 218.88.4.*| 热度|

39 曹聪 聂荣智 左嘉陵 许培扬 魏焱明 马萧萧 曹元兰 李盛庆 元云芬 王达伟 李健 杨正瓴 武夷山 刘立 彭真明 刘洋 庄世宇 张能立 金耀初 韩涛 周忠浩 易奎 陆泽橼 赵美娣 赵凤光 毛宁 赵继慧 赵君渝 王娜娜 张博 icgwang luxiaobing12 yzqts xchen nm zjzhaokeqin ncepuztf xqhuang zzseng

该博文允许注册用户评论 请点击登录 评论 (53 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-10-15 05:00

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部