GFS 論文筆記
Google 三駕馬車之一
1. 介紹
列出了設計 GFS 的三大基本假設
- 首先，元件故障是一種常态，而不是例外。是以，持續監控、錯誤檢測、容錯和自動恢複必須與系統內建在一起。
- 其次，檔案大小很大 ，是以，設計假設和參數(如I/O操作和塊大小)必須重新考慮。
- 第三，大多數檔案是通過追加新資料而不是覆寫現有資料來改變的
2. 設計摘要
系統由大量廉價的普通伺服器組成，需要容錯
負載基本是 大量的流式讀取和小量随機讀
高持續帶寬比低延遲更重要。
此外，GFS還有快照和記錄追加操作。
2.3 架構
GFS叢集由單個主伺服器（其實還有幾個影子 master）和多個chunkserver組成，并由多個客戶機通路，架構圖如下所示：
檔案被分成固定大小的塊。每個塊都由一個不可變且全局唯一的64位塊句柄辨別，該句柄是在建立塊時由master配置設定的。Chunkservers将塊作為Linux檔案存儲在本地磁盤上，并讀取或寫入由塊句柄和位元組範圍指定的塊資料。為了提高可靠性，每個塊都被複制到多個chunkserver上。預設情況下，存儲三個副本
master 主伺服器維護所有檔案系統中繼資料，主伺服器定期與心跳消息中的每個塊伺服器通信，給它指令并收集它的狀态。
用戶端和chunkserver都不會緩存檔案資料，然而，用戶端會緩存中繼資料。
2.4 單 master
用戶端從不通過主伺服器讀寫檔案資料。相反，用戶端詢問主伺服器它應該聯系哪個塊伺服器。它在有限的時間内緩存這些資訊，并直接與chunkserver進行互動以進行許多後續操作。
然後，它向主伺服器發送一個包含檔案名和塊索引的請求。主伺服器使用相應的塊句柄和副本的位置進行響應。用戶端使用檔案名和塊索引作為鍵來緩存該資訊。
直到緩存的資訊過期或檔案重新打開。
2.5 塊大小
塊大小的設計：
- 首先減少了客戶與主機互動的需求
- 其次減少網絡開銷
- 第三，它減少了存儲在主伺服器上的中繼資料的大小。
一個小檔案由少量塊組成，可能隻有一個塊。
對于熱點塊的資料，我們通過使用較高的複制因子存儲這些可執行檔案，并使批處理隊列系統錯開應用程式的啟動時間，解決了這個問題。
2.6 中繼資料
master 存儲三種類型的中繼資料：檔案和塊名稱空間、從檔案到塊的映射以及每個塊副本的位置。
前兩種類型(名稱—塊名稱空間和檔案到塊的映射)也通過将突變記錄到存儲在master的本地磁盤上并複制到遠端機器上的記錄檔來保持持久化
master不會持久地存儲塊位置資訊。相反，它會在主伺服器啟動時詢問每個chunkserver關于它的chunk的資訊，以及每當有chunkserver加入叢集時。
2.6.1 記憶體資料結構
master 會定期掃描記憶體的中繼資料
這種定期掃描用于實作塊垃圾收集、在chunkserver故障時的重新複制，以及塊遷移以平衡負載和磁盤空間
2.6.2 塊位置
塊位置包含在每次的心跳中
2.6.3 記錄檔
中繼資料唯一 的持久記錄
master通過重放記錄檔恢複檔案系統狀态。為了最小化啟動時間，我們必須保持日志較小。每當日志超過一定的大小時，主檢查點就會改變其狀态，以便它可以通過從本地磁盤加載最新的檢查點并在此之後隻重放有限數量的日志記錄來恢複。檢查點是一種緊湊的類似b樹的形式，可以直接映射到記憶體中，并用于名稱空間查找，而不需要額外的解析。這進一步加快了恢複速度并提高了可用性。
恢複隻需要最新的完整檢查點和後續的日志檔案。舊的檢查點和日志檔案可以自由删除，但我們保留了一些以防止災難發生。檢查點期間的失敗不會影響正确性，因為恢複代碼會檢測并跳過不完整的檢查點。
2.7 一緻性模型
GFS 為強一緻性，通過使用 塊版本号 來檢測塊的一緻性和是否進行磁盤垃圾回收
GFS通過主伺服器和所有塊伺服器之間的正常握手識别出失敗的塊伺服器，并通過校驗和檢測資料損壞
2.7.2 應用的實作
GFS 一緻性的實作手段：依賴追加而不是覆寫、檢查點和寫入自驗證、自辨別的記錄。
讀取器隻驗證和處理直到最後一個檢查點的檔案區域，該檢查點已知處于已定義的狀态。
讀取器可以使用校驗和識别并丢棄額外的填充和記錄片段。
3. 系統互動
3.1 租約
我們使用租約來維持副本間一緻的變異順序。
primary為chunk的所有突變選擇一個序列順序。當應用突變時，所有的複制都遵循這個順序。
這些擴充請求和授權由master和所有塊伺服器之間定期交換的HeartBeat消息承載。
master 和 主伺服器之間存在租約，預設逾時60s，是當主伺服器在租約期間，就可以在心跳包中無限地延長租約時間；master 也可以在主伺服器的租約期間進行租約撤銷，如果主伺服器失去和 master 的連接配接，master 也可以把租約用在從伺服器上
GFS 的資料流如下圖所示：
- 用戶端請求 master 擁有租約的主伺服器位址，如果沒有，則指定一個
- master 傳回主伺服器辨別以及從伺服器的位置；用戶端緩存資料，僅當主伺服器不可達或不再持有租約
- 用戶端發送資料給所有副本，通過将控制資訊和資料流解耦，可以根據網絡拓撲對資料流排程，不用關心主從
- 一旦所有副本接收資料後，用戶端發送寫請求到主伺服器，主伺服器将接收到的所有突變編号并按序應用到本地
- 主伺服器轉發寫請求到所有副本，每個副本按照同樣編号序應用突變
- 副本成功後傳回成功給主伺服器
- 任意副本出錯都将傳回錯誤給用戶端，有可能最終出錯了但是主和部分從是成功；若主伺服器出錯，則不會應用到副本上；目前應對出錯的辦法是重試
對過大的寫請求，如跨 chunk，用戶端還會分成幾個操作進行
3.2 資料流
資料沿着塊伺服器鍊線性推送
每台機器都将資料轉發到網絡拓撲中“最近的”沒有接收資料的機器。
我們的網絡拓撲結構非常簡單，可以從IP位址準确地估計“距離”。
一旦chunkserver接收到一些資料，它立即開始轉發。
在沒有網絡擁塞的情況下，将B位元組傳輸到R副本的理想運作時間是B/T + RL，其中T是網絡吞吐量，L是兩台機器之間傳輸位元組的延時。
3.3 原子資料追加
如果用戶端使用傳統的寫操作，則需要額外複雜和昂貴的同步，例如通過分布式鎖管理器。
Record append是一種變體，它遵循3.1節中的控制流，在主節點上隻添加了一點額外的邏輯。
塊碎片
用戶端将資料推入檔案最後一塊的所有副本，然後将請求發送給主伺服器。主程式檢查将記錄追加到目前塊是否會導緻塊超過最大大小(64 MB)。如果是，它将塊填充到最大大小，告訴輔助程式做同樣的事情，并回複客戶機，訓示應該在下一個塊上重試操作。(Record append被限制為最多為最大塊大小的四分之一，以使最壞情況的碎片保持在可接受的水準。)
一緻性保證
根據我們的一緻性保證(antees)，成功記錄追加操作寫入資料的區域是定義的(是以是一緻的)，而插入的區域是不一緻的(是以是未定義的)。
3.4 快照
快照操作幾乎是瞬間複制一個檔案或一個目錄樹(“源”)，同時最小化正在進行的突變的任何中斷。
像AFS[5]一樣，我們使用标準的寫時複制技術來實作快照
4. master 操作
master 執行如下操作：
它做出放置決策，建立新的塊和副本，并協調各種系統範圍的活動，以保持塊完全複制，在所有chunkserver之間平衡負載，并回收未使用的存儲
4.1 命名空間管理和鎖
master 允許多個操作處于活動狀态，并在名稱空間的區域上使用鎖以確定适當的序列化
GFS邏輯上将其命名空間表示為一個将完整路徑名映射到中繼資料的查找表。使用字首壓縮，可以有效地在記憶體中表示該表。命名空間樹中的每個節點(無論是絕對檔案名還是絕對目錄名)都有一個關聯的讀寫鎖。
每個主操作在運作之前都會獲得一組鎖。通常，如果涉及/d1/d2/…/dn/leaf，它将獲得目錄名/d1， /d1/d2，…, / d1、d2 /……/d1/d2/…/dn/葉上的讀鎖或寫鎖。注意，根據操作的不同，leaf可能是一個檔案或目錄。
現在我們示範這種鎖定機制如何防止在/home/user被快照到/save/user時建立檔案/home/user/foo。快照操作獲得/home和/save上的讀鎖，以及/home/user和/save/user上的寫鎖。檔案建立ac-查詢/home和/home/user上的讀鎖，以及/home/user/foo上的寫鎖。這兩個操作将被正确地序列化，因為它們試圖在/home/user上獲得沖突的鎖。在父目錄上建立檔案不需要寫鎖，因為沒有目錄或類似inode的資料結構可以保護不被修改。名稱上的讀鎖足以保護父目錄不被删除。
它們首先在名稱空間樹中按級别排序，并按字典順序排列在同一級别内。
4.2 副本放置
我們還必須在機架上放置塊的複制
它還意味着一個塊的流量(尤其是讀)可以利用多個機架的聚合帶寬。另一方面，寫流量必須流經多個機架，這是我們願意做的一種權衡。
4.3 建立，重複制，再平衡
建立塊副本有三個原因:塊建立、重新複制和再平衡。
- 我們希望在磁盤空間使用率低于平均水準的chunkserver上放置新的副本。
- 我們想要限制每個塊伺服器上“最近”建立的數量。
- 如上所述，我們希望将塊的副本分散到各個機架上。
chunkserver變得不可用，它報告它的副本可能已損壞，它的一個磁盤由于錯誤而被禁用，或複制目标增加。需要重新複制的每個塊都根據幾個因素進行了優先級排序。一個是它離複制目标有多遠。例如，我們給丢失兩個副本的塊比隻丢失一個副本的塊更高的優先級。此外，我們更傾向于首先為活動檔案重新複制塊，而不是那些屬于最近删除的檔案的塊(參見4.4節)。
均衡磁盤空間使用率，限制任何單個chunkserver上的活動克隆操作，并跨機架分布副本。為了防止克隆流量超過客戶機流量，主伺服器對叢集和每個塊伺服器的活動克隆操作數量進行了限制。此外，每個chunkserver通過對源chunkserver的讀請求進行節流來限制它在每個克隆操作上花費的帶寬。
master 定期檢查目前副本分布并移動副本以獲得更好的磁盤空間和負載平衡。
此外，主伺服器還必須選擇要删除的現有副本。通常，它傾向于删除空閑空間低于平均水準的chunkserver上的那些伺服器，以便均衡磁盤空間使用。
4.4 垃圾回收
删除檔案後，GFS不會立即回收可用的實體存儲。它隻在檔案和塊級别的正常垃圾收集期間惰性地這樣做。
4.4.1 機制
不是立即回收資源，檔案隻是重命名為一個隐藏的名稱，其中包括删除時間戳。在主伺服器對檔案系統名稱空間的正常掃描期間，如果隐藏檔案存在超過三天(間隔是可配置的)，它将删除這些隐藏檔案。
在類似的塊命名空間的正常掃描中，主塊辨別孤立的塊(即從任何檔案無法通路的塊)，并擦除這些塊的中繼資料。在與主伺服器定期交換的HeartBeat消息中，每個chunkserver報告它所擁有的塊的子集，主伺服器用不再出現在主伺服器中繼資料中的所有塊的辨別進行響應。
回收政策利弊
- 垃圾回收簡單可靠
- master 負責，成本攤銷
- 給實體删除提供緩沖時間
主要的缺點是，當存儲時間很緊時，延遲有時會妨礙使用者調整使用。重複建立和删除臨時檔案的應用程式可能無法立即重用存儲。如果已删除檔案再次顯式删除，我們通過加速存儲回收來解決這些問題。
4.5 陳舊副本判斷
對于每個塊，主塊維護一個塊版本号，以區分最新的副本和陳舊的副本。
每當主伺服器授予塊的新租約時，它就增加塊的版本号并通知最新的副本。
主伺服器在其正常垃圾收集中删除過時的副本。
客戶機或chunkserver在執行操作時驗證版本号，以便始終通路最新的資料。
用版本号決定一個 chunk 的更新狀态
5. 容錯與診斷
5.1 高可用
快速恢複和複制
5.1.2 塊複制
當chunkserver離線或通過校驗和轉換(參見5.2節)檢測損壞副本時，主克隆現有副本，以保持每個塊完全複制。
使用奇偶碼或者擦除碼
5.1.3 master 複制
它的記錄檔和檢查點被複制到多台機器上。隻有當其日志記錄在本地和所有主副本上重新整理到磁盤後，才認為對狀态的更改已送出
如果它的機器或磁盤出現故障，監視GFS外部的基礎設施将在其他地方啟動一個新的主程序，并使用複制的記錄檔。
而且，“影子”主伺服器提供對檔案系統的隻讀通路，即使主伺服器當機。
5.2 資料完整性
每個chunkserver使用校驗和來檢測存儲資料的損壞。
此外，不同的副本可能是合法的:GFS突變的語義，特别是前面讨論的原子記錄附加，并不保證相同的副本。是以，每個塊伺服器必須通過主包含校驗和獨立地驗證自己副本的完整性。
與其他中繼資料一樣，校驗和儲存在記憶體中，并通過日志持久化存儲，與使用者資料分開。
對于讀操作，chunkserver在将任何資料傳回給請求者(無論是用戶端還是另一個chunkserver)之前，驗證重疊讀範圍的資料塊的校驗和。
在一個有效的新副本就位後，主伺服器訓示報告不比對的chunkserver删除它的副本。
GFS用戶端代碼通過嘗試在校驗和塊邊界對齊讀取進一步減少了這個開銷。
我們隻是增量地更新最後部分校驗和塊的校驗和，并為append填充的任何全新校驗和塊計算新的校驗和。
如果我們在部分覆寫第一個和最後一個塊之前不驗證它們，新的校驗和可能隐藏存在于未被覆寫區域的損壞。
在空閑期間，chunkserver可以掃描和驗證非活動塊的内容。這允許我們檢測很少被讀取的塊中的腐敗。
5.3 診斷工具
通過将請求與應答進行比對，并在不同的機器上整理RPC記錄，我們可以重建整個互動曆史來診斷問題。
log 是順序和異步的
6. 測試
儲存在master上的中繼資料要小得多，隻有幾十mb，或者平均每個檔案大約100位元組。這與我們的假設一緻，即在實踐中，主記憶體的大小不會限制系統的容量。大多數檔案中繼資料是以字首壓縮形式存儲的檔案名。其他中繼資料包括檔案所有權和權限，從檔案到塊的映射，以及每個塊的目前版本。此外，我們為每個塊存儲目前的複制位置和一個用于實作寫時複制的引用計數。
我們已經改變了主資料結構，允許通過名稱空間進行有效的二進制搜尋。
7. 經驗
早些時候，由于fsync()的開銷，我們在Linux 2.2核心上遇到了一些問題。它的開銷與檔案的大小成比例，而不是與修改部分的大小成比例。對于我們的大型記錄檔來說，這是一個問題，特别是在我們實作檢查點之前。我們使用同步寫來解決這個問題，最終遷移到Linux 2.4。
另一個Linux問題是單個讀寫器鎖，位址空間中的任何線程在從磁盤調入(讀寫器鎖)或在mmap()調用中修改位址空間(寫器鎖)時都必須持有該鎖。我們發現系統在低負載下出現了短暫的逾時，并努力查找資源瓶頸或零星的硬體故障。甚至，我們發現，當磁盤線程在對先前映射的資料進行分頁時，這個鎖阻塞了主網絡線程将新資料映射到記憶體。由于我們主要受到網絡接口而不是記憶體複制帶寬的限制，