云計算_02Google云計算原理與高級開發(fā)應(yīng)用

1、電子工業(yè)出版社云計算(第二版)配套課件第第2章章 Google云計算原理與應(yīng)用云計算原理與應(yīng)用云計算（第二版）購買網(wǎng)址：當(dāng)當(dāng)網(wǎng) 京東商城姊妹力作實戰(zhàn)Hadoop購買網(wǎng)址：當(dāng)當(dāng)網(wǎng) 京東商城提提 綱綱 Google文件系統(tǒng)GFS 分布式數(shù)據(jù)處理MapReduce 分布式鎖服務(wù)Chubby 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable 分布式存儲系統(tǒng)Megastore 大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper Google應(yīng)用程序引擎 分布式鎖服務(wù)Chubby Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能 一種建議性的鎖而不是強制性的鎖；具有更大的

2、靈活性 GFS使用Chubby選取一個GFS主服務(wù)器 Bigtable使用Chubby指定一個主服務(wù)器并發(fā)現(xiàn)、控制與其相關(guān)的子表服務(wù)器 Chubby還可以作為一個穩(wěn)定的存儲系統(tǒng)存儲包括元數(shù)據(jù)在內(nèi)的小數(shù)據(jù) Google內(nèi)部還使用Chubby進行名字服務(wù)（Name Server）ChubbyChubby GoogleGoogle設(shè)計的提供粗粒度鎖服務(wù)的一個設(shè)計的提供粗粒度鎖服務(wù)的一個文件系統(tǒng)文件系統(tǒng)，它基于松耦，它基于松耦合分布式系統(tǒng)，解決了分布的一致性問題合分布式系統(tǒng)，解決了分布的一致性問題 PaxosPaxos算法算法 Paxos算法算法 Leslie Lamport最先提出的一種基于消息傳遞

3、（最先提出的一種基于消息傳遞（Messages Passing）的一致性算法，用于解決）的一致性算法，用于解決分布式系統(tǒng)中的一致性分布式系統(tǒng)中的一致性問題問題 分布式系統(tǒng)一致性問題分布式系統(tǒng)一致性問題就是如何保證系統(tǒng)就是如何保證系統(tǒng)中初始狀態(tài)相同的各個節(jié)點在執(zhí)行相同的操作中初始狀態(tài)相同的各個節(jié)點在執(zhí)行相同的操作序列時，看到的指令序列是完全一致的，并且序列時，看到的指令序列是完全一致的，并且最終得到完全一致的結(jié)果最終得到完全一致的結(jié)果 一個最簡單的方案在分布式系統(tǒng)中設(shè)置一個專門節(jié)點，在每次需要進行操作之前，系統(tǒng)的各個部分向它發(fā)出請求，告訴該節(jié)點接下來系統(tǒng)要做什么。該節(jié)點接受第一個到達的請求內(nèi)容作

4、為接下來的操作，這樣就能夠保證系統(tǒng)只有一個唯一的操作序列 方案存在什么缺陷？PaxosPaxos算法算法缺陷缺陷專門節(jié)點失效，整專門節(jié)點失效，整個系統(tǒng)就很可能出現(xiàn)不一致。個系統(tǒng)就很可能出現(xiàn)不一致。為了避免這種情況，在系統(tǒng)為了避免這種情況，在系統(tǒng)中必然要設(shè)置多個專門節(jié)點，中必然要設(shè)置多個專門節(jié)點，由這些節(jié)點來共同決定操作由這些節(jié)點來共同決定操作序列序列 Paxos算法算法 proposers提出決議（Value，系統(tǒng)接下來執(zhí)行的指令）acceptors批準(zhǔn)決議 learners獲取并使用已經(jīng)通過的決議 PaxosPaxos算法算法（1）決議只有被）決議只有被proposers提出后才提出后才能批

5、準(zhǔn)能批準(zhǔn) （2）每次只批準(zhǔn)一個決議）每次只批準(zhǔn)一個決議 （3）只有決議確定被批準(zhǔn)后）只有決議確定被批準(zhǔn)后learners才能獲取這個決議才能獲取這個決議 PaxosPaxos算法算法P1：每個acceptor只接受它得到的第一個決議 系統(tǒng)約束條件系統(tǒng)約束條件P1表明一個acceptor可以收到多個決議，為區(qū)分，對每個決議進行編號，后到的決議編號大于先到的決議編號 ；約束條件P1不是很完備 ！P2：一旦某個決議得到通過，之后通過的決議必須和該決議保持一致 P2a：一旦某個決議v得到通過，之后任何acceptor再批準(zhǔn)的決議必須是v P2a和P1是有矛盾的 ! P2b：一旦某個決議v得到通過，之后

6、任何proposer再提出的決議必須是v P1和P2b保證條件（2），彼此之間不存在矛盾。但是P2b很難通過一種技術(shù)手段來實現(xiàn)它，因此提出了一個蘊涵P2b的約束P2c P2c：如果一個編號為n的提案具有值v，那么存在一個“多數(shù)派”，要么它們中沒有誰批準(zhǔn)過編號小于n的任何提案，要么它們進行的最近一次批準(zhǔn)具有值v PaxosPaxos算法算法 準(zhǔn)備階段：準(zhǔn)備階段：proposers選擇一個提案并選擇一個提案并將它的編號設(shè)為將它的編號設(shè)為n，然后將它發(fā)送給，然后將它發(fā)送給acceptors中的一個中的一個“多數(shù)派多數(shù)派”。Acceptors 收到后，如果提案的編號大收到后，如果提案的編號大于它已經(jīng)回

7、復(fù)的所有消息，則于它已經(jīng)回復(fù)的所有消息，則acceptors將自己上次的批準(zhǔn)回復(fù)給將自己上次的批準(zhǔn)回復(fù)給proposers，并不再批準(zhǔn)小于并不再批準(zhǔn)小于n的提案的提案 批準(zhǔn)階段：當(dāng)批準(zhǔn)階段：當(dāng)proposersproposers接收到接收到acceptors acceptors 中的這個中的這個“多數(shù)派多數(shù)派”的回復(fù)的回復(fù)后，就向回復(fù)請求的后，就向回復(fù)請求的acceptorsacceptors發(fā)送發(fā)送acceptaccept請求，在符合請求，在符合acceptorsacceptors一方的約一方的約束條件下，束條件下，acceptorsacceptors收到收到acceptaccept請求后請

8、求后即批準(zhǔn)這個請求即批準(zhǔn)這個請求 解決一致性問題算法解決一致性問題算法：為了減少決議發(fā)布過程中的消息量，acceptors將這個通過的決議發(fā)送給learners 的一個子集，然后由這個子集中的learners 去通知所有其他的learners；特殊情況特殊情況：如果兩個proposer在這種情況下都轉(zhuǎn)而提出一個編號更大的提案，那么就可能陷入活鎖。此時需要選舉出一個president，僅允許 president提出提案分布式鎖服務(wù)Chubby Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能 系統(tǒng)設(shè)計目標(biāo)系統(tǒng)設(shè)計目標(biāo)Chubby系統(tǒng)設(shè)計高可

9、用性和高可靠性；首要目標(biāo)，在保證這一目標(biāo)的基礎(chǔ)上再考慮系統(tǒng)的吞吐量和存儲能力 高擴展性；將數(shù)據(jù)存儲在價格較為低廉的RAM，支持大規(guī)模用戶訪問文件 支持粗粒度的建議性鎖服務(wù)；提供這種服務(wù)的根本目的是提高系統(tǒng)的性能 服務(wù)信息的直接存儲；可直接存儲包括元數(shù)據(jù)、系統(tǒng)參數(shù)在內(nèi)的有關(guān)服務(wù)信息支持通報機制；客戶可以及時地了解到事件發(fā)生 支持緩存機制；通過一致性緩存將常用信息保存在客戶端，避免了頻繁地訪問主服務(wù)器 Chubby系統(tǒng)設(shè)計Chubby中還添加了一些新的功能特性；這種設(shè)計主要是考慮到以下幾個問題 030302020101n開發(fā)者初期很少考慮系統(tǒng)開發(fā)者初期很少考慮系統(tǒng)的一致性，但隨著開發(fā)進的一致性，但

10、隨著開發(fā)進行，問題會變得越來越嚴(yán)行，問題會變得越來越嚴(yán)重。單獨的鎖服務(wù)可以保重。單獨的鎖服務(wù)可以保證原有系統(tǒng)架構(gòu)不會發(fā)生證原有系統(tǒng)架構(gòu)不會發(fā)生改變，而使用函數(shù)庫很可改變，而使用函數(shù)庫很可能需要對系統(tǒng)架構(gòu)做出大能需要對系統(tǒng)架構(gòu)做出大幅度的改動幅度的改動 n系統(tǒng)中很多事件發(fā)生是需系統(tǒng)中很多事件發(fā)生是需要告知其他用戶和服務(wù)器，要告知其他用戶和服務(wù)器，使用一個基于文件系統(tǒng)的使用一個基于文件系統(tǒng)的鎖服務(wù)可以將這些變動寫鎖服務(wù)可以將這些變動寫入文件中。有需要的用戶入文件中。有需要的用戶和服務(wù)器直接訪問這些文和服務(wù)器直接訪問這些文件即可，避免因大量系統(tǒng)件即可，避免因大量系統(tǒng)組件之間事件通信帶來系組件之間事件

11、通信帶來系統(tǒng)性能下降統(tǒng)性能下降 n基于鎖的開發(fā)接口容易基于鎖的開發(fā)接口容易被開發(fā)者接受。雖然在被開發(fā)者接受。雖然在分布式系統(tǒng)中鎖的使用分布式系統(tǒng)中鎖的使用會有很大的不同，但是會有很大的不同，但是和一致性算法相比，鎖和一致性算法相比，鎖顯然被更多的開發(fā)者所顯然被更多的開發(fā)者所熟知熟知 Chubby系統(tǒng)設(shè)計Paxos算法實現(xiàn)過程中需要一個“多數(shù)派多數(shù)派”就某個值達成一致，本質(zhì)上就是分布式系統(tǒng)中常見的quorum機制機制；為保證系統(tǒng)高可用性，需要若干臺機器，但使用單獨鎖服務(wù)的話一臺機器也能保證這種高可用性Chubby設(shè)計過程中一些細節(jié)問題值得關(guān)注：在Chubby系統(tǒng)中采用了建議性的鎖而沒有采用強制性

12、的鎖。兩者的根本區(qū)別在于用戶訪問某個被鎖定的文件時，建議性用戶訪問某個被鎖定的文件時，建議性的鎖不會阻止訪問，而強制性的鎖則會阻止訪問，實際上這的鎖不會阻止訪問，而強制性的鎖則會阻止訪問，實際上這是為了方便系統(tǒng)組件之間的信息交互是為了方便系統(tǒng)組件之間的信息交互另外，Chubby還采用了粗粒度（Coarse-Grained）鎖服務(wù)而沒有采用細粒度（Fine-Grained）鎖服務(wù)，兩者的差異在于持有鎖的時間，細粒度的鎖持有時間很短細粒度的鎖持有時間很短Chubby系統(tǒng)設(shè)計 客戶端應(yīng) 用程序 Chubby 程序庫 客戶端應(yīng) 用程序 Chubby 程序庫 客戶端進程 主服務(wù)器 Chubby 單元的

13、五個服務(wù)器 遠程過程調(diào)用 Chubby基本架構(gòu)：客戶端基本架構(gòu)：客戶端和服務(wù)器端，兩者通過遠程和服務(wù)器端，兩者通過遠程過程調(diào)用（過程調(diào)用（RPC）來連接）來連接客戶端每個客戶應(yīng)用程序都客戶端每個客戶應(yīng)用程序都有一個有一個Chubby程序庫程序庫（Chubby Library），所），所有應(yīng)用都是通過調(diào)用這個庫有應(yīng)用都是通過調(diào)用這個庫中相關(guān)函數(shù)來完成中相關(guān)函數(shù)來完成服務(wù)器一端服務(wù)器一端Chubby單元，單元，一般由五個稱為副本一般由五個稱為副本（Replica）服務(wù)器組成，）服務(wù)器組成，它們配置上完全一致，且系它們配置上完全一致，且系統(tǒng)剛開始時處于對等地位統(tǒng)剛開始時處于對等地位 分布式鎖服務(wù)Ch

14、ubby Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能 Chubby中的Paxos單個單個Chubby副本結(jié)構(gòu)副本結(jié)構(gòu) 容錯日志容錯日志對數(shù)據(jù)庫正確性提供重要支持；一致性由Paxos算法保證；副本之間通過特定的Paxos協(xié)議通信，同時本地文件中保存與Chubby中相同的日志數(shù)據(jù) 容錯數(shù)據(jù)庫容錯數(shù)據(jù)庫快照（Snapshot）和記錄數(shù)據(jù)庫操作重播日志（Replay-log）；每一次的數(shù)據(jù)庫操作最終都將提交至日志中；本地文件中也保存著一份數(shù)據(jù)庫數(shù)據(jù)副本 Chubby構(gòu)建在這個容錯的數(shù)據(jù)庫之上，Chubby利用這個數(shù)據(jù)庫存儲所有的數(shù)據(jù)。Chu

15、bby的客戶端通過特定的Chubby協(xié)議和單個的Chubby副本進行通信 Chubby中的Paxos容錯日志的容錯日志的API Content Title Content TitleChubby中中Paxos算法過程算法過程 2 2、協(xié)調(diào)者從客戶提交的值中選擇一個，、協(xié)調(diào)者從客戶提交的值中選擇一個，acceptaccept消息廣播給所有的副本，其他的消息廣播給所有的副本，其他的副本收到廣播后，選擇接受或者拒絕這副本收到廣播后，選擇接受或者拒絕這個值，并將決定結(jié)果反饋個值，并將決定結(jié)果反饋3、協(xié)調(diào)者收到大多數(shù)副本接受信息后，、協(xié)調(diào)者收到大多數(shù)副本接受信息后，認(rèn)為達到了一致性，接著向相關(guān)副本發(fā)認(rèn)為

16、達到了一致性，接著向相關(guān)副本發(fā)送一個送一個commit消息消息 1、選擇一副本為協(xié)調(diào)者（、選擇一副本為協(xié)調(diào)者（Coordinator） Chubby中的PaxosChubby設(shè)計者借鑒了Paxos的兩種解決機制：給協(xié)調(diào)者指派序號或限制協(xié)調(diào)者可以選擇的值 指派序號的方法 （1）在一個有n個副本系統(tǒng)中，為每個副本分配一個id ，其中 0irn-1。則副本的序號，其中k的初始值為0 （2）某個副本想成為協(xié)調(diào)者之后，它就根據(jù)規(guī)則生成一個比它以前的序號更大的序號（實際上就是提高k的值），并將這個序號通過propose消息廣播給其他所有的副本 （3）如果接受到廣播的副本發(fā)現(xiàn)該序號比它以前見過的序號都大，則

17、向發(fā)出廣播的副本返回一個promise消息，并且承諾不再接受舊的協(xié)調(diào)者發(fā)送的消息。如果大多數(shù)副本都返回了promise消息，則新的協(xié)調(diào)者就產(chǎn)生了 限制協(xié)調(diào)者可以選擇的值 Paxos強制新的協(xié)調(diào)者必須選擇和前任相同的值 Chubby中的PaxosChubby做了一個重要優(yōu)化來提高系統(tǒng)效率在選擇某一個副本作為協(xié)調(diào)者之后就長期不變，此時協(xié)調(diào)者就被稱為主服務(wù)器（Master） 客戶端的數(shù)據(jù)請求由主服務(wù)器完成，Chubby保證在一定時間內(nèi)有且僅有一個主服務(wù)器，這個時間就稱為主服務(wù)器租約期（Master Lease） 客戶端需要確定主服務(wù)器的位置，可向DNS發(fā)送一個主服務(wù)器定位請求，非主服務(wù)器的副本將對該

18、請求做出回應(yīng) Chubby對于Paxos論文中未提及的一些技術(shù)細節(jié)進行了補充，所以Chubby的實現(xiàn)是基于Paxos，但其技術(shù)手段更加的豐富，更具有實踐性 分布式鎖服務(wù)Chubby Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能 Chubby文件系統(tǒng)Chubby系統(tǒng)本質(zhì)上就是一個分布式的、存儲大量小文件的分布式的、存儲大量小文件的文件系統(tǒng)文件系統(tǒng)，它所有的操作都是在文件的基礎(chǔ)上完成Chubby最常用的鎖服務(wù)中，每一個文件就代表一個鎖，用戶通過打開、關(guān)閉和讀取文件，獲取共享（Shared）鎖或獨占（Exclusive）鎖選舉主服務(wù)器過程中

19、，符合條件的服務(wù)器都同時申請打開某個文件并請求鎖住該文件成功獲得鎖的服務(wù)器自動成為主服務(wù)器并將其地址寫入這個文件夾，以便其他服務(wù)器和用戶可以獲知主服務(wù)器的地址信息Chubby文件系統(tǒng)Chubby的文件系統(tǒng)和UNIX類似 例如在文件名“/ls/foo/wombat/pouch”中，ls代表lock service，這是所有Chubby文件系統(tǒng)的共有前綴；foo是某個單元的名稱；/wombat/pouch則是foo這個單元上的文件目錄或者文件名 Google對Chubby做了一些與UNIX不同的改變 例如Chubby不支持內(nèi)部文件的移動；不記錄文件的最后訪問時間；另外在Chubby中并沒有符號連接

20、（Symbolic Link，又叫軟連接，類似于Windows系統(tǒng)中的快捷方式）和硬連接（Hard Link，類似于別名）的概念 在具體實現(xiàn)時，文件系統(tǒng)由許多節(jié)點組成，分為永久型和臨時型，每個節(jié)點就是一個文件或目錄。節(jié)點中保存著包括ACL（Access Control List，訪問控制列表）在內(nèi)的多種系統(tǒng)元數(shù)據(jù) 實例號實例號：新節(jié)點實例號必定大于舊節(jié)點的實例號 元數(shù)據(jù)包含以下四種單調(diào)遞增64位編號 內(nèi)容生成號內(nèi)容生成號：文件內(nèi)容修改時該號增加 鎖生成號鎖生成號：鎖被用戶持有時該號增加 ACL生成號生成號：ACL名被覆寫時該號增加 Chubby文件系統(tǒng)Chubby文件系統(tǒng)序號序號：確定句柄由當(dāng)

21、前還是以前的主服務(wù)器創(chuàng)建：確定句柄由當(dāng)前還是以前的主服務(wù)器創(chuàng)建2模式信息模式信息：用于新的主服務(wù)器重新創(chuàng)建一個舊句柄：用于新的主服務(wù)器重新創(chuàng)建一個舊句柄 3用戶打開某個節(jié)點的同時會獲取一個類似于UNIX中文件描述符（File Descriptor）的句柄，這個句柄由以下三個部分組成 校驗數(shù)位校驗數(shù)位：防止其他用戶創(chuàng)建或猜測這個句柄：防止其他用戶創(chuàng)建或猜測這個句柄 1Chubby文件系統(tǒng)在實際執(zhí)行中，為了避免所有的通信都使用序號帶來系統(tǒng)開銷增長，Chubby引入了sequencer的概念sequencer實際上就是一個序號，只能由鎖的持有者在獲取鎖時向系統(tǒng)發(fā)出請求來獲得。這樣一來Chubby系統(tǒng)

22、中只有涉及鎖的操作才需要序號，其他一概不用。在文件操作中，用戶可以將句柄看做一個指向文件系統(tǒng)的指針 函 數(shù) 名 稱作 用Open()打開某個文件或者目錄來創(chuàng)建句柄Close()關(guān)閉打開的句柄，后續(xù)的任何操作都將中止Poison()中止當(dāng)前未完成及后續(xù)的操作，但不關(guān)閉句柄GetContentsAndStat()返回文件內(nèi)容及元數(shù)據(jù)GetStat()只返回文件元數(shù)據(jù)ReadDir()返回子目錄名稱及其元數(shù)據(jù)SetContents()向文件中寫入內(nèi)容SetACL()設(shè)置ACL名稱Delete()如果該節(jié)點沒有子節(jié)點的話則執(zhí)行刪除操作Acquire()獲取鎖Release()釋放鎖GetSequenc

23、er()返回一個sequencerSetSequencer()將sequencer和某個句柄進行關(guān)聯(lián)CheckSequencer()檢查某個sequencer是否有效常用句柄函數(shù)及其作用常用句柄函數(shù)及其作用 分布式鎖服務(wù)Chubby Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能 ChubbyChubby客戶端與服務(wù)器端的通信過程客戶端與服務(wù)器端的通信過程 1 2 3 4 5 6 7 8 舊的主 服務(wù)器 新的主 服務(wù)器 寬限期 舊的主服 務(wù)器故障 選出新的 主服務(wù)器 客戶端 租約期 M2 租約期 C1 無主服務(wù)器 危險狀態(tài)臨界點 安全狀

24、態(tài)臨界點 KeepAlives 租約期 M1 租約期 C2 租約期 C3 租約期 M3 從左到右的水平方向表示時間在增加，斜向上的箭頭表示一次KeepAlive請求，斜向下的箭頭則是主服務(wù)器的一次回應(yīng) M1、M2、M3表示不同的主服務(wù)器租約期主服務(wù)器租約期；C1、C2、C3則是客戶端對主服務(wù)器租約期時長租約期時長做出的一個估計 KeepAlive是周期發(fā)送的一種信息，它主要有兩方面的功能：延遲租約的延遲租約的有效期有效期和攜帶事件信息告訴用戶更新攜帶事件信息告訴用戶更新 故障處理故障處理 客戶端租約過期客戶端租約過期 客戶端向主服務(wù)器發(fā)出一個客戶端向主服務(wù)器發(fā)出一個KeepAlive請求（上圖

25、請求（上圖1） 如果有需要通知的事件時則主服務(wù)器會立刻做出回應(yīng)，否則等到客戶如果有需要通知的事件時則主服務(wù)器會立刻做出回應(yīng)，否則等到客戶端的租約期端的租約期C1快結(jié)束的時候才做出回應(yīng)（圖快結(jié)束的時候才做出回應(yīng)（圖2），并更新主服務(wù)器租約），并更新主服務(wù)器租約期為期為M2 客戶端接到回應(yīng)后認(rèn)為該主服務(wù)器仍處于活躍狀態(tài)，于是將租約期更客戶端接到回應(yīng)后認(rèn)為該主服務(wù)器仍處于活躍狀態(tài)，于是將租約期更新為新為C2并立刻發(fā)出新的并立刻發(fā)出新的KeepAlive請求（圖請求（圖3） 寬限期內(nèi)，客戶端不會立刻斷開其與服務(wù)器端的聯(lián)系，而是不斷地做寬限期內(nèi)，客戶端不會立刻斷開其與服務(wù)器端的聯(lián)系，而是不斷地做探詢，當(dāng)

26、它接到客戶端的第一個探詢，當(dāng)它接到客戶端的第一個KeepAlive請求（圖請求（圖4）時會拒絕（圖）時會拒絕（圖5） 客戶端在主服務(wù)器拒絕后使用新紀(jì)元號來發(fā)送客戶端在主服務(wù)器拒絕后使用新紀(jì)元號來發(fā)送KeepAlive請求（圖請求（圖6） 新的主服務(wù)器接受這個請求并立刻做出回應(yīng)（圖新的主服務(wù)器接受這個請求并立刻做出回應(yīng)（圖7）如果客戶端接收到這個回應(yīng)的時間仍處于寬限期內(nèi)，系統(tǒng)會恢復(fù)到安全如果客戶端接收到這個回應(yīng)的時間仍處于寬限期內(nèi)，系統(tǒng)會恢復(fù)到安全狀態(tài)，租約期更新為狀態(tài)，租約期更新為C3。如果在寬限期未接到主服務(wù)器的相關(guān)回應(yīng)，客。如果在寬限期未接到主服務(wù)器的相關(guān)回應(yīng)，客戶端終止當(dāng)前的會話戶端終止

27、當(dāng)前的會話故障處理故障處理 主服務(wù)器出錯主服務(wù)器出錯 正常情況下舊的主服務(wù)器出現(xiàn)故障后系統(tǒng)會很快地選舉出新的主服務(wù)器，正常情況下舊的主服務(wù)器出現(xiàn)故障后系統(tǒng)會很快地選舉出新的主服務(wù)器，新選舉需要經(jīng)歷以下九個步驟新選舉需要經(jīng)歷以下九個步驟：（1 1）產(chǎn)生一個新的紀(jì)元號以便今后客戶端通信時使用，這能保證當(dāng)前的主服務(wù)產(chǎn)生一個新的紀(jì)元號以便今后客戶端通信時使用，這能保證當(dāng)前的主服務(wù)器不必處理針對舊的主服務(wù)器的請求器不必處理針對舊的主服務(wù)器的請求（2 2）只處理主服務(wù)器位置相關(guān)的信息，不處理會話相關(guān)的信息只處理主服務(wù)器位置相關(guān)的信息，不處理會話相關(guān)的信息（3 3）構(gòu)建處理會話和鎖所需的內(nèi)部數(shù)據(jù)結(jié)構(gòu)構(gòu)建處理

28、會話和鎖所需的內(nèi)部數(shù)據(jù)結(jié)構(gòu)（4 4）允許客戶端發(fā)送允許客戶端發(fā)送KeepAliveKeepAlive請求，不處理其他會話相關(guān)的信息請求，不處理其他會話相關(guān)的信息（5 5）向每個會話發(fā)送一個故障事件，促使所有的客戶端清空緩存向每個會話發(fā)送一個故障事件，促使所有的客戶端清空緩存（6 6）等待直到所有的會話都收到故障事件或會話終止等待直到所有的會話都收到故障事件或會話終止（7 7）開始允許執(zhí)行所有的操作開始允許執(zhí)行所有的操作（8 8）如果客戶端使用了舊的句柄則需要為其重新構(gòu)建新的句柄如果客戶端使用了舊的句柄則需要為其重新構(gòu)建新的句柄（9 9）一定時間段后（一定時間段后（1 1分鐘），刪除沒有被打開過

29、的臨時文件夾分鐘），刪除沒有被打開過的臨時文件夾如果這一過程在寬限期內(nèi)順利完成，則用戶不會感覺到任何故障的發(fā)生，也就是說新舊主服務(wù)器的替換對于用戶來說是透明透明的的，用戶感覺到的僅僅是一個延遲延遲 系統(tǒng)實現(xiàn)時，Chubby還使用了一致性客戶端緩存一致性客戶端緩存（Consistent Client-Side Caching）技術(shù)，這樣做的目的是減少通信壓力，降低通信頻率減少通信壓力，降低通信頻率 在客戶端保存一個和單元上數(shù)據(jù)一致的本地緩存，需要時客戶可以直接從緩存中取出數(shù)據(jù)而不用再和主服務(wù)器通信 當(dāng)某個文件數(shù)據(jù)或者元數(shù)據(jù)需要修改時，主服務(wù)器首先將這個修改阻塞；然后通過查詢主服務(wù)器自身維護的一個

30、緩存表，向?qū)π薷牡臄?shù)據(jù)進行了緩存的所有客戶端發(fā)送一個無效標(biāo)志（Invalidation） 客戶端收到這個無效標(biāo)志后會返回一個確認(rèn)（Acknowledge），主服務(wù)器在收到所有的確認(rèn)后才解除阻塞并完成這次修改 這個過程的執(zhí)行效率非常高，僅僅需要這個過程的執(zhí)行效率非常高，僅僅需要發(fā)送一次無效標(biāo)志發(fā)送一次無效標(biāo)志即可，即可，因為對于沒有返回確認(rèn)的節(jié)點，主服務(wù)器直接認(rèn)為其是因為對于沒有返回確認(rèn)的節(jié)點，主服務(wù)器直接認(rèn)為其是未緩存未緩存 分布式鎖服務(wù)Chubby Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能 一致性 每個Chubby單元是由五個副

31、本組成的，這五個副本中需要選舉產(chǎn)生一個主服務(wù)器，這種選舉本質(zhì)上就是一個一致性問題。實際執(zhí)行過程中，Chubby使用Paxos算法來解決 主服務(wù)器產(chǎn)生后客戶端的所有讀寫操作都是由主服務(wù)器來完成的 讀操作很簡單，客戶直接從主服務(wù)器上讀取所需數(shù)據(jù)即可 寫操作就會涉及數(shù)據(jù)一致性的問題；為了保證客戶的寫操作能夠同步到所有的服務(wù)器上，系統(tǒng)再次利用了Paxos算法安全性 Chubby用ACL形式安全保障措施。系統(tǒng)有三種ACL名：寫ACL名（Write ACL Name）、讀ACL名（Read ACL Name）和變更ACL名（Change ACL Name） 只要不被覆寫，子節(jié)點都是直接繼承直接繼承父節(jié)點的

32、ACL名 ACL同樣被保存在文件中，它是節(jié)點元數(shù)據(jù)的一部分，用戶在進行相關(guān)操作時首先需要通過ACL來獲取相應(yīng)的授權(quán)授權(quán) chinacloud CLOUD fun chinacloud 請求寫文件 讀取寫 ACL名 查詢 成功查到 允許寫入 成功寫入 Chubby的ACL機制 用戶用戶chinacloud提出向文件提出向文件CLOUD中寫入內(nèi)中寫入內(nèi)容請求。容請求。CLOUD首先首先讀取自身的寫讀取自身的寫ACL名名fun，接著接著在在fun中查到了中查到了chinacloud這一行記錄，這一行記錄，于是于是返回信息允許返回信息允許chinacloud對文件進行寫操對文件進行寫操作，作，此時此時

33、chinacloud才被允許向才被允許向CLOUD寫入寫入內(nèi)容。內(nèi)容。其他的操作和寫操作類似其他的操作和寫操作類似性能優(yōu)化 為滿足系統(tǒng)高可擴展性，Chubby目前已經(jīng)采取了一些措施：比如提高主服務(wù)器默認(rèn)的租約期、使用協(xié)議轉(zhuǎn)換服務(wù)將Chubby協(xié)議轉(zhuǎn)換成較簡單的協(xié)議、客戶端一致性緩存等；除此之外，Google的工程師們還考慮使用代理（Proxy）和分區(qū)（Partition）技術(shù) 代理可以減少主服務(wù)器處理KeepAlive以及讀請求帶來的服務(wù)器負載，但是它并不能減少寫操作帶來的通信量 使用分區(qū)技術(shù)的話可以將一個單元的命名空間（Name Space）劃分成N份。除了少量的跨分區(qū)通信外，大部分的分區(qū)都

34、可以獨自地處理服務(wù)請求。通過分區(qū)可以減少各個分區(qū)上的讀寫通信量，但不能減少KeepAlive請求的通信量 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable 設(shè)計動機與目標(biāo) 數(shù)據(jù)模型 系統(tǒng)架構(gòu) 主服務(wù)器 子表服務(wù)器 性能優(yōu)化 設(shè)計動機與目標(biāo)需要存儲的數(shù)據(jù)種類繁多需要存儲的數(shù)據(jù)種類繁多：Google目前向公眾開放的服務(wù)很多，需要處理的數(shù)據(jù)類型也非常多。包括URL、網(wǎng)頁內(nèi)容、用戶的個性化設(shè)置在內(nèi)的數(shù)據(jù)都是Google需要經(jīng)常處理的 海量的服務(wù)請求海量的服務(wù)請求：Google運行著目前世界上最繁忙的系統(tǒng)，它每時每刻處理的客戶服務(wù)請求數(shù)量是普通的系統(tǒng)根本無法承受的 商用數(shù)據(jù)庫無法滿足商用數(shù)據(jù)庫無法滿足Google的需

35、求的需求：一方面現(xiàn)有商用數(shù)據(jù)庫設(shè)計著眼點在于通用性，根本無法滿足Google的苛刻服務(wù)要求；另一方面對于底層系統(tǒng)的完全掌控會給后期的系統(tǒng)維護、升級帶來極大的便利 設(shè)計動機設(shè)計動機與目標(biāo)基本目標(biāo)基本目標(biāo)高可用性高可用性 Bigtable設(shè)計的重要設(shè)計的重要目標(biāo)之一就是確保幾目標(biāo)之一就是確保幾乎所有的情況下系統(tǒng)乎所有的情況下系統(tǒng)都可用都可用 廣泛的適用性廣泛的適用性 Bigtable是為了滿足是為了滿足系列系列Google產(chǎn)品而產(chǎn)品而非特定產(chǎn)品存儲要求非特定產(chǎn)品存儲要求 簡單性簡單性 底層系統(tǒng)簡單性既可底層系統(tǒng)簡單性既可減少系統(tǒng)出錯概率，減少系統(tǒng)出錯概率，也為上層應(yīng)用開發(fā)帶也為上層應(yīng)用開發(fā)帶來便利

36、來便利 很強的可擴展性很強的可擴展性 根據(jù)需要隨時可以加根據(jù)需要隨時可以加入或撤銷服務(wù)器入或撤銷服務(wù)器 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable 設(shè)計動機與目標(biāo) 數(shù)據(jù)模型 系統(tǒng)架構(gòu) 主服務(wù)器 子表服務(wù)器 性能優(yōu)化 數(shù)據(jù)模型 Bigtable是一個分布式多維映射表，表中的數(shù)據(jù)通過一個行關(guān)鍵一個行關(guān)鍵字字（Row Key）、一一個列關(guān)鍵字個列關(guān)鍵字（Column Key）以及一個時間戳一個時間戳（Time Stamp）進行索引 Bigtable對存儲在其中的數(shù)據(jù)不做任何解析，一律看做字符串字符串Bigtable的存儲邏輯可以表示為： (row:string, column:string, time:in

37、t64)string “內(nèi)容： ” “錨點：” “錨點：my.look.ca” “n.www” “” “” “” “CNN.com” “CNN” t3 t5 t6 t8 t9 Bigtable數(shù)據(jù)模型 數(shù)據(jù)模型行 Bigtable的行關(guān)鍵字可以是的行關(guān)鍵字可以是任意的字符串任意的字符串，但是大小不能超過，但是大小不能超過64KB。Bigtable和傳統(tǒng)的關(guān)系型數(shù)據(jù)庫有很大不同，它和傳統(tǒng)的關(guān)系型數(shù)據(jù)庫有很大不同，它不支持一般意義上的不支持一般意義上的事務(wù)，但能保證對于行的讀寫操作具有原子性（事務(wù)，但能保證對于行的讀寫操作具有原子性（Atomic） 表中數(shù)據(jù)都是根據(jù)行關(guān)鍵字進行排序的，排序使用的是

38、表中數(shù)據(jù)都是根據(jù)行關(guān)鍵字進行排序的，排序使用的是詞典序詞典序。 一個典型實例，其中一個典型實例，其中n.www就是一個行關(guān)鍵字。不直接存就是一個行關(guān)鍵字。不直接存儲網(wǎng)頁地址而將其倒排是儲網(wǎng)頁地址而將其倒排是Bigtable的一個巧妙設(shè)計。這樣做至少會帶的一個巧妙設(shè)計。這樣做至少會帶來以下兩個好處來以下兩個好處 同一地址域的網(wǎng)頁會被存儲在表中的連續(xù)位置，有利于用戶查同一地址域的網(wǎng)頁會被存儲在表中的連續(xù)位置，有利于用戶查找和分析找和分析 倒排便于數(shù)據(jù)壓縮，可以大幅提高壓縮率倒排便于數(shù)據(jù)壓縮，可以大幅提高壓縮率 數(shù)據(jù)模型列 Bigtable并不是簡單地存儲所有的列關(guān)鍵字，而是將其組織成所謂并不是簡單

39、地存儲所有的列關(guān)鍵字，而是將其組織成所謂的列族（的列族（Column Family），每個族中的數(shù)據(jù)都屬于同一個類型，并），每個族中的數(shù)據(jù)都屬于同一個類型，并且同族的數(shù)據(jù)會被壓縮在一起保存。引入了列族的概念之后，列關(guān)鍵且同族的數(shù)據(jù)會被壓縮在一起保存。引入了列族的概念之后，列關(guān)鍵字就采用下述的語法規(guī)則來定義：字就采用下述的語法規(guī)則來定義： 族名：限定詞（族名：限定詞（family：qualifier） 族名必須有意義，限定詞則可以任意選定族名必須有意義，限定詞則可以任意選定 圖中，內(nèi)容（圖中，內(nèi)容（Contents）、錨點（）、錨點（Anchor）都是不同的族。而）都是不同的族。而和和my.lo

40、ok.ca則是錨點族中不同的限定詞則是錨點族中不同的限定詞 族同時也是族同時也是Bigtable中訪問控制（中訪問控制（Access Control）基本單元，）基本單元，也就是說訪問權(quán)限的設(shè)置是在族這一級別上進行的也就是說訪問權(quán)限的設(shè)置是在族這一級別上進行的 “內(nèi)容： ” “錨點：” “錨點：my.look.ca” “n.www” “” “” “” “CNN.com” “CNN” t3 t5 t6 t8 t9 數(shù)據(jù)模型時間戳 Google的很多服務(wù)比如網(wǎng)頁檢索和用戶的個性化設(shè)置等都需要保存的很多服務(wù)比如網(wǎng)頁檢索和用戶的個性化設(shè)置等都需要保存不同時間的數(shù)據(jù)，這些不同的數(shù)據(jù)版本必須通過時間戳來區(qū)

41、分。圖不同時間的數(shù)據(jù)，這些不同的數(shù)據(jù)版本必須通過時間戳來區(qū)分。圖2中內(nèi)容列的中內(nèi)容列的t3、t5和和t6表明其中保存了在表明其中保存了在t3、t5和和t6這三個時間獲取的這三個時間獲取的網(wǎng)頁。網(wǎng)頁。Bigtable中的時間戳是中的時間戳是64位整型數(shù)，具體的賦值方式可以采取位整型數(shù)，具體的賦值方式可以采取系統(tǒng)默認(rèn)的方式，也可以用戶自行定義系統(tǒng)默認(rèn)的方式，也可以用戶自行定義 為了簡化不同版本的數(shù)據(jù)管理，為了簡化不同版本的數(shù)據(jù)管理，Bigtable目前提供了兩種設(shè)置：一目前提供了兩種設(shè)置：一種是種是保留最近的保留最近的N個不同版本個不同版本，圖中數(shù)據(jù)模型采取的就是這種方法，圖中數(shù)據(jù)模型采取的就是這

42、種方法，它保存最新的三個版本數(shù)據(jù)。另一種就是它保存最新的三個版本數(shù)據(jù)。另一種就是保留限定時間內(nèi)的所有不同保留限定時間內(nèi)的所有不同版本版本，比如可以保存最近，比如可以保存最近10天的所有不同版本數(shù)據(jù)。失效的版本將會天的所有不同版本數(shù)據(jù)。失效的版本將會由由Bigtable的垃圾回收機制自動處理的垃圾回收機制自動處理 “內(nèi)容： ” “錨點：” “錨點：my.look.ca” “n.www” “” “” “” “CNN.com” “CNN” t3 t5 t6 t8 t9 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable 設(shè)計動機與目標(biāo) 數(shù)據(jù)模型 系統(tǒng)架構(gòu) 主服務(wù)器 子表服務(wù)器 性能優(yōu)化 系統(tǒng)架構(gòu) 一個分布式的任務(wù)調(diào)

43、度器，主要一個分布式的任務(wù)調(diào)度器，主要被用來處理分布式系統(tǒng)隊列分組被用來處理分布式系統(tǒng)隊列分組和任務(wù)調(diào)度和任務(wù)調(diào)度 系統(tǒng)架構(gòu) 在Bigtable中Chubby主要有以下幾個作用：（1）選取并保證同一時間內(nèi)只有一個主服務(wù)器（Master Server）（2）獲取子表的位置信息（3）保存Bigtable的模式信息及訪問控制列表 另外在Bigtable的實際執(zhí)行過程中，Google的MapReduce和Sawzall也被用來改善其性能系統(tǒng)架構(gòu) Bigtable主要由三個部分組成：客戶端程序庫（主要由三個部分組成：客戶端程序庫（Client Library）、一）、一個主服務(wù)器（個主服務(wù)器（Maste

44、r Server）和多個子表服務(wù)器（）和多個子表服務(wù)器（Tablet Server） 客戶訪問客戶訪問Bigtable服務(wù)時，首先要利用其庫函數(shù)執(zhí)行服務(wù)時，首先要利用其庫函數(shù)執(zhí)行Open()操作來打開一操作來打開一個鎖（實際上就是個鎖（實際上就是獲取了文件目錄獲取了文件目錄），鎖打開以后客戶端就可以和子表服務(wù)），鎖打開以后客戶端就可以和子表服務(wù)器進行通信器進行通信 和許多具有單個主節(jié)點分布式系統(tǒng)一樣，客戶端主要與子表服務(wù)器通信，和許多具有單個主節(jié)點分布式系統(tǒng)一樣，客戶端主要與子表服務(wù)器通信，幾乎不和主服務(wù)器進行通信，這使得主服務(wù)器的幾乎不和主服務(wù)器進行通信，這使得主服務(wù)器的負載大大降低負載大大

45、降低 主服務(wù)主要進行一些元數(shù)據(jù)操作以主服務(wù)主要進行一些元數(shù)據(jù)操作以及子表服務(wù)器之間負載調(diào)度問題，及子表服務(wù)器之間負載調(diào)度問題，實際數(shù)據(jù)是存儲在子表服務(wù)器上實際數(shù)據(jù)是存儲在子表服務(wù)器上 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable 設(shè)計動機與目標(biāo) 數(shù)據(jù)模型 系統(tǒng)架構(gòu) 主服務(wù)器 子表服務(wù)器 性能優(yōu)化 主服務(wù)器 當(dāng)一個新子表產(chǎn)生時，主服務(wù)器通過一個加載命令將其分配給一個空當(dāng)一個新子表產(chǎn)生時，主服務(wù)器通過一個加載命令將其分配給一個空間足夠的子表服務(wù)器。創(chuàng)建新表、表合并以及較大子表的分裂都會產(chǎn)間足夠的子表服務(wù)器。創(chuàng)建新表、表合并以及較大子表的分裂都會產(chǎn)生一個或多個新子表。對于前面兩種，主服務(wù)器會生一個或多個新子表

46、。對于前面兩種，主服務(wù)器會自動檢測自動檢測到，而較到，而較大子表的分裂是大子表的分裂是由子服務(wù)由子服務(wù)發(fā)起并完成的，所以主服務(wù)器并不能自動檢發(fā)起并完成的，所以主服務(wù)器并不能自動檢測到，因此在分割完成之后子服務(wù)器需要向主服務(wù)測到，因此在分割完成之后子服務(wù)器需要向主服務(wù)發(fā)出一個通知發(fā)出一個通知 由于系統(tǒng)設(shè)計之初就要求能達到良好的擴展性，所以主服務(wù)器必須對由于系統(tǒng)設(shè)計之初就要求能達到良好的擴展性，所以主服務(wù)器必須對子表服務(wù)器的狀態(tài)進行子表服務(wù)器的狀態(tài)進行監(jiān)控監(jiān)控，以便及時檢測到服務(wù)器的加入或撤銷，以便及時檢測到服務(wù)器的加入或撤銷 Bigtable中主服務(wù)器對子表服務(wù)器的監(jiān)控是通過中主服務(wù)器對子表服務(wù)

47、器的監(jiān)控是通過Chubby完成的完成的子表服務(wù)器在初始化時都會從子表服務(wù)器在初始化時都會從Chubby中得到一個中得到一個獨占鎖獨占鎖。通過這。通過這種方式所有子表服務(wù)器基本信息被保存在種方式所有子表服務(wù)器基本信息被保存在Chubby中一個稱為中一個稱為服務(wù)器服務(wù)器目錄目錄（Server Directory）的特殊目錄之中）的特殊目錄之中主服務(wù)器 主服務(wù)器會定期向其詢問主服務(wù)器會定期向其詢問獨占鎖的狀態(tài)獨占鎖的狀態(tài)。如果子表服務(wù)器的鎖丟失或。如果子表服務(wù)器的鎖丟失或沒有回應(yīng)，則此時可能有兩種情況沒有回應(yīng)，則此時可能有兩種情況 要么是要么是Chubby出現(xiàn)了問題出現(xiàn)了問題（雖然這種概率很小，但的

48、確存在，（雖然這種概率很小，但的確存在，Google自己也做過相關(guān)測試）自己也做過相關(guān)測試） 要么是要么是子表服務(wù)器自身出現(xiàn)了問題子表服務(wù)器自身出現(xiàn)了問題。對此主服務(wù)器首先自己嘗試獲。對此主服務(wù)器首先自己嘗試獲取這個獨占鎖，如果失敗說明取這個獨占鎖，如果失敗說明Chubby服務(wù)出現(xiàn)問題，需等待恢復(fù)；服務(wù)出現(xiàn)問題，需等待恢復(fù)；如果成功則說明如果成功則說明Chubby服務(wù)良好而子表服務(wù)器本身出現(xiàn)了問題服務(wù)良好而子表服務(wù)器本身出現(xiàn)了問題 當(dāng)在狀態(tài)監(jiān)測時發(fā)現(xiàn)某個子表服務(wù)器上負載過重時，主服務(wù)器會自動當(dāng)在狀態(tài)監(jiān)測時發(fā)現(xiàn)某個子表服務(wù)器上負載過重時，主服務(wù)器會自動對其進行對其進行負載均衡負載均衡操作操作 主

49、服務(wù)器 基于系統(tǒng)出現(xiàn)故障基于系統(tǒng)出現(xiàn)故障是一種常態(tài)的設(shè)計理念，每個主服務(wù)器被設(shè)是一種常態(tài)的設(shè)計理念，每個主服務(wù)器被設(shè)定了一個會話時間的限制。當(dāng)某個主服務(wù)器到時退出后，管理定了一個會話時間的限制。當(dāng)某個主服務(wù)器到時退出后，管理系統(tǒng)就會指定一個新的主服務(wù)器，這個系統(tǒng)就會指定一個新的主服務(wù)器，這個主服務(wù)器的啟動主服務(wù)器的啟動需要經(jīng)需要經(jīng)歷以下四個步驟歷以下四個步驟： （1）從）從Chubby中獲取一個獨占鎖，確保同一時間只有一個主服務(wù)器中獲取一個獨占鎖，確保同一時間只有一個主服務(wù)器 （2）掃描服務(wù)器目錄，發(fā)現(xiàn)目前活躍的子表服務(wù)器）掃描服務(wù)器目錄，發(fā)現(xiàn)目前活躍的子表服務(wù)器 （3）與所有的活躍子表服務(wù)器

50、取得聯(lián)系以便了解所有子表的分配情）與所有的活躍子表服務(wù)器取得聯(lián)系以便了解所有子表的分配情況況 （4）掃描元數(shù)據(jù)表，發(fā)現(xiàn)未分配的子表并將其分配到合適子表服務(wù)）掃描元數(shù)據(jù)表，發(fā)現(xiàn)未分配的子表并將其分配到合適子表服務(wù)器器如果元數(shù)據(jù)表未分配，則首先需要將根子表（如果元數(shù)據(jù)表未分配，則首先需要將根子表（Root Tablet）加入未分配的子表中。）加入未分配的子表中。由于根子表保存了其他所有元數(shù)據(jù)子表的信息，確保了掃描能夠發(fā)現(xiàn)所有未分配由于根子表保存了其他所有元數(shù)據(jù)子表的信息，確保了掃描能夠發(fā)現(xiàn)所有未分配的子表的子表 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable 設(shè)計動機與目標(biāo) 數(shù)據(jù)模型 系統(tǒng)架構(gòu) 主服務(wù)器 子表

51、服務(wù)器 性能優(yōu)化 SSTable及子表基本結(jié)構(gòu) 64KB 塊 塊 . 索引 SSTable 塊 塊 SSTable 日志 . . 索引 64KB 64KB 64KB SSTable是Google為Bigtable設(shè)計的內(nèi)部數(shù)據(jù)存儲格式。所有的SSTable文件都存儲在GFS上 SSTable中數(shù)據(jù)被劃分成一個中數(shù)據(jù)被劃分成一個個的個的塊塊（Block），每個塊的大），每個塊的大小是可以設(shè)置的，一般為小是可以設(shè)置的，一般為64KB在在SSTable的結(jié)尾有一個的結(jié)尾有一個索引索引（Index），這個索引保存了塊），這個索引保存了塊的位置信息，在的位置信息，在SSTable打開時打開時這個索引會被

52、加載進內(nèi)存，用這個索引會被加載進內(nèi)存，用戶在查找某個塊時首先在內(nèi)存戶在查找某個塊時首先在內(nèi)存中查找塊的中查找塊的位置信息位置信息，然后在，然后在硬盤上直接找到這個塊硬盤上直接找到這個塊由于每個由于每個SSTable一般都不是一般都不是很大，用戶還可以選擇將其很大，用戶還可以選擇將其整整體加載進內(nèi)存體加載進內(nèi)存，這樣查找起來，這樣查找起來會更快會更快 SSTable結(jié)構(gòu)結(jié)構(gòu) 子表實際組成子表實際組成 每個子表都是由每個子表都是由多個多個SSTableSSTable以以及日志（及日志（LogLog）文件）文件構(gòu)成構(gòu)成 不同子表的不同子表的SSTableSSTable可以可以共享共享Bigtable

53、中的日志文件是一種中的日志文件是一種共享日志共享日志，每，每個子表服務(wù)器上僅保存一個日志文件，某個子個子表服務(wù)器上僅保存一個日志文件，某個子表日志只是這個共享日志的表日志只是這個共享日志的一個片段一個片段。這樣會。這樣會節(jié)省大量的空間節(jié)省大量的空間，但在恢復(fù)時卻有，但在恢復(fù)時卻有一定的難度一定的難度Google為了避免這種情況出現(xiàn)，對日志做了為了避免這種情況出現(xiàn)，對日志做了一些改進。一些改進。Bigtable規(guī)定將日志的內(nèi)容按照規(guī)定將日志的內(nèi)容按照鍵鍵值進行排序值進行排序，這樣不同的子表服務(wù)器都可以連，這樣不同的子表服務(wù)器都可以連續(xù)讀取日志文件了續(xù)讀取日志文件了一般來說每個子表的大小在一般來說

54、每個子表的大小在100MB到到200MB之間。每個子表服務(wù)器上保存的子表數(shù)量可以之間。每個子表服務(wù)器上保存的子表數(shù)量可以從幾十到上千不等，通常情況下是從幾十到上千不等，通常情況下是100個左右個左右 子表地址結(jié)構(gòu) Chubby 文件 根子表 （元數(shù)據(jù)表中第一條記錄） 用戶表 1 用戶表 N 其他元數(shù)據(jù)子表 子表地址的查詢查詢是經(jīng)常碰到的操作。在Bigtable系統(tǒng)的內(nèi)部采用的是一種類似類似B+樹的三層查詢體系樹的三層查詢體系 所有子表地址都被記錄在所有子表地址都被記錄在元數(shù)據(jù)表元數(shù)據(jù)表中，元數(shù)據(jù)表也是由一個個的中，元數(shù)據(jù)表也是由一個個的元數(shù)元數(shù)據(jù)子表據(jù)子表（Metadata tablet）組成

55、）組成根子表是元數(shù)據(jù)表中一個比較特殊的子表，它既是根子表是元數(shù)據(jù)表中一個比較特殊的子表，它既是元數(shù)據(jù)表的第一條記元數(shù)據(jù)表的第一條記錄，也包含了其他元數(shù)據(jù)子表的地址錄，也包含了其他元數(shù)據(jù)子表的地址，同時，同時Chubby中的一個文件也存儲中的一個文件也存儲了這個根子表的信息。了這個根子表的信息。查詢時，查詢時，首先首先從從Chubby中提取這個根子表的地址，中提取這個根子表的地址，進而進而讀取所需的元讀取所需的元數(shù)據(jù)子表的位置，數(shù)據(jù)子表的位置，最后最后就可以從元數(shù)據(jù)子表中找到待查詢的子表。除了就可以從元數(shù)據(jù)子表中找到待查詢的子表。除了這些子表的元數(shù)據(jù)之外，元數(shù)據(jù)表中還保存了其他一些有利于調(diào)試和分

56、這些子表的元數(shù)據(jù)之外，元數(shù)據(jù)表中還保存了其他一些有利于調(diào)試和分析的信息，比如析的信息，比如事件日志事件日志等等 Chubby 文件 根子表 （元數(shù)據(jù)表中第一條記錄） 用戶表 1 用戶表 N 其他元數(shù)據(jù)子表 為了減少訪問開銷，提高客戶訪問效率，為了減少訪問開銷，提高客戶訪問效率，BigtableBigtable使用了使用了緩存緩存（CacheCache）和和預(yù)?。A(yù)?。≒refetchPrefetch）技術(shù)技術(shù) 子表的地址信息被子表的地址信息被緩存緩存在客戶端，客戶在尋址時直接根據(jù)緩存信息進行查在客戶端，客戶在尋址時直接根據(jù)緩存信息進行查找。一旦出現(xiàn)緩存為空或緩存信息過時的情況，客戶端就需要按照

57、圖示方式找。一旦出現(xiàn)緩存為空或緩存信息過時的情況，客戶端就需要按照圖示方式進行網(wǎng)絡(luò)的來回通信（進行網(wǎng)絡(luò)的來回通信（Network Round-tripsNetwork Round-trips）進行尋址，在）進行尋址，在緩存為空的情況緩存為空的情況下下需要三個網(wǎng)絡(luò)來回通信。如果需要三個網(wǎng)絡(luò)來回通信。如果緩存的信息是過時緩存的信息是過時的，則需要六個網(wǎng)絡(luò)來回的，則需要六個網(wǎng)絡(luò)來回通信。其中三個用來確定信息是過時的，另外三個獲取新的地址通信。其中三個用來確定信息是過時的，另外三個獲取新的地址 預(yù)取預(yù)取則是在每次訪問元數(shù)據(jù)表時不僅僅讀取所需的子表元數(shù)據(jù)，而是讀取則是在每次訪問元數(shù)據(jù)表時不僅僅讀取所需的子表元數(shù)據(jù)，而是讀取多個子表的元數(shù)據(jù)，這樣下次需要時就不用再次訪問元數(shù)據(jù)表多個子表的元數(shù)據(jù)，這樣下次需要時就不用再次訪問元數(shù)據(jù)表 Chubby 文件 根子表 （元數(shù)據(jù)表中第一條記錄） 用戶表 1 用戶表 N 其他元數(shù)據(jù)子表 子表數(shù)據(jù)存儲及讀/寫操作 內(nèi) 存 表 寫 操 作 讀 操 作 子 表 日 志 內(nèi) 存 GFS SSTable文 件 Bigtable數(shù)據(jù)存儲及讀數(shù)據(jù)存儲及讀/寫操作寫操作 Bigtable將數(shù)據(jù)存儲劃分成兩塊：將數(shù)據(jù)存儲劃分成兩塊：較新的數(shù)據(jù)存