大家覺得有意義和幫助記得及時關(guān)注和點贊!!!

---

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

---

摘要

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

• 數(shù)據(jù)通過行鍵、列鍵和一個時間戳進(jìn)行索引，
• 表中的每個數(shù)據(jù)項都是不作理解的字節(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.

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

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

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

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

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

2.1 行（Row）

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

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

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

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

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

2.2 Column Families（列族）

多個 column keys 可以組織成?column families（列族）。 column family 是訪問控制（access control）的基本單位。

2.2.1 設(shè)計

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

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

2.2.2 column key 的格式：family:qualifier

其中，

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

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

例如，

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

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

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

2.3 時間戳

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

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

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

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

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

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

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

3 API

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

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

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

圖 2 Writing to Bigtable

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

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

圖 3 Reading from Bigtable

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

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

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

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

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

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

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

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

• GFS
• SSTable
• Chubby

4.1 GFS

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

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

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

4.2 SSTable

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

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

• 鍵和值都可以是任意字節(jié)字符串。
• 提供了按 key 查詢和對指定的 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)部，每個 SSTable 都包含一系列的?blocks（通常每個 block 64KB，但這個參數(shù) 可配置）。

block 用?block index（存儲在 SSTable 的末尾）來定位，block index 會在打開 SSTable 的時候加載到內(nèi)存。

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

4.3 Chuby

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

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

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

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

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

Bigtable 使用 Chubby 完成很多不同類型的工作：

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

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

5 實現(xiàn)

5.0 組件

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

1. 一個客戶端庫，會鏈接到每個客戶端

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

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

3. 多個 tablet server

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

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

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

5.1 Tablet 位置

服務(wù)端

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

圖 4 Tablet location hierarchy

• 第一級：Chubby 中的一個文件
• 第二級：METADATA tables（第一個?METADATA?table 比較特殊，所以在圖中單獨畫 出，但它其實和其他?METADATA?table 都屬于第二級）
• 第三級：user tablets

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

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

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

METADATA?table 存儲 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?這樣一個中等大小，這種三級位置方案就可以存儲高達(dá)?2^34?個 tablets（?128MB?=?2^17 * 1KB，即?METADATA?table 可以指向?2^17?個 user table，每個 user table 同樣是?128MB?的話，就有?2^17 * 2^17 = 2^34?個 tablets，譯者注）。 如果每個 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).

客戶端

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

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

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

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

5.2 Tablet 分配

每個 tablet 每次只會分配給一個 tablet server。

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

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

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

tablet server 失去鎖之后，如果鎖文件還在，它會嘗試重新去獲取這個鎖；如果鎖 文件不在了，tablet server 會自殺（kill itself），因為它無法為這個 tablet 提 供服務(wù)了。

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

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

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

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

master 啟動流程

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

master 啟動后所做的事情如下：

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

難點

以上過程的一個難點是：在掃描?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 還沒有被分配出去，那 master 就要先將它放到 未分配 tablets 集合，然后去執(zhí)行步驟 4。 這樣就保證了 root tablet 將會被分配出去。

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

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

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

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

master 能夠跟蹤這些變化，因為除了 tablet 分裂之外，其他流程都是由 master 處理的。tablet 分裂比較特殊，因為它是由 tablet server 發(fā)起的。

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

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

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

圖 5 Reading from Bigtable

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

tablet 恢復(fù)

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

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

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

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

寫操作

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

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

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

讀操作

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

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

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

5.4 壓縮（Compactions）

• minor compaction
• major compaction

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

minor compaction 有兩個目的：

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

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

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

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

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

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

6 改進(jìn)（Refinements）

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

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

6.1 Locality groups

客戶端可以將多個 column family 組織到一個 locality group。 每個 tablet 會為每個 locality group 生成一個單獨的 SSTable。

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

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

6.2 壓縮（Compression）

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

6.2.1 壓縮的粒度和算法

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

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

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

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

6.2.2 壓縮的速度和效率

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

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

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

6.3 讀緩存

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

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

6.4 Bloom 過濾器

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

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

我們的實際使用也顯示，大部分對不存在的行或列的訪問都無需涉及磁盤操作（在 Bloom 過濾器這一層就判斷不存在了，無需再查找磁盤）。

6.5 Commit-log 實現(xiàn)

每個 tablet 還是每個 tablet server 一個 log 文件

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

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

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

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

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

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

優(yōu)化：兩個寫線程和兩份 commit log

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

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

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

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

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

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

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

6.7 利用不可變性（Exploiting immutability）

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

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

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

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

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

7 性能評估

7.0 準(zhǔn)備

測試環(huán)境

我們在一套有 N 個 tablet server 的 Bigtable 集群進(jìn)行測試，測量 N 變化時 Bigtable 的性能和可擴(kuò)展性。

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

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

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

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

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

性能指標(biāo)

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

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

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

sequential read（順序讀）生產(chǎn)行鍵的方式與順序?qū)戭愃?#xff0c;讀的也是順序?qū)憸y試寫入的 數(shù)據(jù)。

random read（隨機(jī)讀）與隨機(jī)寫類似。

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

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

圖 6 以兩種視圖展示了讀/寫 1000 字節(jié)的值到 Bigtable 時的性能。 左側(cè)是每個 tablet server 每秒的操作數(shù)；右側(cè)是聚合之后的每秒操作數(shù)。

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

7.1 單 tablet-server 性能

首先看單個 tablet server 的性能。

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

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

從內(nèi)存的隨機(jī)讀會快很多，因為每個 1000 字節(jié)的讀都是從 tablet server 的本地內(nèi)存讀 取的，不需要從 GFS 訪問 64KB 的 block。

隨機(jī)和順序?qū)懙男阅芏家入S機(jī)讀好，因為每個 tablet server 會將所有寫操作追加 到同一個 commit log 然后執(zhí)行批量提交（group commit），從而高效地寫入到 GFS。?隨機(jī)寫和順序?qū)懙男阅懿]有明顯差異，因為兩種情況下，所有到 tablet server 的 寫最后都是到了同一個 commit log。

順序讀的性能遠(yuǎn)好于隨機(jī)讀，因為每個從 GFS?預(yù)取（prefetch）的 64KB SSTable block 都存儲到了 blcok 緩存，下一次 64 讀請求就會用到。

掃描的性能更好，因為客戶端的一次 RPC 請求就可以從 tablet server 拿到大量的值，因 此 RPC 開銷被平攤了。

7.2 擴(kuò)展性（scaling）

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

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

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

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

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

8 真實應(yīng)用

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

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

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

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

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

• 120 萬次請求/秒（QPS）
• 741 MB/s RPC 入流量
• 16 GB/s RPC 出流量

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

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

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

8.1 Google Analytics

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

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

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

這里簡要介紹 Google Analytics 使用的兩個 table。

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

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

8.2 Google Earth

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

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

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

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

8.3 Personalized Search

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

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

個性化搜索利用 MapReduce 在 Bigtable 上進(jìn)行運算，為每個用戶生成一個 profile。 這些 profile 就會用來做個性化的實時搜索。

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

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

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

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

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

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

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

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

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

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

9.2 避免過早添加使用場景不明確的新特性

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

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

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

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

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

例如，我們擴(kuò)展了我們的 RPC 系統(tǒng)，可以記錄重要動作的詳細(xì)跟蹤信息。這個特性幫助我 們檢測和解決了很多問題，包括：

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

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

9.4 保持設(shè)計的簡潔

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

考慮到我們的系統(tǒng)規(guī)模（10 萬行代碼，不包括測試），以及代碼都會隨著時間以難以 意料的方式演進(jìn)，我們發(fā)現(xiàn)代碼和設(shè)計的簡潔性對代碼的維護(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.

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

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

最終，我們放棄了這個版本，重新回到了一個新的更簡單的協(xié)議，只依賴使用廣泛的 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é)

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

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

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

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

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

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

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.