摘 要： 以电子商务网站为对象，提出一种改善其性能的调度算法和系统的体系机构。通过大量的实验数据将算法与FIFO进行性能比较。
关键词： 电子商务 动态加权公平服务 性能改善
目前改善Web Server性能的主要策略有：采用Web Server的复制策略[1]来达到负载均衡的效果；利用缓存(Cache)技术[2]来减少Web的延迟；通过短连接优先调度[3]的策略来减少Web Server的响应时间；从客户端应用程序的角度来提高应用程序的自适应性[4]并基于预测做出相应的决策。
典型的购物网站中，客户的请求是基于会话(Session)[5]的。Session里包含了来自同一客户端连续的请求序列。客户能感受到的服务质量就是响应时间。对于这类网站，Session里有浏览、查询、订单等不同的处理，这些不同的客户行为对Web Server的需求也不相同。其中查询处理会涉及访问数据库，订单处理要应用程序进行数据库操作，浏览则不涉及复杂的操作。同时，客户对不同行为的响应时间的要求也不同，例如浏览客户能忍受的延迟可能不超过1秒，而对于查询操作客户可忍受的延迟会较长些。于是把请求分成4种：浏览首页、购物付账、查询和浏览静态页面。对于每个到达的请求依据其种类进入相应的队列，再动态调整队列权值，其依据就是使得效益函数取得最大值。然后采用动态加权公平服务(Dynamic Weighted Fair Service，DWFS)算法，对不同类型的请求提供有区别但相对权值来说又是公平的服务。
1 相关工作
算法思想来源于一个理想的绝对公平的策略——处理机共享[6]。它先建立多个队列，在每次循环中只发送1位。这样，每个忙的源站都能够得到完全相同的处理机容量，是绝对化公平的。特别是，如果有N个队列，同时每个队列永远都有1个分组要发送，则每个队列就正好得到可用容量的1/N。这种处理称为处理机共享。下面定义一些术语。
R(t)：时间t内，在处理机共享规则中发生的循环次数。
N(t)：t时刻的非空队列数。
Pi：分组i的处理时间。
Zia：在队列a中分组i的到达时间。
Sia：队列a中分组i的开始被处理时R(t)的值。
Fia：在队列a中分组i的结束处理时R(t)的值。
可以将R(t)想象成一个虚拟时间，记录了在队列头部第1个分组所看到的服务速率。
下面的3个递归关系式归纳了处理机共享系统的基本思想：
2 Web Server性能改进算法的基本原理
本文提出的体系结构如图1所示。其思想是：将顾客的请求根据所需要的服务器类型分类；对同一类请求分配相同的权值；权值会随着当前的请求和Web服务器的处理情况调整；基于权值对请求进行公平服务。
2.1 算法基本思想
为了使处理机能支持服务质量，而有区别地分配容量，并且能够发送整个分组，而不是单个位，就需要设计一个具有区别服务的可实现的处理机共享系统。
(1)考虑公平加权。为了考虑不同队列的不同需求，应将处理机共享规则广义化，即允许分配任意的处理机容量。为每个队列指派1个权值Φα，它确定了在每次循环中从该队列可发送多少比特。假设只有3个队列且均为非空，权值分别为0.8、0.1和0.1。对于队列1中的请求i，Pi是全部处理机资源都在处理此请求时所需的时间，则请求i在这种情况下的实际处理时间就变为Pi/0.8=5Pi/4，比原来大1/4倍。因为非空队列权值之和未必等于1，所以公式(1)中的Pi不能简单地变为Pi/Φi，而应变换为(Pi/Φi)*C1，其中C1在给定的权值下为常数。因为队列具有权值，不能同等对待，所以虚拟时间R(t)也要变化，不再是1/N(t)。非空队列的权值之和越大，处理能力越分散，轮询一遍所需的时间就越长，虚拟时间的涨幅越小。即R(t)′与∑Φ非空队列成反比，记为R(t)′＝C2/∑Φ非空队列，其中C2在给定的权值下为常数。把以上2个结论分别代入公式(1)、(2)、(3)，就得到如下3个式子：
(2)考虑具体实现。由于要处理的不是单个位，而是整个请求，属0/1问题，因此需进一步完善。加权公平服务算法就是设计一个模拟逐位轮流的规则。实现此算法时要随时计算虚拟开始时间Si与虚拟结束时间Fi，就好像正在运行加权的处理机共享那样。规定：只要一个请求的处理过程结束，下一个将被处理的请求就具有最小Fi值。为此建立了请求到达处理模型，且可以发现，随着时间的推移，请求收到的平均响应时间收敛于在逐位发送规则下的结果。
2.2 动态调整权值
由于服务不同，赋予的初始权值也就不同。而且每个队列长度也在不断变化，因此要防止拥塞，就需要每隔一定时间调用权值调整函数，根据队列初始权值和当前队列长度计算新的权值。
2.3 权值调整算法和加权公平服务算法
每隔一段时间调用一次权值调整方法：
每次请求处理结束，调用加权公平服务方法，返回下一个应处理的请求：
3 Web Server性能改进算法具体实现
3.1 系统模拟环境
系统的程序实现框图如图2所示。在真实的Web服务器前端实现一个代理(Proxy)，在Proxy中实现了FIFO和DWFS算法。为了产生较多的HTTP请求，用程序模拟了HTTP客户端的实现。该客户端能按照一定的时间间隔和规律来生成请求。
3.2 实验程序说明
使用Java程序模拟Proxy的实现。其实现主要由以下类组成。
(1)Http客户端（HttpClient）：模拟客户机发送Http请求。
(2)Http服务端（HttpServer）：模拟服务器，将Http请求进行排队处理。
(3)Http请求接收（HttpRequestRsv）：接收Http请求，根据访问页面分类进入队列。
(4)Http请求队列(HttpRequestQueue)：队列数据结构。
(5)Http请求队列处理（HttpRequestQueueHandler）：采取FIFO或DWFS进行调度。
(6)Http请求处理（HttpRequestHandler）：调度后，发送真实Http请求，并进行处理。
(7)数据日志（Datalog）：记录实验数据写日志文件。
3.3 实验初始参数
服务器同时处理10个请求，选用了几个有代表性的页面，各页面参数如表1所示。
4 实验结果数据分析
数据采集的参数包括：当前请求响应时间、各队列当前平均响应时间、所有请求的平均响应时间和各队列当前长度。
(1)分别间隔300ms和200ms发送请求分析响应时间。在每隔300ms发送请求时，2种算法下的系统性能几乎相同。而且，随着发送的请求个数越来越多，响应时间并未增大。因为每隔300ms的时间发送一个请求的速度对于Web服务器来说远没有达到饱和，因此不论采用什么算法，都不会造成系统的拥塞，系统性能相对稳定，2种算法没有明显区别。每隔200ms发送请求时，在前150个请求到来之前2种算法的系统性能几乎相同。然而随着请求的增多，应用DWFS算法的请求响应时间只是FIFO的一半。这说明在系统负载接近饱和的情况下，DWFS算法会使系统性能明显提高。
(2)分析间隔200ms发送请求时的队列平均响应时间和队列长度。在发送130个请求后，FIFO的各个队列平均响应时间和长度均大于DWFS各队列的响应时间。此外，应用FIFO的各队列极不稳定，不论“长”请求队列还是“短”请求队列都可能得不到响应，队列会出现拥塞。而DWFS的各个队列平均响应时间和队列长度相对稳定，但对于需要较长处理时间的搜索页面队列通常的响应时间也较长，会有较多的请求排队。
5 结论及展望
该体系结构中仍然存在一些不足：请求的产生是均匀、依次的，而实际客户访问各个页面都是随机的；仅在特定时刻根据队列的长度调整权值。针对以上不足可作进一步的改善：在请求的产生上，引入概率转移矩阵模型用于反映客户在不同队列间的转移关系，以更客观地模拟实际请求；根据客户的优先级调整权值。
参考文献
1 Qiu L，Padmanabhan V，Voelker G.On the Placement of Web Server Replicas.In：Proceedings of IEEE Infocom，2001
2 Chandranmenon G，Varghese G.Reducing Web Latency Using Reference Point Caching.In：Proceedings of the IEEE Infocom，2001
3 Crovella M，Frangioso R，Harchol-Balte M.Connection Scheduling in Web Servers.In：USENIX Symposium on Internet Technologies and Systems(USITS′99)，1999
4 Stemm M，Seshan S，Katz R H.A Network Measurement Architecture for Adaptive Applications.In：Proceedings of IEEE Infocom，2000
5 Chen H，Mohapatra P.Session-Based Overload Control for QoS-Aware Web Servers.In：Proceedings of IEEE Infocom，2002
6 Stallings W著，齐望东译.高速网络：TCP/IP和ATM的设计原理.北京：电子工业出版社，1999