英文原文：The Google File System，編譯：ImportNew - 儲曉穎   新浪微博：@瘋狂編碼中的xiaoY

　　【譯者預讀】

　　GFS這三個字母無需過多修飾，《Google File System》的論文也早有譯版。但是這不妨礙我們加點批注、重溫經典，并結合上篇Haystack的文章，將GFS、TFS、Haystack進行一次全方位的對比，一窺各巨頭的架構師們是如何權衡利弊、各取所需。

　　1. 介紹

　　我們設計和實現了GFS來滿足Google與日俱增的數據處理需求。與傳統的分布式文件系統一樣，GFS著眼在幾個重要的目標，比如性能、可伸縮性、可靠性和可用性。不過它也會優先考慮我們自身應用場景的特征和技術環境，所以與早先一些文件系統的設計思想還是有諸多不同。我們取傳統方案之精華、根據自身需求做了大膽的設計創新。在我們的場景中：

　　首先，組件故障是常態而不是異常。文件系統包含成百上千的存儲機器，而且是廉價的普通機器，被大量的客戶端機器訪問。這樣的機器質量和數量導致任何時間點都可能有一些機器不可用，甚至無法從當前故障中恢復。導致故障的原因很多，比如應用bug、操作系統bug、人為錯誤，以及磁盤、內存、連接器、網絡等硬件故障，甚至是電力供應。因此，持續監控、錯誤偵測、故障容忍和自動恢復必須全面覆蓋整個系統。

　　其次，用傳統視角來看，我們要處理的文件很多都是巨型的，好幾GB的文件也很常見。通常情況下每個文件中包含了多個應用對象，比如web文檔。面對快速增長、TB級別、包含數十億對象的數據集合，如果按數十億個KB級別的小文件來管理，即使文件系統能支持，也是非常不明智的。因此，一些設計上的假設和參數，比如I/O操作和塊大小，需要被重新審視。

　　第三，大部分文件發生變化是通過append新數據，而不是覆蓋、重寫已有的數據，隨機寫幾乎不存在。被寫入時，文件變成只讀，而且通常只能是順序讀。很多數據場景都符合這些特征。比如文件組成大型的庫，使用數據分析程序對其掃描。比如由運行中的程序持續生成的數據流。比如歸檔數據。還可能是分布式計算的中間結果，在一臺機器上產生、然后在另一臺處理。這些數據場景都是由制造者持續增量的產生新數據，再由消費者讀取處理。在這種模式下append是性能優化和保證原子性的焦點。然而在客戶端緩存數據塊沒有太大意義。

　　第四，向應用提供類似文件系統API，增加了我們的靈活性。松弛的一致性模型設計也極大的簡化了API，不會給應用程序強加繁重負擔。我們將介紹一個原子的append操作，多客戶端能并發的對一個文件執行append，不需考慮任何同步。

　　當前我們部署了多個GFS集群，服務不同的應用。最大的擁有超過1000個存儲節點，提供超過300TB的磁盤存儲，被成百上千個客戶端機器大量訪問。

　　2 設計概覽

　　2.1 假設

　　設計GFS過程中我們做了很多的設計假設，它們既意味著挑戰，也帶來了機遇。現在我們詳細描述下這些假設。

• 系統是構建在很多廉價的、普通的組件上，組件會經常發生故障。它必須不間斷監控自己、偵測錯誤，能夠容錯和快速恢復。
• 系統存儲了適當數量的大型文件，我們預期幾百萬個，每個通常是100MB或者更大，即使是GB級別的文件也需要高效管理。也支持小文件，但是不需要著重優化。
• 系統主要面對兩種讀操作：大型流式讀和小型隨機讀。在大型流式讀中，單個操作會讀取幾百KB，也可以達到1MB或更多。相同客戶端發起的連續操作通常是在一個文件讀取一個連續的范圍。小型隨機讀通常在特定的偏移位置上讀取幾KB。重視性能的應用程序通常會將它們的小型讀批量打包、組織排序，能顯著的提升性能。
• 也會面對大型的、連續的寫，將數據append到文件。append數據的大小與一次讀操作差不多。一旦寫入，幾乎不會被修改。不過在文件特定位置的小型寫也是支持的，但沒有著重優化。
• 系統必須保證多客戶端對相同文件并發append的高效和原子性。我們的文件通常用于制造者消費者隊列或者多路合并。幾百個機器運行的制造者，將并發的append到一個文件。用最小的同步代價實現原子性是關鍵所在。文件被append時也可能出現并發的讀。
• 持久穩定的帶寬比低延遲更重要。我們更注重能夠持續的、大批量的、高速度的處理海量數據，對某一次讀寫操作的回復時間要求沒那么嚴格。

　　2.2 接口

　　GFS提供了一個非常親切的文件系統接口，盡管它沒有全量實現標準的POSIX API。像在本地磁盤中一樣，GFS按層級目錄來組織文件，一個文件路徑（path）能作為一個文件的唯一ID。我們支持常規文件操作，比如create、delete、open、close、read和write。

　　除了常規操作，GFS還提供快照和record append操作。快照可以用很低的花費為一個文件或者整個目錄樹創建一個副本。record append允許多個客戶端并發的append數據到同一個文件，而且保證它們的原子性。這對于實現多路合并、制造消費者隊列非常有用，大量的客戶端能同時的append，也不用要考慮鎖等同步問題。這些特性對于構建大型分布式應用是無價之寶。快照和record append將在章節3.4、3.3討論。

　　2.3 架構

　　一個GFS集群包含單個master和多個chunkserver，被多個客戶端訪問，如圖1所示。圖1中各組件都是某臺普通Linux機器上運行在用戶級別的一個進程。在同一臺機器上一起運行chunkserver和客戶端也很容易，只要機器資源允許。

　　文件被劃分為固定大小的chunk。每個chunk在創建時會被分配一個chunk句柄，chunk句柄是一個不變的、全局唯一的64位的ID。chunkserver在本地磁盤上將chunk存儲為Linux文件，按照chunk句柄和字節范圍來讀寫chunk數據。為了可靠性，每個chunk被復制到多個chunkserver上，默認是3份，用戶能為不同命名空間的文件配置不同的復制級別。

　　master維護所有的文件系統元數據。包括命名空間，訪問控制信息，從文件到chunk的映射，和chunk位置。它也負責主導一些影響整個系統的活動，比如chunk租賃管理、孤兒chunk的垃圾回收，以及chunkserver之間的chunk遷移。master會周期性的與每臺chunkserver通訊，使用心跳消息，以發號施令或者收集chunkserver狀態。

　　每個應用程序會引用GFS的客戶端API，此API與正規文件系統API相似，并且負責與master和chunkserver通訊，基于應用的行為來讀寫數據。客戶端只在獲取元數據時與master交互，真實的數據操作會直接發至chunkserver。我們不需提供嚴格完整的POSIX API，因此不需要hook到Linux的vnode層面。

　　客戶端和chunkserver都不會緩存文件數據。客戶端緩存文件數據收益很小，因為大部分應用通常會順序掃描大型文件，緩存重用率不高，要么就是工作集合太大緩存很困難。沒有緩存簡化了客戶端和整個系統，排除緩存一致性問題。（但是客戶端會緩存元數據。）chunkserver不需要緩存文件數據因為chunk被存儲為本地文件，Linux提供的OS層面的buffer緩存已經保存了頻繁訪問的文件。

　　2.4 單一Master

　　單一master大大的簡化了我們的設計，單一master能夠放心使用全局策略執行復雜的chunk布置、制定復制決策等。然而，我們必須在讀寫過程中盡量減少對它的依賴，它才不會成為一個瓶頸。客戶端從不通過master讀寫文件，它只會詢問master自己應該訪問哪個chunkserver。客戶端會緩存這個信息一段時間，隨后的很多操作即可以復用此緩存，與chunkserver直接交互。

　　我們利用圖1來展示一個簡單讀操作的交互過程。首先，使用固定的chunk size，客戶端將應用程序指定的文件名和字節偏移量翻譯為一個GFS文件及內部chunk序號，隨后將它們作為參數，發送請求到master。master找到對應的chunk句柄和副本位置，回復給客戶端。客戶端緩存這些信息，使用GFS文件名+chunk序號作為key。

　　客戶端然后發送一個讀請求到其中一個副本，很可能是最近的那個。請求中指定了chunk句柄以及在此chunk中讀取的字節范圍。后面對相同chunk的讀不再與master交互，直到客戶端緩存信息過期或者文件被重新打開。事實上，客戶端通常會在一個與master的請求中順帶多索要一些其他chunk的信息，而且master也可能將客戶端索要chunk后面緊跟的其他chunk信息主動回復回去。這些額外的信息避免了未來可能發生的一些client-master交互，幾乎不會導致額外的花費。

　　2.5 chunk size

　　chunk size是其中一個關鍵的設計參數。我們選擇了64MB，這是比典型的文件系統的塊大多了。每個chunk副本在chunkserver上被存儲為一個普通的Linux文件，只在必要的時候才去擴展。懶惰的空間分配避免了內部碎片導致的空間浪費，chunk size越大，碎片的威脅就越大。

　　chunk size較大時可以提供幾種重要的優勢。首先，它減少了客戶端與master的交互，因為對同一個chunk的讀寫僅需要對master執行一次初始請求以獲取chunk位置信息。在我們的應用場景中大部分應用會順序的讀寫大型文件，chunk size較大（chunk數量就較少）能有效的降低與master的交互次數。對于小型的隨機讀，即使整個數據集合達到TB級別，客戶端也能舒服的緩存所有的chunk位置信息（因為chunk size大，chunk數量小）。其次，既然用戶面對的是較大的chunk，它更可能愿意在同一個大chunk上執行很多的操作（而不是操作非常多的小chunk），這樣就可以對同一個chunkserver保持長期的TCP連接以降低網絡負載。第三，它減少了master上元數據的大小，這允許我們放心的在內存緩存元數據，章節2.6.1會討論繼而帶來的各種好處。

　　不過chunk size如果很大，即使使用懶惰的空間分配，也有它的缺點。一個小文件包含chunk數量較少，可能只有一個。在chunkserver上這些chunk可能變成熱點，因為很多客戶端會訪問相同的文件（如果chunk size較小，那小文件也會包含很多chunk，資源競爭可以分擔到各個小chunk上，就可以緩解熱點）。不過實際上熱點沒有導致太多問題，因為我們的應用大部分都是連續的讀取很大的文件，包含很多chunk（即使chunk size較大）。

　　然而，熱點確實曾經導致過問題，當GFS最初被用在批量隊列系統時：用戶將一個可執行程序寫入GFS，它只占一個chunk，然后幾百臺機器同時啟動，請求此可執行程序。存儲此可執行文件的chunkserver在過多的并發請求下負載較重。我們通過提高它的復制級別解決了這個問題（更多冗余，分擔壓力），并且建議該系統交錯安排啟動時間。一個潛在的長期解決方案是允許客戶端從其他客戶端讀取數據（P2P模式~）。

　　2.6 元數據

　　master主要存儲三種類型的元數據：文件和chunk的命名空間，從文件到chunk的映射，每個chunk副本的位置。所有的元數據被保存在master的內存中。前兩種也會持久化保存，通過記錄操作日志，存儲在master的本地磁盤并且復制到遠程機器。使用操作日志允許我們更簡單可靠的更新master狀態，不會因為master的當機導致數據不一致。master不會持久化存儲chunk位置，相反，master會在啟動時詢問每個chunkserver以獲取它們各自的chunk位置信息，新chunkserver加入集群時也是如此。

　　2.6.1 內存中數據結構

　　因為元數據存儲在內存中，master可以很快執行元數據操作。而且可以簡單高效的在后臺周期性掃描整個元數據狀態。周期性的掃描作用很多，有些用于實現chunk垃圾回收，有些用于chunkserver故障導致的重新復制，以及為了均衡各機器負載與磁盤使用率而執行的chunk遷移。章節4.3和4.4將討論其細節。

　　這么依賴內存不免讓人有些顧慮，隨著chunk的數量和今后整體容量的增長，整個系統將受限于master有多少內存。不過實際上這不是一個很嚴重的限制。每個64MB的chunk，master為其維護少于64byte的元數據。大部分chunk是填充滿數據的，因為大部分文件包含很多chunk，只有少數可能只填充了部分。同樣的，對于文件命名空間數據，每個文件只能占用少于64byte，文件名稱會使用前綴壓縮緊密的存儲。

　　如果整個文件系統真的擴展到非常大的規模，給master添點內存條、換臺好機器scale up一下也是值得的。為了單一master+內存中數據結構所帶來的簡化、可靠性、性能和彈性，咱豁出去了。

　　2.6.2 Chunk位置

　　master不會持久化的保存哪個chunkserver有哪些chunk副本。它只是在自己啟動時拉取chunkserver上的信息（隨后也會周期性的執行拉取）。master能保證它自己的信息時刻都是最新的，因為它控制了所有的chunk布置操作，并用常規心跳消息監控chunkserver狀態。

　　我們最初嘗試在master持久化保存chunk位置信息，但是后來發現這樣太麻煩，每當chunkserver加入或者離開集群、改變名稱、故障、重啟等等時候就要保持master信息的同步。一般集群都會有幾百臺服務器，這些事件經常發生。

　　話說回來，只有chunkserver自己才對它磁盤上存了哪些chunk有最終話語權。沒理由在master上費盡心機的維護一個一致性視圖，chunkserver上發生的一個錯誤就可能導致chunk莫名消失（比如一個磁盤可能失效）或者運維人員可能重命名一個chunkserver等等。

　　2.6.3 操作日志

　　操作日志是對重要元數據變更的歷史記錄。它是GFS的核心之一。不僅因為它是元數據唯一的持久化記錄，而且它還要承擔一個邏輯上的時間標準，為并發的操作定義順序。各文件、chunk、以及它們的版本（見章節4.5），都會根據它們創建時的邏輯時間被唯一的、永恒的標識。

　　既然操作日志這么重要，我們必須可靠的存儲它，而且直至元數據更新被持久化完成（記錄操作日志）之后，才能讓變化對客戶端可見。否則，我們有可能失去整個文件系統或者最近的客戶端操作，即使chunkserver沒有任何問題（元數據丟了或錯了，chunkserver沒問題也變得有問題了）。因此，我們將它復制到多個遠程機器，直到日志記錄被flush到本地磁盤以及遠程機器之后才會回復客戶端。master會捆綁多個日志記錄，一起flush，以減少flush和復制對整個系統吞吐量的沖擊。

　　master可以通過重放操作日志來恢復它的元數據狀態。為了最小化master的啟動時間，日志不能太多（多了重放就需要很久）。所以master會在適當的時候執行“存檔”，每當日志增長超過一個特定的大小就會執行存檔。所以它不需要從零開始回放日志，僅需要從本地磁盤裝載最近的存檔，并回放存檔之后發生的有限數量的日志。存檔是一個緊密的類B樹結構，它能直接映射到內存，不用額外的解析。通過這些手段可以加速恢復和改進可用性。

　　因為構建一個存檔會消耗點時間，master的內部狀態做了比較精細的結構化設計，創建一個新的存檔不會延緩持續到來的請求。master可以快速切換到一個新的日志文件，在另一個后臺線程中創建存檔。這個新存檔能體現切換之前所有的變異結果。即使一個有幾百萬文件的集群，創建存檔也可以在短時間完成。結束時，它也會寫入本地和遠程的磁盤。

　　恢復元數據時，僅僅需要最后完成的存檔和其后產生的日志。老的存檔和日志文件能被自由刪除，不過我們保險起見不會隨意刪除。在存檔期間如果發生故障（存檔文件爛尾了）也不會影響正確性，因為恢復代碼能偵測和跳過未完成的存檔。

　　2.7 一致性模型

　　GFS松弛的一致性模型能很好的支持我們高度分布式的應用，而且實現起來非常簡單高效。我們現在討論GFS的一致性保證。

　　2.7.1 GFS的一致性保證

　　文件命名空間變化（比如文件創建）是原子的，只有master能處理此種操作：master中提供了命名空間的鎖機制，保證了原子性的和正確性（章節4.1）；master的操作日志為這些操作定義了一個全局統一的順序（章節2.6.3）

　　各種數據變異在不斷發生，被它們改變的文件區域處于什么狀態？這取決于變異是否成功了、有沒有并發變異等各種因素。表1列出了所有可能的結果。對于文件區域A，如果所有客戶端從任何副本上讀到的數據都是相同的，那A就是一致的。如果A是一致的，并且客戶端可以看到變異寫入的完整數據，那A就是defined。當一個變異成功了、沒有受到并發寫的干擾，它寫入的區域將會是defined（也是一致的）：所有客戶端都能看到這個變異寫入的完整數據。對同個區域的多個并發變異成功寫入，此區域是一致的，但可能是undefined：所有客戶端看到相同的數據，但是它可能不會反應任何一個變異寫的東西，可能是多個變異混雜的碎片。一個失敗的變異導致區域不一致（也是undefined）：不同客戶端可能看到不同的數據在不同的時間點。下面描述我們的應用程序如何區分defined區域和undefined區域。

　　數據變異可能是寫操作或者record append。寫操作導致數據被寫入一個用戶指定的文件偏移。而record append導致數據（record）被原子的寫入GFS選擇的某個偏移（正常情況下是文件末尾，見章節3.3），GFS選擇的偏移被返回給客戶端，其代表了此record所在的defined區域的起始偏移量。另外，某些異常情況可能會導致GFS在區域之間插入了padding或者重復的record。他們占據的區域可認為是不一致的，不過數據量不大。

　　如果一系列變異都成功寫入了，GFS保證發生變異的文件區域是defined的，并完整的包含最后一個變異。GFS通過兩點來實現：(a) chunk的所有副本按相同的順序來實施變異（章節3.1）；(b) 使用chunk版本數來偵測任何舊副本，副本變舊可能是因為它發生過故障、錯過了變異（章節4.5）。執行變異過程時將跳過舊的副本，客戶端調用master獲取chunk位置時也不會返回舊副本。GFS會盡早的通過垃圾回收處理掉舊的副本。

　　因為客戶端緩存了chunk位置，所以它們可能向舊副本發起讀請求。不過緩存項有超時機制，文件重新打開時也會更新。而且，我們大部分的文件是append-only的，這種情況下舊副本最壞只是無法返回數據（append-only意味著只增不減也不改，版本舊只意味著會丟數據、少數據），而不會返回過期的、錯誤的數據。一旦客戶端與master聯系，它將立刻得到最新的chunk位置（不包含舊副本）。

　　在一個變異成功寫入很久之后，組件的故障仍然可能腐化、破壞數據。GFS中，master和所有chunkserver之間會持續handshake通訊并交換信息，借此master可以識別故障的chunkserver并且通過檢查checksum偵測數據腐化（章節5.2）。一旦發現此問題，會盡快執行一個restore，從合法的副本復制合法數據替代腐化副本（章節4.3）。一個chunk也可能發生不可逆的丟失，那就是在GFS反應過來采取措施之前，所有副本都被丟失。通常GFS在分鐘內就能反應。即使出現這種天災，chunk也只是變得不可用，而不會腐化：應用收到清晰的錯誤而不是錯誤的數據。

　　【譯者注】一致性的問題介紹起來難免晦澀枯燥，下面譯者用一些比較淺顯的例子來解釋GFS中的一致、不一致、defined、undefined四種狀態。

　　讀者可以想象這樣一個場景，某人和他老婆共用同一個Facebook賬號，同時登陸，同時看到某張照片，他希望將其順時針旋轉90度，他老婆希望將其逆時針旋轉90度。兩人同時點了修改按鈕，Facebook應該聽誰的？俗話說意見相同聽老公的，意見不同聽老婆的。但是Facebook不懂這個算法，當他們重新打開頁面時可能會：1. 都看到圖片順時針旋轉了90度；2. 都看到圖片逆時針旋轉了90度；3. 其他情況。對于1、2兩種情況，都是可以接受的，小夫妻若來投訴那只能如實相告讓他們自己回去猜拳，不關Facebook的事兒。因為1、2既滿足一致性（兩人在并發修改發生后都一直看到一致相同的內容），又滿足defined（內容是其中一人寫入的完整數據）。對于3會有哪些其他情況呢？如果這事兒發生在單臺電腦的本地硬盤（相當于兩人同時打開一個圖片軟件、編輯同一個圖片、然后并發提交保存），若不加鎖讓其串行，則可能導致數據碎片，以簡單的代碼為例：

File file = new File("D:/temp.txt");
FileOutputStream fos1 = new FileOutputStream(file);
FileOutputStream fos2 = new FileOutputStream(file);
fos1.write('1');
fos1.write('2');
fos1.write('3');
fos2.write('a');
fos2.write('b');
fos2.write('c');
fos1.close();
fos2.close();

　　這樣一段代碼可以保證temp.txt的內容是“abc”（fos2寫入的字節流完全覆蓋了fos1），fos2寫入是完全的，也就是defined。而寫入字節流是一個持續過程，不是原子的，如果在多線程環境下則可能因為線程調度、I/O中斷等因素導致代碼的執行順序交錯，形成這樣的效果：

File file = new File("D:/temp.txt");
FileOutputStream fos1 = new FileOutputStream(file);
FileOutputStream fos2 = new FileOutputStream(file);
fos1.write('1');
fos2.write('a');
fos2.write('b');
fos1.write('2');
fos1.write('3');
fos2.write('c');
fos1.close();
fos2.close();

　　這段代碼導致temp.txt的內容變成了“a2c”，它不是fos1的寫入也不是fos2的寫入，它是碎片的組合，這就是undefined狀態。還有更糟的情況，這種情況在單臺電腦本地硬盤不會出現，而會在分布式文件系統上出現：分布式文件系統都有冗余備份，fos1和fos2的寫入需要在每個副本上都執行，而在每個副本上會因為各自的線程調度、I/O中斷導致交錯的情況不一、順序不一，于是出現了副本數據不一致的情況（不僅有a2c，還可能是12c、1b3等等），在查詢時由于會隨機選擇副本，于是導致多個查詢可能看到各種不一致的數據。這就是既不一致又undefined的情況。在分布式文件系統上還有另一種情況，在各副本上fos1和fos2都沒有交錯產生碎片，但是它們整體順序不一致，一個副本產出了123，另一個產出了abc，這種也是不一致的異常情況。

　　如何解決上述問題呢？比較可行的方案就是串行化，按順序執行，fos1寫完了才輪到fos2。不過即使如此也不能完全避免一些令人不悅的現象：比如fos1要寫入的是“12345”，fos2要寫入的是“abc”，即使串行，最后也會產出“abc45”。不過對于這種現象，只能認為是外界需求使然，不是文件系統能解決的，GFS也不會把它當做碎片，而認為它是defined。在分布式環境下，不僅要保證每個副本串行執行變異，還要保證串行的順序是一致的，GFS的對策就是后文中的租賃機制。這樣還不夠，還要謹防某個副本因為機器故障而執行異常，GFS的對策是版本偵測機制，利用版本偵測踢除異常的副本。

　　2.7.2 對應用的啟示

　　在使用GFS時，應用如果希望達到良好的一致性效果，需要稍作考慮以配合GFS的松弛一致性模型。但GFS的要求并不高，而且它要求的事情一般你都會去做（為了某些其他的目的）：比如GFS希望應用使用append寫而不是覆蓋重寫，以及一些自我檢查、鑒定和驗證的能力。

　　無論你面對GFS還是普通的本地文件API（比如FileInputStream、FileOutputStream），有些一致性問題你都要去考慮。當一個文件正在被寫時，它依然可以被另一個線程讀，寫入磁盤不是一瞬間的事情，當然有可能讀到沒有寫入完全的數據（可以理解為上述的undefined情況，你只看到了碎片沒有看到完整寫入的內容），這種情況GFS不會幫你解決（它是按照標準文件API來要求自己的，標準文件API也沒有幫你解決這種問題）。比較嚴謹的程序會使用各種方法來避免此問題，比如先寫入臨時文件，寫入結束時才原子的重命名文件，此時才對讀線程可見。或者在寫入過程中不斷記錄寫入完成量，稱之為checkpoint，讀線程不會隨意讀文件的任何位置，它會判斷checkpoint（哪個偏移之前的數據是寫入完全的，也就是defined），checkpoint甚至也可以像GFS一樣做應用級別的checksum。這些措施都可以幫助reader只讀取到defined區域。

　　還有這種情況：你正在寫入一個文件，將新數據append到文件末尾，還沒結束時程序異常或者機器故障了，于是你必須重試，但是之前那次append可能已經寫入了部分數據，這部分數據也是undefined，也不希望讓reader讀到。無論在本地磁盤還是在GFS上都要面臨這種問題。不過這一點上GFS提供了一些有效的幫助。在GFS里，剛才那種情況可能會導致兩種異常，一是沒有寫入完全的padding，二是重復的數據（GFS有冗余副本，寫入數據時任一副本故障會導致所有副本都重試，這就可能導致正常的副本上不止寫入一次）。對于padding，GFS提供了checksum機制，讀取時通過簡單的核查即可跳過不合法的padding。不過對于重復，應用如果不能容忍的話最好能加強自身的冪等性檢查，比如當你將大量應用實體寫入文件時，實體可以包含ID，讀取實體進行業務處理時能通過ID的冪等性檢查避免重復處理。

　　GFS雖然沒有直接在系統層面解決上述難以避免的一致性問題，但是上面提到的解決方案都會作為共享代碼庫供大家使用。

　　3 系統交互

　　在GFS的架構設計中，我們會竭盡所能的減少所有操作對master的依賴（因為架構上的犧牲權衡，master是個理論上的單點）。在這個背景下，下面將描述客戶端、master、chunkserver之間是如何交互，最終實現了各種數據變異、原子的record append、快照等特性。

　　3.1 租賃和變異順序

　　變異可以理解為一種操作，此操作會改變chunk的數據內容或者元數據，比如一個寫操作或者一個append操作。對chunk的任何變異都需要實施到此chunk的各個副本上。我們提出了一種“租賃”機制，來維護一個跨副本的一致性變異順序。master會在chunk各副本中選擇一個，授予其租賃權，此副本稱之為首要副本，其他的稱之為次級副本。首要副本負責為chunk的所有變異排出一個嚴格的順序。所有副本在實施變異時都必須遵循此順序。因此，全局統一的變異過程可以理解為：首先由master選出首要和次級副本；首要副本為這些變異制定實施序號；首要和次級副本內嚴格按首要副本制定的序號實施變異。

　　租賃機制需要盡量減少對master產生的負載。一個租賃初始的超時時間為60秒。然而只要chunk正在實施變異，首要副本能向master申請連任，一般都會成功。master和所有chunkserver之間會持續的交換心跳消息，租賃的授予、請求連任等請求都是在這個過程中完成。master有時候會嘗試撤回一個還沒過期的租賃（比如要重命名一個文件，master希望暫停所有對其實施的變異）。即使master與首要副本失去通訊，它也能保證在老租賃過期后安全的選出一個新的首要副本。

　　圖2描述了具體的控制流程，其中步驟的解釋如下：
　　1. 客戶端要對某chunk執行操作，它詢問master哪個chunkserver持有其租賃以及各副本的位置信息。如果沒有任何人拿到租賃，master選擇一個副本授予其租賃（此時不會去通知這個副本）。
　　2. master將首要者、副本位置信息回復到客戶端。客戶端緩存這些數據以便未來重用，這樣它僅需要在當前首要副本無法訪問或者卸任時去再次聯系master。
　　3. 客戶端推送數據到所有的副本。只是推送，不會實施，只是在各chunkserver上將數據準備好，推送的順序也與控制流無關。每個副本所在的chunkserver將數據存儲在一個內部的LRU的緩沖中，直到數據被使用或者過期。通過將數據流和控制流解耦，我們能有效的改進性能，實現基于網絡拓撲的算法來調度“昂貴”的數據流，而不需要關心控制流中哪個chunkserver是首要的還是次要的。章節3.2將討論此算法的細節。
　　4. 一旦所有副本都確認收到了數據，客戶端正式發送一個寫請求到首要副本。寫請求無真實數據，只有一個身份標識，對應第三步中發給各個副本的數據包。在首要副本中會持續的收到來自各個客戶端的各種變異請求，本次寫請求只是其中一個而已。在持續接收請求的過程中，首要副本會為每個請求分配唯一的遞增序號，它也會嚴格按照此順序來在本地狀態中實施變異。
　　5. 首要將寫請求推送到所有次級副本（請求中已帶有分配的序號），每個次級副本都會嚴格按順序依次實施變異。
　　6. 次級副本回復給首要的，確認他們已完成操作。
　　7. 首要副本回復客戶端。在任何副本遭遇的任何錯誤，都被匯報給客戶端。在錯誤發生時，此寫操作可能已經在首要和某些次級副本中實施成功。（如果它首要就失敗，就不會分配序號也不會往后推進。）客戶端則認為此次請求失敗，請求所修改的區域變成了不一致狀態。對于失敗變異，客戶端會重試，它首先會做一些嘗試在步驟3到步驟7，實在不行就重試整個流程。

　　一個寫請求（非append）可能很大，跨越了chunk邊界，GFS客戶端代碼會將其拆分為對多個chunk的多個寫操作。各個寫操作都遵從上述控制流，但是也可能因為來自其他客戶端的并發寫導致某幾個子操作的文件區域產生數據碎片。不過即使如此，各副本的數據是相同的，因為此控制流保證了所有副本執行的變異順序是完全一致的。所以即使某些區域產生了碎片，還是滿足一致性的，但是會處于undefined狀態（章節2.7描述的）。

　　【譯者YY】上述流程中多次提到要按順序、依次、串行等詞匯，來避免并發導致的一致性問題。這些會不會導致性能問題？畢竟這是一個I/O密集型系統，請求串行化不是一個值得驕傲的解決方案。文章末尾對此疑問會嘗試解答。

　　3.2 數據流

　　我們將數據流和控制流解耦來更高效的利用網絡。從上述控制流的分析中可以看出，從客戶端到首要副本然后到所有次級副本，請求是沿著一個小心謹慎的鏈路、像管道一樣，在各個chunkserver之間推送。我們不能容忍真實數據的流程被此嚴謹的控制流綁架，我們的目標是最大化利用每個機器的網絡帶寬，避免網絡瓶頸和高延遲連接，最小化推送延遲。

　　為了最大化利用每臺機器的網絡帶寬，我們讓數據沿著一個線性鏈路推送（chunkserver就是鏈路中的一個個節點），而不是零亂的分布于其他拓撲結構中（比如樹狀）。我們希望每臺機器都會使用全量帶寬盡快傳輸一整批數據，而不是頻繁收發零亂的小批數據。

　　為了盡可能的避免網絡瓶頸和高延遲連接（內聯交換機經常遇到此問題），每個機器都會嘗試推送數據到網絡拓撲中最近的其他目標機器。假設客戶端希望推送數據到chunkserver S1、S2、S3、S4。不管網絡拓撲結構如何，我們假設S1離客戶端最近，S2離S1最近。首先客戶端會發送數據到最近的S1；S1收到數據，傳輸目標減少為[S2、S3、 S4]，繼而推送到離S1最近的S2，傳輸目標減少為[S3、S4]。相似的，S2繼續推送到S3或者S4（看誰離S2更近），如此繼續。我們的網絡拓撲并不復雜，可以用IP地址準確的預估出“距離”。

　　最后，我們使用TCP流式傳輸數據，以最小化延遲。一旦chunkserver收到數據，它立刻開始推送。TCP管道流式傳輸的效果顯著，因為我們使用的是 switched network with full-duplex links。立刻發送數據并不會影響接收速度。沒有網絡擁擠的情況下，傳輸B個字節到R個副本的理想耗時是B/T+RL，T是網絡吞吐量，L是在機器間傳輸字節的延遲。我們網絡連接是典型的100Mbps（T），L小于1ms，因此1MB的數據流大約耗時80ms。

　　3.3 原子append

　　GFS提供了原子append能力，稱之為record append。在傳統的寫操作中，客戶端指明偏移量，寫入時seek到此偏移，然后順序的寫入新數據。而record append操作中，客戶端僅需要指明數據。GFS可以選擇一個偏移量（一般是文件末尾），原子的將數據append到此偏移量，至少一次（沒有數據碎片，是一個連續序列的字節）偏移量被返回到客戶端。類似的，UNIX中多個writer并發寫入O_APPEND模式打開的文件時也沒有競爭條件。

　　record append在我們分布式應用中被大量的使用，其中很多機器上的大量客戶端會并發的append到相同的文件。如果用傳統的寫模式，將嚴重增加客戶端的復雜度，實施昂貴的同步，比如通過一個分布式鎖管理器。我們的實際應用場景中，record append經常用于多個制造者、單個消費者隊列情景，或者用于存儲多客戶端的合并結果。

　　record append也是一種變異，遵從控制流（章節3.1），但是會需要首要副本執行一點點額外的邏輯。客戶端將數據推送到文件末尾對應的chunk的所有副本上。然后發送寫請求到首要副本。首要副本需要檢查append到此chunk是否會導致chunk超過最大的size（64MB）。如果超過，它將此chunk填補到最大size，并告訴次級副本也這么做，隨后回復客戶端這個操作需要重試，并使用下一個chunk（上一個chunk剛剛已經被填滿，文件末尾會對應到一個新chunk）。record append的數據大小被限制為小于等于chunk maxsize的四分之一，這樣可以避免填補導致的過多碎片。如果不需要填補（通常都不需要），首要副本append數據到它的副本，得出其偏移量，并告訴次級副本將數據準確的寫入此偏移，最終回復客戶端操作已成功。

　　如果一個record append在任何副本失敗了，客戶端需要重試。因此，同一個chunk的各個副本可能包含不同的數據，各自都可能包含重復的record。GFS不保證所有副本是字節上相同的。它僅僅保證record apend能原子執行，寫入至少一次。不過有一點可以保證，record append最終成功后，所有副本寫入此有效record的偏移量是相同的。另外，所有副本至少和此record的結尾是一樣長的，因此任何未來的record將被分配到更高的偏移或者不同的chunk，即使首要副本換人。依據我們的一致性保證，成功的record append操作寫入的區域是defined（因此也是一致的），若操作最終失敗，則此區域是不一致的（因此undefined的）。我們的應用能處理這種不一致區域（2.7.2討論過）。

　　3.4 快照

　　快照操作能非常快的對一個文件或者一個目錄樹（稱之為源）執行一次拷貝，期間收到的新變異請求也只會受到很小的影響。我們的用戶經常使用快照功能快速的為大型的數據集合創建分支拷貝（經常拷貝再拷貝，遞歸的），或者存檔當前狀態，以便安全的實驗一些變異，隨后可以非常簡單提交或回滾。

　　與AFS類似，我們使用標準的copy-on-write技術來實現快照。當master收到一個快照請求，它找出此快照涉及的文件對應的所有chunk，撤回這些chunk上任何未償還的租賃。這樣即可保證隨后對這些chunk的寫請求將需要一個與master的交互來找到租賃擁有者。master利用此機會暗地里對此chunk創建一個新拷貝。

　　在撤回租賃完成后，master將此快照操作日志記錄到磁盤。實施快照操作時，它會在內存狀態中快速復制一份源文件、源目錄樹的元數據，復制出來的元數據映射到相同的chunk（和JVM中對象的引用計數相似，此chunk的引用計數為2，源元數據和快照元數據兩份引用）。

　　假設快照操作涉及的某個文件包含一個chunk（稱之為C），在快照操作后，某個客戶端需要寫入chunk C，它發送一個請求到master來找到當前租賃持有者。master注意到C的引用計數大于1（源元數據和快照元數據，2個引用）。它不著急給客戶端回復，而是選擇一個新的chunk句柄（稱之為C’），然后要求包含C的副本的chunkserver都為C’創建一個新副本。新老副本在同一個chunkserver，數據都是本地復制，不需要網絡傳輸（磁盤比100Mb的以太網快三倍）。master確認C’的副本都創建完畢后才會回復客戶端，客戶端只是略微感到了一點延遲，隨后它會對C及其副本執行正常的寫入操作。

　　4. master操作

　　所有的命名空間操作都由master執行。而且，它還負責管理所有chunk副本，貫穿整個系統始終：它需要做出布置決策、創建新chunk及其副本，協調控制各種系統級別的活動，比如保持chunk的復制級別、均衡所有chunkserver的負載，以及回收無用存儲。下面我們就各個主題展開討論。

　　4.1 命名空間管理和鎖

　　很多master操作會花費較長時間：比如一個快照操作需要撤回很多chunkserver的租賃。因此master操作必須能夠同時并發的執行以提高效率，但是又要避免它們產生的沖突。為此我們提供了命名空間的區域鎖機制，來保證在某些點的串行，避免沖突。

　　不像傳統的文件系統，GFS沒有目錄的listFiles功能。也不支持文件或者目錄的別名（也就是軟鏈接、硬鏈接、快捷方式）。master中的命名空間邏輯上可以理解為一個lookup table，其中包含完整的路徑名到元數據的映射。并且利用前綴壓縮提高其效率。命名空間樹的每個節點（無論一個絕對文件名或者一個絕對目錄名）都有一個對應的讀寫鎖。

　　每個master操作都會為其牽涉的節點申請讀鎖或寫鎖。如果它涉及/d1/d2/../dn/leaf，它將為目錄名稱為/d1、/d1/d2/、…、/d1/d2/…/dn申請讀鎖，以及完整路徑/d1/d2/…/dn/leaf的讀鎖。注意leaf可能是文件也可能是目錄。

　　下面舉例說明其細節。比如當/home/user/目錄正在被快照到/save/user時，我們能利用鎖機制防止用戶創建一個/home/user/foo的新文件。首先快照操作會為/home 和 /save申請讀鎖，以及在/home/user和/save/user申請寫鎖。創建新文件的請求會申請/home和/home/user的讀鎖，和/home/user/foo上的寫鎖。由于在/home/user上的鎖沖突，快照和創建新文件操作會串行執行。GFS中的目錄比標準文件API要弱化（不支持listFiles等），沒有類似的inode信息需要維護，所以在創建、刪除文件時不會修改此文件上級目錄的結構數據，創建/home/user/foo時也不需要申請父目錄/home/user的寫鎖。上述例子中申請/home/user的讀鎖可以保護此目錄不被刪除。

　　通過命名空間鎖可以允許在相同目錄發生并發的變化。比如多個文件在同一個目錄被并發創建：每個創建會申請此目錄的讀鎖和各自文件的寫鎖，不會導致沖突。目錄的讀鎖可以保護在創建時此目錄不會被刪除、重命名或者執行快照。對相同文件的創建請求，由于寫鎖的保護，也只會導致此文件被串行的創建兩次。

　　因為命名空間的節點不少，全量分配讀寫鎖有點浪費資源，所以它們都是lazy分配、用完即刪。而且鎖申請不是隨意的，為了防止死鎖，一個操作必須按特定的順序來申請鎖：首先按命名空間樹的層級排序，在相同層級再按字典序。

　　4.2 副本布置

　　GFS集群是高度分布式的，而且有多個層級（層級是指：機房/機架/服務器這樣的層級結構）。通常會在多個機架上部署幾百個chunkserver。這些chunkserver可能被各機架的幾百個客戶端訪問。不同機架之間的機器通訊可能跨一個或多個網絡交換機。進出一個機架的帶寬可能會低于機架內所有機器的總帶寬。多級分布式要求我們更加合理的分布數據，以提高可擴展性、可靠性和可用性。

　　chunk副本的布置策略主要遵循兩個目標：最大化數據可靠性和可用性，最大化網絡帶寬利用。僅僅跨機器的冗余副本是不夠的，這僅僅能防御磁盤或者機器故障，也只考慮到單臺機器的網絡帶寬。我們必須跨機架的冗余chunk副本。這能保證系統仍然可用即使整個機架損壞下線（比如網絡交換機或者電力故障）。而且能按機架的帶寬來分攤讀操作的流量。不過這會導致寫流量被發往多個機架，這一點犧牲我們可以接受。

　　4.3 創建、重復制、重負載均衡

　　chunk副本會在三個情況下被創建：chunk創建、restore、重負載均衡

　　當master創建一個chunk，它需要選擇在哪些chunkserver上布置此chunk的初始化空副本。選擇過程主要會考慮幾個因素。1. 盡量選擇那些磁盤空間利用率低于平均值的chunkserver。這樣長此以往可以均衡各chunkserver的磁盤使用率。2. 我們不希望讓某臺chunkserver在短時間內創建過多副本。盡管創建本身是廉價的，但它預示著即將來臨的大量寫流量（客戶端請求創建chunk就是為了向其寫入），而且據我們觀察它還預示著緊隨其后的大量讀操作。3. 上面論述過，我們想要跨機架的為chunk保存副本。

　　master需要關注chunk的復制級別是否達標（每個chunk是否有足夠的有效副本），一旦不達標就要執行restore操作為其補充新副本。很多原因會導致不達標現象：比如某個chunkserver不可用了，某個副本可能腐化了，某個磁盤可能不可用了，或者是用戶提高了復制級別。restore時也要按優先級考慮幾個因素。第一個因素是chunk低于復制標準的程度，比如有兩個chunk，一個缺兩份副本、另一個只缺一份，那必須先restore缺兩份的。第二，我們會降低已被刪除和曾被刪除文件對應chunk的優先級。最后，我們會提高可能阻塞客戶端進程的chunk的優先級。

　　master選擇高優先級的chunk執行restore時，只需指示某些chunkserver直接從一個已存在的合法副本上拷貝數據并創建新副本。選擇哪些chunkserver也是要考慮布置策略的，其和創建時的布置策略類似：盡量均衡的利用磁盤空間、避免在單臺chunkserver上創建過多活躍的chunk副本、以及跨機架。restore會導致整個chunk數據在網絡上傳輸多次，為了盡量避免影響，master會限制整個集群以及每臺chunkserver上同時執行的restore數量，不會在短時間執行大量的restore。而且每個chunkserver在拷貝源chunkserver的副本時也會采用限流等措施來避免占用過多網絡帶寬。

　　重負載均衡是指：master會檢查當前的副本分布情況，為了更加均衡的磁盤空間利用率和負載，對必要的副本執行遷移（從負擔較重的chunkserver遷移到較輕的）。當新的chunkserver加入集群時也是依靠這個活動來慢慢的填充它，而不是立刻讓它接收大量的寫流量。master重新布置時不僅會考慮上述的3個標準，還要注意哪些chunkserver的空閑空間較低，優先為其遷移和刪除。

　　4.4 垃圾回收

　　在一個文件被刪除后，GFS不會立刻回收物理存儲。它會在懶惰的、延遲的垃圾回收時才執行物理存儲的回收。我們發現這個方案讓系統更加簡單和可靠。

　　4.4.1 機制

　　當一個文件被應用刪除時，master立刻打印刪除操作的日志，然而不會立刻回收資源，僅僅將文件重命名為一個隱藏的名字，包含刪除時間戳。在master對文件系統命名空間執行常規掃描時，它會刪除任何超過3天的隱藏文件（周期可配）。在那之前此隱藏文件仍然能夠被讀，而且只需將它重命名回去就能恢復。當隱藏文件被刪除時，它才在內存中元數據中被清除，高效的切斷它到自己所有chunk的引用。

　　在另一個針對chunk命名空間的常規掃描中，master會識別出孤兒chunk（也就是那些任何文件都不會引用的chunk），并刪除它們的元數據。在與master的心跳消息交換中，每個chunkserver都會報告它的一個chunk子集，master會回復哪些chunk已經不在其元數據中了，chunkserver于是刪除這些chunk的副本。

　　4.4.2 討論

　　盡管分布式垃圾回收是一個困難的問題，它需要復雜的解決方案，但是我們的做法卻很簡單。master的“文件到chunk映射”中記錄了對各chunk引用信息。我們也能輕易的識別所有chunk副本：他們是在某臺chunkserver上、某個指定的目錄下的一個Linux文件。任何master沒有登記在冊的副本都可以認為是垃圾。

　　我們的垃圾回收方案主要有三點優勢。首先，它保證了可靠性的同時也簡化了系統。chunk創建操作可能在一些chunkserver成功了、在另一些失敗了，失敗的也有可能是創建完副本之后才失敗，如果對其重試，就會留下垃圾。副本刪除消息也可能丟失，master是否需要嚴謹的關注每個消息并保證重試？垃圾回收提供了一個統一的可依靠的方式來清理沒有任何引用的副本，可以讓上述場景少一些顧慮，達到簡化系統的目的。其次，垃圾回收的邏輯被合并到master上各種例行的后臺活動中，比如命名空間掃描，與chunkserver的握手等。所以它一般都是批處理的，花費也被大家分攤。而且它只在master相對空閑時執行，不影響高峰期master的快速響應。第三，延遲的回收有時可挽救偶然的不可逆的刪除（比如誤操作）。

　　在我們的實驗中也遇到了延遲回收機制的弊端。當應用重復的創建和刪除臨時文件時，會產生大量不能被及時回收的垃圾。針對這種情況我們在刪除操作時會主動判斷此文件是否是首次刪除，若不是則主動觸發一些回收動作。與復制級別類似，不同的命名空間區域可配置各自的回收策略。

　　4.5 舊副本偵測

　　當chunkserver故障，錯過對chunk的變異時，它的版本就會變舊。master會為每個chunk維護一個版本號來區分最新的和舊的副本。

　　每當master授予一個新的租賃給某個chunk，都會增長chunk版本號并通知各副本。master和這些副本都持久化記錄新版本號。這些都是在寫操作被處理之前就完成了。如果某個副本當前不可用，它的chunk版本號不會被更新。master可以偵測到此chunkserver有舊的副本，因為chunkserver重啟時會匯報它的chunk及其版本號信息。如果master看到一個比自己記錄的還要高的版本號，它會認為自己在授予租賃時發生了故障，繼而認為更高的版本才是最新的。

　　master會在常規垃圾回收活動時刪除舊副本。在那之前，它只需保證回復給客戶端的信息中不包含舊副本。不僅如此，master會在各種與客戶端、與chunkserver的其他交互中都附帶上版本號信息，盡可能避免任何操作、活動訪問到舊的副本。

　　5 故障容忍和診斷

　　我們最大挑戰之一是頻繁的組件故障。GFS集群中組件的質量（機器質量較低）和數量（機器數量很多）使得這些問題更加普遍：我們不能完全的信賴機器，也不能完全信賴磁盤。組件故障能導致系統不可用甚至是腐化的數據。下面討論我們如何應對這些挑戰，以及我們構建的幫助診斷問題的工具。

　　5.1 高可用性

　　GFS集群中有幾百臺機器，任何機器任何時間都可能不可用。我們保持整體系統高度可用，只用兩個簡單但是高效的策略：快速恢復和復制。

　　5.1.1 快速恢復

　　master和chunkserver都可以在幾秒內重啟并恢復它們的狀態。恢復的時間非常短，甚至只會影響到那些正在執行中的未能回復的請求，客戶端很快就能重連到已恢復的服務器。

　　5.1.2 chunk復制

　　早先討論過，每個chunk會復制到多個機架的chunkserver上。用戶能為不同的命名空間區域指定不同的復制級別。默認是3份。master需要保持每個chunk是按復制級別完全復制的，當chunkserver下線、偵測到腐化副本時master都要補充新副本。盡管復制機制運行的挺好，我們仍然在開發其他創新的跨服務器冗余方案。

　　5.1.3 master復制

　　master保存的元數據狀態尤其重要，它必須被冗余復制。其操作日志和存檔會被復制到多臺機器。只有當元數據操作的日志已經成功flush到本地磁盤和所有master副本上才會認為其成功。所有的元數據變化都必須由master負責執行，包括垃圾回收之類的后臺活動。master故障時，它幾乎能在一瞬間完成重啟。如果它的機器或磁盤故障，GFS之外的監控設施會在另一臺冗余機器上啟用一個新master進程（此機器保存了全量的操作日志和存檔）。客戶端是通過canonical域名（比如gfs-test）來訪問master的，這是一個DNS別名，對其做些手腳就能將客戶端引導到新master。

　　此外我們還提供了陰影master，它能在master宕機時提供只讀訪問。他們是陰影，而不是完全鏡像，陰影會比主master狀態落后一秒左右。如果文件不是正在發生改變，或者應用不介意拿到有點舊的結果，陰影確實增強了系統的可用性。而且應用不會讀取到舊的文件內容，因為文件內容是從chunkserver上讀取的，最多只會從陰影讀到舊的文件元數據，比如目錄內容或者訪問控制信息。

　　陰影master會持續的讀取某個master副本的操作日志，并重放到自己的內存中數據結構。和主master一樣，它也是在啟動時拉取chunkserver上的chunk位置等信息（不頻繁），也會頻繁與chunkserver交換握手消息以監控它們的狀態。僅僅在master決定創建或刪除某個master副本時才需要和陰影交互（陰影需要從它的副本里抓日志重放）。

　　5.2 數據完整性

　　每個chunkserver使用checksum來偵測腐化的存儲數據。一個GFS集群經常包含幾百臺服務器、幾千個磁盤，磁盤故障導致數據腐化或丟失是常有的事兒。我們能利用其他正常的chunk副本恢復腐化的數據，但是通過跨chunkserver對比副本之間的數據來偵測腐化是不切實際的。另外，各副本內的字節數據出現差異也是正常的、合法的（原子的record append就可能導致這種情況，不會保證完全一致的副本，但是不影響客戶端使用）。因此，每個chunkserver必須靠自己來核實數據完整性，其對策就是維護checksum。

　　一個chunk被分解為多個64KB的塊。每個塊有對應32位的checksum。像其他元數據一樣，checksum被保存在內存中，并用利用日志持久化保存，與用戶數據是隔離的。

　　在讀操作中，chunkserver會先核查讀取區域涉及的數據塊的checksum。因此chunkserver不會傳播腐化數據到客戶端（無論是用戶客戶端還是其他chunkserver）。如果一個塊不匹配checksum，chunkserver向請求者明確返回錯誤。請求者收到此錯誤后，將向其他副本重試讀請求，而master則會盡快從其他正常副本克隆數據創建新的chunk。當新克隆的副本準備就緒，master命令發生錯誤的chunkserver刪除異常副本。

　　checksum對讀性能影響不大。因為大部分讀只會跨幾個塊，checksum的數據量不大。GFS客戶端代碼在讀操作中可以盡量避免跨越塊的邊界，進一步降低checksum的花費。而且chunkserver查找和對比checksum是不需要任何I/O的，checksum的計算通常也在I/O 等待時被完成，不爭搶CPU資源。

　　checksum的計算是為append操作高度優化的，因為append是我們的主要應用場景。append時可能會修改最后的塊、也可能新增塊。對于修改的塊只需增量更新其checksum，對于新增塊不管它有沒有被填滿都可以計算其當前的checksum。對于最后修改的塊，即使它已經腐化了而且append時沒有檢測到，還對其checksum執行了增量更新，此塊的checksum匹配依然會失敗，在下次被讀取時即能偵測到。

　　普通的寫操作則比append復雜，它會覆蓋重寫文件的某個區域，需要在寫之前檢查區域首尾塊的checksum。它不會創建新的塊，只會修改老的塊，而且不是增量更新。對于首尾之間的塊沒有關系，反正是被全量的覆蓋。而首尾塊可能只被覆蓋了一部分，又不能增量更新，只能重新計算整個塊的checksum，覆蓋老checksum，此時如果首尾塊已經腐化，就無法被識別了。所以必須先檢測后寫。

　　在系統較空閑時，chunkserver會去掃描和檢查不太活躍的chunk。這樣那些很少被讀的chunk也能被偵測到。一旦腐化被偵測到，master會為其創建一個新副本，并刪除腐化副本。GFS必須保證每個chunk都有足夠的有效副本以防不可逆的丟失，chunk不活躍可能會導致GFS無法察覺它的副本異常，此機制可以有效的避免這個風險。

　　5.3 診斷工具

　　大量詳細的診斷日志對于問題隔離、調試、和性能分析都能提供無法估量的價值，打印日志卻只需要非常小的花費。如果沒有日志，我們永遠捉摸不透那些短暫的、不可重現的機器間交互。GFS服務器生成的診斷日志存儲了很多重要的事件（比如chunkserver的啟動和關閉）以及所有RPC請求和回復。這些診斷日志能被自由的刪除而不影響系統正確性。然而我們會盡一切可能盡量保存這些有價值的日志。

　　RPC日志包含了在線上每時每刻發生的請求和回復，除了讀寫的真實文件數據。通過在不同機器之間匹配請求和回復、整理RPC記錄，我們能重現整個交互歷史，以便診斷問題。日志也能服務于負載測試和性能分析的追蹤。

　　日志造成的性能影響很小（與收益相比微不足道），可以用異步緩沖等各種手段優化。有些場景會將大部分最近的事件日志保存在機器內存中以供更嚴格的在線監控。

　　【擴展閱讀】

　　“GFS……也支持小文件，但是不需要著重優化”，這是論文中的一句原話，初讀此文時還很納悶，GFS不是據說解決了海量小文件存儲的難題嗎，為何前后矛盾呢？逐漸深讀才發現這只是個小誤會。下面譯者嘗試在各個視角將GFS、TFS、Haystack進行對比分析，讀者可結合前文基礎，了解個中究竟。

　　1. 愿景和目標

　　GFS的目標可以一言以蔽之：給用戶一個無限容量、放心使用的硬盤，快速的存取文件。它并沒有把自己定位成某種特定場景的文件存儲解決方案，比如小文件存儲或圖片存儲，而是提供了標準的文件系統API，讓用戶像使用本地文件系統一樣去使用它。這與Haystack、TFS有所不同，GFS的目標更加通用、更加針對底層，它的編程界面也更加標準化。

　　比如用戶在使用Haystack存取圖片時，可想而知，編程界面中肯定會有類似create(photo)、read(photo_id)這樣的接口供用戶使用。而GFS給用戶提供的接口則更類似File、FileInputStream、FileOutputStream（以Java語言舉例）這樣的標準文件系統接口。對比可見，Haystack的接口更加高層、更加抽象，更加貼近于應用，但可能只適合某些定制化的應用場景；GFS的接口則更加底層、更加通用，標準文件系統能支持的它都能支持。舉個例子，有一萬張圖片，每張100KB左右，用Haystack、GFS存儲都可以，用Haystack更方便，直接有create(photo)這樣的接口可以用，調用即可；用GFS就比較麻煩，你需要自己考慮是存成一萬張小文件還是組裝為一些大文件、按什么格式組裝、要不要壓縮……GFS不去管這些，你給它什么它就存什么。假如把一萬張圖片換成一部1GB的高清視頻AVI文件，總大小差不多，一樣可以放心使用GFS來存儲，但是Haystack可能就望而卻步了（難道把一部電影拆散放入它的一個個needle？）。

　　這也回答了剛剛提到的那個小誤會，GFS并不是缺乏對小文件的優化和支持，而是它壓根就沒有把自己定位成小文件存儲系統，它是通用的標準文件系統，它解決的是可靠性、可擴展性、存取性能等后顧之憂，至于你是用它來處理大文件、存儲增量數據、打造一個NoSQL、還是解決海量小文件，那不是它擔心的問題。只是說它這個文件系統和標準文件系統一樣，也不喜歡數量太多的小文件，它也建議用戶能夠將數據合理的組織安排，放入有結構有格式的大文件中，而不要將粒度很細的一條條小數據保存為海量的小文件。 相反，Haystack和TFS則更注重實用性，更貼近應用場景，并各自做了很多精細化的定制優化。在通用性和定制化之間如何抉擇，前文2.3中Haystack的架構師也糾結過，但是可以肯定的是，基于GFS，一樣可以設計needle結構、打造出Haystack。

　　2 存儲數據結構

　　這里的數據結構僅針對真實文件內容所涉及的存儲數據結構。三者在這種數據結構上有些明顯的相同點：

　　首先，都有一個明確的邏輯存儲單元。在GFS中就是一個Chunk，在Haystack、TFS中分別是邏輯卷和Block。三者都是靠各自的大量邏輯存儲單元組成了一個龐大的文件系統。設計邏輯存儲單元的理由很簡單——保護真正的物理存儲結構，不被用戶左右。用戶給的數據太小，那就將多個用戶數據組裝進一個邏輯存儲單元（Haystack將多個圖片作為needle組裝到一個邏輯卷中）；用戶給的數據太大，那就拆分成多個邏輯存儲單元（GFS將大型文件拆分為多個chunk）。總之就是不管來者是大還是小，都要轉換為適應本系統的物理存儲格式，而不按照用戶給的格式。一個分布式文件系統想要保證自身的性能，它首先要保證自己能基于真實的物理文件系統打造出合格的性能指標（比如GFS對chunk size=64MB的深入考究），在普通Linux文件系統上，固定大小的文件+預分配空間+合理的文件總數量+合理的目錄結構等等，往往是保證I/O性能的常用方案。所以必須有個明確的邏輯存儲單元。

　　另一個很明顯的相同點：邏輯存儲單元和物理機器的多對多關系。在GFS中一個邏輯存儲單元Chunk對應多個Chunk副本，副本分布在多個物理存儲chunkserver上，一個chunkserver為多個chunk保存副本（所以chunk和chunkserver是多對多關系）。Haystack中的邏輯卷與Store機器、TFS中的Block與DataServer都有這樣的關系。這種多對多的關系很好理解，一個物理存儲機器當然要保存多個邏輯存儲單元，而一個邏輯存儲單元對應多個物理機器是為了冗余備份。

　　三者在數據結構上也有明顯的區別，主要是其編程界面的差異導致的。比如在Haystack、TFS的存儲結構中明確有needle這種概念，但是GFS卻不見其蹤影。這是因為Haystack、TFS是為小文件定制的，小文件是它們的存儲粒度，是用戶視角下的存儲單元。比如在Haystack中，需要考慮needle在邏輯卷中如何組織檢索等問題，邏輯卷和needle是一對多的關系，一個邏輯卷下有多個needle，某個needle屬于一個邏輯卷。這些關系GFS都不會去考慮，它留給用戶自行解決（上面愿景和目標里討論過了）。

　　3 架構組件角色

　　Haystack一文中的對比已經看到分布式文件系統常用的架構范式就是“元數據總控+分布式協調調度+分區存儲”。在Haystack中Directory掌管所有應用元數據、為客戶端指引目標（指引到合適的目標Store機器做合適的讀寫操作，指引過程就是協調調度過程），單個Store機器則負責處理好自身的物理存儲、本地數據讀寫；TFS中NameServer控制所有應用元數據、指引客戶端，DataServer負責物理存儲結構、本地數據讀寫。可以看出這個范式里的兩個角色——協調組件、存儲組件。協調組件負責了元數據總控+分布式協調調度，各存儲組件作為一個分區，負責實際的存儲結構和本地數據讀寫。架構上的相同點顯而易見——GFS也滿足此范式，作為協調組件的master、和作為存儲組件的chunkserver。在組件角色的一些關鍵設計上，三者也曾面臨了一些相似的技術難題，比如它們都竭力減少對協調組件的依賴、減少其交互次數，不希望給它造成過大壓力。協調組件為啥顯得這么脆弱、這么缺乏安全感呢？從兩篇論文都可以看出，GFS和Haystack的作者非常希望協調組件能夠簡化，其原因很簡單——人如果有兩個大腦那很多事會很麻煩。協調組件可認為是整個系統的大腦，它不停的派發命令、指點迷津；如果大腦有兩個，那客戶端聽誰的、兩個大腦信息是否需要同步、兩個大腦在指定策略時是否有資源競爭……就跟人一樣，這種核心總控的大腦有多個會帶來很多復雜度、一致性問題，難以承受。即使各平臺都有備用協調組件，比如GFS的陰影master，但都只是作為容災備用，不會在線參與協調。

　　4 元數據

　　雖然Haystack的Directory、TFS的NameServer、GFS的master干的是同樣的活，但是其在元數據問題上也有值得討論的差異。上篇文章中曾重點介紹了譯者對于全量緩存應用元數據的疑惑（Haystack全量緩存所有圖片的應用元數據，而TFS用了巧妙的命名規則），難道GFS不會遇到這個難題嗎？而且此篇文章還反復強調了GFS的master是單例的、純內存的，難道它真的不會遭遇單點瓶頸嗎？答案還是同一個：編程界面。GFS的編程界面決定了即使它整個集群存了幾百TB的數據，也不會有太多的文件。對于Haystack和TFS，它們面對的是billions的圖片文件，對于GFS，它可能面對的僅僅是一個超巨型文件，此文件里有billions的圖片數據。也就是說Haystack和TFS要保存billions的應用元數據，而GFS只需保存一個。那GFS把工作量丟給誰了？對，丟給用戶了。所以GFS雖然很偉大、很通用、愿景很酷，但是對特定應用場景的支持不一定友好，這也是Haystack最終自行定制的原因之一吧。

　　同時，這也是GFS敢于設計單點、內存型master的原因，它認為一個集群內的文件數量不會超過單點master的能力上限。同樣的，GFS也沒有著重介紹文件系統元數據的方案（Haystack文章中反復強調了文件系統元數據牽扯的I/O問題），原因也是一樣：文件系統元數據的I/O問題對于Haystack來說很難纏是因為Haystack要面對海量小文件，而GFS并不需要。 有了這樣的前提，GFS的master確實可以解脫出來，做更多針對底層、面向偉大愿景的努力。比如可以輕輕松松的在單機內存中全量掃描所有元數據、執行各種策略（如果master受元數據所累、有性能壓力、需要多個master分布式協作，那執行這種全局策略就會很麻煩了，各種一致性問題會撲面而來）。

　　不過GFS中會多出一種Haystack和TFS都沒有的元數據——文件命名空間。當你把GFS當做本地磁盤一樣使用時，你需要考慮文件的目錄結構，一個新文件產生時是放到一個已有目錄還是創建新目錄、創建新文件時會不會有另一個請求正在刪除父目錄……這些內容是GFS特有的（Haystack和TFS的用戶不需要面對這些內容），所以它考慮了master的命名空間鎖、操作日志順序等機制，來保護命名空間的更新。

　　5 控制流、數據流（以及一致性模型）

　　GFS、Haystack、TFS的控制流大致相同，其思路不外乎：1 客戶端需要發起一次新請求；2 客戶端詢問協調組件，自己應該訪問哪個存儲組件；3 協調組件分析元數據，給出答復；4 客戶端拿到答復直接訪問指定的存儲組件，提交請求；5 各存儲組件執行請求，返回結果。

　　但是細節上各自有差異，上篇文章提到Haystack是對等結構，客戶端直接面對各對等存儲組件（比如寫入時看到所有物理卷、分別向其寫入），而TFS是主備結構，客戶端只面對主DataServer，主向備同步數據……GFS在這方面最大的差異在于：

　　5.1 租賃機制

　　回想Haystack，客戶端直接將寫請求提給各個Store機器即可解決問題，GFS也是對等設計，為何要搗鼓出令人費解的租賃機制？不能直接由客戶端分別寫入各個對等chunkserver嗎？這個問題已經在一致性模型章節討論過，當時提到了租賃機制是為了保證各個副本按相同順序串行變異，那我們也可以反過來問一句：Haystack、TFS里為啥沒有遇到這等問題？是它們對一致性考慮太少了嗎？ 這個答案如果要追本溯源，還是要牽扯到編程界面的問題：Haystack、TFS中用戶面對的是一個個小圖片，用戶將圖片存進去、拿到一個ID，將來只要保證他拿著此ID依然能找到對應圖片就行，即使各個副本執行存儲時順序有差別，也絲毫不影響用戶使用（比如Hasytack收到3個并發圖片A、B、C的存儲請求，提交到3臺Store機器，分別存成了ABC、ACB、BAC三種不同的順序，導致副本內容不一致，但是當用戶無論拿著A、B、C哪個圖片ID來查詢、無論查的是哪個Store機器，都能檢索到正確的圖片，沒有問題；Haystack和TFS的編程界面封裝的更高級，GFS在底層遭遇的難題影響不到它們）。而在GFS比較底層的編程界面中，用戶面對的是眾多圖片組裝而成的一整個文件，如果GFS在不同副本里存儲的文件內容不一致，那就會影響用戶的檢索邏輯，那攤上大事兒了。另外，Haystack、TFS只支持小文件的append和remove，而GFS懷抱著偉大的愿景，它需要支持對文件的隨機寫，只有保證順序才能避免同個文件區域并發隨機寫導致的undefined碎片問題。所以GFS花心思設計租賃機制也就合情合理了。

　　談到串行就不得不考慮一下性能問題，串行絕不是大規模并發系統的目標，而只是一種妥協——對于多核操作系統下的I/O密集型應用，當然是越并行越有益于性能。比如現在有10個并發的append請求，是逐個依次執行，每一個都等待上一個I/O處理完成嗎？這樣每個請求的I/O Wait時間cpu不就空閑浪費嗎？根據譯者的推測，GFS所謂的串行僅僅應該是理論上的串行（即執行效果符合串行效果），但真正執行時并不會采用加鎖、同步互斥、按順序單線程依次執行等性能低劣的方案。以10個并發append為例，理論上只需要一個AtomicLong對象，保存了文件長度，10個append線程可并發調用其addAndGet()，得到各自不沖突的合法偏移位置，繼而并發執行I/O寫入操作，互不干擾。再比如對同個文件的隨機偏移寫，也不是要全部串行，只有在影響了同一塊文件區域時才需要串行，因此可以減小串行粒度，影響不同區域的請求可并行寫入。通過這樣的技巧，再結合在首要chunkserver上分配的唯一序號，GFS應該可以實現高性能的串行效果，尤其是append操作。

　　TFS和Haystack的文章之所以沒有過多提及一致性問題，并不是因為它們不保證，而是在它們的編程界面下（面向小文件的append-only寫），一致性問題不大，沒有什么難纏的陷阱。

　　5.2 數據流分離

　　Haystack沒法在數據流上做什么文章，它的客戶端需要分別寫入各個Store機器；TFS可以利用其主備機制，合理安排master-slave的拓撲位置以優化網絡負載。而GFS則是完全將真實文件的數據流和控制流解耦分離，在網絡拓撲、最短路徑、最小化鏈式傳輸上做足了文章。系統規模到一定程度時，機房、機架網絡拓撲結構對于整體性能的影響是不容忽略的，GFS在這種底層機制上考慮的確實更加到位。

　　6 可擴展性和容錯性

　　在上篇文章中已經詳盡的討論了Haystack、TFS是如何實現了優雅的高可擴展性。對于元數據不成難題的GFS，當然也具備同樣的實力，其原理就不重復敘述了。值得一提的是，GFS從元數據的負擔中解放出來后，它充分利用了自身的優勢，實現了各種全局策略、系統活動，極大的提高了系統的可擴展性及附屬能力，比如restore、重負載均衡等等。而且其并不滿足于簡單的機器層面，還非常深入的考慮了網絡拓撲、機架布置……GFS這些方面確實要領先于同類產品。

　　容錯性的對比同樣在上篇文章中詳細描述過，在結構方面GFS的chunkserver也是對等結構（控制流的首次之分與容錯無關），其效果與Haystack的容錯機制類似，無論是機器故障還是機房故障。相對來說，GFS在故障的恢復、偵測、版本問題、心跳機制、協調組件主備等環節介紹的更加細致，這些細節Haystack沒有怎么提及。值得一提的差異是GFS在數據完整性上的深入考究，其checksum機制可有效的避免腐化的數據，這一點Haystack、TFS沒有怎么提及。

　　7  刪除和修改

　　很多時候我們會重點關注一個系統是否能刪除和修改數據，這是因為當今越來越多架構設計為了追求更高的主流可用性，而犧牲了其他次要的特性。比如你發表一篇微博時一瞬間就提交成功，速度快、用戶體驗非常好；結果你發現不小心帶了一句“大概八點二十分發”，傻眼了，到處找不著微博修改的按鈕；于是你只能刪除老微博，再發一條新的，老微博的評論、轉發都丟失了。當你不承認自己發過八點二十分的微博時，網友拿出了截圖，你說是PS的，新浪在旁冷笑，你那條八點二十分的微博一直在原處，從未被刪除，估計要過好幾個小時之后才會真正從磁盤刪掉。

　　在學習Haystack、TFS、GFS的過程中我們可以看出大家都有這種傾向，原因可能有很多，其中有兩個是比較明顯的。首先，對于存儲的數據結構，增加新數據造成的破壞較小，而刪除、修改造成的破壞較大。新增只是往末尾附加一些新data，而不會影響已有的data；刪除則導致已有data中空出了一塊區域，這塊區域不能就這么空放著，最低劣的做法是直接將已有data進行大規模位移來填補狹縫，比較婉轉的做法是先不著急等不忙的時候做一次碎片整理；修改會導致某條數據size發生變化，size變小會導致狹縫碎片，size變大則空間不足，要擠占后面數據的位置。其次，新增數據可以做到無競爭（剛才5.1討論了GFS的原子append，并發的新增操作影響的是不同的文件區域，互不干擾），而刪除和修改則很難（并發的刪除和修改操作可能影響相同的文件區域，這就必須有條件競爭）。有這兩個原因存在，大家都偏愛append、不直接實現修改和刪除，就不難理解了。

　　不過GFS依然支持直接的修改功能——隨機偏移寫。這并不是因為GFS的架構設計更強大，而是因為它不需要承擔某些責任。比如在Haystack和TFS中，它們需要承擔圖片在真實文件中的存儲格式、檢索等責任，當將一個圖片從100KB修改為101KB時，對存儲格式的破壞是難以承受的，所以它們不支持這種直接的修改，只能采用刪除+新增來模擬修改。而GFS并沒有維護一個文件內部格式的責任，還是那句話，你交給它什么它就存什么。所以用戶會保護自己的文件內部格式，他說可以寫那就可以寫，GFS并沒有什么難題，只需解決好一致性、defined、統一變異順序等問題即可。

　　同樣，GFS的刪除與Haystack、TFS的刪除，其意義也不同。GFS的刪除指的是整個大文件的刪除。Haystack和TFS刪除的是用戶視角下的一條數據，比如一張圖片，它是邏輯存儲單元中的一個entry而已。而GFS的刪除則是用戶視角下的一整個文件，一個文件就對應了多個邏輯存儲單元（chunk），里面也包含了海量的應用實體（比如圖片）。在這種差異的背景下，他們面臨的難題也完全不同。Haystack和TFS面臨的就是剛才提到的“刪除會破壞存儲文件已有數據的格式、造成狹縫碎片”問題，它們的對策就是懶惰軟刪除、閑了再整理。而GFS則不會遭遇此難題，用戶在文件內部刪除幾條數據對于GFS來說和隨機偏移寫沒啥區別，狹縫碎片也是用戶自己解決。GFS需要解決的是整個文件被刪除，遺留下了大量的chunk，如何回收的問題。相比Haystack和TFS，GFS的垃圾回收其實更加輕松，因為它要回收的是一個個邏輯存儲單元（chunk），一個chunk（副本）其實就是一個真實的Linux文件，調用file.delete()刪了就等于回收了，而不需要擔心文件內部那些精細的組織格式、空間碎片。

　　8 其他細節和總結

　　GFS還是有很多與眾不同的技巧，比如合理有效的利用操作日志+存檔來實現元數據持久化存儲；比如細粒度、有條不紊的命名空間鎖機制；便捷的快照功能等等。從整體風格來說，GFS偏愛底層上的深入考究，追求標準化通用化的理想，它希望別人把它當成一個普通的文件系統，無需華麗的產品包裝，而只是務實的搭建好底層高可靠、高可用、高可擴展的基礎。但是美好的不一定是合適的，通用的不一定是最佳的，Haystack、TFS在追求各自目標的道路上一樣風雨無阻披荊斬棘。這兩篇論文的翻譯和對比，只希望能將巨頭的架構師們糾結權衡的分岔路口擺到讀者面前，一起感同身受，知其痛，理解其抉擇背后的意義。