大数据技术就在生活中: 登机牌、阅卷与 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方式,夜以继日做出来的结果,真是养兵千日。

大数据

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个值机柜台,引导加上乘客趋短避长的心态,保证了各个小队列长度大致平衡。