Linux虚拟服务器是实现高可伸缩、高可用网络服务的Linux集群。我们在Linux内核中实现了三种基于IP层负载平衡调度的方法，能灵活高效地将一组服务器组成一个高可伸缩的、高可用的网络服务。通过在服务器集群中透明地加入和删除结点实现系统的伸缩性，通过检测结点或服务进程故障和正确地重置系统达到高可用性。本文详细讨论了Linux虚拟服务器的体系结构及设计方法。
随着Internet的飞速发展和对我们生活的深入影响，越来越多的个人在互联网上购物、娱乐、休闲、与人沟通、获取信息；越来越多的企业把他们与顾客和业务伙伴之间的联络搬到互联网上，通过网络来完成交易，建立与客户之间的联系。互联网的用户数和网络流量正以几何级数增长，这对网络服务的可伸缩性提出很高的要求。如热门的Web站点会因为被访问次数急剧增长和不能及时处理用户的请求，而导致用户长时间的等待。另外，随着电子商务等关键性应用在网上运行，任何例外的服务中断都将造成不可估量的损失，服务的高可用性也越来越重要。
与之相应地，对用硬件和软件方法实现高可伸缩、高可用网络服务的需求也在不断增长。单服务器显然不能处理不断增长的负载。这种服务器升级方法有下列不足：一是升级过程烦琐，机器切换会使服务暂时中断，并造成原有计算资源的浪费；二是越往高端的服务器，所花费的代价越大；三是一旦该服务器或应用软件失效，会导致整个服务的中断。通过高性能网络或局域网互联的服务器集群正成为实现高可伸缩的、高可用网络服务的有效结构。这种松耦合结构比单处理系统和紧耦合的多处理器系统具有更好的伸缩性和性能价格比，但是，这里有很多挑战性的工作，如何在集群系统实现并行网络服务，它对外是透明的，它具有良好的可伸缩性和可用性。
针对以上需求，我们给出了三种基于IP层负载平衡调度的解决方法，并在Linux内核中实现了这三种方法，将一组服务器构成一个实现可伸缩的、高可用网络服务的服务器集群，我们称之为Linux虚拟服务器（Linux Virtual Server）。在LVS集群中，使得服务器集群的结构对客户是透明的，客户访问集群提供的网络服务就像访问一台高性能、高可用的服务器一样。客户程序不受服务器集群的影响，不需作任何修改。系统的伸缩性通过在服务机群中透明地加入和删除一个节点来达到，通过检测节点或服务进程故障和正确地重置系统达到高可用性。
相关的解决方法
在网络服务中，一端是客户程序，另一端是服务程序，在中间可能有代理程序。由此看来，可以在不同的层次上实现多台服务器的负载均衡。用集群解决网络服务性能问题的现有方法主要分为以下四类:
● 基于客户端的方法
在Berkeley的Smart Client中，客户端的Applet向一组服务器查询负载情况，选出负载轻的服务器，再向该服务器发服务请求；当服务器失效时， Applet会尝试其他服务器。
● 服务端的RR-DNS方法
NCSA的可伸缩的Web服务器系统就是最早基于轮转域名系统RR-DNS(Round-Robin Domain Name System)的原型系统。其基本思想是：通过RR- DNS服务器把域名轮流解析到这组Web服务器的不同IP地址，将负载分到各台服务器上，从而提高整个系统的性能。然而，该方法存在以下问题：第一，域名服务系统是按层次结构组织的，各级域名服务器都会缓冲已解析的名字到IP地址的映射，它会妨碍Round- Robin方法在客户端生效，从而导致不同WEB服务器间严重的负载不平衡，另外，域名到IP地址映射的TTL(Time To Live)值较难设定。第二，由于用户访问请求的突发性和访问方式不同，即使TTL值为0，各服务器间的负载仍存在较严重的负载不平衡。第三，系统的可靠性和可维护性差，一台服务器失效或管理员对其进行维护，均会导致域名已被解析到该服务器的用户出现服务中止。
● 服务端的应用层负载平衡调度方法
EDDIE、Reverse-Proxy和SWEB都使用基于应用层调度的方法来建立一个可伸缩的WEB服务器。它们都将到达的HTTP请求转发到不同的Web 服务器，取得结果后，再返回给用户。该方法也存在一些问题：首先，从请求到达至处理结束，调度器需要进行四次从核心与用户空间的切换，从用户到调度器和调度器到真实服务器的两次TCP连接，系统处理开销特别大，致使系统的伸缩性有限。其次，基于应用层的负载平衡调度器与应用协议密切相关，对于HTTP、Proxy和SMTP等应用协议，需要写不同的调度器。
● 服务端的IP层负载平衡调度方法
Berkeley的MagicRouter、Cisco的LocalDirector、Altheon 的ACEDirector和F5的Big/IP等都是使用网络地址转换方法。MagicRouter是在Linux 1.3 版本上应用快速报文插入技术，使得进行负载平衡调度的用户进程访问网络设备接近核心空间的速度，降低了上下文切换的处理开销，但并不彻底，它只是研究的原型系统，没有成为有用的系统存活下来。
LVS集群的体系结构
LVS采用基于IP层负载平衡调度技术，在操作系统核心空间中将IP层上的TCP/UDP请求均衡地转移到不同的服务器上，且调度器自动屏蔽掉服务器的故障，从而将一组服务器构成一个高性能的、高可用的虚拟服务器。为此，在设计时需要考虑系统的透明性、可伸缩性、高可用性和易管理性。LVS集群的体系结构如图1所示，它有3个主要组成部分：
● 负载调度器（Load Balancer），它是整个集群对外面的前端机，负责将客户的发送到一组服务器上执行，而客户认为服务是来自一个IP地址上的。
● 服务器池（Server Pool），是一组真正执行客户请求的服务器，执行的服务有WEB、MAIL、FTP和DNS等。
● 后端存储（Backend Storage），它为服务器池提供一个共享的存储区，这样很容易使得服务器池拥护相同的内容提供相同的服务。
调度器采用基于IP层负载平衡调度技术。当客户请求到达时，调度器根据负载情况从服务器池中选出一个服务器，将该请求转发到选出的服务器，并记录这个调度。所有的操作都是在操作系统核心空间中完成的，它的调度开销很小，所以它能调度很多服务器，而本身不会成为系统的瓶颈。服务器池的结点数目是可变的。当整个系统收到的负载超过目前所有结点的处理能力时，可以在服务器池中增加服务器来满足不断增长的请求负载。对大多数网络服务来说，结点与结点间不存在很强的相关性，所以整个系统的性能可以随着服务器池的结点数目增加而线性增长。
集群系统的特点是它在软硬件上都有冗余。系统的高可用性可以通过检测节点或服务进程故障和正确地重置系统来实现。通常，在调度器上由资源监视进程来时刻监视各个服务器结点的健康状况，当服务器对ICMP ping不可达或网络服务在指定的时间没有响应时，资源监视进程通知操作系统内核，将该服务器从调度列表中删除或者失效。这样，新的服务请求就不会被调度到坏的结点。
现在前端的调度器有可能成为系统的单一失效点。为了避免调度器失效导致整个系统不能工作，需要设立调度器的备份。两个心跳进程（Heartbeat Daemon）分别在主、从调度器上运行，它们通过串口线和UDP等心跳线来相互汇报各自的健康情况。当从调度器不能听到主调度器的心跳时，从调度器会接管主调度器的工作提供负载调度服务。一般通过ARP欺骗（Gratuitous ARP）来接管集群的Virtual IP Address。当主调度器恢复时，将自动变成从调度器，或从调度器释放Virtual IP Address，主调度器收回Virtual IP Address并提供负载调度服务。然而，主调度器接管后会导致已有的调度信息丢失，需要客户程序重新发送请求。
后端存储通常用容错的分布式文件系统，如AFS、GFS、 Coda和Intermezzo等。这些系统会考虑文件访问的伸缩性和可用性。各服务器访问分布式文件系统就像访问本地文件系统一样。然而，当不同服务器上的应用程序同时访问分布式文件系统上同一资源时，应用程序的访问冲突需要消解才能使得资源处于一致状态。这需要一个分布式锁管理器（Distributed Lock Manager），它可能是分布式文件系统内部提供的，也可能是外部的。
IP负载均衡技术
LVS实现了三种IP负载均衡技术，它们分别为VS/NAT、 VS/TUN和VS/DR。以下几小节将描述它们的工作原理和它们的优缺点。在以下描述中，我们称客户的socket和服务器的socket之间的数据通信为连接，无论它们是使用TCP还是UDP协议。
Virtual Server via Network Address Translation（VS/NAT）
由于IPv4中IP地址空间的日益紧张和安全方面的原因，很多网络使用Internet上未被分配的保留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)。当内部网络中的主机要访问Internet或被Internet访问时，就需要采用网络地址转换（Network Address Translation, 以下简称NAT），将内部地址转化为 Internet上可用的外部地址。NAT的工作原理是报文头（目标地址、源地址和端口等）被正确改写后，客户相信它们连接一个IP地址，而不同IP地址的服务器组也认为它们是与客户直接相连的。由此，可以用NAT方法将不同IP地址的并行网络服务变成在一个IP 地址上的一个虚拟服务。
VS/NAT的体系结构如图2所示。在一组服务器前有一个调度器，用户通过Virtual IP Address（即调度器的外部地址）访问服务时，请求报文到达调度器，调度器以负载均衡方法从一组真实服务器选出一个，将报文的目标地址Virtual IP Address改写成选定服务器的地址，报文的目标端口改写成选定服务器的相应端口，最后将报文发送给选定的服务器。同时，调度器在Hash表中记录这个连接，当这个连接的下一个报文到达时，从Hash表中可以得到原选定服务器的地址和端口，进行同样的改写操作，并将报文传给原选定的服务器。真实服务器的回应报文经过调度器时，将报文的源地址和源端口改为Virtual IP Address和相应的端口，再把报文发给用户。当连接终止或超时，调度器将这个连接从Hash表中删除。这样，用户所看到的只是在Virtual IP Address 上提供的服务，而虚拟服务器的结构对用户是透明的。对改写后的报文，应用增量调整 Checksum的算法调整TCP Checksum的值，避免了扫描整个报文来计算Checksum的开销。 Virtual Server via IP Tunneling (VS/TUN)
在VS/NAT的集群系统中，请求和应答的数据包都需要通过负载调度器，当实际服务器的数量超过20时，负载调度器将成为集群系统的新瓶颈。许多Internet服务都有这样的特点：请求报文较短而响应报文往往包含大量的数据。如果能将请求和响应分开处理，即在负载调度器中只负责调度请求而响应直接返回给客户，将极大地提高整个集群系统的吞吐量。
利用IP隧道技术将请求报文封装转发给后端服务器，响应报文能从后端服务器直接返回给客户。但在这里，后端服务器有一组而非一个，所以我们不可能静态地建立一一对应的隧道，而是动态地选择一台服务器，将请求报文封装和转发给选出的服务器。这样，我们可以利用IP隧道的原理将一组服务器上的网络服务组成在一个IP地址上的虚拟网络服务。VS/TUN的体系结构如图3所示，各个服务器将 VIP地址配置在自己的IP隧道设备上
VS/TUN的连接调度和管理与VS/NAT中的一样，只是它的报文转发方法不同。调度器根据各个服务器的负载情况，动态地选择一台服务器，将请求报文封装在另一个IP报文中，再将封装后的IP报文转发给选出的服务器；那台服务器收到报文后，先将报文解封获得原来目标地址为VIP的报文，服务器发现VIP地址被配置在本地的IP隧道设备上，所以就处理这个请求，然后根据路由表将响应报文直接返回给客户。
Virtual Server via Direct Routing(VS/DR)
这种IP层负载均衡方法与IBM的NetDispatcher中的方法类似。它的体系结构如图4所示：调度器和服务器组都必须在物理上有一个网卡通过不分断的局域网相连，如通过交换机或者高速的HUB相连。VIP地址为调度器和服务器组共享，调度器配置的VIP地址是对外可见的，用于接收虚拟服务的请求报文；所有的服务器把VIP地址配置在各自的Non-ARP网络设备上，它对外面是不可见的，只是用于处理目标地址为VIP的网络请求。
VS/DR的连接调度和管理与VS/NAT和VS/TUN中的一样，它的报文转发方法又有不同，将报文直接路由给目标服务器。在VS/DR中，调度器根据各个服务器的负载情况，动态地选择一台服务器，不修改也不封装IP报文，而是将数据帧的MAC地址改为选出服务器的MAC地址，再将修改后的数据帧在与服务器组的局域网上发送；因为数据帧的MAC地址是选出的服务器，所以服务器肯定可以收到该报文，发现VIP地址被配置在本地的网络设备上，所以就处理这个请求，然后根据路由表将响应报文直接返回给客户。
三种方法的优缺点
三种IP负载均衡技术的优缺点归纳在下表中：
● Virtual Server via NAT
VS/NAT的优点是服务器可以运行任何支持TCP/IP的操作系统，它只需要一个IP地址配置在调度器上，服务器组可以用私有的IP地址。缺点是它的伸缩能力有限，当服务器结点数目升到20时，调度器本身有可能成为系统的新瓶颈，因为在VS/NAT中请求和响应报文都需要通过负载调度器。在Pentium 166主机上测得重写报文的平均延时为60us，假设TCP报文的平均长度为536 Bytes，则调度器的最大吞吐量为8.93 MBytes/s。再假设每台服务器的吞吐量为600KBytes/s，这样一个调度器可以带动16台服务器。
● Virtual Server via IP Tunneling
在VS/TUN的集群系统中，负载调度器只将请求调度到不同的实际服务器，实际服务器将应答的数据直接返回给用户。这样，负载调度器就可以处理巨量的请求，而不会成为系统的瓶颈。即使负载调度器只有100Mbps的全双工网卡，虚拟服务器的最大吞吐量可以达到几Gbps。所以，VS/TUN可以极大地增加负载调度器调度的服务器数量，它可以用来构建高性能超级服务器。VS/TUN技术对服务器的要求是所有的服务器必须支持“IP Tunneling”或者“IP Encapsulation”协议。目前，VS/TUN 的后端服务器主要运行Linux操作系统。因为“IP Tunneling”正成为各个操作系统的标准协议，所以VS/TUN也会适用运行其他操作系统的后端服务器。
● Virtual Server via Direct Routing
同VS/TUN一样，VS/DR调度器只处理客户到服务器端的连接，响应数据可以直接从独立的网络路由返回给客户。这可以极大地提高LVS集群系统的伸缩性。同VS/TUN相比，这种方法没有IP隧道的开销，但是要求负载调度器与实际服务器都有一块网卡连在同一物理网段上，服务器网络设备或者设备别名不作ARP 响应。
连接调度
负载平衡调度是以连接为粒度的。在HTTP协议（非持久）中，每个对象从WEB服务器上获取都需要建立一个TCP连接，同一用户的不同请求会被调度到不同的服务器上，所以这种细粒度的调度完全避免了用户访问的突发性引起的负载不平衡。我们已实现了以下4种调度算法：
轮转调度(Round-Robin Scheduling)
加权轮转调度(Weighted Round-Robin Scheduling)
最小连接调度（Least-Connection Scheduling）
加权最小连接调度（Weighted Least-Connection Scheduling）
轮转调度算法是假设所有服务器处理性能均相同，依次将请求调度不同的服务器，算法简单，但不适用于服务器组中处理性能不一的情况。为此使用加权轮转调度算法，用相应的权值表示服务器的处理性能，将请求数目按权值的比例分配到各服务器。权值高的服务器先收到连接，权值高的服务器比权值低的服务器处理更多的连接，相同权值的服务器处理相同数目的连接数。
最小连接调度是需要记录各个服务器已建立TCP连接的数目，把新的连接请求发送当前连接数最小的服务器。当各个服务器有相同的处理性能时，最小连接调度能把负载变化大的请求平滑分布到各个服务器上，所有处理时间比较长的请求不可能被发送到同一台服务器上。但是，当各个服务器的处理能力不同时，该算法并不理想，因为TCP连接处理请求后会进入TIME_WAIT状态，TCP的TIME_WAIT 一般为2分钟，此时连接还占用服务器的资源，所以会出现这样情形，性能高的服务器已处理所收到的连接，连接处于TIME_WAIT状态，而性能低的服务器既要忙于处理所收到的连接，还要收到新的连接请求。加权最小连接调度是最小连接调度的超集，各个服务器用相应的权值表示其处理性能。假设每台服务器的权值为Wi(i=1..n)，TCP连接数目为 Ti(i=1..n)，依次选Ti/Wi为最小者的服务器为调度对象。
Linux虚拟服务器在Linux内核实现了三种IP负载调度技术和四种连接调度算法。通过负载平衡调度、故障检测技术和集群管理等，将一组服务器组成一个高性能、高可用的网络服务。该系统具有良好的伸缩性，支持几百万个并发连接。无需对客户机和服务器作任何修改，可适用任何Internet站点。