云計算第三Google云計算原理與應用二

1、第 2 章Google云計算原理與應用（二）2.1 Google文件系統(tǒng)GFS2.2 分布式數(shù)據(jù)處理MapReduce2.3 分布式鎖服務Chubby2.4 分布式結構化數(shù)據(jù)表Bigtable2.5 分布式存儲系統(tǒng)Megastore2.6 大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構Dapper2.7 海量數(shù)據(jù)的交互式分析工具Dremel2.8 內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9 Google應用程序引擎初步了解ChubbyChubby是Google設計的提供粗粒度鎖服務的一個文件系統(tǒng)，它基于松耦合分布式系統(tǒng)，解決了分布的一致性問題。通過使用Chubby的鎖服務，用戶可以確保數(shù)據(jù)操作過程中的一致性

2、Chubby作為一個穩(wěn)定的存儲系統(tǒng)存儲包括元數(shù)據(jù)在內(nèi)的小數(shù)據(jù)Google內(nèi)部還使用Chubby進行名字服務（Name Server）32.3 分布式鎖服務ChubbyPaxosPaxos算法算法 Paxos算法算法 Leslie Lamport最先提出的一種基于消息傳遞（最先提出的一種基于消息傳遞（Messages Passing）的一致性算法，用于解決）的一致性算法，用于解決分布式系統(tǒng)中的一致性分布式系統(tǒng)中的一致性問題問題 分布式系統(tǒng)一致性問題分布式系統(tǒng)一致性問題就是如何保證系統(tǒng)就是如何保證系統(tǒng)中初始狀態(tài)相同的各個節(jié)點在執(zhí)行相同的操作中初始狀態(tài)相同的各個節(jié)點在執(zhí)行相同的操作序列時，看到的指令

3、序列是完全一致的，并且序列時，看到的指令序列是完全一致的，并且最終得到完全一致的結果最終得到完全一致的結果 一個最簡單的方案在分布式系統(tǒng)中設置一個專門節(jié)點，在每次需要進行操作之前，系統(tǒng)的各個部分向它發(fā)出請求，告訴該節(jié)點接下來系統(tǒng)要做什么。該節(jié)點接受第一個到達的請求內(nèi)容作為接下來的操作，這樣就能夠保證系統(tǒng)只有一個唯一的操作序列 方案存在什么缺陷？PaxosPaxos算法算法缺陷缺陷專門節(jié)點失效，整專門節(jié)點失效，整個系統(tǒng)就很可能出現(xiàn)不一致。個系統(tǒng)就很可能出現(xiàn)不一致。為了避免這種情況，在系統(tǒng)為了避免這種情況，在系統(tǒng)中必然要設置多個專門節(jié)點，中必然要設置多個專門節(jié)點，由這些節(jié)點來共同決定操作由這些節(jié)點

4、來共同決定操作序列序列 Paxos算法算法 proposers提出決議（Value，系統(tǒng)接下來執(zhí)行的指令）acceptors批準決議 learners獲取并使用已經(jīng)通過的決議 2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統(tǒng)設計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能Paxos算法proposersacceptorslearners提出決議批準決議獲取并使用已經(jīng)通過的決議三類節(jié)點決議只有在被proposers提出后才能批準每次只批準一個決議只有決議確定被批準后learners才能獲取

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

6、acceptors 才批準編號為n的提案。82.3 分布式鎖服務Chubby9一個決議分為兩個階段準備階段12批準階段proposers選擇一個提案并將它的編號設為n將它發(fā)送給acceptors中的一個“多數(shù)派”acceptors 收到后，如果提案的編號大于它已經(jīng)回復的所有消息，則acceptors將自己上次的批準回復給proposers，并不再批準小于n的提案。當proposers接收到acceptors 中的這個“多數(shù)派”的回復后，就向回復請求的acceptors發(fā)送accept請求，在符合acceptors一方的約束條件下，acceptors收到accept請求后即批準這個請求。2.3

7、分布式鎖服務Chubby2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統(tǒng)設計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能54611Chubby的設計目標主要有以下幾點高可用性和高可靠性213高擴展性支持粗粒度的建議性鎖服務服務信息的直接存儲支持通報機制支持緩存機制2.3 分布式鎖服務Chubby系統(tǒng)設計目標系統(tǒng)設計目標Chubby系統(tǒng)設計系統(tǒng)設計高可用性和高可靠性；首要目標，在保證這一目標的基礎上再考慮系統(tǒng)的吞吐量和存儲能力 高擴展性；將數(shù)據(jù)存儲在價格較為低廉的RAM，支持大規(guī)模用戶訪問

8、文件 支持粗粒度的建議性鎖服務；提供這種服務的根本目的是提高系統(tǒng)的性能 服務信息的直接存儲；可直接存儲包括元數(shù)據(jù)、系統(tǒng)參數(shù)在內(nèi)的有關服務信息支持通報機制；客戶可以及時地了解到事件發(fā)生 支持緩存機制；通過一致性緩存將常用信息保存在客戶端，避免了頻繁地訪問主服務器 ChubbyChubby系統(tǒng)設計系統(tǒng)設計Chubby中還添加了一些新的功能特性；這種設計主要是考慮到以下幾個問題 030302020101n開發(fā)者初期很少考慮系統(tǒng)的一致性，但隨著開發(fā)進行，問題會變得越來越嚴重。單獨的鎖服務可以保證原有系統(tǒng)架構不會發(fā)生改變，而使用函數(shù)庫很可能需要對系統(tǒng)架構做出大幅度的改動 n系統(tǒng)中很多事件發(fā)生是需要告知其

9、他用戶和服務器，使用一個基于文件系統(tǒng)的鎖服務可以將這些變動寫入文件中。有需要的用戶和服務器直接訪問這些文件即可，避免因大量系統(tǒng)組件之間事件通信帶來系統(tǒng)性能下降 n基于鎖的開發(fā)接口容易被開發(fā)者接受。雖然在分布式系統(tǒng)中鎖的使用會有很大的不同，但是和一致性算法相比，鎖顯然被更多的開發(fā)者所熟知 ChubbyChubby系統(tǒng)設計系統(tǒng)設計Paxos算法實現(xiàn)過程中需要一個“多數(shù)派多數(shù)派”就某個值達成一致，本質上就是分布式系統(tǒng)中常見的quorum機制機制；為保證系統(tǒng)高可用性，需要若干臺機器，但使用單獨鎖服務的話一臺機器也能保證這種高可用性Chubby設計過程中一些細節(jié)問題值得關注：在Chubby系統(tǒng)中采用了建

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

11、15Chubby的基本架構在客戶這一端每個客戶應用程序都有一個Chubby程序庫（Chubby Library），客戶端的所有應用都是通過調用這個庫中的相關函數(shù)來完成的。服務器一端稱為Chubby單元，一般是由五個稱為副本（Replica）的服務器組成的，這五個副本在配置上完全一致，并且在系統(tǒng)剛開始時處于對等地位?？蛻舳朔掌鞫?.3 分布式鎖服務Chubby2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統(tǒng)設計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能ChubbyChubby中的中的P

12、axosPaxos單個單個Chubby副本結構副本結構 容錯日志容錯日志對數(shù)據(jù)庫正確性提供重要支持；一致性由Paxos算法保證；副本之間通過特定的Paxos協(xié)議通信，同時本地文件中保存與Chubby中相同的日志數(shù)據(jù) 容錯數(shù)據(jù)庫容錯數(shù)據(jù)庫快照（Snapshot）和記錄數(shù)據(jù)庫操作重播日志（Replay-log）；每一次的數(shù)據(jù)庫操作最終都將提交至日志中；本地文件中也保存著一份數(shù)據(jù)庫數(shù)據(jù)副本 Chubby構建在這個容錯的數(shù)據(jù)庫之上，Chubby利用這個數(shù)據(jù)庫存儲所有的數(shù)據(jù)。Chubby的客戶端通過特定的Chubby協(xié)議和單個的Chubby副本進行通信 ChubbyChubby中的中的PaxosPaxo

13、s容錯日志的容錯日志的API Content Title Content TitleChubby中中Paxos算法過程算法過程 2 2、協(xié)調者從客戶提交的值中選擇一個，、協(xié)調者從客戶提交的值中選擇一個，acceptaccept消息廣播給所有的副本，其他的消息廣播給所有的副本，其他的副本收到廣播后，選擇接受或者拒絕這副本收到廣播后，選擇接受或者拒絕這個值，并將決定結果反饋個值，并將決定結果反饋3、協(xié)調者收到大多數(shù)副本接受信息后，、協(xié)調者收到大多數(shù)副本接受信息后，認為達到了一致性，接著向相關副本發(fā)認為達到了一致性，接著向相關副本發(fā)送一個送一個commit消息消息 1、選擇一副本為協(xié)調者（、選擇一副

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

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

16、by對于Paxos論文中未提及的一些技術細節(jié)進行了補充，所以Chubby的實現(xiàn)是基于Paxos，但其技術手段更加的豐富，更具有實踐性 2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統(tǒng)設計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能ChubbyChubby文件系統(tǒng)文件系統(tǒng)Chubby系統(tǒng)本質上就是一個分布式的、存儲大量小文件的分布式的、存儲大量小文件的文件系統(tǒng)文件系統(tǒng)，它所有的操作都是在文件的基礎上完成Chubby最常用的鎖服務中，每一個文件就代表一個鎖，用戶通過打開、關閉和讀取文件，獲取

17、共享（Shared）鎖或獨占（Exclusive）鎖選舉主服務器過程中，符合條件的服務器都同時申請打開某個文件并請求鎖住該文件成功獲得鎖的服務器自動成為主服務器并將其地址寫入這個文件夾，以便其他服務器和用戶可以獲知主服務器的地址信息ChubbyChubby文件系統(tǒng)文件系統(tǒng)Chubby的文件系統(tǒng)和UNIX類似 例如在文件名“/ls/foo/wombat/pouch”中，ls代表lock service，這是所有Chubby文件系統(tǒng)的共有前綴；foo是某個單元的名稱；/wombat/pouch則是foo這個單元上的文件目錄或者文件名 Google對Chubby做了一些與UNIX不同的改變 例如Ch

18、ubby不支持內(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ù) 24單調遞增的64位編號實例號Instance Number新節(jié)點實例號必定大于舊節(jié)點的實例號。1鎖生成號Lock Generation Number鎖被用戶持有時該號增加。內(nèi)容生成號Conte

19、nt Generation Number文件內(nèi)容修改時該號增加。23ACL生成號ACL Generation NumberACL名被覆寫時該號增加。42.3 分布式鎖服務ChubbyChubbyChubby文件系統(tǒng)文件系統(tǒng)序號：確定句柄由當前還是以前的主服務器創(chuàng)建序號：確定句柄由當前還是以前的主服務器創(chuàng)建2模式信息：用于新的主服務器重新創(chuàng)建一個舊句柄模式信息：用于新的主服務器重新創(chuàng)建一個舊句柄 3用戶打開某個節(jié)點的同時會獲取一個類似于UNIX中文件描述符（File Descriptor）的句柄，這個句柄由以下三個部分組成 校驗數(shù)位：防止其他用戶創(chuàng)建或猜測這個句柄校驗數(shù)位：防止其他用戶創(chuàng)建或猜測

20、這個句柄 1ChubbyChubby文件系統(tǒng)文件系統(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ù)Get

21、Stat()只返回文件元數(shù)據(jù)ReadDir()返回子目錄名稱及其元數(shù)據(jù)SetContents()向文件中寫入內(nèi)容SetACL()設置ACL名稱Delete()如果該節(jié)點沒有子節(jié)點的話則執(zhí)行刪除操作Acquire()獲取鎖Release()釋放鎖GetSequencer()返回一個sequencerSetSequencer()將sequencer和某個句柄進行關聯(lián)CheckSequencer()檢查某個sequencer是否有效常用句柄函數(shù)及其作用常用句柄函數(shù)及其作用 2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統(tǒng)設計2.3.3 Chubby中的Paxos

22、2.3.4 Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能ChubbyChubby系統(tǒng)設計系統(tǒng)設計 客戶端應 用程序 Chubby 程序庫 客戶端應 用程序 Chubby 程序庫 客戶端進程 主服務器 Chubby 單元的 五個服務器 遠程過程調用 Chubby基本架構：客戶端基本架構：客戶端和服務器端，兩者通過遠程和服務器端，兩者通過遠程過程調用（過程調用（RPC）來連接）來連接客戶端每個客戶應用程序都客戶端每個客戶應用程序都有一個有一個Chubby程序庫程序庫（Chubby Library），所），所有應用都是通過調用這個庫有應用都是通過調用這個庫中相關函數(shù)來完成中相關函

23、數(shù)來完成服務器一端服務器一端Chubby單元，單元，一般由五個稱為副本一般由五個稱為副本（Replica）服務器組成，）服務器組成，它們配置上完全一致，且系它們配置上完全一致，且系統(tǒng)剛開始時處于對等地位統(tǒng)剛開始時處于對等地位 ChubbyChubby客戶端與服務器端的通信過程客戶端與服務器端的通信過程 1 2 3 4 5 6 7 8 舊的主 服務器 新的主 服務器 寬限期 舊的主服 務器故障 選出新的 主服務器 客戶端 租約期 M2 租約期 C1 無主服務器 危險狀態(tài)臨界點 安全狀態(tài)臨界點 KeepAlives 租約期 M1 租約期 C2 租約期 C3 租約期 M3 從左到右的水平方向表示時間

24、在增加，斜向上的箭頭表示一次KeepAlive請求，斜向下的箭頭則是主服務器的一次回應 M1、M2、M3表示不同的主服務器租約期主服務器租約期；C1、C2、C3則是客戶端對主服務器租約期時長租約期時長做出的一個估計 KeepAlive是周期發(fā)送的一種信息，它主要有兩方面的功能：延遲租約的延遲租約的有效期有效期和攜帶事件信息告訴用戶更新攜帶事件信息告訴用戶更新 30可能出現(xiàn)的兩種故障2.3 分布式鎖服務Chubby客戶端租約過期主服務器出錯12客戶端租約過期故障處理客戶端租約過期故障處理 客戶端租約過期客戶端租約過期 客戶端向主服務器發(fā)出一個客戶端向主服務器發(fā)出一個KeepAlive請求（上圖請

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

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

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

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

29、定時間段后（1 1分鐘），刪除沒有被打開過的臨時文件夾分鐘），刪除沒有被打開過的臨時文件夾如果這一過程在寬限期內(nèi)順利完成，則用戶不會感覺到任何故障的發(fā)生，也就是說新舊主服務器的替換對于用戶來說是透明的，用戶感覺到的僅僅是一個延遲 2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統(tǒng)設計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能34一致性2.3 分布式鎖服務Chubby正確性與性能每個Chubby單元是由五個副本組成的，這五個副本中需要選舉產(chǎn)生一個主服務器，這種選舉本質上就是一個一致性問題安

30、全性采用的是ACL形式的安全保障措施。只要不被覆寫，子節(jié)點都是直接繼承父節(jié)點的ACL名性能優(yōu)化提高主服務器默認的租約期、使用協(xié)議轉換服務將Chubby協(xié)議轉換成較簡單的協(xié)議、客戶端一致性緩存等一致性一致性 每個Chubby單元是由五個副本組成的，這五個副本中需要選舉產(chǎn)生一個主服務器，這種選舉本質上就是一個一致性問題。實際執(zhí)行過程中，Chubby使用Paxos算法來解決 主服務器產(chǎn)生后客戶端的所有讀寫操作都是由主服務器來完成的 讀操作很簡單，客戶直接從主服務器上讀取所需數(shù)據(jù)即可 寫操作就會涉及數(shù)據(jù)一致性的問題；為了保證客戶的寫操作能夠同步到所有的服務器上，系統(tǒng)再次利用了Paxos算法安全性安全性

31、 Chubby用ACL形式安全保障措施。系統(tǒng)有三種ACL名：寫ACL名（Write ACL Name）、讀ACL名（Read ACL Name）和變更ACL名（Change ACL Name）只要不被覆寫，子節(jié)點都是直接繼承父節(jié)點的ACL名 ACL同樣被保存在文件中，它是節(jié)點元數(shù)據(jù)的一部分，用戶在進行相關操作時首先需要通過ACL來獲取相應的授權 chinacloud CLOUD fun chinacloud 請求寫文件 讀取寫 ACL名 查詢 成功查到 允許寫入 成功寫入 Chubby的ACL機制 用戶用戶chinacloud提出向文件提出向文件CLOUD中寫入內(nèi)中寫入內(nèi)容請求。容請求。CLO

32、UD首先讀取自身的寫首先讀取自身的寫ACL名名fun，接著在接著在fun中查到了中查到了chinacloud這一行記錄，這一行記錄，于是返回信息允許于是返回信息允許chinacloud對文件進行寫操對文件進行寫操作，此時作，此時chinacloud才被允許向才被允許向CLOUD寫入寫入內(nèi)容。其他的操作和寫操作類似內(nèi)容。其他的操作和寫操作類似性能優(yōu)化性能優(yōu)化 為滿足系統(tǒng)高可擴展性，Chubby目前已經(jīng)采取了一些措施：比如提高主服務器默認的租約期、使用協(xié)議轉換服務將Chubby協(xié)議轉換成較簡單的協(xié)議、客戶端一致性緩存等；除此之外，Google的工程師們還考慮使用代理（Proxy）和分區(qū)（Parti

33、tion）技術 代理可以減少主服務器處理KeepAlive以及讀請求帶來的服務器負載，但是它并不能減少寫操作帶來的通信量 使用分區(qū)技術的話可以將一個單元的命名空間（Name Space）劃分成N份。除了少量的跨分區(qū)通信外，大部分的分區(qū)都可以獨自地處理服務請求。通過分區(qū)可以減少各個分區(qū)上的讀寫通信量，但不能減少KeepAlive請求的通信量 2.1 Google文件系統(tǒng)GFS2.2 分布式數(shù)據(jù)處理MapReduce2.3 分布式鎖服務Chubby2.4 分布式結構化數(shù)據(jù)表Bigtable2.5 分布式存儲系統(tǒng)Megastore2.6 大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構Dapper2.7 海量數(shù)據(jù)的交

34、互式分析工具Dremel2.8 內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9 Google應用程序引擎382.4 分布式結構化數(shù)據(jù)表Bigtable2.4.1 設計動機與目標2.4.2 數(shù)據(jù)模型2.4.3 系統(tǒng)架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優(yōu)化402.4 分布式結構化數(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)根本無法承受的一方面

35、現(xiàn)有商用數(shù)據(jù)庫的設計著眼點在于其通用性。另一方面對于底層系統(tǒng)的完全掌控會給后期的系統(tǒng)維護、升級帶來極大的便利412.4 分布式結構化數(shù)據(jù)表BigtableBigtable 應達到的基本目標廣泛的適用性很強的可擴展性高可用性簡單性Bigtable是為了滿足一系列Google產(chǎn)品而并非特定產(chǎn)品的存儲要求。根據(jù)需要隨時可以加入或撤銷服務器確保幾乎所有的情況下系統(tǒng)都可用底層系統(tǒng)的簡單性既可以減少系統(tǒng)出錯的概率，也為上層應用的開發(fā)帶來便利2.4 分布式結構化數(shù)據(jù)表Bigtable2.4.1 設計動機與目標2.4.2 數(shù)據(jù)模型2.4.3 系統(tǒng)架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優(yōu)

36、化43Bigtable數(shù)據(jù)的存儲格式2.4 分布式結構化數(shù)據(jù)表BigtableBigtable是一個分布式多維映射表，表中的數(shù)據(jù)通過一個行關鍵字（Row Key）、一個列關鍵字（Column Key）以及一個時間戳（Time Stamp）進行索引Bigtable的存儲邏輯可以表示為：(row:string, column:string, time:int64)stringBigtable對存儲在其中的數(shù)據(jù)不做任何解析，一律看做字符串44Bigtable數(shù)據(jù)的存儲格式2.4 分布式結構化數(shù)據(jù)表Bigtable假設想要拷貝一個可能被很多項目都使用的、很大的網(wǎng)頁集合以及相關的信息，把這個特定的表稱為

37、Webtable。在Webtable當中，使用URL作為行鍵，網(wǎng)頁的不同方面作為列鍵，并把網(wǎng)頁的內(nèi)容存儲在contents:column中，如圖所示圖存儲了網(wǎng)頁數(shù)據(jù)的Webtable的一個片段。行名稱是反轉的URL，contents列家族包含了網(wǎng)頁內(nèi)容，anchor列家族包含了任何引用這個頁面的anchor文本。CNN的主頁被Sports Illustrated和MY-look主頁同時引用，因此，行包含了名稱為”anchor:”和”anchor:my.look.ca”的列。每個anchor單元格都只有一個版本，contents列有三個版本，分別對應于時間戳t3,t5和t6。數(shù)據(jù)模型數(shù)據(jù)模型行

38、Bigtable的行關鍵字可以是任意的字符串，但是大小不能超過64KB。Bigtable和傳統(tǒng)的關系型數(shù)據(jù)庫有很大不同，它不支持一般意義上的事務，但能保證對于行的讀寫操作具有原子性（Atomic） 表中數(shù)據(jù)都是根據(jù)行關鍵字進行排序的，排序使用的是詞典序。 一個典型實例，其中n.www就是一個行關鍵字。不直接存儲網(wǎng)頁地址而將其倒排是Bigtable的一個巧妙設計。這樣做至少會帶來以下兩個好處 同一地址域的網(wǎng)頁會被存儲在表中的連續(xù)位置，有利于用戶查找和分析 倒排便于數(shù)據(jù)壓縮，可以大幅提高壓縮率 數(shù)據(jù)模型數(shù)據(jù)模型列 Bigtable并不是簡單地存儲所有的列關鍵字，而是將其組織成所謂的列族（Colum

39、n Family），每個族中的數(shù)據(jù)都屬于同一個類型，并且同族的數(shù)據(jù)會被壓縮在一起保存。引入了列族的概念之后，列關鍵字就采用下述的語法規(guī)則來定義： 族名：限定詞（family：qualifier） 族名必須有意義，限定詞則可以任意選定 圖中，內(nèi)容（Contents）、錨點（Anchor）都是不同的族。而和my.look.ca則是錨點族中不同的限定詞 族同時也是Bigtable中訪問控制（Access Control）基本單元，也就是說訪問權限的設置是在族這一級別上進行的 “內(nèi)容： ” “錨點：” “錨點：my.look.ca” “n.www” “” “” “” “CNN.com” “CNN” t

40、3 t5 t6 t8 t9 數(shù)據(jù)模型數(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ù)。失效的版本

41、將會由Bigtable的垃圾回收機制自動處理 “內(nèi)容： ” “錨點：” “錨點：my.look.ca” “n.www” “” “” “” “CNN.com” “CNN” t3 t5 t6 t8 t9 2.4 分布式結構化數(shù)據(jù)表Bigtable2.4.1 設計動機與目標2.4.2 數(shù)據(jù)模型2.4.3 系統(tǒng)架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優(yōu)化49Bigtable 基本架構2.4 分布式結構化數(shù)據(jù)表Bigtable502.4 分布式結構化數(shù)據(jù)表BigtableBigtable 中 Chubby 的主要作用作用一選取并保證同一時間內(nèi)只有一個主服務器（Master Serv

42、er）。獲取子表的位置信息。保存Bigtable的模式信息及訪問控制列表。作用二作用三系統(tǒng)架構 BigtableBigtable主要由三個部分組成：客戶端程序庫（主要由三個部分組成：客戶端程序庫（Client LibraryClient Library）、一個主）、一個主服務器（服務器（Master ServerMaster Server）和多個子表服務器（）和多個子表服務器（Tablet ServerTablet Server） 客戶訪問客戶訪問BigtableBigtable服務時，首先要利用其庫函數(shù)執(zhí)行服務時，首先要利用其庫函數(shù)執(zhí)行Open()Open()操作來打開一個操作來打開一個鎖（

43、鎖（實際上就是獲取了文件目錄實際上就是獲取了文件目錄），鎖打開以后客戶端就可以和子表服務器），鎖打開以后客戶端就可以和子表服務器進行通信進行通信 和許多具有單個主節(jié)點分布式系統(tǒng)一樣，客戶端主要與子表服務器通信，和許多具有單個主節(jié)點分布式系統(tǒng)一樣，客戶端主要與子表服務器通信，幾乎不和主服務器進行通信，這使得主服務器的負載大大降低幾乎不和主服務器進行通信，這使得主服務器的負載大大降低 主服務主要進行一些元數(shù)據(jù)操作以主服務主要進行一些元數(shù)據(jù)操作以及子表服務器之間負載調度問題，及子表服務器之間負載調度問題，實際數(shù)據(jù)是存儲在子表服務器上實際數(shù)據(jù)是存儲在子表服務器上 2.4 分布式結構化數(shù)據(jù)表Bigtab

44、le2.4.1 設計動機與目標2.4.2 數(shù)據(jù)模型2.4.3 系統(tǒng)架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優(yōu)化532.4 分布式結構化數(shù)據(jù)表Bigtable主服務器新子表分配子表服務器狀態(tài)監(jiān)控子服務器之間的負載均衡當一個新的子表產(chǎn)生時，主服務器通過一個加載命令將其分配給一個空間足夠的子表服務器。創(chuàng)建新表、表合并以及較大子表的分裂都會產(chǎn)生一個或多個新子表。分割完成之后子服務器需要向主服務發(fā)出一個通知。主服務器必須對子表服務器的狀態(tài)進行監(jiān)控，以便及時檢測到服務器的加入或撤銷主服務器主服務器Bigtable中主服務表服務器的監(jiān)控是通過Chubby完成的子表服務器在初始化時都會從

45、Chubby中得到一器對子個獨占鎖。通過這種方式所有子表服務器基本信息被保存在Chubby中一個稱為服務器目錄（Server Directory）的特殊目錄之中。主服務器通過這個目錄可以隨時獲取最新的子表服務器信息，包括： 目前活躍的子表服務器； 每個子表服務器上現(xiàn)已分配的子表。主服務器主服務器 對于每個具體的子表服務器，主服務器會定期向其詢問獨占鎖的狀態(tài)對于每個具體的子表服務器，主服務器會定期向其詢問獨占鎖的狀態(tài)。如果子表服務器的鎖丟失或沒有回應，則此時可能有兩種情況：。如果子表服務器的鎖丟失或沒有回應，則此時可能有兩種情況： 要么是要么是ChubbyChubby出現(xiàn)了問題出現(xiàn)了問題（雖然這

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

47、器會自動對其進行負載均衡操作對其進行負載均衡操作 主服務器主服務器 基于系統(tǒng)出現(xiàn)故障是一種常態(tài)的設計理念，每個主服務器被設基于系統(tǒng)出現(xiàn)故障是一種常態(tài)的設計理念，每個主服務器被設定了一個會話時間的限制。當某個主服務器到時退出后，管理系定了一個會話時間的限制。當某個主服務器到時退出后，管理系統(tǒng)就會指定一個新的主服務器，這個主服務器的啟動需要經(jīng)歷以統(tǒng)就會指定一個新的主服務器，這個主服務器的啟動需要經(jīng)歷以下四個步驟下四個步驟： 572.4 分布式結構化數(shù)據(jù)表Bigtable從Chubby中獲取一個獨占鎖，確保同一時間只有一個主服務器Bigtable 中 Chubby 的主要作用掃描服務器目錄，發(fā)現(xiàn)目前

48、活躍的子表服務器與所有的活躍子表服務器取得聯(lián)系以便了解所有子表的分配情況通過掃描元數(shù)據(jù)表（Metadata Table），發(fā)現(xiàn)未分配的子表并將其分配到合適的子表服務器步驟 1 步驟 3 步驟 2 步驟 4如果元數(shù)據(jù)表未分配，則首先需要將根子表（Root Tablet）加入未分配的子表中。由于根子表保存了其他所有元數(shù)據(jù)子表的信息，確保了掃描能夠發(fā)現(xiàn)所有未分配的子表 2.4 分布式結構化數(shù)據(jù)表Bigtable2.4.1 設計動機與目標2.4.2 數(shù)據(jù)模型2.4.3 系統(tǒng)架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優(yōu)化SSTableSSTable及子表基本結構及子表基本結構 64K

49、B 塊 塊 . 索引 SSTable 塊 塊 SSTable 日志 . . 索引 64KB 64KB 64KB SSTable是Google為Bigtable設計的內(nèi)部數(shù)據(jù)存儲格式。所有的SSTable文件都存儲在GFS上 SSTable結構 子表實際組成 每個子表都是由每個子表都是由多個多個SSTableSSTable以以及日志（及日志（LogLog）文件）文件構成構成不同子表的不同子表的SSTableSSTable可以可以共享共享SSTable中數(shù)據(jù)被劃分成一個個的塊（Block），每個塊的大小是可以設置的，一般為64KB在SSTable的結尾有一個索引（Index），這個索引保存了塊的位

50、置信息，在SSTable打開時這個索引會被加載進內(nèi)存，用戶在查找某個塊時首先在內(nèi)存中查找塊的位置信息，然后在硬盤上直接找到這個塊由于每個SSTable一般都不是很大，用戶還可以選擇將其整體加載進內(nèi)存，這樣查找起來會更快 Bigtable中的日志文件是一種共享日志，每個子表服務器上僅保存一個日志文件，某個子表日志只是這個共享日志的一個片段。這樣會節(jié)省大量的空間，但在恢復時卻有一定的難度Google為了避免這種情況出現(xiàn)，對日志做了一些改進。Bigtable規(guī)定將日志的內(nèi)容按照鍵值進行排序，這樣不同的子表服務器都可以連續(xù)讀取日志文件了一般來說每個子表的大小在100MB到200MB之間。每個子表服務器

51、上保存的子表數(shù)量可以從幾十到上千不等，通常情況下是100個左右 6064KB塊64KB塊SSTable索引SSTable 格式的基本示意2.4 分布式結構化數(shù)據(jù)表BigtableSSTable是Google為Bigtable設計的內(nèi)部數(shù)據(jù)存儲格式。所有的SSTable文件都存儲在GFS上，用戶可以通過鍵來查詢相應的值。61子表實際組成日志64KB塊64KB塊SSTable索引64KB塊64KB塊SSTable索引2.4 分布式結構化數(shù)據(jù)表Bigtable不同子表的SSTable可以共享每個子表服務器上僅保存一個日志文件Bigtable規(guī)定將日志的內(nèi)容按照鍵值進行排序每個子表服務器上保存的子表數(shù)

52、量可以從幾十到上千不等，通常情況下是100個左右62Chubby文件根子表（元數(shù)據(jù)表中第一條記錄）用戶表1用戶表N其他元數(shù)據(jù)子表子表地址組成2.4 分布式結構化數(shù)據(jù)表Bigtable子表地址的查詢查詢是經(jīng)常碰到的操作。在Bigtable系統(tǒng)的內(nèi)部采用的是一種類似類似B+B+樹的三層查詢體系樹的三層查詢體系 所有子表地址都被記錄在所有子表地址都被記錄在元數(shù)據(jù)表元數(shù)據(jù)表中，元數(shù)據(jù)表也是由一個個的中，元數(shù)據(jù)表也是由一個個的元數(shù)據(jù)元數(shù)據(jù)子表子表（Metadata tabletMetadata tablet）組成）組成根子表是元數(shù)據(jù)表中一個比較特殊的子表，它既是根子表是元數(shù)據(jù)表中一個比較特殊的子表，它既

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

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

55、圖示方式進行網(wǎng)絡的來回通信（進行網(wǎng)絡的來回通信（Network Round-tripsNetwork Round-trips）進行尋址，在）進行尋址，在緩存為空的情況下緩存為空的情況下需要三個網(wǎng)絡來回通信。如果需要三個網(wǎng)絡來回通信。如果緩存的信息是過時緩存的信息是過時的，則需要六個網(wǎng)絡來回通的，則需要六個網(wǎng)絡來回通信。其中三個用來確定信息是過時的，另外三個獲取新的地址信。其中三個用來確定信息是過時的，另外三個獲取新的地址 預取預取則是在每次訪問元數(shù)據(jù)表時不僅僅讀取所需的子表元數(shù)據(jù)，而是讀取則是在每次訪問元數(shù)據(jù)表時不僅僅讀取所需的子表元數(shù)據(jù)，而是讀取多個子表的元數(shù)據(jù)，這樣下次需要時就不用再次訪問

56、元數(shù)據(jù)表多個子表的元數(shù)據(jù)，這樣下次需要時就不用再次訪問元數(shù)據(jù)表 Chubby 文件 根子表 （元數(shù)據(jù)表中第一條記錄） 用戶表 1 用戶表 N 其他元數(shù)據(jù)子表 子表數(shù)據(jù)存儲及讀子表數(shù)據(jù)存儲及讀/ /寫操作寫操作 內(nèi) 存 表 寫 操 作 讀 操 作 子 表 日 志 內(nèi) 存 GFS SSTable文 件 Bigtable數(shù)據(jù)存儲及讀/寫操作 Bigtable將數(shù)據(jù)存儲劃分成兩塊：較新的數(shù)據(jù)存儲在內(nèi)存中一個稱為內(nèi)存表（Memtable）的有序緩沖里，較早的數(shù)據(jù)則以SSTable格式保存在GFS中 寫操作（Write Op）先查詢Chubby中保存的訪問控制列表確定用戶具相應寫權限，通過認證之后寫入的數(shù)

57、據(jù)首先被保存在提交日志（Commit Log）中。提交日志中以重做記錄（Redo Record）的形式保存著最近的一系列數(shù)據(jù)更改，這些重做記錄在子表進行恢復時可以向系統(tǒng)提供已完成的更改信息。 讀操作（Read Op）先通過認證，之后讀操作就要結合內(nèi)存表和SSTable文件來進行，因為內(nèi)存表和SSTable中都保存了數(shù)據(jù) SSTable SSTable 內(nèi)存表 SSTable 內(nèi)存表 內(nèi)存表 次壓縮 次壓縮 . . . . . . . . SSTable SSTable 合并壓縮 SSTable 主壓縮 . . . . 三種形式壓縮之間的關系 Bigtable中有三種形式的數(shù)據(jù)壓縮 ：次壓縮（M

58、inor Compaction）合并壓縮（Merging Compaction）主壓縮（Major Compaction） 數(shù)據(jù)壓縮問題每一次舊的內(nèi)存表停止使用時都會進行一個次壓縮操作，這會產(chǎn)生一個SSTable。但如果系統(tǒng)中只有這種壓縮的話，SSTable的數(shù)量就會無限制地增加下去 而在Bigtable中，讀操作實際上比寫操作更重要，因此Bigtable會定期地執(zhí)行一次合并壓縮的操作，將一些已有的SSTable和現(xiàn)有的內(nèi)存表一并進行一次壓縮 主壓縮其實是合并壓縮的一種，只不過它將所有的SSTable一次性壓縮成一個大的SSTable文件。主壓縮也是定期執(zhí)行，執(zhí)行一次主壓縮之后可以保證將所有的

59、被壓縮數(shù)據(jù)徹底刪除 2.4 分布式結構化數(shù)據(jù)表Bigtable2.4.1 設計動機與目標2.4.2 數(shù)據(jù)模型2.4.3 系統(tǒng)架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優(yōu)化68 內(nèi)容 語言 排名 SSTable SSTable n.www 局部性群組2.4 分布式結構化數(shù)據(jù)表BigtableBigtable允許用戶將原本并不存儲在一起的數(shù)據(jù)以列族為單位，根據(jù)需要組織在一個單獨的SSTable中，以構成一個局部性群組。用戶可以只看自己感興趣的內(nèi)容。對于一些較小的且會被經(jīng)常讀取的局部性群組，明顯地改善讀取效率。692.4 分布式結構化數(shù)據(jù)表Bigtable壓縮12利用Bentle

60、y & McIlroy方式（BMDiff）在大的掃描窗口將常見的長串進行壓縮采取Zippy技術進行快速壓縮，它在一個16KB大小的掃描窗口內(nèi)尋找重復數(shù)據(jù)，這個過程非?？靿嚎s可以有效地節(jié)省空間，Bigtable中的壓縮被應用于很多場合。首先壓縮可以被用在構成局部性群組的SSTable中，可以選擇是否對個人的局部性群組的SSTable進行壓縮。702.4 分布式結構化數(shù)據(jù)表Bigtable布隆過濾器Bigtable向用戶提供了一種稱為布隆過濾器的數(shù)學工具。布隆過濾器是巴頓布隆在1970年提出的，實際上它是一個很長的二進制向量和一系列隨機映射函數(shù)，在讀操作中確定子表的位置時非常有用。布隆過濾器的速度