詹杭龍，曹東剛+，謝　冰

1.北京大學 高可信軟件技術教育部重點實驗室，北京 100871 2.北京大學（天津濱海）新一代信息技術研究院，天津 300450

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

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

1.北京大學 高可信軟件技術教育部重點實驗室，北京 100871 2.北京大學（天津濱海）新一代信息技術研究院，天津 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.

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

圖處理；分布式并行計算；彈性伸縮；任務遷移

1　引言

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

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

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

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

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

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

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

本文主要有如下貢獻：提出了一種面向并行圖處理的任務模型；設計了一個支持動態(tài)任務調度的圖處理框架；引入了一種動態(tài)調度遷移機制，初步實現了彈性伸縮。

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

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

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

2.1圖結構的分區(qū)與派發(fā)

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

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

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

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

2.2迭代執(zhí)行

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

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

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

2.3迭代執(zhí)行運行時需要考慮的調度問題

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

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

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

經過上述分析，本文概括了現有圖處理框架中的運行時調度機制在彈性伸縮方面所存在的不足，如下：

（1）缺乏一個圖處理問題的任務模型，導致對彈性伸縮性的研究不夠清晰、直觀；

（2）以頂點作為負載均衡的粒度過小，需要一個合適粒度的調度方案；

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

3　SParTaG框架的設計與實現

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

為此，首先對圖處理應用構建任務模型，明確其任務的結構和依賴關系；其次，設計彈性伸縮的分布式圖處理框架SParTaG，并介紹其任務遷移機制；最后，設計基于負載均衡的調度算法實現動態(tài)擴展。

3.1圖處理應用的任務模型

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

定義操作符f，用于描述在每個超級步中對每一個頂點的運算過程?；贐SP計算模型，每一個頂點vx首先處理其入邊所相鄰的頂點在前一個超級步所發(fā)送來的消息，更新自身的狀態(tài)，而后發(fā)送新消息給其出邊所相鄰的頂點。定義如下符號進行描述：

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

Msg(OutEdge(vx))[s]，在頂點vx的第s個超級步所發(fā)送的所有消息；

Msg(InEdge(vx))[s]，在頂點vx的第s個超級步所收到的所有消息。

于是，有：

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

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

而對頂點vx的第s步運算過程 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]作為參數傳入，更新vx的值成為State(vx)[s+1]，并產生消息組Msg(OutEdge(vx))[s]用于傳播數據。更進一步，對分區(qū)Pz的第s步運算過程可表示為：

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

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

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

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

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

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

3.2SParTaG框架與編程接口

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

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

（1）任務雙向隊列負責記錄該運算節(jié)點所分配的一系列圖分區(qū)，以及維護該運算節(jié)點所執(zhí)行的超級步。

Fig.3　Architecture of distributed SParTaG圖3　分布式SParTaG架構圖

（2）channel為消息接收信箱，負責記錄該運算節(jié)點所接收到的用于下一超級步運算所需的消息集合。在運算初始時，因為尚無消息傳遞，所以每個運算節(jié)點的channel均為空。

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

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

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

從任務雙向隊列中獲取圖分區(qū)數據

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

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

調用應用程序接口處理這些消息，更新頂點狀態(tài)；

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

}

將buffer中的消息根據目標頂點的不同發(fā)送到相應運算節(jié)點的channel中

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

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

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

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

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

在SParTaG框架中，任務遷移機制通過任務雙向隊列來實現。任務雙向隊列提供兩種類型的獲取任務接口，如圖5所示。如果是本地的運算節(jié)點請求獲取任務，則調用fetch_task接口從任務雙向隊列的隊首取出圖分區(qū)返回；如果是遠程的運算節(jié)點需要遷移任務，則可根據調度決策的需要以任務ID為索引，調用migrate_task接口從任務雙向隊列中獲取若干塊對應的任務數據。

Fig.5　Two operations of task queue圖5　任務隊列的兩種操作

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

在遷移過程中，圖分區(qū)數據和對應的消息集合都要進行傳輸。

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

Fig.6　Diagram of task migration圖6　任務遷移過程

任務遷移機制既可以讓圖分區(qū)擴展到新的計算節(jié)點，也可以對現有計算節(jié)點進行收縮，把待收縮節(jié)點中的圖分區(qū)遷移到剩余的工作節(jié)點，因此任務遷移是實現動態(tài)伸縮的重要途徑。

3.4運行時監(jiān)控與基于負載均衡的調度

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

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

（1）獲取所有worker的負載信息；

（2）判斷當前的負載是否均衡；

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

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

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

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

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

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

算法1伸縮調度算法

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

輸出：任務遷移列表。

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

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

3.設任務遷移列表為空；

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

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

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

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

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

3.5分布式索引表

在系統(tǒng)的實現過程中，還有一個問題需要考慮。頂點之間的數據傳遞是通過進程發(fā)送消息實現的，而進程發(fā)送消息需要指明消息傳輸的目的地。因此，在作業(yè)運行過程中，圖的每一個頂點均需要有地址屬性，說明該頂點位于哪一個運算節(jié)點中。當頂點a向頂點b傳遞數據時，它需要先知道頂點b屬于哪一個運算節(jié)點，再向該運算節(jié)點發(fā)送消息。此外，由于SParTaG引入了任務遷移機制，在作業(yè)運行過程中，某些頂點可能遷移到新的運算節(jié)點中，改變了地址屬性，這個時候發(fā)送給這些遷移頂點的消息就需要更新其目標運算節(jié)點。

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

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

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

4　實驗結果與分析

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

表1展示了幾個圖數據的信息。圖處理算法為PageRank應用和單源最短路徑（single source shortest path，SSSP）應用。

Table 1　Size of input graph表1　圖數據大小

4.1SParTaG與Giraph的性能測試

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

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

由該實驗可知，對于不同尺寸的圖數據，靜態(tài)SParTaG具有與Giraph可比的性能。此外，通過該實驗也可以發(fā)現，對于同等尺寸的實際圖和隨機圖，處理時間是不一樣的。以LiveJournal與R_Graph A為例，圖的尺寸均為頂點4.8×106，邊68×106，在SParTaG中用PageRank算法處理LiveJournal的時間是123.933 s，處理R_Graph A的時間是106.039 s。這是因為實際圖LiveJournal中邊的分布并不均衡，導致在處理過程中各個worker的運算時間有長有短，每個超級步所花時間更久，因而總時間更長。這就需要動態(tài)調度機制來提升性能。

4.2擴展性

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

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

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

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

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

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

此外，在兩個圖的執(zhí)行過程中動態(tài)加入兩臺機器，圖12中的Elastic Scaling R_Graph B與Elastic ScalingArabic為執(zhí)行效果。彈性伸縮機制使得SParTaG能夠將作業(yè)動態(tài)地擴展到新增機器上，而不用重啟系統(tǒng)，并減少了運算時間，實現了即時（on the fly）加速。

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

4.4彈性伸縮的運行剖面圖

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

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

Fig.14　Execution profile of every superstep圖14　每個超級步的運算用時對比

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

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

5　相關工作與討論

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

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

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

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

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

6　結束語

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

未來的工作重點主要包含以下兩個方面：一方面考慮改進圖的分區(qū)算法，以基于子圖邊密度的策略實現對圖結構的均衡劃分；另一方面考慮改進調度算法，以更細致的負載指標來指導任務調度。

[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.

附中文參考文獻：

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

[2]盧錫城,王懷民,王戟.虛擬計算環(huán)境iVCE:概念與體系結構[J].中國科學:E輯信息科學,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—），男，福建漳州人，北京大學信息科學技術學院博士研究生，主要研究領域為大數據，系統(tǒng)軟件，分布式并行計算等。

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年于北京大學信息科學技術學院獲得博士學位，現為北京大學信息科學技術學院軟件所副教授，主要研究領域為系統(tǒng)軟件，分布并行處理等。發(fā)表學術論文30余篇，承擔過國家973計劃、863計劃、自然科學基金等多個項目，獲國家技術發(fā)明二等獎，電子學會電子信息科學技術一等獎。

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年于國防科技大學計算機學院獲得博士學位，現為北京大學信息科學技術學院軟件所教授、博士生導師，主要研究領域為軟件工程，形式化方法，軟件復用等。發(fā)表學術論文80余篇，主持多項國家863計劃重點項目，獲國家科技進步二等獎、技術發(fā)明二等獎等。

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(國家自然科學基金);the National Basic Research Program of China under Grant No.2011CB302604(國家重點基礎研究發(fā)展計劃(973計劃));the Baidu Cloud Service Platform Demonstration Project(百度云服務開放平臺示范項目).

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