RAID Part 3, Iteration, Block Sizes, and the First Steps of Recovery

In the previous installments, I have talked about the general concept of RAID and how it is not really standardized. We broke RAID down into 4 main groups, left symmetrical, left asymmetrical, right symmetrical, and right asymmetrical. Of course if that was all to it, it wouldn't be such a hassle to reconstruct failed RAID arrays. To that end, I spoke about parity levels and that the number of disks don't necessarily have to be equal. This can complicate matters a bit in the reconstruction process. Of course, that is not the end to the configuration variables that must be discovered to reconstruct an array.

Iteration (Delay)

In the previous article, we examined a number of array configurations for RAID 5. The easiest to understand in probably the left-asymmetrical RAID 5. Again, in the previous article, the example used was a left asymmetrical RAID 5, Parity 5, on 5 disks. In this example, the parity rotated on every stripe, thus it rotation iteration is 1 stripe, then rotate.

left asymmetrical RAID 5, Parity 5, on 5 Disks, Iteration 1

However, some manufactures (cough, HP/Compaq, cough) decided this was too simple for their liking, so added a new variable to the game, iteration (delay). In the this configuration, some number of stripes greater than 1 is written/read before the parity rotation occurs. Thus array is somewhat akin to an incestuous relationship between RAID 4 and RAID 5, where the parity remains on the same position (note, that this is not necessarily the same disk as discussed in the previous article) for a number of stripes before rotation. When the previously defined number of iterations has occurred, the parity rotates as normal. The number of iterations of a stripe before rotation is up to you to find out (we will talk about techniques in later articles), but 16 is usually a good place to start.

left asymmetrical RAID 5, Parity 5, on 5 Disks, Iteration 2

Block Size Primer

Up until now, we have ignored block sizes. I am not talking about blocks at the disk level (sectors), but the chunk of data that is written to a disk before moving to the next disk. A "true" RAID five should always use some integer multiple of the sector size of its component disks (usually a 512 byte sector), but I have been surprised before so consider yourself forewarned. If your into guessing, start at 2^3 (8) sectors, moving up by a factor of 2 each time until you get to 512. If you get here, you probably missed something. Of course, if your not into guessing so much, know that the block size is usually some power of 2*sectors_size and read on.

Determining the Parity Level

As I mentioned, though somewhat briefly, in the previous installments of this RAID series, the parity in RAID 5 is a simple XOR of the data blocks within the stripe. The parity is then written to the parity block for the stripe. If one of the disks in the RAID fails, the missing blocks can be recalculated by performing an XOR on the remaining blocks to recover the data. We can use this fact to our advantage in the recovery process. Provided that we are working with a controller failure or other situation that all of the component disks of the RAID are present, we can easily determine the parity level of the RAID. Since the parity block of any particular stripe is equal to the XOR of the remaining data blocks in the stripe AND any value XOR itself is zero, the XOR of an entire stripe, including the parity block will always equal zero. Therefore, if you write a little program that performs XOR on 3, then 4, then 5, etc blocks at a time, the one that consistently results in zero is your parity level! That's it, well not really. There are some other variables we need to talk about for this to work in practice. This first being configuration data at the beginning of the disk that would not play well with such a simple method.
That being said, in the next installment we will talk about areas of the component disks where metadata of the RAID itself may be stored, locating the beginning of the data area, locating other common structures that will help you determine some parameters, and finding the parity blocks programmaticly.

j

Powered by Qumana

RAID Part 2, RAID 5

I am going to talk a bit today about the various configurations of RAID 5. As I have mentioned before, RAID is not a standard, but a concept of how to use multiple disks as a single device. First defined by the paper "A Case for Redundant Arrays of Inexpensive Disks (RAID)” by Gibson, Katz, and Patterson in 1988 by the CS powerhouse of the time…you guessed it, Berkley. However, the paper described the concept of RAID, it did not define a standard nor was the concept ever boiled down to one. As a result, RAID 5, or most any other RAID level, is implemented differently by each manufacturer. This makes it difficult indeed to recover an array when things go bad.
The concept of RAID 5 is striping with rotating parity. The idea is that data is written in blocks to an ordered disk set and one of the disks for every stripe contains the parity (simple XOR) of the data in the stripe. There are a bunch of sites out there that explain this, but the basic idea is that the data from each data block in the stripe is XOR’ed with the others, the result of which is written to the parity block. Thus, if a disk fails, the data from the remaining blocks can be XOR’ed to reconstruct the missing disk. The parity level is the number of data blocks plus the parity block, e.g. parity 3 (p3) is two data blocks plus parity. Since the parity block and its member blocks must each be located on a unique disk, the maximum number of blocks per pass is the number of disks minus one (n-1). While it is of the norm to see the parity level equal the number of disks in a set, it is not a requirement. Therefore, the parity level can equal any number between 3 and the number of disks in the array, which can cause al sorts of headaches for those trying to recover data off a dead array.

RAID 5 can be broken down into four different methods. There are certainly more variations on these methods which I will talk about in another article, but this is the best place to start. The methods are left asymmetrical, left symmetrical, right asymmetrical, and right symmetrical. For the purpose of the explanation, I am going to ignore block sizes and iteration (delayed rotation), which must be known or discovered to recover data.

Left asymmetrical is most employed by hardware RAID cards. It writes data to blocks n, n+1, n+2, … n-1 then parities those data blocks to the last block so that the resulting sequence is n, n+1, n+2…n-1, p. Parity is then rotated left (backwards) one block so that the sequence is n, n+1, n+2…p, n-1.

left-asymmetrical RAID 5, Parity 5, on 5 disks

This is probably the simplest form of RAID 5 to understand; however, from a performance standpoint, the system can read only from Parity-1 blocks before running to the possibility of reading a disk twice. This is where symmetrical RAID 5 comes in. Here this blocks are written as before, n, n+1, n+2...n-1,p; however, instead of the next block being written to next sequential device, it is written after the parity block (which is below the previous parity block) and the stripe is written in-line from that point on, until it wraps to the parity block. This method allows for all blocks in a stripe to be read.


left-symmetrical RAID 5, parity 5, on 5 disks

There are the right hand versions of the above as well. Right asymmetrical starts with the parity block at the first placement, and rotates right. The first data block in the stripe is always in the first placement (except when the parity block is located there, then it is incremented).


right-asymmetrical RAID 5, parity 5, on 5 disks
Right symmetrical writes the data blocks following the parity block, as with its left rotating brother, it writes data following the parity block and wraps around until it reaches the parity block again.


Right symmetrical RAID 5, parity 5, on 5 disks


Adding to the confusion
In the above examples, we looked at RAID 5, parity 5, on 5 disks. The parity level could be any integer greater than or equal to 3. To make things more difficult, the number of disks is not limited to parity level. They can number greater than or equal to the parity level. Lets take a look at a left-asymmetrical RAID 5, parity 4, on 5 disks.


Left asymmetrical RAID 5, parity 4, on 5 disks
Here the data is striped with three data blocks and a parity block, which is parity 4. However, in the second stripe, position 0 is on the first block or the 5th disk, so the beginning of the stripe starts there. Notice that if we did not know the configuration of the array, we would end up with 2 parity blocks in some rows.
In the next installment, I will talk about rotation iteration (delay), block sizes, and ways to determine parity levels. Stay tuned.
j

Powered by Qumana

RAID Tool Update

I have released a FUSE file system that can put together an asymmetrical RAID 5 with any parity level and any iteration level. I don't have any controllers to test the thing on other than the Compaq one it was developed with. Remember this tool is a proof of concept, use it accordingly. I am working on the update to this tool that will use one single fuse mount command and plugins to add "files" at will. Reassembled RAID images will be the first of these files and it will allow for compound RAID with only one fuse instance running.

If your interested in the tool, check it out at http://raidfs.sourceforge.net/ or download at http://sourceforge.net/search/?type_of_search=soft&words=raidfs

Jason

Powered by Qumana

RAID Part 1

Large dataset analysis and recovery has been an interest of mine for some time. The server room is vastly important in today’s business enviroments and is increasingly part of any investigation involving business, including small businesses. Unfortunately, computer forensics is slow to catch up to this trend and has all but neglected designing tools to approach large datasets and has instead continued its trend to focus on the home user machines. While I understand this is where the bang for the buck is in the industry, it does leave a gaping hole that needs to be filled. Thus my interest ;-)

RAID is one such subset of my interest in this area. Encase and X-Ways have RAID reconstruction functionality, but it is very limited. They seem to have designed their algorythms for this functionality as an afterthought or stub, again a bang for the buck issue. The problem with RAID is that it is not standardized. Sure there is a loose definition of each type of RAID, RAID 0-6 and such; however, there is not implementation standard. For example, a RAID5 from Compaq looks nothing like a RAID5 from Adaptec. For example, configuration information information is stored in different locations/sizes and parity rotatation is implemented differently. It is not just the direction of rotation either but the iteration of rotation. In short it is just a mess.

So I am working on a program to deal with this. Actually, I started it some time ago and I have now come back to it. I will release the program on sourceforge when I feel it is at least to alpha quality and properly documented. It should handle every structured RAID from 0 – 5, regardless of rotation direction, number of disks, rotation iteration, blocksize, or parity level. Next I will move on to a program that evalutes component disks and deduces likely configurations.

j