Check out the new USENIX Web site. next up previous
Next: Storage I/O Rate Up: Web Service Models Previous: Web Service Models

   
Server Memory

Many studies indicate that requests to static Web objects follow a Zipf-like popularity distribution [11,38]. The probability px of a request to the xth most popular object is proportional to $1/x^\alpha$, for some parameter $\alpha$. Many requests target the most popular objects, but the distribution has a heavy tail of unpopular objects with poor reference locality. Higher $\alpha$ values increase the concentration of requests on the most popular objects. We assume that object size is independent of popularity [11], and that size distributions are stable for each service [35].

Given these assumptions, a utility OS can estimate hit ratio for a memory size M from two parameters: $\alpha$, and T, the total size of the service's data (consider M and T to be in units of objects). If the server effectively caches the most popular objects (i.e., assuming perfect Least Frequently Used or LFU replacement), and ignoring object updates, the predicted object hit ratio H is given by the portion of the Zipf-distributed probability mass that is concentrated in the M most popular objects. We can closely approximate this H by integrating over a continuous form of the Zipf probability distribution function [11,38]. The closed form solution reduces to:


\begin{displaymath}H = \frac{1-M^{1-\alpha}}{1 -T^{1-\alpha}}
\end{displaymath} (1)

Zipf distributions appear to be common in a large number of settings, so this model is more generally applicable. While pure LFU replacement is difficult to implement, a large body of Web caching research has yielded replacement algorithms that approximate LFU; even poor schemes such as LRU are qualitatively similar in their behavior.


 
Table 2: Performance measures predicted by Web models.
Parameter Meaning
RP CPU response time
H Object cache hit ratio
$\lambda _S$ Storage request load in IOPS
RS Average storage response time
R Average total response time
 


next up previous
Next: Storage I/O Rate Up: Web Service Models Previous: Web Service Models
Ronald Doyle
2003-01-20