摘要#
Bigtable 是一個用於管理結構化數據的分佈式存儲系統，被設計成能夠擴展到非常大的規模：分佈在數千台商用伺服器上的 PB 級別的數據。Google 內部的許多項目使用 Bigtable 存儲數據，包括 web 索引，Google Earth 和 Google Finance。這些應用給 Bigtable 提出了不同的需求，無論是在數據大小（從 URL 到網頁到行星圖像）還是延遲要求（從後台批處理到實時數據服務）方面。儘管存在各種各樣的需求，Bigtable 成功地提供了一個用於所有這些 Google 產品的靈活的，高性能的解決方案。
介紹#
在過去兩年半的時間裡，我們在 Google 設計實現和部署了一個稱為 Bigtable 的用於管理結構化數據的分佈式存儲系統。Bigtable 被設計成可靠地擴展到 PB 級別的數據和數千台機器。Bigtable 已經達成了多個目標：廣泛適用性，擴展性，高性能和高可用性。Bigtable 在 Google 用於超過 60 個產品和項目，包括 Google Analytics, Google Finance, Orkut, Personalized Search, Writely 和 Google Earth。這些產品使用 Bigtable 處理各種高負荷工作負載，範圍從吞吐量導向的批處理作業到用於用戶端的延遲敏感型服務。這些產品使用的 Bigtable 集群覆蓋了廣泛的配置範圍，從幾台到數千台伺服器，存儲多達數百 TB 的數據。
從很多方面來說，Bigtable 類似於數據庫，和數據庫的共享很多實現策略。並行數據庫和內存數據庫已經實現了擴展性和高性能，但是 Bigtable 提供了相對於這些系統不同的接口。Bigtable 不支持完整的關係型數據模型，相反，它給客戶端提供了一個簡單的數據模型，支持數據佈局和數據格式的動態控制，並允許客戶端自行推理底層存儲中所表示的數據的局部性質（譯注：允許客戶端根據底層存儲的數據的位置關係推斷數據之間的局部關聯性質）。數據通過 row 和 column 來索引，其名字可以是任意的字符串。Bigtable 將數據視作原始字符串，儘管客戶端序列化各種形式的結構化和半結構化數據序列化成這些字符串。客戶端可以通過精心選擇數據格式來控制數據的局部性。最後，Bigtable 的 schema 參數允許客戶端動態控制是否從內存或磁碟中獲取數據。
數據模型#
bigtable 是稀疏分佈式持久化多維度有序哈希表，通過行鍵，列鍵和一個時間戳進行索引，每個值都是一個原始字節數組。
(row: string, column: string, time: int64) -> string
在研究了很多潛在使用 Bigtable-like 系統後，我們選定了這種數據模型。舉一個實際影響我們設計決策的例子，假設我們想要維護一個可以用於不同項目的，大規模的網頁集合及其相關信息的集合的拷貝，我們將這個表稱為 Webtable。在 Webtable 中，我們可能會使用 URLs 作為行鍵，網頁的各個屬性（譯注：如網頁內容，其中的錨點等等）作為列鍵，然後將對應的（不同時間獲取到的）內容存儲為值。如下圖：
行#
table 中的行鍵可以是任意的字符串（目前最大 64KB）。在同一個行鍵下進行的每次讀寫數據都具有原子性，這樣設計使得客戶端更容易推斷系統在並發更新同一行時的行為。Bigtable 根據行鍵的字典序維護數據。表內行的範圍是動態分區的，每個行範圍叫做一個 tablet，也是分佈和負載均衡的基本單元。這樣，讀取一個小的行範圍非常高效，一般只需要跟很少數量的機器通信。客戶端可以在選擇行鍵時利用這個性質，在訪問數據時得到較好的局部性。比如在 Webtable 中通過反轉 URLs 中的 hostname 部分，將域相同的網頁分組在一起。比如我們將 maps.google.com/index.html 的數據存儲在鍵 com.google.maps/index.html 下，將相同域的頁面存儲在彼此相近的位置使得一些主機和域的分析更加高效。
列族#
列鍵被分組成叫做列族的集合（column families），組成一個訪問控制的基本單元。在一個列族內存儲的所有數據類型一般是相同的（我們將相同列族的數據壓縮在一起）。列族必須在數據可以存儲到列族內的任一列鍵之前創建，在列族創建之後，列族內的所有列鍵都可以使用。
我們的目的是讓一個表內不同的列族的數量較少（最多上百個），並且在操作期間列族很少改變，相比之下一個表可能有無限多數量個列。一个列鍵可以用這種語法命名：族：標識符。列族的名字必須是可打印出來的，但是標識符可以是任意字符串。比如 Webtable 中的一個列族是語言，存儲編寫網頁內容使用的語言。我們在語言列族中只使用一個列鍵，其存儲每個網頁的語言 ID。這個表另一個有用的列族是錨點（anchor），這個族內的每個列鍵表示一個單獨的錨點（如上圖），其中的標識符是其引用的網址，內容是鏈接文本。
訪問控制，磁碟和內存計量都在列族這一級別進行。在我們 Webtable 的例子中，這種控制允許我們管理多種不同的應用：一些添加新的基礎數據，一些讀取基本數據並且創建派生出來的列族，還有一些只允許查看當前存在的數據（出於隱私的原因甚至不能查看所有的列族）。
時間戳#
Bigtable 內的每個 cell 可以包含相同數據的多個版本，這些版本通過時間戳來索引。Bigtable 的時間戳是 64 位整數。時間戳可以被 Bigtable 以微秒表示的真實時間賦值，也可以由客戶端應用顯式賦值，應用必須生成唯一時間戳以避免產生衝突。一個 cell 的不同版本以遞減的順序存儲，這樣最新的數據可以被最先讀取到。
為了減輕管理不同版本數據的負擔，我們支持兩種列族級別的設置使 Bigtable 進行自動垃圾收集：客戶端可以指定只保存最近的 n 個版本，或者只存儲足夠新的版本（比如最新七天寫入的數據）。
在 Webtable 的例子中，我們將存儲在內容中的爬取到的網頁的時間戳設置為這些頁面被實際爬取時的時間，上面描述過的垃圾回收機制讓我們只存儲每個頁面最近的三個版本。
API#
Bigtable API 提供了創建和刪除表以及列族的功能，也提供了修改集群，表，和列族元數據的功能，比如訪問控制權力。
客戶端應用可以寫入和刪除 Bigtable 的值，通過單獨的行查找值，或者遍歷表內數據的一個子集。下面是一個使用 RowMutation 抽象執行一系列數據更新的 C++ 代碼（省略了一些無關代碼）。其中 Apply 調用在 Webtable 上執行了一個原子性的變更：在 www.cnn.com 行上添加了一個錨點，刪除了一個不同的錨點。
// 打開 table
Table *T = OpenOrDie("/bigtable/web/webtable");
// 寫入新的錨點並且刪除舊的錨點
RowMutation r1(T, "com.cnn.www");
r1.Set("anchor:www.c-span.org", "CNN");
r1.Delete("anchor:www.abc.com");
Operation op;
Apply(&op, &r1);
下面是一個使用 Scanner 抽象來遍歷指定行的所有錨點的 C++ 代碼。客戶端可以遍歷多個列族，並且有很多機制可以限制掃描產生的行，列和時間戳的數目。比如我們可以限制掃描只產生錨點滿足正則表達式 anchor:*.cnn.com 的列，或者只產生時間戳落在最近十天以內的錨點。
Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily("anchor");
stream->SetReturnAllVersions();
scanner.Lookup("com.cnn.www");
for (; !stream->Done(); stream->Next()) {
printf("%s %s %lld %s\n",
scanner.RowName(),
stream->ColumnName(),
stream->MicroTimestamp(),
stream->Value());
}
Bigtable 支持多種其他特性，允許用戶以更複雜的方式處理數據。首先 Bigtable 支持單行事務，可以用於單個行鍵下原子性的執行讀取 - 修改 - 寫入序列。Bigtable 目前還不支持通用的跨行事務，儘管給客戶端提供了一個跨行批量寫的接口。其次 Bigtable 允許將 cell 用於整數計數器。最後 Bigtable 支持在服務端的地址空間內執行客戶端提供的腳本，這個腳本使用 Google 開發的一個用於處理數據的語言 Sawzall。目前我們基於 Sawzall 的 API 不支持客戶端腳本寫入 Bigtable，但是支持很多形式的數據轉換，基於任意表達式的過濾，通過各種操作進行聚合。
Bigtable 也可以用於 MapReduce，Google 開發的一個用於運行大規模並行計算的框架，我們做了一系列的封裝允許將 Bigtable 用於 MapReduce 作業的輸入源和輸出目標。
基礎組件#
Bigtable 構建在 Google 的許多其他的基礎設施之上，Bigtable 使用 GFS 存儲日誌和數據文件。一個 Bigtable 集群一般運行在一個共享的機器池中，其中還運行著廣泛的其他分佈式應用，並且 Bigtable 進程經常和其他分佈式應用進程共享相同的機器。Bigtable 依賴一個集群管理系統進行作業調度，在共享機器上管理資源，處理機器故障，和監控機器狀態。
Bigtable 使用 Google SSTable 文件格式存儲內部數據 SSTable 提供了一個持久化，有序的，不可變鍵值映射表，其中鍵和值是任意字節字符串。SSTable 提供了查找指定鍵對應的值，和根據一個指定鍵範圍進行所有鍵值對遍歷的操作。
在內部，每個 SSTable 包含一些連續的塊（通常每個塊的大小是 64KB 但是可配置）。在 SSTable 末尾有一個索引塊用於塊定位，當 SSTable 被打開時這個塊被加載到內存中。一次查詢操作可能是通過單次磁碟查找來完成：首先通過在內存索引中執行二叉搜索到找到正確的塊，然後在磁碟中讀取對應的塊。另外，一個 SSTable 也可以整個映射到內存中，使得我們不需要任何磁碟操作就可以執行查詢和掃描。
Bigtable 依賴一個高可用，持久化的分佈式鎖服務 Chubby 一個 Chubby 服務由五個活動副本組成，其中一個被選舉為 master 負責主動處理請求。當大多數副本存活且能夠彼此通信時服務就在線 Chubby 使用 Paxos 算法來保證面臨故障時副本保持一致。Chubby 提供了一個由目錄和小文件組成的命名空間，每個目錄或者文件都可以被用作一個鎖，並且單個文件的讀寫都是原子性的。Chubby 客戶端庫提供了 Chubby 文件的一致性緩存。每個 Chubby 客戶端維護一個跟 Chubby 服務的會話。當租約時間過期且不能將租約續期時客戶端會話將會過期。當客戶端會話過期，它會丟棄所有的鎖和打開的文件句柄。Chubby 客戶端也可以在 Chubby 目錄和文件上註冊回調，以獲取變更或會話過期的通知。
Bigtable 用 Chubby 處理多種任務：確保在任何時候最多只有一個活動的 master；存儲 Bigtable 數據的啟動位置；發現 tablet 伺服器和確認 tablet 伺服器死亡；存儲 Bigtable 格式信息（每個表的列族信息）；存儲訪問控制列表。如果 Chubby 在很長時間內不可用 Bigtable 也會跟著不可用。我們最近在跨越 11 個 Chubby 實例的 14 個 Bigtable 集群中測量了這種影響。由於 Chubby 的不可用（Chubby 中斷或者是網絡問題）導致存儲在 Bigtable 的某些數據不可用的 Bigtable 服務時間的平均百分比是 0.0047% 單個集群被 Chubby 的不可用性影響的最高百分比是 0.0326%。
實現#
Bigtable 的實現包含三個主要的組件：鏈接到每個客戶端的庫，一個 master 服務和很多 tablet 服務。其中 tablet 服務可以在集群中動態的添加或移除，以適應工作負載的變更。
master 負責將表分配到 tablet 伺服器，發現新增和過期的 tablet 伺服器，均衡 tablet 伺服器的負載，GFS 中的文件的垃圾回收。此外，也處理 schema 變更比如表和列族的創建。
每個 tablet 伺服器管理一組 tablet 的集合（一般一個 tablet 伺服器上有十到一千個 tablet），處理其加載的 tablet 的讀寫請求，分割過大的 tablet。
像很多單 master 的分佈式存儲系統一樣，客戶端數據不直接發送到 master 而是和 tablet 伺服器直接讀寫通信。由於 Bigtable 客戶端不依賴 master 獲取 tablet 位置信息，所以大多數客戶端不會和 master 通信。最終 master 在實踐中的負載很低。
一個 Bigtable 存儲許多表，每個表由一組 tablets 組成，每個 tablet 包含一行範圍內關聯的所有數據。一開始每個表只有一個 tablet 隨著表數據的增長，它會自動分割成多個 tablets 默認每個 tablet 的大小在 100-200MB 之間。
Tablet 位置#
我們使用一個類似 B+ 樹的三級層級結構來存儲 tablet 位置信息。
第一级是一个存储在 Chubby 上的文件包含 root tablet 的信息。root tablet 在一个特殊的 METADATA 表中包含所有 tablet 的位置信息。每个 METADATA tablet 包含一系列用户 tablets 的集合。root tablet 实际上就是 METADATA 表的第一个 tablet 其永远不会被分割，以确保 tablet 位置结构不会超过三级。
METADATA 表将 tablet 的位置信息存储在存储在以 tablet 的表标识符加上其结尾的行键编码成的行键上。每个 METADATA 行在内存中存储将近 1KB 的数据 METADATA tablet 采用了一个适度的限制 128MB 这样我们的三级定位方案足够寻址 2^34 个 tablet 也即 2^61 字节的数据。（譯注：root metatablet 可以容納 128MB / 1KB = 2^17 個次級條目，每個次級條目也可以容納 128MB / 1KB = 2^17 個三級條目，共 2^34 個 tablet 每個 tablet 的大小在 100-200 MB 取 128MB 即 2^27 得到總大小 2^61 字節）
客戶端庫會緩存 tablet 位置，如果客戶端不知道一個 tablet 的位置，或者發現其緩存的位置信息不正確，則會遞歸向上查找目標 tablet 的位置信息。如果客戶端緩存是空的，則尋址算法需要三次網絡來回，包括一次 Chubby 讀取。如果客戶端緩存是舊的，尋址算法可能會花費最多六個來回（假設 METADATA tablet 不會頻繁的移動），因為僅有在不命中時才會發現緩存過時（譯注：先用緩存，向上找三次都不命中，然後從上往下重新查詢三次）。
由於 tablet 的位置信息存儲在內存中，所以不需要訪問 GFS 我們通過客戶端庫預取 tablet 位置信息又進一步降低了開銷：客戶端每次讀取 METADATA 表時都會讀取多個 tablet。
我們在 METADATA 表中也存儲了次要（secondary）信息，包括與每個 tablet 相關的事件的所有日誌（比如一個 tablet 開始服務），這些信息在調試和性能分析時很有幫助。
Tablet 分配#
每個 tablet 在同一時間只會賦值到一個 tablet server 上 master 會持續跟蹤所有存活的 tablet server 的集合，和當前所有 tablet 在 tablet server 上的分配情況，包括那些沒有被分配的 tablet 當一個 tablet 未分配，並且由一個可用的 tablet server 有足夠的空間，則 master 會通過發送一個 tablet 加載請求將 table 分配到這個 tablet server 上。
Bigtable 使用 Chubby 持續追蹤 tablet server 當一個 tablet server 啟動，它會在一個指定的 Chubby 目錄下創建一個獨一無二的文件，並且申請一個互斥鎖。master 會監控這個目錄。
一個 tablet server 在丟失互斥鎖時會停止工作：比如網絡分區導致 server 丟失了 Chubby 會話（Chubby 提供了一種高效的機制允許 tablet server 在不使用網絡流量的情況下檢查自己是否仍然持有鎖）。只要文件仍然存在 tablet server 就會嘗試重新獲取文件上的互斥鎖，而如果文件不再存在，則 tablet server 就不可能再次提供服務，所以會將自己終止掉。無論何時，一個 tablet server 終止時（比如由於集群管理系統將 tablet server 的機器從集群中移除），會嘗試釋放自己持有的鎖，這樣 master 可以更快速的將其 tablet 分配到其他伺服器上。
master 負責檢測何時 tablet server 不再服務於其 tablets 然後將這些 tablets 儘可能快的從新分配。為了檢測何時 tablet server 不再服務於其 tablets master 會周期性的詢問每個 tablet server 的鎖的狀態。如果一個 tablet server 報告自己丟失了鎖，或者是 master 在幾次嘗試之後，不能夠達到這個 server 則 master 會嘗試獲取對應 server 的文件的互斥鎖。如果 master 能夠獲取到鎖，說明 Chubby 存活且 tablet server 可能已經終止或者是和 Chubby 有通信故障，因此 master 通過刪除 server 文件，以確保其不可能再次提供服務。一旦 server 文件被刪除 master 可以將之前分配到這個 server 上的所有 tablets 移動到未分配的 tablets 集合中。為了確保 Bigtable 集群不會受到 master 和 Chubby 之間網絡的影響，master 會在和 Chubby 的會話過期時將自己終止，然而如上所述 master 的故障不改變 tablets 在 tablet server 上的分配。
當一個 master 被集群管理系統啟動，在進行修改之前，需要知道 tablet 的分配情況。master 執行以下步驟以啟動：1. master 在 Chubby 上申請一個獨一無二的鎖，以避免並行的 master 實例化；2. master 掃描 Chubby 上的 servers 目錄來找到存活的 server；3. master 與每個存活的 tablet server 通信來發現每個 tablet server 已經分配了哪些 tablet；4. master 掃描 METADATA 查看所有的 tablet 每當掃描到一個還未被分配的 tablet 則 master 會將其添加到一個未分配 tablet 的集合，使得這個 tablet 可以被分配（譯注：只有在未分配 tablet 集合的 tablet 可以被分配）。
一個複雜的情況是只有 METADATA tablets 被分配之後才能掃描 METADATA 表。因此在開始第四步的掃描之前，如果在第三步沒有發現 root tablet 則 master 將 root tablet 添加到未分配集合中。這一步確保 root tablet 會被分配。由於 root tablet 包含所有 METADATA tablets 的名字，在 master 掃描完 root tablet 後就可以知道所有的 tablets。
目前存在的 tablets 集合在以下情況變更：tablet 被創建或者刪除，兩個存在的 tablet 合併成一個更大的 tablet，或者一個 tablet 分割成兩個更小的 tablet。master 能夠追蹤到這些變更，因為其發起了除最後一項以外的所有變化（譯注：創建 / 刪除 / 合併都是由 master 執行的，分割不是）。Tablet 的分割是特殊的，因為他們由 tablet server 執行。tablet server 通過在 METADATA 表中記錄新的 tablet 的信息來提交分割操作，當分割操作已經提交，它會通知 master 如果這個通知丟失（tablet server 或者 master 宕機），master 也會在請求 tablet server 加載已經被分割的 tablet 時發現，因為 tablet server 在 METADATA 表中找到被要求加載的 tablet 對應的條目只包含了一部分（譯注：通過 row range 判斷）然後 tablet server 會向 master 發送 tablet 已經被分割的通知。
Tablet 服務#
tablet 的持久化狀態存儲在 GFS 中，如上圖。更新操作提交了一條包含 redo 記錄的提交日誌。關於這些更新，最近的提交存儲在內存一個叫做 memtable 的有序緩衝區中；舊的提交存儲在一系列的 SSTables 中。 為了恢復一個 tablet，tablet server 從 METADATA 表中讀取 tablet 的元數據：包含組成 tablet 的 SSTables 的列表和一個 redo 指針集合，指向
所有可能包含該 tablet 數據的提交日誌。server 將 SSTables 的索引讀取到內存中，並通過執行已經提交過的所有 redo 日誌來執行更新，重建 memtable。
當一個寫操作到達 tablet server，server 檢查格式是否正確，這樣發送者被授權執行這個變更，授權是通過從一個 Chubby 文件中讀取（大部分情況下都會命中緩存）允許寫入者列表來執行的。一個有效的變更會寫入到提交日誌，分組提交（group commit）用於提高小型變更的吞吐量。在寫入被提交後，其內存會被插入到 memtable。當 tablet server 收到一個讀操作，同樣先檢查格式和權限合適。一個合法的讀取操作會在 memtable 和一系列 SSTables 的合併視圖上執行。由於 SSTables 和 memtable 都是以字典序排序的數據結構，合併視圖可以高效的構建。
tablets 分割或合併時，讀寫操作都可以持續進行。
壓縮#
寫操作執行後 memtable 的大小會遞增，當 memtable 的大小達到一個閾值 memtable 會被冻结，然後一個新的 memtable 會被創建出來，被凍結的 memtable 會被轉換成一個 SSTable 並寫入 GFS。這個 * 次要壓縮 (minor major)* 過程有兩個目標：收縮 tablet server 的內存佔用，減少 server 宕機恢復時需要讀取提交日誌數據的數量。在壓縮過程中讀寫操作可以持續進行。
每個次要壓縮創建一個新的 SSTable 如果這種操作一直繼續下去，讀操作可能需要合併任意數量的 SSTables 的更新。相反，我們通過在後台周期性的執行合併壓縮來限制文件的數量。每個合併壓縮讀取一些 SSTables 和 memtable 的內容，寫入到一個新的 SSTable，在壓縮完成之後，輸入的 SSTable 和 memtable 就可以被丟棄了。
重寫所有 SSTables 合併壓縮到只有一個 SSTable 的操作稱為主要壓縮 (major compaction)，通過非主要壓縮產生的 SSTables 可能會包含特殊的刪除條目，抑制舊的 SSTable 中依然存活的數據（譯注：沒看明白）。換種說法，主要壓縮產生的一個 SSTable 不包含任何的刪除信息或者被刪除的數據（譯注：所有數據都存在這一個 SSTables 裡面不需要保存刪除相關的信息）。Bigtable 週期性的遍歷所有的 tablets 並且在其上執行主要壓縮操作。這些主要壓縮操作允許 Bigtable 回收被刪除的數據使用的資源，也能夠確保已經刪除的數據及時從系統中消失，這對於存儲敏感數據的服務來說很重要。
優化#
上面所描述的實現需要一定的優化來達到我們的用戶要求的高性能，高可用和可靠性。本節會更詳細的描述部分實現，以突出這些改進。
本地性組#
客戶端可以將多個列族組合成一個 locality group 每個 tablet 都會給每個 locality group 創建一個單獨的 SSTable。將通常不會一起訪問的列族分隔到不同的 locality groups 可以提高讀取效率。比如 Webtable 中的頁面元數據可以被放到一個 locality group，而頁面內容可以放到不同的 locality group，這樣一個需要讀取頁面元數據的應用就不需要讀取到任何頁面的內容。
此外，可以在每個 locality group 的基礎上指定一些有用的微調參數。比如一個 locality group 可以被聲明為存儲在內存中。存儲在內存 SSTables 中的 locality groups 會被 tablet server 惰性加載到內存中。一旦加載，讀取屬於這個 locality groups 的列族就可以無需訪問磁碟。這個特性對一些小塊但是經常訪問的數據很有用：在內部，我們在 METADATA 表中使用這個特性來定位列族。
壓縮#
客戶端可以控制是否壓縮一個 locality group 的 SSTables 如果是則使用壓縮格式。用戶指定的壓縮格式會使用在每個 SSTable 塊上（大小可以通過 locality group 的微調參數指定控制）。儘管將每個塊分開壓縮會丟失一些空間，但好處是讀取 SSTable 的一小部分時需要解壓整個文件。許多客戶端使用兩步自定義壓縮格式，第一步使用 Bentley and McIlroy’s scheme 在一個大的窗口中壓縮長的公共字符串，第二部使用一個快速壓縮算法，在一個 16KB 大小的窗口上查找重複的模式。兩個壓縮過程速度都非常快，在現代機器上編碼速度 100–200 MB/s 解碼速度 400–1000 MB/s。
儘管我們在選擇壓縮算法時更注重速度而非空間縮減，這種兩步壓縮模式還是取得了出人意料的好結果。比如在 Webtable 中我們使用這種壓縮模式存儲網頁內容。在一個實驗中，我們在一個被壓縮的 locality group 中存儲了大量的文檔，為了實驗的目標，我們限制在每個文檔中只存儲一個版本（譯注：同一文檔多個版本的內容可能是極其相似的）。這種壓縮模式在空間上達到了 10:1 的壓縮比。這比普通的 Gzip 在 HTML 頁面上 3:1 或者 4:1 的壓縮比要好很多，原因在於 Webtable 的行存儲方式是：同一主機的所有所有頁面存儲在相近的位置，這使得 Bentley-McIlroy 算法能夠標識相同主機下頁面上大量的共享樣板（譯注：大量網頁可能有相同的頁眉頁腳或其他靜態模板）。
許多應用不僅是 Webtable 選擇能夠將相似的數據最終聚合到一起的行名稱，因此能夠達到非常高的壓縮比。Bigtable 在存儲多版本數據時壓縮比甚至更高。
讀性能的緩存#
為了改善讀性能 tablet servers 使用了兩層緩存。Scan Cache 是高層級的緩存，緩存 tablet server 代碼裡 SSTable 接口返回的鍵值對，Block Cache 是低層級的緩存直接緩存從 GFS 讀取的 SSTables 塊。Scan Cache 對於會重複讀取相同數據的應用最有用，Block Cache 對於短期內讀取的數據非常接近的應用最有用（比如順序讀或者在一個熱點行上隨機讀取相同 locality group 的不同列）。
Bloom 過濾器#
如上所述，一個讀操作必須讀取構成 tablet server 狀態的所有 SSTables，如果 SSTables 不在內存中，會導致很多磁碟訪問，我們通過允許客戶端指定應該為特定的 locality group 創建 Bloom 過濾器來減少這個數量。一個 Bloom 允許我們詢問一個 SSTable 是否包含一個指定行 / 列對的任何數據。對於某些應用，在 tablet server 使用很小的一塊內存存儲 Bloom 過濾器能夠大幅度的減少讀取操作的磁碟訪問數量。使用 Bloom 過濾器也意味著，大部分對不存在的行或列的查詢根本不需要訪問磁碟。
提交日誌實現#
如果我們一直將每個 tablet 的提交日誌寫到不同的日誌文件，那麼在 GFS 會有非常大量的文件並發寫入。依賴於每個 GFS server 上的底層文件系統的實現，這些寫入可能會造成大量的磁碟定位（seek）以寫入到不同的物理日誌文件。此外，給每個 tablet 上寫入不同的日誌文件會減少 group commit 優化的效率，因為 groups 會變得很小（譯注：不同的 commit 寫入到不同的文件不能放入同一個 group）。為了修復這個問題，我們在每個 tablet server 將變更附加到單獨的提交日誌，在同一個物理日誌文件中混合不同 tablets 的變更。
使用一個日誌文件可以在常規操作提供了極大的提升性能，但是會使恢復變得複雜。當一個 tablet server 宕機，其服務的 tablets 會被移動到大量的其他的 tablet servers 上：每個 server 通常只加載原先 tablet server 上的很小數量的數據。為了恢復一個 tablet 的狀態，新的 tablet server 需要從原先 tablet server 的提交日誌文件上重放對應 tablet 的變更。然而，這個 tablet 的變更和其他 tablet 的變更混合到相同的物理日誌文件上。一個方法是每個新的 tablet server 讀取全量的提交日誌文件，然後只重放恢復所需要的對應 tablet 的條目。然而，在這種模式下，如果一個故障的 tablet server 上的 tablet 被分配給了 100 台機器，則日誌文件會被讀取 100 次（每個 tablet server 都讀取一次）
我們通過首先將提交日誌條目按照 <table, row name, log sequence number> 作為鍵進行排序。在排序的輸出中，所有特定的 tablet 的變更都是連續的因此可以只通過一次磁碟定位高效的順序讀取出來。為了並行化排序，我們將日誌文件分隔成 64MB 的段，然後在不同的 tablet server 上並行排序各個段。這個排序過程由 master 協調，並且在一個 tablet server 表明自己需要從一些提交日誌文件上恢復變更時啟動。
將提交日誌寫入到 GFS 有時導致一段短暫的性能問題，由於各種各樣的原因：比如一個 GFS server 機器產生寫崩潰，或者到達三個 GFS 伺服器的網絡路徑上出現擁堵，又或者是負載太高等等。為了保護在 GFS 延遲峰值情況下的變更，每個 tablet server 實際上有兩個線程同時使用。如果寫入到活動日誌文件的性能很低，日誌文件寫入會切換到其他線程，並且提交日誌隊列中的變更通過新的線程寫入。日誌條目中包含序列號，允許恢復過程忽略由於日誌切換線程產生的重複條目。
加速 tablet 恢復#
如果 master 將一個 tablet 從一個 tablet server 轉移到另一個，源 tablet server 首先在對應的 tablet 上做一個次要壓縮，這個壓縮通過減少 tablet server 提交日誌中未壓縮的狀態的數量來減少恢復所需要的時間。在完成這次壓縮後這個 tablet server 停止為這個 tablet 服務，在其真正取消加載 tablet 之前 tablet server 會再做一次次要壓縮（通常很快）來消除在第一次次要壓縮執行後到達的，剩下的其他沒有壓縮的狀態。在第二次次要壓縮完成後，這個 tablet 就可以被加載到其他 tablet server 上而無需恢復任何日誌條目。
利用不可變性#
除了 SSTable 緩存，Bigtable 系統的許多其他部分也因為實際上我們生成的 SSTables 是不可變的而被簡化了。比如，當從 SSTables 進行讀取時，我們不需要在訪問的文件系統上做任何同步操作。最終，可以很高效的實現不同行之間的並發通知。唯一可變的，可以被同時讀寫的數據結構是 memtable 為了減少 memtable 讀取時的競爭，我們給 memtable 的每行做了 copy-on-write 並且允許讀寫並行執行。
由於 SSTables 是不可變的，永久移除已刪除數據的問題轉換成了垃圾回收廢棄 SSTables。每個 tablet 的 SSTables 註冊在 METADATA 表內。master 通過標記 - 擦除在 SSTables 中移除淘汰的 SSTables METADATA 表包含根 tablet 的集合。最終，不可變的 SSTables 使得我們能夠將 tablets 快速的分隔，我們讓子 tablets 共享父 tablet 的 SSTables 而非給每個子 tablet 生成一個新的 SSTables 集合。
教訓#
在設計，實現，維護和支持 Bigtable 的過程中，我們收穫了很多經驗並且學到了許多有趣的教訓。
我們學到的一個教訓是大型分佈式系統容易受到很多各種故障的影響，不僅是標準的在許多分佈式協議中假設的網絡分區和故障停止錯誤。比如我們發現很多由於這些原因造成的問題：內存和網絡故障，大的時鐘偏差，機器掛起（無響應），持續的不對稱的網絡分區，我們使用其他系統（比如 Chubby）的 bug，GFS 配額溢出，以及其他計劃和非計劃內的硬件維護。隨著我們已經在這些問題上獲得了許多這些問題的，我們通過修改各種協議來解決他們。比如，我們在 RPC 機制中添加了校驗和。我們也通過移除系統中的一部分對其他部分做出的假設來處理這些問題，比如我們不再假設一個給定的 Chubby 只會返回一定範圍內的錯誤。
另一個我們學到的教訓是，在搞清楚新的特性會被如何使用之前延遲添加新特性很重要。比如我們一開始計劃在我們的 API 中支持通用事務。因為目前沒有使用場景，我們沒有實現它們。現在我們有許多真實的應用運行在 Bigtable 上，我們可以調查它們的實際需求，發現大多數應用只需要單行事務。對於用戶需求的分佈式事務，最重要的用途是維護輔助索引，我們計劃添加一個特殊的機制來滿足它們的需求。新的機制會不比分佈式事務更加通用（less general），但是會更高效（特別是在更新數百行的跨度上），並且也能和我們跨數據中心副本樂觀複製方案更好的兼容（interact better）。
我們在支持 Bigtable 的過程中學到的一個實用的教訓是，適當的系統級監控非常重要（比如：不僅監控 Bigtable 本身，還監控使用 Bigtable 的客戶端）。例如：我們擴展了我們的 RPC 系統，這樣對於一個簡單的 RPC 他會詳細記錄所有該 RPC 所作的所有重要操作的詳細跟蹤。這個特性允許我們發現和修復了許多問題，比如：tablet 數據結構的鎖競爭，提交到 Bigtable 的變更寫入 GFS 太慢，當 METADATA tablets 不可用時訪問 METADATA table 導致阻塞訪問。另一個監控有用的例子是，每個 Bigtable 集群都註冊在 Chubby 中，這允許我們跟蹤到所有集群的，了解它們的大小，運行的軟件版本，收到了多大的流量，監控是否存在延遲異常高的問題。
我們學到的最重要的教訓是簡單設計的價值。鑑於我們系統的大小（除去測試代碼大概 100000 行），代碼以不可預期的方式發展，我們發現代碼和設計的清晰度極大的影響維護和調試。比如我們的 tablet-server 成員協議。我們的第一個協議很簡單：master 週期性的向 tablet-server 發出租約，然後 tablet servers 在租約過期時殺死自己。不幸的是，在產生網絡問題時，這個協議極大的降低了可用性，而且對 master 的恢復時間很敏感。我們重新設計了很多次，直到有一個表現良好的協議。然而結果是，這個協議過於複雜而且依賴於 Chubby 的一些很少被其他應用使用的特性的行為。
我們發現我們在處理一些模糊的邊界情況上花費了太多的時間，不僅僅是在 Bigtable 的代碼，而且還有 Chubby 代碼。最終，我們廢棄了這個協議並且轉移到了一個新的簡單的協議，僅依賴於常用的 Chubby 特性。
結論#
我們已經描述了 Bigtable 這樣一個 Google 用來存儲結構化數據的分佈式系統。Bigtable 自 2005 年四月開始子啊生產環境中使用，在這之前，我們花費了將近七人 - 年來設計和實現它。在 2006 年八月份，超過六十個項目使用 Bigtable。我們的用戶喜歡 Bigtable 提供的高性能和高可用性，並且隨著時間資源需求的增長，可以通過簡單的增加更多的機器來擴展集群的容量。
考慮到 Bigtable 不同尋常的接口，一個有趣的問題是，對於我們的用戶來說適應使用 Bigtable 有多困難。新用戶通常不確定怎麼最好的使用 Bigtable 的接口，尤其當他們已經習慣於使用關係型數據庫提供的支持的通用事務。儘管如此，許多 Google 產品成功的使用了 Bigtable 的事實證明我們的設計在實踐上工作的還不錯。
我們仍在開發許多額外的 Bigtable 的新特性，比如支持輔助索引，構建跨數據中心複製的，具有多個 master 副本的 Bigtables 基礎設施。我們也開始將 Bigtable 部署為提供給產品組的一個服務，這樣單獨的產品不需要維護他們自己的集群。隨著我們服務集群的擴展，我們需要解決更多 Bigtable 本身資源共享的問題。
最終，我們發現在 Google 自建存儲解決方案有巨大的好處，在給 Bigtable 設計我們自己的數據模型時，獲取了顯著的靈活性。除此以外，我們可以自主控制 Bigtable 的實現及其所依賴的 Google 基礎設施，意味著在我們可以及時的消除瓶頸和低效。