大數(shù)據(jù)的關(guān)鍵技術(shù)(51p)課件

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

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

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

4、且子集之間相互獨(dú)立分割為若干獨(dú)立的子操作，每個子操作只處理對應(yīng)的部分?jǐn)?shù)據(jù)，并將這些子操作配到不同的處理器上執(zhí)行例： Scan Merge第9頁，共52頁。并行系統(tǒng)架構(gòu)共享內(nèi)存（Shared Memory，SM）多個處理器，多個磁盤，一個共享內(nèi)存，通過數(shù)據(jù)總線相連處理器間共享全部磁盤和內(nèi)存結(jié)構(gòu)簡單，負(fù)載均衡數(shù)據(jù)總線成為瓶頸，可擴(kuò)展性較差，共享內(nèi)存單點(diǎn)故障適合處理器較少（8）的小規(guī)模并行數(shù)據(jù)庫共享磁盤（Shared Disk，SD）多個處理器，每個處理器擁有獨(dú)立內(nèi)存，多個磁盤，處理器與磁盤通過數(shù)據(jù)總線相連處理器間共享全部磁盤容錯性提高共享磁盤成為性能瓶頸，需要額外維護(hù)內(nèi)存與磁盤間的數(shù)據(jù)一致性無共享

5、（Shared Nothing，SN）每個處理器擁有獨(dú)立的內(nèi)存和若干磁盤，通過高速網(wǎng)絡(luò)相連處理器獨(dú)立處理所管理的數(shù)據(jù)數(shù)據(jù)傳輸量小，效率高可擴(kuò)展性強(qiáng)節(jié)點(diǎn)間交換數(shù)據(jù)開銷較大適合處理器數(shù)量較大的大規(guī)模并行系統(tǒng)后期發(fā)展的主流第10頁，共52頁。三大關(guān)鍵問題存儲計(jì)算容錯第11頁，共52頁。數(shù)據(jù)容錯 RAID單節(jié)點(diǎn)數(shù)據(jù)冗余存儲 RAID0：并行磁盤 RAID1：鏡像冗余 RAID10：RAID1+RAID0 RAID5：校驗(yàn)冗余Source: / 集群多節(jié)點(diǎn)數(shù)據(jù)冗余存儲第12頁，共52頁。計(jì)算任務(wù)容錯 計(jì)算任務(wù)容錯的關(guān)鍵問題： 故障監(jiān)測 計(jì)算數(shù)據(jù)定位與獲取 任務(wù)遷移第13頁，共52頁。Google是如何解

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

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

8、nce Page, Sergey Brin, et. al., The PageRank Citation Ranking: Bringing Order to theWeb. Technical Report, Stanford InfoLab, 1999. (6881) 三大法寶 Sanjay Ghemawat, Howard Gobioff, et. al., The Google file system, Proceedings of theNineteenth ACM Symposium on Operating Systems Principles, 2003. (3911) Je

9、ffrey Dean, Sanjay Ghemawat, MapReduce: Simplified Data Processing on Large Clusters ,Sixth Symposium on Operating System Design and Implementation, 2004. (9569) Fay Chang, Jeffrey Dean, et. al., Bigtable: A Distributed Storage System for Structured Data,Seventh Symposium on Operating System Design

10、and Implementation, 2006. (2558)靈魂血肉第18頁，共52頁。第19頁，共52頁。 搜索結(jié)果如何排序！第20頁，共52頁。第21頁，共52頁。 佩奇（Page），斯坦福 整個互聯(lián)網(wǎng)就像一張大的圖，每個網(wǎng)站就像一個節(jié)點(diǎn)，每個網(wǎng)頁的鏈接就像一個弧。我想，互聯(lián)網(wǎng)可以用一個圖或者矩陣描述，我也許可以用這個發(fā)現(xiàn)做篇博士論文。第22頁，共52頁。 算法的圖論表述第23頁，共52頁。01/201/20001/201/200010000011/31/31/300n1n2n3 n4 n5第24頁，共52頁。PageRank（9） 算法的計(jì)算問題如何計(jì)算10億、100億個網(wǎng)頁？行列數(shù)

11、以億為單位的矩陣相乘！第25頁，共52頁。Google三大法寶之一：MapReduce第26頁，共52頁。矩陣乘法串行實(shí)現(xiàn)1: for i=1;i=N;i+2:for j=1;j=N;j+3:4:5:6:for k=1;k #(5 8 9 8 5)(reduce #+ #(5 8 9 8 5) - 35Lisp中的Map和Reduce操作第31頁，共52頁。MapReduce原理Source：sun.fim.uni-passau.de/cl/MapReduceFoundation/第32頁，共52頁。MapReduce機(jī)制 主控程序（Master）：將Map和Reduce分配到合適的工作機(jī)上

12、工作機(jī)（Worker）：執(zhí)行Map或Reduce任務(wù)第33頁，共52頁。MapReduce不僅僅是編程模型! 讓程序員在使用MapReduce時面對以下細(xì)節(jié)問題？ 大數(shù)據(jù)如何分割為小數(shù)據(jù)塊？ 如何調(diào)度計(jì)算任務(wù)并分配和調(diào)度map和reduce任務(wù)節(jié)點(diǎn)？ 如何在任務(wù)節(jié)點(diǎn)間交換數(shù)據(jù)？ 如何同步任務(wù)？ 相互依賴的任務(wù)是否執(zhí)行完成？ 任務(wù)節(jié)點(diǎn)失效時該如何處理？ Google的MapReduce是一個完整的計(jì)算框架 程序員只需要編寫少量的程序?qū)崿F(xiàn)應(yīng)用層邏輯第34頁，共52頁。程序示例：WordCount#include mapreduce/mapreduce.hclass WordCounter : pu

13、blic Mapper public:virtual void Map(const MapInput& input) const string& text = input.value();const int n = text.size();for (int i = 0; i n; ) while (i n) & isspace(texti) i+;int start = i;while (i n) & !isspace(texti) i+;if (start done() value += StringToInt(input-value();input-NextValue();Emit(Int

14、ToString(value); ;REGISTER_REDUCER(Adder);int main(int argc, char* argv) ParseCommandLineFlags(argc, argv);MapReduceSpecification spec;for (int i = 1; i set_format(text);input-set_filepattern(argvi);input-set_mapper_class(WordCounter);MapReduceOutput* out = spec.output();out-set_filebase(/gfs/test/f

15、req);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);MapReduceResult result;if (!MapReduce(spec, &result) abort();return 0;第35頁，共52頁。Google三大法寶之二：GFS第36頁，共52頁。GFS

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

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

18、oogle的第一臺服務(wù)器（1998）Intel CPU + IDE硬盤集群多節(jié)點(diǎn)數(shù)據(jù)冗余存儲第41頁，共52頁。GFS系統(tǒng)架構(gòu)客戶端（Client）GFS提供給上層應(yīng)用使用的一組接口庫上層應(yīng)用通過調(diào)用接口庫中的接口實(shí)現(xiàn)GFS系統(tǒng)中的文件管理適合自身應(yīng)用的簡單接口主控節(jié)點(diǎn)（Master）管理節(jié)點(diǎn)唯一性保存元數(shù)據(jù)調(diào)配塊服務(wù)器塊服務(wù)器（Chunk Server）存儲數(shù)據(jù)塊（Chunk）多個固定塊大?。J(rèn)64MB）數(shù)據(jù)庫多節(jié)點(diǎn)冗余備份討論：分析一下，GFS的文件讀寫流程大致應(yīng)該是怎么樣的？第42頁，共52頁。計(jì)算索引：客戶端將應(yīng)用提供的文件名和字節(jié)偏移通過固定文件塊大小進(jìn)行計(jì)算后獲得塊索引傳遞索引：

19、客戶端將文件名稱和塊索引發(fā)送給主控節(jié)點(diǎn)返回位置：主控節(jié)點(diǎn)將用于訪問文件塊的塊句柄和文件塊所在的塊服務(wù)器位置返回給客戶端訪問數(shù)據(jù)：客戶端將位置信息進(jìn)行緩存，并訪問離自己距離最近的塊服務(wù)器返回?cái)?shù)據(jù)：被訪問的塊服務(wù)器將數(shù)據(jù)返回給客戶端GFS讀數(shù)據(jù)流程第43頁，共52頁。Google三大法寶之三：BigTable第44頁，共52頁。簡單搜索框背后的復(fù)雜工作1. Crawler從URL服務(wù)器提取地址進(jìn)行遍歷查找2. 獲取文檔docs ,建立文檔docIDs ,進(jìn)行分析、壓縮3. 存儲到文檔數(shù)據(jù)庫4. 索引器為docs建立順排索引和倒排索引5. 索引數(shù)據(jù)存儲到集群中建立索引響應(yīng)請求.5.對請

20、求進(jìn)行預(yù)處理，包括拼寫檢查、附加廣告等GWS向索引服務(wù)器發(fā)送查詢關(guān)鍵字索引服務(wù)器根據(jù)關(guān)鍵字查找匹配文檔并向GWS返回docIDsGWS將docIDs傳給文檔服務(wù)器，獲得文檔GWS將查詢結(jié)果文檔以HTML形式返回給用戶第45頁，共52頁。為什么需要BigTable？ GFS的局限性：文件系統(tǒng)，不適合結(jié)構(gòu)化數(shù)據(jù)的存儲和訪問 結(jié)構(gòu)化數(shù)據(jù)？使用DB2、SQLServer、MySQL之類的數(shù)據(jù)庫系統(tǒng)？ 非也！因?yàn)椋?存儲數(shù)據(jù)的多樣性與復(fù)雜性： URL、網(wǎng)頁內(nèi)容、用戶數(shù)據(jù)等 海量的處理請求 成本與控制力 BigTable的目標(biāo)： 適應(yīng)各種不同類型的數(shù)據(jù)和應(yīng)用 隨時增加和減少處理節(jié)點(diǎn)的可擴(kuò)展性和自動平衡能力

21、 PB級數(shù)據(jù)環(huán)境下的高吞吐量和高并發(fā)（百萬級TPS） 連續(xù)服務(wù)的高可用性和容錯性 架構(gòu)與使用的簡潔性第46頁，共52頁。BigTable數(shù)據(jù)模型 BigTable：是一個經(jīng)過排序后的分布式的、稀疏的、多維映射表 分布式：數(shù)據(jù)是分布式存儲的 稀疏：列數(shù)可能很多，而某一行中可能只有少數(shù)列有數(shù)據(jù) 多維映射表： 數(shù)據(jù)索引由行關(guān)鍵字（Row Key）、列關(guān)鍵字（Column Key）和時間戳（Time Stamp）三個維度構(gòu)成 數(shù)據(jù)以鍵/值映射的形式組織( row:string, column:string, time:int64 ) string第47頁，共52頁。BigTable示例 網(wǎng)站頁面內(nèi)容及

22、其中超鏈接的解析 t3、t5、t6三個時間點(diǎn)抓取的網(wǎng)頁內(nèi)容存儲在contents列中 有兩個網(wǎng)頁包含了到網(wǎng)頁的鏈接，分別是位于頁面的超鏈接文字CNN，和位于my.look.ca頁面的超鏈接文字CNN.com第43第48頁，共52頁。BigTable表的展開行數(shù)行關(guān)鍵字版本列族：contents列族：anchor限定詞：限定詞：my.look.ca12com.bbc.wwwn.www“CNN”“CNN.com”t2t1t7t6t5t4t3a2a1d4c3b2第49頁，共52頁。 面向列的存儲 提高訪問少數(shù)列的效率 整行掃描 vs. 單列讀取 提高壓縮比 雜 vs. 純第50頁，共52頁。BigT

23、able系統(tǒng)架構(gòu)子表（Tablet）過大的數(shù)據(jù)表不利于存儲和訪問效率大表在水平方向上被分為多個子表，每個子表包含表中若干行的數(shù)據(jù)支持?jǐn)?shù)據(jù)表的分布式存儲和表訪問的負(fù)載均衡主控服務(wù)器操作及管理數(shù)據(jù)表元數(shù)據(jù)子表分配與監(jiān)控負(fù)載均衡控制子表服務(wù)器數(shù)據(jù)服務(wù)器的基本單元數(shù)據(jù)以文件形式存儲在GFS文件系統(tǒng)中第51頁，共52頁。1、不是井里沒有水，而是你挖的不夠深。不是成功來得慢，而是你努力的不夠多。2、孤單一人的時間使自己變得優(yōu)秀，給來的人一個驚喜，也給自己一個好的交代。3、命運(yùn)給你一個比別人低的起點(diǎn)是想告訴你，讓你用你的一生去奮斗出一個絕地反擊的故事，所以有什么理由不努力!4、心中沒有過分的貪求，自然苦就少

24、?？诶锊徽f多余的話，自然禍就少。腹內(nèi)的食物能減少，自然病就少。思緒中沒有過分欲，自然憂就少。大悲是無淚的，同樣大悟無言。緣來盡量要惜，緣盡就放。人生本來就空，對人家笑笑，對自己笑笑，笑著看天下，看日出日落，花謝花開，豈不自在，哪里來的塵埃!5、心情就像衣服，臟了就拿去洗洗，曬曬，陽光自然就會蔓延開來。陽光那么好，何必自尋煩惱，過好每一個當(dāng)下，一萬個美麗的未來抵不過一個溫暖的現(xiàn)在。6、無論你正遭遇著什么，你都要從落魄中站起來重振旗鼓，要繼續(xù)保持熱忱，要繼續(xù)保持微笑，就像從未受傷過一樣。7、生命的美麗，永遠(yuǎn)展現(xiàn)在她的進(jìn)取之中;就像大樹的美麗，是展現(xiàn)在它負(fù)勢向上高聳入云的蓬勃生機(jī)中;像雄鷹的美麗，是展現(xiàn)在它搏風(fēng)擊雨如蒼天之魂的翱翔中;像江河的美麗，是展現(xiàn)在它