google三篇論文之GFS

Google在03至06年發表了著名的三大論文——GFS、BigTable、MapReduce，用來實現一個大規模的管理計算系統。

今天先來談談GFS。因為論文里大段大段的文字加上專業術語讀起來對我來說還是有一定困難的，這幾篇論文我粗略地看了一遍，然后查詢了一些資料，把我的理解以及把論文里一些原文提取出來整合了一下。把每個知識點單獨列出來再分為更小的知識點，這樣覺得比較容易理解。如果什么地方有理解錯誤的話，也請大家見諒。

谷歌之所以現在能稱霸世界搜索引擎市場，最重要的技術就是GFS，GFS是Google分布式存儲的基石，其他存儲系統，比如Google的bigtable、megastore、percolator均直接或者間接的構建在GFS上。Google?File?System那么被人稱道的原因就是它是Google集群技術的核心。

一、GFS的設計目標

Google?File?System是一個面向密集應用的，可伸縮的大規模分布式文件系統，以滿足其龐大的儲存需求。GFS與之前的分布式文件系統具有以下不同：

1、組件失效被認為是常態事件，而不是意外事件

Google的一個應用至少有成百上千臺服務器正在運轉，同時也有一定數量級的用戶進行訪問，而系統不能保證時時刻刻每臺服務器都運轉正常，任意時刻下某個服務器都有可能因為人為操作的失誤、程序的bug、操作系統的bug、硬件或者網絡的問題，導致組件失效。即使昂貴的硬件設備也不能完全阻止這種情況發生，所以GFS使用多個廉價的磁盤驅動器來組成存儲設備。為了對抗組件的失效，GFS中包含了監視、錯誤偵測、容錯以及自動修復的機制。

2、系統存儲一定量的大文件，數GB的文件非常普遍

因為GFS處理的都是大規模的數據集，以后面對的基本是數百GB級別的數據，所以設計的假設條件和參數，比如I/O操作和Block的尺寸都需要重新考慮。雖然GFS支持對以KB計算的小文件進行處理，但是這樣做效率并不高。

3、系統的工作負載的讀操作主要有兩種：大規模的流式讀取和小規模的隨機讀取。

大規模的流式讀取通常一次讀取1MB甚至更多的數據。來自同一個客戶機的連續操作通常是讀取同一個文件中的連續的一個區域。小規模的隨機讀取通常是在文件某個隨即位置讀取幾個KB的數據。

所以，如果應用程序對性能非常關注，通常的做法是把小規模的隨機讀取操作合并并且排序，之后按順序批量讀取，這樣就避免了在文件中前后來回移動讀取位置。

4、絕大部分文件的修改是采用在文件尾部追加數據，而不是覆蓋原有數據的方式。

Google應用中對大部分文件的修改，不是覆蓋原有數據，而是在文件尾追加新數據。對文件的隨機寫是幾乎不存在的，一個文件一旦被寫好，只是被連續地讀取。對于海量文件的訪問模式，客戶端對數據塊緩存已經沒有意義。

5、應用程序和文件系統的API的協同設計提高了系統的靈活性

Google希望通過簡化GFS的一致性模型來簡化文件系統，而不是給應用程序太多壓力。由于同時讀寫數據的客戶端很多，因此使用最小的同步開銷來實現的原子的多路追加數據操作是必不可少的，所以數據的追加操作是性能優化和原子性保證的主要考量因素。

6、高性能的穩定網絡帶寬遠比低延遲重要。

大多數的應用程序都是高速地處理大量數據，而對每一次的讀寫操作沒有嚴格的時間要求。?目標程序（客戶端）絕大部分要求能夠高速率的、大批量的處理數據，高性能穩定的網絡帶寬比延遲更重要。

7、GFS提供了快照操作

GFS中的快照功能是非常強大的，可以非常快的對文件或者目錄進行拷貝，并且不影響當前的操作（讀、寫、復制）。快照也能以很低的成本創建一個文件或者目錄樹的拷貝。

二、GFS架構

一個GFS集群包含了一個單獨的Master節點（Master）、多臺Chunk服務器（Chunkserver），并且同時被多個客戶端（Client）訪問。

Master：管理元數據、整體協調系統活動

ChunkServer：存儲維護數據塊，讀寫文件數據

Client：向Master請求元數據，并根據元數據訪問對應ChunkServer的Chunk

1、GFS文件的存儲方法

GFS存儲的文件都被分割成固定大小的塊（Chunk），之后Master服務器會給每個Chunk分配一個不變的、全球唯一的64位Chunk標識。Chunk服務器把Chunk以linux文件的形式保存在本地硬盤上，并根據指定的Chunk標識來讀寫Chunk數據。

出于可靠性考慮，每個Chunk都會復制到多個Chunk服務器上（缺省時為3個）。

2、Master節點職責

(1)管理所有文件系統的元數據，如名字空間（namespace）、訪問控制信息、文件和Chunk的映射信息、以及當前Chunk的位置信息。

(2)管理系統范圍內的活動，如Chunk租用（lease）管理、孤立Chunk的回收、以及Chunk在Chunk服務器之間的遷移。

(3)使用心跳信息周期地和每個Chunk’服務器通訊，發送指令到各個Chunk服務器并接受Chunk服務器的狀態信息。

3、客戶端

(1)GFS客戶端和Master節點的通信只獲取元數據，所有的數據操作都是由客戶端直接和Chunk服務器進行交互的。

(2)GFS客戶端代碼以庫的形式被鏈接到客戶端程序里，客戶端代碼實現了GFS文件系統的API接口函數、應用程序與Master節點和Chunk服務器的通訊、以及對數據進行讀寫操作。

(3)客戶端緩存數據幾乎沒有什么用處，因為大部分程序要么以流的方式讀取一個巨大文件，要么工作集太大根本無法被緩存。但是客戶端會緩存元數據。

三、GFS架構各模塊

單一Master節點：

單一的Master節點可以通過全局的信息精確定位Chunk的位置以及進行復制決策。

另外，我們必須減少對Master節點的讀寫，避免Master節點成為系統的瓶頸。

客戶端并不通過Master節點讀寫文件數據。反之，客戶端向Master節點讀寫文件數據。反之，客戶端向Master節點詢問它應該聯系的Chunk服務器。客戶端將這些元數據信息緩存一段時間，后續的操作將直接和Chunk服務器進行數據讀寫操作。

客戶端讀取數據流程：

首先，客戶端把文件名和程序指定的字節偏移，根據固定的Chunk大小，轉換成文件的Chunk索引。

其次，它把文件名和Chunk索引發送給Master節點。

然后，Master節點將相應的Chunk標識和副本的位置信息發還給客戶端。客戶端用文件名和Chunk索引作為key緩存這些信息。

最后，客戶端發送請求到其中一個副本處，一般會選擇最近的。

Chunk尺寸：

由于GFS主要面向大文件存儲和大規模讀寫操作，所以其選擇了遠大于一般文件系統的64MB的Chunk尺寸。

好處：

(1)減少了客戶端與Master節點通訊的需求。

(2)客戶端可以與一個Chunk進行多次操作，這樣就可以通過Chunk服務器保持較長的TCP連接，減少網絡負載。

(3)可以減少Master節點需要保存的元數據的數量。

壞處：

(1)易產生數據碎片。

(2)小文件占用Chunk少，對小文件的頻繁訪問會幾種在少數ChunkServer上，從而產生小文件訪問熱點。

可能解決的方案：

(1)增大小文件復制參數。

(2)客戶端間互傳數據。

元數據存儲方式：

命名空間、文件和Chunk的對應關系的存儲方式：

內存：真實數據；

磁盤：定期Checkpoint（壓縮B樹）和上次CheckPoint后的操作日志；

多機備份：Checkpoint文件和操作日志。

Chunk位置信息的存儲方式：

內存：真實數據

磁盤：不持久存儲

Master不會持久保存Chunk位置信息，系統啟動和新Chunk服務器加入時向各個Chunk服務器輪訓它們所存儲的Chunk信息。而且通過周期性的心跳信息監控Chunk服務器狀態（數據同步問題一并解決）。

內存中的數據結構：

所有元數據保存在內存中，所以Master服務器的操作速度非常快。并且，Master服務器可以在后臺簡單而高效地周期性掃描自己保存的全部信息。

將元數據全部保存在內存中的方法有潛在問題：Chunk的數量以及整個系統的承載能力都受限于Master服務器所擁有的內存大小。但是在實際應用中，這并不是一個嚴重的問題。Master服務器只需要不到64個字節的元數據就能夠管理一個64MB的Chunk。

四、一致性模型

我的理解是Master對于namespace的修改具有原子性，namespace在邏輯上可以理解為一張查找表，可以將路徑名與元數據相映射。

比如說，當兩個用戶在應用程序中同時同一塊文件區域寫入了數據，或者一個用戶和另外一名用戶在同一時刻同一塊文件區域分別進行了讀寫操作，為了確保數據的讀寫正確，必須要保證數據的一致性。

文件狀態：

一致的（串行/并行追加寫）：如果所有客戶端，無論從哪個副本讀取，獨到的數據都一樣。

已定義的（串行隨機寫）：如果對文件的數據修改之后，region是一致的，并且客戶端能夠看到寫入操作全部的內容

一致但未定義（并行隨機寫）：并行修改操作成功完成之后，所有的客戶端看到同樣的數據，但是無法讀到任何一次寫入操作寫入的數據。

不一致（修改失敗）：file?region內包含了來自多個修改操作的、混雜的數據片段或者不同的客戶在不同的時間會看到不同的數據。

數據修改操作分為寫入或者記錄追加兩種。寫入操作把數據卸載應用程序指定的文件偏移位置上。即使有多個修改操作并行執行時，記錄追加操作至少可以把數據原子性的追加到文件中一次，但是偏移位置是由GFS選擇的。

GFS返回給客戶端一個偏移量，表示了包含寫入記錄的、已定義的region的起點。

經過了一系列的成功的修改操作之后，GFS確保被修改的file?region是已定義的，并且飽含最后一次修改操作寫入的數據。GFS通過以下措施確保上述行為：

(1)對Chunk的所有副本的修改操作順序一致

(2)使用Chunk的版本號來檢測副本是否因為它所在的Chunk服務器宕機而錯過了修改操作而導致其失效。

對失效副本的處理：

失效的副本不會再進行任何修改操作，Master服務器也不再返回這個Chunk副本的位置信息給客戶端。它們會被垃圾收集系統盡快回收。

即使在修改操作成功執行很長時間之后，組件的失效也可能損壞或者刪除數據。GFS通過Master服務器和所有Chunk服務器的定期“握手”來找?到失效的Chunk服務器，并且使用Checksum來校驗數據是否損壞。一旦發現問題，數據要盡快利用有效的副本進行恢復。只有當一個Chunk的所有副本在GFS檢測到錯誤并采取應對措施之前全部丟失，這個Chunk才會不可逆轉的丟失。在一般情況下GFS的反應時間（譯者注：指Master節點檢測到錯誤并采取應對措施）?是幾分鐘。即使在這種情況下，Chunk也只是不可用了，而不是損壞了：應用程序會收到明確的錯誤信息而不是損壞的數據。

從程序實現的角度來說使用以下機制可以更好地實現一致性：

(1)采用追加寫入而不是覆蓋的方式。

(2)checkingpoint機制（每條數據追加寫入的時候都包含一些額外的檢驗信息）。

(3)寫時自檢驗自表示記錄等等方式。

五、系統交互

設計這個系統的一個重要的原則是，最小化所有操作和Master節點的交互。

1、租約(lease)和變更順序

Master收到變更操作請求后：

(1)選擇一個Chunk副本發放定時租約作為主Chunk并返回給客戶端；

(2)客戶端與主Chunk進行通信進行變更操作；

(3)租約超時前，對該Chunk的變更操作都由主Chunk進行序列化控制。

2、數據流

(1)數據流和控制流分開。

(2)控制流從客戶機到主Chunk、然后再到所有二級副本。

(3)數據沿著一個Chunk服務器鏈數序以管道方式推送。

(4)每臺機器都盡量的在網絡拓撲中選擇一臺還沒有接收到數據的、離自己最近的機器(通過IP)作為目標推送數據。

(5)利用基于TCP連接的、管道式數據推送方式來最小化延遲。

3、記錄追加的過程

(1)Master與Chunk副本建立一個lease。

(2)根據建好的租約，客戶機將數據推送給主Chunk以及每一個Chunk副本。

(3)發送請求給主Chunk。

(4)主Chunk根據分配的序列號向Chunk副本中寫數據。

追加操作會使Chunk超過尺寸：

填充當前Chunk；

通知二級副本做同樣操作；

通知客戶機向新Chunk追加；

追加操作不會使Chunk超過尺寸：

主Chunk追加數據；

通知二級副本寫在相同位置上；

成功?-?返回偏移；?失敗?-?再次操作。

(5)回復客戶機追加操作成功。

4、快照

使用COW技術，瞬間完成。快照實現的過程：

(1)收回文件所有Chunk的租約；

(2)操作元數據完成元數據拷貝；

(3)客戶端要寫入該文件的Chunk時，Master通知該Chunk所在ChunkServer進行本地拷貝；

(4)發放租約給拷貝Chunk；

(5)返回拷貝Chunk的位置信息。

六、Master節點設計

Master節點執行所有的名稱空間操作。此外，它還管理著整個系統里所有Chunk的副本：它決定Chunk的存儲位置，創建忻Chunk和它的副本，協調各種各樣的系統活動以保證Chunk被完全復制，在所有的Chunk服務器之間進行負載均衡，回收不再使用的存儲空間。

1、名稱空間管理和鎖

保證Master節點上的并行操作以正確的順序執行。文件操作需獲得父目錄讀鎖和目標文件/目錄寫鎖。

2、副本的位置

Chunk跨機架分布：

兩大目標：

(1)最大化數據可靠性和可用性

(2)最大化網絡帶寬利用率

3、創建，重新復制，重新負載均衡

(1)創建操作，主要考慮：

平衡硬盤使用率；

限制單ChunkServer短期創建次數（創建開銷雖小，但每次創建往往意味著大量的后續寫入）；

跨機架分布。

(2)重復制，即有效副本不足時，通過復制增加副本數。優先考慮：

副本數量和復制因數相差多的；

live（未被刪除）文件的；

阻塞客戶機處理的Chunk進行重復制。策略與創建類似。

(3)重負載均衡，通過調整副本位置，平衡格機負載。策略與創建類似。新ChunkServer將被逐漸填滿。

七、垃圾回收

GFS在文件刪除后不會立刻回收可用的物理空間。

1、當一個文件被應用程序刪除時，Master節點像對待其它修改操作一樣，立刻把刪除操作以日志的方式記錄下來。

2、Master節點并不馬上回收資源，而是把文件名改為一個包含刪除時間戳、隱藏的名字。（設為隱藏文件）

3、Master節點對文件系統命名空間做常規掃描的時候，它會刪除所有三天前的隱藏文件。

4、當隱藏文件被從名稱空間中刪除，Master服務器內存中保存的這個文件的相關元數據才會被刪除。

5、Chunk服務器在和Master節點交互的心跳信息中，報告它擁有的Chunk子集的信息，Master節點回復Chunk服務器哪些Chunk在Master節點保存的元數據中已經不存在了。Chunk服務器可以任意刪除這些Chunk的副本。

好處：

與創建失敗的無效Chunk一致的處理方式；

批量執行開銷分散，Master相對空閑時進行；

刪除操作一定時間內可逆轉。

壞處：

不便于用戶進行?存儲空間調優。

解決方案：

再次刪除加速回收，不同命名空間不同復制回收策略。

過期檢測：Master維護Chunk級別版本號，新租約增加Chunk版本號，并通知所有副本更新版本號，過期Chunk會因版本號過舊被檢測。

八、容錯機制設計

1、高可用性

(1)組件快速恢復

(2)Chunk復制

(3)Master服務器復制

Checkpoint和操作日志多機備份；

Master進程失效重啟，硬件失效則新機器重啟Master進程；

“影子”Master，通過操作日志“模仿”主Master操作，元數據版本稍慢。作用?-?分擔一定負載、失效期暫時接管。

2、數據完整性

每個Chunk服務器必須獨立維護Checksum來校驗自己的副本的完整性。原因：

(1)跨Chunk服務器比較副本開銷大；

(2)追加操作造成的的byte級別不一致，導致無法通過比較副本判斷完整性。

Checksum校驗的開銷：

(1)Checksum讀取開銷；

(2)Checksum校驗計算開銷。

Checksum對讀操作的性能影響：

Checksum對讀操作的性能影響很小，可以基于幾個原因來分析一下。因為大部分的讀操作都至少要讀取幾個塊，而我們只需要讀取一小部分額外的相關數據進行椒鹽，

GFS客戶端代碼通過每次把讀取操作都對齊在Checksum?block的邊界上，進一步減少了這些額外的讀取操作的負面影響。

九、總結

這篇論文前前后后看了大概一個星期，盡量寫的讓自己好讀懂一些。

GFS支持了必需提供超大文件量與超大流量的?Google?搜尋引擎服務，是許多?Google?應用軟件或云服務的基礎，可以說是云時代的殺手級技術。

后面將會繼續深入了解BigTable和MapReduce。

網絡

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。