[發明專利]一種基于NUMA架構的大規模流式圖數據更新方法

有效

• 申請號: 201910368729.7
• 申請日: 2019-05-05
• 公開（公告）號: CN110245135B
• 公開（公告）日: 2021-05-18
• 發明（設計）人: 邵志遠;金海;廖小飛;趙智慧
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/23
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 李智;曹葆青

1.一種基于NUMA架構的大規模流式圖數據更新方法，其特征在于，該方法包括以下步驟：

S1.初始化服務器端的基礎圖數據，并將服務器端完整圖數據各個頂點劃分到不同的NUMA Node；

S2.服務器端接收客戶端發送的更新批次，并依次將更新批次加入請求隊列；

S3.服務器端從請求隊列取出待處理更新批次，按照源節點將該更新批次劃分為多個更新段，并將各個頂點的更新段分配給該頂點劃分到的Node；

S4.依次處理該更新批次內的各個頂點的更新段，判斷該頂點的度數是否大于閾值，若是，進入步驟S5，否則，進入步驟S6；

S5.根據頂點的更新代價較小原則，自適應選擇調用batch update方法或beap-basedupdate方法更新基礎圖數據，將更新數據存儲到間接索引結構，該間接索引結構在該頂點劃分到的Node上動態分配內存；

S6.調用batch update方法更新基礎圖數據，將更新數據存儲到直接索引結構；

S7.重復步驟S3～S6，直至請求隊列里所有更新批次處理完；

步驟S5包括以下子步驟：

步驟S51.判斷頂點v的間接索引結構是否已組織為beap形式，若是，則直接采用beap-based方法來處理當前頂點v的更新；否則，則根據頂點的更新段B_v，計算更新段長度len_b和頂點v的當前度數d(v)，進入步驟S52；

步驟S52.根據更新段長度len_b和頂點v的當前度數d(v)，分別計算batch update和beap-based update方法的更新成本cost_BU和cost_beap；

cost_BU＝d(v)*log₂len_b

步驟S53.判斷Cost_BU是否小于Cost_beap，若是，則采用batch update方法來處理當前頂點v的更新；否則，則將頂點v的鄰居列表重構為beap形式，再采用beap-based update方法來處理當前頂點v的更新。

2.如權利要求1所述的大規模流式圖數據更新方法，其特征在于，步驟S1包括以下子步驟：

步驟S11.初始化系統的基礎圖數據，并將完整圖數據中各頂點按照當前度數從大到小排序；

步驟S12.將完整圖數據中各頂點按序均分到所有NUMA Node，使得各NUMA Node負載均衡。

3.如權利要求1所述的大規模流式圖數據更新方法，其特征在于，步驟S3包括以下子步驟：

步驟S31.從請求隊列取出下一個待處理的更新批次；

步驟S32.根據該更新批次中源節點劃分，得到更新批次中各個頂點的更新段；

步驟S33.獲取各個頂點被分配的NUMA Node，將對應更新段分配給該Node上的空閑CPU。

4.如權利要求1至3任一項所述的大規模流式圖數據更新方法，其特征在于，間接索引結構存儲模型具體包括：一個4KB的L1索引頁，共包含512個指針項，前511個指針均可指向1KB大小的L1存儲頁，最后一個指針項可指向一個4KB的L2索引頁，將索引擴展到第二級，類似地，L2索引頁共包含512個指針項，所有的指針均可指向2MB大小的L2存儲頁。

5.如權利要求1至3任一項所述的大規模流式圖數據更新方法，其特征在于，在不斷接收更新數據的過程中，如果一個頂點v的度數超過了閾值，為該頂點分配一個L1索引頁和第一個L1存儲頁，然后將直接索引結構中頂點v所在的cell里面的所有鄰居列表數據搬移到L1存儲頁，最后將該cell回收到直接索引結構中，將cell的標識單元s置為空閑狀態；如果第一個L1存儲頁已滿，為頂點v分配第二個L1存儲頁，依次在需要的時候才分配L1存儲頁；如果所有L1存儲頁都已存滿，為頂點分配一個L2索引頁和第一個L2存儲頁，L1索引頁的最后一個指針項指向L2索引頁。