[發明專利]一種Gaia系統中基于數據特征的動態優先級迭代器

有效

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

本發明提供一種Gaia系統中基于數據特征的動態優先級迭代器，涉及分布式大數據計算技術領域。該迭代器包括優先級調度模塊、全量迭代計算模塊和增量迭代計算模塊；優先級調度模塊讀取數據源的數據作為迭代計算的初始工作集，并在每次迭代任務執行過程中維護一個用于查找和選擇數據單元的跳表，以及一個用于保存數據單元對應的狀態信息的狀態表；并在每次迭代任務開始時按照優先級調整公式來更新狀態表，當本次迭代任務所輸入的數據單元全部更新完后，確定每個數據單元的優先級；Gaia系統則根據各個數據單元的優先級信息進行迭代計算；全量迭代模塊由BulkIterate算子實現迭代計算，增量迭代模塊由Delta Itreate算子實現迭代計算。

技術領域

本發明涉及分布式大數據計算技術領域，尤其涉及一種Gaia系統中基于數據特征的動態優先級迭代器。

背景技術

Gaia系統是一個基于多計算模型混合并存的高時效、可擴展的新一代大數據計算系統。在自適應、可伸縮的大數據存儲、批流融合大數據計算、高維大規模機器學習和高時效大數據智能交互向導等大數據分析系統的幾個核心層面，解決一系列關鍵技術問題，構建自主可控的高時效、可伸縮的新一代大數據分析系統，掌握國際領先的大數據分析系統核心技術。

在大數據環境下，分布式迭代計算在數據處理及分析中發揮著至關重要的作用，已經應用到諸如社會網絡分析、高性能計算、推薦系統、模式識別等諸多領域中。傳統的迭代計算模型負責將要進行處理的數據導入已定義迭代邏輯函數的迭代器進行反復運算，直到輸出結果滿足迭代終止條件，也即迭代邏輯函數收斂為止。目前支持迭代計算的分布式系統有HaLoop、PrIter、iMapReduce、REX、Naiad。在上述分布式系統中，對迭代計算的支持通常依賴于為每次迭代過程提交一個新的作業，或者通過向運行中的作業執行圖(DAG)添加額外的節點。Gaia系統中的迭代計算方式是通過迭代步驟函數和一個包含整個執行圖的特殊算子來實現的，具體結構如圖1所示，為了保持基于DAG圖的運行時和調度器，Gaia允許建立迭代“頭”和“尾”任務與反饋流隱式連接。Gaia系統已對傳統的迭代計算過程從減少通信代價和內存優化等角度進行了不同程度上的改進，而且已廣泛應用于各種不同的大數據場景下的迭代算法的執行。

Gaia作為分布式實時流處理系統，它的迭代不同于可提供迭代計算的傳統框架，它是以迭代步驟為核心的形式實現的，這些迭代步驟本身就包含一個DAG執行圖，如圖2所示。Gaia為了維護基于DAG執行圖的運行時和調度器，允許添加迭代頭和尾任務，這些任務通過與反饋邊Feedback隱式連接來建立一個到迭代步驟的主動反饋通道，并為在這個反饋通道內處理傳輸中的數據記錄提供協調，但是它在每次迭代時會對所有數據執行更新計算，這些數據的更新計算被默認為同等重要。由于在大規模數據中往往只有少數數據的更新計算將對迭代算法收斂將起著決定性作用，而大多數數據的更新計算所發揮的作用往往是有限的，所以上述迭代機制會造成Gaia進行一些不必要的計算，不能夠使迭代算法快速收斂，極大地降低了系統的執行效率。

但是在當今數據量爆發的時代，Gaia系統對時變性明顯的數據的處理效率低下，所支持的迭代算法開始出現諸多不適用性，系統處理也容易出現瓶頸，無法滿足用戶對實時性的需求。尤其是對于存在數據傾斜現象的數據，如果仍然依照傳統思路，僅考慮大數據計算系統內處理節點的內存和性能來對迭代計算過程進行優化，而不考慮所處理的迭代數據本身的特征，就會使系統進行一些不必要的操作甚至使迭代算法無法在有效時間內進行收斂，從而導致系統整體任務的完成時間和吞吐量受到影響。

發明內容

本發明要解決的技術問題是針對上述現有技術的不足，提供一種Gaia系統中基于數據特征的動態優先級迭代器，將Gaia系統中需經過迭代算法處理的數據按一定順序來調度給該迭代器進行執行。

為解決上述技術問題，本發明所采取的技術方案是：一種Gaia系統中基于數據特征的動態優先級迭代器，包括：優先級調度模塊、全量迭代計算模塊和增量迭代計算模塊；

所述優先級調度模塊包括數據緩存單元、狀態信息維護單元和優先級調度單元；