這篇文章是本人按照 MIT 6.824 的課程安排閱讀 Google File System 的論文以及相關課程資料並總結而來。

MIT 6.824 第一課學習的實際上是 Google MapReduce，第二課才學 GFS。不過考慮到大家對於 MapReduce 應該也沒啥興趣了，所以就先搬 GFS 的文章。

你也可以點擊此處前往我的博客閱讀該文章。

GFS 的主要需求

在學習 GFS 的原理前，首先我們應當瞭解 GFS 在設計時所面對的需求場景。簡單概括，GFS 的設計主要基於以下幾個需求：

  • 節點失效是常態。系統會構建在大量的普通機器上，這使得節點失效的可能性很高。因此，GFS 必須能有較高的容錯性、能夠持續地監控自身的狀態，同時還要能夠順暢地從節點失效中快速恢復
  • 存儲內容以大文件為主。系統需要存儲的內容在通常情況下由數量不多的大文件構成，每個文件通常有幾百 MB 甚至是幾 GB 的大小；系統應當支持小文件，但不需要為其做出優化
  • 主要負載為大容量連續讀、小容量隨機讀以及追加式的連續寫
  • 系統應當支持高效且原子的文件追加操作，源於在 Google 的情境中，這些文件多用於生產者-消費者模式或是多路歸併
  • 當需要做出取捨時，系統應選擇高數據吞吐量而不是低延時

GFS 集羣組成

本章會先給大家介紹一下一個 GFS 集羣的基本組成以及各個組件的基本職責。

簡單來講，除了客戶端以外，一個 GFS 集羣還包括一個 Master 節點和若干個 Chunk Server。它們會作為用戶級進程運行在普通的 Linux 機器上。

在存儲文件時，GFS 會把文件切分成若干個擁有固定長度的 Chunk（塊）並存儲。Master 在創建 Chunk 時會為它們賦予一個唯一的 64 位 Handle（句柄），並把它們移交給 Chunk Server，而 Chunk Server 則以普通文件的形式將每個 Chunk 存儲在自己的本地磁碟上。為了確保 Chunk 的可用性，GFS 會把每個 Chunk 備份成若干個 Replica 分配到其他 Chunk Server 上。

GFS 的 Master 負責維護整個集羣的元數據，包括集羣的 Namespace（命名空間，即文件元數據）以及 Chunk Lease 管理、無用 Chunk 回收等系統級操作。Chunk Server 除了保存 Chunk 以外也會週期地和 Master 通過心跳信號進行通信，Master 也藉此得以收集每個 Chunk Server 當前的狀態，並向其發送指令。

鑒於整個集羣只有一個 Master，客戶端在和 GFS 集羣通信時，首先會從 Master 處獲取 GFS 的元數據，而實際文件的數據傳輸則會與 Chunk Server 直接進行，以避免 Master 成為整個系統的數據傳輸瓶頸；除此以外，客戶端也會在一定時間內緩存 Master 返回的集羣元數據。

GFS 的元數據

GFS 集羣的所有元數據都會保存在 Master 的內存中。鑒於整個集羣只會有一個 Master，這也使得元數據的管理變得更為簡單。GFS 集羣的元數據主要包括以下三類信息：

  • 文件與 Chunk 的 Namespace
  • 文件與 Chunk 之間的映射關係
  • 每個 Chunk Replica 所在的位置

元數據保存在 Master 的內存中使得 Master 要對元數據做出變更變得極為容易；同時，這也使得 Master 能夠更加高效地掃描集羣的元數據，以喚起 Chunk 回收、Chunk 均衡等系統級管理操作。唯一的不足在於這使得整個集羣所能擁有的 Chunk 數量受限於 Master 的內存大小，不過從論文的內容來看，這樣的瓶頸在 Google 中從來沒有被觸及過，源於對於一個 64MB 大小的 Chunk，Master 只需要維持不到 64 位元組的元數據。況且，相比於增加代碼的複雜度，提高 Master 內存容量的成本要小得多。

為了保證元數據的可用性，Master 在對元數據做任何操作前對會用先寫日誌的形式將操作進行記錄，日誌寫入完成後再進行實際操作，而這些日誌也會被備份到多個機器上進行保存。不過，Chunk Replica 的位置不會被持久化到日誌中，而是由 Master 在啟動時詢問各個 Chunk Server 其當前所有的 Replica。這可以省去 Master 與 Chunk Server 同步數據的成本，同時進一步簡化 Master 日誌持久化的工作。這樣的設計也是合情合理的，畢竟 Chunk Server 當前實際持有哪些 Replica 也應由 Chunk Server 自己說了算。

數據一致性

用戶在使用 GFS 這類數據存儲系統時，首先應當瞭解其所能提供的數據一致性，而作為學習者我們也應先理解 GFS 對外呈現的數據一致性功能。

首先，命名空間完全由單節點 Master 管理在其內存中，這部分數據的修改可以通過讓 Master 為其添加互斥鎖來解決並發修改的問題，因此命名空間的數據修改是可以確保完全原子的。

文件的數據修改則相對複雜。在講述接下來的內容前，首先我們先明確，在文件的某一部分被修改後，它可能進入以下三種狀態的其中之一：

  • 客戶端讀取不同的 Replica 時可能會讀取到不同的內容，那這部分文件是不一致的（Inconsistent）
  • 所有客戶端無論讀取哪個 Replica 都會讀取到相同的內容，那這部分文件就是一致的（Consistent）
  • 所有客戶端都能看到上一次修改的所有完整內容，且這部分文件是一致的，那麼我們說這部分文件是確定的（Defined）

在修改後，一個文件的當前狀態將取決於此次修改的類型以及修改是否成功。具體來說：

  • 如果一次寫入操作成功且沒有與其他並發的寫入操作發生重疊，那這部分的文件是確定的（同時也是一致的）
  • 如果有若干個寫入操作並發地執行成功，那麼這部分文件會是一致的但會是不確定的：在這種情況下，客戶端所能看到的數據通常不能直接體現出其中的任何一次修改
  • 失敗的寫入操作會讓文件進入不一致的狀態

這之間的關係也被整理為了論文中的表格 1：

GFS 支持的文件數據修改數據包括兩種：指定偏移值的數據寫入（Write）以及數據追加（Record Append）。當寫入時，指定的數據會被直接寫入到客戶端指定的偏移位置中，覆蓋原有的數據。GFS 並未為該操作提供太多的一致性保證：如果不同的客戶端並發地寫入同一塊文件區域，操作完成後這塊區域的數據可能由各次寫入的數據碎片所組成，即進入不確定的狀態。

與寫入操作不同，GFS 確保即便是在並發時，數據追加操作也是原子且 at least once（至少一次）的。操作完成後，GFS 會把實際寫入的偏移值返回給客戶端，該偏移值即代表包含所寫入數據的確定的文件區域的起始位置。由於數據追加操作是 at least once 的，GFS 有可能會在文件中寫入填充（padding）或是重複數據，但出現的概率不高。

在讀取數據時，為了避免讀入填充數據或是損壞的數據，數據在寫入前往往會放入一些如校驗和等元信息以用於驗證其可用性，如此一來 GFS 的客戶端 library 便可以在讀取時自動跳過填充和損壞的數據。不過，鑒於數據追加操作的 at lease once 特性，客戶端仍有可能讀入重複的數據，此時只能由上層應用通過鑒別記錄的唯一 ID 等信息來過濾重複數據了。

對應用的影響

GFS 的一致性模型是相對鬆散的，這就要求上層應用在使用 GFS 時能夠適應 GFS 所提供的一致性語義。簡單來講，上層應用可以通過兩種方式來做到這一點：更多使用追加操作而不是覆寫操作；寫入包含校驗信息的數據。

青睞追加操作而不是覆寫操作的原因是明顯的：GFS 針對追加操作做出了顯著的優化，這使得這種數據寫入方式的性能更高，而且也能提供更強的一致性語義。儘管如此，追加操作 at least once 的特性仍使得客戶端可能讀取到填充或是重複數據，這要求客戶端能夠容忍這部分無效數據。一種可行的做法是在寫入的同時為所有記錄寫入各自的校驗和，並在讀取時進行校驗，以剔除無效的數據；如果客戶端無法容忍重複數據，客戶端也可以在寫入時為每條記錄寫入唯一的標識符，以便在讀取時通過標識符去除重複的數據。

GFS 集羣常見操作流程

Master Namespace 管理

在前面我們已經瞭解到，Namespace 作為 GFS 元信息的一部分會被維持在 Master 的內存中，由 Master 負責管理。在邏輯上，GFS Master 並不會根據文件與目錄的關係以分層的結構來管理這部分數據，而是單純地將其表示為從完整路徑名到對應文件元數據的映射表，並在路徑名上應用前綴壓縮以減少內存佔用。

為了管理來自不同客戶端的並發請求對 Namespace 的修改，Master 會為 Namespace 中的每個文件和目錄都分配一個讀寫鎖（Read-Write Lock）。由此，對不同 Namespace 區域的並發請求便可以同時進行。

所有 Master 操作在執行前都會需要先獲取一系列的鎖：通常，當操作涉及某個路徑 /d1/d2/.../dn/leaf 時，Master 會需要先獲取從 /d1、/d1/d2 到 /d1/d2/.../dn 的讀鎖，然後再根據操作的類型獲取 /d1/d2/.../dn/lead 的讀鎖或寫鎖 —— 獲取父目錄的讀鎖是為了避免父目錄在此次操作執行的過程中被重命名或刪除。

由於大量的讀寫鎖可能會造成較高的內存佔用，這些鎖會在實際需要時才進行創建，並在不再需要時被銷毀。除外，所有的鎖獲取操作也會按照一個相同的順序進行，以避免發生死鎖：鎖首先按 Namespace 樹的層級排列，同一層級內則以路徑名字典序排列。

讀取文件

客戶端從 GFS 集羣中讀取文件內容的過程大致如下：

  1. 對於指定的文件名和讀取位置偏移值，客戶端可以根據固定的 Chunk 大小來計算出該位置在該文件的哪一個 Chunk 中
  2. 客戶端向 Master 發出請求，其中包含要讀取的文件名以及 Chunk 索引值
  3. Master 向客戶端響應該 Chunk 的 Handle 以及其所有 Replica 當前所在的位置。客戶端會以文件名和 Chunk 索引值為鍵緩存該數據
  4. 之後，客戶端便可以選取其中一個 Replica 所在的 Chunk Server 並向其發起請求，請求中會指定需要讀取的 Chunk 的 Handle 以及要讀取的範圍

Chunk Lease

在客戶端對某個 Chunk 做出修改時，GFS 為了能夠處理不同的並發修改，會把該 Chunk 的 Lease 交給某個 Replica，使其成為 Primary：Primary 會負責為這些修改安排一個執行順序，然後其他 Replica 便按照相同的順序執行這些修改。

Chunk Lease 在初始時會有 60 秒的超時時間。在未超時前，Primary 可以向 Master 申請延長 Chunk Lease 的時間；必要時 Master 也可以直接撤回已分配的 Chunk Lease。

文件寫入

客戶端嘗試將數據寫入到某個 Chunk 的指定位置的過程大致如下：

  1. 客戶端向 Master 詢問目前哪個 Chunk Server 持有該 Chunk 的 Lease
  2. Master 向客戶端返回 Primary 和其他 Replica 的位置
  3. 客戶端將數據推送到所有的 Replica 上。Chunk Server 會把這些數據保存在緩衝區中，等待使用
  4. 待所有 Replica 都接收到數據後，客戶端發送寫請求給 Primary。Primary 為來自各個客戶端的修改操作安排連續的執行序列號，並按順序地應用於其本地存儲的數據
  5. Primary 將寫請求轉發給其他 Secondary Replica，Replica 們按照相同的順序應用這些修改
  6. Secondary Replica 響應 Primary，示意自己已經完成操作
  7. Primary 響應客戶端，並返回該過程中發生的錯誤（若有）

如果該過程有發生錯誤，可以認為修改已在 Primary 和部分 Secondary 上成功執行（如果在 Primary 上就出錯了，那麼寫請求不會被轉發出去）。此時可以認為此次修改操作沒有成功，因為數據會處於不一致的狀態。實際上，GFS 所使用的客戶端 lib 在此時會重新嘗試執行此次操作。

值得注意的是，這個流程特意將數據流與控制流分開：客戶端先向 Chunk Server 提交數據，再將寫請求發往 Primary。這麼做的好處在於 GFS 能夠更好地利用網路帶寬資源。

從上述步驟可見，控制流藉由寫請求從客戶端流向 Primary，再流向其他 Secondary Replica。實際上，數據流以一條線性數據管道進行傳遞的：客戶端會把數據上傳到離自己最近的 Replica，該 Replica 在接收到數據後再轉發給離自己最近的另一個 Replica，如此遞歸直到所有 Replica 都能接收到數據，如此一來便能夠利用上每臺機器的所有出口帶寬。

文件追加

文件追加操作的過程和寫入的過程有幾分相似：

  1. 客戶端將數據推送到每個 Replica，然後將請求發往 Primary
  2. Primary 首先判斷將數據追加到該塊後是否會令塊的大小超過上限：如果是，那麼 Primary 會為該塊寫入填充至其大小達到上限，並通知其他 Replica 執行相同的操作，再響應客戶端，通知其應在下一個塊上重試該操作
  3. 如果數據能夠被放入到當前塊中，那麼 Primary 會把數據追加到自己的 Replica 中，拿到追加成功返回的偏移值，然後通知其他 Replica 將數據寫入到該偏移位置中
  4. 最後 Primary 再響應客戶端

當追加操作在部分 Replica 上執行失敗時，Primary 會響應客戶端，通知它此次操作已失敗，客戶端便會重試該操作。和寫入操作的情形相同，此時已有部分 Replica 順利寫入這些數據，重新進行數據追加便會導致這一部分的 Replica 上出現重複數據，不過 GFS 的一致性模型也確實並未保證每個 Replica 都會是完全一致的。

GFS 只確保數據會以一個原子的整體被追加到文件中至少一次。由此我們可以得出，當追加操作成功時，數據必然已被寫入到所有 Replica 的相同偏移位置上，且每個 Replica 的長度都至少超出此次追加的記錄的尾部，下一次的追加操作必然會被分配一個比該值更大的偏移值，或是被分配到另一個新的塊上。

文件快照

GFS 還提供了文件快照操作，可為指定的文件或目錄創建一個副本。

快照操作的實現採用了寫時複製（Copy on Write）的思想：

  1. 在 Master 接收到快照請求後，它首先會撤回這些 Chunk 的 Lease，以讓接下來其他客戶端對這些 Chunk 進行寫入時都會需要請求 Master 獲知 Primary 的位置，Master 便可利用這個機會創建新的 Chunk
  2. 當 Chunk Lease 撤回或失效後，Master 會先寫入日誌，然後對自己管理的命名空間進行複製操作，複製產生的新記錄指向原本的 Chunk
  3. 當有客戶端嘗試對這些 Chunk 進行寫入時，Master 會注意到這個 Chunk 的引用計數大於 1。此時，Master 會為即將產生的新 Chunk 生成一個 Handle，然後通知所有持有這些 Chunk 的 Chunk Server 在本地複製出一個新的 Chunk，應用上新的 Handle，然後再返回給客戶端

Replica 管理

為了進一步優化 GFS 集羣的效率，Master 在 Replica 的位置選取上會採取一定的策略。

Master 的 Replica 編排策略主要為了實現兩個目標：最大化數據的可用性，以及最大化網路帶寬的利用率。為此，Replica 不僅需要被保存在不同的機器上，還會需要被保存在不同的機架上，這樣如果整個機架不可用了，數據仍然得以存活。如此一來，不同客戶端對同一個 Chunk 進行讀取時便可以利用上不同機架的出口帶寬，但壞處就是進行寫入時數據也會需要在不同機架間流轉，不過在 GFS 的設計者看來這是個合理的 trade-off。

Replica 的生命週期轉換操作實際只有兩個：創建和刪除。首先，Replica 的創建可能源於以下三種事件：創建 Chunk、為 Chunk 重備份、以及 Replica 均衡。

在 Master 創建一個新的 Chunk 時，首先它會需要考慮在哪放置新的 Replica。Master 會考慮如下幾個因素：

  1. Master 會傾向於把新的 Replica 放在磁碟使用率較低的 Chunk Server 上
  2. Master 會傾向於確保每個 Chunk Server 上「較新」的 Replica 不會太多，因為新 Chunk 的創建意味著接下來會有大量的寫入，如果某些 Chunk Server 上有太多的新 Chunk Replica，那麼寫操作壓力就會集中在這些 Chunk Server 上
  3. 如上文所述，Master 會傾向於把 Replica 放在不同的機架上

當某個 Chunk 的 Replica 數量低於用戶指定的閾值時，Master 就會對該 Chunk 進行重備份。這可能是由 Chunk Server 失效、Chunk Server 回報 Replica 數據損壞或是用戶提高了 Replica 數量閾值所觸發。

首先，Master 會按照以下因素為每個需要重備份的 Chunk 安排優先順序：

  1. 該 Chunk 的 Replica 數距離用戶指定的 Replica 數量閾值的差距有多大
  2. 優先為未刪除的文件（見下文）的 Chunk 進行重備份
  3. 除外，Master 還會提高任何正在阻塞用戶操作的 Chunk 的優先順序

有了 Chunk 的優先順序後，Master 會選取當前擁有最高優先順序的 Chunk，並指定若干 Chunk Server 直接從現在已有的 Replica 上複製數據。Master 具體會指定哪些 Chunk Server 進行複製操作同樣會考慮上面提到的幾個因素。除外，為了減少重備份對用戶使用的影響，Master 會限制當前整個集羣正在進行的複製操作的數量，同時 Chunk Server 也會限制複製操作所使用的帶寬。

最後，Master 會週期地檢查每個 Chunk 當前在集羣內的分佈情況，並在必要時遷移部分 Replica 以更好地均衡各節點的磁碟利用率和負載。新 Replica 的位置選取策略和上面提到的大體相同，除此以外 Master 還會需要選擇要移除哪個已有的 Replica：簡單概括的話，Master 會傾向於移除磁碟佔用較高的 Chunk Server 上的 Replica，以均衡磁碟使用率。

刪除文件

當用戶對某個文件進行刪除時，GFS 不會立刻刪除數據，而是在文件和 Chunk 兩個層面上都 lazy 地對數據進行移除。

首先，當用戶刪除某個文件時，GFS 不會從 Namespace 中直接移除該文件的記錄，而是將該文件重命名為另一個隱藏的名稱，並帶上刪除時的時間戳。在 Master 週期掃描 Namespace 時，它會發現那些已被「刪除」較長時間，如三天，的文件，這時候 Master 才會真正地將其從 Namespace 中移除。在文件被徹底從 Namespace 刪除前，客戶端仍然可以利用這個重命名後的隱藏名稱讀取該文件，甚至再次將其重命名以撤銷刪除操作。

Master 在元數據中有維持文件與 Chunk 之間的映射關係：當 Namespace 中的文件被移除後，對應 Chunk 的引用計數便自動減 1。同樣是在 Master 週期掃描元數據的過程中，Master 會發現引用計數已為 0 的 Chunk，此時 Master 便會從自己的內存中移除與這些 Chunk 有關的元數據。在 Chunk Server 和 Master 進行的週期心跳通信中，Chunk Server 會彙報自己所持有的 Chunk Replica，此時 Master 便會告知 Chunk Server 哪些 Chunk 已不存在於元數據中，Chunk Server 則可自行移除對應的 Replica。

採用這種刪除機制主要有如下三點好處：

  1. 對於大規模的分散式系統來說，這樣的機制更為可靠：在 Chunk 創建時，創建操作可能在某些 Chunk Server 上成功了，在其他 Chunk Server 上失敗了，這導致某些 Chunk Server 上可能存在 Master 不知道的 Replica。除此以外，刪除 Replica 的請求可能會發送失敗，Master 會需要記得嘗試重發。相比之下，由 Chunk Server 主動地刪除 Replica 能夠以一種更為統一的方式解決以上的問題
  2. 這樣的刪除機制將存儲回收過程與 Master 日常的週期掃描過程合併在了一起，這就使得這些操作可以以批的形式進行處理，以減少資源損耗；除外，這樣也得以讓 Master 選擇在相對空閑的時候進行這些操作
  3. 用戶發送刪除請求和數據被實際刪除之間的延遲也有效避免了用戶誤操作的問題

不過，如果在存儲資源較為稀缺的情況下，用戶對存儲空間使用的調優可能就會受到該機制的阻礙。為此，GFS 允許客戶端再次指定刪除該文件，以確實地從 Namespace 層移除該文件。除外，GFS 還可以讓用戶為 Namespace 中不同的區域指定不同的備份和刪除策略，如限制 GFS 不對某個目錄下的文件進行 Chunk 備份等。

高可用機制

Master

前面我們提到，Master 會以先寫日誌（Operation Log）的形式對集羣元數據進行持久化：日誌在被確實寫出前，Master 不會對客戶端的請求進行響應，後續的變更便不會繼續執行；除外，日誌還會被備份到其他的多個機器上，日誌只有在寫入到本地以及遠端備份的持久化存儲中才被視為完成寫出。

在重新啟動時，Master 會通過重放已保存的操作記錄來恢復自身的狀態。為了保證 Master 能夠快速地完成恢復，Master 會在日誌達到一定大小後為自身的當前狀態創建 Checkpoint（檢查點），並刪除 Checkpoing 創建以前的日誌，重啟時便從最近一次創建的 Checkpoint 開始恢復。Checkpoint 文件的內容會以 B 樹的形式進行組織，且在被映射到內存後便能夠在不做其他額外的解析操作的情況下檢索其所存儲的 Namespace，這便進一步減少了 Master 恢復所需的時間。

為了簡化設計，同一時間只會有一個 Master 起作用。當 Master 失效時，外部的監控系統會偵測到這一事件，並在其他地方重新啟動新的 Master 進程。

除外，集羣中還會有其他提供只讀功能的 Shadow Master：它們會同步 Master 的狀態變更，但有可能延遲若干秒，其主要用於為 Master 分擔讀操作的壓力。Shadow Master 會通過讀取 Master 操作日誌的某個備份來讓自己的狀態與 Master 同步；它也會像 Master 那樣，在啟動時輪詢各個 Chunk Server，獲知它們所持有的 Chunk Replica 信息，並持續監控它們的狀態。實際上，在 Master 失效後，Shadow Master 仍能為整個 GFS 集羣提供只讀功能，而 Shadow Master 對 Master 的依賴只限於 Replica 位置的更新事件。

Chunk Server

作為集羣中的 Slave 角色，Chunk Server 失效的幾率比 Master 要大得多。在前面我們已經提到，Chunk Server 失效時，其所持有的 Replica 對應的 Chunk 的 Replica 數量便會降低，Master 也會發現 Replica 數量低於用戶指定閾值的 Chunk 並安排重備份。

除外，當 Chunk Server 失效時，用戶的寫入操作還會不斷地進行，那麼當 Chunk Server 重啟後，Chunk Server 上的 Replica 數據便有可能是已經過期的。為此，Master 會為每個 Chunk 維持一個版本號，以區分正常的和過期的 Replica。每當 Master 將 Chunk Lease 分配給一個 Chunk Server 時，Master 便會提高 Chunk 的版本號，並通知其他最新的 Replica 更新自己的版本號。如果此時有 Chunk Server 失效了，那麼它上面的 Replica 的版本號就不會變化。

在 Chunk Server 重啟時，Chunk Server 會向 Master 彙報自己所持有的 Chunk Replica 及對應的版本號。如果 Master 發現某個 Replica 版本號過低，便會認為這個 Replica 不存在，如此一來這個過期的 Replica 便會在下一次的 Replica 回收過程中被移除。除外，Master 向客戶端返回 Replica 位置信息時也會返回 Chunk 當前的版本號，如此一來客戶端便不會讀取到舊的數據。

數據完整性

如前面所述，每個 Chunk 都會以 Replica 的形式被備份在不同的 Chunk Server 中，而且用戶可以為 Namespace 的不同部分賦予不同的備份策略。

為了保證數據完整，每個 Chunk Server 都會以校驗和的形式來檢測自己保存的數據是否有損壞；在偵測到損壞數據後，Chunk Server 也可以利用其它 Replica 來恢複數據。

首先，Chunk Server 會把每個 Chunk Replica 切分為若干個 64KB 大小的塊，並為每個塊計算 32 位校驗和。和 Master 的元數據一樣，這些校驗和會被保存在 Chunk Server 的內存中，每次修改前都會用先寫日誌的形式來保證可用。當 Chunk Server 接收到讀請求時，Chunk Server 首先會利用校驗和檢查所需讀取的數據是否有發生損壞，如此一來 Chunk Server 便不會把損壞的數據傳遞給其他請求發送者，無論它是客戶端還是另一個 Chunk Server。發現損壞後，Chunk Server 會為請求發送者發送一個錯誤，並向 Master 告知數據損壞事件。接收到錯誤後，請求發送者會選擇另一個 Chunk Server 重新發起請求，而 Master 則會利用另一個 Replica 為該 Chunk 進行重備份。當新的 Replica 創建完成後，Master 便會通知該 Chunk Server 刪除這個損壞的 Replica。

當進行數據追加操作時，Chunk Server 可以為位於 Chunk 尾部的校驗和塊的校驗和進行增量式的更新，或是在產生了新的校驗和塊時為其計算新的校驗和。即使是被追加的校驗和塊在之前已經發生了數據損壞，增量更新後的校驗和依然會無法與實際的數據相匹配，在下一次讀取時依然能夠檢測到數據的損壞。在進行數據寫入操作時，Chunk Server 必須讀取並校驗包含寫入範圍起始點和結束點的校驗和塊，然後進行寫入，最後再重新計算校驗和。

除外，在空閑的時候，Chunk Server 也會週期地掃描並校驗不活躍的 Chunk Replica 的數據，以確保某些 Chunk Replica 即使在不怎麼被讀取的情況下，其數據的損壞依然能被檢測到，同時也確保了這些已損壞的 Chunk Replica 不至於讓 Master 認為該 Chunk 已有足夠數量的 Replica。

附錄

節點緩存

在 GFS 中，客戶端和 Chunk Server 都不會對文件數據進行緩存。對於客戶端而言，考慮到大多數應用都會選擇順序讀取某些大文件，緩存的作用微乎其微，不過客戶端確實會緩存 GFS 的元數據以減少和 Master 的通信；對於 Chunk Server 來說，緩存文件數據也是不必要的，因為這些內容本身就保存在它的本地磁碟上，Linux 內核的緩存機制也會把經常訪問的磁碟內容放置在內存中。

Chunk 的大小

對於 GFS 而言，Chunk 的大小是一個比較重要的參數，而 GFS 選擇了使用 64MB 作為 Chunk 的大小。

較大的 Chunk 主要帶來瞭如下幾個好處：

  1. 降低客戶端與 Master 通信的頻率
  2. 增大客戶端進行操作時這些操作落到同一個 Chunk 上的概率
  3. 減少 Master 所要保存的元數據的體積

不過，較大的 Chunk 會使得小文件佔據額外的存儲空間；一般的小文件通常只會佔據一個 Chunk，這些 Chunk 也容易成為系統的負載熱點。但正如之前所設想的需求那樣，這樣的文件在 Google 的場景下不是普遍存在的，這樣的問題並未在 Google 中真正出現過。即便真的出現了，也可以通過提升這類文件的 Replica 數量來將負載進行均衡。

組件的快速恢復

GFS 的組件在設計時著重提高了狀態恢復的速度，通常能夠在幾秒鐘內完成啟動。在這樣的保證下，GFS 的組件實際上並不對正常關閉和異常退出做區分：要關閉某個組件時直接 kill -9 即可。

FAQ

MIT 6.824 的課程材料中給出了和 GFS 有關的 FAQ，在此我簡單地翻譯一下其中比較重要的一些內容。

Q：為什麼原子記錄追加操作是至少一次（At Least Once），而不是確定一次（Exactly Once）？

要讓追加操作做到確定一次是不容易的，因為如此一來 Primary 會需要保存一些狀態信息以檢測重複的數據，而這些信息也需要複製到其他伺服器上，以確保 Primary 失效時這些信息不會丟失。在 Lab 3 中你會實現確定一次的行為，但用的是比 GFS 更複雜的協議（Raft）。

Q：應用怎麼知道 Chunk 中哪些是填充數據或者重複數據？

要想檢測填充數據，應用可以在每個有效記錄之前加上一個魔數（Magic Number）進行標記，或者用校驗和保證數據的有效性。應用可通過在記錄中添加唯一 ID 來檢測重複數據，這樣應用在讀入數據時就可以利用已經讀入的 ID 來排除重複的數據了。GFS 本身提供了 library 來支撐這些典型的用例。

Q：考慮到原子記錄追加操作會把數據寫入到文件的一個不可預知的偏移值中，客戶端該怎麼找到它們的數據？

追加操作（以及 GFS 本身）主要是面向那些會完整讀取文件的應用的。這些應用會讀取所有的記錄，所以它們並不需要提前知道記錄的位置。例如，一個文件中可能包含若干個並行的網路爬蟲獲取的所有鏈接 URL。這些 URL 在文件中的偏移值是不重要的，應用只會想要完整讀取所有 URL。

Q：如果一個應用使用了標準的 POSIX 文件 API，為了使用 GFS 它會需要做出修改嗎？

答案是需要的，不過 GFS 並不是設計給已有的應用的，它主要面向的是新開發的應用，如 MapReduce 程序。

Q：GFS 是怎麼確定最近的 Replica 的位置的？

論文中有提到 GFS 是基於保存 Replica 的伺服器的 IP 地址來判斷距離的。在 2003 年的時候，Google 分配 IP 地址的方式應該確保瞭如果兩個伺服器的 IP 地址在 IP 地址空間中較為接近，那麼它們在機房中的位置也會較為接近。

Q：Google 現在還在使用 GFS 嗎？

Google 仍然在使用 GFS，而且是作為其他如 BigTable 等存儲系統的後端。由於工作負載的擴大以及技術的革新，GFS 的設計在這些年裡無疑已經經過大量調整了，但我並不瞭解其細節。HDFS 是公眾可用的對 GFS 的設計的一種效仿，很多公司都在使用它。

Q：Master 不會成為性能瓶頸嗎？

確實有這個可能，GFS 的設計者也花了很多心思來避免這個問題。例如，Master 會把它的狀態保存在內存中以快速地進行響應。從實驗數據來看，對於大文件讀取（GFS 主要針對的負載類型），Master 不是瓶頸所在；對於小文件操作以及目錄操作，Master 的性能也還跟得上（見 6.2.4 節）。

Q：GFS 為了性能和簡潔而犧牲了正確性，這樣的選擇有多合理呢？

這是分散式系統領域的老問題了。保證強一致性通常需要更加複雜且需要機器間進行更多通信的協議（正如我們會在接下來幾門課中看到的那樣）。通過利用某些類型的應用可以容忍較為鬆懈的一致性的事實，人們就能夠設計出擁有良好性能以及足夠的一致性的系統。例如，GFS 對 MapReduce 應用做出了特殊優化，這些應用需要的是對大文件的高讀取效率，還能夠容忍文件中存在數據空洞、重複記錄或是不一致的讀取結果；另一方面，GFS 則不適用於存儲銀行賬號的存款信息。

Q：如果 Master 失效了會怎樣？

GFS 集羣中會有持有 Master 狀態完整備份的 Replica Master；通過論文中沒有提到的某個機制，GFS 會在 Master 失效時切換到其中一個 Replica（見 5.1.3 節）。有可能這會需要一個人類管理者的介入來指定一個新的 Master。無論如何，我們都可以確定集羣中潛伏著一個故障單點，理論上能夠讓集羣無法從 Master 失效中進行自動恢復。我們會在後面的課程中學習如何使用 Raft 協議實現可容錯的 Master。

問題

除了 FAQ，課程還要求學生在閱讀 GFS 的論文後回答一個問題，問題如下：

Describe a sequence of events that result in a client reading stale data from the Google File System

描述一個事件序列，使得客戶端會從 Google File System 中讀取到過時的數據

通過查閱論文，不難找到兩處答案：由失效後重啟的 Chunk Server + 客戶端緩存的 Chunk 位置數據導致客戶端讀取到過時的文件內容（見 4.5 和 2.7.1 節），和由於 Shadow Master 讀取到的過時文件元信息（見 5.1.3 節）。以上是保證所有寫入操作都成功時客戶端可能讀取到過時數據的兩種情況 —— 如果有寫入操作失敗，數據會進入不確定的狀態，自然客戶端也有可能讀取到過時或是無效的數據。

結語

本文沒有總結論文中第六、七章的內容：第六章是 GFS 各項指標的測試結果，受限於篇幅故沒能在此放出，若讀者對 Google 測試 GFS 性能指標的方法有所興趣也可參考這一章的內容；第七章則提到了 Google 在開發 GFS 時踩過的一些坑，主要和 Linux 本身的 bug 有關，此處沒能放出這部分的內容主要是考慮到這些 bug 主要涉及 Linux 2.2 和 2.4 版本，相較於今日已失去其時效性，況且這些 bug 也很有可能已經由 GFS 的開發者修復並提交到新版的 Linux 中了。

從內容上看，閱讀 GFS 的論文是對高性能和強一致性之間的矛盾的一次很好的 Case Study：在強一致性面前，GFS 選擇了更高的吞吐性能以及自身架構的簡潔。高性能與強一致性之間的矛盾是分散式系統領域經久不衰的話題，源於它們通常是不可兼得的。除外，為了實現理想的一致性，系統也可能面臨來自並發操作、機器失效、網路隔離等問題所帶來的挑戰。

從概念上來講，一致指的是某個正確的狀態，而一個系統往往會有很多種不同的正確的狀態，它們又常被統稱為系統的一致性模型。在後面要閱讀的論文中，我們還會不斷地看到這個概念。

Google File System 論文的發表催生了後來的 HDFS，後者直到今天依然是開源分散式文件系統解決方案的首選。Google MapReduce 加上 Google File System 這兩篇論文可謂是大數據時代的開山之作，與 Google BigTable 並稱 Google 的三架馬車，由此看來這幾篇經典論文還是很值得我們去學習一番的。


推薦閱讀：
查看原文 >>
相關文章