云計(jì)算（第三版）配套之05第2章Google云計(jì)算原理與應(yīng)用（四）

目錄

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

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

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