詳解Linux服務器集群服務器集群系統（二）集群的體系結構本文主要介紹了集群的體系結構。先給出集群的通用體系結構，并討論了其的設計原則和相應的特點；最后將集群應用于建立可伸縮的、、和等網絡服務。.引言

在過去的十幾年中，從幾個研究機構相連為信息共享的網絡發展成為擁有大量應用和服務的全球性網絡，它正成為人們生活中不可缺少的一部分。雖然發展速度很快，但建設和維護大型網絡服務依然是一項挑戰性的任務，因為系統必須是高性能的、高可靠的，尤其當訪問負載不斷增長時，系統必須能被擴展來滿足不斷增長的性能需求。由于缺少建立可伸縮網絡服務的框架和設計方法，這意味著只有擁有非常出色工程和管理人才的機構才能建立和維護大型的網絡服務。針對這種情形，本文先給出集群的通用體系結構，并討論了其的設計原則和相應的特點；最后將集群應用于建立可伸縮的、、和等網絡服務。詳解Linux服務器集群全文共34頁，當前為第1頁。集群的通用體系結構

集群采用負載均衡技術和基于內容請求分發技術。調度器具有很好的吞吐率，將請求均衡地轉移到不同的服務器上執行，且調度器自動屏蔽掉服務器的故障，從而將一組服務器構成一個高性能的、高可用的虛擬服務器。整個服務器集群的結構對客戶是透明的，而且無需修改客戶端和服務器端的程序。詳解Linux服務器集群全文共34頁，當前為第1頁。

圖：集群的體系結構為此，在設計時需要考慮系統的透明性、可伸縮性、高可用性和易管理性。一般來說，集群采用三層結構，其體系結構如圖所示，三層主要組成部分為：負載調度器（），它是整個集群對外面的前端機，負責將客戶的請求發送到一組服務器上執行，而客戶認為服務是來自一個地址（我們可稱之為虛擬地址）上的。服務器池（），是一組真正執行客戶請求的服務器，執行的服務有、、和等。共享存儲（），它為服務器池提供一個共享的存儲區，這樣很容易使得服務器池擁有相同的內容，提供相同的服務。調度器是服務器集群系統的唯一入口點（），它可以采用負載均衡技術、基于內容請求分發技術或者兩者相結合。在負載均衡技術中，需要服務器池擁有相同的內容提供相同的服務。當客戶請求到達時，調度器只根據服務器負載情況和設定的調度算法從服務器池中選出一個服務器，將該請求轉發到選出的服務器，并記錄這個調度；當這個請求的其他報文到達，也會被轉發到前面選出的服務器。在基于內容請求分發技術中，服務器可以提供不同的服務，當客戶請求到達時，調度器可根據請求的內容選擇服務器執行請求。因為所有的操作都是在操作系統核心空間中將完成的，它的調度開銷很小，所以它具有很高的吞吐率。詳解Linux服務器集群全文共34頁，當前為第2頁。服務器池的結點數目是可變的。當整個系統收到的負載超過目前所有結點的處理能力時，可以在服務器池中增加服務器來滿足不斷增長的請求負載。對大多數網絡服務來說，請求間不存在很強的相關性，請求可以在不同的結點上并行執行，所以整個系統的性能基本上可以隨著服務器池的結點數目增加而線性增長。詳解Linux服務器集群全文共34頁，當前為第2頁。共享存儲通常是數據庫、網絡文件系統或者分布式文件系統。服務器結點需要動態更新的數據一般存儲在數據庫系統中，同時數據庫會保證并發訪問時數據的一致性。靜態的數據可以存儲在網絡文件系統（如）中，但網絡文件系統的伸縮能力有限，一般來說，服務器只能支持個繁忙的服務器結點。對于規模較大的集群系統，可以考慮用分布式文件系統，如[]、[]、[]和[]等。分布式文件系統可為各服務器提供共享的存儲區，它們訪問分布式文件系統就像訪問本地文件系統一樣，同時分布式文件系統可提供良好的伸縮性和可用性。此外，當不同服務器上的應用程序同時讀寫訪問分布式文件系統上同一資源時，應用程序的訪問沖突需要消解才能使得資源處于一致狀態。這需要一個分布式鎖管理器（），它可能是分布式文件系統內部提供的，也可能是外部的。開發者在寫應用程序時，可以使用分布式鎖管理器來保證應用程序在不同結點上并發訪問的一致性。負載調度器、服務器池和共享存儲系統通過高速網絡相連接，如交換網絡、和網絡等。使用高速的網絡，主要為避免當系統規模擴大時互聯網絡成為整個系統的瓶頸。是為系統管理員提供整個集群系統的監視器，它可以監視系統的狀態。是基于瀏覽器的，所以無論管理員在本地還是異地都可以監測系統的狀況。為了安全的原因，瀏覽器要通過（）協議和身份認證后，才能進行系統監測，并進行系統的配置和管理。.為什么使用層次的體系結構層次的體系結構可以使得層與層之間相互獨立，每一個層次提供不同的功能，在一個層次可以重用不同的已有軟件。例如，調度器層提供了負載平衡、可伸縮性和高可用性等，在服務器層可以運行不同的網絡服務，如、、和等，來提供不同的可伸縮網絡服務。明確的功能劃分和清晰的層次結構使得系統容易建設，以后整個系統容易維護，而且系統的性能容易被擴展。.為什么是共享存儲共享存儲如分布式文件系統在這個集群系統是可選項。當網絡服務需要有相同的內容，共享存儲是很好的選擇，否則每臺服務器需要將相同的內容復制到本地硬盤上。當系統存儲的內容越多，這種無共享結構（）的代價越大，因為每臺服務器需要一樣大的存儲空間，任何的更新需要涉及到每臺服務器，系統的維護代價會非常高。共享存儲為服務器組提供統一的存儲空間，這使得系統的內容維護工作比較輕松，如只需要更新共享存儲中的頁面，對所有的服務器都有效。分布式文件系統提供良好的伸縮性和可用性，當分布式文件系統的存儲空間增加時，所有服務器的存儲空間也隨之增大。對于大多數服務來說，它們都是讀密集型（）的應用，分布式文件系統在每臺服務器使用本地硬盤作（如的空間），可以使得訪問分布式文件系統本地的速度接近于訪問本地硬盤。此外，存儲硬件技術的發展也促使從無共享的集群向共享存儲的集群遷移。存儲區域網（）技術解決了集群的每個結點可以直接連接共享一個龐大的硬盤陣列，硬件廠商也提供多種硬盤共享技術，如光纖通道（）、共享（）。是一個通用的高性能規范，使得存儲區域網中以更低的延時傳輸消息和集群通訊消息，并且提供很好的伸縮性。得到絕大多數的大廠商的支持，如、、、、、和等，它正在成為一個業界的標準。這些技術的發展使得共享存儲變得容易，規模生產也會使得成本逐步降低。詳解Linux服務器集群全文共34頁，當前為第3頁。.高可用性詳解Linux服務器集群全文共34頁，當前為第3頁。集群系統的特點是它在軟硬件上都有冗余。系統的高可用性可以通過檢測節點或服務進程故障和正確地重置系統來實現，使得系統收到的請求能被存活的結點處理。通常，我們在調度器上有資源監測進程來時刻監視各個服務器結點的健康狀況。當服務器對不可達時或者探測她的網絡服務在指定的時間沒有響應時，資源監測進程通知操作系統內核將該服務器從調度列表中刪除或者失效。這樣，新的服務請求就不會被調度到壞的結點。資源監測進程能通過電子郵件或傳呼機向管理員報告故障。一旦監測進程到服務器恢復工作，通知調度器將其加入調度列表進行調度。另外，通過系統提供的管理程序，管理員可發命令隨時可以將新機器加入服務來提高系統的處理性能，也可以將已有的服務器切出服務，以便對服務器進行系統維護。現在前端的調度器有可能成為系統的單一失效點（）。一般來說，調度器的可靠性較高，因為調度器上運行的程序較少而且大部分程序早已經遍歷過，但我們不能排除硬件老化、網絡線路或者人為誤操作等主要故障。為了避免調度器失效而導致整個系統不能工作，我們需要設立一個從調度器作為主調度器的備份。兩個心跳（）進程[]分別在主、從調度器上運行，它們通過串口線和等心跳線來相互定時地匯報各自的健康狀況。當從調度器不能聽得主調度器的心跳時，從調度器通過欺騙（）來接管集群對外的，同時接管主調度器的工作來提供負載調度服務。當主調度器恢復時，這里有兩種方法，一是主調度器自動變成從調度器，二是從調度器釋放，主調度器收回并提供負載調度服務。這里，多條心跳線可以使得因心跳線故障導致誤判（即從調度器認為主調度器已經失效，其實主調度器還在正常工作）的概論降到最低。通常，當主調度器失效時，主調度器上所有已建立連接的狀態信息將丟失，已有的連接會中斷。客戶需要向重新連接，從調度器才會將新連接調度到各個服務器上，這對客戶會造成一定的不便。為此，調度器在內核中實現一種高效狀態同步機制，將主調度器的狀態信息及時地同步到從調度器。當從調度器接管時，絕大部分已建立的連接會持續下去。.可伸縮服務詳解Linux服務器集群全文共34頁，當前為第4頁。基于的集群的體系結構如圖所示：第一層是負載調度器，一般采用負載均衡技術，可以使得整個系統有較高的吞吐率；第二層是服務器池，在每個結點上可以分別運行服務或服務、或者兩者都運行；第三層是共享存儲，它可以是數據庫，可以是網絡文件系統或分布式文件系統，或者是三者的混合。集群中各結點是通過高速網絡相連接的。詳解Linux服務器集群全文共34頁，當前為第4頁。

圖：基于的集群對于動態頁面（如、和等），需要訪問的動態數據一般存儲在數據庫服務器中。數據庫服務運行在獨立的服務器上，為所有服務器共享。無論同一服務器上多個動態頁面訪問同一數據，還是不同服務器上多個動態頁面訪問同一數據，數據庫服務器有鎖機制使得這些訪問有序地進行，從而保證數據的一致性。對于靜態的頁面和文件（如文檔和圖片等），可以存儲在網絡文件系統或者分布式文件系統中。至于選擇哪一種，看系統的規模和需求而定。通過共享的網絡文件系統或者分布式文件系統，可以看到統一的文檔存儲空間，維護和更新頁面比較方便，對共享存儲中頁面的修改對所有的服務器都有效。在這種結構下，當所有服務器結點超載時，管理員可以很快地加入新的服務器結點來處理請求，而無需將文檔等復制到結點的本地硬盤上。詳解Linux服務器集群全文共34頁，當前為第5頁。有些服務可能用到，它是將數據存儲在客戶的瀏覽器來追蹤和標識客戶的機制。使用后，來同一客戶的不同連接存在相關性，這些連接必須被發送到同一服務器。一些服務使用安全的協議，它是協議加（）協議。另有些服務可能使用安全的協議，它是協議加協議。當客戶訪問服務（的缺省端口為）時，會先建立一個連接，來交換對稱公鑰加密的證書并協商一個，來加密以后的會話。在的生命周期內，后續的所有連接都使用這個，所以同一客戶的不同連接也存在相關性。針對這些需要，調度器提供了持久服務的功能，它可以使得在設定的時間內，來自同一地址的不同連接會被發送到集群中同一個服務器結點，可以很好地解決客戶連接的相關性問題。詳解Linux服務器集群全文共34頁，當前為第5頁。.可伸縮媒體服務基于的媒體集群的體系結構如圖所示：第一層是負載調度器，一般采用負載均衡技術，可以使得整個系統有較高的吞吐率；第二層是服務器池，在每個結點上可以運行相應的媒體服務；第三層是共享存儲，通過網絡文件系統分布式文件系統存儲媒體節目。集群中各結點是通過高速網絡相連接。

圖：基于的媒體集群負載調度器一般使用直接路由方法（即方法，將在以后文章中詳細敘述），來架構媒體集群系統。調度器將媒體服務請求較均衡地分發到各個服務器上，而媒體服務器將響應數據直接返回給客戶，這樣可以使得整個媒體集群系統具有很好的伸縮性。詳解Linux服務器集群全文共34頁，當前為第6頁。媒體服務器可以運行各種媒體服務軟件。目前，集群對于、和媒體服務都有很好的支持，都有真實的系統在運行。一般來說，流媒體服務都會使用一個連接（如協議：）進行帶寬的協商和流速的控制，通過將流數據返回客戶。這里，調度器提供功能將和集中考慮，保證來自同一客戶的媒體和連接會被轉發到集群中同一臺媒體服務器，使得媒體服務準確無誤地進行。詳解Linux服務器集群全文共34頁，當前為第6頁。共享存儲是媒體集群系統中最關鍵的問題，因為媒體文件往往非常大（一部片子需要幾百兆到幾千兆的存儲空間），這對存儲的容量和讀的速度有較高的要求。對于規模較小的媒體集群系統，例如有至個媒體服務器結點，存儲系統可以考慮用帶千兆網卡的服務器，使用軟件和日志型文件系統，再運行內核的服務，會有不錯的效果。對于規模較大的媒體集群系統，最好選擇對文件分段（）存儲和文件緩存有較好支持的分布式文件系統；媒體文件分段存儲在分布式文件系統的多個存儲結點上，可以提高文件系統的性能和存儲結點間的負載均衡；媒體文件在媒體服務器上自動地被緩存，可提高文件的訪問速度。否則，可以考慮自己在媒體服務器上開發相應的工具，如緩存工具能定時地統計出最近的熱點媒體文件，將熱點文件復制到本地硬盤上，并替換緩存中的非熱點文件，最后通知其他媒體服務器結點它所緩存的媒體文件以及負載情況；在媒體服務器上有應用層調度工具，它收到客戶的媒體服務請求，若所請求的媒體文件緩存在本地硬盤上，則直接轉給本地媒體服務進程服務，否則先考慮該文件是否被其他媒體服務器緩存；如該文件被其他服務器緩存并且該服務器不忙，則將請求轉給該服務器上的媒體服務進程處理，否則直接轉給本地媒體服務進程，從后端的共享存儲中讀出媒體文件。共享存儲的好處是媒體文件的管理人員看到統一的存儲空間，使得媒體文件維護工作比較方便。當客戶訪問不斷增加使得整個系統超載時，管理員可以很快地加入新的媒體服務器結點來處理請求。公司以其高壓縮比的音頻視頻格式、媒體服務器和媒體播放器而聞名。公司正在使用以上結構將由多臺服務器組成的可伸縮和媒體集群，為其全球用戶提供和音頻視頻服務。公司的高級技術主管聲稱擊敗所有他們嘗試過的商品化負載均衡產品[]。.可伸縮服務有效的網絡系統可以大大地減少網絡流量、降低響應延時以及服務器的負載。但是，若服務器超載而不能及時地處理請求，反而會增加響應延時。所以，服務的可伸縮性很重要，當系統負載不斷增長時，整個系統能被擴展來提高服務的處理能力。尤其，在主干網上的服務可能需要幾個的吞吐率，單臺服務器（例如目前最高端的服務器）遠不能達到這個吞吐率。可見，通過服務器集群實現可伸縮服務是很有效的方法，也是性能價格比最高的方法。詳解Linux服務器集群全文共34頁，當前為第7頁。基于的集群的體系結構如圖所示：第一層是負載調度器，一般采用負載均衡技術，可以使得整個系統有較高的吞吐率；第二層是服務器池，一般服務器放置在接近主干連接處，它們可以分布在不同的網絡中。調度器可以有多個，放在離客戶接近的地方。詳解Linux服務器集群全文共34頁，當前為第7頁。

圖：基于的集群負載調度器一般使用隧道方法（即方法，將在以后文章中詳細敘述），來架構集群系統，因為服務器可能被放置不同的地方（例如在接近主干連接處），而調度器與服務器池可能不在同一個物理網絡中。采用方法，調度器只調度請求，而服務器將響應數據直接返回給客戶。在請求對象不能在本地命中的情況下，服務器要向源服務器發請求，將結果取回，最后將結果返回給客戶；若采用技術的商品化調度器，需要四次進出調度器，完成這個請求。而用方法（或者方法），調度器只調度一次請求，其他三次都由服務器直接訪問完成。所以，這種方法對集群系統特別有效。詳解Linux服務器集群全文共34頁，當前為第8頁。服務器采用本地硬盤來存儲可緩存的對象，因為存儲可緩存的對象是寫操作，且占有一定的比例，通過本地硬盤可以提高的訪問速度。服務器間有專用的多播通道（），通過協議（）來交互信息。當一臺服務器在本地硬盤中未命中當前請求時，它可以通過查詢其他服務器是否有請求對象的副本，若存在，則從鄰近的服務器取該對象的副本，這樣可以進一步提高服務的命中率。詳解Linux服務器集群全文共34頁，當前為第8頁。為多所大學和地區服務的英國國家網在年月用以上結構實現可伸縮的集群[]，只用了原有多臺相互獨立服務器的一半，用戶反映網絡速度跟夏天一樣快（學生放暑假）。可見，通過負載調度可以摸平單臺服務器訪問的毛刺（），提高整個系統的資源利用率。.可伸縮郵件服務詳解Linux服務器集群全文共34頁，當前為第9頁。隨著用戶不斷增長，很多面臨他們郵件服務器超載的問題。當郵件服務器不能容納更多的用戶帳號時，有些買更高檔的服務器來代替原有的，將原有服務器的信息（如用戶郵件）遷移到新服務器是很繁瑣的工作，會造成服務的中斷；有些設置新的服務器和新的郵件域名，新的郵件用戶放置在新的服務器上，如上海電信現在用不同的郵件服務器、到放置用戶的郵件帳號，這樣靜態地將用戶分割到不同的服務器上，會造成郵件服務器負載不平衡，系統的資源利用率低，對用戶來說郵件的地址比較難記。詳解Linux服務器集群全文共34頁，當前為第9頁。

圖：基于的可伸縮郵件集群可以利用框架實現高可伸縮、高可用的郵件服務系統。它的體系結構如圖所示：在前端是一個采用負載均衡技術的負載調度器；第二層是服務器池，有（）服務器和一組郵件服務器。第三層是數據存儲，通過分布式文件系統來存儲用戶的郵件。集群中各結點是通過高速網絡相連接。詳解Linux服務器集群全文共34頁，當前為第10頁。用戶的信息如用戶名、口令、主目錄和郵件容量限額等存儲在服務器中，可以通過讓管理員進行用戶管理。在各個郵件服務器上運行（）、（）、（）和服務。接受和轉發用戶的郵件，服務進程查詢服務器獲得用戶信息，再存儲郵件。和通過服務器獲得用戶信息，口令驗證后，處理用戶的郵件訪問請求。這里，需要有機制避免不同服務器上的、和服務進程對用戶郵件的讀寫沖突。服務是讓用戶通過瀏覽器可以訪問郵件。詳解Linux服務器集群全文共34頁，當前為第10頁。調度器將、、和請求流負載較均衡地分發到各郵件服務器上，從上面各服務的處理流程來看，不管請求被發送到哪一臺郵件服務器處理，其結果是一樣的。這里，將、、和運行在各個郵件服務器上進行集中調度，有利于提高整個系統的資源利用率。系統中可能的瓶頸是服務器，對服務中樹的參數進行優化，再結合高端的服務器，可以獲得較高的性能。若分布式文件系統沒有多個存儲結點間的負載均衡機制，則需要相應的郵件遷移機制來避免郵件訪問的傾斜。這樣，這個集群系統對用戶來說就像一個高性能、高可靠的郵件服務器（例如上海電信只要用一個郵件域名就可以）。當郵件用戶不斷增長時，只要在集群中增加服務器結點和存儲結點。用戶信息的集中存儲使得用戶管理變得容易，且集群系統有利于提高資源利用率。.小結本文給出集群的通用體系結構，并討論了它的設計原則和相應的特點；最后將集群應用于建立可伸縮的、、和網絡服務，并指出了系統架設時應注意的要點。我們將在后續的文章中詳細解釋集群的技術、實現和應用。

服務器集群系統(三)集群中的負載均衡技術本文在分析服務器集群實現虛擬網絡服務的相關技術上，詳細描述了集群中實現的三種負載均衡技術（、和）的工作原理，以及它們的優缺點。.前言

在前面文章中，講述了可伸縮網絡服務的幾種結構，它們都需要一個前端的負載調度器（或者多個進行主從備份）。我們先分析實現虛擬網絡服務的主要技術，指出負載均衡技術是在負載調度器的實現技術中效率最高的。在已有的負載均衡技術中，主要有通過網絡地址轉換（）將一組服務器構成一個高性能的、高可用的虛擬服務器，我們稱之為技術（）。在分析的缺點和網絡服務的非對稱性的基礎上，我們提出了通過隧道實現虛擬服務器的方法（），和通過直接路由實現虛擬服務器的方法（），它們可以極大地提高系統的伸縮性。、和技術是集群中實現的三種負載均衡技術，我們將在文章中詳細描述它們的工作原理和各自的優缺點。在以下描述中，我們稱客戶的和服務器的之間的數據通訊為連接，無論它們是使用還是協議。下面簡述當前用服務器集群實現高可伸縮、高可用網絡服務的幾種負載調度方法，并列舉幾個在這方面有代表性的研究項目。.實現虛擬服務的相關方法

在網絡服務中，一端是客戶程序，另一端是服務程序，在中間可能有代理程序。由此看來，可以在不同的層次上實現多臺服務器的負載均衡。用集群解決網絡服務性能問題的現有方法主要分為以下四類。詳解Linux服務器集群全文共34頁，當前為第11頁。.基于的解決方法詳解Linux服務器集群全文共34頁，當前為第11頁。的可伸縮的服務器系統就是最早基于（）的原型系統[]。它的結構和工作流程如下圖所示：

圖：基于的可伸縮服務器

(注：本圖來自文獻【】)有一組服務器，他們通過分布式文件系統()來共享所有的文檔。這組服務器擁有相同的域名（如），當用戶按照這個域名訪問時,服務器會把域名輪流解析到這組服務器的不同地址，從而將訪問負載分到各臺服務器上。詳解Linux服務器集群全文共34頁，當前為第12頁。這種方法帶來幾個問題。第一，域名服務器是一個分布式系統，是按照一定的層次結構組織的。當用戶就域名解析請求提交給本地的域名服務器，它會因不能直接解析而向上一級域名服務器提交，上一級域名服務器再依次向上提交，直到域名服器把這個域名解析到其中一臺服務器的地址。可見，從用戶到間存在多臺域名服器，而它們都會緩沖已解析的名字到地址的映射,這會導致該域名服器組下所有用戶都會訪問同一服務器，出現不同服務器間嚴重的負載不平衡。為了保證在域名服務器中域名到地址的映射不被長久緩沖，在域名到地址的映射上設置一個()值，過了這一段時間，域名服務器將這個映射從緩沖中淘汰。當用戶請求，它會再向上一級域名服器提交請求并進行重新影射。這就涉及到如何設置這個值，若這個值太大，在這個期間，很多請求會被映射到同一臺服務器上，同樣會導致嚴重的負載不平衡。若這個值太小，例如是０，會導致本地域名服務器頻繁地向提交請求，增加了域名解析的網絡流量，同樣會使服務器成為系統中一個新的瓶頸。詳解Linux服務器集群全文共34頁，當前為第12頁。第二，用戶機器會緩沖從名字到地址的映射，而不受值的影響，用戶的訪問請求會被送到同一臺服務器上。由于用戶訪問請求的突發性和訪問方式不同，例如有的人訪問一下就離開了，而有的人訪問可長達幾個小時，所以各臺服務器間的負載仍存在傾斜（）而不能控制。假設用戶在每個會話中平均請求數為，負載最大的服務器獲得的請求數額高于各服務器平均請求數的平均比率超過百分之三十。也就是說，當值為時，因為用戶訪問的突發性也會存在著較嚴重的負載不平衡。第三，系統的可靠性和可維護性差。若一臺服務器失效，會導致將域名解析到該服務器的用戶看到服務中斷，即使用戶按“”按鈕，也無濟于事。系統管理員也不能隨時地將一臺服務器切出服務進行系統維護，如進行操作系統和應用軟件升級，這需要修改服務器中的地址列表，把該服務器的地址從中劃掉，然后等上幾天或者更長的時間，等所有域名服器將該域名到這臺服務器的映射淘汰，和所有映射到這臺服務器的客戶機不再使用該站點為止。.基于客戶端的解決方法基于客戶端的解決方法需要每個客戶程序都有一定的服務器集群的知識，進而把以負載均衡的方式將請求發到不同的服務器。例如，瀏覽器訪問的主頁時，它會隨機地從一百多臺服務器中挑選第臺，最后將請求送往。然而，這不是很好的解決方法，只是利用它的避免了解析的麻煩，當使用等其他瀏覽器不可避免的要進行解析。[]是做的另一種基于客戶端的解決方法。服務提供一個在客戶方瀏覽器中運行，向各個服務器發請求來收集服務器的負載等信息，再根據這些信息將客戶的請求發到相應的服務器。高可用性也在中實現，當服務器沒有響應時，向另一個服務器轉發請求。這種方法的透明性不好，向各服務器查詢來收集信息會增加額外的網絡流量，不具有普遍的適用性。.基于應用層負載均衡調度的解決方法多臺服務器通過高速的互聯網絡連接成一個集群系統，在前端有一個基于應用層的負載調度器。當用戶訪問請求到達調度器時，請求會提交給作負載均衡調度的應用程序，分析請求，根據各個服務器的負載情況，選出一臺服務器，重寫請求并向選出的服務器訪問，取得結果后，再返回給用戶。應用層負載均衡調度的典型代表有負載調度器[]、[]、[]和[]等。負載調度器是公司的商業產品，它是在服務器程序改寫而成的，采用單進程事件驅動的服務器結構。就是一個基于服務器程序改寫而成的并行調度程序，當一個請求到達時，會選出一個服務器，重寫請求并向這個服務器發出改寫后的請求，等結果返回后，再將結果轉發給客戶。利用中的模塊和模塊實現一個可伸縮服務器，它與的不同之處在于它要先從的中查找后，若沒有這個副本，再選一臺服務器，向服務器發送請求，再將服務器返回的結果轉發給客戶。是利用中的錯誤代碼，將客戶請求到達一臺服務器后，這個服務器根據自己的負載情況，自己處理請求，或者通過錯誤代碼將客戶引到另一臺服務器，以實現一個可伸縮的服務器。詳解Linux服務器集群全文共34頁，當前為第13頁。基于應用層負載均衡調度的多服務器解決方法也存在一些問題。第一，系統處理開銷特別大，致使系統的伸縮性有限。當請求到達負載均衡調度器至處理結束時，調度器需要進行四次從核心到用戶空間或從用戶空間到核心空間的上下文切換和內存復制；需要進行二次連接，一次是從用戶到調度器，另一次是從調度器到真實服務器；需要對請求進行分析和重寫。這些處理都需要不小的ＣＰＵ、內存和網絡等資源開銷，且處理時間長。所構成系統的性能不能接近線性增加的，一般服務器組增至或臺時，調度器本身可能會成為新的瓶頸。所以，這種基于應用層負載均衡調度的方法的伸縮性極其有限。第二，基于應用層的負載均衡調度器對于不同的應用，需要寫不同的調度器。以上幾個系統都是基于協議，若對于、、等應用，都需要重寫調度器。詳解Linux服務器集群全文共34頁，當前為第13頁。.基于層負載均衡調度的解決方法用戶通過虛擬地址（）訪問服務時，訪問請求的報文會到達負載調度器，由它進行負載均衡調度，從一組真實服務器選出一個，將報文的目標地址改寫成選定服務器的地址，報文的目標端口改寫成選定服務器的相應端口，最后將報文發送給選定的服務器。真實服務器的回應報文經過負載調度器時，將報文的源地址和源端口改為和相應的端口，再把報文發給用戶。的[]、的、的和的等都是使用網絡地址轉換方法。是在版本上應用快速報文插入技術，使得進行負載均衡調度的用戶進程訪問網絡設備接近核心空間的速度，降低了上下文切換的處理開銷，但并不徹底，它只是研究的原型系統，沒有成為有用的系統存活下來。的、的和的是非常昂貴的商品化系統，它們支持部分協議，有些在處理上存在問題。的[]使用修改過的網絡地址轉換方法在系統實現可伸縮的服務器。修改請求報文的目標地址并把它轉發給選出的服務器，服務器能把響應報文的源地址置為地址而非自己的地址。這種方法的好處是響應報文可以直接返回給客戶，壞處是每臺服務器的操作系統內核都需要修改。的[]是的后繼者，它將報文轉發給服務器，而服務器在的設備配置路由器的地址。這種方法與集群中的類似，它具有很高的可伸縮性，但一套在和需要上百萬美金。總的來說，的技術還挺不錯的。在貝爾實驗室的[]中，每臺服務器都獨立的地址，但都用配置上同一地址，采用路由和廣播兩種方法分發請求，服務器收到請求后按地址處理請求，并以為源地址返回結果。這種方法也是為了避免回應報文的重寫，但是每臺服務器用配置上同一地址，會導致地址沖突，有些操作系統會出現網絡失效。通過廣播分發請求，同樣需要修改服務器操作系統的源碼來過濾報文，使得只有一臺服務器處理廣播來的請求。微軟的負載均衡服務（，）[]是年底收購公司獲得的，它與中的基于本地過濾方法一樣。作為過濾器運行在網卡驅動程序和協議棧之間，獲得目標地址為的報文，它的過濾算法檢查報文的源地址和端口號，保證只有一臺服務器將報文交給上一層處理。但是，當有新結點加入和有結點失效時，所有服務器需要協商一個新的過濾算法，這會導致所有有的連接中斷。同時，需要所有的服務器有相同的配置，如網卡速度和處理能力。.通過實現虛擬服務器（）由于中地址空間的日益緊張和安全方面的原因，很多網絡使用保留地址（、和）[,,]。這些地址不在上使用，而是專門為內部網絡預留的。當內部網絡中的主機要訪問或被訪問時，就需要采用網絡地址轉換（,以下簡稱），將內部地址轉化為上可用的外部地址。的工作原理是報文頭（目標地址、源地址和端口等）被正確改寫后，客戶相信它們連接一個地址，而不同地址的服務器組也認為它們是與客戶直接相連的。由此，可以用方法將不同地址的并行網絡服務變成在一個地址上的一個虛擬服務。詳解Linux服務器集群全文共34頁，當前為第14頁。的體系結構如圖所示。在一組服務器前有一個調度器，它們是通過相連接的。這些服務器提供相同的網絡服務、相同的內容，即不管請求被發送到哪一臺服務器，執行結果是一樣的。服務的內容可以復制到每臺服務器的本地硬盤上，可以通過網絡文件系統（如）共享，也可以通過一個分布式文件系統來提供。詳解Linux服務器集群全文共34頁，當前為第14頁。

圖：的體系結構客戶通過（虛擬服務的地址）訪問網絡服務時，請求報文到達調度器，調度器根據連接調度算法從一組真實服務器中選出一臺服務器，將報文的目標地址改寫成選定服務器的地址，報文的目標端口改寫成選定服務器的相應端口，最后將修改后的報文發送給選出的服務器。同時，調度器在連接表中記錄這個連接，當這個連接的下一個報文到達時，從連接表中可以得到原選定服務器的地址和端口，進行同樣的改寫操作，并將報文傳給原選定的服務器。當來自真實服務器的響應報文經過調度器時，調度器將報文的源地址和源端口改為和相應的端口，再把報文發給用戶。我們在連接上引入一個狀態機，不同的報文會使得連接處于不同的狀態，不同的狀態有不同的超時值。在連接中，根據標準的有限狀態機進行狀態遷移，這里我們不一一敘述，請參見.的《》；在中，我們只設置一個狀態。不同狀態的超時值是可以設置的，在缺省情況下，狀態的超時為分鐘，狀態的超時為分鐘，狀態的超時為分鐘；狀態的超時為分鐘。當連接終止或超時，調度器將這個連接從連接表中刪除。詳解Linux服務器集群全文共34頁，當前為第15頁。這樣，客戶所看到的只是在上提供的服務，而服務器集群的結構對用戶是透明的。對改寫后的報文，應用增量調整的算法調整的值，避免了掃描整個報文來計算的開銷。詳解Linux服務器集群全文共34頁，當前為第15頁。在一些網絡服務中，它們將地址或者端口號在報文的數據中傳送，若我們只對報文頭的地址和端口號作轉換，這樣就會出現不一致性，服務會中斷。所以，針對這些服務，需要編寫相應的應用模塊來轉換報文數據中的地址或者端口號。我們所知道有這個問題的網絡服務有、、、、、、、、、、、、、、、、、和。下面，舉個例子來進一步說明，如圖所示：

圖：的例子的配置如下表所示，所有到地址為和端口為的流量都被負載均衡地調度的真實服務器和上。目標地址為的報文被轉移到上。而到其他端口的報文將被拒絕。從以下的例子中，我們可以更詳細地了解報文改寫的流程。訪問服務的報文可能有以下的源地址和目標地址：調度器從調度列表中選出一臺服務器，例如是。該報文會被改寫為如下地址，并將它發送給選出的服務器。從服務器返回到調度器的響應報文如下：響應報文的源地址會被改寫為虛擬服務的地址，再將報文發送給客戶：詳解Linux服務器集群全文共34頁，當前為第16頁。這樣，客戶認為是從服務得到正確的響應，而不會知道該請求是服務器還是服務器處理的。詳解Linux服務器集群全文共34頁，當前為第16頁。.通過隧道實現虛擬服務器（）在的集群系統中，請求和響應的數據報文都需要通過負載調度器，當真實服務器的數目在臺和臺之間時，負載調度器將成為整個集群系統的新瓶頸。大多數服務都有這樣的特點：請求報文較短而響應報文往往包含大量的數據。如果能將請求和響應分開處理，即在負載調度器中只負責調度請求而響應直接返回給客戶，將極大地提高整個集群系統的吞吐量。隧道（）是將一個報文封裝在另一個報文的技術，這可以使得目標為一個地址的數據報文能被封裝和轉發到另一個地址。隧道技術亦稱為封裝技術（）。隧道主要用于移動主機和虛擬私有網絡（），在其中隧道都是靜態建立的，隧道一端有一個地址，另一端也有唯一的地址。詳解Linux服務器集群全文共34頁，當前為第17頁。我們利用隧道技術將請求報文封裝轉發給后端服務器，響應報文能從后端服務器直接返回給客戶。但在這里，后端服務器有一組而非一個，所以我們不可能靜態地建立一一對應的隧道，而是動態地選擇一臺服務器，將請求報文封裝和轉發給選出的服務器。這樣，我們可以利用隧道的原理將一組服務器上的網絡服務組成在一個地址上的虛擬網絡服務。的體系結構如圖所示，各個服務器將地址配置在自己的隧道設備上。詳解Linux服務器集群全文共34頁，當前為第17頁。

圖：的體系結構詳解Linux服務器集群全文共34頁，當前為第18頁。的工作流程如圖所示：它的連接調度和管理與中的一樣，只是它的報文轉發方法不同。調度器根據各個服務器的負載情況，動態地選擇一臺服務器，將請求報文封裝在另一個報文中，再將封裝后的報文轉發給選出的服務器；服務器收到報文后，先將報文解封獲得原來目標地址為的報文，服務器發現地址被配置在本地的隧道設備上，所以就處理這個請求，然后根據路由表將響應報文直接返回給客戶。詳解Linux服務器集群全文共34頁，當前為第18頁。

圖：的工作流程在這里需要指出，根據缺省的協議棧處理，請求報文的目標地址為，響應報文的源地址肯定也為，所以響應報文不需要作任何修改，可以直接返回給客戶，客戶認為得到正常的服務，而不會知道究竟是哪一臺服務器處理的。

圖：半連接的有限狀態機.通過直接路由實現虛擬服務器（）詳解Linux服務器集群全文共34頁，當前為第19頁。跟方法相同，利用大多數服務的非對稱特點，負載調度器中只負責調度請求，而服務器直接將響應返回給客戶，可以極大地提高整個集群系統的吞吐量。該方法與的產品中使用的方法類似（其中服務器上的地址配置方法是相似的），但的是非常昂貴的商品化產品，我們也不知道它內部所使用的機制，其中有些是的專利。詳解Linux服務器集群全文共34頁，當前為第19頁。的體系結構如圖所示：調度器和服務器組都必須在物理上有一個網卡通過不分斷的局域網相連，如通過高速的交換機或者相連。地址為調度器和服務器組共享，調度器配置的地址是對外可見的，用于接收虛擬服務的請求報文；所有的服務器把地址配置在各自的網絡設備上，它對外面是不可見的，只是用于處理目標地址為的網絡請求。

圖：的體系結構詳解Linux服務器集群全文共34頁，當前為第20頁。的工作流程如圖所示：它的連接調度和管理與和中的一樣，它的報文轉發方法又有不同，將報文直接路由給目標服務器。在中，調度器根據各個服務器的負載情況，動態地選擇一臺服務器，不修改也不封裝報文，而是將數據幀的地址改為選出服務器的地址，再將修改后的數據幀在與服務器組的局域網上發送。因為數據幀的地址是選出的服務器，所以服務器肯定可以收到這個數據幀，從中可以獲得該報文。當服務器發現報文的目標地址是在本地的網絡設備上，服務器處理這個報文，然后根據路由表將響應報文直接返回給客戶。詳解Linux服務器集群全文共34頁，當前為第20頁。

圖：的工作流程在中，根據缺省的協議棧處理，請求報文的目標地址為，響應報文的源地址肯定也為，所以響應報文不需要作任何修改，可以直接返回給客戶，客戶認為得到正常的服務，而不會知道是哪一臺服務器處理的。負載調度器跟一樣只處于從客戶到服務器的半連接中，按照半連接的有限狀態機進行狀態遷移。.三種方法的優缺點比較三種負載均衡技術的優缺點歸納在下表中：()()()注：以上三種方法所能支持最大服務器數目的估計是假設調度器使用網卡，調度器的硬件配置與后端服務器的硬件配置相同，而且是對一般服務。使用更高的硬件配置（如千兆網卡和更快的處理器）作為調度器，調度器所能調度的服務器數量會相應增加。當應用不同時，服務器的數目也會相應地改變。所以，以上數據估計主要是為三種方法的伸縮性進行量化比較。詳解Linux服務器集群全文共34頁，當前為第21頁。.詳解Linux服務器集群全文共34頁，當前為第21頁。的優點是服務器可以運行任何支持的操作系統，它只需要一個地址配置在調度器上，服務器組可以用私有的地址。缺點是它的伸縮能力有限，當服務器結點數目升到時，調度器本身有可能成為系統的新瓶頸，因為在中請求和響應報文都需要通過負載調度器。我們在處理器的主機上測得重寫報文的平均延時為，性能更高的處理器上延時會短一些。假設報文的平均長度為，則調度器的最大吞吐量為.我們再假設每臺服務器的吞吐量為，這樣一個調度器可以帶動臺服務器。（注：這是很早以前測得的數據）基于的的集群系統可以適合許多服務器的性能要求。如果負載調度器成為系統新的瓶頸，可以有三種方法解決這個問題：混合方法、和。在混合集群系統中，有若干個負載調度器，每個負載調度器帶自己的服務器集群，同時這些負載調度器又通過組成簡單的域名。但和是提高系統吞吐量的更好方法。對于那些將地址或者端口號在報文數據中傳送的網絡服務，需要編寫相應的應用模塊來轉換報文數據中的地址或者端口號。這會帶來實現的工作量，同時應用模塊檢查報文的開銷會降低系統的吞吐率。.在的集群系統中，負載調度器只將請求調度到不同的后端服務器，后端服務器將應答的數據直接返回給用戶。這樣，負載調度器就可以處理大量的請求，它甚至可以調度百臺以上的服務器（同等規模的服務器），而它不會成為系統的瓶頸。即使負載調度器只有的全雙工網卡，整個系統的最大吞吐量可超過。所以，可以極大地增加負載調度器調度的服務器數量。調度器可以調度上百臺服務器，而它本身不會成為系統的瓶頸，可以用來構建高性能的超級服務器。技術對服務器有要求，即所有的服務器必須支持“”或者“”協議。目前，的后端服務器主要運行操作系統，我們沒對其他操作系統進行測試。因為“”正成為各個操作系統的標準協議，所以應該會適用運行其他操作系統的后端服務器。.跟方法一樣，調度器只處理客戶到服務器端的連接，響應數據可以直接從獨立的網絡路由返回給客戶。這可以極大地提高集群系統的伸縮性。跟相比，這種方法沒有隧道的開銷，但是要求負載調度器與實際服務器都有一塊網卡連在同一物理網段上，服務器網絡設備（或者設備別名）不作響應，或者能將報文重定向（）到本地的端口上。.小結本文主要講述了集群中的三種負載均衡技術。在分析網絡地址轉換方法（）的缺點和網絡服務的非對稱性的基礎上，我們給出了通過隧道實現虛擬服務器的方法，和通過直接路由實現虛擬服務器的方法，極大地提高了系統的伸縮性。詳解Linux服務器集群全文共34頁，當前為第22頁。

詳解Linux服務器集群全文共34頁，當前為第22頁。服務器集群系統(四)集群的負載調度""\""章文嵩

("")

年月本文主要講述了集群的負載均衡軟件在內核中實現的各種連接調度算法。針對請求的服務時間變化很大，給出一個動態反饋負載均衡算法，它結合內核中的加權連接調度算法，根據動態反饋回來的負載信息來調整服務器的權值，來進一步避免服務器間的負載不平衡。.前言

在上一篇文章中，我們主要講述了集群中實現的三種負載均衡技術，它們主要解決系統的可伸縮性和透明性問題，如何通過負載調度器將請求高效地分發到不同的服務器執行，使得由多臺獨立計算機組成的集群系統成為一臺虛擬服務器；客戶端應用程序與集群系統交互時，就像與一臺高性能的服務器交互一樣。本文將主要講述在負載調度器上的負載調度策略和算法，如何將請求流調度到各臺服務器，使得各臺服務器盡可能地保持負載均衡。文章主要由兩個部分組成。第一部分描述負載均衡軟件在內核中所實現的各種連接調度算法；第二部分給出一個動態反饋負載均衡算法（），它結合內核中的加權連接調度算法，根據動態反饋回來的負載信息來調整服務器的權值，來進一步避免服務器間的負載不平衡。在下面描述中，我們稱客戶的和服務器的之間的數據通訊為連接，無論它們是使用還是協議。對于數據報文的調度，調度器也會為之建立調度記錄并設置超時值（如分鐘）；在設定的時間內，來自同一地址（地址和端口）的數據包會被調度到同一臺服務器。.內核中的連接調度算法在內核中的負載均衡調度是以連接為粒度的。在協議（非持久）中，每個對象從服務器上獲取都需要建立一個連接，同一用戶的不同請求會被調度到不同的服務器上，所以這種細粒度的調度在一定程度上可以避免單個用戶訪問的突發性引起服務器間的負載不平衡。在內核中的連接調度算法上，已實現了以下八種調度算法：輪叫調度（）加權輪叫調度（）最小連接調度（）加權最小連接調度（）基于局部性的最少鏈接（）帶復制的基于局部性最少鏈接（）目標地址散列調度（）詳解Linux服務器集群全文共34頁，當前為第23頁。源地址散列調度（）詳解Linux服務器集群全文共34頁，當前為第23頁。下面，我們先介紹這八種連接調度算法的工作原理和算法流程，會在以后的文章中描述怎么用它們。.輪叫調度輪叫調度（）算法就是以輪叫的方式依次將請求調度不同的服務器，即每次調度執行()，并選出第臺服務器。算法的優點是其簡潔性，它無需記錄當前所有連接的狀態，所以它是一種無狀態調度。在系統實現時，我們引入了一個額外條件，當服務器的權值為零時，表示該服務器不可用而不被調度。這樣做的目的是將服務器切出服務（如屏蔽服務器故障和系統維護），同時與其他加權算法保持一致。所以，算法要作相應的改動，它的算法流程如下：輪叫調度算法流程假設有一組服務器{,,…,}，一個指示變量表示上一次選擇的服務器，()表示服務器的權值。變量被初始化為，其中>。;{ (); (()>){ ; ; }}();;輪叫調度算法假設所有服務器處理性能均相同，不管服務器的當前連接數和響應速度。該算法相對簡單，不適用于服務器組中處理性能不一的情況，而且當請求服務時間變化比較大時，輪叫調度算法容易導致服務器間的負載不平衡。雖然方法也是以輪叫調度的方式將一個域名解析到多個地址，但輪叫方法的調度粒度是基于每個域名服務器的，域名服務器對域名解析的緩存會妨礙輪叫解析域名生效，這會導致服務器間負載的嚴重不平衡。這里，輪叫調度算法的粒度是基于每個連接的，同一用戶的不同連接都會被調度到不同的服務器上，所以這種細粒度的輪叫調度要比的輪叫調度優越很多。.加權輪叫調度加權輪叫調度（）算法可以解決服務器間性能不一的情況，它用相應的權值表示服務器的處理性能，服務器的缺省權值為。假設服務器的權值為，的權值為，則表示服務器的處理性能是的兩倍。加權輪叫調度算法是按權值的高低和輪叫方式分配請求到各服務器。權值高的服務器先收到的連接，權值高的服務器比權值低的服務器處理更多的連接，相同權值的服務器處理相同數目的連接數。加權輪叫調度算法流程如下：詳解Linux服務器集群全文共34頁，當前為第24頁。加權輪叫調度算法流程詳解Linux服務器集群全文共34頁，當前為第24頁。假設有一組服務器{,,…,}，()表示服務器的權值，一個指示變量表示上一次選擇的服務器，指示變量表示當前調度的權值，()表示集合中所有服務器的最大權值，()表示集合中所有服務器權值的最大公約數。變量初始化為，初始化為零。(){();(){();(<){();();}}(()>);}例如，有三個服務器、和分別有權值、和，則在一個調度周期內((()))調度序列為。加權輪叫調度算法還是比較簡單和高效。當請求的服務時間變化很大，單獨的加權輪叫調度算法依然會導致服務器間的負載不平衡。從上面的算法流程中，我們可以看出當服務器的權值為零時，該服務器不被被調度；當所有服務器的權值為零，即對于任意有()，則沒有任何服務器可用，算法返回，所有的新連接都會被丟掉。加權輪叫調度也無需記錄當前所有連接的狀態，所以它也是一種無狀態調度。.最小連接調度最小連接調度（）算法是把新的連接請求分配到當前連接數最小的服務器。最小連接調度是一種動態調度算法，它通過服務器當前所活躍的連接數來估計服務器的負載情況。調度器需要記錄各個服務器已建立連接的數目，當一個請求被調度到某臺服務器，其連接數加；當連接中止或超時，其連接數減一。在系統實現時，我們也引入當服務器的權值為零時，表示該服務器不可用而不被調度，它的算法流程如下：詳解Linux服務器集群全文共34頁，當前為第25頁。最小連接調度算法流程詳解Linux服務器集群全文共34頁，當前為第25頁。假設有一組服務器{,,...,}，()表示服務器的權值，()表示服務器的當前連接數。(;<;){ (()>){ (;<;){ (()<) ; (()<()) ; } ; }};當各個服務器有相同的處理性能時，最小連接調度算法能把負載變化大的請求分布平滑到各個服務器上，所有處理時間比較長的請求不可能被發送到同一臺服務器上。但是，當各個服務器的處理能力不同時，該算法并不理想，因為連接處理請求后會進入狀態，的一般為分鐘，此時連接還占用服務器的資源，所以會出現這樣情形，性能高的服務器已處理所收到的連接，連接處于狀態，而性能低的服務器已經忙于處理所收到的連接，還不斷地收到新的連接請求。.加權最小連接調度加權最小連接調度（）算法是最小連接調度的超集，各個服務器用相應的權值表示其處理性能。服務器的缺省權值為，系統管理員可以動態地設置服務器的權值。加權最小連接調度在調度新連接時盡可能使服務器的已建立連接數和其權值成比例。加權最小連接調度的算法流程如下：詳解Linux服務器集群全文共34頁，當前為第26頁。加權最小連接調度的算法流程詳解Linux服務器集群全文共34頁，當前為第26頁。假設有一組服務器{,,...,}，()表示服務器的權值，()表示服務器的當前連接數。所有服務器當前連接數的總和為Σ()(,,..,)。當前的新連接請求會被發送服務器，當且僅當服務器滿足以下條件(())(){(())()}(,,.,)其中()不為零因為在這一輪查找中是個常數，所以判斷條件可以簡化為()(){()()}(,,.,)其中()不為零因為除法所需的周期比乘法多，且在內核中不允許浮點除法，服務器的權值都大于零，所以判斷條件()()>()()可以進一步優化為()*()>()*()。同時保證服務器的權值為零時，服務器不被調度。所以，算法只要執行以下流程。(;<;){ (()>){ (;<;){ (()*()>()*()) ; } ; }};.基于局部性的最少鏈接調度基于局部性的最少鏈接調度（，以下簡稱為）算法是針對請求報文的目標地址的負載均衡調度，目前主要用于集群系統，因為在集群中客戶請求報文的目標地址是變化的。這里假設任何后端服務器都可以處理任一請求，算法的設計目標是在服務器的負載基本平衡情況下，將相同目標地址的請求調度到同一臺服務器，來提高各臺服務器的訪問局部性和主存命中率，從而整個集群系統的處理能力。調度算法先根據請求的目標地址找出該目標地址最近使用的服務器，若該服務器是可用的且沒有超載，將請求發送到該服務器；若服務器不存在，或者該服務器超載且有服務器處于其一半的工作負載，則用“最少鏈接”的原則選出一個可用的服務器，將請求發送到該服務器。該算法的詳細流程如下：詳解Linux服務器集群全文共34頁，當前為第27頁。調度算法流程詳解Linux服務器集群全文共34頁，當前為第27頁。假設有一組服務器{,,...,}，()表示服務器的權值，()表示服務器的當前連接數。[]是一個關聯變量，表示目標地址所對應的服務器結點，一般來說它是通過表實現的。()表示在集合中的加權最小連接服務器，即前面的加權最小連接調度。為當前系統時間。([]){ (); (); [];}{ []; (() (()>() ()<()))){ (); (); []; }}[];;此外，對關聯變量[]要進行周期性的垃圾回收（），將過期的目標地址到服務器關聯項進行回收。過期的關聯項是指哪些當前時間（實現時采用系統時鐘節拍數）減去最近使用時間超過設定過期時間的關聯項，系統缺省的設定過期時間為小時。.帶復制的基于局部性最少鏈接調度帶復制的基于局部性最少鏈接調度（，以下簡稱為）算法也是針對目標地址的負載均衡，目前主要用于集群系統。它與算法的不同之處是它要維護從一個目標地址到一組服務器的映射，而算法維護從一個目標地址到一臺服務器的映射。對于一個“熱門”站點的服務請求，一臺服務器可能會忙不過來處理這些請求。這時，調度算法會從所有的服務器中按“最小連接”原則選出一臺服務器，映射該“熱門”站點到這臺服務器，很快這臺服務器也會超載，就會重復上述過程選出新的服務器。這樣，可能會導致該“熱門”站點的映像會出現在所有的服務器上，降低了服務器的使用效率。調度算法將“熱門”站點映射到一組服務器（服務器集合），當該“熱門”站點的請求負載增加時，會增加集合里的服務器，來處理不斷增長的負載；當該“熱門”站點的請求負載降低時，會減少集合里的服務器數目。這樣，該“熱門”站點的映像不太可能出現在所有的服務器上，從而提供集群系統的使用效率。算法先根據請求的目標地址找出該目標地址對應的服務器組；按“最小連接”原則從該服務器組中選出一臺服務器，若服務器沒有超載，將請求發送到該服務器；若服務器超載；則按“最小連接”原則從整個集群中選出一臺服務器，將該服務器加入到服務器組中，將請求發送到該服務器。同時，當該服務器組有一段時間沒有被修改，將最忙的服務器從服務器組中刪除，以降低復制的程度。調度算法的流程如下：詳解Linux服務器集群全文共34頁，當前為第28頁。調度算法流程詳解Linux服務器集群全文共34頁，當前為第28頁。假設有一組服務器{,,...,}，()表示服務器的權值，()表示服務器的當前連接數。[]是一個關聯變量，表示目標地址所對應的服務器集合，一般來說它是通過表實現的。()表示在集合中的加權最小連接服務器，即前面的加權最小連接調度；()表示在集合中的加權最大連接服務器。為當前系統時間，表示集合的最近修改時間，為對集合進行調整的設定時間。([]){ (); (); [];}{ ([]); (() () (()>() ()<()))){ (); (); []; } ([]> []>){ ([]); []; }}[];([]) [];;此外，對關聯變量[]也要進行周期性的垃圾回收（），將過期的目標地址到服務器關聯項進行回收。過期的關聯項是指哪些當前時間（實現時采用系統時鐘節拍數）減去最近使用時間（）超過設定過期時間的關聯項，系統缺省的設定過期時間為小時。.目標地址散列調度目標地址散列調度（）算法也是針對目標地址的負載均衡，但它是一種靜態映射算法，通過一個散列（）函數將一個目標地址映射到一臺服務器。目標地址散列調度算法先根據請求的目標地址，作為散列鍵（）從靜態分配的散列表找出對應的服務器，若該服務器是可用的且未超載，將請求發送到該服務器，否則返回空。該算法的流程如下：詳解Linux服務器集群全文共34頁，當前為第29頁。目標地址散列調度算法流程詳解Linux服務器集群全文共34頁，當前為第29頁。假設有一組服務器{,,...,}，()表示服務器的權值，()表示服務器的當前連接數。[]是一個有個桶（）的表，一般來說服務器的數目會運小于，當然表的大小也是可以調整的。算法的初始化是將所有服務器順序、循環地放置到表中。若服務器的連接數目大于倍的權值，則表示服務器已超載。[()];(() (())(()>*())) ;;在實現時，我們采用素數乘法函數，通過乘以素數使得散列鍵值盡可能地達到較均勻的分布。所采用的素數乘法函數如下：素數乘法函數(){(*);}其中，是到^()間接近于黃金分割的素數，(()).源地址散列調度源地址散列調度（）算法正好與目標地址散列調度算法相反，它根據請求的源地址，作為散列鍵（）從靜態分配的散列表找出對應的服務器，若該服務器是可用的且未超載，將請求發送到該服務器，否則返回空。它采用的散列函數與目標地址散列調度算法的相同。它的算法流程與目標地址散列調度算法的基本相似，除了將請求的目標地址換成請求的源地址，所以這里不一一敘述。在實際應用中，源地址散列調度和目標地址散列調度可以結合使用在防火墻集群中，它們可以保證整個系統的唯一出入口。.動態反饋負載均衡算法詳解Linux服務器集群全文共34頁，當前為第30頁。動態反饋負載均衡算法考慮服務器的實時負載和響應情況，不斷調整服務器間處理請求的比例，來避免有些服務器超載時依然收到大量請求，從而提高整個系統的吞吐率。圖顯示了該算法的工作環境，在負載調度器上運行進程，來監視和收集各個服務器的負載信息。可根據多個負載信息算出一個綜合負載值。將各個服務器的綜合負載值和當前權值算出一組新的權值，若新權值和當前權值的差值大于設定的閥值，將該服務器的權值設置到內核中的調度中，而在內核中連接調度一般采用加權輪叫調度算法或者加權最小連接調度算法。詳解Linux服務器集群全文共34頁，當前為第30頁。

圖：動態反饋負載均衡算法的工作環境.連接調度當客戶通過連接訪問網絡訪問時，服務所需的時間和所要消耗的計算資源是千差萬別的，它依賴于很多因素。例如，它依賴于請求的服務類型、當前網絡帶寬的情況、以及當前服務器資源利用的情況。一些負載比較重的請求需要進行計算密集的查詢、數據庫訪問、很長響應數據流；而負載比較輕的請求往往只需要讀一個頁面或者進行很簡單的計算。請求處理時間的千差萬別可能會導致服務器利用的傾斜（），即服務器間的負載不平衡。例如，有一個頁面有、、和文件，其中是大圖像文件，瀏覽器需要建立四個連接來取這些文件。當多個用戶通過瀏覽器同時訪問該頁面時，最極端的情況是所有文件的請求被發到同一臺服務器。所以說，有可能存在這樣情況，有些服務器已經超負荷運行，而其他服務器基本是閑置著。同時，有些服務器已經忙不過來，有很長的請求隊列，還不斷地收到新的請求。反過來說，這會導致客戶長時間的等待，覺得系統的服務質量差。.簡單連接調度簡單連接調度可能會使得服務器傾斜的發生。在上面的例子中，若采用輪叫調度算法，且集群中正好有四臺服務器，必有一臺服務器總是收到文件的請求。這種調度策略會導致整個系統資源的低利用率，因為有些資源被用盡導致客戶的長時間等待，而其他資源空閑著。詳解Linux服務器集群全文共34頁，當前為第31頁。.實際流量的特征詳解Linux服務器集群全文共34頁，當前為第31頁。文獻[]說明網絡流量是呈波浪型發生的，在一段較長時間的小流量后，會有一段大流量的訪問，然后是小流量，這樣跟波浪一樣周期性地發生。文獻[]揭示在和上網絡流量存在自相似的特征，在訪問流也存在自相似性。這就需要一個動態反饋機制，利用服務器組的狀態來應對訪問流的自相似性。.動態反饋負載均衡機制流量的特征通俗地說是有許多短事務和一些長事務組成，而長事務的工作量在整個工作量占有較高的比例。所以，我們要設計一種負載均衡算法，來避免長事務的請求總被分配到一些機器上，而是盡可能將帶有毛刺（）的分布分割成相對較均勻的分布。我們提出基于動態反饋負載均衡機制，來控制新連接的分配，從而控制各個服務器的負載。例如，在調度器的內核中使用加權輪叫調度（）算法來調度新的請求連接；在負載調度器的用戶空間中運行。定時地監視和收集各個服務器的負載信息，根據多個負載信息算出一個綜合負載值。將各個服務器的綜合負載值和當前權值算出一組新的權值。當綜合負載值表示服務器比較忙時，新算出的權值會比其當前權值要小，這樣新分配到該服務器的請求數就會少一些。當綜合負載值表示服務器處于低利用率時，新算出的權值會比其當前權值要大，來增加新分配到該服務器的請求數。若新權值和當前權值的差值大于設定的閥值