云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)

云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2024/3/12云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)摘要隨著社交網(wǎng)絡(luò)分析、語義Web分析、生物信息網(wǎng)絡(luò)分析等新興應(yīng)用的快速增長(zhǎng),對(duì)億萬個(gè)頂點(diǎn)級(jí)別大規(guī)模圖的處理能力的需求愈加迫切,這是當(dāng)前高性能計(jì)算領(lǐng)域的研究和開發(fā)熱點(diǎn).文中結(jié)合云計(jì)算的特點(diǎn),從圖數(shù)據(jù)管理與圖數(shù)據(jù)處理機(jī)制兩個(gè)方面,綜述了云計(jì)算環(huán)境下進(jìn)行大規(guī)模圖數(shù)據(jù)處理的關(guān)鍵問題,包括圖數(shù)據(jù)的存儲(chǔ)方式、圖索引結(jié)構(gòu)、圖分割策略、圖計(jì)算模型、消息通信機(jī)制、容錯(cuò)管理、可伸縮性、圖查詢處理等.全面總結(jié)了當(dāng)前的研究現(xiàn)狀和進(jìn)展,詳細(xì)分析了存在的挑戰(zhàn)性問題,并深入探討了未來的研究方向.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)AbstractWiththerapidgrowthofemergingapplicationslikesocialnetworkana-nalysis,semanticWebanalysis,andbioinformaticsnetworkanalysis,itisurgenttorequiretheprocessingcapabilityonlargescalegraphswithbilli-onsofvertices,whichisthehottopicoftheresearchanddevelopmentinthecurrenthighperformancecomputingfield.Withthefeaturesofcloudcomputingandfromtheaspectsofgraphmanagementandgraphprocess-singmechanisms,thispapersurveysthekeyissuesoflargescalegraphprocessingoncloudcomputingenvironments,includinggraphdatastoragescheme,indexstructureofgraphdata,graphpartitioningstrategy,graphcomputingmodel

,messagecommunicationmechanism,fault-tolerancemanagement,scalability,andgraphqueryprocessing.Thispapersum-arizesthestate-of-artofcurrentresearchworkscompletely,analyzestheexistingchallengeproblemsindetail,anddeeplyexplorestheresearchdi-rectionsinfuture.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)目錄1.引言2.圖數(shù)據(jù)模型與存儲(chǔ)管理5.圖數(shù)據(jù)處理的執(zhí)行機(jī)制4.圖計(jì)算模型與典型系統(tǒng)結(jié)構(gòu)3.圖數(shù)據(jù)的分割策略6.圖查詢處理7.結(jié)束語云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)1.引言圖是計(jì)算機(jī)科學(xué)中最常用的一類抽象數(shù)據(jù)結(jié)構(gòu),在結(jié)構(gòu)和語義方面比線性表和樹更為復(fù)雜,更具有一般性表示能力.現(xiàn)實(shí)世界中的許多應(yīng)用場(chǎng)景都需要用圖結(jié)構(gòu)表示,與圖相關(guān)的處理和應(yīng)用幾乎無所不在.傳統(tǒng)應(yīng)用如最優(yōu)運(yùn)輸路線的確定、疾病爆發(fā)路徑的預(yù)測(cè)、科技文獻(xiàn)的引用關(guān)系等;新興應(yīng)用如社交網(wǎng)絡(luò)分析、語義Web分析、生物信息網(wǎng)絡(luò)分析等.雖然圖的應(yīng)用和處理技術(shù)已經(jīng)發(fā)展了很長(zhǎng)時(shí)間,理論也日趨完善,但是隨著信息化時(shí)代的到來,各種信息以爆炸模式增長(zhǎng),導(dǎo)致圖的規(guī)模日益增大,如何對(duì)大規(guī)模圖進(jìn)行高效處理,成為一個(gè)新的挑戰(zhàn).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)1.1大規(guī)模圖數(shù)據(jù)處理問題以互聯(lián)網(wǎng)和社交網(wǎng)絡(luò)為例,近十幾年來,隨著互聯(lián)網(wǎng)的普及和Web2.0技術(shù)的推動(dòng),網(wǎng)頁數(shù)量增長(zhǎng)迅猛,據(jù)CNNIC統(tǒng)計(jì),2010年中國(guó)網(wǎng)頁規(guī)模達(dá)到600億,年增長(zhǎng)率78.6%,而基于互聯(lián)網(wǎng)的社交網(wǎng)絡(luò)也后來居上,如全球最大的社交網(wǎng)絡(luò)Facebook,已有約7億用戶,國(guó)內(nèi)如QQ空間、人人網(wǎng)等,發(fā)展也異常迅猛.真實(shí)世界中實(shí)體規(guī)模的擴(kuò)張,導(dǎo)致對(duì)應(yīng)的圖數(shù)據(jù)規(guī)模迅速增長(zhǎng),動(dòng)輒有數(shù)十億個(gè)頂點(diǎn)和上萬億條邊.本文所指的大規(guī)模強(qiáng)調(diào)的就是單個(gè)圖的大規(guī)模性,通常包含10億個(gè)以上頂點(diǎn).面對(duì)這樣大規(guī)模的圖,對(duì)海量數(shù)據(jù)處理技術(shù)提出了巨大挑戰(zhàn).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)1.1大規(guī)模圖數(shù)據(jù)處理問題以搜索引擎中常用的PageRank計(jì)算為例,一個(gè)網(wǎng)頁的PageRank得分根據(jù)網(wǎng)頁之間相互的超鏈接關(guān)系計(jì)算而得到.將網(wǎng)頁用圖頂點(diǎn)表示,網(wǎng)頁之間的鏈接關(guān)系用有向邊表示,按鄰接表形式存儲(chǔ)100億個(gè)圖頂點(diǎn)和600億條邊,假設(shè)每個(gè)頂點(diǎn)及出度邊的存儲(chǔ)空間占100字節(jié),那么整個(gè)圖的存儲(chǔ)空間將超過1TB.如此大規(guī)模的圖,對(duì)其存儲(chǔ)、更新、查找等處理的時(shí)間開銷和空間開銷遠(yuǎn)遠(yuǎn)超出了傳統(tǒng)集中式圖數(shù)據(jù)管理的承受能力.針對(duì)大規(guī)模圖數(shù)據(jù)的高效管理,如存儲(chǔ)、索引、更新、查找等,已經(jīng)成為急需解決的問題.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)1.2采用云計(jì)算環(huán)境處理大規(guī)模圖的優(yōu)勢(shì)依靠云計(jì)算環(huán)境對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行高效處理,是一個(gè)非常有發(fā)展?jié)摿Φ姆较?其主要優(yōu)勢(shì)表現(xiàn)在:(1)海量的圖數(shù)據(jù)存儲(chǔ)和維護(hù)能力.大規(guī)模圖的數(shù)據(jù)量可達(dá)幾百GB甚至PB級(jí)別,難以在傳統(tǒng)文件系統(tǒng)或數(shù)據(jù)庫中存儲(chǔ),而云計(jì)算環(huán)境提供分布式存儲(chǔ)模式,可以匯聚成百上千普通計(jì)算機(jī)的存儲(chǔ)能力和計(jì)算能力,提供高容量的存儲(chǔ)服務(wù),完全能夠存放和處理大規(guī)模的圖數(shù)據(jù).云計(jì)算環(huán)境下的并發(fā)控制、一致性維護(hù)、數(shù)據(jù)備份和可靠性等控制策略,可以為大規(guī)模圖數(shù)據(jù)的維護(hù)提供保障.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)1.2采用云計(jì)算環(huán)境處理大規(guī)模圖的優(yōu)勢(shì)依靠云計(jì)算環(huán)境對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行高效處理,是一個(gè)非常有發(fā)展?jié)摿Φ姆较?其主要優(yōu)勢(shì)表現(xiàn)在:(1)海量的圖數(shù)據(jù)存儲(chǔ)和維護(hù)能力.(2)強(qiáng)大的分布式并行處理能力.利用云計(jì)算分布平行處理的特點(diǎn),可以將一個(gè)大圖分割成若干子圖,把針對(duì)一個(gè)大圖的處理分割為若干針對(duì)子圖的處理任務(wù).云計(jì)算分布式并行運(yùn)算能力,能夠顯著提高對(duì)大規(guī)模圖的處理能力.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)1.2采用云計(jì)算環(huán)境處理大規(guī)模圖的優(yōu)勢(shì)依靠云計(jì)算環(huán)境對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行高效處理,是一個(gè)非常有發(fā)展?jié)摿Φ姆较?其主要優(yōu)勢(shì)表現(xiàn)在:(1)海量的圖數(shù)據(jù)存儲(chǔ)和維護(hù)能力.(2)強(qiáng)大的分布式并行處理能力.(3)良好的可伸縮性和靈活性.從技術(shù)角度和經(jīng)濟(jì)角度講,云計(jì)算環(huán)境具有良好的可伸縮性和靈活性,非常適合處理數(shù)據(jù)量彈性變化的大規(guī)模圖問題.云計(jì)算環(huán)境通常由廉價(jià)的普通計(jì)算機(jī)構(gòu)成.隨著圖數(shù)據(jù)規(guī)模的不斷增大,可以向云中動(dòng)態(tài)添加節(jié)點(diǎn)來擴(kuò)展存儲(chǔ)容量和計(jì)算資源,而無需傳統(tǒng)并行機(jī)模式的巨大投資.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)1.3關(guān)鍵技術(shù)挑戰(zhàn)圖計(jì)算及其分布式并行處理通常涉及復(fù)雜的處理過程,需要大量的迭代和數(shù)據(jù)通信,針對(duì)聯(lián)機(jī)事務(wù)處理等應(yīng)用的傳統(tǒng)技術(shù)很難直接應(yīng)用到圖數(shù)據(jù)處理中.云計(jì)算環(huán)境下的大規(guī)模圖處理主要面臨兩大挑戰(zhàn):(1)圖計(jì)算的強(qiáng)耦合性.在一個(gè)圖中,數(shù)據(jù)之間都是相互關(guān)聯(lián)的,圖的計(jì)算也是相互關(guān)聯(lián)的.圖計(jì)算的并行算法中對(duì)內(nèi)存的訪問表現(xiàn)出很低的局部性.對(duì)于幾乎每一個(gè)頂點(diǎn)之間都是連通的圖來講,難以分割成若干完全獨(dú)立的子圖以進(jìn)行獨(dú)立的并行處理.并且,“水桶效應(yīng)”問題加劇.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)1.3關(guān)鍵技術(shù)挑戰(zhàn)圖計(jì)算及其分布式并行處理通常涉及復(fù)雜的處理過程,需要大量的迭代和數(shù)據(jù)通信,針對(duì)聯(lián)機(jī)事務(wù)處理等應(yīng)用的傳統(tǒng)技術(shù)很難直接應(yīng)用到圖數(shù)據(jù)處理中.云計(jì)算環(huán)境下的大規(guī)模圖處理主要面臨兩大挑戰(zhàn):(1)圖計(jì)算的強(qiáng)耦合性.為了提高執(zhí)行效率,需要采取多種優(yōu)化技術(shù).首先,在預(yù)處理階段進(jìn)行合適的圖分割時(shí),盡可能地降低子圖之間的耦合性;其次,在執(zhí)行階段應(yīng)選取合適的圖計(jì)算模型,避免迭代過程中反復(fù)啟動(dòng)任務(wù)和讀寫磁盤,降低任務(wù)調(diào)度開銷和IO開銷;應(yīng)充分利用迭代過程中的收斂特性進(jìn)行查詢優(yōu)化,同時(shí)進(jìn)行有效的同步控制和消息通信優(yōu)化,減少通信開銷,以達(dá)到降低水桶效應(yīng)的目的.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)1.3關(guān)鍵技術(shù)挑戰(zhàn)圖計(jì)算及其分布式并行處理通常涉及復(fù)雜的處理過程,需要大量的迭代和數(shù)據(jù)通信,針對(duì)聯(lián)機(jī)事務(wù)處理等應(yīng)用的傳統(tǒng)技術(shù)很難直接應(yīng)用到圖數(shù)據(jù)處理中.云計(jì)算環(huán)境下的大規(guī)模圖處理主要面臨兩大挑戰(zhàn):(1)圖計(jì)算的強(qiáng)耦合性.(2)云計(jì)算節(jié)點(diǎn)的低可靠性.大規(guī)模圖處理,需要相對(duì)較長(zhǎng)的時(shí)間來完成計(jì)算任務(wù),如PageRank計(jì)算需要約30次迭代處理,消耗大量的時(shí)間和資源.而云計(jì)算節(jié)點(diǎn)通常是由普通的計(jì)算機(jī)組成,在這種長(zhǎng)時(shí)間的處理過程中,個(gè)別節(jié)點(diǎn)出現(xiàn)故障是難免的.這時(shí)不能簡(jiǎn)單地重新計(jì)算,而應(yīng)該從斷點(diǎn)或者某個(gè)合適的位置接續(xù)執(zhí)行.否則,將造成很大的浪費(fèi),甚至一些大型的圖計(jì)算根本就不能完成.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)1.3關(guān)鍵技術(shù)挑戰(zhàn)圖計(jì)算及其分布式并行處理通常涉及復(fù)雜的處理過程,需要大量的迭代和數(shù)據(jù)通信,針對(duì)聯(lián)機(jī)事務(wù)處理等應(yīng)用的傳統(tǒng)技術(shù)很難直接應(yīng)用到圖數(shù)據(jù)處理中.云計(jì)算環(huán)境下的大規(guī)模圖處理主要面臨兩大挑戰(zhàn):(1)圖計(jì)算的強(qiáng)耦合性.(2)云計(jì)算節(jié)點(diǎn)的低可靠性.另一方面,由于圖計(jì)算并行子任務(wù)之間的強(qiáng)耦合性,一個(gè)子任務(wù)的失敗可能導(dǎo)致其它子任務(wù)的失敗,這又增加了恢復(fù)處理的復(fù)雜性.因此,需要考慮有效的容錯(cuò)管理機(jī)制,減少大規(guī)模圖處理過程中的故障恢復(fù)開銷,盡量避免重復(fù)計(jì)算,提高大規(guī)模圖處理的運(yùn)算效率和穩(wěn)定性云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)1.3關(guān)鍵技術(shù)挑戰(zhàn)圖計(jì)算及其分布式并行處理通常涉及復(fù)雜的處理過程,需要大量的迭代和數(shù)據(jù)通信,針對(duì)聯(lián)機(jī)事務(wù)處理等應(yīng)用的傳統(tǒng)技術(shù)很難直接應(yīng)用到圖數(shù)據(jù)處理中.云計(jì)算環(huán)境下的大規(guī)模圖處理主要面臨兩大挑戰(zhàn):(1)圖計(jì)算的強(qiáng)耦合性.(2)云計(jì)算節(jié)點(diǎn)的低可靠性.為了解決云計(jì)算環(huán)境下的大規(guī)模圖處理問題,可從圖數(shù)據(jù)管理和圖處理機(jī)制兩方面加以考慮.在圖數(shù)據(jù)管理上,需要解決圖數(shù)據(jù)的分割、圖數(shù)據(jù)的存儲(chǔ)、圖數(shù)據(jù)索引的建立、圖查詢處理等問題;在圖處理機(jī)制上,需要解決處理過程中圖計(jì)算模型選取、同步控制、消息通信、容錯(cuò)管理和可伸縮性等問題.本文將針對(duì)上述內(nèi)容,結(jié)合云計(jì)算的優(yōu)勢(shì)和存在的挑戰(zhàn),綜述云計(jì)算環(huán)境下的大規(guī)模圖處理現(xiàn)有技術(shù)的進(jìn)展解決方案以及今后的發(fā)展趨勢(shì)和研究方向.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)目錄1.引言2.圖數(shù)據(jù)模型與存儲(chǔ)管理5.圖數(shù)據(jù)處理的執(zhí)行機(jī)制4.圖計(jì)算模型與典型系統(tǒng)結(jié)構(gòu)3.圖數(shù)據(jù)的分割策略6.圖查詢處理7.結(jié)束語云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.圖數(shù)據(jù)模型與存儲(chǔ)管理圖數(shù)據(jù)的邏輯表達(dá)形式和物理存儲(chǔ)結(jié)構(gòu)是實(shí)現(xiàn)圖處理的基礎(chǔ).本節(jié)首先介紹圖數(shù)據(jù)模型,然后,介紹圖的存儲(chǔ)管理以及為了提高查找效率而為圖數(shù)據(jù)建立的索引結(jié)構(gòu).作為數(shù)學(xué)的一個(gè)重要分支,圖論以圖作為研究對(duì)象,在簡(jiǎn)單圖的基礎(chǔ)上衍生出超圖理論、極圖理論、拓?fù)鋱D論等,使圖可以從多方面表達(dá)現(xiàn)實(shí)世界.當(dāng)前大規(guī)模圖數(shù)據(jù)管理,采用的數(shù)據(jù)模型有多種.按照?qǐng)D中節(jié)點(diǎn)的復(fù)雜程度分為簡(jiǎn)單節(jié)點(diǎn)圖模型和復(fù)雜節(jié)點(diǎn)圖模型;按照一條邊可以連接的頂點(diǎn)數(shù)目分為簡(jiǎn)單圖模型和超圖模型.不論是簡(jiǎn)單圖模型、超圖模型、簡(jiǎn)單節(jié)點(diǎn)模型還是復(fù)雜節(jié)點(diǎn)模型,它們的頂點(diǎn)和邊都可以帶有屬性.下面介紹簡(jiǎn)單圖模型和超圖模型,其它模型請(qǐng)參考文獻(xiàn)[4].云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.1.1簡(jiǎn)單圖模型(1)簡(jiǎn)單圖模型.這里所說的簡(jiǎn)單圖,并不是圖論中的簡(jiǎn)單圖,是相對(duì)于超圖而言的.簡(jiǎn)單圖中,一條邊只能連接兩個(gè)頂點(diǎn)允許存在環(huán)路.簡(jiǎn)單圖的存儲(chǔ)和處理都比較容易,對(duì)于一般的應(yīng)用,簡(jiǎn)單圖的表達(dá)能力完全可以勝任,如PageRank計(jì)算、最短路徑查詢等.Pregel、Hama等系統(tǒng)均采用簡(jiǎn)單圖模型來組織存儲(chǔ)和處理大規(guī)模圖數(shù)據(jù).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.1.2超圖模型(2)超圖模型.一條邊可以連接任意數(shù)目的圖頂點(diǎn).此模型中圖的邊稱為超邊.基于這種特點(diǎn),超圖比上述簡(jiǎn)單圖的適用性更強(qiáng),保留的信息更多.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.1.2超圖模型(2)超圖模型.例如,以圖頂點(diǎn)代表文章,每條邊代表兩個(gè)頂點(diǎn)(文章)享有同一個(gè)作者.現(xiàn)有3篇文章V1(作者A、B)、V2(作者A、C)、V3(作者A、D),3篇文章的作者都有A.圖1(a)表示了簡(jiǎn)單圖存儲(chǔ)模式,3條獨(dú)立的邊e1,e2,e3={v1,v2},{v1,v3},{v2,v3},無法直接保留作者A同時(shí)是3篇文章V1、V2、V3的作者這一信息.圖1(b)代表了超圖存儲(chǔ)模式,超邊e1={v1,v2,v3}直接保留了A是3篇文章V1、V2、V3的作者這一信息.對(duì)于具有復(fù)雜聯(lián)系的應(yīng)用,可以使用超圖模型建模,例如社交網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)等.Trinity等圖數(shù)據(jù)庫系統(tǒng)支持超圖模型來管理大規(guī)模圖數(shù)據(jù).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.2圖數(shù)據(jù)的存儲(chǔ)方式在目前的大規(guī)模圖數(shù)據(jù)管理應(yīng)用中主要采用簡(jiǎn)單圖和超圖兩種數(shù)據(jù)模型二者的組織存儲(chǔ)格式略有不同.這兩種模型都可以處理有向圖和無向圖，默認(rèn)情況是有向圖，而無向圖中的邊可以看作是兩條有向邊，即有向圖的一種.在之后的討論中不再強(qiáng)調(diào)圖中邊的方向.簡(jiǎn)單圖模型的常用存儲(chǔ)結(jié)構(gòu)包括鄰接矩陣、鄰接表、十字鏈表和鄰接多重表等多種方式.從大規(guī)模圖處理的應(yīng)用需求和維護(hù)的復(fù)雜程度考慮,鄰接矩陣和鄰接表是最常用的兩種結(jié)構(gòu).采用鄰接矩陣表示圖的拓?fù)浣Y(jié)構(gòu),直觀簡(jiǎn)潔,便于快速查找頂點(diǎn)之間的關(guān)系,但是鄰接矩陣的存儲(chǔ)代價(jià)高昂,對(duì)于大規(guī)模圖數(shù)據(jù),這個(gè)問題尤為嚴(yán)重.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.2圖數(shù)據(jù)的存儲(chǔ)方式GBASE系統(tǒng)以鄰接矩陣的形式組織存儲(chǔ)圖,考慮到鄰接矩陣的存儲(chǔ)開銷,GBASE對(duì)矩陣進(jìn)行了聚簇分割,盡量將矩陣中的非零值集中存儲(chǔ)并采用Zip技術(shù)壓縮編碼,減少矩陣的存儲(chǔ)代價(jià).與鄰接矩陣相比,鄰接表的應(yīng)用范圍更加廣泛.像PageRank計(jì)算、最短路徑計(jì)算等應(yīng)用,并不需要頻繁查找兩個(gè)圖頂點(diǎn)之間的連通性,鄰接表完全可以滿足計(jì)算需求.鄰接表的存儲(chǔ)開銷小,邏輯簡(jiǎn)單,便于分割處理,是一種比較理想的圖組織方式,Pregel、Hama和HaLoop等系統(tǒng)均采用鄰接表的形式組織圖數(shù)據(jù).超圖模型的組織方式主要使用關(guān)系矩陣.從形式上講,關(guān)系矩陣和鄰接矩陣較為相似,但是矩陣的行和列分別表示圖頂點(diǎn)編號(hào)和超邊的編號(hào).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.2圖數(shù)據(jù)的存儲(chǔ)方式大規(guī)模的圖數(shù)據(jù)存儲(chǔ)需要依賴云計(jì)算環(huán)境的分布式存儲(chǔ)系統(tǒng).云計(jì)算環(huán)境的存儲(chǔ)系統(tǒng)分為兩種:一種是以GFS、HDFS為代表的分布式文件系統(tǒng),對(duì)于鄰接矩陣、鄰接表等結(jié)構(gòu),可以直接存放;另一種是以BigTable、Hbase為代表的NoSQL(NotOnlySQL)分布式數(shù)據(jù)庫.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.2圖數(shù)據(jù)的存儲(chǔ)方式NoSQL數(shù)據(jù)庫采用的數(shù)據(jù)模型主要有文檔存儲(chǔ)(DocumentStore)模型、列族存儲(chǔ)(ColumnFamilyStore)模型、Key-Value存儲(chǔ)模型、圖存儲(chǔ)模型等幾大類.文檔存儲(chǔ)模型在存儲(chǔ)格式方面十分靈活,比較適合存儲(chǔ)系統(tǒng)日志等非結(jié)構(gòu)化數(shù)據(jù),CouchDB和MongoDB是采用這種存儲(chǔ)模型的典型系統(tǒng).但是,文檔存儲(chǔ)模型不太適合以鄰接矩陣或鄰接表組織的圖數(shù)據(jù).此外,文檔存儲(chǔ)模型為支持靈活性所導(dǎo)致的處理效率的降低也會(huì)成為大規(guī)模圖數(shù)據(jù)管理的性能瓶頸.列族存儲(chǔ)模型比較適合對(duì)某一列進(jìn)行隨機(jī)查詢處理,但是對(duì)于窮舉式遍歷,反而不如傳統(tǒng)的面向行的存儲(chǔ)模式.采用該存儲(chǔ)模型的典型系統(tǒng)有BigTable、Hbase、Cassandra等.圖存儲(chǔ)模型的相關(guān)研究目前還不完善,只有少數(shù)分布式圖數(shù)據(jù)庫,如Neo4j等采用這種模型存儲(chǔ)圖數(shù)據(jù).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.2圖數(shù)據(jù)的存儲(chǔ)方式與上述3種存儲(chǔ)模型相比,Key-Value存儲(chǔ)模型較為適合存儲(chǔ)大規(guī)模圖數(shù)據(jù).Key-Value存儲(chǔ)模型的存儲(chǔ)模式簡(jiǎn)單,支持海量數(shù)據(jù)存儲(chǔ)和高并發(fā)查詢操作,非常適合通過主鍵進(jìn)行查詢或遍歷,但對(duì)復(fù)雜的條件查詢支持度不佳.采用該模型的典型系統(tǒng)有Dynamo和SimpleDB.從圖處理的角度出發(fā),像PageRank計(jì)算等,并不需要復(fù)雜查詢,Key-Value模型完全可以勝任.若圖數(shù)據(jù)采用鄰接表組織,可以將圖的源頂點(diǎn)作為Key,將源頂點(diǎn)值、出邊及邊信息作為Value.文獻(xiàn)[21]結(jié)合語義Web和傳統(tǒng)的Key-Value存儲(chǔ)模型,提出Key-Key-Value存儲(chǔ)模型.以社交網(wǎng)絡(luò)為例,Key-Key-Value模型將Alice和Bob之間的好友關(guān)系組織為一個(gè)三元組<Alice,Bob,FriendShip>.該模型存儲(chǔ)的信息比傳統(tǒng)的Key-Value模型更加豐富,可以據(jù)此進(jìn)行數(shù)據(jù)遷移和合并,以提高空間局部性,使得在查詢處理時(shí)能減少遠(yuǎn)程讀取數(shù)據(jù)的次數(shù),因而可以提高數(shù)據(jù)讀取效率.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.2圖數(shù)據(jù)的存儲(chǔ)方式此外,對(duì)于分布式圖數(shù)據(jù)庫,當(dāng)圖數(shù)據(jù)更新時(shí),需要提供事務(wù)功能,解決在分布式環(huán)境下的一致性控制問題.HyperGraphDB和Trinity等人都宣稱自己支持事務(wù)機(jī)制和一致性控制.如果圖數(shù)據(jù)存儲(chǔ)在HDFS類型的分布式文件系統(tǒng)上,因其不支持更新和隨機(jī)插入操作,也就不存在一致性維護(hù)問題.前面討論了NoSQL數(shù)據(jù)庫的4種主要存儲(chǔ)模型.文獻(xiàn)[23]從管理數(shù)據(jù)的規(guī)模和模型的復(fù)雜性兩個(gè)維度比較了這4種基本存儲(chǔ)模型,見圖2.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.3圖數(shù)據(jù)的索引結(jié)構(gòu)索引是傳統(tǒng)關(guān)系數(shù)據(jù)庫中的關(guān)鍵技術(shù),包括B+樹索引、Hash索引、位圖索引等,技術(shù)較為成熟,可以提高數(shù)據(jù)查詢處理效率,尤其是在查詢結(jié)果的數(shù)據(jù)量遠(yuǎn)小于原始數(shù)據(jù)的情況下.對(duì)于一個(gè)大規(guī)模圖,云計(jì)算的分布式并行處理機(jī)制,可以根據(jù)查詢條件遍歷所有的子圖數(shù)據(jù),如果查詢結(jié)果的數(shù)據(jù)量較大,這種處理方式的性能是比較好的,但是如果查詢結(jié)果的數(shù)量很小,則會(huì)訪問很多無用的數(shù)據(jù),造成計(jì)算資源的浪費(fèi)和查詢效率的低下,而通過建立合適的索引,可以有效解決這一問題.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.3圖數(shù)據(jù)的索引結(jié)構(gòu)目前用于云計(jì)算環(huán)境下的索引技術(shù),很少有專門針對(duì)圖數(shù)據(jù)的.但是,這些索引技術(shù)大都是可以被圖數(shù)據(jù)存儲(chǔ)所利用.目前的云環(huán)境下用于數(shù)據(jù)管理的索引結(jié)構(gòu)可以分為適用于P2P網(wǎng)絡(luò)結(jié)構(gòu)的索引以及適用于Shared-nothing集群結(jié)構(gòu)的索引.文獻(xiàn)[24]針對(duì)云計(jì)算環(huán)境下的大規(guī)模數(shù)據(jù)查詢處理,提出了二級(jí)索引技術(shù)CG-index.它首先在每一個(gè)數(shù)據(jù)分片上建立本地B+tree形成索引分片,后將計(jì)算節(jié)點(diǎn)組織成Overlay結(jié)構(gòu),接下來基于Overlay的路由協(xié)議把各個(gè)計(jì)算節(jié)點(diǎn)上B+tree分片發(fā)布到Overlay上,建立全局索引CG-index.這種索引具有自適應(yīng)性和可擴(kuò)展性.文獻(xiàn)[25]建立了多維索引機(jī)制RT-CAN,集成CAN協(xié)議和R樹的特點(diǎn),在云計(jì)算環(huán)境下提供高效查詢服務(wù).文獻(xiàn)[26]也針對(duì)P2P環(huán)境,在分布式KD-tree基礎(chǔ)上提出多維索引MIDAS,用以支持多維查詢、范圍查詢和k最近鄰查詢等應(yīng)用.文獻(xiàn)[27]提出了一個(gè)通用的、靈活的、容錯(cuò)的、且可擴(kuò)展的分布式B-tree索引結(jié)構(gòu).文獻(xiàn)[28]將R-tree和KD-tree結(jié)合起來組織數(shù)據(jù)記錄,提出了用于云數(shù)據(jù)管理的多維索引EMINC,可以提供快速的查詢處理和有效的索引維護(hù).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.3圖數(shù)據(jù)的索引結(jié)構(gòu)云計(jì)算環(huán)境下的通用索引機(jī)制,沒有考慮圖結(jié)構(gòu)的特點(diǎn),在圖查詢處理方面,效果不明顯.而分布式圖數(shù)據(jù)庫,無論是數(shù)據(jù)存儲(chǔ)還是索引結(jié)構(gòu),都針對(duì)圖數(shù)據(jù)進(jìn)行了優(yōu)化.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.3圖數(shù)據(jù)的索引結(jié)構(gòu)Neo4j的索引分為兩類:數(shù)據(jù)庫本身就是一個(gè)樹形結(jié)構(gòu)的索引,可用于提高查詢效率,此外,還可以使用獨(dú)立的Lucene索引,提供全文索引和索引命中率排序功能.Neo4j可以對(duì)圖頂點(diǎn)和邊分別建立索引,通過對(duì)索引的緩存,可進(jìn)一步加快查找速度.索引的維護(hù)操作(如刪除、更新)則必須在事務(wù)管理機(jī)制下進(jìn)行.對(duì)于更新,必須先刪除舊的索引值,然后才能添加新索引值,代價(jià)較高.InfiniteGraph與Neo4j類似,也提供內(nèi)建索引和Lucene索引.在HyperGraph-DB的兩層存儲(chǔ)架構(gòu)中,索引是存儲(chǔ)層必備的組成部分,一個(gè)Key可對(duì)應(yīng)多個(gè)已排序的Value,并支持Value共享;在模型層,Key采用UUID編號(hào)并排序,在Key上建立索引.索引文件以B-tree格式存儲(chǔ)并具有緩存功能,可以為查詢等操作提供持久化的元數(shù)據(jù)信息.Trinity數(shù)據(jù)庫提供Trie樹和Hash兩種索引結(jié)構(gòu)來訪問圖頂點(diǎn)、邊的名字以及相關(guān)的其它信息,可減少有公共前綴的字符串的匹配次數(shù).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)2.3圖數(shù)據(jù)的索引結(jié)構(gòu)支持圖計(jì)算處理的索引,主要是在云計(jì)算平臺(tái)中體現(xiàn).文獻(xiàn)[30]針對(duì)Hadoop系統(tǒng)中的Shuffle過程和Reduce過程進(jìn)行了改進(jìn),采用動(dòng)態(tài)增量式Hash索引和緩存技術(shù)降低Shuffle過程的磁盤IO代價(jià),提高CPU利用率.HaLoop則對(duì)Map任務(wù)的輸入、Reduce任務(wù)的輸入和輸出進(jìn)行緩存并建立索引,在一定程度上提高了Hadoop迭代處理的效率.文獻(xiàn)[31]針對(duì)MapReduce的連接操作,提出Trojan索引技術(shù),通過對(duì)分片信息和Key值的重新構(gòu)造,建立索引,使需要連接的數(shù)據(jù)位于同一個(gè)分片上,減少連接操作的網(wǎng)絡(luò)通信量.由于MapReduce模型是一個(gè)通用計(jì)算模型,Hadoop處理平臺(tái)的索引也是通用性的,對(duì)于大規(guī)模圖的迭代處理的針對(duì)性并不強(qiáng).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)目錄1.引言2.圖數(shù)據(jù)模型與存儲(chǔ)管理5.圖數(shù)據(jù)處理的執(zhí)行機(jī)制4.圖計(jì)算模型與典型系統(tǒng)結(jié)構(gòu)3.圖數(shù)據(jù)的分割策略6.圖查詢處理7.結(jié)束語云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)3.圖數(shù)據(jù)發(fā)分割策略云計(jì)算環(huán)境下的通用索引機(jī)制,沒有考慮圖結(jié)構(gòu)的特點(diǎn),在圖查詢處理方面,效果不明顯.而分布式圖數(shù)據(jù)庫,無論是數(shù)據(jù)存儲(chǔ)還是索引結(jié)構(gòu),都針對(duì)圖數(shù)據(jù)進(jìn)行了優(yōu)化.在云計(jì)算環(huán)境下,對(duì)于一個(gè)大規(guī)模圖的處理,必須進(jìn)行分布式并行處理.由于圖數(shù)據(jù)本身固有的連通性和圖計(jì)算表現(xiàn)出強(qiáng)耦合性的特點(diǎn),為了實(shí)現(xiàn)高效的并行處理,盡可能降低分布式處理的各子圖之間的耦合度是非常重要的.有效的圖分割就是實(shí)現(xiàn)解耦的重要手段.這首先要將一個(gè)邏輯上完整的大圖分割成若干部分,分別放置到分布式存儲(chǔ)系統(tǒng)的各工作節(jié)點(diǎn)上.其后對(duì)圖的處理,就是針對(duì)已經(jīng)分布式存放的每一個(gè)子圖,啟動(dòng)一個(gè)計(jì)算任務(wù),進(jìn)行相同的處理操作,當(dāng)所有子圖處理結(jié)束,則完成整個(gè)大圖的一次處理了.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)3.1圖分割策略在云計(jì)算環(huán)境下,實(shí)現(xiàn)大圖分割并取得較好的分割效果,是一項(xiàng)挑戰(zhàn)性很大的工作.將一個(gè)大圖分割為若干子圖,有兩個(gè)主要原則:一是提高子圖內(nèi)部的連通性,降低子圖之間的連通性,這種特點(diǎn)尤其適合云計(jì)算的分布式并行處理機(jī)制;二是考慮子圖規(guī)模的均衡性,盡量保證各子圖的數(shù)據(jù)規(guī)模均衡,不要出現(xiàn)較大的偏斜,從數(shù)據(jù)規(guī)模方面防止各并行任務(wù)的執(zhí)行時(shí)間相差過大,降低任務(wù)同步控制過程中“水桶效應(yīng)”的影響.當(dāng)然,大圖分割的時(shí)間復(fù)雜度必須控制在可以忍受的范圍內(nèi).圖3對(duì)比了3種不同的圖分割效果,如果單純考慮子圖的數(shù)據(jù)均衡或子圖之間的連通性,其效果均不理想,只有同時(shí)考慮著兩個(gè)因素,才能顯著提高分布并行式處理效率.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)3.2單指標(biāo)分割技術(shù)如果只考慮數(shù)據(jù)負(fù)載均衡這一單項(xiàng)指標(biāo)最簡(jiǎn)單的圖分割技術(shù)就是Hash方式，即在設(shè)定了分片數(shù)目之后對(duì)圖頂點(diǎn)ID進(jìn)行Hash將數(shù)據(jù)劃分成給定數(shù)目的分片.這種分割方法效率很高時(shí)間復(fù)雜度為O(n)，可以在圖數(shù)據(jù)的載入過程中或圖處理之前完成分片操作.在一定條件下設(shè)計(jì)良好的Hash方式可以避免數(shù)據(jù)偏斜使各子圖的數(shù)據(jù)規(guī)模接近相同.但是Hash方式?jīng)]有考慮圖數(shù)據(jù)的局部性甚至連原始數(shù)據(jù)的局部性也無法得到保留.Hash方式雖然在云計(jì)算環(huán)境下容易實(shí)現(xiàn)但是負(fù)責(zé)各子圖處理的任務(wù)之間消息通信頻繁會(huì)造成較大的網(wǎng)絡(luò)通信開銷.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)3.2單指標(biāo)分割技術(shù)如果只考慮子圖內(nèi)斂性這一單項(xiàng)指標(biāo),即增大子圖內(nèi)部的關(guān)聯(lián)性,降低子圖之間的關(guān)聯(lián)性,可采用聚類技術(shù),效果十分明顯.關(guān)于在云計(jì)算環(huán)境下實(shí)現(xiàn)分布式聚類的方法,在Apache開源項(xiàng)目Mahout中有詳細(xì)介紹.但是,聚類操作一般都是一個(gè)迭代處理的過程,時(shí)間開銷不容忽視.另外,聚類技術(shù)一般不考慮各聚簇之間的數(shù)據(jù)規(guī)模偏斜問題,很可能導(dǎo)致分割后的各子圖的數(shù)據(jù)規(guī)模相差較大,增大了圖處理過程中的?水桶效應(yīng)?.在改善子圖分割的時(shí)間復(fù)雜度方面,Yahoo研究院發(fā)現(xiàn),即便圖數(shù)據(jù)的原始規(guī)模很大,最終得到的聚簇仍然要小得多.基于這一發(fā)現(xiàn),Yahoo研究院開發(fā)出?LocalPartition?算法,該算法的運(yùn)行時(shí)間與最終輸出結(jié)果的聚簇大小成正比,而與圖的原始輸入數(shù)據(jù)規(guī)模無關(guān),從而可以對(duì)更大規(guī)模的圖進(jìn)行分割處理.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)3.2單指標(biāo)分割技術(shù)此外,還有很多研究者從其它方面對(duì)分布式環(huán)境下的圖分割技術(shù)進(jìn)行了探索.文獻(xiàn)[35]采用隨機(jī)森林(SF)方法,進(jìn)行圖分割.文獻(xiàn)[36]提出確定性和非確定性的分布式圖分割算法SyncPart、Fast_Part和Elect_Part.文獻(xiàn)[37]在使用Hadoop進(jìn)行圖的迭代處理時(shí),通過設(shè)置Partitioner函數(shù)來不斷調(diào)整圖的分布.將一個(gè)Reduce任務(wù)處理的圖數(shù)據(jù)視為一個(gè)子圖,通過Map階段和Reduce階段的Shuffle處理,使連通性較強(qiáng)的圖頂點(diǎn)分布到同一個(gè)Reduce任務(wù)并作為輸出結(jié)果存儲(chǔ)為一個(gè)單獨(dú)的文件,在下一個(gè)Map階段中加以利用,以減少通信量.以PageRank應(yīng)用為例,可以針對(duì)頂點(diǎn)URL的內(nèi)容,設(shè)計(jì)Hash函數(shù),使得關(guān)聯(lián)較大的圖頂點(diǎn)能夠分配到同一個(gè)Reduce任務(wù)中.后兩種方法雖然實(shí)現(xiàn)了子圖之間的有效解耦,但由于子圖的個(gè)數(shù)不確定和大小不均勻,導(dǎo)致并行處理的負(fù)載不平衡.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)3.3多指標(biāo)分割技術(shù)同時(shí)考慮子圖數(shù)據(jù)規(guī)模均衡和子圖內(nèi)斂性等多項(xiàng)指標(biāo),也有很多研究者進(jìn)行了嘗試.文獻(xiàn)[38]針對(duì)分布式P2P網(wǎng)絡(luò),提出了一種基于圖頂點(diǎn)度序列和廣度優(yōu)先搜索的k-圖分割技術(shù),能夠?qū)⒁粋€(gè)大型P2P網(wǎng)絡(luò)分割成k個(gè)子網(wǎng)絡(luò)并且能夠做到各子網(wǎng)絡(luò)的任務(wù)負(fù)載均衡.文獻(xiàn)[39]通過3步處理來實(shí)現(xiàn)大規(guī)模圖的分割:(1)建立帶權(quán)重的深度優(yōu)先搜索樹;(2)將大圖分割成若干個(gè)均衡的子圖;(3)迭代處理,盡量減少子圖之間的關(guān)聯(lián).GBASE系統(tǒng)利用現(xiàn)有的METIS、Disco等劃分算法,對(duì)存儲(chǔ)圖數(shù)據(jù)的鄰接矩陣進(jìn)行聚類,將行和列重新排序,把一個(gè)大矩陣聚集為多個(gè)均勻區(qū)域,形成分塊,保證塊內(nèi)的子圖聯(lián)系緊密,塊間聯(lián)系松散,將若干個(gè)塊作為一個(gè)網(wǎng)格,分給一個(gè)任務(wù)進(jìn)行處理,在一定程度上解決了數(shù)據(jù)均衡問題.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)3.3多指標(biāo)分割技術(shù)同時(shí)考慮子圖數(shù)據(jù)規(guī)模均衡和子圖內(nèi)斂性等多項(xiàng)指標(biāo),也有很多研究者進(jìn)行了嘗試.文獻(xiàn)[38]針對(duì)分布式P2P網(wǎng)絡(luò),提出了一種基于圖頂點(diǎn)度序列和廣度優(yōu)先搜索的k-圖分割技術(shù),能夠?qū)⒁粋€(gè)大型P2P網(wǎng)絡(luò)分割成k個(gè)子網(wǎng)絡(luò)并且能夠做到各子網(wǎng)絡(luò)的任務(wù)負(fù)載均衡.文獻(xiàn)[39]通過3步處理來實(shí)現(xiàn)大規(guī)模圖的分割:(1)建立帶權(quán)重的深度優(yōu)先搜索樹;(2)將大圖分割成若干個(gè)均衡的子圖;(3)迭代處理,盡量減少子圖之間的關(guān)聯(lián).GBASE系統(tǒng)利用現(xiàn)有的METIS、Disco等劃分算法,對(duì)存儲(chǔ)圖數(shù)據(jù)的鄰接矩陣進(jìn)行聚類,將行和列重新排序,把一個(gè)大矩陣聚集為多個(gè)均勻區(qū)域,形成分塊,保證塊內(nèi)的子圖聯(lián)系緊密,塊間聯(lián)系松散,將若干個(gè)塊作為一個(gè)網(wǎng)格,分給一個(gè)任務(wù)進(jìn)行處理,在一定程度上解決了數(shù)據(jù)均衡問題.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)3.3多指標(biāo)分割技術(shù)

云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)3.3多指標(biāo)分割技術(shù)此外,Horton系統(tǒng)中提出,對(duì)于需要長(zhǎng)期存儲(chǔ)的圖數(shù)據(jù)采用靜態(tài)處理和動(dòng)態(tài)處理相結(jié)合的技術(shù)實(shí)現(xiàn)圖分割.在圖數(shù)據(jù)載入分布式存儲(chǔ)系統(tǒng)的過程中采用靜態(tài)處理方法使用EvolvingSets技術(shù)將大圖分割存儲(chǔ).新的圖數(shù)據(jù)加入或更新時(shí)采用動(dòng)態(tài)方法使用基于消息通信的Affinitypropagation算法對(duì)已有的子圖進(jìn)行增量式分割和維護(hù).這種分割技術(shù)既能降低子圖計(jì)算之間的耦合性又能保證負(fù)載平衡.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)目錄1.引言2.圖數(shù)據(jù)模型與存儲(chǔ)管理5.圖數(shù)據(jù)處理的執(zhí)行機(jī)制4.圖計(jì)算模型與典型系統(tǒng)結(jié)構(gòu)3.圖數(shù)據(jù)的分割策略6.圖查詢處理7.結(jié)束語云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.圖計(jì)算模型與典型系統(tǒng)結(jié)構(gòu)本節(jié)介紹典型的云計(jì)算環(huán)境下大規(guī)模圖數(shù)據(jù)處理的計(jì)算模型和一些典型的圖處理系統(tǒng).計(jì)算模型決定了分布式并行執(zhí)行方式是進(jìn)行解耦處理和提高可靠性的基礎(chǔ).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.1MapReduce模型和BSP模型在云計(jì)算環(huán)境中,最廣泛使用的就是MapReduce模型.一個(gè)并行處理作業(yè)由多個(gè)map任務(wù)和多個(gè)reduce任務(wù)組成.作業(yè)的執(zhí)行分為Map階段和Reduce階段：在Map階段,每個(gè)map任務(wù)對(duì)分配給它的數(shù)據(jù)(通常是本地的數(shù)據(jù))進(jìn)行計(jì)算,然后按照map的輸出key值將結(jié)果數(shù)據(jù)映射到對(duì)應(yīng)的reduce任務(wù)中;在Reduce階段,每個(gè)reduce任務(wù)對(duì)接收到的數(shù)據(jù)做進(jìn)一步聚集處理,得到輸出結(jié)果.數(shù)據(jù)通常保存在分布式文件系統(tǒng)中,如HDFS.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.1MapReduce模型和BSP模型BSP(BulkSynchronousParallelmodel)模型是2010年圖靈獎(jiǎng)得主Valiant在1990年提出來的一種基于消息通信的并行執(zhí)行模型.一個(gè)BSP作業(yè)由若干個(gè)順序執(zhí)行的超步(superstep)組成:S1,S2,…,Sn,對(duì)應(yīng)于n次迭代處理.并行任務(wù)按照超步組織,在超步Si內(nèi),各任務(wù)異步接受來自Si-1的消息,執(zhí)行本地計(jì)算并發(fā)送消息給下一個(gè)超步Si+1.在超步之間,通過顯式地同步控制,確保所有任務(wù)均已完成超步Si的工作.這種同步方式可避免死鎖和數(shù)據(jù)競(jìng)爭(zhēng)問題.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.1MapReduce模型和BSP模型在云環(huán)境下實(shí)現(xiàn)大規(guī)模圖的處理,主要采用這兩種模型,下面將對(duì)比它們?cè)趫D處理方面的特點(diǎn).在執(zhí)行機(jī)制方面；MapReduce是一個(gè)數(shù)據(jù)流模型,每個(gè)任務(wù)只是對(duì)輸入數(shù)據(jù)進(jìn)行處理,產(chǎn)生的輸出數(shù)據(jù)作為另一個(gè)任務(wù)的輸入數(shù)據(jù),并行任務(wù)之間獨(dú)立地進(jìn)行,串行任務(wù)之間以磁盤和數(shù)據(jù)復(fù)制作為交換介質(zhì)和接口.而BSP是一個(gè)狀態(tài)模型,各個(gè)子任務(wù)在本地的子圖數(shù)據(jù)上進(jìn)行計(jì)算、通信、修改圖的狀態(tài)等操作.并行任務(wù)之間通過消息通信交流中間計(jì)算結(jié)果,不需要像MapReduce那樣對(duì)全體數(shù)據(jù)進(jìn)行復(fù)制.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.1MapReduce模型和BSP模型在云環(huán)境下實(shí)現(xiàn)大規(guī)模圖的處理,主要采用這兩種模型,下面將對(duì)比它們?cè)趫D處理方面的特點(diǎn).在執(zhí)行機(jī)制方面；在迭代處理方面；MapReduce模型理論上需要連續(xù)啟動(dòng)若干作業(yè)才可以完成圖的迭代處理,相鄰作業(yè)之間通過分布式文件系統(tǒng)交換全部數(shù)據(jù).BSP模型僅需啟動(dòng)一個(gè)作業(yè),利用多個(gè)超步就可以完成迭代處理,兩次迭代之間通過消息傳遞中間計(jì)算結(jié)果.由于減少了作業(yè)啟動(dòng)、調(diào)度開銷和磁盤存取開銷,BSP模型的迭代執(zhí)行效率較高.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)在云環(huán)境下實(shí)現(xiàn)大規(guī)模圖的處理,主要采用這兩種模型,下面將對(duì)比它們?cè)趫D處理方面的特點(diǎn).在執(zhí)行機(jī)制方面；在迭代處理方面；在數(shù)據(jù)分割方面；基于BSP的圖處理模型,需要對(duì)加載后的圖數(shù)據(jù)進(jìn)行一次再分布的過程,以確定消息通信時(shí)的路由地址.例如,各任務(wù)并行加載數(shù)據(jù)過程中,根據(jù)一定的映射策略,將讀入的數(shù)據(jù)重新分發(fā)到對(duì)應(yīng)的計(jì)算任務(wù)上(通常是存放在內(nèi)存中),既有磁盤IO又有網(wǎng)絡(luò)通信,開銷很大.但是一個(gè)BSP作業(yè)僅需一次數(shù)據(jù)分割,在之后的迭代計(jì)算過程中除了消息通信之外,不再需要進(jìn)行數(shù)據(jù)的遷移.而基于MapReduce的圖處理模型,一般情況下,不需要專門的數(shù)據(jù)分割處理，但是Map階段和educe階段存在中間結(jié)果的Shuffle過程,增加了磁盤IO和網(wǎng)絡(luò)通信開銷.4.1MapReduce模型和BSP模型云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.1MapReduce模型和BSP模型MapReduce模型的商業(yè)化應(yīng)用已經(jīng)開始推廣,其良好的可伸縮性和容錯(cuò)管理能力受到了業(yè)界推崇,在大規(guī)模數(shù)據(jù)處理方面的表現(xiàn)也值得稱贊.但是作為通用計(jì)算模型,在圖處理方面,連續(xù)的作業(yè)調(diào)度和任務(wù)分配,代價(jià)較高,對(duì)于圖拓?fù)浣Y(jié)構(gòu)信息的反復(fù)磁盤讀取,尤其是從分布式文件系統(tǒng)上讀取,也增大了IO開銷.此外,在迭代處理方面,需要用戶編程控制,較為繁瑣.相對(duì)而言,BSP模型是一個(gè)比較適合迭代處理的計(jì)算模型,為用戶提供了簡(jiǎn)單易用的編程接口,Google的Pregel、Yahoo!的Giraph和開源的Hama系統(tǒng),都是基于BSP模型開發(fā)的.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.1MapReduce模型和BSP模型從原理上講,BSP模型避免了MapReduce模型在多次迭代時(shí)的數(shù)據(jù)反復(fù)遷移和作業(yè)連續(xù)調(diào)度,其特有的超步和全局同步機(jī)制,使迭代處理的控制更加靈活,在大規(guī)模圖處理方面很有開發(fā)前景.但目前上述系統(tǒng)還處于研究開發(fā)階段,所處理的數(shù)據(jù)放置于內(nèi)存,未考慮索引問題,數(shù)據(jù)處理規(guī)模也受到極大的制約,需要進(jìn)一步開發(fā)基于磁盤的系統(tǒng)并對(duì)I/O操作進(jìn)行優(yōu)化.此外,BSP模型中各任務(wù)之間的消息通信也是難以消除的效率瓶頸,而在容錯(cuò)管理等方面,尚無完善的理論和方法.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.2典型系統(tǒng)結(jié)構(gòu)目前,關(guān)于云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)管理系統(tǒng),大致可以分為3類:基于MapReduce模型的分布式并行處理系統(tǒng)、基于BSP模型的分布式并行處理系統(tǒng)和分布式圖數(shù)據(jù)庫系統(tǒng).基于MapReduce模型的分布式并行處理系統(tǒng),大部分是通用處理平臺(tái),如Hadoop以及改進(jìn)版本HOP系統(tǒng),可以應(yīng)用于各種大規(guī)模數(shù)據(jù)處理,為了適應(yīng)需要多次迭代的圖處理應(yīng)用,很多研究者對(duì)Hadoop原有處理平臺(tái)進(jìn)行了優(yōu)化改進(jìn),如HaLoop、Twister、Prlter、HaLoop使用緩存、索引技術(shù)來減少不必要的磁盤IO,改進(jìn)原有的任務(wù)調(diào)度模塊使連續(xù)作業(yè)的調(diào)度和迭代條件的控制變得較為容易,具備一定的實(shí)用價(jià)值.Twister系統(tǒng)對(duì)Hadoop進(jìn)行了較大的改動(dòng),全部處理數(shù)據(jù)駐留內(nèi)存,采用第3方消息通信機(jī)制,使用任務(wù)池來避免多次作業(yè)調(diào)度.但是駐留內(nèi)存的限制使其難以實(shí)用,目前只是供研究使用.Prlter是在Hadoop和HOP基礎(chǔ)上開發(fā)的,支持帶優(yōu)先級(jí)的迭代計(jì)算,可以確保迭代處理的快速收斂,尤其適合在線查詢,如top-k查詢.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.2典型系統(tǒng)結(jié)構(gòu)基于BSP模型的分布式并行處理系統(tǒng),最著名的就是Google提出的Pregel平臺(tái).Pregel對(duì)于圖的分割、計(jì)算處理、消息通信優(yōu)化、同步控制和容錯(cuò)管理都提出了可行的解決方案,是目前較為完善的專門針對(duì)大規(guī)模圖處理應(yīng)用的系統(tǒng).Hadoop的開發(fā)商Yahoo提出了開源項(xiàng)目Giraph.Giraph可以視為在Hadoop平臺(tái)上運(yùn)行的一個(gè)大規(guī)模圖算法庫,在原有MapReduce模型基礎(chǔ)上,只啟動(dòng)map任務(wù),在map任務(wù)里面參考Pregel的設(shè)計(jì),嵌套了BSP模型,實(shí)現(xiàn)多次循環(huán)迭代,以支持大規(guī)模圖處理應(yīng)用.開源項(xiàng)目Hama同Pregel一樣,也是一個(gè)獨(dú)立的分布式并行處理系統(tǒng),適合需要多次迭代的圖處理.但是Hama目前很不完善,尚無可穩(wěn)定運(yùn)行的發(fā)布版本.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.2典型系統(tǒng)結(jié)構(gòu)無論是MapReduce模型還是BSP模型,上述提及的處理平臺(tái)都是分布式并行處理系統(tǒng),它們的優(yōu)勢(shì)是完成復(fù)雜的圖處理任務(wù),如PageRank計(jì)算、最短路徑查詢、社交網(wǎng)絡(luò)分析和圖挖掘等,但是對(duì)于圖數(shù)據(jù)的一般性存儲(chǔ)、更新維護(hù)等,則不如分布式圖數(shù)據(jù)庫系統(tǒng).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.2典型系統(tǒng)結(jié)構(gòu)分布式圖數(shù)據(jù)庫系統(tǒng)集數(shù)據(jù)存儲(chǔ)、維護(hù)、查詢于一體,繼承了傳統(tǒng)數(shù)據(jù)庫的事務(wù)、一致性控制等特點(diǎn),有的甚至支持較為復(fù)雜的管理.HyperGraphDB是一種基于Key-Value模型的分布式P2P數(shù)據(jù)庫,采用超圖作為數(shù)據(jù)模型,利用UUID技術(shù)在分布式環(huán)境下實(shí)現(xiàn)Key編號(hào)的唯一,支持海量圖數(shù)據(jù)的高速存儲(chǔ);在查詢方面,依靠索引的幫助支持快速圖遍歷和集合查詢,而基于SPARQL語言的模式查詢正在開發(fā)中.Trinity是微軟研究院開發(fā)的基于內(nèi)存的分布式圖數(shù)據(jù)庫系統(tǒng),該系統(tǒng)采用超圖作為數(shù)據(jù)模型,支持滿足ACI特性的事務(wù)機(jī)制、一致性控制和索引,能滿足高并發(fā)查詢請(qǐng)求.Trinity提供良好的圖分割算法,以減少查詢時(shí)的網(wǎng)絡(luò)延遲,支持同步、異步兩種模式的批處理計(jì)算.其它著名的分布式圖數(shù)據(jù)庫系統(tǒng)還有Neo4j和InfiniteGraph等.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)4.2典型系統(tǒng)結(jié)構(gòu)此外,也有很多研究團(tuán)隊(duì)開發(fā)了自己獨(dú)特的圖處理平臺(tái)和圖管理系統(tǒng).如微軟針對(duì)云計(jì)算環(huán)境開發(fā)的Dryad、DryadLINQ分布式執(zhí)行引擎,提供完善的輸入輸出、任務(wù)調(diào)度、容錯(cuò)管理機(jī)制,支持SQL查詢;Orleans處理平臺(tái)支持異步消息通信和索引,采用新的消息機(jī)制,避免RPC通信的應(yīng)答阻塞,采用隨機(jī)分配方法實(shí)現(xiàn)負(fù)載均衡,支持任務(wù)遷移;Horton則支持對(duì)大規(guī)模圖的在線查詢優(yōu)化，GBASE系統(tǒng)是一個(gè)可伸縮的通用圖數(shù)據(jù)管理系統(tǒng),具有完整的圖數(shù)據(jù)分塊、壓縮、索引和存儲(chǔ)機(jī)制以及一系列能夠支撐復(fù)雜圖挖掘應(yīng)用的原語操作.GBASE底層采用鄰接矩陣存儲(chǔ)圖數(shù)據(jù),所有的圖處理操作最終都轉(zhuǎn)化為Hadoop作業(yè)執(zhí)行.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)目錄1.引言2.圖數(shù)據(jù)模型與存儲(chǔ)管理5.圖數(shù)據(jù)處理的執(zhí)行機(jī)制4.圖計(jì)算模型與典型系統(tǒng)結(jié)構(gòu)3.圖數(shù)據(jù)的分割策略6.圖查詢處理7.結(jié)束語云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.圖數(shù)據(jù)處理的執(zhí)行機(jī)制本節(jié)介紹實(shí)現(xiàn)云計(jì)算環(huán)境下大規(guī)模圖數(shù)據(jù)處理的基本執(zhí)行機(jī)制,包括消息通信、同步控制、容錯(cuò)管理,并討論可伸縮性問題.其中消息通信和同步控制是針對(duì)圖計(jì)算強(qiáng)耦合性進(jìn)行優(yōu)化處理的重要內(nèi)容,容錯(cuò)管理旨在解決可靠性方面的挑戰(zhàn),可伸縮性是云計(jì)算靈活性的重要體現(xiàn).云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.1消息通信圖處理的消息,主要產(chǎn)生在圖頂點(diǎn)的計(jì)算過程中.但是消息發(fā)送方式,則可以根據(jù)不同的通信策略分為異步式和集中式.對(duì)于異步式通信；圖頂點(diǎn)的計(jì)算處理與消息通信并發(fā)執(zhí)行,在計(jì)算過程中就可以發(fā)送消息,將大規(guī)模消息的發(fā)送分散在不同的時(shí)間段,避免瞬時(shí)網(wǎng)絡(luò)通信阻塞,但是接收端需要額外空間,存儲(chǔ)臨時(shí)接收到的消息,相當(dāng)于用空間換取時(shí)間.目前,Pregel、HOP系統(tǒng)等采用異步通信方式.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.1消息通信圖處理的消息,主要產(chǎn)生在圖頂點(diǎn)的計(jì)算過程中.但是消息發(fā)送方式,則可以根據(jù)不同的通信策略分為異步式和集中式.對(duì)于異步式通信；對(duì)于集中式通信；圖頂點(diǎn)的計(jì)算處理與消息通信串行進(jìn)行,在計(jì)算完畢后,統(tǒng)一發(fā)送消息,控制和實(shí)現(xiàn)方式簡(jiǎn)單,可在發(fā)送端對(duì)消息進(jìn)行最大程度優(yōu)化,但容易造成瞬間的網(wǎng)絡(luò)通信阻塞以及增加發(fā)送端的消息存儲(chǔ)開銷云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.1消息通信鑒于大規(guī)模圖數(shù)據(jù)處理過程中的網(wǎng)絡(luò)通信瓶頸,需要對(duì)通信次數(shù)和通信的數(shù)據(jù)量加以優(yōu)化控制以降低耦合代價(jià).利用圖分割,可以降低子圖之間的連通性,使大部分消息的目的圖頂點(diǎn)均位于同一個(gè)任務(wù)的處理范圍中,將網(wǎng)絡(luò)通信變?yōu)楸镜赝ㄐ?從根本上減少任務(wù)之間的消息發(fā)送;針對(duì)具體應(yīng)用,采用消息合并機(jī)制,也可以減少網(wǎng)絡(luò)通信量和存儲(chǔ)量,如Pregel和Hadoop系統(tǒng);此外,通過消息緩存和批量發(fā)送機(jī)制,可以減少網(wǎng)絡(luò)通信的次數(shù),降低通信鏈接的維護(hù)開銷.至于消息通信的實(shí)現(xiàn)方式,Hadoop、Hama和Giraph等采用基于Http協(xié)議的RPC通信機(jī)制.作為Hadoop的改進(jìn)版本,Twister系統(tǒng)直接使用第3方消息通信管理插件來完成通信控制,Twister系統(tǒng)目前支持NaradaBroking和ActiveMQ等基于發(fā)布-訂閱架構(gòu)的通信插件.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.2同步控制同步控制是所有分布式計(jì)算處理框架都必須面對(duì)的問題,只不過有的框架顯式地提供同步控制,如采用BSP模型的Pregel系統(tǒng)、Hama系統(tǒng);有的處理框架提供隱式的同步過程,如采用MapReduce模型的Hadoop系統(tǒng),在Map階段和Reduce階段存在隱式的同步控制.如果使用MapReduce模型進(jìn)行大規(guī)模圖迭代處理,相鄰作業(yè)之間也存在同步控制的過程.在需要多次迭代的圖處理應(yīng)用中,同步控制還應(yīng)該提供圖中間狀態(tài)信息統(tǒng)計(jì)查詢功能和收斂條件判斷功能.同步控制的優(yōu)化可以減少圖計(jì)算強(qiáng)耦合性帶來的影響.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.2同步控制目前,同步控制的設(shè)計(jì)方案有兩種:主從式控制和分散式協(xié)同控制前者由主控節(jié)點(diǎn)統(tǒng)一協(xié)調(diào)各任務(wù)的同步,完成收斂條件判斷以及中間狀態(tài)信息統(tǒng)計(jì)查詢功能,便于集中管理,結(jié)構(gòu)清晰,可維護(hù)性好,不容易產(chǎn)生死鎖.但是當(dāng)數(shù)據(jù)量較大、任務(wù)數(shù)量很多時(shí),主控節(jié)點(diǎn)會(huì)成為處理瓶頸,多作業(yè)并發(fā)運(yùn)行以及圖處理應(yīng)用的多次迭代,更加劇了這種瓶頸效應(yīng)；后者的同步過程由各任務(wù)自己協(xié)調(diào),無主控節(jié)點(diǎn),避免了單點(diǎn)處理瓶頸,可伸縮性很好.但是不便于集中管理,一旦各任務(wù)開始運(yùn)行,就難以在迭代過程中加以人工控制,靈活性差.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.2同步控制在同步控制中,由于任務(wù)處理速度不一致,當(dāng)各任務(wù)負(fù)責(zé)處理的數(shù)據(jù)規(guī)?；驍?shù)據(jù)內(nèi)部的復(fù)雜程度不同時(shí),會(huì)導(dǎo)致任務(wù)處理速度相差很大,因此造成了水桶效應(yīng).為降低水桶效應(yīng),Hadoop系統(tǒng)采用“任務(wù)推測(cè)式執(zhí)行方式”,希望“糾正”執(zhí)行緩慢的任務(wù),降低Map階段和Reduce階段的水桶效應(yīng).文獻(xiàn)[30]提出動(dòng)態(tài)增量Hash技術(shù)來弱化Map階段和Reduce階段之間的同步,實(shí)現(xiàn)計(jì)算過程的部分重疊,減少Reduce任務(wù)等待時(shí)間.另外,在圖處理應(yīng)用中,傳統(tǒng)Hadoop平臺(tái)難以解決相鄰作業(yè)之間的水桶效應(yīng),HOP系統(tǒng)的“pipeline”技術(shù),可以在一定程度上緩解該問題.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.3容錯(cuò)管理在云計(jì)算領(lǐng)域,當(dāng)前容錯(cuò)管理的主流設(shè)計(jì)思想是通過硬盤讀寫和冗余備份來提供保障.容錯(cuò)管理需要考慮的內(nèi)容主要包括:冗余備份的寫入時(shí)機(jī)、冗余備份的存放位置、故障偵測(cè)、故障恢復(fù)等.其中故障的偵測(cè),目前均是采用“心跳”報(bào)告的方法完成.針對(duì)圖處理一般是多次迭代的特點(diǎn),備份的寫入時(shí)機(jī)應(yīng)該在兩次相鄰迭代之間,但這又提出了備份生成頻率的問題:迭代多少次進(jìn)行一次備份是合適的.較高的備份頻率會(huì)導(dǎo)致作業(yè)運(yùn)行速度緩慢,較低的備份頻率又會(huì)導(dǎo)致故障恢復(fù)時(shí)重復(fù)處理的代價(jià)增高.目前對(duì)于這個(gè)問題,并沒有定論.一種可能的解決方案是統(tǒng)計(jì)特定云計(jì)算節(jié)點(diǎn)的故障率,根據(jù)不同圖處理作業(yè)的迭代步數(shù)來動(dòng)態(tài)設(shè)定備份頻率.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.3容錯(cuò)管理借鑒HOP的容錯(cuò)思想,可以在一個(gè)map任務(wù)的中間增加備份同時(shí)記錄原始數(shù)據(jù)的處理偏移量,當(dāng)故障發(fā)生后,重啟的map任務(wù)直接從偏移量處開始計(jì)算.也可以在一次圖處理迭代過程中,設(shè)置中間備份并記錄處理偏移量,這可以減少故障恢復(fù)時(shí)的重復(fù)處理,提高恢復(fù)效率,但是增大了備份生成頻率和磁盤開銷,也增大了容錯(cuò)管理的復(fù)雜度.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.3容錯(cuò)管理故障恢復(fù)時(shí),如果各并行任務(wù)之間完全獨(dú)立,則重啟故障任務(wù)即可,Hadoop系統(tǒng)就采用這種恢復(fù)策略.在圖處理過程中,可以直接利用Hadoop系統(tǒng)自身的容錯(cuò)機(jī)制,但是由于Hadoop的容錯(cuò)是以MapReduce作業(yè)為單位,而一個(gè)迭代的圖處理作業(yè)一般需要多個(gè)MapReduce作業(yè),多個(gè)MapReduce作業(yè)間的容錯(cuò)管理就不是Hadoop所能解決的了,需要用戶自己編碼實(shí)現(xiàn),較為繁瑣.如果各并行任務(wù)之間耦合度很高,如基于BSP模型開發(fā)的Pregel系統(tǒng),就需要使所有任務(wù)回歸到同一個(gè)檢查點(diǎn).作為改進(jìn),Pregel提出“檢查點(diǎn)加消息記錄”的容錯(cuò)管理方案,將圖頂點(diǎn)狀態(tài)備份后,還需要將每個(gè)超步內(nèi)各任務(wù)間收發(fā)的消息寫入磁盤.在故障發(fā)生時(shí),僅需恢復(fù)故障任務(wù),不必全部回滾,減少因任務(wù)耦合度過高導(dǎo)致的高昂的恢復(fù)代價(jià),但是對(duì)消息的記錄增大了磁盤存儲(chǔ)開銷,在一定程度上也影響了作業(yè)的正常運(yùn)行效率.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.4可伸縮性云計(jì)算環(huán)境下的可伸縮性,應(yīng)該從兩個(gè)方面考慮:硬件方面,即動(dòng)態(tài)添加、刪除節(jié)點(diǎn)來實(shí)現(xiàn)云平臺(tái)處理能力的伸縮性;軟件方面,系統(tǒng)處理框架應(yīng)該盡量避免單點(diǎn)處理瓶頸.從硬件方面考慮,應(yīng)該允許在運(yùn)行期間,動(dòng)態(tài)添加物理機(jī)器以擴(kuò)充整個(gè)云計(jì)算平臺(tái)的可用資源.云計(jì)算平臺(tái)可用資源的伸縮性,一方面是指新提交的作業(yè)可以利用新添加的資源,其實(shí)現(xiàn)比較容易,不同云計(jì)算系統(tǒng)的實(shí)現(xiàn)方式較為統(tǒng)一,都是通過注冊(cè)方式將新機(jī)器添加到可用工作節(jié)點(diǎn)集合;另一方面也包括正在運(yùn)行的作業(yè)可以利用新添加的資源,不同的處理框架對(duì)其實(shí)現(xiàn)方式是不同的,而且對(duì)于大規(guī)模圖處理應(yīng)用,更有意義.假設(shè)目前正在運(yùn)行一個(gè)大規(guī)模圖處理作業(yè),由于云平臺(tái)處理資源的限制導(dǎo)致運(yùn)行緩慢,此時(shí)考慮動(dòng)態(tài)添加一批工作節(jié)點(diǎn),如果正在運(yùn)行的作業(yè)能夠利用新添加的計(jì)算資源,就可以加快處理速度.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.4可伸縮性云計(jì)算環(huán)境下的可伸縮性,應(yīng)該從兩個(gè)方面考慮:硬件方面,即動(dòng)態(tài)添加、刪除節(jié)點(diǎn)來實(shí)現(xiàn)云平臺(tái)處理能力的伸縮性;軟件方面,系統(tǒng)處理框架應(yīng)該盡量避免單點(diǎn)處理瓶頸.從數(shù)據(jù)存儲(chǔ)能力方面考慮,基于BSP模型的圖處理框架,具有較高的內(nèi)存資源要求,最理想方法是將所有的圖數(shù)據(jù)都駐留在內(nèi)存中,這樣不需要進(jìn)行內(nèi)外存交換,否則計(jì)算速度將顯著下降.但這提高了對(duì)硬件配置的要求,在一定程度上也制約了數(shù)據(jù)處理的規(guī)模.基于MapReduce的圖數(shù)據(jù)處理系統(tǒng),只要計(jì)算的中間結(jié)果能夠存儲(chǔ)在磁盤上,系統(tǒng)就可以運(yùn)行,而對(duì)節(jié)點(diǎn)的配置沒有過高的要求.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)5.4可伸縮性從理論上講,云計(jì)算環(huán)境的伸縮能力應(yīng)該是沒有上限的,即加入的物理機(jī)器越多,平臺(tái)中可用資源越多,處理性能越好.但是,從實(shí)際來看,并不是這樣的.以Hadoop為例,Yahoo發(fā)現(xiàn),當(dāng)計(jì)算節(jié)點(diǎn)的規(guī)模達(dá)到4000臺(tái)時(shí),Hadoop系統(tǒng)遭遇到伸縮性壁壘,新加入的計(jì)算資源不能被云平臺(tái)充分利用.造成這種問題的根源,是由于目前的云計(jì)算環(huán)境主要依賴于主從式控制模式,存在單點(diǎn)處理瓶頸,當(dāng)整個(gè)云平臺(tái)規(guī)模過大,主控節(jié)點(diǎn)的處理能力成為提高系統(tǒng)性能的制約瓶頸.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)目錄1.引言2.圖數(shù)據(jù)模型與存儲(chǔ)管理5.圖數(shù)據(jù)處理的執(zhí)行機(jī)制4.圖計(jì)算模型與典型系統(tǒng)結(jié)構(gòu)3.圖數(shù)據(jù)的分割策略6.圖查詢處理7.結(jié)束語云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)6.圖查詢處理圖數(shù)據(jù)管理的最終目的是支持查詢處理,這里的查詢是指廣義的查詢,既包括簡(jiǎn)單的查詢,如好友關(guān)系查詢,也包括復(fù)雜的圖計(jì)算和圖挖掘,如PageRank計(jì)算、社交網(wǎng)絡(luò)分析等.從查詢語義的角度考慮,將大規(guī)模圖查詢分為兩大類:一類是基本的圖查詢計(jì)算,如特定圖頂點(diǎn)或邊的查詢、好友關(guān)系查詢等;另一類是復(fù)雜查詢計(jì)算與圖挖掘,如RWR(RandomWalkwithRestart)計(jì)算、子圖挖掘等.對(duì)于一個(gè)大規(guī)模圖,由于數(shù)據(jù)的海量性,必須考慮查詢處理的效率,采用云計(jì)算環(huán)境作為處理平臺(tái),就是希望利用分布式并行處理機(jī)制提高效率.此外,還可以根據(jù)不同類型的查詢,設(shè)計(jì)有針對(duì)性的查詢優(yōu)化策略,本節(jié)將圍繞查詢語義,著重介紹兩類圖查詢處理的研究進(jìn)展.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)圖的簡(jiǎn)單查詢,一般不需要多次迭代,用戶可以對(duì)大規(guī)模圖進(jìn)行查找,查詢自己感興趣的信息.查找過程中,對(duì)于某些應(yīng)用,通過建立合適的索引、調(diào)整查詢順序和查詢復(fù)用等技術(shù),可以避免對(duì)整個(gè)圖頂點(diǎn)的遍歷,有效提高查找效率.從所處理的查詢請(qǐng)求和優(yōu)化技術(shù)方面考慮,此類圖查詢類似于普通的數(shù)據(jù)庫查詢.傳統(tǒng)集中式數(shù)據(jù)庫系統(tǒng),不僅為用戶提供了良好的SQL查詢語言接口,還通過索引組織和查詢優(yōu)化,提供高效的查詢服務(wù).云計(jì)算環(huán)境下,對(duì)于大規(guī)模圖的簡(jiǎn)單查詢,在考慮分布式環(huán)境和圖結(jié)構(gòu)特點(diǎn)的同時(shí),也應(yīng)該盡量提供類似的功能.6.1基本的圖查詢計(jì)算云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)6.1基本的圖查詢計(jì)算Horton是微軟正在設(shè)計(jì)的一款專門針對(duì)大規(guī)模圖數(shù)據(jù)提供高效在線查詢服務(wù)的系統(tǒng).Horton為減少查詢時(shí)的網(wǎng)絡(luò)通信代價(jià),對(duì)圖數(shù)據(jù)進(jìn)行專門分割,以提高局部性.從查詢語言和處理機(jī)制方面,Horton將用戶的具體查詢請(qǐng)求分解為若干原語,采用有限自動(dòng)機(jī)方法,確定底層的廣度優(yōu)先搜索的執(zhí)行順序.至于查詢優(yōu)化方面,在具體應(yīng)用中,如好友關(guān)系和照片關(guān)注關(guān)系,研究發(fā)現(xiàn),以不同的順序執(zhí)行有限自動(dòng)機(jī),查詢代價(jià)相差很大.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)6.1基本的圖查詢計(jì)算云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)6.1基本的圖查詢計(jì)算對(duì)于圖應(yīng)用中的基本計(jì)算,Pregel、Giraph和Hama等系統(tǒng)或圖算法庫,有較大的發(fā)展前景,它們均具備一定的通用性.目前,基于Pregel和Giraph圖計(jì)算處理,需要用戶重寫系統(tǒng)提供的圖頂點(diǎn)基類來表達(dá)自己的查詢處理請(qǐng)求.對(duì)于具體的圖計(jì)算應(yīng)用,可以進(jìn)行針對(duì)性的優(yōu)化,獲得較好的性能指標(biāo).以最短路徑計(jì)算為例,可以利用預(yù)計(jì)算的索引來加快響應(yīng)時(shí)間.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)6.2復(fù)雜查詢與圖挖掘相比于基本圖計(jì)算,復(fù)雜圖計(jì)算與挖掘?qū)儆诟呒?jí)圖處理應(yīng)用,如模式匹配、RWR計(jì)算等.Pregel系統(tǒng)給出了對(duì)于BipartiteMatching和Semi-Clustering算法的BSP模型實(shí)現(xiàn)方式[5].PEGASUS算法庫提供了大量基于Hadoop的圖挖掘算法.PEGASUS系統(tǒng)使用GIM-V(GeneralizedIterativeMatrixVectormultiplication)原語算子,將圖挖掘的迭代處理過程轉(zhuǎn)換為圖鄰接矩陣的迭代相乘.目前比較通用的圖查詢處理系統(tǒng),主要