Bigtable：一個分布式的結(jié)構(gòu)化數(shù)據(jù)存儲系統(tǒng)譯者：alex
摘要Bigtable是一個分布式的結(jié)構(gòu)化數(shù)據(jù)存儲系統(tǒng),，它被設計用來處理海量數(shù)據(jù)：通常是分布在數(shù)千臺普通服務器上的PB級的數(shù)據(jù)。Google
的很多項目使用Bigtable存儲數(shù)據(jù),，包括Web索引,、Google Earth、Google
Finance,。這些應用對Bigtable提出的要求差異非常大,，無論是在數(shù)據(jù)量上（從URL到網(wǎng)頁到衛(wèi)星圖像）還是在響應速度上（從后端的批量處理到
實時數(shù)據(jù)服務）。盡管應用需求差異很大,，但是,，針對Google的這些產(chǎn)品，Bigtable還是成功的提供了一個靈活的,、高性能的解決方案,。本論文描述
了Bigtable提供的簡單的數(shù)據(jù)模型，利用這個模型,，用戶可以動態(tài)的控制數(shù)據(jù)的分布和格式,；我們還將描述Bigtable的設計和實現(xiàn)。
1 介紹在過去兩年半時間里,，我們設計,、實現(xiàn)并部署了一個分布式的結(jié)構(gòu)化數(shù)據(jù)存儲系統(tǒng) —
在Google，我們稱之為Bigtable,。Bigtable的設計目的是可靠的處理PB級別的數(shù)據(jù),，并且能夠部署到上千臺機器上。Bigtable已
經(jīng)實現(xiàn)了下面的幾個目標：適用性廣泛,、可擴展,、高性能和高可用性。Bigtable已經(jīng)在超過60個Google的產(chǎn)品和項目上得到了應用,，包括
Google Analytics,、Google Finance、Orkut,、Personalized Search,、Writely和Google
Earth。這些產(chǎn)品對Bigtable提出了迥異的需求,，有的需要高吞吐量的批處理,，有的則需要及時響應，快速返回數(shù)據(jù)給最終用戶,。它們使用的
Bigtable集群的配置也有很大的差異,，有的集群只有幾臺服務器,，而有的則需要上千臺服務器、存儲幾百TB的數(shù)據(jù),。
在很多方面,，Bigtable和數(shù)據(jù)庫很類似：它使用了很多數(shù)據(jù)庫的實現(xiàn)策略。并行數(shù)據(jù)庫【14】和內(nèi)存數(shù)據(jù)庫【13】已經(jīng)具備可擴展性和高性
能,，但是Bigtable提供了一個和這些系統(tǒng)完全不同的接口,。Bigtable不支持完整的關系數(shù)據(jù)模型；與之相反,，Bigtable為客戶提供了簡單
的數(shù)據(jù)模型,，利用這個模型，客戶可以動態(tài)控制數(shù)據(jù)的分布和格式（alex注：也就是對BigTable而言,，數(shù)據(jù)是沒有格式的,，用數(shù)據(jù)庫領域的術語說，就是數(shù)據(jù)沒有Schema,，用戶自己去定義Schema）,，用戶也可以自己推測(alex注：reason about)底層存儲數(shù)據(jù)的位置相關性(alex注：位置相關性可以這樣理解，比如樹狀結(jié)構(gòu),，具有相同前綴的數(shù)據(jù)的存放位置接近,。在讀取的時候，可以把這些數(shù)據(jù)一次讀取出來),。
數(shù)據(jù)的下標是行和列的名字,，名字可以是任意的字符串。Bigtable將存儲的數(shù)據(jù)都視為字符串,，但是Bigtable本身不去解析這些字符串,，客戶程序
通常會在把各種結(jié)構(gòu)化或者半結(jié)構(gòu)化的數(shù)據(jù)串行化到這些字符串里。通過仔細選擇數(shù)據(jù)的模式,，客戶可以控制數(shù)據(jù)的位置相關性,。最后,，可以通過BigTable
的模式參數(shù)來控制數(shù)據(jù)是存放在內(nèi)存中,、還是硬盤上。
第二節(jié)描述關于數(shù)據(jù)模型更多細節(jié)方面的東西,；第三節(jié)概要介紹了客戶端API,；第四節(jié)簡要介紹了BigTable底層使用的Google的基礎框架；第五節(jié)
描述了BigTable實現(xiàn)的關鍵部分,；第6節(jié)描述了我們?yōu)榱颂岣連igTable的性能采用的一些精細的調(diào)優(yōu)方法,；第7節(jié)提供了BigTable的性能
數(shù)據(jù)；第8節(jié)講述了幾個Google內(nèi)部使用BigTable的例子,；第9節(jié)是我們在設計和后期支持過程中得到一些經(jīng)驗和教訓,；最后,，在第10節(jié)列出我們
的相關研究工作，第11節(jié)是我們的結(jié)論,。
2 數(shù)據(jù)模型Bigtable是一個稀疏的,、分布式的、持久化存儲的多維度排序Map（alex注：對于程序員來說,，Map應該不用翻譯了吧,。Map由key和value組成，后面我們直接使用key和value,，不再另外翻譯了）,。Map的索引是行關鍵字、列關鍵字以及時間戳,；Map中的每個value都是一個未經(jīng)解析的byte數(shù)組,。
(row:string, column:string,time:int64)->string 我們在仔細分析了一個類似Bigtable的系統(tǒng)的種種潛在用途之后，決定使用這個數(shù)據(jù)模型,。我們先舉個具體的例子,，這個例子促使我們做了很多
設計決策；假設我們想要存儲海量的網(wǎng)頁及相關信息,，這些數(shù)據(jù)可以用于很多不同的項目,，我們姑且稱這個特殊的表為Webtable。在Webtable里,，
我們使用URL作為行關鍵字,，使用網(wǎng)頁的某些屬性作為列名，網(wǎng)頁的內(nèi)容存在“contents:”列中,，并用獲取該網(wǎng)頁的時間戳作為標識(alex注：即按照獲取時間不同,，存儲了多個版本的網(wǎng)頁數(shù)據(jù))，如圖一所示,。
圖一：一個存儲Web網(wǎng)頁的例子的表的片斷,。行名是一個反向URL。contents列族存放的是網(wǎng)頁的內(nèi)容,，anchor列族存放引用該網(wǎng)頁的錨鏈接文本（alex注：如果不知道HTML的Anchor,，請Google一把）。CNN的主頁被Sports Illustrater和MY-look的主頁引用,，因此該行包含了名為“anchor:cnnsi.com”和 “anchhor:my.look.ca”的列,。每個錨鏈接只有一個版本（alex注：注意時間戳標識了列的版本，t9和t8分別標識了兩個錨鏈接的版本）,；而contents列則有三個版本,，分別由時間戳t3，t5,，和t6標識,。
行 表中的行關鍵字可以是任意的字符串（目前支持最大64KB的字符串,，但是對大多數(shù)用戶，10-100個字節(jié)就足夠了）,。對同一個行關鍵字的讀或
者寫操作都是原子的（不管讀或者寫這一行里多少個不同列）,，這個設計決策能夠使用戶很容易的理解程序在對同一個行進行并發(fā)更新操作時的行為。
Bigtable通過行關鍵字的字典順序來組織數(shù)據(jù),。表中的每個行都可以動態(tài)分區(qū),。每個分區(qū)叫做一個”Tablet”，Tablet是數(shù)據(jù)分布
和負載均衡調(diào)整的最小單位,。這樣做的結(jié)果是,，當操作只讀取行中很少幾列的數(shù)據(jù)時效率很高，通常只需要很少幾次機器間的通信即可完成,。用戶可以通過選擇合適
的行關鍵字,，在數(shù)據(jù)訪問時有效利用數(shù)據(jù)的位置相關性，從而更好的利用這個特性,。舉例來說,，在Webtable里，通過反轉(zhuǎn)URL中主機名的方式,，可以把同
一個域名下的網(wǎng)頁聚集起來組織成連續(xù)的行,。具體來說，我們可以把maps.google.com/index.html的數(shù)據(jù)存放在關鍵字
com.google.maps/index.html下,。把相同的域中的網(wǎng)頁存儲在連續(xù)的區(qū)域可以讓基于主機和域名的分析更加有效,。
列族 列關鍵字組成的集合叫做“列族“，列族是訪問控制的基本單位,。存放在同一列族下的所有數(shù)據(jù)通常都屬于同一個類型（我們可以把同一個列族下的數(shù)據(jù)壓縮 在一起）,。列族在使用之前必須先創(chuàng)建，然后才能在列族中任何的列關鍵字下存放數(shù)據(jù),；列族創(chuàng)建后,，其中的任何一個列關鍵字下都可以存放數(shù)據(jù)。根據(jù)我們的設計 意圖,，一張表中的列族不能太多（最多幾百個）,，并且列族在運行期間很少改變。與之相對應的,，一張表可以有無限多個列,。 列關鍵字的命名語法如下：列族：限定詞。 列族的名字必須是可打印的字符串,，而限定詞的名字可以是任意的字符串。比如,，Webtable有個列族language,，language列族用來存放撰 寫網(wǎng)頁的語言,。我們在language列族中只使用一個列關鍵字，用來存放每個網(wǎng)頁的語言標識ID,。Webtable中另一個有用的列族是anchor,； 這個列族的每一個列關鍵字代表一個錨鏈接，如圖一所示,。Anchor列族的限定詞是引用該網(wǎng)頁的站點名,；Anchor列族每列的數(shù)據(jù)項存放的是鏈接文本。 訪問控制,、磁盤和內(nèi)存的使用統(tǒng)計都是在列族層面進行的,。在我們的Webtable的例子中，上述的控制權(quán)限能幫助我們管理不同類型的應用：我們允許 一些應用可以添加新的基本數(shù)據(jù),、一些應用可以讀取基本數(shù)據(jù)并創(chuàng)建繼承的列族,、一些應用則只允許瀏覽數(shù)據(jù)（甚至可能因為隱私的原因不能瀏覽所有數(shù)據(jù)）。 時間戳 在Bigtable中,，表的每一個數(shù)據(jù)項都可以包含同一份數(shù)據(jù)的不同版本,；不同版本的數(shù)據(jù)通過時間戳來索引。Bigtable時間戳的類型是64位 整型,。Bigtable可以給時間戳賦值,，用來表示精確到毫秒的“實時”時間；用戶程序也可以給時間戳賦值,。如果應用程序需要避免數(shù)據(jù)版本沖突,，那么它必 須自己生成具有唯一性的時間戳。數(shù)據(jù)項中,，不同版本的數(shù)據(jù)按照時間戳倒序排序,，即最新的數(shù)據(jù)排在最前面。 為了減輕多個版本數(shù)據(jù)的管理負擔,，我們對每一個列族配有兩個設置參數(shù),，Bigtable通過這兩個參數(shù)可以對廢棄版本的數(shù)據(jù)自動進行垃圾收集。用戶可以指定只保存最后n個版本的數(shù)據(jù),，或者只保存“足夠新”的版本的數(shù)據(jù)（比如,，只保存最近7天的內(nèi)容寫入的數(shù)據(jù)）。 在Webtable的舉例里,，contents:列存儲的時間戳信息是網(wǎng)絡爬蟲抓取一個頁面的時間,。上面提及的垃圾收集機制可以讓我們只保留最近三個版本的網(wǎng)頁數(shù)據(jù)。
3 APIBigtable提供了建立和刪除表以及列族的API函數(shù),。Bigtable還提供了修改集群,、表和列族的元數(shù)據(jù)的API，比如修改訪問權(quán)限,。
客戶程序可以對Bigtable進行如下的操作：寫入或者刪除Bigtable中的值,、從每個行中查找值,、或者遍歷表中的一個數(shù)據(jù)子集。圖2中
的Ｃ++代碼使用RowMutation抽象對象進行了一系列的更新操作,。（為了保持示例代碼的簡潔,，我們忽略了一些細節(jié)相關代碼）。調(diào)用Apply函數(shù)
對Ｗebtable進行了一個原子修改操作：它為www.增加了一個錨點,，同時刪除了另外一個錨點,。
圖3中的C++代碼使用Scanner抽象對象遍歷一個行內(nèi)的所有錨點?？蛻舫绦蚩梢员闅v多個列族,，有幾種方法可以對掃描輸出的行、列和時間戳進行 限制,。例如,，我們可以限制上面的掃描，讓它只輸出那些匹配正則表達式*.的錨點,，或者那些時間戳在當前時間前10天的錨點,。 Bigtable還支持一些其它的特性，利用這些特性,，用戶可以對數(shù)據(jù)進行更復雜的處理,。首先，Bigtable支持單行上的事務處理,，利用這個功 能,，用戶可以對存儲在一個行關鍵字下的數(shù)據(jù)進行原子性的讀-更新-寫操作。雖然Bigtable提供了一個允許用戶跨行批量寫入數(shù)據(jù)的接口,，但 是,，Bigtable目前還不支持通用的跨行事務處理。其次,，Bigtable允許把數(shù)據(jù)項用做整數(shù)計數(shù)器,。最后，Bigtable允許用戶在服務器的地 址空間內(nèi)執(zhí)行腳本程序,。腳本程序使用Google開發(fā)的Sawzall【28】數(shù)據(jù)處理語言,。雖然目前我們基于的Sawzall語言的API函數(shù)還不允許 客戶的腳本程序?qū)懭霐?shù)據(jù)到Bigtable，但是它允許多種形式的數(shù)據(jù)轉(zhuǎn)換,、基于任意表達式的數(shù)據(jù)過濾,、以及使用多種操作符的進行數(shù)據(jù)匯總。 Bigtable可以和MapReduce【12】一起使用,，MapReduce是Google開發(fā)的大規(guī)模并行計算框架,。我們已經(jīng)開發(fā)了一些Wrapper類，通過使用這些Wrapper類，Bigtable可以作為MapReduce框架的輸入和輸出,。
4 BigTable構(gòu)件Bigtable是建立在其它的幾個Google基礎構(gòu)件上的,。BigTable使用Google的分布式文件系統(tǒng)(GFS)【17】存儲日志
文件和數(shù)據(jù)文件,。BigTable集群通常運行在一個共享的機器池中,，池中的機器還會運行其它的各種各樣的分布式應用程序，BigTable的進程經(jīng)常要
和其它應用的進程共享機器,。BigTable依賴集群管理系統(tǒng)來調(diào)度任務,、管理共享的機器上的資源、處理機器的故障,、以及監(jiān)視機器的狀態(tài),。
BigTable內(nèi)部存儲數(shù)據(jù)的文件是Google
SSTable格式的。SSTable是一個持久化的,、排序的,、不可更改的Map結(jié)構(gòu)，而Map是一個key-value映射的數(shù)據(jù)結(jié)構(gòu),，key和
value的值都是任意的Byte串,。可以對SSTable進行如下的操作：查詢與一個key值相關的value,，或者遍歷某個key值范圍內(nèi)的所有的
key-value對,。從內(nèi)部看，SSTable是一系列的數(shù)據(jù)塊（通常每個塊的大小是64KB,，這個大小是可以配置的）,。SSTable使用塊索引（通
常存儲在SSTable的最后）來定位數(shù)據(jù)塊；在打開SSTable的時候,，索引被加載到內(nèi)存,。每次查找都可以通過一次磁盤搜索完成：首先使用二分查找法
在內(nèi)存中的索引里找到數(shù)據(jù)塊的位置，然后再從硬盤讀取相應的數(shù)據(jù)塊,。也可以選擇把整個SSTable都放在內(nèi)存中,，這樣就不必訪問硬盤了。
BigTable還依賴一個高可用的,、序列化的分布式鎖服務組件,，叫做Chubby【8】。一個Chubby服務包括了5個活動的副本,，其中的
一個副本被選為Master,，并且處理請求。只有在大多數(shù)副本都是正常運行的,，并且彼此之間能夠互相通信的情況下,，Chubby服務才是可用的。當有副本
失效的時候，Chubby使用Paxos算法【9,23】來保證副本的一致性,。Chubby提供了一個名字空間,，里面包括了目錄和小文件。每個目錄或者文
件可以當成一個鎖,，讀寫文件的操作都是原子的,。Chubby客戶程序庫提供對Chubby文件的一致性緩存。每個Chubby客戶程序都維護一個與
Chubby服務的會話,。如果客戶程序不能在租約到期的時間內(nèi)重新簽訂會話的租約,，這個會話就過期失效了(alex注：又用到了lease。原文是：A client’s session expires if it is unable to renew its session lease within the lease expiration time.),。當一個會話失效時,，它擁有的鎖和打開的文件句柄都失效了。Chubby客戶程序可以在文件和目錄上注冊回調(diào)函數(shù),，當文件或目錄改變,、或者會話過期時，回調(diào)函數(shù)會通知客戶程序,。
Bigtable使用Chubby完成以下的幾個任務：確保在任何給定的時間內(nèi)最多只有一個活動的Master副本,；存儲BigTable數(shù)據(jù)
的自引導指令的位置（參考5.1節(jié)）；查找Tablet服務器,，以及在Tablet服務器失效時進行善后（5.2節(jié)）,；存儲BigTable的模式信息
（每張表的列族信息）；以及存儲訪問控制列表,。如果Chubby長時間無法訪問,，BigTable就會失效。最近我們在使用11個Chubby服務實例的
14個BigTable集群上測量了這個影響,。由于Chubby不可用而導致BigTable中的部分數(shù)據(jù)不能訪問的平均比率是0.0047%
（Chubby不能訪問的原因可能是Chubby本身失效或者網(wǎng)絡問題）,。單個集群里，受Chubby失效影響最大的百分比是0.0326%（alex注：有點莫名其妙,，原文是： The percentage for the single cluster that was most affected by Chubby unavailability was 0.0326%.）,。
5 介紹Bigtable包括了三個主要的組件：鏈接到客戶程序中的庫、一個Master服務器和多個Tablet服務器,。針對系統(tǒng)工作負載的變化情況,，BigTable可以動態(tài)的向集群中添加（或者刪除）Tablet服務器。
Master服務器主要負責以下工作：為Tablet服務器分配Tablets,、檢測新加入的或者過期失效的Table服務器,、對Tablet服務器進行負載均衡、以及對保存在GFS上的文件進行垃圾收集,。除此之外,，它還處理對模式的相關修改操作，例如建立表和列族。
每個Tablet服務器都管理一個Tablet的集合（通常每個服務器有大約數(shù)十個至上千個Tablet）,。每個Tablet服務器負責處理它所加載的Tablet的讀寫操作,，以及在Tablets過大時，對其進行分割,。
和很多Single-Master類型的分布式存儲系統(tǒng)【17.21】類似,，客戶端讀取的數(shù)據(jù)都不經(jīng)過Master服務器：客戶程序直接和
Tablet服務器通信進行讀寫操作。由于BigTable的客戶程序不必通過Master服務器來獲取Tablet的位置信息,，因此,，大多數(shù)客戶程序甚
至完全不需要和Master服務器通信,。在實際應用中,，Master服務器的負載是很輕的。
一個BigTable集群存儲了很多表,，每個表包含了一個Tablet的集合,，而每個Tablet包含了某個范圍內(nèi)的行的所有相關數(shù)據(jù)。初始狀
態(tài)下,，一個表只有一個Tablet,。隨著表中數(shù)據(jù)的增長，它被自動分割成多個Tablet,，缺省情況下,，每個Tablet的尺寸大約是100MB到
200MB。
5.1 Tablet的位置我們使用一個三層的,、類似Ｂ+樹[10]的結(jié)構(gòu)存儲Tablet的位置信息(如圖4),。
 第一層是一個存儲在Chubby中的文件，它包含了Root Tablet的位置信息,。Root Tablet包含了一個特殊的METADATA表里所有的Tablet的位置信息,。METADATA表的每個Tablet包含了一個用戶Tablet的集 合。Root Tablet實際上是METADATA表的第一個Tablet,，只不過對它的處理比較特殊 — Root Tablet永遠不會被分割 — 這就保證了Tablet的位置信息存儲結(jié)構(gòu)不會超過三層,。 在METADATA表里面，每個Tablet的位置信息都存放在一個行關鍵字下面,，而這個行關鍵字是由Tablet所在的表的標識符和Tablet 的最后一行編碼而成的,。METADATA的每一行都存儲了大約1KB的內(nèi)存數(shù)據(jù)。在一個大小適中的,、容量限制為128MB的METADATA Tablet中,，采用這種三層結(jié)構(gòu)的存儲模式，可以標識2^34個Tablet的地址（如果每個Tablet存儲128MB數(shù)據(jù),，那么一共可以存儲 2^61字節(jié)數(shù)據(jù)）,。 客戶程序使用的庫會緩存Tablet的位置信息。如果客戶程序沒有緩存某個Tablet的地址信息，或者發(fā)現(xiàn)它緩存的地址信息不正確,，客戶程序就在 樹狀的存儲結(jié)構(gòu)中遞歸的查詢Tablet位置信息,；如果客戶端緩存是空的，那么尋址算法需要通過三次網(wǎng)絡來回通信尋址,，這其中包括了一次Chubby讀操 作,；如果客戶端緩存的地址信息過期了，那么尋址算法可能需要最多６次網(wǎng)絡來回通信才能更新數(shù)據(jù),，因為只有在緩存中沒有查到數(shù)據(jù)的時候才能發(fā)現(xiàn)數(shù)據(jù)過期（alex注：其中的三次通信發(fā)現(xiàn)緩存過期,，另外三次更新緩存數(shù)據(jù)）(假 設METADATA的Tablet沒有被頻繁的移動）。盡管Tablet的地址信息是存放在內(nèi)存里的,，對它的操作不必訪問GFS文件系統(tǒng),，但是，通常我們 會通過預取Tablet地址來進一步的減少訪問的開銷：每次需要從METADATA表中讀取一個Tablet的元數(shù)據(jù)的時候,，它都會多讀取幾個 Tablet的元數(shù)據(jù),。 在METADATA表中還存儲了次級信息(alex注：secondary information)，包括每個Tablet的事件日志（例如,，什么時候一個服務器開始為該Tablet提供服務）,。這些信息有助于排查錯誤和性能分析。 5.2 Tablet分配在任何一個時刻,，一個Tablet只能分配給一個Tablet服務器,。Master服務器記錄了當前有哪些活躍的Tablet服務器、哪些 Tablet分配給了哪些Tablet服務器,、哪些Tablet還沒有被分配,。當一個Tablet還沒有被分配、并且剛好有一個Tablet服務器有足夠 的空閑空間裝載該Tablet時,，Master服務器會給這個Tablet服務器發(fā)送一個裝載請求,，把Tablet分配給這個服務器。 BigTable使用Chubby跟蹤記錄Tablet服務器的狀態(tài),。當一個Tablet服務器啟動時,，它在Chubby的一個指定目錄下建立一個 有唯一性名字的文件，并且獲取該文件的獨占鎖,。Master服務器實時監(jiān)控著這個目錄（服務器目錄）,，因此Master服務器能夠知道有新的Tablet 服務器加入了。如果Tablet服務器丟失了Chubby上的獨占鎖 — 比如由于網(wǎng)絡斷開導致Tablet服務器和Chubby的會話丟失 — 它就停止對Tablet提供服務,。（Chubby提供了一種高效的機制,，利用這種機制，Tablet服務器能夠在不增加網(wǎng)絡負擔的情況下知道它是否還持有 鎖）,。只要文件還存在,，Tablet服務器就會試圖重新獲得對該文件的獨占鎖,；如果文件不存在了，那么Tablet服務器就不能再提供服務了,，它會自行退 出（alex注：so it kills itself）,。當Tablet服務器終止時（比如，集群的管理系統(tǒng)將運行該Tablet服務器的主機從集群中移除）,，它會嘗試釋放它持有的文件鎖,，這樣一來，Master服務器就能盡快把Tablet分配到其它的Tablet服務器,。 Master服務器負責檢查一個Tablet服務器是否已經(jīng)不再為它的Tablet提供服務了,，并且要盡快重新分配它加載的Tablet。 Master服務器通過輪詢Tablet服務器文件鎖的狀態(tài)來檢測何時Tablet服務器不再為Tablet提供服務,。如果一個Tablet服務器報告它 丟失了文件鎖,，或者Master服務器最近幾次嘗試和它通信都沒有得到響應，Master服務器就會嘗試獲取該Tablet服務器文件的獨占鎖,；如果 Master服務器成功獲取了獨占鎖,，那么就說明Chubby是正常運行的，而Tablet服務器要么是宕機了,、要么是不能和Chubby通信了，因 此,，Master服務器就刪除該Tablet服務器在Chubby上的服務器文件以確保它不再給Tablet提供服務,。一旦Tablet服務器在 Chubby上的服務器文件被刪除了，Master服務器就把之前分配給它的所有的Tablet放入未分配的Tablet集合中,。為了確保 Bigtable集群在Master服務器和Chubby之間網(wǎng)絡出現(xiàn)故障的時候仍然可以使用,，Master服務器在它的Chubby會話過期后主動退 出。但是不管怎樣,，如同我們前面所描述的,，Master服務器的故障不會改變現(xiàn)有Tablet在Tablet服務器上的分配狀態(tài)。 當集群管理系統(tǒng)啟動了一個Master服務器之后,，Master服務器首先要了解當前Tablet的分配狀態(tài),，之后才能夠修改分配狀態(tài)。 Master服務器在啟動的時候執(zhí)行以下步驟：（1）Master服務器從Chubby獲取一個唯一的Master鎖,，用來阻止創(chuàng)建其它的Master服 務器實例,；（2）Master服務器掃描Chubby的服務器文件鎖存儲目錄，獲取當前正在運行的服務器列表,；（3）Master服務器和所有的正在運行 的Tablet表服務器通信,，獲取每個Tablet服務器上Tablet的分配信息；（4）Master服務器掃描METADATA表獲取所有的 Tablet的集合,。在掃描的過程中,，當Master服務器發(fā)現(xiàn)了一個還沒有分配的Tablet,，Master服務器就將這個Tablet加入未分配的 Tablet集合等待合適的時機分配。 可能會遇到一種復雜的情況：在METADATA表的Tablet還沒有被分配之前是不能夠掃描它的,。因此,，在開始掃描之前（步驟4），如果在第三步 的掃描過程中發(fā)現(xiàn)Root Tablet還沒有分配,，Master服務器就把Root Tablet加入到未分配的Tablet集合,。這個附加操作確保了Root Tablet會被分配。由于Root Tablet包括了所有METADATA的Tablet的名字,，因此Master服務器掃描完Root Tablet以后,，就得到了所有的METADATA表的Tablet的名字了。 保存現(xiàn)有Tablet的集合只有在以下事件發(fā)生時才會改變：建立了一個新表或者刪除了一個舊表,、兩個Tablet被合并了,、或者一個Tablet被 分割成兩個小的Tablet。Master服務器可以跟蹤記錄所有這些事件,，因為除了最后一個事件外的兩個事件都是由它啟動的,。Tablet分割事件需要 特殊處理，因為它是由Tablet服務器啟動,。在分割操作完成之后,，Tablet服務器通過在METADATA表中記錄新的Tablet的信息來提交這個 操作；當分割操作提交之后,，Tablet服務器會通知Master服務器,。如果分割操作已提交的信息沒有通知到Master服務器（可能兩個服務器中有一 個宕機了），Master服務器在要求Tablet服務器裝載已經(jīng)被分割的子表的時候會發(fā)現(xiàn)一個新的Tablet,。通過對比METADATA表中 Tablet的信息,，Tablet服務器會發(fā)現(xiàn)Master服務器要求其裝載的Tablet并不完整，因此,，Tablet服務器會重新向Master服務 器發(fā)送通知信息,。 5.3 Tablet服務 如圖5所示，Tablet的持久化狀態(tài)信息保存在GFS上,。更新操作提交到REDO日志中（alex注：Updates are committed to a commit log that stores redo records）,。 在這些更新操作中，最近提交的那些存放在一個排序的緩存中,，我們稱這個緩存為memtable,；較早的更新存放在一系列SSTable中。為了恢復一個 Tablet,，Tablet服務器首先從METADATA表中讀取它的元數(shù)據(jù),。Tablet的元數(shù)據(jù)包含了組成這個Tablet的SSTable的列表， 以及一系列的Redo Point（alex注：a set of redo points）,，這些Redo Point指向可能含有該Tablet數(shù)據(jù)的已提交的日志記錄,。Tablet服務器把SSTable的索引讀進內(nèi)存,，之后通過重復Redo Point之后提交的更新來重建memtable。 當對Tablet服務器進行寫操作時,，Tablet服務器首先要檢查這個操作格式是否正確,、操作發(fā)起者是否有執(zhí)行這個操作的權(quán)限。權(quán)限驗證的方法是 通過從一個Chubby文件里讀取出來的具有寫權(quán)限的操作者列表來進行驗證（這個文件幾乎一定會存放在Chubby客戶緩存里）,。成功的修改操作會記錄在 提交日志里,。可以采用批量提交方式（alex注：group commit）來提高包含大量小的修改操作的應用程序的吞吐量【13,，16】,。當一個寫操作提交后，寫的內(nèi)容插入到memtable里面,。 當對Tablet服務器進行讀操作時,，Tablet服務器會作類似的完整性和權(quán)限檢查。一個有效的讀操作在一個由一系列SSTable和memtable合并的視圖里執(zhí)行,。由于SSTable和memtable是按字典排序的數(shù)據(jù)結(jié)構(gòu),，因此可以高效生成合并視圖。 當進行Tablet的合并和分割時,，正在進行的讀寫操作能夠繼續(xù)進行,。 5.4 Compactions(alex注：這個詞挺簡單，但是在這節(jié)里面挺難翻譯的,。應該是空間縮減的意思,，但是似乎又不能完全概括它在上下文中的意思，干脆,，不翻譯了) 隨著寫操作的執(zhí)行，memtable的大小不斷增加,。當memtable的尺寸到達一個門限值的時候,，這個memtable就會被凍結(jié)，然后創(chuàng)建一個新的memtable,；被凍結(jié)住memtable會被轉(zhuǎn)換成SSTable,，然后寫入GFS（alex注：我們稱這種Compaction行為為Minor Compaction）。Minor Compaction過程有兩個目的：shrink(alex注：shrink是數(shù)據(jù)庫用語,，表示空間收縮)Tablet服務器使用的內(nèi)存,，以及在服務器災難恢復過程中，減少必須從提交日志里讀取的數(shù)據(jù)量,。在Compaction過程中,，正在進行的讀寫操作仍能繼續(xù)。 每一次Minor Compaction都會創(chuàng)建一個新的SSTable,。如果Minor Compaction過程不停滯的持續(xù)進行下去,，讀操作可能需要合并來自多個SSTable的更新,；否則，我們通過定期在后臺執(zhí)行Merging Compaction過程合并文件,，限制這類文件的數(shù)量,。Merging Compaction過程讀取一些SSTable和memtable的內(nèi)容，合并成一個新的SSTable,。只要Merging Compaction過程完成了,，輸入的這些SSTable和memtable就可以刪除了。 合并所有的SSTable并生成一個新的SSTable的Merging Compaction過程叫作Major Compaction,。由非Major Compaction產(chǎn)生的SSTable可能含有特殊的刪除條目,，這些刪除條目能夠隱藏在舊的、但是依然有效的SSTable中已經(jīng)刪除的數(shù)據(jù)（alex 注：令人費解啊,，原文是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,，并且定期對它們執(zhí)行 Major Compaction,。Major Compaction機制允許Bigtable回收已經(jīng)刪除的數(shù)據(jù)占有的資源，并且確保BigTable能及時清除已經(jīng)刪除的數(shù)據(jù)（alex注：實際是回收資源,。數(shù)據(jù)刪除后,，它占有的空間并不能馬上重復利用；只有空間回收后才能重復使用）,，這對存放敏感數(shù)據(jù)的服務是非常重要,。 6 優(yōu)化上一章我們描述了Bigtable的實現(xiàn)，我們還需要很多優(yōu)化工作才能使Bigtable到達用戶要求的高性能,、高可用性和高可靠性,。本章描述了Bigtable實現(xiàn)的其它部分，為了更好的強調(diào)這些優(yōu)化工作,，我們將深入細節(jié),。
局部性群組 客戶程序可以將多個列族組合成一個局部性群族。對Tablet中的每個局部性群組都會生成一個單獨的SSTable,。將通常不會一起訪問的列族
分割成不同的局部性群組可以提高讀取操作的效率,。例如，在Webtable表中,，網(wǎng)頁的元數(shù)據(jù)（比如語言和Checksum）可以在一個局部性群組中,，網(wǎng)
頁的內(nèi)容可以在另外一個群組：當一個應用程序要讀取網(wǎng)頁的元數(shù)據(jù)的時候，它沒有必要去讀取所有的頁面內(nèi)容,。
此外,，可以以局部性群組為單位設定一些有用的調(diào)試參數(shù)。比如,，可以把一個局部性群組設定為全部存儲在內(nèi)存中,。Tablet服務器依照惰性加載的
策略將設定為放入內(nèi)存的局部性群組的SSTable裝載進內(nèi)存,。加載完成之后，訪問屬于該局部性群組的列族的時候就不必讀取硬盤了,。這個特性對于需要頻繁
訪問的小塊數(shù)據(jù)特別有用：在Bigtable內(nèi)部,，我們利用這個特性提高METADATA表中具有位置相關性的列族的訪問速度。
壓縮 客戶程序可以控制一個局部性群組的SSTable是否需要壓縮,；如果需要壓縮,，那么以什么格式來壓縮。每個SSTable的塊（塊的大小由局部性群組的優(yōu)化參數(shù)指定）都使用用戶指定的壓縮格式來壓縮,。雖然分塊壓縮浪費了少量空間（alex注：相比于對整個SSTable進行壓縮,，分塊壓縮壓縮率較低），但 是,，我們在只讀取SSTable的一小部分數(shù)據(jù)的時候就不必解壓整個文件了,。很多客戶程序使用了“兩遍”的、可定制的壓縮方式,。第一遍采用Bentley and McIlroy’s方式[6],，這種方式在一個很大的掃描窗口里對常見的長字符串進行壓縮；第二遍是采用快速壓縮算法,，即在一個16KB的小掃描窗口中尋 找重復數(shù)據(jù),。兩個壓縮的算法都很快，在現(xiàn)在的機器上,，壓縮的速率達到100-200MB/s,，解壓的速率達到400-1000MB/s。 雖然我們在選擇壓縮算法的時候重點考慮的是速度而不是壓縮的空間,，但是這種兩遍的壓縮方式在空間壓縮率上的表現(xiàn)也是令人驚嘆,。比如，在 Webtable的例子里,，我們使用這種壓縮方式來存儲網(wǎng)頁內(nèi)容,。在一次測試中，我們在一個壓縮的局部性群組中存儲了大量的網(wǎng)頁,。針對實驗的目的，我們沒 有存儲每個文檔所有版本的數(shù)據(jù),，我們僅僅存儲了一個版本的數(shù)據(jù),。該模式的空間壓縮比達到了10:1。這比傳統(tǒng)的Gzip在壓縮HTML頁面時3:1或者 4:1的空間壓縮比好的多,；“兩遍”的壓縮模式如此高效的原因是由于Webtable的行的存放方式：從同一個主機獲取的頁面都存在臨近的地方,。利用這個 特性，Bentley-McIlroy算法可以從來自同一個主機的頁面里找到大量的重復內(nèi)容,。不僅僅是Webtable,，其它的很多應用程序也通過選擇合 適的行名來將相似的數(shù)據(jù)聚簇在一起,，以獲取較高的壓縮率。當我們在Bigtable中存儲同一份數(shù)據(jù)的多個版本的時候,，壓縮效率會更高,。 通過緩存提高讀操作的性能 為了提高讀操作的性能，Tablet服務器使用二級緩存的策略,。掃描緩存是第一級緩存,，主要緩存Tablet服務器通過SSTable接口獲取的 Key-Value對；Block緩存是二級緩存,，緩存的是從GFS讀取的SSTable的Block,。對于經(jīng)常要重復讀取相同數(shù)據(jù)的應用程序來說，掃描 緩存非常有效,；對于經(jīng)常要讀取剛剛讀過的數(shù)據(jù)附近的數(shù)據(jù)的應用程序來說,，Block緩存更有用（例如，順序讀,，或者在一個熱點的行的局部性群組中隨機讀取 不同的列),。 Bloom過濾器 (alex注：Bloom，又叫布隆過濾器,，什么意思,？請參考Google黑板報http:///2007/07/bloom-filter.html請務必先認真閱讀) 如5.3節(jié)所述，一個讀操作必須讀取構(gòu)成Tablet狀態(tài)的所有SSTable的數(shù)據(jù),。如果這些SSTable不在內(nèi)存中,，那么就需要多次訪問硬 盤。我們通過允許客戶程序?qū)μ囟ň植啃匀航M的SSTable指定Bloom過濾器【7】,，來減少硬盤訪問的次數(shù),。我們可以使用Bloom過濾器查詢一個 SSTable是否包含了特定行和列的數(shù)據(jù)。對于某些特定應用程序,，我們只付出了少量的,、用于存儲Bloom過濾器的內(nèi)存的代價，就換來了讀操作顯著減少 的磁盤訪問的次數(shù),。使用Bloom過濾器也隱式的達到了當應用程序訪問不存在的行或列時,，大多數(shù)時候我們都不需要訪問硬盤的目的。 Commit日志的實現(xiàn) 如果我們把對每個Tablet的操作的Commit日志都存在一個單獨的文件的話,，那么就會產(chǎn)生大量的文件,，并且這些文件會并行的寫入GFS。根據(jù)GFS服務器底層文件系統(tǒng)實現(xiàn)的方案,，要把這些文件寫入不同的磁盤日志文件時(alex注：different physical log files),，會有大量的磁盤Seek操作。另外，由于批量提交(alex注：group commit)中 操作的數(shù)目一般比較少,，因此,，對每個Tablet設置單獨的日志文件也會給批量提交本應具有的優(yōu)化效果帶來很大的負面影響。為了避免這些問題,，我們設置每 個Tablet服務器一個Commit日志文件,，把修改操作的日志以追加方式寫入同一個日志文件，因此一個實際的日志文件中混合了對多個Tablet修改 的日志記錄,。 使用單個日志顯著提高了普通操作的性能,，但是將恢復的工作復雜化了。當一個Tablet服務器宕機時,，它加載的Tablet將會被移到很多其它的 Tablet服務器上：每個Tablet服務器都裝載很少的幾個原來的服務器的Tablet,。當恢復一個Tablet的狀態(tài)的時候，新的Tablet服務 器要從原來的Tablet服務器寫的日志中提取修改操作的信息,，并重新執(zhí)行,。然而，這些Tablet修改操作的日志記錄都混合在同一個日志文件中的,。一種 方法新的Tablet服務器讀取完整的Commit日志文件,，然后只重復執(zhí)行它需要恢復的Tablet的相關修改操作。使用這種方法,，假如有100臺 Tablet服務器,，每臺都加載了失效的Tablet服務器上的一個Tablet，那么,，這個日志文件就要被讀取100次（每個服務器讀取一次）,。 為了避免多次讀取日志文件，我們首先把日志按照關鍵字（table,，row name,，log sequence number）排序。排序之后,，對同一個Tablet的修改操作的日志記錄就連續(xù)存放在了一起,，因此，我們只要一次磁盤Seek操作,、之后順序讀取就可以 了,。為了并行排序，我們先將日志分割成64MB的段,，之后在不同的Tablet服務器對段進行并行排序,。這個排序工作由Master服務器來協(xié)同處理，并 且在一個Tablet服務器表明自己需要從Commit日志文件恢復Tablet時開始執(zhí)行,。 在向GFS中寫Commit日志的時候可能會引起系統(tǒng)顛簸，原因是多種多樣的（比如，寫操作正在進行的時候,，一個GFS服務器宕機了,；或者連接三個 GFS副本所在的服務器的網(wǎng)絡擁塞或者過載了）。為了確保在GFS負載高峰時修改操作還能順利進行,，每個Tablet服務器實際上有兩個日志寫入線程,，每 個線程都寫自己的日志文件，并且在任何時刻,，只有一個線程是工作的,。如果一個線程的在寫入的時候效率很低，Tablet服務器就切換到另外一個線程,，修改 操作的日志記錄就寫入到這個線程對應的日志文件中,。每個日志記錄都有一個序列號，因此,，在恢復的時候,，Tablet服務器能夠檢測出并忽略掉那些由于線程 切換而導致的重復的記錄。 Tablet恢復提速 當Master服務器將一個Tablet從一個Tablet服務器移到另外一個Tablet服務器時,，源Tablet服務器會對這個
Tablet做一次Minor
Compaction,。這個Compaction操作減少了Tablet服務器的日志文件中沒有歸并的記錄，從而減少了恢復的時間,。Compaction
完成之后,，該服務器就停止為該Tablet提供服務。在卸載Tablet之前,，源Tablet服務器還會再做一次（通常會很快）Minor
Compaction,，以消除前面在一次壓縮過程中又產(chǎn)生的未歸并的記錄。第二次Minor
Compaction完成以后,，Tablet就可以被裝載到新的Tablet服務器上了,，并且不需要從日志中進行恢復。
利用不變性 我們在使用Bigtable時,，除了SSTable緩存之外的其它部分產(chǎn)生的SSTable都是不變的,，我們可以利用這一點對系統(tǒng)進行簡化。例如,， 當從SSTable讀取數(shù)據(jù)的時候,，我們不必對文件系統(tǒng)訪問操作進行同步。這樣一來,，就可以非常高效的實現(xiàn)對行的并行操作,。memtable是唯一一個能 被讀和寫操作同時訪問的可變數(shù)據(jù)結(jié)構(gòu)。為了減少在讀操作時的競爭,，我們對內(nèi)存表采用COW(Copy-on-write)機制,，這樣就允許讀寫操作并行執(zhí) 行,。 因為SSTable是不變的，因此,，我們可以把永久刪除被標記為“刪除”的數(shù)據(jù)的問題,，轉(zhuǎn)換成對廢棄的SSTable進行垃圾收集的問題了。每個 Tablet的SSTable都在METADATA表中注冊了,。Master服務器采用“標記-刪除”的垃圾回收方式刪除SSTable集合中廢棄的 SSTable【25】,，METADATA表則保存了Root SSTable的集合。 最后,，SSTable的不變性使得分割Tablet的操作非?？旖荨Ｎ覀儾槐貫槊總€分割出來的Tablet建立新的SSTable集合,，而是共享原來的Tablet的SSTable集合,。 7 性能評估為了測試Bigtable的性能和可擴展性，我們建立了一個包括N臺Tablet服務器的Bigtable集群,，這里N是可變的,。每臺
Tablet服務器配置了1GB的內(nèi)存，數(shù)據(jù)寫入到一個包括1786臺機器,、每臺機器有2個IDE硬盤的GFS集群上,。我們使用N臺客戶機生成工作負載測
試Bigtable。（我們使用和Tablet服務器相同數(shù)目的客戶機以確?？蛻魴C不會成為瓶頸,。）
每臺客戶機配置2GZ雙核Opteron處理器，配置了足以容納所有進程工作數(shù)據(jù)集的物理內(nèi)存,，以及一張Gigabit的以太網(wǎng)卡,。這些機器都連入一個兩
層的、樹狀的交換網(wǎng)絡里,，在根節(jié)點上的帶寬加起來有大約100-200Gbps,。所有的機器采用相同的設備，因此,，任何兩臺機器間網(wǎng)絡來回一次的時間都小
于1ms,。
Tablet服務器、Master服務器,、測試機,、以及GFS服務器都運行在同一組機器上。每臺機器都運行一個GFS的服務器,。其它的機器要么運行Tablet服務器,、要么運行客戶程序、要么運行在測試過程中,，使用這組機器的其它的任務啟動的進程,。
R是測試過程中,，Bigtable包含的不同的列關鍵字的數(shù)量。我們精心選擇R的值,，保證每次基準測試對每臺Tablet服務器讀/寫的數(shù)據(jù)量都在1GB左右,。
在序列寫的基準測試中，我們使用的列關鍵字的范圍是0到R-1,。這個范圍又被劃分為10N個大小相同的區(qū)間。核心調(diào)度程序把這些區(qū)間分配給N個
客戶端,，分配方式是：只要客戶程序處理完上一個區(qū)間的數(shù)據(jù),，調(diào)度程序就把后續(xù)的、尚未處理的區(qū)間分配給它,。這種動態(tài)分配的方式有助于減少客戶機上同時運行
的其它進程對性能的影響,。我們在每個列關鍵字下寫入一個單獨的字符串。每個字符串都是隨機生成的,、因此也沒有被壓縮（alex注：參考第6節(jié)的壓縮小節(jié)）,。另外，不同列關鍵字下的字符串也是不同的,，因此也就不存在跨行的壓縮,。隨機寫入基準測試采用類似的方法，除了行關鍵字在寫入前先做Hash,，Hash采用按R取模的方式,，這樣就保證了在整個基準測試持續(xù)的時間內(nèi)，寫入的工作負載均勻的分布在列存儲空間內(nèi),。
序列讀的基準測試生成列關鍵字的方式與序列寫相同,，不同于序列寫在列關鍵字下寫入字符串的是，序列讀是讀取列關鍵字下的字符串（這些字符串由之前序列寫基準測試程序?qū)懭耄?。同樣的,，隨機讀的基準測試和隨機寫是類似的。
掃描基準測試和序列讀類似,，但是使用的是BigTable提供的,、從一個列范圍內(nèi)掃描所有的value值的API。由于一次RPC調(diào)用就從一個Tablet服務器取回了大量的Value值,，因此,，使用掃描方式的基準測試程序可以減少RPC調(diào)用的次數(shù)。
隨機讀（內(nèi)存）基準測試和隨機讀類似,，除了包含基準測試數(shù)據(jù)的局部性群組被設置為“in-memory”,，因此，讀操作直接從Tablet服務
器的內(nèi)存中讀取數(shù)據(jù),，不需要從GFS讀取數(shù)據(jù),。針對這個測試,，我們把每臺Tablet服務器存儲的數(shù)據(jù)從1GB減少到100MB，這樣就可以把數(shù)據(jù)全部加
載到Tablet服務器的內(nèi)存中了,。
 圖6中有兩個視圖,，顯示了我們的基準測試的性能；圖中的數(shù)據(jù)和曲線是讀/寫 1000-byte value值時取得的,。圖中的表格顯示了每個Tablet服務器每秒鐘進行的操作的次數(shù),；圖中的曲線顯示了每秒種所有的Tablet服務器上操作次數(shù)的總和。
單個Tablet服務器的性能 我們首先分析下單個Tablet服務器的性能,。隨機讀的性能比其它操作慢一個數(shù)量級或以上（alex注：by the order of magnitude or more） ,。 每個隨機讀操作都要通過網(wǎng)絡從GFS傳輸64KB的SSTable到Tablet服務器，而我們只使用其中大小是1000 byte的一個value值,。Tablet服務器每秒大約執(zhí)行1200次讀操作,，也就是每秒大約從GFS讀取75MB的數(shù)據(jù)。這個傳輸帶寬足以占滿 Tablet服務器的CPU時間,，因為其中包括了網(wǎng)絡協(xié)議棧的消耗,、SSTable解析、以及BigTable代碼執(zhí)行,；這個帶寬也足以占滿我們系統(tǒng)中網(wǎng) 絡的鏈接帶寬,。大多數(shù)采用這種訪問模式BigTable應用程序會減小Block的大小，通常會減到8KB,。 內(nèi)存中的隨機讀操作速度快很多,，原因是，所有1000-byte的讀操作都是從Tablet服務器的本地內(nèi)存中讀取數(shù)據(jù),，不需要從GFS讀取64KB的Block,。 隨機和序列寫操作的性能比隨機讀要好些，原因是每個Tablet服務器直接把寫入操作的內(nèi)容追加到一個Commit日志文件的尾部,，并且采用批量提 交的方式,，通過把數(shù)據(jù)以流的方式寫入到GFS來提高性能。隨機寫和序列寫在性能上沒有太大的差異,，這兩種方式的寫操作實際上都是把操作內(nèi)容記錄到同一個 Tablet服務器的Commit日志文件中,。 序列讀的性能好于隨機讀，因為每取出64KB的SSTable的Block后,，這些數(shù)據(jù)會緩存到Block緩存中,，后續(xù)的64次讀操作直接從緩存讀取數(shù)據(jù)。 掃描的性能更高,，這是由于客戶程序每一次RPC調(diào)用都會返回大量的value的數(shù)據(jù),，所以，RPC調(diào)用的消耗基本抵消了,。 性能提升 隨著我們將系統(tǒng)中的Tablet服務器從1臺增加到500臺,，系統(tǒng)的整體吞吐量有了夢幻般的增長,，增長的倍率超過了100。比如,，隨著Tablet 服務器的數(shù)量增加了500倍,，內(nèi)存中的隨機讀操作的性能增加了300倍。之所以會有這樣的性能提升,，主要是因為這個基準測試的瓶頸是單臺Tablet服務 器的CPU,。 盡管如此，性能的提升還不是線性的,。在大多數(shù)的基準測試中我們看到,，當Tablet服務器的數(shù)量從1臺增加到50臺時，每臺服務器的吞吐量會有一個 明顯的下降,。這是由于多臺服務器間的負載不均衡造成的，大多數(shù)情況下是由于其它的程序搶占了CPU,。 我們負載均衡的算法會盡量避免這種不均衡,，但是基于兩個主要原因，這個算法并不能完美的工作：一個是盡量減少Tablet的移動導致重新負載均衡能力受限 （如果Tablet被移動了,，那么在短時間內(nèi) — 一般是1秒內(nèi) — 這個Tablet是不可用的）,，另一個是我們的基準測試程序產(chǎn)生的負載會有波動（alex注：the load generated by our benchmarks shifts around as the benchmark progresses）。 隨機讀基準測試的測試結(jié)果顯示,，隨機讀的性能隨Tablet服務器數(shù)量增加的提升幅度最?。ㄕw吞吐量只提升了100倍，而服務器的數(shù)量卻增加了 500倍）,。這是因為每個1000-byte的讀操作都會導致一個64KB大的Block在網(wǎng)絡上傳輸,。這樣的網(wǎng)絡傳輸量消耗了我們網(wǎng)絡中各種共享的 1GB的鏈路，結(jié)果導致隨著我們增加服務器的數(shù)量,，每臺服務器上的吞吐量急劇下降,。 8 實際應用 截止到2006年8月，Google內(nèi)部一共有388個非測試用的Bigtable集群運行在各種各樣的服務器集群上,，合計大約有24500個
Tablet服務器,。表1顯示了每個集群上Tablet服務器的大致分布情況。這些集群中,，許多用于開發(fā)目的,，因此會有一段時期比較空閑。通過觀察一個由
14個集群,、8069個Tablet服務器組成的集群組,，我們看到整體的吞吐量超過了每秒1200000次請求，發(fā)送到系統(tǒng)的RPC請求導致的網(wǎng)絡負載達
到了741MB/s,，系統(tǒng)發(fā)出的RPC請求網(wǎng)絡負載大約是16GB/s,。
 表2提供了一些目前正在使用的表的相關數(shù)據(jù),。一些表存儲的是用戶相關的數(shù)據(jù)，另外一些存儲的則是用于批處理的數(shù)據(jù),；這些表在總的大小,、 每個數(shù)據(jù)項的平均大小、從內(nèi)存中讀取的數(shù)據(jù)的比例,、表的Schema的復雜程度上都有很大的差別,。本節(jié)的其余部分，我們將主要描述三個產(chǎn)品研發(fā)團隊如何使 用Bigtable的,。 8.1 Google AnalyticsGoogle Analytics是用來幫助Web站點的管理員分析他們網(wǎng)站的流量模式的服務,。它提供了整體狀況的統(tǒng)計數(shù)據(jù)，比如每天的獨立訪問的用戶數(shù)量,、每天每個 URL的瀏覽次數(shù),；它還提供了用戶使用網(wǎng)站的行為報告，比如根據(jù)用戶之前訪問的某些頁面,，統(tǒng)計出幾成的用戶購買了商品,。 為了使用這個服務，Web站點的管理員只需要在他們的Web頁面中嵌入一小段JavaScript腳本就可以了,。這個Javascript程序在頁 面被訪問的時候調(diào)用,。它記錄了各種Google Analytics需要使用的信息，比如用戶的標識,、獲取的網(wǎng)頁的相關信息,。Google Analytics匯總這些數(shù)據(jù)，之后提供給Web站點的管理員,。 我們粗略的描述一下Google Analytics使用的兩個表,。Row Click表（大約有200TB數(shù)據(jù)）的每一行存放了一個最終用戶的會話。行的名字是一個包含Web站點名字以及用戶會話創(chuàng)建時間的元組,。這種模式保證了 對同一個Web站點的訪問會話是順序的,，會話按時間順序存儲。這個表可以壓縮到原來尺寸的14%,。 Summary表（大約有20TB的數(shù)據(jù)）包含了關于每個Web站點的,、各種類型的預定義匯總信息。一個周期性運行的MapReduce任務根據(jù) Raw Click表的數(shù)據(jù)生成Summary表的數(shù)據(jù),。每個MapReduce工作進程都從Raw Click表中提取最新的會話數(shù)據(jù),。系統(tǒng)的整體吞吐量受限于GFS的吞吐量。這個表的能夠壓縮到原有尺寸的29%,。 8.2 Google EarthGoogle通過一組服務為用戶提供了高分辨率的地球表面衛(wèi)星圖像,，訪問的方式可以使通過基于Web的Google Maps訪問接口（maps.google.com），也可以通過Google Earth定制的客戶端軟件訪問。這些軟件產(chǎn)品允許用戶瀏覽地球表面的圖像：用戶可以在不同的分辨率下平移,、查看和注釋這些衛(wèi)星圖像,。這個系統(tǒng)使用一個表 存儲預處理數(shù)據(jù)，使用另外一組表存儲用戶數(shù)據(jù),。 數(shù)據(jù)預處理流水線使用一個表存儲原始圖像,。在預處理過程中，圖像被清除,，圖像數(shù)據(jù)合并到最終的服務數(shù)據(jù)中,。這個表包含了大約70TB的數(shù)據(jù)，所以需要從磁盤讀取數(shù)據(jù),。圖像已經(jīng)被高效壓縮過了,，因此存儲在Bigtable后不需要再壓縮了。 Imagery表的每一行都代表了一個單獨的地理區(qū)域,。行都有名稱,，以確保毗鄰的區(qū)域存儲在了一起。Imagery表中有一個列族用來記錄每個區(qū)域 的數(shù)據(jù)源,。這個列族包含了大量的列：基本上市每個列對應一個原始圖片的數(shù)據(jù),。由于每個地理區(qū)域都是由很少的幾張圖片構(gòu)成的，因此這個列族是非常稀疏的,。 數(shù)據(jù)預處理流水線高度依賴運行在Bigtable上的MapReduce任務傳輸數(shù)據(jù)。在運行某些MapReduce任務的時候,，整個系統(tǒng)中每臺Tablet服務器的數(shù)據(jù)處理速度是1MB/s,。 這個服務系統(tǒng)使用一個表來索引GFS中的數(shù)據(jù)。這個表相對較?。ù蠹s是500GB）,，但是這個表必須在保證較低的響應延時的前提下，針對每個數(shù)據(jù)中心,，每秒處理幾萬個查詢請求,。 因此，這個表必須在上百個Tablet服務器上存儲數(shù)據(jù),，并且使用in-memory的列族,。 8.3 個性化查詢個性化查詢（www.google.com/psearch）是一個雙向服務；這個服務記錄用戶的查詢和點擊,，涉及到各種Google的服務,，比如Web查詢、圖像和新聞,。用戶可以瀏覽他們查詢的歷史,，重復他們之前的查詢和點擊；用戶也可以定制基于Google歷史使用習慣模式的個性化查詢結(jié)果,。 個性化查詢使用Bigtable存儲每個用戶的數(shù)據(jù),。每個用戶都有一個唯一的用戶id,，每個用戶id和一個列名綁定。一個單獨的列族被用來存儲各種 類型的行為（比如,，有個列族可能是用來存儲所有的Web查詢的）,。每個數(shù)據(jù)項都被用作Bigtable的時間戳，記錄了相應的用戶行為發(fā)生的時間,。個性化 查詢使用以Bigtable為存儲的MapReduce任務生成用戶的數(shù)據(jù)圖表,。這些用戶數(shù)據(jù)圖表用來個性化當前的查詢結(jié)果。 個性化查詢的數(shù)據(jù)會復制到幾個Bigtable的集群上,，這樣就增強了數(shù)據(jù)可用性,，同時減少了由客戶端和Bigtable集群間的“距離”造成的延 時。個性化查詢的開發(fā)團隊最初建立了一個基于Bigtable的,、“客戶側(cè)”的復制機制為所有的復制節(jié)點提供一致性保障?，F(xiàn)在的系統(tǒng)則使用了內(nèi)建的復制子 系統(tǒng)。 個性化查詢存儲系統(tǒng)的設計允許其它的團隊在它們自己的列中加入新的用戶數(shù)據(jù),，因此,，很多Google服務使用個性化查詢存儲系統(tǒng)保存用戶級的配置參數(shù)和設置。在多個團隊之間分享數(shù)據(jù)的結(jié)果是產(chǎn)生了大量的列族,。為了更好的支持數(shù)據(jù)共享,，我們加入了一個簡單的配額機制(alex注：quota，參考AIX的配額機制)限制用戶在共享表中使用的空間,；配額也為使用個性化查詢系統(tǒng)存儲用戶級信息的產(chǎn)品團體提供了隔離機制,。 9 經(jīng)驗教訓在設計、實現(xiàn),、維護和支持Bigtable的過程中,，我們得到了很多有用的經(jīng)驗和一些有趣的教訓。 一個教訓是,，我們發(fā)現(xiàn),，很多類型的錯誤都會導致大型分布式系統(tǒng)受損，這些錯誤不僅僅是通常的網(wǎng)絡中斷,、或者很多分布式協(xié)議中設想的fail-stop類型的錯誤（alex注：fail-stop failture,，指一旦系統(tǒng)fail就stop，不輸出任何數(shù)據(jù),；fail-fast failture,，指fail不馬上stop，在短時間內(nèi)return錯誤信息,，然后再stop）,。比如，我們遇到過下面這些類型的錯誤導致的問題：內(nèi)存數(shù)據(jù)損壞、網(wǎng)絡中斷,、時鐘偏差,、機器掛起、擴展的和非對稱的網(wǎng)絡分區(qū)（alex注：extended and asymmetric network partitions,，不明白什么意思,。partition也有中斷的意思，但是我不知道如何用在這里）,、我 們使用的其它系統(tǒng)的Bug（比如Chubby）,、GFS配額溢出、計劃內(nèi)和計劃外的硬件維護,。我們在解決這些問題的過程中學到了很多經(jīng)驗,，我們通過修改協(xié) 議來解決這些問題。比如,，我們在我們的RPC機制中加入了Checksum,。我們在設計系統(tǒng)的部分功能時，不對其它部分功能做任何的假設,，這樣的做法解決 了其它的一些問題,。比如，我們不再假設一個特定的Chubby操作只返回錯誤碼集合中的一個值,。 另外一個教訓是,，我們明白了在徹底了解一個新特性會被如何使用之后，再決定是否添加這個新特性是非常重要的,。比如,，我們開始計劃在我們的API中支 持通常方式的事務處理。但是由于我們還不會馬上用到這個功能,，因此，我們并沒有去實現(xiàn)它?，F(xiàn)在,，Bigtable上已經(jīng)有了很多的實際應用，我們可以檢查 它們真實的需求,；我們發(fā)現(xiàn),，大多是應用程序都只是需要單個行上的事務功能。有些應用需要分布式的事務功能,，分布式事務大多數(shù)情況下用于維護二級索引,，因此 我們增加了一個特殊的機制去滿足這個需求。新的機制在通用性上比分布式事務差很多,，但是它更有效（特別是在更新操作的涉及上百行數(shù)據(jù)的時候）,，而且非常符 合我們的“跨數(shù)據(jù)中心”復制方案的優(yōu)化策略。 還有一個具有實踐意義的經(jīng)驗：我們發(fā)現(xiàn)系統(tǒng)級的監(jiān)控對Bigtable非常重要（比如，監(jiān)控Bigtable自身以及使用Bigtable的客戶程 序）,。比如,，我們擴展了我們的RPC系統(tǒng)，因此對于一個RPC調(diào)用的例子,，它可以詳細記錄代表了RPC調(diào)用的很多重要操作,。這個特性允許我們檢測和修正很 多的問題，比如Tablet數(shù)據(jù)結(jié)構(gòu)上的鎖的內(nèi)容,、在修改操作提交時對GFS的寫入非常慢的問題,、以及在METADATA表的Tablet不可用時，對 METADATA表的訪問掛起的問題,。關于監(jiān)控的用途的另外一個例子是,，每個Bigtable集群都在Chubby中注冊了。這可以幫助我們跟蹤所有的集 群狀態(tài),、監(jiān)控它們的大小,、檢查集群運行的我們軟件的版本、監(jiān)控集群流入數(shù)據(jù)的流量,，以及檢查是否有引發(fā)集群高延時的潛在因素,。 對我們來說，最寶貴的經(jīng)驗是簡單設計的價值,?？紤]到我們系統(tǒng)的代碼量（大約100000行生產(chǎn)代碼（alex注：non-test code））， 以及隨著時間的推移,，新的代碼以各種難以預料的方式加入系統(tǒng),，我們發(fā)現(xiàn)簡潔的設計和編碼給維護和調(diào)試帶來的巨大好處。這方面的一個例子是我們的 Tablet服務器成員協(xié)議,。我們第一版的協(xié)議很簡單：Master服務器周期性的和Tablet服務器簽訂租約,，Tablet服務器在租約過期的時候 Kill掉自己的進程。不幸的是,，這個協(xié)議在遇到網(wǎng)絡問題時會大大降低系統(tǒng)的可用性,，也會大大增加Master服務器恢復的時間。我們多次重新設計這個協(xié) 議,，直到它能夠很好的處理上述問題,。但是，更不幸的是,，最終的協(xié)議過于復雜了,，并且依賴一些Chubby很少被用到的特性。我們發(fā)現(xiàn)我們浪費了大量的時間 在調(diào)試一些古怪的問題(alex注：obscure corner cases),，有些是Bigtable代碼的問題,，有些事Chubby代碼的問題,。最后，我們只好廢棄了這個協(xié)議,，重新制訂了一個新的,、更簡單、只使用Chubby最廣泛使用的特性的協(xié)議,。 10 相關工作Boxwood【24】項目的有些組件在某些方面和Chubby,、GFS以及Bigtable類似，因為它也提供了諸如分布式協(xié)議,、鎖,、分布式 Chunk存儲以及分布式B-tree存儲。Boxwood與Google的某些組件盡管功能類似,，但是Boxwood的組件提供更底層的服務,。 Boxwood項目的目的是提供創(chuàng)建類似文件系統(tǒng)、數(shù)據(jù)庫等高級服務的基礎構(gòu)件,，而Bigtable的目的是直接為客戶程序的數(shù)據(jù)存儲需求提供支持,。 現(xiàn)在有不少項目已經(jīng)攻克了很多難題，實現(xiàn)了在廣域網(wǎng)上的分布式數(shù)據(jù)存儲或者高級服務,，通常是“Internet規(guī)模”的,。這其中包括了分布式的 Hash表，這項工作由一些類似CAN【29】,、Chord【32】,、Tapestry【37】和Pastry【30】的項目率先發(fā)起。這些系統(tǒng)的主要關 注點和Bigtable不同,，比如應對各種不同的傳輸帶寬,、不可信的協(xié)作者、頻繁的更改配置等,；另外,，去中心化和Byzantine災難冗余(alex 注：Byzantine，即拜占庭式的風格,，也就是一種復雜詭秘的風格,。Byzantine Fault表示：對于處理來說，當發(fā)錯誤時處理器并不停止接收輸出,，也不停止輸出，錯就錯了,，只管算,，對于這種錯誤來說，這樣可真是夠麻煩了,，因為用戶根 本不知道錯誤發(fā)生了,，也就根本談不上處理錯誤了,。在多處理器的情況下，這種錯誤可能導致運算正確結(jié)果的處理器也產(chǎn)生錯誤的結(jié)果,，這樣事情就更麻煩了,，所以 一定要避免處理器產(chǎn)生這種錯誤。)也不是Bigtable的目的,。 就提供給應用程序開發(fā)者的分布式數(shù)據(jù)存儲模型而言,，我們相信，分布式B-Tree或者分布式Hash表提供的Key-value pair方式的模型有很大的局限性,。Key-value pair模型是很有用的組件,，但是它們不應該是提供給開發(fā)者唯一的組件。我們選擇的模型提供的組件比簡單的Key-value pair豐富的多,，它支持稀疏的,、半結(jié)構(gòu)化的數(shù)據(jù)。另外,，它也足夠簡單,，能夠高效的處理平面文件；它也是透明的（通過局部性群組）,，允許我們的使用者對系 統(tǒng)的重要行為進行調(diào)整,。 有些數(shù)據(jù)庫廠商已經(jīng)開發(fā)出了并行的數(shù)據(jù)庫系統(tǒng)，能夠存儲海量的數(shù)據(jù),。Oracle的RAC【27】使用共享磁盤存儲數(shù)據(jù)（Bigtable使用 GFS）,，并且有一個分布式的鎖管理系統(tǒng)（Bigtable使用Chubby）。IBM并行版本的DB2【4】基于一種類似于Bigtable的,、不共享 任何東西的架構(gòu)（a shared-nothing architecture）【33】,。每個DB2的服務器都負責處理存儲在一個關系型數(shù)據(jù)庫中的表中的行的一個子集。這些產(chǎn)品都提供了一個帶有事務功能的 完整的關系模型,。 Bigtable的局部性群組提供了類似于基于列的存儲方案在壓縮和磁盤讀取方面具有的性能,；這些以列而不是行的方式組織數(shù)據(jù)的方案包括C- Store【1，34】,、商業(yè)產(chǎn)品Sybase IQ【15,，36】、SenSage【31】,、KDB+【22】,，以及MonetDB/X100【38】的ColumnDM存儲層。另外一種在平面文件中 提供垂直和水平數(shù)據(jù)分區(qū),、并且提供很好的數(shù)據(jù)壓縮率的系統(tǒng)是AT&T的Daytona數(shù)據(jù)庫【19】,。局部性群組不支持Ailamaki系統(tǒng)中描 述的CPU緩存級別的優(yōu)化【2】。 Bigtable采用memtable和SSTable存儲對表的更新的方法與Log-Structured Merge Tree【26】存儲索引數(shù)據(jù)更新的方法類似,。這兩個系統(tǒng)中,，排序的數(shù)據(jù)在寫入到磁盤前都先存放在內(nèi)存中,，讀取操作必須從內(nèi)存和磁盤中合并數(shù)據(jù)產(chǎn)生最終的 結(jié)果集。 C-Store和Bigtable有很多相似點：兩個系統(tǒng)都采用Shared-nothing架構(gòu),，都有兩種不同的數(shù)據(jù)結(jié)構(gòu),，一種用于當前的寫操 作，另外一種存放“長時間使用”的數(shù)據(jù),，并且提供一種機制在兩個存儲結(jié)構(gòu)間搬運數(shù)據(jù),。兩個系統(tǒng)在API接口函數(shù)上有很大的不同：C-Store操作更像關 系型數(shù)據(jù)庫，而Bigtable提供了低層次的讀寫操作接口,，并且設計的目標是能夠支持每臺服務器每秒數(shù)千次操作,。C-Store同時也是個“讀性能優(yōu)化 的關系型數(shù)據(jù)庫”，而Bigtable對讀和寫密集型應用都提供了很好的性能,。 Bigtable也必須解決所有的Shared-nothing數(shù)據(jù)庫需要面對的,、類型相似的一些負載和內(nèi)存均衡方面的難題（比如， 【11,，35】）,。我們的問題在某種程度上簡單一些：（1）我們不需要考慮同一份數(shù)據(jù)可能有多個拷貝的問題，同一份數(shù)據(jù)可能由于視圖或索引的原因以不同的 形式表現(xiàn)出來,；（2）我們讓用戶決定哪些數(shù)據(jù)應該放在內(nèi)存里,、哪些放在磁盤上，而不是由系統(tǒng)動態(tài)的判斷,；（3）我們的系統(tǒng)中沒有復雜的查詢執(zhí)行或優(yōu)化工 作,。 11 結(jié)論我們已經(jīng)講述完了Bigtable，Google的一個分布式的結(jié)構(gòu)化數(shù)據(jù)存儲系統(tǒng),。Bigtable的集群從2005年4月開始已經(jīng)投入使用了,， 在此之前，我們花了大約7人年設計和實現(xiàn)這個系統(tǒng),。截止到2006年4月,，已經(jīng)有超過60個項目使用Bigtable了。我們的用戶對Bigtable提 供的高性能和高可用性很滿意,，隨著時間的推移,，他們可以根據(jù)自己的系統(tǒng)對資源的需求增加情況，通過簡單的增加機器,，擴展系統(tǒng)的承載能力,。 由于Bigtable提供的編程接口并不常見，一個有趣的問題是：我們的用戶適應新的接口有多難,？新的使用者有時不太確定使用Bigtable接口 的最佳方法,，特別是在他們已經(jīng)習慣于使用支持通用事務的關系型數(shù)據(jù)庫的接口的情況下。但是,，Google內(nèi)部很多產(chǎn)品都成功的使用了Bigtable的事 實證明了,，我們的設計在實踐中行之有效。 我們現(xiàn)在正在對Bigtable加入一些新的特性,，比如支持二級索引,，以及支持多Master節(jié)點的、跨數(shù)據(jù)中心復制的Bigtable的基礎構(gòu) 件,。我們現(xiàn)在已經(jīng)開始將Bigtable部署為服務供其它的產(chǎn)品團隊使用,，這樣不同的產(chǎn)品團隊就不需要維護他們自己的Bigtable集群了。隨著服務集 群的擴展,，我們需要在Bigtable系統(tǒng)內(nèi)部處理更多的關于資源共享的問題了【3,，5】。 最后,，我們發(fā)現(xiàn),，建設Google自己的存儲解決方案帶來了很多優(yōu)勢。通過為Bigtable設計我們自己的數(shù)據(jù)模型,，是我們的系統(tǒng)極具靈活性,。另 外，由于我們?nèi)婵刂浦鳥igtable的實現(xiàn)過程,，以及Bigtable使用到的其它的Google的基礎構(gòu)件,，這就意味著我們在系統(tǒng)出現(xiàn)瓶頸或效率低 下的情況時，能夠快速的解決這些問題,。 AcknowledgementsWe thank the anonymous reviewers, David Nagle, and our shepherd Brad
Calder, for their feedback on this paper.The Bigtable system has
benefited greatly from the feedback of our many users within Google. In
addition,we thank the following people for their contributions to
Bigtable: Dan Aguayo, Sameer Ajmani, Zhifeng Chen,Bill Coughran, Mike
Epstein, Healfdene Goguen, Robert Griesemer, Jeremy Hylton, Josh Hyman,
Alex Khesin, References[1] ABADI, D. J., MADDEN, S. R., AND FERREIRA, M. C. Integrating
compression and execution in columnoriented database systems. Proc. of
SIGMOD (2006). |
|
|
