[發(fā)明專利]一種基于一致性哈希算法的親和性動態(tài)負載均衡方法

在審

• 申請?zhí)枺?/td>: 201710474382.5
• 申請日: 2017-06-21
• 公開（公告）號: CN107197035A
• 公開（公告）日: 2017-09-22
• 發(fā)明（設計）人: 曹衛(wèi)東;孫曉君;丁建立;王靜;王家亮
• 申請（專利權）人: 中國民航大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 天津才智專利商標代理有限公司12108
• 代理人: 龐學欣

技術領域

本發(fā)明屬于集群系統(tǒng)中服務請求親和性負載分配技術領域，特別是涉及一種基于一致性哈希算法的親和性動態(tài)負載均衡方法。

背景技術

目前我國民航業(yè)發(fā)展迅速，據(jù)統(tǒng)計，2016年，民航業(yè)完成旅客運輸量48796萬人次，比上年增長11.9％。逐年增長的航空旅客運輸量產(chǎn)生大量的訂票需求，給民航旅客服務系統(tǒng)帶來了極大挑戰(zhàn)。新一代旅客服務系統(tǒng)(即PSS，Passenger Service System)等大規(guī)模分布式集群系統(tǒng)能夠共同分擔海量用戶請求，其上部署的負載均衡算法可以提供一種廉價并且有效透明的方法來擴展網(wǎng)絡設備和服務器的帶寬、增加吞吐量、提高數(shù)據(jù)處理能力等，因此，負載均衡成為大規(guī)模分布式集群系統(tǒng)的重點研究內(nèi)容。

民航業(yè)一直在積極建設新一代PSS，由于系統(tǒng)結構和業(yè)務需求原因，部分服務的上下文環(huán)境被存儲在處理該服務請求的服務器上，不能被其他服務器共享，而在處理同一個用戶后續(xù)請求過程中需要用到這些環(huán)境，所以需要分配相同服務器處理。同一個用戶的請求會出現(xiàn)互相關聯(lián)現(xiàn)象，即處理后續(xù)請求時，需要用到前面請求的處理結果，所以這部分請求需按時間順序進行處理。

因此，來自同一個用戶的請求，應分配到相同的服務器去處理。這稱之為服務的親和性。即服務的親和性是指：同一用戶的連續(xù)請求必須由同一服務器進行處理。若服務的親和性無法滿足，會導致用戶請求分配不合理性等問題。因此設計同時保證服務的親和性和負載均衡的算法是必要的。

在負載均衡算法的研究方面，目前已經(jīng)有很多研究成果，從民航業(yè)務的親和性的角度，按照用戶請求分配方式，對這些算法進行了如下總結和分析。

一類是以輪詢機制分配請求，例如：

(1)固定比例因子算法：以服務器為單位分配比例因子，并按比例因子輪流分發(fā)請求給各個服務器；

(2)輪詢算法：將用戶的請求依次分配給集群系統(tǒng)中的服務節(jié)點，循環(huán)往復。

另一類是按照特定規(guī)則分配請求，例如：

(1)最小未完成交易數(shù)算法：以未完成交易數(shù)為負載度量指標，循環(huán)服務列表中的每一個服務實例，選擇未完成交易數(shù)最低的服務器處理請求；

(2)改進的動態(tài)告警負載均衡算法：基于請求類型、節(jié)點工作能力和實時負載值來確定請求轉(zhuǎn)發(fā)目標；

(3)基于空間填充曲線的動態(tài)負載均衡算法：利用空間填充曲線可高效地將高維數(shù)據(jù)映射到一維索引的特點，使均衡器根據(jù)實時收集的各項負載指標快速定位到最優(yōu)編碼的服務器。

(4)基于內(nèi)存云架構的帶寬負載均衡算法：內(nèi)存云數(shù)據(jù)中心采用段式日志結構文件系統(tǒng)，提出一種數(shù)據(jù)段交換(data-segments exchanging，DSE)算法，周期性地對內(nèi)存帶寬負載不均衡的服務器上數(shù)據(jù)段進行相互交換，使集群的帶寬負載達到均衡。

但以上多種負載均衡算法，對于來自同一用戶的連續(xù)請求，可能會被分配到不同的服務器上，因此不能在保證負載均衡的情況下滿足服務的親和性需求。

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

為了解決上述問題，本發(fā)明的目的在于提供一種基于一致性哈希算法的親和性動態(tài)負載均衡方法。

為了達到上述目的，本發(fā)明提供的基于一致性哈希算法的親和性動態(tài)負載均衡方法包括按按順序進行的下列步驟：

步驟一、構建由多個實際服務器節(jié)點構成的哈希空間環(huán)，并根據(jù)集群系統(tǒng)中各實際服務器節(jié)點的權重計算虛擬節(jié)點數(shù)量，生成相應的虛擬節(jié)點，然后建立虛擬節(jié)點和該實際服務器節(jié)點之間的映射關系，由此將虛擬節(jié)點映射到哈希環(huán)空間環(huán)上；

步驟二、每當有一新的用戶請求發(fā)送到集群系統(tǒng)中時，解析該用戶請求，并從中提取出有用的標識信息，然后將用戶請求映射到上述哈希環(huán)空間環(huán)上，再映射到距離其最近的實際服務器節(jié)點上進行處理；

步驟三、當集群系統(tǒng)規(guī)模發(fā)生動態(tài)調(diào)整時，針對擴展和縮減兩類實際情況，將用戶請求的映射根據(jù)集群系統(tǒng)動態(tài)調(diào)整策略進行調(diào)整。

在步驟一中，所述的構建由多個實際服務器節(jié)點構成的哈希空間環(huán)，并根據(jù)集群系統(tǒng)中各實際服務器節(jié)點的權重計算虛擬節(jié)點數(shù)量，生成相應的虛擬節(jié)點，然后建立虛擬節(jié)點和該實際服務器節(jié)點之間的映射關系，由此將虛擬節(jié)點映射到哈希環(huán)空間環(huán)上的具體步驟如下：

根據(jù)鍵值的比特數(shù)N構建一個由多個實際服務器節(jié)點構成的0～2³²-1的哈希空間環(huán)，比特數(shù)N＝32；

定義虛擬節(jié)點數(shù)量并將虛擬節(jié)點數(shù)量記為VNN，計算公式如下：