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