摘要：HyG圖計算引擎採用CSR格式來存儲圖的拓撲信息，CSR格式可以將稀疏矩陣的存儲空間壓縮，進而大大降低圖的存儲開銷，同時具備訪問效率高、格式易轉化等優點。 本文分享自華為雲社區《CSR格式如何更新？ GES圖計算引擎HyG揭秘之數據更新》，作者： π 。 HyG圖計算引擎採用CSR格式來存儲圖 ...
摘要：HyG圖計算引擎採用CSR格式來存儲圖的拓撲信息，CSR格式可以將稀疏矩陣的存儲空間壓縮，進而大大降低圖的存儲開銷，同時具備訪問效率高、格式易轉化等優點。
本文分享自華為雲社區《CSR格式如何更新？ GES圖計算引擎HyG揭秘之數據更新》，作者： π 。
HyG圖計算引擎採用CSR格式來存儲圖的拓撲信息，CSR格式可以將稀疏矩陣的存儲空間壓縮，進而大大降低圖的存儲開銷，同時具備訪問效率高、格式易轉化等優點。利用CSR + 列存（parquet格式）的組合，HyG獲得了很高的圖訪問性能。但是，對於數據需要增量更新的場景，CSR的更新非常困難，可能會導致大量的數據複製和移動，進而影響系統性能。HyG對傳統CSR更新進行了一系列優化，實現了高效的數據更新。
什麼是CSR格式？
CSR格式是一種常用的稀疏矩陣存儲格式，它將稀疏矩陣以三個數組的形式存儲。具體來說，CSR格式使用 values、column indices和row offsets三個數組來表示稀疏矩陣。
定義NNZ（Num-non-zero）為矩陣M中非0元素的個數。
第一個數組為values數組。其中，values數組的長度為NNZ，分別從左到右從上到下的非零元素的值。
第二個數組為column數組。其中，column數組的長度為NNZ，其對應於values數組中的元素的column_index（例如元素8排列在所在行的第3個位置,因此其column index為2）。
第三個數組為row offsets，其中row offsets的數組大小為m+1，其前m個元素分別代表這每一行中第一個非零元素在Values數組的下標。（例如元素2是第二行的第二個元素，其在values數組中的下標為2.）。
CSC和CSR類似，只不過和CSR行列互換。values數組裡是按列存的數值，row offsets變成了col offsets，column數組變成了row數組。
CSR格式由於其緊湊的存儲方式和高效的計算方式，已經成為了處理稀疏矩陣的標準格式之一。具體來說，CSR格式可以利用連續的記憶體塊來存儲非零元素，這使得電腦在處理稀疏矩陣時可以跳過大量的零元素，從而提高了計算效率。此外，CSR格式所需要的存儲空間相對於其他格式，如COO格式（Coordinate）等，也更為緊湊，這在處理大型稀疏矩陣時非常有利。
如何更新CSR格式數據？
傳統方案：
更新圖數據需要對三個數組進行操作：values、columns和row offset。
更新
要更新矩陣中某個位置（i，j）的值，需要找到該位置在CSR格式中對應的行（第i行）在values和columns數組中的起始和結束索引。具體而言，該行的非零元素在values數組中的起始位置是row offset [i]，結束位置是row offset [i+1]-1。然後，在columns數組中找到對應的列（第j列）的索引位置。
接下來，可以直接更新values數組中對應位置的值，即values[row offset[i]+k]，其中k是columns數組中第j列的索引位置。
插入
如果要插入一個新的非零元素，可以按照以下步驟進行：
1、找到要插入的元素在CSR格式中對應的行（第i行）在values和columns數組中的起始和結束索引，方法同上。
2、在columns數組中找到新元素應該插入的位置，即找到插入元素後columns數組中第j列的索引位置。
3、將新元素的值插入到values數組中正確的位置，並將columns數組中對應位置以及後面的元素向後移動一個位置。
4、更新row offset數組中第i行及其後面所有行的元素起始位置，因為在第i行插入了一個新的非零元素。
刪除
如果要刪除一個非零元素，可以按照以下步驟進行：
1、找到要刪除的元素在CSR格式中對應的行（第i行）在values和columns數組中的起始和結束索引，方法同上。
2、在columns數組中找到要刪除的元素的位置。
3、從values和columns數組中刪除該元素，並將後面的元素向前移動一個位置。
4、更新row offset數組中第i行及其後面所有行的元素起始位置，因為在第i行刪除了一個非零元素。
需要註意的是，更新CSR格式中的元素可能會導致數組長度的變化，因此需要動態分配和釋放記憶體空間。此外，在進行插入和刪除操作時，可能需要對row offset數組中的元素進行更新，這可能會影響CSR格式的性能。
總之，CSR格式的更新操作相對複雜，需要對三個數組進行操作，並需要考慮記憶體分配和數組長度的變化等問題，這十分不利於實時分批式的增量更新。
HyG數據更新策略
- 每次更新都會生成一個子圖（delta_graph），這個子圖是CSR格式，描述了增量信息。
- 引入deleted_biset數組，記錄被刪除的點、邊信息。
- 按順序載入 MergedPG = pg + [delta_graph]
- 對各點、邊按照所屬的pg/ delta_graph進行本地訪問和增、刪。
因為HyG考慮了分散式切分圖的場景，我們將場景簡化，接下來描述一下數據更新的流程。
圖原始數據如下圖所示，圖中包含4個點，4條邊，4條邊上的值分別為1、7、2、8。
圖對應的CSR格式如下圖所示，這個是原始的拓撲數據。
我們對數據進行更新，基於原始圖新增了邊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]。進而得到了右側的delta graph。
刪除了1條邊，這條邊是屬於pg（原始圖），所以，我們會對pg的deleted_bitset置位，因為刪除是column數組的最後一個，因此，我們會將最後一個bit置為1，表示這個邊已被刪除。
到此，我們就完成了一次增、刪操作，生成了一個新的delta graph，這個delta graph跟歷史數據沒有任何關係，它只表示了本次增量的數據，因此，對於超大規模的圖，更新數據不再需要大量的數據拷貝和移動，只需要生成一個很小的delta graph就可以了。
圖訪問
經過增量更新，全量圖的信息就會被分解為一個原始圖和一個增量圖。HyG設計了一種同時讀取到兩個圖信息的訪問迭代器（以下簡稱“二級迭代器”），這種迭代器會將這多個子圖視為一個全量圖訪問，可以在不同的子圖間游走。
HyG增量圖迭代性能優化
HyG增量圖會產生多個快照，每個快照是一個子圖，對應著一次commit。演算法讀取增量圖需要依賴HyG的二級迭代器，迭代器會在不同的快照間游走，校驗點、邊是否已被刪除，最終返回給演算法結果。因此，迭代器需要維護很多信息，遠遠大於pg（原始圖）的輕量級迭代器，進而使增量圖迭代的性能很低，快照數量越多性能下降越劇烈。
優化方案
HyG引入基於頁的快照索引技術來緩解由於存在大量快照導致的性能下降問題。
為每個快照劃分虛擬頁，比如頁的大小是4K，那麼一個頁對應著4K個點以及這4k點對應的邊。
索引表記錄了每個頁最近被更新的快照，因此，如果這個頁沒有被更新，那麼利用索引表可以直接跳過對應的快照。
索引表採用copy on write的方式更新，每生成一個新快照，會把上一個快照的全部索引信息copy一份，然後把修改信息更新到對應的索引上，得到最新快照的索引表。
同時，對於二級迭代器的構造，我們也進行了優化，儘量減少數據成員的數量，當迭代器在不同快照間切換時，去更新該快照的上下文信息，而不會維護所有快照的信息。
利用快照索引技術，我們可以快速的定位到點、邊對應的最新修改的快照，進而可以跳過很多無效的訪問。但是，隨著快照數量的增多，圖遍歷的性能還是會不斷下降，被刪除的點、邊不但浪費了大量的存儲空間，還會增加無效的訪問延時，因此，設計一套有效的自動化合併方案，當快照數量過多或者刪除點、邊過多時，觸發合併，提升系統性能。如果大家感興趣，我們後面會接著介紹HyG是如何實現快照合併的。
