GFS論文整理(三)

Snapshot:

    snapshot(快照)操作瞬間為檔案或者目錄樹（即source）做一個copy，最小化對正在進行的變更操作的打斷。我們的使用者使用快照功能來快速建立資料集龐大的分支副本（經常是副本的複制，遞歸地），或者在嘗試應用資料修改之前對目前狀态設定checkpoint，這樣簡單地送出或者復原。

    像AFS，我們使用标準的copy-on-write技術來實作snapshot。當master收到snapshot請求後，它首先撤銷需要被snapshot的檔案中所有chunks上的所有的outstanding leases（？？未傳遞的lease，大概意思可能是未被收回，尚在起效的leases），這就保證接下來的對這些chunks的所有write操作都需要與master互動一次來獲知leases的持有者。這就給master一個建立chunk copy的時機。（聲明：snapshot并不是檔案的copy，此處論文用詞有誤）

    在這些leases被撤銷或者過期後，master将這個操作記錄在日志中。然後它通過複制源檔案metadata或者目錄樹的方式，把這個log record應用到它的記憶體狀态（估計大概意思是在leases撤銷後，master就把這個record資訊寫入記憶體，作為一種狀态儲存，同時開始複制medatadata of the source file  or directory tree）。這個建立的snapshot檔案和源檔案指向相同的chunks。

    在snapshot操作後，一個client需要向chunk C寫入操作，它向master請求目前的lease持有者。Master 發現對chunk C的引用計數器大于1（參見snapshot原理，建立檔案的snapshot，會造成源檔案的引用計數器+1，實體引用指針）。它（master）推遲對client的響應，而是建立一個新的chunk handle C‘，然後它問詢每個chunkserver（持有C的replicas）來建立一個新的稱為 C’ 的chunk。 通過在同一個chunkserver上建立新的chunk（每個chunkserver，各自建立自己的新chunk），我們能夠確定資料在本地複制，而不是通過網絡傳輸（硬碟的速度是網速的數倍，通過snapshot之後，每個chunkserver都有了對file的copy資訊）。基于這一點，請求的處理和其他chunk沒什麼差別了：master給其中一個replicas C‘授權leases，然後響應給client，然後client就可以像往常一樣write操作，而且它無需知道C’是從原有的chunk上建立的。

Master operation：

    master處理所有的namespace操作。此外，它管理整個系統的chunk replicas：它負責chunk的實體位置配置設定，建立新chunk和replicas，協調多個系統範圍内的活動來保持chunk全量的replicated，在所有的chunkserver間負載均衡，回收無用的storage。

Namespace管理和鎖：

    master的許多操作是需要花費較長的時間：例如，snapshot操作需要撤銷chunkserver中所有chunk（snapshot所覆寫，即需要snapshot的檔案對應的chunk）上的leases。在它們運作的時候，我們不想拖延master的其他操作。是以，我們允許多個操作同時進行，我們在相應namspace的region上使用locks，來確定适當的序列化。

    不像傳統的檔案系統，GFS沒有per-directory （按照目錄區分資料）資料結構列出那個目錄下的所有檔案。也不支援對一個檔案多個别名（像unix下的軟/硬連結，hard links）（大概意思是，GFS不像其他檔案系統，直接以pathname進行file管理，例如window的檔案系統，GFS在這種pathname上做了一些工作，轉換成namespace的方式，其實namespace也是給予pathname的，但是做了一些自己的mapping）。GFS邏輯上以一個映射全路徑名到metadata的查找表格來描述它的命名空間（GFS logically represents its namespace as a lookup table mapping full pathnames to metadata），使用字首壓縮，這個表格可以被高效的在記憶體中展示。Namespace tree的每個節點（絕對的檔案名稱或者絕對的路徑名）有一個相關的read-write lock。

    每個master操作之前需要擷取一系列的locks。如果它（master）調用/d1/d2.../dn/leaf，它将會擷取read-locks在路徑名為/d1,/d1/d2,......,/d1/d2/..../dn,同時也會擷取/d1/d2/.../dn/leaf（全路徑）上read-lock或者write-lock。注意leaf節點可能是一個檔案或者是一個目錄，這個依賴于操作類型。

    我們描述一下當/home/user在snapshot成/save/user時，locking機制是如何阻止/home/user/foo檔案被建立的。Snapshot操作在/home和/save上擷取read-locks，在/home/user和/save/user上擷取write-locks。檔案建立操作在/home和/home/user上擷取read-locks，在/home/user/foo上擷取write-locks。這兩個操作将會被适當的序列化，因為他們都在嘗試在/home/user上擷取沖突的locks。建立檔案操作不需要在其父目錄上（parent directory）擷取write-locks。在名稱上的read-lock故意防止父目錄被删除。

    這種鎖模式的一個比較好的特性就是允許一個目錄下并發的變更。例如，在同一目錄下，允許多個檔案同時建立：每個操作都在目錄名稱上擷取一個read-lock，和檔案名稱上的write-lock。目錄名稱上的read-lock能夠阻止目錄被删除/重命名/snapshot。在file name上的write-lock序列化的去嘗試兩次建立新檔案（同一名稱的檔案，嘗試兩次）。

    因為namespace能有無數個nodes，read-write lock對象和它們相關連，并且在它們不用時删除（删除locks）。是以，locks的擷取是按照一緻的順序，以避免死鎖：它們（locks）以所在namespace tree的level作為第一排序，同一級别按照字典順序。

Replica placement：

    一個GFS的叢集是一個多級的高度分布式系統。它通常會有數百台chunkserver，分布在數個機架中。這些chunkservers輪流為來自相同的或者不同的racks上的用戶端提供通路服務。不同機架（racks）的2台機器通信可能會跨越多個網絡交換機。此外，一個機架上的出口和入口貸款可能比此機架上所有機器的整體帶寬要小。多極分布式出現一個獨特的挑戰：分布式資料的擴充性，可靠性，和可用性。

Creation，re-replication，rebalancing（replica的建立，重複制，重均衡）:

    chunk replicas建立的原因有三：chunk建立，重新複制，重新均衡。

    當master建立一個chunk，它将選擇放置這個初始為空的replicas的位置。它将考慮幾個因素：1）我們想把此replica放置在磁盤使用率低于平均值的chunkserver上 2）我們想限制每個chunkserver最近建立chunk的數量，雖然建立本身開支較小，它意味着即将有大量的write操作因為chunks的建立是由于有大量寫操作，并且在我們這種append-once-read-many的workload情況下，通常他們在寫入成功後，實際上就變成了隻讀。3）據上所述，我們想跨機架分布這些chunk replicas。

    當一個chunk的replicas的數量低于使用者制定的目标後，master就會re-replication這個chunk。有很多原因會觸發這種情況：一個chunkserver不可用，或者chunkserver報告自己replicas損壞，或者其中一個disk故障，或者使用者的replicas目标提高了。不過，每個需要re-replicated 的chunk的優先級基于幾個因素。一個是它（chunk）與replication目标的差距（即重複制的饑渴程度），例如失去2個replicas的chunk将比失去一個replicas的具有更高的優先級。此外，我們更傾向于首先re-replicate活躍的（現存的）chunk檔案，而不是剛剛删除檔案的chunk。最後，為了最小化故障的chunk對正在運作的系統的影響，我們提高那寫阻塞用戶端處理的chunk的優先級。

    master選擇優先級最高的chunk，通過告知一些chunkserver從現有的有效replicas中直接複制這個chunk資料的方式去“clone”（re-replication）.新的replicas的放置和他們的建立有相同的目标：均衡磁盤使用率，單個chunkserver限制活躍的clone操作數量，跨機架分布這些replicas。為了放置這種clone操作消耗傳輸量壓制client請求的傳輸量，master在cluster環境中和單個chunkserver都會限制活躍的clone操作數量。此外，每個chunkserver也會通過限制從source chunkserver中讀取量（clone時），來控制它clone操作的帶寬開支。

    最後，會周期性的reblances replicas：它會檢測目前replicas的分布情況，為了更好利用磁盤空間和負載均衡，它會遷移replicas。通過這個處理，master逐漸的填充一個新的chunkserver，而不是立即分發給它新的chunks，而造成随之而來的大量write操作。placement政策和建立replicas非常相似。此外，master也需要選擇哪個現有的replicas被删除。通常，它傾向于删除磁盤剩餘空間低于平均值的chunkserver的replicas，這也是為了均衡花磁盤使用率。

Garbage Collection:

    當一個檔案删除後，GFS不會立即回收其有效的實體存儲空間。GFS會回收它在延後的定期垃圾回收期間回收，無論是chunk和檔案級别。我們發現這種方式會讓系統更加簡單和可靠。

機制：

    當一個file被應用删除，master會其他變更操作一樣通過日志立即記錄這個删除操作。不過不是立即回收資源，這個檔案僅僅被重命名成一個隐藏的名字且包含删除的時間戳。在master定期掃描檔案系統namespace期間，它會删除這些隐藏的檔案（如果它們已經存在超過3天—這個值可以配置）。直到此時，file仍然可以在一個新的，特殊的命名的下read；也能夠在不删除的情況下把它重命名回正常，不過它的in-memory metadata會被清除。

    在定期掃描chunk namaspace時，master能夠識别孤立的chunks（任何file都無法到達—指向）并且清楚這些chunk的metadata。在master定期的heartBeat資訊交換中，每個chunkserver會報告它們所持有的chunks集合，master會把已經不在master metadata中的chunks的标示響應給chunkservers。Chunkserver可以随意的删除這些chunks的replicas。

讨論：

    雖然分布式的垃圾回收是一個難題，程式設計方面需要解決很多複雜的情況，但是在我們系統中，是相當的簡單。我們能夠很簡單的識别chunks的所有引用：它們在隻有master才持有的file-to-chunk映射中。我們也能很簡單的識别這些chunks replicas：它們是每個chunkserver中按照設計的目錄下的linux檔案。每個不能被master認知的replicas就是需要被回收的。

    垃圾回收的方式也存儲再利用的chunk，比起立即删除，有多個優點。第一，在元件故障很常見的高擴充性的分布式環境中，它是簡單和可用的。chunk的建立操作可能在部分chunkserver上成功，但是有些chunkserver上卻失敗了，留下了一些master不能發現其存在的replics。甚至replicas删除的消息也會丢失，master需要記住重發這些消息，無論是它自己的還是chunkserver的。回收機制提供了一個統一且可靠的方式來清除這些不被認知的chunks，這種方式很有用。第二,它把存儲重用（回收）并進master的定期的背景操作，像定期的namespaces掃描和chunkserver的握手一樣。是以它是批量處理的，開銷也是分攤的。此外，隻有當master負載相對較小時才會執行的。master就可以更快的相應client的請求。第三,這種可延遲回收存儲的方式，也可以一種安全的網絡避免偶爾的不可恢複的删除。

    在我們的經驗中，一個主要的缺點就是，當存儲空間比較tight（緊湊，或者不足時），這種延遲回收會阻礙我們去優化磁盤使用情況。應用重複的建立和删除臨時檔案或許不能正确的重用存儲空間。我們通過加速存儲回收的方式也應對這個問題，如果一個被删除的檔案再次被删除。我們允許使用者針對不同的namaspace部分，使用不同的replication和reclamation的政策。

例如，使用者能夠指定某個directory tree下的檔案的所有chunks存儲而無需replication，也可以指定任何删除的檔案立即且不可恢複的從檔案系統中删除。

Stale Replica delection：（過期replicas的删除）

    如果chunkserver故障，在此期間，它會丢失chunk的所有變更操作，那麼此chunk也變成了stale（過期）。對于每個chunk，master儲存了chunkser version number，來區分實時的（最新的）和過期的replicas。

    一旦master給chunk授權lease，它（primary）增加chunk version number并且會通知up-to-date replicas。Master和這些replicas都會在她們的持久化狀态中記錄這個新的version number。這個動作（新增版本号）是在告知用戶端之前發生，也就是在它（chunk）開始寫入之前發生。如果其他的replicas目前不可用，那麼它的chunk version number将不會再增長了。那麼在chunkserver重新開機後，報告它的chunks集合和這些chunks的版本号時，master就會檢測到這個chunkserver中有一個過期的replicas。如果master發現一個比自己的記錄更高的版本号，它會認為在授權lease的時（該回收的lease沒有回收成功）失敗了，它就會采取這個較高的版本号做為最新的。

    master會在其定期的垃圾回收來删除這些過期的replicas。在删除之前，它（master）會檢查這些過期的replicas不會包含在它響應給client的chunk資訊中。作為應一個安全防護，master會在它告知client哪個chunkserver持有chunk lease時，或者它在複制操作中指派chunkserver從另一個chunkserver中讀取chunk資料時，都會包含這個chunk 的version number。client或者chunkserver會在它執行操作是校驗這個版本号，是以它總是通路最新的資料。

Fault tolerance and Diagnosis(容錯和故障診斷):

    這個系統設計的最大挑戰就是處理頻繁的元件故障。元件的數量和品質讓這個問題：我們不能完全信任這些機器，也不能完全信任磁盤，元件故障可能會造成系統不可用，甚至資料損壞。我讨論我們是如何解決這些問題的，以及系統内置的一些工具來檢測出現的問題。

High avialability：（高可用性）

    在具有數百台機器的GFS分布式環境中，任何時候都有可能有機器不可用。我們采用2中簡單有效的政策保持系統的高可用行：快速恢複/複制

  快速恢複:

    無論是master還是chunkserver都是設計成儲存他們的狀态，并且在數秒内啟動無論他們是如何終止的。事實上，我們是不會區分正常和非正常終止。Servers僅僅是通過殺死程序的方式來shut down（挺掉服務）。client和其他servers會經曆一次小的振蕩，當他們的請求逾時，然後重試。（意思：GFS server終止後，請求會逾時，然後用戶端會嘗試重新連接配接，重試操作。。）接下來講解。。

    chunk replication：

    每個chunk會被replicated在不同的機架上不同的chunkserver中。使用者能夠對不同的namespace部分，指定不同的replicate級别。預設是3.master會根據需要來保持每個chunk能夠全量的replicated，當chunkserver下線或者通過校驗和檢測出損壞的資料。

    Master replication：

    master狀态為了可靠性也需要replicated(和master有關的資料replicated，而不是多master 拓撲).它的checkpoints和記錄檔是replicated在多個機器上。一個狀态的變更認為是送出的，隻有當它的日志記錄重新整理到本地硬碟和所有的master replicas。簡單來說，master程序負責所有的變更，包括一些背景活動，例如垃圾回收這樣的内部活動。當master故障，可以在短時間内重新開機。如果它的機器或者硬碟出現故障，GFS外部的監控機制會在operation log分布的replicas機器上啟動一個新的master程序。client隻使用規範的master的名稱（例如gfs-test）,這（gfs-test）是一個DNS别名，當master被定向到其他機器時它也能随着改變。

    此外，“shadow”master（slaver？可以認為非主master）提供了對檔案系統的隻讀的操作，即使primary master失效。它們是“shadow”，不是mirrors（影像），它們通常比primary略微落後,通常是幾分之一秒.它們提高了檔案的read的性能,對那些變更相對不活躍或者應用不在乎擷取一個稍微過期的結果(shadow的延遲).這些過期的結果原因(這麼極短的時間内),主要是檔案的metadata的變更,例如目錄内容或者存取控制等.

    為了保持自己狀态是更新的(時刻被跟進),一個shadow master讀取replicas中不斷增長的operation log,并且按照和master相同的序列去應用這些資料結構的變更.和primary master一樣,每個shadow master也會在啟動時去poll chunkserver擷取replicas位置資訊/交換handshake消息來監控他們的狀态.它僅僅依賴于primary master對replicas的位置更新(primary負責對replicas的建立/位置重配置設定等).

GFS論文整理(一):[http://shift-alt-ctrl.iteye.com/blog/1842245]

GFS論文整理(二):[http://shift-alt-ctrl.iteye.com/blog/1842286]

GFS論文整理(四):[http://shift-alt-ctrl.iteye.com/blog/1842510]