摘要:針對衛(wèi)星通信系統(tǒng)高并發(fā)處理需求,文章提出一種多處理器自適應負載均衡方法,該方法對傳統(tǒng)Hash算法進行了改進,綜合考慮了各處理器處理能力的差異,解決了普通Hash算法存在的Hash不均問題,在處理器數(shù)量發(fā)生變化時整個系統(tǒng)映射關系的調整較小。算法在系統(tǒng)容錯性、可擴展性和負載均衡性方面均有較大的改進,克服了現(xiàn)有負載均衡方法的局限性。
關鍵詞:衛(wèi)星通信;負載均衡;一致性哈希
中圖分類號:TN92文獻標志碼:A
0 引言
衛(wèi)星通信因其業(yè)務覆蓋廣、系統(tǒng)可靠、傳輸性高、系統(tǒng)不受地面環(huán)境狀態(tài)影響等優(yōu)勢,在各行各業(yè)被越來越廣泛地應用。隨著衛(wèi)星通信用戶量越來越多,地面衛(wèi)星通信系統(tǒng)高并發(fā)處理需求也隨之提高,傳統(tǒng)的單進程信息處理器很難滿足業(yè)務通信過程中用戶高并發(fā)請求下信息處理的實時性要求,需要進行多進程信息處理器負載均衡[1]。目前,進行多進程信息處理器負載均衡的主流方法主要有靜態(tài)負載均衡和動態(tài)負載均衡方法。靜態(tài)負載均衡主要有輪轉算法、加權輪轉算法和散列法等;動態(tài)負載均衡算法主要有最少連接法、最快響應法等。其中,輪轉算法適合所有節(jié)點的處理能力均相同的情況,請求到來時按照順序分別發(fā)給各個處理器進行處理,若節(jié)點處理能力不同,則可能出現(xiàn)不同處理能力的節(jié)點之間負載分擔不均問題;加權輪轉算法是普通輪轉算法的改進,考慮了各個處理器節(jié)點處理能力的差異,根據(jù)處理能力的差異確定權值,改善了負載分擔的均衡性,但處理器故障的容錯性和數(shù)量的擴展性較差;散列法的均衡性取決于哈希均勻性,存在哈希不均的問題且當處理器數(shù)量增加或因故障減少時,哈希值和處理器之間的映射關系需要重新調整;動態(tài)均衡算法主要是動態(tài)檢測處理器當前的請求數(shù)和信息處理響應時間,根據(jù)各個處理器當前的請求數(shù)和響應時間動態(tài)調整請求信令的分配,會增大系統(tǒng)的處理開銷。
針對現(xiàn)有分配方式存在的一些問題,本文提出一種衛(wèi)星通信系統(tǒng)自適應負載均衡方法。該方法將各處理器進程使用相同的哈希算法計算哈希值,并將值映射到0~(232-1)組成的閉合哈希圓環(huán)上,進行用戶請求分配時,系統(tǒng)根據(jù)用戶請求信息特征值計算對應的哈希值,并根據(jù)哈希值在閉合哈希圓環(huán)上順時針尋找最近的滿足處理能力的處理器進行處理,如遇到最近的處理器不滿足條件則繼續(xù)遍歷下一個,各處理器共享狀態(tài)存儲模塊的數(shù)據(jù),實現(xiàn)系統(tǒng)無狀態(tài)處理。該方法綜合考慮了各處理器處理能力的差異以及處理器數(shù)量發(fā)生變化時整個系統(tǒng)映射關系的最小化調整問題,在系統(tǒng)容錯性、可擴展性和負載均衡性方面均有較大的改進,克服了現(xiàn)有負載均衡方法的局限性。
1 衛(wèi)星通信系統(tǒng)架構
地面衛(wèi)星通信系統(tǒng)包括地球站和通信業(yè)務控制中心等部分,如圖1所示。本文所述的自適應負載均衡算法主要針對圖示通信業(yè)務中心模塊中的核心處理器部分,當?shù)厍蛘居脩袅枯^多時,同一時間可能會有大量的入網/呼叫請求需要核心處理器處理,此時如果不進行負載均衡則可能導致處理器過載或用戶請求處理時延變長,影響用戶體驗。
為解決上述問題,需要增加核心處理器數(shù)量,并選擇合適的算法進行多處理器負載均衡,將大量的用戶請求信息分發(fā)給多個處理器同時進行處理,達到提升處理速度,優(yōu)化用戶體驗的目的。
2 改進負載均衡算法和系統(tǒng)
2.1 傳統(tǒng)哈希算法
對于多進程處理器之間的負載均衡多采用哈希算法進行。傳統(tǒng)哈希算法通常是建立哈希值映射表,將哈希值和處理器之間進行循環(huán)映射,根據(jù)待處理信令特征信息計算哈希值,并根據(jù)計算的哈希值查表確定處理器,從而選擇對應的處理器進行處理。此種算法在處理器數(shù)量新增或者減少時都需要對哈希值映射關系進行重新調整,降低了系統(tǒng)的穩(wěn)定性和處理效率。
一致性哈希算法針對上述傳統(tǒng)哈希算法存在的問題進行了改進[2],將所有哈希值抽象成一個圓環(huán),比如哈希值范圍為0~(232-1),則抽象的哈希環(huán)0和(232-1)首尾相接構成一個圓環(huán),計算各處理器節(jié)點的哈希值并映射在哈希環(huán)的對應位置上,計算用戶請求數(shù)據(jù)的哈希值,根據(jù)哈希值順時針尋找距離最近的處理器節(jié)點作為數(shù)據(jù)處理節(jié)點。此種算法在處理器數(shù)量新增或減少時,哈希值映射不需要重新調整,但未考慮不同的處理器節(jié)點可能存在的處理能力差異,也未考慮當用戶量不夠大時可能存在的負載分擔偏移問題。
2.2 改進負載分擔算法
針對上述傳統(tǒng)算法存在的問題,本文對負載分擔算法進行改進,根據(jù)各處理器節(jié)點的CPU利用率、內存利用率、當前處理數(shù)量、當前流量、響應時間等綜合考慮各節(jié)點的處理能力[3],并計算各處理器節(jié)點的最大處理上限,同時對用戶量不夠大時可能存在的負載分擔不均問題進行改善,提升系統(tǒng)整體的性能。
改進負載分擔算法如圖2所示,整體示意圖為抽象成的哈希環(huán),ServerA到ServerD表示當前系統(tǒng)內的4個處理器節(jié)點,處理器節(jié)點之間A1、B1等小的節(jié)點表示各處理器服務節(jié)點的虛擬節(jié)點,通過虛擬節(jié)點可定位對應的實際服務節(jié)點,可解決負載傾斜的問題;此外,算法實施過程中同時兼顧各節(jié)點的處理能力,并根據(jù)節(jié)點處理能力確定各節(jié)點的最大處理并發(fā)量和選擇權重。
其中,哈希環(huán)上處理器實體節(jié)點和虛擬節(jié)點的確定方法采用如下斐波那契散列法計算確定[4]。
哈希函數(shù)為:
H(k)=[m×(k×Amod1)]
其中,m=1 000,A=(5-1)/2。
處理器實體節(jié)點和虛擬節(jié)點的算法如下。
實體節(jié)點:H(k)=[m×(k×Amod1)]。
虛擬節(jié)點1:H(k1)=[m×(H(k)×Amod1)]。
虛擬節(jié)點2:H(k2)=[m×(H(k1)×Amod1)]。
依次類推,根據(jù)各個節(jié)點的處理能力確定需要添加的虛擬節(jié)點個數(shù)。
算法的執(zhí)行流程如圖3所示,改進負載分擔算法的工作流程如下。
(1)利用用戶請求數(shù)據(jù)中的特征數(shù)據(jù)計算哈希值。
(2)根據(jù)哈希值確定在哈希環(huán)上的位置。
(3)順時針查找圓環(huán)上的節(jié)點,根據(jù)找到的實體節(jié)點或虛擬節(jié)點對應的服務節(jié)點確定處理節(jié)點。
(4)若節(jié)點對應的服務節(jié)點當前處理能力已經到達上限,則繼續(xù)查找下一節(jié)點。
(5)若用戶量過大導致所有的節(jié)點均已達到最大處理上限,則根據(jù)節(jié)點的選擇權重選擇性能最優(yōu)的節(jié)點盡可能保障用戶。
2.3 帶負載均衡衛(wèi)星通信系統(tǒng)
根據(jù)上述算法的描述,帶負載均衡的衛(wèi)星通信系統(tǒng)結構如圖4所示。來自地球站的請求信息經過負載均衡處理模塊處理后散轉到各個處理器節(jié)點進行處理,處理后相關的狀態(tài)數(shù)據(jù)存儲在同一個數(shù)據(jù)庫中,各節(jié)點共享數(shù)據(jù),當處理器節(jié)點發(fā)生變更導致同一個地球站的請求后續(xù)會被不同的處理器處理時,可維持地球站的狀態(tài)數(shù)據(jù)一致性,提高系統(tǒng)容錯性和穩(wěn)定性[5]。
3 衛(wèi)星通信負載均衡工作流程
3.1 正常工作流程
衛(wèi)星通信負載均衡正常工作流程是指所有處理器節(jié)點狀態(tài)均正常的情況下的工作流程,如圖5所示。圖中示意了節(jié)點狀態(tài)正常和有節(jié)點負載達到上限狀態(tài)下的節(jié)點選擇情況,節(jié)點狀態(tài)正常的情況以節(jié)點A為例,負載達上限的情況以節(jié)點B為例,具體如下:
節(jié)點狀態(tài)正常情況下的流程以圖中請求Q1為例。Q1為地球站請求信令計算出的哈希值在圓環(huán)上的位置,以Q1為起點順時針查找節(jié)點,順時針第一個節(jié)點為虛擬節(jié)點A1,虛擬節(jié)點A1對應服務處理節(jié)點A,因此請求Q1分配給服務處理節(jié)點A進行處理。
節(jié)點負載達到上限的情況以圖中請求Q2為例。以Q2為起點順時針查找節(jié)點,順時針第一個節(jié)點為虛擬節(jié)點B1,虛擬節(jié)點B1對應服務處理節(jié)點B,但此時節(jié)點B負載達到上限,繼續(xù)順時針查找下一節(jié)點,因此請求Q2分配給服務處理節(jié)點C進行處理。
3.2 節(jié)點數(shù)量變更時工作流程
節(jié)點數(shù)量變更指因故障等問題減少或因處理需要新增節(jié)點的情況,工作流程如圖6所示。節(jié)點數(shù)量減少和新增情況下對用戶請求的分配情況,節(jié)點減少以取消節(jié)點A為例,節(jié)點增加以新增節(jié)點E為例。具體如下:
節(jié)點數(shù)量減少的情況以請求Q3為例,以Q3為起點順時針查找最近的節(jié)點,由于處理器節(jié)點A取消,因此與節(jié)點A關聯(lián)的所有虛擬節(jié)點均取消,此時最近的節(jié)點為虛擬節(jié)點B2,虛擬節(jié)點B2對應服務處理節(jié)點B,因此請求Q3分配給服務處理節(jié)點B進行處理。
節(jié)點數(shù)量新增的情況以請求Q4為例,新增的節(jié)點為節(jié)點E,以Q4為起點順時針查找最近的節(jié)點,順時針第一個節(jié)點為虛擬節(jié)點E1,對應服務處理節(jié)點E,因此請求Q4分配給服務處理節(jié)點E進行處理。
上述可見,本文算法具有較好的容錯性和擴展性,在處理器節(jié)點數(shù)量減少或新增時,可以自適應地將新增或者減少的節(jié)點在哈希環(huán)上進行標識,對用戶請求進行分配時,只有發(fā)生新增或者減少的節(jié)點分配受到影響,處理器節(jié)點和請求哈希值之間的映射關系不需要重新分配,提升了系統(tǒng)的容錯性和擴展性。
4 結語
本文提出了一種地面衛(wèi)星通信系統(tǒng)自適應負載均衡方法,與傳統(tǒng)的衛(wèi)星通信系統(tǒng)負載均衡方法相比,本方法對負載均衡時使用的Hash算法進行了改進[6],解決了基于普通Hash算法的負載均衡可能存在的Hash不均導致的分擔不均問題,解決了傳統(tǒng)負載分擔易出現(xiàn)的狀態(tài)不一致問題,改進了分擔效果。
參考文獻
[1]王健,孫建伶,王新宇,等.容錯多處理機中一種高效的實時調度算法[J].軟件學報,2009(10):2628-2636.
[2]方堃,武小年.改進的一致性哈希算法及應用[J].大眾科技,2015(4):5-7.
[3]盧建元.高性能哈希技術及其應用的研究[D].北京:清華大學,2017.
[4]郭寧,張新.一致性哈希算法在多處理機進程分配的應用[J].計算機與現(xiàn)代化,2013(9):71-74.
[5]姚墨涵,謝紅薇.一致性哈希算法在分布式系統(tǒng)中的應用[J].電腦開發(fā)與應用,2012(7):1-2.
[6]張開琦,劉曉燕,王信,等.基于動態(tài)權重的一致性哈希微服務負載均衡優(yōu)化[J].計算機工程與科學,2020(8):1339-1344.
Research on adaptive load balancing method of the terrestrial satellite communication system
QiuChunrong, YanYingzi
(Nanjing Panda Handa Technology Co., Ltd., Nanjing 210000, China)
Abstract: A multi processor adaptive load balancing method is proposed to address the high requirements for concurrent processing in satellite communication systems. This method improves traditional Hash algorithms and takes into account the differences in processing capabilities of each processor. It Solved the problem of Hash unevenness in ordinary Hash algorithms. The adjustment of the entire system mapping relationship is relatively small when the number of processors changes.it has greater improvement in System Error-tolerance, scalability, and load balancing, overcoming the limitations of existing load balancing methods.
Key words: satellite communications; load balance; consistent Hash