課件04多結(jié)構(gòu)化數(shù)據(jù)管理googleGFS1

1、數(shù)據(jù)存儲與組織方法 現(xiàn)有技術(shù)（Google GFS）2 23GFS幾百甚至幾千臺普通的廉價設(shè)備組裝的存儲機群， 同時被相當數(shù)量的客戶機訪問。文件可能非常巨大（數(shù)GB的文件非常普遍），每個文件通常都包含許多應(yīng)用程序?qū)ο螅ɡ鐆eb文檔、微博）。經(jīng)常需要處理快速增長的、并且由數(shù)億個對象構(gòu)成的、數(shù)以TB的數(shù)據(jù)集。絕大部分的修改是在文件尾部追加數(shù)據(jù)，而不是覆蓋原有數(shù)據(jù)。一旦寫完之后，對文件的操作就只有讀，而且通常是按順序讀。3 組件失效 是常態(tài)而不是意外事件（任何給定時間內(nèi)都有可能發(fā)生某些組件無法工作、無法從它們目前的失效狀態(tài)中恢復(fù)）。 放松了對一致性模型的要求，引入了原子性的記錄追加操作，從而保證多

2、個客戶端能同時進行追加操作，不需要額外的同步操作來保證數(shù)據(jù)的一致性。45Chunk：文件都被分割成固定大小的Chunk。 Chunk創(chuàng)建時，Master服務(wù)器會給每個Chunk分配一個不變的、全球唯一的64位的Chunk標識。Namespace：GFS提供了一套類似傳統(tǒng)文件系統(tǒng)的API接口函數(shù)（沒有嚴格按照POSIX等標準API的形式實現(xiàn)），文件以分層目錄的形式組織，用路徑名來標識。 在邏輯上，GFS的名稱空間就是一個全路徑和元數(shù)據(jù)映射關(guān)系的查找表。5大塊1）利用前綴壓縮，namespace表高效的存儲在內(nèi)存中。2）在存儲名稱空間的樹型結(jié)構(gòu)上，每個節(jié)點（絕對路徑的文件名或絕對路徑的目錄名）都有

3、一個關(guān)聯(lián)的讀寫鎖。不同于許多傳統(tǒng)文件系統(tǒng)，GFS沒有針對每個目錄實現(xiàn)能夠列出目錄下所有文件的數(shù)據(jù)結(jié)構(gòu)，GFS也不支持文件或者目錄的鏈接（即Unix術(shù)語中的硬鏈接或者符號鏈接）。6元數(shù)據(jù)的存儲與訪問機制7Chunkserver：Chunk服務(wù)器把Chunk以linux文件的形式保存在本地硬盤上，并且根據(jù)指定的Chunk標識和字節(jié)范圍來讀寫塊數(shù)據(jù)。 可靠性 每個塊都會復(fù)制到多個chunkserver上（缺省3個存儲復(fù)制節(jié)點）。 用戶可以為不同的文件命名空間區(qū)域設(shè)定不同的復(fù)制級別。78Master：GFS分布式文件系統(tǒng)中的總控節(jié)點。u執(zhí)行所有的namespace操作。u管理整個系統(tǒng)里所有Chunk的

4、副本決定Chunk的存儲位置創(chuàng)建新Chunk和它的副本協(xié)調(diào)各種系統(tǒng)活動以保證Chunk被完全復(fù)制在所有的Chunk服務(wù)器之間進行負載均衡回收不再使用的存儲空間8 Master管理所有的文件系統(tǒng)元數(shù)據(jù)：Namespace訪問控制信息文件和Chunk的映射信息Chunk當前的位置信息Master節(jié)點還管理著系統(tǒng)范圍內(nèi)的活動：Chunk租約管理孤兒Chunk(orphaned chunks)的回收Chunk在Chunk服務(wù)器之間的遷移。910一個GFS集群包含一個邏輯上單獨的Master節(jié)點（Master組件）。 物理上有Master節(jié)點復(fù)制機制，為便于理解，可認為一個邏輯的Master節(jié)點包括兩臺

5、物理主機，即兩臺Master服務(wù)器。 與Chunk服務(wù)器通訊？ Master節(jié)點使用心跳信息周期地和每個Chunk服務(wù)器通訊，發(fā)送指令到各個Chunk服務(wù)器并接收Chunk服務(wù)器的狀態(tài)信息。1011Client：GFS客戶端實現(xiàn)了GFS文件系統(tǒng)的API接口函數(shù)，代碼以庫的形式被鏈接到客戶程序里。應(yīng)用程序與Master節(jié)點和Chunk服務(wù)器通訊，對數(shù)據(jù)進行讀寫操作。 客戶端和Master節(jié)點的通信只獲取元數(shù)據(jù)，所有的數(shù)據(jù)操作都是由客戶端直接和Chunk服務(wù)器進行交互的。11Data message Control message1212DHT?MEMCACHE? 13Master存儲3種主要類型

6、的元數(shù)據(jù)： 文件和Chunk的命名空間 文件和Chunk的對應(yīng)關(guān)系 每個Chunk副本的存放地點Master不持久保存Chunk位置信息 在啟動或者有新的Chunk服務(wù)器加入時，向各個Chunk服務(wù)器輪詢它們所存儲的Chunk信息，并通過周期性的心跳信息監(jiān)控Chunk服務(wù)器的狀態(tài)。13內(nèi)存中14 Master在啟動和之后定期輪詢Chunk服務(wù)器及其更新的設(shè)計簡化了Master和Chunk服務(wù)器數(shù)據(jù)同步的問題（在一個有數(shù)百臺服務(wù)器的集群中，這類事件會頻繁的發(fā)生：有Chunk服務(wù)器加入/離開集群、更名、失效、重啟）。14只有Chunk服務(wù)器才能最終確定一個Chunk是否在它的硬盤上，Chunk服務(wù)

7、器的錯誤可能會導(dǎo)致Chunk自動消失(如硬盤損壞或無法訪問)，或者操作人員會重命名一個Chunk服務(wù)器。 不在Master上持久化維護這些信息的全局視圖。15 兩種類型的元數(shù)據(jù)（命名空間、文件和Chunk的對應(yīng)關(guān)系）同時也會以變更日志的方式記錄在操作系統(tǒng)的系統(tǒng)日志文件（存儲在本地磁盤）中，該日志同時被復(fù)制到其它的遠程Master服務(wù)器上。 系統(tǒng)能簡單可靠的更新Master服務(wù)器的狀態(tài)，不用擔心Master服務(wù)器崩潰導(dǎo)致數(shù)據(jù)不一致的風險。15有什么數(shù)據(jù)？數(shù)據(jù)的邏輯組成？16 Chunk的數(shù)量以及整個系統(tǒng)的承載能力都受限于Master的內(nèi)存大小，實際應(yīng)用中的容量很大。1）Master只需不到64個

8、字節(jié)的元數(shù)據(jù)就能管理一個64MB的Chunk。2）大多數(shù)文件都包含多個Chunk，因此絕大多數(shù)Chunk都是滿的（除了文件的最后一個Chunk）。3）同樣，一個文件在命名空間中的數(shù)據(jù)大小通常在64字節(jié)以下（文件名保存使用前綴壓縮算法）。 即便要支持更大的文件系統(tǒng)，為Master服務(wù)器增加額外內(nèi)存的費用也是值得的。1617 Master和客戶端都會緩存元數(shù)據(jù)。 客戶端和Chunk服務(wù)器都不緩存文件數(shù)據(jù)，簡化了客戶端和整個系統(tǒng)的設(shè)計和實現(xiàn)。 大部分程序要么以流的方式讀取一個巨大文件，要么工作集太大根本無法被緩存 客戶端緩存文件數(shù)據(jù)意義不大。 Chunk以本地文件的方式保存， Linux操作系統(tǒng)的文

9、件系統(tǒng)緩存會把經(jīng)常訪問的數(shù)據(jù)緩存在內(nèi)存中 Chunk服務(wù)器不緩存文件數(shù)據(jù)。17181）客戶端將文件名和程序指定的字節(jié)偏移根據(jù)固定的Chunk大小轉(zhuǎn)換成文件的Chunk索引，進而把文件名和Chunk索引發(fā)送給Master節(jié)點。2）Master節(jié)點將相應(yīng)的Chunk標識和副本的位置信息發(fā)還給客戶端?？蛻舳擞梦募虲hunk索引作為key緩存這些信息，之后客戶端發(fā)送請求（包含Chunk的標識和字節(jié)范圍）到其中的一個副本處（一般會選擇最近的）。3）Chunkserver讀取chunk數(shù)據(jù)返回客戶端。18 在開始了對Chunk的數(shù)據(jù)讀取操作后，客戶端不必再和Master節(jié)點通訊，除非緩存的元數(shù)據(jù)信息過

10、期或者文件被重新打開。 實際過程中，客戶端通常會在一次請求中查詢多個Chunk信息，Master節(jié)點的回應(yīng)也可能包含了被請求的Chunk的后續(xù)Chunk的信息。 同樣代價額外元數(shù)據(jù)，避免客戶端和Master節(jié)點未來可能會發(fā)生的幾次通訊。1920 Master節(jié)點可通過全局的信息精確定位Chunk的位置并制定復(fù)制決策。單一Master節(jié)點的策略簡化了設(shè)計。 必須減少對Master節(jié)點的讀寫（避免Master節(jié)點成為系統(tǒng)的瓶頸）：1）客戶端不通過Master節(jié)點讀寫文件數(shù)據(jù)，僅向Master節(jié)點詢問它應(yīng)該聯(lián)系的Chunk服務(wù)器；2）客戶端將這些元數(shù)據(jù)信息緩存一段時間；3）后續(xù)的數(shù)據(jù)讀寫操作直接對C

11、hunk服務(wù)器進行。2021惰性分配策略：每個Chunk（副本）都以普通Linux文件的形式保存在Chunk服務(wù)器上，只在需要的時候才擴大。 避免因內(nèi)部碎片造成的空間浪費。 Chunk的大小是關(guān)鍵的設(shè)計參數(shù)之一，設(shè)置為64MB這個遠遠大于一般文件系統(tǒng)的Block尺寸存在著爭議。2122優(yōu)點：1）選用較大的Chunk尺寸減少了Master節(jié)點需要保存的元數(shù)據(jù)的數(shù)量，有利于元數(shù)據(jù)全部放在內(nèi)存中。2）采用較大的Chunk尺寸，客戶端能對一個塊進行多次操作，從而通過與Chunk服務(wù)器保持較長時間的TCP連接來減少網(wǎng)絡(luò)負載。3）減少了客戶端和Master節(jié)點通訊的需求（應(yīng)用程序通常連續(xù)讀寫大文件），客戶

12、端可以輕松緩存一個數(shù)TB的工作數(shù)據(jù)集所擁有的Chunk位置信息。2223缺點： 小文件包含較少的Chunk(甚至只有一個Chunk)。當有許多的客戶端對同一個小文件進行多次的訪問時，存儲這些Chunk的Chunk服務(wù)器就會變成熱點。實例：當GFS用于批處理隊列系統(tǒng) 熱點問題。例：一個可執(zhí)行文件在GFS上保存單一chunk文件，之后這個可執(zhí)行文件在數(shù)百臺機器上同時啟動。 存放這個可執(zhí)行文件的幾個Chunk服務(wù)器被數(shù)百個客戶端并發(fā)請求訪問，導(dǎo)致系統(tǒng)局部過載。2324 存放某個可執(zhí)行文件的幾個Chunk服務(wù)器被數(shù)百個客戶端的并發(fā)請求訪問導(dǎo)致系統(tǒng)局部過載。解決方法：1）使用更大的復(fù)制參數(shù)來保存可執(zhí)行文

13、件；2）錯開批處理隊列系統(tǒng)程序的啟動時間；3）允許客戶端從其它客戶端讀取數(shù)據(jù)。2425 操作日志包含元數(shù)據(jù)變更歷史記錄：1）是元數(shù)據(jù)唯一的持久化存儲記錄；2）是作為判斷同步操作順序的邏輯時間基線（邏輯日志序號作為操作發(fā)生的邏輯時間，類似于事務(wù)系統(tǒng)中的LSN）。 文件和Chunk（連同它們的版本）都由它們創(chuàng)建的邏輯時間唯一的、永久的標識。25261）確保日志文件是完整的且元數(shù)據(jù)的變化被持久化后，日志才對客戶端是可見的。否則，即使Chunk本身沒有出現(xiàn)問題，仍有可能丟失整個文件系統(tǒng)（或者客戶端最近的操作）。2）日志會復(fù)制到多臺遠程機器，只有相應(yīng)的日志記錄寫入到本地以及遠程機器的硬盤后，才會響應(yīng)客戶

14、端的操作請求。3）Master服務(wù)器會收集多個日志記錄后批量處理，以減少寫入磁盤和復(fù)制對系統(tǒng)整體性能的影響。2627災(zāi)難恢復(fù)時，Master通過重演操作日志把文件系統(tǒng)恢復(fù)到最近的狀態(tài)。帶來的問題：從日志頭開始恢復(fù)（日志過長）?解決方法：checkpoint，減少重演操作的日志量。2728日志增長到一定量 Master對系統(tǒng)狀態(tài)做一次Checkpoint，將所有的狀態(tài)數(shù)據(jù)寫入一個Checkpoint文件（并刪除之前的日志文件）?；謴?fù)：Master從磁盤上讀取最新的Checkpoint文件，重演Checkpoint之后的有限個日志文件便可恢復(fù)系統(tǒng)。Checkpoint文件存儲：壓縮B-樹形式。可以

15、直接映射到內(nèi)存，在用于命名空間查詢時無需額外的解析，從而大大提高恢復(fù)速度，增強可用性。2829checkpoint過程不阻塞正在進行的修改操作：Master使用獨立的線程切換到新的日志文件和創(chuàng)建新的Checkpoint文件。 新的Checkpoint文件包括切換前所有的修改（對于一個包含數(shù)百萬個文件的集群，創(chuàng)建一個Checkpoint文件需要1分鐘左右）。 創(chuàng)建完成后，Checkpoint文件會被寫入在本地和遠程的硬盤里。 舊的Checkpoint文件和日志文件可以被刪除，但是為了應(yīng)對災(zāi)難性的故障，通常會多保存一些歷史文件。2930GFS必須將對數(shù)據(jù)塊的修改同步到每一個副本。 多個應(yīng)用可能同時

16、修改同一數(shù)據(jù)塊 必須為修改操作定義統(tǒng)一的時序，否則多個副本會出現(xiàn)不一致的情況。誰來定義時序？由于采用了元數(shù)據(jù)緩存機制（為減少master的負擔，client在獲得副本位置后就不再和master交互），誰來定義時序？30需要有人代替master的角色 選出一個master代理來完成時序約定任務(wù)。 租約（lease）機制：master將租約授權(quán)給某個副本，稱其為primary，由它來確定數(shù)據(jù)修改的順序，其它副本照做。313232331)客戶機向Master節(jié)點詢問哪個Chunk服務(wù)器持有當前租約，以及其它副本的位置。 如果沒有Chunk持有租約，Master就選擇其中一個副本建立一個租約。342)

17、Master將主Chunk的標識符以及其它副本（secondary副本/二級副本）的位置返回給客戶機?？蛻魴C緩存這些數(shù)據(jù)以便后續(xù)操作。此后只有在主Chunk不可用或主Chunk回復(fù)信息表明它已不再持有租約時，客戶機才重新聯(lián)系Master節(jié)點。353）客戶機把數(shù)據(jù)推送到所有的副本上（可按任意的順序推送）。Chunk服務(wù)器接收到數(shù)據(jù)并保存在它的內(nèi)部LRU緩存中，直到數(shù)據(jù)被使用或過期交換出去。364）當所有的副本都確認收到了數(shù)據(jù)后，客戶機發(fā)送寫請求到主Chunk服務(wù)器。主Chunk為接收到的所有操作分配連續(xù)的序列號（這些操作可能來自不同的客戶機，序列號保證了操作順序執(zhí)行），它以序列號的順序把操作應(yīng)用

18、到它自己的本地狀態(tài)中（主Chunk順序執(zhí)行這些操作，并更新自己的狀態(tài)）。375）主Chunk把寫請求傳遞到所有的二級副本。每個二級副本依照主Chunk分配的序列號以相同的順序執(zhí)行這些操作。6）所有的二級副本回復(fù)主Chunk“它們已經(jīng)完成了操作”。387）主Chunk服務(wù)器回復(fù)客戶機（任何副本產(chǎn)生的任何錯誤都會返回給客戶機）。 出現(xiàn)錯誤時，寫操作可能在主Chunk和一些二級副本執(zhí)行成功。（如果主Chunk上操作失敗，操作不會被分配序列號，也不會傳遞）客戶端請求被確認為失敗，被修改的region處于不一致狀態(tài)。客戶機代碼通過重復(fù)執(zhí)行失敗的操作來處理這樣的錯誤。在從頭開始重復(fù)執(zhí)行之前，客戶機會先嘗試

19、幾次步驟（3）（7）。39應(yīng)用程序一次寫入的數(shù)據(jù)量較大，或者數(shù)據(jù)跨越了多個Chunk。 客戶機代碼會把它們分成多個寫操作。這些操作都遵循上述控制流程，但可能會被其它客戶機上同時進行的操作打斷或者覆蓋。 共享的文件region的尾部可能包含來自不同客戶機的數(shù)據(jù)片段。 盡管如此，由于這些分解后的寫入操作在所有的副本上都以相同的順序執(zhí)行完成，Chunk的所有副本都是一致的。40GFS提供原子性的數(shù)據(jù)追加操作記錄追加（一種特殊的修改操作），遵循一般的寫操作控制流程（除了在主Chunk有些額外的控制邏輯）：1）客戶機把數(shù)據(jù)推送給文件最后一個Chunk的所有副本。2）發(fā)送請求給主Chunk。3）主Chun

20、k檢查這次記錄追加操作是否會使Chunk超過最大尺寸（64MB）。如果超過則主Chunk先將當前Chunk填充到最大尺寸，之后通知所有二級副本做同樣的操作，然后回復(fù)客戶機要求其對下一個Chunk重新進行記錄追加操作。41 記錄追加：客戶機只需指定要寫入的數(shù)據(jù)，GFS保證至少有一次原子的寫入操作成功執(zhí)行（寫入一個順序的byte流），寫入的數(shù)據(jù)追加到GFS指定的偏移位置上，之后GFS返回這個偏移量給客戶機。 如果記錄追加操作在任何一個副本上失敗了，客戶端就需要重新進行操作。 重新記錄追加一個Chunk的不同副本可能包含不同的數(shù)據(jù)（重復(fù)包含一個記錄全部或者部分的數(shù)據(jù)）。GFS并不保證Chunk的所有

21、副本在字節(jié)級別是完全一致的，它只保證數(shù)據(jù)作為一個整體原子的被至少寫入一次。42 GFS支持一個寬松的一致性模型，能很好的支撐高度分布的應(yīng)用。文件命名空間的修改（如文件創(chuàng)建） （一致性重要）僅由Master節(jié)點控制，命名空間鎖提供原子性和正確性，Master節(jié)點的操作日志定義些操作在全局的順序。 文件region？43兩個概念：一致的如果所有客戶端無論從哪個副本讀取，讀到的數(shù)據(jù)都一樣，那么認為文件region是“一致的”。已定義的如果對文件的數(shù)據(jù)修改之后，region是一致的，并且客戶端能夠看到寫入操作全部的內(nèi)容，那么這個region是“已定義的”。44 數(shù)據(jù)修改成功執(zhí)行且沒有受到同時執(zhí)行的其它

22、寫操作的干擾，則影響的region就是已定義的（隱含了一致性）。 并行修改操作成功完成之后，region處于一致的、未定義的狀態(tài)：所有的客戶端看到同樣的數(shù)據(jù)，但可能無法讀到寫入的全部數(shù)據(jù)。 通常情況下，文件region內(nèi)包含了來自多個修改操作的、混雜的數(shù)據(jù)片段寫記錄追加串行成功已定義已定義部分不一致（寬松）并行成功一致但是未定義失敗不一致45 另一種典型的應(yīng)用： 許多應(yīng)用程序并行的追加數(shù)據(jù)到同一個文件（例如進行結(jié)果的合并或者是一個生產(chǎn)者-消費者隊列）。 記錄追加方式的“至少一次追加”特性 保證了Writer的輸出。 Writers在每條寫入的記錄中都包含了額外的信息，例如Checksum，用來

23、驗證它的有效性。 Readers可以利用Checksum識別和拋棄偶然性的填充數(shù)據(jù)和重復(fù)內(nèi)容。 如果應(yīng)用不能容忍偶爾的重復(fù)內(nèi)容，可以用記錄的唯一標識符來過濾它們。 唯一標識符通常用于命名程序中處理的實體對象（例如web文檔）。 這些記錄I/O功能（除了剔除重復(fù)數(shù)據(jù)）都包含在程序共享的庫中，適用于Google內(nèi)部的其它的文件接口實現(xiàn)。所以，相同序列的記錄（加上一些偶爾出現(xiàn)的重復(fù)數(shù)據(jù)）都被分發(fā)到Reader了。4647 經(jīng)過了一系列的成功的修改操作之后，GFS確保被修改的文件region是已定義的，并且包含最后一次修改操作寫入的數(shù)據(jù)。 GFS通過以下措施確保上述行為：（a）對Chunk的所有副本的

24、修改操作順序一致；（b）使用Chunk的版本號來檢測副本是否因為它所在的Chunk服務(wù)器宕機而錯過了修改操作而導(dǎo)致其失效。失效的副本不會再進行任何修改操作，Master服務(wù)器也不再返回這個Chunk副本的位置信息給客戶端，它會被垃圾收集系統(tǒng)盡快回收。48Chunk位置信息會被客戶端緩存 在緩存的超時時間和文件下一次被打開的時間之間存在一個時間窗，在信息刷新前，客戶端有可能從一個失效的副本讀取了數(shù)據(jù)。 文件再次被打開后會清除緩存中與該文件有關(guān)的所有Chunk位置信息。文件大多數(shù)都是只進行追加操作的 一個失效的副本通常返回一個提前結(jié)束的Chunk而不是過期的數(shù)據(jù)。 當一個Reader重新嘗試并聯(lián)絡(luò)

25、Master服務(wù)器時，它就會立刻得到最新的Chunk位置信息。4950 修改操作成功執(zhí)行很長時間之后，組件的失效可能損壞或者刪除數(shù)據(jù)。 GFS通過Master服務(wù)器和所有Chunk服務(wù)器的定期“握手”來找到失效的Chunk服務(wù)器，并且使用Checksum來校驗數(shù)據(jù)是否損壞。 發(fā)現(xiàn)問題則盡快利用有效的副本恢復(fù)數(shù)據(jù)。只有當一個Chunk的所有副本在GFS檢測到錯誤并采取應(yīng)對措施之前全部丟失，這個Chunk才會不可逆轉(zhuǎn)的丟失。51應(yīng)用請求：對一個文件或者目錄樹做一個拷貝 快照操作 幾乎瞬間完成，幾乎不會對正在進行的其它操作造成任何干擾。 用戶可使用快照迅速創(chuàng)建一個巨大數(shù)據(jù)集的分支拷貝，或使用快照操作

26、備份當前狀態(tài)，之后可以輕松的提交或者回滾到備份時的狀態(tài)。52實現(xiàn)技術(shù)：copy-on-write。1）Master節(jié)點收到快照請求，取消做快照的文件的所有Chunk的租約（使后續(xù)對這些Chunk的寫操作都必須與Master交互以找到租約持有者，從而給Master一個率先創(chuàng)建Chunk的新拷貝的機會）。2）租約取消或過期之后，Master把操作以日志的方式記錄到硬盤上，然后通過復(fù)制源文件或者目錄的元數(shù)據(jù)的方式，把這條日志記錄的變化反映到內(nèi)存的狀態(tài)中。新創(chuàng)建的快照文件和源文件指向完全相同的Chunk地址。53 快照操作后，當客戶機第一次想寫入數(shù)據(jù)到相關(guān)Chunk C時：1）它會先發(fā)送請求到Mast

27、er查詢當前的租約持有者。2）Master通過發(fā)現(xiàn)Chunke C的引用計數(shù)超過了1，會選擇一個新的Chunk句柄C。3）Master要求每個擁有Chunk C當前副本的Chunk服務(wù)器在本地創(chuàng)建一個叫做C的新Chunk。 本地復(fù)制使得寫請求的處理方式和任何其它Chunk沒什么不同。 Master節(jié)點確保新Chunk C的一個副本擁有租約并回復(fù)客戶機，客戶機得到回復(fù)后就可以正常的寫這個Chunk。54Master節(jié)點的每個操作在開始之前都要獲得一系列的鎖。例：一個寫操作涉及/d1/d2/dn/leaf，那么它首先要獲得目錄/d1，/d1/d2，/d1/d2/dn的讀鎖，以及/d1/d2/dn/

28、leaf的讀寫鎖。注意：leaf可以是一個文件，也可以是一個目錄。 因為名稱空間可能有很多節(jié)點，讀寫鎖采用惰性分配策略，并且在不再使用時立刻刪除。 避免死鎖：鎖的獲取依據(jù)一個全局一致的順序，首先按名稱空間的層次排序，在同一個層次內(nèi)按字典順序排序。順序封鎖法55特點： 讀寫鎖支持對同一目錄的并行操作，可以在同一個目錄下同時創(chuàng)建多個文件（每一個操作都獲取一個目錄名的上的讀取鎖和文件名上的寫入鎖）。 目錄名的讀取鎖防止目錄被刪除、改名以及被快照。 文件名的寫入鎖序列化文件創(chuàng)建操作，確保不會多次創(chuàng)建同名的文件。56例：/home/user被快照到/save/user，并且需要創(chuàng)建文件foo。 此時應(yīng)防

29、止創(chuàng)建文件/home/user/foo。 快照操作獲取/home和/save的讀取鎖，以及/home/user和/save/user的寫入鎖。 文件創(chuàng)建操作獲得/home和/home/user的讀取鎖，以及/home/user/foo的寫入鎖。 這兩個操作只能串行執(zhí)行（因為它們試圖獲取的/home/user的鎖相互沖突）。57Chunk在Writer真正寫入數(shù)據(jù)時才被創(chuàng)建。Master創(chuàng)建一個Chunk時，需要選擇在哪里放置初始的空副本，考慮幾個因素：（1）盡量選擇低于平均硬盤使用率的Chunk服務(wù)器。（2）限制每個Chunk服務(wù)器上”最近”的Chunk創(chuàng)建操作的次數(shù)。雖然Chunk在Writ

30、er真正寫入數(shù)據(jù)時才被創(chuàng)建，但是創(chuàng)建也意味著隨之會有大量的寫入數(shù)據(jù)的操作。（3）盡量把Chunk的副本分布在多個機架之間。58Chunk的有效副本數(shù)量少于用戶指定的復(fù)制因數(shù)時（某些副本壞了，或者Chunk副本的復(fù)制因數(shù)提高了） Master會重新復(fù)制它。需要被重新復(fù)制的Chunk會根據(jù)幾個因素進行排序：（1）Chunk現(xiàn)有副本數(shù)量和復(fù)制因數(shù)相差多少（丟失兩個副本的Chunk比丟失一個副本的Chunk優(yōu)先級更高）。（2）優(yōu)先復(fù)制活躍文件的Chunk而不是最近剛被刪除的文件的Chunk（和垃圾回收相關(guān)）。（3）提高會阻塞客戶機程序處理流程的Chunk的優(yōu)先級。59 Master選擇優(yōu)先級最高的Ch

31、unk，然后命令某個Chunk服務(wù)器直接從可用的副本”克隆”一個副本出來。 選擇新副本的位置的策略和創(chuàng)建時類似：平衡硬盤使用率、限制同一臺Chunk服務(wù)器上的正在進行的克隆操作的數(shù)量、在機架間分布副本。 為防止克隆產(chǎn)生的網(wǎng)絡(luò)流量大大超過客戶機的流量：1）Master限制整個集群和每個Chunk服務(wù)器上的同時進行的克隆操作的數(shù)量。2）Chunk服務(wù)器通過調(diào)節(jié)它對源Chunk服務(wù)器讀請求的頻率來限制它用于克隆操作的帶寬。60 Master周期性地對副本進行負載均衡：檢查當前副本分布情況，然后移動副本以更好的利用硬盤空間、更有效的進行負載均衡。 Master必須選擇哪個副本要被移走：1）通常移走剩余

32、空間低于平均值的Chunk服務(wù)器上的副本，從而平衡系統(tǒng)整體的硬盤使用率。2）Master逐漸的填滿一個新的Chunk服務(wù)器，而不是在短時間內(nèi)用新的Chunk填滿它，以至于過載。61惰性： GFS在文件刪除后不會立刻回收可用的物理空間，采用惰性的回收策略，只在文件和Chunk級的常規(guī)垃圾收集時進行。日志、隱藏： 當文件被應(yīng)用程序刪除時，Master立刻把刪除操作以日志的方式記錄下來。但是，Master并不馬上回收資源，而是把文件名改為一個包含刪除時間戳的、隱藏的名字?；厥眨?當Master對文件系統(tǒng)命名空間做常規(guī)掃描時，它會刪除所有三天前的隱藏文件（時間間隔可設(shè)置）。直到文件被真正刪除，它們?nèi)耘f

33、可以用新的特殊的名字讀取，也可以通過把隱藏文件改名為正常顯示的文件名的方式“反刪除”。孤立： 當隱藏文件被從名稱空間中刪除，Master內(nèi)存中保存的這個文件的相關(guān)元數(shù)據(jù)才會被刪除。這也有效的切斷了文件和它包含的所有Chunk的連接。6263 在對Chunk名字空間做類似的常規(guī)掃描時，Master找到孤兒Chunk（不被任何文件包含的Chunk）并刪除它們的元數(shù)據(jù)。 Chunk服務(wù)器在和Master交互的心跳信息中，報告它擁有的Chunk子集的信息，Master節(jié)點回復(fù)Chunk服務(wù)器哪些Chunk在Master節(jié)點保存的元數(shù)據(jù)中已經(jīng)不存在了。Chunk服務(wù)器可以任意刪除這些Chunk的副本。6

34、4 當Chunk服務(wù)器失效時，Chunk的副本可能因錯失了一些修改操作而過期失效。 Master保存每個Chunk的版本號以區(qū)分當前副本和過期副本，客戶機或者Chunk服務(wù)器在執(zhí)行操作時都會驗證版本號以確保總是訪問當前版本的數(shù)據(jù)。保護措施：1）過期副本被回收之前，Master在回復(fù)客戶機的Chunk信息請求時會認為那些過期的Chunk不存在。2）Master在例行垃圾回收時移除所有的過期失效副本。3）Master在通知客戶機某個Chunk服務(wù)器持有租約、或者指示從哪個Chunk服務(wù)器進行克隆時，消息中都附帶了Chunk的版本號。6566當Master節(jié)點和Chunk簽訂一個新租約時 它會增加Chunk的版本號，然后通知最新的副本。 Mast