轉(zhuǎn)自孟巖的blog : http://www.mengyan.org/blog/archives/2006/11/15/138.html

Map Reduce – the Free Lunch is not over?

微軟著名的C++大師 Herb Sutter 在2005年初的時(shí)候曾經(jīng)寫(xiě)過(guò)一篇重量級(jí)的文章：” The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software “，預(yù)言O(shè)O之后軟件開(kāi)發(fā)將要面臨的又一次重大變革-并行計(jì)算。

摩爾定律統(tǒng)制下的軟件開(kāi)發(fā)時(shí)代有一個(gè)非常有意思的現(xiàn)象：”Andy giveth, and Bill taketh away.”。不管CPU的主頻有多快，我們始終有辦法來(lái)利用它，而我們也陶醉在機(jī)器升級(jí)帶來(lái)的程序性能提高中。

我記著我大二的時(shí)候曾經(jīng)做過(guò)一個(gè)五子棋的程序，當(dāng)時(shí)的算法就是預(yù)先設(shè)計(jì)一些棋型（有優(yōu)先級(jí)），然后掃描棋盤，對(duì)形勢(shì)進(jìn)行分析，看看當(dāng)前走哪部對(duì)自己 最重要。當(dāng)然下棋還要堵別人，這就需要互換雙方的棋型再計(jì)算。如果只算一步，很可能被狡猾的對(duì)手欺騙，所以為了多想幾步，還需要遞歸和回朔。在當(dāng)時(shí)的機(jī)器 上，算3步就基本上需要3秒左右的時(shí)間了。后來(lái)大學(xué)畢業(yè)收拾東西的時(shí)候找到這個(gè)程序，試了一下，發(fā)現(xiàn)算10步需要的時(shí)間也基本上感覺(jué)不出來(lái)了。

不知道你是否有同樣的經(jīng)歷，我們不知不覺(jué)的一直在享受著這樣的免費(fèi)午餐。可是，隨著摩爾定律的提前終結(jié)，免費(fèi)的午餐終究要還回去。雖然硬件設(shè)計(jì)師還 在努力：Hyper Threading CPU（多出一套寄存器，相當(dāng)于一個(gè)邏輯CPU）使得Pipeline盡可能滿負(fù)荷，使多個(gè)Thread的操作有可能并行，使得多線程程序的性能有 5%-15%的提升；增加Cache容量也使得包括Single-Thread和Multi-Thread程序都能受益。也許這些還能幫助你一段時(shí)間，但 問(wèn)題是，我們必須做出改變，面對(duì)這個(gè)即將到來(lái)的變革，你準(zhǔn)備好了么？

Concurrency Programming != Multi-Thread Programming 。很多人都會(huì)說(shuō)MultiThreading誰(shuí)不會(huì)，問(wèn)題是，你是為什么使用/如何使用多線程的？我從前做過(guò)一個(gè)類似AcdSee 一樣的圖像查看/處理程序，我通常用它來(lái)處理我的數(shù)碼照片。我在里面用了大量的多線程，不過(guò)主要目的是在圖像處理的時(shí)候不要Block住UI，所以將 CPU Intensive的計(jì)算部分用后臺(tái)線程進(jìn)行處理。而并沒(méi)有把對(duì)圖像矩陣的運(yùn)算并行分開(kāi)。

我覺(jué) 得Concurrency Programming真正的挑戰(zhàn)在于Programming Model的改變，在程序員的腦子里面要對(duì)自己的程序怎樣并行化有很清楚的 認(rèn)識(shí) ，更重要的是，如何去 實(shí)現(xiàn) （包括架構(gòu)、容錯(cuò)、實(shí)時(shí)監(jiān)控等等）這種并行化，如何去 調(diào)試 ，如何去 測(cè)試 。

在Google，每天有海量的數(shù)據(jù)需要在有限的時(shí)間內(nèi)進(jìn)行處理（其實(shí)每個(gè)互聯(lián)網(wǎng)公司都會(huì)碰到這樣的問(wèn)題），每個(gè)程序員都需要進(jìn)行分布式的程序開(kāi)發(fā)，這其中包括如何分布、調(diào)度、監(jiān)控以及容錯(cuò)等等 。Google的 MapReduce 正是把分布式的業(yè)務(wù)邏輯從這些復(fù)雜的細(xì)節(jié)中抽象出來(lái)，使得沒(méi)有或者很少并行開(kāi)發(fā)經(jīng)驗(yàn)的程序員也能進(jìn)行并行應(yīng)用程序的開(kāi)發(fā)。

　　MapReduce中最重要的兩個(gè)詞就是 Map（映射） 和 Reduce（規(guī)約） 。初看Map/Reduce這兩個(gè)詞，熟悉Function Language的人一定感覺(jué)很熟悉。FP把這樣的函數(shù)稱為”higher order function”（”High order function”被成為Function Programming的利器之一哦），也就是說(shuō)，這些函數(shù)是編寫(xiě)來(lái)被與其它函數(shù)相結(jié)合（或者說(shuō)被其它函數(shù)調(diào)用的）。如果說(shuō)硬要比的化，可以把它想象成C 里面的CallBack函數(shù)，或者STL里面的 Functor 。比如你要對(duì)一個(gè)STL的容器進(jìn)行查找，需要制定每?jī)蓚€(gè)元素相比較的 Functor（Comparator），這個(gè)Comparator在遍歷容器的時(shí)候就會(huì)被調(diào)用。

拿前面說(shuō)過(guò)圖像處理程序來(lái)舉例，其實(shí)大多數(shù)的圖像處理操作都是對(duì)圖像矩陣進(jìn)行某種運(yùn)算。這里的運(yùn)算通常有兩種，一種是映射，一種是規(guī)約。拿兩種效果 來(lái)說(shuō)，”老照片”效果通常是強(qiáng)化照片的G/B值，然后對(duì)每個(gè)象素加一些隨機(jī)的偏移，這些操作在二維矩陣上的每一個(gè)元素都是獨(dú)立的，是Map操作。而”雕 刻”效果需要提取圖像邊緣，就需要元素之間的運(yùn)算了，是一種Reduce操作。再舉個(gè)簡(jiǎn)單的例子， 一個(gè)一維矩陣（數(shù)組）[0,1,2,3,4]可以映射為 [0,2,3,6,8]（乘2），也可以映射為[1,2,3,4,5]（加1）。它可以規(guī)約為0（元素求積）也可以規(guī)約為10（元素求和）。

面對(duì)復(fù)雜問(wèn)題，古人教導(dǎo)我們要“ 分 而 治 之”，英文中對(duì)應(yīng)的詞是” Divide and Conquer “。Map/Reduce其實(shí)就是Divide/Conquer的過(guò)程， 通過(guò)把問(wèn)題Divide，使這些Divide后的Map運(yùn)算高度并行，再將Map后的結(jié)果Reduce（根據(jù)某一個(gè)Key），得到最終的結(jié)果。

Googler發(fā)現(xiàn)這是問(wèn)題的核心，其它都是共性問(wèn)題。因此，他們把MapReduce抽象分離出來(lái)。這樣，Google的 程序員可以只關(guān)心應(yīng)用邏輯，關(guān)心根據(jù)哪些Key把問(wèn)題進(jìn)行分解，哪些操作是Map操作，哪些操作是Reduce操作 。其它并行 計(jì)算中的復(fù)雜問(wèn)題諸如分布、工作調(diào)度、容錯(cuò)、機(jī)器間 通信都交給Map/Reduce Framework去做 ，很大程度上簡(jiǎn)化了整個(gè)編程模型。

MapReduce的另一個(gè)特點(diǎn)是，Map和Reduce的 輸入和輸出都是中間臨時(shí)文件 （MapReduce利用Google文件系統(tǒng)來(lái)管理和訪問(wèn)這些文件），而不是不同進(jìn)程間或者不同機(jī)器間的其它通信方式。我覺(jué)得，這是Google一貫的風(fēng)格，化繁為簡(jiǎn)，返璞歸真。

接下來(lái)就放下其它，研究一下Map/Reduce操作。（其它比如容錯(cuò)、備份任務(wù)也有很經(jīng)典的經(jīng)驗(yàn)和實(shí)現(xiàn)，論文里面都有詳述）

Map的定義 ：

Map, written by the user, takes an input pair and produces a set of intermediate key/value pairs. The MapReduce library groups together all intermediate values associated with the same intermediate key I and passes them to the Reduce function.

Reduce的定義 ：

The Reduce function, also written by the user, accepts an intermediate key I and a set of values for that key. It merges together these values to form a possibly smaller set of values. Typically just zero or one output value is produced per Reduce invocation. The intermediate values are supplied to the user’s reduce function via an iterator. This allows us to handle lists of values that are too large to fit in memory.

MapReduce論文中給出了這樣一個(gè)例子：在一個(gè)文檔集合中統(tǒng)計(jì)每個(gè)單詞出現(xiàn)的次數(shù)。

Map操作的輸入是每一篇文檔，將輸入文檔中每一個(gè)單詞的出現(xiàn)輸出到中間文件中去。

map(String key, String value):
// key: document name
// value: document contents
for each word w in value:
EmitIntermediate(w, “1″);

比如我們有兩篇文檔，內(nèi)容分別是

A － “I love programming”

B － “I am a blogger, you are also a blogger”。

B文檔經(jīng)過(guò)Map運(yùn)算后輸出的中間文件將會(huì)是：

    I,1
    

     am,1
    

     a,1
    

     blogger,1
    

     you,1
    

     are,1
    

     a,1
    

     blogger,1
  

Reduce操作的輸入是單詞和出現(xiàn)次數(shù)的序列。用上面的例子來(lái)說(shuō)，就是 (“I”, [1, 1]), (“l(fā)ove”, [1]), (“programming”, [1]), (“am”, [1]), (“a”, [1,1]) 等。然后根據(jù)每個(gè)單詞，算出總的出現(xiàn)次數(shù)。

reduce(String key, Iterator values):
// key: a word
// values: a list of counts
int result = 0;
for each v in values:
result += ParseInt(v);
Emit(AsString(result));

最后輸出的最終結(jié)果就會(huì)是：(“I”, 2″), (“a”, 2″)……

實(shí)際的執(zhí)行順序是 ：

1. MapReduce Library將Input分成M份。這里的Input Splitter也可以是多臺(tái)機(jī)器 并行Split 。
2. Master將M份Job分給Idle狀態(tài)的M個(gè)worker來(lái)處理；
3. 對(duì)于輸入中的每一個(gè)<key, value> pair 進(jìn)行Map操作，將中間結(jié)果Buffer在Memory里；
4. 定期的（或者根據(jù)內(nèi)存狀態(tài)），將Buffer中的中間信息Dump到 本地 磁盤上，并且把文件信息傳回給Master（Master需要把這些信息發(fā)送給Reduce worker）。這里最重要的一點(diǎn)是， 在寫(xiě)磁盤的時(shí)候，需要將中間文件做Partition（比如R個(gè)） 。拿上面的例子來(lái)舉例，如果把所有的信息存到一個(gè)文件，Reduce worker又會(huì)變成瓶頸。我們只需要保證 相同Key能出現(xiàn)在同一個(gè)Partition 里面就可以把這個(gè)問(wèn)題分解。
5. R個(gè)Reduce worker開(kāi)始工作，從不同的Map worker的Partition那里拿到數(shù)據(jù)（ read the buffered data from the local disks of the map workers ）， 用key進(jìn)行排序（如果內(nèi)存中放不下需要用到外部排序 – external sort）。很顯然，排序（或者說(shuō)Group）是Reduce函數(shù)之前必須做的一步。 這里面很關(guān)鍵的是，每個(gè)Reduce worker會(huì)去從很多Map worker那里拿到X(0<X<R) Partition的中間結(jié)果，這樣，所有屬于這個(gè)Key的信息已經(jīng)都在這個(gè)worker上了。
6. Reduce worker遍歷中間數(shù)據(jù)，對(duì)每一個(gè)唯一Key，執(zhí)行Reduce函數(shù)（參數(shù)是這個(gè)key以及相對(duì)應(yīng)的一系列Value）。
7. 執(zhí)行完畢后，喚醒用戶程序，返回結(jié)果（最后應(yīng)該有R份Output，每個(gè)Reduce Worker一個(gè)） 。

可見(jiàn)，這里的分（Divide）體現(xiàn)在兩步， 分別是將輸入分成M份，以及將Map的中間結(jié)果分成R份 。將輸入分開(kāi)通常很簡(jiǎn)單，Map的中間結(jié)果通常 用”hash(key) mod R”這個(gè)結(jié)果作為標(biāo)準(zhǔn)，保證相同的Key出現(xiàn)在同一個(gè)Partition里面。當(dāng)然，使用者也可以指定自己的Partition Function，比如，對(duì)于Url Key，如果希望同一個(gè)Host的URL出現(xiàn)在同一個(gè)Partition，可以用”hash(Hostname(urlkey)) mod R”作為Partition Function。

對(duì)于上面的例子來(lái)說(shuō)，每個(gè)文檔中都可能會(huì)出現(xiàn)成千上萬(wàn)的 (“the”, 1)這樣的中間結(jié)果，瑣碎的中間文件必然導(dǎo)致傳輸上的損失。因此，MapReduce還支持用戶提供Combiner Function。這個(gè)函數(shù)通常與Reduce Function有相同的實(shí)現(xiàn)，不同點(diǎn)在于Reduce函數(shù)的輸出是最終結(jié)果，而Combiner函數(shù)的輸出是Reduce函數(shù)的某一個(gè)輸入的中間文件。

Tom White給出了Nutch[2]中另一個(gè)很直觀的例子， 分布式Grep 。我一直覺(jué)得，Pipe中的很多操作，比如More、Grep、Cat都類似于一種Map操作，而Sort、Uniq、wc等都相當(dāng)于某種Reduce操作。

加上前兩天Google剛剛發(fā)布的 BigTable 論文，現(xiàn)在Google有了自己的集群 – Googel Cluster ，分布式文件系統(tǒng) – GFS ，分布式計(jì)算環(huán)境 – MapReduce ，分布式結(jié)構(gòu)化存儲(chǔ) – BigTable ，再加上 Lock Service 。我真的能感覺(jué)的到Google著名的免費(fèi)晚餐之外的對(duì)于程序員的另一種免費(fèi)的晚餐，那個(gè)由大量的commodity PC組成的large clusters。我覺(jué)得這些才真正是Google的核心價(jià)值所在。

呵呵，就像微軟老兵 Joel Spolsky （你應(yīng)該看過(guò)他的”Joel on Software”吧？）曾經(jīng)說(shuō)過(guò)，對(duì)于微軟來(lái)說(shuō)最可怕的是[1]，微軟還在苦苦追趕Google來(lái)完善Search功能的時(shí)候，Google已經(jīng)在部署下一代的超級(jí)計(jì)算機(jī)了。

The very fact that Google invented MapReduce, and Microsoft didn’t, says something about why Microsoft is still playing catch up trying to get basic search features to work, while Google has moved on to the next problem: building Skynet^H^H^H^H^H^H the world’s largest massively parallel supercomputer . I don’t think Microsoft completely understands just how far behind they are on that wave.

注1：其實(shí)，微軟也有自己的方案 – DryAd 。問(wèn)題是，大公司里，要想重新部署這樣一個(gè)底層的InfraStructure，無(wú)論是技術(shù)的原因，還是政治的原因，將是如何的難。

注2： Lucene 之父Doug Cutting的又一力作，Project Hadoop ?- 由Hadoop分布式文件系統(tǒng)和一個(gè)Map/Reduce的實(shí)現(xiàn)組成，Lucene/Nutch的成產(chǎn)線也夠齊全。

[ZZ]Map/Reduce