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

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

2、靈活性 GFS使用Chubby選取一個(gè)GFS主服務(wù)器 Bigtable使用Chubby指定一個(gè)主服務(wù)器并發(fā)現(xiàn)、控制與其相關(guān)的子表服務(wù)器 Chubby還可以作為一個(gè)穩(wěn)定的存儲(chǔ)系統(tǒng)存儲(chǔ)包括元數(shù)據(jù)在內(nèi)的小數(shù)據(jù) Google內(nèi)部還使用Chubby進(jìn)行名字服務(wù)（Name Server）ChubbyChubby GoogleGoogle設(shè)計(jì)的提供粗粒度鎖服務(wù)的一個(gè)設(shè)計(jì)的提供粗粒度鎖服務(wù)的一個(gè)文件系統(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)相同的各個(gè)節(jié)點(diǎn)在執(zhí)行相同的操作中初始狀態(tài)相同的各個(gè)節(jié)點(diǎn)在執(zhí)行相同的操作序列時(shí)，看到的指令序列是完全一致的，并且序列時(shí)，看到的指令序列是完全一致的，并且最終得到完全一致的結(jié)果最終得到完全一致的結(jié)果 一個(gè)最簡(jiǎn)單的方案在分布式系統(tǒng)中設(shè)置一個(gè)專門節(jié)點(diǎn)，在每次需要進(jìn)行操作之前，系統(tǒng)的各個(gè)部分向它發(fā)出請(qǐng)求，告訴該節(jié)點(diǎn)接下來系統(tǒng)要做什么。該節(jié)點(diǎn)接受第一個(gè)到達(dá)的請(qǐng)求內(nèi)容作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22、中只有涉及鎖的操作才需要序號(hào)，其他一概不用。在文件操作中，用戶可以將句柄看做一個(gè)指向文件系統(tǒng)的指針 函 數(shù) 名 稱作 用Open()打開某個(gè)文件或者目錄來創(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é)點(diǎn)沒有子節(jié)點(diǎn)的話則執(zhí)行刪除操作Acquire()獲取鎖Release()釋放鎖GetSequenc

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

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

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

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

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

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

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

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

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

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

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

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

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

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

37、t64)string “內(nèi)容： ” “錨點(diǎn)：” “錨點(diǎn)：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ù)庫(kù)有很大不同，它和傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)有很大不同，它不支持一般意義上的不支持一般意義上的事務(wù)，但能保證對(duì)于行的讀寫操作具有原子性（事務(wù)，但能保證對(duì)于行的讀寫操作具有原子性（Atomic） 表中數(shù)據(jù)都是根據(jù)行關(guān)鍵字進(jìn)行排序的，排序使用的是

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

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

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

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

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

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

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

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

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

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

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

49、服務(wù)器 基于系統(tǒng)出現(xiàn)故障基于系統(tǒng)出現(xiàn)故障是一種常態(tài)的設(shè)計(jì)理念，每個(gè)主服務(wù)器被設(shè)是一種常態(tài)的設(shè)計(jì)理念，每個(gè)主服務(wù)器被設(shè)定了一個(gè)會(huì)話時(shí)間的限制。當(dāng)某個(gè)主服務(wù)器到時(shí)退出后，管理定了一個(gè)會(huì)話時(shí)間的限制。當(dāng)某個(gè)主服務(wù)器到時(shí)退出后，管理系統(tǒng)就會(huì)指定一個(gè)新的主服務(wù)器，這個(gè)系統(tǒng)就會(huì)指定一個(gè)新的主服務(wù)器，這個(gè)主服務(wù)器的啟動(dòng)主服務(wù)器的啟動(dòng)需要經(jīng)需要經(jīng)歷以下四個(gè)步驟歷以下四個(gè)步驟： （1）從）從Chubby中獲取一個(gè)獨(dú)占鎖，確保同一時(shí)間只有一個(gè)主服務(wù)器中獲取一個(gè)獨(dú)占鎖，確保同一時(shí)間只有一個(gè)主服務(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è)計(jì)動(dòng)機(jī)與目標(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è)計(jì)的內(nèi)部數(shù)據(jù)存儲(chǔ)格式。所有的SSTable文件都存儲(chǔ)在GFS上 SSTable中數(shù)據(jù)被劃分成一個(gè)中數(shù)據(jù)被劃分成一個(gè)個(gè)的個(gè)的塊塊（Block），每個(gè)塊的大），每個(gè)塊的大小是可以設(shè)置的，一般為小是可以設(shè)置的，一般為64KB在在SSTable的結(jié)尾有一個(gè)的結(jié)尾有一個(gè)索引索引（Index），這個(gè)索引保存了塊），這個(gè)索引保存了塊的位置信息，在的位置信息，在SSTable打開時(shí)打開時(shí)這個(gè)索引會(huì)被

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

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

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

55、）組成根子表是元數(shù)據(jù)表中一個(gè)比較特殊的子表，它既是根子表是元數(shù)據(jù)表中一個(gè)比較特殊的子表，它既是元數(shù)據(jù)表的第一條記元數(shù)據(jù)表的第一條記錄，也包含了其他元數(shù)據(jù)子表的地址錄，也包含了其他元數(shù)據(jù)子表的地址，同時(shí)，同時(shí)Chubby中的一個(gè)文件也存儲(chǔ)中的一個(gè)文件也存儲(chǔ)了這個(gè)根子表的信息。了這個(gè)根子表的信息。查詢時(shí)，查詢時(shí)，首先首先從從Chubby中提取這個(gè)根子表的地址，中提取這個(gè)根子表的地址，進(jìn)而進(jìn)而讀取所需的元讀取所需的元數(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ù) 子表的地址信息被子表的地址信息被緩存緩存在客戶端，客戶在尋址時(shí)直接根據(jù)緩存信息進(jìn)行查在客戶端，客戶在尋址時(shí)直接根據(jù)緩存信息進(jìn)行查找。一旦出現(xiàn)緩存為空或緩存信息過時(shí)的情況，客戶端就需要按照

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