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

• 多個(gè)計(jì)算機(jī)進(jìn)行協(xié)作
• 大規(guī)模數(shù)據(jù)庫(kù)，P2P文件共享，MR，DNS等等
• 許多重要的基礎(chǔ)設(shè)施是分布式的

為什么要使用分布式？

• 連接物理隔離的實(shí)體
• 通過(guò)隔離取得安全性
• 通過(guò)副本機(jī)制容忍故障
• 可水平擴(kuò)展資源提高生產(chǎn)力

實(shí)現(xiàn)中的困難？

• 許多并發(fā)問(wèn)題
• 處理局部故障
• 難以實(shí)現(xiàn)理論性能

主題

關(guān)于分布式程序背后的三大抽象方面：

• 存儲(chǔ)
• 通信
• 計(jì)算

話題：實(shí)現(xiàn)

RPC ，threads，concurrency control

話題：性能

目標(biāo)：可伸縮的吞吐量，n臺(tái)服務(wù)器提供對(duì)應(yīng)n臺(tái)對(duì)應(yīng)的性能總量（cpu，disk，net）
困難點(diǎn): 難以實(shí)現(xiàn)線性提升至N倍，原因如下：

1.負(fù)載均衡， stragglers（可能是負(fù)載過(guò)高的某一節(jié)點(diǎn)）
2.非平行化的代碼： 初始化關(guān)系，或有相互作用
3.由于共享資源產(chǎn)生瓶頸：例如網(wǎng)絡(luò)

話題：故障容忍

當(dāng)集群的規(guī)模很大，網(wǎng)絡(luò)結(jié)構(gòu)很復(fù)雜時(shí)，總會(huì)有一些節(jié)點(diǎn)故障，而我們需要讓應(yīng)用能夠隱藏這些故障，通常需要：
1.可用性：整個(gè)集群仍可提供服務(wù)，使用存儲(chǔ)的數(shù)據(jù)
2.耐久性：當(dāng)故障節(jié)點(diǎn)恢復(fù)時(shí)，相關(guān)的數(shù)據(jù)也會(huì)隨之恢復(fù)

一個(gè)好的解決方案： 冗余的服務(wù)。當(dāng)一個(gè)實(shí)例崩潰時(shí)，客戶端可執(zhí)行另一個(gè)副本實(shí)例

話題：一致性

通用的基礎(chǔ)架構(gòu)需要提供明確的行為，例如Get操作產(chǎn)生的值要來(lái)自于最近的Put操作，但是達(dá)到這樣好的行為時(shí)困難的。
冗余的（副本）服務(wù)之間很難保證(eg.數(shù)據(jù))完全相同，如：

1.客戶端可能中途崩潰在由多步組成的更新操作
2.服務(wù)端可能崩潰在一個(gè)“尷尬”點(diǎn)：例如在計(jì)算完成和上報(bào)結(jié)果之間
3.網(wǎng)絡(luò)可能使活著的服務(wù)看起來(lái)是故障的.嚴(yán)重"腦裂"問(wèn)題

一致性和性能是矛盾的，達(dá)到一致性需要進(jìn)行通信（例如去獲得最近的put操作值）。
強(qiáng)一致往往使得服務(wù)變慢
高性能得服務(wù)通常是弱一致
人們?cè)谶@個(gè)領(lǐng)域追求很多設(shè)計(jì)點(diǎn)

案例分析 MapReduce

綜述

設(shè)計(jì)背景：對(duì)上TB得數(shù)據(jù)集進(jìn)行多個(gè)小時(shí)的計(jì)算獲取結(jié)果，然而這通常需要一定規(guī)模的服務(wù)器集群進(jìn)行處理，進(jìn)而需要分布式編程，但通常分布式編程需要考慮很多問(wèn)題，是很困難的。
總體目標(biāo)：使非專業(yè)的程序員能夠很容易的處理分離在多臺(tái)機(jī)器上的數(shù)據(jù)并達(dá)到可接受的效率，程序員來(lái)編寫Map和Reduce函數(shù)，而順序執(zhí)行的代碼通常是相當(dāng)簡(jiǎn)單的。
MR將上文中的Map Reduce函數(shù)“同時(shí)”運(yùn)行在上千臺(tái)具有大量輸入的機(jī)器上，并且隱藏背后的分布式細(xì)節(jié)

抽象展示mapreduce

  Input1 -> Map -> a,1 b,1 c,1
  Input2 -> Map ->     b,1
  Input3 -> Map -> a,1     c,1
                    |   |   |
                        |   -> Reduce -> a,2 c,2
                        -----> Reduce -> b,2
                   

M是分配Map任務(wù)的數(shù)量，R是分配Reduce任務(wù)數(shù)量
整體輸入被劃分成了M份并分別輸入給各map任務(wù)，map函數(shù)執(zhí)行后會(huì)生成<k2,v2>值（由程序指定），稱之為“中間值”，并對(duì)k2進(jìn)行hash（size=R）寫入指定的文件中，MR程序會(huì)讓各Reduce程序去拉去對(duì)應(yīng)自己hash值的文件（相同的k2值會(huì)發(fā)送給同一個(gè)reduce任務(wù)），進(jìn)行reduce作業(yè)后生成最終的結(jié)果<k2,k3>。這些結(jié)果reduce直接寫入自己的reduce結(jié)果文件中（共R份結(jié)果）

例子：?jiǎn)卧~統(tǒng)計(jì)

  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))

mapreduce隱藏許多困難的細(xì)節(jié)問(wèn)題：

• 在服務(wù)器上啟動(dòng)軟件
• 追蹤具體任務(wù)的完成情況
• 數(shù)據(jù)傳輸
• 從故障中恢復(fù)

Mapreduce 擴(kuò)展性很好：

N倍的計(jì)算機(jī)給你提供N倍的吞吐力：

• 假定M和R的數(shù)量大于等于N，Maps（）因?yàn)槿蝿?wù)之間沒(méi)有互相影響所以能夠平行化，Reduce()也相同
• 所以你可以購(gòu)買更多的機(jī)器提高更大的吞吐，而不是通過(guò)高效平行化編程提高指定應(yīng)用性能（機(jī)器要比程序員更便宜）

什么會(huì)限制性能表現(xiàn)：

我們會(huì)關(guān)心幾個(gè)方面去優(yōu)化
CPU 內(nèi)存 磁盤 網(wǎng)絡(luò)
在2004年的論文中，限制主要存在于跨域網(wǎng)絡(luò)帶寬：
在Map->Reduce的Shuffle階段數(shù)據(jù)是會(huì)通過(guò)網(wǎng)絡(luò)傳輸，論文中的主交換機(jī)是100-200GB的帶寬，總共1800臺(tái)服務(wù)器 所以每個(gè)機(jī)器只有55MB的帶寬，這要比磁盤或者內(nèi)存的速度慢的多。

所以他們關(guān)注在網(wǎng)絡(luò)中數(shù)據(jù)的最小化移動(dòng)。（當(dāng)前的數(shù)據(jù)中心已經(jīng)比那時(shí)快的多了）

工作流程：

figure 1

• master：指派任務(wù)給worker，記錄中間值的位置
• M個(gè)Map任務(wù)，R個(gè)Reduce任務(wù)
• 每個(gè)服務(wù)器運(yùn)行MR的owrker和GFS，每個(gè)Map的輸入文件由3個(gè)副本
• 通常輸入的任務(wù)大于總worker數(shù)，老的Map執(zhí)行后，該worker繼續(xù)執(zhí)行新的task
• Map的worker 對(duì)中間值的key進(jìn)行hash寫入到R個(gè)partitions（worker的本地磁盤），直到所有的map任務(wù)結(jié)束后reduce操作開(kāi)始
• master告知reduce worker從指定的map worker獲取中間數(shù)據(jù)
• reduce worker將最終的結(jié)果值寫入GFS（每個(gè)reduce worker一個(gè)結(jié)果文件）

如何設(shè)計(jì)使得緩解慢網(wǎng)絡(luò)的影響？

• Map的輸入從GFS的副本中讀取，這通常是在本地磁盤而不是通過(guò)網(wǎng)絡(luò)拉取
• 中間數(shù)據(jù)只在網(wǎng)絡(luò)中傳輸一次，map的會(huì)將中間結(jié)果寫在本地磁盤而不是GFS中
• 許多key的中間結(jié)果存在同一個(gè)partition文件中，因?yàn)榇笪募鬏斝矢?/li>

如何取得好的負(fù)載均衡

關(guān)鍵點(diǎn): N-1個(gè)服務(wù)可能在等待1個(gè)worker完成，而有的任務(wù)可能會(huì)比其他任務(wù)完成的慢

解決方案：將任務(wù)拆分，使得總?cè)蝿?wù)數(shù)大于workers數(shù)量
master將新任務(wù)交給剛完成了任務(wù)的worker，這樣使得每個(gè)任務(wù)都比較小不會(huì)占用相對(duì)太長(zhǎng)的時(shí)間，性能強(qiáng)勁的worker會(huì)處理更多的任務(wù)

如何容錯(cuò)？

隱含解決故障問(wèn)題會(huì)使編程更加容易
MR會(huì)重啟失敗了的map或是reduce任務(wù)，而不是整體重啟
因?yàn)檫@些任務(wù)都是純函數(shù)的：

• 他們不會(huì)在調(diào)用過(guò)程中保存狀態(tài)
• 他們不會(huì)讀或?qū)慚R規(guī)定以外的文件
• 這些任務(wù)之間沒(méi)有隱藏的通信

所以重新調(diào)用這些任務(wù)會(huì)得到相同的結(jié)果
這也是MR相對(duì)于其他的平行化編程模型的最大限制，但這也保證了MR的簡(jiǎn)單性

故障恢復(fù)細(xì)節(jié)

Map Worker:
當(dāng)master接收不到某worker的ping結(jié)果時(shí)，該worker可能崩潰了，他的中間結(jié)果可能已經(jīng)丟失，而很多reduce任務(wù)可能需要這些數(shù)據(jù)。master會(huì)重新執(zhí)行這個(gè)任務(wù)在這份輸入文件的其他GFS副本worker上。
有時(shí)reduce操作在該map worker崩潰前已經(jīng)讀完了他生成的中間結(jié)果，所以會(huì)在重啟該map任務(wù)，除非這個(gè)reduce也發(fā)生了故障

Reduce Worker：
完成的reduce任務(wù)會(huì)將結(jié)果存儲(chǔ)在GFS中，如果某個(gè)reduce失敗則只需要重新啟動(dòng)這個(gè)reduce任務(wù)在其他的worker上。GFS會(huì)保證輸出結(jié)果在完成前時(shí)不可見(jiàn)的，當(dāng)完成后原子性的重命名該文件。所以master時(shí)很安全的重啟reduce任務(wù)，無(wú)論在那個(gè)worker上

其他一些關(guān)于故障的問(wèn)題？

如果master啟動(dòng)了兩個(gè)相同的Map（）任務(wù)？

可能由于master誤判了一個(gè)map失敗，但reduce worker只會(huì)得到其中一個(gè)中間結(jié)果

如果master啟動(dòng)了兩個(gè)相同reduce任務(wù)？

他們可能會(huì)嘗試寫入“相同的一個(gè)結(jié)果文件”，由GFS的原子性保證只有一個(gè)完成結(jié)果會(huì)被重命名成最終結(jié)果文件

如何解決某個(gè)非常慢的任務(wù)---straggler問(wèn)題？

master會(huì)為最后的一些任務(wù)啟動(dòng)第二個(gè)副本task共同執(zhí)行

如何解決由于硬件或軟件導(dǎo)致的錯(cuò)誤結(jié)果？

MR會(huì)采取失敗停止，終止整個(gè)任務(wù)告知用戶

什么樣的應(yīng)用不適合MR？

不是所有的任務(wù)都適合 map/suffle/reduce 這樣的模式

• 數(shù)據(jù)量較小
• 對(duì)大數(shù)據(jù)集進(jìn)行非常小的更新操作
• 不可預(yù)期的讀內(nèi)容
• 需要多個(gè)shuffles階段

總結(jié)：

Mapreduce 通常用于一個(gè)大規(guī)模的集群

• 并不總是很高效或靈活
• 擴(kuò)展性很好
• 很容易去編程（隱藏了很多分布式問(wèn)題）

他是生產(chǎn)中進(jìn)行很好的折中產(chǎn)物