陽(yáng) 杰, 王木涵, 徐九韻
(中國(guó)石油大學(xué)(華東)計(jì)算機(jī)與通信工程學(xué)院,青島 266580)
基于Spark和Redis的大規(guī)模RDF數(shù)據(jù)查詢(xún)系統(tǒng)①
陽(yáng) 杰, 王木涵, 徐九韻
(中國(guó)石油大學(xué)(華東)計(jì)算機(jī)與通信工程學(xué)院,青島 266580)
隨著語(yǔ)義Web技術(shù)的不斷發(fā)展,RDF數(shù)據(jù)量增長(zhǎng)迅速,單機(jī)RDF查詢(xún)系統(tǒng)已經(jīng)難以滿(mǎn)足現(xiàn)實(shí)需要,研究和構(gòu)建分布式RDF查詢(xún)系統(tǒng)已經(jīng)成為學(xué)術(shù)界與工業(yè)界的研究熱點(diǎn)之一.現(xiàn)有的RDF查詢(xún)系統(tǒng)主要是基于Hadoop或通用分布式技術(shù).前者磁盤(pán)I/O太高;后者則可擴(kuò)展性較差.且兩種系統(tǒng)在基本圖模式查詢(xún)時(shí),效率都較低.針對(duì)上述問(wèn)題,本文設(shè)計(jì)了基于Spark和Redis的分布式系統(tǒng)架構(gòu),并改進(jìn)了查詢(xún)計(jì)劃生成算法,最后實(shí)現(xiàn)了原型系統(tǒng)RDF-SR.該系統(tǒng)使用Spark減少了磁盤(pán)I/O,借助Redis提高了數(shù)據(jù)映射速率,利用改進(jìn)的算法減少了數(shù)據(jù)混洗次數(shù).實(shí)驗(yàn)表明,相比于現(xiàn)有的其他系統(tǒng),RDF-SR既保持了較高可擴(kuò)展性,又在基本圖模式查詢(xún)時(shí),具有更高的性能.
語(yǔ)義Web;大規(guī)模RDF;Spark;Redis
隨著語(yǔ)義Web的不斷發(fā)展,基于語(yǔ)義網(wǎng)的應(yīng)用也越來(lái)越多.RDF(資源描述框架)已被廣泛地應(yīng)用于各個(gè)領(lǐng)域的本體建模和推理中,例如電子政務(wù)、生物醫(yī)藥、地理空間等領(lǐng)域.以鏈接開(kāi)放數(shù)據(jù)(Linked Open Data)項(xiàng)后為例,該項(xiàng)后一共包含了約520億個(gè)三元組,這是典型的大規(guī)模RDF數(shù)據(jù)[1].傳統(tǒng)單機(jī)RDF數(shù)據(jù)查詢(xún)系統(tǒng)在數(shù)據(jù)集較小的情況下,能夠呈現(xiàn)出優(yōu)異的性能,但是隨著RDF數(shù)據(jù)規(guī)模的增加,其擴(kuò)展能力和查詢(xún)性能都會(huì)出現(xiàn)瓶頸,海量RDF數(shù)據(jù)的存儲(chǔ)和查詢(xún)面臨著巨大挑戰(zhàn)[2].因此,研究和構(gòu)建分布式的RDF數(shù)據(jù)查詢(xún)系統(tǒng),實(shí)現(xiàn)數(shù)據(jù)的快速查詢(xún)具有十分重要的意義.
現(xiàn)有的分布式RDF查詢(xún)系統(tǒng)可以分為兩類(lèi):基于通用分布式技術(shù)的RDF查詢(xún)系統(tǒng)和基于Hadoop的RDF查詢(xún)系統(tǒng).基于通用分布式技術(shù)的系統(tǒng)有RDFPeers[3]、YARS2[4]等.RDFPeers建立在P2P系統(tǒng)MAAN(Multi Attribute Addressable Network)上,它把RDF數(shù)據(jù)的三個(gè)副本存儲(chǔ)在不同節(jié)點(diǎn)上,并建立了索.該系統(tǒng)在三元組匹配時(shí)能取得較好的性能,但在基本圖模式查詢(xún)時(shí)查詢(xún)代價(jià)過(guò)高.YARS2在每個(gè)節(jié)點(diǎn)上用關(guān)系數(shù)據(jù)庫(kù)存儲(chǔ)RDF數(shù)據(jù),該系統(tǒng)在三元組匹配時(shí)性能較高,但是在基本圖模式下性能較低,并且較難擴(kuò)展.基于Hadoop的系統(tǒng)主要有文獻(xiàn)[5]、PigSPARQL[6]、文獻(xiàn)[2]、Sempala[7]、HadoopRDF[8]等.文獻(xiàn)[5]基于 Hadoop 和RDF-3X實(shí)現(xiàn),其中RDF-3X是一種單機(jī)RDF數(shù)據(jù)庫(kù).該文獻(xiàn)還給出了一種圖分區(qū)算法,將數(shù)據(jù)分散存儲(chǔ)到每個(gè)節(jié)點(diǎn)的RDF-3X數(shù)據(jù)庫(kù)中,并使聯(lián)系緊密的三元組存儲(chǔ)在同一節(jié)點(diǎn)上,從而減少基本圖模式查詢(xún)時(shí)的網(wǎng)絡(luò)I/O.由于該系統(tǒng)依賴(lài)于單機(jī)RDF數(shù)據(jù)庫(kù),所以降低了存儲(chǔ)系統(tǒng)的可擴(kuò)展性.PigSPARQL采用平面文件組織RDF數(shù)據(jù),它將Sparql語(yǔ)句轉(zhuǎn)換成Pig Latin實(shí)現(xiàn)并行查詢(xún),Pig Latin會(huì)被解析成一系列的MapReduce作業(yè)來(lái)執(zhí)行.文獻(xiàn)[2]采用了Hadoop和HBase構(gòu)建RDF查詢(xún)系統(tǒng),它利用HBase自身的索機(jī)制提升三元組匹配速率,并使用貪心算法生成查詢(xún)計(jì)劃.該系統(tǒng)在處理三元組匹配和簡(jiǎn)單圖匹配時(shí)都表現(xiàn)出了不錯(cuò)的性能,系統(tǒng)的可擴(kuò)展性也很好.但是在較為復(fù)雜的基本圖模式查詢(xún)時(shí),性能較低.主要原因是Hadoop在迭代執(zhí)行任務(wù)時(shí),需要多次耗時(shí)的讀盤(pán)和寫(xiě)盤(pán)操作,嚴(yán)重影響了系統(tǒng)的查詢(xún)性能.除此之外,該系統(tǒng)使用了貪心算法生成樹(shù)狀查詢(xún)計(jì)劃,該算法每次迭代選擇連接結(jié)果集最多的變量進(jìn)行連接,后的在于利用多路連接方法,減少連接操作次數(shù)[2].該算法并有沒(méi)有考慮查詢(xún)中間結(jié)果集的規(guī)模信息,然而如果合理利用這些信息,調(diào)整連接的順序,可以進(jìn)一步提升查詢(xún)的效率.
基于此,本文設(shè)計(jì)了一種基于Spark和Redis的分布式架構(gòu).Spark是由加州大學(xué)伯克利分校的AMP實(shí)驗(yàn)室所開(kāi)源的基于內(nèi)存的通用并行框架[9].它將作業(yè)中間輸出的結(jié)果保留在內(nèi)存中,不需要讀寫(xiě)磁盤(pán).因此,Spark可以有效減少迭代型作業(yè)的磁盤(pán)I/O.Redis是一個(gè)既可基于內(nèi)存亦可持久化的鍵值型分布式數(shù)據(jù)庫(kù)[10].它既保證了高效存取,又保證了數(shù)據(jù)的完整性.同時(shí),Redis非常容易擴(kuò)展.所以Redis可以顯著提升并行讀取數(shù)據(jù)映射表的速率.本文還改進(jìn)了查詢(xún)計(jì)劃生成算法,該算法基于數(shù)據(jù)連接中間結(jié)果集的規(guī)模信息調(diào)整了結(jié)果集連接順序,并利用分布式平臺(tái)廣播數(shù)據(jù)的特性[11]減少了數(shù)據(jù)混洗操作次數(shù),進(jìn)而提升查詢(xún)速率.
本文的貢獻(xiàn)點(diǎn)主要有如下兩點(diǎn):
(1)設(shè)計(jì)出一種基于Spark和Redis的分布式架構(gòu),并給出了原型系統(tǒng)RDF-SR.
(2)利用查詢(xún)中間結(jié)果集的規(guī)模信息,改進(jìn)了查詢(xún)計(jì)劃生成算法.
本文安排如下:第一部分是言,說(shuō)明了本文的研究后的及意義、主要貢獻(xiàn)點(diǎn)及組織結(jié)構(gòu).第二部分是RDF查詢(xún)基本算法,介紹了RDF數(shù)據(jù)形式以及查詢(xún)的基本算法.第三部分是RDF-SR系統(tǒng)設(shè)計(jì),介紹了RDF-SR系統(tǒng)的特點(diǎn)和架構(gòu).第四部分是查詢(xún)計(jì)劃生成算法,描述了本文改進(jìn)查詢(xún)計(jì)劃生成算法的原理和步驟.第五部分是實(shí)驗(yàn)結(jié)果與分析,主要測(cè)試了RDF-SR系統(tǒng)在基本圖模式下的查詢(xún)性能,并與基于Hadoop的系統(tǒng)作了對(duì)比.第六部分是小結(jié),總結(jié)本文的工作內(nèi)容和成果,指出了今后進(jìn)一步進(jìn)行研究的展望和設(shè)想.
RDF是以三元組(主語(yǔ),謂詞,賓語(yǔ))的形式描述資源的.一組三元組的集合被成為RDF圖,RDF圖可以通過(guò)結(jié)點(diǎn)和弧線表示,弧的兩端是主語(yǔ)和賓語(yǔ),弧的方向總是由主語(yǔ)指向賓語(yǔ).RDF數(shù)據(jù)的基本圖模式查詢(xún)條件是一個(gè)帶變量的子圖,因此RDF上的查詢(xún)處理可以被轉(zhuǎn)換為大圖上的子圖匹配問(wèn)題[12].圖1是RDF圖的實(shí)例,圖2是查詢(xún)子圖的實(shí)例.
子圖匹配RDF大圖的基本算法可以分為如下幾個(gè)步驟(假設(shè)子圖有k個(gè)模式):
(1)將k個(gè)模式分別與大圖匹配,得到k個(gè)匹配結(jié)果集(每個(gè)結(jié)果集只保留變量對(duì)應(yīng)的列).
(2)將k個(gè)結(jié)果集放入集合S,如果集合還存在兩個(gè)結(jié)果集可以連接,則重復(fù)執(zhí)行步驟3.
(3)找出具有公共變量的兩個(gè)結(jié)果集,把它們從S中刪除,并將它們基于公共變量進(jìn)行連接操作,將連接產(chǎn)生的結(jié)果集加入S.
本系統(tǒng)的主要特點(diǎn)包含了以下三個(gè)方面:
(1)系統(tǒng)能夠支持Sparql查詢(xún)中的三元組模式查詢(xún)和基本圖模式查詢(xún).
(2)系統(tǒng)使用Redis存儲(chǔ)RDF大圖數(shù)據(jù)的ID映射表,以及大圖數(shù)據(jù)的統(tǒng)計(jì)信息.
(3)系統(tǒng)使用Spark集群作為計(jì)算擎.
圖1 RDF圖
圖2 基本圖模式查詢(xún)條件
RDF-SR使用Sparql作為用戶(hù)操作接口,Sparql是為RDF開(kāi)發(fā)的一種查詢(xún)語(yǔ)言和數(shù)據(jù)獲取協(xié)議,用戶(hù)可以使用這種類(lèi)似SQL的查詢(xún)語(yǔ)言進(jìn)行RDF數(shù)據(jù)的查詢(xún)操作[13].整個(gè)系統(tǒng)可以分為兩個(gè)部分,數(shù)據(jù)預(yù)處理子系統(tǒng)和數(shù)據(jù)查詢(xún)子系統(tǒng).
數(shù)據(jù)預(yù)處理子系統(tǒng)又可以分為兩個(gè)部分:第一部分的功能是生成ID映射表,并把ID映射表寫(xiě)入Redis;第二部分的功能是把三元組映射為ID形式,并統(tǒng)計(jì)出元素在不同列出現(xiàn)的次數(shù),最后把統(tǒng)計(jì)信息寫(xiě)入到Redis.具體流程如圖3所示.
數(shù)據(jù)查詢(xún)子系統(tǒng)主要功能是:從用戶(hù)那里接受Sparql語(yǔ)句,然后用Jena ARQ[14]解析出基本圖模式的三元組;把三元組內(nèi)的文本映射為ID,然后讀取大圖統(tǒng)計(jì)信息,最后用改進(jìn)的算法生成查詢(xún)計(jì)劃;把任務(wù)提交到Spark集群上運(yùn)行,然后選出用戶(hù)關(guān)心的列,并把ID映射為文本,返回給用戶(hù).具體如圖4所示.
查詢(xún)計(jì)劃生成算法改進(jìn)的主要原理是通過(guò)近似計(jì)算結(jié)果集的大小,優(yōu)先選取數(shù)據(jù)量小的結(jié)果集當(dāng)作連接的左表,從而利用分布式平臺(tái)廣播數(shù)據(jù)的特性[11],避免數(shù)據(jù)混洗操作,提高連接的速度,進(jìn)而提高查詢(xún)的整體速度.采用近似計(jì)算而不采用實(shí)時(shí)計(jì)算的原因是,在分布式環(huán)境中,在計(jì)算階段實(shí)時(shí)獲取結(jié)果集的大小,網(wǎng)絡(luò)I/O開(kāi)銷(xiāo)較大,反而會(huì)降低查詢(xún)速度.
近似計(jì)算連接結(jié)果集的大小,是數(shù)據(jù)庫(kù)領(lǐng)域的一個(gè)重要問(wèn)題,已有較為豐富的研究成果.利用選擇率來(lái)預(yù)估連接結(jié)果集的大小程度,是一種較為有效的途徑[17].為了充分利用在RDF數(shù)據(jù)預(yù)處理階段得到的統(tǒng)計(jì)信息,本文定義了一種選擇率計(jì)算方法.假設(shè)RDF圖G中有N個(gè)三元組.列號(hào),其中0是主語(yǔ)列,1是謂語(yǔ)列,2是賓語(yǔ)列.ek是位于位置k的元素,模式TP也就可以表示為(e0,e1,e2).元素選擇率的計(jì)算公式為
其中count(ek)是指元素ek在圖G中出現(xiàn)的次數(shù).模式TP選擇率的計(jì)算公式為:
連接結(jié)果集大小上界的計(jì)算公式為:
其中match(TP)是指模式TP匹配圖G后的結(jié)果集大小.連接結(jié)果選擇率的計(jì)算公式為:
圖4 數(shù)據(jù)查詢(xún)子系統(tǒng)
該算法可以分成如下幾個(gè)步驟(假設(shè)有k個(gè)模式):
(1)預(yù)處理大圖數(shù)據(jù),分別遍歷大圖的主語(yǔ)列、謂詞列、賓語(yǔ)列的所有元素,統(tǒng)計(jì)不同元素在不同列出現(xiàn)的次數(shù).
(2)將每個(gè)模式與大圖匹配得到k個(gè)結(jié)果集.
(3)從步驟1統(tǒng)計(jì)的數(shù)據(jù)中,得到每個(gè)結(jié)果集的大小,把所有結(jié)果集加入集合S,一直循環(huán)執(zhí)行步驟4,直到集合S中不存在任何兩個(gè)結(jié)果集擁有公共變量.
(4)選出最小的兩個(gè)可連接的結(jié)果集,從S中刪除,同時(shí)小表在左大表在右進(jìn)行連接,連接后產(chǎn)生結(jié)果集A,近似計(jì)算A的大小,并加入S.
本文使用一個(gè)的簡(jiǎn)單例子說(shuō)明該算法的有效性.假設(shè)例子中的3個(gè)模式匹配大圖數(shù)據(jù)后得到3個(gè)結(jié)果集,如表1所示.
表1 匹配結(jié)果集
對(duì)于這3個(gè)結(jié)果集,使用貪心算法和本文提出的算法分別生成查詢(xún)計(jì)劃并進(jìn)行連接操作,具體如圖5所示.
圖5 兩種方法生成的查詢(xún)計(jì)劃
圖5中,左圖是使用貪心算法生成的查詢(xún)計(jì)劃,使用了多路連接,右圖是使用本文的算法生成的查詢(xún)計(jì)劃,圖中的數(shù)字代表結(jié)果集的大小.分析上面的例子可以發(fā)現(xiàn):使用貪心算法生成的查詢(xún)計(jì)劃,雖然只需要一次多路連接就能得到最終結(jié)果,但是卻由于較大結(jié)果集C的影響,觸發(fā)了數(shù)據(jù)混洗操作,產(chǎn)生大量網(wǎng)絡(luò)I/O,導(dǎo)致查詢(xún)效率較低;使用本文提出的算法生成的查詢(xún)計(jì)劃,雖然有兩次連接,但是可以將較小結(jié)果集當(dāng)作左表,利用分布式平臺(tái)廣播數(shù)據(jù)的特性,避免了數(shù)據(jù)混洗操作,反而使得整體查詢(xún)效率提高.
本文基于青云大數(shù)據(jù)平臺(tái)[15]搭建了具有5個(gè)節(jié)點(diǎn)的Spark集群和一個(gè)Redis節(jié)點(diǎn),節(jié)點(diǎn)配置情況如表2所示.
表2 節(jié)點(diǎn)配置情況
為了測(cè)試系統(tǒng)的性能,需要做一些基準(zhǔn)測(cè)試.本文采用當(dāng)前廣泛使用的基準(zhǔn)測(cè)試集LUBM(Lehigh University Benchmark,LUBM)[16].本文采用LUBM生成器,生成了三組大學(xué)的語(yǔ)義數(shù)據(jù)集,數(shù)據(jù)集規(guī)模如表3所示.
表3 數(shù)據(jù)集規(guī)模
為了測(cè)試系統(tǒng)在基本圖模式下的查詢(xún)性能,本文選用了Q1,Q2,Q3這三條Sparql語(yǔ)句進(jìn)行了測(cè)試,并與基于Hadoop的系統(tǒng)(文獻(xiàn)[2])做了對(duì)比.Q1,、Q2、Q3的細(xì)節(jié)如表4所示.
表4 Sparql語(yǔ)句細(xì)節(jié)
圖6和圖7展示了實(shí)驗(yàn)的結(jié)果.從圖6得出的結(jié)論是RDF-SR在3個(gè)基本圖模式查詢(xún)時(shí)的性能,比基于Hadoop的系統(tǒng)快3-6倍.從圖7中可以看出,隨著數(shù)據(jù)規(guī)模的增加,RDF-SR查詢(xún)時(shí)間的增長(zhǎng)速度比基于Hadoop的系統(tǒng)更加緩慢.這些主要得益于本系統(tǒng)的3個(gè)特點(diǎn):使用了基于內(nèi)存的分布式計(jì)算擎Spark進(jìn)行運(yùn)算,顯著減少了磁盤(pán)I/O;使用了基于內(nèi)存的數(shù)據(jù)庫(kù)Redis,提升了讀取ID映射表和大圖數(shù)據(jù)統(tǒng)計(jì)信息的速率;使用了改進(jìn)了的查詢(xún)計(jì)劃生成算法,避免了大量數(shù)據(jù)混洗操作.
圖6 三組數(shù)據(jù)集上的查詢(xún)時(shí)間對(duì)比
圖7 不同規(guī)模數(shù)據(jù)集下,查詢(xún)時(shí)間的走勢(shì)
本文的主要工作是針對(duì)現(xiàn)有分布式系統(tǒng)在基本圖模式下查詢(xún)大規(guī)模RDF效率較低的問(wèn)題,設(shè)計(jì)了一種基于Spark和Redis的分布式系統(tǒng)架構(gòu);利用查詢(xún)中間結(jié)果集的規(guī)模信息,改進(jìn)了查詢(xún)計(jì)劃生成算法;實(shí)現(xiàn)了原型系統(tǒng)RDF-SR.實(shí)驗(yàn)證明RDF-SR相比于基于Hadoop的RDF查詢(xún)系統(tǒng),在基本圖模式下的查詢(xún)效率顯著提高.
本文的不足之處在于,RDF-SR并沒(méi)有使用索結(jié)構(gòu)來(lái)提升三元組匹配的速率,同時(shí)也沒(méi)有考慮RDF數(shù)據(jù)動(dòng)態(tài)變化的場(chǎng)景.所以未來(lái)的工作在于加入索機(jī)制進(jìn)一步提升查詢(xún)效率,并考慮在RDF數(shù)據(jù)動(dòng)態(tài)變化的場(chǎng)景下,如何保證數(shù)據(jù)的查詢(xún)效率.
1 http://lod-cloud.net/versions/2011-09-19/lod-cloud.html.
2 宋紀(jì)成.海量RDF數(shù)據(jù)存儲(chǔ)與查詢(xún)技術(shù)的研究與實(shí)現(xiàn)[碩士學(xué)位論文].北京:北京工業(yè)大學(xué),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 杜方,陳躍國(guó),杜小勇.RDF數(shù)據(jù)查詢(xún)處理技術(shù)綜述.軟件學(xué)報(bào),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
陽(yáng)杰,王木涵,徐九韻.基于Spark和Redis的大規(guī)模RDF數(shù)據(jù)查詢(xún)系統(tǒng).計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(9):69–74.http://www.c-sa.org.cn/1003-3254/5923.html
2016-12-13;采用時(shí)間:2017-01-09