A performance study of robust load sharing strategies fordistributed heterogeneous Web server systems

Replication of information across multiple servers is becoming a common approach to support popular Web sites. A distributed architecture with some mechanisms to assign client requests to Web servers is more scalable than any centralized or mirrored architecture. In this paper, we consider distributed systems in which the Authoritative Domain Name Server (ADNS) of the Web site takes the request dispatcher role by mapping the URL hostname into the IP address of a visible node, that is, a Web server or a Web cluster interface. This architecture can support local and geographical distribution of the Web servers. However, the ADNS controls only a very small fraction of the requests reaching the Web site because the address mapping is not requested for each client access. Indeed, to reduce Internet traffic, address resolution is cached at various name servers for a time-to-live (TTL) period. This opens an entirely new set of problems that traditional centralized schedulers of parallel/distributed systems do not have to face. The heterogeneity assumption on Web node capacity, which is much more likely in practice, increases the order of complexity of the request assignment problem and severely affects the applicability and performance of the existing load sharing algorithms. We propose new assignment strategies, namely adaptive TTL schemes, which tailor the TTL value for each address mapping instead of using a fixed value for all mapping requests. The adaptive TTL schemes are able to address both the nonuniformity of client requests and the heterogeneous capacity of Web server nodes. Extensive simulations show that the proposed algorithms are very effective in avoiding node overload, even for high levels of heterogeneity and limited ADNS control     

An approximation-based load-balancing algorithm with admission control for cluster web servers with dynamic workloads

The growth of web-based applications in business and e-commerce is building up demands for high performance web servers for better throughputs and lower user-perceived latency. These demands are leading to a widespread substitution of powerful single servers by robust newcomers, cluster web servers, in many enterprise companies. In this respect the load-balancing algorithms play an important role in boosting the performance of cluster servers. The previous load-balancing algorithms which were designed for the handling of static contents in web services suffer from significant performance degradation under dynamic and database-driven workloads. Regarding this, we propose an approximation-based load-balancing algorithm with admission control for cluster-based web servers in this study. Since it is difficult to accurately determine the loads of web servers through feedbacks from distributed agents in web servers, we propose an analytical model of a web server to estimate the web servers’ loads. To achieve this, the algorithm classifies requests based on their service times and track numbers of outstanding requests for each class of each web server node and also based on their resource demands to dynamically estimate the loads of each node. For the error handling of the model a proportional integral (PI) controller from control theory is used. Then the estimated available capacity of each web server is used for load balancing and admission control decisions. The implementation results with a standard benchmark confirm the effectiveness of the proposed scheme, which improves both the mean response time and the throughput of the cluster compared to rival load-balancing algorithms, and also avoids situations in which the cluster is overloaded, even when the request rates are beyond the cluster capacity.     

Trade-offs in designing Web clusters

High-volume Web sites often use clusters of servers to support their architectures. A load balancer in front of such clusters directs requests to the various servers in a way that equalizes, as much as possible, the load placed on each. There are two basic approaches to scaling Web clusters: adding more servers of the same type (scaling out, or horizontally) or upgrading the capacity of the servers in the cluster (scaling up, or vertically). Although more detailed and complex models would be required to obtain more accurate results about such systems' behavior, simple queuing theory provides a reasonable abstraction level to shed some insight on which scaling approach to employ in various scenarios. Typical issues in Web cluster design include: whether to use a large number of low-capacity inexpensive servers or a small number of high-capacity costly servers to provide a given performance level; how many servers of a given type are required to provide a certain performance level at a given cost; and how many servers are needed to build a Web site with a given reliability. Using queuing theory, I examine the average response time, capacity, cost, and reliability tradeoffs involved in designing Web server clusters.     

Tulip: A New Hash Based Cooperative Web Caching Architecture

With the exponential growth of WWW traffic, web proxy caching becomes a critical technique for Internet web services. Well-organized proxy caching systems with multiple servers can greatly reduce the user perceived latency and decrease the network bandwidth consumption. Thus, many research papers focused on improving web caching performance with the efficient coordination algorithms among multiple servers. Hash based algorithm is the most widely used server coordination mechanism, however, there's still a lot of technical issues need to be addressed. In this paper, we propose a new hash based web caching architecture, Tulip. Tulip aggregates web objects that are likely to be accessed together into object clusters and uses object clusters as the primary access units. Tulip extends the locality-based algorithm in UCFS to hash based web proxy systems and proposes a simple algorithm to reduce the data grouping overhead. It takes into consideration the access speed dispatch between memory and disk and replaces expensive small disk I/O with less large ones. In case a client request cannot be fulfilled by the server in the memory, the system fetches the whole cluster which contains the required object into memory, the future requests for other objects in the same cluster can be satisfied directly from memory and slow disk I/Os are avoided. It also introduces a simple and efficient data dupllication algorithm, few maintenance work need to be done in case of server join/leave or server failure. Along with the local caching strategy, Tulip achieves better fault tolerance and load balance capability with the minimal cost. Our simulation results show Tulip has better performance than previous approaches.     

Keta中的Socket复用技术

随着信息技术的不断发展,提高Web服务器的性能是个亟待解决的问题。内核级Web Server的实现有效地提高了Web服务器的处理能力。然而,目前的内核级Web服务器通常只处理静态请求,而动态请求需要转发到外部传统Web服务器上进行处理。本文针对一种内核级非对称多线程流水线服务器——Keta,研究并改进了动态请求的转发机制,提出了利用Socket复用技术来实现转发的策略,有效地提高了该服务器的效率。     

CoRAL: A transparent fault-tolerant web service

The Web is increasingly used for critical applications and services. We present a client-transparent mechanism, called CoRAL, that provides high reliability and availability for Web service. CoRAL provides fault tolerance even for requests being processed at the time of server failure. The scheme does not require deterministic servers and can thus handle dynamic content. CoRAL actively replicates the TCP connection state while maintaining logs of HTTP requests and replies. In the event of a primary server failure, active client connections fail over to a spare, where their processing continues seamlessly. We describe key aspects of the design and implementation as well as several performance optimizations. Measurements of system overhead, failover performance, and preliminary validation using fault injection are presented.     

Socket-based RR scheduling scheme for tightly coupled clusters providing single-name images

Server clusters for Internet services can yield both high performance and cost effectiveness. Contemporary approaches to cluster design must confront the tradeoff between dynamic load-balancing and efficiency when dispatching client requests to servers in the cluster. In this paper we describe a packet filtering-based RR scheduling scheme, intended to be an easily implemented scheme for hosting Internet services on a server cluster in a way transparent to clients. We take a non-centralized approach, in which client packets sent to the cluster's single IP address are broadcast to all of its servers. Packets requesting that a new TCP session be set up cause counters in each server to be incremented; if a server's counter matches its fixed unique ID, it takes charge of the session, else it ignores the packet. This yields a round-robin type algorithm. We describe this approach in detail, and present results of simulations that show it achieves higher performance (in terms of throughput and reliability) than similar approaches based on client-IP hashing and dispatcher-based RR.     

集群服务器在混合请求下的负载均衡优化算法

针对Web集群服务器在处理分配混合页面访问任务时开环负载均衡算法导致局部服务器负载偏高而降低系统效率的问题,建立了一类基于动态调节的闭环负载分配策略。根据服务器处理Web访问页面类型的特点,建立静态页面与动态页面混合处理的负载量模型,形成处理不同服务请求与负载均衡的内在动态映射关系,以此优化静态页面缓存与调用方式,并基于服务器负载率动态预测和均衡指标,采用负载率偏差最小的任务权重最优分配模型,确定服务器集群的最优任务权重,实现了服务器集群处理混合页面访问的负载均衡分配策略和算法。仿真结果验证了负载均衡算法的正确性和有效性,可以达到更好的负载均衡效果。     

ReDAL: An Efficient and Practical Request Distribution Technique for Application Server Clusters

Modern Web-based application infrastructures are based on clustered multitiered architectures, where request distribution occurs in two sequential stages: over a cluster of Web servers and over a cluster of application servers. Much work has focused on strategies for distributing requests across a Web server cluster in order to improve the overall throughput across the cluster. The strategies applied at the application layer are the same as those at the Web server layer because it is assumed that they transfer directly. In this paper, we argue that the problem of distributing requests across an application server cluster is fundamentally different from the Web server request distribution problem due to core differences in request processing in Web and application servers. We devise an approach for distributing requests across a cluster of application servers such that the overall system throughput is enhanced, and load across the application servers is balanced.     

基于Nginx负载均衡的动态改进算法

随着过去几十年互联网服务的指数增长,各大网站的访问量急剧上升。海量的用户请求使得热门网站的网络请求率可能在几秒钟内大规模增加。一旦服务器承受不住这样的高并发请求,由此带来的网络拥塞和延迟会极大地影响用户体验。负载均衡是高可用网络基础架构的关键组件,通过在后端引入一个负载均衡器,将工作负载分布到多个服务器来缓解海量并发请求对服务器造成的巨大压力,提高后端服务器和数据库的性能以及可靠性。而Nginx作为一款高性能的HTTP和反向代理服务器,正越来越多地应用到实践中。文中将分析Nginx服务器负载均衡的体系架构,研究默认的加权轮询算法,并提出一种改进后的动态负载均衡算法,实时收集负载信息,重新计算并分配权值。通过实验测试,对比不同算法下的负载均衡性能,改进后的算法能有效提高服务器集群的性能。     

A predictive and probabilistic load-balancing algorithm for cluster-based web servers

The exponential demands for high performance web servers led to use of cluster-based web servers. This increasing trend continues as dynamic contents are changing traditional web environments. Increasing utilization of cluster web servers through effective and fair load balancing is a crucial task specifically when it comes to advent of dynamic contents and database-driven applications on the internet. The proposed load-balancing algorithm classifies requests into different classes. The algorithm dynamically selects a request from a class and assigns the request to a server. For both the scheduling and dispatching, new probabilistic algorithms are proposed. To avoid using unreliable measured utilization in the face of fluctuating loads the proposed load-balancing algorithm benefits from a queuing model to predict the utilization of each server. We also used a control loop feedback to adjust the predicted values periodically based on soft computing techniques. The implementation results, using standard benchmarks confirms the effectiveness of proposed load-balancing algorithm. The algorithm significantly improves both the throughput and mean response time in contrast to two existing load-balancing algorithms.     

ZipfAllocation: an algorithm for static allocation of movies in a cluster of video servers

When a single video server provides a streaming service, there are many limitations. Thus, clusters of multiple video servers are widely used today to provide better service. How movies are allocated to each server in a cluster is an important and ongoing research topic because the movies are large, and there are so many of them. We have developed a movie allocation algorithm based on the observation that client accesses follow a Zipf distribution. We have developed an algorithm in which servers use their storage to their full capacities, movies are assigned to servers as evenly as possible, servers receive requests as evenly as possible, and all movies are allocated to at least one server. Copyright © 2010 John Wiley & Sons, Ltd.     

An SSL Back-End Forwarding Scheme in Cluster-Based Web Servers

State-of-the-art cluster-based data centers consisting of three tiers (Web server, application server, and database server) are being used to host complex Web services such as e-commerce applications. The application server handles dynamic and sensitive Web contents that need protection from eavesdropping, tampering, and forgery. Although the secure sockets layer (SSL) is the most popular protocol to provide a secure channel between a client and a cluster-based network server, its high overhead degrades the server performance considerably and, thus, affects the server scalability. Therefore, improving the performance of SSL-enabled network servers is critical for designing scalable and high-performance data centers. In this paper, we examine the impact of SSL offering and SSL-session-aware distribution in cluster-based network servers. We propose a back-end forwarding scheme, called ssl_with_bf, that employs a low-overhead user-level communication mechanism like virtual interface architecture (VIA) to achieve a good load balance among server nodes. We compare three distribution models for network servers, round robin (RR), ssl_with_session, and ssl_with_bf, through simulation. The experimental results with 16-node and 32-node cluster configurations show that, although the session reuse of ssl_with_session is critical to improve the performance of application servers, the proposed back-end forwarding scheme can further enhance the performance due to better load balancing. The ssl_with_bf scheme can minimize the average latency by about 40 percent and improve throughput across a variety of workloads.     

DNS dispatching algorithms with state estimators for scalable Web‐server clusters

Replication of information across a server cluster provides a promising way to support popular Web sites. However, a Web‐server cluster requires some mechanism for the scheduling of requests to the most available server. One common approach is to use the cluster Domain Name System (DNS) as a centralized dispatcher. The main problem is that WWW address caching mechanisms (although reducing network traffic) only let this DNS dispatcher control a very small fraction of the requests reaching the Web‐server cluster. The non‐uniformity of the load from different client domains, and the high variability of real Web workload introduce additional degrees of complexity to the load balancing issue. These characteristics make existing scheduling algorithms for traditional distributed systems not applicable to control the load of Web‐server clusters and motivate the research on entirely new DNS policies that require some system state information. We analyze various DNS dispatching policies under realistic situations where state information needs to be estimated with low computation and communication overhead so as to be applicable to a Web cluster architecture. In a model of realistic scenarios for the Web cluster, a large set of simulation experiments shows that, by incorporating the proposed state estimators into the dispatching policies, the effectiveness of the DNS scheduling algorithms can improve substantially, in particular if compared to the results of DNS algorithms not using adequate state information. This revised version was published online in August 2006 with corrections to the Cover Date.     

Energy-Efficient Redundant Execution of Processes in a Fault-Tolerant Cluster of Servers

This paper investigates into fault tolerance of cluster of servers and their energy efficiency to realize a reliable and energy aware server cluster system. A client issues a request to one server in a server cluster and the server sends a reply to the client in information systems. Once the server stops by fault, the client does not receive a reply of the request. Even if the request is performed on another server on detection of fault of the server, some QoS requirements like response time may not be satisfied. Hence, each request has to be redundantly performed on multiple servers to be tolerant of server faults. The redundant power consumption laxity-based (RPCLB) algorithm is discussed where multiple servers are selected to redundantly and energy-efficiently perform a request process in our previous studies. Since each application process is redundantly performed on more than one server, the larger amount of electric power is consumed. In this paper, we propose a novel and improved RPCLB (IRPCLB) algorithm to reduce the power consumption of servers, where once a process successfully terminates on one server, meaningless redundant processes are forced to terminate on the other servers. In the evaluation, we show the total power consumption of servers and total execution time of processes are reduced in homogeneous and heterogeneous types of clusters by the IRPCLB algorithm than the RPCLB and RR algorithms.     

Analysis of task assignment policies in scalable distributedweb-server systems

A distributed multiserver Web site can provide the scalability necessary to keep up with growing client demand at popular sites. Load balancing of these distributed Web-server systems, consisting of multiple, homogeneous Web servers for document retrieval and a Domain Name Server (DNS) for address resolution, opens interesting new problems. In this paper, we investigate the effects of using a more active DNS which, as an atypical centralized scheduler, applies some scheduling strategy in routing the requests to the most suitable Web server. Unlike traditional parallel/distributed systems in which a centralized scheduler has full control of the system, the DNS controls only a very small fraction of the requests reaching the multiserver Web site. This peculiarity, especially in the presence of highly skewed load, makes it very difficult to achieve acceptable load balancing and avoid overloading some Web servers. This paper adapts traditional scheduling algorithms to the DNS, proposes new policies, and examines their impact under different scenarios. Extensive simulation results show the advantage of strategies that make scheduling decisions on the basis of the domain that originates the client requests and limited server state information (e.g., whether a server is overloaded or not). An initially unexpected result is that using detailed server information, especially based on history, does not seem useful in predicting the future load and can often lead to degraded performance     

Web服务器集群系统的实现方法及负载管理

影响WWW网站应用的一个主要因素是用户请求的响应时间太慢,这严重影响了基于Internet的各项应用的发展。本文主要阐述了如何通过多个分布式的Web服务器结点来构筑Web服务器集群系统。文中详细说明了Web服务器集群系统的实现原理及方法,并讨论提出了实出其中各个服务结点之间负载平衡的一些基本技术及机制。     

集中管理式Web缓存系统及性能分析

共享缓存文件是减少网络通信量和服务器负载的重要方法，本文在介绍Web Caching技术及流行的Web缓存通信协议ICP的基础上，提出了一种集中管理式Web缓存系统，该系统通过将用户的HTTP请求，按照一定的算法分发到系统中某一合适的缓存服务器上，从而消除了缓存系统内部服务器之间庞大的通信开销及缓存处理负担，减少了缓存内容的冗余度．通过分析，证明了集中管理式Web缓存系统比基于ICP的简单缓存系统具有缓存效率高、处理开销低、延迟小等优点，并且该系统具有良好的可扩展性．     

Web服务器性能评测

Web服务器性能评测是一种理解Web服务器对不同负载反应能力的方法，它对Web服务器的容量规划和性能增强有很大的帮助。讨论了Web服务器性能评测的原理、方法、难点及解决方案，介绍了基于Web负载的特点、ON／OFF源模型及浏览器／服务器体系结构，开发了一个Web服务器性能评测工具－WSBench。WSBench产生渐近自相似的HTTP请求序列，从静态文档、动态文档（没有数据库存取）、动态文档（有数据库存取）及前三者根据Zipf法则的组合4个层次来评测Web服务器的性能。性能测试结果表现为每秒请求数、每秒字节数和往返时间3个指标。最后讨论了Web服务器性能问题及使用WSBench测得的指标来建议Web服务器性能增强可以采用的方法。     

Enforcing direct communications between clients and Web servers to improve proxy performance and security

The amount of dynamic Web contents and secured e‐commerce transactions has been dramatically increasing on the Internet, where proxy servers between clients and Web servers are commonly used for the purpose of sharing commonly accessed data and reducing Internet traffic. A significant and unnecessary Web access delay is caused by the overhead in proxy servers to process two types of accesses, namely dynamic Web contents and secured transactions, not only increasing response time, but also raising some security concerns. Conducting experiments on Squid proxy 2.3STABLE4, we have quantified the unnecessary processing overhead to show its significant impact on increased client access response times. We have also analyzed the technical difficulties in eliminating or reducing the processing overhead and the security loopholes based on the existing proxy structure. In order to address these performance and security concerns, we propose a simple but effective technique from the client side that adds a detector interfacing with a browser. With this detector, a standard browser, such as the Netscape/Mozilla, will have simple detective and scheduling functions, called a detective browser. Upon an Internet request from a user, the detective browser can immediately determine whether the requested content is dynamic or secured. If so, the browser will bypass the proxy and forward the request directly to the Web server; otherwise, the request will be processed through the proxy. We implemented a detective browser prototype in Mozilla version 0.9.7, and tested its functionality and effectiveness. Since we have simply moved the necessary detective functions from a proxy server to a browser, the detective browser introduces little overhead to Internet accessing, and our software can be patched to existing browsers easily. Copyright © 2004 John Wiley & Sons, Ltd.