一種基于關(guān)系數(shù)據(jù)庫管理系統(tǒng)的圖計算平臺

蔣奎,陳亮

(1.河北軌道運輸職業(yè)技術(shù)學(xué)院,石家莊050021; 2.微軟亞洲研究院,北京100080)

一種基于關(guān)系數(shù)據(jù)庫管理系統(tǒng)的圖計算平臺

蔣奎1,陳亮2

(1.河北軌道運輸職業(yè)技術(shù)學(xué)院,石家莊050021; 2.微軟亞洲研究院,北京100080)

本文提出了一種新的基于關(guān)系數(shù)據(jù)庫管理系統(tǒng)(Relational Database Management System,RDBMS)(本文簡稱關(guān)系數(shù)據(jù)庫)的圖計算平臺.該平臺將圖數(shù)據(jù)以原生的形式在關(guān)系數(shù)據(jù)庫的表格中存儲,從而在數(shù)據(jù)表達(dá)上和原生圖計算平臺達(dá)到了一致.該平臺將圖計算邏輯完整準(zhǔn)確地表達(dá)為SQL(Structured Query Language)查詢語句.關(guān)系數(shù)據(jù)庫執(zhí)行SQL查詢語句,從而完成圖計算,并將結(jié)果返回.實驗結(jié)果表明,該新的平臺有效地利用了關(guān)系數(shù)據(jù)庫成熟的查詢優(yōu)化技術(shù),在很多方面優(yōu)于現(xiàn)有的原生數(shù)據(jù)平臺;而目前的性能局限,也會隨著未來關(guān)系數(shù)據(jù)庫的不斷演化和迭代,得到有效的解決.

關(guān)系數(shù)據(jù)庫管理系統(tǒng);圖計算;原生圖計算平臺

0 引言

圖數(shù)據(jù)在今天的企業(yè)環(huán)境中無處不在,它的大量出現(xiàn)使得越來越多的應(yīng)用需要高效地分析、處理、計算圖數(shù)據(jù),進(jìn)而對圖計算平臺產(chǎn)生了大量的需求.雖然今天關(guān)系數(shù)據(jù)庫(RDBMS)在企業(yè)中是最為重要的數(shù)據(jù)平臺,但它的成功常常被看作僅僅局限于表格數(shù)據(jù),而在圖計算領(lǐng)域面臨著諸多困難.事實上,在最近的NoSQL(Not Only SQL)趨勢中,大量的原生圖計算平臺紛紛涌現(xiàn)[1-3],其中的絕大部分放棄了關(guān)系數(shù)據(jù)庫,從而完全重新設(shè)計、實現(xiàn)針對圖數(shù)據(jù)的存儲和查詢引擎.

原生圖計算平臺和關(guān)系數(shù)據(jù)最明顯的區(qū)別體現(xiàn)在兩方面:數(shù)據(jù)存儲和計算語言.和關(guān)系數(shù)據(jù)庫的表格相比,原生圖計算平臺中最為自然的表達(dá)圖的數(shù)據(jù)結(jié)構(gòu)為鄰接表(Adjacency List).鄰接表為一個鏈表,鏈表中的每一個元素代表了一條指向鄰居節(jié)點的邊.物理表達(dá)上,鏈表中的每個元素為鄰居節(jié)點的ID(Identification).通過鏈表中的ID可以在底層存儲中定位每個鄰居節(jié)點.如果每條邊上還附帶有屬性,則鏈表中的元素從節(jié)點ID變?yōu)橐粋€元組(Tuple),該元祖不僅包含鄰居節(jié)點的ID,還包含邊上的屬性.

在原生圖計算平臺中,廣泛采用的編程模型為BSP(Bulk Synchronous Parallel)模型[4]. BSP模型最早在并行計算中被提出,因為近些年在Google的Pregel圖計算平臺上被采用而廣為人知[5].BSP模型將圖中的每一個節(jié)點定義為一個計算單元,每個計算單元維護(hù)自己的狀態(tài),并不斷從它的鄰居節(jié)點接收鄰居的狀態(tài),用它們來更新自己的狀態(tài).該更新過程一直持續(xù),直到所有節(jié)點的狀態(tài)都已經(jīng)收斂,或者某個定義的參數(shù)滿足某些條件.正像Google在Pregel中展示的那樣,大多數(shù)圖計算算法都可以通過該模型來表達(dá),比如最短路徑、PageRank算法以及最小生成樹(Minimal Spanning Tree).

基于鄰接表的數(shù)據(jù)表達(dá)以及BSP的編程模型,看起來和傳統(tǒng)關(guān)系數(shù)據(jù)庫的表格以及SQL語句有著巨大差距.長久以來,基于關(guān)系數(shù)據(jù)庫的圖計算研究一直十分有限.如何利用關(guān)系數(shù)據(jù)庫成熟、高效的查詢優(yōu)化技術(shù)來支持圖計算,不僅有學(xué)術(shù)價值,還有著深遠(yuǎn)的實際價值,能使數(shù)百萬關(guān)系數(shù)據(jù)庫的用戶更為方B地利用現(xiàn)有平臺滿足新的計算需求.

本文提出了一種新的基于關(guān)系數(shù)據(jù)庫(RDBMS)的計算平臺.該平臺采用了和原生圖計算平臺相同的數(shù)據(jù)結(jié)構(gòu)來表示圖數(shù)據(jù):鄰接表.在該數(shù)據(jù)表達(dá)之上,平臺利用SQL查詢語句表達(dá)BSP程序邏輯,并將該SQL語句在底層的關(guān)系數(shù)據(jù)庫運行.SQL查詢語句包含了迭代邏輯,在每一輪迭代中不斷更新節(jié)點上的狀態(tài),直到收斂.同時,圖算法的優(yōu)化可以同通過SQL語句準(zhǔn)確清晰地表達(dá)出來,極大地提高了圖計算的性能.

在本文中,平臺的實現(xiàn)以SQL Server數(shù)據(jù)庫為基礎(chǔ).SQL Server數(shù)據(jù)庫是主流關(guān)系數(shù)據(jù)庫之一.本文中介紹的用于實現(xiàn)鄰接表和BSP編程的技術(shù),在其他關(guān)系數(shù)據(jù)庫中也可以找到相應(yīng)的對應(yīng).

1 圖在關(guān)系數(shù)據(jù)庫中的表達(dá)和解析

在本節(jié)中,我們分別討論鄰接表以及圖數(shù)據(jù)在關(guān)系數(shù)據(jù)庫中的表示和操作,這是圖計算的基礎(chǔ).

1.1 圖的表達(dá):鄰接表

圖數(shù)據(jù)由節(jié)點和邊組成.節(jié)點和邊上可以附帶額外的屬性.一個節(jié)點上的所有出邊(Outgoing Edges)組成了一個鄰接表(Adjacency List),表中的每一個元素代表了一條指向鄰居節(jié)點的邊.在物理表達(dá)上,鄰接表中的每個元素為一個元組(Tuple),它包含了這條邊所指向的鄰居節(jié)點的ID,以及該邊上的屬性.類似,一個節(jié)點上的所有入邊(Incoming Edges),組成了另外一個鄰接表,其中的每一個元祖代表了一條指向節(jié)點自己的邊.在圖的操作中,給定一個節(jié)點,訪問該節(jié)點的鄰居十分方B:通過遍歷鄰接表,可以方B地知道每個鄰居節(jié)點的ID,通過ID也就可以進(jìn)一步定位到鄰居節(jié)點.

盡管鄰接表十分方B圖的遍歷,但在關(guān)系數(shù)據(jù)庫中表達(dá)鄰接表卻十分困難.其根本原因在于,關(guān)系數(shù)據(jù)庫中表格的一列無法存儲一個鏈表;一個多值集合只能存到額外的表格中,并通過主鍵(Primary Key)和外鍵(Foreign Key)將兩張表格聯(lián)系起來,進(jìn)而喪失了鄰接表的方B.在系統(tǒng)實現(xiàn)中,這個困難直接導(dǎo)致了眾多系統(tǒng)開發(fā)人員放棄了關(guān)系數(shù)據(jù)庫作為圖數(shù)據(jù)的存儲引擎,進(jìn)而設(shè)計原生圖存儲.

本文提出了一種新的在關(guān)系數(shù)據(jù)庫中表達(dá)鄰接表的方式,克服了上述提到的困難.其基本思想如下:盡管鄰接表無法直接存儲于表格的一列中,但它可以被序列化為二進(jìn)制字符串.現(xiàn)有的關(guān)系數(shù)據(jù)庫都對變長二進(jìn)制字符串有著很好的支持,會自動根據(jù)字符串的長短分配地址空間.因此通過將鏈表序列化,就能把鄰接表存放于表格的一列中,達(dá)到和原生圖存儲相同的數(shù)據(jù)表達(dá).

給定鄰接表的表達(dá),圖數(shù)據(jù)可以方B地存儲在關(guān)系數(shù)據(jù)庫的表格中:每一個節(jié)點映射到表的一行;節(jié)點的每一個屬性,映射到表格的一列;節(jié)點出邊的鄰接表和入邊的鄰接表分別映射到兩個特殊的二進(jìn)制字符串列.圖1給出了一個社交網(wǎng)絡(luò)圖在SQL Server數(shù)據(jù)庫的存儲樣例.在該表格中,第一列存儲節(jié)點ID;第二列存儲節(jié)點上的屬性,即每位用戶的姓名;第三列存儲出邊的鄰接表.在SQL Server數(shù)據(jù)庫中,鄰接表以二進(jìn)制字符串存儲.

圖1 社交網(wǎng)絡(luò)圖在SQL Server數(shù)據(jù)庫中存儲樣例Fig.1An example of a social network graph in SQL Server

1.2 圖的解析

把鄰接表以二進(jìn)制字符串存儲在關(guān)系表格中,關(guān)系數(shù)據(jù)庫的查詢引擎無法知曉該字符串的語義,也就無法用傳統(tǒng)的SQL語句來實現(xiàn)圖的遍歷.本節(jié)介紹如何通過SQL Server數(shù)據(jù)庫的擴展技術(shù),將鄰接表解析為SQL Server數(shù)據(jù)庫可見的數(shù)據(jù),進(jìn)而用SQL語句實現(xiàn)從一個節(jié)點游走到鄰居節(jié)點.該技術(shù)對其他關(guān)系數(shù)據(jù)庫同樣適用.

圖的單步游走包含了3個基本步驟:①將節(jié)點從底層存儲中取出;②遍歷該節(jié)點上的鄰接表;③對于每個鄰居節(jié)點指針(即鄰居節(jié)點ID),定位到相應(yīng)的節(jié)點.第一步操作對應(yīng)為SQL查詢語句中的一個或多個查詢條件.第二步操作是一個遍歷操作,因為關(guān)系數(shù)據(jù)庫只能對表格進(jìn)行遍歷,因此,二進(jìn)制表達(dá)的鄰接表必須首先轉(zhuǎn)化為表格.在SQL Server數(shù)據(jù)庫中,這樣的轉(zhuǎn)化由TVF(Table-Valued Function)函數(shù)來實現(xiàn).TVF函數(shù)是一個用戶自定義函數(shù),由C#實現(xiàn),它傳入一個標(biāo)量數(shù)據(jù),返回的則是表格數(shù)據(jù).TVF函數(shù)必須實現(xiàn)3個標(biāo)準(zhǔn)接口Reset()、Current以及MoveNext(),使得SQL Server數(shù)據(jù)庫能不斷調(diào)用這些接口,將標(biāo)量數(shù)據(jù)轉(zhuǎn)化為表格數(shù)據(jù).TVF函數(shù)的接口和定義參見圖2.

在圖計算平臺中,我們把解析鄰接表的TVF函數(shù)稱為Transpose.Transpose傳入的是二進(jìn)制表達(dá)的鄰接表.通過TVF函數(shù)中MoveNext()的實現(xiàn),Transpose完成對二進(jìn)制字符串的解析.通過Current接口,它不斷地將當(dāng)前解析出的邊返回給SQL Server數(shù)據(jù)庫引擎.SQL Server數(shù)據(jù)庫將新解析出的邊插入到臨時表格中,并通過該臨時表格將鄰居節(jié)點的ID最終傳遞給下一級的SQL語句.二進(jìn)制表示的鄰接表的完整解析過程參見圖3.在圖中,鄰接表被解析到一個臨時表中.臨時表包含兩列,第二列Sink包含了每個起始節(jié)點的鄰居指針.

圖2 TVF函數(shù)的接口與定義Fig.2Interfaces and definition of a table-valued function(TVF)

圖3 二進(jìn)制鄰接表的解析Fig.3Decoding of serialized adjacency lists

在鄰接表被解析成臨時表格之后,單步游走的最后一步通過Join操作完成,即將臨時表的每一個鄰居指針(即鄰居ID)和鄰居節(jié)點關(guān)聯(lián)起來.完整的查詢語句如下所示.

SELECT friend.NodeID,friend.Name

FROM SocialTable AS user CROSS APPLY Transpose(user.Friends)AS E

JOIN SocialTable AS friend on E.Sink=friend.NodeID

WHERE user.Name=‘John Smith'

2 圖計算編程和優(yōu)化

2.1 BSP實現(xiàn)簡述

BSP(Bulk Synchronous Parallel)為現(xiàn)有圖計算平臺的主要編程模型,它給每個節(jié)點定義一個狀態(tài),每個節(jié)點根據(jù)鄰居的狀態(tài)不斷更新自己的狀態(tài),直到狀態(tài)收斂.BSP模型又分為“同步BSP”和“異步BSP”.同步BSP規(guī)定每個節(jié)點第k輪的狀態(tài)由其所有鄰居的k一1輪狀態(tài)決定.因此,只有當(dāng)所有節(jié)點的第k一1輪狀態(tài)計算完畢,節(jié)點的k輪狀態(tài)才能開始計算,即存在一個全局的分界點將第k輪計算和第k一1輪計算明確地分隔開.相比而言,異步BSP則放松了每一輪更新對鄰居節(jié)點狀態(tài)的要求,節(jié)點的第k輪狀態(tài)可以由其鄰居節(jié)點的k一l輪狀態(tài)決定,l≥1.由此,異步BSP并不需要全局的分界點將所有節(jié)點的k一1輪計算和k輪計算分隔開來.在任意時刻,有些節(jié)點的狀態(tài)處于第k輪,而有些節(jié)點的狀態(tài)可能已經(jīng)是第k+l輪,l＞1.同步BSP與異步BSP比較起來,邏輯清晰,實現(xiàn)簡單.因此也成為圖計算平臺主要的編程模型.在本文的討論中,我們主要關(guān)注同步BSP.

同步BSP可以在本文提出的圖計算平臺上通過SQL語句方B地表達(dá)和實現(xiàn).每個節(jié)點的狀態(tài)映射到表格中的一列.在每一輪迭代中,每個節(jié)點需要從鄰居接受其上一輪的狀態(tài).這個操作通過解析鄰接表以及Join操作將每個節(jié)點和鄰居節(jié)點關(guān)聯(lián)起來.接著,每個節(jié)點的狀態(tài)更新表達(dá)為基于該節(jié)點的聚合函數(shù)(Aggregation Function).最后通過SQL提供的循環(huán)語句控制迭代.因為在關(guān)系數(shù)據(jù)庫中,兩次循環(huán)的執(zhí)行不會重疊,兩次循環(huán)之間存在著一個全局分界點.由此,所有節(jié)點的同步也得到天然的保障.

BSP編程模型及其對應(yīng)的SQL語句有很強的表達(dá)力,能表達(dá)多種圖算法,比如最短路徑和最小生成樹.因為每個算法細(xì)節(jié)不同,實現(xiàn)起來也各不一樣,在本文中無法窮盡.在下面的討論中,我們著重關(guān)注一個很有代表性的實例:PageRank算法的實現(xiàn)和優(yōu)化.其他圖算法可以類似實現(xiàn).

2.2 PageRank算法實現(xiàn)

PageRank算法是鏈接分析里很重要的一個算法.它通過迭代運算給每個節(jié)點賦予一個分?jǐn)?shù).分?jǐn)?shù)越高的節(jié)點,重要性越高.在迭代初始狀態(tài),所有節(jié)點被賦予相同的分?jǐn)?shù).以上面提到的社交網(wǎng)絡(luò)為例,我們將圖1中的表格擴展一列Score,用來存儲每個節(jié)點的分?jǐn)?shù).在每一輪迭代中,每個節(jié)點將自己的分?jǐn)?shù)和指向自己的鄰居的分?jǐn)?shù)加權(quán)疊加,得到自己新的分?jǐn)?shù).當(dāng)節(jié)點的分?jǐn)?shù)更新后不再改變,則該節(jié)點收斂;當(dāng)所有節(jié)點收斂后,迭代運算也就終止.我們將圖1中的表格再擴展一列Converge來表示每個節(jié)點在哪一輪收斂,Converge=0表示該節(jié)點還未收斂.

圖4展示了PageRank實現(xiàn)的代碼樣例.在循環(huán)內(nèi)部中,SQL語句通過Transpose函數(shù)解析鄰接表,并通過Join將每條邊的起點和終點關(guān)聯(lián)起來.在此基礎(chǔ)之上,SQL通過GROUP BY語句和聚合函數(shù)計算每個節(jié)點新的PageRank分?jǐn)?shù).該聚合函數(shù)是一個簡單的求和函數(shù),將每個節(jié)點鄰居的分?jǐn)?shù)加權(quán)求和.在代碼中,BinaryCount是另一個自定義函數(shù),用來計算給定鄰接表的長度.

2.3 PageRank算法優(yōu)化

圖4給出的PageRank的代碼是在SQL Server數(shù)據(jù)庫上最樸素的實現(xiàn).針對具體的圖算法特性,經(jīng)常會有算法級別的優(yōu)化.這類優(yōu)化不依賴于底層系統(tǒng),和具體算法緊密相關(guān),因此很難抽象為統(tǒng)一的優(yōu)化策略而在系統(tǒng)中實現(xiàn).一個好的圖計算平臺應(yīng)該提供有足夠表達(dá)力的語言,使得算法設(shè)計和實現(xiàn)者能在該平臺上將這些優(yōu)化準(zhǔn)確、簡潔地實現(xiàn)出來.本文提出的計算平臺,利用SQL語句表達(dá)算法邏輯,能很好地滿足這一需求.本小節(jié)以PageRank為例,展示如何利用SQL語句來實現(xiàn)PageRank算法的優(yōu)化.

PageRank的計算是一個非常耗時的過程,很重要的一個原因就是每一輪迭代需要對全圖進(jìn)行遍歷.同時,只要有任何節(jié)點沒有收斂,迭代就要一直進(jìn)行下去.之前的研究者觀察到一個很重要的現(xiàn)象,可以用來極大的降低計算復(fù)雜度[6]:在PageRank分?jǐn)?shù)的計算過程中,只有少數(shù)分?jǐn)?shù)很高的節(jié)點遲遲不能收斂;大多數(shù)分?jǐn)?shù)較低的節(jié)點在開始幾輪迭代后很快就收斂了,在迭代過程中,已經(jīng)收斂的節(jié)點就不用再繼續(xù)計算了;同時,收斂節(jié)點對于未收斂節(jié)點分?jǐn)?shù)的貢獻(xiàn)也就固定不變了.如果在每輪迭代中,重用收斂節(jié)點的分?jǐn)?shù)以及它們對其他節(jié)點的貢獻(xiàn),那每一輪的迭代就可以避免重復(fù)計算,從而大大降低計算復(fù)雜度.下面我們將該優(yōu)化思想以數(shù)學(xué)公式嚴(yán)格地表達(dá)出來.

圖4 PageRank實現(xiàn)代碼樣例Fig.4PageRank implementation using SQL

PageRank的計算可以用迭代公式

描述,其中,X是一個向量,每一維代表了一個節(jié)點的PageRank分?jǐn)?shù),Xk代表了第k輪迭代后所有節(jié)點的分?jǐn)?shù),A為圖的鄰接矩陣.

我們將上述的所有優(yōu)化移植到圖4的SQL語句中,就得到了優(yōu)化后的PageRank算法實現(xiàn),如圖5所示.圖5和圖4代碼的不同之處在圖5中通過加黑高亮出來.在內(nèi)部查詢語句里,加入了條件

該條件用在每一輪選出未收斂節(jié)點或者有最新收斂的節(jié)點.每一輪查詢語句計算兩個數(shù)值: scoren和deltac.前者對應(yīng),計算了所有未收斂節(jié)點之間互相的分?jǐn)?shù)貢獻(xiàn);后者對應(yīng)在每一輪的增量.

圖5 PageRank優(yōu)化后的PageRank實現(xiàn)Fig.5An optimized implementation of PageRank in SQL

3 實驗結(jié)果

本節(jié)對本文提出的基于關(guān)系數(shù)據(jù)庫的圖計算平臺進(jìn)行實驗評估.底層的關(guān)系數(shù)據(jù)庫為SQL Server數(shù)據(jù)庫.我們選取GraphLab作為對比系統(tǒng)[3].GraphLab是一個用C++編寫的并行圖計算平臺,它提供了BSP類型的編程接口,使得開發(fā)者能夠方B地在上面實現(xiàn)圖算法.GraphLab的系統(tǒng)以迭代式圖算法為主要設(shè)計目標(biāo),其性能也以迭代式算法而著稱.在數(shù)據(jù)存儲上,GraphLab將節(jié)點以對象的形式存儲在內(nèi)存中.在默認(rèn)模式下,GraphLab僅僅維護(hù)內(nèi)存對象,而不會將這些對象同步到磁盤上.因為完全避免了磁盤訪問,這種模式會給GraphLab帶來極大的性能優(yōu)勢.但另一方面,這種模式對于關(guān)系數(shù)據(jù)庫并不公平.在關(guān)系數(shù)據(jù)庫里,任何更新都有事務(wù)(Transaction)保障,所有操作的結(jié)果都時時同步到磁盤上,以防硬件出錯和機器重啟以后結(jié)果丟失.沒有了同步機制,如果運算因為各種原因中斷,GraphLab將會丟失所有中間結(jié)果,而不得不從頭開始.因此,GraphLab也提供了同步機制,允許使用者指定一定的間隔將所有節(jié)點同步到磁盤上.在實驗中,我們分別考慮了下面兩種模式下的性能.

我們選取了兩組數(shù)據(jù)來評估PageRank算法在基于SQL Server數(shù)據(jù)庫的圖平臺和GraphLab上的運行效率.兩組數(shù)據(jù)都來自斯坦福大學(xué)發(fā)布的萬維網(wǎng)超鏈接圖,兩組數(shù)據(jù)的大小如表1所示.

表1 實驗數(shù)據(jù)集Tab.1Experiment data sets

我們首先測量了GraphLab在有同步機制下和SQL Server數(shù)據(jù)庫的性能比較.GraphLab在PageRank每輪迭代完后,將當(dāng)前圖的狀態(tài)同步到磁盤上.在每組實驗中,我們分別測量了無優(yōu)化的PageRank算法和優(yōu)化后的PageRank的算法.實驗結(jié)果如圖6所示.可以看到,在這組實驗中,基于SQL Server數(shù)據(jù)庫的PageRank性能遠(yuǎn)遠(yuǎn)好于GraphLab.當(dāng)PageRank算法沒有任何優(yōu)化時,兩個系統(tǒng)迭代次數(shù)相同.在每輪迭代中,因為所有節(jié)點的分?jǐn)?shù)都要更新一遍,和磁盤之間同步的數(shù)據(jù)量也相同.但是基于SQL Server數(shù)據(jù)庫的圖計算的性能仍然大大高于GraphLab.我們將這樣的性能差距歸咎于關(guān)系數(shù)據(jù)庫長期以來的對磁盤讀寫的優(yōu)化.相比較而言,GraphLab開發(fā)時間較短,在磁盤讀寫上還有很多設(shè)計和實現(xiàn)需要優(yōu)化.對于優(yōu)化后的PageRank算法,SQL Server數(shù)據(jù)庫的性能優(yōu)勢更加明顯;性能提升在20倍左右.這是因為,優(yōu)化后的PageRank算法每一輪迭代只會更新還未收斂的節(jié)點.在開始幾輪迭代后,需要更新的節(jié)點數(shù)量銳減,進(jìn)而磁盤讀寫也會大大降低.而GraphLab并未實現(xiàn)增量式同步機制.所以每一輪迭代后,所有節(jié)點都要被寫回磁盤,即使它的狀態(tài)沒有任何更新.GraphLab在這種模式下,幾乎沒有享受到PageRank算法優(yōu)化所帶來的好處.

圖6 GraphLab磁盤和SQL Server數(shù)據(jù)庫PageRank性能比較Fig.6Performance comparison between GraphLab-disk and SQL Server

在第二組比較實驗中,我們測量GraphLab在沒有同步機制下的性能.實驗結(jié)果如圖7所示.可以看到,當(dāng)GraphLab沒有任何磁盤讀寫時,其性能大大好于基于SQL Server數(shù)據(jù)庫的實現(xiàn).考慮到磁盤讀寫遠(yuǎn)遠(yuǎn)慢于內(nèi)存操作,GraphLab在完全沒有磁盤訪問的情況下,這樣的性能差距并不意外.從另一方面看,將數(shù)據(jù)放在內(nèi)存中從而完全避免磁盤操作,并不是圖數(shù)據(jù)的專利.在近些年,隨著內(nèi)存容量不斷擴大,內(nèi)存價格不斷走低,越來愈多的內(nèi)存型關(guān)系數(shù)據(jù)應(yīng)運而生.傳統(tǒng)商業(yè)數(shù)據(jù)庫也開始逐步將內(nèi)存數(shù)據(jù)庫的概念、技術(shù)融入到其存儲、查詢引擎中.可以預(yù)見,隨著內(nèi)存技術(shù)在關(guān)系數(shù)據(jù)庫中成熟,圖7中的性能差距會越來越小,甚至消失.

圖7 GraphLab內(nèi)存和SQL Server數(shù)據(jù)庫PageRank性能比較Fig.7Performance comparison between GraphLab-memory and SQL Server

4 結(jié)論

本文提出了一種基于關(guān)系數(shù)據(jù)庫的圖計算平臺.該平臺將圖的拓?fù)浣Y(jié)構(gòu)以鄰接表的形式存儲在表格中,從而達(dá)到了和原生圖計算平臺相同的數(shù)據(jù)格式.在此基礎(chǔ)上,利用SQL語句豐富的表達(dá)力,將BSP編程模型下的圖算法簡潔、準(zhǔn)確地表達(dá)出來.SQL語句進(jìn)而被關(guān)系數(shù)據(jù)庫高效地執(zhí)行,最終將圖計算結(jié)果返回.實驗結(jié)果表明,基于關(guān)系數(shù)據(jù)庫的圖計算與原生圖平臺比較起來,在很多方面都有性能優(yōu)勢.目前存在的性能局限,和圖數(shù)據(jù)本身并無關(guān)系.隨著關(guān)系數(shù)據(jù)庫的發(fā)展、演化,這些局限最終都可以被彌補、消除,在各類場景下提供高效的圖計算支持.

［1］GONZALEZ J E,LOW Y,GU H J,et al.PowerGraph:Distributed graph-parallel computation on natural graphs[C]//Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation. 2012:17-30.

［2］KYROLA A,BLELLOCH G,GUESTRIN C.GraphChi:Large-scale graph computation on just a PC [C]//Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation.2012: 31-46.

［3］LOW Y,GONZALEZ J E,KYROLA A,et al.GraphLab:A new framework for parallel machine learning[J]. Computer Science,2014:arXiv:1408.2041[cs.LG].

［4］VALIANT L G.A bridging model for parallel computation[J].Communications of the ACM,1990,33(8):103-111.

［5］MALEWICZ G,AUSTERN M H,BIK A J C,et al.Pregel:A system for large-scale graph processing [C]//Proceedings of the 28th ACM Symposium on Principles of Distributed Computing.2009:6-16.

［6］Kamvar S,Haveliwala T,Golub G.Adaptive methods for the computation of PageRank[J].Linear Algebra and its Applications,2004,386:51-65.

(責(zé)任編輯:李藝)

A RDBMS-based graph computing platform

JIANG Kui1,CHEN Liang2
(1.Hebei Vocational College of Rail Transportation,Shijiazhuang,050021 China; 2.Microsoft Research Asia,Beijing100080,China)

This paper proposes a new RDBMS-based(relational database management system)graph computing platform.In this platform,graph data is represented in native data structures,achieving the same representation as in native graph computing systems. On top of this native representation,graph algorithms are expressed as SQL(Structured Query Language)statements,which are executed by the underlying relational database systems.Experimental results show that this new graph computing platform leverages mature SQL technologies on query optimization and execution,thereby providing superior performance in many aspects.Its current performance limitations,on the other hand,will be overcome by future evolution and optimization of relational database systems.

RDBMS(relational database management system);graph computing; native graph computing platforms

TP392

A

10.3969/j.issn.1000-5641.2016.05.012

1000-5641(2016)05-0103-09

2016-05

蔣奎,男,高級講師,研究方向為鐵道車輛及鐵道信息系統(tǒng).E-mail:mwong56@gmail.com.

陳亮,男,研究員,研究方向為數(shù)據(jù)庫及信息系統(tǒng).E-mail:jeche@microsoft.com.