大表(Bigtable):結(jié)構(gòu)化數(shù)據(jù)的分布存儲(chǔ)系統(tǒng)
http://labs.google.com/papers/bigtable-osdi06.pdf
｛中是譯者評(píng)論,程序除外｝
{本文的翻譯可能有不準(zhǔn)確的地方,詳細(xì)資料請(qǐng)參考原文.}
摘要
bigtable是設(shè)計(jì)來(lái)分布存儲(chǔ)大規(guī)模結(jié)構(gòu)化數(shù)據(jù)的，從設(shè)計(jì)上它可以擴(kuò)展到上２^50字節(jié)，分布存儲(chǔ)在幾千個(gè)普通服務(wù)器上．Ｇoogle的很多項(xiàng)目使用ＢＴ來(lái)存儲(chǔ)數(shù)據(jù)，包括網(wǎng)頁(yè)查詢，google earth和google金融．這些應(yīng)用程序?qū)Γ拢缘囊蟾鞑幌嗤簲?shù)據(jù)大?。◤腢RL到網(wǎng)頁(yè)到衛(wèi)星圖象）不同，反應(yīng)速度不同（從后端的大批處理到實(shí)時(shí)數(shù)據(jù)服務(wù)）．對(duì)于不同的要求，ＢＴ都成功的提供了靈活高效的服務(wù)．在本文中，我們將描述ＢＴ的數(shù)據(jù)模型．這個(gè)數(shù)據(jù)模型讓用戶動(dòng)態(tài)的控制數(shù)據(jù)的分布和結(jié)構(gòu)．我們還將描述ＢＴ的設(shè)計(jì)和實(shí)現(xiàn)．
１．介紹
在過(guò)去兩年半里，我們?cè)O(shè)計(jì)，實(shí)現(xiàn)并部署了ＢＴ．ＢＴ是用來(lái)分布存儲(chǔ)和管理結(jié)構(gòu)化數(shù)據(jù)的．ＢＴ的設(shè)計(jì)使它能夠管理2^50 bytes(petabytes)數(shù)據(jù)，并可以部署到上千臺(tái)機(jī)器上．ＢＴ完成了以下目標(biāo)：應(yīng)用廣泛，可擴(kuò)展，高性能和高可用性（high availability）. 包括google analytics, google finance, orkut, personalized search, writely和google earth在內(nèi)的60多個(gè)項(xiàng)目都使用BT.這些應(yīng)用對(duì)ＢＴ的要求各不相同，有的需要高吞吐量的批處理，有的需要快速反應(yīng)給用戶數(shù)據(jù)．它們使用的ＢＴ集群也各不相同，有的只有幾臺(tái)機(jī)器，有的有上千臺(tái)，能夠存儲(chǔ)2^40字節(jié)(terabytes)數(shù)據(jù)．
ＢＴ在很多地方和數(shù)據(jù)庫(kù)很類似：它使用了很多數(shù)據(jù)庫(kù)的實(shí)現(xiàn)策略．并行數(shù)據(jù)庫(kù)［１４］和內(nèi)存數(shù)據(jù)庫(kù)［１３］有可擴(kuò)展性和高性能，但是ＢＴ的界面不同．ＢＴ不支持完全的關(guān)系數(shù)據(jù)模型；而是為客戶提供了簡(jiǎn)單的數(shù)據(jù)模型，讓客戶來(lái)動(dòng)態(tài)控制數(shù)據(jù)的分布和格式{就是只存儲(chǔ)字串，格式由客戶來(lái)解釋}，并允許客戶推斷底層存儲(chǔ)數(shù)據(jù)的局部性｛以提高訪問(wèn)速度｝．?dāng)?shù)據(jù)下標(biāo)是行和列的名字，數(shù)據(jù)本身可以是任何字串．ＢＴ的數(shù)據(jù)是字串，沒有解釋｛類型等｝．客戶會(huì)在把各種結(jié)構(gòu)或者半結(jié)構(gòu)化的數(shù)據(jù)串行化｛比如說(shuō)日期串｝到數(shù)據(jù)中．通過(guò)仔細(xì)選擇數(shù)據(jù)表示，客戶可以控制數(shù)據(jù)的局部化．最后，可以使用ＢＴ模式來(lái)控制數(shù)據(jù)是放在內(nèi)存里還是在硬盤上．｛就是說(shuō)用模式，你可以把數(shù)據(jù)放在離應(yīng)用最近的地方．畢竟程序在一個(gè)時(shí)間只用到一塊數(shù)據(jù)．在體系結(jié)構(gòu)里，就是：locality, locality, locality｝
第二節(jié)描述數(shù)據(jù)模型細(xì)節(jié)．第三節(jié)關(guān)于客戶ＡＰＩ概述．第四節(jié)簡(jiǎn)介ＢＴ依賴的google框架．第五節(jié)描述ＢＴ的實(shí)現(xiàn)關(guān)鍵部分．第6節(jié)敘述提高ＢＴ性能的一些調(diào)整．第7節(jié)提供ＢＴ性能的數(shù)據(jù)．在第8節(jié)，我們提供ＢＴ的幾個(gè)使用例子，第9節(jié)是經(jīng)驗(yàn)教訓(xùn)．在第10節(jié)，我們列出相關(guān)研究．最后是我們的結(jié)論．
２．?dāng)?shù)據(jù)模型
ＢＴ是一個(gè)稀疏的，長(zhǎng)期存儲(chǔ)的｛存在硬盤上｝，多維度的，排序的映射表．這張表的索引是行關(guān)鍵字，列關(guān)鍵字和時(shí)間戳．每個(gè)值是一個(gè)不解釋的字符數(shù)組．｛數(shù)據(jù)都是字符串，沒類型，客戶要解釋就自力更生吧｝．
(row:string, column:string,time:int64)->string {能編程序的都能讀懂，不翻譯了}
//彼岸翻譯的第二節(jié)
我們仔細(xì)查看過(guò)好些類似bigtable的系統(tǒng)之后定下了這個(gè)數(shù)據(jù)模型。舉一個(gè)具體例子（它促使我們做出某些設(shè)計(jì)決定）， 比如我們想要存儲(chǔ)大量網(wǎng)頁(yè)及相關(guān)信息，以用于很多不同的項(xiàng)目；我們姑且叫它Webtable。在Webtable里，我們將用URL作為行關(guān)鍵字，用網(wǎng)頁(yè)的某些屬性作為列名，把網(wǎng)頁(yè)內(nèi)容存在contents:列中并用獲取該網(wǎng)頁(yè)的時(shí)間戳作為標(biāo)識(shí)，如圖一所示。
圖一：一個(gè)存儲(chǔ)Web網(wǎng)頁(yè)的范例列表片斷。行名是一個(gè)反向URL｛即com.cnn.www｝。contents列族｛原文用 family，譯為族，詳見列族｝存放網(wǎng)頁(yè)內(nèi)容，anchor列族存放引用該網(wǎng)頁(yè)的錨鏈接文本。CNN的主頁(yè)被Sports Illustrater｛即所謂SI，CNN的王牌體育節(jié)目｝和MY-look的主頁(yè)引用，因此該行包含了名叫“anchor:cnnsi.com”和 “anchhor:my.look.ca”的列。每個(gè)錨鏈接只有一個(gè)版本｛由時(shí)間戳標(biāo)識(shí)，如t9，t8｝；而contents列則有三個(gè)版本，分別由時(shí)間 戳t3，t5，和t6標(biāo)識(shí)。
行
表中的行關(guān)鍵字可以是任意字符串（目前支持最多64KB，多數(shù)情況下10－100字節(jié)足夠了）。在一個(gè)行關(guān)鍵字下的每一個(gè)讀寫操作都是原子操作（不管讀寫這一行里多少個(gè)不同列），這是一個(gè)設(shè)計(jì)決定，這樣在對(duì)同一行進(jìn)行并發(fā)操作時(shí)，用戶對(duì)于系統(tǒng)行為更容易理解和掌控。
Bigtable通過(guò)行關(guān)鍵字的字典序來(lái)維護(hù)數(shù)據(jù)。一張表可以動(dòng)態(tài)劃分成多個(gè)連續(xù)行。連續(xù)行在這里叫做“子表”｛tablet｝，是數(shù)據(jù)分布和負(fù)載均衡的單位。這樣一來(lái)，讀較少的連續(xù)行就比較有效率，通常只需要較少機(jī)器之間的通信即可。用戶可以利用這個(gè)屬性來(lái)選擇行關(guān)鍵字，從而達(dá)到較好數(shù)據(jù)訪問(wèn)地域性｛locality｝。舉例來(lái)說(shuō)，在Webtable里，通過(guò)反轉(zhuǎn)URL中主機(jī)名的方式，可以把同一個(gè)域名下的網(wǎng)頁(yè)組織成連續(xù)行。具體來(lái)說(shuō)，可以把maps.google.com/index.html中的數(shù)據(jù)存放在關(guān)鍵字com.google.maps/index.html下。按照相同或?qū)傩韵嘟挠蛎麃?lái)存放網(wǎng)頁(yè)可以讓基于主機(jī)和基于域名的分析更加有效。
列族
一組列關(guān)鍵字組成了“列族”，這是訪問(wèn)控制的基本單位。同一列族下存放的所有數(shù)據(jù)通常都是同一類型（同一列族下的數(shù)據(jù)可壓縮在一起）。列族必須先創(chuàng)建，然后在能在其中的列關(guān)鍵字下存放數(shù)據(jù)；列族創(chuàng)建后，族中任何一個(gè)列關(guān)鍵字均可使用。我們希望，一張表中的不同列族不能太多（最多幾百個(gè)），并且列族在運(yùn)作中絕少改變。作為對(duì)比，一張表可以有無(wú)限列。
列關(guān)鍵字用如下語(yǔ)法命名：列族：限定詞。 列族名必須是看得懂｛printable｝的字串，而限定詞可以是任意字符串。比如，Webtable可以有個(gè)列族叫l(wèi)anguage，存放撰寫網(wǎng)頁(yè)的語(yǔ)言。我們?cè)趌anguage列族中只用一個(gè)列關(guān)鍵字，用來(lái)存放每個(gè)網(wǎng)頁(yè)的語(yǔ)言標(biāo)識(shí)符。該表的另一個(gè)有用的列族是anchor；給列族的每一個(gè)列關(guān)鍵字代表一個(gè)錨鏈接，如圖一所示。而這里的限定詞則是引用該網(wǎng)頁(yè)的站點(diǎn)名；表中一個(gè)表項(xiàng)存放的是鏈接文本。
訪問(wèn)控制，磁盤使用統(tǒng)計(jì)，內(nèi)存使用統(tǒng)計(jì)，均可在列族這個(gè)層面進(jìn)行。在Webtable舉例中，我們可以用這些控制來(lái)管理不同應(yīng)用：有的應(yīng)用添加新的基本數(shù)據(jù)，有的讀取基本數(shù)據(jù)并創(chuàng)建引申的列族，有的則只能瀏覽數(shù)據(jù)（甚至可能因?yàn)殡[私權(quán)原因不能瀏覽所有數(shù)據(jù)）。
時(shí)間戳
Bigtable表中每一個(gè)表項(xiàng)都可以包含同一數(shù)據(jù)的多個(gè)版本，由時(shí)間戳來(lái)索引。Bigtable的時(shí)間戳是64位整型。可以由Bigtable來(lái)賦值，表示準(zhǔn)確到毫秒的“實(shí)時(shí)”；或者由用戶應(yīng)用程序來(lái)賦值。需要避免沖突的應(yīng)用程序必須自己產(chǎn)生具有唯一性的時(shí)間戳。不同版本的表項(xiàng)內(nèi)容按時(shí)間戳倒序排列，即最新的排在前面。
為了簡(jiǎn)化對(duì)于不同數(shù)據(jù)版本的數(shù)據(jù)的管理，我們對(duì)每一個(gè)列族支持兩個(gè)設(shè)定，以便于Bigtable對(duì)表項(xiàng)的版本自動(dòng)進(jìn)行垃圾清除。用戶可以指明只保留表項(xiàng)的最后n個(gè)版本，或者只保留足夠新的版本（比如，只保留最近7天的內(nèi)容）。
在Webtable舉例中，我們?cè)赾ontents:列中存放確切爬行一個(gè)網(wǎng)頁(yè)的時(shí)間戳。如上所述的垃圾清除機(jī)制可以讓我們只保留每個(gè)網(wǎng)頁(yè)的最近三個(gè)版本。
//我開始翻譯3,4節(jié)
3.API
BT的ＡＰＩ提供了建立和刪除表和列族的函數(shù)．還提供了函數(shù)來(lái)修改集群，表和列族的元數(shù)據(jù)，比如說(shuō)訪問(wèn)權(quán)限．
// Open the table
Table *T = OpenOrDie(”/bigtable/web/webtable”);
// Write a new anchor and delete an old anchor
RowMutation r1(T, “com.cnn.www”);
r1.Set(”anchor:www.c-span.org”, “CNN”);
r1.Delete(”anchor:www.abc.com”);
Operation op;
Apply(&op, &r1);
圖 2: 寫入Bigtable.
在ＢＴ中，客戶應(yīng)用可以寫或者刪除值，從每個(gè)行中找值，或者遍歷一個(gè)表中的數(shù)據(jù)子集．圖2的Ｃ＋＋代碼是使用RowMutation抽象表示來(lái)進(jìn)行一系列的更新（為保證代碼精簡(jiǎn)，沒有包括無(wú)關(guān)的細(xì)節(jié)）．調(diào)用Apply函數(shù)，就對(duì)Ｗebtable進(jìn)行了一個(gè)原子修改：它為http://www.cnn.com/增加了一個(gè)錨點(diǎn)，并刪除了另外一個(gè)錨點(diǎn)．
Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily(”anchor”);
stream->SetReturnAllVersions();
scanner.Lookup(”com.cnn.www”);
for (; !stream->Done(); stream->Next()) {
printf(”%s %s %lld %s\n”,
scanner.RowName(),
stream->ColumnName(),
stream->MicroTimestamp(),
stream->Value());
}
圖3: 從Bigtable讀數(shù)據(jù).
圖3的Ｃ＋＋代碼是使用Scanner抽象來(lái)遍歷一個(gè)行內(nèi)的所有錨點(diǎn)．客戶可以遍歷多個(gè)列族．有很多方法可以限制一次掃描中產(chǎn)生的行，列和時(shí)間戳．例如，我們可以限制上面的掃描，讓它只找到那些匹配正則表達(dá)式*.cnn.com的錨點(diǎn)，或者那些時(shí)間戳在當(dāng)前時(shí)間前10天的錨點(diǎn)．
ＢＴ還支持其他一些更復(fù)雜的處理數(shù)據(jù)的功能．首先，ＢＴ支持單行處理．這個(gè)功能可以用來(lái)對(duì)存儲(chǔ)在一個(gè)行關(guān)鍵字下的數(shù)據(jù)進(jìn)行原子的讀-修改-寫操作．ＢＴ目前不支持跨行關(guān)鍵字的處理，但是它有一個(gè)界面，可以用來(lái)讓客戶進(jìn)行批量的跨行關(guān)鍵字處理操作．其次，ＢＴ允許把每個(gè)表項(xiàng)用做整數(shù)記數(shù)器．最后，ＢＴ支持在服務(wù)器的地址空間內(nèi)執(zhí)行客戶端提供的腳本程序．腳本程序的語(yǔ)言是google開發(fā)的Sawzall[28]數(shù)據(jù)處理語(yǔ)言．目前，我們基于的Sawzall的ＡＰＩ還不允許客戶腳本程序向ＢＴ內(nèi)寫數(shù)據(jù)，但是它允許多種形式的數(shù)據(jù)變換，基于任何表達(dá)式的過(guò)濾和通過(guò)多種操作符的摘要．
ＢＴ可以和MapReduce[12]一起使用．MapReduce是google開發(fā)的大規(guī)模并行計(jì)算框架．我們?yōu)榫帉懥艘惶淄鈱映绦?，使ＢＴ可以作為MapReduce處理的數(shù)據(jù)源頭和輸出結(jié)果．
4.建立ＢＴ的基本單元
ＢＴ是建立在其他數(shù)個(gè)google框架單元上的．ＢＴ使用google分布式文件系統(tǒng)(GFS)[17]來(lái)存儲(chǔ)日志和數(shù)據(jù)文件{yeah, right, what else can it use, FAT32?}．一個(gè)ＢＴ集群通常在一個(gè)共享的機(jī)器池中工作，池中的機(jī)器還運(yùn)行其他的分布式應(yīng)用{雖然機(jī)器便宜的跟白菜似的，可是一樣要運(yùn)行多個(gè)程序，命苦的象小白菜}，ＢＴ和其他程序共享機(jī)器｛ＢＴ的瓶頸是ＩＯ/內(nèi)存，可以和CPU要求高的程序并存｝．ＢＴ依賴集群管理系統(tǒng)來(lái)安排工作，在共享的機(jī)器上管理資源，處理失效機(jī)器并監(jiān)視機(jī)器狀態(tài)｛典型的server farm結(jié)構(gòu)，ＢＴ是上面的應(yīng)用之一｝．
ＢＴ內(nèi)部存儲(chǔ)數(shù)據(jù)的格式是google SSTable格式．一個(gè)SSTable提供一個(gè)從關(guān)鍵字到值的映射，關(guān)鍵字和值都可以是任意字符串．映射是排序的，存儲(chǔ)的｛不會(huì)因?yàn)榈綦姸鴣G失｝，不可改寫的．可以進(jìn)行以下操作：查詢和一個(gè)關(guān)鍵字相關(guān)的值；或者根據(jù)給出的關(guān)鍵字范圍遍歷所有的關(guān)鍵字和值．在內(nèi)部，每個(gè)SSTable包含一列數(shù)據(jù)塊（通常每個(gè)塊的大小是64KB,但是大小是可以配置的｛索引大小是16 bits，應(yīng)該是比較好的一個(gè)數(shù)｝）．塊索引（存儲(chǔ)在SSTable的最后）用來(lái)定位數(shù)據(jù)塊；當(dāng)打開SSTable的時(shí)候，索引被讀入內(nèi)存｛性能｝．每次查找都可以用一個(gè)硬盤搜索完成｛根據(jù)索引算出數(shù)據(jù)在哪個(gè)道上，一個(gè)塊應(yīng)該不會(huì)跨兩個(gè)道，沒必要省那么點(diǎn)空間｝：首先在內(nèi)存中的索引里進(jìn)行二分查找找到數(shù)據(jù)塊的位置，然后再?gòu)挠脖P讀去數(shù)據(jù)塊．最佳情況是：整個(gè)SSTable可以被放在內(nèi)存里，這樣一來(lái)就不必訪問(wèn)硬盤了．｛想的美，前面是誰(shuí)口口聲聲說(shuō)要跟別人共享機(jī)器來(lái)著？你把內(nèi)存占滿了別人上哪睡去？｝
ＢＴ還依賴一個(gè)高度可用的，存儲(chǔ)的分布式數(shù)據(jù)鎖服務(wù)Chubby[8]｛看你怎么把這個(gè)high performance給說(shuō)圓嘍｝．一個(gè)Chubby服務(wù)由5個(gè)活的備份｛機(jī)器｝構(gòu)成，其中一個(gè)被這些備份選成主備份，并且處理請(qǐng)求．這個(gè)服務(wù)只有在大多數(shù)備份都活著并且互相通信的時(shí)候才是活的｛繞口令？去看原文吧，是在有出錯(cuò)的前提下的冗余算法｝．當(dāng)有機(jī)器失效的時(shí)候，Chubby使用Paxos算法[9,23]來(lái)保證備份的一致性｛這個(gè)問(wèn)題還是比較復(fù)雜的，建議去看引文了解一下問(wèn)題本身｝．Chubby提供了一個(gè)名字空間，里面包括了目錄和小文件｛萬(wàn)變不離其宗｝．每個(gè)目錄或者文件可以當(dāng)成一個(gè)鎖來(lái)用，讀寫文件操作都是原子化的．Chubby客戶端的程序庫(kù)提供了對(duì)Chubby文件的一致性緩存｛究竟是提高性能還是降低性能？如果訪問(wèn)是分布的，就是提高性能｝．每個(gè)Chubby客戶維護(hù)一個(gè)和Chubby服務(wù)的會(huì)話．如果一個(gè)客戶不能在一定時(shí)間內(nèi)更新它的會(huì)話，這個(gè)會(huì)話就過(guò)期失效了｛還是針對(duì)大server farm里機(jī)器失效的頻率設(shè)計(jì)的｝．當(dāng)一個(gè)會(huì)話失效時(shí)，其擁有的鎖和打開的文件句柄都失效｛根本設(shè)計(jì)原則：失效時(shí)回到安全狀態(tài)｝．Chubby客戶可以在文件和目錄上登記回調(diào)函數(shù)，以獲得改變或者會(huì)話過(guò)期的通知．｛翻到這里，有沒有人聞到j(luò)ava的味道了？｝
ＢＴ使用Chubby來(lái)做以下幾個(gè)任務(wù)：保證任何時(shí)間最多只有一個(gè)活躍的主備份；來(lái)存儲(chǔ)ＢＴ數(shù)據(jù)的啟動(dòng)位置（參考5.1節(jié)）；發(fā)現(xiàn)小表（tablet）服務(wù)器，并完成tablet服務(wù)器消亡的善后（5.2節(jié)）；存儲(chǔ)ＢＴ數(shù)據(jù)的模式信息（每張表的列信息）；以及存儲(chǔ)訪問(wèn)權(quán)限列表．如果有相當(dāng)長(zhǎng)的時(shí)間Chubby不能訪問(wèn)，ＢＴ就也不能訪問(wèn)了｛任何系統(tǒng)都有其弱點(diǎn)｝．最近我們?cè)谑褂?1個(gè)Chubby服務(wù)實(shí)例的14個(gè)ＢＴ集群中度量了這個(gè)效果，由于Chubby不能訪問(wèn)而導(dǎo)致BT中部分?jǐn)?shù)據(jù)不能訪問(wèn)的平均百分比是0.0047%,這里Chubby不能訪問(wèn)的原因是Chubby本身失效或者網(wǎng)絡(luò)問(wèn)題．單個(gè)集群里，受影響最大的百分比是0.0326%｛基于文件系統(tǒng)的Chubby還是很穩(wěn)定的｝.
聯(lián)系客服
