李高超，李犇，盧毓海，劉夢(mèng)雅，劉燕兵

（1. 中國科學(xué)院大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，北京 100049；2. 國家計(jì)算機(jī)網(wǎng)絡(luò)與信息安全管理中心，北京 100029；3. 北京市公安局朝陽分局，北京 100029；4. 中國科學(xué)院信息工程研究所，北京 100093；5. 信息內(nèi)容安全技術(shù)國家工程實(shí)驗(yàn)室，北京 100093；6. 英國南安普頓大學(xué)，南安普頓SO171BJ）

1 引言

隨著網(wǎng)絡(luò)中大規(guī)模復(fù)雜多變數(shù)據(jù)的產(chǎn)生，數(shù)據(jù)分析的關(guān)注點(diǎn)從實(shí)體屬性逐漸轉(zhuǎn)向?qū)嶓w間的關(guān)系[1]，圖成為社交網(wǎng)絡(luò)、信息檢索等領(lǐng)域研究分析數(shù)據(jù)的有效模型[2-4]，各種面向?qū)嶓w間關(guān)系的基于圖數(shù)據(jù)的應(yīng)用層出不窮。大規(guī)模圖數(shù)據(jù)結(jié)構(gòu)復(fù)雜、耦合度高等特點(diǎn)使查詢操作時(shí)間開銷大、緩存命中率低，并給數(shù)據(jù)管理帶來了巨大的挑戰(zhàn)，導(dǎo)致當(dāng)前業(yè)界應(yīng)用廣泛的數(shù)據(jù)庫在存儲(chǔ)和檢索圖數(shù)據(jù)方面顯得力不從心[5-6]。優(yōu)化圖數(shù)據(jù)查詢?cè)L問算法能夠滿足圖數(shù)據(jù)存儲(chǔ)、計(jì)算、更新等操作節(jié)省處理時(shí)間和存儲(chǔ)空間的需求。

在大規(guī)模實(shí)體關(guān)系圖中，查詢計(jì)算分析以節(jié)點(diǎn)屬性查詢、邊屬性查詢和節(jié)點(diǎn)鄰居查詢?yōu)橹?。帶有屬性信息的大?guī)模圖數(shù)據(jù)通常無法完全加載到內(nèi)存中，提高節(jié)點(diǎn)鄰居查詢命中緩存的概率能夠有效減少查詢的時(shí)間。本文針對(duì)上述圖數(shù)據(jù)查詢需求，提出了圖數(shù)據(jù)壓縮索引算法——GComIdx。GComIdx在屬性圖模型的核心思想基礎(chǔ)上，分別對(duì)屬性查詢和節(jié)點(diǎn)鄰居查詢這2個(gè)方面進(jìn)行了優(yōu)化，在超大規(guī)模簡(jiǎn)單圖的查詢方面有著較好的表現(xiàn)，且GComIdx主要針對(duì)的是靜態(tài)圖的應(yīng)用場(chǎng)景。

2 二級(jí)索引圖壓縮算法

本節(jié)提出針對(duì)實(shí)體關(guān)系網(wǎng)絡(luò)查詢需求的圖數(shù)據(jù)壓縮索引算法——GComIdx，該算法支持的查詢操作有節(jié)點(diǎn)屬性查詢、邊屬性查詢和節(jié)點(diǎn)鄰居查詢。以圖1中的圖數(shù)據(jù)為例逐一說明該算法的工作過程。圖1為微博業(yè)務(wù)中常見的用戶、文章產(chǎn)生的關(guān)系網(wǎng)絡(luò)，其中，節(jié)點(diǎn)包括用戶和文章2種，關(guān)系包括關(guān)注、互粉、發(fā)布、轉(zhuǎn)發(fā)、收藏等。

2.1 屬性查詢

在屬性查找方面，GComIdx將節(jié)點(diǎn)和邊的屬性存儲(chǔ)模型抽象成Key-Value形式，按照Key將數(shù)據(jù)進(jìn)行排序后壓縮存儲(chǔ)，當(dāng)查找節(jié)點(diǎn)和邊的屬性時(shí)，采用二分查找的方式實(shí)現(xiàn)屬性的快速查找。

圖1 微博關(guān)系數(shù)據(jù)

2.1.1 屬性壓縮索引構(gòu)建

GComIdx算法中屬性壓縮索引構(gòu)建過程主要包括以下3個(gè)步驟：排序、分塊、壓縮。最終，該算法在解決屬性圖模型中屬性查找的問題方面，采用在有序的Key-Value數(shù)據(jù)集上建立二級(jí)壓縮索引的方式實(shí)現(xiàn)。

首先，本文算法將節(jié)點(diǎn)和邊的數(shù)據(jù)抽象為Key-Value[7]形式。其中，Key 為＜u0,v0＞的形式，Value為按照特定規(guī)則處理的序列化數(shù)據(jù)。

在節(jié)點(diǎn)數(shù)據(jù)抽象方面，本文算法將節(jié)點(diǎn)進(jìn)行編號(hào)，分配節(jié)點(diǎn)ID，節(jié)點(diǎn)ID從1到n編號(hào)。第i個(gè)節(jié)點(diǎn)屬性數(shù)據(jù)抽象為 Key-Value，即＜i,0＞-Attri，其中，Key為＜i,0＞（u0為 i，v0為 0），Value為本節(jié)點(diǎn)的屬性數(shù)據(jù)Attri。

在邊屬性數(shù)據(jù)抽象方面，本文算法將節(jié)點(diǎn)u與節(jié)點(diǎn)v之間的關(guān)系A(chǔ)ttr＜u,v＞抽象為Key-Value形式，即＜u,v＞- Attr＜u,v＞，其中，Key 為＜u,v＞（u0為 u，v0為v），Value為節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的關(guān)系屬性數(shù)據(jù)Attr＜u,v＞。本文算法對(duì)原始Key進(jìn)行處理，將u0和v0的ID轉(zhuǎn)換為二進(jìn)制后，再將u0左移32位末尾補(bǔ)0，其結(jié)果與v0做與操作，處理后得到一個(gè)64位的長整型Key。

最后，逐條讀入節(jié)點(diǎn)和邊的屬性數(shù)據(jù)并對(duì)其按照源節(jié)點(diǎn)ID進(jìn)行分桶，在桶內(nèi)以64位的長整型Key進(jìn)行排序，同時(shí)記錄源節(jié)點(diǎn)的出度，過程如圖2所示。

圖2 GComIdx索引構(gòu)造過程

圖數(shù)據(jù)對(duì)應(yīng)的有序 Key-Value[7]列表生成方式如圖3所示，將節(jié)點(diǎn)和邊的屬性存儲(chǔ)模型抽象成Key-Value數(shù)據(jù)集，并將數(shù)據(jù)集按 Key值進(jìn)行排序。基于Key值有序的屬性數(shù)據(jù)具有以下3個(gè)方面的優(yōu)勢(shì)：1)在查找屬性信息時(shí)，可以在有序的數(shù)據(jù)上進(jìn)行二分查找，提高查找的效率；2)有序的數(shù)據(jù)具有相似性，當(dāng)這些數(shù)據(jù)集中存放在同一個(gè)數(shù)據(jù)塊中，在對(duì)數(shù)據(jù)塊進(jìn)行壓縮時(shí)能獲得較好的壓縮比[8-9]；3)從當(dāng)前計(jì)算機(jī)硬件發(fā)展的規(guī)律來看，CPU的計(jì)算已不再是系統(tǒng)瓶頸，而是內(nèi)存空間大小和磁盤I/O速度[10]，壓縮比較高的數(shù)據(jù)塊載入內(nèi)存與解壓縮時(shí)間開銷遠(yuǎn)小于將原始數(shù)據(jù)讀入內(nèi)存的時(shí)間開銷。

在已經(jīng)排序的Key-Value數(shù)據(jù)集上對(duì)數(shù)據(jù)進(jìn)行分塊和壓縮，如圖3所示按照壓縮分塊的分布情況建立二級(jí)索引。首先根據(jù)數(shù)據(jù)集的大小和數(shù)據(jù)塊的大小確定低級(jí)索引的數(shù)據(jù)規(guī)模，一般以低級(jí)索引能夠常駐內(nèi)存為標(biāo)準(zhǔn)，從而加速查找速度。同理，在低級(jí)索引的基礎(chǔ)上建立高級(jí)索引，高級(jí)索引指向低級(jí)索引中的相應(yīng)位置。

GComIdx屬性查詢索引的構(gòu)建如算法1所示，算法輸入為節(jié)點(diǎn)出度統(tǒng)計(jì)表C、有序的邊列表文件E和數(shù)據(jù)塊規(guī)模s。步驟1)～步驟8)根據(jù)節(jié)點(diǎn)出度和塊規(guī)模 s對(duì)節(jié)點(diǎn)進(jìn)行分塊，得到分塊后的每個(gè)塊所包含的邊數(shù)目。步驟9)～步驟25)根據(jù)已經(jīng)分好的塊大小逐行讀取邊數(shù)據(jù)信息，對(duì)邊數(shù)據(jù)抽象成屬性模型并將Key和Value分別讀入內(nèi)存的同一數(shù)據(jù)塊中，對(duì)數(shù)據(jù)進(jìn)行壓縮，最后將壓縮的數(shù)據(jù)塊寫入磁盤。

算法1 GComIdx屬性查詢索引構(gòu)建算法

1) GComIdx-Property (C , E , s )

2) for C中的每一個(gè)元素 do

3) n ← n+element.count

4) if n ＞ s do

5) Push(element.node,B)

6) Push(n,S)

7) end if

8) end for

9) EdgeOffset ← 0

10) for B中的每一個(gè)元素do

11) Offset ← 0

12) while從E中讀取一行元素do

13) Key,Value ← line

14) Push(Key,DBlock)

圖3 GComIdx屬性查詢索引構(gòu)造過程

15) Push(Offset,DBlock)

16) Push(Value,DBlock[Offset])

17) Offset ← Offset + length(Value)

18) if Offset == 0 do

19) Push(Key,Edges_Index)

20) Push(EdgeOffset,Edges_Offset)

21) end if

22) end while

23) CBlock ← Compress(DBlock)

24) append CBlock to the index file

25) end for

2.1.2 屬性查詢操作

屬性的查詢操作分為節(jié)點(diǎn)的屬性查詢和邊的屬性查詢 2種。當(dāng)進(jìn)行節(jié)點(diǎn)屬性查詢時(shí)，查詢的Key值為節(jié)點(diǎn)ID；當(dāng)進(jìn)行邊的屬性查詢時(shí)，查詢的Key值為＜u,v＞，其中，u為邊的起始節(jié)點(diǎn)ID，v為邊的結(jié)束節(jié)點(diǎn)ID，GComIdx將u和v的ID轉(zhuǎn)換為二進(jìn)制后組合成一個(gè)64位的長整型Key。獲得查詢Key值后，GComIdx在有序的Key值數(shù)組上進(jìn)行二分查找。

2.2 相鄰節(jié)點(diǎn)查詢

在相鄰節(jié)點(diǎn)查找方面，GComIdx仍采用有序Key-Value列表方式存儲(chǔ)邊數(shù)據(jù)。大規(guī)模實(shí)體關(guān)系圖中節(jié)點(diǎn)數(shù)遠(yuǎn)低于邊數(shù)[11]，所以 GComIdx對(duì)節(jié)點(diǎn)的索引采取一級(jí)hash索引組織管理數(shù)據(jù)，即將邊列表排序后按照邊的起始節(jié)點(diǎn)ID進(jìn)行hash的方式構(gòu)建索引，以達(dá)到快速查找指定節(jié)點(diǎn)相鄰所有節(jié)點(diǎn)的目的。

2.2.1 相鄰節(jié)點(diǎn)壓縮索引構(gòu)建

GComIdx將邊數(shù)據(jù)＜u,v＞存為其相應(yīng)Key值（見2.1.2節(jié)），并將所有邊按Key值排序，節(jié)點(diǎn)u的所有邊在數(shù)據(jù)塊中將連續(xù)存在，如圖4所示，根據(jù)已經(jīng)計(jì)算得到的節(jié)點(diǎn)出度表信息，得出每個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的邊數(shù)據(jù)段在壓縮的邊屬性信息中所對(duì)應(yīng)的位置。按照 2.1.1節(jié)中相同的分塊方法劃分得到數(shù)據(jù)塊并壓縮，構(gòu)造鄰居節(jié)點(diǎn)索引。

2.2.2 相鄰節(jié)點(diǎn)查詢操作

查詢給定節(jié)點(diǎn)的相鄰節(jié)點(diǎn)時(shí)，根據(jù)待查詢的節(jié)點(diǎn) u，從鄰居節(jié)點(diǎn)索引中獲取該節(jié)點(diǎn)的首條邊在壓縮數(shù)據(jù)塊中的位置Offsetu，將對(duì)應(yīng)的數(shù)據(jù)塊CBlocki調(diào)入內(nèi)存，執(zhí)行解壓縮和遍歷、去重等操作，從而獲取節(jié)點(diǎn)集合V，其中， V = { v | ＜ u ,v ＞ ∈ E }。

3 實(shí)驗(yàn)評(píng)估

3.1 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)數(shù)據(jù)為特定行業(yè)收集到的大規(guī)模社交網(wǎng)絡(luò)圖數(shù)據(jù)，包括600萬個(gè)節(jié)點(diǎn)、2.8億條邊。

實(shí)驗(yàn)環(huán)境為曙光服務(wù)器A620-G，具體配置如下：AMD Opteron 6128 2 GHz CPU（主頻：3.10 GHz八核），32 GB DDR3內(nèi)存，Linux Centos 7（64位）操作系統(tǒng)。算法代碼以C++實(shí)現(xiàn)，用GCC 4.8.3編譯。

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)主要從圖初始化和子圖查詢[12]這2個(gè)方面進(jìn)行，因子圖查詢需要同時(shí)執(zhí)行屬性查詢和鄰居查詢。在圖數(shù)據(jù)集上對(duì) PostgreSQL[13]、SSDB、Redis[14]、Neo4j[15]和 GComIdx數(shù)據(jù)存儲(chǔ)方案進(jìn)行比較，主要以圖數(shù)據(jù)導(dǎo)入的時(shí)間開銷、占用磁盤空間和不同規(guī)模圖數(shù)據(jù)上的查詢操作所耗費(fèi)的時(shí)間作為評(píng)價(jià)標(biāo)準(zhǔn)。

3.3 索引構(gòu)建時(shí)間比較

將大規(guī)模圖數(shù)據(jù)分別導(dǎo)入PostgreSQL、SSDB、Redis、Neo4j和 GComIdx，觀察記錄程序運(yùn)行時(shí)間和磁盤占用空間。各個(gè)存儲(chǔ)方案的初始化時(shí)間如表1所示。在同樣的實(shí)驗(yàn)條件下用時(shí)最長的是圖數(shù)據(jù)庫PostgreSQL。由此可知，Neo4j和PostgreSQL等通用數(shù)據(jù)庫比較適用于圖規(guī)模逐漸增大的場(chǎng)景，如動(dòng)態(tài)圖的處理。而采用Key-Value結(jié)構(gòu)的存儲(chǔ)方案，如Redis、SSDB、GComIdx，在數(shù)據(jù)導(dǎo)入方面有著明顯優(yōu)勢(shì)。

表1 存儲(chǔ)方案初始化時(shí)間

GComIdx在初始化時(shí)間開銷上有著較好的表現(xiàn)，其用時(shí)僅次于Redis內(nèi)存數(shù)據(jù)庫集群。但是由于Redis是內(nèi)存數(shù)據(jù)庫，當(dāng)實(shí)驗(yàn)數(shù)據(jù)量過大時(shí)，單機(jī)上的單進(jìn)程寫入多次失敗，雖然集群部署方案可以解決寫入失敗問題，但是引入了查詢失敗和多次查詢的問題，導(dǎo)致查詢效率下降。相較而言，GComIdx以微小的初始化保證正確初始化和成功查詢。

圖4 GComIdx鄰居節(jié)點(diǎn)索引構(gòu)造過程

3.4 索引存儲(chǔ)空間比較

實(shí)驗(yàn)數(shù)據(jù)集在各個(gè)存儲(chǔ)方案初始化處理后占用的磁盤空間如表2所示。GComIdx算法磁盤占用率最低，SSDB、Redis具有較好的空間性能，Neo4j、PostgreSQL磁盤占用率較高。Key-Value結(jié)構(gòu)在節(jié)省磁盤空間上同樣優(yōu)于通用數(shù)據(jù)庫，而與其他采用Key-Value結(jié)構(gòu)的方案相比，GComIdx在磁盤占用空間上表現(xiàn)出的優(yōu)勢(shì)來源于壓縮操作，盡管其生成并存儲(chǔ)了二級(jí)索引，但其對(duì)邊序列排序分塊后的壓縮操作成功降低了磁盤上需要存儲(chǔ)的數(shù)據(jù)量。

表2 存儲(chǔ)方案磁盤空間

GComIdx算法充分利用了Key-Value結(jié)構(gòu)在初始化和存儲(chǔ)空間上的優(yōu)勢(shì)，并通過對(duì)圖數(shù)據(jù)的排序和分塊后的壓縮進(jìn)一步提高了其在節(jié)省磁盤空間上的優(yōu)勢(shì)。實(shí)驗(yàn)說明，無論從初始化時(shí)間還是磁盤空間占比來看，GComIdx都優(yōu)于其他通用數(shù)據(jù)庫。

3.5 查詢效率比較

在導(dǎo)入后的圖數(shù)據(jù)集上，按各個(gè)圖數(shù)據(jù)管理方案分別查詢邊規(guī)模為50、100、500、1 000、5 000、10 000、50 000、100 000的子圖，觀察并記錄其查詢時(shí)間的變化，如圖5所示。從實(shí)驗(yàn)結(jié)果來看，當(dāng)查詢的子圖規(guī)模小于10 000條邊時(shí)，各方案查詢效率相差不大，查詢時(shí)間都呈線性增長；當(dāng)查詢的子圖規(guī)模大于 10 000條邊時(shí)，PostgreSQL與 Neo4j的性能表現(xiàn)都急劇下降，其他方案表現(xiàn)相差不大。

與其他存儲(chǔ)方案相比，GComIdx算法在子圖規(guī)模為50 000條邊以下時(shí)，查詢耗時(shí)最小；當(dāng)子圖規(guī)模為100 000條邊時(shí)，其查詢耗時(shí)與SSDB和Redis方案近似相同。GComIdx算法在執(zhí)行查詢操作時(shí)，利用二級(jí)索引查詢得到所需節(jié)點(diǎn)或邊的信息后，還需要執(zhí)行數(shù)據(jù)分塊載入內(nèi)存中的解壓縮操作，即實(shí)驗(yàn)結(jié)果表示的查詢時(shí)間包含了解壓縮操作的時(shí)間，因此不難得出，GComIdx提出的基于Key值排序后的二級(jí)索引算法在圖數(shù)據(jù)上的查詢更具有優(yōu)勢(shì)。

圖5 存儲(chǔ)方案查詢時(shí)間

4 結(jié)束語

針對(duì)通用數(shù)據(jù)庫在管理圖數(shù)據(jù)時(shí)存在的查詢耗時(shí)高和空間占比大的難題，本文針對(duì)圖數(shù)據(jù)上的查詢操作，提出二級(jí)索引壓縮算法——GComIdx。基于有序的Key-Value結(jié)構(gòu)，為屬性查詢和節(jié)點(diǎn)鄰居查詢分別構(gòu)建二級(jí)索引和節(jié)點(diǎn)hash索引，充分利用了節(jié)點(diǎn)相關(guān)性提高查詢速度，降低數(shù)據(jù)壓縮后的磁盤占用空間。實(shí)驗(yàn)結(jié)果表明，GComIdx在有效降低圖數(shù)據(jù)初始化時(shí)間開銷和磁盤占用空間的情況下，查詢效率仍優(yōu)于通用數(shù)據(jù)庫和其他 Key-Value存儲(chǔ)方案。