MIT 6.824學習指南(1)

這篇筆記針對的是Spring 2018課程

1. 課程名稱是分散式系統工程，所以要有一定的工程功底
2. 課程使用語言是go, 所以要先下載go並且熟悉基本語法
3. 課程有Spring 2015的公開課視頻，可以看 YouTube觀看地址
4. 可以提前閱讀一些書籍， 推薦Distributed systems for fun and profit

Lecture 1: Introduction

分散式系統工程

什麼是分散式系統?

• 多個協同的計算機
• 大型網站的儲存，MapReduce, 點對點的分享，諸如此類
• 很多關鍵的基礎設施都是分散式的

為什麼要分散式

• 組織物理上獨立的實體
• 通過隔離實現安全
• 通過複製來容錯
• 通過並行的 cpu/內存/磁碟/網路來擴展吞吐量

但是

• 複雜性： 有很多並發的組件
• 必須處理部分的失敗
• 達到較好的性能很棘手

為什麼要參加這門課?

• 感興趣 -- 難題，強大的解決方案
• 實際系統使用 -- 拜日益龐大的網站所賜
• 活躍的研究區域 -- 很多在解決中+ 一大堆未解決的問題
• 實際操作 -- 你會在試驗中構造嚴謹的系統

課程組成

• 講課
• 閱讀
• 兩次考試
• 實驗
• 最終項目(可選的)
• 。。。

講課

想法，論文討論，實驗

閱讀

• 研究論文，一些是經典的，一些是新的
• 論文闡述了關鍵思想和重要細節
• 許多課程圍繞論文
• 請在課前閱讀論文
• 每篇論文都有個小問題等待你回答
• 每篇論文同樣也要提出一個問題
• 在前一天午夜提交問題和答案

考試

• 期中考試
• 最後一周的期末考試

實驗目標

• 深度理解一些重要的技術
• 分散式編程的經驗

實驗列表

1. MapReduce
2. 使用Raft來實現基於複製的容錯
3. 容錯的KV儲存
4. 分布的KV儲存

關注主題

這是一門關於基礎設施的課程，供應用程序使用。

應用程序中隱藏的分散式抽象如下：

• 儲存
• 通信
• 計算

有幾個話題會被反覆提到。

實現

RPC， 多線程， 並發控制

性能

期望：可伸縮的吞吐

• N個服務端 -> 通過並行的CPU/磁碟/網路實現N被的吞吐。
• 可以僅通過增加機器來實現更多負載

隨著N的增長，伸縮變得更加困難：

• 負載不均衡(原文： Load im-balance, stragglers 不知道該怎麼翻譯)
• 不能並行化的代碼：初始化，交互
• 共享資源的瓶頸, 例如網路

記住一些性能問題不能輕易的通過縮放來解決

• 例如降低單個用戶請求的響應時間
• 可能需要程序員的努力而不僅只是增加更多機器

容錯

1000+的伺服器，複雜的網路 -> 總是有壞掉的

我們希望在應用端隱藏這些錯誤

我們經常想要：

• 可用性 - 及時出現了錯誤，應用程序也可以繼續運行
• 持久性 - 當錯誤被修復時，應用程序可以恢復正常

一致性

通用組件需要定義良好的行為，例如

Get(k)會返回之前Put(K,V)中的值

實現好的行為是很難的

• 複製的服務端很難保持一致
• 客戶端可能在多步驟的更新過程中出錯
• 服務端可能在不變的時候出錯，例如在執行之後但沒有得到響應的時間點
• 網路可能使的存活的服務端看起來失活了。存在『腦裂』的問題。

一致性和性能是敵人

• 一致性要求通信，例如獲得最後一次Put()
• 強一致性通常導致緩慢的系統
• 應用端通常強制弱一致性來保證高性能

人們已經在這一領域中追求了許多設計要點

學習案例: MapReduce

我們將會使用MapReduce作為學習案例，MapReuce是6.824課程主要課題的一個很好例子，同時也是實驗1的重點

MapReduce一覽

內容：在TB級別大小的數據集上進行數個小時的計算

• 例如分析爬取網頁的圖結構
• 只有1000多台電腦才有實用價值(only practical with 1000s of computers)
• 通常不是由分散式系統專家開發的
• 分散式實現起來很痛苦，例如應對失敗

總體目標：非專業程序員可以輕鬆拆分

• 以合理的效率在許多伺服器上處理數據

程序員定義Map和Reduce函數

• 順序的代碼; 通常相當簡單

MapReduce在具有大量輸入的1000多台機器上運行這些功能，並隱藏了分配細節

MapReduce的抽象視圖

輸入分割到M份文件

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

MapReudce對於每一個輸入文件調用Map()函數， 產生輸出集k2,v2

• 中間數據
• 每一個Map()調用被稱為一個任務

對於給定的k2，MapReduce收集所有的中間結果v2並且將其傳遞給Reduce調用

最終的輸出是來自Reduce()函數的(k2,v3)的鍵值對集合，儲存在R份輸出文件里

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

示例： 單詞計數

輸入是數千份文本文件

Map(k, v) split v into words for each word w emit(w, "1") Reduce(k, v) emit(len(v))

MapReduce隱藏了許多痛苦的細節

• 在服務端啟動s/w
• 跟蹤哪些任務完成了
• 數據移動
• 從失敗中恢復

MapReduce伸縮性很好

N台計算機可以給你N倍的吞吐

• 假設M和R>=N (即大量的輸入文件和映射輸出的key)
• Map()可以並行運行，因為它們不會相互作用
• Reduce()函數也是一樣
• 唯一的交互是通過在map和reduce中間"洗牌"

所以你可以通過購買更多的計算機來獲得更多的吞吐量

• 而不是每個程序專門的高效並行
• 計算機比程序員要便宜

哪些可能會限制性能？

我們需要關心這些來優化

CPU？內存？硬碟？網路？

在2004年作者被網路帶寬(network cross-section bandwidth)限制

• 在Map->Reduce交換的時候，所有的數據都需要通過網路
• 論文中的根交換器：100到200Gbit每秒
• 1800台機器，平均55Mbit每秒每台機器
• 很小，遠小於硬碟(當時大約50-100MB/s)或者內存速度

所以他們關心最小化通過網路的數據移動。(數據中心的網路現在已經快很多了)

更多細節(論文中的圖片1)

master:分配任務給workers;記住中間輸出是M份map任務，R份reduce任務

輸入儲存在GFS中，每個Map輸入文件將會複製三份

所有的計算機同時運行GFS和MapReduce workers;

輸入任務遠大於workers數量。

master分配個每個worker一個map任務，前一個任務完成時提交一個新的任務

Map worker在本地磁碟通過hash中間key來切分成R份

問題：實現這一目標有什麼好的數據結構？

在所有的Map任務完成成Reduce將不會被調用

master通知Reduce從Map workers處獲得中間數據

Reduce worker會將最終輸出寫入到GFS(每一個Reduce任務一個文件)

減少緩慢網路的影響的設計細節是怎麼樣的？

Map的輸入是通過讀取GFS在本地硬碟上的副本，而不是通過網路

中間數據只會通過網路傳輸一次

• Map worker將會寫在本地硬碟而不是GFS

中間數據被許多key分成文件(Intermediate data partitioned into files holding many keys.)

• 問題：為什麼不通過流式傳輸(通過TCP)將mapper產生的數據給reducer

他們如何獲得一個好的負載均衡

縮放至關重要 -- N-1的服務端在等待1個完成是非常查的

但是其中一些任務可能比其他任務花費更長時間。

解決方案：任務要遠大於workers

• master會將新的任務提交給那些已經完成前一個任務的
• 所以沒有一個任務大到支配完成時間(期望)
• 所以更快的伺服器會比慢的伺服器完成更多工作，但在同樣長的時間內結束

關於容錯

假如一個伺服器在處理MapReduce的過程中宕機了怎麼辦？

隱藏失敗是編程的一個重要部分

問題: 為什麼不從一開始就重新開始整個工作

MapReduce會重新運行失敗的Map()和Reduce()任務

MapReuce要求他們是純函數:

• 他們在調用過程中不儲存狀態
• 除了MapReduce的輸入/輸出文件外，他們不讀寫任何文件。
• 他們在整個任務中通信是透明的

所以重新執行將會返回統一的輸入結果

與其他並行編程框架相比，純函數的要求是一個主要限制。MapReduce的簡單性至關重要。

worker的崩潰恢復細節

Map Worker崩潰了

master通過ping發現worker很長時間沒有響應了

崩潰的worker的中間map輸入結果丟失了，但是每一個Reduce任務都需要這個輸出

master重新運行，通過其他的GFS的副本輸入來切分任務。

一些Reducer可能已經讀取了失敗的worker的中間數據。這裡我們依賴功能性和確定性的Map()

假如Reducer已經收到了所有的中間數據，master就不需要重新運行Map。之後如果Reduce崩潰了將會強制重新運行失敗的Map

Reduce worker崩潰了

已經完成任務的沒關係 -- 已經儲存在GFS並且有副本

master將會在其他worker上重啟沒有完成的任務

Reduce worker在寫入輸出的中間崩潰了

GFS具有原子重命名功能，可防止輸出在完成之前可見。

所以master在其他地方重新運行Reduce任務是安全的。

其他的失敗/問題

假如master分配兩個worker同一個的Map()任務怎麼辦？

可能master錯誤的任務其中一個worker已經掛了。

他將會通知Reduce worker其中一個。

假如master分配兩個worker同一個Reduce()任務怎麼辦？

他們將會同時嘗試些GFS上面的同一份輸出文件。

原子的GFS重命名將會防止混合。只有一個完成的文件會看得見。

假如一個worker非常慢怎麼辦？

也許是由於硬體的問題。

master啟動前幾個任務的第二個副本。

假如由於失效的h/w或者s/w導致一個worker計算了錯誤的輸出怎麼辦？

太糟糕了！MapReduce假設錯誤不會出現在CPU和軟體層面

假如master崩潰了怎麼辦？

從檢查點恢復，或者放棄任務

怎麼樣的程序不能在MapReduce上運行良好

不是所有的都適應map/shuffle/reduce這個模式

小數據，因為開銷很高。 例如， 不是網站後台

在大數據上的小更新，例如 將一些文件添加到大型索引中

不可預知的讀取（Map和Reduce都不能選擇輸入）

多次洗牌，例如 page-rank（可以使用多個MR，但效率不高),

更靈活的系統允許這些，但需要更複雜的模型。

現實中網路公司會怎麼使用MapReduce？

待續

結論

MapReduce簡單的處理方式使得大集群的計算流行了

• 不是最有效或者靈活的
• 伸縮性很好
• 編程雞蛋 -- 錯誤和數據移動被隱藏了

在實踐中權衡的很好

我們稍後在課程中會看到一些更高級的接班人。

實驗快樂！