詳解MapReduce的模式、算法和用例

前言

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

基本MapReduce模式

計數(shù)與求和

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

解決方案：

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

?

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

?

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

?

應(yīng)用：

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

整理歸類

問題陳述：

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

解決方案：

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

應(yīng)用：

倒排索引， ETL

過濾 （文本查找），解析和校驗

問題陳述：

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

解決方案：

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

應(yīng)用：

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

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

問題陳述：

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

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

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

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

應(yīng)用：

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

排序

問題陳述：

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

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

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

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

應(yīng)用：

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