摘要：HyG圖計算引擎采用CSR格式來存儲圖的拓撲信息，CSR格式可以將稀疏矩陣的存儲空間壓縮，進而大大降低圖的存儲開銷，同時具備訪問效率高、格式易轉(zhuǎn)化等優(yōu)點。

本文分享自華為云社區(qū)《CSR格式如何更新？ GES圖計算引擎HyG揭秘之?dāng)?shù)據(jù)更新》，作者： π 。

HyG圖計算引擎采用CSR格式來存儲圖的拓撲信息，CSR格式可以將稀疏矩陣的存儲空間壓縮，進而大大降低圖的存儲開銷，同時具備訪問效率高、格式易轉(zhuǎn)化等優(yōu)點。利用CSR + 列存（parquet格式）的組合，HyG獲得了很高的圖訪問性能。但是，對于數(shù)據(jù)需要增量更新的場景，CSR的更新非常困難，可能會導(dǎo)致大量的數(shù)據(jù)復(fù)制和移動，進而影響系統(tǒng)性能。HyG對傳統(tǒng)CSR更新進行了一系列優(yōu)化，實現(xiàn)了高效的數(shù)據(jù)更新。

什么是CSR格式？

CSR格式是一種常用的稀疏矩陣存儲格式，它將稀疏矩陣以三個數(shù)組的形式存儲。具體來說，CSR格式使用 values、column indices和row offsets三個數(shù)組來表示稀疏矩陣。

定義NNZ（Num-non-zero）為矩陣M中非0元素的個數(shù)。

第一個數(shù)組為values數(shù)組。其中，values數(shù)組的長度為NNZ，分別從左到右從上到下的非零元素的值。

第二個數(shù)組為column數(shù)組。其中，column數(shù)組的長度為NNZ，其對應(yīng)于values數(shù)組中的元素的column_index（例如元素8排列在所在行的第3個位置,因此其column index為2）。

第三個數(shù)組為row offsets，其中row offsets的數(shù)組大小為m+1，其前m個元素分別代表這每一行中第一個非零元素在Values數(shù)組的下標。（例如元素2是第二行的第二個元素，其在values數(shù)組中的下標為2.）。

CSC和CSR類似，只不過和CSR行列互換。values數(shù)組里是按列存的數(shù)值，row offsets變成了col offsets，column數(shù)組變成了row數(shù)組。

CSR格式由于其緊湊的存儲方式和高效的計算方式，已經(jīng)成為了處理稀疏矩陣的標準格式之一。具體來說，CSR格式可以利用連續(xù)的內(nèi)存塊來存儲非零元素，這使得計算機在處理稀疏矩陣時可以跳過大量的零元素，從而提高了計算效率。此外，CSR格式所需要的存儲空間相對于其他格式，如COO格式（Coordinate）等，也更為緊湊，這在處理大型稀疏矩陣時非常有利。

如何更新CSR格式數(shù)據(jù)？

傳統(tǒng)方案：

更新圖數(shù)據(jù)需要對三個數(shù)組進行操作：values、columns和row offset。

更新

要更新矩陣中某個位置（i，j）的值，需要找到該位置在CSR格式中對應(yīng)的行（第i行）在values和columns數(shù)組中的起始和結(jié)束索引。具體而言，該行的非零元素在values數(shù)組中的起始位置是row offset [i]，結(jié)束位置是row offset [i+1]-1。然后，在columns數(shù)組中找到對應(yīng)的列（第j列）的索引位置。

接下來，可以直接更新values數(shù)組中對應(yīng)位置的值，即values[row offset[i]+k]，其中k是columns數(shù)組中第j列的索引位置。

插入

如果要插入一個新的非零元素，可以按照以下步驟進行：

1、找到要插入的元素在CSR格式中對應(yīng)的行（第i行）在values和columns數(shù)組中的起始和結(jié)束索引，方法同上。

2、在columns數(shù)組中找到新元素應(yīng)該插入的位置，即找到插入元素后columns數(shù)組中第j列的索引位置。

3、將新元素的值插入到values數(shù)組中正確的位置，并將columns數(shù)組中對應(yīng)位置以及后面的元素向后移動一個位置。

4、更新row offset數(shù)組中第i行及其后面所有行的元素起始位置，因為在第i行插入了一個新的非零元素。

刪除

如果要刪除一個非零元素，可以按照以下步驟進行：

1、找到要刪除的元素在CSR格式中對應(yīng)的行（第i行）在values和columns數(shù)組中的起始和結(jié)束索引，方法同上。

2、在columns數(shù)組中找到要刪除的元素的位置。

3、從values和columns數(shù)組中刪除該元素，并將后面的元素向前移動一個位置。

4、更新row offset數(shù)組中第i行及其后面所有行的元素起始位置，因為在第i行刪除了一個非零元素。

需要注意的是，更新CSR格式中的元素可能會導(dǎo)致數(shù)組長度的變化，因此需要動態(tài)分配和釋放內(nèi)存空間。此外，在進行插入和刪除操作時，可能需要對row offset數(shù)組中的元素進行更新，這可能會影響CSR格式的性能。

總之，CSR格式的更新操作相對復(fù)雜，需要對三個數(shù)組進行操作，并需要考慮內(nèi)存分配和數(shù)組長度的變化等問題，這十分不利于實時分批式的增量更新。

HyG數(shù)據(jù)更新策略

• 每次更新都會生成一個子圖（delta_graph），這個子圖是CSR格式，描述了增量信息。
• 引入deleted_biset數(shù)組，記錄被刪除的點、邊信息。
• 按順序加載 MergedPG = pg + [delta_graph]
• 對各點、邊按照所屬的pg/ delta_graph進行本地訪問和增、刪。

因為HyG考慮了分布式切分圖的場景，我們將場景簡化，接下來描述一下數(shù)據(jù)更新的流程。

圖原始數(shù)據(jù)如下圖所示，圖中包含4個點，4條邊，4條邊上的值分別為1、7、2、8。

圖對應(yīng)的CSR格式如下圖所示，這個是原始的拓撲數(shù)據(jù)。

我們對數(shù)據(jù)進行更新，基于原始圖新增了邊0(src)->3(dst)，邊的值為3。刪除了邊1(src)->2(dst)，邊的值為8。

新增了1條邊，邊的src是0，dst是3，因此CSR的row offset為[1 1 1 1]，column為[3]，value為[3]。進而得到了右側(cè)的delta graph。

刪除了1條邊，這條邊是屬于pg（原始圖），所以，我們會對pg的deleted_bitset置位，因為刪除是column數(shù)組的最后一個，因此，我們會將最后一個bit置為1，表示這個邊已被刪除。

到此，我們就完成了一次增、刪操作，生成了一個新的delta graph，這個delta graph跟歷史數(shù)據(jù)沒有任何關(guān)系，它只表示了本次增量的數(shù)據(jù)，因此，對于超大規(guī)模的圖，更新數(shù)據(jù)不再需要大量的數(shù)據(jù)拷貝和移動，只需要生成一個很小的delta graph就可以了。

圖訪問

經(jīng)過增量更新，全量圖的信息就會被分解為一個原始圖和一個增量圖。HyG設(shè)計了一種同時讀取到兩個圖信息的訪問迭代器（以下簡稱“二級迭代器”），這種迭代器會將這多個子圖視為一個全量圖訪問，可以在不同的子圖間游走。

HyG增量圖迭代性能優(yōu)化

HyG增量圖會產(chǎn)生多個快照，每個快照是一個子圖，對應(yīng)著一次commit。算法讀取增量圖需要依賴HyG的二級迭代器，迭代器會在不同的快照間游走，校驗點、邊是否已被刪除，最終返回給算法結(jié)果。因此，迭代器需要維護很多信息，遠遠大于pg（原始圖）的輕量級迭代器，進而使增量圖迭代的性能很低，快照數(shù)量越多性能下降越劇烈。

優(yōu)化方案

HyG引入基于頁的快照索引技術(shù)來緩解由于存在大量快照導(dǎo)致的性能下降問題。

為每個快照劃分虛擬頁，比如頁的大小是4K，那么一個頁對應(yīng)著4K個點以及這4k點對應(yīng)的邊。

索引表記錄了每個頁最近被更新的快照，因此，如果這個頁沒有被更新，那么利用索引表可以直接跳過對應(yīng)的快照。

索引表采用copy on write的方式更新，每生成一個新快照，會把上一個快照的全部索引信息copy一份，然后把修改信息更新到對應(yīng)的索引上，得到最新快照的索引表。

同時，對于二級迭代器的構(gòu)造，我們也進行了優(yōu)化，盡量減少數(shù)據(jù)成員的數(shù)量，當(dāng)?shù)髟诓煌煺臻g切換時，去更新該快照的上下文信息，而不會維護所有快照的信息。

利用快照索引技術(shù)，我們可以快速的定位到點、邊對應(yīng)的最新修改的快照，進而可以跳過很多無效的訪問。但是，隨著快照數(shù)量的增多，圖遍歷的性能還是會不斷下降，被刪除的點、邊不但浪費了大量的存儲空間，還會增加無效的訪問延時，因此，設(shè)計一套有效的自動化合并方案，當(dāng)快照數(shù)量過多或者刪除點、邊過多時，觸發(fā)合并，提升系統(tǒng)性能。如果大家感興趣，我們后面會接著介紹HyG是如何實現(xiàn)快照合并的。

?

點擊關(guān)注，第一時間了解華為云新鮮技術(shù)~文章來源地址http://www.zghlxwxcb.cn/news/detail-492012.html

到了這里，關(guān)于CSR格式如何更新？ GES圖計算引擎HyG揭秘之?dāng)?shù)據(jù)更新的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！