基于內(nèi)存計(jì)算的大規(guī)模圖數(shù)據(jù)管理研究

袁培森， 舒 欣， 沙朝鋒， 徐煥良

（1.南京農(nóng)業(yè)大學(xué) 信息科技學(xué)院，南京 210095；2.復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海 200433）

0 引 言

圖數(shù)據(jù)是一類重要的數(shù)據(jù)，可以描述豐富的信息及信息之間的依賴關(guān)系，是一種經(jīng)典的數(shù)據(jù)建模工具，在社交網(wǎng)絡(luò)、Web數(shù)據(jù)超鏈接、交通網(wǎng)絡(luò)等方面被廣泛應(yīng)用.這些應(yīng)用中的圖包含了百萬(wàn)和億萬(wàn)級(jí)別的頂點(diǎn)和邊，如截至2014年第一季度Facebook包含了12.3億個(gè)活躍用戶，每個(gè)用戶平均好友130個(gè)；Web鏈接圖頂點(diǎn)數(shù)達(dá)到T級(jí)，邊的個(gè)數(shù)達(dá)到P級(jí).同時(shí)，圖數(shù)據(jù)分析與處理技術(shù)在機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘中具有重要應(yīng)用，例如信念傳播算法［1］、隨機(jī)優(yōu)化［2］等.鑒于圖建模的靈活性和應(yīng)用廣泛性，大規(guī)模圖數(shù)據(jù)的存儲(chǔ)和分析處理技術(shù)成為近年來(lái)數(shù)據(jù)庫(kù)等領(lǐng)域的研究熱點(diǎn)，尤其是分布式集群計(jì)算的廣泛應(yīng)用，研究者提出了在集群上處理大規(guī)模圖數(shù)據(jù)存儲(chǔ)和分析處理技術(shù)［3－7］.

分布式集群為海量數(shù)據(jù)處理提供了技術(shù)和平臺(tái)，也給大規(guī)模圖數(shù)據(jù)管理帶來(lái)機(jī)遇.大規(guī)模圖數(shù)據(jù)在分布式集群上處理涉及的關(guān)鍵技術(shù)：① 圖數(shù)據(jù)劃分（partition），需要將大規(guī)模的圖分割為相互獨(dú)立的部分，進(jìn)而根據(jù)一定的數(shù)據(jù)分布算法存儲(chǔ)到集群節(jié)點(diǎn)上；② 計(jì)算模型，圖中的信息存儲(chǔ)在頂點(diǎn)或者邊上，然而由于圖數(shù)據(jù)的結(jié)構(gòu)性質(zhì)，數(shù)據(jù)之間存在依賴關(guān)系，圖的計(jì)算模型一般涉及多次迭代，數(shù)據(jù)狀態(tài)更新需要通過(guò)消息通信或者數(shù)據(jù)流.圖的劃分是圖數(shù)據(jù)管理的關(guān)鍵步驟，不僅與數(shù)據(jù)存儲(chǔ)與數(shù)據(jù)均衡、負(fù)載均衡有關(guān)，還與計(jì)算節(jié)點(diǎn)間通信與數(shù)據(jù)移動(dòng)量有關(guān)；同時(shí)計(jì)算模型關(guān)系到計(jì)算表達(dá)能力和粒度.

現(xiàn)有集群技術(shù)在處理大規(guī)模圖數(shù)據(jù)時(shí)，其性能、計(jì)算表達(dá)能力等方面存在不足：首先，MapReduce［8］計(jì)算模式適合批式處理無(wú)依賴關(guān)系的數(shù)據(jù)，然而圖的數(shù)據(jù)元素之間的存在依賴關(guān)系，難于表達(dá)圖之間計(jì)算依賴關(guān)系.第二，圖的大部分算法需要多次迭代才能收斂，此外迭代過(guò)程產(chǎn)生大量的中間結(jié)果，需要在計(jì)算節(jié)點(diǎn)之間消息結(jié)果和移動(dòng)數(shù)據(jù).文獻(xiàn)［9］指出圖數(shù)據(jù)計(jì)算過(guò)程需要多次隨機(jī)訪問(wèn)數(shù)據(jù)，是典型的I／O密集型計(jì)算.第三，此外，圖中的遍歷計(jì)算需在整個(gè)圖上進(jìn)行，數(shù)據(jù)訪問(wèn)缺少局部性，對(duì)性能優(yōu)化帶來(lái)了限制.最后，對(duì)實(shí)時(shí)性要求不能滿足，而大量的應(yīng)用需要實(shí)時(shí)的獲得分析的結(jié)果.例如社交網(wǎng)絡(luò)中好友關(guān)系分析、推薦系統(tǒng)等.以上幾個(gè)方面對(duì)直接使用現(xiàn)有集群管理大規(guī)模圖數(shù)據(jù)提出了挑戰(zhàn).

近年來(lái)，內(nèi)存的容量根據(jù)摩爾定律在發(fā)展，同時(shí)價(jià)格在大幅地下降，可以使得單機(jī)內(nèi)存容量高達(dá)TB級(jí)，為海量數(shù)據(jù)的放入內(nèi)存帶來(lái)了可能.最近，研究者提出的內(nèi)存計(jì)算（In－Memory Computing，IMC）作為提升數(shù)據(jù)分析效率的有效技術(shù)發(fā)展迅速.基于內(nèi)存計(jì)算避免了I／O瓶頸，成為海量數(shù)據(jù)分析的利器，主要應(yīng)用在BI、ERP、數(shù)據(jù)倉(cāng)庫(kù)等方面［28］.典型的基于內(nèi)存計(jì)算技術(shù)的數(shù)據(jù)分析產(chǎn)品為SAP的HANA［10］.目前，內(nèi)存計(jì)算的研究已成為數(shù)據(jù)庫(kù)等領(lǐng)域關(guān)注的主題之一［7，11］，對(duì)于大規(guī)模圖數(shù)據(jù)，研究者提出了在多核單機(jī)環(huán)境下和在分布式內(nèi)存集群下大規(guī)模圖數(shù)據(jù)管理的技術(shù).

本文在大規(guī)模圖數(shù)據(jù)管理需求和內(nèi)存計(jì)算大發(fā)展背景下，研究了大規(guī)模圖數(shù)據(jù)并行計(jì)算的編程模式、計(jì)算策略、圖劃分策略及計(jì)算同步等問(wèn)題，接著介紹了內(nèi)存計(jì)算相關(guān)的概念、設(shè)計(jì)理念和產(chǎn)品.主要介紹了基于內(nèi)存計(jì)算機(jī)制的圖數(shù)據(jù)管理進(jìn)展和典型的系統(tǒng)，總結(jié)了基于內(nèi)存計(jì)算的大規(guī)模圖處理的關(guān)鍵，最后對(duì)本文進(jìn)行了總結(jié).

1 圖數(shù)據(jù)管理

1.1 圖數(shù)據(jù)表示

一般把圖建模為二元關(guān)系模型，G＝（V，E），V＝｛v1，...vn｝為圖G的非空頂點(diǎn)集合，E＝｛〈vi，vj〉｝?V×V為由頂點(diǎn)集合構(gòu)成的邊的集合，如果邊集合為頂點(diǎn)構(gòu)成的有序?qū)?，稱為有向圖，否則稱為無(wú)向圖.通常在構(gòu)造圖的過(guò)程中，圖的頂點(diǎn)和邊可以附帶一些屬性，例如權(quán)重、用戶信息等.文獻(xiàn)［12］把圖數(shù)據(jù)附帶的屬性考慮進(jìn)去，提出了帶屬性圖（property graph），定義為GP＝（V，E，P），其中P＝（PV，PE），PV和PE分別為圖G 的頂點(diǎn)和邊所附帶的屬性.

1.2 計(jì)算框架

圖數(shù)據(jù)的分布式并行計(jì)算一般分為三個(gè)步驟：① 圖劃分，② 圖數(shù)據(jù)分布與計(jì)算，③ 最終結(jié)果產(chǎn)生.大規(guī)模圖數(shù)據(jù)研究框架見(jiàn)圖1所示.

圖1 大規(guī)模圖數(shù)據(jù)處理框架圖Fig.1 Framework of processing on massive graph management

對(duì)于海量的圖數(shù)據(jù)，首先是對(duì)圖根據(jù)一定的規(guī)則進(jìn)行劃分，把圖數(shù)據(jù)劃分為若干個(gè)不相交的部分，進(jìn)而把數(shù)據(jù)分布到集群上的計(jì)算節(jié)點(diǎn).典型的圖分割算法包括：基于邊的切割（p－way edge－cut）、基于頂點(diǎn)的切割（p－way vertex－cut）、基于隨機(jī)的哈希方法和啟發(fā)式的劃分等.圖的劃分質(zhì)量對(duì)工作負(fù)載均衡、計(jì)算節(jié)點(diǎn)通信、存儲(chǔ)和計(jì)算效率都有著極大影響.

第二步，將劃分后的數(shù)據(jù)分布到計(jì)算節(jié)點(diǎn)上進(jìn)行分布式存儲(chǔ)和并行計(jì)算處理.該步驟是圖計(jì)算的核心，從邏輯上可以劃分為三層：最上層的應(yīng)用、中間的模型、底層物理層.

應(yīng)用層的應(yīng)用從實(shí)時(shí)性可以劃分為在線查詢和離線分析.在線查詢實(shí)時(shí)查詢，一般無(wú)法預(yù)測(cè)查詢與圖結(jié)構(gòu)的關(guān)系，而離線分析數(shù)據(jù)訪問(wèn)模式是可以預(yù)測(cè).從計(jì)算方法分三大類圖計(jì)算：① 圖的遍歷，例如最短路徑、連通分量計(jì)算等；② 隨機(jī)行走，例如PageRank［13］，HITS［14］等；③ 圖聚集計(jì)算，例如圖概要［15］、圖粗化［16］等.

中間層是圖計(jì)算模型層，該層次是圖的計(jì)算策略，包括三種策略：① 以頂點(diǎn)為中心的策略（Vertex－centric）；② 以邊為中心的策略（Edge－centric）；③ 以圖為中心的策略（Graphcentric）.

底層為物理層，包括計(jì)算同步策略，數(shù)據(jù)存儲(chǔ)方式、編程框架和容錯(cuò)機(jī)制等.同步策略包括BSP（Bulk Synchronous Parallel）同步［4］、異步［17］和異步混合模式［3，17］等.存儲(chǔ)方法包括分布式文件、key－value方式存儲(chǔ)、數(shù)組、BigTable等.

最后是計(jì)算最終分析結(jié)果.

2 圖的計(jì)算

2.1 圖的編程模式

根據(jù)圖的結(jié)構(gòu)性質(zhì)，圖的并行分布式計(jì)算基于以下兩點(diǎn)：① 應(yīng)用的數(shù)據(jù)及狀態(tài)更新是在頂點(diǎn)或邊上的迭代計(jì)算，計(jì)算直到計(jì)算狀態(tài)收斂到一個(gè)固定點(diǎn)；② 計(jì)算的每一次迭代可以在圖的頂點(diǎn)層面或邊上并行獨(dú)立進(jìn)行.計(jì)算中間結(jié)果擴(kuò)展和聚集方法的不同可以把編程模式分為SG和SAG兩種策略.

SG（scatter－gather）模式［22］，該模式分為兩個(gè)階段：①scatter階段發(fā)送狀態(tài)信息到頂點(diǎn)的鄰接點(diǎn)與邊；②gather階段應(yīng)用更新信息到頂點(diǎn)上.

SAG模式［3］，該模式分為三個(gè)階段：Gather、Apply和Scatter.Gather階段收集計(jì)算鄰接點(diǎn)與邊的信息，Apply階段將Gather階段計(jì)算的結(jié)果應(yīng)用于頂點(diǎn)，Scatter階段使用Apply階段的更新值更新頂點(diǎn)的鄰接邊.

圖2所示展示了兩種編程模式數(shù)據(jù)更新的過(guò)程.圖2（a）中的SG模式，首先頂點(diǎn)u通過(guò)scatter把更新數(shù)據(jù)傳遞給鄰接點(diǎn)v，接著頂點(diǎn)u獲取以它為目標(biāo)節(jié)點(diǎn)的更新.圖2（b）的GAS模式中，頂Gather階段獲得點(diǎn)u、邊u→v和鄰接點(diǎn)v的值的計(jì)算結(jié)果，Apply階段把該結(jié)果應(yīng)用于頂點(diǎn)u，scatter階段把頂點(diǎn)u的值更新到相應(yīng)的邊上.

圖2 圖的SG和GAS編程模式Fig.2 SG and GAS program model of graph

2.2 圖的計(jì)算策略

圖數(shù)據(jù)的計(jì)算包括兩部分：圖的頂點(diǎn)計(jì)算和圖的邊計(jì)算.根據(jù)對(duì)圖的處理視角的不同，可以把計(jì)算模型劃分為三種：以頂點(diǎn)為中心、以邊為中心的和以圖為中心.三種計(jì)算模型的表達(dá)能力和計(jì)算能力不同，各有優(yōu)缺點(diǎn).

為了形式描述圖上的運(yùn)算，把圖數(shù)據(jù)的計(jì)算問(wèn)題形式定義為PX＝｛G，Q｝，其中X代表圖G的元素，可為圖的頂點(diǎn)、邊或子圖，Q（X）為計(jì)算在圖G的元素X上的運(yùn)算.例如X為頂點(diǎn)時(shí)，Q（X）可以表示頂點(diǎn)上的PageRank計(jì)算.

（1）頂點(diǎn)為中心.以頂點(diǎn)為中心的圖計(jì)算表示為PV＝｛G，Q｝，其中Q（V）在G中頂點(diǎn)集合V上運(yùn)行的算法或者應(yīng)用.該模型把圖數(shù)據(jù)的頂點(diǎn)作為處理對(duì)象，采用SG編程模型，利用圖的邊傳遞信息，PV的計(jì)算通過(guò)頂點(diǎn)與鄰接點(diǎn)之間的邊通信，進(jìn)而在鄰接點(diǎn)之間傳遞計(jì)算和狀態(tài)信息.該模型的特點(diǎn)是scatter和gather都在圖的頂點(diǎn)上進(jìn)行迭代.

頂點(diǎn)為中心實(shí)際上是把頂點(diǎn)作為獨(dú)立的計(jì)算代理節(jié)點(diǎn)，計(jì)算代理節(jié)點(diǎn)相互獨(dú)立地執(zhí)行計(jì)算和通信任務(wù).不同的PV相互獨(dú)立，要求滿足交換律和結(jié)合律，因此其執(zhí)行順序互不影響.頂點(diǎn)為中心的計(jì)算模型可以解決諸如圖挖掘，PageRank計(jì)算等典型的圖數(shù)據(jù)計(jì)算問(wèn)題.

（2）以邊為中心.以邊為中心的圖計(jì)算問(wèn)題表示為PE＝｛G，Q｝，其中Q（E）在圖G的邊集合E上的算法.該方式同樣在圖的頂點(diǎn)中保存計(jì)算狀態(tài)信息，并把計(jì)算分為scatter和gather階段，每個(gè)階段的頂點(diǎn)通過(guò)邊進(jìn)行更新?tīng)顟B(tài).以邊為中心與以頂點(diǎn)為中心的計(jì)算過(guò)程如表1所示.

表1 以頂點(diǎn)為中心和以邊為中心的計(jì)算策略Tab.1 Evaluations of vertex－centric and edge－centric strategies

（3）以圖為中心.以圖為中心的圖計(jì)算問(wèn)題表示為PSG＝｛G，Q｝，其中Q（SG）在G中子圖SG上運(yùn)行的算法或者應(yīng)用.

以圖為中心模型把頂點(diǎn)集劃分為不相交的子集，子圖由頂點(diǎn)、頂點(diǎn)鏈出的頂點(diǎn)以及邊構(gòu)成，每個(gè)子圖構(gòu)成一個(gè)劃分.該模型計(jì)算和同步的粒度為子圖.以圖為中心的模型把子圖中的頂點(diǎn)分為兩類：內(nèi)部（internal）頂點(diǎn)和邊界（boundary）頂點(diǎn).同時(shí)每個(gè)頂點(diǎn)數(shù)據(jù)維護(hù)兩個(gè)拷貝，其中內(nèi)部頂點(diǎn)的數(shù)據(jù)為主拷貝，邊界頂點(diǎn)的數(shù)據(jù)為本地拷貝.把頂點(diǎn)分為主拷貝和本地拷貝該模型是與頂點(diǎn)為中心的計(jì)算模型的重要區(qū)別［18］.內(nèi)部頂點(diǎn)是構(gòu)成子圖的核心，內(nèi)部頂點(diǎn)之間交換信息代價(jià)較小，但是邊界頂點(diǎn)交換信息或改變狀態(tài)需要在在節(jié)點(diǎn)之間消息傳遞，代價(jià)較大.表2對(duì)比了三種計(jì)算策略的優(yōu)缺點(diǎn).

表2 三種計(jì)算策略的優(yōu)缺點(diǎn)對(duì)比Tab.2 The comparison of three evaluation strategies

2.3 圖的并行策略

集群平臺(tái)的圖計(jì)算的并行典型策略有兩種：一種不考慮數(shù)據(jù)依賴關(guān)系，稱為數(shù)據(jù)并行（Data－parallel）；另一種是考慮圖元素之間的依賴關(guān)系，根據(jù)依賴關(guān)系迭代計(jì)算和通信，稱為圖并行（Graph－parallel）.

數(shù)據(jù)并行是把圖數(shù)據(jù)作為相互獨(dú)立的部分并行處理，通過(guò)把圖數(shù)據(jù)劃分為獨(dú)立的部分，分布到集群各節(jié)點(diǎn)，在不同的分布節(jié)點(diǎn)上獨(dú)立計(jì)算.典型的為Spark［7］，該類系統(tǒng)的優(yōu)點(diǎn)是在分布節(jié)點(diǎn)上對(duì)數(shù)據(jù)在計(jì)算節(jié)點(diǎn)間的移動(dòng)不做限制，擴(kuò)展性好.但是由于圖分析迭代計(jì)算的性質(zhì)，對(duì)數(shù)據(jù)并行系統(tǒng)提出了挑戰(zhàn)，例如圖結(jié)構(gòu)、數(shù)據(jù)Join導(dǎo)致數(shù)據(jù)移動(dòng)代價(jià)較高.典型的操作為 map，reduce，filter，join等.

圖并行策略是把根據(jù)圖分割算法把圖劃分為具有依賴關(guān)系的部分，在具有依賴關(guān)系的數(shù)據(jù)上進(jìn)行迭代并行計(jì)算，依賴部分的計(jì)算是通過(guò)在鄰居節(jié)點(diǎn)迭代以及節(jié)點(diǎn)間的通信完成的.在該并行策略下，典型的計(jì)算策略是以頂點(diǎn)為中心的計(jì)算.該方法大幅提升了圖并行處理的性能.典型的系統(tǒng)為Power Graph［3－5］.但是該類型系統(tǒng)的計(jì)算表達(dá)能力不強(qiáng)，例如圖構(gòu)造、圖結(jié)構(gòu)更新、多圖合并計(jì)算等.兩種并行策略的對(duì)比如表3所示.

以上兩種并行策略各有優(yōu)缺點(diǎn)，通過(guò)兩者的結(jié)合，在圖數(shù)據(jù)加載階段采用數(shù)據(jù)并行，而在圖數(shù)據(jù)分析階段采用圖并行，利用二者的優(yōu)點(diǎn).典型的系統(tǒng)為GraphX［6］.

表3 數(shù)據(jù)并行和圖并行兩種策略Tab.3 Two strategies of data－parallel and graph－parallel

2.4 圖劃分

圖劃分是大規(guī)模圖數(shù)據(jù)計(jì)算的重要操作，典型的圖分割算法包括隨機(jī)劃分、基于邊的平衡劃分、基于頂點(diǎn)的平衡劃分和啟發(fā)式劃分［6］、流劃分、譜劃分（Spectral Partitioning）［35］等.文獻(xiàn)［19］研究了經(jīng)典的圖劃分方法.

（1）基于邊的切割是沿著圖的邊劃分，把頂點(diǎn)均勻地分布到p個(gè)計(jì)算節(jié)點(diǎn)，最小化邊在計(jì)算節(jié)點(diǎn)的跨越.該方法要求每一個(gè)割邊需要多個(gè)計(jì)算節(jié)點(diǎn)上保留復(fù)制和通信，以保持圖之間的結(jié)構(gòu)依賴關(guān)系.

（2）基于頂點(diǎn)的切割沿著中心頂點(diǎn)劃分，把邊均勻地分布到p個(gè)計(jì)算節(jié)點(diǎn)，該方法可以最小化存儲(chǔ)可通信開(kāi)銷.GraphX［6］系統(tǒng)采用該方式對(duì)圖進(jìn)行分割.圖3顯示了這兩種切割.

圖3 邊和頂點(diǎn)切割［6］Fig.3 Edge－cut and vertex－cut［6］

（3）基于隨機(jī)的哈希方法對(duì)圖的每個(gè)頂點(diǎn)指定一個(gè)ID，通過(guò)使用hash（ID）modp把頂點(diǎn)均勻分布到p個(gè)結(jié)算節(jié)點(diǎn).隨機(jī)劃分方法能夠快速、方便實(shí)現(xiàn)，且數(shù)據(jù)分布均衡［4－5］，但由于沒(méi)有考慮圖的結(jié)構(gòu)性質(zhì)，導(dǎo)致計(jì)算節(jié)點(diǎn)間通信開(kāi)銷較高，收斂速度較慢.

（4）啟發(fā)式的劃分以最小化數(shù)據(jù)復(fù)制為目標(biāo)函數(shù)，找出劃分的規(guī)則，根據(jù)規(guī)則確定每一條邊的存儲(chǔ)節(jié)點(diǎn)［3］.

圖劃分的質(zhì)量對(duì)在工作負(fù)載均衡、計(jì)算節(jié)點(diǎn)通信、存儲(chǔ)和計(jì)算效率等都有極大影響.優(yōu)化劃分的原則是：減少邊跨越劃分的個(gè)數(shù)，減少計(jì)算節(jié)點(diǎn)之間的通信，加快計(jì)算收斂速度.圖分割的難點(diǎn)在于真實(shí)世界的圖一般符合冪率分布，這對(duì)分布式的工作平衡帶來(lái)挑戰(zhàn)，使得圖難于均勻分割［3］；第二，基于Hash的圖節(jié)點(diǎn)劃分技術(shù)導(dǎo)致數(shù)據(jù)局部性非常差；第三，不平衡數(shù)據(jù)的分布導(dǎo)致計(jì)算節(jié)點(diǎn)間大量的通信開(kāi)銷；第四，度數(shù)高的節(jié)點(diǎn)對(duì)計(jì)算和存儲(chǔ)的擴(kuò)展性帶來(lái)挑戰(zhàn).此外，過(guò)于復(fù)雜的分割帶來(lái)的計(jì)算開(kāi)銷也是必須要考慮的一個(gè)重要因素，基于哈希的分割簡(jiǎn)單易于實(shí)現(xiàn)，代價(jià)較小，應(yīng)用也比較廣泛［4－5］.

2.5 圖處理的同步策略

由于圖結(jié)構(gòu)依賴性導(dǎo)致其計(jì)算往往需要多次迭代，復(fù)雜性的結(jié)構(gòu)使得達(dá)到穩(wěn)定點(diǎn)計(jì)算步驟不同，需要在計(jì)算步之間進(jìn)行控制.常見(jiàn)的同步方式有：同步計(jì)算、異步計(jì)算和混合方式.其中BSP（Bulk Synchronous Parallel）［20］是最常用的同步模型.

BSP把計(jì)算劃分為計(jì)算步（superstep），模型采用異步計(jì)算同步迭代，每一個(gè)計(jì)算步的計(jì)算并行運(yùn)行，在下一個(gè)計(jì)算步發(fā)起之前，需要等待前一個(gè)計(jì)算步的計(jì)算全部完成.每個(gè)計(jì)算步可分為三個(gè)階段：本地計(jì)算、通信和柵欄同步.具體如圖4所示.

本地計(jì)算時(shí)各計(jì)算節(jié)點(diǎn)的數(shù)據(jù)駐留內(nèi)存，各結(jié)算節(jié)點(diǎn)相互獨(dú)立；通信是在進(jìn)程間通過(guò)put和get操作交換數(shù)據(jù)；柵欄同步等待所有進(jìn)程計(jì)算通信完畢.采用BSP同步計(jì)算結(jié)束的條件是消息處理完畢且所有計(jì)算投票表示停止.使用BSP的系統(tǒng)典型有Power Graph［3］，Pregel［4］和 Graphx系統(tǒng)［6］等.

BSP同步處理確保計(jì)算的確定性和最大化并行性，用戶易于設(shè)計(jì)，編程，測(cè)試和部署，并且具有良好的擴(kuò)展性和加速比.但是由于每個(gè)計(jì)算步的運(yùn)算時(shí)間不同，最慢的計(jì)算將嚴(yán)重影響整體收斂速度，例如PageRank、最短路徑的計(jì)算［5］.

為了最大化并行計(jì)算的效率，研究者提出了異步處理.異步處理模式的優(yōu)勢(shì)在于可以通過(guò)計(jì)算的順序智能排序，加速計(jì)算的收斂速度，但是異步處理模式編程復(fù)雜，不便于調(diào)試和測(cè)試，不能保證更新一致性，結(jié)果是不確定的，并發(fā)和隔離需要用戶控制.典型的有GraphLab［5］系統(tǒng).

為了兼具BSP同步簡(jiǎn)便性和異步的高效性，GRACE［17］把計(jì)算策略和應(yīng)用邏輯區(qū)分開(kāi)來(lái)，提出了圖編程模型的同步迭代，在BSP運(yùn)行時(shí)中兼容用戶內(nèi)建的異步計(jì)算運(yùn)行.此外，文獻(xiàn)［3］提出了異步串行化模式.

圖4 BSP處理模型Fig.4 Processing model of BSP

2.6 圖處理的容錯(cuò)機(jī)制

集群上的圖數(shù)據(jù)計(jì)算需要穩(wěn)定可靠的處理環(huán)境，系統(tǒng)容錯(cuò)至關(guān)重要，尤其是內(nèi)存計(jì)算環(huán)境下內(nèi)存數(shù)據(jù)的易失性.典型的容錯(cuò)機(jī)制包括：分布式檢測(cè)點(diǎn)機(jī)制［3－5］；分布式文件備份［27］等.

圖的分布式檢測(cè)點(diǎn)機(jī)制通過(guò)存儲(chǔ)快照到磁盤(pán)或者SSD，包括頂點(diǎn)、邊的值、消息等.在故障時(shí)通過(guò)使用最近的快照快速恢復(fù)，采用BSP同步機(jī)制的系統(tǒng)一般采用檢測(cè)點(diǎn)機(jī)制容錯(cuò)［3－4，27］.快照分為同步快照和異步快照.同步快照在建立的時(shí)候需要暫停所有的計(jì)算，清空消息并把所有的修改寫(xiě)到持久存儲(chǔ)上.異步快照通過(guò)增量式構(gòu)建而不需要暫停計(jì)算.GraphLab［5］支持同步快照和異步快照.

對(duì)于核心的數(shù)據(jù)，可以采用分布式文件備份，例如文獻(xiàn)［27］把共享地址表在集群的文件系統(tǒng)中保留備份，地址表的更新提交之前首先要寫(xiě)入文件系統(tǒng)的備份中.

3 內(nèi)存計(jì)算

3.1 內(nèi)存計(jì)算的興起

內(nèi)存計(jì)算以其快速響應(yīng)成為目前海量數(shù)據(jù)快速分析計(jì)算的利器.內(nèi)存容量的增加與價(jià)格的下降，以及硬件技術(shù)的成熟使得內(nèi)存計(jì)算成為現(xiàn)實(shí).目前T、P級(jí)別的內(nèi)存已經(jīng)應(yīng)用在數(shù)據(jù)分析領(lǐng)域.Gartner預(yù)計(jì)2015年將有35%的大中型企業(yè)使用內(nèi)存計(jì)算，而在2012年還不足10%.

內(nèi)存計(jì)算不是最新提出的概念，但是近年來(lái)成為業(yè)界和研究領(lǐng)域的一個(gè)熱點(diǎn)，它組合了硬件和軟件最新技術(shù).技術(shù)發(fā)展和應(yīng)用需求是兩大推動(dòng)力，一方面多核計(jì)算和64位計(jì)算系統(tǒng)普及和價(jià)格的下降，另一方面是大數(shù)據(jù)和Web等應(yīng)用的興起.通過(guò)把數(shù)據(jù)裝載到內(nèi)存中，避免了I／O瓶頸，以前在數(shù)小時(shí)、數(shù)天時(shí)間內(nèi)計(jì)算的結(jié)果在內(nèi)存計(jì)算環(huán)境中，可以在數(shù)秒內(nèi)完成.在此高性能的計(jì)算背景下，內(nèi)存計(jì)算再次成為業(yè)界和學(xué)界研究關(guān)注的熱點(diǎn).

在多核CPU演進(jìn)、內(nèi)存價(jià)格的不斷下降，以及系統(tǒng)架構(gòu)的不斷演進(jìn)下，內(nèi)存計(jì)算技術(shù)將成為未來(lái)高性能計(jì)算的主流.

3.2 內(nèi)存計(jì)算的核心及產(chǎn)品

在IMC方式下，所有的數(shù)據(jù)在初始化階段全部加載到內(nèi)存中，數(shù)據(jù)及查詢的執(zhí)行都在高速內(nèi)存內(nèi)執(zhí)行，CPU直接從內(nèi)存讀取數(shù)據(jù)，進(jìn)行實(shí)時(shí)的計(jì)算和分析，避免了應(yīng)用程序、服務(wù)器、網(wǎng)絡(luò)硬件、儲(chǔ)存設(shè)備、磁盤(pán)之間的數(shù)據(jù)交換，減少了許多網(wǎng)絡(luò)與I／O的影響，大幅提升了計(jì)算處理的數(shù)據(jù)吞吐量與處理的速度，通常這部分開(kāi)銷占90%的計(jì)算資源.例如，對(duì)于內(nèi)存數(shù)據(jù)庫(kù)（In－memory database）來(lái)說(shuō)，可以避免I／O密集的索引創(chuàng)建等開(kāi)銷［23］.

內(nèi)存計(jì)算目前尚未有統(tǒng)一的定義.Gartner對(duì)內(nèi)存計(jì)算的定義為［21］：一種應(yīng)用平臺(tái)中間件，實(shí)現(xiàn)分布式、可靠及可擴(kuò)展性、強(qiáng)一致或最終一致性的內(nèi)存NoSQL數(shù)據(jù)存儲(chǔ)，可供多個(gè)應(yīng)用共享.

內(nèi)存計(jì)算不僅僅是把數(shù)據(jù)駐留內(nèi)存，還需要對(duì)軟件體系、計(jì)算模型等進(jìn)行專門(mén)的設(shè)計(jì)［29］.內(nèi)存計(jì)算主要的設(shè)計(jì)理念是：① 將數(shù)據(jù)存放在內(nèi)存中以加快處理的速度.② 使用壓縮技術(shù)減少數(shù)據(jù)量.內(nèi)存計(jì)算可以同一塊存儲(chǔ)空間連續(xù)存儲(chǔ)，為數(shù)據(jù)進(jìn)行壓縮和順序訪問(wèn)提供便利進(jìn)行.文獻(xiàn)［22］通過(guò)實(shí)驗(yàn)，在磁盤(pán)、SSD和內(nèi)存三種存儲(chǔ)介質(zhì)上對(duì)比了順序訪問(wèn)和隨機(jī)訪問(wèn)性能，順序讀效率分別大約提升500倍、30倍和4.5倍.③ 減少數(shù)據(jù)的移動(dòng)，僅移動(dòng)運(yùn)算后的結(jié)果，而非搬移數(shù)據(jù)到運(yùn)算.④ 利用多核處理器，提高處理效率.

一般認(rèn)為內(nèi)存計(jì)算的內(nèi)存是DRAM，數(shù)據(jù)具有易失性，因此IMC環(huán)境下數(shù)據(jù)恢復(fù)管理與傳統(tǒng)的系統(tǒng)差別很大，災(zāi)難恢復(fù)、數(shù)據(jù)備份、監(jiān)控和管理都較難，尤其是分布式集群環(huán)境中.

目前，內(nèi)存計(jì)算的業(yè)界推動(dòng)者為SAP，典型的產(chǎn)品為IMC數(shù)據(jù)庫(kù)HANA［25］，主要應(yīng)用于ERP和CRM等.支持高速事務(wù)處理的內(nèi)存數(shù)據(jù)庫(kù)VoltDB［30］，同時(shí)IBM的solidDB［31］、Oracle的Exadata X3、微軟的SQLServer 2012已經(jīng)引入了內(nèi)存計(jì)算.文獻(xiàn)［24］詳細(xì)研究了基于內(nèi)存的高性能集群，指出硬件和操作系統(tǒng)技術(shù)的進(jìn)步使應(yīng)用全部?jī)?nèi)存中成為可能.

本文把內(nèi)存計(jì)算分為三類：第一類是在多核單機(jī)上的多線程內(nèi)存計(jì)算；第二類是集群環(huán)境中各計(jì)算節(jié)點(diǎn)的內(nèi)存全局統(tǒng)一管理和訪問(wèn)的內(nèi)存集群架構(gòu)；第三類是集群的各計(jì)算節(jié)點(diǎn)獨(dú)立管理本地內(nèi)存，但是計(jì)算時(shí)全部數(shù)據(jù)裝載到本地內(nèi)存中.

4 基于內(nèi)存計(jì)算的圖數(shù)據(jù)處理方案

圖計(jì)算分析是一種I／O密集型計(jì)算［9］，大部分的應(yīng)用計(jì)算需要多次迭代，計(jì)算的狀態(tài)信息需要在計(jì)算節(jié)點(diǎn)間消息傳遞和頻繁更新，尤其是大規(guī)模的圖數(shù)據(jù)，需要在集群的節(jié)點(diǎn)間頻繁的消息傳遞和中間結(jié)果存儲(chǔ).如果把數(shù)據(jù)全部在內(nèi)存中計(jì)算，將極大地提高效率.同時(shí)，文獻(xiàn)［4，37］指出，現(xiàn)有的MapReduce模式不適合大規(guī)模圖數(shù)據(jù)處理，原因一是MapReduce的優(yōu)勢(shì)在于并行處理無(wú)依賴關(guān)系的計(jì)算，對(duì)在有依賴關(guān)系的圖數(shù)據(jù)很難大規(guī)模并行；二是MapReduce共享數(shù)據(jù)的唯一方式是把數(shù)據(jù)寫(xiě)到分布式文件中，增加了數(shù)據(jù)復(fù)制帶來(lái)的I／O，文獻(xiàn)［32］指出該操作帶來(lái)超過(guò)90%的計(jì)算開(kāi)銷，圖數(shù)據(jù)處理將產(chǎn)生大量的中間結(jié)果.

傳統(tǒng)的在單機(jī)運(yùn)行的圖數(shù)據(jù)計(jì)算算法庫(kù)，例如LEDA［33］，擴(kuò)展性不好，面對(duì)大規(guī)模的圖數(shù)據(jù)計(jì)算能力不足；MapReduce計(jì)算框架容錯(cuò)性、擴(kuò)展性等方面較好，但是對(duì)于圖計(jì)算效率不高［32］；現(xiàn)有的圖并行處理系統(tǒng)，存在容錯(cuò)性等問(wèn)題［34］.因此，需要研究適合大規(guī)模圖數(shù)據(jù)計(jì)算的內(nèi)存集群管理計(jì)算技術(shù).

為了提升大規(guī)模圖數(shù)據(jù)計(jì)算的效率，研究者提出了基于內(nèi)存的圖處理系統(tǒng)［7，17，27］.圖的內(nèi)存計(jì)算系統(tǒng)大致可以分為三種：第一種是基于內(nèi)存分布式集群系統(tǒng)，例如Trinity［27］系統(tǒng)；第二種是基于內(nèi)存共享的分布式系統(tǒng)，例如文獻(xiàn)［5－7］所介紹的；第三種是在多核單機(jī)上多線程共享大內(nèi)存系統(tǒng)，例如GRACE［17，35－37］.下面介紹幾個(gè)典型的基于內(nèi)存計(jì)算的圖處理系統(tǒng).

4.1 典型的系統(tǒng)

下面根據(jù)現(xiàn)有的基于內(nèi)存計(jì)算的圖數(shù)據(jù)計(jì)算系統(tǒng)分別進(jìn)行介紹.

4.1.1 內(nèi)存分布式集群

Trinity［27］是一種數(shù)據(jù)存儲(chǔ)和計(jì)算框架，采用內(nèi)存分布式框架和內(nèi)存key－value模式存儲(chǔ)，集群中的節(jié)點(diǎn)的內(nèi)存全局共享，提供在線計(jì)算和離線分析功能.Trinity系統(tǒng)包含三類組件：Slave、Proxy和client.Slave主要負(fù)責(zé)存儲(chǔ)圖數(shù)據(jù)和數(shù)據(jù)上的計(jì)算，Proxy負(fù)責(zé)Salve與Client間的消息通信，Client是用戶與系統(tǒng)通過(guò)API交互的接口.系統(tǒng)支持在線查詢和離線分析.

Trinity采用的內(nèi)存集群采用內(nèi)存全局共享模式，系統(tǒng)把內(nèi)存劃分為2p個(gè)內(nèi)存塊，其中2p＞m，m為集群系統(tǒng)中的機(jī)器個(gè)數(shù).該內(nèi)存管理模式可以在內(nèi)存塊級(jí)別增加并行性，并減少因單個(gè)哈希表沖突造成的性能下降.為提高系統(tǒng)的容錯(cuò)性，Trinity支持?jǐn)?shù)據(jù)后臺(tái)類似HDFS分布式文件備份.

Trinity采用內(nèi)存key－value存儲(chǔ)，其中key為64位的全局唯一ID，value為任意長(zhǎng)度的數(shù)據(jù)塊，通過(guò)哈希方式訪問(wèn)key－value對(duì).具體訪問(wèn)方法如圖5所示.

如圖5所示，在集群全局內(nèi)存空間數(shù)據(jù)通過(guò)key訪問(wèn)數(shù)據(jù)經(jīng)三步：首先確定存儲(chǔ)該keyvalue對(duì)的機(jī)器，可以通過(guò)i＝hash（64bitKey）mod2p獲得所在的內(nèi)存塊i；再通過(guò)查詢?nèi)值刂繁恚ˋddressing Table）獲得該內(nèi)存塊所在的機(jī)器；再次使用key在該機(jī)器上的內(nèi)存塊中訪問(wèn)value.

在Trinity系統(tǒng)中，圖的頂點(diǎn)和邊元素建模為cell，提供一種稱為T(mén)SL的基于面向?qū)ο蟮恼Z(yǔ)言.在數(shù)據(jù)一致性方面，在key－value對(duì)上采用自旋鎖，確保操作的原子性，但不保證并發(fā)序列化操作.在計(jì)算策略選擇方面，Trinity同時(shí)支持BSP同步和異步模式，且其計(jì)算迭代的消息接收和發(fā)送是有選擇性的.Trinity對(duì)圖的劃分采用了二分圖劃分方式，極大地減少了通信開(kāi)銷.Trinity在容錯(cuò)機(jī)制方面，采用分布式文件系統(tǒng)保存持久備份，對(duì)在線更新，

圖5 Trinity系統(tǒng)中數(shù)據(jù)劃分和訪問(wèn)［27］Fig.5 Data accessing and partitioning of Trinity［27］

采用日志機(jī)制確保數(shù)據(jù)一致性.

Trinity利用了內(nèi)存支持快速隨機(jī)訪問(wèn)和并行計(jì)算，支持高效的在線分析和基于頂點(diǎn)為中心計(jì)算模式的離線分析，其中離線分析采用有限制的頂點(diǎn)為中心計(jì)算模式，優(yōu)化了消息傳遞和計(jì)算性能.

4.1.2 分布式內(nèi)存共享的圖處理

1.Spark［7］

Spark是基于內(nèi)存優(yōu)化的內(nèi)存計(jì)算引擎，用于多遍的迭代和交互計(jì)算.Spark的核心概念是彈性分布數(shù)據(jù)集（Resident Distributed Datasets，RDDs），系統(tǒng)把數(shù)據(jù)表示為彈性分布數(shù)據(jù)集.RDD是只讀的、具有容錯(cuò)性記錄劃分集合，它可以從穩(wěn)定數(shù)據(jù)存儲(chǔ)或者其他RDD上構(gòu)建，允許用戶在內(nèi)存中保留中間結(jié)果和控制劃分并提供操控操作原語(yǔ).

系統(tǒng)在主從式集群上實(shí)現(xiàn)圖的內(nèi)存計(jì)算，提供了粗粒度數(shù)據(jù)并行操作的編程API，操作原語(yǔ)包括兩類：數(shù)據(jù)轉(zhuǎn)換類（transformation）和行為類（action）.數(shù)據(jù)轉(zhuǎn)換類用于定義RDD，包括map、filter、collect、Join、partitionByKey等，行為類用于發(fā)起運(yùn)算或保存結(jié)果，包括count、collect、reduce、save等.待處理的數(shù)據(jù)存儲(chǔ)可以存在HDFS或Hbase上，本地?cái)?shù)據(jù)完全加載到本地節(jié)點(diǎn)的內(nèi)存中，其運(yùn)行和數(shù)據(jù)加載如圖6所示.任務(wù)的調(diào)度通過(guò)建立RDD世系圖DAG分階段執(zhí)行.

圖6 Spark數(shù)據(jù)加載和運(yùn)行時(shí)［7］Fig.6 Data load and runtime［7］

內(nèi)存提供三種對(duì)象持久存儲(chǔ)方式：內(nèi)存反序列化Java對(duì)象，序列化數(shù)據(jù)和磁盤(pán)存儲(chǔ)，但尚未實(shí)現(xiàn)集群節(jié)點(diǎn)內(nèi)存的全局化統(tǒng)一管理.三種方式在性能方面依次降低.在數(shù)據(jù)一致性方面，Spark支持檢測(cè)點(diǎn)機(jī)制和RDD世系恢復(fù).數(shù)據(jù)劃分和分布采用基于哈希的數(shù)據(jù)劃分.

鑒于Spark粗粒度編程API，使得它的編程能力有限.Spark適用于在數(shù)據(jù)集上操作相同的批處理應(yīng)用，而對(duì)更新類型應(yīng)用效率不高.

GraphX［6］系統(tǒng)是在Spark系統(tǒng)的基礎(chǔ)上，除了提供數(shù)據(jù)并行操作，例如map、reduce、filter等之外，還提供了以邊為中心圖并行操作API，例如subgaph等.由于GraphX使用了索引、執(zhí)行策略以及Join優(yōu)化，使得GraphX的性能比Spark快一個(gè)量級(jí)以上.

2.GraphLab［5］

GraphLab是采用分布式共享內(nèi)存的圖處理系統(tǒng)，即把整個(gè)圖和程序狀態(tài)存儲(chǔ)在內(nèi)存中，但是集群中的內(nèi)存由本地計(jì)算機(jī)管理，每個(gè)本地計(jì)算節(jié)點(diǎn)采用多線程并發(fā).首先儲(chǔ)存在分布式文件中的圖被劃分為k個(gè)部分，分別存儲(chǔ)于各計(jì)算節(jié)點(diǎn)，每一個(gè)部分存儲(chǔ)一個(gè)包括頂點(diǎn)和鄰接邊信息的文件，圖的連通結(jié)構(gòu)和k部分的數(shù)據(jù)位置信息存儲(chǔ)在索引中.索引用于數(shù)據(jù)加載以確保數(shù)據(jù)劃分均衡.GraphLab系統(tǒng)視圖如圖7所示.圖中GraphLab的圖處理分為兩個(gè)階段：初始化階段和執(zhí)行階段.初始化階段主要完成數(shù)據(jù)解析、劃分和創(chuàng)建索引.執(zhí)行階段，數(shù)據(jù)文件從分布式文件系統(tǒng)加載到內(nèi)存在GraphLab引擎上運(yùn)行.

圖7 GraphLab系統(tǒng)視圖［5］Fig.7 System overview of GraphLab［5］

GraphLab中圖的結(jié)構(gòu)是靜態(tài)不可改變的.GraphLab把圖的計(jì)算抽象為三部分：數(shù)據(jù)圖、更新函數(shù)和同步操作.數(shù)據(jù)圖是在頂點(diǎn)或邊上關(guān)聯(lián)用戶數(shù)據(jù)的有向圖.更新函數(shù)可以表示為f（v，Sv）→（Sv，T），函數(shù)的輸入為頂點(diǎn)v以及由頂點(diǎn)v和v鄰接的頂點(diǎn)和鄰接邊集合Sv，函數(shù)更新Sv中元素的狀態(tài)并返回下一次迭代將要更新的元素集合T.GraphLab同步和一致性分別通過(guò)著色引擎和分布式鎖引擎來(lái)實(shí)現(xiàn)，支持三種一致性模型：完整一致性、邊一致性和頂點(diǎn)一致性.三者的并行性依次增強(qiáng).數(shù)據(jù)的容錯(cuò)則采用了分布式檢測(cè)點(diǎn)機(jī)制.

3.Pregel［4］

Pregel系統(tǒng)是工作在Google集群架構(gòu)之上，采用分布式集群和BSP消息同步機(jī)制處理有向圖.Pregel把所有的計(jì)算狀態(tài)駐留在集群中工作節(jié)點(diǎn)的內(nèi)存，也是分布式內(nèi)存計(jì)算的一種形式.根據(jù)圖計(jì)算的特點(diǎn)，把計(jì)算表達(dá)為迭代序列，計(jì)算序列之間通過(guò)圖的頂點(diǎn)接收和發(fā)送消息或改變狀態(tài).Pergel計(jì)算模型如圖8所示，圖中兩個(gè)頂點(diǎn)v和n，其計(jì)算包括接收其他頂點(diǎn)發(fā)送的消息，更新自身狀態(tài)，更新邊的狀態(tài)，向鄰接點(diǎn)發(fā)送消息.

圖8 Pregel計(jì)算模型［4］Fig.8 Computation of Pregel［4］

Pregel的核心包括節(jié)點(diǎn)間消息傳送、中間結(jié)果合并（Combiner）、全局結(jié)果聚合（Aggregator）.聚合函數(shù)要求滿足交換律和結(jié)合律.數(shù)據(jù)的劃分采用哈希函數(shù)隨機(jī)劃分并支持用戶定制的劃分.在容錯(cuò)方面Pregel采用檢測(cè)點(diǎn)機(jī)制.

此外，Giraph［39］是一種在采用Hadoop分布式平臺(tái)上處理大規(guī)模圖數(shù)據(jù)的平臺(tái)，系統(tǒng)與Pregel采用相似的設(shè)計(jì)，實(shí)質(zhì)是Pregel的開(kāi)源實(shí)現(xiàn).Giraph所有的計(jì)算在內(nèi)存中進(jìn)行，采用ZooKeeper同步.

4.PowerGraph［3］

PowerGraph綜合了GraphLab與Pregel的優(yōu)點(diǎn)，采用共享內(nèi)存結(jié)構(gòu)，引入了GAS模型來(lái)表示圖處理的過(guò)程，G階段在頂點(diǎn)u與鄰居節(jié)點(diǎn)v和邊e（u，v）上進(jìn)行計(jì)算，形式化記，其中運(yùn)算 ⊕ 要求滿足交換律和結(jié)合律；A 階段的任務(wù)是更新頂點(diǎn)u的值，記為；S階段使用新的值來(lái)更新頂點(diǎn)u的鄰居節(jié)點(diǎn)，記為

PowerGraph把基于頂點(diǎn)的計(jì)算分解為邊并行（edge－parallel）和頂點(diǎn)并行（vertex－parallel）兩個(gè)階段.在多數(shù)情況下，節(jié)點(diǎn)上運(yùn)行的計(jì)算并不涉及全部的鄰居節(jié)點(diǎn)，PowerGraph通過(guò)緩存G階段的計(jì)算值而避免大量的計(jì)算.PowerGraph同時(shí)支持同步和異步運(yùn)行模式，試驗(yàn)表明異步模式較適合數(shù)據(jù)挖掘類的應(yīng)用.在異步處理時(shí)，PowerGraph采用與GrapLab類似的序列化技術(shù)：為每一個(gè)頂點(diǎn)運(yùn)行的程序定義相應(yīng)的執(zhí)行序列，通過(guò)鎖技術(shù)控制鄰居節(jié)點(diǎn)的運(yùn)行順序.PowerGraph提供了同步、異步和異步＋串行模式，采用快照機(jī)制實(shí)現(xiàn)容錯(cuò).

4.1.3 單機(jī)多核圖處理

單機(jī)上的圖計(jì)算多利用多核CPU，采用大內(nèi)存和多線程并行，一般為了充分發(fā)揮單機(jī)的計(jì)算效能，采取充分利用內(nèi)存和CPU的cache、優(yōu)化磁盤(pán)讀取等措施.單機(jī)環(huán)境的圖內(nèi)存計(jì)算一般可以支持圖的動(dòng)態(tài)更新，但一般擴(kuò)展性有限.

1.Graphchi［38］

Graphchi是在多核單機(jī)系統(tǒng)上采用多線程和內(nèi)存并行滑動(dòng)窗口（Parallel Sliding Windows，PSW）技術(shù).Graphchi通過(guò)三個(gè)階段：① 從磁盤(pán)加載圖數(shù)據(jù)到內(nèi)存塊；② 更新頂點(diǎn)和邊的值；③ 把更新寫(xiě)入磁盤(pán).首先把圖的頂點(diǎn)劃分為P個(gè)區(qū)間，對(duì)每一個(gè)頂點(diǎn)區(qū)間，關(guān)聯(lián)一個(gè)用于存儲(chǔ)以該區(qū)間內(nèi)的頂點(diǎn)為終點(diǎn)的邊的內(nèi)存塊（Shard），區(qū)間的大小需確保所有的邊都能加載到內(nèi)存.根基PSW的設(shè)計(jì)，區(qū)間p存儲(chǔ)了該區(qū)間頂點(diǎn)的所有入邊，該區(qū)間頂點(diǎn)的出邊可以通過(guò)滑動(dòng)（P－1）個(gè)滑動(dòng)窗口獲得，如圖11所示.

圖9 Graphchi內(nèi)存并行滑動(dòng)窗口示意圖［38］Fig.9 Parallel sliding windows illustration of Graphchi［38］

Graphchi系統(tǒng)計(jì)算的每一次迭代需要順序訪問(wèn)磁盤(pán)P次，因此對(duì)于一次計(jì)算需要O（P2）磁盤(pán)I／O.通過(guò)內(nèi)存計(jì)算和磁盤(pán)操作并行，最大化單機(jī)上計(jì)算效率.Graphchi采用異步計(jì)算模型，支持圖結(jié)構(gòu)更新，但對(duì)于圖遍歷訪問(wèn)效率不高，因?yàn)轫旤c(diǎn)鄰接點(diǎn)的訪問(wèn)需要掃描所有的內(nèi)存塊.

2.Grace［35］

Grace在多核單機(jī)上實(shí)現(xiàn)基于內(nèi)存圖數(shù)據(jù)管理，提供了從底層cache、內(nèi)存分配到高層圖查詢和更新的API接口.Grace采用以頂點(diǎn)為中心的數(shù)據(jù)更新模型，對(duì)圖進(jìn)行哈希和基于啟發(fā)式的劃分策略，每個(gè)物理核處理一個(gè)劃分，各個(gè)計(jì)算內(nèi)核采用BSP同步計(jì)算，其事務(wù)采用快照隔離技術(shù)支持事務(wù)級(jí)的圖結(jié)構(gòu)和數(shù)據(jù)更新.

Grace內(nèi)存的數(shù)據(jù)結(jié)構(gòu)如圖12所示.內(nèi)存數(shù)據(jù)結(jié)構(gòu)主要有：① 頂點(diǎn)數(shù)組（Vertex Log），用于存儲(chǔ)該劃分內(nèi)的所有頂點(diǎn)；② 邊邊指針數(shù)組，用于存儲(chǔ)頂點(diǎn)的邊集的位置；③ 邊數(shù)組（Edge Log）用于存儲(chǔ)邊的度數(shù)和邊集，每條邊包括所在劃分的ID和目標(biāo)頂點(diǎn)的位置確定；④ 頂點(diǎn)的索引，用于在頂點(diǎn)單數(shù)組中查詢；⑤ 頂點(diǎn)分配位圖，用于指示頂點(diǎn)數(shù)組中的頂點(diǎn)是否有效.

圖10 Grace內(nèi)存的數(shù)據(jù)結(jié)構(gòu)［35］Fig.10 In－memory data structure of Grace［35］

Grace中圖的計(jì)算在多核之間迭代進(jìn)行，實(shí)驗(yàn)表明Grace在多核系統(tǒng)上具有良好的擴(kuò)展性能夠和加速比.

綜上所述，目前基于內(nèi)存的圖處理系統(tǒng)從計(jì)算策略、并行策略、計(jì)算同步以及容錯(cuò)處理等方面進(jìn)行了研究和實(shí)驗(yàn)驗(yàn)證.表4總結(jié)了以上介紹的代表性圖處理系統(tǒng).

表4 代表性系統(tǒng)圖處理系統(tǒng)對(duì)比Tab.4 The comparison of representative systems

4.2 圖內(nèi)存計(jì)算關(guān)鍵技術(shù)

綜合基于內(nèi)存計(jì)算的圖數(shù)據(jù)管理技術(shù)進(jìn)展，文章分析總結(jié)了基于內(nèi)存的圖處理系統(tǒng)的研究關(guān)鍵，主要包括以下幾個(gè)方面.

（1）內(nèi)存分配與管理.內(nèi)存是內(nèi)存計(jì)算的核心資源，內(nèi)存分配與管理是內(nèi)存計(jì)算的關(guān)鍵，如何在內(nèi)存中存儲(chǔ)和訪問(wèn)，是首先要解決的問(wèn)題.Trinity［27］系統(tǒng)研究了集群中全局內(nèi)存統(tǒng)一的訪問(wèn)與管理，采用key－value和自旋鎖key－value數(shù)據(jù)固定在物理內(nèi)存中.文獻(xiàn)［35］采用多種數(shù)據(jù)結(jié)構(gòu)管理圖的邊和頂點(diǎn)，文獻(xiàn)［38］通過(guò)并行滑動(dòng)窗口機(jī)制，達(dá)到圖的內(nèi)存計(jì)算和I／O并行.

（2）圖計(jì)算模式.為了充分的利用內(nèi)存計(jì)算數(shù)據(jù)隨機(jī)訪問(wèn)的特點(diǎn)，需要研究新的計(jì)算模式.以頂點(diǎn)為中心和以圖為中心的計(jì)算兩種策略對(duì)于圖并行處理的效率差別很大，計(jì)算策略極大地影響計(jì)算效率和計(jì)算表達(dá)能力，SG計(jì)算策略和GAS計(jì)算策略都是基于內(nèi)存共享的集群，文獻(xiàn)［27］指出在全局內(nèi)存共享的環(huán)境上有進(jìn)一步的優(yōu)化空間.

（3）操作原語(yǔ)與優(yōu)化機(jī)制.圖數(shù)據(jù)處理的性能優(yōu)化及人性化操作原語(yǔ)，同時(shí)圖的各種應(yīng)用計(jì)算可通過(guò)一列的Join和聚集操作實(shí)現(xiàn)，研究適合內(nèi)存計(jì)算的圖操作原語(yǔ)，從物理層、計(jì)算層優(yōu)化性能，進(jìn)一步提升計(jì)算模型的計(jì)算表達(dá)能力.現(xiàn)有系統(tǒng)缺乏統(tǒng)一的模型、優(yōu)化機(jī)制和操作原語(yǔ).

（4）同步機(jī)制.目前大多系統(tǒng)采用BSP同步，部分系統(tǒng)采用異步機(jī)制.內(nèi)存環(huán)境下計(jì)算的效率遠(yuǎn)高于磁盤(pán)環(huán)境，消息的傳遞的網(wǎng)絡(luò)開(kāi)銷就顯得影響很大，要研究適合內(nèi)存環(huán)境下圖計(jì)算的同步機(jī)制.此外，圖并行處理的數(shù)據(jù)一致性和序列化研究較少.

（5）圖的劃分.大規(guī)模圖的劃分是圖并行處理的關(guān)鍵，眾多研究和實(shí)驗(yàn)表明，圖的劃分的質(zhì)量對(duì)計(jì)算效率、通信開(kāi)銷、負(fù)載均衡等都有極大的影響.為了簡(jiǎn)化劃分和易于實(shí)現(xiàn)，部分系統(tǒng)采用隨機(jī)哈希技術(shù)，對(duì)于內(nèi)存計(jì)算環(huán)境下的圖劃分優(yōu)化，對(duì)性能的影響更為明顯.

（6）容錯(cuò)處理.內(nèi)存數(shù)據(jù)的易失性，使得內(nèi)存計(jì)算環(huán)境下數(shù)據(jù)恢復(fù)和容錯(cuò)至關(guān)重要.文獻(xiàn)［7］指出內(nèi)存計(jì)算和存儲(chǔ)的容錯(cuò)至關(guān)重要，目前容錯(cuò)處理主要有：① 數(shù)據(jù)復(fù)制.內(nèi)存計(jì)算的數(shù)據(jù)復(fù)制到分布式文件，將帶來(lái)巨大的存儲(chǔ)和通信開(kāi)銷；② 日志機(jī)制.③ 分布式鎖.④ 快照.

總之，基于內(nèi)存計(jì)算環(huán)境的大規(guī)模圖數(shù)據(jù)計(jì)算獲得了大量的研究成果，但是技術(shù)分散，模型尚不統(tǒng)一，系統(tǒng)各有優(yōu)缺點(diǎn)，需要結(jié)合內(nèi)存計(jì)算的特征，從物理層、通信層、模型層以及應(yīng)用層設(shè)計(jì)整體的框架，整合各種資源，提供自動(dòng)優(yōu)化和便于操作的原語(yǔ)，支持圖的結(jié)構(gòu)更新和演化，提供在線查詢和離線分析的統(tǒng)一計(jì)算平臺(tái).

4 結(jié) 語(yǔ)

本文從大規(guī)模圖計(jì)算的編程模式、計(jì)算和并行策略、圖劃分、計(jì)算同步等方面分析了大規(guī)模圖數(shù)據(jù)并行處理的計(jì)算核心技術(shù)，研究了主流的基于內(nèi)存計(jì)算的圖處理系統(tǒng)進(jìn)展，對(duì)比分析了典型系統(tǒng)核心功能和技術(shù)，總結(jié)了基于內(nèi)存圖處理系統(tǒng)關(guān)鍵技術(shù)，可作為大規(guī)模圖數(shù)據(jù)管理研究的參考.基于內(nèi)存的圖計(jì)算管理系統(tǒng)發(fā)展迅速，本文就典型的系統(tǒng)進(jìn)行了介紹，沒(méi)有包含所有的系統(tǒng)和技術(shù)，后期會(huì)繼續(xù)跟蹤相關(guān)技術(shù)的發(fā)展.

［1］ GONZALEZ J，LOW Y，GUESTRIN C.Residual splash for optimally parallelizing belief propagation［C］／／International Conference on Artificial Intelligence and Statistics.2009：177－184.

［2］ SMOLA A，NARAYANAMURTHY S.An architecture for parallel topic models［J］.Proceedings of the VLDB Endowment，2010，3（1－2）：703－710.

［3］ GONZALEZ J E，LOW Y，GU H，et al.PowerGraph：distributed graph－parallel computation on natural graphs［C］／／Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation.2012：17－30.

［4］ MALEWICZ G，AUSTERN M H，BIK A J C，et al.Pregel：a system for large－scale graph processing［C］／／SIGMOD.2010：135－146.

［5］ LOW Y，BICKSON D，GONZALEZ J，et al.Distributed GraphLab：a framework for machine learning and data mining in the cloud［J］.Proceedings of the VLDB Endowment，2012，5（8）：716－727.

［6］ XIN R S，GONZALEZ J E，F(xiàn)RANKLIN M J，et al.Graphx：A resilient distributed graph system on spark［C］／／First International Workshop on Graph Data Management Experiences and Systems.2013.

［7］ ZAHARIA M，CHOWDHURY M，DAS T，et al.Resilient distributed datasets：A fault－tolerant abstraction for in－memory cluster computing［C］／／Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation.2012：2－2.

［8］ DEAN J，GHEMAWAT S.MapReduce：simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）：107－113.

［9］ LUMSDAINE A，GREGOR D，HENDRICKSON B，et al.Challenges in parallel graph processing［J］.Parallel Processing Letters，2007，17（01）：5－20.

［10］ F?RBER F，CHA S K，PRIMSCH J，et al.SAP HANA database：data management for modern business applications［J］.ACM Sigmod Record，2012，40（4）：45－51.

［11］ PLATTNER H.A common database approach for OLTP and OLAP using an in－memory column database［C］／／SIGMOD.2009：1－2.

［12］ ROBINSON I，WEBBER J，EIFREM E.Graph databases［M］.O＇Reilly Media，Inc.，2013.

［13］ BRIN S，PAGE L.The anatomy of a large－scale hypertextual web search engine［C］／／WWW，1998：107－117.

［14］ KLEINBERG J M.Authoritative sources in a hyperlinked environment［J］.Journal of the ACM （JACM），1999，46（5）：604－632.

［15］ TIAN Y，HANKINS R，PATEL J M.Efficient aggregation for graph summarization［C］／／SIGMOD，2008：419－432.

［16］ KARYPIS G，KUMAR V.A Coarse－Grain Parallel Formulation of Multilevel k－way Graph Partitioning Algorithm［C］／／PARALLEL PROCESSING FOR SCIENTIFIC COMPUTING.SIAM.1997.

［17］ WANG G，XIE W，DEMERS A J，et al.Asynchronous Large－Scale Graph Processing Made Easy［C］／／CIDR.2013.

［18］ TIAN Y，BALMIN A，CORSTEN S A，et al.From“think like a vertex”to“think like a graph”［J］.Proceedings of the VLDB Endowment，2013，7（3）：193－204

［19］ KARYPIS G，KUMAR V.Multilevel k－way Partitioning Scheme for Irregular Graphs［J］.Journal of Parallel and Distributed Computing，1998，48（1）：96－129.

［20］ VALIANT L G.A bridging model for parallel computation［J］.Communications of the ACM，1990，33（8）：103－111.

［21］ GARTNER Says In－Memory Computing Is Racing Towards Mainstream Adoption［EB／OL］.2013［2014－07－01］.http：／／www.gartner.com／newsroom／id／2405315.

［22］ ROY A，MIHAILOVIC I，ZWAENEPOEL W.X－Stream：edge－centric graph processing using streaming partitions［C］／／Proceedings of the Twenty－Fourth ACM Symposium on Operating Systems Principles.2013：472－488.

［23］ DEFINITION in－memory database［EB／OL］.2013［2014－07－01］.http：／／whatis.techtarget.com／definition／inmemory－database.

［24］ OUSTERHOUT J，AGRAWAL P，ERICKSON D，et al.The case for RAMClouds：scalable high－performance storage entirely in DRAM［J］.ACM SIGOPS Operating Systems Review，2010，43（4）：92－105.

［25］ F?RBER F，CHA S K，PRIMSCH J，et al.SAP HANA database：data management for modern business applications［J］.ACM Sigmod Record，2012，40（4）：45－51.

［26］ CDH100%Open Source Distribution including Apache Hadoop.［EB／OL］.2014［2014－07－01］.http：／／www.cloudera.com／content／cloudera／en／products－and－services／cdh.html.

［27］ Shao B，Wang H，Li Y.Trinity：A distributed graph engine on a memory cloud［C］／／Proceedings of the 2013international conference on Management of data.2013：505－516.

［28］ KANE F.Why in－memory computing is going mainstream.［EB／OL］.2013［2014－07－01］.http：／／www.information－age.com／technology／information－management／123457007／why－in－memory－computing－is－going－mainstream.

［29］ In Memory Databases：HANA，Exadata X3 and Flash Memory.［EB／OL］.2012［2014－07－01］.http：／／flashdba.com／2012／10／10／in－memory－databases－part2／.

［30］ STONEBRAKER M，WEISBERG A.The VoltDB Main Memory DBMS［J］.IEEE Data Eng Bull，2013，36（2）：21－27.

［31］ LINDSTR?M J，RAATIKKA V，RUUTH J，et al.IBM solidDB：In－Memory Database Optimized for Extreme Speed and Availability［J］.IEEE Data Eng Bull，2013，36（2）：14－20.

［32］ ZAHARIA M，CHOWDHURY M，DAS T，et al.Fast and interactive analytics over Hadoop data with Spark［C］／／USENIX，2012，37（4）：45－51

［33］ LEDA algorithmic.［EB／OL］.2014［2014－07－01］.http：／／www.algorithmic－solutions.com／leda／.

［34］ GREGOR D，LUMSDAINE A.The parallel BGL：A generic library for distributed graph computations［J］.Parallel Object－Oriented Scientific Computing（POOSC），2005，2：1－18

［35］ PRABHAKARAN V，WU M，WENG X，et al.Managing Large Graphs on Multi－Cores with Graph Awareness［C］／／USENIX Annual Technical Conference.2012：41－52.

［36］ JOUILI S，REYNAGA A.imGraph：A distributed in－memory graph database［C］／／Social Computing （Social－Com），2013：732－737.

［37］ LOW Y，GONZALEZ J，KYROLA A，et al.Graphlab：A new framework for parallel machine learning［J］.arXiv preprint arXiv：1006.4990，2010.

［38］ KYROLA A，BLELLOCH G，GUESTRIN C.Graphchi：Large－scale graph computation on just a pc［C］／／OSDI，2012，8：31－46.

［39］ Welcome to Apache Giraph！.［EB／OL］.2014［2014－01－28］.https：／／giraph.apache.org／.