调度linuxweb服务器

Vol.
14,No.
122003JournalofSoftware软件学报1000-9825/2003/14(12)2068基于内容的分布式Web服务器调度算法杜增凯+,郑名扬,鞠九滨(吉林大学计算机科学与技术学院,吉林长春130012)ADistributedAlgorithmforContent-AwareWebServerClustersDUZeng-Kai+,ZHENGMing-Yang,JUJiu-Bin(CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012,China)+Correspondingauthor:Phn:86-431-5169350,E-mail:zkdu@sina.
com.
cnhttp://www.
jlu.
edu.
cnReceived2002-08-20;Accepted2003-03-04DuZK,ZhengMY,JuJB.
Adistributedalgorithmforcontent-awareWebserverclusters.
JournalofSoftware,2003,14(12):2068~2073.
http://www.
jos.
org.
cn/1000-9825/14/2068.
htmAbstract:Whilecontent-awaredistributionpoliciesaregettingmorepopularincluster-basedwebsystems,theymakethedispatchingnodeabottleneck.
Toaddressthescalabilityandfault-toleranceproblem,issuesaboutdesigningdistributeddispatchingpoliciesarediscussed.
Forthepoliciesaimingatimprovingthecachehitrate,adistributeddispatchingpolicynamedDWARD(distributedworkload-awarerequestdistribution)thattakesintoaccountboththeloadbalanceandthelocalityenhancementispresented.
Finally,atestbedisimplementedonthebasisofaLinuxkerneltobenchmarkvariousdispatchingalgorithms.
TheperformanceresultsshowthatDWARDcanachieveafavorablethroughputcomparedwiththestate-of-the-artdispatchingpolicies.
Keywords:distributedWebserver(DWS);content-based;scalability;faulttolerance摘要:在分布式Web服务系统的研究中,基于内容的调度策略日益受到关注.
但是,基于内容的请求调度带来的额外开销使得调度节点成为系统的瓶颈,限制了系统规模.
为了实现系统的容错和扩展,集中讨论了分布式调度策略的设计问题,并针对难于分布的面向缓存调度策略设计了相应的分布式调度算法DWARD(distributedworkload-awarerequestdistribution).
基于LINUXIP协议栈的系统测试表明,DWARD算法可以在适当调整的情况下获得良好的性能.
关键词:分布式Web服务器;基于内容;可扩展性;容错中图法分类号:TP393文献标识码:A随着Internet的飞速发展,人们对全球网络数据的访问需求也急剧增加.
越来越多的站点和Internet服务提供商采用机群体系结构(分布式Web服务器(distributedWebserver),简称DWS)提供Web服务.
传统DWS系统的研究大都根据数据包的IP地址和TCP端口号实现请求的调度.
基于内容的DWS请求调度将客户请求的类SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.
60073040(国家自然科学基金)第一作者简介:杜增凯(1974-),男,河北沧州人,博士生,主要研究领域为分布式系统,分布式Web服务器.
杜增凯等:基于内容的分布式Web服务器调度算法2069型甚至具体内容都纳入了调度的范畴.
丰富的调度信息增强了DWS的灵活性和智能性,扩大了DWS系统的应用范围.
目前,基于内容的DWS研究大都使用集中式的调度算法[1~5].
这些算法只能在一个集中的调度节点上运行,不但为系统增加了单一失效节点,而且在很大程度上限制了系统的扩展.
研究表明[6],基于内容的DWS调度所能支持的系统规模与传统的Web调度相比下降了近一个数量级.
本文试图通过设计分布式的调度策略从根本上解决DWS系统的扩展问题.
首先,我们将通过分析调度算法对调度信息的需求讨论现存调度策略的分布化问题.
对于难于分布的面向缓存调度策略,我们设计了相应的分布式调度算法DWARD(distributedworkload-awarerequestdistribution).
此算法不但可以让所有的服务节点参与请求的调度,而且可以同时兼顾系统的负载平衡和缓存命中率.
另外,DWARD算法的运行无须节点间频繁的信息交互.
基于LINUXIP协议栈的系统测试表明,DWARD算法可以在适当调整的情况下获得良好的性能.
1基于内容的分布式调度策略在过去的几年中,研究人员根据各自的需要设计了大量的调度算法,典型调度算法的分类比较可参见文献[7,8].
这些算法虽然可以使用各种调度信息实现请求的调度,却只能运行在集中的调度节点上.
我们的目标是要设计分布式的调度策略.
在采用分布式调度策略的系统中,每个服务节点负责调度自己收到的客户请求.
这将使系统中不再存在性能瓶颈和单一失效节点.
以下我们将通过分析调度算法对调度信息的需求讨论现存调度算法的分布化问题.
通过分析现存的调度算法,我们把调度信息分为两种:客户请求信息和服务器状态信息.
客户请求信息是指可以从客户请求中获取的信息,包括请求的URL,Cookie,SSLSessionID等.
服务器状态信息有:(1)静态调度信息:包括系统中各节点的硬件配置和软件配置.
硬件配置信息可能包括节点功能强弱、专用服务器类别等.
软件配置信息则包括负载集合在各节点的分布以及特定调度算法所需的统计数据.
(2)动态调度信息:包括各服务节点的负载情况(CPU利用率、I/O利用率、未处理的连接数)以及它们对文件的缓存情况.
表1列出了典型的调度算法和调度信息之间的关系.
Table1Stateinformationusedbypopulardispatchingpolicies表1典型调度算法使用的调度信息AlgorithmsClientinformationStaticserverinformationDynamicserverinformationHASHRequestedURLCAPRequestedURL[9]SITA-ERequestedURL[10]SizeoftargetfileLARDRequestedURL[11]Activeconnections,cachestateClientaffinityCookie,SSLSessionID[12,13].
ServicedifferentiationCookie[13],customHTTPheader[14]ContentplacementRequestedURL[15]WorkingsetofeachservernodeSpecializedserverRequestedURLTypeofspecializedserver由表1可以看出,在基于内容的请求调度中,来自客户请求的信息占有重要的地位.
CAP,HASH等调度算法单纯依靠来自客户请求的信息就可以实现完整的调度策略.
由于请求的初始接收节点可以方便地获取来自客户请求的信息,这一类算法很容易分布化.
显然,也有不少调度算法需要来自服务器的状态信息.
其中一些只需要来自服务器的静态调度信息.
利用这些信息,不但可以有效地使用某些专用服务器,而且可以在各服务节点之间实现站点内容的分布.
在调度算法SITA-E中,一种来自服务器的重要调度信息是URL与文件大小的对应关系.
由于这些服务器端的静态调度信息可以在系统配置过程中一次性获得,因此相关的调度算法也不难实现分布化.

在表1中,只有少数调度算法考虑来自服务器的动态信息.
但是由于精确的负载信息较难获取且难以利用,需要负载信息的调度策略往往使用当前连接数来衡量不同节点的负载[11].
为了提高静态网页的缓存命中率,面向缓存的调度策略需要获取全局的缓存信息.
集中式的调度策略往往假定它们运行在一个集中的调度节点上.

在这一特殊的调度节点上,可以很方便地获取全局的缓存信息,进而实现优化的调度决策.
然而在一个分布式的调度算法中,各服务节点地位平等,这使得它们无法自然地获得静态网页的全局缓存信息.
通过广播的方式固然2070JournalofSoftware软件学报2003,14(12)可以实现缓存信息的共享,但是让服务节点每响应一个用户的请求都进行一次广播无疑会带来很大的开销.

2面向缓存的分布式调度算法DWARD目前,面向缓存的调度算法主要有HASH,LARD和WARD.
HASH算法是一种静态的调度算法,它可以有效地提高缓存的命中率,但无法保证系统的负载平衡.
HASH算法的另外一个特点就是容易分布化,在第3节的系统测试中我们将使用分布式的HASH算法DHASH.
LARD[11]算法对系统工作集的划分是动态的,这使得它可以在提高缓存命中率的同时,兼顾服务节点间的负载平衡.
然而,在使用LARD算法的系统中,大部分的客户请求将被转接[11]到其他服务节点.
WARD算法[16]将访问最为频繁的一小部分文件定义为core,通过core集合的本地服务可以有效地减少昂贵的TCP转接操作.
然而,WARD仍然是一个集中式的调度算法.
对比LARD算法和WARD算法的调度流程可以发现,WARD算法隐含着一个重要的特征:WARD算法不考虑负载平衡问题.
在LARD算法中,负载平衡问题决定了工作集划分的动态变化,使LARD算法的每一次请求调度都需要全局缓存信息的支持,也正是这一点使得LARD算法难于分布化.
WARD算法对负载平衡问题的忽略让我们认识到,负载平衡功能可以从基于内容的调度算法中分离出来.
我们将充分利用这一特征,实现一个分布式的WARD算法,称为DWARD.
与WARD算法一样,DWARD把系统的工作集分为3部分:core,partition和disk.
Core集合和partition集合缓存在各节点的内存中,disk集合则包含无法缓存在内存中的部分.
Core集合相对较小,然而由于访问频繁,它会覆盖绝大部分的客户请求.
partition和disk集合只覆盖少数的客户访问,但它可能包含大部分目标文件.
与WARD算法类似,DWARD算法在本地处理客户对core集合的访问.
由于core集合覆盖了绝大部分的客户请求,core请求的本地处理避免了大量费时的TCP转接操作.
然而对于DWARD算法来说,core请求的本地处理还有一个更重要的特征:它避免了节点之间的交互,使得系统对core请求的处理可以分布化.
WARD算法对partition集合的处理在某种程度上继承了LARD算法的处理方式,其主要目的在于减少内存空间的消耗.
在DWARD算法中,我们采用HASH算法来处理对partition集合的访问.
这种处理方法不但可以节省内存空间的使用,而且使得系统对这部分文件的处理可以分布化.
另外,partition集合的特点(覆盖请求少、包含文件多)使得客户对这部分文件的访问相对均匀,使用HASH算法处理对这部分文件的访问不会导致负载的不均衡.
以下是DWARD算法对请求的调度流程:(1)请求属于core,本地服务;(2)请求属于partition,使用HASH算法选定目标节点;(3)请求属于disk,本地服务.
由于core集合的存在,DWARD算法可以在前端交换机的支持下实现负载平衡.
从这一点可以看出,DWARD并不是静态的调度算法,这与(分布式)HASH算法是有区别的.
与LARD/WARD算法相比,DWARD算法不再需要集中的调度节点.
集中调度节点的消除不但减少了系统的配置,而且为系统除掉了单一的失效节点,在一定程度上提高了系统的容错性能.
在LARD/WARD算法中,每个客户请求的调度都需要服务节点和调度节点间的一次交互.
而在DWARD算法中,所有的节点都可以根据自身的局部信息实现请求的调度,这从根本上消除了各服务节点间的频繁交互.
在DWARD算法中,core文件集合的选择直接影响着系统的性能.
core集合的增大会使大量的请求在本地得到服务,显著地降低系统的转接开销.
但是core集合的增大也会将部分partition集合的文件兑换到磁盘上,增加磁盘访问的开销.
对于指定的访问模式和系统指标,计算一个较优的core集合是可能的.
文献[16]提出了一种计算core集合大小的算法.
该算法考虑了网站的访问模式和大量的系统参数(如节点个数、节点内存、TCP转接开销、读盘开销等).
该算法的缺点在于,它必须事先从访问日志中获取各目标文件的访问频度以及许多精确的系统参数.
另外,它也没有考虑到磁盘系统和CPU的并行问题.
采用适当的工具对系统进行详细的建模分析是很有必要的.
在第3节,我们将采用实测的方法确定core集合的大小.
杜增凯等:基于内容的分布式Web服务器调度算法20713性能评价为了定量地测试第2节提到的调度算法,我们基于LinuxIP协议栈和TCP转接技术实现了一个测试平台.
配合不同的调度算法,测试平台可以配置成不同的调度框架.
对于集中式的调度算法,我们将测试平台配置为ScalaServer调度框架[6].
据我们所知,ScalaServer调度框架是运行集中式调度算法扩展性最好的调度框架.
对于分布式的调度算法,我们将使用一种分布式的调度框架.
于是所有的待测组合有:(1)S-LARD:ScalaServer调度框架上运行LARD算法;(2)S-WARD:ScalaServer调度框架上运行WARD算法;(3)D-DHASH:分布式调度框架上运行DHASH算法;(4)D-DWARD:分布式调度框架上运行DWARD算法.
我们的测试平台由客户节点、前端交换机和服务器群3部分组成,如图1所示.
服务器群由4个配置相同的节点组成,其配置为:Pentium133,32兆内存,IDE硬盘,100兆网卡.
对于ScalaServer调度框架,增加一个调度节点(PIII450,64兆内存,IDE硬盘,100网卡).
为了减少客户端的数量,使用较高配置的客户机:PIII933,128兆内存,IDE硬盘,100兆网卡.
各服务节点运行Linux操作系统(内核版本2.
4.
10),并通过一个可装载模块实现TCP转接功能.
在分布式调度框架中,调度策略的实现分布在各节点的TCP转接模块中,而与之对比的ScalaServer调度框架则在调度节点上集中实现.
服务节点使用Apache-1.
3.
20作为Web服务器.
客户端使用的软件源自S-Clients[17].
我们在S-Clients的基础上增加了日志回放和多机共同测试的功能.
我们选用S-Clients的原因在于,它可以按照指定的频率产生连接请求,这使得它生成的负载不受被测系统的限制.
在如图1所示的测试平台中,前端交换机具有两项功能:(1)负责客户机与服务节点之间以及各服务节点之间的通信;(2)在四层实现简单的负载平衡策略.
要实现这两项功能可以简单地使用商用的四层交换机.
由于没有四层交换设备,我们使用常用的交换设备实现必需的通信功能,而将交换设备的负载平衡功能在测试软件中实现.
由于在两种调度框架中前端交换机的功能是相同的,因此这种配置的变化不会影响结果的可比性.
ClusterserverClientsFig.
1Thetestbed图1测试平台Switch鉴于被测的4种算法都是面向缓存的,我们采用日志回放的方法来生成接近现实的Web负载.
在测试过程中,我们使用来自美国宇航局肯尼迪空间中心Web服务器的访问日志(简称NASA日志).
此日志时间跨度一个月,成功请求为1647832个,其文件-访问分布图为图2.
0.
00.
20.
40.
60.
81.
00.
00.
20.
40.
60.
81.
0Cumul.
reqs,filesize(norm.
)Filesbyrequestfrequency(normalized)RequestsFilesizeFig.
2TheNASAtrace图2NASA日志2072JournalofSoftware软件学报2003,14(12)图2中X轴代表目标文件数(按访问频率降序排列),Y轴表示这些文件所占的空间和覆盖的请求数.
为了便于显示,我们将空间占用量和覆盖请求数进行了标准化处理.
NASA日志包含4584个目标文件,共占空间200M,要覆盖97/98/99%的客户请求需要77.
6/90.
5/112.
6M内存空间.
首先,我们要为WARD和DWARD算法确定一个较优的core文件集合.
图3显示了WARD和DWARD算法在不同大小core集合下的性能参数(NASA日志).
图中X轴表示core集合相对于节点最大缓存空间的百分比,Y轴表示单位时间内系统完成的请求个数.
每个数据点的测试时间为10分钟.
从图3的性能曲线我们可以得出以下几点结论:(1)静态调度算法性能较差.
在性能曲线的左端点,WARD(DWARD)算法的core集合为空.
实际上,这是一种静态划分负载集的调度算法.
大量的转接操作以及对负载情况的忽略导致了静态调度算法的性能较差.