Search Algorithm

Our approach uses Algorithm 2 to search for the peak rate for a given setting of factors.

Algorithm 2 takes various parameters to define the conditions for the reported peak rate:

• $R_{sat}$, a threshold on the mean server response time. The server is considered to be saturated if mean response time exceeds this threshold, i.e., $\bar{R} > R_{sat}$.

• $P_{sat}$ and $L_{sat}$ defining a threshold on percentile server response time. The server is considered to be saturated if the $P_{sat}$ percentile response time exceeds $L_{sat}$. For example, if $P_{sat}=0.95$ then the server is saturated if no more than 95% of responses show latency at or below $L_{sat}$. To simplify the presentation we use the $R_{sat}$ threshold test on mean response time and do not discuss $P_{sat}$ further.

• Width parameter $s$ defining the peak-rate region $[R_{sat} \pm sR_{sat}]$. The reported peak rate $\lambda ^*$ can be any test load level that drives the mean server response time into this region. (The region $[P_{sat} \pm sP_{sat}]$ is defined similarly.)

• Target confidence $c$ in the peak rate that the algorithm estimates.

• Target accuracy $a$ of the peak rate that the algorithm estimates.

Algorithm 2 chooses (a) a sequence of test loads to try; (b) the number of independent trials at any test load; and (c) the runlength of the workload at that load. It automatically adapts the number of trials at any test load according to the load factor and the desired target confidence and accuracy. At each load level the algorithm conducts a small (often the minimum of two in our experiments) number of trials to establish with $95$% confidence that the current test load is not the peak rate (Step $10$). However, as soon as the algorithm identifies a test load $\lambda$ to be a potential peak rate, which happens near a load factor of $1$, it spends just enough time to check whether it is in fact the peak rate.

More specifically, for each test load $\lambda _{cur}$, Algorithm 2 first conducts two trials to generate an initial confidence interval for $\bar{R}_{\lambda_{cur}}$, the mean server response time at load $\lambda _{cur}$, at $95$% confidence level. (Steps $6$ and $7$ in Algorithm 2.) Next, it checks if the confidence interval overlaps with the specified peak-rate region (Step $9$).

If the regions overlap, then Algorithm 2 identifies the current test load $\lambda _{cur}$ as an estimate of a potential peak rate with 95% confidence. It then computes the accuracy of the mean server response time $\bar{R}_{\lambda_{cur}}$ at the current test load, at the target confidence level $c$ (Section 2.1). If it reaches the target accuracy $a$, then the algorithm terminates (Step $4$), otherwise it conducts more trials at the current test load (Step $6$) to narrow the confidence interval, and repeats the threshold condition test. Thus the cost of the algorithm varies with the target confidence and accuracy.

If there is no overlap (Step $10$), then Algorithm 2 moves on to the next test load. It uses any of several load-picking algorithms to generate the sequence of test loads, described in the rest of this section. All load-picking algorithms take as input the set of past test loads and their results. The output becomes the next test load in Algorithm 2. For example, Algorithm 3 gives a load-picking algorithm using a simple binary search.

To simplify the choice of runlength for each experiment at a test load (Step 5), Algorithm 2 uses the ``sweet spot'' derived from Figure 6 (Section 3.2). The figure shows that for all workloads that this paper considers, a runlength of $3$ minutes is the sweet spot for the minimum number of trials.