LEC 1:Introduction

什么是分布式系統(tǒng)？

多臺(tái)協(xié)同工作的計(jì)算機(jī)。大型網(wǎng)站的存儲(chǔ)，MapReduce，P2P文件交換系統(tǒng)(peer-to-peer sharing),&c,DNS域名解析。許多關(guān)鍵的基礎(chǔ)設(shè)施是分布式的。

為何選擇分布式架構(gòu)？

1.聯(lián)通物理上分散的節(jié)點(diǎn),節(jié)點(diǎn)之間傳遞消息的唯一方式是通過不可靠的網(wǎng)絡(luò)進(jìn)行通信，即一個(gè)節(jié)點(diǎn)可以向其他節(jié)點(diǎn)通過網(wǎng)絡(luò)發(fā)送消息,但發(fā)送消息的節(jié)點(diǎn)無法確認(rèn)消息是否被接收節(jié)點(diǎn)完整正確收到,下面的章節(jié)會(huì)詳細(xì)討論這種網(wǎng)絡(luò)異常通信的問題。

2.通過各個(gè)節(jié)點(diǎn)的資源隔離保證安全。

3.通過備份實(shí)現(xiàn)高可用(通過復(fù)制實(shí)現(xiàn)容錯(cuò))，高可用(high availability)通常來描述一個(gè)系統(tǒng)經(jīng)過專門的設(shè)計(jì)，從而減少停工時(shí)間，而保持其服務(wù)的高度可用性。計(jì)算機(jī)系統(tǒng)的可用性可用平均無故障時(shí)間(MTTF)來度量，即計(jì)算機(jī)系統(tǒng)平均能夠正常運(yùn)行多長(zhǎng)時(shí)間，才發(fā)生一次故障?？捎眯栽礁?，平均無故障時(shí)間越長(zhǎng)。

4.通過并行的CPU/mem/disk/net來達(dá)到橫向擴(kuò)展,擴(kuò)容(來提高吞吐量，吞吐量是指在單位時(shí)間內(nèi)中央處理器(CPU)從設(shè)備讀取->處理->存儲(chǔ)信息的量，高吞吐意味著系統(tǒng)可以同時(shí)承載大量的用戶使用。高并發(fā)是高吞吐的延伸需求。)

分布式系統(tǒng)要求在不同的機(jī)器上進(jìn)行調(diào)用，網(wǎng)絡(luò)通信時(shí)間明顯大于單機(jī)服務(wù)，那為什么說能提高吞吐量呢？為什么通過并行的CPU/mem/disk/net這些能提高吞吐量呢？

只有當(dāng)單個(gè)節(jié)點(diǎn)的處理能力無法滿足日益增長(zhǎng)的計(jì)算，存儲(chǔ)任務(wù)，且硬件的提升(加內(nèi)存，加磁盤，使用更好的CPU)高昂到得不償失時(shí)候，應(yīng)用程序也不能進(jìn)一步優(yōu)化的時(shí)候，我們才需要考慮分布式系統(tǒng)。那么一臺(tái)服務(wù)器CPU/mem/disk/net等單位時(shí)間的吞吐量顯然是小于分布式系統(tǒng)，因?yàn)榉植际较到y(tǒng)明顯是有很多臺(tái)服務(wù)器的。所以當(dāng)單臺(tái)服務(wù)器運(yùn)行不了的時(shí)候(假設(shè)其耗時(shí)為N)，將其任務(wù)分別包給多臺(tái)機(jī)器，運(yùn)算完再返回其總體時(shí)間是要小于N的。值得注意的事，單個(gè)可執(zhí)行任務(wù)的單機(jī)吞吐量是大于分布式系統(tǒng)的，因?yàn)橐紤]通信消耗，但是我們需要考慮的是一整個(gè)系統(tǒng)的吞吐量

但是分布式系統(tǒng)實(shí)現(xiàn)很復(fù)雜，需要解決各個(gè)層次上的并發(fā)(多個(gè)并發(fā)部分)，肯定會(huì)出現(xiàn)部分節(jié)點(diǎn)失效的情況(必須處理部分失敗的情況)，還需要有很強(qiáng)的系統(tǒng)性能優(yōu)化能力，即難以實(shí)現(xiàn)的性能潛力(操作系統(tǒng)、文件系統(tǒng)、網(wǎng)絡(luò)Lan->Wan、數(shù)據(jù)庫(kù)等底層的優(yōu)化使用)。

主題

對(duì)分布式系統(tǒng)的復(fù)雜性進(jìn)行抽象，其包括下面三個(gè)抽象：存儲(chǔ)，通訊，計(jì)算(圖表:用戶、應(yīng)用服務(wù)器、存儲(chǔ)服務(wù)器)

這三個(gè)領(lǐng)域也是體系結(jié)構(gòu)的老問題，這三個(gè)領(lǐng)域中關(guān)于分布式系統(tǒng)工程實(shí)現(xiàn)都有一些共性需要去解決的問題，也是我們的主題，也將反復(fù)出現(xiàn)

實(shí)現(xiàn)(implementation)

RPC機(jī)制、線程機(jī)制、并發(fā)控制等如何高效實(shí)現(xiàn)

性能(performance)

理想: 可伸縮的吞吐量。通過購(gòu)買更多的機(jī)器處理更高的負(fù)載。

擴(kuò)展變得越來越困難：

負(fù)載不均衡

straggler(Some node is much more slower than others.慢節(jié)點(diǎn))

共享資源形成瓶頸等情況如何處理，例如網(wǎng)絡(luò)

部分邏輯無法并發(fā)

不可并發(fā)代碼：初始化、交互(initialization,interaction)

請(qǐng)注意，一些性能問題不容易通過擴(kuò)展來解決，例如減少單個(gè)用戶請(qǐng)求的響應(yīng)時(shí)間，以及一些算法問題，即比起增加更多的機(jī)器，倒不如聘請(qǐng)一個(gè)算法工程師使代碼運(yùn)行所占內(nèi)存更小，運(yùn)行更快。

常見的性能指標(biāo)有:系統(tǒng)的吞吐能力，指系統(tǒng)在某一時(shí)間可以處理的數(shù)據(jù)總量，通?？梢杂孟到y(tǒng)每秒處理的總的數(shù)據(jù)量來衡量；系統(tǒng)的響應(yīng)延遲，指系統(tǒng)完成某一功能需要使用的時(shí)間；系統(tǒng)的并發(fā)能力，指系統(tǒng)可以同時(shí)完成某一功能的能力，通常也用QPS(query per second)來衡量。

可擴(kuò)展性

系統(tǒng)的可擴(kuò)展性(scalability)指分布式系統(tǒng)通過擴(kuò)展集群機(jī)器規(guī)模提高系統(tǒng)性能(吞吐、延遲、并發(fā))、存儲(chǔ)容量、計(jì)算能力的特性?？蓴U(kuò)展性是分布式系統(tǒng)的特有性質(zhì)。分布式系統(tǒng)的設(shè)計(jì)初衷就是利用集群多機(jī)的能力處理單機(jī)無法解決的問題。好的分布式系統(tǒng)總在追求“線性擴(kuò)展性”,也就是使得系統(tǒng)的某一指標(biāo)可以隨著集群中的機(jī)器數(shù)量線性增長(zhǎng)。

擴(kuò)展性上訴也已經(jīng)提到過了，具象化描述一下就是我們期望2倍的計(jì)算機(jī)可以得到2倍的性能、吞吐量,常見的做法就是擴(kuò)展web服務(wù)器,當(dāng)擴(kuò)展web服務(wù)器時(shí)可以提高吞吐量,但是當(dāng)提高到20臺(tái)或更多之后,DB就會(huì)成為瓶頸,此時(shí)再擴(kuò)展web服務(wù)器也是沒有用的,所以很少有能力添加無限數(shù)量的計(jì)算機(jī),實(shí)際上很多都是加一個(gè)DB做分布式存儲(chǔ),但這很難或工作量太大。

容錯(cuò)(fault tolerance)

用于解決大問題的分布式系統(tǒng),會(huì)把非常罕見的非常真實(shí)的故障問題變?yōu)槌Ｒ姷墓收蠁栴},在一個(gè)1000臺(tái)計(jì)算機(jī)集群的系統(tǒng)中每天一定會(huì)發(fā)生錯(cuò)誤,所以處理失效的能力必須融入到系統(tǒng)設(shè)計(jì)總，我們期望從應(yīng)用程序中隱藏這些錯(cuò)誤。

我們經(jīng)常希望：

Availability(可用性):即時(shí)出錯(cuò)系統(tǒng)也可以繼續(xù)使用,利用replicated sercice可實(shí)現(xiàn)

recoverability(可恢復(fù)性):這意味著故障后什么都不做,直到有人修復(fù)了故障它可以像無故障一樣被訪問,這需要額外的工作,比如把最新的data存在磁盤故障修復(fù)后取回最新的data

在這里領(lǐng)域,最重要的方式就是(使用)非易失性存儲(chǔ)(non-volatile storage),通常是利用check-point來記錄狀態(tài)。

重要理念：

復(fù)制服務(wù)器。如果一個(gè)服務(wù)器故障了，客戶端可以使用連接別的服務(wù)器

一致性(consistency)

通用的基礎(chǔ)架構(gòu)需求定義明確的行為。例如：Get(k)獲取到的值應(yīng)該是最近的Put(k,v)設(shè)置的(這里的put是指物理上最近的機(jī)器上獲取，還是指近期獲取的緩存中獲取?)。

實(shí)現(xiàn)良好的行為是很困難的!因?yàn)椤案北尽狈?wù)器很難保持一致；客戶端可能在多步更新的中途崩潰；服務(wù)器可能會(huì)在“執(zhí)行之后回復(fù)之前”等一些尷尬的時(shí)刻崩潰；網(wǎng)絡(luò)可能會(huì)讓還存活的服務(wù)器(需要即時(shí)通信的服務(wù)器)看起來像掛掉一樣；存在“腦裂”的風(fēng)險(xiǎn)。

一致性和性能不能兼得，一致性需要溝通,如獲取最新的Put()；“強(qiáng)一致性”經(jīng)常使得系統(tǒng)緩慢(帶有嚴(yán)格同步語(yǔ)義的系統(tǒng)往往是緩慢的。)；高性能通常會(huì)給應(yīng)用程序帶來“弱一致性”。那么如何做到性能與一致性之間的設(shè)計(jì)平衡是工程師應(yīng)該研究的地方。

弱一致性:不能保證讀取到最新的更新

強(qiáng)一致性:保證能讀取到最近一次put的數(shù)據(jù),但代價(jià)很大,可以肯定的是服務(wù)器必須做大量的通信,但真正讓你陷入麻煩的地方是加入我們用副本技術(shù)(replication)來容錯(cuò),我們真的要這些副本有獨(dú)立的故障概率,例如我們把兩個(gè)副本放在同一個(gè)機(jī)房的同一個(gè)機(jī)架上,這可能是非常差的注意,若有人踢掉電源線,數(shù)據(jù)拷貝就消失了,所以為了獲得更好的容錯(cuò)能力,應(yīng)該盡可能地讓副本的故障具有獨(dú)立和不相關(guān)性,人們喜歡將副本放在盡可能遠(yuǎn)的地方,比如在不同的城市,而這又使得強(qiáng)一致性的通信代價(jià)很大,可能要等20ms或30ms才能和數(shù)據(jù)的兩個(gè)副本通信,才能確保得到最新版本。

工程師在設(shè)計(jì)一個(gè)分布式系統(tǒng)時(shí)，應(yīng)當(dāng)充分考慮到上面的要點(diǎn)，根據(jù)實(shí)際情況作出相應(yīng)的設(shè)計(jì)。

讓我們以MapReduce為例看看這個(gè)架構(gòu)如何碰到上面的這些問題，又是如何解決的，同時(shí)也是lab01的關(guān)注點(diǎn)。

MapReduce概要

背景：嚴(yán)格來講，MapReduce是一種分布式計(jì)算模型，用于解決大于1TB數(shù)據(jù)量的大數(shù)據(jù)計(jì)算處理。在TB級(jí)別的數(shù)據(jù)集上需要很多個(gè)小時(shí)才能完成計(jì)算，例如爬取網(wǎng)頁(yè)后分析其圖形結(jié)構(gòu)只有在1000臺(tái)計(jì)算機(jī)的情況下才可行，而這通常不是由分布式系統(tǒng)開發(fā)專家開發(fā)，一旦發(fā)生錯(cuò)誤就會(huì)非常痛苦。著名的開源項(xiàng)目Hadoop和Spark在計(jì)算方面都實(shí)現(xiàn)的是MapReduce模型。從論文中可以看到花了不少篇幅在講解這個(gè)模型的原理和運(yùn)行過程。

總體目標(biāo)：非分布式專家的程序員可以輕松的在合理的效率下解決的巨大的數(shù)據(jù)處理問題。程序員定義Map函數(shù)和Reduce函數(shù)、順序代碼一般都比較簡(jiǎn)單。 MR在成千的機(jī)器上面運(yùn)行處理大量的數(shù)據(jù)輸入，隱藏全部分布式的細(xì)節(jié)。

MapReduce的抽象視圖

input is divided into M files//輸入被分割成M個(gè)文件

[diagram: maps generate rows of K-V pairs, reduces consume columns]

Input1 -> Map -> a,1 b,1 c,1

Input2 -> Map -> b,1

Input3 -> Map -> a,1

             |   |   |

             |   |   -> Reduce -> c,1

             |   -----> Reduce -> b,2

              ---------> Reduce -> a,2

MapReduce實(shí)際上是分為兩個(gè)函數(shù)map,reduce:

Map(k, v):通常k是filename,v是content,v的文本會(huì)被分割成單詞,對(duì)于每個(gè)單詞w都會(huì)被發(fā)射為(w,”1”)

Reduce(k,v), k通常就是map中產(chǎn)生的單詞w,v就是”1”, emit(len(v))其實(shí)就是單詞w有多少個(gè)

shuffle:需要通過網(wǎng)絡(luò)將每一塊數(shù)據(jù)從map移動(dòng)到reduce中

  //數(shù)字是出現(xiàn)的次數(shù),Reduce是合并出現(xiàn)的次數(shù),減少key

MR calls Map() for each input file, produces set of k2,v2  

"intermediate" data

    each Map() call is a "task"

  MR gathers all intermediate v2's for a given k2,

    and passes them to a Reduce call

  final output is set of <k2,v3> pairs from Reduce()

    stored in R output files

  [diagram: MapReduce API --

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

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

例子：word count

input is thousands of text files

Map(k, v)

split v into words

for each word w

    emit(w, "1")

Reduce(k, v)

   emit(len(v))//因?yàn)槭亲址腥绻?個(gè)w,reduce后為”111”,len(v)=3

MapReduce隱藏了很多令人痛苦的細(xì)節(jié)：①start s/w on servers(在服務(wù)器上運(yùn)行軟件)②跟蹤完成了哪些任務(wù)③數(shù)據(jù)傳送④從故障中恢復(fù)。

MapReduce的模型設(shè)計(jì)很容易進(jìn)行水平橫向擴(kuò)展以加強(qiáng)系統(tǒng)的能力，基本分為兩種任務(wù)：map和reduce，通過map任務(wù)完成程序邏輯的并發(fā)，通過reduce任務(wù)完成并發(fā)結(jié)果的歸約和收集，使用這個(gè)框架的開發(fā)者的任務(wù)就是把自己的業(yè)務(wù)邏輯先分為這兩種任務(wù)，然后丟給MapReduce模型去運(yùn)行。設(shè)計(jì)上，執(zhí)行這兩種任務(wù)的worker可以運(yùn)行在普通的PC機(jī)器上，不需要使用太多資源。當(dāng)系統(tǒng)整體能力不足時(shí)，通過增加worker即可解決。

詳細(xì)說一下MapReduce的容易擴(kuò)展性質(zhì)：N臺(tái)電腦可以具有Nx的吞吐量(N臺(tái)計(jì)算機(jī)可以同時(shí)執(zhí)行nx個(gè)Map函數(shù)和Reduce函數(shù))，假設(shè)M和R大于等于N，Map函數(shù)不需要相互等待或者共享數(shù)據(jù)，完全可以并行的執(zhí)行，對(duì)于reduce而言也是一樣的。Map和reduce唯一的交互是在”shuffle”。在一定程度上，你可以通過購(gòu)買更多的計(jì)算機(jī)來獲取更大的吞吐量。而不是每個(gè)應(yīng)用程序?qū)Ｓ玫母咝Р⑿?。電腦是比程序員更便宜!

哪些將會(huì)成為性能的限制?

我們關(guān)心的就是我們需要優(yōu)化的。CPU?內(nèi)存？硬盤？網(wǎng)絡(luò)？在2004年這篇文章問世的時(shí)候回答還是”網(wǎng)絡(luò)帶寬“最受限，在論文中作者想方設(shè)法的減少數(shù)據(jù)在系統(tǒng)內(nèi)的搬運(yùn)與傳輸，請(qǐng)注意，在Map->Reduce shuffle期間所有的數(shù)據(jù)都是通過網(wǎng)絡(luò)傳輸?shù)?。論文的root交換機(jī)，1800臺(tái)機(jī)器傳輸速度在100到200千兆/秒，所有每臺(tái)機(jī)器55兆/秒，這是很小的，比當(dāng)時(shí)的磁盤霍爾RAM速度小的多。所以他們關(guān)心最小化網(wǎng)絡(luò)上的數(shù)據(jù)傳輸。而到如今數(shù)據(jù)中心的內(nèi)網(wǎng)速度要比當(dāng)時(shí)快多了，因此如今更可能的答案恐怕就是磁盤了，新的架構(gòu)會(huì)減少數(shù)據(jù)持久化到磁盤的次數(shù)，更多的利用內(nèi)存甚至網(wǎng)絡(luò)（這正是Spark的設(shè)計(jì)理念）。

更多細(xì)節(jié)(論文的Figure 1,mapreduce 2003年經(jīng)典論文):

master:給workers分配工作，記得運(yùn)行時(shí)輸出的中間結(jié)果是M個(gè)Map任務(wù)產(chǎn)生的，R個(gè)Reduce任務(wù)輸入存儲(chǔ)在GFS，每個(gè)Map輸入文件拷貝三份，全部電腦運(yùn)行GFS和MR workers，輸入的任務(wù)(分片?)遠(yuǎn)遠(yuǎn)多于worker的數(shù)量，master在每臺(tái)機(jī)器上面執(zhí)行Map任務(wù)，當(dāng)原來的任務(wù)完成之后map會(huì)處理新的任務(wù)。

Map worker將輸出按key散列映射輸出到R分區(qū)保存在本地磁盤上。

問題：有沒好的數(shù)據(jù)結(jié)構(gòu)可以實(shí)現(xiàn)這這個(gè)設(shè)計(jì)?

直到所有的Maps完成后Reduce再開始調(diào)用。

master告訴Reduce處理者們獲取從Map workers中產(chǎn)生的中間數(shù)據(jù)分區(qū)集合。Reduce workers把最終的輸出寫入GF(一個(gè)文件減少一個(gè)任務(wù))。

如何設(shè)計(jì)可以降低網(wǎng)速慢帶來的影響?

Map的輸入是從本地硬盤的GFS備份中讀取，而不要通過網(wǎng)絡(luò)來讀取。

中間數(shù)據(jù)僅在網(wǎng)絡(luò)中傳輸一次。Map worker將數(shù)據(jù)寫入本地磁盤,而不是GFS。

中間數(shù)據(jù)通過key被劃分到多個(gè)文件，”大網(wǎng)絡(luò)傳輸“更加有效。Question:為什么不將records以stream形式傳輸?shù)絩educer（通過TCP），因?yàn)樗鼈兪怯蒻appers生成的?

參考論文3.4節(jié)減少網(wǎng)絡(luò)帶寬資源的浪費(fèi)，都盡量讓輸入數(shù)據(jù)保存在構(gòu)成集群機(jī)器的本地硬盤上，并通過使用分布式文件系統(tǒng)GFS進(jìn)行本地磁盤的管理。嘗試分配map任務(wù)到盡量靠近這個(gè)任務(wù)的輸入數(shù)據(jù)庫(kù)的機(jī)器上執(zhí)行，這樣從GFS讀時(shí)大部分還是在本地磁盤讀出來。中間數(shù)據(jù)傳輸（map到reduce）經(jīng)過網(wǎng)絡(luò)一次，但是分多個(gè)key并行執(zhí)行

他們是如何處理好負(fù)載均衡問題?

吞吐量是關(guān)鍵(Critical to scaling):某個(gè)task運(yùn)行時(shí)間比較其他N-1個(gè)都長(zhǎng)，大家都必須等其結(jié)束那就尷尬了，因此參考論文3.5節(jié)、3.6節(jié)系統(tǒng)設(shè)計(jì)保證task比worker數(shù)量要多，做的快的worker可以繼續(xù)先執(zhí)行其他task，減少等待。（框架的任務(wù)調(diào)度后來發(fā)現(xiàn)更值得研究），但是有些reduce可能就是比其他任務(wù)需要更長(zhǎng)的時(shí)間。

[diagram: packing variable-length tasks into workers]

比worker多的多的任務(wù)的解決方案:

1.Master不斷的將新的任務(wù)分配給那些已經(jīng)完成之前任務(wù)的worker。

2.希望沒有任何一個(gè)任務(wù)是超級(jí)巨大以至于被其控制了(影響)完成時(shí)間。

3.同時(shí)速度更快的服務(wù)器將會(huì)處理更多的工作，最后一起完成。

what about fault tolerance?

即如果服務(wù)器在MR job期間崩潰了怎么辦?參考論文3.3節(jié)重新執(zhí)行那些失敗的MR任務(wù)即可，因此需要保證MR任務(wù)本身是冪等且無狀態(tài)的。隱藏失敗對(duì)于編程的易寫性是很重要的一部分。

Question:為什么不重新開始整個(gè)job呢?

MR僅重新運(yùn)行那些失敗的Map和Reduce任務(wù)。MR需要他們是一些純粹的函數(shù):①它們不用在調(diào)用過程中保持狀態(tài)②除了MR的inputs/outputs，它們不用讀或者寫文件③任務(wù)之間沒有隱藏的交流。

與其他并行編程方案相比，對(duì)純粹函數(shù)的要求是MR的一個(gè)主要限制。但這對(duì)MR的簡(jiǎn)單性至關(guān)重要。

Details of worker crash recovery(MR怎么應(yīng)對(duì)worker崩潰)

Map Worker崩潰：

master看到worker不再對(duì)pings響應(yīng)時(shí)就知道work崩潰了。已崩潰的Map workers產(chǎn)生的中間數(shù)據(jù)已丟失，但是每個(gè)Reduce任務(wù)都可能會(huì)需要它。

基于GFS的其他副本的輸入輸出傳播任務(wù)master重新執(zhí)行。

有些Reduce workers也許在讀取中間數(shù)據(jù)的時(shí)候就已經(jīng)失敗，我們依賴于功能和確定性的Map函數(shù)。

如果Reduces已經(jīng)獲取全部的中間數(shù)據(jù)，那么master不需要重啟Map函數(shù)；如果Reduce崩潰那么必須等待Map再次運(yùn)行。Reduce worker在輸出結(jié)果前崩潰,master必須在其他worker上面重新開始該任務(wù)。

Reduce worker crashes:

完成的任務(wù)可以存儲(chǔ)在GFS中(帶有副本)。

master將未完成的任務(wù)交給其他的workers。

Reduce worker在輸出結(jié)果的過程中崩潰：

GFS會(huì)自動(dòng)重命名輸出，然后使其保持不可見直到Reduce完成，所以master在其他地方再次運(yùn)行Reduce worker將會(huì)是安全的。

其他錯(cuò)誤/問題:

如果master分配給兩個(gè)worker同樣的Map()任務(wù)怎么辦?

也許master錯(cuò)誤的認(rèn)為另一個(gè)worker掛掉了。

僅會(huì)告訴Reduce workers其中的一個(gè)。

如果master分配給兩個(gè)worker相同的Reduce()任務(wù)怎么辦?

他們將會(huì)嘗試將同樣的輸出文件寫入到GFS中！GFS的文件名不會(huì)重名，一個(gè)完整的文件將會(huì)被看到。

如果單個(gè)master非常慢--一個(gè)“散兵游勇”的計(jì)算機(jī)怎么辦?

可能是因?yàn)闄C(jī)器的硬件不行了。master開始最后幾個(gè)未完成任務(wù)的副本。

如果worker計(jì)算的結(jié)果是不正確的，是因?yàn)檐浖€是硬件問題?

MR assumes “fail-stop” cpus and software

如果master崩潰了怎么辦?

從check-point恢復(fù)或者放棄任務(wù)。

那些應(yīng)用程序不適合用MapReduce

不是所有的任務(wù)都適合使用map/shuffle/reduce的模式。

小數(shù)據(jù)，因?yàn)楣芾沓杀咎撸绶蔷W(wǎng)站后端。

大數(shù)據(jù)中的小更新，比如添加一些document到大的索引。

不可預(yù)知的讀(Map和Reduce都不能選擇輸入)。

Multiple shuffles, e.g. page-rank (can use multiple MR but not very efficient)。

多數(shù)靈活的系統(tǒng)允許MR，但是使用非常復(fù)雜的模型。

現(xiàn)實(shí)世界的互聯(lián)網(wǎng)公司是如何使用MapReduce的?

一家運(yùn)營(yíng)貓的社交網(wǎng)絡(luò)互聯(lián)網(wǎng)企業(yè)需要這樣做：

1.建立一個(gè)搜索索引，以便用戶能夠檢索到其他人養(yǎng)的貓。

2.分析不同貓的受歡迎程度，決定廣告價(jià)值。

3.檢測(cè)狗，并刪除它們的檔案。

可以將MapReduce用于所有這些目的！--每天晚上對(duì)所有配置文件運(yùn)行大量批處理作業(yè)

1.建立倒序索引，讓用戶可以檢索到其他用戶的貓

2.統(tǒng)計(jì)主頁(yè)瀏覽次數(shù)：map(web logs) -> (cat_id, "1")

reduce(cat_id, list("1")) -> list(cat_id, count)

3.過濾檔案:map(profile image) -> img analysis -> (cat_id, "dog!")

reduce(cat_id, list("dog!")) -> list(cat_id)

結(jié)論

因?yàn)镸apReduce的出現(xiàn)而使得計(jì)算機(jī)集群技術(shù)流行起來。但MR不是最有效或者最靈活的，但它具有良好的擴(kuò)展性，并且易于編程，并且對(duì)開發(fā)者隱去了數(shù)據(jù)傳輸和容錯(cuò)的麻煩。其實(shí)還有部分工程問題，這篇文章中并沒有討論，可能因?yàn)檫@些更偏重工程實(shí)踐，比如：task任務(wù)的狀態(tài)如何監(jiān)控、數(shù)據(jù)如何移動(dòng)、worker故障后如何恢復(fù)等。

最后總結(jié)一下MapReduce，這是個(gè)非常成功的分布式系統(tǒng)模型設(shè)計(jì)，盡管它可能不是某個(gè)問題的最佳解決方案，但是它是最通用化的解決方法（有點(diǎn)類似集裝箱，不一定可以裝最多，但是最容易標(biāo)準(zhǔn)化）。利用它你可以很輕松的將程序的邏輯進(jìn)行標(biāo)準(zhǔn)化并放到多節(jié)點(diǎn)上并行執(zhí)行。這種標(biāo)準(zhǔn)化模型的橫向擴(kuò)展性很強(qiáng)，同時(shí)因?yàn)闃?biāo)準(zhǔn)化也解決了分布式系統(tǒng)中需要處理的種種問題，成功簡(jiǎn)化了分布式應(yīng)用的開發(fā)，使得大數(shù)據(jù)處理程序得以工業(yè)級(jí)流水線生產(chǎn)，普通開發(fā)人員即可勝任，可謂是開啟大數(shù)據(jù)時(shí)代的發(fā)明。它在工程設(shè)計(jì)上各個(gè)特性的取舍實(shí)踐也很有學(xué)習(xí)的價(jià)值。我將在后續(xù)看到更高級(jí)的繼任者。