淺析云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)

摘要：文章從云計(jì)算簡(jiǎn)介入手，對(duì)基于云計(jì)算的圖數(shù)據(jù)存儲(chǔ)方式、圖數(shù)據(jù)分割、圖數(shù)據(jù)計(jì)算模型以及圖數(shù)據(jù)查詢處理進(jìn)行了研究。期望通過(guò)本文的研究能夠?qū)Υ龠M(jìn)大規(guī)模圖數(shù)據(jù)處理技術(shù)的完善有所幫助。

關(guān)鍵詞：云計(jì)算；大規(guī)模圖數(shù)據(jù)；處理技術(shù)

中圖分類號(hào)：TP274 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-2374（2014）09-0053-02

1 云計(jì)算簡(jiǎn)介

1.1 云計(jì)算的涵義

云計(jì)算是在互聯(lián)網(wǎng)技術(shù)高速發(fā)展的背景下提出的一種全新的計(jì)算方法，它的核心是互聯(lián)網(wǎng)。云計(jì)算在2007年底由美國(guó)IBM公司提出，這是云計(jì)算首次出現(xiàn)在世人面前。IBM定義云計(jì)算如下：云計(jì)算一詞用于同時(shí)描述一個(gè)系統(tǒng)平臺(tái)或是一種類型的應(yīng)用程序。

1.2 云計(jì)算的特性

云計(jì)算的技術(shù)特性可歸納為以下幾個(gè)方面：

（1）虛擬化。用戶可以在連通網(wǎng)絡(luò)的任何位置用計(jì)算機(jī)、筆記本、手機(jī)等工具連接到云計(jì)算的服務(wù)器上實(shí)現(xiàn)各種計(jì)算任務(wù)。這些云計(jì)算服務(wù)器通常是集群，并且不具備有形的實(shí)體。

（2）通用性與可擴(kuò)展性。在規(guī)模龐大的集群的支撐下，云計(jì)算平臺(tái)能夠支持和構(gòu)造出各種各樣的應(yīng)用，而不僅僅針對(duì)特定的應(yīng)用，并且同一個(gè)云計(jì)算平臺(tái)可以同時(shí)支持不同的應(yīng)用同時(shí)運(yùn)行；云計(jì)算集群的規(guī)模具有動(dòng)態(tài)伸縮性，能夠滿足用戶以及應(yīng)用規(guī)模增長(zhǎng)的需要，這使其具備了良好的可擴(kuò)展性。

（3）經(jīng)濟(jì)性高。由于要同時(shí)支持很多的計(jì)算任務(wù)，云計(jì)算集群的規(guī)模非常龐大，如云計(jì)算服務(wù)提供商Google的云計(jì)算平臺(tái)的集群數(shù)量超過(guò)200萬(wàn)臺(tái)，其他提供商如IBM、微軟、雅虎的云計(jì)算集群也擁有幾十萬(wàn)臺(tái)，用戶可以從云計(jì)算集群當(dāng)中獲取到豐富的計(jì)算資源。幾乎所有的云計(jì)算集群服務(wù)器都是廉價(jià)設(shè)備，這是因?yàn)樵朴?jì)算本身具有超強(qiáng)的容錯(cuò)能力，它可以利用廉價(jià)的設(shè)備構(gòu)成云集群，這一點(diǎn)不但充分體現(xiàn)出了云計(jì)算的低成本優(yōu)勢(shì)，而且也為其大范圍推廣應(yīng)用奠定了基礎(chǔ)。

1.3 云計(jì)算的相關(guān)技術(shù)

（1）海量分布式存儲(chǔ)技術(shù)。分布式存儲(chǔ)是云計(jì)算存儲(chǔ)數(shù)據(jù)的主要方式，這在一定程度上確保了數(shù)據(jù)的高可靠性、可用性和經(jīng)濟(jì)性。其中數(shù)據(jù)存儲(chǔ)的高可靠性主要是憑借冗余存儲(chǔ)方式來(lái)實(shí)現(xiàn)的，通過(guò)可靠的軟件工具能夠有效彌補(bǔ)硬件方面存在的各種不足。因?yàn)樵朴?jì)算系統(tǒng)需要滿足大量的用戶使用需求，這就需要數(shù)據(jù)存儲(chǔ)技術(shù)應(yīng)該具有更高的傳輸速率和吞吐量，這樣才能為所有用戶并行地提供服務(wù)，而分布式的存儲(chǔ)方式恰恰可以滿足這一要求。

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

（3）虛擬化技術(shù)。目前，全球的IT界都在逐步邁入云計(jì)算的時(shí)代，雖然單個(gè)虛擬化技術(shù)也為IT方面帶來(lái)了諸多的利益，但不得不承認(rèn)的是，人們更看重是其全面的虛擬化戰(zhàn)略。在云計(jì)算的環(huán)境下，虛擬化的解決方法是系統(tǒng)整合方案，其集服務(wù)器、軟件、相關(guān)服務(wù)、存儲(chǔ)系統(tǒng)以及網(wǎng)絡(luò)設(shè)備等于一體，它帶給人們的是真正意義上的虛擬化服務(wù)。

（4）并行編程模式。由于數(shù)量眾多的用戶同時(shí)提供規(guī)模龐大的任務(wù)，云計(jì)算的編程模型必須確保后臺(tái)復(fù)雜的并行執(zhí)行和任務(wù)調(diào)度，這是有效利用云計(jì)算資源的前提也是基礎(chǔ)。目前，云計(jì)算一般都是采用Map Reduce作為編程模式，該模式為并行系統(tǒng)的數(shù)據(jù)處理提供了簡(jiǎn)單、有效、實(shí)用的解決方案，其優(yōu)勢(shì)在于歸并成本、高產(chǎn)出、性能更佳、效果更好、部署更容易。

2 云計(jì)算環(huán)境下大規(guī)模圖數(shù)據(jù)處理技術(shù)的研究

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

2.1 基于云計(jì)算的圖數(shù)據(jù)存儲(chǔ)方式

通過(guò)對(duì)大量的文獻(xiàn)進(jìn)行研究分析后發(fā)現(xiàn)，現(xiàn)階段，在大規(guī)模圖數(shù)據(jù)的管理應(yīng)用中，最為常用的數(shù)據(jù)模型有兩種，即單圖數(shù)據(jù)模型和超圖數(shù)據(jù)模型，這兩種模型全都能夠?qū)τ邢驁D和無(wú)向圖進(jìn)行處理，唯一的區(qū)別是兩者的存儲(chǔ)格式不同。云計(jì)算的分布式存儲(chǔ)系統(tǒng)是大規(guī)模圖數(shù)據(jù)存儲(chǔ)的基礎(chǔ)，大體上可將云計(jì)算的存儲(chǔ)系統(tǒng)分為以下兩種，分布式文件系統(tǒng)和分布式數(shù)據(jù)庫(kù)。分布式文件系統(tǒng)以GFS和HDFS為代表，能夠?qū)︵徑颖砗袜徑泳仃嚨冉Y(jié)構(gòu)進(jìn)行直接存放；分布式數(shù)據(jù)庫(kù)，即NoSQL，以Big Table和Hbase為代表。該數(shù)據(jù)庫(kù)所采用的數(shù)據(jù)模型可分為以下幾大類：DS模型（文檔存儲(chǔ)）、CFS模型（列族存儲(chǔ)）以及KV存儲(chǔ)模型等等。其中DS模型在存儲(chǔ)格式上具有靈活、方便的特點(diǎn)，適用于非結(jié)構(gòu)化數(shù)據(jù)的存儲(chǔ)，該模型不太適合存儲(chǔ)圖數(shù)據(jù)。大量的研究表明，KV存儲(chǔ)模型最為適合大規(guī)模圖數(shù)據(jù)的存儲(chǔ)。該模型具有存儲(chǔ)模式簡(jiǎn)單、高并發(fā)查詢、支持海量存儲(chǔ)等優(yōu)點(diǎn)。對(duì)Page Rank等圖數(shù)據(jù)處理而言，幾乎不涉及較為復(fù)雜的查詢操作，這樣KV模型基本可以滿足要求，如果圖數(shù)據(jù)以鄰接表的形式出現(xiàn)，可以圖的源頂點(diǎn)作為Key，以點(diǎn)的值和出邊信息為Value，這樣便可以進(jìn)行數(shù)據(jù)合并和遷移，有利于提高空間的局部性，并使查詢處理過(guò)程中數(shù)據(jù)讀取的次數(shù)大幅度減少，有助于數(shù)據(jù)讀取效率的提高。

2.2 基于云計(jì)算的圖數(shù)據(jù)分割

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

2.3 基于云計(jì)算的圖數(shù)據(jù)計(jì)算模型

目前，在云計(jì)算環(huán)境中應(yīng)用最為廣泛的模型有兩種，一種是Map Reduce模型，另一種是BSP模型。

（1）Map Reduce模型。是指一個(gè)并行處理作業(yè)由多個(gè)map與reduce任務(wù)共同構(gòu)成，作業(yè)的執(zhí)行也分為兩個(gè)階段，一個(gè)是Map階段，在該階段每一個(gè)map任務(wù)對(duì)分配給它的數(shù)據(jù)進(jìn)行相應(yīng)的計(jì)算，然后輸出key值，再將結(jié)果數(shù)據(jù)映射到與之相對(duì)應(yīng)的reduce任務(wù)中。另一個(gè)是Reduce階段，在該階段，每一個(gè)reduce任務(wù)會(huì)對(duì)接收到的數(shù)據(jù)進(jìn)行聚集處理，以此來(lái)獲取輸出結(jié)果，并將數(shù)據(jù)保存在分布式文件系統(tǒng)中。

（2）BSP模型。具體是指基于消息通信的并行執(zhí)行模式，它的特點(diǎn)是能夠避免死鎖以及數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題。

目前基于云計(jì)算的大規(guī)模圖數(shù)據(jù)處理主要應(yīng)用的也是這兩種模型，在迭代處理方面BSP模型的執(zhí)行效率要比Map Reduce模型高一些。

2.4 基于云計(jì)算的圖數(shù)據(jù)查詢處理

在云計(jì)算環(huán)境下，支持大規(guī)模圖數(shù)據(jù)查詢處理的驅(qū)動(dòng)模式主要有以下兩種：主動(dòng)遍歷模式和被動(dòng)遍歷模式。這兩種模式的共同點(diǎn)是操作對(duì)象都是圖頂點(diǎn)，具體而言，處理操作的核心都是圖頂點(diǎn)。

（1）主動(dòng)遍歷模式。該模式具有適用性強(qiáng)的優(yōu)點(diǎn)，但在某些特定的應(yīng)用當(dāng)中，有可能導(dǎo)致資源浪費(fèi)的情況發(fā)生。

（2）被動(dòng)遍歷模式。模式的優(yōu)點(diǎn)是無(wú)需調(diào)用處理函數(shù)，從而減少不必要的頂點(diǎn)調(diào)用處理開(kāi)銷，節(jié)省資源。

3 結(jié)語(yǔ)

綜上所述，本文以云計(jì)算環(huán)境為依托，對(duì)大規(guī)模圖數(shù)據(jù)處理的相關(guān)技術(shù)進(jìn)行了研究。結(jié)論表明，云計(jì)算的相關(guān)技術(shù)可用于大規(guī)模圖數(shù)據(jù)處理當(dāng)中，這充分體現(xiàn)出了云計(jì)算在數(shù)據(jù)處理中的廣泛適用性。

參考文獻(xiàn)

[1] 陳艷金.Map Reduce模型在Hadoop平臺(tái)下實(shí)現(xiàn)作

業(yè)調(diào)度算法的研究和改進(jìn)[D].華南理工大學(xué)，

2011.

[2] 杜清運(yùn)，虞昌彬，任福.利用嵌套金字塔模型進(jìn)

行瓦片地圖數(shù)據(jù)組織[J].武漢大學(xué)學(xué)報(bào)（信息科

學(xué)版），2011，（5）.

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

架及其平臺(tái)關(guān)鍵技術(shù)研究[D].浙江大學(xué)，2011.

作者簡(jiǎn)介：李淵（1985—），男，河南延津人，蘇州大學(xué)助理實(shí)驗(yàn)師，碩士。