我們?yōu)槭裁匆P(guān)注MapReduce?
1．什么是MapReduce?
MapReduce 是由Google公司的Jeffrey Dean 和 Sanjay Ghemawat 開發(fā)的一個(gè)針對大規(guī)模群組中的海量數(shù)據(jù)處理的分布式編程模型。MapReduce實(shí)現(xiàn)了兩個(gè)功能。Map把一個(gè)函數(shù)應(yīng)用于集合中的所有成員，然后返回一個(gè)基于這個(gè)處理的結(jié)果集。而Reduce是把從兩個(gè)或更多個(gè)Map中，通過多個(gè)線程，進(jìn)程或者獨(dú)立系統(tǒng)并行執(zhí)行處理的結(jié)果集進(jìn)行分類和歸納。Map() 和 Reduce() 兩個(gè)函數(shù)可能會并行運(yùn)行，即使不是在同一的系統(tǒng)的同一時(shí)刻。
Google 用MapReduce來索引每個(gè)抓取過來的Web頁面。它取代了2004開始試探的最初索引算法，它已經(jīng)證明在處理大量和非結(jié)構(gòu)化數(shù)據(jù)集時(shí)更有效。用不同程序設(shè)計(jì)語言實(shí)現(xiàn)了多個(gè)MapReduce，包括 Java, C++, Python, Perl, Ruby和C, 其它語言。在某些范例里，如Lisp或者Python, Map() 和Reduce()已經(jīng)集成到語言自身的結(jié)構(gòu)里面。通常，這些函數(shù)可能會如下定義：
List2 map(Functor1, List1);
Object reduce(Functor2, List2);
Map()函數(shù)把大數(shù)據(jù)集進(jìn)行分解操作到兩個(gè)或更多的小“桶”。而一個(gè)“桶”則是包含松散定義的邏輯記錄或者文本行的集合。每個(gè)線程，處理器或者系統(tǒng)在獨(dú)立的“桶”上執(zhí)行Map()函數(shù)，去計(jì)算基于每個(gè)邏輯記錄處理的一系列中間值。合并的結(jié)果值就會如同是單個(gè)Map()函數(shù)在單個(gè)“桶”上完全一致。Map()函數(shù)的通常形式是：
map(function, list) { foreach element in list { v = function(element)
intermediateResult.add(v)
}
} // map
Reduce()函數(shù)把從內(nèi)存，磁盤或者網(wǎng)絡(luò)介質(zhì)提取過來的一個(gè)或多個(gè)中間結(jié)果列表，對列表中的每個(gè)元素逐一執(zhí)行一個(gè)函數(shù)。完成操作的最終結(jié)果是通過對所有運(yùn)行reduce()操作的處理結(jié)果進(jìn)行分類和解釋。Reduce()函數(shù)的通常形式是：
reduce(function, list, init) { result = init
foreach value in list { result = function(result, value)
}
outputResult.add(result)
}
MapReduce的實(shí)現(xiàn)把業(yè)務(wù)邏輯從多個(gè)處理邏輯中分離出來了，map()和reduce()函數(shù)跨越多個(gè)系統(tǒng)，通過共享池和部分RPC的形式來達(dá)到彼此之間的同步和通信。這里的業(yè)務(wù)邏輯是由用戶自定義的函數(shù)子實(shí)現(xiàn)，并且這些函數(shù)子只能用在邏輯記錄處理的工作上，而不用關(guān)心多個(gè)處理操作的問題。這樣一旦MapReduce框架就位，就能通過大量的處理器快速的轉(zhuǎn)變?yōu)閼?yīng)用系統(tǒng)的并行處理。因?yàn)殚_發(fā)人員可以把精力花在寫函數(shù)子上面了。MapReduce簇可以通過替換函數(shù)子和提供新的數(shù)據(jù)源來重新使用，而無需每次都對整個(gè)應(yīng)用進(jìn)行編譯，測試和部署。
2．實(shí)現(xiàn)MapReduce
MapReduce()的目的是為了大型集群的系統(tǒng)能在大數(shù)據(jù)集上進(jìn)行并行工作。
圖1顯示了一個(gè)運(yùn)行在一個(gè)主系統(tǒng)上的主程序，協(xié)調(diào)其它實(shí)例進(jìn)行map()或者reduce()操作，然后從每個(gè)reduce操作中收集結(jié)果。
【圖 1】
主應(yīng)用程序負(fù)責(zé)把基礎(chǔ)的數(shù)據(jù)集分解到“桶”中。桶的最佳大小依賴于應(yīng)用，結(jié)點(diǎn)的數(shù)量和可用的I/O帶寬。這些“桶”通常存儲在磁盤，但有必要也可能分散到主存中，這依賴于具體的應(yīng)用。“桶”將作為map()函數(shù)的輸入。
主應(yīng)用程序也負(fù)責(zé)調(diào)度和分散幾個(gè)MapReduce的核心備份，除了控制者給空閑的處理器或線程分配了調(diào)整map()和reduce()任務(wù)之外，它們是完全相致的。控制者會持續(xù)跟蹤每個(gè)map()和reduce()任務(wù)的狀態(tài)，并且可以作為map()和reduce()任務(wù)之間路由中間結(jié)果的管道。每個(gè)map() 任務(wù)處理器完全指派給“桶”，然后產(chǎn)生一個(gè)存到共享存儲區(qū)域的中間結(jié)果集。共享存儲可以設(shè)計(jì)成分布緩存，磁盤或其它設(shè)備等形式。當(dāng)一個(gè)新的中間結(jié)果寫入共享存儲區(qū)域后，任務(wù)就向控制者發(fā)出通知，并提供指向其共享存儲位置的句柄。
當(dāng)新的中間結(jié)果可用時(shí)，控制者分配reduce()任務(wù)。這個(gè)任務(wù)通過應(yīng)用獨(dú)立的中間鍵值來實(shí)現(xiàn)排序，使相同的數(shù)據(jù)能聚集在一起，以提供更快的檢索。大塊的結(jié)果集可以進(jìn)行外部排序，reduce()任務(wù)遍歷整個(gè)排序的數(shù)據(jù)，把每個(gè)唯一的鍵和分類的結(jié)果傳遞到用戶的reduce() 函數(shù)子進(jìn)行處理。
通過map()和reduce()實(shí)例終端的處理，當(dāng)所有的“桶”都用完，然后全部的reduce()任務(wù)就通知控制者，以說明它們的結(jié)果已經(jīng)產(chǎn)生了。控制者就向主應(yīng)用程序發(fā)出檢索這個(gè)結(jié)果的信號。主應(yīng)用程序可能就直接操作這些結(jié)果，或者重新分配到不同的MapReduce控制者和任務(wù)進(jìn)行進(jìn)一步的處理，
顯示情況下MapReduce的實(shí)現(xiàn)可能通常分配給控制者，map()和reduce()任務(wù)分配給單獨(dú)的系統(tǒng)。Google操作模型是基于跨越大量的廉價(jià)硬件設(shè)備上組成的集群或者白盒子上面部署MapReduce應(yīng)用。為了處理它自己的桶的需要，每個(gè)白盒子都有本地存儲裝置，一個(gè)合理數(shù)量的私有內(nèi)存（2到4GB RAM）和至少兩個(gè)處理內(nèi)核。白盒子是可互相交換的，主應(yīng)用程序可能把集群中的任何機(jī)器指派為控制者，而這個(gè)機(jī)器就把map()和reduce()任務(wù)分派給其它連接的白盒子。
3．基于Java的MapReduce 實(shí)現(xiàn)
Google的環(huán)境是為它自己的需求定制和適應(yīng)它們的操作環(huán)境。比如，為了它的MapReduce實(shí)現(xiàn)更好的執(zhí)行這種類型的操作，使其更優(yōu)化，Google使用了專有的文件系統(tǒng)用來存儲文件。相反，企業(yè)應(yīng)用系統(tǒng)都是建立在Java或類似的技術(shù)上面的，它們依賴于已有的文件系統(tǒng)，通信協(xié)議和應(yīng)用棧。
一個(gè)基于Java的MapReduce實(shí)現(xiàn)應(yīng)該考慮到已存在的數(shù)據(jù)存儲設(shè)備，將來部署到的結(jié)構(gòu)里面支持那種協(xié)議，有哪些內(nèi)部API和支持部署那種第三方產(chǎn)品（開源的或商業(yè)的）。圖2顯示了通常的架構(gòu)是如何通過映射到已有的、健壯的Java開源架構(gòu)來實(shí)現(xiàn)的。
【圖 2】
這個(gè)架構(gòu)采用了已有的工具，比如Terracotta和Mule，它們經(jīng)常出現(xiàn)在很多企業(yè)系統(tǒng)的組織里面。已物理或虛擬系統(tǒng)形成存在的白盒子通過有效簡單的配置和部署，設(shè)計(jì)成MapReduce群組中的一部分。為了效率，一個(gè)很大的系統(tǒng)可以分解到幾個(gè)虛擬機(jī)器上，如果需要可以分配更多的結(jié)點(diǎn)。可以根據(jù)容量的問題和處理器的有效利用賴決定是否在群集中使用物理“白盒子”，虛擬機(jī)或者它們兩者的結(jié)合。
Terracotta 集群技術(shù)是map()和reduce()任務(wù)之間共享數(shù)據(jù)的很好選擇，因?yàn)樗?/span>map()和reduce()之間的通信過程，包括共享文件或者使用RPC調(diào)用已初始處理結(jié)構(gòu)都做了抽象。
從前面章節(jié)的描述知道，Map()和reduce()任務(wù)是在同一個(gè)核心應(yīng)用中實(shí)現(xiàn)的。用來共享中間結(jié)構(gòu)集的數(shù)據(jù)結(jié)構(gòu)可以保持在內(nèi)存的數(shù)據(jù)結(jié)構(gòu)中，通過Terracotta透明的共享交換。
由跨域集群的MapReduce產(chǎn)生的進(jìn)程內(nèi)通信問題，自從Terracotta運(yùn)行時(shí)掌管著這些共享數(shù)據(jù)結(jié)構(gòu)后就不存在了。不同于實(shí)現(xiàn)一個(gè)復(fù)雜的信號系統(tǒng)，所有的map()任務(wù)需要標(biāo)記內(nèi)存中的中間結(jié)構(gòu)集，然后reduce()任務(wù)就直接提取它們。
控制者和主應(yīng)用程序都會在同時(shí)處在等待狀態(tài)一段時(shí)間，即使是MapReduce集群有大量可用的并行處理能力。這兩個(gè)組件之間以及當(dāng)歸并完成后的reduce()任務(wù)和控制者之間，都是通過Mule的ESB傳遞信號的。通過這種方式，為了其它應(yīng)用的處理，輸出結(jié)構(gòu)可以排到隊(duì)列，或者像前面章節(jié)講的一樣，為了其他MapReduced的處理，一個(gè)Mule服務(wù)對象（or UMO）可以把這些輸出結(jié)果分解到“桶”中。
通過主流的企業(yè)應(yīng)用協(xié)議或者完全的原始TCP/IP Sockets，Mule支持在內(nèi)存中進(jìn)行同步和異步的數(shù)據(jù)傳輸. Mule可以用于在同一臺機(jī)器執(zhí)行的應(yīng)用系統(tǒng)，跨域不同的數(shù)據(jù)中心或者在完全不同地方且被程序員分開標(biāo)識的本地終端結(jié)點(diǎn)互相傳遞輸出結(jié)構(gòu)集。其它基于Java的實(shí)現(xiàn)可以通過Hadoop, 是一個(gè)用于運(yùn)行應(yīng)用程序在大型集群的廉價(jià)硬件設(shè)備上的框架， 它是基于lucene框架。Hadoop是一個(gè)開源，點(diǎn)對點(diǎn)，通用的MapReduce實(shí)現(xiàn)。
4.結(jié)論
不管使用什么技術(shù)，索引大量非結(jié)構(gòu)化數(shù)據(jù)是一件很艱難的任務(wù)。應(yīng)用傳統(tǒng)的算法和啟發(fā)式方法很難維護(hù)，因?yàn)殡S著時(shí)間的推移，系統(tǒng)的性能下降使系統(tǒng)變得難以控制。RDBMS 能有效的用于索引和檢索大量的結(jié)構(gòu)化數(shù)據(jù)集合，但不適合用于非結(jié)構(gòu)化的數(shù)據(jù)。MapReduce為并行系統(tǒng)的數(shù)據(jù)處理，提供了一個(gè)簡單，優(yōu)雅的解決方案，優(yōu)勢有：
l 歸并成本
l 程序員的高產(chǎn)出，因?yàn)橛貌⑿械拇a獨(dú)立實(shí)現(xiàn)了業(yè)務(wù)邏輯
l 比傳統(tǒng)RDBMS技術(shù)更好的性能和更優(yōu)的結(jié)果。
l 使用Java企業(yè)框架和開發(fā)人員都熟悉的已有的技術(shù)和工具更易部署
用MapReduce, Google有令人印象深刻的跟蹤記錄，而且每天出現(xiàn)的工具都能輕易的融入到這個(gè)體系中。在企業(yè)級的應(yīng)用系統(tǒng)中，如果你準(zhǔn)備開始一個(gè)快速，簡單的任務(wù)，例如根據(jù)IP地址分析請求的擁堵模型到你的web集群中，或者類似的東西。一個(gè)這樣的練習(xí)將會很大程度上提高你對關(guān)鍵系統(tǒng)面臨的問題和挑戰(zhàn)的認(rèn)識,MapReduce則就是為這些而準(zhǔn)備的。
英文原址：http://www.theserverside.com/tt/knowledgecenter-tc/knowledgecenter-tc.tss?l=MapReduce