Bigtable結(jié)構(gòu)化數(shù)據(jù)的分布式存儲(chǔ)系統(tǒng)上

1、Bigtable 結(jié)構(gòu)化數(shù)據(jù)的分布式存儲(chǔ)系統(tǒng) 上轉(zhuǎn)載請(qǐng)注明：作者phylipsbmy摘要Bigtable是設(shè)計(jì)用來管理那些可能達(dá)到很大大小(比如可能是存儲(chǔ)在數(shù)千臺(tái)服務(wù)器上的數(shù)PB的數(shù)據(jù))的結(jié)構(gòu)化數(shù)據(jù)的分布式存儲(chǔ)系統(tǒng)。Google的很多項(xiàng)目都將數(shù)據(jù)存儲(chǔ)在Bigtable中，比如網(wǎng)頁索引，google地球，google金融。這些應(yīng)用對(duì)Bigtable提出了很多不同的要求，無論是數(shù)據(jù)大小(從單純的URL到包含圖片附件的網(wǎng)頁)還是延時(shí)需求。盡管存在這些各種不同的需求，Bigtable成功地為google的所有這些產(chǎn)品提供了一個(gè)靈活的，高性能的解決方案。在這篇論文中，我們將描述Bigtable所提供的允

2、許客戶端動(dòng)態(tài)控制數(shù)據(jù)分布和格式的簡單數(shù)據(jù)模型，此外還會(huì)描述Bigtable的設(shè)計(jì)和實(shí)現(xiàn)。1.導(dǎo)引在過去的2年半時(shí)間里，我們?cè)O(shè)計(jì),實(shí)現(xiàn),部署了一個(gè)稱為Bigtable的用來管理google的數(shù)據(jù)的分布式存儲(chǔ)系統(tǒng)。Bigtable的設(shè)計(jì)使它可以可靠地?cái)U(kuò)展到成PB的數(shù)據(jù)以及數(shù)千臺(tái)機(jī)器上。Bigtable成功的實(shí)現(xiàn)了這幾個(gè)目標(biāo)：廣泛的適用性，可擴(kuò)展性，高性能以及高可用性。目前，Bigtable已經(jīng)被包括Google分析，google金融，Orkut，個(gè)性化搜索，Writely和google地球在內(nèi)的60多個(gè)google產(chǎn)品和項(xiàng)目所使用。這些產(chǎn)品使用Bigtable用于處理各種不同的工作負(fù)載類型，從面向

3、吞吐率的批處理任務(wù)到時(shí)延敏感的面向終端用戶的數(shù)據(jù)服務(wù)。這些產(chǎn)品所使用的Bigtable集群也跨越了廣泛的配置規(guī)模，從幾臺(tái)機(jī)器到存儲(chǔ)了幾百TB數(shù)據(jù)的上千臺(tái)服務(wù)器。在很多方面，Bigtable都類似于數(shù)據(jù)庫：它與數(shù)據(jù)庫采用了很多相同的實(shí)現(xiàn)策略。目前的并行數(shù)據(jù)庫和主存數(shù)據(jù)庫已經(jīng)成功實(shí)現(xiàn)了可擴(kuò)展性和高性能，但是Bigtable提供了與這些系統(tǒng)不同的接口。Bigtable并不支持一個(gè)完整的關(guān)系數(shù)據(jù)模型，而是給用戶提供了一個(gè)可以動(dòng)態(tài)控制數(shù)據(jù)分布和格式的簡單數(shù)據(jù)模型，允許用戶將數(shù)據(jù)的局部性屬性體現(xiàn)在底層的數(shù)據(jù)存儲(chǔ)上。數(shù)據(jù)使用可以是任意字符串的行列名稱進(jìn)行索引。Bigtable將數(shù)據(jù)看做是未經(jīng)解釋的字符串，盡

4、管用戶經(jīng)常將各種形式的結(jié)構(gòu)化或半結(jié)構(gòu)化的數(shù)據(jù)存儲(chǔ)到這些字符串里。用戶可以通過在schema中的細(xì)心選擇來控制數(shù)據(jù)的locality。最后，Bigtable的schema參數(shù)還允許用戶選擇從磁盤還是內(nèi)存獲取數(shù)據(jù)。第2節(jié)更加詳細(xì)的描述了該數(shù)據(jù)模型。第3節(jié)提供了關(guān)于用戶API的概覽。第4節(jié)簡要描述了Bigtable所依賴的底層軟件。第5節(jié)描述了Bigtable的基本實(shí)現(xiàn)。第6節(jié)描述了我們?yōu)樘岣連igtable的性能使用的一些技巧。第7節(jié)提供了一些對(duì)于Bigtable的性能測(cè)量數(shù)據(jù)。第8節(jié)展示了幾個(gè)Google內(nèi)部的Bigtable的使用實(shí)例。第9節(jié)討論了我們?cè)谠O(shè)計(jì)支持Bigtable所學(xué)到的一些經(jīng)驗(yàn)

5、教訓(xùn)。最后第10節(jié)描述了相關(guān)工作，第11節(jié)進(jìn)行了總結(jié)。2.數(shù)據(jù)模型Bigtable是一個(gè)稀疏的，分布式的一致性多維有序map。這個(gè)map是通過行關(guān)鍵字，列關(guān)鍵字以及時(shí)間戳進(jìn)行索引的；map中的每個(gè)值都是一個(gè)未經(jīng)解釋的字節(jié)數(shù)組。(row：string,column：string,time：int64)-string我們?cè)趯?duì)于這種類Bigtable系統(tǒng)的潛在使用場(chǎng)景進(jìn)行了大量考察后，最終確定了這個(gè)數(shù)據(jù)模型。舉一個(gè)影響到我們的某些設(shè)計(jì)決策的具體例子，比如我們想保存一份可以被很多工程使用的一大集網(wǎng)頁及其相關(guān)信息的拷貝。我們把這個(gè)表稱為webtable，在這個(gè)表中，我們可以使用URL作為行關(guān)鍵字，網(wǎng)頁的

6、各種信息作為列名稱，將網(wǎng)頁的內(nèi)容作為表的內(nèi)容存儲(chǔ)：獲取的時(shí)候還需要在列上加上時(shí)間戳，如圖1所示。表中的行關(guān)鍵字是大字符串(目前最大可以到64KB，盡管對(duì)于大多數(shù)用戶來說最常用的是10-100字節(jié))。在一個(gè)行關(guān)鍵字下的數(shù)據(jù)讀寫是原子性的(無論這一行有多少個(gè)不同的列被讀寫)，這個(gè)設(shè)計(jì)使得用戶在對(duì)相同行的并發(fā)更新出現(xiàn)時(shí)，更容易理解系統(tǒng)的行為。Bigtable按照行關(guān)鍵字的字典序來維護(hù)數(shù)據(jù)。行組row range，將它翻譯為行組，一個(gè)row range可能由多個(gè)行組成是可以動(dòng)態(tài)劃分的。每個(gè)行組叫做一個(gè)tablet，是數(shù)據(jù)存放以及負(fù)載平衡的單位。這樣，對(duì)于一個(gè)短的行組的讀就會(huì)很有效，而且只需要與少數(shù)的機(jī)

7、器進(jìn)行通信?？蛻舳丝梢酝ㄟ^選擇行關(guān)鍵字來利用這個(gè)屬性，這樣它們可以為數(shù)據(jù)訪問得到好的局部性。比如，在webtable里，相同域名的網(wǎng)頁可以通過將URL中的域名反轉(zhuǎn)而使他們放在連續(xù)的行里來組織到一塊。比如我們將網(wǎng)頁/index.html的數(shù)據(jù)存放在關(guān)鍵字com.google.maps/index.html下。將相同域名的網(wǎng)頁存儲(chǔ)在鄰近位置可以使對(duì)主機(jī)或域名的分析更加有效。列族不同的列關(guān)鍵字可以被分組到一個(gè)集合，我們把這樣的一個(gè)集合稱為一個(gè)列族，它是基本的訪問控制單元。存儲(chǔ)在同一個(gè)列族的數(shù)據(jù)通常是相同類型的(我們將同一列族的數(shù)據(jù)壓縮在一塊)。在數(shù)據(jù)能夠存儲(chǔ)到某個(gè)列族的

8、列關(guān)鍵字下之前，必須首先要?jiǎng)?chuàng)建該列族。我們假設(shè)在一個(gè)表中不同列族的數(shù)目應(yīng)該比較小(最多數(shù)百個(gè))，而且在操作過程中這些列族應(yīng)該很少變化。與之相比，一個(gè)表的列數(shù)目可以沒有限制。一個(gè)列關(guān)鍵字是使用如下的字符來命名的：family：qualifier。列族名稱必須是可打印的，但是qualifier可能是任意字符串。比如webtable有一個(gè)列族是language，它存儲(chǔ)了網(wǎng)頁所使用的語言。在language列族里，我們只使用了一個(gè)列關(guān)鍵字，里面存儲(chǔ)了每個(gè)網(wǎng)頁的language id。該表的另一個(gè)列族是anchor，在該列族的每個(gè)列關(guān)鍵字代表一個(gè)單獨(dú)的anchor，如圖1所示。Qualifier是站點(diǎn)的

9、名稱，里面的內(nèi)容是鏈接文本。訪問控制以及磁盤的內(nèi)存分配都是在列族級(jí)別進(jìn)行的。在webtable這個(gè)例子中，這些控制允許我們管理不同類型的應(yīng)用：一些可能會(huì)添加新的基礎(chǔ)數(shù)據(jù)，一些可能讀取這些基礎(chǔ)數(shù)據(jù)來創(chuàng)建新的列族，一些可能只需要查看現(xiàn)有數(shù)據(jù)(甚至可能因?yàn)殡[私策略不需要查看所有現(xiàn)有數(shù)據(jù))。時(shí)間戳Bigtable里的每個(gè)cell可以包含相同數(shù)據(jù)的多個(gè)版本；這些不同的版本是通過時(shí)間戳索引的。Bigtable的時(shí)間戳是一個(gè)64位的整數(shù)。它們可以由Bigtable來賦值，在這種情況下它們以毫秒來代表時(shí)間。也可以由客戶端應(yīng)用程序顯式分配。應(yīng)用程序?yàn)榱吮苊鉀_突必須能夠自己生成唯一的時(shí)間戳。一個(gè)cell的不同版本

10、是按照時(shí)間戳降序排列，這樣最近的版本可以被首先讀到。為了使不同版本的數(shù)據(jù)管理更簡單，我們支持2個(gè)針對(duì)每個(gè)列族的設(shè)定來告訴Bigtable可以對(duì)cell中的數(shù)據(jù)版本進(jìn)行自動(dòng)的垃圾回收。用戶可以指定最近的哪幾個(gè)版本需要保存，或者保存那些足夠新的版本(比如只保存那些最近7天寫的數(shù)據(jù))。在我們的webtable中，我們將爬取的網(wǎng)頁的時(shí)間戳存儲(chǔ)在內(nèi)容里：這些時(shí)間說明了這些網(wǎng)頁的不同版本分別是在何時(shí)被抓取的。前面描述的垃圾回收機(jī)制，使我們只保存每個(gè)網(wǎng)頁最新的三個(gè)版本。3.API Bigtable API提供了一些函數(shù)用于表及列族的創(chuàng)建和刪除。它也提供了一些用于改變集群，表格及列族元數(shù)據(jù)的函數(shù)，比如訪問控制

11、權(quán)限。客戶端應(yīng)用程序可以寫或者刪除Bigtable里的值，從行里查找值或者在表中的一個(gè)數(shù)據(jù)子集中進(jìn)行迭代。圖2展示了使用RowMutation執(zhí)行一系列更新的C+代碼(為了保持簡單省略了不相關(guān)的細(xì)節(jié))。Apply調(diào)用對(duì)webtable執(zhí)行了一個(gè)原子性的變更操作：給增加一個(gè)anchor，然后刪除另一個(gè)anchor。圖3展示的c+代碼使用Scanner來在一個(gè)特殊行上的所有anchor進(jìn)行迭代，用戶可以在多個(gè)列族上進(jìn)行迭代，存在幾種機(jī)制來對(duì)掃描到的行，列，時(shí)間戳進(jìn)行過濾。比如我們可以限制只掃描那些與正則表達(dá)式anchor：*.匹配的列，或者那些時(shí)間戳距離當(dāng)前時(shí)間10天以內(nèi)的ancho

12、r。Bigtable提供了幾種其他的feature允許用戶使用更復(fù)雜的方式熟練控制數(shù)據(jù)。首先，Bigtable支持單行事務(wù)，能夠支持對(duì)存儲(chǔ)在一個(gè)行關(guān)鍵字上的執(zhí)行原子性的讀寫修改序列。Bigtable當(dāng)前并不支持跨行的事務(wù)，盡管它提供了一個(gè)多個(gè)用戶的跨行寫的接口。其次，Bigtable允許用戶將cell作為一個(gè)整數(shù)計(jì)數(shù)器來使用。最后，Bigtable支持在服務(wù)器地址空間內(nèi)執(zhí)行一個(gè)客戶端腳本。這些腳本是使用google內(nèi)部開發(fā)的數(shù)據(jù)處理語言sawzall編寫的。當(dāng)前，我們基于Sawzall的API不允許客戶端腳本向Bigtable中寫回，但是它允許進(jìn)行各種形式的數(shù)據(jù)轉(zhuǎn)換，基于各種表達(dá)式的過濾以及大

13、量的統(tǒng)計(jì)操作符。Bigtable可以與MapReduce(google內(nèi)部開發(fā)的一個(gè)運(yùn)行大規(guī)模并行程序的框架)一起使用。我們寫了很多wrapper它允許將Bigtable作為輸入源或者輸出目標(biāo)。4.基礎(chǔ)構(gòu)件Bigtable是建立在google的其他幾個(gè)設(shè)施之上。Bigtable使用GFS來存儲(chǔ)日志和數(shù)據(jù)文件。Bigtable集群通常運(yùn)行在一個(gè)運(yùn)行著大量其他分布式應(yīng)用的共享機(jī)器池上。Bigtable依賴于一個(gè)集群管理系統(tǒng)進(jìn)行job調(diào)度，共享機(jī)器上的資源管理，處理機(jī)器失敗以及監(jiān)控機(jī)器狀態(tài)。Bigtable內(nèi)部采用Google SSTable文件格式來存儲(chǔ)數(shù)據(jù)。一個(gè)SSTable提供了一個(gè)一致性的，

14、有序的從key到value的不可變map，key和value都是任意的字節(jié)串。操作通常是通過一個(gè)給定的key來查找相應(yīng)的value，或者在一個(gè)給定的key range上迭代所有的key/value對(duì)。每個(gè)SSTable內(nèi)部包含一系列的塊(通常每個(gè)塊是64KB大小，但是該大小是可配置的)。一個(gè)塊索引(保存在SSTable的尾部)是用來定位block的，當(dāng)SSTable打開時(shí)該索引會(huì)被加載到內(nèi)存。一次查找可以通過一次磁盤訪問完成：首先通過在內(nèi)存中的索引進(jìn)行一次二分查找找到相應(yīng)的塊，然后從磁盤中讀取該塊。另外，一個(gè)SSTable可以被完全映射到內(nèi)存，這樣就不需要我們接觸磁盤就可以執(zhí)行所有的查找和掃描

15、。關(guān)于SSTable(StaticSearchTable)的具體格式可以參考YunTable開發(fā)日記(4)-BigTable的存儲(chǔ)模型，中對(duì)HBASE的HFile的介紹Bigtable依賴于一個(gè)高可用的一致性分布式鎖服務(wù)Chubby。Chubby由5個(gè)活動(dòng)副本組成，其中的一個(gè)選為master處理請(qǐng)求。當(dāng)大部分的副本運(yùn)行并且可以相互通信時(shí)，該服務(wù)就是活的。Chubby使用Paxos算法來在出現(xiàn)失敗時(shí)，保持副本的一致性。Chubby提供了一個(gè)由目錄和小文件組成的名字空間。每個(gè)文件或者目錄可以當(dāng)作一個(gè)鎖來使用，對(duì)于一個(gè)文件的讀寫是原子性的。Chubby的客戶端庫為Chubby文件提供一致性緩存。每個(gè)

16、Chubby客戶端維護(hù)這一個(gè)與Chubby服務(wù)的會(huì)話。如果在租約有效時(shí)間內(nèi)無法更新會(huì)話的租約，客戶端的會(huì)話就會(huì)過期。當(dāng)一個(gè)客戶端會(huì)話過期后，它會(huì)丟失所有的鎖和打開的文件句柄。Chubby客戶端也會(huì)在Chubby文件和目錄上注冊(cè)回調(diào)函數(shù)來處理這些變更或者會(huì)話的過期。Bigtable使用Chubby來完成各種任務(wù)：保證任意時(shí)刻最多只有一個(gè)活動(dòng)的master；存儲(chǔ)Bigtable數(shù)據(jù)的bootstrap location(參見5.2節(jié))；發(fā)現(xiàn)tablet服務(wù)器以及finalize tablet服務(wù)器的死亡(參見5.2節(jié))；保存Bigtable schema信息(每個(gè)表的列族信息)；存儲(chǔ)訪問控制列表。

17、如果chubby在一段時(shí)間內(nèi)不可用，Bigtable也會(huì)不可用。我們最近在使用了11個(gè)chubby實(shí)例的14個(gè)Bigtable集群進(jìn)行了測(cè)量。由于Chubby不可用而造成的存儲(chǔ)在Bigtable上的數(shù)據(jù)不可用的平均概率是0.0047%。對(duì)于單個(gè)集群來說，由于Chubby不可用造成的這個(gè)概率是0.0326%。5.實(shí)現(xiàn)Bigtable實(shí)現(xiàn)有3個(gè)主要的組件：每個(gè)客戶端需要鏈接的庫，一個(gè)master服務(wù)器，很多tablet服務(wù)器。tablet服務(wù)器可以從一個(gè)集群中動(dòng)態(tài)添加(或者刪除)來適應(yīng)工作負(fù)載的動(dòng)態(tài)變化。Master負(fù)責(zé)將tablet分配到tablet服務(wù)器，檢測(cè)tablet服務(wù)器的添加和過期，平

18、衡tablet服務(wù)器負(fù)載，GFS文件的垃圾回收。另外，它還會(huì)處理schema的變化，比如表和列族的創(chuàng)建。每個(gè)tablet服務(wù)器管理一個(gè)tablets集合(通常每個(gè)tablet服務(wù)器有10到1000個(gè)tablet)。Tablet服務(wù)器負(fù)責(zé)它已經(jīng)加載的那些tablet的讀寫請(qǐng)求，也會(huì)將那些過于大的tablet進(jìn)行分割。tablet服務(wù)器本身實(shí)際上也是GFS的用戶，它們只是負(fù)載它加載的那些tablet的管理，這些tablet的物理存儲(chǔ)并不一定存放在管理它的服務(wù)器上，底層的存儲(chǔ)是由GFS完成的，tablet服務(wù)器可以只調(diào)用它的接口來完成相應(yīng)任務(wù)。而METADATA表中的位置信息應(yīng)該是指某個(gè)tablet

19、由哪個(gè)tablet服務(wù)器管理，而不是物理上存儲(chǔ)在哪個(gè)機(jī)器上。正如很多單master的分布式存儲(chǔ)系統(tǒng)，客戶端數(shù)據(jù)的移動(dòng)并不會(huì)經(jīng)過master：客戶端直接與tablet服務(wù)器進(jìn)行通信來進(jìn)行讀寫。因?yàn)锽igtable客戶端并不依賴于master得到tablet的位置信息，大部分的客戶端從來不會(huì)于master通信。所以，master實(shí)際中通常都是負(fù)載很輕的。Bigtable集群存儲(chǔ)了大量的表。每個(gè)表由一系列的tablet組成，每個(gè)tablet包含一個(gè)行組的所有相關(guān)數(shù)據(jù)。一開始，每個(gè)表由一個(gè)tablet組成。隨著表格的增長，它會(huì)自動(dòng)分割成多個(gè)tablet，它們大小默認(rèn)是100-200MB。5.1 Tab

20、let存放位置我們使用一個(gè)類似于B+樹的三級(jí)結(jié)構(gòu)來存儲(chǔ)tablet的放置信息如圖4。第一級(jí)是一個(gè)存儲(chǔ)在Chubby的包含了root tablet位置信息的文件。root tablet包含了在一個(gè)特殊的METADATA表里的所有tablet的位置信息root tablet實(shí)際上是METADATA表的第一個(gè)tablet，它存儲(chǔ)了該表其他的tablet的位置信息。每個(gè)METADATA tablet包含了一集用戶tablet的位置。Root tablet僅僅是METADATA表的第一個(gè)tablet，但是是特殊對(duì)待的-它永遠(yuǎn)不會(huì)被分割-為了保證tablet位置信息的層次結(jié)構(gòu)不會(huì)超過3級(jí)。METADATA

21、表的每一個(gè)行關(guān)鍵字(由tablet所屬的表標(biāo)識(shí)符和它的結(jié)束行組成)下存儲(chǔ)了一個(gè)tablet的位置。每個(gè)METADATA行在內(nèi)存中大概存儲(chǔ)了1KB數(shù)據(jù)。我們限制METADATA的tablet的大小為128MB，我們的三級(jí)層次結(jié)構(gòu)足以用來尋址234個(gè)tablet(如果tablet按照128MB算，就是261字節(jié))root tablet大小為128M，每個(gè)行1KB，那么它就可以存儲(chǔ)128*220/210=128*210個(gè)METADATA tablet，同樣的，每個(gè)METADATA tablet可以存儲(chǔ)128*210個(gè)普通tablet，這樣總共可以存儲(chǔ)128*210*128*210即234個(gè)普通tab

22、let，每個(gè)tablet又將近1KB數(shù)據(jù)，這樣算起來存儲(chǔ)這些元信息就需要4TB的數(shù)據(jù)，所以該METADATA表也不可能全部放入內(nèi)存，而是采用與普通的表一樣的存儲(chǔ)方式，放在GFS上。但是會(huì)把某些特殊信息放在內(nèi)存中，比如第6節(jié)提到的：METADATA中的location列族會(huì)被放入內(nèi)存。客戶端庫會(huì)緩存tablet的位置信息。如果客戶端不知道某個(gè)tablet的信息，或者發(fā)現(xiàn)緩存的位置信息是錯(cuò)誤的，那么它就會(huì)遞歸地在tablet位置存儲(chǔ)結(jié)構(gòu)中查找。如果客戶端緩存是空的，定位算法需要三次網(wǎng)絡(luò)往返，包括從Chubby的一次讀操作。如果客戶端緩存是陳舊的，定位算法將需要多達(dá)6次的往返，因?yàn)殛惻f的緩存值只有在

23、不命中時(shí)才會(huì)被發(fā)現(xiàn)(假設(shè)METADATA tablet并不會(huì)經(jīng)常移動(dòng))。盡管Tablet位置信息是存儲(chǔ)在內(nèi)存中(如上所述)，不需要訪問GFS，但是我們還是通過在客戶端庫里進(jìn)行預(yù)取來降低花費(fèi)：當(dāng)讀取METADATA表時(shí)，它會(huì)讀取不止一個(gè)tablet的信息。我們也會(huì)將一些額外信息存放在METADATA表里，包括對(duì)于每個(gè)tablet有關(guān)的事件日志(比如一個(gè)服務(wù)器何時(shí)開始提供服務(wù))。這些信息對(duì)于調(diào)試和性能分析很有幫助。5.2 tablet分配每個(gè)Tablet一次只會(huì)分配給一個(gè)tablet服務(wù)器。Master保存了現(xiàn)有的活著的tablet服務(wù)器集合的所有行蹤，tablet服務(wù)器當(dāng)前分配的tablet，哪

24、些tablet未被分配。當(dāng)一個(gè)tablet沒有被分配并且有一個(gè)可以存儲(chǔ)該tablet的tablet服務(wù)器存在時(shí)，master通過給那個(gè)tablet服務(wù)器發(fā)送一個(gè)tablet負(fù)載請(qǐng)求來分配該tablet。Bigtable使用Chubby來追蹤tablet服務(wù)器的狀態(tài)。當(dāng)一個(gè)tablet服務(wù)器啟動(dòng)時(shí)，它創(chuàng)建并獲取一個(gè)在給定的Chubby目錄上的唯一命名的文件的獨(dú)占鎖。Master通過監(jiān)控這個(gè)目錄(服務(wù)器目錄)來發(fā)現(xiàn)tablet服務(wù)器。Tablet服務(wù)器如果丟失了它的獨(dú)占鎖(比如由于網(wǎng)絡(luò)問題)就停止它上面的tablet服務(wù)。一個(gè)tablet服務(wù)器會(huì)嘗試重新獲取在該文件上的獨(dú)占鎖，只要該文件還存在。如

25、果該文件也不存在了，那么tablet服務(wù)器就永遠(yuǎn)無法提供該服務(wù)了。當(dāng)一個(gè)tablet服務(wù)器停止(比如集群管理系統(tǒng)從集群中刪除了該tablet服務(wù)器機(jī)器)，它就會(huì)嘗試釋放這個(gè)鎖這樣master就可以更快地重新分配它上面的tablets了。Master負(fù)責(zé)檢測(cè)一個(gè)tablet服務(wù)器何時(shí)停止提供服務(wù)，以盡快重新安排它的tablets。為了進(jìn)行檢測(cè)，master周期性的向每個(gè)tablet服務(wù)器詢問它的鎖狀態(tài)。如果一個(gè)tablet服務(wù)器報(bào)告它丟失了它的鎖，或者master在它的幾次嘗試中不能到達(dá)一個(gè)服務(wù)器，master會(huì)嘗試獲取該服務(wù)器的鎖。如果master可以獲取該鎖，那么Chubby就是活的，而ta

26、blet服務(wù)器要么是死的要么因?yàn)槟承﹩栴}而無法到達(dá)Chubby，那么master就可以通過刪除它的server文件來使得該tablet服務(wù)器永遠(yuǎn)都不能提供服務(wù)。一旦一個(gè)服務(wù)器的文件被刪除了，master就可以將之前分配給該服務(wù)器的所有tablet移到那些為分配的tablet集合中。為了保證一個(gè)Bigtable集群不會(huì)因?yàn)榕cmaster和Chubby間的網(wǎng)絡(luò)問題而變得脆弱，如果master的Chubby會(huì)話過期了，master會(huì)自殺。然而，如前面所述，master的失敗并不會(huì)改變tablet服務(wù)器的tablet分配。當(dāng)master被集群管理系統(tǒng)啟動(dòng)后，在它可以改變tablets之前需要知道它們當(dāng)

27、前的分配狀態(tài)。Master在啟動(dòng)時(shí)執(zhí)行如下步驟：1.master在Chubby獲得一個(gè)唯一的master鎖，該鎖可以防止出現(xiàn)同時(shí)生成多個(gè)master實(shí)例。2.master掃描Chubby的服務(wù)器目錄來找到所有活著的服務(wù)器。3.master與活著的tablet服務(wù)器通信來發(fā)現(xiàn)每個(gè)服務(wù)器安排了哪些tablet。4.master掃描METADATA表來找到tablet集合。當(dāng)掃描中碰到一個(gè)未被分配的tablet，master會(huì)將它添加到未分配的tablet集合，并對(duì)這個(gè)tablet進(jìn)行分配。在METADATA的tablets未被分配之前，對(duì)于METADATA的掃描不能進(jìn)行。因此在開始掃描之前(步驟4

28、)，如果在步驟3沒有發(fā)現(xiàn)對(duì)于root tablet的分配，master會(huì)將root tablet添加到未分配tablets集合中。這個(gè)添加將會(huì)使root tablet變得可以被分配。因?yàn)閞oot tablet包含所有METADATA tablets的名稱，master當(dāng)掃描完root tablet后就能知道METADATA的所有的tablets。只有當(dāng)一個(gè)表被創(chuàng)建，現(xiàn)有的兩個(gè)tablets合并為一個(gè)，或者一個(gè)tablet被分割為一個(gè)時(shí)，現(xiàn)有的tablet集合才會(huì)發(fā)生變化。Master能夠追蹤所有的這些變化，因?yàn)樗?fù)責(zé)維護(hù)它們。Tablet分割需要特殊對(duì)待因?yàn)樗鼈兪怯梢粋€(gè)tablet服務(wù)器啟動(dòng)的

29、。Tablet服務(wù)器通過將新的tablet的信息記錄到METADATA表中來提交這個(gè)分割。當(dāng)分割提交后，它會(huì)通知master。為了防止分割通知丟失(因?yàn)閠ablet服務(wù)器或者master死了)，當(dāng)master向tablet服務(wù)器請(qǐng)求加載剛剛發(fā)生分割的那個(gè)tablet時(shí)，它會(huì)檢測(cè)到這個(gè)新的tablet。Tablet服務(wù)器會(huì)將這個(gè)分割通知master，因?yàn)樗贛ETADATA表中的tablet鍵值僅包含了master讓它加載的那個(gè)tablet的一部分。假設(shè)master沒有收到這個(gè)分割通知，那么它所記錄的tablet與METADATA表中的就是不一致的，這樣在它讓tablet服務(wù)器加載該tablet

30、時(shí)就會(huì)發(fā)現(xiàn)該不一致。5.3 tablet服務(wù)Tablet的持久性狀態(tài)是通過GFS進(jìn)行存儲(chǔ)的，如圖5所示。更新是提交到一個(gè)保存了redo記錄的提交日志里。在這些更新里，最近提交的那些被保存到內(nèi)存中一個(gè)叫做memtable的有序緩存里，老的更新則被保存在一系列的SSTable中。為了恢復(fù)一個(gè)tablet，tablet服務(wù)器從METADATA表中讀取該tablet的元數(shù)據(jù)。元數(shù)據(jù)中包含組成該tablet的SSTable列表，以及一系列的redo點(diǎn)(指向那些包含該tablet數(shù)據(jù)的commit日志條目)的集合。Tablet服務(wù)器將所有SSTable的索引讀入內(nèi)存，然后通過應(yīng)用那些從redo點(diǎn)開始以及提

31、交的更新操作來重新構(gòu)建memtable。更新操作肯定會(huì)被保存到commit log里，但是當(dāng)某個(gè)服務(wù)器掛掉時(shí)，它那些保存在memtable的最新的更新就不存在了，而redo點(diǎn)應(yīng)該就是記錄已保存到SSTable的與還在memtable中的操作的分界點(diǎn)，這樣通過重新執(zhí)行它之后的那些操作就可以將memtable重建redo點(diǎn)何時(shí)被更新?有多少個(gè)commit log?參見第6節(jié)當(dāng)一個(gè)寫操作到達(dá)一個(gè)tablet服務(wù)器時(shí)，服務(wù)器首先檢查它的格式是否合法，發(fā)送者是否有權(quán)限進(jìn)行該操作。權(quán)限檢查是通過從Chubby讀取一個(gè)允許的寫操作者列表(通常它直接存在于Chubby的客戶端緩存中)完成的。一個(gè)合法的變更會(huì)被

32、寫入到已提交日志里。操作的提交可以通過分組執(zhí)行來提高大量小變更操作出現(xiàn)時(shí)的吞吐率，當(dāng)該寫操作提交后，它的內(nèi)容會(huì)被插入到memtable里。當(dāng)一個(gè)讀操作到達(dá)一個(gè)tablet服務(wù)器時(shí)，類似的首先要進(jìn)行格式和權(quán)限檢查。一個(gè)合法的讀操作將會(huì)在一系列SSTable和memtable的一個(gè)合并視圖上執(zhí)行因?yàn)镾STable一旦寫入就不可變，這樣就使得更新操作必須寫到新的SSTable中，這樣就導(dǎo)致同一個(gè)key值可能在多個(gè)SSTable中出現(xiàn)，這樣讀取時(shí)就必須讀取多個(gè)SSTable才能得到它真實(shí)的最終狀態(tài)。因?yàn)镾STable和memtable都是字典有序的數(shù)據(jù)結(jié)構(gòu)，因此可以很快生成這個(gè)視圖。為了讀取一個(gè)key

33、時(shí)，要讀入所有的SSTable，所以第6節(jié)有一個(gè)針對(duì)該問題的優(yōu)化Bloom Filter。此外伴隨著SSTable的增多，這種視圖合并也會(huì)變得低效，所以也引出了下面的Compation當(dāng)tablet發(fā)生分割或者合并時(shí)，也可以繼續(xù)接受讀寫操作。5.4 compaction伴隨著寫操作的執(zhí)行，memtable的大小會(huì)逐漸變大。當(dāng)memtable大小增長到一個(gè)閾值，這個(gè)memtable就會(huì)被凍結(jié)，一個(gè)新的memtable被創(chuàng)建，被凍結(jié)的舊的memtable會(huì)被轉(zhuǎn)化為一個(gè)SSTable寫入GFS。這個(gè)minor compaction過程有兩個(gè)目的：降低tablet server的內(nèi)存使用，降低該tab

34、let服務(wù)器掛掉時(shí)需要從已提交日志中讀取的數(shù)據(jù)大小。當(dāng)compaction發(fā)生時(shí)，也可以繼續(xù)接受讀寫操作。每次minor Compation會(huì)創(chuàng)建一個(gè)新的SSTable。如果這個(gè)行為持續(xù)的進(jìn)行而不檢查，那么讀操作就可能會(huì)需要從大量的SSTable中合并它們的更新。我們通過周期性的執(zhí)行一個(gè)merging compaction來將這樣的文件數(shù)目限制在一定范圍內(nèi)。一個(gè)merging compaction讀取多個(gè)SStable和memtable，然后寫入到一個(gè)新的SSTable(形成一個(gè)最終的歸并視圖)。一旦這個(gè)compaction結(jié)束，這些SSTable和memtable就可以丟棄了。將多個(gè)SSTa

35、ble重新寫入到一個(gè)SSTable的merging compaction稱為主compaction。由非主compaction產(chǎn)生的SSTable里可以包含一些在舊的SSTable中仍然存活但是目前已經(jīng)被刪除的數(shù)據(jù)。另一方面，一個(gè)主compaction產(chǎn)生的SSTable不會(huì)包含刪除操作信息或者已刪除數(shù)據(jù)。Bigtable循環(huán)掃描它所有的tablet，周期的對(duì)它們執(zhí)行主compaction。這些主compaction使得Bigtable可以回收那些被已刪除的數(shù)據(jù)使用的資源。這也保證那些已經(jīng)刪除的數(shù)據(jù)在一定時(shí)間內(nèi)會(huì)從系統(tǒng)中消失，這對(duì)于那些存儲(chǔ)敏感數(shù)據(jù)的服務(wù)來說很重要。6技巧前面一節(jié)描述的實(shí)現(xiàn)需要

36、大量的技巧來到達(dá)用戶所需要的高性能，可用性，可靠性。這一節(jié)更細(xì)節(jié)地描述下實(shí)現(xiàn)的各個(gè)部分，著重講述下使用的這些技巧。局部性群組(對(duì)應(yīng)一個(gè)SSTable)用戶可以將多個(gè)列族組織為一個(gè)局部性群組。對(duì)于每個(gè)tablet里的每個(gè)局部性群組都會(huì)生成一個(gè)單獨(dú)的SSTable。將那些通常不會(huì)被一起訪問的列族分離到獨(dú)立的局部性群組可以增加訪問的效率。比如，webtable的關(guān)于網(wǎng)頁的元數(shù)據(jù)(比如語言，校驗(yàn)和)可放到一個(gè)局部性群組，網(wǎng)頁內(nèi)容可以放到另一個(gè)群組里：這樣一個(gè)訪問元數(shù)據(jù)的應(yīng)用程序就不需要讀取所有網(wǎng)頁的內(nèi)容。另外，一些有用的tuning參數(shù)也可以以局部性群組為單位進(jìn)行設(shè)置。比如一個(gè)局部性群組可以聲明為放入

37、內(nèi)存的。對(duì)于聲明為放入內(nèi)存的局部性群組的SSTable在需要時(shí)才會(huì)加載到tablet服務(wù)器的內(nèi)存中。一旦加載之后，對(duì)于該局部性群組的訪問就不需要訪問磁盤。這個(gè)特點(diǎn)對(duì)于那些需要經(jīng)常訪問的小片數(shù)據(jù)很有用：比如在Bigtable內(nèi)部我們將它應(yīng)用在METADATA表的location列族上。壓縮用戶可以控制對(duì)于一個(gè)局部性群組的SSTables是否進(jìn)行壓縮，以及使用哪種壓縮格式。用戶指定的壓縮格式會(huì)應(yīng)用在SSTable的每個(gè)塊上(塊大小可以通過一個(gè)局部性群組的參數(shù)進(jìn)行控制)。對(duì)于每個(gè)塊單獨(dú)進(jìn)行壓縮，盡管這使我們丟失了一些空間，但是這使得我們不需要解壓整個(gè)文件就可以讀取SSTable的部分內(nèi)容。很多用戶使

38、用一個(gè)兩遍壓縮模式，第一遍壓縮使用Bentley and McIlroy模式，該模式在一個(gè)很大的窗口大小里壓縮普通的長字符串。第二遍壓縮了一個(gè)快速壓縮算法，該算法在一個(gè)小的16KB窗口大小內(nèi)查找重復(fù)。這兩遍壓縮都很快速，壓縮速率在100-200MB/s，解壓速率在400-1000MB/s。盡管在選擇壓縮算法時(shí)，我們更重視速率而不是空間的減少，但是這個(gè)兩遍壓縮模式或做的出奇地好。比如，在webtable里我們使用這種壓縮模式存儲(chǔ)網(wǎng)頁內(nèi)容。實(shí)驗(yàn)中，我們?cè)谝粋€(gè)壓縮的局部性群組里存儲(chǔ)了大量文檔。為了實(shí)驗(yàn)?zāi)康?，我們將文檔的版本數(shù)限制為1。該壓縮模式達(dá)到了10：1的壓縮率。這比通常的Gzip對(duì)于HTML網(wǎng)

39、頁的3：1或4：1的壓縮率要好多了。這是由我們的webtable的行分布方式造成的：來自相同主機(jī)的網(wǎng)頁被存儲(chǔ)在相鄰的位置。這使Bentley and McIlroy算法可以識(shí)別出來自相同站點(diǎn)的大量固有模式。很多應(yīng)用程序，不僅僅是webtable，選擇的行名稱使得類似數(shù)據(jù)會(huì)聚集在一起，因此達(dá)到了很好的壓縮率。當(dāng)我們?cè)贐igtable中存儲(chǔ)相同值的多個(gè)版本時(shí)壓縮率會(huì)更好。為了讀性能進(jìn)行緩存為了提高讀性能，tablet服務(wù)器使用一個(gè)二級(jí)緩存。掃描緩存是一個(gè)用來緩存由SSTable返回給tablet服務(wù)器的key-value對(duì)的高級(jí)緩存。塊緩存是用來緩存從GFS讀取的SSTable塊的低級(jí)緩存。掃描緩

40、存主要用于那些傾向于重復(fù)讀取相同數(shù)據(jù)的應(yīng)用，塊緩存則用于那些傾向于從最近讀取的數(shù)據(jù)的鄰近位置讀取數(shù)據(jù)的應(yīng)用(比如順序讀，或者讀取一個(gè)熱點(diǎn)行內(nèi)的相同局部性群組里的不同列值)。Bloom Filters正如5.3節(jié)所描述的，一個(gè)讀操作需要從組成該tablet的所有SSTable里讀取。如果這些SSTable不在內(nèi)存，就需要很多磁盤操作。通過讓用戶為某個(gè)局部性群組的SSTables指定對(duì)應(yīng)的Bloom filters，可以降低磁盤訪問次數(shù)。一個(gè)Bloom Filter允許我們查詢對(duì)應(yīng)的SSTable是否包含某個(gè)給定的row/column對(duì)的數(shù)據(jù)。對(duì)于特定的應(yīng)用程序來說，只需要很少的tablet服務(wù)器

41、內(nèi)存來保存Bloom Filter，但可以大大減少讀操作所需要的磁盤操作。同時(shí)Bloom Filter可以避免那些對(duì)于不存在的行列的查找訪問磁盤。提交日志實(shí)現(xiàn)如果我們?yōu)槊總€(gè)tablet的提交日志建立一個(gè)獨(dú)立的日志文件，就會(huì)使得大量的文件需要并發(fā)寫入GFS。由于每個(gè)GFS服務(wù)器的底層文件系統(tǒng)實(shí)現(xiàn)，這些寫操作會(huì)引起在不同物理日志文件上的大量的磁盤尋道。另外，每個(gè)tablet一個(gè)日志文件會(huì)降低分組提交優(yōu)化的效率。為了解決這些問題，每個(gè)tablet服務(wù)器將更新操作append一個(gè)日志文件里，將對(duì)于不同的tablet的變更放到同一個(gè)物理日志文件里。使用一個(gè)日志為正常操作提供了很明顯的性能好處，但是使恢復(fù)

42、變復(fù)雜了。當(dāng)一個(gè)tablet服務(wù)器掛掉后，它負(fù)責(zé)的那些tablet需要移動(dòng)到大量其他的tablet服務(wù)器上：每個(gè)服務(wù)器通常都會(huì)加載一些該服務(wù)器的tablet。為了恢復(fù)一個(gè)tablet的狀態(tài)，新的tablet服務(wù)器需要通過原來那個(gè)tablet服務(wù)器的提交日志重新應(yīng)用這個(gè)tablet的變更操作。然而對(duì)于這些tablet的變更是混在同一個(gè)日志文件里的。一種方法是，每個(gè)新的tablet服務(wù)器全部讀取這個(gè)日志文件，然后僅應(yīng)用那些它需要恢復(fù)的tablet的變更操作。然而，在這種模式下，如果失敗的那臺(tái)tablet服務(wù)器的tablet被分配到了100個(gè)機(jī)器，那么這個(gè)日志文件就需要讀取100次。我們通過對(duì)提交日志里的entry根據(jù)table,row name,log sequence number進(jìn)行排序避免了重復(fù)的日志讀取。在已排序的輸出中，對(duì)于一個(gè)tablet的所有變更都是連續(xù)的，因此可以通過一次的磁盤尋道和順序讀操