## 3 Related Methods  
### Basic Data Striping and RAID Storage Systems  
RAID stands for Redundant Array of Independent Disks. It is a well-known method of combining several hard disk drives into one logical unit, so as to address the fault-tolerance and performance limitations of an individual hard disk drive. The key notions behind a RAID storage system are Data Striping and various levels of Redundancy. The striping process takes large data blocks and splits them into blocks of a defined size, such as 4 KB, which are then spread across each of the disks in the array. This can increase the performance of a storage system as a _n_-disk array (_i.e._, _n_-way striping) provides \(n\) times the read and write speed improvement of a single disk (although in practice the actual performance achieved tends to be less than \(n\) times due to control overheads). However, the trade-off is reliability, as the failure of any individual disk would result in the failure of the entire array. Formally, assume that each independent hard disk drive has an identical rate of failure \(r\), then the overall failure rate of an array of \(n\) disks is:  
\[1-(1-r)^{n}\]  
Basic data striping over an array of _n_-disks without redundancy is referred to as RAID0, which is only suitable to situations where the highest I/O performance is desired, whilst the resulting increased probability of data loss can be tolerated. In other situations, reliability of data may outweigh system performance, and thus instead of striping the data over \(n\) disks, the same data is duplicated (or mirrored) to \(n\) disks. This strategy is referred to as RAID1, which is suitable to ensure the reliability of critical data. In comparison to RAID0, the overall failure rate of a RAID1 array of \(n\) disks becomes:  
\[r^{n}\]  
However, when the same set of data is duplicated over \(n\) disks, it would result in a storage overhead of \(n\) -1 disks. RAID0 and RAID1 can be combined into a RAID01 or a RAID10 configuration. The former means a mirrored configuration of multiple striped sets (_i.e._, mirror of stripes); and the latter means a stripe across a number of mirrored sets (_i.e._, stripe of mirrors). Both strategies are able to provide very good performance and reliability, whereas both are expensive solutions as considerable amount of hard disk storage is committed to maintaining redundancy information. Another RAID level, namely RAID5, attempts to mitigate the high costs of RAID01/10. RAID5 utilizes striping and parity techniques to achieve simultaneously a similar I/O performance to RAID0 with a significantly lower failure rate of:  
\(1-(1-r)^{n}-nr(1-r)^{n-1}\)  
A parity bit (or check bit) is a bit added to the end of a string of binary code that indicates whether the number of bits in the string with the value 1 is even or odd. In computing and telecommunications, a parity bit is calculated via an XOR sum of all the previous bits, yielding 0 for even parity and 1 for odd parity. Let A and B being two binary sequences. If:  
X = A XOR B  
then the following will be true:  
B = X XOR A  
Using this property, we can say that the following expressions are also true (and this can be repeated for an infinite amount of terms):  
A XOR B XOR C XOR X = D  
Put simply, if we calculate a XOR of a number sequence, we can substitute X for any number in this sequence, recalculate the XOR, and recover the original number. This is the principle for building a RAID5 array, of which an example is shown in Figure 1. Each of the four drives in Figure 1 are divided into four blocks, each belonging to a stripe on the same level across each drive. Each drive and each stripe have a parity block (stored in disk 4) which is the XOR of the other three blocks.