映射-歸約（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 多層映射，多層歸約：在首都機場我們看到了映射有三層，第一次映射到值機臺分區，分而治之；第二次次到值機臺，第三次映射到《乘客，航班號，座號》三元組；根據實際情況，歸約也可以是多層次的。
理論和真實還有差距，量變超過了一定閾值，會引發質變。
閱讀更多 石頭大V 的文章
