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

電子工業(yè)出版社《云計算(第三版)》配套課件第2章Google云計算原理與應用（四）目錄

2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據處理MapReduce2.3分布式鎖服務Chubby2.4分布式結構化數(shù)據表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構Dapper2.7海量數(shù)據的交互式分析工具Dremel2.8內存大數(shù)據分析系統(tǒng)PowerDrill2.9Google應用程序引擎數(shù)據本身不會產生價值只有經過分析才有可能產生價值2.7海量數(shù)據的交互式分析工具Dremel2.7.1產生背景2.7.2數(shù)據模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結5產生背景2.7海量數(shù)據的交互式分析工具DremelMapReduce優(yōu)點：便攜缺點：效率低Google的團隊結合其自身的實際需求，借鑒搜索引擎和并行數(shù)據庫的一些技術，開發(fā)出了實時的交互式查詢系統(tǒng)Dremel。2.7海量數(shù)據的交互式分析工具DremelDremel支持的典型應用Web文檔的分析Android市場的應用安裝數(shù)據的跟蹤Google產品的錯誤報告Google圖書的光學字符識別欺詐信息的分析Google地圖的調試Bigtable實例上的tablet遷移Google分布式構建系統(tǒng)的測試結果分析磁盤I/O信息的統(tǒng)計Google數(shù)據中心上運行任務的資源監(jiān)控Google代碼庫的符號和依賴關系分析62.7海量數(shù)據的交互式分析工具Dremel2.7.1產生背景2.7.2數(shù)據模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結8兩方面的技術支撐兩方面的技術支撐一方面：統(tǒng)一的存儲平臺另一方面：統(tǒng)一的數(shù)據存儲格式實現(xiàn)高效的數(shù)據存儲，Dremel使用的底層數(shù)據存儲平臺是GFS存儲的數(shù)據才可以被不同的平臺所使用2.7海量數(shù)據的交互式分析工具Dremel9兩方面的技術支撐關系數(shù)據庫用關系模型進行建模，其數(shù)據存儲方式有兩種：

早期：行存儲（面向記錄的存儲）

晚期：列存儲，以屬性為單位，每次存儲一個屬性，應用時將需要的屬性重

新組裝成原始的記錄缺點：很多數(shù)據之間沒有嚴格關系，無法用關系模型進行很好地建模

嵌套數(shù)據模型（GOOGLE采用）Dremel第一次在嵌套數(shù)據模型基礎上實現(xiàn)列存儲優(yōu)點：處理時只需要使用涉及的列數(shù)據；

更利于數(shù)據的壓縮。2.7海量數(shù)據的交互式分析工具Dremel102.7海量數(shù)據的交互式分析工具Dremel面向記錄和面向列的存儲Google的Dremel是第一個在嵌套數(shù)據模型基礎上實現(xiàn)列存儲的系統(tǒng)。列存儲更利于數(shù)據的壓縮處理時只需要使用涉及的列數(shù)據好處一：好處二：112.7海量數(shù)據的交互式分析工具Dremel嵌套模型的形式化定義原子類型（AtomicType）原子類型允許的取值類型包括整型、浮點型、字符串等記錄類型（RecordType）記錄類型則可以包含多個域記錄型數(shù)據包括三種類型：必須的（Required）、可重復的（Repeated）以及可選的（Optional）122.7海量數(shù)據的交互式分析工具Dremel嵌套結構的模式和實例文檔的模式（Schema）定義符合該模式的兩條記錄利用該數(shù)據模型，可以使用Java語言，也可以使用C++語言來處理數(shù)據，甚至可以用Java編寫的MapReduce程序直接處理C++語言產生的數(shù)據集。這種跨平臺的優(yōu)良特性正是Google所需要的。2.7海量數(shù)據的交互式分析工具Dremel2.7.1產生背景2.7.2數(shù)據模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結14問題：對圖2-41中的r1的‘en-us’和‘en’，單純記錄下來無法判斷這兩個值對應的是r1中的那個位置，因為r1中Name.Language.Code屬性出現(xiàn)了3次

解決辦法：Dremel定義了兩個變量：r(重復深度)和d（定義深度）2.7海量數(shù)據的交互式分析工具Dremel15圖2-41中Name.Language.Code出現(xiàn)了三次en-us’，‘en’和‘en-gb’Name.Language.Code中可重復的字段有兩個：Name,Language,因此Code的可重復深度的取值可能為0，1，2,其中0表示一個新紀錄的開始。en-us的重復深度：0（Name和Language沒重復，表示一個新紀錄）en的重復深度：2（Language出現(xiàn)了第2次，Language在Name.Language.Code路徑中位置第二）

en-gb的重復深度：1（Name重復，Name在Name.Language.Code路徑中位置第1）

注意：第二個Name在r1中沒有包含任何Code值，為了確定出現(xiàn)在第三個Name中而不是第二個，系統(tǒng)會添加一個NULL值在’en’和‘en-gb’之間重復深度記錄的是該列的值是在哪一個級別上重復的2.7海量數(shù)據的交互式分析工具Dremel16定義深度：值的路徑中有多少個可以不被定義的字段（可選和重復）實際是有定義的路徑Name.Language.Country的定義深度的可能取值：0，1，2，3在r1中共有4個定義：‘us’,‘NULL’，‘NULL’和‘gb’定義深度分別為3，2，1，32.7海量數(shù)據的交互式分析工具Dremel172.7海量數(shù)據的交互式分析工具Dremel數(shù)據結構的無損表示帶有重復深度和定義深度的r1與r2的列存儲重復深度主要關注的是可重復類型，而定義深度同時關注可重復類型和可選類型（optional）每一列最終會被存儲為塊（Block）的集合，每個塊包含重復深度和定義深度且包含字段值。182.7海量數(shù)據的交互式分析工具Dremel高效的數(shù)據編碼計算重復和定義深度的基礎算法Dremel利用圖中算法創(chuàng)建一個樹狀結構樹的節(jié)點為字段的writer，它的結構與模式中的字段層級匹配。核心的想法是只在字段writer有自己的數(shù)據時執(zhí)行更新，非絕對必要時不嘗試往下傳遞父節(jié)點狀態(tài)。子節(jié)點writer繼承父節(jié)點的深度值。當任意值被添加時，子writer將深度值同步到父節(jié)點。192.7海量數(shù)據的交互式分析工具Dremel數(shù)據重組Dremel數(shù)據重組方法的核心思想是為每個字段創(chuàng)建一個有限狀態(tài)機（FSM），讀取字段值和重復深度，然后順序地將值添加到輸出結果上。202.7海量數(shù)據的交互式分析工具Dremel21當前FSM寫入值下一個重復深度值動作DocId（開始）100跳轉至Links.BackwardLinks.BackwardNULL0跳轉至Links.ForwardLinks.Forward201停留在Links.ForwardLinks.Forward401停留在Links.ForwardLinks.Forward600跳轉至Name.Language.CodeName.Language.Codeen-us2跳轉至Name.Language.CountryName.Language.Countryus2跳轉至Name.Language.CodeName.Language.Codeen1跳轉至Name.Language.CountryName.Language.CountryNULL1跳轉至Name.UrlName.Urlhttp://A1跳轉至Name.Language.CodeName.Language.CodeNULL1跳轉至Name.Language.CountryName.Language.CountryNULL1跳轉至Name.UrlName.Urlhttp://B1跳轉至Name.Language.CodeName.Language.Codeen-gb0跳轉至Name.Language.CountryName.Language.Countrygb0跳轉至Name.UrlName.UrlNULL0結束2.7海量數(shù)據的交互式分析工具Dremel數(shù)據重組r1的完整數(shù)據重組過程222.7海量數(shù)據的交互式分析工具Dremel數(shù)據重組如果具體的查詢中不是涉及所有列，而是僅涉及很少的列的話，上述數(shù)據重組的過程會更加便利，下圖中僅僅涉及DocId和Name.Language.Country的有限狀態(tài)機。232.7海量數(shù)據的交互式分析工具Dremel數(shù)據重組核心的思想如下：設置t為當前字段讀取器的當前值f所返回的下一個重復深度。在模式樹中，找到它在深度t的祖先，然后選擇該祖先節(jié)點的第一個葉子字段n。由此得到一個FSM狀態(tài)變化(f,t)->n。有限狀態(tài)機的構造算法2.7海量數(shù)據的交互式分析工具Dremel2.7.1產生背景2.7.2數(shù)據模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結252.7海量數(shù)據的交互式分析工具Dremel查詢語言與執(zhí)行Dremel的SQL查詢輸入的是一個或多個嵌套結構的表以及相應的模式，而輸出的結果是一個嵌套結構的表以及相應的模式。嵌套子查詢記錄內聚合top-kjoins自定義函數(shù)……262.7海量數(shù)據的交互式分析工具DremelDremel利用多層級服務樹（multi-levelservicetree）的概念來執(zhí)行查詢操作根服務器接受客戶端發(fā)出的請求，讀取相應的元數(shù)據，將請求轉發(fā)至中間服務器。中間服務器負責查詢中間結果的聚集葉子服務器負責執(zhí)行數(shù)據來源查詢語言與執(zhí)行27查詢語言與執(zhí)行Dremel中的數(shù)據都是分布式存儲的，因此每一層查詢涉及的數(shù)據實際都被水平劃分后存儲在多個服務器上。Dremel是一個多用戶系統(tǒng)，因此同一時刻往往會有多個用戶進行查詢。查詢分發(fā)器有一個很重要參數(shù)，它表示在返回結果之前一定要掃描百分之多少的tablet2.7海量數(shù)據的交互式分析工具Dremel2.7海量數(shù)據的交互式分析工具Dremel2.7.1產生背景2.7.2數(shù)據模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結29表名記錄數(shù)（億)規(guī)模（未壓縮，TB）域數(shù)目數(shù)據中心復制因子T185087270A3T224013530A3T340701200A3T4>1000010550B3T5>100002050B22.7海量數(shù)據的交互式分析工具Dremel由于Dremel并不開源，我們只能通過Google論文中的分析大致了解其性能。Google的實驗數(shù)據集規(guī)模如下圖：性能分析302.7海量數(shù)據的交互式分析工具Dremel性能分析MR從面向記錄轉換到列狀存儲后性能提升了一個數(shù)量級（從小時到分鐘），而使用Dremel則又提升了一個數(shù)量級（從分鐘到秒）2.7海量數(shù)據的交互式分析工具Dremel2.7.1產生背景2.7.2數(shù)據模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結322.7海量數(shù)據的交互式分析工具Dremel小結Dremel和MapReduce并不是互相替代，而是相互補充的技術。在不同的應用場景下各有其用武之地。Drill的設計目標就是復制一個開源的Dremel，但是從目前來看，該項目無論是進展還是影響力都達不到Hadoop的高度。希望未來能出現(xiàn)一個真正有影響力的開源系統(tǒng)實現(xiàn)Dremel的主要功能并被廣泛采用。123目錄

2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據處理MapReduce2.3分布式鎖服務Chubby2.4分布式結構化數(shù)據表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構Dapper2.7海量數(shù)據的交互式分析工具Dremel2.8內存大數(shù)據分析系統(tǒng)PowerDrill2.9Google應用程序引擎2.8內存大數(shù)據分析系統(tǒng)PowerDrill2.8.1產生背景與設計目標2.8.2基本數(shù)據結構2.8.3性能優(yōu)化2.8.4性能分析與對比352.8內存大數(shù)據分析系統(tǒng)PowerDrill產生背景與設計目標用戶對于實時的交互式數(shù)據查詢和分析一直都有很高的要求一些數(shù)據探索場景：

先向系統(tǒng)發(fā)出請求

根據結果修正查詢內容

再次向系統(tǒng)發(fā)出新的查詢

如此反復……MapReduce無法實現(xiàn)這種程度的交互式查詢，Dremel在一定程度上（數(shù)據規(guī)模比較小的情況下）能實現(xiàn)隨著數(shù)據規(guī)模的增大和內部對adhoc（即席查詢）查詢需求的增多，Google設計開發(fā)了新的交互式查詢系統(tǒng)PowerDrill362.8內存大數(shù)據分析系統(tǒng)PowerDrill產生背景與設計目標adhoc（即席查詢）查詢是用戶根據自己的需求，靈活地選擇查詢條件，系統(tǒng)根據用戶的選擇生成相應的統(tǒng)計結果。通常的查詢在系統(tǒng)設計和實施時是已知的，在構建系統(tǒng)是通過建立索引，分區(qū)等技術來優(yōu)化查詢Adhoc查詢是用戶在使用時臨時產生的，系統(tǒng)無法優(yōu)化，需要通過其它手段來實現(xiàn)高效的adhoc查詢372.8內存大數(shù)據分析系統(tǒng)PowerDrill產生背景與設計目標兩個假設結論（1）絕大多數(shù)的查詢是類似和一致的；（2）存儲系統(tǒng)中的表只有一小部分是經常被使用的，絕大部分的表使用頻率不高?？紤]兩方面的內容（1）如何盡可能在查詢中略去不需要的數(shù)據分塊；（2）如何盡可能地減少數(shù)據在內存中的占用，占用越少意味著越多的數(shù)據可以被加載進內存中處理。PowerDrill整個系統(tǒng)實際分為三個部分WebUI一個抽象層列式存儲2.8內存大數(shù)據分析系統(tǒng)PowerDrill2.8.1產生背景與設計目標2.8.2基本數(shù)據結構2.8.3性能優(yōu)化2.8.4性能分析與對比392.8內存大數(shù)據分析系統(tǒng)PowerDrill基本數(shù)據結構列式存儲：減少查詢涉及的數(shù)據量；便于數(shù)據壓縮。關系數(shù)據庫通過索引來減少查詢中用到的數(shù)據量，但adhoc查詢場景中索引不起作用PowerDrill的解決方式是對數(shù)據進行分塊，巧妙設計塊數(shù)據的數(shù)據結構，使得查詢時可以確定那些塊不需要，可直接略去，大大減少了所需數(shù)據量402.8內存大數(shù)據分析系統(tǒng)PowerDrill下圖闡述了PowerDrill采用的數(shù)據結構，簡單來說就是一個雙層數(shù)據字典結構。塊字典記錄的是塊id（chunk-id）和全局id的映射關系塊元素記錄的是塊中存儲數(shù)據的塊id（注意不是全局id）基本數(shù)據結構全局字典表存儲全局id和搜索關鍵字的對應關系3個塊的數(shù)據2.8內存大數(shù)據分析系統(tǒng)PowerDrill2.8.1產生背景與設計目標2.8.2基本數(shù)據結構2.8.3性能優(yōu)化2.8.4性能分析與對比422.8內存大數(shù)據分析系統(tǒng)PowerDrill數(shù)據分塊傳統(tǒng)的索引對于PowerDrill的查詢場景作用不是很大，因此一個很自然的考慮就是對數(shù)據進行分塊，過濾查詢中不需要的數(shù)據塊來減少數(shù)據量背景常見的分區(qū)方法有范圍分區(qū)、散列分區(qū)等。PowerDrill實際采用的是一種組合范圍分區(qū)方法。方法領域專家確定若干個劃分的域步驟利用這幾個域對數(shù)據進行劃分每個塊的行數(shù)達到閾值時就停止劃分局限PowerDrill采用的數(shù)據分塊方法簡單實用，但是由于域的確定需要領域專家，因此這種方法在實際使用中還有一定的局限性432.8內存大數(shù)據分析系統(tǒng)PowerDrill數(shù)據編碼的優(yōu)化統(tǒng)計一組數(shù)中不同值的個數(shù)有一個專有名詞，稱為“基數(shù)估計”對于小規(guī)模的數(shù)據集，可以比較容易地統(tǒng)計出精確的基數(shù)。但是在大數(shù)據的環(huán)境下，精確的基數(shù)統(tǒng)計非常耗時，因此能保證一定精度的基數(shù)估計就可以滿足實際的需求。基數(shù)估計的方法很多，大多利用了散列函數(shù)的一些特性，Google內部使用的是一種稱為Hyperloglog的基數(shù)估計方法的變種。對于不同的塊，如果我們可以確定塊中不同值的數(shù)量，那么就可以根據這個數(shù)量值來選擇可變的比特位來記錄塊id442.8內存大數(shù)據分析系統(tǒng)PowerDrill全局字典優(yōu)化優(yōu)化中主要利用兩個特性全局字典是有序的排序后的數(shù)據常常有共同的前綴對每個全局字典塊還會維護一個布隆過濾器（bloomfilter）來快速確定某個值是否在字典中。實際使用中為了進一步減少查詢中需要加載到內存的全局字典，對全局字典又進行了分塊452.8內存大數(shù)據分析系統(tǒng)PowerDrill算法壓縮后剩余數(shù)據百分比編碼速度解碼速度GZIP13.4%21MB/s118MB/sLZO20.5%135MB/s410MB/sZippy/Snappy22.2%172MB/s409MB/s壓縮算法Google曾經對一些主流的壓縮算法做過簡單的測試，如下圖：不管壓縮算法的解壓速度多快，總會消耗一定的物理資源與時間。對此PowerDrill采用了一種冷熱數(shù)據分別對待的策略。在冷熱數(shù)據切換策略中，比較常用的是LRU算法。PowerDrill開發(fā)團隊采用了啟發(fā)式的緩存策略來代替原始的LRU算法。462.8內存大數(shù)據分析系統(tǒng)PowerDrill行的重排數(shù)據壓縮的算法有很多，比較常用的一種稱為游程編碼（Run-LengthEncoding，RLE），又稱行程長度編碼，其好處是壓縮和解壓縮都非常快。數(shù)據重排的過程等效于著名的TSP（旅行商）問題PowerDrill在實際生產環(huán)境中對數(shù)據分塊時選定的那幾個域按照字典序進行排序來得到重排的結果010011100兩個等長字符串之間的漢明距離是兩個字符串對應位置的不同字符的個數(shù)2.8內存大數(shù)據分析系統(tǒng)PowerDrill2.8.1產生背景與設計目標2.8.2基本數(shù)據結構2.8.3性能優(yōu)化2.8.4性能分析與對比482.8內存大數(shù)據分析系統(tǒng)PowerDrill我們比較關注的兩組數(shù)據在查詢過程中，平均92.41%的數(shù)據被略去5.02%的數(shù)據會直接被緩存命中一般僅須掃描2.66%的數(shù)據即可得到查詢結果超過70%的查詢是不需要從磁盤訪問任何數(shù)據的這些查詢的平均訪問延遲大約是25秒96.5%的查詢需要訪問的磁盤量不超過1GB492.8內存大數(shù)據分析系統(tǒng)PowerDrill性能分析與對比訪問數(shù)據量（GB）延遲時間（s）502.8內存大數(shù)據分析系統(tǒng)PowerDrillPowerDrillDremel設計目標處理非常大量的數(shù)據集分析少量的核心數(shù)據集設計理念處理的數(shù)據來自外存處理的數(shù)據盡可能地存于內存未進行數(shù)據分區(qū)，分析時要掃描所有需要的列使用了組合范圍分區(qū)，分析時可以跳過很多不需要的分區(qū)數(shù)據通常不需要加載，增加數(shù)據很方便數(shù)據需要加載，增加數(shù)據相對不便PowerDrill與Dremel的對比目錄

2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據處理MapReduce2.3分布式鎖服務Chubby2.4分布式結構化數(shù)據表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構Dapper2.7海量數(shù)據的交互式分析工具Dremel2.8內存大數(shù)據分析系統(tǒng)PowerDrill2.9Google應用程序引擎2.9Google應用程序引擎2.9.1GoogleAppEngine簡介2.9.2應用程序環(huán)境2.9.3GoogleAppEngine服務什么是GoogleAppEngineGoogleAppEngine是一個由Python應用服務器群、Bigtable數(shù)據庫及GFS數(shù)據存儲服務組成的平臺，它能為開發(fā)者提供一體化的可自動升級的在線應用服務。GoogleAppEngine可以讓開發(fā)人員在Google的基礎架構上運行網絡應用程序。在GoogleAppEngine中，用戶可以使用域上的免費域名為應用程序提供服務，也可以使用Google企業(yè)應用套件從自己的域為它提供服務?？梢悦赓M使用GoogleAppEngine。注冊一個免費賬戶即可開發(fā)和發(fā)布應用程序，而且不需要承擔任何費用和責任。GoogleAppEngine552.9Google應用程序引擎GoogleAppEngine的整體架構前端和靜態(tài)文件負責將請求轉發(fā)給應用服務器并進行負載均衡和靜態(tài)文件的傳輸應用服務器能同時運行多個應用的運行時（Runtime）服務器群提供了一些服務，主要有Memcache、Images、URLfetch、E-mail和DataStore等應用管理節(jié)點主要負責應用的啟停和計費。2.9Google應用程序引擎2.9.1GoogleAppEngine簡介2.9.2應用程序環(huán)境2.9.3GoogleAppEngine服務572.9Google應用程序引擎動態(tài)網絡服務功能。能夠完全支持常用的網絡技術。具有持久存儲的空間。在這個空間里平臺可以支持一些基本操作，如查詢、分類和事務的操作。具有自主平衡網絡和系統(tǒng)的負載、自動進行擴展的功能。可以對用戶的身份進行驗證，并且支持使用Google賬戶發(fā)送郵件。有一個功能完整的本地開發(fā)環(huán)境，可以在自身的計算機上模擬GoogleAppEngine環(huán)境。支持在指定時間或定