云計(jì)算在計(jì)算機(jī)群中的應(yīng)用

云計(jì)算在計(jì)算機(jī)群中的應(yīng)用

云計(jì)算的出現(xiàn)是計(jì)算技術(shù)、軟件工程和網(wǎng)絡(luò)技術(shù)發(fā)展的必然結(jié)果。云計(jì)算在商業(yè)和科研領(lǐng)域的應(yīng)用價(jià)值得到了包括IBM、Google等公司的重視,其未來將像工業(yè)革命一樣引領(lǐng)著社會(huì)的發(fā)展。目前,云計(jì)算的研究與應(yīng)用尚處于初級(jí)階段,云計(jì)算實(shí)現(xiàn)商業(yè)價(jià)值指日可待,云計(jì)算的特點(diǎn)是使數(shù)據(jù)存儲(chǔ)及應(yīng)用商業(yè)化,Web數(shù)據(jù)挖掘是一個(gè)應(yīng)用價(jià)值大理論性很強(qiáng)的研究領(lǐng)域,本文基于云計(jì)算框架下對(duì)Web數(shù)據(jù)挖掘算法進(jìn)行了討論和研究。1云計(jì)算的內(nèi)涵及其特點(diǎn)到目前為止,學(xué)者們對(duì)云計(jì)算的定義多種多樣,定義主要包括如下幾種。1)維基百科對(duì)云計(jì)算如此定義:云計(jì)算是以服務(wù)方式提供給用戶IT相關(guān)的能力,而用戶不需要了解提供服務(wù)的技術(shù)、相關(guān)知識(shí)以及設(shè)備操作能力,用戶通過Internet接受請(qǐng)求的服務(wù)。2)中國云計(jì)算網(wǎng)的云計(jì)算定義是:云計(jì)算是分布式計(jì)算、并行計(jì)算和網(wǎng)格計(jì)算的發(fā)展,也可定義為分布式計(jì)算、并行計(jì)算和網(wǎng)格計(jì)算這些科學(xué)概念的商業(yè)實(shí)現(xiàn)。3)文獻(xiàn)在概括了多個(gè)云計(jì)算的定義后,將云計(jì)算定義如下:云計(jì)算是一個(gè)具有大量可用的虛擬資源(例如開發(fā)平臺(tái)、硬件以及I/O服務(wù))的資源池。根據(jù)不同的負(fù)載這些虛擬資源可以動(dòng)態(tài)地重新配置,從而以提高資源利用率。云計(jì)算技術(shù)具有以下特點(diǎn):1)云計(jì)算系統(tǒng)的服務(wù)性。云計(jì)算服務(wù)的實(shí)現(xiàn)機(jī)制一般對(duì)用戶透明,用戶要獲得需要的服務(wù),是不需要了解云計(jì)算的具體機(jī)制的,即服務(wù)對(duì)用戶透明。2)云計(jì)算采用冗余方式提高可靠性。云計(jì)算系統(tǒng)提供數(shù)據(jù)處理服務(wù)給用戶,大量商用計(jì)算機(jī)集群組成云計(jì)算系統(tǒng)。如果PC數(shù)量不斷地增加,系統(tǒng)出現(xiàn)錯(cuò)誤甚至崩潰的概率就會(huì)會(huì)不斷增大。在沒有專用的可靠性硬件支持的情況下,采用軟件的方式保證數(shù)據(jù)的可靠性,就必須使用數(shù)據(jù)冗余和分布式存儲(chǔ)方式。3)可用性高。自動(dòng)檢測(cè)技術(shù)是云計(jì)算系統(tǒng)的一大特點(diǎn),可以檢測(cè)失效節(jié)點(diǎn),也可以排除失效節(jié)點(diǎn),系統(tǒng)的正常運(yùn)行并不受此影響。云計(jì)算系統(tǒng)服務(wù)質(zhì)量的提高,主要是通過集成海量存儲(chǔ)和高性能的計(jì)算能力來實(shí)現(xiàn)的。4)高層次的編程模型。通過簡(jiǎn)單學(xué)習(xí)后,用戶就可以編寫自己的云計(jì)算程序,在“云”系統(tǒng)上執(zhí)行,使用戶的需求得到滿足?，F(xiàn)在云計(jì)算系統(tǒng)主要采用Map-Reduce模型。5)經(jīng)濟(jì)性。高性能的超級(jí)計(jì)算機(jī)的價(jià)格是很昂貴的,而組建一個(gè)和超級(jí)計(jì)算機(jī)性能相同大量商業(yè)機(jī)集群所需要的花銷要比超級(jí)計(jì)算機(jī)少得多。6)服務(wù)多樣性。云系統(tǒng)能夠提供給用戶各式各樣的服務(wù),只要支付很少的費(fèi)用,用戶就可以獲得不同的服務(wù)。2存儲(chǔ)及編程技術(shù)特點(diǎn)云計(jì)算是一種數(shù)據(jù)密集型的,以數(shù)據(jù)為中心的超級(jí)計(jì)算。在數(shù)據(jù)存儲(chǔ)、數(shù)據(jù)管理、編程模式等多方面具有自身獨(dú)特的技術(shù)特點(diǎn)。本章介紹云計(jì)算主要的技術(shù),包括數(shù)據(jù)存儲(chǔ)技術(shù),虛擬化技術(shù),數(shù)據(jù)管理技術(shù),編程模式等。2.1云計(jì)算數(shù)據(jù)存儲(chǔ)系統(tǒng)云計(jì)算存儲(chǔ)數(shù)據(jù)是采用分布式存儲(chǔ)方式實(shí)現(xiàn)的,這就可以保證高可靠性、高可用性和經(jīng)濟(jì)性,數(shù)據(jù)存儲(chǔ)的高可靠性是采用冗余存儲(chǔ)的方式來保證的,用可靠的軟件來彌補(bǔ)硬件的不足,從而提供廉價(jià)可靠的海量分布式存儲(chǔ)服務(wù)和計(jì)算服務(wù)。另外,數(shù)據(jù)存儲(chǔ)技術(shù)必須具有高吞吐率和高傳輸率的特點(diǎn),這樣云計(jì)算系統(tǒng)就可同時(shí)滿足大量用戶的需求,才能為大量用戶并行地提供服務(wù)。云計(jì)算的數(shù)據(jù)存儲(chǔ)系統(tǒng)最著名的是谷歌研發(fā)的非開源系統(tǒng)GFS(GoogleFileSystem)和Hadoop開發(fā)團(tuán)隊(duì)開發(fā)的開源系統(tǒng)HDFS(HadoopDistributedFileSystem)。以GFS為例。GFS是可擴(kuò)展的分布式文件系統(tǒng),能夠管理大型分布式數(shù)據(jù)密集型計(jì)算。GFS向用戶提供大量的高性能服務(wù),系統(tǒng)是使用廉價(jià)的商用硬件搭建起來的?？蛻舳藶楸苊獯罅孔x操作使Master成為系統(tǒng)瓶頸,所以不通過Master讀取數(shù)據(jù)?？蛻舳酥苯雍蛪K服務(wù)器交互進(jìn)行讀操作。如圖1。即客戶端獲取Master的寫授權(quán)之后,數(shù)據(jù)向所有的數(shù)據(jù)副本傳輸,在所有的數(shù)據(jù)副本收到修改的數(shù)據(jù)后,便發(fā)出寫請(qǐng)求控制信號(hào)。在所有的數(shù)據(jù)副本更新完數(shù)據(jù)后,客戶端從主副本發(fā)出寫操作完成控制信號(hào)。2.2紅字?jǐn)?shù)據(jù)管理模塊云計(jì)算系統(tǒng)經(jīng)常處理、分析大數(shù)據(jù)集并提供用戶高效的服務(wù)。所以,云計(jì)算數(shù)據(jù)管理技術(shù)必須能夠高效地管理大數(shù)據(jù)集。另一個(gè)云計(jì)算數(shù)據(jù)管理技術(shù)所必須解決的問題是如何在規(guī)模巨大的數(shù)據(jù)集中找到特定的數(shù)據(jù)。云計(jì)算數(shù)據(jù)管理技術(shù)中最著名的當(dāng)屬BigTable數(shù)據(jù)管理技術(shù),在文獻(xiàn)提出的。以BigTable為例。BigTable數(shù)據(jù)管理技術(shù)設(shè)計(jì)者Google給出了如下定義:“BigTable是一種分布式存儲(chǔ)系統(tǒng),能夠管理結(jié)構(gòu)化數(shù)據(jù),可擴(kuò)展成大規(guī)模數(shù)據(jù),例如在數(shù)已萬計(jì)的服務(wù)器上達(dá)到PB(Petabytes)規(guī)模的數(shù)據(jù)?！盉igTable技術(shù)優(yōu)化了數(shù)據(jù)讀操作,采用列存儲(chǔ)的方式,提高了數(shù)據(jù)讀取效率。BigTab1e數(shù)據(jù)的存儲(chǔ)管理結(jié)構(gòu)為:<row:string,column:string,time:int64>->string。BigTable的基本元素由行,列,記錄板和時(shí)間戳組成。其中,記錄板是行的集合體。以行關(guān)鍵字的字典順序?qū)igTable的數(shù)據(jù)項(xiàng)進(jìn)行排列,將每行劃分到記錄板中。時(shí)間戳是一個(gè)64位的整數(shù),表示數(shù)據(jù)的不同版本。每個(gè)節(jié)點(diǎn)管理大約100個(gè)記錄板。列族是若干列的集合,BigTable中的存取權(quán)限控制在列族的粒度進(jìn)行。2.3云計(jì)算和應(yīng)用環(huán)境主要考慮了現(xiàn)在,當(dāng)整個(gè)IT界正處于逐漸步入云計(jì)算時(shí)代的過程中,單個(gè)虛擬化技術(shù)雖然都為企業(yè)在IT方面帶來了利益,但是人們更看重的是基于所面對(duì)的各自不同的獨(dú)特環(huán)境發(fā)展出一個(gè)適合自己的全面的虛擬化戰(zhàn)略。我們需要考慮的是將所有可用的虛擬化技術(shù)作為一個(gè)整體來考慮和組合,以使從中生產(chǎn)的效益最大化。也就是說在云計(jì)算環(huán)境下,所有虛擬化解決方案都是集服務(wù)器、存儲(chǔ)系統(tǒng)、網(wǎng)絡(luò)設(shè)備、軟件及服務(wù)于一體的系統(tǒng)整合方案。虛擬化打開了云計(jì)算的大門,而云計(jì)算帶給大家的從本質(zhì)上講正是虛擬化服務(wù)。從虛擬化到云計(jì)算的計(jì)算,我們實(shí)現(xiàn)了跨系統(tǒng)的資源動(dòng)態(tài)調(diào)度,將大量的計(jì)算資源組成IT資源池,用于動(dòng)態(tài)創(chuàng)建虛擬化的資源供給用戶使用,從而最終實(shí)現(xiàn)應(yīng)用、數(shù)據(jù)和IT資源以服務(wù)的方式通過網(wǎng)絡(luò)提供給用戶,并以前所未見的高速和富有彈性地方式完成任務(wù)。2.4map創(chuàng)造算法設(shè)計(jì)云計(jì)算的編程模型必須保證后臺(tái)復(fù)雜的并行執(zhí)行和任務(wù)調(diào)度向用戶和編程人員透明,才能有效地利用云計(jì)算資源,使用戶能更輕松的享受云計(jì)算帶來的服務(wù)。云計(jì)算采用MapReduce編程模式,任務(wù)被自動(dòng)分成多個(gè)子任務(wù),通過Map和Reduce兩步實(shí)現(xiàn)任務(wù)在大規(guī)模計(jì)算節(jié)點(diǎn)中的調(diào)度與分配。MapReduce是由Google公司發(fā)明,近些年新興的并行編程系統(tǒng)。它將并行化、容錯(cuò)、數(shù)據(jù)分布、負(fù)載均衡等放在一個(gè)庫里,而將系統(tǒng)對(duì)數(shù)據(jù)的所有操作都?xì)w結(jié)兩個(gè)步驟:Map階段和Reduce階段。程序員向MapReduce提交的所有操作處理作業(yè)程序中只需要定義Map函數(shù)和Reduce函數(shù),MapReduce系統(tǒng)即可根據(jù)輸入數(shù)據(jù)的大小以及作業(yè)的配置等信息,自動(dòng)將該作業(yè)初始化為多個(gè)相同的Map任務(wù)和Reduce任務(wù)、分別讀取不同的輸入數(shù)據(jù)塊并調(diào)用Map函數(shù)和Reduce函數(shù)進(jìn)行處理。MapReduce系統(tǒng)主要由三個(gè)模塊組成,客戶端(Client)用于將用戶撰寫的并行處理作業(yè)提交至Master節(jié)點(diǎn);主節(jié)點(diǎn)(Master)自動(dòng)將用戶作業(yè)分解為Map任務(wù)和Reduce任務(wù),并將任務(wù)調(diào)度到工作節(jié)點(diǎn)(Work-er);工作節(jié)點(diǎn)(Worker)用于向master請(qǐng)求執(zhí)行任務(wù),同時(shí)多個(gè)Worker節(jié)點(diǎn)組成的分布式文件系統(tǒng)用于存儲(chǔ)MapReduce的輸入/輸出數(shù)據(jù)。MapReduce主要應(yīng)用于海量數(shù)據(jù)處理,其任務(wù)策略的一大特色既是優(yōu)先將任務(wù)調(diào)度至數(shù)據(jù)所在的節(jié)點(diǎn)。這種基于數(shù)據(jù)位置的調(diào)度方案,使得當(dāng)請(qǐng)求任務(wù)的Worker節(jié)點(diǎn)保存有任務(wù)處理的數(shù)據(jù)時(shí),Map任務(wù)可以在本地讀取并處理數(shù)據(jù),從而降低了網(wǎng)絡(luò)的開銷,提高了系統(tǒng)性能。MapReduce的工作模式,map負(fù)責(zé)分解任務(wù),reduce負(fù)責(zé)將分解的任務(wù)進(jìn)行合并。MapReduce的工作流如圖2所示。3web數(shù)據(jù)3.1web數(shù)據(jù)挖掘Web數(shù)據(jù)挖掘涉及Web、數(shù)據(jù)挖掘、計(jì)算機(jī)語言學(xué)、信息學(xué)等領(lǐng)域,是數(shù)據(jù)挖掘技術(shù)與Web結(jié)合的產(chǎn)物,是一項(xiàng)綜合技術(shù)。Web數(shù)據(jù)挖掘是指從大量Web文檔結(jié)構(gòu)和使用的集合C中發(fā)現(xiàn)隱含的模式p。如果將C看作輸入,將p看作輸出,那么Web挖掘的過程就是從輸入到輸出的一個(gè)映射,ξ:C→p3.2web數(shù)據(jù)挖掘Web數(shù)據(jù)挖掘就是利用數(shù)據(jù)挖掘技術(shù)從網(wǎng)絡(luò)文檔和服務(wù)中發(fā)現(xiàn)和提取信息,Web上各種形式的文檔和Web的結(jié)構(gòu)內(nèi)容及用戶訪問信息構(gòu)成了Web數(shù)據(jù)挖掘的對(duì)象。根據(jù)挖掘?qū)ο蟮牟煌?將Web數(shù)據(jù)挖掘分為內(nèi)容挖掘、結(jié)構(gòu)挖掘和使用挖掘3類。所謂內(nèi)容挖掘是指在人為組織的Web上,從文件內(nèi)容及其描述中獲取有用信息的過程;結(jié)構(gòu)挖掘則是從人為的鏈接結(jié)構(gòu)、文檔的內(nèi)部結(jié)構(gòu)和文檔URL中的路徑結(jié)構(gòu)中獲取有用知識(shí)的過程;使用挖掘是通過挖掘相應(yīng)站點(diǎn)的日志文件和相關(guān)數(shù)據(jù)來發(fā)現(xiàn)該站點(diǎn)上的瀏覽者和顧客的行為模式。4云計(jì)算平臺(tái)的apriori關(guān)聯(lián)規(guī)則算法的設(shè)計(jì)4.1傳統(tǒng)abcjp二通道自適應(yīng)功能基于對(duì)分布式數(shù)據(jù)庫劃分的思想,把數(shù)據(jù)庫D劃分為:D1,D2…Dm,其中D1∪D2∪…∪Dm=D,D1∩D2∩…∩Dm=φ,劃分后將各個(gè)數(shù)據(jù)分塊分別發(fā)送到對(duì)應(yīng)的服務(wù)器節(jié)點(diǎn),每一個(gè)數(shù)據(jù)節(jié)點(diǎn)分別處理一個(gè)分塊,多節(jié)點(diǎn)可實(shí)現(xiàn)并行工作。Apriori算法對(duì)每個(gè)節(jié)點(diǎn)求解頻繁K-項(xiàng)集,求取對(duì)應(yīng)數(shù)據(jù)中包含的局部頻繁項(xiàng)集。Apriori使用逐層迭代方法,即用K-項(xiàng)集搜索(k+1)-項(xiàng)集。用LK-1與自己作連接產(chǎn)生候選K-項(xiàng)集的集合Ck,得到K-項(xiàng)集LK。這一步由各個(gè)任務(wù)獨(dú)立完成,而最后由全局端進(jìn)行由Ck得到Lk所進(jìn)行的閥值操作,最后由全局控制端使用公式:計(jì)算關(guān)聯(lián)規(guī)則的置信度。其中support_count(A∪B)是包含項(xiàng)集A∪B的事物數(shù),其值即為全局控制器得到頻繁項(xiàng)集的支持度計(jì)數(shù)。support_count(A)是包含項(xiàng)集A的事物數(shù),其值應(yīng)是各個(gè)服務(wù)器節(jié)點(diǎn)包含A的事物數(shù)的累加。4.2節(jié)點(diǎn)任務(wù)端機(jī)器上整個(gè)數(shù)據(jù)挖掘程序分為全局控制器(位于提交任務(wù)的機(jī)器上)和各個(gè)服務(wù)器節(jié)點(diǎn)任務(wù)端(位于各個(gè)服務(wù)器節(jié)點(diǎn)上)兩個(gè)部分。算法描述如下:輸入:數(shù)據(jù)挖掘任務(wù)輸出:關(guān)聯(lián)規(guī)則全局控制器:各個(gè)服務(wù)器節(jié)點(diǎn)任務(wù)端:4.3