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

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

我記著我大二的時(shí)候曾經(jīng)做過一個(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í)間了。后來大學(xué)畢業(yè)收拾東西的時(shí)候找到這個(gè)程序，試了一下，發(fā)現(xiàn)算10步需要的時(shí)間也基本上感覺不出來了。

不知道你是否有同樣的經(jīng)歷，我們不知不覺的一直在享受著這樣的免費(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í)間，但問題是，我們必須做出改變，面對(duì)這個(gè)即將到來的變革，你準(zhǔn)備好了么？

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

我覺得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ì)碰到這樣的問題），每個(gè)程序員都需要進(jìn)行分布式的程序開發(fā)，這其中包括如何分布、調(diào)度、監(jiān)控以及容錯(cuò)等等。Google的MapReduce正是把分布式的業(yè)務(wù)邏輯從這些復(fù)雜的細(xì)節(jié)中抽象出來，使得沒有或者很少并行開發(fā)經(jīng)驗(yàn)的程序員也能進(jìn)行并行應(yīng)用程序的開發(fā)。

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

拿前面說過圖像處理程序來舉例，其實(shí)大多數(shù)的圖像處理操作都是對(duì)圖像矩陣進(jìn)行某種運(yùn)算。這里的運(yùn)算通常有兩種，一種是映射，一種是規(guī)約。拿兩種效果來說，”老照片”效果通常是強(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ù)雜問題，古人教導(dǎo)我們要“分而治之”，英文中對(duì)應(yīng)的詞是”Divide and Conquer“。Map/Reduce其實(shí)就是Divide/Conquer的過程，通過把問題Divide，使這些Divide后的Map運(yùn)算高度并行，再將Map后的結(jié)果Reduce（根據(jù)某一個(gè)Key），得到最終的結(jié)果。

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

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

接下來就放下其它，研究一下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)過Map運(yùn)算后輸出的中間文件將會(huì)是：

	I,1
am,1
a,1
blogger,1
you,1
are,1
a,1
blogger,1

Reduce操作的輸入是單詞和出現(xiàn)次數(shù)的序列。用上面的例子來說，就是 (”I”, [1, 1]), (”love”, [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來處理；
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)是，在寫磁盤的時(shí)候，需要將中間文件做Partition（比如R個(gè)）。拿上面的例子來舉例，如果把所有的信息存到一個(gè)文件，Reduce worker又會(huì)變成瓶頸。我們只需要保證相同Key能出現(xiàn)在同一個(gè)Partition里面就可以把這個(gè)問題分解。
5. R個(gè)Reduce worker開始工作，從不同的Map worker的Partition那里拿到數(shù)據(jù)（read the buffered data from the local disks of the map workers），用key進(jìn)行排序（如果內(nèi)存中放不下需要用到外部排序 - external sort）。很顯然，排序（或者說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è)）。

可見，這里的分（Divide）體現(xiàn)在兩步，分別是將輸入分成M份，以及將Map的中間結(jié)果分成R份。將輸入分開通常很簡(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ì)于上面的例子來說，每個(gè)文檔中都可能會(huì)出現(xià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。我一直覺得，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。我真的能感覺的到Google著名的免費(fèi)晚餐之外的對(duì)于程序員的另一種免費(fèi)的晚餐，那個(gè)由大量的commodity PC組成的large clusters。我覺得這些才真正是Google的核心價(jià)值所在。

呵呵，就像微軟老兵Joel Spolsky（你應(yīng)該看過他的”Joel on Software”吧？）曾經(jīng)說過，對(duì)于微軟來說最可怕的是[1]，微軟還在苦苦追趕Google來完善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。問題是，大公司里，要想重新部署這樣一個(gè)底層的InfraStructure，無論是技術(shù)的原因，還是政治的原因，將是如何的難。

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

Popularity: 52%

This entry was posted on Wednesday, November 15th, 2006 at 8:54 pm and is filed under 技術(shù). You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Related entries:

• How NLB works
• Final Destination
• Google Pack, Google Dell Page
• 重度Google使用者
• Google Base : the largest CMS in the world?
• Googlebombing, Google WiFi
• I just found Google Bendi
• Google的影響力
• MSN Messenger 7.5 Released
• Pull -> Push era coming ?
• An architecture of participation
• Xerdoc網(wǎng)站靜態(tài)化備忘