Reliable and Fault-Tolerant Storage Systems - Scalable Continuous Media Streaming Systems - page 100

in pipelined rebuild as soon as a track is retrieved from each of the ( N D − 1) surviving disks,

the server will reconstruct the lost track and store it to the spare disk immediately. In this way,
the track reading and writing processes operate simultaneously in a pipelined manner.
Under this pipelined rebuild algorithm, the rebuild buffer requirement is reduced to

B r = ( N D − 1) SY max + SY max (5.37)

where the first term is the buffer required for reading and the second term is the buffer required
for writing.
However, the scenario in Figure 5.6 is idealized with the assumption that track retrievals
for all surviving disks complete at the same instant. In practice, this is unlikely to be the case
due to variations in disk rotational latencies incurred in reading media blocks prior to reading
the rebuild tracks. To account for this disk asynchrony, we introduce a deviation bound D syn
defined as the maximum difference between the time the first track retrieval completes and the
time the last track retrieval completes.
Mathematically, let t i , j be the retrieval completion time for reading rebuild track i , i =

0 1), as shown in Figure 5.7. We define a track

group as the set of corresponding tracks from all ( N D −

, 1 ,..., N trk , by disk j , j = 0 , 1 ,..., ( N D −

1) surviving disks that forms a parity
group. For example, track group i comprises track i from each of the ( N D − 1) disks.

Let e i and l i be the earliest completion time and latest completion time respectively for track
group i :

e i = min { t i , j |∀ j } and l i = max { t i , j |∀ j } (5.38)

Then D asyn can be computed from

D asyn = max { l i − e i |∀ i } (5.39)

Figure 5.7 A snapshot of track retrievals at time t = l i with disk asynchrony