《大数据》2015年第3期“网络大数据专题”——从系统角度审视大图计算
從系統角度審視大圖計算
吳城文，張廣艷，鄭緯民
（清華大學計算機科學與技術系 北京 100084）
摘要：大圖計算已經成為學術界和工業界的一種基本計算模式，并且已經被應用到許多實際的大數據計算問題上，如社交網絡分析、網頁搜索以及商品推薦等。對于這些問題，大圖的規模約有10億級的點以及1 000億級的邊，這樣的規模給大圖的高效處理帶來了諸多挑戰。為此，介紹了大圖計算的基本特征和挑戰、典型的計算模型以及具有代表性的分布式、單機處理系統，同時對圖處理系統中的關鍵技術進行總結，最后從系統的角度給出大圖計算可能的一些研究方向。
關鍵詞：大數據計算；大圖計算；計算模型；計算系統
doi: 10.11959/j.issn.2096-0271.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)
Abstract: 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 associal 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 graphcomputing, 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.
Key words: big data computing, large graphcomputing, computing model, computing system
論文引用格式： 吳城文, 張廣艷, 鄭緯民. 從系統角度審視大圖計算. 大數據, 2015028
Wu C W, Zhang G Y, Zheng W M. Reviewing large graph computing from a system perspective. Big Data Research, 2015028
1 引言
圖可以用來表征不同實體間復雜的依賴關系。因而，在許多實際的應用當中，如社交網絡分析、網頁搜索、商品推薦等都可以使用圖來進行問題的建模和分析。然而，在大數據時代，這類問題的規模通常十分龐大，以社交網絡為例，Facebook在2014年7月的用戶已經達到22億戶，而用戶之間的關系數量則更多，以數據的方式進行存儲通常會占用幾百GB甚至TB級的存儲量。因此，大圖計算不僅是計算密集型，同時也是存儲密集型問題，如何在可以接受的時間內對大圖進行計算，是需要解決的難題。
通常，為了快速地對大圖進行處理，常常會使用分布式并行計算的思想，但是由于圖計算本身特征使得在實現并行圖計算時，不能使用傳統科學計算領域的并行模式（計算偏微分方程）[1]；且以往在處理大數據問題上的map/reduce[2]模式，在處理圖問題時效率極低；另外，并行圖算法庫Parallel BGL[3]或CGMgraph[4]沒有容錯機制。基于以上幾點，需要一套符合大圖計算特點的高效分布式并行計算框架。現在一些常見的分布式處理系統有Pregel[5]及其對應的開源實現Giraph以及GraphLab[6]、PowerGraph[7]、GraphX[8]和Cyclops[9]。這些分布式系統大部分采用“think like a vertex”的思想，即以點為中心（vertex-centric）的計算模型，如圖1[10]所示。在這種模型中，所有的點從其入邊的鄰點獲取數據，執行用戶自定義的函數對自己的狀態進行更新，然后將自己的更新狀態通過消息發給其出邊的鄰點。還有少數一些分布式系統采用了其他的計算模型，如PowerGraph的以邊為中心（edge-centric）的計算模型，如圖2所示。在這種計算模型當中，首先依次遍歷所有的邊，將邊的源點的更新值通過其出邊傳遞給目的點，然后遍歷所有的更新值，將更新值更新到目的點（在PowerGraph中將gather操作移到了scatter操作前面）。另外，還有以塊[11]、路徑[12]為中心的計算模型，在這類計算模型中，針對圖結構來進行圖劃分，增加了計算的局部性，但是也存在圖劃分時間過長等問題。
圖 1 以點為中心的計算模型
圖 2 以邊為中心的計算模型
分布式圖處理系統隨著問題規模的擴大具有很好的拓展性，但是在提高系統處理效率方面仍然面臨許多挑戰。比如圖的劃分，要提高系統性能需要在保證集群各節點負載均衡的情況下，使得集群內各節點的通信量最少，是一個NP難問題。此外，一個分布式系統需要解決集群內各節點協同工作、容錯等一系列問題，而這類問題對系統的性能有重要的影響。另一方面，對于使用分布式系統的程序員來說，環境的搭建、編寫分布式程序比較復雜，而且程序的調試和優化又相對困難。基于此，最近一些大圖計算的研究工作，在使用單臺計算機進行大圖計算處理上有了一些新的成果，如以點為中心的計算模型的GraphChi[13]和以邊為中心的計算模型的X-Stream[10]，另外還有VENUS[14]、GridGraph[15]等。這些成果極大地降低了大圖計算的成本開銷，同時能夠達到甚至好于一些分布式圖計算系統處理時延。本文將介紹當前大圖計算的主要特征及挑戰，從系統角度給出當前大圖處理系統的主要特征及其研究成果，并對圖處理系統中的關鍵技術進行總結，最后給出大圖計算系統方面可能的研究方向。
2 大圖計算的特征及挑戰
大圖計算是大數據計算中的一個子問題，除了滿足大數據的基本特性之外，大圖計算還有著自身的計算特性，相應地面臨著新的挑戰。
（1）局部性差
圖表示著不同實體之間的關系，而在實際的問題當中，這些關系經常是不規則和無結構的，因此圖的計算和訪存模式都沒有好的局部性，而在現有的計算機體系架構上，程序的性能獲得往往需要利用好局部性。所以，如何對圖數據進行布局和劃分，并且提出相應的計算模型來提升數據的局部性，是提高圖計算性能的重要方面，也是面臨的關鍵挑戰。
（2）數據及圖結構驅動的計算
圖計算基本上完全是由圖中的數據所驅動的。當執行圖算法時，算法是依據圖中的點和邊來進行指導，而不是直接通過程序中的代碼展現出來。所以，不同的圖結構在相同的算法實現上，將會有著不同的計算性能。因此，如何使得不同圖結構在同一個系統上都有較優的處理結果，也是一大難題。
（3）圖數據的非結構化特性
圖計算中圖數據往往是非結構化和不規則的，在利用分布式框架進行圖計算時，首先需要對圖進行劃分，將負載分配到各個節點上，而圖的這種非結構化特性很難實現對圖的有效劃分，從而達到存儲、通信和計算的負載均衡。一旦劃分不合理，節點間不均衡的負載將會使系統的拓展性受到嚴重的限制，處理能力也將無法符合系統的計算規模。
（4）高訪存/計算比
絕大部分的大圖計算規模使得內存中無法存儲下所有的數據，計算中磁盤的I/O必不可少，而且大部分圖算法呈現出迭代的特征，即整個算法需要進行多次迭代，每次迭代需要遍歷整個圖結構，而且每次迭代時所進行的計算又相對較少。因此，呈現出高的訪存/計算比。另外，圖計算的局部性差，使得計算在等待I/O上花費了巨大的開銷。
3 分布式大圖計算系統
本節將介紹幾個典型的大圖處理的分布式系統，重點突出每個系統的特點。
3.1 Pregel
Pregel是由Google公司開發的分布式處理圖系統，其主要的設計思想是基于BSP（bulk synchronous parallel）[16]。在此思想上，Pregel使用了以點為中心的計算模型，對整個圖根據點進行劃分，將不同的點以及相關的鄰邊存儲到不同的計算機器上。在Pregel中，用戶可以自定義點的compute()函數，每個點多次迭代執行這個函數，并最終得出整個圖的計算結果。具體地，在每一次迭代（super step）中，每個活躍的點（active vertex）會執行compute()函數，在這個函數中，該點讀取在前一次迭代中其鄰點發送的消息，通過這些消息計算自己新的狀態，再將自己最新的狀態通過出邊發送給其鄰點（鄰點將會在下一次迭代中收到這些消息），然后該點會進入不活躍狀態（inactive），如圖3所示。當不活躍的點（inactive vertex）在下一輪收到消息時，就會重新處于活躍狀態。當所有活躍的點執行完compute()函數之后，當前迭代結束，并且進入到下一次迭代。如果系統當中所有的點都處于不活躍狀態，并且沒有任何新的消息，算法結束。
圖 3 Pregel 點的狀態機
Pregel使用了消息傳遞（message passing）的方式進行計算節點之間的通信，在一次迭代中每個點可以向其他點發送任意量的消息，而這些消息將會在下一次迭代中被對應的點讀取。在分布式的環境中，為了減少機器間的通信量，提升計算的性能，當點的compute()函數的操作符合交換律和結合律時，Pregel可以支持用戶實現combiner()函數，把從機器Mi到另一臺機器 Mj上點v的所有消息合并成一條消息。
3.2 Giraph
Giraph構建在Hadoop之上，是對Google公司Pregel的開源實現。 Facebook使用Giraph來進行社交關系圖的分析。為了提升系統的性能，在原有Giraph基礎上增加了一些優化的措施。Facebook在Giraph的加載圖數據、寫回圖數據以及計算階段引入了多進程，提升了系統的整體性能，尤其對計算密集型的應用，引入多線程可以使性能隨著處理器的增加獲得接近線性的加速比。
3.3 GraphLab和PowerGraph
與Pregel的同步數據推送的BSP模型不同，GraphLab使用異步的GAS（gather、 apply、scatter）模型來實現大圖分布式并行計算。 GraphLab使用共享內存（shared memory）的方式來實現以點為中心的計算模式，在這種方式下，每個點可以直接讀取和修改其鄰點和鄰邊的值。在GraphLab上實現算法時，用戶需要實現符合算法要求的GAS函數，在算法執行時，圖的每個點都會執行該函數。
在gather階段，每個執行GAS函數的活躍點從其鄰點和鄰邊獲取數據，然后使用這些值來計算自己的更新值，這里計算操作必須滿足交換律和結合律。在apply階段，活躍點將原來的舊值更新為計算得到的新值。在scatter階段，活躍的點會通過鄰邊激活對應的鄰點。如圖4所示，在GraphLab中使用一個全局的調度器，各個工作節點通過從該調度器獲取活躍的點來進行計算，這些正在被計算的點也可能會將其鄰點調入調度器中。最后當調度器中沒有任何可調度的點時，算法終止。這種調度器的使用使得GraphLab同時支持算法的異步調度執行和同步調度執行。
圖 4 GraphLab 計算框架
在同步執行（synchronous execution）計算模式下，每個點或者邊的更新不能馬上被當前迭代中接下來的計算感知到，直到當前迭代結束時，在下一次迭代當中才能讀取到更新的值。異步執行（asynchronous execution）與同步執行不同，點或者邊的更新能夠馬上被接下來的計算所感知并使用到，這種計算模式可以使得如PageRank的一些算法收斂速度更快，但也同時會導致數據競爭，從而產生額外的計算開銷。另外，在分布式系統中，這種模式會產生隨機的信息傳遞，因而也會產生較大的通信開銷。一般來說，對于計算密集型的算法（如BP）來說，更適合使用異步計算的模式。
PowerGraph包含在GraphLab 2.2中，是在GraphLab的基礎上對符合冪律分布（power-law）[18]的自然圖計算性能的改進，其主要改進是在圖的劃分上。如圖5所示， PowerGraph使用了Vertex-cut的圖劃分策略，將待處理的圖以切割點集的方式進行劃分，將那些度極大的點的邊分割給不同的計算節點，同時，將對應的點也復制給這些計算節點作為鏡像（mirror）點。具體計算時，每個主點及其對應鏡像點在本地執行gather操作，隨后鏡像點將自己的計算結果發送給主點，收到全部計算結果后，主點執行apply操作，并且將更新值發送給所有鏡像點，最后主點和鏡像點進行scatter操作。
圖 5 PowerGraph 切割點集劃分及通信模式
3.4 GraphX
如圖6所示，GraphX是構建在分布數據流框架Spark上的分布式圖處理系統。GraphX支持Pregel和GraphLab的計算模型，并且拓展了Spark中的RDD（resilient distributed dataset，彈性分布數據集），引入了RDG（resilient distributed graph，彈性分布圖），這種結構可以支持許多圖操作，因此現有的大多數圖算法都可以使用系統中提供的基本操作算子（如join、map和group-by）來實現，并且實現十分簡單。為了利用Spark中這種算子操作，GraphX重構了新的vertex-cut圖劃分方法，將圖劃分成水平分區的頂點和邊的集合。GraphX的性能比直接使用分布式數據流框架好一個數量級，稍差于GraphLab。另外，由于GraphX是構建在Spark之上的，所以GraphX能夠得到低開銷的容錯和透明的錯誤恢復支持。
圖 6 GraphX 的層次結構（括號中為代碼行數）
4 單機大圖計算系統
隨機單臺計算機處理能力和存儲能力的提升，再加上人們對于圖計算模式研究的深入，一些在單機上處理大圖計算的系統被提出，這些系統有著很好的圖計算性能，同時相比分布式系統，其低硬件成本和低功耗的優勢明顯。本節將介紹幾個代表性的單機大圖計算系統。
4.1 GraphChi
GraphChi是一個基于磁盤的單機大圖處理系統。在大圖計算中，計算的訪存局部性非常差，嚴重影響到計算的性能。特別地，在單機情況下系統的計算能力十分有限，因此，為了提升計算性能， GraphChi使用了具有創新性的磁盤數據布局和對應的計算模型來減少磁盤的隨機訪問；使用選擇性的調度來加速算法的收斂。
磁盤數據的布局和計算模型。GraphChi在計算前首先會對圖數據進行預處理，將輸入的圖劃分成多個shard，每個shard中存儲對應點集的所有入邊，并且將入邊按照其源節點的ID進行排序，劃分時需要保證每個shard中邊的數量大致相同，每個shard都能夠加載進內存。GraphChi使用以點為中心的計算模型，使用并行滑動窗口（parallel sliding window）來加載數據進行計算，如圖7所示，每次（interval）計算一個子圖，即一個shard所對應點集中所有點的值，需要順序讀取某個點集對應的入邊（深灰色部分）以及該點集在其他shard中所對應的出邊（黑色矩形框部分），這種數據布局和計算模型可以保證每次計算的I/O是順序的。這樣，一次迭代計算整個圖中所有點的值，多次迭代，直到算法收斂。
圖 7 并行滑動窗口計算模型
選擇性的調度。在GraphChi中可以使用選擇調度性調度（selective scheduling）策略來加快圖中某些點的收斂，尤其是對這些在兩次相鄰的迭代當中變化很顯著的點。在點執行update()函數時，類似GraphLab中的apply()，可以將其鄰點加入調度器中，進行選擇性的調度。
4.2 X-Stream
與GraphChi所使用的以點為中心的計算模型不同，X-Stream使用以邊為中心的計算模型，并且所有的狀態都保存在點中。X-Stream的計算過程主要分為3個階段：scatter、shuffle和gather，如圖8所示。在scatter階段，X-Stream依次遍歷每一條邊，判斷邊的源節點是否產生更新，如果有更新產生，將邊通過出邊發送給目的節點。shuffle階段是在對圖進行劃分之后，需要增加的一個不同劃分塊之間更新數據交換的階段，主要是為了降低在scatter階段的隨機寫開銷。在gather階段，X-Stream依次遍歷在scatter階段產生的所有更新，并更新對應點的狀態值。X-Stream以邊為中心的計算模型對邊進行順序訪問，可以充分發揮磁盤的等二級存儲介質的順序訪問高帶寬加速圖計算，但是在X-Stream中對點的訪問還是隨機的，為了對此進行優化，進一步提高計算性能，X-Stream對圖的點集合均等劃分成小的子點集合，每個子點集合其每個點所有的出邊也對應地組成一個邊的劃分集合。對點的劃分主要滿足每個子集合中的點都能夠存儲到內存中，這樣當計算每個劃分塊時，對點的隨機訪問開銷能夠極大地降低，為X-Stream進行劃分后的計算模型。
圖 8 X-Stream 以邊為中心的計算模型（Uin/Uout 為輸入 / 輸出緩存）
在對圖進行劃分之后，每個劃分塊在scatter階段，首先將所有的更新值寫在本地的一個輸出緩存中，當所有的塊都完成scatter之后，進入一個shuffle階段，這個階段的主要工作是將所有劃分塊的更新進行分配，將更新分配到對應的劃分塊的輸入緩存中，作為gather階段的輸入，對點的狀態進行更新處理。相比于GraphChi，X-Stream對所有邊進行順序訪問，能夠充分發揮磁盤等二級存儲介質的順序帶寬的速度，同時預處理階段（簡單的散列圖劃分操作）無須進行開銷巨大的排序處理，因此能夠獲得較好的圖處理性能。
4.3 VENUS
盡管GraphChi在大圖處理上能夠取得較好的計算效果，但是也存在如下的缺陷：預處理需要對邊的源節點進行排序，開銷大；圖數據的加載和計算是分開的，沒有充分利用磁盤和I/O的并行來提高計算性能；對shard內的邊排序后，每個點所對應的邊不在相鄰的位置，緩存局部性不高。
基于以上的這幾點觀察，筆者提出了如圖9所示的以點為中心的流線型（vertex-centric streamlined）計算模型。在這種計算模型中，筆者分別構建了g-shard和v-shard，其中g-shard與GraphCHi中shard的概念類似，存儲了一個子點集對應的所有入邊，但是不用對邊進行排序，而是將目的頂點相同的邊存儲在相鄰的位置，v-shard存儲對應一個g-shard中所有目的頂點和源頂點的值。另外，使用了一個全局的點值表，v-shard從其中讀取和寫回對應的點值。系統計算點的更新值時，無須像GraphChi將所有的入邊和出邊同時加載進內存，只需將入邊加載進內存，同時節點更新后，不用再將更新值寫入出邊，這樣可以極大地減少I/O。此外，當加載完g-shard中一個點的所有入邊時，即可對該點的值進行計算，重疊了I/O和CPU的時間開銷，極大地提高了系統的性能。實驗結果表明，VENUS的性能顯著地好于GraphChi和X-Stream。
圖 9 以點為中心的流線型計算模型
4.4 GridGraph
在X-Stream中，在scatter和gather階段之間，還需要一個shuffle階段將每個劃分在scatter階段產生的更新值分配到對應劃分的輸入緩存中，供gather階段進行計算。在scatter階段，更新值會有O(|E|)這樣的規模，其中|E|代表圖中邊的數量。所以，當內存不足時，需要將一部分緩存先寫入磁盤，并且在gather階段需要將寫入磁盤的更新值重新讀入內存，因此，在此過程中可能會觸發較多的I/O，嚴重影響系統的性能。
為此，GridGraph提出了如圖10所示的格子劃分方式。首先，將整個點集劃分成相同大小的P份子點集，然后將邊以行和列劃分成格子，每一行對應在某個子點集內的點所對應的所有出邊，每一列對應在某個子點集內的點所對應的所有入邊。對應這種圖的劃分方法，筆者提出了雙重滑動窗口的計算模型（如圖11所示），是圖10（a）中圖結構的PageRank第一次迭代過程，計算點的更新值需要讀取其入邊源節點的值，為此從上到下，依次讀取該列每個格子內的邊進行計算，然后當一列計算完畢后，即完成一個子點集中點的值的計算，窗口滑動到下一列，繼續進行計算，直至所有的格子都遍歷完畢。在這種計算模型中，值的更新計算操作必須符合交換律，另外，這種方式點的更新是就地更新，不會產生中間的更新結果，極大地減少了I/O，同時，點的數據訪問的局部性也有了提升。在進行圖劃分時，使用二級的圖劃分策略，即先將圖劃分成Q份，使得每個格子的邊都能夠存儲進內存中，然后再對剛才的每個格子進行劃分，使得每個小格子能夠存儲進最后一級cache（LLC）當中。另外，GridGraph還支持選擇性的調度，在BFS和WCC這樣的算法中，可以極大地減少I/O，提高計算性能。
圖 10 GridGraph 的圖劃分例子
圖 11 雙重滑動窗口計算模型示例
5 大圖計算中的關鍵技術
本節將介紹在分布式和單機圖處理系統中常用的技術。
5.1 異構計算平臺
在異構計算系統中，存在著計算能力和計算特點不同的計算單元。比如，GPU具有比CPU更強的多線程并行計算能力，因此在異構系統中，CPU會把一些或者全部的計算交給GPU來執行。在圖計算領域，相關的異構計算系統已經被開發出來。TOTEM[19]會將度高的點交給CPU計算執行，而將度低的點交給GPU來執行。而另外一些系統，如MapGraph[20]和CuSha[21]等，會將整個圖都交給GPU來執行。除了GPU和CPU的異構圖計算平臺之外，一些研究人員發現，solid-state drive（SSD）有著與傳統hard disk drive（HDD）不同的訪存特性。一些圖計算系統（如TurboGraph[22]和FlashGraph[23]）針對SSD對計算系統進行了優化，使得系統在SDD上有著很高的計算性能。目前使用異構計算的平臺的圖處理系統主要是單機圖處理系統。
5.2 通信模型
在消息傳遞的通信模型中，算法中點的狀態保存在本地，通過消息傳遞的方式更新在其他機器上點的狀態。在Pregel和Giraph中，使用了消息傳遞的通信模型，為了確保所有更新的數據可用，需要在前后兩次迭代計算之間加入一個同步操作。
在共享內存的通信模型中，各個處理單元允許并發訪問和修改相同地址的數據。在一些分布式的計算系統（如GraphLab和PowerGraph）中，使用了虛擬共享內存來實現各計算節點之間的透明的同步。在這些圖處理系統中，使用了假點（ghost vertex）的方式來實現虛擬共享內存。在假點的這種實現策略中，圖中的每個點有一個歸屬的工作節點，另外有一些工作節點擁有該點的副本。因此，在這種通信模型中，當多個工作節點并發訪問同一內存地址時，需要考慮數據一致性的問題。
5.3 執行模型
（1）同步執行
許多圖算法由一系列迭代計算組成，在前后兩次迭代之間有一個全局的同步過程。這種執行模式將計算節點之間的通信控制在每次迭代的結束，因此適合于那些計算量小而通信量大的算法。
（2）異步執行
在圖中某個點的值有了更新值之后，立即將這個最新的更新值更新到該點上。在這種執行模式中，節點之間的通信是不規則的，因此這種模式對于計算量不均衡，并且節點之間通信量小的算法非常適用。
5.4 圖的劃分
圖的劃分是進行高效圖計算的一個關鍵問題。通常，一個理想的圖劃分情況是各工作節點的任務量基本相同，同時各工作節點之間的通信量最小，但是這是一個NP難的問題。現在，常用的圖劃分算法分為3類。
第一類，首先對輸入的圖數據進行一個預處理，將初始的圖數據轉化為某個特定的存儲格式，使得圖計算的訪存局部性更好或者使圖數據的數據量占用更少。比如GraphChi使用shard以及shard內存源點的排序來增強磁盤訪存的局部性。另外， X-Stream使用簡單的流劃分來降低預處理的開銷。
第二類，在算法執行過程中使用動態的重劃分，由于算法在執行之前行為是無法預測的，所以這種動態劃分的策略可以根據現有算法的執行狀態進行相應地劃分，提高系統的性能。這種動態劃分策略需要對圖進行多次劃分，引入了圖劃分開銷。
第三類，使用edge-cut和vertex-cut劃分。edge-cut將圖中的點均勻地劃分，并且保證跨不同劃分塊之間的邊最少。vertex-cut將邊均勻地劃分，同時保證跨不同塊之間的點最少。現實生活中的許多大圖符合冪律分布[27]，因此，相比于edge-cut，使用vertex-cut有助于系統的負載均衡，但是圖計算系統需要使用以邊為中心的計算模型，如PowerGraph。
5.5 負載均衡
負載均衡的算法分為靜態負載均衡和動態負載均衡，靜態負載均衡在算法執行之前進行任務的分配，但是由于算法在執行之前無法預測其具體的行為，因而在算法的執行過程中可能出現負載不均衡的情況。動態的負載均衡策略針對靜態負載策略進行了改進，即在算法的運行過程中，系統中任務少的工作節點可以從任務量大的工作節點“偷取”任務來實現負載均衡，提高系統的整體性能。
5.6 容錯
容錯在分布式圖處理系統中是需要解決的一個問題。在分布式處理系統中，每臺機器都會有一定的概率出錯失效，如果不加以處理，將對系統產生嚴重的影響。常見的分布式圖處理系統使用主從節點的方式，在這種構建方式中，主節點負責整個系統的管理和調度，從節點負責具體的計算。主要的容錯方式有多副本策略、日志重做策略等。在多副本策略中，當主工作節點執行其任務時，另外有一個工作節點作為副本工作節點會執行相同的任務；當主節點失效時，副本會接管主節點的工作任務，這種容錯方式基本沒有錯誤恢復時間，但是會消耗掉很多計算和內存資源。在日志重做的策略中，使用checkpoint或者log的方式記錄工作節點的計算操作，當機器出現失效時，可以將記錄的操作重做來進行恢復，這種恢復方式會消耗一定的恢復時間，但是對計算和內存資源的消耗相對較少。
6 結論及未來研究方向
本文介紹了幾個典型的分布式大圖處理系統和單機大圖處理系統，這兩種類型的系統有著各自的優點和缺點。對于分布式系統，其特點是計算能力強，能夠應對不同的計算需求，但是編程模型和系統的構建（計算的協調和容錯機制）比較復雜；對于單機系統，其特點是編程和計算模型簡單，硬件開銷很低，但是計算能力有限，無法滿足某些計算需求。從計算模型來看，現在大圖計算的計算模型主要分為兩種：以點為中心的計算模型和以邊為中心的計算模型。在分布式處理系統Pregel、GraphLab等以及單機系統GraphChi主要使用了以點為中心的計算模型，這種計算模型更易于編程和理解，以邊為中心的計算模型主要用于單機的系統，如X-Stream。除了這兩種主要的計算模型之外，還有一些系統從數據的局部性出發，提出一些新的計算模型來提升系統的性能，但從本質上來說，這些計算模型是基于以點為中心的計算模型，只是針對數據的布局，做出了相應的修改。
盡管現在有許多針對大圖計算系統的研究工作被提出，但是從系統角度來看，在大圖處理系統上還有許多值得深入研究的領域。在分布式圖計算系統方面，設計一套高效、合理的圖劃分策略，不僅可以減少集群中各節點的通信開銷，而且可以保證機器間的負載均衡，在這方面已經有一些相關的研究，但仍然值得更深入的研究。另外，容錯也是分布式系統改善性能的一個重要方面，現在主要的容錯方法有主副本備份容錯、校驗點容錯等，目的是在減少容錯開銷的同時盡可能地提高錯誤恢復的速度。在單機圖計算系統方面，由于計算能力的限制，有效的圖劃分策略并且使用與劃分策略相匹配的計算模型來增強計算的局部性是研究的熱點。另一方面，應該充分發揮機器的多核特點，使得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: ageneric 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 memorymachines. International Journal of High Performance Computing Applications,2005, 19(1): 81~97
[5] Malewicz G, Austern M, Bik A JC, et al. Pregel:a system for large-scale graph processing. Proceedings of ACM Special InterestGroup 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 graph-parallel computation on natural graphs. Proceedings ofthe 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 andcommunication 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: ablock-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. Fastiterative graph computation: a path centric approach. Proceedings of theInternational Conference for High Performance Computing, Networking, Storageand 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] Cheng J 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 hierarchicalpartitioning. 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 onUncertainty in Artificial Intelligence, Catalina Island, California, USA, 2010
[18] Baraba′si A L, Albert R. Emergence of scalingin 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 andDistributed Processing, Washington DC, USA, 2013:851~862
[20] Fu Z S, Personick M, Thompson B. MapGraph: ahigh 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 ACMSymposium on High-Performance Parallel and Distributed Computing, Vancouver,Canada, 2014: 239~252
[22] Han WS, Lee S, Park K, et al. TurboGraph: afast parallel graph engine handling billion-scale graphs in a single PC.Proceedings of the 19th ACM SIGKDD Conference on Knowledge Discovery and DataMining, 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
總結
以上是生活随笔為你收集整理的《大数据》2015年第3期“网络大数据专题”——从系统角度审视大图计算的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： push ebp
- 下一篇： 如果已经知道某一CALL的具体作用,能否