吳城文，張廣艷，鄭緯民

清華大學(xué)計算機科學(xué)與技術(shù)系 北京 100084

從系統(tǒng)角度審視大圖計算

吳城文，張廣艷，鄭緯民

清華大學(xué)計算機科學(xué)與技術(shù)系 北京 100084

大圖計算已經(jīng)成為學(xué)術(shù)界和工業(yè)界的一種基本計算模式，并且已經(jīng)被應(yīng)用到許多實際的大數(shù)據(jù)計算問題上，如社交網(wǎng)絡(luò)分析、網(wǎng)頁搜索以及商品推薦等。對于這些問題，大圖的規(guī)模約有10億級的點以及1 000億級的邊，這樣的規(guī)模給大圖的高效處理帶來了諸多挑戰(zhàn)。為此，介紹了大圖計算的基本特征和挑戰(zhàn)、典型的計算模型以及具有代表性的分布式、單機處理系統(tǒng)，同時對圖處理系統(tǒng)中的關(guān)鍵技術(shù)進行總結(jié)，最后從系統(tǒng)的角度給出大圖計算可能的一些研究方向。

大數(shù)據(jù)計算；大圖計算；計算模型；計算系統(tǒng)

1 引言

圖可以用來表征不同實體間復(fù)雜的依賴關(guān)系。因而，在許多實際的應(yīng)用當(dāng)中，如社交網(wǎng)絡(luò)分析、網(wǎng)頁搜索、商品推薦等都可以使用圖來進行問題的建模和分析。然而，在大數(shù)據(jù)時代，這類問題的規(guī)模通常十分龐大，以社交網(wǎng)絡(luò)為例，F(xiàn)acebook在2014年7月的用戶已經(jīng)達到22億戶1http://tech. qq.com/a/ 20140725/ 000288.htm，而用戶之間的關(guān)系數(shù)量則更多，以數(shù)據(jù)的方式進行存儲通常會占用幾百GB甚至TB級的存儲量。因此，大圖計算不僅是計算密集型，同時也是存儲密集型問題，如何在可以接受的時間內(nèi)對大圖進行計算，是需要解決的難題。

通常，為了快速地對大圖進行處理，常常會使用分布式并行計算的思想，但是由于圖計算本身特征使得在實現(xiàn)并行圖計算時，不能使用傳統(tǒng)科學(xué)計算領(lǐng)域的并行模式（計算偏微分方程）[1]；且以往在處理大數(shù)據(jù)問題上的map/reduce[2]模式，在處理圖問題時效率極低；另外，并行圖算法庫Parallel BGL[3]或CGMgraph[4]沒有容錯機制。基于以上幾點，需要一套符合大圖計算特點的高效分布式并行計算框架?，F(xiàn)在一些常見的分布式處理系統(tǒng)有Pregel[5]及其對應(yīng)的開源實現(xiàn)Giraph2https://giraph. apache.org/以及GraphLab[6]、PowerGraph[7]、GraphX[8]和Cyclops[9]。這些分布式系統(tǒng)大部分采用“think like a vertex”的思想，即以點為中心（vertex-centric）的計算模型，如圖1[10]所示。在這種模型中，所有的點從其入邊的鄰點獲取數(shù)據(jù)，執(zhí)行用戶自定義的函數(shù)對自己的狀態(tài)進行更新，然后將自己的更新狀態(tài)通過消息發(fā)給其出邊的鄰點。還有少數(shù)一些分布式系統(tǒng)采用了其他的計算模型，如PowerGraph的以邊為中心（edge-centric）的計算模型，如圖2所示。在這種計算模型當(dāng)中，首先依次遍歷所有的邊，將邊的源點的更新值通過其出邊傳遞給目的點，然后遍歷所有的更新值，將更新值更新到目的點（在PowerGraph中將gather操作移到了scatter操作前面）。另外，還有以塊[11]、路徑[12]為中心的計算模型，在這類計算模型中，針對圖結(jié)構(gòu)來進行圖劃分，增加了計算的局部性，但是也存在圖劃分時間過長等問題。

圖1 以點為中心的計算模型[10]

圖2 以邊為中心的計算模型[10]

分布式圖處理系統(tǒng)隨著問題規(guī)模的擴大具有很好的拓展性，但是在提高系統(tǒng)處理效率方面仍然面臨許多挑戰(zhàn)。比如圖的劃分，要提高系統(tǒng)性能需要在保證集群各節(jié)點負載均衡的情況下，使得集群內(nèi)各節(jié)點的通信量最少，是一個NP難問題。此外，一個分布式系統(tǒng)需要解決集群內(nèi)各節(jié)點協(xié)同工作、容錯等一系列問題，而這類問題對系統(tǒng)的性能有重要的影響。另一方面，對于使用分布式系統(tǒng)的程序員來說，環(huán)境的搭建、編寫分布式程序比較復(fù)雜，而且程序的調(diào)試和優(yōu)化又相對困難。基于此，最近一些大圖計算的研究工作，在使用單臺計算機進行大圖計算處理上有了一些新的成果，如以點為中心的計算模型的GraphChi[13]和以邊為中心的計算模型的X-Stream[10]，另外還有VENUS[14]、GridGraph[15]等。這些成果極大地降低了大圖計算的成本開銷，同時能夠達到甚至好于一些分布式圖計算系統(tǒng)處理時延。

本文將介紹當(dāng)前大圖計算的主要特征及挑戰(zhàn)，從系統(tǒng)角度給出當(dāng)前大圖處理系統(tǒng)的主要特征及其研究成果，并對圖處理系統(tǒng)中的關(guān)鍵技術(shù)進行總結(jié)，最后給出大圖計算系統(tǒng)方面可能的研究方向。

2 大圖計算的特征及挑戰(zhàn)

大圖計算是大數(shù)據(jù)計算中的一個子問題，除了滿足大數(shù)據(jù)的基本特性之外，大圖計算還有著自身的計算特性，相應(yīng)地面臨著新的挑戰(zhàn)。

（1）局部性差

圖表示著不同實體之間的關(guān)系，而在實際的問題當(dāng)中，這些關(guān)系經(jīng)常是不規(guī)則和無結(jié)構(gòu)的，因此圖的計算和訪存模式都沒有好的局部性，而在現(xiàn)有的計算機體系架構(gòu)上，程序的性能獲得往往需要利用好局部性。所以，如何對圖數(shù)據(jù)進行布局和劃分，并且提出相應(yīng)的計算模型來提升數(shù)據(jù)的局部性，是提高圖計算性能的重要方面，也是面臨的關(guān)鍵挑戰(zhàn)。

（2）數(shù)據(jù)及圖結(jié)構(gòu)驅(qū)動的計算

圖計算基本上完全是由圖中的數(shù)據(jù)所驅(qū)動的。當(dāng)執(zhí)行圖算法時，算法是依據(jù)圖中的點和邊來進行指導(dǎo)，而不是直接通過程序中的代碼展現(xiàn)出來。所以，不同的圖結(jié)構(gòu)在相同的算法實現(xiàn)上，將會有著不同的計算性能。因此，如何使得不同圖結(jié)構(gòu)在同一個系統(tǒng)上都有較優(yōu)的處理結(jié)果，也是一大難題。

（3）圖數(shù)據(jù)的非結(jié)構(gòu)化特性

圖計算中圖數(shù)據(jù)往往是非結(jié)構(gòu)化和不規(guī)則的，在利用分布式框架進行圖計算時，首先需要對圖進行劃分，將負載分配到各個節(jié)點上，而圖的這種非結(jié)構(gòu)化特性很難實現(xiàn)對圖的有效劃分，從而達到存儲、通信和計算的負載均衡。一旦劃分不合理，節(jié)點間不均衡的負載將會使系統(tǒng)的拓展性受到嚴(yán)重的限制，處理能力也將無法符合系統(tǒng)的計算規(guī)模。

（4）高訪存/計算比

絕大部分的大圖計算規(guī)模使得內(nèi)存中無法存儲下所有的數(shù)據(jù)，計算中磁盤的I/O必不可少，而且大部分圖算法呈現(xiàn)出迭代的特征，即整個算法需要進行多次迭代，每次迭代需要遍歷整個圖結(jié)構(gòu)，而且每次迭代時所進行的計算又相對較少。因此，呈現(xiàn)出高的訪存/計算比。另外，圖計算的局部性差，使得計算在等待I/O上花費了巨大的開銷。

3 分布式大圖計算系統(tǒng)

本節(jié)將介紹幾個典型的大圖處理的分布式系統(tǒng)，重點突出每個系統(tǒng)的特點。

3.1 Pregel

Pregel是由Google公司開發(fā)的分布式處理圖系統(tǒng)，其主要的設(shè)計思想是基于BSP（bulk synchronous parallel）[16]。在此思想上，Pregel使用了以點為中心的計算模型，對整個圖根據(jù)點進行劃分，將不同的點以及相關(guān)的鄰邊存儲到不同的計算機器上。在Pregel中，用戶可以自定義點的compute( )函數(shù)，每個點多次迭代執(zhí)行這個函數(shù)，并最終得出整個圖的計算結(jié)果。具體地，在每一次迭代（superstep）中，每個活躍的點（active vertex）會執(zhí)行compute( )函數(shù)，在這個函數(shù)中，該點讀取在前一次迭代中其鄰點發(fā)送的消息，通過這些消息計算自己新的狀態(tài)，再將自己最新的狀態(tài)通過出邊發(fā)送給其鄰點（鄰點將會在下一次迭代中收到這些消息），然后該點會進入不活躍狀態(tài)（inactive），如圖3http://hadoop. apache.org/所示。當(dāng)不活躍的點（inactive vertex）在下一輪收到消息時，就會重新處于活躍狀態(tài)。當(dāng)所有活躍的點執(zhí)行完compute( )函數(shù)之后，當(dāng)前迭代結(jié)束，并且進入到下一次迭代。如果系統(tǒng)當(dāng)中所有的點都處于不活躍狀態(tài)，并且沒有任何新的消息，算法結(jié)束。

Pregel使用了消息傳遞（message passing）的方式進行計算節(jié)點之間的通信，在一次迭代中每個點可以向其他點發(fā)送任意量的消息，而這些消息將會在下一次迭代中被對應(yīng)的點讀取。在分布式的環(huán)境中，為了減少機器間的通信量，提升計算的性能，當(dāng)點的compute( )函數(shù)的操作符合交換律和結(jié)合律時，Pregel可以支持用戶實現(xiàn)combiner( )函數(shù)，把從機器Mi到另一臺機器Mj上點v的所有消息合并成一條消息。

3.2 Giraph

Giraph構(gòu)建在Hadoop3http://hadoop. apache.org/之上，是對Google公司Pregel的開源實現(xiàn)。Facebook使用Giraph來進行社交關(guān)系圖的分析。為了提升系統(tǒng)的性能，在原有Giraph基礎(chǔ)上增加了一些優(yōu)化的措施。Facebook在Giraph的加載圖數(shù)據(jù)、寫回圖數(shù)據(jù)以及計算階段引入了多進程，提升了系統(tǒng)的整體性能，尤其對計算密集型的應(yīng)用，引入多線程可以使性能隨著處理器的增加獲得接近線性的加速比。

圖3 Pregel點的狀態(tài)機[5]

3.3 GraphLab和PowerGraph

與Pregel的同步數(shù)據(jù)推送的BSP模型不同，GraphLab使用異步的GAS（gather、apply、scatter）模型來實現(xiàn)大圖分布式并行計算。GraphLab使用共享內(nèi)存（shared memory）的方式來實現(xiàn)以點為中心的計算模式，在這種方式下，每個點可以直接讀取和修改其鄰點和鄰邊的值。在GraphLab上實現(xiàn)算法時，用戶需要實現(xiàn)符合算法要求的GAS函數(shù)，在算法執(zhí)行時，圖的每個點都會執(zhí)行該函數(shù)。

在gather階段，每個執(zhí)行GAS函數(shù)的活躍點從其鄰點和鄰邊獲取數(shù)據(jù)，然后使用這些值來計算自己的更新值，這里計算操作必須滿足交換律和結(jié)合律。在apply階段，活躍點將原來的舊值更新為計算得到的新值。在scatter階段，活躍的點會通過鄰邊激活對應(yīng)的鄰點。如圖4所示，在GraphLab中使用一個全局的調(diào)度器，各個工作節(jié)點通過從該調(diào)度器獲取活躍的點來進行計算，這些正在被計算的點也可能會將其鄰點調(diào)入調(diào)度器中。最后當(dāng)調(diào)度器中沒有任何可調(diào)度的點時，算法終止。這種調(diào)度器的使用使得GraphLab同時支持算法的異步調(diào)度執(zhí)行和同步調(diào)度執(zhí)行。

圖4 GraphLab計算框架[17]

在同步執(zhí)行（synchronous execution）計算模式下，每個點或者邊的更新不能馬上被當(dāng)前迭代中接下來的計算感知到，直到當(dāng)前迭代結(jié)束時，在下一次迭代當(dāng)中才能讀取到更新的值。異步執(zhí)行（asynchronous execution）與同步執(zhí)行不同，點或者邊的更新能夠馬上被接下來的計算所感知并使用到，這種計算模式可以使得如PageRank的一些算法收斂速度更快，但也同時會導(dǎo)致數(shù)據(jù)競爭，從而產(chǎn)生額外的計算開銷。另外，在分布式系統(tǒng)中，這種模式會產(chǎn)生隨機的信息傳遞，因而也會產(chǎn)生較大的通信開銷。一般來說，對于計算密集型的算法（如BP）來說，更適合使用異步計算的模式。

圖5 PowerGraph切割點集劃分及通信模式[7]

PowerGraph包含在GraphLab 2.2中，是在GraphLab的基礎(chǔ)上對符合冪律分布（power-law）[18]的自然圖計算性能的改進，其主要改進是在圖的劃分上。如圖5所示，PowerGraph使用了Vertex-cut的圖劃分策略，將待處理的圖以切割點集的方式進行劃分，將那些度極大的點的邊分割給不同的計算節(jié)點，同時，將對應(yīng)的點也復(fù)制給這些計算節(jié)點作為鏡像（mirror）點。具體計算時，每個主點及其對應(yīng)鏡像點在本地執(zhí)行g(shù)ather操作，隨后鏡像點將自己的計算結(jié)果發(fā)送給主點，收到全部計算結(jié)果后，主點執(zhí)行apply操作，并且將更新值發(fā)送給所有鏡像點，最后主點和鏡像點進行scatter操作。

3.4 GraphX

如圖6所示，GraphX是構(gòu)建在分布數(shù)據(jù)流框架Spark4http://spark. apache.org/上的分布式圖處理系統(tǒng)。GraphX支持Pregel和GraphLab的計算模型，并且拓展了Spark中的RDD（resilient distributed dataset，彈性分布數(shù)據(jù)集），引入了RDG（resilient distributed graph，彈性分布圖），這種結(jié)構(gòu)可以支持許多圖操作，因此現(xiàn)有的大多數(shù)圖算法都可以使用系統(tǒng)中提供的基本操作算子（如join、map和group-by）來實現(xiàn)，并且實現(xiàn)十分簡單。為了利用Spark中這種算子操作，GraphX重構(gòu)了新的vertex-cut圖劃分方法，將圖劃分成水平分區(qū)的頂點和邊的集合。GraphX的性能比直接使用分布式數(shù)據(jù)流框架好一個數(shù)量級，稍差于GraphLab。另外，由于GraphX是構(gòu)建在Spark之上的，所以GraphX能夠得到低開銷的容錯和透明的錯誤恢復(fù)支持。

4 單機大圖計算系統(tǒng)

隨機單臺計算機處理能力和存儲能力的提升，再加上人們對于圖計算模式研究的深入，一些在單機上處理大圖計算的系統(tǒng)被提出，這些系統(tǒng)有著很好的圖計算性能，同時相比分布式系統(tǒng)，其低硬件成本和低功耗的優(yōu)勢明顯。本節(jié)將介紹幾個代表性的單機大圖計算系統(tǒng)。

圖6 GraphX的層次結(jié)構(gòu)（括號中為代碼行數(shù)）[8]

4.1 GraphChi

GraphChi是一個基于磁盤的單機大圖處理系統(tǒng)。在大圖計算中，計算的訪存局部性非常差，嚴(yán)重影響到計算的性能。特別地，在單機情況下系統(tǒng)的計算能力十分有限，因此，為了提升計算性能，GraphChi使用了具有創(chuàng)新性的磁盤數(shù)據(jù)布局和對應(yīng)的計算模型來減少磁盤的隨機訪問；使用選擇性的調(diào)度來加速算法的收斂。

磁盤數(shù)據(jù)的布局和計算模型。GraphChi在計算前首先會對圖數(shù)據(jù)進行預(yù)處理，將輸入的圖劃分成多個shard，每個shard中存儲對應(yīng)點集的所有入邊，并且將入邊按照其源節(jié)點的ID進行排序，劃分時需要保證每個shard中邊的數(shù)量大致相同，每個shard都能夠加載進內(nèi)存。GraphChi使用以點為中心的計算模型，使用并行滑動窗口（parallel sliding window）來加載數(shù)據(jù)進行計算，如圖7所示，每次（interval）計算一個子圖，即一個shard所對應(yīng)點集中所有點的值，需要順序讀取某個點集對應(yīng)的入邊（深灰色部分）以及該點集在其他shard中所對應(yīng)的出邊（黑色矩形框部分），這種數(shù)據(jù)布局和計算模型可以保證每次計算的I/O是順序的。這樣，一次迭代計算整個圖中所有點的值，多次迭代，直到算法收斂。

圖7 并行滑動窗口計算模型[12]

選擇性的調(diào)度。在GraphChi中可以使用選擇調(diào)度性調(diào)度（selective scheduling）策略來加快圖中某些點的收斂，尤其是對這些在兩次相鄰的迭代當(dāng)中變化很顯著的點。在點執(zhí)行update( )函數(shù)時，類似GraphLab中的apply( )，可以將其鄰點加入調(diào)度器中，進行選擇性的調(diào)度。

圖8 X-Stream以邊為中心的計算模型（Uin/Uout為輸入/輸出緩存）[13]

4.2 X-Stream

與GraphChi所使用的以點為中心的計算模型不同，X-Stream使用以邊為中心的計算模型，并且所有的狀態(tài)都保存在點中。X-Stream的計算過程主要分為3個階段：scatter、shuffle和gather，如圖8所示。在scatter階段，X-Stream依次遍歷每一條邊，判斷邊的源節(jié)點是否產(chǎn)生更新，如果有更新產(chǎn)生，將邊通過出邊發(fā)送給目的節(jié)點。shuffle階段是在對圖進行劃分之后，需要增加的一個不同劃分塊之間更新數(shù)據(jù)交換的階段，主要是為了降低在scatter階段的隨機寫開銷。在gather階段，X-Stream依次遍歷在scatter階段產(chǎn)生的所有更新，并更新對應(yīng)點的狀態(tài)值。X-Stream以邊為中心的計算模型對邊進行順序訪問，可以充分發(fā)揮磁盤的等二級存儲介質(zhì)的順序訪問高帶寬加速圖計算，但是在X-Stream中對點的訪問還是隨機的，為了對此進行優(yōu)化，進一步提高計算性能，X-Stream對圖的點集合均等劃分成小的子點集合，每個子點集合其每個點所有的出邊也對應(yīng)地組成一個邊的劃分集合。對點的劃分主要滿足每個子集合中的點都能夠存儲到內(nèi)存中，這樣當(dāng)計算每個劃分塊時，對點的隨機訪問開銷能夠極大地降低，為X-Stream進行劃分后的計算模型。

在對圖進行劃分之后，每個劃分塊在scatter階段，首先將所有的更新值寫在本地的一個輸出緩存中，當(dāng)所有的塊都完成scatter之后，進入一個shuffle階段，這個階段的主要工作是將所有劃分塊的更新進行分配，將更新分配到對應(yīng)的劃分塊的輸入緩存中，作為gather階段的輸入，對點的狀態(tài)進行更新處理。相比于GraphChi，X-Stream對所有邊進行順序訪問，能夠充分發(fā)揮磁盤等二級存儲介質(zhì)的順序帶寬的速度，同時預(yù)處理階段（簡單的散列圖劃分操作）無須進行開銷巨大的排序處理，因此能夠獲得較好的圖處理性能。

4.3 VENUS

盡管GraphChi在大圖處理上能夠取得較好的計算效果，但是也存在如下的缺陷：預(yù)處理需要對邊的源節(jié)點進行排序，開銷大；圖數(shù)據(jù)的加載和計算是分開的，沒有充分利用磁盤和I/O的并行來提高計算性能；對shard內(nèi)的邊排序后，每個點所對應(yīng)的邊不在相鄰的位置，緩存局部性不高。

基于以上的這幾點觀察，筆者提出了如圖9所示的以點為中心的流線型（vertex-centric streamlined）計算模型。在這種計算模型中，筆者分別構(gòu)建了g-shard和v-shard，其中g(shù)-shard與GraphCHi中shard的概念類似，存儲了一個子點集對應(yīng)的所有入邊，但是不用對邊進行排序，而是將目的頂點相同的邊存儲在相鄰的位置，v-shard存儲對應(yīng)一個g-shard中所有目的頂點和源頂點的值。另外，使用了一個全局的點值表，v-shard從其中讀取和寫回對應(yīng)的點值。系統(tǒng)計算點的更新值時，無須像GraphChi將所有的入邊和出邊同時加載進內(nèi)存，只需將入邊加載進內(nèi)存，同時節(jié)點更新后，不用再將更新值寫入出邊，這樣可以極大地減少I/O。此外，當(dāng)加載完g-shard中一個點的所有入邊時，即可對該點的值進行計算，重疊了I/O和CPU的時間開銷，極大地提高了系統(tǒng)的性能。實驗結(jié)果表明，VENUS的性能顯著地好于GraphChi和X-Stream。

圖9 以點為中心的流線型計算模型[14]

4.4 GridGraph

圖10 GridGraph的圖劃分例子[15]

在X-Stream中，在scatter和gather階段之間，還需要一個shuffle階段將每個劃分在scatter階段產(chǎn)生的更新值分配到對應(yīng)劃分的輸入緩存中，供gather階段進行計算。在scatter階段，更新值會有O(|E|)這樣的規(guī)模，其中|E|代表圖中邊的數(shù)量。所以，當(dāng)內(nèi)存不足時，需要將一部分緩存先寫入磁盤，并且在gather階段需要將寫入磁盤的更新值重新讀入內(nèi)存，因此，在此過程中可能會觸發(fā)較多的I/O，嚴(yán)重影響系統(tǒng)的性能。

圖11 雙重滑動窗口計算模型示例[15]

為此，GridGraph提出了如圖10所示的格子劃分方式。首先，將整個點集劃分成相同大小的P份子點集，然后將邊以行和列劃分成格子，每一行對應(yīng)在某個子點集內(nèi)的點所對應(yīng)的所有出邊，每一列對應(yīng)在某個子點集內(nèi)的點所對應(yīng)的所有入邊。對應(yīng)這種圖的劃分方法，筆者提出了雙重滑動窗口的計算模型（如圖11所示），是圖10（a）中圖結(jié)構(gòu)的PageRank第一次迭代過程，計算點的更新值需要讀取其入邊源節(jié)點的值，為此從上到下，依次讀取該列每個格子內(nèi)的邊進行計算，然后當(dāng)一列計算完畢后，即完成一個子點集中點的值的計算，窗口滑動到下一列，繼續(xù)進行計算，直至所有的格子都遍歷完畢。在這種計算模型中，值的更新計算操作必須符合交換律，另外，這種方式點的更新是就地更新，不會產(chǎn)生中間的更新結(jié)果，極大地減少了I/O，同時，點的數(shù)據(jù)訪問的局部性也有了提升。在進行圖劃分時，使用二級的圖劃分策略，即先將圖劃分成Q份，使得每個格子的邊都能夠存儲進內(nèi)存中，然后再對剛才的每個格子進行劃分，使得每個小格子能夠存儲進最后一級cache（LLC）當(dāng)中。另外，GridGraph還支持選擇性的調(diào)度，在BFS和WCC這樣的算法中，可以極大地減少I/O，提高計算性能。

5 大圖計算中的關(guān)鍵技術(shù)

本節(jié)將介紹在分布式和單機圖處理系統(tǒng)中常用的技術(shù)。

5.1 異構(gòu)計算平臺

在異構(gòu)計算系統(tǒng)中，存在著計算能力和計算特點不同的計算單元。比如，GPU具有比CPU更強的多線程并行計算能力，因此在異構(gòu)系統(tǒng)中，CPU會把一些或者全部的計算交給GPU來執(zhí)行。在圖計算領(lǐng)域，相關(guān)的異構(gòu)計算系統(tǒng)已經(jīng)被開發(fā)出來。TOTEM[19]會將度高的點交給CPU計算執(zhí)行，而將度低的點交給GPU來執(zhí)行。而另外一些系統(tǒng)，如MapGraph[20]和CuSha[21]等，會將整個圖都交給GPU來執(zhí)行。除了GPU和CPU的異構(gòu)圖計算平臺之外，一些研究人員發(fā)現(xiàn)，solid-state drive（SSD）有著與傳統(tǒng)hard disk drive（HDD）不同的訪存特性。一些圖計算系統(tǒng)（如TurboGraph[22]和FlashGraph[23]）針對SSD對計算系統(tǒng)進行了優(yōu)化，使得系統(tǒng)在SDD上有著很高的計算性能。目前使用異構(gòu)計算的平臺的圖處理系統(tǒng)主要是單機圖處理系統(tǒng)。

5.2 通信模型

在消息傳遞的通信模型中，算法中點的狀態(tài)保存在本地，通過消息傳遞的方式更新在其他機器上點的狀態(tài)。在Pregel和Giraph中，使用了消息傳遞的通信模型，為了確保所有更新的數(shù)據(jù)可用，需要在前后兩次迭代計算之間加入一個同步操作。

在共享內(nèi)存的通信模型中，各個處理單元允許并發(fā)訪問和修改相同地址的數(shù)據(jù)。在一些分布式的計算系統(tǒng)（如GraphLab和PowerGraph）中，使用了虛擬共享內(nèi)存來實現(xiàn)各計算節(jié)點之間的透明的同步。在這些圖處理系統(tǒng)中，使用了假點（ghost vertex）的方式來實現(xiàn)虛擬共享內(nèi)存。在假點的這種實現(xiàn)策略中，圖中的每個點有一個歸屬的工作節(jié)點，另外有一些工作節(jié)點擁有該點的副本。因此，在這種通信模型中，當(dāng)多個工作節(jié)點并發(fā)訪問同一內(nèi)存地址時，需要考慮數(shù)據(jù)一致性的問題。

5.3 執(zhí)行模型

（1）同步執(zhí)行

許多圖算法由一系列迭代計算組成，在前后兩次迭代之間有一個全局的同步過程。這種執(zhí)行模式將計算節(jié)點之間的通信控制在每次迭代的結(jié)束，因此適合于那些計算量小而通信量大的算法。

（2）異步執(zhí)行

在圖中某個點的值有了更新值之后，立即將這個最新的更新值更新到該點上。在這種執(zhí)行模式中，節(jié)點之間的通信是不規(guī)則的，因此這種模式對于計算量不均衡，并且節(jié)點之間通信量小的算法非常適用。

5.4 圖的劃分

圖的劃分是進行高效圖計算的一個關(guān)鍵問題。通常，一個理想的圖劃分情況是各工作節(jié)點的任務(wù)量基本相同，同時各工作節(jié)點之間的通信量最小，但是這是一個NP難的問題?，F(xiàn)在，常用的圖劃分算法分為3類。

第一類，首先對輸入的圖數(shù)據(jù)進行一個預(yù)處理，將初始的圖數(shù)據(jù)轉(zhuǎn)化為某個特定的存儲格式，使得圖計算的訪存局部性更好或者使圖數(shù)據(jù)的數(shù)據(jù)量占用更少。比如GraphChi使用shard以及shard內(nèi)存源點的排序來增強磁盤訪存的局部性。另外，X-Stream使用簡單的流劃分來降低預(yù)處理的開銷。

第二類，在算法執(zhí)行過程中使用動態(tài)的重劃分，由于算法在執(zhí)行之前行為是無法預(yù)測的，所以這種動態(tài)劃分的策略可以根據(jù)現(xiàn)有算法的執(zhí)行狀態(tài)進行相應(yīng)地劃分，提高系統(tǒng)的性能。這種動態(tài)劃分策略需要對圖進行多次劃分，引入了圖劃分開銷。

第三類，使用edge-cut和vertexcut劃分。edge-cut將圖中的點均勻地劃分，并且保證跨不同劃分塊之間的邊最少。vertex-cut將邊均勻地劃分，同時保證跨不同塊之間的點最少?，F(xiàn)實生活中的許多大圖符合冪律分布[27]，因此，相比于edge-cut，使用vertex-cut有助于系統(tǒng)的負載均衡，但是圖計算系統(tǒng)需要使用以邊為中心的計算模型，如PowerGraph。

5.5 負載均衡

負載均衡的算法分為靜態(tài)負載均衡和動態(tài)負載均衡，靜態(tài)負載均衡在算法執(zhí)行之前進行任務(wù)的分配，但是由于算法在執(zhí)行之前無法預(yù)測其具體的行為，因而在算法的執(zhí)行過程中可能出現(xiàn)負載不均衡的情況。動態(tài)的負載均衡策略針對靜態(tài)負載策略進行了改進，即在算法的運行過程中，系統(tǒng)中任務(wù)少的工作節(jié)點可以從任務(wù)量大的工作節(jié)點“偷取”任務(wù)來實現(xiàn)負載均衡，提高系統(tǒng)的整體性能。

5.6 容錯

容錯在分布式圖處理系統(tǒng)中是需要解決的一個問題。在分布式處理系統(tǒng)中，每臺機器都會有一定的概率出錯失效，如果不加以處理，將對系統(tǒng)產(chǎn)生嚴(yán)重的影響。常見的分布式圖處理系統(tǒng)使用主從節(jié)點的方式，在這種構(gòu)建方式中，主節(jié)點負責(zé)整個系統(tǒng)的管理和調(diào)度，從節(jié)點負責(zé)具體的計算。主要的容錯方式有多副本策略、日志重做策略等。在多副本策略中，當(dāng)主工作節(jié)點執(zhí)行其任務(wù)時，另外有一個工作節(jié)點作為副本工作節(jié)點會執(zhí)行相同的任務(wù)；當(dāng)主節(jié)點失效時，副本會接管主節(jié)點的工作任務(wù)，這種容錯方式基本沒有錯誤恢復(fù)時間，但是會消耗掉很多計算和內(nèi)存資源。在日志重做的策略中，使用checkpoint或者log的方式記錄工作節(jié)點的計算操作，當(dāng)機器出現(xiàn)失效時，可以將記錄的操作重做來進行恢復(fù)，這種恢復(fù)方式會消耗一定的恢復(fù)時間，但是對計算和內(nèi)存資源的消耗相對較少。

6 結(jié)論及未來研究方向

本文介紹了幾個典型的分布式大圖處理系統(tǒng)和單機大圖處理系統(tǒng)，這兩種類型的系統(tǒng)有著各自的優(yōu)點和缺點。對于分布式系統(tǒng)，其特點是計算能力強，能夠應(yīng)對不同的計算需求，但是編程模型和系統(tǒng)的構(gòu)建（計算的協(xié)調(diào)和容錯機制）比較復(fù)雜；對于單機系統(tǒng)，其特點是編程和計算模型簡單，硬件開銷很低，但是計算能力有限，無法滿足某些計算需求。從計算模型來看，現(xiàn)在大圖計算的計算模型主要分為兩種：以點為中心的計算模型和以邊為中心的計算模型。在分布式處理系統(tǒng)Pregel、GraphLab等以及單機系統(tǒng)GraphChi主要使用了以點為中心的計算模型，這種計算模型更易于編程和理解，以邊為中心的計算模型主要用于單機的系統(tǒng)，如X-Stream。除了這兩種主要的計算模型之外，還有一些系統(tǒng)從數(shù)據(jù)的局部性出發(fā)，提出一些新的計算模型來提升系統(tǒng)的性能，但從本質(zhì)上來說，這些計算模型是基于以點為中心的計算模型，只是針對數(shù)據(jù)的布局，做出了相應(yīng)的修改。

盡管現(xiàn)在有許多針對大圖計算系統(tǒng)的研究工作被提出，但是從系統(tǒng)角度來看，在大圖處理系統(tǒng)上還有許多值得深入研究的領(lǐng)域。在分布式圖計算系統(tǒng)方面，設(shè)計一套高效、合理的圖劃分策略，不僅可以減少集群中各節(jié)點的通信開銷，而且可以保證機器間的負載均衡，在這方面已經(jīng)有一些相關(guān)的研究，但仍然值得更深入的研究。另外，容錯也是分布式系統(tǒng)改善性能的一個重要方面，現(xiàn)在主要的容錯方法有主副本備份容錯、校驗點容錯等，目的是在減少容錯開銷的同時盡可能地提高錯誤恢復(fù)的速度。在單機圖計算系統(tǒng)方面，由于計算能力的限制，有效的圖劃分策略并且使用與劃分策略相匹配的計算模型來增強計算的局部性是研究的熱點。另一方面，應(yīng)該充分發(fā)揮機器的多核特點，使得I/O和計算并行，并且提高計算時的并行度，這兩點也是值得深入研究的方向。

[1] Lumsdaine A, Gregor D, Hendrickson B,et al. Challenges in parallel graph processing. Parallel Processing Letters, 2007, 17(1): 5～20

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

[3] Gregor D, Lumsdaine A. The parallel BGL: a generic library for distributed graph computations. Proceedings of Parallel Object-Oriented Scientic Computing (POOSC), Glasgow, UK, 2005

[4] Chan A, Dehne F, Taylor R. CGMGRAPH/ CGMLIB: implementing and testing CGM graph algorithms on PC clusters and shared memory machines. International Journal of High Performance Computing Applications, 2005, 19(1): 81～97

[5] Malewicz G, Austern M, Bik A J C,et al. Pregel: a system for large-scale graph processing. Proceedings of ACM Special Interest Group on Management of Data, Indianapolis, IN, USA, 2010: 135～146

[6] Low Y C, Bickson D, GonzalezJ,et al. Distributed GraphLab: a framework for machine learning in the cloud. Proceedings of the VLDB Endowment (PVLDB), 2012,5(8): 716～727

[7] Gonzalez J E, Low Y C, Gu H J,et al. Power graph: distributed graphparallel computation on natural graphs.Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation, Hollywood, CA, USA, 2012: 17～30

[8] GonzalezJ E, Xin R S, Dave A,et al. Graphx: graph processing in a distributed dataflow framework. Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation, Broomfield, CO, USA, 2014: 599～613

[9] Chen R, Ding X, Wang P,et al. Computation and communication efficient graph processing with distributed immutable view. Proceedings of High-Performance Parallel and Distributed Computing, New York, USA, 2014: 215～226

[10] Yan D, Cheng J, Lu Y,et al. Blogel: a block-centric framework for distributed computation on real-world graphs. Proceedings of the VLDB Endowment (PVLDB), 2014, 7(14): 1981～1992

[11] Yuan P P, Zhang W Y, Xie C F,et al. Fast iterative graph computation: a path centric approach. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Piscataway, NJ, USA , 2014: 401～412

[12] Kyrola A, Blelloch G, Guestrin C,et al. GraphChi: large-scale graph computation on just a PC. Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation, Hollywood, CA, USA, 2012: 31～46

[13] Roy A, Mihailovic I, Zwaenepoel W. X-stream: edge-centric graph processing using streaming partitions. Proceedings of ACM Symposium on Operating Systems Principles, Farmington, PA, USA, 2013: 472～488

[14] ChengJ F, Liu Q, Li Z G,et al. VENUS: vertex-centric streamlined graph computation on a single PC. Proceedings of the 31st IEEE International Conference on Data Engineering, Seoul, Korea, 2015: 1131～1142

[15] Zhu X W, Han W T, Chen W G. Grid graph: large-scale graph processing on a single machine using 2-level hierarchical partitioning. Proceedings of the 2015 USENIX Conference on Usenix Annual Technical Conference, Santa Clara, CA, USA, 2015: 375～386

[16] Valiant Leslie G. A bridging model for parallel computation. Communications of the ACM, 1990, 33(8): 103～111

[17] Low Y C, Gonzalez J, Kyrola A,et al. GraphLab: a new framework for parallel machine learning. Proceedings of Conference on Uncertainty in Artificial Intelligence, Catalina Island, California, USA, 2010

[18] Baraba′si A L, Albert R. Emergence of scaling in random networks. Science,1999, 286(5439): 509～512

[19] Gharaibeh A, Costa L B, Santos-Neto E,et al. On graphs, GPUs, and blind dating: a work load to processor matchmaking quest. Proceedings of IEEE the 27th International Symposium on Parallel and Distributed Processing, Washington DC, USA, 2013: 851～862

[20] Fu Z S, Personick M, Thompson B. MapGraph: a high level API for fast development of high performance graph analytics on GPUs. Proceedings of Graph Data-management Experiences & Systems, Utah, USA, 2014: 1～6

[21] Khorasani F, Vora K, Gupta R,et al. CuSha: vertex-centric graph processing on GPUs. Proceedings of the International ACM Symposium on High-Performance Parallel and Distributed Computing, Vancouver, Canada, 2014: 239～252

[22] Han W S, Lee S, Park K,et al. TurboGraph: a fast parallel graph engine handling billion-scale graphs in a single PC. Proceedings of the 19th ACM SIGKDD Conference on Knowledge Discovery andData Mining, Chicago, USA, 2013: 77～85

[23] Zheng D, Mhembere D, Burns R,et al. FlashGraph: processing billion-node graphs on an array of commodity SSDs. Proceedings of the 13th USENIX Conference on File and Storage Technologies, Santa Clara, CA, USA, 2015: 45～58

吳城文，男，清華大學(xué)計算機科學(xué)與技術(shù)系碩士生，主要研究領(lǐng)域為大數(shù)據(jù)圖計算。

張廣艷，男，博士，清華大學(xué)計算機科學(xué)與技術(shù)系副教授，中國計算機學(xué)會會員，主要研究領(lǐng)域為大數(shù)據(jù)計算、網(wǎng)絡(luò)存儲、分布式計算。

鄭緯民，男，清華大學(xué)教授、博士生導(dǎo)師，中國計算機學(xué)會理事長，目前主要從事并行與分布式計算、存儲系統(tǒng)的研究工作，主持和參與多項國家“973”計劃、“863”計劃、國家自然科學(xué)基金項目。近年來在IEEE TC/ IEEE TPDS/ACM TOS/FAST等本領(lǐng)域頂級期刊與國際會議發(fā)表論文40余篇。

Wu C W, Zhang G Y, Zheng W M. Reviewing large graph computing from a system perspective. Big Data Research, 2015028

Reviewing Large Graph Computing from a System Perspective

Wu Chengwen, Zhang Guangyan, Zheng Weimin
Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

Large graphcomputing has been a fundamental computing pattern in both academic and industry field, and it was applied to a lot of practical big data applications, such as social network analysis, web page search, and goods recommendation. In general, most of large graphs scale to billions of vertices, and corresponding to hundreds billions of edges, which brings us challenges of efficient graph processing. Therefore, the basic feature and challenges of current large graph computing, typical computing models, and representative distributed, and single machine large graph processing systems were introduced. Then, some key technologies employed in large graph computing were summarized. Finally, some research directions in large graph computing from a system perspective were given.

big data computing, large graph computing, computing model, computing system

10.11959/j.issn.2096-0271.2015028

2015-08-19

國家重點基礎(chǔ)研究發(fā)展計劃（“973”計劃）基金資助項目（No.2014CB340402），國家自然科學(xué)基金資助項目（No.61170008，No.61272055）

Foundation Items:The National Basic Research Program of China(973 Program)(No.2014CB340402), The National Natural Science Foundation of China(No.61170008，No.61272055)

吳城文, 張廣艷, 鄭緯民. 從系統(tǒng)角度審視大圖計算. 大數(shù)據(jù), 2015028