Triple-parity RAID

[kureshii]

Article from ACM Queue: Triple-parity RAID and Beyond

Choice excerpts:

How much longer will current RAID techniques persevere? The RAID levels were codified in the late 1980s [...] RAID-6, double-parity RAID, was not described in Patterson, Gibson, and Katz's original 1988 paper but was added in 1993 in response to the observation that as disk arrays grow, so too do the chances of a double failure.

While bit error rates have nearly kept pace with the growth in disk capacity, throughput has not been given its due consideration when determining RAID reliability. [...] When RAID systems were developed in the 1980s and 1990s, reconstruction times were measured in minutes. The trend for the past 10 years is quite clear regardless of the drive speed or its market segment: the time to perform a RAID reconstruction is increasing exponentially as capacity far outstrips throughput. [...] The time to repair a failed drive is increasing, and at the same time the lengthening duration of a scrub means that errors are more likely to be encountered during the repair.


Time required to repopulate a failed disk in a RAID array



The common questions:
How is this relevant to home use?
It's not, not at the moment anyway. But RAID 5 came about in the 1980s, and almost nobody thought it would be deployed for home use one of these days. The consumer market generally benefits from a trickle-down effect from technologies that are usually first deployed in enterprise environments.

Isn't triple-parity RAID overkill? Most of us haven't even needed double-parity RAID yet...
If you have to ask, of course it is overkill for you. But that doesn't mean nobody else needs it.

That's just silly, why don't people use multiple RAID5  or RAID6 volumes instead of a single triple-parity storage volume?
Why don't you use a cluster of Pentium 1s instead of a dual-core or quad-core machine?



Anyway, the point of posting this article is to ask a question. The following paragraph in the article caught my attention:

A recurring theme in computer science is that algorithms can be specialized for small fixed values, but are then generalized to scale to an arbitrary value. A common belief in the computer industry had been that double-parity RAID was effectively that generalization, that it provided all the data reliability that would ever be needed. RAID-6 is inadequate, leading to the need for triple-parity RAID, but that, too, if current trends persist, will become insufficient. Not only is there a need for triple-parity RAID, but there's also a need for efficient algorithms that truly address the general case of RAID with an arbitrary number of parity devices.

What that means is that the RAID 5 and 6 algorithms are not scalable with regards to parity blocks. You can scale the number of disks in a RAID 5 or 6 array, but those arrays will always use 1 and 2 blocks of parity data respectively, in every stripe (concurrent series of blocks) of data.

RAID 5 is a single-parity algorithm, and RAID 6 is a double-parity algorithm. Currently, triple-parity RAID-Z is also not using a generic algorithm. Perhaps in time to come we'll finally have an efficient, robust n-parity RAID algorithm that works for multiple values of n (I hesitate to say all values of n, because then one has to consider absurdly huge numbers that won't be practical even for enterprise use)

This got me thinking. I'm not intimately familiar with the mathematical details of the RAID5 and RAID6 algorithms, apart from the fact they use Reed-Solomon codes for redundancy, so I don't know how computationally intensive it is to generate parity data blocks for each of these 2 algorithms.

But assuming that we do have a robust n-parity RAID algorithm, how would the computational load scale with n? Be it a computation-efficient or memory-efficient algorithm, what would an optimistic estimate of the scaling function be?

I find such questions quite interesting, and although I don't have the time to read up on this in detail, if anyone has interesting insights I'll be glad to hear them.

[nstgc]

I'm far from an expert, but that doesn't make that much sense. If the problem is errors that accumulate during the reconstruction time, which are getting exponentially longer, then nested arrays should take care of that. I remember going over the calculations once for fairlure rate in a nsted system versus an n-parity system. I can't remember exactly what I came to, but concluded that a nested system was better. I did not take reconstruction time into consideration, however. If, as you said, the size of drives is increasing at a great rate, then it seems that the best thing to do is not use RAID 5/6 at all for the top level. The problem with a nesteded array is the hardware to run it. With more controllers, more things can go wrong. If you have a duplex of two nested arrays (lets say a large RAID 6 arrar of small RAID 5s with a spare RAID 5 array) wouldn't that take care of it. The chances of that many HDD dying seems very slim, but the chances of enough HDD and a controller (which may be harder to detect in advance) seems like a possibility.

Again, I've only looked at a single piece of the problem, but that is my opinion.

[edit] Another disclaimer -- my memory isn't perfect.

[edit2] On second thought, simply doubling already costly equipment doesn't seem very cost effective. What if the spare drive was an SDD? The array itself should be able to recover and read the parity at a respectable rate, but I can see how copying it onto that spare would be time consuming. This can be alleviated with a faster drive. You won't need a lot of them. Just enough to replace one hard drive or perhaps one array (on a lower level).

[edit4] edit3 was wrong. Chances of failure given a 50k MTBF HDD in a 6 member RAID 5 array that already has a dead drive in a 24 hour period is 8.2% not 1.7%. 1.3% is in 4h not 0.27%.

[halfelite]

You could always run triple parity raid-z. Unless you are running 12+ drives at home I see no reason for triple parity. And even then running an offline raid0 system as a backup gives you even more of a fail proof then just adding more parity. And the cost effectiveness is not that bad.

[Proin Drakenzol]

I could see needing n-parity RAID first for military applications where speed of reconstitution through the use of hot-swappable drives is more important than cost efficiency or even data transfer efficiency. However a corporation is probably better off using a cheaper solution involving nested and alternating active/inactive RAIDs than investing in n-parity capability.

[nstgc]

You could always run triple parity raid-z. Unless you are running 12+ drives at home I see no reason for triple parity. And even then running an offline raid0 system as a backup gives you even more of a fail proof then just adding more parity. And the cost effectiveness is not that bad.

The discussion isn't on home use.

I could see needing n-parity RAID first for military applications where speed of reconstitution through the use of hot-swappable drives is more important than cost efficiency or even data transfer efficiency. However a corporation is probably better off using a cheaper solution involving nested and alternating active/inactive RAIDs than investing in n-parity capability.

Wouldn't higher parity be more cost effective? Isn't it more a software limitation then a hardware limitation? Once the software is developed, wouldn't the price scale more favourably then a nested array? While I agree that a nested RAID is a better solution, it doesn't seem as if its necessarily more cost effective. I don't know. I've only dealt with non-nested RAIDs on the level of a home computer. (Four member RAID 5 using a dedicated card with its own xor processor. The damn card died! Redundancy is great, but it doesn't do any good if the controller is shit.)

One thing I don't understand is why you can't just use something like par2 (a archive backup program that uses a Read-Solomon ring), but with drives. It scales very well.

[mgz]

i think its kinda silly to even discuss it, to some people and for data to some, there is no such thing as being to careful

[nstgc]

The discussion isn't on individuals using it. The discussion is for corporations, and, as Proin mentioned, the military/government.

[kureshii]

I'm far from an expert, but that doesn't make that much sense. If the problem is errors that accumulate during the reconstruction time, which are getting exponentially longer, then nested arrays should take care of that. I remember going over the calculations once for fairlure rate in a nsted system versus an n-parity system. I can't remember exactly what I came to, but concluded that a nested system was better. I did not take reconstruction time into consideration, however. If, as you said, the size of drives is increasing at a great rate, then it seems that the best thing to do is not use RAID 5/6 at all for the top level. The problem with a nested array is the hardware to run it. With more controllers, more things can go wrong. If you have a duplex of two nested arrays (lets say a large RAID 6 arrar of small RAID 5s with a spare RAID 5 array) wouldn't that take care of it. The chances of that many HDD dying seems very slim, but the chances of enough HDD and a controller (which may be harder to detect in advance) seems like a possibility.

We've been through nested RAID before, and you can probably add to that thread, but the inevitable conclusion is with more nested levels, it simply becomes cost-ineffective to be using entire RAID arrays for parity data.So that's not a scalable solution (or not a cost-effective one at scale, anyway).

As far as I can tell from the article, the 2 main issues are:
1) Throughput not increasing at the same scale as disk capacity
2) Scalable efficient n-level RAID algorithm not in existence yet

The first issue leads to longer RAID rebuild times (and not errors accumulating during rebuild)), and for sufficiently large arrays the rebuild time can stretch to days, or even weeks. The article mainly attributes this to the low throughput of the drives relative to their capacity. Many degraded RAID arrays are left to run in a degraded state while they're still being rebuilt (because for some enterprises the point of a RAID is maximum uptime); that does not leave much throughput available for RAID rebuilding.

With RAID rebuild times stretching that long, the chance of a second or even third disk failing during the rebuild period increases as well. And hence the increasing need for triple-parity RAID. Extrapolating from that, a scaleable n-level RAID algorithm (the second issue) would eliminate the need to have to write a new RAID algorithm each time an additional parity level is required.

Additionally, there are other factors affecting rebuild times, such as time required for a human operator to procure a new disk and insert it into the array, but let's ignore those for now.



So at heart, it's really a throughput problem. Low throughput (relative to disk capacity) leads to longer rebuild times, longer rebuild times lead to increased risk of additional disks failing during rebuild, higher level parity needed to offset increased risk of additional disks failing.

Or to put things in perspective, it takes ~3.5hrs to fill a 2TB hard disk at 150MB/s write speed (I assume you're all astute enough to correct me on the issues and not the numbers). In the near future, we'll have 4TB disks, but disk read/write speeds are hardly doubling; a 4TB disk will take 7 hours to fill, and so on.

But I don't find throughput issues that interesting, which is why I'm focusing on the second issue: scaleable n-level RAID algorithms, and the associated computational costs.

One thing I don't understand is why you can't just use something like par2 (a archive backup program that uses a Read-Solomon ring), but with drives. It scales very well.

par2 helps repair corrupted data, it doesn't increase drive reliability, or prevent the whole array going down when the disk fails.

[nstgc]

And what about my suggestion to use SDD as a auto-swap drive?

I understand that any numbers anyone provides would be worthless (even though I gave some already) since we are talking some arbitrary distance into the future.

I didn't read that entire "RAID over RAID" thread, however I still hold to the belief that you should at least have two levels so you can swap out an array if need be. I don't know if that was addressed, I'll look it up tomorrow (its 1:26 am here and I'm quite tired).

[edit] Another option I just thought of that scales as well as n-parity RAID would be to make the spare a RAID instead of a drive. Admittedly it seems (is clearly) more costly, but it is a technology that exists now, and would work. I doubt any of us are actually actively trying to solve this problem for personal gain, so I think this is a valid option in Fairyland.

[kureshii]

I'm far from an expert, but that doesn't make that much sense. If the problem is errors that accumulate during the reconstruction time, which are getting exponentially longer, then nested arrays should take care of that. I remember going over the calculations once for fairlure rate in a nsted system versus an n-parity system. I can't remember exactly what I came to, but concluded that a nested system was better. I did not take reconstruction time into consideration, however. If, as you said, the size of drives is increasing at a great rate, then it seems that the best thing to do is not use RAID 5/6 at all for the top level. The problem with a nesteded array is the hardware to run it. With more controllers, more things can go wrong. If you have a duplex of two nested arrays (lets say a large RAID 6 arrar of small RAID 5s with a spare RAID 5 array) wouldn't that take care of it. The chances of that many HDD dying seems very slim, but the chances of enough HDD and a controller (which may be harder to detect in advance) seems like a possibility.

It seems like a big waste of parity data to me. Despite using the equivalent of 2 whole arrays as well as 1 disk in each of the remaining arrays for parity, the failure of at least 2 disks in at least 3 arrays would bring the whole nested RAID down.

Of course, it is not likely that such a thing would happen, but what can be accomplished with such a setup that can't be accomplished with a 7-level RAID and less hardware?



I don't get what you mean by using a silicon disk drive as swap. What advantages would that provide? Because if the sole advantage is a lower risk of failure, it still does not address the issues of time for RAID rebuilding.

[nstgc]

What would it accomplish? Well, as mentioned, its a system meant to be used in Fairyland. It also doesn't need anything new. The suggestion presented in the previous post is independent of that given in the first by the way. Its that you just need a single spare fast array to last long enough for a real drive to back up. That will alway be scaleable and its not like a normal nested array.

The SSD's have a faster transfer rate correct? Theoretical the rate of reconstruction could be the number of drives remaining times their throughput. Constant use for, oh I don't know, their actual purpose, would cause some problems, but thats partly why I think no matter what you should have two levels (or three in the fairyland solution).

[kureshii]

Ah, so it's just a less space-efficient stand-in, in the absence of n-level RAID. Ok, I see what you're talking about now.

Wait, were you talking about SSDs or SDDs? The first time you said SDD I thought it was a typo, but then you said it again a second time so I thought you meant Silicon Disk Drive...

But assuming you mean SSDs as in Solid State Disks, yeah you can reconstruct RAID arrays consisting of those much more quickly. An SSD RAID will also cost much more than a mechanical disk drive RAID for the same capacity. In the article flash disks (i.e. SSDs) were mentioned, with a possible use being as intermediary write caches so as not to make the rebuild process too disk-bound. But at heart the issue is still one of disk throughput for affordable high-capacity disks. (Don't we all want arrays of fusion-io Octal 5TB modules...)

If one is so inclined I suppose one could use small RAID arrays in place of hard disks in a RAID setup, but it will undeniably bring more hardware into the picture and increases the proportion of total capacity used for parity data, not necessarily in a manner that makes full use of all that parity data.

I'm inclined to think that once n-level RAID is available (probably in software form rather than chipset firmware form), it should be a more cost-effective solution for corporations needing that level of redundancy.