google云計算三大核心技術

1、Google三大核心技術之一三大核心技術之一:MapReduceMapReduce:超大機群上的簡單數(shù)據(jù)處理超大機群上的簡單數(shù)據(jù)處理摘要摘要MapReduce是一個編程模型和處理產生大數(shù)據(jù)集的相關實現(xiàn).用戶指定一個map函數(shù)處理一個keyvalue對從而產生中間的keyvalue對集.然后再指定一個reduce函數(shù)合并所有的具有相同中間key的中間value.下面將列舉許多可以用這個模型來表示的現(xiàn)實世界的工作.以這種方式寫的程序能自動的

2、在大規(guī)模的普通機器上實現(xiàn)并行化.這個運行時系統(tǒng)關心這些細節(jié):分割輸入數(shù)據(jù)在機群上的調度機器的錯誤處理管理機器之間必要的通信.這樣就可以讓那些沒有并行分布式處理系統(tǒng)經驗的程序員利用大量分布式系統(tǒng)的資源.我們的MapReduce實現(xiàn)運行在規(guī)?？梢造`活調整的由普通機器組成的機群上一個典型的MapReduce計算處理幾千臺機器上的以TB計算的數(shù)據(jù).程序員發(fā)現(xiàn)這個系統(tǒng)非常好用:已經實現(xiàn)了數(shù)以百計的MapReduce程序每天在Google的機群上都

3、有1000多個MapReduce程序在執(zhí)行.1.介紹介紹在過去的5年里作者和Google的許多人已經實現(xiàn)了數(shù)以百計的為專門目的而寫的計算來處理大量的原始數(shù)據(jù)比如爬行的文檔Web請求日志等等.為了計算各種類型的派生數(shù)據(jù)比如倒排索引Web文檔的圖結構的各種表示每個主機上爬行的頁面數(shù)量的概要每天被請求數(shù)量最多的集合等等.很多這樣的計算在概念上很容易理解.然而輸入的數(shù)據(jù)量很大并且只有計算被分布在成百上千的機器上才能在可以接受的時間內完成.怎樣并

4、行計算分發(fā)數(shù)據(jù)處理錯誤所有這些問題綜合在一起使得原本很簡介的計算因為要大量的復雜代碼來處理這些問題而變得讓人難以處理.作為對這個復雜性的回應我們設計一個新的抽象模型它讓我們表示我們將要執(zhí)行的簡單計算而隱藏并行化容錯數(shù)據(jù)分布負載均衡的那些雜亂的細節(jié)在一個庫里.我們的抽象模型的靈感來自Lisp和許多其他函數(shù)語言的map和reduce的原始表示.我們認識到我們的許多計算都包含這樣的操作:在我們輸入數(shù)據(jù)的邏輯記錄上應用map操作來計算出一個中間

5、keyvalue對集在所有具有相同key的value上應用reduce操作來適當?shù)暮喜⑴缮臄?shù)據(jù).功能模型的使用再結合用戶指定的map和reduce操作讓我們可以非常容易的實現(xiàn)大規(guī)模并行化計算和使用再次執(zhí)行作為初級機制來實現(xiàn)容錯.這個工作的主要貢獻是通過簡單有力的接口來實現(xiàn)自動的并行化和大規(guī)模分布式計算結合這個接口的實現(xiàn)來在大量普通的PC機上實現(xiàn)高性能計算.第二部分描述基本的編程模型并且給一些例子.第三部分描述符合我們的基于集群的計算環(huán)

6、境的MapReduce的接口的實現(xiàn).第四部分描述我們覺得編程模型中一些有用的技巧.第五部分對于各種不同的任務測量我們實現(xiàn)的性能.第六部分探究在Google內部使用MapReduce作為基礎來重寫我們的索引系統(tǒng)產品.第七部分討論相關的和未來的工作.2.編程模型編程模型計算利用一個輸入keyvalue對集來產生一個輸出keyvalue對集.MapReduce庫的用戶用兩個函數(shù)表達這這里有一些讓人感興趣的簡單程序可以容易的用MapReduce

7、計算來表示.分布式的分布式的Grep(UNIX工具程序可做文件內的字符串查找):如果輸入行匹配給定的樣式map函數(shù)就輸出這一行.reduce函數(shù)就是把中間數(shù)據(jù)復制到輸出.計算計算URL訪問頻率訪問頻率:map函數(shù)處理web頁面請求的記錄輸出(URL1).reduce函數(shù)把相同URL的value都加起來產生一個(URL記錄總數(shù))的對.倒轉網絡鏈接圖倒轉網絡鏈接圖:map函數(shù)為每個鏈接輸出(目標源)對一個URL叫做目標包含這個URL的頁面叫

8、做源.reduce函數(shù)根據(jù)給定的相關目標URLs連接所有的源URLs形成一個列表產生(目標源列表)對.每個主機的術語向量每個主機的術語向量:一個術語向量用一個(詞頻率)列表來概述出現(xiàn)在一個文檔或一個文檔集中的最重要的一些詞.map函數(shù)為每一個輸入文檔產生一個(主機名術語向量)對(主機名來自文檔的URL).reduce函數(shù)接收給定主機的所有文檔的術語向量.它把這些術語向量加在一起丟棄低頻的術語然后產生一個最終的(主機名術語向量)對.倒排索

9、引倒排索引:map函數(shù)分析每個文檔然后產生一個(詞文檔號)對的序列.reduce函數(shù)接受一個給定詞的所有對排序相應的文檔IDs并且產生一個(詞文檔ID列表)對.所有的輸出對集形成一個簡單的倒排索引.它可以簡單的增加跟蹤詞位置的計算.分布式排序分布式排序:map函數(shù)從每個記錄提取key并且產生一個(keyrecd)對.reduce函數(shù)不改變任何的對.這個計算依賴分割工具(在4.1描述)和排序屬性(在4.2描述).3實現(xiàn)實現(xiàn)MapReduc

10、e接口可能有許多不同的實現(xiàn).根據(jù)環(huán)境進行正確的選擇.例如一個實現(xiàn)對一個共享內存較小的機器是合適的另外的適合一個大NUMA的多處理器的機器而有的適合一個更大的網絡機器的集合.這部分描述一個在Google廣泛使用的計算環(huán)境的實現(xiàn):用交換機連接的普通PC機的大機群.我們的環(huán)境是:1.Linux操作系統(tǒng)雙處理器24GB內存的機器.2.普通的網絡硬件每個機器的帶寬或者是百兆或者千兆但是平均小于全部帶寬的一半.3.因為一個機群包含成百上千的機器所有

11、機器會經常出現(xiàn)問題.4.存儲用直接連到每個機器上的廉價IDE硬盤.一個從內部文件系統(tǒng)發(fā)展起來的分布式文件系統(tǒng)被用來管理存儲在這些磁盤上的數(shù)據(jù).文件系統(tǒng)用復制的方式在不可靠的硬件上來保證可靠性和有效性.5.用戶提交工作給調度系統(tǒng).每個工作包含一個任務集每個工作被調度者映射到機群中一個可用的機器集上.3.1執(zhí)行預覽執(zhí)行預覽通過自動分割輸入數(shù)據(jù)成一個有M個split的集map調用被分布到多臺機器上.輸入的split能夠在不同的機器上被并行處理

12、.通過用分割函數(shù)分割中間key來形成R個片(例如hash(key)modR)reduce調用被分布到多臺機器上.分割數(shù)量(R)和分割函數(shù)由用戶來指定.圖1顯示了我們實現(xiàn)的MapReduce操作的全部流程.當用戶的程序調用MapReduce的函數(shù)的時候將發(fā)生下面的一系列動作(下面的數(shù)字和圖1中的數(shù)字標簽相對應):1.在用戶程序里的MapReduce庫首先分割輸入文件成M個片每個片的大小一般從16到64MB(用戶可以通過可選的參數(shù)來控制).