# 7-1. Bigtable: A Distributed Storage System for Structured Data

Bigtable是Google的分散式儲存系統，可處理極大規模的結構化資料，涵蓋網頁索引、Google Earth和Google Finance等多個專案。儘管需求各異（資料大小和延遲需求），Bigtable仍成功提供靈活、高效的解決方案。

## Introduction

Bigtable是一個處理結構化資料的分散式儲存系統，能可靠地擴展至PB級資料和數千台伺服器，Bigtable實現了幾個目標：廣泛應用性、擴展性、高性能和高可用性，並被超過60個Google產品和專案使用。

Bigtable有點像資料庫，但使用方式不同。它提供簡單的資料模型，讓客戶動態控制資料的格式和排列，而非支援完整的關聯式資料模型。資料是用任意字串作為row和column的名字進行索引的。雖然資料被視為uninterpreted strings，但客戶通常會將各種形式的結構化和半結構化資料轉換成這些字串。客戶可以透過精心設計的schema來控制資料位置，並且有參數讓客戶可以動態控制從記憶體還是磁碟中提取資料。

## Data Model

Bigtable是一個稀疏的、分散的、持久的多維排序map，以row key、column key和timestamp索引。Map中的每個值都是一個未解釋的位元組陣列。

`(row:string, column:string, time:int64) → string`

:::info

舉例：Webtable，以網址作為row key，將網頁不同的部分作為column name，並且將網頁的內容儲存在contents欄在抓取的timestamp下。


- Row name是reversed URL
- Column family
- contents: 網頁的內容
- anchor: 引用該頁面的任何錨點的文本

CNN的主頁被Sports Illustrated和MY-look首頁引用，因此該row包含名為anchor:cnnsi.com和anchor:my.look.ca的欄位。每個anchor cell都有一個版本；內容欄有三個版本，timestamp分別為 t3、t5 和 t6。
:::

**Rows**

- Row key是任意字串，大小可達64KB，但通常為10至100位元組。
- 對單一row key資料的讀寫操作是atomic的，便於客戶推理在同一行的concurrent更新情況下系統的行為。
- Bigtable按照row key的字典序維護資料。
- *tablet*: 動態分割出來的表格row range，是distribution和load balancing的單位。
- 對於short row ranges的讀取是高效的，通常只需要與少量的機器通訊。
- Client可以透過row key的選擇來獲得對其資料訪問的良好局部性。
- 例如：將 `maps.google.com/index.html` 的資料儲存在 `com.google.maps/index.html` 這個key下，將來自同一域的網頁存儲在相鄰位置可以使一些主機和域分析更高效。

**Column Families**

- *column families*: column keys的群組集合，為access control的基本單元。
- 族中的資料通常都是相同類型的，這些資料會一起壓縮。
- 在把資料存放在column family中的任何column key之前，都必須先建立column family。建立了column family後，該族中的任何column key都可以使用。
- 希望表中的column family數量很少（最多數百個），並且在操作期間很少更改。相反，表可能有無限多個欄位。
- column key的命名語法：family:qualifier
- column family name必須是printable的，但qualifier可以是任意的字串。
- 存取控制和資源管理在column family級別進行
- 可以根據column family來管理不同類型的應用程式。
- 有一些應用程序負責添加新的base data，有些負責讀取base data並建立新的column family，還有一些只允許查看現有資料（甚至出於隱私保護的考慮，可能不允許查看所有column family）

**Timestamps**

- Bigtable中的每個儲存格可以有多個版本，版本是按時間戳排序的。
- 時間戳是64位元整數，可以由Bigtable自動分配，或者由應用程式指定。
- 儲存格的不同版本按照時間戳降序存儲，以便最新版本可以優先讀取。
- 為了讓版本化資料的管理更輕鬆，支援兩種 per-column-family 的設定，讓Bigtable自動進行垃圾回收
- 只保留儲存格的最後n個版本
- 只保留足夠新的版本（像是7天內寫入的內容）

## API

Bigtable API提供了創建和刪除table和column family的函數。它還提供了更改叢集、table格和column family metadata的函數，如存取控制權限。

:::info
**Writing to Bigtable**


使用RowMutation抽象來執行一系列更新，調用Apply執行了對Webtable的原子變更。
:::

:::info
**Reading from Bigtable**


使用Scanner抽象在特定行上迭代所有anchor。
:::

Bigtable支援幾個允許用戶以更複雜的方式操作資料的功能：
1. **single-row transactions**：可用於對單個row key下的資料執行atomic的read-modify-write sequences，目前不支援跨row keys的general transactions，只提供批次的寫入介面。
2. **儲存格計數器**：允許將儲存格用作整數計數器。
3. **用戶端腳本**：支援在伺服器的地址空間中執行用戶端提供的腳本，以Google開發用來處理資料的Sawzall撰寫。目前Sawzall-based API不支援用戶端的腳本對Bigtable的寫回，但允許以各種運算子進行資料轉換、基於任意表達式的過濾和摘要。

Bigtable可與Google開發的MapReduce框架配合使用，我們提供了一組wrapper，使Bigtable可以作為MapReduce作業的輸入源和輸出目標。

## Building Blocks

Bigtable建立在Google基礎設施上，使用Google文件系統（GFS）來存儲日誌和資料檔案，並在共享的機器池中運行。

**SSTable**
- 用於在Bigtable內部儲存資料，每個SSTable包含一系列區塊
- 提供持久、有序、不可變的key-value mapping，允許查找特定key的value或遍歷指定key range的所有key/value pair
- 打開SSTable時，將存在SSTable末尾的block index加載到記憶體
- 可用一個disk seek完成lookup：在記憶體中的目錄目錄做binary search找到適當的區塊，然後從磁碟讀取
- SSTable可選擇性地完全map到記憶體，以實現無需磁碟讀取的lookup和scan

Bigtable使用**Chubby**分散式鎖服務確保資料的可靠性和一致性。

- 確保任何時間只有一個active master
- 儲存Bigtable資料的啟動位置
- 發現Tablet伺服器並確定Tablet伺服器的故障
- 儲存Bigtable的schema資訊（每個table的column families）
- 儲存存取控制清單

如果Chubby長時間不可用，Bigtable也會變得不可用。

## Implementation

Bigtable有三個主要的組件：
- 連結到每個Client的Library * 1
- Master伺服器 * 1
- Tablet伺服器 * n，可以動態地新增（或移除）到叢集中以應付工作量的變化。

**Master**
- 將tablet指派給tablet伺服器
- 偵測tablet伺服器的新增和到期
- 平衡tablet-server負載
- 處理GFS檔案的垃圾收集
- 處理schema變更（table和column family的創建等）

**Tablet Server**
- 管理一組tablet（通常10~1000個）
- 處理對已載入的tablet的讀寫請求
- 拆分增長至過大的tablet

在 Bigtable 中，用戶端的資料不必透過master伺服器傳遞，而是直接和tablet伺服器溝通，因此master伺服器的負擔很輕。

Bigtable叢集儲存多個table，每個table由一組tablet組成，而每個tablet包含一個row range的資料。最初每個table只有一個tablet，table隨著資料量增加而自動分割成多個tablet，每個tablet的默認大小約為100到200MB。

### Tablet Location

使用類似B+\-tree的三層次結構儲存tablet location。

- **Root tablet**: 位置存在Chubby，包含所有tablet的位置，是METADATA table中的第一個tablet，但永遠不會被拆分，確保層級永遠不會超過三層。
- **Metadata tablet**: 每個包含一組user tablet的位置，以及與每個tablet相關的所有事件的日誌。

Client library快取tablet位置，並透過遞迴搜尋或預先讀取來提高效率。

### Tablet Assignment

* **Single Assignment**：每個tablet一次僅分配給一台tablet伺服器。Master伺服器追蹤活著的Tablet伺服器及其分配的Tablet。
* **指派未分配的Tablet**：如果某個 Tablet 未分配且有 Tablet 伺服器可用，則master透過傳送load請求將 Tablet 指派給該伺服器。
* **Chubby的使用**：
- **發現Tablet伺服器**：Tablet伺服器透過在特定的 Chubby 目錄中建立並鎖定唯一檔案來註冊。Master伺服器監視該目錄來發現活動的 Tablet 伺服器。
- **處理伺服器故障**：如果Tablet伺服器失去lock（例如，網路問題），它將停止為Tablet提供服務，然後由Master伺服器將這些Tablet重新分配給其他伺服器。
* **失敗時重新分配**：
- Master定期檢查每個Tablet伺服器的鎖的狀態。如果伺服器遺失鎖或變得無法訪問，Master伺服器將取得伺服器的檔案鎖以確認其狀態。
- 如果Master伺服器可以獲得鎖，它會刪除伺服器的檔案，將其所有Tablet標記為未分配以便重新分配。
* **Master啟動**：
- 啟動時，Master透過取得唯一的鎖來確保它是唯一活著的Master。
- 掃描 Chubby 目錄中活著的伺服器，並與它們通訊以確定當前的Tablet分配。
- 掃描Metadata table以識別任何未分配的Tablet並將它們添加到清單中以進行重新分配。

### Tablet Serving

Tablet的持久狀態儲存在GFS，如下圖。

更新被記錄在日誌中
- 最近提交：儲存在memtable，記憶體中的sorted buffer
- 較舊的：儲存在SSTables

**Write Operation**

- Tablet伺服器確認
- 格式正確
- 發送者是否被授權執行該變更
- 讀取Chubby檔案允許的寫入者列表
- 將有效的變更寫入提交日誌
- Group commit: 提高大量小型變更的吞吐量
- 提交後，內容被insert到memtable

**Read Operation**

- Tablet伺服器確認格式及授權
- 有效的讀取操作會在 SSTables 和 memtable 的merged view上執行
- SSTables 和 memtable 都按字典序排序，可以高效地形成merged view

當 Tablet 進行拆分和合併時，讀取和寫入操作可以持續進行。

### Compactions

**小型壓縮(minor compaction)** 會在memtable達到閾值時啟動。凍結的memtable轉換為SSTable並寫入GFS，以**節省記憶體並減少故障恢復時需要讀取的日誌**。在壓縮過程中，讀寫操作不受影響。

每次小型壓縮都會建立新的SSTable，為**避免讀取操作需合併過多SSTables**，後台定期執行**合併壓縮(merging compaction)**，將幾個SSTables和記憶表的內容合併成一個新的SSTable，完成後即可丟棄原來的。

**主要壓縮(major compaction)** 將所有SSTables合併成一個，不含已刪除的資料，而非主要壓縮產生的SSTable可以包含特殊的刪除條目，這些條目會壓縮仍處於live state的舊 SSTable 中已刪除的資料。主要壓縮有助於資**源回收並確保已刪除的資料及時消失**。

## Refinements

更詳細地描述部分實現細節，以突出這些改進。

**Locality groups**

Client可以將數個column family分為不同的locality group，提高讀取效率。例如，將網頁metadata和內容分開儲存，應用程式只需讀取所需的資料。

此外，可針對每個locality group指定調整參數，例如將某些群組宣告為記憶體中的，以便在不存取磁碟的情況下進行讀取。

**Compression**

Client可以控制是否壓縮locality group的SSTable，以及使用的壓縮格式。

我們使用的2-pass自定義壓縮方案，速度很快且效果良好。
- 1st pass: Bentley and McIlroy's scheme
- 2nd pass: fast compression algorithm that looks for repetitions in a small 16 KB window of the data

在 Webtable 中使用這種壓縮方案儲存網頁內容，可以實現很高的壓縮比（10-to-1 reduction）

在 Bigtable 中存儲同一值的多個版本時，壓縮比會更好。

**Caching for read performance**

為了提升讀取效能，Tablet伺服器使用了two level快取：
- **掃描快取(Scan Cache)**: 快取SSTable介面回傳的key-value pairs，對重複讀取同樣資料的應用很有幫助。
- **區塊快取(Block Cache)**: 快取從GFS讀取的區塊，對傾向讀取最近讀取的資料附近的資料很有幫助。

**Bloom filters**

讀取操作需要從構成Tablet狀態的所有SSTable中讀取。為了減少磁碟訪問次數，Client可以指定在特定locality group中為SSTable創建Bloom filter。Bloom filter可以判斷某個SSTable是否可能包含特定row/column pair的資料，從而減少disk seek次數。

**Commit-log implementation**

為了降低GFS中的磁碟訪問次數，將每個Tablet的提交日誌混合到一個日誌檔案中。這樣做可以提高性能，但在恢復時會變得複雜。因此透過key <table, row name, log sequence number>排序提交日誌條目，提高讀取時的效率。此外，為了避免GFS延遲的影響，每個Tablet伺服器實際上有兩個寫入日誌的執行緒，並且定期切換以保持性能。

**Speeding up tablet recovery**

當master將tablet從一個伺服器移到另一個時，源伺服器首先會對該tablet做小型壓縮，減少未壓縮的狀態，以縮短恢復時間。完成後，伺服器停止serve該tablet，在unload前進行另一個迅速的小型壓縮以確保所有未壓縮的狀態被處理。這樣，tablet可以在其他伺服器上加載，無需恢復日誌條目。

**Exploiting immutability**

Bigtable 系統中的各部分因為所有生成的 SSTables 都是不可變的(immutable)而變得簡化。例如，從 SSTables 讀取時無需同步檔案系統，對row的concurrency control就能很高效的實現。唯一的可變資料結構是memtable，為減少競爭，每個memtable row都是 copy-on-write，允許同時進行讀取和寫入。

由於 SSTables 是不可變的，刪除資料轉化為回收過時 SSTables。每個 Tablet 的 SSTables 在 METADATA 表中註冊，Master 以mark-and-sweep的方式回收過時的SSTables。

SSTables 的不可變性讓我們能快速拆分 Tablet，讓子Tablet共享父Tablet的SSTables。

## Conclusions

Bigtable 是 Google 開發的一個分佈式系統，用於儲存結構化的資料，自 2005 年 4 月以來已投入使用，至 2006 年 8 月已有超過六十個項目在使用。使用者欣賞其性能、高可用性和可擴展性，儘管使用初期在適應上可能有些困難。

規劃中的增強功能包括次級索引(secondary indices)和跨資料中心的複製(infrastructure for building cross-data-center replicated Bigtables with multiple master replicas)。將 Bigtable 作為服務提供的工作也在進行中。內部開發 Bigtable 給了 Google 在處理效率低下問題上更大的靈活性和控制力。

---

## References

原文
https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf