《云計算(第三版)》第2章-Google云計算原理與應用(二)-2

of56第2章Google云計算原理與應用（二）《云計算》第三版配套PPT課件ooff

5566目錄2.1

Google文件系統(tǒng)GFS分布式數(shù)據(jù)處理MapReduce分布式鎖服務Chubby分布式結(jié)構化數(shù)據(jù)表Bigtable分布式存儲系統(tǒng)Megastore大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構Dapper海量數(shù)據(jù)的交互式分析工具Dremel內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrillGoogle應用程序引擎56《云計算》第三版配套PPT課件初步了解ChubbyChubby是Google設計的提供粗粒度鎖服務的一個文件系統(tǒng)，它基于松耦合分布式系統(tǒng)，解決了分布的一致性問題。通過使用Chubby的鎖

服務，用戶可以確保數(shù)據(jù)操作過程中的一致性Chubby作為一個穩(wěn)定

的存儲系統(tǒng)存儲包括元數(shù)據(jù)在內(nèi)的小數(shù)據(jù)Google內(nèi)部還使用Chubby進行名字服務（Name

Server）3

of2.3分布式鎖服務Chubby《云計算》第三版配套PPT課件Paxos算法Paxos算法Leslie

Lamport最先提出的一種基于消息傳遞（MessagesPassing）的一致性算法，用于解決分布式系統(tǒng)中的一致性問題分布式系統(tǒng)一致性問題——就是如何保證系統(tǒng)中初始狀態(tài)相同的各個節(jié)點在執(zhí)行相同的操作序列時，看到的指令序列是完全一致的，并且最終得到完全一致的結(jié)果一個最簡單的方案——在分布式系統(tǒng)中設置一個專門節(jié)點，在每次需要進行操作之前，系統(tǒng)的各個部分向它發(fā)什么。該節(jié)點接受第一個到達的請求內(nèi)容作為接下來的操作，這樣就能夠保證系統(tǒng)只有一個唯一的操作序列方案存在什么出缺請求陷，？告訴該節(jié)點接下來系統(tǒng)要做of56《云計算》第三版配套PPT課件Paxos算法缺陷——專門節(jié)點失效，整個系統(tǒng)就很可能出現(xiàn)不一致。為了避免這種情況，在系統(tǒng)中必然要設置多個專門節(jié)點，由這些節(jié)點來共同決定操作序列Paxos算法proposers提出決議（Value，系統(tǒng)接下來執(zhí)行的指令）acceptors批準決議learners獲取并使用已經(jīng)通過的決議of56《云計算》第三版配套PPT課件ooff

55662.3分布式鎖服務ChubbyPaxos算法Chubby系統(tǒng)設計Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能《云計算》第三版配套PPT課件Paxos算法proposersacceptors提出決議批準決議三類

節(jié)點learners

獲取并使用已經(jīng)通過的決議決議只有在被proposers提出后才能批準每次只批準一個決議只有決議確定被批準后learners才能獲取這個決議三個7

of56條件2.3分布式鎖服務Chubby《云計算》第三版配套PPT課件系統(tǒng)的約束條件p1：每個acceptor只接受它得到的第一個決議。p2：一旦某個決議得到通過，之后通過的決議必須和該決議保持一致。p2a：一旦某個決議v得到通過，之后任何acceptor再批準的決議必須是v。p2b：一旦某個決議v得到通過，之后任何proposer再提出的決議必須是v。p2c：如果一個編號為n的提案具有值v，那么存在一個“多數(shù)派”，要么它們中沒有誰批準過編號小于n的任何提案，要么它們進行的最近一次批準具有值v。為了保證決議的唯一性，acceptors也要滿足一個約束條件：當且僅當acceptors沒有收到編號大于n的請求時，acceptors才批準編號為n的提案。8

of562.3分布式鎖服務Chubby《云計算》第三版配套PPT課件1準備階段2批準階段一個決議分為兩個階段proposers選擇一個提案并將它的編號設為n將它發(fā)送給acceptors中的一個“多數(shù)派”acceptors收到后，如果提案的編號大于它已經(jīng)回復的所有消息，則acceptors將自己上次的批準回復給proposers，并不再批準小于n的提案。當proposers接收到acceptors中的這個“多數(shù)派”的回復后，就向回復請求的acceptors發(fā)送accept請求，在符合acceptors一方的約束條件下，acceptors收到accept請求后即批準這個請求。9

of562.3分布式鎖服務Chubbyof56《云計算》第三版配套PPT課件2.3分布式鎖服務ChubbyPaxos算法Chubby系統(tǒng)設計Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能56《云計算》第三版配套PPT課件54611

ofChubby的設計目標主要有以下幾點高可用性和高可靠性213高擴展性支持粗粒度的建議性鎖服務服務信息的直接存儲支持通報機制支持緩存機制2.3分布式鎖服務Chubby《云計算》第三版配套PPT課件設計目標Chubby系統(tǒng)設計高可用性和高可靠性；首要目標，在保證這一目標的基礎上再考慮系統(tǒng)的吞吐量和存儲能力高擴展性；將數(shù)據(jù)存儲在價格較為低廉的RAM，支持大規(guī)模用戶訪問文件支持粗粒度的建議性鎖服務；提供這種服務的根本目的是提高系統(tǒng)的性能服務信息的直接存儲；可直接存儲包括元數(shù)據(jù)、系統(tǒng)參數(shù)在內(nèi)的有關服務信息支持通報機制；客戶可以及時地了解到事件發(fā)生支持緩存機制；通過一致性緩存將常用信息保存在客戶端，避免了頻繁o地f

56訪問主服務器56《云計算》第三版配套PPT課件Chubby系統(tǒng)設計Chubby中還添加了一些新的功能特性；這種設計主要是考慮到以下幾個問題030201開發(fā)者初期很少考慮系統(tǒng)的一致性，但隨著開發(fā)進行，問題會變得越來越嚴重。單獨的鎖服務可以保證原有系統(tǒng)架構不會發(fā)生改變，而使用函數(shù)庫很可能需要對系統(tǒng)架構做出大幅度的改動系統(tǒng)中很多事件發(fā)生是需要告知其他用戶和服務器，使用一個基于文件系統(tǒng)的鎖服務可以將這些變動寫入文件中。有需要的用戶和服務器直接訪問這些文件即可，避免因大量系統(tǒng)組件之間事件通信帶來系統(tǒng)性能下降of基于鎖的開發(fā)接口容易被開發(fā)者接受。雖然在分布式系統(tǒng)中鎖的使用會有很大的不同，但是和一致性算法相比，鎖顯然被更多的開發(fā)者所熟知《云計算》第三版配套PPT課件Chubby系統(tǒng)設計Paxos算法實現(xiàn)過程中需要一個“多數(shù)派”就某個值達成一致，本質(zhì)上就是分布式系統(tǒng)中常見的quorum機制；為保證系統(tǒng)高可用性，需要若干臺機器，但使用單獨鎖服務的話一臺機器也能保證這種高可用性Chubby設計過程中一些細節(jié)問題值得關注：在Chubby系統(tǒng)中采用了建議性的鎖而沒有采用強制性的鎖。兩者的根本區(qū)別在于用戶訪問某個被鎖定的文件時，建議性的鎖不會阻止訪問，而強制性的鎖則會阻止訪問，實際上這是為了方便系統(tǒng)組件之間的信息交互另外，Chubby還采用了粗粒度（Coarse-Grained）鎖服務而沒有采用細粒度（Fine-Grained）鎖服務，兩者的差異在于持有鎖的時間，細粒度的鎖持有時間很短of

5656《云計算》第三版配套PPT課件客戶端應用程序客戶端應用程序Chubby程序率Chubby程序率…遠程過程調(diào)用Chubby單元的五個服務器主服務器客戶端進程15

ofChubby的基本架構在客戶這一端每個客戶應用程序都有

一個Chubby程序庫（ChubbyLibrary），客戶端的所有應用都是通過調(diào)用這個庫中的相關函數(shù)來完成的。服務器一端稱為Chubby單元，一般

是由五個稱為副本（Replica）的服務器組成的，這五個副本在配置上完全一致，并且在系統(tǒng)剛開始時處于對等地位?？蛻舳朔掌鞫?.3分布式鎖服務Chubby《云計算》第三版配套PPT課件2.3分布式鎖服務ChubbyPaxos算法Chubby系統(tǒng)設計Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能of56《云計算》第三版配套PPT課件Chubby中的Paxos單個Chubby副本結(jié)構容錯日志——對數(shù)據(jù)庫正確性提供重要支持；一致性由Paxos算法保證；副本之間通過特定的Paxos協(xié)議通信，同時本地文件中保存與Chubby中相同的日志數(shù)據(jù)容錯數(shù)據(jù)庫——快照（Snapshot）和記錄數(shù)據(jù)庫操作重播日志（Replay-log）；每一次的數(shù)據(jù)庫操作最終都將提交至日志中；本地文件中也保存著一份數(shù)據(jù)庫數(shù)據(jù)副本of56Chubby構建在這個容錯的數(shù)據(jù)庫之上，Chubby利用這個數(shù)據(jù)庫存儲所有的數(shù)據(jù)。Chubby的客戶端通過特定的Chubby協(xié)議和單個的Chubby副本進行通信《云計算》第三版配套PPT課件Chubby中的Paxos容錯日志的APIt

nlContent

TitleChubby中Paxos算法過程of562、協(xié)調(diào)者從客戶提交的值中選擇一個，accept消息廣播給所有的副本，其他的副本收到廣播后，選擇接受或者拒絕這個值，并將決定結(jié)果反饋3、協(xié)調(diào)者收到大多數(shù)副本接受信息后，認為達到了一致性，接著向相關副本發(fā)送一個commit消息1、選擇一副本為協(xié)調(diào)者（Coordinator）《云計算》第三版配套PPT課件of56Chubby中的PaxosChubby設計者借鑒了Paxos的兩種解決機制：給協(xié)調(diào)者指派序號或限制協(xié)調(diào)者可以選擇的值指派序號的方法在一個有n個副本系統(tǒng)中，為每個副本分配一個id:ir，其中0≤ir≤n-1。則副本的序號s=k*n+ir，其中k的初始值為0某個副本想成為協(xié)調(diào)者之后，它就根據(jù)規(guī)則生成一個比它以前的序號更大的序號（實際上就是提高k的值），并將這個序號通過

propose消息廣播給其他所有的副本如果接受到廣播的副本發(fā)現(xiàn)該序號比它以前見過的序號都大，則向發(fā)出廣播的副本返回一個promise消息，并且承諾不再接受舊的協(xié)調(diào)者發(fā)送的消息。如果大多數(shù)副本都返回了promise消息，則新的協(xié)調(diào)者就產(chǎn)生了限制協(xié)調(diào)者可以選擇的值Paxos強制新的協(xié)調(diào)者必須選擇和前任相同的值《云計算》第三版配套PPT課件of56Chubby中的PaxosChubby做了一個重要優(yōu)化來提高系統(tǒng)效率—在選擇某一個副本作為協(xié)調(diào)者之后就長期不變，此時協(xié)調(diào)者就被稱為主服務器（Master）客戶端的數(shù)據(jù)請求由主服務器完成，Chubby保證在一定時間內(nèi)有且僅有一個主服務器，這個時間就稱為主服務器租約期（Master

Lease）客戶端需要確定主服務器的位置，可向DNS發(fā)送一個主服務器定位請求，非主服務器的副本將對該請求做出回應Chubby對于Paxos論文中未提及的一些技術細節(jié)進行了補充，所以Chubby的實現(xiàn)是基于Paxos，但其技術手段更加的豐富，更具有實踐性《云計算》第三版配套PPT課件2.3分布式鎖服務ChubbyPaxos算法Chubby系統(tǒng)設計Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能of56《云計算》第三版配套PPT課件of56Chubby文件系統(tǒng)Chubby系統(tǒng)本質(zhì)上就是一個分布式的、存儲大量小文件的文件系統(tǒng)，它所有的操作都是在文件的基礎上完成Chubby最常用的鎖服務中，每一個文件就代表一個鎖，用戶通過打開、關閉和讀取文件，獲取共享（Shared）鎖或獨占（Exclusive）鎖選舉主服務器過程中，符合條件的服務器都同時申請打開某個文件并請求鎖住該文件成功獲得鎖的服務器自動成為主服務器并將其地址寫入這個文件夾，以便其他服務器和用戶可以獲知主服務器的地址信息《云計算》第三版配套PPT課件of56Chubby文件系統(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中并沒有符號連接（Symbolic

Link，又叫軟連接，類似于Windows系統(tǒng)中的快捷方式）和硬連接（Hard

Link，類似于別名）的概念在具體實現(xiàn)時，文件系統(tǒng)由許多節(jié)點組成，分為永久型和臨時型，每個節(jié)點就是一個文件或目錄。節(jié)點中保存著包括ACL（Access

Control

List，訪問控制列表）在內(nèi)的多種系統(tǒng)元數(shù)據(jù)56《云計算》第三版配套PPT課件24

of單調(diào)遞增的64位編號新節(jié)點實例號必定大于舊節(jié)點的實例號。1

實例號Instance

Number鎖被用戶持有時該號增加。內(nèi)容生成號Content

Generation

Number文件內(nèi)容修改時該號增加。23

鎖生成號Lock

Generation

NumberACL生成號ACL

Generation

NumberACL名被覆寫時該號增加。42.3分布式鎖服務Chubbyof56《云計算》第三版配套PPT課件Chubby文件系統(tǒng)序號：確定句柄由當前還是以前的主服務器創(chuàng)建2模式信息：用于新的主服務器重新創(chuàng)建一個舊句柄3用戶打開某個節(jié)點的同時會獲取一個類似于UNIX中文件描述符（File

Descriptor）的句柄，這個句柄由以下三個部分組成校驗數(shù)位：防止其他用戶創(chuàng)建或猜測這個句柄1of《云計算》第三版配套PPT課件Chubby文件系統(tǒng)在實際執(zhí)行中，為了避免所有的通信都使用序號帶來系統(tǒng)開銷增長，Chubby引入了sequencer的概念sequencer實際上就是一個序號，只能由鎖的持有者在獲取鎖時向系統(tǒng)發(fā)出請求來獲得。這樣一來Chubby系統(tǒng)中只有涉及鎖的操作才需要序號，其他一概不用。在文件操作中，用戶可以將句柄看做一個指向文件系統(tǒng)的指針函數(shù)名稱作用Open()打開某個文件或者目錄來創(chuàng)建句柄Close()關閉打開的句柄，后續(xù)的任何操作都將中止Poison()中止當前未完成及后續(xù)的操作，但不關閉句柄GetContentsAndStat()返回文件內(nèi)容及元數(shù)據(jù)GetStat()只返回文件元數(shù)據(jù)ReadDir()返回子目錄名稱及其元數(shù)據(jù)SetContents()向文件中寫入內(nèi)容SetACL()設置ACL名稱Delete()如果該節(jié)點沒有子節(jié)點的話則執(zhí)行刪除操作Acquire()獲取鎖Release()釋放鎖GetSequencer()返回一個sequencerSetSequencer()將sequencer和某個句柄進行關聯(lián)CheckSequencer()檢查某個sequencer是否有效56常用句柄函數(shù)及其作用《云計算》第三版配套PPT課件2.3分布式鎖服務ChubbyPaxos算法Chubby系統(tǒng)設計Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能of56《云計算》第三版配套PPT課件Chubby系統(tǒng)設計Chubby基本架構：客戶端和服務器端，兩者通過遠程過程調(diào)用（RPC）來連接客戶端每個客戶應用程序都有一個Chubby程序庫（Chubby

Library），所有應用都是通過調(diào)用這個庫中相關函數(shù)來完成服務器一端Chubby單元，一般由五個稱為副本（Replica）服務器組成，它們配置上完全一致，且系統(tǒng)剛開始時處于對等地位of56《云計算》第三版配套PPT課件Chubby客戶端與服務器端的通信過程從左到右的水平方向表示時間在增加，斜向上的箭頭表示一次KeepAlive請求，斜向下的箭頭則是主服務器的一次回應M1、M2、M3表示不同的主服務器租約期；C1、C2、C3則是客戶端對主服務器租約期時長做出的一個估計KeepAlive是周期發(fā)送的一種信息，它主要有兩方面的功能：延遲租約的有效期和攜帶事件信息告訴用戶更新of5656《云計算》第三版配套PPT課件30

of可能出現(xiàn)的兩種故障2.3分布式鎖服務Chubby客戶端租約過期主服務器出錯12of56《云計算》第三版配套PPT課件客戶端租約過期故障處理客戶端向主服務器發(fā)出一個KeepAlive請求（上圖1）如果有需要通知的事件時則主服務器會立刻做出回應，否則等到客戶端的租約期C1快結(jié)束的時候才做出回應（圖2），并更新主服務器租約期

為M2客戶端接到回應后認為該主服務器仍處于活躍狀態(tài)，于是將租約期更新為C2并立刻發(fā)出新的KeepAlive請求（圖3）租約過期寬限期內(nèi)，客戶端不會立刻斷開其與服務器端的聯(lián)系，而是不斷地做探詢，當它接到客戶端的第一個KeepAlive請求（圖4）時會拒絕（圖5）客戶端在主服務器拒絕后使用新紀元號來發(fā)送KeepAlive請求（圖6）新的主服務器接受這個請求并立刻做出回應（圖7）如果客戶端接收到這個回應的時間仍處于寬限期內(nèi)，系統(tǒng)會恢復到安全狀態(tài)，租約期更新為C3。如果在寬限期未接到主服務器的相關回應，客戶端終止當前的會話《云計算》第三版配套PPT課件主服務器出錯故障處理務器出錯正常情況下舊的主服務器出現(xiàn)故障后系統(tǒng)會很快地選舉出新的主服務器，新選舉需要經(jīng)歷以下九個步驟：產(chǎn)生一個新的紀元號以便今后客戶端通信時使用，這能保證當前的主服務器不必處理針對舊的主服務器的請求只處理主服務器位置相關的信息，不處理會話相關的信息（3）構建處理會話和鎖所需的內(nèi)部數(shù)據(jù)結(jié)構如果這一過程在寬限期內(nèi)順利完成，則用戶不會感覺到任何故障的發(fā)生，也就是說新舊主服務器的替換對于用戶來說是透明（的4，）用允戶許客感戶覺端到發(fā)的送僅K僅ee是pA一li個ve延請遲求，不處理其他會話相關的信息向每個會話發(fā)送一個故障事件，促使所有的客戶端清空緩存等待直到所有的會話都收到故障事件或會話終止開始允許執(zhí)行所有的操作如果客戶端使用了舊的句柄則需要為其重新構建新的句柄of

56一定時間段后（1分鐘），刪除沒有被打開過的臨時文件夾of56《云計算》第三版配套PPT課件2.3分布式鎖服務ChubbyPaxos算法Chubby系統(tǒng)設計Chubby中的PaxosChubby文件系統(tǒng)通信協(xié)議正確性與性能56《云計算》第三版配套PPT課件34

of一致性2.3分布式鎖服務Chubby正確性與性能每個Chubby單元是由五

個副本組成的，這五個副本中需要選舉產(chǎn)生一個主服務器，這種選舉本質(zhì)上就是一個一致性問題安全性采用的是ACL形式的安全保障措施。只要不被覆寫，子節(jié)點都是直接繼承父節(jié)點的ACL名性能優(yōu)化提高主服務器默認的租約期、使用協(xié)議轉(zhuǎn)換服務將

Chubby協(xié)議轉(zhuǎn)換成較簡

單的協(xié)議、客戶端一致性緩存等《云計算》第三版配套PPT課件of56一致性每個Chubby單元是由五個副本組成的，這五個副本中需要選舉產(chǎn)生一個主服務器，這種選舉本質(zhì)上就是一個一致性問題。實際執(zhí)行過程中，Chubby使用Paxos算法來解決主服務器產(chǎn)生后客戶端的所有讀寫操作都是由主服務器來完成的讀操作很簡單，客戶直接從主服務器上讀取所需數(shù)據(jù)即可寫操作就會涉及數(shù)據(jù)一致性的問題；為了保證客戶的寫操作能夠同步到所有的服務器上，系統(tǒng)再次利用了Paxos算法《云計算》第三版配套PPT課件安全性Chubby用ACL形式安全保障措施。系統(tǒng)有三種

ACL名：寫ACL名（Write

ACL

Name）、讀ACL名（Read

ACLName）和變更ACL名（Change

ACL

Name）只要不被覆寫，子節(jié)點都是直接繼承父節(jié)點的ACL名ACL同樣被保存在文件中，它是節(jié)點元數(shù)據(jù)的一部分，用戶在進行相關操作時首先需要通過ACL來獲取相應的授權Chubby的ACL機制of56用戶chinacloud提出向文件CLOUD中寫入內(nèi)

容請求。CLOUD首先讀取自身的寫ACL名fun，接著在fun中查到了chinacloud這一行記錄，于是返回信息允許chinacloud對文件進行寫操作，此時chinacloud才被允許向CLOUD寫入

內(nèi)容。其他的操作和寫操作類似《云計算》第三版配套PPT課件of56性能優(yōu)化為滿足系統(tǒng)高可擴展性，Chubby目前已經(jīng)采取了一些措施：比如提高主服務器默認的租約期、使用協(xié)議轉(zhuǎn)換服務將Chubby協(xié)議轉(zhuǎn)換成較簡單的協(xié)議、客戶端一致性緩存等；除此之外，Google的工程師們還考慮使用代理（Proxy）和分區(qū)（Partition）技術代理可以減少主服務器處理KeepAlive以及讀請求帶來的服務器負載，但是它并不能減少寫操作帶來的通信量使用分區(qū)技術的話可以將一個單元的命名空間（NameSpace）劃分成N份。除了少量的跨分區(qū)通信外，大部分的分區(qū)都可以獨自地處理服務請求。通過分區(qū)可以減少各個分區(qū)上的讀寫通信量，但不能減少KeepAlive請求的通信量《云計算》第三版配套PPT課件目錄Google文件系統(tǒng)GFS分布式數(shù)據(jù)處理MapReduce分布式鎖服務Chubby分布式結(jié)構化數(shù)據(jù)表Bigtable分布式存儲系統(tǒng)Megastore大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構Dapper海量數(shù)據(jù)的交互式分析工具Dremel內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrillGoogle應用程序引擎38of56《云計算》第三版配套PPT課件2.4分布式結(jié)構化數(shù)據(jù)表Bigtable設計動機與目標數(shù)據(jù)模型系統(tǒng)架構主服務器子表服務器性能優(yōu)化of56《云計算》第三版配套PPT課件2.4分布式結(jié)構化數(shù)據(jù)表BigtableBigtable的設計動機123需要存儲的數(shù)據(jù)種類繁多海量的服務請求商用數(shù)據(jù)庫無法滿足需求包括URL、網(wǎng)頁內(nèi)容、用戶的個性化設置在內(nèi)的數(shù)據(jù)都是Google需要經(jīng)常處理的Google運行著目前世界上最繁忙的系統(tǒng)，它每時每刻處理的客戶服務請求數(shù)量是普通的系統(tǒng)根本無法承受的一方面現(xiàn)有商用數(shù)據(jù)庫的設計著眼點在于其通用性。

另一方面對于底層系統(tǒng)的完全掌控會給后期的系統(tǒng)維護、升級帶來極大的便利40

of56《云計算》第三版配套PPT課件2.4分布式結(jié)構化數(shù)據(jù)表BigtableBigtable應達到的基本目標廣泛的適用性41

of56很強的可擴展性高可用性簡單性Bigtable是為了滿足一系列Google產(chǎn)品而并非特定產(chǎn)品的存儲要求。根據(jù)需要隨時可以加入或撤銷服務器確保幾乎所有的情況下系統(tǒng)都可用底層系統(tǒng)的簡單性既可以減少系統(tǒng)出錯的概率，也為上層應用的開發(fā)帶來便利of56《云計算》第三版配套PPT課件2.4分布式結(jié)構化數(shù)據(jù)表Bigtable設計動機與目標數(shù)據(jù)模型系統(tǒng)架構主服務器子表服務器性能優(yōu)化《云計算》第三版配套PPT課件2.4分布式結(jié)構化數(shù)據(jù)表BigtableBigtable數(shù)據(jù)的存儲格式Bigtable是一個分布式多維映射表，表中的數(shù)據(jù)通過一個行關鍵字（Row

Key）、一個列關鍵字（Column

Key）以及一個時間戳（Time

Stamp）進行索引Bigtable對存儲在其中的數(shù)據(jù)不做任何解析，一律看做字符串Bigtable的存儲邏輯可以表示為：(row:string,

column:string,

time:int64)→string43

of56《云計算》第三版配套PPT課件2.4分布式結(jié)構化數(shù)據(jù)表BigtableBigtable數(shù)據(jù)的存儲格式假設想要拷貝一個可能被很多項目都使用的、很大的網(wǎng)頁集合以及相關的信息，把這個特定的表稱為Webtable。在Webtable當中，使用URL作為行鍵，網(wǎng)頁的不同方面作為列鍵，并把網(wǎng)頁的內(nèi)容存儲在contents:column中，如圖所示圖存儲了網(wǎng)頁數(shù)據(jù)的Webtable的一個片段。行名稱是反轉(zhuǎn)的URL，contents列家族包含了網(wǎng)頁內(nèi)容，anchor列家族包含了任何引用這個頁面的anchor文本。

CNN的主頁被Sports

Illustrated和MY-look主頁同時引用，因此，行包含了名稱為”anchor:”和”anchor:my.look.ca”的列。每個anchor單元格都只有一個版本，contents列有三個版本，分別對應于時間戳t3,t5和t6。44

of56《云計算》第三版配套PPT課件of56數(shù)據(jù)模型行Bigtable的行關鍵字可以是任意的字符串，但是大小不能超過64KB。

Bigtable和傳統(tǒng)的關系型數(shù)據(jù)庫有很大不同，它不支持一般意義上的

事務，但能保證對于行的讀寫操作具有原子性（Atomic）表中數(shù)據(jù)都是根據(jù)行關鍵字進行排序的，排序使用的是詞典序。一個典型實例，其中n.www就是一個行關鍵字。不直接存儲網(wǎng)頁地址而將其倒排是Bigtable的一個巧妙設計。這樣做至少會帶來以下兩個好處同一地址域的網(wǎng)頁會被存儲在表中的連續(xù)位置，有利于用戶查找和分析倒排便于數(shù)據(jù)壓縮，可以大幅提高壓縮率《云計算》第三版配套PPT課件of56數(shù)據(jù)模型列Bigtable并不是簡單地存儲所有的列關鍵字，而是將其組織成所謂的列族（Column

Family），每個族中的數(shù)據(jù)都屬于同一個類型，并且同族的數(shù)據(jù)會被壓縮在一起保存。引入了列族的概念之后，列關鍵字就采用下述的語法規(guī)則來定義：族名：限定詞（family：qualifier）族名必須有意義，限定詞則可以任意選定圖中，內(nèi)容（Contents）、錨點（Anchor）都是不同的族。而和my.look.ca則是錨點族中不同的限定詞族同時也是Bigtable中訪問控制（AccessControl）基本單元，也就是說訪問權限的設置是在族這一級別上進行的《云計算》第三版配套PPT課件of56數(shù)據(jù)模型時間戳Google的很多服務比如網(wǎng)頁檢索和用戶的個性化設置等都需要保存不同時間的數(shù)據(jù)，這些不同的數(shù)據(jù)版本必須通過時間戳來區(qū)分。圖2中內(nèi)容列的t3、t5和t6表明其中保存了在t3、t5和t6這三個時間獲取的網(wǎng)頁。Bigtable中的時間戳是64位整型數(shù)，具體的賦值方式可以采取

系統(tǒng)默認的方式，也可以用戶自行定義為了簡化不同版本的數(shù)據(jù)管理，Bigtable目前提供了兩種設置：一種是保留最近的N個不同版本，圖中數(shù)據(jù)模型采取的就是這種方法，它保存最新的三個版本數(shù)據(jù)。另一種就是保留限定時間內(nèi)的所有不同版本，比如可以保存最近10天的所有不同版本數(shù)據(jù)。失效的版本將會由Bigtable的垃圾回收機制自動處理《云計算》第三版配套PPT課件2.4分布式結(jié)構化數(shù)據(jù)表Bigtable設計動機與目標數(shù)據(jù)模型系統(tǒng)架構主服務器子表服務器性能優(yōu)化of56《云計算》第三版配套PPT課件Bigtable基本架構2.4分布式結(jié)構化數(shù)據(jù)表Bigtable49

of56《云計算》第三版配套PPT課件2.4分布式結(jié)構化數(shù)據(jù)表BigtableBigtable中Chubby的主要作用作用一50

of56選取并保證同一時間內(nèi)只有一個主服務器（MasterServer）。獲取子表的位置信息。保存Bigtable的模式信息及訪問控制列表。作用二作用三《云計算》第三版配套PPT課件of56系統(tǒng)架構Bigtable主要由三個部分組成：客戶端程序庫（Client

Library）、一服務器（Master

Server）和多個子表服務器（Tablet

Server）客戶訪問Bigtable服務時，首先要利用其庫函數(shù)執(zhí)行Open()操作來打開一個（實際上就是獲取了文件目錄），鎖打開以后客戶端就可以和子表服務器進行通信和許多具有單個主節(jié)點分布式系統(tǒng)一樣，客戶端主要與子表服務器通信，幾乎不和主服務器進行通信，這使得主服務器的負載大大降低主服務主要進行一些元數(shù)據(jù)操作以及子表服務器之間負載調(diào)度問題，實際數(shù)據(jù)是存儲在子表服務器上《云計算》第三版配套PPT課件2.4分布式結(jié)構化數(shù)據(jù)表Bigtable設計動機與目標數(shù)據(jù)模型系統(tǒng)架構主服務器子表服務器性能優(yōu)化of5656《云計算》第三版配套PPT課件53

of2.4分布式結(jié)構化數(shù)據(jù)表Bigtable主服務器新子表分配子表服務器狀態(tài)監(jiān)控子服務器之間的負載均衡當一個新的子表產(chǎn)生時，主服務器通過一個加載命令將其分配給一個空間足夠的子表服務器。創(chuàng)建新表、表合并以及較大子表的分裂都會產(chǎn)生一個或多個新子表。分割完成之后子服務器需要向主服務發(fā)出一個通知。主服務器必須對子表服務器的狀態(tài)進行監(jiān)控，以便及時檢測到服務器的加入或撤銷ooff

5566《云計算》主第三服版配務套PP器T課件Bigtable中主服務表服務器的監(jiān)控是通過Chubby完成的——子表服務器在初始化時都會從Chubby中得到一器對子個獨占鎖。通過這種方式所

有子表服務器基本信息被保存在Chubby中一個稱為服務器目錄（ServerDirectory）的特殊目錄之中。主服務器通過這個目錄可以隨時獲取最新的子表服務器信息，包括：目前活躍的子表服務器；每個子表服務器上現(xiàn)已分配的子表。ooff

5566《云計算》主第三服版配務套PP器T課件對于每個具體的子表服務器，主服務器會定期向其詢問獨占鎖的狀態(tài)。如果子表服務器的鎖丟失或沒有回應，則此時可能有兩種情況：要么是Chubby出現(xiàn)了問題（雖然這種概率很小，但的確存在，Google自己也做過相關測試）要么是子表服務器自身出現(xiàn)了問題。對此主服務器首先自己嘗試獲取這個獨占鎖，如果失敗說明Chubby服務出現(xiàn)問題，需等待恢復；如果成功則說明Chubby服務良好而子表服務器本身出現(xiàn)了問題當在狀態(tài)監(jiān)測時發(fā)現(xiàn)某個子表服務器上負載過重時，主服務器會自動對其進行負載均衡操作ooff

5566《云計算》主第三服版配務套PP器T課件基于系統(tǒng)出現(xiàn)故障是一種常態(tài)的設計理念，每個主服務器被設定了一個會話時間的限制。當某個主服務器到時退出后，管理系統(tǒng)就會指定一個新的主服務器，這個主服務器的啟動需要經(jīng)歷以下四個步驟：《云計算》第三版配套PPT課件57

of

562.4分布式結(jié)構化數(shù)據(jù)表Bigtable從Chubby中獲取

一個獨占鎖，確保同一時間只有一個主服務器Bigtable中Chubby的主要作用掃描服務器目錄，發(fā)現(xiàn)目前活躍的子表服務器與所有的活躍子表服務器取得聯(lián)系以便了解所有子表的分配情況通過掃描元數(shù)據(jù)表（MetadataTable），發(fā)現(xiàn)未分配的子表并將其分配到合適的子表步驟

1步驟

3步驟

2步驟

4如果元數(shù)據(jù)表未分配，則首先需要將根子表（Root

Tablet）加入服未務分器配的子表中。由于根子表保存了其他所有元數(shù)據(jù)子表的信息，確保了掃描能夠發(fā)現(xiàn)所有未分配的子表of56《云計算》第三版配套PPT課件2.4分布式結(jié)構化數(shù)據(jù)表Bigtable設計動機與目標數(shù)據(jù)模型系統(tǒng)架構主服務器子表服務器性能優(yōu)化ooff

5566《云計算》第三版配套PPT課件SSTable及子表基本結(jié)構SSTable結(jié)構子表實際組成SSTable中數(shù)據(jù)被劃分成一個個的塊（Block），每個塊的大小是可以設置的，一般為64KB在SSTable的結(jié)尾有一個索引（Index），這個索引保存了塊的位置信息，在SSTable打開時這個索引會被加載進內(nèi)存，用戶S在ST查a找bl某e個是塊G時oo首g先le在為內(nèi)存中查找塊的位置信息，然后在Bi硬g盤ta上b直le接設找計到這的個內(nèi)塊部數(shù)據(jù)存儲格式。所有的SS由T于ab每l個e文SST件ab都le一存般儲都在不是很GF大S，上用戶還可以選擇將其整體加載進內(nèi)存，這樣查找起來會更快·Bigtable中的日志文件是一種共享日志，每個子表服務器上僅保存一個日志文件，某個子表日志只是這個共享日志的一個片段。這樣會節(jié)省大量的空間，但在恢復時卻有一定的難度續(xù)讀取日志文件了·Google為了避免這種情況出現(xiàn)，對日志做了一些改進。Bigtable規(guī)定將日志的內(nèi)容按照鍵值進行每排個序子，這表樣都不是同的由子多表個服務SS器T都ab可l以e連以及日志（Log）文件構成一般不來同說子每個表子的表S的S大Ta小b在le10可0M以B到共200享MB之間。每個子表服務器上保存的子表數(shù)量可以從幾十到上千不等，通常情況下是100個左右《云計算》第三版配套PPT課件64KB塊64KB塊…SSTable索引2.4分布式結(jié)構化數(shù)據(jù)表Bigtable60

of56SSTable格式的基本示意SSTable是Google為Bigtable設計的內(nèi)部數(shù)據(jù)存儲格式。所有的SSTable文件都存儲在GFS上，用戶可以通過鍵來查詢相應的值?！对朴嬎恪返谌媾涮譖PT課件64KB塊塊…

64KBSSTable索引塊61

of5664KB

…

64KB塊SSTable索引…2.4分布式結(jié)構化數(shù)據(jù)表Bigtable子表實際組成不同子表的SSTable可以共享每個子表服務器上僅保存一個日志文件Bigtable規(guī)定將日志的內(nèi)容按照鍵值進行排序每個子表服務器上保存的子表數(shù)量可以從幾十到上千不等，通常情況下是100個左右日志《云計算》第三版配套PPT課件Chubby文件根子表（元數(shù)據(jù)表中第一條記錄）

…

…

…

…

…

…

用戶表1用戶表N其他元數(shù)據(jù)子表······2.4分布式結(jié)構化數(shù)據(jù)表Bigtable……···子表地址組成子表地址的查詢是經(jīng)常碰到的操作。在Bigtable系統(tǒng)的內(nèi)部采用的是一種類似B+樹的三層查詢體系62

of56ooff

5566《云計算》第三版配套PPT課件所有子表地址都被記錄在元數(shù)據(jù)表中，元數(shù)據(jù)表也是由一個個的元數(shù)據(jù)子表（Metadata

tablet）組成根子表是元數(shù)據(jù)表中一個比較特殊的子表，它既是元數(shù)據(jù)表的第一條記

錄，也包含了其他元數(shù)據(jù)子表的地址，同時Chubby中的一個文件也存儲了這個根子表的信息。查詢時，首先從Chubby中提取這個根子表的地址，進而讀取所需的元數(shù)據(jù)子表的位置，最后就可以從元數(shù)據(jù)子表中找到待查詢的子表。除了這

些子表的元數(shù)據(jù)之外，元數(shù)據(jù)表中還保存了其他一些有利于調(diào)試和分析

的信息，比如事件日志等ooff

5566《云計算》第三版配套PPT課件為了減少訪問開銷，提高客戶訪問效率，Bigtable使用了緩存（Cache）和預?。≒refetch）技術子表的地址信息被緩存在客戶端，客戶在尋址時直接根據(jù)緩存信息進行查找。一旦出現(xiàn)緩存為空或緩存信息過時的情況，客戶端就需要按照圖示方式進行網(wǎng)絡的來回通信（Network

Round-trips）進行尋址，在緩存為空的情況下需要三個