【論文閱讀筆記】The Google File System

1 簡介

Google File System (GFS) 是一個可擴展的分布式文件系統，專為快速增長的Google數據處理需求而設計。這篇論文發表于2003年，此前已在Google內部大規模應用。

GFS不僅追求性能、可伸縮性、可靠性和可用性等傳統分布式文件系統的設計目標，還基于對自身應用負載情況和技術環境的深入觀察，提出了獨特的設計思路，與早期文件系統的假設明顯不同。

2 設計概述

2.1 設計目標

GFS 在設計的時候有一些假想，即預期要實現的目標。

系統由許多廉價的普通組件組成，因此組件失效是一種常態。GFS必須能夠持續監控自身的狀態，將組件失效作為一種常態事件，并能夠迅速偵測、冗余和恢復失效的組件。
系統能存儲一定數量的大文件。Google預期會存儲幾百萬個文件，這些文件通常大小在100MB以上，數GB大小的文件也是普遍存在的。系統必須能夠高效管理這些大文件，同時，系統也必須支持小文件，但不需要針對小文件進行專門優化。
工作負載主要包括兩類讀操作：
- 大規模流式讀取：單個讀操作一般讀幾百 KB，更常見的是讀 1MB 甚至更多。來自同一個客戶端的連續操作通常是讀取同一個文件中連續的一個區域。
- 小規模隨機讀取：一般是在文件的某個隨機位置讀幾個 KB 數據。注重性能的應用程序通常會將小規模隨機讀取操作合并并排序，之后按順序批量讀取，避免在文件中前后移動讀取位置。
系統的工作負載也會有很多大規模的、順序的、數據追加方式的寫操作。一般這種操作的大小和大規模讀類似。一旦寫入操作完成，這個文件很少會被修改。小規模的隨機寫也支持，但是不太高效。
系統必須高效的、行為定義明確的實現多客戶端并行追加數據到同一個文件里的語意。GFS 中的文件通常用作“生產者—消費者”隊列或其他多路文件合并操作。系統中通常有數百個生產者，每個機器上運行一個，這些生產者并發地追加修改一個文件，因此以最小的同步開銷來實現原子性是必不可少的。這些文件可能隨后被讀取，也可能是消費者在追加的操作的同時讀取文件。
高性能的穩定網絡帶寬遠比低延遲重要。GFS 的大多數目標應用程序都重視以高速率的、大批量的處理數據，而很少有應用程序對單個讀或寫有嚴格的響應時間要求。

2.2 接口

GFS 提供了一套類似傳統文件系統的 API 接口函數，雖然并不是嚴格按照 POSIX 等標準 API 的形式實現的。文件以分層目錄的形式組織，用路徑名來標識。GFS 支持常用操作以創建(create)、刪除(delete)、打開(open)、關閉(close)、讀(read)和寫(write)文件。

另外，GFS 提供了快照和記錄追加操作。

快照以很低的成本創建一個文件或者目錄樹的拷貝。
記錄追加操作允許多個客戶端同時對一個文件進行數據追加操作，同時保證每個客戶端的追加操作都是原子性的。這對于實現多路結果合并、“生產者-消費者”隊列非常有用，多個客戶端可以同時追加寫入，而不需要額外的同步鎖。Google 發現在構建大型分布式應用時，這些類型的文件是非常有用的。

2.3 架構

一個 GFS 集群包含一個單獨的master節點和多個chunk服務器，允許多個客戶端訪問，如下圖所示。

所有這些機器通常是普通的 Linux 機器，運行用戶級別的服務進程。可以將 chunkserver和客戶端部署在同一臺機器上，前提是機器資源允許，并能接受穩定性降低的風險。

其中GFS存儲的文件都被分割成固定大小的chunk。在chunk 創建的時候，master會給每個 chunk 分配一個不變的、全局唯一的 64 位的 chunk 句柄來標識。chunkserver把 chunk 以 Linux 文件的形式保存在本地硬盤上，并且根據指定的 chunk 句柄和字節范圍來讀寫塊數據。出于可靠性的考慮，每個chunk都會復制到多個chunk服務器上。默認使用3 個存儲復制節點，不過用戶可以為不同的文件命名空間設定不同的復制級別。

master節點管理所有的文件系統元數據。這些元數據包括命名空間、訪問控制信息、文件和chunk 的映射信息、以及chunk當前的位置信息。Master 節點還管理著系統范圍內的活動，比如，chunk 租用管理、孤兒 chunk的回收、以及 chunk 在 chunkserver之間的遷移。master 節點使用心跳信息周期地和每個 chunkserver通訊，發送指令到各個 chunkserver并接收 chunkserver的狀態信息。

鏈接到每個應用程序的 GFS 客戶端代碼中實現了文件系統 API，這個 GFS 客戶端代表應用程序與 master 和 chunk服務器通信以讀寫數據。客戶端與 master 交互只進行元數據操作，所有的數據操作都是由客戶端直接和 chunkserver進行交互的。GFS 沒有提供 POSIX標準的API，因此不需要深入到 Linux 的 vnode 層。

客戶端和 chunk服務器都不緩存文件數據。

客戶端緩存文件數據幾乎沒什么好處，因為大多數應用程序通過巨大的文件進行流式傳輸，或者工作集太大而無法緩存。不緩存文件數據使得客戶端代碼和總體系統的代碼得以簡化，因為無需編寫代碼解決緩存一致性的問題（不過客戶端是緩存元數據的）。
chunk服務器不需要緩存文件數據是因為 chunk 以本地文件的方式保存，Linux 操作系統的文件系統緩存會把經常訪問的數據緩存在內存中。

2.4 單個Master

單一的 Master 節點策略大大簡化了系統設計。單一的 Master 節點能夠通過全局信息精確定位 chunk 的位置，并做出復制決策。不過必須最小化在讀寫中 master 的調用次數，防止 master 成為 GFS 系統的性能瓶頸。客戶端永遠不通過 Master 節點直接讀寫文件數據，而是向 master 節點請求應聯系的 chunkserver，并將這些元數據緩存一段時間，后續操作直接與 chunkserver進行。

以上圖GFS架構為例，在一次簡單讀取操作中：

客戶端將文件名和字節偏移量轉換成文件的 chunk索引（chunk_index = offset / chunk_size），并將文件名和 chunk 索引發送給 master 節點。
master 節點返回相應的 chunk 句柄和副本的位置信息，客戶端將這些信息緩存。
客戶端將請求發送給一個副本，通常選擇最近的副本，請求包含 chunk 句柄和字節范圍。在后續對該 chunk 的讀取操作中，客戶端無需再次與 master 節點通訊，除非緩存的元數據信息過期或文件被重新打開。

客戶端通常會在一次請求中查詢多個 chunk 信息，master 節點的回復可能包含后續 chunk 的信息，這些額外信息在避免未來多次通訊的同時，不增加額外代價。這種設計保證了系統的高效性，減少了 master 節點的負擔，提高了整體性能。

2.5 chunk大小

chunk 的大小是 GFS 的關鍵設計參數之一，GFS 選擇了 64MB 的 chunk 大小，這遠大于一般文件系統的 block 大小。每個 chunk 的副本都以普通 Linux 文件的形式保存在 chunkserver上，并且只有在需要時才擴大，采用惰性空間分配策略避免了內部碎片造成的空間浪費。

將 chunk 設置為 64MB 這么大，有以下幾個有點：

它減少了客戶端和 master 節點之間的通信需求。因為一次與 master 節點通信即可獲取 chunk 的位置信息，之后可以對同一個 chunk 進行多次讀寫操作。
較大的 chunk大小使客戶端能夠對同一個 chunk 進行多次操作，通過與 chunkserver保持較長時間的 TCP 連接來減少網絡負載。
較大的 chunk大小減少了 master 節點需要保存的元數據數量，允許將所有元數據放在內存中，從而提高訪問速度。

然而，較大的 chunk 大小也有缺點。小文件包含的 chunk 較少，甚至只有一個 chunk。當多個客戶端頻繁訪問同一個小文件時，存儲這些 chunk 的服務器容易成為熱點。在實際應用中，這種情況較少發生，因為程序通常是連續讀取包含多個 chunk 的大文件。

但將GFS應用于批處理隊列系統中，熱點問題曾經出現過：一個可執行文件保存在一個單一 chunk 中，當數百臺機器同時啟動這個文件時，存儲這個 chunk 的服務器因并發請求導致系統局部過載。為解決這個問題，GFS通過增加可執行文件的復制參數和錯開程序啟動時間來緩解。此外，一個長效解決方案是允許客戶端在這種情況下從其他客戶端讀取數據。

2.6 元數據

master 中主要存儲三種類型的元數據：

文件和 chunk 的命名空間；
文件和 chunk 的映射；
每個 chunk 的副本的位置。

所有的元數據都存儲在 master 的內存里。前兩種類型也會通過在操作日志(operation log)上記錄修改來持久化，操作日志文件存儲在 master 的本地磁盤上，同時日志會被復制到其它的遠程master服務器上。使用日志使得我們能夠簡單可靠的更新 master 的狀態，，而不用擔心 master 崩潰導致的不一致性的風險。master 不會持久的存儲 chunk 位置信息，而是會在 master 啟動時或一個 chunkserver加入集群時向 chunkserver輪詢其 chunk 信息。

2.6.1 內存中的數據結構

GFS 的設計將所有元數據保存在內存中，使 master 的操作速度非常快。這種設計允許 master 在后臺簡單而高效地周期性掃描所有狀態信息，實現如 chunk 垃圾收集、在 chunkserver失效的時重新復制數據、通過 chunk 的遷移實現跨 chunkserver的負載均衡以及磁盤使用狀況統計等功能。

雖然將元數據保存在內存中會使 chunk 的數量和系統的承載能力受限于 master 的內存大小，但在實際應用中，這并不是嚴重問題。具體而言，master 管理每個 64MB 的 chunk 只需不到 64字節的元數據。由于大多數文件包含多個 chunk，絕大多數chunk 都是滿的，只有最后一個 chunk 可能部分填充。同樣，每個文件在命名空間中的數據大小通常在 64 字節以下，因為文件名經過前綴壓縮。

即便需要支持更大的文件系統，增加 master 的內存成本也相對較低。通過增加少量內存，可以使元數據全部保存在內存中，從而增強系統的簡潔性、可靠性、高性能和靈活性。

2.6.2 chunk位置信息

master 不持久化存儲哪個 chunkserver包含指定 chunk 副本的信息，master 只是在啟動時會輪詢 chunkserver以獲取這些信息，并通過控制 chunk 位置分配和定期的心跳信息監控chunk服務器狀態保持最新。

Google起初嘗試將 chunk 位置信息持久化保存在 master 上，但發現啟動時輪詢 chunkserver并定期更新更為簡便。這種設計簡化了在 chunkserver加入、離開、更名、故障和重啟時的數據同步問題，適應了大規模集群中頻繁發生的事件。

這個設計的另一個理解思路：只有 chunkserver才能最終確定一個 chunk 是否在其硬盤上。在 master 上維護全局視圖是不現實的，因為 chunkserver的錯誤可能導致 chunk 自動消失，或者操作人員可能重命名 chunkserver。這種方法確保了系統的簡潔性和可靠性。

2.6.3 操作日志

操作日志包含關鍵的元數據變更歷史記錄，是元數據唯一的持久化存儲和判斷同步操作順序的邏輯時間基線。每個文件和 chunk，還有它們的版本，都由它們創建的邏輯時間唯一的、永久的標識。

日志文件必須確保完整性。只有在元數據變更被持久化后，日志才對客戶端可見，以防止丟失文件系統或最近的客戶端操作。為此，日志會被復制到多臺遠程機器，只有在本地和遠程機器都寫入日志后，master 才響應客戶端請求。master 會收集多個日志記錄后批量處理，以減少寫入和復制對系統性能的影響。

在災難恢復時，master 通過重演操作日志恢復文件系統。為了縮短啟動時間，日志必須足夠小。當日志增長到一定量時，master 會進行 checkpoint，將所有狀態數據寫入 checkpoint 文件。恢復時，master讀取 Checkpoint 文件并重演之后的日志文件即可。Checkpoint 文件以壓縮 B-樹形式存儲，可以直接映射到內存，在用于命名空間查詢時無需額外的解析，提高了恢復速度和系統可用性。

創建 Checkpoint 文件時，master 確保不會阻塞正在進行的操作，通過獨立線程切換到新的日志文件和創建新的 Checkpoint 文件。生成一個 Checkpoint 文件大約需要一分鐘，完成后Checkpoint會被寫入本地和遠程硬盤。

master 恢復僅需最新的 Checkpoint 文件和后續日志文件。雖然舊的 Checkpoint 文件和日志文件可以刪除，但通常會保留一些歷史文件以應對災難性故障。Checkpoint 失敗不會對正確性產生任何影響，因為恢復功能的代碼可以檢測并跳過沒有完成的 Checkpoint 文件（使用前一個完整的 Checkpoint 文件和之后的操作日志來恢復系統）。

2.7 一致性模型

GFS 有一個寬松的一致性模型，很好地支持我們的高度分布式應用程序，但是實現起來依然簡單且高效。

我們現在討論 GFS 如何保證一致性，以及這對應用程序來說有何意義。我們也會強調 GFS 如何維護這些保證，但是更詳細的內容將在本文的其他部分來說。

2.7.1 GFS一致性保障機制

文件命名空間的修改（例如，文件創建）是原子性的，且僅由 master 控制。命名空間鎖保證了操作的原子性和正確性（詳見4.1），而操作日志定義了這些操作的全局順序（詳見2.6.3）。

數據修改后的文件區域狀態取決于操作類型、成功與否以及是否同步修改。下表總結了各種操作的結果。

如果所有客戶端，無論從哪個副本讀取，讀到的數據都一樣，那么我們認為文件區域是consistent；
如果對文件的數據修改之后，文件區域是一致的，并且客戶端能夠看到寫入操作全部的內容，那么這個 region 是defined。

其中，對于一個文件區域，只要所有客戶端看到的數據都是一樣的，那這個區域就是 consistent 的。在 consistent 的前提下，如果所有修改都已經被寫入，就是 defined 的。consistent 是 defined 的子集。即 defined 的一定是 consistent 的，但 consistent 的不一定是 defined 的。

當一個數據修改操作成功執行，并且沒有受到同時執行的其它寫入操作的干擾（即串行修改），那么受影響的區域就是 defined（隱含了 consistent ）：所有的客戶端都可以看到寫入的內容。

當多個并行修改操作成功完成后，文件區域處于consistent但undefined的狀態：即所有的客戶端看到的數據是一樣的，但這并不意味著每個修改都已經被寫入。一般來說，寫入的內容由多個修改的混合片段組成。

失敗的修改操作導致文件區域inconsistent (因此也是 undefined )：不同客戶端在不同時間看到的數據不同。后面我們將描述應用如何區分 defined 和 undefined 的區域。應用程序沒有必要再去細分 undefined 區域的不同類型。

數據修改操作分為寫入或者記錄追加兩種：

寫入操作：數據寫在應用程序指定的文件偏移位置上。
記錄追加操作：數據（記錄）原子性追加到文件中至少一次（即使是并發修改），但偏移位置由 GFS 選擇（3.3）。

作為對比，一個普通的追加操作僅僅是一個在客戶端認為是當前文件末尾的偏移處的寫入操作。GFS 返回給客戶端一個偏移量，表示包含寫入記錄的 defined 區域的起點。另外，GFS 可能會在文件中間插入填充數據或者重復記錄。這些數據占據的文件區域被認定是 inconsistent（即上表中的 defined interspersed with inconsistent，即 defined 區域中穿插了 inconsistent 區域，但這些區域不會影響讀取數據的結果，因為會被過濾掉），這些數據通常比用戶數據小的多。

經過一系列成功的修改操作后，GFS 確保被修改的文件區域是defined的，并包含最后一次修改操作寫入的數據。GFS 通過以下措施確保這一點：

對chunk的所有副本的修改操作順序一致。
使用 chunk 版本號檢測副本是否因其所在的 chunkserver宕機而錯過了修改操作導致失效。失效的副本不再進行修改操作，master 也不會返回該副本的位置信息給客戶端，失效副本會被垃圾收集系統盡快回收。

由于 chunk 位置信息會被客戶端緩存，在信息刷新前，客戶端可能從失效的副本讀取數據。只有當緩存條目超時，或文件被重新打開時，這個問題才能解決，因為條目超時或重新打開文件會清除客戶端緩存中的所有跟這個文件有關的 chunk 信息。此外，大多數文件只進行追加操作，因此失效副本通常返回一個提前結束的 chunk 而不是過期的數據（也就是說，數據還是有效的數據，只是返回的偏移位置不對）。當 Reader 程序重新嘗試聯絡 master 時，會立刻得到最新的 chunk 位置信息。

即使修改操作成功執行后很長時間，組件故障仍可能損壞或刪除數據。GFS 通過 master 和所有 chunkserver的定期“握手”找到失效的 chunkserver，并使用校驗和檢測數據是否損壞。一旦發現問題，數據將盡快利用有效副本進行恢復。只有當一個 chunk 的所有副本在 GFS 檢測到錯誤并采取應對措施之前全部丟失，chunk 才會不可逆轉地丟失。通常，GFS 的反應時間（master 節點檢測到錯誤并采取應對措施）為幾分鐘。即便如此，chunk 也只是不可用而非損壞，應用程序會收到明確的錯誤信息而非損壞的數據。

2.7.2 對應用程序的影響

使用 GFS 的應用程序可以利用一些簡單的技術來實現寬松的一致性模型，也可以實現其他目標功能，包括盡量采用追加寫入而不是覆蓋、Checkpoint、寫入自驗證和自識別的記錄。

在實際應用中，我們所有的應用程序對文件的寫入操作都盡量采用追加方式而不是覆蓋方式。例如，應用程序從頭到尾寫入數據生成一個文件，寫入完成后自動將文件改名為一個永久文件名，或者定期進行 Checkpoint，記錄成功寫入的數據量。Checkpoint 文件可以包含程序級別的校驗和。Readers 僅校驗并處理上個 Checkpoint 之后的文件區域，這些區域的狀態是defined的。這種方法滿足了我們的一致性和并發處理需求。追加寫入比隨機寫入更加高效，對應用程序的失敗處理更具彈性。Checkpoint 允許 Writer 以漸進方式重新開始，并防止 Reader 處理已成功寫入但從應用程序的角度來看未完成的數據。

另一個典型的應用場景是，許多應用程序并行追加數據到同一個文件，例如進行結果合并或者是一個生產者-消費者隊列。記錄追加方式的“至少一次追加”特性保證了 Writer 的輸出。Readers 可以通過以下方法處理偶然性的填充數據和重復內容：Writers 在每條寫入記錄中包含額外信息，例如 Checksum，用來驗證有效性。Reader 可以利用 Checksum 識別并丟棄額外的填充數據和記錄片段。如果應用不能容忍偶爾的重復內容，可以使用記錄的唯一標識符來過濾重復數據，這些唯一標識符通常用于命名程序中處理的實體對象，如 web 文檔。這些記錄 I/O 功能都包含在我們共享的程序庫中，并適用于 Google 內部的其他文件接口實現。這樣，相同序列的記錄，加上偶爾出現的重復數據，都能正確分發給 Reader。

3 系統交互

Google 設計 GFS 系統一個重要的原則是最小化所有操作和 master 的交互（因為 master 只有一個，必須減輕 master 的壓力）。在這個背景下，我們現在來說客戶端、master 和 chunk服務器如何互動以實現數據修改、原子記錄追加(append)，以及快照(snapshot)。

3.1 租約（lease）和變更順序

變更是一個會改變 chunk 內容或者元數據的操作（如寫入或記錄追加），會在 chunk 的所有副本上執行。為了保持多個副本間變更順序的一致性，GFS 采用了租約（lease）機制。master 節點為 chunk 的一個副本（主 chunk）建立租約，初始租期為 60 秒。主 chunk 對所有更改操作進行序列化，所有副本遵從這個序列進行修改。因此，修改操作全局的順序首先由 master 選擇的租約的順序決定，然后由租約中主 chunk 分配的序列號決定。

只要 chunk 被修改了，主 chunk 就可以申請更長的租期，通常會得到 master 的確認并收到租約延長的時間。這些租約延長請求和批準的信息通常都是附加在 master 和 chunkserver之間的心跳消息中來傳遞。有時 master 會試圖提前取消租約（例如，master 想取消在一個已經被改名的文件上的修改操作）。即使 master 和主chunk失去聯系，它仍然可以安全地在舊的租約到期后和另外一個chunk副本簽訂新的租約。

在下圖中，我們通過列出寫入操作的控制流描述了這個過程，并且用數字標記了步驟順序。

客戶端向master詢問哪個chunk服務器持有當前的租約，以及其他副本的位置。如果沒有一個chunk服務器持有租約，master則會選擇其中一個副本建立一個租約（圖中沒有顯示此步驟）；
master將主chunk的標識符以及其他副本（又稱二級副本）的位置返回給客戶端。客戶端緩存這些數據以便后續的操作。只有在主 chunk 不可用，或者主 chunk 回復信息表明它已不再持有租約的時候，客戶端才需要重新跟 master 聯系。
客戶端把數據 push 給所有的副本，客戶端可以以任意的順序 push。chunkserver接收到數據并保存在它的內部 LRU 緩存中，一直到數據被使用或者過期交換出去。通過將數據流與控制流解耦，我們可以基于網絡拓撲情況調度昂貴的數據流來提高性能，而不管哪個 chunk服務器是主 chunk。
當所有的副本都確認接收到了數據，客戶端發送寫請求到主chunk服務器。這個請求標識了之前推送到所有副本的數據。主 chunk 為接收到的所有操作分配連續的序列號，這些操作可能來自不同的客戶端，序列號保證了操作順序執行。它以序列號的順序把操作應用到它自己的本地狀態中。
主chunk把寫請求傳遞到所有的二級副本。每個二級副本依照主chunk分配的序列號以相同的順序執行這些操作。
所有完成了操作的二級副本向主chunk 回復，表明它們已經完成了操作。
主 chunk 回復客戶端。任何副本產生的任何錯誤都會返回給客戶端。在出現錯誤的情況下，寫入操作可能在主chunk和一些二級副本執行成功（因為是主chunk 先成功完成修改后，才會讓二級副本開始應用修改，如果主 chunk 失敗了，二級副本就不會收到序列號以及應用更改的命令）。客戶端的請求被確認為失敗，被修改的區域處于inconsistent的狀態。我們的客戶端代碼通過重復執行失敗的操作來處理這樣的錯誤。在從頭開始重復執行之前，客戶端會先從步驟（3）到步驟（7）做幾次嘗試。（Q：已經完成操作或部分完成操作的副本，接收到重試的數據后，如何處理？A：直接在文件末尾（最后一個 chunk 末尾）繼續寫入，之前成功的二級副本會重復寫入，去重任務由讀取數據的客戶端來完成。）

如果應用程序一次寫入的數據量很大，或者數據跨越了多個 chunk，GFS 客戶端代碼會把它們分成多個寫操作。這些操作都遵循前面描述的控制流程，但是可能會被其它客戶端上同時進行的操作打斷或者覆蓋。因此，共享的文件區域的尾部可能包含來自不同客戶端的數據片段，盡管如此，由于這些分解后的寫入操作在所有的副本上都以相同的順序執行完成，chunk 的所有副本都是一致的。這使文件 region 處于 2.7 節描述的consistent但是undefined的狀態。

3.2 數據流

為了提高網絡效率，GFS采取了將數據流和控制流分開的措施。在控制流從客戶端到主 chunk再到所有二級副本的同時，數據以管道方式順序沿著精心選擇的 chunkserver鏈推送，充分利用每臺機器的帶寬，避免網絡瓶頸和高延時連接，最小化數據推送延時。

數據順序沿著一個 chunkserver鏈推送，而不是分散推送（如樹型拓撲結構），以充分利用每臺機器的出口帶寬，實現最快速度的傳輸，而不分散帶寬。為避免網絡瓶頸和高延遲連接，每臺機器盡量選擇網絡拓撲中離自己最近且尚未接收到數據的機器作為目標推送數據。例如，客戶端將數據推送到最近的 chunkserver S1，S1 推送到 S2，以此類推，基于 IP 地址計算節點距離。

利用基于 TCP 連接的管道式數據推送方式最小化延遲。chunkserver接收到數據后立即向前推送，利用全雙工交換網絡的優勢，傳輸不會減慢接收速度。在無網絡擁塞情況下，傳送 $B$ 字節的數據到 $R$ 個副本的理想時間為 $\frac{B}{T} + RL$ （ $T$ 是網絡吞吐量， $L$ 是傳輸延遲）。通常，我們的網絡連接速度是 100Mbps，傳輸 1MB 數據的理想時間約為 80ms。

3.3 原子的記錄追加

GFS 提供了一種原子的記錄追加操作，客戶端只需指定要寫入的數據，GFS 保證至少一次原子寫入成功執行（即寫入一個順序的byte流），寫入數據追加到 GFS 指定的偏移位置，并返回該偏移量給客戶端。類似于 Unix 的 O_APPEND 模式，多個并發寫操作無競態條件。

記錄追加在分布式應用中頻繁使用，特別是在多個客戶端并行追加數據的情況下。傳統寫入需要復雜的同步機制，如分布式鎖管理器，而記錄追加簡化了這種需求，常用于生產者/消費者隊列系統或數據合并文件。

記錄追加遵循 3.1 節描述的控制流程，主 chunk 有額外控制邏輯。客戶端將數據推送到最后一個 chunk 的所有副本，然后發送請求給主 chunk。主 chunk 檢查是否超出最大大小（64MB），如果超出，則填充到最大大小并通知二級副本做同樣的操作，然后回復客戶端要求其對下一個chunk重新進行記錄追加。通常情況下，主 chunk 追加數據并通知二級副本寫入相同位置，最后回復客戶端操作成功。

如果記錄追加在任何副本上失敗，客戶端需要重新操作，可能導致同一個chunk的不同副本包含不同數據。GFS 只保證數據整體原子性寫入至少一次，而不保證字節級別一致。成功執行操作的數據區域是defined的（且consistent的），否則是inconsistent的（且undefined義的）。程序可以處理這些inconsistent區域。

3.4 快照

快照操作在 GFS 中幾乎瞬間完成，且不干擾其他操作。用戶可以用快照快速創建數據集的分支拷貝或在實驗前備份當前狀態，方便之后提交或回滾。

就像AFS（Andrew File System，一種分布式文件系統），GFS 使用標準的“寫時復制”（copy-on-write）技術實現快照。當 master 收到快照請求時，它會取消作快照的文件的所有 chunk 的租約，確保后續寫操作必須與 master 交互，使 master 有機會先創建 chunk 的新拷貝。

租約取消或過期后，master 將操作記錄到硬盤日志，并通過復制源文件或目錄的元數據將變化反映到內存中。新創建的快照文件與源文件共享相同的 chunk 地址。

快照操作后，當客戶端首次寫入 chunk C 時，會先請求 master 查詢當前租約持有者。master 發現 chunk C 的引用計數超過 1（寫時復制方法創建快照時是給這個chunk加一個引用計數，沒有立刻真的拷貝，一個 chunk 的引用計數大于 1 的話就代表這個 chunk 是某個快照的一部分，要保留原樣數據的。當這個 chunk 上有新的寫入的時候，這個 chunk 才會真的被復制，客戶端在新復制的 chunk 上寫入，而原來的舊 chunk 被快照繼續引用），不立即回復客戶端，而是選擇新的 chunk 句柄 C'，并要求所有持有 chunk C 副本的服務器創建 C'。通過在本地創建新的 chunk 避免了網絡復制，提高了效率。master 確保新 chunk C'的一個副本擁有租約后回復客戶機，客戶機即可正常寫入該 chunk。

4 Master操作

master 執行所有的命名空間操作。此外，它還管理著整個系統里所有 Chunk 的副本：

master 決定 chunk 副本的存儲位置；
創建新的 chunk 和它的副本；
協調各種各樣的系統范圍內的活動以保證 chunk 被完全拷貝；
在所有的 chunkserver上做負載均衡；
回收不再使用的存儲空間。

下面我們深入討論下上述的幾點。

4.1 命名空間管理和鎖

在 GFS 中，master 節點的操作可能耗時較長，例如快照操作需取消所有相關 chunk 的租約。為避免延緩其他操作，GFS 允許多個操作同時進行，并通過命名空間的區域鎖保證順序正確。

GFS 命名空間是一個全路徑與元數據映射的查找表，采用前綴壓縮高效存儲在內存中。不同于傳統文件系統，GFS 不支持列出目錄下所有文件的結構，也不支持文件或目錄的鏈接。每個節點（絕對路徑的文件名或目錄名）有一個關聯的讀寫鎖。

每個 master 操作開始前都要獲得相關鎖。通常，涉及路徑/d1/d2/.../dn/leaf 的操作需要獲得/d1，/d1/d2，…，/d1/d2/.../dn 的讀鎖，以及/d1/d2/.../dn/leaf 的讀寫鎖。根據操作不同，leaf 可以是文件或目錄。例如，在/home/user 快照到/save/user 時，鎖機制防止創建文件/home/user/foo。快照操作獲得/home 和/save 的讀鎖及/home/user 和/save/user 的寫鎖；文件創建操作獲得/home 和/home/user 的讀鎖及/home/user/foo 的寫鎖。由于/home/user 鎖沖突，這兩個操作順序執行。文件創建操作不需要獲取父目錄的寫入鎖，因為這里沒有“目錄”，或者類似 inode 等用來禁止修改的數據結構。文件名的讀取鎖足以防止父目錄被刪除。

這種鎖方案支持對同一目錄的并行操作。例如，可在同一目錄下同時創建多個文件：每個操作獲取目錄名的讀鎖和文件名的寫鎖。目錄名的讀鎖防止目錄被刪除、改名或快照；文件名的寫鎖序列化文件創建操作，確保不會多次創建同名文件。

由于命名空間節點眾多，讀寫鎖采用惰性分配策略，不再使用時立刻刪除。鎖的獲取依據全局一致的順序避免死鎖：首先按命名空間層次排序，在同一層次內按字典順序排序。

4.2 副本放置

GFS 集群采用高度分布的多層布局結構，典型拓撲包括數百個 chunkserver分布在多個機架上，由來自同一或不同機架的數百個客戶機訪問。通信可能跨越一個或多個網絡交換機，且機架出入帶寬可能較小。多層分布架構帶來數據靈活性、可靠性和可用性挑戰。

chunk 副本位置選擇旨在最大化數據可靠性和可用性，以及網絡帶寬利用率。僅在多臺機器上存儲副本不足以達到目標，需在多個機架間分布儲存 chunk 的副本。這保證即使整個機架故障或掉線，某些副本仍可用，且網絡流量尤其讀操作可利用多個機架的帶寬。盡管寫操作需與多個機架設備通信，但這是值得的。

4.3 創建、重新復制、重新平衡

chunk 副本在 GFS 中有三個主要用途：chunk 創建、重新復制和重新平衡。

Master 節點在創建 chunk 時選擇存放初始空副本的位置，考慮以下因素：
- 優先選擇硬盤使用率低于平均值的 chunkserver，以平衡硬盤使用率。
- 限制每個 chunkserver上最近 chunk 創建操作的次數，以減少寫入操作的集中度。
- 分布在多個機架之間，以提高可靠性。
當有效副本數量低于指定復制因數時，master 節點會重新復制 chunk，可能原因包括：
- chunkserver不可用或報告副本損壞。
- 磁盤錯誤或復制因數增加。
- 重新復制優先級基于現有副本數量與復制因數的差異、chunk 活躍狀態及其對客戶端的影響。
master 選擇優先級最高的chunk，命令 chunkserver克隆副本，選擇新副本的位置的策略類似于 chunk 創建。為防止克隆操作超載網絡，master會限制克隆操作數量及其讀請求頻率。
master 周期性檢查副本分布，移動副本以優化硬盤空間利用和平衡。在這個過程中，master 漸進式填充新 chunkserver，避免短期內填充過載。副本位置選擇策略同上，并優先移走剩余空間低于平均值的服務器上的副本，以平衡整體硬盤使用率。

4.4 垃圾回收

GFS 在文件刪除后不會立即回收物理空間，而是采用惰性垃圾回收策略，僅在文件和 chunk 級的常規垃圾收集中進行。這樣簡化了系統設計，提高了可靠性。

4.4.1 機制

當一個文件被應用程序刪除時，master立刻把刪除操作以日志的方式記錄下來。但是，master 并不馬上回收資源，而是把文件名改為一個包含刪除時間戳的、隱藏的名字。當 master 對文件系統命名空間做常規掃描的時候，它會刪除所有三天前的隱藏文件（這個時間間隔是可以設置的）。在文件被真正刪除之前，它們仍舊可以用新的特殊的名字（即被重命名后的帶有刪除時間戳的名字）讀取，也可以通過把隱藏文件改名為正常顯示的文件名的方式“取消刪除”。當隱藏文件被從命名空間中刪除，master 內存中保存的這個文件的相關元數據才會被刪除。這也有效的切斷了文件和它包含的所有 chunk 的連接。

在對 chunk 命名空間做類似的常規掃描時，master 找到孤兒 chunk（不被任何文件包含的 Chunk）并刪除它們的元數據。chunkserver在和 master 交互的心跳信息中，報告它擁有的 chunk 子集的信息， master 回復 chunkserver哪些 chunk 在 master 保存的元數據中已經不存在了。chunkserver可以任意刪除這些 chunk 的副本。

4.4.2 討論

GFS 的垃圾回收方案簡單可靠。可以輕易得到chunk 的引用：存儲在 master 的文件到chunk的映射表中；也可以輕松得到chunk所有副本：以Linux文件的形式存儲在 chunkserver指定目錄下。所有master 不能識別的副本即為“垃圾”。

垃圾回收在空間回收方面相比直接刪除有幾個優勢。

在大規模分布式系統中，組件失效是常態。chunk 可能在某些服務器上創建成功，但在其他服務器上失敗，失敗的副本處于無法被 master 識別的狀態。副本刪除消息可能丟失，master 必須重新發送失敗的刪除消息，包括自身的（元數據）和 chunkserver的。垃圾回收提供了一致的、可靠的清除無用副本的方法。
垃圾回收將存儲空間回收操作合并到 master 的規律性后臺活動中，如例行掃描和與 chunkserver的握手。因此操作被批量執行，減少開銷。回收在 master 相對空閑時進行，提高了響應速度。
延遲回收為意外、不可逆轉的刪除操作提供了安全保障，防止誤刪。

雖然延遲回收可能阻礙存儲優化，尤其在空間緊缺時。但可以通過顯式再次刪除文件可以加速回收。用戶可以為不同命名空間設置不同的復制和回收策略，以優化存儲使用。

4.5 過期副本檢測

當 chunkserver失效時，chunk 的副本可能因錯失一些修改操作而過期。master 通過保存每個 Chunk 的版本號來區分當前副本和過期副本。每次與 chunk 簽訂新租約時，master 都會增加 chunk 的版本號，并通知最新的副本，且這些副本會將新的版本號記錄在其持久化存儲中。這個過程在任何客戶端得到通知前完成，因此也是在對這個 chunk 開始寫之前完成的。如果某個副本所在的 chunkserver正好失效，那么其版本號就不會被更新。待該 chunkserver重新啟動并向 master 報告其持有的 chunk 及相應版本號時，master 會檢測出其包含過期的 chunk。若 master 發現一個比其記錄的版本號更高的版本號，會認為之前簽訂租約的操作失敗，并選擇更高的版本號作為當前版本號。

master 在例行垃圾回收過程中移除所有過期副本。在此之前，master 在回復客戶端的 chunk 信息請求時，master 實際上會認為根本不存在一個過期的副本（也就是說，給客戶端返回的 chunk 列表中可能包含過期的 chunk，客戶端有可能去讀過期的 chunk。GFS 是弱一致性的）。另外一重保障措施是，master 在通知客戶端哪個 chunkserver持有租約或指示 chunkserver從哪個 chunkserver進行克隆時，消息中都會附帶 chunk 的版本號。客戶端或 chunkserver在執行操作時會驗證版本號，以確保總是訪問當前版本的數據。

5 容錯和診斷

5.1 高可用性

在 GFS 集群中，高可用性的策略主要包括快速恢復和復制。

首先，對于快速恢復，無論是 master 還是 chunkserver，它們都能在數秒內恢復狀態并重新啟動。系統不區分正常關閉和異常關閉，通常通過直接終止進程來關閉服務器。
其次，對于 chunk 復制，每個 chunk 都被復制到不同機架上的不同 chunkserver上，并可以根據需要設定不同的復制級別。當有 chunkserver 離線或發現數據損壞時，master 通過克隆已有的副本來確保每個 chunk 都被完整復制。
最后，master 的狀態也需要復制以保證其可靠性。master 的所有操作日志和 checkpoint 文件都被復制到多臺機器上，確保操作日志寫入備用節點和本機磁盤，以支持失敗后的快速重新啟動。此外，還存在“影子”master，用于提供文件系統的只讀訪問。這些“影子”服務器能夠保持狀態最新，并通過與主 master 相同的方式處理數據結構的更改。它們定期從 chunkserver拉取數據，并與其握手以確定狀態，從而確保系統的高可用性。

5.2 數據完整性

每個 Chunkserver使用 checksum 來檢查保存的數據是否損壞。由于 GFS 集群通常包含數百臺機器和數千塊硬盤，磁盤損壞導致的數據丟失或損壞在讀寫過程中是常見的。雖然可以通過其他副本恢復數據，但跨服務器比較副本以檢查數據完整性并不實際。此外，由于 GFS 允許存在有歧義的副本，特別是在原子記錄追加操作中，副本并不總是完全一致的（副本不是 byte-wise 完全一致的）。因此，每個 chunkserver必須獨立維護 checksum 來校驗自己的副本完整性。

每個 chunk 被分為 64KB 的塊，每個塊對應一個 32 位的 checksum，存儲在內存和硬盤上，并記錄在操作日志中。在讀取數據之前，chunkserver會校驗與讀取范圍重疊的數據塊的checksum。如果 checksum 不匹配，服務器返回錯誤信息并通知 master，之后從其他副本讀取數據并進行克隆恢復。一旦新的副本就緒，master 通知 chunkserver刪除錯誤的副本。

checksum 對讀操作性能影響很小，因為大部分讀操作涉及多個塊，而只需讀取少量額外數據進行校驗。通過對齊讀操作到 checksum塊的邊界，可以進一步減少額外讀取操作的影響。此外，checksum 的查找和比較不需要額外的 I/O 操作，計算可以與 I/O 操作并行進行。

針對追加寫入操作，checksum 的計算進行了優化，因為這種操作在 GFS 工作中占很大比例。只需增量更新最后一個不完整塊的 checksum，并使用新寫入的數據計算新的 checksum。如果最后一個checksum塊損壞，問題會在下次讀取時被發現。

相比之下，覆蓋寫操作需要讀取和校驗被覆蓋范圍內的第一個和最后一個塊，操作完成后重新計算和寫入新的 checksum。如果不校驗第一個和最后一個被寫的塊，新的 checksum 可能會隱藏未覆蓋區域內的數據錯誤。

當 chunkserver空閑時，會掃描和校驗每個不活動 chunk 的內容，以發現很少被讀取的 chunk 是否完整。一旦發現數據損壞，master 可以創建新的正確副本并刪除損壞的副本，避免非活動的損壞 chunk 誤導 master，使其認為副本數量足夠。

5.3 診斷工具

詳盡的、深入細節的診斷日志在問題隔離、調試和性能分析等方面提供了極大的幫助，而所需開銷卻很小。沒有日志，我們很難理解短暫的、不重復的機器間消息交互。GFS 服務器會生成大量日志，記錄關鍵事件（如 chunkserver 的啟動和關閉）以及所有 RPC 請求和回復。這些日志可以隨時刪除，不影響系統的正確運行，但我們在存儲空間允許的情況下盡量保留這些日志。

RPC 日志詳細記錄了網絡上的所有請求和響應，但不包括讀寫的文件數據。通過匹配請求與回應，并收集不同機器上的 RPC 日志，我們可以重現所有消息交互來診斷問題。這些日志還用于跟蹤負載測試和進行性能分析。

日志對性能的影響很小，因為日志寫入是順序且異步的。最近的事件日志保存在內存中，用于持續的在線監控。

6 經驗

在構建和部署 GFS 的過程中，Google 遇到了許多問題，包括操作和技術方面的挑戰。最初，GFS 主要作為生產系統的后端文件系統，后來逐漸支持研究和開發任務，增加了權限和配額等功能。

最大的難題是磁盤和 Linux 相關問題。許多磁盤聲稱支持 Linux IDE 驅動，但實際應用中情況不一，導致協議不匹配，數據可能因內核問題而被破壞。為此，Google 使用校驗和來驗證數據，并修改內核處理這些問題。

早期使用 Linux 2.2 內核時，fsync() 效率與文件大小相關而非修改部分大小相關，導致操作日志文件過大時出現問題，尤其是在尚未實現checkpoint 的時候。Google費了很大的力氣用同步寫來解決這個問題，但是最后還是移植到了 Linux2.4 內核上。

另一個問題是單個讀寫鎖，導致系統偶爾超時。Google 通過用 pread() 替代 mmap() 并增加額外復制操作解決了這個問題。

在任意地址空間的線程在磁盤讀入（讀鎖）時或 mmap() 調用（寫鎖）時必須持有鎖。即使系統負載很輕，也會偶爾超時。Google花費大量精力查找資源瓶頸或硬件問題，最終發現磁盤線程在交換數據到磁盤時，鎖住了當前網絡線程，阻止其將新數據映射到內存。由于性能主要受限于網絡接口而非內存復制帶寬，Google用 pread() 替代 mmap()，通過額外復制操作解決了問題。