基于Spark和Redis的大規(guī)模RDF數(shù)據(jù)查詢系統(tǒng)①

陽 杰, 王木涵, 徐九韻

(中國石油大學(華東)計算機與通信工程學院,青島 266580)

基于Spark和Redis的大規(guī)模RDF數(shù)據(jù)查詢系統(tǒng)①

陽 杰, 王木涵, 徐九韻

(中國石油大學(華東)計算機與通信工程學院,青島 266580)

隨著語義Web技術(shù)的不斷發(fā)展,RDF數(shù)據(jù)量增長迅速,單機RDF查詢系統(tǒng)已經(jīng)難以滿足現(xiàn)實需要,研究和構(gòu)建分布式RDF查詢系統(tǒng)已經(jīng)成為學術(shù)界與工業(yè)界的研究熱點之一.現(xiàn)有的RDF查詢系統(tǒng)主要是基于Hadoop或通用分布式技術(shù).前者磁盤I/O太高;后者則可擴展性較差.且兩種系統(tǒng)在基本圖模式查詢時,效率都較低.針對上述問題,本文設(shè)計了基于Spark和Redis的分布式系統(tǒng)架構(gòu),并改進了查詢計劃生成算法,最后實現(xiàn)了原型系統(tǒng)RDF-SR.該系統(tǒng)使用Spark減少了磁盤I/O,借助Redis提高了數(shù)據(jù)映射速率,利用改進的算法減少了數(shù)據(jù)混洗次數(shù).實驗表明,相比于現(xiàn)有的其他系統(tǒng),RDF-SR既保持了較高可擴展性,又在基本圖模式查詢時,具有更高的性能.

語義Web;大規(guī)模RDF;Spark;Redis

隨著語義Web的不斷發(fā)展,基于語義網(wǎng)的應(yīng)用也越來越多.RDF(資源描述框架)已被廣泛地應(yīng)用于各個領(lǐng)域的本體建模和推理中,例如電子政務(wù)、生物醫(yī)藥、地理空間等領(lǐng)域.以鏈接開放數(shù)據(jù)(Linked Open Data)項后為例,該項后一共包含了約520億個三元組,這是典型的大規(guī)模RDF數(shù)據(jù)[1].傳統(tǒng)單機RDF數(shù)據(jù)查詢系統(tǒng)在數(shù)據(jù)集較小的情況下,能夠呈現(xiàn)出優(yōu)異的性能,但是隨著RDF數(shù)據(jù)規(guī)模的增加,其擴展能力和查詢性能都會出現(xiàn)瓶頸,海量RDF數(shù)據(jù)的存儲和查詢面臨著巨大挑戰(zhàn)[2].因此,研究和構(gòu)建分布式的RDF數(shù)據(jù)查詢系統(tǒng),實現(xiàn)數(shù)據(jù)的快速查詢具有十分重要的意義.

現(xiàn)有的分布式RDF查詢系統(tǒng)可以分為兩類:基于通用分布式技術(shù)的RDF查詢系統(tǒng)和基于Hadoop的RDF查詢系統(tǒng).基于通用分布式技術(shù)的系統(tǒng)有RDFPeers[3]、YARS2[4]等.RDFPeers建立在P2P系統(tǒng)MAAN(Multi Attribute Addressable Network)上,它把RDF數(shù)據(jù)的三個副本存儲在不同節(jié)點上,并建立了索.該系統(tǒng)在三元組匹配時能取得較好的性能,但在基本圖模式查詢時查詢代價過高.YARS2在每個節(jié)點上用關(guān)系數(shù)據(jù)庫存儲RDF數(shù)據(jù),該系統(tǒng)在三元組匹配時性能較高,但是在基本圖模式下性能較低,并且較難擴展.基于Hadoop的系統(tǒng)主要有文獻[5]、PigSPARQL[6]、文獻[2]、Sempala[7]、HadoopRDF[8]等.文獻[5]基于 Hadoop 和RDF-3X實現(xiàn),其中RDF-3X是一種單機RDF數(shù)據(jù)庫.該文獻還給出了一種圖分區(qū)算法,將數(shù)據(jù)分散存儲到每個節(jié)點的RDF-3X數(shù)據(jù)庫中,并使聯(lián)系緊密的三元組存儲在同一節(jié)點上,從而減少基本圖模式查詢時的網(wǎng)絡(luò)I/O.由于該系統(tǒng)依賴于單機RDF數(shù)據(jù)庫,所以降低了存儲系統(tǒng)的可擴展性.PigSPARQL采用平面文件組織RDF數(shù)據(jù),它將Sparql語句轉(zhuǎn)換成Pig Latin實現(xiàn)并行查詢,Pig Latin會被解析成一系列的MapReduce作業(yè)來執(zhí)行.文獻[2]采用了Hadoop和HBase構(gòu)建RDF查詢系統(tǒng),它利用HBase自身的索機制提升三元組匹配速率,并使用貪心算法生成查詢計劃.該系統(tǒng)在處理三元組匹配和簡單圖匹配時都表現(xiàn)出了不錯的性能,系統(tǒng)的可擴展性也很好.但是在較為復(fù)雜的基本圖模式查詢時,性能較低.主要原因是Hadoop在迭代執(zhí)行任務(wù)時,需要多次耗時的讀盤和寫盤操作,嚴重影響了系統(tǒng)的查詢性能.除此之外,該系統(tǒng)使用了貪心算法生成樹狀查詢計劃,該算法每次迭代選擇連接結(jié)果集最多的變量進行連接,后的在于利用多路連接方法,減少連接操作次數(shù)[2].該算法并有沒有考慮查詢中間結(jié)果集的規(guī)模信息,然而如果合理利用這些信息,調(diào)整連接的順序,可以進一步提升查詢的效率.

基于此,本文設(shè)計了一種基于Spark和Redis的分布式架構(gòu).Spark是由加州大學伯克利分校的AMP實驗室所開源的基于內(nèi)存的通用并行框架[9].它將作業(yè)中間輸出的結(jié)果保留在內(nèi)存中,不需要讀寫磁盤.因此,Spark可以有效減少迭代型作業(yè)的磁盤I/O.Redis是一個既可基于內(nèi)存亦可持久化的鍵值型分布式數(shù)據(jù)庫[10].它既保證了高效存取,又保證了數(shù)據(jù)的完整性.同時,Redis非常容易擴展.所以Redis可以顯著提升并行讀取數(shù)據(jù)映射表的速率.本文還改進了查詢計劃生成算法,該算法基于數(shù)據(jù)連接中間結(jié)果集的規(guī)模信息調(diào)整了結(jié)果集連接順序,并利用分布式平臺廣播數(shù)據(jù)的特性[11]減少了數(shù)據(jù)混洗操作次數(shù),進而提升查詢速率.

本文的貢獻點主要有如下兩點:

(1)設(shè)計出一種基于Spark和Redis的分布式架構(gòu),并給出了原型系統(tǒng)RDF-SR.

(2)利用查詢中間結(jié)果集的規(guī)模信息,改進了查詢計劃生成算法.

本文安排如下:第一部分是言,說明了本文的研究后的及意義、主要貢獻點及組織結(jié)構(gòu).第二部分是RDF查詢基本算法,介紹了RDF數(shù)據(jù)形式以及查詢的基本算法.第三部分是RDF-SR系統(tǒng)設(shè)計,介紹了RDF-SR系統(tǒng)的特點和架構(gòu).第四部分是查詢計劃生成算法,描述了本文改進查詢計劃生成算法的原理和步驟.第五部分是實驗結(jié)果與分析,主要測試了RDF-SR系統(tǒng)在基本圖模式下的查詢性能,并與基于Hadoop的系統(tǒng)作了對比.第六部分是小結(jié),總結(jié)本文的工作內(nèi)容和成果,指出了今后進一步進行研究的展望和設(shè)想.

1 RDF查詢基本算法

RDF是以三元組(主語,謂詞,賓語)的形式描述資源的.一組三元組的集合被成為RDF圖,RDF圖可以通過結(jié)點和弧線表示,弧的兩端是主語和賓語,弧的方向總是由主語指向賓語.RDF數(shù)據(jù)的基本圖模式查詢條件是一個帶變量的子圖,因此RDF上的查詢處理可以被轉(zhuǎn)換為大圖上的子圖匹配問題[12].圖1是RDF圖的實例,圖2是查詢子圖的實例.

子圖匹配RDF大圖的基本算法可以分為如下幾個步驟(假設(shè)子圖有k個模式):

(1)將k個模式分別與大圖匹配,得到k個匹配結(jié)果集(每個結(jié)果集只保留變量對應(yīng)的列).

(2)將k個結(jié)果集放入集合S,如果集合還存在兩個結(jié)果集可以連接,則重復(fù)執(zhí)行步驟3.

(3)找出具有公共變量的兩個結(jié)果集,把它們從S中刪除,并將它們基于公共變量進行連接操作,將連接產(chǎn)生的結(jié)果集加入S.

2 RDF-SR系統(tǒng)設(shè)計

本系統(tǒng)的主要特點包含了以下三個方面:

(1)系統(tǒng)能夠支持Sparql查詢中的三元組模式查詢和基本圖模式查詢.

(2)系統(tǒng)使用Redis存儲RDF大圖數(shù)據(jù)的ID映射表,以及大圖數(shù)據(jù)的統(tǒng)計信息.

(3)系統(tǒng)使用Spark集群作為計算擎.

圖1 RDF圖

圖2 基本圖模式查詢條件

RDF-SR使用Sparql作為用戶操作接口,Sparql是為RDF開發(fā)的一種查詢語言和數(shù)據(jù)獲取協(xié)議,用戶可以使用這種類似SQL的查詢語言進行RDF數(shù)據(jù)的查詢操作[13].整個系統(tǒng)可以分為兩個部分,數(shù)據(jù)預(yù)處理子系統(tǒng)和數(shù)據(jù)查詢子系統(tǒng).

數(shù)據(jù)預(yù)處理子系統(tǒng)又可以分為兩個部分:第一部分的功能是生成ID映射表,并把ID映射表寫入Redis;第二部分的功能是把三元組映射為ID形式,并統(tǒng)計出元素在不同列出現(xiàn)的次數(shù),最后把統(tǒng)計信息寫入到Redis.具體流程如圖3所示.

數(shù)據(jù)查詢子系統(tǒng)主要功能是:從用戶那里接受Sparql語句,然后用Jena ARQ[14]解析出基本圖模式的三元組;把三元組內(nèi)的文本映射為ID,然后讀取大圖統(tǒng)計信息,最后用改進的算法生成查詢計劃;把任務(wù)提交到Spark集群上運行,然后選出用戶關(guān)心的列,并把ID映射為文本,返回給用戶.具體如圖4所示.

3 查詢計劃生成算法

查詢計劃生成算法改進的主要原理是通過近似計算結(jié)果集的大小,優(yōu)先選取數(shù)據(jù)量小的結(jié)果集當作連接的左表,從而利用分布式平臺廣播數(shù)據(jù)的特性[11],避免數(shù)據(jù)混洗操作,提高連接的速度,進而提高查詢的整體速度.采用近似計算而不采用實時計算的原因是,在分布式環(huán)境中,在計算階段實時獲取結(jié)果集的大小,網(wǎng)絡(luò)I/O開銷較大,反而會降低查詢速度.

近似計算連接結(jié)果集的大小,是數(shù)據(jù)庫領(lǐng)域的一個重要問題,已有較為豐富的研究成果.利用選擇率來預(yù)估連接結(jié)果集的大小程度,是一種較為有效的途徑[17].為了充分利用在RDF數(shù)據(jù)預(yù)處理階段得到的統(tǒng)計信息,本文定義了一種選擇率計算方法.假設(shè)RDF圖G中有N個三元組.列號,其中0是主語列,1是謂語列,2是賓語列.ek是位于位置k的元素,模式TP也就可以表示為(e0,e1,e2).元素選擇率的計算公式為

其中count(ek)是指元素ek在圖G中出現(xiàn)的次數(shù).模式TP選擇率的計算公式為:

連接結(jié)果集大小上界的計算公式為:

其中match(TP)是指模式TP匹配圖G后的結(jié)果集大小.連接結(jié)果選擇率的計算公式為:

圖4 數(shù)據(jù)查詢子系統(tǒng)

該算法可以分成如下幾個步驟(假設(shè)有k個模式):

(1)預(yù)處理大圖數(shù)據(jù),分別遍歷大圖的主語列、謂詞列、賓語列的所有元素,統(tǒng)計不同元素在不同列出現(xiàn)的次數(shù).

(2)將每個模式與大圖匹配得到k個結(jié)果集.

(3)從步驟1統(tǒng)計的數(shù)據(jù)中,得到每個結(jié)果集的大小,把所有結(jié)果集加入集合S,一直循環(huán)執(zhí)行步驟4,直到集合S中不存在任何兩個結(jié)果集擁有公共變量.

(4)選出最小的兩個可連接的結(jié)果集,從S中刪除,同時小表在左大表在右進行連接,連接后產(chǎn)生結(jié)果集A,近似計算A的大小,并加入S.

本文使用一個的簡單例子說明該算法的有效性.假設(shè)例子中的3個模式匹配大圖數(shù)據(jù)后得到3個結(jié)果集,如表1所示.

表1 匹配結(jié)果集

對于這3個結(jié)果集,使用貪心算法和本文提出的算法分別生成查詢計劃并進行連接操作,具體如圖5所示.

圖5 兩種方法生成的查詢計劃

圖5中,左圖是使用貪心算法生成的查詢計劃,使用了多路連接,右圖是使用本文的算法生成的查詢計劃,圖中的數(shù)字代表結(jié)果集的大小.分析上面的例子可以發(fā)現(xiàn):使用貪心算法生成的查詢計劃,雖然只需要一次多路連接就能得到最終結(jié)果,但是卻由于較大結(jié)果集C的影響,觸發(fā)了數(shù)據(jù)混洗操作,產(chǎn)生大量網(wǎng)絡(luò)I/O,導(dǎo)致查詢效率較低;使用本文提出的算法生成的查詢計劃,雖然有兩次連接,但是可以將較小結(jié)果集當作左表,利用分布式平臺廣播數(shù)據(jù)的特性,避免了數(shù)據(jù)混洗操作,反而使得整體查詢效率提高.

4 實驗結(jié)果與分析

4.1 測試環(huán)境和數(shù)據(jù)來源

本文基于青云大數(shù)據(jù)平臺[15]搭建了具有5個節(jié)點的Spark集群和一個Redis節(jié)點,節(jié)點配置情況如表2所示.

表2 節(jié)點配置情況

為了測試系統(tǒng)的性能,需要做一些基準測試.本文采用當前廣泛使用的基準測試集LUBM(Lehigh University Benchmark,LUBM)[16].本文采用LUBM生成器,生成了三組大學的語義數(shù)據(jù)集,數(shù)據(jù)集規(guī)模如表3所示.

表3 數(shù)據(jù)集規(guī)模

4.2 基本圖模式查詢性能測試

為了測試系統(tǒng)在基本圖模式下的查詢性能,本文選用了Q1,Q2,Q3這三條Sparql語句進行了測試,并與基于Hadoop的系統(tǒng)(文獻[2])做了對比.Q1,、Q2、Q3的細節(jié)如表4所示.

表4 Sparql語句細節(jié)

圖6和圖7展示了實驗的結(jié)果.從圖6得出的結(jié)論是RDF-SR在3個基本圖模式查詢時的性能,比基于Hadoop的系統(tǒng)快3-6倍.從圖7中可以看出,隨著數(shù)據(jù)規(guī)模的增加,RDF-SR查詢時間的增長速度比基于Hadoop的系統(tǒng)更加緩慢.這些主要得益于本系統(tǒng)的3個特點:使用了基于內(nèi)存的分布式計算擎Spark進行運算,顯著減少了磁盤I/O;使用了基于內(nèi)存的數(shù)據(jù)庫Redis,提升了讀取ID映射表和大圖數(shù)據(jù)統(tǒng)計信息的速率;使用了改進了的查詢計劃生成算法,避免了大量數(shù)據(jù)混洗操作.

圖6 三組數(shù)據(jù)集上的查詢時間對比

圖7 不同規(guī)模數(shù)據(jù)集下,查詢時間的走勢

5 小結(jié)

本文的主要工作是針對現(xiàn)有分布式系統(tǒng)在基本圖模式下查詢大規(guī)模RDF效率較低的問題,設(shè)計了一種基于Spark和Redis的分布式系統(tǒng)架構(gòu);利用查詢中間結(jié)果集的規(guī)模信息,改進了查詢計劃生成算法;實現(xiàn)了原型系統(tǒng)RDF-SR.實驗證明RDF-SR相比于基于Hadoop的RDF查詢系統(tǒng),在基本圖模式下的查詢效率顯著提高.

本文的不足之處在于,RDF-SR并沒有使用索結(jié)構(gòu)來提升三元組匹配的速率,同時也沒有考慮RDF數(shù)據(jù)動態(tài)變化的場景.所以未來的工作在于加入索機制進一步提升查詢效率,并考慮在RDF數(shù)據(jù)動態(tài)變化的場景下,如何保證數(shù)據(jù)的查詢效率.

1 http://lod-cloud.net/versions/2011-09-19/lod-cloud.html.

2 宋紀成.海量RDF數(shù)據(jù)存儲與查詢技術(shù)的研究與實現(xiàn)[碩士學位論文].北京:北京工業(yè)大學,2013.

3 Cai M,Frank M.RDFPeers:A scalable distributed RDF repository based on a structured peer-to-peer network.Proc.of the 13th International Conference on World Wide Web.New York,NY,USA.2004.650–657.

4 Harth A,Umbrich J,Hogan A,et al.YARS2:A federated repository for querying graph structured data from the web.The Semantic Web.Lecture Notes in Computer Science.Berlin Heidelberg.2007.211–224.

5 Huang JW,Abadi DJ,Ren K.Scalable SPARQL querying of large RDF graphs.Proc.of the VLDB Endowment,2011,4(11):1123–1134.

6 Sch?tzle A,Przyjaciel-Zablocki M,Hornung T,et al.PigSPARQL:A SPARQL query processing baseline for big data.Proc.of the 2013 International Conference on Posters &Demonstrations Track.Sydney,Australia.2013.241–244.

7 Sch?tzle A,Przyjaciel-Zablocki M,Neu A,et al.Sempala:Interactive SPARQL query processing on hadoop.The Semantic Web-ISWC 2014.Cham.2014.164–179.

8 Du JH,Wang HF,Ni Y,et al.HadoopRDF:A scalable semantic data analytical engine.Intelligent Computing Theories and Applications.Berlin Heidelberg.2012.633–641.

9 https://spark.apache.org/docs/latest/index.html.

10 Carlson JL.Redis in Action.Greenwich,CT,USA:Manning Publications,2013.

11 Apache Spark.Spark programming guide.https://spark.apache.org/docs/latest/programming-guide.html#broadcast-variables.

12 杜方,陳躍國,杜小勇.RDF數(shù)據(jù)查詢處理技術(shù)綜述.軟件學報,2013,24(6):1222–1242.

13 Prud’hommeaux E,Seaborne A.SPARQL query language for RDF.W3C Recommendation,2008:15.

14 ARQ-A SPARQL processor for jena.http://jena.apache.org/documentation/query/index.html.

15 https://www.qingcloud.com.

16 LUBMft -the RDF fulltext benchmark.http://www.l3s.de/～minack/rdf-fulltext-benchmark.

17 Stocker M,Seaborne A,Bernstein A,et al.SPARQL basic graph pattern optimization using selectivity estimation.Proc.of the 17th International Conference on World Wide Web.Beijing,China.2008.595–604.

Big RDF Graph Query System Based on Spark and Redis

YANG Jie,WANG Mu-Han,XU Jiu-Yun
(School of Computer &Communication Engineering,China University of Petroleum,Qingdao 266580,China)

With the development of semantic web technology,RDF data grow rapidly.The single node RDF query system cannot meet the practical needs.Building distributed RDF query system has become one of the hotspots in the academia and industry.The existing RDF query system is based on Hadoop and general distributed technology.The disk I/O of the former is too high and the latter is less scalable.Besides,the two systems perform poorly in the basic pattern matching mode.In order to solve these problems,we design a distributed system architecture based on Spark and Redis,and improve the query plan generation algorithm.We call the prototype system RDF-SR.This system reduces the disk I/O by Spark,improves the data mapping rate by Redis and reduces the data shuffling process with improved algorithms.Our evaluation shows that RDF-SR performs better in the basic pattern matching mode compared with other systems.

semantic Web;big RDF graph;Spark;Redis

陽杰,王木涵,徐九韻.基于Spark和Redis的大規(guī)模RDF數(shù)據(jù)查詢系統(tǒng).計算機系統(tǒng)應(yīng)用,2017,26(9):69–74.http://www.c-sa.org.cn/1003-3254/5923.html

2016-12-13;采用時間:2017-01-09