云計算（第三版）配套之05第2章Google云計算原理與應用（四）

目錄

2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據(jù)處理MapReduce2.3分布式鎖效勞Chubby2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6大規(guī)模分布式系統(tǒng)的監(jiān)控根底架構(gòu)Dapper2.7海量數(shù)據(jù)的交互式分析工具Dremel2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9Google應用程序引擎數(shù)據(jù)本身不會產(chǎn)生價值只有經(jīng)過分析才有可能產(chǎn)生價值2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)4產(chǎn)生背景2.7海量數(shù)據(jù)的交互式分析工具DremelMapReduce優(yōu)點：便攜缺點：效率低2.7海量數(shù)據(jù)的交互式分析工具DremelDremel支持的典型應用Web文檔的分析Android市場的應用安裝數(shù)據(jù)的跟蹤Google產(chǎn)品的錯誤報告Google圖書的光學字符識別欺詐信息的分析Google地圖的調(diào)試Bigtable實例上的tablet遷移Google分布式構(gòu)建系統(tǒng)的測試結(jié)果分析磁盤I/O信息的統(tǒng)計Google數(shù)據(jù)中心上運行任務的資源監(jiān)控Google代碼庫的符號和依賴關(guān)系分析52.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)7一方面：統(tǒng)一的存儲平臺另一方面：統(tǒng)一的數(shù)據(jù)存儲格式實現(xiàn)高效的數(shù)據(jù)存儲，Dremel使用的底層數(shù)據(jù)存儲平臺是GFS存儲的數(shù)據(jù)才可以被不同的平臺所使用2.7海量數(shù)據(jù)的交互式分析工具Dremel82.7海量數(shù)據(jù)的交互式分析工具Dremel面向記錄和面向列的存儲Google的Dremel是第一個在嵌套數(shù)據(jù)模型根底上實現(xiàn)列存儲的系統(tǒng)。列存儲更利于數(shù)據(jù)的壓縮處理時只需要使用涉及的列數(shù)據(jù)好處一：好處二：92.7海量數(shù)據(jù)的交互式分析工具Dremel嵌套模型的形式化定義原子類型〔AtomicType〕原子類型允許的取值類型包括整型、浮點型、字符串等記錄類型〔RecordType〕記錄類型那么可以包含多個域記錄型數(shù)據(jù)包括三種類型：必須的〔Required〕、可重復的〔Repeated〕以及可選的〔Optional〕102.7海量數(shù)據(jù)的交互式分析工具Dremel嵌套結(jié)構(gòu)的模式和實例文檔的模式〔Schema〕定義符合該模式的兩條記錄利用該數(shù)據(jù)模型，可以使用Java語言，也可以使用C++語言來處理數(shù)據(jù)，甚至可以用Java編寫的MapReduce程序直接處理C++語言產(chǎn)生的數(shù)據(jù)集。這種跨平臺的優(yōu)良特性正是Google所需要的。2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)122.7海量數(shù)據(jù)的交互式分析工具Dremel數(shù)據(jù)結(jié)構(gòu)的無損表示帶有重復深度和定義深度的r1與r2的列存儲重復深度主要關(guān)注的是可重復類型，而定義深度同時關(guān)注可重復類型和可選類型〔optional〕每一列最終會被存儲為塊〔Block〕的集合，每個塊包含重復深度和定義深度且包含字段值。132.7海量數(shù)據(jù)的交互式分析工具Dremel高效的數(shù)據(jù)編碼計算重復和定義深度的根底算法Dremel利用圖中算法創(chuàng)立一個樹狀結(jié)構(gòu)樹的節(jié)點為字段的writer，它的結(jié)構(gòu)與模式中的字段層級匹配。核心的想法是只在字段writer有自己的數(shù)據(jù)時執(zhí)行更新，非絕對必要時不嘗試往下傳遞父節(jié)點狀態(tài)。子節(jié)點writer繼承父節(jié)點的深度值。當任意值被添加時，子writer將深度值同步到父節(jié)點。142.7海量數(shù)據(jù)的交互式分析工具Dremel數(shù)據(jù)重組Dremel數(shù)據(jù)重組方法的核心思想是為每個字段創(chuàng)立一個有限狀態(tài)機〔FSM〕，讀取字段值和重復深度，然后順序地將值添加到輸出結(jié)果上。15當前FSM寫入值下一個重復深度值動作DocId（開始）100跳轉(zhuǎn)至Links.BackwardLinks.BackwardNULL0跳轉(zhuǎn)至Links.ForwardLinks.Forward201停留在Links.ForwardLinks.Forward401停留在Links.ForwardLinks.Forward600跳轉(zhuǎn)至Name.Language.CodeName.Language.Codeen-us2跳轉(zhuǎn)至Name.Language.CountryName.Language.Countryus2跳轉(zhuǎn)至Name.Language.CodeName.Language.Codeen1跳轉(zhuǎn)至Name.Language.CountryName.Language.CountryNULL1跳轉(zhuǎn)至Name.UrlName.Urlhttp://A1跳轉(zhuǎn)至Name.Language.CodeName.Language.CodeNULL1跳轉(zhuǎn)至Name.Language.CountryName.Language.CountryNULL1跳轉(zhuǎn)至Name.UrlName.Urlhttp://B1跳轉(zhuǎn)至Name.Language.CodeName.Language.Codeen-gb0跳轉(zhuǎn)至Name.Language.CountryName.Language.Countrygb0跳轉(zhuǎn)至Name.UrlName.UrlNULL0結(jié)束2.7海量數(shù)據(jù)的交互式分析工具Dremel數(shù)據(jù)重組r1的完整數(shù)據(jù)重組過程162.7海量數(shù)據(jù)的交互式分析工具Dremel數(shù)據(jù)重組如果具體的查詢中不是涉及所有列，而是僅涉及很少的列的話，上述數(shù)據(jù)重組的過程會更加便利，以下圖中僅僅涉及DocId和的有限狀態(tài)機。172.7海量數(shù)據(jù)的交互式分析工具Dremel數(shù)據(jù)重組核心的思想如下：設(shè)置t為當前字段讀取器的當前值f所返回的下一個重復深度。在模式樹中，找到它在深度t的祖先，然后選擇該祖先節(jié)點的第一個葉子字段n。由此得到一個FSM狀態(tài)變化(f,t)->n。有限狀態(tài)機的構(gòu)造算法2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)192.7海量數(shù)據(jù)的交互式分析工具Dremel查詢語言與執(zhí)行Dremel的SQL查詢輸入的是一個或多個嵌套結(jié)構(gòu)的表以及相應的模式，而輸出的結(jié)果是一個嵌套結(jié)構(gòu)的表以及相應的模式。嵌套子查詢記錄內(nèi)聚合top-kjoins自定義函數(shù)……202.7海量數(shù)據(jù)的交互式分析工具DremelDremel利用多層級效勞樹〔multi-levelservicetree〕的概念來執(zhí)行查詢操作根效勞器接受客戶端發(fā)出的請求，讀取相應的元數(shù)據(jù)，將請求轉(zhuǎn)發(fā)至中間效勞器。中間效勞器負責查詢中間結(jié)果的聚集葉子效勞器負責執(zhí)行數(shù)據(jù)來源查詢語言與執(zhí)行21查詢語言與執(zhí)行Dremel中的數(shù)據(jù)都是分布式存儲的，因此每一層查詢涉及的數(shù)據(jù)實際都被水平劃分后存儲在多個效勞器上。Dremel是一個多用戶系統(tǒng)，因此同一時刻往往會有多個用戶進行查詢。查詢分發(fā)器有一個很重要參數(shù)，它表示在返回結(jié)果之前一定要掃描百分之多少的tablet2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)23表名記錄數(shù)（億)規(guī)模（未壓縮，TB）域數(shù)目數(shù)據(jù)中心復制因子T185087270A3T224013530A3T340701200A3T4>1000010550B3T5>100002050B22.7海量數(shù)據(jù)的交互式分析工具Dremel由于Dremel并不開源，我們只能通過Google論文中的分析大致了解其性能。Google的實驗數(shù)據(jù)集規(guī)模如以下圖：性能分析242.7海量數(shù)據(jù)的交互式分析工具Dremel性能分析MR從面向記錄轉(zhuǎn)換到列狀存儲后性能提升了一個數(shù)量級〔從小時到分鐘〕，而使用Dremel那么又提升了一個數(shù)量級〔從分鐘到秒〕2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)262.7海量數(shù)據(jù)的交互式分析工具Dremel小結(jié)Drill的設(shè)計目標就是復制一個開源的Dremel，但是從目前來看，該工程無論是進展還是影響力都達不到Hadoop的高度。希望未來能出現(xiàn)一個真正有影響力的開源系統(tǒng)實現(xiàn)Dremel的主要功能并被廣泛采用。123目錄

2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據(jù)處理MapReduce2.3分布式鎖效勞Chubby2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6大規(guī)模分布式系統(tǒng)的監(jiān)控根底架構(gòu)Dapper2.7海量數(shù)據(jù)的交互式分析工具Dremel2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9Google應用程序引擎2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.8.1產(chǎn)生背景與設(shè)計目標2.8.2根本數(shù)據(jù)結(jié)構(gòu)2.8.3性能優(yōu)化2.8.4性能分析與比照292.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill產(chǎn)生背景與設(shè)計目標兩個假設(shè)結(jié)論〔1〕絕大多數(shù)的查詢是類似和一致的；〔2〕存儲系統(tǒng)中的表只有一小局部是經(jīng)常被使用的，絕大局部的表使用頻率不高?？紤]兩方面的內(nèi)容〔1〕如何盡可能在查詢中略去不需要的數(shù)據(jù)分塊；〔2〕如何盡可能地減少數(shù)據(jù)在內(nèi)存中的占用，占用越少意味著越多的數(shù)據(jù)可以被加載進內(nèi)存中處理。PowerDrill整個系統(tǒng)實際分為三個局部WebUI一個抽象層列式存儲2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.8.1產(chǎn)生背景與設(shè)計目標2.8.2根本數(shù)據(jù)結(jié)構(gòu)2.8.3性能優(yōu)化2.8.4性能分析與比照312.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill以下圖闡述了PowerDrill采用的數(shù)據(jù)結(jié)構(gòu)，簡單來說就是一個雙層數(shù)據(jù)字典結(jié)構(gòu)。塊字典記錄的是塊id〔chunk-id〕和全局id的映射關(guān)系塊元素記錄的是塊中存儲數(shù)據(jù)的塊id〔注意不是全局id〕根本數(shù)據(jù)結(jié)構(gòu)全局字典表存儲全局id和搜索關(guān)鍵字的對應關(guān)系3個塊的數(shù)據(jù)2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.8.1產(chǎn)生背景與設(shè)計目標2.8.2根本數(shù)據(jù)結(jié)構(gòu)2.8.3性能優(yōu)化2.8.4性能分析與比照332.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill數(shù)據(jù)分塊傳統(tǒng)的索引對于PowerDrill的查詢場景作用不是很大，因此一個很自然的考慮就是對數(shù)據(jù)進行分塊，過濾查詢中不需要的數(shù)據(jù)塊來減少數(shù)據(jù)量背景常見的分區(qū)方法有范圍分區(qū)、散列分區(qū)等。PowerDrill實際采用的是一種組合范圍分區(qū)方法。方法領(lǐng)域?qū)＜掖_定假設(shè)干個劃分的域步驟利用這幾個域?qū)?shù)據(jù)進行劃分每個塊的行數(shù)到達閾值時就停止劃分局限PowerDrill采用的數(shù)據(jù)分塊方法簡單實用，但是由于域確實定需要領(lǐng)域?qū)＜遥虼诉@種方法在實際使用中還有一定的局限性342.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill數(shù)據(jù)編碼的優(yōu)化統(tǒng)計一組數(shù)中不同值的個數(shù)有一個專有名詞，稱為“基數(shù)估計〞對于小規(guī)模的數(shù)據(jù)集，可以比較容易地統(tǒng)計出精確的基數(shù)。但是在大數(shù)據(jù)的環(huán)境下，精確的基數(shù)統(tǒng)計非常耗時，因此能保證一定精度的基數(shù)估計就可以滿足實際的需求?；鶖?shù)估計的方法很多，大多利用了散列函數(shù)的一些特性，Google內(nèi)部使用的是一種稱為Hyperloglog的基數(shù)估計方法的變種。對于不同的塊，如果我們可以確定塊中不同值的數(shù)量，那么就可以根據(jù)這個數(shù)量值來選擇可變的比特位來記錄塊id352.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill全局字典優(yōu)化優(yōu)化中主要利用兩個特性全局字典是有序的排序后的數(shù)據(jù)常常有共同的前綴對每個全局字典塊還會維護一個布隆過濾器〔bloomfilter〕來快速確定某個值是否在字典中。實際使用中為了進一步減少查詢中需要加載到內(nèi)存的全局字典，對全局字典又進行了分塊362.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill算法壓縮后剩余數(shù)據(jù)百分比編碼速度解碼速度GZIP13.4%21MB/s118MB/sLZO20.5%135MB/s410MB/sZippy/Snappy22.2%172MB/s409MB/s壓縮算法Google曾經(jīng)對一些主流的壓縮算法做過簡單的測試，如以下圖：不管壓縮算法的解壓速度多快，總會消耗一定的物理資源與時間。對此PowerDrill采用了一種冷熱數(shù)據(jù)分別對待的策略。在冷熱數(shù)據(jù)切換策略中，比較常用的是LRU算法。PowerDrill開發(fā)團隊采用了啟發(fā)式的緩存策略來代替原始的LRU算法。372.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill行的重排數(shù)據(jù)壓縮的算法有很多，比較常用的一種稱為游程編碼〔Run-LengthEncoding，RLE〕，又稱行程長度編碼，其好處是壓縮和解壓縮都非?？?。數(shù)據(jù)重排的過程等效于著名的TSP〔旅行商〕問題PowerDrill在實際生產(chǎn)環(huán)境中對數(shù)據(jù)分塊時選定的那幾個域按照字典序進行排序來得到重排的結(jié)果010011100兩個等長字符串之間的漢明距離是兩個字符串對應位置的不同字符的個數(shù)2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.8.1產(chǎn)生背景與設(shè)計目標2.8.2根本數(shù)據(jù)結(jié)構(gòu)2.8.3性能優(yōu)化2.8.4性能分析與比照392.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill我們比較關(guān)注的兩組數(shù)據(jù)在查詢過程中，平均92.41%的數(shù)據(jù)被略去5.02%的數(shù)據(jù)會直接被緩存命中一般僅須掃描2.66%的數(shù)據(jù)即可得到查詢結(jié)果超過70%的查詢是不需要從磁盤訪問任何數(shù)據(jù)的這些查詢的平均訪問延遲大約是25秒96.5%的查詢需要訪問的磁盤量不超過1GB402.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill性能分析與比照訪問數(shù)據(jù)量〔GB〕延遲時間〔s〕412.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrillPowerDrillDremel設(shè)計目標處理非常大量的數(shù)據(jù)集分析少量的核心數(shù)據(jù)集設(shè)計理念處理的數(shù)據(jù)來自外存處理的數(shù)據(jù)盡可能地存于內(nèi)存未進行數(shù)據(jù)分區(qū)，分析時要掃描所有需要的列使用了組合范圍分區(qū)，分析時可以跳過很多不需要的分區(qū)數(shù)據(jù)通常不需要加載，增加數(shù)據(jù)很方便數(shù)據(jù)需要加載，增加數(shù)據(jù)相對不便PowerDrill與Dremel的比照目錄

2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據(jù)處理MapReduce2.3分布式鎖效勞Chubby2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6大規(guī)模分布式系統(tǒng)的監(jiān)控根底架構(gòu)Dapper2.7海量數(shù)據(jù)的交互式分析工具Dremel2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9Google應用程序引擎2.9Google應用程序引擎2.9.1GoogleAppEngine簡介2.9.2應用程序環(huán)境2.9.3GoogleAppEngine效勞什么是GoogleAppEngineGoogleAppEngine是一個由Python應用效勞器群、Bigtable數(shù)據(jù)庫及GFS數(shù)據(jù)存儲效勞組成的平臺，它能為開發(fā)者提供一體化的可自動升級的在線應用效勞。GoogleAppEngine可以讓開發(fā)人員在Google的根底架構(gòu)上運行網(wǎng)絡應用程序。在GoogleAppEngine中，用戶可以使用appspot域上的免費域名為應用程序提供效勞，也可以使用Google企業(yè)應用套件從自己的域為它提供效勞?？梢悦赓M使用GoogleAppEngine。注冊一個免費賬戶即可開發(fā)和發(fā)布應用程序，而且不需要承擔任何費用和責任。GoogleAppEngine462.9Google應用程序引擎GoogleAppEngine的整體架構(gòu)前端和靜態(tài)文件負責將請求轉(zhuǎn)發(fā)給應用效勞器并進行負載均衡和靜態(tài)文件的傳輸應用效勞器能同時運行多個應用的運行時〔Runtime〕效勞器群提供了一些效勞，主要有Memcache、Images、URLfetch、E-mail和DataStore等應用管理節(jié)點主要負責應用的啟停和計費。2.9Google應用程序引擎2.9.1GoogleAppEngine簡介2.9.2應用程序環(huán)境2.9.3GoogleAppEngine效勞482.9Google應