云計(jì)算及應(yīng)用課件：分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

設(shè)計(jì)動(dòng)機(jī)與目標(biāo)

數(shù)據(jù)模型

系統(tǒng)架構(gòu)

主服務(wù)器

子表服務(wù)器

性能優(yōu)化設(shè)計(jì)動(dòng)機(jī)與目標(biāo)需要存儲(chǔ)的數(shù)據(jù)種類(lèi)繁多：Google目前向公眾開(kāi)放的服務(wù)很多，需要處理的數(shù)據(jù)類(lèi)型也非常多。包括URL、網(wǎng)頁(yè)內(nèi)容、用戶(hù)的個(gè)性化設(shè)置在內(nèi)的數(shù)據(jù)都是Google需要經(jīng)常處理的海量的服務(wù)請(qǐng)求：Google運(yùn)行著目前世界上最繁忙的系統(tǒng)，它每時(shí)每刻處理的客戶(hù)服務(wù)請(qǐng)求數(shù)量是普通的系統(tǒng)根本無(wú)法承受的商用數(shù)據(jù)庫(kù)無(wú)法滿(mǎn)足Google的需求：一方面現(xiàn)有商用數(shù)據(jù)庫(kù)設(shè)計(jì)著眼點(diǎn)在于通用性，根本無(wú)法滿(mǎn)足Google的苛刻服務(wù)要求；另一方面對(duì)于底層系統(tǒng)的完全掌控會(huì)給后期的系統(tǒng)維護(hù)、升級(jí)帶來(lái)極大的便利設(shè)計(jì)動(dòng)機(jī)設(shè)計(jì)動(dòng)機(jī)與目標(biāo)基本目標(biāo)高可用性

Bigtable設(shè)計(jì)的重要目標(biāo)之一就是確保幾乎所有的情況下系統(tǒng)都可用

廣泛的適用性

Bigtable是為了滿(mǎn)足系列Google產(chǎn)品而非特定產(chǎn)品存儲(chǔ)要求

簡(jiǎn)單性

底層系統(tǒng)簡(jiǎn)單性既可減少系統(tǒng)出錯(cuò)概率，也為上層應(yīng)用開(kāi)發(fā)帶來(lái)便利

很強(qiáng)的可擴(kuò)展性

根據(jù)需要隨時(shí)可以加入或撤銷(xiāo)服務(wù)器

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

設(shè)計(jì)動(dòng)機(jī)與目標(biāo)

數(shù)據(jù)模型

系統(tǒng)架構(gòu)

主服務(wù)器

子表服務(wù)器

性能優(yōu)化數(shù)據(jù)模型

Bigtable是一個(gè)分布式多維映射表，表中的數(shù)據(jù)通過(guò)一個(gè)行關(guān)鍵字（RowKey）、一個(gè)列關(guān)鍵字（ColumnKey）以及一個(gè)時(shí)間戳（TimeStamp）進(jìn)行索引

Bigtable對(duì)存儲(chǔ)在其中的數(shù)據(jù)不做任何解析，一律看做字符串

Bigtable的存儲(chǔ)邏輯可以表示為：

(row:string,column:string,time:int64)→stringBigtable數(shù)據(jù)模型數(shù)據(jù)模型行

Bigtable的行關(guān)鍵字可以是任意的字符串，但是大小不能超過(guò)64KB。Bigtable和傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)有很大不同，它不支持一般意義上的事務(wù)，但能保證對(duì)于行的讀寫(xiě)操作具有原子性（Atomic）

表中數(shù)據(jù)都是根據(jù)行關(guān)鍵字進(jìn)行排序的，排序使用的是詞典序。

一個(gè)典型實(shí)例，其中n.www就是一個(gè)行關(guān)鍵字。不直接存儲(chǔ)網(wǎng)頁(yè)地址而將其倒排是Bigtable的一個(gè)巧妙設(shè)計(jì)。這樣做至少會(huì)帶來(lái)以下兩個(gè)好處

同一地址域的網(wǎng)頁(yè)會(huì)被存儲(chǔ)在表中的連續(xù)位置，有利于用戶(hù)查找和分析

倒排便于數(shù)據(jù)壓縮，可以大幅提高壓縮率

數(shù)據(jù)模型列

Bigtable并不是簡(jiǎn)單地存儲(chǔ)所有的列關(guān)鍵字，而是將其組織成所謂的列族（ColumnFamily），每個(gè)族中的數(shù)據(jù)都屬于同一個(gè)類(lèi)型，并且同族的數(shù)據(jù)會(huì)被壓縮在一起保存。引入了列族的概念之后，列關(guān)鍵字就采用下述的語(yǔ)法規(guī)則來(lái)定義：

族名：限定詞（family：qualifier）

族名必須有意義，限定詞則可以任意選定

圖中，內(nèi)容（Contents）、錨點(diǎn)（Anchor）都是不同的族。而和my.look.ca則是錨點(diǎn)族中不同的限定詞

族同時(shí)也是Bigtable中訪問(wèn)控制（AccessControl）基本單元，也就是說(shuō)訪問(wèn)權(quán)限的設(shè)置是在族這一級(jí)別上進(jìn)行的數(shù)據(jù)模型時(shí)間戳

Google的很多服務(wù)比如網(wǎng)頁(yè)檢索和用戶(hù)的個(gè)性化設(shè)置等都需要保存不同時(shí)間的數(shù)據(jù)，這些不同的數(shù)據(jù)版本必須通過(guò)時(shí)間戳來(lái)區(qū)分。圖2中內(nèi)容列的t3、t5和t6表明其中保存了在t3、t5和t6這三個(gè)時(shí)間獲取的網(wǎng)頁(yè)。Bigtable中的時(shí)間戳是64位整型數(shù)，具體的賦值方式可以采取系統(tǒng)默認(rèn)的方式，也可以用戶(hù)自行定義

為了簡(jiǎn)化不同版本的數(shù)據(jù)管理，Bigtable目前提供了兩種設(shè)置：一種是保留最近的N個(gè)不同版本，圖中數(shù)據(jù)模型采取的就是這種方法，它保存最新的三個(gè)版本數(shù)據(jù)。另一種就是保留限定時(shí)間內(nèi)的所有不同版本，比如可以保存最近10天的所有不同版本數(shù)據(jù)。失效的版本將會(huì)由Bigtable的垃圾回收機(jī)制自動(dòng)處理

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

設(shè)計(jì)動(dòng)機(jī)與目標(biāo)

數(shù)據(jù)模型

系統(tǒng)架構(gòu)

主服務(wù)器

子表服務(wù)器

性能優(yōu)化系統(tǒng)架構(gòu)

一個(gè)分布式的任務(wù)調(diào)度器，主要被用來(lái)處理分布式系統(tǒng)隊(duì)列分組和任務(wù)調(diào)度

系統(tǒng)架構(gòu)

在Bigtable中Chubby主要有以下幾個(gè)作用：（1）選取并保證同一時(shí)間內(nèi)只有一個(gè)主服務(wù)器（MasterServer）（2）獲取子表的位置信息（3）保存Bigtable的模式信息及訪問(wèn)控制列表

另外在Bigtable的實(shí)際執(zhí)行過(guò)程中，Google的MapReduce和Sawzall也被用來(lái)改善其性能系統(tǒng)架構(gòu)

Bigtable主要由三個(gè)部分組成：客戶(hù)端程序庫(kù)（ClientLibrary）、一個(gè)主服務(wù)器（MasterServer）和多個(gè)子表服務(wù)器（TabletServer）

客戶(hù)訪問(wèn)Bigtable服務(wù)時(shí)，首先要利用其庫(kù)函數(shù)執(zhí)行Open()操作來(lái)打開(kāi)一個(gè)鎖（實(shí)際上就是獲取了文件目錄），鎖打開(kāi)以后客戶(hù)端就可以和子表服務(wù)器進(jìn)行通信

和許多具有單個(gè)主節(jié)點(diǎn)分布式系統(tǒng)一樣，客戶(hù)端主要與子表服務(wù)器通信，幾乎不和主服務(wù)器進(jìn)行通信，這使得主服務(wù)器的負(fù)載大大降低

主服務(wù)主要進(jìn)行一些元數(shù)據(jù)操作以及子表服務(wù)器之間負(fù)載調(diào)度問(wèn)題，實(shí)際數(shù)據(jù)是存儲(chǔ)在子表服務(wù)器上

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

設(shè)計(jì)動(dòng)機(jī)與目標(biāo)

數(shù)據(jù)模型

系統(tǒng)架構(gòu)

主服務(wù)器

子表服務(wù)器

性能優(yōu)化主服務(wù)器

當(dāng)一個(gè)新子表產(chǎn)生時(shí)，主服務(wù)器通過(guò)一個(gè)加載命令將其分配給一個(gè)空間足夠的子表服務(wù)器。創(chuàng)建新表、表合并以及較大子表的分裂都會(huì)產(chǎn)生一個(gè)或多個(gè)新子表。對(duì)于前面兩種，主服務(wù)器會(huì)自動(dòng)檢測(cè)到，而較大子表的分裂是由子服務(wù)發(fā)起并完成的，所以主服務(wù)器并不能自動(dòng)檢測(cè)到，因此在分割完成之后子服務(wù)器需要向主服務(wù)發(fā)出一個(gè)通知

由于系統(tǒng)設(shè)計(jì)之初就要求能達(dá)到良好的擴(kuò)展性，所以主服務(wù)器必須對(duì)子表服務(wù)器的狀態(tài)進(jìn)行監(jiān)控，以便及時(shí)檢測(cè)到服務(wù)器的加入或撤銷(xiāo)

Bigtable中主服務(wù)器對(duì)子表服務(wù)器的監(jiān)控是通過(guò)Chubby完成的——子表服務(wù)器在初始化時(shí)都會(huì)從Chubby中得到一個(gè)獨(dú)占鎖。通過(guò)這種方式所有子表服務(wù)器基本信息被保存在Chubby中一個(gè)稱(chēng)為服務(wù)器目錄（ServerDirectory）的特殊目錄之中主服務(wù)器

主服務(wù)器會(huì)定期向其詢(xún)問(wèn)獨(dú)占鎖的狀態(tài)。如果子表服務(wù)器的鎖丟失或沒(méi)有回應(yīng)，則此時(shí)可能有兩種情況

要么是Chubby出現(xiàn)了問(wèn)題（雖然這種概率很小，但的確存在，Google自己也做過(guò)相關(guān)測(cè)試）

要么是子表服務(wù)器自身出現(xiàn)了問(wèn)題。對(duì)此主服務(wù)器首先自己嘗試獲取這個(gè)獨(dú)占鎖，如果失敗說(shuō)明Chubby服務(wù)出現(xiàn)問(wèn)題，需等待恢復(fù)；如果成功則說(shuō)明Chubby服務(wù)良好而子表服務(wù)器本身出現(xiàn)了問(wèn)題

當(dāng)在狀態(tài)監(jiān)測(cè)時(shí)發(fā)現(xiàn)某個(gè)子表服務(wù)器上負(fù)載過(guò)重時(shí)，主服務(wù)器會(huì)自動(dòng)對(duì)其進(jìn)行負(fù)載均衡操作

主服務(wù)器

基于系統(tǒng)出現(xiàn)故障是一種常態(tài)的設(shè)計(jì)理念，每個(gè)主服務(wù)器被設(shè)定了一個(gè)會(huì)話(huà)時(shí)間的限制。當(dāng)某個(gè)主服務(wù)器到時(shí)退出后，管理系統(tǒng)就會(huì)指定一個(gè)新的主服務(wù)器，這個(gè)主服務(wù)器的啟動(dòng)需要經(jīng)歷以下四個(gè)步驟：

（1）從Chubby中獲取一個(gè)獨(dú)占鎖，確保同一時(shí)間只有一個(gè)主服務(wù)器（2）掃描服務(wù)器目錄，發(fā)現(xiàn)目前活躍的子表服務(wù)器（3）與所有的活躍子表服務(wù)器取得聯(lián)系以便了解所有子表的分配情況（4）掃描元數(shù)據(jù)表，發(fā)現(xiàn)未分配的子表并將其分配到合適子表服務(wù)器如果元數(shù)據(jù)表未分配，則首先需要將根子表（RootTablet）加入未分配的子表中。由于根子表保存了其他所有元數(shù)據(jù)子表的信息，確保了掃描能夠發(fā)現(xiàn)所有未分配的子表分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

設(shè)計(jì)動(dòng)機(jī)與目標(biāo)

數(shù)據(jù)模型

系統(tǒng)架構(gòu)

主服務(wù)器

子表服務(wù)器

性能優(yōu)化SSTable及子表基本結(jié)構(gòu)

SSTable是Google為Bigtable設(shè)計(jì)的內(nèi)部數(shù)據(jù)存儲(chǔ)格式。所有的SSTable文件都存儲(chǔ)在GFS上

SSTable中數(shù)據(jù)被劃分成一個(gè)個(gè)的塊（Block），每個(gè)塊的大小是可以設(shè)置的，一般為64KB

在SSTable的結(jié)尾有一個(gè)索引（Index），這個(gè)索引保存了塊的位置信息，在SSTable打開(kāi)時(shí)這個(gè)索引會(huì)被加載進(jìn)內(nèi)存，用戶(hù)在查找某個(gè)塊時(shí)首先在內(nèi)存中查找塊的位置信息，然后在硬盤(pán)上直接找到這個(gè)塊

由于每個(gè)SSTable一般都不是很大，用戶(hù)還可以選擇將其整體加載進(jìn)內(nèi)存，這樣查找起來(lái)會(huì)更快

SSTable結(jié)構(gòu)

子表實(shí)際組成

每個(gè)子表都是由多個(gè)SSTable以及日志（Log）文件構(gòu)成

不同子表的SSTable可以共享Bigtable中的日志文件是一種共享日志，每個(gè)子表服務(wù)器上僅保存一個(gè)日志文件，某個(gè)子表日志只是這個(gè)共享日志的一個(gè)片段。這樣會(huì)節(jié)省大量的空間，但在恢復(fù)時(shí)卻有一定的難度Google為了避免這種情況出現(xiàn)，對(duì)日志做了一些改進(jìn)。Bigtable規(guī)定將日志的內(nèi)容按照鍵值進(jìn)行排序，這樣不同的子表服務(wù)器都可以連續(xù)讀取日志文件了

一般來(lái)說(shuō)每個(gè)子表的大小在100MB到200MB之間。每個(gè)子表服務(wù)器上保存的子表數(shù)量可以從幾十到上千不等，通常情況下是100個(gè)左右

子表地址結(jié)構(gòu)

子表地址的查詢(xún)是經(jīng)常碰到的操作。在Bigtable系統(tǒng)的內(nèi)部采用的是一種類(lèi)似B+樹(shù)的三層查詢(xún)體系

所有子表地址都被記錄在元數(shù)據(jù)表中，元數(shù)據(jù)表也是由一個(gè)個(gè)的元數(shù)據(jù)子表（Metadatatablet）組成

根子表是元數(shù)據(jù)表中一個(gè)比較特殊的子表，它既是元數(shù)據(jù)表的第一條記錄，也包含了其他元數(shù)據(jù)子表的地址，同時(shí)Chubby中的一個(gè)文件也存儲(chǔ)了這個(gè)根子表的信息。

查詢(xún)時(shí)，首先從Chubby中提取這個(gè)根子表的地址，進(jìn)而讀取所需的元數(shù)據(jù)子表的位置，最后就可以從元數(shù)據(jù)子表中找到待查詢(xún)的子表。除了這些子表的元數(shù)據(jù)之外，元數(shù)據(jù)表中還保存了其他一些有利于調(diào)試和分析的信息，比如事件日志等

為了減少訪問(wèn)開(kāi)銷(xiāo)，提高客戶(hù)訪問(wèn)效率，Bigtable使用了緩存（Cache）和預(yù)?。≒refetch）技術(shù)

子表的地址信息被緩存在客戶(hù)端，客戶(hù)在尋址時(shí)直接根據(jù)緩存信息進(jìn)行查找。一旦出現(xiàn)緩存為空或緩存信息過(guò)時(shí)的情況，客戶(hù)端就需要按照?qǐng)D示方式進(jìn)行網(wǎng)絡(luò)的來(lái)回通信（NetworkRound-trips）進(jìn)行尋址，在緩存為空的情況下需要三個(gè)網(wǎng)絡(luò)來(lái)回通信。如果緩存的信息是過(guò)時(shí)的，則需要六個(gè)網(wǎng)絡(luò)來(lái)回通信。其中三個(gè)用來(lái)確定信息是過(guò)時(shí)的，另外三個(gè)獲取新的地址

預(yù)取則是在每次訪問(wèn)元數(shù)據(jù)表時(shí)不僅僅讀取所需的子表元數(shù)據(jù)，而是讀取多個(gè)子表的元數(shù)據(jù)，這樣下次需要時(shí)就不用再次訪問(wèn)元數(shù)據(jù)表

子表數(shù)據(jù)存儲(chǔ)及讀/寫(xiě)操作

Bigtable數(shù)據(jù)存儲(chǔ)及讀/寫(xiě)操作

Bigtable將數(shù)據(jù)存儲(chǔ)劃分成兩塊：較新的數(shù)據(jù)存儲(chǔ)在內(nèi)存中一個(gè)稱(chēng)為內(nèi)存表（Memtable）的有序緩沖里，較早的數(shù)據(jù)則以SSTable格式保存在GFS中

寫(xiě)操作（WriteOp）——先查詢(xún)Chubby中保存的訪問(wèn)控制列表確定用戶(hù)具相應(yīng)寫(xiě)權(quán)限，通過(guò)認(rèn)證之后寫(xiě)入的數(shù)據(jù)首先被保存在提交日志（CommitLog）中。提交日志中以重做記錄（RedoRecord）的形式保存著最近的一系列數(shù)據(jù)更改，這些重做記錄在子表進(jìn)行恢復(fù)時(shí)可以向系統(tǒng)提供已完成的更改信息。

讀操作（ReadOp）——先通過(guò)認(rèn)證，之后讀操作就要結(jié)合內(nèi)存表和SSTable文件來(lái)進(jìn)行，因?yàn)閮?nèi)存表和SSTable中都保存了數(shù)據(jù)

三種形式壓縮之間的關(guān)系

Bigtable中有三種形式的數(shù)據(jù)壓縮：

次壓縮（MinorCompaction）

合并壓縮（MergingCompaction）

主壓縮（MajorCompaction）數(shù)據(jù)壓縮問(wèn)題每一次舊的內(nèi)存表停止使用時(shí)都會(huì)進(jìn)行一個(gè)次壓縮操作，這會(huì)產(chǎn)生一個(gè)SSTable。但如果系統(tǒng)中只有這種壓縮的話(huà)，SSTable的數(shù)量就會(huì)無(wú)限制地增加下去而在Bigtable中，讀操作實(shí)際上比寫(xiě)操作更重要，因此Bigtable會(huì)定期地執(zhí)行一次合并壓縮的操作，將一些已有的SSTable和現(xiàn)有的內(nèi)存表一并進(jìn)行一次壓縮主壓縮其實(shí)是合并壓縮的一種，只不過(guò)它將所有的SSTable一次性壓縮成一個(gè)大的SSTable文件。主壓縮也是定期執(zhí)行，執(zhí)行一次主壓縮之后可以保證將所有的被壓縮數(shù)據(jù)徹底刪除分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

設(shè)計(jì)動(dòng)機(jī)與目標(biāo)

數(shù)據(jù)模型

系統(tǒng)架構(gòu)

主服務(wù)器

子表服務(wù)器

性能優(yōu)化局部性群組（Localitygroups）

局部性群組(LocalityGroup)

根據(jù)需要，將原本不存儲(chǔ)在一起的數(shù)據(jù)，以列族為單位存儲(chǔ)至單獨(dú)的子表

有的用戶(hù)可能只對(duì)網(wǎng)頁(yè)內(nèi)容感興趣，那么它可以通過(guò)設(shè)置局部性群組（見(jiàn)下圖）只看內(nèi)容這一列；有的對(duì)諸如網(wǎng)頁(yè)語(yǔ)言、網(wǎng)站排名等可以用于分析的信息比較感興趣，他也可以將這些列設(shè)置到一個(gè)群組中

壓縮

壓縮

壓縮可以有效地節(jié)省空間，Bigtable中的壓縮被應(yīng)用于很多場(chǎng)合

首先壓縮可以被用在構(gòu)成局部性群組的SSTable中，可以選擇是否對(duì)個(gè)人的局部性群組的SSTable進(jìn)行壓縮。這種壓縮是對(duì)每個(gè)局部性群組獨(dú)立進(jìn)行，雖然會(huì)浪費(fèi)一些空間，但是在需要讀時(shí)解壓速度非常快

通常情況下，用戶(hù)可