大家覺(jué)得有意義和幫助記得及時(shí)關(guān)注和點(diǎn)贊!!!

---

• 譯者序
• 摘要
• 1 引言
• 2 數(shù)據(jù)模型
  • 2.1 行（Row）
  • 2.2 Column Families（列族）
    • 2.2.1 設(shè)計(jì)
    • 2.2.2 column key 的格式：family:qualifier
    • 2.2.3 訪(fǎng)問(wèn)控制和磁盤(pán)/內(nèi)存記賬（accounting）都是在 column family 層做的
  • 2.3 時(shí)間戳
• 3 API
• 4 外部系統(tǒng)依賴(lài)（Building Blocks）
  • 4.1 GFS
  • 4.2 SSTable
  • 4.3 Chuby
• 5 實(shí)現(xiàn)
  • 5.0 組件
  • 5.1 Tablet 位置
    • 服務(wù)端
    • 客戶(hù)端
  • 5.2 Tablet 分配
    • master 啟動(dòng)流程
    • 難點(diǎn)
    • tablet 分裂和分裂后的新 tablet 發(fā)現(xiàn)
  • 5.3 為 tablet 提供服務(wù)（Tablet Serving）
    • tablet 恢復(fù)
    • 寫(xiě)操作
    • 讀操作
  • 5.4 壓縮（Compactions）
• 6 改進(jìn)（Refinements）
  • 6.1 Locality groups
  • 6.2 壓縮（Compression）
    • 6.2.1 壓縮的粒度和算法
    • 6.2.2 壓縮的速度和效率
  • 6.3 讀緩存
  • 6.4 Bloom 過(guò)濾器
  • 6.5 Commit-log 實(shí)現(xiàn)
    • 每個(gè) tablet 還是每個(gè) tablet server 一個(gè) log 文件
    • 恢復(fù)過(guò)程變復(fù)雜
    • 優(yōu)化：兩個(gè)寫(xiě)線(xiàn)程和兩份 commit log
  • 6.6 加速 tablet 恢復(fù)過(guò)程
  • 6.7 利用不可變性（Exploiting immutability）
• 7 性能評(píng)估
  • 7.0 準(zhǔn)備
    • 測(cè)試環(huán)境
    • 性能指標(biāo)
  • 7.1 單 tablet-server 性能
  • 7.2 擴(kuò)展性（scaling）
• 8 真實(shí)應(yīng)用
  • 8.1 Google Analytics
  • 8.2 Google Earth
  • 8.3 Personalized Search
• 9 從中所學(xué)（Lessons）
  • 9.1 故障源遠(yuǎn)比你想象中多
  • 9.2 避免過(guò)早添加使用場(chǎng)景不明確的新特性
  • 9.3 系統(tǒng)級(jí)監(jiān)控非常重要
  • 9.4 保持設(shè)計(jì)的簡(jiǎn)潔
• 10 相關(guān)工作
• 11 總結(jié)
• Acknowledgements
• 參考文獻(xiàn)

---

摘要

Bigtable 是一個(gè)用于管理結(jié)構(gòu)化數(shù)據(jù)（structured data）的分布式存儲(chǔ)系統(tǒng)， 設(shè)計(jì)可以擴(kuò)展到非常大的規(guī)模：由幾千個(gè)通用服務(wù)器（commodity servers）組成的 PB 級(jí)存儲(chǔ)。

很多 Google 產(chǎn)品，包括 web index、Google Earth 和 Google Finance，都將數(shù)據(jù)存儲(chǔ)在 Bigtable 中。不過(guò)，這些應(yīng)用對(duì) Bigtable 的要求有很大差異，不管是從數(shù)據(jù)大小（從 URL 到網(wǎng)頁(yè)到衛(wèi)星圖像）還是從延遲（從后臺(tái)批量處理到實(shí)時(shí)數(shù)據(jù)服務(wù)）考慮。但是， Bigtable 仍然給這些產(chǎn)品提供了一個(gè)靈活、高性能的解決方案，它提供的簡(jiǎn)單數(shù)據(jù)模型可以 使客戶(hù)端動(dòng)態(tài)控制數(shù)據(jù)的布局和格式（layout and format）。

本文介紹 Bigtable 的設(shè)計(jì)與實(shí)現(xiàn)。

1 引言

在過(guò)去的兩年半中，我們?cè)O(shè)計(jì)、實(shí)現(xiàn)并部署了一個(gè)稱(chēng)為 Bigtable 的分布式存儲(chǔ) 系統(tǒng)，用于管理 Google 的結(jié)構(gòu)化數(shù)據(jù)。 設(shè)計(jì)中 Bigtable 能可靠地?cái)U(kuò)展到?PB 級(jí)數(shù)據(jù)，上千個(gè)節(jié)點(diǎn)。 現(xiàn)在已經(jīng)實(shí)現(xiàn)了廣泛的應(yīng)用場(chǎng)景支持、可擴(kuò)展性、高性能，以及高可用性等設(shè)計(jì)目標(biāo)。

目前 Bigtable 已經(jīng)被超過(guò) 60 個(gè) Google 產(chǎn)品和項(xiàng)目所使用，其中包括 Google Analytics、Google Finance、Orkut、Personalized Search、Writely、以及 Google Earth。這些產(chǎn)品的使用場(chǎng)景差異很大，從面向吞吐的批處理任務(wù)，到延遲敏感的終端用戶(hù) 數(shù)據(jù)服務(wù)。不同產(chǎn)品使用的 Bigtable 集群配置差異也很大，有的集群只有幾臺(tái)節(jié)點(diǎn)，有的 有幾千臺(tái)，存儲(chǔ)幾百 TB 的數(shù)據(jù)。

從某些方面看，Bigtable?像是一個(gè)數(shù)據(jù)庫(kù)：

• 它的很多實(shí)現(xiàn)策略（implementation strategies）確實(shí)和數(shù)據(jù)庫(kù)類(lèi)似。
• 并行數(shù)據(jù)庫(kù)?[14]（Parallel databases）和主存數(shù)據(jù)庫(kù)?[13]（main-memory databases）已經(jīng)在可擴(kuò)展性和高性能方面取得了很大成功， （Bigtable 也關(guān)注這兩方面，但除此之外，）Bigtable 提供的接口與它們不同。

Bigtable 不支持完整的關(guān)系型數(shù)據(jù)模型（full relational data model）；

• 它提供給客戶(hù)端的是一個(gè)簡(jiǎn)單數(shù)據(jù)模型（simple data model），
• 支持動(dòng)態(tài)控制數(shù)據(jù)的布局和格式（layout and format），并允許客戶(hù)端推測(cè)數(shù)據(jù)在底層存儲(chǔ)中的 locality（本地性）特性。
• 數(shù)據(jù)使用行名和列名（row and column names）進(jìn)行索引，這些名字可以是任意字符串（strings）。

Bigtable?不理解數(shù)據(jù)的內(nèi)容（將數(shù)據(jù)視為 uninterpreted strings）， 雖然很多字符串都是客戶(hù)端將各種結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)（structured and semi-structured data） 序列化而來(lái)的?？蛻?hù)端可以通過(guò)精心選擇 schema 來(lái)控制數(shù)據(jù)的 locality。schema 參數(shù)還可以讓客戶(hù)端動(dòng)態(tài)控制數(shù)據(jù)是從內(nèi)存還是磁盤(pán)讀取（serve）。

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

一個(gè) Bigtable 就是一個(gè)稀疏、分布式、持久的多維有序映射表（map），

• 數(shù)據(jù)通過(guò)行鍵、列鍵和一個(gè)時(shí)間戳進(jìn)行索引，
• 表中的每個(gè)數(shù)據(jù)項(xiàng)都是不作理解的字節(jié)數(shù)組，
• 映射：(row:string, column:string, time:int64) -> string

A Bigtable is a sparse, distributed, persistent multidimensional sorted map. The map is indexed by a row key, column key, and a timestamp; each value in the map is an uninterpreted array of bytes.

我們首先評(píng)估了類(lèi)似 Bigtable 這樣的系統(tǒng)有哪些潛在的使用場(chǎng)景，然后才確定了數(shù)據(jù)模型。 舉個(gè)具體例子，這個(gè)例子也影響了 Bigtable 的一些設(shè)計(jì)：我們想保存大量的網(wǎng)頁(yè) 和網(wǎng)頁(yè)相關(guān)的元數(shù)據(jù)，這些數(shù)據(jù)會(huì)被不同的項(xiàng)目使用，這里將這張表稱(chēng)為?Webtable。

在?Webtable?中，我們用網(wǎng)頁(yè)的 URL 作為行鍵，網(wǎng)頁(yè)某些信息作為列鍵，將網(wǎng)頁(yè)內(nèi)容存 儲(chǔ)在?contents:?列，并記錄抓取網(wǎng)頁(yè)時(shí)對(duì)應(yīng)的時(shí)間戳，最終存儲(chǔ)布局如圖 1 所示。

圖 1 存儲(chǔ)網(wǎng)頁(yè)的 bigtable 的一個(gè)切片（slice）

• 行索引：URL
• contents:?列：存儲(chǔ)頁(yè)面內(nèi)容（page content）
• anchor:?開(kāi)頭的列：存儲(chǔ)引用了這個(gè)頁(yè)面的 anchor（HTML 錨點(diǎn)）的文本（text of the anchors that reference this page）

圖中可以看出，CNN 主頁(yè)被 Sports Illustrated（cnnsi.com）和 MY-look 主頁(yè)（?my.look.ca）引用了，因此會(huì)有?anchor:cnnsi.com?和?anchor:my.look.ca?兩列，其 中每列一個(gè)版本；contents:?列有三個(gè)版本，時(shí)間戳分別為?t3、t5?和?t6。

2.1 行（Row）

行鍵（row key）可以是任意字符串（目前最大支持 64KB，大部分用戶(hù)使用的 key 都在 10-100 字節(jié)之間）。

單行數(shù)據(jù)的讀/寫(xiě)操作是原子的（不管該行有多少列參與讀/寫(xiě)），這樣的設(shè)計(jì)使得多 個(gè)客戶(hù)端并發(fā)更新同一行時(shí)，更容易推斷系統(tǒng)的行為。

Bigtable 中的數(shù)據(jù)是根據(jù)行鍵的詞典順序（lexicographic order）組織的，并動(dòng)態(tài) 地對(duì)行范圍（row range）進(jìn)行切分（partition）。

每個(gè)行范圍稱(chēng)為一個(gè) tablet，這是請(qǐng)求分散和負(fù)載均衡的單位（unit of distribution and load balancing）。因此，讀取一個(gè)較小的行范圍（short row ranges）是很高效的，通常情況下只需要和很少的幾臺(tái)機(jī)器通信。客戶(hù)端可以利用這個(gè)特 性，通過(guò)合理的選擇行鍵來(lái)在訪(fǎng)問(wèn)數(shù)據(jù)時(shí)獲得更好 locality。

舉個(gè)例子，在 Webtable 中，將 URL 的 hostname 字段進(jìn)行翻轉(zhuǎn)，來(lái)自相同域（domain） 的頁(yè)面在存儲(chǔ)時(shí)就會(huì)變成連續(xù)的行。例如?maps.google.com/index.html?頁(yè)面在存儲(chǔ)時(shí)行 鍵就是?com.google.maps/index.html。來(lái)自相同域的頁(yè)面存儲(chǔ)到連續(xù)的行，會(huì)使那 些針對(duì)主機(jī)和域的分析（host and domain analyses）非常高效。

2.2 Column Families（列族）

多個(gè) column keys 可以組織成?column families（列族）。 column family 是訪(fǎng)問(wèn)控制（access control）的基本單位。

2.2.1 設(shè)計(jì)

一般來(lái)說(shuō)，存儲(chǔ)在同一 column family 內(nèi)的數(shù)據(jù)，類(lèi)型都是相同的， （我們會(huì)將同一 column family 內(nèi)的數(shù)據(jù)壓縮到一起），

• 先創(chuàng)建一個(gè) column family，才能向這個(gè) column family 內(nèi)的列寫(xiě)入數(shù)據(jù)；創(chuàng)建完成后，就可以在這個(gè) family 內(nèi)使用任何的列鍵；
• 我們有意使得每個(gè) table 內(nèi)的?column family 數(shù)量盡量少（最多幾百個(gè)），并且在隨后的過(guò)程中 family 很少有變化。
• 另一方面，每個(gè) table 的?column 數(shù)量并沒(méi)有限制。

2.2.2 column key 的格式：family:qualifier

其中，

• family?必須為可打印的（printable）字符串，
• qualifier（修飾符）可以為任意字符串。

圖 1 存儲(chǔ)網(wǎng)頁(yè)的 bigtable 的一個(gè)切片（slice）

例如，

1. Webtable 中有一個(gè) column family 是語(yǔ)言（language），用來(lái)標(biāo)記每個(gè)網(wǎng)頁(yè)分別是用什么語(yǔ)言寫(xiě)的。 在這個(gè) column family 中我們只用了一個(gè)列鍵，其中存儲(chǔ)的是每種語(yǔ)言的 ID。
2. Webtable 中的另一個(gè) column family 是 anchor，在這個(gè) family 中每一個(gè)列鍵都表示一 個(gè)獨(dú)立的 anchor，如圖 1 所示，其中的修飾符（qualifier）是引用這個(gè)網(wǎng)頁(yè)的 anchor 名字，對(duì)應(yīng)的數(shù)據(jù)項(xiàng)內(nèi)容是鏈接的文本（link text）。

2.2.3 訪(fǎng)問(wèn)控制和磁盤(pán)/內(nèi)存記賬（accounting）都是在 column family 層做的

還是以 Webtable 為例，這種級(jí)別的控制可以使我們管理幾種不同類(lèi)型的應(yīng)用： 有的只添加新的基礎(chǔ)數(shù)據(jù)進(jìn)來(lái)，有的讀取基礎(chǔ)數(shù)據(jù)后創(chuàng)建衍生的 column family， 有的只允許查看當(dāng)前的數(shù)據(jù)（甚至可以根據(jù)保密程度只允許查看一部分 column family）。

2.3 時(shí)間戳

Bigtable 中的每個(gè)數(shù)據(jù)都可以存儲(chǔ)多個(gè)版本，不同版本用時(shí)間戳索引。

時(shí)間戳是 64 位整數(shù)，

• 可以由 Bigtable 指定，這種情況下就是毫秒（ms）級(jí)的真實(shí)時(shí)間戳；
• 也可以由客戶(hù)端應(yīng)用指定，為了避免沖突，應(yīng)用必須保證時(shí)間戳的唯一性。

同一數(shù)據(jù)的不同版本以時(shí)間戳降序（decreasing timestamp order）的方式存儲(chǔ)，這樣 首先讀到的都是最新的版本。

為避免版本化數(shù)據(jù)的管理過(guò)于繁瑣，我們提供了兩個(gè)配置參數(shù)可以讓 Bigtable 自動(dòng)進(jìn)行垃圾回收（GC）。 客戶(hù)端可以指定：

• 保留最后的 N 個(gè)版本
• 保留最近的某段時(shí)間內(nèi)的版本（例如，只保留過(guò)去 7 天寫(xiě)入的版本）

在 Webtable 中，每個(gè)頁(yè)面的時(shí)間戳是該頁(yè)面被爬取時(shí)的時(shí)間，我們?cè)O(shè)置只保留最后的 3 個(gè)版本。

3 API

Bigtable API 提供了創(chuàng)建、刪除 table 和 column family 的功能。另外，它還提供了更 改集群、table 和 column family 元數(shù)據(jù)的能力，例如訪(fǎng)問(wèn)控制權(quán)限。

客戶(hù)端應(yīng)用可以讀/寫(xiě) Bigtable 中的值，從指定行中查找值，或者對(duì) table 內(nèi)的一個(gè)數(shù)據(jù) 子集進(jìn)行遍歷。

圖 2 是向 Bigtable 寫(xiě)數(shù)據(jù)的一段 C++ 代碼，使用了?RowMutation?抽象來(lái)執(zhí)行一系列 更新操作。為保持代碼簡(jiǎn)潔，例子中去掉了一些無(wú)關(guān)的技術(shù)細(xì)節(jié)。

圖 2 Writing to Bigtable

Apply()?向 Webtable 執(zhí)行一次原子操作，其中包括：添加一個(gè) anchor 到?www.cnn.com，刪除另一個(gè) anchor。

圖 3 是另一個(gè)例子，使用一個(gè)?Scanner?抽象對(duì)一行內(nèi)的所有 anchor 進(jìn)行遍歷。

圖 3 Reading from Bigtable

客戶(hù)端可以在多個(gè) column family 上進(jìn)行遍歷，這里有幾種限制 scan 產(chǎn)生的行、列和時(shí) 間戳的機(jī)制。 例如，可以指定以上 scan 只產(chǎn)生列鍵能匹配正則表達(dá)式?anchor:*.cnn.com?的 anchors， 或者時(shí)間戳在最近 10 天內(nèi)的 anchor。

Bigtable 還提供其他的一些特性，使得用戶(hù)可以對(duì)數(shù)據(jù)進(jìn)行更復(fù)雜的控制。

首先，提供了單行事務(wù)（single-row transaction），可以對(duì)單行內(nèi)的數(shù)據(jù)執(zhí)行原子的 “讀-修改-寫(xiě)”（read-modify-write）序列操作。但 Bigtable 目前并不支持通用的跨行事 務(wù)（general transactions across row keys），雖然它提供了在客戶(hù)端側(cè)進(jìn)行跨行批量 寫(xiě)（batching writes across row keys）的接口。

第二，允許將 cell（table 中的一個(gè)格子）當(dāng)整型計(jì)數(shù)器用。

最后，支持在服務(wù)端執(zhí)行由客戶(hù)端提供的腳本。腳本使用的是 Google 為數(shù)據(jù)處理開(kāi)發(fā)的 稱(chēng)為 Aawzall [28] 的語(yǔ)言。目前這套基于 Sawzall 的 API 不允許客戶(hù)端腳本將數(shù)據(jù)回寫(xiě) 到 Bigtable，但它們可以進(jìn)行各種形式的數(shù)據(jù)變換、計(jì)算、求和等等。

Bigtable 可以和 MapReduce [12] 一起使用，后者是 Google 開(kāi)發(fā)的一個(gè)大規(guī)模并行計(jì)算框架。 我們寫(xiě)了一些封裝函數(shù)，將 Bigtable 用作 MapReduce job 的輸入源和輸出目標(biāo)。

4 外部系統(tǒng)依賴(lài)（Building Blocks）

Bigtable 構(gòu)建在其他幾個(gè) Google 的基礎(chǔ)設(shè)施之上。

• GFS
• SSTable
• Chubby

4.1 GFS

Bigtable 使用分布式文件系統(tǒng) GFS（Google File System）[17] 存儲(chǔ)日志和數(shù)據(jù)文件。

Bigtable 集群通常和其他一些分布式應(yīng)用共享一個(gè)服務(wù)器資源池（pool of machines），而且?Bigtable 進(jìn)程經(jīng)常和其他應(yīng)用混跑在同一臺(tái)機(jī)器上。

Bigtable 依賴(lài)一個(gè)集群管理系統(tǒng)來(lái)調(diào)度任務(wù)、管理共享的機(jī)器上的資源、處理機(jī)器故障， 以及監(jiān)控機(jī)器狀態(tài)。

4.2 SSTable

Bigtable?內(nèi)部使用 Google 的 SSTable 格式存儲(chǔ)數(shù)據(jù)。

SSTable 是一個(gè)持久化的、有序的、不可變的映射表（map），

• 鍵和值都可以是任意字節(jié)字符串。
• 提供了按 key 查詢(xún)和對(duì)指定的 key range 進(jìn)行遍歷的操作。

An SSTable provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings.

在內(nèi)部，每個(gè) SSTable 都包含一系列的?blocks（通常每個(gè) block 64KB，但這個(gè)參數(shù) 可配置）。

block 用?block index（存儲(chǔ)在 SSTable 的末尾）來(lái)定位，block index 會(huì)在打開(kāi) SSTable 的時(shí)候加載到內(nèi)存。

一次查詢(xún)操作只需要一次磁盤(pán)尋址（disk seek）：首先在內(nèi)存中通過(guò)二分查找（ binary search）找到 block index，然后定位到 block 在磁盤(pán)中的位置，從磁盤(pán)?讀取相應(yīng)的數(shù)據(jù)。另外，也可以將整個(gè) SSTable 映射到內(nèi)存，這樣查詢(xún)就完全不需要 磁盤(pán)操作了。

4.3 Chuby

Bigtable 依賴(lài) Chubby —— 一個(gè)高可用、持久的分布式鎖服務(wù)（a highly-available and persistent distributed lock service） [8]。

一個(gè) Chubby 服務(wù)由?5 個(gè)活躍副本（active replicas）組成，其中一個(gè)會(huì)被選舉為 master，并負(fù)責(zé)處理請(qǐng)求。只有大多數(shù)副本都活著，并且互相之間可以通信時(shí)，這個(gè)服務(wù)才 算活著（live）。

在遇到故障時(shí)，Chubby 使用 Paxos 算法 [9, 23] 保證副本之間的一致性。

Chubby 提供了一個(gè)包含目錄和小文件的命名空間（namespace），每個(gè)目錄或文件都 可以作為一個(gè)鎖，讀或?qū)懸粋€(gè)文件是原子的。

Chubby 客戶(hù)端庫(kù)維護(hù)了一份這些文件的一致性緩存（consistent caching）。每個(gè) Chubby 客戶(hù)端都會(huì)和 Chubby 服務(wù)維持一個(gè) session。當(dāng)一個(gè)客戶(hù)端的租約（lease）到期 并且無(wú)法續(xù)約（renew）時(shí)，這個(gè) session 就失效了。session 失效后會(huì)失去它之前的鎖 和打開(kāi)的文件句柄（handle）。Chubby 客戶(hù)端還可以在 Chubby 文件和目錄上注冊(cè)回調(diào) 函數(shù)，當(dāng)文件/目錄有變化或者 session 過(guò)期時(shí)，就會(huì)收到通知。

Bigtable 使用 Chubby 完成很多不同類(lèi)型的工作：

1. 保證任何時(shí)間最多只有一個(gè) active master
2. 存儲(chǔ) Bigtable 數(shù)據(jù)的 bootstrap location（見(jiàn) 5.1）
3. tablet 服務(wù)發(fā)現(xiàn)和服務(wù)終止清理工作（見(jiàn) 5.2）
4. 存儲(chǔ) Bigtable schema 信息（每個(gè) table 的 column family 信息）
5. 存儲(chǔ)訪(fǎng)問(wèn)控制列表

如果 Chubby 服務(wù)不可用超過(guò)一段時(shí)間，Bigtable 也將變得不可用。我們近期對(duì) 14 個(gè) Bigtable 集群（總共依賴(lài) 11 個(gè) Chubby 集群）的測(cè)量顯示，由于 Chubby 不可用（網(wǎng)絡(luò) 或 Chubby 本身問(wèn)題引起的） 導(dǎo)致的 Bigtable 不可用時(shí)間（數(shù)據(jù)在 Bigtable 中但無(wú)法訪(fǎng) 問(wèn)）百分比平均為?0.0047%，受影響最大的那個(gè)集群為?0.0326%。

5 實(shí)現(xiàn)

5.0 組件

Bigtable 主要由三個(gè)組件構(gòu)成：

1. 一個(gè)客戶(hù)端庫(kù)，會(huì)鏈接到每個(gè)客戶(hù)端

2. 一個(gè) master server。master 負(fù)責(zé)：

   1. 將 tablet 分配給 tablet server
   2. 檢測(cè) tablet server 的過(guò)期（expiration）及新加（addition）事件
   3. 平衡 tablet server 負(fù)載
   4. 垃圾回收（GC）
   5. 處理 schema 變動(dòng)，例如 table 和 column family 的創(chuàng)建

3. 多個(gè) tablet server

   1. 每個(gè) tablet server?管理一組 tablets（一般 10～1000 個(gè)）。
   2. tablet server 管理這些 tablet 的讀寫(xiě)請(qǐng)求，并且當(dāng) tablet 太大時(shí)，還負(fù)責(zé)對(duì)它們進(jìn)行切分（split）。
   3. 可以根據(jù)系統(tǒng)負(fù)載動(dòng)態(tài)地向集群添加或刪除 tablet server。

和很多單 master（single master）分布式存儲(chǔ)系統(tǒng)一樣 [17, 21]，?客戶(hù)端數(shù)據(jù)不經(jīng)過(guò) master 節(jié)點(diǎn)：讀寫(xiě)請(qǐng)求直接到 tablet server。 由于客戶(hù)端不依賴(lài) master 就能確定 tablet 位置信息，因此大部分客戶(hù)端從來(lái)不和 master 通信。因此，實(shí)際中 master 節(jié)點(diǎn)的負(fù)載很低。

每個(gè) Bigtable 集群會(huì)有很多張 table，每張 table 會(huì)有很多 tablets，每個(gè) tablets 包 含一個(gè) row range（行鍵范圍）內(nèi)的全部數(shù)據(jù)。 初始時(shí)每個(gè) table 只包含一個(gè) tablet。當(dāng) table 逐漸變大時(shí)，它會(huì)自動(dòng)分裂成多個(gè) tablets，默認(rèn)情況下每個(gè) tablet 大約 100-200MB。

5.1 Tablet 位置

服務(wù)端

我們使用一個(gè)和 B+ 樹(shù) [10] 類(lèi)似的三級(jí)結(jié)構(gòu)（three level hierarchy）來(lái)存儲(chǔ) tablet 位置信息，如圖 4 所示。

圖 4 Tablet location hierarchy

• 第一級(jí)：Chubby 中的一個(gè)文件
• 第二級(jí)：METADATA tables（第一個(gè)?METADATA?table 比較特殊，所以在圖中單獨(dú)畫(huà) 出，但它其實(shí)和其他?METADATA?table 都屬于第二級(jí)）
• 第三級(jí)：user tablets

METADATA?是一個(gè)特殊的 tablet，其中的第一個(gè) tablet 稱(chēng)為?root tablet。root tablet 和?METADATA?內(nèi)其他 tablet 不同之處在于：它永遠(yuǎn)不會(huì)分裂（split），這 樣就可以保證 tablet location 層級(jí)不會(huì)超過(guò)三層。

三級(jí)間的關(guān)系：

• Chubby 中的文件保存了 root tablet 的位置
• root tablet 保存了?METADATA?table 內(nèi)所有其他 table 的位置
• 每個(gè)?METADATA?tablet（root tablet 除外）保存了一組 user tablet 的位置

METADATA?table 存儲(chǔ) user tablet 位置信息的方式（假設(shè) user table 名為?UserTableX）：

• value：UserTableX?的位置
• key（row key）：UserTableX?的 table ID 和它的最后一行的某種編碼（encoding）

The METADATA table stores the location of a tablet under a row key that is an encoding of the tablet’s table identifier and its end row.

METADATA?的每行數(shù)據(jù)在內(nèi)存中大約占 1KB。如果將?METADATA?tablet 限制在?128MB?這樣一個(gè)中等大小，這種三級(jí)位置方案就可以存儲(chǔ)高達(dá)?2^34?個(gè) tablets（?128MB?=?2^17 * 1KB，即?METADATA?table 可以指向?2^17?個(gè) user table，每個(gè) user table 同樣是?128MB?的話(huà)，就有?2^17 * 2^17 = 2^34?個(gè) tablets，譯者注）。 如果每個(gè) tablet 128 MB 大小，那總數(shù)據(jù)量就高達(dá)?2^61?字節(jié)（128MB = 2^27 Byte，?2^34 * 2^27 = 2^61，即?2000PB）。

With a modest limit of 128 MB METADATA tablets, our three-level location scheme is sufficient to address 234 tablets (or 2^61 bytes in 128 MB tablets).

客戶(hù)端

客戶(hù)端庫(kù)會(huì)緩存 tablet 位置信息。 如果客戶(hù)端不知道 tablet 的位置，或者發(fā)現(xiàn)緩存的位置信息不對(duì)，它就會(huì)去訪(fǎng)問(wèn) table location 層級(jí)結(jié)構(gòu)，逐層向上（recursively moves up）。

如果客戶(hù)端的緩存是空的，位置算法需要三個(gè)網(wǎng)絡(luò)往返（round trip），其中包括一次 Chubby 讀取。如果客戶(hù)端緩存過(guò)期了，位置算法需要最多六次網(wǎng)絡(luò)往返，因?yàn)橹粫?huì)在 cache miss 的時(shí)候才會(huì)檢測(cè)緩存是否過(guò)期（假設(shè)?METADATA?tablets 移動(dòng)不是非常頻繁 ）。

雖然 tablet 位置放在內(nèi)存，不需要 GFS 操作，但是，我們可以通過(guò)客戶(hù)端預(yù)取（ prefetch）的方式繼續(xù)減少這里的開(kāi)銷(xiāo)：每次從?METADATA?table 讀取的時(shí)候，都讀取 多個(gè) tablet 的元數(shù)據(jù)。

另外，我們還在?METADATA?table 中存儲(chǔ)了其他一些次要信息，包括每個(gè) tablet 上的事件 的日志（例如使用這個(gè) tablet 的服務(wù)是何時(shí)啟動(dòng)的），這些信息對(duì) debug 和性能分析很 有用。

5.2 Tablet 分配

每個(gè) tablet 每次只會(huì)分配給一個(gè) tablet server。

master 會(huì)跟蹤活著的 tablet server 以及當(dāng)前 tablet 和 tablet server 的分配關(guān)系， 其中包括哪些 tablet 是還沒(méi)有被分配出去的。當(dāng)一個(gè) tablet 還沒(méi)有分配出去，并且找到 了一個(gè)有空閑資源的 tablet server，master 就會(huì)向這個(gè) server?發(fā)送一個(gè) tablet 加載 請(qǐng)求（load request），將這個(gè) tablet 分配給它。

Bigtable?使用 Chubby 跟蹤 tablet servers。當(dāng)一個(gè) tablet server 啟動(dòng)后，它會(huì)?在特定的 Chubby 目錄下創(chuàng)建和獲取一個(gè)名字唯一的獨(dú)占鎖（exclusive lock）。 master 通過(guò)監(jiān)聽(tīng)這個(gè)目錄（the?servers directory）來(lái)發(fā)現(xiàn) tablet servers?。

如果一個(gè) tablet server?失去了這個(gè)獨(dú)占鎖，例如由于網(wǎng)絡(luò)分裂導(dǎo)致 Chubby session 斷了，那這個(gè) server 會(huì)停止服務(wù)這個(gè) tablet。（Chubby 提供了一種高效機(jī)制使得 tablet server 無(wú)需產(chǎn)生網(wǎng)絡(luò)流量就可以判斷它自己是否還擁有鎖）。

tablet server 失去鎖之后，如果鎖文件還在，它會(huì)嘗試重新去獲取這個(gè)鎖；如果鎖 文件不在了，tablet server 會(huì)自殺（kill itself），因?yàn)樗鼰o(wú)法為這個(gè) tablet 提 供服務(wù)了。

tablet server 終止時(shí)（例如，由于集群管理系統(tǒng)將 tablet server 所在的機(jī)器移 除集群）會(huì)將它持有的鎖釋放，這樣 master 就可以及時(shí)將對(duì)應(yīng)的 tablets 分配給其他 tablet server。

master 負(fù)責(zé)檢測(cè) tablet server 是否工作正常，以及及時(shí)重新分配 tablets。

為了檢測(cè) tablet server 是否正常工作，master 會(huì)定期地詢(xún)問(wèn)每個(gè) tablet server 的鎖 的狀態(tài)。如果一個(gè) server 匯報(bào)說(shuō)鎖丟失了，或者如果 master 連續(xù) N 次無(wú)法連接到這個(gè) server，master 就會(huì)嘗試親自去獲取這個(gè)鎖文件。如果獲取鎖成功，說(shuō)明 Chubby 是活著的，那 master 就可以確定：要么是 tablet server 掛了，要么是它無(wú)法連 接到 Chubby，然后 master 就會(huì)刪掉這個(gè)鎖文件，以保證這個(gè) tablet server 不會(huì)再為這 個(gè) tablet 提供服務(wù)。刪除后，master 就將原來(lái)分配給這個(gè) tablet server 的 tablets 標(biāo)記為未分配的（unassigned）。

為了保證 Bigtable 不受 master 和 Chubby 之間的網(wǎng)絡(luò)問(wèn)題的影響，master 會(huì)在它的 Chubby session 過(guò)期時(shí)自殺。但如前面所描述的，master 掛掉不會(huì)影響 tablets 的 分配。

master 啟動(dòng)流程

當(dāng)一個(gè) master 被集群管理系統(tǒng)啟動(dòng)后，它必須先查看當(dāng)前的 tablet 分配情況，然后才能 去修改。

master 啟動(dòng)后所做的事情如下：

1. 從 Chubby 獲取一個(gè)唯一的?master?鎖，這樣為了避免并發(fā)的 master 實(shí)例化（instantiation）
2. 掃描 Chubby 中的?servers?目錄，查看當(dāng)前有哪些活著的 server
3. 和每個(gè)活著的 tablet server 通信，查看（discover）當(dāng)前分別給這些 tablet server 分 配了哪些 tablets
4. 掃描?METADATA?table，查看當(dāng)前有哪些 tablets（全部 tablets 都在這里）；掃描 過(guò)程中發(fā)現(xiàn)的還未被分配出去的 tablets，會(huì)添加到一個(gè)未分配 tables 集合，后面就 可以被重新分配出去

難點(diǎn)

以上過(guò)程的一個(gè)難點(diǎn)是：在掃描?METADATA?table 之前，必須保證?METADATA?tablets 自己已經(jīng)被分配出去了。

One complication is that the scan of the METADATA table cannot happen until the METADATA tablets have been assigned.

因此，如果在步驟 3 中發(fā)現(xiàn) root tablet 還沒(méi)有被分配出去，那 master 就要先將它放到 未分配 tablets 集合，然后去執(zhí)行步驟 4。 這樣就保證了 root tablet 將會(huì)被分配出去。

tablet 分裂和分裂后的新 tablet 發(fā)現(xiàn)

因?yàn)?root tablet 包含了所有?METADATA?tablet 的名字，因此 master 掃描 root tablet 之后就知道了當(dāng)前有哪些 tablets。

只有在發(fā)生以下情況時(shí)，當(dāng)前的 tablets 集合才會(huì)有變化：

1. 創(chuàng)建或刪除一個(gè) table
2. 兩個(gè) tablets 合并成一個(gè)更大的，或者一個(gè) tablet 分裂成兩個(gè)小的

master 能夠跟蹤這些變化，因?yàn)槌?tablet 分裂之外，其他流程都是由 master 處理的。tablet 分裂比較特殊，因?yàn)樗?strong>由 tablet server 發(fā)起的。

tablet server 將新的 tablet 信息記錄到?METADATA?table，然后提交這次分裂。提交 后，master 會(huì)收到通知。如果通知丟失（由于 tablet server 或 master 掛掉），master 會(huì)在它下次要求一個(gè) tablet server 加載 tablets 時(shí)發(fā)現(xiàn)。這個(gè) tablet server 會(huì)將這 次分裂信息通知給 master，因?yàn)樗?METADATA?table 中發(fā)現(xiàn)的 tablets 項(xiàng)只覆蓋 master 要求它加載的 tablets 的了一部分。

5.3 為 tablet 提供服務(wù)（Tablet Serving）

tablet 的持久狀態(tài)存儲(chǔ)在 GFS 中，如圖 5 所示。

圖 5 Reading from Bigtable

更新（update）會(huì)提交到一個(gè) commit log 文件，其中保存了 redo 記錄。 最近的幾次更新會(huì)存儲(chǔ)在內(nèi)存中一個(gè)稱(chēng)為?sstable?的有序緩沖區(qū)（ sorted buffer）中；其他老一些的更新存儲(chǔ)在 SSTable 中。

tablet 恢復(fù)

恢復(fù)一個(gè) tablet 時(shí)，tablet server 需要從?METADATA?table 讀取它的元數(shù)據(jù)。

這里的元數(shù)據(jù)包括：

1. 組成這個(gè) tablet 的 SSTable 列表
2. 一系列 redo 點(diǎn)，指向 commit log 中 tablet 的數(shù)據(jù)

tablet server?將 SSTable 索引讀到內(nèi)存，然后應(yīng)用 redo 點(diǎn)之后提交的所有更新， 就可以重建 memtable。

寫(xiě)操作

當(dāng)一個(gè)寫(xiě)操作到達(dá) tablet server 時(shí)，它會(huì)檢查寫(xiě)操作是否格式正確（well-formed），以 及發(fā)送者是否有權(quán)限執(zhí)行這次操作。

鑒權(quán)的實(shí)現(xiàn)方式是：從 Chubby 文件讀取允許的寫(xiě)者列表（writer list）（在絕大多 數(shù)情況下，這次讀都會(huì)命中 Chubby 客戶(hù)端的緩存）。

一次合法的寫(xiě)操作會(huì)記錄到 commit log。為了提高小文件寫(xiě)入的吞吐，我們使用了批量 提交（group commit）技術(shù) [13, 16]。寫(xiě)操作被提交后，它的內(nèi)容（數(shù)據(jù)）就會(huì)/才會(huì) 插入到 memtable。

讀操作

一次讀操作到達(dá) tablet server 時(shí)，也會(huì)執(zhí)行類(lèi)似的格式檢查和鑒權(quán)。

合法的讀操作是在 SSTable 和 memtable 的合并視圖上進(jìn)行的（executed on a merged view of the sequence of SSTables and the memtable）。 由于 SSTable 和 memtable 都是按詞典順序排序的，因此合并視圖的創(chuàng)建很高效。

在 tablet 分裂或合并時(shí)，讀或?qū)懖僮魅匀皇强梢赃M(jìn)行的。

5.4 壓縮（Compactions）

• minor compaction
• major compaction

隨著寫(xiě)操作的增多，memtable 在不斷變大。memtable 超過(guò)一定大小時(shí)會(huì)被凍結(jié)（ frozen），然后創(chuàng)建一個(gè)新的 memtable 來(lái)接受寫(xiě)入，凍結(jié)的 memtable 會(huì)轉(zhuǎn)化成 SSTable 寫(xiě)入 GFS，這稱(chēng)為?minor compaction。

minor compaction 有兩個(gè)目的：

1. 減少 tablet server 占用的內(nèi)存
2. tablet server 掛掉之后恢復(fù)時(shí)，減少?gòu)?commit log 讀取的數(shù)據(jù)量

在 compaction 的過(guò)程中，讀和寫(xiě)操作是可以正常進(jìn)行的。

每次 minor compaction 都會(huì)創(chuàng)建一個(gè)新 SSTable，如果不加額外處理，后面的讀操作可能 就需要將多個(gè) SSTable 進(jìn)行合并才能讀到需要的內(nèi)容。

因此，我們?cè)诤笈_(tái)定期地執(zhí)行一個(gè)?merge compaction，這樣就可以保證文件（SSTable ）數(shù)量保持在一個(gè)范圍內(nèi)。合并壓縮讀取若干個(gè) SSTable 和?memtable?的內(nèi)容，然后寫(xiě)到 一個(gè)新的 SSTable。寫(xiě)入完成后，原來(lái)的 SSTable 和 memtable 的內(nèi)容就可以刪掉了。這 種將多個(gè) SSTable 重寫(xiě)成一個(gè)的 merge compaction 就稱(chēng)為?major compaction。

非 major compaction 產(chǎn)生的 SSTable 會(huì)包含特殊的刪除信息（deletion entries） ，用于標(biāo)記其中已經(jīng)被刪除的數(shù)據(jù) —— 實(shí)際上這些數(shù)據(jù)還沒(méi)有被真正刪除，只是標(biāo)記為已刪 除。而?major compaction 產(chǎn)生的 SSTable 不會(huì)包含這些刪除信息或者已刪除的數(shù)據(jù)?（deletion information or deleted data）。

Bigtable 定期地遍歷所有 tablets，執(zhí)行 major compaction 操作。這使得 Bigtable 可 以及時(shí)回收已（被標(biāo)記為）刪除的數(shù)據(jù)占用的資源，而且可以保證已（被標(biāo)記為）刪除 的數(shù)據(jù)及時(shí)從系統(tǒng)中消失，這對(duì)于存儲(chǔ)敏感數(shù)據(jù)的服務(wù)來(lái)說(shuō)是很重要的。

6 改進(jìn)（Refinements）

以上描述的實(shí)現(xiàn)需要一些改進(jìn)才能滿(mǎn)足我們的用戶(hù)所需的高性能、可用性和可靠性。

本節(jié)將更深入地介紹幾個(gè)實(shí)現(xiàn)部分，以此來(lái)展示這些需求。

6.1 Locality groups

客戶(hù)端可以將多個(gè) column family 組織到一個(gè) locality group。 每個(gè) tablet 會(huì)為每個(gè) locality group 生成一個(gè)單獨(dú)的 SSTable。

將一般不會(huì)一起訪(fǎng)問(wèn)的 column family 劃分到不同的 locality group 會(huì)提升讀性能?。例如，Webtable 中的頁(yè)面元數(shù)據(jù)（例如語(yǔ)言和校驗(yàn)和）可以放到同一個(gè) locality group ，而將頁(yè)面內(nèi)容放到另一個(gè) locality group：應(yīng)用讀取元數(shù)據(jù)的時(shí)候就不需要再讀取整個(gè) 頁(yè)面內(nèi)容。

此外，還可以基于 locality group 維度對(duì)某些參數(shù)進(jìn)行調(diào)優(yōu)。例如，可以聲明一個(gè) locality group 是駐留內(nèi)存的（in-memory）。駐留內(nèi)存的 locality group 對(duì)應(yīng)的 SSTable 會(huì)被惰性加載到 tablet server 的內(nèi)存。 一旦加載，這類(lèi) column family 的讀 操作就不再需要訪(fǎng)問(wèn)磁盤(pán)。這個(gè)特性對(duì)訪(fǎng)問(wèn)頻繁的小文件非常有用：METADATA?table 的?location?column family 內(nèi)部用的就是這種類(lèi)型。

6.2 壓縮（Compression）

客戶(hù)端可以控制 SSTable 是否需要壓縮，以及用什么格式壓縮。

6.2.1 壓縮的粒度和算法

壓縮的基本單位是 SSTable block（大小可以由 locality group 的參數(shù)控制）。 雖然 block 級(jí)別的壓縮（相對(duì)于更大的數(shù)據(jù)級(jí)別）損失了一些壓縮效率，但在只需讀取 部分內(nèi)容時(shí)，我們不需要解壓整個(gè)文件，從而提高了讀效率。

我們的很多客戶(hù)端都使用一種自定義的 two-pass（兩遍）壓縮算法：

1. 先使用 Bentley-McIlroy 算法 [6] 壓縮大窗口內(nèi)的長(zhǎng)公共前綴（long common strings across a large window）
2. 再使用一個(gè)快速算法壓縮 16KB 窗口內(nèi)的重復(fù)字符串

在現(xiàn)代計(jì)算機(jī)上，這兩個(gè)算法都非?？?#xff0c;壓縮速度可以達(dá)到 100~200 MB/s，解壓可以達(dá)到 400~1000 MB/s。

6.2.2 壓縮的速度和效率

雖然相比于壓縮效率我們更看重壓縮速度，但令人驚奇的是，我們的雙通壓縮算法效率非常 好。

例如，在 Webtable 中，我們存儲(chǔ)了大量的頁(yè)面進(jìn)行了一次實(shí)驗(yàn)。實(shí)驗(yàn)中每個(gè)頁(yè)面只存儲(chǔ)了 一個(gè)版本。結(jié)果顯示，這個(gè)算法的壓縮比達(dá)到了 10:1，而典型情況下 Gzip 壓縮 HTML 頁(yè) 面只有 3:1 或 4:1 的效率。

這么高的壓縮效率來(lái)自 Webtable 的行（row）組織方式：來(lái)自相同域名（host）的頁(yè) 面都存儲(chǔ)在一起。這些頁(yè)面有著很多類(lèi)似內(nèi)容（模板），非常適合 Bentley-McIlroy 算法 。不止是 Webtable，很多應(yīng)用都根據(jù)行名（row names）將相似的數(shù)據(jù)組織到一起進(jìn)行存儲(chǔ) ，因此可以取得非常好的壓縮比。如果數(shù)據(jù)是存儲(chǔ)了多個(gè)版本而不是一個(gè)版本，那壓縮比會(huì) 更高。

6.3 讀緩存

為了提高讀性能，tablet server 使用了兩級(jí)緩存：

• Scan Cache
  • 高層緩存
  • 存儲(chǔ) SSTable 返回給 tablet server 的?key-value pair
  • 適用于頻繁訪(fǎng)問(wèn)相同數(shù)據(jù)的應(yīng)用
• Block Cache
  • 低層緩存
  • 存儲(chǔ)從 GFS 讀取的?SSTable blocks
  • 適用于連續(xù)訪(fǎng)問(wèn)相鄰（相近）數(shù)據(jù)的應(yīng)用。例如順序讀，或者在熱點(diǎn)行（hot row）中相同 locality group 內(nèi)不同列的隨機(jī)讀

6.4 Bloom 過(guò)濾器

5.3 介紹過(guò)，一次讀操作必須要對(duì)組成一個(gè) tablet 狀態(tài)的所有 SSTable 都進(jìn)行讀取。 如果這些 SSTable 沒(méi)有在內(nèi)存，我們就要進(jìn)行多次磁盤(pán)訪(fǎng)問(wèn)。我們?cè)试S客戶(hù)端在一個(gè)特殊的 locality group 內(nèi)指定要對(duì) SSTable 創(chuàng)建 Bloom 過(guò)濾器?[7]，

• Bloom 過(guò)濾器可以判斷一個(gè)?SSTable 是否包含指定行/列對(duì)（row/column pair）對(duì)應(yīng)的數(shù)據(jù)。
• 對(duì)于特定的應(yīng)用來(lái)說(shuō)，給 tablet server?增加少量?jī)?nèi)存用于存儲(chǔ) Bloom 過(guò)濾器，就可以極大地減少讀操作的磁盤(pán)訪(fǎng)問(wèn)。

我們的實(shí)際使用也顯示，大部分對(duì)不存在的行或列的訪(fǎng)問(wèn)都無(wú)需涉及磁盤(pán)操作（在 Bloom 過(guò)濾器這一層就判斷不存在了，無(wú)需再查找磁盤(pán)）。

6.5 Commit-log 實(shí)現(xiàn)

每個(gè) tablet 還是每個(gè) tablet server 一個(gè) log 文件

如果為每個(gè) tablet 維護(hù)一個(gè)單獨(dú)的 log 文件，那會(huì)導(dǎo)致底層 GFS 大量文件的并發(fā)寫(xiě)?？?慮到 GFS 的具體實(shí)現(xiàn)，這些并發(fā)寫(xiě)進(jìn)而會(huì)導(dǎo)致大量的磁盤(pán)訪(fǎng)問(wèn)，以完成不同物理文件的并 發(fā)寫(xiě)入。另外，每個(gè) tablet 一個(gè) log 文件的設(shè)計(jì)還會(huì)降低組提交（group commit，批量 提交）優(yōu)化的有效性，因?yàn)槊總€(gè)組（group）都會(huì)很小。

因此，為了克服以上問(wèn)題，我們?yōu)?strong>每個(gè) tablet server 維護(hù)一個(gè) commit log，將屬于 這個(gè) tablet server 的不同的 tablet 操作都寫(xiě)入這同一個(gè)物理上的 log 文件 [18, 20]。

恢復(fù)過(guò)程變復(fù)雜

這種方式使得常規(guī)操作（normal operations）的性能得到了很大提升，但是，它使 tablet 恢復(fù)過(guò)程變得復(fù)雜。

當(dāng)一個(gè) tablet server 掛掉后，它負(fù)責(zé)的那些 tablets 就會(huì)重新分配給其他（大量）的 tablet servers：通常情況下每個(gè) tablet server 只會(huì)分到其中的一小部分?；謴?fù)一個(gè) tablet 的狀態(tài)時(shí)，新的 tablet server 需要從原 tablet server 的 commit log 里重新 應(yīng)用（reapply）這個(gè) tablet 的修改（mutation）。然而，這些 tablet 的 mutation 都 混在同一個(gè)物理的 log 文件內(nèi)。

一種方式是每個(gè)新的 tablet server 都去讀完整的 commit log，將自己需要的部分過(guò)濾出 來(lái)。但是，如果有 100 個(gè)機(jī)器分到了 tablet 的話(huà)，這個(gè) log 文件就要被讀 100 次。

優(yōu)化：兩個(gè)寫(xiě)線(xiàn)程和兩份 commit log

為了避免這種重復(fù)讀，我們將 commit log 內(nèi)容以?(table; row name; log sequence number)?為鍵（key）進(jìn)行排序。在排序后的 commit log 中，每個(gè) tablet 的所有 mutation 都是連續(xù)的，因此可以實(shí)現(xiàn)高效的讀取：只需一次磁盤(pán)尋址加隨后的順序讀。 為了加速排序過(guò)程，我們還將 commit log 分割成 64 MB 的段（segment），分散到多個(gè) tablet server 上并發(fā)地進(jìn)行排序。

這個(gè)排序過(guò)程是由?master 協(xié)調(diào)（coordinate）、tablet server 觸發(fā)的： tablet server 向 master 匯報(bào)說(shuō)需要從一些 commit log 中恢復(fù)一些 mutation。

寫(xiě)提交記錄到 GFS 有時(shí)會(huì)遇到性能卡頓，這可能有多方面原因。例如，負(fù)責(zé)寫(xiě)操作的 GFS server 掛了，或者到三個(gè)指定的 GFS master 的網(wǎng)絡(luò)發(fā)生了擁塞或過(guò)載。為了減少這些 GFS 導(dǎo)致的延遲抖動(dòng)，每個(gè) tablet server 為 commit log 使用了兩個(gè)寫(xiě)線(xiàn)程：每個(gè) 線(xiàn)程寫(xiě)到各自的 log 文件，但同時(shí)只會(huì)有一個(gè)線(xiàn)程是活躍的。 如果當(dāng)前的活躍線(xiàn)程寫(xiě)性能非常差，寫(xiě)操作就會(huì)切換到另一個(gè)線(xiàn)程，由這個(gè)新線(xiàn)程負(fù)責(zé)之后 的寫(xiě)。

log 中的記錄（entry）都有序列號(hào)，恢復(fù)的時(shí)候可以根據(jù)序列號(hào)過(guò)濾由于 log 切換導(dǎo)致 的重復(fù)數(shù)據(jù)。

6.6 加速 tablet 恢復(fù)過(guò)程

如果 master 將一個(gè) tablet 從一個(gè) tablet server 移動(dòng)到另一個(gè)，源 tablet server 會(huì)先對(duì)這個(gè) tablet 進(jìn)行一次 minor compaction。 這會(huì)對(duì) commit log 里還未壓縮的狀態(tài)進(jìn)行一次壓縮，減少恢復(fù)時(shí)需要讀取的數(shù)據(jù)量。 這次壓縮完成后，源 tablet server 停止為這個(gè) tablet 提供服務(wù)。

源 tablet server 在真正卸載（unload）這個(gè) tablet 之前會(huì)再進(jìn)行一次（通常非?？斓?）minor compaction，對(duì)第一次 minor compaction 到當(dāng)前時(shí)刻內(nèi)新進(jìn)來(lái)的未壓縮狀態(tài)進(jìn)行 壓縮。這次壓縮做完之后，這個(gè) tablet 就可以被其他的 tablet server 加載（load）， 而無(wú)需恢復(fù)任何 log 記錄。

6.7 利用不可變性（Exploiting immutability）

除了 SSTable 緩存之外，Bigtable 系統(tǒng)其他一些部分也因 SSTable 的不可變性而得到簡(jiǎn) 化。例如，從 SSTable 讀取數(shù)據(jù)時(shí)，對(duì)文件系統(tǒng)的訪(fǎng)問(wèn)不需要任何同步。因此，對(duì)行的并 發(fā)控制可以實(shí)現(xiàn)地非常高效。

讀和寫(xiě)操作涉及的唯一可變數(shù)據(jù)結(jié)構(gòu)是 memtable。為減少 memtable 的讀競(jìng)爭(zhēng)，我們 將 memtable 的行（row）設(shè)計(jì)為寫(xiě)時(shí)復(fù)制（copy-on-write），這樣讀和寫(xiě)就可以并行 進(jìn)行。

因?yàn)?SSTable 是不可變的，所以徹底刪除數(shù)據(jù)（permanently removing deleted data ）的問(wèn)題就變成了對(duì)過(guò)期的 SSTable 進(jìn)行垃圾回收（garbage collecting obsolete SSTables）。

每個(gè) tablet 的 SSTable 會(huì)注冊(cè)到?METADATA?table。master 會(huì)對(duì)過(guò)期的 SSTable 進(jìn)行“先標(biāo)記后清除”（mark-and-sweep） [25]，其中?METADATA?table 記錄了這些 SSTable 的對(duì)應(yīng)的 tablet 的 root。

最后，SSTable 的不可變性使得 tablet 分裂過(guò)程更快。我們直接讓子 tablet 共享 父 tablet 的 SSTable ，而不是為每個(gè)子 tablet 分別創(chuàng)建一個(gè)新的 SSTable。

7 性能評(píng)估

7.0 準(zhǔn)備

測(cè)試環(huán)境

我們?cè)谝惶子?N 個(gè) tablet server 的 Bigtable 集群進(jìn)行測(cè)試，測(cè)量 N 變化時(shí) Bigtable 的性能和可擴(kuò)展性。

每個(gè) tablet server 使用 1GB 內(nèi)存，寫(xiě)到由 1786 臺(tái)節(jié)點(diǎn)組成的 GFS 集群，其中每個(gè)節(jié) 點(diǎn)配備了兩個(gè) 400GB 的 IDE 硬盤(pán)。

N 個(gè)客戶(hù)端生成 Bigtable 負(fù)載用于測(cè)試（用和 tablet server 同樣數(shù)量的客戶(hù)端是 為了保證客戶(hù)端不會(huì)稱(chēng)為性能瓶頸）。

每個(gè)機(jī)器有兩個(gè)雙核 Opteron 2 GHz 處理器，足夠的物理內(nèi)存，以及一個(gè) 1Gbps 以太網(wǎng)鏈 路。所有機(jī)器連接到一個(gè)兩級(jí)樹(shù)狀交換網(wǎng)絡(luò)（two-level tree-shaped switched network），網(wǎng)絡(luò)根節(jié)點(diǎn)有 100-200 Gbps 的聚合帶寬。所有機(jī)器都在同一個(gè)物理基礎(chǔ)設(shè)施 中，因此機(jī)器間的時(shí)延小于 1ms。

tablet server、master、測(cè)試用的客戶(hù)端，以及 GFS server 都運(yùn)行在相同的一組機(jī)器上 。本實(shí)驗(yàn)是在一個(gè)正常使用中的集群上進(jìn)行的，因此：

1. 每個(gè)機(jī)器都運(yùn)行了一個(gè) GFS server
2. 有的機(jī)器運(yùn)行了一個(gè) tablet server，或者一個(gè)客戶(hù)端進(jìn)程，或者其他與本實(shí)驗(yàn) 無(wú)關(guān)的工作任務(wù)

性能指標(biāo)

R?是測(cè)試中 Bigtable 的不重復(fù)行鍵（row key）數(shù)量。R?的選擇使得每個(gè)基準(zhǔn)測(cè)試 中每個(gè) tablet server 讀或?qū)懘蠹s 1GB 數(shù)據(jù)。

sequential write（順序?qū)?#xff09;將行空間等分成 10N 份，通過(guò)一個(gè)中心調(diào)度器分配給 N 個(gè) 客戶(hù)端，每個(gè)客戶(hù)端都是先拿到一份進(jìn)行處理，完成后調(diào)度器會(huì)再分給它一份，這種動(dòng)態(tài)分 配可以減少客戶(hù)端所在機(jī)器上的其他進(jìn)程對(duì)實(shí)驗(yàn)的影響。每一個(gè)行鍵對(duì)應(yīng)寫(xiě)一個(gè)字符串，字 符串是隨機(jī)生產(chǎn)的，因此無(wú)法壓縮（uncompressible）。另外，不同行鍵對(duì)應(yīng)的字符串是不 同的，因此也是無(wú)法跨行壓縮的。

random write（隨機(jī)寫(xiě)）基準(zhǔn)測(cè)試與順序?qū)戭?lèi)似，除了行鍵在寫(xiě)之前是對(duì)?R?取模的（ row key was hashed modulo R），因此寫(xiě)操作可以在整個(gè)測(cè)試期間都均勻地分散到整個(gè)行 空間。

sequential read（順序讀）生產(chǎn)行鍵的方式與順序?qū)戭?lèi)似，讀的也是順序?qū)憸y(cè)試寫(xiě)入的 數(shù)據(jù)。

random read（隨機(jī)讀）與隨機(jī)寫(xiě)類(lèi)似。

scan（掃描）和順序讀類(lèi)似，但利用了 Bigtable 提供的掃描給定行范圍內(nèi)的所有值?的 API。使用這個(gè) API 可以減少 RPC 的次數(shù)，因?yàn)橐淮?RPC 就可以從 tablet server 取 到大量的值。

random read (mem)?和順序讀類(lèi)似，但測(cè)試數(shù)據(jù)的 locality group 標(biāo)記為駐留內(nèi)存型（ in-memory），因此會(huì)從 tablet server 的內(nèi)存而不是 GFS 讀取。在這個(gè)測(cè)試中，我們將 每個(gè) tablet 的測(cè)試數(shù)據(jù)從 1GB 降到了 100MB，以充分保證它們能落到 tablet server 的 內(nèi)存中。

圖 6 以?xún)煞N視圖展示了讀/寫(xiě) 1000 字節(jié)的值到 Bigtable 時(shí)的性能。 左側(cè)是每個(gè) tablet server 每秒的操作數(shù)；右側(cè)是聚合之后的每秒操作數(shù)。

圖 6 讀/寫(xiě) 1000 字節(jié)的值到 Bigtable 時(shí)的性能

7.1 單 tablet-server 性能

首先看單個(gè) tablet server 的性能。

隨機(jī)讀比其他的操作都要慢一個(gè)數(shù)量級(jí)甚至更多。

每次隨機(jī)讀都需要將 64KB 的 SSTable block 從 GFS 通過(guò)網(wǎng)絡(luò)傳輸?shù)?tablet server， 而其中僅僅包含了一個(gè) 1000 字節(jié)的值。tablet server 每秒大約 1200 次讀操作，折 算約為?75 MB/s?從 GFS 讀數(shù)據(jù)。考慮到網(wǎng)絡(luò)棧、SSTable 解析、Bigtable 代碼等開(kāi) 銷(xiāo)，這個(gè)帶寬足以使 tablet server 的 CPU 達(dá)到飽和了，也足以使機(jī)器的網(wǎng)絡(luò)鏈路飽和了 （75 MB/s = 600 Mbps，系統(tǒng)總共 1Gbps 帶寬）。大部分這種訪(fǎng)問(wèn)類(lèi)型的 Bigtable 應(yīng)用 會(huì)將 block size 設(shè)置的更小，一般設(shè)為 8 KB。

從內(nèi)存的隨機(jī)讀會(huì)快很多，因?yàn)槊總€(gè) 1000 字節(jié)的讀都是從 tablet server 的本地內(nèi)存讀 取的，不需要從 GFS 訪(fǎng)問(wèn) 64KB 的 block。

隨機(jī)和順序?qū)懙男阅芏家入S機(jī)讀好，因?yàn)槊總€(gè) tablet server 會(huì)將所有寫(xiě)操作追加 到同一個(gè) commit log 然后執(zhí)行批量提交（group commit），從而高效地寫(xiě)入到 GFS。?隨機(jī)寫(xiě)和順序?qū)懙男阅懿](méi)有明顯差異，因?yàn)閮煞N情況下，所有到 tablet server 的 寫(xiě)最后都是到了同一個(gè) commit log。

順序讀的性能遠(yuǎn)好于隨機(jī)讀，因?yàn)槊總€(gè)從 GFS?預(yù)取（prefetch）的 64KB SSTable block 都存儲(chǔ)到了 blcok 緩存，下一次 64 讀請(qǐng)求就會(huì)用到。

掃描的性能更好，因?yàn)榭蛻?hù)端的一次 RPC 請(qǐng)求就可以從 tablet server 拿到大量的值，因 此 RPC 開(kāi)銷(xiāo)被平攤了。

7.2 擴(kuò)展性（scaling）

當(dāng)我們將系統(tǒng)中 tablet server 的數(shù)量從 1 增加到 500 時(shí)， 聚合吞吐量（aggregate throughput）的增長(zhǎng)非常明顯，超過(guò)了 100 倍。 例如，當(dāng) tablet server 數(shù)量增加到 500 倍時(shí)，random read (mem)?增長(zhǎng)了幾乎 300 倍。這是因?yàn)檫@個(gè)基準(zhǔn)測(cè)試的性能瓶頸在 tablet server 的 CPU。

但是，性能并沒(méi)有線(xiàn)性增長(zhǎng)。對(duì)于大部分基準(zhǔn)測(cè)試，在 tablet server 從 1 增加到 500 的過(guò)程中，單臺(tái) server 的吞吐量都有一個(gè)明顯的下降（圖 6 左邊的表）。這個(gè)下降 是由不同 server 配置導(dǎo)致的負(fù)載不均衡引起的，大部分情況下是由于機(jī)器上的其他進(jìn)程 在競(jìng)爭(zhēng) CPU 和網(wǎng)絡(luò)資源。

我們的負(fù)載均衡算法就是想解決這個(gè)問(wèn)題，但由于兩個(gè)主要原因無(wú)法做到完美：

1. 減少 tablet 的移動(dòng)會(huì)引起 rebalancing 的抖動(dòng)（tablet 在移動(dòng)的時(shí)候會(huì)有很短的一 段時(shí)間不可用，一般在 1 秒以下）
2. 基準(zhǔn)測(cè)試生成的負(fù)載會(huì)隨著測(cè)試的進(jìn)行而不斷漂移（shifts around）

隨機(jī)讀基準(zhǔn)測(cè)試的擴(kuò)展性最差（server 增加 500 倍時(shí)，它的聚合吞吐量只增加了 100 倍）。 前面解釋過(guò)，造成這個(gè)問(wèn)題的原因是對(duì)于每個(gè) 1000 字節(jié)的值，我們都需要通過(guò)網(wǎng)絡(luò)傳輸一 個(gè) 64KB 的 block。這個(gè)數(shù)據(jù)量使得我們與其他進(jìn)程共享的 1Gbps 網(wǎng)絡(luò)帶寬達(dá)到飽和，因 此隨著機(jī)器數(shù)量的增加，每節(jié)點(diǎn)平均吞吐量（per-server throughput）下降非常明顯。

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

截至 2006 年 8 月，Google 總共運(yùn)行著 388 個(gè)非測(cè)試的 Bigtable 集群，分布在不同的 數(shù)據(jù)中心，加起來(lái)有 24,500 個(gè) tablet server。

表 1 展示了這些集群中 tablet server 數(shù)量的大致分布：

表 1 Bigtable 集群中 tablet server 數(shù)量分布

其中一些集群是用于開(kāi)發(fā)目的，因此會(huì)有較長(zhǎng)時(shí)間的空閑狀態(tài)。

我們挑選了 14 個(gè)活躍集群，總共包含 8069 個(gè) tablet server，提供了如下聚合性能：

• 120 萬(wàn)次請(qǐng)求/秒（QPS）
• 741 MB/s RPC 入流量
• 16 GB/s RPC 出流量

圖 2 給出了目前在用的幾個(gè) table 的一些數(shù)據(jù)。

表 2 生產(chǎn)環(huán)境 Bigtable 的一些數(shù)據(jù)

一些 table 存儲(chǔ)的是給用戶(hù)使用的數(shù)據(jù)，另外一些存儲(chǔ)的是批處理用的數(shù)據(jù)。table 的 大小、平均 cell 大小、內(nèi)存中數(shù)據(jù)（served from memory）所占的比例、table schema 的復(fù)雜度等等差異都很大。在本節(jié)接下來(lái)的內(nèi)容中，我們將簡(jiǎn)要介紹產(chǎn)品團(tuán)隊(duì)是如何使用 Bigtable 的。

8.1 Google Analytics

Google Analytics (analytics.google.com) 是一個(gè)幫助網(wǎng)站管理員分析網(wǎng)站流量的服務(wù)。

它提供了很多聚合統(tǒng)計(jì)數(shù)據(jù)，例如每天的獨(dú)立訪(fǎng)問(wèn)量和每個(gè) URL 每天的訪(fǎng)問(wèn)量，以及網(wǎng)站 跟蹤報(bào)告，例如給定一組之前瀏覽了某個(gè)頁(yè)面的用戶(hù)，它可以給出實(shí)際發(fā)生了購(gòu)買(mǎi)行為的用 戶(hù)比例。

為了實(shí)現(xiàn)這些功能，網(wǎng)絡(luò)管理員需要在他們的網(wǎng)頁(yè)上嵌入一段 JavaScript 代碼。 這樣每當(dāng)這個(gè)網(wǎng)頁(yè)被訪(fǎng)問(wèn)時(shí)，這段程序就會(huì)被激活。它會(huì)記錄很多的信息，例如用戶(hù) ID 以 及頁(yè)面信息，發(fā)送給 Google Analytics，Google Analytics 會(huì)對(duì)這些信息進(jìn)行匯總，最后 呈現(xiàn)給網(wǎng)站管理員。

這里簡(jiǎn)要介紹 Google Analytics 使用的兩個(gè) table。

原始點(diǎn)擊（raw click）table（~200 TB）為每個(gè)用戶(hù)維護(hù)了一個(gè)（數(shù)據(jù)）行。行名是網(wǎng)站 名和 session 創(chuàng)建時(shí)間組成的一個(gè)元組（tuple）。這樣的 schema 保證了訪(fǎng)問(wèn)網(wǎng)站的 session 按照時(shí)間順序（chronologically）是連續(xù)的。這個(gè) table 壓縮到了原始大小的 14%。

匯總（summary）table（~20TB）存儲(chǔ)了每個(gè)網(wǎng)站的一些預(yù)定義的匯總。這個(gè) table 是通過(guò) 定期的 MapReduce 任務(wù)對(duì)原始點(diǎn)擊表進(jìn)行計(jì)算得到的。每個(gè) MapReduce 任務(wù)會(huì)從原始點(diǎn)擊 表中提取最近的 session 數(shù)據(jù)，系統(tǒng)整體的吞吐受限于 GFS 的吞吐。這個(gè)表壓縮到了原始 大小的 29%。

8.2 Google Earth

Google 提供了地球高精度衛(wèi)星圖服務(wù)給用戶(hù)，可以通過(guò)基于網(wǎng)頁(yè)的 Google Maps 接口（ maps.google.com）或客戶(hù)端軟件 Google Earth（earth.google.com）訪(fǎng)問(wèn)。這些產(chǎn)品允許 用戶(hù)在任何分辨率的衛(wèi)星圖上游走，停留、查看和標(biāo)注。

這個(gè)系統(tǒng)使用了一個(gè)表來(lái)做數(shù)據(jù)預(yù)處理，另外很多表來(lái)服務(wù)客戶(hù)端數(shù)據(jù)。預(yù)處理 pipeline 使用一個(gè)表來(lái)存儲(chǔ)原始圖像。預(yù)處理過(guò)程會(huì)將圖像進(jìn)行清洗和合并（clean and consolidate），變成可以提供服務(wù)的數(shù)據(jù)。這個(gè)表存儲(chǔ)了大約 70 TB 的數(shù)據(jù)，因此是放在 磁盤(pán)上的。另外這些圖像都已經(jīng)高效地壓縮過(guò)了，因此 Bigtable 的壓縮是關(guān)閉的。表的每 一行代表一個(gè) geographic segment（地理位置）。行名的設(shè)計(jì)使得地理上相鄰的 segment 在存儲(chǔ)的時(shí)候也是相鄰的。另外，這個(gè)表還包含一個(gè) column family，用來(lái)跟蹤每個(gè) segment 的數(shù)據(jù)來(lái)源（sources of data for each segment）。這個(gè) column family 有大 量的列：基本上每個(gè)原始數(shù)據(jù)圖像（raw data image）都有一列。因?yàn)槊總€(gè) segment 都是 用少量幾張圖像合成的，因此這個(gè) column family 非常稀疏。

預(yù)處理 pipeline 強(qiáng)烈依賴(lài) MapReduce 對(duì) Bigtable 內(nèi)的數(shù)據(jù)進(jìn)行變換。部分 MapReduce job 進(jìn)行時(shí)，系統(tǒng)整體可以達(dá)到每個(gè) tablet server 1MB/s 以上的數(shù)據(jù)處理速度。

服務(wù)系統(tǒng)使用一個(gè)表來(lái)索引存儲(chǔ)在 GFS 中的數(shù)據(jù)。這個(gè)表相對(duì)比較小（~500GB），但它必 須保證每個(gè)數(shù)據(jù)中心每秒幾萬(wàn)次請(qǐng)求（QPS）的負(fù)載下，仍然保持很低的延遲。因此，這個(gè) 表同時(shí)分散到了幾百個(gè) tablet server 上進(jìn)行處理，并且還包含了駐留內(nèi)存的 column family。

8.3 Personalized Search

Personalized Search（個(gè)性化搜索）(www.google.com/psearch)是一個(gè)自選的服務(wù)，它會(huì) 記錄用戶(hù)的搜索關(guān)鍵詞和在各種 Google 服務(wù)上的點(diǎn)擊，例如網(wǎng)頁(yè)搜索、圖像和新聞等等。 用戶(hù)可以通過(guò)瀏覽自己的搜索關(guān)鍵詞和點(diǎn)擊記錄來(lái)查看他們的搜索歷史，可以要求根據(jù) 自己過(guò)去的 Google 使用習(xí)慣來(lái)向他們提供個(gè)性化搜索結(jié)果。

個(gè)性化搜索將用戶(hù)數(shù)據(jù)存儲(chǔ)到 Bigtable。每個(gè)用戶(hù)有一個(gè)唯一的用戶(hù) ID，并根據(jù)這個(gè) ID 分配一個(gè)行名。所有的用戶(hù)動(dòng)作存儲(chǔ)在另一個(gè)表，每種類(lèi)型的動(dòng)作會(huì)占用一個(gè) column family（例如，有一個(gè) column family 存儲(chǔ)所有的網(wǎng)頁(yè)查詢(xún)）。每個(gè)數(shù)據(jù)用動(dòng)作發(fā)生的時(shí) 刻作為它在 Bigtable 中的時(shí)間戳。

個(gè)性化搜索利用 MapReduce 在 Bigtable 上進(jìn)行運(yùn)算，為每個(gè)用戶(hù)生成一個(gè) profile。 這些 profile 就會(huì)用來(lái)做個(gè)性化的實(shí)時(shí)搜索。

個(gè)性化搜索的數(shù)據(jù)會(huì)在幾個(gè) Bigtable 之間做復(fù)制，以提高可用性，減少客戶(hù)端距離導(dǎo)致的 延遲。這個(gè)團(tuán)隊(duì)最初在 Bigtable 之上開(kāi)發(fā)了自己的一套客戶(hù)端側(cè)復(fù)制機(jī)制，以保證所有副 本的最終一致性。現(xiàn)在，復(fù)制子系統(tǒng)已經(jīng)集成到服務(wù)端。

個(gè)性化搜索存儲(chǔ)系統(tǒng)的設(shè)計(jì)允許其他團(tuán)隊(duì)在他們各自的列中添加用戶(hù)級(jí)別的（per-user）信 息，這個(gè)系統(tǒng)現(xiàn)在被很多 Google 其他產(chǎn)品在使用，存儲(chǔ)他們自己的用戶(hù)級(jí)別的（per-user ）配置選項(xiàng)和設(shè)置。但在多個(gè)開(kāi)發(fā)團(tuán)隊(duì)之間共享一個(gè)表會(huì)導(dǎo)致數(shù)量異常龐大的 column family。

為了幫助共享，我們給 Bigtable 添加了一個(gè)簡(jiǎn)單的配額（quota）機(jī)制，限制單一客戶(hù)端 在一個(gè)共享表中所占的存儲(chǔ)大小。對(duì)于那些多個(gè)產(chǎn)品團(tuán)隊(duì)使用 Bigtable 存儲(chǔ)用戶(hù)級(jí)別信息 的場(chǎng)景，這種機(jī)制提供了一定的隔離性。

9 從中所學(xué)（Lessons）

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

9.1 故障源遠(yuǎn)比你想象中多

首先我們認(rèn)識(shí)到，大型分布式系統(tǒng)在很多方面的故障面前都很脆弱，不僅僅是很多分布式協(xié) 議所假設(shè)的網(wǎng)絡(luò)分裂和出錯(cuò)后停止服務(wù)（fail-stop failures）。例如，我們就遇到過(guò)如下 場(chǎng)景引起的故障：

• 內(nèi)存和網(wǎng)絡(luò)損壞
• 很大的時(shí)鐘偏差（clock skew）
• 機(jī)器死機(jī)（hung）
• 更復(fù)雜的和非對(duì)稱(chēng)的網(wǎng)絡(luò)分裂
• 依賴(lài)的基礎(chǔ)服務(wù)的 bug（例如 Chubby）
• GFS 配額溢出（overflow）
• 計(jì)劃及非計(jì)劃的硬件維護(hù)

隨著對(duì)這一問(wèn)題的了解的深入，我們開(kāi)始修改各種的協(xié)議來(lái)應(yīng)對(duì)這一問(wèn)題。例如，我們給 RPC 機(jī)制添加了校驗(yàn)和。

另外，我們還去掉了系統(tǒng)的一個(gè)部分對(duì)另一部分的假設(shè)。例如，我們不再假設(shè)一次 Chubby 操作只會(huì)返回固定的幾種錯(cuò)誤。

9.2 避免過(guò)早添加使用場(chǎng)景不明確的新特性

我們得到的另一重要經(jīng)驗(yàn)是：如果還不是非常清楚一個(gè)新特性將被如何使用，那就不要著急 添加到系統(tǒng)中。

例如，我們最初有計(jì)劃在 API 中支持廣義事物模型（general-purpose transaction）。但 因?yàn)楫?dāng)時(shí)沒(méi)有迫切的使用場(chǎng)景，因此沒(méi)有立即去實(shí)現(xiàn)?，F(xiàn)在有了很多真實(shí)應(yīng)用跑在 Bigtable 之后，我們審視了這些應(yīng)用的真實(shí)需求，發(fā)現(xiàn)大部分應(yīng)用其實(shí)只需要單行事務(wù)（single-row transaction）。

對(duì)于真的有分布式事務(wù)需求的人，我們發(fā)現(xiàn)他們最核心的需求其實(shí)是維護(hù)二級(jí)索引（ secondary indices），因此我們計(jì)劃通過(guò)添加一個(gè)特殊的機(jī)制來(lái)滿(mǎn)足這個(gè)需求。這個(gè)機(jī)制 沒(méi)有分布式事務(wù)通用，但性能會(huì)更好（尤其是跨上百行以上的更新），而且對(duì)于樂(lè)觀(guān)跨數(shù)據(jù) 中心復(fù)制（optimistic cross-data-center replication）來(lái)說(shuō)，和我們系統(tǒng)的集成會(huì)更好。

9.3 系統(tǒng)級(jí)監(jiān)控非常重要

在日常支持 Bigtable 中學(xué)到的實(shí)際一課是：合理的系統(tǒng)級(jí)監(jiān)控（例如監(jiān)控 Bigtable 本身 ，以及使用 Bigtable 的客戶(hù)端）非常重要。

例如，我們擴(kuò)展了我們的 RPC 系統(tǒng)，可以記錄重要?jiǎng)幼鞯脑敿?xì)跟蹤信息。這個(gè)特性幫助我 們檢測(cè)和解決了很多問(wèn)題，包括：

1. tablet 數(shù)據(jù)結(jié)構(gòu)上的鎖競(jìng)爭(zhēng)
2. 提交 Bigtable mutation 時(shí) GFS 寫(xiě)很慢
3. METADATA?tablets 不可用時(shí)訪(fǎng)問(wèn)?METADATA?表時(shí)被卡住（stuck）

監(jiān)控的另一個(gè)例子是每個(gè) Bigtable 集群都注冊(cè)到了 Chubby。這使得我們可以跟蹤所有的集 群，看到集群有多大，各自運(yùn)行的是什么版本，接收到的流量有多大，是否有異常的大延遲 等等。

9.4 保持設(shè)計(jì)的簡(jiǎn)潔

我們學(xué)到的最重要經(jīng)驗(yàn)是：簡(jiǎn)單設(shè)計(jì)帶來(lái)的價(jià)值（the value of simple designs）。

考慮到我們的系統(tǒng)規(guī)模（10 萬(wàn)行代碼，不包括測(cè)試），以及代碼都會(huì)隨著時(shí)間以難以 意料的方式演進(jìn)，我們發(fā)現(xiàn)代碼和設(shè)計(jì)的簡(jiǎn)潔性對(duì)代碼的維護(hù)和 debug 有著巨大的幫助。

Given both the size of our system (about 100,000 lines of non-test code), as well as the fact that code evolves over time in unexpected ways, we have found that code and design clarity are of immense help in code maintenance and debugging.

一個(gè)例子是我們的 tablet server 成員（membership）協(xié)議。我們的第一版非常簡(jiǎn)單： master 定期向 tablet server 提供租約，如果一個(gè) tablet server 的租約到期，它就自 殺。不幸的是，這個(gè)協(xié)議在發(fā)生網(wǎng)絡(luò)問(wèn)題時(shí)可用性非常差，而且對(duì) master 恢復(fù)時(shí)間也很敏感。

接下來(lái)我們重新設(shè)計(jì)了好幾版這個(gè)協(xié)議，直到它令我們滿(mǎn)意。但是，這時(shí)的協(xié)議已經(jīng)變得過(guò) 于復(fù)雜，而且依賴(lài)了一些很少被其他應(yīng)用使用的 Chubby 特性。最后發(fā)現(xiàn)我們花了大量的時(shí) 間來(lái) debug 怪異的邊界場(chǎng)景，不僅僅是 Bigtable 代碼，還包括 Chubby 代碼。

最終，我們放棄了這個(gè)版本，重新回到了一個(gè)新的更簡(jiǎn)單的協(xié)議，只依賴(lài)使用廣泛的 Chubby 特性。

10 相關(guān)工作

The Boxwood project [24] has components that overlap in some ways with Chubby, GFS, and Bigtable, since it provides for distributed agreement, locking, distributed chunk storage, and distributed B-tree storage. In each case where there is overlap, it appears that the Boxwood’s component is targeted at a somewhat lower level than the corresponding Google service. The Boxwood project’s goal is to provide infrastructure for building higher-level services such as file systems or databases, while the goal of Bigtable is to directly support client applications that wish to store data.

Many recent projects have tackled the problem of providing distributed storage or higher-level services over wide area networks, often at “Internet scale.” This includes work on distributed hash tables that began with projects such as CAN [29], Chord [32], Tapestry [37], and Pastry [30]. These systems address concerns that do not arise for Bigtable, such as highly variable bandwidth, untrusted participants, or frequent reconfiguration; decentralized control and Byzantine fault tolerance are not Bigtable goals.

In terms of the distributed data storage model that one might provide to application developers, we believe the key-value pair model provided by distributed B-trees or distributed hash tables is too limiting. Key-value pairs are a useful building block, but they should not be the only building block one provides to developers. The model we chose is richer than simple key-value pairs, and supports sparse semi-structured data. Nonetheless, it is still simple enough that it lends itself to a very ef cient representation, and it is transparent enough (via locality groups) to allow our users to tune important behaviors of the system.

Several database vendors have developed parallel databases that can store large volumes of data. Oracle’s Real Application Cluster database [27] uses shared disks to store data (Bigtable uses GFS) and a distributed lock manager (Bigtable uses Chubby). IBM’s DB2 Parallel Edition [4] is based on a shared-nothing [33] architecture similar to Bigtable. Each DB2 server is responsible for a subset of the rows in a table which it stores in a local relational database. Both products provide a complete relational model with transactions.

Bigtable locality groups realize similar compression and disk read performance benets observed for other systems that organize data on disk using column-based rather than row-based storage, including C-Store [1, 34] and commercial products such as Sybase IQ [15, 36], SenSage [31], KDB+ [22], and the ColumnBM storage layer in MonetDB/X100 [38]. Another system that does vertical and horizontal data partioning into and achieves good data compression ratios is AT&T’s Daytona database [19]. Locality groups do not support CPUcache- level optimizations, such as those described by Ailamaki [2].

The manner in which Bigtable uses memtables and SSTables to store updates to tablets is analogous to the way that the Log-Structured Merge Tree [26] stores updates to index data. In both systems, sorted data is buffered in memory before being written to disk, and reads must merge data from memory and disk.

C-Store and Bigtable share many characteristics: both systems use a shared-nothing architecture and have two different data structures, one for recent writes, and one for storing long-lived data, with a mechanism for moving data from one form to the other. The systems differ significantly in their API: C-Store behaves like a relational database, whereas Bigtable provides a lower level read and write interface and is designed to support many thousands of such operations per second per server. C-Store is also a “read-optimized relational DBMS”, whereas Bigtable provides good performance on both read-intensive and write-intensive applications.

Bigtable’s load balancer has to solve some of the same kinds of load and memory balancing problems faced by shared-nothing databases (e.g., [11, 35]). Our problem is somewhat simpler: (1) we do not consider the possibility of multiple copies of the same data, possibly in alternate forms due to views or indices; (2) we let the user tell us what data belongs in memory and what data should stay on disk, rather than trying to determine this dynamically; (3) we have no complex queries to execute or optimize.

11 總結(jié)

我們?cè)?Google 設(shè)計(jì)了 Bigtable，一個(gè)存儲(chǔ)結(jié)構(gòu)化數(shù)據(jù)的分布式系統(tǒng)。

Bigtable 從 2005 年 4 月開(kāi)始用于生產(chǎn)環(huán)境，而在此之前，我們花了大約?7 個(gè)人年?（person-year）的時(shí)間在設(shè)計(jì)和實(shí)現(xiàn)上。到 2006 年 8 月，已經(jīng)有超過(guò) 60 個(gè)項(xiàng)目在使用 Bigtable。

我們的用戶(hù)很喜歡 Bigtable 提供的性能和高可用性，當(dāng)集群面臨的負(fù)載不斷增加時(shí) ，他們只需簡(jiǎn)單地向集群添加更多的節(jié)點(diǎn)就可以擴(kuò)展 Bigtable 的容量。

考慮到 Bigtable 的接口不是太常規(guī)（unusual），一個(gè)有趣的問(wèn)題就是，我們的用戶(hù)需要 花多長(zhǎng)時(shí)間去適應(yīng) Bigtable。新用戶(hù)有時(shí)不太確定如何使用 Bigtable 最合適，尤其是如 果之前已經(jīng)習(xí)慣了關(guān)系型數(shù)據(jù)庫(kù)提供的廣義事務(wù)。然后，很多 Google 產(chǎn)品成功地使用了 Bigtable 還是說(shuō)明了，我們的設(shè)計(jì)在實(shí)際使用中還是非常不錯(cuò)的。

當(dāng)前我們正在添加一些新的特性，例如支持 secondary indices，以及構(gòu)建跨數(shù)據(jù)中心復(fù)制 的、有多個(gè) master 副本的 Bigtable。我們還在做的是將 Bigtable 作為一個(gè)服務(wù)提供給 各產(chǎn)品組，以后每個(gè)組就不需要自己維護(hù)他們的集群。隨著服務(wù)集群的擴(kuò)展，我們將 需要處理更多 Bigtable 內(nèi)部的資源共享問(wèn)題 [3, 5]。

最后，我們發(fā)現(xiàn)構(gòu)建我們自己的存儲(chǔ)解決方案可以帶來(lái)非常大的優(yōu)勢(shì)。為 Bigtable 設(shè) 計(jì)自己的數(shù)據(jù)模型已經(jīng)給我們帶來(lái)非常多的便利性。另外，我們對(duì) Bigtable 的實(shí)現(xiàn)，以 及 Bigtable 所依賴(lài)的其他 Google 基礎(chǔ)設(shè)施有足夠的控制權(quán)，因此任何一個(gè)地方有瓶頸 了，我們都可以及時(shí)解決。

Acknowledgements

We 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, Joanna Kulik, Alberto Lerner, Sherry Listgarten, Mike Maloney, Eduardo Pinheiro, Kathy Polizzi, Frank Yellin, and Arthur Zwiegincew.