淺析云計算環境下的大規模圖數據處理技術

摘要：文章從云計算簡介入手，對基于云計算的圖數據存儲方式、圖數據分割、圖數據計算模型以及圖數據查詢處理進行了研究。期望通過本文的研究能夠對促進大規模圖數據處理技術的完善有所幫助。

關鍵詞：云計算；大規模圖數據；處理技術

中圖分類號：TP274 文獻標識碼：A 文章編號：1009-2374（2014）09-0053-02

1 云計算簡介

1.1 云計算的涵義

云計算是在互聯網技術高速發展的背景下提出的一種全新的計算方法，它的核心是互聯網。云計算在2007年底由美國IBM公司提出，這是云計算首次出現在世人面前。IBM定義云計算如下：云計算一詞用于同時描述一個系統平臺或是一種類型的應用程序。

1.2 云計算的特性

云計算的技術特性可歸納為以下幾個方面：

（1）虛擬化。用戶可以在連通網絡的任何位置用計算機、筆記本、手機等工具連接到云計算的服務器上實現各種計算任務。這些云計算服務器通常是集群，并且不具備有形的實體。

（2）通用性與可擴展性。在規模龐大的集群的支撐下，云計算平臺能夠支持和構造出各種各樣的應用，而不僅僅針對特定的應用，并且同一個云計算平臺可以同時支持不同的應用同時運行；云計算集群的規模具有動態伸縮性，能夠滿足用戶以及應用規模增長的需要，這使其具備了良好的可擴展性。

（3）經濟性高。由于要同時支持很多的計算任務，云計算集群的規模非常龐大，如云計算服務提供商Google的云計算平臺的集群數量超過200萬臺，其他提供商如IBM、微軟、雅虎的云計算集群也擁有幾十萬臺，用戶可以從云計算集群當中獲取到豐富的計算資源。幾乎所有的云計算集群服務器都是廉價設備，這是因為云計算本身具有超強的容錯能力，它可以利用廉價的設備構成云集群，這一點不但充分體現出了云計算的低成本優勢，而且也為其大范圍推廣應用奠定了基礎。

1.3 云計算的相關技術

（1）海量分布式存儲技術。分布式存儲是云計算存儲數據的主要方式，這在一定程度上確保了數據的高可靠性、可用性和經濟性。其中數據存儲的高可靠性主要是憑借冗余存儲方式來實現的，通過可靠的軟件工具能夠有效彌補硬件方面存在的各種不足。因為云計算系統需要滿足大量的用戶使用需求，這就需要數據存儲技術應該具有更高的傳輸速率和吞吐量，這樣才能為所有用戶并行地提供服務，而分布式的存儲方式恰恰可以滿足這一要求。

（2）數據管理技術。由于云計算需要經常性的處理分析較大的數據集以完成用戶提交的計算任務，為此云計算數據管理技術必須具備對大數據集的高效管理能力，同時還要能夠從巨大的數據集當中找出特定的數據，以此來滿足用戶的應用需求。BigTable和Hbase是目前云計算數據管理技術中最知名，也是最常用的技術。

（3）虛擬化技術。目前，全球的IT界都在逐步邁入云計算的時代，雖然單個虛擬化技術也為IT方面帶來了諸多的利益，但不得不承認的是，人們更看重是其全面的虛擬化戰略。在云計算的環境下，虛擬化的解決方法是系統整合方案，其集服務器、軟件、相關服務、存儲系統以及網絡設備等于一體，它帶給人們的是真正意義上的虛擬化服務。

（4）并行編程模式。由于數量眾多的用戶同時提供規模龐大的任務，云計算的編程模型必須確保后臺復雜的并行執行和任務調度，這是有效利用云計算資源的前提也是基礎。目前，云計算一般都是采用Map Reduce作為編程模式，該模式為并行系統的數據處理提供了簡單、有效、實用的解決方案，其優勢在于歸并成本、高產出、性能更佳、效果更好、部署更容易。

2 云計算環境下大規模圖數據處理技術的研究

圖屬于一種非線性數據結構，其具有十分鮮明的多對多結構關系，圖數據當中每個元素都可以有零個或是多個直接前趨以及直接后繼。與其它數據結構形式相比，圖數據可以表達更加豐富的語義，其被廣泛應用于科研、工程等領域當中。由于可用的圖數據量非常之大，所以對大規模圖數據處理技術的研究一直是業界的重要課題。在專家學者的不斷研究中，圖的處理技術獲得了長足進步，與之相關的理論也日漸成熟，這為圖數據的應用提供了條件。然而，在信息時代到來的今天，各種各樣信息飛速增長，這在一定程度上造成了圖的規模越來越大，為此，應當對大規模圖數據的處理加大研究力度。云計算的提出為大規模圖數據處理提供了一個有效的平臺，下面本文就此展開詳細論述。

2.1 基于云計算的圖數據存儲方式

通過對大量的文獻進行研究分析后發現，現階段，在大規模圖數據的管理應用中，最為常用的數據模型有兩種，即單圖數據模型和超圖數據模型，這兩種模型全都能夠對有向圖和無向圖進行處理，唯一的區別是兩者的存儲格式不同。云計算的分布式存儲系統是大規模圖數據存儲的基礎，大體上可將云計算的存儲系統分為以下兩種，分布式文件系統和分布式數據庫。分布式文件系統以GFS和HDFS為代表，能夠對鄰接表和鄰接矩陣等結構進行直接存放；分布式數據庫，即NoSQL，以Big Table和Hbase為代表。該數據庫所采用的數據模型可分為以下幾大類：DS模型（文檔存儲）、CFS模型（列族存儲）以及KV存儲模型等等。其中DS模型在存儲格式上具有靈活、方便的特點，適用于非結構化數據的存儲，該模型不太適合存儲圖數據。大量的研究表明，KV存儲模型最為適合大規模圖數據的存儲。該模型具有存儲模式簡單、高并發查詢、支持海量存儲等優點。對Page Rank等圖數據處理而言，幾乎不涉及較為復雜的查詢操作，這樣KV模型基本可以滿足要求，如果圖數據以鄰接表的形式出現，可以圖的源頂點作為Key，以點的值和出邊信息為Value，這樣便可以進行數據合并和遷移，有利于提高空間的局部性，并使查詢處理過程中數據讀取的次數大幅度減少，有助于數據讀取效率的提高。

2.2 基于云計算的圖數據分割

通常情況下，基于云計算的大規模圖數據處理，需要進行分布式并行處理，由于圖數據的連通性特點以及圖計算的強耦合性特點，為了進一步提高對圖數據的并行處理效率，需要對各子圖之間的耦合度進行降低，而圖分割則是實現這一目標的有效途徑之一。具體過程如下：首先分割一個邏輯結構相對比較完整的大圖，然后將分割的部分分別放到分布式存儲系統的各個工作節點中，再進行處理，即針對每個子圖啟動一個與之相對應的計算任務，當所有子圖全部處理完畢后，就完成了一個大圖的處理。在這一過程中，對大圖進行分割，并獲得較好的分割效果是關鍵之所在，在分割時要考慮圖內部的連通性以及子圖規模的均衡性兩方面的因素。要盡可能的提高圖內部的連通性，并降低各個子圖之間的連通性，這有利于云計算分布式并行處理機制的應用；另外盡量考慮子圖規模的均衡性，盡量不要出現過大的偏斜，以免造成任務執行時間差距過大，影響同步性。

2.3 基于云計算的圖數據計算模型

目前，在云計算環境中應用最為廣泛的模型有兩種，一種是Map Reduce模型，另一種是BSP模型。

（1）Map Reduce模型。是指一個并行處理作業由多個map與reduce任務共同構成，作業的執行也分為兩個階段，一個是Map階段，在該階段每一個map任務對分配給它的數據進行相應的計算，然后輸出key值，再將結果數據映射到與之相對應的reduce任務中。另一個是Reduce階段，在該階段，每一個reduce任務會對接收到的數據進行聚集處理，以此來獲取輸出結果，并將數據保存在分布式文件系統中。

（2）BSP模型。具體是指基于消息通信的并行執行模式，它的特點是能夠避免死鎖以及數據競爭問題。

目前基于云計算的大規模圖數據處理主要應用的也是這兩種模型，在迭代處理方面BSP模型的執行效率要比Map Reduce模型高一些。

2.4 基于云計算的圖數據查詢處理

在云計算環境下，支持大規模圖數據查詢處理的驅動模式主要有以下兩種：主動遍歷模式和被動遍歷模式。這兩種模式的共同點是操作對象都是圖頂點，具體而言，處理操作的核心都是圖頂點。

（1）主動遍歷模式。該模式具有適用性強的優點，但在某些特定的應用當中，有可能導致資源浪費的情況發生。

（2）被動遍歷模式。模式的優點是無需調用處理函數，從而減少不必要的頂點調用處理開銷，節省資源。

3 結語

綜上所述，本文以云計算環境為依托，對大規模圖數據處理的相關技術進行了研究。結論表明，云計算的相關技術可用于大規模圖數據處理當中，這充分體現出了云計算在數據處理中的廣泛適用性。

參考文獻

[1] 陳艷金.Map Reduce模型在Hadoop平臺下實現作

業調度算法的研究和改進[D].華南理工大學，

2011.

[2] 杜清運，虞昌彬，任福.利用嵌套金字塔模型進

行瓦片地圖數據組織[J].武漢大學學報（信息科

學版），2011，（5）.

[3] 方雷.基于云計算的土地資源服務高效處理理論框

架及其平臺關鍵技術研究[D].浙江大學，2011.

作者簡介：李淵（1985—），男，河南延津人，蘇州大學助理實驗師，碩士。