counter stats

Capacity Planning for Server Farms:
How many servers are optimal?

 

People

Adam Wierman
Takayuki Osogami
Mor Harchol-Balter
Alan Scheller-Wolf

Figure 1.  An diagram of a multiserver priority queue.
 
Motivation

A fundamental design decision in server farms is whether to use a large number of slow servers or a few fast servers.  This question is difficult to answer even when arriving jobs are scheduled using the simplest policy: First Come First Served (FCFS). However, more commonly, jobs have different priority levels, e.g. High/Low, and jobs with higher priority levels are allowed to serve first. The analysis of these multiserver priority queues is a long standing open problem. The difficulty is that the Markov chain underlying the model of this system is infinite in m-dimensions when there are m priority classes, and while one-dimensionally infinite Markov chains with repeating structure are analytically tractable, two (and higher) dimensionally infinite Markov chains are typically not.

Figure 2.  A diagram illustrating the optimal server configuration (given a fixed total service capacity) for high and low priority customers in a dual priority server farm as a function of the load and variability of the workload.  Notice that low priority customers always prefer to have more servers than high priority customers.
 
Results

We provide the first near-exact analysis of the m-class priority queue with k servers under general (phase-type) job sizes. The analysis uses a new technique called Recursive Dimensionality Reduction (RDR), which serves to recursively use the solution to an n−1 dimensional Markov chain in order to solve an n dimensional Markov chain.  Though the technique is approximate, it can be made as accurate as desired. Using this new analysis, we address (for the first time) important design questions about how prioritization behaves in server farm architectures, e.g. “how does the impact of prioritization in multiserver systems compare to that in single server systems?” Further, we provide a detailed exploration of the question of how many servers are optimal given a fixed total service capacity.


Impact

In addition to its usefulness in studying multiserver systems, RDR has turned out to be useful in many other application domains, and has led to more than a dozen papers from our research group at Carnegie Mellon.  The papers study a wide variety of different multiserver systems including: cycle stealing and task assignment.  You can find a  thorough summary in Taka's thesis.


Publications