蔣奎,陳亮

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

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

蔣奎1,陳亮2

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 圖的解析

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

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

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

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

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

在鄰接表被解析成臨時(shí)表格之后,單步游走的最后一步通過Join操作完成,即將臨時(shí)表的每一個(gè)鄰居指針(即鄰居ID)和鄰居節(jié)點(diǎn)關(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 圖計(jì)算編程和優(yōu)化

2.1 BSP實(shí)現(xiàn)簡(jiǎn)述

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

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

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

2.2 PageRank算法實(shí)現(xiàn)

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

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

2.3 PageRank算法優(yōu)化

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

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

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

PageRank的計(jì)算可以用迭代公式

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

4 結(jié)論

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

［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

蔣奎,男,高級(jí)講師,研究方向?yàn)殍F道車輛及鐵道信息系統(tǒng).E-mail:mwong56@gmail.com.

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