1
Bigtable簡介
Bigtable是谷歌在其分布式文件系統(tǒng)GFS上設(shè)計(jì)的一個用于解決GFS無法對結(jié)構(gòu)化數(shù)據(jù)進(jìn)行訪問與管理的結(jié)構(gòu)化數(shù)據(jù)存儲訪問管理系統(tǒng)?；贖DFS的Apache HBase就是它的一個開源實(shí)現(xiàn)版本。作為 Google 的大數(shù)據(jù)三架馬車之一，Bigtable 依托于 Google 的 GFS、Chubby 及 SSTable 而誕生，谷歌將許多自己提供服務(wù)的數(shù)據(jù)使用Bigtable進(jìn)行管理，例如Google Earth、Google Finance、Gmail等等。所以Bigtable不僅需要應(yīng)對種類繁多的數(shù)據(jù)，在處理后端容量巨大的同時(shí)，還要保證對延遲敏感任務(wù)數(shù)據(jù)服務(wù)的及時(shí)性。同時(shí)由于谷歌眾多的服務(wù)都由Bigtable提供支持，在系統(tǒng)設(shè)計(jì)中，除了上述的高適用性外，更要考慮系統(tǒng)設(shè)計(jì)的高容錯性、高可用性以及可擴(kuò)展性。
2
數(shù)據(jù)模型
首先要說明Bigtable中數(shù)據(jù)是以什么形式存儲的。在Bigtable中，為了數(shù)據(jù)的高效管理與使用，數(shù)據(jù)被設(shè)計(jì)通過三個層次進(jìn)行索引，它們分別是：
· 行 (rows)
行標(biāo)識可以有任意不超過64KB的字符串組成，任何在同一行內(nèi)的讀或者寫操作都具有原子性。在維護(hù)數(shù)據(jù)表的過程中，數(shù)據(jù)按照行關(guān)鍵字進(jìn)行字典序劃分，同時(shí)，根據(jù)行關(guān)鍵字還可以將數(shù)據(jù)動態(tài)地劃分為一個個稱作“子表” (Tablet) 的區(qū)間，存儲在不同的子表服務(wù)器上做負(fù)載均衡。一般來說字典序相接近的兩個行關(guān)鍵字下數(shù)據(jù)被劃分在同一個子表服務(wù)器的概率較大，存取的效率也更高。
· 列族 (column families)
實(shí)際的數(shù)據(jù)表中，通常擁有較多的列，但是傳統(tǒng)關(guān)系型數(shù)據(jù)庫中按列為粒度進(jìn)行權(quán)限管理，給數(shù)據(jù)管理帶來了很大的難度。Bigtable將數(shù)據(jù)表中的列先劃分為不同的列族，在列族中還可以再定義相應(yīng)的列關(guān)鍵字，組成形如family:qualifier的列關(guān)鍵字，來存儲一些相似的數(shù)據(jù)。列族的設(shè)計(jì)目的是在能夠容納同樣數(shù)量的列數(shù)的同時(shí)，將相同類型的列聚集為一個族來統(tǒng)一管理，甚至可以統(tǒng)一進(jìn)行數(shù)據(jù)壓縮，方便了數(shù)據(jù)管理，也提高了數(shù)據(jù)存儲的靈活度。
· 時(shí)間戳 (timestamps)
數(shù)據(jù)表中的數(shù)據(jù)通常有版本上的更替，為了防止版本間的沖突，Bigtable設(shè)計(jì)了時(shí)間戳維度，同行同列的數(shù)據(jù)按照時(shí)間關(guān)系被賦予一個時(shí)間戳，時(shí)間戳既可以由客戶機(jī)應(yīng)用程序自行設(shè)置，也可以由時(shí)間的毫秒數(shù)來決定以64位整數(shù)形式存儲，并且時(shí)間戳按照降序排列，方便獲取最新的一個版本。Bigtable支持兩種自動回收舊版本的機(jī)制，一是保留最新的幾個版本，另一種策略是僅保留一定時(shí)間內(nèi)的所有版本。
所以，Bigtable中的每一個數(shù)據(jù)單元格式如下：
(row:string, coloum:string, time:int64) -> string
文中舉了一個例子如圖1所示，這是一個網(wǎng)頁數(shù)據(jù)表，row值中存儲著所記錄網(wǎng)頁的倒敘URL，即“com.cnn.www”。倒敘存放可以使同一個域名下的不同頁面根據(jù)字典序存放在一起。“content:”是一個列族，但這個列族中沒有其他的qulifier，下面存放著網(wǎng)頁html的內(nèi)容，這里的內(nèi)容一共有三個版本，按時(shí)間順序的時(shí)間戳為t3, t5, t6。“anchor：”為第二個列族，這個列族中有兩個不同的column keys，分別是“cnnsi.com”和“my.look.ca”，記錄著所有連接到row值存儲頁面的所有頁面，而對應(yīng)列下存儲的就是這些頁面中連接到row頁面的anchor。
3
系統(tǒng)組成
本章將會介紹Bigtable系統(tǒng)中的幾個關(guān)鍵組成部分或者支撐技術(shù)。
· 主服務(wù)器 (master)
主服務(wù)器上不存儲子表，也不是用來提供表定位信息的，而是主要負(fù)責(zé)子表服務(wù)器 的分配、負(fù)載均衡，監(jiān)控子表服務(wù)器的狀態(tài)，當(dāng)子表服務(wù)器的租約到后仍然沒有回應(yīng)則要重新安排新的子表服務(wù)器來代替，同時(shí)當(dāng)子表服務(wù)器的所存的子表過大的時(shí)候還要分配新的子表服務(wù)器進(jìn)行負(fù)載均衡。同時(shí)，主服務(wù)器還要負(fù)責(zé)處理表模式更改、列族增加和GFS上垃圾回收等任務(wù)。
· 子表服務(wù)器(tablet server)
Bigtable在存儲表的時(shí)候會將表劃分為一個個子表來進(jìn)行存儲。子表服務(wù)器上存儲著子表信息，由于為了減小主服務(wù)器的負(fù)載，數(shù)據(jù)請求不會經(jīng)過主服務(wù)器，子表服務(wù)器還需要直接響應(yīng)客戶機(jī)對字表服務(wù)器上存儲的子表的讀和寫操作。在所存儲的子表過大的時(shí)候需要對子表進(jìn)行切分操作。需要注意的是，子表服務(wù)器也不是直接存放數(shù)據(jù)的，數(shù)據(jù)只是存放在GFS中，然后由子服務(wù)器來進(jìn)行分片管理。
· 客戶端的庫
客戶端的庫用于緩存子表的位置，只有當(dāng)沒有緩存子表的位置或子表的位置出錯的情況下，客戶機(jī)才會啟動子表定位。
· GFS Bigtable
底層所使用的分布式文件系統(tǒng) (Google File System)，存放著數(shù)據(jù)文件和日志文件。
· SSTable Bigtable
內(nèi)部使用的文件格式，提供不變有序的鍵值映射，鍵與值都是用任意的字節(jié)串組成的。SSTable內(nèi)部包含一系列默認(rèn)大小為64KB的塊 (block)，并將這些塊的索引值存放在文件末尾。每一個子表可能對應(yīng)著多個SSTable文件。
· Chubby Chubby
是Google設(shè)計(jì)的一個鎖服務(wù)，每個Chubby服務(wù)都利用Paxos算法保留了5個副本，其中一個作為主副本提供服務(wù)。Chubby提供了一系列的目錄與文件，每個目錄與文件都被當(dāng)成“鎖”來使用以保證，使用Chubby服務(wù)的客戶機(jī)需要保持和Chubby服務(wù)之間的會話，并維護(hù)一個租期的關(guān)系，超出租期如果Chubby沒有收到客戶機(jī)的續(xù)約申請，那么客戶機(jī)就會失去在Chubby服務(wù)中的所有鎖。Chubby在Bigtable中有非常重要的作用，以至于一旦Chubby服務(wù)失效，整個Bigtable就無法工作。無論是在主服務(wù)器的確定、子表服務(wù)器定位、子表服務(wù)器分配、表的權(quán)限控制等等方面都運(yùn)用到了Chubby服務(wù)。這些運(yùn)用將會在后面的章節(jié)中提到。
子表操作
本章將會介紹子表的定位、子表分配以及子表的讀寫操作。
1. 子表定位
Bigtable將子表按照三層關(guān)系進(jìn)行組織，三層關(guān)系如圖1所示：
第一層，存儲在Chubby file中，里面包含了Root tablet的位置信息。
第二層，根子表 (Root tablet) ，元數(shù)據(jù)子表 (METADATA tablets) 中的第一個子表，它存儲著元數(shù)據(jù)表里其他子表的位置信息，根子表隨著大小的增長是不會被分割的。
第三層，原數(shù)據(jù)子表 (METADATA tablets) ，保存其他用戶數(shù)據(jù)表的子表信息。
在查找子表的時(shí)候，客戶機(jī)首先會檢查自己的庫，看是否已經(jīng)有這個子表位置的緩存，如果存在這個緩存且這個緩存還有效，就會按照這個位置去獲取子表信息。如果這個子表的緩存信息錯誤，那么客戶機(jī)將會遞歸向上一層的子表服務(wù)器進(jìn)行查詢。若緩存為空，則客戶機(jī)將會從Chubby file開始獲取根子表的位置，查詢根子表查尋相應(yīng)元數(shù)據(jù)子表的位置，再在元數(shù)據(jù)字表中找到需要的數(shù)據(jù)子表的位置，完成完整的一次詢問的查找。
2. 子表分配
前文中有提到主服務(wù)器master主要負(fù)責(zé)監(jiān)控子表服務(wù)器狀態(tài)以及子表的分配。主服務(wù)器需要通過Chubby確認(rèn)每個子表服務(wù)器是否還在正常工作，跟蹤子表都分配給了哪些子表服務(wù)器以及哪些子表還沒有被分配。
當(dāng)一個子表服務(wù)器啟動的時(shí)候，它會在Chubby特定的目錄下建立一個自己的文件并獲得互斥鎖，主服務(wù)器通過文件來監(jiān)控存在哪些子表服務(wù)器，通過周期性嘗試獲取這些文件的互斥鎖來確認(rèn)這些子表服務(wù)器是否還在正常工作。當(dāng)子表服務(wù)器失去與Chubby的連接后，就會失去這個互斥鎖。但是只要子表服務(wù)器上的數(shù)據(jù)還存在并且Chubby相應(yīng)文件還存在，它還會不斷試圖請求會這個互斥鎖。一旦主服務(wù)器獲得了這個互斥鎖，它就會刪除這個文件，導(dǎo)致子表服務(wù)器的最終停止。而子表服務(wù)器主動停止服務(wù)的時(shí)候，也會釋放這個互斥鎖，以便主服務(wù)器更快意識到這個子表服務(wù)器的退出。
當(dāng)主服務(wù)器和Chubby連接被斷開后，當(dāng)前的主服務(wù)器會主動關(guān)閉自己，這時(shí)候系統(tǒng)就會重新選擇一個新的主服務(wù)器出來。主服務(wù)器啟動時(shí)，會首先獲取一個Chubby上的master鎖以防止其他服務(wù)器同時(shí)成為主服務(wù)器；然后新主服務(wù)器會掃描Chubby的特定目錄嘗試獲取互斥鎖來獲得當(dāng)前正在工作的子表服務(wù)器；之后再詢問每個子表服務(wù)器被分配的子表；最后再統(tǒng)計(jì)METADATA子表中還未被分配的子表，準(zhǔn)備將其分配 (若元數(shù)據(jù)子表還未被分配，則需先將根子表加入到待分配的子表集合中) 。
3. 子表的讀寫操作
讀寫操作的基本示意圖如圖3所示。其中SSTable Files是已經(jīng)持久化在GFS中的數(shù)據(jù)，memtable是還未存入SSTable Files的數(shù)據(jù)緩存，tablet log是寫操作的日志，用于子表服務(wù)器啟動時(shí)從重做點(diǎn)開始恢復(fù)子表。
讀操作首先要經(jīng)過權(quán)限的驗(yàn)證，通過驗(yàn)證后，由于數(shù)據(jù)的不同版本分布在位于內(nèi)存的memtable中以及位于GFS的SSTable Files中，所以需要事先進(jìn)行合并。
寫操作也類似，首先要經(jīng)過權(quán)限驗(yàn)證，然后使用日志先行 (WAL) 的方式先提交到日志中，然后再把變更插入到memtable中。
4. 子表壓縮
每當(dāng)進(jìn)行一次寫操作，新寫的記錄不會覆蓋原有記錄，而是被添加到memtable后面，當(dāng)memtable的大小達(dá)到一定程度的時(shí)候，就要用新的一個memtable來代替原來的memtable并把原來的table保存為一個SSTable文件。這個操作過程叫作minor compaction。
但是minor compaction會逐漸增加SSTable的數(shù)量，會影響文件維護(hù)的效率。因此需要周期性的對SSTable文件和memtable進(jìn)行合并，這個操作叫作merging compaction。
還有一種特殊的merging compaction叫作major compaction。這種compaction會把所有的SSTable和memtable都merge到一個單獨(dú)的SSTable中，并且與前兩種方法不同的是，major compaction將會刪除掉那些已經(jīng)無效的數(shù)據(jù)，節(jié)省集群空間，釋放資源以適應(yīng)巨大的容量需求。
5
總結(jié)
這篇文章介紹了谷歌在GFS上搭建的結(jié)構(gòu)化數(shù)據(jù)表存儲系統(tǒng)Bigtable，首先在其使用的數(shù)據(jù)模型、系統(tǒng)組成方面進(jìn)行的簡單的介紹，然后分別詳細(xì)討論了在Bigtable上如何進(jìn)行數(shù)據(jù)定位、數(shù)據(jù)分配以及數(shù)據(jù)讀寫操作。討論了主服務(wù)器如何產(chǎn)生，當(dāng)主服務(wù)器以及子表服務(wù)器出現(xiàn)問題后應(yīng)該如何將正在管理數(shù)據(jù)移交出去，新啟動的服務(wù)器應(yīng)當(dāng)如何加入到系統(tǒng)中并獲得數(shù)據(jù)。還提到了Bigtable底層如何維護(hù)與壓縮保存的數(shù)據(jù)文件等等。Bigtable 論文中的以下兩點(diǎn)是最有啟發(fā)性的：
· 利用 Chubby 分布式鎖服務(wù)實(shí)現(xiàn)節(jié)點(diǎn)間的協(xié)調(diào)
· 利用 LSM Tree 將數(shù)據(jù)庫的隨機(jī)寫入操作轉(zhuǎn)化為順序?qū)懭耄M(jìn)而利用 GFS 提供數(shù)據(jù)冗余類似 Chubby 的服務(wù)在開源界已經(jīng)有很多了，無論是倍受其影響的 ZooKeeper 還是后來出現(xiàn)的 etcd，現(xiàn)在大家對于如何使用這類服務(wù)都有了很好的認(rèn)識。
