Linux服务器集群系统

miaolingzizhzu

Linux服务器集群系统(一)

LVS项目介绍
　　
　　本文介绍了Linux服务器集群系统――LVS（Linux Virtual Server）项目的产生背景和目标，并描述了LVS服务器集群框架及目前提供的软件，列举LVS集群系统的特点和一些实际应用，最后，本文谈论了LVS项目的开发进展和开发感触。
　　1. 背景
　　
　　当今计算机技术已进入以网络为中心的计算时期。由于客户/服务器模型的简单性、易管理性和易维护性，客户/服务器计算模式在网上被大量采用。在九十年代中期，万维网（World Wide Web）的出现以其简单操作方式将图文并茂的网上信息带给普通大众，Web也正在从一种内容发送机制成为一种服务平台，大量的服务和应用（如新闻服务、网上银行、电子商务等）都是围绕着Web进行。这促进Internet用户剧烈增长和Internet流量爆炸式地增长，图1显示了1995至2000年与Internet连接主机数的变化情况[1]，可见增长趋势较以往更迅猛。
　　
　　　

　　图1：1995至2000年Internet主机数的变化
　　Internet的飞速发展给网络带宽和服务器带来巨大的挑战。从网络技术的发展来看，网络带宽的增长远高于处理器速度和内存访问速度的增长，如100M Ethernet、ATM、Gigabit Ethernet等不断地涌现，10Gigabit Ethernet即将就绪，在主干网上密集波分复用（DWDM）将成为宽带IP的主流技术[2,3]，Lucent已经推出在一根光纤跑800Gigabit的WaveStar? OLS 800G产品[4]。所以，我们深信越来越多的瓶颈会出现在服务器端。很多研究显示Gigabit Ethernet在服务器上很难使得其吞吐率达到1Gb/s的原因是协议栈（TCP/IP）和操作系统的低效，以及处理器的低效，这需要对协议的处理方法、操作系统的调度和IO的处理作更深入的研究。在高速网络上，重新设计单台服务器上的网络服务程序也是个重要课题。
　　
　　比较热门的站点会吸引前所未有的访问流量，例如根据Yahoo的新闻发布，Yahoo已经每天发送6.25亿页面[5]。一些网络服务也收到巨额的流量，如American Online的Web Cache系统每天处理50.2亿个用户访问Web的请求，每个请求的平均响应长度为5.5Kbytes。与此同时，很多网络服务因为访问次数爆炸式地增长而不堪重负，不能及时处理用户的请求，导致用户进行长时间的等待，大大降低了服务质量。如何建立可伸缩的网络服务来满足不断增长的负载需求已成为迫在眉睫的问题。
　　
　　大部分网站都需要提供每天24小时、每星期7天的服务，对电子商务等网站尤为突出，任何服务中断和关键性的数据丢失都会造成直接的商业损失。例如，根据Dell的新闻发布[6]，Dell现在每天在网站上的交易收入为一千四百万美元，一个小时的服务中断都会造成平均五十八万美元的损失。所以，这对网络服务的可靠性提出了越来越高的要求。
　　
　　现在Web服务中越来越多地使用CGI、动态主页等CPU密集型应用，这对服务器的性能有较高要求。未来的网络服务会提供更丰富的内容、更好的交互性、更高的安全性等，需要服务器具有更强的CPU和I/O处理能力。例如，通过HTTPS（Secure HTTP）取一个静态页面需要的处理性能比通过HTTP的高一个数量级，HTTPS正在被电子商务站点广为使用。所以，网络流量并不能说明全部问题，要考虑到应用本身的发展也需要越来越强的处理性能。
　　
　　因此，对用硬件和软件方法实现高可伸缩、高可用网络服务的需求不断增长，这种需求可以归结以下几点：
　　
　　可伸缩性（Scalability），当服务的负载增长时，系统能被扩展来满足需求，且不降低服务质量。
　　高可用性（Availability），尽管部分硬件和软件会发生故障，整个系统的服务必须是每天24小时每星期7天可用的。
　　可管理性（Manageability），整个系统可能在物理上很大，但应该容易管理。
　　价格有效性（Cost-effectiveness），整个系统实现是经济的、易支付的。
　　2. 服务器集群系统
　　
　　对称多处理（Symmetric Multi-Processor，简称SMP）是由多个对称的处理器、和通过总线共享的内存和I/O部件所组成的计算机系统。SMP是一种低并行度的结构，是我们通常所说的"紧耦合多处理系统"，它的可扩展能力有限，但SMP的优点是单一系统映像（Single System Image），有共享的内存和I/O，易编程。
　　
　　由于SMP的可扩展能力有限，SMP服务器显然不能满足高可伸缩、高可用网络服务中的负载处理能力不断增长需求。随着负载不断增长，会导致服务器不断地升级。这种服务器升级有下列不足：一是升级过程繁琐，机器切换会使服务暂时中断，并造成原有计算资源的浪费；二是越往高端的服务器，所花费的代价越大；三是SMP服务器是单一故障点（Single Point of Failure），一旦该服务器或应用软件失效，会导致整个服务的中断。
　　
　　通过高性能网络或局域网互联的服务器集群正成为实现高可伸缩的、高可用网络服务的有效结构。这种松耦合结构的服务器集群系统有下列优点：
　　
　　性能
　　网络服务的工作负载通常是大量相互独立的任务，通过一组服务器分而治之，可以获得很高的整体性能。
　　
　　性能/价格比
　　组成集群系统的PC服务器或RISC服务器和标准网络设备因为大规模生产降低成本，价格低，具有最高的性能/价格比。若整体性能随着结点数的增长而接近线性增加，该系统的性能/价格比接近于PC服务器。所以，这种松耦合结构比紧耦合的多处理器系统具有更好的性能/价格比。
　　
　　可伸缩性
　　集群系统中的结点数目可以增长到几千个，乃至上万个，其伸缩性远超过单台超级计算机。
　　
　　高可用性
　　在硬件和软件上都有冗余，通过检测软硬件的故障，将故障屏蔽，由存活结点提供服务，可实现高可用性。
　　
　　当然，用服务器集群系统实现可伸缩网络服务也存在很多挑战性的工作：
　　
　　透明性（Transparency）
　　如何高效地使得由多个独立计算机组成的松藕合的集群系统构成一个虚拟服务器；客户端应用程序与集群系统交互时，就像与一台高性能、高可用的服务器交互一样，客户端无须作任何修改。部分服务器的切入和切出不会中断服务，这对用户也是透明的。
　　
　　性能（Performance）
　　性能要接近线性加速，这需要设计很好的软硬件的体系结构，消除系统可能存在的瓶颈。将负载较均衡地调度到各台服务器上。
　　
　　高可用性（Availability）
　　需要设计和实现很好的系统资源和故障的监测和处理系统。当发现一个模块失败时，要这模块上提供的服务迁移到其他模块上。在理想状况下，这种迁移是即时的、自动的。
　　
　　可管理性（Manageability）
　　要使集群系统变得易管理，就像管理一个单一映像系统一样。在理想状况下，软硬件模块的插入能做到即插即用（Plug & Play）。
　　
　　可编程性（Programmability）
　　在集群系统上，容易开发应用程序。
　　
　　3. Linux Virtual Server项目
　　
　　针对高可伸缩、高可用网络服务的需求，我们给出了基于IP层和基于内容请求分发的负载平衡调度解决方法，并在Linux内核中实现了这些方法，将一组服务器构成一个实现可伸缩的、高可用网络服务的虚拟服务器。
　　
　　虚拟服务器的体系结构如图2所示，一组服务器通过高速的局域网或者地理分布的广域网相互连接，在它们的前端有一个负载调度器（Load Balancer）。负载调度器能无缝地将网络请求调度到真实服务器上，从而使得服务器集群的结构对客户是透明的，客户访问集群系统提供的网络服务就像访问一台高性能、高可用的服务器一样。客户程序不受服务器集群的影响不需作任何修改。系统的伸缩性通过在服务机群中透明地加入和删除一个节点来达到，通过检测节点或服务进程故障和正确地重置系统达到高可用性。由于我们的负载调度技术是在Linux内核中实现的，我们称之为Linux虚拟服务器（Linux Virtual Server）。
　　
　　　

　　图2：虚拟服务器的结构
　　在1998年5月，我成立了Linux Virtual Server的自由软件项目，进行Linux服务器集群的开发工作。同时，Linux Virtual Server项目是国内最早出现的自由软件项目之一。
　　
　　Linux Virtual Server项目的目标：使用集群技术和Linux操作系统实现一个高性能、高可用的服务器，它具有很好的可伸缩性（Scalability）、可靠性（Reliability）和可管理性（Manageability）。
　　
　　目前，LVS项目已提供了一个实现可伸缩网络服务的Linux Virtual Server框架，如图3所示。在LVS框架中，提供了含有三种IP负载均衡技术的IP虚拟服务器软件IPVS、基于内容请求分发的内核Layer-7交换机KTCPVS和集群管理软件。可以利用LVS框架实现高可伸缩的、高可用的Web、Cache、Mail和Media等网络服务；在此基础上，可以开发支持庞大用户数的、高可伸缩的、高可用的电子商务应用。
　　

　　
　　图3：Linux虚拟服务器框架
　　
　　3.1 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），它们可以极大地提高系统的伸缩性。所以，IPV
LVS集群的体系结构
　　
　　本文主要介绍了LVS集群的体系结构。先给出LVS集群的通用体系结构，并讨论了其的设计原则和相应的特点；最后将LVS集群应用于建立可伸缩的Web、Media、Cache和Mail等网络服务。
　　1.引言
　　在过去的十几年中，Internet从几个研究机构相连为信息共享的网络发展成为拥有大量应用和服务的全球性网络，它正成为人们生活中不可缺少的一部分。虽然Internet发展速度很快，但建设和维护大型网络服务依然是一项挑战性的任务，因为系统必须是高性能的、高可靠的，尤其当访问负载不断增长时，系统必须能被扩展来满足不断增长的性能需求。由于缺少建立可伸缩网络服务的框架和设计方法，这意味着只有拥有非常出色工程和管理人才的机构才能建立和维护大型的网络服务。
　　
　　针对这种情形，本文先给出LVS集群的通用体系结构，并讨论了其的设计原则和相应的特点；最后将LVS集群应用于建立可伸缩的Web、Media、Cache和Mail等网络服务。
　　
　　2.LVS集群的通用体系结构
　　LVS集群采用IP负载均衡技术和基于内容请求分发技术。调度器具有很好的吞吐率，将请求均衡地转移到不同的服务器上执行，且调度器自动屏蔽掉服务器的故障，从而将一组服务器构成一个高性能的、高可用的虚拟服务器。整个服务器集群的结构对客户是透明的，而且无需修改客户端和服务器端的程序。
　　　


　　图1：LVS集群的体系结构
　　
　　为此，在设计时需要考虑系统的透明性、可伸缩性、高可用性和易管理性。一般来说，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）协议和身份认证后，才能进行系统监测，并进行系统的配置和管理。
　　
　　2.1. 为什么使用层次的体系结构
　　
　　
　　层次的体系结构可以使得层与层之间相互独立，每一个层次提供不同的功能，在一个层次可以重用不同的已有软件。例如，调度器层提供了负载平衡、可伸缩性和高可用性等，在服务器层可以运行不同的网络服务，如Web、Cache、Mail和Media等，来提供不同的可伸缩网络服务。明确的功能划分和清晰的层次结构使得系统容易建设，以后整个系统容易维护，而且系统的性能容易被扩展。
　　
　　2.2. 为什么是共享存储
　　
　　
　　共享存储如分布式文件系统在这个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等，它正在成为一个业界的标准。这些技术的发展使得共享存储变得容易，规模生产也会使得成本逐步降低。
　　
　　2.3. 高可用性
　　
　　
　　集群系统的特点是它在软硬件上都有冗余。系统的高可用性可以通过检测节点或服务进程故障和正确地重置系统来实现，使得系统收到的请求能被存活的结点处理。
　　
　　通常，我们在调度器上有资源监测进程来时刻监视各个服务器结点的健康状况。当服务器对ICMP ping不可达时或者探测她的网络服务在指定的时间没有响应时，资源监测进程通知操作系统内核将该服务器从调度列表中删除或者失效。这样，新的服务请求就不会被调度到坏的结点。资源监测进程能通过电子邮件或传呼机向管理员报告故障。一旦监测进程到服务器恢复工作，通知调度器将其加入调度列表进行调度。另外，通过系统提供的管理程序，管理员可发命令随时可以将新机器加入服务来提高系统的处理性能，也可以将已有的服务器切出服务，以便对服务器进行系统维护。
　　
　　现在前端的调度器有可能成为系统的单一失效点（Single Point of Failure）。一般来说，调度器的可靠性较高，因为调度器上运行的程序较少而且大部分程序早已经遍历过，但我们不能排除硬件老化、网络线路或者人为误操作等主要故障。为了避免调度器失效而导致整个系统不能工作，我们需要设立一个从调度器作为主调度器的备份。两个心跳（Heartbeat）进程[6]分别在主、从调度器上运行，它们通过串口线和UDP等心跳线来相互定时地汇报各自的健康状况。当从调度器不能听得主调度器的心跳时，从调度器通过ARP欺骗（Gratuitous ARP）来接管集群对外的Virtual IP Address，同时接管主调度器的工作来提供负载调度服务。当主调度器恢复时，这里有两种方法，一是主调度器自动变成从调度器，二是从调度器释放Virtual IP Address，主调度器收回Virtual IP Address并提供负载调度服务。这里，多条心跳线可以使得因心跳线故障导致误判（即从调度器认为主调度器已经失效，其实主调度器还在正常工作）的概论降到最低。
　　
　　通常，当主调度器失效时，主调度器上所有已建立连接的状态信息将丢失，已有的连接会中断。客户需要向重新连接，从调度器才会将新连接调度到各个服务器上，这对客户会造成一定的不便。为此，IPVS调度器在Linux 内核中实现一种高效状态同步机制，将主调度器的状态信息及时地同步到从调度器。当从调度器接管时，绝大部分已建立的连接会持续下去。
　　
　　3.可伸缩Web服务
　　
　　基于LVS的Web集群的体系结构如图2所示：第一层是负载调度器，一般采用IP负载均衡技术，可以使得整个系统有较高的吞吐率；第二层是Web服务器池，在每个结点上可以分别运行HTTP服务或HTTPS服务、或者两者都运行；第三层是共享存

temp LVS集群中的IP负载均衡技术
　　
　　本文在分析服务器集群实现虚拟网络服务的相关技术上，详细描述了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]。它的结构和工作流程如下图所示：
　　
　　　


　　图1：基于RR-DNS的可伸缩WEB服务器 (注：本图来自文献【9】)
　　有一组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地址处理请求
temp LVS集群的负载调度
　　
　　本文主要讲述了LVS集群的IP负载均衡软件IPVS在内核中实现的各种连接调度算法。针对请求的服务时间变化很大，给出一个动态反馈负载均衡算法，它结合内核中的加权连接调度算法，根据动态反馈回来的负载信息来调整服务器的权值，来进一步避免服务器间的负载不平衡。
　　1. 前言
　　在上一篇文章中，我们主要讲述了LVS集群中实现的三种IP负载均衡技术，它们主要解决系统的可伸缩性和透明性问题，如何通过负载调度器将请求高效地分发到不同的服务器执行，使得由多台独立计算机组成的集群系统成为一台虚拟服务器；客户端应用程序与集群系统交互时，就像与一台高性能的服务器交互一样。
　　
　　本文将主要讲述在负载调度器上的负载调度策略和算法，如何将请求流调度到各台服务器，使得各台服务器尽可能地保持负载均衡。文章主要由两个部分组成。第一部分描述IP负载均衡软件IPVS在内核中所实现的各种连接调度算法；第二部分给出一个动态反馈负载均衡算法（Dynamic-feedback load balancing），它结合内核中的加权连接调度算法，根据动态反馈回来的负载信息来调整服务器的权值，来进一步避免服务器间的负载不平衡。
　　
　　在下面描述中，我们称客户的socket和服务器的socket之间的数据通讯为连接，无论它们是使用TCP还是UDP协议。对于UDP数据报文的调度，IPVS调度器也会为之建立调度记录并设置超时值（如5分钟）；在设定的时间内，来自同一地址（IP地址和端口）的UDP数据包会被调度到同一台服务器。
　　
　　2. 内核中的连接调度算法
　　IPVS在内核中的负载均衡调度是以连接为粒度的。在HTTP协议（非持久）中，每个对象从WEB服务器上获取都需要建立一个TCP连接，同一用户的不同请求会被调度到不同的服务器上，所以这种细粒度的调度在一定程度上可以避免单个用户访问的突发性引起服务器间的负载不平衡。
　　
　　在内核中的连接调度算法上，IPVS已实现了以下八种调度算法：
　　
　　
　　轮叫调度（Round-Robin Scheduling）
　　加权轮叫调度（Weighted Round-Robin Scheduling）
　　最小连接调度（Least-Connection Scheduling）
　　加权最小连接调度（Weighted Least-Connection Scheduling）
　　基于局部性的最少链接（Locality-Based Least Connections Scheduling）
　　带复制的基于局部性最少链接（Locality-Based Least Connections with Replication Scheduling）
　　目标地址散列调度（Destination Hashing Scheduling）
　　源地址散列调度（Source Hashing Scheduling）
　　
　　下面，我们先介绍这八种连接调度算法的工作原理和算法流程，会在以后的文章中描述怎么用它们。
　　
　　2.1. 轮叫调度
　　
　　轮叫调度（Round Robin Scheduling）算法就是以轮叫的方式依次将请求调度不同的服务器，即每次调度执行i = (i 1) mod n，并选出第i台服务器。算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。
　　
　　在系统实现时，我们引入了一个额外条件，当服务器的权值为零时，表示该服务器不可用而不被调度。这样做的目的是将服务器切出服务（如屏蔽服务器故障和系统维护），同时与其他加权算法保持一致。所以，算法要作相应的改动，它的算法流程如下：
　　
　　轮叫调度算法流程
　　假设有一组服务器S = {S0, S1, …, Sn-1}，一个指示变量i表示上一次选择的
　　服务器，W(Si)表示服务器Si的权值。变量i被初始化为n-1，其中n > 0。
　　
　　j = i;
　　do {
　　 j = (j 1) mod n;
　　 if (W(Sj) > 0) {
　　 i = j;
　　 return Si;
　　 }
　　} while (j != i);
　　return NULL;
　　
　　
　　
　　
　　轮叫调度算法假设所有服务器处理性能均相同，不管服务器的当前连接数和响应速度。该算法相对简单，不适用于服务器组中处理性能不一的情况，而且当请求服务时间变化比较大时，轮叫调度算法容易导致服务器间的负载不平衡。
　　
　　虽然Round-Robin DNS方法也是以轮叫调度的方式将一个域名解析到多个IP地址，但轮叫DNS方法的调度粒度是基于每个域名服务器的，域名服务器对域名解析的缓存会妨碍轮叫解析域名生效，这会导致服务器间负载的严重不平衡。这里，IPVS轮叫调度算法的粒度是基于每个连接的，同一用户的不同连接都会被调度到不同的服务器上，所以这种细粒度的轮叫调度要比DNS的轮叫调度优越很多。
　　
　　2.2. 加权轮叫调度
　　
　　加权轮叫调度（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和cw最初都被初始化为零。
　　
　　while (true) {
　　 if (i == 0) {
　　 cw = cw - gcd(S);
　　 if (cw = cw)
　　 return Si;
　　}
　　
　　
　　
　　
　　例如，有三个服务器A、B和C分别有权值4、3和2，则在一个调度周期内(mod sum(W(Si)))调度序列为AABABCABC。加权轮叫调度算法还是比较简单和高效。当请求的服务时间变化很大，单独的加权轮叫调度算法依然会导致服务器间的负载不平衡。
　　
　　从上面的算法流程中，我们可以看出当服务器的权值为零时，该服务器不被被调度；当所有服务器的权值为零，即对于任意i有W(Si)=0，则没有任何服务器可用，算法返回NULL，所有的新连接都会被丢掉。加权轮叫调度也无需记录当前所有连接的状态，所以它也是一种无状态调度。
　　
　　2.3. 最小连接调度
　　
　　最小连接调度（Least-Connection Scheduling）算法是把新的连接请求分配到当前连接数最小的服务器。最小连接调度是一种动态调度算法，它通过服务器当前所活跃的连接数来估计服务器的负载情况。调度器需要记录各个服务器已建立连接的数目，当一个请求被调度到某台服务器，其连接数加1；当连接中止或超时，其连接数减一。
　　
　　在系统实现时，我们也引入当服务器的权值为零时，表示该服务器不可用而不被调度，它的算法流程如下：
　　
　　最小连接调度算法流程
　　假设有一组服务器S = {S0, S1, ..., Sn-1}，W(Si)表示服务器Si的权值，
　　C(Si)表示服务器Si的当前连接数。
　　
　　for (m = 0; m  0) {
　　 for (i = m 1; i  C(Si) / W(Si) 可以进一步优化
　　为C(Sm)*W(Si) > C(Si)* W(Sm)。同时保证服务器的权值为零时，服务器不被调
　　度。所以，算法只要执行以下流程。
　　
　　for (m = 0; m  0) {
　　 for (i = m 1; i  C(Si)*W(Sm))
　　 m = i;
　　 }
　　 return Sm;


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/23081/showart_209217.html