轉：http://blog.csdn.net/boyplayee/archive/2010/02/22/5318092.aspx

谷歌技術“三寶”之一的Google文件系統和Kosmos 文件系統 收藏
    雖然針對大規模分布式存儲系統，Google將推陳出新，推新的理由有很多，如"single-master design,…… but it was certainly unacceptable for latency-sensitive applications, such as video serving."。參考《Google File System II: Dawn of the Multiplying Master Nodes》和《GFS:Evolution on Fast-forward》。但是GFS畢竟為其服務了10年時間，連李開復博士也宣稱每個計算機學生都有必要學學這套系統。

      本篇也一起談談Kosmos文件系統，傳聞Google的兩個共同創始人佩奇和布林有兩個大學同窗，是兩個印度人,名叫Anand Rajaraman和Venky Harinarayan，看到Google獲得巨大成功之后，就動手做了個一個新的搜索引擎CloudStore (原先一直叫Kosmos filesystem，現在搭上了云計算的順風車改了頭銜)。在做這個搜索引擎的過程中，他們實現了一個類似GFS的文件系統KFS(很多理念都從GFS那里搬過來，比如constant monitoring, error detection, fault tolerance, and automatic recovery)。因為GFS的論文只是設計，而KFS是開源的，兩者結合看效果可能比較好。

     首先，看過谷歌工程師寫地這篇《The Google File System》的能不能做下面這道證明題：考慮一個擁有1000個節點的GFS集群，定性(不定量)證明：在有800個節點失效的情況下，剩下的200個節點仍然能夠完成工作，即performance下降的情況下，scalability,reliability,availability等保持良好。

本文想闡釋谷歌文件系統的一些設計理念。

一 架構：

下圖為谷歌文件系統的結構圖，一個GFS集群包含一個主服務器和多個塊服務器, 這是一個單一主服務器模型：

      概括一下塊(chunk)的一些信息：塊尺寸是64MB；文件被分割成固定尺寸的塊，在每個塊創建的時候，服務器分配給它一個不變的、唯一的64位的塊句柄對它進行標識；每個塊都會復制到多個塊服務器上。

      主服務器保存三種主要類型的metadata：文件和塊的命名空間，文件到塊的映射，以及每個塊副本的位置，它通過全局的信息精確確定塊的位置以及進行復制決定。主服務器的主要工作有：主服務器在后臺周期掃貓自己的整個狀態，用來在塊服務器間實現塊的垃圾收集的功能，用來實現塊服務器失效的時復制新副本的功能，用來實現負載均衡的塊移動的功能，以及用來實現統計硬盤使用情況的功能等。

      塊服務器保存著塊，并根據指定的塊句柄和字節區間來讀寫塊數據。

      客戶端不通過主服務器讀寫數據。反之，客戶端向主服務器詢問它應該聯系的塊服務器。客戶端短期緩存這些信息，后續的操作直接跟塊服務器進行。

      讀取流程:首先，利用固定的塊尺寸，客戶端把文件名和程序指定的字節偏移轉換成文件的塊索引。然后，它把文件名和塊索引發送給主服務器。主服務器回答相應的塊句柄和副本們的位置。客戶端用文件名和塊索引作為鍵值緩存這些信息。

      此系統可靠性方面相關的一些設計，下面概要敘述一下，后面會有詳細描述：

      1主服務器不持久化保存塊的位置信息。主服務器在自己啟動以及塊服務器加入集群的時候，詢問塊服務器它所包含的塊的信息，然后定期的心跳信息監控塊服務器的狀態。

      2 名稱空間和文件塊映射的metadata，會用log的方式保存在主服務器的硬盤上的操作日志內，并在遠程的機器內復制一個副本。使用log，可以更新主服務器的狀態，而且不用擔心服務器崩潰帶來的數據不一致的風險。

      3. 主服務器通過重放operation log恢復其文件系統。operation log是metadata唯一的持久化存儲記錄，起到了定義同步操作順序的邏輯時間線的作用。文件和塊及其版本都是唯一和持久地由他們創建時的邏輯時間標識的。進行恢復僅需要最新的checkpoint和相應的日志文件。日志增長到一個特定尺寸的時候，主服務器匯總的狀態為一個checkpoint。

4文件命名空間的修改（例如，文件創建）是原子性的。他們僅受主服務器的控制：命名空間鎖定保證了原子性和正確性；主服務器的操作日志定義了這些操作的全局總順序。在修改操作成功后，部件故障仍可以使數據受到破壞。GFS通過master和chunkserver間定期的handshake，借助校驗和來檢測對數據的破壞。一旦檢測到，就從一個有效的副本盡快重新存儲。只有在GFS檢測前，所有的副本都失效，這個塊才會丟失。

5…………….

二 系統交互

這一節討論客戶機，服務器和塊服務器三者如何交互以實現數據操作，原子化的記錄追加及快照。

2.1 leases and mutation order

Mutations是一個會改變塊內容或者元數據的操作，例如寫入或者記錄追加。每個變更執行在塊的所有副本上。使用leases來保持多個副本間變更順序的一致性，leases機制的設計是為了最小化主服務器的管理負載。由于Master首先grants一個主塊（即副本中的一個塊lease），所以全局的mutation order就形成了：首先由主服務器選擇的lease生成順序決定，然后由lease中主塊分配的序列號決定。再用圖來說明寫入操作的控制流程：

      1客戶機向主服務器詢問哪一個塊服務器保存了當前的lease，以及其它副本的位置。如果沒有一個塊服務器有lease，主服務器就選擇一個副本給它一個lease（沒有被顯示出來）。

      2主服務器回復主塊的標識符以及其他副本的位置。客戶機為了后續的操作緩存這個數據。只有主塊不可用，或者主塊回復說它已經不再擁有lease的時候，客戶機才需要重新跟主服務器聯絡。

      3客戶機把數據推送到所有的副本上。客戶機可以用任意的順序推送。每個塊服務器會把這些數據保存在它的內部LRU緩沖內，直到數據被使用或者過期。通過把數據流和控制流分離，我們可以基于網絡負載狀況對昂貴的數據流進行規劃，以提高性能，而不用去管哪個塊服務器是主塊。

      4所有的副本都被確認已經得到數據后，客戶機發送寫請求到主塊。這個請求標識了早前推送到所有副本的數據。主塊為收到的所有操作分配連續的序列號，這些可能來自不同的客戶機。它依照序列號的順序把這些操作應用到它自己的本地狀態中。

      5主塊把寫請求傳遞到所有的二級副本。每個二級副本依照主塊分配的序列號的順序應用這些操作。

      6所有二級副本回復主塊說明他們已經完成操作。

      7主塊回復客戶機。任何副本產生的錯誤都會報告給客戶機。錯誤的情況下，主塊和一些二級副本可能成功的寫入了數據。（如果主塊寫入失敗，操作就不會被分配序列號，也不會被傳遞。）客戶端請求被確認為失敗，已經修改的區域保持不一致的狀態。我們的客戶機代碼通過重復失敗的操作來處理這樣的錯誤。在完全從頭開始寫入之前，可能會先從步驟3到步驟7進行幾次嘗試。

 2.2 數據流

      數據流和控制流分開。控制流從客戶機到主塊然后再到所有二級副本的同時，數據順序推送到一個精心選擇的管道形式的塊服務器鏈。特點：用IP地址就可以計算出節點的遠近；用在TCP連接上管道化數據傳輸來最小化延遲。

2.3 原子性的記錄追加

      GFS提供了一個原子性的添加操作：record append。在傳統的寫操作中，client指定被寫數據的偏移位置，向同一個區間的并發的寫操作是不連續的：區間有可能包含來自多個client的數據碎片。在record append中， client只是指定數據。GFS在其選定的偏移出將數據至少原子性的加入文件一次，并將偏移返回給client。

在分布式的應用中，不同機器上的許多client可能會同時向一個文件執行添加操作，添加操作被頻繁使用。如果用傳統的write操作，可能需要額外的、復雜的、開銷較大的同步，例如通過分布式鎖管理。在我們的工作量中，這些文件通常以多個生產者單個消費者隊列的方式或包含從多個不同 client的綜合結果。

      Record append和前面講的write操作的控制流差不多，只是在primary上多了一些邏輯判斷。首先，client將數據發送到文件最后一塊的所有副本上。然后向primary發送請求。Primary檢查添加操作是否會導致該塊超過最大的規模（64M）。如果這樣，它將該塊擴充到最大規模，并告訴其它副本做同樣的事，同時通知client該操作需要在下一個塊上重新嘗試。如果記錄滿足最大規模的要求，primary就會將數據添加到它的副本上，并告訴其它的副本在同樣的偏移處寫數據，最后primary向client報告寫操作成功。如果在任何一個副本上record append操作失敗，client將重新嘗試該操作。這時候，同一個塊的副本可能包含不同的數據，因為有的可能復制了全部的數據，有的可能只復制了部分。GFS不能保證所有的副本每個字節都是一樣的。它只保證每個數據作為一個原子單元被寫過至少一次。這個是這樣得出的：操作要是成功，數據必須在所有的副本上的同樣的偏移處被寫過。進一步，從這以后，所有的副本至少和記錄一樣長，所以后續的記錄將被指定到更高的偏移處或者一個不同的塊上，即使另一個副本成了primary。根據一致性保證，成功的record append操作的區間是已定義的。而受到干擾的區間是不一致的。

 2.4快照

      快照操作幾乎在瞬間構造一個文件和目錄樹的副本，同時將正在進行的其他修改操作對它的影響減至最小。

我們使用copy-on-write技術來實現snapshot。當master受到一個snapshot請求時，它首先要撤消將要snapshot的文件上塊上的lease。這使得任何一個向這些塊寫數據的操作都必須和master交互以找到擁有lease的副本。這就給master一個創建這個塊的副本的機會。

副本被撤銷或終止后，master在磁盤上登記執行的操作，然后復制源文件或目錄樹的metadata以對它的內存狀態實施登記的操作。這個新創建的snapshot文件和源文件（其metadata）指向相同的塊（chunk）。

       Snapshot之后，客戶第一次向chunk c寫的時候，它發一個請求給master以找到擁有lease的副本。Master注意到chunk c的引用記數比1大，它延遲對用戶的響應，選擇一個chunk handle C’,然后要求每一有chunk c的副本的chunkserver創建一個塊C’。每個chunkserver在本地創建chunk C’避免了網絡開銷。從這以后和對別的塊的操作沒有什么區別。

3.Mast操作

MASTER執行所有名字空間的操作，除此之外，他還在系統范圍管理數據塊的復制：決定數據塊的放置方案，產生新數據塊并將其備份，和其他系統范圍的操作協同來確保數據備份的完整性，在所有的數據塊服務器之間平衡負載并收回沒有使用的存儲空間。

3.1 名字空間管理和加鎖

      與傳統文件系統不同的是，GFS沒有與每個目錄相關的能列出其所有文件的數據結構，它也不支持別名（unix中的硬連接或符號連接），不管是對文件或是目錄。GFS的名字空間邏輯上是從文件元數據到路徑名映射的一個查用表。

MASTER在執行某個操作前都要獲得一系列鎖，例如，它要對/d1/d2…/dn/leaf執行操作，則它必須獲得/d1，/d1/d2，…， /d1/d2/…/dn的讀鎖，/d1/d2…/dn/leaf的讀鎖或寫鎖（其中leaf可以使文件也可以是目錄）。MASTER操作的并行性和數據的一致性就是通過這些鎖來實現的。

3.2 備份存儲放置策略

一個GFS集群文件系統可能是多層分布的。一般情況下是成千上萬個文件塊服務器分布于不同的機架上，而這些文件塊服務器又被分布于不同機架上的客戶來訪問。因此，不同機架上的兩臺機器之間的通信可能通過一個或多個交換機。數據塊冗余配置策略要達到多個目的：最大的數據可靠性和可用性，最大的網絡帶寬利用率。因此，如果僅僅把數據的拷貝置于不同的機器上很難滿足這兩個要求，必須在不同的機架上進行數據備份。這樣即使整個機架被毀或是掉線，也能確保數據的正常使用。這也使數據傳輸，尤其是讀數據，可以充分利用帶寬，訪問到多個機架，而寫操作，則不得不涉及到更多的機架。

3.3 產生、重復制、重平衡數據塊

      當MASTER產生新的數據塊時，如何放置新數據塊，要考慮如下幾個因素：（1）盡量放置在磁盤利用率低的數據塊服務器上，這樣，慢慢地各服務器的磁盤利用率就會達到平衡。（2）盡量控制在一個服務器上的“新創建”的次數。（3）由于上一小節討論的原因，我們需要把數據塊放置于不同的機架上。

      MASTER在可用的數據塊備份低于用戶設定的數目時需要進行重復制。這種情況源于多種原因：服務器不可用，數據被破壞，磁盤被破壞，或者備份數目被修改。每個被需要重復制的數據塊的優先級根據以下幾項確定：第一是現在的數目距目標的距離，對于能阻塞用戶程序的數據塊，我們也提高它的優先級。最后， MASTER按照產生數據塊的原則復制數據塊，并把它們放到不同的機架內的服務器上。

       MASTER周期性的平衡各服務器上的負載：它檢查chunk分布和負載平衡，通過這種方式來填充一個新的服務器而不是把其他的內容統統放置到它上面帶來大量的寫數據。數據塊放置的原則與上面討論的相同，此外，MASTER還決定哪些數據塊要被移除，原則上它會清除那些空閑空間低于平均值的那些服務器。

3.4 垃圾收集

      在一個文件被刪除之后，GFS并不立即收回磁盤空間，而是等到垃圾收集程序在文件和數據塊級的的檢查中收回。

當一個文件被應用程序刪除之后，MASTER會立即記錄下這些變化，但文件所占用的資源卻不會被立即收回，而是重新給文件命了一個隱藏的名字，并附上了刪除的時間戳。在MASTER定期檢查名字空間時，它刪除超過三天（可以設定）的隱藏的文件。在此之前，可以以一個新的名字來讀文件，還可以以前的名字恢復。當隱藏的文件在名字空間中被刪除以后，它在內存中的元數據即被擦除，這就有效地切斷了他和所有數據塊的聯系。

在一個相似的定期的名字空間檢查中，MASTER確認孤兒數據塊（不屬于任何文件）并擦除它的元數據，在和MASTER的心跳信息交換中，每個服務器報告他所擁有的數據塊，MASTER返回元數據不在內存的數據塊，服務器即可以刪除這些數據塊。

3.5 過時數據的探測

      在數據更新時如果服務器停機了，那么他所保存的數據備份就會過時。對每個數據塊，MASTER設置了一個版本號來區別更新過的數據塊和過時的數據塊。

      當MASTER授權一個新的lease時，他會增加數據塊的版本號并會通知更新數據備份。MASTER和備份都會記錄下當前的版本號，如果一個備份當時不可用，那么他的版本號不可能提高，當ChunkServer重新啟動并向MASTER報告他的數據塊集時，MASTER就會發現過時的數據。

      MASTER在定期的垃圾收集程序中清除過時的備份，在此以前，處于效率考慮，在各客戶及英大使，他會認為根本不存在過時的數據。作為另一個安全措施， MASTER在給客戶及關于數據塊的應答或是另外一個讀取數據的服務器數據是都會帶上版本信息，在操作前客戶機和服務器會驗證版本信息以確保得到的是最新的數據。

4、容錯和診斷

4.1 高可靠性

4.1.1 快速恢復

不管如何終止服務，MASTER和數據塊服務器都會在幾秒鐘內恢復狀態和運行。實際上，我們不對正常終止和不正常終止進行區分，服務器進程都會被切斷而終止。客戶機和其他的服務器會經歷一個小小的中斷，然后它們的特定請求超時，重新連接重啟的服務器，重新請求。

4.1.2 數據塊備份

如上文所討論的，每個數據塊都會被備份到放到不同機架上的不同服務器上。對不同的名字空間，用戶可以設置不同的備份級別。在數據塊服務器掉線或是數據被破壞時，MASTER會按照需要來復制數據塊。

4.1.3 MASTER備份

為確保可靠性，MASTER的狀態、操作記錄和檢查點都在多臺機器上進行了備份。一個操作只有在數據塊服務器硬盤上刷新并被記錄在MASTER和其備份的上之后才算是成功的。如果MASTER或是硬盤失敗，系統監視器會發現并通過改變域名啟動它的一個備份機，而客戶機則僅僅是使用規范的名稱來訪問，并不會發現MASTER的改變。

4.2 數據完整性

每個數據塊服務器都利用校驗和來檢驗存儲數據的完整性。原因：每個服務器隨時都有發生崩潰的可能性，并且在兩個服務器間比較數據塊也是不現實的，同時，在兩臺服務器間拷貝數據并不能保證數據的一致性。

每個Chunk按64kB的大小分成塊，每個塊有32位的校驗和，校驗和和日志存儲在一起，和用戶數據分開。

在讀數據時，服務器首先檢查與被讀內容相關部分的校驗和，因此，服務器不會傳播錯誤的數據。如果所檢查的內容和校驗和不符，服務器就會給數據請求者返回一個錯誤的信息，并把這個情況報告給MASTER。客戶機就會讀其他的服務器來獲取數據，而MASTER則會從其他的拷貝來復制數據，等到一個新的拷貝完成時，MASTER就會通知報告錯誤的服務器刪除出錯的數據塊。

附加寫數據時的校驗和計算優化了，因為這是主要的寫操作。我們只是更新增加部分的校驗和，即使末尾部分的校驗和數據已被損壞而我們沒有檢查出來，新的校驗和與數據會不相符，這種沖突在下次使用時將會被檢查出來。

相反，如果是覆蓋現有數據的寫，在寫以前，我們必須檢查第一和最后一個數據塊，然后才能執行寫操作，最后計算和記錄校驗和。如果我們在覆蓋以前不先檢查首位數據塊，計算出的校驗和則會因為沒被覆蓋的數據而產生錯誤。

在空閑時間，服務器會檢查不活躍的數據塊的校驗和，這樣可以檢查出不經常讀的數據的錯誤。一旦錯誤被檢查出來，服務器會拷貝一個正確的數據塊來代替錯誤的。

4.3 診斷工具

廣泛而細致的診斷日志以微小的代價換取了在問題隔離、診斷、性能分析方面起到了重大的作用。GFS服務器用日志來記錄顯著的事件（例如服務器停機和啟動）和遠程的應答。遠程日志記錄機器之間的請求和應答，通過收集不同機器上的日志記錄，并對它們進行分析恢復，我們可以完整地重現活動的場景，并用此來進行錯誤分析。

以下是Kosmos filesystem的一些特性：

自動存儲擴充（添加新的chunckserver,系統自動感知）

有效性（復制機制保證文件有效性，一般文件會被以三種方式存儲，當其中一個chunkserver出現錯誤的時候，不會影響         數據的讀取）

文件復制粒度：可以配置文件復制的粒度，最大可以被復制64份

還原復制：當其中一個Chunckserver出現故障的時候，Metaserver會強制使用其他的chunckserver

負載平衡（系統周期地檢查chunkservers的磁盤利用，并重新平衡chunkservers的磁盤利用，HDFS現在還沒有支持）

數據完整性（當要讀取數據時檢查數據的完整性，如果檢驗出錯使用另外的備份覆蓋當前的數據）

文件寫入：當一個應用程序創建了一個文件，這個文件名會被立刻寫入文件系統，但為了性能，寫入的數據會被緩存在kfs客戶端.并且周期性的從緩存中把數據更新到chunkserver中。當然，應用程序也可以強制把數據更新到服務器上。一旦數據被更新到服務器，就可以被有效的讀取了。

契約（使用契約來保證Client緩存的數據和文件系統中的文件保持一致性）

支持FUSE（在linux系統下，可以通過Fuse 映射一個文件夾，從而可以很方便的讀取kfs的文件）

支持C++,Java,Python方式的調用

提供了豐富的工具程序，如kfsshell,cp2kfs等

提供了啟動和停止服務的腳本

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/boyplayee/archive/2010/02/22/5318092.aspx