云計算技術(shù)與大規(guī)模數(shù)據(jù)并行處理

云計算與

大規(guī)模數(shù)據(jù)并行處理技術(shù)計算機(jī)科學(xué)與技術(shù)系軟件新技術(shù)國家重點實驗室主要內(nèi)容第一部分：云計算技術(shù)簡介簡要介紹云計算及其主要特點，云計算發(fā)展背景與現(xiàn)狀，云計算的關(guān)鍵技術(shù)第二部分：MapReduce大規(guī)模數(shù)據(jù)并行處理技術(shù)簡要介紹Google和HadoopMapReduce大規(guī)模數(shù)據(jù)并行處理技術(shù)第三部分：大規(guī)模數(shù)據(jù)并行處理技術(shù)研究與應(yīng)用介紹大規(guī)模數(shù)據(jù)并行處理技術(shù)研究，主要討論大規(guī)模數(shù)據(jù)并行算法研究、大規(guī)模數(shù)據(jù)索引查詢技術(shù)、以及Hadoop改進(jìn)和優(yōu)化技術(shù)研究第一部分

云計算技術(shù)云計算技術(shù)簡介什么是云計算？CloudComputing,UtilityComputing,ServiceComputing……通過集中式遠(yuǎn)程計算資源池，以按需分配方式，為終端用戶提供強(qiáng)大而廉價的計算服務(wù)能力工業(yè)化部署、商業(yè)化運作的大規(guī)模計算能力一種新的、可商業(yè)化的計算和服務(wù)模式計算能力像水電煤氣一樣，按需分配使用資源池物理上對用戶透明就像在云端一樣云計算的主要特點透明的云端計算服務(wù)“無限”多的計算資源，強(qiáng)大的計算能力按需分配，彈性伸縮，取用方便，成本低廉資源共享，降低企業(yè)IT基礎(chǔ)設(shè)施建設(shè)維護(hù)費用應(yīng)用部署快速而容易軟件/應(yīng)用功能更新方便快捷節(jié)省能源，綠色環(huán)保集計算技術(shù)之大成，具有很強(qiáng)的技術(shù)性、工程型特點云計算的分類按云計算服務(wù)層面進(jìn)行分類SaaS：SoftwareasaService提供各種應(yīng)用軟件服務(wù)PaaS：PlatformasaService提供軟件支撐平臺服務(wù)IaaS：InfrastructureasaService提供接近于裸機(jī)(物理機(jī)或虛擬機(jī))的計算資源

和基礎(chǔ)設(shè)施服務(wù)云計算硬件平臺云計算的分類云計算軟件支撐平臺云計算應(yīng)用服務(wù)軟件SaaS如騰訊云詞典PaaS如GoogleAppEngIaaS如AmazonEC2云計算應(yīng)用按云計算服務(wù)層面進(jìn)行分類云計算的分類按云計算系統(tǒng)類型進(jìn)行分類美國聯(lián)邦云計算戰(zhàn)略報告中，定義了4中云：公用云：提供面向社會大眾、公共群體的云計算服務(wù)如Amazon云平臺，GoogleAppEng

公有云有很多優(yōu)點，但最大的一個缺點是難以保證數(shù)據(jù)的私密性私有云：提供面向應(yīng)用行業(yè)/組織內(nèi)的云計算服務(wù)如政府機(jī)關(guān)、移動通信、學(xué)校等內(nèi)部使用的云平臺

私有云可較好地解決數(shù)據(jù)私密性問題，對移動通信、公安等數(shù)據(jù)私密性要求特別高的企業(yè)或機(jī)構(gòu)，建設(shè)私有云將是一個必然的選擇云計算的分類按云計算系統(tǒng)類型進(jìn)行分類社區(qū)云：提供面向社團(tuán)組織內(nèi)用戶使用的云計算平臺

如美國航天局(NASA)Nebula云平臺為NASA內(nèi)的研究人員提供快速的IT訪問服務(wù)混合云：包含以上2種以上云計算類型的混合式云平臺云計算發(fā)展背景云計算技術(shù)的爭議反方：云計算是業(yè)界的商業(yè)性行為正方：云計算是計算技術(shù)的重大發(fā)展趨勢個人認(rèn)為：云計算技術(shù)有其發(fā)展的必然性和必要性

云計算發(fā)展背景

集中分散集中60-70’s:大型機(jī)(mainframe),

集中式、終端用戶共享80-90’s:個人計算機(jī),人手一臺95-06:互聯(lián)網(wǎng)/網(wǎng)格/集群

07-現(xiàn)在:云計算“天下大勢，合久必分，分久必合”“否定之否定，螺旋式上升”云計算發(fā)展背景應(yīng)用需求背景大粒度應(yīng)用系統(tǒng)的規(guī)模越來越大應(yīng)用系統(tǒng)數(shù)據(jù)量越來越大中國移動全國每天的電話短信通聯(lián)記錄數(shù)據(jù)達(dá)到500TB；而中國移動一個流量最大的省每天的通聯(lián)記錄數(shù)據(jù)可達(dá)到65TB阿里巴巴電子商務(wù)平臺日處理數(shù)據(jù)量將達(dá)到500TB百度存儲100-1000PB數(shù)據(jù)，每日處理10-100PB；存儲1千-1萬億網(wǎng)頁，索引100-1000億網(wǎng)頁2009年eBays數(shù)據(jù)倉庫，一個有2PB用戶數(shù)據(jù)，另一個6.5PB用戶數(shù)據(jù)包含170TB記錄且每天增長150GB個記錄Facebook：2.5PB用戶數(shù)據(jù)，每天增加15TB僅2011年，全世界產(chǎn)生1.8ZB（1.8萬億GB）數(shù)據(jù)，相當(dāng)于每位美國人每分鐘寫3條Twitter，不停地寫2.7萬年YouTube每分鐘有13h視頻上傳，每天數(shù)據(jù)10TB相當(dāng)于好萊塢每周發(fā)行57000部電影

云計算發(fā)展背景應(yīng)用需求背景大粒度應(yīng)用系統(tǒng)的規(guī)模越來越大超大的計算量和計算復(fù)雜度用SGI工作站進(jìn)行電影渲染時，每幀一般需要1～2小時一部2小時的電影渲染需要：

2小時x3600秒x24幀x(1~2小時)/24小時=20~40年!特殊場景每幀可能需要60個小時(影片“星艦騎兵”中數(shù)千只蜘蛛爬行的場面),用橫向4096象素分辨率進(jìn)行渲染時，如果以每幀60個小時的速度，則1秒的放映量（24幀）需要60天的渲染時間,1分鐘則需要100年！云計算發(fā)展背景應(yīng)用需求背景小粒度應(yīng)用系統(tǒng)資源重復(fù)、無法共享

企業(yè)內(nèi)大量的小粒度應(yīng)用系統(tǒng)需要添置獨立的硬件資源，但忙閑不均，忙時資源不夠，閑時資源空置，資源無法相互調(diào)配和共享，造成資源和資金浪費

淘寶網(wǎng)案例：后臺設(shè)置約15萬臺服務(wù)器，服務(wù)于不同的應(yīng)用系統(tǒng)；而不同應(yīng)用系統(tǒng)的負(fù)載不同，忙閑不均；據(jù)淘寶測算，如能在不同應(yīng)用間合理調(diào)配計算資源，大約可省去2/3約10萬臺服務(wù)器，以每臺3萬元計算，約可節(jié)省30億元！云計算發(fā)展背景技術(shù)發(fā)展背景貫穿整個計算機(jī)技術(shù)發(fā)展歷史的兩條主線：

計算能力角度：不斷追求計算性能提升無論是微處理器還是巨型機(jī)，近20年性能提高3千多倍

使用角度：不斷追求易用性和靈活性可獲得性、易用性、可擴(kuò)展性和靈活性不斷提升Intel微處理器每秒1千8百億次浮點運算！近20年性能提高3千多倍不斷追求計算性能提升巨型機(jī)：中國天河一號，2010年底世界TOP500強(qiáng)第1名

每秒2千5百多萬億次浮點運算，近20年性能提高3千多倍億億千萬億百萬億十萬億萬億千億百億十億億TOP500系統(tǒng)體系結(jié)構(gòu)演化向量機(jī)=>SMP=>MPP=>ClusterCluster以高獲得性、高可擴(kuò)展性優(yōu)勢成為發(fā)展主流

不斷追求方便性和靈活性云計算發(fā)展背景云計算發(fā)展背景技術(shù)發(fā)展背景

雖然新的計算技術(shù)在易用性和靈活性上有不斷提高，但仍然存在很大不足：

計算能力仍取決于硬件計算資源，計算能力不夠時，需要不斷增加硬件資源；空閑時，硬件資源閑置浪費，不能共享；計算能力的獲取和使用上仍然存在較大的制約。云計算正是一種解決這一問題的新的計算服務(wù)模式，其基本思路是集中計算資源提供巨大的計算能力的同時，提供使用上的方便性和靈活性云計算發(fā)展背景技術(shù)發(fā)展背景云計算是諸多計算技術(shù)發(fā)展成熟與自然進(jìn)化的產(chǎn)物計算機(jī)虛擬化技術(shù)、大規(guī)模并行計算、分布式存儲、面向服務(wù)構(gòu)架、公用服務(wù)計算等諸多技術(shù)廣泛應(yīng)用計算機(jī)系統(tǒng)規(guī)模和處理能力迅速擴(kuò)大技術(shù)發(fā)展成熟與自然進(jìn)化的結(jié)果云計算發(fā)展背景“Thecomputationandthedataandsoforthareintheservers.…Wecallitcloudcomputing.”(ErickSchmidt,2006)“computationmaysomedaybeorganizedasapublicutility”(JohnMcCarthy,1960)“云計算”的概念在2006年由Google公司正式提出但最初的思想雛形可追溯到更早的時間云計算發(fā)展背景云計算發(fā)展意義云計算出現(xiàn)的意義，可與20世紀(jì)電力工業(yè)的變革相比20世紀(jì)初電力工業(yè)變革的幾項關(guān)鍵技術(shù)

發(fā)電容量大幅提升

交流電的出現(xiàn)(1888)

電表的發(fā)明和使用(1894)20世紀(jì)初私有電廠向公共電力服務(wù)轉(zhuǎn)化過程1900:美國有5萬多個私有小型電廠，3千6百個中心電站1907:40%并入了公共電力服務(wù)系統(tǒng)

1920:70%并入了公共電力服務(wù)系統(tǒng)

1930:80%~90%并入了公共電力服務(wù)系統(tǒng)

云計算發(fā)展背景云計算發(fā)展意義

云計算的一個重要目標(biāo)是，把計算能力變成像水電等公用服務(wù)一樣，隨用隨取，按需使用。故此也有人把云計算稱為“UtilityComputing”這里Utility不是效用、實用的意思，在英文里Utility有一個專門的含義，專指類似于水電煤氣的公用服務(wù)，故UtilityComputing應(yīng)譯為“公用服務(wù)計算”云計算發(fā)展背景云計算發(fā)展意義

2011年2月8日美國奧巴馬總統(tǒng)簽署了聯(lián)邦云計算戰(zhàn)略報告，制定該報告的目的：TheFederalGovernment’scurrentInformationTechnology(IT)environmentischaracterizedbylowassetutilization,afragmenteddemandforresources,duplicativesystems,environmentswhicharedifficulttomanage,andlongprocurementleadtimes.TheseinefficienciesnegativelyimpacttheFederalGovernment’sabilitytoservetheAmericanpublic.Cloudcomputinghasthepotentialtoplayamajorpartinaddressingtheseinefficienciesandimprovinggovernmentservicedelivery.Thecloudcomputingmodelcansignificantlyhelpagenciesgrapplingwiththeneedtoprovidehighlyreliable,innovativeservicesquicklydespiteresourceconstraints.美國聯(lián)邦政府部門計劃用全部的800億美元IT預(yù)算中的200億作為云計算平臺開發(fā)建設(shè)的費用。美國聯(lián)邦云計算戰(zhàn)略報告，2011/2/8云計算發(fā)展背景云計算發(fā)展意義

美國聯(lián)邦云計算戰(zhàn)略報告認(rèn)為：CloudisafundamentalshiftinITCloudcomputingenablesITsystemstobescalableandelastic.Endusersdonotneedtodeterminetheirexactcomputingresourcerequirementsupfront.Instead,theyprovisioncomputingresourcesasrequired,on-demand.Usingcloudcomputingservices,aFederalagencydoesnotneedtoowndatacenterinfrastructuretolaunchacapabilitythatservesmillionsofusersCloudcomputingcansignificantlyimprovepublicsectorITAnumberofgovernmentagenciesareadoptingcloudtechnologiesandarerealizingconsiderablebenefits.Forinstance,NASANebula,throughacommunitycloud,givesresearchersaccesstoITservicesrelativelyinexpensivelyinminutes.Priortoadoptingthisapproach,itwouldtakeresearchersmonthstoprocureandconfigurecomparableITresourcesandsignificantmanagementoversighttomonitorandupgradesystems.ApplyingcloudtechnologiesacrosstheentireFederalGovernmentcanyieldtremendousbenefitsinefficiency,agility,andinnovation.云計算發(fā)展現(xiàn)狀與趨勢業(yè)界云計算技術(shù)的發(fā)展自2006年Google公司提出云計算技術(shù)的概念后，全球IT著名企業(yè)紛紛予以極大關(guān)注，并投入了巨大力量進(jìn)行云計算技術(shù)的研究開發(fā)。GoogleCloudInfrastructureSchedulerChubbyGFSmasterNodeNodeNode…UserGoogleAppEngineSchedulerslaveGFSLinuxNodeMapReduceFrameworkBigTableServerGoogleCloudInfrastructure

(GoogleAppEngine，PaaS型公用云平臺)GoogleAppEngine提供了一種PaaS類型的云計算服務(wù)平臺，用戶可租用該平臺的計算資源，并使用AppEngine提供的各種應(yīng)用開發(fā)和支撐軟件平臺開發(fā)和部署自己的應(yīng)用軟件S3EBSEC2EBSEC2EBSEC2EBSEC2SimpleDBSQSUserDeveloperAmazonElasticComputingCloud

(AmazonEC2，IaaS型公用云平臺)SQS:SimpleQueueServiceEC2:RunningInstanceofVirtualMachinesEBS:ElasticBlockService,ProvidingtheBlockInterface,StoringVirtualMachineImagesS3:SimpleStorageService,SOAP,ObjectInterfaceSimpleDB:SimplifiedDatabaseAmazonEC2提供了一種IaaS類型的云計算服務(wù)平臺，在該平臺上用戶可部署自己的系統(tǒng)軟件，完成應(yīng)用軟件的開發(fā)和發(fā)布。28租用案例2007年，美國紐約時報租用Amazon云計算平臺，用于將1851-1922年紐約時報的1100萬篇報刊文章轉(zhuǎn)換為PDF文件,供讀者上網(wǎng)免費訪問。共租用了100個EC2節(jié)點，運行了24小時，處理了4TB的報刊原始掃描圖像，生成了1.5TB的PDF文件。每節(jié)點每小時費用為10美分，整個計算任務(wù)僅花費了240美元(100節(jié)點x24小時x$0.10)！如果用自己的服務(wù)器，將需要數(shù)月和多得多的費用！

AmazonElasticComputingCloud29MicrosoftCloudServices

(WindowAzure，私有云平臺管理和服務(wù)軟件)

Azure?ServicesPlatformMicrosoftSharePointServicesMicrosoftDynamicsCRMServicesIBM云計算方案

(私有云計算平臺管理和服務(wù)軟件)提供私有云計算資源管理軟件平臺，主要負(fù)責(zé)管理和調(diào)度虛擬計算資源，完成資源申請、調(diào)度和管理等整個生命周期管理2/3/202331其它國內(nèi)外IT企業(yè)云計算研發(fā)

除以上幾家全球著名的IT企業(yè)外，其它著名IT企業(yè)如Cisco、HP、EMC、VMWare等，都在大力推進(jìn)云計算技術(shù)和系統(tǒng)研發(fā)。國內(nèi)諸多著名IT企業(yè)，如中國移動、中國電信、中國聯(lián)通、阿里巴巴、騰訊、百度、萬網(wǎng)、中興通信、華為等，也大力推動云計算研發(fā)。云計算發(fā)展現(xiàn)狀與趨勢32中國移動BigCloud云計算發(fā)展現(xiàn)狀目標(biāo)是建立可為中國移動企業(yè)內(nèi)部進(jìn)行海量通信數(shù)據(jù)存儲和處理的使用的私有云平臺，以及為社會大眾和群體使用的公有云平臺。大規(guī)模低成本數(shù)據(jù)中心的訂制化硬件設(shè)計分布式文件系統(tǒng)結(jié)構(gòu)化數(shù)據(jù)存儲非結(jié)構(gòu)化數(shù)據(jù)存儲分布式計算資源管理大規(guī)模離線數(shù)據(jù)處理在線服務(wù)綜合監(jiān)控計費系統(tǒng)安全高可靠保障機(jī)制云計算編程模型與訪問接口商品交易平臺軟件服務(wù)平臺數(shù)據(jù)服務(wù)平臺企業(yè)IT服務(wù)統(tǒng)一的資源調(diào)度服務(wù)阿里巴巴電子交易云計算平臺云計算發(fā)展現(xiàn)狀與趨勢云計算發(fā)展趨勢云計算將提供一種新的計算模式和服務(wù)模式。云計算將是計算技術(shù)的一次重大變革，作為今后計算發(fā)展的潮流將大大改變現(xiàn)有的計算模式，對計算技術(shù)領(lǐng)域本身以及各個應(yīng)用行業(yè)都將帶來重大的影響，提供更多的發(fā)展機(jī)遇通過云計算人們能獲得前所未有的強(qiáng)大計算能力，并能按需分配，按需付費，提升了本地計算能力但使用成本低廉，而且還能大幅削減不斷升級軟硬件系統(tǒng)的費用通過云計算平臺強(qiáng)大的計算和存儲能力，人們將能完成傳統(tǒng)系統(tǒng)所無法完成的計算和處理，開發(fā)出更強(qiáng)大的應(yīng)用功能，提供更多智能化應(yīng)用云計算發(fā)展現(xiàn)狀與趨勢云計算發(fā)展趨勢通過各種個人終端使用云端的計算能力，將大大擴(kuò)展現(xiàn)有的移動設(shè)備的計算能力，提供各種新的增值應(yīng)用模式云計算與物聯(lián)網(wǎng)有重要的關(guān)聯(lián)性，作為未來的人機(jī)物計算的重要組成部分，云計算關(guān)注的是服務(wù)器端技術(shù)，物聯(lián)網(wǎng)關(guān)注的客戶和終端技術(shù)云計算發(fā)展現(xiàn)狀與趨勢云計算發(fā)展趨勢面向民生工程的政企應(yīng)用將是云計算的潛在市場，并能帶動產(chǎn)業(yè)整體發(fā)展未來3年，云計算應(yīng)用將以政府、電信、教育、醫(yī)療、金融、石油石化和電力等行業(yè)為重點，在中國市場逐步被越來越多的企業(yè)和機(jī)構(gòu)采用，市場規(guī)模將從2009年的92.23億元增長到2012年的606.78億元，年復(fù)合增長率達(dá)87.4%（來源:賽迪顧問

中國云計算產(chǎn)業(yè)發(fā)展白皮書）云計算的關(guān)鍵技術(shù)主要包括以下關(guān)鍵技術(shù)虛擬化技術(shù)：虛擬機(jī)的安裝、設(shè)置、調(diào)度分配、使用、故障檢測與失效恢復(fù)等云計算構(gòu)架技術(shù)：研究解決適合于云計算的系統(tǒng)軟硬件構(gòu)架資源調(diào)度技術(shù)：解決物理或虛擬計算資源的自動化分配、調(diào)度、配置、使用、負(fù)載均衡、回收等資源管理云計算的關(guān)鍵技術(shù)主要包括以下關(guān)鍵技術(shù)并行計算技術(shù)：針對大規(guī)模數(shù)據(jù)或復(fù)雜計算應(yīng)用，解決數(shù)據(jù)或計算任務(wù)切分和并行計算算法設(shè)計問題海量存儲技術(shù)：解決大規(guī)模數(shù)據(jù)的分布存儲、共享訪問、數(shù)據(jù)備份等問題云安全技術(shù)：解決云計算系統(tǒng)的訪問安全性、數(shù)據(jù)安全性（包括數(shù)據(jù)私密性）等問題此外，還有云計算中心的節(jié)能和散熱等工程技術(shù)問題云計算的關(guān)鍵技術(shù)怎樣才算是云計算？云計算概念很熱，各級政府部門、很多行業(yè)和應(yīng)用都想搞云計算。大家很熱議的問題是：云計算與傳統(tǒng)計算系統(tǒng)有什么區(qū)別？系統(tǒng)做成什么樣才能稱得上是云計算系統(tǒng)？云計算的關(guān)鍵技術(shù)怎樣才算是云計算？回答這兩個問題必須從發(fā)展云計算技術(shù)的兩個根本目的、以及云計算區(qū)別于傳統(tǒng)計算的特點上來看提高計算能力：集中計算資源，為應(yīng)用提供強(qiáng)大而廉價的計算能力 =>大規(guī)模并行計算能力提高易用性和靈活性：合理調(diào)配資源，為應(yīng)用提供彈性資源分配、資源共享

=>資源虛擬化和彈性調(diào)度

云計算的關(guān)鍵技術(shù)怎樣才算是云計算？因此，個人認(rèn)為：一個計算系統(tǒng)必須具備以下兩個特征才能算是云計算系統(tǒng)（至少具備第一個特征）:資源虛擬化和彈性調(diào)度

基于虛擬化和彈性調(diào)度，以按需分配方式，為小粒度應(yīng)用提供計算資源，實現(xiàn)資源共享大規(guī)模并行計算服務(wù)

基于云端的強(qiáng)大而廉價的計算能力，為大粒度應(yīng)用提供傳統(tǒng)計算系統(tǒng)或用戶終端所無法完成的計算服務(wù)。這些計算能力包括海量數(shù)據(jù)存儲能力、以及大規(guī)模并行計算能力。第二部分

MapReduce

大規(guī)模數(shù)據(jù)并行處理技術(shù)大規(guī)模數(shù)據(jù)并行處理技術(shù)的重要性為什么大規(guī)模數(shù)據(jù)并行處理是云計算核心技術(shù)之一？大規(guī)模數(shù)據(jù)處理和行業(yè)應(yīng)用需求日益增加和迫切出現(xiàn)越來越多的超大規(guī)模數(shù)據(jù)處理應(yīng)用需求，傳統(tǒng)系統(tǒng)難以提供足夠的存儲和計算資源進(jìn)行處理，云計算平臺是最理想的解決方案。調(diào)查顯示：目前，IT專業(yè)人員對云計算中諸多關(guān)鍵技術(shù)最為關(guān)心的是大規(guī)模數(shù)據(jù)并行處理技術(shù)大數(shù)據(jù)并行處理沒有通用和現(xiàn)成的解決方案對于應(yīng)用行業(yè)來說，云計算平臺軟件、虛擬化軟件都不需要自己開發(fā)，但行業(yè)的大規(guī)模數(shù)據(jù)處理應(yīng)用軟件沒有通用的軟件，需要針對特定的應(yīng)用需求專門開發(fā)，涉及到諸多并行化算法、索引查詢優(yōu)化技術(shù)研究、以及系統(tǒng)的設(shè)計實現(xiàn)大規(guī)模數(shù)據(jù)并行處理技術(shù)的重要性為什么大規(guī)模數(shù)據(jù)并行處理是云計算核心技術(shù)之一？處理數(shù)據(jù)的能力大幅落后于數(shù)據(jù)增長速度

磁盤容量增長遠(yuǎn)遠(yuǎn)快過存儲訪問帶寬和延遲：80年代中期數(shù)十MB到今天1-2TB，增長10萬倍，而延遲僅提高2倍，帶寬僅提高50倍！海量數(shù)據(jù)隱含著更準(zhǔn)確的事實

研究發(fā)現(xiàn)：訓(xùn)練數(shù)據(jù)集越大,數(shù)據(jù)分類精度越高；大數(shù)據(jù)集上的簡單算法能比小數(shù)據(jù)集上的復(fù)雜算法產(chǎn)生更好的結(jié)果大規(guī)模數(shù)據(jù)并行處理技術(shù)的重要性大數(shù)據(jù)(BigData)應(yīng)用需求

出現(xiàn)越來越多的大數(shù)據(jù)應(yīng)用和行業(yè)需求。2008年，在Google成立10周年之際，《Nature》雜志出版一期?？瘜ｉT討論未來的大數(shù)據(jù)（BigData）處理相關(guān)的一系列技術(shù)問題和挑戰(zhàn)。據(jù)預(yù)計：未來10年，數(shù)據(jù)量將從數(shù)百EB增長到數(shù)百ZB量級！Google大規(guī)模數(shù)據(jù)并行處理技術(shù)簡介GoogleMapReduceGoogle在2004年提出的一種通用的大規(guī)模數(shù)據(jù)并行計算平臺和編程模型和框架MapReduce發(fā)明后，Google大量用于各種海量數(shù)據(jù)處理，目前Google內(nèi)部有7千以上的程序基于MapReduce實現(xiàn)，包括其搜索引擎

的全部索引處理什么是MapReduce？MapReduce三個層面的含義基于集群的高性能并行計算平臺(ClusterInfrastructure)

允許用市場上的普通服務(wù)器，構(gòu)成一個包含數(shù)百到數(shù)千個節(jié)點的分布式并行計算集群并行程序開發(fā)與運行框架(SoftwareFramework)提供了一個龐大但設(shè)計精良的并行計算軟件構(gòu)架，能自動完成計算任務(wù)的并行化處理，自動劃分計算數(shù)據(jù)和計算任務(wù)，在集群節(jié)點上自動分配和執(zhí)行子任務(wù)以及收集計算結(jié)果，將數(shù)據(jù)分布存儲、數(shù)據(jù)通信、容錯處理等并行計算中的很多復(fù)雜細(xì)節(jié)交由系統(tǒng)負(fù)責(zé)處理，大大減少了軟件開發(fā)人員的負(fù)擔(dān)并行程序設(shè)計模型與方法(ProgrammingModel&Methodology)

借助于函數(shù)式語言中的設(shè)計思想，提供了一種簡便的并行程序設(shè)計方法，用Map和Reduce兩個函數(shù)編程實現(xiàn)基本的并行計算任務(wù)，提供了完整的并行編程接口，完成大規(guī)模數(shù)據(jù)處理典型的流式大數(shù)據(jù)處理問題的特征大量數(shù)據(jù)記錄/元素進(jìn)行重復(fù)處理對每個數(shù)據(jù)記錄/元素作感興趣的處理、獲取感興趣的中間結(jié)果信息排序和整理中間結(jié)果以利后續(xù)處理收集整理中間結(jié)果產(chǎn)生最終結(jié)果輸出MapReduce關(guān)鍵思想：借助于Lisp函數(shù)式程序設(shè)計思想，為大數(shù)據(jù)處理過程中的兩個主要處理操作提供一種抽象機(jī)制MapReduce的基本設(shè)計思想MapReduce的基本設(shè)計思想MapReduce三個層面上的基本設(shè)計思想如何對付大數(shù)據(jù)處理：分而治之

對相互間不具有計算依賴關(guān)系的大數(shù)據(jù)，實現(xiàn)并行最自然的辦法就是采取分而治之的策略上升到抽象模型：Mapper與Reducer

MapReduce借鑒了Lisp函數(shù)式語言中的思想，用Map和Reduce兩個函數(shù)提供了高層的并行編程抽象模型，程序員只需描述需要“做什么”

(whattodo),不需要關(guān)心具體“怎么做”（How

todo)上升到統(tǒng)一構(gòu)架：為程序員隱藏系統(tǒng)層細(xì)節(jié)對于具體的“怎么做”的問題，MapReduce提供了一個統(tǒng)一的計算框架，為程序員隱藏了數(shù)據(jù)存儲訪問、數(shù)據(jù)塊劃分、計算節(jié)點調(diào)度管理、數(shù)據(jù)通信、結(jié)果收集、容錯處理、負(fù)載均衡、性能優(yōu)化等諸多低層細(xì)節(jié)，交由系統(tǒng)負(fù)責(zé)處理，因而大大減輕了程序員進(jìn)行并行編程時的負(fù)擔(dān)MapReduce的基本設(shè)計思想大數(shù)據(jù)任務(wù)劃分和并行計算模型大數(shù)據(jù)計算任務(wù)子任務(wù)子任務(wù)子任務(wù)子任務(wù)……任務(wù)劃分計算結(jié)果結(jié)果合并Map和Reduce操作的抽象描述

MapReduce借鑒了函數(shù)式程序設(shè)計語言Lisp中的思想，定義了如下的Map和Reduce兩個抽象的編程接口，由用戶去編程實現(xiàn):map:(k1;v1)[(k2;v2)]輸入：鍵值對(k1;v1)表示的數(shù)據(jù)處理：文檔數(shù)據(jù)記錄(如文本文件中的行，或數(shù)據(jù)表格中的行)將以“鍵值對”形式傳入map函數(shù)；map函數(shù)將處理這些鍵值對，并以另一種鍵值對形式輸出處理的一組鍵值對中間結(jié)果[(k2;v2)]輸出：鍵值對[(k2;v2)]表示的一組中間數(shù)據(jù)MapReduce的基本設(shè)計思想MapReduce的基本設(shè)計思想Map和Reduce操作的抽象描述

reduce:(k2;[v2])

[(k3;v3)]輸入：

由map輸出的一組鍵值對[(k2;v2)]將被進(jìn)行合并處理將同樣主鍵下的不同數(shù)值合并到一個列表[v2]中，故reduce的輸入為(k2;[v2])處理：對傳入的中間結(jié)果列表數(shù)據(jù)進(jìn)行某種整理或進(jìn)一步的處理,并產(chǎn)生最終的某種形式的結(jié)果輸出[(k3;v3)]。輸出：最終輸出結(jié)果[(k3;v3)]MapReduce的基本設(shè)計思想基于Map和Reduce的并行計算模型

海量數(shù)據(jù)存儲……數(shù)據(jù)劃分MapMapMapMap初始kv鍵值對初始kv鍵值對初始kv鍵值對初始kv鍵值對中間結(jié)果(k1,val)(k2,val)(k3,val)(k1,val)(k3,val)(k2,val)(k3,val)(k1,val)(k2,val)(k3,val)Barrier：AggregationandShuffleReduceReduceReduce(k1,values)(k2,values)(k3,values)計算結(jié)果(K1,val)(K2,val)(K3,val)MapReduce的基本設(shè)計思想基于Map和Reduce的并行計算模型各個map函數(shù)對所劃分的數(shù)據(jù)并行處理，從不同的輸入數(shù)據(jù)產(chǎn)生不同的中間結(jié)果輸出各個reduce也各自并行計算，各自負(fù)責(zé)處理不同的中間結(jié)果數(shù)據(jù)集合進(jìn)行reduce處理之前,必須等到所有的map函數(shù)做完，因此,在進(jìn)入reduce前需要有一個同步障(barrier);這個階段也負(fù)責(zé)對map的中間結(jié)果數(shù)據(jù)進(jìn)行收集整理(aggregation&shuffle)處理,以便reduce更有效地計算最終結(jié)果最終匯總所有reduce的輸出結(jié)果即可獲得最終結(jié)果MapReduce并行處理示例文檔詞頻統(tǒng)計WordCount設(shè)有4組原始文本數(shù)據(jù)：Text1:theweatherisgoodText2:todayisgoodText3:goodweatherisgoodText4:today

hasgoodweather傳統(tǒng)的串行處理方式(Java)：

String[]text=newString[]{“helloworld”,“helloeveryone”,“sayhellotoeveryoneintheworld”｝;HashTableht=newHashTable();for(i=0;i<3;++i){StringTokenizerst=newStringTokenizer(text[i]);while(st.hasMoreTokens()){Stringword=st.nextToken();if(!ht.containsKey(word)){ht.put(word,newInteger(1));}else{intwc=((Integer)ht.get(word)).intValue()+1;//計數(shù)加1ht.put(word,newInteger(wc));}}}for(Iteratoritr=ht.KeySet().iterator();itr.hasNext();){Stringword=(String)itr.next();System.out.print(word+“:”+(Integer)ht.get(word)+“;”);}輸出：good:5;has:1;is:3;the:1;today:2;weather:3MapReduce并行處理示例文檔詞頻統(tǒng)計WordCountMap處理示例設(shè)使用4個map節(jié)點：map節(jié)點1:

輸入：(text1,“theweatherisgood”)

輸出：(the,1),(weather,1),(is,1),(good,1)map節(jié)點2:

輸入：(text2,“todayisgood”)

輸出：(today,1),(is,1),(good,1)map節(jié)點3:

輸入：(text3,“goodweatherisgood”)

輸出：(good,1),(weather,1),(is,1),(good,1)map節(jié)點4:

輸入：(text3,“todayhasgoodweather”)

輸出：(today,1),(has,1),(good,1),(weather,1)Barrier(good,1)(good,1)(good,2)(good,1)PartitionerPartitionerPartitionerPartitioner(is,1)(is,1)(is,1)(has,1)(weather,1)(weather,1)(weather,1)(the,1)(today,1)(today,1)海量數(shù)據(jù)存儲計算結(jié)果……數(shù)據(jù)劃分Map初始kv鍵值對初始kv鍵值對初始kv鍵值對初始kv鍵值對MapMapMap中間結(jié)果(the,1)(weather,1)(is,1)(good,1)CombinerCombinerCombinerCombiner(the,1)(weather,1)(is,1)(good,1)(today,1)(is,1)(good,1)(good,1)(weather,1)(is,1)(good,1)(today,1)(has,1)(good,1)(weather,1)(today,1)(is,1)(good,1)(good,2)(weather,1)(is,1)(today,1)(has,1)(good,1)(weather,1)ReduceReduceReduce(good,5)(is,3)(has,1)(weather,3)(the,1)(today,2)完整的MapReduce并行處理模型和過程MapReduce并行處理示例MapReduce并行處理示例文檔詞頻統(tǒng)WordCountReduce處理示例設(shè)使用3個Reduce節(jié)點:reduce節(jié)點1:

輸入：(good,1),(good,1),(good,2),(good,1)

輸出：(good,5)reduce節(jié)點2:

輸入：(has,1),(is,1),(is,1),(is,1),

輸出：(has,1),(is,3)reduce節(jié)點3:

輸入：(the,1),(today,1),(today,1)(weather,1),(weather,1),(weather,1)

輸出：(the,1),(today,2),(weather,3)輸出：good:5is:3has:1the:1today:2weather:3MapReduce并行處理示例文檔詞頻統(tǒng)WordCountMapReduce程序?qū)崿F(xiàn)MapReduce偽代碼(實現(xiàn)Map和Reduce兩個函數(shù))：ClassMappermethodmap(Stringinput_key,Stringinput_value):

//input_key:textdocumentname//input_value:documentcontents

foreachwordwininput_value:

EmitIntermediate(w,"1");ClassReducermethodreduce(Stringoutput_key,

Iteratorintermediate_values):

//output_key:aword//output_values:alistofcounts

intresult=0;

foreachvinintermediate_values:result+=ParseInt(v);

Emit(output_key，result);提供統(tǒng)一的計算框架主要需求和目標(biāo)：實現(xiàn)自動并行化計算為程序員隱藏系統(tǒng)層細(xì)節(jié)需要考慮的細(xì)節(jié)技術(shù)問題：如何管理和存儲數(shù)據(jù)？如何劃分?jǐn)?shù)據(jù)？如何調(diào)度計算任務(wù)并分配map和reduce節(jié)點？如果節(jié)點間需要共享或交換數(shù)據(jù)怎么辦？如何考慮數(shù)據(jù)通信和同步？如何掌控節(jié)點的執(zhí)行完成情況？如何收集中間和最終的結(jié)果數(shù)據(jù)？節(jié)點失效如何處理？如何恢復(fù)數(shù)據(jù)？如何恢復(fù)計算任務(wù)？節(jié)點擴(kuò)充后如何保證原有程序仍能正常運行并保證系統(tǒng)性能提升？問題：我們能把這些細(xì)節(jié)和復(fù)雜性都交給系統(tǒng)去負(fù)責(zé)處理嗎？提供統(tǒng)一的計算框架答案：MapReduce之前的并行計算方法都未能做到

但MapReduce做到了！MapReduce提供一個統(tǒng)一的計算框架，可完成：計算任務(wù)的劃分和調(diào)度數(shù)據(jù)的分布存儲和劃分處理數(shù)據(jù)與計算任務(wù)的同步結(jié)果數(shù)據(jù)的收集整理(sorting,combining,partitioning,…)系統(tǒng)通信、負(fù)載平衡、計算性能優(yōu)化處理計算和存儲節(jié)點出錯檢測和失效恢復(fù)MapReduce的主要設(shè)計思想與特點

向“外”橫向擴(kuò)展，而非向“上”縱向擴(kuò)展

（Scale“out”,not“up”）

即MapReduce集群的構(gòu)筑選用價格便宜、易于擴(kuò)展的大量低端商用服務(wù)器，而非價格昂貴、不易擴(kuò)展的高端服務(wù)器（SMP）低端服務(wù)器市場與高容量DesktopPC有重疊的市場，因此，由于相互間價格的競爭、可互換的部件、和規(guī)模經(jīng)濟(jì)效應(yīng)，使得低端服務(wù)器保持較低的價格基于TPC-C在2007年底的性能評估結(jié)果,一個低端服務(wù)器平臺與高端的共享存儲器結(jié)構(gòu)的服務(wù)器平臺相比,其性價比大約要高4倍;如果把外存價格除外,低端服務(wù)器性價比大約提高12倍對于大規(guī)模數(shù)據(jù)處理，由于有大量數(shù)據(jù)存儲需要，顯而易見，基于低端服務(wù)器的集群遠(yuǎn)比基于高端服務(wù)器的集群優(yōu)越，這就是為什么MapReduce并行計算集群會基于低端服務(wù)器實現(xiàn)*CitefromJimmyLin,University

ofMaryland,Data-IntensiveTextprocessingwithMapReduceMapReduce的主要設(shè)計思想與特點

失效被認(rèn)為是常態(tài)（Assumefailuresarecommon）MapReduce集群中使用大量的低端服務(wù)器(Google目前在全球共使用百萬臺以上的服務(wù)器節(jié)點),因此，節(jié)點硬件失效和軟件出錯是常態(tài)，因而：一個良好設(shè)計、具有容錯性的并行計算系統(tǒng)不能因為節(jié)點失效而影響計算服務(wù)的質(zhì)量，任何節(jié)點失效都不應(yīng)當(dāng)導(dǎo)致結(jié)果的不一致或不確定性；任何一個節(jié)點失效時，其它節(jié)點要能夠無縫接管失效節(jié)點的計算任務(wù)；當(dāng)失效節(jié)點恢復(fù)后應(yīng)能自動無縫加入集群，而不需要管理員人工進(jìn)行系統(tǒng)配置MapReduce并行計算軟件框架使用了多種有效的機(jī)制，如節(jié)點自動重啟技術(shù)，使集群和計算框架具有對付節(jié)點失效的健壯性，能有效處理失效節(jié)點的檢測和恢復(fù)。

把計算向數(shù)據(jù)遷移 Movingprocessingtothedata傳統(tǒng)高性能計算系統(tǒng)通常有很多處理器節(jié)點與一些外存儲器節(jié)點相連，如用區(qū)域存儲網(wǎng)絡(luò)(SAN,StorageAreaNetwork)連接的磁盤陣列，因此，大規(guī)模數(shù)據(jù)處理時外存文件數(shù)據(jù)I/O訪問會成為一個制約系統(tǒng)性能的瓶頸。為了減少大規(guī)模數(shù)據(jù)并行計算系統(tǒng)中的數(shù)據(jù)通信開銷，代之以把數(shù)據(jù)傳送到處理節(jié)點(數(shù)據(jù)向處理器或代碼遷移)，應(yīng)當(dāng)考慮將處理向數(shù)據(jù)靠攏和遷移。MapReduce采用了數(shù)據(jù)/代碼互定位的技術(shù)方法，計算節(jié)點將首先將盡量負(fù)責(zé)計算其本地存儲的數(shù)據(jù),以發(fā)揮數(shù)據(jù)本地化特點(locality),僅當(dāng)節(jié)點無法處理本地數(shù)據(jù)時，再采用就近原則尋找其它可用計算節(jié)點，并把數(shù)據(jù)傳送到該可用計算節(jié)點。MapReduce的主要設(shè)計思想與特點

順序處理數(shù)據(jù)、避免隨機(jī)訪問數(shù)據(jù) Processdatasequentiallyandavoidrandomaccess大規(guī)模數(shù)據(jù)處理的特點決定了大量的數(shù)據(jù)記錄不可能存放在內(nèi)存、而只可能放在外存中進(jìn)行處理。磁盤的順序訪問和隨即訪問在性能上有巨大的差異

例：100億(1010)個數(shù)據(jù)記錄(每記錄100B,共計1TB)的數(shù)據(jù)庫

更新1%的記錄(一定是隨機(jī)訪問)需要1個月時間；

而順序訪問并重寫所有數(shù)據(jù)記錄僅需1天時間！MapReduce設(shè)計為面向大數(shù)據(jù)集批處理的并行計算系統(tǒng)，所有計算都被組織成很長的流式操作，以便能利用分布在集群中大量節(jié)點上磁盤集合的高傳輸帶寬。MapReduce的主要設(shè)計思想與特點

為應(yīng)用開發(fā)者隱藏系統(tǒng)層細(xì)節(jié) Hidesystem-leveldetailsfromtheapplicationdeveloper軟件工程實踐指南中，專業(yè)程序員認(rèn)為之所以寫程序困難，是因為程序員需要記住太多的編程細(xì)節(jié)(從變量名到復(fù)雜算法的邊界情況處理)，這對大腦記憶是一個巨大的認(rèn)知負(fù)擔(dān),需要高度集中注意力而并行程序編寫有更多困難，如需要考慮多線程中諸如同步等復(fù)雜繁瑣的細(xì)節(jié)，由于并發(fā)執(zhí)行中的不可預(yù)測性，程序的調(diào)試查錯也十分困難；大規(guī)模數(shù)據(jù)處理時程序員需要考慮諸如數(shù)據(jù)分布存儲管理、數(shù)據(jù)分發(fā)、數(shù)據(jù)通信和同步、計算結(jié)果收集等諸多細(xì)節(jié)問題MapReduce提供了一種抽象機(jī)制將程序員與系統(tǒng)層細(xì)節(jié)隔離開來，程序員僅需描述需要計算什么(whattocompute),而具體怎么去做(howtocompute)就交由系統(tǒng)的執(zhí)行框架處理，這樣程序員可從系統(tǒng)層細(xì)節(jié)中解放出來，而致力于其應(yīng)用本身計算問題的算法設(shè)計MapReduce的主要設(shè)計思想與特點

平滑無縫的可擴(kuò)展性 Seamlessscalability主要包括兩層意義上的擴(kuò)展性：數(shù)據(jù)擴(kuò)展和系統(tǒng)規(guī)模擴(kuò)展理想的軟件算法應(yīng)當(dāng)能隨著數(shù)據(jù)規(guī)模的擴(kuò)大而表現(xiàn)出持續(xù)的有效性，性能上的下降程度應(yīng)與數(shù)據(jù)規(guī)模擴(kuò)大的倍數(shù)相當(dāng)在集群規(guī)模上，要求算法的計算性能應(yīng)能隨著節(jié)點數(shù)的增加保持接近線性程度的增長絕大多數(shù)現(xiàn)有的單機(jī)算法都達(dá)不到以上理想的要求；把中間結(jié)果數(shù)據(jù)維護(hù)在內(nèi)存中的單機(jī)算法在大規(guī)模數(shù)據(jù)處理時很快失效；從單機(jī)到基于大規(guī)模集群的并行計算從根本上需要完全不同的算法設(shè)計奇妙的是，MapReduce幾乎能實現(xiàn)以上理想的擴(kuò)展性特征。

多項研究發(fā)現(xiàn)基于MapReduce的計算性能可隨節(jié)點數(shù)目增長保持近似于線性的增長MapReduce的主要設(shè)計思想與特點并行數(shù)據(jù)處理MapReduceGoogle分布式文件系統(tǒng)GFS(GoogleFileSystem)結(jié)構(gòu)化數(shù)據(jù)表BigTable分布式鎖管理ChubbyMapReduceBigTableGFSChubbyGoogleMapReduce框架和關(guān)鍵技術(shù)用市場上的普通服務(wù)器，構(gòu)建了非?？煽康拇笠?guī)模并行計算集群！

GoogleMapReduce的基本工作原理CitefromDeanandGhemawat(OSDI2004)1.有一個待處理的大數(shù)據(jù)，被劃分為大小相同的數(shù)據(jù)塊(如64MB),及與此相應(yīng)的用戶作業(yè)程序2.系統(tǒng)中有一個負(fù)責(zé)調(diào)度的主節(jié)點(Master),以及數(shù)據(jù)Map和Reduce工作節(jié)點(Worker)3.主節(jié)點為作業(yè)程序?qū)ふ液团鋫淇捎玫腗ap節(jié)點，并將程序和數(shù)據(jù)傳送給map節(jié)點4.主節(jié)點也為作業(yè)程序?qū)ふ液团鋫淇捎玫腞educe節(jié)點，并將程序傳送給Reduce節(jié)點5.主節(jié)點啟動每個Map節(jié)點執(zhí)行程序，每個map節(jié)點盡可能讀取本地或本機(jī)架的數(shù)據(jù)進(jìn)行計算6.每個Map節(jié)點處理讀取的數(shù)據(jù)塊,并做一些數(shù)據(jù)整理工作(combining,sorting等)并將中間結(jié)果存放在本地；同時通知主節(jié)點計算任務(wù)完成并告知中間結(jié)果數(shù)據(jù)存儲位置7.主節(jié)點等所有Map節(jié)點計算完成后,開始啟動Reduce節(jié)點運行；Reduce節(jié)點從主節(jié)點掌握的中間結(jié)果數(shù)據(jù)位置信息讀取這些數(shù)據(jù)8.Reduce節(jié)點計算結(jié)果匯總輸出到一個結(jié)果文件即獲得整個處理結(jié)果70GoogleMapReduce的基本工作原理失效檢測和恢復(fù)處理主節(jié)點失效主節(jié)點中會周期性地設(shè)置檢查點(checkpoint)，檢查整個計算作業(yè)的執(zhí)行情況，一旦某個任務(wù)失效，可以從最近有效的檢查點開始重新執(zhí)行，避免從頭開始計算的時間浪費。工作節(jié)點失效工作節(jié)點失效是很普遍發(fā)生的，主節(jié)點會周期性地給工作節(jié)點發(fā)送檢測命令，如果工作節(jié)點沒有回應(yīng)，這認(rèn)為該工作節(jié)點失效，主節(jié)點將終止該工作節(jié)點的任務(wù)并把失效的任務(wù)重新調(diào)度到其它工作節(jié)點上重新執(zhí)行

GoogleMapReduce的基本工作原理帶寬優(yōu)化問題

大量的鍵值對數(shù)據(jù)在傳送給Reduce節(jié)點時會引起較大的通信帶寬開銷。解決方案每個Map節(jié)點處理完成的中間鍵值隊將由Combiner做一個合并壓縮，即把那些鍵名相同的鍵值對歸并為一個鍵名下的一組數(shù)值。(good,1)(weather,1)(is,1)(good,1)(good,2)(weather,1)(is,1)combiner

GoogleMapReduce的基本工作原理計算優(yōu)化問題Reduce節(jié)點必須要等到所有Map節(jié)點計算計算才能開始執(zhí)行，因此，如果有一個計算量大、或者由于某個問題導(dǎo)致很慢結(jié)束的Map節(jié)點，則會成為嚴(yán)重的“拖后腿者”。解決方案把一個Map計算任務(wù)讓多個Map節(jié)點同時做，取最快完成者的計算結(jié)果。根據(jù)Google的測試，使用了這個冗余Map節(jié)點計算方法以后，計算任務(wù)性能提高40%多！

GoogleMapReduce的基本工作原理用數(shù)據(jù)分區(qū)解決數(shù)據(jù)相關(guān)性問題問題

一個Reduce節(jié)點上的計算數(shù)據(jù)可能會來自多個Map節(jié)點，因此，為了在進(jìn)入Reduce節(jié)點計算之前，需要把屬于一個Reduce節(jié)點的數(shù)據(jù)歸并到一起。解決方案在Map階段進(jìn)行了Combine以后，可以根據(jù)一定的策略對Map輸出的中間結(jié)果進(jìn)行分區(qū)(partition)，這樣即可解決以上數(shù)據(jù)相關(guān)性問題避免Reduce計算過程中的數(shù)據(jù)通信。例如：有一個巨大的數(shù)組,其最終結(jié)果需要排序,每個Map節(jié)點數(shù)據(jù)處理好后,為了避免在每個Reduce節(jié)點本地排序完成后還需要進(jìn)行全局排序,我們可以使用一個分區(qū)策略如:(d%R),d為數(shù)據(jù)大小，R為Reduce節(jié)點的個數(shù)，則可根據(jù)數(shù)據(jù)的大小將其劃分到指定數(shù)據(jù)范圍的Reduce節(jié)點上,每個Reduce將本地數(shù)據(jù)拍好序后即為最終結(jié)果GoogleGFS的基本構(gòu)架GoogleGFS是一個基于分布式集群的大型分布式文件系統(tǒng)，為MapReduce計算框架提供低層數(shù)據(jù)存儲和數(shù)據(jù)可靠性支撐；GFS是一個構(gòu)建在分布節(jié)點本地文件系統(tǒng)之上的一個邏輯上文件系統(tǒng)，它將數(shù)據(jù)存儲在物理上分布的每個節(jié)點上，但通過GFS將整個數(shù)據(jù)形成一個邏輯上整體的文件。分布式文件系統(tǒng)GFS工作原理……GoogleGFSGoogleMapReduceMapReduceApplicationsGoogleGFS的基本構(gòu)架廉價本地磁盤分布存儲

各節(jié)點本地分布式存儲數(shù)據(jù)，優(yōu)點是不需要采用價格較貴的集中式磁盤陣列，容量可隨節(jié)點數(shù)增加自動增加多數(shù)據(jù)自動備份解決可靠性

采用廉價的普通磁盤，把磁盤數(shù)據(jù)出錯視為常態(tài)，用自動多數(shù)據(jù)備份存儲解決數(shù)據(jù)存儲可靠性問題為上層的MapReduce計算框架提供支撐GFS作為向上層MapReduce執(zhí)行框架的底層數(shù)據(jù)存儲支撐，負(fù)責(zé)處理所有的數(shù)據(jù)自動存儲和容錯處理，因而上層框架不需要考慮低層的數(shù)據(jù)存儲和數(shù)據(jù)容錯問題分布式文件系統(tǒng)GFS工作原理GoogleGFS的基本構(gòu)架和工作原理

分布式文件系統(tǒng)GFS工作原理CitefromGhemawatetal.(SOSP2003)GFSMasterGFSMaster：保存GFS文件系統(tǒng)的三種元數(shù)據(jù)：命名空間(NameSpace),即整個分布式文件系統(tǒng)的目錄結(jié)構(gòu)

Chunk與文件名的映射表Chunk副本的位置信息，每一個Chunk默認(rèn)有3個副本GFSChunkServer：用來保存大量實際數(shù)據(jù)的數(shù)據(jù)服務(wù)器；每個數(shù)據(jù)塊缺省劃分為64MB在Google發(fā)表了文章后，DougCutting，2004年，開源項目Lucene(搜索索引程序庫)和Nutch(搜索引擎)的創(chuàng)始人，發(fā)現(xiàn)MapReduce正是其所需要的解決大規(guī)模分布數(shù)據(jù)處理的重要技術(shù)，因而模仿GoogleMapReduce，基于Java設(shè)計出了稱為Hadoop的開源MapReduce，該項目成為Apache下最重要項目Hadoop目前最新版本是0.23.0,11/11/2010Yahoo是Hadoop聯(lián)盟中最大的支持者，目前大量使用了Hadoop集群Yahoo!Hadoop集群(引自Yahoo）開源的HadoopMapReducedatanodedaemonLinuxfilesystem…tasktrackerslavenodedatanodedaemonLinuxfilesystem…tasktrackerslavenodedatanodedaemonLinuxfilesystem…tasktrackerslavenodenamenodenamenodedaemonjobsubmissionnodejobtrackerHadoopMapReduce的基本工作原理數(shù)據(jù)存儲與計算節(jié)點構(gòu)架HadoopMapReduce的基本工作原理對等于GoogleMapReduce中的Master對等于GoogleMapReduce中的WorkerHadoopMapReduce程序執(zhí)行過程HadoopMapReduce程序執(zhí)行過程HadoopMapReduce的基本工作原理HDFS基本構(gòu)架對等于GFS

Master對等于GFS

ChunkServer應(yīng)用程序HDFS客戶端文件名或數(shù)據(jù)塊號數(shù)據(jù)塊號，數(shù)據(jù)塊位置HDFSNameNodeDataNode數(shù)據(jù)DataNode數(shù)據(jù)DataNode數(shù)據(jù)Hadoop的分布式文件系統(tǒng)HDFSGoogle技術(shù)培訓(xùn)2009年12月Google在清華大學(xué)舉辦的MapReduce技術(shù)培訓(xùn)班大規(guī)模數(shù)據(jù)并行技術(shù)培訓(xùn)、教學(xué)和平臺建設(shè)課程建設(shè)2009年參加了Google公司MapReduce技術(shù)培訓(xùn)班，后與Google公司簽約在Google資助下開設(shè)了“MapReduce大規(guī)模數(shù)據(jù)并行處理”課程，是目前為止江蘇省唯一開設(shè)該課程的教師和院系大規(guī)模數(shù)據(jù)并行技術(shù)培訓(xùn)、教學(xué)和平臺建設(shè)教材出版2011年7月合著編寫《實戰(zhàn)Hadoop》，有關(guān)Hadoop技術(shù)第一本具有原著性質(zhì)的書籍，456頁，9月電子工業(yè)出版出版發(fā)行。大規(guī)模數(shù)據(jù)并行技術(shù)培訓(xùn)、教學(xué)和平臺建設(shè)

《實戰(zhàn)Hadoop》大規(guī)模數(shù)據(jù)并行技術(shù)培訓(xùn)、教學(xué)和平臺建設(shè)

5.1簡介1145.2復(fù)合鍵值對的使用1155.2.1把小的鍵值對合并成大的鍵值對1155.2.2巧用復(fù)合鍵讓系統(tǒng)完成排序1175.3用戶定制數(shù)據(jù)類型1235.3.1hadoop內(nèi)置的數(shù)據(jù)類型1235.3.2用戶自定義數(shù)據(jù)類型的實現(xiàn)1245.4用戶定制輸入/輸出格式1265.4.1hadoop內(nèi)置的數(shù)據(jù)輸入格式和recordreader1265.4.2用戶定制數(shù)據(jù)輸入格式與recordreader1275.4.3hadoop內(nèi)置的數(shù)據(jù)輸出格式與recordwriter1335.4.4用戶定制數(shù)據(jù)輸出格式與recordwriter1345.4.5通過定制數(shù)據(jù)輸出格式實現(xiàn)多集合文件輸出1345.5用戶定制partitioner和combiner1375.5.1用戶定制partitioner1375.5.2用戶定制combiner1395.6組合式mapreduce計算作業(yè)1415.6.1迭代mapreduce計算任務(wù)1415.6.2順序組合式mapreduce作業(yè)的執(zhí)行1425.6.3具有復(fù)雜依賴關(guān)系的組合式mapreduce作業(yè)的執(zhí)行1445.6.4mapreduce前處理和后處理步驟的鏈?zhǔn)綀?zhí)行1455.7多數(shù)據(jù)源的連接1485.7.1基本問題數(shù)據(jù)示例1495.7.2用datajoin類實現(xiàn)reduce端連接1505.7.3用全局文件復(fù)制方法實現(xiàn)map端連接1585.7.4帶map端過濾的reduce端連接1625.7.5多數(shù)據(jù)源連接解決方法的限制1625.8全局參數(shù)/數(shù)據(jù)文件的傳遞與使用1635.8.1全局作業(yè)參數(shù)的傳遞1635.8.2查詢?nèi)謒apreduce作業(yè)屬性1665.8.3全局?jǐn)?shù)據(jù)文件的傳遞1675.9關(guān)系數(shù)據(jù)庫的連接與訪問1695.9.1從數(shù)據(jù)庫中輸入數(shù)據(jù)1695.9.2向數(shù)據(jù)庫中輸出計算結(jié)果170第1章神奇的大象—hadoop第2章HDFS—不怕故障的海量存儲第3章分久必合—MapReduce第4章一張無限大的表—HBase第5章更上一層樓—MapReduce進(jìn)階第6章Hive—飛進(jìn)數(shù)據(jù)倉庫的小蜜蜂第7章Pig—一頭什么都能吃的豬第8章Facebook的女神—cassandra第9章Chukwa—收集數(shù)據(jù)的大烏龜?shù)?0章一統(tǒng)天下—Zookeeper第11章綜合實戰(zhàn)1—打造一個搜索引擎第12章綜合實戰(zhàn)2—生物信息學(xué)應(yīng)用第13章綜合實戰(zhàn)3—移動通信信令監(jiān)測與查詢第14章高枕無憂—Hadoop容錯大規(guī)模數(shù)據(jù)并行技術(shù)培訓(xùn)、教學(xué)和平臺建設(shè)購建高性能MapReduce并行計算集群

2011年1月和10月共斥資100萬建成南京大學(xué)第一臺專用于科研的高性能MapReduce并行計算集群81臺DELL高性能機(jī)架式服務(wù)器構(gòu)成其中80臺服務(wù)器每臺包含：2路4核IntelXeon5620,2.4GHz24GB內(nèi)存4TB硬盤整個集群總計：332個處理器核1000GB內(nèi)存162TB硬盤存儲量千兆以太網(wǎng)交換機(jī),背板帶寬184Gbps第三部分

大規(guī)模數(shù)據(jù)并行處理技術(shù)

研究與應(yīng)用大規(guī)模數(shù)據(jù)處理的主要研究問題

數(shù)據(jù)存儲+數(shù)據(jù)傳輸+數(shù)據(jù)處理

具體可包括以下主要技術(shù)問題：海量數(shù)據(jù)存儲管理技術(shù)海量數(shù)據(jù)壓縮與傳輸技術(shù)大規(guī)模數(shù)據(jù)并行算法海量數(shù)據(jù)索引和查詢技術(shù)Hadoop系統(tǒng)改進(jìn)與優(yōu)化研究大規(guī)模數(shù)據(jù)并行處理應(yīng)用

以下主要討論后3項內(nèi)容大規(guī)模數(shù)據(jù)處理的主要研究內(nèi)容大規(guī)模數(shù)據(jù)并行算法基本算法各種全局?jǐn)?shù)據(jù)相關(guān)性小、能適當(dāng)劃分?jǐn)?shù)據(jù)的計算任務(wù)，如：分布式排序分布式GREP(文本匹配查找)關(guān)系代數(shù)操作

如：選擇，投影，求交集、并集，連接，成組，聚合…矩陣向量相乘、矩陣相乘詞頻統(tǒng)計(wordcount)，詞頻重要性分析(TF-IDF)單詞同現(xiàn)關(guān)系分析

典型的應(yīng)用如從生物醫(yī)學(xué)文獻(xiàn)中自動挖掘基因交互作用關(guān)系文檔倒排索引……大規(guī)模數(shù)據(jù)并行算法復(fù)雜算法或應(yīng)用Web搜索引擎

網(wǎng)頁爬取、倒排索引、網(wǎng)頁排序、搜索算法Web訪問日志分析

分析和挖掘用戶在Web上的訪問、購物行為特征、以定制個性化用戶界面或投放用戶感興趣的產(chǎn)品廣告數(shù)據(jù)/文本統(tǒng)計分析

如科技文獻(xiàn)引用關(guān)系分析和統(tǒng)計、專利文獻(xiàn)引用分析和統(tǒng)計圖算法

并行化寬度優(yōu)先搜索(最短路徑問題，可克服Dijkstra串行算法的不足)，最小生成樹，子樹搜索、比對Web鏈接圖分析算法PageRank，垃圾郵件連接分析91大規(guī)模數(shù)據(jù)并行算法復(fù)雜算法或應(yīng)用聚類(clustering)

文檔聚類、圖聚類、其它數(shù)據(jù)集聚類相似性比較分析算法

字符序列、文檔、圖、數(shù)據(jù)集相似性比較分析基于統(tǒng)計的文本處理

最大期望(EM)統(tǒng)計模型，隱馬可夫模型(HMM)，……機(jī)器學(xué)習(xí)

監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)、分類算法（決策樹、SVM…)數(shù)據(jù)挖掘統(tǒng)計機(jī)器翻譯生物信息處理

DNA序列分析比對算法Blast：雙序列比對、多序列比對生物網(wǎng)絡(luò)功能模塊(Motif)查找和比對廣告推送與推薦系統(tǒng)……92

大規(guī)模數(shù)據(jù)并行算法Stanford大學(xué)研究小組研究了基于多核構(gòu)架、自行設(shè)計的輕量級MapReduce框架的各種機(jī)器學(xué)習(xí)算法,發(fā)現(xiàn)計算性能可隨處理器核數(shù)增長保持近似于線性的增長Cheng-TaoChuet.al,MapReduceforMachineLearningonMulticore,2006機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘算法93中國移動通信數(shù)據(jù)挖掘ChinaMobilelookstodatawarehousingandminingofthisdatatoextractinsightsforimprovingmarketingoperations,networkoptimization,andserviceoptimization.SometypicalapplicationsincludeAnalyzinguserbehaviorPredictingcustomerchurnAnalyzingserviceassociationAnalyzingnetworkqualityofservice(QOS)AnalyzingsignalingdataFiltering原來使用由著名供應(yīng)商提供的專用的商業(yè)數(shù)據(jù)挖掘系統(tǒng)，但該系統(tǒng)的單服務(wù)器構(gòu)架嚴(yán)重限制了大數(shù)據(jù)量挖掘處理。一個分支機(jī)構(gòu)使用了8核、32GB內(nèi)存、一個磁盤陣列的Unix服務(wù)器，但僅能處理1.4百萬個用戶的行為數(shù)據(jù)，或者僅僅本分支機(jī)構(gòu)10%的用戶數(shù)據(jù),而且處理時間很長大規(guī)模數(shù)據(jù)并行算法中國移動通信數(shù)據(jù)挖掘

然后他們基于Hadoop重新做了一個數(shù)據(jù)挖掘系統(tǒng)Datanode/TaskTracker—單路4核Xeon2.5GHzCPU,8GBRAM,4x250GBSATAdisksNamenode/JobTracker—雙路2核AMDOpteron2.6GHzCPU,16GBRAM,4x146GBSAS價格比較1/5的價格10倍數(shù)據(jù)時的速度比較一個數(shù)量級的性能提升大規(guī)模數(shù)據(jù)并行算法大規(guī)模數(shù)據(jù)并行算法海量數(shù)據(jù)挖掘算法研究發(fā)現(xiàn)：大數(shù)據(jù)隱含著更準(zhǔn)確的事實

信息檢索、自然語言理解和機(jī)器學(xué)習(xí)的三個要素：

數(shù)據(jù)，特征，與算法

2001,BankoandBrill發(fā)表了一篇自然語言領(lǐng)域的經(jīng)典研究論文，探討訓(xùn)練數(shù)據(jù)集大小對分類精度的影響，發(fā)現(xiàn)數(shù)據(jù)越大，精度越高；更有趣的發(fā)現(xiàn)是，他們發(fā)現(xiàn)當(dāng)數(shù)據(jù)不斷增長時，不同算法的分類精度趨向于相同，使得小數(shù)據(jù)集時不同算法在精度上的差別基本消失！

結(jié)論引起爭論：算法不再要緊，數(shù)據(jù)更重要！不再需要研究復(fù)雜算法，找更多數(shù)據(jù)就行了！大規(guī)模數(shù)據(jù)并行算法海量數(shù)據(jù)隱含著更準(zhǔn)確的事實2001年,一個基于事實的簡短問答研究,如提問:WhoshotAbrahamLincoln？在很大的數(shù)據(jù)集時,只要使用簡單的模式匹配方法,找到在“shotAbrahamLincoln”前面的部分即可快速得到準(zhǔn)確答案：JohnWilkesBooth2007,Brantsetal.描述了一個基于2萬億個單詞訓(xùn)練數(shù)據(jù)集的語言模型，比較了當(dāng)時最先進(jìn)的Kneser-Neysmoothing算法與他們稱之為“stupidbackoff“(簡單退避)的簡單算法,最后發(fā)現(xiàn),后者在小數(shù)據(jù)集時效果不佳，但在大數(shù)據(jù)集時，該算法最終居然產(chǎn)生了更好的語言模型！

結(jié)論：大數(shù)據(jù)集上的簡單算法能比小數(shù)據(jù)集上的復(fù)雜算法產(chǎn)生更好的結(jié)果！

大規(guī)模數(shù)據(jù)并行算法中科院計算所智能信息重點實驗室何清教授進(jìn)行了基于MapReduce的K-Means聚類、分類、和關(guān)聯(lián)規(guī)則挖掘等海量數(shù)據(jù)挖掘并行算法、以及常用的數(shù)據(jù)統(tǒng)計分析算法的研究；并基于這些算法開發(fā)了一個并行分布式數(shù)據(jù)挖掘工具平臺PDMiner，其中大規(guī)模數(shù)據(jù)存儲在HDFS上，且通過MapReduce實現(xiàn)各種并行數(shù)據(jù)預(yù)處理和數(shù)據(jù)挖掘算法。ParallelK-meansclusteringbasedonMapReduce

Zhao,Weizhong(KeyLaboratoryofIntelligentInformationProcessing,InstituteofComputingTechnology,ChineseAcademyofSciences,China);Ma,Huifang;He,Qing

Source:

LectureNotesinComputerScience(includingsubseriesLectureNotesinArtificialIntelligenceandLectureNotesinBioinformatics),v5931LNCS,p674-679,2009,CloudComputing-FirstInternationalConference,CloudCom2009,ProceedingsParallelimplementationofclassificationalgorithmsbasedonmapreduce

He,Qing(KeyLaboratoryofIntelligentInformationProcessing,InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190,China);Zhuang,Fuzhen;Li,Jincheng;Shi,Zh