google云計(jì)算三大核心技術(shù)

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

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

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

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

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

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

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

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

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

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

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

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