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

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

設(shè)計動機與目標

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

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

主服務(wù)器

子表服務(wù)器

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

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

廣泛的適用性

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

簡單性

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

很強的可擴展性

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

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

設(shè)計動機與目標

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

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

主服務(wù)器

子表服務(wù)器

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

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

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

Bigtable的存儲邏輯可以表示為：

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

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

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

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

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

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

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

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

族名：限定詞（family：qualifier）

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

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

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

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

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

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

設(shè)計動機與目標

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

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

主服務(wù)器

子表服務(wù)器

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

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

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

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

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

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

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

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

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

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

設(shè)計動機與目標

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

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

主服務(wù)器

子表服務(wù)器

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

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

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

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

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

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

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

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

主服務(wù)器

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

（1）從Chubby中獲取一個獨占鎖，確保同一時間只有一個主服務(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è)計動機與目標

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

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

主服務(wù)器

子表服務(wù)器

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

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

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

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

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

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

子表實際組成

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

次壓縮（MinorCompaction）

合并壓縮（MergingCompaction）

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

設(shè)計動機與目標

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

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

主服務(wù)器

子表服務(wù)器

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

局部性群組(LocalityGroup)

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

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

壓縮

壓縮

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

首先壓縮可以被用在構(gòu)成局部性群組的SSTable中，可以選擇是否對個人的局部性群組的SSTable進行壓縮。這種壓縮是對每個局部性群組獨立進行，雖然會浪費一些空間，但是在需要讀時解壓速度非?？?/p>

通常情況下，用戶可