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

Bigtable是一個(gè)分布式的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)系統(tǒng)，它被設(shè)計(jì)用來(lái)處理海量數(shù)據(jù)：通常是分布在數(shù)千臺(tái)普通服務(wù)器上的PB級(jí)的數(shù)據(jù)。Google的很多項(xiàng)目使用Bigtable存儲(chǔ)數(shù)據(jù)，包括Web索引、GoogleEarth、GoogleFinance。這些應(yīng)用對(duì)Bigtable提出的要求差異非常大，無(wú)論是在數(shù)據(jù)量上（從URL到網(wǎng)頁(yè)到衛(wèi)星圖像）還是在響應(yīng)速度上（從后端的批量處理到實(shí)時(shí)數(shù)據(jù)服務(wù)）。盡管應(yīng)用需求差異很大，但是，針對(duì)Google的這些產(chǎn)品，Bigtable還是成功的提供了一個(gè)靈活的、高性能的解決方案。本論文描述了Bigtable提供的簡(jiǎn)單的數(shù)據(jù)模型，利用這個(gè)模型，用戶(hù)可以動(dòng)態(tài)的控制數(shù)據(jù)的分布和格式；我們還將描述Bigtable的設(shè)計(jì)和實(shí)現(xiàn)。在過(guò)去兩年半時(shí)間里，我們?cè)O(shè)計(jì)、實(shí)現(xiàn)并部署了一個(gè)分布式的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)系統(tǒng)—在Google，我們稱(chēng)之為Bigtable。Bigtable的設(shè)計(jì)目的是可靠的處理PB級(jí)別的數(shù)據(jù)，并且能夠部署到上千臺(tái)機(jī)器上。Bigtable已經(jīng)實(shí)現(xiàn)了下面的幾個(gè)目標(biāo)：適用性廣泛、可擴(kuò)展、高性能和高可用性。Bigtable已經(jīng)在超過(guò)60個(gè)Google的產(chǎn)品和項(xiàng)目上得到了應(yīng)用，包括GoogleAnalytics、GoogleFinance、Orkut、PersonalizedSearch、Writely和GoogleEarth。這些產(chǎn)品對(duì)Bigtable提出了迥異的需求，有的需要高吞吐量的批處理，有的則需要及時(shí)響應(yīng)，快速返回?cái)?shù)據(jù)給最終用戶(hù)。它們使用的Bigtable集群的配置也有很大的差異，有的集群只有幾臺(tái)服務(wù)器，而有的則需要上千臺(tái)服務(wù)器、存儲(chǔ)幾百TB的數(shù)據(jù)。

在很多方面，Bigtable和數(shù)據(jù)庫(kù)很類(lèi)似：它使用了很多數(shù)據(jù)庫(kù)的實(shí)現(xiàn)策略。并行數(shù)據(jù)庫(kù)【14】和內(nèi)存數(shù)據(jù)庫(kù)【13】已經(jīng)具備可擴(kuò)展性和高性能，但是Bigtable提供了一個(gè)和這些系統(tǒng)完全不同的接口。Bigtable不支持完整的關(guān)系數(shù)據(jù)模型；與之相反，Bigtable為客戶(hù)提供了簡(jiǎn)單的數(shù)據(jù)模型，利用這個(gè)模型，客戶(hù)可以動(dòng)態(tài)控制數(shù)據(jù)的分布和格式（alex注：也就是對(duì)BigTable而言，數(shù)據(jù)是沒(méi)有格式的，用數(shù)據(jù)庫(kù)領(lǐng)域的術(shù)語(yǔ)說(shuō)，就是數(shù)據(jù)沒(méi)有Schema，用戶(hù)自己去定義Schema），用戶(hù)也可以自己推測(cè)(alex注：reasonabout)底層存儲(chǔ)數(shù)據(jù)的位置相關(guān)性(alex注：位置相關(guān)性可以這樣理解，比如樹(shù)狀結(jié)構(gòu)，具有相同前綴的數(shù)據(jù)的存放位置接近。在讀取的時(shí)候，可以把這些數(shù)據(jù)一次讀取出來(lái))。數(shù)據(jù)的下標(biāo)是行和列的名字，名字可以是任意的字符串。Bigtable將存儲(chǔ)的數(shù)據(jù)都視為字符串，但是Bigtable本身不去解析這些字符串，客戶(hù)程序通常會(huì)在把各種結(jié)構(gòu)化或者半結(jié)構(gòu)化的數(shù)據(jù)串行化到這些字符串里。通過(guò)仔細(xì)選擇數(shù)據(jù)的模式，客戶(hù)可以控制數(shù)據(jù)的位置相關(guān)性。最后，可以通過(guò)BigTable的模式參數(shù)來(lái)控制數(shù)據(jù)是存放在內(nèi)存中、還是硬盤(pán)上。第二節(jié)描述關(guān)于數(shù)據(jù)模型更多細(xì)節(jié)方面的東西；第三節(jié)概要介紹了客戶(hù)端API；第四節(jié)簡(jiǎn)要介紹了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ì)和后期支持過(guò)程中得到一些經(jīng)驗(yàn)和教訓(xùn)；最后，在第10節(jié)列出我們的相關(guān)研究工作，第11節(jié)是我們的結(jié)論。Bigtable是一個(gè)稀疏的、分布式的、持久化存儲(chǔ)的多維度排序Map（alex注：對(duì)于程序員來(lái)說(shuō)，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è)類(lèi)似Bigtable的系統(tǒng)的種種潛在用途之后，決定使用這個(gè)數(shù)據(jù)模型。我們先舉個(gè)具體的例子，這個(gè)例子促使我們做了很多設(shè)計(jì)決策；假設(shè)我們想要存儲(chǔ)海量的網(wǎng)頁(yè)及相關(guān)信息，這些數(shù)據(jù)可以用于很多不同的項(xiàng)目，我們姑且稱(chēng)這個(gè)特殊的表為Webtable。在Webtable里，我們使用URL作為行關(guān)鍵字，使用網(wǎng)頁(yè)的某些屬性作為列名，網(wǎng)頁(yè)的內(nèi)容存在“contents:”列中，并用獲取該網(wǎng)頁(yè)的時(shí)間戳作為標(biāo)識(shí)(alex注：即按照獲取時(shí)間不同，存儲(chǔ)了多個(gè)版本的網(wǎng)頁(yè)數(shù)據(jù))，如圖一所示。圖一：一個(gè)存儲(chǔ)Web網(wǎng)頁(yè)的例子的表的片斷。行名是一個(gè)反向URL。contents列族存放的是網(wǎng)頁(yè)的內(nèi)容，anchor列族存放引用該網(wǎng)頁(yè)的錨鏈接文本（alex注：如果不知道HTML的Anchor，請(qǐng)Google一把）。CNN的主頁(yè)被SportsIllustrater和MY-look的主頁(yè)引用，因此該行包含了名為“anchor:”和“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ù)用戶(hù)，10-100個(gè)字節(jié)就足夠了）。對(duì)同一個(gè)行關(guān)鍵字的讀或者寫(xiě)操作都是原子的（不管讀或者寫(xiě)這一行里多少個(gè)不同列），這個(gè)設(shè)計(jì)決策能夠使用戶(hù)很容易的理解程序在對(duì)同一個(gè)行進(jìn)行并發(fā)更新操作時(shí)的行為。

Bigtable通過(guò)行關(guān)鍵字的字典順序來(lái)組織數(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ī)器間的通信即可完成。用戶(hù)可以通過(guò)選擇合適的行關(guān)鍵字，在數(shù)據(jù)訪(fǎng)問(wèn)時(shí)有效利用數(shù)據(jù)的位置相關(guān)性，從而更好的利用這個(gè)特性。舉例來(lái)說(shuō)，在Webtable里，通過(guò)反轉(zhuǎn)URL中主機(jī)名的方式，可以把同一個(gè)域名下的網(wǎng)頁(yè)聚集起來(lái)組織成連續(xù)的行。具體來(lái)說(shuō)，我們可以把/index.html的數(shù)據(jù)存放在關(guān)鍵字com.google.maps/index.html下。把相同的域中的網(wǎng)頁(yè)存儲(chǔ)在連續(xù)的區(qū)域可以讓基于主機(jī)和域名的分析更加有效。

列族列關(guān)鍵字組成的集合叫做“列族“，列族是訪(fǎng)問(wèn)控制的基本單位。存放在同一列族下的所有數(shù)據(jù)通常都屬于同一個(gè)類(lèi)型（我們可以把同一個(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)的，一張表可以有無(wú)限多個(gè)列。列關(guān)鍵字的命名語(yǔ)法如下：列族：限定詞。列族的名字必須是可打印的字符串，而限定詞的名字可以是任意的字符串。比如，Webtable有個(gè)列族language，language列族用來(lái)存放撰寫(xiě)網(wǎng)頁(yè)的語(yǔ)言。我們?cè)趌anguage列族中只使用一個(gè)列關(guān)鍵字，用來(lái)存放每個(gè)網(wǎng)頁(yè)的語(yǔ)言標(biāo)識(shí)ID。Webtable中另一個(gè)有用的列族是anchor；這個(gè)列族的每一個(gè)列關(guān)鍵字代表一個(gè)錨鏈接，如圖一所示。Anchor列族的限定詞是引用該網(wǎng)頁(yè)的站點(diǎn)名；Anchor列族每列的數(shù)據(jù)項(xiàng)存放的是鏈接文本。訪(fǎng)問(wèn)控制、磁盤(pán)和內(nèi)存的使用統(tǒng)計(jì)都是在列族層面進(jìn)行的。在我們的Webtable的例子中，上述的控制權(quán)限能幫助我們管理不同類(lèi)型的應(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ù)通過(guò)時(shí)間戳來(lái)索引。Bigtable時(shí)間戳的類(lèi)型是64位整型。Bigtable可以給時(shí)間戳賦值，用來(lái)表示精確到毫秒的“實(shí)時(shí)”時(shí)間；用戶(hù)程序也可以給時(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通過(guò)這兩個(gè)參數(shù)可以對(duì)廢棄版本的數(shù)據(jù)自動(dòng)進(jìn)行垃圾收集。用戶(hù)可以指定只保存最后n個(gè)版本的數(shù)據(jù)，或者只保存“足夠新”的版本的數(shù)據(jù)（比如，只保存最近7天的內(nèi)容寫(xiě)入的數(shù)據(jù)）。在Webtable的舉例里，contents:列存儲(chǔ)的時(shí)間戳信息是網(wǎng)絡(luò)爬蟲(chóng)抓取一個(gè)頁(yè)面的時(shí)間。上面提及的垃圾收集機(jī)制可以讓我們只保留最近三個(gè)版本的網(wǎng)頁(yè)數(shù)據(jù)。Bigtable提供了建立和刪除表以及列族的API函數(shù)。Bigtable還提供了修改集群、表和列族的元數(shù)據(jù)的API，比如修改訪(fǎng)問(wèn)權(quán)限。

//Openthetable

Table*T=OpenOrDie(“/bigtable/web/webtable”);

//Writeanewanchoranddeleteanoldanchor

RowMutationr1(T,“n.www”);

r1.Set(“anchor:”,“CNN”);

r1.Delete(“anchor:”);

Operationop;

Apply(&op,&r1);

Figure2:WritingtoBigtable.

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

Scannerscanner(T);

ScanStream*stream;

stream=scanner.FetchColumnFamily(“anchor”);

stream->SetReturnAllVersions();

scanner.Lookup(“n.www”);

for(;!stream->Done();stream->Next()){

printf(“%s%s%lld%s\n”,

scanner.RowName(),

stream->ColumnName(),

stream->MicroTimestamp(),

stream->Value());

}

Figure3:ReadingfromBigtable.

圖3中的C++代碼使用Scanner抽象對(duì)象遍歷一個(gè)行內(nèi)的所有錨點(diǎn)?？蛻?hù)程序可以遍歷多個(gè)列族，有幾種方法可以對(duì)掃描輸出的行、列和時(shí)間戳進(jìn)行限制。例如，我們可以限制上面的掃描，讓它只輸出那些匹配正則表達(dá)式*.的錨點(diǎn)，或者那些時(shí)間戳在當(dāng)前時(shí)間前10天的錨點(diǎn)。Bigtable還支持一些其它的特性，利用這些特性，用戶(hù)可以對(duì)數(shù)據(jù)進(jìn)行更復(fù)雜的處理。首先，Bigtable支持單行上的事務(wù)處理，利用這個(gè)功能，用戶(hù)可以對(duì)存儲(chǔ)在一個(gè)行關(guān)鍵字下的數(shù)據(jù)進(jìn)行原子性的讀-更新-寫(xiě)操作。雖然Bigtable提供了一個(gè)允許用戶(hù)跨行批量寫(xiě)入數(shù)據(jù)的接口，但是，Bigtable目前還不支持通用的跨行事務(wù)處理。其次，Bigtable允許把數(shù)據(jù)項(xiàng)用做整數(shù)計(jì)數(shù)器。最后，Bigtable允許用戶(hù)在服務(wù)器的地址空間內(nèi)執(zhí)行腳本程序。腳本程序使用Google開(kāi)發(fā)的Sawzall【28】數(shù)據(jù)處理語(yǔ)言。雖然目前我們基于的Sawzall語(yǔ)言的API函數(shù)還不允許客戶(hù)的腳本程序?qū)懭霐?shù)據(jù)到Bigtable，但是它允許多種形式的數(shù)據(jù)轉(zhuǎn)換、基于任意表達(dá)式的數(shù)據(jù)過(guò)濾、以及使用多種操作符的進(jìn)行數(shù)據(jù)匯總。Bigtable可以和MapReduce【12】一起使用，MapReduce是Google開(kāi)發(fā)的大規(guī)模并行計(jì)算框架。我們已經(jīng)開(kāi)發(fā)了一些Wrapper類(lèi)，通過(guò)使用這些Wrapper類(lèi)，Bigtable可以作為MapReduce框架的輸入和輸出。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依賴(lài)集群管理系統(tǒng)來(lái)調(diào)度任務(wù)、管理共享的機(jī)器上的資源、處理機(jī)器的故障、以及監(jiān)視機(jī)器的狀態(tài)。

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

BigTable還依賴(lài)一個(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】來(lái)保證副本的一致性。Chubby提供了一個(gè)名字空間，里面包括了目錄和小文件。每個(gè)目錄或者文件可以當(dāng)成一個(gè)鎖，讀寫(xiě)文件的操作都是原子的。Chubby客戶(hù)程序庫(kù)提供對(duì)Chubby文件的一致性緩存。每個(gè)Chubby客戶(hù)程序都維護(hù)一個(gè)與Chubby服務(wù)的會(huì)話(huà)。如果客戶(hù)程序不能在租約到期的時(shí)間內(nèi)重新簽訂會(huì)話(huà)的租約，這個(gè)會(huì)話(huà)就過(guò)期失效了(alex注：又用到了lease。原文是：Aclient’ssessionexpiresifitisunabletorenewitssessionleasewithintheleaseexpirationtime.)。當(dāng)一個(gè)會(huì)話(huà)失效時(shí)，它擁有的鎖和打開(kāi)的文件句柄都失效了。Chubby客戶(hù)程序可以在文件和目錄上注冊(cè)回調(diào)函數(shù)，當(dāng)文件或目錄改變、或者會(huì)話(huà)過(guò)期時(shí)，回調(diào)函數(shù)會(huì)通知客戶(hù)程序。

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ǔ)訪(fǎng)問(wèn)控制列表。如果Chubby長(zhǎng)時(shí)間無(wú)法訪(fǎng)問(wèn)，BigTable就會(huì)失效。最近我們?cè)谑褂?1個(gè)Chubby服務(wù)實(shí)例的14個(gè)BigTable集群上測(cè)量了這個(gè)影響。由于Chubby不可用而導(dǎo)致BigTable中的部分?jǐn)?shù)據(jù)不能訪(fǎng)問(wèn)的平均比率是0.0047%（Chubby不能訪(fǎng)問(wèn)的原因可能是Chubby本身失效或者網(wǎng)絡(luò)問(wèn)題）。單個(gè)集群里，受Chubby失效影響最大的百分比是0.0326%（alex注：有點(diǎn)莫名其妙，原文是：

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

Master服務(wù)器主要負(fù)責(zé)以下工作：為T(mén)ablet服務(wù)器分配Tablets、檢測(cè)新加入的或者過(guò)期失效的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的讀寫(xiě)操作，以及在Tablets過(guò)大時(shí)，對(duì)其進(jìn)行分割。

和很多Single-Master類(lèi)型的分布式存儲(chǔ)系統(tǒng)【17.21】類(lèi)似，客戶(hù)端讀取的數(shù)據(jù)都不經(jīng)過(guò)Master服務(wù)器：客戶(hù)程序直接和Tablet服務(wù)器通信進(jìn)行讀寫(xiě)操作。由于BigTable的客戶(hù)程序不必通過(guò)Master服務(wù)器來(lái)獲取Tablet的位置信息，因此，大多數(shù)客戶(hù)程序甚至完全不需要和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ù)的增長(zhǎng)，它被自動(dòng)分割成多個(gè)Tablet，缺省情況下，每個(gè)Tablet的尺寸大約是100MB到200MB。我們使用一個(gè)三層的、類(lèi)似Ｂ+樹(shù)[10]的結(jié)構(gòu)存儲(chǔ)Tablet的位置信息(如圖4)。第一層是一個(gè)存儲(chǔ)在Chubby中的文件，它包含了RootTablet的位置信息。RootTablet包含了一個(gè)特殊的METADATA表里所有的Tablet的位置信息。METADATA表的每個(gè)Tablet包含了一個(gè)用戶(hù)Tablet的集合。RootTablet實(shí)際上是METADATA表的第一個(gè)Tablet，只不過(guò)對(duì)它的處理比較特殊—RootTablet永遠(yuǎn)不會(huì)被分割—這就保證了Tablet的位置信息存儲(chǔ)結(jié)構(gòu)不會(huì)超過(guò)三層。在METADATA表里面，每個(gè)Tablet的位置信息都存放在一個(gè)行關(guān)鍵字下面，而這個(gè)行關(guān)鍵字是由Tablet所在的表的標(biāo)識(shí)符和Tablet的最后一行編碼而成的。METADATA的每一行都存儲(chǔ)了大約1KB的內(nèi)存數(shù)據(jù)。在一個(gè)大小適中的、容量限制為128MB的METADATATablet中，采用這種三層結(jié)構(gòu)的存儲(chǔ)模式，可以標(biāo)識(shí)2^34個(gè)Tablet的地址（如果每個(gè)Tablet存儲(chǔ)128MB數(shù)據(jù)，那么一共可以存儲(chǔ)2^61字節(jié)數(shù)據(jù)）?？蛻?hù)程序使用的庫(kù)會(huì)緩存Tablet的位置信息。如果客戶(hù)程序沒(méi)有緩存某個(gè)Tablet的地址信息，或者發(fā)現(xiàn)它緩存的地址信息不正確，客戶(hù)程序就在樹(shù)狀的存儲(chǔ)結(jié)構(gòu)中遞歸的查詢(xún)Tablet位置信息；如果客戶(hù)端緩存是空的，那么尋址算法需要通過(guò)三次網(wǎng)絡(luò)來(lái)回通信尋址，這其中包括了一次Chubby讀操作；如果客戶(hù)端緩存的地址信息過(guò)期了，那么尋址算法可能需要最多６次網(wǎng)絡(luò)來(lái)回通信才能更新數(shù)據(jù)，因?yàn)橹挥性诰彺嬷袥](méi)有查到數(shù)據(jù)的時(shí)候才能發(fā)現(xiàn)數(shù)據(jù)過(guò)期（alex注：其中的三次通信發(fā)現(xiàn)緩存過(guò)期，另外三次更新緩存數(shù)據(jù)）(假設(shè)METADATA的Tablet沒(méi)有被頻繁的移動(dòng)）。盡管Tablet的地址信息是存放在內(nèi)存里的，對(duì)它的操作不必訪(fǎng)問(wèn)GFS文件系統(tǒng)，但是，通常我們會(huì)通過(guò)預(yù)取Tablet地址來(lái)進(jìn)一步的減少訪(fǎng)問(wèn)的開(kāi)銷(xiāo)：每次需要從METADATA表中讀取一個(gè)Tablet的元數(shù)據(jù)的時(shí)候，它都會(huì)多讀取幾個(gè)Tablet的元數(shù)據(jù)。在METADATA表中還存儲(chǔ)了次級(jí)信息(alex注：secondaryinformation)，包括每個(gè)Tablet的事件日志（例如，什么時(shí)候一個(gè)服務(wù)器開(kāi)始為該Tablet提供服務(wù)）。這些信息有助于排查錯(cuò)誤和性能分析。在任何一個(gè)時(shí)刻，一個(gè)Tablet只能分配給一個(gè)Tablet服務(wù)器。Master服務(wù)器記錄了當(dāng)前有哪些活躍的Tablet服務(wù)器、哪些Tablet分配給了哪些Tablet服務(wù)器、哪些Tablet還沒(méi)有被分配。當(dāng)一個(gè)Tablet還沒(méi)有被分配、并且剛好有一個(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ò)斷開(kāi)導(dǎo)致Tablet服務(wù)器和Chubby的會(huì)話(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注：soitkillsitself）。當(dāng)Tablet服務(wù)器終止時(shí)（比如，集群的管理系統(tǒng)將運(yùn)行該Tablet服務(wù)器的主機(jī)從集群中移除），它會(huì)嘗試釋放它持有的文件鎖，這樣一來(lái)，Master服務(wù)器就能盡快把Tablet分配到其它的Tablet服務(wù)器。Master服務(wù)器負(fù)責(zé)檢查一個(gè)Tablet服務(wù)器是否已經(jīng)不再為它的Tablet提供服務(wù)了，并且要盡快重新分配它加載的Tablet。Master服務(wù)器通過(guò)輪詢(xún)Tablet服務(wù)器文件鎖的狀態(tài)來(lái)檢測(cè)何時(shí)Tablet服務(wù)器不再為T(mén)ablet提供服務(wù)。如果一個(gè)Tablet服務(wù)器報(bào)告它丟失了文件鎖，或者M(jìn)aster服務(wù)器最近幾次嘗試和它通信都沒(méi)有得到響應(yīng)，Master服務(wù)器就會(huì)嘗試獲取該Tablet服務(wù)器文件的獨(dú)占鎖；如果Master服務(wù)器成功獲取了獨(dú)占鎖，那么就說(shuō)明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ì)話(huà)過(guò)期后主動(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鎖，用來(lái)阻止創(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的集合。在掃描的過(guò)程中，當(dāng)Master服務(wù)器發(fā)現(xiàn)了一個(gè)還沒(méi)有分配的Tablet，Master服務(wù)器就將這個(gè)Tablet加入未分配的Tablet集合等待合適的時(shí)機(jī)分配?？赡軙?huì)遇到一種復(fù)雜的情況：在METADATA表的Tablet還沒(méi)有被分配之前是不能夠掃描它的。因此，在開(kāi)始掃描之前（步驟4），如果在第三步的掃描過(guò)程中發(fā)現(xiàn)RootTablet還沒(méi)有分配，Master服務(wù)器就把RootTablet加入到未分配的Tablet集合。這個(gè)附加操作確保了RootTablet會(huì)被分配。由于RootTablet包括了所有METADATA的Tablet的名字，因此Master服務(wù)器掃描完RootTablet以后，就得到了所有的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ù)器通過(guò)在METADATA表中記錄新的Tablet的信息來(lái)提交這個(gè)操作；當(dāng)分割操作提交之后，Tablet服務(wù)器會(huì)通知Master服務(wù)器。如果分割操作已提交的信息沒(méi)有通知到Master服務(wù)器（可能兩個(gè)服務(wù)器中有一個(gè)宕機(jī)了），Master服務(wù)器在要求Tablet服務(wù)器裝載已經(jīng)被分割的子表的時(shí)候會(huì)發(fā)現(xiàn)一個(gè)新的Tablet。通過(guò)對(duì)比METADATA表中Tablet的信息，Tablet服務(wù)器會(huì)發(fā)現(xiàn)Master服務(wù)器要求其裝載的Tablet并不完整，因此，Tablet服務(wù)器會(huì)重新向Master服務(wù)器發(fā)送通知信息。如圖5所示，Tablet的持久化狀態(tài)信息保存在GFS上。更新操作提交到REDO日志中（alex注：Updatesarecommittedtoacommitlogthatstoresredorecords）。在這些更新操作中，最近提交的那些存放在一個(gè)排序的緩存中，我們稱(chēng)這個(gè)緩存為memtable；較早的更新存放在一系列SSTable中。為了恢復(fù)一個(gè)Tablet，Tablet服務(wù)器首先從METADATA表中讀取它的元數(shù)據(jù)。Tablet的元數(shù)據(jù)包含了組成這個(gè)Tablet的SSTable的列表，以及一系列的RedoPoint（alex注：asetofredopoints），這些RedoPoint指向可能含有該Tablet數(shù)據(jù)的已提交的日志記錄。Tablet服務(wù)器把SSTable的索引讀進(jìn)內(nèi)存，之后通過(guò)重復(fù)RedoPoint之后提交的更新來(lái)重建memtable。當(dāng)對(duì)Tablet服務(wù)器進(jìn)行寫(xiě)操作時(shí)，Tablet服務(wù)器首先要檢查這個(gè)操作格式是否正確、操作發(fā)起者是否有執(zhí)行這個(gè)操作的權(quán)限。權(quán)限驗(yàn)證的方法是通過(guò)從一個(gè)Chubby文件里讀取出來(lái)的具有寫(xiě)權(quán)限的操作者列表來(lái)進(jìn)行驗(yàn)證（這個(gè)文件幾乎一定會(huì)存放在Chubby客戶(hù)緩存里）。成功的修改操作會(huì)記錄在提交日志里。可以采用批量提交方式（alex注：groupcommit）來(lái)提高包含大量小的修改操作的應(yīng)用程序的吞吐量【13，16】。當(dāng)一個(gè)寫(xiě)操作提交后，寫(xiě)的內(nèi)容插入到memtable里面。當(dāng)對(duì)Tablet服務(wù)器進(jìn)行讀操作時(shí)，Tablet服務(wù)器會(huì)作類(lèi)似的完整性和權(quán)限檢查。一個(gè)有效的讀操作在一個(gè)由一系列SSTable和memtable合并的視圖里執(zhí)行。由于SSTable和memtable是按字典排序的數(shù)據(jù)結(jié)構(gòu)，因此可以高效生成合并視圖。當(dāng)進(jìn)行Tablet的合并和分割時(shí)，正在進(jìn)行的讀寫(xiě)操作能夠繼續(xù)進(jìn)行。(alex注：這個(gè)詞挺簡(jiǎn)單，但是在這節(jié)里面挺難翻譯的。應(yīng)該是空間縮減的意思，但是似乎又不能完全概括它在上下文中的意思，干脆，不翻譯了)隨著寫(xiě)操作的執(zhí)行，memtable的大小不斷增加。當(dāng)memtable的尺寸到達(dá)一個(gè)門(mén)限值的時(shí)候，這個(gè)memtable就會(huì)被凍結(jié)，然后創(chuàng)建一個(gè)新的memtable；被凍結(jié)住memtable會(huì)被轉(zhuǎn)換成SSTable，然后寫(xiě)入GFS（alex注：我們稱(chēng)這種Compaction行為為MinorCompaction）。MinorCompaction過(guò)程有兩個(gè)目的：shrink(alex注：shrink是數(shù)據(jù)庫(kù)用語(yǔ)，表示空間收縮)Tablet服務(wù)器使用的內(nèi)存，以及在服務(wù)器災(zāi)難恢復(fù)過(guò)程中，減少必須從提交日志里讀取的數(shù)據(jù)量。在Compaction過(guò)程中，正在進(jìn)行的讀寫(xiě)操作仍能繼續(xù)。每一次MinorCompaction都會(huì)創(chuàng)建一個(gè)新的SSTable。如果MinorCompaction過(guò)程不停滯的持續(xù)進(jìn)行下去，讀操作可能需要合并來(lái)自多個(gè)SSTable的更新；否則，我們通過(guò)定期在后臺(tái)執(zhí)行MergingCompaction過(guò)程合并文件，限制這類(lèi)文件的數(shù)量。MergingCompaction過(guò)程讀取一些SSTable和memtable的內(nèi)容，合并成一個(gè)新的SSTable。只要MergingCompaction過(guò)程完成了，輸入的這些SSTable和memtable就可以刪除了。合并所有的SSTable并生成一個(gè)新的SSTable的MergingCompaction過(guò)程叫作MajorCompaction。由非MajorCompaction產(chǎn)生的SSTable可能含有特殊的刪除條目，這些刪除條目能夠隱藏在舊的、但是依然有效的SSTable中已經(jīng)刪除的數(shù)據(jù)（alex注：令人費(fèi)解啊，原文是SSTablesproducedbynon-majorcompactionscancontainspecialdeletionentriesthatsuppressdeleteddatainolderSSTablesthatarestilllive）。而MajorCompaction過(guò)程生成的SSTable不包含已經(jīng)刪除的信息或數(shù)據(jù)。Bigtable循環(huán)掃描它所有的Tablet，并且定期對(duì)它們執(zhí)行MajorCompaction。MajorCompaction機(jī)制允許Bigtable回收已經(jīng)刪除的數(shù)據(jù)占有的資源，并且確保BigTable能及時(shí)清除已經(jīng)刪除的數(shù)據(jù)（alex注：實(shí)際是回收資源。數(shù)據(jù)刪除后，它占有的空間并不能馬上重復(fù)利用；只有空間回收后才能重復(fù)使用），這對(duì)存放敏感數(shù)據(jù)的服務(wù)是非常重要。上一章我們描述了Bigtable的實(shí)現(xiàn)，我們還需要很多優(yōu)化工作才能使Bigtable到達(dá)用戶(hù)要求的高性能、高可用性和高可靠性。本章描述了Bigtable實(shí)現(xiàn)的其它部分，為了更好的強(qiáng)調(diào)這些優(yōu)化工作，我們將深入細(xì)節(jié)。

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

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

壓縮客戶(hù)程序可以控制一個(gè)局部性群組的SSTable是否需要壓縮；如果需要壓縮，那么以什么格式來(lái)壓縮。每個(gè)SSTable的塊（塊的大小由局部性群組的優(yōu)化參數(shù)指定）都使用用戶(hù)指定的壓縮格式來(lái)壓縮。雖然分塊壓縮浪費(fèi)了少量空間（alex注：相比于對(duì)整個(gè)SSTable進(jìn)行壓縮，分塊壓縮壓縮率較低），但是，我們?cè)谥蛔x取SSTable的一小部分?jǐn)?shù)據(jù)的時(shí)候就不必解壓整個(gè)文件了。很多客戶(hù)程序使用了“兩遍”的、可定制的壓縮方式。第一遍采用Bentley

andMcIlroy’s方式[6]，這種方式在一個(gè)很大的掃描窗口里對(duì)常見(jiàn)的長(zhǎng)字符串進(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的例子里，我們使用這種壓縮方式來(lái)存儲(chǔ)網(wǎng)頁(yè)內(nèi)容。在一次測(cè)試中，我們?cè)谝粋€(gè)壓縮的局部性群組中存儲(chǔ)了大量的網(wǎng)頁(yè)。針對(duì)實(shí)驗(yàn)的目的，我們沒(méi)有存儲(chǔ)每個(gè)文檔所有版本的數(shù)據(jù)，我們僅僅存儲(chǔ)了一個(gè)版本的數(shù)據(jù)。該模式的空間壓縮比達(dá)到了10:1。這比傳統(tǒng)的Gzip在壓縮HTML頁(yè)面時(shí)3:1或者4:1的空間壓縮比好的多；“兩遍”的壓縮模式如此高效的原因是由于Webtable的行的存放方式：從同一個(gè)主機(jī)獲取的頁(yè)面都存在臨近的地方。利用這個(gè)特性，Bentley-McIlroy算法可以從來(lái)自同一個(gè)主機(jī)的頁(yè)面里找到大量的重復(fù)內(nèi)容。不僅僅是Webtable，其它的很多應(yīng)用程序也通過(guò)選擇合適的行名來(lái)將相似的數(shù)據(jù)聚簇在一起，以獲取較高的壓縮率。當(dāng)我們?cè)贐igtable中存儲(chǔ)同一份數(shù)據(jù)的多個(gè)版本的時(shí)候，壓縮效率會(huì)更高。通過(guò)緩存提高讀操作的性能為了提高讀操作的性能，Tablet服務(wù)器使用二級(jí)緩存的策略。掃描緩存是第一級(jí)緩存，主要緩存Tablet服務(wù)器通過(guò)SSTable接口獲取的Key-Value對(duì)；Block緩存是二級(jí)緩存，緩存的是從GFS讀取的SSTable的Block。對(duì)于經(jīng)常要重復(fù)讀取相同數(shù)據(jù)的應(yīng)用程序來(lái)說(shuō)，掃描緩存非常有效；對(duì)于經(jīng)常要讀取剛剛讀過(guò)的數(shù)據(jù)附近的數(shù)據(jù)的應(yīng)用程序來(lái)說(shuō)，Block緩存更有用（例如，順序讀，或者在一個(gè)熱點(diǎn)的行的局部性群組中隨機(jī)讀取不同的列)。Bloom過(guò)濾器(alex注：Bloom，又叫布隆過(guò)濾器，什么意思？請(qǐng)參考Google黑板報(bào)/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)存中，那么就需要多次訪(fǎng)問(wèn)硬盤(pán)。我們通過(guò)允許客戶(hù)程序?qū)μ囟ň植啃匀航M的SSTable指定Bloom過(guò)濾器【7】，來(lái)減少硬盤(pán)訪(fǎng)問(wèn)的次數(shù)。我們可以使用Bloom過(guò)濾器查詢(xún)一個(gè)SSTable是否包含了特定行和列的數(shù)據(jù)。對(duì)于某些特定應(yīng)用程序，我們只付出了少量的、用于存儲(chǔ)Bloom過(guò)濾器的內(nèi)存的代價(jià)，就換來(lái)了讀操作顯著減少的磁盤(pán)訪(fǎng)問(wèn)的次數(shù)。使用Bloom過(guò)濾器也隱式的達(dá)到了當(dāng)應(yīng)用程序訪(fǎng)問(wèn)不存在的行或列時(shí)，大多數(shù)時(shí)候我們都不需要訪(fǎng)問(wèn)硬盤(pán)的目的。Commit日志的實(shí)現(xiàn)如果我們把對(duì)每個(gè)Tablet的操作的Commit日志都存在一個(gè)單獨(dú)的文件的話(huà)，那么就會(huì)產(chǎn)生大量的文件，并且這些文件會(huì)并行的寫(xiě)入GFS。根據(jù)GFS服務(wù)器底層文件系統(tǒng)實(shí)現(xiàn)的方案，要把這些文件寫(xiě)入不同的磁盤(pán)日志文件時(shí)(alex注：different

physical

logfiles)，會(huì)有大量的磁盤(pán)Seek操作。另外，由于批量提交(alex注：groupcommit)中操作的數(shù)目一般比較少，因此，對(duì)每個(gè)Tablet設(shè)置單獨(dú)的日志文件也會(huì)給批量提交本應(yīng)具有的優(yōu)化效果帶來(lái)很大的負(fù)面影響。為了避免這些問(wèn)題，我們?cè)O(shè)置每個(gè)Tablet服務(wù)器一個(gè)Commit日志文件，把修改操作的日志以追加方式寫(xiě)入同一個(gè)日志文件，因此一個(gè)實(shí)際的日志文件中混合了對(duì)多個(gè)Tablet修改的日志記錄。使用單個(gè)日志顯著提高了普通操作的性能，但是將恢復(fù)的工作復(fù)雜化了。當(dāng)一個(gè)Tablet服務(wù)器宕機(jī)時(shí)，它加載的Tablet將會(huì)被移到很多其它的Tablet服務(wù)器上：每個(gè)Tablet服務(wù)器都裝載很少的幾個(gè)原來(lái)的服務(wù)器的Tablet。當(dāng)恢復(fù)一個(gè)Tablet的狀態(tài)的時(shí)候，新的Tablet服務(wù)器要從原來(lái)的Tablet服務(wù)器寫(xiě)的日志中提取修改操作的信息，并重新執(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，rowname，logsequencenumber）排序。排序之后，對(duì)同一個(gè)Tablet的修改操作的日志記錄就連續(xù)存放在了一起，因此，我們只要一次磁盤(pán)Seek操作、之后順序讀取就可以了。為了并行排序，我們先將日志分割成64MB的段，之后在不同的Tablet服務(wù)器對(duì)段進(jìn)行并行排序。這個(gè)排序工作由Master服務(wù)器來(lái)協(xié)同處理，并且在一個(gè)Tablet服務(wù)器表明自己需要從Commit日志文件恢復(fù)Tablet時(shí)開(kāi)始執(zhí)行。在向GFS中寫(xiě)Commit日志的時(shí)候可能會(huì)引起系統(tǒng)顛簸，原因是多種多樣的（比如，寫(xiě)操作正在進(jìn)行的時(shí)候，一個(gè)GFS服務(wù)器宕機(jī)了；或者連接三個(gè)GFS副本所在的服務(wù)器的網(wǎng)絡(luò)擁塞或者過(guò)載了）。為了確保在GFS負(fù)載高峰時(shí)修改操作還能順利進(jìn)行，每個(gè)Tablet服務(wù)器實(shí)際上有兩個(gè)日志寫(xiě)入線(xiàn)程，每個(gè)線(xiàn)程都寫(xiě)自己的日志文件，并且在任何時(shí)刻，只有一個(gè)線(xiàn)程是工作的。如果一個(gè)線(xiàn)程的在寫(xiě)入的時(shí)候效率很低，Tablet服務(wù)器就切換到另外一個(gè)線(xiàn)程，修改操作的日志記錄就寫(xiě)入到這個(gè)線(xiàn)程對(duì)應(yīng)的日志文件中。每個(gè)日志記錄都有一個(gè)序列號(hào)，因此，在恢復(fù)的時(shí)候，Tablet服務(wù)器能夠檢測(cè)出并忽略掉那些由于線(xiàn)程切換而導(dǎo)致的重復(fù)的記錄。Tablet恢復(fù)提速當(dāng)Master服務(wù)器將一個(gè)Tablet從一個(gè)Tablet服務(wù)器移到另外一個(gè)Tablet服務(wù)器時(shí)，源Tablet服務(wù)器會(huì)對(duì)這個(gè)Tablet做一次MinorCompaction。這個(gè)Compaction操作減少了Tablet服務(wù)器的日志文件中沒(méi)有歸并的記錄，從而減少了恢復(fù)的時(shí)間。Compaction完成之后，該服務(wù)器就停止為該Tablet提供服務(wù)。在卸載Tablet之前，源Tablet服務(wù)器還會(huì)再做一次（通常會(huì)很快）MinorCompaction，以消除前面在一次壓縮過(guò)程中又產(chǎn)生的未歸并的記錄。第二次MinorCompaction完成以后，Tablet就可以被裝載到新的Tablet服務(wù)器上了，并且不需要從日志中進(jìn)行恢復(fù)。

利用不變性我們?cè)谑褂肂igtable時(shí)，除了SSTable緩存之外的其它部分產(chǎn)生的SSTable都是不變的，我們可以利用這一點(diǎn)對(duì)系統(tǒng)進(jìn)行簡(jiǎn)化。例如，當(dāng)從SSTable讀取數(shù)據(jù)的時(shí)候，我們不必對(duì)文件系統(tǒng)訪(fǎng)問(wèn)操作進(jìn)行同步。這樣一來(lái)，就可以非常高效的實(shí)現(xiàn)對(duì)行的并行操作。memtable是唯一一個(gè)能被讀和寫(xiě)操作同時(shí)訪(fǎng)問(wèn)的可變數(shù)據(jù)結(jié)構(gòu)。為了減少在讀操作時(shí)的競(jìng)爭(zhēng)，我們對(duì)內(nèi)存表采用COW(Copy-on-write)機(jī)制，這樣就允許讀寫(xiě)操作并行執(zhí)行。因?yàn)镾STable是不變的，因此，我們可以把永久刪除被標(biāo)記為“刪除”的數(shù)據(jù)的問(wèn)題，轉(zhuǎn)換成對(duì)廢棄的SSTable進(jìn)行垃圾收集的問(wèn)題了。每個(gè)Tablet的SSTable都在METADATA表中注冊(cè)了。Master服務(wù)器采用“標(biāo)記-刪除”的垃圾回收方式刪除SSTable集合中廢棄的SSTable【25】，METADATA表則保存了RootSSTable的集合。最后，SSTable的不變性使得分割Tablet的操作非?？旖?。我們不必為每個(gè)分割出來(lái)的Tablet建立新的SSTable集合，而是共享原來(lái)的Tablet的SSTable集合。為了測(cè)試Bigtable的性能和可擴(kuò)展性，我們建立了一個(gè)包括N臺(tái)Tablet服務(wù)器的Bigtable集群，這里N是可變的。每臺(tái)Tablet服務(wù)器配置了1GB的內(nèi)存，數(shù)據(jù)寫(xiě)入到一個(gè)包括1786臺(tái)機(jī)器、每臺(tái)機(jī)器有2個(gè)IDE硬盤(pán)的GFS集群上。我們使用N臺(tái)客戶(hù)機(jī)生成工作負(fù)載測(cè)試Bigtable。（我們使用和Tablet服務(wù)器相同數(shù)目的客戶(hù)機(jī)以確保客戶(hù)機(jī)不會(huì)成為瓶頸。）每臺(tái)客戶(hù)機(jī)配置2GZ雙核Opteron處理器，配置了足以容納所有進(jìn)程工作數(shù)據(jù)集的物理內(nèi)存，以及一張Gigabit的以太網(wǎng)卡。這些機(jī)器都連入一個(gè)兩層的、樹(shù)狀的交換網(wǎng)絡(luò)里，在根節(jié)點(diǎn)上的帶寬加起來(lái)有大約100-200Gbps。所有的機(jī)器采用相同的設(shè)備，因此，任何兩臺(tái)機(jī)器間網(wǎng)絡(luò)來(lái)回一次的時(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)行客戶(hù)程序、要么運(yùn)行在測(cè)試過(guò)程中，使用這組機(jī)器的其它的任務(wù)啟動(dòng)的進(jìn)程。

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

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

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

掃描基準(zhǔn)測(cè)試和序列讀類(lèi)似，但是使用的是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ī)讀類(lèi)似，除了包含基準(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ù)和曲線(xiàn)是讀/寫(xiě)1000-bytevalue值時(shí)取得的。圖中的表格顯示了每個(gè)Tablet服務(wù)器每秒鐘進(jìn)行的操作的次數(shù)；圖中的曲線(xiàn)顯示了每秒種所有的Tablet服務(wù)器上操作次數(shù)的總和。

單個(gè)Tablet服務(wù)器的性能我們首先分析下單個(gè)Tablet服務(wù)器的性能。隨機(jī)讀的性能比其它操作慢一個(gè)數(shù)量級(jí)或以上（alex注：bytheorderofmagnitudeormore）

。每個(gè)隨機(jī)讀操作都要通過(guò)網(wǎng)絡(luò)從GFS傳輸64KB的SSTable到Tablet服務(wù)器，而我們只使用其中大小是1000byte的一個(gè)value值。Tablet服務(wù)器每秒大約執(zhí)行1200次讀操作，也就是每秒大約從GFS讀取75MB的數(shù)據(jù)。這個(gè)傳輸帶寬足以占滿(mǎn)Tablet服務(wù)器的CPU時(shí)間，因?yàn)槠渲邪司W(wǎng)絡(luò)協(xié)議棧的消耗、SSTable解析、以及BigTable代碼執(zhí)行；這個(gè)帶寬也足以占滿(mǎn)我們系統(tǒng)中網(wǎng)絡(luò)的鏈接帶寬。大多數(shù)采用這種訪(fǎng)問(wèn)模式BigTable應(yīng)用程序會(huì)減小Block的大小，通常會(huì)減到8KB。內(nèi)存中的隨機(jī)讀操作速度快很多，原因是，所有1000-byte的讀操作都是從Tablet服務(wù)器的本地內(nèi)存中讀取數(shù)據(jù)，不需要從GFS讀取64KB的Block。隨機(jī)和序列寫(xiě)操作的性能比隨機(jī)讀要好些，原因是每個(gè)Tablet服務(wù)器直接把寫(xiě)入操作的內(nèi)容追加到一個(gè)Commit日志文件的尾部，并且采用批量提交的方式，通過(guò)把數(shù)據(jù)以流的方式寫(xiě)入到GFS來(lái)提高性能。隨機(jī)寫(xiě)和序列寫(xiě)在性能上沒(méi)有太大的差異，這兩種方式的寫(xiě)操作實(shí)際上都是把操作內(nèi)容記錄到同一個(gè)Tablet服務(wù)器的Commit日志文件中。序列讀的性能好于隨機(jī)讀，因?yàn)槊咳〕?4KB的SSTable的Block后，這些數(shù)據(jù)會(huì)緩存到Block緩存中，后續(xù)的64次讀操作直接從緩存讀取數(shù)據(jù)。掃描的性能更高，這是由于客戶(hù)程序每一次RPC調(diào)用都會(huì)返回大量的value的數(shù)據(jù)，所以，RPC調(diào)用的消耗基本抵消了。性能提升隨著我們將系統(tǒng)中的Tablet服務(wù)器從1臺(tái)增加到500臺(tái)，系統(tǒng)的整體吞吐量有了夢(mèng)幻般的增長(zhǎng)，增長(zhǎng)的倍率超過(guò)了100。比如，隨著Tablet服務(wù)器的數(shù)量增加了500倍，內(nèi)存中的隨機(jī)讀操作的性能增加了300倍。之所以會(huì)有這樣的性能提升，主要是因?yàn)檫@個(gè)基準(zhǔn)測(cè)試的瓶頸是單臺(tái)Tablet服務(wù)器的CPU。盡管如此，性能的提升還不是線(xiàn)性的。在大多數(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注：theloadgeneratedbyourbenchmarksshiftsaroundasthebenchmarkprogresses）。隨機(jī)讀基準(zhǔn)測(cè)試的測(cè)試結(jié)果顯示，隨機(jī)讀的性能隨Tablet服務(wù)器數(shù)量增加的提升幅度最小（整體吞吐量只提升了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ù)器上的吞吐量急劇下降。截止到2006年8月，Google內(nèi)部一共有388個(gè)非測(cè)試用的Bigtable集群運(yùn)行在各種各樣的服務(wù)器集群上，合計(jì)大約有24500個(gè)Tablet服務(wù)器。表1顯示了每個(gè)集群上Tablet服務(wù)器的大致分布情況。這些集群中，許多用于開(kāi)發(fā)目的，因此會(huì)有一段時(shí)期比較空閑。通過(guò)觀(guān)察一個(gè)由14個(gè)集群、8069個(gè)Tablet服務(wù)器組成的集群組，我們看到整體的吞吐量超過(guò)了每秒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ǔ)的是用戶(hù)相關(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的。GoogleAnalytics是用來(lái)幫助Web站點(diǎn)的管理員分析他們網(wǎng)站的流量模式的服務(wù)。它提供了整體狀況的統(tǒng)計(jì)數(shù)據(jù)，比如每天的獨(dú)立訪(fǎng)問(wèn)的用戶(hù)數(shù)量、每天每個(gè)URL的瀏覽次數(shù)；它還提供了用戶(hù)使用網(wǎng)站的行為報(bào)告，比如根據(jù)用戶(hù)之前訪(fǎng)問(wèn)的某些頁(yè)面，統(tǒng)計(jì)出幾成的用戶(hù)購(gòu)買(mǎi)了商品。為了使用這個(gè)服務(wù)，Web站點(diǎn)的管理員只需要在他們的Web頁(yè)面中嵌入一小段JavaScript腳本就可以了。這個(gè)Javascript程序在頁(yè)面被訪(fǎng)問(wèn)的時(shí)候調(diào)用。它記錄了各種GoogleAnalytics需要使用的信息，比如用戶(hù)的標(biāo)識(shí)、獲取的網(wǎng)頁(yè)的相關(guān)信息。GoogleAnalytics匯總這些數(shù)據(jù)，之后提供給Web站點(diǎn)的管理員。我們粗略的描述一下GoogleAnalytics使用的兩個(gè)表。RowClick表（大約有200TB數(shù)據(jù)）的每一行存放了一個(gè)最終用戶(hù)的會(huì)話(huà)。行的名字是一個(gè)包含Web站點(diǎn)名字以及用戶(hù)會(huì)話(huà)創(chuàng)建時(shí)間的元組。這種模式保證了對(duì)同一個(gè)Web站點(diǎn)的訪(fǎng)問(wèn)會(huì)話(huà)是順序的，會(huì)話(huà)按時(shí)間順序存儲(chǔ)。這個(gè)表可以壓縮到原來(lái)尺寸的14%。Summary表（大約有20TB的數(shù)據(jù)）包含了關(guān)于每個(gè)Web站點(diǎn)的、各種類(lèi)型的預(yù)定義匯總信息。一個(gè)周期性運(yùn)行的MapReduce任務(wù)根據(jù)RawClick表的數(shù)據(jù)生成Summary表的數(shù)據(jù)。每個(gè)MapReduce工作進(jìn)程都從RawClick表中提取最新的會(huì)話(huà)數(shù)據(jù)。系統(tǒng)的整體吞吐量受限于GFS的吞吐量。這個(gè)表的能夠壓縮到原有尺寸的29%。Google通過(guò)一組服務(wù)為用戶(hù)提供了高分辨率的地球表面衛(wèi)星圖像，訪(fǎng)問(wèn)的方式可以使通過(guò)基于Web的GoogleMaps訪(fǎng)問(wèn)接口（），也可以通過(guò)GoogleEarth定制的客戶(hù)端軟件訪(fǎng)問(wèn)。這些軟件產(chǎn)品允許用戶(hù)瀏覽地球表面的圖像：用戶(hù)可以在不同的分辨率下平移、查看和注釋這些衛(wèi)星圖像。這個(gè)系統(tǒng)使用一個(gè)表存儲(chǔ)預(yù)處理數(shù)據(jù)，使用另外一組表存儲(chǔ)用戶(hù)數(shù)據(jù)。數(shù)據(jù)預(yù)處理流水線(xiàn)使用一個(gè)表存儲(chǔ)原始圖像。在預(yù)處理過(guò)程中，圖像被清除，圖像數(shù)據(jù)合并到最終的服務(wù)數(shù)據(jù)中。這個(gè)表包含了大約70TB的數(shù)據(jù)，所以需要從磁盤(pán)讀取數(shù)據(jù)。圖像已經(jīng)被高效壓縮過(guò)了，因此存儲(chǔ)在Bigtable后不需要再壓縮了。Imagery表的每一行都代表了一個(gè)單獨(dú)的地理區(qū)域。行都有名稱(chēng)，以確保毗鄰的區(qū)域存儲(chǔ)在了一起。Imagery表中有一個(gè)列族用來(lái)記錄每個(gè)區(qū)域的數(shù)據(jù)源。這個(gè)列族包含了大量的列：基本上市每個(gè)列對(duì)應(yīng)一個(gè)原始圖片的數(shù)據(jù)。由于每個(gè)地理區(qū)域都是由很少的幾張圖片構(gòu)成的，因此這個(gè)列族是非常稀疏的。數(shù)據(jù)預(yù)處理流水線(xiàn)高度依賴(lài)運(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è)表來(lái)索引GFS中的數(shù)據(jù)。這個(gè)表相對(duì)較小（大約是500GB），但是這個(gè)表必須在保證較低的響應(yīng)延時(shí)的前提下，針對(duì)每個(gè)數(shù)據(jù)中心，每秒處理幾萬(wàn)個(gè)查詢(xún)請(qǐng)求。因此，這個(gè)表必須在上百個(gè)Tablet服務(wù)器上存儲(chǔ)數(shù)據(jù)，并且使用in-memory的列族。個(gè)性化查詢(xún)（/psearch）是一個(gè)雙向服務(wù)；這個(gè)服務(wù)記錄用戶(hù)的查詢(xún)和點(diǎn)擊，涉及到各種Google的服務(wù)，比如Web查詢(xún)、圖像和新聞。用戶(hù)可以瀏覽他們查詢(xún)的歷史，重復(fù)他們之前的查詢(xún)和點(diǎn)擊；用戶(hù)也可以定制基于Google歷史使用習(xí)慣模式的個(gè)性化查詢(xún)結(jié)果。個(gè)性化查詢(xún)使用Bigtable存儲(chǔ)每個(gè)用戶(hù)的數(shù)據(jù)。每個(gè)用戶(hù)都有一個(gè)唯一的用戶(hù)id，每個(gè)用戶(hù)id和一個(gè)列名綁定。一個(gè)單獨(dú)的列族被用來(lái)存儲(chǔ)各種類(lèi)型的行為（比如，有個(gè)列族可能是用來(lái)存儲(chǔ)所有的Web查詢(xún)的）。每個(gè)數(shù)據(jù)項(xiàng)都被用作Bigtable的時(shí)間戳，記錄了相應(yīng)的用戶(hù)行為發(fā)生的時(shí)間。個(gè)性化查詢(xún)使用以Bigtable為存儲(chǔ)的MapReduce任務(wù)生成用戶(hù)的數(shù)據(jù)圖表。這些用戶(hù)數(shù)據(jù)圖表用來(lái)個(gè)性化當(dāng)前的查詢(xún)結(jié)果。個(gè)性化查詢(xún)的數(shù)據(jù)會(huì)復(fù)制到幾個(gè)Bigtable的集群上，這樣就增強(qiáng)了數(shù)據(jù)可用性，同時(shí)減少了由客戶(hù)端和Bigtable集群間的“距離”造成的延時(shí)。個(gè)性化查詢(xún)的開(kāi)發(fā)團(tuán)隊(duì)最初建立了一個(gè)基于Bigtable的、“客戶(hù)側(cè)”的復(fù)制機(jī)制為所有的復(fù)制節(jié)點(diǎn)提供一致性保障。現(xiàn)在的系統(tǒng)則使用了內(nèi)建的復(fù)制子系統(tǒng)。個(gè)性化查詢(xún)存儲(chǔ)系統(tǒng)的設(shè)計(jì)允許其它的團(tuán)隊(duì)在它們自己的列中加入新的用戶(hù)數(shù)據(jù)，因此，很多Google服務(wù)使用個(gè)性化查詢(xún)存儲(chǔ)系統(tǒng)保存用戶(hù)級(jí)的配置參數(shù)和設(shè)置。在多個(gè)團(tuán)隊(duì)之間分享數(shù)據(jù)的結(jié)果是產(chǎn)生了大量的列族。為了更好的支持?jǐn)?shù)據(jù)共享，我們加入了一個(gè)簡(jiǎn)單的配額機(jī)制(alex注：quota，參考AIX的配額機(jī)制)限制用戶(hù)在共享表中使用的空間；配額也為使用個(gè)性化查詢(xún)系統(tǒng)存儲(chǔ)用戶(hù)級(jí)信息的產(chǎn)品團(tuán)體提供了隔離機(jī)制。在設(shè)計(jì)、實(shí)現(xiàn)、維護(hù)和支持Bigtable的過(guò)程中，我們得到了很多有用的經(jīng)驗(yàn)和一些有趣的教訓(xùn)。一個(gè)教訓(xùn)是，我們發(fā)現(xiàn)，很多類(lèi)型的錯(cuò)誤都會(huì)導(dǎo)致大型分布式系統(tǒng)受損，這些錯(cuò)誤不僅僅是通常的網(wǎng)絡(luò)中斷、或者很多分布式協(xié)議中設(shè)想的fail-stop類(lèi)型的錯(cuò)誤（alex注：fail-stopfailture，指一旦系統(tǒng)fail就stop，不輸出任何數(shù)據(jù)；fail-fastfailture，指fail不馬上stop，在短時(shí)間內(nèi)return錯(cuò)誤信息，然后再stop）。比如，我們遇到過(guò)下面這些類(lèi)型的錯(cuò)誤導(dǎo)致的問(wèn)題：內(nèi)存數(shù)據(jù)損壞、網(wǎng)絡(luò)中斷、時(shí)鐘偏差、機(jī)器掛起、擴(kuò)展的和非對(duì)稱(chēng)的網(wǎng)絡(luò)分區(qū)（alex注：extendedandasymmetricnetworkpartitions，不明白什么意思。partition也有中斷的意思，但是我不知道如何用在這里）、我們使用的其它系統(tǒng)的Bug（比如Chubby）、GFS配額溢出、計(jì)劃內(nèi)和計(jì)劃外的硬件維護(hù)。我們?cè)诮鉀Q這些問(wèn)題的過(guò)程中學(xué)到了很多經(jīng)驗(yàn)，我們通過(guò)修改協(xié)議來(lái)解決這些問(wèn)題。比如，我們?cè)谖覀兊腞PC機(jī)制中加入了Checksum。我們?cè)谠O(shè)計(jì)系統(tǒng)的部分功能時(shí)，不對(duì)其它部分功能做任何的假設(shè)，這樣的做法解決了其它的一些問(wèn)題。比如，我們不再假設(shè)一個(gè)特定的Chubby操作只返回錯(cuò)誤碼集合中的一個(gè)值。另外一個(gè)教訓(xùn)是，我們明白了在徹底了解一個(gè)新特性會(huì)被如何使用之后，再?zèng)Q定是否添加這個(gè)新特性是非常重要的。比如，我們開(kāi)始計(jì)劃在我們的API中支持通常方式的事務(wù)處理。但是由于我們還不會(huì)馬上用到這個(gè)功能，因此，我們并沒(méi)有去實(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ī)制去滿(mǎn)足這個(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的客戶(hù)程序）。比如，我們擴(kuò)展了我們的RPC系統(tǒng)，因此對(duì)于一個(gè)RPC調(diào)用的例子，它可以詳細(xì)記錄代表了RPC調(diào)用的很多重要操作。這個(gè)特性允許我們檢測(cè)和修正很多的問(wèn)題，比如Tablet數(shù)據(jù)結(jié)構(gòu)上的鎖的內(nèi)容、在修改操作提交時(shí)對(duì)GFS的寫(xiě)入非常慢的問(wèn)題、以及在METADATA表的Tablet不可用時(shí)，對(duì)METADATA表的訪(fǎng)問(wèn)掛起的問(wèn)題。關(guān)于監(jiān)控的用途的另外一個(gè)例子是，每個(gè)Bigtable集群都在Chubby中注冊(cè)了。這可以幫助我們跟蹤所有的集群狀態(tài)、監(jiān)控它們的大小、檢查集群運(yùn)行的我們軟件的版本、監(jiān)控集群流入數(shù)據(jù)的流量，以及檢查是否有引發(fā)集群高延時(shí)的潛在因素。對(duì)我們來(lái)說(shuō)，最寶貴的經(jīng)驗(yàn)是簡(jiǎn)單設(shè)計(jì)的價(jià)值。考慮到我們系統(tǒng)的代碼量（大約100000行生產(chǎn)代碼（alex注：non-testcode）），以及隨著時(shí)間的推移，新的代碼以各種難以預(yù)料的方式加入系統(tǒng)，我們發(fā)現(xiàn)簡(jiǎn)潔的設(shè)計(jì)和編碼給維護(hù)和調(diào)試帶來(lái)的巨大好處。這方面的一個(gè)例子是我們的Tablet服務(wù)器成員協(xié)議。我們第一版的協(xié)議很簡(jiǎn)單：Master服務(wù)器周期性的和Tablet服務(wù)器簽訂租約，Tablet服務(wù)器在租約過(guò)期的時(shí)候Kill掉自己的進(jìn)程。不幸的是，這個(gè)協(xié)議在遇到網(wǎng)絡(luò)問(wèn)題時(shí)會(huì)大大降低系統(tǒng)的可用性，也會(huì)大大增加Master服務(wù)器恢復(fù)的時(shí)間。我們多次重新設(shè)計(jì)這個(gè)協(xié)議，直到它能夠很好的處理上述問(wèn)題。但是，更不幸的是，最終的協(xié)議過(guò)于復(fù)雜了，并且依賴(lài)一些Chubby很少被用到的特性。我們發(fā)現(xiàn)我們浪費(fèi)了大量的時(shí)間在調(diào)試一些古怪的問(wèn)題(alex注：obscurecornercases)，有些是Bigtable代碼的問(wèn)題，有些事Chubby代碼的問(wèn)題。最后，我們只好廢棄了這個(gè)協(xié)議，重新制訂了一個(gè)新的、更簡(jiǎn)單、只使用Chubby最廣泛使用的特性的協(xié)議。Boxwood【24】項(xiàng)目的有些組件在某些方面和Chubby、GFS以及Bigtable類(lèi)似，因?yàn)樗蔡峁┝酥T如分布式協(xié)議、鎖、分布式Chu