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

2、許客戶(hù)端動(dòng)態(tài)控制數(shù)據(jù)分布和格式的簡(jiǎn)單數(shù)據(jù)模型，此外還會(huì)描述Bigtable的設(shè)計(jì)和實(shí)現(xiàn)。1.導(dǎo)引在過(guò)去的2年半時(shí)間里，我們?cè)O(shè)計(jì),實(shí)現(xiàn),部署了一個(gè)稱(chēng)為Bigtable的用來(lái)管理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ù)載類(lèi)型，從面向

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

4、管用戶(hù)經(jīng)常將各種形式的結(jié)構(gòu)化或半結(jié)構(gòu)化的數(shù)據(jù)存儲(chǔ)到這些字符串里。用戶(hù)可以通過(guò)在schema中的細(xì)心選擇來(lái)控制數(shù)據(jù)的locality。最后，Bigtable的schema參數(shù)還允許用戶(hù)選擇從磁盤(pán)還是內(nèi)存獲取數(shù)據(jù)。第2節(jié)更加詳細(xì)的描述了該數(shù)據(jù)模型。第3節(jié)提供了關(guān)于用戶(hù)API的概覽。第4節(jié)簡(jiǎn)要描述了Bigtable所依賴(lài)的底層軟件。第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ò)行關(guān)鍵字，列關(guān)鍵字以及時(shí)間戳進(jìn)行索引的；map中的每個(gè)值都是一個(gè)未經(jīng)解釋的字節(jié)數(shù)組。(row：string,column：string,time：int64)-string我們?cè)趯?duì)于這種類(lèi)Bigtable系統(tǒng)的潛在使用場(chǎng)景進(jìn)行了大量考察后，最終確定了這個(gè)數(shù)據(jù)模型。舉一個(gè)影響到我們的某些設(shè)計(jì)決策的具體例子，比如我們想保存一份可以被很多工程使用的一大集網(wǎng)頁(yè)及其相關(guān)信息的拷貝。我們把這個(gè)表稱(chēng)為webtable，在這個(gè)表中，我們可以使用URL作為行關(guān)鍵字，網(wǎng)頁(yè)的

6、各種信息作為列名稱(chēng)，將網(wǎng)頁(yè)的內(nèi)容作為表的內(nèi)容存儲(chǔ)：獲取的時(shí)候還需要在列上加上時(shí)間戳，如圖1所示。表中的行關(guān)鍵字是大字符串(目前最大可以到64KB，盡管對(duì)于大多數(shù)用戶(hù)來(lái)說(shuō)最常用的是10-100字節(jié))。在一個(gè)行關(guān)鍵字下的數(shù)據(jù)讀寫(xiě)是原子性的(無(wú)論這一行有多少個(gè)不同的列被讀寫(xiě))，這個(gè)設(shè)計(jì)使得用戶(hù)在對(duì)相同行的并發(fā)更新出現(xiàn)時(shí)，更容易理解系統(tǒng)的行為。Bigtable按照行關(guān)鍵字的字典序來(lái)維護(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)行通信?？蛻?hù)端可以通過(guò)選擇行關(guān)鍵字來(lái)利用這個(gè)屬性，這樣它們可以為數(shù)據(jù)訪(fǎng)問(wèn)得到好的局部性。比如，在webtable里，相同域名的網(wǎng)頁(yè)可以通過(guò)將URL中的域名反轉(zhuǎn)而使他們放在連續(xù)的行里來(lái)組織到一塊。比如我們將網(wǎng)頁(yè)/index.html的數(shù)據(jù)存放在關(guān)鍵字com.google.maps/index.html下。將相同域名的網(wǎng)頁(yè)存儲(chǔ)在鄰近位置可以使對(duì)主機(jī)或域名的分析更加有效。列族不同的列關(guān)鍵字可以被分組到一個(gè)集合，我們把這樣的一個(gè)集合稱(chēng)為一個(gè)列族，它是基本的訪(fǎng)問(wèn)控制單元。存儲(chǔ)在同一個(gè)列族的數(shù)據(jù)通常是相同類(lèi)型的(我們將同一列族的數(shù)據(jù)壓縮在一塊)。在數(shù)據(jù)能夠存儲(chǔ)到某個(gè)列族的

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

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

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

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

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

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

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

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

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

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è)集群來(lái)說(shuō)，由于Chubby不可用造成的這個(gè)概率是0.0326%。5.實(shí)現(xiàn)Bigtable實(shí)現(xiàn)有3個(gè)主要的組件：每個(gè)客戶(hù)端需要鏈接的庫(kù)，一個(gè)master服務(wù)器，很多tablet服務(wù)器。tablet服務(wù)器可以從一個(gè)集群中動(dòng)態(tài)添加(或者刪除)來(lái)適應(yīng)工作負(fù)載的動(dòng)態(tài)變化。Master負(fù)責(zé)將tablet分配到tablet服務(wù)器，檢測(cè)tablet服務(wù)器的添加和過(guò)期，平

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的讀寫(xiě)請(qǐng)求，也會(huì)將那些過(guò)于大的tablet進(jìn)行分割。tablet服務(wù)器本身實(shí)際上也是GFS的用戶(hù)，它們只是負(fù)載它加載的那些tablet的管理，這些tablet的物理存儲(chǔ)并不一定存放在管理它的服務(wù)器上，底層的存儲(chǔ)是由GFS完成的，tablet服務(wù)器可以只調(diào)用它的接口來(lái)完成相應(yīng)任務(wù)。而METADATA表中的位置信息應(yīng)該是指某個(gè)tablet

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

20、let存放位置我們使用一個(gè)類(lèi)似于B+樹(shù)的三級(jí)結(jié)構(gòu)來(lái)存儲(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包含了一集用戶(hù)tablet的位置。Root tablet僅僅是METADATA表的第一個(gè)tablet，但是是特殊對(duì)待的-它永遠(yuǎn)不會(huì)被分割-為了保證tablet位置信息的層次結(jié)構(gòu)不會(huì)超過(guò)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)足以用來(lái)尋址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ù)，這樣算起來(lái)存儲(chǔ)這些元信息就需要4TB的數(shù)據(jù)，所以該METADATA表也不可能全部放入內(nèi)存，而是采用與普通的表一樣的存儲(chǔ)方式，放在GFS上。但是會(huì)把某些特殊信息放在內(nèi)存中，比如第6節(jié)提到的：METADATA中的location列族會(huì)被放入內(nèi)存。客戶(hù)端庫(kù)會(huì)緩存tablet的位置信息。如果客戶(hù)端不知道某個(gè)tablet的信息，或者發(fā)現(xiàn)緩存的位置信息是錯(cuò)誤的，那么它就會(huì)遞歸地在tablet位置存儲(chǔ)結(jié)構(gòu)中查找。如果客戶(hù)端緩存是空的，定位算法需要三次網(wǎng)絡(luò)往返，包括從Chubby的一次讀操作。如果客戶(hù)端緩存是陳舊的，定位算法將需要多達(dá)6次的往返，因?yàn)殛惻f的緩存值只有在

23、不命中時(shí)才會(huì)被發(fā)現(xiàn)(假設(shè)METADATA tablet并不會(huì)經(jīng)常移動(dòng))。盡管Tablet位置信息是存儲(chǔ)在內(nèi)存中(如上所述)，不需要訪(fǎng)問(wèn)GFS，但是我們還是通過(guò)在客戶(hù)端庫(kù)里進(jìn)行預(yù)取來(lái)降低花費(fèi)：當(dāng)讀取METADATA表時(shí)，它會(huì)讀取不止一個(gè)tablet的信息。我們也會(huì)將一些額外信息存放在METADATA表里，包括對(duì)于每個(gè)tablet有關(guān)的事件日志(比如一個(gè)服務(wù)器何時(shí)開(kāi)始提供服務(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沒(méi)有被分配并且有一個(gè)可以存儲(chǔ)該tablet的tablet服務(wù)器存在時(shí)，master通過(guò)給那個(gè)tablet服務(wù)器發(fā)送一個(gè)tablet負(fù)載請(qǐng)求來(lái)分配該tablet。Bigtable使用Chubby來(lái)追蹤tablet服務(wù)器的狀態(tài)。當(dāng)一個(gè)tablet服務(wù)器啟動(dòng)時(shí)，它創(chuàng)建并獲取一個(gè)在給定的Chubby目錄上的唯一命名的文件的獨(dú)占鎖。Master通過(guò)監(jiān)控這個(gè)目錄(服務(wù)器目錄)來(lái)發(fā)現(xiàn)tablet服務(wù)器。Tablet服務(wù)器如果丟失了它的獨(dú)占鎖(比如由于網(wǎng)絡(luò)問(wèn)題)就停止它上面的tablet服務(wù)。一個(gè)tablet服務(wù)器會(huì)嘗試重新獲取在該文件上的獨(dú)占鎖，只要該文件還存在。如

25、果該文件也不存在了，那么tablet服務(wù)器就永遠(yuǎn)無(wú)法提供該服務(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ù)器詢(xún)問(wèn)它的鎖狀態(tài)。如果一個(gè)tablet服務(wù)器報(bào)告它丟失了它的鎖，或者master在它的幾次嘗試中不能到達(dá)一個(gè)服務(wù)器，master會(huì)嘗試獲取該服務(wù)器的鎖。如果master可以獲取該鎖，那么Chubby就是活的，而ta

26、blet服務(wù)器要么是死的要么因?yàn)槟承﹩?wèn)題而無(wú)法到達(dá)Chubby，那么master就可以通過(guò)刪除它的server文件來(lái)使得該tablet服務(wù)器永遠(yuǎn)都不能提供服務(wù)。一旦一個(gè)服務(wù)器的文件被刪除了，master就可以將之前分配給該服務(wù)器的所有tablet移到那些為分配的tablet集合中。為了保證一個(gè)Bigtable集群不會(huì)因?yàn)榕cmaster和Chubby間的網(wǎng)絡(luò)問(wèn)題而變得脆弱，如果master的Chubby會(huì)話(huà)過(guò)期了，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ù)器目錄來(lái)找到所有活著的服務(wù)器。3.master與活著的tablet服務(wù)器通信來(lái)發(fā)現(xiàn)每個(gè)服務(wù)器安排了哪些tablet。4.master掃描METADATA表來(lái)找到tablet集合。當(dāng)掃描中碰到一個(gè)未被分配的tablet，master會(huì)將它添加到未分配的tablet集合，并對(duì)這個(gè)tablet進(jìn)行分配。在METADATA的tablets未被分配之前，對(duì)于METADATA的掃描不能進(jìn)行。因此在開(kāi)始掃描之前(步驟4

28、)，如果在步驟3沒(méi)有發(fā)現(xiàn)對(duì)于root tablet的分配，master會(huì)將root tablet添加到未分配tablets集合中。這個(gè)添加將會(huì)使root tablet變得可以被分配。因?yàn)閞oot tablet包含所有METADATA tablets的名稱(chēng)，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ù)器通過(guò)將新的tablet的信息記錄到METADATA表中來(lái)提交這個(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沒(méi)有收到這個(gè)分割通知，那么它所記錄的tablet與METADATA表中的就是不一致的，這樣在它讓tablet服務(wù)器加載該tablet

30、時(shí)就會(huì)發(fā)現(xiàn)該不一致。5.3 tablet服務(wù)Tablet的持久性狀態(tài)是通過(guò)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)存，然后通過(guò)應(yīng)用那些從redo點(diǎn)開(kāi)始以及提

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

32、寫(xiě)入到已提交日志里。操作的提交可以通過(guò)分組執(zhí)行來(lái)提高大量小變更操作出現(xiàn)時(shí)的吞吐率，當(dāng)該寫(xiě)操作提交后，它的內(nèi)容會(huì)被插入到memtable里。當(dāng)一個(gè)讀操作到達(dá)一個(gè)tablet服務(wù)器時(shí)，類(lèi)似的首先要進(jìn)行格式和權(quán)限檢查。一個(gè)合法的讀操作將會(huì)在一系列SSTable和memtable的一個(gè)合并視圖上執(zhí)行因?yàn)镾STable一旦寫(xiě)入就不可變，這樣就使得更新操作必須寫(xiě)到新的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ì)該問(wèn)題的優(yōu)化Bloom Filter。此外伴隨著SSTable的增多，這種視圖合并也會(huì)變得低效，所以也引出了下面的Compation當(dāng)tablet發(fā)生分割或者合并時(shí)，也可以繼續(xù)接受讀寫(xiě)操作。5.4 compaction伴隨著寫(xiě)操作的執(zhí)行，memtable的大小會(huì)逐漸變大。當(dāng)memtable大小增長(zhǎng)到一個(gè)閾值，這個(gè)memtable就會(huì)被凍結(jié)，一個(gè)新的memtable被創(chuàng)建，被凍結(jié)的舊的memtable會(huì)被轉(zhuǎn)化為一個(gè)SSTable寫(xiě)入GFS。這個(gè)minor compaction過(guò)程有兩個(gè)目的：降低tablet server的內(nèi)存使用，降低該tab

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

35、ble重新寫(xiě)入到一個(gè)SSTable的merging compaction稱(chēng)為主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ù)來(lái)說(shuō)很重要。6技巧前面一節(jié)描述的實(shí)現(xiàn)需要

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

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

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

39、頁(yè)的3：1或4：1的壓縮率要好多了。這是由我們的webtable的行分布方式造成的：來(lái)自相同主機(jī)的網(wǎng)頁(yè)被存儲(chǔ)在相鄰的位置。這使Bentley and McIlroy算法可以識(shí)別出來(lái)自相同站點(diǎn)的大量固有模式。很多應(yīng)用程序，不僅僅是webtable，選擇的行名稱(chēng)使得類(lèi)似數(shù)據(jù)會(huì)聚集在一起，因此達(dá)到了很好的壓縮率。當(dāng)我們?cè)贐igtable中存儲(chǔ)相同值的多個(gè)版本時(shí)壓縮率會(huì)更好。為了讀性能進(jìn)行緩存為了提高讀性能，tablet服務(wù)器使用一個(gè)二級(jí)緩存。掃描緩存是一個(gè)用來(lái)緩存由SSTable返回給tablet服務(wù)器的key-value對(duì)的高級(jí)緩存。塊緩存是用來(lái)緩存從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)存，就需要很多磁盤(pán)操作。通過(guò)讓用戶(hù)為某個(gè)局部性群組的SSTables指定對(duì)應(yīng)的Bloom filters，可以降低磁盤(pán)訪(fǎng)問(wèn)次數(shù)。一個(gè)Bloom Filter允許我們查詢(xún)對(duì)應(yīng)的SSTable是否包含某個(gè)給定的row/column對(duì)的數(shù)據(jù)。對(duì)于特定的應(yīng)用程序來(lái)說(shuō)，只需要很少的tablet服務(wù)器

41、內(nèi)存來(lái)保存Bloom Filter，但可以大大減少讀操作所需要的磁盤(pán)操作。同時(shí)Bloom Filter可以避免那些對(duì)于不存在的行列的查找訪(fǎng)問(wèn)磁盤(pán)。提交日志實(shí)現(xiàn)如果我們?yōu)槊總€(gè)tablet的提交日志建立一個(gè)獨(dú)立的日志文件，就會(huì)使得大量的文件需要并發(fā)寫(xiě)入GFS。由于每個(gè)GFS服務(wù)器的底層文件系統(tǒng)實(shí)現(xiàn)，這些寫(xiě)操作會(huì)引起在不同物理日志文件上的大量的磁盤(pán)尋道。另外，每個(gè)tablet一個(gè)日志文件會(huì)降低分組提交優(yōu)化的效率。為了解決這些問(wèn)題，每個(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ù)器需要通過(guò)原來(lái)那個(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次。我們通過(guò)對(duì)提交日志里的entry根據(jù)table,row name,log sequence number進(jìn)行排序避免了重復(fù)的日志讀取。在已排序的輸出中，對(duì)于一個(gè)tablet的所有變更都是連續(xù)的，因此可以通過(guò)一次的磁盤(pán)尋道和順序讀操