ѧ
JOURNAL OF SOFTWARE
1999 10 7ڡNo.7 Vol.10 1999



WWWȺ㷨о
ۡ˸֣γˡ
ժҪΪЧWWWӦٶȺͿչ,෱æվ׷תòWWWȺԭеĵһ.Щվձ似,неHTTP,Ȼ󡰾⡱ط䵽Ⱥеĸд.õתַӷӷ㷨ڷʱ,ҪôԼȺиܲ,Ҫôľ,ʵϵͳЧʽϵ.һ칹Ⱥľֲ㷨least time increment,LTI,ۺϿǷܲ졢ݺͷǰص,Ϊ.»LTI㷨ĸĽLTI+,ܹбͱ⼯Ⱥٽ״̬.¸㷨۷ʵԽ.ͬ,㷨ܹﵽСƽӦӳٺͽϴ,ӶܸõھȺĲд,ŻȺ.
ؼʡWWWȺ,HTTPЭ,,ؾ,㷨,ٽ״̬.
ͼšTP393
Research on Request Dispatching Algorithm for Web Server Clusters
DI Shuo ZHENG Wei-min WANG Ding-xing SHEN Mei-ming
(Department of Computer Science and Technology Tsinghua University Beijing 100084)
AbstractIn order to improve the throughput, response speed and scalability of Web servers efficiently, many famous Web sites have thrown away single servers and turned into Web server clusters. Request-dispatching is a technology used by these sites, which centrally accepts all the coming requests and evenly dispatches them to the servers in the cluster.Round-robin, Least-connections and Fastest Connection algorithms which Commonly used request-dispatching show low efficiencies, because they either do not consider the difference in performance between servers or do not consider the contents of coming HTTP requests. In this paper, the authors give a novel algorithm designed for heterogeneous Web server clusters, called LTI (least time increment), which considers not only the deference in performance between servers, but also the contents of coming HTTP requests and the current load level of each server in the cluster. They also give the reformed edition of LTI algorithm, namely LTI+, which can judge whether the cluster is closed to the critical state and prevent such trend. Theoretical analysis and real system test show that the algorithm achieves better response latency and throughput than Least connections and Fastest Connection algorithms. So it makes the Web server clusters more parallel and more scaleable.
Key wordsWeb server clusters, HTTP protocol, request dispatching, load balancing, request dispatching algorithm, critical state.
InternetϵWWWվ,ŷͷƵȵĲ,ʼWWWص1.Ϊ,߷Ӧٶ,ǲò.ѡ,һǲðĸSMP,һǰѶ̨þһȺ,ͨдչܣ13.Ƚַ,ߵĳɱϵ,ҾнϴԺͽϸߵĿɿ,ĿǰWWWվѾתƽ̨.ǳƽ̨ΪWWWȺ.
2,3ǲWWWȺвõһֵͼ.Ҫԭһ̨ļһΪнеHTTP,ȻһԭǷ䵽Ⱥеĸ̨ȥд.ҪĿʹ̨ĸطֲȽϾ,ӶýϸߵͽϿķӦٶ.Ŀǰõ㷨Ҫתַ2ݡӷӷ33.1㷨ʵּ,ӱϽûпǸؾ.2㷨Ըܲ,Ҳǿȣļĳȣ.3㷨Ȼ˷,ûпǿ.ЩʹЩ㷨޷صġ⡱,޷ϺõطϵͳĲд.
ΪЧ㷨Ч,ʹ㷨ܹӦ칹Ⱥ,ƲWWWȺϵͳʱ,Ӧʹܹ֪ÿһ̨Ĵ,ҿɶԼнյÿһHTTPݽз,ͬʱӦܱȽ׼ȷظٸĸ.Ĵͨʵ,HTTPֻͷ,ظͨϼ¼Ӧʵ.Ͽ,ʵһ칹WWWȺ,һۺϿHTTPݺ͸Լǰĸ㷨LTI(least time increment),ĿʹӦʱܺ;ܶ.Ϊ,ǰӦʱΪLTI㷨Ż.Ϊ˱ӽֵʱܼ½,ǻһӳٲ,Чؽ.Ƕ㷨۷,Ƕϵͳʵʲ,LTI㷨ıֶתַӷӷҪ.
ĵ1ڽļȺϵͳɺ͹ԭ.2ڼҪ۵ļ,ȻӰܵ,һЩ.3ڸ㷨LTI,з͸Ľ.4ڸǶϵͳĲԽ,ӷӷĽбȽ.,5ڸĵĽ,δҪĹһ.
1ϵͳɺ͹ԭ
ĿǰĲWWWȺҪɷʽ,һCiscoLocalDirector3Ϊĸʽ,ӷӷ;һNCSAScalable Web Server2ΪķǸʽ,תַ.һַʽ,Ҫ̨WebϢķ·Ҫȫһһͨļϵͳרõļʵ֣.ߵЩǷֱInternet,ûɼ.ʽȺProxy4ݵļ,ֻһIPַ,е󶼷IPַ,䵽Ⱥеĸ̨ȥ,صĽҲظûǸʽȺеÿһ̨жIPַ,̬ͨDNS2,HTTP Redirect3ݵȼʵֵ,Ӧͨ,ɸֱ̨Ӵظû.ͼ1ֲͬṹȺʾͼ.

ͼ1ֲͬṹĲWWWȺɽṹ
ǵļȺϵͳõǸʽ,ȺFast Ethernet̨Power PC̨Sun WorkstationɣPower PCSun Workstation,UNIXϵͳNCSA HTTPD,һ̨Windows NTPC䵱.ļϵͳNFS,ö߳Proxy.
2۲Ӱܵ
Ŀǰ,WWWҪʺƽӦӳ5.RPSΪƽÿ봦,ƽӦӳMRDΪӽӵӦ֮ʱƽֵ.õĲԼɸСһһķֲ.νĴСָȡļĳȻִеScriptڶռʱִʱ.
HTTPЭ6һ״̬Э,ÿɿͻһ,Ӧɷ.ͷ,ͷһ־нṹı,һֳΪMIMEʽĸı.ͷָĿ,,ȡļ֤ļǷ»ִзϵScripts.ͬHTTPԷĸشźܴĲ.
RPSMRDɷĴ.WWWȺ˵,MRDеϵ.Щϵ.
һӦʱҪ3ɣ7ݣ
(1) ʱTC.ʱһԺ.
(2) ȡļʱTF.ʱȡļȡʹٶȦ.һʱ,Nֲ,ʱ,ؿԽƵΪNɷ,=/N.,Ϊֻһʱļȡʹٶ,һضķ,ʵ.ǳƦΪӦٶ,Ϊٶ.
(3) ڷִScriptsʱTE.Ƚϸ,ʱȹ.Ϊ˼,ʱTE.
һҪ˵NĳһֵNMaxȡڷ,һضķʵãʱ,TCͻȻֱ,ͬʱػͻȻ½8,ͼ2ʾ.ǳ״̬Ϊٽ״̬,NMaxΪ˷ٽ.⣺ЩҪķĻԴ,ӽ򳬹ϵͳڴ޶ʱ,ϵͳʼʹá桱,ʱԲ,Ʊزһֶѭ,ϵͳЧʼ½.,Ϊ˱֤ϵͳRPSMRD,Ӧ跨NﵽNMax.

ͼ2TcwNNMaxʱ仯
һ̨ʱӦʱ.
ĳһʱ̸÷Nͬʱļ,Щļʣ೤ȷֱΪL1,L2,...,LN.ʱ,һµHTTP󵽴÷,ļΪL.L1...LKL<LK+1...LN,ģͣļʱļĳȳ,ٶȳɷȣԼ㣨˴ʡԼ㷽LӦʱ
(1)
㷨Ҫ.
3 㷨
Ϊʵ㷨,ü.1ΪFLT,еΪWWWռļ·ͳ.2ΪTST,дŵǸĻٶ.3ΪRCT,ŸӦ.輯ȺйM,ΪÿһCFT(i),1iM,Ŵ˷ǰӦĸļĳȺʣ೤.㷨LTIö̼߳,㷨ɲ߳,һڸٸӦ,һ.
㷨1. 㷨LTI.
߳1ظ٣
ÿһ̶СʱΦȽ²
(1) TSTRCTӦٶȦ.
(2) CFT(i)иļʣ೤٦*,1iM.
ĳļʣ೤ȡ0,ɾӦCFT(i)ĶӦRCTд˷ĵǰ.
߳2䣩
(1) 󵽴,ͷеURLȡļ·,FLTвļĳL.
(2) ÿi,TSTRCTCFT(i),ʽ(1)ķ㽫L÷Ӧʱi,1iM.
(3) 覤K=Min(i),1iM,LK,ͬʱRCTд˷ĵǰ,CFT(i)һ,ļʣ೤1ΪL.
LTI㷨ӦʱΪŻĶ,,¶.
. ŻMRD˵,LTI㷨һֲ㷨.
֤:һԼn,ʽ(1)MRDĶ,

T(i)CΪӽʱ,Ϊ̶ֵ(i)ΪǰĻӦʱ.LTI㷨,µÿһʱ,ʹӦĦ(i)ȡ˵ǰ״̬¿ܵСֵ,,ӾֲϽ,㷨ŵ.
ָ,Nӽ򳬹ĳһֵNMaxʱ,ܻἱ½.㷨ûп,ڸغʱ,Ӧʱ佫󳬹Ԥֵ,㷨׼ȷԾ͵ò֤.мַ.1ַǾܾ,ֱз˳ٽ״̬.2ַǽµ䵽һ̨ȥ.3ַǽµӳ,ȵз˳ٽ״̬ʱԴ.
1ַΪûѽ,ʵǲе,ǲ迼.ǶԵ2ַʵо,ְLTI㷨ѡķﵽֵʱ,Ҳ϶ӽٽ״̬,,ַ𲻵ԵЧ.ǽϵ2͵3ַ,LTI㷨¸Ľ.
޸ıRCT,г˴ŸӦN,ǵٽ.ӶDRQ,ٽ״̬ӳٵļĳ.һӽٽ״ָ̬NӽδﵽٽNMax,ʱ,ܻûм½.
㷨2. 㷨LTI+.
߳1ظ٣LTI㷨ͬ.
߳2䣩
(1) 󵽴,ͷȡļ·,FLTвļĳL.ʱûδӽٽ״̬ķ,ӳٶDRQĶβ,ļĳȣ
(2) δӽٽ״̬ķi,TSTRCTCFT(i),ʽ(1)ķ㽫L÷Ӧʱi,1iM.
(3) 覤K=Min(i),1iM,LK,ͬʱRCTд˷ĵǰ,CFT(i)һ,ļδΪL.
߳3ӳٵ
ӳٶDRQǿ,ÿʱȼǷз˳ٽ״̬.,²
(1) ȡDRQ׵,ļĳΪL.
(2) δӽٽ״̬ķi,TST,RCTCFT(i),ʽ(1)ķ㽫L÷Ӧʱi,1iM.
(3) 覤K=Min(i),1iM,LK,ͬʱRCTд˷ĵǰ,CFT(i)һ,ļδΪL
㷨LTI+һ̴߳ӳٵ.Ⱥδӽٽ״̬ʱ,㷨㷨LTIȫͬ.Ⱥӽٽ״̬ʱ,㷨ͨӳµ⼯Ⱥٽ״̬.ھм϶ͻԵ,㷨ʵǽͻ⵽Ժʱȥ.
4 ʵıȽϺͷ
ĵ1ڽʵֵһȺ.ƽ̨϶LTILTI+㷨ʵо,ӷӷ˱Ƚ.
ף9ݶǿȷֲо,һɲͬǿȵɵĲԼ.ǿȵķֲ1ʾ.
1ǿȵķֲ

ļС(Bytes)5005K50K500K
ռ(%)3550141


õ4̨Power PC䵱,.ÿģ150WWW Client,ÿClient̶ܰձ1ıϷHTTP,ܹ¼ЩӦʱ.ʵͼ36ʾ.ͼ3ͼ5LTI㷨㷨㷨Client5ʼʱƽӦӳٺʵı仯.ͼ4ͼ6LTI+㷨LTI㷨Client100仯200ʱƽӦӳٺʵı仯. 

ͼ33㷨ڲͬClientʱMRD

ͼ4LTILTI+㷨MRDıȽ

ͼ53㷨ڲͬClientʱRPS

ͼ6LTILTI+㷨RPSıȽ
ͼ3ͼ5Ľ֤ʵӷӷ,LTI㷨ȷʵܹЧؼƽӦӳٺ.ClientСʱ,ܸƲ̫,ClientһЩ,LTI㷨Ʋ𽥱ֳ.˵ڼȺĸؽʱ,3㷨󶼿Դﵽ⸺صĿģﵽһĸɣﵽһ,LTI㷨ԼȺصĸٺͷΪȷ,ԸصķΪ.
ͼ4ͼ6֪,Clientһ,LTI㷨Ҳʼ½,ʱ,LTI+ԽԾֳ.ΪŸصļ,׷׽ӽٽ״̬,LTI+㷨б״̬,ȡʩЧرƵ,LTI㷨û.
5 
ļҪWWWȺɺ͹ԭ,ܵӰܵ,رǷӦʱǿԼǰ״̬֮Ĺϵ.ڴ˻,ӦʱΪŻĿ㷨LTI,֤˸㷨ľֲ.Ϊ˽Ⱥڽӽٽ״̬ʱܼ½,ǶLTI㷨˸Ľ,õ㷨LTI+,㷨ܹбͱ⼯Ⱥٽ״̬.,ǸһЩʵ,ͨ㷨бȽ,֤ʵLTILTI+㷨ЧԣܹӾȷظٺͷȺϵͳĸ,Ӿط为,ӶﵽϺõ.
ڱĵ۹,Ϊ˼,ʱûпһЩʵдڵ,磬ڼȡļʱʱTFģ,ûпڷִScriptsʱTE.ǵ㷨һЩ.ĿǰڶЩио.,ǻȫļϵͳΪȺиṩͳһļ·ĹͶԤȡȷѰܵ;.
оõ863߿ƼĿ.ۡ˸,1970,ʿ,ҪоΪ,д.֣γ,1946,,ʿʦ,ҪоΪлȺϵͳ,.,1937,,ʿʦ,ҪоΪ/ֲ,ܼϵͳ.,1938,,ʿʦ,ҪоΪ/ֲ,лȺϵͳ.
ͨѶϵ:ۡ˸,100084,廪ѧѧ뼼ϵ
ߵλ廪ѧѧ뼼ϵ100084
E-mail dishuo@263.net
ο
1Kwan Thomas T, McGrath Robert E. NCSA's world wide web server: design and performance. IEEE Computer, 1995,28(11):6874
2Katz Eric Dean, Butler Michelle, McGrath Robert E. A scalable HTTP server: the NCSA prototype. Computer Networks and ISDN Systems, 1994,(27):155164
3Cisco Inc.. Scaling the World Wide Web. Technical Report, http: //www.cisco.com
4Luotonen A, Altis K. World wide web proxies. In: Proceedings of the 1st International Conference on the World-Wide Web. 1994
5Trent Gene, Sake Mark. WebSTONE: the first generation in HTTP server benchmarking. Whitepaper, Silicon Graphics Inc., February 1995
6Berners-Lee T, Fielding R T, Frystyk H. Hypertext transfer protocol-HTTP/1.0. Informational RFC 1945, Network Working Group, May 1996
7Padmanabhan Venkata N, Mogul Jeffrey C. Improving HTTP latency. Computer Networks and ISDN Systems, 1995,(28):2535
8Slothouber Louis P. A Model of Web Server Performance. April 1997. http: // louvx.biap.com/webperformance/modelpaper.html
9Carlton Alexander. An Explanation of the SPECweb96 Benchmark. Whitepaper, Standard Performance Evaluation Corporation, 1996
1998-03-20յԭ 
1998-08-03յ޸ĸ
