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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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