BigTable

為解決海量數據存儲的問題，Google的軟件開發工程師研發了Bigtable，並於2005年4月投入使用 ^[3]  。Google在2006年的OSDI大會上發表了關於Bigtable分佈式數據庫的論文 ^[1]  。

Bigtable為Google60多種產品和項目提供存儲和獲取結構化數據的支撐平台，其中包括有Google Print、Orkut、Google Maps和Blogger等，而且在Google內部至少運行着500個Bigtable集羣 ^[3]  。

Bigtable是一個稀疏、分佈式、持久化存儲的多維有序映射表，表的索引是行關鍵字、列關鍵字和時間戳 ^[1]  。Bigtable中存儲的表項都是未經解析的字節數組，其數據模型如下 ^[1]  ：

選定該數據模型，是在仔細分析了Bigtable系統的種種用途之後決定的 ^[1]  。比如一個存儲了大量網頁及其相關信息的表Webtable，Webtable使用URL作為行關鍵字，使用網頁的某些屬性作為列名，網頁的內容存入contents列中，並使用獲取該網頁的時間戳標識同一個網頁的不同版本 ^[1]  。在Bigtable中，Webtable的存儲範例如圖《Webtable範例片段》所示 ^[1]  。

行關鍵字可以是任意字符串，最大支持64KB ^[1]  。Bigtable按照行關鍵字的字典序組織數據，利用這個特性可以通過選擇合適的行關鍵字，使數據訪問具有良好的局部性 ^[1]  。如Webtable中，通過將反轉的URL作為行關鍵字，可以將同一個域名下的網頁聚集在一起 ^[1]  。表的行區間可以動態劃分，每個行區間稱為一個子表 ^[1]  。子表是Bigtable數據分佈和負載均衡的基本單位，不同的子表可以有不同的大小 ^[1]  。為了限制子表的移動和恢復成本，每個子表默認的最大尺寸為200MB ^[1]  。

列關鍵字一般都表示一種數據類型，列關鍵字的集合稱作列族，列族是訪問控制的基本單位 ^[1]  。存儲在同一列族下的數據屬於同一種類型，列族下的數據被壓縮在一起保存 ^[1]  。數據在被存儲之前必須先創建列族，並且表中的列族不宜過多，通常幾百個，但表中可以有無限多個列 ^[1]  。在Bigtable中列關鍵字的命名語法為：“列族：限定詞”，列族名稱必須是可打印的字符串，限定詞則可以是任意字符串 ^[1]  。如Webtable中名為anchor的列族，該列族的每一個列關鍵字代表一個錨鏈接；anchor列族的限定詞是引用網頁的站點名，每列的數據項是鏈接文本 ^[1]  。

Bigtable中的表項可以包含同一數據的不同版本，採用時間戳進行索引 ^[1]  。時間戳是64位整型，既可以由系統賦值也可由用户指定。表項的不同版本按照時間戳倒序排列，即最新的數據排在最前面 ^[1]  。為了簡化多版本數據的管理，每個列族都有兩個設置參數用於版本的自動回收，用户可以指定保存最近N個版本，或保留足夠新的版本(如最近7天的內容) ^[1]  。在Webtable的例子中，contents列族存儲的時間戳是網絡爬蟲抓取頁面的時間，表中的回收機制是保留任一頁面的最近三個版本 ^[1]  。

下面用JSON的數據格式展示了Bigtable的數據模型 ^[3]  。

如圖《Bigtable數據模型》所示，表的名稱是“tableName”，行的名稱是“rowA” ^[3]  。“rowA”有兩個列族分別為“ColumnFamilyA”和“ColumnFamilyB” ^[3]  。每個列族又可以同時擁有多個列，每列都有自己唯一的列標示符 ^[3]  。例如，在列族“ColumnFamilyA”中有兩列，分別為“IdentifierA”和“IdentifierB” ^[3]  。

值得注意的是Bigtable允許空值作為列的標示符 ^[3]  。例如，在列族“ColumnFamilyB”中有一個空值的列標示符 ^[3]  。

Bigtable可以同時存儲多個版本的數據，每個版本的數據都有自己唯一的時間戳，而且不同版本的數據是按照時間戳遞減的順序排列的 ^[3]  。

Bigtable系統實現了數據的分佈式管理和結構的組織 ^[4]  。Bigtable包含了3個主要的組件：鏈接到每個客户的庫，一個Master服務器和多個Tablet服務器。根據負載情況的變化，Bigtable可以動態的向集羣中添加或者刪除Tablet服務器 ^[2]  。

Master的主要任務是向Tablet服務器分配Tablet，檢測是否有新加入或者失效的Tablet服務器，對Tablet-server進行負載均衡，以及對GFS上文件進行垃圾收集 ^[2]  。除此之外，它還可以進行模式修改，例如表和列族的建立 ^[2]  。

每個Tablet服務器都管理了一系列的Tablet ^[2]  。每個Tablet服務器處理它自身上面的Tablet的讀寫請求，並且當其上面的Tablets增長到一定程度對過大的Tablets進行分割 ^[2]  。

和很多的單一Master分佈式存儲系統類似，客户端讀取的數據不經過Master，客户直接和Tablet服務器通信進行讀寫操作 ^[2]  。

Bigtable依賴一個高可用和持續分佈式鎖服務器Chubby進行管理 ^[2]  。Chubby提供了一個名字空間，裏面包含了目錄和小文件 ^[2]  。每個目錄或者文件可以當成是一個鎖，讀寫文件的操作都是原子的 ^[2]  。每個Chubby的客户程序都維護一個與Chubby服務的會話 ^[2]  。

Bigtable使用Google的分佈式文件系統（GFS）存儲日誌文件和數據文件 ^[2]  。Bigtable集羣通常運行在一個共享的機器池裏，Bigtable依賴集羣管理系統調度任務、管理共享機器上的資源、處理機器的故障以及監視機器的狀態 ^[2]  。

下表從不同方面對Bigtable和傳統並行分佈式關係數據庫進行比較 ^[2]  。

HBase是Apache下Hadoop的存儲系統，是一個高可靠性、高性能、面向列、可伸縮的分佈式存儲系統 ^[1]  。HBase在Hadoop之上提供了Bigtable的功能，HBase已經成為Apache開源項目的一個頂級項目 ^[1]  。

Hypertable是Bigtable的開源實現，由Zvents公司使用Boost C++進行開發，並於2008年3月公佈其源碼 ^[1]  。Hypertable是一個稀疏、分佈式、高性能的多維有序映射表，用於處理海量結構化和半結構化數據 ^[1]  。Hypertable可以讓用户通過主鍵來組織海量數據，併為用户提供了數據查詢語言HQL以實現高效查詢 ^[1]  。