Generating Initial Candidates

To avoid searching a complex space of resource combinations to achieve a given performance goal, Candidate follows a simple principle: build a balanced system. The allocator configures CPU and storage throughput ($\phi$) allotments around a predetermined average utilization level $\rho_{target}$. The $\rho_{target}$ may be set in a ``sweet spot'' range from 50-80% that balances efficient use of storage and CPU resources against queuing delays incurred at servers and storage units. The value for $\rho_{target}$ is a separate policy choice. Lower values for $\rho_{target}$ provide more ``headroom'' to absorb transient load bursts for the service, reducing the probability of violating SLA targets. The algorithm generalizes to independent $\rho_{target}$ values for each (service, resource)pair. ,

The Candidate algorithm consists of the following steps:

• Step 1. Predict CPU response time R_P at the configured $\rho_{target}$, as described in Section 3.4. Select initial $\phi = \mu_S$.

• Step 2. Using $\phi$ and $\rho_{target}$, predict storage response time R_S using Equation (4). Note that the allocator does not know $\lambda _S$at this stage, but it is not necessary because R_S depends only on $\phi$ and the ratio of $\lambda _S$/$\phi$, which is given by $\rho_{target}$.

• Step 3. Determine the required server memory hit ratio (H) to reach the SLA target response time R, using Equation (5) and solving for H as:
  

  $$H = 1 - \frac{R - R_P}{R_S}$$ (6)

  
  

• Step 4. Determine the storage arrival rate $\lambda _S$ from $\lambda$ and H, using Equation (2). Determine and assign the resulting candidate storage throughput allotment $\phi$ = $\lambda _S$/ $\rho_{target}$.

• Step 5. Loop to step 2 to recompute storage response time R_Swith the new value of $\phi$. Loop until the difference of $\phi$ values is within a preconfigured percentage of $\mu_S$.

• Step 6. Determine and assign the memory allotment M necessary to achieve the hit ratio H, using Equation (1).

  

Figure: Using Candidate and LocalAdjust to determine memory and storage allotments for a service. As service load ($\lambda$) increases, Candidate increases the storage share $\phi$ to meet response time targets. After encountering a resource constraint at $\phi = 200$ IOPS, LocalAdjust transforms the candidate allotments to stay on target by adding memory instead.

Note that the candidate M is the minimum required to meet the response time target. Given reasonable targets, Candidate leaves memory undercommitted. To illustrate, Figure 5 shows candidate storage and memory allotments $[M, \phi ]$for an example service as offered Web load $\lambda$increases along the x-axis. Candidate responds to increasing load by increasing $\phi$rather than M. This is because increasing $\lambda$ does not require a higher hit ratio H to meet a fixed response time target. For a fixed M and corresponding H, $\lambda _S$ grows linearly with $\lambda$, and so the storage allotment $\phi$ also grows linearly following $\lambda_S/\phi = \rho_{target}$.

Figure 5 also shows how the provisioning scheme adjusts the vectors to conform to a resource constraint. This example constrains $\phi$ to 200 IOPS, ultimately forcing the system to meet its targets by increasing the candidate M. Candidate itself does not consider resource constraints; the next two primitives adapt allotment vectors on a local or group basis to conform to resource constraints, or to allocate surplus resources to improve performance according to system-wide metrics.

  

Figure: Memory allotments by GroupAdjust for four competing services with different caching profiles (left) and different request arrival rates (right).