CSE646 Final Project Design Report

QoS Support for Web Server Clusters

 

Chang Li          Jinshan Liu

1. Goal

 

The goal of our project is to implement a guaranteed quality of service system on web server clusters. Most of current web server systems only provide differentiated service, i.e. prioritization among different customers. We attempt to support guaranteed number of “normal sized” requests per second for each customer. 

 

We determine the “size” of a request by comparing its servicing time with the typical request servicing time on our servers. A request is considered to be “normal sized” only if its servicing time falls into a certain range. This is a simple approximation of server resource used by the request.

 

2. Assumptions

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Design

3.1 Front-end components
 
 

 

 

 

 

 

 

 

Whenever a HTTP request is accepted by the front-end server, it first goes through the classifier. The responsibility of the classifier is to classify an incoming HTTP request according to its target domain name, i.e., it decides which  customer this request belongs to.  A classified request will be added to the request queue of the corresponding customer.

Classification has two steps:

1. HTTP request parsing: locate the URL from a HTTP request, and then extract the domain name from the URL.

2. Hash table lookup: Domain name is the key of our hash table; the lookup procedure will return a pointer to the corresponding customer queue.

 

Scheduler will decide the order in which the requests are dispatched to back-end servers.  It may also decide to reject a request when necessary for the sack of overload protection.

Since we want to provide guaranteed number of request per second service, the scheduler will schedule the requests according to QoS requirement and current server time usage of each customer. If a customer has used up its reservation in the current time cycle, its requests will be delayed.

Consider the following situation: customer A wants 500 requests per second, customer B wants 100 requests per second, our typical request service time is 20ms, and we have 5 back-end servers, each of which processes 5 requests concurrently. Since the 10 back-end servers service requests in a parallel manner, in each second, our web server cluster can service (1000/20)*5*5=1250 requests. This is much greater than the sum of customer requirements. The scheduler will guarantee that at least 500 “normal sized” requests from the queue A and at least 100 “normal sized” requests from the queue B will be dispatched to back-end servers per second. In the spare time, it may use other scheduling strategy such as FIFO or round robin.

Now suppose we have two more customers: customer C and D want 400 and 150 requests per second respectively. Now the sum of requirements is near to our total ability. The scheduler has to carefully compute the available service time of each customer and make sure every customer is satisfied.

A problem is how do we know a request is “normal sized” or not. Since we want to keep the front-end simple and efficient, we do not want to maintain such information on the front-end. So it’s the responsibility of back-end servers to feedback service time information of each request. This means the front-end server doesn’t know the service time of a request when it dispatches it. We will discuss this in detail in next section.

 

The responsibility of dispatcher is to maintain load balance among the back-end servers. For now, we assume that the cost of a certain request remains the same on each back-end server. This is a simplification allowing us to focus on the QoS part of web server clusters.

The dispatcher will dispatch requests according to load level of each back-end server. The goal is to make the back-end servers evenly loaded. We measure the load of a back-end server by the number of concurrent requests being processed. Each time, the request is dispatched to the server with smallest number of requests.

 

 

3.2 Information feedback

 

Now the question is how the front-end server will get the information it needs to make the scheduling or dispatching decisions. Such information includes: how much server time a particular request has consumed and the current loading level of each back-end server.

 

It’s each back-end server’s responsibility to provide such information to front-end server. So in each back-end server, we will insert a software module to monitor request numbers and elapse time of each request.

 
 
 


 

 

 

 

 

 

 

 

 

 

 

 

3.3 Splicing support

 

Now let’s consider the scalability of this system. The work of back-end servers is well distributed, but the front-end server has central control over the whole system. As the number of back-end server increases, we do not want the front-end server becomes a bottleneck. We try to avoid this by inserting splicing support into both front-end and back-end.

 

When the client wanted to send a request, it first established a TCP connection C1 with the front-end server.  Only after the front-end server received the HTTP request, it can extract the URL and then do classification. When the request is dispatched, another TCP connection C2 is established. The selected back-end server will receive the request from C2 and send back the requested page to C2. Splicing is a mechanism to combine these two connections as if there is only one connection between the client and the selected back-end server. Previous splicing implementations splice the two connections at the front-end, which does no good to the scalability. In our implementation, splicing of request-direction remains on the front-end server, but the response-direction part is moved to each back-end server. Thus the traffic from back-end servers to clients will not go through front-end server. Since main part of total traffic goes in this direction, the work load of front-end server is greatly relieved. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


In both front-end server and back-end servers, the splicing support is implemented in a sub-layer between IP and Ethernet driver.

 

 

 

 

 

 

 

 

 

 


3.4 Communication between front-end and back-end

 

We will implement our own communication protocol between front-end server and back-end servers. Four types of messages will be exchanged:

 

  1. Register message, while initialization, each back-end server will register to the front-end server, telling its hardware address and other useful information.
  2. Splicing message, including information needed to map a pair of connections (client IP, client port, ID of selected BS, and so on) and information needed to splice the two connections (such as initial sequence number of each connection).
  3. Feedback message, including the service time of each request and number of concurrence requests being serviced at a back-end server.
  4. Keep alive message, enabling the front-end server to detect failure of a back-end server. Front-end server will maintain a timer for each registered back-end server. If a timer timeout before a keep-alive message is received from the corresponding back-end server, front-end server will try to reconnect to the back-end server. If it still failed, front-end server will decide that this back-end server is out of service and then delete it from the back-end server list. If some time later, the back-end server goes up again, it will re-register to the front-end server.

 

When a failure occurred, front-end server has to re-compute the number of requests serviced for each customer, because some of the requests dispatched to the failed back-end server may never be served.

 

4. Important Issues

4.1 Scheduling algorithm

 

We use a cycle time of about 10ms for our scheduling algorithm. At the beginning of each cycle, we deposit some credits(number of requests the customer deserved in this cycle) to each customer according to our contract with the customer. The credits are added to the customer’s current balance. Whenever a request of this customer is dispatched, we decrease the balance by one. If the request consumes double the typical sever time, we decrease another one from the balance. A customer may have a negative balance at the beginning of a cycle if in the previous cycles, some “big” request consumed too much credits.   The scheduler will visit each queue in a round robin manner, but only the requests in a queue with positive balance will be dispatched. Only when every queue is empty or has a negative balance, the schedule will consider of dispatching requests from negative-balance queues.

 

While dispatching a request, the scheduler will assume that it’s a normal sized request, i.e., it will not cost more than 20ms server time. After the feedback information of this request comes back from a back-end server, the scheduler will update its request count if necessary. For example, it the back-end server reports that a certain request used 40ms; the scheduler will consider it as two requests.

 

4.2 Concurrency vs. accurate scheduling

 

The scheduler doesn’t know how much time a request will take before the request is serviced. Although for a long term, the scheduler will meet requirements of each customer, there is possibility of inaccurate scheduling for some period of time. Imagine a consecutive sequence of big requests of a certain customer. The scheduler will consider them as normal requests and may dispatch all of them to meet this customers QoS requirement. While since these request are so big, that they may use much more than the customer’s share. As a result, normal requests of other customers cannot be served.

 

This can be relieved by putting a limitation on number of requests being processed on the back-end servers. The less number of requests dispatched during a cycle, the less mistake the scheduler can make. But smaller number of requests being processed means less concurrency at back-end servers. We need to find a balance between them.

 

4.3 Resource usage information

 

The elapse time of a request we are using is not an accurate measurement of server resource usage. Since each back-end server is a concurrent web server. The process serving a request may be put into a waiting queue by the operating system, while the process of some other request is running. Without cooperation of web server software or the operating system, we cannot get accurate information about exactly how much CPU time, IO time a request costs. But we will try to find some way to make our approximation more accurate. One possibility is to get the current average process sleeping time from the O.S. and subtract it from the elapse time of each request. We will do some more research along this line.

 

5.  Related works

 

Other work about differentiated services on the web server has been carried on around the world. Extensions of differentiated services have been proposed at the application-, kernel- and network layer.

 

Almeida et al have designed several application-level and kernel approaches to web QoS. Their first application-level mechanism limits the server pool sizes allocated to requests of different classes. The second mechanism they have implemented is a kernel level-scheduler that allows preemption of low-level requests and assigns process priorities based on the request class. While they confirm that simple application-level mechanisms (such as a limited pool of servers) are effective, they claim that under heavy load, kernel-level preemption mechanisms are needed to improve performance.

 

Several soft-realtime kernel extensions to give applications more control about scheduling and resources allocation have been proposed. AQUA [Lakshman et al. 1998] is a kernel-level framework that allows cooperating multimedia applications to dynamically negotiate their CPU and network I/O requirements with the kernel. If a resource becomes congested, applications are notified by AQUA and may adapt to the new service environment. Unfortunately, it requires kernel changes and does not address non-allocated bottlenecks. OMEGA [Nahrstedt and smith 1986] is an end-system kernel framework that supports soft-realtime scheduling of CPU, memory and network resource allocation to provide end-to-end QoS. OMEGA is similar to AQUA; applications dynamically negotiate their resource requirements with a QoS broker. Another approach is the scheduling of web server worker processes with the same priority as the request. This ensures that the higher priority requests are executed first once they are assigned to a worker process. Resource Container [Gaurav and Peter 1999] is used to account for and control consumption of operating system resources by different classes of requests. This Operating system control mechanism has been shown to ensure class-based performance in web servers.

 

Application-level mechanisms cannot directly control what happens to their traffic inside the network. Network-layer mechanisms could be used to improve application-level backgrounding mechanisms. At the network-layer, several proposals have been made to accommodate different levels of service. One such proposal is to extend IP for integrated services [Wroclawski 1997]. In this scheme, receivers initiate a resource reservation request to receive a guaranteed service commitment with the Resource Reservation Protocol (RSVP) [Zhang et al. 1993. A second proposal is to extend IP to support differentiated services [Blake et al. 1998]. This approach allows high priority traffic to take precedence over existing traffic on a per-packet basis. Compliant routers will respect priorities in their queuing and forwarding decisions.

 

Ultimately the network and end system OS are the best places to provide differentiated services. A router can react to traffic requirements directly, and the end system OS has better means of enforcing QoS than non-privileged applications. Deployment of these mechanisms is difficult since many routers must support these protocols for the system to become effective. 

 

External devices such as intelligent switches or routers can be placed in front of a web server to intercept web traffic. Alteon, Packeteer, and Local director switch products can be configured perform request aware traffic shaping. Typically, these devices are used as load balancers for a cluster of web servers. Other switches can differentiate performance based on application type using admission control and bandwidth reservation.