系统webhosting

Vol.
14,No.
12003JournalofSoftware软件学报1000-9825/2003/14(01)0117基于标记的缓存协作分布式Web服务器系统林曼筠1,2+,钱华林11(中国科学院计算机网络信息中心,北京100080)2(中国科学院计算技术研究所,北京100080)ADistributedWebServerSystemBasedonCooperativeCacheUsingTagLINMan-Yun1,2+,QIANHua-Lin11(ComputerNetworkInformationCenter,TheChineseAcademyofSciences,Beijing100080,China)2(InstituteofComputingTechnology,TheChineseAcademyofSciences,Beijing100080,China)+Correspondingauthor:Phn:86-10-68409547,E-mail:lmanyun@yahoo.
comhttp://www.
cstnet.
net.
cnReceived2001-08-13;Accepted2002-04-10LinMY,QianHL.
AdistributedWebserversystembasedoncooperativecacheusingtag.
JournalofSoftware,2003,14(1):117~123.
Abstract:Inthispaper,thestate-of-the-artDWSS(distributedWebserversystem)technologiesaredescribed,includingtheirmechanisms,advantagesanddisadvantages.
ThenanewalgorithmTB-CCRD(tagbasedcachecooperativeWebrequestsdistribution)forWebrequestsdistributionispresented.
Basedonit,ascalablehighperformanceDWSSisconstructed.
InthisnewarchitectureofDWSS,thefront-endserverorganizesthecachesofeachbackendWebserverintoavirtuallargecachetoimprovethehitrateofcacheandtheresponsetimeoftheDWSS.
TheoperationofTCPconnectionhandoffisdistributedamongthebackendserverstopreventthefront-endfrombecomingabottleneckofthesystem.
TagsareusedtoindicatewherethecontentofaURLiscached,soastoavoidextracommunicationswithinthesystem.
Throughthismechanism,theTB-CCRDDWSSachievesbothhigherperformanceandbetterscalability.
Keywords:DWSS(distributedWebserversystem);loadbalancing;cooperativeWebcaching;Webrequestsdistributionalgorithm;Webperformanceanalysis摘要:介绍了提高Web服务器性能的前沿技术——分布式Web服务器系统,讨论了现有各种方案的优缺点,在此基础上提出一种新的分布式Web服务器系统.
该系统使用基于标记的缓存协作用户请求分发方法(tagbasedcachecooperativeWebrequestsdistribution,简称TB-CCRD),通过前端机把系统中各个Web服务器的缓存组织成一个大的虚拟缓存系统,提高系统的整体缓存命中率,缩短了请求的响应时间;通过分布式处理TCP连接转交来消除前端机的性能瓶颈;利用标记通告URL在缓存中的位置,避免了额外的系统内部通信.
从而得到了一个可扩展的高性能分布式Web服务器系统.
SupportedbytheNationalHighTechnologyDevelopment863ProgramofChinaunderGrantNo.
863-306-ZD08-01-1(国家863高科技发展计划)第一作者简介:林曼筠(1968-),女,海南琼山人,博士,工程师,主要研究领域为计算机网络技术.

118JournalofSoftware软件学报2003,14(1)关键词:分布式Web服务器系统;负载平衡;协作式Web缓存;Web请求分发算法;Web性能分析中图法分类号:TP393文献标识码:A提高Web服务器性能的传统方法是升级单机系统.
这种做法简单、易行,但由于业务的发展和多种随机事件的发生,准确预测网站的访问量几乎是不可能的,因此,满足当前性能要求的服务器有可能很快就需要进一步的升级.
另外,被替换下来的机器很可能被闲置,从而造成资源和资金的浪费.

分布在LAN或者WAN上的多台Web服务器主机通过自组织方式或者由专门的设备负责组织调度的方式进行协同工作,组成一个Web站点,共同分担用户对该站点的Web请求负荷,我们称这样的系统为分布式Web服务器系统(distributedWebserversystem,简称DWSS).
DWSS是目前最前沿的服务器性能提升技术之一,其关键技术在于系统的组织结构、系统各部分之间的协作方法以及相应的任务分配——用户请求分发算法.
请求分发的目的在于通过负载平衡增加系统的吞吐量,缩短用户响应时间.
本文提出了一种新的算法,并据此构造了一个DWSS系统,在性能和可扩展性方面均有显著的提高.
第1节介绍几种典型的DWSS,并分析它们的优点和不足.
第2节介绍我们提出的基于TB-CCRD(tagbasedcachecooperativeWebrequestsdistribution)的DWSS.
第3节通过性能的数值比较和仿真实验研究新系统的扩展性和性能.
第4节是结论.
1典型的分布式Web服务器系统使用镜像技术的DWSS[1,2],由置于网络上的服务器的多个拷贝共同来提供服务,分担负荷,提高站点的处理能力.
该系统中的多台主机对用户是可见的,不了解各服务器的处理能力和拥挤程度的用户必须首先指定某一镜像站点为其提供服务,即便在某些服务器仍然空闲的情况下,用户的请求也可能会因发往某个已是满负荷运行的镜像点而得不到服务;另一方面,站点的运营者无法控制负载的分布.

以DNS为中心的DWSS[3,4],由服务器端DNS按照某种调度方法,将用户请求的URL中的主机名解释为DWSS中某个服务器的IP,使相应的客户请求发往该服务器.
常用的DNS调度方法有DNS轮询(DNSround-robin)和加权DNS轮询调度算法(weightedround-robinscheduling,简称WRR)[4].
然而,由于URL和IP的对应关系会在浏览器及许多中间媒介的DNS中缓存,因此,只有部分用户请求可以由服务器端来调度;而服务器端DNS每次选中系统中的某个服务器,都有可能在某一时段(TTL)内给该服务器带来难以预测的突发流量.

以分配器为中心的DWSS[5~7]以分配器为前端机,它不但可以控制所有的用户请求流量,而且还可以为站点提供单一的IP映像.
一般情况下,所有的用户请求都首先发往分配器,由它按照某种调度策略将请求转发给系统中的某一个Web服务器主机(又称为后端机)来处理.
分配器上使用的用户请求分发方法有多种.
简单轮询(roundrobin)、URL-Hash等静态调度方法不考虑服务器的实际负载等状况,难以实现真正的负载平衡;HTTP重定向、最小连接法(least-connectionscheduling)以及带权重的最小连接法等动态调度算法,利用定期收集的服务器负载等状态参数动态调整负载的分布,从而改善负载平衡效果.
但是,http重定向使用户必须重新建立TCP连接,增加了延迟,也增加了网络流量,而分配器转发过程中对数据包的改写会引入额外的延迟,如果处理不当,则可能使分配器成为系统的瓶颈.
在基于分布式用户请求调度策略的DWSS中,组成系统的每一个服务器都参与用户请求的调度,它克服了集中调度方式中因核心设备负载过重而易成为系统瓶颈的缺点[8].
使用HTTP重定向方式控制负载的分布[9];利用特制的Web服务器软件对Web页面中嵌入的URL进行操作并完成相应的URL内容的自动拷贝和转存,从而实现对负载分布的控制.
这些方法的弱点是增加了网络通信负荷,并引入了较明显的延迟.

在上述DWSS中,用户请求的分发方法都只考虑了多个服务器的负载平衡,而没有考虑Cache的命中率,长时间来看,系统中的每一个服务器都倾向于提供该站点的全部内容,而这些内容往往会超出单个服务器的缓存能力;另一方面,相同的内容可能在多个服务器中重复缓存,资源利用率低,系统的整体缓存命中率不高[10,11].
实际上,CPU速度的提高远远要比磁盘存取速度的提高快得多,因此,当磁盘存取速度远远不能满足CPU的需求林曼筠等:基于标记的缓存协作分布式Web服务器系统119时,提高Cache的命中率对于改善DWSS的性能将是十分有益的.
另外,使用"识别内容的请求调度策略(content-awarerequestsdistribution,简称CARD)"[11~13],有利于分布式存储策略的实施,也便于使用专门的服务器为特定的一些客户提供服务,以确保服务质量.
多方面的用途使CARD日益受到关注.
CARD首先了解用户请求的文档内容,然后再选择适当的服务器来处理该请求.
由于HTTP协议是建立在面向连接的TCP/IP协议上的,因此,必须首先经过3次握手,建立用户与Web服务器端的TCP连接,才能了解用户请求的内容.
为了保持调度方法对用户透明且开销最小,必须有某种方法,使实际处理用户请求的服务器无须再次建立与用户的TCP连接,而是接受已有的连接,直接处理用户的请求并给出回应[11,12].
TCP连接转交(TCPhandoff)[11]是目前较好的方案.
基于LARD(localawarerequestsdistribution)[11]的DWSS使用TCP连接转交方法获得了比WRR更高的吞吐率.
MohitAron等人[12]指出,该系统的前端机是潜在的性能瓶颈,并提出了一种改进的方法SCARD.
SCARD通过使用多个设备分担前端机的工作,以改善系统的可扩展性.
但是,该系统中前端机性能的改善是以增加系统内部各设备之间的通信量为代价的.
分发器需要与分配器进行通信,以便了解URL的分布情况.
在完成TCP转交或者连接中断时,分发器需要与前端机通信,以便于更改连接信息.
这些内部通信不但增加了参与通信的各个部件的负担,也占用了系统内部宝贵的网络带宽资源,使系统的扩展性受到限制.
我们建议分发器使用批量查询的方法,即当收到多个用户的URL请求之后再向分配器查询其分布情况,而不是为每一个用户的URL请求单独发送一个查询包.
显然,这种方法将增加用户的响应延迟.
2基于标记的缓存协作分布式Web服务器系统在基于LARD的DWSS中,前端机的工作主要包括TCP/IP连接的建立、数据包的转发、URL分发和TCP连接的转交.
实验表明[11,12],TCP/IP连接的建立和转交的延迟都远远大于URL分发和数据包转发的延迟,因此,TCP连接的建立和转交是系统扩展时前端机不堪重负的主要原因.
为了保持LARD和SCARD的优点,克服其不足,我们设计了一种新的DWSS,即基于TB-CCRD请求调度方法的DWSS.
该系统通过集中管理URL在各个服务器Cache的分布来提高Cache的命中率;利用标记传递URL分布信息,避免额外的网络通信量;用分布式处理TCP连接转交消除系统的瓶颈.
2.
1系统框架结构及工作原理基于TB-CCRD的新系统采用与Linux直接路由式虚拟服务器相同的框架结构.
如图1所示,DWSS的各个后端服务器通过高速以太网相互连接,它们屏蔽ARP协议,并拥有与前端机相同的IP(记为vIP)和Web服务端口号(记为vPort),在用户看来,这个系统就相当于一个IP地址为vIP,服务端口号为vPort的Web服务器.
在新系统中,前端机负责接收来自用户的数据包,发放用于指示处理该数据包最适当的服务器ID(可以是后端机在系统内部的标识符,也可以是它的MAC地址)的标记,并转发数据包;后端机则负责处理由前端机转发而来的用户数据包并直接回应用户,具体包括建立/拆除与用户的TCP连接、TCP连接转交以及提供URL内容等工作.
Back_endserverBack_endserver.
.
.
Back_endserverFront_endserverBrowserRequestResponseInternetFig.
1TheframeworkoftheTB-CCRDbasedDWSS图1基于标记的缓存协作DWSS系统框架2.
2系统工作流程2.
2.
1连接状态表和URL分布表为了转发用户数据包和实现对后端机缓存系统的统一管理,前端机需要维护两张表:连接状态表和URL分布表.
连接状态表通过某一连接的用户端标识(即用户的IP地址和端口号,记为(IPc,PORTc))检索出服务器系统中负责处理该连接的后端机的MAC地址、该连接的最近使用时间和连接状态.
此外,根据某个后端服务器的120JournalofSoftware软件学报2003,14(1)MAC地址检索该表,还可得到该服务器当前负荷情况(由当前的活动连接数表示).

URL分布表通过URL-hash,检索对应的URL内容在哪一个(或一组)后端机的本地磁盘或者cache中(后端机由它的MAC地址代表、本地磁盘命中标志的"True"/"False"表示该URL是/否在硬盘中,cache命中标志的"True"/"False"表示该URL是/否在cache中).
该表还记录各个URL的大小(url_size)及其在cache中最后一次被访问的时间.
在站点发布新的内容时,产生或者更新URL分布表.
初始状态,磁盘命中标志(Disk_hit)根据URL是否在本地磁盘中存储而分别设为"True"或"False",而所有的缓存(Cache_hit)命中标志都设为"False",当URL内容进、出后端机的cache时,缓存标志作相应的修改.
2.
2.
2系统的工作流程TB-CCRD方法需要前端机和后端机相互配合来实现.
基于TB-CCRD的DWSS的工作流程如图2所示.
75LANWebrequestUser/BrowserBack_endserverTCP/IPhandoffTagschecker/urldistributorApplicationlayerOSkernelFront_endserverBack_endserverTCP/IPhandoffTagschecker/urldistributor12TCP/IPpacketscheckingTagsdistributor34Framere-organizerFramesender689WebserverresponseServersideClientsideFig.
2TheoperationflowchartoftheTB-CCRDbasedDWSS图2基于标记的缓存协作DWSS的工作流程图为了描述方便,我们按照TCP标志位和TCP数据部分长度的不同特点,将DWSS收到的来自用户的IP数据包分为4类:(1)TCP连接建立请求包.
用于向Web服务器请求建立TCP连接,特点是TCP的syn标志位置1,简称为syn包.
(2)信息确认包.
这是指用户收到来自服务器的数据包(比如连接请求应答包,即ack和syn都置1的包,或者包含用户所请求的URL内容的数据包)之后发给服务器的确认数据包,其特点是TCP标志位ack置1,且TCP的数据部分长度为0,简称为ack包.
(3)URL请求包.
这是TCP连接建立之后,用户用于向服务器索取URL内容的数据包,其特点是ack位置1,且TCP的数据部分包含用户希望索取信息的URL字段等信息,长度不为0,简称为url请求包.
(4)TCP连接结束数据包.
这类数据包在用户希望结束TCP连接或者收到不属于当前TCP连接的服务器端数据包时使用,其特点是,TCP的fin或者rst位置1,简称为fin/rst包.
在新系统中,前端机位于用户通往真正提供服务的后端Web服务器的逻辑路径上,每一个来自用户的IP数据包(记为P)都必须经由它中转.
为了避免重新计算IPchecksum,我们将标记插在以太网帧头和IP数据包头之间.
考虑到MAC地址能够方便地惟一识别一台后端机,我们采用后端机的MAC地址作为标记,并将特殊的MAC地址"0x000000000000"称为0标记.
若P为syn包,则前端机根据WRR规则为它选择一个后端机(记为BEtmp,其MAC地址为MACtmp),向BEtmp转交由P和0标记构成的数据帧,并将相应TCP连接的状态信息存入连接状态表中;若P是url请求包,则首先由前端机的标记分发模块为它选择一个标记tag(记为MACbest,相应的后端机记为BEbest),然后,前端机向当前处理该连接的后端机转交由P和相应标记(即MACbes)构成的数据帧,并修改连接状态表中相应TCP连接的状态林曼筠等:基于标记的缓存协作分布式Web服务器系统121信息(更新"最后通信时间"、"连接状态",并将"处理该连接的后端机MAC地址"改为标记分发模块新选中的MACbest);若P是ack包或者fin/rst包,则前端机根据连接状态表读取处理该连接的后端机MAC地址(MACtmp或MACbest),向它转交由P和0标记构成的数据帧,对ack包,前端机还要修改连接状态表中相应TCP连接的状态信息(更新"最后通信时间"、"连接状态"等信息),对于fin/rst包,前端机还要删除连接状态表中相应的记录.
标记分发模块产生标记tag的方法如下:(1)根据P.
url查询URL分布表和连接状态表,获取Cache_hit="True",且当前活跃连接数目最小的后端机,记为BEbest.
(2)如果所有后端机缓存中都没有P.
url,或者(1)选中的后端机已经满负载运行,则(a)另选一个对P.
url而言Disk_hit="True",且当前活跃连接数最小的后端机,记为BEbest;(b)更改URL分布表中相应于(P.
url,BEbest)的记录,把P.
url在BEbest中的Cache命中标志置为"True";(c)检查BEbest是否有足够的cache空间存放P.
url,如果空间不足(∑url_size>MAX_CACHE_SIZE),则按照预先约定的缓存替换策略,把即将被替换出缓存的url的Cache_hit置为"False".
(3)将所选中的最佳后端机BEbest的MAC地址MACbest作为标记,即tag=MACbest.
更新URL分布表中相应于(P.
url,BEbest)的记录的最后访问时间.
如果站点内容可以全部存在于一个后端机的本地硬盘中,则这是上述算法的一个特例,只要将URL分布表中的"本地磁盘命中标志"都置为"True"即可.
HTTP1.
1允许在一次TCP连接过程中提交多个URL请求,这些URL可能缓存于不同的后端机中,这时,系统需要进行多次TCP连接转交.
上述算法同样适用.
后端机负责建立和拆除与用户之间的TCP连接,按照前端机给出的标记处理用户的URL请求,实现URL在Cache中的分布.
根据标记的不同,当后端机收到数据包时,执行不同的操作:若tag为0标记,则由本机的Web服务器进程来对数据包进行处理:建立与用户的TCP/IP连接,或者从本地Cache中获得相应内容并应答用户,若Cache不命中,则从磁盘获得数据并缓存,然后回应给用户;若tag不是0标记,则将相应的TCP连接转交给tag所指示的最佳后端机BEbest,由它来接手处理该URL请求以及此后属于该连接的所有数据包.
从系统的算法流程中可以看到,前端机对系统缓存的集中管理,使其能够给出TCP的转交信息,后端服务器在完成连接转交之后无须向前端机通告连接的变更信息;同时,前端机通过在客户的URL请求数据包中插入标记的方式通告TCP的转交目标;这些措施使得新系统在使用分布式处理TCP连接转交的同时无须引入大量额外的系统内部通信开销,节省了宝贵的内部带宽资源.
3性能的数值比较与仿真实验LARD通过提高URL请求命中率获得了较好的Web服务性能,但是,LARD使用集中处理的方式完成TCP连接的建立和转交,导致前端机容易成为系统瓶颈,扩展性较差.
SCARD致力于改进前端机的处理能力,从而改进系统性能和扩展性,但是它的URL分发方案带来了随系统规模增长的不可忽视的系统开销,使系统的扩展性受到限制.
WRR系统虽然有更好的扩展性,但是Web服务性能较差.
以上方法在系统的可扩展性和Web服务性能上不可兼得.
DWSS系统的扩展性主要体现在前端机的处理能力以及系统内部信道的开销上,而Web服务的性能主要体现在URL的cache命中率及吞吐率上.
我们的TB-CCRD方法同时考虑了以上两个方面的问题,在维护系统良好的扩展性的同时获得较高的性能.
下面,我们通过模拟实验和性能比较来分析TB-CCRD系统的扩展性和Web服务性能.
3.
1前端机扩展性比较根据文献[11,12],在基于LARD的DWSS中,前端机处理一个请求所需的CPU时间为T1=连接建立时间(Tconn)+TCP转交时间(Thandoff)+任务分派时间(Tdispatch)+Pack转发时间(Ttranfer).
其中Thandoff,Tconn都在Ttransfer的15倍以上,而Tdispatch为Thandoff的10%~20%.
122JournalofSoftware软件学报2003,14(1)对基于TB-CCRD的系统,在同等条件下,前端机处理一个请求所需的CPU时间为T2=P.
syn/P.
fin/rst/P.
url/P.
ack的转发时间(4*Ttransfer)+任务分派时间(Tdispatch).
可见,TB-CCRD系统前端机的处理能力是LARD系统的5倍以上.
3.
2系统内部信道开销比较在SCARD系统中,分配器与每一个后端机之间建立一个持久的TCP连接,当后端机收到客户的URL请求之后,它将利用这个连接向分配器询问该URL该由哪一个后端机来处理,因此,了解一个URL的缓存位置所带来的系统内部信道开销包括从后端机发往分配器的查询数据包和相应的分配器的回应数据包.
根据文献[12]提供的原型系统,后端机发往分配器的查询数据包的最小长度为以太网帧报头/尾(26B)+IP报文报头(20B)+应用层报文报头(22B)+URL_hash(16B)=84Bytes.
分配器的回应数据包最的小长度为以太网帧报头/尾开销(26B)+IP报文报头开销(20B)+应用层报文报头(26B)=72Bytes.
TB-CCRD系统采取类似于MPLS夹缝头(shimheader)的标记封装方式,在客户的URL请求包中加贴一个标记来传播URL的缓存分布信息.
大多数的HTTP连接包含5~6个来自用户的数据包[12],因此,后端机了解一个URL的缓存位置所带来的系统内部通信开销为6Bytes*6=36Bytes,小于SCARD系统通信开销的1/4.
3.
3Web服务性能仿真实验3.
3.
1仿真模型及其参数为了研究和比较不同的用户请求分发策略的效率和性能,并与文献[11]具有可比性,我们参照文献[11]给出的实验模型和参数,以软件方式定制了DWSS仿真模型,对TB-CCRD和WRR调度算法的性能进行比较.
DWSS仿真模型如图3所示.
CachemissReadfinishedNewrequestBack_endactivequeueFront_endwaitingqueueDiskCPU在该模型中,每一个后端Web服务器都有自己的CPU和磁盘,用户的Web请求经过前端机的调度后进入各后端机的等待处理队列.
对用户Web请求的处理包括连接建立、磁盘文件读取(Cache不命中时)、数据传输、连接拆除几个步骤.
我们使用与文献[11]相同的延迟参数.
Fig.
3DWSSsimulationModel图3DWSS仿真模型我们在数值仿真实验中使用LRU缓存替换算法,大于500KB的文件不缓存.
同一个请求的几个处理步骤必须顺序进行,不同请求的CPU处理时间、访存时间和磁盘存取时间可以重叠,并假设网络性能和前端机的速度都能够满足系统的最大吞吐率要求.
3.
3.
2仿真实验的输入文件和输出结果仿真实验的用户请求序列来自Clarknet的存档轨迹文件[14].
系统的整体吞吐率以轨迹文件中请求的个数除以模型处理完这些请求所需要的时间而得到,Cache不命中率由不命中的请求个数除以输入请求的总个数得到.
图4和图5是仿真实验的结果.
从图中可以看出,基于TB-CCRD的DWSS的命中率明显高于基于WRR的系统,而且随着系统规模的扩大,前者的性能越来越优于后者.
数值仿真实验的结果表明,相对于WRR算法,尽管TB-CCRD算法引入了URL分发和TCP连接转交等额外的开销,但由于新系统显著提高了Fig.
4Throughput图4吞吐率8000100001200014000TB-CCRDWRR304050TB-CCRDWRRCachemissratio(%)Cachemissratio(%)0102013579111315Numberofback-endserversNumberofback-endserversFig.
5Cachemissratio图5Cache不命中率Throughput(Reqs.
/s)Throughput(Reqs.
/s)020004000600013579111315Numberofback-endserversNumberofback-endservers林曼筠等:基于标记的缓存协作分布式Web服务器系统123缓存命中率,因此能够较显著地提高系统的吞吐量,从而缩短对用户请求的响应时间,提高Web服务性能.
4结论本文在分析现有的分布式Web服务器系统技术的基础上,提出了一种基于标记的缓存协作分布式Web服务器系统,该系统通过前端机将系统中各个服务器的缓存组织成为一个大的虚拟缓存系统,以集中管理的方式控制URL在这个大的虚拟缓存系统中的分布,并利用在正常通信数据包中加贴标记的方式传递URL的分布信息.
该系统的特点是:(1)使用识别内容的请求分发方法,在进行用户请求分发时不仅考虑负载分布情况,同时还考虑URL的cache命中率问题,从而提高系统的总体cache命中率,缩短用户请求响应时间,提高Web服务性能.
(2)把导致前端机性能瓶颈的TCP连接转交分布到各个后端机去完成,随着系统规模的扩大,参与完成TCP连接转交的主机数目也相应增多,从而使得前端机不会成为系统瓶颈.
(3)把提高URLCache命中率的分布式功能通过标记的方式实现,避免了额外的网络通信负荷.