目標#

設計一個分散式且可擴展的系統，能夠儲存大量的結構化資料。資料以列鍵（Row Key）進行索引，每一列（Row）可以擁有不限數量的欄位（Column）。

什麼是 BigTable？#

BigTable 是一個分散式、大規模可擴展的寬欄儲存系統（Wide-column Store）。它專為儲存巨量的結構化資料而設計，如其名稱所暗示，BigTable 提供了儲存超大型表格（通常達到 TB 等級）的能力。

在 CAP 定理中，BigTable 屬於 CP 系統，即提供嚴格一致性（Strictly Consistent）的讀寫操作。BigTable 可以作為 MapReduce 工作的輸入來源或輸出目標。

背景#

BigTable 由 Google 開發，自 2005 年起便在數十項 Google 服務中投入使用。由於其服務規模龐大，Google 無法使用商業資料庫，而使用外部解決方案的成本也過於高昂，因此 Google 選擇自行打造內部解決方案。BigTable 是一個高可用性（High Availability）與高效能的資料庫，支撐了 Google 的多個應用程式，每個應用程式在資料儲存大小和延遲需求上各不相同。

雖然 BigTable 本身並非開源，但其論文對啟發許多強大的開源資料庫至關重要，例如：

• Cassandra：借鑒了 BigTable 的資料模型
• HBase：一個分散式非關聯式資料庫
• Hypertable：另一個受 BigTable 啟發的開源資料庫

BigTable 的使用場景#

Google 建造 BigTable 是為了儲存大量資料並對其執行每秒數千次查詢。BigTable 資料的範例包括數十億個 URL（每個頁面有多個版本）、PB 等級的 Google Earth 資料，以及數十億使用者的搜尋資料。

BigTable 適合儲存以下類型的資料集：

• 資料量大於 1TB
• 每一列小於 10MB
• 資料可以結構化為鍵值對（Key-value Pair）或列欄格式（Row-column）

BigTable 不提供 ACID（原子性、一致性、隔離性、持久性）特性或交易（Transaction）支援，因此不適用於需要交易處理的線上交易處理（OLTP）應用程式。非結構化資料（如圖片或影片）也不應儲存在 BigTable 中。

以下是 Google 在 BigTable 中儲存的資料範例：

• URL 及相關資料：例如 PageRank、頁面內容、爬蟲元資料（爬取時間、回應碼等）、連結、錨點。有數十億個 URL，每個頁面有多個版本。
• 使用者資料：例如偏好設定、最近的查詢／搜尋結果。Google 有數億名使用者。

BigTable 可用於儲存以下類型的資料：

1. 時間序列資料（Time Series Data）：資料天然有序
2. 物聯網資料（IoT Data）：持續的寫入串流
3. 金融資料（Financial Data）：通常以時間序列形式表示

資料模型（Data Model）#

簡單來說，BigTable 可以被描述為一個稀疏的、分散式的、持久的、多維度的、有序映射表（Sorted Map）。

傳統資料庫使用二維資料布局，每個儲存格值由「列 ID（Row ID）」和「欄位名稱（Column Name）」標識。而 BigTable 具有四維資料模型，四個維度分別為：

1. 列鍵（Row Key）：唯一標識一列
2. 欄位族（Column Family）：表示一組欄位的集合
3. 欄位名稱（Column Name）：唯一標識一個欄位
4. 時間戳記（Timestamp）：每個欄位儲存格可以有不同版本的值，每個版本由時間戳記標識

資料以列鍵、欄位鍵（Column Key）和時間戳記進行索引（或排序）。因此，要存取一個儲存格的內容，需要這三個值。如果未指定時間戳記，BigTable 會傳回最新版本。

(row_key: string, column_name: string, timestamp: int64) → cell contents (string)

列（Rows）#

表格中的每一列都有一個關聯的列鍵，它是一個最大 64KB 的任意字串（儘管大多數鍵明顯更小）：

• 每一列由列鍵唯一標識
• 每個列鍵在內部以字串形式表示
• 單一列下的每次讀寫操作都是原子性（Atomic）的。這也意味著跨列的原子性無法保證，例如更新兩列時，一列可能成功，另一列可能失敗
• 表格的資料僅以列鍵、欄位鍵和時間戳記進行索引，不存在次要索引（Secondary Index）

欄位族（Column Families）#

欄位鍵被分組為稱為欄位族的集合。儲存在同一個欄位族中的資料通常屬於相同類型。表格中不同欄位族的數量應該較少（最多數百個），且在運作期間很少變動。存取控制（Access Control）以及磁碟和記憶體的統計都是在欄位族層級執行的。

欄位族的關鍵特性：

• 欄位族格式：family:optional_qualifier
• 所有列都具有相同的欄位族集合
• BigTable 可以高效率地從同一個欄位族中檢索資料
• 較短的欄位族名稱更佳，因為名稱會包含在資料傳輸中

欄位（Columns）#

• 欄位是欄位族中的單位
• BigTable 可以擁有不限數量的欄位
• 新欄位可以隨時動態新增
• 較短的欄位名稱更佳，因為名稱會在每次資料傳輸中傳遞，例如 ColumnFamily:ColumnName => Work:Dept
• BigTable 非常適合稀疏資料，因為空欄位不會被儲存

時間戳記（Timestamps）#

每個欄位儲存格可以包含多個版本的內容。一個 64 位元的時間戳記標識每個版本，該時間戳記可以代表真實時間或由客戶端指定的自訂值。讀取時，如果未指定時間戳記，BigTable 會傳回最新版本。如果客戶端指定了時間戳記，則傳回早於該指定時間戳記的最新版本。

BigTable 支援兩種按欄位族設定的版本垃圾回收（Garbage Collection）策略：

• 僅保留最後 N 個版本
• 僅保留足夠新的版本（例如只保留過去七天內寫入的值）

系統 API#

BigTable 提供兩種類型的操作 API：

中繼資料操作（Metadata Operations）#

BigTable 提供用於建立和刪除表格及欄位族的 API。它還提供用於變更叢集（Cluster）、表格和欄位族中繼資料（例如存取控制權限）的功能。

資料操作（Data Operations）#

客戶端可以在 BigTable 中插入、修改或刪除值，也可以從個別列查詢值或在表格中迭代資料的子集。

資料操作的關鍵特性：

• BigTable 支援單列交易（Single-row Transaction），可用於對單一列鍵下的資料執行原子性的讀取-修改-寫入（Read-modify-write）序列
• BigTable 不支援跨列鍵的交易，但提供跨列鍵批次寫入的客戶端介面
• 儲存格可以用作整數計數器
• BigTable 可以同時作為 MapReduce 工作的輸入來源和輸出目標
• 客戶端也可以使用 Sawzall（Google 開發的語言）編寫腳本，在網路傳輸之前指示伺服器端的資料處理（轉換、過濾、彙總）

寫入操作的 API：

• Set()：寫入一列中的儲存格
• DeleteCells()：刪除一列中的儲存格
• DeleteRow()：刪除一列中所有的儲存格

讀取操作的特性：

• 每次列讀取操作都是原子性的
• 可以請求單一列或所有列的資料
• 可以將傳回的列限制在特定範圍內
• 可以請求所有欄位、特定欄位族或特定欄位

分區與高階架構#

表格分區（Table Partitioning）#

BigTable 的單一實例稱為叢集（Cluster）。每個叢集可以儲存多個表格，每個表格被拆分為多個 Tablet，每個 Tablet 大約 100-200 MB。

Tablet 的關鍵特性：

• 一個 Tablet 持有一組連續範圍的列
• 表格在列的邊界處被拆分為 Tablet
• 初始時，每個表格僅包含一個 Tablet。隨著表格增長，會建立多個 Tablet。預設情況下，表格大約在 100 至 200 MB 時拆分
• Tablet 是分配和負載平衡（Load Balancing）的單位
• 由於表格按列排序，讀取短範圍的列始終是高效率的，即只需與少數 Tablet 通訊
• 選擇具有高度局部性（Locality）的列鍵非常重要
• 每個 Tablet 被指派給一個 Tablet 伺服器（Tablet Server），管理該 Tablet 的所有讀寫請求

高階架構#

BigTable 叢集的架構由三個主要元件組成：

1. 客戶端程式庫（Client Library）：連結到每個客戶端的程式庫元件。客戶端透過此程式庫與 BigTable 通訊。
2. 一個主伺服器（Master Server）：負責執行中繼資料操作，以及將 Tablet 指派給 Tablet 伺服器並管理它們。
3. 多個 Tablet 伺服器：每個 Tablet 伺服器為其被指派的 Tablet 提供資料的讀寫服務。

BigTable 建構在 Google 基礎設施的多個元件之上：

1. GFS：BigTable 使用 Google 檔案系統（Google File System）來儲存其資料和日誌檔案。
2. SSTable：Google 的 SSTable（Sorted String Table，有序字串表）檔案格式用於儲存 BigTable 資料。SSTable 提供持久的、有序的、不可變的（Immutable）鍵值映射。SSTable 的設計確保任何資料存取最多只需一次磁碟存取。
3. Chubby：BigTable 使用一個高可用且持久的分散式鎖定服務（Distributed Lock Service）Chubby 來處理同步問題和儲存設定資訊。
4. 叢集排程系統（Cluster Scheduling System）：Google 的叢集管理系統負責排程、監控和管理 BigTable 的叢集。

SSTable#

Tablet 如何儲存在 GFS 中？#

BigTable 使用 Google 檔案系統（GFS）這個持久的分散式檔案儲存系統，以檔案形式儲存資料。BigTable 用來儲存檔案的格式稱為 SSTable：

• SSTable 是持久的、有序的鍵值映射，其中鍵和值都是任意的位元組字串
• 每個 Tablet 以一系列稱為 SSTable 的檔案儲存在 GFS 中
• 一個 SSTable 由一系列資料區塊（Data Block）組成（通常為 64KB 大小）

• 區塊索引（Block Index）用於定位區塊；索引在 SSTable 開啟時載入記憶體

• 透過在記憶體中的索引進行二元搜尋（Binary Search）找到適當的區塊，然後從磁碟讀取該區塊，僅需一次磁碟搜尋即可完成查詢
• 讀取 SSTable 資料時，可以將整個 SSTable 複製到記憶體，或僅載入索引。前者避免了後續查詢的磁碟搜尋，後者每次查詢需要一次磁碟搜尋

SSTable 提供兩種操作：

• 取得與給定鍵關聯的值
• 在給定鍵範圍內迭代一組值

每個 SSTable 一旦寫入 GFS 即為不可變的（Immutable，唯讀）。如果新增資料，會建立新的 SSTable。一旦舊的 SSTable 不再需要，就會被標記為垃圾回收。SSTable 的不可變性是 BigTable 資料檢查點和恢復流程的核心，提供以下優勢：

• 讀取操作期間不需要同步
• 更容易拆分 Tablet
• 垃圾回收器處理已刪除或過期資料的永久移除

Table vs. Tablet vs. SSTable#

Table、Tablet 和 SSTable 之間的關係：

• 多個 Tablet 構成一個 Table
• SSTable 可以被多個 Tablet 共享
• Tablet 不會重疊，SSTable 可以重疊

為了提升寫入效能，BigTable 使用一個記憶體中的、可變的排序緩衝區，稱為 MemTable，來儲存最近的更新。隨著更多寫入操作的執行，MemTable 大小增加，當達到閾值時，MemTable 被凍結，建立新的 MemTable，凍結的 MemTable 被轉換為 SSTable 並寫入 GFS。

每次資料更新也會寫入一個提交日誌（Commit Log），該日誌同樣儲存在 GFS 中。此日誌包含重做記錄（Redo Record），用於在 Tablet 伺服器在將 MemTable 提交到 SSTable 之前失敗時進行恢復。

讀取時，資料可能在 MemTable 或 SSTable 中。由於兩者都是排序的，因此很容易找到最新的資料。

GFS 與 Chubby#

GFS#

GFS 是 Google 為其大型資料密集型應用程式（如 BigTable）開發的可擴展分散式檔案系統。

• GFS 檔案被拆分為固定大小的區塊，稱為 Chunk
• Chunk 儲存在稱為 ChunkServer 的資料伺服器上
• GFS Master 管理中繼資料
• SSTable 被分割為固定大小的區塊，這些區塊儲存在 ChunkServer 上
• GFS 中的每個 Chunk 跨多個 ChunkServer 複製以確保可靠性
• 客戶端與 GFS Master 互動以取得中繼資料，但所有資料傳輸直接在客戶端和 ChunkServer 之間進行

Chubby#

Chubby 是一個高可用且持久的分散式鎖定服務，允許擁有數千個節點的 BigTable 叢集保持協調。

Chubby 的關鍵特性：

• Chubby 通常執行五個活動副本（Replica），其中一個被選舉為主節點（Master）來處理請求。要保持運作，Chubby 的多數副本必須正在執行
• BigTable 高度依賴 Chubby，如果 Chubby 長時間不可用，BigTable 也將變得不可用
• Chubby 使用 Paxos 演算法在面對故障時保持其副本的一致性

Chubby 提供由檔案和目錄組成的命名空間（Namespace）。每個檔案或目錄可以用作鎖定（Lock）：

• 對 Chubby 檔案的讀寫存取是原子性的
• 每個 Chubby 客戶端與 Chubby 服務維護一個會話（Session）。如果客戶端無法在租約到期時間內續約其會話租約（Session Lease），則會話過期
• 當客戶端的會話過期時，它會失去所有鎖定和開啟的控制代碼（Handle）
• Chubby 客戶端也可以在 Chubby 檔案和目錄上註冊回呼（Callback），以接收變更或會話過期的通知

在 BigTable 中，Chubby 用於：

• 確保只有一個活動的主伺服器。主伺服器與 Chubby 維護一個會話租約，並定期續約以保持主伺服器的狀態
• 儲存 BigTable 資料的啟動位置（Bootstrap Location）
• 發現新的 Tablet 伺服器以及檢測現有伺服器的故障
• 儲存 BigTable 的綱要資訊（Schema Information，每個表格的欄位族資訊）
• 儲存存取控制清單（ACL，Access Control List）

BigTable 元件#

如前所述，BigTable 叢集由三個主要元件組成：

1. 連結到每個客戶端的程式庫元件
2. 一個主伺服器
3. 多個 Tablet 伺服器

主伺服器（Master Server）#

BigTable 叢集中只有一個主伺服器，負責：

• 將 Tablet 指派給 Tablet 伺服器並確保有效的負載平衡
• 監控 Tablet 伺服器的狀態，管理 Tablet 伺服器的加入或故障
• 垃圾回收儲存在 GFS 中的底層檔案
• 處理中繼資料操作，例如表格和欄位族的建立

BigTable 的主伺服器不參與將 Tablet 映射到 GFS 底層檔案的核心任務（這由 Tablet 伺服器處理）。這意味著 BigTable 客戶端完全不需要與主伺服器通訊。此設計決策大幅降低了主伺服器的負載，並減少了主伺服器成為瓶頸的可能性。

Tablet 伺服器#

• 每個 Tablet 伺服器由主伺服器指派一定數量的 Tablet（通常每台伺服器 10 至 1,000 個 Tablet）
• 每個 Tablet 伺服器為其被指派的 Tablet 提供資料的讀寫服務。客戶端直接與 Tablet 伺服器通訊進行讀寫
• Tablet 伺服器可以動態地從叢集中新增或移除，以適應工作負載的變化
• Tablet 的建立、刪除或合併由主伺服器發起，而 Tablet 的分割由 Tablet 伺服器處理並通知主伺服器

使用 Tablet#

定位 Tablet（Locating Tablets）#

由於 Tablet 會在伺服器之間移動（因為負載平衡、Tablet 伺服器故障等），給定一列，如何找到正確的 Tablet 伺服器？BigTable 維護一個三層階層結構，類似於 B+ 樹，來儲存 Tablet 的位置資訊。

BigTable 建立一個特殊的表格，稱為 Metadata 表格，來儲存 Tablet 的位置。此 Metadata 表格為每個 Tablet 包含一列，告訴我們哪個 Tablet 伺服器正在服務此 Tablet。METADATA 表格中的每一列在列鍵下儲存 Tablet 的位置，該列鍵是 Tablet 的表格識別碼和其結束列的編碼。

METADATA: Key: table id + end row
          Data: tablet server location

BigTable 將 Metadata 表格的資訊分為兩部分：

1. Meta-1 Tablet：為每個資料 Tablet（或非 Meta Tablet）包含一列。由於 Meta-1 Tablet 可能很大，它會被拆分為多個 Metadata Tablet 並分佈到多個 Tablet 伺服器
2. Meta-0 Tablet：為每個 Meta-1 Tablet 包含一列。Meta-0 表格永遠不會被拆分。BigTable 將 Meta-0 Tablet 的位置儲存在一個 Chubby 檔案中

尋找 Tablet 位置的 BigTable 客戶端，首先在 Chubby 中查詢一個已知持有 Meta-0 Tablet 位置的特定檔案。此 Meta-0 Tablet 包含其他 Metadata Tablet 的資訊，這些 Tablet 又包含實際資料 Tablet 的位置。透過此方案，樹的深度限制為三層。為了提升效率，客戶端程式庫會快取（Cache）Tablet 的位置，並在讀取 METADATA 表格時預先載入（Prefetch）與其他 Tablet 相關的中繼資料。

指派 Tablet（Assigning Tablets）#

一個 Tablet 在任何時間只被指派給一個 Tablet 伺服器。主伺服器追蹤所有活動的 Tablet 伺服器以及 Tablet 到 Tablet 伺服器的映射。主伺服器也追蹤任何未指派的 Tablet，並將它們指派給有足夠空間的 Tablet 伺服器。

當 Tablet 伺服器啟動時，它會在 Chubby 的「servers」目錄中建立並取得一個唯一命名檔案的獨佔鎖定（Exclusive Lock）。此機制用於告知主伺服器該 Tablet 伺服器處於活動狀態。

當主伺服器由叢集管理系統重新啟動時，會發生以下事情：

1. 主伺服器在 Chubby 中取得一個唯一的主鎖定（Master Lock），以防止多個主伺服器實例化
2. 主伺服器掃描 Chubby 的「servers」目錄以找到活動的 Tablet 伺服器
3. 主伺服器與每個活動的 Tablet 伺服器通訊，以發現每台伺服器被指派了哪些 Tablet
4. 主伺服器掃描 METADATA 表格以了解完整的 Tablet 集合。每當此掃描遇到尚未被指派的 Tablet，主伺服器就將該 Tablet 加入未指派 Tablet 的集合。同樣地，主伺服器建立一組未指派的 Tablet 伺服器，這些伺服器有資格進行 Tablet 指派。主伺服器利用此資訊將未指派的 Tablet 指派給適當的 Tablet 伺服器

flowchart TD
    A[主伺服器 Master 偵測到\nTablet 伺服器故障] --> B[1. 重新指派故障伺服器的\nTablet 至其他伺服器]
    B --> C[2. 新伺服器從 METADATA 表格\n讀取 Tablet 中繼資料]
    C --> D[3. 新伺服器從提交日誌\n CommitLog 載入重做記錄]
    D --> E[4. 從 SSTable 讀取\n已持久化的資料]
    E --> F[重建 MemTable 狀態\n恢復 Tablet 服務]

    style A fill:#f96,stroke:#333
    style F fill:#6f9,stroke:#333

監控 Tablet 伺服器（Monitoring Tablet Servers）#

BigTable 在 Chubby 中維護一個「Servers」目錄，其中為每個活動的 Tablet 伺服器包含一個檔案。每當新的 Tablet 伺服器上線時，它會在此目錄中建立一個新檔案以表明其可用性，並取得此檔案的獨佔鎖定。只要 Tablet 伺服器保持其 Chubby 檔案上的鎖定，它就被視為活動的。

BigTable 的主伺服器持續監控「Servers」目錄，每當在此目錄中看到新檔案時，它就知道有新的 Tablet 伺服器可用並準備好被指派 Tablet。此外，主伺服器定期檢查鎖定的狀態。如果鎖定遺失，主伺服器會假設 Tablet 伺服器或 Chubby 出了問題。在這種情況下，主伺服器嘗試取得鎖定，如果成功，它就確定 Chubby 運作正常，而 Tablet 伺服器有問題。此時主伺服器刪除該檔案並重新指派故障 Tablet 伺服器的 Tablet。檔案的刪除作為一個訊號，讓故障的 Tablet 伺服器終止自己並停止服務 Tablet。

每當 Tablet 伺服器失去其在「servers」目錄中建立的檔案上的鎖定時，它會停止服務其 Tablet。它嘗試再次取得鎖定，如果成功，則認為這是暫時的網路問題並重新開始服務 Tablet。如果檔案被刪除，則 Tablet 伺服器終止自己以重新開始。

flowchart TD
    A[主伺服器 Master 定期檢查\nTablet 伺服器狀態] --> B{Tablet 伺服器的\nChubby 鎖定是否存在？}
    B -- 是 --> C[伺服器正常運作]
    B -- 否 --> D[鎖定遺失：伺服器或\nChubby 可能有問題]
    D --> E{主伺服器嘗試取得\n該伺服器的 Chubby 鎖定}
    E -- 取得成功 --> F[確認 Chubby 正常\nTablet 伺服器已故障]
    F --> G[刪除伺服器的 Chubby 檔案]
    G --> H[重新指派該伺服器的\n所有 Tablet]
    E -- 取得失敗 --> I[Chubby 本身可能有問題\n主伺服器等待恢復]

    style C fill:#6f9,stroke:#333
    style F fill:#f96,stroke:#333
    style I fill:#ff9,stroke:#333

負載平衡 Tablet 伺服器#

主伺服器負責將 Tablet 指派給 Tablet 伺服器。主伺服器追蹤所有可用的 Tablet 伺服器，並維護叢集應該服務的 Tablet 清單。此外，主伺服器定期詢問 Tablet 伺服器的當前負載。所有這些資訊讓主伺服器擁有叢集的全域視圖，並幫助進行 Tablet 的指派和負載平衡。

讀寫操作的生命週期#

寫入請求（Write Request）#

收到寫入請求時，Tablet 伺服器執行以下步驟：

1. 檢查請求格式是否正確
2. 檢查發送者是否有權執行變更（Mutation）。此授權基於儲存在 Chubby 檔案中的存取控制清單（ACL）
3. 如果上述兩個條件都滿足，變更被寫入 GFS 中的提交日誌（Commit Log），該日誌儲存重做記錄
4. 一旦變更被提交到提交日誌，其內容就儲存在記憶體中的排序緩衝區 MemTable 中
5. 將資料插入 MemTable 後，向客戶端發送確認，表示資料已成功寫入
6. MemTable 定期被刷新（Flush）為 SSTable，SSTable 在壓縮（Compaction）期間被合併

sequenceDiagram
    participant C as 客戶端 (Client)
    participant TS as Tablet 伺服器 (Tablet Server)
    participant CL as 提交日誌 (CommitLog/WAL)
    participant MT as 記憶體表 (MemTable)
    participant SS as SSTable (GFS)

    C->>TS: 1. 發送寫入請求
    TS->>TS: 2. 檢查授權 (從 Chubby 取得 ACL)
    TS->>CL: 3. 寫入變更至提交日誌 (WAL)
    CL-->>TS: 確認提交完成
    TS->>MT: 4. 將資料插入 MemTable
    MT-->>TS: 插入完成
    TS-->>C: 5. 回傳寫入確認
    Note over MT,SS: 6. 當 MemTable 達到閾值時
    MT->>SS: 刷新 (Flush) 為 SSTable 至 GFS
    Note over SS: 壓縮 (Compaction) 合併多個 SSTable

讀取請求（Read Request）#

收到讀取請求時，Tablet 伺服器執行以下步驟：

1. 檢查請求格式是否正確且發送者已被授權
2. 如果資料在快取（Cache）中可用，則傳回
3. 首先讀取 MemTable 以找到所需的列
4. 讀取載入記憶體中的 SSTable 索引，找到包含所需資料的 SSTable，然後從這些 SSTable 中讀取列
5. 合併從 MemTable 和 SSTable 讀取的列以找到所需版本的資料。由於 SSTable 和 MemTable 都是排序的，合併視圖可以高效率地形成

flowchart TD
    A[收到讀取請求] --> B{1. 格式正確且已授權？}
    B -- 否 --> C[拒絕請求]
    B -- 是 --> D{2. 資料在快取 Cache 中？}
    D -- 是 --> E[直接傳回快取資料]
    D -- 否 --> F[3. 查詢 MemTable 最近資料]
    F --> G[4. 使用布隆過濾器 Bloom Filter\n篩選相關的 SSTable]
    G --> H[從符合的 SSTable 讀取資料]
    H --> I[5. 合併 MemTable + SSTable 結果]
    I --> J[傳回合併後的最新版本資料]

容錯與壓縮#

容錯與複製（Fault Tolerance and Replication）#

BigTable 使用兩個獨立的系統 Chubby 和 GFS，它們都採用複製策略以實現容錯和更高的可用性（架構詳見前述 GFS 與 Chubby 章節的圖示）：

• Chubby 單元（Cell）通常由五台伺服器組成，其中一台成為主伺服器，其餘四台作為副本。如果主伺服器故障，其中一個副本被選舉為領導者，從而最大限度地減少 Chubby 的停機時間
• GFS 在不同的 ChunkServer 上儲存資料的多個副本

Tablet 伺服器的容錯#

BigTable 的主伺服器負責監控 Tablet 伺服器。主伺服器透過定期檢查每個 Tablet 伺服器的 Chubby 鎖定狀態來完成此工作。當主伺服器發現 Tablet 伺服器已經故障時，它會重新指派故障 Tablet 伺服器的 Tablet。

主伺服器的容錯#

主伺服器在 Chubby 檔案中取得鎖定並維護租約。如果在任何時候主伺服器的租約到期，它會自行終止。當 Google 的叢集管理系統發現沒有活動的主伺服器時，它會啟動一個新的主伺服器。新的主伺服器必須在 Chubby 檔案上取得鎖定後才能作為主伺服器運作。

壓縮（Compaction）#

BigTable 中的變更會佔用額外空間，直到壓縮發生。BigTable 在背景管理壓縮。以下是壓縮的類型：

1. 次要壓縮（Minor Compaction）：隨著寫入操作的執行，MemTable 大小增長。當 MemTable 達到特定閾值時，它被凍結，並建立新的 MemTable。凍結的 MemTable 被轉換為 SSTable 並寫入 GFS。次要壓縮有兩個好處：

   • 減少 Tablet 伺服器的記憶體使用量，因為它將 MemTable 刷新到 GFS。一旦 MemTable 寫入 GFS，提交日誌中的相應條目也會被移除
   • 減少在伺服器故障恢復期間需要從提交日誌讀取的資料量

2. 合併壓縮（Merging Compaction）：次要壓縮不斷增加 SSTable 的數量。這意味著讀取操作可能需要從任意數量的 SSTable 合併更新。為了減少 SSTable 的數量，會執行合併壓縮，讀取幾個 SSTable 和 MemTable 的內容並寫出一個新的 SSTable。輸入的 SSTable 和 MemTable 在壓縮完成後可以被丟棄

3. 主要壓縮（Major Compaction）：在主要壓縮中，所有 SSTable 被寫入單一個 SSTable。主要壓縮產生的 SSTable 不包含任何刪除資訊或已刪除的資料，而非主要壓縮產生的 SSTable 可能包含已刪除的條目。主要壓縮允許 BigTable 回收被已刪除資料使用的資源，並確保已刪除的資料從系統中快速消失，這對儲存敏感資料的服務非常重要

BigTable 的最佳化#

BigTable 實作了若干最佳化以實現高效能、可用性和可靠性。

局部性群組（Locality Groups）#

客戶端可以將多個欄位族組合成一個局部性群組。BigTable 為每個局部性群組產生獨立的 SSTable。這有兩個好處：

• 將經常一起存取的欄位分組在一個局部性群組中，可以提升讀取效能
• 客戶端可以明確宣告任何局部性群組存放在記憶體中以加速存取。這樣，經常存取的較小局部性群組可以保留在記憶體中

掃描一個局部性群組的複雜度為 O(bytes_in_locality_group)，而非 O(bytes_in_table)。

壓縮（Compression）#

客戶端可以選擇壓縮局部性群組的 SSTable 以節省空間。BigTable 允許客戶端根據其應用需求選擇壓縮技術。當儲存同一資料的多個版本時，壓縮率更佳。壓縮分別應用於每個 SSTable 區塊。

快取（Caching）#

為了提升讀取效能，Tablet 伺服器採用兩級快取：

• 掃描快取（Scan Cache）：快取 SSTable 傳回的（鍵, 值）對，適用於多次讀取相同資料的應用程式
• 區塊快取（Block Cache）：快取從 GFS 讀取的 SSTable 區塊，適用於傾向讀取與最近讀取的資料相近的資料的應用程式（例如，在經常存取的列中同一局部性群組內不同欄位的循序或隨機讀取）

布隆過濾器（Bloom Filters）#

任何讀取操作都必須從構成 Tablet 的所有 SSTable 中讀取。如果這些 SSTable 不在記憶體中，讀取操作可能會進行多次磁碟存取。為了減少磁碟存取次數，BigTable 使用布隆過濾器。

布隆過濾器為 SSTable（特別是局部性群組）建立。它們透過預測 SSTable 是否可能包含與特定（列, 欄位）對應的資料，來幫助減少磁碟存取次數。布隆過濾器佔用少量記憶體，但可以大幅提升讀取效能。

統一提交日誌（Unified Commit Log）#

BigTable 不為每個 Tablet 維護單獨的提交日誌檔案，而是為每個 Tablet 伺服器維護一個日誌檔案。這提供了更好的寫入效能，因為每次寫入都必須寫入提交日誌，寫入大量日誌檔案會因大量磁碟搜尋而變慢。

單一日誌檔案的一個缺點是使 Tablet 恢復過程變得複雜。當 Tablet 伺服器故障時，它服務的 Tablet 將被移動到其他 Tablet 伺服器。為了恢復 Tablet 的狀態，新的 Tablet 伺服器需要從原始 Tablet 伺服器寫入的提交日誌中重新應用該 Tablet 的變更。然而，這些 Tablet 的變更混合在同一個實體日誌檔案中。

一種方法是讓每個新的 Tablet 伺服器讀取完整的提交日誌檔案，並僅應用恢復所需 Tablet 的條目。但在此方案下，如果 100 台機器各被指派一個來自故障 Tablet 伺服器的 Tablet，則日誌檔案將被讀取 100 次。BigTable 透過先按鍵 <table, row name, log sequence number> 的順序排序提交日誌條目來避免重複讀取日誌。在排序後的輸出中，特定 Tablet 的所有變更是連續的，因此可以高效率地讀取。

為了進一步提升效能，每個 Tablet 伺服器維護兩個日誌寫入執行緒，每個執行緒寫入其自己的獨立日誌檔案。在任何時刻只有一個執行緒處於活動狀態。如果其中一個執行緒效能不佳（例如由於網路壅塞），寫入會切換到另一個執行緒。日誌條目包含序列號以支援恢復過程。

加速 Tablet 恢復#

載入 Tablet 時一個複雜且耗時的任務是確保 Tablet 伺服器載入提交日誌中的所有條目。當主伺服器將 Tablet 從一個 Tablet 伺服器移動到另一個時，來源 Tablet 伺服器執行壓縮以確保目標 Tablet 伺服器不需要讀取提交日誌。這分三個步驟完成：

1. 來源伺服器執行一次次要壓縮。此壓縮減少提交日誌中的資料量
2. 之後，來源 Tablet 伺服器停止服務該 Tablet
3. 最後，來源伺服器執行另一次（通常非常快速的）次要壓縮，以應用在第一次次要壓縮執行期間到達的任何新日誌條目。在第二次次要壓縮完成後，Tablet 可以載入到另一個 Tablet 伺服器上，而不需要恢復任何日誌條目

BigTable 特性#

BigTable 的效能#

以下是 BigTable 效能和受歡迎的幾個原因：

Dynamo vs. BigTable#

以下是 Dynamo 與 BigTable 的比較：

基於 BigTable 原則開發的資料儲存系統#

Google 的 BigTable 啟發了許多 NoSQL 系統。以下是幾個著名的系統：

• HBase：一個開源的分散式非關聯式資料庫，以 BigTable 為模型，建構在 Hadoop 分散式檔案系統（HDFS）之上
• Hypertable：類似於 HBase，是 BigTable 的開源實作，使用 C++ 編寫。與 BigTable 只使用一個儲存層（GFS）不同，Hypertable 能夠在任何檔案系統上執行（例如 HDFS、GlusterFS 或 CloudStore）。為此，系統透過分散式檔案系統代理程序（Broker Process）發送所有資料請求，抽象化了檔案系統的介面
• Cassandra：一個分散式、去中心化且高可用的 NoSQL 資料庫。其架構基於 Dynamo 和 BigTable。Cassandra 可以被描述為在類似 Dynamo 的基礎設施上執行的類似 BigTable 的資料儲存。Cassandra 也是寬欄儲存，並使用 BigTable 的儲存模型，即 SSTable 和 MemTable

總結#

• BigTable 是 Google 的分散式儲存系統，設計用於管理大量結構化資料，具有高可用性、低延遲、可擴展性和容錯目標
• BigTable 是一個稀疏的、分散式的、持久的、多維度的有序映射表
• 映射表以由列鍵、欄位鍵和時間戳記組成的唯一鍵進行索引
• 每個列鍵是最大 64KB 的任意字串，大多數鍵明顯更小
• 不同於傳統的關聯式資料庫表格，BigTable 是具有不限數量欄位的寬欄資料儲存
• 欄位被分組為欄位族。每個欄位族以「family:qualifier」的欄位鍵儲存相同類型的資料
• 列鍵和欄位（族限定詞）鍵唯一標識一個資料儲存格。在每個儲存格中，資料內容進一步以時間戳記索引，提供資料隨時間的多個版本
• 單一列下的每次讀寫都是原子性的。跨列的原子性無法保證
• BigTable 提供用於中繼資料操作（如建立和刪除表格及欄位族）的 API。客戶端可以使用資料操作 API 來寫入或刪除值、從個別列查詢值，或迭代表格中資料的子集
• 表格被拆分為較小的列範圍，稱為 Tablet。Tablet 持有一組連續範圍的列
• Tablet 是分配和負載平衡的單位
• BigTable 架構由一個主伺服器和多個 Tablet 伺服器組成
• 主伺服器負責將 Tablet 指派給 Tablet 伺服器，以及監控和平衡 Tablet 伺服器的負載
• 每個 Tablet 伺服器為其被指派的 Tablet 提供資料的讀寫服務
• BigTable 客戶端直接與 Tablet 伺服器通訊以讀寫資料
• 每個 Tablet 伺服器以不可變的 SSTable 檔案儲存資料，存放在 Google 檔案系統（GFS）中
• 新提交的更新首先儲存在基於記憶體的 MemTable 中
• BigTable 對 SSTable 和 MemTable 的合併視圖執行所有讀取操作
• MemTable 定期被刷新為 SSTable，以實現高效率的記憶體使用
• 為提升讀取效能，BigTable 使用快取和布隆過濾器
• BigTable 高度依賴分散式鎖定服務 Chubby 進行主伺服器選舉和監控

參考資料與延伸閱讀#

• Bigtable: A Distributed Storage System for Structured Data ^↗