圖是由點和邊構成的一種古老的數據結構，已有上百年曆史。由於其優秀的表達能力和堅實的數學基礎，圖已經在物理、生物、計算機科學等眾多領域得到了廣泛應用。僅以計算機科學領域為例，圖被用來表示通信網絡、數據組織、計算流和數據流等。當前廣泛應用的分佈式計算框架如Dryad、TensorFlow等均根據有向無環圖（Directed Acyclic Graph，DAG）作為基本的作業模型。而對互聯網和社交網絡拓撲結構的分析則揭示了其小世界（smallworld）和無尺度（scale-free）特性。隨著信息技術的持續進步以及數據量的不斷增長，圖上的運算面臨越來越多的挑戰，基於圖的數據處理和分析已經形成了“圖計算”這一專門的研究方向，吸引著越來越多的研究者投身其中。
與其他應用相比，圖計算應用具有以下幾個主要特點：
- 1. 具有很高的訪存計算比。即應用的很大一部分時間都花費在了數據讀寫（訪存）方面，而真正用於計算的時間並不多。對於這類應用而言，其性能的瓶頸在於內存和I/O帶寬，優化的關鍵在於提升數據加載速度，儘可能減少Cache-內存-外存之間的數據交換。此外，重疊計算和通信也會有所幫助。
- 2. 數據局部性差。數據局部性是為了應對處理器Cache、內存和外存的讀寫性能差異而引入的提升性能的重要舉措，其核心是提升Cache利用率。然而，由於計算模式的多樣性以及圖頂點之間關聯關係的複雜性，儘管已經有了不少優化數據局部性的措施，但現有的圖計算應用對系統 Cache的利用率通常都不高。
- 3. 類型與操作多樣。圖有很多種類型，從邊的連接關係來看，分為有向圖、無向圖和混合圖等；從圖本身的特性來看，分為正則圖、完全圖、二分圖、連通圖等。圖上的操作也是多種多樣的，從最簡單的度（degree）數統計、鄰接點查找、遍歷，到複雜的路徑查找、著色、流分析（如最大流最小切割）、子圖匹配、種子集擴充（seed set expansion），在應用中均有所涉及。二者耦合，產生了豐富的應用場景。
- 4. 規模巨大，結構不規則。隨著社交網絡的發展，現實生活中規模達數千萬乃至上億條邊的圖已經變得十分普遍。更為重要的是，這些圖往往遵循冪律（power law）分佈，即頂點的度數非常不均勻，一小部分頂點擁有大量的連接，而大量的點只有有限的幾條邊與之相連，給數據的高效處理帶來了巨大的困擾。
上述應用特點並不是孤立的，而是相互交織在一起的。類型與操作多樣表明，我們很難找到滿足所有應用場景的最優計算方式，甚至連次優方式都很難做到，這也是有大量相關工作存在的最根本的原因。從體系結構的角度來說，由於數據訪問速度的差異，高的訪存計算比意味著系統Cache的利用率十分重要，然而，圖數據本身局部性差使得其對Cache的利用率先天不足。圖的巨大規模超出了單臺物理機的處理能力，必須擴展到分佈式環境中去計算，而局部性差意味著系統需要耗費更多的時間進行大量數據的跨節點傳輸，而這進一步降低了數據處理的效率；在分佈式環境中，由於作業的結束時間就是最後一個任務的結束時間，各個節點之間的負載不均衡會極大影響應用的效率，而結構的不規則如果不加以精心處理，不可避免地會引起負載不均衡。綜上，圖計算的效率優化是一個非常複雜的問題，充滿了挑戰。
圖計算的一般模型：
計算的基本目標是描述清楚應用需求，在應用需求和硬件環境之間架起橋樑，使得需求中所指定的各種運算能夠高效地在給定的硬件上完成，圖計算也是如此。應用需求是通過編程模型來描述的，編程模型的易用性和表達能力在很大程度上直接決定了框架的生命力，同時也影響到執行優化的空間；而運算的完成則是由執行框架負責的，它在編程模型所描述的應用需求的指導下，結合硬件環境的特點，自動完成數據的劃分、任務到硬件環境的映射（即任務調度）、數據傳輸和任務執行管理。現有的執行框架通常都支持負載的自動擴展和容錯等功能，通過屏蔽底層硬件環境的細節，使得用戶能夠關注於業務本身。
分佈式圖計算的任務執行主要有以下三種模式：
一是以 Pregel及其開源實現Giraph為代表的整體同步並行計算（Bulk Synchronous Paralle，BSP）模式。該模式採用以點為中心的編程模型，“每一次計算由一系列的超步（superstep）組成，每一個超步又可以分成本地併發計算、全局通信和同步三個步驟。在本地計算時不產生任何通訊，相對的，全局通訊時也不進行任何計算”。按照這一描述，每一個超步的本地併發計算階段就是各個節點分別執行點程序的過程，而全局通信階段則負責把產生的消息送達至相應的計算節點。這種模式的優缺點十分明顯：優點是非常簡單，無須任何併發控制，而且容易實現基於檢查點（checkpoint）的容錯機制；缺點是同步開銷大，一旦出現負載不均衡，很容易影響執行效率。
二是PowerGraph在GraphLab異步計算模型的基礎上所提出的收集-應用-擴散（Gather-Apply-Scatter，GAS）模式。不同於BSP同步計算模型，異步計算模型沒有顯式的步的概念，每個節點只要有資源就可以調度自己負責的任務，因而運行速度更快。GAS模式採用以邊為中心（頂點切割）的編程模型，把度數很大的頂點分割成若干個鏡像，每個鏡像與一部分邊相連，被分配到不同的計算節點上，而程序的執行過程明確地被分割成了收集、應用和擴散三個階段：在收集階段，圖頂點所有副本同時聚合相鄰頂點（可能在本地，也可能在其他節點）的數據並將聚合結果發送給主副本；在應用階段，主副本將收到的結果彙總到主鏡像上，得到該頂點的全局結果（當前值）並將更新後的值同步到所有副本中；在擴散階段，每個副本將更新後的值按需發送給相鄰頂點。GAS模式與BSP模式的最大區別就是，它將那些度數極大的點的計算也並行化了，從而降低了可能的負載不均衡。
三是數據流（dataflow）模式，其典型的代表系統就是GraphX。數據流模式是一種數據驅動的並行計算模型，當輸入的數據可用時，對應的程序模塊就會被激活，並在資源可用的情況下投入運行，因而可以實現超大規模的並行，而且同步開銷更小。GraphX在分佈式處理框架Spark的基礎上引入了一系列與圖計算相關的抽象與操作。如GraphX把圖抽象成一對頂點集（collections）和邊集，具體的計算則抽象為數據流上的操作。藉助於Spark的擴展和容錯能力，GraphX能夠獲得更高的並行度，運行更為可靠。
分佈式圖計算與單機圖計算的差異主要體現在數據傳輸和任務的執行方面。在單機計算，特別是外存圖計算中，系統會選擇性地將當前需要的部分數據調入內存之中進行計算，而將不再需要的數據換出，從而避免單機內存容量的限制。數據傳輸主要是內外存之間的數據交換，任務執行都在本機完成。由於外存存儲設備的隨機訪問帶寬遠低於其順序訪問帶寬，為了保證計算的運行速度，已有的外存圖計算系統都設計了精巧的數據組織格式或者訪問模式，將隨機訪問儘可能轉變成順序訪問。對於分佈式圖計算系統，任務執行在多個計算節點上完成，數據傳輸通過網絡將其他計算節點上的數據讀取到本地內存之中。與數據的本地讀取相比，網絡讀取延遲更大，速度更慢，因此減少執行過程中的網絡通信量對於提升性能至關重要，而這方面起決定作用的因素就是數據和任務的劃分。
從數據劃分到任務執行實際上經歷了兩重映射，一是數據到任務的映射，二是任務到資源的映射。從執行效率的角度而言，前者的關鍵在於保證不同任務之間的負載均衡，並減少不同任務之間的通訊量，而後者的關鍵在於提升數據的局部性。
閱讀更多 我是天邊飄過一朵雲 的文章
