[發明專利]基于Gossip通信協議和Raft選舉算法的優化方法

有效

• 申請號: 201710004354.7
• 申請日: 2017-01-04
• 公開（公告）號: CN106656624B
• 公開（公告）日: 2019-05-14
• 發明（設計）人: 顧乃杰;黃增士;李燚;郝建林;朱方祥;王芬
• 申請（專利權）人: 合肥康捷信息科技有限公司
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L29/08
• 代理公司: 安徽省合肥新安專利代理有限責任公司 34101
• 代理人: 陸麗莉;何梅生

1.一種基于Gossip通信協議和Raft選舉算法的優化方法，是應用于由N×(n+1)個節點組成的Redis集群中，所述節點是運行在集群模式下的Redis服務器，并分為N個主節點和N×n個從節點，任意一個主節點分別對應于n個從節點，由一個主節點及其對應的n個從節點構成一個分片；其特征是，所述優化方法按如下步驟進行：

步驟1、全局定義：

定義所述N個主節點構成的主節點集合為{M₁,M₂,…,M_i,…,M_N}，M_i表示第i個主節點；1≤i≤N；

定義所述第i個主節點M_i的從節點集合為{S_i1,S_i2,…,S_ij,…,S_in}，S_ij表示第i個主節點M_i所對應的第j個從節點；1≤j≤n；

定義Redis集群中的所有節點集合為{N₁,N₂,…,N_k,…,N_N×(n+1)}，N_k表示第k個節點，1≤k≤N×(n+1)；

定義保存所述第k個節點N_k詳細狀態信息的結構體為第k個狀態結構體CN_k；

定義保存并維護所述第k個節點N_k對Redis集群認知的結構體為第k個認知結構體CS_k，所述第k個認知結構體CS_k中所保存的信息包括：當前紀元、上一次投票紀元和Redis集群中所有節點的狀態結構體；定義第k個認知結構體CS_k中的當前紀元記為CE_k、上一次投票紀元記為LE_k、所有節點的狀態結構體所組成的鏈表為NO_k；

定義任意第p個節點N_p和第q個節點N_q之間周期性的通信消息為PING/PONG消息；1≤p,q≤N×(n+1)；p≠q；

所述第p個節點N_p發送的PING/PONG消息中攜帶自身的狀態信息和相應的Gossip單元；定義所述Gossip單元包含w條Gossip消息；每條Gossip消息對應一個其他節點的狀態信息，通過Redis集群中的PING/PONG消息傳播，所述第p個節點N_p更新自身的認知結構體CS_p；

定義節點間的通信超時時間為T；

定義所述Redis集群中的所有節點分為三種狀態，包括：在線狀態、疑似下線狀態、下線狀態；

在線狀態表示第p個節點N_p在發送PING消息后，在通信超時時間T內收到接收第q個節點N_q的PONG消息，則第q個節點N_q認為第p個節點N_p處于在線狀態；

疑似下線狀態表示第p個節點N_p在發送PING消息后，在通信超時時間T內沒有收到接收第q個節點N_q的PONG消息，則第p個節點N_p認為第q個節點N_q處于疑似下線狀態；

下線狀態表示第p個節點N_p發現超過個主節點認為第q個節點N_q處于疑似下線狀態，則第p個節點N_p認為第q個節點N_q處于下線狀態，并將第q個節點N_q的下線消息廣播給其他節點；

定義在Redis集群中第k個節點N_k的鏈表NO_k中處于疑似下線狀態的節點數為u_k；

定義選取次數為r，并初始化r＝1；

步驟2、第k個節點N_k每秒鐘固定向其他m個接收節點發送PING消息；

步驟3、基于Gossip通信協議優化方法對m的值和接收節點的選取方式進行更改：

步驟3.1、令

步驟3.2、第k個節點N_k在Redis集群中未選取的節點內第r次隨機選取一個預接收節點，判斷所述預接收節點與第k個節點N_k之間中斷PING/PONG通信的時間是否超過T/2，若超過，則將所述預接收節點作為接收節點；否則，丟棄所述預接收節點；

步驟3.3、將r+1賦值給r，并返回步驟3.2執行，直到r＝m+1為止，從而獲得m₁個接收節點；

步驟3.4、判斷m₁＝m是否成立，若成立，則執行步驟3.8，否則執行步驟3.5；

步驟3.5、初始化r＝1；

步驟3.6、第k個節點N_k在Redis集群中未選取的節點內第r次隨機選取一個接收節點；

步驟3.7、將r+1賦值給r，并返回步驟3.6執行，直到r＝m-m₁+1為止，從而獲得m-m₁個接收節點；

步驟3.8、第k個節點N_k向m個接收節點發送PING消息；

步驟4、主節點M′故障后，第k個節點N_k向主節點M′發送PING消息，并在通信超時時間T內未收到主節點M′的PONG消息，則第k個節點N_k認為主節點M′處于疑似下線狀態，并將所述主節點M′的狀態信息作為一條Gossip消息添加到PING/PONG消息的Gossip單元中，并發送給其他節點，從而告知其他節點主節點M′處于疑似下線狀態；

步驟5、通過PING/PONG消息的傳播，主節點M′的疑似下線消息會在Redis集群中擴散，基于Gossip通信協議的優化方法對w的值和Gossip單元的選取方式進行更改：

步驟5.1、令w_k＝w+u_k；

步驟5.2、第k個節點N_k標記u_k個處于疑似下線狀態的節點，并將所述u_k個節點的狀態信息優先添加到自身PING/PONG消息的Gossip單元中；

步驟5.3、第k個節點N_k在未選取的節點中隨機選取w個節點，并將所述w個節點的狀態信息優先添加到自身PING/PONG消息的Gossip單元中；從而共選取w+u_k個節點作為w_k個Gossip消息添加到Gossip單元中；

步驟6、通過PING/PONG消息的傳播，第p個節點N_p發現超過個主節點認為主節點M′處于疑似下線狀態，則第p個節點N_p認為主節點M′處于下線狀態，并將主節點M′的下線消息廣播給其他節點；從而使得主節點M′處于下線狀態的消息在Redis集群中傳播；

步驟7、假設發生故障的主節點M′所對應的主節點為第i個主節點M_i；則當從節點集合{S_i1,S_i2,…,S_ij,…,S_in}接收到的PING/PONG消息中包含主節點M′處于下線狀態的信息時，第j個從節點S_ij向所有節點發起投票請求；

步驟8、第k個節點N_k接收到所述第j個從節點S_ij的投票請求，則基于Raft選舉算法對投票方式進行更改：

步驟8.1、第k個節點N_k將認知結構體CS_k上的當前紀元CE_k和上一次投票紀元LE_k保存到鏈表NO_k的所有狀態結構體中；從而使得所有狀態結構體中均保存各自的當前紀元和上一次投票紀元；

步驟8.2、若第k個節點N_k是主節點，則獲得發生故障的主節點M′在所有節點中所在的位置z后，第k個節點N_k通過認知結構體CS_k保存的第z個狀態結構體CN_z上的當前紀元和上一次投票紀元來判斷是否發送支持票給第j個從節點S_ij；若第k個節點N_k是從節點，則第k個節點N_k對投票請求不做任何處理；

步驟9、當第j個從節點S_ij接收到個主節點的支持票時，第j個從節點S_ij升為新的主節點，代替原來主節點的功能，并通過廣播PING消息告知所有的其他節點，從而使得Redis集群中所有節點得知第j個從節點S_ij升為主節點；

步驟10、Redis集群恢復成功。