Bigtable_1 (MIT 6.824: Lec 3: Reading)

• 2020 年 12 月 15 日
• AI

從本篇文章開始，專欄將以《MIT 6.824：Distributes Systems》的課程邏輯出發，逐步更新課程內的全部內容，敬請關注，謝謝。

如果想要跟方便的查看課程的更新內容，也歡迎關注微信公眾號：《油麻酥愛學習愛健身》，微訊號：youmasu。

除了MIT分散式課程的學習以外，公眾號還會不定期分享自己的健身經驗，包括，家庭自重健身，健身房增肌減脂，日常飲食營養等健身內容，再次謝謝大家。

一、簡介

設計上，Bigtable是一個管理PB級結構化數據的分散式存儲系統。Google中超過60個項目的數據都存在Bigtable中，比如網頁索引、Google地球和Google金融。雖然這些應用在數據大小（網頁URL vs. 衛星圖片）和延遲要求（高吞吐後台數據處理 vs. 低延遲實時數據處理）各有不同，但Bigtable卻能為它們統一提供可擴展、高性能和高可用的解決方案。本文將詳細介紹Bigtable中的數據模型是如何為客戶端提供動態控制選項（數據布局、格式）的設計方案和具體實現。

雖然Bigtable基於很多已有的資料庫設計理念而實現，比如，並行資料庫和記憶體資料庫實現了高擴展和高性能。但是它提供了一個完全不同的使用介面。Bigtable不支援完整的關係型數據模型，相反，它為客戶端提供簡單的數據模型，以支援對數據布局和格式的動態控制，並允許客戶端去推理存儲在底層資料庫中的局部性（locality property）。數據可以使用任意字元串表示的行列名稱進行索引。雖然這些字元串通常由客戶端將各種結構化或半結構化的數據序列化而得到，但Bigtable並不關心它們。因此，客戶端可以審慎地選擇適合自己業務的schema來控制數據的局部性。最後，Bigtable提供的參數還可以讓客戶端自主選擇數據是存儲在記憶體或是落地到磁碟。

二、數據模型

Bigtable是稀疏的、分散式的、持久化的多維排序map。這個map使用row key，column key和timestamp作為索引，map里的value是一個經過用戶序列化後的位元組數組。

形式上，等價於(row:string, column:string, time:int64) -> string。

我們調研了大量有可能使用bigtable的場景後，決定是有這個模型。比如，我想要保存一份海量網頁和它們相關資訊的數據，暫命名為Webtable。如果使用URL作為row key，頁面上的其他資訊作為column key後，存儲網頁在所有column中，不同time下抓取的content。如下圖所示：

1、Rows

table中的row key可以是任意字元串，最大可達到64KB，但通常只有10-100個位元組。所有在一個row key下的讀寫操作都是原子的，和它的columns無關。這個設計可以方便client在並發更新同一行數據時，理解和推測系統的行為。

bigtable按照字母序維護row key。一張表中row range是動態劃分的，一個row range被稱作一個tablet，它是分散式和負載均衡的基本單位。因此，多次讀取一個小的row range，只需要和少部分的機器通訊，效率高。客戶端可以充分利用這個特性去選擇它們的row key，並以此擁有在訪問時，比較好的局部性。比如，在Webtable中，相同域下的若干個頁面，可以通過反轉URL，使其自動按照域名分組。因此，按照域名的網頁分析會更高效。

2、Column Family

column key被分組到set中，作為訪問控制的基本單元，該set被稱作Column Family。相同column family數據的type相同，並且會被壓縮。在數據被存儲到任意一個column key之前，column family必須提前創建，然後才能被使用。設計上，column family最多只有幾百個，數量很小。但是，一張表可能有「無限」多個column。

一個column key使用family:qualifier來定義。family必須要能被列印，但qualifier可以是任意string。比如在Webtable中，有個column family是language family，其中我們只使用一個column key，存儲所有網頁的language ID。另一個column family是錨點（anchor），每個column key代表一種單獨的anchor，qualifier就是它引用的站點名稱，content就是anchor的單元格內容。

訪問許可權控制、硬碟和記憶體使用數據記賬都在column-family的層級進行。比如，在Webtable中，column-family控制我們對不同類型操作（增刪查改）許可權的管理。

3、時間戳（Timestamps）

Bigtable中的每個單元格都包含同一數據的多個版本。所有版本使用一個64位的時間戳按照遞減順序來索引，最新的數據被優先讀取。Bigtable默認使用以毫秒計的時間戳，客戶端應用也可以在避免業務衝突的場景下，自行指定時間戳。

為了降低多版本數據管理的複雜性，我們使用兩個per-column-family的設置，讓Bigtable自動收集過期版本的數據。因此，client可以指定保留最近n個版本的數據或者「足夠新」的版本數據（比如，指定天數內）。在Webtable的例子中，使用抓取時間作為正文contents的時間戳，每個頁面只保留最新3個版本的數據。

三、API

Bigtable提供創建或刪除table和column family的函數（偏內容），以及改變集群、table或column family元數據的函數（偏控制）。

client應用可以寫入或刪除Bigtable中的元素值、從row中查找元素、迭代table中的數據子集。下圖展示了C++如何使用RowMutation的封裝執行一系列更新操作。Apply函數向//www.cnn.com中新增一個錨點的同時，刪除其他錨點。

下圖也展示了C++如何使用Scanner封裝迭代特定row的所有錨點。client可以同時迭代多個column families，Bigtable提供各種機制來限制由scan查出來的rows、columns和timestamps數目。比如，正則表達式匹配錨點模式，timestamp限制時間範圍。

Bigtable也支援其他特性允許用戶以更複雜的方式操作數據。首先，Bigtable支援單行事務。即，在一個單獨的row key上，支援原子化的read-modify-write操作。雖然Bigtable也提供了對多個row key的批量操作介面，但是目前並不支援跨row key的通用事務。其次，Bigtable允許client將單元格作為整形計數器。最後，Bigtable支援Sawzall腳本執行數據轉換、任意表達式的過濾和列印不同操作的數據報表等操作，但不允許將數據寫回到Bigtable。

在MapReduce上，Bigtable已經得到了廣泛應用。我們也實現了很多封裝以方便將Bigtable作為MapReduce Job的輸入或輸出源。

四、構建基礎

Bigtable建立在Google已有的基礎設施上。比如，使用GFS作為日誌或數據文件的文件存儲系統；使用Google的集群管理系統來調度任務，管理資源和共享機器的同時，實現容錯和監控。

Bigtable使用GoogleSSTable文件格式來存儲數據。SSTable提供一個持久化、有序性和不可變的k-v map支援查找和迭代，其中k和v是任意位元組數組。SSTable內部使用blocks來組織數據，每個block通常是64KB，支援可配。同時，在打開SSTable時，可以將存儲在末尾的索引載入記憶體來定位block。SSTable的查找操作通常在一次disk seek中完成：首先使用記憶體中的索引執行二分搜索，找到對應的block；接著從磁碟中讀取block並查找目標數據。作為備選，SSTable可以被完整映射到記憶體中，在記憶體中完成查找和遍歷。

五、實現

Bigtable的實現有3個主要組件：客戶端鏈接庫、一個master server和很多可根據負載情況動態擴縮的tablet servers。

master的任務是向tablet server分配tablet、探測tablet server的新增或過期、平衡tablet server的負載、垃圾收集儲存在GFS上的文件以及處理類似table或column family相關的schema的改變。

一般情況下，一個tablet server管理10到1000個tablet，並處理該tablet上的所有讀寫請求。當tablet太大時，還能支援tablet自動拆分。

跟很多其他單主的分散式存儲系統一樣，client的數據讀寫都是直接與tablet server通訊。並且Bigtable客戶端不依賴由master提供的tablet位置資訊，大多數client甚至都不會和master通訊。因此，master的負載極低。

Bigtable集群可以存儲若干tables，每個table由一個tablet集合組成，每個tablet包含一個row range中的所有數據。初始狀態下，一個table只有一個tablet，隨著table的增長，可以自動拆分成多個tablets，每個tablet默認100-200MB。

1、Tablet位置

Bigtable使用一個類似B+樹的三層結構存儲tablet的位置資訊。

第一層是存儲在Chubby中的文件，包含root tablet的位置資訊。Root tablet是第一個METADATA table，它包含所有其他METADATA tablets的位置資訊。對Bigtable而言，root tablet是一個特殊存在，它一定不會被拆分，確保tablet位置資訊的層次不超過3層。

METADATA table存儲一個row key下，一個tablet的位置資訊，其中row key以tablet的表名和結束行來編碼。每個METADATA行在記憶體中大概存儲1KB的數據。在保守估計的假設下，128MB的METADATA tablets在三層結構下足夠存儲2^34個tablets的地址。

Bigtable提供的客戶端鏈接庫會快取tablet的位置。如果client不知道tablet的位置或者已知的位置出錯，它會遞歸地逐層向上尋找。即，如果client快取為空，定址演算法會有3次網路通訊，包括從chubby讀文件。如果快取臟掉了，定址演算法有6次網路通訊，因為首先會經過3次定址後，才發現tablet位置miss了，再重新查位置。雖然tablet的位置資訊都存在記憶體中，應該在定址的時候盡量避免對GFS的訪問。所以，client鏈接庫會在每次讀取METADATA table的時候，額外讀入一些其他tablet的位置資訊。

Bigtable也會在METADATA table中存儲一些二級資訊，包括每個tablet所有事件的日誌資訊（比如，tablet server啟動時間等）。這些資訊有助於調試程式碼和性能分析。

2、Tablet分配

每個tablet會在合適的時間被分配給一個tablet server。master保持與所有tablet servers的通訊，並維護當前tablet的分配狀態（已分配和未分配）。當一個tablet未分配而其中一個tablet server又有足夠的空間，master會發出一個tablet load請求分配這個tablet。

Bigtable使用Chubby來維護所有tablet servers。當一個tablet server啟動時，Chubby會在一個特定的目錄中獲得一個排他鎖，並創建文件和指定一個唯一命名。master通過實時監控該目錄來發現tablet server。如果一個tablet server因為網路中斷而丟失了與Chubby的連接進而失去了它自己的排他鎖時，tablet server會暫時停止服務。但是，Chubby會提供一個高效的機制來確保，在不通過網路的情況下，讓tablet有辦法check自己是否還持有這把鎖。只要目錄中的文件存在，該tablet server還會嘗試去重新獲取該文件的排他鎖。但如果文件已經不存在了，該tablet server就只能kill掉自己，不再提供服務了。當這種情況發生時，tablet服務終止，並嘗試釋放這把鎖，集群管理系統也會將該server移出集群，好讓master儘快感知，並向其他server分配tablets。

Master server有義務也有責任做到這一點。它會周期性的輪詢所有tablet server並詢問它們持有鎖的狀態。當tablet server失去鎖或master不能連通它時，master會去嘗試獲取這把鎖，如果獲取成功，說明Chubby是好的，而tablet server要麼down，要麼無法和Chubby通訊。因此，master斷定該tablet server有問題，並刪除這個指定的文件。一旦文件被刪除，master就能決定將先前分配給該tablet server的所有tablets全部置為未分配狀態。如果master自己和Chubby斷連，master會立即kill掉自己，這種情況並不會改變已分配tablets的任何狀態。

當集群管理系統重新啟動master時，在發生任何改變前，master需要先了解當前tablet的分配狀態。他會依次執行如下4步：（1）master獲取Chubby中自己文件的排他鎖，防止腦裂；（2）master遍歷Chubby中所有的server目錄檢查仍然存活的tablet server；（3）master和每個tablet server通訊，以獲取當前已分配tablet的基本情況；（4）master瀏覽METADATA table了解所有tablet的基本情況。在此過程中，master會維護所有未分配tablet的列表，以便後續地正常工作。

有一個麻煩的地方是，在METADATA table未被分配之前肯定是沒法遍歷的。所以，如果在第（3）步，master發現root tablet未被分配，就需要立馬將其放入未分配集合，以確保master自己能從root tablet中讀到所有METADATA table的資訊。

有4種情況會改變tablet的存在性：新建、刪除、合併和拆分。master會跟蹤所有的變化情況。前3種由master發起，但第4種「拆分」確是由tablet server發起。由tablet server首先到METADATA table中創建新的tablet資訊以提交拆分請求，完成後通知master。為了防止通知消息因為網路或服務異常的原因丟失，master會要求tablet server首先載入需要拆分的tablet，然後才能檢測到新的tablet。

3、Tablet Serving

tablet的狀態被持久化存儲在GFS中。任何更新操作首先被提交到一份commit log中，供撤銷使用。最近提交的更新操作以memtable（一個排序buffer）的形式放入記憶體，較老的更新按次序存在SSTables里。

為了發現一個tablet，tablet server會從METADATA table中讀取自己的metadata。其中包含一個SSTable的列表，tablet server會依次讀取SStable中包含的checkpoint和update log，並在記憶體中重建這個tablet。

當一個寫操作到達tablet server時，tablet server首先檢查請求的有效性（格式正確且客戶端被授權）。其中，被授權的客戶端列表存在一個特殊的Chubby文件中，它的讀取一定能被快取命中。有效的mutation首先會被寫入commit log。Commit log會被分組提交以提高small mutation的吞吐量。寫操作提交完成後，它的內容會被插入到memtable里。

當一個讀操作到達tablet server時，同樣會先檢查有效性。讀操作會在SSTable和memtable合併後的視圖上執行。因為SSTable和memtable本身就是依字母序排列的，所以合併操作非常高效。

在當前tablet被拆分或合併之前，讀、寫操作都會按上文的描述有序進行。

4、Compaction

隨著寫操作的進行，memtable的size也隨之增大。當memtable增長到指定閾值會被自動凍結，同時創建一個新的memtable，並且凍結的memtable會被轉換成一個SSTable並寫入GFS。Minor compaction有2個目的：其一是減少tablet server的記憶體佔用；其二是減少在server掛掉並重啟後，恢複數據時需要讀取的數據量。當compaction在進行的過程中，讀寫不受影響。

每一次的minor compaction都會創建一個新的SSTable。為了避免由client在讀取時merge不同的SSTable才能獲得最終更新結果，由Bigtable在後台周期性的執行merging compaction。這個過程會讀取若干張SSTable和memtable的數據並創建合併後的SStable。當merging compaction完成後，作為輸入的SStable和memtable會被丟棄。

如果某一次的merging操作新建了一個匯總的SStable，則這一次的操作被稱為major compaction。minor新建的SSTable可能會包含一些特殊的deletion entries來表明某些在老舊SSTable中看上去仍然存活的數據實際上已經被刪除了。這種deletion記錄在major新建的SSTable種不會出現。Bigtable會定期對所有的tablet執行major compaction。在該過程中，Bigtable會回收已刪除數據的資源並確保數據在系統中及時、徹底消失，這對那些存儲敏感數據的應用非常重要。

六、細節

之前介紹的主要功能需要太多的細節設計才能保證用戶對高性能、高可用和高可靠的要求。

1、Locality groups

客戶端可以將多個column family按一個locality group分組。當在任意一個tablet中出現任意一個locality group時，就會創建一個隔離的SSTable。當然，為了保證高效地讀操作，完全不搭界的column family也不應該被分組到一個locality group中。比如在Webtable項目中，網頁元數據之間（language、checksums等），可以被分到一個locality group，但任意元數據和網頁正文內容之間，肯定不能這樣。畢竟，對於只需要元數據的應用來說，完全對正文內容不感興趣。

另外，有一些有用的微調參數，可以在每一個不同的locality group上進行調整。比如，一個locality group可以在記憶體中聲明後，對應的SSTable會被tablet server懶載入到記憶體。一旦載入成功，這些column family上的數據訪問就不用再通過硬碟。這對需要高頻訪問的數據片段非常有用：比如，METADATA table中的location column family。

2、Compression

Client可以控制是否對某一個locality group的SSTable數據塊進行壓縮，並指定壓縮格式（SSTable數據塊的大小由微調參數指定）。雖然按照SSTable數據塊來壓縮會浪費一些空間，但讀取數據時也不用為了查找某個數據塊而解壓整個文件。client通常會使用自定義的two-pass compression schema。The first pass使用Bentley-McIlroy演算法，它使用一個大的窗口壓縮長字元串。The second past使用快速壓縮演算法在一個16KB的數據窗口內尋找重複數據。Two-pass compression schema執行效率非常高，編碼有100-200MB/s，解碼則達到400-1000MB/s。

同樣，Two-pass compression的壓縮比也很高，在Webtable的實驗場景下，只存儲網頁內容的一個版本，壓縮比可以達到10-to-1，遠好於Gzip在存儲HTML內容時3-to-1或4-to-1的壓縮比。究其原因，主要是Bigtable的行布局能力。在Webtable項目中，來自相同host的所有網頁存儲位置非常接近，這使得Bentley-McIlroy演算法可以在一個host的內容中定義大量的共享模板。如果存儲數據的多個版本，會有更高的壓縮比。

3、讀時快取

Tablet server使用2層快取架構提高讀性能。第一層Scan Cache快取由SSTable介面返回的key-value pair。第二層Block Cache快取從GFS中讀取的SSTable block。當應用層讀取相同的業務數據時，Scan Cache發揮作用。當應用層讀取與業務數據在布局上相近的數據時（比如在同一個locality group上順序讀或隨機讀數據），Block Cache發揮作用。

4、Bloom filters

前文圖示的讀操作，必須讀取一個tablet下的所有SSTables來獲取最新數據。如果這些SSTables不在記憶體里，將會從磁碟載入。 Bigtable允許client在一個特定的locality group的SSTable中自定義Bloom filter，以減少對磁碟的訪問。Bloom filter對檢索指定的row/column pair是否存在於某個SSTable中非常高效。在特定應用中，當tablet server使用少量的記憶體存儲Bloom filter時，將大大減少對磁碟的訪問。當然，使用Bloom filter的前提是，Bigtable假設應用中存在大量無效或不存在任何數據的row/column的查找，這根本不需要去訪問磁碟。

5、Commit-log的實現

如果我們為每一個tablet都保存一個單獨的commit log，大量存儲在GFS中的log文件將會被並發寫。受制於GFS的文件系統實現，對物理磁碟上不同日誌文件的寫操作會產生大量的磁碟尋道。除此之外，每個tablet一個日誌文件還會降低group commit效率，因為每一個group相對會變得更小。因此，最終我們決定讓每一個tablet server使用append mutation的方式記錄一份日誌，將其上若干個tablet的日誌記錄到一個文件上。

一個log文件的方案在正常場景下帶來巨大的性能提升，但使得出錯恢復時的邏輯更複雜。每當一個tablet server宕機，其上的tablets都要被轉移到其他tablet server上，雖然每個tablet server只負責其中一小塊tablet的轉移，但仍然需要執行掛掉tablet server上所有commit log的操作。因為SSTable是不可變的，所以對它的讀操作不需要任何並發同步，效率很高。但對可變的memtable的讀寫都是需要同步的，為了提高memtable的讀性能，我們為每一個memtable設計row cop-on-write的方案來允許並行讀寫。

因為SSTables是不可變的，所以只能使用垃圾收集的方式來刪除廢棄的SSTable。因為每個tablet的SSTable都會在METADATA里註冊，master可以使用「標記-清除」的方式執行垃圾清除。

最後，不可變的SSTables也讓split變得更高效。我們不用為拆分後的child tablet創建新的SSTable，而只需要讓它們共享parent SSTable即可。

七、參考文章

鏈接：//static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf