1、設計動機與目標

(1)設計動機

需要存儲的數據種類繁多：Google目前向公眾開放的服務很多，需要處理的數據類型也非常多。包括URL、網頁內容、用戶的個性化設置在內的數據都是Google需要經常處理的?

海量的服務請求：Google運行著目前世界上最繁忙的系統，它每時每刻處理的客戶服務請求數量是普通的系統根本無法承受的?

商用數據庫無法滿足Google的需求：一方面現有商用數據庫設計著眼點在于通用性，根本無法滿足Google的苛刻服務要求；另一方面對于底層系統的完全掌控會給后期的系統維護、升級帶來極大的便利?

(2)基本目標

2、數據模型

Bigtable是一個分布式多維映射表，表中的數據通過一個行關鍵字（Row Key）、一個列關鍵字（Column Key）以及一個時間戳（Time Stamp）進行索引

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

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

( row:string , column:string , time:int64)→string

?行

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

? ??表中數據都是根據行關鍵字進行排序的，排序使用的是詞典序。

??? ??一個典型實例，其中com.cnn.www就是一個行關鍵字。不直接存儲網頁地址而將其倒排是Bigtable的一個巧妙設計。這樣做至少會帶來以下兩個好處

?????? 同一地址域的網頁會被存儲在表中的連續位置，有利于用戶查找和分析

?????? 倒排便于數據壓縮，可以大幅提高壓縮率

?列

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

???族名：限定詞（family：qualifier）

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

????? 圖中，內容（Contents）、錨點（Anchor）都是不同的族。而cnnsi.com和my.look.ca則是錨點族中不同的限定詞

????? 族同時也是Bigtable中訪問控制（Access Control）基本單元，也就是說訪問權限的設置是在族這一級別上進行的

?時間戳

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

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

3、系統架構

?在Bigtable中Chubby主要有以下幾個作用：

（1）選取并保證同一時間內只有一個主服務器（MasterServer）

（2）獲取子表的位置信息

（3）保存Bigtable的模式信息及訪問控制列表

?另外在Bigtable的實際執行過程中，Google的MapReduce

和Sawzall也被用來改善其性能

4、主服務器

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

?由于系統設計之初就要求能達到良好的擴展性(既然要求有擴展性，那么，當有新的服務器加進來時，必須得及時知道)，所以主服務器必須對子表服務器的狀態進行監控，以便及時檢測到服務器的加入或撤銷

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

?主服務器會定期向其詢問獨占鎖的狀態。如果子表服務器的鎖丟失或沒有回應，則此時可能有兩種情況

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

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

?當在狀態監測時發現某個子表服務器上負載過重時，主服務器會自動對其進行 負載均衡操作

? 基于系統出現故障是一種常態的設計理念，每個主服務器被設定了一個會話時間的限制。當某個主服務器到時退出后，管理系統就會指定一個新的主服務器，這個主服務器的啟動需要經歷以下四個步驟：

?? （1）從Chubby中獲取一個獨占鎖，確保同一時間只有一個主服務器

?? （2）掃描服務器目錄，發現目前活躍的子表服務器

?? （3）與所有的活躍子表服務器取得聯系以便了解所有子表的分配情況

?? （4）掃描元數據表，發現未分配的子表并將其分配到合適子表服務器

如果元數據表未分配，則首先需要將根子表（Root Tablet）加入未分配的子表中。由于根子表保存了其他所有元數據子表的信息，確保了掃描能夠發現所有未分配的子表?

5、子表服務器

由于一個BigTable需要存儲海量數據，所以它不得不被分成多個Tablet，而每個Tablet都會負責一定范圍的列。并且存儲在多個服務器上。

SSTable及子表基本結構

SSTable是Sorted String Table的縮寫，按照鍵排序后存儲鍵/值對(Key——Value)字符串，并且它是不可變動的，也就是寫子之后，只能將其更新附加至其后，而不能直接對其進行修改，這樣是為了讓系統能執行磁盤所擅長的順序訪問，而不是隨機訪問。

SSTable及子表基本結構

子表實際組成?

Bigtable中的日志文件是一種共享日志，每個子表服務器上僅保存一個日志文件，某個子表日志只是這個共享日志的一個片段。這樣會節省大量的空間，但在恢復時卻有一定的難度

Google為了避免這種情況出現，對日志做了一些改進。Bigtable規定將日志的內容按照鍵值進行排序，這樣不同的子表服務器都可以連續讀取日志文件了 一般來說每個子表的大小在 100MB到200MB之間。每個子表服務器上保存的子表數量可以從幾十到上千不等，通常情況下是100個左右

（個人理解：由此，一個子表服務器上有一個日志文件，而同時，每個子表中也有自己的日志，它是其所在服務器上日志文件中的一個片段）

SSTable表的結構

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

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

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

2所有子表地址都被記錄在元數據表中，元數據表也是由一個個的元數據子表（Metadata tablet）組成

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

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

為了減少訪問開銷，提高客戶訪問效率，Bigtable使用了緩存（Cache）和預取（Prefetch）技術

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

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

子表數據存儲及元數據

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

?寫操作（Write Op）——先查詢Chubby中保存的訪問控制列表確定用戶具相應寫權限，通過認證之后寫入的數據首先被保存在提交日志（Commit Log）中。提交日志中以重做記錄（RedoRecord）的形式保存著最近的一系列數據更改，這些重做記錄在子表進行恢復時可以向系統提供已完成的更改信息。

? 讀操作（ Read Op ）——先通過認證，之后讀操作就要結合內存表和SSTable文件來進行，因為內存表和SSTable中都保存了數據

每一次舊的內存表停止使用時都會進行一個次壓縮操作，這會產生一個SSTable。但如果系統中只有這種壓縮的話，SSTable的數量就會無限制地增加下去?

而在Bigtable中，讀操作實際上比寫操作更重要，因此Bigtable會定期地執行一次合并壓縮的操作，將一些已有的SSTable和現有的內存表一并進行一次壓縮?

主壓縮其實是合并壓縮的一種，只不過它將所有的SSTable一次性壓縮成一個大的SSTable文件。主壓縮也是定期執行，執行一次主壓縮之后可以保證將所有的被壓縮數據徹底刪除

?壓縮

?

?壓縮可以有效地節省空間，Bigtable中的壓縮被應用于很多場合

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

?通常情況下，用戶可以采用兩步壓縮的方式：

?F第一步利用Bentley & McIlroy方式（BMDiff）在大的掃描窗口將常見的長串進行壓縮；第二步采取Zippy技術進行快速壓縮，它在一個16KB大小的掃描窗口內尋找重復數據，這個過程非常快

?壓縮技術還可以 提高子表的恢復速度，當某個子表服務器停止使用后，需要將上面所有的子表移至另一個子表服務器。轉移前兩次壓縮： 第一次壓縮減少了提交日志中未壓縮狀態；文件正式轉移前還要進行一次壓縮，主要是 將第一次壓縮后遺留的未壓縮空間進行壓縮

?布隆過濾器（Bloom Filter）

?

?巴頓·布隆在1970年提出的，實際上它是一個很長的二進制向量和一系列隨機映射函數，在讀操作中確定子表的位置時非常有用

?F優勢：速度快，省空間。而且它有一個最大的好處是它絕不會將一個存在的子表判定為不存在

?F缺點：在某些情況下它會將不存在的子表判斷為存在。不過這種情況出現的概率非常小，跟它帶來的巨大好處相比這個缺點是可以忍受的

????? 目前包括Google Analytics、Google Earth、個性化搜索、Orkut和RRS閱讀器在內幾十個項目都使用Bigtable。這些應用對Bigtable的要求以及使用的集群機器數量都各不相同，但從實際運行來看，Bigtable完全可以滿足這些不同需求的應用，而這一切都得益于其優良的構架以及恰當的技術選擇 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的《云计算》学习笔记4——Google的云计算原理与应用(分布式结构化数据表BigTable)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。