且听风吟

分布式系統領域的經典論文，在 ChatGPT 和 Claude 的幫助下一遍讀一遍翻譯，主要是前 5 章 這裡看原文

概述#

GFS 是一個用於大型分佈式數據密集型應用的，可伸縮的分佈式文件系統。

GFS 的應用場景和設計要點#

1. GFS 系統運行在許多廉價的普通硬件之上，故障非常常見，包括應用程序 bug、操作系統 bug、人為錯誤、磁碟 / 記憶體 / 驅動 / 網路 / 電源故障等。因此需要常態化的監控，錯誤檢測，容錯和自動恢復機制，將組件故障視作常態而非異常。
2. GFS 系統存儲的文件通常較大，達到 100MB 甚至 GB 級別都很常見。所以需要對大文件進行高效的管理，小文件可以支持但無需針對其進行優化。
3. 文件修改更多是追加寫而非覆蓋，隨機寫非常少見。文件的讀取一般是大規模的串流讀取（幾百 KB 至數 MB）或者小規模（幾 KB）的隨機讀取。
4. 負載主要來自於：大規模的串流讀取（幾百 KB 至數 MB），小規模（幾 KB）的隨機讀取以及大量級的序列化的追加寫。
5. GFS 的文件經常用作生產 - 消費隊列或者多路合併，所以系統必須高效的實現多個客戶端對同一文件的並行追加語義。
6. 高持續帶寬比低延遲更重要。

接口#

GFS 接口提供以下操作：create, delete, open, close, read, write, snapshot, record append，其中 snapshot 是一種低成本的文件創建或者目錄複製操作，record append 是原子追加操作，允許多個 client 並行追加一個文件並保證每個 client 操作的原子性，用於多路合併。

架構#

一個 GFS 集群有一個 master 節點和多個 chunkserver 在集群中，所有文件被分割成固定大小的 chunk，每個 chunk 在創建時由 master 分配一個全局唯一的不可變的 64bit chunk handle。chunks 由 chunkserver 存儲在本地磁碟上，通過 chunk handle 和 byte range 進行讀寫。為了保證可靠性，每個 chunk 會在多個 chunkserver 上創建副本，默認創建三個。

master 節點存儲所有文件的 metadata，包括 namespace 權限控制信息，文件到 chunk 的映射，以及 chunk 的位置信息。master 節點同時控制系統級的活動如 chunk 租約管理，孤兒 chunk 的垃圾回收，以及 chunk 在 chunkserver 之間的遷移。master 節點定期的通過 HeartBeat 消息和 chunkserver 通信來下發指令和收集 chunkserver 的狀態信息。

client 通過與 master 互動獲取和修改 metadata，所有承載數據的通信都直接與 chunkserver 連接，client 和 chunkserver 都不緩存文件（但是 client 會緩存 metadata），有以下原因：

• client 做緩存的收益很小。因為大多數請求都會串流傳輸大文件或者有很大的 work set 無法緩存。沒有緩存會使得客戶端的實現更簡單且整個系統可以不必考慮緩存失效（一致性）問題。
• chunkserver 也沒必要另作一層緩存因為 chunk 本身存儲為普通文件，Linux 的 buffer cache 已經能夠保持頻繁訪問的文件放在內存裡面。

交互流程#

1. client 根據固定的 chunksize 將文件名和偏移量轉換成 chunkindex。
2. client 將文件名和 chunkindex 發送到 master。
3. master 返回對應 chunk 的多個副本的 chunk handle 和位置信息。
4. client 以文件名加上 chunkindex 作為 key 緩存服務端返回的信息。
5. client 指定 chunk handle 和字節範圍，向其中一個副本（一般使用距離最近的那個）所在 chunkserver 發送數據請求。
6. 後續對同一 chunk 的讀請求使用本地緩存，無需和 master 互動，直到緩存信息失效或者文件被重新打開。
7. 通常 client 會在一個請求中包含多個 chunk，而 master 也會將多個之後可能需要的 chunk 一併返回以減少後續請求的消耗。

chunk 大小#

GFS 選擇的 chunksize 為 64MB，比通常操作系統的磁碟塊要大，每個 chunk 副本在 chunkserver 上以 Linux 普通文件的形式存儲，空間分配是惰性的，避免由於內部碎片造成的空間浪費。選擇較大的 chunksize 有以下優點：

• 單個文件的 chunk 數量更少，減少 client 和 master 互動獲取 chunkserver 位置信息的請求。
• 一個 client 可以在同一 chunk 上執行多個操作，只需保持一個持久的 TCP 連接即可，減少了許多連接創建的額外消耗。
• 系統 chunk 總量更少，從而減少了 master 需要存儲的 metadata 大小，使得 metadata 可以保持在內存中。

通常，小文件只包含少量甚至僅有一個 chunk。如果許多 client 訪問相同的文件，這些 chunkserver 可能會是熱點，實際情況下熱點不是主要問題，因為應用大多順序讀取多 chunk 文件。然後當 GFS 首次應用在批處理隊列系統上時，確實出現了熱點問題：一個可執行文件被寫入到 GFS 作為一個單 chunk 文件後續上百台機器同時訪問，存儲這個文件的少量 chunkserver 由於數百個同時請求導致過載。我們通過兩個方式修復這個問題：1. 增大副本數量 2. 應用程序將 chunk 讀取的時間錯位避免同時請求。還有一種可能有效解決方案是：在這種場景下允許 client 讀取其他 client 的數據。

元信息#

master 存儲三種 metadata：文件和 chunk 的 namespace、文件到 chunks 的映射、每個 chunk 副本的位置信息。所有 metadata 都會一直存在 master 的內存中，而且 master 會將前兩種信息的變更日誌持久化到本地和遠端的磁碟。通過日誌回放可以簡單的更新 master 的狀態，保證可靠性和崩潰後狀態恢復的一致性問題。

master 不持久化存儲 chunk 副本的位置信息，而是在啟動時向 chunkserver 詢問或者是有 chunkserver 新加入集群時詢問。

內存狀態#

由於 metadata 存儲在內存中所以 master 的操作一般都很快，且可以很高效的在後台對完整狀態進行周期性的遍歷。周期性的掃描用於：實現垃圾回收、為失效的 chunkserver 上的 chunk 重新創建副本、執行 chunk 的遷移以保證 chunkserver 間的負載和磁碟空間的負載均衡。

全部存在內存中的問題是，整個系統 chunk 的容量受到 master 機器內存限制，在實踐中一般不是什么問題，一個 64MB chunk 的 metadata 一般小於 64byte 而且大多數文件的 chunk 是滿的，除了最後一個 chunk 這樣就不會有很多稀碎的 chunk。同時文件 namespace 的 metadata 一般也小於 64byte，文件名使用了前綴壓縮存儲的很緊湊。最後，如果真的需要支持更大的文件系統只需要簡單的增加 master 機器的內存即可。

chunk 位置#

master 上沒有存儲哪個 chunkserver 有哪些 chunk 的副本的持久化記錄，只是在啟動時輪詢所有的 chunkserver，且 master 能夠保證這些信息是最新的因為 master 控制所有 chunk 的位置的安排，而且還會通過 HeartBeat 監控所有 chunkserver 的狀態。

通過啟動時查詢能夠消除很多由於 master 和 chunkserver 同步問題，比如 chunkserver 加入集群，離開集群，修改名稱，重啟，崩潰等等，在一個比較大的集群裡，這些事情會經常發生。另一方面，由於 chunkserver 上的很多錯誤可能導致 chunk 憑空消失（比如磁碟故障導致不可用）或者重命名操作，只有 chunkserver 自己才知道是不是真正存儲了有效的 chunk，所以在 master 上存儲這個信息也沒有意義。

操作日誌#

操作日誌包含了關鍵的 metadata 的變更歷史記錄，也是 metadata 僅有的持久化信息，而且為所有的並行操作提供了邏輯上的時間線順序。所有的 chunk 創建和版本號變更時，都會標記一個邏輯時間。由於操作日誌的重要性，必須保證足夠可靠的存儲，而且在持久化完成之前對 client 不可見。操作日誌會在遠端機器上創建副本，並且只有在本地和遠端磁碟上都刷新後才返回給客戶端。

master 通過回放操作日誌進行恢復，為了最小化 master 啟動時間，日誌需要盡可能小。在日誌量達到一定大小時 master 會為當前完整狀態創建一個 checkpoint，再次啟動時只需要從最後一個 checkpoint 往後回放日誌即可。checkpoint 本身是一顆緊湊 B-tree 結構可以直接映射到內存並進行命名空間的查詢而無需額外的解析。

創建 checkpoint 本身需要一定的時間，master 內部的狀態是結構化的，新的 checkpoint 的創建可以不阻塞當前的修改操作。創建 checkpoint 時會在另外一個線程上，切換到新的日誌文件，新創建的 checkpoint 包含之前的所有變更。百萬級別文件的系統 checkpoint 可以在一分鐘內創建，創建完成後還需要寫入到本地和遠端的磁碟才算成功。master 恢復時只需要回放從最後一個完整有效的 checkpoint 之後的操作日誌，更早的 checkpoint 可以直接刪除，創建 checkpoint 期間的失敗不影響正確性，因為恢復時會檢查並且跳過不完整的 checkpoint。

一致性模型#

GFS 使用了相對寬鬆的一致性模型，但仍然能夠保證相對簡單且高效的實現 GFS 的保證如下：namespace 的變更（mutation）（如創建文件）具有原子性、master 節點會在 namespace 上添加互斥鎖來執行操作、master 節點上的操作日誌能夠定義變更的全局順序。

文件區域（file region 指文件在存儲設備上的字節範圍）在數據變更後的狀態取決於數據變更的類型：成功 / 失敗，是否是並發變更。

文件區域（file region）指的是文件在存儲設備上的字節範圍，如果所有 client 無論從哪個副本，都始終能讀取到相同的數據，則這個文件區域是一致的。如果一個文件數據變更後保持一致的同時，所有 client 都能看到變更寫入的完整內容則這個區域是 defined（這個詞不太好翻譯，可以理解為這個文件區域的內容是 client 可以確定的）。

• 寫失敗：結果當然是不一致了。
• 非並發（順序）寫成功：結果肯定是 defined 對應文件區域的內容就是 client 寫入的內容。
• 並發寫成功後：文件區域是一致的，但對應文件區域寫入的內容可能是多個寫入片段混合在一起，所以是 undefined。
• 順序 / 並發追加成功：由於追加具有原子性，所以最終成功的那個區域的文件內容是確定即 defined，但在此之前可能還有成功或失敗的寫入以及填充數據等。

數據變更可能是寫入或者追加：寫入需要客戶端指定偏移量，追加是在 client 認為是文件結尾的位置作為偏移量進行寫入。追加操作會原子性的執行至少一次，即使存在並發變更，但執行追加時，最終偏移量是由 GFS 選擇的，最終寫入成功使用的偏移量會返回給 client 並且標記為包含這條 append record 的 defined 的文件區域的起點（前面可能也寫成功或失敗過）。

GFS 可能會插入填充或者重複添加記錄，這塊區域會被認為是不一致的。在一系列的變更之後，最終的文件可以保證在一定範圍內是 defined 並且包含最後一次變更寫入的數據。

GFS 通過按順序將變更應用到 chunk 的所有副本來進行歸檔，然後使用 chunk 版本號檢查所有過時的副本，這些副本可能是由於 chunkserver 下線導致變更丟失變更。過時的副本不會參與後續的所有變更，也不會在 client 請求 master 時被返回給 client，它們會儘可能早的被垃圾回收掉。由於 client 緩存了 chunk 的位置信息，所以在此緩存刷新前 client 可能會從一個過時的副本中讀取數據，這個時間窗口受到緩存單元的超時時間和下一次文件的打開時間限制。由於大多數文件都是只追加的，所以過時的副本相對於最新的數據只是文件的結束位置較早，需要讀最新數據的 client 會讀取失敗，重試時會向 master 重新請求 chunk 信息，此時就能夠立即得到最新的 chunk 位置信息了。

在一個變更成功很久之後，組件故障也能導致數據損壞或丟失 GFS 會通過和所有 chunkserver 的握手請求，檢查校驗和發現數據損壞，然後將 chunkserver 標記為失效。一旦發現了錯誤，數據會可能快的從其他有效副本中重新複製存儲，一個 chunk 只有在 GFS 反應過來之前所有副本都失效了才有可能不可逆的丟失，通常這個時間大概是數分鐘。在這種情況下會返回給 client 數據不可用而不是損壞。

對於使用 GFS 的應用，為了適應這種寬鬆的一致性，應該儘量使用追加寫而非隨機寫，根據寫入的位置自己定義文件，周期性的設置已經寫入完成的 checkpoint 並且包含應用層的校驗和。然後只讀取 checkpoint 之前的數據，並進行校驗和檢查。無論是一致性問題還是並發問題，這樣都能很好的處理。在發生寫入錯誤時，應用可以在自己記錄的 checkpoint 後重新增量寫入。應用可以根據 checksum 丟棄填充的內容和碎片記錄。應用也可以給每條記錄添加一個唯一 ID 標識重複記錄。

系統交互#

租約和變更順序#

變更是一個改變數據或者 metadata 的操作，每個變更都會應用到 chunk 的所有副本 GFS 使用租約機制維護所有副本間變更的一致性。在執行變更前 GFS 會在 chunk 的所有副本中選擇一個授予租約，此副本稱為 primary，primary 負責決定在這個 chunk 執行變更操作的串行順序，所有的其他副本在執行 chunk 變更操作時都遵循這個順序。

由此，整個系統的全局變更順序就能夠由 master 授予租約的順序，以及各個 primary 的執行變更順序決定。租約機制是為了最小化在 master 節點上的管理開銷，租約有一個初始為 60s 的超時時間，但只要有 chunk 變更完成 primary 就可以擴充超時時間，master 會將此超時時間擴充通過 HeartBeat 消息發送給所有的 chunkserver。master 在某些情況下可能會撤銷租約，比如 master 想要禁用在一個已經重命名的文件上的變更，在 master 和 primary 丟失通信的情況下，可以通過超時機制重新賦予新的租約。

client 執行一個變更的流程如下：

1. client 向 master 請求持有指定 chunk 租約的 chunkserver 及其他副本的位置信息。如果當前沒有租約，則 master 選擇一個副本授予租約。
2. master 返回所有副本的位置信息，並標識哪個是 primary，然後 client 會緩存這些信息供後續使用，client 只有在無法和 primary 通信或者是 primary 不再持有租約時才再次請求 master 節點。
3. client 以任意順序將數據推送到所有的副本，每個 chunkserver 會將數據存儲在內部的 LRU buffer cache 中，直到數據被使用或者過期。將數據流和控制流解耦後，可以基於網路拓撲調度數據流來提升性能。
4. 當所有副本都確認收到數據後 client 向 primary 發送一個寫請求，並標識早先已經推送給所有副本的數據，primary 為收到的所有變更賦值連續的序列號，然後按照序號執行所有的變更到自己本地的狀態上。
5. primary 將寫請求轉發到所有的 secondary 上，然後 secondary 按照 primary 賦值的序列號順序執行所有的變更。
6. 所有的 secondary 回覆 primary 後表明他們都已經完成了操作。
7. 如果在任意 secondary 失敗（即沒有在全部 secondary 上成功）primary 會將對應的失敗的錯誤返回給 client，已經修改的文件區域現在變成了不一致狀態，然後 client 會重試失敗的變更，即重複步驟 3 至步驟 7。

如果一個寫入非常大或者是跨 chunk 寫入 GFS 的 client 代碼會將其分割成多個寫入操作，分別按照以上流程進行寫入。但是如果多個 client 並發執行，交錯執行可能導致覆寫，共享的文件末尾就包含多個 client 寫入的片段，這種情況下由於所有副本按照相同的順序執行，文件區域是一致的，但文件的狀態是 undefined，不確定哪個在前哪個在後。

數據流#

解耦控制流和數據流是為了使網路傳輸更加高效，控制流從 client 到 primary 然後再到其他 secondary，而數據流以流水線的方式沿著精心挑選的 chunkserver 鏈路線性推送，目的是為了最大化的利用每台機器的帶寬以及最小化推送所有數據的延遲。每台機器的全部出口帶寬都盡可能用於儘快傳輸數據，而不是為多個接收者進行數據的切分。

為了儘可能避免網路瓶頸和高延遲鏈路，每台機器轉發數據會選擇網路拓撲上距離最近還沒有收到數據的機器 GFS 內部的網路拓撲非常簡單，可以通過 IP 地址精確的估計距離。GFS 內部通過流水線傳輸數據以降低延遲，一旦 chunkserver 開始收到數據，就會立即開始轉發。

原子性記錄追加#

GFS 提供了一種具有原子性的追加操作稱為 record append，與一般的寫入不同的是 record append 不指定寫入位置，GFS 保證會將此數據原子性的追加到文件末尾至少一次，然後將偏移量返回給 client，有點類似 Unix 下 O_APPEND 模式並發寫入文件，不會有數據競爭。如果用普通寫想到達此效果需要分佈式鎖。

record append 是變更的操作之一，遵循相同的控制流，但在 primary 上稍有不同，client 將追加數據推送到文件末尾的最後一個 chunk 的所有副本，然後將請求發送到 primary，然後 primary 檢查在當前 chunk 上追加記錄後是否會超過最大大小（64MB）。

• 如果超過了則 primary 會先將當前 chunk 填充到最大大小，告訴所有的 secondary 執行相同的操作，然後返回給 client，此操作應該在下一個 chunk 上重試（record append 的大小被限制在 1/4 個 chunksize 以避免比較極端的碎片化的情況）。
• 如果沒有超過 chunksize 則 primary 在本地的副本上追加記錄然後將偏移量發送給所有的 secondary 進行數據寫入，最終返回響應給 client。

如果 record append 在任一副本上追加失敗，client 會重試此操作，最終同一 chunk 的不同副本可能包含不同數據，包含全部或部分重複的同一記錄。

GFS 不保證所有副本字節級別的完全相同，只能保證數據會被至少原子性的寫入一次，對於寫入成功的操作，數據一定在 chunk 的所有副本上的寫在相同偏移量上，所有副本的長度至少會跟追加數據的長度相同，後續的追加只會有更高的偏移量。按照之前一致性的定義 record append 操作成功後文件區域可以被認為是 defined，當然也是具有一致性的。

快照#

snapshot 操作可以幾乎立刻的創建文件或者目錄樹的拷貝，儘量減少正在進行的變更或者任何的中斷。

GFS 使用 copy-on-write 技術來實現 snapshot 當 master 收到 snapshot 請求後，首先將相關文件的 chunks 的所有未完成的租約撤銷掉，保證對這些 chunk 上的任何後續的寫入都需要請 master 獲取新的租約的持有者，這樣 master 就有機會在這之前先創建 chunk 拷貝。

在租約被撤銷 / 過期後 master 將 snapshot 操作日誌寫到到本地磁碟，修改內存狀態，複製一份源文件 / 目錄樹的 metadata。

新創建的 snapshot 文件仍指向源文件的 chunk，在 snapshot 操作完成後，當有一個 client 想要向 chunk 寫入內容時會向 master 請求當前租約的持有者。此時 master 可以發現對應 chunk 的引用計數大於 1，然後 master 會延遲響應 client，首先選擇一個新的 chunk handle，然後告知擁有 chunkC 副本的所有 chunkserver 創建一個新的 chunk，每個 chunkserver 在本地進行文件複製而無需經過網路（GFS 系統內磁碟速度是網路的三倍，這裡比的應該是讀文件？）接著 master 會在新的 chunk 上授予新的租約返回給 client，後續在複製出來的 chunk 上正常寫入即可。

master 操作#

master 執行所有 namespace 相關的操作，管理系統內所有 chunk 的副本，決定在什麼位置創建新的 chunk 及其副本，協調各種系統級別的活動，保證所有的 chunk 備份完整，平衡 chunkserver 的負載，回收未使用的存儲等。

命名空間管理和鎖#

master 上許多操作都很耗時，為了避免單個耗時的操作對其他操作的影響 GFS 允許同時執行多個操作，通過對 namespace 上的某個 region 加鎖來確保正確的串行化。

和傳統的文件系統不同 GFS 中目錄本身沒有一個單獨數據結構（相對於傳統的文件系統，存儲目錄下的文件等），也不支持文件 / 目錄別名（軟 / 硬鏈接）。邏輯上相當於只有一張表包含了文件全名到 metadata 信息的映射表，利用前綴壓縮這個表可以在內存中高效的表示。

namespace 中的每個節點（文件名或者目錄名的絕對路徑）有一個相關聯的讀寫鎖，master 在執行每個操作前需要獲取這些鎖的某個集合。比如某個操作和 /d1/d2/.../dn/leaf 相關聯則需要獲取 /d1, /d1/d2, ..., /d1/d2/.../dn 的讀鎖和 /d1/d2/.../dn/leaf 的讀鎖或者寫鎖（根據對應操作的需要），這裡路徑上的葉子節點在不同的操作中可能是一個文件也可能是目錄。

考慮一個場景：在 /home/user 被 snapshot 到 /save/user 過程中創建 /home/user/foo，首先 snapshot 操作會獲取 /home 和 /save 的讀鎖以及 /home/user 和 /save/user 的寫鎖，而 /home/user/foo 的創建需要 /home 和 /home/user 的讀鎖以及 /home/user/foo 的寫鎖，這兩個操作會在 /home/user 上產生鎖衝突，文件創建操作無需在 /home/user 上加寫鎖，因為 GFS 的 "目錄" 沒有任何需要修改的信息，只需要在目錄上加讀鎖就足夠避免其被刪除 / 重命名或者被 snapshot 的情況。

這種鎖模式可以很好地支持在同目錄下的並發變更操作，比如在同一目錄下並發創建多個文件。由於 namespace 下可以用很多節點，讀寫鎖對象都是惰性創建的並且一旦不再使用就立即刪除。

為了避免死鎖，所有的鎖都按照一致的順序申請：先按照在 namespace 中的層級排序，然後同級以字典序排序。

副本位置#

一個 GFS 集群中可能有數百上分佈在不同機架上的 chunkserver，而這些 chunkserver 又被來自於相同或不同機架上的數百個 client 訪問，不同機架上的機器進行通信可能要跨過一個或者多個交換機。而機架本身的輸入輸出帶寬可能比機架上所有機器的帶寬之和要小。

chunk 副本的選擇策略服務於兩個目標：最大化數據的可靠性和可用性，最大化網路帶寬利用。

將副本分散到所有機器上僅能夠避免磁碟或者機器故障並且最大化利用每台機器的網路帶寬，同時也需要分散到不同的機架，以保證在整個機架不可用（共享資源故障 / 交換機 / 電源故障等）的情況下 chunk 仍有可用的副本（保證可用性），而且對一個 chunk 的讀取能夠利用到多個機架的總帶寬，但另一方面，寫入數據必須在多個機架之間傳輸，這是需要取捨權衡的點。

副本的創建、重做（複製）和平衡#

chunk 副本會在三種情況下被創建：chunk 創建，重新複製（re-replication），重新平衡。

當 master 創建一個 chunk 時會選擇副本的存放位置，主要考慮幾個因素：

1. 存放在磁碟利用率低於平均值的 chunkserver 上，這樣長時間以後所有 chunkserver 的磁碟利用率會相對均衡。
2. 限制每個 chunkserver 上最近創建副本的數量，因為一般文件創建後就會有較大流量的寫入，需要避免在這種情況下的網路擁擠。
3. 儘可能的將 chunk 分散到不同機架上的 chunkserver。

當一個 chunk 的可用副本數量低於用戶指定的目標時，比如 chunkserver 不可用或者是磁碟故障導致副本損壞等導致可用副本數量減少，或者用戶增加了指定的副本數量，master 會儘快的進行重新複製。

每個需要重新複製的 chunk 會根據以下條件劃分優先級：

1. 離複製目標還有多遠，比如丟失了兩個副本的 chunk 會比丟失了一個副本的 chunk 的優先級高。
2. 優先複製當前存活的文件而非最近要被刪除的文件。
3. 為了最小化故障對運行中應用的影響，阻塞 client 請求的 chunk 的優先級會被提高。

master 會選取優先級最高的 chunk 下發指令到選定的 chunkserver 直接從當前存在的有效的副本上複製數據，新的副本的位置選擇和 chunk 創建時的選擇規則一致。

為了避免副本複製時的流量淹沒客戶端流量，master 會限制集群內和每個 chunkserver 上執行複製的數量，此外每個 chunkserver 會通過限制向源 chunkserver 發送的請求來限制副本複製的帶寬佔用。

master 還會定期的進行副本的重新平衡，master 會檢查當前副本的分佈情況，通過將副本移動到更合適的磁碟空間上來進行負載均衡。新的副本的位置的選擇策略同上，在新副本創建後由於副本數量多出來了，master 需要選擇當前存在的副本進行刪除，一般傾向於選擇空閒空間低於平均值的 chunkserver 來平衡磁碟空間使用。

垃圾收集#

在一個文件被刪除後 GFS 並不立即回收其佔用的物理空間，而是在常規的 GC 期間進行文件和 chunk 級別的回收，這種方式使整個系統更加簡單和可靠。

當應用刪除文件時 master 立即記錄刪除日誌，然後將其重命名成一個包含有刪除時間的隱藏文件。在 master 常規掃描文件系統時會移除已經存在了三天以上的隱藏文件，在移除之前，隱藏文件一樣可以通過其特殊文件名進行訪問，也可以通過將其重命名回普通文件名實現刪除回滾。

當隱藏文件從 namespace 中移除後其內存中的 metadata 也會一並擦除，這樣相當於切斷了其跟 chunk 的聯繫。在常規的 chunk namespace 掃描期間 master 會標記孤兒 chunk（即哪些不會從任何文件上訪問到的 chunk）並且將這些 chunk 的 metadata 擦除。在 master 和 chunkserver 通信的 HeartBeat 消息中 chunkserver 會報告自己擁有的 chunk 的一個子集，然後 master 會在響應中標記那些在 master 中沒有 metadata 的 chunk，然後 chunkserver 就可以隨時將其副本刪除了。

這種 GC 方式的優點：

1. 在大規模分佈式系統中這種實現方式很簡單且可靠，每個 chunk 的創建在某些 chunkserver 上可能會失敗，副本刪除的消息可能會丟失，但是 master 不必重試或記住這些失敗的副本。
2. 所有存儲空間的回收都是在後台分期分批次進行的，而且是在 master 相對空閒的時期，在平時 master 可以更加迅速的響應要緊的 client 的請求。
3. 延遲回收空間的方式可以防止意外導致的不可逆刪除。

延遲刪除的主要的缺點是會妨礙用戶在存儲緊缺時候的空間調整工作（比如想刪除一部分文件），應用重複的創建和刪除臨時文件並不能直接重用存儲。解決方式是，如果一個已經刪除的文件被再次刪除，系統內部會加快對應存儲的回收進程，同時允許應用在不同的 namespace 上使用不同的副本和回收策略，比如用戶可以指定在某個目錄樹下的所有 chunk 都不需要存儲副本，並且任何文件刪除都立即執行，在文件系統上做不可恢復的移除。

檢查過時副本#

副本可能會由於 chunkserver 下線導致過時和丟失變更，對每個 chunk master 維護一個版本號來區別最新的副本和過時的副本，當 master 在 chunk 上授予租約時會增加其版本號，並告知所有其當前最新的副本，然後 master 和這些副本會將新的版本號持久化，以上步驟發生在 client 寫 chunk 之前。

如果有副本當前不可用則其 chunkversion 就會落後，在 chunkserver 重啟時 master 會檢測到其擁有過時的副本然後通知 chunkserver 對應過時的 chunk 及最新的版本號。如果 master 檢測到比當前記錄高的 chunkversion 可以認為是在授予租約失敗的過程中產生的（租約失敗也不可能有寫入），然後可以直接將這個較高的 chunkversion 修改為當前版本。

master 在常規的 GC 期間移除過時的副本，在返回給 client chunk 相關信息時會無視過時的副本。作為另一重保證：master 在告知 client 哪個 chunkserver 持有租約，或者指示一個 chunkserver 從另一個 chunkserver 上複製數據時，會包含 chunkversion，然後 client 和 chunkserver 在執行操作時會校驗 chunkverison 以保證訪問的是最新的數據。

容錯和診斷#

GFS 系統設計的最大挑戰之一是應對頻繁的組件故障。組件的質量和數量導致故障是一種常態而非異常：即不能完全信任機器和磁碟。組件故障可能導致系統不可用甚至數據損壞。

高可用#

一個 GFS 集群中有數百個服務，其中一些可能在任意時間不可用 GFS 通過兩個簡單而有效的方式保證系統的高可用性：快速恢復和副本（複製）。

快速恢復#

master 和 chunkserver 都被設計成無論如何終止都能夠在幾秒鐘之內恢復狀態並啟動。事實上 GFS 也並不區分正常終止和異常終止，伺服器例行關機時就直接把進程 kill 掉 client 或者其他服務在其未完成的請求超時時會短暫的停頓一下然後重新連接重啟的服務進行重試。

chunk 複製#

chunk 複製以上說過很多了 master 會在 chunkservers 下線或者檢測副本損壞時（通過校驗和）通過 clone 操作複製。此外 GFS 還會使用奇偶校驗或者擦除碼以滿足越來越多的只讀存儲需求。

master 複製#

為了保證可靠性 master 的狀態也會被複製，操作日誌和 checkpoint 會被複製到多台機器上，每個狀態變更操作只有在日誌已經被刷新到本地磁碟和所有的 master 副本上以後才能被認為是提交了的。

為了保證簡單，只有一個 master 負責所有的變更操作和後台活動如 GC 等，當 master 進程故障時，可以幾乎瞬間重啟，如果 master 的機器或者磁碟產生故障 GFS 以外的監控基礎設施會啟動一個新的 master 進程使用操作日誌副本繼續進行處理。而 client 只會使用一個標準名稱比如 gfs-test 來訪問 master 而不是 IP 或者其他會根據機器修改而變更的名稱。

此外 master 的副本即 shadow master 也可以提供對文件系統的只讀訪問，即使是 primary master 下線的時候，但是 master 副本相對於 primary 可能會稍微滯後幾分之一秒。對於不經常修改的文件，或者在實時性要求相對較弱的情況下，這樣方式可以提升讀的可用性。事實上文件內容是從 chunkserver 上讀取的應用根本感知不到文件內容是否是過時。只有目錄內容或者是權限控制信息這種 metadata 會在一個很小的時間窗口內過期。

每個 shadow master 讀取和執行操作日誌副本上的遞增操作，並且像 primary 一樣按照順序執行並修改自己的內存狀態。和 primary master 類似 shadow master 在啟動時輪詢所有的 chunkserver 來定位所有 chunk 副本的信息，後續通過頻繁的的握手消息交換來監控他們的狀態。除此以外，只有創建和刪除副本這種由 primary 做出的決定導致的副本位置更新上才會依賴 primary master。

數據完整性#

每個 chunkserver 使用校驗和檢查數據是否損壞。一個 GFS 集群可能有分佈在數百台機器上的數千個磁碟，在讀或寫時數據損壞和丟失都很常見，此時可以使用其他的 chunk 副本上進行恢復。通過比較不同 chunkserver 上的副本來檢查數據損壞不太實際。此外，在一些操作比如 atomic record append 中並不能保證所有副本完全一致，但這些副本也是合法的。因此每個 chunkserver 必須通過維護校驗和獨立驗證數據的完整性。

每個 chunk 會分割成 64KB 的 block，每個 block 有一個 32bit 的校驗和，此校驗和會被保存在內存和持久化到日誌中與用戶數據分離。對於讀取請求，在返回數據給 client 或者 chunkserver 之前 chunkserver 會驗證讀取範圍內的 block 的校驗和，如果校驗失敗 chunkserver 不會將損壞的數據發送出去，而是返回一個錯誤給請求者然後向 master 報告錯誤。請求者則重新向其他副本請求數據，master 會執行副本重做（此時有效副本數量不足），然後通知校驗出錯的 chunkserver 刪除它的副本。

計算校驗和對讀性能影響很小，因為大多數的讀請求的跨度都只有很少的 block，因此只需要相關的很小的一部分額外數據用於校驗，而且 GFS 的 client 代碼會儘量按照 block 的大小進行對齊讀取以減少這部分的開銷。此外校驗和的查找和校驗本身沒有任何的 I/O 開銷，而且校驗和的計算通常可以和 I/O 操作重疊（讀文件的時候就順便計算了）。

對於 chunk 的追加寫操作校驗和計算是高度優化的，因為這項工作在負載中佔據主導地位。我們只會增量更新最後一個不完整的 block，然後對之後追加寫入的新的 block 計算新的校驗和。即使最後一個不完整的 block 的數據已經損壞，雖然現在檢查不到，但是新的校驗會跟數據不匹配，在下次讀取這一塊數據的時候就能夠檢測到。

作為對比，如果一個寫操作覆寫 chunk 中已經存在的範圍，我們必須先讀取覆寫範圍內的第一個到最後一個 block 做校驗，然後再執行寫入操作，最後計算和記錄新的校驗和。

在空閒期間 chunkserver 會掃描和校驗那些不活躍 chunk 的數據，一旦檢查到損壞 master 會創建新的副本並將損壞的副本刪除。這樣可以避免在 master 不知情的情況下，不活躍的 chunk 悄悄損壞，導致沒有足夠的有效副本。

診斷工具#

詳細且詳盡的診斷日誌在問題隔離、調試和性能分析上都提供了不可估量的幫助 GFS 服務會產生很多診斷日誌，包含關鍵事件（比如 chunkserver 上線或者下線）和所有的 RPC 請求及響應。這些日誌隨時可以刪除，但我們總是儘量在存儲空間允許的情況下保留足夠的久。

RPC 日誌中包含在通信線路上傳輸的的確切的請求和響應，通過匹配請求和響應日誌以及在不同機器上的記錄，可以重構出整個交互的歷史來診斷一個問題。日誌也可以用於負載測試追蹤和性能分析。

日誌對性能的影響很小，因為這些日誌都是順序且異步寫的。大多數最近的事件也都會保存在內存中用於持續在線監控。

經驗#

業務系統總是嚴謹可控的但用戶不是，所以需要更多的基礎設施來防止用戶間的相互干預。

我們的很多問題都跟磁碟和 Linux 相關，許多磁碟對驅動聲明自己支持一系列的 IDE 協議但是事實上只能可靠響應最近期的一個版本。由於協議在多個版本間非常相似，大部分情況下驅動會正常工作，但偶爾產生的錯誤會導致驅動和內核的狀態不一致，導致數據慢慢被損壞，這也是我們使用校驗和的動機，我們也同時修改了內核以修改這些協議錯誤問題。

早期我們在使用 Linux2.2 內核時發現了一些問題 fsync 的耗時跟文件整體大小成比例而非寫入的那一部分。對於大量級的操作日誌，這是一個問題，特別是在實現 checkpoint 之前。我們先是使用同步寫處理這個問題，後續遷移到 Linux2.4。

另一個 Linux 的問題是單一（全局）讀寫鎖，地址空間內的任何線程在磁碟換入內存（讀鎖）或者修改 mmap 映射的內存地址（寫鎖）都需要獲取這個鎖。我們發現即使在系統負載很低的情況下會有短暫的超時，然後查找資源瓶頸和間歇性的硬體故障，最終我們發現，是這個單一（全局）鎖阻塞了網路主線程將新數據映射到內存，因為磁碟線程正在將之前映射的內存換入。由於我們主要是受到網路接口帶寬的限制而非內存複製帶寬，我們通過將 mmap 替換為 pread 解決了這個問題。

結論#

GFS 很成功的支持了我們的存儲需求，並且作為搜索和業務數據處理的存儲平台在 Google 中被廣泛應用。