前言

? ? ? ?本文總結(jié)了幾種網(wǎng)上或者論文中常見的MapReduce模式和算法，并系統(tǒng)化的解釋了這些技術(shù)的不同之處。所有描述性的文字和代碼都使用了標(biāo)準(zhǔn)hadoop的MapReduce模型，包括Mappers， Reduces， Combiners， Partitioners，和 sorting。詳細(xì)分析如下所示。

基本MapReduce模式

計(jì)數(shù)與求和

問(wèn)題陳述： 有許多文檔，每個(gè)文檔都有一些字段組成。需要計(jì)算出每個(gè)字段在所有文檔中的出現(xiàn)次數(shù)或者這些字段的其他什么統(tǒng)計(jì)值。例如，給定一個(gè)log文件，其中的每條記錄都包含一個(gè)響應(yīng)時(shí)間，需要計(jì)算出平均響應(yīng)時(shí)間。

解決方案：

讓我們先從簡(jiǎn)單的例子入手。在下面的代碼片段里，Mapper每遇到指定詞就把頻次記1，Reducer一個(gè)個(gè)遍歷這些詞的集合然后把他們的頻次加和。

?

這種方法的缺點(diǎn)顯而易見，Mapper提交了太多無(wú)意義的計(jì)數(shù)。它完全可以通過(guò)先對(duì)每個(gè)文檔中的詞進(jìn)行計(jì)數(shù)從而減少傳遞給Reducer的數(shù)據(jù)量：

?

如果要累計(jì)計(jì)數(shù)的的不只是單個(gè)文檔中的內(nèi)容，還包括了一個(gè)Mapper節(jié)點(diǎn)處理的所有文檔，那就要用到Combiner了：

?

應(yīng)用：

Log 分析， 數(shù)據(jù)查詢

整理歸類

問(wèn)題陳述：

有一系列條目，每個(gè)條目都有幾個(gè)屬性，要把具有同一屬性值的條目都保存在一個(gè)文件里，或者把條目按照屬性值分組。 最典型的應(yīng)用是倒排索引。

解決方案：

解決方案很簡(jiǎn)單。 在 Mapper 中以每個(gè)條目的所需屬性值作為 key，其本身作為值傳遞給 Reducer。 Reducer 取得按照屬性值分組的條目，然后可以處理或者保存。如果是在構(gòu)建倒排索引，那么 每個(gè)條目相當(dāng)于一個(gè)詞而屬性值就是詞所在的文檔ID。

應(yīng)用：

倒排索引， ETL

過(guò)濾 （文本查找），解析和校驗(yàn)

問(wèn)題陳述：

假設(shè)有很多條記錄，需要從其中找出滿足某個(gè)條件的所有記錄，或者將每條記錄傳換成另外一種形式（轉(zhuǎn)換操作相對(duì)于各條記錄獨(dú)立，即對(duì)一條記錄的操作與其他記錄無(wú)關(guān)）。像文本解析、特定值抽取、格式轉(zhuǎn)換等都屬于后一種用例。

解決方案：

非常簡(jiǎn)單，在Mapper 里逐條進(jìn)行操作，輸出需要的值或轉(zhuǎn)換后的形式。

應(yīng)用：

日志分析，數(shù)據(jù)查詢，ETL，數(shù)據(jù)校驗(yàn)

分布式任務(wù)執(zhí)行

問(wèn)題陳述：

大型計(jì)算可以分解為多個(gè)部分分別進(jìn)行然后合并各個(gè)計(jì)算的結(jié)果以獲得最終結(jié)果。

解決方案： 將數(shù)據(jù)切分成多份作為每個(gè) Mapper 的輸入，每個(gè)Mapper處理一份數(shù)據(jù)，執(zhí)行同樣的運(yùn)算，產(chǎn)生結(jié)果，Reducer把多個(gè)Mapper的結(jié)果組合成一個(gè)。

案例研究： 數(shù)字通信系統(tǒng)模擬

像 WiMAX 這樣的數(shù)字通信模擬軟件通過(guò)系統(tǒng)模型來(lái)傳輸大量的隨機(jī)數(shù)據(jù)，然后計(jì)算傳輸中的錯(cuò)誤幾率。 每個(gè) Mapper 處理樣本 1/N 的數(shù)據(jù)，計(jì)算出這部分?jǐn)?shù)據(jù)的錯(cuò)誤率，然后在 Reducer 里計(jì)算平均錯(cuò)誤率。

應(yīng)用：

工程模擬，數(shù)字分析，性能測(cè)試

排序

問(wèn)題陳述：

有許多條記錄，需要按照某種規(guī)則將所有記錄排序或是按照順序來(lái)處理記錄。

解決方案： 簡(jiǎn)單排序很好辦 – Mappers 將待排序的屬性值為鍵，整條記錄為值輸出。 不過(guò)實(shí)際應(yīng)用中的排序要更加巧妙一點(diǎn)， 這就是它之所以被稱為MapReduce 核心的原因（“核心”是說(shuō)排序？因?yàn)樽C明Hadoop計(jì)算能力的實(shí)驗(yàn)是大數(shù)據(jù)排序？還是說(shuō)Hadoop的處理過(guò)程中對(duì)key排序的環(huán)節(jié)？）。在實(shí)踐中，常用組合鍵來(lái)實(shí)現(xiàn)二次排序和分組。

MapReduce 最初只能夠?qū)︽I排序， 但是也有技術(shù)利用可以利用Hadoop 的特性來(lái)實(shí)現(xiàn)按值排序。想了解的話可以看 這篇博客。

按照BigTable的概念，使用 MapReduce來(lái)對(duì)最初數(shù)據(jù)而非中間數(shù)據(jù)排序，也即保持?jǐn)?shù)據(jù)的有序狀態(tài)更有好處，必須注意這一點(diǎn)。換句話說(shuō)，在數(shù)據(jù)插入時(shí)排序一次要比在每次查詢數(shù)數(shù)據(jù)的時(shí)候排序更高效。

應(yīng)用：

ETL，數(shù)據(jù)分析