MapReduce編程模型是什么

這篇文章主要講解了“MapReduce編程模型是什么”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“MapReduce編程模型是什么”吧！

MapReduce：大型集群上的簡單數(shù)據(jù)處理

摘要

MapReduce是一個設(shè)計模型，也是一個處理和產(chǎn)生海量數(shù)據(jù)的一個相關(guān)實現(xiàn)。用戶指定一個用于處理一個鍵值（key-value）對生成一組key/value對形式的中間結(jié)果的map函數(shù)，以及一個將中間結(jié)果鍵相同的鍵值對合并到一起的reduce函數(shù)。許多現(xiàn)實世界的任務都能滿足這個模型，如這篇文章所示。

使用這個功能形式實現(xiàn)的程序能夠在大量的普通機器上并行執(zhí)行。這個運行程序的系統(tǒng)關(guān)心下面的這些細節(jié)：輸入數(shù)據(jù)的分區(qū)、一組機器上調(diào)度程序執(zhí)行、處理機器失敗問題，以及管理所需的機器內(nèi)部的通信。這使沒有任何并行處理和分布式系統(tǒng)經(jīng)驗的程序員能夠利用這個大型分布式系統(tǒng)的資源。

我們的MapReduce實現(xiàn)運行在一個由普通機器組成的大規(guī)模集群上，具有很高的可擴展性：一個典型的MapReduce計算會在幾千臺機器上處理許多TB的數(shù)據(jù)。程序員們發(fā)現(xiàn)這個系統(tǒng)很容易使用：目前已經(jīng)實現(xiàn)了幾百個MapReduce程序，在Google的集群上，每天有超過一千個的MapReduce工作在運行。

一、        介紹

在過去的5年中，本文作者和許多Google的程序員已經(jīng)實現(xiàn)了數(shù)百個特定用途的計算程序，處理了海量的原始數(shù)據(jù)，包括抓取到的文檔、網(wǎng)頁請求日志等，計算各種衍生出來的數(shù)據(jù)，如反向索引、網(wǎng)頁文檔的圖形結(jié)構(gòu)的各種表示、每個host下抓取到的頁面數(shù)量的總計、一個給定日期內(nèi)的最頻繁查詢的集合等。大多數(shù)這種計算概念明確。然而，輸入數(shù)據(jù)通常都很大，并且計算必須分布到數(shù)百或數(shù)千臺機器上以確保在一個合理的時間內(nèi)完成。如何并行計算、分布數(shù)據(jù)、處理錯誤等問題使這個起初很簡單的計算，由于增加了處理這些問題的很多代碼而變得十分復雜。

為了解決這個復雜問題，我們設(shè)計了一個新的抽象模型，它允許我們將想要執(zhí)行的計算簡單的表示出來，而隱藏其中并行計算、容錯、數(shù)據(jù)分布和負載均衡等很麻煩的細節(jié)。我們的抽象概念是受最早出現(xiàn)在lisp和其它結(jié)構(gòu)性語言中的map和reduce啟發(fā)的。我們認識到，大多數(shù)的計算包含對每個在輸入數(shù)據(jù)中的邏輯記錄執(zhí)行一個map操作以獲取一組中間key/value對，然后對含有相同key的所有中間值執(zhí)行一個reduce操作，以此適當?shù)暮喜⒅暗难苌鷶?shù)據(jù)。由用戶指定map和reduce操作的功能模型允許我們能夠簡單的進行并行海量計算，并使用re-execution作為主要的容錯機制。

這項工作的最大貢獻是提供了一個簡單的、強大的接口，使我們能夠自動的進行并行和分布式的大規(guī)模計算，通過在由普通PC組成的大規(guī)模集群上實現(xiàn)高性能的接口來進行合并。

第二章描述了基本的編程模型，并給出了幾個例子。第三章描述了一個為我們的聚類計算環(huán)境定制的MapReduce接口實現(xiàn)。第四章描述了我們發(fā)現(xiàn)對程序模型很有用的幾個優(yōu)化。第六章探索了MapReduce在Google內(nèi)部的使用，包括我們在將它作為生產(chǎn)索引系統(tǒng)重寫的基礎(chǔ)的一些經(jīng)驗。第七章討論了相關(guān)的和未來的工作。

二、        編程模型

這個計算輸入一個key/value對集合，產(chǎn)生一組輸出key/value對。MapReduce庫的用戶通過兩個函數(shù)來標識這個計算：Map和Reduce。

Map，由用戶編寫，接收一個輸入對，產(chǎn)生一組中間key/value對。MapReduce庫將具有相同中間key I的聚合到一起，然后將它們發(fā)送給Reduce函數(shù)。

Reduce，也是由用戶編寫的，接收中間key I和這個key的值的集合，將這些值合并起來，形成一個盡可能小的集合。通常，每個Reduce調(diào)用只產(chǎn)生0或1個輸出值。這些中間值經(jīng)過一個迭代器（iterator）提供給用戶的reduce函數(shù)。這允許我們可以處理由于數(shù)據(jù)量過大而無法載入內(nèi)存的值的鏈表。

2.1 例子

考慮一個海量文件集中的每個單詞出現(xiàn)次數(shù)的問題，用戶會寫出類似于下面的偽碼：

Map函數(shù)對每個單詞增加一個相應的出現(xiàn)次數(shù)（在這個例子中僅僅為“1”）。Reduce函數(shù)將一個指定單詞所有的計數(shù)加到一起。

此外，用戶使用輸入和輸出文件的名字、可選的調(diào)節(jié)參數(shù)編寫代碼，來填充一個mapreduce規(guī)格對象，然后調(diào)用MapReduce函數(shù)，并把這個對象傳給它。用戶的代碼與MapReduce庫（C++實現(xiàn)）連接到一起。。附錄A包含了這個例子的整個程序。

2.2 類型

盡管之前的偽代碼中使用了字符串格式的輸入和輸出，但是在概念上，用戶定義的map和reduce函數(shù)需要相關(guān)聯(lián)的類型：

map       (k1, v1)                      -->         list(k2, v2)

reduce   (k2, list(v2))                -->          list(v2)

也就是說，輸入的鍵和值和輸出的鍵和值來自不同的域。此外，中間結(jié)果的鍵和值與輸出的鍵和值有相同的域。

MapReduce的C++實現(xiàn)與用戶定義的函數(shù)使用字符串類型進行參數(shù)傳遞，將類型轉(zhuǎn)換的工作留給用戶的代碼來處理。

2.3 更多的例子

這里有幾個簡單有趣的程序，能夠使用MapReduce計算簡單的表示出來。

分布式字符串查找（Distributed Grep）：map函數(shù)將匹配一個模式的行找出來。Reduce函數(shù)是一個恒等函數(shù)，只是將中間值拷貝到輸出上。

URL訪問頻率計數(shù)（Count of URL Access Frequency）：map函數(shù)處理web頁面請求的日志，并輸出<URL, 1>。Reduce函數(shù)將相同URL的值累加到一起，生成一個<URL, total count>對。

翻轉(zhuǎn)網(wǎng)頁連接圖（Reverse Web-Link Graph）：map函數(shù)為在一個名為source的頁面中指向目標（target）URL的每個鏈接輸出<target, source>對。Reduce函數(shù)將一個給定目標URL相關(guān)的所有源（source）URLs連接成一個鏈表，并生成對：<target, list(source)>。

主機關(guān)鍵向量指標（Term-Vector per Host）：一個檢索詞向量將出現(xiàn)在一個文檔或是一組文檔中最重要的單詞概述為一個<word, frequency>對鏈表。Map函數(shù)為每個輸入文檔產(chǎn)生一個<hostname, term vector>（hostname來自文檔中的URL）。Reduce函數(shù)接收一個給定hostname的所有文檔檢索詞向量，它將這些向量累加到一起，將罕見的向量丟掉，然后生成一個最終的<hostname, term vector>對。

倒排索引（Inverted Index）：map函數(shù)解析每個文檔，并生成一個<word, document ID>序列。Reduce函數(shù)接收一個給定單詞的所有鍵值對，所有的輸出對形成一個簡單的倒排索引?？梢酝ㄟ^對計算的修改來保持對單詞位置的追蹤。

分布式排序（Distributed Sort）：map函數(shù)將每個記錄的key抽取出來，并生成一個<key, record>對。Reduce函數(shù)不會改變?nèi)魏蔚逆I值對。這個計算依賴了在4.1節(jié)提到的分區(qū)功能和4.2節(jié)提到的排序?qū)傩浴?/p>

三、        實現(xiàn)

MapReduce接口有很多不同的實現(xiàn)，需要根據(jù)環(huán)境來做出合適的選擇。比如，一個實現(xiàn)可能適用于一個小的共享內(nèi)存機器，而另一個實現(xiàn)則適合一個大的NUMA多處理器機器，再另一個可能適合一個更大的網(wǎng)絡(luò)機器集合。

這一章主要描述了針對在Google內(nèi)部廣泛使用的計算環(huán)境的一個實現(xiàn)：通過交換以太網(wǎng)將大量的普通PC連接到一起的集群。在我們的環(huán)境中：

（1）    機器通常是雙核x86處理器、運行Linux操作系統(tǒng)、有2-4G的內(nèi)存。

（2）    使用普通的網(wǎng)絡(luò)硬件—通常是100Mb/s或者是1Gb/s的機器帶寬，但是平均值遠小于帶寬的一半。

（3）    由數(shù)百臺或者數(shù)千臺機器組成的集群，因此機器故障是很平常的事

（4）    存儲是由直接裝在不同機器上的便宜的IDE磁盤提供。一個內(nèi)部的分布式文件系統(tǒng)用來管理存儲這些磁盤上的數(shù)據(jù)。文件系統(tǒng)在不可靠的硬件上使用副本機制提供了可用性和可靠性。

（5）    用戶將工作提交給一個調(diào)度系統(tǒng)，每個工作由一個任務集組成，通過調(diào)度者映射到集群中可用機器的集合上。

3.1 執(zhí)行概述

通過自動的將輸入數(shù)據(jù)分區(qū)成M個分片，Map調(diào)用被分配到多臺機器上運行。數(shù)據(jù)的分片能夠在不同的機器上并行處理。使用分區(qū)函數(shù)（如，hash(key) mod R）將中間結(jié)果的key進行分區(qū)成R個分片，Reduce調(diào)用也被分配到多臺機器上運行。分區(qū)的數(shù)量（R）和分區(qū)函數(shù)是由用戶指定的。

獨立的工作機器的計數(shù)器值周期性的傳送到master（附在ping的響應上）master將從成功的map和reduce任務上獲取的計數(shù)器值進行匯總，當MapReduce操作完成時，將它們返回給用戶的代碼。當前的計數(shù)器值也被顯示在了master的狀態(tài)頁面上，使人們能夠看到當前計算的進度。當匯總計數(shù)器值時，master通過去掉同一個map或reduce任務的多次執(zhí)行所造成的影響來防止重復計數(shù)。（重復執(zhí)行可能會在我們使用備用任務和重新執(zhí)行失敗的任務時出現(xiàn)。）

一些計數(shù)器的值是由MapReduce庫自動維護的，如已處理的輸入key/value對的數(shù)量和已生成的輸出key/value對的數(shù)量。

用戶發(fā)現(xiàn)計數(shù)器對檢查MapReduce操作的行為很有用處。例如，在一些MapReduce操作中，用戶代碼可能想要確保生成的輸出對的數(shù)量是否精確的等于已處理的輸入對的數(shù)量，或者已處理的德國的文檔數(shù)量在已處理的所有文檔數(shù)量中是否被容忍。

五、        性能

在這章中，我們測試兩個運行在一個大規(guī)模集群上的MapReduce計算的性能。一個計算在大約1TB的數(shù)據(jù)中進行特定的模式匹配，另一個計算對大約1TB的數(shù)據(jù)進行排序。

這兩個程序能夠代表實際中大量的由用戶編寫的MapReduce程序，一類程序?qū)?shù)據(jù)從一種表示方式轉(zhuǎn)換成另一種形式；另一類程序是從海里的數(shù)據(jù)集中抽取一小部分感興趣的數(shù)據(jù)。

5.1 集群配置

所有的程序運行在一個由將近1800臺機器組成的集群上。每個機器有兩個2GHz、支持超線程的Intel Xeon處理器、4GB的內(nèi)存、兩個160GB的IDE磁盤和一個1Gbps的以太網(wǎng)鏈路，這些機器部署在一個兩層的樹狀交換網(wǎng)絡(luò)中，在根節(jié)點處有大約100-200Gbps的帶寬。所有的機器都采用相同的部署，因此任意兩個機器間的RTT都小于1ms。

在4GB內(nèi)存里，有接近1-1.5GB用于運行在集群上的其它任務。程序在一個周末的下午開始執(zhí)行，這時主機的CPU、磁盤和網(wǎng)絡(luò)基本都是空閑的。

5.2 字符串查找（Grep）

這個grep程序掃描了大概1010個100字節(jié)大小的記錄，查找出現(xiàn)概率相對較小的3個字符的模式（這個模式出現(xiàn)在92337個記錄中）。輸入被分割成接近64MB的片（M=15000），整個輸出被放到一個文件中（R=1）。

圖3：對于排序程序的不同執(zhí)行過程隨時間的數(shù)據(jù)傳輸速率

圖3（a）顯示了排序程序的正常執(zhí)行過程。左上方的圖顯示了輸入讀取的速率，這個速率峰值大約為13GB/s，因為所有的map任務執(zhí)行完成，速率也在200秒前下降到了0。注意，這里的輸入速率比字符串查找的要小，這是因為排序程序的map任務花費了大約一半的處理時間和I/O帶寬將終結(jié)結(jié)果輸出到它們的本地磁盤上，字符串查找相應的中間結(jié)果輸出幾乎可以忽略。

左邊中間的圖顯示了數(shù)據(jù)通過網(wǎng)絡(luò)從map任務發(fā)往reduce任務的速率。這個緩慢的數(shù)據(jù)移動在第一個map任務完成時會盡快開始。圖中的第一個峰值是啟動了第一批大概1700個reduce任務（整個MapReduce被分配到大約1700臺機器上，每個機器每次最多只執(zhí)行一個reduce任務）。這個計算執(zhí)行大概300秒后，第一批reduce任務中的一些執(zhí)行完成，我們開始執(zhí)行剩下的reduce任務進行數(shù)據(jù)處理。所有的處理在計算開始后的大約600秒后完成。

左邊下方的圖顯示了reduce任務就愛那個排序后的數(shù)據(jù)寫到最終的輸出文件的速率。在第一個處理周期完成到寫入周期開始間有一個延遲，因為機器正在忙于對中間數(shù)據(jù)進行排序。寫入的速率會在2-4GB/s上持續(xù)一段時間。所有的寫操作會在計算開始后的大約850秒后完成。包括啟動的開銷，整個計算耗時891秒，這與TeraSort benchmark中的最好記錄1057秒相似。

一些事情需要注意：因為我們的位置優(yōu)化策略，大多數(shù)數(shù)據(jù)從本地磁盤中讀取，繞開了網(wǎng)絡(luò)帶寬的顯示，所以輸入速率比處理速率和輸出速率要高。處理速率要高于輸出速率，因為輸出過程要將排序后的數(shù)據(jù)寫入到兩個拷貝中（為了可靠性和可用性，我們將數(shù)據(jù)寫入到兩個副本中）。我們將數(shù)據(jù)寫入兩個副本，因為我們的底層文件系統(tǒng)為了可靠性和可用性提供了相應的機制。如果底層文件系統(tǒng)使用容錯編碼（erasure coding）而不是復制，寫數(shù)據(jù)的網(wǎng)絡(luò)帶寬需求會降低。

5.4 備用任務的作用

在圖3（b）中，我們顯示了一個禁用備用任務的排序程序的執(zhí)行過程。執(zhí)行的流程與如3（a）中所顯示的相似，除了有一個很長的尾巴，在這期間幾乎沒有寫入行為發(fā)生。在960秒后，除了5個reduce任務的所有任務都執(zhí)行完成。然而，這些落后者只到300秒后才執(zhí)行完成。整個計算任務耗時1283秒，增加了大約44%的時間。

5.5 機器故障

在圖3（c）中，我們顯示了一個排序程序的執(zhí)行過程，在計算過程開始都的幾分鐘后，我們故意kill掉了1746個工作進程中的200個。底層的調(diào)度者會迅速在這些機器上重啟新的工作進程（因為只有進程被殺掉，機器本身運行正常）。

工作進程死掉會出現(xiàn)負的輸入速率，因為一些之前已經(jīng)完成的map工作消失了（因為香港的map工作進程被kill掉了），并且需要重新執(zhí)行。這個map任務會相當快的重新執(zhí)行。整個計算過程在933秒后完成，包括了啟動開銷（僅僅比普通情況多花費了5%的時間）。

六、        經(jīng)驗

我們在2003年2月完成了MapReduce庫的第一個版本，并在2003年8月做了重大的改進，包括位置優(yōu)化、任務在工作機器上的動態(tài)負載均衡執(zhí)行等。從那時起，我們驚喜的發(fā)現(xiàn)，MapReduce庫能夠廣泛的用于我們工作中的各種問題。它已經(jīng)被用于Google內(nèi)部廣泛的領(lǐng)域，包括：

• 大規(guī)模機器學習問題

• Google新聞和Froogle產(chǎn)品的集群問題

• 抽取數(shù)據(jù)用于公眾查詢的產(chǎn)品報告

• 從大量新應用和新產(chǎn)品的網(wǎng)頁中抽取特性（如，從大量的位置查詢頁面中抽取地理位置信息）

• 大規(guī)模圖形計算

表1： 2004年8月運行的MapReduce任務

在每個工作的最后，MapReduce庫統(tǒng)計了工作使用的計算資源。在表1中，我們看到一些2004年8月在Google內(nèi)部運行的MapReduce工作的一些統(tǒng)計數(shù)據(jù)。

6.1 大規(guī)模索引

目前為止，MapReduce最重要的應用之一就是完成了對生產(chǎn)索引系統(tǒng)的重寫，它生成了用于Google網(wǎng)頁搜索服務的數(shù)據(jù)結(jié)構(gòu)。索引系統(tǒng)的輸入數(shù)據(jù)是通過我們的爬取系統(tǒng)檢索到的海量文檔，存儲為就一個GFS文件集合。這些文件的原始內(nèi)容還有超過20TB的數(shù)據(jù)。索引程序是一個包含了5-10個MapReduce操作的序列。使用MapReduce（代替了之前版本的索引系統(tǒng)中的adhoc分布式處理）有幾個優(yōu)點：

• 索引程序代碼是一個簡單、短小、易于理解的代碼，因為容錯、分布式和并行處理都隱藏在了MapReduce庫中。比如，一個計算程序的大小由接近3800行的C++代碼減少到使用MapReduce的大約700行的代碼。

• MapReduce庫性能非常好，以至于能夠?qū)⒏拍钌喜幌嚓P(guān)的計算分開，來代替將這些計算混合在一起進行，避免額外的數(shù)據(jù)處理。這會使索引程序易于改變。比如，對之前的索引系統(tǒng)做一個改動大概需要幾個月時間，而對新的系統(tǒng)則只需要幾天時間。

• 索引程序變得更易于操作，因為大多數(shù)由于機器故障、機器處理速度慢和網(wǎng)絡(luò)的瞬間阻塞等引起的問題都被MapReduce庫自動的處理掉，而無需人為的介入。

七、        相關(guān)工作

許多系統(tǒng)都提供了有限的程序模型，并且對自動的并行計算使用了限制。比如，一個結(jié)合函數(shù)可以在logN時間內(nèi)在N個處理器上對一個包含N個元素的數(shù)組使用并行前綴計算，來獲取所有的前綴[6，9，13]。MapReduce被認為是這些模型中基于我們對大規(guī)模工作計算的經(jīng)驗的簡化和精華。更為重要的是，我們提供了一個在數(shù)千個處理器上的容錯實現(xiàn)。相反的，大多數(shù)并行處理系統(tǒng)只在較小規(guī)模下實現(xiàn)，并將機器故障的處理細節(jié)交給了程序開發(fā)者。

Bulk Synchronous Programming和一些MPI源于提供了更高層次的抽象使它更易于讓開發(fā)者編寫并行程序。這些系統(tǒng)和MapReduce的一個關(guān)鍵不同點是MapReduce開發(fā)了一個有限的程序模型來自動的并行執(zhí)行用戶的程序，并提供了透明的容錯機制。

我們的位置優(yōu)化機制的靈感來自于移動磁盤技術(shù)，計算用于處理靠近本地磁盤的數(shù)據(jù)，減少數(shù)據(jù)在I/O子系統(tǒng)或網(wǎng)絡(luò)上傳輸?shù)拇螖?shù)。我們的系統(tǒng)運行在掛載幾個磁盤的普通機器上，而不是在磁盤處理器上運行，但是一般方法是類似的。

我們的備用任務機制與Charlotte系統(tǒng)中采用的eager調(diào)度機制類似。簡單的Eager調(diào)度機制有一個缺點，如果一個給定的任務造成反復的失敗，整個計算將以失敗告終。我們通過跳過損壞計算路的機制，解決了這個問題的一些情況。

MapReduce實現(xiàn)依賴了內(nèi)部集群管理系統(tǒng)，它負責在一個大規(guī)模的共享機器集合中分發(fā)和運行用戶的任務。盡管不是本篇文章的焦點，但是集群管理系統(tǒng)在本質(zhì)上與像Condor的其它系統(tǒng)類似。

排序功能是MapReduce庫的一部分，與NOW-Sort中的操作類似。源機器（map工作進程）將將要排序的數(shù)據(jù)分區(qū)，并將其發(fā)送給R個Reduce工作進程中的一個。每個reduce工作進程在本地對這些數(shù)據(jù)進行排序（如果可能的話就在內(nèi)存中進行）。當然NOW-Sort沒有使MapReduce庫能夠廣泛使用的用戶定義的Map和Reduce函數(shù)。

River提供了一個編程模型，處理進程通過在分布式隊列上發(fā)送數(shù)據(jù)來進行通信。像MapReduce一樣，即使在不均勻的硬件或系統(tǒng)顛簸的情況下，River系統(tǒng)依然試圖提供較好的平均性能。River系統(tǒng)通過小心的磁盤和網(wǎng)絡(luò)傳輸調(diào)度來平衡完成時間。通過限制編程模型，MapReduce框架能夠?qū)栴}分解成很多細顆粒的任務，這些任務在可用的工作進程上動態(tài)的調(diào)度，以至于越快的工作進程處理越多的任務。這個受限制的編程模型也允許我們在工作將要結(jié)束時調(diào)度冗余的任務進行處理，這樣可以減少不均勻情況下的完成時間。

BAD-FS與MapReduce有完全不同的編程模型，不像MapReduce，它是用于在廣域網(wǎng)下執(zhí)行工作的。然而，它們有兩個基本相似點。（1）兩個系統(tǒng)都使用了重新執(zhí)行的方式來處理因故障而丟失的數(shù)據(jù)。（2）兩個系統(tǒng)都本地有限調(diào)度原則來減少網(wǎng)絡(luò)鏈路上發(fā)送數(shù)據(jù)的次數(shù)。

TASCC是一個用于簡化結(jié)構(gòu)的高可用性的網(wǎng)絡(luò)服務。像MapReduce一樣，它依靠重新執(zhí)行作為一個容錯機制。

感謝各位的閱讀，以上就是“MapReduce編程模型是什么”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對MapReduce編程模型是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！