Table of Contents

Introduction

The Linux Virtual Server is a highly scalable and highly available server built on a cluster of real servers, with the load balancer running on the Linux operating system. The architecture of the server cluster is fully transparent to end users, and the users interact as if it were a single high-performance virtual server.

The real servers and the load balancers may be interconnected by either high-speed LAN or by geographically dispersed WAN. The load balancers can dispatch requests to the different servers and make parallel services of the cluster to appear as a virtual service on a single IP address, and request dispatching can use IP load balancing technolgies or application-level load balancing technologies. Scalability of the system is achieved by transparently adding or removing nodes in the cluster. High availability is provided by detecting node or daemon failures and reconfiguring the system appropriately.

现在Web服务中越来越多地使用CGI、动态主页等CPU密集型应用,这对服务器的性能有较高要求。未来的网络服务会提供更丰富的内容、更好的交互性、更高的安全性等,需要服务器具有更强的CPU和I/O处理能力。例如,通过HTTPS(Secure HTTP)取一个静态页面需要的处理性能比通过HTTP的高一个数量级,HTTPS正在被电子商务站点广为使用。所以,网络流量并不能说明全部问题,要考虑到应用本身的发展也需要越来越强的处理性能。

对用硬件和软件方法实现高可伸缩、高可用网络服务的需求不断增长,这种需求可以归结以下几点:

可伸缩性(Scalability),当服务的负载增长时,系统能被扩展来满足需求,且不降低服务质量。 高可用性(Availability),尽管部分硬件和软件会发生故障,整个系统的服务必须是每天24小时每星期7天可用的。 可管理性(Manageability),整个系统可能在物理上很大,但应该容易管理。 价格有效性(Cost-effectiveness),整个系统实现是经济的、易支付的。

服务器集群系统

通过高性能网络或局域网互联的服务器集群正成为实现高可伸缩的、高可用网络服务的有效结构。这种松耦合结构的服务器集群系统有下列优点:

  • 性能

    网络服务的工作负载通常是大量相互独立的任务,通过一组服务器分而治之,可以获得很高的整体性能。

  • 性能/价格比

    组成集群系统的PC服务器或RISC服务器和标准网络设备因为大规模生产降低成本,价格低,具有最高的性能/价格比。若整体性能随着结点数的增长而接近线性增加,该系统的性能/价格比接近于PC服务器。所以,这种松耦合结构比紧耦合的多处理器系统具有更好的性能/价格比。

  • 可伸缩性

    集群系统中的结点数目可以增长到几千个,乃至上万个,其伸缩性远超过单台超级计算机。

  • 高可用性

    在硬件和软件上都有冗余,通过检测软硬件的故障,将故障屏蔽,由存活结点提供服务,可实现高可用性。

当然,用服务器集群系统实现可伸缩网络服务也存在很多挑战性的工作:

  • 透明性(Transparency)

    如何高效地使得由多个独立计算机组成的松藕合的集群系统构成一个虚拟服务器;客户端应用程序与集群系统交互时,就像与一台高性能、高可用的服务器交互一样,客户端无须作任何修改。部分服务器的切入和切出不会中断服务,这对用户也是透明的。

  • 性能(Performance)

    性能要接近线性加速,这需要设计很好的软硬件的体系结构,消除系统可能存在的瓶颈。将负载较均衡地调度到各台服务器上。

  • 高可用性(Availability)

    需要设计和实现很好的系统资源和故障的监测和处理系统。当发现一个模块失败时,要这模块上提供的服务迁移到其他模块上。在理想状况下,这种迁移是即时的、自动的。

  • 可管理性(Manageability)

    要使集群系统变得易管理,就像管理一个单一映像系统一样。在理想状况下,软硬件模块的插入能做到即插即用(Plug & Play)。

  • 可编程性(Programmability)

    在集群系统上,容易开发应用程序。

Linux Vertual Server

针对高可伸缩、高可用网络服务的需求,我们给出了基于IP层和基于内容请求分发的负载平衡调度解决方法,并在Linux内核中实现了这些方法,将一组服务器构成一个实现可伸缩的、高可用网络服务的虚拟服务器。

一组服务器通过高速的局域网或者地理分布的广域网相互连接,在它们的前端有一个负载调度器(Load Balancer)。负载调度器能无缝地将网络请求调度到真实服务器上,从而使得服务器集群的结构对客户是透明的,客户访问集群系统提供的网络服务就像访 问一台高性能、高可用的服务器一样。客户程序不受服务器集群的影响不需作任何修改。系统的伸缩性通过在服务机群中透明地加入和删除一个节点来达到,通过检 测节点或服务进程故障和正确地重置系统达到高可用性。由于我们的负载调度技术是在Linux内核中实现的,我们称之为Linux虚拟服务器(Linux Virtual Server)。

               ---------------------    --------
               | Internet/Intranet | <- | User |
               -----------v---------    --------
                          | Virtual IP Address
--------------------------|-------------------------------
                  --------------------------             |
                  | Load Balancer | Backup |             | <- Load Balancer
                  --------------------------             |
  Virtual Server          |                              |
                     -----------                         |
        -------------| LAN/WAN |---------------          |
        |            -----------              |          |
        |                 |                   |          |
---------------------------------------------------------|
| Real Server 1 | Real Server 2 |  ...  | Real Server  n | <- Server Cluster
|--------------------------------------------------------|
| Database | Network FileSystem | Distributed FileSystem | <- Storage
----------------------------------------------------------

LVS集群采用IP负载均衡技术和基于内容请求分发技术。调度器具有很好的吞吐率,将请求均衡地转移到不同的服务器上执行,且调度器自动屏蔽掉服 务器的故障,从而将一组服务器构成一个高性能的、高可用的虚拟服务器。整个服务器集群的结构对客户是透明的,而且无需修改客户端和服务器端的程序。

LVS 集群分为三层结构:

  • 负载调度器 (Load Balancer):它是整个 LVS 集群对外的前端机器,负责将 client 请求发送到一组服务器 (多台LB IP) 上执行,而 client 端认为是返回来一个同一个 IP (通常把这个IP 称为虚拟IP/VIP)

    Distribute requests among servers in the cluster

    Compared to DNS based load balancing, dispatcher can schedule requests at fine granularity, such as per connection, for better load balancing among servers. Failure can be masked when one server or more fail. Server management is becoming easy, and administrator can take a server or more in and out of service at any time, which won’t interrupt services to end users.

  • 服务器池 (Server Pool):一组真正执行 client 请求的服务器,执行的服务有WEB、MAIL、FTP和DNS等。
  • 共享存储(Shared Storage):它为 Server Pool 提供了一个共享的存储区,这样很容易使得服务器池拥有相同的内容,提供相同的服务。

调度器是服务器集群系统的唯一入口点(Single Entry Point),它可以采用IP负载均衡技术、基于内容请求分发技术或者两者相结合。在IP负载均衡技术中,需要服务器池拥有相同的内容提供相同的服务。当客户请求到达时,调度器只根据服务器负载情况和设定的调度算法从服务器池中选出一个服务器,将该请求转发到选出的服务器,并记录这个调度;当这个请求的其他报文到达,也会被转发到前面选出的服务器。在基于内容请求分发技术中,服务器可以提供不同的服务,当客户请求到达时,调度器可根据请求的内容选择服务器执行请求。因为所有的操作都是在Linux操作系统核心空间中将完成的,它的调度开销很小,所以它具有很高的吞吐率。

服务器池的结点数目是可变的。当整个系统收到的负载超过目前所有结点的处理能力时,可以在服务器池中增加服务器来满足不断增长的请求负载。对大多数网络服务来说,请求间不存在很强的相关性,请求可以在不同的结点上并行执行,所以整个系统的性能基本上可以随着服务器池的结点数目增加而线性增长。

共享存储通常是数据库、网络文件系统或者分布式文件系统。 服务器结点需要动态更新的数据一般存储在数据库系统中,同时数据库会保证并发访问时数据的一致性。 静态的数据可以存储在网络文件系统(如NFS/CIFS)中,但网络文件系统的伸缩能力有限,一般来说,NFS/CIFS服务器只能支持3~6个繁忙的服务器结点。 对于规模较大的集群系统,可以考虑用分布式文件系统,如AFS[1]、GFS[2.3]、Coda[4]和 Intermezzo[5]等。 分布式文件系统可为各服务器提供共享的存储区,它们访问分布式文件系统就像访问本地文件系统一样,同时分布式文件系统可提供良好的伸缩性和可用性。 此外,当不同服务器上的应用程序同时读写访问分布式文件系统上同一资源时,应用程序的访问冲突需要消解才能使得资源处于一致状态。 这需要一个分布式锁管理器(Distributed Lock Manager),它可能是分布式文件系统内部提供的,也可能是外部的。开发者在写应用程序时,可以使用分布式锁管理器来保证应用程序在不同结点上并发访 问的一致性。

负载调度器、服务器池和共享存储系统通过高速网络相连接,如100Mbps交换网络、Myrinet和Gigabit网络等。使用高速的网络,主要为避免当系统规模扩大时互联网络成为整个系统的瓶颈。

Graphic Monitor是为系统管理员提供整个集群系统的监视器,它可以监视系统的状态。Graphic Monitor是基于浏览器的,所以无论管理员在本地还是异地都可以监测系统的状况。为了安全的原因,浏览器要通过HTTPS(Secure HTTP)协议和身份认证后,才能进行系统监测,并进行系统的配置和管理。

The goal of Linux Virtual Server Project:

Build a high-performance and highly available server for Linux using clustering technology, which provides good scalability, reliability and serviceability. 使用集群技术和Linux操作系统实现一个高性能、高可用的服务器,它具有很好的可伸缩性(Scalability)、可靠性(Reliability)和可管理性(Manageability)。

层次体系结构

层次的体系结构可以使得层与层之间相互独立,每一个层次提供不同的功能,在一个层次可以重用不同的已有软件。例如,调度器层提供了负载平衡、可伸缩性和高可用性等,在服务器层可以运行不同的网络服务,如Web、Cache、Mail和Media等,来提供不同的可伸缩网络服务。明确的功能划分和清晰的层次结构使得系统容易建设,以后整个系统容易维护,而且系统的性能容易被扩展。

共享存储

共享存储如分布式文件系统在这个LVS集群系统是可选项。当网络服务需要有相同的内容,共享存储是很好的选择,否则每台服务器需要将相同的内容复制到本地硬盘上。当系统存储的内容越多,这种无共享结构(Shared-nothing Structure)的代价越大,因为每台服务器需要一样大的存储空间,任何的更新需要涉及到每台服务器,系统的维护代价会非常高。

共享存储为服务器组提供统一的存储空间,这使得系统的内容维护工作比较轻松,如Webmaster只需要更新共享存储中的页面,对所有的服务器都有效。分布式文件系统提供良好的伸缩性和可用性,当分布式文件系统的存储空间增加时,所有服务器的存储空间也随之增大。对于大多数 Internet服务来说,它们都是读密集型(Read-intensive)的应用,分布式文件系统在每台服务器使用本地硬盘作Cache(如 2Gbytes的空间),可以使得访问分布式文件系统本地的速度接近于访问本地硬盘。

此外,存储硬件技术的发展也促使从无共享的集群向共享存储的集群迁移。存储区域网(Storage Area Networks)技术解决了集群的每个结点可以直接连接/共享一个庞大的硬盘阵列,硬件厂商也提供多种硬盘共享技术,如光纤通道(Fiber Channel)、共享SCSI(Shared SCSI)。InfiniBand是一个通用的高性能I/O规范,使得存储区域网中以更低的延时传输I/O消息和集群通讯消息,并且提供很好的伸缩性。 InfiniBand得到绝大多数的大厂商的支持,如Compaq、Dell、Hewlett-Packard、IBM、Intel、Microsoft 和SUN Microsystems等,它正在成为一个业界的标准。这些技术的发展使得共享存储变得容易,规模生产也会使得成本逐步降低。

共享存储是媒体集群系统中最关键的问题,因为媒体文件往往非常大(一部片子需要几百兆到几千兆的存储空间),这对存储的容量和读的速度 有较高的要求。对于规模较小的媒体集群系统,例如有3至6个媒体服务器结点,存储系统可以考虑用带千兆网卡的Linux服务器,使用软件RAID和日志型 文件系统,再运行内核的NFS服务,会有不错的效果。对于规模较大的媒体集群系统,最好选择对文件分段(File Stripping)存储和文件缓存有较好支持的分布式文件系统;媒体文件分段存储在分布式文件系统的多个存储结点上,可以提高文件系统的性能和存储结点 间的负载均衡;媒体文件在媒体服务器上自动地被缓存,可提高文件的访问速度。否则,可以考虑自己在媒体服务器上开发相应的工具,如缓存工具能定时地统计出 最近的热点媒体文件,将热点文件复制到本地硬盘上,并替换缓存中的非热点文件,最后通知其他媒体服务器结点它所缓存的媒体文件以及负载情况;在媒体服务器 上有应用层调度工具,它收到客户的媒体服务请求,若所请求的媒体文件缓存在本地硬盘上,则直接转给本地媒体服务进程服务,否则先考虑该文件是否被其他媒体 服务器缓存;如该文件被其他服务器缓存并且该服务器不忙,则将请求转给该服务器上的媒体服务进程处理,否则直接转给本地媒体服务进程,从后端的共享存储中 读出媒体文件。

高可用性

集群系统的特点是它在软硬件上都有冗余。系统的高可用性可以通过检测节点或服务进程故障和正确地重置系统来实现,使得系统收到的请求能被存活的结点处理。

通常,我们在调度器上有资源监测进程来时刻监视各个服务器结点的健康状况。当服务器对ICMP ping不可达时或者探测她的网络服务在指定的时间没有响应时,资源监测进程通知操作系统内核将该服务器从调度列表中删除或者失效。这样,新的服务请求就 不会被调度到坏的结点。资源监测进程能通过电子邮件或传呼机向管理员报告故障。一旦监测进程到服务器恢复工作,通知调度器将其加入调度列表进行调度。另 外,通过系统提供的管理程序,管理员可发命令随时可以将新机器加入服务来提高系统的处理性能,也可以将已有的服务器切出服务,以便对服务器进行系统维护。

现在前端的调度器有可能成为系统的单一失效点(Single Point of Failure)。一般来说,调度器的可靠性较高,因为调度器上运行的程序较少而且大部分程序早已经遍历过,但我们不能排除硬件老化、网络线路或者人为误 操作等主要故障。为了避免调度器失效而导致整个系统不能工作,我们需要设立一个从调度器作为主调度器的备份。两个心跳(Heartbeat)进程[6]分 别在主、从调度器上运行,它们通过串口线和UDP等心跳线来相互定时地汇报各自的健康状况。当从调度器不能听得主调度器的心跳时,从调度器通过ARP欺骗 (Gratuitous ARP)来接管集群对外的Virtual IP Address,同时接管主调度器的工作来提供负载调度服务。当主调度器恢复时,这里有两种方法,一是主调度器自动变成从调度器,二是从调度器释放 Virtual IP Address,主调度器收回Virtual IP Address并提供负载调度服务。这里,多条心跳线可以使得因心跳线故障导致误判(即从调度器认为主调度器已经失效,其实主调度器还在正常工作)的概论 降到最低。

通常,当主调度器失效时,主调度器上所有已建立连接的状态信息将丢失,已有的连接会中断。客户需要向重新连接,从调度器才会将新连接调 度到各个服务器上,这对客户会造成一定的不便。为此,IPVS调度器在Linux 内核中实现一种高效状态同步机制,将主调度器的状态信息及时地同步到从调度器。当从调度器接管时,绝大部分已建立的连接会持续下去。

可伸缩Cache服务

有效的网络Cache系统可以大大地减少网络流量、降低响应延时以及服务器的负载。 但是,若Cache服务器超载而不能及时地处理请求,反而会增加响应延时。 所以,Cache服务的可伸缩性很重要,当系统负载不断增长时,整个系统能被扩展来提高Cache服务的处理能力。 尤其,在主干网上的 Cache 服务可能需要几个Gbps的吞吐率,单台服务器(例如SUN目前最高端的Enterprise 10000服务器)远不能达到这个吞吐率。 可见,通过PC服务器集群实现可伸缩Cache服务是很有效的方法,也是性能价格比最高的方法。

IPVS负载调度器一般使用IP隧道方法(即VS/TUN方法,将在以后文章中详细叙述),来架构Cache集群系统,因为Cache服务器可能被 放置不同的地方(例如在接近主干Internet连接处),而调度器与Cache服务器池可能不在同一个物理网络中。采用VS/TUN方法,调度器只调度 Web Cache请求,而Cache服务器将响应数据直接返回给客户。在请求对象不能在本地命中的情况下,Cache服务器要向源服务器发请求,将结果取回,最 后将结果返回给客户;若采用NAT技术的商品化调度器,需要四次进出调度器,完成这个请求。而用VS/TUN方法(或者VS/DR方法),调度器只调度一 次请求,其他三次都由Cache服务器直接访问Internet完成。所以,这种方法对Cache集群系统特别有效。

Cache服务器采用本地硬盘来存储可缓存的对象,因为存储可缓存的对象是写操作,且占有一定的比例,通过本地硬盘可以提高I/O的访 问速度。Cache服务器间有专用的多播通道(Multicast Channel),通过ICP协议(Internet Cache Protocol)来交互信息。当一台Cache服务器在本地硬盘中未命中当前请求时,它可以通过ICP查询其他Cache服务器是否有请求对象的副本, 若存在,则从邻近的Cache服务器取该对象的副本,这样可以进一步提高Cache服务的命中率。

实现虚拟服务的相关方法

基于RR-DNS的解决方法

RR-DNS(Round-Robin Domain Name System)

这种方法带来几个问题。第一,域名服务 器是一个分布式系统,是按照一定的层次结构组织的。当用户就域名解析请求提交给本地的域名服务器,它会因不能直接解析而向上一级域名服务器提交,上一级域 名服务器再依次向上提交,直到RR-DNS域名服器把这个域名解析到其中一台服务器的IP地址。可见,从用户到RR-DNS间存在多台域名服器,而它们都 会缓冲已解析的名字到IP地址的映射,这会导致该域名服器组下所有用户都会访问同一WEB服务器,出现不同WEB服务器间严重的负载不平衡。为了保证在域 名服务器中域名到IP地址的映射不被长久缓冲,RR-DNS在域名到IP地址的映射上设置一个TTL(Time To Live)值,过了这一段时间,域名服务器将这个映射从缓冲中淘汰。当用户请求,它会再向上一级域名服器提交请求并进行重新影射。这就涉及到如何设置这个 TTL值,若这个值太大,在这个TTL期间,很多请求会被映射到同一台WEB服务器上,同样会导致严重的负载不平衡。若这个值太小,例如是0,会导致本地 域名服务器频繁地向RR-DNS提交请求,增加了域名解析的网络流量,同样会使RR-DNS服务器成为系统中一个新的瓶颈。

第二,用户机器 会缓冲从名字到IP地址的映射,而不受TTL值的影响,用户的访问请求会被送到同一台WEB服务器上。由于用户访问请求的突发性和访问方式不同,例如有的 人访问一下就离开了,而有的人访问可长达几个小时,所以各台服务器间的负载仍存在倾斜(Skew)而不能控制。假设用户在每个会话中平均请求数为20,负 载最大的服务器获得的请求数额高于各服务器平均请求数的平均比率超过百分之三十。也就是说,当TTL值为0时,因为用户访问的突发性也会存在着较严重的负 载不平衡。

第三,系统的可靠性和可维护性差。若一台服务器失效,会导致将域名解析到该服务器的用户看到服务中断,即使用户按 “Reload”按钮,也无济于事。系统管理员也不能随时地将一台服务器切出服务进行系统维护,如进行操作系统和应用软件升级,这需要修改RR-DNS服 务器中的IP地址列表,把该服务器的IP地址从中划掉,然后等上几天或者更长的时间,等所有域名服器将该域名到这台服务器的映射淘汰,和所有映射到这台服 务器的客户机不再使用该站点为止。

基于客户端的解决方法

基于客户端的解决方法需要每个客户程序都有一定的服务器集群的知识,进而把以负载均衡的方式将请求发到不同的服务器。例如,Netscape Navigator浏览器访问Netscape的主页时,它会随机地从一百多台服务器中挑选第N台,最后将请求送往wwwN.netscape.com。 然而,这不是很好的解决方法,Netscape只是利用它的Navigator避免了RR-DNS解析的麻烦,当使用IE等其他浏览器不可避免的要进行 RR-DNS解析。

基于应用层负载均衡调度的解决方法

多台服务器通过高速的互联网络连接成一个集群系统,在前端有一个基于应用层的负载调度器。当用户访问请求到达调度器时,请求会提交给作负载均衡调度的应用程 序,分析请求,根据各个服务器的负载情况,选出一台服务器,重写请求并向选出的服务器访问,取得结果后,再返回给用户。

应用层负载均衡调度的典型代表有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连接,一次是 从用户到调度器,另一次是从调度器到真实服务器;需要对请求进行分析和重写。这些处理都需要不小的CPU、内存和网络等资源开销,且处理时间长。所构成系 统的性能不能接近线性增加的,一般服务器组增至3或4台时,调度器本身可能会成为新的瓶颈。所以,这种基于应用层负载均衡调度的方法的伸缩性极其有限。第 二,基于应用层的负载均衡调度器对于不同的应用,需要写不同的调度器。以上几个系统都是基于HTTP协议,若对于FTP、Mail、POP3等应用,都需 要重写调度器。

基于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处理上存在问题。

基于IP层负载均衡调度的解决方法

通过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地址 上的一个虚拟服务。

在一组服务器前有一个调度器,它们是通过Switch/HUB相连接的。这些服务器 提供相同的网络服务、相同的内容,即不管请求被发送到哪一台服务器,执行结果是一样的。服务的内容可以复制到每台服务器的本地硬盘上,可以通过网络文件系 统(如NFS)共享,也可以通过一个分布式文件系统来提供。

客户通过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。

通过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地址上的虚拟网络服务。

调度器根据各个服务器的负载情况,动态地选择一台服务器, 将请求报文封装在另一个IP报文中,再将封装后的IP报文转发给选出的服务器;服务器收到报文后,先将报文解封获得原来目标地址为VIP的报文,服务器发 现VIP地址被配置在本地的IP隧道设备上,所以就处理这个请求,然后根据路由表将响应报文直接返回给客户。

           ------------------
IP Packet  | VIP |          |            Linux Director
           ------------------
                   | Encapsulating       Select one real server, encapsulate and
   ----------------v---------            forward it to the real server. Linux is
   | SrvIP | VIP |          |            on the client-to-server half connection
   --------------------------
                   |
              -----v-----
              | LAN/WAN |
              -----v-----
                   |
   ----------------v---------
   | SrvIP | VIP |          |            The real server
   --------------------------
                   | Decapsulating       Decapsulate the packet and process the
           ------------------            packet locally and send response packet
IP Packet  | VIP |          |            to the client directly
           ------------------

在这里需要指出,根据缺省的TCP/IP协议栈处理,请求报文的目标地址为VIP,响应报文的源地址肯定也为VIP,所以响应报文不需要作任何修改,可以直接返回给客户,客户认为得到正常的服务,而不会知道究竟是哪一台服务器处理的。

通过直接路由实现虚拟服务器(VS/DR

VS/TUN 方法相同,VS/DR利用大多数Internet服务的非对称特点,负载调度器中只负责调度请求,而服务器直接将响应返回给客户,可以极大地提高整个集群 系统的吞吐量。该方法与IBM的NetDispatcher产品中使用的方法类似(其中服务器上的IP地址配置方法是相似的),但IBM的 NetDispatcher是非常昂贵的商品化产品,我们也不知道它内部所使用的机制,其中有些是IBM的专利。

调度器和服务器组都必须在物理上有一个网卡通过不分断的局域网相连,如通过高速的交换机或者HUB相连。VIP地址为调度器和服务器组共享,调度 器配置的VIP地址是对外可见的,用于接收虚拟服务的请求报文;所有的服务器把VIP地址配置在各自的Non-ARP网络设备上,它对外面是不可见的,只 是用于处理目标地址为VIP的网络请求。

它的连接调度和管理与VS/NATVS/TUN中的一样,它的报文转发方法又有不同,将报文直接路由给目标服务器。在VS/DR 中,调度器根据各个服务器的负载情况,动态地选择一台服务器,不修改也不封装IP报文,而是将数据帧的MAC地址改为选出服务器的MAC地址,再将修改后 的数据帧在与服务器组的局域网上发送。因为数据帧的MAC地址是选出的服务器,所以服务器肯定可以收到这个数据帧,从中可以获得该IP报文。当服务器发现 报文的目标地址VIP是在本地的网络设备上,服务器处理这个报文,然后根据路由表将响应报文直接返回给客户。

                         ------------------
IP Packet                | VIP |          |    Linux Director
                         ------------------
                           | Encapsulating     Select one real server, directly
           ----------------v---------------    forward it to the real server.
Data Frame | Srv MAC |...| VIP |          |    Linux Directory is on the
           --------------------------------    client-to-server half connection.
                |
        --------v---------
        | Physical Layer |
        --------v---------
                |
           -----v--------------------------
Data Frame | Srv MAC |...| VIP |          |    The real server
           --------------------------------
                            | Decapsulating    Since the VIP is on its loopback
                         ---v--------------    alias interface, it processes the
IP Packet                | VIP |          |    packet locally and send response
                         ------------------    packet to the client directly.

在这里需要指出,根据缺省的TCP/IP协议栈处理,请求报文的目标地址为VIP,响应报文的源地址肯定也为VIP,所以响应报文不需要作任何修改,可以直接返回给客户,客户认为得到正常的服务,而不会知道究竟是哪一台服务器处理的。

VS/DR负载调度器跟VS/TUN一样只处于从客户到服务器的半连接中,按照半连接的TCP有限状态机进行状态迁移。

三种方法的优缺点比较

Compare VS/NAT VS/TUN VS/DR
Server any Tunneling Non-arp device
Server network private LAN/WAN LAN
Server number low (10~20) high (100) high (100)
Server gateway load balancer own router own router

LVS集群中实现的三种IP负载均衡技术,它们主要解决系统的可伸缩性和透明性问题,如何通过负载调度器将请求高 效地分发到不同的服务器执行,使得由多台独立计算机组成的集群系统成为一台虚拟服务器;客户端应用程序与集群系统交互时,就像与一台高性能的服务器交互一样。

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/TUNVS/DR。在DNS混合集群系统中,有若干个VS/NAT负载调度器,每个负载调度器带自己的服务器集群,同时这些负载调度器又通过RR-DNS组成简 单的域名。但VS/TUNVS/DR是提高系统吞吐量的更好方法。

对于那些将IP地址或者端口号在报文数据中传送的网络服务,需要编写相应的应用模块来转换报文数据中的IP地址或者端口号。这会带来实现的工作量,同时应用模块检查报文的开销会降低系统的吞吐率。

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应该会适用运行其他操作系统的后端服务器。

Virtual Server via Direct Routing

VS/TUN方法一样,VS/DR调度器只处理客户到服务器端的连接,响应数据可以直接从独立的网络路由返回给客户。这可以极大地提高LVS集群系统的伸缩性。

VS/TUN相比,这种方法没有IP隧道的开销,但是要求负载调度器与实际服务器都有一块网卡连在同一物理网段上,服务器网络设备(或者设备别名)不作ARP响应,或者能将报文重定向(Redirect)到本地的Socket端口上。

四种模式的性能比较

DR > IP TUNNEL > NAT > FULL NAT

因为DR模式, IP TUNEL 模式都是在 package in 时经过LVS ;在package out是直接返回给client;所以二者的性能比NAT 模式高;但IP TUNNEL 因为是TUNNEL 模式比较复杂,其性能不如DR模式;FULL NAT 模式因为不仅要更换 DST IP 还更换 SOURCE IP 所以性能比NAT 下降10%

LVS集群的负载调度

本文将主要讲述在负载调度器上的负载调度策略和算法,如何将请求流调度到各台服务器,使得各台服务器尽可能地保持负载均衡。文章主要由两个部分组 成。第一部分描述IP负载均衡软件IPVS在内核中所实现的各种连接调度算法;第二部分给出一个动态反馈负载均衡算法(Dynamic-feedback load balancing),它结合内核中的加权连接调度算法,根据动态反馈回来的负载信息来调整服务器的权值,来进一步避免服务器间的负载不平衡。

IP虚拟服务器软件IPVS

在调度器的实现技术中,IP负载均衡技术是效率最高的。 在已有的IP负载均衡技术中有通过网络地址转换(Network Address Translation)将一组服务器构成一个高性能的、高可用的虚拟服务器,我们称之为VS/NAT技术(Virtual Server via Network Address Translation),大多数商品化的IP负载均衡调度器产品都是使用此方法,如Cisco的LocalDirector、F5的Big/IP和 Alteon的ACEDirector。 在分析VS/NAT的缺点和网络服务的非对称性的基础上,我们提出通过IP隧道实现虚拟服务器的方法VS/TUN (Virtual Server via IP Tunneling),和通过直接路由实现虚拟服务器的方法VS/DR(Virtual Server via Direct Routing),它们可以极大地提高系统的伸缩性。所以,IPVS软件实现了这三种IP负载均衡技术,它们的大致原理如下(我们将在其他章节对其工作原 理进行详细描述),

IPVS在内核中的负载均衡调度是以连接为粒度的。在HTTP协议(非持久)中,每个对象从WEB服务器上获取都需要建立一个TCP连接,同一用户 的不同请求会被调度到不同的服务器上,所以这种细粒度的调度在一定程度上可以避免单个用户访问的突发性引起服务器间的负载不平衡。

  1. Virtual Server via Network Address Translation(VS/NAT

    通过网络地址转换,调度器重写请求报文的目标地址,根据预设的调度算法,将请求分派给后端的真实服务器;真实服务器的响应报文通过调度器时,报文的源地址被重写,再返回给客户,完成整个负载调度过程。

  2. Virtual Server via IP Tunneling(VS/TUN

    采用NAT技术时,由于请求和响应报文都必须经过调度器地址重写,当客户请求越来越多时,调度器的处理能力将成为瓶颈。为了解决这个问题,调度器把请求报 文通过IP隧道转发至真实服务器,而真实服务器将响应直接返回给客户,所以调度器只处理请求报文。由于一般网络服务应答比请求报文大许多,采用 VS/TUN技术后,集群系统的最大吞吐量可以提高10倍。

  3. Virtual Server via Direct Routing(VS/DR

    VS/DR通过改写请求报文的MAC地址,将请求发送到真实服务器,而真实服务器将响应直接返回给客户。同VS/TUN技术一样,VS/DR技术可极大地 提高集群系统的伸缩性。这种方法没有IP隧道的开销,对集群中的真实服务器也没有必须支持IP隧道协议的要求,但是要求调度器与真实服务器都有一块网卡连 在同一物理网段上。

针对不同的网络服务需求和服务器配置, 在内核中的连接调度算法上,IPVS已实现了以下八种调度算法:

1. 轮叫(Round-Robin)

调度器通过”轮叫”调度算法将外部请求按顺序轮流分配到集群中的真实服务器上,它均等地对待每一台服务器,而不管服务器上实际的连接数和系统负载。

轮叫调度(Round Robin Scheduling)算法就是以轮叫的方式依次将请求调度不同的服务器,即每次调度执行i = (i + 1) mod n,并选出第i台服务器。算法的优点是其简洁性,它无需记录当前所有连接的状态,所以它是一种无状态调度。

在系统实现时,我们引入了一个额外条件,当服务器的权值为零时,表示该服务器不可用而不被调度。这样做的目的是将服务器切出服务(如屏蔽服务器故障和系统维护),同时与其他加权算法保持一致。所以,算法要作相应的改动,它的算法流程如下:

j = i /* i: last selected server */
do {
    j = (j + i) mod n;
    if (weight(server[j]) > 0) {
        i = j;
        return server[i];
    }
} while (i != j);
return NULL;

轮叫调度算法假设所有服务器处理性能均相同,不管服务器的当前连接数和响应速度。该算法相对简单,不适用于服务器组中处理性能不一的情况,而且当请求服务时间变化比较大时,轮叫调度算法容易导致服务器间的负载不平衡。

虽然Round-Robin DNS方法也是以轮叫调度的方式将一个域名解析到多个IP地址,但轮叫DNS方法的调度粒度是基于每个域名服务器的,域名服务器对域名解析的缓存会妨碍轮 叫解析域名生效,这会导致服务器间负载的严重不平衡。这里,IPVS轮叫调度算法的粒度是基于每个连接的,同一用户的不同连接都会被调度到不同的服务器 上,所以这种细粒度的轮叫调度要比DNS的轮叫调度优越很多。

2. 加权轮叫(Weighted Round-Robin)

调度器通过”加权轮叫”调度算法根据真实服务器的不同处理能力来调度访问请求。这样可以保证处理能力强的服务器处理更多的访问流量。调度器可以自动问询真实服务器的负载情况,并动态地调整其权值。

加权轮叫调度(Weighted Round-Robin Scheduling)算法可以解决服务器间性能不一的情况,它用相应的权值表示服务器的处理性能,服务器的缺省权值为1。假设服务器A的权值为1,B的 权值为2,则表示服务器B的处理性能是A的两倍。加权轮叫调度算法是按权值的高低和轮叫方式分配请求到各服务器。权值高的服务器先收到的连接,权值高的服 务器比权值低的服务器处理更多的连接,相同权值的服务器处理相同数目的连接数。加权轮叫调度算法流程如下:

假设有一组服务器S = {S0, S1, , Sn-1}W(Si)表示服务器Si的权值,一个
指示变量i表示上一次选择的服务器,指示变量cw表示当前调度的权值,max(S)
表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器权值的最大
公约数。变量i初始化为-1cw初始化为零。

while (true) {
  i = (i + 1) mod n;
  if (i == 0) {
     cw = cw - gcd(S); 
     if (cw <= 0) {
       cw = max(S);
       if (cw == 0)
         return NULL;
     }
  } 
  if (W(Si) >= cw) 
    return Si;
}

例如,有三个服务器A、B和C分别有权值4、3和2,则在一个调度周期内(mod sum(W(Si)))调度序列为AABABCABC。加权轮叫调度算法还是比较简单和高效。当请求的服务时间变化很大,单独的加权轮叫调度算法依然会导致服务器间的负载不平衡。

从上面的算法流程中,我们可以看出当服务器的权值为零时,该服务器不被被调度;当所有服务器的权值为零,即对于任意i有W(Si)=0,则没有任何 服务器可用,算法返回NULL,所有的新连接都会被丢掉。加权轮叫调度也无需记录当前所有连接的状态,所以它也是一种无状态调度。

3. 最少链接(Least Connections)

调度器通过”最少连接”调度算法动态地将网络请求调度到已建立的链接数最少的服务器上。如果集群系统的真实服务器具有相近的系统性能,采用”最小连接”调度算法可以较好地均衡负载。

最小连接调度(Least-Connection Scheduling)算法是把新的连接请求分配到当前连接数最小的服务器。最小连接调度是一种动态调度算法,它通过服务器当前所活跃的连接数来估计服务 器的负载情况。调度器需要记录各个服务器已建立连接的数目,当一个请求被调度到某台服务器,其连接数加1;当连接中止或超时,其连接数减一。

在系统实现时,我们也引入当服务器的权值为零时,表示该服务器不可用而不被调度,它的算法流程如下:

假设有一组服务器S = {S0, S1, ..., Sn-1}W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。

for (m = 0; m < n; m++) {
    if (W(Sm) > 0) {
        for (i = m+1; i < n; i++) {
            if (W(Si) <= 0)
                continue;
            if (C(Si) < C(Sm))
                m = i;
        }
        return Sm;
    }
}
return NULL;

当各个服务器有相同的处理性能时,最小连接调度算法能把负载变化大的请求分布平滑到各个服务器上,所有处理时间比较长的请求不可能被发送到同一台服 务器上。但是,当各个服务器的处理能力不同时,该算法并不理想,因为TCP连接处理请求后会进入TIME_WAIT状态,TCP的TIME_WAIT一般 为2分钟,此时连接还占用服务器的资源,所以会出现这样情形,性能高的服务器已处理所收到的连接,连接处于TIME_WAIT状态,而性能低的服务器已经 忙于处理所收到的连接,还不断地收到新的连接请求。

4. 加权最少链接(Weighted Least Connections)

在集群系统中的服务器性能差异较大的情况下,调度器采用”加权最少链接”调度算法优化负载均衡性能,具有较高权值的服务器将承受较大比例的活动连接负载。调度器可以自动问询真实服务器的负载情况,并动态地调整其权值。

加权最小连接调度(Weighted Least-Connection Scheduling)算法是最小连接调度的超集,各个服务器用相应的权值表示其处理性能。服务器的缺省权值为1,系统管理员可以动态地设置服务器的权 值。加权最小连接调度在调度新连接时尽可能使服务器的已建立连接数和其权值成比例。加权最小连接调度的算法流程如下:

假设有一组服务器S = {S0, S1, ..., Sn-1}W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。所有服务器当前连接数的总和为
CSUM = ΣC(Si)  (i=0, 1, .. , n-1)。当前的新连接请求会被发送服务器Sm
当且仅当服务器Sm满足以下条件
  (C(Sm) / CSUM)/ W(Sm) = min { (C(Si) / CSUM) / W(Si)}  (i=0, 1, . , n-1)
  其中W(Si)不为零
因为CSUM在这一轮查找中是个常数,所以判断条件可以简化为
  C(Sm) / W(Sm) = min { C(Si) / W(Si)}  (i=0, 1, . , n-1)
  其中W(Si)不为零

因为除法所需的CPU周期比乘法多,且在Linux内核中不允许浮点除法,服务器的
权值都大于零,所以判断条件C(Sm) / W(Sm) > C(Si) / W(Si) 可以进一步优化
C(Sm)*W(Si) > C(Si)* W(Sm)。同时保证服务器的权值为零时,服务器不被调
度。所以,算法只要执行以下流程。

for (m = 0; m < n; m++) {
    if (W(Sm) > 0) {
        for (i = m+1; i < n; i++) {
            if (C(Sm)*W(Si) > C(Si)*W(Sm))
                m = i;
        }
        return Sm;
    }
}
return NULL;

5. 基于局部性的最少链接(Locality-Based Least Connections)

“基于局部性的最少链接” 调度算法是针对目标IP地址的负载均衡,目前主要用于Cache集群系统。该算法根据请求的目标IP地址找出该目标IP地址最近使用的服务器,若该服务器 是可用的且没有超载,将请求发送到该服务器;若服务器不存在,或者该服务器超载且有服务器处于一半的工作负载,则用”最少链接”的原则选出一个可用的服务 器,将请求发送到该服务器。

基于局部性的最少链接调度(Locality-Based Least Connections Scheduling,以下简称为LBLC)算法是针对请求报文的目标IP地址的负载均衡调度,目前主要用于Cache集群系统,因为在Cache集群中 客户请求报文的目标IP地址是变化的。这里假设任何后端服务器都可以处理任一请求,算法的设计目标是在服务器的负载基本平衡情况下,将相同目标IP地址的 请求调度到同一台服务器,来提高各台服务器的访问局部性和主存Cache命中率,从而整个集群系统的处理能力。

LBLC调度算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器,若该服务器是可用的且没有超载,将请求发送到该服务器;若服务器不 存在,或者该服务器超载且有服务器处于其一半的工作负载,则用“最少链接”的原则选出一个可用的服务器,将请求发送到该服务器。该算法的详细流程如下:

假设有一组服务器S = {S0, S1, ..., Sn-1}W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。ServerNode[dest_ip]是一个关联变量,表示
目标IP地址所对应的服务器结点,一般来说它是通过Hash表实现的。WLC(S)表示
在集合S中的加权最小连接服务器,即前面的加权最小连接调度。Now为当前系统
时间。

if (ServerNode[dest_ip] is NULL) then {
    n = WLC(S);
    if (n is NULL) then return NULL;
    ServerNode[dest_ip].server = n;
} else {
    n = ServerNode[dest_ip].server;
    if ((n is dead) OR
        (C(n) > W(n) AND
         there is a node m with C(m) < W(m)/2))) then {
        n = WLC(S);
        if (n is NULL) then return NULL;
        ServerNode[dest_ip].server = n;
    }
}
ServerNode[dest_ip].lastuse = Now;
return n;

此外,对关联变量ServerNode[dest_ip]要进行周期性的垃圾回收(Garbage Collection),将过期的目标IP地址到服务器关联项进行回收。过期的关联项是指哪些当前时间(实现时采用系统时钟节拍数jiffies)减去最 近使用时间超过设定过期时间的关联项,系统缺省的设定过期时间为24小时。

6. 带复制的基于局部性最少链接(Locality-Based Least Connections with Replication)

“带复制的基于局部性最少链接”调度算法也是针对目标IP地址的负载均衡,目前主要用于Cache集群系统。它与LBLC算法的不同之处是它要维护从一个 目标IP地址到一组服务器的映射,而LBLC算法维护从一个目标IP地址到一台服务器的映射。该算法根据请求的目标IP地址找出该目标IP地址对应的服务 器组,按”最小连接”原则从服务器组中选出一台服务器,若服务器没有超载,将请求发送到该服务器,若服务器超载;则按”最小连接”原则从这个集群中选出一 台服务器,将该服务器加入到服务器组中,将请求发送到该服务器。同时,当该服务器组有一段时间没有被修改,将最忙的服务器从服务器组中删除,以降低复制的 程度。

带复制的基于局部性最少链接调度(Locality-Based Least Connections with Replication Scheduling,以下简称为LBLCR)算法也是针对目标IP地址的负载均衡,目前主要用于Cache集群系统。它与LBLC算法的不同之处是它要 维护从一个目标IP地址到一组服务器的映射,而LBLC算法维护从一个目标IP地址到一台服务器的映射。对于一个“热门”站点的服务请求,一台Cache 服务器可能会忙不过来处理这些请求。这时,LBLC调度算法会从所有的Cache服务器中按“最小连接”原则选出一台Cache服务器,映射该“热门”站 点到这台Cache服务器,很快这台Cache服务器也会超载,就会重复上述过程选出新的Cache服务器。这样,可能会导致该“热门”站点的映像会出现 在所有的Cache服务器上,降低了Cache服务器的使用效率。LBLCR调度算法将“热门”站点映射到一组Cache服务器(服务器集合),当该“热 门”站点的请求负载增加时,会增加集合里的Cache服务器,来处理不断增长的负载;当该“热门”站点的请求负载降低时,会减少集合里的Cache服务器 数目。这样,该“热门”站点的映像不太可能出现在所有的Cache服务器上,从而提供Cache集群系统的使用效率。

LBLCR算法先根据请求的目标IP地址找出该目标IP地址对应的服务器组;按“最小连接”原则从该服务器组中选出一台服务器,若服务器没有超载, 将请求发送到该服务器;若服务器超载;则按“最小连接”原则从整个集群中选出一台服务器,将该服务器加入到服务器组中,将请求发送到该服务器。同时,当该 服务器组有一段时间没有被修改,将最忙的服务器从服务器组中删除,以降低复制的程度。LBLCR调度算法的流程如下:

假设有一组服务器S = {S0, S1, ..., Sn-1}W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。ServerSet[dest_ip]是一个关联变量,表示
目标IP地址所对应的服务器集合,一般来说它是通过Hash表实现的。WLC(S)表示
在集合S中的加权最小连接服务器,即前面的加权最小连接调度;WGC(S)表示在
集合S中的加权最大连接服务器。Now为当前系统时间,lastmod表示集合的最近
修改时间,T为对集合进行调整的设定时间。

if (ServerSet[dest_ip] is NULL) then {
    n = WLC(S);
    if (n is NULL) then return NULL;
    add n into ServerSet[dest_ip];
} else {
    n = WLC(ServerSet[dest_ip]);
    if ((n is NULL) OR
        (n is dead) OR
        (C(n) > W(n) AND
         there is a node m with C(m) < W(m)/2))) then {
        n = WLC(S);
        if (n is NULL) then return NULL;
        add n into ServerSet[dest_ip];
    } else
    if (|ServerSet[dest_ip]| > 1 AND
        Now - ServerSet[dest_ip].lastmod > T) then {
        m = WGC(ServerSet[dest_ip]);
        remove m from ServerSet[dest_ip];
    }
}
ServerSet[dest_ip].lastuse = Now;
if (ServerSet[dest_ip] changed) then
    ServerSet[dest_ip].lastmod = Now;
return n;

此外,对关联变量ServerSet[dest_ip]也要进行周期性的垃圾回收(Garbage Collection),将过期的目标IP地址到服务器关联项进行回收。过期的关联项是指哪些当前时间(实现时采用系统时钟节拍数jiffies)减去最 近使用时间(lastuse)超过设定过期时间的关联项,系统缺省的设定过期时间为24小时。

7. 目标地址散列(Destination Hashing)

“目标地址散列”调度算法根据请求的目标IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。

目标地址散列调度(Destination Hashing Scheduling)算法也是针对目标IP地址的负载均衡,但它是一种静态映射算法,通过一个散列(Hash)函数将一个目标IP地址映射到一台服务器。

目标地址散列调度算法先根据请求的目标IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。该算法的流程如下:

假设有一组服务器S = {S0, S1, ..., Sn-1}W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。ServerNode[]是一个有256个桶(Bucket)的
Hash表,一般来说服务器的数目会运小于256,当然表的大小也是可以调整的。
算法的初始化是将所有服务器顺序、循环地放置到ServerNode表中。若服务器的
连接数目大于2倍的权值,则表示服务器已超载。

n = ServerNode[hashkey(dest_ip)];
if ((n is dead) OR
    (W(n) == 0) OR
    (C(n) > 2*W(n))) then
    return NULL;
return n;

在实现时,我们采用素数乘法Hash函数,通过乘以素数使得散列键值尽可能地达到较均匀的分布。所采用的素数乘法Hash函数如下:

static inline unsigned hashkey(unsigned int dest_ip)
{
    return (dest_ip* 2654435761UL) & HASH_TAB_MASK;
}
其中,2654435761UL22^32 (4294967296)间接近于黄金分割的素数,
  (sqrt(5) - 1) / 2 =  0.618033989
  2654435761 / 4294967296 = 0.618033987

8. 源地址散列(Source Hashing)

“源地址散列”调度算法根据请求的源IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。

源地址散列调度(Source Hashing Scheduling)算法正好与目标地址散列调度算法相反,它根据请求的源IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。它采用的散列函数与目标地址散列调度算法 的相同。它的算法流程与目标地址散列调度算法的基本相似,除了将请求的目标IP地址换成请求的源IP地址,所以这里不一一叙述。

在实际应用中,源地址散列调度和目标地址散列调度可以结合使用在防火墙集群中,它们可以保证整个系统的唯一出入口。

Configuration

yum install ipvsadm
# check if ip forwarding is active
sysctl net.ipv4.ip_forward
# setup director
/sbin/ifconfig eth0:0 192.168.1.200 broadcast 192.168.1.200 netmask 255.255.255.255 up
/sbin/route add -host 192.168.1.200 dev eth0:0
ipvsadm --add-service --tcp-service oxnz.github.io:80 --scheduler rr
# setup real server
/sbin/ifconfig lo:0 192.168.1.200 broadcast 192.168.1.200 netmask 255.255.255.255 up
/sbin/route add -host 192.168.1.200 dev lo:0
echo 1 > /proc/sys/net/ipv4/conf/lo/arp_ignore
echo 1 > /proc/sys/net/ipv4/conf/all/arp_ignore
echo 2 > /proc/sys/net/ipv4/conf/lo/arp_announce
echo 2 > /proc/sys/net/ipv4/conf/all/arp_announce
ipvsadm --add-server -t oxnz.github.io:80 --real-server 192.168.1.107:8000 --gatewaying
ipvsadm -a --tcp-service oxnz.github.io:80 -r 192.168.1.108:8000 -g
# save
ipvsadm --save > /etc/sysconfig/ipvsadm
systemctl restart ipvsadm
# verify
ipvsadm --list

动态反馈负载均衡算法

动态反馈负载均衡算法考虑服务器的实时负载和响应情况,不断调整服务器间处理请求的比例,来避免有些服务器超载时依然收到大量请求,从而提 高整个系统的吞吐率。

在负载调度器上运行Monitor Daemon进程,Monitor Daemon来监视和收集各个服务器的负载信息。Monitor Daemon可根据多个负载信息算出一个综合负载值。Monitor Daemon将各个服务器的综合负载值和当前权值算出一组新的权值,若新权值和当前权值的差值大于设定的阀值,Monitor Daemon将该服务器的权值设置到内核中的IPVS调度中,而在内核中连接调度一般采用加权轮叫调度算法或者加权最小连接调度算法。

------------------------------------
|          Linux Directory         |
|----------------------------------|
|  ------------------              |
|  | Monitor Daemon |<------<<<---------
|  -------v--^-------              |   |
| weights |  | counters  Userspace |   |
|---------|--|---------------------|   |
|       --v-----            Kernel |   ^
|       | IPVS |                   |   ^
|       --------                   |   ^
|-----------------------------------   |
|                                      |
| Server 1 | Server 2 | ... | Server n |
----->>-------->>------->>>----->>------

连接调度

当客户通过TCP连接访问网络访问时,服务所需的时间和所要消耗的计算资源是千差万别的,它依赖于很多因素。例如,它依赖于请求的服务类型、当前网 络带宽的情况、以及当前服务器资源利用的情况。一些负载比较重的请求需要进行计算密集的查询、数据库访问、很长响应数据流;而负载比较轻的请求往往只需要 读一个HTML页面或者进行很简单的计算。

请求处理时间的千差万别可能会导致服务器利用的倾斜(Skew),即服务器间的负载不平衡。例如,有一个WEB页面有A、B、C和D文件,其中D是 大图像文件,浏览器需要建立四个连接来取这些文件。当多个用户通过浏览器同时访问该页面时,最极端的情况是所有D文件的请求被发到同一台服务器。所以说, 有可能存在这样情况,有些服务器已经超负荷运行,而其他服务器基本是闲置着。同时,有些服务器已经忙不过来,有很长的请求队列,还不断地收到新的请求。反 过来说,这会导致客户长时间的等待,觉得系统的服务质量差。

简单连接调度

简单连接调度可能会使得服务器倾斜的发生。在上面的例子中,若采用轮叫调度算法,且集群中正好有四台服务器,必有一台服务器总是收到D文件的请求。这种调度策略会导致整个系统资源的低利用率,因为有些资源被用尽导致客户的长时间等待,而其他资源空闲着。

实际TCP/IP流量的特征

文献[1]说明网络流量是呈波浪型发生的,在一段较长时间的小流量后,会有一段大流量的访问,然后是小流量,这样跟波浪一样周期性地发生。文献 [2,3,4,5]揭示在WAN和LAN上网络流量存在自相似的特征,在WEB访问流也存在自相似性。这就需要一个动态反馈机制,利用服务器组的状态来应 对访问流的自相似性。

动态反馈负载均衡机制

TCP/IP流量的特征通俗地说是有许多短事务和一些长事务组成,而长事务的工作量在整个工作量占有较高的比例。所以,我们要设计一种负载均衡算法,来避免长事务的请求总被分配到一些机器上,而是尽可能将带有毛刺(Burst)的分布分割成相对较均匀的分布。

我们提出基于动态反馈负载均衡机制,来控制新连接的分配,从而控制各个服务器的负载。例如,在IPVS调度器的内核中使用加权轮叫调度 (Weighted Round-Robin Scheduling)算法来调度新的请求连接;在负载调度器的用户空间中运行Monitor Daemon。Monitor Daemon定时地监视和收集各个服务器的负载信息,根据多个负载信息算出一个综合负载值。Monitor Daemon将各个服务器的综合负载值和当前权值算出一组新的权值。当综合负载值表示服务器比较忙时,新算出的权值会比其当前权值要小,这样新分配到该服 务器的请求数就会少一些。当综合负载值表示服务器处于低利用率时,新算出的权值会比其当前权值要大,来增加新分配到该服务器的请求数。若新权值和当前权值 的差值大于设定的阀值,Monitor Daemon将该服务器的权值设置到内核中的IPVS调度中。过了一定的时间间隔(如2秒钟),Monitor Daemon再查询各个服务器的情况,并相应调整服务器的权值;这样周期性地进行。可以说,这是一个负反馈机制,使得服务器保持较好的利用率。

在加权轮叫调度算法中,当服务器的权值为零,已建立的连接会继续得到该服务器的服务,而新的连接不会分配到该服务器。系统管理员可以将一台服务器的 权值设置为零,使得该服务器安静下来,当已有的连接都结束后,他可以将该服务器切出,对其进行维护。维护工作对系统都是不可少的,比如硬件升级和软件更新 等,零权值使得服务器安静的功能很主要。所以,在动态反馈负载均衡机制中我们要保证该功能,当服务器的权值为零时,我们不对服务器的权值进行调整。

综合负载

在计算综合负载时,我们主要使用两大类负载信息:输入指标和服务器指标。输入指标是在调度器上收集到的,而服务器指标是在服务器上的各种负载信息。 我们用综合负载来反映服务器当前的比较确切负载情况,对于不同的应用,会有不同的负载情况,这里我们引入各个负载信息的系数,来表示各个负载信息在综合负 载中轻重。系统管理员根据不同应用的需求,调整各个负载信息的系数。另外,系统管理员设置收集负载信息的时间间隔。

输入指标主要是在单位时间内服务器收到新连接数与平均连接数的比例,它是在调度器上收集到的,所以这个指标是对服务器负载情况的一个估计值。在调度 器上有各个服务器收到连接数的计数器,对于服务器Si,可以得到分别在时间T1和T2时的计数器值Ci1和Ci2,计算出在时间间隔T2-T1内服务器 Si收到新连接数Ni = Ci2 - Ci1。这样,得到一组服务器在时间间隔T2-T1内服务器Si收到新连接数{Ni},服务器Si的输入指标INPUTi为其新连接数与n台服务器收到平 均连接数的比值,其公式为

服务器指标主要记录服务器各种负载信息,如服务器当前CPU负载LOADi、服务器当前磁盘使用情况Di、当前内存利用情况Mi和当前进程数目 Pi。有两种方法可以获得这些信息;一是在所有的服务器上运行着SNMP(Simple Network Management Protocol)服务进程,而在调度器上的Monitor Daemon通过SNMP向各个服务器查询获得这些信息;二是在服务器上实现和运行收集信息的Agent,由Agent定时地向Monitor Daemon报告负载信息。若服务器在设定的时间间隔内没有响应,Monitor Daemon认为服务器是不可达的,将服务器在调度器中的权值设置为零,不会有新的连接再被分配到该服务器;若在下一次服务器有响应,再对服务器的权值进 行调整。再对这些数据进行处理,使其落在[0, ∞)的区间内,1表示负载正好,大于1表示服务器超载,小于1表示服务器处于低负载状态。获得调整后的数据有DISKi、MEMORYi和 PROCESSi。

另一个重要的服务器指标是服务器所提供服务的响应时间,它能比较好地反映服务器上请求等待队列的长度和请求的处理时间。调度器上的Monitor Daemon作为客户访问服务器所提供的服务,测得其响应时间。例如,测试从WEB服务器取一个HTML页面的响应延时,Monitor Daemon只要发送一个“GET /”请求到每个服务器,然后记录响应时间。若服务器在设定的时间间隔内没有响应,Monitor Daemon认为服务器是不可达的,将服务器在调度器中的权值设置为零。同样,我们对响应时间进行如上调整,得到RESPONSEi。

这里,我们引入一组可以动态调整的系数Ri来表示各个负载参数的重要程度,其中ΣRi = 1。综合负载可以通过以下公式计算出:

例如,在WEB服务器集群中,我们采用以下系数{0.1, 0.3, 0.1, 0.1, 0.1, 0.3},认为服务器的CPU负载和请求响应时间较其他参数重要一些。若当前的系数Ri不能很好地反映应用的负载,系统管理员可以对系数不断地修正,直到 找到贴近当前应用的一组系数。

另外,关于查询时间间隔的设置,虽然很短的间隔可以更确切地反映各个服务器的负载,但是很频繁地查询(如1秒钟几次)会给调度器和服务器带来一定的 负载,如频繁执行的Monitor Daemon在调度器会有一定的开销,同样频繁地查询服务器指标会服务器带来一定的开销。所以,这里要有个折衷(Tradeoff),我们一般建议将时间 间隔设置在5到20秒之间。

权值计算

当服务器投入集群系统中使用时,系统管理员对服务器都设定一个初始权值DEFAULT_WEIGHTi,在内核的IPVS调度中也先使用这个权值。 然后,随着服务器负载的变化,对权值进行调整。为了避免权值变成一个很大的值,我们对权值的范围作一个限制[DEFAULT_WEIGHTi, SCALE*DEFAULT_WEIGHTi],SCALE是可以调整的,它的缺省值为10。

Monitor Daemon周期性地运行,若DEFAULT_WEIGHTi不为零,则查询该服务器的各负载参数,并计算出综合负载值AGGREGATE_LOADi。我们引入以下权值计算公式,根据服务器的综合负载值调整其权值。

在公式中,0.95是我们想要达到的系统利用率,A是一个可调整的系数(缺省值为5)。当综合负载值为0.95时,服务器权值不变;当综合负载值大 于0.95时,权值变小;当综合负载值小于0.95时,权值变大。若新权值大于SCALEDEFAULT_WEIGHTi,我们将新权值设为 SCALEDEFAULT_WEIGHTi。若新权值与当前权值的差异超过设定的阀值,则将新权值设置到内核中的IPVS调度参数中,否则避免打断 IPVS调度的开销。我们可以看出这是一个负反馈公式,会使得权值调整到一个稳定点,如系统达到理想利用率时,权值是不变的。

在实际使用中,若发现所有服务器的权值都小于他们的DEFAULT_WEIGHT,则说明整个服务器集群处于超载状态,这时需要加入新的服务器结点 到集群中来处理部分负载;反之,若所有服务器的权值都接近于SCALE*DEFAULT_WEIGHT,则说明当前系统的负载都比较轻。

内核Layer-7交换机KTCPVS

在基于IP负载调度技术中,当一个TCP连接的初始SYN报文到达时,调度器就选择一台服务器,将报文转发给它。此后通过查发报文的IP和TCP报文头地 址,保证此连接的后继报文被转发到该服务器。这样,IPVS无法检查到请求的内容再选择服务器,这就要求后端服务器组提供相同的服务,不管请求被发送到哪 一台服务器,返回结果都是一样的。但是,在有些应用中后端服务器功能不一,有的提供HTML文档,有的提供图片,有的提供CGI,这就需要基于内容的调度 (Content-Based Scheduling)。

由于用户空间TCP Gateway的开销太大,我们提出在操作系统的内核中实现Layer-7交换方法,来避免用户空间与核心空间的切换和内存复制的开销。在Linux操作系统的内核中,我们实现了Layer-7交换,称之为KTCPVS(Kernel TCP Virtual Server)。目前,KTCPVS已经能对HTTP请求进行基于内容的调度,但它还不很成熟,在其调度算法和各种协议的功能支持等方面,有大量的工作需要做。

虽然应用层交换处理复杂,它的伸缩性有限,但应用层交换带来以下好处:

  • 相同页面的请求被发送到同一服务器,可以提高单台服务器的Cache命中率。
  • 一些研究[5]表明WEB访问流中存在局部性。Layer-7交换可以充分利用访问的局部性,将相同类型的请求发送到同一台服务器,使得每台服务器收到的请求具有更好的相似性,可进一步提高单台服务器的Cache命中率。
  • 后端服务器可运行不同类型的服务,如文档服务,图片服务,CGI服务和数据库服务等。

LVS集群的特点

LVS集群的特点可以归结如下:

  1. 功能

    有实现三种IP负载均衡技术和八种连接调度算法的IPVS软件。在IPVS内部实现上,采用了高效的Hash函数和垃圾回收机制,能正确处理所调度报文相 关的ICMP消息(有些商品化的系统反而不能)。虚拟服务的设置数目没有限制,每个虚拟服务有自己的服务器集。它支持持久的虚拟服务(如HTTP Cookie和HTTPS等需要该功能的支持),并提供详尽的统计数据,如连接的处理速率和报文的流量等。针对大规模拒绝服务(Deny of Service)攻击,实现了三种防卫策略。 有基于内容请求分发的应用层交换软件KTCPVS,它也是在Linux内核中实现。有相关的集群管理软件对资源进行监测,能及时将故障屏蔽,实现系统的高可用性。主、从调度器能周期性地进行状态同步,从而实现更高的可用性。

  2. 适用性

    后端服务器可运行任何支持TCP/IP的操作系统,包括Linux,各种Unix(如FreeBSD、Sun Solaris、HP Unix等),Mac/OS和Windows NT/2000等。 负载调度器能够支持绝大多数的TCP和UDP协议:

    Protocol Content
    TCP HTTP,FTP,PROXY,SMTP,POP3,IMAP4,DNS,LDAP,HTTPS,SSMTP, etc.
    UDP DNS,NTP,ICP,视频、音频流播放协议, etc.

    无需对客户机和服务器作任何修改,可适用大多数Internet服务。

  3. 性能

    LVS服务器集群系统具有良好的伸缩性,可支持几百万个并发连接。配置100M网卡,采用VS/TUNVS/DR调度技术,集群系统的吞吐量可高达1Gbits/s;如配置千兆网卡,则系统的最大吞吐量可接近10Gbits/s。

  4. 可靠性

    LVS服务器集群软件已经在很多大型的、关键性的站点得到很好的应用,所以它的可靠性在真实应用得到很好的证实。有很多调度器运行一年多,未作一次重启动。

  5. 软件许可证

    LVS集群软件是按GPL(GNU Public License)许可证发行的自由软件,这意味着你可以得到软件的源代码,有权对其进行修改,但必须保证你的修改也是以GPL方式发行。

LVS集群的应用

LVS项目的开发进展与感触

目前,正在进行的 LVS项目开发工作包括:

  • 扩充IPVS对其他传输协议的支持,如AH(Authentication Header)和ESP(Encapsulating Security Payload )等,这样IPVS调度器将实现IPSec的服务器集群。
  • 提供一个统一的、功能较完善、更灵活的LVS集群管理软件。
  • 扩充和改进KTCPVS的调度算法和多种协议的支持,使之功能较完备和系统更稳定。
  • 在TCP粘合(TCP Splicing)和TCP转移(TCP Handoff)等方面,做一些尝试性工作,进一步改进LVS集群中的应用层调度。

Other software components for LVS

  • Keepalived
  • Linux-HA heartbeat package

Nginx Load Balancer

http {
    upstream servers {
        # ip_hash;
        # upstream_hash;
        # least_conn;
        server 192.168.1.107:8000 weight=3 max_fails=3 fail_timeout=20s;
        server 192.168.1.108:8000 weight=7 max_fails=3 fail_timeout=20s;
        server 192.168.1.109:8000 backup;
        server 192.168.1.110:8000 down;
    }
    server {
        listen 80;
        location / {
            proxy_pass http://servers;
        }
    }
}

Apache httpd

LoadModule proxy_module mod_proxy.so
LoadModule proxy_http_module mod_proxy_http.so
LoadModule proxy_balancer_module mod_proxy_balancer.so
ProxyRequests Off
<Proxy \*>
    Order deny,allow
    Deny from all
</Proxy>
<Proxy balancer://clusterX>
    BalancerMember http://192.168.1.107:8000
    BalancerMember http://192.168.1.108:8000
    Order allow,deny
    Allow from all
</Proxy>
ProxyPass / balancer://clusterX/

References