Check out the new USENIX Web site. next up previous
Next: Group Constraint or Surplus Up: A Model-Based Allocator Previous: Generating Initial Candidates

Local Constraint or Surplus

The input to LocalAdjust is a candidate allotment vector and request arrival rate $\lambda $, together with specified constraints on each resource. The output of LocalAdjust is an adjusted vector that achieves a predicted average-case response time as close as possible to the target, while conforming to the resource constraints. Since this paper focuses primarily on memory and storage resources, we ignore CPU constraints. Specifically, we assume that the expected CPU response time RP for a given $\rho_{target}$is fixed and achievable. CPU allotments are relatively straightforward because memory and storage allotments affect per-request CPU demand only minimally. For example, if the CPU is the bottleneck, then the allotments for other resources are easy to determine: set $\lambda $ to the saturation request throughput rate, and provision other resources as before.

If the storage constraint falls below the candidate storage allotment $\phi $, then LocalAdjust assigns the maximum value to $\phi $, and rebalances the system by expanding the memory allotment M to meet the response time target given the lower allowable request rate $\lambda _S$ for storage. Determine the allowable $\lambda_{S} = \phi \rho_{target}$ at the preconfigured $\rho_{target}$. Determine the hit ratio H needed to achieve this $\lambda _S$ using Equation (2), and the memory allotment M to achieve H using Equation (1).

Figure 5 illustrates the effect of LocalAdjust on the candidate vector under a storage constraint at $\phi = 200$ IOPS. As load $\lambda $ increases, LocalAdjust meets the response time target by holding $\phi $to the maximum and growing M instead. The candidate M varies in a (slightly) nonlinear fashion because H grows as M increases, so larger shares of the increases to $\lambda $ are absorbed by the cache. This effect is partially offset by the dynamics of Web content caching captured in Equation (1): due to the nature of Zipf distributions, H grows logarithmically with M, requiring larger marginal increases to M to effect the same improvement in H.

If memory is constrained, LocalAdjust sets M to the maximum and rebalances the system by expanding $\phi $ (if possible). The algorithm is as follows: determine H and $\lambda _S$ at M using Equations (1) and (2), and use $\lambda _S$ to determine the adjusted storage allotment as $\phi = \lambda_{S}/\rho_{target}$. Then compensate for the reduced H by increasing $\phi $ further to reduce storage utilization levels below $\rho_{target}$, improving the storage response time RS.

If both $\phi $ and M are constrained, assign both to their maximum values and report the predicted response time using the models in the obvious fashion. LocalAdjust adjusts allotments to consume a local surplus in the same way. This may be useful if the service is the only load component assigned to some server or set of servers. Surplus assignment is more interesting when the system must distribute resources among multiple competing services, as described below.


next up previous
Next: Group Constraint or Surplus Up: A Model-Based Allocator Previous: Generating Initial Candidates
Ronald Doyle
2003-01-20