# The Google File System ## 1. INTRODUCTION Google File System(GFS) * 滿足 Google 日益增長的數據處理需求 * GFS 與以往的分佈式 File System，相同的目標，performance、scalability、reliability、availability ## 2. DESIGN OVERVIEW ### 2.1 Assumptions File System 觀察 * 共同設計 application 和 file system API 有利於提高整體系統的靈活性 * 例如 * 我們放寬了 GFS 的一致性模型，以極大地簡化文件系統，而不對應用程序施加沉重的負擔 * 引入了一種原子附加操作，使多個客戶端可以同時附加到文件，而無需額外的同步 * component 故障是常態而非例外 * 由數百甚至數千台由廉價商品零件構成的 storage 機器組成，並由相當數量的 client 訪問 * 系統中必須內置持續監控、錯誤檢測、故障容忍和自動恢復 * 文件的大小遠超傳統標準 * 每個文件通常包含許多 application object，如網頁文檔 * 預期有幾百萬個文件，每個文件通常大小為 100MB 或更大 * 多GB的文件很常見，應該高效管理 * 必須支持小文件，但不需要對其進行優化 * workload: 文件 I/O * 主要由兩種類型的 read 組成 * 大範圍的 streaming read: 單次操作通常讀取數百 KB 的數據，更常見的是 1MB 或更多，來自同一客戶端的連續操作通常會讀取文件的連續區域。 * 小範圍的 random read: 通常會在某個任意偏移量讀取幾 KB 的數據(注重性能的應用程序通常會批量處理並排序小範圍的讀取，以穩步地讀取文件，而不是來回跳轉) * 大範圍的順序 write * 大多數文件通過附加新數據來修改，而不是覆蓋現有數據 * 巨型文件的訪問模式下，附加操作成為性能優化和原子性保證的重點，而在客戶端 cache data block 的吸引力則下降 * 文件中的隨機寫入幾乎不存在，文件一旦寫入，通常很少再被修改 * 典型的操作大小與 read 類似 * 支持在文件中的任意位置進行小範圍的寫入，但不需要高效 * 系統必須高效實現多個客戶端同時附加到同一文件的明確 semantics * 原子性操作和最小的同步成本是必要的 * 高且持續 bandwidth 比低延遲更重要 * 大多數目標 application 重視以高速度批量處理數據，而很少有 application 對單次讀取或寫入操作的響應時間有嚴格要求 ### 2.2 Interface >GFS interface = API 文件在目錄中以層次結構組織，並通過路徑名標識 * 創建、刪除、打開、關閉、讀取、寫入文件 * snapshot: 以低成本創建文件或目錄樹的副本 * record append: 允許多個客戶端同時將數據追加到同一文件，並保證每個客戶端追加操作的原子性，許多客戶端可以同時追加而不需要額外的鎖定 ### 2.3 Architecture ![image](https://hackmd.io/_uploads/B1NDgY3mR.png) 一個 GFS cluster * 一個 master * 多個 chunkserver，並由多個客戶端訪問 * 每個 node 通常是一台運行 user-level server process 的普通 Linux 機器 chunkserver * 文件被分成固定大小的 chunk * 每個 chunk 由 master 在創建時分配的一個不可變且全局唯一的 64 bit chunk handle * chunkserver 將 chunk 以 Linux 文件存儲在本地 disk 上，並根據 chunk handle 和 byte 範圍讀取或寫入 chunk 數據 * 為了可靠性，每個 chunk 會在多個 chunkserver 上進行複製 * 默認情況下存儲三個副本，但用戶可以為文件命名空間(文件的儲存結構)的不同區域指定不同的複製級別 master * 維護所有的文件系統 metadata * 包括命名空間、訪問控制信息、文件到 chunk 的 map、chunk 的當前位置 * 控制系統範圍的活動，如 chunk 租約管理、孤立 chunk 的垃圾回收、chunkserver 之間的 chunk 遷移 * 定期通過 HeartBeat 與每個 chunkserver 通信，以給予指示並收集其狀態 client * 鏈接到每個 application * 實現文件系統 API * 與 master 和 chunkserver 通信，以代表 application 讀取或寫入數據 * client 與 master 進行 metadata 操作，但所有涉及數據的通信直接與 chunkserver 進行 cache file data * 客戶端 * 不 cache 文件數據 * 大多數 application 都會 stream 處理大型文件或過大而無法 cache 的工作集 * 不進行緩存簡化了客戶端和整個系統，消除了 cache 一致性問題 * cache metadata * chunkserver * 不需要 cache 文件數據，因為 chunk 是作為本地文件存儲，因此 Linux 的 buffer cache 已經將經常訪問的數據保存在 memory 中 ### 2.4 Single Master :::info * master 能夠利用全局資訊做出複雜的 chunk 放置和複製決策 * 必須盡量減少 master 在讀取和寫入中的參與，以避免成為瓶頸 * 客戶端從不通過 master 讀取和寫入文件數據，but 客戶端會詢問 master 應該聯繫哪些chunkserver * 客戶端將這些信息緩存一段時間，並直接與 chunkserver 進行後續操作 ::: client 與系統的交互 1. 使用固定的 chunk 大小，客戶端將 application 指定的 file name 和 byte 偏移量轉換為文件中的 chunk index 2. 客戶端向 master 發送包含 file name 和 chunk index 的請求，master 回覆對應的 chunk handle 和 chunk copys location 3. 客戶端將這些信息使用 file name 和 chunk index 作為鍵進行 cache 4. 客戶端向其中一個副本發送請求，通常是最接近的那個。請求中指定了 chunk handle 和 byte range * 對同一 chunk 的進一步讀取操作不需要再與 master 交互，直到 cache 的信息過期或文件被重新打開 * 客戶端通常在同一請求中請求多個 chunk，master 還可以包含請求的那些 chunk 之後的 chunk 信息。避免了多次未來的 客戶端-master 交互 ### 2.5 Chunk Size ::: info GFS 的 chuck size 遠大於典型文件系統的 block 大小 * 每個 chuck 副本作為普通的 Linux 文件存儲在 chunkserver 上，僅在需要時才擴展 * Lazy 空間分配避免了由於 internal fragmentation 導致的空間浪費 ::: Large chunk size * 優點 * 減少了 client 與 master 交互的需求 * 減少 workload * 讀取和寫入大型文件: application 主要照順序，對同一 chunk 的讀取和寫入僅需要一次初始請求來獲取 chunk 位置信息，所以單一 chunk 能代表的資訊越多越好 * 小範圍的隨機讀取: 客戶端可以輕鬆地緩存多TB工作集的所有 chunk 位置信息，這樣能使用到的範圍越多 * 客戶端更有可能對給定的 chunk 執行多次操作，它可以通過在較長時間內保持與chunkserver 的持久 TCP 連接來減少網路開銷 * 減少了存儲在 master 上的 metadata 的大小，可以將 metadata 保存在 memory 中 * 缺點 * 如果許多客戶端訪問相同的文件，存儲這些 chunk 的 chunkserver 可能成為熱點 * Ex: batch-queue system: 一個可執行文件被寫入 GFS 作為 chunk 文件，然後在數百台機器上同時啟動，存儲這個可執行文件的少數 chunkserver 被數百個同時請求所超載 * 通過以更高的複製因子存儲這些可執行文件，並讓 batch-queue system 錯開 application 啟動時間來解決這個問題 * 允許客戶端在這種情況下從其他客戶端讀取數據 ### 2.6 Metadata * 三種類型的 metadata：file 和 chunk 的 namespace、file 到 chunk 的 map 、每個 chuck 副本的位置 * 所有的 metadata 都保存在 master 的 memory 中 * operation log * 存儲在 master 的本地 disk 上，並在遠程機器上進行複製 * 允許簡單、可靠地更新 master 狀態，並在 master 崩潰時不會危害到一致性 * namespace 和 map 也通過將變更記錄到 operation log 中來保持持久性 #### 2.6.1 In-Memory Data Structures 優點 * master 的操作速度非常快 * master 可以輕鬆高效在後台定期掃描其整個狀態，實現 chunk的垃圾回收、在 chunkserver 故障時進行重新複製、在 chunk 之間進行 chunk 遷移以平衡負載和 disk 空間使用 這種僅 memory 的一個潛在問題是，系統的容量和 chunk 的數量受 master memory 大小的限制 * 在實踐中並不是一個嚴重的限制，因為 metadata 在相對於 chunk 來說小很多 * 如果需要支持更大的文件系統，增加 master memory 的成本相比於我們通過將 metadata 存儲在 memory 中獲得的簡單性、可靠性、性能和靈活性而言，是一個很小的代價 #### 2.6.2 Chunk Locations master 不會持久化存儲 chunk 位置信息 1. master 會在 master 啟動時輪詢每個 chunkserver 關於其 chunk 的信息 2. 此後，會定期的 heartbeat 消息控制所有的 chunk 放置並監控 chunkserver 的狀態，master 就可以保持最新狀態 > heartbeat好處 > 1. 消除了在 chunkserver 加入和離開集群、改變名稱、故障、重啟等情況下如何保持 master 和 chunkserver 同步的問題 > 2. chunkserver 對其自身 disk 上有哪些 chunk 擁有最終決定權，試圖在 master 維護這些信息的一致性是沒有意義的，因為 chunkserver 上的錯誤可能導致 chunk自發消失或可能重命名 chunkserver #### 2.6.3 Operation Log * 包含關鍵 metadata 變更的歷史記錄 * GFS 的核心: * 唯一的持久性 metadata 記錄 * 定義平行操作的順序邏輯時間線(文件和 chunk 以及它們的版本都由創建時的邏輯時間唯一且永遠標識) * 可靠存儲 * 在 metadata 變更被持久化之前不讓變更對客戶端可見 * 在多台遠程機器上進行複製，並且僅在將需求的 log 刷新到本地和遠程 disk 後才響應客戶端操作 * master 在刷新之前將多個 log 批處理在一起，從而減少刷新和複製對整體系統吞吐量的影響 * checkpoint * master 通過重放 log 來恢復其文件系統狀態，為了最小化啟動時間，必須保持 log 小 * 當 log 增長到一定大小時，master 會對其狀態進行 checkpoint，以便通過從本地 disk 加載最新的檢查點並僅重放之後的有限數量的 log 來恢復 * checkpoint 是一種緊湊的 B tree 形式，包括切換之前的所有變更，可以直接映射到 memory 中，用於命名空間查詢而無需額外解析，加快恢復速度並提高可用性 * 創建 checkpoint 需要一段時間，master 可以在不延遲處理資訊的情況下創建新 checkpoint * master 切換到一個新的 log，並在一個單獨的 thread 中創建新的 checkpoint，完成後將其寫入本地和遠程 disk * 在創建 checkpoint 過程中發生的故障不會影響正確性，因為恢復代碼會檢測並跳過不完整的 checkpoint ### 2.7 Consistency Model GFS 具有一種放寬的一致性模型，這種模型支持高度分佈式的應用程序，但仍然相對簡單且高效實現 #### 2.7.1 Guarantees by GFS 文件命名空間的變更是原子的，由 master 處理 ![image](https://hackmd.io/_uploads/ryOLnnqE0.png) 數據變更後的文件區域狀態取決於變更的類型、是否成功、是否存在並發變更 * defined: 一個文件數據變更後的區域是一致的，並且客戶端看到的是變更所寫入的完整數據 * 當變更在沒有並發寫入的情況下成功時，受影響的區域是 defined：所有客戶端將總是看到變更所寫入的數據 * 並發的成功變更會使區域變得 undefined 但一致：所有客戶端看到的數據是一樣的，但可能不反映任何一次變更的完整內容 * 失敗的變更會使區域變得不一致（也是 undefined）：不同客戶端可能在不同時刻看到不同的數據 GFS 確保在一系列成功的變更之後，變更的文件區域保證是 defined 的並包含最後一次變更寫入的數據，方法: * 在所有副本上以相同的順序應用變更 * 使用 chunk 版本號來檢測任何由於 chunkserver 故障而錯過變更的副本，過時的副本不會參與變更或被提供給請求 chunk 位置信息的客戶端，它們會在最早的時候被垃圾回收 違反保證的可能: * 由於客戶端緩存了 chunk 位置信息，它們可能會在信息刷新之前從過時的副本讀取 * 解決: * 緩存條目的超時和文件的下一次打開操作(會從緩存中清除該文件的所有 chunk 信息) * 大多數文件僅追加，過時的副本通常返回的是過早的 chunk 結束而不是過期的數據 * 在成功變更很久之後，component 故障可能損壞或破壞數據 * 解決: * GFS 通過 master 與所有 chunkserver 之間的定期握手來識別故障的chunkserver，並通過checksum來檢測數據損壞，一旦問題出現，數據會盡快從有效的副本中恢復 * 只有在 GFS 能夠反應之前，所有副本都丟失的情況下，chunk 才會不可逆地丟失，在這種情況下，chunk 變得不可用而不是損壞：應用程序會收到明確的錯誤而不是損壞的數據 #### 2.7.2 Implications for Applications GFS 的應用程序適應放寬的一致性模型 * 依賴追加而不是覆寫: 所有的應用程序都是通過追加而不是覆寫來修改文件 * 設置 checkpoint * 編寫自校驗自標識的記錄 使用場景: * 寫入者從頭到尾生成一個文件，在寫入所有數據後，文件原子性地將文件重命名為永久名稱 1. 追加比隨機寫入更高效且更能抵抗應用程序故障 2. 2.1 期間定期 checkpoint 記錄已成功寫入的數據量 2.2 checkpoint 允許寫入者逐步重啟，並防止讀取者處理從應用程序的角度來看仍不完整的已成功寫入的文件數據 5. checkpoint 還可以包括應用層的checksum，讀取者僅驗證和處理到最後一個 checkpoint 為止的文件區域(處於 defined 狀態) * 許多寫入者同時將數據追加到一個文件中，以獲得合併結果或作為生產者-消費者 queue 1. 記錄追加的“至少追加一次”語義保證了每個寫入者的輸出 3. 3.1每個由寫入者準備的記錄包含額外的信息，如checksum，以便驗證其有效性，讀取者可以使用這些checksum識別並丟棄額外的填充和記錄片段 3.2 如果讀取者無法容忍偶爾的重複，可以使用記錄中的唯一標識符過濾掉它們，這些唯一標識符需要用來命名相應的應用實體，如網頁文檔 ## 3. SYSTEM INTERACTIONS 設計系統的目標是將 master 在所有操作中的參與度降到最低 ### 3.1 Leases and Mutation Order >變更是一種改變 chunk 的內容或 metadata 的操作，例如寫入或追加操作，每次變更都會在該 chunk 的所有副本上執行 租約 * 在副本之間保持一致的變更順序 * 設計的目的: 將 master 的管理開銷降到最低 * 主副本 * master 向其中一個副本授予 chunk 租約 * 主副本為所有對該 chunk 的變更選擇一個序列順序，所有副本在應用變更時都遵循這個順序。 * 一個租約的初始超時為 60 秒，只要該 chunk 正在被變更，主副本可以向 master 請求並通常會獲得無限期的擴展 * 請求附加在 master 與所有 chunkserver 之間定期交換的 heartbeat 上 * master 有時可能會在租約到期之前嘗試撤銷租約，即使 master 與主副本的通信中斷，它也可以在舊租約到期後安全地將新租約授予另一個副本 ![image](https://hackmd.io/_uploads/rJ9zofhEA.png) 寫入操作的 control flow 1. 客戶端詢問 master 哪個 chunkserver 持有該 chunk 的當前租約以及其他副本的位置。如果沒有人持有租約，master 會將租約授予它選擇的一個副本 2. master 回覆主副本的身份及其他副本的位置。客戶端將此數據緩存以便未來的變更使用，只有當主副本變得無法聯繫或回覆它不再持有租約時，才需要再次聯繫 master 3. 客戶端將數據推送到所有副本(客戶端可以以任意順序進行)。每個 chunkserver 會將數據存儲在內部的 LRU 緩存中，直到數據被使用或過期 4. 一旦所有副本都確認收到數據後，客戶端向主副本發送寫入請求且標識了先前推送到所有副本的數據。主副本為它接收到的所有變更（可能來自多個客戶端）分配連續的序列號，以序列化，之後按照序列號順序將變更應用到其本地狀態 6. 主副本將寫入請求轉發給所有次要副本，每個次要副本按照主副本分配的相同序列號順序應用變更 7. 所有次要副本向主副本回覆，顯示它們已完成操作 8. 主副本回覆客戶端。在任何副本遇到的任何錯誤都會報告給客戶端，如果發生錯誤，寫入可能已在主副本和次要副本的任意子集中成功（如果在主副本上失敗，它不會被分配序列號並轉發），客戶端代碼通過重試失敗的變更來處理此類錯誤。它會在3.到7.中進行幾次嘗試，然後才重新從寫入的開始重試 >如果應用程序的寫入操作很大或跨越了 chunk 邊界，客戶端會將其拆分成多個寫入操作，可能會與其他客戶端的並發操作交錯並覆蓋。因此，共享的文件區域最終可能包含來自不同客戶端的片段，儘管所有副本都是相同的(因為各個操作在所有副本上都按相同的順序成功完成)。這使得文件區域處於一致但 undefined 的狀態 ### 3.2 Data Flow :::info 將 data flow 與 control flow 分離，以高效利用網路。雖然 control flow 從客戶端流向主副本，然後到所有次要副本，但 data 是沿著 chunkserver chain 以流水線方式線性推送。目標是充分利用每台機器的網路 bandwidth，避免網路瓶頸和高延遲鏈路，最小化推送所有數據的延遲 ::: * 數據是沿著 chunkserver 鏈線性拓樸推送，哪個害沒收到且最近就送哪個，可以避免網路瓶頸和高延遲鏈路（例如，交換機之間的鏈路通常既是瓶頸又是高延遲），可以從 IP 地址來估計距離 * 使用的是 full-duplex link 的交換網路，立即發送數據不會減少接收率。在沒有網路擁塞的情況下，將 B byte 數據傳輸到 R 副本的理想經過時間是 B/T + RL，其中 T 是網路吞吐量，L 是兩台機器之間傳輸 byte 的延遲 ### 3.3 Atomic Record Appends GFS 提供 record append * atomic append 操作 * 傳統寫入操作: 客戶端指定數據寫入的偏移量，對同一區域的並發寫入是不可序列化的，該區域最終可能包含來自多個客戶端的數據片段 * record append 操作: 客戶端只指定數據，GFS 將其原子追加到文件中的一個偏移量，並將該偏移量返回給客戶端，避免了多個寫入者同時寫入時的競爭條件 * 客戶端將數據推送到文件最後一個 chunk 的所有副本，然後將請求發送給主副本，主副本檢查是否將記錄追加到當前 chunk 會導致 chunk 超過最大大小 * 如果會，它會將 chunk 填充到最大大小，告訴次副本也這樣做，並回覆客戶端操作應在下一個 chunk 上重試 * 如果記錄符合最大大小，主副本將數據追加到其副本，告訴次副本在相同的偏移量寫入數據，最後回覆客戶端成功 * 如果任何副本的記錄追加失敗，客戶端將重試操作，因此，同一chunk的副本可能包含不同的數據，可能包括同一記錄的整體或部分重複 => GFS 不保證所有副本在 byte 上完全相，只保證數據至少作為一個原子單元被寫入一次 ### 3.4 Snapshot * 能幾乎瞬間複製文件或目錄樹，同時將正在進行的變更中斷降到最低 * 用來快速創建大型 dataset 的分支副本，或者進行可能的 commit 或 rollback 來更改之前設置當前狀態的 checkpoint * 使用 copy-on-write 來實現 snapshot 1. 當 master 接收到 snapshot 請求時，首先撤銷對即將 snapshot 的文件中 chunk 的任何未完成的租約(確保任何後續對這些 chunk 的寫入都需要與 master 交互以找到租約持有者，來創建 chunk 的新副本) 2. 在租約被撤銷或到期後，master 將操作 log 記錄到 disk 上。通過複製 source file 或 directory tree 的 metadata 將此 log 應用到其 memory 中的狀態。新創建的 snapshot 文件指向與 source file 相同的 chunk 3. 在 snapshot 操作之後 1. 客戶端第一次想要寫入 chunk C 時，它會發送請求給 master 以找到當前的租約持有者 2. master 注意到 chunk C 的引用計數大於 1 後推遲回應客戶端請求，並選擇一個新的 chunk handle C' 3. 它請求每個擁有當前 chunk C 副本的 chunkserver 創建一個新的 chunk，稱為 C'。 * 通過在與原始 chunk 相同的 chunkserver上創建新 chunk，我們確保數據可以在本地複製，而不是通過網路，請求處理與任何 chunk 的處理沒有區別 ## 4. MASTER OPERATION master 執行所有命名空間操作 + 管理整個系統中的 chunk 副本 ### 4.1 Namespace Management and Locking >許多 master 操作可能需要很長時間，允許多個操作同時進行，並使用命名空間區域上的鎖來確保適當的序列化 GFS 將其命名空間表示為一個查找表，將完整路徑名映射到 metadata，命名空間樹中的每個節點都有一個相關的讀寫鎖 * 每個 master 操作在運行之前都會獲取一組鎖 * 涉及 /d1/d2/.../dn/leaf，會獲取目錄名稱 /d1、/d1/d2、...、/d1/d2/.../dn 的讀鎖，對完整路徑名 /d1/d2/.../dn/leaf 獲取讀鎖或寫鎖 * 例子: 如何防止在 /home/user 被 snapshot 到 /save/user 的過程中創建文件 /home/user/foo * snapshot 獲取 /home 和 /save 的讀鎖 + /home/user 和 /save/user 的寫鎖 * 文件創建獲取 /home 和 /home/user 的讀鎖 + /home/user/foo 的寫鎖 * 這兩個操作將正確地被序列化，因為它們試圖在 /home/user 上獲取相互衝突的鎖 * 優點是允許在同一目錄中進行平行變更 * 例如，可以在同一目錄中同時創建多個文件：每個操作獲取目錄名稱的讀鎖和文件名稱的寫鎖 * 對目錄名稱的讀鎖防止目錄被刪除、重命名、snapshot * 對文件名稱的寫鎖序列化兩次創建同名文件的行為 * 讀寫鎖對象是 lazy 分配，並且在不再使用時被刪除 * 鎖是按照一致的總順序獲取，以防止死鎖：鎖首先按命名空間樹中的層次順序排列，然後在同一層次內按字典順序排列 ### 4.2 Replica Placement chunk 副本放置策略有兩個目的 * 最大化數據的可靠性和可用性 * 最大化網路頻寬的利用率 need 機器 + rank 分佈 chunk 副本 * chunk 的流量，尤其是讀取流量，可以利用多個 rank 的總頻寬；寫入流量必須通過多個 rank ### 4.3 Creation, Re-replication, Rebalancing :::success chunk 副本創建有三個原因：chunk 創建、再複製、重新平衡 ::: 當 master 創建一個 chunk 時，它選擇在哪裡放置最初的空副本，考慮幾個因素: * 將新副本放置在 disk 空間使用率低於平均水平的 chunkserver 上，隨著時間的推移，將使 chunkserver 之間的 disk 使用率趨於平衡 * 限制每個 chunkserver 上的最近創建數量，雖然創建本身是廉價的，但它會出現的嚴重的寫流量 * 將 chunk 的副本分佈在不同的 rank 上 當可用副本數量低於用戶指定的目標時，master 會立即再複製一個 chunk * 由於多種原因發生 * chunkserver 變得不可用 * chunkserver 報告其副本可能已損壞 * chunksercer disk 之一因錯誤被禁用 * chunkserver 複製目標增加 * 每個需要再複製的 chunk 根據多個因素進行優先排序 * 離複製目標有多遠: 例如優先處理已經丟失了兩個副本的 chunk，而不是只丟失一個副本的 chunk * 首先再複製活躍文件的 chunk，而不是最近刪除文件的 chunk * 為了將故障對運行應用程序的影響降到最低，會提高任何阻礙客戶端進度的 chunk 的優先級 * master 選擇最高優先級的 chunk，並通過指示某些 chunkserver 直接從現有有效副本複製該 chunk 數據來 clone，新副本的放置目標與創建時類似 * 為了防止 clone 流量壓倒客戶端流量，master 限制了集群和每個 chunksercer 上的 clone 數量 * 每個 chunkserver 通過限制對 source chunkserver 的讀取請求來限制每個 clone 使用的頻寬量 master 會定期重新平衡副本，檢查當前的副本分佈並移動副本以實現更好的 disk 空間和負載平衡 * master 會逐步填充新的 chunkserver，而不是立即用新 chunk 和隨之而來的大量寫流量淹沒它 * 新副本的放置標準類似於上述討論 * 必須選擇要移除的現有副本，通常會移除那些在 disk 空間低於平均水平的 chunkserver 上的副本 ### 4.4 Garbage Collection 文件被刪除後，GFS 不會立即回收可用的物理存儲空間，只有在文件和 chunk 層級的定期垃圾回收過程中，它才會 lazy回收 #### 4.4.1 Mechanism 1. 當應用程序刪除文件時，master 會像處理其他更改一樣立即記錄刪除操作 2. mater 會將文件重命名為包含刪除時間戳的隱藏名稱 3. 文件仍然可以通過新特殊名稱讀取，並且可以通過將其重命名回正常名稱來取消刪除 5. 在 master 對文件系統命名空間的定期掃描過程中，如果這些隱藏文件已存在超過三天（此間隔是可配置的），它會將其刪除，master 中 file 的相關 metadata 會被刪除(切斷了文件與所有 chunk 的鏈接) 6. 在對 chunk 命名空間的定期掃描中，master 會識別孤立的 chunk （即無法從任何文件訪問到的 chunk），並刪除這些 chunk 的 metadata 7. 在與 master 定期交換的 heartbeat 消息中，每個 chunkserver 報告它擁有的 chunk，而 master 會回覆所有不再存在於 metadata 中的 chunk，chunkserver 可以自由刪除這些 chunk 的副本 #### 4.4.2 Discussion 垃圾回收的存儲回收方法相比於立即刪除有幾個優點 * 在經常有元件故障的大規模分佈式系統中，提供了一種簡單、統一、可靠的方式來清理任何被認為無用的副本 * chunk 創建可能在一些 chunksercer 上成功一些不成功，留下 master 不知道存在的副本 * 副本刪除消息可能丟失，master 必須記住在故障期間發的消息 * 將存儲回收與 master 的定期後台活動合併 * 在批處理中完成的，成本被平分 * 只有在 master 相對空閒時才進行，master 可以更迅速地響應需要及時關注的客戶端請求 * 回收存儲的延遲提供了一個防止意外、不可逆刪除的安全性 缺點: 延遲有時會妨礙用戶在存儲緊繃時調整空間使用 * 通過在文件被再次明確刪除時加速存儲回收來解決問題 * 例如，反覆創建和刪除臨時文件的應用程序可能無法立即重複使用存儲 * 允許用戶對命名空間的不同部分應用不同的複製和回收策略 * 例如，用戶可以指定某些目錄樹內的文件中的所有 chunk 都不進行複製，並且任何刪除的文件會立即且不可逆地從文件系統狀態中移除 ### 4.5 Stale Replica Detection :::success 對於每個 chunk，master 維護一個 chunk 版本號，以區分最新的副本和過時的副本 ::: 版本號 * 每當 master 授予 chunk 的新租約時，它會增加 chunk 的版本號並通知最新的副本 * 如果另一個副本當前不可用，其 chunk 版本號將不會被更新，當 chunkserver 重新啟動並報告其 chunk 集及其相關的版本號時，master 將檢測到該 chunkserver 有一個過時的副本 * 如果 master 看到一個版本號大於其記錄中的版本號，則 master 假設在授予租約時出現故障，並將更高的版本號視為最新的版本號 * 在任何客戶端被通知前，master 和這些副本都會在其持久性狀態中記錄新的版本號，也就是在客戶端開始寫入 chunk 之前進行 * master 在定期垃圾回收中刪除過時的副本，在此之前，當 master 回覆客戶端的 chunk 信息請求時，它視為過時的副本不存在 * 當 master 通知客戶端哪個 chunkserver 持有 chunk 的租約，或指示 chunkserver 在 clone 中從另一個 chunkserver 讀取 chunk 時，它會包括 chunk 版本號 * 客戶端或 chunkserver 在執行操作時會驗證版本號，以確保其始終訪問最新的數據 ## 5. FAULT TOLERANCE AND DIAGNOSIS ### 5.1 High Availability 通過兩個簡單但有效的策略來保持整個系統的高可用性：快速恢復、複製 #### 5.1.1 Fast Recovery 機器被設計為能夠在幾秒鐘內恢復狀態並重新啟動 * 不區分正常和異常終止，server 通常只是通過殺死 process 來關閉 * 客戶端和其他 server 在它們對未完成的請求超時後，會重新連接到重啟的 server 並重試操作，經歷一次輕微的中斷 #### 5.1.2 Chunk Replication * 用戶可以為文件命名空間的不同部分指定不同的複製程度，default 為三個副本 * master 在需要時 clone 現有副本，以保持每個 chunk 在 chunkserver 下線或通過checksum驗證檢測到損壞的副本時完全複製 #### 5.1.3 Master Replication master 的狀態需要被複製以提高可靠性 * log 和 checkpoint 在多台機器上進行複製，對狀態的變更只有在 log 被刷新到本地 disk 和所有 master 副本後才被認為是提交的 * 當一個 master process 失敗時，可以幾乎立即重新啟動；如果 master 的機器或 disk 發生故障，GFS 外部的監控設施會在其他地方啟動一個新的 master process，使用複製的 log * 客戶端只使用 master 的標準名稱 * 例如 gfs-test，這是一個 DNS 別名，如果 master 遷移到另一台機器，可以更改該別名 * shadow master * 在 primary master 宕機時提供文件系統的只讀訪問 * 是影子而非鏡像，它們可能會稍微滯後於 primary master * 增強了對不經常變更文件或不介意獲取稍微舊結果的應用程序的讀取可用性 * 因為文件內容是從 chunkserver 讀取的，應用程序不會察覺到舊的文件內容 * 在短時間內可能會陳舊的是文件 metadata，如目錄內容或訪問控制信息 * 為了保持自身的信息更新，會讀取增長的 log 的副本，並按與 primary master 完全相同的順序將更改應用到其數據結構中 * 平常和 primary master 的行為一樣，但須依賴由 primary master 決定創建和刪除副本而產生的副本位置更新 ### 5.2 Data Integrity >檢測存儲數據的損壞 >* 可以使用其他 chunk 副本來恢復數據，但通過跨 chunkserver 比較副本來檢測損壞是不切實際的 >* 不同的副本可能是合法的，每個 chunkserver 必須獨立驗證其副本的完整性 checksum * 一個 chunk 被分成 64 KB 的 block，每個 chunk 都有一個對應的 32 bit 的 checksum * checksum 保存在 memory 中，並與 log 分開持久存儲，與用戶數據分離 * 讀取操作 1. chunkserver在返回任何數據給請求者之前，會驗證讀取範圍內數據chunk的checksum * chunkserver不會將損壞的數據傳播到其他機器 2. 如果一個 chunk 與記錄的 checksum 不匹配，chunkserver 會向請求者返回錯誤並向master 報告不匹配 3. 作為回應，請求者將從其他副本讀取數據，而 master 將從另一個副本 clone 該 chunk 4. 在新的有效副本到位後，master 指示報告不匹配的 chunkserver 刪除其副本 * checksum 對讀取性能的影響很小 * 大多數讀取操作跨越至少幾個 chunk，只需要讀取和校驗少量額外的數據 * GFS 客戶端 code 通過嘗試在 checksum block 邊界對齊讀取操作來減少開銷 * chunkserver 上的 checksum 查詢和比較是在沒有任何 I/O 的情況下完成的，通常可以與 I/O 重疊進行 * 寫入操作 * append * 增加更新最後一個部分的 checksum block 的 checksum，並為任何新增的checksum block 計算新的 checksum * 即使最後一個部分 checksum block 已經損壞且現在未能檢測到，新 checksum 值也不會與存儲的數據匹配，並且在下次讀取該 block 時會檢測到損壞 * 覆蓋 chunk 的現有範圍 * 必須讀取並驗證被覆蓋範圍的第一和最後一個 block，然後執行寫入，最後計算並記錄新的 checksum * 在空閒期間，chunkserver 可以掃描並驗證非活動 chunk 的內容 * 允許檢測那些很少被讀取的 chunk 中的損壞 * 一旦檢測到損壞，master 可以創建一個新的未損壞的副本並刪除損壞的副本 * 防止了一個非活動但損壞的 chunk 副本欺騙 master，使其誤以為它有足夠有效的chunk副本 ### 5.3 Diagnostic Tools GFS server 生成記錄許多重要事件和所有 RPC 請求和回覆的 Diagnostic log * 廣泛且詳細的 Diagnostic log 在問題隔離、調試和性能分析方面提供了極大的幫助，同時只產生了極小的成本 * 這些 Diagnostic log 可以自由刪除而不影響系統的正確性 * RPC log 包括在網路上發送的請求和回應，除了讀取或寫入的文件數據 * 通過匹配請求與回應並整理不同機器上的 RPC 記錄，可以重建整個交互歷史以診斷問題，還用作負載測試和性能分析的跟蹤記錄 * log 的性能影響很小，因為這些 log 是按順序且異步寫入的，最近的事件也保存在 memory 中，並可用於持續在線監控