《The Google File System》論文研讀

• 2020 年 7 月 4 日
• 筆記
• GFS, 分散式存儲, 分散式文件系統, 分散式系統

GFS 論文總結

說明：本文為論文 《The Google File System》 的個人總結，難免有理解不到位之處，歡迎交流與指正 。

論文地址：GFS Paper

閱讀此論文的過程中，感覺內容繁多且分散，一個概念的相關內容在不同部分相交地出現 。所以本文盡量將同一概念的相關內容串聯並總結在一起 。

本文以批註的形式添加個人理解 。

1. 前言

Google File System (GFS) 是由 Google 設計並實現的、一個面向大規模數據密集型應用的分散式文件系統，它不僅滿足所有分散式文件系統共有的 高性能 、伸縮性 、可靠性 、可用性 ，還以 Google 自身 應用程式 和 技術環境 為基礎進行了特有的設計 ，主要包括：

• 因為 GFS 使用設備數多，將組件失效視為常態事件 。因此 持續監控 、錯誤檢測 、災難冗餘 和 自動恢復 的機制必須包括在 GFS 中 。
• 主要對大文件的管理進行了優化 。
• 主要應用於 對文件尾部追加數據 的修改，而非覆蓋原有數據的方式，如 「生產者-消費者」 隊列，或者其他多路文件合併操作 。一旦寫完後，對文件的操作通常是順序讀 。
• 採用了較弱的 一致性 要求，引用 原子性的記錄追加 操作，保證多個客戶端能夠同時進行追加操作，不需要額外的同步操作來保證數據的一致性 。
• 目標程式絕大多數要求高速率、大批量地處理數據，極少要求對單一讀寫操作有嚴格的響應時間要求 。即 高性能的穩定網路頻寬 比 低延遲 更重要 。

2. 架構

2.1 介面

GFS 提供了一套類似傳統文件系統的 API介面函數 ，文件以 分層目錄 的形式組織，用 路徑名 來標識 。支援：創建新文件、刪除文件、打開文件、關閉文件、讀和寫文件，以及快照和記錄追加操作 。

2.2 架構設計

一個 GFS 集群包含：一個 master 、多台 chunkserver 、同時被多個 client 訪問 ，這些都是普通的 Linux 機器 。

每個文件被分為多個 chunk ，每個 chunk 大小為 64MB 。

chunk 保存在 chunkserver 上，每個 chunk 含有 3 個 副本 ，分別存於 3 個不同機架上的不同 chunkserver 。

文件只以本地文件形式保存在 chunkserver ，不在 client 或 chunksever 進行快取 。

3. Chunk及其副本

3.1 chunk 大小與數量

chunk 大小為 64MB ，每個 chunk 副本都以普通 Linux 文件的形式保存在 chunkserver ，使用 惰性分配 策略避免了因內部碎片造成的空間浪費 。

惰性分配：指直到使用一個資源的時候再去給它分配空間 。

chunkserver 把 chunk 以 Linux 文件形式保存在本地硬碟，並根據 chunk handle 和位元組範圍來讀寫 chunk 。

出於可靠性的考慮，每個 chunk 都會複製到多個 chunksever 上，默認副本數為 3 。

選擇較大 chunk 尺寸的優點：

• 減少了客戶端和 master 節點通訊的需求
• 用較大的 chunk 尺寸，客戶端能夠對一個塊進行多次操作，這樣就可以與 chunkserver 保持較長時間的 TCP 連接而減少網路負載
• 減少了 master 節點需要的元數據的數量

3.2 副本的位置

GFS 集群是高度分布的 多層布局結構 。一般將一個 chunk 的多個副本本別存儲在多個 機架 上，可以：

• 最大化數據可靠性和可用性：不僅可以預防硬碟損壞、伺服器宕機引發的問題，還可以預防網路、電源故障失效，比僅部署在不同伺服器上擁有更高的可靠性
• 最大化網路頻寬利用率：針對 chunk 的讀操作，能夠利用多個機架的整合頻寬

3.3 chunk 創建

master 創建一個 chunk 時，會選擇在哪裡放置初始的空的副本，主要考慮幾個因素：

• 希望在低於平均硬碟使用率的 chunkserver 上存儲新的副本
• 希望限制在每個 chunkserver 上 最近 的 chunk 創建操作的次數
• 希望把 chunk 分布在多個機架上

3.4 chunk 重新複製

當 chunk 的有效副本數量少於用戶指定的複製因素的時候（ 默認為 3 ），master 會重新複製它 。

可能的原因有：chunkserver 不可用了、chunkserver 上副本損壞、chunkserver 磁碟不可用或 chunk 副本的複製因素被提高了 。

優先順序因素：優先複製 副本數量和複製因素相差多的 、優先複製活躍的文件而非剛被刪除的文件 、優先複製會阻塞 client 程式的chunk 。

master 選擇優先順序最高的 chunk ，然後命令 chunkserver 直接從可用的副本克隆一個副本出來，選擇新副本位置的策略和創建時的策略相同 。

3.5 chunk 重新負載均衡

master 伺服器周期性地對副本進行 重新負載均衡 ：它檢查當前的副本分布情況，然後移動副本以便更好地利用硬碟空間、更有效地進行負載均衡 。

若加入了新的 chunkserver ，master 會通過重新負載均衡的方式逐漸填滿這個新的 chunkserver ，而不是短時間內填滿它（可能導致過載）。

3.6 租約 (lease)

master 為 chunk 的一個副本建立一個 lease ，將這個副本稱為 primary （ 主 chunk ），剩餘副本為 secondary 。

primary 對 chunk 的所有更改操作進行序列化，所有的副本都遵從這個序列進行修改操作 。因此，修改操作全局的順序首先由 master 節點選擇 lease 的順序決定，然後由 primary 的分配的序列號決定 。

設置 primary 的 目的 ：為了最小化 master 的管理負擔 。

split-brain 問題：

假設 S1 是一個 chunk 的 primary，並且 master 和 S1 之間的網路連接已斷開，master 發現此 S1 無響應後將確立 S2 為 primary 。此時 client 可以和 S1、S1 兩個 primary 連接 ，這就是 split-brain 問題 。

為解決 split-brain 問題，將 lease 的超時設置為 60s 。master 發現 S1 沒有響應，則會等 lease 過期後，分配新的 lease ，即 S2 只有在 S1 到期後才有可能被設為 primary 。

只要 chunk 被修改了，primary 就可以申請更長的租期，得到 master 的確認並收到租約延長的時間 。這些租約延長請求和批准的資訊通常附加在 master 和 chunkserver 之間的 HeatBeat 來傳遞 。

4. master

4.1 元數據

master 主要存放 3 類型的 元數據 ：文件和 chunk 的命名空間、文件和 chunk 的對應關係、每個 chunk 副本的存放地址 。

元數據細節：

namespace (a lookup table mapping full pathnames to metadata)	  (nv)
filename -> array of chunk handles		                  (nv)
chunk handle -> version num				          (nv)
list of chunkservers	                                          (v)
primary					                          (v)
lease time				                          (v)
// nv 表示非易失的，即存儲於記憶體與磁碟；v 表示存於記憶體

master 伺服器可以在後台周期性掃描自己保存的全部狀態資訊 。

4.2 chunk 管理

chunk 創建的時候，master 會給每個 chunk 分配一個唯一的標識符 chunk handler 。

master 伺服器在啟動時，或者有新的 chunkserver 加入時，向各個 chunkserver 輪詢它們所存儲的 chunk 資訊 （ chunk 位置等 ）。

master 會為 chunk 的一個副本建立 lease 。

master 使用 HeatBeat 資訊周期性地和每個 chunkserver 通訊，發送指令到各個 chunkserver 並接收 chunkserver 的狀態資訊 。

master 會對自己保存的元數據進行周期性掃描，這種周期性的狀態掃描也用於實現 chunk 垃圾收集、在 chunkserver 失效的時重新複製數據、通過 chunk 的遷移實現跨 chunkserver 的負載均衡以及磁碟使用狀況統計等功能 。

4.3 操作日誌

操作日誌包含了關鍵的 元數據變更歷史記錄 ，操作日誌不僅是元數據唯一的持久化存儲記錄，也作為判斷同步操作順序的邏輯時間基準線 。

會把日誌複製到多台遠程機器，並且只有把相應的日誌記錄寫入到本地以及遠程機器的硬碟之後，才響應客戶端的操作請求 。

4.4 快照

快照操作幾乎可以瞬間完成對一個 文件或目錄樹 (源) 做一個拷貝，而且幾乎不會對正在進行的其他操作造成任何干擾 。

使用 copy-on-write （ 寫時複製 ）技術實現快照 ：

• 當 master 接收到一個快照請求，首先取消需要快照的文件的所有 chunk lease
• lease 取消或過期後，master 將此操作記錄到日誌，並通過複製源的元數據將此日誌記錄反映到記憶體中（ 此時該 chunk 的引用計數加一，但並不真實地複製 chunk ）
• 直到 client 要寫入數據到此 chunk 時，發請求到 master 詢問 primary
• master 注意到該 chunk 引用計數大於一，就要求所有擁有該 chunk 副本的 chunkserver 建立拷貝，對這三個新拷貝中的一個設置 lease ，返回給 client
• client 得到回復後就可以正常寫這個 chunk ，而源 chunk 此時就保存成為快照

之所以要先取消需要快照的文件的 chunk ，是因為當 client 與 chunkserver 通訊，找不到 primary 時，必須去詢問 master 誰是 primary，這就相當於給了 master 一個觸發條件，讓它去發現建立快照的需求（ 即 chunk 的引用計數大於一 ），並創建 chunk 新拷貝 。

使用寫時複製的原因：這樣可以減少不必要的複製，因為建立快照時，並不是所有的 chunk 都被修改過（ 相較於上一次建立快照 ），所以直到一個 chunk 被修改時才真正複製它 。

4.5 命名空間鎖

通過使用 命名空間鎖 來保證 master 並發操作的正確順序 。

每個 master 的操作在開始之前都要獲得一系列的鎖。通常情況下，如果一個操作涉及 /d1/d2/…/dn/leaf ，那麼操作首先要獲得目錄 /d1， /d1/d2 ，…， /d1/d2/…/dn 的讀鎖，以及 /d1/d2/…/dn/leaf 的讀寫鎖 。根據操作的不同， leaf 可以是一個文件，也可以是一個目錄。

5. Client

GFS client 程式碼以庫的形式被鏈接在客戶程式里，client 程式碼實現了 GFS 文件系統的 API 介面函數、應用程式與 master 和 chunkserver 通訊、以及對數據進行讀寫操作。

client 和 master 節點的通訊只獲取元數據，它向 master 詢問應該聯繫的 chunkserver ，客戶端將這些元數據資訊快取一段時間，後續的操作將直接和 chunkserver 進行數據讀寫操作 。

6. 系統交互

6.1 讀

藉助系統架構圖描述 讀 的過程：

• client 發送 filename 和根據位元組偏移量計算得出的 chunk index （當前位元組偏移量/64MB ） 給 master
• master 返回 chunk handle 和 chunk 的副本位置（僅包含最近 version 的）資訊給 client
• client 以 filename 和 chunk index 為 key 快取這些數據
• client 發送請求到 chunkserver （一般選擇最近的），請求包括 chunk handle 和位元組範圍
• chunkserver 讀取文件，返回數據
• client 接收到數據，通過 checksum 去除填充數據以及通過 unique id 去重（如果有需要的話）

對於填充數據和重複數據的問題，有的任務並不介意這些，比如搜索引擎返回了兩個一樣的鏈接並無大礙 。對於介意這兩個問題的任務，則使用 checksum 去除填充數據，使用 unique id 去重 。

unique id 去重：client 上應用程式檢查數據的 id ，若此數據 id 與之前收到的數據的 id 一樣，則丟棄它 。

GFS 提供了處理填充數據和重複數據的庫 。

client 快取資訊到期或文件被重新打開前，client 不必再與 master 通訊 。

client 通常會在一次請求中查詢多個 chunk 資訊 。

上述流程主要用於大規模的流式讀取，如果是小規模的隨機讀取，通常做法是把小規模的隨機讀取合併並排序，之後按順序批量讀取 。

6.2 寫

1. client 向 master 詢問 chunk 的哪個副本是 primary ，以及該 chunk 的位置 。若沒有 primary ：
   • 若所有的 chunkserver 都沒有最近的版本號，返回錯誤
   • master 在擁有最近版本的副本中選擇 primary
   • 版本號遞增，並寫入硬碟中的 log
   • 告訴 primary 和 secondary 它們的身份和新版本號，並將新版本號寫入 chunkserver 的硬碟
2. master 將 primary 的標識符和 secondary 的位置返回給 cient ，client 快取這些數據後續使用 。只有 primary 不可用或 lease 已到期，client 才會再跟 master 進行聯繫 。
3. client 將數據推送到所有的副本上（ 數據以管道的方式，順序沿著一個 chunkserver 鏈進行傳送，優先選擇最近的 chunkserver ），chunkserver 接收到數據並保存在 LRU 快取中。
4. 所有副本確認接收到數據後，client 發送寫請求到 primary 。這個請求標識了早前推送到所有副本的數據，primary 為接收到的所有操作分配連續的序列號（ 這些操作可能來自不同的 client ）。primary 以序列號的順序將操作在本地執行 。
5. primary 將寫請求傳遞到所有的 secondary ，secondary 依照相同的序列號執行操作 。
6. 所有 secondary 回復 primary 已完成操作 。
7. primary 回復 client 。若返回錯誤，client 重複發起操作請求 。

若應用程式一次寫入的數據量很大，或數據跨越了多個 chunk ，client 會將它們拆分為多個寫操作 。

通過將 數據流和控制流分開 的方式，充分利用每台機器的頻寬，避免網路瓶頸和高延時的連接，最小化推送所有數據的延時 。

6.3 追加

GFS 提供了原子性的 記錄追加 ，使用記錄追加，client 只需要指定要寫入的數據，GFS 保證有至少一次原子的 ( atomically at least once ) 寫入操作成功執行（ 即寫入一個順序的 byte 流 ），寫入的數據追加到 GFS 指定的偏移位置上，之後 GFS 返回這個偏移量給client 。

傳統方式的寫入操作需要 client 指定數據寫入的偏移量，對一個 region 並行寫入時，region 尾部可能包含不同 client 寫入的數據片段 。

追加操作流程與寫流程（ 本文 6.3 ）基本一致，區別在於：

• 步驟 4 、5 、6
  • client 推送數據到文件最後一個 chunk 所有副本之後，發送請求給 primary 。primary 檢查追加數據是否超過 64MB ，若超過，primary 將當前 chunk 填充到最大尺寸，通知 secondary 執行相同操作，最後回復 client 讓其對下一個 chunk 重新進行追加請求 。
• 步驟 7
  • 若追加操作在任何一個副本上失敗了，client 重新請求追加，此時已經追加成功的副本還要多進行一次追加，就產生了記錄的重複 （ GFS 不保證 chunk 的所有副本在位元組級別是完全一致的，它只保證數據 原子性地至少一次 (atomically at least once) 地追加 ）。

7. 一致性模型

GFS 支援一個寬鬆的一致性模型 。

GFS 的弱一致性：

系統和一致性之間存在 tradeoff ，更好的一致性往往意味著更複雜的系統設計以及更多的機器間通訊。GFS 採用的較弱的一致性來降低系統複雜度，提高性能 。所以，它適用於對與不一致讀的問題不太敏感的任務，例如使用搜索引擎搜索某個關鍵詞，即使顯示的幾萬條結果里有少數幾條缺失、或順序不對，我們並不會意識到這些問題，說明 GFS 服務於搜索引擎這種任務是可行的；而像銀行數據存儲這種對一致性和準確性有較高要求的任務，則不適合使用 GFS 。

文件命名空間的修改（ 如：文件創建 ）是原子性的，它僅由 master 控制：命名空間鎖提供了原子性和正確性、master 操作日誌定義了這些操作在全局的順序 。

7.1 讀、寫、追加的一致性

對於數據修改後的文件 region ，首先有兩個定義：

• 一致的 (consistent)：對於一個 chunk ，所有 client 看到的所有副本內容都是一樣的
• 定義的 (defined)：數據修改後是一致的，且 client 可以看到寫入操作的全部內容（ 換句話說，可以看到每步操作修改後的內容 ）

對於不同類型修改的 region 狀態如下圖所示：

當一個數據寫操作成功執行，且沒有並發寫入，那麼影響的 region 就是 defined ：所有 client 都能看到寫入的內容。（ 隱含了 consistent ）

當並行修改寫完成之後，region 處於 consistent but undefined 狀態：所有 client 看到同樣的數據，但是無法讀到任何一次寫入操作寫入的數據 （ 因為可能有並行寫操作覆蓋了同一區域 ）。

失敗的寫操作導致 region 處於 inconsistent 狀態（ 同時也是 undifined 的 ）：不同 client 在不同時間會看到不同的數據　。

當對文件進行追加操作，若追加操作成功，那麼 region 處於 defined and consistent 狀態；若某次追加操作失敗，由本文 6.3 可知，client 重新請求後會導致數據填充和重複數據的情況，此時 region 處於 defined but inconsistent 狀態 。

某次追加失敗過程：

C1 向副本 S1 、S2 中追加 a ，若向 S2 中追加 a 時失敗，修改後結果為：

S1 – | a |
S2 – | |

此時 C2 並發地向 S1 、S2 中追加 b ，在兩副本相同偏移位置追加，執行成功，修改後結果為：

S1 – | a | b |
S2 – | | b |

之後 C1 由於有副本追加失敗，重新發起追加 a 的請求，此次追加成功，修改後結果為：

S1 – | a | b | a |
S2 – | | b | a |

可以看到，重複請求使得 S1 中有了重複記錄，使得 S2 中有了填充數據（ 那個空白 ），這就導致了這塊 region 是 defined（ 每步修改都能看到 ），但是 inconsistent（ 不同副本數據不一樣 ）

8. 垃圾回收

GFS 在文件刪除後不會立刻進行回收可用的物理空間，GFS 空間回收採用惰性的策略，只在文件和 chunk 級的常規垃圾收集時進行 。

當一個文件被應用程式刪除時，master 立即把刪除操作記錄到日誌 。master 並不立馬回收資源，而是把文件名改為一個包含 刪除時間戳 的隱藏名字 。當 master 對命名空間做 常規掃描 的時候，會刪除三天前的隱藏文件 ，此文件相關元數據也被刪除 。

在 master 對 chunk 命名空間做常規掃描時，若發現 孤兒 chunk （ 即不被任何文件包含的 chunk ），會提示 chunkserver 刪除這些 chunk 的副本 。

隱藏文件在真正被刪除前，還可以用新的名字讀取，也可以將其改為正常文件名以恢復 。

這種垃圾回收方式的優勢：

• 對於組件失效是常態的大規模分散式系統上，這種垃圾回收方式簡單可靠
• 垃圾回收把存儲空間的回收操作合併到 master 節點規律性的後台活動中（ 如 master 與 chunkserver 的握手 ），操作被批量執行，開銷被分散
• 延快取儲空間回收為意外的、不可逆轉的刪除操作提供了安全保障

9. 容錯與診斷

9.1 過期失效的副本檢測

過期副本：當 chunkserver 失效時，chunk 的副本可能因為錯失了一些修改而失效 。

master 保存了每個 chunk 的版本號用來區分當前副本和過期副本 。

只要 master 分配 chunk 一個 lease ，該 chunk 的版本號就會增加，然後通知最新的副本，master 和這些副本都將最新的版本號寫入硬碟保存 。若某個副本所在的 chunkserver 處於失效狀態，他的版本號就不會增加 。之後這個 chunkserver 重啟，向 master 報告它擁有的 chunk 和對應版本號的時候，master 會檢測出過期 chunk 。

且當 master 回復 client 關於 primary 的資訊、或者是 chunkserver 從哪個 chunkserver 進行克隆時，消息中會附帶了版本號，client 或 chunkserver 在執行操作時都會驗證版本號以確保總是訪問當前版本的數據 。

master 在例行的垃圾回收過程中移除所有過期失效的副本 。

9.2 快速恢復

不管 master 和 chunkserver 是如何關閉的，都在數秒內恢復狀態並重新啟動 。不區分正常關閉和異常關閉 。

master 在災難恢復時，從磁碟上讀取最近的快照，以及重演此快照後的有限個日誌文件就能夠恢復系統 。

chunkserver 重啟後會發送 chunk 狀態以及版本號給 master 。

9.3 chunk複製

每個 chunk 都被複制到不同機架的不同伺服器上，用戶可為文件命名空間的不同部分設定不同的複製級別 。

當有 chunkserver 離線了，或者通過 checksum 校驗發現了已損壞的數據，master 通過克隆已有的副本保證每個 chunk 都被完整複製 。

9.4 master 的複製

master 所有操作日誌和快照文件都被複制到多台機器的硬碟中 。若 master 進程所在的機器或硬碟失效了，處於 GFS 系統外部的監控進程會在其他的存有完整操作日誌的機器上啟動一個新的 master 進程 。

論文中沒有詳述這個 「外部的監控進程」，據 MIT 的 Robert Morris 教授解釋，切換到新的 master 需要人為進行 。

還有 shadow master 在 master 宕機時提供文件系統的只讀訪問 。它啟動的時候也會從 chunkserver 輪詢得到數據、定期和 chunkserver 握手來獲取狀態 。在 master 因創建和刪除副本導致副本位置資訊更新時，shadow master 才和 master 通訊來更新自身狀態 。

9.5 數據完整性

每個 chunkserver 都獨立維護 checksum 來檢查保存的數據的完整性 。checksum 保存在記憶體和硬碟上，也記錄在操作日誌中 。

對於讀操作來說：

• 在把數據返回給 client 或者其它的 chunkserver 之前， chunkserver 會校驗讀取操作涉及的範圍內的塊的 checksum
• 若某個副本的 checksum 不正確，chunkserver 返回請求者一個錯誤消息，並通知 master 這個錯誤消息
• 作為回應，請求者從其他副本讀取數據，master 伺服器從其他副本克隆數據進行恢復
• 新副本就緒後，master 通知 chunkserver 刪掉錯誤的副本

chunkserver 空閑的時候，也會掃描和校驗不活動 chunk 的內容 。一旦發現數據損壞，master 創建新的正確的副本，且把損壞的副本刪除掉 。

9.6 診斷工具

GFS 伺服器會產生大量日誌，記錄大量關鍵的事件（ 如 chunkserver 的啟動和關閉 ）以及所有 RPC 的請求和回復 。

可以通過重演所有消息交互來診斷問題。日誌還可以用來跟蹤負載測試和性能分析 。

10. GFS 的優點

• master 和 chunkserver 的設計，將文件管理和文件存儲分離
• 將文件分割成 chunk 存儲，可並發訪問，吞吐量較大
• 修改數據時控制流和數據流分離，充分利用每台機器的頻寬
• 使用 lease 降低 master 工作負載，防止 split-brain 問題
• 對文件追加和順序讀的功能有優化
• 好的容錯性

11. GFS 的缺點

• 只有一個 master ，元數據過多的話可能記憶體不夠用
• client 量很大的話，一個 master 負載過大
• master 不能出錯自動重啟，出故障後人工切換 master 比較耗時
• master 通過瀏覽所有的 chunk 進行垃圾回收效率太低
• 不擅長處理隨機寫問題、海量小文件存儲
• 一致性過松，無法處理對一致性要求高的任務
• GFS 被設計用於運行在單個數據中心的系統