大數(shù)據(jù)存儲(chǔ)與處理-第二講51

1、大數(shù)據(jù)的三個(gè)關(guān)鍵問題Google的大數(shù)據(jù)技術(shù)Google的業(yè)務(wù)：PageRank三大法寶1第二講 大數(shù)據(jù)的關(guān)鍵技術(shù)文件存儲(chǔ)儲(chǔ)數(shù)據(jù)分析析數(shù)據(jù)計(jì)算算數(shù)據(jù)存儲(chǔ)儲(chǔ)平臺(tái)管理數(shù)據(jù)集成成數(shù)據(jù)源DatabaseWebLog現(xiàn)代數(shù)據(jù)據(jù)處理能力組件件現(xiàn)代數(shù)據(jù)據(jù)處理框框架三大關(guān)鍵鍵問題3V計(jì)算存儲(chǔ)容錯(cuò)三大關(guān)鍵鍵問題存儲(chǔ)計(jì)算容錯(cuò)存儲(chǔ)問題題解決大數(shù)據(jù)存儲(chǔ)效率的兩方面面：容量吞吐量容量單硬盤容容量提升升：MBGBTB系統(tǒng)整體體容量提提升：DAS、NAS、SAN吞吐量=傳輸數(shù)據(jù)據(jù)量/傳輸時(shí)間間單硬盤吞吞吐量提提升：轉(zhuǎn)轉(zhuǎn)速、接接口、緩緩存等節(jié)點(diǎn)吞吐吐量提升升：RAID、專用數(shù)數(shù)據(jù)庫機(jī)機(jī)提升吞吐吐量RAID：Redundant

2、ArrayofInexpensiveDisks，冗冗余磁盤盤陣列把多塊獨(dú)獨(dú)立的硬硬盤按一一定的方方式組合合起來形形成一個(gè)個(gè)硬盤組組，從而而實(shí)現(xiàn)高高性能和高可可靠性RAID0：連連續(xù)以位位或字節(jié)節(jié)為單位位分割數(shù)數(shù)據(jù)，并并行讀/寫于多多個(gè)磁盤盤上，提提升吞吐量三大關(guān)鍵鍵問題存儲(chǔ)計(jì)算容錯(cuò)多核技術(shù)術(shù)Moor定律：當(dāng)價(jià)格格不變時(shí)時(shí)，集成成電路上上可容納納的晶體體管數(shù)目目，約每每隔18個(gè)個(gè)月便會(huì)會(huì)增加一一倍，性性能也將將提升一一倍。采用多核核（Multi-core）技術(shù)提提升IPC，從從而突破破性能提提升瓶頸頸。指令數(shù)主頻IPSMFIPC 多處理器器技術(shù)多處理器器技術(shù)的的核心：按處理器器之間的的關(guān)系可可以

3、分為為兩類：1F1F/N非對稱多多處理器器架構(gòu)（ASMP）不同類型型計(jì)算任任務(wù)或進(jìn)進(jìn)程由不不同處理理器執(zhí)行行簡單，操操作系統(tǒng)統(tǒng)修改小小低效早期過渡渡性架構(gòu)構(gòu)對稱多處處理器架架構(gòu)（SMP）所有處理理器完全全對等計(jì)算任務(wù)務(wù)按需分分配高效普遍采用用并行模式式獨(dú)立并行行兩個(gè)數(shù)據(jù)據(jù)操作間間沒有數(shù)數(shù)據(jù)依賴關(guān)系可以采用用獨(dú)立并并行的方方式分配給不同同的處理理器執(zhí)行行例：兩個(gè)個(gè)獨(dú)立數(shù)數(shù)據(jù)集的的Scan操作流水線并并行多個(gè)操作作間存在在依賴關(guān)關(guān)系，且且后一個(gè)操操作必須須等待前前一個(gè)操操作處理完完后方可可執(zhí)行將多個(gè)操操作分配配給不同同處理器器，但處理器器間以流流水線方方式執(zhí)行行例：ScanSortGroup分割并

4、行行數(shù)據(jù)操作作的輸入入數(shù)據(jù)可可以分解解為多個(gè)個(gè)子集，且且子集之之間相互互獨(dú)立分割為若若干獨(dú)立立的子操操作，每每個(gè)子操操作只處理理對應(yīng)的的部分?jǐn)?shù)數(shù)據(jù)，并并將這些些子操作配配到不同同的處理理器上執(zhí)執(zhí)行例：ScanMerge并行系統(tǒng)統(tǒng)架構(gòu)共享內(nèi)存存（SharedMemory，SM）多個(gè)處理理器，多多個(gè)磁盤盤，一個(gè)個(gè)共享內(nèi)存，通通過數(shù)據(jù)據(jù)總線相相連處理器間間共享全全部磁盤盤和內(nèi)存存結(jié)構(gòu)簡單單，負(fù)載載均衡數(shù)據(jù)總線線成為瓶瓶頸，可可擴(kuò)展性性較差，共享內(nèi)存存單點(diǎn)故故障適合處理理器較少少（8）的小小規(guī)模并并行數(shù)據(jù)庫庫共享磁盤盤（SharedDisk，SD）多個(gè)處理理器，每每個(gè)處理理器擁有有獨(dú)立內(nèi)存，多多個(gè)磁盤

5、盤，處理理器與磁磁盤通過數(shù)據(jù)總總線相連連處理器間間共享全全部磁盤盤容錯(cuò)性提提高共享磁盤盤成為性性能瓶頸頸，需要要額外維護(hù)內(nèi)存存與磁盤盤間的數(shù)數(shù)據(jù)一致致性無共享（SharedNothing，SN）每個(gè)處理理器擁有有獨(dú)立的的內(nèi)存和和若干磁磁盤，通過高速速網(wǎng)絡(luò)相相連處理器獨(dú)獨(dú)立處理理所管理理的數(shù)據(jù)據(jù)數(shù)據(jù)傳輸輸量小，效率高高可擴(kuò)展性性強(qiáng)節(jié)點(diǎn)間交交換數(shù)據(jù)據(jù)開銷較較大適合處理理器數(shù)量量較大的的大規(guī)模模并行系系統(tǒng)后期發(fā)展展的主流流三大關(guān)鍵鍵問題存儲(chǔ)計(jì)算容錯(cuò)數(shù)據(jù)容錯(cuò)RAID單節(jié)點(diǎn)點(diǎn)數(shù)據(jù)冗冗余存儲(chǔ)儲(chǔ)集群多節(jié)節(jié)點(diǎn)數(shù)據(jù)據(jù)冗余存存儲(chǔ)計(jì)算任務(wù)務(wù)容錯(cuò)計(jì)算任務(wù)務(wù)容錯(cuò)的的關(guān)鍵問問題：故障監(jiān)測測計(jì)算數(shù)據(jù)據(jù)定位與與獲取任務(wù)遷移移

6、Google是是如何解解決其大數(shù)據(jù)處理理的三個(gè)個(gè)關(guān)鍵性性問題的的?我們需要要先了解解Google的業(yè)務(wù)特特點(diǎn)。14Google的大數(shù)據(jù)據(jù)技術(shù)1995199619971999200120032005200720092011.19982000200220042006200820102012當(dāng)佩奇遇遇見布林合作開發(fā)發(fā)BackRub搜索引擎擎命名GoogleGoogle公司成立立首名專用用廚師入職職建立10億網(wǎng)址的索索引圖片搜索索+30億億網(wǎng)址索引商品+新新聞+API開始收購購+Google圖書80億網(wǎng)網(wǎng)址索引+上上市+學(xué)術(shù)搜搜索地圖+Talk+分析YouTube+GoogleAppsGmail+街景

7、+AndroidHealth+iPhone應(yīng)用社交網(wǎng)絡(luò)絡(luò)搜索+實(shí)實(shí)時(shí)地圖導(dǎo)航航+搜索收購Moto手機(jī)+投投平板電腦腦資能源+Google應(yīng)用商店店眼鏡GoogleGoogle最最重要的的業(yè)務(wù)？搜索AdWordsGoogle發(fā)發(fā)展史Google之之前的搜搜索目錄型搜搜索：Yahoo!收集：人人工分類類索引：主主題使用：目目錄結(jié)構(gòu)構(gòu)優(yōu)點(diǎn)：準(zhǔn)準(zhǔn)確率高高缺點(diǎn)：覆覆蓋率低低索引型搜搜索：AltaVista收集：自自動(dòng)爬取?。⊿cooter）索引：自自動(dòng)標(biāo)記記使用：輸輸入關(guān)鍵鍵詞搜索索優(yōu)點(diǎn)：覆覆蓋率高高缺點(diǎn)：準(zhǔn)準(zhǔn)確率低低覆蓋率VS.準(zhǔn)確率：魚與熊熊掌不可可兼得？GoogleGoogle的的自我揭揭秘！核心

8、算法法LawrencePage,SergeyBrin,et.al.,ThePageRankCitationRanking:BringingOrdertotheWeb.TechnicalReport,StanfordInfoLab,1999.(6881)三大法寶寶SanjayGhemawat,HowardGobioff,et.al.,TheGooglefilesystem,ProceedingsoftheNineteenthACMSymposiumonOperatingSystemsPrinciples,2003.(3911)JeffreyDean,SanjayGhemawat,MapReduc

9、e:SimplifiedDataProcessingonLargeClusters,SixthSymposiumonOperatingSystemDesignandImplementation,2004.(9569)FayChang,JeffreyDean,et.al.,Bigtable:ADistributedStorageSystemforStructuredData,SeventhSymposiumonOperatingSystemDesignandImplementation,2006.(2558)靈魂血肉搜索結(jié)果果如何排排序！佩奇（Page），斯斯坦福整個(gè)互聯(lián)聯(lián)網(wǎng)就像像一張大大的圖，

10、每個(gè)網(wǎng)網(wǎng)站就像像一個(gè)節(jié)節(jié)點(diǎn)，每個(gè)網(wǎng)頁頁的鏈接接就像一一個(gè)弧。我想，互聯(lián)網(wǎng)網(wǎng)可以用用一個(gè)圖或者矩矩陣描述述，我也也許可以以用這個(gè)個(gè)發(fā)現(xiàn)做做篇博士士論文。算法的圖圖論表述述01/201/20001/201/200010000011/31/31/300n1n2n3n4n5PageRank（9）算法的計(jì)計(jì)算問題題如何計(jì)算算10億億、100億個(gè)個(gè)網(wǎng)頁？行列數(shù)以以億為單單位的矩矩陣相乘乘！Google三三大法寶寶之一：MapReduce矩陣乘法法串行實(shí)實(shí)現(xiàn)1:fori=1;i=N;i+2:forj=1;j=N;j+3:4:5:6:fork=1;k#(58985)(reduce#+#(58985)-35Li

11、sp中的Map和和Reduce操作MapReduce原原理MapReduce機(jī)機(jī)制主控程序序（Master）：將Map和Reduce分分配到合合適的工工作機(jī)上上工作機(jī)（Worker）：執(zhí)執(zhí)行Map或Reduce任任務(wù)MapReduce不不僅僅是是編程模模型!讓程序員員在使用用MapReduce時(shí)面對對以下細(xì)細(xì)節(jié)問題題？大數(shù)據(jù)如如何分割割為小數(shù)數(shù)據(jù)塊？如何調(diào)度度計(jì)算任任務(wù)并分分配和調(diào)調(diào)度map和reduce任任務(wù)節(jié)點(diǎn)點(diǎn)？如何在任任務(wù)節(jié)點(diǎn)點(diǎn)間交換換數(shù)據(jù)？如何同步步任務(wù)？相互依賴賴的任務(wù)務(wù)是否執(zhí)執(zhí)行完成成？任務(wù)節(jié)點(diǎn)點(diǎn)失效時(shí)時(shí)該如何何處理？Google的的MapReduce是一個(gè)個(gè)完整的的計(jì)算框框架程

12、序員只只需要編編寫少量量的程序序?qū)崿F(xiàn)應(yīng)應(yīng)用層邏邏輯程序示例例：WordCount#includemapreduce/mapreduce.hclassWordCounter:publicMapperpublic:virtualvoidMap(constMapInput&input)conststring&text=input.value();constintn=text.size();for(inti=0;in;)while(in)&isspace(texti)i+;intstart=i;while(in)&!isspace(texti)i+;if(startdone()value+=Strin

13、gToInt(input-value();input-NextValue();Emit(IntToString(value);REGISTER_REDUCER(Adder);intmain(intargc,char*argv)ParseCommandLineFlags(argc,argv);MapReduceSpecificationspec;for(inti=1;iset_format(text);input-set_filepattern(argvi);input-set_mapper_class(WordCounter);MapReduceOutput*out=spec.output()

14、;out-set_filebase(/gfs/test/freq);out-set_num_tasks(100);out-set_format(text);out-set_reducer_class(Adder);out-set_combiner_class(Adder);spec.set_machines(2000);spec.set_map_megabytes(100);spec.set_reduce_megabytes(100);MapReduceResultresult;if(!MapReduce(spec,&result)abort();return0;Google三三大法寶寶之二：

15、GFSGFS簡簡介GFSGoogleFileSystem，Google自有的的分布式式文件系統(tǒng)為什么需需要GFS？已有多種種分布式式文件系系統(tǒng)（NFS、AFS、DFS、）Google特特有的環(huán)環(huán)境與負(fù)負(fù)載需要要Google特特有的數(shù)數(shù)據(jù)和計(jì)計(jì)算Google處處理的主主要數(shù)據(jù)據(jù)爬取的網(wǎng)網(wǎng)頁網(wǎng)站訪問問日志其他相對對獨(dú)立的的數(shù)據(jù)數(shù)據(jù)計(jì)算算的期望望結(jié)果詞頻統(tǒng)計(jì)計(jì)倒排索引引網(wǎng)頁文檔檔的鏈接接圖網(wǎng)站頁面面數(shù)量統(tǒng)統(tǒng)計(jì)特點(diǎn)單個(gè)計(jì)算算簡單數(shù)量龐大大數(shù)據(jù)相對對獨(dú)立GFS支支持大容容量用集群方方式提升升系統(tǒng)整整體容量量Google的的第一臺(tái)臺(tái)服務(wù)器器（1998）IntelCPU+IDE硬硬盤xGFS支支持高吞吞吐量

16、Google處處理的數(shù)數(shù)據(jù)特點(diǎn)點(diǎn)抓取網(wǎng)頁頁并存儲(chǔ)儲(chǔ)：順序序?qū)懭?，極少發(fā)發(fā)生隨機(jī)機(jī)寫的情情況分析網(wǎng)頁頁內(nèi)容：文件寫寫入后，只會(huì)發(fā)發(fā)生讀的的操作，不會(huì)再再修改GFS實(shí)實(shí)現(xiàn)高吞吞吐量的的兩個(gè)關(guān)關(guān)鍵點(diǎn)：順序?qū)懭肴耄樞蛐蜃x取，避免隨隨機(jī)讀寫寫文件傳輸輸效率公公式SEEK_TIMEblock_size/SPEEDSEEK_TIME1trans_timetrans_timeSEEK_TIMEeffect西數(shù)80GSATA硬盤隨機(jī)讀558.2數(shù)據(jù)以遠(yuǎn)遠(yuǎn)大于操操作系統(tǒng)統(tǒng)文件塊塊的基本本單元進(jìn)進(jìn)行存儲(chǔ)儲(chǔ)（64MBvs.512B）GFS支支持容錯(cuò)錯(cuò)問題：大大量廉價(jià)價(jià)PC組組件構(gòu)成成的集群群作為硬硬件基礎(chǔ)礎(chǔ)，單節(jié)節(jié)

17、點(diǎn)故障障率較高高Google的的第一臺(tái)臺(tái)服務(wù)器器（1998）IntelCPU+IDE硬硬盤集群多節(jié)節(jié)點(diǎn)數(shù)據(jù)據(jù)冗余存存儲(chǔ)GFS系系統(tǒng)架構(gòu)構(gòu)客戶端（Client）GFS提提供給上上層應(yīng)用用使用的的一組接口庫庫上層應(yīng)用用通過調(diào)調(diào)用接口口庫中的接口實(shí)實(shí)現(xiàn)GFS系統(tǒng)統(tǒng)中的文文件管理適合自身身應(yīng)用的的簡單接接口主控節(jié)點(diǎn)點(diǎn)（Master）管理節(jié)點(diǎn)點(diǎn)唯一性保存元數(shù)數(shù)據(jù)調(diào)配塊服服務(wù)器塊服務(wù)器器（ChunkServer）存儲(chǔ)數(shù)據(jù)據(jù)塊（Chunk）多個(gè)固定塊大大?。J(rèn)64MB）數(shù)據(jù)庫多多節(jié)點(diǎn)冗冗余備份份討論：分分析一下下，GFS的文件讀讀寫流程程大致應(yīng)應(yīng)該是怎怎么樣的的？計(jì)算索引引：客戶戶端將應(yīng)應(yīng)用提供供的文件

18、件名和字字節(jié)偏移移通過固固定文件件塊大小小進(jìn)行計(jì)計(jì)算后獲獲得塊索索引傳遞索引引：客戶戶端將文文件名稱稱和塊索索引發(fā)送送給主控控節(jié)點(diǎn)返回位置置：主控控節(jié)點(diǎn)將將用于訪訪問文件件塊的塊塊句柄和和文件塊塊所在的的塊服務(wù)務(wù)器位置置返回給給客戶端端訪問數(shù)據(jù)據(jù)：客戶戶端將位位置信息息進(jìn)行緩緩存，并并訪問離離自己距距離最近近的塊服服務(wù)器返回?cái)?shù)據(jù)據(jù)：被訪訪問的塊塊服務(wù)器器將數(shù)據(jù)據(jù)返回給給客戶端端GFS讀讀數(shù)據(jù)流流程Google三三大法寶寶之三：BigTable簡單搜索索框背后后的復(fù)雜雜工作1.Crawler從URL服務(wù)務(wù)器提取取地址進(jìn)進(jìn)行遍歷歷查找2.獲取文檔檔docs,建立文文檔docIDs,進(jìn)行分分析、壓壓

19、縮3.存儲(chǔ)到文文檔數(shù)據(jù)據(jù)庫4.索引器為為docs建立立順排索索引和倒倒排索引引5.索引數(shù)據(jù)據(jù)存儲(chǔ)到到集群中中建立索引引響應(yīng)請求求1.2.3.4.5.對請求進(jìn)進(jìn)行預(yù)處處理，包包括拼寫寫檢查、附加廣廣告等GWS向向索引服服務(wù)器發(fā)發(fā)送查詢詢關(guān)鍵字字索引服務(wù)務(wù)器根據(jù)據(jù)關(guān)鍵字字查找匹匹配文檔檔并向GWS返返回docIDsGWS將將docIDs傳給文文檔服務(wù)務(wù)器，獲獲得文檔檔GWS將將查詢結(jié)結(jié)果文檔檔以HTML形形式返回回給用戶戶為什么需需要BigTable？GFS的的局限性性：文件件系統(tǒng)，不適合合結(jié)構(gòu)化化數(shù)據(jù)的的存儲(chǔ)和和訪問結(jié)構(gòu)化數(shù)數(shù)據(jù)？使使用DB2、SQLServer、MySQL之之類的數(shù)數(shù)據(jù)庫系系統(tǒng)？非也！因因?yàn)椋捍鎯?chǔ)數(shù)據(jù)據(jù)的多樣樣性與復(fù)復(fù)雜性：URL、網(wǎng)頁內(nèi)內(nèi)容、用用戶數(shù)據(jù)據(jù)等海量的處處理請求求成本與控控制力BigTable的目目標(biāo)：適應(yīng)各種種不同類類型的數(shù)數(shù)據(jù)和應(yīng)應(yīng)用隨時(shí)增加加和減少少處理節(jié)節(jié)點(diǎn)的可可擴(kuò)展性性和自動(dòng)動(dòng)平衡能能力PB級數(shù)數(shù)據(jù)環(huán)境境下的高高吞吐量量和高并并發(fā)（百百萬級TPS）連續(xù)服務(wù)務(wù)的高可可用性和和容錯(cuò)性