柯學翰, 陳榕

上海交通大學軟件學院并行與分布式系統(tǒng)研究所，上海 200240

摘要：在目前的研究中，圖查詢和圖計算系統(tǒng)是相互獨立的，但在實際應用中兩者通常是同時存在的。為解決相互獨立的系統(tǒng)帶來的存儲空間浪費、數(shù)據(jù)一致性維護等問題，基于圖查詢系統(tǒng)設計了一種圖計算引擎，使得在單一系統(tǒng)中支持查詢和計算操作。通過為鍵值對存儲增加圖計算索引、基于拉取模式的數(shù)據(jù)更新等方式，有效地提高系統(tǒng)中數(shù)據(jù)遍歷的性能和減少數(shù)據(jù)傳輸?shù)某杀?#xff0c;同時針對數(shù)據(jù)更新和負載均衡等方面提出了相關優(yōu)化。實驗表明，該圖計算引擎能夠達到與傳統(tǒng)圖計算系統(tǒng)PowerLyra和Gemini相近或比其更優(yōu)的性能，且具有較好的可擴展性。

關鍵詞：?分布式系統(tǒng) ; 圖計算 ; 圖查詢 ; 鍵值對存儲

論文引用格式：柯學翰, 陳榕. 基于圖查詢系統(tǒng)的圖計算引擎. 大數(shù)據(jù)[J], 2019, 5(4):16-26

KE X H,CHEN R. Graph processing engine based on graph query system. Big Data Research[J], 2019, 5(4): 16-26

1 引言

近年來，隨著互聯(lián)網(wǎng)和社交網(wǎng)絡的快速發(fā)展，大規(guī)模的圖結構數(shù)據(jù)逐漸增多，例如將知識圖譜、社交網(wǎng)絡等信息抽象成的圖結構數(shù)據(jù)。相比于傳統(tǒng)的大數(shù)據(jù)處理系統(tǒng)，圖系統(tǒng)能更好地利用圖的結構信息，對圖數(shù)據(jù)的處理更為高效。目前對圖系統(tǒng)的研究可分為圖查詢系統(tǒng)和圖計算系統(tǒng)兩個方面。

圖查詢系統(tǒng)需要找到符合用戶需求的圖數(shù)據(jù)，常見的圖查詢系統(tǒng)有Wukong、TriAD、Trinity.RDF等。圖查詢任務通常只需要訪問全圖中小部分的數(shù)據(jù)，但對時延非常敏感，需要在秒甚至毫秒級返回結果。因此，圖查詢系統(tǒng)通常使用鍵值對的存儲模式，使得對單個頂點的訪問更加高效。與圖查詢系統(tǒng)不同，在圖計算系統(tǒng)中，一般使用稀疏矩陣存儲圖的結構。圖計算任務通常需要訪問全圖上所有的頂點，對全圖上的數(shù)據(jù)進行多輪迭代計算后才能結束，時延通常是分鐘甚至小時級別的。因此，在圖計算系統(tǒng)中，單個頂點的訪問時延不是最重要的，其更關注的是整個系統(tǒng)的計算吞吐率。常見的圖計算系統(tǒng)有Pregel、PowerGraph、PowerLyra、Gemini等。

目前對圖查詢系統(tǒng)和圖計算系統(tǒng)的研究一般是相互獨立的，但在實際應用中，圖查詢和圖計算任務通常是同時存在的。例如對于一個記錄了電商平臺上用戶和商品之間的關系的圖數(shù)據(jù)，電商平臺既有查詢用戶歷史訂單的需求（圖查詢任務），又有基于該圖數(shù)據(jù)進行商品推薦的需求（圖計算任務）。傳統(tǒng)的做法是在圖查詢系統(tǒng)和圖計算系統(tǒng)中分別加載該圖數(shù)據(jù)進行分析。但是一份數(shù)據(jù)多份存儲會帶來許多的問題，例如內存空間的浪費、維護不同系統(tǒng)間數(shù)據(jù)的一致性等問題。

為了避免以上問題，本文在現(xiàn)有圖查詢系統(tǒng)基礎上設計和實現(xiàn)了一種高效的圖計算引擎，其能夠在單個系統(tǒng)中同時支持高效的圖查詢和圖計算操作。首先給鍵值對的存儲結構增加針對圖計算的索引，使其加快對圖的遍歷效率；其次針對圖系統(tǒng)中的數(shù)據(jù)劃分，為其設計了基于拉取（pull）模型的消息傳遞模式；最后針對該計算引擎的數(shù)據(jù)更新和負載均衡等方面進行了優(yōu)化。在不同的測試集中的測試結果表明，該計算引擎圖計算性能可達到PowerLyra系統(tǒng)的4.7倍到20倍，同時具有良好的可擴展性。

2 背景介紹

2.1 圖數(shù)據(jù)的存儲結構

鍵值對存儲因具有可擴展強、結構簡單、查找迅速等特點被廣泛應用于圖查詢系統(tǒng)中，如Wukong、Trinity.RDF。在Wukong系統(tǒng)中，圖上的邊會轉換成鍵值對進行存儲，將頂點編號、邊的類型、邊的方向、值的地址和大小等信息組合成鍵（key），對應鄰居頂點構成值（value），如圖1所示。當需要查詢頂點1、邊類型為2的所有入邊（in）時，先通過Hash函數(shù)找到對應的鍵的存儲位置，然后根據(jù)鍵得到值的存儲地址（offset），最后再通過遠端或者本地訪問的方式獲取值的信息，即對應的鄰居有頂點8和頂點9。

圖1???鍵值對存儲

在圖計算系統(tǒng)中廣泛使用壓縮稀疏矩陣來存儲圖的結構，如圖2所示，包括GraphLab、PowerGraph、Gemini等系統(tǒng)。行壓縮稀疏矩陣（compressed sparse row，CSR）表示出邊的信息，列壓縮稀疏矩陣（compressed sparse column，CSC）表示入邊的信息。頂點索引（vertex index）記錄了每個頂點在邊數(shù)組中的起始位置，并且頂點編號與頂點索引數(shù)組的序號保持一致。如頂點2，在頂點索引中的值為4，則頂點2的鄰居頂點從邊數(shù)組中下標為4的元素開始，一直到下一個頂點對應的索引值6，也就是說頂點1、頂點3是頂點2的鄰居頂點。若該結構為CSC，則（1，2）和（3，2）是原圖中的邊；若為CSR，則（2，1）和（2，3）為原圖中的邊。壓縮稀疏矩陣的圖存儲方式對于遍歷圖上所有邊的計算而言是高效的。

圖2???壓縮稀疏矩陣存儲邊的數(shù)據(jù)

2.2 圖計算系統(tǒng)的圖劃分和執(zhí)行模式

在圖計算系統(tǒng)中，圖劃分在減少數(shù)據(jù)跨機器通信、負載均衡等方面發(fā)揮著很重要的作用。目前的劃分方式可以分為邊劃分（edge-cut）和點劃分（vertex-cut），如圖3所示。

圖3???邊劃分和點劃分

邊劃分是指圖從邊切開，每個頂點被放置在一臺服務器上（通常通過Hash的方式），也就是該頂點對應的邊信息都存儲在該機器上，其他服務器上只有該頂點的鏡像頂點，因此每條邊會在多臺機器上出現(xiàn)。邊劃分的優(yōu)點是計算過程中對鄰居頂點信息的聚集都可以在本地完成；缺點是對于冪律分布的圖，會出現(xiàn)負載不均衡的問題。冪律分布的圖的特點是少部分的點擁有大量的邊，因此擁有著這些點的機器的信息計算和通信開銷會遠大于其他的機器。點劃分是將每條邊唯一放置在一臺機器上，頂點可能會被切分在不同的機器中。點劃分的優(yōu)點是對于冪律分布的圖也能實現(xiàn)很好的負載均衡。但是存在的問題是，在計算的過程中，由于一個頂點被切分在不同服務器上，則聚合鄰居頂點的信息需要進行跨機器通信。還有一些工作是將點劃分和邊劃分的方法相互結合，為圖上不同的頂點提供不同的劃分方法。

圖計算引擎的實現(xiàn)通常有兩種方式：基于推送（push-based）模式和基于拉取（pull-based）模式。基于推送模式是對源頂點進行遍歷，然后源頂點將自身的狀態(tài)通過出邊更新鄰居頂點的狀態(tài)。相反地，基于拉取模式是對目標頂點進行遍歷，通過入邊拉取鄰居頂點的狀態(tài)更新自己。相比于基于推送模式的更新鄰居頂點（寫）操作，基于拉取模式的引擎只需要拉取鄰居頂點的信息（讀）即可，因此其能夠達到更高的計算吞吐率。基于推送模式比較適合圖中活躍頂點較少的算法，可以方便地跳過該輪迭代中沒有活躍的頂點，減少計算量。同時也有系統(tǒng)混合使用了兩種更新方式，在執(zhí)行的過程中動態(tài)地選擇適合的更新模式，如Gemini、Polymer等系統(tǒng)。

3 圖計算引擎的設計和優(yōu)化

該節(jié)主要介紹了如何在圖查詢系統(tǒng)中設計和實現(xiàn)一個高效的圖計算引擎。首先總結了在圖查詢系統(tǒng)上實現(xiàn)圖計算引擎的兩點挑戰(zhàn)；然后針對兩點挑戰(zhàn)分別提出了針對圖計算索引優(yōu)化和基于拉取模式的消息傳遞模式兩種技術；接著介紹了圖計算引擎的編程接口；最后給出了兩種圖計算引擎的優(yōu)化方法：非阻塞式更新和負載均衡。

3.1 挑戰(zhàn)

在單一系統(tǒng)中，所有的設計是為了該類型系統(tǒng)而設計的，包括數(shù)據(jù)的存儲結構、數(shù)據(jù)的傳輸模型等。因此，不同系統(tǒng)間的設計是不匹配的，甚至是相互沖突的。首先，不同的系統(tǒng)對底層存儲結構的要求不同。圖查詢系統(tǒng)一般使用鍵值對的方式存儲圖的結構信息，這樣的存儲方式有利于特定數(shù)據(jù)的快速查找，同時具有良好的可擴展性。而在圖計算系統(tǒng)中，為了提升計算性能，需要的是支持高效圖數(shù)據(jù)遍歷的存儲結構，例如CSR和CSC。其次，圖計算系統(tǒng)進行數(shù)據(jù)傳輸?shù)哪Ｊ皆诤艽蟪潭壬先Q于圖數(shù)據(jù)的劃分方式。在一個圖查詢系統(tǒng)的數(shù)據(jù)劃分方法下，一般不能直接套用現(xiàn)有圖計算系統(tǒng)的數(shù)據(jù)傳輸模型，因為會出現(xiàn)頂點或者邊的信息缺失等問題。

本文基于目前性能出色的分布式圖查詢系統(tǒng)Wukong實現(xiàn)圖計算引擎。鍵值對的存儲結構具有很好的可擴展性，因此筆者希望在不改變原來圖查詢系統(tǒng)的基本的數(shù)據(jù)存儲模式的情況下，增加高效的圖計算引擎支持。基于以上分析，目前面臨的挑戰(zhàn)主要有以下兩個方面。

挑戰(zhàn)1：圖計算系統(tǒng)需要高效的圖遍歷存儲結構，如何針對鍵值對的存儲進行高效的圖計算。

直接使用鍵值對存儲進行圖計算存在的問題是計算性能不理想。在Wukong中，每個頂點訪問其鄰居頂點的信息時需要先構造對應的鍵，然后通過Hash表查找，最后才能獲得鄰居頂點的存儲位置。這主要是因為圖查詢任務對于頂點的訪問是隨機的，Hash表可以加速一次隨機的查找。而在圖計算系統(tǒng)中，對于頂點的訪問是順序遍歷的。CSC或CSR存儲模式不僅可以通過一次訪存操作獲得鄰居頂點的地址，而且使得數(shù)據(jù)具有很好的空間局部性。相比之下，使用Hash表查找的方式順序遍歷所有的頂點無疑是比較低效的。針對該問題本文提出了針對圖計算的索引優(yōu)化技術。

挑戰(zhàn)2：圖計算的數(shù)據(jù)傳遞模式在很大程度上取決于圖數(shù)據(jù)的劃分，如何在圖查詢系統(tǒng)中為圖計算引擎設計合適的數(shù)據(jù)傳遞模式。

在Wukong系統(tǒng)中，非查詢索引部分的圖數(shù)據(jù)是按照邊劃分的模式進行的，即每個頂點屬于唯一一臺機器，并且為了加速查詢，邊的信息會進行雙向的存儲。這種圖劃分的模式不同于PowerGraph、Gemini等圖計算系統(tǒng)的劃分方式，因此在Wukong系統(tǒng)上直接使用這些圖計算系統(tǒng)的消息傳遞模式是不合適的。針對該挑戰(zhàn)，本文提出了一種基于拉取模型的消息傳遞模式。

3.2 針對圖計算的索引優(yōu)化技術

為了解決第3.1節(jié)中的挑戰(zhàn)1，圖查詢系統(tǒng)的存儲結構需要支持高效的順序遍歷。高效的順序遍歷是指圖系統(tǒng)能夠快速地遍歷圖中所有的點和點對應的鄰居，同時，原圖查詢系統(tǒng)的隨機訪問的性能不能受到影響。基于此目的，本文提出了針對圖計算的索引優(yōu)化技術。

針對圖計算的索引優(yōu)化是指在原先鍵值對的存儲結構下，增加高效地順序遍歷索引的支持，使得頂點的遍歷不需要通過Hash表獲取頂點存儲位置的地址偏移量，而是可以直接從索引中得到。這樣能夠大大地縮短數(shù)據(jù)訪問的時間。

如圖4所示，本文在原系統(tǒng)的存儲結構中增加了索引的結構。原查詢系統(tǒng)（Wukong）中的數(shù)據(jù)存儲結構主要包括兩個部分：鍵存儲和值存儲。索引是一個數(shù)組的結構，數(shù)組的下標與對應的頂點ID一致，數(shù)組中的值為該頂點在值存儲中的起始地址偏移量，對應的終止偏移量可以根據(jù)下一個頂點的起始地址偏移量來計算。例如，1號頂點對應的起始偏移量是0， 2號頂點對應的起始偏移量為4，說明1號頂點對應的鄰居頂點為值數(shù)組中0號到3號的位置的數(shù)，分別為4號、5號、8號、9號頂點。需要注意的是，在原圖查詢系統(tǒng)中，不同鍵對應的值的存儲可以是不連續(xù)的。在新的存儲模式下，為了便于索引的訪問，值需要按頂點ID有序并且連續(xù)存儲。但這樣的限制不會對原先的圖查詢系統(tǒng)產(chǎn)生性能影響。

圖4???基于圖計算引擎的索引

在增加了圖計算索引的存儲結構下，圖數(shù)據(jù)的訪問模式主要分為以下兩種。

● 圖查詢任務：與原查詢系統(tǒng)一致，首先通過Hash函數(shù)找到特定頂點的鍵的位置，然后根據(jù)鍵找到值的存儲位置，即可獲得鄰居頂點的信息。

● 圖計算任務：當圖計算引擎需要遍歷所有頂點的信息時，通過遍歷圖計算索引上的數(shù)據(jù)，就可以直接獲得對應頂點的鄰居信息的偏移量。

通過添加圖計算的索引，圖計算引擎對頂點的遍歷基本與使用壓縮稀疏存儲結構一致，因此對圖數(shù)據(jù)的訪問也可以達到與單一圖計算系統(tǒng)相似的性能。通過索引，對于每個頂點只需要一次內存訪問就可以獲得其對應的鄰居頂點的偏移量。對于圖的遍歷，只需要順序遍歷一次索引數(shù)組和值數(shù)組即可，并且在計算過程中數(shù)據(jù)也具有很好的空間局部性。

3.3 基于拉取模式的消息傳遞

圖計算引擎的消息傳遞模式與圖的劃分方式有很大的關系，因為圖數(shù)據(jù)劃分的模式影響了頂點收集鄰居頂點的消息來更新自己的方式。在Wukong中，鍵值對的存儲模式事實上是一種邊劃分的方式，即每一個頂點只屬于一臺服務器，在其他服務器上的只是它的鏡像頂點。

根據(jù)圖查詢系統(tǒng)的數(shù)據(jù)劃分特點，本文使用基于拉取模式的消息傳遞，類似于Ligra、Polymer等系統(tǒng)中使用的pull模式。在每輪迭代中主要分為兩個步驟進行，如圖5所示。

圖5???基于拉取模型的消息傳遞模式

步驟1 每臺服務器上的頂點拉取其入邊頂點的消息來更新自身的值。例如頂點2通過入邊信息，聚合鄰居頂點1、頂點3的值，然后更新自己的值。

步驟2 每臺服務器上的頂點會將步驟1中更新的值發(fā)送給其他機器，更新其鏡像頂點的值，到此一輪迭代的計算完成。例如服務器0上的頂點2、頂點4會發(fā)送信息給服務器1，以更新服務器1上頂點2、頂點4的鏡像頂點的值。

在圖查詢系統(tǒng)Wukong中選擇拉取模式而不是推送模式，是由其數(shù)據(jù)的存儲模式?jīng)Q定的。因為每臺服務器存儲的信息是主頂點（master）聚集起來的，如果選擇推送的模式，則每個頂點需要發(fā)送信息更新它的出邊鄰居頂點，發(fā)送的消息數(shù)量為O(E)（E表示邊的數(shù)量，發(fā)送消息的數(shù)量與邊的數(shù)量成正比）。例如服務器0上的頂點2需要更新服務器1上的頂點1、頂點3，因為服務器1上沒有頂點2的鄰居信息（只能通過頂點1、頂點3訪問頂點2，不能通過頂點2訪問頂點1、頂點3），因此服務器0需要發(fā)送兩條信息，分別更新服務器1上的頂點1和頂點3。而在拉取模式下，頂點的聚合操作都是在本地進行的，不同服務器間只需要進行主頂點和鏡像頂點的通信即可，消息發(fā)送數(shù)量由O(E)減少為O(V)（V表示頂點的數(shù)量）。

同時，對于不同機器間的頂點更新，本文采用了批量更新（batch）的方法，以減少單次數(shù)據(jù)更新的開銷。批量更新是指將需要更新的頂點數(shù)據(jù)聚集在一起，然后一次性發(fā)送給其他的機器進行更新，而不是每個頂點單獨發(fā)送一條更新消息。批量更新的方法雖然增加了單次數(shù)據(jù)發(fā)送的時間，但是大大地降低了數(shù)據(jù)發(fā)送的次數(shù)，因此平均下來每一條數(shù)據(jù)的傳播時間被極大地縮短。

3.4 圖計算模型抽象接口

本文借鑒了其他圖計算工作中提出的抽象接口，為用戶提供了兩種操作接口：Vertex_map和Edge_map。在接口設計上，保持了圖計算系統(tǒng)中“像頂點一樣去思考”的設計原則，接口介紹如下。

● Vertex_map(F_Vertex,Active)：這個接口通過F_Vertex定義了單個頂點本地的操作。F_Vertex 為用戶自定義函數(shù)，參數(shù)為當前頂點ID。用戶可以自己定義如何對單個頂點進行操作。Active為活躍頂點的集合，每輪迭代中，只有活躍的頂點參與計算。

● Edge_map(F_Edge,Active)：這個接口通過F_Edge定義用戶如何在邊上進行數(shù)據(jù)聚集操作。參數(shù)F_Edge是一個用戶自定義函數(shù)，該函數(shù)的參數(shù)為當前頂點ID和該頂點所有入邊頂點。

算法1給出了PageRank算法使用上述接口的具體實現(xiàn)。

算法1：Pagerank 算法。

Dnext<- {0.0,0.0 … 0.0}

Dcurr<- {0.0,0.0 … 0.0}

F_Vertex (v){

Dcurr[v]= 1/|V|;

}

F_Edge(s,dst[]) {

for(i =0;i <dst.size;i ++) {

Dnext[s]<- Dcurr[dst[i]]/Out[dst[i]];

}

Dnext[s]<-0.15/|V| + 0.85*Dnext[s];

}

PageRank（iter_num） {

iter<- 0

A<- V

Vertex_map(F_Vertex,A);

while iter<iter_num do {

Edge_map(F_Edge,A);

Swap(Dcurr,Dnext);

}

}

3.5 優(yōu)化

3.5.1 非阻塞式更新

在拉取模式下的步驟2，需要將本地更新的主頂點數(shù)據(jù)發(fā)送給其他機器，更新對應的鏡像頂點。阻塞式更新是指服務器在接收別的服務器發(fā)送過來的更新數(shù)據(jù)時一直處于等待的狀態(tài)，直到所有的數(shù)據(jù)接收完成后才開始本地的更新操作。

而非阻塞式更新在接受消息時不會阻塞整個更新的過程，即在接收數(shù)據(jù)的同時也在更新本地的數(shù)據(jù)。具體實現(xiàn)如圖6所示，將數(shù)據(jù)接收和計算交由不同的線程負責。通信線程（communication thread）負責數(shù)據(jù)的接收，當接收一部分數(shù)據(jù)后就通知前臺計算線程（computation thread）。計算線程發(fā)現(xiàn)有可更新的數(shù)據(jù)時，就將數(shù)據(jù)更新到本地，此時通信線程仍在繼續(xù)接收新的數(shù)據(jù)，這樣數(shù)據(jù)的接收和更新是并行的。當數(shù)據(jù)接收完成時，數(shù)據(jù)的更新也基本完成，使得消息傳播的時間“覆蓋”更新時間。

圖6???非阻塞式更新

3.5.2 負載均衡

負載均衡是分布式并行計算系統(tǒng)一個重要的研究方向。對于一個同步的圖計算引擎來說，計算的時間取決于最慢的機器的執(zhí)行時間。其中，同步的圖計算引擎是指新一輪迭代的開始需要等待所有的點完成上一輪迭代。因此，不同機器間以及單個機器中不同線程間的計算任務需要盡可能均衡。不同機器間的負載均衡由圖的劃分來保證，本文主要關注單臺機器上不同線程間的負載均衡問題。針對該問題，筆者提出兩個優(yōu)化方案：基于邊數(shù)量的任務劃分和任務竊取。

基于邊數(shù)量的任務劃分方法是基于Grazelle系統(tǒng)中的思想提出的，指依據(jù)邊的數(shù)量為每個線程劃分負責的點的數(shù)量。拉取引擎的計算過程包括兩層循環(huán)，外層循環(huán)對所有目標頂點進行遍歷，內層循環(huán)對每個目標頂點通過入邊聚集源頂點的信息。不同的系統(tǒng)通常在外層循環(huán)中使用并行方法進行優(yōu)化，即每個線程負責不同的目標頂點的計算。一種簡單的劃分策略是按照外層循環(huán)的頂點數(shù)量進行劃分，但不同頂點對應邊的數(shù)量不一致，這可能導致不同線程的計算量差異較大。因此，本文基于邊數(shù)量預先為每個線程分配好需要負責的頂點。如圖7所示，將下面的計算任務劃分給兩個線程，線程0負責0號頂點，線程1負責1~5號頂點，每個線程中的計算都包含了7條邊。如果使用基于點的數(shù)量的任務劃分方法，則線程1負責0～2號頂點，一共10條邊，而線程2負責3～5號頂點，一共4條邊，會出現(xiàn)負載不均衡的問題。

任務竊取技術被廣泛應用在分布式并行系統(tǒng)中，它讓已經(jīng)完成任務的線程“竊取”其他線程未完成的任務來執(zhí)行。在本系統(tǒng)中其可以與基于邊數(shù)量的任務劃分技術共同使用，具體實現(xiàn)如下：首先每個線程維護一個任務隊列；然后將被分配好的任務劃分成更多的子任務，保存在各自的任務隊列里；最后每個線程從各自的任務隊列里獲取子任務并執(zhí)行，當任務隊列為空時，檢查旁邊線程的任務隊列，“竊取”其他線程的任務來執(zhí)行。

圖7???基于邊的數(shù)量的任務劃分

4 測試

PowerGraph是一個功能完善、業(yè)界認可度比較高的圖計算系統(tǒng)， PowerLyra是在PowerGraph基礎上針對冪律圖進行改進的系統(tǒng)。Gemini是目前性能比較出色的圖計算系統(tǒng)，性能優(yōu)于PowerGraph和PowerLyra。因此，本文選擇PowerLyra和Gemini作為主要比較的系統(tǒng)。以下主要從性能和可擴展性兩個方面對本文的圖計算引擎進行分析。

4.1 實驗環(huán)境

本文所有實驗均在6臺多核服務器組成的集群上完成，單節(jié)點配置如下：兩個10核Intel(R) Xeon(R) E5-2650 v3 2.30 GHz處理器，內存分別為64 GB，其中遠程直接內存訪問（remote direct memory access，RDMA）網(wǎng)絡使用ConnectX-3 MCX353A 56 Gbit/s InfiniBand網(wǎng)卡，通過Mellanox IS5025 40 Gbit/s交換機連接；以太網(wǎng)使用Intel X520 10GbE 網(wǎng)卡，通過Force10 S4810P 10GbE交換機連接。Wukong系統(tǒng)支持RDMA，因此在其基礎上實現(xiàn)的圖計算引擎使用RDMA進行機器通信，其他不支持RDMA的圖計算系統(tǒng)使用普通以太網(wǎng)進行通信。表1給出了用于測試的數(shù)據(jù)集（UK、Twitter、RoadUS、Wiki）的相關信息，其中，|V|表示頂點數(shù)量，|E|表示邊的數(shù)量。

4.2 性能測試

圖8是在4臺服務器配置下，不同系統(tǒng)在多種數(shù)據(jù)集下的執(zhí)行Pagerank算法（20次迭代）的時間對比。Pull-based表示在直接圖查詢系統(tǒng)中使用基于拉取模式的消息傳遞，沒有使用其他的優(yōu)化。Pull-optimal表示使用了相關技術優(yōu)化后的圖計算引擎，包括針對索引的優(yōu)化技術、非阻塞式更新以及負載均衡等。其中Pull-based作為自身對照的基線系統(tǒng)， PowerLyra和Gemini作為與圖計算系統(tǒng)對照的基線系統(tǒng)。

圖8???性能對比測試

從圖8可以看出，相比于自身基線系統(tǒng)Pull-based，Pull-optimal的運行速度是其2.08~3.14倍。在圖計算任務中，對圖數(shù)據(jù)的遍歷訪問主要集中在核心計算路徑上，因此增加圖計算的索引結構、加快圖數(shù)據(jù)遍歷速度可以極大地縮短圖計算的整體執(zhí)行時間。

相比于圖查詢系統(tǒng)PowerLyra，Pulloptimal的運行速度是其4.75~19.98倍。這一方面是因為PowerLyra是一個功能比較完善的圖計算系統(tǒng)，其提供了更多的抽象和復雜圖的操作，同時也帶來了較大的開銷；另一方面是因為在Pull-optimal中使用了高速網(wǎng)絡RDMA，使得數(shù)據(jù)傳輸?shù)臅r間大大縮短。相比于Gemini系統(tǒng)，在UK和RoadUS數(shù)據(jù)集下，本文中圖計算引擎執(zhí)行時間分別為Gemini的1.99倍和1.06倍。Gemini系統(tǒng)針對圖存儲結構做出了更多的優(yōu)化，例如針對非統(tǒng)一內存訪問架構（non-uniform memory access， NUMA）結構的存儲、按塊的圖劃分等。但是這些優(yōu)化與現(xiàn)有的圖查詢系統(tǒng)存儲是沖突的，不能應用于本文的系統(tǒng)上，因此Pull-optimal性能差于Gemini。在Twitter和Wiki數(shù)據(jù)集下，由于Gemini系統(tǒng)中機器間的通信數(shù)據(jù)量增大，占據(jù)了執(zhí)行時間的絕大部分，而本文中圖計算引擎使用高速網(wǎng)絡RDMA，大大減少了網(wǎng)絡的開銷，因此性能優(yōu)于Gemini系統(tǒng)。整體來看，本文基于圖查詢的圖計算引擎相比獨立的圖計算系統(tǒng)，帶來的額外開銷不超過1倍，最優(yōu)性能接近原性能的20倍。

4.3 可擴展性測試

圖9展示了本文中圖計算引擎隨著服務器數(shù)目的增加整體運行時間的變化。測試使用Twitter作為測試的數(shù)據(jù)集，機器數(shù)量從1臺變化到6臺，運行PageRank算法。從圖9中可以看出，該圖計算引擎有很好的可擴展性。相對于2臺機器（分布式模式下最小的機器數(shù)）的執(zhí)行時間，當機器數(shù)目擴展到4臺和6臺時，分別可以達到2臺機器性能的1.71倍和2.77倍。這是因為鍵值對的存儲系統(tǒng)本身具有良好的可擴展性。

圖9???可擴展性測試

5 結束語

隨著圖結構化數(shù)據(jù)的增多，如何高效處理大量圖結構數(shù)據(jù)成為研究的熱點。但由于目前相互獨立的圖查詢系統(tǒng)和圖計算系統(tǒng)與實際應用的需要不相符，本文提出了基于圖查詢系統(tǒng)的圖計算引擎。首先通過為鍵值對存儲添加圖計算索引的方式，提高圖計算的效率；其次，基于圖系統(tǒng)中的圖劃分模式，使用基于拉取模式的消息傳遞；最后針對數(shù)據(jù)更新和負載均衡進行了優(yōu)化。通過測試表明，本文提出的圖計算引擎能夠在兼容圖查詢系統(tǒng)的同時，利用各種優(yōu)化技術提供與PowerLyra和Gemini接近或比其更優(yōu)的性能，并具有較好的可擴展性。

作者簡介

柯學翰（1996- ），男，上海交通大學軟件學院并行與分布式系統(tǒng)研究所碩士生，主要研究方向為分布式 圖計算系統(tǒng)。

陳榕（1981- ），男，博士，上海交通大學軟件學院并行與分布式系統(tǒng)研究所副教授，主要研究方向為并 行與分布式系統(tǒng)、內存計算等。

《大數(shù)據(jù)》期刊

《大數(shù)據(jù)（Big Data Research，BDR）》雙月刊是由中華人民共和國工業(yè)和信息化部主管，人民郵電出版社主辦，中國計算機學會大數(shù)據(jù)專家委員會學術指導，北京信通傳媒有限責任公司出版的中文科技核心期刊。

關注《大數(shù)據(jù)》期刊微信公眾號，獲取更多內容

---

往期文章回顧

綜合交通大數(shù)據(jù)應用技術的發(fā)展展望

邊緣智能：現(xiàn)狀和展望

我國地方大數(shù)據(jù)政策的擴散模式與轉移特征研究

知識圖譜中的關系方向與強度研究

面向大數(shù)據(jù)的索引結構研究進展

---

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的基于图查询系统的图计算引擎的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。