大数据技术就在生活中: 登机牌、阅卷与 Map-Reduce(归约)

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 归约成为倒排表

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

大数据

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

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

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

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

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

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

大数据

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

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

5 安检时的映射-归约,

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

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

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

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

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

大数据

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

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

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

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

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

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

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

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