一、圖數據劃分
如同人們所熟知的數據組織方式會影響讀寫性能，圖數據的劃分和佈局也會對後續的處理性能產生影響。當圖的規模超過單個處理器核或單個計算節點的處理能力時，就需要對圖進行劃分。現有的分佈式圖計算系統通常將數據的劃分簡單地等同於任務的劃分，其劃分目標主要有兩方面：一是劃分的大小盡量均勻，避免負載不均衡；二是儘可能地減少通訊開銷，跨分塊的邊儘量少。對於一般的圖來說，圖劃分問題是一個NP-完全問題，在實際應用過程中都是採用近似算法來完成的。多級圖劃分是目前最常用的圖劃分算法，其基本想法是不斷通過收縮頂點和邊來粗化（coarsen）圖的結構，規模較小時使用已有的較好的算法來做劃分，之後再逐步把圖還原成原來的樣子，並不斷優化（refine）劃分。這樣的算法既能保證較快的速度，也能提供很好的劃分結果。這裡劃分結果好壞的評判是與計算過程密切相關的，同樣的劃分結果針對不同計算場景的表現有可能存在較大的差異，並不存在所謂“唯一最優”的劃分方法或結果。現有的分佈式圖計算系統通常將數據的劃分簡單地等同於任務的劃分，因此數據劃分與編程模型直接相關，可粗略地分成以下幾類：
- 1. Pregel系統所使用的以點為中心的劃分方法，也被稱為一維劃分方法。按照此方法，數據圖中的頂點被均勻地劃分給不同的機器，每個頂點與它所有的鄰邊都存儲在一起。由於圖中的邊表示交互關係，如果一條邊對應的兩個頂點被分到了不同的機器上，在計算過程中這兩臺機器之間就會產生一次遠程通訊。換句話說，在一維劃分中，最終的通訊量和被分割的邊的數量成正比。由於其簡單性，一維劃分被廣泛使用。儘管如此，一維劃分在應對遵循冪律分佈的圖數據時，仍會產生嚴重的負載不均衡，影響執行效率。雖然Mizan和GPS進一步引入了動態調整頂點劃分的優化技術，但並不能從根本上解決負載不均衡問題。
- 2. PowerGraph所提出的基於邊的劃分方法，也被稱為點切分（vertex-cut）或二維劃分方法。不同於維劃分，二維劃分將圖中的邊（而不是點）均分給各個計算節點從而達到負載均衡的目的，這樣做的原因是：在大部分圖計算應用中，計算開銷一般和邊數成正比，如果各個計算節點被分配數目基本相同的邊，它們的計算負載就基本是均衡的。在二維劃分中，度數非常高的頂點被劃分給多個節點，因而計算可以並行進行。但由於實際應用要求將與一個頂點相關的所有計算都一次性完成，因此PowerGraph提出了GAS模式與二維劃分配合，使得對同一頂點不同邊的並行計算成為現實。在二維劃分中，通訊量的大小和副本的數量（即頂點被切分成的份數）成正比，雖然PowerGraph以及隨後的一些論文都提出了不少減少副本數量的方法，但它們往往難以在劃分速度和劃分效果兩方面都取得很好的結果。
- 3. PowerLyra系統中所採用的是混合劃分（hybrid-cut）方法。混合劃分的思想很簡單，就是區別對待高度數頂點和低度數頂點。當一條邊的終點度數小於預先給定的閾值（一般設為100-200）時，混合劃分按照這條邊終點的哈希值對其進行分配，反之則按源點的哈希值分配。如此一來，度數較小的頂點對應的所有邊都會被分配到同一個計算節點之上（相當於對這些頂點使用了一維劃分方法），而度數較大的頂點對應的邊則被分配給了不同的計算節點（相當於對這些頂點使用了二維劃分方法）。
- 4. OSDI 2016會議上提出的三維劃分方法。上述三種劃分方法都將頂點或邊所對應的屬性作為一個不可分割的整體，但三維劃分方法發現，在許多數據挖掘和機器學習應用中，數據圖中頂點和邊的權值經常是一個向量，可以被再次劃分，因此，該方法將數據圖中的每個點進一步劃分成子點，並把同一個點劃分出的不同子點分配給不同的計算節點。正因為引入了這一全新的維度，該劃分方法被稱為三維劃分。三維劃分和其他劃分算法的主要區別在於：每一個子點只包含原來完整點權中的一部分數據，因此我們可以將更多的子點放在同一計算節點之中。
二、圖計算任務執行
圖計算任務的執行實際上是要完成任務到資源的映射，其關鍵是提升數據的局部性。圖計算任務的執行除了所遵循的編程模型不同之外，與其他大數據任務的執行並沒有根本性的差異。這也是GraphX基於Spark實現的原因之一。傳統意義上，人們認為網絡是分佈式圖計算的主要性能瓶頸，因而已有的很多圖計算框架的優化工作重心都放在降低網絡數據傳輸的開銷上，例如PowerLyra的實驗都是在1Gbps甚至100Mbps的以太網環境下進行的。在這樣的網絡環境下，對單機的性能優化往往被忽略，因而導致很多單機圖計算框架（如GraphChi和X-Stream）的性能在某些情況下甚至勝過一個分佈式系統，GRAM系統把InfiniBand應用到圖計算中，其2-3us的低延遲和高達40Gbps的網絡帶寬凸顯了提升單機處理性能的必要性。
除了利用最新的硬件特性之外，轉換數據結構也是發揮硬件潛能、提升執行效率的重要方式現有的分佈式圖計算框架大部分用圖作為後端處理引擎的處理對象。這種方式往往會導致計算順序的隨機性，數據局部性差，因而影響到硬件執行部件的效率。加州大學伯克利分校的研究人員發現，圖數據和稀疏矩陣數據在邏輯上是等價的。利用這一特性，他們找到了一系列等價於稀疏矩陣運算的常見的圖計算操作，並將它們集合成一個以矩陣為中心的圖計算框架CombBLAS。藉助於很多已有的矩陣計算優化技巧，CombbLAS具有很高的執行效率。GraphMat也採用了類似的方式，能夠自動將用戶編寫的以圖為主要數據結構的程序映射成矩陣操作，並交給矩陣計算引擎進行計算，從而提升後臺計算的效率。Gemini系統在上述工作的基礎上，針對當前圖計算系統的性能與最新的共享內存系統相比還有較大差距的情形，進一步提出了以計算為中心的設計思想，給出了一系列與體系結構（主要是多核處理器和高速互聯網絡）相關的優化，在保證可擴展性的同時，提升了圖計算的執行效率。
區分活動邊（活動頂點，即持續更新的頂點所對應的出邊）稠密與否的雙向更新傳播模型。對於稀疏情形，採取推送（push）模型，由活動頂點直接將更新結果推送給鄰居頂點，這樣，只要處理出邊即可；對於稠密的情形，則採取拉取（pull）模型，由頂點主動收集鄰居頂點的更新，這樣，頂點更新引起的競爭減少了。輕權、基於數據塊（chunk）的多級數據劃分方法。對於有p個節點的集群，考慮圖本身固有的局部性，將其劃分成p個連續的頂點塊；將頂點對應的出邊和入邊分別用壓縮稀疏行（Compressed Sparse Row，CSR）和壓縮稀疏列（Compressed Sparse Column，CSC）格式來表示，進一步減少了內存訪問；允許系統根據底層的硬件架構對頂點塊做進一步的劃分，使得系統能夠同時滿足更快速的內存訪問和更高的Cache利用率。
細粒度的任務調度。在整個集群層面，Gemini採用計算和通信的聯合調度，更加有效地實現計算和跨節點通信的重疊；而在計算節點內部Gemini設計了更細粒度的工作竊取機制，以確保不同CPU內核之間的負載均衡。如此一來，硬件得到了有效利用，性能也有了提升。將圖計算任務映射到硬件上去執行涉及到眾多的因素，既需要考慮硬件自身的特性，也需要結合計算框架和計算過程本身的特點。
閱讀更多 我是天邊飄過一朵雲 的文章
