Bigtable為Google設計的一個分布式結構化資料存儲系統，用來處理Google的海量資料。Google内包括Web索引、Google地球等項目都在使用Bigtable存儲資料。盡管這些應用需求差異很大，但是Bigtable還是提供了一個靈活的、高性能的解決方案。
-----------------------------------------------------------------------------------------------------------------------------------
一、簡介
* 設計目标：可靠的處理PB級别的資料，适用性廣泛、可擴充、高性能和高可用性。
* 很多方面Bigtable和資料庫類似，其也使用了資料庫很多實作政策，但是Bigtable提供了和這些系統完全不同的接口。Bigtable不支援完整的關系資料模型，但為使用者提供了一種簡單的資料模型，使用者可以動态控制資料的分布和格式
二、資料模型
* Bigtable是一個稀疏的、分布式的、持久化存儲的多元排序Map（Key=>Value）。Map的索引（Key）是行關鍵字、列關鍵字和時間戳，Map的值（Value）都是未解析的Byte數組：
- Key (row:string, col:string, time:int64) => Value (string)
* 下圖是Bigtable存儲網頁資訊的一個例子：
- 行："com.cn.www"為網頁的URL
- 列："contents:"為網頁的文檔内容，"anchor:"為網頁的錨連結文本（anchor:為列族，包含2列cnnsi.com和my.look.ca）
- 時間戳：t3、t5、t6、t8和t9均為時間戳
1、行
* 行和列關鍵字都為字元串類型，目前支援最大64KB，但一般10~100個位元組就足夠了
* 對同一個行關鍵字的讀寫操作都是原子的，這裡類似Mysql的行鎖，鎖粒度并沒有達到列級别
* Bigtable通過行關鍵字的字典序來組織資料，表中每行都可以動态分區。每個分區叫做一個"Tablet"，故Tablet是資料分布和負載均衡調整的最小機關。這樣做的好處是讀取行中很少幾列資料的效率很高，而且可以有效的利用資料的位置相關性（局部性原理）
2、列族
* 列關鍵字組成的集合叫做"列族"，列族是通路控制的基本機關，存放在同一列族的資料通常都屬于同一類型。
* 一張表列族不能太多（最多幾百個），且很少改變，但列卻可以有無限多
* 列關鍵字的命名文法：列族:限定詞。
* 通路控制、磁盤和記憶體的使用統計都是在列族層面進行的
3、時間戳
* 在Bigtable中，表的每個資料項都可包含同一資料的不同版本，不同版本通過時間戳來索引（64位整型，可精确到毫秒）
* 為了減輕各版本資料的管理負擔，每個列族有2個設定參數，可通過這2個參數可以對廢棄版本資料進行自動垃圾收集，使用者可以指定隻儲存最後n個版本資料
三、API
* 在表操作方面，提供建表、删表、建列族、删列族，以及修改叢集、表和列族中繼資料（如通路權限等）等基本API。一個例子：
* 在資料操作方面，提供寫入、删除、讀取、周遊等基礎API。一個例子：
* 根據具體需求，Bigtable還開發出支援一些其他的特性，比如：1 支援單行上的事務處理，2 允許把資料項做整數計數器 3 允許使用者在Bigtable伺服器位址空間上執行腳本程式
四、基礎構件
* Bigtable是建立在其他幾個Google基礎構件上的，有GFS、SSTable、Chubby等
1、基礎存儲相關
* Bigtable使用GFS存儲日志檔案和資料檔案，叢集通常運作在共享機器池（cloud）中，依靠叢集管理系統做任務排程、資源管理和機器監控等
2、資料檔案格式相關
* Bigtable的内部儲存檔案為Google SSTable格式的，SSTable是一個持久化、排序的、不可更改的Map結構
* 從内部看，SSTable是一系列的資料塊，并通過塊索引定位，塊索引在打開SSTable時加載到記憶體中，用于快速查找到指定的資料塊
3、分布式同步相關
* Bigtable還依賴一個高可用的、序列化的分布式鎖服務元件Chubby（類zookeeper）。
* Chubby服務維護5個活動副本，其中一個選為Master并處理請求，并通過Paxos算法來保證副本一緻性。另外Chubby提供一個名字空間，提供對Chubby檔案的一緻性緩存等
* Bigtable使用Chubby來完成幾個任務，比如：1 確定任意時間隻有一個活動Master副本，2 存儲資料的自引導指令位置，3 查找Tablet伺服器資訊等 4 存儲通路控制清單等
五、實作
* Bigtable包括3個主要的元件：連結到使用者程式的庫，1個Master伺服器和多個Tablet伺服器。Tablet伺服器可根據工作負載動态增減
* Master伺服器：為Tablet伺服器配置設定Tablets，對Tablet伺服器進行負載均衡，檢測Tablet伺服器的增減等
* Tablet伺服器：管理一個Tablets集合（十到上千個Tablet），并負責它們的讀寫操作。與一般Single-Master類型的分布式存儲系統類似，用戶端可直接和Tablet伺服器通信并進行讀寫，故Master的負載并不大
* 初始情況下，每個表隻含一個Tablet，随着表資料的增長，它會被自動分割成多個Tablet，使得每個Table一般為100~200MB
1、Tablet的位置資訊
* 我們使用三層的、類B+樹的結構存儲Tablet的位置資訊，如下圖所示：
* 第一層為存儲于Chubby中的Root Tablet位置資訊。Root Tablet包含一個MetaData表，MetaData表每個Tablet包含一個使用者Tablet集合
* 在MetaData表内，每個Tablet的位置資訊都存儲在一個行關鍵字下，這個行關鍵字由Tablet所在表的辨別符和最後一行編碼而成
* MetaData表每一行都存儲約1KB記憶體資料，即在一個128MB的MetaData表中，采用這種3層存儲結構，可辨別2^32個Tablet位址
* 使用者程式使用的庫會緩存Tablet的位置資訊，如果某個Tablet位置資訊沒有緩存或緩存失效，那麼用戶端會在樹狀存儲結構中遞歸查詢。故通常會通過預取Tablet位址來減少通路開銷
2、Tablet的配置設定
* 在任何時刻，一個Tablet隻能配置設定給一個Tablet伺服器，這個由Master來控制配置設定（一個Tablet沒配置設定，而一個Tablet伺服器用足夠空閑空間，則Master會發給該Tablet伺服器裝載請求）
* Bigtable通過Chubby跟蹤Tablet伺服器的狀态。當Tablet伺服器啟動時，會在Chubby注冊檔案節點并獲得其獨占鎖，當Tablet伺服器失效或關閉時，會釋放這個獨占鎖
* 當Tablet伺服器不提供服務時，Master會通過輪詢Chubby上Tablet伺服器檔案鎖的狀态檢查出來，确認後會删除其在Chubby注冊的節點，使其不再提供服務。最後Master會重新配置設定這個Tablet伺服器上的Tablet到其他未配置設定的Tablet集合内
* 當叢集管理系統啟動一個Master伺服器之後，這個Master會執行以下步驟：
- 1 從Chubby擷取一個唯一的Master鎖，保證Chubby隻有一個Master執行個體
- 2 掃描Chubby上的Tablet檔案鎖目錄，擷取目前運作的Tablet伺服器清單
- 3 和所有Tablet伺服器通信，擷取每個Tablet伺服器上的Tablet配置設定資訊
- 4 掃描MetaData表擷取所有Tablet集合，如果發現有還沒配置設定的Tablet，就會将其加入未配置設定Tablet集合等待配置設定
3、Tablet的服務
* 如圖所示，Tablet的持久化狀态資訊儲存在GFS上。更新操作會送出Redo日志，更新操作分2類：
- 最近送出的更新操作會存放在一個排序緩存中，稱為memtable
- 較早送出的更新操作會存放在SSTable中，落地在GFS上
* Tablet的恢複：Tablet伺服器從MetaData中讀取這個Tablet的中繼資料，中繼資料裡面就包含了組成這個Tablet的SSTable和RedoPoint，然後通過重複RedoPoint之後的日志記錄來重建（類似Mysql的binlog）
* 對Tablet伺服器寫操作：首先檢查操作格式正确性和權限（從Chubby拉取權限清單）。之後有效的寫記錄會送出日志，也支援批量送出，最後寫入的内容插入memtable内
* 對Tablet伺服器讀操作：也首先檢查格式和權限，之後有效的讀操作在一系列SSTable和memtable合并的視圖内執行（都按字典序排序，可高效生成合并視圖）
4、Compactions
* 當memtable增大達到一個門限值時，這個memtable會轉換為SSTable并建立新的memtable，這個過程稱為Minor Compaction。
* Minor Compaction過程為了減少Tablet伺服器使用的記憶體，以及在災難恢複時減少從送出日志讀取的資料量
* 如果Minor Compaction過程不斷進行下去，SStable數量會過多而影響讀操作合并多個SSTable，是以Bigtable會定期合并SStable檔案來限制其數量，這個過程稱為Major Compaction。
* 除此之外，Major Compaction過程生産的新SStable不會包含已删除的資料，幫助Bigtable來回收已删除的資源
六、優化
1、局部性群族
* 使用者可将多個列族組合成一個局部性群族，Tablet中每個局部性群族都會生産一個SSTable，将通常不會一起通路的分割成不同局部性群族，可以提高讀取操作的效率
* 此外，可以局部性群族為機關專門設定一些調優參數，如是否存儲于記憶體等
2、壓縮
* 使用者可以控制一個局部性群族的SSTable是否壓縮
* 很多使用者使用”兩遍可定制“的壓縮方式：第一遍采用Bentley and Mcllroy（大掃描視窗内常見長字元串壓縮），第二遍采用快速壓縮算法（小掃描視窗内重複資料），這種方式壓縮速度達到100~200MB/s，解壓速度達到400~1000MB/s，空間壓縮比達到10:1
3、緩存
* Tablet伺服器使用二級緩存政策來提高讀操作性能。兩級的緩存針對性不同：
* 第一級緩存為掃描緩存：緩存Tablet伺服器通過SSTable接口擷取的Key-Value對（時間局部性）
* 第二季緩存為塊緩存：緩存從GFS讀取的SSTable塊（空間局部性）
4、布隆過濾器
* 一個讀操作必須讀取構成Tablet狀态的所有SSTable資料，故如果這些SSTable不在記憶體便需多次通路磁盤
* 我們允許使用者使用一個Bloom過濾器來查詢SStable是否包含指定的行和列資料，付出少量Bloom過濾器記憶體存儲代價，換來顯著減少通路磁盤次數
5、Commit日志實作
* 如果每個Tablet操作的Commit日志單獨寫一個檔案，會導緻日志檔案數過多，寫入GFS會産生大量的磁盤Seek操作而産生負面影響
* 優化：設定為每個Tablet伺服器寫一個公共的日志檔案，裡面混合了各個Tablet的修改日志。
* 這個優化顯著提高普通操作性能，卻讓恢複工作複雜化。當一台Tablet伺服器挂了，需要将其上面的tablet均勻恢複到其他Tablet伺服器，則其他伺服器都得讀取完整的Commit日志。為了避免多次讀Commit日志，我們将日志按關鍵字排序(table, row, log_seq)，讓同一個Tablet的記錄檔連續存放
6、Tablet恢複提速
* Master轉移Tablet時，源Tablet伺服器會對這個Tablet做一次Minor Compaction，減少Tablet伺服器日志檔案沒有歸并的記錄，進而減少了恢複時間
7、利用不變性
* 在使用Bigtable時，除了SSTable緩存外其他部分産生的SSTable都是不變的，可以利用這個不變性對系統簡化
七、性能評估
* 實驗設計：N台Tablet伺服器叢集（N=1、50、250、500...），每台Tablet伺服器1G記憶體，資料寫入一個含1786台機器的GFS叢集。使用N台Client産生工作負載，這些機器都連入一個兩層樹狀網絡，根節點帶寬約100~200Gbps。
* 一共有6組基準測試：序列寫、随機寫、序列讀、随機讀、随機讀（記憶體）和掃描，測試結果如下圖所示：
測試均為讀/寫1000位元組value的資料，圖1顯示了1/50/250/500台Tablet伺服器，每台伺服器的每秒操作次數，圖2曲線顯示随着Tablet伺服器數量增加，所有伺服器的每秒操作次數總和
* 對于圖1單個Tablet伺服器性能次元，有下面幾個特點：
- 随機讀性能最慢，這是因為每個随機讀操作都要通過網絡從GFS叢集拉回64KB（1塊）資料到Tablet伺服器
- 随機讀（記憶體）性能很快，因為這些讀操作的資料都從Tablet伺服器的記憶體讀取
- 序列讀性能好于随機讀，因為每次從GFS取出64KB資料，這些資料會緩存，序列讀很多落到同個塊上而減少GFS讀取次數
- 寫操作比讀操作高，因為寫操作實質上為Tablet伺服器直接把寫入内容追加到Commit日志檔案尾部（随機寫和序列寫性能相近的原因），最後再采用批量送出的方式寫入GFS
- 掃描的性能最高，因為Client的每一次RPC調用都會傳回大量value資料，抵消了RPC調用消耗
* 對于圖2Tablet伺服器叢集性能次元，有下面幾個特點：
- 随着Tablet伺服器的增加，系統整體吞吐量有了夢幻般的增加，之是以會有這樣的性能提升，主要是因為基準測試的瓶頸是單台Tablet伺服器的CPU
- 盡管如此，性能的增加也不是線性的，這是由于多台Tablet伺服器間負載不均衡造成的
- 随機讀的性能提升最小，還是由于每個1000位元組value的讀操作都會導緻一個64KB塊的網絡傳輸，消耗了網絡的共享帶寬
八、實際應用
* 截止到2006年，Google内部一共運作了388個非測試的Bigtable叢集，約24500台Tablet伺服器，這些應用以及應用資料大緻如下：
* 如上圖所示，可以了解到Google分析，Google地圖，Google個性化查詢等應用的Bigtable使用情況
九、經驗教訓
* 很多類型的錯誤都會導緻大型分布式系統受損，而不僅僅是網絡中斷等“正常”錯誤。我們使用修改協定來解決這些問題（容錯性），如在RPC機制中加入Checksum等
* 需要在徹底了解一個新特性如何使用後，再決定添加這個新特性是否是重要的。
* 系統級的監控對Bigtable非常重要，能有效跟蹤叢集狀态、檢查引發叢集高時延的潛在因素等
* 簡單的設計和編碼給維護和調試帶來了巨大的好處