近年来，Internet的发展步入黄金时期，网上信息交换的数量正在呈指数形式的增长。特别是，由于电子商务的蓬勃发展，人们已经预计在下一世纪，网上消费将成为日常生活的重要形式。

随着网络硬件设备的飞速进步，网络带宽的瓶颈效应日趋减弱，WEB服务器的性能问题逐渐显现出来。单一的服务器系统处理客户请求的能力有限，如何处理快速增长的客户请求，是当前研究人员关注的重要问题。从目前的研究方向看，服务器方向的研究可以归结为两个方面：

1. 从实现机制上入手。主要研究Caching技术、预取技术等。这方面的研究主要从客户访问行为分析入手，研究可以缩小响应时间的方法，这些技术可以在现有服务器设备的基础上尽可能地提高系统的性能，但性能提高的程度有限。
2. 从体系结构入手。将过去单一的服务器结构扩充为集群式服务器结构。这种改造可能需要增加较大的开销，但可以显著提高服务器的总体性能。

体系结构研究	软件技术研究
单机服务器	协议分析
	缓存机制Caching
	预取技术Pre-fetching
	请求调度
集群服务器	节点分发

就某一商业Web站点而言，人们通常会认为，日访问人数越多，说明销售的潜力越大，潜在的购买者越多。但统计结果向我们显示的却是另一种结果。随着日访问人数的增加，销售量上升到一定程度后，反而下降。图1给出的是某汽车销售网站网上销售的模拟计算结果。注意，当网站日查询业务量为正常的120%或更高时，访问的服务时间明显增长，使得日收益反而比正常情况下降很多。

图1：某汽车销售商网上销售模拟计算结果

	正常	正常+10%	正常＋20％	正常＋30％
日查询业务量	92448	101693	110938	120182
服务器响应时间	2.86	3.80	5.67	11.28
损失交易比例	0	0	60%	95%
每日交易量	4622	5085	2219	300
日收入	83203	91524	39938	5408
可能的日收益	83203	91524	99844	108164
损失的日收益			59906	102756

究其原因，我们不难发现，服务器的性能是导致这种现象的最根本的原因。当服务器负载接近边界时，负载的一个小小的增长都有可能使服务器陷入象死锁那样的一种境地。由此可以得出，如何优化Web服务器性能将是今后一段时间研究的一个热点。许多服务器制造商都在努力推出性能更加优良的服务器，但是单一服务器结构有一个致命的缺陷，那就是由于服务器的处理能力有限，有可能会出现死锁的情况。死锁的产生是由于新请求的到达率大于系统服务率，系统没有能力在短期内处理所有的请求，导致等待队列溢出，系统 稳定状态转为不稳定状态，最后崩溃。集群服务器具有良好的可扩展性，可以随着负载的增大动态地向集群中增加服务器，从而就避免了由于处理能力不足而导致的系统崩溃。

粗粒度分发策略

在集群系统中，粒度指的是负载调度和迁移的单位。集群系统中的粗粒度指的是调度和迁移的单位是服务，而细粒度指的是进程。目前，关于集群式服务器的研究主要集中在体系结构和负载平衡策略的研究上，其中负载平衡策略的研究又是体系结构研究的基础。早期的集群式服务器系统常采用Round-Robin DNS算法实现客户请求的分发。实际上是一种粗粒度的负载分配策略。

1.1 工作原理

正常情况下，域名服务器将主机名映射为一个IP地址，为了改善负载平衡状况，早期的集群服务器系统采用RR－DNS(Round-Robin DNS)调度算法将一个域名映射为一组IP地址，允许客户端链接到服务器集群中的某一台服务器上，由此提供了服务器站点的伸缩性。一些可伸缩Web服务器(例如Eddie和NCSA的Scalable Web Server)采用RR-DNS实现负载平衡，一些高吞吐率的站点(Yahoo)也继续采用这种简单应用。图2为这类服务器结构的工作原理图。

图 2 基于DNS机制的集群服务器结构

RR－DNS在解析域名时，附加一个生存期(TTL：Time-To-Live)，这样一个请求生成后TTL时间内没有获得应答信息，可以向RR－DNS获取不同的IP地址。

1.2 工作流程

1. 客户发出地址请求(URL) 
   地址请求报文到达DNS
2. DNS选择服务器IP地址和TTL
3. 地址映象(URL->ADDRESS 1) 
   地址映象(URL->ADDRESS 1)
4. 客户向服务器1发出文档请求
5. 服务器1响应客户的文档请求

1.3 存在缺陷

在一个TTL时期内，多个域名请求将被映射到相同的IP地址，这样大量的客户端请求可能出现在同一服务器上，导致明显的负载失衡。如果TTL很小，又会明显增加域名解析的网络负载。

另一个相关问题是由于客户端缓存域名－IP地址解析结果，客户端可以在未来的任意时刻发送请求，导致服务器的负载无法得到控制，出现服务器负载失衡。

1.4 相关算法研究

为解决请求的负载分布均衡问题，研究者对RR－DNS算法进行了多种改进，这些改进依据TTL的设定形式可分为TTL恒定算法和自适应TTL算法。

TTL恒定算法 TTL恒定算法根据用户使用系统状态信息的情况又可分为系统无状态算法、基于服务器状态算法、基于客户状态算法和基于服务器/客户状态算法。

1. SSL：系统无状态算法system-stateless algorithm

   系统无状态算法指DNS服务器按固定时间间隔将客户请求分发到不同服务器上。例如时刻的客户接受服务器k1的服务，时刻的客户接受服务器k2的服务，式中的 为TTL值。客户获取服务器地址后，将地址缓存在客户端，然后根据需要，向服务器发请求。

   使用系统无状态算法，DNS只能控制部分请求的流向，由于不考虑服务器的容量和可用性，以及客户请求到达的不确定性，导致服务器超载或将请求发送到不可用服务器上，此算法性能很差，没有实用价值。

2. SSB：基于服务器状态算法Server-state-based algorithm

   获取服务器状态的目的是为了选择可用性更高的服务器处理客户请求，防止服务器阻塞或服务失败。服务器状态算法需要使用简单的服务器侦听机制(例如心跳协议等)对服务器状态进行定时跟踪。当客户请求到达时，将负载最轻的服务器地址映射给客户端。SUN-SCALR在实现上就是采用这种机制。

3. CSB：基于客户状态算法Client-state-based algorithm

   来自客户端的信息可归结为客户访问的平均负载状况和客户分布情况。如果不考虑客户的优先级高低，CSB算法使用HLW(hidden load weight)参量描述新客户的到达率(TTL周期内，访问服务器的新客户数量)，根据新客户到达率，进行服务器分配，这类算法的典型代表是MRRP(multitier round-robin policy)。

   另外，Cisco的Distributed Director在实现上也采用CSB策略，Distributed Director在服务器集群中充当主域名服务器，根据客户－服务器的拓扑距离和新客户到达率，选择最适合的服务器分发给客户。

4. SCSB：基于服务器/客户状态的算法server and client state based algorithm

   在DNS算法中，同时使用服务器状态和客户状态信息时，获得的性能往往是最高的。例如Distributed Director的DNS算法以服务器可用信息和客户的距离信息为指标分配处理服务器。当节点服务器超载，服务器发送异步警报反馈信息给DNS控制器，控制器将此服务器从可用服务器表中剔除，根据客户状态信息选择最有利的服务器处理客户请求。使用此算法需要对服务器状态进行动态分析和预测。

5. WRR：带有权重的RR算法 Weight Round-Robin algorithm

   根据各台实际服务器的处理能力给它们分配不同的权重，使具有相同权重的服务器获得链接的概率相同，高权重的服务器获得链接的概率比低权重服务器获得链接的概率大。

自适应TTL算法[20]
为平衡多服务器节点的负载，特别是异构服务器的负载，人们提出了自适应的TTL算法。这类算法使用基于服务器/客户状态DNS策略选择节点服务器，并动态调整TTL值。在异构服务器集群中，根据各服务器容量不同，设置的TTL值也不完全相同，由此控制因负载不对称造成的超载问题。

自适应TTL算法使用两步表决机制：首先DNS选择服务器的方法和基于客户状态算法相似；第二步，DNS根据负载分布情况、服务器处理能力和服务器的繁忙程度选择合适的TTL值，服务器越忙，设定的TTL值越小。

另外，自适应TTL算法的可扩展性很强，算法实现中的数据都可以动态获得。使用自适应TTL算法可以使服务器集群比较容易地从局域网拓展到广域网。

1.5 DNS算法比较

由于客户端和中间域名服务器缓存URL－IP地址映射，使用服务器状态信息的DNS算法不能保证负载平衡[15]，每个地址缓存都有可能引发大量的客户请求阻塞集群中的某个服务器节点。因此，合理地预测客户请求的到达率对于选择服务器更加有效。

使用客户到达率信息和服务器监听的调度算法可以获得更高可用性的服务器。但是这种算法明显不适于异构型集群服务器。

为平衡分布系统的请求负载，自适应TTL算法是最可靠、有效的。但是，这种算法忽略了客户－服务器距离的重要性。

算法名称		优点	缺点
固定 TTL 算法	系统无状态算法	简单	不实用
	基于服务器状态算法	提高服务器可用性	不能保证负载均衡
	基于客户状态算法
	基于服务器/客户状态算法	可以获得更高可用性的服务器	不适于异构型集群服务器
自适应TTL算法		DNS算法中可靠性最好、效率最高的算法	忽略了客户－服务器距离的重要性

回页首

细粒度分发策略

为实现客户请求的集中调度和完全路由控制，采用细粒度负载分配策略的服务器结构中必须包含一个路由器节点──平衡器(可能是一个硬件路由器或集群服务器中配置专用软件的节点)接收发向Web站点的所有请求，根据某种负载平衡算法将请求转发到不同的服务器节点上。

与基于DNS的体系结构不同的是，平衡器采用单一的、虚拟IP地址IP-SVA(single virtual IP adress)，这个IP地址是众所周知的一个IP地址，而节点服务器的实际地址对用户是透明的。由于此机制是在URL层进行请求的处理，Web页中包含的多个目标，可以由集群中的不同节点提供，这样提供了比RR－DNS更细粒度的控制策略。

根据路由机制的不同，细粒度负载分配策略又可分为报文重写(单向重写或双向重写)、报文转发和HTTP重定向。

2.1 PDR：报文双向重写策略

PDR采用集中调度方式完成客户请求的路由控制，服务器系统的平衡器负责客户请求的接收、分发和结果的返回工作。与RR－DNS策略不同，平衡器在IP层进行地址重写，使用动态地址映射表，实现客户请求的重定向。采用单一的虚拟IP地址(IP-SVA)，用户可见的只是平衡器，节点服务器是透明的。在选择节点服务器时采用的调度策略主要有：Round Robin（轮转）、Weighted Round Robin（加权轮转）、Least Connection（最少连接）和Weighted Least Connection（加权最少连接）。平衡器将客户和节点服务器的映射添加到映射表中，这样就保证了同一客户的所有请求都发送到同一台节点服务器上，从而保证了访问的持续性。采用PDR策略的典型代表是Cisco的Local Director，从路由机制上看，Local Director当前采用最少连接数策略。图1-3给出了Local Director处理客户请求的原理图。

图 3 LocalDirector原理图

工作流程

1. 客户向服务器发出请求
2. 平衡器选择客户请求的处理节点
3. 将客户请求的目的IP地址(IP-SVA)改写为节点服务器地址(address1)
4. 将客户请求发送给处理节点
5. 处理节点将结果返回给平衡器
6. 平衡器将应答报文的源IP地址(address1)改写为IP-SVA
7. 客户接收应答报文

性能分析
与粗粒度负载平衡策略不同，PDR在IP级进行负载平衡分配，这样就省去了从应用层到IP层的通讯开销，因此有效缩短了服务器处理时间。较DNS机制，性能提高很大。但是这种策略也存在如下问题：

1. 平衡器容量有限，导致系统可伸缩性不高。另外，平衡器可能成为整个服务器集群的瓶颈。
2. 此机制只适于在局域网范围内实现。

2.2 PSR：报文单向重写策略

在某些体系结构中，平衡器对接收的客户请求进行二次路由，将客户报文的目的IP地址改写为实际处理节点的IP地址，例如基本的TCP路由机制[15]。

在TCP路由机制中，服务器集群由一组节点服务器和一个TCP路由器组成，TCP路由器充当IP地址平衡器。当客户请求到达TCP路由器时，由于IP-SVA是唯一公开的IP地址，平衡器将请求报文中的目标IP地址重写为节点服务器的私有IP地址。由于一个客户请求可能是由多个报文构成，TCP路由器在地址表中记录客户(具有相同的源IP地址)与执行服务器的地址映射，保证来自同一客户的所有报文都能到达同一台节点服务器。服务器在发送应答报文给客户时，将平衡器的IP-SVA写入源IP地址，这样客户并不知道请求是由隐藏的执行服务器完成。图4给出了服务器使用报文单向重写策略时，客户请求的执行过程。

工作流程：

1. 客户向服务器发出请求
2. 平衡器进行地址解析，选择执行服务器
3. 平衡器用执行服务器的私有地址(address1)替换客户请求报文的目的IP地址
4. 客户请求报文二次路由，到达执行服务器
5. 执行服务器处理客户请求，并将IP-SVA写入应答报文的源IP地址中
6. 客户接收应答报文

图 4：报文单向重写示意图

性能分析
使用报文单向重写机制可以提高系统可用性程度，当平衡器节点出现故障时，路由表可以由原平衡器迁移到新的服务器上，服务器的结构也可以从局域网拓展到广域网。但是这种机制导致服务器结构透明性较差，而且执行服务器和平衡器在判断客户请求是否结束上存在困难。

2.3 PF：报文转发

由于报文重写增加了平衡器处理请求的复杂度，导致平衡器负载加重，研究者提出了报文转发策略(PF)。采用PF策略，平衡器和执行服务器共用一个IP-SVA地址，客户请求报文到达平衡器后，平衡器根据调度选择执行服务器，利用执行服务器的物理地址(MAC)将报文转发给执行节点。转发过程中不需要进行地址解析，所以不必改动客户请求报文。采用PF策略的典型代表是IBM的Network Dispatcher。

局域网内部的Network Dispatcher集群处理客户请求的原理与图5相似，其工作流程如下：

1. 客户向服务器发出请求报文；
2. 平衡器根据负载平衡策略选择执行服务器；
3. 平衡器利用执行服务器的私有MAC地址转发客户报文；
4. 客户报文路由；
5. 执行服务器处理客户请求；
6. 执行服务器将应答报文发送给客户。

为了将服务器集群从局域网拓展到广域网，Network Dispatcher采用两级平衡器机制，图5显示了广域网服务器集群的原理图。一级平衡器到二级服务器之间采用类似报文单向重写策略，平衡器将客户请求报文的目的地址(IP-SVA)改写为二级平衡器的IP地址，选择二级平衡器的原则是根据客户-服务器间的距离，将客户请求分发到最近的服务器子群上。二级平衡器将客户请求报文的目的地址改回IP-SVA，然后将报文转发到执行服务器上，服务器子群要求必须在同一局域网中。

图 5：广域网实现的报文转发

在广域网环境下，实现客户请求报文处理的流程是：

1. 客户向服务器发送请求报文；
2. 一级平衡器根据客户－服务器距离选择二级平衡器；
3. 一级平衡器将客户报文的目的地址改写为二级平衡器的IP地址；
4. 客户请求报文由一级平衡器向二级平衡器路由；
5. 二级平衡器根据负载平衡策略选择执行服务器；
6. 二级平衡器将客户请求报文的目的地址改写为IP-SVA；
7. 客户请求报文转发；
8. 执行服务器将应答报文直接传送给客户。

随着负载数量的增长，相应的处理变得越来越复杂(每个服务器节点每秒处理的请求数量有限)，目前路由器只负责接收报文，但链接的复杂性、每个请求的返回数据量都限制了路由器的可伸缩性。

2.4 HTTP重定向策略

集中式平衡器接收所有客户请求，使用HTTP重定向机制将客户请求分发到不同的执行服务器上。平衡器根据特殊的响应状态码，指明客户请求文件在服务器上的位置，因此重定向机制是高度透明的。与其他分发机制不同的是，HTTP重定向机制不需要对通讯报文的IP地址进行修改，HTTP重定向机制可以由以下两种技术实现。

2.4.1 基于服务器状态分发
在分布式服务器集群体系结构中，修正现有的HTTP协议，增加新方法实现对Web服务器的管理，改变平衡器与执行服务器间的信息交换。由于平衡器需要考虑服务器的负载情况，每个执行服务器必须周期性地报告处理进程数量和客户请求到达率。平衡器选择负载最轻的执行服务器处理新的客户请求。

2.4.2 基于位置的分发
Cisco的Distributed Director提供了两种分发模式，第一种是基于DNS的SCSB策略，第二种为HTTP重定向策略。Distributed Director评估客户－服务器距离和节点可用性，将客户请求重定向到最合适的执行服务器。

回页首

细粒度分发策略的比较

基于平衡器的报文双向重写机制的问题是，平衡器必须对应答报文进行重写，而应答报文的数量明显超过请求报文的数量。

使用TCP路由器结构的报文单向重写机制，由于执行服务器处理众多的应答报文，减轻了平衡器的负载。广域网环境下的Network Dispatcher仅对请求报文进行两次重写，因而执行效率更高。

报文转发机制可以有效避免报文重写带来的开销，然而共享单IP地址导致静态调度策略失效(服务器状态不决定路由)。基于路由的平衡器需要对每个报文进行二次路由，基于广播的平衡器需要把报文广播到每个执行服务器，这样明显加重了服务器负载。

局域网环境下的Network Dispatcher结构避免了共享IP地址、TCP路由和双向重写的开销等问题，但是它只能在同一网段内实现，可伸缩性很差。HTTP重定向可以很好地应用于局域网和广域网中，但必须复制一定数量的TCP连接。

回页首

各种负载平衡策略的比较

基于DNS机构的实现机制可以明显减轻服务器的瓶颈效应，可伸缩能力得到加强，服务器环境从局域网拓展到广域网。但是，使用这种结构，服务器的数量不能超过32台(受UDP报文长度的限制)。基于DNS结构的服务器通过地址映射决定客户请求的目的地址，然而，这种粗粒度负载平衡机制要求TTL必须大于0，由于客户端对服务器地址进行缓存，导致服务器负载平衡不能保证，人们提出了基于状态信息算法和自适应TTL算法对DNS策略的性能进行改进。总的来说，单纯基于DNS策略的服务器适合于小规模的同构型服务器集群，但不适于异构性服务器结构。

基于平衡器结构的服务器由于受到单仲裁入口的限制，客户请求迅速增长可能导致平衡器成为系统瓶颈；由于平衡器对客户请求报文重写或转发，增加了客户等待延迟，降低了服务器性能；另外使用集中调度策略，若平衡器当机，则整个系统都会崩溃。从另一方面讲，平衡器实现的细粒度负载平衡策略，共享服务器IP地址又克服客户端网络层地址缓存问题。基于服务器拓扑结构实现的报文重写和转发策略是目前局域网或高速广域网中集群服务器实现的主要策略。

改进执行服务器处理过程将原有的请求集中控制改为部分分布控制，是服务器结构研究的一种进步，与平衡器结构服务器相同，这种技术也是一种细粒度负载平衡策略，但它带来的客户等待延迟要比其他策略增加很多。

从目前集群式服务器结构研究的现状分析可以看出，今后服务器集群的发展趋势将是面向广域网的分布控制的服务器集群研究。

参考资料

• Andrew S. Tanenbaum ,《计算机网络》, 清华大学出版社，1998
• 刘振英、张毅等，多机系统的动态负载平衡，《计算机科学》, Vol. 26 , No 1:38-40, 1999
• Eager D L,et al. Adaptive load sharing in homogeneous distributed systems. IEEE Tran. On Software Engineering, SE-12(5)，1986
• Zhou S. A trace-driven simulation stydy of dynamic load balancing. IEEE Tran . On Software Engineering. SE-14(9):1327~1341，1988
• 魏永明、杨飞月、吴漠霖，《Linux实用教程》，电子工业出版社，1999
• 胡子昂、王立，算法、网络拓扑及调度频率与动态负载平衡的关系，《计算机工程与科学》，Vol.22.No.1, 2000
• Aaron Mackee，A TurboLinux Technical Case Study,www.turbolinux.com
• www.linuxvirtualserver.com
• aniel A.Menasce, "CS672-Computer System Performance Evaluation" http://www.cs.gmu. edu/faculty/menasce.html
• Louis P.Slothouber, "A model of Web Server Performance", http://louvx.biap.com/webperfor mance/modelpaperhead.html
• V.Cardellini, M.Colajanni et al, "DNS Dispatching Algorithms with State Estimators for Scalable Web Server Clusters", World Wide Web J.Baltzer Science Bussum, Netherlands Vol 2, No.2 July 1999
• M.Colajanni et al, "Analysis of Task Assignment Policies in Scalable Web Server Systems", IEEE Trans Parallel and Distributed Systems, Vol.9 No.6, June 1998, pp585-600
• D.M.Dias et al, "A Scalable and Highly Available Web Server", Proc 41st IEEE Computer Soc. Int'l Conf, IEEE Computer Soc. Press, Los Alamitos, Calif, Feb,1996, pp85-92
• "Network Dispatcher : a connection router for scalable Internet Services",In Proceedings of the 7th Interional WWW conference , Brisbance Australia , April 1998 http://decweb .ethz.ch/www/1899/com1899.htm
• D.L.Eager E,D Lazowska and J,Zahorjan , "Adaptive load sharing in homogeneous distributed systems", IEEE Transactions on Software Engineering ,12(5):662-675, May 1986
• IBM "IBM parallel system support programs for AIX : group services programming guide and reference" 1996 SC28-1675-00
• O.Kremien and J.Kramer,"Methodical analysis of adaptive load sharing algorithms", IEEE Transactions on Parallel and Distributed Processing 3(6), November 1992
• Daniel Ridge,"Beowulf Harnessing the Power of Parallelism in a Pile of PCs"