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

（1.南京農(nóng)業(yè)大學 信息科技學院，南京 210095；2.復(fù)旦大學 計算機科學技術(shù)學院，上海 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)用中的圖包含了百萬和億萬級別的頂點和邊，如截至2014年第一季度Facebook包含了12.3億個活躍用戶，每個用戶平均好友130個；Web鏈接圖頂點數(shù)達到T級，邊的個數(shù)達到P級.同時，圖數(shù)據(jù)分析與處理技術(shù)在機器學習與數(shù)據(jù)挖掘中具有重要應(yīng)用，例如信念傳播算法［1］、隨機優(yōu)化［2］等.鑒于圖建模的靈活性和應(yīng)用廣泛性，大規(guī)模圖數(shù)據(jù)的存儲和分析處理技術(shù)成為近年來數(shù)據(jù)庫等領(lǐng)域的研究熱點，尤其是分布式集群計算的廣泛應(yīng)用，研究者提出了在集群上處理大規(guī)模圖數(shù)據(jù)存儲和分析處理技術(shù)［3－7］.

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

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

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

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

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

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

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

1.2 計算框架

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

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

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

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

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

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

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

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

2 圖的計算

2.1 圖的編程模式

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

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

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

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

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

2.2 圖的計算策略

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

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

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

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

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

表1 以頂點為中心和以邊為中心的計算策略Tab.1 Evaluations of vertex－centric and edge－centric strategies

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

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

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

2.3 圖的并行策略

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

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

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

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

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

2.4 圖劃分

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

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

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

圖3 邊和頂點切割［6］Fig.3 Edge－cut and vertex－cut［6］

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

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

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

2.5 圖處理的同步策略

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

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

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

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

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

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

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

2.6 圖處理的容錯機制

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

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

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

3 內(nèi)存計算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 典型的系統(tǒng)

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

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

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

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

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

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

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

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

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

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

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

1.Spark［7］

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

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

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

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

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

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

2.GraphLab［5］

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

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

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

3.Pregel［4］

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

圖8 Pregel計算模型［4］Fig.8 Computation of Pregel［4］

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

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

4.PowerGraph［3］

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

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

4.1.3 單機多核圖處理

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

1.Graphchi［38］

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

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

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

2.Grace［35］

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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