[發(fā)明專利]一種基于NUMA架構(gòu)的大規(guī)模流式圖數(shù)據(jù)更新方法

有效

• 申請?zhí)枺?/td>: 201910368729.7
• 申請日: 2019-05-05
• 公開（公告）號: CN110245135B
• 公開（公告）日: 2021-05-18
• 發(fā)明（設(shè)計）人: 邵志遠;金海;廖小飛;趙智慧
• 申請（專利權(quán)）人: 華中科技大學(xué)
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/23
• 代理公司: 華中科技大學(xué)專利中心 42201
• 代理人: 李智;曹葆青

本發(fā)明公開了一種基于NUMA架構(gòu)的大規(guī)模流式圖數(shù)據(jù)更新方法，屬于大數(shù)據(jù)技術(shù)領(lǐng)域。本發(fā)明對度較小的頂點，直接采用batch update方法處理更新，對度較大的頂點，根據(jù)頂點的更新代價較小原則，自適應(yīng)選擇調(diào)用batch update方法或beap?based update方法處理更新，降低了檢索和插入復(fù)雜度；將度較小的頂點直接存儲在完全連續(xù)的直接索引，將度較大的頂點存儲在獨立可擴展的間接索引結(jié)構(gòu)，在更新時存儲結(jié)構(gòu)不需要頻繁動態(tài)分配空間，間接索引結(jié)構(gòu)的存儲頁是完全連續(xù)的；將完整圖數(shù)據(jù)集中的各頂點按度數(shù)依次劃分到不同的NUMA Node上，并分配各頂點被劃分到的Node上的CPU來處理頂點的更新數(shù)據(jù)，使得本地Node上的CPU訪問本地內(nèi)存來處理更新數(shù)據(jù)，盡量減少更新過程中的遠程訪問，來提高訪問效率。

技術(shù)領(lǐng)域

本發(fā)明屬于大數(shù)據(jù)技術(shù)領(lǐng)域，更具體地，涉及一種基于NUMA架構(gòu)的大規(guī)模流式圖數(shù)據(jù)更新方法。

背景技術(shù)

在大數(shù)據(jù)時代，流式圖數(shù)據(jù)的大規(guī)模、高更新頻率使得圖計算技術(shù)領(lǐng)域面臨巨大挑戰(zhàn)。如何加快接收流式圖數(shù)據(jù)更新量的速度，以維持最新圖結(jié)構(gòu)，成為了亟待解決的問題。近幾年，大規(guī)模流式圖處理系統(tǒng)有了一些成果——Stinger、Snap、DCSR、GPMA。這些成果極大地提高了接收流式圖更新的速度，同時能夠支撐圖算法的執(zhí)行性能。這些流式圖處理的方式主要包括：基于服務(wù)器的流式圖系統(tǒng)和基于GPU設(shè)備的流式圖系統(tǒng)。

基于服務(wù)器的流式圖系統(tǒng)，如Stinger，每個頂點都會有出邊和入邊鄰居列表，鄰居列表的數(shù)據(jù)結(jié)構(gòu)是基于鏈接的block list結(jié)構(gòu)，每個block可存儲固定數(shù)目大小的出邊或入邊，其圖更新的步驟是：初始化圖結(jié)構(gòu)、客戶端給服務(wù)端以批次為單位發(fā)送更新數(shù)據(jù)、服務(wù)端接收圖更新數(shù)據(jù)、服務(wù)端處理接收的圖更新數(shù)據(jù)、服務(wù)端更新圖結(jié)構(gòu)。基于服務(wù)器的流式圖系統(tǒng)隨著圖規(guī)模的擴大有很好的擴展性，但是系統(tǒng)處理效率難以提高。首先，在面臨高更新頻率的圖數(shù)據(jù)時，其存儲結(jié)構(gòu)需要不斷的分配和回收空間，時間開銷大。其次，采用的數(shù)據(jù)結(jié)構(gòu)在更新圖數(shù)據(jù)時的檢索和插入復(fù)雜度較高，特別是度數(shù)越高的頂點，鄰居列表越長，檢索時間越長，制約了系統(tǒng)的性能。最后，數(shù)據(jù)在內(nèi)存中存放不連續(xù)，對于各類圖算法的執(zhí)行不利。

基于GPU設(shè)備的流式圖系統(tǒng)，如GPMA，則是在GPU上提出存儲方案，利用PMA結(jié)構(gòu)，為樹結(jié)構(gòu)的每一層片段分配上下界密度閾值，根據(jù)密度范圍來分配圖數(shù)據(jù)。而基于GPU設(shè)備的圖系統(tǒng)，主要是設(shè)備空間大小受限，系統(tǒng)能處理的圖規(guī)模受限。

發(fā)明內(nèi)容

針對現(xiàn)有技術(shù)的缺陷，本發(fā)明的目的在于解決現(xiàn)有技術(shù)大規(guī)模流式圖數(shù)據(jù)更新時間開銷大的技術(shù)問題。

為實現(xiàn)上述目的，第一方面，本發(fā)明實施例提供了一種基于NUMA架構(gòu)的大規(guī)模流式圖數(shù)據(jù)更新方法，該方法包括以下步驟：

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

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

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

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

S5.根據(jù)頂點的更新代價較小原則，自適應(yīng)選擇調(diào)用batch update方法或beap-based update方法更新基礎(chǔ)圖數(shù)據(jù)，將更新數(shù)據(jù)存儲到間接索引結(jié)構(gòu)，該間接索引結(jié)構(gòu)在該頂點劃分到的Node上動態(tài)分配內(nèi)存；

S6.調(diào)用batch update方法更新基礎(chǔ)圖數(shù)據(jù)，將更新數(shù)據(jù)存儲到直接索引結(jié)構(gòu)；

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

具體地，步驟S1包括以下子步驟：