6.824-1-Introduction

分布式系統

結合視訊和知乎的翻譯做的筆記，不保證原創性，隻為了記錄。

概要

分布式系統的核心是通過網絡來協調，共同完成一緻任務的一些計算機。我們在本課程中将會重點介紹一些案例，包括：大型網站的儲存系統、大資料運算，如 MapReduce、以及一些更為奇妙的技術，比如點對點的檔案共享。這是我們學習過程中的一些例子。分布式計算之是以如此重要的原因是，許多重要的基礎設施都是在它之上建立的，它們需要多台計算機或者說本質上需要多台實體隔離的計算機。

如果你可以在一台計算機上解決，而不需要分布式系統，那你就應該用一台計算機解決問題。在選擇使用分布式系統解決問題前，你應該要充分嘗試别的思路

人們使用大量的互相協作的計算機驅動力是：

• 人們需要獲得更高的計算性能。可以這麼了解這一點，（大量的計算機意味着）大量的并行運算，大量CPU、大量記憶體、以及大量磁盤在并行的運作。
• 另一個人們建構分布式系統的原因是，它可以提供容錯（tolerate faults）。比如兩台計算機運作完全相同的任務，其中一台發生故障，可以切換到另一台。
• 第三個原因是，一些問題天然在空間上是分布的。例如銀行轉賬，我們假設銀行A在紐約有一台伺服器，銀行B在倫敦有一台伺服器，這就需要一種兩者之間協調的方法。是以，有一些天然的原因導緻系統是實體分布的。
• 最後一個原因是，人們建構分布式系統來達成一些安全的目标。比如有一些代碼并不被信任，但是你又需要和它進行互動，這些代碼不會立即表現的惡意或者出現bug。你不會想要信任這些代碼，是以你或許想要将代碼分散在多處運作，這樣你的代碼在另一台計算機運作，我的代碼在我的計算機上運作，我們通過一些特定的網絡協定通信。是以，我們可能會擔心安全問題，我們把系統分成多個的計算機，這樣可以限制出錯域。

這門課程中，主要會讨論前兩點：性能和容錯。剩下兩點我們會通過對某些案例的研究來學習。

• 因為系統中存在很多部分，這些部分又在并發執行，你會遇到并發程式設計和各種複雜互動所帶來的問題，以及時間依賴的問題（比如同步，異步）。這讓分布式系統變得很難。
• 另一個導緻分布式系統很難的原因是，分布式系統有多個組成部分，再加上計算機網絡，你會會遇到一些意想不到的故障。如果你隻有一台計算機，那麼它通常要麼是工作，要麼是故障或者沒電，總的來說，要麼是在工作，要麼是沒有工作。而由多台計算機組成的分布式系統，可能會有一部分元件在工作，而另一部分元件停止運作，或者這些計算機都在正常運作，但是網絡中斷了或者不穩定。是以，局部錯誤也是分布式系統很難的原因。
• 最後一個導緻分布式系統很難的原因是，人們設計分布式系統的根本原因通常是為了獲得更高的性能，比如說一千台計算機或者一千個磁盤臂達到的性能。但是實際上一千台機器到底有多少性能是一個棘手的問題，這裡有很多難點。是以通常需要倍加小心地設計才能讓系統實際達到你期望的性能。

實驗組成部分

• MapReduce
• Raft
  • 這是一個理論上通過複制來讓系統容錯的算法，具體是通過複制和出現故障時自動切換來實作
• KV server
  • 需要使用你的Raft算法實作來建立一個可以容錯的KV服務
• 分片式KV服務-sharded key value service sharding
  • 需要把你寫的KV伺服器分發到一系列的獨立叢集中，這樣你會切分你的KV服務，并通過運作這些獨立的副本叢集進行加速。同時，你也要負責将不同的資料塊在不同的伺服器之間搬遷，并確定資料完整。這裡我們通常稱之為分片式KV服務。分片是指我們将資料在多個伺服器上做了分區，來實作并行的加速。

分布式系統的抽象和實作工具（Abstraction and Implementation）

這門課程是有關應用的基礎架構的。是以，貫穿整個課程，我會以分離的方式介紹：第三方的應用程式，和這些應用程式所基于的，我們課程中主要介紹的一些基礎架構。基礎架構的類型主要是存儲，通信（網絡）和計算。

最關注的是存儲，因為這是一個定義明确且有用的抽象概念，并且通常比較直覺。人們知道如何建構和使用儲存系統，知道如何去建構一種多副本，容錯的，高性能分布式存儲實作。

讓使用者認為這個分布式上不是一個分布式。

（讓使用者認為一個多線程的使用者是一個單線程的任務）

RPC，Threads，concurrent，

• RPC（Remote Procedure Call）。RPC的目标就是掩蓋我們正在不可靠網絡上通信的事實。
• 另一個我們會經常看到的實作相關的内容就是線程。這是一種程式設計技術，使得我們可以利用多核心計算機。對于本課程而言，更重要的是，線程提供了一種結構化的并發操作方式，這樣，從程式員角度來說可以簡化并發操作。
• 因為我們會經常用到線程，我們需要在實作的層面上，花費一定的時間來考慮并發控制，比如鎖。

可擴充性（Scalability）

另一個就是性能。

建構分布式系統的目的是為了擷取人們常常提到的可擴充的加速。是以，我們這裡追求的是可擴充性（Scalability）。而我這裡說的可擴充或者可擴充性指的是，如果我用一台計算機解決了一些問題，當我買了第二台計算機，我隻需要一半的時間就可以解決這些問題，或者說每分鐘可以解決兩倍數量的問題。兩台計算機構成的系統如果有兩倍性能或者吞吐，就是可擴充性。

當你隻有1-2個使用者時，一台計算機就可以運作web伺服器和資料，或者一台計算機運作web伺服器，一台計算機運作資料庫。但是有可能你的網站一夜之間就火了起來，你發現可能有一億人要登入你的網站。你該怎麼修改你的網站，使它能夠在一台計算機上支援一億個使用者？你可以花費大量時間極緻優化你的網站，但是很顯然你沒有那個時間。是以，為了提升性能，你要做的第一件事情就是購買更多的伺服器，然後把不同使用者分到不同伺服器上。這樣，一部分使用者可以去通路第一台web伺服器，另一部分去通路第二台web伺服器。所有的使用者最終都需要看到相同的資料。是以，所有的web伺服器都與後端資料庫通信。這樣，很長一段時間你都可以通過添加web伺服器來并行的提高web伺服器的代碼效率。

很可能在某個時間點你有了10台，20台，甚至100台web伺服器，它們都在和同一個資料庫通信。現在，資料庫突然成為了瓶頸，并且增加更多的web伺服器都無濟于事了。是以就可能需要很多個DB伺服器了，但是很難将多個DB進行同步。

可用性（Availability）

大型分布式系統中有一個大問題，那就是一些很罕見的問題會被放大。例如在我們的1000台計算機的叢集中，總是有故障，要麼是機器故障，要麼是運作出錯，要麼是運作緩慢，要麼是執行錯誤的任務。

大規模系統會将一些幾乎不可能并且你不需要考慮的問題，變成一個持續不斷的問題。

是以，因為錯誤總會發生，必須要在設計時就考慮，系統能夠屏蔽錯誤，或者說能夠在出錯時繼續運作。同時，因為我們需要為第三方應用開發人員提供友善的抽象接口，我們的确也需要建構這樣一種基礎架構，它能夠盡可能多的對應用開發人員屏蔽和掩蓋錯誤。這樣，應用開發人員就不需要處理各種各樣的可能發生的錯誤。

對于容錯，有很多不同的概念可以表述。這些表述中，有一個共同的思想就是可用性（Availability）。某些系統經過精心的設計，這樣在特定的錯誤類型下，系統仍然能夠正常運作，仍然可以像沒有出現錯誤一樣，為你提供完整的服務。

某些系統通過這種方式提供可用性。比如，你建構了一個有兩個拷貝的多副本系統，其中一個故障了，另一個還能運作。當然如果兩個副本都故障了，你的系統就不再有可用性。是以，可用系統通常是指，在特定的故障範圍内，系統仍然能夠提供服務，系統仍然是可用的。如果出現了更多的故障，系統将不再可用。

除了可用性之外，另一種容錯特性是自我可恢複性（recoverability）—如果出現了問題，服務會停止工作，不再響應請求，之後有人來修複，并且在修複之後系統仍然可以正常運作，就像沒有出現過問題一樣。這是一個比可用性更弱的需求，因為在出現故障到故障元件被修複期間，系統将會完全停止工作。但是修複之後，系統又可以完全正确的重新運作，是以可恢複性是一個重要的需求。

為了實作這些特性，有很多工具。其中最重要的有兩個：

• 一個是非易失存儲（non-volatile storage，類似于硬碟）。這樣當出現類似電源故障，甚至整個機房的電源都故障時，我們可以使用非易失存儲，比如硬碟，閃存，SSD之類的。我們可以存放一些checkpoint或者系統狀态的log在這些存儲中，這樣當備用電源恢複或者某人修好了電力供給，我們還是可以從硬碟中讀出系統最新的狀态，并從那個狀态繼續運作。是以，這裡的一個工具是非易失存儲。因為更新非易失存儲是代價很高的操作，是以相應的出現了很多非易失存儲的管理工具。同時建構一個高性能，容錯的系統，聰明的做法是避免頻繁的寫入非易失存儲。在過去，甚至對于今天的一個3GHZ的處理器，寫入一個非易失存儲意味着移動磁盤臂并等待磁碟旋轉，這兩個過程都非常緩慢。有了閃存會好很多，但是為了擷取好的性能，仍然需要許多思考。
• 對于容錯的另一個重要工具是複制（replication），不過，管理複制的多副本系統會有些棘手。任何一個多副本系統中，都會有一個關鍵的問題，比如說，我們有兩台伺服器，它們本來應該是有着相同的系統狀态，現在的關鍵問題在于，這兩個副本總是會意外的偏離同步的狀态，而不再互為副本。對于任何一種使用複制實作容錯的系統，我們都面臨這個問題。lab2都是通過管理多副本來實作容錯的系統，你将會看到這裡究竟有多複雜。

一緻性（Consistency）

假設我們在建構一個分布式存儲系統，并且這是一個KV服務。這個KV服務隻支援兩種操作，其中一個是put操作會将一個value存入一個key；另一個是get操作會取出key對應的value。整體表現就像是一個大的key-value表單。

一緻性就是用來定義操作行為的概念。因為，從性能和容錯的角度來說，我們通常會有多個副本。在一個非分布式系統中，你通常隻有一個伺服器，一個表單。雖然不是絕對，但是通常來說對于put/get的行為不會有歧義。直覺上來說，put就是更新這個表單，get就是從表單中擷取目前表單中存儲的資料。

但是在一個分布式系統中，由于複制或者緩存，資料可能存在于多個副本當中，于是就有了多個不同版本的key-value對。現在某個用戶端發送了一個put請求，并希望将key 1改成值21。這個put請求發送給了第一台伺服器，之後會發送給第二台伺服器（某種政策），因為相同的put請求需要發送給兩個副本，這樣這兩個副本才能保持同步。但是就在用戶端準備給第二台伺服器發送相同請求時，這個用戶端故障了。這時候一個是20，一個是21，這是一個很不好的結果。

現在某人通過get讀取key為1的值，那麼他可能獲得21，也可能獲得20，取決于get請求發送到了哪個伺服器。即使規定了總是把請求先發送給第一個伺服器，那麼我們在建構容錯系統時，如果第一台伺服器故障了，請求也會發給第二台伺服器。

強一緻（Strong Consistency）： get請求可以得到最近一次完成的put請求寫入的值。

弱一緻 (Weak Consistency)：不保證get請求可以得到最近一次完成的put請求寫入的值。

事實上，建構一個弱一緻的系統也是非常有用的。

人們對于弱一緻感興趣的原因是，雖然強一緻可以確定get擷取的是最新的資料，但是實作這一點的代價非常高。如果我們要實作強一緻，簡單的方法就是同時讀兩個副本，如果有多個副本就讀取所有的副本，并使用最近一次寫入的資料。但是這樣的代價很高，因為需要大量的通信才能得到一個資料，而且失去了分布式的本意，工作量并沒有分攤。是以，為了盡可能的避免通信，尤其當副本相隔的很遠的時候，人們會建構弱一緻系統，并允許讀取出舊的資料。當然，為了讓弱一緻更有實際意義，人們還會定義更多的規則。

MapReduce

需要一種架構，使得普通工程師也可以很容易的完成并運作大規模的分布式運算。這就是MapReduce出現的背景。

MapReduce的思想是，應用程式設計人員和分布式運算的使用者，隻需要寫簡單的Map函數和Reduce函數，而不需要知道任何有關分布式的事情，MapReduce架構會處理剩下的事情。

抽象來看，MapReduce假設啟動的時候，有一些輸入，這些輸入被分割成大量的不同的檔案或者資料塊。

MapReduce啟動時，會查找Map函數。之後，MapReduce架構會為每個輸入檔案運作Map函數。這裡很明顯有一些可以并行運算的地方，比如說可以并行運作多個隻關注輸入和輸出的Map函數。

Map函數會輸出key-value對，其中key是單詞，而value是1。我們對所有的輸入檔案都運作了Map函數，并得到了論文中稱之為中間輸出（intermediate output），也就是每個Map函數輸出的key-value對。

運算的第二階段是運作Reduce函數。MapReduce架構會收集所有Map函數輸出的每一個單詞的統計。比如說，MapReduce架構會先收集每一個Map函數輸出的key為a的key-value對。收集了之後，會将它們送出給Reduce函數。

是以第一個Reduce輸出a=2，第二個Reduce輸出b=2，第三個Reduce輸出c=1。

這就是一個典型的MapReduce Job。從整體來看，為了保證完整性，有一些術語要介紹一下：

• Job。整個MapReduce計算稱為Job。
• Task。每一次MapReduce調用稱為Task。

是以，對于一個完整的MapReduce Job，它由一些Map Task和一些Reduce Task組成。是以這是一個單詞計數器的例子，它解釋了MapReduce的基本工作方式。

Map函數和Reduce函數

Map函數使用一個key和一個value作為參數。我們這裡說的函數是由普通程式設計語言編寫(c++,Java)

入參中，key是輸入檔案的名字，通常會被忽略，因為我們不太關心檔案名是什麼，value是輸入檔案的内容。是以，對于一個單詞計數器來說，value包含了要統計的文本，我們會将這個文本拆分成單詞。

之後對于每一個單詞，我們都會調用emit。emit由MapReduce架構提供，并且這裡的emit屬于Map函數。emit會接收兩個參數，其中一個是key，另一個是value。在單詞計數器的例子中，emit入參的key是單詞，value是字元串“1”。這就是一個Map函數。在一個單詞計數器的MapReduce Job中，Map函數實際就可以這麼簡單。

Reduce函數的入參是某個特定key的所有執行個體（Map輸出中的key-value對中，出現了一次特定的key就可以算作一個執行個體）。是以Reduce函數也是使用一個key和一個value作為參數，其中value是一個數組，裡面每一個元素是Map函數輸出的key的一個執行個體的value。對于單詞計數器來說，key就是單詞，value就是由字元串“1”組成的數組，是以，我們不需要關心value的内容是什麼，我們隻需要關心value數組的長度。

Reduce函數也有一個屬于自己的emit函數。這裡的emit函數隻會接受一個參數value，這個value會作為Reduce函數入參的key的最終輸出。是以，對于單詞計數器，我們會給emit傳入數組的長度。這就是一個最簡單的Reduce函數

疑問：

###　調用emit時，資料會發生什麼變化？emit函數在哪運作？

首先看，這些函數在哪運作。這裡可以看MapReduce論文的圖1。現實中，MapReduce運作在大量的伺服器之上，我們稱之為worker伺服器或者worker。同時，也會有一個Master節點來組織整個計算過程。這裡實際發生的是，Master伺服器知道有多少輸入檔案，例如5000個輸入檔案，之後它将Map函數分發到不同的worker。是以，它會向worker伺服器發送一條消息說，請對這個輸入檔案執行Map函數吧。之後，MapReduce架構中的worker程序會讀取檔案的内容，調用Map函數并将檔案名和檔案内容作為參數傳給Map函數。worker程序還需要實作emit，這樣，每次Map函數調用emit，worker程序就會将資料寫入到本地磁盤的檔案中。是以，Map函數中調用emit的效果是在worker的本地磁盤上建立檔案，這些檔案包含了目前worker的Map函數生成的所有的key和value。

是以，Map階段結束時，我們看到的就是Map函數在worker上生成的一些檔案。之後，MapReduce的worker會将這些資料移動到Reduce所需要的位置。對于一個典型的大型運算，Reduce的入參包含了所有Map函數對于特定key的輸出。通常來說，每個Map函數都可能生成大量key。是以通常來說，在運作Reduce函數之前。運作在MapReduce的worker伺服器上的程序需要與叢集中每一個其他伺服器互動來詢問說，看，我需要對key=a運作Reduce，請看一下你本地磁盤中存儲的Map函數的中間輸出，找出所有key=a，并通過網絡将它們發給我。是以，Reduce worker需要從每一個worker擷取特定key的執行個體。這是通過由Master通知到Reduce worker的一條指令來觸發。一旦worker收集完所有的資料，它會調用Reduce函數，Reduce函數運算完了會調用自己的emit，這個emit與Map函數中的emit不一樣，它會将輸出寫入到一個Google使用的共享檔案服務中。

有關輸入和輸出檔案的存放位置，這是我之前沒有提到的，它們都存放在檔案中，但是因為我們想要靈活的在任意的worker上讀取任意的資料，這意味着我們需要某種網絡檔案系統（network file system）來存放輸入資料。

是以實際上，MapReduce論文談到了GFS（Google File System）。GFS是一個共享檔案服務，并且它也運作在MapReduce的worker叢集的實體伺服器上。GFS會自動拆分你存儲的任何大檔案，并且以64MB的塊存儲在多個伺服器之上。是以，如果你有了10TB的網頁資料，你隻需要将它們寫入到GFS，甚至你寫入的時候是作為一個大檔案寫入的，GFS會自動将這個大檔案拆分成64MB的塊，并将這些塊平均的分布在所有的GFS伺服器之上，而這是極好的，這正是我們所需要的。如果我們接下來想要對剛剛那10TB的網頁資料運作MapReduce Job，資料已經均勻的分割存儲在所有的伺服器上了。如果我們有1000台伺服器，我們會啟動1000個Map worker，每個Map worker會讀取1/1000輸入資料。這些Map worker可以并行的從1000個GFS檔案伺服器讀取資料，并擷取巨大的讀取吞吐量，也就是1000台伺服器能提供的吞吐量。