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

云計(jì)算與

大規(guī)模數(shù)據(jù)并行處理技術(shù)計(jì)算機(jī)科學(xué)與技術(shù)系軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室主要內(nèi)容第一部分：云計(jì)算技術(shù)簡(jiǎn)介簡(jiǎn)要介紹云計(jì)算及其主要特點(diǎn)，云計(jì)算發(fā)展背景與現(xiàn)狀，云計(jì)算的關(guān)鍵技術(shù)第二部分：MapReduce大規(guī)模數(shù)據(jù)并行處理技術(shù)簡(jiǎn)要介紹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ù)研究第一部分

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

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

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

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

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

云計(jì)算發(fā)展背景

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

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

07-現(xiàn)在:云計(jì)算“天下大勢(shì)，合久必分，分久必合”“否定之否定，螺旋式上升”云計(jì)算發(fā)展背景應(yīng)用需求背景大粒度應(yīng)用系統(tǒng)的規(guī)模越來越大應(yīng)用系統(tǒng)數(shù)據(jù)量越來越大中國移動(dòng)全國每天的電話短信通聯(lián)記錄數(shù)據(jù)達(dá)到500TB；而中國移動(dòng)一個(gè)流量最大的省每天的通聯(lián)記錄數(shù)據(jù)可達(dá)到65TB阿里巴巴電子商務(wù)平臺(tái)日處理數(shù)據(jù)量將達(dá)到500TB百度存儲(chǔ)100-1000PB數(shù)據(jù)，每日處理10-100PB；存儲(chǔ)1千-1萬億網(wǎng)頁，索引100-1000億網(wǎng)頁2009年eBays數(shù)據(jù)倉庫，一個(gè)有2PB用戶數(shù)據(jù)，另一個(gè)6.5PB用戶數(shù)據(jù)包含170TB記錄且每天增長150GB個(gè)記錄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部電影

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

AmazonElasticComputingCloud29MicrosoftCloudServices

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

Azure?ServicesPlatformMicrosoftSharePointServicesMicrosoftDynamicsCRMServicesIBM云計(jì)算方案

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

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

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

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

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

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

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

MapReduce

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

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

研究發(fā)現(xiàn)：訓(xùn)練數(shù)據(jù)集越大,數(shù)據(jù)分類精度越高；大數(shù)據(jù)集上的簡(jiǎn)單算法能比小數(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》雜志出版一期專刊專門討論未來的大數(shù)據(jù)（BigData）處理相關(guān)的一系列技術(shù)問題和挑戰(zhàn)。據(jù)預(yù)計(jì)：未來10年，數(shù)據(jù)量將從數(shù)百EB增長到數(shù)百ZB量級(jí)！Google大規(guī)模數(shù)據(jù)并行處理技術(shù)簡(jiǎn)介GoogleMapReduceGoogle在2004年提出的一種通用的大規(guī)模數(shù)據(jù)并行計(jì)算平臺(tái)和編程模型和框架MapReduce發(fā)明后，Google大量用于各種海量數(shù)據(jù)處理，目前Google內(nèi)部有7千以上的程序基于MapReduce實(shí)現(xiàn)，包括其搜索引擎

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

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

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

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

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

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

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

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

reduce:(k2;[v2])

[(k3;v3)]輸入：

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

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

輸入：(text1,“theweatherisgood”)

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

輸入：(text2,“todayisgood”)

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

輸入：(text3,“goodweatherisgood”)

輸出：(good,1),(weather,1),(is,1),(good,1)map節(jié)點(diǎn)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ù)存儲(chǔ)計(jì)算結(jié)果……數(shù)據(jù)劃分Map初始kv鍵值對(duì)初始kv鍵值對(duì)初始kv鍵值對(duì)初始kv鍵值對(duì)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個(gè)Reduce節(jié)點(diǎn):reduce節(jié)點(diǎn)1:

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

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

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

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

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

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

（Scale“out”,not“up”）

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

ofMaryland,Data-IntensiveTextprocessingwithMapReduceMapReduce的主要設(shè)計(jì)思想與特點(diǎn)

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

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

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

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

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

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

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

平滑無縫的可擴(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ī)模上，要求算法的計(jì)算性能應(yīng)能隨著節(jié)點(diǎn)數(shù)的增加保持接近線性程度的增長絕大多數(shù)現(xiàn)有的單機(jī)算法都達(dá)不到以上理想的要求；把中間結(jié)果數(shù)據(jù)維護(hù)在內(nèi)存中的單機(jī)算法在大規(guī)模數(shù)據(jù)處理時(shí)很快失效；從單機(jī)到基于大規(guī)模集群的并行計(jì)算從根本上需要完全不同的算法設(shè)計(jì)奇妙的是，MapReduce幾乎能實(shí)現(xiàn)以上理想的擴(kuò)展性特征。

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

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

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

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

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

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

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

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

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

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

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

Master對(duì)等于GFS

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

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

5.1簡(jiǎn)介1145.2復(fù)合鍵值對(duì)的使用1155.2.1把小的鍵值對(duì)合并成大的鍵值對(duì)1155.2.2巧用復(fù)合鍵讓系統(tǒng)完成排序1175.3用戶定制數(shù)據(jù)類型1235.3.1hadoop內(nèi)置的數(shù)據(jù)類型1235.3.2用戶自定義數(shù)據(jù)類型的實(shí)現(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ù)輸出格式實(shí)現(xiàn)多集合文件輸出1345.5用戶定制partitioner和combiner1375.5.1用戶定制partitioner1375.5.2用戶定制combiner1395.6組合式mapreduce計(jì)算作業(yè)1415.6.1迭代mapreduce計(jì)算任務(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類實(shí)現(xiàn)reduce端連接1505.7.3用全局文件復(fù)制方法實(shí)現(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ù)庫中輸出計(jì)算結(jié)果170第1章神奇的大象—hadoop第2章HDFS—不怕故障的海量存儲(chǔ)第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章綜合實(shí)戰(zhàn)1—打造一個(gè)搜索引擎第12章綜合實(shí)戰(zhàn)2—生物信息學(xué)應(yīng)用第13章綜合實(shí)戰(zhàn)3—移動(dòng)通信信令監(jiān)測(cè)與查詢第14章高枕無憂—Hadoop容錯(cuò)大規(guī)模數(shù)據(jù)并行技術(shù)培訓(xùn)、教學(xué)和平臺(tái)建設(shè)購建高性能MapReduce并行計(jì)算集群

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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