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

吳城文，張廣艷，鄭緯民

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

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

吳城文，張廣艷，鄭緯民

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

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

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

1 引言

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

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

圖1 以點(diǎn)為中心的計(jì)算模型[10]

圖2 以邊為中心的計(jì)算模型[10]

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

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

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

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

（1）局部性差

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

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

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

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

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

（4）高訪存/計(jì)算比

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

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

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

3.1 Pregel

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

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

3.2 Giraph

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

圖3 Pregel點(diǎn)的狀態(tài)機(jī)[5]

3.3 GraphLab和PowerGraph

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

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

圖4 GraphLab計(jì)算框架[17]

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

圖5 PowerGraph切割點(diǎn)集劃分及通信模式[7]

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

3.4 GraphX

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

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

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

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

4.1 GraphChi

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

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

圖7 并行滑動(dòng)窗口計(jì)算模型[12]

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

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

4.2 X-Stream

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

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

4.3 VENUS

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

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

圖9 以點(diǎn)為中心的流線型計(jì)算模型[14]

4.4 GridGraph

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

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

圖11 雙重滑動(dòng)窗口計(jì)算模型示例[15]

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

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

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

5.1 異構(gòu)計(jì)算平臺(tái)

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

5.2 通信模型

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

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

5.3 執(zhí)行模型

（1）同步執(zhí)行

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

（2）異步執(zhí)行

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

5.4 圖的劃分

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

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

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

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

5.5 負(fù)載均衡

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

5.6 容錯(cuò)

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

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

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

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

[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é)計(jì)算機(jī)科學(xué)與技術(shù)系碩士生，主要研究領(lǐng)域?yàn)榇髷?shù)據(jù)圖計(jì)算。

張廣艷，男，博士，清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系副教授，中國(guó)計(jì)算機(jī)學(xué)會(huì)會(huì)員，主要研究領(lǐng)域?yàn)榇髷?shù)據(jù)計(jì)算、網(wǎng)絡(luò)存儲(chǔ)、分布式計(jì)算。

鄭緯民，男，清華大學(xué)教授、博士生導(dǎo)師，中國(guó)計(jì)算機(jī)學(xué)會(huì)理事長(zhǎng)，目前主要從事并行與分布式計(jì)算、存儲(chǔ)系統(tǒng)的研究工作，主持和參與多項(xiàng)國(guó)家“973”計(jì)劃、“863”計(jì)劃、國(guó)家自然科學(xué)基金項(xiàng)目。近年來(lái)在IEEE TC/ IEEE TPDS/ACM TOS/FAST等本領(lǐng)域頂級(jí)期刊與國(guó)際會(huì)議發(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

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（“973”計(jì)劃）基金資助項(xiàng)目（No.2014CB340402），國(guó)家自然科學(xué)基金資助項(xiàng)目（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)角度審視大圖計(jì)算. 大數(shù)據(jù), 2015028