Reliable Storage - Operating Systems: Principles and Practice - page 430

Disk 0 Disk 1 Disk 2 Disk 3 Disk 4

Strip (0,0) Strip (1,0) Strip (2,0) Strip (3,0) Strip (4,0)

Parity (0,0,0)
Parity (1,0,0)
Parity (2,0,0)
Parity (3,0,0)

Data Block 0
Data Block 1
Data Block 2
Data Block 3

Data Block 4
Data Block 5
Data Block 6

Data Block 8
Data Block 9
Data Block 10
Data Block 11

Data Block 12
Data Block 13
Data Block 14
Data Block 15

Stripe 0

Data Block 7

Strip (0,1) Strip (1,1) Strip (2,1) Strip (3,1) Strip (4,1)

Data Block 16
Data Block 17
Data Block 18
Data Block 19

Parity (0,1,1)
Parity (1,1,1)
Parity (2,1,1)
Parity (3,1,1)

Data Block 20
Data Block 21
Data Block 22
Data Block 23

Data Block 24
Data Block 25
Data Block 26
Data Block 27

Data Block 28
Data Block 29
Data Block 30
Data Block 31

Stripe 1

Strip (0,2) Strip (1,2) Strip (2,2) Strip (3,2) Strip (4,2)

Data Block 32
Data Block 33
Data Block 34
Data Block 35

Data Block 36
Data Block 37
Data Block 38
Data Block 39

Parity (0,2,2)
Parity (1,2,2)
Parity (2,2,2)
Parity (3,2,2)

Data Block 40
Data Block 41
Data Block 42
Data Block 43

Data Block 44
Data Block 45
Data Block 46
Data Block 46

Stripe 2

Figure14.6: RAID 5 with rotating parity.

Rotating parity. In RAIDs with rotating parity (also called RAID 5 ),

),Definition: rotating parity
Definition: RAID 5 the system reduces replication overheads by storing several blocks of data

on several disks and protecting those blocks with one redundant block
stored on yet another disk as Figure 14.6 illustrates.
In particular, this approach uses groups of G disks, and writes each of
G 1 blocks of data to a dierent disk and 1 block of parity to the
remaining disk. Each bit of the parity block is produced by computing
the exclusive-or of the corresponding bits of the data blocks:

parity = data 0 data 1 :::data G1

If one of the disks suffers a sector or whole-disk failure, lost data blocks
can be reconstructed using the corresponding data and parity blocks from
the other disks. Note that because the system already knows which disk
has failed, parity is sucient for error correction, not just error detection.
For example, if the disk containing block data 0 fails, the block can be
constructed by computing the exclusive-or of the parity block and the
remaining data blocks:

data 0 = paritydata 1 :::data G1

To maximize performance, rotating parity RAIDs carefully organize their
data layout by rotating parity and striping data to balance parallelism
and sequential access: