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

有效

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

1.一種應(yīng)對傾斜數(shù)據(jù)流在線連接的處理方法，其特征在于包括以下步驟：

1)數(shù)據(jù)流R和數(shù)據(jù)流S分別被隨機劃分成n個節(jié)點R1，R2，…，Rn和m個節(jié)點S1，S2，…，Sm，將各個節(jié)點分別存儲在n個或m個處理單元中，且數(shù)據(jù)流R和數(shù)據(jù)流S分別位于二部圖連接模型的兩側(cè)；數(shù)據(jù)流R和數(shù)據(jù)流S根據(jù)基于鍵值的哈希函數(shù)進(jìn)行元組劃分，數(shù)據(jù)流R或S的元組被分配至同一側(cè)的不同節(jié)點進(jìn)行存儲，并同步將該元組發(fā)送至另一側(cè)處理單元以完成在線連接的操作；

2)以預(yù)先設(shè)定時間間隔周期性地監(jiān)控二部圖連接模型每側(cè)節(jié)點的負(fù)載統(tǒng)計信息，并搜集發(fā)送至預(yù)先構(gòu)建的數(shù)據(jù)流控制器；若數(shù)據(jù)流控制器監(jiān)控到某些處理單元超過負(fù)載均衡因子的臨界值，則根據(jù)啟發(fā)式規(guī)則動態(tài)制定遷移策略；

所述步驟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è)定遷出元組和遷入元組的基本算法，遷出元組的基本算法為：

首先，判斷遷出集合中遷出元組的鍵值范圍，并確定待遷入元組的處理單元；

然后，針對各個遷出鍵值按照啟發(fā)式規(guī)則H1和規(guī)則H2完成數(shù)據(jù)遷出，并更新路由表；

最后，確定遷移計劃；

遷入元組的基本算法為：

首先，判斷遷入集合中遷入元組的鍵值范圍，并確定待遷出元組的處理單元；

然后，針對各個遷入鍵值按照啟發(fā)式規(guī)則H3完成數(shù)據(jù)遷入，并更新路由表；

最后，確定遷移計劃；

動態(tài)制定遷移策略是根據(jù)不同遷移類型定義三種代價：

(1)網(wǎng)絡(luò)代價Cnetwork：數(shù)據(jù)分裂的情況下，相同鍵值的元組分布于不同的處理單元，在連接操作時由于復(fù)制數(shù)據(jù)帶來的代價；

(2)遷移代價Cmigration：元組從某一處理單元遷移到其他處理單元的代價；

(3)路由代價Crouting：數(shù)據(jù)遷移后，為記錄鍵值和處理單元的映射關(guān)系而維護(hù)遷移路由的代價；

3)在數(shù)據(jù)遷移之前，將新產(chǎn)生的數(shù)據(jù)流暫存在高吞吐量的分布式發(fā)布訂閱消息系統(tǒng)中，暫緩新數(shù)據(jù)的連接操作；此時，按照遷移策略進(jìn)行數(shù)據(jù)流和連接狀態(tài)信息的遷移，并同步更新路由表；

4)繼續(xù)發(fā)送Kafka中暫存的和新到來的數(shù)據(jù)，完成后續(xù)的在線連接操作。

2.如權(quán)利要求1所述的一種應(yīng)對傾斜數(shù)據(jù)流在線連接的處理方法，其特征在于：所述步驟2)中，在時刻t，單側(cè)的數(shù)據(jù)遷移采用ISM算法，其過程如下：

首先，統(tǒng)計時刻t每個處理單元的負(fù)載Lt(pu)，并計算出平均負(fù)載；

然后，對于需要遷出數(shù)據(jù)的處理單元，調(diào)用遷出元組算法；

最后，對于需要遷入數(shù)據(jù)的處理單元，調(diào)用遷入元組算法。

3.如權(quán)利要求1所述的一種應(yīng)對傾斜數(shù)據(jù)流在線連接的處理方法，其特征在于：所述步驟2)中，針對兩側(cè)節(jié)點邏輯遷移采用S2SM算法，其過程如下：

首先，統(tǒng)計每個處理單元的負(fù)載Lt(pu)，并分別統(tǒng)計各側(cè)和整個集群的平均負(fù)載L_tm,L_tn和L_t；其中，L_tm表示t時刻具有m個處理單元側(cè)的平均負(fù)載，L_tn表示t時刻具有n個處理單元側(cè)的平均負(fù)載，L_t表示t時刻整個集群的平均負(fù)載；

然后，根據(jù)臨界值判定遷出元組的一側(cè)和遷入元組的一側(cè)；

最后，針對遷出側(cè)，判斷需要遷出的處理單元并調(diào)用遷出元組算法，針對遷入側(cè)，判斷需要遷入的處理單元并調(diào)用遷入元組算法。