# 6-3. The Google File System

> GFS 是為大規模分散式資料密集型應用設計的一個可擴展的分散式檔案系統，它運行在廉價伺服器上，提供容錯機制，為大量用戶端提供高效能儲存服務。

## Introduction

為滿足Google日益迅速增長的資料處理需求，設計並實踐了Google File System (GFS)。GFS和在此之前的分散式檔案系統一樣有很多相同的目標：可擴展性、可靠性和可用性。然而，GFS的設計由我們對當前和預期的應用程式工作負載和技術環境的關鍵觀察出發，反應了與一些早期檔案系統設計假設的明顯背離。重新審視傳統的選擇，並探索設計空間中截然不同的重點。

1. 組件故障是常態，而非例外。持續的監視、錯誤偵測、容錯和自動恢復必須整合至系統中。
2. 現今處理的檔案以傳統的標準來說太巨大了。必須重新審視設計假設和參數，例如 I/O 操作和區塊大小。
3. 大多數檔案是透過添加新資料而非覆蓋現有資料來改變的。有許多資料具有這樣的特徵：實務上不存在隨機寫入，一旦寫入，檔案就只能被讀取，而且通常只能按順序讀取。因應這種大檔案的存取模式，appending變成了效能最佳化和原子性保證的焦點，而在用戶端快取data blocks則失去了吸引力。
4. 共同設計應用程式和檔案系統 API，提高靈活性，有利於整理系統。

目前部署了多個用於不同的目的的GFS叢集。 最大的擁有超過 1000 個儲存節點、超過 300 TB 的磁碟空間，並且由不同電腦上的數百個用戶端持續大量存取。

## Design Overview

### Assumptions

* 系統由許多廉價的伺服器構建而成，**組件經常發生故障**。系統必須**不斷地監視自身並檢測、容忍並迅速恢復例行的組件故障**。
* 系統儲存了一些**數量不多但很大的檔案**。預期有幾百萬個檔案，每個檔案通常大小為100 MB或更大。多GB大小的檔案是常見的情況，應該要有效地管理它們。系統必須**支援小檔案，但不需要針對它們進行最佳化。**
* 工作負載主要包括兩種類型的讀取：
* **大型串流讀取(large streaming reads)**: 個別操作通常讀取數百KB，更常見的是1 MB以上。來自同一用戶端的連續操作通常會讀取檔案的一個連續區域。
* **小型隨機讀取(small random reads)**: 通常會在某個任意偏移量處讀取幾KB。考慮效能的應用通常會批量處理小型讀取，排序後穩健地進行檔案的連續讀取，而不是來回跳躍。
* 工作負載還包括許多**大型的順序寫入操作**，將資料追加到檔案中。典型的操作大小與讀取操作類似。一旦寫入，檔案很少再次修改。系統**支持在檔案中任意位置進行小型寫入操作，但不需要對其進行高效優化。**
* 系統必須**有效地實現對同一檔案進行並行追加(concurrently append)的明確語義**。我們的檔案經常用作生產者-消費者佇列(producer-consumer queues)或多路合併(many-way merging)的用途。具有**最小同步開銷的原子性**是必不可少的。
* **高持續頻寬比低延遲更重要**。我們大部分的目標應用優先考慮高速批量處理資料，而**只有少數對單個讀取或寫入的響應時間有嚴格要求。**

### Interface

- 提供熟悉的檔案系統介面，沒有實做像是POSIX這樣的標準API
- Files are organized hierarchically in directories and identified by pathnames.
- 支援常見的操作：create, delete, open, close, read 和 write
- 額外操作：
- snapshot: 以低成本創建檔案或directory tree的副本。
- record append: 讓多個用戶端並行的append資料到同個檔案，保證每個個別用戶端append的原子性。
- 對於實現多路合併結果和生產者-消費者佇列非常有用
- 許多用戶端可以同時對其進行追加，而無需額外的鎖定

### Architecture


如上圖，一個GFS叢集由一個master和多個chunkserver構成，能被多個client存取。

**Chunk**: 檔案被劃分為固定大小的chunk。
- 標識：64 bit的chunk handle，由master在chunk創建時分配，不可變且全局唯一
- 儲存：作為Linux files儲存在chunkserver的本地磁碟
- 讀寫：根據chunk handle和byte range
- 副本：每個chunk儲存在多個chunkservers上。默認儲存三個副本，但使用者可以為file namespace的不同區域指定不同的副本級別。

**Master**
* 維護整個檔案系統的metadata
* 控制系統範圍的活動：chunk租用管理、處理孤兒chunk的垃圾收集，以及chunkservers之間的chunk遷移
* 定期透過Heartbeat消息和每個chunkserver溝通，發送指令並收集狀態

**Client**
* GFS client code
* 實作檔案系統API，連結到每個應用程式
* 代表應用程式溝通，進行讀寫
* master: metadata operations
* chunkservers: 承載資料的通訊

Client 和 Chunkserver 都不會快取檔案資料，原因如下：
* Client: 大部分的應用都是對大型檔案做串流處理，或是工作集太大無法被快取。不用快取可以消除快取一致性的問題，簡化用戶端和整體系統。
* Chunkserver: chunk 儲存在本地，Linux 的 buffer cache 已經把頻繁存取的資料保存在記憶體了。

### Single Master

* 好處：簡化設計，master可以使用全局知識做出複雜的chunk放置和複製決策
* 必須：最小化涉入讀寫操作，避免成為瓶頸
* Client 詢問 Master 它應該和哪個 Chunkserver 聯繫，將這個聯繫資訊快取保留一陣子，後續直接對 Chunkserver

### Chunk Size

**採取大的 chunk size**

Chunk大小是設計的關鍵參數之一。我們選擇了64 MB，比典型的檔案系統塊大得多。每個chunk副本都存儲為Chunkserver上的plain Linux files，並根據需要進行擴展。Lazy space allocation避免了因internal fragmentation浪費空間，解決大chunk大小的最大問題。

**優點**
1. 減少Client和Master交互的次數，因為對同一個chunk的讀寫只需要向Master發送一次初始請求，獲取chunk位置訊息
- 這很重要，因為應用程式大多是對大檔案進行順序讀寫
- 對於小型隨機讀取，Client也可以快取所有chunk的位置訊息，處理多TB的工作集
2. Client更可能對給定的chunk做很多操作，因此可以通過在較長時間內保持與Chunkserver的持久TCP連線來減少網絡開銷
3. 減少了Master儲存的Metadata大小，讓其能被保留在記憶體，帶來下一節討論到的優點

**缺點**：小檔案的熱點問題
一個由少量chunk組成的小檔案，如果許多Client訪問同一個檔案，儲存這些chunk的Chunkservers可能會成為熱點。在實務中，熱點並不是主要問題，因為我們的應用程式主要是順序讀取大型的多chunk檔案。

然而，在GFS首次被批處理佇列系統(batch-queue system)使用時，確實出現了熱點問題：一個可執行檔被作為單一chunk檔案寫入GFS，然後同時在數百台機器上啟動。儲存此可執行檔的少數chunkservers被數百個同時請求壓垮。

我們通過將此類可執行檔以更高的replication factor儲存，並通過使批處理佇列系統分階段應用程式啟動時間來解決了這個問題。

潛在的長期解決方案是在這種情況下允許Client從其他Client讀取資料。

### Metadata

Master 主要儲存三種 metadata，都存在記憶體。

1. file and chunk namespaces
2. the mapping from files to chunks

為保證以上兩者的持久性，會將變更操作記錄到Master本地磁盤上的operation log，並複製到遠端機器上。

3. the location of each chunk's replicas

則不會永久保存，Master在以下時機向每個chunkserver詢問chunk的資訊：
- Master啟動時
- 每次chunkserver加入叢集時

#### In-Memory Data Structures

- 儲存在記憶體，操作速度快，便於定期掃描。定期掃描用於chunk垃圾收集、在chunkserver故障時重新複製，及chunk migration以平衡chunkserver的負載跟磁碟空間使用率。
- 潛在問題是chunk的數量以及整個系統的容量受限於Master的記憶體大小，但不嚴重
- 為每個64 MB的chunk維護不到64字節的metadata，大部分的chunk是滿的
- 對於更大的檔案系統，增加Master記憶體的成本微不足道

#### Chunk Locations

Master**不會持久記錄**哪些chunkserver擁有特定chunk的副本。

- 在啟動時向chunkserver請求訊息
- 透過定期的HeartBeat消息控制所有的chunk placement並監控chunkserver的狀態

好處：消除在chunkserver加入和離開叢集、更改名稱、故障、重啟等情況下，Master和chunkserver同步的問題。

#### Operation Log

操作日誌包含對關鍵metadata變更的歷史記錄，是GFS的核心。

- metadata的唯一持久記錄
- 定義並行操作順序的邏輯時間線

→ 在多個遠端機器上複製，並只在本地和遠端的磁碟上的記錄完全刷新後才回應用戶端的操作。Master在刷新之前會將多個日誌記錄進行批處理，降低刷新和複製對整個系統吞吐量的影響。

Checkpoint: compact B-tree like form

- 直接map到記憶體
- 用於namespace lookup，不需要額外的parsing

減少replay操作日誌的時間，加速恢復，改善可用性。

創建新的checkpoint需要時間，但不應影響傳入Master的改變記錄
- 切換到新的日誌檔案並在單獨的thread創建新的checkpoint
- 結束後寫到本地和遠端的磁碟

### Consistency Model

Relaxed consistency model

#### Guarantees by GFS

File namespace的變更是原子性的，由Master處理
- namespace locking 保證原子性和正確性
- operation log 定義全局的順序

- *consistent*: 不論從哪個副本讀取，所有用戶端都看到同樣的資料
- *defined*: consistent 且用戶端完整地看到所有變更寫的內容

在一連串成功的變更後，GFS保證被變更的file region會是defined，包含最後的變更寫入的資料。
- 在所有副本上以相同順序對chunk進行變異
- 使用chunk版本號，檢測任何因其chunkserver關閉而錯過變異而變得過時的副本

用戶端因為有快取chunk location，可能會讀到過時的副本，但這個窗口會被快取的timeout和下次打開檔案時bound住。大多數檔案都是append-only的，過時的副本打開通常是提前結束的chunk，只要用戶端向Master聯繫就能拿到新的。

組件故障問題
- GFS用Master和所有Chunkserver定期的handshakes識別哪些Chunkserver故障了
- 所有Chunkserver用checksum偵測資料毀損
遇到問題時，盡快從valid的副本恢復

只有在幾分鐘內所有副本都丟失，GFS來不及反應的情況，chunk才會丟失。即使如此，它只是unavailable而非corrupted。

#### Implications for Applications

GFS應用可以透過一些簡單的技術來適應relaxed consistency model
- 依賴append而非overwrite
- checkpointing
- 編寫自我驗證、自我識別的記錄

## System Interactions

解釋Client、Master和Chunkservers如何互動來做data mutations、atomic record append及snapshot。

### Leases and Mutation Order

- **Lease**: 維護副本間一致的mutation order。
- 初始timeout為60秒，Primary可無限期的向Master請求並（通常會）獲得延期，租約的延期和授予都和HeartBeat messages一起。
- Master可能在到期前撤銷租約，例如Master想禁止某個重新命名的檔案被更改時。
- 即使Master和Primary失去通訊，也可以在到期後授予給另一個副本。
- **Primary**: Master授予租約的副本。給chunk的變更選擇一個serial order，所有副本follow這個order。


1. **Client向Master詢問chunk位置**
- 哪個Chunkserver擁有chunk的當前租約以及其他副本的位置
- 如果沒有任何人擁有租約，Master會選擇一個副本授予租約
2. **Master回覆**
- 主要副本的identity及其他(secondary)副本的位置
- Client快取這些資料以供未來的變異使用，在主要副本變得無法訪問或不再擁有租約時才需要再次聯繫Master。
3. **Client將資料推送到所有副本**
- 可以用任何順序推送
- 每個Chunkserver將資料儲存在內部的LRU buffer，直到資料被使用或被淘汰
- 透過將資料流與控制流解耦，可以根據網絡拓撲排程昂貴的資料流，而不考慮哪個Chunkserver是主要副本
4. 一旦所有副本確認接收了資料，**Client向主要副本發送寫入請求**
- identify之前推送給所有副本的資料
- 主要副本為所有收到的變更分配連續的序列號，提供必要的serialization
- 按照序列號的順序進行變更
5. **主要副本將寫入請求轉發給所有次要副本**
- 每個次要副本按照主要副本分配的相同序列號順序進行變更
6. **所有次要副本向主要副本回覆完成操作**
7. **主要副本回覆Client**
- 報告任何副本遇到的錯誤
- 在錯誤情況下
- 寫入可能已在主要副本和一個任意的次要副本子集上成功執行（如果在主要副本上失敗，它將不會被分配序列號並轉發）
- Client請求被認為失敗，修改的區域保持不一致狀態
- 我們的Client代碼通過重試失敗的變異來處理此類錯誤，重複幾次步驟3到7，然後退回到寫入的開始重試

如果應用程式的寫入量很大或跨越了chunk邊界，GFS Client code會將其分解成多個寫入操作。

### Data Flow

- 將資料流與控制流分開，以有效利用網路
- 為了充分利用每台機器的網路頻寬，資料沿著一條Chunkserver鏈線性推送
- 為了盡量避免網路瓶頸和高延遲鏈路，每台機器將資料轉發到網路拓撲中距離**最近**且尚未接收該資料的機器
- 透過在TCP連線上進行pipelined資料傳輸來最小化延遲
- 一旦Chunkserver接收到一些資料，就立刻開始轉發
- 使用具有全雙工連接的交換式網路，立即發送資料不會降低接收速率

### Atomic Record Appends

- 傳統寫入：指定資料寫入的偏移量，對同一區域的並行寫入操作無法進行序列化
- Record Append：僅指定要追加的資料

GFS會把資料至少一次原子地（作為一個連續的字節序列）append到檔案，並返回該offset給Client。

- Client將資料推送到檔案的最後一個chunk的所有副本，然後向主要副本發送請求
- 主要副本檢查將記錄追加到當前chunk是否會導致chunk超過最大大小
- （少見）是，將chunk填充到最大大小，告訴次要副本也這樣做，然後向Client回覆指示應該在下一個chunk上重試該操作。（為了保持最壞情況下的fragmentation在可接受範圍內，記錄追加的大小限制為最大chunk大小的四分之一）
- （常見）否，主要副本將資料追加到副本，告訴次要副本在確切的offset上寫入資料，最後向Client回覆成功。

如果在任何副本上記錄追加操作失敗，Client會重試。

GFS不保證所有副本的bytewise identical，僅保證資料至少被原子地寫入一次。操作的資料必須在某個chunk的所有副本上的相同offset上被寫入，才能回報success。

成功的Record Append操作寫入資料的區域是defined的（因此是一致的），而中間區域是不一致的（因此是undefined），而我們的應用應能處理不一致的區域，見[2.7.2](#Implications-for-Applications)。

### Snapshot

- 作用：在幾乎瞬間將file或directory tree (the "source")複製，同時最大程度地減少中斷正在進行的變更操作。
- 用途：快速創建巨大資料集的branch副本，或對當前狀態進行checkpoint。

像 AFS 一樣，使用標準的寫時複製（copy-on-write）技術來實現快照
- 當Master收到快照請求時，會**先撤銷檔案中要進行快照的chunk上的任何未完成的租約**，確保對這些chunk的任何後續寫入都需要與Master互動以查找租約持有者，使Master有機會先創建chunk的新副本。
- 在租約被撤銷或過期後，Master將操作記錄到磁盤上，然後透過複製源檔案或directory tree的metadata來將此日誌記錄應用於其記憶體狀態。新創建的快照檔案指向與源檔案相同的chunk。

## Master Operation

Master執行所有namespace操作，並管理系統中的chunk副本：做出放置決策、建立新的chunk和副本，協調系統範圍的活動，確保chunk的完全複製、平衡chunkservers負載，並回收未使用的空間。

### Namespace Management and Locking

GFS 在邏輯上將namespace表示為將完整路徑名map到metadata的查找表。通過前綴壓縮，該表可以在記憶體中有效地表示。namespace tree中的每個節點（絕對檔案名或絕對目錄名）都有一個read-write lock。

每個操作都在目錄名上獲取read lock，並在檔案名上獲取write lock。

### Replica Placement

兩大目標：
- 最大化資料可靠性和可用性
- 最大化網路頻寬的使用率

副本不僅要分佈在**不同的機器**上，還需要分佈在**不同的機架**上，以確保即使某個機架出現故障，資料仍然可用，並且讀取流量可以利用多個機架的總頻寬。儘管這意味著寫入流量需要跨機架傳輸，但這是一個可以接受的權衡。

### Creation, Re-replication, Rebalancing

**創建 Creation**

當Master創建一個chunk時，選擇在哪裡放置最初的空白副本的考慮因素：
- 放在磁碟使用率低於平均值的chunkservers，平衡使用率
- 限制每個chunkservers上的近期創建數量，因為創建本身開銷很小，但是通常伴隨著大量的寫入
- 希望將chunk的副本分佈在不同的機架上

**再複製 Re-replication**

可用的副本數量低於設定目標時的原因：
- chunkserver不可用
- 副本損壞
- 磁碟錯誤
- 目標增加

這時，Master會立即再複製該chunk。

需要再複製的 chunk 會依據以下因素優先處理：
- 與目標副本數的差距
- 屬於活躍檔案(live files)
- 影響Client progress

Master 會指示 chunkserver 從有效副本中直接複製資料，複製的考量和創建類似。

**再平衡 Re-balancing**

- Master定期重新平衡副本，檢查當前副本分佈，並移動副本以最佳化磁碟空間和負載平衡。
- 過程中，新chunkserver會逐漸填滿，而非瞬間被大量新chunks及寫入流量淹沒。
- 新副本的放置標準與前述相似，並優先移除那些位於磁碟空間低於平均水準的 chunkservers 上的副本，以均衡磁碟空間使用。

### Garbage Collection

檔案被刪除後，GFS不會立即回收可用的物理儲存空間，而是定期對檔案和和chunk兩個級別進行垃圾收集。

#### Mechanism

當應用程式刪除檔案時：
- Master立即記錄刪除操作，但不會立即回收資源
- 將檔案重命名為包含刪除時間戳的隱藏名稱
- 在此期間，檔案仍可以通過新的特殊名稱進行讀取，並且可以通過將其重新命名回正常狀態來還原

定期掃描時：刪除存在超過三天（可調整）的隱藏檔案
- Master找出孤兒chunk，刪除chunk的Metadata
- HeartBeat消息中，Master回覆哪些chunk不再存在於Master的Metadata中，Chunkservers 可以自由地刪除這些 chunks 的副本

#### Discussion

雖然分散式的垃圾收集很困難，但我們可以

- identify all references to chunks
- easily identify all the chunk replicas

在這個情況下，任何Master不知道的replica都是垃圾。

**優點**：
- 統一且可靠的將所有未知的副本回收
- 將垃圾收集合併到Master的後台活動（對namespace的定期掃描，以及和chunkserver的handshakes）
- 批量進行，且成本是分攤的
- 只在Master相對有空時執行，可以更迅速地回應需要及時處理的Client請求
- 延遲回收儲存空間提供了安全網，防止意外且不可逆的刪除

**缺點**：阻礙使用者在儲存空間不足時做細微調整的努力，但可以通過加快存儲回收和允許不同的回收策略來解決

### Stale Replica Detection

使用 *chunk version number* 來區分最新和過期的副本。

- Master在授予新的chunk租約時更新版本號，並通知所有最新的副本
- Master和最新的副本都記錄新版本號（在任何Client被通知之前完成）
- 當Chunkservers重新啟動並報告其持有的chunk及版本號時，Master會檢測並刪除過期的副本
- Master在定期的垃圾收集中刪除過期的副本
- Master在通知Client持有租約的Chunkservers或進行chunk複製操作時，會包括chunk的版本號，這種機制確保Client始終訪問最新的資料。

## Fault Tolerance and Diagnosis

組件的品質和數量使得這些問題更成為常態而非例外，設計系統時最大挑戰之一是處理頻繁的組件故障，這節討論如何應對這些挑戰。

### High Availability

透過兩種簡單而有效的策略保持整個系統高度可用：快速恢復和複製。

#### Fast Recovery

- Master和Chunkserver被設計為無論如何終止，都可以在幾秒鐘內恢復其狀態並啟動
- 不區分正常終止和異常終止，伺服器通常只是透過killing process來關閉
- 用戶端和其他伺服器會在其未完成的請求超時後經歷輕微的中斷，然後重新連接到重新啟動的伺服器並重試

#### Chunk Replication

- 每個chunk在不同機架上的多個chunkserver上進行複製，使用者可以為檔案namespace的不同部分指定不同的複製級別，默認為三個
- Master根據需要複製現存的副本，以在Chunkserver離線或透過校驗和驗證檢測到損壞的副本時保持每個chunk的完全複製

複製達成的效果很好，但正在探索其他形式的cross-server redundancy，例如用於不斷增長的唯讀儲存要求的parity或erasure code。

#### Master Replication

為了可靠性，也在多台機器上複製Master狀態：
- operation log
- checkpoints

**Master故障**
幾乎可以立刻重啟。如果是機器或磁碟故障，GFS外部監控會用複製的操作日誌在其他地方啟動一個新的Master。

**影子Master**
- 在Master停機也能提供唯讀訪問，雖然稍微落後於Master，但增強了對未被活躍地修改的檔案的讀取可用性。
- 由於檔案內容是從Chunkserver讀取的，應用程式不會觀察到過時的檔案內容，短時間內可能過時的是檔案Metadata，如目錄內容或存取控制資訊。
- 透過讀取操作日誌副本保持同步，並定期與Chunkserver通訊(handshake)以監控狀態，只有在Master決定建立和刪除副本時，影子Master副本的位置更新才會依賴Master。

### Data Integrity

每個Chunkserver使用checksum來檢測和處理資料損壞，以確保系統的資料完整性。當發現損壞時，從其他副本恢復資料。

因為前面提過不保證identical的副本，所以每個Chunkserver要能夠透過維護checksum來獨立驗證自己的副本的完整性。

**Checksum**
- 一個chunk有64 KB，有對應的32 bit checksum
- 和其他metadata一樣，保留在記憶體中，並透過日誌持久保存
- 為什麼有用？
- 在向請求者傳回任何資料前，Chunkserver會驗證與讀取範圍重疊的資料區塊的checksum，因此Chunkserver不會將損壞傳播給其他機器
- 損壞時，會回覆請求者錯誤，並向Master報告不符的情況
- 請求者將從其他副本中讀取
- Master從另一個副本中複製該區塊
- 在有效的新副本就位後，Master會指示報告不符的Chunkserver刪除其副本
- 對讀取效能的影響很小，原因：
- 大多數讀取至少跨越幾個區塊，因此只需要讀取和校驗相對較少的額外資料進行驗證
- GFS 用戶端程式碼會嘗試在校驗和區塊邊界對齊讀取，從而進一步減少此開銷
- 在Chunkserver的校驗和尋找和比較不需要任何 I/O，校驗和計算通常會與 I/O 重疊
- 針對append寫入的校驗和計算進行了優化，只更新最後一個部分校驗和區塊
- 如果寫入覆蓋現有資料範圍，則需要驗證覆蓋範圍的首尾區塊以確保資料完整性
- Chunkserver在空閒時掃描並驗證inactive chunks，偵測損壞並建立新的未損壞副本

### Diagnostic Tools

- 診斷日誌對問題隔離、調試和效能分析至關重要，成本極低
- 沒有日誌將難以理解機器之間的瞬時互動
- GFS 伺服器生成詳細的診斷日誌，記錄重要事件和所有 RPC 請求和回應
- 日誌可以隨意刪除，不影響系統正確性，但盡量保留
- RPC 日誌包括確切的請求和回應，可用於重建互動歷史和診斷問題
- 日誌也用於負載測試和效能分析，對系統效能影響極小

## Conclusions

- Google檔案系統(GFS)適合在廉價硬體上處理大規模資料工作負載
- 重新檢視傳統檔案系統假設，針對我們的工作負載和技術環境進行設計
- 將元件故障視為常態，針對大型檔案進行優化，並擴展檔案系統介面
- 系統通過持續監控、資料複製和自動恢復提供容錯能力
- 使用chunk複製和校驗機制來處理伺服器故障和資料損壞
- 分離檔案系統控制和資料傳輸，以實現高吞吐量
- 預期networking stack的改進將提升Client的寫入吞吐量
- GFS成功地滿足了我們的儲存需求，並廣泛應用於Google的研究開發和生產資料處理

## References

原文
https://static.googleusercontent.com/media/research.google.com/en//archive/gfs-sosp2003.pdf

筆記
https://paper-notes.zhjwpku.com/fs/gfs.html