前言：當Web伺服器集群（Web Server Farm）的利用率出現傾斜（Skew）狀況時，便意謂著少數伺服器業已呈現應接不暇的現象，但在同一時刻，其他伺服器卻處於閒置的狀態，如此一來，用戶在不耐久候的前提下，即有可能心生埋怨，並對該系統的服務品質留下極為負面的印象；可以想見，絕大多數網路應用服務的提供者，都不樂見此事發生。
意欲避免Web伺服器集群負載不均，其實非輕而易舉之事，此乃由於，就本質而論，TCP/IP流量原本即呈現波浪走勢，甚難憑制式化的規則加以掌控，再者，隱含於每一條TCP Link背後的服務請求型態，也呈現著至為紊亂、多元化的走向，各個行為所對應到資源消耗需求，自然也不甚一致，在此情況下，倘若在Linux Virtual Server（LVS）環境之中，單憑系統核心裡頭IP負載平衡機制－IPVS所支援的制式演算法，恐難求取最佳平衡點，緣於此故，本文特就諸多相關技術文獻加以彙整、歸納，牽引出動態回饋式負載平衡（Dynamic-feedback Load Balancing）演算法，期望藉由該技術運用之道的闡述，協助用戶化解此一僵局。
在進入動態回饋式負載平衡演算法的議題之前，先就當前大多數Web運算環境的一些概況加以說明。此處必須強調的是，之所以採行動態回饋式負載平衡演算法，並非是將IPVS調度機制當中的所有演算法全都拋諸一旁，換言之，不同演算技術之間，並無相互取代關係，反倒會相輔相成。
以LVS集群環境而論，目前欲將所有來自於客戶端（Clinet）的服務請求，均衡地調度至集群當中的各台Web伺服器，基本上可從系統核心層面的IPVS出發，而IPVS目前所能支援的連結調度演算技術，包括循環式排程演算法（Round-Robin Scheduling）、加權循環式排程演算法（Weighted Round-Robin Scheduling）、最小連結數排程演算法（Least-Connection Scheduling）、加權最小連結數排程演算法（Weighted Least-Connection Scheduling）、基於位置最少連線排程演算法（Locality-Based Least-Connection Scheduling）、帶複製的基於位置最少連線排程演算法（Locality-Based Least Connections with Replication Scheduling）、目地雜湊排程演算法（Destination Hashing Scheduling），以及來源雜湊排程演算法（Source Hashing Scheduling）等共計8項，其中又以加權循環式排程、加權最小連結數排程等2項技術，被使用到的機率相對較大。
加權循環式、加權最小連結數等排程技術之介紹
所謂加權循環式排程演算法，旨在化解伺服器之間效能不一的狀況，主要是以相對應的權值，作為各台伺服器處理效能的表徵，一般而言，預設（Default）權值為1。
假使伺服器甲的權值為1，而伺服器乙的權值為2，即表示伺服器甲的處理效能，為乙的一半而已；論及加權循環式排程演算法，便是依照權值的高低，佐以循環排程的方式，從而將各個服務請求，分配至各台伺服器加以執行，而權值較高的伺服器，其所能處理的連結數目，將比權值較低的伺服器來得多，至於權值相同的伺服器，則可處理同等數目的連結數。
在介紹加權循環式排程演算法的進行流程之前，先進行前提假設：有1組Web伺服器集群Q = {Q0, Q1, Q2, …, Qn-1}，此時即可以W（Qi）作為伺服器Qi的權值表徵，接著以i表示上一次選擇的伺服器，cw表示目前排程的權值，max（Q）表示Q伺服器集群當中所有伺服器的最大權值，qcd（Q）表示Q伺服器集群當中所有伺服器權值的最大公約數字，而變數i初始化數值為-1，cw初始化數值為0。如此一來，其流程大致如下圖示。
至於加權最小連結數排程演算法，則意謂著最小連結排程的超集合，而各台伺服器皆以相對應的權值，表示其處理效能，Default權值仍為1，而企業系統管理員可以動態地針對伺服器的權值加以調整。
該演算技術在排程新連結之際，都將儘可能使伺服器的已建立連結數，與其權值成一定比例。而在進入加權最小連結數排程演算法的流程闡述之前，同樣先做一些前提假設：假設有1組Web伺服器集群Q = {Q0, Q1, Q2, …, Qn-1}，W（Qi）作為伺服器Qi的權值表徵，C（Qi）代表伺服器Qi當下的連結數，而所有伺服器目前連結數目的總和為CSUM =ΣC（Qi）（i=0,1,2,3,…,n-1）。
當前新連結請求，將會被分配至伺服器Qm，而Qm必須能夠滿足下列條件。值得一提的是，W（Qi）不得為0。
只不過，除法計算所須耗用的處理器時脈環，通常會比乘法計算多出許多，而且Linux核心之中，除法計算也不被允許，在此前提下，伺服器的權值都會大於0，故原本所採行C（Qm）/ W（Qm）> C（Qi）/ W（Qi）之判斷條件，不妨可加以優化到下列結果，並同時保證當伺服器權值為0的話，該伺服器便不會進入排程。
歷經這一微幅調整後，加權最小連結數排程演算法的執行流程，便可被精簡到下列步驟。
Web連結請求迥異甚大 傾斜狀況在所難免
分析多數Web伺服器之所以出現負載失衡狀態，箇中原因其實不難理解。首先，論及TCP/IP流量的特徵，即充滿了濃厚的波浪型樣貌，亦即可能在一段較長時間的小流量後，便出現一段大流量連結請求的湧入，這波過後，或將回歸到小流量狀態，猶如週期性的波浪理論一般，在WAN世界如此，在LAN環境亦可套用此一原理，著實讓人捉摸不定；正因如此，本文才會以動態回饋式負載平衡演算技術為初衷，此乃由於，惟有透過該項演算法，方能讓伺服器集群，被動態調教成為「足以應付不定性的Web波浪」。
此外，探究每一客戶端的TCP連結行為，其背後都會植基於不同的服務請求，每個請求所需的處理時間、以及所需消耗的運算資源，由於變數甚多，舉凡請求服務的型態、當下的網路頻寬與伺服器資源利用情況，都有可能造成重大影響，故其結果往往多所迥異。
在此情況下，一些負載相對吃重的請求，由於需要進行較高密集的查詢，甚或需要造訪資料庫，故其回應速度難免相對遲緩；相反的，如果只需要進行簡單計算，抑或僅欲讀取1個HTML頁面，則回應速度便會相對來得快。
由此，系統管理員將不難理解，礙於各項請求被處理時程之巨大差異，即可能導致伺服器使用狀況的嚴重傾斜，亦即負載失衡狀態。在此舉個例子，假設1個Web頁面係由甲、乙、丙、丁等4個檔案所組合而成，而其間甲為大型圖像檔案，此時客戶端瀏覽器欲同時造訪此一網頁，即需要建立4個連結，同時對這4個檔案加以讀取，若僅有單一客戶端從事此項連結行為，或許還在控制範圍之內，但如果同一時間內，有許多客戶端都連結到該網頁，情況便將失控。
最糟的狀況是，所有攸關甲檔案的請求，將被分派到同一台伺服器，而該台伺服器的負載頓時飆高，甚至已經窮於應付，故有些請求貯列被拖得相當長，且還不停地接收到新的請求，但此時其他伺服器卻處於閒置狀態；值此時刻，便即Web集群內含再多伺服器，亦難營造出令前端用戶滿意的服務品質。
值得一提的是，前述這般失衡狀態，若是對應到常見的簡單連結調度方式，便可能會使得Web伺服器傾斜狀況更加顯著，假設用戶採行若採用循環式排程演算法，而且其伺服器集群係由4台伺服器所組合而成，則其間某1台伺服器，極可能總是接收到猶如前例甲檔案（大型圖像檔案）的請求，從而造成整體系統資源利用率的偏低，亦即4台伺服器負載不均的狀況。
啟用動態式回饋負載平衡 化解伺服器集群失衡現象
為解決前述種種亂象，用戶即不妨可考慮採用動態式回饋負載平衡演算法，來彌補簡單連結調度方式之不足，此乃由於，這項演算法有考慮到伺服器的即時負載與回應狀況，會就Web伺服器之間處理請求的比重，做出持續性的調整，據以避免部分伺服器遭逢超載狀況時，依然收到大量請求之現象，把工作任務均攤給集群中的其他成員，進而拉抬整體系統的吞吐效率。
茲以下列圖示，闡述動態式回饋負載平衡的工作環境。
在上圖當中，係於負載調度器之上，運行著Monitor Daemon進程，並由此項機制來負責監控與蒐集各台伺服器的負載資訊，此外還能夠依據多個負載資訊，計算出1個綜合性的負載值；換言之，當Monitor Daemon將各台伺服器的綜合負載值，以及當下的權值算出1組新的權值後，倘若發現新的權值與當前權值之間的差異，大於其所設定的Threshold數值，此時Monitor Daemon便會將該伺服器的權值，設置到系統核心裡頭的IPVS調度機制中。
持平而論，依TCP/IP流量的慣性而論，往往是由許多「短事務」搭配一些「長事務」所組合而成，不過長事務所挾帶的工作負載需求，通常會在整體工作量的結構中，佔有相當高的比例，如此一來，用戶便應採行1種較聰明的負載平衡演算法，方能避免來自於長事務的請求，總是被分派到特定主機來執行，換言之，便是把原本挾帶Burst意味的分布方式，調校成為具備相對勻稱的分布格局；值此時刻，所謂的動態回饋負載平衡演算法，便不失為用以控制新連結的任務分派、以及各台伺服器負載狀況的可行技術。
具體的作法是，假使在IPVS調度機制中，採行加權循環式排程演算法，用以針對新請求連結來進行排程，即可在負載調度器的用戶空間中，運行Monitor Daemon，並由它來定時監視與蒐集各台伺服器的負載資訊，從而根據多個負載資訊，算出1個綜合負載值，如同前面已提及的運作流程。
與此同時，當綜合負載值顯示出，伺服器處於負載吃重之際，則新計算出的權值，將比其當前權值來得小，如此一來，被新分派到該伺服器的請求數目，就會自動減少；相反的，如果綜合負載值顯示某台或某些伺服器，處在利用率偏低的狀態，則新計算出來的權值，自然就會比其當前權值要來得大，故系統即會針對該台或該群伺服器，增加新請求的接收數量排程。
另外，假使新權值與當前權值的差異，比原本設定的Threshold數值為大，則Monitor Daemon會將該伺服器的權值，設置到IPVS調度器之中，此後再度過了一定的時間間距後，Monitor Daemon即再度查詢各台伺服器的負載狀況，同時再就伺服器的權值進行相對應的調整，而且會循週期性模式反覆進行，究其終極目的，無非是讓伺服器集群得以維持較佳的利用率。
因此，在運行加權循環式排程演算法的狀態下，當伺服器的權值歸零之後，則其已建立的連結，仍將持續獲得該伺服器所提供之服務，但新的連結請求，就不會被排程至該伺服器；此時系統管理員也可考慮把其中1台伺服器的權值設定為0，讓該伺服器完完全全地安靜下來，當已有的連結都處理完畢後，就可以把該台伺服器予以切割，然後對其進行硬體升級或更新等維護事務，畢竟維護工作對於系統管理而言，著實為不可或缺的一環。
在此前提下，用戶若欲於動態式回饋負載平衡機制中，確保一些必要性的維護工作得以順利運行的話，則當伺服器的權值為0時，便不應對伺服器的權值進行任何調整。
而在動態式回饋負載平衡演算法的使用過程中，如前所述，有牽涉到綜合負載值的計算，有關於這一數值的演算來源，主要係含括2種型態的負載資訊，一為輸入指標，另一則是伺服器指標；其中輸入指標必須由調度器上加以蒐集，至於伺服器指標，則代表存在於伺服器之上的各項負載資訊。值得一提的，採行綜合負載的計算方式，主要理由是為了讓伺服器當前的負載狀況，獲得相對精準的反映，而不同的應用程式運行基礎之上，連帶也將產生不同程度的負載狀態。
如此一來，藉由各項負載資訊係數的充分引用，即可適度地彰顯出各項負載資訊，處在綜合負載數值之中的輕重，從而俾使系統管理員，能根據不同應用服務的需求，調整各項負載資訊的係數，也讓系統管理員能更加方便地就蒐集負載資訊的時間間距部分，加以精確地設定。
所謂輸入指標，主要是在單位時間裡頭，伺服器所接收到新連結數目，佔整體平均連結數目的比重關係，是透過調度器加以蒐集而來，因此這一指標等同於伺服器負載狀況的估計值。假設伺服器Si，分別在T1、T2等時段，對應到調度器計數機制的數值為Ci1、Ci2，即可計算出Si伺服器在T2-T1時段內，其所接收到的新請求連結數為Ni = Ci2 - Ci1；如此一來，1組伺服器在T2-T1時段內伺服器Si所接收到新連結數為{Ni}，而伺服器Si的輸入指標INPUTi便是其新連結數、與n台伺服器所接收之平均連結數目的比值，具體公式內容如下。
至於伺服器指標，則是用以記錄存在於各台伺服器的各項負載資訊，譬如代表伺服器當前處理器負載狀況的LOADi、代表伺服器當前磁碟使用狀況的Di、代表伺服器當前記憶體使用狀況的Mi，以及當前進程（Process）數目的Pi；有關於這些資訊，系統管理員可藉由2種途徑加以取得，其一，是從所有的伺服器上所運行的SNMP（Simple Network Management Protocol）服務進程來著手，繼而利用調度器上的Monitor Daemon、透過SNMP向各台伺服器進行查詢，以獲取這些資訊，另外，則是在伺服器上灌裝可負責蒐集這些資訊的代理程式，然後由代理程式定時地向Monitor Daemon回報負載資訊。
假設伺服器在設定的時間間距內，並未做出任何回應，則Monitor Daemon即會認為該伺服器已無力應付新增請求連結，從而在調度器裡頭，將該將伺服器的權值設置為0，讓它不會再繼續接收到新的排程；倘若在下一次資訊蒐集過程中，該伺服器又開始提出回應，則系統便將對其權值進行調整，然後再對這些資料進行處理，使其落在[0, ∞]的區間內，其中1代表負載處於恰到好處的狀態，小於1代表伺服器處於低負載狀況，大於1則代表伺服器處於超載狀況。
值得一提的，伺服器在提供各項應用服務所對應到的回應時間，也堪稱衡量伺服器指標的重要依據之一，因為它較能充分反映伺服器上請求等待佇列的長度，以及面對各個請求的處理時間；意欲蒐集此項數據，仍得透過調度器上的Monitor Daemon，作為客戶端訪問伺服器提供之服務所測得的回應時間；倘若伺服器在設定的時間間距未做出回應，則Monitor Daemon會認為該伺服器已不適合繼續執行任務，進而將該伺服器在調度器中的權值設置為0，如此一來，系統管理員便可依據回應時間進行調整，從而獲得RESPONSEi資訊。
在掌握了DISKi、MEMORYi、PROCESSi、RESPONSEi等數據後，系統管理員便可援引1組可供動態調整的係數－Ri，用以彰顯各項負載參數的重要程度，其中ΣRi = 1，而綜合負載即可藉由下列公式加以計算。當然，假設系統管理員發現到，當前的Ri係數已不能反映實際應用的負載狀況，便可針對該數值持續進行修正，直至取得1組貼近實際狀況的係數為止。
另一方面，不可諱言，若把查詢時間的間隔設定得愈短，就能夠更精確地反映各台伺服器的負載狀況，然而太過密集的話，也容易為調度器、伺服器構成沈重負擔，因此務必在得失之間取得平衡，一般來說，時間間距設定在5∼20秒內，還算是合情合理，過猶不及、都不理想。
借助適當公式 精準計算負載權值
每當任何一台伺服器加入集群環境之際，系統管理員通常對其設定1個初始性的權值，往往以DEFAULT_WEIGHTi來表示，爾後，系統核心當中的IPVS調度機制，亦將優先採用此一權值；然伴隨著伺服器負載狀態的改變，又憑藉動態式回饋負載平衡演算法對其權值進行調整，如果不加以節制，仍有可能讓權值演變成龐大數值，與此同時，系統管理員即有必要針對權值範圍加以限制，可透過[DEFAULT_WEIGHTi, SCALE*DEFAULT_WEIGHTi]公式來實現其限制目的，至於公式中的SCALE，其Default值為10，但會隨時被調整。此後，在Monitor Daemon週期性地執行任務之下，如果DEFAULT_WEIGHTi不是0，而欲查詢該伺服器的各項負載參數，並計算綜合負載值AGGREGATE_LOADi的話，可藉由下列計算公式為之，其計算結果可作為系統管理員用以調整權值之依據。此處附帶說明，公式中的0.95，係表示系統管理員所期望的系統利用率，其中A的Default值為5，但可被動態調整，當綜合負載值等於0.95，伺服器權值也不會改變，但是當綜合負載值大於0.95時，伺服器權值則會變小。
假使新權值比SCALE*DEFAULT_WEIGHTi來得大，系統管理員可將新的權值設定為SCALE*DEFAULT_WEIGHTi，但若新權值與當前權值之間的差距大於原本所設定的Threshold值，便可將新權值設定到IPVS調度參數中，藉此讓權值得以被調整到相對穩定的狀況。
如此一來，當所有伺服器的權值，皆小於各自的DEFAULT_WEIGHT，則意謂全體伺服器集群處在超載狀態，此時有必要加入新的伺服器節點至集群之中，據以分攤繁重的計算任務；相反的，如果所有伺服器的權值都與SCALE*DEFAULT_WEIGHT甚為接近，則意謂當前系統的負載，皆處於相對清閒的狀態，此時較無排程方面的困擾。
附帶說明，Red Hat Enterprise Linux系統之中，有1個名為Piranha的集群管理工具選項（如下圖），其雖然只能涵蓋處理器負載狀況等少數面向，但也可協助系統管理員，用以執行1個簡易型的動態式回饋負載平衡計算，相關計算方式與前述公式頗為神似，就某種程度而論，不失為系統管理員調整權值的參考依據之一。
1 則留言:
演算法是科技的基礎
張貼留言