[發(fā)明專利]一種Gaia系統(tǒng)中基于數(shù)據(jù)特征的動態(tài)優(yōu)先級迭代器

有效

• 申請?zhí)枺?/td>: 202011473342.7
• 申請日: 2020-12-15
• 公開（公告）號: CN112527483B
• 公開（公告）日: 2022-06-10
• 發(fā)明（設計）人: 岳曉飛;趙宇海;王國仁;季航旭;李博揚
• 申請（專利權）人: 東北大學;北京理工大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;G06F9/54
• 代理公司: 沈陽東大知識產權代理有限公司 21109
• 代理人: 李珉

1.一種Gaia系統(tǒng)中基于數(shù)據(jù)特征的動態(tài)優(yōu)先級迭代器，其特征在于：包括：優(yōu)先級調度模塊、全量迭代計算模塊和增量迭代計算模塊；

所述優(yōu)先級調度模塊包括數(shù)據(jù)緩存單元、狀態(tài)信息維護單元和優(yōu)先級調度單元；

所述數(shù)據(jù)緩存單元將向Gaia系統(tǒng)中的算子提供數(shù)據(jù)集的數(shù)據(jù)源提供的流數(shù)據(jù)加載到搭載Gaia系統(tǒng)的分布集群的分布式內存中，并將流數(shù)據(jù)導入內存數(shù)據(jù)庫中進行緩存，并在下游迭代算子空閑時，Gaia系統(tǒng)將從按優(yōu)先級從大到小排列好的數(shù)據(jù)隊列中對數(shù)據(jù)進行讀取，并將讀取的數(shù)據(jù)作為迭代計算的初始工作集；

所述狀態(tài)信息維護單元在每次迭代任務執(zhí)行過程中在Gaia系統(tǒng)的每個計算結點上維護一個基于線性鏈表改進得到的用于查找和選擇數(shù)據(jù)單元的數(shù)據(jù)結構—跳表，以及一個用于保存數(shù)據(jù)單元對應的狀態(tài)信息的哈希表數(shù)據(jù)結構—狀態(tài)表；所述狀態(tài)表記錄工作集中每個數(shù)據(jù)單元的優(yōu)先級信息和訪問頻次信息；

所述優(yōu)先級調度單元通過定義狀態(tài)更新函數(shù)在每次迭代任務開始時按照優(yōu)先級調整公式來更新狀態(tài)表，記錄數(shù)據(jù)單元的訪問頻次和初始優(yōu)先級，當本次迭代任務所輸入的數(shù)據(jù)單元全部更新完后，再通過定義優(yōu)先級生成函數(shù)來決定每個數(shù)據(jù)單元的優(yōu)先級；Gaia系統(tǒng)則根據(jù)各個數(shù)據(jù)單元的優(yōu)先級信息率先提取優(yōu)先級最高的數(shù)據(jù)單位進行迭代計算；

所述全量迭代計算模塊由BulkIterate算子實現(xiàn)，增量迭代計算模塊由Delta Itreate算子實現(xiàn)；

所述BulkIterate算子和Delta Itreate算子均包括：迭代輸入獲取函數(shù)、迭代函數(shù)、迭代結果、迭代終止條件；所述Delta Itreate算子還包括迭代輸出NextWorkset/UpdateSolutionSet，所述BulkIterate算子還包括迭代輸出NextPartialSolution；

所述跳表中數(shù)據(jù)單元的key值和數(shù)據(jù)單元在跳表中所對應的位置滿足以下關系：

跳表中給定key值的數(shù)據(jù)單元在跳表中的排序位置與數(shù)據(jù)單元的分布特征有關，在已知數(shù)據(jù)累計分布函數(shù)的情況下，對于包含N個元素的數(shù)據(jù)集，數(shù)據(jù)單元的key值和數(shù)據(jù)單元在跳表中的位置滿足如下公式：

其中，CFD()為累計分布函數(shù)，N為數(shù)據(jù)集中元素個數(shù)，key為數(shù)據(jù)單元的key值，location為key值所對應數(shù)據(jù)單元在跳表中的位置；

(1)對于跳表中未存在key值的數(shù)據(jù)單元進行插入的時候，通過核密度估計的方式估計出數(shù)據(jù)的累計分布函數(shù)預估key值所對應數(shù)據(jù)單元在跳表中的位置，如下公式所示:

其中，為key值所對應的數(shù)據(jù)單元在跳表中位置的估計值，為通過核密度估計的方式估計出數(shù)據(jù)的累計分布函數(shù)值；

(2)對于后續(xù)到達的數(shù)據(jù)單元對應的key值已經存在于跳表中的情況，根據(jù)迭代算法對該key值對應的數(shù)據(jù)單元的訪問頻率，來對該key值對應的數(shù)據(jù)單元在跳表中的數(shù)據(jù)層數(shù)進行調整，進而根據(jù)數(shù)據(jù)單元所在跳表或經過調整后的跳表層數(shù)來量化生成動態(tài)優(yōu)先級；該動態(tài)優(yōu)先級作為迭代器不同時刻選擇合適key值的數(shù)據(jù)單元來執(zhí)行迭代算法的依據(jù)；若跳表將訪問頻率排名處于前2^h-1的熱數(shù)據(jù)均放在最上面h層，而maxlevel-h層及以下層級都是訪問頻率排名處于末尾2^h-1的冷數(shù)據(jù)，其中，maxlevel為跳表的最大層數(shù)；則對訪問頻率排名處于前2^h-1的熱數(shù)據(jù)的優(yōu)先級Priority進行動態(tài)調整，如下公式所示：

其中，level為當前數(shù)據(jù)單元在跳表中的層數(shù)，函數(shù)count(key)的返回值為數(shù)據(jù)集中key值的數(shù)量，N為數(shù)據(jù)集大小，freqs為當前數(shù)據(jù)單元的訪問頻次，p為Gaia系統(tǒng)最小誤差系數(shù)。