RAID Striping Algorithms: The Missing Link II

In the prior post I explained how physical stripes including parity are laid out in a RAID 5 configuration. I introduced data mapping as a separate layer from striping.

To continue... while the physical striping is ordered and easy to understand, the data mapping layer or logical stripes aren't always laid out in a simple contiguous pattern. When I first started writing my unstriping tools, this confounded me no end.


To understand the differences we need to return to my simplified annotation of the 3 points of view of the stripes. We can use the model at the right to help. The first stripe represented has reverse parity with the data contiguously laid out from Disk 0 to Disk 2. The parity stripe is on Disk 3. A1 corresponds to S1D0 and PV1 as well as LV1. The second level is well ordered simply eliminating the parity stripe from the logical volume.

So, you ask, "Where is all the complication?" The difficulty comes when you reach the parity stripe. In a simple schema you expect the next logical stripe (LV4) to be B1 (S2D0: 128 - 255 sectors) which would also correspond to PV5. However, this isn't what always happens. A common striping algorithm puts the next stripe (LV4) on the second stripe of the last drive (S2D3) as if it jumps up to the next level. Then, the second stripe on the first drive (S2D0) becomes LV5 and the second stripe on the second drive (S2D1) becomes LV6. It doesn't seem to make sense adding an unnecessary complication.

In the Compaq schema from my previous post it was even more complex. Compaq created an array using a factor of 16:1 parity stripes to data stripes. For each 16 data stripes on the data drives one drive was designated as the parity drive. Then, it would switch in reverse parity fashion to the next drive for 16 data stripes on the other drives. To make things even more complicated, they still rotated the data stripes on the other drives. It wasn't just a simple big stripe of 2048 (16 * 128) sectors which was my first attempt.

There is no substitution for spending the time and doing a good analysis of the stripes. After making several unstripe attempts adjusting parameters and testing the outcome on that Compaq recovery, I came close to recoverying data. However, I would get some files back but not others. On inspection of the rebuilt volume there were "holes" in the file system. The array contained 14 drives and each needed to be inspected. The failed drives had both been successfully recovered. So, there was no excuse for missing data. To check continuity, I look for easy to read files, usually text files. Long MS Word documents also contain sufficient text data. I want to find files that cross stripe boundaries. When an easily readable file crosses a stripe boundary, I can connect the stripes. This helps me to create a map of the array laying out all the stripes in both logical order and physical order. Using the map I am able to construct the algorithm for unstriping.

It would be too long to go into further detail. Unstriping tools are a book unto themselves and go beyond the scope of this blog.

Next I will take a look at some of the NAS devices we have recovered and their issues.