劉恩孚　冷芳玲　鮑玉斌

摘要：提出了一個基于整體同步并行計算（BSP）模型的、具有磁盤暫存功能的大規(guī)模圖處理系統(tǒng)——BC-BSP。該系統(tǒng)通過提供應用程序接口（API）實現(xiàn)系統(tǒng)配置和有關策略的可擴展性，通過優(yōu)化的圖數(shù)據(jù)磁盤存儲實現(xiàn)了數(shù)據(jù)處理規(guī)模的高可擴展性以及高性能的容錯方案，并且可以處理普通數(shù)據(jù)集的聚類和分類等需要迭代計算的數(shù)據(jù)挖掘算法。通過實驗驗證了該系統(tǒng)的可擴展性，其在真實數(shù)據(jù)集上性能優(yōu)于Giraph1.0.0，在模擬數(shù)據(jù)集上稍遜于Giraph的內存版。

關鍵詞：BSP；大規(guī)模圖處理；迭代計算；磁盤緩存

Abstract：We describe a bulk synchronous parallel （BSP）-based parallel iterative processing system for graph data with disk caching assist. This system is called BC-BSP. The system can achieve the scalability of system configuration and policy by providing APIs， high scalability of the data scale processed， and high performance of fault-tolerant scheme by disk storage optimization to graph data. It can also execute some data mining algorithms with iterative processing， such as clustering and classification on non-graph data sets. The experimental results show that the scalability and performance of the proposed system are better than that of Giraph1.0.0 on the real data set，but it is lightly poorer than the memory version of Giraph.

Key words：BSP； large-scale graph processing； iterative computing； disk cache

圖是計算機科學中最常用的一類抽象數(shù)據(jù)結構，更具有一般性的表示能力?，F(xiàn)實世界中的許多應用場景都可以很自然地使用圖結構表示。例如，交通運輸網(wǎng)絡、社交網(wǎng)絡中的資源對象之間的關系以及生物信息網(wǎng)絡等。在大數(shù)據(jù)時代，需要分析的圖規(guī)模越來越大。以互聯(lián)網(wǎng)和社交網(wǎng)絡為例，隨著互聯(lián)網(wǎng)的深入使用和Web 2.0技術的推動，網(wǎng)頁數(shù)量增長迅猛，據(jù)中國互聯(lián)網(wǎng)絡信息中心（CNNIC）統(tǒng)計：截止2014年12月中國網(wǎng)頁規(guī)模達到1 899億個，年增長率26.6%；而基于互聯(lián)網(wǎng)的社交網(wǎng)絡更是如此，如全球最大的社交網(wǎng)絡Facebook，2014年7月已有約22億用戶，其中月活躍用戶數(shù)13億人。在中國，如QQ空間、微博、開心網(wǎng)等，發(fā)展也異常迅猛。因此，實際應用中圖的頂點可達10億，而邊就會更多，對應的數(shù)據(jù)文件會更大。對如此大規(guī)模圖數(shù)據(jù)的存儲和分析處理的時間和空間開銷遠遠超出了傳統(tǒng)集中式圖數(shù)據(jù)處理的承受能力。因此，對大規(guī)模圖的有效處理成為了一個新的挑戰(zhàn)。

MapReduce計算模型可以實現(xiàn)對大規(guī)模（圖）數(shù)據(jù)的處理，并且具有很好的容錯性和可擴展性。但是由于圖數(shù)據(jù)分析（如網(wǎng)頁的PageRank[1]計算、最短路徑計算、聚類分析）都需要多次迭代才能完成。每次迭代需要一個或多個開銷較大的MapReduce作業(yè)完成。為解決迭代計算的時間性能問題，谷歌公司開發(fā)了基于整體同步并行計算（BSP）模型的Pregel[2]系統(tǒng)，之后Apache的兩個開源項目Hama和Giraph也開展了基于BSP的迭代計算系統(tǒng)的開發(fā)。它們都是在內存中做數(shù)據(jù)處理，因此能夠處理的圖的規(guī)模有限。文中，我們設計開發(fā)了基于BSP模型的、能夠處理大規(guī)模（圖）數(shù)據(jù)的并行迭代計算系統(tǒng)——BC-BSP。該系統(tǒng)主要特色在于：（1）實現(xiàn)了具有磁盤輔助的基于BSP的大規(guī)模圖數(shù)據(jù)并行迭代處理系統(tǒng)，該系統(tǒng)在內存受限的情況下具有很好的數(shù)據(jù)處理能力，即在可用的節(jié)點規(guī)模和內存配置的情況下，可以處理的數(shù)據(jù)規(guī)模較大；（2）系統(tǒng)多方面考慮負載均衡，在充分考慮數(shù)據(jù)本地化的前提下考慮了各個節(jié)點的負載均衡問題，并且結點的負載均衡優(yōu)先于數(shù)據(jù)本地化。我們做了大量的實驗，比較了基于BSP的大規(guī)模圖處理系統(tǒng)的性能和擴展性。

1 BSP模型和相關工作

BSP是一種“塊”同步模型[3]，即通過消息傳遞機制，實現(xiàn)塊內異步并行，塊間顯式同步。一個基于BSP的計算系統(tǒng)是由具有處理機和存儲器的多個自治的計算服務器組成的集群，并且這個集群采用主/從結構。主節(jié)點用于協(xié)調整個集群，包括接收用戶的作業(yè)提交、作業(yè)調度、故障監(jiān)控等功能，從節(jié)點（也稱為工作節(jié)點）用于存儲和處理數(shù)據(jù)。

谷歌公司開發(fā)的基于BSP模型的分布式圖計算框架Pregel主要是為了處理大規(guī)模圖數(shù)據(jù)，如網(wǎng)頁的PageRank計算、最短路徑等。Pregel假設處理的數(shù)據(jù)都在內存中，因此在一定的節(jié)點規(guī)模下，它能夠處理的數(shù)據(jù)規(guī)模是有限制的。基于Pregel的思想，許多基于BSP的大規(guī)模圖處理系統(tǒng)被開發(fā)出來。例如，Apache推出了基于Java的開源項目Hama[4]，它是一個純粹的基于BSP的用于大規(guī)?？茖W計算（如矩陣計算、圖和網(wǎng)絡算法）的計算框架，同樣它的早期版本沒有考慮磁盤輔助的問題，而是假設所有數(shù)據(jù)全部位于內存中，最新的版本也在添加磁盤輔助功能，但是很不完善；而Apache的另一個開源項目Giraph，是建立在Hadoop基礎之上的Pregel的開源實現(xiàn)[5]，可以認為它是MapReduce模型和BSP模型的結合體，即它利用MapReduce作業(yè)的Map任務實現(xiàn)了基于BSP模型的迭代計算，而不需要Reduce任務，整個圖處理過程只需要啟動一次MapRedcue作業(yè)，但是一旦出現(xiàn)故障，整個作業(yè)需要重新啟動；GraphLab是卡內基梅隆大學提出的面向大規(guī)模數(shù)據(jù)挖掘和圖計算的分布式內存計算框架[6]。更多的基于BSP模型的類Pregel的大規(guī)模數(shù)據(jù)分布式并行處理系統(tǒng)和框架請見文獻[7]。

2 BC-BSP概述

圖1給出了BC-BSP系統(tǒng)的整體結構，主要包括BSP核心層、管理接口層和接口層。BC-BSP實現(xiàn)了對Hadoop分布式文件系統(tǒng)（HDFS）、HBase、MySQL等底層存儲系統(tǒng)的支持，包括數(shù)據(jù)的輸入和輸出。BC-BSP系統(tǒng)內部核心層主要包括客戶端作業(yè)提交和數(shù)據(jù)劃分，主節(jié)點端的作業(yè)調度和集群監(jiān)控，從節(jié)點端的本地計算處理、全局同步、消息通信和容錯控制；接口層主要包括應用編程接口（API）和命令行接口（CLI）；管理接口層主要包括集群管理、系統(tǒng)自動化安裝部署、日志管理、性能管理和故障管理等工具。

從系統(tǒng)實現(xiàn)的角度，BC-BSP系統(tǒng)是一個主從式結構，主要分為客戶端、主控節(jié)點、工作節(jié)點、任務模塊、全局同步模塊。圖2給出了BC-BSP的運行控制機制以及系統(tǒng)中客戶端、主控節(jié)點、工作節(jié)點、任務模塊、全局同步模塊之間的協(xié)作關系。

在BC-BSP系統(tǒng)中，客戶端主要根據(jù)用戶指定的輸入路徑進行數(shù)據(jù)分片，調整分區(qū)數(shù)目，檢查作業(yè)運行的可行性，向主控節(jié)點申請作業(yè)并將作業(yè)打包提交給BSP主控節(jié)點，當作業(yè)開始運行后，負責及時反饋作業(yè)運行狀態(tài)；主控節(jié)點端管理集群工作節(jié)點的注冊、心跳信息和狀態(tài)信息收集等，并作為容錯控制的控制中心，提供各種狀態(tài)查詢接口，并以作業(yè)為單位，負責作業(yè)的初始化、調度和同步控制等；工作節(jié)點端主要負責工作節(jié)點本地的任務管理和局部同步控制以及局部聚集計算等；任務模塊端是任務運行的實體，主要負責執(zhí)行用戶的業(yè)務處理邏輯和數(shù)據(jù)輸入輸出處理等；全局同步負責同一作業(yè)的所有任務在各個超步之間的全局同步工作，超步路障同步由主節(jié)點端、工作節(jié)點端及任務模塊端共同完成，在同步過程中，可以完成聚集計算，系統(tǒng)中的同步主要通過第三方組件Zookeeper實現(xiàn)；消息通信主要在每一個超步的本地計算執(zhí)行過程中，負責異步地發(fā)送和接收消息，并將接收的消息暫存到本地的接收消息隊列中，當內存空間不足時，支持磁盤輔助存儲，這里主要是通過遠程過程調用協(xié)議（RPC）機制實現(xiàn)消息傳遞；容錯控制模塊負責容錯備份、故障檢測和故障恢復等功能，以寫檢查點機制作為主要的容錯方案，支持手動備份和自動周期備份功能；管理工具主要通過Web界面或命令行的方式為用戶提供可視化的系統(tǒng)管理和監(jiān)控功能；接口模塊主要為用戶提供本地計算、消息發(fā)送/接收等的應用編程接口，以及為用戶提供啟動和關閉系統(tǒng)服務、作業(yè)提交等命令行接口。

3 BC-BSP提供的API

系統(tǒng)給用戶提供了與作業(yè)建立相關的API，用于編寫針對圖處理或科學計算的處理程序。另外，系統(tǒng)還提供了用于系統(tǒng)功能擴展的接口。下面我們簡單介紹這些接口。

（1）消息管理接口負責消息的發(fā)送/接收功能，在每一個超步的本地計算執(zhí)行過程中，并行地發(fā)送和接收消息，并將接收的消息緩存到本地的接收消息隊列中，在發(fā)送消息隊列達到一定規(guī)模的時候，執(zhí)行Combine操作，然后再將消息發(fā)送給目的節(jié)點。

（2）分區(qū)數(shù)據(jù)管理接口負責在進行圖數(shù)據(jù)處理之前將待處理的圖數(shù)據(jù)按照一定的原則劃分給各個任務。本系統(tǒng)實現(xiàn)了基于Hash的劃分方法和基于Hash的均衡劃分方法。

（3）圖頂點上下文接口負責在任務處理的一個超步中，處理每個圖頂點時獲取正在處理的圖頂點的相關屬性信息和方法。

（4）消息合并接口在圖處理過程中，通常以頂點為中心進行處理，該接口為了減少在網(wǎng)絡上傳送的消息數(shù)量，在發(fā)送端對發(fā)給同一個頂點的消息進行合并。

（5）聚集計算接口許多圖處理/機器學習算法中需要聚集計算，實現(xiàn)該接口可進行超步間的聚集值計算。

（6）數(shù)據(jù)輸入輸出接口包括輸入接口和輸出接口，用于實現(xiàn)將數(shù)據(jù)從指定數(shù)據(jù)存儲系統(tǒng)中讀入和寫出。

4 BC-BSP系統(tǒng)的實現(xiàn)

本節(jié)介紹BC-BSP系統(tǒng)在實現(xiàn)上的一些主要策略和細節(jié)，主要包括圖數(shù)據(jù)的表示、主節(jié)點控制器、從節(jié)點管理器、本地計算與消息通信、圖數(shù)據(jù)劃分以及故障恢復等的實現(xiàn)。

4.1 主節(jié)點控制器

主控節(jié)點是整個BC-BSP集群的控制中心，負責管理所有的工作節(jié)點，監(jiān)控整個集群的工作狀態(tài)，接收各工作節(jié)點的心跳信息并加以處理，完成整個作業(yè)的全局同步控制，并提供統(tǒng)一的信息查詢接口和作業(yè)提交接口。當集群啟動后，主控節(jié)點接收各工作節(jié)點的注冊信息，形成統(tǒng)一的集群資源信息，在運行過程中通過心跳信息不斷更新集群資源信息，例如，可用任務槽數(shù)量。當客戶端請求提交作業(yè)時，將其放入作業(yè)等待隊列，作業(yè)調度器按照優(yōu)先級加先入先出隊列（FIFO）的策略調度作業(yè)；而完成一個作業(yè)的具體任務的調度則是按照負載均衡和數(shù)據(jù)本地化的原則。因為本系統(tǒng)中一個作業(yè)的所有任務需要同時運行，所以系統(tǒng)中的任務調度是采用由BSP主節(jié)點控制器根據(jù)上述原則將任務依次不斷下推給各個節(jié)點。

4.2 從節(jié)點管理器

工作節(jié)點是硬件上的計算單元，系統(tǒng)啟動后，BC-BSP集群的各個節(jié)點上啟動一個從節(jié)點管理器（WM）進程，負責完成具體的任務啟動和消息通信。每個工作節(jié)點啟動后，都首先向主控節(jié)點注冊，使自己成為BC-BSP集群中的一員；之后，工作節(jié)點定期向主控節(jié)點發(fā)送心跳信息，匯報自己的狀態(tài)；當有新任務下達時，工作節(jié)點根據(jù)新任務的指令，到HDFS上讀取作業(yè)信息并下載到本地文件系統(tǒng)；然后創(chuàng)建任務控制對象和對應的執(zhí)行進程，接著運行任務。WM為在本節(jié)點上運行的每個作業(yè)建立一個WorkerAgent對象，用于收集該作業(yè)在本節(jié)點上的各個任務的心跳信息、工作狀態(tài)信息等。這樣全局同步采用兩級同步方式，即一個工作節(jié)點上的屬于同一個作業(yè)的各個任務在本節(jié)點上實現(xiàn)局部同步，然后再以節(jié)點為單位向Zookeeper注冊實現(xiàn)全局同步。工作節(jié)點以作業(yè)為單位維護在本節(jié)點上運行的隸屬于同一個作業(yè)的所有任務，進行統(tǒng)一管理，完成各種局部操作，例如本地聚集計算。

4.3 磁盤輔助的本地計算和消息通信

任務模塊是邏輯上的計算處理單元，稱為一個任務。BSP主節(jié)點控制器中的任務調度器根據(jù)負載均衡和數(shù)據(jù)本地化原則將任務分配到具體的工作節(jié)點上，由WM創(chuàng)建該任務模塊進程。任務模塊啟動后，首先完成數(shù)據(jù)加載，將需要處理的數(shù)據(jù)分片從存儲介質上按照指定的輸入格式讀入本地，并進行數(shù)據(jù)劃分。計算過程中會定期地向WM的WorkerAgent對象發(fā)送心跳信息，報告任務的狀態(tài)等信息。

在Pregel系統(tǒng)以及基于它思想的各種實現(xiàn)中，都假設集群的處理節(jié)點足夠，使得待處理的數(shù)據(jù)等夠完全存放在內存中。但是實際情況卻不是這樣的：一方面對于一個給定的待處理數(shù)據(jù)集，用戶很難確定需要幾個工作節(jié)點才能使得各個任務處理的數(shù)據(jù)能夠存放在內存中；另一方面，當集群規(guī)模有限時，也希望能夠處理相對較大規(guī)模的數(shù)據(jù)。對于系統(tǒng)中發(fā)送（或接收）的消息也是如此。鑒于以上原因，本系統(tǒng)中使用了磁盤臨時存儲數(shù)據(jù)和消息（也稱之為磁盤暫存），以便能夠處理較大規(guī)模的數(shù)據(jù)。

對于消息數(shù)據(jù)，將消息數(shù)據(jù)的內存占用比例按照用戶指定的靜態(tài)劃分參數(shù)確定，系統(tǒng)運行時處理各種類型的消息時內存的使用單獨分配處理，每種類型的消息內存占用都具有一個獨立的閾值控制。

對于任務處理的數(shù)據(jù)而言，在迭代計算過程中常駐磁盤。對于出邊表不變的計算情況，即不增加也不刪除邊的情形，將頂點的出邊表與頂點的其他在計算中變化的部分，例如頂點的值或標簽等信息，分開存放，但是同樣使用記錄的ID的Hash映射進行劃分，如圖3所示。將圖數(shù)據(jù)分開處理的好處在于：每次迭代結束只需將本次迭代過程中變化的數(shù)據(jù)寫回本地磁盤文件即可，不變的靜態(tài)部分不需要寫回磁盤，同時也為容錯控制提供了方便。

4.4 圖的頂點類

一個圖是由頂點集合和邊集合構成，因此有頂點類和邊類。本系統(tǒng)中使用鄰接表的方式組織圖數(shù)據(jù)。這樣一個頂點類中除了頂點本身的屬性之外，還有與之相連的出邊信息，同時提供了對頂點和邊進行操作的方法（見圖4）。

4.5 數(shù)據(jù)劃分

數(shù)據(jù)劃分是BSP計算與MapReduce計算不同的地方。前者需要在迭代計算中能夠定位消息發(fā)送的目的地在哪里。因此，數(shù)據(jù)劃分是將各個任務與之綁定的數(shù)據(jù)分片的數(shù)據(jù)從數(shù)據(jù)源讀入，然后利用一定的數(shù)據(jù)劃分原則，例如Hash劃分，將圖數(shù)據(jù)分配給某個任務，以便形成超步迭代計算時的數(shù)據(jù)分區(qū)。

一個作業(yè)的各個數(shù)據(jù)分區(qū)大小是否均勻直接影響系統(tǒng)的負載均衡，但是Hash函數(shù)很難保證各個分區(qū)大小的均衡。為此，我們采用了多Hash桶合并的劃分方法，以實現(xiàn)數(shù)據(jù)的近似均衡劃分。合并的原則可以是各個桶中的對象數(shù)據(jù)盡可能均衡，還可以考慮數(shù)據(jù)的本地性。本系統(tǒng)目前是按照各個桶中數(shù)據(jù)對象近似均衡為主兼顧本地性的原則進行合并。

4.6 容錯機制

容錯是本分布式處理系統(tǒng)必須考慮的問題。BC-BSP系統(tǒng)中考慮兩類故障：一類是任務故障，例如任務進程宕掉；另一類是工作節(jié)點故障，例如一個Worker出現(xiàn)網(wǎng)絡斷開故障或者磁盤讀寫故障。系統(tǒng)中各個任務通過心跳機制向所在Worker的WM匯報自己的工作狀態(tài)，而各個工作節(jié)點也是通過心跳機制定期向BSP主節(jié)點控制器匯報工作狀態(tài)。

本模塊包括寫檢查點、故障檢測和故障診斷以及故障恢復等功能。寫檢查點是定期或者人工控制方式將某個時刻的作業(yè)運行快照保存到分布式文件系統(tǒng)，如HDFS；故障檢測與故障診斷是完成故障信息的收集與故障類型的判斷，不同階段的不同類型的故障，采用不同的恢復機制。BC-BSP系統(tǒng)實現(xiàn)了基本的基于檢查點的故障恢復策略和面向磁盤駐留的多級容錯處理策略。

所謂的面向磁盤駐留的多級容錯處理策略，是利用了本系統(tǒng)的磁盤輔助機制的一些措施，即將圖數(shù)據(jù)分成不變的常駐磁盤的靜態(tài)部分（例如圖頂點的出邊表）和每次迭代計算幾乎都會變化的需要寫回磁盤的動態(tài)部分。因此在進行系統(tǒng)快照備份時，實現(xiàn)增量備份，即對圖數(shù)據(jù)的靜態(tài)部分只需要備份一次即可，而每次迭代計算時只需增量地備份動態(tài)變化部分。當然每次備份時需要備份本次收到的所有消息。

5 BC-BSP系統(tǒng)應用示例

本節(jié)討論使用本系統(tǒng)進行圖數(shù)據(jù)的PageRank計算和多維數(shù)值型數(shù)據(jù)集的k-means聚類分析的示例。在k-means示例中，可以論證BC-BSP系統(tǒng)也可以有效地處理非圖數(shù)據(jù)的數(shù)據(jù)挖掘算法。

5.1 PageRank

使用BC-BSP系統(tǒng)實現(xiàn)PageRank計算中，首先將一個頂點的PageRank值按照一定的規(guī)則（如各個出邊頂點平分），通過發(fā)送消息的方式發(fā)送給出邊頂點，同時獲得來自入邊頂點的消息；之后按照PageRank算法的PageRank值計算公式，將一個頂點的消息值（即PageRank貢獻值）累加，計算當前頂點新的PageRank值。因此用戶可以提供combine方法實現(xiàn)消息發(fā)送前的合并，再基于頂點的新PageRank值重復上面的計算過程，直到滿足收斂條件結束計算，并按預先的用戶配置輸出計算結果。

5.2 多維數(shù)值型數(shù)據(jù)集的k-means

聚類

使用BC-BSP系統(tǒng)對多維數(shù)值型數(shù)據(jù)集進行k-means聚類，不需要進行頂點間的消息傳遞，但是需要利用聚集器計算新的聚類中心，可以通過各個聚簇的所有數(shù)據(jù)點的累計和與累計數(shù)據(jù)點計數(shù)兩種聚集器實現(xiàn)。因此，用戶可以實現(xiàn)BC-BSP系統(tǒng)提供的staffStartup接口，完成整個聚類作業(yè)開始之前的聚類中心初始化工作，例如讀取預先設定好的存儲在分布式文件中的初始聚類中心，利用系統(tǒng)提供的聚集器接口實現(xiàn)聚簇內數(shù)據(jù)點累計和與累計計數(shù)計算新的聚類中心，這樣就需要每個任務計算自己任務內的局部累計和與累計計數(shù)，然后在BSP主節(jié)點控制器計算各個類的總累計和以及總類內數(shù)據(jù)點數(shù)，在新的超步開始時計算聚集中心。

當k-means聚類的k值較?。ɡ鐜资畟€）時，這種利用聚集器的方法是可行的。然而，實驗中我們發(fā)現(xiàn)：當k值上百或更大時，就會出現(xiàn)異常。這是因為需要向Zookeeper寫的內容太多。因為系統(tǒng)框架中聚集器的實現(xiàn)利用了Zookeeper，所以在實現(xiàn)k-means聚類時，使用了分布式文件暫存各個任務的局部聚集結果。在執(zhí)行超步計算前讀取這些臨時文件，計算新的聚類中心，可以解決k值較大時引起的異常問題。

6 BC-BSP系統(tǒng)的實驗

選擇同樣基于BSP模型的Hama[4]和Giraph[5]作為參照比較系統(tǒng)，并且使用它們的API實現(xiàn)了PageRank算法。實驗軟硬件配置是：30個工作節(jié)點，一個作為控制節(jié)點，29個用作存儲和計算的工作節(jié)點，Java虛擬機（JVM）的內存設置為2 GB。每個節(jié)點的配置如下：Intel Core i3-2100雙核中央處理器（CPU）、8 GB雙倍速率同步動態(tài)隨機存儲器（DDR）3內存、500 G/7200 RPM磁盤，安裝了Red Hat Centos 6.0操作系統(tǒng)、JDK1.6.0-30、Hadoop-0.20.2和Zookeeper-3.3.2。統(tǒng)計了運行PageRank 10次迭代的運行時間開銷。

測試數(shù)據(jù)采用不同規(guī)模的真實數(shù)據(jù)和人工合成數(shù)據(jù)；人工合成數(shù)據(jù)集由數(shù)據(jù)生成器生成。實驗中我們選擇了定點規(guī)模不同的5個真實數(shù)據(jù)集[8]，它們的統(tǒng)計信息見表1。

6.1 真實數(shù)據(jù)集測試結果

利用表1中描述的5個真實數(shù)據(jù)集，在Giraph1.0.0的內存版（Giraph 1.0.0_MEM）和磁盤版（Giraph 1.0.0_HDD）、Hama 0.6.4和BC-BSP 2.0系統(tǒng)上分別運行了PageRank算法，得到了圖5所示的結果。

由圖5展示的結果可得出：BC-BSP2.0的性能優(yōu)于另外3個對比系統(tǒng)，總體上比Giraph1.0.0的內存版的性能好。

6.2虛擬數(shù)據(jù)集測試結果

通過測試虛擬數(shù)據(jù)集進行系統(tǒng)可擴展性的對比，我們可知：數(shù)據(jù)從1 000萬頂點至11 000萬頂點，主要用于測試系統(tǒng)的可擴展性和計算性能，平均出度規(guī)模為11.5。

由圖6展示的結果可得出：圖數(shù)據(jù)的頂點從1 000萬到11 000萬，BC-BSP 2.0在數(shù)據(jù)吞吐量以及在相同數(shù)據(jù)集的處理效率上都要優(yōu)于HAMA-0.6.4，并優(yōu)于GIRAPH-1.0.0_HDD，效率略低于GIRAPH-1.0.0_MEM，但可擴展性更好。

7 結束語

文章描述了在Java語言環(huán)境下基于BSP模型實現(xiàn)的用于大規(guī)模圖數(shù)據(jù)迭代處理的系統(tǒng)BC-BSP。該系統(tǒng)在Pregel思想的基礎上，實現(xiàn)了它的基本功能，同時增加了若干優(yōu)化策略，包括增加了均衡的數(shù)據(jù)劃分策略，使得每個任務處理的節(jié)點數(shù)量盡可能相近，圖數(shù)據(jù)處理和消息通信過程中的磁盤暫存使得在計算節(jié)點及其內存資源有限的情況下可以處理較大的數(shù)據(jù)，具有更高的可擴展性。

盡管在系統(tǒng)開發(fā)過程中已經(jīng)做了大量的優(yōu)化工作，但是系統(tǒng)還有可優(yōu)化的地方。例如，關于圖數(shù)據(jù)結構的優(yōu)化與改進：（1）目前不論是圖頂點對象還是邊對象都采用字符串方式存儲，可以改成支持泛型的實現(xiàn)；（2）系統(tǒng)利用寫檢查點機制實現(xiàn)了故障恢復，但是對于故障類型的捕獲和診斷還有待進一步加強；（3）在系統(tǒng)實現(xiàn)中發(fā)現(xiàn)Java環(huán)境對內存的開銷巨大，因此對數(shù)據(jù)結構的設計以及使用需要仔細地斟酌。

致謝

本研究得到東北大學于戈教授和谷峪副教授的幫助，以及中國移動（蘇州）研發(fā)中心錢嶺博士的支持，謹致謝意！

本系統(tǒng)開發(fā)工作是由東北大學計算機軟件所王志剛博士研究生以及許多已經(jīng)畢業(yè)的研究生共同完成，對他們謹致謝意！

參考文獻

[1] SERGEY B， LARRY P. The Anatomy of a Large-Scale Hypertextual Web Search Engine [J]. Computer Networks and ISDN Systems， 1998， 30（98）： 1-7

[2] GUERON M， LLIA R， MARGULIS G. Pregel： A System for Large-Scale Graph Processing [J]. American Journal of Emergency Medicine， 2009， 18（18）：135-146

[3] VALIANT L G. Bulk-Synchrony： A Bridging Model for Parallel Computation [J]. Communications of the ACM， 1990， 33（8）：103-111

[4] Welcome to Hama Project [EB/OL].[2011-07-13] . http：//incubator.apache.org/hama/

[5] AVERY C， CHRISTAN K. Giraph： Large-Scalegraph Processing Infrastructure on Hadoop [EB/OL]. [2011-06-29]. Hadoop Summit 2011， https：//github.com/aching/Giraph

[6] LOW Y， BICKSON D， GONZALEZ J， GUESTRIN C， et al. Distributed GraphLab： A Framework for Machine Learning and Data Mining in the Cloud [J]. Proceedings of the VLDB Endowment， 2012， 5（8）： 716-727

[7] MAMOU H. An Experimental Comparison of Pregel-Like Graph Processing Systems [C]// Proceedings of Vldb Endowment. USA： ACM 2014： 7（12）：1047-1058

[8] Using the Stanford Large Network Dataset Collection [EB/OL]， https：//snap.stanford.edu /data/index.html