ca1209(大数据中的映射-归约)

映射-归约（Map-Reduce）是一种海量数据索引的方法，也有人说它是里程碑性的技术。在日常生活中人们不知不觉地就用了映射-归约技术，如机场分登机，银行取号，高考作业阅卷。假设某搜索引擎每天新增5000万篇网文，考虑到网文中有些太平凡的字词（不适合做关键字，如 “的”、“地”、“得”、“不但”、“而且”，等等，每个网页平均有效关键字按200估算，要做完一天新增网页的倒排表，用笨方法，需要读扫描1亿网页，写处理200亿词汇，然后记录下所有如下的对子：

<关键字，页面>

然后整理，去重、合并、压缩，这需要用多少个CPU小时！需要多大的空间！谷歌提出了一个从海量文档中做倒排索引的聪明方法–Map-Reduce（映射-归约），协调若干万台电脑，并行计算，完成了倒排表的构建与维护。

我们就用机场办理登机牌的例子来说明。

1、机场登机牌分发中的映射-归约

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

1.1、第一次映射，分而治之

进入首都机场候机大厅，乘客会看到如下的液晶屏。这屏信息，提示乘客按航班分流，例如航班CA1209是在K0—K14号的15个值机台办理登机牌；分而治之，缩小了数据规模，这是如今处理大数据朴素方法。

1.2、 第二次映射，把乘客分到值机台

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

1.3、第三次映射，把乘客映射到《航班，座号》

柜台处理包括验看证件，发放登机牌，把乘客分到了航班上，并给托运行李挂上航班标签。设在多个值机台的并行工作下，证件号为 1，3，5的乘客，分到了航班 CA1209，而证件号为 2，4，6的乘客，分到了航班 3U8882，于是，得到了下列《乘客，航班号，座号》三元组。并行地完成了这6位乘客的第三次映射 。

1.4、归约成为倒排表

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

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

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

1.5、倒排表帮助改善服务

上述倒排索引能帮助机组人员知道登机人数与座位，改善服务，例如能叫出头等舱客户和金卡客户的姓名、且服务到座位，就显得格外温馨和谐。办理登机牌的全过程可以表达为下列经典的Map-Reduce图，这个图大致反映了并行地映射-归约的流向。

现在的互联网搜索引擎，倒排表中机理大致如上，但数量增大若干个数量级，相当于在上图中的乘客组有几千万， 值机台（CPU）有100万， 而航班（倒排索引项）是几万-几十万。需要说明，这只是为了说明‘映射-归约”机制而编的例子，真实的机场工作机制要复杂得多。

2、安检时的映射-归约

Map： 一位安检人员指引乘客，分流到个安检口；

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

3、高考阅卷中的映射归约

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

映射阶段：把答卷片组分给承担任务的阅卷人，（就像把乘客组分到值机台）

归约预处理阶段：阅卷人阅承担的片段，汇总片段所得总分；（就像值机台把乘客分到航班，并发登机牌）

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

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

4、总结映射-归约技术要点

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

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

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

3. 并行处理：多个（几百—几十万个，甚至更多）处理单元（电脑，CPU，人员）；

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

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

理论和真实还有差距，量变超过了一定阈值，会引发质变。