In 1988, three researchers from the University of California (David A. Patterson, Garth Gibson, and Randy H. Katz) developed an alternative approach to the problem of storing data on multiple disks. Their results promised a performance and reliability level that was at least one order of magnitude better than the alternatives – and at a lower cost, thanks to the new array of cheap, small disks. They dubbed their system RAID (Redundant Array of Inexpensive Disks).

The original publication http://1 described RAID levels 1 through 5. Today, we also have RAID levels 0 and 6 and still higher levels featuring combinations of the basic RAID forms.

RAID level 0, simple striping, does not support redundancy and, therefore, actually contradicts its own name. Striping involves splitting the data into chunks (stripes), which are written alternately to the disks. In an ideal case, you access all disks in parallel. The chunk size is configurable and matches the typical file size. RAID 0 does not offer fault tolerance; however, the use of multiple disks can offer performance benefits.

RAID 1

RAID level 1 is mirroring: all data is written in parallel on two disks. If one disk fails, you can go on working with the other without delay or loss. If the two halves of the mirror are connected to different channels of the RAID controller, you can ideally double the read speed, but writing is only half as fast as on a single disk – at most. The biggest disadvantage of mirroring, however, lies in the fact that it doubles the cost of data storage: For the price of two disks, you get the capacity of one. This makes simple mirroring mainly useful for particularly sensitive data that is mostly read.

RAID 2-4

RAID levels 2, 3, and 4 avoid the high cost of mirroring by reducing redundancy slightly and computing a parity value instead of duplicating write operations.

RAID level 2 is not used at all today and, in fact, was only ever used in mainframe landscapes. RAID 2 achieves redundancy by means of a linear error correcting block code, named after its inventor Hamming, which was originally developed for cleaning up read errors from punch cards. It is a complex process that involves computing parity codes against a fixed-length data block where single-bit errors can be corrected.

RAID 3 has also largely disappeared from the market today. The RAID 3 approach involves striping, but with additional protection by storing parity information on an extra parity disk. The parity disk stores bitwise records showing whether the sum of all data bits at a specific location across all data disks is odd or even. If a data disk fails, the sum of all remaining bits reveals whether the missing disk would need to have a 0 or a 1 to meet the even or odd status stored on the parity disk.

The advantage of RAID 3 is that you only need one parity disk no matter how many data disks you have. At the same time, this is also the biggest disadvantage, because the parity disk is needed for each write operation and thus creates a bottleneck.

RAID 4, which is also uncommon today, introduced a slight improvement compared with RAID 3: It still uses a separate parity disk, but it writes bigger chunks to the data disks. The disadvantage of the parity disk can be significantly mitigated if write operations are buffered in NVRAM cache. In this constellation, NetApp RAID-DP still uses its own WAFL (Write Anywhere File Layout) filesystem today for a RAID 4-related algorithm with a second drive for parity data.

RAID 5

RAID 5 uses the same block-based storage approach as RAID 4, but the parity information is distributed across all the disks instead of being concentrated on just one. This approach also distributes and parallelizes all write operations and avoids the bottleneck of a parity disk. However, RAID 5 requires two read and two write operations per write request, which inevitably slows down the write performance.

Figure 5 shows the schematic layout of a RAID 5 array. The data is stored in stripes. The stripes are consecutive segments on different physical disks. Each stripe is spread over all disks. The segments with a white background contain the actual data; the segments with a yellow background contain the parity information. As you can see, the parity data is evenly distributed across all disks.

Figure 5: Schema of a RAID 5 array with four disks. Yellow fields contain parity information, which is generated by XOR-ing the other segments of the stripe.

The parity data is calculated from the payload by XOR-ing (an exclusive OR operation, also called non-equivalence). The XOR function links two values so that a logical 1 is generated if the input variables were different. 0 XOR 1 = 1; 0 XOR 0 = 0; 1 XOR 1 = 0; 1 XOR 0 = 1. The payload data of all the segments in a stripe are now bitwise XOR'd. Taking the second line of the schema in the graphic as an example: 0010 XOR 0000 is 0010, and 0010 XOR 0100 is 0110. This is the value in the yellow segment at the intersection of stripe 2/drive 3. The same applies for the other stripes in the example. If a disk now fails, the missing data can be recreated by XOR-ing the remaining disks (rebuild), as long as at least three disks were involved in each stripe. Assume you can't access drive 2. The RAID controller computes the following for stripe 2: 0010 XOR 0110 (drive 1 and drive 3) – the result is 0100. This value 0100 XOR 0100 from drive 4 is 0000. It is thus clear that the missing segment of the failed drive 2 must have contained a value of 0000. Similarly, you can simply compute each segment in each stripe by XOR-ing the other segments in the stripe, but if more than one disk fails, all data from all stripes is irretrievably lost.

RAID and Risk

Operations with a failed disk (status degraded) or while restoring the contents of a previously failed drive (status rebuild) are particularly critical in a classic RAID scenario. If just one more disk fails, or if even one sector on the remaining disks is unreadable, all data is lost.

How likely is it that more damage will occur precisely at this sensitive time? A simple calculation assumes that the mean time to data loss (MTTDL) includes the total number of hard disks, their mean time to failure (MTTF), and the duration of the recovery process. The formula for this is still manageable, but it has a flaw: It is based on the assumption that hard disk failures are independent of one another. In a production scenario, all the disks come from a single production lot, have been exposed to identical environmental conditions, and age in a similar way, meaning that the chance for a double failure is significantly better than the theoretical value. Also, the probability of failure increases with use, which means that the MTTF drops after each failure.

The whole thing becomes even more complicated if you do not just consider total failure of one additional hard disk, but also the probability of simple read errors, which can also lead to a total loss of data. The hard disk bit error rate is responsible for this. Don't let the big numbers blind you. Even with a very small bit error probability, the risk of a bad sector is as much as 30 percent if the total capacity of the RAID array is 5TB. The larger the RAID, the higher the likelihood of an error, and the longer the rebuild takes, thus increasing the risk of a disastrous double failure. This leads to the conclusion that very large RAID sets cannot be reliably secured using classic methods.

One solution to the double-failure problem involves creating RAID sets of elements which, in turn, are RAID sets themselves. For example, if you mirror parity-based RAID sets, as in RAID 50 (mirrored RAID 5 sets), the resilience is a bit higher because now one disk can fail in each mirror half without loss of data. Under favorable conditions, the entire construct will tolerate two disk failures. However, this comes at the cost of an even poorer use of disk capacity: Because RAID 5 always loses the capacity of one disk for the parity data, the loss is doubled in two RAID 5 sets (one in each mirror half).

XOR-based parity methods cannot compensate for more than two disk failures. Error correcting code, which was once used in RAID 2, would make it possible, in principle, to achieve even higher tolerance, and work is in progress on this. However, the underlying mathematical algorithms are computationally intensive.

One candidate for a block encoding method is the Reed-Solomon code (RS code), for example, which is also used in the transmission of television signals in line with the DVB standard, where it can improve the bit error rate of the received signal at a magnitude of more than six powers. RAID 6 uses an RS code – at least in some implementations – which supplements the XOR checksum with a second checksum based on the RS method. The performance hits in RAID 6 are slightly larger than RAID 5, and one disk more is required (at least four); however, a RAID 6 configuration is capable of surviving the failure of two disks.