在進(jìn)行各種圖處理、圖計(jì)算、圖查詢的時(shí)候,內(nèi)存或是硬盤中如何存儲(chǔ)圖結(jié)構(gòu)是一個(gè)影響性能的關(guān)鍵因素。本文主要分析了幾種常見(jiàn)的內(nèi)存圖結(jié)構(gòu),及其時(shí)間、空間復(fù)雜度,希望對(duì)你有所啟發(fā)。 通常來(lái)說(shuō),對(duì)于圖結(jié)構(gòu)的幾種常見(jiàn)的基礎(chǔ)操作:
插入一個(gè)點(diǎn)
插入一個(gè)邊
刪除一個(gè)邊
刪除一個(gè)點(diǎn)的全部鄰邊
找到一個(gè)點(diǎn)的全部鄰邊
找到一個(gè)點(diǎn)的另一個(gè)鄰點(diǎn)
全圖掃描
獲取一個(gè)點(diǎn)的入度或者出度
這些圖相關(guān)的操作,除了要關(guān)心時(shí)間復(fù)雜度之外,需要考慮空間占用的問(wèn)題。 對(duì)于大多數(shù)實(shí)時(shí)讀寫型的系統(tǒng),增刪改查的性能問(wèn)題會(huì)比較重要,它們比較關(guān)注上面 1-6 的操作;對(duì)于部分密集計(jì)算的系統(tǒng),對(duì)批量讀取的性能會(huì)比較重視,側(cè)重上面 5-8 的操作。 不過(guò)遺憾的是,無(wú)論是常規(guī)的圖查詢,還是進(jìn)階的圖計(jì)算,根據(jù) RUM 猜想[1],讀快、寫快、又省空間這樣”既要又要也要”的好事是不存在的。 下面,我們介紹幾個(gè)數(shù)據(jù)結(jié)構(gòu)并給出少量的定量分析。 我們先從三個(gè)典型的方案(鄰接矩陣、壓縮稀疏矩陣和鄰接表)說(shuō)起,再介紹幾種近幾年的研究的變種結(jié)構(gòu) PCSR、VCSR、CSR++。
鄰接矩陣 Adjacency Matrix ?
用矩陣來(lái)表示圖結(jié)構(gòu)是大學(xué)里數(shù)據(jù)結(jié)構(gòu)課程中都學(xué)過(guò)的知識(shí),也是一種非常直觀的辦法。 點(diǎn) i 與點(diǎn) j 之間有一條邊,等價(jià)對(duì)應(yīng)于矩陣上 $M_{ij}$ 為 1。當(dāng)然,這里的點(diǎn) ID 是需要連續(xù)排列無(wú)空洞。 用矩陣來(lái)表示圖結(jié)構(gòu)有明顯的好處,可以復(fù)用大量線性代數(shù)的研究成果:比如圖上模式匹配類的問(wèn)題等價(jià)于矩陣的相乘。 下面是一個(gè)模式匹配問(wèn)題,它的大體意思是在全圖上尋找這樣一種圖結(jié)構(gòu):
?
Match?(src)-[friend?*?2..4]->(fof) WHERE?src.age?>?30 RETURN?fof?
?
?
對(duì)于這樣一個(gè)問(wèn)題可以直接對(duì)應(yīng)右邊的矩陣操作:
比如,2 跳遍歷等價(jià)于矩陣 F 自乘;2 - 4 跳遍歷分別等價(jià)于 F2、F3、F^4;取屬性等價(jià)于乘以一個(gè)過(guò)濾矩陣。
?
更進(jìn)一步,由于矩陣操作是天生可以分塊并行加速,這在性能上有極大的優(yōu)勢(shì)。 下面,我們對(duì)鄰接矩陣操作進(jìn)行一個(gè)簡(jiǎn)單的定量分析
?
操作 | 時(shí)間復(fù)雜度 | 備注 |
---|---|---|
插入一個(gè)點(diǎn) | O(n^2) | 對(duì)于矩陣來(lái)說(shuō),增加一個(gè)點(diǎn)意味著整個(gè)矩陣的維度增加,通常需要另外開(kāi)辟一塊空間 |
插入一個(gè)邊 | O(1) | 增加一個(gè)邊只是將對(duì)應(yīng)的位置置 1 |
刪除一個(gè)邊 | O(1) | 置0 |
刪除一個(gè)點(diǎn)的全部鄰邊 | O(n) | 對(duì)于某個(gè)點(diǎn)所有出邊的刪除對(duì)應(yīng)某一行的置0。入邊對(duì)應(yīng)某一列,可以批量操作 |
找到一個(gè)點(diǎn)的全部鄰邊 | O(n) | ? |
找到一個(gè)點(diǎn)的給定鄰點(diǎn) | O(1) | ? |
全圖掃描 | O(n^2) | ? |
?
其中,n=|V|,m=|E|。
優(yōu)化上,批量操作(CPU Cache/SSD block)可以線性增加性能,例如 O(n) 可以降低到 O(n/B),但不影響定量分析。
由于絕大多數(shù)圖結(jié)構(gòu)是極其稀疏的,因此簡(jiǎn)單用鄰接矩陣來(lái)表示圖結(jié)構(gòu),其內(nèi)存會(huì)有夸張的浪費(fèi)。更為嚴(yán)重的是,當(dāng)有多種邊類型時(shí),每種邊類型各需要一個(gè)鄰接矩陣。這使得裸用矩陣在實(shí)際情況中只能處理很小數(shù)據(jù)量的場(chǎng)景。當(dāng)然,對(duì)于現(xiàn)代服務(wù)器動(dòng)輒幾百 G 的內(nèi)存,如果只有幾億點(diǎn)邊的數(shù)據(jù)量,像是 twitter2010,這并不會(huì)是很嚴(yán)重的問(wèn)題。但大多數(shù)情況下,條件允許的話,大家還是希望找到一些更加經(jīng)濟(jì)的結(jié)構(gòu)。
壓縮稀疏矩陣 CSR/CSC ?
壓縮稀疏矩陣是一種非常流行和緊湊的圖結(jié)構(gòu)表示方式,大多數(shù)圖計(jì)算系統(tǒng)都采用 CSR。
?
這里簡(jiǎn)單介紹一下 CSR 的結(jié)構(gòu):
對(duì)于點(diǎn) IDx,取鄰居 ID 就是 F[N[x]] 到 F[N[x+1]-1]。
例如,查找點(diǎn) ID2 的鄰居,對(duì)應(yīng)為 F[N[2]] 到 F[N[2+1]-1],對(duì)應(yīng)到上圖也即 1 6 8。查找點(diǎn) ID7 的鄰居,對(duì)應(yīng)為 F[N[7]] 到 F[N[7+1]-1],也就是 2 和 4。
另外,CSR 記錄的僅是出邊的信息,如果要考慮入邊就使用 CSC,其原理是類似的。
?
操作 | 時(shí)間復(fù)雜度 | 備注 |
---|---|---|
插入一個(gè)點(diǎn) | O(1) | 在點(diǎn)矢量尾部增加 |
插入一個(gè)邊 ,v> | O(m+n) | 邊矢量,從 u 對(duì)應(yīng)的鄰居開(kāi)始,都向后移動(dòng)一位;點(diǎn)矢量,從 u 對(duì)應(yīng)位置開(kāi)始每個(gè)值加 1 |
刪除一個(gè)邊 | O(m+n) | 插入邊的逆過(guò)程 |
刪除一個(gè)點(diǎn) v 的全部鄰邊 | O(m+n) | 邊矢量移動(dòng) deg(v) 位,點(diǎn)矢量 u 對(duì)應(yīng)位置置 0 |
找到一個(gè)點(diǎn)的全部鄰邊 | O(deg(v)) | ? |
找到一個(gè)點(diǎn)的給定鄰點(diǎn) | O(log(deg(v))) | deg(v) 內(nèi)的排序查找 |
全圖掃描 | O(m+n) | ? |
?
CSR 的空間占用是 O(|V|+|E|),在空間節(jié)省和順序查找上是極其高效的。但在大量插入時(shí),壓縮稀疏矩陣和鄰接矩陣一樣,需要重新開(kāi)辟空間,效率很低。所以,它適合于計(jì)算密集場(chǎng)景但不適合增改頻繁的場(chǎng)景。
CSR 還有一個(gè)顯著的優(yōu)點(diǎn)是可以快速獲取每個(gè)點(diǎn)的出入度,只要計(jì)算 N[x+1]-N[x],這在判斷一些點(diǎn)是否為超級(jí)節(jié)點(diǎn)時(shí)很方便。如果不是稀疏矩陣的話,通常會(huì)用另外一個(gè)單獨(dú)的結(jié)構(gòu)來(lái)記錄出入度。
此外,CSR 不容易實(shí)現(xiàn)并發(fā)修改,其每次插入都需要對(duì)兩個(gè)矢量進(jìn)行位移,這并不高效。
鄰接鏈表 Adjacency List ?
和基于矩陣的方式不同,鄰接鏈表 AL 空間上有優(yōu)勢(shì),但對(duì)于邊的讀寫上會(huì)略微慢一點(diǎn)(指針在內(nèi)存中不能連續(xù)移動(dòng))。AL 的做法是把鄰邊(出邊)用 list 或者有序 list 的方式串連起來(lái)。由此延伸的一個(gè)變種是鄰邊從 list 改為 array。
?
操作 | 時(shí)間復(fù)雜度 | 備注 |
---|---|---|
插入一個(gè)點(diǎn) | O(1) | 尾插入 |
插入一個(gè)邊 ,v> | O(log(deg(u))) | 有序 list |
刪除一個(gè)邊 | O(log(deg(u))) | ? |
刪除一個(gè)點(diǎn) v 的全部鄰邊 | O(1) | ? |
找到一個(gè)點(diǎn)的全部鄰邊 | O(deg(u)) | ? |
找到一個(gè)點(diǎn)的給定鄰點(diǎn) | O(log(deg(u))) | ? |
全圖掃描 | O(n+m) | ? |
?
AL 相比 CSR 通常不能直接獲得點(diǎn)的出入度,可以通過(guò)可以單獨(dú)維護(hù)一個(gè)字段實(shí)現(xiàn)該功能。
此外,鄰接表并不需要 ID 連續(xù)排布,對(duì)于頻繁增刪點(diǎn)的場(chǎng)景特別友好。AL 對(duì)于并發(fā)修改的支持也更友好,天然在點(diǎn)級(jí)別有并行度。當(dāng)然,對(duì)于超級(jí)節(jié)點(diǎn),直接用 list 的方式,還是會(huì)有些性能的問(wèn)題要考慮;優(yōu)化上可能會(huì)進(jìn)一步改造成 Blocked list 的方式,可以帶來(lái)更好的數(shù)據(jù)局部性和細(xì)顆粒度。
由于 ID 不用嚴(yán)格連續(xù)排布,AL 的一個(gè)常見(jiàn)變種就是 Tree。
Tree ?
在這種結(jié)構(gòu)中,一個(gè)點(diǎn)和其所有的鄰邊被建模成了 key-value,key 是點(diǎn) ID,value 是所有鄰邊的編碼。Key 通過(guò) Tree 的方式組織在一起。這里的樹(shù)可以是 B-Tree 等各變種 Tree。雖然本文沒(méi)有討論圖屬性,但 value 中也是可以存放 value。
?
操作 | 時(shí)間復(fù)雜度 | 備注 |
---|---|---|
插入一個(gè)點(diǎn) | O(log(n)) | ? |
插入一個(gè)邊 ,v> | O(deg(u) log(n)) | ? |
刪除一個(gè)邊 | O(deg(u) log(n)) | ? |
刪除一個(gè)點(diǎn) v 的全部鄰邊 | O(log(n)) | ? |
找到一個(gè)點(diǎn)的全部鄰邊 | O(deg(u) log(n)) | ? |
找到一個(gè)點(diǎn)的給定鄰點(diǎn) | O(log(n deg(u)) | ? |
全圖掃描 | O(n+m) | ? |
?
為了控制訪問(wèn)顆粒度,每個(gè)葉子通常會(huì)被限定為固定的大?。?yè))。這就是在數(shù)據(jù)庫(kù)類系統(tǒng)里面最常見(jiàn)的辦法 B-tree。為了增改方便,也可以把每頁(yè)的 in-place update 改成 Copy-On-Write 的方式;一個(gè)典型的代表就是 LLAMA[2],但這種多版本的讀取通常會(huì)需要更多的空間,并且當(dāng)有大量累積修改時(shí),需要定期的多版本合并以降低跨快照讀。某種程度上,它和 LSM-Tree 的思路有些接近。
基于 CSR 的變種 PCSR 和 VCSR ?
由于 CSR 在空間和讀性能上有很大的優(yōu)勢(shì),但在插入時(shí)的耗時(shí)和空間上都很弱,因此本節(jié)幾個(gè)變種的主要目的都是為了改善其弱項(xiàng),大體思路都是分塊和 buffer。
在 CSR 的邊矢量進(jìn)行增刪時(shí)可以注意到,主要耗時(shí)是在對(duì)于矢量的元素位移上。因此,一個(gè)直觀的思路是預(yù)留一些插入空白位,在刪除時(shí)也不立刻回收這些空白。
而分塊思想,是指將一些局部數(shù)據(jù)放在同一個(gè)分塊內(nèi),例如 Tree 中每個(gè) page 就是一種分塊的方式。與此對(duì)應(yīng)的是,buffer 空白之間的連續(xù)區(qū)域。
PCSR
PCSR [3]的基本思想是:對(duì)于點(diǎn)矢量,其元素從一個(gè)值改為對(duì)應(yīng)邊矢量中對(duì)應(yīng)鄰邊位置的?<起點(diǎn),終點(diǎn)>。而對(duì)于邊矢量,在這些分塊所對(duì)應(yīng)邊界放置哨兵 sentinel,上圖中的 S,上圖的 “-”?對(duì)應(yīng)預(yù)留插入位置留空。
事實(shí)上,原文中,對(duì)于邊矢量,其本質(zhì)是實(shí)現(xiàn)為一個(gè) B-Tree,本文先簡(jiǎn)化成一個(gè) Array。?
?
操作 | 時(shí)間復(fù)雜度 | 備注 |
---|---|---|
插入一個(gè)點(diǎn) | O(1) | 直接在點(diǎn)矢量和邊矢量的尾插入 |
插入一個(gè)邊 ,v> | O(log(deg(u)) | 邊矢量對(duì)應(yīng)分片的二分+空位查找 |
刪除一個(gè)邊 | O(log(deg(u)) | ? |
刪除一個(gè)點(diǎn)v的全部鄰邊 | O(1) | 邊矢量對(duì)應(yīng)分片置空,點(diǎn)矢量對(duì)應(yīng) ID 位置置空 |
找到一個(gè)點(diǎn)的全部鄰邊 | O(deg(u)) | ? |
找到一個(gè)點(diǎn)的給定鄰點(diǎn) | O(log(deg(u)) | ? |
全圖掃描 | O(n+m) | ? |
?
可以看到,PCSR 的預(yù)留位置多少都是需要重平衡,不能過(guò)多也不能不足。特別是大批量增刪時(shí),對(duì)預(yù)留位置的處理會(huì)是一個(gè)較重的操作。
此外,如果把 PMA 的 B-Tree 以及需要 rebalance 的本質(zhì)考慮進(jìn)去,其和前述 Tree 方式的區(qū)別并不是很大。
? ? ? VCSR
VCSR[4]主要是對(duì) PCSR 的一個(gè)改進(jìn),其樸素思想是 PCSR 的留空是均勻的,而大多數(shù)圖結(jié)構(gòu)的出入度,是存在 20-80 這樣的冪率特征,而 PCSR 的一個(gè)主要痛點(diǎn)是頻繁的 rebalance。VCSR 的做法是為每個(gè)分塊預(yù)留空間正比于其分塊內(nèi)的點(diǎn)的數(shù)量,即:邊矢量中,一個(gè)分塊內(nèi),如果點(diǎn)的數(shù)量多,就多預(yù)留一些空位。在直覺(jué)上,點(diǎn)數(shù)量多時(shí),其分塊對(duì)應(yīng)的邊插入會(huì)更多一些,這樣可以減少 rebalance 的頻率。
此外,VCSR 還有些版本號(hào)之類的優(yōu)化。 ? ? ? CSR++
事實(shí)上,CSR++[5]在設(shè)計(jì)上其實(shí)更接近一種 AL/Tree 的變種,而不是 CSR。它主要有三個(gè)方面的優(yōu)化:
第一,對(duì)于 Vertex Array 再分段,將一個(gè)大的 Array 拆成多段,這樣可以有更細(xì)的讀寫顆粒度。通過(guò)?段 ID + 點(diǎn) ID?來(lái)定位每個(gè)點(diǎn)和其鄰邊。第二,Vertex Array 中每個(gè)元素,除了記錄點(diǎn) ID 之外,對(duì)于鄰邊數(shù)量很少的點(diǎn),直接把鄰居 ID 也對(duì)齊地塞 inline 進(jìn)去。
對(duì)于大多數(shù)的點(diǎn),其鄰邊就不需要單獨(dú)的 Edge Array 來(lái)存儲(chǔ)了。
可以看到這種方式在圖比較稀疏的時(shí)候,對(duì)于 CPU Cache 掃描是很友好的。
第三,對(duì)于每個(gè)點(diǎn)的鄰邊,采用copy-on-write、標(biāo)記刪除等常見(jiàn)的優(yōu)化辦法,構(gòu)建成類似?std::vector?結(jié)構(gòu)。
?
?
小結(jié) ?
最后,由于在圖查詢、圖存儲(chǔ)和圖計(jì)算不同場(chǎng)景下,對(duì)于圖結(jié)構(gòu)的讀寫掃描和生命周期都有些不同的要求,不同的數(shù)據(jù)結(jié)構(gòu)也有不同的優(yōu)劣。
當(dāng)然,本文只是討論了圖結(jié)構(gòu)可以放在內(nèi)存中的情況。當(dāng)不得不把部分?jǐn)?shù)據(jù)放在硬盤上時(shí),問(wèn)題就完全不同了。當(dāng)然本文也沒(méi)有討論不同 CPU 對(duì)于不同距離內(nèi)存的性能差異 NUMA,或者跨進(jìn)程通信帶來(lái)的影響。
延伸閱讀 ?
最后,我們來(lái)了解下在圖計(jì)算/圖算法上的圖操作。
圖算法中的圖操作 在圖計(jì)算中,存在多種圖結(jié)構(gòu)算法,可能會(huì)涉及多種基礎(chǔ)操作。 中心性 Centrality Algorithms,一種衡量一個(gè)節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)圖中所在中心程度的算法,包括:度中心性、接近中心性、介數(shù)中心性等,會(huì)涉及“找到一個(gè)點(diǎn)的全部鄰邊”、“找到一個(gè)點(diǎn)的另一個(gè)鄰點(diǎn)”、“全圖掃描”的操作組合。
度中心性通過(guò)節(jié)點(diǎn)的度數(shù),即關(guān)聯(lián)的邊數(shù)來(lái)刻畫節(jié)點(diǎn)的受歡迎程度,這將會(huì)要求找到一個(gè)點(diǎn)的所有鄰邊。
接近中心性,通過(guò)計(jì)算每個(gè)節(jié)點(diǎn)到全圖其他所有節(jié)點(diǎn)的路徑和來(lái)刻畫節(jié)點(diǎn)與其他所有節(jié)點(diǎn)的關(guān)系密切程度,這將會(huì)要求進(jìn)行全圖掃描,查找點(diǎn)和圖中所有點(diǎn)的路徑信息。
介數(shù)中心性,則用于衡量一個(gè)頂點(diǎn)出現(xiàn)在其他任意兩個(gè)頂點(diǎn)對(duì)之間最短路徑上的次數(shù),從而來(lái)刻畫節(jié)點(diǎn)的重要性,這將會(huì)要求進(jìn)行全圖掃描,找到一個(gè)點(diǎn)和它的鄰點(diǎn)及路徑信息
PageRank,又稱網(wǎng)頁(yè)排名、谷歌左側(cè)排名,是一種由搜索引擎根據(jù)網(wǎng)頁(yè)之間相互的超鏈接計(jì)算的技術(shù)作為網(wǎng)頁(yè)排名的要素之一的排名方法。它以 Google 公司創(chuàng)辦人拉里·佩奇 Larry Page 之姓來(lái)命名。Google 用它來(lái)體現(xiàn)網(wǎng)頁(yè)的相關(guān)性和重要性,在搜索引擎優(yōu)化操作中是經(jīng)常被用來(lái)評(píng)估網(wǎng)頁(yè)優(yōu)化的成效因素之一。一般來(lái)說(shuō),PageRank 的值越高,表示其被很多其他網(wǎng)頁(yè)鏈接到,說(shuō)明它的重要性很高;而如果一個(gè) PageRank 很高的網(wǎng)頁(yè)鏈接到其他網(wǎng)頁(yè),被鏈接的網(wǎng)頁(yè)的 PageRank值也會(huì)隨之提高。PageRank 的計(jì)算過(guò)程如下: 假設(shè)由 4 個(gè)網(wǎng)頁(yè)組成的集合:A、B、C、D,每個(gè)頁(yè)面的初始 PageRank 值相同,為了滿足概率值為 0-1 之間,假設(shè)這個(gè)值為 0.25。 如果所有頁(yè)面都只鏈接至 A,如下圖,則 A 點(diǎn)的值將是 B、C、D 的 PageRank 值的和。
倘若是下圖這種圖結(jié)構(gòu):
B 鏈接到 C,D 鏈接到 B 和 C,A 點(diǎn)的值計(jì)算的方式如下:
這里的 2、1、3,分別是 B 點(diǎn)對(duì)外鏈接的 2 條邊,C 點(diǎn)對(duì)外鏈接的 1 條邊,D 點(diǎn)對(duì)外鏈接的 3 條邊。
換句話說(shuō),算法將根據(jù)每個(gè)頁(yè)面連出總數(shù)平分該頁(yè)面的 PR 值,并將其加到其所指向的頁(yè)面:
最后,所有這些 PR 值被換算成百分比形式再乘上一個(gè)修正系數(shù)。
由于“沒(méi)有向外鏈接的網(wǎng)頁(yè)”傳遞出去的 PR 值會(huì)是0,這時(shí)候如果遞歸的話,會(huì)導(dǎo)致指向它的頁(yè)面的 PR 值的計(jì)算結(jié)果同樣為零,所以 PageRank 會(huì)賦給每個(gè)頁(yè)面一個(gè)最小值。
因此,一個(gè)頁(yè)面的 PR 值直接取決于指向它的的頁(yè)面。如果在最初給每個(gè)網(wǎng)頁(yè)一個(gè)隨機(jī)且非零的 PR 值,經(jīng)過(guò)重復(fù)計(jì)算,這些頁(yè)面的 PR 值會(huì)趨向于某個(gè)定值,也就是處于收斂的狀態(tài),即最終結(jié)果。
簡(jiǎn)單來(lái)說(shuō),大多數(shù)迭代圖計(jì)算模型都是基于“找到一個(gè)點(diǎn)的全部鄰邊”、“找到一個(gè)點(diǎn)的另一個(gè)鄰點(diǎn)”操作。
AIGC 小課堂 ?
在 AIGC 小課堂部分,我們會(huì)用 NebulaGraph 接入的 aibot 來(lái)講解下文中的部分概念。你如果對(duì) chatgpt 或者是 aibot 有興趣,可以來(lái)?https://discuss.nebula-graph.com.cn/?向 aibot 提出你的要求。
?
? ? ? ? 參考文獻(xiàn) ?
Athanassoulis, M., Kester, M. S., Maas, L. M., et al. (2016). Designing Access Methods: The RUM Conjecture. In EDBT (pp. 461-466).
Macko, P., Marathe, V. J., Margo, D. W., et al. (2015). Llama: Efficient Graph Analytics Using Large Multiversioned Arrays. In 2015 IEEE 31st International Conference on Data Engineering (pp. 363-374). IEEE.
Wheatman, B., & Xu, H. (2018). Packed Compressed Sparse Row: A Dynamic Graph Representation. In 2018 IEEE High Performance Extreme Computing Conference (HPEC) (pp. 1-7). IEEE.
Islam, A. A. R., Dai, D., & Cheng, D. (2022). VCSR: Mutable CSR Graph Format Using Vertex-Centric Packed Memory Array. In 2022 22nd IEEE International Symposium on Cluster, Cloud and Internet Computing (CCGrid) (pp. 71-80). IEEE.
Firmli, S., Trigonakis, V., Lozi, J. P., et al. (2020). CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure. In 24th International Conference on Principles of Distributed Systems (OPODIS'20).
編輯:黃飛
?
評(píng)論