2.3 Reducing Both Seek and Rotational Delay

In the previous sections, we have discussed existing techniques for reducing seek distance and rotational delay in isolation. Their combined effects, however, are not well understood. We now develop models that predict the overall latency as we increase the number of disks.

SR-Array: Combining Striping and Rotational Replication
 

Since disk striping reduces seek distance and rotational replication reduces rotational delay, we can combine the two techniques to reduce overall latency. We call the resulting configuration an SR-Array. Figure 3 shows an example SR-Array. In an SR-Array, we perform rotational replication on the same disk. We explore rotational replication on different disks in a later section.

  

Figure 3: Reducing both seek and rotational delay in an SR-Array. (a) Data on an original disk is divided into six parts. (b) A $3 \times 2$ SR-Array. Each disk holds only one sixth of the original data. The two rotational replicas for each block ensure that the maximum rotational delay for any data is half of a full rotation. (Two times the number of disks are needed to support two-way rotational replication; this is shown in the vertical dimension.) The rotational replicas expand the seek distance between different data blocks so the maximum seek distance on each of these six disks is the same as that in a simple three-way striped system (denoted by the three disks in the horizontal dimension).

Given a fixed budget of D disks, we would now like to answer the following question: what degree of striping and what degree of rotational replication should we use for the best resulting performance? We call this the ``aspect ratio'' question. We first consider this question for random access latency, and then we examine how the model can be extended to take into account other workload parameters.

Read Latency on an SR-Array

In this paper, we define overhead to include various processing times, transfer costs, track switch time, and mechanical acceleration/deceleration times. We focus on the overhead-independent part of the latency in the following analysis.

Let us assume that we have a single disk's worth of data, and we have a total of D disks. Suppose the maximum seek time on one disk is S, the time for a full rotation is R, only 1/D_s of the cylinders on a single disk is used to limit the seek distance, and D_r is the number of replicas for reducing rotational delay ( D_s D_r = D). If D_r=1, an SR-Array degenerates to simple striping and only 1/D of the available space is used. If D_s=1, we use all the available space. In Figure 3, D_s = 3 and D_r = 2.

Because the random read latency is the sum of the overhead, the average seek time, and the average rotational time, we can approximate the overhead-independent part of random read latency T_R(D_s,D_r) as:

$$T_R(D_s,D_r) = \frac{S}{3 D_s} + \frac{R}{2 D_r}$$ (4)

Given the constraint of D_s D_r = D, we can prove that the following configuration produces the best overall latency for independent random I/Os under low load:

$$\left\{ \begin{array}{c} D_s = \sqrt{\frac{2 S}{3 R} D}\\ D_r = \sqrt{\frac{3 R}{2 S} D} \end{array}\right.$$ (5)

The overhead-independent part of latency under this configuration is therefore:

$$T_{best} = \sqrt{\frac{2 S R}{3 D}}$$ (6)

It is likely that the optimal D_s and D_r are not integer values. For such scenarios, we choose D_r to be the maximum integer factor of Dthat is less than or equal to the optimal non-integer value.

Disks with slow rotational speed (large R) demand a higher degree of rotational replication. In terms of the SR-Array illustration of Figure 3(b), this argues for a tall thin grid. Conversely, disks with poor seek characteristics (large S) demand a large striping factor. In terms of Figure 3(b), this argues for a short fat grid. The model indicates that the latency improvement on an SR-Array is proportional to the square root of the number of disks ($\sqrt{D}$).

So far, our discussion of the model applies to random access by assuming an average seek of S/3 in Equation (6). To capture seek locality, we replace S/3 with the average seek of a workload. In the later experimental sections, this is accomplished by dividing S/3 with a ``seek locality index'' (L), which is observed from the workload. The model does not directly account for sequential access.

Read/Write Latency on an SR-Array

Now we extend the latency model of an SR-Array to model the performance of both read and write operations. When performing a write, in the worst case scenario of not being able to mask the cost of replica propagation, we must incur a write latency of T_W(D_s,D_r):

$$T_W(D_s,D_r) = \frac{S}{3 D_s} + R - \frac{R}{2 D_r}$$ (7)

Let the number of reads be X_r, the number of writes that can be propagated in the background be X_wb, and the number of writes that are propagated in the foreground be X_wf. We define the ratio p:

$$p = \frac{X_r + X_{wb}}{X_r + X_{wb} + X_{wf}}$$ (8)

The average read/write latency, T(D_s,D_r)=p T_R + (1-p) T_W, can be expressed as:

$$T(D_s,D_r) = \frac{S}{3D_s} + p \frac{R}{2 D_r} + (1-p)(R - \frac{R}{2 D_r})$$ (9)

The first term is the average seek incurred by any request. The second term is the average rotational delay consumed by I/O operations that do not result in foreground replica propagation (based on Equation (2)) with probability p; and the third term is the rotational delay consumed by writes whose replicas are propagated in the foreground due to lack of idle time (based on Equation (3)) with probability 1-p. We can prove that the following configuration provides the best overall latency:

$$\left\{ \begin{array}{c} D_s = \sqrt{\frac{2 S}{3 R (2p-1)} D}\\ D_r = \sqrt{\frac{3 R (2p-1)}{2 S} D} \end{array}\right.$$ (10)

The latency under this configuration is:

$$T_{best} = \sqrt{\frac{2 S R (2p-1)}{3 D}} + (1-p)R$$ (11)

A low p ratio calls for a short fat grid in Figure 3(b). A p ratio under 50% precludes rotational replication and pure striping provides the best configuration. In the best case, when all write replicas can be propagated in the background (or when we have no writes at all), writes and reads become indistinguishable as far as this model is concerned, so p approaches 1 and the latency improvement is proportional to $\sqrt{D}$.