網(wǎng)絡存儲2-Z-海量存儲示例

示例2023/2/112023/2/122023/2/132023/2/142023/2/152023/2/162023/2/172023/2/182023/2/192023/2/1102023/2/111秘密武器：云計算平臺！Google業(yè)務全球最大搜索引擎、GoogleMaps、GoogleEarth、Gmail、YouTube等數(shù)據(jù)量巨大，且面向全球用戶提供實時服務

Google云計算平臺技術架構(gòu)文件存儲，GoogleDistributedFileSystem，GFS并行數(shù)據(jù)處理MapReduce分布式鎖Chubby分布式結(jié)構(gòu)化數(shù)據(jù)表BigTable分布式存儲系統(tǒng)Megastore分布式監(jiān)控系統(tǒng)Dapper

提綱Google文件系統(tǒng)GFS分布式數(shù)據(jù)處理MapReduce

分布式鎖服務Chubby

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

分布式存儲系統(tǒng)Megastore大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構(gòu)DapperGoogle應用程序引擎Google文件系統(tǒng)GFS系統(tǒng)架構(gòu)容錯機制系統(tǒng)管理技術GFS設計動機Google需要一個支持海量存儲的文件系統(tǒng)購置昂貴的分布式文件系統(tǒng)與硬件？是否可以在一堆廉價且不可靠的硬件上構(gòu)建可靠的分布式文件系統(tǒng)？GFS設計動機為什么不使用當時現(xiàn)存的文件系統(tǒng)？Google所面臨的問題與眾不同

不同的工作負載，不同的設計優(yōu)先級（廉價、不可靠的硬件）需要設計與Google應用和負載相符的文件系統(tǒng)GFS將容錯的任務交給文件系統(tǒng)完成，利用軟件的方法解決系統(tǒng)可靠性問題，使存儲的成本成倍下降。GFS將服務器故障視為正常現(xiàn)象，并采用多種方法，從多個角度，使用不同的容錯措施，確保數(shù)據(jù)存儲的安全、保證提供不間斷的數(shù)據(jù)存儲服務

GFS架構(gòu)是怎樣的？系統(tǒng)架構(gòu)Client（客戶端）：應用程序的訪問接口

Master（主服務器）：管理節(jié)點，在邏輯上只有一個，保存系統(tǒng)的元數(shù)據(jù)，負責整個文件系統(tǒng)的管理ChunkServer（數(shù)據(jù)塊服務器）：負責具體的存儲工作。數(shù)據(jù)以文件的形式存儲在ChunkServer上實現(xiàn)機制客戶端首先訪問Master節(jié)點，獲取交互的ChunkServer信息，然后訪問這些ChunkServer，完成數(shù)據(jù)存取工作。這種設計方法實現(xiàn)了控制流和數(shù)據(jù)流的分離。Client與Master之間只有控制流，而無數(shù)據(jù)流，極大地降低了Master的負載。Client與ChunkServer之間直接傳輸數(shù)據(jù)流，同時由于文件被分成多個Chunk進行分布式存儲，Client可以同時訪問多個ChunkServer，從而使得整個系統(tǒng)的I/O高度并行，系統(tǒng)整體性能得到提高。

GFS特點有哪些？GFS特點采用中心服務器模式可以方便地增加ChunkServerMaster掌握系統(tǒng)內(nèi)所有ChunkServer的情況，方便進行負載均衡不存在元數(shù)據(jù)的一致性問題不緩存數(shù)據(jù)

文件操作大部分是流式讀寫，不存在大量重復讀寫，使用Cache對性能提高不大ChunkServer上數(shù)據(jù)存取使用本地文件系統(tǒng)，若讀取頻繁，系統(tǒng)具有Cache從可行性看，Cache與實際數(shù)據(jù)的一致性維護也極其復雜在用戶態(tài)下實現(xiàn)

利用POSIX編程接口存取數(shù)據(jù)降低了實現(xiàn)難度，提高通用性

POSIX接口提供功能更豐富

用戶態(tài)下有多種調(diào)試工具

Master和ChunkServer都以進程方式運行，單個進程不影響整個操作系統(tǒng)

GFS和操作系統(tǒng)運行在不同的空間，兩者耦合性降低只提供專用接口降低實現(xiàn)的難度對應用提供一些特殊支持降低復雜度

Google文件系統(tǒng)GFS系統(tǒng)架構(gòu)容錯機制系統(tǒng)管理技術Master容錯

MasterNameSpace，文件系統(tǒng)目錄結(jié)構(gòu)

Chunk與文件名的映射Chunk副本的位置信息(默認有三個副本)

NameSpace，文件系統(tǒng)目錄結(jié)構(gòu)

Chunk與文件名的映射Chunk副本的位置信息Master單個Master，對于前兩種元數(shù)據(jù)，GFS通過操作日志來提供容錯功能

第三種元數(shù)據(jù)信息保存在各個ChunkServer上，Master故障時，磁盤恢復

GFS還提供了Master遠程的實時備份,防止Master徹底死機的情況ChunkServer容錯

采用副本方式實現(xiàn)ChunkServer容錯每一個Chunk有多個存儲副本（默認為三個），分布存儲在不同的ChunkServer上用戶態(tài)的GFS不會影響ChunkServer的穩(wěn)定性副本的分布策略需要考慮多種因素，如網(wǎng)絡的拓撲、機架的分布、磁盤的利用率等對于每一個Chunk，必須將所有的副本全部寫入成功，才視為成功寫入盡管一份數(shù)據(jù)需要存儲三份，好像磁盤空間的利用率不高，但綜合比較多種因素，加之磁盤的成本不斷下降，采用副本無疑是最簡單、最可靠、最有效，而且實現(xiàn)的難度也最小的一種方法。Simple,andgoodenough!GFS中的每一個文件被劃分成多個Chunk，Chunk的默認大小是64MBChunkServer存儲的是Chunk的副本，副本以文件的形式進行存儲每個Chunk又劃分為若干Block（64KB），每個Block對應一個32bit的校驗碼，保證數(shù)據(jù)正確（若某個Block錯誤，則轉(zhuǎn)移至其他Chunk副本）Google文件系統(tǒng)GFS系統(tǒng)架構(gòu)容錯機制系統(tǒng)管理技術大規(guī)模集群安裝技術故障檢測技術

節(jié)點動態(tài)加入技術

節(jié)能技術

新的ChunkServer加入時，只需裸機加入，大大減少GFS維護工作量

GFS構(gòu)建在不可靠廉價計算機之上的文件系統(tǒng)，由于節(jié)點數(shù)目眾多，故障發(fā)生十分頻繁

Google采用了多種機制降低服務器能耗，如采用蓄電池代替昂貴的UPS系統(tǒng)管理技術GFS集群中通常有非常多的節(jié)點，需要相應的技術支撐

小結(jié)簡單的，就是最好的！提綱Google文件系統(tǒng)GFS分布式數(shù)據(jù)處理MapReduce

分布式鎖服務Chubby

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

分布式存儲系統(tǒng)Megastore大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構(gòu)DapperGoogle應用程序引擎MapReduce一種處理海量數(shù)據(jù)的并行編程模式，用于大規(guī)模數(shù)據(jù)集（通常大于1TB）的并行運算。

“Map（映射）”、“Reduce（化簡）”的概念和主要思想，都是從函數(shù)式編程語言和矢量編程語言借鑒適合非結(jié)構(gòu)化和結(jié)構(gòu)化的海量數(shù)據(jù)的搜索、挖掘、分析與機器智能學習等

分布式數(shù)據(jù)處理MapReduce

產(chǎn)生背景

編程模型實現(xiàn)機制案例分析Google擁有海量數(shù)據(jù)，并且需要快速處理計算問題簡單，但求解困難

待處理數(shù)據(jù)量巨大（PB級），只有分布在成百上千個節(jié)點上并行計算才能在可接受的時間內(nèi)完成如何進行并行分布式計算？如何分發(fā)待處理數(shù)據(jù)？如何處理分布式計算中的錯誤？簡單的問題，計算并不簡單！JefferyDean設計一個新的抽象模型，封裝并行處理、容錯處理、本地化計算、負載均衡的細節(jié)，還提供了一個簡單而強大的接口這就是MapReduceGoogleMapReduce架構(gòu)設計師JeffreyDean分布式數(shù)據(jù)處理MapReduce

產(chǎn)生背景

編程模型實現(xiàn)機制案例分析MapReduce運行模型

Map函數(shù)——對一部分原始數(shù)據(jù)進行指定的操作。每個Map操作都針對不同的原始數(shù)據(jù)，因此Map與Map之間是互相獨立的，這使得它們可以充分并行化Reduce操作——對每個Map所產(chǎn)生的一部分中間結(jié)果進行合并操作，每個Reduce所處理的Map中間結(jié)果是互不交叉的，所有Reduce產(chǎn)生的最終結(jié)果經(jīng)過簡單連接就形成了完整的結(jié)果集Map:(in_key,in_value){(keyj,valuej)|j=1…k}Reduce:(key,[value1,…,valuem])(key,final_value)

開發(fā)者需編寫兩個主要函數(shù)

Map輸入?yún)?shù)：in_key和in_value，它指明了Map需要處理的原始數(shù)據(jù)Map輸出結(jié)果：一組<key,value>對，這是經(jīng)過Map操作后所產(chǎn)生的中間結(jié)果

Map:(in_key,in_value){(keyj,valuej)|j=1…k}Reduce:(key,[value1,…,valuem])(key,final_value)

開發(fā)者需編寫兩個主要函數(shù)

Reduce輸入?yún)?shù)：（key,[value1,…,valuem]）Reduce工作：對這些對應相同key的value值進行歸并處理Reduce輸出結(jié)果：（key,final_value），所有Reduce的結(jié)果并在一起就是最終結(jié)果Map的輸入?yún)?shù)指明了需要處理哪部分數(shù)據(jù)，以“<在文本中的起始位置，需要處理的數(shù)據(jù)長度>”表示，經(jīng)過Map處理，形成一批中間結(jié)果“<單詞，出現(xiàn)次數(shù)>”。而Reduce函數(shù)處理中間結(jié)果，將相同單詞出現(xiàn)的次數(shù)進行累加，得到每個單詞總的出現(xiàn)次數(shù)

怎么用MapReduce計算一個大型文本文件中各單詞出現(xiàn)次數(shù)？分布式數(shù)據(jù)處理MapReduce

產(chǎn)生背景

編程模型實現(xiàn)機制案例分析MapReduce操作執(zhí)行流程圖

操作過程（1）輸入文件分成M塊，每塊大概16M～64MB（可以通過參數(shù)決定），接著在集群的機器上執(zhí)行分派處理程序

（2）M個Map任務和R個Reduce任務需要分派，Master選擇空閑Worker來分配這些Map或Reduce任務（3）Worker讀取并處理相關輸入塊，Map函數(shù)產(chǎn)生的中間結(jié)果<key,value>對暫時緩沖到內(nèi)存（4）中間結(jié)果定時寫到本地硬盤，分區(qū)函數(shù)將其分成R個區(qū)。中間結(jié)果在本地硬盤的位置信息將被發(fā)送回Master，然后Master負責把這些位置信息傳送給ReduceWorker操作過程（5）當Master通知執(zhí)行Reduce的Worker關于中間<key,value>對的位置時，它調(diào)用遠程過程，從MapWorker的本地硬盤上讀取緩沖的中間數(shù)據(jù)。當ReduceWorker讀到所有的中間數(shù)據(jù)，它就使用中間key進行排序，這樣可使相同key的值都在一起（6）ReduceWorker根據(jù)每一個唯一中間key來遍歷所有的排序后的中間數(shù)據(jù)，并且把key和相關的中間結(jié)果值集合傳遞給用戶定義的Reduce函數(shù)。Reduce函數(shù)的結(jié)果寫到一個最終的輸出文件

（7）當所有的Map任務和Reduce任務都完成的時候，Master激活用戶程序。此時MapReduce返回用戶程序的調(diào)用點MapReduce容錯

Master周期性地給Worker發(fā)送ping命令，若沒有應答，則認為Worker失效，終止其任務調(diào)度，把該任務調(diào)度到其他Worker上重新執(zhí)行Master會周期性地設置檢查點（checkpoint），并導出Master的數(shù)據(jù)。一旦某個任務失效，系統(tǒng)就從最近的一個檢查點恢復并重新執(zhí)行MapReduce容錯分布式數(shù)據(jù)處理MapReduce

產(chǎn)生背景

編程模型實現(xiàn)機制案例分析假設有一批海量的數(shù)據(jù)，每個數(shù)據(jù)都是由26個字母組成的字符串，原始的數(shù)據(jù)集合是完全無序的，怎樣通過MapReduce完成排序工作，使其有序（字典序）呢？排序通常用于衡量分布式數(shù)據(jù)處理框架的數(shù)據(jù)處理能力

對原始的數(shù)據(jù)進行分割（Split），得到N個不同的數(shù)據(jù)分塊每一個數(shù)據(jù)分塊都啟動一個Map進行處理。采用桶排序的方法，每個Map中按照首字母將字符串分配到26個不同的桶中按照首字母將Map中不同桶中的字符串集合放置到相應的Reduce中進行處理。具體來說就是首字母為a的字符串全部放在Reduce1中處理，首字母為b的字符串全部放在Reduce2，以此類推提綱Google文件系統(tǒng)GFS分布式數(shù)據(jù)處理MapReduce

分布式鎖服務Chubby

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

分布式存儲系統(tǒng)Megastore大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構(gòu)DapperGoogle應用程序引擎分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable設計動機與目標數(shù)據(jù)模型系統(tǒng)架構(gòu)主服務器

子表服務器

性能優(yōu)化設計動機與目標需要存儲的數(shù)據(jù)種類繁多：Google目前向公眾開放的服務很多，需要處理的數(shù)據(jù)類型也非常多。包括URL、網(wǎng)頁內(nèi)容、用戶的個性化設置在內(nèi)的數(shù)據(jù)都是Google需要經(jīng)常處理的海量的服務請求：Google運行著目前世界上最繁忙的系統(tǒng)，它每時每刻處理的客戶服務請求數(shù)量是普通的系統(tǒng)根本無法承受的商用數(shù)據(jù)庫無法滿足Google的需求：一方面現(xiàn)有商用數(shù)據(jù)庫設計著眼點在于通用性，根本無法滿足Google的苛刻服務要求；另一方面對于底層系統(tǒng)的完全掌控會給后期的系統(tǒng)維護、升級帶來極大的便利設計動機設計動機與目標基本目標高可用性

Bigtable設計的重要目標之一就是確保幾乎所有的情況下系統(tǒng)都可用

廣泛的適用性

Bigtable是為了滿足系列Google產(chǎn)品而非特定產(chǎn)品存儲要求

簡單性

底層系統(tǒng)簡單性既可減少系統(tǒng)出錯概率，也為上層應用開發(fā)帶來便利

很強的可擴展性

根據(jù)需要隨時可以加入或撤銷服務器

針對結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)數(shù)據(jù)分類分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable設計動機與目標數(shù)據(jù)模型系統(tǒng)架構(gòu)主服務器

子表服務器

性能優(yōu)化數(shù)據(jù)模型

Bigtable是一個分布式多維映射表，表中的數(shù)據(jù)通過一個行關鍵字（RowKey）、一個列關鍵字（ColumnKey）以及一個時間戳（TimeStamp）進行索引Bigtable對存儲在其中的數(shù)據(jù)不做任何解析，一律看做字符串Bigtable數(shù)據(jù)模型Bigtable的存儲邏輯可以表示為：

(row:string,column:string,time:int64)→string數(shù)據(jù)模型行

Bigtable的行關鍵字可以是任意的字符串，但是大小不能超過64KB。Bigtable和傳統(tǒng)的關系型數(shù)據(jù)庫有很大不同，它不支持一般意義上的事務，但能保證對于行的讀寫操作具有原子性（Atomic）

表中數(shù)據(jù)都是根據(jù)行關鍵字進行排序的，排序使用的是詞典序。

一個典型實例，其中n.www就是一個行關鍵字。不直接存儲網(wǎng)頁地址而將其倒排是Bigtable的一個巧妙設計。這樣做至少會帶來以下兩個好處同一地址域的網(wǎng)頁會被存儲在表中的連續(xù)位置，有利于用戶查找和分析

倒排便于數(shù)據(jù)壓縮，可以大幅提高壓縮率

數(shù)據(jù)模型列

Bigtable并不是簡單地存儲所有的列關鍵字，而是將其組織成所謂的列族（ColumnFamily），每個族中的數(shù)據(jù)都屬于同一個類型，并且同族的數(shù)據(jù)會被壓縮在一起保存。引入了列族的概念之后，列關鍵字就采用下述的語法規(guī)則來定義：

族名：限定詞（family：qualifier）族名必須有意義，限定詞則可以任意選定圖中，內(nèi)容（Contents）、錨點（Anchor）都是不同的族。而和my.look.ca則是錨點族中不同的限定詞族同時也是Bigtable中訪問控制（AccessControl）基本單元，也就是說訪問權(quán)限的設置是在族這一級別上進行的數(shù)據(jù)模型時間戳

Google的很多服務比如網(wǎng)頁檢索和用戶的個性化設置等都需要保存不同時間的數(shù)據(jù)，這些不同的數(shù)據(jù)版本必須通過時間戳來區(qū)分。圖2中內(nèi)容列的t3、t5和t6表明其中保存了在t3、t5和t6這三個時間獲取的網(wǎng)頁。Bigtable中的時間戳是64位整型數(shù)，具體的賦值方式可以采取系統(tǒng)默認的方式，也可以用戶自行定義為了簡化不同版本的數(shù)據(jù)管理，Bigtable目前提供了兩種設置：一種是保留最近的N個不同版本，圖中數(shù)據(jù)模型采取的就是這種方法，它保存最新的三個版本數(shù)據(jù)。另一種就是保留限定時間內(nèi)的所有不同版本，比如可以保存最近10天的所有不同版本數(shù)據(jù)。失效的版本將會由Bigtable的垃圾回收機制自動處理

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable設計動機與目標數(shù)據(jù)模型系統(tǒng)架構(gòu)主服務器

子表服務器

性能優(yōu)化系統(tǒng)架構(gòu)

一個分布式的任務調(diào)度器，主要被用來處理分布式系統(tǒng)隊列分組和任務調(diào)度

系統(tǒng)架構(gòu)

在Bigtable中Chubby主要有以下幾個作用：（1）選取并保證同一時間內(nèi)只有一個主服務器（MasterServer）（2）獲取子表的位置信息（3）保存Bigtable的模式信息及訪問控制列表另外在Bigtable的實際執(zhí)行過程中，Google的MapReduce和Sawzall也被用來改善其性能系統(tǒng)架構(gòu)

Bigtable主要由三個部分組成：客戶端程序庫（ClientLibrary）、一個主服務器（MasterServer）和多個子表服務器（TabletServer）客戶訪問Bigtable服務時，首先要利用其庫函數(shù)執(zhí)行Open()操作來打開一個鎖（實際上就是獲取了文件目錄），鎖打開以后客戶端就可以和子表服務器進行通信和許多具有單個主節(jié)點分布式系統(tǒng)一樣，客戶端主要與子表服務器通信，幾乎不和主服務器進行通信，這使得主服務器的負載大大降低主服務主要進行一些元數(shù)據(jù)操作以及子表服務器之間負載調(diào)度問題，實際數(shù)據(jù)是存儲在子表服務器上

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable設計動機與目標數(shù)據(jù)模型系統(tǒng)架構(gòu)主服務器

子表服務器

性能優(yōu)化主服務器當一個新子表產(chǎn)生時，主服務器通過一個加載命令將其分配給一個空間足夠的子表服務器。創(chuàng)建新表、表合并以及較大子表的分裂都會產(chǎn)生一個或多個新子表。對于前面兩種，主服務器會自動檢測到，而較大子表的分裂是由子服務發(fā)起并完成的，所以主服務器并不能自動檢測到，因此在分割完成之后子服務器需要向主服務發(fā)出一個通知由于系統(tǒng)設計之初就要求能達到良好的擴展性，所以主服務器必須對子表服務器的狀態(tài)進行監(jiān)控，以便及時檢測到服務器的加入或撤銷Bigtable中主服務器對子表服務器的監(jiān)控是通過Chubby完成的——子表服務器在初始化時都會從Chubby中得到一個獨占鎖。通過這種方式所有子表服務器基本信息被保存在Chubby中一個稱為服務器目錄（ServerDirectory）的特殊目錄之中主服務器主服務器會定期向其詢問獨占鎖的狀態(tài)。如果子表服務器的鎖丟失或沒有回應，則此時可能有兩種情況要么是Chubby出現(xiàn)了問題（雖然這種概率很小，但的確存在，Google自己也做過相關測試）要么是子表服務器自身出現(xiàn)了問題。對此主服務器首先自己嘗試獲取這個獨占鎖，如果失敗說明Chubby服務出現(xiàn)問題，需等待恢復；如果成功則說明Chubby服務良好而子表服務器本身出現(xiàn)了問題當在狀態(tài)監(jiān)測時發(fā)現(xiàn)某個子表服務器上負載過重時，主服務器會自動對其進行負載均衡操作

主服務器基于系統(tǒng)出現(xiàn)故障是一種常態(tài)的設計理念，每個主服務器被設定了一個會話時間的限制。當某個主服務器到時退出后，管理系統(tǒng)就會指定一個新的主服務器，這個主服務器的啟動需要經(jīng)歷以下四個步驟：

（1）從Chubby中獲取一個獨占鎖，確保同一時間只有一個主服務器（2）掃描服務器目錄，發(fā)現(xiàn)目前活躍的子表服務器（3）與所有的活躍子表服務器取得聯(lián)系以便了解所有子表的分配情況（4）掃描元數(shù)據(jù)表，發(fā)現(xiàn)未分配的子表并將其分配到合適子表服務器如果元數(shù)據(jù)表未分配，則首先需要將根子表（RootTablet）加入未分配的子表中。由于根子表保存了其他所有元數(shù)據(jù)子表的信息，確保了掃描能夠發(fā)現(xiàn)所有未分配的子表分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable設計動機與目標數(shù)據(jù)模型系統(tǒng)架構(gòu)主服務器

子表服務器

性能優(yōu)化SSTable及子表基本結(jié)構(gòu)

SSTable是Google為Bigtable設計的內(nèi)部數(shù)據(jù)存儲格式。所有的SSTable文件都存儲在GFS上

SSTable中數(shù)據(jù)被劃分成一個個的塊（Block），每個塊的大小是可以設置的，一般為64KB在SSTable的結(jié)尾有一個索引（Index），這個索引保存了塊的位置信息，在SSTable打開時這個索引會被加載進內(nèi)存，用戶在查找某個塊時首先在內(nèi)存中查找塊的位置信息，然后在硬盤上直接找到這個塊由于每個SSTable一般都不是很大，用戶還可以選擇將其整體加載進內(nèi)存，這樣查找起來會更快

SSTable結(jié)構(gòu)

子表實際組成

每個子表都是由多個SSTable以及日志（Log）文件構(gòu)成不同子表的SSTable可以共享Bigtable中的日志文件是一種共享日志，每個子表服務器上僅保存一個日志文件，某個子表日志只是這個共享日志的一個片段。這樣會節(jié)省大量的空間，但在恢復時卻有一定的難度Google為了避免這種情況出現(xiàn)，對日志做了一些改進。Bigtable規(guī)定將日志的內(nèi)容按照鍵值進行排序，這樣不同的子表服務器都可以連續(xù)讀取日志文件了一般來說每個子表的大小在100MB到200MB之間。每個子表服務器上保存的子表數(shù)量可以從幾十到上千不等，通常情況下是100個左右

子表地址結(jié)構(gòu)

子表地址的查詢是經(jīng)常碰到的操作。在Bigtable系統(tǒng)的內(nèi)部采用的是一種類似B+樹的三層查詢體系

所有子表地址都被記錄在元數(shù)據(jù)表中，元數(shù)據(jù)表也是由一個個的元數(shù)據(jù)子表（Metadatatablet）組成根子表是元數(shù)據(jù)表中一個比較特殊的子表，它既是元數(shù)據(jù)表的第一條記錄，也包含了其他元數(shù)據(jù)子表的地址，同時Chubby中的一個文件也存儲了這個根子表的信息。查詢時，首先從Chubby中提取這個根子表的地址，進而讀取所需的元數(shù)據(jù)子表的位置，最后就可以從元數(shù)據(jù)子表中找到待查詢的子表。除了這些子表的元數(shù)據(jù)之外，元數(shù)據(jù)表中還保存了其他一些有利于調(diào)試和分析的信息，比如事件日志等為了減少訪問開銷，提高客戶訪問效率，Bigtable使用了緩存（Cache）和預取（Prefetch）技術

子表的地址信息被緩存在客戶端，客戶在尋址時直接根據(jù)緩存信息進行查找。一旦出現(xiàn)緩存為空或緩存信息過時的情況，客戶端就需要進行網(wǎng)絡的來回通信（NetworkRound-trips）進行尋址，在緩存為空的情況下需要三個網(wǎng)絡來回通信。如果緩存的信息是過時的，則需要六個網(wǎng)絡來回通信。其中三個用來確定信息是過時的，另外三個獲取新的地址

預取則是在每次訪問元數(shù)據(jù)表時不僅僅讀取所需的子表元數(shù)據(jù)，而是讀取多個子表的元數(shù)據(jù)，這樣下次需要時就不用再次訪問元數(shù)據(jù)表

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable設計動機與目標數(shù)據(jù)模型系統(tǒng)架構(gòu)主服務器

子表服務器

性能優(yōu)化局部性群組（Localitygroups）

局部性群組(LocalityGroup)根據(jù)需要，將原本不存儲在一起的數(shù)據(jù)，以列族為單位存儲至單獨的子表有的用戶可能只對網(wǎng)頁內(nèi)容感興趣，那么它可以通過設置局部性群組（見下圖）只看內(nèi)容這一列；有的對諸如網(wǎng)頁語言、網(wǎng)站排名等可以用于分析的信息比較感興趣，他也可以將這些列設置到一個群組中

壓縮壓縮

壓縮可以有效地節(jié)省空間，Bigtable中的壓縮被應用于很多場合

首先壓縮可以被用在構(gòu)成局部性群組的SSTable中，可以選擇是否對個人的局部性群組的SSTable進行壓縮。這種壓縮是對每個局部性群組獨立進行，雖然會浪費一些空間，但是在需要讀時解壓速度非常快壓縮技術還可以提高子表的恢復速度，當某個子表服務器停止使用后，需要將上面所有的子表移至另一個子表服務器。轉(zhuǎn)移前兩次壓縮：第一次壓縮減少了提交日志中未壓縮狀態(tài)；文件正式轉(zhuǎn)移前還要進行一次壓縮，主要是將第一次壓縮后遺留的未壓縮空間進行壓縮提綱Google文件系統(tǒng)GFS分布式數(shù)據(jù)處理MapReduce

分布式鎖服務Chubby

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

分布式存儲系統(tǒng)Megastore大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構(gòu)DapperGoogle應用程序引擎分布式存儲系統(tǒng)Megastore設計目標及方案選擇Megastore數(shù)據(jù)模型Megastore中的事務及并發(fā)控制

Megastore基本架構(gòu)產(chǎn)品性能及控制措施在互聯(lián)網(wǎng)的應用中，為了達到好的可擴展性，常常會采用NoSQL存儲方式。但是從應用程序的構(gòu)建方面來看，傳統(tǒng)的關系型數(shù)據(jù)庫又有著NoSQL所不具備的優(yōu)勢。

Google設計和構(gòu)建了用于互聯(lián)網(wǎng)中交互式服務的分布式存儲系統(tǒng)Megastore，該系統(tǒng)成功的將關系型數(shù)據(jù)庫和NoSQL的特點與優(yōu)勢進行了融合設計目標及方案選擇

可用性——實現(xiàn)了一個同步的、容錯的、適合遠距離傳輸?shù)膹椭茩C制。引入Paxos算法并對其做出一定的改進以滿足遠距離同步復制的要求

可擴展性——借鑒了數(shù)據(jù)庫中數(shù)據(jù)分區(qū)的思想，將整個大的數(shù)據(jù)分割成很多小的數(shù)據(jù)分區(qū)，每個數(shù)據(jù)分區(qū)連同它自身的日志存放在NoSQL數(shù)據(jù)庫中，具體來說就是存放在Bigtable中設計目標一種介于傳統(tǒng)的關系型數(shù)據(jù)庫和NoSQL之間的存儲技術，盡可能達到高可用性和高可擴展性的統(tǒng)一數(shù)據(jù)分區(qū)和復制

數(shù)據(jù)分區(qū)和復制Megastore中，這些小的數(shù)據(jù)分區(qū)被稱為實體組集（EntityGroups）。每個實體組集包含若干實體組（EntityGroup，相當于分區(qū)中表的概念），而一個實體組中又包含很多的實體（Entity，相當于表中記錄的概念）。從圖中還可以看出單個實體組支持ACID語義實體組集之間只具有比較松散的一致性。每個實體組都通過復制技術在數(shù)據(jù)中心中保存若干數(shù)據(jù)副本，這些實體組及其副本都存儲在NoSQL數(shù)據(jù)庫（Bigtable）中

分布式存儲系統(tǒng)Megastore設計目標及方案選擇Megastore數(shù)據(jù)模型Megastore中的事務及并發(fā)控制

Megastore基本架構(gòu)產(chǎn)品性能及控制措施Megastore數(shù)據(jù)模型

傳統(tǒng)的關系型數(shù)據(jù)庫是通過連接（Join）來滿足用戶的需求的，但是就Megastore而言，這種數(shù)據(jù)模型是不合適的，主要有以下三個原因：（1）對于高負載的交互式應用來說，可預期的性能提升要比使用一種代價高昂的查詢語言所帶來的好處多（2）Megastore所面對的應用是讀遠多于寫，因此好的選擇是將讀操作所需要做的工作盡可能地轉(zhuǎn)移到寫操作上（3）在Bigtable這樣的鍵/值存儲系統(tǒng)中存儲和查詢級聯(lián)數(shù)據(jù)（HierarchicalData）是很方便的

Megastore數(shù)據(jù)模型怎么設計？Google設計了一種能夠提供細粒度控制的數(shù)據(jù)模型和模式語言

同關系型數(shù)據(jù)庫一樣，Megastore的數(shù)據(jù)模型是在模式（schema）中定義的且是強類型的（stronglytyped）

每個模式都由一系列的表（tables）構(gòu)成，表又包含有一系列的實體（entities），每實體中包含一系列屬性（properties）

屬性是命名的且具有類型，這些類型包括字符型（strings）、數(shù)字類型（numbers）或者Google的ProtocolBuffers。這些屬性可以被設置成必須的（required）、可選的（optional）或者可重復的（repeated，即允許單個屬性上有多個值）

數(shù)據(jù)模型實例

照片共享服務數(shù)據(jù)模型實例

圖中表Photo就是一個子表，因為它聲明了一個外鍵；User則是一個根表。一個Megastore實例中可以有若干個不同的根表，表示不同類型的實體組集圖中實例還可以看到三種不同屬性設置，既有必須的（如user_id），也有可選的（如thumbnail_url）；值得注意的是Photo中的可重復類型的tag屬性，這也就意味著一個Photo中允許同時出現(xiàn)多個tag屬性索引（Index）

Megastore索引分成兩大類：局部索引（localindex）和全局索引（globalindex）

局部索引定義在單個實體組中，作用域僅限于單個實體組（如PhotosByTime）

全局索引則可以橫跨多個實體組集進行數(shù)據(jù)讀取操作（如PhotosByTag）Megastore還提供了一些額外的索引特性：

STORING子句（STORINGClause）

可重復的索引（RepeatedIndexes）

內(nèi)聯(lián)索引（InlineIndexes）Bigtable中數(shù)據(jù)存儲情況

行鍵（RowKey）UPhoto.timePhoto.tagPhoto._url101John101,50012:30:01Dinner,Paris…101,50212:15:22Betty,Paris…102Mary表中不難看出——Bigtable的列名實際上是表名和屬性名結(jié)合在一起得到，不同表中實體可存儲在同一個Bigtable行中分布式存儲系統(tǒng)Megastore設計目標及方案選擇Megastore數(shù)據(jù)模型Megastore中的事務及并發(fā)控制

Megastore基本架構(gòu)產(chǎn)品性能及控制措施Megastore中的事務及并發(fā)控制Megastore三種方式的讀，分別是current、snapshot和inconsistent

其中current讀和snapshot讀總是在單個實體組中完成

對于snapshot讀，系統(tǒng)取出已知的最后一個完整提交的事務的時間戳，接著從這個位置讀數(shù)據(jù)inconsistent讀忽略日志的狀態(tài)直接讀取最新的值Megastore中的事務及并發(fā)控制Megastore事務中的寫操作采用了預寫式日志（Write-aheadLog）

一個寫事務總是開始于一個current讀以便確認下一個可用的日志位置。提交操作將數(shù)據(jù)變更聚集到日志，接著分配一個比之前任意一個都高的時間戳，然后使用Paxos將數(shù)據(jù)變更加入到日志中

協(xié)議使用了樂觀并發(fā)（OptimisticConcurrency）：盡管可能有多個寫操作同時試圖寫同一個日志位置，但只會有1個成功讀：獲取最后一次提交的事務的時間戳和日志位置完整事務周期應用邏輯：從Bigtable讀取且聚集數(shù)據(jù)到日志入口提交：使用Paxos達到一致，將個入口追加到日志生效：將數(shù)據(jù)更新到Bigtable中的實體和索引清除：清理不再需要的數(shù)據(jù)Megastore中的事務機制

消息隊列機制消息能夠橫跨實體組

每個消息都有一個發(fā)送和接收實體組如果兩個實體組是不同的，則傳輸將是異步特點規(guī)模：聲明一個隊列后可以在其他所有的實體組上創(chuàng)建一個收件箱支持兩階段提交增加競爭風險，不鼓勵使用

Megastore中的事務機制

分布式存儲系統(tǒng)Megastore設計目標及方案選擇Megastore數(shù)據(jù)模型Megastore中的事務及并發(fā)控制

Megastore基本架構(gòu)產(chǎn)品性能及控制措施Megastore的基本架構(gòu)Megastore中三種副本

完整副本：Bigtable中存儲完整的日志和數(shù)據(jù)見證者副本：在Paxos算法執(zhí)行過程中無法產(chǎn)生一個決議時參與投票只讀副本：讀取最近過去某一個時間點一致性數(shù)據(jù)

Megastore的基本架構(gòu)Megastore中提供快速讀（FastReads）和快速寫（FastWrites）機制

快速讀如果讀操作不需要副本之間進行通信即可完成，那么讀取的效率必然相對較高利用本地讀取（LocalReads）實現(xiàn)快速讀，能夠帶來更好的用戶體驗及更低的延遲確保快速讀成功的