王 鵬, 黃 焱, 劉 峰, 安俊秀

(1.成都信息工程學(xué)院并行計算實驗室,四川成都610225;2.中國科學(xué)院成都計算機應(yīng)用研究所,四川成都610041;3.中國科學(xué)院大學(xué),北京 100049)

0 引言

信息技術(shù)的發(fā)展越來越清晰地呈現(xiàn)出兩大主題——計算和數(shù)據(jù),伴隨這兩大主題,信息技術(shù)領(lǐng)域出現(xiàn)了大數(shù)據(jù)這個技術(shù)概念,大數(shù)據(jù)技術(shù)的出現(xiàn)與云計算技術(shù)的出現(xiàn)幾乎是同時的,早在1960年John McCarthy預(yù)言:“今后計算機將會作為公共設(shè)施提供給公眾”[1]這一云計算核心理念,1984年SUN公司董事會主席John Gage提出“網(wǎng)絡(luò)就是計算機”[2]這一具有云計算特征的論點,到網(wǎng)絡(luò)的繁盛期2006年Google公司CEO Eric Schmidt提出云計算概念,再到2008年云計算概念全面進入中國,網(wǎng)絡(luò)技術(shù)在云計算發(fā)展歷程背后發(fā)揮了重要的推動作用。網(wǎng)絡(luò)技術(shù)的發(fā)展促使服務(wù)向云端集中,并使數(shù)據(jù)量出現(xiàn)爆發(fā)式增長,因此面向數(shù)據(jù)成為云計算技術(shù)的重要特征之一,在一段時間里云計算和大數(shù)據(jù)兩個概念甚至被當(dāng)成同一個概念使用,一些大數(shù)據(jù)系統(tǒng)如Hadoop也被稱為云計算系統(tǒng),概念的模糊使不少人產(chǎn)生困惑。嚴格來講,大數(shù)據(jù)技術(shù)是指針對海量數(shù)據(jù)的存儲、分析和發(fā)布技術(shù),而云計算是對資源和服務(wù)網(wǎng)絡(luò)化提供方式的一種描述,兩個概念之間的區(qū)別是很明顯的。大數(shù)據(jù)系統(tǒng)是一種計算和數(shù)據(jù)都密集的分布式系統(tǒng),計算需要為數(shù)據(jù)分析服務(wù),也可以稱之為面向數(shù)據(jù)的高性能計算,計算和數(shù)據(jù)的協(xié)作機制是研究這類系統(tǒng)的一個視角。

李國杰院士認為:“信息系統(tǒng)需要從數(shù)據(jù)圍繞著處理器轉(zhuǎn)改為處理能力圍繞著數(shù)據(jù)轉(zhuǎn),將計算用于數(shù)據(jù),而不是將數(shù)據(jù)用于計算”[3]。海量數(shù)據(jù)本身很難直接使用,只有通過處理的數(shù)據(jù)才能真正成為有用的數(shù)據(jù),因此計算和數(shù)據(jù)兩大主題可以進一步明確為數(shù)據(jù)和針對數(shù)據(jù)的計算,計算可以使海量數(shù)據(jù)成為有用的信息,進而處理成為知識。在大數(shù)據(jù)系統(tǒng)中存儲不是一個獨立存在的系統(tǒng),特別是在集群條件下,計算和存儲都是分布式的,如何讓計算“找”到自己需要處理的數(shù)據(jù)是大數(shù)據(jù)系統(tǒng)需要具有的核心功能。面向數(shù)據(jù)要求計算是面向數(shù)據(jù)的,那么數(shù)據(jù)的存儲方式將會深刻地影響計算實現(xiàn)的方式。這種在分布式系統(tǒng)中實現(xiàn)計算和數(shù)據(jù)有效融合從而提高數(shù)據(jù)處理能力,簡化分布式程序設(shè)計難度,降低系統(tǒng)網(wǎng)絡(luò)通訊壓力從而使系統(tǒng)能有效地面對大數(shù)據(jù)處理的機制稱為計算和數(shù)據(jù)的協(xié)作機制,在這種協(xié)作機制中計算如何找到數(shù)據(jù)并啟動分布式處理任務(wù)的問題是需要重點研究的課題,在文中這一問題被稱為計算和數(shù)據(jù)的位置一致性問題。

1 從面向計算到面向數(shù)據(jù)

1.1 計算機技術(shù)向大數(shù)據(jù)的演進歷程

大數(shù)據(jù)系統(tǒng)架構(gòu)的基本設(shè)計思想就是面向數(shù)據(jù),面向數(shù)據(jù)可以更準(zhǔn)確地稱為“面向數(shù)據(jù)的計算”,要求系統(tǒng)的設(shè)計和架構(gòu)是圍繞數(shù)據(jù)為核心展開的,而計算與數(shù)據(jù)的有效協(xié)作是面向數(shù)據(jù)的核心要求。

圖1 計算技術(shù)向大數(shù)據(jù)的演進

回顧計算機技術(shù)的發(fā)展歷程,可以清晰地看到計算機技術(shù)從面向計算逐步轉(zhuǎn)變到面向數(shù)據(jù)的過程。這一過程的描述如圖1所示,該圖從硬件、網(wǎng)絡(luò)和大數(shù)據(jù)的演進過程等方面以時間為順序進行了縱向和橫向的對比。

從圖1可以看到在計算機技術(shù)的早期由于硬件設(shè)備體積龐大,價格昂貴,這一階段數(shù)據(jù)的產(chǎn)生還是“個別”人的工作,這個時期的數(shù)據(jù)生產(chǎn)者主要是科學(xué)家或軍事部門,他們更關(guān)注計算機的計算能力,計算能力的高低決定了研究能力和一個國家軍事能力的高低,相對而言由于這時數(shù)據(jù)量很小,數(shù)據(jù)在整個計算系統(tǒng)中的重要性并不突出。這時網(wǎng)絡(luò)還沒有出現(xiàn),推動計算技術(shù)發(fā)展的主要動力是硬件的發(fā)展,這個時期是硬件的高速變革時期,硬件從電子管迅速發(fā)展到大規(guī)模集成電路。1969年ARPANET網(wǎng)絡(luò)的出現(xiàn)改變了整個計算機技術(shù)的發(fā)展歷史,網(wǎng)絡(luò)逐步成為推動技術(shù)發(fā)展的一個重要力量,1989年Tim Berners-Lee發(fā)明的萬維網(wǎng)改變了信息的交流方式,特別是高速移動通信網(wǎng)絡(luò)技術(shù)的發(fā)展和成熟使現(xiàn)在數(shù)據(jù)的生產(chǎn)成為全球人的共同活動,人們生產(chǎn)數(shù)據(jù)不再是在固定時間和固定地點進行,人們隨時隨地都在產(chǎn)生數(shù)據(jù),微博、博客、社交網(wǎng)、視頻共享網(wǎng)站、即時通訊等媒介隨時都在生產(chǎn)著數(shù)據(jù)并被融入全球網(wǎng)絡(luò)中。

從云計算之父John McCarthy提出云計算的概念到大數(shù)據(jù)之父Gray提出科學(xué)研究的第四范式,時間已經(jīng)跨越半個世紀(jì)。以硬件為核心的時代也是面向計算的時代,那時數(shù)據(jù)的構(gòu)成非常簡單,數(shù)據(jù)之間基本沒有關(guān)聯(lián)性,物理學(xué)家只處理物理實驗數(shù)據(jù),生物學(xué)家只處理生物學(xué)數(shù)據(jù),計算和數(shù)據(jù)之間的對應(yīng)關(guān)系非常簡單和直接。到以網(wǎng)絡(luò)為核心的時代,數(shù)據(jù)的構(gòu)成變得非常復(fù)雜,數(shù)據(jù)來源多樣化,不同數(shù)據(jù)之間存在大量的隱含關(guān)聯(lián)性,這時計算所面對的數(shù)據(jù)變得非常復(fù)雜,如社會感知、微關(guān)系等應(yīng)用將數(shù)據(jù)和復(fù)雜的人類社會運行相關(guān)聯(lián),由于人人都是數(shù)據(jù)的生產(chǎn)者,人們之間的社會關(guān)系和結(jié)構(gòu)就被隱含到所產(chǎn)生的數(shù)據(jù)中。數(shù)據(jù)的產(chǎn)生目前呈現(xiàn)出大眾化、自動化、連續(xù)化、復(fù)雜化的趨勢,大數(shù)據(jù)概念正是在這樣的背景下出現(xiàn),這一時期的典型特征就是計算必須面向數(shù)據(jù),數(shù)據(jù)是架構(gòu)整個系統(tǒng)的核心要素,這就使計算和存儲的協(xié)作機制研究成為需要重點關(guān)注的核心技術(shù),計算能有效找到自己需要處理的數(shù)據(jù)可以使系統(tǒng)能更高效地完成海量數(shù)據(jù)的處理和分析。

1.2 第四范式——大數(shù)據(jù)時代的科學(xué)研究方法

信息技術(shù)領(lǐng)域提出面向數(shù)據(jù)的概念同時也開始深刻地改變科學(xué)研究的模式,2007年著名的數(shù)據(jù)庫專家Gray提出科學(xué)研究的第四范式。他認為利用海量的數(shù)據(jù)已可以為科學(xué)研究和知識發(fā)現(xiàn)提供除經(jīng)驗,理論,計算外的第四種重要方法?？茖W(xué)研究的4個范式的發(fā)展歷程也同樣反映了從面向計算走向面向數(shù)據(jù)的過程。

圖2 科學(xué)研究4個范式的發(fā)展歷程

如圖2所示,人類早期知識的發(fā)現(xiàn)主要依賴于經(jīng)驗、觀察和實驗,需要的計算和產(chǎn)生的數(shù)據(jù)都很少,人類在這一時期對于宇宙的認識都是這樣形成的,就像伽利略為了證明自由落體定理,是通過在比薩斜塔扔下兩個大小不一的小球一樣,人類在那個時代知識的獲取方式是原始而樸素的。當(dāng)人類知識積累在一定程度后,知識逐漸形成了理論體系,如牛頓力學(xué)體系,Maxwell的電磁場理論,人類可以利用這些理論體系去預(yù)測自然并獲取新知識,這時對計算和數(shù)據(jù)的需求已經(jīng)在萌生,人類已可以依賴這些理論發(fā)現(xiàn)新的行星,如海王星、冥王星的發(fā)現(xiàn)不是通過觀測而是通過計算得到。計算機的出現(xiàn)為人類發(fā)現(xiàn)新的知識提供了重要的工具,這個時代正好對應(yīng)于面向計算的時代,這時可以在某些具有完善理論體系領(lǐng)域利用計算機仿真計算來進行研究,這時計算機的作用主要是計算,例如人類利用仿真計算可以實現(xiàn)模擬核爆這樣的復(fù)雜計算?，F(xiàn)在人類在一年內(nèi)所產(chǎn)生的數(shù)據(jù)可能已經(jīng)超過人類過去幾千年產(chǎn)生的數(shù)據(jù)的總和,即使是復(fù)雜度為O(n)的數(shù)據(jù)處理方法在面對龐大的n時都顯得力不從心,人類逐步進入大數(shù)據(jù)的時代,第四范式說明可以利用海量數(shù)據(jù)加上高速計算發(fā)現(xiàn)新的知識,計算和數(shù)據(jù)的關(guān)系在大數(shù)據(jù)時代變得十分緊密,也使計算和數(shù)據(jù)的協(xié)作問題面臨巨大的技術(shù)挑戰(zhàn)。

2 機群系統(tǒng)中計算和數(shù)據(jù)的協(xié)作機制分析

回顧高性能計算的發(fā)展過程可以將高性能計算分為面向計算的高性能計算和面向數(shù)據(jù)的高性能計算。傳統(tǒng)的高性能計算通常指面向計算的高性能計算,這種系統(tǒng)以實現(xiàn)高速的計算能力為目標(biāo);而面向數(shù)據(jù)的高性能計算以實現(xiàn)對海量數(shù)據(jù)的存儲和處理為目標(biāo)。由于他們都需要快速的計算能力所以這兩類系統(tǒng)常常以機群方式實現(xiàn)強大的計算。在機群系統(tǒng)中實施計算都存在計算如何獲得數(shù)據(jù)的問題,在面向計算系統(tǒng)中這一問題并不突出,在面向數(shù)據(jù)時代計算和數(shù)據(jù)的協(xié)作機制就成為必須考慮的問題,通常這種機制的實現(xiàn)與系統(tǒng)的架構(gòu)有緊密的關(guān)系,系統(tǒng)的基礎(chǔ)架構(gòu)決定了系統(tǒng)計算和數(shù)據(jù)的基本協(xié)作模式,下面以常見的分布式機群系統(tǒng)為例對計算和數(shù)據(jù)的協(xié)作機制進行分析對比。

2.1 面向計算的高性能計算

苗向計算的高性能計算系統(tǒng)出現(xiàn)在以硬件為核心的時代,從Cray C-90為代表的并行向量處理機[4]發(fā)展到IBM R50為代表的對稱多處理器機(SMP)[5]最終到工作站集群(COW)及Beowulf機群結(jié)構(gòu),這一過程對應(yīng)的正是CPU等硬件技術(shù)的高速發(fā)展,可以采用便宜的工作站甚至通用的PC機來架構(gòu)高性能系統(tǒng),完成面向計算的高性能計算任務(wù)。

基于消息傳遞機制的并行計算技術(shù)MPI(Message-Passing Interface)幫助工作站機群和Beowulf機群實現(xiàn)強大的計算能力,提供了靈活的編程機制。MPI將大量的節(jié)點通過消息傳遞機制連接起來,從而使節(jié)點的計算能力聚集成為強大的高性能計算,主要面向計算密集的任務(wù)。MPI提供API接口,通過MPI-Send()和MPI-Recv()等消息通訊函數(shù)實現(xiàn)計算過程中數(shù)據(jù)的交換。高性能計算是一種較為典型的面向計算的系統(tǒng),通常處理的是計算密集的工作,因此在基于MPI的分布式系統(tǒng)中并沒有與之匹配的文件系統(tǒng)支持,計算在發(fā)起前通過NFS等網(wǎng)絡(luò)文件系統(tǒng)從集中的存儲系統(tǒng)中讀出數(shù)據(jù)并用于計算。基于MPI的分布式系統(tǒng)的典型系統(tǒng)結(jié)構(gòu)如圖3所示。

從圖3知,典型的利用MPI實現(xiàn)的分布式計算系統(tǒng)在發(fā)起計算時,首先將計算程序由主節(jié)點通過NFS等網(wǎng)絡(luò)共享文件系統(tǒng)分發(fā)到各子節(jié)點內(nèi)存啟動計算,由于沒有分布式文件系統(tǒng)的支持,MPI一般不能直接從節(jié)點存儲設(shè)備上讀取數(shù)據(jù),計算程序在子節(jié)點發(fā)起后只有通過網(wǎng)絡(luò)共享文件讀取需要處理的數(shù)據(jù)來進行計算,在這里數(shù)據(jù)和計算程序一般都是被集中存儲在陣列等專門的存儲系統(tǒng)中。這一過程并沒有計算尋找數(shù)據(jù)的過程,計算程序只是按設(shè)計要求先被分發(fā)給所有參與計算的節(jié)點。在進行MPI并行程序設(shè)計時,程序設(shè)計者需要事先將計算任務(wù)本身在程序中進行劃分,計算程序被分配到節(jié)點后根據(jù)判斷條件啟動相應(yīng)的計算工作,計算中需要進行節(jié)點間的數(shù)據(jù)交換時通過MPI提供的消息傳遞機制進行數(shù)據(jù)交換。由于CPU的運行速度遠遠大于網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)乃俣?通常希望不同節(jié)點間的任務(wù)關(guān)聯(lián)性越小越好,在MPI的編程實踐中就是“用計算換數(shù)據(jù)通訊”的原則,使系統(tǒng)盡可能少的進行數(shù)據(jù)交換。MPI的消息傳遞機制為計算的并行化提供了靈活的方法,但目前對于任意問題的自動并行化并沒有非常有效的方法,因此計算的切分工作往往需要編程人員自己根據(jù)經(jīng)驗來完成,所以這種靈活性是以增加編程的難度為代價的。

圖3 MPI的典型系統(tǒng)架構(gòu)

基于MPI的高性能計算是一種典型的面向計算的分布式系統(tǒng),這種典型的面向計算的系統(tǒng)往往要求節(jié)點的計算能力越強越好,從而降低系統(tǒng)的數(shù)據(jù)通訊代價。MPI的基本工作過程可以總結(jié)為:切分計算,注入程序,啟動計算,讀取數(shù)據(jù)。MPI雖然是典型的面向計算的分布式系統(tǒng),但它也有類似于后來Google系統(tǒng)中的MapReduce能力,如MPI提供MPI-Reduce()函數(shù)實現(xiàn)Reduce功能[6],只是沒有像GFS這樣的分布式文件系統(tǒng)的支持,MPI的Reduce能力是相對有限而低效的,并不能實現(xiàn)計算在數(shù)據(jù)存儲位置發(fā)起的功能。

通常將MPI這樣以切分計算實現(xiàn)分布式計算的系統(tǒng)稱為面向計算的高性能計算系統(tǒng)。這種系統(tǒng)計算和存儲的協(xié)作是通過數(shù)據(jù)向計算的遷移實現(xiàn),也就是說系統(tǒng)先定位計算節(jié)點再將數(shù)據(jù)從集中存儲設(shè)備通過網(wǎng)絡(luò)讀入計算程序所在的節(jié)點,在數(shù)據(jù)量不大時這種方法是可行的,但對于海量數(shù)據(jù)讀取這種方式會很低效。

2.2 面向數(shù)據(jù)的高性能計算

進入網(wǎng)絡(luò)高速發(fā)展的時期,數(shù)據(jù)的產(chǎn)生成為了全民無時無刻不在進行的日常行為,數(shù)據(jù)量呈現(xiàn)出爆炸式增長,大數(shù)據(jù)時代到來,數(shù)據(jù)的作用被提到很高的地位,人們對數(shù)據(jù)帶來的知識發(fā)現(xiàn)表現(xiàn)出強烈的信心。長期以來數(shù)據(jù)挖掘技術(shù)的應(yīng)用一直都處于不溫不火的狀態(tài),大數(shù)據(jù)時代的到來也使這一技術(shù)迅速地被再次重視起來,基于海量數(shù)據(jù)的挖掘被很快應(yīng)用于網(wǎng)頁數(shù)據(jù)分析、客戶分析、行為分析、社會分析[7],現(xiàn)在可以經(jīng)?？吹奖粶?zhǔn)確推送到自己電腦上的產(chǎn)品介紹和新聞報道就是基于這類面向數(shù)據(jù)的數(shù)據(jù)挖掘技術(shù)?；跀?shù)據(jù)切分實現(xiàn)分布式計算的方法被稱為數(shù)據(jù)并行(data parallel)方法,但在面向計算時代真正的問題在于計算和數(shù)據(jù)之間只是簡單的協(xié)作關(guān)系,數(shù)據(jù)和計算事實上并沒有很好的融合,計算只是簡單地讀取其需要處理的數(shù)據(jù)而已,系統(tǒng)并沒有太多地考慮數(shù)據(jù)的存儲方式,網(wǎng)絡(luò)帶寬的利用率等問題。

通過數(shù)據(jù)切分實現(xiàn)計算的分布化是面向數(shù)據(jù)技術(shù)的一個重要特征,2003年Google逐步公開了它的系統(tǒng)結(jié)構(gòu),Google的GFS文件系統(tǒng)實現(xiàn)了在文件系統(tǒng)上就對數(shù)據(jù)進行了切分,這一點對利用MapReduce實現(xiàn)對數(shù)據(jù)的自動分布式計算非常重要,文件系統(tǒng)自身就對文件施行了自動的切分完全改變了分布式計算的性質(zhì),MPI、網(wǎng)格計算都沒有相匹配的文件系統(tǒng)支持,從本質(zhì)上看數(shù)據(jù)都是集中存儲的,網(wǎng)格計算雖然有數(shù)據(jù)切分的功能,但只是在集中存儲前提下的切分。具有數(shù)據(jù)切分功能的文件系統(tǒng)是面向數(shù)據(jù)的分布式系統(tǒng)的基本要求。

2004年Jeffrey Dean和Sanjay Ghemawat描述了Google系統(tǒng)的MapReduce框架[8],與MPI不同這種框架通常不是拆分計算來實現(xiàn)分布式處理,而是通過拆分數(shù)據(jù)來實現(xiàn)對大數(shù)據(jù)的分布式處理,MapReduce框架中分布式文件系統(tǒng)是整個框架的基礎(chǔ),如圖4所示。這一框架下的文件系統(tǒng)一般將數(shù)據(jù)分為64MB的塊進行分布式存放,需要對數(shù)據(jù)進行處理時將計算在各個塊所在的節(jié)點直接發(fā)起,避免了從網(wǎng)絡(luò)上讀取數(shù)據(jù)所耗費的大量時間,實現(xiàn)計算主動“尋找”數(shù)據(jù)的功能,大大簡化了分布式處理程序設(shè)計的難度。在這里數(shù)據(jù)塊被文件系統(tǒng)預(yù)先切分是MapReduce能自動實現(xiàn)分布式計算的重要前提,系統(tǒng)通過主節(jié)點的元數(shù)據(jù)維護各數(shù)據(jù)塊在系統(tǒng)中存儲的節(jié)點位置,從而使計算能有效地找到所需要處理的數(shù)據(jù)。MapReduce這種大塊化的數(shù)據(jù)拆分策略非常適合對大數(shù)據(jù)的處理,過小的數(shù)據(jù)分塊會使這一框架在進行數(shù)據(jù)處理時的效率下降。這一框架在獲得良好的大數(shù)據(jù)并行處理能力的時候也有其應(yīng)用的局限,MapReduce框架在對同類型大數(shù)據(jù)塊進行同類型的計算處理時具有非常好的自動分布式處理能力,但在數(shù)據(jù)較小、數(shù)據(jù)類型復(fù)雜、數(shù)據(jù)處理方式多變的應(yīng)用場景卻效率相對低下。為了實現(xiàn)Google系統(tǒng)良好的計算和數(shù)據(jù)的協(xié)作機制GFS和MapReduce是密不可分的,沒有GFS支持單獨的采用MapReduce是沒有太大價值的。

圖4 基于數(shù)據(jù)切分的分布式系統(tǒng)結(jié)構(gòu)

MapReduce框架使計算在機群節(jié)點中能準(zhǔn)確找到所處理的數(shù)據(jù)所在節(jié)點位置的前提是所處理的數(shù)據(jù)具有相同的數(shù)據(jù)類型和處理模式,從而可以通過數(shù)據(jù)的拆分實現(xiàn)計算向數(shù)據(jù)的遷移,事實上這類面向數(shù)據(jù)系統(tǒng)的負載均衡在其對數(shù)據(jù)進行分塊時就完成了,系統(tǒng)各節(jié)點的處理壓力與該節(jié)點上的數(shù)據(jù)塊的具體情況相對應(yīng),因此MapReduce框架下某一節(jié)點處理能力低下可能會造成系統(tǒng)的整體等待形成數(shù)據(jù)處理的瓶頸。在MapReduce框架下節(jié)點服務(wù)器主要是完成基本的計算和存儲功能,因此可以采用廉價的服務(wù)器作為節(jié)點,這一變化改變了人們對傳統(tǒng)服務(wù)器的看法。2005年Apache基金會以Google的系統(tǒng)為模板啟動了Hadoop項目,Hadoop完整地實現(xiàn)了上面描述的面向數(shù)據(jù)切分的分布式計算系統(tǒng),對應(yīng)的文件系統(tǒng)為HDFS[9],Hadoop成為了面向數(shù)據(jù)系統(tǒng)的一個被廣泛接納的標(biāo)準(zhǔn)系統(tǒng)。類似的如HPCC(High Performance Computing Cluster)系統(tǒng)則不是通過基于數(shù)據(jù)塊的數(shù)據(jù)分割而是通過基于記錄的數(shù)據(jù)分割來實現(xiàn)對數(shù)據(jù)的分布式計算,但進行數(shù)據(jù)分割的方法都是一樣的。

同時數(shù)據(jù)分析技術(shù)是面向數(shù)據(jù)的高性能計算的研究熱點。對類似于Web海量數(shù)據(jù)的分析需要對大量的新增數(shù)據(jù)進行分析,由于MapReduce框架無法對以往的局部,中間計算結(jié)果進行存儲,MapReduce框架只能對新增數(shù)據(jù)后的數(shù)據(jù)集全部進行重新計算,以獲得新的索引結(jié)果,這樣的計算方法所需要的計算資源和耗費的計算時間會隨著數(shù)據(jù)量的增加線性增加。Percolator是一種全新的架構(gòu),可以很好地用于增量數(shù)據(jù)的處理分析,已在Google索引中得到應(yīng)用,大大提升Google索引更新速度[10],但與MapReduce等非增量系統(tǒng)不再兼容,并且編程人員需要根據(jù)特定應(yīng)用開發(fā)動態(tài)增量的算法,使算法和代碼復(fù)雜度大大增加。Incoop[11]提出增量Hadoop文件系統(tǒng)(Inc-HDFS),HDFS按照固定的塊大小進文件劃分,而Inc-HDFS則根據(jù)內(nèi)容進行文件劃分,當(dāng)文件的內(nèi)容發(fā)生變化時,只有少量的文件塊發(fā)生變化,大大減少了Map操作量。

迭代操作是PageRank、K-means等Web數(shù)據(jù)分析的核心操作,MapReduce作為一種通用的并行計算框架,其下一步迭代必須等待上一步迭代完成并把輸出寫入文件系統(tǒng)才能進行,如果有終止條件檢查也必須等待其完成。同時,上一步迭代輸出的數(shù)據(jù)寫入文件系統(tǒng)后馬上又由下一步迭代讀入,導(dǎo)致了明顯的網(wǎng)絡(luò)帶寬,I/O、CPU時間的浪費。iHadoop在分析了迭代過程存在的執(zhí)行相關(guān),數(shù)據(jù)相關(guān),控制相關(guān)之后對潛在的可并行性進行挖掘,提出了異步迭代方式,比Hadoop實現(xiàn)的MapReduce執(zhí)行時間平均減少了25%[12]。Twister對MapReduce的任務(wù)復(fù)用、數(shù)據(jù)緩存、迭代結(jié)束條件判斷等進行調(diào)整以適合迭代計算,但其容錯機制還很欠缺[13]。

Pregel是Google提出專用于解決分布式大規(guī)模圖計算的計算模型[14],適合計算FaceBook等社交關(guān)系圖分析,其將處理對象看成是連通圖,而MapReduce將處理對象看成是Key-Value對;Pregel將計算細化到頂點,而MapReduce將計算進行批量化,按任務(wù)進行循環(huán)迭代控制[15]。

在分布式文件系統(tǒng)條件下數(shù)據(jù)的切分使對文件的管理變復(fù)雜化,因此此類集群系統(tǒng)下文件系統(tǒng)的管理和數(shù)據(jù)分析是需要進行重點關(guān)注的研究領(lǐng)域之一,面向數(shù)據(jù)的高性能計算系統(tǒng)就是大數(shù)據(jù)系統(tǒng)。

2.3 兩種高性能計算系統(tǒng)的分析對比

表1 兩種高性能計算系統(tǒng)的對比

從面向計算發(fā)展到面向數(shù)據(jù),分布式系統(tǒng)的主要特征發(fā)生了變化,表1對面向計算的高性能計算系統(tǒng)和面向數(shù)據(jù)的高性能計算系統(tǒng)進行了對比和分析。面向數(shù)據(jù)的高性能計算系統(tǒng)往往有對應(yīng)的分布式文件系統(tǒng)的支持,從文件存儲開始就實現(xiàn)數(shù)據(jù)塊的劃分,為數(shù)據(jù)分析時實現(xiàn)自動的分布式計算提供了可能,計算和數(shù)據(jù)的協(xié)作機制在面向數(shù)據(jù)的系統(tǒng)中成為了核心問題,其重要性凸現(xiàn)出來。

由于面向計算的高性能計算系統(tǒng)具有靈活和功能強大的計算能力,能完成大多數(shù)問題的計算任務(wù),而面向數(shù)據(jù)的高性能計算系統(tǒng)雖然能較好地解決海量數(shù)據(jù)的自動分布式處理問題,但目前其仍是一種功能受限的分布式計算系統(tǒng),并不能靈活地適應(yīng)大多數(shù)的計算任務(wù),因此現(xiàn)在已有一些研究工作在探討將面向計算的高性能計算系統(tǒng)與面向數(shù)據(jù)高性能計算系統(tǒng)進行結(jié)合,希望能在計算的靈活性和對海量數(shù)據(jù)的處理上獲得良好的性能。文獻[16]初步探討了MPI和Hadoop結(jié)合問題,Amazon EC2也發(fā)布了面向高性能計算的解決方案CCI(Cluster Compute Instances),文獻[17]利用標(biāo)準(zhǔn)測試程序?qū)Ρ攘嗽贏mazon EC2 CCI上實現(xiàn)的云計算模式的高性能計算和在本機群上實現(xiàn)的高性能計算之間的性能。文獻[18]討論了將MPI應(yīng)用于處理數(shù)據(jù)密集問題的可能性,將MPI的消息傳遞機制和Hadoop RPC進行對比,Hadoop RPC使Hadoop具有消息傳遞機制,這使其分布式編程能力變得更加靈活,但目前來說與MPI相比還有一定的差距。文獻[19]探討了采用MPI的機制實現(xiàn)MapReduce的可能性?？梢钥吹侥壳凹夹g(shù)的發(fā)展正在使面向計算和面向數(shù)據(jù)的系統(tǒng)之間的界限越來越不明確,很難準(zhǔn)確地說某一個系統(tǒng)一定是面向計算的還是面向數(shù)據(jù)的系統(tǒng),數(shù)據(jù)以及面向數(shù)據(jù)的計算在大數(shù)據(jù)時代到來時已緊密地結(jié)合在一起。

3 實現(xiàn)計算和數(shù)據(jù)協(xié)作機制的方法

面向數(shù)據(jù)的系統(tǒng)通常是分布式系統(tǒng),往往是計算向數(shù)據(jù)遷移從而降低數(shù)據(jù)在系統(tǒng)中傳輸?shù)耐ㄐ糯鷥r,實現(xiàn)計算尋找數(shù)據(jù),定位計算的前提是定位數(shù)據(jù),而且數(shù)據(jù)存儲和切分的方式又會影響計算(數(shù)據(jù)分析)的處理效率和模式,因此實現(xiàn)計算和數(shù)據(jù)的有效協(xié)作首先需要研究數(shù)據(jù)在分布式文件系統(tǒng)中的存儲方法,同時由于在分布式系統(tǒng)中需要解決數(shù)據(jù)的備份、冗余、節(jié)點失效處理等問題,這給研究計算和數(shù)據(jù)的協(xié)作機制提出巨大的挑戰(zhàn)。由于計算和數(shù)據(jù)的位置一致性是協(xié)作機制的核心研究內(nèi)容,下面主要從解決計算和數(shù)據(jù)位置一致性的角度進行討論。

3.1 計算和數(shù)據(jù)位置一致性的映射模型

在分布式系統(tǒng)中計算和數(shù)據(jù)的位置一致性問題可以等效地理解為將計算和數(shù)據(jù)映射到同一個節(jié)點位置上,也就是說使計算在數(shù)據(jù)存儲的位置發(fā)起。例如網(wǎng)格計算系統(tǒng)就是計算先于數(shù)據(jù)到達客戶節(jié)點,數(shù)據(jù)根據(jù)客戶端請求被映射到指定的客戶端進行處理;Hadoop系統(tǒng)是數(shù)據(jù)先于計算被存儲于分布式系統(tǒng)的某一個節(jié)點,計算發(fā)起時通過元數(shù)據(jù)查詢獲得數(shù)據(jù)的存儲位置,Map任務(wù)被映射到相應(yīng)的節(jié)點進行處理。因此可以把計算和數(shù)據(jù)的位置一致性問題抽象為如圖5的映射模型。數(shù)據(jù)和計算的映射過程其實就是數(shù)據(jù)到節(jié)點的映射過程,計算程序片和數(shù)據(jù)片按照一定的映射規(guī)則定位到節(jié)點,將數(shù)據(jù)和計算注入節(jié)點,當(dāng)集群節(jié)點發(fā)生失效時,數(shù)據(jù)片按規(guī)則進行數(shù)據(jù)遷移和備份,計算程序片則按照相應(yīng)的規(guī)則重新映射到其對應(yīng)的節(jié)點。

圖5 計算和數(shù)據(jù)位置一致性的映射模型

在這個模型中計算本身也被視為一種特殊數(shù)據(jù),因為計算其實就是某種程序語言設(shè)計的可執(zhí)行程序片,在被系統(tǒng)映射時可以與數(shù)據(jù)同等對待,而且計算程序中往往包含了其所要處理的數(shù)據(jù)的邏輯位置信息。分布式文件系統(tǒng)中定位數(shù)據(jù)塊的算法其實就是起到了將數(shù)據(jù)映射到相應(yīng)的節(jié)點上的功能。所以在前面講到要實現(xiàn)計算和數(shù)據(jù)的位置一致性系統(tǒng)必須要有相應(yīng)的分布式文件系統(tǒng)的支持。同時由于分布式系統(tǒng)存在數(shù)據(jù)冗余、計算遷移、存儲遷移等問題,在具體實現(xiàn)時會與節(jié)點負載均衡調(diào)度算法、存儲冗余技術(shù)(如副本策略、糾刪碼)[20]等技術(shù)相結(jié)合,實現(xiàn)一個計算和數(shù)據(jù)有效協(xié)作條件下的健壯穩(wěn)定的高可用系統(tǒng)。相應(yīng)典型的映射方法可以分為元數(shù)據(jù)映射方法,哈希映射方法。

3.2 元數(shù)據(jù)映射方法

元數(shù)據(jù)映射方法是最容易想到的實現(xiàn)計算和存儲位置一致性的方案,元數(shù)據(jù)方法通過在元數(shù)據(jù)庫中保存數(shù)據(jù)塊的存儲位置,使計算按照元數(shù)據(jù)庫中的位置被映射到指定的存儲節(jié)點上。元數(shù)據(jù)方法實現(xiàn)數(shù)據(jù)和計算的定位非常類似于網(wǎng)絡(luò)路由中的路由表,計算和數(shù)據(jù)通過查詢路由表來保證計算和數(shù)據(jù)能被分配到同一個節(jié)點。采用元數(shù)據(jù)方法的分布式系統(tǒng)通常是主從結(jié)構(gòu),單點失效對系統(tǒng)的影響較為嚴重,GFS、HDFS的結(jié)構(gòu)就是采用元數(shù)據(jù)方法構(gòu)建,在Hadoop中的Namenode就是負責(zé)存儲元數(shù)據(jù)的管理節(jié)點,元數(shù)據(jù)方法系統(tǒng)在存儲數(shù)據(jù)時的策略通常會根據(jù)各節(jié)點當(dāng)前的存儲負載來判斷,為了避免主從結(jié)構(gòu)對單節(jié)點失效的敏感,文獻[21]通過元數(shù)據(jù)復(fù)制方法實現(xiàn)Hadoop系統(tǒng)的高可用性,Hadoop也可以通過Zookeeper組件利用主備機方案來提升系統(tǒng)的可用性。

采用元數(shù)據(jù)方法可以較為容易地利用集群系統(tǒng)當(dāng)前的工作狀態(tài)作為依據(jù)實現(xiàn)分布式系統(tǒng)負載均衡,這時主節(jié)點會根據(jù)監(jiān)控系統(tǒng)獲得的數(shù)據(jù)利用一定的調(diào)度算法對數(shù)據(jù)的存儲和計算的進行分配實現(xiàn)系統(tǒng)的負載均衡,并將相應(yīng)的分配信息作為元數(shù)據(jù)進行保存。不少針對集群負載均衡的算法都可以用在元數(shù)據(jù)方法中作為主節(jié)點分配資源的依據(jù),這類方法學(xué)者已進行了較為充分的研究。例如,文獻[22]研究了由海量不同性能的PC構(gòu)成的異構(gòu)集群的負載均衡算法,使弱計算節(jié)點不再成為異構(gòu)集群的性能瓶頸;文獻[23]提出了一種基于分布式架構(gòu)的動態(tài)自適應(yīng)集群負載均衡算法,該算法具備在線負載預(yù)測機制,通過調(diào)整負載信息的采樣方式,有效降低網(wǎng)絡(luò)交換壓力,提高算法響應(yīng)速度;文獻[24]提出了一種基于認知可信模型的動態(tài)優(yōu)先級調(diào)度算法,確保任務(wù)在安全的環(huán)境中運行,提高了集群任務(wù)分配的成功率;文獻[25]總結(jié)了3種分布式集群負載均衡算法:蜂群算法、隨機抽樣算法和動態(tài)聚集算法,比較分析了使用這3種算法時集群性能與節(jié)點數(shù)和節(jié)點性能的關(guān)系;文獻[26]提出一種基于指數(shù)平滑預(yù)測的加權(quán)最小連接算法,根據(jù)系統(tǒng)的當(dāng)前任務(wù)對集群的負載進行動態(tài)預(yù)測,提高集群的資源使用率;文獻[27]提出了一種基于遺傳算法的任務(wù)調(diào)度策略,將智能算法運用于集群調(diào)度。

元數(shù)據(jù)映射方法雖然在面對網(wǎng)絡(luò)信息搜索這類大塊數(shù)據(jù)應(yīng)用時特別有效,也非常便于大量成熟的負載均衡算法的應(yīng)用,但在面對有大量小文件的系統(tǒng)時由于元數(shù)據(jù)服務(wù)器需要維護大量的路由數(shù)據(jù),查詢的效率會變低。

3.3 哈希映射方法

哈希算法是一種從稀疏值范圍到緊密值范圍的映射方法,在存儲和計算定位時可以被看作是一種路由算法,通過這種路由算法文件塊能被唯一地定位到一個節(jié)點的位置。傳統(tǒng)的哈希算法容錯性和擴展性都不好,無法有效地適應(yīng)面向數(shù)據(jù)系統(tǒng)節(jié)點的動態(tài)變化。1997年David Karger提出了一致性哈希算法來定位數(shù)據(jù)[28],實現(xiàn)了機群系統(tǒng)在節(jié)點變化時的單調(diào)性,實現(xiàn)了較小的數(shù)據(jù)遷移代價。Amazon的云存儲系統(tǒng)Dynamo改進了基本的一致性哈希算法,引入虛擬節(jié)點,使系統(tǒng)具有更加均衡的存儲定位能力。Facebook開發(fā)的Cassandra系統(tǒng)也采用了一致性哈希算法的存儲管理算法。一致性哈希算法及其改進算法已成為分布式存儲領(lǐng)域的一個標(biāo)準(zhǔn)技術(shù)。使用一致性哈希算法的系統(tǒng)無需中心節(jié)點來維護元數(shù)據(jù),解決了元數(shù)據(jù)服務(wù)器的單點失效和性能瓶頸問題,但對于系統(tǒng)的負載均衡和調(diào)度節(jié)點的有效性提出了更高的要求。

一致性哈希算法的基本實現(xiàn)過程為:對Key值首先用MD5算法將其變換一個長度32位的16進制數(shù)值,再用這個數(shù)值對232取模,將其映射到由232個值構(gòu)成的環(huán)狀哈?？臻g,對節(jié)點也以相同的方法映射到環(huán)狀哈希空間,最后Key值會在環(huán)狀哈?？臻g中找到大于它的最小的節(jié)點值作為路由值。

基于一致性哈希的原理可以給出計算和存儲的一致性哈希方法,從而使計算能在數(shù)據(jù)存儲節(jié)點發(fā)起。對于多用戶分布式存儲系統(tǒng)來說:“用戶名+邏輯存儲位置”所構(gòu)成的字符串在系統(tǒng)中是唯一確定的,如屬于用戶wang,邏輯存儲位置為/test/test1.txt的文件所構(gòu)成的字符串“wang/test/test1.txt”在系統(tǒng)中一定是唯一的,同時某一個計算任務(wù)需要對test1.txt這個文件進行操作和處理,則它一定會在程序中指定用戶名和邏輯位置,因此存儲和計算test1.txt都利用相同的一致性哈希算法就能保證計算被分配的節(jié)點和當(dāng)時存儲test1.txt文件時被分配的節(jié)點是同一個節(jié)點。

現(xiàn)在以下面這個應(yīng)用場景為例,說明一致性哈希算法實現(xiàn)計算和存儲位置一致性的方法:

(1)面向相對“小”數(shù)據(jù)進行處理,典型的文件大小為100MB之內(nèi),通常不涉及對文件的分塊問題,這一點與MapReduce框架不同;

(2)待處理數(shù)據(jù)之間沒有強的關(guān)聯(lián)性,數(shù)據(jù)塊之間的處理是獨立的,數(shù)據(jù)處理是不需要進行數(shù)據(jù)塊之間的消息通訊,保證節(jié)點間發(fā)起的計算是低偶合的計算任務(wù);

(3)程序片的典型大小遠小于需要處理的數(shù)據(jù)大小,計算程序片本質(zhì)上也可以看作是一種特殊的數(shù)據(jù),這一假設(shè)在大多數(shù)情況下成立;

(4)數(shù)據(jù)的存儲先于計算發(fā)生。

根據(jù)一致性哈希算法的基本原理在面向數(shù)據(jù)的分布式系統(tǒng)中計算和存儲位置一致性方法如圖6所示,其主要步驟如下:

(1)將服務(wù)器節(jié)點以IP地址用為Key值,以一致性哈希方法映射到哈希環(huán)上;

(2)在數(shù)據(jù)存儲時以(用戶名+文件邏輯位置)作為唯一的Key值,映射到哈希環(huán)上,并順時針找到離自己哈希值最近的節(jié)點作為實際數(shù)據(jù)存儲的位置;

(3)在發(fā)起計算任務(wù)時提取計算任務(wù)所要操作的數(shù)據(jù)對應(yīng)的(用戶名+文件邏輯位置)值作為Key值,映射到哈希環(huán)上,并順時針找到離自己哈希值最近的節(jié)點注入程序并發(fā)起計算的節(jié)點。由于相同用戶的相同數(shù)據(jù)其(用戶名+文件邏輯位置)在一致性哈希算法作用下一定會被分配到相同的節(jié)點,從而保證了計算所發(fā)起的節(jié)點剛好就是計算所需要處理的數(shù)據(jù)所在的節(jié)點。

在這種算法的支持下只要計算程序片需要處理的數(shù)據(jù)邏輯位置是確定的,系統(tǒng)就會將計算程序片路由到數(shù)據(jù)存儲位置所在的節(jié)點,這時節(jié)點間的負載均衡性是由數(shù)據(jù)分布的均衡化來實現(xiàn)。

圖6 一致性哈希算法實現(xiàn)計算與數(shù)據(jù)的位置一致性

一致性哈希算法可以實現(xiàn)無中心節(jié)點的計算和數(shù)據(jù)定位,使計算可以唯一地找到其所要處理和分析數(shù)據(jù),使計算能最大可能地在數(shù)據(jù)存儲的位置發(fā)起,節(jié)約大量的網(wǎng)絡(luò)資源,同時避免了系統(tǒng)單點失效造成的不良影響,利用一致性哈希方法在面對海量文件時系統(tǒng)不用維護一個龐大的元數(shù)據(jù)庫用于保存文件的存儲信息,計算尋找數(shù)據(jù)的速度非常直接,路由算法復(fù)雜度低。

4 計算和數(shù)據(jù)的流式拓樸協(xié)作機制

多數(shù)大數(shù)據(jù)系統(tǒng)(如Hadoop,HPCC)的實現(xiàn)都是以非實時批處理方式進行的,在實時處理領(lǐng)域不能有效的發(fā)揮作用,實時大數(shù)據(jù)系統(tǒng)的出現(xiàn)填補了大數(shù)據(jù)系統(tǒng)在實時處理上的弱點,Storm就是一種較為典型的實時大數(shù)據(jù)處理系統(tǒng)。

4.1 典型的流式分布式系統(tǒng)——Storm系統(tǒng)

在高性能數(shù)據(jù)處理中流水線(pipelining)技術(shù)[29]是一項重要的并行技術(shù),基本思想為:將一個任務(wù) t分成一系列有先后關(guān)系的子任務(wù)t1,t2…,tm,在流水線模式中ti任務(wù)的啟動依賴于ti-1任務(wù)的完成。對于數(shù)據(jù)具有強的先后相關(guān)性的數(shù)據(jù)分析任務(wù)十分適用。采用流式技術(shù)作為分布式系統(tǒng)計算和數(shù)據(jù)協(xié)作機制的框架,已越來越顯示出其靈活性和生命力,與Dynamo和MapReduce等采用的技術(shù)形成鼎立的關(guān)系,微軟發(fā)布Dryad[30]就是將任務(wù)表示為一個有向無環(huán)圖(Directed Acycline Graph,DAG)實現(xiàn)分布式任務(wù)設(shè)計,與其相似的開源實現(xiàn)Storm中采用的Topology也是這種模式,本節(jié)以Storm為例進行介紹。

Storm是由Twitter推出的面向?qū)崟r應(yīng)用的流式分布式系統(tǒng)[31],集群由一個主節(jié)點和多個工作節(jié)點組成,主節(jié)點用于分配代碼,布置任務(wù)及故障檢測。

如圖7所示,Storm要完成一個實時計算任務(wù)需要建立一個Topology,Topology對數(shù)據(jù)處理的邏輯計算規(guī)劃,在Storm系統(tǒng)中數(shù)據(jù)流的基本單位為元組tuple,tuple可以看作是一個被封裝的數(shù)據(jù)結(jié)構(gòu),Storm最高一級的執(zhí)行單元就是Topology,Topology是由一個個計算節(jié)點構(gòu)成的拓撲,拓撲上的每一個節(jié)點完成一定的計算邏輯,圖中的箭頭表示數(shù)據(jù)的流向。流水線技術(shù)也叫管道技術(shù),所以Storm的設(shè)計者把數(shù)據(jù)流的生成器叫做Spout,把每一個處理位置叫做Bolt。由于Spout是數(shù)據(jù)流的源頭,Spout讀取數(shù)據(jù)并形成流傳送給Bolt,Bolt可以接收任意多個輸

入流,并對流中的數(shù)據(jù)進行特定的處理。相比在高性能計算領(lǐng)域傳統(tǒng)的流水線并行化技術(shù),Storm采用Topology結(jié)構(gòu)后使數(shù)據(jù)處理更為靈活功能更為強大。在Storm中主節(jié)點依據(jù)Topology的邏輯任務(wù)圖分配Bolt任務(wù),最終的任務(wù)會被分配到相應(yīng)的物理節(jié)點上。從Storm的架構(gòu)上看,在計算和數(shù)據(jù)協(xié)作機制的處理上Storm是由主節(jié)點依據(jù)Topology進行物理分配,元組tuple數(shù)據(jù)流按Topology的描述逐步被相應(yīng)Bolt節(jié)點上的計算程序所處理,并由主節(jié)點將這一邏輯過程映射為物理節(jié)點的順序。

圖7 Storm的Topology結(jié)構(gòu)示意

4.2 計算和數(shù)據(jù)協(xié)作機制的流式拓樸映射模型

Storm的系統(tǒng)結(jié)構(gòu)提示利用類似Topology這樣的邏輯結(jié)構(gòu)可以靈活地實現(xiàn)非常復(fù)雜的分布式數(shù)據(jù)處理任務(wù)。圖8將計算和數(shù)據(jù)協(xié)作機制的流式拓樸映射方法進行了抽象,在這種方法中Topology相當(dāng)于是對一個計算任務(wù)的邏輯規(guī)劃,并不直接對應(yīng)于物理節(jié)點,系統(tǒng)的主節(jié)點可能維護大量的這種Topology結(jié)構(gòu),每一個Topology結(jié)構(gòu)都相當(dāng)于是處理某一個問題的邏輯規(guī)劃。Topology結(jié)構(gòu)幾乎可以描述大多數(shù)問題的處理方法。圖中的操作相當(dāng)于是Storm系統(tǒng)的Bolt,數(shù)據(jù)發(fā)生器相當(dāng)于是Spout。系統(tǒng)主節(jié)點監(jiān)控和管理著大量的處理節(jié)點,對于每一個維護的Topology邏輯規(guī)劃主節(jié)點都會依據(jù)一定的策略為其分配相應(yīng)的物理節(jié)點以完成指定的計算任務(wù)。如圖8中所示,主節(jié)點為操作1分配物理節(jié)點1,為操作2分配物理節(jié)點2,為操作3分配物理節(jié)點3,為操作4分配物理節(jié)點1,這種分配完畢后Topology邏輯結(jié)構(gòu)就被映射為集群中的物理結(jié)構(gòu),并能實際地完成相應(yīng)的計算任務(wù)。作為編程人員只需要定義問題的Topology邏輯,Topology邏輯物理映射工作由主節(jié)點上的系統(tǒng)來維護,程序設(shè)計人員不用擔(dān)心節(jié)點的失效問題,因為當(dāng)某一操作對應(yīng)的節(jié)點失效時,主節(jié)點會將對應(yīng)的操作重新映射給一個完好的物理節(jié)點,從而保證整個Topology規(guī)劃能順利地執(zhí)行。

下面舉例說明Topology的映射過程,定義操作1是對輸入整型數(shù)據(jù)流的加2計算并輸出,操作2是對輸入整型數(shù)據(jù)流的加3計算并輸出,操作3是對輸入整型數(shù)據(jù)流的乘2計算并輸出,操作4是對輸入整型數(shù)據(jù)流的乘3計算并輸出,數(shù)據(jù)發(fā)生器不斷的產(chǎn)生整型數(shù)據(jù)。按照這一Topology的邏輯規(guī)劃,系統(tǒng)將操作1的計算程序注入物理節(jié)點1,操作2的計算程序注入物理節(jié)點2,操作3的計算程序注入物理節(jié)點3,操作4的計算程序注入物理節(jié)點1,并按Topology描述的流向建立節(jié)點1和節(jié)點2之間的流消息傳遞機制,節(jié)點3和節(jié)點1之間的流消息傳遞機制。啟動運算后如數(shù)據(jù)發(fā)生器1生成一個整型數(shù)據(jù)5后,節(jié)點1對其加2后將結(jié)果7傳送給節(jié)點2,節(jié)點2將其加3后輸出結(jié)果10,同時根據(jù)Topology的描述數(shù)據(jù)發(fā)生器1的數(shù)據(jù)也會送給節(jié)點3,節(jié)點3對其乘2后將結(jié)果10傳送給節(jié)點1,節(jié)點1將其乘3后輸出最后結(jié)果為30。數(shù)據(jù)發(fā)生器2產(chǎn)生的數(shù)據(jù)處理方法與此相似。

可以看出利用計算和數(shù)據(jù)協(xié)作機制的流式拓樸映射方法集群系統(tǒng)可以根據(jù)Topology的描述自動組合成不同的集群計算結(jié)構(gòu),從而能靈活面對復(fù)雜問題的處理。在這里主節(jié)點起到計算和數(shù)據(jù)的路由工作,計算和數(shù)據(jù)的協(xié)作機制就是依據(jù)Topology的描述來跟蹤定位的。

圖8 計算和數(shù)據(jù)協(xié)作機制的流式拓樸映射方法

用MPI來形式化的模擬從Topology到物理的映射過程,節(jié)點間通過MPI-Send()函數(shù)將流數(shù)據(jù)元組注入指定節(jié)點,在該節(jié)點上發(fā)起相應(yīng)的操作,并通過MPI-Recv()函數(shù)接收前端發(fā)來的數(shù)據(jù),實現(xiàn)節(jié)點間的通訊,如圖9所示。

圖9 用MPI模擬流式拓撲映射

主節(jié)點即節(jié)點0為數(shù)據(jù)發(fā)生器,發(fā)起兩個數(shù)據(jù)流。在數(shù)據(jù)流1中,節(jié)點0將其產(chǎn)生的數(shù)據(jù)通過MPI-Send()函數(shù)發(fā)送到節(jié)點1,節(jié)點1通過MPI-Recv()函數(shù)接收節(jié)點0發(fā)送來的數(shù)據(jù),并發(fā)起加2的操作,將結(jié)果通過MPI-Send()函數(shù)發(fā)送到節(jié)點2,節(jié)點2通過MPI-Recv()函數(shù)接收節(jié)點1發(fā)送來的數(shù)據(jù),并發(fā)起加3的操作。如果主節(jié)點不斷產(chǎn)生數(shù)據(jù)并向子節(jié)點發(fā)送數(shù)據(jù)就形成了流式系統(tǒng)的模式,MPI的靈活性在這里也體現(xiàn)得非常明顯。

從以上分析可以看出流式拓樸協(xié)作機制由于是基于機群結(jié)構(gòu)的因此可以實現(xiàn)海量數(shù)據(jù)的實時處理,避免了一些大數(shù)據(jù)系統(tǒng)只能對數(shù)據(jù)進行非實時批處理的問題,同時利用拓樸結(jié)構(gòu)可以實現(xiàn)更為靈活的分布式計算規(guī)劃,使大數(shù)據(jù)系統(tǒng)能靈活的設(shè)計數(shù)據(jù)分析算法。

5 結(jié)束語

從計算和數(shù)據(jù)的協(xié)作機制這一視角對大數(shù)據(jù)技術(shù)的發(fā)展歷程,主要的系統(tǒng)架構(gòu)分類,主流系統(tǒng)的實現(xiàn)機制進行了介紹、對比和分析。認為計算和數(shù)據(jù)的協(xié)作機制是實現(xiàn)大數(shù)據(jù)系統(tǒng)的關(guān)鍵核心技術(shù),協(xié)作機制的實現(xiàn)與分布式系統(tǒng)的整體架構(gòu)有緊密的聯(lián)系,特別是分布式文件系統(tǒng)與計算的融合是解決協(xié)作機制的關(guān)鍵,單獨地考慮存儲和單獨考慮計算在面向數(shù)據(jù)的分布式系統(tǒng)中都是不全面的,由于數(shù)據(jù)的分析處理也是非常重要的,所以大數(shù)據(jù)系統(tǒng)應(yīng)該是一種計算和數(shù)據(jù)都密集的系統(tǒng)。

未來大數(shù)據(jù)時代的數(shù)據(jù)會朝著:數(shù)據(jù)量更大,數(shù)據(jù)的關(guān)聯(lián)性更強,數(shù)據(jù)類型更多樣化的方向發(fā)展。同時大數(shù)據(jù)技術(shù)未來會呈現(xiàn)出以下發(fā)展趨勢和特點:(1)大數(shù)據(jù)系統(tǒng)中機群結(jié)構(gòu)會成為主流架構(gòu);(2)對單個節(jié)點計算能力和穩(wěn)定性的要求會下降;(3)傳統(tǒng)的面向計算的高性能計算技術(shù)會重新被人們認識并與大數(shù)據(jù)技術(shù)相結(jié)合,通過大數(shù)據(jù)系統(tǒng)使陽春白雪式的高性能計算變的更為貼近人們的生活;(4)新的大數(shù)據(jù)實現(xiàn)技術(shù)會涌現(xiàn),如實時大數(shù)據(jù)處理、大規(guī)模圖處理技術(shù);(5)數(shù)據(jù)挖掘算法特別是大數(shù)據(jù)架構(gòu)下的數(shù)據(jù)挖掘算法會得到更多的關(guān)注。

致謝:感謝成都市科技局創(chuàng)新發(fā)展戰(zhàn)略研究項目(11RKYB016ZF)對本文的資助

[1] Parkhill,D F.The challenge of the computer utility(Addison-Wesley Publishing Company Reading,1966.1966).

[2] http://en.wikipedia.org/wiki/John-Gage.

[3] Li,G.Scientific value of big data research[J].Communications of the CCF,2012,8(9):8-15.

[4] Batcher,K E.Design of a massively parallel processor[J].Computers,IEEE Transactions on,1980,100(9):836-840.

[5] Duncan,S H,Keefer,C D,McLaughlin T A.High performance I/O design in the AlphaServer 4100 symmetric multiprocessing system[J].Digital Technical Journal,1996,8(4):61-75.

[6] Wang,P.Cloud Computing:Key Technique and Application[M].Posts&Telecom Press,2010.

[7] Wang F Y,Carley K M,Zeng D.Social computing:From social informatics to social intelligence[J].Intelligent Systems,IEEE,2007,22(2):79-83.

[8] Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the Acm,2008,51(1):107-113.

[9] Borthakur D.HDFS architecture guide[EB/OL].Hadoop Apache Project.http://hadoop.apache.org/common/docs/current/hdfs-design.pdf,2008.

[10] Peng D,Dabek F.Large-scale incremental processing using distributed transactions and notifications[R].Proc.Proceedings of the 9th USENIX conference on Operating systems design and implementation,2010:1-15.

[11] Bhatotia P,Wieder A,Rodrigues R.Incoop:MapReduce for incremental computations[R].Proc.Proceedings of the 2nd ACM Symposium on Cloud Computing,2011:7.

[12] Elnikety E,Elsayed T,Ramadan H E.iHadoop:asynchronous iterations for MapReduce[R].Proc.Cloud Computing Technology and Science(CloudCom),2011 IEEE Third International Conference on,2011:81-90.

[13] Ekanayake J,Li H.Zhang B.Twister:a runtime for iterative mapreduce[R].Proc.Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing,2010:810-818.

[14] Malewicz G,Austern M H,Bik A J.Pregel:a system for large-scale graph processing[R].Proc.Proceedings of the 2010 ACM SIGMOD International Conference on Management of data,2010:135-146.

[15] http://wuyanzan60688.blog.163.com.

[16] Guo,B,Wang P,Chen G.Cloud Computing Model Based on MPI[J].Computer Engineering,2009,35(24).

[17] Zhai Y,Liu M,Zhai J.Cloud versus in-house cluster:evaluating Amazon cluster compute instances for running MPI applications[R].Proc.State of the Practice Reports,2011:11.

[18] Lu X,Wang B,Zha L.Can mpi benefit hadoop and mapreduce applications[R].Proc.Parallel Processing Workshops(ICPPW),2011 40th International Conference on,2011:371-379.

[19] Hoefler T,Lumsdaine A,Dongarra J.Towards efficient mapreduce using mpi[R].:Recent Advances in Parallel Virtual Machine and Message Passing Interface(Springer,2009),2009:240-249.

[20] Luo X,Shu J.Summary of Research for Erasure Code in Storage System[J].Journal of Computer Research and Development,2012,49(1):1-11.

[21] Wang F,Qiu J,Yang J,Dong B.Hadoop high availability through metadata replication[R].Proc.Proceedings of the first international workshop on Cloud data management,2009:37-44.

[22] Bohn C A,Lamont G B.Load balancing for heterogeneous clusters of PCs,Future Generation Computer Systems[J].2002,18(3):389-400.

[23] Dong B,Li X,Wu Q.A dynamic and adaptive load balancing strategy for parallel file system with large-scale I/O servers[J].Journal of Parallel and Distributed Computing,2012,(1).

[24] Wang W,Zeng G,Tang D.Cloud-DLS:Dynamic trusted scheduling for Cloud computing[J].Expert Systems with Applications,2012,39(3):2321-2329.

[25] Randles M,Lamb D,Taleb-Bendiab A.A comparative study into distributed load balancing algorithms for cloud computing[R].Proc.Advanced Information Networking and Applications Workshops(WAINA),2010 IEEE 24th International Conference on,2010:551-556.

[26] Ren X,Lin R,Zou H.A dynamic load balancing strategy for cloud computing platform based on exponential smoothing forecast[R].Proc.Cloud Computing and Intelligence Systems(CCIS),2011 IEEE International Conference on,2011:220-224.

[27] Ge Y,Wei G.Ga-based task scheduler for the cloud computing systems[R].Proc.Web Information Systems and Mining(WISM),2010 International Conference on,2010:181-186.

[28] Karger D.Sherman A.Berkheimer A.Web caching with consistent hashing,Computer Networks,1999,31(11):1203-1213.

[29] Shires D.Mohan R.Mark A.A Discussion of Optimization Strategies and Performance for Unstructured Computations in Parallel HPC Platforms',2001.

[30] Isard M.Budiu M.Yu Y.Dryad:distributed data-parallel programs from sequential building blocks,ACM SIGOPS Operating Systems Review,2007,41,(3):59-72.

[31] http://storm-project.net/.