[Linux-cluster] Announce: Higher level cluster raid

[Daniel Phillips]

Hi all,

A number of participants on this list have speculated about the 
possibility of running higher level raid on a cluster, to provide lower 
redundancy and greater throughput than simple cluster mirroring.  This 
is a natural idea, and I am pleased to be able to say that it is now a 
reality here on my workbench.

This project started life as a cluster mirror back before Jon decided to 
try extending the existing dm-raid1 driver to work on a cluster.  It 
got mothballed at that time, but luckily I had already promised a 
cluster raid paper for LCA next month.  With that deadline looming, I 
unmothballed it and went to work.  To add spice, I thought I would try 
to extend it to a higher raid level.

Well, raid 5 is really hard to implement under the best of conditions, 
but on a cluster it gets really crazy due to caching issues[1].  Raid 2 
and 3 are generally considered impractical to implement in software 
because of the necessary per-byte parity handling.  Fortunately, there 
is a variant I investigated a couple of years ago and published a paper 
on, that I call raid 3.5.  This approach restricts the number of disks 
in an array to 2**k+1 and divides each filesystem block into a binary 
number of fragments which are striped across the array.  You can think 
of this as sub-block striping, as opposed to raid 4 and 5 which use 
multi-block striping.  The big advantage of raid 3.5 over raid 4 or 5 
is that each parity block does not tie together multiple data blocks, 
so caching can be avoided.  Each data block can be written directly to 
or read directly from the array, along with its associated parity.

Here is a nice picture of how raid 3 works:

   http://www.acnc.com/04_01_03.html

Raid 3.5 is much like that, except for the way data blocks are striped 
across disks, which is designed to make it easy to implement in 
software.

On a single node, the main attraction of raid 3.5 is, it is much easier 
to implement than raid 4 or 5.  However, on a cluster raid 3.5 really 
comes into its own: decoupling the parity blocks from unrelated data 
blocks is a fundamental advantage.  Per-block synchronization becomes 
unnecessary, which would otherwise be complex and costly.  More 
importantly, there is no need to read other blocks of a parity set 
before updating, which would create a horrible new level of data 
caching and cluster synchronization issues.

The main theoretical disadvantage of raid 3.5 versus raid 5 is lower 
transaction throughput, because each filesystem transaction involves 
all disks of the array, whereas raid 5 can sometimes seek in parallel 
for parallel filesystem transactions.  This problem disappears on a 
cluster  because you can fill each cluster data node with many disks 
and stripe them together, yielding the same transaction parallelization 
characteristics as raid 4 or 5.

Another disadvantage of raid 3.5 is the limited number of supported 
array configurations.  Each 4K filesystem block can only be divided 
into eight pieces before hitting the 512 byte Linux sector addressing 
limit.  This means that for practical purposes, raid 3.5 can only have 
3, 5 or 9 members[2].  Well, that is not a big problem when you 
consider that, until now, you could not do cluster level data 
redundancy at all, other than mirroring.

Now to put this in perspective.  The availability of higher level 
cluster raid gives us a new type of cluster, a "distributed data" 
cluster, as opposed to what GFS currently offers, which I call a 
"shared data" cluster.  With a distributed data cluster, you can unplug 
one of the data nodes and the cluster will continue running without any 
data loss and with negligible loss of performance.

Ironically, many naive observers tend to hold the  belief that this is 
exactly the way a cluster filesystem is supposed to work and we must 
disappoint them by telling them you actually need to share a disk.  
Well, now we have the means to cater to that common fantasy and avoid 
the disappointment.

Note that the number of data nodes in a distributed data cluster is 
independent from the total number of nodes.  You could, for example, 
have a 100 node cluster with 5 data nodes.  This is superior to running 
the cluster off a mirrored disk because storage redundancy is reduced 
from 50% to 20% and maximum read throughput is increased from 2X to 4X.  
Unlike a mirror, raid 3.5 increases maximum write throughput as well.

It turned out that raid 3.5 was quite easy to graft on top of my cluster 
mirror prototype, which only took a couple of days.  Except for one 
thing: handling multi-page bio transfers is really tedious.  Going from 
single page bio transfers to multipage transfers has kept me busy for 
the better part of a week, and I am still putting the finishing touches 
on it.  But the thing is, now a single bio can handle a massive amount 
of contiguous filesystem data.  Even better, the parity calculations 
for all the eesny weensy little block fragments line up nicely and 
coalesce into contiguous runs inside each multipage bio.  Though you 
would think raid 3.5 makes a real hash of transfer contiguity, actually 
it does not.  In essence, I finesse the problem onto the scatter gather 
hardware[3].

I have tested up to 1 megabyte contiguous transfers, which works very 
well[4].  I have not yet had time to test throughput in a realistic 
environment, so I cannot report performance numbers today.  Hopefully 
tomorrow.

Code will be in cvs on Wednesday, I think.  This is a new project, 
tentatively called "ddraid" where dd means "distributed data".  A 
project page will appear in the fullness of time.  And of course that 
LCA paper, which I will present next month in Canberra.

The current code is production quality in a number of interesting 
respects, particularly the main read/write path.  I have implemented 
read-with-verify on the read path, where each read transaction checks 
the parity fragments to ensure nothing has gone wrong in hardware or 
software.  This works nicely, and I wonder why raid implementations do 
not typically provide such an option.

I built the ddraid implementation using the same template (and code) as 
the cluster snapshot, which saved an immense amount of time and 
hopefully will save maintenance time as well  Anybody who is interested 
in how that works can find reasonably up to date documentation here:

  http://sourceware.org/cluster/csnap/cluster.snapshot.design.html
  http://sourceware.org/cluster/csnap/csnap.ps

Like the cluster snapshot, ddraid has a userspace synchronization 
server.  And like any cluster server (userspace or not) this raises 
difficult memory deadlock issues.  Hopefully, after LCA I can sit down 
and solve these issues definitively for these and other cluster server 
components.

Due to time pressure, I must leave some work hanging until after LCA:

  * Degraded read (reconstruct from parity)
  * Degraded write
  * Parity reconstruction (currently can only reconstruct raid 1)
  * Some aspects of failover

OK, thanks a lot for reading this far, time to get back to work.  I will 
provide further details in a couple of days.

[1] To update one block of a raid 4 or 5 parity set, at least two parity 
set members must first be read and other nodes must be prevented from 
modifying these before the update is completed.

[2] Two member raid 3.5 is equivalent to raid 1.

[3] It will be interesting to see how well the scatter gather hardware 
holds up under the load of tens of thousands of tiny transfer fragments 
per second.

[4] The only real limit to transfer size is the size of a region in the 
dirty log, which persistently records which parts of the data array 
need to be reconstructed if the system fails at any given instant.  
Typical dirty log region size runs from a few KB to a few MB.

Regards,

Daniel