MIT的【分布式系統課程】學習記錄

內容純屬個人學習過程中的筆記記錄，如果有侵權現象請留言，會立刻刪除

分布式存儲系統的難點：

設計大型存儲系統的出發點：利用數百臺計算機資源同時完成大量工作，達到性能加成

• 如何做？數據分割，從并行的多臺服務器上讀取數據【分片（Sharding）】
• 由于大量分片，故障會成常態。需要一個自動的容錯系統，而不是每次都人工介入【容錯（fault tolerance）】
• 實現容錯的最有用方式之一就是復制，維護2-3個副本，其中一個故障了還能用另一個【復制（replication）】
• 多份數據副本時，就會存在【不一致問題（inconsistency）】
• 通過設計可避免不一致問題，但需要不同服務器之間網絡額外的交互，會降低性能，所以想要一致性，代價就是【低性能】

如果想要好的一致性，就需犧牲一定性能，如果不想付出代價，就需要忍受一些不確定行為

GFS的設計目標：大型、快速的文件系統

• 全局有效，這樣不同應用程序都可（申請權限）然后從中讀取數據【共享】

• 【大容量、高速】，包含數據的文件會被GFS自動分割存放在多個服務器上，寫操作會很快

• 可以【自我修復】

• 只在一個數據中心運行

• 對大型順序文件的讀寫進行定制。GFS只順序處理，不支持隨機訪問，關注點在于吞吐量大

GFS Master：Active-Standby模式，只有一個Master節點在工作

• Master節點保存了文件名和存儲位置的對應關系【Master管理文件和Chunk信息】
• 還有大量的Chunk服務器，每一個Chunk服務器上都有1-2塊磁盤【Chunk存儲實際數據】

將兩類數據的管理問題完全隔離，Master節點知道每一個文件對應的所有的Chunk的ID，Chunk每個是64MB大小，共同構成了一個文件

如果我有一個1GB的文件，那么Master節點就知道文件的第一個Chunk存儲在哪，第二個Chunk存儲在哪，等等。當我想讀取這個文件中的任意一個部分時，我需要向Master節點查詢對應的Chunk在哪個服務器上，之后我可以直接從Chunk服務器讀取對應的Chunk數據

• Master節點內保存的數據內容：主要是兩個表單

  • 第一個是文件名到Chunk ID或者Chunk Handle數組的對應。這個表單主要講文件對應了哪些Chunk ID

  • 第二個表單記錄了Chunk ID到Chunk數據的對應關系。這里的數據又包括：

    • 每個Chunk存儲在哪些服務器上

    • 每個Chunk當前的版本號

    • 所有對于Chunk的寫操作都必須在主Chunk（Primary Chunk）上順序處理，主Chunk是Chunk的多個副本之一。所以，Master節點必須記住哪個Chunk服務器持有主Chunk

    • 主Chunk只能在特定的租約時間內擔任主Chunk，Master節點要記住主Chunk的租約過期時間

以上數據都存儲在內存中，如果Master故障了，這些數據就都丟失了。為了能讓Master重啟而不丟失數據，Master節點會同時將數據存儲在磁盤上。所以Master節點讀數據只會從內存讀，但是寫數據的時候，至少有一部分數據會接入到磁盤中。更具體來說，Master會在磁盤上存儲log，每次有數據變更時，Master會在磁盤的log中追加一條記錄，并生成CheckPoint（類似于備份點）。

有些數據需要存在磁盤上，而有些不用：

• Chunk Handle的數組（第一個表單）要保存在磁盤上
• Chunk服務器列表不用保存到磁盤上。因為Master節點重啟之后可以與所有的Chunk服務器通信，并查詢每個Chunk服務器存儲了哪些Chunk，所以不用寫入磁盤
• 版本號要不要寫入磁盤取決于GFS是如何工作的
• 主Chunk的ID，幾乎可以確定不用寫入磁盤，因為Master節點重啟之后會忘記誰是主Chunk，它只需要等待60秒租約到期，那么它知道對于這個Chunk來說沒有主Chunk，這個時候，Master節點可以安全指定一個新的主Chunk
• 租約過期時間也不用寫入磁盤

這里在磁盤中維護log而不是數據庫的原因是，數據庫本質上來說是某種B樹（b-tree）或者hash table，相比之下，追加log會非常的高效，因為你可以將最近的多個log記錄一次性的寫入磁盤。因為這些數據都是向同一個地址追加，這樣只需要等待磁盤的磁碟旋轉一次。而對于B樹來說，每一份數據都需要在磁盤中隨機找個位置寫入。所以使用Log可以使得磁盤寫入更快一些

當Master節點故障重啟，需要重建它的狀態，所以Master節點會在磁盤中創建一些checkpoint點，這可能要花費幾秒甚至一分鐘。這樣Master節點重啟時，會從log中的最近一個checkpoint開始恢復，再逐條執行從Checkpoint開始的log，最后恢復自己的狀態

GFS 讀文件：

• GFS客戶端會選擇一個網絡上最近的服務器發送 一個文件名 + 想從文件某個位置讀取的偏移量 給Master節點
• Master節點從自己的file表單中查詢文件名，得到Chunk ID數組，每個Chunk是64MB，偏移量/64MB就是從數組中得到對應的Chunk ID
• Master節點從Chunk表單中找Chunk服務器列表，返回給客戶端

GFS 寫文件：

• 客戶端向Master節點發送請求，想向這個文件名對應的文件追加數據，請告訴我文件中最后一個Chunk的位置

  多個客戶端同時寫同一個文件時，客戶端不知道文件究竟多長。此時，客戶端可以向Master節點查詢哪個Chunk服務器保存了文件的最后一個Chunk

• 讀文件可以從任何最新的Chunk副本讀取數據，但是寫文件必須要通過Chunk的主副本（Primary Chunk）來寫入。所以，寫文件時需要考慮Chunk的主副本不存在的情況

  對于Master節點來說，如果發現Chunk的主副本不存在，Master會找出所有存有Chunk最新副本的Chunk服務器

  如果你的一個系統已經運行了很長時間，那么有可能某一個Chunk服務器保存的Chunk副本是舊的，比如說還是昨天或者上周的。導致這個現象的原因可能是服務器因為宕機而沒有收到任何的更新。所以，Master節點需要能夠在Chunk的多個副本中識別出，哪些副本是新的，哪些是舊的。所以需要找出新的Chunk副本

? 當客戶端想要對文件進行追加，但是又不知道文件尾的Chunk對應的Primary在哪時，Master會等所有存儲了 最新Chunk版本的服務器集合完成，然后挑選一個作為Primary，其他的作為Secondary

• 之后，Master會增加版本號，并將版本號寫入磁盤，這樣就算故障了也不會丟失這個數據

• 接下來，Master節點會向Primary和Secondary副本對應的服務器發送消息并告訴它們，誰是Primary，誰是Secondary，Chunk的新版本是什么。Primary和Secondary服務器都會將版本號存儲在本地的磁盤中。這樣，當它們因為電源故障或者其他原因重啟時，它們可以向Master報告本地保存的Chunk的實際版本號

• Primary可以接收來自客戶端的寫請求，并將寫請求應用在多個Chunk服務器中。之所以要管理Chunk的版本號，是因為這樣Master可以將實際更新Chunk的能力轉移給Primary服務器。并且在將版本號更新到Primary和Secondary服務器之后，如果Master節點故障重啟，還是可以在相同的Primary和Secondary服務器上繼續更新Chunk。

• Master節點通知Primary和Secondary服務器，可以修改這個Chunk。它還給Primary一個租約，這個租約告訴Primary說，在接下來的60秒中，你將是Primary，60秒之后你必須停止成為Primary。這種機制可以確保我們不會同時有兩個Primary

  假設現在Master節點告訴客戶端誰是Primary，誰是Secondary，GFS提出了一種聰明的方法來實現寫請求的執行序列。客戶端會將要追加的數據發送給Primary和Secondary服務器，這些服務器會將數據寫入到一個臨時位置。所以最開始，這些數據不會追加到文件中。當所有的服務器都返回確認消息說，已經有了要追加的數據，客戶端會向Primary服務器發送一條消息說，你和所有的Secondary服務器都有了要追加的數據，現在我想將這個數據追加到這個文件中。Primary服務器或許會從大量客戶端收到大量的并發請求，Primary服務器會以某種順序，一次只執行一個請求。對于每個客戶端的追加數據請求（也就是寫請求），Primary會查看當前文件結尾的Chunk，并確保Chunk中有足夠的剩余空間，然后將客戶端要追加的數據寫入Chunk的末尾。并且，Primary會通知所有的Secondary服務器也將客戶端要追加的數據寫入在它們自己存儲的Chunk末尾。這樣，包括Primary在內的所有副本，都會收到通知將數據追加在Chunk的末尾。

• Secondary可能可以執行成功，也可能會執行失敗，比如說磁盤空間不足，比如說故障了，比如說Primary發出的消息網絡丟包了。如果Secondary實際真的將數據寫入到了本地磁盤存儲的Chunk中，它會回復“yes”給Primary。如果所有的Secondary服務器都成功將數據寫入，并將“yes”回復給了Primary，并且Primary也收到了這些回復。Primary會向客戶端返回寫入成功。如果至少一個Secondary服務器沒有回復Primary，或者回復了，但是內容卻是：抱歉，一些不好的事情發生了，比如說磁盤空間不夠，或者磁盤故障了，Primary會向客戶端返回寫入失敗。

如果客戶端從Primary得到寫入失敗，那么客戶端應該重新發起整個追加過程。客戶端首先會重新與Master交互，找到文件末尾的Chunk；之后，客戶端需要重新發起對于Primary和Secondary的數據追加操作。

GFS 一致性：

追加數據時，面對Chunk的三個副本，當客戶端發送了一個追加數據的請求，要將數據A追加到文件末尾，所有的三個副本，包括一個Primary和兩個Secondary，都成功的將數據追加到了Chunk，所以Chunk中的第一個記錄是A，假設第二個客戶端加入進來，想要追加數據B，但是由于網絡問題發送給某個副本的消息丟失了。所以，追加數據B的消息只被兩個副本收到，一個是Primary，一個是Secondary。這兩個副本都在文件中追加了數據B，所以，現在我們有兩個副本有數據B，另一個沒有。之后，第三個客戶端想要追加數據C，并且第三個客戶端記得下圖中左邊第一個副本是Primary。Primary選擇了偏移量，并將偏移量告訴Secondary，將數據C寫在Chunk的這個位置。三個副本都將數據C寫在這個位置。

對于數據B來說，客戶端會收到寫入失敗的回復，客戶端會重發寫入數據B的請求。所以，第二個客戶端會再次請求追加數據B，或許這次數據沒有在網絡中丟包，并且所有的三個副本都成功追加了數據B。現在三個副本都在線，并且都有最新的版本號。

之后，如果一個客戶端讀文件，讀到的內容取決于讀取的是Chunk的哪個副本。客戶端總共可以看到三條數據，但是取決于不同的副本，讀取數據的順序是不一樣的。如果讀取的是第一個副本，那么客戶端可以讀到A、B、C，然后是一個重復的B。如果讀取的是第三個副本，那么客戶端可以讀到A，一個空白數據，然后是C、B。所以，如果讀取前兩個副本，B和C的順序是先B后C，如果讀的是第三個副本，B和C的順序是先C后B。所以，不同的讀請求可能得到不同的結果。

或許最壞的情況是，一些客戶端寫文件時，因為其中一個Secondary未能成功執行數據追加操作，客戶端從Primary收到寫入失敗的回復。在客戶端重新發送寫文件請求之前，客戶端就故障了。所以，可能進入這種情形：數據D出現在某些副本中，而其他副本則完全沒有。

在GFS的這種工作方式下，如果Primary返回寫入成功，那么一切都還好，如果Primary返回寫入失敗，就不是那么好了。Primary返回寫入失敗會導致不同的副本有完全不同的數據。

GFS這樣設計的理由是足夠的簡單，但是同時也給應用程序暴露了一些奇怪的數據。這里希望為應用程序提供一個相對簡單的寫入接口，但應用程序需要容忍讀取數據的亂序。如果應用程序不能容忍亂序，應用程序要么可以通過在文件中寫入序列號，這樣讀取的時候能自己識別順序，要么如果應用程序對順序真的非常敏感那么對于特定的文件不要并發寫入。例如，對于電影文件，你不會想要將數據弄亂，當你將電影寫入文件時，你可以只用一個客戶端連續順序而不是并發的將數據追加到文件中。

如果想要將GFS升級成強一致系統，需要考慮的事情：

• 需要讓Primary來探測重復的請求，這樣第二個寫入數據B的請求到達時，Primary就知道，我們之前看到過這個請求，可能執行了也可能沒執行成功。Primay要嘗試確保B不會在文件中出現兩次。所以首先需要的是探測重復的能力。
• 對于Secondary來說，如果Primay要求Secondary執行一個操作，Secondary必須要執行而不是只返回一個錯誤給Primary。對于一個嚴格一致的系統來說，是不允許Secondary忽略Primary的請求而沒有任何補償措施的。所以我認為，Secondary需要接受請求并執行它們。如果Secondary有一些永久性故障，例如磁盤被錯誤的拔出了，你需要有一種機制將Secondary從系統中移除，這樣Primary可以與剩下的Secondary繼續工作。但是GFS沒有做到這一點，或者說至少沒有做對。
• 當Primary要求Secondary追加數據時，直到Primary確信所有的Secondary都能執行數據追加之前，Secondary必須小心不要將數據暴露給讀請求。所以對于寫請求，你或許需要多個階段。在第一個階段，Primary向Secondary發請求，要求其執行某個操作，并等待Secondary回復說能否完成該操作，這時Secondary并不實際執行操作。在第二個階段，如果所有Secondary都回復說可以執行該操作，這時Primary才會說，好的，所有Secondary執行剛剛你們回復可以執行的那個操作。這是現實世界中很多強一致系統的工作方式，這被稱為兩階段提交（Two-phase commit）。
• 另一個問題是，當Primary崩潰時，可能有一組操作由Primary發送給Secondary，Primary在確認所有的Secondary收到了請求之前就崩潰了。當一個Primary崩潰了，一個Secondary會接任成為新的Primary，但是這時，新Primary和剩下的Secondary會在最后幾個操作有分歧，因為部分副本并沒有收到前一個Primary崩潰前發出的請求。所以，新的Primary上任時，需要顯式的與Secondary進行同步，以確保操作歷史的結尾是相同的。
• 最后，時不時的，Secondary之間可能會有差異，或者客戶端從Master節點獲取的是稍微過時的Secondary。系統要么需要將所有的讀請求都發送給Primary，因為只有Primary知道哪些操作實際發生了，要么對于Secondary需要一個租約系統，就像Primary一樣，這樣就知道Secondary在哪些時間可以合法的響應客戶端。

為了實現強一致，需要增加了系統的復雜度，增加了系統內部組件的交互

許多Google的基礎架構，例如BigTable和MapReduce是構建在GFS之上，所以GFS在Google內部廣泛被應用。它最嚴重的局限可能在于，它只有一個Master節點，會帶來以下問題：

• Master節點必須為每個文件，每個Chunk維護表單，隨著GFS的應用越來越多，這意味著涉及的文件也越來越多，最終Master會耗盡內存來存儲文件表單。你可以增加內存，但是單臺計算機的內存也是有上限的。所以，這是人們遇到的最早的問題。
• 除此之外，單個Master節點要承載數千個客戶端的請求，而Master節點的CPU每秒只能處理數百個請求，尤其Master還需要將部分數據寫入磁盤，很快，客戶端數量超過了單個Master的能力。
• 另一個問題是，應用程序發現很難處理GFS奇怪的語義
• 最后一個問題是，GFS論文中，Master節點的故障切換不是自動的。GFS需要人工干預來處理已經永久故障的Master節點，并更換新的服務器，這可能需要幾十分鐘甚至更長的而時間來處理。對于某些應用程序來說，這個時間太長了。

（所以我們才需要多副本，多活，高可用，故障自修復的分布式系統啊）