文|唐常杰（四川大學(xué)，計(jì)算機(jī)學(xué)院，教授）
映射-歸約（Map-Reduce）是谷歌多年前推出的建立海量數(shù)據(jù)索引的方法，有人說(shuō)它是里程碑性的技術(shù)。而理解“映射-歸約”，又是理解更時(shí)髦的Hadoop和Spark等大數(shù)據(jù)技術(shù)的基礎(chǔ)。一位作管理的朋友說(shuō)，雖看過(guò)一些大數(shù)據(jù)相關(guān)文章，但對(duì)“映射-歸約”的體驗(yàn)很不踏實(shí)，最先在網(wǎng)上，也曾在云里, 而今卻在霧中；鼓勵(lì)我寫(xiě)一篇科普文章，以便能讓非計(jì)算機(jī)專業(yè)朋友了解梗概。
其實(shí)，在谷歌之前，人們就不知不覺(jué)地用了映射-歸約技術(shù)，如機(jī)場(chǎng)分發(fā)登機(jī)牌，銀行取號(hào)排隊(duì)，流水作業(yè)閱卷，不過(guò)，要說(shuō)清楚“映射向何方，歸約在何處”，還有一點(diǎn)挑戰(zhàn)，Let me try。
1、搜索引擎有多快
本文將三次用到飛機(jī)航班相關(guān)的實(shí)例，在百度（或谷歌）查詢欄中輸入”CA1209”，不到一秒鐘，百度給出200個(gè)結(jié)果，分成20多頁(yè)呈現(xiàn),其中前幾頁(yè)是比較靠譜的，為后面敘述方便，不妨把這200個(gè)結(jié)果頁(yè)面記為p1,p2,…,p200。
2 為什么快？養(yǎng)兵千日的倒排索引
搜索網(wǎng)站服務(wù)器中有這樣一個(gè)索引，類似于規(guī)范的科技書(shū)籍之書(shū)末索引，其特點(diǎn)是一關(guān)鍵字對(duì)多個(gè)標(biāo)號(hào)（或頁(yè)碼），又稱為倒排表,其中航班“CA1209”這一項(xiàng)關(guān)鍵字，對(duì)應(yīng)了百度列出的200條信息p1,p2,…,p200.
百度在回答查詢時(shí)，一秒鐘送出這些現(xiàn)成的p1,p2,…..,p200。不過(guò)是小菜一碟的用兵一時(shí)。
而這個(gè)倒排索引是由若干萬(wàn)臺(tái)電腦（或CPU）以365×24方式,夜以繼日做出來(lái)的結(jié)果，真是養(yǎng)兵千日。
3、大數(shù)據(jù)環(huán)境下，倒排索引有多難
設(shè)某搜索引擎每天新增1億篇網(wǎng)文，考慮到網(wǎng)文中有些太平凡的字詞（停用詞，Stop Word）不適合做關(guān)鍵字，如 “的”、“地”、“得”、“不但”、“而且”，等等，每個(gè)網(wǎng)頁(yè)平均有效關(guān)鍵字按100估算，要做完一天新增網(wǎng)頁(yè)的倒排表，用笨方法，需要讀掃描1億網(wǎng)頁(yè)，寫(xiě)處理100億詞匯，然后記錄下所有如下的對(duì)子：
<關(guān)鍵字，所在頁(yè)面>
再加以整理，去重、合并、壓縮，這需要用多少個(gè)CPU小時(shí)！需要多大的空間！
谷歌在創(chuàng)業(yè)之初，提出了一個(gè)從海量文檔中做倒排索引的聰明方法–Map-Reduce（映射-歸約），正是它，協(xié)調(diào)若干萬(wàn)臺(tái)電腦，并行計(jì)算，完成了倒排表的構(gòu)建與維護(hù)，使谷歌在求多求快的競(jìng)爭(zhēng)中立于不敗之地。
下面用機(jī)場(chǎng)辦理登機(jī)牌的例子來(lái)說(shuō)明。
4 機(jī)場(chǎng)登機(jī)牌分發(fā)中的映射-歸約
乘客在首都機(jī)場(chǎng)辦理登機(jī)手續(xù)時(shí)，會(huì)經(jīng)過(guò)三次映射（三次映射的復(fù)合還是映射）和一次歸約。
4.1 第一次映射，分而治之，進(jìn)入首都機(jī)場(chǎng)候機(jī)大廳，乘客會(huì)看到如下的液晶屏：
這屏信息，提示乘客按航班分流，例如航班CA1209是在K0—K14號(hào)的15個(gè)值機(jī)臺(tái)辦理登機(jī)牌；分而治之，縮小了數(shù)據(jù)規(guī)模，這是古代政治家治理國(guó)家的經(jīng)典策略，也是如今處理大數(shù)據(jù)樸素方法。
4.2 第二次映射，把乘客分到值機(jī)臺(tái)
下圖展示了首都機(jī)場(chǎng)K0–K14值機(jī)臺(tái)辦理登機(jī)牌的情況。為保護(hù)隱私，故意把圖片做了模糊化處理。
右邊是乘客隊(duì)列（相當(dāng)于第3段例子中的每天新增的1億個(gè)網(wǎng)頁(yè)）。在中間，一位機(jī)場(chǎng)人員把乘客分成組（例如15人一組），一次進(jìn)入一組，分到15個(gè)值機(jī)柜臺(tái)，引導(dǎo)加上乘客趨短避長(zhǎng)的心態(tài)，保證了各個(gè)小隊(duì)列長(zhǎng)度大致平衡。