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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 面向計(jì)算的高性能計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 哈希映射方法

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

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

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

現(xiàn)在以下面這個(gè)應(yīng)用場(chǎng)景為例,說(shuō)明一致性哈希算法實(shí)現(xiàn)計(jì)算和存儲(chǔ)位置一致性的方法:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖9 用MPI模擬流式拓?fù)溆成?/p>

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

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

5 結(jié)束語(yǔ)

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

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

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

[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/.