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