本文在分析服務器集群實現虛擬網絡服務的相關技術上，詳細描述了LVS集群中實現的三種IP負載均衡技術（VS/NAT、VS/TUN和VS/DR）的工作原理，以及它們的優缺點。
1.前言
我們先分析實現虛擬網絡服務的主要技術，指出 IP負載均衡技術是在負載調度器的實現技術中效率最高的。在已有的IP負載均衡技術中，主要有通過網絡地址轉換（Network Address Translation）將一組服務器構成一個高性能的、高可用的虛擬服務器，我們稱之為VS/NAT技術（Virtual Server via Network Address Translation）。在分析VS/NAT的缺點和網絡服務的非對稱性的基礎上，我們提出了通過IP隧道實現虛擬服務器的方法VS/TUN （Virtual Server via IP Tunneling），和通過直接路由實現虛擬服務器的方法VS/DR（Virtual Server via Direct Routing），它們可以極大地提高系統的伸縮性。VS/NAT、VS/TUN和VS/DR技術是LVS集群中實現的三種IP負載均衡技術，我們將在文章中詳細描述它們的工作原理和各自的優缺點。
在以下描述中，我們稱客戶的socket和服務器的socket之間的數據通訊為連接，無論它們是使用TCP還是UDP協議。下面簡述當前用服務器集群實現高可伸縮、高可用網絡服務的幾種負載調度方法，并列舉幾個在這方面有代表性的研究項目。
2.實現虛擬服務的相關方法
在網絡服務中，一端是客戶程序，另一端是服務程序，在中間可能有代理程序。由此看來，可以在不同的層次上實現多臺服務器的負載均衡。用集群解決網絡服務性能問題的現有方法主要分為以下四類。
2.1. 基于RR-DNS的解決方法
NCSA的可伸縮的WEB服務器系統就是最早基于RR-DNS（Round-Robin Domain Name System）的原型系統[1,2]。它的結構和工作流程如下圖所示：
基于RR-DNS的可伸縮WEB服務器
有一組WEB服務器，他們通過分布式文件系統AFS(Andrew File System)來共享所有的html文檔。這組服務器擁有相同的域名（如www.ncsa.uiuc.edu），當用戶按照這個域名訪問時, RR-DNS服務器會把域名輪流解析到這組服務器的不同IP地址，從而將訪問負載分到各臺服務器上。
這種方法帶來幾個問題。第一，域名服務器是一個分布式系統，是按照一定的層次結構組織的。當用戶就域名解析請求提交給本地的域名服務器，它會因不能直接解析而向上一級域名服務器提交，上一級域名服務器再依次向上提交，直到RR-DNS域名服器把這個域名解析到其中一臺服務器的IP地址。可見，從用戶到RR-DNS間存在多臺域名服器，而它們都會緩沖已解析的名字到IP地址的映射,這會導致該域名服器組下所有用戶都會訪問同一WEB服務器，出現不同WEB服務器間嚴重的負載不平衡。為了保證在域名服務器中域名到IP地址的映射不被長久緩沖，RR-DNS在域名到IP地址的映射上設置一個TTL(Time To Live)值，過了這一段時間，域名服務器將這個映射從緩沖中淘汰。當用戶請求，它會再向上一級域名服器提交請求并進行重新影射。這就涉及到如何設置這個 TTL值，若這個值太大，在這個TTL期間，很多請求會被映射到同一臺WEB服務器上，同樣會導致嚴重的負載不平衡。若這個值太小，例如是０，會導致本地域名服務器頻繁地向RR-DNS提交請求，增加了域名解析的網絡流量，同樣會使RR-DNS服務器成為系統中一個新的瓶頸。
第二，用戶機器會緩沖從名字到IP地址的映射，而不受TTL值的影響，用戶的訪問請求會被送到同一臺WEB服務器上。由于用戶訪問請求的突發性和訪問方式不同，例如有的人訪問一下就離開了，而有的人訪問可長達幾個小時，所以各臺服務器間的負載仍存在傾斜（Skew）而不能控制。假設用戶在每個會話中平均請求數為20，負載最大的服務器獲得的請求數額高于各服務器平均請求數的平均比率超過百分之三十。也就是說，當TTL值為0時，因為用戶訪問的突發性也會存在著較嚴重的負載不平衡。
第三，系統的可靠性和可維護性差。若一臺服務器失效，會導致將域名解析到該服務器的用戶看到服務中斷，即使用戶按 “Reload”按鈕，也無濟于事。系統管理員也不能隨時地將一臺服務器切出服務進行系統維護，如進行操作系統和應用軟件升級，這需要修改RR-DNS服務器中的IP地址列表，把該服務器的IP地址從中劃掉，然后等上幾天或者更長的時間，等所有域名服器將該域名到這臺服務器的映射淘汰，和所有映射到這臺服務器的客戶機不再使用該站點為止。
2.2. 基于客戶端的解決方法
基于客戶端的解決方法需要每個客戶程序都有一定的服務器集群的知識，進而把以負載均衡的方式將請求發到不同的服務器。例如，Netscape Navigator瀏覽器訪問Netscape的主頁時，它會隨機地從一百多臺服務器中挑選第N臺，最后將請求送往wwwN.netscape.com。然而，這不是很好的解決方法，Netscape只是利用它的Navigator避免了RR-DNS解析的麻煩，當使用IE等其他瀏覽器不可避免的要進行 RR-DNS解析。
Smart Client[3]是Berkeley做的另一種基于客戶端的解決方法。服務提供一個JAVA Applet在客戶方瀏覽器中運行，Applet向各個服務器發請求來收集服務器的負載等信息，再根據這些信息將客戶的請求發到相應的服務器。高可用性也在Applet中實現，當服務器沒有響應時，Applet向另一個服務器轉發請求。這種方法的透明性不好，Applet向各服務器查詢來收集信息會增加額外的網絡流量，不具有普遍的適用性。
2.3. 基于應用層負載均衡調度的解決方法
多臺服務器通過高速的互聯網絡連接成一個集群系統，在前端有一個基于應用層的負載調度器。當用戶訪問請求到達調度器時，請求會提交給作負載均衡調度的應用程序，分析請求，根據各個服務器的負載情況，選出一臺服務器，重寫請求并向選出的服務器訪問，取得結果后，再返回給用戶。
應用層負載均衡調度的典型代表有Zeus負載調度器[4]、pWeb[5]、Reverse-Proxy[6]和SWEB[7]等。Zeus負載調度器是Zeus公司的商業產品，它是在Zeus Web服務器程序改寫而成的，采用單進程事件驅動的服務器結構。pWeb就是一個基于Apache 1.1服務器程序改寫而成的并行WEB調度程序，當一個HTTP請求到達時，pWeb會選出一個服務器，重寫請求并向這個服務器發出改寫后的請求，等結果返回后，再將結果轉發給客戶。Reverse-Proxy利用Apache 1.3.1中的Proxy模塊和Rewrite模塊實現一個可伸縮WEB服務器，它與pWeb的不同之處在于它要先從Proxy的cache中查找后，若沒有這個副本，再選一臺服務器，向服務器發送請求，再將服務器返回的結果轉發給客戶。SWEB是利用HTTP中的redirect錯誤代碼，將客戶請求到達一臺WEB服務器后，這個WEB服務器根據自己的負載情況，自己處理請求，或者通過redirect錯誤代碼將客戶引到另一臺WEB服務器，以實現一個可伸縮的WEB服務器。
基于應用層負載均衡調度的多服務器解決方法也存在一些問題。第一，系統處理開銷特別大，致使系統的伸縮性有限。當請求到達負載均衡調度器至處理結束時，調度器需要進行四次從核心到用戶空間或從用戶空間到核心空間的上下文切換和內存復制；需要進行二次TCP連接，一次是從用戶到調度器，另一次是從調度器到真實服務器；需要對請求進行分析和重寫。這些處理都需要不小的ＣＰＵ、內存和網絡等資源開銷，且處理時間長。所構成系統的性能不能接近線性增加的，一般服務器組增至3或4臺時，調度器本身可能會成為新的瓶頸。所以，這種基于應用層負載均衡調度的方法的伸縮性極其有限。第二，基于應用層的負載均衡調度器對于不同的應用，需要寫不同的調度器。以上幾個系統都是基于HTTP協議，若對于FTP、Mail、POP3等應用，都需要重寫調度器。
2.4. 基于IP層負載均衡調度的解決方法
用戶通過虛擬IP地址（Virtual IP Address）訪問服務時，訪問請求的報文會到達負載調度器，由它進行負載均衡調度，從一組真實服務器選出一個，將報文的目標地址Virtual IP Address改寫成選定服務器的地址，報文的目標端口改寫成選定服務器的相應端口，最后將報文發送給選定的服務器。真實服務器的回應報文經過負載調度器時，將報文的源地址和源端口改為Virtual IP Address和相應的端口，再把報文發給用戶。Berkeley的MagicRouter[8]、Cisco的LocalDirector、 Alteon的ACEDirector和F5的Big/IP等都是使用網絡地址轉換方法。MagicRouter是在linux 1.3版本上應用快速報文插入技術，使得進行負載均衡調度的用戶進程訪問網絡設備接近核心空間的速度，降低了上下文切換的處理開銷，但并不徹底，它只是研究的原型系統，沒有成為有用的系統存活下來。Cisco的LocalDirector、Alteon的ACEDirector和F5的Big/IP是非常昂貴的商品化系統，它們支持部分TCP/UDP協議，有些在ICMP處理上存在問題。
IBM的TCP Router[9]使用修改過的網絡地址轉換方法在SP/2系統實現可伸縮的WEB服務器。TCP Router修改請求報文的目標地址并把它轉發給選出的服務器，服務器能把響應報文的源地址置為TCP Router地址而非自己的地址。這種方法的好處是響應報文可以直接返回給客戶，壞處是每臺服務器的操作系統內核都需要修改。IBM的 NetDispatcher[10]是TCP Router的后繼者，它將報文轉發給服務器，而服務器在non-ARP的設備配置路由器的地址。這種方法與LVS集群中的VS/DR類似，它具有很高的可伸縮性，但一套在IBM SP/2和NetDispatcher需要上百萬美金。總的來說，IBM的技術還挺不錯的。
在貝爾實驗室的 ONE-IP[11]中，每臺服務器都獨立的IP地址，但都用IP Alias配置上同一VIP地址，采用路由和廣播兩種方法分發請求，服務器收到請求后按VIP地址處理請求，并以VIP為源地址返回結果。這種方法也是為了避免回應報文的重寫，但是每臺服務器用IP Alias配置上同一VIP地址，會導致地址沖突，有些操作系統會出現網絡失效。通過廣播分發請求，同樣需要修改服務器操作系統的源碼來過濾報文，使得只有一臺服務器處理廣播來的請求。
微軟的windows NT負載均衡服務（Windows NT Load Balancing Service，WLBS）[12]是1998年底收購Valence Research公司獲得的，它與ONE-IP中的基于本地過濾方法一樣。WLBS作為過濾器運行在網卡驅動程序和TCP/IP協議棧之間，獲得目標地址為VIP的報文，它的過濾算法檢查報文的源IP地址和端口號，保證只有一臺服務器將報文交給上一層處理。但是，當有新結點加入和有結點失效時，所有服務器需要協商一個新的過濾算法，這會導致所有有Session的連接中斷。同時，WLBS需要所有的服務器有相同的配置，如網卡速度和處理能力。
3. 通過NAT實現虛擬服務器（VS/NAT）
由于IPv4中IP地址空間的日益緊張和安全方面的原因，很多網絡使用保留IP地址（10.0.0.0/255.0.0.0、 172.16.0.0/255.128.0.0和192.168.0.0/255.255.0.0）[64, 65, 66]。這些地址不在Internet上使用，而是專門為內部網絡預留的。當內部網絡中的主機要訪問Internet或被Internet訪問時，就需要采用網絡地址轉換（Network Address Translation, 以下簡稱NAT），將內部地址轉化為Internets上可用的外部地址。NAT的工作原理是報文頭（目標地址、源地址和端口等）被正確改寫后，客戶相信它們連接一個IP地址，而不同IP地址的服務器組也認為它們是與客戶直接相連的。由此，可以用NAT方法將不同IP地址的并行網絡服務變成在一個IP地址上的一個虛擬服務。
VS/NAT的體系結構如圖2所示。在一組服務器前有一個調度器，它們是通過Switch/HUB相連接的。這些服務器提供相同的網絡服務、相同的內容，即不管請求被發送到哪一臺服務器，執行結果是一樣的。服務的內容可以復制到每臺服務器的本地硬盤上，可以通過網絡文件系統（如NFS）共享，也可以通過一個分布式文件系統來提供。
VS/NAT的體系結構
客戶通過Virtual IP Address（虛擬服務的IP地址）訪問網絡服務時，請求報文到達調度器，調度器根據連接調度算法從一組真實服務器中選出一臺服務器，將報文的目標地址 Virtual IP Address改寫成選定服務器的地址，報文的目標端口改寫成選定服務器的相應端口，最后將修改后的報文發送給選出的服務器。同時，調度器在連接Hash 表中記錄這個連接，當這個連接的下一個報文到達時，從連接Hash表中可以得到原選定服務器的地址和端口，進行同樣的改寫操作，并將報文傳給原選定的服務器。當來自真實服務器的響應報文經過調度器時，調度器將報文的源地址和源端口改為Virtual IP Address和相應的端口，再把報文發給用戶。我們在連接上引入一個狀態機，不同的報文會使得連接處于不同的狀態，不同的狀態有不同的超時值。在TCP 連接中，根據標準的TCP有限狀態機進行狀態遷移，這里我們不一一敘述，請參見W. Richard Stevens的《TCP/IP Illustrated Volume I》；在UDP中，我們只設置一個UDP狀態。不同狀態的超時值是可以設置的，在缺省情況下，SYN狀態的超時為1分鐘，ESTABLISHED狀態的超時為15分鐘，FIN狀態的超時為1分鐘；UDP狀態的超時為5分鐘。當連接終止或超時，調度器將這個連接從連接Hash表中刪除。
這樣，客戶所看到的只是在Virtual IP Address上提供的服務，而服務器集群的結構對用戶是透明的。對改寫后的報文，應用增量調整Checksum的算法調整TCP Checksum的值，避免了掃描整個報文來計算Checksum的開銷。
在一些網絡服務中，它們將IP地址或者端口號在報文的數據中傳送，若我們只對報文頭的IP地址和端口號作轉換，這樣就會出現不一致性，服務會中斷。所以，針對這些服務，需要編寫相應的應用模塊來轉換報文數據中的IP地址或者端口號。我們所知道有這個問題的網絡服務有FTP、IRC、H.323、 CUSeeMe、Real Audio、Real Video、Vxtreme / Vosiac、VDOLive、VIVOActive、True Speech、RSTP、PPTP、StreamWorks、NTT AudioLink、NTT SoftwareVision、Yamaha MIDPlug、iChat Pager、Quake和Diablo。
下面，舉個例子來進一步說明VS/NAT，如圖所示：
VS/NAT的例子
VS/NAT 的配置如下表所示，所有到IP地址為202.103.106.5和端口為80的流量都被負載均衡地調度的真實服務器172.16.0.2:80和 172.16.0.3:8000上。目標地址為202.103.106.5:21的報文被轉移到172.16.0.3:21上。而到其他端口的報文將被拒絕。
從以下的例子中，我們可以更詳細地了解報文改寫的流程。
訪問Web服務的報文可能有以下的源地址和目標地址：
SOURCE202.100.1.2:3456DEST202.103.106.5:80
調度器從調度列表中選出一臺服務器，例如是172.16.0.3:8000。該報文會被改寫為如下地址，并將它發送給選出的服務器。
SOURCE202.100.1.2:3456DEST172.16.0.3:8000
從服務器返回到調度器的響應報文如下：
SOURCE172.16.0.3:8000DEST202.100.1.2:3456
響應報文的源地址會被改寫為虛擬服務的地址，再將報文發送給客戶：
SOURCE202.103.106.5:80DEST202.100.1.2:3456
這樣，客戶認為是從202.103.106.5:80服務得到正確的響應，而不會知道該請求是服務器172.16.0.2還是服務器172.16.0.3處理的。
4. 通過IP隧道實現虛擬服務器（VS/TUN）
在VS/NAT 的集群系統中，請求和響應的數據報文都需要通過負載調度器，當真實服務器的數目在10臺和20臺之間時，負載調度器將成為整個集群系統的新瓶頸。大多數 Internet服務都有這樣的特點：請求報文較短而響應報文往往包含大量的數據。如果能將請求和響應分開處理，即在負載調度器中只負責調度請求而響應直接返回給客戶，將極大地提高整個集群系統的吞吐量。
IP隧道（IP tunneling）是將一個IP報文封裝在另一個IP報文的技術，這可以使得目標為一個IP地址的數據報文能被封裝和轉發到另一個IP地址。IP隧道技術亦稱為IP封裝技術（IP encapsulation）。IP隧道主要用于移動主機和虛擬私有網絡（Virtual Private Network），在其中隧道都是靜態建立的，隧道一端有一個IP地址，另一端也有唯一的IP地址。
我們利用IP隧道技術將請求報文封裝轉發給后端服務器，響應報文能從后端服務器直接返回給客戶。但在這里，后端服務器有一組而非一個，所以我們不可能靜態地建立一一對應的隧道，而是動態地選擇一臺服務器，將請求報文封裝和轉發給選出的服務器。這樣，我們可以利用IP隧道的原理將一組服務器上的網絡服務組成在一個IP地址上的虛擬網絡服務。 VS/TUN的體系結構如圖4所示，各個服務器將VIP地址配置在自己的IP隧道設備上。
VS/TUN的體系結構
VS/TUN 的工作流程如圖5所示：它的連接調度和管理與VS/NAT中的一樣，只是它的報文轉發方法不同。調度器根據各個服務器的負載情況，動態地選擇一臺服務器，將請求報文封裝在另一個IP報文中，再將封裝后的IP報文轉發給選出的服務器；服務器收到報文后，先將報文解封獲得原來目標地址為VIP的報文，服務器發現VIP地址被配置在本地的IP隧道設備上，所以就處理這個請求，然后根據路由表將響應報文直接返回給客戶。
VS/TUN的工作流程
在這里需要指出，根據缺省的TCP/IP協議棧處理，請求報文的目標地址為VIP，響應報文的源地址肯定也為VIP，所以響應報文不需要作任何修改，可以直接返回給客戶，客戶認為得到正常的服務，而不會知道究竟是哪一臺服務器處理的。
半連接的TCP有限狀態機
5. 通過直接路由實現虛擬服務器（VS/DR）
跟VS/TUN 方法相同，VS/DR利用大多數Internet服務的非對稱特點，負載調度器中只負責調度請求，而服務器直接將響應返回給客戶，可以極大地提高整個集群系統的吞吐量。該方法與IBM的NetDispatcher產品中使用的方法類似（其中服務器上的IP地址配置方法是相似的），但IBM的 NetDispatcher是非常昂貴的商品化產品，我們也不知道它內部所使用的機制，其中有些是IBM的專利。
VS/DR的體系結構如圖 7所示：調度器和服務器組都必須在物理上有一個網卡通過不分斷的局域網相連，如通過高速的交換機或者HUB相連。VIP地址為調度器和服務器組共享，調度器配置的VIP地址是對外可見的，用于接收虛擬服務的請求報文；所有的服務器把VIP地址配置在各自的Non-ARP網絡設備上，它對外面是不可見的，只是用于處理目標地址為VIP的網絡請求。
VS/DR的體系結構
VS/DR 的工作流程如圖8所示：它的連接調度和管理與VS/NAT和VS/TUN中的一樣，它的報文轉發方法又有不同，將報文直接路由給目標服務器。在VS/DR 中，調度器根據各個服務器的負載情況，動態地選擇一臺服務器，不修改也不封裝IP報文，而是將數據幀的mac地址改為選出服務器的MAC地址，再將修改后的數據幀在與服務器組的局域網上發送。因為數據幀的MAC地址是選出的服務器，所以服務器肯定可以收到這個數據幀，從中可以獲得該IP報文。當服務器發現報文的目標地址VIP是在本地的網絡設備上，服務器處理這個報文，然后根據路由表將響應報文直接返回給客戶。
VS/DR的工作流程
在VS/DR中，根據缺省的TCP/IP協議棧處理，請求報文的目標地址為VIP，響應報文的源地址肯定也為VIP，所以響應報文不需要作任何修改，可以直接返回給客戶，客戶認為得到正常的服務，而不會知道是哪一臺服務器處理的。
VS/DR負載調度器跟VS/TUN一樣只處于從客戶到服務器的半連接中，按照半連接的TCP有限狀態機進行狀態遷移。
6.三種方法的優缺點比較
三種IP負載均衡技術的優缺點歸納在下表中：
_VS/NATVS/TUNVS/DRServeranyTunnelingNon-arp deviceserver networkprivateLAN/WANLANserver numberlow (10~20)High (100)High (100)server gatewayload balancerown routerOwn router
注：以上三種方法所能支持最大服務器數目的估計是假設調度器使用100M網卡，調度器的硬件配置與后端服務器的硬件配置相同，而且是對一般Web服務。使用更高的硬件配置（如千兆網卡和更快的處理器）作為調度器，調度器所能調度的服務器數量會相應增加。當應用不同時，服務器的數目也會相應地改變。所以，以上數據估計主要是為三種方法的伸縮性進行量化比較。
6.1. Virtual Server via NAT
VS/NAT 的優點是服務器可以運行任何支持TCP/IP的操作系統，它只需要一個IP地址配置在調度器上，服務器組可以用私有的IP地址。缺點是它的伸縮能力有限，當服務器結點數目升到20時，調度器本身有可能成為系統的新瓶頸，因為在VS/NAT中請求和響應報文都需要通過負載調度器。 我們在Pentium 166 處理器的主機上測得重寫報文的平均延時為60us，性能更高的處理器上延時會短一些。假設TCP報文的平均長度為536 Bytes，則調度器的最大吞吐量為8.93 MBytes/s. 我們再假設每臺服務器的吞吐量為800KBytes/s，這樣一個調度器可以帶動10臺服務器。（注：這是很早以前測得的數據）
基于 VS/NAT的的集群系統可以適合許多服務器的性能要求。如果負載調度器成為系統新的瓶頸，可以有三種方法解決這個問題：混合方法、VS/TUN和 VS/DR。在DNS混合集群系統中，有若干個VS/NAT負載調度器，每個負載調度器帶自己的服務器集群，同時這些負載調度器又通過RR-DNS組成簡單的域名。但VS/TUN和VS/DR是提高系統吞吐量的更好方法。
對于那些將IP地址或者端口號在報文數據中傳送的網絡服務，需要編寫相應的應用模塊來轉換報文數據中的IP地址或者端口號。這會帶來實現的工作量，同時應用模塊檢查報文的開銷會降低系統的吞吐率。
6.2. Virtual Server via IP Tunneling
在VS/TUN 的集群系統中，負載調度器只將請求調度到不同的后端服務器，后端服務器將應答的數據直接返回給用戶。這樣，負載調度器就可以處理大量的請求，它甚至可以調度百臺以上的服務器（同等規模的服務器），而它不會成為系統的瓶頸。即使負載調度器只有100Mbps的全雙工網卡，整個系統的最大吞吐量可超過 1Gbps。所以，VS/TUN可以極大地增加負載調度器調度的服務器數量。VS/TUN調度器可以調度上百臺服務器，而它本身不會成為系統的瓶頸，可以用來構建高性能的超級服務器。
VS/TUN技術對服務器有要求，即所有的服務器必須支持“IP Tunneling”或者“IP Encapsulation”協議。目前，VS/TUN的后端服務器主要運行Linux操作系統，我們沒對其他操作系統進行測試。因為“IP Tunneling”正成為各個操作系統的標準協議，所以VS/TUN應該會適用運行其他操作系統的后端服務器。
6.3. Virtual Server via Direct Routing
跟VS/TUN方法一樣，VS/DR調度器只處理客戶到服務器端的連接，響應數據可以直接從獨立的網絡路由返回給客戶。這可以極大地提高LVS集群系統的伸縮性。
跟VS/TUN相比，這種方法沒有IP隧道的開銷，但是要求負載調度器與實際服務器都有一塊網卡連在同一物理網段上，服務器網絡設備（或者設備別名）不作ARP響應，或者能將報文重定向（Redirect）到本地的Socket端口上。
7.小結
本文主要講述了LVS集群中的三種IP負載均衡技術。在分析網絡地址轉換方法（VS/NAT）的缺點和網絡服務的非對稱性的基礎上，我們給出了通過IP隧道實現虛擬服務器的方法VS/TUN，和通過直接路由實現虛擬服務器的方法VS/DR，極大地提高了系統的伸縮性。
