Strawman: Linear Search with Fixed $r$ and $t$

Common practice for finding the peak rate is to script a sequence of runs for a standard workload at a fixed linear sequence of escalating load levels, with a preconfigured runlength $r$ and number of trials $t$ for each load level. The algorithm is in essence a linear search for the peak rate: it starts at a default load level and increments the load level (e.g., arrival rate) by some fixed increment until it drives the server into saturation. The last load level $\lambda$ before saturation is taken as the peak rate $\lambda ^*$. We refer to this algorithm as strawman.

Figure 3: An efficient policy for finding peak rate converges quickly to a load factor near $1$, and reduces benchmarking cost by obtaining a high-confidence result only for the load factor of $1$. It is significantly less costly than the strawman policy: a linear search with a fixed runlength and fixed number of trials per test load.

Figure 4: Mean server response time at different test loads for the DB_TP fstress workload using $1$ disk and $4$ NFS daemon (nfsd) threads for the server. The variability in mean server response time for multiple trials increases with load. The results are representative of other server configurations and workloads.

Strawman is not efficient. If the increment is too small, then it requires many iterations to reach the peak rate. Its cost is also sensitive to the difference between the peak rate and the initial load level: more powerful server configurations take longer to benchmark. A larger increment can converge on the peak rate faster, but then the test may overshoot the peak rate and compromise accuracy. In addition, strawman misses opportunities to reduce cost by taking ``rough'' readings at low cost early in the search, and to incur only as much cost as necessary to obtain a statistically sound reading once the peak rate is found.

A simple workbench controller with feedback can improve significantly on the strawman approach to searching for the peak rate. To illustrate, Figure 3 depicts the search for $\lambda ^*$ for two policies conducting a sequence of experiments, with no concurrent testing. For strawman we use runlength $r$ = $5$ minutes, $t = 10$ trials, and a small increment to produce an accurate result. The figure compares strawman to an alternative that converges quickly on the peak rate using binary search, and that adapts $r$ and $t$ dynamically to balance accuracy, confidence, and cost during the search. The figure represents the sequence of actions taken by each policy with cumulative benchmarking time on the x-axis; the y-axis gives the load factor $\rho = \frac{\lambda}{\lambda^*}$ for each test load evaluated by the policies. The figure shows that strawman can incur a much higher benchmarking cost (time) to converge to the peak rate and complete the search with a final accurate reading at load factor $\rho = 1$. The strawman policy not only evaluates a large number of test loads with load factors that are not close to $1$, but also incurs unnecessary cost at each load.

The remainder of the paper discusses the improved controller policies in more detail, and their interactions with the outer loop in mapping response surfaces.