Google 檔案系統簡介#

設計目標#

設計一個分散式檔案系統，用於儲存超大檔案（TB 及以上等級）。該系統需具備可擴展性（Scalability）、可靠性（Reliability）與高可用性（High Availability）。

什麼是 Google 檔案系統（GFS）？#

GFS 是 Google 為其大規模資料密集型應用所開發的可擴展分散式檔案系統（Distributed File System）。

背景#

GFS 專為大型資料集的批次處理（Batch Processing）而設計，著重於系統對系統的互動，而非使用者對系統的互動。Google 在設計 GFS 時有以下目標：

  • 可擴展性（Scalable）：GFS 應能在由普通硬體（Commodity Hardware）建構的大型系統上可靠運行。
  • 容錯性（Fault-tolerant）：設計必須能充分容忍硬體與軟體故障，使應用層服務在任何可能的故障組合下仍能持續運作。
  • 大型檔案：GFS 中儲存的檔案通常非常龐大，數 GB 的檔案十分常見。
  • 大量循序讀取與少量隨機讀取：工作負載主要由兩種讀取組成——大量串流讀取（Streaming Reads）與少量隨機讀取（Random Reads）。
  • 循序寫入（Sequential Writes）：工作負載也包含大量循序寫入，將資料附加到檔案尾端。檔案一旦寫入，就很少再修改。
  • 非為小型資料最佳化：系統支援小型隨機讀寫，但並未對此做最佳化。
  • 高併發存取（Concurrent Access）：併發存取的程度很高，大量併發附加操作尤為常見，通常伴隨著併發讀取。
  • 高吞吐量（High Throughput）：GFS 應針對資料讀取的高持續吞吐量做最佳化，並將其優先於延遲（Latency）。這並非說延遲不重要，而是 GFS 需要針對大量資料的高效能讀取與附加操作做最佳化。

GFS 的使用情境#

GFS 是為 Gmail 或 YouTube 等大型分散式資料密集型應用所建構的分散式檔案系統。

  • 最初是為了儲存 Google 大規模爬取與索引系統所產生的資料而建造。
  • Google 的 BigTable 使用 GFS 來儲存日誌（Log）與資料檔案。

API#

GFS 不提供標準的 POSIX API，而是提供使用者層級的 API。在 GFS 中，檔案以目錄階層結構組織，並以路徑名稱識別。GFS 支援以下常見的檔案系統操作：

操作說明
create建立新的檔案實例
delete刪除檔案實例
open開啟指定檔案並回傳控制代碼（Handle）
close關閉指定控制代碼所對應的檔案
read從指定檔案與偏移量讀取資料
write將資料寫入指定檔案與偏移量

此外，GFS 支援兩種特殊操作：

  • 快照（Snapshot）：一種高效率地建立檔案或目錄樹當前狀態副本的方式。
  • 附加（Append）：允許多個客戶端同時對同一檔案附加資料，同時保證原子性（Atomicity）。這對於實作多路合併結果及生產者—消費者佇列（Producer-Consumer Queues）非常有用，多個客戶端可在不需要額外鎖定的情況下同時附加資料。

高層架構#

一個 GFS 叢集（Cluster）由一個主節點（Master）和多個區塊伺服器（ChunkServer）組成，並由多個客戶端存取。

區塊（Chunk）#

區塊複製

由於 GFS 中儲存的檔案通常非常大，GFS 將檔案切分為多個固定大小的區塊，每個區塊大小為 64 MB。

區塊控制代碼（Chunk Handle）#

每個區塊由一個不可變且全域唯一的 64 位元 ID 識別，稱為區塊控制代碼（Chunk Handle）。這允許 2^64 個唯一區塊。若每個區塊為 64 MB，總儲存空間將超過 10^9 EB。

由於檔案被切分為區塊，GFS 的工作就是提供從檔案到區塊的對應，然後支援標準的檔案操作，將其對映到個別區塊上的操作。

叢集（Cluster）#

GFS 組織為一個簡單的電腦網路，稱為叢集。所有 GFS 叢集包含三種實體：

  1. 單一主節點伺服器（Master Server）
  2. 多個區塊伺服器（ChunkServer）
  3. 眾多客戶端（Client）

主節點儲存系統的所有中繼資料（Metadata），而區塊伺服器儲存實際的檔案資料。

GFS 的高層架構

區塊伺服器（ChunkServer）#

區塊伺服器將區塊作為一般 Linux 檔案儲存在本機磁碟上，並根據區塊控制代碼與位元組範圍來讀取或寫入區塊資料。

為了可靠性，每個區塊會被複製到多個區塊伺服器。預設情況下，GFS 儲存三個副本（Replica），但可依據檔案設定不同的複製因子（Replication Factor）。

主節點（Master）#

主節點伺服器是 GFS 叢集的協調者，負責追蹤檔案系統中繼資料：

  1. 主節點儲存的中繼資料包括：
    • 每個檔案的名稱與目錄
    • 每個檔案到其區塊的對應
    • 區塊的當前位置
    • 存取控制資訊
  2. 主節點也控制系統範圍的活動，如區塊租約管理（Chunk Lease Management）、孤立區塊的垃圾回收（Garbage Collection），以及區塊伺服器之間的區塊遷移（Chunk Migration）。主節點在區塊建立時分配區塊控制代碼。
  3. 主節點透過心跳訊息（HeartBeat Messages）定期與每個區塊伺服器通訊，向其傳送指令並收集其狀態。
  4. 為了效能與快速隨機存取，所有中繼資料都儲存在主節點的主記憶體中，包括整個檔案系統命名空間以及所有名稱到區塊的對應。
  5. 為了容錯性並處理主節點當機，所有中繼資料變更都會寫入磁碟上的操作日誌（Operation Log），此日誌也會複製到遠端機器。操作日誌類似於日誌檔（Journal），檔案系統的每個操作都會記錄其中。
  6. 主節點是單點故障（Single Point of Failure），因此會將資料複製到多台遠端機器上，以便在故障時能快速恢復。
  7. 擁有單一集中式主節點的好處在於它擁有檔案系統的全域視野，因此能做出最佳的管理決策，例如區塊放置的相關決策。

客戶端（Client）#

客戶端是向 GFS 發出讀取或寫入請求的實體。GFS 客戶端函式庫（Client Library）被連結到每個使用 GFS 的應用程式中。此函式庫與主節點通訊以處理所有中繼資料相關的操作，如建立或刪除檔案、查詢檔案等。要讀取或寫入資料時，客戶端直接與持有資料的區塊伺服器互動。

客戶端與區塊伺服器都不會快取檔案資料。客戶端快取幾乎沒有好處，因為大多數應用程式都在串流處理大型檔案，或者工作集太大以致無法快取。區塊伺服器依賴 Linux 的緩衝區快取（Buffer Cache）將頻繁存取的資料保存在記憶體中。

單一主節點與大區塊大小#

單一主節點#

擁有單一主節點大幅簡化了 GFS 的設計，使主節點能利用全域知識做出精密的區塊放置與複製決策。然而，GFS 將主節點在讀寫操作中的參與降到最低，以免其成為瓶頸。客戶端永遠不會透過主節點讀寫檔案資料。相反地，客戶端會向主節點詢問應聯繫哪些區塊伺服器，在有限時間內快取此資訊，然後直接與區塊伺服器互動進行後續操作。

區塊大小（Chunk Size）#

區塊大小是關鍵的設計參數之一。GFS 選擇了 64 MB，遠大於一般檔案系統的區塊大小（通常約 4 KB）。使用大區塊大小的優勢包括：

  1. 由於 GFS 設計用於處理大型檔案，小區塊大小意義不大，因為每個檔案會產生大量區塊的對應表。
  2. 主節點管理中繼資料並負責檔案分配，在區塊讀取、修改或刪除時都會參與。小區塊大小會顯著增加主節點需管理的資料量，也會增加需傳給客戶端的資料量，產生額外的網路流量。
  3. 大區塊大小減少了主節點上儲存的中繼資料量，使主節點能將所有中繼資料保存在記憶體中，從而大幅降低控制操作的延遲。
  4. 大區塊大小減少了客戶端與主節點之間的頻繁通訊需求。客戶端可以快取大型檔案所有區塊位置的相關資訊。客戶端中繼資料快取設有逾時機制，以降低快取過期資料的風險。
  5. 大區塊大小使得 TCP 連線可長時間保持開啟，攤銷建立 TCP 連線的時間成本。
  6. 大區塊大小簡化了區塊伺服器的管理，例如檢查哪些區塊伺服器接近容量上限或負載過重。
  7. 大區塊大小為大量資料的循序讀取與附加提供了高效能。

延遲空間分配（Lazy Space Allocation）#

每個區塊副本作為普通 Linux 檔案儲存在區塊伺服器上。GFS 在建立區塊時不會分配整個 64 MB 的磁碟空間，而是在客戶端附加資料時，由區塊伺服器延遲地擴展區塊。這種延遲空間分配策略避免了因內部碎片化（Internal Fragmentation）而浪費空間。例如，若分配了 64 MB 的區塊但只填入 20 MB，剩餘空間就會閒置。

大區塊大小的一個缺點是對小型檔案的處理。由於小型檔案只有一個或少數幾個區塊，儲存這些區塊的區塊伺服器在大量客戶端存取同一檔案時可能成為熱點（Hotspot）。為應對此情境，GFS 以較高的複製因子儲存此類檔案，並在存取這些檔案的應用程式啟動時加入隨機延遲。

中繼資料（Metadata）#

主節點儲存三種類型的中繼資料：

  1. 檔案與區塊的命名空間（Namespace），即目錄階層結構
  2. 檔案到區塊的對應
  3. 每個區塊副本的位置

主節點管理中繼資料有三個面向：

  1. 主節點將所有中繼資料保存在記憶體中。
  2. 前兩種類型（命名空間和檔案到區塊的對應）也持久化儲存在主節點的本機磁碟上。
  3. 第三種類型（區塊副本位置）不做持久化儲存。

在記憶體中儲存中繼資料#

由於中繼資料儲存在記憶體中，主節點操作非常快速。此外，主節點可以輕鬆且高效地定期在背景掃描其完整狀態。此定期掃描用於實作三項功能：

  1. 區塊垃圾回收
  2. 區塊伺服器故障時的重新複製（Re-replication）
  3. 區塊遷移以平衡各區塊伺服器間的負載與磁碟空間使用

這種純記憶體方式的一個潛在問題是，區塊數量及整個系統的容量受限於主節點的記憶體大小。但在實務上，這並非嚴重問題。主節點對每個 64 MB 區塊的中繼資料不到 64 位元組。大多數區塊都是滿的，因為大多數檔案包含許多區塊，只有最後一個可能未完全填滿。同樣地，檔案命名空間資料通常也不超過每檔案 64 位元組，因為主節點使用前綴壓縮（Prefix Compression）來緊湊儲存檔案名稱。

若需要支援更大的檔案系統，為主節點增加額外記憶體的成本相對於將中繼資料儲存在記憶體中所獲得的簡潔性、可靠性、效能與彈性而言，是很小的代價。

區塊位置（Chunk Location）#

主節點不保留哪些區塊伺服器擁有特定區塊副本的持久化記錄。相反地，主節點在啟動時詢問每個區塊伺服器其所持有的區塊，以及每當區塊伺服器加入叢集時再次詢問。之後，主節點透過控制所有區塊放置並以定期心跳訊息監控區塊伺服器狀態來保持資訊的即時性。

透過讓區塊伺服器作為每個區塊位置的最終真實來源（Source of Truth），GFS 消除了主節點與區塊伺服器之間同步的問題。在主節點上維護一致的區塊位置視圖並無好處，因為區塊伺服器上的錯誤可能導致區塊自發消失（例如磁碟損壞、區塊伺服器重新命名或故障等）。在擁有數百台伺服器的叢集中，這類事件經常發生。

操作日誌（Operation Log）#

讀取操作的剖析

主節點維護一份操作日誌，包含命名空間與檔案到區塊的對應，並儲存在本機磁碟上。此日誌記錄所有中繼資料變更的歷史紀錄。操作日誌對 GFS 非常重要，它包含中繼資料的持久化記錄，並作為定義併發操作順序的邏輯時間軸（Logical Timeline）。

為了容錯與可靠性，此操作日誌會複製到多台遠端機器上，且中繼資料變更在持久化到所有副本之前不會對客戶端可見。主節點會批次處理多筆日誌記錄後再一次刷新（Flush），以減少刷新與複製對整體系統吞吐量的影響。

重啟時，主節點可透過重播操作日誌來還原其檔案系統狀態。此日誌必須保持小型以最小化啟動時間，這透過定期建立檢查點（Checkpoint）來實現。

檢查點（Checkpointing）#

主節點的狀態會定期序列化到磁碟並複製，以便在恢復時，主節點可將檢查點載入記憶體、重播操作日誌中的後續操作，然後很快地恢復服務。為進一步加速恢復並提升可用性，GFS 以緊湊的 B 樹（B-tree）類似格式儲存檢查點，可直接映射到記憶體中並用於命名空間查詢，無需額外解析。

檢查點過程可能耗時，因此為避免延遲進行中的變更操作（Mutation），主節點會切換到新的日誌檔案，並在獨立的執行緒中建立新的檢查點。新的檢查點包含切換前的所有變更。

主節點操作#

主節點執行所有命名空間操作，並在整個系統中管理區塊副本。其負責的工作包括：

  • 做出副本放置決策
  • 建立新區塊及其副本
  • 確保區塊依據複製因子被完整複製
  • 在所有區塊伺服器之間平衡負載
  • 回收未使用的儲存空間

命名空間管理與鎖定#

主節點透過對命名空間區域取得鎖定來確保適當的序列化，並允許多個操作同時在主節點上執行。GFS 沒有類似 i-node 的目錄與檔案樹狀結構，而是使用雜湊表（Hash Map）將檔案名稱對應到其中繼資料，並對雜湊表的每個節點套用讀寫鎖（Reader-Writer Locks）來同步。

鎖定機制的運作方式如下：

  • 每個絕對檔案名稱或絕對目錄名稱都有關聯的讀寫鎖。
  • 每個主節點操作在執行前會取得一組鎖定。
  • 要操作 /dir1/dir2/leaf，需要取得以下鎖定：
    • /dir1 的讀取鎖
    • /dir1/dir2 的讀取鎖
    • /dir1/dir2/leaf 的讀取或寫入鎖
  • 此機制立即阻止對同一葉節點的併發寫入，但同時允許對同一目錄的併發修改。
  • 建立檔案不需要父目錄的寫入鎖；父目錄名稱上的讀取鎖即足以保護其不被刪除、重新命名或建立快照。
  • 檔案名稱上的寫入鎖可防止建立多個同名檔案的嘗試。
  • 鎖定依一致的順序取得以防止死鎖（Deadlock）：先按命名空間樹的層級排序，同一層級內再按字典順序排序。

副本放置（Replica Placement）#

為確保最大的資料可用性與完整性，主節點將副本分佈在不同的機架（Rack）上，以便在機架故障時客戶端仍能讀寫。由於機架的進出頻寬可能低於個別機器頻寬的總和，將資料放置在不同機架有助於客戶端利用多機架讀取。對於寫入操作，多機架實際上是不利的，因為資料需要傳輸更長的距離。這是 GFS 有意做出的取捨。

副本建立與重新複製#

主節點的目標是將副本放置在磁碟使用率低於平均值的伺服器上、將副本分散到不同機架，並減少每個區塊伺服器上「近期」建立的數量（即使寫入本身代價不高，但其後會伴隨大量寫入流量），以避免額外負載。

當可用副本數量低於使用者指定的複製因子時（由於伺服器上的資料損壞或副本不可用），區塊需要盡快重新複製。主節點不會一次重新複製所有此類區塊，而是依優先順序排定，以防止這些複製操作成為瓶頸。每台伺服器的重新複製頻寬也受到限制，以免影響客戶端請求。

區塊的重新複製優先順序如何決定？

  • 依據區塊離其複製目標的差距程度排定優先順序。例如，失去兩個副本的區塊優先於只失去一個副本的區塊。
  • GFS 優先處理存活檔案的區塊，而非屬於最近刪除檔案的區塊。已刪除的檔案不會立即移除，而是暫時重新命名並在數天後進行垃圾回收。

副本重新平衡（Replica Rebalancing）#

主節點定期重新平衡副本以實現負載平衡與更好的磁碟空間利用率。它可能將副本從一個區塊伺服器移至另一個，以使伺服器的磁碟使用率更接近平均值。任何新加入叢集的區塊伺服器會由主節點逐步填充，而非以大量寫入操作灌入。

過期副本偵測（Stale Replica Detection）#

區塊副本可能因區塊伺服器故障而變得過期（Stale），即伺服器停機期間錯過了對該區塊的變更。對於每個區塊，主節點維護一個區塊版本號（Chunk Version Number），以區分最新與過期的副本。每當主節點授予租約（Lease）時，就會遞增區塊版本號並通知所有最新的副本。主節點與這些副本都會在其持久化狀態中記錄新的版本號。

若某個區塊伺服器在變更期間停機，其上的區塊副本就會變得過期並擁有較舊的版本號。主節點會在區塊伺服器重啟並回報其區塊集合及對應版本號時偵測到此情況。主節點會在定期垃圾回收時移除過期副本。

過期副本不會在客戶端向主節點查詢區塊位置時被回傳，也不會參與變更操作。然而，由於客戶端會快取區塊位置，在資料重新同步前可能會從過期副本讀取。此影響很小，因為對區塊的大多數操作都是僅附加（Append-only）。這意味著過期副本通常回傳的是區塊的提前結束（Premature End of Chunk），而非過時的資料。

讀取操作的剖析#

客戶端應用程式與 GFS 叢集的典型讀取互動流程如下：

  1. 首先，客戶端將應用程式指定的檔案名稱與位元組偏移量轉換為檔案內的區塊索引。由於區塊大小固定，此計算很簡單。
  2. 客戶端向主節點發送 RPC 請求，包含檔案名稱與區塊索引。
  3. 主節點回覆區塊控制代碼及持有該區塊之副本的位置。客戶端以檔案名稱與區塊索引作為鍵值來快取此中繼資料，後續存取資料時使用。
  4. 客戶端向其中一個副本（最近的那個）發送請求，指定區塊控制代碼與該區塊內的位元組範圍。
    • 後續對同一區塊的讀取無需再與主節點互動，直到快取資訊過期或檔案被重新開啟。
    • 實際上，客戶端通常在同一請求中要求多個區塊，主節點也可能附帶回傳緊隨其後的區塊資訊。
  5. 副本區塊伺服器回覆所請求的資料。
  6. 從上述流程可見，主節點僅在開始時參與，之後完全不介入，實現了控制流與資料流的分離（Separation of Control and Data Flows），這對維持檔案存取的高效能至關重要。

寫入操作的剖析#

寫入操作的剖析

什麼是區塊租約（Chunk Lease）？#

為了防止兩個不同副本上的併發寫入，GFS 使用區塊租約機制。當請求對某個區塊進行變更（寫入、附加或刪除操作）時，主節點找到持有該區塊的區塊伺服器，並授予其中一個 60 秒的區塊租約。持有租約的伺服器稱為主要副本（Primary），負責為該區塊上所有當前待處理的併發變更提供序列順序。每個區塊在任何時間只有一個租約，因此若兩個寫入請求到達主節點，兩者都會看到指向同一主要副本的同一個租約。

全域排序由區塊租約的順序與主要副本所決定的順序共同提供。主要副本可在需要時請求租約延長。當主節點授予租約時，會遞增區塊版本號並通知所有包含該區塊的副本新的版本號。

資料寫入#

實際的資料寫入分為兩個階段：

  • 傳送階段（Sending）：首先，客戶端取得副本清單，包含主要區塊伺服器與次要副本的識別資訊。客戶端將資料傳送到最近的副本，然後副本以鏈式方式將資料傳送給所有其他副本，以最大化頻寬與吞吐量。最終所有副本都收到資料，但尚未寫入檔案，資料暫存在快取中。
  • 寫入階段（Writing）：當客戶端收到所有副本已接收資料的確認後，向主要副本發送寫入請求，指定前一階段傳送的資料。主要副本負責寫入的序列化——為收到的所有寫入請求分配連續的序列號，按序列號順序將寫入套用到檔案，並按該順序將寫入請求轉發給次要副本。一旦主要副本收到所有次要副本的確認，就回應客戶端，寫入操作即完成。過程中任何階段的錯誤都會以重試處理，最終失敗時回傳錯誤給客戶端。

以下是資料傳輸的步驟分解：

  1. 客戶端向主節點詢問哪個區塊伺服器持有該區塊的當前租約以及其他副本的位置。
  2. 主節點回覆主要副本的身份及次要副本的位置。
  3. 客戶端將資料推送到最近的副本，然後副本以鏈式方式將資料傳送給所有其他副本。
  4. 一旦所有副本確認已收到資料，客戶端向主要副本發送寫入請求。主要副本為收到的所有變更分配連續序列號以提供序列化，並按序列號順序套用變更。
  5. 主要副本將寫入請求轉發給所有次要副本，它們按相同的序列號順序套用變更。
  6. 次要副本回覆主要副本表示已完成操作。
  7. 主要副本向客戶端回覆成功或錯誤訊息。

關鍵要點是資料流與控制流不同。資料從客戶端流向一個區塊伺服器，再從該區塊伺服器流向另一個區塊伺服器，直到儲存該區塊副本的所有區塊伺服器都收到資料。控制流（寫入請求）從客戶端流向該區塊的主要區塊伺服器，主要副本再將請求轉發給所有次要副本。這確保了即使主要副本同時收到多個併發寫入請求，它仍能控制寫入順序。所有副本的資料將以相同的順序寫入。區塊版本號用於偵測是否有任何副本持有未更新的過期資料（因為該區塊伺服器在某次更新期間停機）。

附加操作的剖析#

Record Append 操作以獨特的方式做了最佳化，使 GFS 區別於其他分散式檔案系統。在一般寫入中，客戶端指定資料要寫入的偏移量。對同一區域的併發寫入可能產生競爭條件（Race Condition），該區域最終可能包含來自多個客戶端的資料片段。然而，在 Record Append 中，客戶端只需指定資料，GFS 會以原子方式（即作為一段連續的位元組序列）至少一次地將資料附加到檔案中 GFS 選定的偏移位置，並將該偏移量回傳給客戶端。

Record Append 是一種改變區塊中繼資料內容的變更操作。當應用程式嘗試對區塊附加資料時，客戶端將資料推送到檔案最後一個區塊的所有副本，就像寫入操作一樣。當客戶端將請求轉發給主要副本時，主要副本檢查將記錄附加到現有區塊是否會使區塊大小超過其上限（區塊最大為 64 MB）。若超過，主要副本會將區塊填充到最大上限，命令次要副本執行相同操作，並請求客戶端嘗試附加到下一個區塊。若記錄可以放入最大大小限制內，主要副本將資料附加到其副本，告知次要副本在完全相同的偏移量處寫入資料，最終回覆客戶端成功。

若附加操作在任何副本上失敗，客戶端會重試該操作。因此，同一區塊的副本可能包含不同的資料，可能包括同一記錄的全部或部分重複。GFS 不保證所有副本在位元組層面完全相同；它只保證資料作為原子單元被至少寫入一次（At-Least-Once）。

flowchart TD
    A["客戶端（Client）發送\nRecord Append 請求"] --> B["將資料推送至所有副本\n（與寫入操作相同）"]
    B --> C["客戶端將請求轉發\n給主要副本（Primary）"]
    C --> D{"現有區塊是否有\n足夠空間？\n（≤ 64 MB）"}
    D -- "是" --> E["主要副本將資料\n附加至其副本"]
    E --> F["命令次要副本（Secondary）\n在相同偏移量處寫入"]
    F --> G{"所有次要副本\n寫入成功？"}
    G -- "是" --> H["回覆客戶端：成功"]
    G -- "否" --> I["客戶端重試操作\n（At-Least-Once 語義）"]
    D -- "否" --> J["主要副本將當前區塊\n填充至最大上限"]
    J --> K["命令次要副本\n執行相同填充操作"]
    K --> L["告知客戶端\n重試至下一個區塊"]
    L --> A

    style A fill:#4a90d9,color:#fff
    style H fill:#2d8659,color:#fff
    style I fill:#d94a4a,color:#fff
    style L fill:#d9a04a,color:#fff

GFS 一致性模型與快照#

GFS 一致性模型#

為保持簡單與高效，GFS 採用寬鬆的一致性模型（Relaxed Consistency Model）。

中繼資料操作（如檔案建立）是原子性的，由主節點獨佔處理。命名空間鎖定保證原子性與正確性，而主節點的操作日誌定義了這些操作的全域總序（Global Total Order）。

在資料變更中，寫入與附加操作之間有重要的區別：

  • 寫入操作指定變更應發生的偏移量。
  • 附加操作總是應用在檔案的尾端，偏移量由系統決定。

對同一位置的併發寫入不具可序列化性，可能導致檔案的損壞區域。對於附加操作，GFS 保證附加至少發生一次且具原子性（即作為一段連續的位元組序列）。系統不保證區塊的所有副本完全相同（部分可能有重複資料）。

快照（Snapshotting）#

快照是全域命名空間某個子樹在特定時間點的副本。GFS 客戶端使用快照來高效地分支同一資料的兩個版本。GFS 中的快照初始時是零複製（Zero-Copy）的，這意味著只有在客戶端請求修改區塊時才會進行資料複製。此機制稱為寫入時複製（Copy-on-Write）。

快照的運作流程：

  1. 當主節點收到快照請求時，首先撤銷要進行快照的檔案中所有區塊上的未完成租約，等待租約被撤銷或過期。
  2. 將快照操作記錄到操作日誌中。
  3. 透過複製來源目錄樹的中繼資料來建立快照。新建立的快照檔案仍指向原始區塊。
  4. 當客戶端請求寫入這些區塊之一時，主節點透過檢查其參考計數（Reference Count，此時大於一）來偵測到這是一個寫入時複製區塊。
  5. 此時主節點要求每個持有副本的區塊伺服器在本地複製該區塊。本地複製是為了避免透過網路複製區塊。
  6. 複製完成後，主節點為新副本發放租約，寫入操作即可進行。
flowchart TD
    A["主節點（Master）收到\n快照（Snapshot）請求"] --> B["撤銷目標檔案所有區塊的\n未完成租約（Lease）"]
    B --> C["等待租約被撤銷或過期"]
    C --> D["將快照操作記錄至\n操作日誌（Operation Log）"]
    D --> E["複製來源目錄樹的中繼資料\n（新快照指向相同區塊）"]
    E --> F["零複製完成\n（Zero-Copy Snapshot）"]
    F --> G{"客戶端請求寫入\n已快照的區塊？"}
    G -- "否" --> H["維持共享狀態\n（無額外複製）"]
    G -- "是" --> I["主節點檢查參考計數\n（Reference Count > 1）"]
    I --> J["要求區塊伺服器（ChunkServer）\n在本地複製該區塊"]
    J --> K["本地複製完成\n（避免網路傳輸）"]
    K --> L["主節點為新副本發放租約"]
    L --> M["寫入操作在新副本上進行"]

    style A fill:#4a90d9,color:#fff
    style F fill:#2d8659,color:#fff
    style H fill:#6b7b8d,color:#fff
    style M fill:#2d8659,color:#fff

容錯性、高可用性與資料完整性#

容錯性#

為使系統具有容錯性與可用性，GFS 使用兩個簡單的策略：

  1. 元件故障時的快速恢復
  2. 透過複製實現高可用性

以下說明 GFS 如何從主節點或副本故障中恢復：

主節點故障時：主節點作為單點故障，可能在短時間內使整個系統不可用。為應對此問題，所有套用在主節點上的操作都保存在操作日誌中。此日誌會建立檢查點並複製到多台遠端機器上，以便在恢復時主節點可將檢查點載入記憶體、重播操作日誌中的後續操作，並在短時間內恢復可用。GFS 依賴外部監控基礎設施偵測主節點故障並將流量切換到備用主節點伺服器。

影子主節點（Shadow Masters） 是主節點的副本，即使主要主節點停機也能提供唯讀的檔案系統存取。所有影子主節點透過讀取主要主節點的操作日誌並套用相同的更新序列來保持自身資訊的更新。影子主節點可能略微落後於主要主節點，但它們為非正在被積極修改的檔案或不介意取得略微過期中繼資料的應用程式提供了讀取可用性的提升。由於檔案內容是從區塊伺服器讀取的，應用程式不會觀察到過期的檔案內容。

主要副本故障時：若活躍的主要副本故障（或發生網路分區），主節點偵測到故障（因為沒有心跳），等待當前租約過期（以防主要副本仍在直接為客戶端提供服務），然後將租約分配給新節點。當舊的主要副本恢復時，主節點會透過檢查區塊版本號將其偵測為「過期」。主節點會挑選新節點取代過期節點，並在其能重新加入群組前進行垃圾回收。

次要副本故障時：若次要副本故障，所有客戶端操作都會在其上開始失敗。此時客戶端會重試幾次；若所有重試都失敗，則向主節點回報故障。這可能導致次要副本不一致，因為它錯過了部分變更。如前所述，過期節點將被主節點挑選的新節點取代，並最終被垃圾回收。

過期副本可能會被暴露給客戶端。應用程式開發者需自行處理這些過期讀取。GFS 不保證區塊讀取的強一致性。

透過區塊複製實現高可用性#

每個區塊都會複製到不同機架上的多個區塊伺服器。使用者可以為檔案命名空間的不同部分指定不同的複製等級，預設值為三。當區塊伺服器離線或主節點透過校驗和驗證偵測到損壞的副本時，主節點會複製現有副本以保持每個區塊被完整複製。

一個區塊只有在 GFS 來不及反應之前所有副本都遺失時才會不可逆地遺失。即使在這種情況下，資料也只是變得不可用而非損壞，這意味著應用程式會收到明確的錯誤而非損壞的資料。

透過校驗和實現資料完整性#

每個區塊伺服器使用校驗和（Checksum）來偵測儲存資料的損壞。區塊被分解為 64 KB 的區塊，每個區塊對應一個 32 位元的校驗和。校驗和與其他中繼資料一樣保存在記憶體中，並與日誌一起持久化儲存，與使用者資料分開。

  1. 讀取時：區塊伺服器在回傳任何資料給請求者之前，驗證與讀取範圍重疊的資料區塊的校驗和。因此區塊伺服器不會將損壞傳播到其他機器。若區塊與記錄的校驗和不符，區塊伺服器向請求者回傳錯誤並向主節點回報不匹配。請求者隨後從其他副本讀取，主節點則從另一個副本複製區塊。在有效的新副本就位後，主節點指示回報不匹配的區塊伺服器刪除其副本。
  2. 寫入時：區塊伺服器在執行寫入前，驗證與寫入範圍重疊的第一個和最後一個資料區塊的校驗和，然後計算並記錄新的校驗和。若區塊已損壞，區塊伺服器向請求者回傳錯誤並向主節點回報不匹配。
  3. 附加時：校驗和計算做了最佳化——不對最後一個區塊做校驗和驗證，而是僅增量更新最後一個部分區塊的校驗和，並為附加操作填充的全新區塊計算新的校驗和。如此一來，若最後一個部分區塊已經損壞（而 GFS 此時未能偵測），新的校驗和值將與儲存的資料不符，損壞將在下次讀取該區塊時被偵測到。

在閒置期間，區塊伺服器可以掃描並驗證不活躍區塊的內容，以防止不活躍但已損壞的區塊副本欺騙主節點使其認為擁有足夠的有效副本。

校驗和對讀取效能的影響很小，原因如下：

  • 由於大多數讀取跨越至少數個區塊，GFS 只需讀取並校驗相對少量的額外資料用於驗證。
  • GFS 客戶端程式碼透過嘗試對齊讀取到校驗和區塊邊界來進一步減少此開銷。
  • 區塊伺服器上的校驗和查詢與比較無需任何 I/O。
  • 校驗和計算通常可與 I/O 操作重疊進行。

垃圾回收#

透過延遲刪除實現垃圾回收#

當檔案被刪除時，GFS 不會立即回收該檔案所使用的實體空間，而是採用延遲垃圾回收策略（Lazy Garbage Collection）。當客戶端發出刪除檔案操作時，GFS 執行兩件事：

  1. 主節點像其他變更一樣記錄刪除操作。
  2. 已刪除的檔案被重新命名為一個隱藏名稱，其中也包含刪除時間戳記。

該檔案仍可以在新的特殊名稱下讀取，也可以透過重新命名回正常名稱來取消刪除。為回收實體儲存空間，主節點在定期掃描檔案系統時，移除已存在超過三天（此間隔可設定）的此類隱藏檔案，並刪除其記憶體中的中繼資料。這種延遲刪除策略為誤刪檔案的使用者提供了恢復的時間窗口。

主節點在定期掃描區塊命名空間時，會刪除不屬於任何檔案的區塊的中繼資料。此外，在與主節點的定期心跳訊息交換中，每個區塊伺服器回報其持有的區塊子集，主節點回覆該子集中不再存在於主節點資料庫中的區塊清單；這些區塊隨後從區塊伺服器上刪除。

延遲刪除的優點#

  • 簡單且可靠：若區塊刪除訊息遺失，主節點不需要重試。區塊伺服器可透過後續的心跳訊息執行垃圾回收。
  • GFS 將儲存空間回收合併到主節點的常規背景活動中，如定期的檔案系統掃描或心跳訊息交換。因此批次處理，成本被攤銷。
  • 垃圾回收在主節點相對空閒時進行。
  • 延遲刪除提供了防止意外不可逆刪除的安全保障。

延遲刪除的缺點#

刪除後儲存空間不會立即可用。頻繁建立與刪除檔案的應用程式可能無法立即重複使用儲存空間。為克服此問題，GFS 提供以下選項：

  • 若客戶端再次刪除已刪除的檔案，GFS 會加速儲存空間回收。
  • 使用者可指定不進行複製的目錄。
  • 使用者也可指定立即執行刪除的目錄。

對 GFS 的批評#

單一主節點的相關問題#

隨著 GFS 使用量的增長，Google 開始發現集中式主節點方案的以下問題：

  • 儘管控制流（中繼資料操作）與資料流已分離，主節點仍逐漸成為設計中的瓶頸。隨著客戶端數量增長，單一主節點因 CPU 能力不足而無法服務所有客戶端。
  • 儘管大區塊大小減少了中繼資料量，主節點儲存的中繼資料量仍增加到難以全部保存在主記憶體中的程度。

大區塊大小的相關問題#

GFS 中 64 MB 的大區塊大小在讀取時有其缺點。由於小型檔案只有一個或少數幾個區塊，當大量客戶端存取同一檔案時，儲存這些區塊的區塊伺服器可能成為熱點。作為變通方案，GFS 為小型檔案儲存額外的副本以將負載分散到多個區塊伺服器，並在存取此類檔案的應用程式啟動時加入隨機延遲。

總結#

  • GFS 是為大型資料密集型應用設計的可擴展分散式檔案儲存系統。
  • GFS 使用普通硬體以降低基礎設施成本。
  • GFS 的設計基於系統硬體故障隨時可能發生的理解。
  • 讀取工作負載由大量串流讀取與少量隨機讀取組成；寫入工作負載由大量循序寫入組成，將資料附加到檔案。
  • GFS 提供常見檔案操作的 API（如 create、delete、open、close、read 和 write），另外支援快照（Snapshot）與 Record Append 操作。快照建立檔案或目錄樹的副本。Record Append 允許多個客戶端同時對同一檔案附加資料，同時保證原子性。
  • GFS 叢集由一個主節點、多個區塊伺服器組成，並由多個客戶端存取。
  • 檔案被切分為固定大小的區塊，每個區塊為 64 MB。每個區塊由不可變且全域唯一的 64 位元區塊控制代碼識別，由主節點在區塊建立時分配。
  • 區塊伺服器將區塊作為 Linux 檔案儲存在本機磁碟上。
  • 為了可靠性，每個區塊被複製到多個區塊伺服器。
  • 主節點是 GFS 叢集的協調者，負責追蹤所有檔案系統中繼資料，包括命名空間、檔案到區塊的對應，以及區塊的當前位置。
  • 主節點將所有中繼資料保存在記憶體中以加速操作。為了容錯與處理主節點當機，所有中繼資料變更都寫入磁碟上的操作日誌，此日誌也複製到遠端機器。
  • 主節點不保留哪些區塊伺服器持有特定區塊副本的持久化記錄，而是在啟動時或區塊伺服器加入叢集時詢問各區塊伺服器。
  • 檢查點機制使主節點的狀態定期序列化到磁碟並複製，以便在恢復時快速載入並恢復可用。
  • 心跳機制使主節點透過心跳訊息與每個區塊伺服器通訊，傳送指令並收集狀態。
  • 客戶端（GFS Client Code）連結到每個應用程式，實作檔案系統 API，並與叢集通訊。客戶端與主節點互動取得中繼資料，但所有資料傳輸直接在客戶端與區塊伺服器之間進行。
  • 資料完整性方面，每個區塊伺服器使用校驗和偵測儲存資料的損壞。
  • 垃圾回收方面，檔案刪除後 GFS 不會立即回收可用的實體儲存空間，而是在定期垃圾回收時延遲處理。
  • 一致性方面，主節點透過確保所有副本上變更的順序以及使用區塊版本號來保證資料一致性。若副本的版本號不正確，則被垃圾回收。
  • GFS 對寫入保證至少一次寫入。這意味著記錄可能被寫入多次（雖然很少），讀取端有責任利用區塊中的校驗和與序列號來過濾和丟棄重複資料。
  • 客戶端與區塊伺服器均不快取檔案資料。客戶端快取幾乎沒有好處，但客戶端會快取中繼資料。

系統設計模式#

以下是 GFS 中使用的系統設計模式總結：

  • 預寫日誌（Write-Ahead Log）：為了容錯與處理主節點當機，所有中繼資料變更都寫入磁碟上的操作日誌，這是一種預寫日誌。
  • 心跳（HeartBeat）：GFS 主節點透過心跳訊息定期與每個區塊伺服器通訊，傳送指令並收集其狀態。
  • 校驗和（Checksum）：每個區塊伺服器使用校驗和偵測儲存資料的損壞。