分布共享環(huán)境下支持彈性伸縮的圖處理框架*

詹杭龍，曹東剛+，謝　冰

1.北京大學(xué) 高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871 2.北京大學(xué)（天津?yàn)I海）新一代信息技術(shù)研究院，天津 300450

分布共享環(huán)境下支持彈性伸縮的圖處理框架*

詹杭龍1,2，曹東剛1,2+，謝冰1,2

1.北京大學(xué) 高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871 2.北京大學(xué)（天津?yàn)I海）新一代信息技術(shù)研究院，天津 300450

ZHAN Hanglong,CAO Donggang,XIE Bing.Graph processing framework supporting elastic scalability in distributed shared environment.Journal of Frontiers of Computer Science and Technology,2016,10(7): 901-914.

作為大數(shù)據(jù)處理的一種重要模式，圖處理被廣泛地應(yīng)用在機(jī)器學(xué)習(xí)、數(shù)據(jù)統(tǒng)計(jì)和數(shù)據(jù)挖掘等場(chǎng)景中。在企業(yè)級(jí)應(yīng)用中，多種類(lèi)型的大數(shù)據(jù)處理框架通常會(huì)部署在同一個(gè)分布式集群中，其運(yùn)行環(huán)境是開(kāi)放、共享的，這時(shí)圖處理需要考慮運(yùn)算資源動(dòng)態(tài)變化的問(wèn)題。為了能適應(yīng)這種動(dòng)態(tài)性，更加充分地利用開(kāi)放共享環(huán)境的資源，圖處理框架應(yīng)該具備彈性伸縮能力。通過(guò)調(diào)研，發(fā)現(xiàn)現(xiàn)有的圖處理框架尚未完全實(shí)現(xiàn)彈性伸縮。為此，介紹了一種支持彈性伸縮的分布式并行圖處理框架SParTaG。首先基于任務(wù)并行模型定義了圖處理任務(wù)集及任務(wù)模型；其次基于任務(wù)遷移機(jī)制設(shè)計(jì)并實(shí)現(xiàn)了可動(dòng)態(tài)伸縮的圖處理框架；最后設(shè)計(jì)了一個(gè)基于負(fù)載均衡的調(diào)度算法，實(shí)現(xiàn)了動(dòng)態(tài)伸縮的圖處理過(guò)程。實(shí)驗(yàn)結(jié)果說(shuō)明，SParTaG的性能與當(dāng)前流行的開(kāi)源圖處理框架Giraph相近，且具有較好的彈性伸縮能力。

圖處理；分布式并行計(jì)算；彈性伸縮；任務(wù)遷移

1　引言

作為大數(shù)據(jù)處理的一種重要模式，圖處理被廣泛地應(yīng)用在機(jī)器學(xué)習(xí)、數(shù)據(jù)統(tǒng)計(jì)和數(shù)據(jù)挖掘等場(chǎng)景中。圖處理是指利用圖算法、機(jī)器學(xué)習(xí)算法等對(duì)圖結(jié)構(gòu)進(jìn)行分析和統(tǒng)計(jì)的過(guò)程。為了高效地執(zhí)行圖處理程序，學(xué)術(shù)界研發(fā)了一系列分布式圖處理系統(tǒng)。這些分布式圖處理系統(tǒng)一方面把多處理器的運(yùn)算資源整合起來(lái)，實(shí)現(xiàn)圖中頂點(diǎn)數(shù)據(jù)的并行運(yùn)算，并控制這種運(yùn)算以迭代的方式向前演進(jìn)；另一方面向上提供了有效的編程抽象，簡(jiǎn)化了在企業(yè)級(jí)應(yīng)用中圖處理程序的開(kāi)發(fā)。在企業(yè)級(jí)應(yīng)用中，對(duì)大數(shù)據(jù)的分析往往要經(jīng)過(guò)流處理、批處理和圖處理等多種過(guò)程[1]，不同類(lèi)型的處理框架通常會(huì)部署在同一個(gè)分布式集群中，因此這種運(yùn)算平臺(tái)是開(kāi)放共享的。這里的開(kāi)放性是指分布式集群可能因?yàn)閿U(kuò)容或者臨時(shí)需要而添加更多的運(yùn)算節(jié)點(diǎn)，這使得數(shù)據(jù)處理框架有可能獲得更多的計(jì)算資源。所謂共享性是指平臺(tái)中常常同時(shí)存在多個(gè)作業(yè)，這就導(dǎo)致單個(gè)作業(yè)在執(zhí)行時(shí)所占用的計(jì)算資源可能發(fā)生變化[2]。對(duì)于這種開(kāi)放共享平臺(tái)上運(yùn)行的圖處理作業(yè)，如果在計(jì)算資源增加時(shí)無(wú)法即刻利用富余的資源，或者需要重啟作業(yè)才能使用更大規(guī)模的運(yùn)算資源，將造成不必要的資源或時(shí)間浪費(fèi)。因此，分布式集群的開(kāi)放性和共享性要求其上層的圖處理作業(yè)應(yīng)該具有彈性伸縮的能力，當(dāng)分配給作業(yè)的資源規(guī)模發(fā)生變化時(shí)，作業(yè)能夠及時(shí)動(dòng)態(tài)地調(diào)整負(fù)載的分布，以更加充分地利用集群資源，如圖1所示。

Fig.1　Elastic scalable graph processing圖1　圖處理彈性伸縮示意圖

以Apache Giraph圖處理框架為例，對(duì)頂點(diǎn)數(shù)為4×106，邊數(shù)為68×106的網(wǎng)頁(yè)圖數(shù)據(jù)執(zhí)行PageRank作業(yè)需要近40 min的時(shí)間（http://giraph.apache.org/）。在PageRank作業(yè)運(yùn)行過(guò)程中，開(kāi)放共享平臺(tái)可能由于總作業(yè)量的減少而產(chǎn)生若干空閑的運(yùn)算節(jié)點(diǎn)。如果這時(shí)PageRank作業(yè)能夠彈性擴(kuò)展到空閑的運(yùn)算節(jié)點(diǎn)中，提高并行度，則有可能實(shí)現(xiàn)作業(yè)的加速，用更少的時(shí)間完成作業(yè)。

然而，圖處理作業(yè)的彈性伸縮并不像MapReduce應(yīng)用實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)展那樣直觀。在MapReduce中，輸入的數(shù)據(jù)塊被分配到Mapper Slot中進(jìn)行第一步處理，產(chǎn)生中間結(jié)果再被發(fā)射到Reduce Slot中進(jìn)行合并處理。數(shù)據(jù)塊與數(shù)據(jù)塊之間不存在依賴(lài)關(guān)系，因此可以簡(jiǎn)單地通過(guò)增加Slot來(lái)提高并行度，進(jìn)而實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)展。而圖處理是一個(gè)迭代執(zhí)行且有中間狀態(tài)的過(guò)程，在每一個(gè)迭代步中每個(gè)頂點(diǎn)都需要獲取其鄰接頂點(diǎn)的信息。這種頂點(diǎn)的依賴(lài)關(guān)系是比較復(fù)雜的。因此，為了實(shí)現(xiàn)圖處理的彈性伸縮，需要在運(yùn)行時(shí)調(diào)度層面提供更加復(fù)雜的支持。

自從Google在2010年提出Pregel[3]系統(tǒng)介紹分布式并行圖處理技術(shù)以來(lái)，許多圖處理系統(tǒng)都對(duì)伸縮性（scalability）提供了支持。這里所描述的伸縮性一般有兩個(gè)層面的含義：第一，當(dāng)使用更多計(jì)算資源的時(shí)候，重新執(zhí)行的作業(yè)可以在更短的時(shí)間內(nèi)完成；第二，作業(yè)所輸入的圖結(jié)構(gòu)可以是不同規(guī)模的圖，而不需要更改處理框架的相關(guān)配置。但是，這兩個(gè)層面的伸縮性都不是即時(shí)的，需要作業(yè)重新運(yùn)行一遍才能生效。因此在開(kāi)放共享環(huán)境中，這些圖處理系統(tǒng)的伸縮性無(wú)法及時(shí)響應(yīng)計(jì)算資源的變動(dòng)，難以實(shí)現(xiàn)在當(dāng)前運(yùn)算完成進(jìn)度的基礎(chǔ)上動(dòng)態(tài)伸縮。

此外，還有一些工作在運(yùn)行時(shí)調(diào)度層面提出了動(dòng)態(tài)調(diào)整機(jī)制來(lái)解決圖處理過(guò)程中負(fù)載均衡的問(wèn)題。例如文獻(xiàn)[4]介紹了一種基于頂點(diǎn)遷移的動(dòng)態(tài)負(fù)載均衡機(jī)制，通過(guò)對(duì)每個(gè)頂點(diǎn)的消息通信量、響應(yīng)時(shí)間進(jìn)行監(jiān)控，以實(shí)現(xiàn)頂點(diǎn)的遷移，從而達(dá)到動(dòng)態(tài)的負(fù)載均衡。文獻(xiàn)[5-6]針對(duì)圖處理過(guò)程中圖結(jié)構(gòu)發(fā)生變化的場(chǎng)景進(jìn)行分析，通過(guò)對(duì)運(yùn)行過(guò)程中的圖進(jìn)行重新分區(qū)，以實(shí)現(xiàn)負(fù)載均衡。這些工作圍繞圖處理的動(dòng)態(tài)調(diào)整機(jī)制進(jìn)行了有益的嘗試，但它們并未考慮開(kāi)放分布式環(huán)境的變化，無(wú)法處理運(yùn)算資源發(fā)生變化的情況。針對(duì)上述問(wèn)題，本文介紹了一種面向開(kāi)放分布環(huán)境的支持彈性伸縮的圖處理框架SParTaG。這里的彈性伸縮，是指圖處理作業(yè)的運(yùn)行過(guò)程能適應(yīng)分布式平臺(tái)中資源的動(dòng)態(tài)變化，適時(shí)地調(diào)整遷移各運(yùn)算節(jié)點(diǎn)的負(fù)載，以實(shí)現(xiàn)運(yùn)行時(shí)的動(dòng)態(tài)伸縮及作業(yè)加速。

與大多數(shù)分布式圖處理框架相同，SParTaG目前基于BSP（bulk synchronous parallel）[7]的計(jì)算模型實(shí)現(xiàn)。不同的是SParTaG在對(duì)圖進(jìn)行分區(qū)的基礎(chǔ)上，利用圖分區(qū)的遷移機(jī)制實(shí)現(xiàn)動(dòng)態(tài)的負(fù)載均衡與作業(yè)擴(kuò)展。通過(guò)對(duì)各個(gè)分區(qū)的運(yùn)行時(shí)信息進(jìn)行監(jiān)控，SParTaG計(jì)算出分區(qū)間的遷移方案，從而實(shí)現(xiàn)圖處理的動(dòng)態(tài)調(diào)度。SParTaG使用Erlang語(yǔ)言開(kāi)發(fā)，Erlang是一種函數(shù)式編程語(yǔ)言[8]，具有輕量級(jí)進(jìn)程，高效的消息通信，支持分布節(jié)點(diǎn)的進(jìn)程監(jiān)控等特點(diǎn)，非常適合構(gòu)建支持動(dòng)態(tài)伸縮的分布式系統(tǒng)。

本文主要有如下貢獻(xiàn)：提出了一種面向并行圖處理的任務(wù)模型；設(shè)計(jì)了一個(gè)支持動(dòng)態(tài)任務(wù)調(diào)度的圖處理框架；引入了一種動(dòng)態(tài)調(diào)度遷移機(jī)制，初步實(shí)現(xiàn)了彈性伸縮。

本文組織結(jié)構(gòu)如下：第2章簡(jiǎn)述分布式圖處理的整體流程，分析實(shí)現(xiàn)圖處理彈性伸縮所需要解決的問(wèn)題；第3章介紹SParTaG的設(shè)計(jì)與實(shí)現(xiàn)，包括圖處理問(wèn)題的任務(wù)模型、負(fù)載監(jiān)控與動(dòng)態(tài)遷移機(jī)制以及基于負(fù)載均衡的調(diào)度算法；第4章給出實(shí)驗(yàn)數(shù)據(jù)，并對(duì)實(shí)驗(yàn)數(shù)據(jù)加以分析；第5章對(duì)相關(guān)工作進(jìn)行介紹；最后對(duì)本文進(jìn)行總結(jié)，并討論進(jìn)一步的工作方向。

2　分布式圖處理的整體流程

下面對(duì)基于BSP計(jì)算模型的分布式圖處理流程進(jìn)行介紹。圖處理流程包含兩個(gè)階段：圖結(jié)構(gòu)的分區(qū)與派發(fā)、迭代執(zhí)行與調(diào)度，如圖2所示。

2.1圖結(jié)構(gòu)的分區(qū)與派發(fā)

為了讓圖處理作業(yè)能在分布式環(huán)境中并行執(zhí)行，處理框架首先需要將圖數(shù)據(jù)分發(fā)到各個(gè)運(yùn)算節(jié)點(diǎn)中。這個(gè)預(yù)處理過(guò)程被稱(chēng)為圖的分區(qū)（partitioning）。該過(guò)程根據(jù)并行度的大小將完整的圖結(jié)構(gòu)切分成若干子圖，每個(gè)子圖包含了完整圖中的部分頂點(diǎn)和部分邊的數(shù)據(jù)，再利用一定的靜態(tài)調(diào)度策略將這些子圖分派到各個(gè)運(yùn)算節(jié)點(diǎn)上。對(duì)圖結(jié)構(gòu)進(jìn)行分區(qū)的目標(biāo)有兩個(gè)：一是負(fù)載均衡，即每個(gè)運(yùn)算節(jié)點(diǎn)所承擔(dān)的計(jì)算量及通信量要盡量相近，這樣在運(yùn)算過(guò)程中作業(yè)不會(huì)因?yàn)槟骋粋€(gè)節(jié)點(diǎn)的執(zhí)行時(shí)間過(guò)長(zhǎng)而陷入不必要的等待；二是盡量減少跨子圖的邊，這樣能夠降低在運(yùn)算過(guò)程中處理器之間的通信量。

Fig.2　Distributed graph processing based on BSP圖2　基于BSP的分布式圖處理流程

圖結(jié)構(gòu)的分區(qū)問(wèn)題在圖論中得到了長(zhǎng)期的研究，已有的算法包括局部改進(jìn)圖劃分算法和全局圖劃分算法，其中局部改進(jìn)算法比較經(jīng)典的是KL（Kernighan-Lin）算法[9]和FM（Fiduccia-Mattheyses）算法[10]；全局算法比較經(jīng)典的是Laplace圖特征值譜二分法[11]和多層圖劃分算法[12]，多層圖劃分算法的典型代表是METIS[13]及其并行版本ParMETIS。然而，這些劃分技術(shù)都是集中式的，在算法運(yùn)行時(shí)需要保存對(duì)整張圖的全局視圖，且都具有較高的時(shí)間復(fù)雜度。因此，這些分片技術(shù)并不適用于現(xiàn)實(shí)生活中大規(guī)模的圖處理。

近年來(lái)，針對(duì)大數(shù)據(jù)場(chǎng)景下圖處理的需要，分布式圖框架在效果最優(yōu)化與算法執(zhí)行成本之間進(jìn)行權(quán)衡，提出了一系列相對(duì)簡(jiǎn)單可行的分布式圖分片算法。例如基于隨機(jī)散列的分區(qū)策略、基于區(qū)間劃分的分區(qū)策略、基于標(biāo)簽傳播的分區(qū)策略等。

2.2迭代執(zhí)行

完成圖結(jié)構(gòu)的分區(qū)與派發(fā)后，作業(yè)開(kāi)始執(zhí)行。基于BSP計(jì)算模型的分布式圖處理框架采取一種以頂點(diǎn)為中心的并行運(yùn)算思路，要求應(yīng)用程序通過(guò)定義頂點(diǎn)的狀態(tài)更新和數(shù)據(jù)傳遞等操作來(lái)描述圖處理的算法。在執(zhí)行過(guò)程中，圖處理常常由一串迭代步驟所構(gòu)成，每一次迭代稱(chēng)為一個(gè)超級(jí)步。每個(gè)超級(jí)步之間存在一個(gè)全局的同步控制，即必須等到所有的頂點(diǎn)處理完當(dāng)前超級(jí)步的運(yùn)算后，系統(tǒng)才會(huì)觸發(fā)下一個(gè)超級(jí)步的運(yùn)算。這種方式使得頂點(diǎn)的并行執(zhí)行過(guò)程更加清晰可控，易于保證圖處理過(guò)程的正確性。

在每一個(gè)超級(jí)步中，所有頂點(diǎn)將在集群的所有處理器中并行執(zhí)行，并根據(jù)圖結(jié)構(gòu)中有向邊所記錄的鄰接信息來(lái)傳遞數(shù)據(jù)。這種數(shù)據(jù)的傳遞是跨越相鄰的兩個(gè)超級(jí)步的。即：如果在圖結(jié)構(gòu)中存在一條有向邊從頂點(diǎn)va指向頂點(diǎn)vb，那么從va的角度來(lái)看，va需要向vb傳遞數(shù)據(jù)以供vb在下一個(gè)超級(jí)步中使用；而從vb的角度來(lái)看，在當(dāng)前超級(jí)步，vb則需要先處理由va在上一個(gè)超級(jí)步所傳遞的數(shù)據(jù)。每個(gè)頂點(diǎn)在執(zhí)行完當(dāng)前超級(jí)步之后，需要根據(jù)應(yīng)用程序定義的邏輯判定當(dāng)前狀態(tài)是否可以暫時(shí)停機(jī)，可以則頂點(diǎn)進(jìn)入休眠狀態(tài)。當(dāng)圖中所有的頂點(diǎn)都進(jìn)入休眠狀態(tài)時(shí)，整個(gè)運(yùn)算過(guò)程結(jié)束。

為了更方便地描述以頂點(diǎn)為中心的程序邏輯，許多文獻(xiàn)提出了不同方式的編程接口。Pregel系統(tǒng)[3]基于compute-send模型來(lái)描述每個(gè)超級(jí)步中每個(gè)頂點(diǎn)的行為；PowerGraph系統(tǒng)[14]提出了基于GAS（gatherapply-scatter）模型的接口以充分利用頂點(diǎn)內(nèi)部的并行能力；Galois系統(tǒng)[15]提出了一套不定型的數(shù)據(jù)并行模型（amorphous data-parallelism，ADP），并設(shè)計(jì)了基于活動(dòng)元素集（activity set）和算子（operator）的編程接口等。

2.3迭代執(zhí)行運(yùn)行時(shí)需要考慮的調(diào)度問(wèn)題

在圖處理應(yīng)用的運(yùn)算過(guò)程中，為了達(dá)到較好的性能，首先要考慮的調(diào)度問(wèn)題是負(fù)載均衡，即參與運(yùn)算的每個(gè)處理器在每個(gè)超級(jí)步中處理各自所包含的圖分區(qū)的時(shí)間要盡量相近。在實(shí)際場(chǎng)景中，輸入的圖數(shù)據(jù)可能來(lái)自不同的場(chǎng)景，圖結(jié)構(gòu)可能呈現(xiàn)出不同的特點(diǎn)。對(duì)于一個(gè)由特定算法（如文獻(xiàn)[16]）隨機(jī)生成的圖，它的邊分布比較均衡，對(duì)其進(jìn)行分區(qū)的效果也比較理想。而對(duì)于一些從真實(shí)場(chǎng)景構(gòu)建出的圖結(jié)構(gòu)，它們存在一些特殊的性質(zhì)，如邊分布的冪律性[17]或高密度局部圖等。由于這類(lèi)圖的規(guī)模較大，在可接受的時(shí)間內(nèi)較難通過(guò)復(fù)雜的圖分區(qū)算法實(shí)現(xiàn)嚴(yán)格均衡的子圖劃分。從而圖處理過(guò)程一般是在無(wú)法完全掌握?qǐng)D的結(jié)構(gòu)特點(diǎn)的情況下進(jìn)行運(yùn)算的，這極可能導(dǎo)致負(fù)載不均。因此需要有動(dòng)態(tài)的負(fù)載調(diào)整機(jī)制來(lái)改善這一情況，減少因負(fù)載不均導(dǎo)致的時(shí)間浪費(fèi)。

現(xiàn)有圖處理系統(tǒng)對(duì)動(dòng)態(tài)負(fù)載均衡的支持一般是通過(guò)圖中頂點(diǎn)的遷移來(lái)實(shí)現(xiàn)[6]。然而，由于輸入圖結(jié)構(gòu)的規(guī)模較大，頂點(diǎn)數(shù)量較多，如果以頂點(diǎn)為粒度進(jìn)行監(jiān)控和運(yùn)算，可能導(dǎo)致用于調(diào)度算法的執(zhí)行時(shí)間過(guò)長(zhǎng)，影響運(yùn)算性能。此外，現(xiàn)有的基于頂點(diǎn)遷移的方案在調(diào)度決策中只考慮頂點(diǎn)的執(zhí)行時(shí)間，并未考慮待遷移頂點(diǎn)與原分區(qū)中其他頂點(diǎn)的關(guān)系。這樣的遷移可能導(dǎo)致舊分區(qū)中原本重要的頂點(diǎn)被遷移到其他分區(qū)，導(dǎo)致更嚴(yán)重的負(fù)載不均。因此，如果圖處理系統(tǒng)能選擇較好的分區(qū)算法（如METIS算法、基于標(biāo)簽傳播的分區(qū)算法等），而不是簡(jiǎn)單的隨機(jī)劃分或區(qū)間劃分策略，使得劃分后的各個(gè)圖分區(qū)內(nèi)部相對(duì)緊密，那么負(fù)載的遷移就應(yīng)該考慮由更大的粒度來(lái)完成。

另一方面，在當(dāng)前的開(kāi)放共享環(huán)境中，資源是動(dòng)態(tài)聚合與彈性綁定的[18]。這意味著集群中的作業(yè)可能在剛開(kāi)始運(yùn)算時(shí)只擁有少量的計(jì)算資源，而隨著運(yùn)算的執(zhí)行又獲得了更多的資源。因此，圖處理系統(tǒng)應(yīng)該能夠適應(yīng)這一動(dòng)態(tài)過(guò)程，充分利用可用資源，實(shí)現(xiàn)運(yùn)算的加速。然而，圖處理過(guò)程是迭代且有狀態(tài)的，如何實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)展，是圖處理的調(diào)度過(guò)程中一個(gè)待解決的問(wèn)題。

經(jīng)過(guò)上述分析，本文概括了現(xiàn)有圖處理框架中的運(yùn)行時(shí)調(diào)度機(jī)制在彈性伸縮方面所存在的不足，如下：

（1）缺乏一個(gè)圖處理問(wèn)題的任務(wù)模型，導(dǎo)致對(duì)彈性伸縮性的研究不夠清晰、直觀；

（2）以頂點(diǎn)作為負(fù)載均衡的粒度過(guò)小，需要一個(gè)合適粒度的調(diào)度方案；

（3）現(xiàn)有工作很少考慮資源動(dòng)態(tài)增加時(shí)作業(yè)彈性伸縮的解決方案。

3　SParTaG框架的設(shè)計(jì)與實(shí)現(xiàn)

針對(duì)上文描述的不足，提出解決方案。彈性伸縮的圖處理首先要求負(fù)載能夠在節(jié)點(diǎn)間進(jìn)行轉(zhuǎn)移，以適應(yīng)資源變化時(shí)作業(yè)的伸縮。這一點(diǎn)與負(fù)載均衡的實(shí)現(xiàn)方式是一致的。然而，圖處理比MapReduce應(yīng)用的邏輯更加復(fù)雜，為了保證彈性伸縮時(shí)的正確性，需要對(duì)圖處理問(wèn)題中的任務(wù)進(jìn)行建模，確保負(fù)載能夠完全轉(zhuǎn)移。

為此，首先對(duì)圖處理應(yīng)用構(gòu)建任務(wù)模型，明確其任務(wù)的結(jié)構(gòu)和依賴(lài)關(guān)系；其次，設(shè)計(jì)彈性伸縮的分布式圖處理框架SParTaG，并介紹其任務(wù)遷移機(jī)制；最后，設(shè)計(jì)基于負(fù)載均衡的調(diào)度算法實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)展。

3.1圖處理應(yīng)用的任務(wù)模型

本節(jié)介紹圖處理的任務(wù)模型。對(duì)于一個(gè)輸入圖，定義為G=(V,E)，其中V表示圖中頂點(diǎn)的集合{v1,v2,…,vn}，E表示圖中的有向邊組成的集合。對(duì)于每一條邊，用一個(gè)二元組(vi,vj)表示，其中vi是有向邊的起始點(diǎn)，vj是目標(biāo)點(diǎn)。對(duì)于某個(gè)頂點(diǎn)vx，其入邊集合為 InEdge(vx)={(vi,vx)∈E}，其出邊集合為OutEdge(vx)={(vx,vj)∈E}。為了對(duì)輸入圖進(jìn)行并行處理，輸入圖將被劃分成若干分區(qū)組成的集合，表示為P={P1,P2,…,Pm}。每一個(gè)Pi包含一組頂點(diǎn)，Pi中的每一個(gè)頂點(diǎn) vx記錄著特定屬性，包括頂點(diǎn)的值State(vx)、入邊集合InEdge(vx)、出邊集合OutEdge(vx)。

定義操作符f，用于描述在每個(gè)超級(jí)步中對(duì)每一個(gè)頂點(diǎn)的運(yùn)算過(guò)程。基于BSP計(jì)算模型，每一個(gè)頂點(diǎn)vx首先處理其入邊所相鄰的頂點(diǎn)在前一個(gè)超級(jí)步所發(fā)送來(lái)的消息，更新自身的狀態(tài)，而后發(fā)送新消息給其出邊所相鄰的頂點(diǎn)。定義如下符號(hào)進(jìn)行描述：

Msg((vx,vy))[s]，在頂點(diǎn)vx的第s個(gè)超級(jí)步發(fā)送一條消息給頂點(diǎn)vy；

Msg(OutEdge(vx))[s]，在頂點(diǎn)vx的第s個(gè)超級(jí)步所發(fā)送的所有消息；

Msg(InEdge(vx))[s]，在頂點(diǎn)vx的第s個(gè)超級(jí)步所收到的所有消息。

于是，有：

Msg(InEdge(vx))[s]={Msg((vj,vx))[s-1]|(vj,vx)∈E}

Msg(OutEdge(vx))[s]={Msg((vx,vj))[s]|(vx,vj)∈E}

而對(duì)頂點(diǎn)vx的第s步運(yùn)算過(guò)程 f可以表示為：

f(vx):Msg(InEdge(vx))[s],State(vx)[s]→

State(vx)[s+1],Msg(OutEdge(vx))[s]

操作符 f以 Msg(InEdge(vx))[s]與State(vx)[s]作為參數(shù)傳入，更新vx的值成為State(vx)[s+1]，并產(chǎn)生消息組Msg(OutEdge(vx))[s]用于傳播數(shù)據(jù)。更進(jìn)一步，對(duì)分區(qū)Pz的第s步運(yùn)算過(guò)程可表示為：

f(Pz):{Msg(InEdge(vi))[s]|vi∈Pz},State(Pz)[s]→

State(Pz)[s+1],{Msg(OutEdge(vi))[s]|vi∈Pz}

從該式可以知道，當(dāng)對(duì)一個(gè)分區(qū)進(jìn)行操作時(shí)，f需要兩部分參數(shù)：{Msg(InEdge(vi))[s]|vi∈Pz}代表第s個(gè)超級(jí)步中所有在Pz中的頂點(diǎn)接收到的所有消息；State(Pz)[s]代表第s個(gè)超級(jí)步中所有在Pz中的頂點(diǎn)的值。當(dāng)分區(qū)為了動(dòng)態(tài)擴(kuò)展的需要而在處理器之間遷移時(shí)，上述兩部分參數(shù)均需要進(jìn)行遷移。因此，本文定義SParTaG中的任務(wù)模型如下：

Task(Pk)[s]=(Pk[s],Msg(Pk)[s]),

where Msg(Pk)[s]={Msg(InEdge(vi))[s]|vi∈Pk}

由此可知，SParTaG中的task首先有一個(gè)時(shí)間維度的屬性，用于記錄當(dāng)前的超級(jí)步。此外包含兩部分：其一是圖分區(qū)的結(jié)構(gòu)，這部分?jǐn)?shù)據(jù)可以保存在處理器中以利用本地性，并在每一次迭代運(yùn)算中自我更新；另一部分是在上一個(gè)超級(jí)步所接收的用于當(dāng)前超級(jí)步處理的消息集合。每個(gè)頂點(diǎn)的運(yùn)算所需要的消息只能等待其他頂點(diǎn)傳播，因此消息部分正是圖處理與其他簡(jiǎn)單并行模式（如MapReduce）所不同的地方。

3.2SParTaG框架與編程接口

SParTaG框架基于BSP計(jì)算模型。在預(yù)處理階段，SParTaG提供了多種圖劃分策略，如基于隨機(jī)散列的分區(qū)策略、基于標(biāo)簽傳播的分區(qū)策略等。輸入的圖結(jié)構(gòu)利用某種分區(qū)策略劃分成若干子圖。SParTaG將這些子圖（或稱(chēng)為圖分區(qū)）均分到包含多個(gè)運(yùn)算節(jié)點(diǎn)的集群中，每個(gè)運(yùn)算節(jié)點(diǎn)可能負(fù)責(zé)處理多個(gè)圖分區(qū)數(shù)據(jù)。

為了維護(hù)處理單元中的圖分區(qū)數(shù)據(jù)，便于動(dòng)態(tài)遷移，SParTaG利用3.1節(jié)定義的任務(wù)模型將每一塊圖分區(qū)映射成一個(gè)任務(wù)，并設(shè)計(jì)了任務(wù)隊(duì)列。如圖3所示，每個(gè)運(yùn)算節(jié)點(diǎn)包含4部分：

（1）任務(wù)雙向隊(duì)列負(fù)責(zé)記錄該運(yùn)算節(jié)點(diǎn)所分配的一系列圖分區(qū)，以及維護(hù)該運(yùn)算節(jié)點(diǎn)所執(zhí)行的超級(jí)步。

Fig.3　Architecture of distributed SParTaG圖3　分布式SParTaG架構(gòu)圖

（2）channel為消息接收信箱，負(fù)責(zé)記錄該運(yùn)算節(jié)點(diǎn)所接收到的用于下一超級(jí)步運(yùn)算所需的消息集合。在運(yùn)算初始時(shí)，因?yàn)樯袩o(wú)消息傳遞，所以每個(gè)運(yùn)算節(jié)點(diǎn)的channel均為空。

（3）處理單元負(fù)責(zé)實(shí)際執(zhí)行圖處理運(yùn)算，每當(dāng)處理單元處于空閑狀態(tài)時(shí)，便向本地的任務(wù)雙向隊(duì)列請(qǐng)求一個(gè)任務(wù)。根據(jù)前文所述，處理單元獲取到的任務(wù)結(jié)構(gòu)為一個(gè)二元組，由圖分區(qū)與對(duì)應(yīng)的消息集合所構(gòu)成。當(dāng)處理單元處理完當(dāng)前任務(wù)時(shí)，把更新后的圖分區(qū)提交回任務(wù)雙向隊(duì)列，以便下一超級(jí)步使用。

（4）為了減少實(shí)際運(yùn)算過(guò)程中的通信量，SParTaG不是對(duì)圖分區(qū)中的每一條有向邊都對(duì)應(yīng)發(fā)送一條消息，而是引入buffer，用于緩存任務(wù)雙向隊(duì)列在處理圖分區(qū)過(guò)程中發(fā)送給其他頂點(diǎn)的消息，再打包發(fā)送。channel與buffer可利用應(yīng)用程序?qū)崿F(xiàn)的combine接口對(duì)消息進(jìn)行合并，進(jìn)一步減少消息的通信和處理數(shù)量。

在作業(yè)執(zhí)行過(guò)程中，所有運(yùn)算節(jié)點(diǎn)將以迭代的方式處理各自包含的任務(wù)。在相鄰兩個(gè)超級(jí)步間，所有運(yùn)算節(jié)點(diǎn)通過(guò)全局同步的方式控制迭代過(guò)程。在執(zhí)行每一個(gè)任務(wù)時(shí)，運(yùn)算節(jié)點(diǎn)的處理邏輯如下：

從任務(wù)雙向隊(duì)列中獲取圖分區(qū)數(shù)據(jù)

foreach（頂點(diǎn)in圖分區(qū)）{

從channel獲取發(fā)送給該頂點(diǎn)的所有消息；

調(diào)用應(yīng)用程序接口處理這些消息，更新頂點(diǎn)狀態(tài)；

根據(jù)頂點(diǎn)的出邊集將待發(fā)消息緩存到buffer中；

}

將buffer中的消息根據(jù)目標(biāo)頂點(diǎn)的不同發(fā)送到相應(yīng)運(yùn)算節(jié)點(diǎn)的channel中

應(yīng)用程序需要描述如何處理頂點(diǎn)接收到的數(shù)據(jù)，更新頂點(diǎn)狀態(tài)，以及發(fā)送消息給哪些頂點(diǎn)。SParTaG的編程接口如圖4所示。其中compute用于實(shí)現(xiàn)每個(gè)頂點(diǎn)在每個(gè)迭代步的運(yùn)算；NewState表示頂點(diǎn)在這次運(yùn)算完成后是否進(jìn)入休眠狀態(tài)；combine用于實(shí)現(xiàn)消息的合并，減少跨機(jī)器的通信量。

Fig.4　Application programming interface of SParTaG圖4　SParTaG的編程接口

3.3面向圖分區(qū)的任務(wù)遷移機(jī)制

遷移是實(shí)現(xiàn)負(fù)載均衡的重要途徑，也是實(shí)現(xiàn)作業(yè)伸縮的一種可行方案。針對(duì)2.3節(jié)所分析的頂點(diǎn)遷移所存在的問(wèn)題，SParTaG提出了以圖分區(qū)為監(jiān)控和遷移粒度的彈性伸縮方案。

3.1節(jié)提到的圖處理任務(wù)模型亦是根據(jù)此方案而定義的。以圖分區(qū)為監(jiān)控和遷移粒度，調(diào)度算法的執(zhí)行復(fù)雜度便與圖分區(qū)的數(shù)量相關(guān)，而不是與頂點(diǎn)數(shù)量相關(guān)，運(yùn)算量大為減少；在進(jìn)行負(fù)載遷移時(shí)，整個(gè)圖分區(qū)轉(zhuǎn)存到新的處理器，頂點(diǎn)之間的緊密關(guān)系依然保持，分區(qū)內(nèi)的頂點(diǎn)依然可以進(jìn)行本地通信。

在SParTaG框架中，任務(wù)遷移機(jī)制通過(guò)任務(wù)雙向隊(duì)列來(lái)實(shí)現(xiàn)。任務(wù)雙向隊(duì)列提供兩種類(lèi)型的獲取任務(wù)接口，如圖5所示。如果是本地的運(yùn)算節(jié)點(diǎn)請(qǐng)求獲取任務(wù)，則調(diào)用fetch_task接口從任務(wù)雙向隊(duì)列的隊(duì)首取出圖分區(qū)返回；如果是遠(yuǎn)程的運(yùn)算節(jié)點(diǎn)需要遷移任務(wù)，則可根據(jù)調(diào)度決策的需要以任務(wù)ID為索引，調(diào)用migrate_task接口從任務(wù)雙向隊(duì)列中獲取若干塊對(duì)應(yīng)的任務(wù)數(shù)據(jù)。

Fig.5　Two operations of task queue圖5　任務(wù)隊(duì)列的兩種操作

為了支持動(dòng)態(tài)擴(kuò)展，SParTaG還需要考慮任務(wù)遷移的時(shí)機(jī)問(wèn)題。在每一個(gè)超級(jí)步中，每個(gè)頂點(diǎn)均通過(guò)運(yùn)算節(jié)點(diǎn)向其鄰接頂點(diǎn)傳遞數(shù)據(jù)。如果在這個(gè)時(shí)候進(jìn)行任務(wù)遷移，將會(huì)使得頂點(diǎn)的計(jì)算與通信產(chǎn)生混亂，不容易保證擴(kuò)展后作業(yè)執(zhí)行的正確性。而當(dāng)所有的頂點(diǎn)完成某一超級(jí)步的執(zhí)行，阻塞等待全局同步時(shí)，所有頂點(diǎn)上的運(yùn)算已經(jīng)完成，網(wǎng)絡(luò)中亦無(wú)消息傳遞，在這個(gè)時(shí)候進(jìn)行任務(wù)遷移，是簡(jiǎn)單可控的。因此，SParTaG將每一個(gè)超級(jí)步的全局同步點(diǎn)與下一步的執(zhí)行觸發(fā)點(diǎn)分離開(kāi)，添加到任務(wù)調(diào)度與遷移階段，用于完成作業(yè)的動(dòng)態(tài)擴(kuò)展。

在遷移過(guò)程中，圖分區(qū)數(shù)據(jù)和對(duì)應(yīng)的消息集合都要進(jìn)行傳輸。

2.2節(jié)提到SParTaG使用任務(wù)雙向隊(duì)列記錄圖分區(qū)的結(jié)構(gòu)，channel記錄下一個(gè)超級(jí)步所需的所有消息。當(dāng)發(fā)生任務(wù)遷移時(shí)，被遷移的運(yùn)算節(jié)點(diǎn)以任務(wù)ID為索引，從任務(wù)雙向隊(duì)列中取出圖分區(qū)添加到目標(biāo)運(yùn)算節(jié)點(diǎn)的任務(wù)雙向隊(duì)列中，同時(shí)從channel中取出與該分區(qū)相關(guān)的所有消息傳遞到目標(biāo)運(yùn)算節(jié)點(diǎn)的channel中，如圖6所示。這樣，便完成了此次的任務(wù)遷移。

Fig.6　Diagram of task migration圖6　任務(wù)遷移過(guò)程

任務(wù)遷移機(jī)制既可以讓圖分區(qū)擴(kuò)展到新的計(jì)算節(jié)點(diǎn)，也可以對(duì)現(xiàn)有計(jì)算節(jié)點(diǎn)進(jìn)行收縮，把待收縮節(jié)點(diǎn)中的圖分區(qū)遷移到剩余的工作節(jié)點(diǎn)，因此任務(wù)遷移是實(shí)現(xiàn)動(dòng)態(tài)伸縮的重要途徑。

3.4運(yùn)行時(shí)監(jiān)控與基于負(fù)載均衡的調(diào)度

在任務(wù)遷移機(jī)制的基礎(chǔ)上，SParTaG引入監(jiān)控與調(diào)度機(jī)制，使得圖處理獲得彈性伸縮的能力，更好地適應(yīng)計(jì)算資源的動(dòng)態(tài)變化。

SParTaG定義任務(wù)遷移只在相鄰兩次超級(jí)步之間發(fā)生，因此監(jiān)控與調(diào)度機(jī)制也在每次超級(jí)步執(zhí)行完成后進(jìn)行。如圖7所示，監(jiān)控與調(diào)度機(jī)制分為如下幾個(gè)步驟：

（1）獲取所有worker的負(fù)載信息；

（2）判斷當(dāng)前的負(fù)載是否均衡；

（3）如果均衡，則觸發(fā)下一個(gè)超級(jí)步開(kāi)始執(zhí)行；

（4）如果不均衡，則執(zhí)行任務(wù)遷移操作，完成后再觸發(fā)下一個(gè)超級(jí)步。

Fig.7　Monitoring and scheduling mechanism圖7　監(jiān)控與調(diào)度機(jī)制

，ε為運(yùn)算節(jié)點(diǎn)獲取圖分區(qū)結(jié)構(gòu)和消息集合所需時(shí)間，相對(duì)于T(pi)可以忽略不計(jì)。T(w)用于粗略判定負(fù)載是否均衡，T(pi)用于決策對(duì)哪些圖分區(qū)進(jìn)行任務(wù)遷移。當(dāng)SParTaG在運(yùn)行過(guò)程中獲取到更多的資源，創(chuàng)建更多的運(yùn)算節(jié)點(diǎn)時(shí)，這些新增運(yùn)算節(jié)點(diǎn)的負(fù)載定義為T(mén)(wnew)=0。如圖8中的負(fù)載監(jiān)控表所示。這樣便可以將圖處理的動(dòng)態(tài)擴(kuò)展問(wèn)題轉(zhuǎn)化成新增資源后的負(fù)載均衡問(wèn)題。

Fig.8　Load monitoring table圖8　負(fù)載監(jiān)控表

利用負(fù)載監(jiān)控表，本文接著對(duì)均衡調(diào)度算法進(jìn)行分析。一種直觀的辦法是將該問(wèn)題轉(zhuǎn)化成數(shù)集的劃分問(wèn)題：即存在一個(gè)由所有的圖分區(qū)執(zhí)行時(shí)間構(gòu)成的集合{T(p1),T(p2),…,T(p)}，現(xiàn)需要將該集合劃分成與運(yùn)算節(jié)點(diǎn)數(shù)量相等的若干子集，要求各子集中元素的加和盡量相近。然而，該方案卻不適合用于圖處理問(wèn)題的均衡調(diào)度。因?yàn)槿蝿?wù)遷移是有時(shí)間代價(jià)的，所以應(yīng)該讓大多數(shù)據(jù)任務(wù)盡量留在原有的運(yùn)算節(jié)點(diǎn)上繼續(xù)執(zhí)行，通過(guò)少量任務(wù)的遷移以達(dá)到負(fù)載均衡的目標(biāo)。因此，SParTaG初步設(shè)計(jì)了一種大小配對(duì)與貪心遷移的算法以進(jìn)行調(diào)度決策。算法偽代碼見(jiàn)算法1。

算法1伸縮調(diào)度算法

輸入：所有worker的運(yùn)算時(shí)間{T(w)}，所有partition的執(zhí)行時(shí)間{T(p)}。

輸出：任務(wù)遷移列表。

1.對(duì)集合{T(w)}按時(shí)間從大到小進(jìn)行排序，得到{Ts(w)}={T(ws),T(ws+1),…,T(wt-1),T(wt)}；

2.將排序后的{Ts(w)}進(jìn)行大小配對(duì)，生成由二元組構(gòu)成的集合B={(T(ws),T(wt)),(T(ws+1),T(wt－1)),…}；

3.設(shè)任務(wù)遷移列表為空；

4.對(duì)于集合B中的每一對(duì)二元組(T(wa),T(wb))，如果T(wa)與T(wb)相差超過(guò)閾值，則執(zhí)行如下操作：

5.遷移量=(T(wa),T(wb))/2；

6.將wa所包含的{T(p)}進(jìn)行排序，按從大到小的順序取出圖分區(qū)，直到取出分區(qū)的時(shí)間加和最接近遷移量，獲得分區(qū)列表Lab；

7.將三元組(wa,wb,Lab)加入任務(wù)遷移表中；

8.遍歷所有二元組后，返回任務(wù)遷移表。

3.5分布式索引表

在系統(tǒng)的實(shí)現(xiàn)過(guò)程中，還有一個(gè)問(wèn)題需要考慮。頂點(diǎn)之間的數(shù)據(jù)傳遞是通過(guò)進(jìn)程發(fā)送消息實(shí)現(xiàn)的，而進(jìn)程發(fā)送消息需要指明消息傳輸?shù)哪康牡亍Ｒ虼耍谧鳂I(yè)運(yùn)行過(guò)程中，圖的每一個(gè)頂點(diǎn)均需要有地址屬性，說(shuō)明該頂點(diǎn)位于哪一個(gè)運(yùn)算節(jié)點(diǎn)中。當(dāng)頂點(diǎn)a向頂點(diǎn)b傳遞數(shù)據(jù)時(shí)，它需要先知道頂點(diǎn)b屬于哪一個(gè)運(yùn)算節(jié)點(diǎn)，再向該運(yùn)算節(jié)點(diǎn)發(fā)送消息。此外，由于SParTaG引入了任務(wù)遷移機(jī)制，在作業(yè)運(yùn)行過(guò)程中，某些頂點(diǎn)可能遷移到新的運(yùn)算節(jié)點(diǎn)中，改變了地址屬性，這個(gè)時(shí)候發(fā)送給這些遷移頂點(diǎn)的消息就需要更新其目標(biāo)運(yùn)算節(jié)點(diǎn)。

為了解決這一問(wèn)題，同時(shí)避免單一中心記錄表的查詢(xún)和修改操作代價(jià)過(guò)大[19]，SParTaG使用分布式索引表[20]來(lái)記錄每個(gè)頂點(diǎn)的地址信息。在作業(yè)初始階段，每個(gè)運(yùn)算節(jié)點(diǎn)加載自己擁有的圖分區(qū)結(jié)構(gòu)時(shí)，將圖分區(qū)中所有頂點(diǎn)的地址信息以（key，value）鍵值對(duì)的格式登記到分布式索引表中，其中key為每個(gè)頂點(diǎn)的ID，value為該頂點(diǎn)所在的運(yùn)算節(jié)點(diǎn)ID。在圖處理執(zhí)行過(guò)程中，分布式索引表允許運(yùn)算節(jié)點(diǎn)在本地查詢(xún)到圖中所有頂點(diǎn)的信息（包括本地包含的頂點(diǎn)以及其他運(yùn)算節(jié)點(diǎn)所包含的頂點(diǎn)）；也允許運(yùn)算節(jié)點(diǎn)在本地修改頂點(diǎn)的地址信息，并保證每個(gè)運(yùn)算節(jié)點(diǎn)獲取新的頂點(diǎn)信息的及時(shí)性和一致性。

以一個(gè)遷移場(chǎng)景為例，如圖9所示。在圖中存在一條頂點(diǎn)Va指向Vb的有向邊。在第s個(gè)超級(jí)步時(shí)，頂點(diǎn)Va位于運(yùn)算節(jié)點(diǎn)X中，頂點(diǎn)Vb位于運(yùn)算節(jié)點(diǎn)Y中。運(yùn)算節(jié)點(diǎn)X在處理頂點(diǎn)Va時(shí)，首先從分布式索引表中獲取頂點(diǎn)Vb的地址位置運(yùn)算節(jié)點(diǎn)Y；接著將消息發(fā)送給運(yùn)算節(jié)點(diǎn)Y中的Vb。第s個(gè)超級(jí)步結(jié)束時(shí)，圖處理框架進(jìn)行任務(wù)遷移，將Vb所在的圖分區(qū)遷移到運(yùn)算節(jié)點(diǎn)Z中。運(yùn)算節(jié)點(diǎn)Z獲得遷移后的圖分區(qū)后，更新該分區(qū)中所有頂點(diǎn)的地址信息，這個(gè)信息通過(guò)分布式索引表擴(kuò)散到所有運(yùn)算節(jié)點(diǎn)的索引表中。在第s+1個(gè)超級(jí)步運(yùn)算節(jié)點(diǎn)X處理頂點(diǎn)Va時(shí)，從本地的索引表獲取Vb新的位置。再將第s+1步的消息發(fā)送給位于運(yùn)算節(jié)點(diǎn)Z的Vb。為了提升運(yùn)算節(jié)點(diǎn)讀分布式索引表的效率，SParTaG實(shí)現(xiàn)了cache用于所需頂點(diǎn)地址信息的緩存。

Fig.9　Workflow of distribute index table圖9　分布式索引表的工作機(jī)制

4　實(shí)驗(yàn)結(jié)果與分析

本文通過(guò)實(shí)驗(yàn)對(duì)SParTaG的處理效率和彈性伸縮能力進(jìn)行評(píng)估。實(shí)驗(yàn)的物理環(huán)境是由8個(gè)節(jié)點(diǎn)組成的分布式平臺(tái)。機(jī)器配置為：4 Intel?Xeon?CPU E5-2670，內(nèi)存8 GB，操作系統(tǒng)版本64 bit Debian 3.16.3-2。因?yàn)槭菆D處理問(wèn)題，所以需要圖結(jié)構(gòu)作為輸入數(shù)據(jù)。本文首先從Stanford網(wǎng)絡(luò)分析項(xiàng)目的網(wǎng)站(http:// snap.stanford.edu/data/index.html)中下載了若干真實(shí)的圖結(jié)構(gòu)，另外利用圖的隨機(jī)生成算法[16]構(gòu)造兩個(gè)尺寸與上述真實(shí)圖相近的隨機(jī)圖。

表1展示了幾個(gè)圖數(shù)據(jù)的信息。圖處理算法為PageRank應(yīng)用和單源最短路徑（single source shortest path，SSSP）應(yīng)用。

Table 1　Size of input graph表1　圖數(shù)據(jù)大小

4.1SParTaG與Giraph的性能測(cè)試

本節(jié)首先測(cè)試SParTaG在基準(zhǔn)情況下的性能，即不使用彈性伸縮機(jī)制時(shí)，SParTaG靜態(tài)執(zhí)行圖處理應(yīng)用的能力。這里以當(dāng)前比較流行的開(kāi)源圖處理框架Apache Giraph作為比較對(duì)象。第一組實(shí)驗(yàn)在單臺(tái)機(jī)器上運(yùn)行，均創(chuàng)建10個(gè)運(yùn)算節(jié)點(diǎn)，運(yùn)行PageRank和SSSP應(yīng)用。實(shí)驗(yàn)結(jié)果如圖10所示。

Fig.10　Comparison of running time between static SParTaG and Giraph圖10 靜態(tài)SParTaG與Giraph的運(yùn)行時(shí)間比較

由該實(shí)驗(yàn)可知，對(duì)于不同尺寸的圖數(shù)據(jù)，靜態(tài)SParTaG具有與Giraph可比的性能。此外，通過(guò)該實(shí)驗(yàn)也可以發(fā)現(xiàn)，對(duì)于同等尺寸的實(shí)際圖和隨機(jī)圖，處理時(shí)間是不一樣的。以LiveJournal與R_Graph A為例，圖的尺寸均為頂點(diǎn)4.8×106，邊68×106，在SParTaG中用PageRank算法處理LiveJournal的時(shí)間是123.933 s，處理R_Graph A的時(shí)間是106.039 s。這是因?yàn)閷?shí)際圖LiveJournal中邊的分布并不均衡，導(dǎo)致在處理過(guò)程中各個(gè)worker的運(yùn)算時(shí)間有長(zhǎng)有短，每個(gè)超級(jí)步所花時(shí)間更久，因而總時(shí)間更長(zhǎng)。這就需要?jiǎng)討B(tài)調(diào)度機(jī)制來(lái)提升性能。

4.2擴(kuò)展性

本實(shí)驗(yàn)用于驗(yàn)證SParTaG框架的擴(kuò)展性。對(duì)Arabic-05與LiveJournal兩個(gè)實(shí)際圖的數(shù)據(jù)執(zhí)行PageRank算法。每次應(yīng)用的執(zhí)行使用不同數(shù)量的機(jī)器，每個(gè)機(jī)器創(chuàng)建10個(gè)運(yùn)算節(jié)點(diǎn)。將1個(gè)機(jī)器執(zhí)行應(yīng)用的時(shí)間與多個(gè)機(jī)器的時(shí)間做比值，求加速比。實(shí)驗(yàn)結(jié)果如圖11所示。

Fig.11　Scalability verification of static SParTaG圖11 靜態(tài)SParTaG的擴(kuò)展性驗(yàn)證

從實(shí)驗(yàn)結(jié)果可以看出，SParTaG具有較好的擴(kuò)展性。這里的擴(kuò)展性是靜態(tài)的。由于LiveJournal圖的尺寸較小，分布在更多節(jié)點(diǎn)上時(shí)，每個(gè)運(yùn)算節(jié)點(diǎn)所承擔(dān)的圖分區(qū)規(guī)模變小，影響了并行所帶來(lái)的收益。因而加速效果相對(duì)差些。

4.3靜態(tài)執(zhí)行與彈性伸縮執(zhí)行

本實(shí)驗(yàn)用于驗(yàn)證SParTaG的彈性伸縮能力。對(duì)實(shí)際圖Arabic-05與隨機(jī)圖R_Graph B兩個(gè)尺寸相近的圖數(shù)據(jù)執(zhí)行PageRank算法，比較靜態(tài)執(zhí)行和彈性伸縮執(zhí)行的時(shí)間差異。對(duì)于每個(gè)輸入圖均運(yùn)行3個(gè)實(shí)例：實(shí)例Static使用兩臺(tái)機(jī)器靜態(tài)執(zhí)行PagaRank；實(shí)例Load Balancing啟用彈性伸縮策略，但保持機(jī)器的數(shù)量始終為兩臺(tái)，每臺(tái)機(jī)器創(chuàng)建10個(gè)運(yùn)算節(jié)點(diǎn)；實(shí)例Elastic Scaling同樣啟動(dòng)彈性伸縮策略，但在作業(yè)初始時(shí)機(jī)器數(shù)量為兩臺(tái)，在作業(yè)執(zhí)行到某一時(shí)刻額外添加兩臺(tái)機(jī)器，其中每臺(tái)機(jī)器各創(chuàng)建10個(gè)運(yùn)算節(jié)點(diǎn)。

在實(shí)驗(yàn)結(jié)果中，Load Balancing Arabic與Static Arabic相比，Load Balancing R_Graph B與Static R_ Graph B相比，均減少了作業(yè)執(zhí)行時(shí)間。Load Balaing Arabic減少的幅度更大些，這是因?yàn)閷?shí)際圖Arabic由于圖結(jié)構(gòu)密度不均，利用簡(jiǎn)單的圖分區(qū)算法難以保證負(fù)載均衡。經(jīng)過(guò)動(dòng)態(tài)調(diào)度后，在一定程序上改善了負(fù)載不均的情況。R_Graph B為隨機(jī)圖，圖結(jié)構(gòu)較為平均，因此動(dòng)態(tài)調(diào)整對(duì)其優(yōu)化程度不大。

此外，在兩個(gè)圖的執(zhí)行過(guò)程中動(dòng)態(tài)加入兩臺(tái)機(jī)器，圖12中的Elastic Scaling R_Graph B與Elastic ScalingArabic為執(zhí)行效果。彈性伸縮機(jī)制使得SParTaG能夠?qū)⒆鳂I(yè)動(dòng)態(tài)地?cái)U(kuò)展到新增機(jī)器上，而不用重啟系統(tǒng)，并減少了運(yùn)算時(shí)間，實(shí)現(xiàn)了即時(shí)（on the fly）加速。

Fig.12　Time comparison of static and elastic execution圖12　靜態(tài)執(zhí)行與彈性執(zhí)行效果對(duì)比

4.4彈性伸縮的運(yùn)行剖面圖

為了更直觀地展示SParTaG動(dòng)態(tài)調(diào)度的效果，本節(jié)對(duì)圖處理過(guò)程進(jìn)行時(shí)間剖面分析，并對(duì)每個(gè)超級(jí)步所花時(shí)間進(jìn)行記錄。實(shí)驗(yàn)用例為對(duì)Arabic圖數(shù)據(jù)執(zhí)行PageRank算法，初始時(shí)機(jī)器規(guī)模為兩臺(tái)。在作業(yè)運(yùn)行過(guò)程的某一時(shí)刻加入額外的兩臺(tái)機(jī)器。兩個(gè)對(duì)比實(shí)驗(yàn)分別為：靜態(tài)執(zhí)行與啟用彈性伸縮機(jī)制的動(dòng)態(tài)圖處理。實(shí)驗(yàn)結(jié)果如圖13、圖14所示。

Fig.13　Progresscomparisonofstaticandelasticexecution圖13　靜態(tài)執(zhí)行與彈性伸縮執(zhí)行的進(jìn)度對(duì)比

Fig.14　Execution profile of every superstep圖14　每個(gè)超級(jí)步的運(yùn)算用時(shí)對(duì)比

在圖13中，橫軸表示作業(yè)執(zhí)行的時(shí)間，縱軸表示作業(yè)在某一時(shí)刻已完成的超級(jí)步。對(duì)于靜態(tài)執(zhí)行的實(shí)驗(yàn)，總共用時(shí)2 000多秒。對(duì)于啟動(dòng)彈性伸縮機(jī)制的實(shí)驗(yàn)，在600 s左右時(shí)添加新的機(jī)器，SParTaG將作業(yè)擴(kuò)展到新增的運(yùn)算節(jié)點(diǎn)中，使得剩下的每一個(gè)超級(jí)步都能夠用更短的時(shí)間完成，最終在將近1 400 s時(shí)完成最后一個(gè)超級(jí)步，實(shí)現(xiàn)了作業(yè)的動(dòng)態(tài)加速。

圖14用更直觀的方式說(shuō)明SParTaG是如何實(shí)現(xiàn)動(dòng)態(tài)加速的。在彈性執(zhí)行實(shí)驗(yàn)中，出現(xiàn)兩次比較明顯的調(diào)度與遷移階段。第一次是作業(yè)剛開(kāi)始運(yùn)行時(shí)，由于負(fù)載不均而導(dǎo)致的任務(wù)遷移。負(fù)載均衡后每個(gè)超級(jí)步的執(zhí)行時(shí)間相比于靜態(tài)實(shí)驗(yàn)有所減小。第二次是新節(jié)點(diǎn)加入時(shí)，調(diào)度機(jī)制將任務(wù)遷移到空閑的運(yùn)算節(jié)點(diǎn)上，以實(shí)現(xiàn)新的規(guī)模下的負(fù)載均衡。這時(shí)，圖處理的并行度增加，每個(gè)超級(jí)步的執(zhí)行時(shí)間再次減小，圖處理作業(yè)也因此獲得了加速。

5　相關(guān)工作與討論

開(kāi)放共享的集群環(huán)境對(duì)企業(yè)級(jí)的大數(shù)據(jù)處理提出了新的要求，彈性伸縮是這種環(huán)境下構(gòu)建大數(shù)據(jù)處理平臺(tái)所需要考慮的重要問(wèn)題。為了讓平臺(tái)中的應(yīng)用能夠彈性地執(zhí)行，不僅需要在集群中引入實(shí)現(xiàn)彈性資源分配的相關(guān)設(shè)施（如MESOS[21]、Yarn[22]等），更需要在處理框架層面根據(jù)作業(yè)的邏輯提供支持彈性伸縮的運(yùn)行時(shí)調(diào)度機(jī)制。

為此，相關(guān)工作圍繞大數(shù)據(jù)處理框架的彈性伸縮技術(shù)展開(kāi)了研究。例如：Morpho[23]、EMRE[24]等實(shí)現(xiàn)了支持動(dòng)態(tài)伸縮的MapReduce執(zhí)行框架，ESC[25]實(shí)現(xiàn)了一種基于MAPE循環(huán)的彈性流處理框架，DETS[26]實(shí)現(xiàn)了一種基于任務(wù)池調(diào)度的面向計(jì)算密集型應(yīng)用的彈性伸縮并行框架。

然而，對(duì)于圖處理框架，目前雖然存在著若干關(guān)于負(fù)載均衡調(diào)整技術(shù)的研究，但對(duì)于彈性伸縮的研究仍處于探索階段。根據(jù)系統(tǒng)架構(gòu)的不同，圖處理框架可以分為4類(lèi)：圖數(shù)據(jù)庫(kù)、基于共享內(nèi)存的圖處理框架、基于消息通信的分布式圖處理框架、基于內(nèi)存計(jì)算的分布式處理框架。Neo4j[27]是一個(gè)當(dāng)前十分流行的開(kāi)源圖數(shù)據(jù)庫(kù)，通過(guò)提供一系列接口以支持圖數(shù)據(jù)的讀寫(xiě)、索引和遍歷操作。基于共享內(nèi)存的圖處理系統(tǒng)包括GraphLab[28]，PowerGraph、PowerLyra[29]、Seraph[30]等，它們把整個(gè)圖和程序狀態(tài)存儲(chǔ)在內(nèi)存中，在運(yùn)算過(guò)程中，頂點(diǎn)之間的數(shù)據(jù)傳遞通過(guò)讀寫(xiě)共享內(nèi)存實(shí)現(xiàn)。由于是共享內(nèi)存的架構(gòu)，作業(yè)在訪問(wèn)共享數(shù)據(jù)時(shí)的加鎖操作往往導(dǎo)致更大的開(kāi)銷(xiāo)，其橫向擴(kuò)展能力相對(duì)弱一些。上述兩類(lèi)圖處理框架受到擴(kuò)展能力的限制，尚未有工作對(duì)其彈性伸縮進(jìn)行研究。

基于消息通信的分布式圖處理框架包括Pregel[3]、Giraph、Mizan[4]、PAGE[31]等，它們基于BSP計(jì)算模型實(shí)現(xiàn)圖處理，通過(guò)消息通信進(jìn)行頂點(diǎn)間數(shù)據(jù)的傳遞，這種分布式的結(jié)構(gòu)使得系統(tǒng)具有較好的擴(kuò)展性。因此，現(xiàn)有的關(guān)于圖處理負(fù)載均衡動(dòng)態(tài)調(diào)整問(wèn)題的研究[4-6]主要是在這一類(lèi)框架上進(jìn)行。本文所介紹的SParTaG也是基于消息通信的圖處理框架。

此外，還有一類(lèi)圖處理框架是基于內(nèi)存計(jì)算的，例如GraphX系統(tǒng)[32]在Spark RDD的基礎(chǔ)上構(gòu)建出基于BSP計(jì)算模型的分布式圖處理框架。RDD對(duì)韌性（resilience）的支持使得GraphX具有動(dòng)態(tài)容錯(cuò)的能力；RDD中對(duì)partitions的調(diào)度設(shè)施為GraphX提供了動(dòng)態(tài)擴(kuò)展的可能。然而，GraphX中缺乏彈性機(jī)制，無(wú)法在運(yùn)行過(guò)程中自適應(yīng)地調(diào)整各個(gè)partitions，要實(shí)現(xiàn)彈性伸縮仍需要更進(jìn)一步的工作。利用Spark中RDD的容錯(cuò)能力與Tachyon內(nèi)存文件系統(tǒng)高效的分布式讀寫(xiě)，可以考慮重新構(gòu)建基于Spark的支持彈性伸縮的圖處理框架。

6　結(jié)束語(yǔ)

本文介紹了一種面向開(kāi)放共享環(huán)境下支持彈性伸縮的并行圖處理框架SParTaG。SParTaG首先定義了動(dòng)態(tài)環(huán)境下圖處理應(yīng)用的任務(wù)模型，并利用圖分區(qū)的遷移機(jī)制實(shí)現(xiàn)動(dòng)態(tài)的負(fù)載均衡與擴(kuò)展。通過(guò)對(duì)各個(gè)分區(qū)的運(yùn)行時(shí)信息進(jìn)行監(jiān)控，SParTaG計(jì)算出分區(qū)間的遷移方案，從而實(shí)現(xiàn)圖處理的動(dòng)態(tài)調(diào)度。實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了SParTaG與當(dāng)前流行的開(kāi)源圖處理框架Apache Giraph的性能相當(dāng)，而且SParTaG還具有彈性伸縮的能力，能夠充分利用分布式環(huán)境下動(dòng)態(tài)變化的運(yùn)算資源，實(shí)現(xiàn)作業(yè)的加速。

未來(lái)的工作重點(diǎn)主要包含以下兩個(gè)方面：一方面考慮改進(jìn)圖的分區(qū)算法，以基于子圖邊密度的策略實(shí)現(xiàn)對(duì)圖結(jié)構(gòu)的均衡劃分；另一方面考慮改進(jìn)調(diào)度算法，以更細(xì)致的負(fù)載指標(biāo)來(lái)指導(dǎo)任務(wù)調(diào)度。

[1]Cheng Xueqi,Jin Xiaolong,Wang Yuanzhuo,et al.Survey on big data system and analytic technology[J].Journal of Software,2014,25(9):1889-1908.

[2]Lu Xicheng,Wang Huaimin,Wang Ji.Internet virtual computing environment—iVCE:concept and architecture[J]. Science in China:Series E Information Sciences,2006,36 (10):1081-1099.

[3]Malewicz G,Austern M H,Bik A J,et al.Pregel:a system for large-scale graph processing[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data,Indianapolis,USA,Jun 6-11,2010.New York,USA: ACM,2010:135-146.

[4]Khayyat Z,Awara K,Alonazi A,et al.Mizan:a system fordynamic load balancing in large-scale graph processing[C]// Proceedings of the 8th ACM European Conference on Computer Systems,Prague,Czech Republic,Apr 15-17,2013. New York,USA:ACM,2013:169-182.

[5]Vaquero L,Cuadrado F,Logothetis D,et al.xDGP:a dynamic graph processing system with adaptive partitioning[C]//Proceedings of the 4th Annual Symposium on Cloud Computing, 2013.

[6]Nicoara D,Kamali S,Daudjee K,et al.Managing social network data through dynamic distributed partitioning[Z]. 2014.

[7]Valiant L G.A bridging model for parallel computation[J]. Communications of theACM,1990,33(8):103-111.

[8]Armstrong J.Programming Erlang:software for a concurrent world[M].[S.l.]:Pragmatic Bookshelf,2007.

[9]Dutt S.New faster Kernighan-Lin-type graph partitioning algorithms[C]//Proceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design,Santa Clara, USA,Nov 7-11,1993.Piscataway,USA:IEEE,1993:370-377.

[10]Fiduccia C M,Mattheyses R M.A linear-time heuristic for improving network partitions[C]//Proceedings of the 19th Conference on Design Automation,Las Vegas,USA,Jun 14-16,1982.Piscataway,USA:IEEE,1982:175-181.

[11]Pothen A,Simon H D,Liou K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAM Journal on Matrix Analysis andApplications,1990,11(3):430-452.

[12]Karypis G,Kumar V.Multilevel graph partitioning schemes [C]//Proceedings of the 1995 International Conference on Parallel Processing,Urbana-Champain,USA,Aug 14-18, 1995.Boca Raton,USA:CRC Press,1995:113-122.

[13]Karypis G,Kumar V.METIS:unstructured graph partitioning and sparse matrix ordering system[R].University of Minnesota,1995.

[14]Gonzalez J E,Low Y Gu Haijie,et al.PowerGraph:distributed graph-parallel computation on natural graphs[C]//Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation,Hollywood,USA,Oct 8-10,2012.Berkeley,USA:USENIXAssociation,2012:17-30.

[15]Nguyen D,Lenharth A,Pingali K.A lightweight infrastructure for graph analytics[C]//Proceedings of the 24th Symposium on Operating Systems Principles,Farmington,USA, Nov 3-6,2013.New York,USA:ACM,2013:456-471.

[16]Gilbert E.N Random graphs[J].The Annals of Mathematical Statistics,1959,30(4):1141-1144.

[17]Mitzenmacher M.A brief history of generative models for power law and lognormal distributions[J].Internet Mathematics,2002,1(2):226-251.

[18]Lu Xicheng,Wang Huaimin,Wang Ji,et al.Internet-based virtual computing environment:beyond the data center as a computer[J].Future Generation Computer Systems,2013, 29(1):309-322.

[19]Balakrishnan H,Kaashoek M F,Karger D,et al.Looking up data in P2P systems[J].Communications of the ACM, 2003,46(2):43-48.

[20]Mattsson H,Nilsson H,Wikstrom C.Mnesia:a distributed robust DBMS for telecommunications applications[C]// LNCS 1551:Proceedings of the 1st International Workshop on Practical Aspects of Declarative Languages,San Antonio, USA,Jan 18-19,1999.Berlin,Heidelberg:Springer,1999: 152-163.

[21]Hindman B,Konwinski A,Zaharia M,et al.Mesos:a platform for fine-grained resource sharing in the data center [C]//Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation,Boston,USA, Mar 30-Apr 1,2011.Berkeley,USA:USENIX Association, 2011:295-308.

[22]Yarn.Apache Hadoop next generation MapReduce(Yarn)[R]. http://hadoop.apache.org/docs/r2.3.0/hadoop-yarn/hadoopyarn-site/YARN.html.

[23]Lu Lu,Shi Xuanhua,Jin Hai,et al.Morpho:a decoupled MapReduce framework for elastic cloud computing[J].Future Generation Computer Systems,2014,36:80-90.

[24]Goh W X,Tan K L.Elastic MapReduce execution[C]//Proceedings of the 2014 14th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing,Chicago,USA, May 26-29,2014.Piscataway,USA:IEEE,2014:216-225.

[25]Satzger B,Hummer W,Leitner P,et al.ESC:towards an elastic stream computing platform for the cloud[C]//Proceedings of the 2011 International Conference on Cloud Computing,Washington,USA,Jul 4-9,2011.Piscataway, USA:IEEE,2011:348-355.

[26]Zhan Hanglong,Kang Lianghuan,Cao Donggang.DETS:a dynamic and elastic task scheduler supporting multiple parallel schemes[C]//Proceedings of the 8th International Symposium on Service Oriented System Engineering,Oxford, UK,Apr 7-10,2014.Piscataway,USA:IEEE,2014:278-283.

[27]Webber J.A programmatic introduction to Neo4j[C]//Pro-ceedings of the 3rd Annual Conference on Systems,Programming,and Applications:Software for Humanity,Tucson,USA,Oct 21-25,2012:217-218.

[28]Low Y,Gonzalez J,KyrolaA,et al.GraphLab:a new framework for parallel machine learning[J].arXiv:1006.4990, 2010.

[29]Chen Rong,Shi Jiaxin,Chen Yanzhe,et al.PowerLyra:differentiated graph computation and partitioning on skewed graphs[C]//Proceedings of the 10th European Conference on Computer Systems,Bordeaux,France,Apr 21-24,2015. New York,USA:ACM,2015.

[30]Xue Jilong,Yang Zhi,Qu Zhi,et al.Seraph:an efficient, low-cost system for concurrent graph processing[C]//Proceedings of the 23rd International Symposium on High Performance Parallel and Distributed Computing,Vancouver, Canada,Jun 23-27,2014.New York,USA:ACM,2014: 227-238.

[31]Shao Yingxia,Yao Junjie,Cui Bin,et al.PAGE:a partition aware graph computation engine[C]//Proceedings of the 22nd ACM International Conference on Conference on Information&Knowledge Management,San Francisco,USA,Oct 27-Nov 1,2013.New York,USA:ACM,2013:823-828.

[32]Gonzalez J E,Xin R S,Dave A,et al.GraphX:graph processing in a distributed dataflow framework[C]//Proceedings of the 11th USENIX Symposium on Operating System Design and Implementation,Broomfield,USA,Oct 6-8,2014. Berkeley,USA:USENIXAssociation,2014:599-613.

附中文參考文獻(xiàn)：

[1]程學(xué)旗,靳小龍,王元卓,等.大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J].軟件學(xué)報(bào),2014,25(9):1889-1908.

[2]盧錫城,王懷民,王戟.虛擬計(jì)算環(huán)境iVCE:概念與體系結(jié)構(gòu)[J].中國(guó)科學(xué):E輯信息科學(xué),2006,36(10):1081-1099.

ZHAN Hanglong was born in 1989.He is a Ph.D.candidate at School of Electronics Engineering and Computer Science,Peking University.His research interests include big data,system software,parallel and distributed computing,etc.

詹杭龍（1989—），男，福建漳州人，北京大學(xué)信息科學(xué)技術(shù)學(xué)院博士研究生，主要研究領(lǐng)域?yàn)榇髷?shù)據(jù)，系統(tǒng)軟件，分布式并行計(jì)算等。

CAO Donggang was born in 1975.He received the Ph.D.degree from School of Electronics Engineering and Computer Science,PekingUniversity in 2004.Now he is an associate professor at Software Institute,School of Electronics Engineering and Computer Science,Peking University.His research interests include system software,parallel and distributed computing,etc.

曹東剛（1975—），男，山東威海人，2004年于北京大學(xué)信息科學(xué)技術(shù)學(xué)院獲得博士學(xué)位，現(xiàn)為北京大學(xué)信息科學(xué)技術(shù)學(xué)院軟件所副教授，主要研究領(lǐng)域?yàn)橄到y(tǒng)軟件，分布并行處理等。發(fā)表學(xué)術(shù)論文30余篇，承擔(dān)過(guò)國(guó)家973計(jì)劃、863計(jì)劃、自然科學(xué)基金等多個(gè)項(xiàng)目，獲國(guó)家技術(shù)發(fā)明二等獎(jiǎng)，電子學(xué)會(huì)電子信息科學(xué)技術(shù)一等獎(jiǎng)。

XIE Bing was born in 1970.He received the Ph.D.degree from School of Computer,National University of Defense Technology in 1998.Now he is a professor and Ph.D.supervisor at Peking University.His research interests include software engineering,formal methods and software reuse,etc.

謝冰（1970—），男，湖南湘潭人，1998年于國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院獲得博士學(xué)位，現(xiàn)為北京大學(xué)信息科學(xué)技術(shù)學(xué)院軟件所教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)檐浖こ蹋问交椒ǎ浖?fù)用等。發(fā)表學(xué)術(shù)論文80余篇，主持多項(xiàng)國(guó)家863計(jì)劃重點(diǎn)項(xiàng)目，獲國(guó)家科技進(jìn)步二等獎(jiǎng)、技術(shù)發(fā)明二等獎(jiǎng)等。

Graph Processing Framework Supporting Elastic Scalability in Distributed Shared Environment?

ZHAN Hanglong1,2,CAO Donggang1,2+,XIE Bing1,2
1.Key Lab of High Confidence Software Technologies(Peking University),Ministry of Education,Beijing 100871, China 2.Beida(Binhai)Information Research,Tianjing 300450,China +Corresponding author:E-mail:caodg@pku.edu.cn

As an important pattern in big data processing,graph processing has been widely used in many kinds of scenarios,such as machine learning,data statistics and data mining,etc.when running enterprise-level applications,various kinds of big-data processing frameworks are usually deployed in the same distributed cluster,so the runtime environmentisopenandshared.Asaresult,graphprocessingshouldconsiderthedynamicchangesofcomputingresources. In order to adapt to this dynamics and make good use of computing resources,graph processing framework should have the ability of elastic scaling.However,current graph processing frameworks have not fully realized elastic scaling yet as far as this paper knows.This paper introduces the design and implementation of an elastic scalable parallelgraph processing framework,SParTaG.SParTaG firstly defines the task set and task model in graph processing problem;then designs an elastic scalable framework based on task migration mechanism;and proposes a load-balancing based scheduling algorithm at last.Experiments show that SParTaG achieves performance parity with the currently popular open-source Giraph system,and it can run graph job well in an elastic scalable manner.

graph processing;distributed parallel computing;elastic scaling;task migration

2015-07,Accepted 2015-09.

10.3778/j.issn.1673-9418.1509009

A

TP391

*The National Natural Science Foundation of China under Grant Nos.61272154,61121063(國(guó)家自然科學(xué)基金);the National Basic Research Program of China under Grant No.2011CB302604(國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃));the Baidu Cloud Service Platform Demonstration Project(百度云服務(wù)開(kāi)放平臺(tái)示范項(xiàng)目).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-09,http://www.cnki.net/kcms/detail/11.5602.TP.20151009.1639.010.html