The Google File System 翻譯和理解

2022 年 11 月 7 日
筆記
分散式系統

The Google File System

摘要

GFS 是一個可擴展的分散式文件系統，用於大型分散式數據密集型應用上。它可以運行在便宜的普通硬體上，提供了高性能和一定的容錯性。

1. 分散式文件系統介紹

GFS 與過去的分散式文件系統有很多相似之處，如性能、擴展性、可靠性和高可用性。但對 GFS 的設計是由我們對應用負載和技術環節的探索所驅動的，它與之前的文件系統還是有設計上的明顯區別。

我們考慮下面一些設計分散式文件系統時的關鍵點：

首先，組件出錯是一個普遍情況，而不是異常事件。我們幾乎可以確定在一個大型文件系統中，有一部分機器不可用，一部分機器無法從錯誤中恢復。造成錯誤的原因可能有：
- 應用程式或作業系統的 bug。
- 人為錯誤。
- 磁碟、記憶體、網路等的錯誤。
- 等等。
因此，實時監控、錯誤檢測、容錯設計、錯誤恢復是這個系統不可或缺的一部分。
其次，文件是巨大的。每個文件通常包含很多對象，例如網頁文檔。當我們經常使用由數十億個對象組成的、大小達到許多個 TB 且依然在快速增長的數據集時，即使文件系統不拒絕這樣的需求，我們也必須重新審視設計的假設和參數，例如 IO 操作和存儲塊的大小。
第三，大多數文件通過追加數據而不是覆蓋數據來進行操作，文件的隨機寫事實上並不存在。這些文件寫入後只用作讀需求，且經常只是順序讀，各種數據共享這些屬性。
- 一些組成了數據倉庫，用於供數據分析程式使用；
- 一些是正在運行的程式連續產生的數據流；
- 一些是檔案資料；
- 一些是存儲在一台機器上並在另一台機器上處理的中間數據（如 MapReduce 的中間鍵值對）
對於上述這種文件的處理，在客戶端快取數據塊已經沒有意義，而追加操作成為了性能優化和原子性保證的焦點。
第四，應用程式和文件系統 API 在設計上的協作提高了整個系統的靈活性，從而優化了整個系統。例如我們放鬆了 GFS 在一致性上的要求，這大大簡化了文件系統，同時沒有為應用程式引入額外的負擔。我們還採用了原子性的追加操作，以此使多個用戶可以同時對一個文件進行追加操作，但又不用帶來額外的同步開銷。

在 Google，多個 GFS 集群以不同的目的進行部署，最大的一個集群包含了超過 1000 個存儲節點，300TB 以上的磁碟存儲，能讓數百個不同機器上的客戶端進行連續的頻繁訪問。

2. 設計概要

2.1 設想

在根據需求設計文件系統的過程中，我們也會依照一些挑戰和機會並存的假設進行設計。在第一節提到的一些事實的基礎上，我們在細節上展示我們的一些假設：

系統是由許多廉價的、普通的、易出錯的組件組成的。它必須有不間斷的自我監控、探測、容錯，以及組件錯誤狀態的快速恢復。
系統存儲了適量的大文件。我們期望有幾百萬的文件，每個文件通常是 100MB 或者更大。GB 級別的文件是很常見的，並且能夠有效的進行管理。小文件必須被支援，但是我們無需對它們進行優化。
工作負載主要由兩種讀操作組成：大規模的流讀取和小規模的隨機讀取。在大規模的流讀取中，單個的操作通常會讀幾百 KB 的數據，更常見的是 1MB 或者更多的數據。來自同一個客戶端的連續操作通常讀取一個文件的一個連續範圍。小規模的隨機讀取通常在任意的位置讀取幾 KB 的數據。追求性能的應用通過批處理和排序小規模的讀操作，用以順序的讀取文件，而不是在讀取過程中前後移動。
工作負載同樣還有很多大量的、序列寫操作，它們將數據追加到文件末尾。一般操作的大小與相應的讀操作相近。一旦寫入，文件將很少再次改變。在文件任意位置進行的小規模的寫操作雖然是支援的，但效率很低。
系統必須是高效的，這裡的高效是指有很多客戶端能夠同時對一個文件進行數據追加。我們的文件通常用於生產者-消費者隊列或者多路合併。運行在不同機器上的數百個生產者，將並發地對一個文件進行數據追加，使用最小同步開銷的原子化操作是很有必要的。這個文件可能會在以後被讀取，或者正在同時被一個消費者讀取。
持續的高頻寬比低時延更重要。大多數目標應用更看重大量地、高效地處理數據，而很少有應用對單個的讀或寫操作有嚴格的響應時間要求。

2.2 介面

GFS 提供了常見的文件系統介面，文件被存放到目錄中，並由路徑名進行標識。我們支援常見的操作如create、delete、open、close、read以及write文件。

特殊地，GFS 還有**快照 snapshot **和 記錄追加 record append 操作。

快照低開銷地創建了一個文件或目錄樹的拷貝。
記錄追加允許多個客戶端同時向一個文件追加數據，並保證每個單獨的客戶端追加操作的原子性。可以用於實現多路結果合併和生產者-消費者隊列，它們使很多客戶端在不加鎖的情況下可以同時進行追加操作。

2.3 架構

一個 GFS 集群由一個 Master 和多個塊伺服器 chunkservers 組成，可以被多個客戶端訪問。每個節點都是一個運行在 Linux 上的普通進程。

GFS 文件被劃分為固定大小的塊，每個塊由一個不變的、全局唯一的 64bit 塊句柄標識，它是由主節點在創建塊時分配的。塊伺服器存儲這些塊並對其進行讀寫操作，為了提高可靠性，每個塊都會在多個塊伺服器上進行複製。默認情況下，我們會存儲三個副本，用戶也可以對不同的命名空間設置不同的複製級別。

Master 存儲了整個文件系統的元數據，包含命名空間、訪問控制資訊、文件到塊的映射，以及塊的當前位置等等。它也控制了一些系統層的行為，如塊的租約管理，孤兒塊的垃圾回收，以及塊伺服器之間的塊遷移。Master 周期性地與每個塊節點進行通訊，通過心跳資訊發送指令並收集塊伺服器狀態。

GFS 客戶端程式碼嵌入到應用中，實現了文件系統 API，代表客戶端進行讀寫數據，與主節點和塊伺服器進行通訊。客戶端與主節點進行元數據的交互操作，而與數據相關的通訊則直接與塊伺服器進行。

2.4 單一的主節點

單一的主節點簡化了我們的設計，令主節點能夠根據整體資訊確定塊的位置，以及進行複製決策。

由於主節點是單一的，我們必須最小化對主節點的讀寫操作，以保證它不會成為系統性能的瓶頸。客戶端不會通過主節點讀寫數據，而只會向主節點詢問需要與哪些塊伺服器進行聯繫。客戶端會將主節點的答覆快取一段時間，並在後續直接和塊伺服器交互。

簡單解釋一下上圖中的一個讀操作交互。

首先，使用固定的塊大小，客戶端將文件名和應用指定的位元組便宜轉換為文件塊的索引。
然後，它向主節點發送一個包含文件名和塊索引的請求，主節點回復相應的塊句柄和副本的位置。客戶端使用文件名和塊索引作為 Key 快取這條資訊。
客戶端向其中一個副本發送請求，大多數時候選擇最近的那個。請求指定了塊句柄和那個塊的一個位元組範圍。後續客戶端無需和主節點交互，除非快取資訊過期或文件被重新打開。

事實上，客戶端通常在一個請求中詢問多個塊，主節點的回復也會包含緊跟在請求塊後面的塊的資訊，這在實際中往往可以在未來減少一些客戶端-主節點通訊。

2.5 塊大小

塊大小是設計的關鍵參數，我們選擇 64MB，這要比一般文件系統的塊要大許多。每個塊副本在塊伺服器上被存儲為一個普通的 Linux 文件，只有在需要時才擴大。

令塊的大小很大的最大隱患在於內部碎片。GFS 使用惰性空間分配避免了因內部碎片帶來的空間浪費。

採用大小比較大的塊有以下幾個重要優點：

它能減少客戶端和主節點的交互次數，因為一個塊的位置資訊代表了更多的數據的位置。
由於大的塊大小，客戶端能在一個塊上進行更多操作。這樣可以通過與塊伺服器在一段時間內保持一個 TCP 長連接賴減少網路開銷。
主節點可以存儲更少的元數據，這樣我們可以把元數據存儲在記憶體中。所帶來的好處在 2.6.1 節中討論。

採用大小大的塊也有下面這個缺點：

當大量客戶端訪問相同的文件時，存儲這個塊的塊伺服器會成為熱點。顯然當塊的大小比較大，出現熱點塊伺服器的概率也就更大。

在實際中，熱點不是一個主要問題，因為我們的應用大多會順序讀取大量的包含多個塊的文件。

但是當 GFS 第一次用於一個批處理序列系統時，還是發生了熱點問題：一個可執行文件以單個塊的形式寫入 GFS，然後在數百台機器上同時啟動。少量的存儲這個文件的塊伺服器會由於數百台機器的同時訪問而過載。我們通過以下兩個手段解決這個問題：

提高可執行文件的複製因子 replication factor。讓更多的塊伺服器存儲這些熱點數據。
令批處理序列系統和應用程式不同時，而是交替啟動。

一個可能的長期的解決方案是讓客戶端能從其他客戶端讀取數據。

2.6 元數據

主節點存儲了三種主要類型的元數據：文件和塊的命名空間，文件到塊的映射，以及每個塊副本的位置，所有元數據都保留在主節點的記憶體中。

命名空間，以及文件到塊的映射，通過將操作記錄存儲在本地磁碟上的日誌文件中得以永久保存，並在遠程的機器上進行日誌備份。使用日誌使我們能夠簡單可靠地更新主節點狀態，並且不用擔心主節點崩潰造成的不一致。主節點不會永久保存塊位置資訊，而會在啟動時，以及有新的塊伺服器加入集群時，詢問每個塊伺服器的塊資訊。

2.6.1 記憶體中的數據結構

得益於元數據存放在記憶體中，主節點的操作非常快。它也能使主節點能夠周期性地在後台簡單有效的地瀏覽整個系統的狀態。這個周期性的瀏覽操作用於實現塊的垃圾回收、塊伺服器出錯後的重複制，負載均衡和磁碟空間使用的塊遷移，4.3 和 4.4 節會深入的討論這些行為。

但將元數據放在記憶體中有一個潛在問題，即塊的數量和將來整個系統的容量受到主節點的記憶體大小限制。但由於塊的元數據大小實際很小，所以在實際中這不是一個嚴重的問題。更何況，即使需要為主伺服器增加額外的記憶體，這個花費相比將元數據存放在記憶體中帶來的簡單性、可靠性、有效性和擴展性來說，也是很值得的。

2.6.2 塊位置

主節點不會永久保留類似哪些塊伺服器含有一個給定的塊的記錄這樣的資訊。而是在啟動時輪詢塊伺服器獲取這些資訊。主節點可以將自己保持在最新狀態，因為它控制所有塊的放置，並且通過常規的心跳消息來監控塊伺服器的狀態。

起初我們考慮在主節點永久地保存塊位置資訊，但後來發現在啟動時向塊伺服器請求數據並在此後進行周期性更新要簡單許多。這消除了當塊伺服器加入或離開集群、更改名字、出錯、重啟等異常發生時，保持主節點和塊伺服器同步的問題。在大型集群中這些問題發生得很頻繁。

理解這種設計的另一個角度是：認識到塊伺服器對他的磁碟上最終存儲或不存儲某個塊有最終的決定權。在主節點上維護這些資訊的一致性視圖是沒有意義的，因為塊伺服器上的錯誤可能會導致塊發生主伺服器不能及時知悉的變動，例如塊被刪除或重命名等。

2.6.3 操作日誌

操作日誌包含了關鍵的元數據變化的歷史記錄，是 GFS 的核心。它不僅永久的記錄了元數據，還能提供確定並發操作順序的邏輯時間線服務。文件和塊，連同它們的版本，都是由它們創建的邏輯時間唯一的、永久的進行標識的。

因為操作日誌是臨界資源，我們必須可靠的存儲它，在元數據的變化持久化之前，客戶端是無法看到這些操作日誌的。否則，即使塊本身保存下來，仍然有可能丟失整個文件系統或者客戶端最近的操作。因此，我們將它複製到幾個遠程的機器上，並在將相應的操作刷新（flush）到本地和遠程磁碟後再回復客戶端。主節點會在刷新之前批處理一些日誌記錄，以此減少刷新和系統內複製對整個系統吞吐量的影響。

主節點通過重新執行操作日誌來恢復狀態。為了使啟動時間盡量短，我們必須保持日誌較小。當日誌超過一個特定的大小時，主節點會檢查它的狀態。這樣一來，以使它能夠在足夠小的代價下通過載入本地磁碟的最後一個檢查點及之後的日誌記錄進行恢復。檢查點是一個類似 B 樹的數據結構，能夠直接映射到記憶體中，並且在用於命名空間查詢時無需額外的解析。這大大提高了恢復速度，增加了可用性。

因為創建檢查點需要一定的時間，所以主節點的內部狀態會被格式化，格式化的結果保證了新檢查點的創建不會阻塞正在進行的修改操作。當主節點切換到新的日誌文件時，GFS 通過另一個執行緒進行新檢查點的創建。新檢查點包括切換前所有的修改操作。對於一個有幾百萬文件的集群來說，創建一個新檢查點大概需要1分鐘。當創建完成後，它將寫入本地和遠程磁碟。

恢復只需要最近完成的檢查點和在此之後的日誌文件。老的檢查點和日誌文件能夠被刪除，但為了應對災難性故障，我們會保留其中的一部分。檢查點的失敗不會影響恢復的正確性，因為恢復程式碼會探測並跳過未完成的檢查點。

2.7 一致性模型

GFS 採用弱一致性模型，能很好的支援分散式應用，同時實現上比較簡單。我們在這裡將討論 GFS 的一致性保障機制以及其對於應用的意義。我們也將著重描述了 GFS 如何維持這些一致性保障機制，但將一些細節留在了其它章節。

2.7.1 GFS的一致性保障機制

文件命名空間修改（如，創建文件）是原子性的。它們僅由主節點進行處理：命名空間鎖保障了操作的原子性和正確性；主節點操作日誌定義了這些操作的全局排序。

下圖是經過修改後的文件區域狀態表：

一個文件區域（region）在一個數據修改後的狀態依賴於該修改的類型、成功或失敗、以及是否為同步的修改。表1 總結了一次修改後的結果。

如果所有的客戶端無論從哪些副本讀取數據，得到的數據都是相同的，則這個文件區域為一致的 consistent。
在一個文件數據修改後，如果它是一致的，則這個區域已定義 defined，客戶端將看到被寫入的全部內容。
當一個修改完全沒有受到並發寫入操作的影響並成功時，那麼影響到的區域已定義（隱含一致性） consistent interspersed undefined：所有的客戶端將總會看到修改已經寫入的內容。

已定義的一定一致
並發成功的修改使區域處於一致，但未定義狀態 consistent but undefined：所有的客戶端將看到相同的數據，但是它可能不能反映出任意一個修改已寫入的內容。
- 通常，它是由一些來自多個修改操作的、混合的數據碎片組成的。
一致的未必已定義，因為數據一致，但有些操作可能未成功或成功了一半
一個失敗的修改會造成區域的不一致性（因此也沒有被定義）inconsistent：不同的客戶端在不同的時間可能會看到不同的數據。

我們將在後面描述我們的應用如何區分已定義和未定義的區域。這些應用程式不需要更深入的區分不同種類的未定義區域間的區別。

數據修改操作可能是寫入 write 或記錄追加 append 操作。一個寫操作會將數據寫入到應用指定的文件位置。偏移位置將被返回給客戶端，並標明包含這個記錄的已定義區間的開始位置。

如果有多個並發修改操作，一個記錄追加操作會將數據（記錄）至少一次的原子性的追加到文件，而具體的偏移量是由GFS選定的。
一個通常的追加操作僅僅是將數據追加到客戶端認為是當前文件結尾的位置。

此外。GFS 能夠在文件中插入數據或複製記錄，這種情況下這些數據佔據的文件區域被認為為非一致性的，但數量通常比用戶數據總量要小很多。

在一系列成功的修改操作後，被修改的文件區域被保證為是已定義的，並且包含了最後一次修改操作寫入的數據。GFS通過以下步驟完成上面行為：

在所有副本上按相同的順序執行一個塊上的修改操作（3.1）
使用版本號來檢測並複製過期文件（4.5）
- 這種過期可能是由於塊伺服器宕機而造成了部分修改丟失引起的。過期的副本不會再涉及修改操作，主節點也不會將該副本返回給客戶端。它們會儘快的進行垃圾回收操作。

因為客戶端快取了塊位置資訊，它們可能會在位置資訊更新前直接訪問到一個過期的副本。這個問題出現的窗口是受快取條目的超時時間和下一次文件的打開時間限制的，下一次文件打開時才會對這個文件的所有塊資訊的快取進行清理。此外，由於大多數文件都是只能追加的，一個過期的副本經常會返回一個因過早結束而缺失數據的塊，而不是過期的數據。當一個讀客戶端再次向主節點查詢時，它將會立即獲得塊的當前位置資訊。

在一個修改操作成功執行完一段時間後，組件的失效依然能損壞或刪除數據。

GFS通過在主節點和所有塊伺服器間定期的握手來標識失效的塊伺服器，並通過校驗和來探測數據損壞（5.2）。
一旦問題被發現，數據將會儘快的利用有效副本進行恢復（4.3）。

只有在GFS反應之前的幾分鐘之內，一個塊的所有副本都丟失，這個塊才會徹底的丟失。在這種情況下，應用會接收到明確的錯誤碼，而不是損壞的數據。

2.7.2 應用的實現

GFS 基於一些簡單的技術實現了一個寬鬆的一致性模型：

依賴追加而不是覆蓋。
檢查點
寫入時自驗證。
自標識的記錄。

這些技術在 GFS 的其他設計目標已經是必不可缺的，所以我們可以理解為一致性模型沒有帶來額外的負擔。

實際中，我們所有的應用都是通過 append 而不是 overwriting 來修改文件。在一個典型的例子中，一個寫操作生成一個文件，並從頭到尾的寫入數據。它將寫入完數據的文件原子地重命名為一個不變的名字，或者周期性的創建檢查點來記錄有多少執行成功的寫操作。

檢查點也含有應用層的校驗和。讀操作僅驗證並處理上一個檢查點之後的文件區域，這個文件區域應該是已定義的。即使一致性和並發性問題，這個方法很好地滿足了我們的需求。追加寫操作比隨機寫操作更有效率，對應用的錯誤更有彈性。檢查點允許寫操作逐步地進行重啟，並防止讀操作處理已成功寫入但在應用視角上沒有處理完畢的文件數據。

在另一個典型應用中，許多寫操作並行的追加一個文件，如進行結果的合併或者作為一個生產者-消費者隊列。記錄追加方式的「至少一次追加」的特性保證了每個寫操作都有輸出。

讀操作使用下面的方法處理偶爾的填充數據和重複數據：

每個寫操作寫入的記錄都包含了一些額外的資訊，如校驗和，以使這個記錄能夠被驗證。
一個讀操作能夠通過校驗和識別並丟棄額外的填充數據和記錄碎片。
如果它不能忍受偶現的重複數據（如會導致非冪等的文體），它能通過記錄中的唯一標識來進行過濾。這些標識通常應該可以用於命名相關的應用實體，如網頁文檔。
這些處理 I/O 的函數（除了刪除重複數據）都在應用的共享庫中，並且適用於 Google 其它的文件介面實現。

於是，相同序列下的記錄，加上偶爾出現的重複數據，總是被分發到記錄的讀操作上。

3. 系統交互

我們設計這個系統時，需要最小化所有操作與 Master 的交互。依照這個前提，我們描述了客戶端、Master 和塊伺服器之間如何進行交互，來實現數據的修改、原子記錄追加，以及快照。

3.1 租約(Lease)和修改操作順序

一個修改操作是一個改變了內容或塊元數據的操作，如一個寫操作或者一個追加操作。一個修改操作將在一個塊的所有副本上進行。我們使用租約來保證一個修改在副本間的順序一致性。

Master 將一個塊租約授予所有副本中的一個，這個副本成為 Primary。
- 此時 Master 會找到一個持有最新版本數據的塊作為 Primary，並將這個 Primary 自增後的新版本號作為最新的版本號，除非在後面發現其他塊中有更新的版本號，那它會認為他在尋找 Primary 時出錯了。正常情況下除非 Master 崩潰過，那麼他一定知道最新的版本號是什麼。
Primary 對一個塊的所有修改操作選擇一個串列的順序，所有的副本在執行修改時都按照這個順序。
因此，全局的修改操作的順序首先由 Master 選擇的授予租約的順序決定，然後由租約中Primary 分配的序列號決定。

租約機制的設計是為了最小化 Master 的管理開銷，一個租約初始超時時間為 60 秒，然而，只要塊正在被修改，Primary 就能向主節點請求租約延長（一般會被同意）。這些續約的請求和授予都包含在主節點和所有塊伺服器間定期交換的心跳消息中。

主節點有時會在租約到期之前嘗試取消它（如，當 Master 想要禁止對一個被重命名的文件的修改操作時，就不再授予先前的 Primary 重命名操作的租約）。即使 Master 與 Primary 失去通訊，它也能在前一個租約到期後安全的將一個新租約授予另一個副本。

下圖是寫操作的控制流和數據流：

在圖2中，我們通過跟蹤一個寫操作的控制流，描述了整個過程：

客戶端詢問 Master 哪個塊伺服器持有這個塊的當前租約，以及這個塊的其它副本位置。如果沒有任何一個塊伺服器擁有租約，則 Master 選擇一個副本並授予一個租約（沒有在圖上顯示）。
Master 回復客戶端 Primary 的標識，以及其它（Secondary）副本的位置。客戶端快取這些數據用於以後的修改操作。只有當 Primary 不可達或者接收到 Primary 不再持有租約時才需要再一次請求主節點。
客戶端將數據推送到所有的副本。一個客戶端能夠以任意順序進行推送。每個塊伺服器將數據保存在內部的 LRU 快取中，直到數據被使用或者過期被替換掉。

通過對數據流和控制流的解耦，不管哪個塊伺服器為 Primary，我們都能夠通過基於網路拓撲來調度數據流，以此提高性能。3.2節將進一步討論。
一旦所有的副本都確認接收到了數據，客戶端將向 Primary 發送一個寫請求。這個請求確定了之前的數據被推送到了所有副本。Primary 為接收到的所有修改操作分配連續的序列號，這些操作可能來自多個客戶端，序列號提供了嚴格的序列化，應用按序列號順序執行修改操作，進而改變自己的狀態。

前面只是推送了數據到塊伺服器的快取中，此時才正式請求執行寫入
Primary 將寫請求發送到所有的 Secondary 副本上。每個 Secondary 副本按照 Primary 分配的相同的序列號順序執行這些修改操作。
Secondary 副本回復 Primary，表示它們已經完成了所有的操作。
Primary 回復客戶端。任意副本上的任意錯誤都將報告給客戶端。在一些錯誤情況下，可能部分寫操作已經在 Primary 和一些 Secondary 副本上執行成功。（如果失敗發生在 Primary，它將不會分片一個序列號，並且不會被傳遞。）

此時客戶端的請求將被視為已經失敗，而那些被修改的區域停留在不一致的狀態上。我們的客戶端程式碼通過重試失敗的修改操作來處理這種錯誤。在從頭開始重複執行之前，它將在第3步到第7步上做幾次重做的嘗試。

如果一個應用的寫操作數據很大或者跨越了塊邊界，GFS 客戶端會將這個操作分割成幾個寫操作。這些操作都遵循上面描述的控制流，但是可能會被其它客戶端上的請求打斷或覆蓋。因此，一塊共享的文件區域可能最終包含不同客戶端的數據碎片。儘管如此，一個快伺服器內的所有的副本的對應文件區域都是完全相同的，因為這些獨立的寫操作在所有副本上一定都按著相同的順序成功執行。如 2.7 節所提到的那樣，這使文件區域處於一個一致但未定義的狀態。

3.2 數據流

為了有效的利用網路，我們將數據流和控制流分開。控制流從客戶端到 Primary 上，再到所有的Secondary 上，而數據則以管道形式、線性的沿一個精心設計的塊伺服器鏈進行推送。我們的目標是最大限度的使用每台伺服器的網路頻寬，避免網路瓶頸和高延遲，最小化推送所有數據的時間延遲。

為了有效利用每台機器的網路頻寬，數據被線性的沿一個塊伺服器組成的鏈進行推送，而不是按著其它拓撲進行分發（如，樹）。因此每台機器的出口頻寬都用於以最快的速度專註地傳輸數據，而不是分配給多個接收者。

為了儘可能的避免網路瓶頸和高延遲鏈路，每台機器只將數據推送給網路拓撲中最近的沒有接收到數據的機器。假設客戶端將數據推送給塊伺服器 S1 到 S4。它將數據發送給最近的塊伺服器，我們稱之為 S1，S1 將數據推送給 S2 到 S4 中最近的塊伺服器，我們稱之為 S2，類似的，S2 將數據推送到 S3 或 S4 中距離 S2 較近的塊伺服器等等。我們的網路拓撲足夠簡單，可以通過IP地址來精確的估計距離。

最後，我們通過在 TCP 連接上使用管道傳輸數據來最小化時間延遲。一旦一個塊伺服器接收到數據，則馬上開始進行數據推送。管道對我們的幫助很大，因為我們採用了全雙工的交換網路。立刻推送數據不會降低數據的接收速率。在沒有網路擁塞的情況下，將 B 個位元組傳輸到 R 個副本的理想時間消耗為 B/T+RL，這裡 T 是網路的吞吐量，L 是兩台機器間的傳輸延遲。我們的網路鏈路通常為100Mbps（T），並且 L 遠小於1ms，因此，在理想情況下，1MB 的數據能夠在 80ms 內分發完成。

3.3 原子性的記錄追加

GFS 提供了一種原子性的追加操作稱為記錄追加：

在傳統的寫操作中，客戶端指定數據寫入的位置在文件中的偏移量，這樣對同一個文件區域的並行寫操作不能進行序列化：該區域最終可能包含來自多個客戶端的數據片段。
然而，在一個記錄追加操作中，客戶端只需要指定數據，GFS 將數據至少一次原子性地追加到文件（如，一個連續的位元組序列）的 GFS 選定的一個偏移位置，並將這個偏移位置返回給客戶端。這與在沒有競爭的情況下，Uinx 下多個並發寫操作向一個使用 O_APPEND 選項打開的文件中寫數據相似。

記錄追加操作在我們的分散式應用中使用頻繁，許多運行在不同機器上的客戶端並行的向同一文件上追加數據。如果使用傳統的寫操作進行並發寫，客戶端將需要額外複雜的、昂貴的同步機制，比如，通一個分散式鎖的管理器。在我們的工作中，這樣的文件通常用於多個生產者/一個消費者隊列，或者合併來自許多不同客戶端的數據結果。

記錄追加操作是修改操作中的一種，遵循 3.1 中介紹的控制流程，只在 Primary 上有一些額外的邏輯。客戶端把數據推送到文件最後一個塊的所有的副本上，然後將向 Primary 發送它的請求。Primary 會檢查這次追加操作是否使塊的大小超過了最大尺寸（64MB）。

如果超過，它將把這個塊填充滿，通知所有的 Secondary 副本進行相同的操作，並回復客戶端表明這個操作將在下一個塊上重新執行。（記錄追加操作的數據大小嚴格控制在最大尺寸的 1/4 以內，以確保最壞情況下碎片的數量在一個可接受範圍。）
通常情況下，如果記錄不超過最大尺寸，Primary 將數據追加到它的副本上，然後通知Secondary 把數據寫到與 Primary 相同的位置上，最後回復客戶端操作成功。

如果在任意一個副本上的記錄追加失敗，客戶端將重試這個操作。因此，在同一個塊的副本上可能包含不同的數據，包括同一個記錄的全部或部分的重複數據。GFS 不保證寫入的數據在位元組上完全相同，它只保證作為一個原子單元至少被寫入一次。這個特性能夠通過簡單的觀察得到：如果操作執行成功，數據肯定被寫入到了某些塊副本的相同位置。此外，在這之後，所有副本至少都達到了記錄尾部的長度。因此，即使一個不同的副本成為了 Primary，以後的任何記錄也都將被放置在更大的偏移位置或者是一個不同的塊上。在我們的一致性保障方面，記錄追加操作成功的寫入數據的區域是被定義的（因此是一致的），反之，介於中間狀態的區域是不一致的（因此是未定義的）。我們的應用使用在 2.7.2 討論的方法處理這種不一致的區域。

3.4 快照

快照操作幾乎瞬間為一個文件或一個目錄樹（源）創建一個拷貝，並且不會對正在進行的其它操作造成任何影響。我們的用戶使用它為一個巨大的數據集創建一個拷貝分支（而且經常遞歸的對拷貝進行拷貝），或者是在嘗試變化之前對當前的狀態創建檢查點，之後可以輕鬆的進行提交或回滾。

像 AFS 一樣，我們使用標準的寫時拷貝（Copy-On-Write）技術來實現快照。當 Master 接收到一個快照請求時，它先取消快照相關的文件塊的所有租約。這確保了任何後面對這些塊的寫操作將需要與 Master 進行交互，以獲取租約的持有者，這將為 Master 提供一個為塊創建一個新拷貝的機會。

寫時拷貝：在被修改時才真正執行拷貝

在租約被取消或者過期後，Master 將這些操作記錄到磁碟，然後以複製源文件或目錄樹元數據的方式來在記憶體上執行這些日誌記錄。新創建的快照文件與源文件指向相同的塊。

在快照操作後，我們以下面的方式來執行複製寫入：

客戶端第一次想要向塊 C 中寫入數據前，它將向 Master 發送一個請求來查找當前的租約持有者。
Master 注意到塊 C 的引用計數大於 1，它將推遲回復客戶端的請求，並選擇一個新的塊句柄 C』，然後通知每個擁有塊 C 副本的塊伺服器，創建一個新的塊 C』。通過在同一個塊伺服器上創建一個新的塊，我們能確保這個拷貝是本地的，不需要通過網路進行的（我們的磁碟速度是100MB乙太網鏈路的3倍）。
從這點上看，請求的處理不會與其它的塊處理有差別：主節點將新塊 C』的租約授予其中一個副本，並回復客戶端，客戶端能夠進行一般的寫操作，並不知道這個塊是從一個已存在的塊上創建出來的。

4. Master操作

Master 完成了以下這些工作：

執行所有的命名空間操作。
管理整個系統內的所有塊的副本。
- 決定塊的存儲位置。
- 協調系統範圍內的各種行為以保障塊能夠有足夠的副本。
- 均衡所有塊伺服器的負載。
- 以及回收不再使用的存儲空間。

4.1 命名空間管理與鎖

許多 Master 操作會佔用較長時間：例如，一個快照操作必須撤銷所有進行快照的塊所在塊伺服器的租約，我們不想推遲正在進行的其它 Master 操作，因此，我們允許多個操作同時進行，並使用命名空間區域的鎖來確保這些操作按適當的順序執行。

不像許多傳統的文件系統那樣，GFS 沒有一個目錄數據結構來列出這個目錄下的所有文件，也不支援對文件和目錄的別名操作（如，Unix術語中的硬鏈接或符號鏈接）。GFS 的命名空間邏輯上表現為一個將全路徑名映射為元數據的查詢表。利用前綴壓縮，這個表能夠高效的存儲在記憶體中。每個命名空間樹中的節點（無論是一個絕對文件名還是一個絕對目錄名）都有一個與之關聯的讀寫鎖。

每個主節點操作在執行前都先獲得一系列的鎖，通常，如果它涉及到/d1/d2/.../dn/leaf，它將：

獲得目錄名的讀鎖/d1，/d1/d2，...，/d1/d2/.../dn。
獲取完全文件名/d1/d2/.../dn/leaf的一個讀鎖或寫鎖。

注意，這裡的 leaf 根據其操作，可能是一個文件，也可能是一個目錄。

我們現在舉例說明在/home/user構造快照成/save/user時，這個鎖機制如何防止另一個 Master 任務創建一個文件/home/user/foo：

快照操作獲得了/home和/save上的讀鎖，以及/home/user和/save/user上的寫鎖。
而文件創建操作則獲得了/home和/home/user上的讀鎖，以及/home/user/foo上的寫鎖。因為它們都試圖獲得/home/user上的鎖而造成衝突，所以這兩個操作將適當的進行排序。

文件創建不需要獲取它的父目錄的寫鎖，因為這裡沒有「目錄」或類似 inode 等用來防止被修改的數據結構。文件名上的讀鎖足以防止父目錄被刪除。

這種鎖機制的一個很好的性質是它允許對同一個目錄下的並發操作。比如，在一個相同目錄下，多個文件創建操作可以同時進行：每個操作獲取目錄上的讀鎖，以及其文件名上的寫鎖。目錄名上的讀鎖足以防止目錄被刪除、重命名或進行快照。文件名上的寫鎖可以使使用同一名字創建文件的兩次操作順序執行。

因為命名空間可能包含很多節點，所以讀寫鎖對象採用惰性分配策略，一旦不再使用則被刪除。同樣，鎖需要按一個相同的順序被獲取來防止死鎖：他們先對命名空間進行排序，並在同一級別按字典序排序。

4.2 副本布局

一個GFS集群採用高度分布的多層結構，它通常有幾百個塊伺服器分布在許多機器架構上。這些塊伺服器被來自相同或不同機器架構上的數百個客戶端輪流訪問。不同機架上的兩台機器間的通訊可能要經過一個或多個網路交換，此外，機架的入口或出口頻寬可能比機架上所有機器的頻寬總和要小。多層的分散式對數據的靈活性、可靠性和可用性提出了挑戰。

塊副本布局策略有兩大目標：最大化數據的可靠性和可用性，最大化頻寬利用率。為了這兩個目標，將副本分布在不同的機器是不夠的，它只防止了磁碟或機器的失效，以及最大化了機器的頻寬利用率。我們也必須將副本分布到不同的機架上，這樣可以確保在整個機架損壞或掉線（例如，由於網路交換或電源線路的問題造成的資源共享失效）的情況下，一個塊的一些副本能夠保存下來並能正常使用。這意味著在網路流量上，特別是在讀取一個塊時，可以利用多個機架的整合頻寬。另一方面，寫操作必須將數據導向多個機架，這個代價是我們願意付出的。

4.3 塊副本的創建、重新複製和重新負載均衡

三個原因造成了塊副本的創建：塊創建、重新複製和重新負載均衡。

當主節點創建一個塊時，它會選擇在哪個塊伺服器上初始化一個空的副本。主節點會考慮幾個因素：

我們想要在一個空間使用率低於平均值的塊伺服器上放置新的副本，這會使塊伺服器間的磁碟利用率基本相等。
我們想要限制每台塊伺服器上近期創建塊的數量。儘管創建本身是廉價的，但是它也預示著馬上就會有大量的數據寫入。塊伺服器往往在一波寫入後就變成實際只讀的了。
我們想要將一個塊的副本分布到不同的機架上。

當副本的可用數量低於用戶指定的值時，Master 會儘快進行塊的重新複製。以下原因可能引起這個操作：

一個塊伺服器不可用。
塊伺服器報告存儲的副本可能被損壞。
其中一個磁碟由於錯誤不可用。
備份數量的設置值變大了。

每個需要進行重新複製的塊基於幾個因素優先進行：

一個是塊現有的副本數量與目標數差多少。比如一個丟失兩個副本的塊比丟失一個副本的優先順序高；
相對於最近被刪除的文件的塊來說，我們優先對活躍的文件的塊進行重新複製（4.4）；
為了最小化失效對正在運行的應用的影響，我們會提高阻塞客戶進程的塊的重新複製優先順序。

Master 選取優先順序最高的塊，通過通知一些塊伺服器從一個可用副本上拷貝塊數據來「克隆」它。選擇副本位置的方法與創建時類似：平均磁碟空間使用率，限制單一塊伺服器上運行的克隆操作熟練，以及跨機架分布。

為了防止克隆操作的流量影響到客戶端的流量，Master 限制了集群和每個塊伺服器上正在運行的克隆操作數量。此外，每個塊伺服器通過減少發往源塊伺服器的讀請求，限制了每個克隆操作所佔用的頻寬。

最後，Master 周期性地對副本重新進行負載均衡：它檢查當前的副本分布情況，並將副本移動到更合適的磁碟空間上，達到負載均衡。通過這個過程，Master 逐步的填充新的塊伺服器，而不是馬上使用新的塊和大量的寫入流量填充它。這個新副本的分布標準與上面提到的類似。此外，Master 必須選擇移動哪個已存在的副本，通常情況下，它更傾向於從剩餘空間小於平均值的那個塊伺服器上移動副本，以使磁碟使用率相等。

4.4 垃圾回收

在一個文件被刪除後，GFS 不會立即回收可用的物理存儲空間。而是只在文件和塊級別上定期地進行垃圾回收。我們發現，這個方法使系統更加簡單，更加可靠。

4.4.1 機制

當一個文件被應用刪除時，Master 會像其他操作一樣立即記錄下這個刪除操作。然而，文件僅僅會被重命名為一個包含刪除時間戳且隱藏的名字，而不是立即回收資源。在 Master 定期掃描文件系統的命名空間期間，它將真正刪除已經被隱藏超過三天的文件（這個間隔可以配置）。在此之前，文件仍然可以通過新的特殊的名字進行讀取，也可以通過重命名為普通的文件名從而撤銷刪除操作。當隱藏文件從命名空間中真正被刪除時，記憶體中對應的元數據也會被清除，這樣能有效的切斷文件和它的所有塊的連接。

在對塊的命名空間做類似的掃描時，Master 標識出孤兒塊（任何文件都無法訪問到的塊），並將那些塊的元數據清除。在與 Master 進行定期的心跳資訊交換時，每個塊伺服器報告其所含有塊的集合，Maste r回復塊伺服器哪些塊沒有出現在 Master 的元數據中，塊伺服器將釋放並刪除這些塊的副本。

4.4.2 討論

雖然分散式回收機制在程式語言領域是一個需要複雜解決方案的難題，但在我們的系統中十分簡單。我們能簡單的確定一個塊的所有引用：它們唯一的保存在 Master 的文件-塊映射中。我們也能輕鬆的確定一個塊的所有副本：它們都以 Linux 文件的形式存儲在每台塊伺服器的指定目錄下。任何 Master 不認識的副本都是「垃圾」。

用於存儲回收的垃圾回收方法通過惰性刪除擁有幾個優勢：

首先，對於組件失效是常態的大規模分散式系統來說，這種方式簡單可靠。塊創建操作可能在一些塊伺服器上執行成功，但在另一些伺服器上執行失敗，殘餘的副本在主節點上無法識別。副本刪除消息可能丟失，Master 必須重新發送執行失敗的消息，包括自身的和塊伺服器的。垃圾回收機制提供了一個一致的、可靠的方法來清除沒用的副本。
其次，它將存儲回收操作合併到了 Master 定期的後台操作中，比如定期瀏覽命名空間和與塊伺服器握手。批處理的方式分攤了任務的開銷。此外，只有在 Master 相對空閑時才會完成垃圾回收，Master 對客戶端需要及時回復的請求有更高的優先順序進行響應。
第三，延遲回收存儲空間可以為防止意外的、不可撤銷的刪除操作提供一個安全保障。

在我們的經驗中，上述機制主要的缺點是：當存儲空間緊張時，會阻礙用戶對系統進行及時調整。頻繁創建和刪除臨時文件的應用不能馬上重用刪除數據後的可用空間。我們通過在已被刪除的文件上顯式的再次進行刪除來解決垃圾回收的這些問題；我們也可以允許用戶對命名空間的不同部分應用不同的複製和回收策略。比如，用戶可以指定一些目錄樹下的所有文件進行無副本存儲，任何被刪除的文件會從系統上迅速的、不可恢復的刪除。

4.5 過期副本的檢測

如果一個塊伺服器失效並在宕機期間丟失了塊的修改操作，塊副本可能會過期。對於每個塊，Master 維護一個塊版本號來區分最新的副本和過期的副本。

每當 Master 授予某個塊一個新租約，這個 Primary 副本都會自增版本號，並向所有副本通知新版本號。
在客戶端接收到通知並開始進行寫操作之前，Master 和 Master 的副本將此塊的新版本號持久化。
如果其它副本當前不可用，它的塊版本號將不會被更新。
當塊伺服器重啟並報告它所有的塊集合和它們相應的版本號時，Master 還會探測這個塊伺服器下副本的版本號。
1. 一方面記錄下是否有過期的副本。
2. 另一方面如果 Master 發現有一個版本號高於自己的記錄，Master 會假設在它自己在授予租約後、持久化前發生了失敗，因此會選擇更高的版本號作為最新的版本號。

Master 在定期的垃圾回收操作中清除過期的副本。在這之前，當它回復客戶端的塊資訊請求時，它將認為一個過期的副本實際上根本並不存在。

另一個安全措施是，當 Master 通知客戶端哪個塊伺服器持有這個塊的租約時，或者在進行克隆操作期間它通知一個塊伺服器從另一個塊伺服器上讀取數據時，請求中包含塊版本號。客戶端或塊伺服器在執行操作時會驗證這個版本號，以保證總是可訪問的最新的數據。

5. 容錯和診斷

在設計系統時，最大的挑戰之一就是如何處理頻繁的組件故障。組件的數量和品質讓這些問題變得非常普遍。我們不能完全的信任機器，也不能完全的信任磁碟。組件故障可能會造成系統不可用，甚至損壞數據。我們將討論如何面對這些挑戰，以及當組件不可用時系統內部用於診斷問題的工具。

5.1 高可用性

在 GFS 集群的數百台伺服器中，必定有一些機器在給定的一段時間內是不可用的。我們通過兩個簡單但有效的策略來保證整個系統的高可用性：快速恢復和複製。

5.1.1 快速恢復

Master 和塊伺服器都被設計為無論如何終止，它們都能夠在幾秒內恢復自己的狀態並重新啟動。實際上，我們並不區分正常的和不正常的終止；可以通過 kill 掉進程來關閉服務。由於它們的請求超時而沒有完成，客戶端或其他伺服器可能經歷小的顛簸，但它們會重新連接伺服器並重試。6.2.2 節記錄了實際實驗中觀察得到的重啟時間。

5.1.2 塊複製

如之前討論過的，每個塊被複制到不同機架上的多個塊伺服器上。用戶能夠為文件命名空間的不同部分指定不同的複製級別，默認有三個。當有塊伺服器掉線或通過校驗和（5.2節）檢測出損壞的副本時，Master 克隆已存在的副本來保證每個塊有足夠的副本。

儘管複製策略非常有效，但我們也在探索其他的跨伺服器的冗餘解決方案，如奇偶校驗，或者糾刪碼（erasure code），來應對我們日益增長的只讀存儲需求。在我們高度低耦合的系統中，這些複雜的冗餘方案是具有挑戰的，但並不是不可實現的，因為我們的操作主要是追加和讀取，而不是小規模的隨機寫。

5.1.3 Master複製

為了可靠性，Master 的狀態也被複制。它的操作日誌和檢查點被複制到多個機器上。一個修改操作只有在它的日誌被刷新到本地磁碟和所有的 Master 副本後才認為被提交完成。簡單的說，一個Master 負責所有的操作，包括後台的行為，如垃圾回收等改變系統內部狀態的行為。當它失效時，能夠瞬間重啟。如果它的機器或磁碟發送故障，GFS 的外部監控會在其它有副本操作日誌的機器上啟動一個新的 Master。客戶端視角下只使用主節點的名字（如，gfs-test），它是一個 DNS 的別名，可以更改這個名字來訪問被重新放置到其它機器上的 Master。

此外，當 Primary Master 宕機時，「影子」Master可以為文件系統提供一個只讀的訪問介面。它們是影子，而不是鏡像，它們內部的數據會稍微的落後於 Primary Master，通常不到1秒。因此，它們對於那些不經常修改的文件的讀取，或是不太在意得到的是稍微過期的數據的應用來說是有效的。實際中，因為文件內容是從塊伺服器讀取的，所以應用察覺不到過期的文件內容。在短暫的時間窗口內，過期的可能是文件的元數據，如目錄內容，或訪問控制資訊。

為了保持最新的狀態，影子 Master 讀取一個正在增長的操作日誌副本，並執行與 Primary Master相同的操作序列來改變自己的數據結構。像 Primary 那樣，它在啟動後輪詢塊伺服器（之後很少）來定位塊副本，並通過頻繁的交換握手資訊來監控它們的狀態。當 Primary Master 決定創建或刪除副本造成位置資訊更新時，影子 Master 才會通過 Primary Master 更新狀態。

5.2 數據完整性

每個塊伺服器使用校驗和來探測存儲的數據是否被損壞。考慮到一個 GFS 集群經常由數百個機器上的數千塊磁碟組成，由於磁碟的損壞而造成的讀和寫路徑上的數據損壞或丟失是很常見的。（其中的一個原因見7.1節）我們能夠使用塊的其它副本來進行恢復，但是無法通過不同塊伺服器上的副本的比較來探測出數據塊是否損壞。此外，不同的副本之前有分歧可能是合理的：GFS 修改操作的語法，特別是之前討論過的原子追加操作，本身就不能保證所有副本都相同。因此，每個塊伺服器必須獨立的通過校驗和驗證它所擁有的拷貝是否合法。

一個塊被分割成 64KB 大小的 block，每個 block 都有一個對應的 32bit 校驗和。像其它元數據一樣，校驗和保存在記憶體中，並通過日誌永久存儲，與用戶數據分開。

對於讀操作，在把數據返回給請求者之前，塊伺服器要驗證讀範圍內所有數據 block 的校驗和，因此，塊伺服器不會將損壞的數據傳播到其它機器上。如果一個 block 與記錄的校驗和不匹配，塊伺服器會返回給請求者一個錯誤，並向 Master 報告這個錯誤。在響應中，請求者將從其它的副本讀取數據，同時，Master 將從其它副本上克隆這個塊。在一個新的可用的副本複製完畢後，Master 會通知報告錯誤的塊伺服器刪除出錯的副本。

校驗和對讀操作幾乎沒有影響，原因有幾個：

因為大多數的讀操作至少需要讀取幾個塊，我們只需要讀取一小部分額外的數據用於驗證驗證和。
GFS 客戶端程式碼通過試圖將讀操作對齊到校驗和的 block 邊界上，大大減小了驗證的開銷。
此外，塊伺服器上的校驗和查詢和對比不需要任何 I/O 就能完成，校驗和的計算可以和 I/O 操作同時進行。

校驗和計算針對在塊尾部進行追加寫操作做了很大的優化（相對於覆蓋已有數據的寫操作）。我們僅增量更新最後一個不完整的塊的校驗和，並用追加的新的校驗和來計算 block 新的校驗和。即使最後一個不完整的校驗和已經被損壞，並且我們現在沒有探測出來，新的校驗和將不匹配存儲的數據，當這個塊下一次被讀取時，就會檢測出數據已經損壞。

相反的，如果寫操作覆蓋塊中已經存在的一部分，我們必須讀取並驗證要被覆蓋的這個範圍內的第一個和最後一個 block，然後執行寫操作，最後計算並記錄新的校驗和。如果我們在覆蓋它們之前不進行這一對驗證，新的校驗和可能會隱藏沒有被覆蓋區域的錯誤。

在空閑的時候，塊伺服器能瀏覽和驗證不活躍的塊，這允許我們探測很少被讀取的塊的數據損壞。一旦損壞被探測到，Master 就能創建一個新的沒有損壞的副本，並刪除已損壞的副本。這能夠防止不活躍的、已損壞的塊欺騙 Master，使 Master 認為它是塊的一個可用的副本。

5.3 診斷工具

在問題隔離、調試和性能分析方面，詳盡的、細節的診斷日誌給我們很大的幫助。如果沒有日誌，我們很難理解短暫的、不重複的機器間的消息交互。GFS 伺服器生成診斷日誌用於記錄許多關鍵的事件（如塊伺服器啟動和關閉），以及所有的遠程調用（RPC）的請求和響應。這些診斷日誌能夠被自由的刪除，不會給系統帶來任何影響。然而，在空間允許的情況下，我們會盡量保存這些日誌。

遠程調用（RPC）日誌包括網路上所有的請求和響應，除了文件數據被讀取或寫入。通過匹配請求和響應，以及核對其它機器上的 RPC 記錄，我們能重建這個交互歷史用於診斷錯誤。這些日誌也能用於跟蹤負載測試和性能分析。

記錄日誌所造成的性能影響很小（遠小於它帶來的好處），因為這些日誌非同步的、順序的被寫入。最近的事件也會保存在記憶體中，可用於持續的在線監控。

6. 度量

在這章中，我們介紹幾個微基準測試來描述 GFS 架構和實現中固有的瓶頸，還有一些來自於 Google 正在使用的集群中。

6.1 微基準測試

我們在一個由1個主節點，2個主節點副本，16個塊伺服器和16個客戶端組成的GFS系統上進行性能測試。注意，這個配置是為了方便測試，一般的集群包含數百個塊伺服器和數百個客戶端。

所有的機器都配置為兩個1.4GHz的PIII處理器，2GB的記憶體，兩個5400rpm的80GB的磁碟，以及一個100Mpbs全雙工乙太網連接到一個HP2524的交換機上。兩個交換機之間只用1Gpbs的鏈路連接。

6.1.1 讀操作

N個客戶端同時從文件系統讀取數據。每個客戶端從320GB的數據中，隨機的選取4MB區間進行讀取。這個讀操作會重複256次，使客戶端最終讀取到1GB的數據。塊伺服器總共只有32GB的記憶體，，所以我們期望最多有10%的快取命中率。我們的結果應該與沒有快取的情況下相近。

圖3：總吞吐量。頂上的曲線顯示了理論情況下的由我們的網路拓撲引入的限制。下面的曲線顯示了測試的吞吐量。它們顯示了置信區間為95%的誤差，在一些情況下，由於測量的方差小而不太明顯。

圖3（a）中顯示了N個客戶端的總讀取速率和它的理論極限。當兩個交換機之間的1Gpbs鏈路飽和時，理論極限為125MB/s，或者當客戶端的網路介面達到飽和時，每個客戶端的理論極限為12.5MB/s，無論哪個都適用。當只有一個客戶端進行讀取時，觀測到的讀取速率為10MB/s，或者是每個客戶端極限的80%。對於16個讀操作，總速率可以達到94MB/s，大約是125MB/s網路極限的75%，或者是每個客戶端到達6MB/s的速率。效率從80%下降到75%的原因是，當讀取操作的數量增加時，多個讀操可能同時的從同一個塊伺服器上讀取數據。

6.1.2 寫操作

N個客戶端同時往N個不同文件進行寫操作。每個客戶端以每次1MB的速率向一個新文件寫入1GB的數據。總的寫入速率和理論極限顯示在圖3（b）中。理論極限是67MB/s，因為我們需要把每個位元組都寫入到16個塊伺服器中的3個，而每個塊伺服器的輸入連接極限為12.5MB/s。

每個客戶端的寫入速率為6.3MB/s，大約是極限的一半，主要的原因是我們的網路協議棧，它與我們用於推送塊副本的管道（pipelining）方式不太適應。從一個副本到另一個副本傳播數據的延遲降低了整個系統的寫入速率。

16個客戶端的總寫入速率達到35MB/s（每個客戶端的速率大概是2.2MB/s），大約是理論極限的一半。與多個客戶端進行讀操作的情況類似，由於進行寫操作的客戶端數量的增加，客戶端同時向同一個塊伺服器寫入的幾率也會增加。此外，寫操作衝突的幾率比讀操作的要更大，因為每次寫操作需要涉及三個不同的副本。

寫操作比我們想要的要慢，在實際中，這不會成為一個主要的問題，因為即使對於單個客戶端它也增加了時延，但是對於含有大量客戶端的系統來說，它不會對系統的寫入頻寬有太大影響。

6.1.3 記錄追加

圖3（c）顯示了記錄追加的性能，N個客戶端同時向一個單獨的文件追加數據。性能受存儲文件最後一個塊的塊伺服器的網路頻寬的限制，而不是客戶端的數量。它的速率由一個客戶端的6MB/s下降到16個客戶端的4.8MB/s，主要是由衝突和不同客戶端的網路傳輸速率不同造成的。

我們的應用傾向於同時處理多個這樣的文件。換句話說，N個客戶端同時向M個共享文件追加數據，N和M在0到幾百之間。因此，在我們的經驗中，塊伺服器網路衝突在實際中不是一個嚴重的問題，因為當塊伺服器正在忙於處理一個文件時，客戶端可以進行另一個文件的寫入操作。

6.2 實際應用中的集群

我們現在測試了兩個Google正在使用的集群，它們有一定的代表性。集群A通常用於上百個工程師進行研究和開發。一個普通的任務被人為初始化，並運行幾個小時，它讀取幾MB到幾TB的數據，進行轉換或分析數據，並將結果寫回到集群中。集群B主要用於生產數據的處理。在很少人為干預下，這些任務運行更長的時間，持續的產生和處理幾TB的數據集。在這兩個實例中，一個單獨的任務由運行在很多機器上的很多進程同時讀和寫很多文件組成。

6.2.1 存儲

表2：兩個GFS集群的屬性

如表2的前五個條目所示，兩個集群都有上百個塊伺服器，支援數TB的磁碟空間，存儲了大小合適的數據，但沒有佔滿。「已使用空間」包括所有的塊副本。實際上，所有的文件都有三個副本，因此，集群實際上存儲了18TB和52TB的文件數據。

兩個集群的文件數量相近，不過B含有更大比例的死文件，死文件是指被刪除或者被新版本替換的文件，但它們的存儲空間還沒有被回收。它也存儲了更多的塊，因為它的文件較大。

6.2.2 元數據

塊伺服器總共存儲了數10GB的元數據，大多數是用戶數據64KB的block的校驗和。塊伺服器上其它的元數據則是4.5節討論的塊版本號。

Master上的元數據要小很多，只有幾十MB，或者說，每個文件平均有100位元組的元數據。這符合我們對Master記憶體在實際中不會限制系統能力的設想。大多數的文件元數據是以前綴壓縮方式存放的文件名，其它的元數據包括文件的所有者和許可權，文件到塊的映射表，以及每個塊的當前版本號。此外，還為每個塊存儲了當前副本的位置資訊和引用計數用來實現寫時拷貝（COW）。

每個單獨的伺服器，不論是塊伺服器還是Master，只有50-100MB的元數據。因此恢復速度很快：在伺服器能夠應答請求之前，它會只花費幾秒時間先從磁碟中讀取元數據。然而，主節點會持續顛簸一段時間，通常是30秒-60秒，直到它從所有的塊伺服器上獲取到塊位置資訊。

6.2.3 讀寫速率

表3：兩個GFS集群的性能度量

表3中顯示了持續時間不同的讀寫速率，兩個集群在做這些測試前都已經運行了大概一個星期的時間。（這兩個集群是因為GFS更新到新版本而進行重啟。）

自從重啟後，平均寫速率一直小於30MB/s。當我們做這些測試時，B正在進行速率為100MB/s的大量寫操作，因為寫操作被傳送到三個副本上，所以將產生300MB/s的網路負載。

讀速率要達到高於寫速率。如我們設想的那樣，整個工作由更多的讀操作組成。兩個集群都在進行繁重的讀操作，特別是，集群A在前些周維持了580MB/s的讀速率。它的網路配置能夠支援750MB/s的速率，所以它有效的利用了它的資源。集群B支援的極限讀速率為1300MB/s，但是，它的應用只用到了380MB/s。

6.2.4 Master複製

表3也顯示了發往Master的操作速率，每秒有200-500個操作。Master可以輕鬆的應對這個速率，因此Master的處理性能不是瓶頸。

在早期的GFS版本中，Master有時會成為瓶頸。它花費大多數時間連續的瀏覽大的目錄（可能含有幾百幾千個文件）來查找指定的文件。我們已經改變了Master的數據結構，使用二分查找在命名空間中進行查找，以此提高效率。它也能輕鬆的支援每秒數千次的文件訪問。如果需要，我們能通過在命名空間數據結構之前放置名字查詢快取的方法來進一步提高速度。

6.2.5 恢復時間

在一個塊伺服器發生故障後，一些塊的副本數量會小於指定值，必須進行克隆操作使副本數恢復到指定值。恢復所有塊所需的時間由資源的數量決定。在一個試驗中，我們殺掉了B集群中的一個單獨的塊伺服器，這個塊伺服器大概有15,000個塊，包含了600GB的數據。為了減小對正在運行的應用的影響，以及為調度決策提供修正空間，我們的默認參數限制了集群的並發克隆數為91（塊伺服器數量的40%），在這裡，每個克隆操作被允許最多使用6.2MB/s的頻寬。所有的塊在23.2分鐘後恢復，複製速率為440MB/s。

在另一個試驗中，我們殺掉了兩個塊伺服器，每個包含了大約16000個塊和660GB的數據。這個雙故障造成了有266個塊的成為單副本。這266個塊作為更高的優先順序被克隆，並在兩分鐘之內恢復到至少有兩個副本的狀態，這樣可以讓集群處於一個能夠容忍另一個塊伺服器故障而不丟失數據的狀態。

6.3 工作量明細

在這章中，我們對兩個GFS集群的工作進行詳細的分解介紹，這兩個集群與6.2節中的類似，但不完全相同。集群X用於研究和開發，而集群Y用於生產數據的處理。

6.3.1 方法論和注意事項

這些結果中包含了只有用戶發起的請求，以至於它們能夠反映出由應用文件系統整體產生的工作量。它們不包含用於執行客戶端請求或者內部的後台行為的伺服器間的請求，如正向寫或重新均衡負載。

I/O操作的統計是基於從GFS伺服器的實際RPC請求日誌上重新建立起來的資訊的。例如，GFS客戶端為了增加並行性，會將一個讀操作分解成多個PRC，通過這些調用，我們可以推導出原始的讀操作。因為我們的訪問模式是高度模程式的，我們認為任何錯誤都屬於誤差。應用記錄的詳細日誌能夠提供更準確的數據，但是為了這個目的重新編譯和重啟上千個客戶端在邏輯上是不可能的，而且從這麼多機器上收集結果也是非常麻煩的。

應該注意不要對我們的工作量做過度的歸納，因為Google完全控制著GFS和其它自己的應用，應用針對於GFS做了優化，同樣，GFS也是為了這些應用而設計的。這類的相互作用同樣也存在於普通應用和文件系統之間，但是在我們的實例中，這種作用更加顯著。

6.3.2 塊伺服器工作量

表4：操作工作量大小明細表（%）

表4顯示了操作數量的分布。讀操作展現出一個雙峰的分布，小規模讀（64KB以內的）來自於查詢為主的客戶端，它從海量文件中查詢小片的數據。大規模讀取（大於512KB）來自於從頭到尾讀取整個文件的連續讀操作。

在集群Y中有一些讀操作沒有返回任何數據。我們的應用，特別是哪些在生產系統中的，經常將文件用於生產者-消費者隊列。生產者同時向一個文件追加數據，同時消費者從文件尾部讀取數據。有時，當消費者超過生產者時，就沒有數據返回了。集群X顯示這種情況不常發生，因為它經常用於進行短暫的數據分析，而不是分散式應用的長久數據分析。

寫操作也展現出一個雙峰的分布。大規模寫操作（超過256KB）通常是由於Writer使用了快取機製造成的；快取了較少的數據，頻繁的進行檢查點操作或同步操作，或者僅僅生成了少量數據的Writer解釋了為什麼存在小規模的寫操作（小於64KB）。

表5：位元組傳輸明細表（%）。對於讀操作，這個大小是實際的讀取和傳輸數據的總量，而不是請求的數據量。這兩個可能的不同點在於如果試圖讀取超過文件結束的大小，這樣的操作在我們的工作中並不常見。

對於記錄追加操作，集群Y比集群X中有更高的大規模追加操作比例，這是因為我們的生產系統使用了集群Y，針對GFS做了更多的優化。

表5顯示了按操作的數據大小得到的總的數據傳輸量。對於所有的操作，較大規模的操作（大於256KB）佔據了主要的傳輸量；小規模的讀操作（小於64KB）傳輸量較小，但是在讀取的數據量中仍佔有相當的比例，因為隨機讀操作需要進行查找工作。

6.3.3 追加操作 vs 寫操作

追加操作被頻繁的使用，尤其是在我們的生產系統中。對於集群X，寫操作與記錄追加操作在位元組傳輸量上的比例為108:1，在操作數量上的比例為8:1。對於集群Y，，這個比例為3.7:1和2.5:1。此外，這些比例說明了對於兩個集群，記錄追加操作所佔的比例都比寫操作的大。然而，對於集群X，在測試期間，使用的追加操作相當少，以至於結果幾乎被一兩個使用特定快取大小的應用歪曲了。

不出所料的，記錄追加操作佔據了我們的數據修改的主要工作量，而不是覆蓋寫操作。我們測試了在primary副本上被覆蓋的數據總量。這近似於一種情況，其中客戶端故意的覆蓋之前寫入的數據，而不是追加新的數據。對於集群X，覆蓋操作佔位元組修改的不到0.0001%，占操作數量的不到0.0003%。對於集群Y，這兩個比例都為0.05%。儘管這是微小的，但是仍然比我們預期的要高。它證明了這些覆蓋操作來自於客戶端對於錯誤和超時的重試操作。它們不是工作量的一部分，而是重試機制的結果。

6.3.4 Master工作量

表6：主節點請求明細表（%）

表6顯示了根據發往Master的請求類型的明細。大多數請求都是讀取操作查詢塊的位置資訊（FindLocation）和數據修改操作的租約持有者的資訊（FindLeaseHolder）。

集群X和Y在刪除請求的數量上有顯現的差別，因為集群Y存儲生產數據集，這些數據集會定期的重新生成數據以及用新版本的數據替換舊的數據。其中的一些不同被隱藏在了Open請求中，因為舊版本的文件可能以寫模式打開並從頭開始的方式，被隱式的刪除。

FindMatchingFiles是一個模式匹配請求，提供了「ls」和類似的文件操作。不像其他的Master操作，它可能處理一大部分命名空間，所以可能很昂貴。集群Y中看到了更多的這類請求，因為自動化的數據處理任務傾向檢測部分文件系統，來獲知整個應用的狀態。相反的，集群X的應用更多的處於用戶的顯式控制之下，經常預先知道所有所需文件的名字。

7. 經驗

在建造和部署 GFS 的過程中，我們經歷了各種問題，一些是操作上的，一些是技術上的。

起初，GFS 被想像為是我們生產系統的一個後台的文件系統。隨著時間的推移，GFS 的使用逐漸包含了研究和開發的任務。它開始完全不支援類似許可權和配額的功能，但是現在已經初步的包含了這些功能。雖然生產系統是被嚴格控制的，但是用戶則不會總是這樣。更多的基礎構件被需要用來防止用戶間的干擾。

一些最大的問題是磁碟和 Linux 相關的問題。我們的許多磁碟要求 Linux 驅動，它們支援一定範圍的 IDE 協議版本，但在實際中，只對最新版本的響應可靠。因為協議版本非常相似，這些驅動多數可以工作，但是偶爾也會有錯誤，造成驅動和內核對驅動器狀態的認識不一致。由於內核的問題，這會導致數據隱藏的被損壞。這個問題迫使我們使用校驗和來檢測數據是否損壞，同時我們修改內核來處理這些協議錯誤。

早期在使用 Linux2.2 內核時，由於fsync()效率問題，我們遇到了一些問題。它花費與文件大小成正比的時間，而不是修改部分的大小。對於我們的海量操作日誌，特別是在檢查點之前來說，確實是一個問題。我們在這個問題上花費了一些時間，通過同步寫解決了這個問題，最後還是移植到了 Linux2.4 上。

Linux 的另一個問題是一個單獨的讀寫鎖的問題，在這個地址空間內的任何執行緒都必須在將磁碟page in時（讀鎖）或在調用mmap()進行修改地址空間時持有這個鎖。我們發現我們的系統在低負載時，也會短暫出現超時現象，我們艱難的尋找資源瓶頸，或不定時發生的硬體故障。最後，我們發現在磁碟執行緒正在 page in 之前的映射數據時，這個單獨的鎖阻塞了主網路執行緒向記憶體中映射新數據。因為我們主要受網路介面的限制，而不是記憶體拷貝的頻寬，所以，我們用pread()來代替mmap()，使用一個額外的拷貝開銷來解決了這個問題。

儘管偶爾會有問題，Linux程式碼常常幫助我們發現和理解系統行為。在適當的時候，我們會推進這個內核，並與開源社區共享我們的這些改動。

8. 相關工作

像其他的大型分散式文件系統一樣，如AFS，GFS提供了一個與位置無關的命名空間，它能使數據為了負載均衡或容錯透明的遷移。與AFS不同的是，GFS把文件數據分別到不同的存儲伺服器上，這種方式更像xFS和Swift，這是為了提高整體性能和增加容錯能力。

由於磁碟相對便宜，並且複製要比RAID的方法簡單許多，GFS當前只使用了複製來提供冗餘，所以比xFS和Swift存儲了更多的原始數據。

與AFS、xFS、Frangipani以及Intermezzo等文件系統不同，GFS並沒有在文件系統介面下提供任何快取機制。我們的目標工作是一個運行的應用很少會讀取重複的數據，因為他們要麼是從一個大的數據集中流式的讀取數據，要麼是隨機的進行讀取。

一些分散式文件系統，如Frangipani、xFs、Minnesota』s GFS和GPFS，去掉了中間的伺服器，依靠分散式演算法來保證一致性和進行管理。為了簡單的設計、增加它的可靠性和獲得彈性，我們選擇了中心化的方法。特別的是，因為Master已經保存有大多數有關的資訊，並可以控制它們的改變，因此，它極大地簡化了原本非常複雜的塊分配和複製策略的方法。我們通過保持較小的Master狀態資訊，以及在其它機器上做完整的備份來提高系統容錯性。彈性和高可用性（對於讀操作）通過影子Master機制來提供的。更新Master狀態是通過追加預寫日誌來實現持久化的。因此，我們可以調整為使用類似 Harp 的主拷貝方式來提供高可用性的，它比我們目前的方式有更高的一致性保證。

我們解決了一個類似 Lustre 在有大量客戶端時總的傳輸性能的問題。然而，我們通過只關注我們自己的應用，而不是創建一個適用於 POSIX 的文件系統來簡化這個問題。此外，GFS 採取大量的不可靠組件，所以容錯將是我們設計的中心問題。

GFS 十分接近 NASD 架構，NASD 架構是基於網路磁碟的，GFS 使用了一般的機器作為塊伺服器，與 NASD 協議類型相同。但是與 NASD 不同的是，我們的塊伺服器使用了惰性分配固定大小塊的方式，而不是可變大小的塊。此外，GFS 實現了在生產環境中所需的一些功能，如重新負載均衡、複製和恢復等。

不像 Minnesota』s GFS 和 NASD，我們不會去追求改變存儲設備的模式。我們只關注由一般組件組成的複雜分散式系統所需要的日常數據的處理。

通過原子記錄追加操作實現的生產者-消費者隊列解決了一個與 River 中的分散式隊列類似的簡單問題。River 使用了基於記憶體的分散式隊列，必須小心的控制數據流，GFS則能夠使用被很多生產者同時追加持久化的文件。River 模型支援 m-n 的分散式隊列，但是缺少由持久化存儲提供的容錯功能，而 GFS 只能夠有效的支援 m-1 的隊列。多個消費者能夠讀取同一文件，但他們必須協調分區輸入的負載。

9. 結論

Google 文件系統展示了一個在一般硬體上支援大規模數據處理工作的核心特性。一些設計決定都是根據我們的特殊環境訂製的，但許多還是能夠用於類似規模和成本的數據處理任務。

首先，根據我們當前的和預期的應用工作量和技術環境來重新考察傳統的文件系統。觀察結果引導出一個完全不同的設計思路。我們將組件失敗看成是普通現象而非異常情況，對於向大文件進行追加（可能是並行的）和讀操作（通常是序列化的）來進行優化，以及通過擴展介面和放鬆限制來改進整個系統。

我們的系統通過持續健康、複製關鍵數據以及快速自動的恢復來提供容錯。塊複製允許我們容忍塊伺服器的錯誤。這些錯誤的頻率促進了一個新奇的在線修復機制，它定期的、透明的修復損壞的數據，並儘快對丟失的副本進行補償。此外，在磁碟或IDE子系統層上，我們使用了校驗和來探測數據是否損壞，在這種規模的磁碟數量上，這種問題十分普遍。

對於進行許多並行讀寫操作的各種任務，我們的設計提供了很高的總吞吐量。我們通過將控制流和數據流分開來實現這個目標，控制流直接經過 Master，數據流塊伺服器和客戶端之間傳輸。通過大的塊大小和在數據修改操作中授予主拷貝一個塊租約，能夠最小化 Master 涉及的操作，這使簡單的、中心的 Master 不會太可能成為瓶頸。我們相信我們的網路協議棧的改進可以提高從客戶端看到的寫入吞吐量的限制。

GFS 很好的滿足了我們的存儲需求，並作為存儲平台在 Google 中得到廣泛使用，無論在研究和開發，還是生產數據處理上。它是我們持續創新和攻克整個 web 範圍的難題的一個重要工具。

Tags: 分散式系統