基于二級索引結(jié)構(gòu)的圖壓縮算法

李高超，李犇，盧毓海，劉夢雅，劉燕兵

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

1 引言

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

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

2 二級索引圖壓縮算法

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

2.1 屬性查詢

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) for C中的每一個元素 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中的每一個元素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é)點的屬性查詢和邊的屬性查詢 2種。當進行節(jié)點屬性查詢時，查詢的Key值為節(jié)點ID；當進行邊的屬性查詢時，查詢的Key值為＜u,v＞，其中，u為邊的起始節(jié)點ID，v為邊的結(jié)束節(jié)點ID，GComIdx將u和v的ID轉(zhuǎn)換為二進制后組合成一個64位的長整型Key。獲得查詢Key值后，GComIdx在有序的Key值數(shù)組上進行二分查找。

2.2 相鄰節(jié)點查詢

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

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

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

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

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

3 實驗評估

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

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

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

3.2 評價標準

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

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

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

表1 存儲方案初始化時間

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

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

3.4 索引存儲空間比較

實驗數(shù)據(jù)集在各個存儲方案初始化處理后占用的磁盤空間如表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ù)據(jù)量。

表2 存儲方案磁盤空間

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

3.5 查詢效率比較

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

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

圖5 存儲方案查詢時間

4 結(jié)束語

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