//這里是第二部分.我發(fā)現(xiàn)如果一篇文章太大,我的blog就打開特別慢,不知是WORDPRESS的問題還是什么.所以這里另起一篇.

５．實(shí)現(xiàn)
ＢＴ的實(shí)現(xiàn)有三個(gè)主要組件：客戶程序庫,，一個(gè)主服務(wù)器和多個(gè)子表服務(wù)器．針對負(fù)載的變化，可以動態(tài)的從服務(wù)器群中添加（或者去除）子表服務(wù)器．主服務(wù)器的任務(wù)是：給子表服務(wù)器指定子表,，檢測加入或者失效的子表服務(wù)器,，子表服務(wù)器負(fù)載均衡，以及對google文件系統(tǒng)的文件進(jìn)行垃圾收集．除此之外,，它還處理諸如建立表和列族之類的表模式改變工作．

每個(gè)子表服務(wù)器管理一個(gè)子表集合（通常每個(gè)服務(wù)器處理數(shù)十乃至上千個(gè)子表）．子表服務(wù)器負(fù)責(zé)處理對它管理的子表進(jìn)行的讀寫操作,，當(dāng)子表變的太大時(shí)，服務(wù)器會將子表分割．和很多單個(gè)主服務(wù)器分布式系統(tǒng)［17.21］一樣,，客戶數(shù)據(jù)不經(jīng)過主服務(wù)器．客戶的讀寫操作是通過直接和子表服務(wù)器通信完成的．由于ＢＴ的客戶不必通過主服務(wù)器獲取子表位置信息,，大多數(shù)客戶完全不和主服務(wù)器通信．因此，實(shí)際使用中主服務(wù)器的負(fù)載很輕．

一個(gè)ＢＴ集群存儲多個(gè)表．每個(gè)表由一些子表組成,，每個(gè)子表包含一個(gè)行域內(nèi)的所有數(shù)據(jù)．在起始狀態(tài)下,，一個(gè)表只有一個(gè)子表．當(dāng)一個(gè)表長大以后,，它自動的分割成多個(gè)子表,，每個(gè)子表的缺省大小是100到200MB.

5.1 子表的地址

子表地址信息是存儲在一個(gè)三層類似Ｂ＋樹[10]的結(jié)構(gòu)中的(圖4)．

圖4:子表地址結(jié)構(gòu)

第一層是Chubby中的一個(gè)文件，它存儲根子表的地址．根子表里存儲一個(gè)特殊的表里的所有子表的地址,，地址這個(gè)特殊的表是元數(shù)據(jù)表．每個(gè)元數(shù)據(jù)子表里存儲一組用戶子表的地址．根子表其實(shí)是元數(shù)據(jù)表里的第一個(gè)子表,，但是對它的處理比較特殊：根子表永遠(yuǎn)不會被分割，這樣一來保證了子表地址結(jié)構(gòu)不會超過三層．

元數(shù)據(jù)表里面,，每個(gè)子表的地址都對應(yīng)一個(gè)行關(guān)鍵字,，這個(gè)關(guān)鍵字是由子表所在的表的標(biāo)識符，和子表的最后一行編碼而成的．每個(gè)元數(shù)據(jù)行在內(nèi)存里存儲大約1kb的數(shù)據(jù)．元數(shù)據(jù)子表的大小限制是128MB,，限制看似不大,不過已經(jīng)可以讓這個(gè)三層的地址樹足夠表示2^34個(gè)子表了（如果每個(gè)子表存儲128MB數(shù)據(jù),，一共是2^61字節(jié)數(shù)據(jù)）．

客戶程序庫緩存了子表地址．如果客戶沒有一個(gè)子表的地址，或者它發(fā)現(xiàn)地址不正確,，客戶就遞歸的查詢子表地址樹．如果緩存是空的,，那么尋址算法需要三次網(wǎng)絡(luò)來回通信來尋址，其中包括一次Chubby讀操作．如果緩存數(shù)據(jù)過期,，那么尋址算法可能最多需要６次網(wǎng)絡(luò)來回通信才能更新數(shù)據(jù),，因?yàn)橹挥性诰彺娌幻械臅r(shí)候才能發(fā)現(xiàn)數(shù)據(jù)過期｛三次通信發(fā)現(xiàn)過期，另外三次更新數(shù)據(jù)｝（這里的假定是,，元數(shù)據(jù)子表沒有頻繁的移動）．子表的地址是放在內(nèi)存里的,，所以不必訪問google文件系統(tǒng)ＧＦＳ，我們通過預(yù)取子表地址來進(jìn)一步的減少了訪問開銷｛體系結(jié)構(gòu)里的老花招：緩存,，預(yù)?。好看巫x取子表的元數(shù)據(jù)的時(shí)候,，都讀取幾個(gè)子表的元數(shù)據(jù)｛為什么不說預(yù)取幾個(gè)子表地址？倆,？四個(gè),？這里就是有價(jià)值的東西了，需要時(shí)間去積累經(jīng)驗(yàn)｝．

在元數(shù)據(jù)表中還存儲了次要信息,，包括每個(gè)子表的事件日志（例如,，什么時(shí)候一個(gè)服務(wù)器開始服務(wù)該子表）．這些信息有助于排錯(cuò)和性能分析｛一筆代過重要信息，比如都存了什么事件,，事件屬性是什么等｝．

5.2子表分配

在任一時(shí)刻,，一個(gè)子表只會分配給一個(gè)子表服務(wù)器．主服務(wù)器知道當(dāng)前有哪些活躍的子表服務(wù)器，還知道哪些子表分配到哪些子表服務(wù)器,，哪些以及哪些子表沒有被分配．當(dāng)一個(gè)子表沒有被分配到服務(wù)器,，同時(shí)又有一個(gè)服務(wù)器的空閑空間足夠裝載該子表，主服務(wù)器就給這個(gè)子表服務(wù)器材發(fā)送一個(gè)裝載請求,，把子表分配給這個(gè)服務(wù)器．

｛這里是協(xié)議描述｝ＢＴ使用Chubby來追蹤子表服務(wù)器．當(dāng)一個(gè)子表服務(wù)器啟動時(shí),，它在一個(gè)特定的Chubby目錄里建立一個(gè)有唯一名字的文件，并獲取該文件的獨(dú)占的鎖．主服務(wù)器監(jiān)視這個(gè)目錄{服務(wù)器目錄},，就可以發(fā)現(xiàn)新的子表服務(wù)器．一個(gè)子表服務(wù)器如果喪失了對文件的鎖,，就停止對它的子表們的服務(wù)．服務(wù)器可能喪失鎖的原因很多，例如：網(wǎng)絡(luò)斷開導(dǎo)致服務(wù)器丟失了Chubby會話（Chubby提供一種有效的服務(wù),，使子表服務(wù)器不必通過網(wǎng)絡(luò)就能查詢它是否還擁有文件鎖｛這個(gè)比較神,，難道是tablet server自己只查本地文件，chubby server來幫它在本地建立文件,？要認(rèn)真看看chubby的協(xié)議才知道｝）．如果文件依然存在,，子表服務(wù)器會試圖重新獲得對文件的獨(dú)占鎖．如果文件不存在了，那么子表服務(wù)器就不能服務(wù)了,，它就退出．當(dāng)子表服務(wù)器終止時(shí)（例如,，集群管理系統(tǒng)將子表服務(wù)器的機(jī)器從集群中移除），它會試圖釋放文件鎖,，這樣一來主服務(wù)器就能更快的把子表分配給其他服務(wù)器．

當(dāng)一個(gè)子表服務(wù)器不再服務(wù)它的子表的時(shí)候,，主服務(wù)器有責(zé)任發(fā)現(xiàn)問題，并把子表盡快重新分配．主服務(wù)器發(fā)現(xiàn)問題的方法是定期詢問子表服務(wù)器的文件鎖狀態(tài)．如果一個(gè)子表服務(wù)器報(bào)告丟失了文件鎖,，或者過去幾次詢問都沒有反應(yīng),，主服務(wù)器就會試圖獲取子表服務(wù)器的文件鎖．如果主服務(wù)器能夠獲取鎖，說明Chubby是好的,，子表服務(wù)器或者是死了,，或者不能和Chubby通信，主服務(wù)器就刪除子表服務(wù)器的文件，以確保子表服務(wù)器不再服務(wù)子表．一旦一個(gè)服務(wù)器的文件被刪除,，主服務(wù)器就可以把它的子表都放入未分配的子表集合中．為了保證在主服務(wù)器和Chubby之間有網(wǎng)絡(luò)故障的時(shí)候ＢＴ仍然可以使用,，主服務(wù)器的Chubby會話一旦過期，主服務(wù)器就退出．但是,，如前所述,，主服務(wù)器故障不影響子表到子表服務(wù)器的分配．

當(dāng)一個(gè)集群管理系統(tǒng)啟動一個(gè)主服務(wù)器時(shí)，它需要發(fā)現(xiàn)當(dāng)前的子表分配狀態(tài),，然后才能修改分配狀態(tài)｛設(shè)計(jì)思想：永遠(yuǎn)考慮失效＋恢復(fù)｝．主服務(wù)器執(zhí)行以下啟動步驟：(１)主服務(wù)器在Chubby中獲取唯一的主文件鎖,，來阻止其他主服務(wù)器實(shí)例｛singlton｝．(2)主服務(wù)器材掃描Chubby服務(wù)器目錄,獲取當(dāng)前活躍服務(wù)器列表.(3)主服務(wù)器和活躍子表服務(wù)器通信，獲取子表分配狀態(tài)｛注意子表分配不是主服務(wù)器存儲的,，保證了失效時(shí)主服務(wù)器不會成為性能瓶頸｝．（４）主服務(wù)器掃描元數(shù)據(jù)表,，每次遇到一個(gè)沒有分配的子表，就加入未分配子表集合,，這個(gè)子表就可以被分配了．

這里有一個(gè)復(fù)雜的情況：在元數(shù)據(jù)表沒有被分配之前,，是不能掃描元數(shù)據(jù)表的｛雞和蛋｝．因此，在開始第四步的掃描之前,，如果第三步的掃描沒有發(fā)現(xiàn)根子表沒分配,，主服務(wù)器就把根子表加入未分配的子表集合．這一附加步驟保證了根子表肯定會被分配．由于根子表包括了所有元數(shù)據(jù)子表的名字，主服務(wù)器在掃描過根子表以后,，就知道了所有的元數(shù)據(jù)子表．

現(xiàn)存子表集合僅在以下事件中才會改變：一個(gè)子表被建立或者刪除,，兩個(gè)子表被合并，或者一個(gè)子表被分割成兩個(gè)．主服務(wù)器可以監(jiān)控所有這些事件,，因?yàn)榍叭齻€(gè)事件都是主服務(wù)器啟動的．最后一個(gè)事件：分割子表,，是由子表服務(wù)器啟動的．這個(gè)事件是特別處理的．子表服務(wù)器在分割完畢時(shí),，在元數(shù)據(jù)表中記錄新的子表的信息．當(dāng)分割完成時(shí),，子表服務(wù)器通知主服務(wù)器．如果分割的通知沒有到達(dá)（兩個(gè)服務(wù)器中間死了一個(gè)），主服務(wù)器在請求子表服務(wù)器裝載已經(jīng)分割的子表的時(shí)候,，就會發(fā)現(xiàn)這個(gè)沒有通知的分割操作｛設(shè)計(jì)的時(shí)候一定要考慮到錯(cuò)誤和失敗的恢復(fù)．古人云,，未思進(jìn),先思退｝．子表服務(wù)器就會重新通知主服務(wù)器，因?yàn)樵谠獢?shù)據(jù)表中找到的子表入口只包含要求裝載的子表的部分信息｛細(xì)節(jié),，細(xì)節(jié)呢,？｝．

//今天比較忙,只有這些了.抱歉.

//更新:彼岸翻譯了第5章的剩余部分,貼在這里:

5.3 子表服務(wù)

子表的狀態(tài)存放在GFS里，如圖5所示,。更新內(nèi)容提交到存放redo記錄的提交日志里｛比較繞,，看原文可能清楚點(diǎn)｝。在這些更新中,，最近提交的那些存放在內(nèi)存里一個(gè)叫memtable的有序緩沖里,；老一點(diǎn)的更新則存放在一系列SSTable里。若要恢復(fù)一個(gè)子表，子表服務(wù)器從METADATA表中讀取元數(shù)據(jù),。元數(shù)據(jù)包括了由一個(gè)子表和一系列redo點(diǎn)｛redo怎么翻好,？｝組成的SSTable列表，這些是指向可能含有該子表數(shù)據(jù)的提交日志的指針｛煩死定語從句了｝,。 該服務(wù)器把這些SSTable的索引讀進(jìn)內(nèi)存,，并通過重復(fù)redo點(diǎn)之后提交的更新來重建memtable。

當(dāng)一個(gè)寫操作到達(dá)子表服務(wù)器時(shí),，該服務(wù)器檢查確信這個(gè)操作完整無誤,，而且發(fā)送方有權(quán)執(zhí)行所描述的變換。授權(quán)是通過從一個(gè)Chubby文件里讀取具有寫權(quán)限的操作者列表來進(jìn)行的（幾乎一定會存放在Chubby客戶緩存里）,。合法的變換會寫到提交日志里,。可以用成組提交來提高大量小變換的吞吐量［13,，16］,。寫操作提交后，寫的內(nèi)容就插入到memtable里,。

當(dāng)一個(gè)讀操作到達(dá)子表服務(wù)器時(shí),，會作類似的完整性和授權(quán)檢查。合法的讀操作在一個(gè)由SSTable系列和memtable合并的視圖里執(zhí)行,。由于SSTable和memtable是字典序的數(shù)據(jù)結(jié)構(gòu),，合并視圖可以很有效地形成。

進(jìn)來方向的｛incoming｝讀寫操作在子表分拆和合并時(shí)仍能繼續(xù),。

5.4 緊縮｛compaction｝

在執(zhí)行寫操作時(shí),，memtable的大小不斷增加。當(dāng)memtable大小達(dá)到一定閾值時(shí),，memtable就會被凍結(jié),，然后創(chuàng)建一個(gè)新的memtable，凍結(jié)住的memtable則被轉(zhuǎn)換成SSTable并寫到GFS里,。這種次要緊縮過程有兩個(gè)目的：縮小了子表服務(wù)器的內(nèi)存用度,，以及減少了在服務(wù)器當(dāng)機(jī)后恢復(fù)過程中必須從提交日志里讀取的數(shù)據(jù)量。 進(jìn)來方向的讀寫操作在緊縮進(jìn)行當(dāng)中仍能繼續(xù),。

每一個(gè)次要緊縮會創(chuàng)建一個(gè)新的SSTable,。如果這種行為一直繼續(xù)沒有停止的跡象，讀操作可能需要合并來自任意多SSTable的更新,。相反,，我們通過定期在后臺執(zhí)行合并緊縮來限定這類文件的數(shù)量。合并緊縮讀取一些SSTable和memtable的內(nèi)容,，并寫成一個(gè)新的SSTable,。一旦緊縮完成，作為輸入的這些個(gè)SSTable和memtable就可以扔掉了。

把所有SSTable重寫成唯一一個(gè)SSTable的合并緊縮叫作主要緊縮,。 由非主要緊縮產(chǎn)生的SSTable可以含有特殊的刪除條目,，它們使得老一點(diǎn)但仍活躍的SSTable中已刪除的數(shù)據(jù)不再出現(xiàn)。而主要緊縮則產(chǎn)生不包含刪除信息或刪除數(shù)據(jù)的SSTable,。Bigtable在它所有的子表中循環(huán),，并且定期對它們執(zhí)行主要緊縮。這些主要緊縮使得Bigtable可以回收已刪除數(shù)據(jù)占有的資源,，并且還能保證已刪除數(shù)據(jù)及時(shí)從系統(tǒng)里小時(shí),，這對存放敏感數(shù)據(jù)的服務(wù)很重要。