[發明專利]一種應對傾斜數據流在線連接的處理方法

有效

• 申請號: 201710542086.4
• 申請日: 2017-07-05
• 公開（公告）號: CN107341240B
• 公開（公告）日: 2019-11-15
• 發明（設計）人: 孟小峰;王春凱
• 申請（專利權）人: 中國人民大學
• 主分類號: G06F16/2455
• 分類號: G06F16/2455;G06F16/2453;G06F16/27
• 代理公司: 11245 北京紀凱知識產權代理有限公司
• 代理人: 徐寧;孫楠<國際申請>=<國際公布>=<

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

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

2)以預先設定時間間隔周期性地監控二部圖連接模型每側節點的負載統計信息，并搜集發送至預先構建的數據流控制器；若數據流控制器監控到某些處理單元超過負載均衡因子的臨界值，則根據啟發式規則動態制定遷移策略；

所述步驟2)中，設定的啟發式規則如下：

2.1)規則H1：數據需要遷出的處理單元，如果遷出負載鍵值的元組后可直接滿足非平衡因子閾值的要求，則直接進行遷出操作，并在路由表中記錄遷移鍵值；

2.2)規則H2：數據需要遷出的處理單元，如果遷出某些鍵值的元組后仍不滿足非平衡因子閾值的要求，則需要切分具有較高元組數的鍵值，并將切分后的部分數據進行遷出操作，并在路由表中記錄遷移鍵值；

2.3)規則H3：數據需要遷入的處理單元，如果存在鍵值在路由表中，則優先將該鍵值的元組合并至哈希函數映射的處理單元，并清空路由表中的記錄；

根據啟發式規則，設定遷出元組和遷入元組的基本算法，遷出元組的基本算法為：

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

然后，針對各個遷出鍵值按照啟發式規則H1和規則H2完成數據遷出，并更新路由表；

最后，確定遷移計劃；

遷入元組的基本算法為：

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

然后，針對各個遷入鍵值按照啟發式規則H3完成數據遷入，并更新路由表；

最后，確定遷移計劃；

動態制定遷移策略是根據不同遷移類型定義三種代價：

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

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

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

3)在數據遷移之前，將新產生的數據流暫存在高吞吐量的分布式發布訂閱消息系統中，暫緩新數據的連接操作；此時，按照遷移策略進行數據流和連接狀態信息的遷移，并同步更新路由表；

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

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

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

然后，對于需要遷出數據的處理單元，調用遷出元組算法；

最后，對于需要遷入數據的處理單元，調用遷入元組算法。

3.如權利要求1所述的一種應對傾斜數據流在線連接的處理方法，其特征在于：所述步驟2)中，針對兩側節點邏輯遷移采用S2SM算法，其過程如下：

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

然后，根據臨界值判定遷出元組的一側和遷入元組的一側；

最后，針對遷出側，判斷需要遷出的處理單元并調用遷出元組算法，針對遷入側，判斷需要遷入的處理單元并調用遷入元組算法。