摘要

Bigtable是一個(gè)分布式的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)系統(tǒng)，它被設(shè)計(jì)用來處理海量數(shù)據(jù)：通常是分布在數(shù)千臺(tái)普通服務(wù)器上的PB級(jí)的數(shù)據(jù)。Google 的很多項(xiàng)目使用Bigtable存儲(chǔ)數(shù)據(jù)，包括Web索引、Google Earth、Google Finance。這些應(yīng)用對(duì)Bigtable提出的要求差異非常大，無論是在數(shù)據(jù)量上（從URL到網(wǎng)頁到衛(wèi)星圖像）還是在響應(yīng)速度上（從后端的批量處理到實(shí)時(shí)數(shù)據(jù)服務(wù)）。盡管應(yīng)用需求差異很大，但是，針對(duì)Google的這些產(chǎn)品，Bigtable還是成功的提供了一個(gè)靈活的、高性能的解決方案。本論文描述了Bigtable提供的簡單的數(shù)據(jù)模型，利用這個(gè)模型，用戶可以動(dòng)態(tài)的控制數(shù)據(jù)的分布和格式；我們還將描述Bigtable的設(shè)計(jì)和實(shí)現(xiàn)。

1 介紹

在過去兩年半時(shí)間里，我們?cè)O(shè)計(jì)、實(shí)現(xiàn)并部署了一個(gè)分布式的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)系統(tǒng) — 在Google，我們稱之為Bigtable。Bigtable的設(shè)計(jì)目的是可靠的處理PB級(jí)別的數(shù)據(jù)，并且能夠部署到上千臺(tái)機(jī)器上。Bigtable已經(jīng)實(shí)現(xiàn)了下面的幾個(gè)目標(biāo)：適用性廣泛、可擴(kuò)展、高性能和高可用性。Bigtable已經(jīng)在超過60個(gè)Google的產(chǎn)品和項(xiàng)目上得到了應(yīng)用，包括 Google Analytics、Google Finance、Orkut、Personalized Search、Writely和Google Earth。這些產(chǎn)品對(duì)Bigtable提出了迥異的需求，有的需要高吞吐量的批處理，有的則需要及時(shí)響應(yīng)，快速返回?cái)?shù)據(jù)給最終用戶。它們使用的 Bigtable集群的配置也有很大的差異，有的集群只有幾臺(tái)服務(wù)器，而有的則需要上千臺(tái)服務(wù)器、存儲(chǔ)幾百TB的數(shù)據(jù)。

在很多方面，Bigtable和數(shù)據(jù)庫很類似：它使用了很多數(shù)據(jù)庫的實(shí)現(xiàn)策略。并行數(shù)據(jù)庫【14】和內(nèi)存數(shù)據(jù)庫【13】已經(jīng)具備可擴(kuò)展性和高性能，但是Bigtable提供了一個(gè)和這些系統(tǒng)完全不同的接口。Bigtable不支持完整的關(guān)系數(shù)據(jù)模型；與之相反，Bigtable為客戶提供了簡單的數(shù)據(jù)模型，利用這個(gè)模型，客戶可以動(dòng)態(tài)控制數(shù)據(jù)的分布和格式（alex 注：也就是對(duì)BigTable而言，數(shù)據(jù)是沒有格式的，用數(shù)據(jù)庫領(lǐng)域的術(shù)語說，就是數(shù)據(jù)沒有Schema，用戶自己去定義Schema），用戶也可以自己推測(cè)(alex注：reason about)底層存儲(chǔ)數(shù)據(jù)的位置相關(guān)性(alex注：位置相關(guān)性可以這樣理解，比如樹狀結(jié)構(gòu)，具有相同前綴的數(shù)據(jù)的存放位置接近。在讀取的時(shí)候，可以把這些數(shù)據(jù)一次讀取出來)。數(shù)據(jù)的下標(biāo)是行和列的名字，名字可以是任意的字符串。Bigtable將存儲(chǔ)的數(shù)據(jù)都視為字符串，但是Bigtable本身不去解析這些字符串，客戶程序通常會(huì)在把各種結(jié)構(gòu)化或者半結(jié)構(gòu)化的數(shù)據(jù)串行化到這些字符串里。通過仔細(xì)選擇數(shù)據(jù)的模式，客戶可以控制數(shù)據(jù)的位置相關(guān)性。最后，可以通過BigTable的模式參數(shù)來控制數(shù)據(jù)是存放在內(nèi)存中、還是硬盤上。

第二節(jié)描述關(guān)于數(shù)據(jù)模型更多細(xì)節(jié)方面的東西；第三節(jié)概要介紹了客戶端API；第四節(jié)簡要介紹了BigTable底層使用的Google的基礎(chǔ)框架；第五節(jié)描述了BigTable實(shí)現(xiàn)的關(guān)鍵部分；第6節(jié)描述了我們?yōu)榱颂岣連igTable的性能采用的一些精細(xì)的調(diào)優(yōu)方法；第7節(jié)提供了BigTable的性能數(shù)據(jù)；第8節(jié)講述了幾個(gè)Google內(nèi)部使用BigTable的例子；第9節(jié)是我們?cè)谠O(shè)計(jì)和后期支持過程中得到一些經(jīng)驗(yàn)和教訓(xùn)；最后，在第10節(jié)列出我們的相關(guān)研究工作，第11節(jié)是我們的結(jié)論。

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

Bigtable是一個(gè)稀疏的、分布式的、持久化存儲(chǔ)的多維度排序Map（alex注：對(duì)于程序員來說，Map應(yīng)該不用翻譯了吧。Map由key和value組成，后面我們直接使用key和value，不再另外翻譯了）。Map的索引是行關(guān)鍵字、列關(guān)鍵字以及時(shí)間戳；Map中的每個(gè)value都是一個(gè)未經(jīng)解析的byte數(shù)組。

 

(row:string, column:string,time:int64)->string 

我們?cè)谧屑?xì)分析了一個(gè)類似Bigtable的系統(tǒng)的種種潛在用途之后，決定使用這個(gè)數(shù)據(jù)模型。我們先舉個(gè)具體的例子，這個(gè)例子促使我們做了很多設(shè)計(jì)決策；假設(shè)我們想要存儲(chǔ)海量的網(wǎng)頁及相關(guān)信息，這些數(shù)據(jù)可以用于很多不同的項(xiàng)目，我們姑且稱這個(gè)特殊的表為Webtable。在Webtable里，我們使用URL作為行關(guān)鍵字，使用網(wǎng)頁的某些屬性作為列名，網(wǎng)頁的內(nèi)容存在“contents:”列中，并用獲取該網(wǎng)頁的時(shí)間戳作為標(biāo)識(shí)(alex注：即按照獲取時(shí)間不同，存儲(chǔ)了多個(gè)版本的網(wǎng)頁數(shù)據(jù))，如圖一所示。

圖一：一個(gè)存儲(chǔ)Web網(wǎng)頁的例子的表的片斷。行名是一個(gè)反向URL。contents列族存放的是網(wǎng)頁的內(nèi)容，anchor列族存放引用該網(wǎng)頁的錨鏈接文本（alex注：如果不知道HTML的Anchor，請(qǐng)Google一把）。CNN 的主頁被Sports Illustrater和MY-look的主頁引用，因此該行包含了名為“anchor:cnnsi.com”和 “anchhor:my.look.ca”的列。每個(gè)錨鏈接只有一個(gè)版本（alex 注：注意時(shí)間戳標(biāo)識(shí)了列的版本，t9和t8分別標(biāo)識(shí)了兩個(gè)錨鏈接的版本）；而contents列則有三個(gè)版本，分別由時(shí)間戳 t3，t5，和t6標(biāo)識(shí)。

行

表中的行關(guān)鍵字可以是任意的字符串（目前支持最大64KB的字符串，但是對(duì)大多數(shù)用戶，10-100個(gè)字節(jié)就足夠了）。對(duì)同一個(gè)行關(guān)鍵字的讀或者寫操作都是原子的（不管讀或者寫這一行里多少個(gè)不同列），這個(gè)設(shè)計(jì)決策能夠使用戶很容易的理解程序在對(duì)同一個(gè)行進(jìn)行并發(fā)更新操作時(shí)的行為。

Bigtable通過行關(guān)鍵字的字典順序來組織數(shù)據(jù)。表中的每個(gè)行都可以動(dòng)態(tài)分區(qū)。每個(gè)分區(qū)叫做一個(gè)”Tablet”，Tablet是數(shù)據(jù)分布和負(fù)載均衡調(diào)整的最小單位。這樣做的結(jié)果是，當(dāng)操作只讀取行中很少幾列的數(shù)據(jù)時(shí)效率很高，通常只需要很少幾次機(jī)器間的通信即可完成。用戶可以通過選擇合適的行關(guān)鍵字，在數(shù)據(jù)訪問時(shí)有效利用數(shù)據(jù)的位置相關(guān)性，從而更好的利用這個(gè)特性。舉例來說，在Webtable里，通過反轉(zhuǎn)URL中主機(jī)名的方式，可以把同一個(gè)域名下的網(wǎng)頁聚集起來組織成連續(xù)的行。具體來說，我們可以把maps.google.com/index.html的數(shù)據(jù)存放在關(guān)鍵字 com.google.maps/index.html下。把相同的域中的網(wǎng)頁存儲(chǔ)在連續(xù)的區(qū)域可以讓基于主機(jī)和域名的分析更加有效。

列族

列關(guān)鍵字組成的集合叫做“列族“，列族是訪問控制的基本單位。存放在同一列族下的所有數(shù)據(jù)通常都屬于同一個(gè)類型（我們可以把同一個(gè)列族下的數(shù)據(jù)壓縮在一起）。列族在使用之前必須先創(chuàng)建，然后才能在列族中任何的列關(guān)鍵字下存放數(shù)據(jù)；列族創(chuàng)建后，其中的任何一個(gè)列關(guān)鍵字下都可以存放數(shù)據(jù)。根據(jù)我們的設(shè)計(jì)意圖，一張表中的列族不能太多（最多幾百個(gè)），并且列族在運(yùn)行期間很少改變。與之相對(duì)應(yīng)的，一張表可以有無限多個(gè)列。

列關(guān)鍵字的命名語法如下：列族：限定詞。 列族的名字必須是可打印的字符串，而限定詞的名字可以是任意的字符串。比如，Webtable有個(gè)列族language，language列族用來存放撰寫網(wǎng)頁的語言。我們?cè)趌anguage列族中只使用一個(gè)列關(guān)鍵字，用來存放每個(gè)網(wǎng)頁的語言標(biāo)識(shí)ID。Webtable中另一個(gè)有用的列族是anchor；這個(gè)列族的每一個(gè)列關(guān)鍵字代表一個(gè)錨鏈接，如圖一所示。Anchor列族的限定詞是引用該網(wǎng)頁的站點(diǎn)名；Anchor列族每列的數(shù)據(jù)項(xiàng)存放的是鏈接文本。

訪問控制、磁盤和內(nèi)存的使用統(tǒng)計(jì)都是在列族層面進(jìn)行的。在我們的Webtable的例子中，上述的控制權(quán)限能幫助我們管理不同類型的應(yīng)用：我們?cè)试S一些應(yīng)用可以添加新的基本數(shù)據(jù)、一些應(yīng)用可以讀取基本數(shù)據(jù)并創(chuàng)建繼承的列族、一些應(yīng)用則只允許瀏覽數(shù)據(jù)（甚至可能因?yàn)殡[私的原因不能瀏覽所有數(shù)據(jù)）。

時(shí)間戳

在Bigtable中，表的每一個(gè)數(shù)據(jù)項(xiàng)都可以包含同一份數(shù)據(jù)的不同版本；不同版本的數(shù)據(jù)通過時(shí)間戳來索引。Bigtable時(shí)間戳的類型是64位整型。Bigtable可以給時(shí)間戳賦值，用來表示精確到毫秒的“實(shí)時(shí)”時(shí)間；用戶程序也可以給時(shí)間戳賦值。如果應(yīng)用程序需要避免數(shù)據(jù)版本沖突，那么它必須自己生成具有唯一性的時(shí)間戳。數(shù)據(jù)項(xiàng)中，不同版本的數(shù)據(jù)按照時(shí)間戳倒序排序，即最新的數(shù)據(jù)排在最前面。

為了減輕多個(gè)版本數(shù)據(jù)的管理負(fù)擔(dān)，我們對(duì)每一個(gè)列族配有兩個(gè)設(shè)置參數(shù)，Bigtable通過這兩個(gè)參數(shù)可以對(duì)廢棄版本的數(shù)據(jù)自動(dòng)進(jìn)行垃圾收集。用戶可以指定只保存最后n個(gè)版本的數(shù)據(jù)，或者只保存“足夠新”的版本的數(shù)據(jù)（比如，只保存最近7天的內(nèi)容寫入的數(shù)據(jù)）。

在Webtable的舉例里，contents:列存儲(chǔ)的時(shí)間戳信息是網(wǎng)絡(luò)爬蟲抓取一個(gè)頁面的時(shí)間。上面提及的垃圾收集機(jī)制可以讓我們只保留最近三個(gè)版本的網(wǎng)頁數(shù)據(jù)。

#p#

3 API

Bigtable提供了建立和刪除表以及列族的API函數(shù)。Bigtable還提供了修改集群、表和列族的元數(shù)據(jù)的API，比如修改訪問權(quán)限。

// Open the table  
Table *T = OpenOrDie(“/bigtable/web/webtable”);  
// Write a new anchor and delete an old anchor  
RowMutation r1(T, “com.cnn.www”);  
r1.Set(“anchor:www.c-span.org”, “CNN”);  
r1.Delete(“anchor:www.abc.com”);  
Operation op;  
Apply(&op, &r1);  
Figure 2: Writing to Bigtable. 

客戶程序可以對(duì)Bigtable進(jìn)行如下的操作：寫入或者刪除Bigtable中的值、從每個(gè)行中查找值、或者遍歷表中的一個(gè)數(shù)據(jù)子集。圖2中的Ｃ++代碼使用RowMutation抽象對(duì)象進(jìn)行了一系列的更新操作。（為了保持示例代碼的簡潔，我們忽略了一些細(xì)節(jié)相關(guān)代碼）。調(diào)用Apply函數(shù)對(duì)Ｗebtable進(jìn)行了一個(gè)原子修改操作：它為www.cnn.com增加了一個(gè)錨點(diǎn)，同時(shí)刪除了另外一個(gè)錨點(diǎn)。

Scanner scanner(T);  
ScanStream *stream;  
stream = scanner.FetchColumnFamily(“anchor”);  
stream->SetReturnAllVersions();  
scanner.Lookup(“com.cnn.www”);  
for (; !stream->Done(); stream->Next()) {  
printf(“%s %s %lld %s\n”,  
scanner.RowName(),  
stream->ColumnName(),  
stream->MicroTimestamp(),  
stream->Value());  
}  
Figure 3: Reading from Bigtable. 

圖3中的C++代碼使用Scanner抽象對(duì)象遍歷一個(gè)行內(nèi)的所有錨點(diǎn)?？蛻舫绦蚩梢员闅v多個(gè)列族，有幾種方法可以對(duì)掃描輸出的行、列和時(shí)間戳進(jìn)行 限制。例如，我們可以限制上面的掃描，讓它只輸出那些匹配正則表達(dá)式*.cnn.com的錨點(diǎn)，或者那些時(shí)間戳在當(dāng)前時(shí)間前10天的錨點(diǎn)。

Bigtable還支持一些其它的特性，利用這些特性，用戶可以對(duì)數(shù)據(jù)進(jìn)行更復(fù)雜的處理。首先，Bigtable支持單行上的事務(wù)處理，利用這個(gè)功 能，用戶可以對(duì)存儲(chǔ)在一個(gè)行關(guān)鍵字下的數(shù)據(jù)進(jìn)行原子性的讀-更新-寫操作。雖然Bigtable提供了一個(gè)允許用戶跨行批量寫入數(shù)據(jù)的接口，但 是，Bigtable目前還不支持通用的跨行事務(wù)處理。其次，Bigtable允許把數(shù)據(jù)項(xiàng)用做整數(shù)計(jì)數(shù)器。最后，Bigtable允許用戶在服務(wù)器的地 址空間內(nèi)執(zhí)行腳本程序。腳本程序使用Google開發(fā)的Sawzall【28】數(shù)據(jù)處理語言。雖然目前我們基于的Sawzall語言的API函數(shù)還不允許 客戶的腳本程序?qū)懭霐?shù)據(jù)到Bigtable，但是它允許多種形式的數(shù)據(jù)轉(zhuǎn)換、基于任意表達(dá)式的數(shù)據(jù)過濾、以及使用多種操作符的進(jìn)行數(shù)據(jù)匯總。

Bigtable可以和MapReduce【12】一起使用，MapReduce是Google開發(fā)的大規(guī)模并行計(jì)算框架。我們已經(jīng)開發(fā)了一些 Wrapper類，通過使用這些Wrapper類，Bigtable可以作為MapReduce框架的輸入和輸出。

4 BigTable構(gòu)件

Bigtable是建立在其它的幾個(gè)Google基礎(chǔ)構(gòu)件上的。BigTable使用Google的分布式文件系統(tǒng)(GFS)【17】存儲(chǔ)日志 文件和數(shù)據(jù)文件。BigTable集群通常運(yùn)行在一個(gè)共享的機(jī)器池中，池中的機(jī)器還會(huì)運(yùn)行其它的各種各樣的分布式應(yīng)用程序，BigTable的進(jìn)程經(jīng)常要 和其它應(yīng)用的進(jìn)程共享機(jī)器。BigTable依賴集群管理系統(tǒng)來調(diào)度任務(wù)、管理共享的機(jī)器上的資源、處理機(jī)器的故障、以及監(jiān)視機(jī)器的狀態(tài)。

BigTable內(nèi)部存儲(chǔ)數(shù)據(jù)的文件是Google SSTable格式的。SSTable是一個(gè)持久化的、排序的、不可更改的Map結(jié)構(gòu)，而Map是一個(gè)key-value映射的數(shù)據(jù)結(jié)構(gòu)，key和 value的值都是任意的Byte串。可以對(duì)SSTable進(jìn)行如下的操作：查詢與一個(gè)key值相關(guān)的value，或者遍歷某個(gè)key值范圍內(nèi)的所有的 key-value對(duì)。從內(nèi)部看，SSTable是一系列的數(shù)據(jù)塊（通常每個(gè)塊的大小是64KB，這個(gè)大小是可以配置的）。SSTable使用塊索引（通 常存儲(chǔ)在SSTable的最后）來定位數(shù)據(jù)塊；在打開SSTable的時(shí)候，索引被加載到內(nèi)存。每次查找都可以通過一次磁盤搜索完成：首先使用二分查找法 在內(nèi)存中的索引里找到數(shù)據(jù)塊的位置，然后再從硬盤讀取相應(yīng)的數(shù)據(jù)塊。也可以選擇把整個(gè)SSTable都放在內(nèi)存中，這樣就不必訪問硬盤了。

BigTable還依賴一個(gè)高可用的、序列化的分布式鎖服務(wù)組件，叫做Chubby【8】。 一個(gè)Chubby服務(wù)包括了5個(gè)活動(dòng)的副本，其中的一個(gè)副本被選為Master，并且 處理請(qǐng)求。只有在大多數(shù)副本都是正常運(yùn)行的，并且彼此之間能夠互相通信的情況下，Chubby服務(wù)才是可用的。當(dāng)有副本失效的時(shí)候，Chubby使用 Paxos算法【9,23】來保證副本的一致性。Chubby提供了一個(gè)名字空間，里面包括了目錄和小文件。每個(gè)目錄或者文件可以當(dāng)成一個(gè)鎖，讀寫文件的 操作都是原子的。Chubby客戶程序庫提供對(duì)Chubby文件的一致性緩存。每個(gè)Chubby客戶程序都維護(hù)一個(gè)與Chubby服務(wù)的會(huì)話。如果客戶程 序不能在租約到期的時(shí)間內(nèi)重新簽訂會(huì)話的租約，這個(gè)會(huì)話就過期失效了(alex 注：又用到了lease。 原文是：A client’s session expires if it is unable to renew its session lease within the lease expiration time.)。當(dāng)一個(gè)會(huì)話失效時(shí)，它擁有的鎖和打開的文 件句柄都失效了。Chubby客戶程序可以在文件和目錄上注冊(cè)回調(diào)函數(shù)，當(dāng)文件或目錄改變、或者會(huì)話過期時(shí)，回調(diào)函數(shù)會(huì)通知客戶程序。

Bigtable使用Chubby完成以下的幾個(gè)任務(wù)：確保在任何給定的時(shí)間內(nèi)最多只有一個(gè)活動(dòng)的Master副本；存儲(chǔ)BigTable數(shù)據(jù) 的自引導(dǎo)指令的位置（參考5.1節(jié)）；查找Tablet服務(wù)器，以及在Tablet服務(wù)器失效時(shí)進(jìn)行善后（5.2節(jié)）；存儲(chǔ)BigTable的模式信息 （每張表的列族信息）；以及存儲(chǔ)訪問控制列表。如果Chubby長時(shí)間無法訪問，BigTable就會(huì)失效。最近我們?cè)谑褂?1個(gè)Chubby服務(wù)實(shí)例的 14個(gè)BigTable集群上測(cè)量了這個(gè)影響。由于Chubby不可用而導(dǎo)致BigTable中的部分?jǐn)?shù)據(jù)不能訪問的平均比率是0.0047% （Chubby不能訪問的原因可能是Chubby本身失效或者網(wǎng)絡(luò)問題）。單個(gè)集群里，受Chubby失效影響最大的百分比是0.0326%(James注,由于Chubby的可用性而受到影響的最大比例是0.0326%)（alex注：有點(diǎn)莫名其妙，原文是： The percentage for the single cluster that was most affected by Chubby unavailability was 0.0326%.）。

#p#

5 介紹

Bigtable包括了三個(gè)主要的組件：鏈接到客戶程序中的庫、一個(gè)Master服務(wù)器和多個(gè)Tablet服務(wù)器。針對(duì)系統(tǒng)工作負(fù)載的變化情 況，BigTable可以動(dòng)態(tài)的向集群中添加（或者刪除）Tablet服務(wù)器。

Master服務(wù)器主要負(fù)責(zé)以下工作：為Tablet服務(wù)器分配Tablets、檢 測(cè)新加入的或者過期失效的Table服務(wù)器、對(duì)Tablet服務(wù)器進(jìn)行負(fù)載均衡、以及對(duì)保存在GFS上的文件進(jìn)行垃圾收集。除此之外，它還處理對(duì)模式的相 關(guān)修改操作，例如建立表和列族。

每個(gè)Tablet服務(wù)器都管理一個(gè)Tablet的集合（通常每個(gè)服務(wù)器有大約數(shù)十個(gè)至上千個(gè)Tablet）。每個(gè)Tablet服務(wù)器負(fù)責(zé)處理它 所加載的Tablet的讀寫操作，以及在Tablets過大時(shí)，對(duì)其進(jìn)行分割。

和很多Single-Master類型的分布式存儲(chǔ)系統(tǒng)【17.21】類似，客戶端讀取的數(shù)據(jù)都不經(jīng)過Master服務(wù)器：客戶程序直接和 Tablet服務(wù)器通信進(jìn)行讀寫操作。由于BigTable的客戶程序不必通過Master服務(wù)器來獲取Tablet的位置信息，因此，大多數(shù)客戶程序甚 至完全不需要和Master服務(wù)器通信。在實(shí)際應(yīng)用中，Master服務(wù)器的負(fù)載是很輕的。

一個(gè)BigTable集群存儲(chǔ)了很多表，每個(gè)表包含了一個(gè)Tablet的集合，而每個(gè)Tablet包含了某個(gè)范圍內(nèi)的行的所有相關(guān)數(shù)據(jù)。初始狀 態(tài)下，一個(gè)表只有一個(gè)Tablet。隨著表中數(shù)據(jù)的增長，它被自動(dòng)分割成多個(gè)Tablet，缺省情況下，每個(gè)Tablet的尺寸大約是100MB到 200MB。

5.1 Tablet的位置

我們使用一個(gè)三層的、類似Ｂ+樹[10]的結(jié)構(gòu)存儲(chǔ)Tablet的位置信息(如圖4)。

第一層是一個(gè)存儲(chǔ)在Chubby中的文件，它包含了Root Tablet的位置信息。Root Tablet包含了一個(gè)特殊的METADATA表里所有的Tablet的位置信息。METADATA表的每個(gè)Tablet包含了一個(gè)用戶Tablet的集 合。Root Tablet實(shí)際上是METADATA表的第一個(gè)Tablet，只不過對(duì)它的處理比較特殊 — Root Tablet永遠(yuǎn)不會(huì)被分割 — 這就保證了Tablet的位置信息存儲(chǔ)結(jié)構(gòu)不會(huì)超過三層。

在METADATA表里面，每個(gè)Tablet的位置信息都存放在一個(gè)行關(guān)鍵字下面，而這個(gè)行關(guān)鍵字是由Tablet所在的表的標(biāo)識(shí)符和Tablet 的最后一行編碼而成的。METADATA的每一行都存儲(chǔ)了大約1KB的內(nèi)存數(shù)據(jù)。在一個(gè)大小適中的、容量限制為128MB的METADATA Tablet中，采用這種三層結(jié)構(gòu)的存儲(chǔ)模式，可以標(biāo)識(shí)2^34個(gè)Tablet的地址（如果每個(gè)Tablet存儲(chǔ)128MB數(shù)據(jù)，那么一共可以存儲(chǔ) 2^61字節(jié)數(shù)據(jù)）。

客戶程序使用的庫會(huì)緩存Tablet的位置信息。如果客戶程序沒有緩存某個(gè)Tablet的地址信息，或者發(fā)現(xiàn)它緩存的地址信息不正確，客戶程序就在 樹狀的存儲(chǔ)結(jié)構(gòu)中遞歸的查詢Tablet位置信息；如果客戶端緩存是空的，那么尋址算法需要通過三次網(wǎng)絡(luò)來回通信尋址，這其中包括了一次Chubby讀操 作；如果客戶端緩存的地址信息過期了，那么尋址算法可能需要最多６次網(wǎng)絡(luò)來回通信才能更新數(shù)據(jù)，因?yàn)橹挥性诰彺嬷袥]有查到數(shù)據(jù)的時(shí)候才能發(fā)現(xiàn)數(shù)據(jù)過期（alex注：其中的三次通信發(fā)現(xiàn)緩存過期，另外三次更新緩存數(shù)據(jù)）(假 設(shè)METADATA的Tablet沒有被頻繁的移動(dòng)）。盡管Tablet的地址信息是存放在內(nèi)存里的，對(duì)它的操作不必訪問GFS文件系統(tǒng)，但是，通常我們 會(huì)通過預(yù)取Tablet地址來進(jìn)一步的減少訪問的開銷：每次需要從METADATA表中讀取一個(gè)Tablet的元數(shù)據(jù)的時(shí)候，它都會(huì)多讀取幾個(gè) Tablet的元數(shù)據(jù)。

在METADATA表中還存儲(chǔ)了次級(jí)信息(alex 注：secondary information)，包括每個(gè)Tablet的事件日志（例如，什么時(shí)候一個(gè)服務(wù)器開始為該 Tablet提供服務(wù)）。這些信息有助于排查錯(cuò)誤和性能分析。

5.2 Tablet分配

在任何一個(gè)時(shí)刻，一個(gè)Tablet只能分配給一個(gè)Tablet服務(wù)器。Master服務(wù)器記錄了當(dāng)前有哪些活躍的Tablet服務(wù)器、哪些 Tablet分配給了哪些Tablet服務(wù)器、哪些Tablet還沒有被分配。當(dāng)一個(gè)Tablet還沒有被分配、并且剛好有一個(gè)Tablet服務(wù)器有足夠 的空閑空間裝載該Tablet時(shí)，Master服務(wù)器會(huì)給這個(gè)Tablet服務(wù)器發(fā)送一個(gè)裝載請(qǐng)求，把Tablet分配給這個(gè)服務(wù)器。

BigTable使用Chubby跟蹤記錄Tablet服務(wù)器的狀態(tài)。當(dāng)一個(gè)Tablet服務(wù)器啟動(dòng)時(shí)，它在Chubby的一個(gè)指定目錄下建立一個(gè) 有唯一性名字的文件，并且獲取該文件的獨(dú)占鎖。Master服務(wù)器實(shí)時(shí)監(jiān)控著這個(gè)目錄（服務(wù)器目錄），因此Master服務(wù)器能夠知道有新的Tablet 服務(wù)器加入了。如果Tablet服務(wù)器丟失了Chubby上的獨(dú)占鎖 — 比如由于網(wǎng)絡(luò)斷開導(dǎo)致Tablet服務(wù)器和Chubby的會(huì)話丟失 — 它就停止對(duì)Tablet提供服務(wù)。（Chubby提供了一種高效的機(jī)制，利用這種機(jī)制，Tablet服務(wù)器能夠在不增加網(wǎng)絡(luò)負(fù)擔(dān)的情況下知道它是否還持有 鎖）。只要文件還存在，Tablet服務(wù)器就會(huì)試圖重新獲得對(duì)該文件的獨(dú)占鎖；如果文件不存在了，那么Tablet服務(wù)器就不能再提供服務(wù)了，它會(huì)自行退 出（alex注：so it kills itself）。當(dāng)Tablet服務(wù)器終止時(shí)（比如，集群的管理系統(tǒng)將運(yùn)行該Tablet 服務(wù)器的主機(jī)從集群中移除），它會(huì)嘗試釋放它持有的文件鎖，這樣一來，Master服務(wù)器就能盡快把Tablet分配到其它的Tablet服務(wù)器。

Master服務(wù)器負(fù)責(zé)檢查一個(gè)Tablet服務(wù)器是否已經(jīng)不再為它的Tablet提供服務(wù)了，并且要盡快重新分配它加載的Tablet。 Master服務(wù)器通過輪詢Tablet服務(wù)器文件鎖的狀態(tài)來檢測(cè)何時(shí)Tablet服務(wù)器不再為Tablet提供服務(wù)。如果一個(gè)Tablet服務(wù)器報(bào)告它 丟失了文件鎖，或者M(jìn)aster服務(wù)器最近幾次嘗試和它通信都沒有得到響應(yīng)，Master服務(wù)器就會(huì)嘗試獲取該Tablet服務(wù)器文件的獨(dú)占鎖；如果 Master服務(wù)器成功獲取了獨(dú)占鎖，那么就說明Chubby是正常運(yùn)行的，而Tablet服務(wù)器要么是宕機(jī)了、要么是不能和Chubby通信了，因 此，Master服務(wù)器就刪除該Tablet服務(wù)器在Chubby上的服務(wù)器文件以確保它不再給Tablet提供服務(wù)。一旦Tablet服務(wù)器在 Chubby上的服務(wù)器文件被刪除了，Master服務(wù)器就把之前分配給它的所有的Tablet放入未分配的Tablet集合中。為了確保 Bigtable集群在Master服務(wù)器和Chubby之間網(wǎng)絡(luò)出現(xiàn)故障的時(shí)候仍然可以使用，Master服務(wù)器在它的Chubby會(huì)話過期后主動(dòng)退 出。但是不管怎樣，如同我們前面所描述的，Master服務(wù)器的故障不會(huì)改變現(xiàn)有Tablet在Tablet服務(wù)器上的分配狀態(tài)。

當(dāng)集群管理系統(tǒng)啟動(dòng)了一個(gè)Master服務(wù)器之后，Master服務(wù)器首先要了解當(dāng)前Tablet的分配狀態(tài)，之后才能夠修改分配狀態(tài)。 Master服務(wù)器在啟動(dòng)的時(shí)候執(zhí)行以下步驟：（1）Master服務(wù)器從Chubby獲取一個(gè)唯一的Master鎖，用來阻止創(chuàng)建其它的Master服 務(wù)器實(shí)例；（2）Master服務(wù)器掃描Chubby的服務(wù)器文件鎖存儲(chǔ)目錄，獲取當(dāng)前正在運(yùn)行的服務(wù)器列表；（3）Master服務(wù)器和所有的正在運(yùn)行 的Tablet表服務(wù)器通信，獲取每個(gè)Tablet服務(wù)器上Tablet的分配信息；（4）Master服務(wù)器掃描METADATA表獲取所有的 Tablet的集合。在掃描的過程中，當(dāng)Master服務(wù)器發(fā)現(xiàn)了一個(gè)還沒有分配的Tablet，Master服務(wù)器就將這個(gè)Tablet加入未分配的 Tablet集合等待合適的時(shí)機(jī)分配。

可能會(huì)遇到一種復(fù)雜的情況：在METADATA表的Tablet還沒有被分配之前是不能夠掃描它的。因此，在開始掃描之前（步驟4），如果在第三步 的掃描過程中發(fā)現(xiàn)Root Tablet還沒有分配，Master服務(wù)器就把Root Tablet加入到未分配的Tablet集合。這個(gè)附加操作確保了Root Tablet會(huì)被分配。由于Root Tablet包括了所有METADATA的Tablet的名字，因此Master服務(wù)器掃描完Root Tablet以后，就得到了所有的METADATA表的Tablet的名字了。

保存現(xiàn)有Tablet的集合只有在以下事件發(fā)生時(shí)才會(huì)改變：建立了一個(gè)新表或者刪除了一個(gè)舊表、兩個(gè)Tablet被合并了、或者一個(gè)Tablet被 分割成兩個(gè)小的Tablet。Master服務(wù)器可以跟蹤記錄所有這些事件，因?yàn)槌俗詈笠粋€(gè)事件外的兩個(gè)事件都是由它啟動(dòng)的。Tablet分割事件需要 特殊處理，因?yàn)樗怯蒚ablet服務(wù)器啟動(dòng)。在分割操作完成之后，Tablet服務(wù)器通過在METADATA表中記錄新的Tablet的信息來提交這個(gè) 操作；當(dāng)分割操作提交之后，Tablet服務(wù)器會(huì)通知Master服務(wù)器。如果分割操作已提交的信息沒有通知到Master服務(wù)器（可能兩個(gè)服務(wù)器中有一 個(gè)宕機(jī)了），Master服務(wù)器在要求Tablet服務(wù)器裝載已經(jīng)被分割的子表的時(shí)候會(huì)發(fā)現(xiàn)一個(gè)新的Tablet。通過對(duì)比METADATA表中 Tablet的信息，Tablet服務(wù)器會(huì)發(fā)現(xiàn)Master服務(wù)器要求其裝載的Tablet并不完整，因此，Tablet服務(wù)器會(huì)重新向Master服務(wù) 器發(fā)送通知信息。

5.3 Tablet服務(wù)

如圖5所示，Tablet的持久化狀態(tài)信息保存在GFS上。更新操作提交到REDO日志中（alex注：Updates are committed to a commit log that stores redo records）。在這些更新操作中，最近提交的那些存放在一個(gè)排序的緩存中，我們稱這個(gè)緩存為 memtable；較早的更新存放在一系列SSTable中。為了恢復(fù)一個(gè)Tablet，Tablet服務(wù)器首先從METADATA表中讀取它的元數(shù)據(jù)。 Tablet的元數(shù)據(jù)包含了組成這個(gè)Tablet的SSTable的列表，以及一系列的Redo Point（alex注：a set of redo points），這 些Redo Point指向可能含有該Tablet數(shù)據(jù)的已提交的日志記錄。Tablet服務(wù)器把SSTable的索引讀進(jìn)內(nèi)存，之后通過重復(fù)Redo Point之后提交的更新來重建memtable。

當(dāng)對(duì)Tablet服務(wù)器進(jìn)行寫操作時(shí)，Tablet服務(wù)器首先要檢查這個(gè)操作格式是否正確、操作發(fā)起者是否有執(zhí)行這個(gè)操作的權(quán)限。權(quán)限驗(yàn)證的方法是 通過從一個(gè)Chubby文件里讀取出來的具有寫權(quán)限的操作者列表來進(jìn)行驗(yàn)證（這個(gè)文件幾乎一定會(huì)存放在Chubby客戶緩存里）。成功的修改操作會(huì)記錄在 提交日志里?？梢圆捎门刻峤环绞剑╝lex注：group commit）來提高包含大量小的修改操作的應(yīng)用程序的吞吐量【13，16】。當(dāng)一個(gè)寫操作提交后，寫的內(nèi)容插入到 memtable里面。

當(dāng)對(duì)Tablet服務(wù)器進(jìn)行讀操作時(shí)，Tablet服務(wù)器會(huì)作類似的完整性和權(quán)限檢查。一個(gè)有效的讀操作在一個(gè)由一系列SSTable和 memtable合并的視圖里執(zhí)行。由于SSTable和memtable是按字典排序的數(shù)據(jù)結(jié)構(gòu)，因此可以高效生成合并視圖。

當(dāng)進(jìn)行Tablet的合并和分割時(shí)，正在進(jìn)行的讀寫操作能夠繼續(xù)進(jìn)行。

5.4 Compactions

(alex注：這個(gè)詞挺簡單，但是在這節(jié)里面挺難翻譯的。應(yīng) 該是空間縮減的意思，但是似乎又不能完全概括它在上下文中的意思，干脆，不翻譯了)

隨著寫操作的執(zhí)行，memtable的大小不斷增加。當(dāng)memtable的尺寸到達(dá)一個(gè)門限值的時(shí)候，這個(gè)memtable就會(huì)被凍結(jié)，然后創(chuàng)建一 個(gè)新的memtable；被凍結(jié)住memtable會(huì)被轉(zhuǎn)換成SSTable，然后寫入GFS（alex注：我們稱這種Compaction行為為Minor Compaction）。Minor Compaction過程有兩個(gè)目的：shrink(alex注：shrink是數(shù)據(jù)庫用語，表示空間收縮)Tablet 服務(wù)器使用的內(nèi)存，以及在服務(wù)器災(zāi)難恢復(fù)過程中，減少必須從提交日志里讀取的數(shù)據(jù)量。在Compaction過程中，正在進(jìn)行的讀寫操作仍能繼續(xù)。

每一次Minor Compaction都會(huì)創(chuàng)建一個(gè)新的SSTable。如果Minor Compaction過程不停滯的持續(xù)進(jìn)行下去，讀操作可能需要合并來自多個(gè)SSTable的更新；否則，我們通過定期在后臺(tái)執(zhí)行Merging Compaction過程合并文件，限制這類文件的數(shù)量。Merging Compaction過程讀取一些SSTable和memtable的內(nèi)容，合并成一個(gè)新的SSTable。只要Merging Compaction過程完成了，輸入的這些SSTable和memtable就可以刪除了。

合并所有的SSTable并生成一個(gè)新的SSTable的Merging Compaction過程叫作Major Compaction。由非Major Compaction產(chǎn)生的SSTable可能含有特殊的刪除條目，這些刪除條目能夠隱藏在舊的、但是依然有效的SSTable中已經(jīng)刪除的數(shù)據(jù)（alex注：令人費(fèi)解啊，原文是SSTables produced by non-major compactions can contain special deletion entries that suppress deleted data in older SSTables that are still live）。而Major Compaction過程生成的SSTable不包含已經(jīng)刪除的信息或數(shù)據(jù)。Bigtable循環(huán)掃描它所有的Tablet，并且定期對(duì)它們執(zhí)行 Major Compaction。Major Compaction機(jī)制允許Bigtable回收已經(jīng)刪除的數(shù)據(jù)占有的資源，并且確保BigTable能及時(shí)清除已經(jīng)刪除的數(shù)據(jù)（alex注：實(shí)際是回收資源。數(shù)據(jù)刪除后，它占有的空間并不能馬上重復(fù)利用；只有空間 回收后才能重復(fù)使用），這對(duì)存放敏感數(shù)據(jù)的服務(wù)是非常重要。

6 優(yōu)化

上一章我們描述了Bigtable的實(shí)現(xiàn)，我們還需要很多優(yōu)化工作才能使Bigtable到達(dá)用戶要求的高性能、高可用性和高可靠性。本章描述 了Bigtable實(shí)現(xiàn)的其它部分，為了更好的強(qiáng)調(diào)這些優(yōu)化工作，我們將深入細(xì)節(jié)。

局部性群組

客戶程序可以將多個(gè)列族組合成一個(gè)局部性群族。對(duì)Tablet中的每個(gè)局部性群組都會(huì)生成一個(gè)單獨(dú)的SSTable。將通常不會(huì)一起訪問的列族 分割成不同的局部性群組可以提高讀取操作的效率。例如，在Webtable表中，網(wǎng)頁的元數(shù)據(jù)（比如語言和Checksum）可以在一個(gè)局部性群組中，網(wǎng) 頁的內(nèi)容可以在另外一個(gè)群組：當(dāng)一個(gè)應(yīng)用程序要讀取網(wǎng)頁的元數(shù)據(jù)的時(shí)候，它沒有必要去讀取所有的頁面內(nèi)容。

此外，可以以局部性群組為單位設(shè)定一些有用的調(diào)試參數(shù)。比如，可以把一個(gè)局部性群組設(shè)定為全部存儲(chǔ)在內(nèi)存中。Tablet服務(wù)器依照惰性加載的 策略將設(shè)定為放入內(nèi)存的局部性群組的SSTable裝載進(jìn)內(nèi)存。加載完成之后，訪問屬于該局部性群組的列族的時(shí)候就不必讀取硬盤了。這個(gè)特性對(duì)于需要頻繁 訪問的小塊數(shù)據(jù)特別有用：在Bigtable內(nèi)部，我們利用這個(gè)特性提高M(jìn)ETADATA表中具有位置相關(guān)性的列族的訪問速度。

壓縮

客戶程序可以控制一個(gè)局部性群組的SSTable是否需要壓縮；如果需要壓縮，那么以什么格式來壓縮。每個(gè)SSTable的塊（塊的大小由局部性群 組的優(yōu)化參數(shù)指定）都使用用戶指定的壓縮格式來壓縮。雖然分塊壓縮浪費(fèi)了少量空間（alex注：相比于對(duì)整個(gè)SSTable進(jìn)行壓縮，分塊壓縮壓縮率較低），但是，我們?cè)谥蛔x取SSTable 的一小部分?jǐn)?shù)據(jù)的時(shí)候就不必解壓整個(gè)文件了。很多客戶程序使用了“兩遍”的、可定制的壓縮方式。第一遍采用Bentley and McIlroy’s方式[6]，這種方式在一個(gè)很大的掃描窗口里對(duì)常見的長字符串進(jìn)行壓縮；第二遍是采用快速壓縮算法，即在一個(gè)16KB的小掃描窗口中尋 找重復(fù)數(shù)據(jù)。兩個(gè)壓縮的算法都很快，在現(xiàn)在的機(jī)器上，壓縮的速率達(dá)到100-200MB/s，解壓的速率達(dá)到400-1000MB/s。

雖然我們?cè)谶x擇壓縮算法的時(shí)候重點(diǎn)考慮的是速度而不是壓縮的空間，但是這種兩遍的壓縮方式在空間壓縮率上的表現(xiàn)也是令人驚嘆。比如，在 Webtable的例子里，我們使用這種壓縮方式來存儲(chǔ)網(wǎng)頁內(nèi)容。在一次測(cè)試中，我們?cè)谝粋€(gè)壓縮的局部性群組中存儲(chǔ)了大量的網(wǎng)頁。針對(duì)實(shí)驗(yàn)的目的，我們沒 有存儲(chǔ)每個(gè)文檔所有版本的數(shù)據(jù)，我們僅僅存儲(chǔ)了一個(gè)版本的數(shù)據(jù)。該模式的空間壓縮比達(dá)到了10:1。這比傳統(tǒng)的Gzip在壓縮HTML頁面時(shí)3:1或者 4:1的空間壓縮比好的多；“兩遍”的壓縮模式如此高效的原因是由于Webtable的行的存放方式：從同一個(gè)主機(jī)獲取的頁面都存在臨近的地方。利用這個(gè) 特性，Bentley-McIlroy算法可以從來自同一個(gè)主機(jī)的頁面里找到大量的重復(fù)內(nèi)容。不僅僅是Webtable，其它的很多應(yīng)用程序也通過選擇合 適的行名來將相似的數(shù)據(jù)聚簇在一起，以獲取較高的壓縮率。當(dāng)我們?cè)贐igtable中存儲(chǔ)同一份數(shù)據(jù)的多個(gè)版本的時(shí)候，壓縮效率會(huì)更高。

通過緩存提高讀操作的性能

為了提高讀操作的性能，Tablet服務(wù)器使用二級(jí)緩存的策略。掃描緩存是第一級(jí)緩存，主要緩存Tablet服務(wù)器通過SSTable接口獲取的 Key-Value對(duì)；Block緩 存是二級(jí)緩存，緩存的是從GFS讀取的SSTable的Block。對(duì)于經(jīng)常要重復(fù)讀取相同數(shù)據(jù)的應(yīng)用程序來說，掃描緩存非常有效；對(duì)于經(jīng)常要讀取剛剛讀 過的數(shù)據(jù)附近的數(shù)據(jù)的應(yīng)用程序來說，Block緩存更有用（例如，順序讀，或者在一個(gè)熱點(diǎn)的行的局部性群組中隨機(jī)讀取不同的列)。

Bloom過濾器

(alex注：Bloom，又叫布隆過濾器，什么意思？請(qǐng)參 考Google黑板報(bào)http://googlechinablog.com/2007/07/bloom-filter.html請(qǐng)務(wù)必先認(rèn)真閱讀)

如5.3節(jié)所述，一個(gè)讀操作必須讀取構(gòu)成Tablet狀態(tài)的所有SSTable的數(shù)據(jù)。如果這些SSTable不在內(nèi)存中，那么就需要多次訪問硬 盤。我們通過允許客戶程序?qū)μ囟ň植啃匀航M的SSTable指定Bloom過濾器【7】，來減少硬盤訪問的次數(shù)。我們可以使用Bloom過濾器查詢一個(gè) SSTable是否包含了特定行和列的數(shù)據(jù)。對(duì)于某些特定應(yīng)用程序，我們只付出了少量的、用于存儲(chǔ)Bloom過濾器的內(nèi)存的代價(jià)，就換來了讀操作顯著減少 的磁盤訪問的次數(shù)。使用Bloom過濾器也隱式的達(dá)到了當(dāng)應(yīng)用程序訪問不存在的行或列時(shí)，大多數(shù)時(shí)候我們都不需要訪問硬盤的目的。

Commit日志的實(shí)現(xiàn)

如果我們把對(duì)每個(gè)Tablet的操作的Commit日志都存在一個(gè)單獨(dú)的文件的話，那么就會(huì)產(chǎn)生大量的文件，并且這些文件會(huì)并行的寫入GFS。根據(jù) GFS服務(wù)器底層文件系統(tǒng)實(shí)現(xiàn)的方案，要把這些文件寫入不同的磁盤日志文件時(shí)(alex注：different physical log files)，會(huì)有大量的磁盤Seek操作。另外，由 于批量提交(alex注：group commit)中 操作的數(shù)目一般比較少，因此，對(duì)每個(gè)Tablet設(shè)置單獨(dú)的日志文件也會(huì)給批量提交本應(yīng)具有的優(yōu)化效果帶來很大的負(fù)面影響。為了避免這些問題，我們?cè)O(shè)置每 個(gè)Tablet服務(wù)器一個(gè)Commit日志文件，把修改操作的日志以追加方式寫入同一個(gè)日志文件，因此一個(gè)實(shí)際的日志文件中混合了對(duì)多個(gè)Tablet修改 的日志記錄。

使用單個(gè)日志顯著提高了普通操作的性能，但是將恢復(fù)的工作復(fù)雜化了。當(dāng)一個(gè)Tablet服務(wù)器宕機(jī)時(shí)，它加載的Tablet將會(huì)被移到很多其它的 Tablet服務(wù)器上：每個(gè)Tablet服務(wù)器都裝載很少的幾個(gè)原來的服務(wù)器的Tablet。當(dāng)恢復(fù)一個(gè)Tablet的狀態(tài)的時(shí)候，新的Tablet服務(wù) 器要從原來的Tablet服務(wù)器寫的日志中提取修改操作的信息，并重新執(zhí)行。然而，這些Tablet修改操作的日志記錄都混合在同一個(gè)日志文件中的。一種 方法新的Tablet服務(wù)器讀取完整的Commit日志文件，然后只重復(fù)執(zhí)行它需要恢復(fù)的Tablet的相關(guān)修改操作。使用這種方法，假如有100臺(tái) Tablet服務(wù)器，每臺(tái)都加載了失效的Tablet服務(wù)器上的一個(gè)Tablet，那么，這個(gè)日志文件就要被讀取100次（每個(gè)服務(wù)器讀取一次）。

為了避免多次讀取日志文件，我們首先把日志按照關(guān)鍵字（table，row name，log sequence number）排序。排序之后，對(duì)同一個(gè)Tablet的修改操作的日志記錄就連續(xù)存放在了一起，因此，我們只要一次磁盤Seek操作、之后順序讀取就可以 了。為了并行排序，我們先將日志分割成64MB的段，之后在不同的Tablet服務(wù)器對(duì)段進(jìn)行并行排序。這個(gè)排序工作由Master服務(wù)器來協(xié)同處理，并 且在一個(gè)Tablet服務(wù)器表明自己需要從Commit日志文件恢復(fù)Tablet時(shí)開始執(zhí)行。

在向GFS中寫Commit日志的時(shí)候可能會(huì)引起系統(tǒng)顛簸，原因是多種多樣的（比如，寫操作正在進(jìn)行的時(shí)候，一個(gè)GFS服務(wù)器宕機(jī)了；或者連接三個(gè) GFS副本所在的服務(wù)器的網(wǎng)絡(luò)擁塞或者過載了）。為了確保在GFS負(fù)載高峰時(shí)修改操作還能順利進(jìn)行，每個(gè)Tablet服務(wù)器實(shí)際上有兩個(gè)日志寫入線程，每 個(gè)線程都寫自己的日志文件，并且在任何時(shí)刻，只有一個(gè)線程是工作的。如果一個(gè)線程的在寫入的時(shí)候效率很低，Tablet服務(wù)器就切換到另外一個(gè)線程，修改 操作的日志記錄就寫入到這個(gè)線程對(duì)應(yīng)的日志文件中。每個(gè)日志記錄都有一個(gè)序列號(hào)，因此，在恢復(fù)的時(shí)候，Tablet服務(wù)器能夠檢測(cè)出并忽略掉那些由于線程 切換而導(dǎo)致的重復(fù)的記錄。

Tablet恢復(fù)提速

當(dāng)Master服務(wù)器將一個(gè)Tablet從一個(gè)Tablet服務(wù)器移到另外一個(gè)Tablet服務(wù)器時(shí)，源Tablet服務(wù)器會(huì)對(duì)這個(gè) Tablet做一次Minor Compaction。這個(gè)Compaction操作減少了Tablet服務(wù)器的日志文件中沒有歸并的記錄，從而減少了恢復(fù)的時(shí)間。Compaction 完成之后，該服務(wù)器就停止為該Tablet提供服務(wù)。在卸載Tablet之前，源Tablet服務(wù)器還會(huì)再做一次（通常會(huì)很快）Minor Compaction，以消除前面在一次壓縮過程中又產(chǎn)生的未歸并的記錄。第二次Minor Compaction完成以后，Tablet就可以被裝載到新的Tablet服務(wù)器上了，并且不需要從日志中進(jìn)行恢復(fù)。

利用不變性

我們?cè)谑褂肂igtable時(shí)，除了SSTable緩存之外的其它部分產(chǎn)生的SSTable都是不變的，我們可以利用這一點(diǎn)對(duì)系統(tǒng)進(jìn)行簡化。例如， 當(dāng)從SSTable讀取數(shù)據(jù)的時(shí)候，我們不必對(duì)文件系統(tǒng)訪問操作進(jìn)行同步。這樣一來，就可以非常高效的實(shí)現(xiàn)對(duì)行的并行操作。memtable是唯一一個(gè)能 被讀和寫操作同時(shí)訪問的可變數(shù)據(jù)結(jié)構(gòu)。為了減少在讀操作時(shí)的競(jìng)爭(zhēng)，我們對(duì)內(nèi)存表采用COW(Copy-on-write)機(jī)制，這樣就允許讀寫操作并行執(zhí) 行。

因?yàn)镾STable是不變的，因此，我們可以把永久刪除被標(biāo)記為“刪除”的數(shù)據(jù)的問題，轉(zhuǎn)換成對(duì)廢棄的SSTable進(jìn)行垃圾收集的問題了。每個(gè) Tablet的SSTable都在METADATA表中注冊(cè)了。Master服務(wù)器采用“標(biāo)記-刪除”的垃圾回收方式刪除SSTable集合中廢棄的 SSTable【25】，METADATA表則保存了Root SSTable的集合。

最后，SSTable的不變性使得分割Tablet的操作非?？旖?。我們不必為每個(gè)分割出來的Tablet建立新的SSTable集合，而是共享原 來的Tablet的SSTable集合。

#p#

7 性能評(píng)估

為了測(cè)試Bigtable的性能和可擴(kuò)展性，我們建立了一個(gè)包括N臺(tái)Tablet服務(wù)器的Bigtable集群，這里N是可變的。每臺(tái) Tablet服務(wù)器配置了1GB的內(nèi)存，數(shù)據(jù)寫入到一個(gè)包括1786臺(tái)機(jī)器、每臺(tái)機(jī)器有2個(gè)IDE硬盤的GFS集群上。我們使用N臺(tái)客戶機(jī)生成工作負(fù)載測(cè) 試Bigtable。（我們使用和Tablet服務(wù)器相同數(shù)目的客戶機(jī)以確?？蛻魴C(jī)不會(huì)成為瓶頸。） 每臺(tái)客戶機(jī)配置2GZ雙核Opteron處理器，配置了足以容納所有進(jìn)程工作數(shù)據(jù)集的物理內(nèi)存，以及一張Gigabit的以太網(wǎng)卡。這些機(jī)器都連入一個(gè)兩 層的、樹狀的交換網(wǎng)絡(luò)里，在根節(jié)點(diǎn)上的帶寬加起來有大約100-200Gbps。所有的機(jī)器采用相同的設(shè)備，因此，任何兩臺(tái)機(jī)器間網(wǎng)絡(luò)來回一次的時(shí)間都小 于1ms。

Tablet服務(wù)器、Master服務(wù)器、測(cè)試機(jī)、以及GFS服務(wù)器都運(yùn)行在同一組機(jī)器上。每臺(tái)機(jī)器都運(yùn)行一個(gè)GFS的服務(wù)器。其它的機(jī)器要么 運(yùn)行Tablet服務(wù)器、要么運(yùn)行客戶程序、要么運(yùn)行在測(cè)試過程中，使用這組機(jī)器的其它的任務(wù)啟動(dòng)的進(jìn)程。

R是測(cè)試過程中，Bigtable包含的不同的列關(guān)鍵字的數(shù)量。我們精心選擇R的值，保證每次基準(zhǔn)測(cè)試對(duì)每臺(tái)Tablet服務(wù)器讀/寫的數(shù)據(jù)量 都在1GB左右。

在序列寫的基準(zhǔn)測(cè)試中，我們使用的列關(guān)鍵字的范圍是0到R-1。這個(gè)范圍又被劃分為10N個(gè)大小相同的區(qū)間。核心調(diào)度程序把這些區(qū)間分配給N個(gè) 客戶端，分配方式是：只要客戶程序處理完上一個(gè)區(qū)間的數(shù)據(jù)，調(diào)度程序就把后續(xù)的、尚未處理的區(qū)間分配給它。這種動(dòng)態(tài)分配的方式有助于減少客戶機(jī)上同時(shí)運(yùn)行 的其它進(jìn)程對(duì)性能的影響。我們?cè)诿總€(gè)列關(guān)鍵字下寫入一個(gè)單獨(dú)的字符串。每個(gè)字符串都是隨機(jī)生成的、因此也沒有被壓縮（alex注：參考第6節(jié)的壓縮小節(jié)）。另外，不同列關(guān)鍵字下的字符串也是不同的，因此也就不存在跨行的壓縮。隨機(jī)寫入基準(zhǔn)測(cè)試采 用類似的方法，除了行關(guān)鍵字在寫入前先做Hash，Hash采用按R取模的方式，這樣就保證了在整個(gè)基準(zhǔn)測(cè)試持續(xù)的時(shí)間內(nèi)，寫入的工作負(fù)載均勻的分布在列 存儲(chǔ)空間內(nèi)。

序列讀的基準(zhǔn)測(cè)試生成列關(guān)鍵字的方式與序列寫相同，不同于序列寫在列關(guān)鍵字下寫入字符串的是，序列讀是讀取列關(guān)鍵字下的字符串（這些字符串由之 前序列寫基準(zhǔn)測(cè)試程序?qū)懭耄?。同樣的，隨機(jī)讀的基準(zhǔn)測(cè)試和隨機(jī)寫是類似的。

掃描基準(zhǔn)測(cè)試和序列讀類似，但是使用的是BigTable提供的、從一個(gè)列范圍內(nèi)掃描所有的value值的API。由于一次RPC調(diào)用就從一個(gè) Tablet服務(wù)器取回了大量的Value值，因此，使用掃描方式的基準(zhǔn)測(cè)試程序可以減少RPC調(diào)用的次數(shù)。

隨機(jī)讀（內(nèi)存）基準(zhǔn)測(cè)試和隨機(jī)讀類似，除了包含基準(zhǔn)測(cè)試數(shù)據(jù)的局部性群組被設(shè)置為“in-memory”，因此，讀操作直接從Tablet服務(wù) 器的內(nèi)存中讀取數(shù)據(jù)，不需要從GFS讀取數(shù)據(jù)。針對(duì)這個(gè)測(cè)試，我們把每臺(tái)Tablet服務(wù)器存儲(chǔ)的數(shù)據(jù)從1GB減少到100MB，這樣就可以把數(shù)據(jù)全部加載到Tablet服務(wù)器的內(nèi)存中了。

圖6中有兩個(gè)視圖，顯示了我們的基準(zhǔn)測(cè)試的性能；圖中的數(shù)據(jù)和曲線是讀/寫 1000-byte value值時(shí)取得的。圖中的表格顯示了每個(gè)Tablet服務(wù)器每秒鐘進(jìn)行的操作的次數(shù)；圖中的曲線顯示了每秒種所有的Tablet服務(wù)器上操作次數(shù)的總 和。

單個(gè)Tablet服務(wù)器的性能

我們首先分析下單個(gè)Tablet服務(wù)器的性能。隨機(jī)讀的性能比其它操作慢一個(gè)或多個(gè)數(shù)量級(jí)(或以上,James注此處做了小許調(diào)整)（alex注：by the order of magnitude or more） 。 每個(gè)隨機(jī)讀操作都要通過網(wǎng)絡(luò)從GFS傳輸64KB的SSTable到Tablet服務(wù)器，而我們只使用其中大小是1000 byte的一個(gè)value值。Tablet服務(wù)器每秒大約執(zhí)行1200次讀操作，也就是每秒大約從GFS讀取75MB的數(shù)據(jù)。這個(gè)傳輸帶寬足以占滿 Tablet服務(wù)器的CPU時(shí)間，因?yàn)槠渲邪司W(wǎng)絡(luò)協(xié)議棧的消耗、SSTable解析、以及BigTable代碼執(zhí)行；這個(gè)帶寬也足以占滿我們系統(tǒng)中網(wǎng) 絡(luò)的鏈接帶寬。大多數(shù)采用這種訪問模式BigTable應(yīng)用程序會(huì)減小Block的大小，通常會(huì)減到8KB。

內(nèi)存中的隨機(jī)讀操作速度快很多，原因是，所有1000-byte的讀操作都是從Tablet服務(wù)器的本地內(nèi)存中讀取數(shù)據(jù)，不需要從GFS讀取 64KB的Block。

隨機(jī)和序列寫操作的性能比隨機(jī)讀要好些，原因是每個(gè)Tablet服務(wù)器直接把寫入操作的內(nèi)容追加到一個(gè)Commit日志文件的尾部，并且采用批量提 交的方式，通過把數(shù)據(jù)以流的方式寫入到GFS來提高性能。隨機(jī)寫和序列寫在性能上沒有太大的差異，這兩種方式的寫操作實(shí)際上都是把操作內(nèi)容記錄到同一個(gè) Tablet服務(wù)器的Commit日志文件中。

序列讀的性能好于隨機(jī)讀，因?yàn)槊咳〕?4KB的SSTable的Block后，這些數(shù)據(jù)會(huì)緩存到Block緩存中，后續(xù)的64次讀操作直接從緩存讀 取數(shù)據(jù)。

掃描的性能更高，這是由于客戶程序每一次RPC調(diào)用都會(huì)返回大量的value的數(shù)據(jù)，所以，RPC調(diào)用的消耗基本抵消了。

性能提升

隨著我們將系統(tǒng)中的Tablet服務(wù)器從1臺(tái)增加到500臺(tái)，系統(tǒng)的整體吞吐量有了夢(mèng)幻般的增長，增長的倍率超過了100。比如，隨著Tablet 服務(wù)器的數(shù)量增加了500倍，內(nèi)存中的隨機(jī)讀操作的性能增加了300倍。之所以會(huì)有這樣的性能提升，主要是因?yàn)檫@個(gè)基準(zhǔn)測(cè)試的瓶頸是單臺(tái)Tablet服務(wù) 器的CPU。

盡管如此，性能的提升還不是線性的。在大多數(shù)的基準(zhǔn)測(cè)試中我們看到，當(dāng)Tablet服務(wù)器的數(shù)量從1臺(tái)增加到50臺(tái)時(shí)，每臺(tái)服務(wù)器的吞吐量會(huì)有一個(gè) 明顯的下降。這是由于多臺(tái)服務(wù)器間的負(fù)載不均衡造成的，大多數(shù)情況下是由于其它的程序搶占了CPU。 我們負(fù)載均衡的算法會(huì)盡量避免這種不均衡，但是基于兩個(gè)主要原因，這個(gè)算法并不能完美的工作：一個(gè)是盡量減少Tablet的移動(dòng)導(dǎo)致重新負(fù)載均衡能力受限 （如果Tablet被移動(dòng)了，那么在短時(shí)間內(nèi) — 一般是1秒內(nèi) — 這個(gè)Tablet是不可用的），另一個(gè)是我們的基準(zhǔn)測(cè)試程序產(chǎn)生的負(fù)載會(huì)有波動(dòng)（alex注：the load generated by our benchmarks shifts around as the benchmark progresses）。

隨機(jī)讀基準(zhǔn)測(cè)試的測(cè)試結(jié)果顯示，隨機(jī)讀的性能隨Tablet服務(wù)器數(shù)量增加的提升幅度最?。ㄕw吞吐量只提升了100倍，而服務(wù)器的數(shù)量卻增加了 500倍）。這是因?yàn)槊總€(gè)1000-byte的讀操作都會(huì)導(dǎo)致一個(gè)64KB大的Block在網(wǎng)絡(luò)上傳輸。這樣的網(wǎng)絡(luò)傳輸量消耗了我們網(wǎng)絡(luò)中各種共享的 1GB的鏈路，結(jié)果導(dǎo)致隨著我們?cè)黾臃?wù)器的數(shù)量，每臺(tái)服務(wù)器上的吞吐量急劇下降。

8 實(shí)際應(yīng)用

截止到2006年8月，Google內(nèi)部一共有388個(gè)非測(cè)試用的Bigtable集群運(yùn)行在各種各樣的服務(wù)器集群上，合計(jì)大約有24500個(gè) Tablet服務(wù)器。表1顯示了每個(gè)集群上Tablet服務(wù)器的大致分布情況。這些集群中，許多用于開發(fā)目的，因此會(huì)有一段時(shí)期比較空閑。通過觀察一個(gè)由 14個(gè)集群、8069個(gè)Tablet服務(wù)器組成的集群組，我們看到整體的吞吐量超過了每秒1200000次請(qǐng)求，發(fā)送到系統(tǒng)的RPC請(qǐng)求導(dǎo)致的網(wǎng)絡(luò)負(fù)載達(dá) 到了741MB/s，系統(tǒng)發(fā)出的RPC請(qǐng)求網(wǎng)絡(luò)負(fù)載大約是16GB/s。

表2提供了一些目前正在使用的表的相關(guān)數(shù)據(jù)。一些表存儲(chǔ)的是用戶相關(guān)的數(shù)據(jù)，另外一些存儲(chǔ)的則是用于批處理的數(shù)據(jù)；這些表在總的大小、 每個(gè)數(shù)據(jù)項(xiàng)的平均大小、從內(nèi)存中讀取的數(shù)據(jù)的比例、表的Schema的復(fù)雜程度上都有很大的差別。本節(jié)的其余部分，我們將主要描述三個(gè)產(chǎn)品研發(fā)團(tuán)隊(duì)如何使 用Bigtable的。

8.1 Google Analytics

Google Analytics是用來幫助Web站點(diǎn)的管理員分析他們網(wǎng)站的流量模式的服務(wù)。它提供了整體狀況的統(tǒng)計(jì)數(shù)據(jù)，比如每天的獨(dú)立訪問的用戶數(shù)量、每天每個(gè) URL的瀏覽次數(shù)；它還提供了用戶使用網(wǎng)站的行為報(bào)告，比如根據(jù)用戶之前訪問的某些頁面，統(tǒng)計(jì)出幾成的用戶購買了商品。

為了使用這個(gè)服務(wù)，Web站點(diǎn)的管理員只需要在他們的Web頁面中嵌入一小段JavaScript腳本就可以了。這個(gè)Javascript程序在頁 面被訪問的時(shí)候調(diào)用。它記錄了各種Google Analytics需要使用的信息，比如用戶的標(biāo)識(shí)、獲取的網(wǎng)頁的相關(guān)信息。Google Analytics匯總這些數(shù)據(jù)，之后提供給Web站點(diǎn)的管理員。

我們粗略的描述一下Google Analytics使用的兩個(gè)表。Row Click表（大約有200TB數(shù)據(jù)）的每一行存放了一個(gè)最終用戶的會(huì)話。行的名字是一個(gè)包含Web站點(diǎn)名字以及用戶會(huì)話創(chuàng)建時(shí)間的元組。這種模式保證了 對(duì)同一個(gè)Web站點(diǎn)的訪問會(huì)話是順序的，會(huì)話按時(shí)間順序存儲(chǔ)。這個(gè)表可以壓縮到原來尺寸的14%。

Summary表（大約有20TB的數(shù)據(jù)）包含了關(guān)于每個(gè)Web站點(diǎn)的、各種類型的預(yù)定義匯總信息。一個(gè)周期性運(yùn)行的MapReduce任務(wù)根據(jù) Raw Click表的數(shù)據(jù)生成Summary表的數(shù)據(jù)。每個(gè)MapReduce工作進(jìn)程都從Raw Click表中提取最新的會(huì)話數(shù)據(jù)。系統(tǒng)的整體吞吐量受限于GFS的吞吐量。這個(gè)表的能夠壓縮到原有尺寸的29%。

8.2 Google Earth

Google通過一組服務(wù)為用戶提供了高分辨率的地球表面衛(wèi)星圖像，訪問的方式可以使通過基于Web的Google Maps訪問接口（maps.google.com），也可以通過Google Earth定制的客戶端軟件訪問。這些軟件產(chǎn)品允許用戶瀏覽地球表面的圖像：用戶可以在不同的分辨率下平移、查看和注釋這些衛(wèi)星圖像。這個(gè)系統(tǒng)使用一個(gè)表 存儲(chǔ)預(yù)處理數(shù)據(jù)，使用另外一組表存儲(chǔ)用戶數(shù)據(jù)。

數(shù)據(jù)預(yù)處理流水線使用一個(gè)表存儲(chǔ)原始圖像。在預(yù)處理過程中，圖像被清除，圖像數(shù)據(jù)合并到最終的服務(wù)數(shù)據(jù)中。這個(gè)表包含了大約70TB的數(shù)據(jù)，所以需 要從磁盤讀取數(shù)據(jù)。圖像已經(jīng)被高效壓縮過了，因此存儲(chǔ)在Bigtable后不需要再壓縮了。

Imagery表的每一行都代表了一個(gè)單獨(dú)的地理區(qū)域。行都有名稱，以確保毗鄰的區(qū)域存儲(chǔ)在了一起。Imagery表中有一個(gè)列族用來記錄每個(gè)區(qū)域 的數(shù)據(jù)源。這個(gè)列族包含了大量的列：基本上市每個(gè)列對(duì)應(yīng)一個(gè)原始圖片的數(shù)據(jù)。由于每個(gè)地理區(qū)域都是由很少的幾張圖片構(gòu)成的，因此這個(gè)列族是非常稀疏的。

數(shù)據(jù)預(yù)處理流水線高度依賴運(yùn)行在Bigtable上的MapReduce任務(wù)傳輸數(shù)據(jù)。在運(yùn)行某些MapReduce任務(wù)的時(shí)候，整個(gè)系統(tǒng)中每臺(tái) Tablet服務(wù)器的數(shù)據(jù)處理速度是1MB/s。

這個(gè)服務(wù)系統(tǒng)使用一個(gè)表來索引GFS中的數(shù)據(jù)。這個(gè)表相對(duì)較?。ù蠹s是500GB），但是這個(gè)表必須在保證較低的響應(yīng)延時(shí)的前提下，針對(duì)每個(gè)數(shù)據(jù)中 心，每秒處理幾萬個(gè)查詢請(qǐng)求。 因此，這個(gè)表必須在上百個(gè)Tablet服務(wù)器上存儲(chǔ)數(shù)據(jù)，并且使用in-memory的列族。

8.3 個(gè)性化查詢

個(gè)性化查詢（www.google.com/psearch） 是一個(gè)雙向服務(wù)；這個(gè)服務(wù)記錄用戶的查詢和點(diǎn)擊，涉及到各種Google的服務(wù)，比如Web查詢、圖像和新聞。用戶可以瀏覽他們查詢的歷史，重復(fù)他們之前 的查詢和點(diǎn)擊；用戶也可以定制基于Google歷史使用習(xí)慣模式的個(gè)性化查詢結(jié)果。

個(gè)性化查詢使用Bigtable存儲(chǔ)每個(gè)用戶的數(shù)據(jù)。每個(gè)用戶都有一個(gè)唯一的用戶id，每個(gè)用戶id和一個(gè)列名綁定。一個(gè)單獨(dú)的列族被用來存儲(chǔ)各種 類型的行為（比如，有個(gè)列族可能是用來存儲(chǔ)所有的Web查詢的）。每個(gè)數(shù)據(jù)項(xiàng)都被用作Bigtable的時(shí)間戳，記錄了相應(yīng)的用戶行為發(fā)生的時(shí)間。個(gè)性化 查詢使用以Bigtable為存儲(chǔ)的MapReduce任務(wù)生成用戶的數(shù)據(jù)圖表。這些用戶數(shù)據(jù)圖表用來個(gè)性化當(dāng)前的查詢結(jié)果。

個(gè)性化查詢的數(shù)據(jù)會(huì)復(fù)制到幾個(gè)Bigtable的集群上，這樣就增強(qiáng)了數(shù)據(jù)可用性，同時(shí)減少了由客戶端和Bigtable集群間的“距離”造成的延 時(shí)。個(gè)性化查詢的開發(fā)團(tuán)隊(duì)最初建立了一個(gè)基于Bigtable的、“客戶側(cè)”的復(fù)制機(jī)制為所有的復(fù)制節(jié)點(diǎn)提供一致性保障?，F(xiàn)在的系統(tǒng)則使用了內(nèi)建的復(fù)制子 系統(tǒng)。

個(gè)性化查詢存儲(chǔ)系統(tǒng)的設(shè)計(jì)允許其它的團(tuán)隊(duì)在它們自己的列中加入新的用戶數(shù)據(jù)，因此，很多Google服務(wù)使用個(gè)性化查詢存儲(chǔ)系統(tǒng)保存用戶級(jí)的配置參 數(shù)和設(shè)置。在多個(gè)團(tuán)隊(duì)之間分享數(shù)據(jù)的結(jié)果是產(chǎn)生了大量的列族。為了更好的支持?jǐn)?shù)據(jù)共享，我們加入了一個(gè)簡單的配額機(jī)制(alex注：quota，參考AIX的配額機(jī)制)限制用戶在 共享表中使用的空間；配額也為使用個(gè)性化查詢系統(tǒng)存儲(chǔ)用戶級(jí)信息的產(chǎn)品團(tuán)體提供了隔離機(jī)制。

#p#

9 經(jīng)驗(yàn)教訓(xùn)

在設(shè)計(jì)、實(shí)現(xiàn)、維護(hù)和支持Bigtable的過程中，我們得到了很多有用的經(jīng)驗(yàn)和一些有趣的教訓(xùn)。

一個(gè)教訓(xùn)是，我們發(fā)現(xiàn)，很多類型的錯(cuò)誤都會(huì)導(dǎo)致大型分布式系統(tǒng)受損，這些錯(cuò)誤不僅僅是通常的網(wǎng)絡(luò)中斷、或者很多分布式協(xié)議中設(shè)想的fail- stop類型的錯(cuò)誤（alex注：fail-stop failture，指一旦系統(tǒng)fail就stop，不輸出任何數(shù)據(jù)；fail-fast failture，指fail不馬上stop，在短時(shí)間內(nèi)return錯(cuò)誤信息，然后再stop）。比如，我們遇到過下面這些類型的錯(cuò)誤導(dǎo)致的問題：內(nèi)存數(shù)據(jù)損壞、網(wǎng)絡(luò)中斷、時(shí)鐘偏差、機(jī)器掛起、擴(kuò)展的和非對(duì)稱的網(wǎng)絡(luò)分區(qū)（alex注：extended and asymmetric network partitions，不明白什么意思。partition也有中斷的意思，但是我不知道如何用在這里）(這里應(yīng)該就是指網(wǎng)絡(luò)分區(qū)吧,partition在這里明顯是名詞,所以不大會(huì)是”中斷”)、我們使用的其它系統(tǒng)的 Bug（比如Chubby）、GFS配額溢出、計(jì)劃內(nèi)和計(jì)劃外的硬件維護(hù)。我們?cè)诮鉀Q這些問題的過程中學(xué)到了很多經(jīng)驗(yàn)，我們通過修改協(xié)議來解決這些問題。 比如，我們?cè)谖覀兊腞PC機(jī)制中加入了Checksum。我們?cè)谠O(shè)計(jì)系統(tǒng)的部分功能時(shí)，不對(duì)其它部分功能做任何的假設(shè)，這樣的做法解決了其它的一些問題。 比如，我們不再假設(shè)一個(gè)特定的Chubby操作只返回錯(cuò)誤碼集合中的一個(gè)值。

另外一個(gè)教訓(xùn)是，我們明白了在徹底了解一個(gè)新特性會(huì)被如何使用之后，再?zèng)Q定是否添加這個(gè)新特性是非常重要的。比如，我們開始計(jì)劃在我們的API中支 持通常方式的事務(wù)處理。但是由于我們還不會(huì)馬上用到這個(gè)功能，因此，我們并沒有去實(shí)現(xiàn)它。現(xiàn)在，Bigtable上已經(jīng)有了很多的實(shí)際應(yīng)用，我們可以檢查 它們真實(shí)的需求；我們發(fā)現(xiàn)，大多是應(yīng)用程序都只是需要單個(gè)行上的事務(wù)功能。有些應(yīng)用需要分布式的事務(wù)功能，分布式事務(wù)大多數(shù)情況下用于維護(hù)二級(jí)索引，因此 我們?cè)黾恿艘粋€(gè)特殊的機(jī)制去滿足這個(gè)需求。新的機(jī)制在通用性上比分布式事務(wù)差很多，但是它更有效（特別是在更新操作的涉及上百行數(shù)據(jù)的時(shí)候），而且非常符 合我們的“跨數(shù)據(jù)中心”復(fù)制方案的優(yōu)化策略。

還有一個(gè)具有實(shí)踐意義的經(jīng)驗(yàn)：我們發(fā)現(xiàn)系統(tǒng)級(jí)的監(jiān)控對(duì)Bigtable非常重要（比如，監(jiān)控Bigtable自身以及使用Bigtable的客戶程 序）。比如，我們擴(kuò)展了我們的RPC系統(tǒng)，因此對(duì)于一個(gè)RPC調(diào)用的例子，它可以詳細(xì)記錄代表了RPC調(diào)用的很多重要操作。這個(gè)特性允許我們檢測(cè)和修正很 多的問題，比如Tablet數(shù)據(jù)結(jié)構(gòu)上的鎖的內(nèi)容、在修改操作提交時(shí)對(duì)GFS的寫入非常慢的問題、以及在METADATA表的Tablet不可用時(shí)，對(duì) METADATA表的訪問掛起的問題。關(guān)于監(jiān)控的用途的另外一個(gè)例子是，每個(gè)Bigtable集群都在Chubby中注冊(cè)了。這可以幫助我們跟蹤所有的集 群狀態(tài)、監(jiān)控它們的大小、檢查集群運(yùn)行的我們軟件的版本、監(jiān)控集群流入數(shù)據(jù)的流量，以及檢查是否有引發(fā)集群高延時(shí)的潛在因素。

對(duì)我們來說，最寶貴的經(jīng)驗(yàn)是簡單設(shè)計(jì)的價(jià)值?？紤]到我們系統(tǒng)的代碼量（大約100000行生產(chǎn)代碼（alex注：non-test code）），以及隨著時(shí)間的推移，新的代碼以各種難以預(yù)料的方式加入系統(tǒng)，我們發(fā)現(xiàn)簡潔的設(shè)計(jì)和編碼給維護(hù)和調(diào)試帶來的巨大好處。 這方面的一個(gè)例子是我們的Tablet服務(wù)器成員協(xié)議。我們第一版的協(xié)議很簡單：Master服務(wù)器周期性的和Tablet服務(wù)器簽訂租約，Tablet 服務(wù)器在租約過期的時(shí)候Kill掉自己的進(jìn)程。不幸的是，這個(gè)協(xié)議在遇到網(wǎng)絡(luò)問題時(shí)會(huì)大大降低系統(tǒng)的可用性，也會(huì)大大增加Master服務(wù)器恢復(fù)的時(shí)間。 我們多次重新設(shè)計(jì)這個(gè)協(xié)議，直到它能夠很好的處理上述問題。但是，更不幸的是，最終的協(xié)議過于復(fù)雜了，并且依賴一些Chubby很少被用到的特性。我們發(fā) 現(xiàn)我們浪費(fèi)了大量的時(shí)間在調(diào)試一些古怪的問題(alex注：obscure corner cases)，有些是Bigtable代碼的問題，有些事Chubby代碼的問題。最后，我們只好廢棄了這 個(gè)協(xié)議，重新制訂了一個(gè)新的、更簡單、只使用Chubby最廣泛使用的特性的協(xié)議。

10 相關(guān)工作

Boxwood【24】項(xiàng)目的有些組件在某些方面和Chubby、GFS以及Bigtable類似，因?yàn)樗蔡峁┝酥T如分布式協(xié)議、鎖、分布式 Chunk存儲(chǔ)以及分布式B-tree存儲(chǔ)。Boxwood與Google的某些組件盡管功能類似，但是Boxwood的組件提供更底層的服務(wù)。 Boxwood項(xiàng)目的目的是提供創(chuàng)建類似文件系統(tǒng)、數(shù)據(jù)庫等高級(jí)服務(wù)的基礎(chǔ)構(gòu)件，而Bigtable的目的是直接為客戶程序的數(shù)據(jù)存儲(chǔ)需求提供支持。

現(xiàn)在有不少項(xiàng)目已經(jīng)攻克了很多難題，實(shí)現(xiàn)了在廣域網(wǎng)上的分布式數(shù)據(jù)存儲(chǔ)或者高級(jí)服務(wù)，通常是“Internet規(guī)模”的。這其中包括了分布式的 Hash表，這項(xiàng)工作由一些類似CAN【29】、Chord【32】、Tapestry【37】和Pastry【30】的項(xiàng)目率先發(fā)起。這些系統(tǒng)的主要關(guān) 注點(diǎn)和Bigtable不同，比如應(yīng)對(duì)各種不同的傳輸帶寬、不可信的協(xié)作者、頻繁的更改配置等；另外，去中心化和Byzantine災(zāi)難冗余(alex注：Byzantine，即拜占庭式的風(fēng)格，也就是一種復(fù)雜詭秘的風(fēng)格。 Byzantine Fault表示：對(duì)于處理來說，當(dāng)發(fā)錯(cuò)誤時(shí)處理器并不停止接收輸出，也不停止輸出，錯(cuò)就錯(cuò)了，只管算，對(duì)于這種錯(cuò)誤來說，這樣可真是夠麻煩了，因?yàn)橛脩舾?本不知道錯(cuò)誤發(fā)生了，也就根本談不上處理錯(cuò)誤了。在多處理器的情況下，這種錯(cuò)誤可能導(dǎo)致運(yùn)算正確結(jié)果的處理器也產(chǎn)生錯(cuò)誤的結(jié)果，這樣事情就更麻煩了，所以 一定要避免處理器產(chǎn)生這種錯(cuò)誤。)也不是Bigtable的目的。

就提供給應(yīng)用程序開發(fā)者的分布式數(shù)據(jù)存儲(chǔ)模型而言，我們相信，分布式B-Tree或者分布式Hash表提供的Key-value pair方式的模型有很大的局限性。Key-value pair模型是很有用的組件，但是它們不應(yīng)該是提供給開發(fā)者唯一的組件。我們選擇的模型提供的組件比簡單的Key-value pair豐富的多，它支持稀疏的、半結(jié)構(gòu)化的數(shù)據(jù)。另外，它也足夠簡單，能夠高效的處理平面文件；它也是透明的（通過局部性群組），允許我們的使用者對(duì)系 統(tǒng)的重要行為進(jìn)行調(diào)整。

有些數(shù)據(jù)庫廠商已經(jīng)開發(fā)出了并行的數(shù)據(jù)庫系統(tǒng)，能夠存儲(chǔ)海量的數(shù)據(jù)。Oracle的RAC【27】使用共享磁盤存儲(chǔ)數(shù)據(jù)（Bigtable使用 GFS），并且有一個(gè)分布式的鎖管理系統(tǒng)（Bigtable使用Chubby）。IBM并行版本的DB2【4】基于一種類似于Bigtable的、不共享 任何東西的架構(gòu)（a shared-nothing architecture）【33】。每個(gè)DB2的服務(wù)器都負(fù)責(zé)處理存儲(chǔ)在一個(gè)關(guān)系型數(shù)據(jù)庫中的表中的行的一個(gè)子集。這些產(chǎn)品都提供了一個(gè)帶有事務(wù)功能的 完整的關(guān)系模型。

Bigtable的局部性群組提供了類似于基于列的存儲(chǔ)方案在壓縮和磁盤讀取方面具有的性能；這些以列而不是行的方式組織數(shù)據(jù)的方案包括C- Store【1，34】、商業(yè)產(chǎn)品Sybase IQ【15，36】、SenSage【31】、KDB+【22】，以及MonetDB/X100【38】的ColumnDM存儲(chǔ)層。另外一種在平面文件中 提供垂直和水平數(shù)據(jù)分區(qū)、并且提供很好的數(shù)據(jù)壓縮率的系統(tǒng)是AT&T的Daytona數(shù)據(jù)庫【19】。局部性群組不支持Ailamaki系統(tǒng)中描 述的CPU緩存級(jí)別的優(yōu)化【2】。

Bigtable采用memtable和SSTable存儲(chǔ)對(duì)表的更新的方法與Log-Structured Merge Tree【26】存儲(chǔ)索引數(shù)據(jù)更新的方法類似。這兩個(gè)系統(tǒng)中，排序的數(shù)據(jù)在寫入到磁盤前都先存放在內(nèi)存中，讀取操作必須從內(nèi)存和磁盤中合并數(shù)據(jù)產(chǎn)生最終的 結(jié)果集。

C-Store和Bigtable有很多相似點(diǎn)：兩個(gè)系統(tǒng)都采用Shared-nothing架構(gòu)，都有兩種不同的數(shù)據(jù)結(jié)構(gòu)，一種用于當(dāng)前的寫操 作，另外一種存放“長時(shí)間使用”的數(shù)據(jù)，并且提供一種機(jī)制在兩個(gè)存儲(chǔ)結(jié)構(gòu)間搬運(yùn)數(shù)據(jù)。兩個(gè)系統(tǒng)在API接口函數(shù)上有很大的不同：C-Store操作更像關(guān) 系型數(shù)據(jù)庫，而Bigtable提供了低層次的讀寫操作接口，并且設(shè)計(jì)的目標(biāo)是能夠支持每臺(tái)服務(wù)器每秒數(shù)千次操作。C-Store同時(shí)也是個(gè)“讀性能優(yōu)化 的關(guān)系型數(shù)據(jù)庫”，而Bigtable對(duì)讀和寫密集型應(yīng)用都提供了很好的性能。

【編輯推薦】

1. Twitter推出“Gizzard”分布式數(shù)據(jù)存儲(chǔ)框架
2. 豆瓣網(wǎng)開源數(shù)據(jù)庫BeansDB發(fā)布 采用分布式鍵值存儲(chǔ)
3. 脫離理論，觸摸NoSQL：分布式可擴(kuò)展非關(guān)系數(shù)據(jù)庫聚焦
4. 分布式數(shù)據(jù)庫的前世今生
5. 分布式緩存系統(tǒng)Memcached入門指導(dǎo)