2003-01-16 16:35:32

by Ezra Nugroho

[permalink] [raw]
Subject: raid 5 algorithm docs

I don't know if linux-raid mailing list is still active, the archive
sites look very old...

So, to raid developers in this mailing list,

Is there any documentation out there about the different raid 5 syncing
algorithm?
Raidtab's man page tells about left/right (a)synchronous algorithm, but
doesn't tell how they differ.
I couldn't find any howto pages that explain this either.





2003-01-16 19:40:05

by Paul Clements

[permalink] [raw]
Subject: Re: raid 5 algorithm docs

On 16 Jan 2003, Ezra Nugroho wrote:

> I don't know if linux-raid mailing list is still active, the archive
> sites look very old...

Yes, linux-raid is still alive and kicking...
it's at: [email protected]

> Raidtab's man page tells about left/right (a)synchronous algorithm, but
> doesn't tell how they differ.

I haven't seen much documentation either, but here's what I got from
looking at the code (BTW, the relevant section of code is
raid5.c:raid5_compute_sector(), if you're curious):

Basically, the left/right refers to how the parity information is laid
out and the symmetric/asymmetric refers to how the data is laid out.

The "left" algorithms start with parity on the last disk, moving the
parity one disk closer to the first disk for each stripe (wrapping
as necessary). The "right" algorithms do just the opposite, starting
with parity on the first disk, moving it one disk closer to the last
disk for each stripe (wrapping as necessary).

The "asymmetric" algorithms place the data blocks for a given stripe in
simple sequential order, skipping over the parity block as necessary
and always starting with the first data block of a stripe on the
first disk. The "symmetric" algorithms differ from this in that they
do not always place the first block of a stripe on the first disk,
but continue to lay out the data blocks in sequential disk order,
simply wrapping back to the first disk when it's necessary.
So the symmetric algorithms tend to give better performance on large
sequential reads, for example, since the actual disk reads are
evenly spread across all disks.

There's a pretty good diagram of the left-symmetric disk layout here:
http://www.pdl.cmu.edu/PDL-FTP/Declustering/ASPLOS.ps (see figure 2-1)

--
Paul Clements
[email protected]