張 孝 ，孫一銘 ，吳旭峰

1.教育部數(shù)據(jù)工程與知識工程重點(diǎn)實(shí)驗(yàn)室（中國人民大學(xué)），北京 100872

2.中國人民大學(xué) 信息學(xué)院，北京 100872

1 引言

近年來，社會上的數(shù)據(jù)量以指數(shù)級的增長速度在增長。根據(jù)IDC于2018年時的報(bào)告[1]上預(yù)測，中國的總數(shù)據(jù)量預(yù)計(jì)將達(dá)到8 060 EB，占到全球數(shù)據(jù)總量的18%。大數(shù)據(jù)時代，數(shù)據(jù)規(guī)模的不斷發(fā)展給人們帶來了諸多機(jī)遇，同時在技術(shù)上帶來了更多的挑戰(zhàn)。圖數(shù)據(jù)是具有節(jié)點(diǎn)或者邊標(biāo)簽等圖結(jié)構(gòu)特點(diǎn)的數(shù)據(jù)，并且可能附加信息與圖形相關(guān)聯(lián)。其特點(diǎn)主要在于數(shù)據(jù)集規(guī)模巨大，數(shù)據(jù)本身結(jié)構(gòu)類型多變，應(yīng)用場景豐富，使得用戶會在不同場景下有著不同的查詢操作需求。如何高效、智能地管理圖數(shù)據(jù)如今正在被廣泛研究。目前主流的單數(shù)據(jù)模型引擎對于圖數(shù)據(jù)的管理都只能提供部分應(yīng)用場景上的高效查詢性能。多數(shù)據(jù)引擎協(xié)同存儲圖數(shù)據(jù)，可以在整個數(shù)據(jù)管理平臺中實(shí)現(xiàn)犧牲部分存儲成本，大大提高數(shù)據(jù)管理系統(tǒng)的查詢性能。同時提出的查詢感知的存儲優(yōu)化算法，為這種存儲模式節(jié)省出更多的存儲成本。

在眾多的不同的數(shù)據(jù)模型中，關(guān)系數(shù)據(jù)模型一直自20 世紀(jì)80 年代就處于一個強(qiáng)勢統(tǒng)治地位，出現(xiàn)了以MySQL、Oracle 等為代表的關(guān)系數(shù)據(jù)庫管理系統(tǒng)[2]。但涉及到圖數(shù)據(jù)管理存儲時，由于當(dāng)時的數(shù)據(jù)建模中的一些缺陷與問題，使得關(guān)系數(shù)據(jù)庫一度產(chǎn)生了對于高效存儲管理圖數(shù)據(jù)上的不適應(yīng)。當(dāng)時人們?yōu)榱私鉀Q圖數(shù)據(jù)存儲管理問題，基于NoSQL[3]技術(shù)開發(fā)了新的數(shù)據(jù)模型，圖數(shù)據(jù)庫從此誕生。當(dāng)前，多種并行的圖數(shù)據(jù)處理系統(tǒng)正在被不斷研究與提出用以提高圖數(shù)據(jù)的查詢與處理效率[4]。圖數(shù)據(jù)庫因其獨(dú)特的圖算法優(yōu)化，使得它在很多圖數(shù)據(jù)處理場景下?lián)碛休^好的表現(xiàn)。然而，很多圖數(shù)據(jù)引擎都因?yàn)槠洳粔虺墒?，在?shí)際應(yīng)用中有著大大小小不同的問題。

圖數(shù)據(jù)庫雖然有亮眼之處，但是缺陷無法掩蓋。因此，許多學(xué)者重新將思路放回了擁有幾十年的工程積累的關(guān)系型數(shù)據(jù)庫?；陉P(guān)系型數(shù)據(jù)庫，利用其良好的可拓展性構(gòu)建圖數(shù)據(jù)庫。相對于圖數(shù)據(jù)庫，關(guān)系數(shù)據(jù)庫系統(tǒng)在并發(fā)、鎖、安全性和查詢優(yōu)化等方面，有著工業(yè)級強(qiáng)度的支持。以PostgreSQL為例，目前已經(jīng)有通過基于關(guān)系代數(shù)的運(yùn)用來拓展PostgreSQL 數(shù)據(jù)庫系統(tǒng)在圖數(shù)據(jù)集上的表達(dá)能力[5]。盡管利用關(guān)系數(shù)據(jù)庫系統(tǒng)圖處理能力擴(kuò)展研究正在發(fā)展，但圖數(shù)據(jù)的本質(zhì)難題在關(guān)系數(shù)據(jù)庫中還是沒有得到太好的解決，即數(shù)據(jù)的高度關(guān)聯(lián)所帶來的嚴(yán)重的隨機(jī)訪問問題。傳統(tǒng)的關(guān)系型數(shù)據(jù)庫由于是靠連接實(shí)現(xiàn)關(guān)系，隨機(jī)訪問的情況會顯得更加嚴(yán)重。

針對如何在數(shù)據(jù)云服務(wù)平臺DataCloud中向用戶提供穩(wěn)定高效的圖數(shù)據(jù)查詢性能的問題，基于單個數(shù)據(jù)模型在管理圖數(shù)據(jù)時的局限，本文提出了使用關(guān)系數(shù)據(jù)模型與圖數(shù)據(jù)模型協(xié)同存儲數(shù)據(jù)的方式來管理數(shù)據(jù)，目標(biāo)在犧牲一小部分存儲成本之后，大大提高整個系統(tǒng)的查詢性能，從而達(dá)到更佳的管理效果。同時針對多數(shù)據(jù)模型管理方式下需要面對的數(shù)據(jù)冗余問題，使用查詢感知的自適應(yīng)存儲算法。通過定期分析用戶提交的查詢，解析出不同用戶的個人需求與數(shù)據(jù)集特點(diǎn)，按照不同數(shù)據(jù)引擎的查詢優(yōu)勢，完成數(shù)據(jù)的存儲刪減移動等優(yōu)化。

本文主要貢獻(xiàn)包括：（1）對關(guān)系數(shù)據(jù)模型與圖數(shù)據(jù)模型研究與實(shí)驗(yàn)測評，提出了利用兩個數(shù)據(jù)模型協(xié)同管理數(shù)據(jù)的模式；（2）通過實(shí)驗(yàn)測試對比了關(guān)系數(shù)據(jù)庫PostgreSQL 與圖數(shù)據(jù)庫Neo4J 各自在實(shí)際應(yīng)用中的查詢優(yōu)勢；（3）設(shè)計(jì)了基于用戶查詢感知的自適應(yīng)存儲優(yōu)化技術(shù)，結(jié)合用戶需求與引擎特點(diǎn)，對數(shù)據(jù)存儲位置進(jìn)行存儲調(diào)優(yōu)。

2 相關(guān)工作

本章主要介紹了相關(guān)背景與現(xiàn)有的圖數(shù)據(jù)管理方式，主要有圖數(shù)據(jù)庫存儲與關(guān)系數(shù)據(jù)庫存儲兩種。

2.1 DataCloud數(shù)據(jù)服務(wù)平臺

大數(shù)據(jù)云服務(wù)平臺DataCloud表示將不同類型的數(shù)據(jù)儲存在一個平臺中進(jìn)行統(tǒng)一管理，允許多用戶訪問，或者單用戶進(jìn)行不同需求的分析操作。它的主要特點(diǎn)如下：能夠處理、存儲不同類型的數(shù)據(jù)，包括關(guān)系數(shù)據(jù)、圖數(shù)據(jù)等；能夠適用于多種數(shù)據(jù)使用場景，比如不同需求目標(biāo)的數(shù)據(jù)分析，針對數(shù)據(jù)的智能推薦服務(wù)等；提供持續(xù)穩(wěn)定的高性能價比的數(shù)據(jù)和計(jì)算服務(wù)。如何能夠管理好復(fù)雜的圖數(shù)據(jù)也是DataCloud服務(wù)目標(biāo)之一。因此，本文針對在該平臺背景下探求更智能、更科學(xué)的存儲模式提出了對應(yīng)的存儲優(yōu)化方案。

2.2 圖數(shù)據(jù)庫技術(shù)

圖數(shù)據(jù)的處理目前也正在被廣泛研究，面向大規(guī)模在線社交網(wǎng)絡(luò)、RDF、知識圖譜、生物網(wǎng)絡(luò)提出了大量圖算法。類似于廣度優(yōu)先搜索[6]、連通分量計(jì)算、最短距離計(jì)算、拓?fù)渑判騕7]、PageRank[8]計(jì)算等算法在圖數(shù)據(jù)的處理中被大量使用。針對于此，學(xué)者們開發(fā)了大量不同類型的圖數(shù)據(jù)庫。

圖數(shù)據(jù)庫目前可以稱得上是種類繁多。其中主流的一類是以Neo4J[9]為代表的Native 圖數(shù)據(jù)庫。其主要特點(diǎn)是當(dāng)用戶查找一個節(jié)點(diǎn)的邊或者是查找邊上的端節(jié)點(diǎn)時，不需要再走一次B+樹索引，而是直接通過指針直接指向下一個的物理地址，由此保持這種查詢下的高性能。通常其關(guān)系查詢時的時間復(fù)雜度可以達(dá)到O(n)。另一類熱門的圖數(shù)據(jù)庫是以Titan/JanusGraph[10]為代表的分布式圖數(shù)據(jù)庫。JanusGraph 利用Hadoop[11]進(jìn)行圖的分析與圖的批處理，同時系統(tǒng)所支持外部的存儲系統(tǒng)包括 Apache Cassandra[12]、Apache HBase[13]、Google Cloud BigTable[14]、Apache Solr[15]與 Lucene 索引[16]、ElasticSearch[17]索引系統(tǒng)等。

為了解決圖數(shù)據(jù)高度關(guān)聯(lián)所帶來的嚴(yán)重隨機(jī)訪問問題，所開發(fā)的圖數(shù)據(jù)庫在很多場景下雖有很好的表現(xiàn)，但也暴露了不少問題。例如上面所提的Neo4J數(shù)據(jù)庫的數(shù)據(jù)屬性查詢慢、IO 性能低下等問題；JanusGaph存在查詢與存儲嚴(yán)重分離的問題等。因此，單單依靠目前的圖數(shù)據(jù)庫系統(tǒng)不能很好地達(dá)到高性能的管理圖數(shù)據(jù)的目標(biāo)。

2.3 關(guān)系數(shù)據(jù)庫的圖數(shù)據(jù)管理技術(shù)

目前在關(guān)系數(shù)據(jù)庫上圖數(shù)據(jù)管理的研究愈發(fā)熱烈。Srihari教授在研究中發(fā)現(xiàn)了一種能夠在關(guān)系數(shù)據(jù)庫系統(tǒng)中有效挖掘圖數(shù)據(jù)中密集子圖的算法[18]；文獻(xiàn)[19]利用SQL中的窗口函數(shù)，在關(guān)系數(shù)據(jù)庫系統(tǒng)中實(shí)現(xiàn)了最短路徑算法；文獻(xiàn)[20]在研究中提出了基于SQL的聲明性查詢語言SciQL，作用是為了給關(guān)系數(shù)據(jù)庫系統(tǒng)提供圖的計(jì)算能力；文獻(xiàn)[21]研究開發(fā)了圖形存儲系統(tǒng)SQLGraph，它將鄰接信息的關(guān)系存儲與頂點(diǎn)和邊的屬性存儲用JSON 形式相結(jié)合，并通過實(shí)驗(yàn)證明了該系統(tǒng)比大多的NoSQL圖形存儲性能要強(qiáng)。

除了在關(guān)系數(shù)據(jù)庫上實(shí)現(xiàn)圖操作的研究以外，部分研究者嘗試為關(guān)系數(shù)據(jù)庫添加新邏輯，由此成為新的圖數(shù)據(jù)庫。這種方式雖然形成了新的數(shù)據(jù)庫，但基本依然是憑借著關(guān)系數(shù)據(jù)庫的基礎(chǔ)。其中，這類典型之一，目前火熱的圖數(shù)據(jù)庫AgensGraph，就是在PostgreSQL 上重新添加新的一層邏輯，成為新的圖數(shù)據(jù)庫。AgensGraph作為新一代多模型數(shù)據(jù)庫，它能夠支持經(jīng)典的關(guān)系型數(shù)據(jù)模型，允許開發(fā)人員仍然能夠集成經(jīng)典的關(guān)系數(shù)據(jù)庫模型，同時也能夠支持提供圖數(shù)據(jù)分析環(huán)境。

基于關(guān)系數(shù)據(jù)庫的圖存儲管理技術(shù)開發(fā)，解決了很多之前純圖數(shù)據(jù)庫存儲圖數(shù)據(jù)時遇到的諸多問題，但由于關(guān)系數(shù)據(jù)模型本身的影響，導(dǎo)致面對復(fù)雜的圖運(yùn)算時，數(shù)據(jù)庫的能力還是表現(xiàn)不足。

2.4 多模型數(shù)據(jù)管理系統(tǒng)

目前市場上雖說有數(shù)量不少的多模型數(shù)據(jù)庫產(chǎn)品，但是實(shí)際上大多只是將產(chǎn)品炒作成了多模型數(shù)據(jù)庫，只有少部分的系統(tǒng)才是真正的多數(shù)據(jù)模型數(shù)據(jù)庫。針對圖數(shù)據(jù)管理的多模型系統(tǒng)更是少。

ArangoDB 作為原生的多模型數(shù)據(jù)庫，它將多種不同的數(shù)據(jù)存儲組合在一起存儲在了一個數(shù)據(jù)庫當(dāng)中。在這個多模型數(shù)據(jù)庫中，用戶可以將數(shù)據(jù)存儲為鍵/值對形式、圖形形式或者是文檔形式。用戶可以使用統(tǒng)一的查詢語言進(jìn)行訪問，單次查詢也允許用戶涉及多個數(shù)據(jù)模型的數(shù)據(jù)。

不同類型、不同結(jié)構(gòu)的數(shù)據(jù)采用不同數(shù)據(jù)模型進(jìn)行存儲，可以獲得更高的查詢效率，尤其在大型的數(shù)據(jù)管理平臺當(dāng)中，具有很強(qiáng)的應(yīng)用價值。ArangoDB 通過自身的實(shí)踐應(yīng)用，證明了多模型數(shù)據(jù)庫的價值，在應(yīng)用上擁有很高的訪問效率，當(dāng)然為了獲得這些收益，必須面對一定的維護(hù)代價與數(shù)據(jù)冗余問題。

3 數(shù)據(jù)引擎查詢性能差異

本章主要介紹了關(guān)系數(shù)據(jù)庫PostgreSQL 與圖數(shù)據(jù)庫在存儲數(shù)據(jù)時的具體查詢性能差異。

3.1 TPC-H查詢測試

TPC-H 是由TPC 事務(wù)處理性能委員會組織提供的一套工具包，用戶進(jìn)行OLAP 測試，主要目的是評價特定的一系列查詢的決策支持能力，關(guān)注的是數(shù)據(jù)庫平臺的查詢能力。使用TPC-H 數(shù)據(jù)集進(jìn)行引擎性能對比的實(shí)驗(yàn)測試的最大原因是一方面它成熟的測試體系與接近真實(shí)應(yīng)用的數(shù)據(jù)集環(huán)境，另一方面它測試的查詢包含多個查詢要素，包括多表連接、聚集、排序等典型查詢，進(jìn)而可以比對不同查詢的性能差別。

通過每個查詢數(shù)據(jù)庫查詢的響應(yīng)時間，進(jìn)行兩個數(shù)據(jù)模型實(shí)際應(yīng)用下的性能對比。TPC-H測試中共22個查詢，盡管每個查詢的內(nèi)容不同，但是包含查詢類型存在重復(fù)情況，鑒于測試側(cè)重于對比不同類型查詢的性能差異，因此在對22個查詢結(jié)構(gòu)進(jìn)行解析后，選取11個代表性查詢，如表1 所示。在這里需要補(bǔ)充的是，關(guān)系數(shù)據(jù)引擎與圖數(shù)據(jù)引擎查詢差異一般體現(xiàn)在復(fù)雜關(guān)系查詢與其他類型查詢上，因此實(shí)驗(yàn)查詢主要是在此基礎(chǔ)上進(jìn)行的。而表1 中查詢類型既包含著關(guān)系數(shù)據(jù)模型的查詢也包含著圖數(shù)據(jù)模型的查詢。為了保證實(shí)驗(yàn)的準(zhǔn)確性和可靠性，針對不同的測試實(shí)驗(yàn)，需要做關(guān)系和圖數(shù)據(jù)查詢語言的轉(zhuǎn)換（查詢語言的轉(zhuǎn)換在實(shí)驗(yàn)前統(tǒng)一完成），使其查詢條件是一一對應(yīng)，從而也確保了TPC-H在多數(shù)據(jù)模型下的查詢測試的通用性。具體的語言轉(zhuǎn)換以表1中的序號1為例子進(jìn)行說明：

關(guān)系數(shù)據(jù)庫查詢：

select filed，count（filed） from tname group by filed having coun（tfiled）＞count order by id

圖數(shù)據(jù)庫查詢：

START n=node（num）

MATCH（n）--＞（x）

WHERE coun（tx.filed）＞count

return x.filed，coun（tx.filed）

order by x.id

說明：id、filed為字段名稱，tname為表名，num為節(jié)點(diǎn)編號，count為常量值。

表1 實(shí)驗(yàn)選取查詢包含類型情況

以上語言轉(zhuǎn)換，目前是根據(jù)sql 語句手工模擬出對應(yīng)的圖查詢語句（下一步將做成程序自動模擬），從而執(zhí)行Neo4J查詢，完成整個實(shí)驗(yàn)過程。

實(shí)驗(yàn)服務(wù)器環(huán)境基本配置如下：Windows10 專業(yè)版，i7-3770CPU，主頻 3.4 GHz，8 GB 內(nèi)存，200 GB 硬盤。關(guān)系數(shù)據(jù)庫系統(tǒng)為PostgreSQL，圖數(shù)據(jù)庫系統(tǒng)為Neo4J。實(shí)驗(yàn)數(shù)據(jù)來源為網(wǎng)頁爬取，在PostgreSQL 中生成后，然后轉(zhuǎn)換成CSV 的形式，再導(dǎo)入到Neo4J 中。每個查詢分別在每個數(shù)據(jù)引擎中進(jìn)行20 次查詢（相同的查詢采用緩存機(jī)制），在去除最大值與最小值以排除偶然性因素后，取每一個查詢的平均值。最后的測試結(jié)果對比如圖1所示。

圖1 查詢時間對比

總體而言，PostgreSQL 查詢時間幾乎都優(yōu)于Neo4J的。這主要是因?yàn)門PC-H 依然是關(guān)系數(shù)據(jù)庫上的測試基準(zhǔn)，查詢上做了相對的優(yōu)化。但隨著查詢序號增加，表的連接數(shù)同時增加，查詢時間開始逐漸接近。達(dá)到五表連接時，查詢時間就非常貼近了，最后，甚至出現(xiàn)了Neo4J 查詢時間少于PostgreSQL 的情況。這說明了Neo4J 在關(guān)系復(fù)雜情況下的查詢優(yōu)勢。而在其他查詢類型下，關(guān)系數(shù)據(jù)引擎相比圖數(shù)據(jù)引擎依然有著不小優(yōu)勢。

3.2 Yelp數(shù)據(jù)集查詢測試

通過上一節(jié)的測試，可以得到關(guān)系數(shù)據(jù)模型與圖數(shù)據(jù)模型下不同查詢的性能差異：圖數(shù)據(jù)模型在復(fù)雜關(guān)系查詢上有著優(yōu)勢，但在其他方面表現(xiàn)不如關(guān)系數(shù)據(jù)庫。為了進(jìn)一步地明確具體查詢在兩個引擎上的表現(xiàn)，本節(jié)使用知名數(shù)據(jù)集Yelp進(jìn)行實(shí)驗(yàn)測試，從而得到每一個具體查詢在不同數(shù)據(jù)引擎下的對比。

Yelp 數(shù)據(jù)集來源于美國最大點(diǎn)評網(wǎng)站Yelp。數(shù)據(jù)集涵蓋了Yelp 內(nèi)部存儲的商戶、點(diǎn)評和用戶數(shù)據(jù)，具體包括了用戶評價、商戶信息等。數(shù)據(jù)集由于來源真實(shí)，具有很強(qiáng)的實(shí)際意義，同時內(nèi)部既存在復(fù)雜關(guān)系，也存在多樣的屬性集合。因此選取Yelp 在兩個數(shù)據(jù)引擎進(jìn)行不同基本查詢的性能對比。實(shí)驗(yàn)環(huán)境跟上一測試相同。本次實(shí)驗(yàn)相對更為具體，以SQL語句關(guān)鍵詞為標(biāo)志進(jìn)行測試，具體為：（1）Order by，排序查詢；（2）Aggregate，聚集查詢；（3）Join，四表五表連接查詢；（4）Having，聚集子句；測試的關(guān)鍵詞選用標(biāo)準(zhǔn)來自上一個實(shí)驗(yàn)總結(jié)。測試語句為基礎(chǔ)查詢語句，返回1 000條記錄，每種查詢類型都會用3 個不同的查詢語句測試，最后取加權(quán)平均值，得到這類查詢最終的平均查詢時間。

實(shí)驗(yàn)為得到直觀的數(shù)據(jù)引擎的性能比，對查詢時間進(jìn)行了相對得分處理，每一類查詢在兩個數(shù)據(jù)引擎中的總分為100，各自根據(jù)查詢平均時間的比值得到對應(yīng)的性能比，如圖2所示。由圖可知，Yelp數(shù)據(jù)集的測試下，Neo4J的優(yōu)勢查詢在于超過四層關(guān)聯(lián)關(guān)系查詢時，速度遠(yuǎn)遠(yuǎn)優(yōu)于關(guān)系數(shù)據(jù)庫，而在其他查詢需求上，性能比不上傳統(tǒng)的關(guān)系數(shù)據(jù)引擎。

圖2 不同引擎下不同查詢類型的性能對比

4 關(guān)系-圖協(xié)同存儲與優(yōu)化

基于第3 章中介紹的關(guān)系數(shù)據(jù)模型與圖數(shù)據(jù)數(shù)據(jù)模型的實(shí)際查詢性能的不同，提出兩個數(shù)據(jù)引擎協(xié)同存儲來獲得查詢的高性能，并介紹了查詢感知的自適應(yīng)存儲優(yōu)化技術(shù)的研究與實(shí)現(xiàn)。

4.1 協(xié)同存儲的查詢優(yōu)勢

本節(jié)通過實(shí)驗(yàn)舉例說明的方式，簡單證明關(guān)系-圖協(xié)同存儲下的查詢優(yōu)勢。用戶查詢可以分為簡單查詢與復(fù)合查詢。簡單查詢是查詢結(jié)構(gòu)簡單，只包含多表連接、聚集查詢等查詢中的一個或者兩個。簡單查詢情況下，由于兩個引擎可以根據(jù)自己的優(yōu)勢進(jìn)行查詢選擇，查詢效率一定會比單個引擎進(jìn)行所有查詢的效率要高。因此在證明關(guān)系-圖協(xié)同存儲下的查詢優(yōu)勢，只需要證明用戶復(fù)合查詢下多數(shù)據(jù)模型管理的性能優(yōu)勢。

復(fù)合查詢是指查詢包含圖數(shù)據(jù)引擎擅長的復(fù)雜多表查詢，同時包含關(guān)系數(shù)據(jù)庫擅長的排序聚集等查詢。對此，分別使用單個圖數(shù)據(jù)引擎、單個關(guān)系數(shù)據(jù)引擎與雙引擎進(jìn)行查詢，通過對比三種情況的查詢時間得到性能對比。實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集同上一章Yelp實(shí)驗(yàn)相同，實(shí)驗(yàn)方式具體如下，設(shè)置四組復(fù)合查詢，具體包含類型為：（1）三表連接、排序、聚集；（2）四表連接、排序；（3）五表連接、聚集；（4）五表連接、聚集、排序。實(shí)驗(yàn)通過查詢分割，將復(fù)合查詢中各自擅長的查詢分配至對應(yīng)查詢引擎，再將總的時間與中間成本進(jìn)行整合得到復(fù)合查詢總時長。

對實(shí)驗(yàn)結(jié)果進(jìn)行比例調(diào)整，將協(xié)同存儲下的查詢時間設(shè)為單位1，則其他查詢結(jié)果如圖3所示。可以看到，在使用單個圖數(shù)據(jù)引擎或者單個關(guān)系數(shù)據(jù)引擎存儲時的查詢平均時間都是關(guān)系-圖復(fù)合存儲下的查詢時間的2～5倍。使用多數(shù)據(jù)模型協(xié)同管理復(fù)雜關(guān)系數(shù)據(jù)集時，用戶的查詢性能得到了相應(yīng)的提高，驗(yàn)證了這種存儲模式在查詢上的優(yōu)勢性。

圖3 單引擎與多引擎查詢性能對比

4.2 查詢感知的關(guān)系-圖的存儲優(yōu)化

多數(shù)據(jù)模型對數(shù)據(jù)集進(jìn)行協(xié)同存儲體現(xiàn)了其性能的優(yōu)越性，但也同時需要付出一定的代價。這方面主要體現(xiàn)在復(fù)雜的運(yùn)維與冗余存儲上。本節(jié)提出了查詢感知的存儲優(yōu)化方式，來結(jié)合數(shù)據(jù)特點(diǎn)與用戶需求，來解決冗余存儲的問題。

由于數(shù)據(jù)存儲的優(yōu)化方案受到數(shù)據(jù)集本身特點(diǎn)與用戶個人查詢需求的影響，系統(tǒng)很難一開始就對用戶傳入的數(shù)據(jù)集進(jìn)行結(jié)構(gòu)判斷與需求分析，因此采用用戶查詢感知的方式進(jìn)行協(xié)同存儲調(diào)優(yōu)，其機(jī)制是：定期解析用戶輸入的查詢內(nèi)容，分析用戶的查詢需求并解析數(shù)據(jù)庫中的數(shù)據(jù)結(jié)構(gòu)，進(jìn)而完成自適應(yīng)存儲優(yōu)化，達(dá)到為用戶優(yōu)化存儲空間的目的。

根據(jù)上述基于查詢感知的存儲優(yōu)化思路，用戶上傳至平臺的數(shù)據(jù)流如圖4 所示。用戶上傳數(shù)據(jù)并選擇數(shù)據(jù)庫默認(rèn)選項(xiàng)為全冗余形式，即將數(shù)據(jù)全部傳輸至兩個數(shù)據(jù)引擎當(dāng)中。同時平臺也提供了用戶選項(xiàng)，用戶可以在上傳數(shù)據(jù)時或者在自適應(yīng)優(yōu)化存儲過程中，申請主動分配數(shù)據(jù)至指定空間或申請主動從某一引擎刪除部分?jǐn)?shù)據(jù)。用戶選項(xiàng)的設(shè)置一方面可以提高基于查詢感知自適應(yīng)調(diào)優(yōu)程序的容錯率，減少因調(diào)優(yōu)程序引起部分查詢效率降低的情況，另一方面也可以更好地獲取用戶個人需求信息，進(jìn)行更準(zhǔn)確的存儲調(diào)優(yōu)。

圖4 數(shù)據(jù)庫引擎間的數(shù)據(jù)流

在用戶上傳數(shù)據(jù)進(jìn)入平臺之后，數(shù)據(jù)將以全冗余的形式存入到兩個數(shù)據(jù)引擎當(dāng)中。接下來，平臺的自適應(yīng)調(diào)優(yōu)程序?qū)τ脩籼峤坏拿恳粋€查詢進(jìn)行相應(yīng)的分析，并存儲至用戶對應(yīng)的查詢歷史記錄當(dāng)中。存儲調(diào)優(yōu)過程如圖5 所示。調(diào)優(yōu)程序?qū)ㄆ谡{(diào)用存儲的查詢記錄，根據(jù)解析用戶提交的查詢對數(shù)據(jù)集結(jié)構(gòu)特點(diǎn)與用戶需求進(jìn)行判斷，從而得到如何對數(shù)據(jù)進(jìn)行存儲判斷。需要提及的是，程序中用戶的查詢輸入暫時默認(rèn)為SQL語句形式。

圖5 自適應(yīng)存儲調(diào)優(yōu)處理過程

基于以上的分析，協(xié)同存儲優(yōu)化實(shí)現(xiàn)算法主要分為兩個部分：用戶查詢解析算法與存儲優(yōu)化算法。

4.2.1 用戶查詢解析算法

用戶查詢解析算法將用戶的每一個查詢進(jìn)行結(jié)構(gòu)上與內(nèi)容上的解析，進(jìn)而判斷用戶所存儲的數(shù)據(jù)集中哪一部分?jǐn)?shù)據(jù)參與了復(fù)雜的表連接查詢，哪一部分?jǐn)?shù)據(jù)經(jīng)常參與了聚集查詢等。將查詢語句所隱含的信息解析出來之后，用作接下來自適應(yīng)存儲調(diào)優(yōu)算法的判斷依據(jù)，進(jìn)而完成存儲優(yōu)化的目標(biāo)。

算法整體可分為預(yù)處理階段與信息解析階段。預(yù)處理階段將用戶輸入的查詢語句格式統(tǒng)一后分塊。分塊后有利于之后的信息挖掘與獲取。信息解析階段將分塊后的信息進(jìn)行解析整合。解析后，每個數(shù)據(jù)表的信息會以哈希表的形式存儲下來：該表總查詢訪問數(shù)，該表參與屬性查詢數(shù)，該表參與查詢的本身表連接數(shù)以及該表參與查詢的總連接數(shù)。通過這些哈希表存儲的信息，來傳達(dá)用戶查詢中潛藏的表信息與用戶需求。算法具體描述如下：

算法1查詢解析算法

4.2.2 存儲優(yōu)化算法

用戶查詢解析后，算法將每個表的信息存到對應(yīng)表中，接下來存儲調(diào)優(yōu)算法進(jìn)行冗余存儲優(yōu)化。算法將使用解析信息，對用戶需求與數(shù)據(jù)結(jié)構(gòu)進(jìn)行判斷，由此完成對部分?jǐn)?shù)據(jù)在某一引擎中的存儲或者刪除操作。數(shù)據(jù)存儲調(diào)整單位為關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)表，當(dāng)在關(guān)系數(shù)據(jù)庫中的表發(fā)生存儲變化時，只需按照表的形式進(jìn)行調(diào)整；當(dāng)圖數(shù)據(jù)庫中的數(shù)據(jù)發(fā)生調(diào)整時，則只需按照節(jié)點(diǎn)情況進(jìn)行增減。值得一提的是，由于Neo4J的存儲模式問題，在Neo4J引擎中進(jìn)行任何的數(shù)據(jù)變更成本都比較高，所以算法在判斷數(shù)據(jù)在Neo4J 中的存儲或者刪除時，要求會相對較高。

解析算法核心為啟發(fā)式規(guī)則：（1）當(dāng)數(shù)據(jù)表本身參與連接數(shù)不超過該表總查詢數(shù)時，認(rèn)定該表每次查詢最多本身只參與一次表連接，可判斷這類表基本主要職能為存儲某一節(jié)點(diǎn)的屬性集，因此這類表存儲位置判斷為關(guān)系數(shù)據(jù)庫。（2）當(dāng)該表每次查詢都有x次（x為可調(diào)整系數(shù)，目前設(shè)定為2）聚集、排序等查詢時，則該表至少存儲在關(guān)系數(shù)據(jù)庫中。若該表參與的每個查詢都小于y表連接數(shù)（y為可調(diào)整系數(shù)，目前設(shè)定為3），刪除該表在Neo4J 引擎中的存儲，否則，兩個引擎冗余存儲這段數(shù)據(jù)。（3）當(dāng)該表參與的每個查詢都超過了z表連接數(shù)（z為可調(diào)整系數(shù)，目前設(shè)定為5），判斷數(shù)據(jù)應(yīng)存入Neo4J 數(shù)據(jù)引擎。若該表每次查詢自身參與連接數(shù)超過n（n為可調(diào)整系數(shù)，目前設(shè)定為2），刪除該表在關(guān)系數(shù)據(jù)引擎中的存儲。算法具體描述如下：

算法2存儲優(yōu)化算法

4.2.3 存儲優(yōu)化算法分析

基于啟發(fā)式的存儲空間優(yōu)化算法通過一系列的規(guī)則判斷來完成以表為單位的刪除與存儲選擇，而對于這個規(guī)則它是后期經(jīng)過不斷的學(xué)習(xí)和修改進(jìn)行完善的。就目前來說，算法中的啟發(fā)式規(guī)則借鑒了大量實(shí)踐經(jīng)驗(yàn)，可以保證絕大多數(shù)情況下存儲優(yōu)化算法判斷的正確性，代表了一定的普遍性，但考慮到用戶的查詢不可預(yù)測性、數(shù)據(jù)的多樣化性以及存儲結(jié)構(gòu)的不斷調(diào)整可能會影響用戶某些查詢的執(zhí)行性能以及協(xié)同存儲的分配準(zhǔn)確率，因此系統(tǒng)在優(yōu)化上還進(jìn)行了以下設(shè)定：一是定期調(diào)用自適應(yīng)存儲優(yōu)化算法執(zhí)行程序，待調(diào)優(yōu)完畢后刪除之前的查詢解析信息，重新統(tǒng)計(jì)下一周期的用戶查詢信息，確保每一次存儲調(diào)優(yōu)都是基于用戶最近時間的查詢記錄，同時根據(jù)變化完善算法規(guī)則；二是開放用戶選項(xiàng)，允許用戶申請調(diào)整數(shù)據(jù)的存儲位置，若是采用這一過程將會加大數(shù)據(jù)分類存儲的復(fù)雜性以及存儲優(yōu)化算法的適用性，增加了存儲算法的挑戰(zhàn)性，如果成功，則無異于增強(qiáng)了算法的健壯性與普遍性，從而使系統(tǒng)的執(zhí)行更加完善和具有代表性。因此基于以上分析，采用定期調(diào)用存儲優(yōu)化程序與開放用戶選項(xiàng)兩者相結(jié)合的思路，從而實(shí)現(xiàn)協(xié)同存儲算法的不斷優(yōu)化性、可用性與實(shí)用性和用戶查詢效率的最大化與最優(yōu)化。

5 實(shí)驗(yàn)與分析

實(shí)驗(yàn)分為兩部分：（1）測試雙引擎全冗余存儲下和優(yōu)化存儲后的查詢性能對比與存儲空間優(yōu)化率；（2）測試單數(shù)據(jù)引擎存儲情況下和優(yōu)化存儲后的查詢性能對比與存儲空間對比。通過兩部分實(shí)驗(yàn)來評估查詢感知的自適應(yīng)存儲調(diào)優(yōu)性能。

5.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境中的軟硬件配置如表2 所示。實(shí)驗(yàn)使用數(shù)據(jù)集使用Yelp公開數(shù)據(jù)集，為了達(dá)到測試不同數(shù)據(jù)規(guī)模的算法效果，同時準(zhǔn)備了2倍、4倍與8倍于原數(shù)據(jù)量的實(shí)驗(yàn)數(shù)據(jù)集。

Yelp 數(shù)據(jù)集本身的組織形式為JSON 格式，解析將其存入關(guān)系數(shù)據(jù)庫PostgreSQL 中，一共18 張表。在將Yelp實(shí)際數(shù)據(jù)集導(dǎo)入關(guān)系數(shù)據(jù)庫PostgreSQL中后，再將其轉(zhuǎn)換成CSV 后導(dǎo)入Neo4J 當(dāng)中。圖數(shù)據(jù)Neo4J 中存儲節(jié)點(diǎn)數(shù)量達(dá)到900萬，節(jié)點(diǎn)主要類型有商家、用戶、圖片、評論和建議等。Yelp原數(shù)據(jù)集信息統(tǒng)計(jì)如表3所示。

表2 實(shí)驗(yàn)環(huán)境配置

表3 實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)信息

5.2 查詢實(shí)驗(yàn)設(shè)置

為提高用戶查詢的仿真度，從數(shù)據(jù)源網(wǎng)站中隨機(jī)選取了多個用戶常見查詢作為構(gòu)造查詢的主要參考。為了檢測到存儲優(yōu)化算法的每一個規(guī)則是否都有作用，因此查詢設(shè)置也盡可能地涉及了更多查詢類型，同時查詢的表也盡可能訪問到數(shù)據(jù)庫中18個數(shù)據(jù)表。具體查詢類型設(shè)計(jì)情況如表4所示，并給出了簡單的樣例查詢介紹。

表4 查詢實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)查詢組以包含查詢類型為分組，在每一個實(shí)驗(yàn)查詢組都包含15 個符合條件的查詢，一共設(shè)有120個對應(yīng)的查詢。

5.3 實(shí)驗(yàn)結(jié)果與性能評估

本節(jié)主要說明兩組對比實(shí)驗(yàn)的查詢結(jié)果對比與存儲情況對比，并根據(jù)兩組實(shí)驗(yàn)對比的結(jié)果進(jìn)行存儲優(yōu)化算法執(zhí)行的性能評估。

5.3.1 全冗余存儲與優(yōu)化存儲對比

該對比實(shí)驗(yàn)主要是為了檢驗(yàn)查詢感知的自適應(yīng)存儲優(yōu)化算法的實(shí)際優(yōu)化效果以及算法對整個系統(tǒng)查詢性能影響。

實(shí)驗(yàn)具體操作如下：將設(shè)置好的查詢在全冗余存儲下進(jìn)行測試，記錄時間，并啟動存儲優(yōu)化程序。查詢實(shí)驗(yàn)全部完成后，按照調(diào)優(yōu)程序進(jìn)行存儲位置優(yōu)化后，重新使用查詢實(shí)驗(yàn)進(jìn)行測試，得到優(yōu)化后的查詢時間。圖6 展示了不同規(guī)模大小數(shù)據(jù)集優(yōu)化前后的存儲空間變化。

圖6 存儲空間優(yōu)化效果

存儲算法優(yōu)化空間效果達(dá)到了接近三分之一，已經(jīng)十分接近理想情況下無冗余存儲的0.5。對比不同大小實(shí)驗(yàn)集時，優(yōu)化效果最好的為8 倍的數(shù)據(jù)集，最差的為原數(shù)據(jù)集。數(shù)據(jù)集本身的大小跟優(yōu)化效果關(guān)聯(lián)并不是很大。僅從存儲空間優(yōu)化來看，存儲優(yōu)化算法的優(yōu)化效率還是比較理想的，但仍需關(guān)注存儲優(yōu)化對查詢性能的影響。圖7為不同規(guī)模數(shù)據(jù)集下，查詢性能變化。

優(yōu)化前全冗余的存儲形式相對而言在查詢性能上擁有優(yōu)勢。當(dāng)數(shù)據(jù)規(guī)模大小增大時，部分設(shè)置的查詢組的查詢時間也隨之變大了。這主要是因?yàn)殡S著數(shù)據(jù)集規(guī)模的增大，兩個引擎中進(jìn)行的數(shù)據(jù)查找操作也變得復(fù)雜起來。設(shè)置查詢組后半部分變化較大，也是由于后半部分設(shè)置的查詢組涉及查詢類型較多，數(shù)據(jù)處理情況更為復(fù)雜。

從實(shí)驗(yàn)結(jié)果來看，存儲優(yōu)化算法產(chǎn)生的查詢時間影響波動在5%到20%之間變化。其中，高幅度變化的查詢數(shù)量實(shí)驗(yàn)下并不多。綜合四個數(shù)據(jù)集下不同查詢的平均變化來看，優(yōu)化后的整體查詢時間增加了12%左右。本文認(rèn)為這個數(shù)值處于一個可接受的波動范圍，并且未來認(rèn)為同通過查詢優(yōu)化的方式進(jìn)行進(jìn)一步的時間優(yōu)化。總體而言，存儲優(yōu)化算法在實(shí)驗(yàn)環(huán)境中為全冗余存儲的實(shí)驗(yàn)數(shù)據(jù)完成了30%左右的實(shí)際存儲空間優(yōu)化，同時查詢性能下降了12%左右，優(yōu)化效果較為良好。

圖7 查詢性能優(yōu)化效果

5.3.2 優(yōu)化存儲與單引擎存儲對比

這一組實(shí)驗(yàn)對比是為了驗(yàn)證整個系統(tǒng)在經(jīng)過多引擎協(xié)同存儲與自適應(yīng)存儲優(yōu)化后，與傳統(tǒng)的單引擎管理圖數(shù)據(jù)進(jìn)行查詢性能上與存儲空間上的對比，從而得出查詢感知的關(guān)系-圖自適應(yīng)存儲優(yōu)化的多模型協(xié)同管理方案的整體效果。

實(shí)驗(yàn)查詢空間對比如圖8所示?？梢钥吹?，在進(jìn)行存儲優(yōu)化后，多數(shù)據(jù)模型協(xié)同管理數(shù)據(jù)依然需要使用大量存儲空間?？偟膩砜?，相比單引擎，優(yōu)化后的多數(shù)據(jù)引擎管理使用了多40%左右的實(shí)際存儲。在不考慮查詢的情況下，這種存儲空間對比使用還是不可忽視的。所以依然還是需要結(jié)合查詢時間對比得到更準(zhǔn)確的性能對比結(jié)論。

圖8 單引擎與優(yōu)化多引擎存儲對比

圖9 為單引擎和優(yōu)化后協(xié)同存儲多引擎的查詢時間對比實(shí)驗(yàn)結(jié)果?？偟膩砜?，在任何查詢組中，優(yōu)化過后的協(xié)同存儲管理下的查詢效率始終不是最差的。根據(jù)查詢實(shí)驗(yàn)平均查詢時間得出：單個引擎的查詢時間都是優(yōu)化存儲查詢時間的三倍以上。從這兩個方面而言，優(yōu)化組的查詢性能相對是比較高的。

圖9 單引擎與優(yōu)化后存儲多引擎的查詢性能對比

從不同數(shù)據(jù)規(guī)模實(shí)驗(yàn)結(jié)果對比來看，隨著數(shù)據(jù)規(guī)模的增加，實(shí)驗(yàn)查詢組——后幾組的性能差距也隨之增大。本文認(rèn)為這主要是因?yàn)閿?shù)據(jù)規(guī)模的增加，使數(shù)據(jù)引擎需要做的查詢操作變得更加復(fù)雜，不同引擎之間的查詢性能差距將不斷擴(kuò)大，尤其是多表連接查詢，使得后幾組查詢實(shí)驗(yàn)中涉及多表連接查詢的實(shí)驗(yàn)，在使用單個數(shù)據(jù)庫引擎管理數(shù)據(jù)時，性能會不斷變差，而在多數(shù)據(jù)模型協(xié)同管理情況下的查詢性能相對會好很多。這也證明了多數(shù)據(jù)模型管理在經(jīng)過優(yōu)化后，依然具有很大的整體查詢優(yōu)勢?？傮w而言，優(yōu)化后的多數(shù)據(jù)協(xié)同管理在多使用了不到五成的存儲成本下，可以獲得三倍以上的查詢性能。

6 結(jié)束語

本文針對在數(shù)據(jù)云服務(wù)平臺DataCloud中如何保證圖數(shù)據(jù)在不同需求場景下的高查詢性能問題，通過對多個數(shù)據(jù)模型的查詢效率進(jìn)行預(yù)備實(shí)驗(yàn)和結(jié)果分析，提出了多數(shù)據(jù)模型協(xié)同管理數(shù)據(jù)的模式，并提出了基于查詢感知的自適應(yīng)存儲優(yōu)化算法來解決多數(shù)據(jù)模型存儲數(shù)據(jù)時的存儲冗余問題。該方法利用查詢歷史，分析查詢結(jié)構(gòu)與內(nèi)容，并利用啟發(fā)式規(guī)則建立代價模型，來完成數(shù)據(jù)的遷移與刪除等存儲優(yōu)化工作。實(shí)驗(yàn)結(jié)果表明，多數(shù)據(jù)模型協(xié)同存儲數(shù)據(jù)相比單引擎存儲，有著更好的查詢效果；同時驗(yàn)證了存儲優(yōu)化算法為此種存儲模式提供了良好的存儲優(yōu)化效果。未來將考慮文檔、KV 等更多引擎，以及基于存儲優(yōu)化能力進(jìn)一步優(yōu)化系統(tǒng)查詢處理操作或過程。

致謝本文工作得到中國人民大學(xué)信息技術(shù)與管理國家級實(shí)驗(yàn)教學(xué)示范中心的部分支持。感謝審稿專家們的寶貴修改意見和建議，同時感謝中國人民大學(xué)數(shù)據(jù)工程與知識工程教育部重點(diǎn)實(shí)驗(yàn)室人大行云云平臺為本文項(xiàng)目提供的實(shí)驗(yàn)環(huán)境。