|||
原名:大数据技术就在生活中: 登机牌、阅卷与 Map-Reduce(唐常杰)
映射-归约(Map-Reduce)是谷歌多年前推出的建立海量数据索引的方法,有人说它是里程碑性的技术。而理解“映射-归约”,又是理解更时髦的Hadoop和Spark等大数据技术的基础。一位作管理的朋友说,虽看过一些大数据相关文章,但对“映射-归约”的体验很不踏实,最先在网上,也曾在云里, 而今却在雾中;鼓励我写一篇科普文章,以便能让非计算机专业朋友了解梗概。
其实,在谷歌之前,人们就不知不觉地用了映射-归约技术,如机场分发登机牌,银行取号排队,流水作业阅卷,不过,要说清楚“映射向何方,归约在何处”,还有一点挑战,Let me try。
1 搜索引擎有多快
本文将三次用到飞机航班相关的实例,在百度(或谷歌)查询栏中输入”CA1209”,不到一秒钟,百度给出200个结果,分成20多页呈现,其中前几页是比较靠谱的,为后面叙述方便,不妨把这200个结果页面记为p1,p2,…,p200。
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个值机台办理登机牌;分而治之,缩小了数据规模,这是古代政治家治理国家的经典策略,也是如今处理大数据朴素方法。
4.2 第二次映射,把乘客分到值机台
下图展示了首都机场K0--K14值机台办理登机牌的情况。为保护隐私,故意把图片做了模糊化处理。
右边是乘客队列(相当于第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节描述的归约细节,用于科普,勉强够了。
从乘客组映射到值机台再映射到《航班,座号》, 从《乘客,航班,座号》归约到(航班 ,乘客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-大数据杂谈之一
其他相关博文:
网上流行云计算 --云计算漫谈之一
天边飘来几朵计算的云 ---云计算漫谈之二
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-10-15 05:00
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社