2.1 Reducing Seek Distance

  

Figure 1: Techniques for reducing seek distance. Capital letters represent a portion of the data. To the left of the arrows, we show how data is (logically) stored on a single disk. To the right, we show different ways that data on the single disk can be distributed on two disks (D=2): (a) D-way mirroring, and (b) D-way striping.

We start by defining the following abstract problem: suppose the maximum seek distance on a single disk is S, the total amount of data fits on a single disk, and accesses are uniformly distributed across the data set. Then, how can we effectively employ D disks to reduce the average seek latency? We use seek distance to simplify our presentation. (Seek latency is approximately a linear function of seek distance only for long seeks [22].) As a base case, one can show that the average seek distance for reads on a single disk [24] is S₁ = S/3.

The first seek reduction technique is D-way mirroring (shown in Figure 1(a)). D-way mirroring can reduce seek distance because we can choose the disk head that is closest to the target sector in terms of seek distance. With D disks, the average seek distance is the average of the minimum of D random variables [3], which is S/(2D+1).

The second technique is striping (and keeping disks partially empty). Figure 1(b) illustrates a two-way striping. Data on the original single disk is partitioned into two disjoint sets: B and C. We store B on the outer edge of the first disk and C on the outer edge of the second disk. The space in the middle of these two disks is not used. In this case, the single large disk is in effect split into two smaller disks. As a result, the disk head movement is restricted to a smaller region. Assuming constant track capacity and uniform accesses, Matloff [17] gives the average seek distance of a D-way stripe (S_s):

$$S_s(D) = \frac{S}{3D}$$ (1)

The amount of seek reduction achieved by striping is better than that of D-way mirroring. However, D-way mirroring provides reliability through the use of multiple copies. A hybrid scheme would provide reliability along with smaller seek latencies. RAID-10, widely used in practice, is a concrete example of such a hybrid scheme: in a RAID-10 system, data is striped across D_s disks while each block is also replicated on D_m different disks.