LVS的基本原理和算法

最近在网络上看到不少人热衷于Linux集群的部署和配置。但是配置的思路和具体的步骤实在不敢恭维。
为了解决一些新手在这方面存在的问题，特将本人原创的几个文档贡献出来。希望高手指正，也希望给新手一些帮助。

在调度器的实现技术中，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负载均衡技术，它们的大致原理如下：

Virtual Server via Network Address Translation（VS/NAT） 
通过网络地址转换，调度器重写请求报文的目标地址，根据预设的调度算法，将请求分派给后端真实服务器；真实服务器的响应报文通过调度器时，报文源地址被重写再返回给客户，完成整个负载调度过程。
下面的基本结构和三层结构其实都是利用NAT这种方式。这种情况的配置比较简单，但通常在流量比较大的情况下会造成调度器的瓶颈。因为服务数据的返回必须通过调度器出去。

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

Virtual Server via Direct Routing（VS/DR） 
VS/DR通过改写请求报文的MAC地址，将请求发送到真实服务器，而真实服务器将响应直接返回给客户。同VS/TUN技术一样，VS/DR技术 可极大地提高集群系统的伸缩性。这种方法没有IP隧道的开销，对集群中的真实服务器也没有必须支持IP隧道协议的要求，但是要求调度器与真实服务器都有一 块网卡连在同一物理网段上。也就是说，在这种结构中，数据从外部到内部真实服务器的访问会通过调度器进来，但是真实服务器对其的应答不是通过调度器出去。 即在大多数情况下，真实服务器可以通过各自的网关或者专用的网关对数据进行外发，从而降低调度器负载。

同时在LVS中提供了八种不同的调度算法以供按照实际需求选择：
轮叫（Round Robin） 
调度器通过"轮叫"调度算法将外部请求按顺序轮流分配到集群中的真实服务器上，它均等地对待每一台服务器，而不管服务器上实际的连接数和系统负载。 

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

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

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

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

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

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

源地址散列（Source Hashing） 
"源地址散列"调度算法根据请求的源IP地址，作为散列键（Hash Key）从静态分配的散列表找出对应的服务器，若该服务器是可用的且未超载，将请求发送到该服务器，否则返回空。 
上述八种负载均衡调度算法在实施中，节点的权重越高，在集群中使用的频率就越高。比如说权重为2的节点在每接收两个访问请求之后，权重为1的节点才接收一个访问请求。

LVS集群采用IP负载均衡技术和基于内容请求分发技术。调度器具有很好的吞吐率，将请求均衡地转移到不同的服务器上执行，且调度器自动屏蔽掉服 务器的故障，从而将一组服务器构成一个高性能的、高可用的虚拟服务器。整个服务器集群的结构对客户是透明的，而且无需修改客户端和服务器端的程序。
为此，在设计时需要考虑系统的透明性、可伸缩性、高可用性和易管理性。一般来说，LVS集群采用三层结构，其体系结构如图1所示，三层主要组成部分为： 

负载调度器（load balancer），它是整个集群对外面的前端机，负责将客户的请求发送到一组服务器上执行，而客户认为服务是来自一个IP地址（我们可称之为虚拟IP地址）上的。 
服务器池（server pool），是一组真正执行客户请求的服务器，服务有WEB、MAIL、FTP和DNS等。 
共享存储（shared storage），它为服务器池提供一个共享的存储区，这样很容易使得服务器池拥有相同的内容，提供相同的服务。 

调度器是服务器集群系统的唯一入口点（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）协议和身份认证后，才能进行 系统监测，并进行系统的配置和管理。
层次的体系结构可以使得层与层之间相互独立，每一个层次提供不同的功能，在一个层次可以重用不同的已有软件。例如，调度器层提供了负载平衡、可 伸缩性和高可用性等，在服务器层可以运行不同的网络服务，如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等，它正在成为一个业界的标准。这些技术的发展使得共享存储变得容易，规模生产也会使 得成本逐步降低。
集群系统的特点是它在软硬件上都有冗余。系统的高可用性可以通过检测节点或服务进程故障和正确地重置系统来实现，使得系统收到的请求能被存活的结点处理。
通常，我们在调度器上有资源监测进程来时刻监视各个服务器结点的健康状况。当服务器对ICMP ping不可达时或者探测她的网络服务在指定的时 间没有响应时，资源监测进程通知操作系统内核将该服务器从调度列表中删除或者失效。这样，新的服务请求就不会被调度到坏的结点。资源监测进程能通过电子邮 件或传呼机向管理员报告故障。一旦监测进程到服务器恢复工作，通知调度器将其加入调度列表进行调度。另外，通过系统提供的管理程序，管理员可发命令随时可 以将新机器加入服务来提高系统的处理性能，也可以将已有的服务器切出服务，以便对服务器进行系统维护。

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