GFS 閱讀筆記

這篇部落格是我閱讀著名的 GFS 論文（The Google File System）所總結的筆記以及自己一些的思考。這篇論文是一篇非常經典的論文，尤其對于想要了解分布式或者剛剛開始研究分布式的人來說，是一篇非常好的讀物，它裡面提到了許多分布式方向的基本問題，許多分布式的研究都是圍繞這些基本問題的。

分布式系統

在了解谷歌檔案系統（Google File System）之前，我們必須要了解一下有關分布式系統的一些概念。

Q1：一緻性是什麼？

在分布式檔案系統中，很重要的一部分就是資料的複制（replica），為了保證分布式檔案系統的高可用性，我們常常會把檔案在不同的機器上存儲多份，一緻性的要求就是保證這些不同機器上的複制品（replicas）能夠保持一緻。

Q2：如果隻有一個應用程式，它對檔案系統進行了一次寫操作，這個應用程式在這次寫操作之後的讀操作會觀測到什麼呢？

它會正常觀測到它剛剛寫入的資料。

Q3：如果另外多個應用程式執行的讀操作呢，它們會觀測到什麼呢？

對于弱一緻性的模型來說，這次讀操作有可能會讀取到已經過期的資料；

對于強一緻性的模型來說，讀操作讀到的始終是上一次寫入操作進行完成之後的資料。

強一緻性能保證寫入操作，但是它會影響性能（強一緻性協定複雜）

Q4：理想化的一緻性模型是怎樣的？

分布式檔案系統通過在多個機器上複制檔案來保證可用性，在理想化的一緻性模型中，在檔案系統中所進行的各種操作都要像是在一台機器上進行的操作。實作理想化一緻性模型的難點在于處理高并發問題、如何處理分布式叢集中的機器崩潰以及達到網絡的高效利用，理想化的一緻性模型還會出現裂腦問題（split-brain，如果兩個存儲着相同檔案的機器 A，B同時崩潰，其他的機器并不知道是哪一個先崩潰的，是以就不知道該用 A 恢複 B還是用 B 恢複 A）。總之，使用理想化一緻性算法會影響性能，并且它的實作非常複雜（例如：Paxos）

GFS 不是采用的理想化一緻性模型，但是它解決了機器崩潰恢複的問題以及能夠應對高并發操作同時又能相對高效地利用網絡。

GFS 是什麼？

GFS（Google File System ）是一個大規模分布式檔案系統，具有容錯的特性（機器崩潰後的處理），并且具有較高性能，能夠響應衆多的用戶端。

GFS 設計背景

• 經常會有機器崩潰（因為機器衆多，難免會有機器崩潰）
• 有些存儲的檔案比較大
• append 操作更常見（在檔案後追加，而不是 overwrite 覆寫）
• 主要包括兩種讀取 （read）操作：一種是大的順序讀取（單個檔案讀取幾百 KB 甚至是幾 MB）；另一種是小的随機讀取（在随機位置讀取幾 KB）
• 需要支援并發（例如，多個用戶端同時進行 append 操作）

GFS 所需提供操作

create（檔案建立）、delete（檔案删除）、open（打開檔案）、close（關閉檔案）、read（讀取檔案）、write（寫入檔案）、record append（追加檔案）、snapshot（快照）。

GFS 架構

GFS 的架構由一台 master 伺服器和許多台檔案伺服器（chunkserver）構成，并且有若幹用戶端（client）與之互動。

GFS 特點概述

• 檔案分塊（chunks），每塊有一個64位辨別符（chunk handle），它是在 chunk 被建立時由 master 配置設定的，每一個 chunk 會有3個備份，分别在不同的機器上。
• Master 存儲所有的 metadata，包括命名空間（namespace）、通路控制資訊（access control）、檔案與 chunk 的映射關系（mapping）以及 chunk 的存儲位置
• Master 管理 chunk 租約（lease）、chunk 遷移（如果 chunkserver 挂掉）、chunkserver 之間的通信（heartbeat，它也會向 chunkserver傳達master 的指令，chunkserver 通過 heartbeat 向 master 報告自己的狀态）
• Client 會和 master 以及 chunkserver 進行互動，client向 master 請求 metadata，然後向 chunkserver 進行讀寫操作
• client 與 chunkserver 都不會緩存檔案資料，為的是防止資料出現不一緻的狀況。但是 client 會緩存 metadata 的資訊（但是會出現一個問題，如果 metadata 過期怎麼辦呢？GFS 給出了自己的解決方案，也就是租約 lease）

單一 Master 架構

GFS 為了簡化設計，在整個系統中隻有一個 master 進行管理。Master 不提供讀寫操作，它隻會告訴 client，它所請求操作的檔案在哪個 chunkserver 上，然後 client 會根據 master 提供的資訊，與對應的 chunkserver 進行通信。

例如：以 client 要進行讀取操作為例

1. client 将應用程式請求的檔案名、大小轉化為 chunk index，然後将檔案名和 index 發送給 master
2. master 傳回檔案的 chunk handle 和所有該檔案備份的位置
3. client 将這兩個 master 發送給它的資訊緩存起來作為 value，檔案名和 chunk index 作為 key
4. client 向三個備份之一的 chunkserver 發送讀請求（選擇最近的機器），請求中包含 chunk index 和它要讀取的檔案的 Byte 範圍
5. 如果 client 緩存的資訊沒有過期（如何知道是否過期會在後面的文章進行介紹），client 就不用在與 master 進行通信了，以後可以直接與 chunkserver 進行通信

chunk 大小

GFS 中将 chunk 的大小定為 64MB，它比一般的檔案系統的塊大小要大。

這樣做的優點有：

• 減少 client 與 master 的互動
• client 可以在一個塊上執行更多的操作，通過 TCP 長連接配接減少網絡壓力
• 減小 metadata 的大小

但是這樣做也存在缺點：

• 一個 chunk 可以存更多的小檔案了，這樣的話如果有一個塊存儲了許多小檔案，client 和它進行操作的幾率大大提高，這個 chunk 的壓力會很大（然而在實際中，這個問題影響并不大）
• 在批處理系統中存在很大問題（如果在一個 chunk 上有一個可執行檔案，同時有許多 client 都要請求執行這個檔案，它的壓力會很大。解決方案是把該檔案在不同的 chunkserver 上多添加幾個備份，更長久的方案是應該允許 client 去讀取其他 client 的檔案）

metadata

GFS 的 metadata 存儲着 3 種類型的資訊：

• 檔案名以及 chunk 的名稱
• 檔案與 chunk 的映射關系
• 各個備份（replicas）的位置

Metadata 通常存儲于記憶體中，前兩種資訊有時會存于磁盤中，它們有時會作為操作記錄（operation log）備份的一部分存儲于磁盤，備份于遠端機器。

把 metadata 存儲于記憶體有許多優點，檢視 metadata 資訊時很友善，速度快，有利于 chunk 的垃圾回收（garbage collection）、再備份（re-replication）以及 chunk 遷移（為的是負載均衡）。

但是如果如果Metadata都存放于記憶體的話會不會受限于記憶體的大小呢？

實際上不會的，因為每一條 metadata 的大小非常小，namespace 資訊也很小，并且使用了字首壓縮（prefix compression）進行存儲。并且更新記憶體的花費實際上也很小。

chunk 位置

chunk 的位置資訊在 master 中不是一成不變的，master 會通過定期的 heartbeat 進行更新，這樣做能夠減小開銷，這樣做就不用 master 與 chunkserver 時刻保持同步通信（包括 chunkserver 的加入、退出、改名、當機、重新開機等）。chunkserver 上有一個 final word，它表示了哪個 chunk 在它的磁盤上，哪個 chunk 不在。

操作記錄（operation log）

operation log 中包括了 metadata 變更的曆史記錄

• 它是 metadata 的持久化記錄，備份于磁盤上
• 它表示了并發操作的時間線
• 用于 Master 恢複

一緻性模型

GFS 采用的一緻性模型并不是強一緻性模型，這是在考慮了各種問題後權衡的結果。

GFS 是如何保證一緻性的？

有關檔案命名空間的操作都是原子的（由 namespace lock 保證）

我們先來介紹一下 GFS 保證一緻性的前提和一些概念：

• 如果所有用戶端不論從哪一個備份中讀取同一個檔案，得到的結果都是相同的，那麼我們就說這個檔案空間是一緻的（consistent）
• defined：如果一個檔案區域在經過一系列操作之後依舊是一緻的，并且用戶端完全知曉對它所做的所有操作，我們就稱它為『defined』
• 一個操作如果沒有被其他并發的寫操作影響，那麼這個被操作的檔案區域是 defined 的
• 成功的并發操作也會導緻檔案區域 undefined，但是一定是一緻的（consistent）（用戶端有可能隻看到了最終一緻的結果，但是它并不知道過程）
• 失敗的并發操作會導緻檔案區域 undefined，是以一定也是不一緻的（inconsistent）
• GFS 并不需要是因為什麼導緻的 undefined（不區分是哪種 undefined），它隻需要知道這個區域是 undefined 還是 defined 就可以

造成資料改變的操作可能是寫入（write）或者追加（record append）：

• write：往應用程式指定的 offset 進行寫入
• record append：往并發操作進行過的 offset 處進行寫入，這個 offset 是由 GFS 決定的（至于如何決定的後面會有介紹），這個 offset 會作為 defined 區域的起始位置發送給 client。
• “regular” append：對應于 record append 的一個概念，普通的 append 操作通常 offset 指的是檔案的末尾，但是在分布式的環境中，offset 就沒有這麼簡單了

重要問題

1. GFS 通過在所有的備份（replicas）上應用順序相同的操作來保證一個檔案區域的 defined（具體細節後面會讨論）
2. GFS 會使用 chunk version（版本号）來檢測 replicas 是否過期，過期的 replicas 既不會被讀取也不會被寫入
3. GFS 通過握手（handshakes）來檢測已經當機的 chunkserver
4. GFS 會通過校驗和（checksuming）來檢測檔案的完整性

系統間的互動

這一部分我們來談談系統中各個部分之間的互動（master 和 chunkserver、client 和 master、chunkserver 等），GFS 設計的目标是盡可能地讓 master 更少的涉及到各種操作中。

租約（lease）和修改的順序（mutation order）

Mutation（修改）：mutation 指的是改變了 chunk 的内容或者 metadata，每一次 mutation 都應該作用于所有的備份

GFS 使用租約機制（lease）來保障 mutation 的一緻性：多個備份中的一個持有 lease，這個備份被稱為 primary replica（其餘的備份為 secondary replicas），GFS 會把所有的 mutation 都序列化（串行化），讓 primary 直行，secondary 也按相同順序執行，primary 是由 master 選出來的。一個 lease 通常60秒會逾時。

現在我們以寫操作的資料流程來說明租約機制是如何進行的：

1. client 向 master 請求持有 lease 的 chunk（primary replica）位置和其他 replicas 的位置（如果沒有 chunk 持有 lease，那麼 master 會授予其中一個 replica 一個 lease）
2. master 傳回 primary 的資訊和其他 replicas 的位置，然後 client 将這些資訊緩存起來（隻有當 primary 無法通信或者該 primary replica 沒有 lease 了，client 才會向 master 再次請求）
3. client 會将資料發送到所有的 replicas，每個 chunkserver 會把資料存在 LRU 緩存中
4. 在所有的 replicas 都收到了資料之後，client 會向 primary 發送寫請求。primary 會給它所收到的所有 mutation 配置設定序列号（這些 mutation 有可能不是來自于同一個 client），它會在自己的機器上按序列号進行操作
5. primary 給 secondaries 發送寫請求，secondaries 會按相同的序列執行操作
6. secondaries 告知 primary 操作執行完畢
7. primary 向 client 應答，期間的錯誤也會發送給 client，client 錯誤處理程式（error handler）會重試失敗的 mutation

其他問題：

• 如果一次寫操作要寫的資料比較大，可能會跨越多個 chunk，GFS client 會把它分為幾次小的操作，GFS 支援的最大的操作大小是 chunk 的1/4的大小
• **但是如果像上述這麼做會出現 undefined 但是 consistent 的區域，這是為什麼呢？**GFS 的 record append 操作僅能保證資料在一個原子機關中被寫了一次，并不能保證對所有的 replicas 操作的位置都是相同的，比如每次寫入的 offset 相同，但是 chunk 有可能不一樣

資料流

GFS 對其資料流的設計目标如下：

• 要充分利用網絡帶寬
• 避免網絡瓶頸和高延遲
• 減少資料流動延遲

設計方案如下：

• 資料以鍊（chain）的形式 在 chunkserver 之間線性流動（每個機器都在用自己的全部帶寬與另外一個機器通信，而不是同時讓多個機器分享帶寬）
• 每個機器會把資料發送到離自己最近的還沒有收到資料的機器（GFS 中可以通過機器 IP 位址進行計算）
• 通過 TCP 連接配接将資料傳輸流水線化（pipelining），pipelining 之是以能夠有效果是因為 GFS 的網絡是全雙工的交換網絡

Snapshot 快照

GFS 通過 snapshot 來立即建立一個檔案或者目錄樹的備份，它可以用于備份檔案或者建立 checkpoint（用于恢複），同時 GFS 把寫時複制技術（copy-on-write）引入到了快照操作中，原理與 Linux 程序中的寫時複制基本相同。

當 master 收到 snapshot 操作請求後：

1. 廢除所有的 lease，準備 snapshot（相當于暫停了所有寫操作）
2. master 記錄所有操作，并且将記錄寫入磁盤
3. master 将源檔案和目錄樹的 metadata 進行複制，這樣之前的記錄就和目前的記憶體中所儲存的狀态對應起來了，建立的 snapshot 和源檔案指向的會是同一個 chunk

Master 職責

• 執行所有有關于 namespace 的操作
• 管理整個系統的 chunk replicas：
  • 做出 chunk replicas 的放置決定
  • 建立 chunk/replicas
  • 協調各種操作，保證 chunk 被完全複制
  • 負載均衡
  • 回收閑置空間

管理 namespace

在進行快照操作時，lease 會被廢除，無法進行寫操作，但是 GFS 希望其他 Master 操作不受影響，GFS 采取的方法是使用namespace 鎖。

GFS 的namespace 是一個查找表（lookup table），并且采用了字首壓縮的方式存儲在記憶體中，它是一個樹結構，namespace 樹中的每一個節點（檔案名或者目錄名）都有一個讀/寫鎖。

在 Master 對檔案或者目錄進行操作之前它首先需要擷取一個鎖，比如要對 /d1/d2/…/dn/leaf 進行操作，需要獲得 /d1, /d1/d2, /d1/d2/…/dn的讀鎖，需要 /d1/d2/…/dn/leaf 的讀鎖或者寫鎖（根據不同的操作，鎖也不同）

例如，當/home/user 被快照備份至/save/user 時，如果此時要建立/home/user/foo 會發生什麼呢？

快照操作獲得了/home, /save 的讀鎖和/home/user, /save/user 的寫鎖。建立/home/user/foo需要/home, /home/user的讀鎖和/home/user/foo 的寫鎖。因為兩個操作在 /home/user的鎖上産生了沖突，是以操作會依次執行，在完成 snapshot 操作之後，釋放了/home/user 的寫鎖， /home/user/foo才會被建立。

放置 replicas

如何安置replicas 的目标是：

• 最大化資料可靠性和可用性
• 最大化網絡帶寬的利用

這裡的最大化不僅僅是機器間的問題，還要考慮機架間的問題

在以下3種情況下，Master 會進行建立 replicas 的操作：

• 建立了新的 chunk
• 需要重新備份
• 負載均衡

如何選擇将 replicas放置到哪台機器上呢？

1. 優先選擇磁盤使用率低的 chunkserver
2. GFS 會限制每個 chunkserver『最近』建立的次數。換句話說，如果一個 chunkserver 近期建立 replicas 的操作比較頻繁，就不會優先選擇它（因為建立就意味着以後會進行讀取，為了防止突然間大量的讀取出現在同一台機器上）
3. 保證可用性，盡可能跨機架進行建立操作

當可用的備份低于要求時（GFS 要求為3份），master 會對 chunk 進行重新備份，在以下情況有可能需要重新備份：

• chunkserver 不可用了
• 備份損壞了
• 硬碟挂掉了
• 所要求的最低備份數量提高了

當有多個 chunk 需要備份時，GFS 如何決定先備份哪個呢？政策如下：

• 優先選擇可用備份少的
• 優先備份最近沒有 delete 檔案的
• 優先備份阻塞了 client 操作的

當 master 決定了備份哪個之後，會把目前可用的 chunk 直接克隆到目标位置（遵循replicas 放置規則）

垃圾回收

檔案 delete 之後，GFS 并不會立即對空間進行回收，而是等待垃圾回收機制會空間進行釋放。

當檔案被删除之後，Master 會想其他操作一樣，把删除操作記錄下來，但是不進行空間的回收，而是将這塊空間命名為 hidden（并且包含被删除時的時間戳），Master 會定期進行掃描，把隐藏了一定時間的檔案空間進行回收（這個時間是可以進行配置的），在此期間可以對這塊空間的檔案進行恢複（直接通過重命名回原來的名稱就可以）。

除此之外，垃圾回收機制還會掃描孤兒 chunk（所有的檔案都沒有用到的非空 chunk），然後對這塊 chunk 的 metadata 進行清除。具體的做法是，在 master 于 chunkserver 的 heartbeat 資訊中會攜帶關于 chunk 的資訊，master 會把 metadata 中不存在的 chunk 發送給 chunkserver，chunkserver 會把它擁有的 chunk 發送給 master。

過期 replica 檢測

chunkserver 當機或者是 mutation 的丢失會導緻 replica 的過期，GFS 是如何對 replicas 進行檢測，判斷它們是否是最新的呢？

GFS 對于每一個 chunk 都會有一個版本号，這個版本号由 master 進行管理，通過版本号可以對過期的 replica 進行甄别。當 master 授予 lease 的時候，會增加版本号并且通知所有未過期的 replicas，master 和 replicas 都會記錄下最新的版本号（這些操作需要在用戶端進行寫入操作之前完成）。如果這時，有一個 replica 不可用了，它的版本号就不會再增加了，在 chunkserver 重新開機或者重新向 master報告它的版本号時，master 就會知道這個 replica 已經過期了，并且會在垃圾回收時将它進行回收。如果 master 的版本号落後了呢，它會更新自己的版本号。

本文的版權歸作者 羅遠航 所有，采用 Attribution-NonCommercial 3.0 License。任何人可以進行轉載、分享，但不可在未經允許的情況下用于商業用途；轉載請注明出處。感謝配合！