Bigtable結(jié)構(gòu)化數(shù)據(jù)的分布式存儲系統(tǒng)上

1、Bigtable 結(jié)構(gòu)化數(shù)據(jù)的分布式存儲系統(tǒng) 上轉(zhuǎn)載請注明：作者phylipsbmy摘要Bigtable是設(shè)計用來管理那些可能達到很大大小(比如可能是存儲在數(shù)千臺服務(wù)器上的數(shù)PB的數(shù)據(jù))的結(jié)構(gòu)化數(shù)據(jù)的分布式存儲系統(tǒng)。Google的很多項目都將數(shù)據(jù)存儲在Bigtable中，比如網(wǎng)頁索引，google地球，google金融。這些應(yīng)用對Bigtable提出了很多不同的要求，無論是數(shù)據(jù)大小(從單純的URL到包含圖片附件的網(wǎng)頁)還是延時需求。盡管存在這些各種不同的需求，Bigtable成功地為google的所有這些產(chǎn)品提供了一個靈活的，高性能的解決方案。在這篇論文中，我們將描述Bigtable所提供的允

2、許客戶端動態(tài)控制數(shù)據(jù)分布和格式的簡單數(shù)據(jù)模型，此外還會描述Bigtable的設(shè)計和實現(xiàn)。1.導(dǎo)引在過去的2年半時間里，我們設(shè)計,實現(xiàn),部署了一個稱為Bigtable的用來管理google的數(shù)據(jù)的分布式存儲系統(tǒng)。Bigtable的設(shè)計使它可以可靠地擴展到成PB的數(shù)據(jù)以及數(shù)千臺機器上。Bigtable成功的實現(xiàn)了這幾個目標：廣泛的適用性，可擴展性，高性能以及高可用性。目前，Bigtable已經(jīng)被包括Google分析，google金融，Orkut，個性化搜索，Writely和google地球在內(nèi)的60多個google產(chǎn)品和項目所使用。這些產(chǎn)品使用Bigtable用于處理各種不同的工作負載類型，從面向

3、吞吐率的批處理任務(wù)到時延敏感的面向終端用戶的數(shù)據(jù)服務(wù)。這些產(chǎn)品所使用的Bigtable集群也跨越了廣泛的配置規(guī)模，從幾臺機器到存儲了幾百TB數(shù)據(jù)的上千臺服務(wù)器。在很多方面，Bigtable都類似于數(shù)據(jù)庫：它與數(shù)據(jù)庫采用了很多相同的實現(xiàn)策略。目前的并行數(shù)據(jù)庫和主存數(shù)據(jù)庫已經(jīng)成功實現(xiàn)了可擴展性和高性能，但是Bigtable提供了與這些系統(tǒng)不同的接口。Bigtable并不支持一個完整的關(guān)系數(shù)據(jù)模型，而是給用戶提供了一個可以動態(tài)控制數(shù)據(jù)分布和格式的簡單數(shù)據(jù)模型，允許用戶將數(shù)據(jù)的局部性屬性體現(xiàn)在底層的數(shù)據(jù)存儲上。數(shù)據(jù)使用可以是任意字符串的行列名稱進行索引。Bigtable將數(shù)據(jù)看做是未經(jīng)解釋的字符串，盡

4、管用戶經(jīng)常將各種形式的結(jié)構(gòu)化或半結(jié)構(gòu)化的數(shù)據(jù)存儲到這些字符串里。用戶可以通過在schema中的細心選擇來控制數(shù)據(jù)的locality。最后，Bigtable的schema參數(shù)還允許用戶選擇從磁盤還是內(nèi)存獲取數(shù)據(jù)。第2節(jié)更加詳細的描述了該數(shù)據(jù)模型。第3節(jié)提供了關(guān)于用戶API的概覽。第4節(jié)簡要描述了Bigtable所依賴的底層軟件。第5節(jié)描述了Bigtable的基本實現(xiàn)。第6節(jié)描述了我們?yōu)樘岣連igtable的性能使用的一些技巧。第7節(jié)提供了一些對于Bigtable的性能測量數(shù)據(jù)。第8節(jié)展示了幾個Google內(nèi)部的Bigtable的使用實例。第9節(jié)討論了我們在設(shè)計支持Bigtable所學(xué)到的一些經(jīng)驗

5、教訓(xùn)。最后第10節(jié)描述了相關(guān)工作，第11節(jié)進行了總結(jié)。2.數(shù)據(jù)模型Bigtable是一個稀疏的，分布式的一致性多維有序map。這個map是通過行關(guān)鍵字，列關(guān)鍵字以及時間戳進行索引的；map中的每個值都是一個未經(jīng)解釋的字節(jié)數(shù)組。(row：string,column：string,time：int64)-string我們在對于這種類Bigtable系統(tǒng)的潛在使用場景進行了大量考察后，最終確定了這個數(shù)據(jù)模型。舉一個影響到我們的某些設(shè)計決策的具體例子，比如我們想保存一份可以被很多工程使用的一大集網(wǎng)頁及其相關(guān)信息的拷貝。我們把這個表稱為webtable，在這個表中，我們可以使用URL作為行關(guān)鍵字，網(wǎng)頁的

6、各種信息作為列名稱，將網(wǎng)頁的內(nèi)容作為表的內(nèi)容存儲：獲取的時候還需要在列上加上時間戳，如圖1所示。表中的行關(guān)鍵字是大字符串(目前最大可以到64KB，盡管對于大多數(shù)用戶來說最常用的是10-100字節(jié))。在一個行關(guān)鍵字下的數(shù)據(jù)讀寫是原子性的(無論這一行有多少個不同的列被讀寫)，這個設(shè)計使得用戶在對相同行的并發(fā)更新出現(xiàn)時，更容易理解系統(tǒng)的行為。Bigtable按照行關(guān)鍵字的字典序來維護數(shù)據(jù)。行組row range，將它翻譯為行組，一個row range可能由多個行組成是可以動態(tài)劃分的。每個行組叫做一個tablet，是數(shù)據(jù)存放以及負載平衡的單位。這樣，對于一個短的行組的讀就會很有效，而且只需要與少數(shù)的機

7、器進行通信。客戶端可以通過選擇行關(guān)鍵字來利用這個屬性，這樣它們可以為數(shù)據(jù)訪問得到好的局部性。比如，在webtable里，相同域名的網(wǎng)頁可以通過將URL中的域名反轉(zhuǎn)而使他們放在連續(xù)的行里來組織到一塊。比如我們將網(wǎng)頁/index.html的數(shù)據(jù)存放在關(guān)鍵字com.google.maps/index.html下。將相同域名的網(wǎng)頁存儲在鄰近位置可以使對主機或域名的分析更加有效。列族不同的列關(guān)鍵字可以被分組到一個集合，我們把這樣的一個集合稱為一個列族，它是基本的訪問控制單元。存儲在同一個列族的數(shù)據(jù)通常是相同類型的(我們將同一列族的數(shù)據(jù)壓縮在一塊)。在數(shù)據(jù)能夠存儲到某個列族的

8、列關(guān)鍵字下之前，必須首先要創(chuàng)建該列族。我們假設(shè)在一個表中不同列族的數(shù)目應(yīng)該比較小(最多數(shù)百個)，而且在操作過程中這些列族應(yīng)該很少變化。與之相比，一個表的列數(shù)目可以沒有限制。一個列關(guān)鍵字是使用如下的字符來命名的：family：qualifier。列族名稱必須是可打印的，但是qualifier可能是任意字符串。比如webtable有一個列族是language，它存儲了網(wǎng)頁所使用的語言。在language列族里，我們只使用了一個列關(guān)鍵字，里面存儲了每個網(wǎng)頁的language id。該表的另一個列族是anchor，在該列族的每個列關(guān)鍵字代表一個單獨的anchor，如圖1所示。Qualifier是站點的

9、名稱，里面的內(nèi)容是鏈接文本。訪問控制以及磁盤的內(nèi)存分配都是在列族級別進行的。在webtable這個例子中，這些控制允許我們管理不同類型的應(yīng)用：一些可能會添加新的基礎(chǔ)數(shù)據(jù)，一些可能讀取這些基礎(chǔ)數(shù)據(jù)來創(chuàng)建新的列族，一些可能只需要查看現(xiàn)有數(shù)據(jù)(甚至可能因為隱私策略不需要查看所有現(xiàn)有數(shù)據(jù))。時間戳Bigtable里的每個cell可以包含相同數(shù)據(jù)的多個版本；這些不同的版本是通過時間戳索引的。Bigtable的時間戳是一個64位的整數(shù)。它們可以由Bigtable來賦值，在這種情況下它們以毫秒來代表時間。也可以由客戶端應(yīng)用程序顯式分配。應(yīng)用程序為了避免沖突必須能夠自己生成唯一的時間戳。一個cell的不同版本

10、是按照時間戳降序排列，這樣最近的版本可以被首先讀到。為了使不同版本的數(shù)據(jù)管理更簡單，我們支持2個針對每個列族的設(shè)定來告訴Bigtable可以對cell中的數(shù)據(jù)版本進行自動的垃圾回收。用戶可以指定最近的哪幾個版本需要保存，或者保存那些足夠新的版本(比如只保存那些最近7天寫的數(shù)據(jù))。在我們的webtable中，我們將爬取的網(wǎng)頁的時間戳存儲在內(nèi)容里：這些時間說明了這些網(wǎng)頁的不同版本分別是在何時被抓取的。前面描述的垃圾回收機制，使我們只保存每個網(wǎng)頁最新的三個版本。3.API Bigtable API提供了一些函數(shù)用于表及列族的創(chuàng)建和刪除。它也提供了一些用于改變集群，表格及列族元數(shù)據(jù)的函數(shù)，比如訪問控制

11、權(quán)限?？蛻舳藨?yīng)用程序可以寫或者刪除Bigtable里的值，從行里查找值或者在表中的一個數(shù)據(jù)子集中進行迭代。圖2展示了使用RowMutation執(zhí)行一系列更新的C+代碼(為了保持簡單省略了不相關(guān)的細節(jié))。Apply調(diào)用對webtable執(zhí)行了一個原子性的變更操作：給增加一個anchor，然后刪除另一個anchor。圖3展示的c+代碼使用Scanner來在一個特殊行上的所有anchor進行迭代，用戶可以在多個列族上進行迭代，存在幾種機制來對掃描到的行，列，時間戳進行過濾。比如我們可以限制只掃描那些與正則表達式anchor：*.匹配的列，或者那些時間戳距離當前時間10天以內(nèi)的ancho

12、r。Bigtable提供了幾種其他的feature允許用戶使用更復(fù)雜的方式熟練控制數(shù)據(jù)。首先，Bigtable支持單行事務(wù)，能夠支持對存儲在一個行關(guān)鍵字上的執(zhí)行原子性的讀寫修改序列。Bigtable當前并不支持跨行的事務(wù)，盡管它提供了一個多個用戶的跨行寫的接口。其次，Bigtable允許用戶將cell作為一個整數(shù)計數(shù)器來使用。最后，Bigtable支持在服務(wù)器地址空間內(nèi)執(zhí)行一個客戶端腳本。這些腳本是使用google內(nèi)部開發(fā)的數(shù)據(jù)處理語言sawzall編寫的。當前，我們基于Sawzall的API不允許客戶端腳本向Bigtable中寫回，但是它允許進行各種形式的數(shù)據(jù)轉(zhuǎn)換，基于各種表達式的過濾以及大

13、量的統(tǒng)計操作符。Bigtable可以與MapReduce(google內(nèi)部開發(fā)的一個運行大規(guī)模并行程序的框架)一起使用。我們寫了很多wrapper它允許將Bigtable作為輸入源或者輸出目標。4.基礎(chǔ)構(gòu)件Bigtable是建立在google的其他幾個設(shè)施之上。Bigtable使用GFS來存儲日志和數(shù)據(jù)文件。Bigtable集群通常運行在一個運行著大量其他分布式應(yīng)用的共享機器池上。Bigtable依賴于一個集群管理系統(tǒng)進行job調(diào)度，共享機器上的資源管理，處理機器失敗以及監(jiān)控機器狀態(tài)。Bigtable內(nèi)部采用Google SSTable文件格式來存儲數(shù)據(jù)。一個SSTable提供了一個一致性的，

14、有序的從key到value的不可變map，key和value都是任意的字節(jié)串。操作通常是通過一個給定的key來查找相應(yīng)的value，或者在一個給定的key range上迭代所有的key/value對。每個SSTable內(nèi)部包含一系列的塊(通常每個塊是64KB大小，但是該大小是可配置的)。一個塊索引(保存在SSTable的尾部)是用來定位block的，當SSTable打開時該索引會被加載到內(nèi)存。一次查找可以通過一次磁盤訪問完成：首先通過在內(nèi)存中的索引進行一次二分查找找到相應(yīng)的塊，然后從磁盤中讀取該塊。另外，一個SSTable可以被完全映射到內(nèi)存，這樣就不需要我們接觸磁盤就可以執(zhí)行所有的查找和掃描

15、。關(guān)于SSTable(StaticSearchTable)的具體格式可以參考YunTable開發(fā)日記(4)-BigTable的存儲模型，中對HBASE的HFile的介紹Bigtable依賴于一個高可用的一致性分布式鎖服務(wù)Chubby。Chubby由5個活動副本組成，其中的一個選為master處理請求。當大部分的副本運行并且可以相互通信時，該服務(wù)就是活的。Chubby使用Paxos算法來在出現(xiàn)失敗時，保持副本的一致性。Chubby提供了一個由目錄和小文件組成的名字空間。每個文件或者目錄可以當作一個鎖來使用，對于一個文件的讀寫是原子性的。Chubby的客戶端庫為Chubby文件提供一致性緩存。每個

16、Chubby客戶端維護這一個與Chubby服務(wù)的會話。如果在租約有效時間內(nèi)無法更新會話的租約，客戶端的會話就會過期。當一個客戶端會話過期后，它會丟失所有的鎖和打開的文件句柄。Chubby客戶端也會在Chubby文件和目錄上注冊回調(diào)函數(shù)來處理這些變更或者會話的過期。Bigtable使用Chubby來完成各種任務(wù)：保證任意時刻最多只有一個活動的master；存儲Bigtable數(shù)據(jù)的bootstrap location(參見5.2節(jié))；發(fā)現(xiàn)tablet服務(wù)器以及finalize tablet服務(wù)器的死亡(參見5.2節(jié))；保存Bigtable schema信息(每個表的列族信息)；存儲訪問控制列表。

17、如果chubby在一段時間內(nèi)不可用，Bigtable也會不可用。我們最近在使用了11個chubby實例的14個Bigtable集群進行了測量。由于Chubby不可用而造成的存儲在Bigtable上的數(shù)據(jù)不可用的平均概率是0.0047%。對于單個集群來說，由于Chubby不可用造成的這個概率是0.0326%。5.實現(xiàn)Bigtable實現(xiàn)有3個主要的組件：每個客戶端需要鏈接的庫，一個master服務(wù)器，很多tablet服務(wù)器。tablet服務(wù)器可以從一個集群中動態(tài)添加(或者刪除)來適應(yīng)工作負載的動態(tài)變化。Master負責將tablet分配到tablet服務(wù)器，檢測tablet服務(wù)器的添加和過期，平

18、衡tablet服務(wù)器負載，GFS文件的垃圾回收。另外，它還會處理schema的變化，比如表和列族的創(chuàng)建。每個tablet服務(wù)器管理一個tablets集合(通常每個tablet服務(wù)器有10到1000個tablet)。Tablet服務(wù)器負責它已經(jīng)加載的那些tablet的讀寫請求，也會將那些過于大的tablet進行分割。tablet服務(wù)器本身實際上也是GFS的用戶，它們只是負載它加載的那些tablet的管理，這些tablet的物理存儲并不一定存放在管理它的服務(wù)器上，底層的存儲是由GFS完成的，tablet服務(wù)器可以只調(diào)用它的接口來完成相應(yīng)任務(wù)。而METADATA表中的位置信息應(yīng)該是指某個tablet

19、由哪個tablet服務(wù)器管理，而不是物理上存儲在哪個機器上。正如很多單master的分布式存儲系統(tǒng)，客戶端數(shù)據(jù)的移動并不會經(jīng)過master：客戶端直接與tablet服務(wù)器進行通信來進行讀寫。因為Bigtable客戶端并不依賴于master得到tablet的位置信息，大部分的客戶端從來不會于master通信。所以，master實際中通常都是負載很輕的。Bigtable集群存儲了大量的表。每個表由一系列的tablet組成，每個tablet包含一個行組的所有相關(guān)數(shù)據(jù)。一開始，每個表由一個tablet組成。隨著表格的增長，它會自動分割成多個tablet，它們大小默認是100-200MB。5.1 Tab

20、let存放位置我們使用一個類似于B+樹的三級結(jié)構(gòu)來存儲tablet的放置信息如圖4。第一級是一個存儲在Chubby的包含了root tablet位置信息的文件。root tablet包含了在一個特殊的METADATA表里的所有tablet的位置信息root tablet實際上是METADATA表的第一個tablet，它存儲了該表其他的tablet的位置信息。每個METADATA tablet包含了一集用戶tablet的位置。Root tablet僅僅是METADATA表的第一個tablet，但是是特殊對待的-它永遠不會被分割-為了保證tablet位置信息的層次結(jié)構(gòu)不會超過3級。METADATA

21、表的每一個行關(guān)鍵字(由tablet所屬的表標識符和它的結(jié)束行組成)下存儲了一個tablet的位置。每個METADATA行在內(nèi)存中大概存儲了1KB數(shù)據(jù)。我們限制METADATA的tablet的大小為128MB，我們的三級層次結(jié)構(gòu)足以用來尋址234個tablet(如果tablet按照128MB算，就是261字節(jié))root tablet大小為128M，每個行1KB，那么它就可以存儲128*220/210=128*210個METADATA tablet，同樣的，每個METADATA tablet可以存儲128*210個普通tablet，這樣總共可以存儲128*210*128*210即234個普通tab

22、let，每個tablet又將近1KB數(shù)據(jù)，這樣算起來存儲這些元信息就需要4TB的數(shù)據(jù)，所以該METADATA表也不可能全部放入內(nèi)存，而是采用與普通的表一樣的存儲方式，放在GFS上。但是會把某些特殊信息放在內(nèi)存中，比如第6節(jié)提到的：METADATA中的location列族會被放入內(nèi)存?？蛻舳藥鞎彺鎡ablet的位置信息。如果客戶端不知道某個tablet的信息，或者發(fā)現(xiàn)緩存的位置信息是錯誤的，那么它就會遞歸地在tablet位置存儲結(jié)構(gòu)中查找。如果客戶端緩存是空的，定位算法需要三次網(wǎng)絡(luò)往返，包括從Chubby的一次讀操作。如果客戶端緩存是陳舊的，定位算法將需要多達6次的往返，因為陳舊的緩存值只有在

23、不命中時才會被發(fā)現(xiàn)(假設(shè)METADATA tablet并不會經(jīng)常移動)。盡管Tablet位置信息是存儲在內(nèi)存中(如上所述)，不需要訪問GFS，但是我們還是通過在客戶端庫里進行預(yù)取來降低花費：當讀取METADATA表時，它會讀取不止一個tablet的信息。我們也會將一些額外信息存放在METADATA表里，包括對于每個tablet有關(guān)的事件日志(比如一個服務(wù)器何時開始提供服務(wù))。這些信息對于調(diào)試和性能分析很有幫助。5.2 tablet分配每個Tablet一次只會分配給一個tablet服務(wù)器。Master保存了現(xiàn)有的活著的tablet服務(wù)器集合的所有行蹤，tablet服務(wù)器當前分配的tablet，哪

24、些tablet未被分配。當一個tablet沒有被分配并且有一個可以存儲該tablet的tablet服務(wù)器存在時，master通過給那個tablet服務(wù)器發(fā)送一個tablet負載請求來分配該tablet。Bigtable使用Chubby來追蹤tablet服務(wù)器的狀態(tài)。當一個tablet服務(wù)器啟動時，它創(chuàng)建并獲取一個在給定的Chubby目錄上的唯一命名的文件的獨占鎖。Master通過監(jiān)控這個目錄(服務(wù)器目錄)來發(fā)現(xiàn)tablet服務(wù)器。Tablet服務(wù)器如果丟失了它的獨占鎖(比如由于網(wǎng)絡(luò)問題)就停止它上面的tablet服務(wù)。一個tablet服務(wù)器會嘗試重新獲取在該文件上的獨占鎖，只要該文件還存在。如

25、果該文件也不存在了，那么tablet服務(wù)器就永遠無法提供該服務(wù)了。當一個tablet服務(wù)器停止(比如集群管理系統(tǒng)從集群中刪除了該tablet服務(wù)器機器)，它就會嘗試釋放這個鎖這樣master就可以更快地重新分配它上面的tablets了。Master負責檢測一個tablet服務(wù)器何時停止提供服務(wù)，以盡快重新安排它的tablets。為了進行檢測，master周期性的向每個tablet服務(wù)器詢問它的鎖狀態(tài)。如果一個tablet服務(wù)器報告它丟失了它的鎖，或者master在它的幾次嘗試中不能到達一個服務(wù)器，master會嘗試獲取該服務(wù)器的鎖。如果master可以獲取該鎖，那么Chubby就是活的，而ta

26、blet服務(wù)器要么是死的要么因為某些問題而無法到達Chubby，那么master就可以通過刪除它的server文件來使得該tablet服務(wù)器永遠都不能提供服務(wù)。一旦一個服務(wù)器的文件被刪除了，master就可以將之前分配給該服務(wù)器的所有tablet移到那些為分配的tablet集合中。為了保證一個Bigtable集群不會因為與master和Chubby間的網(wǎng)絡(luò)問題而變得脆弱，如果master的Chubby會話過期了，master會自殺。然而，如前面所述，master的失敗并不會改變tablet服務(wù)器的tablet分配。當master被集群管理系統(tǒng)啟動后，在它可以改變tablets之前需要知道它們當

27、前的分配狀態(tài)。Master在啟動時執(zhí)行如下步驟：1.master在Chubby獲得一個唯一的master鎖，該鎖可以防止出現(xiàn)同時生成多個master實例。2.master掃描Chubby的服務(wù)器目錄來找到所有活著的服務(wù)器。3.master與活著的tablet服務(wù)器通信來發(fā)現(xiàn)每個服務(wù)器安排了哪些tablet。4.master掃描METADATA表來找到tablet集合。當掃描中碰到一個未被分配的tablet，master會將它添加到未分配的tablet集合，并對這個tablet進行分配。在METADATA的tablets未被分配之前，對于METADATA的掃描不能進行。因此在開始掃描之前(步驟4

28、)，如果在步驟3沒有發(fā)現(xiàn)對于root tablet的分配，master會將root tablet添加到未分配tablets集合中。這個添加將會使root tablet變得可以被分配。因為root tablet包含所有METADATA tablets的名稱，master當掃描完root tablet后就能知道METADATA的所有的tablets。只有當一個表被創(chuàng)建，現(xiàn)有的兩個tablets合并為一個，或者一個tablet被分割為一個時，現(xiàn)有的tablet集合才會發(fā)生變化。Master能夠追蹤所有的這些變化，因為它負責維護它們。Tablet分割需要特殊對待因為它們是由一個tablet服務(wù)器啟動的

29、。Tablet服務(wù)器通過將新的tablet的信息記錄到METADATA表中來提交這個分割。當分割提交后，它會通知master。為了防止分割通知丟失(因為tablet服務(wù)器或者master死了)，當master向tablet服務(wù)器請求加載剛剛發(fā)生分割的那個tablet時，它會檢測到這個新的tablet。Tablet服務(wù)器會將這個分割通知master，因為它在METADATA表中的tablet鍵值僅包含了master讓它加載的那個tablet的一部分。假設(shè)master沒有收到這個分割通知，那么它所記錄的tablet與METADATA表中的就是不一致的，這樣在它讓tablet服務(wù)器加載該tablet

30、時就會發(fā)現(xiàn)該不一致。5.3 tablet服務(wù)Tablet的持久性狀態(tài)是通過GFS進行存儲的，如圖5所示。更新是提交到一個保存了redo記錄的提交日志里。在這些更新里，最近提交的那些被保存到內(nèi)存中一個叫做memtable的有序緩存里，老的更新則被保存在一系列的SSTable中。為了恢復(fù)一個tablet，tablet服務(wù)器從METADATA表中讀取該tablet的元數(shù)據(jù)。元數(shù)據(jù)中包含組成該tablet的SSTable列表，以及一系列的redo點(指向那些包含該tablet數(shù)據(jù)的commit日志條目)的集合。Tablet服務(wù)器將所有SSTable的索引讀入內(nèi)存，然后通過應(yīng)用那些從redo點開始以及提

31、交的更新操作來重新構(gòu)建memtable。更新操作肯定會被保存到commit log里，但是當某個服務(wù)器掛掉時，它那些保存在memtable的最新的更新就不存在了，而redo點應(yīng)該就是記錄已保存到SSTable的與還在memtable中的操作的分界點，這樣通過重新執(zhí)行它之后的那些操作就可以將memtable重建redo點何時被更新?有多少個commit log?參見第6節(jié)當一個寫操作到達一個tablet服務(wù)器時，服務(wù)器首先檢查它的格式是否合法，發(fā)送者是否有權(quán)限進行該操作。權(quán)限檢查是通過從Chubby讀取一個允許的寫操作者列表(通常它直接存在于Chubby的客戶端緩存中)完成的。一個合法的變更會被

32、寫入到已提交日志里。操作的提交可以通過分組執(zhí)行來提高大量小變更操作出現(xiàn)時的吞吐率，當該寫操作提交后，它的內(nèi)容會被插入到memtable里。當一個讀操作到達一個tablet服務(wù)器時，類似的首先要進行格式和權(quán)限檢查。一個合法的讀操作將會在一系列SSTable和memtable的一個合并視圖上執(zhí)行因為SSTable一旦寫入就不可變，這樣就使得更新操作必須寫到新的SSTable中，這樣就導(dǎo)致同一個key值可能在多個SSTable中出現(xiàn)，這樣讀取時就必須讀取多個SSTable才能得到它真實的最終狀態(tài)。因為SSTable和memtable都是字典有序的數(shù)據(jù)結(jié)構(gòu)，因此可以很快生成這個視圖。為了讀取一個key

33、時，要讀入所有的SSTable，所以第6節(jié)有一個針對該問題的優(yōu)化Bloom Filter。此外伴隨著SSTable的增多，這種視圖合并也會變得低效，所以也引出了下面的Compation當tablet發(fā)生分割或者合并時，也可以繼續(xù)接受讀寫操作。5.4 compaction伴隨著寫操作的執(zhí)行，memtable的大小會逐漸變大。當memtable大小增長到一個閾值，這個memtable就會被凍結(jié)，一個新的memtable被創(chuàng)建，被凍結(jié)的舊的memtable會被轉(zhuǎn)化為一個SSTable寫入GFS。這個minor compaction過程有兩個目的：降低tablet server的內(nèi)存使用，降低該tab

34、let服務(wù)器掛掉時需要從已提交日志中讀取的數(shù)據(jù)大小。當compaction發(fā)生時，也可以繼續(xù)接受讀寫操作。每次minor Compation會創(chuàng)建一個新的SSTable。如果這個行為持續(xù)的進行而不檢查，那么讀操作就可能會需要從大量的SSTable中合并它們的更新。我們通過周期性的執(zhí)行一個merging compaction來將這樣的文件數(shù)目限制在一定范圍內(nèi)。一個merging compaction讀取多個SStable和memtable，然后寫入到一個新的SSTable(形成一個最終的歸并視圖)。一旦這個compaction結(jié)束，這些SSTable和memtable就可以丟棄了。將多個SSTa

35、ble重新寫入到一個SSTable的merging compaction稱為主compaction。由非主compaction產(chǎn)生的SSTable里可以包含一些在舊的SSTable中仍然存活但是目前已經(jīng)被刪除的數(shù)據(jù)。另一方面，一個主compaction產(chǎn)生的SSTable不會包含刪除操作信息或者已刪除數(shù)據(jù)。Bigtable循環(huán)掃描它所有的tablet，周期的對它們執(zhí)行主compaction。這些主compaction使得Bigtable可以回收那些被已刪除的數(shù)據(jù)使用的資源。這也保證那些已經(jīng)刪除的數(shù)據(jù)在一定時間內(nèi)會從系統(tǒng)中消失，這對于那些存儲敏感數(shù)據(jù)的服務(wù)來說很重要。6技巧前面一節(jié)描述的實現(xiàn)需要

36、大量的技巧來到達用戶所需要的高性能，可用性，可靠性。這一節(jié)更細節(jié)地描述下實現(xiàn)的各個部分，著重講述下使用的這些技巧。局部性群組(對應(yīng)一個SSTable)用戶可以將多個列族組織為一個局部性群組。對于每個tablet里的每個局部性群組都會生成一個單獨的SSTable。將那些通常不會被一起訪問的列族分離到獨立的局部性群組可以增加訪問的效率。比如，webtable的關(guān)于網(wǎng)頁的元數(shù)據(jù)(比如語言，校驗和)可放到一個局部性群組，網(wǎng)頁內(nèi)容可以放到另一個群組里：這樣一個訪問元數(shù)據(jù)的應(yīng)用程序就不需要讀取所有網(wǎng)頁的內(nèi)容。另外，一些有用的tuning參數(shù)也可以以局部性群組為單位進行設(shè)置。比如一個局部性群組可以聲明為放入

37、內(nèi)存的。對于聲明為放入內(nèi)存的局部性群組的SSTable在需要時才會加載到tablet服務(wù)器的內(nèi)存中。一旦加載之后，對于該局部性群組的訪問就不需要訪問磁盤。這個特點對于那些需要經(jīng)常訪問的小片數(shù)據(jù)很有用：比如在Bigtable內(nèi)部我們將它應(yīng)用在METADATA表的location列族上。壓縮用戶可以控制對于一個局部性群組的SSTables是否進行壓縮，以及使用哪種壓縮格式。用戶指定的壓縮格式會應(yīng)用在SSTable的每個塊上(塊大小可以通過一個局部性群組的參數(shù)進行控制)。對于每個塊單獨進行壓縮，盡管這使我們丟失了一些空間，但是這使得我們不需要解壓整個文件就可以讀取SSTable的部分內(nèi)容。很多用戶使

38、用一個兩遍壓縮模式，第一遍壓縮使用Bentley and McIlroy模式，該模式在一個很大的窗口大小里壓縮普通的長字符串。第二遍壓縮了一個快速壓縮算法，該算法在一個小的16KB窗口大小內(nèi)查找重復(fù)。這兩遍壓縮都很快速，壓縮速率在100-200MB/s，解壓速率在400-1000MB/s。盡管在選擇壓縮算法時，我們更重視速率而不是空間的減少，但是這個兩遍壓縮模式或做的出奇地好。比如，在webtable里我們使用這種壓縮模式存儲網(wǎng)頁內(nèi)容。實驗中，我們在一個壓縮的局部性群組里存儲了大量文檔。為了實驗?zāi)康?，我們將文檔的版本數(shù)限制為1。該壓縮模式達到了10：1的壓縮率。這比通常的Gzip對于HTML網(wǎng)

39、頁的3：1或4：1的壓縮率要好多了。這是由我們的webtable的行分布方式造成的：來自相同主機的網(wǎng)頁被存儲在相鄰的位置。這使Bentley and McIlroy算法可以識別出來自相同站點的大量固有模式。很多應(yīng)用程序，不僅僅是webtable，選擇的行名稱使得類似數(shù)據(jù)會聚集在一起，因此達到了很好的壓縮率。當我們在Bigtable中存儲相同值的多個版本時壓縮率會更好。為了讀性能進行緩存為了提高讀性能，tablet服務(wù)器使用一個二級緩存。掃描緩存是一個用來緩存由SSTable返回給tablet服務(wù)器的key-value對的高級緩存。塊緩存是用來緩存從GFS讀取的SSTable塊的低級緩存。掃描緩

40、存主要用于那些傾向于重復(fù)讀取相同數(shù)據(jù)的應(yīng)用，塊緩存則用于那些傾向于從最近讀取的數(shù)據(jù)的鄰近位置讀取數(shù)據(jù)的應(yīng)用(比如順序讀，或者讀取一個熱點行內(nèi)的相同局部性群組里的不同列值)。Bloom Filters正如5.3節(jié)所描述的，一個讀操作需要從組成該tablet的所有SSTable里讀取。如果這些SSTable不在內(nèi)存，就需要很多磁盤操作。通過讓用戶為某個局部性群組的SSTables指定對應(yīng)的Bloom filters，可以降低磁盤訪問次數(shù)。一個Bloom Filter允許我們查詢對應(yīng)的SSTable是否包含某個給定的row/column對的數(shù)據(jù)。對于特定的應(yīng)用程序來說，只需要很少的tablet服務(wù)器

41、內(nèi)存來保存Bloom Filter，但可以大大減少讀操作所需要的磁盤操作。同時Bloom Filter可以避免那些對于不存在的行列的查找訪問磁盤。提交日志實現(xiàn)如果我們?yōu)槊總€tablet的提交日志建立一個獨立的日志文件，就會使得大量的文件需要并發(fā)寫入GFS。由于每個GFS服務(wù)器的底層文件系統(tǒng)實現(xiàn)，這些寫操作會引起在不同物理日志文件上的大量的磁盤尋道。另外，每個tablet一個日志文件會降低分組提交優(yōu)化的效率。為了解決這些問題，每個tablet服務(wù)器將更新操作append一個日志文件里，將對于不同的tablet的變更放到同一個物理日志文件里。使用一個日志為正常操作提供了很明顯的性能好處，但是使恢復(fù)

42、變復(fù)雜了。當一個tablet服務(wù)器掛掉后，它負責的那些tablet需要移動到大量其他的tablet服務(wù)器上：每個服務(wù)器通常都會加載一些該服務(wù)器的tablet。為了恢復(fù)一個tablet的狀態(tài)，新的tablet服務(wù)器需要通過原來那個tablet服務(wù)器的提交日志重新應(yīng)用這個tablet的變更操作。然而對于這些tablet的變更是混在同一個日志文件里的。一種方法是，每個新的tablet服務(wù)器全部讀取這個日志文件，然后僅應(yīng)用那些它需要恢復(fù)的tablet的變更操作。然而，在這種模式下，如果失敗的那臺tablet服務(wù)器的tablet被分配到了100個機器，那么這個日志文件就需要讀取100次。我們通過對提交日志里的entry根據(jù)table,row name,log sequence number進行排序避免了重復(fù)的日志讀取。在已排序的輸出中，對于一個tablet的所有變更都是連續(xù)的，因此可以通過一次的磁盤尋道和順序讀操