一種集群伺服器的動態負載均衡方法
2023-06-19 07:56:36 1
專利名稱：一種集群伺服器的動態負載均衡方法
技術領域：
本發明屬於網絡集群伺服器技術領域，特別是涉及一種新的支持異構集群系統的動態負載均衡方法。
集群負載均衡技術主要分靜態信息和動態信息算法。靜態算法主要適用於較小規模的、同構的、提供靜態網頁信息服務的系統；而動態算法適用於大規模的、異構的、提供動態網頁信息服務的系統，是當前研究的熱點問題。有關文獻Haakon Bryhni.A Comparison ofLoadBalancing Techniques for Scalable Web Servers.2000 IEEE Network；Emiliano Casalicchio.Staticand Dynamic Scheduling Algorithms for Scalable Web Server Farm.2001 IEEE；許建峰等。分布式實時系統中的預測調度算法；軟體學報，2000 Vol.11 No.1。
早期的負載均衡算法有隨機(Random)算法和輪詢(Round-Robin)算法，特別是輪詢算法採用傳統的輪轉轉發分配方式，計算簡單、效率高，應用較廣。但這兩種算法不考慮後端伺服器的差異，不能保證在不同的伺服器間達到負載均衡，因此，不適合於異構的集群系統(見參考文獻。另外還有基於伺服器中當前活躍連接數(正在處理的請求連接)的最小連接數(LeastConnections First)算法，選擇當前正在處理的請求個數最少的伺服器作為轉發對象。但活躍請求連接個數並不能完全反映伺服器處理負荷上的差異，如處理能力強的伺服器在單位時間內可以處理更多的請求。此外，還可能在請求量少時將多個請求分配到同一臺伺服器。
為了適應異構集群系統的需求，出現了加權輪詢(Weighted Round-Robin)算法和加權最小連接數(Weighted Least Connections First)算法，通過為不同的伺服器配置不同的權值來平衡伺服器間的差異，選取合適的轉發對象。但隨著動態、多媒體網絡信息的大量應用，靜態的權值信息不能表現動態的負載特徵，隨著系統運行時間增長，將導致集群負載分布的不平衡。
為了克服靜態配置權值信息的缺點，提出了動態計算權值信息的方法。動態計算權值的負載均衡算法有基於輪詢的(如WRR_time、WRR_num)和基於活躍連接數的(如Round_Trip、XimtByte)。它們都是通過周期性地獲取伺服器狀態信息，動態地計算出當前每臺伺服器應具有的權值。權值的計算方法第一種是用採樣周期內每臺伺服器的平均響應產生時間(以請求轉發到達伺服器至第一個響應的比特輸出為響應產生時間)來計算，如WRR_time(基於WRR)和Round-Trip(基於WLCF)；第二種是用採樣周期內每臺伺服器的活躍連接數來計算，如WRR_num(基於WRR)；第三種是用採樣周內輸出的字節流量來計算，如XimtByte(基於WLCF)。但是，單從某一個性能指標來考慮負載狀況存在局限性，如響應時間只反映了伺服器最初對請求做出處理的速度，不能反映後續處理過程負荷的大小，特別是現在網頁中包含許多文本、圖象、資料庫查詢的嵌入對象，後續處理產生的負載變化很大；活躍連接數雖然在大多數情況下可以相對準確地反映當前的工作負載狀況，而即便是在連接數相同的情況下，不同的任務也會造成系統資源的消耗大不相同；輸出字節流量只反映網絡輸出負載狀況，對靜態文本訪問有一定的效果，但卻完全無法表現需要複雜計算和數據查詢工作的負荷。
有關文獻Zhang Wensong.Linux Virtual ServerServer Clustering for Scalable NetworkServices.InProc of World Congress Conf 2000[c]，Beijing，2000；Haakon Bryhni.A Comparison ofLoad Balancing Techniques for Scalable Web Servers.2000 IEEE Network；Emiliano Casalicchio.Static and Dynamic Scheduling Algorithms for Scalable Web Server Farm.2001 IEEE；Linux集群的負載調度.www.ibm.com/developerWorks/cn/linux/cluster；單志廣，林闖等。Web請求分配和選擇的綜合方案與性能分析；軟體學報，2001 Vol.12 No.3。
目前，有研究者提出了選擇加權百分比(Selected Weighted Percentage)算法。算法中綜合考慮了伺服器的固有能力、當前負荷、服務速度等參數，通過對CPU利用率、內存利用率、網卡輸出流量等分別加權計算來確定轉發對象。從理論分析和一些試驗來看，在許多情況下要好於上述算法。但存在的問題是算式中的各個權值係數需由系統管理員人為確定，這恰恰是很難辦到的。不同速率的CPU和不同大小的內存究竟各佔多大比例合適，根據不同的情況和所完成的任務不一而有所不同。
有關文獻Linux集群的負載調度.www.ibm.com/developerWorks/cn/linux/cluster；於磊等。多伺服器中的負載平衡與容錯；系統仿真學報，2001 Vol.13 No.3。
現有的一些集群請求分配器產品和軟體系統，如Cisco LoadDirector、IBM Dispatcher、浪潮英信XS、Tuber Linux等都提供輪詢、最小連接數優先、最快響應優先等方式的均衡算法。
本發明提供的技術方案是一種集群伺服器的動態負載均衡方法，包括以下步驟一、通過仿真測試程序預先測得集群內每臺伺服器的請求響應飽和值以及臨界值，然後輸入分配器的配置參數表；二、在伺服器空載狀態下，通過分配器發送一個請求讀取伺服器當前狀態的完整過程測得集群內每臺伺服器的參照響應時間，並錄入分配器的配置參數表；三、在每臺伺服器開啟一個守護進程，實時監測每一個接入伺服器TCP連接，並且維護一張TCP連接數據表，記錄每個連接的標識符；如果某一連接釋放，則從連接數據表中刪除對應的記錄；若某一連接雙方沒有數據傳輸的時間超時，則認為該連接已非正常終止釋放；四、採樣周期時間通過配置參數設置；五、每個採樣周期時間到時，分配器通過UDP協議向所有伺服器廣播讀取請求任務，並記錄請求發送時間；六、伺服器接收到廣播請求後，將當前記錄的伺服器狀態信息回傳給分配器；七、分配器接收每個伺服器的響應信息，並計算響應的完成時間，以此作為當前負載計算公式中的參數；如果，某臺伺服器在規定的時間內未能成功做出響應，則該伺服器被視為負載超重，不參與下一個周期的分配權值計算，即不被分配請求任務；八、分配器根據得到的信息計算每臺伺服器的負載權值，對進入臨界狀態的伺服器，在其負載權值中加入遞減因子；九、根據所有伺服器的平均負載權值計算在下一個周期要達到負載均衡每臺伺服器所應有的分配權值；十、將計算出的每臺伺服器的分配權值分配一個概率空間，存入對應的概率空間表；重新啟動計時周期；十一、當一個新的請求任務達到分配器時，計算出一個
間的隨機數，根據該隨機數匹配的概率空間，選定對應的伺服器，將新的請求任務轉發到被選定的伺服器；十二、當計時周期到後，重複廣播發送讀取伺服器狀態信息的請求及計算過程，既轉到第五步循環。
本發明的特點通過請求響應連接的飽和值和對當前響應連接數的修正，更準確地表現了伺服器當前的負載狀態；通過臨界遞減因子，加速減少分配給進入臨界狀態伺服器的請求任務數量，有效地抑制了「拒絕服務」現象的發生；通過隨機概率分配方式，在請求達到個數不確定的情況下，避免了採用某種固定模式可能產生的將多個請求連續分配到同一臺伺服器上的現象；所有計算參數均可以通過實際測試得到，避免了人為配置參數的不確定因素。本發明方法簡單、執行效率高，適用於異構集群系統、多媒體流服務的動態負載均衡，可有效提高集群伺服器系統的工作效率。
從理論上可以證明一個集群系統只有在每臺伺服器所分配的負載與其固有的處理能力成比例時，整個系統達到負載均衡，此時系統工作效率最高。設集群中某臺伺服器Si(i＝1，2，…，m)的固有處理能力為ωi，伺服器當前的請求負載為Li，那麼集群系統達到負載均衡時有L11==Lii==Lmm]]>理論推導和證明略。根據這一理論，本發明提出並實現了一個新的負載均衡方法。將伺服器Si的當前負載與其固有能力之比作為該伺服器Si的當前負載權值，記為WLi=Lii]]>。當集群系統達到負載均衡時，有WL1=WL2=WLm]]>。
可以看出，在負載權值的作用下，集群內所有伺服器都按比例增加或減少被分配的負載，始終朝著達到負載均衡的目標努力。2、負載權值的等效變換但實際中每臺伺服器並不可能將所有的(固有)處理能力都用於響應請求任務，一部分能力要用於維持系統自身的運轉所用。那麼一臺伺服器究竟有多少固有能力用於響應請求任務？首先，看一個實驗的具體情況，如
圖1、圖2所示。
從圖1可以發現，當伺服器中單位時間內到達的請求連接個數達到一定值時，請求連接個數將不再繼續增加。這是因為伺服器為了保護系統不至於死機而採取的一種措施，也稱「拒絕服務」現象。我們稱其為伺服器請求連接的飽和值Cmaxi。另外，從圖2中看出，當請求連接個數達到一定值時，平均響應時間明顯加快增長。我們稱其為伺服器工作負荷的臨界值Ccrii，該區間為伺服器工作負荷較重(進入飽和狀態前)的臨界區。
實際上伺服器提供用於響應請求任務的固有能力就是使請求連接數達到飽和值的能力。每一個請求任務是在這個能力中平均分配系統資源。我們以Cmaxi表示達到飽和時的連接數，並以此作為可用於響應請求的固有能力，有i=Cmaxi]]>。
此外，一般情況下伺服器的工作負載可以用伺服器保持的當前活躍連接數來表示，但簡單地用請求連接數來表示伺服器當前負載會存在一定的偏差。如某些被請求對象可能要開啟更多的進程(線程)執行一些特殊的計算或數據查詢工作，這些請求消耗的系統資源大於一般的請求任務；而對於一些只是處於等待狀態的請求連接，其消耗的系統資源又小於請求任務正常工作時的開銷。
我們採取下述方法來修正當前負載表示。
以一個固定負載L在伺服器空載下的響應時間為基準點ΔT，同樣的L在伺服器當前工作負荷的響應時間為Δt，伺服器Si的當前負載可表示為li，有li=tT,]]>理論推倒略。
將變換的伺服器固有能力和當前負載表示代入到前面負載權值的計算式，有WLi=liCmaxi]]>。我們稱其為負載權值的等效變換，它更準確地反映了伺服器的當前負載狀態，固有能力和當前負載都是實際測試的結果。
在實際實現中，我們利用分配器每次獲取後端伺服器狀態的工作負荷為標準負荷L，因為該過程對所有伺服器是一樣的，並且每次所做的處理也是一樣的。3、實現過程(1)、利用我們的集群系統性能仿真測試軟體或通用的集群系統性能測試軟體SpecWeb99、WebBench、Httperf等測試出集群內每臺伺服器的最大飽和連接數和臨界飽和連接數Cmaxi、Ccrii，通過系統管理員輸入集群系統配置參數表。(2)、在伺服器空載狀態下，通過分配器發送一個請求讀取伺服器當前狀態的完整過程測得集群內每臺伺服器的參照響應時間ΔTi，並錄入分配器的配置參數表。(3)、在每臺伺服器開啟一個守護進程，實時監測每一個接入伺服器TCP連接，並且維護一張TCP連接數據表，記錄每個連接的標識符；如果某一連接釋放，則從連接數據表中刪除對應的記錄；若某一連接雙方沒有數據傳輸的時間超時，則認為該連接已非正常終止釋放。(4)、採樣周期時間通過配置參數設置。前端分配器依據配置的採樣周期時間參數，定時激活該算法的執行程序。分配器運行的主函數首先定義一個鍊表遍歷集群內的所有伺服器，每一項包括一個struct_response結構用於存放伺服器返回的當前狀態參數，以及一個指向下一個伺服器的指針p-＞next；程序根據配置的時間參數設置循環時間，循環時間到則調用broadcast函數，否則循環等待。主函數程序流程框圖見附圖3。(5)、每個採樣周期時間到時，分配器通過UDP協議向所有伺服器廣播讀取請求任務，並記錄請求發送時間。廣播請求程序首先將響應的伺服器個數清零，即response_count＝0，並將已做出響應的伺服器標記清零，即flag＝0；然後發出請求響應廣播；發出請求任務之後，啟動接受響應程序。接受響應程序首先啟動定時期，以記錄響應時間超時，對於響應時間超時的伺服器作為負載過重或通信故障處理，不參加後續的負載均衡分配處理過程；定時器啟動後，調用接受線程receive_thread，等待伺服器響應消息的到來。廣播請求任務程序及響應接受任務程序的流程框圖見附圖4。(6)、伺服器接收到廣播請求後，將當前記錄的伺服器狀態信息回傳給分配器。(7)、分配器接收每個伺服器的響應信息。如果全部伺服器已做出響應，則不理睬該響應信息，即p-＞next＝NULL；分配器首先獲取響應伺服器的IP，即p-＞response.ip＝＝回應機器ip；對該伺服器做已響應標記，即p-＞response.fag＝1；計算該伺服器當前做出響應的時間，即求取響應時間Δti，並記入參數表；判斷是否所有伺服器都已做出響應；如果還有伺服器未做出響應則判斷是否響應超時；如果超時時間到，調用超時函數，某臺伺服器在規定的時間內未能成功做出響應，則該伺服器被視為負載超重，不參與下一個周期的分配權值計算，即不被分配請求任務；響應過程結束，關閉定時器，轉入新一輪的調度計算處理，即調用scheduler。接受程序流程框圖見附圖5。(8)、分配器根據得到的信息計算每臺伺服器的負載權值，負載權值計算公式WLi=liCmaxi]]>。對進入臨界狀態的伺服器，在其負載權值中加入遞減因子。
調度程序根據伺服器鍊表判斷每個伺服器是否成功地傳遞了當前狀態信息，p-＞response.flag＝0？；如果伺服器未能成功傳遞狀態信息，則令其負載權值為0，p-＞response.weight＝0，此伺服器的分配概率將為0。對每臺成功傳遞了狀態信息的伺服器需判斷其是否進入臨界負載狀態，p-＞response.n＞＝Ccri。為了避免伺服器出現「拒絕服務」現象，我們在伺服器系統進入臨界區後，通過加倍減少再分配請求任務個數來抑制負載增加速度的方法，也稱作臨界加速遞減算法。計算臨界遞減因子δ，公式如下 其中Ccrii為伺服器Si的臨界值，ni為伺服器當前實際存活的響應個數，當負載進入臨界區(即niCcrii]]>)後，遞減因子開始啟動。公式中的1-CcriiCmaxi]]>為伺服器的臨界深度，不同的伺服器臨界深度不同，負載繼續增加的速度也不一樣，所以，我們用參數σ來調整。根據仿真實驗，一般σ的取值為2或3較為合適。
重新計算負載權值。採用增加臨界伺服器的負載權值來達到抑制分配的請求任務個數的目的，在負載權值計算公式中加入遞減因子，有WLi=liCmaxi+]]>。保存新的負載權值為p-＞response.WL。
轉入處理下一個伺服器，p＝p-＞next；判斷是否所有伺服器處理結束，p-＞next＝NULL？；全部伺服器處理結束轉下一步。
根據所有伺服器的平均負載權值計算在下一個周期要達到負載均衡每臺伺服器所應有的分配權值。
計算平均負載權值。集群系統當前平均負載權值WL，有WL=1Mi=1MWLi]]>。
負載權值反映了集群中各臺伺服器當前的負載狀況，在算法實施過程中還需要根據負載權值和每臺伺服器之間存在的差異，確定在下一個採樣周期內實際應該分配給每臺伺服器請求任務的比例，這樣才能保證集群系統中的所有伺服器的負載按比例協調增加或減少，實現負載的平衡調度。
由於，無法事先確定下一個採樣周期內會有多少個請求任務到達，因此，將按照每臺伺服器的能力確定其接收請求任務比例，該比例值也稱為伺服器當前狀況的分配權值。
為達到負載平衡伺服器實際調整後應保持的響應個數 有n~i=WLWLini,]]>公式的推導略。
計算分配權值。有了每臺伺服器應被分配的請求任務個數，就可以方便地確定每臺伺服器應具有的分配比例，也即分配權值WAi，有WAi=n~ii=1Mn~i]]>。(10)、將計算出的每臺伺服器的分配權值分配一個概率空間，存入對應的概率空間表，即計算各機器的分配概率p；重新啟動計時周期。
由於分配權值之間不是成整數的比例關係(實際中每臺伺服器能力的差異也不可能是整數比例關係)，為了實現更準確的負載調度，我們採用隨機概率的請求任務分配方式。
上述過程(8)、(9)、(10)的程序流程框圖見附圖6。
按照分配權值為每臺伺服器畫定一個概率空間，空間的大小就是每臺伺服器當前的分配權值。附圖7給出了4臺分配權值分別為0.1、0.15、0.25、0.5的伺服器的概率空間。(11)、當一個新的請求任務達到分配器時，計算出一個
間的隨機數，根據該隨機數匹配的概率空間，選定對應的伺服器，將新的請求任務轉發到被選定的伺服器。
由於無法預先確定將要到達的請求個數，所以採用隨機概率分配轉發方式既可以避免固定分配格式造成的分配不均現象，也可以保證具有較高分配權值的伺服器分得更多的請求任務。
分配程序定義一個結構wvalue，該結構包含所有伺服器的分配概率pro；定義的伺服器鍊表遍歷所有伺服器，包括伺服器所包含的wvalue，定義指向鍊表的指針p。
計算
間的隨即數e；判斷當前指針指向的伺服器的分配概率是否為0，p所指的機器的pro＝0？；如果為0，轉向下一個伺服器；不為0則判斷e是否落在其所指的概率空間內，p-＞wvalue.pro＜e＜＝q-＞wvalue.pro；如果不在則轉入取下一個伺服器；如果在則命中該伺服器，返回指定的伺服器q。該伺服器作為此次分配轉發的對象。
上述過程的程序流程框圖見附圖8。(12)、如果沒有新的請求到達，則等待計時，當計時周期到後，重複廣播發送讀取伺服器狀態信息的請求及計算過程，既轉到第五步循環。
權利要求
一種集群伺服器的動態負載均衡方法，其特徵是，包括以下步驟
一、通過仿真測試程序預先測得集群內每臺伺服器的請求響應飽和值以及臨界值，然後輸入分配器的配置參數表；
二、在伺服器空載狀態下通過分配器發送一個請求讀取伺服器當前狀態的完整過程測得集群內每臺伺服器的參照響應時間，並錄入分配器的配置參數表；
三、在每臺伺服器開啟一個守護進程，實時監測每一個接入伺服器TCP連接，並且維護一張TCP連接數據表，記錄每個連接的標識符；如果某一連接釋放，則從連接數據表中刪除對應的記錄；若某一連接雙方沒有數據傳輸的時間超時，則認為該連接已非正常終止釋放；
四、採樣周期時間通過配置參數設置；
五、每個採樣周期時間到時，分配器通過UDP協議向所有伺服器廣播讀取請求任務，並記錄請求發送時間；
六、伺服器接收到廣播請求後，將當前記錄的伺服器狀態信息回傳給分配器；
七、分配器接收每個伺服器的響應信息，並計算響應的完成時間，以此作為當前負載計算公式中的參數；如果，某臺伺服器在規定的時間內未能成功做出響應，則該伺服器被視為負載超重，不參與下一個周期的分配權值計算，即不被分配請求任務；
八、分配器根據得到的信息計算每臺伺服器的負載權值，對進入臨界狀態的伺服器，在其負載權值中加入遞減因子；
九、根據所有伺服器的平均負載權值計算在下一個周期要達到負載均衡每臺伺服器所應有的分配權值；
十、將計算出的每臺伺服器的分配權值分配一個概率空間，存入對應的概率空間表；重新啟動計時周期；
十一、當一個新的請求任務達到分配器時，計算出一個
間的隨機數，根據該隨機數匹配的概率空間，選定對應的伺服器，將新的請求任務轉發到被選定的伺服器；
十二、當計時周期到後，重複廣播發送讀取伺服器狀態信息的請求及計算過程，既轉到第五步循環。
全文摘要
本發明涉及一種集群伺服器的動態負載均衡方法。本發明通過請求響應連接的飽和值和對當前響應連接數的修正，更準確地表現了伺服器當前的負載狀態；通過臨界遞減因子，加速減少分配給進入臨界狀態伺服器的請求任務數量，有效地抑制了「拒絕服務」現象的發生；通過隨機概率分配方式，在請求達到個數不確定的情況下，避免了採用某種固定模式可能產生的將多個請求連續分配到同一臺伺服器上的現象；所有計算參數均可以通過實際測試得到，避免了人為配置參數的不確定因素。本發明方法簡單、執行效率高，適用於異構集群系統、多媒體流服務的動態負載均衡，可有效提高集群伺服器系統的工作效率。
文檔編號G06F15/16GK1434393SQ0311866
公開日2003年8月6日 申請日期2003年2月24日 優先權日2003年2月24日
發明者郭成城, 晏蒲柳, 周建國, 熊智, 易奇娜 申請人:武漢大學