[發明專利]一種基于LSM樹的動態冪律圖存儲方法

有效

• 申請號: 202110182544.4
• 申請日: 2021-02-08
• 公開（公告）號: CN112817982B
• 公開（公告）日: 2022-09-30
• 發明（設計）人: 劉強;季一木;劉尚東;吳飛;胡林;湯淑寧;劉凱航
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 南京瑞弘專利商標事務所(普通合伙) 32249
• 代理人: 彭雄

本發明公開了一種基于LSM樹的動態冪律圖存儲方法，包括：圖數據動態更新時，統計圖的頂點出度信息，以內存頂點表的形式對大度數頂點和普通頂點進行分離存儲；對大頂點表和普通頂點表，根據冪律分布比例分配內存；當各頂點表的數據量超過閾值時，根據內存分配比例對應的線程數對圖數據進行并發溢寫。本發明能減輕基于冪律分布的圖數據更新頻繁時產生的數據合并開銷和存儲資源浪費等問題，在知識圖譜和圖計算領域具有良好的實用價值和前景。

技術領域

本發明屬于計算機技術領域，具體涉及一種基于LSM樹的動態冪律圖數據存儲方法。

背景技術

近年來，圖計算被越來越多的應用于復雜網絡、深度學習、腦科學及社區發現等領域。隨著圖數據集規模和復雜性不斷增長，如何設計高效的圖存儲機制越來越受到人們的關注。針對該問題，先后出現了如GFS(Google File System)、HDFS(Hadoop File System)等基于鍵值對的PB級分布式文件系統，設計上基于“一次寫多次讀”的設計模式，充分利用了硬盤順序讀取比隨機讀取高效的特點，以提高吞吐率，同時具有較好的可擴展性。

然而，在真實的網絡中，圖數據往往是實時更新的，且在度分布上存在無標度現象，即節點度分布近似服從冪律，如微博意見領袖、網頁權重分級等。HDFS等文件系統基于批處理和追加記錄的方式，難以適應圖數據頻繁更新的需求，導致如數據冗余，合并后重復計算開銷大等問題，也沒有考慮圖數據自身如冪律分布等特點。LSM樹(Log-StructuredMerge Tree)是一種基于日志合并的樹型存儲結構，思想是在內存中對寫操作進行合并，將數據的隨機寫轉換成了順序寫，以提高磁盤寫的吞吐率，主要適用于動態環境下，寫多讀少的應用場景。

發明內容

發明目的：為了解決現有圖存儲技術中存在的問題，本發明提供一種基于LSM樹的動態冪律圖存儲方法，將低度數頂點和大度數頂點分離存儲，并根據圖數據當前度數的冪律分布統計信息分配內存，并配置相應比例的并發溢寫線程數，可以減輕基于冪律分布的圖數據更新頻繁時產生的數據合并開銷和存儲資源浪費等問題，適用于存儲動態圖結構的數據。

技術方案：為實現上述目的，本發明采用的技術方案為：

一種基于LSM樹的動態冪律圖存儲方法，包括：圖數據動態更新時，記錄圖的頂點出度信息，以內存頂點表的形式對大度數頂點和普通頂點進行分離存儲。對大度數頂點表和普通頂點表，根據冪律分布指數分配內存。當各頂點表的數據量超過閾值時，根據內存分配比例對應的線程數對圖數據進行并發寫入，具體包括以下步驟：

步驟201：在LSM樹結構的基礎上，增加用于統計圖數據信息的頂點出度統計表，同時將原有的內存頂點表劃分為大度數頂點表和普通頂點表。

步驟202：圖數據更新時，首先更新WAL日志，然后在頂點出度統計表中更新頂點的統計信息，并根據頂點的出度和統計信息判斷是否為大度數頂點，最后將該頂點對應鍵值對插入大度數頂點表或普通頂點表：大度數頂點的鍵值對插入大度數頂點表，普通頂點的鍵值對插入普通頂點表。

步驟203：當大度數頂點表或普通頂點表內部的圖數據量超過限定的內存閾值時，啟動相應比例的多線程，根據哈希算法對磁盤上的L₀層寫入各分區文件。

優選的：步驟201中的頂點出度統計表，指的是在圖頂點和出度鄰居頂點數量的映射。

優選的：步驟202中根據頂點的出度和統計信息判斷是否為大度數頂點的方法：判定標準為出度鄰居數量大于閾值時，則為大度數頂點，否則為普通頂點。閾值的選擇取決于當前頂點出度統計表中出度的冪律分布比例。

優選的：判斷是否為大度數頂點的閾值k取決于如下冪律公式：

p(k)＝k^-γ

其中，k代表頂點的度，γ為度指數，則p(k)代表度為k的頂點占總頂點數的比例。