GFS

目錄

• 一、GFS是什麼
• • 1、GFS核心思想
  • 2、一緻性
  • • 1)、一緻性模型
    • 2)、一緻性保障
• 二、讀寫操作
• • 1、租約與變更
  • 2、資料修改
  • 3、資料流
• 三、API
• 四、體系結構
• • 1、master伺服器
  • • 1)、中繼資料
    • • ①、chunk位置資訊
      • ②、記錄檔
    • 2)、master結點的操作
    • • ①、命名空間管理和鎖
      • ②、副本的位置
      • ③、建立、重新複制、重新負載均衡
      • ④、垃圾回收
      • ⑤、過期失效副本的檢測
  • 2、chunk伺服器
• 五、容錯
• • • 1、高可用性
    • • 1)、快速恢複
      • 2)、chunk複制
      • 3)、master伺服器的複制
    • 2、資料完整性

一、GFS是什麼

谷歌檔案系統(GFS)就是一個存放資料的分布式檔案系統，個人了解就是一個可以在多台計算機上存儲資料的系統，是其他上層系統(BigTable等)的基礎。

1、GFS核心思想

GFS追求的是整體系統的穩定性，其處理對象是大資料。其指導思想為：

1. 元件故障被當做一種常态進行處理

   也就是說，不認為系統内的每一台計算機都是可靠的。雖然元件故障是正常的，但是需要有措施保障整個系統的正常運作。

2. 對于吉位元組數量級的大檔案的處理

   說明了GFS的處理對象是大檔案，但是仍需要支援小檔案，不過不會對小檔案進行專門優化。

3. 絕大部分修改是追加資料

   實際中随機寫入幾乎不存在，檔案的修改就是追加資料。檔案一旦寫完後，對檔案的操作就隻有讀，而且一般是順序讀。GFS仍然支援小規模的随機寫，但是不保證效率。

4. 應用程式和檔案系統API的協同設計提高整個系統的靈活性

   放松了對GFS一緻性模型的要求。

2、一緻性

檔案命名空間的修改是原子性的，僅由master伺服器控制，master伺服器控制方式包括：

1. 命名空間鎖提供了原子性和正确性保障。
2. 記錄檔定義了操作的順序。

1)、一緻性模型

操作的結果有以下幾類：

1. 一緻的

   對于所有用戶端，無論從哪個副本讀取，讀到的資料都一樣。

2. 已定義的

   一緻的，并且用戶端能夠看到寫入操作的全部内容。一個資料修改操作未受到其他操作的幹擾，那麼它就是已定義的。并行操作修改完成之後，檔案内容包含了多個來自不同用戶端的混雜的資料片段，處于一緻的、未定義的狀态。

3. 失敗的

   結果處于不一緻狀态。

2)、一緻性保障

GFS通過以下操作保證資料是一緻的：

1. 對chunk所有副本的修改操作順序一緻

2. chunk版本号

   使用chunk的版本号檢測chunk是否因為所在伺服器當機而錯過修改，master伺服器不會傳回失效的副本的位置給用戶端，它們會被盡快回收。但是，用戶端可能會緩存chunk位置資訊，這就導緻用戶端有可能會讀取失效的資料。不過，由于修改一般是追加操作，是以用戶端讀到的是提前結束的chunk，而不是過期的資料。

3. 定期握手

   在修改操作執行成功一段時間後，元件也有可能會失效。GFS通過master伺服器和所有chunk伺服器定期握手來找到失效的chunk伺服器，并使用checksum校驗資料是否正确，一旦資料損壞，要盡快利用副本進行恢複。

二、讀寫操作

用戶端首先通路master伺服器以獲得chunk伺服器資訊，然後通路chunk伺服器完成資料讀寫。client與master之間隻有控制流，大大降低了master的負載。client與chunk伺服器直接傳輸資料流，由于每個檔案被分成多個chunk，整個系統的IO高度并行。

1、租約與變更

1. 租約

   master伺服器為chunk的一個副本建立一個租約，這個副本就被稱為主chunk。設計租約的目的是最小化master伺服器的管理負擔。租約的初始逾時設定為60s，不過，隻要chunk被修改了，主chunk就可以申請更長的租期。

2. 變更

   變更是會改變chunk内容或中繼資料的操作，如寫入、記錄追加。變更操作會在chunk所有副本上執行。使用租約來保證變更順序一緻性。主chunk對chunk所有更改操作進行序列化，所有副本都遵循這個序列進行修改操作。

2、資料修改

資料修改分為寫入和記錄追加。寫入操作是把資料寫在應用程式指定的偏移位置上，而并行化的記錄追加的偏移位置是由GFS選擇的。 如果一次寫入的資料量很大，client會分成多個寫操作。此時可能會出現一緻但未定義的結果。

修改的過程如下：

1. client向master詢問哪個chunk伺服器持有目前租約以及其他副本的位置，如果沒有chunk持有租約，就這各副本中選擇一個建立租約。
2. master将主chunk辨別及各副本位置傳回給client，客戶機緩存這些資訊。隻有主chunk不可用或者主chunk回複資訊表明其不再持有租約時，client才重新與master聯系。
3. 客戶機把資料推送到所有副本上。客戶機可以以任意順序推送，chunk伺服器接收到資料，并把其儲存在内部LRU緩存中，一直到資料被使用或者過期交換出去。
4. 當所有副本都确認接收到資料，client發送寫請求到主chunk伺服器，主chunk為接收到的所有操作配置設定連續的序列号，并按照序列号本地執行這些操作。
5. 主chunk将寫請求傳遞給所有副本，每個副本按照相同的序列号執行操作。
6. 所有副本回複主chunk已完成操作。
7. 主chunk伺服器回複client操作執行結果。

3、資料流

為了提高網絡效率，資料流和控制流分開處理。在資料從client到每一個chunk伺服器的過程中，資料沿着一條精心選擇的chunk伺服器鍊推送。

為了充分利用每台機器的帶寬，資料沿着一個chunk伺服器鍊順序推送，而不是以其他拓撲形式分散推送。線上性模式下，每台機器的所有出口帶寬都用于以最快的速度傳輸資料，而不是在多個接收者之間配置設定帶寬。為了避免高延遲的連接配接，每台機器都盡量在網絡拓撲中選擇一台沒有接收資料的、離自己最近的機器作為目标。

三、API

GFS的API包括建立、删除、打開、關閉、讀、寫、快照、記錄追加，對于後4種而言：

1. 讀

   讀分為大規模的流式讀取和小規模的随機讀取，一般都是前者。

2. 寫

   寫一般是追加操作，而花費最小的同步開銷來保證多路追加操作的原子性是必不可少的，這是因為一般會有很多用戶端同時寫資料。

3. 快照

   快照是以低成本來建立一個檔案或目錄樹的拷貝，幾乎可以瞬間完成對一個檔案或目錄樹的拷貝，并且幾乎不會對正在進行的其他操作造成幹擾。

   當master伺服器接收到一個快照請求，它首先取消快照檔案的所有chunk的租約，用于保證此後所有對該檔案的寫操作都必須與master互動以找到租約持有者，使得master可以率先建立一個新拷貝。

   租約取消或者過期後，master把這個操作以日志的形式儲存在硬碟上。然後master伺服器通過複制源檔案或者目錄的源資料的方式，把這條日志記錄的變化反映到儲存在記憶體的狀态中，新建立的快照檔案與源檔案指向相同的chunk位址。

   快照操作之後，當client想寫資料到檔案中時，它首先會發送一個請求到master伺服器查詢租約持有者。master注意到該檔案的引用計數超過1，不會馬上回複client的請求，而是選擇一個新的chunk句柄C’。之後，master結點要求每個擁有該檔案目前副本的的chunk伺服器建立一個叫做C’的chunk。通過在源chunk所在chunk伺服器上建立新chunk，保證資料不通過網絡傳輸。

4. 記錄追加

   記錄追加是允許多個用戶端同時對一個檔案追加資料，同時保證追加操作的原子性。

   使用記錄追加，client隻需要指定要寫入的資料，GFS保證至少有一次原子的寫入操作成功執行。記錄追加遵循修改流程，不過在主chunk有一些額外的控制邏輯。主chunk會檢查記錄追加操作是否會使目前chunk超過最大尺寸，如果超過了最大尺寸，主chunk首先将目前chunk填充到最大尺寸，之後通知所有副本做相同操作，然後回複client要求其對下一個chunk重新進行記錄追加操作。

   如果記錄追加操作失敗了，client就需要重新進行操作，其結果是同一個chunk的不同副本可能包含不同的資料：重複包含一個記錄部分或者全部的資料。GFS并不保證chunk的所有副本在位元組級别完全一緻，它隻保證作為一個原子的資料被至少被寫入一次。

四、體系結構

GFS包括一台master伺服器、多台chunk伺服器以及多個用戶端。

在GFS中，檔案被分成固定大小的chunk，在chunk建立的時候，會配置設定給它一個不變的、唯一的辨別。每個塊都會以副本的形式複制到多個伺服器上，預設數量是3個。

1、master伺服器

master伺服器管理所有的檔案系統中繼資料，包括命名空間、通路控制資訊、檔案和chunk的映射資訊、chunk的位置資訊。此外，master伺服器還負責很多活動，如chunk租用管理、孤兒chunk的回收、chunk在chunk伺服器中的遷移。最後，master伺服器使用心跳資訊獲得chunk伺服器狀态資訊。

1)、中繼資料

master伺服器存儲3種類型的中繼資料：檔案和chunk的命名空間、檔案和chunk的對應關系、每個chunk副本的位置。所有的中繼資料都儲存在master記憶體中，前2種中繼資料也會以日志的形式儲存在系統日志檔案中，并複制到其他master伺服器上。master伺服器不會持久的儲存chunk位置資訊，master伺服器啟動時或者新的chunk伺服器加入時，master伺服器向各個chunk伺服器輪詢存儲的chunk資訊。

①、chunk位置資訊

master伺服器并不持久化儲存chunk存儲在哪個chunk伺服器上，master伺服器會在啟動的時候輪詢chunk伺服器獲得資訊。因為master伺服器控制所有chunk的配置設定，是以其擁有最新的資訊。

②、記錄檔

記錄檔包含了關鍵的中繼資料變更記錄，是中繼資料的唯一持久化存儲記錄。日志會被複制到多台遠端伺服器上，并且隻有在日志被寫入本地和遠端機器硬碟後，才會響應用戶端的操作請求。同時，master伺服器采用檢查點技術，以保證在災難發生時快速恢複。

2)、master結點的操作

master結點執行所有的名稱空間操作，還管理着整個系統裡所有chunk的副本：它決定chunk的存儲位置，建立新chunk和它的副本，協調各種各樣的系統活動以保證chunk被完全複制，在所有的chunk伺服器之間進行負載均衡，回收不再使用的存儲空間。

①、命名空間管理和鎖

master伺服器的很多操作會花費很長時間，比如快照必須取消chunk伺服器上所有快照涉及的chunk的租約。為了執行這些操作時，不影響master伺服器上其他操作，允許多個操作同時進行，使用命名空間上的鎖來保證正确的執行順序。

GFS沒有針對每個目錄實作能夠列出目錄下所有檔案的資料結構，GFS也不支援檔案或目錄的連結。在邏輯上，GFS的命名空間就是一個全路徑與中繼資料映射關系的查找表。在存儲命名空間的結構上，每個檔案名或目錄名都有一個與之關聯的讀寫鎖。

每個master結點的操作開始之前都要獲得一系列的鎖，如果一個操作涉及/d1/d2/···/dn/leaf，則需要獲得/d1/d2/···/dn的讀鎖以及/d1/d2/···/dn/leaf的讀寫鎖。leaf可能是一個檔案，也可能是一個目錄。通過采用這種鎖的機制，可以支援對同一目錄的并行操作。鎖在不用的時候會被立即删除，鎖的擷取需要有一個全局一緻的順序避免死鎖。

②、副本的位置

chunk副本位置選擇政策有2大目标：最大化資料可靠性和可用性、最大化網絡帶寬使用率。因為GFS叢集一般是數百台chunk伺服器安裝在許多機架上，是以僅在多台機器上存儲副本是不夠的，必須在多個機架間分布式存儲副本。

③、建立、重新複制、重新負載均衡

當master結點建立一個新的chunk時，在選擇存儲位置上會考慮一下因素：

1. 在低于平均硬碟使用率的chunk伺服器上存儲新的副本
2. 限制在每個chunk伺服器上最近的chunk建立操作次數
3. 把chunk的副本分布在多個機架之間

當chunk的有效副本數量小于使用者指定的複制因數的時候，比如chunk伺服器不可用，master結點會重新複制它。多個需要複制的chunk會根據政策排序，master伺服器選擇優先級最高的chunk，指令某個chunk伺服器直接從某個可用副本中克隆一個新的副本，其存儲位置考慮因素同建立時一樣。

master結點會周期性的對副本進行重新負載均衡。

④、垃圾回收

GFS在檔案删除後不會立即回收空間，GFS空間回收采用惰性政策，隻在檔案和chunk級的正常垃圾收集時進行。

當一個檔案被删除時，master結點立即把操作以日志的形式記錄下來。但是，master結點并不馬上回收結點，而是把檔案名改成一個包含時間戳的、隐藏的名字。當master伺服器對命名空間做正常掃描時，它會删除所有3天前的隐藏檔案。在檔案被真正删除前，可以通過新的特殊名字讀取，或者把檔案名改成正常檔案名來取消删除。當隐藏檔案從命名空間中删除，master伺服器内儲存的相關中繼資料才會删除，也就切斷了檔案和其對應的所有chunk的連接配接。

在對命名空間做正常掃描時，master結點找到孤兒chunk并删除相應中繼資料。在master與chunk的心跳互動時，chunk伺服器報告它所擁有的chunk子集資訊，master伺服器回複chunk伺服器哪些chunk的中繼資料已經不在，chunk伺服器可以任意删除這些chunk。

⑤、過期失效副本的檢測

當chunk伺服器失效時，chunk的副本可能因為錯過了修改而失效。master伺服器儲存了每個chunk的版本号，用來區分目前副本和過期副本。

隻要master結點和chunk簽訂一個新的租約，它就增加chunk的版本号。master伺服器和副本都将新的版本号記錄在持久化儲存的狀态資訊中。如果chunk伺服器失效，那麼副本的版本号就不會增加。當該chunk伺服器重新啟動時會向master伺服器報告它所擁有的chunk和相應的版本号，master伺服器就會檢測出過期的chunk。

master伺服器在垃圾回收過程中移除所有的失效副本。在此之前，master伺服器在回複client的chunk資訊請求時，會簡單的認為那些過期的塊不存在。此外，master在通知client哪個chunk伺服器持有租約或者訓示chunk伺服器從哪個chunk伺服器克隆時，消息中都附帶了版本号。

2、chunk伺服器

chunk伺服器用來存儲檔案，其存儲的機關是塊。每塊的大小為64MB，這個大小保證了中繼資料的數量較少，可以有效減輕master的負載。

五、容錯

元件的數量與品質讓錯誤的發生不可避免，無論是機器還是硬碟都不可靠，需要采取一些措施去應對這些問題。

1、高可用性

在數百台伺服器中，必定有一些是不可用的。使用兩條政策保證系統的高可用性：快速恢複和複制。

1)、快速恢複

不管是master伺服器還是chunk伺服器都不區分正常關閉和異常關閉，它們被設計成可以在數秒内恢複狀态并重新啟動。client可能會感覺系統有些颠簸，正在發出的請求會逾時，需要重新連接配接重新開機的伺服器。

2)、chunk複制

每個chunk都被複制到不同機架的伺服器上，預設的複制因數是3。當chunk伺服器離線或者chunk損壞時，master通過複制已有副本保證chunk被完整複制。

3)、master伺服器的複制

為保證master伺服器的可靠性，master伺服器的狀态也需要複制。master伺服器的所有記錄檔和checkpoint檔案都被複制到多台機器上。隻有相關記錄檔被寫入master伺服器和後備結點的的磁盤，對master伺服器狀态的修改操作才能成功送出。

master伺服器有一個程序負責所有的修改操作，包括垃圾回收等。當它失效時，幾乎可以立即重新啟動。當他所在的機器或磁盤失效時，GFS系統外的監控程序會在其他有完整記錄檔的機器上啟動一個新的master程序。

此外，GFS中還有一些影子master伺服器，它們的資料可能比主master伺服器更新要慢，在主master伺服器當機的時候提供檔案系統隻讀通路。這對于不經常改變檔案或允許資料有少量過期的應用程式來說，可以提高讀取效率。因為資料是存儲在chunk伺服器上，過期的不會是檔案内容，而是檔案的中繼資料。

為了保證自身狀态是最新的，影子master伺服器會讀取目前正在進行的操作的日志副本，并依照和主master伺服器完全相同的順序改變内部資料結構。影子master伺服器啟動的時候，會輪詢chunk伺服器擷取chunk資訊。也會定期和chunk伺服器握手來确定它們的狀态，隻有主master伺服器因為建立和删除副本導緻其位置資訊更新時，影子master伺服器才和主master伺服器通信來更新自身狀态。

2、資料完整性

chunk伺服器通過checksum來檢查儲存的資料是否損壞，跨伺服器比較副本是不實際的。GFS允許有歧義的副本存在，即不保證副本完全相同。是以每個chunk伺服器需要獨立維護checksum來校驗副本的完整性。

每個chunk被分成64KB大小的塊，每個塊對應一個32位的checksum。和其他中繼資料一樣，checksum和使用者資料是分開的，儲存在記憶體和硬碟上，同時也記錄記錄檔。

對于讀操作來說，在把資料傳回給client或其他chunk伺服器之前，chunk伺服器會校驗涉及到的chunk的checksum，保證不會把錯誤的資料傳遞到其他機器上。如果chunk不正确，chunk伺服器傳回給請求者一個錯誤資訊，并通知master伺服器這個錯誤。請求者會從其他副本處讀資料，master伺服器也會clone一個新的副本，新的副本就緒後，master伺服器通知錯誤副本的chunk伺服器删除錯誤的chunk。

checksum的計算針對記錄追加操作做了高度優化，隻增量更新最後一個不完整的塊的checksum，并且用所有追加來的新checksum塊來計算新的checksum。保證即使最後一個不完整的checksum塊已經損壞且不能馬上檢測出來，由于新的checksum與已有資料不吻合，在下次對這個塊進行讀操作時，會檢查出資料已經損壞。

對于寫操作而言，如果其覆寫一個chunk，就必須讀取和校驗被覆寫的第一個和最後一個塊，然後在執行寫操作，否則新的checksum可能會隐藏未被覆寫的區域的資料錯誤。操作完成後，還需要重新計算和寫入新的checksum。