[Paper Reading] Bigtable: A Distributed Storage System for Structured Data

目錄

===== 1. Introduction

===== 2. Data Model

===== 2.1 Row

===== 2.2 Column Family

===== 2.3 Timestamp

===== 3. API

===== 4. Building Blocks

===== 5. Implementation

===== 5.1 Tablet Location

===== 5.2 Tablet Assignment

===== 5.3 Tablet Serving

===== 5.4 Compactions

===== 6. Refinements

===== 6.1 Locality groups

===== 6.2 Compression

===== 6.3 Caching for read performance

===== 6.4 Bloom filters

===== 6.5 Commit-log implementation

===== 6.6 Speeding up tablet recovery

===== 6.7 Exploiting immutability

===== 7-9 略

===== 10 Related Work

===== 1. Introduction

Bigtable 被設計為一個 PB級資料量、數千機器的可擴充存儲系統。設計目标包括：wide applicability、scalability、high performance、high availablity

Bigtable 在 google 應用在各種場景：從 吞吐較高的批處理job 到 延遲敏感的服務，設計 60多個産品項目

在許多方面，Bigtable 類似 database：與 database 有許多相同的政策。

• Parallel databases [14] & main-memory databases [13] 實作擴充性&高性能，Bigtable 在此基礎上還提供了不同的 interface
• Bigtable 沒有提供一個完全 關系資料模型，而是提供一個 支援控制資料layout&formt（Dynamic control over data layout and format）、允許用戶端對底層資料的位置屬性進行推理（reason about the locality properties of the data） 的簡單資料模型
• 使用行&列名稱對資料進行索引，并将資料視為 未解析的字元串（uninterpreted strings）
• 用戶端可以通過對schema的選項來控制資料的位置，schema也提供參數來動态控制從記憶體還是磁盤提供資料

===== 2. Data Model

【資料結構管理】Bigtable 是一個 稀疏、分布式、持久化的多元sorted map。這個map的索引key 是 row key + column key + timestamp，每個value都是一個 uninterpreted位元組數組

===== 2.1 Row

Row key 可以是任意的字元串，最大支援64KB，10-100B是常見大小。

對單rowKey的讀寫都是原子的（無論列多少），這樣便于用戶端對相同行的更新時推斷系統行為。

Row key 按照字典序排列

【分片方式 -- tablet】資料按照行範圍動态分片，每個分片稱為一個 tablet，tablet 是資料分布&負載均衡的基本單元。

讀取小範圍的資料僅需要和少量的machine互動即可，用戶端可以利用這個屬性來選擇row key，便于他們很好的擷取資料通路位置

===== 2.2 Column Family

Column key 被分組到一個集合中，稱為 column family，存儲在同一個column family中的資料類型往往是相同的，這些資料會被壓縮存儲在一起。

通路控制 以及 記憶體&磁盤的管理都是在 column family 級别完成的。

Column family必須提前建立好，随後才可以向其中的任意 column key 中插入資料。因為 column family 通常比較少（最多上百個）而且極少修改，而column可能特别多。

Column key使用如下的文法命名：family:qualifier。Column family的名字必須是可列印的（printable），而qualifier可以是任意字元。

===== 2.3 Timestamp

Bigtable 中的每個 cell 都包含相同資料的多個版本，這個版本按照 timestamp 索引。

每個 timestamp 都是一個 64bit integer，這個 ts 可以由 Bigtable 生成，也可以由用戶端指定。用戶端如果要避免碰撞，需要指定不同的時間戳。cell中不同的version按照 ts 降序排列，是以最新的資料會先被讀到

支援2種版本回收政策：保留最近n個版本、保留最近n天的版本

===== 3. API

Bigtable API 提供 建立删除 table&column family 的能力，也提供修改 cluster、table、column family metadata的能力

用戶端可以寫入、删除 value，也可以查詢行資訊并疊代讀取。如下展示了 讀寫 的 代碼

Bigtable 還支援一些其他特性：

• 支援單行事務，但不支援跨行事務
• 允許 cell 被當作 integer 計數器使用
• 支援 client定義的script 執行 — 腳本由 Sawzall [28] 語言編寫，部署在 Google上
• Bigtable 可以與 MapReduce [12] 結合使用，可以作為 MR 的 input或者output

===== 4. Building Blocks

Bigtable 在 許多 Google 基礎元件上建構完成。

【GFS】

Bigtable 使用 GFS [17] 來存儲日志和資料。

Bigtable 與其他服務混部運作，以來管理系統排程資源實作機器共享。

【SSTable】Google SSTable 檔案格式被用來存儲 Bigtable 的資料。SSTable 提供持久化的、有序不可修改的map結構，key&value都是任意的字元串。

【Block】每個SSTable 包含多個block，每個block預設 64KB 大小，可配置。

【基于SSTable-Block的查找操作】block的index存儲在SSTable 的最後，當 SSTable open的時候就會加載到記憶體中。這樣查找操作隻需要一次 disk seek 就可以完成：首先從記憶體index中查找對應的block，然後從磁盤中讀取對應的block。此外， SSTable可以被映射到記憶體，這樣查找的時候無序和磁盤互動。

【Chubby】

Bigtable 還依賴 一個高可用、分布式的鎖服務，稱為 Chubby [8]。Chubby 使用 Paxos 協定來保證一緻性 [9, 23]。其提供 namespace 由 dir & file 組成。每個dir & file 都可以被用作lock使用，讀寫都是 atomic 的。Chubby 用戶端維護一個 session，基于 lease 機制重新整理，lease 過期就可能會被搶占鎖。Chubby服務長時間不可用，則Bigtable 就會不可用。

Bigtable 使用Chubby完成各種功能：

• 確定任意時間隻有一個 active master
• 存儲 啟動時用到的 Bigtable 資料
• 發現 tablet 節點 & tablet節點探活
• 存儲 Bigtable schema 資訊
• 存儲 通路控制資訊

===== 5. Implementation

Bigtable 有 3 個主要的元件：一個client library、master server、tablet server。

Master server負責：

• 配置設定 tablet 給 tablet server：assign tablet to tablet server
• 檢測 tablet server 的增删：detect the addition and expiration of tablet server
• 均衡 tablet server的負載：balance tablet server load
• 對 GFS 上的檔案進行 GC：garbage collection of files in GFS
• 處理 schema change：handle schema change

Tablet server可以被動态的添加&删除，每個 tablet server 負責：

• 管理tablet
• 負責其加載的 tablet 的讀寫
• Tablet split

與許多 single-master distributed storage system [17, 21] 相同，client的資料通路不經過 master，而是直接與tablet server互動完成。因為 client 不依賴master來擷取tablet的location資訊，大部分client從不和master互動，是以master會有較低的負載

Bigtable 會存儲多個 table，每個table由多個 tablet 組成，每個 tablet 存儲配置設定給他的行範圍的所有資料。初始情況下，每個table 隻包含一個 tablet，當table增長的時候，系統會自動分裂 tablet，分裂門檻值大約為 100-200MB

===== 5.1 Tablet Location

Bigtable 采用一個 類似B+-Tree [10] 的三級繼承結構（chubby file + root tablet + metadata tablet）。

第一級為存儲在 Chubby file，其中存儲 root tablet 的位置。

Root tablet 中包含 METADATA 表的所有 tablet 存儲位置。

每個 METADATA tablet 存儲一些使用者 tablet 的位置。

Root tablet是 METADATA tablet 中存儲的 第一個 tablet，并且永遠不會分裂，保證 tablet 的層級結構不超過三級

METADATA 表使用其 row key 來管理 tablet 的位置，row key 由 table的辨別符 及 end row 編碼完成。每個 METADATA 的 row 大約存儲 1KB 的資料，對于 128MB 的 METADATA tablet，三級結構可以存儲 2^34個 tablet。

Client library 會緩存 tablet 的位置資訊。當client不清楚 tablet資訊時，會遞歸的向上查詢。

Tablet 的資訊存儲在記憶體上，以避免 GFS 通路開銷，在此之上還會在每次加載 tablet 的時候進行tablet預讀，進一步降低延遲。

===== 5.2 Tablet Assignment

每個 tablet 同一時間隻會被配置設定到一個 tablet server上，master會跟蹤活躍 tablet server 及其上 tablet 的配置設定情況（包括未配置設定的tablet）。master通過給 tablet server 發送一個 load請求 來配置設定 tablet

Bigtable 使用 Chubby 來跟蹤 tablet server。Tablet server 啟動的時候會持有一個 Chubby 鎖，master節點會通過監聽 Chubby 鎖所在的 dir 來發現 tablet server。Tablet server 會保持 Chubby鎖，同時提供服務，失去鎖則停止服務。

【master探測tablet server的政策及reassign tablet】

master負責探測 tablet server負載提供某個 tablet 的服務，然後重配置設定這個 tablet。

發現機制：master定期給每個 tablet server 發送心跳擷取其鎖的狀态。

如果心跳失敗或者 tablet server 彙報失去鎖，則master會擷取這個server對應鎖檔案的排它鎖

如果排它鎖能成功擷取，那麼可以确定 Chubby 時存活的，則是tablet server 發生異常。随後master确認 tablet server 不再提供服務，并會删掉它的 server file，并将其上的 tablet 标記為未配置設定（unassigned）

此外，為了保證系統不會因為 master 與 Chubby 之間的網絡問題存在異常而影響，master 的鎖丢失的時候，會kill 自身。

【master的啟動流程（探測tablet并配置設定）】

 Master 啟動後，首先探測 tablet 的分布情況：

1. 搶占鎖：在 Chubby上 搶占唯一的 master 鎖
2. 擷取存活的tablet server：Scan server directory，确定存活的 tablet server
3. 确定 tablet 配置設定情況：和 tablet server互動，确定 tablet 的配置設定情況
4. 确定tablet資訊：Scan METADATA 表，了解 tablet 資訊。并和 step3 中的tablet資訊對比，對未配置設定的 tablet 重配置設定

這裡還需要保證 scan METADATA表前，所有的 METADATA tablet都已經被配置設定了。為了解決這個問題，如果在 步驟3 中發現 root tablet 未配置設定，那麼會将其直接添加到未配置設定清單，來保證 root tablet 将被配置設定。這樣 master 就可以每個 METADATA tablet 資訊

【tablet 集合變化的場景】

Tablet 集合發生變化有如下場景：tablet被建立或者删除、tablet merge、tablet split

除了 split 外，其他的場景都是由 master 來出發完成的，是以master可以跟蹤到這些變化。

Tablet split 被特殊對待，因為它是由 tablet server 觸發完成的。Tablet server通過将split 資訊 送出給METADATA表的方式來完成送出，當 split 送出以後，tablet server會通知master。

如果通知master失敗了，那master會在下次配置設定這個tablet的時候感覺這次split。

===== 5.3 Tablet Serving

tablet的持久化狀态存儲在 GFS 中，如圖5展示

持久化的存儲包括commit log & SSTable。最近的寫操作被存儲在記憶體的一個有序結構中，稱為 memtable；老的寫入操作存儲在 SSTable 中。

【Recover tablet的方式】從 METADATA表中讀取 tablet 的metadata資訊（包括SSTable & redo point資訊），随後加載 SSTable 到記憶體并重放 redo log 來重構 memtable。

【寫操作流程】1. 确認其格式符合預期，并且具有相關權限；2. 将請求寫入 commit log（采用 group commit 的方式 [13, 16] ）；3. commit的write，寫入 memtable

【讀操作流程】1. 同樣确認格式和權限；2. 将 SSTable & memtable中的資料merge到一起，傳回結果（資料按照字典序排列，是以合并相對高效）

===== 5.4 Compactions

【minor compaction】

随着資料的不斷寫入，memtable持續增長。memtable大小增長到門檻值時，該memtable會被frozen，并建立一個新的memtable接收寫入，随後frozen的memtable被flush到磁盤，這個過程叫做 minor compaction

Minor compaction有2個目的：1. 減少記憶體使用；2. 降低recover時需要從 commit log中讀取的資料

【merging compaction】

minor compaction會不斷建立新的 SSTable，為了避免讀操作從多個SSTable中合并update，我們還會限制SSTable的數量，會定期将部分SSTable和memtable合并，生成新的SSTable，這個過程稱為 merging compaction

【major compaction】

如果merging compaction時讀取所有的SSTable，并重寫到一個SSTable中，那麼這個過程稱為 major compaction

非 major compaction會保留在 old SSTable 中仍然活躍的被删除資料，而 major compaction不會。Major compaction可以回收被删除資料占用的資源，確定被删除資料在系統中及時消失

===== 6. Refinements

===== 6.1 Locality groups

client可以将多個 column family 組合在一起稱為 locality group。同 locality group 的資料存放在一起，這樣可以避免查詢部分資料而需要讀取整行的開銷

此外，一些可調的參數可以獨立作用于 locality group 級别。比如指定某個 locality group 的資料 in-memory

===== 6.2 Compression

Client 可以控制 locality group 的 SSTable 是否進行壓縮以及壓縮方式。使用者指定的壓縮方式會應用到每一個 SSTable block

許多使用者會使用 two-pass（兩遍）自定義壓縮方式：第一遍使用 Bentley & MeIlroy [6]；第二遍會使用一個快速的壓縮算法

盡管對于壓縮算法，我們更關注速度而不是空間壓縮，但是這種 two-pass 壓縮方案效果出奇的好。對網頁content的場景，這種壓縮算法可以達到10:1的壓縮率，而Gzip隻有3:1/4:1

===== 6.3 Caching for read performance

為了提升讀性能，tablet server使用兩級cache：

• Scan Cache 是 high-level cache，緩存SSTable傳回給 tablet server的kv對，便于application重複讀取相同的資料
• Block Cache 是 low-level cache，緩存GFS中的SSTable block，便于application 讀取最近讀取過的相鄰資料

===== 6.4 Bloom filters

如5.3中提到，一個 read 操作需要讀取所有的SSTable 來建構 tablet 的狀态，這可能需要多次磁盤通路。

為了降低磁盤通路次數，我們允許 client 對特定的 locality group 的 SSTable 來建立 Bloom filter [7] ，來友善确認某個 SSTable 中是否存在指定的 row-column 對

這也意味着不存在的 row or column 的通路不需要讀取磁盤

===== 6.5 Commit-log implementation

如果我們為每一個 tablet 都維護單獨的 commit log，會導緻：

• 并發寫入導緻大量的随機寫（disk seek）
• 無法利用 group commit 優化

為了解決這個問題，我們為每個 tablet server 維護一個 commit log，在同一個實體檔案上混合多個tablet的變更 [18, 20]。

使用一個 log 可以提升普通操作的性能，但是 recovery tablet 邏輯會變得複雜。

recover 一個 tablet，新的 tablet server 需要 reapply這個tablet的修改，這就需要并行讀取commit log：每個 tablet server 都需要讀取所有的commit log，并應用所需的部分。

為了避免這個問題，我們首先将commit log中的entry 按照<table, row name, log sequence number>來進行排序。這樣每個tablet的修改都是有序的，可以通過一次disk seek + sequential read來完成。

為了提高 sort 的效率，我們将 log file 拆分成 64MB 的segment，并并發的在多個 tablet server上進行sort，這個 sort 的流程由 master 來協調完成。

Commit log 寫入 GFS 又是會遇到一些性能問題，為了規避這些問題，每個 tablet server 有 2 個commit log寫入線程，同一時間隻有一個線程活躍，當活躍線程寫入變慢的時候，會切換到另外一個線程繼續寫入。 // 這裡并不能解決 GFS 本身慢的問題吧

===== 6.6 Speeding up tablet recovery

Tablet move的過程中為了降低從 commit log 中恢複的時間會進行2次 minor compaction：第一次 compaction 将記憶體态的資料 flush 到磁盤以後，tablet server 會停止對這個 tablet服務。随後在此進行 minor compaction（通常很快），來将第一次compaction後的資料再次 flush 到磁盤

===== 6.7 Exploiting immutability

除了 SSTable cache 外，其他的很多系統也因為 SSTable 的不變性而簡化：

• 比如：不需要通路檔案系統就可以讀取SSTable，這樣并發控制可以很簡單的實作
• 因為不變性，清理已被删除的資料就變成了過期 SSTable GC問題，master 将過期的 SSTable 标記為 mark-and-sweep gc [25]
• Tablet 的 split 也變得高效，不需要生成新的SSTable，而讓子 tablet 共用 parent 的 SSTable

唯一讀寫都需要通路的可變資料結構是memtable，這裡采用 COW 的方式來降低讀沖突，同時也允許讀寫并發通路。

===== 7-9 略

===== 10 Related Work

V.s. Boxwood project [24]

Boxwood項目和Bigtable的功能重疊，但是其元件提供的都是相對low-leve的服務，項目的總體目标是為了提供進階服務的基礎設施

WAN Service problem

最近許多項目解決了提供分布式存儲是遇到的廣域網問題，這些系統解決的都是 Bigtable 不會出現的問題，例如去中心化控制、拜占庭問題、不可控帶寬等

Data model

KV模型使用 B-tree 或者 hash 表示太局限了，KV是有效的建構塊，但不應該是唯一的建構塊，是以我們提供比 KV 複雜的模型，同時支援稀疏半結構化資料

一些資料庫提供商開發可以存儲大量資料的并行資料庫，比如 Oracle Real Application [27]，DB2 Parallel Edition [4]，他們提供了完整的關系模型及事務支援

Bigtable locality group實作了與其他系統類似的壓縮 & 磁盤讀取性能優勢，而這些系統都是基于列組織的資料

V.s. C-store

C-Store 和 Bigtable 有許多相似的特性，但是 C-store 提供關系接口，是一個讀優化的關系資料庫；而 Bigtable 提供低級别的讀寫接口，提供良好的讀寫性能

Bigtable 的 load balancer 必須解決一些 share-nothing結構面臨的負載和記憶體均衡問題，但是我們的問題相對簡單：

• 不需要考慮資料的多副本問題，可能由view或者索引替代
• 讓使用者來決定資料在記憶體還是磁盤
• 沒有複雜的query 需要執行或者優化