BigTable論文學習筆記
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非常重要，能有效跟蹤集群狀態、檢查引發集群高時延的潛在因素等
* 簡單的設計和編碼給維護和調試帶來了巨大的好處
來自：http://blog.csdn.net/yyyiran/article/details/12918921