前言

本著常讀常新的原則，最近又一次閱讀了Google三架馬車之一的《Google File System》。它里面的一些設(shè)計思想，實現(xiàn)原則以及取舍，時至今日仍很有參考價值。

今夜，讓我們一起來聽（讀）相聲（經(jīng)典）吧！

注：下文中我們將Google File System簡稱為GFS。

GFS特點

Google File System在考慮通用分布式文件系統(tǒng)設(shè)計的同時，也更多地從自身業(yè)務(wù)需求出發(fā)，提出了一些新的設(shè)計理念和新的系統(tǒng)特點：

• 將機器宕機，重啟，掛掉視為常態(tài)。

  在這樣的前提前下，就要求GFS本身要具備快速自動地故障偵測和轉(zhuǎn)移的能力，在監(jiān)控上允許一定范圍內(nèi)諸如磁盤或網(wǎng)絡(luò)IO等的小波動，對于客戶端來說通過重試或重新獲取meta信息后再重試即可平緩過渡到穩(wěn)定狀態(tài)。

  GFS的這一設(shè)計理念，更長遠(yuǎn)的意義我認(rèn)為是對于大型存儲，計算系統(tǒng)來說，大型機，小型機等不再是唯一的選擇，它們同樣可以使用相對廉價的普通服務(wù)器來構(gòu)建。

• 支持分塊存儲超大文件

  將大文件作分塊存儲，每塊固定長度64M。GFS的64M可謂是為后世的各個分布式存儲塊大小定了個基調(diào)。下面我們簡單說下塊大小的優(yōu)劣勢。

  	大塊	小塊
  元數(shù)據(jù)量	少（更便于完全加載到內(nèi)存）	多（元數(shù)據(jù)過多，可能需多級索引，復(fù)雜度增加）
  磁盤文件數(shù)	少（inode數(shù)量不易成為瓶頸）	多
  元數(shù)據(jù)與數(shù)據(jù)占比	小	大
  并行讀取效率	低	同一文件有更多的塊分散在不同機器上，讀取并行度更高
  遷移	略慢	單個塊遷移更快
  空間利用率	略低，剩余空間不足一塊大小時會浪費	相對高
  壓縮存儲率	高	低

  論文里有提到：

  Lazy space allocation avoids wasting space due to internal

  fragmentation, perhaps the greatest objection against such

  a large chunksize.

  在寫入前擴充文件空間來實現(xiàn)，但這種方式如何能減少碎片從而避免空間浪費呢？

  按我的理解使用fallocate一次性先預(yù)分配64M的chunk文件空間，更有利用磁盤空間的連續(xù)分配，且提前鎖定磁盤空間，確保寫入時不會出錯。

• 對文件的修改盡量是追加寫，而不是隨機寫

  盡量使用追加寫，一是因為追加寫是順序IO，性能高；二是Google的使用場景多是流式讀取文件，經(jīng)過數(shù)據(jù)分析，然后將中間或最終結(jié)果寫入到新的文件，不需要特別的隨機寫需求。

  另外，追加寫更容易保證寫入操作的原子性，這點我們后面會詳細(xì)講述。

GFS架構(gòu)圖

下面這張架構(gòu)圖，相信大家已經(jīng)看過千百遍，我們還是讓它再一次閃亮登場：

gfs-architecture.jpg

對于絕大部分分布式系統(tǒng)，都需要解決元數(shù)據(jù)和用戶數(shù)據(jù)的存儲，另外還有客戶端讀寫數(shù)據(jù)的SDK這三部分。GFS也不例外，在上圖可以看出：

• GFS master: 存儲元數(shù)據(jù)

• GFS chunkserver: 存儲用戶寫入的數(shù)據(jù)

• GFS client: 使用GFS SDK讀寫數(shù)據(jù)

GFS元數(shù)據(jù)管理

元數(shù)據(jù)分類

• 文件命名空間

  類似于Linux目錄樹的命名空間管理方式。由于對于客戶端來說，它們訪問分布式文件系統(tǒng)和分布本地文件系統(tǒng)最好是沒有任何的差別和感知，因此這種目錄樹式的管理方式應(yīng)該是最自然的。

  目錄樹的每個層次可以設(shè)置自己的屬性，比如chunk復(fù)本數(shù)等。

  目錄樹的每個層次節(jié)點都擁有自己的讀寫鎖，來控制當(dāng)對前目錄的刪除，更改等的并發(fā)操作，以及其子目錄或文件的讀，寫，刪除等并發(fā)操作；

  此元數(shù)據(jù)持久化保存。

• 文件到chunk列表的映射

  記錄每個文件對應(yīng)的chunk列表

  此元數(shù)據(jù)持久化保存。

  gfs-namespace.png

• 每個chunk的所有復(fù)本的位置信息

  此復(fù)本位置信息不持久化保存。

  新的Chunk server啟動時會將自己注冊到Master。Master發(fā)送心跳到各個ChunkServer，ChunkServer上報自己所擁有的chunk給Master。

元數(shù)據(jù)一致性

• 同一時刻，對外提供服務(wù)的Master只有一個節(jié)點；

• 對元數(shù)據(jù)的更改都需要加鎖進行，比如命名空間各節(jié)點上的讀寫鎖；

• 對元數(shù)據(jù)的變更信息已日志的方式記錄到本地，并且同步到其他多臺備份Master節(jié)點后，才返回給客戶端；

• 當(dāng)前Master節(jié)點掛掉后，會迅速切換到熱備的Master；

• 除了備份Master節(jié)點外，還有影子Master，其上面的元數(shù)據(jù)版本略落后于Master。影子Master是個兜底的策略，它確保所有的Master節(jié)點都無法啟動時，影子Master對客戶端提供有限的只讀服務(wù)。

從上面的描述可知，對元數(shù)據(jù)的變更是以變更日志的方式同步到多個Master節(jié)點，然后Master節(jié)點在啟動時重放變更日志，達到與之前的Master節(jié)點一致的狀態(tài)。

Master的兩快

對于Master來說，最重要的是需要兩類快速的操作：

• 客戶端可以從Master處快速獲取到元數(shù)據(jù)

  GFS的作法是將所有的元數(shù)據(jù)都加載到內(nèi)存，前面介紹過的64M大的Chunk塊減少了元數(shù)據(jù)量，讓這個成為可能。

  另外，客戶端通常一次會獲取多個chunk的元數(shù)據(jù)，且后續(xù)的讀寫操作不再與master通信，這大大降低了master負(fù)載，使其可以高效處理過來的請求。

• master啟動快

  master發(fā)生故障轉(zhuǎn)移，新的master需要將所有元數(shù)據(jù)信息盡量快速地加載到內(nèi)存中，以便完成啟動并對外提供服務(wù)。

  前面我們介紹過，master將變更依次持久化到本地磁盤文件。重啟后如果重放所有的變更日志，勢必會很慢。因此master會定期作內(nèi)存元數(shù)據(jù)的checkpoint，這樣重啟后只需要加載最新的checkpoint文件，然后回放此checkpoint后的變更日志即可。

  那加載checkpoint文件會不會很慢呢？Checkpoint 文件以壓縮b-tree的數(shù)據(jù)結(jié)構(gòu)存儲，可以直接映射到內(nèi)存，在用于命名空間查詢時無需額外的解析。

Master的高可用

這部分其實前面已經(jīng)提及到了，從論文上看master分為當(dāng)前可用的master，實時同時變更日志的備份master，準(zhǔn)實時的影子master。

gfs-master.png

常用MetaServer實現(xiàn)方案

通常來說MetaServer至關(guān)重要，meta數(shù)據(jù)的丟失可能直接導(dǎo)致用戶數(shù)據(jù)的丟失。

目前常用的實現(xiàn)方案是MetaServer使用raft協(xié)議等作成AP系統(tǒng)，元數(shù)據(jù)的更改經(jīng)raft模塊后寫入每臺MetaServer的本地存儲，比如RocksDB。

如果集群元數(shù)據(jù)量非常大，可以將MetaServer集群作分組處理，每組MetaServer管理整個集群的一個子域?？蛻舳耸紫冗B接到一個前置服務(wù)，獲取對應(yīng)的MetaServer集群信息。

GFS數(shù)據(jù)讀寫

數(shù)據(jù)寫入

寫入流程圖如下：

GFS-WRITE.png

• GFS支持多個客戶端對同一Chunk的并發(fā)寫入

  客戶端間沒有交互，但是GFS需要保證在各個復(fù)本上寫入的請求順序是一致的，這需要MetaServer來針對當(dāng)前的Chunk上確定一個當(dāng)Chunk。主Chunk來決定到達的并發(fā)寫請求的寫入順序；

  主Chunk由MetaServer來選定，同時賦予一個租約，并通過心跳來續(xù)租，

  然后客戶端要查詢Chunk信息時也就獲取到了主Chunk的相關(guān)信息。

• GFS采取數(shù)據(jù)流和控制流分離的策略

  客戶端寫入一條數(shù)據(jù)時，需要和ChunkServer集群有兩次交互。

  一次是是數(shù)據(jù)流的傳輸，為了盡量減少延遲和充分利用每臺機器的出口帶寬，客戶端將數(shù)據(jù)推送到離其最近的chunk節(jié)點，當(dāng)前chunk節(jié)點再繼續(xù)將數(shù)據(jù)推送到離它最近的節(jié)點，依次類推，直到推送到所有復(fù)本。

  客戶端最終收到推送成功的反饋，然后發(fā)送立即寫入的控制請求到主Chunk。

  由此看到數(shù)據(jù)流和控制流對應(yīng)的chunk有可能不是同一個。

  GFS這樣的數(shù)據(jù)流式推送方式，能充分利用每臺機器的帶寬，且是自帶三復(fù)本“強一致”寫入語義，但量從客戶端算起經(jīng)過了三跳，會導(dǎo)致網(wǎng)絡(luò)延遲增加，而且疊加上數(shù)據(jù)和控制流產(chǎn)生的多次請求，使得這個網(wǎng)絡(luò)延遲進一步增加。

  目前開源系統(tǒng)常用的基于quorum機制的寫入策略有兩類：

  1. 星型寫

     客戶端同時寫三個復(fù)本，只經(jīng)過一跳，延遲小。寫入的一致型，即是否寫入成功由客戶端決定。需要客戶端有較大的出口帶寬。

  2. 主從Y型寫

     三復(fù)本選出一個主，客戶端將寫請求打到主，主同時寫兩個復(fù)本，這樣經(jīng)過兩跳，延遲有所增加，也但客戶端不需要較大的出口帶寬。

• 并發(fā)寫入流程

gfs-multi-write.png

1.  C1,C2,C3,C4分別代表四個不同的客戶端發(fā)送的寫請求，此刻它們在當(dāng)前Chunk的三個復(fù)本上的推送情況如上圖所示，C3和C4已經(jīng)推送到了所有的復(fù)本，并給各自的客戶端返回了推送成功的回應(yīng)；

2.  C3,C4客戶端分別給主Chunk發(fā)送寫入的控制指令；

3.  推測主Chunk為了提高效率批量寫入，可能會緩存積累多個寫入控制指令。比如C3的寫入指令先到，在delay時間內(nèi)如果C4的寫入控制指令也到了，則確定好C3,C4的順序，先寫入本地；

4.  將排序好的寫入指令序列推送給其他復(fù)本，其他復(fù)本在本地寫入成功后，將響應(yīng)返回給主Chunk；

5.  主Chunk將響應(yīng)分別返回到C3,C4兩個客戶端；

6.  如果有部分復(fù)本寫入失敗，則此失敗的信息也會返回到對應(yīng)的客戶端。

主Chunk失效

分為兩種情況：

• 主Chunk宕機

  1. 客戶端的寫入將失敗，重試幾次后客戶端會請求Master獲取新的Chunk信息；

  2. 主Chunk宕機，無法響應(yīng)Master的心跳，Master確定新的主Chunk;

  3. 客戶端獲取到新的Chunk信息繼續(xù)寫。

  這里如里Master繼續(xù)在原Chunk上選取復(fù)本，再短時間內(nèi)復(fù)本數(shù)少一個。Master也可以封印當(dāng)前的Chunk，然后返回給客戶端，要求客戶端創(chuàng)建新的Chunk。

• 主Chunk未宕機，與Master網(wǎng)絡(luò)中斷

  1. 如果當(dāng)前主Chunk和其他復(fù)本間網(wǎng)絡(luò)正常，客戶端可繼續(xù)通過當(dāng)前的主ChunkServer寫入數(shù)據(jù)（此時的寫入數(shù)據(jù)有效），直到主Chunk續(xù)租失敗，此時客戶端與Master通訊，重新獲取Chunk信息（有可能是創(chuàng)建新的Chunk）；

  2. 如果當(dāng)前主Chunk和其他復(fù)本間網(wǎng)絡(luò)中斷，客戶端寫入為失敗，同樣會與Master通訊，重新獲取Chunk信息；

Chunk數(shù)據(jù)一致性

說到數(shù)據(jù)一致性，線性一致性，順序一致性，因果一致性，最終一致性，大家應(yīng)該都是耳熟能詳。

我們來看一下GFS中數(shù)據(jù)一致性的表述：

GFS-FILE-REGION.png

先來解釋兩個概念：

• Defined

  已定義的。意思是說對于一個客戶端來說寫入成功后，從同樣位置讀出的就是它寫入的數(shù)據(jù)；

• Consistent

  一致的。意思是說復(fù)本間相同位置的數(shù)據(jù)完全相同，客戶端無論從讀哪個復(fù)本，讀出的數(shù)據(jù)都是一樣的。

GFS支持多個客戶端并行寫入，又同時支持隨機寫和追加寫，這給上面介紹的“defined”和“consistent”帶來了很多的不確定性。

• 隨機寫

  隨機寫是客戶端提供寫入的offset，寫入位置固定。

  下面我們的闡述都是基于寫入相同位置。

  1. 對于串行寫，隨機寫是一個冪等的動作，即使首次寫入失敗，接下來的重試只要成功，還是寫到相同的位置，因此寫入成功后讀取出來的一定是剛寫入的數(shù)據(jù)，行為是已定義的。

  2. 對于并行寫，A,B兩個客戶端對相同位置的寫入操作會在主Chunk上被排序，這樣兩個寫操作的內(nèi)容會互相覆蓋，那么雖然對A的寫入操作也返回了成功，但它隨后讀取到的可能是B寫入的數(shù)據(jù)。此時的行為是一致的，但是是未定義的。

  3. 還有一種比較極端的情況。由于GFS的Chunk是定長，那么有可能客戶端的一個寫操作要跨兩個Chunk。如果此時并行寫的兩個客戶端都出現(xiàn)這種跨Chunk邊界寫的情況，那么這兩個客戶端的寫入存在都不能保證寫入的已定義。這個本質(zhì)原因是一個寫操作由于Chunk邊界，打破了原子性。

     gfs-split-write.png

上面中客戶端A的數(shù)據(jù)塊1和客戶端B的數(shù)據(jù)塊1并行寫ChunkA的尾部剩余空間，兩個寫入操作經(jīng)主Chunk排序后會疊加覆蓋，假設(shè)結(jié)終寫入了客戶端A的數(shù)據(jù)塊1；同樣的流程，新ChunkB的首部空間最終被寫入的可能是客戶端B的數(shù)據(jù)據(jù)2。如此這般，無論是客戶端A還是客戶端B想要來讀取自己寫入的完整數(shù)據(jù)塊時，讀取到的就都不完全是數(shù)據(jù)寫入的數(shù)據(jù)了。

• 追加寫

  首先需要明確一點，追加寫相比隨機寫不是冪等操作，在重試的過程中可能出現(xiàn)重復(fù)數(shù)據(jù)或空洞。

  1. 對于串行寫，如果沒有重試就寫入成功，則是已定義的，復(fù)本上的數(shù)據(jù)也是一致的。

     如果其中有復(fù)本寫入失敗，重試后成功，則結(jié)果也是已定義的，但復(fù)本局部出現(xiàn)了數(shù)據(jù)不一致的情況。

  gfs-retry.png

如上圖所示，左邊在寫入數(shù)據(jù)3時，復(fù)本1寫入成功，復(fù)本2寫入失敗

然后重試，重試后數(shù)據(jù)3都成功寫入了復(fù)本1和復(fù)本2，且返回客戶端的offset是最后一次都成功寫入后的數(shù)據(jù)3的

Offset，客戶端用此offset可以讀取到數(shù)據(jù)3，行為是已定義的。

但是對于復(fù)本1，寫入了兩次數(shù)據(jù)3，復(fù)本2中間有空洞，出現(xiàn)了不一致的問題。

對于空洞，GFS的處理是寫入特殊的標(biāo)記，比如特殊的crc校驗值，在客戶端讀取時告知客戶端。

對于重復(fù)數(shù)據(jù)，GFS要求客戶端自行處理，比如寫入的數(shù)據(jù)中帶有唯一標(biāo)識，供客戶端去重用。

2.  對于并發(fā)寫，由于追加寫不會發(fā)生跨Chunk的情況(如果當(dāng)前Chunk剩余空間不夠?qū)懭耄瑫魈畛?，然后新?chuàng)建一個Chunk，供當(dāng)有寫入用)，保證了原子性，寫入成功后讀取是已定義的。但是會出現(xiàn)和串行寫失敗重試后出現(xiàn)空洞一樣的問題，導(dǎo)致復(fù)本間數(shù)據(jù)局部不一致。

常見系統(tǒng)多點寫處理

多點并行寫入，會引入不確定性，而這些不確定性對系統(tǒng)的使用者來說也增加了復(fù)雜度。

因此，目前常見的系統(tǒng)，更多地是不支持多點寫，只支持單點寫。

實現(xiàn)上也比較簡單，多個寫者通過搶鎖互斥，搶到鎖的客戶端通過不斷續(xù)租來長期持有鎖，并且提供主動釋放鎖的接口，來避免因持有鎖的客戶端意外掛掉，還需要等租約超時standby的客戶端才能搶到鎖的情況。

復(fù)本選擇策略

復(fù)本位置選擇，遵守兩個大原則：

• 最大化數(shù)據(jù)可靠性和可用性

• 最大化數(shù)網(wǎng)絡(luò)帶寬利用率

這就需要在選擇位置時，需要考慮不同復(fù)本分散到不同機架上，磁盤使用率低于平均磁盤使用率的磁盤被優(yōu)先選中，而且也要避免同一塊磁盤被連續(xù)多次選中，因為新的chunk被分配后，很可能緊接著有大量的數(shù)據(jù)寫入，IO容易成為瓶頸。更細(xì)致的作法是各個ChunkServer上報各個的IO負(fù)載情況，在選擇Chunk位置時，結(jié)合其負(fù)載情況來選擇。

后記

關(guān)于《Google File System》的重讀，我們就先到這里。論文里包含得比這里介紹得要豐富詳實得多，這里算作是拋磚引玉吧。

更多精彩文章，歡迎關(guān)注微信共眾號：程序員Lion