作者:许广斌
实现过程之理论先导篇(3)
本篇是实现过程的第三个理论先导篇，作者将向我们讲述负载平衡策略，并对各种负载平衡策略作了比较。
近年来，Internet的发展步入黄金时期，网上信息交换的数量正在呈指数形式的增长。特别是，由于电子商务的蓬勃发展，人们已经预计在下一世纪，网上消费将成为日常生活的重要形式。
随着网络硬件设备的飞速进步，网络带宽的瓶颈效应日趋减弱，WEB服务器的性能问题逐渐显现出来。单一的服务器系统处理客户请求的能力有限，如何处理快速增长的客户请求，是当前研究人员关注的重要问题。从目前的研究方向看，服务器方向的研究可以归结为两个方面：
1.从实现机制上入手。主要研究Caching技术、预取技术等。这方面的研究主要从客户访问行为分析入手，研究可以缩小响应时间的方法，这些技术可以在现有服务器设备的基础上尽可能地提高系统的性能，但性能提高的程度有限。
2.从体系结构入手。将过去单一的服务器结构扩充为集群式服务器结构。这种改造可能需要增加较大的开销，但可以显著提高服务器的总体性能。
就某一商业Web站点而言，人们通常会认为，日访问人数越多，说明销售的潜力越大，潜在的购买者越多。但统计结果向我们显示的却是另一种结果。随着日访问人数的增加，销售量上升到一定程度后，反而下降。图1给出的是某汽车销售网站网上销售的模拟计算结果。注意，当网站日查询业务量为正常的120%或更高时，访问的服务时间明显增长，使得日收益反而比正常情况下降很多。
究其原因，我们不难发现，服务器的性能是导致这种现象的最根本的原因。当服务器负载接近边界时，负载的一个小小的增长都有可能使服务器陷入象死锁那样的一种境地。由此可以得出，如何优化Web服务器性能将是今后一段时间研究的一个热点。许多服务器制造商都在努力推出性能更加优良的服务器，但是单一服务器结构有一个致命的缺陷，那就是由于服务器的处理能力有限，有可能会出现死锁的情况。死锁的产生是由于新请求的到达率大于系统服务率，系统没有能力在短期内处理所有的请求，导致等待队列溢出，系统稳定状态转为不稳定状态，最后崩溃。集群服务器具有良好的可扩展性，可以随着负载的增大动态地向集群中增加服务器，从而就避免了由于处理能力不足而导致的系统崩溃。
1. 粗粒度分发策略
在集群系统中，粒度指的是负载调度和迁移的单位。集群系统中的粗粒度指的是调度和迁移的单位是服务，而细粒度指的是进程。目前，关于集群式服务器的研究主要集中在体系结构和负载平衡策略的研究上，其中负载平衡策略的研究又是体系结构研究的基础。早期的集群式服务器系统常采用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算法是最可靠、有效的。但是，这种算法忽略了客户－服务器距离的重要性。
. 细粒度分发策略
为实现客户请求的集中调度和完全路由控制，采用细粒度负载分配策略的服务器结构中必须包含一个路由器节点──平衡器(可能是一个硬件路由器或集群服务器中配置专用软件的节点)接收发向Web站点的所有请求，根据某种负载平衡算法将请求转发到不同的服务器节点上。
与基于DNS的体系结构不同的是，平衡器采用单一的、虚拟IP地址IP-SVA(single virtual IP adress)，这个IP地址是众所周知的一个IP地址，而节点服务器的实际地址对用户是透明的。由于此机制是在URL层进行请求的处理，Web页中包含的多个目标，可以由集群中的不同节点提供，这样提供了比RR－DNS更细粒度的控制策略。
根据路由机制的不同，细粒度负载分配策略又可分为
