[發(fā)明專利]一種應(yīng)對(duì)傾斜數(shù)據(jù)流在線連接的處理方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710542086.4
• 申請(qǐng)日: 2017-07-05
• 公開(kāi)（公告）號(hào): CN107341240B
• 公開(kāi)（公告）日: 2019-11-15
• 發(fā)明（設(shè)計(jì)）人: 孟小峰;王春凱
• 申請(qǐng)（專利權(quán)）人: 中國(guó)人民大學(xué)
• 主分類號(hào): G06F16/2455
• 分類號(hào): G06F16/2455;G06F16/2453;G06F16/27
• 代理公司: 11245 北京紀(jì)凱知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 徐寧;孫楠<國(guó)際申請(qǐng)>=<國(guó)際公布>=<

本發(fā)明涉及一種應(yīng)對(duì)傾斜數(shù)據(jù)流在線連接的處理方法，其步驟：數(shù)據(jù)流R和數(shù)據(jù)流S根據(jù)基于鍵值的哈希函數(shù)進(jìn)行元組劃分，各元組被分配至同一側(cè)的不同節(jié)點(diǎn)進(jìn)行存儲(chǔ)，并同步將元組發(fā)送至另一側(cè)處理單元以完成在線連接的操作；以預(yù)先設(shè)定時(shí)間間隔周期性地監(jiān)控二部圖連接模型每側(cè)節(jié)點(diǎn)的負(fù)載統(tǒng)計(jì)信息，并搜集發(fā)送至預(yù)先構(gòu)建的數(shù)據(jù)流控制器；若數(shù)據(jù)流控制器監(jiān)控到某些處理單元超過(guò)負(fù)載均衡因子的臨界值，則根據(jù)啟發(fā)式規(guī)則動(dòng)態(tài)制定遷移策略；在數(shù)據(jù)遷移之前，將新產(chǎn)生的數(shù)據(jù)流暫存在Kafka中，暫緩新數(shù)據(jù)的連接操作；此時(shí)，按照遷移策略進(jìn)行數(shù)據(jù)流和連接狀態(tài)信息的遷移，并同步更新路由表；繼續(xù)發(fā)送Kafka中暫存的和新到來(lái)的數(shù)據(jù)，完成后續(xù)的在線連接操作。

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

本發(fā)明涉及一種數(shù)據(jù)處理方法，特別是關(guān)于一種應(yīng)對(duì)傾斜數(shù)據(jù)流在線連接的 處理方法。

背景技術(shù)

一般基于完全二部圖的連接模型可支持分布式數(shù)據(jù)流的連接操作。該模型具 有內(nèi)存高效、易伸縮和可擴(kuò)展等特性。然而，該模型無(wú)法動(dòng)態(tài)分配查詢節(jié)點(diǎn)，并 需要人工干預(yù)數(shù)據(jù)分組的參數(shù)設(shè)置。尤其是針對(duì)傾斜數(shù)據(jù)的全歷史連接查詢，模 型效率更低。

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

針對(duì)上述問(wèn)題，本發(fā)明的目的是提供一種應(yīng)對(duì)傾斜數(shù)據(jù)流在線連接的處理方 法，該方法能有效應(yīng)對(duì)傾斜數(shù)據(jù)的連接操作，并進(jìn)一步提升分布式數(shù)據(jù)流管理系 統(tǒng)的吞吐率，降低云環(huán)境中的計(jì)算成本。

為實(shí)現(xiàn)上述目的，本發(fā)明采取以下技術(shù)方案：一種應(yīng)對(duì)傾斜數(shù)據(jù)流在線連接 的處理方法，其特征在于包括以下步驟：1)數(shù)據(jù)流R和數(shù)據(jù)流S分別被隨機(jī)劃分 成n個(gè)節(jié)點(diǎn)R1，R2，…，Rn和m個(gè)節(jié)點(diǎn)S1，S2，…，Sm，將各個(gè)節(jié)點(diǎn)分別存儲(chǔ)在 n個(gè)或m個(gè)處理單元中，且數(shù)據(jù)流R和數(shù)據(jù)流S分別位于二部圖連接模型的兩側(cè)； 數(shù)據(jù)流R和數(shù)據(jù)流S根據(jù)基于鍵值的哈希函數(shù)進(jìn)行元組劃分，數(shù)據(jù)流R或S的元 組被分配至同一側(cè)的不同節(jié)點(diǎn)進(jìn)行存儲(chǔ)，并同步將該元組發(fā)送至另一側(cè)處理單元 以完成在線連接的操作；2)以預(yù)先設(shè)定時(shí)間間隔周期性地監(jiān)控二部圖連接模型 每側(cè)節(jié)點(diǎn)的負(fù)載統(tǒng)計(jì)信息，并搜集發(fā)送至預(yù)先構(gòu)建的數(shù)據(jù)流控制器；若數(shù)據(jù)流控 制器監(jiān)控到某些處理單元超過(guò)負(fù)載均衡因子的臨界值，則根據(jù)啟發(fā)式規(guī)則動(dòng)態(tài)制定遷移策略；3)在數(shù)據(jù)遷移之前，將新產(chǎn)生的數(shù)據(jù)流暫存在高吞吐量的分布式發(fā) 布訂閱消息系統(tǒng)中，暫緩新數(shù)據(jù)的連接操作；此時(shí)，按照遷移策略進(jìn)行數(shù)據(jù)流和 連接狀態(tài)信息的遷移，并同步更新路由表；4)繼續(xù)發(fā)送Kafka中暫存的和新到來(lái) 的數(shù)據(jù)，完成后續(xù)的在線連接操作。

所述步驟2)中，設(shè)定的啟發(fā)式規(guī)則如下：2.1)規(guī)則H1：數(shù)據(jù)需要遷出的處 理單元，如果遷出負(fù)載鍵值的元組后可直接滿足非平衡因子閾值的要求，則直接 進(jìn)行遷出操作，并在路由表中記錄遷移鍵值；2.2)規(guī)則H2：數(shù)據(jù)需要遷出的處理 單元，如果遷出某些鍵值的元組后仍不滿足非平衡因子閾值的要求，則需要切分 具有較高元組數(shù)的鍵值，并將切分后的部分?jǐn)?shù)據(jù)進(jìn)行遷出操作，并在路由表中記 錄遷移鍵值；2.3)規(guī)則H3：數(shù)據(jù)需要遷入的處理單元，如果存在鍵值在路由表中， 則優(yōu)先將該鍵值的元組合并至哈希函數(shù)映射的處理單元，并清空路由表中的記錄。

根據(jù)啟發(fā)式規(guī)則，設(shè)定遷出元組和遷入元組的基本算法，遷出元組的基本算 法為：首先，判斷遷出集合中遷出元組的鍵值范圍，并確定待遷入元組的處理單 元；然后，針對(duì)各個(gè)遷出鍵值按照啟發(fā)式規(guī)則H1和規(guī)則H2完成數(shù)據(jù)遷出，并更 新路由表；最后，確定遷移計(jì)劃；遷入元組的基本算法為：首先，判斷遷入集合 中遷入元組的鍵值范圍，并確定待遷出元組的處理單元；然后，針對(duì)各個(gè)遷入鍵 值按照啟發(fā)式規(guī)則H3完成數(shù)據(jù)遷入，并更新路由表；最后，確定遷移計(jì)劃。

所述步驟2)中，動(dòng)態(tài)制定遷移策略是根據(jù)不同遷移類型定義三種代價(jià)：(1)網(wǎng) 絡(luò)代價(jià)Cnetwork：數(shù)據(jù)分裂的情況下，相同鍵值的元組分布于不同的處理單元， 在連接操作時(shí)由于復(fù)制數(shù)據(jù)帶來(lái)的代價(jià)；(2)遷移代價(jià)Cmigration：元組從某一處 理單元遷移到其他處理單元的代價(jià)；(3)路由代價(jià)Crouting：數(shù)據(jù)遷移后，為記錄 鍵值和處理單元的映射關(guān)系而維護(hù)遷移路由的代價(jià)。