A Tutorial on RAID Storage Systems
Sameshan Perumal and Pieter Kritzinger
May 6, 2004
Data Network Architectures Group
Department of Computer Science
University of Cape Town
7701 South Africa
e-mail: dna@cs.uct.ac.za
RAID storage systems have been in use since the early 1990's. Recently, however, as the demand for
huge amounts of on-line storage has increased, RAID has once again come into focus. This report
reviews the history of RAID, as well as where and how RAID systems ¯t in the storage hierarchy
of an Enterprize Computing System (EIS). We describe the known RAID con¯gurations and the
advantages and disadvantages of each. Since the focus of our research is on the performance of RAID
systems we devote a section to the various factors which a®ect RAID performance. Modelling RAID
systems for their performance analysis is the topic of the next section and we report on the issues
as well as brie°y describe one simulator, RAIDframe, which has been developed. We conclude with
section which describes the current open research questions in the area.
1 Introduction
The concept of Redundant Arrays of Inexpensive Disks (RAID) was introduced about two decades
ago and a RAID taxonomy was ¯rst established by Patterson [Patterson et al. 1988] in 1988. The
taxonomy outlines the theory of RAID systems and provides several schemes to utilize the capa-
bilities in varying ways. These RAID levels describe data placement and redundancy strategies for
di®erent applications, as well as the bene¯ts of each level. RAID overcomes the capacity limita-
tions of commodity disks by treating an array of such low-capacity disks as one large Single Large
Expensive Disk (SLED). Such arrays o®er °exibility over SLED, in that capacity can be increased
incrementally, and as desired, by simply adding more disks to the array.
Commodity storage disks currently o®er a number of bene¯ts:
1. They are inexpensive, with approximately the same or lower cost per byte than SLED's;
2. Individual disks has a Mean Time To Failure (MTTF) rate comparable to most SLED's;
3. They require far less power;
4. They conform to a uniform access standard, typically SCSI or IDE, and usually
5. they have built in controller logic which performs both error detection and correction functions.
Since each individual disk in a RAID system consumes little power, and the cost of replacement
of a single disk is small compared to the overall cost, RAID systems have low maintenance costs.
Finally, given that each disk in the array, depending on the logical arrangement, can perform
transfers independently of the others the potential for faster transfers through the exploitation of
parallelism exists.
2 Overview
The two main hardware architecture factors Dominating the performance of RAID systems are
{ bandwidth and parallelism, both of which are in°uenced heavily by storage caches.
{ Data placement on the disks, and
{ The way blocks belonging to a single ¯le are places across the various disks, know as striping
{ Workload or the storage access pattern of an application as we discuss in Section 4.1.
The following ¯gure illustrates a typical EIS secondary storage hierarchy which includes a RAID
system and which we shall refer to later in this report.
2.1 EIS Storage Hierarchy
Disk Server
EIS Storage Area Network
Fibre Channel
Fibre Channel
FC Switch
FC Switch
Server Server Server
Server Server Server
Figure 1: A typical EIS secondary storage hierarchy which includes a RAID system
2.2 RAID Taxonomy
A possible approach is to place each bit on a di®erent disk - however reads occur in multiples of
sector sizes, hence this approach is not commonly used. The more common case divides the ¯le
into blocks and then distributes these blocks among the disks in rotation. A stripe then consists of
the same sector from each disk in the array, and is e®ectively equivalent to single sector in a stand
alone disk.
2.2.1 Non-redundant Disk Arrays - RAID Level 0
D? = Data Block
D3 D4
D1 D2
D5 D6 D8
D9 D10 D11 D12
Disk 1 Disk 2 Disk 3 Disk 4
Block 1
Block 2
Block 3
Figure 2: Data Layout in RAID 0 scheme
The above scheme has come to be known as RAID 0, though it is generally acknowledged that
is not a true RAID. A single failure will render the data across the entire array useless, since each
disk stores part of every ¯le. It is thus necessary to store error correcting information, so that it
is possible to recover from at least one disk failure. This is achieved by using parity information,
similarly to Error Correcting Codes (ECC) used in disks. Parity is calculated by applying the XOR
operator to data across every disk in a stripe. Since each disk has a controller capable of detecting
a read error, it is not necessary to store information on which disk in the array failed. Thus, the
parity information is su±cient to correct a single error, i.e., a single disk failure.
2.2.2 Mirroring - RAID Level 1
In the case of mirroring1, reliability is achieved by simply duplicating all data across two or more
disks. This provides complete reliability with minimal repair and recovery time - in the event of
a single failure, any of the duplicates can be used for reads, while writes can be mirrored across
the remaining disks. This scheme o®ers the possibility of greater bandwidth through parallelism,
since two reads of di®erent sectors can be assigned to two di®erent disks - both reads occur at the
same time, e®ectively doubling the bandwidth. With more than two disks, multiple reads can be
scheduled simultaneously.
1Initially referred to as disk shadowing in [Britton and Gray 1988]
Disk 1 Disk 2 Disk 3 Disk 4
Block 1
Block 2
Block 3
D? = Data Block
D1 D1 D1
D2 D2 D2
D3 D3
Figure 3: Data Layout in RAID 1 scheme
Mirrored disks also su®er the smallest write penalty, since the cost of any write is simply the
maximum cost for any of the individual disk writes. If the disk spindles and heads are synchronized2,
there is no write penalty, since all disks move in unison, acting as one large disk.
Mirroring has the highest storage overhead of all (100%), however, since each disk other than the
main one is used solely for redundancy - none of its capacity is available for useful storage. Another
issue is that recovering a failed disk involves copying an entire disk to a replacement - this is not
only time consuming, it also reduces the performance of the RAID during reconstruction, which
may not be acceptable in certain real-time applications. However, if more than 2 disks are used,
one of the clones can simply be taken o® line and used to recover the failed disk in a short period
of time.
2.2.3 Striped Data with Parity - RAID Levels 2 - 4
P? = Parity Block
D1 D2 D3
Disk 1 Disk 2 Disk 3 Disk 4
Block 1
Block 2
Block 3
D? = Data Block
D4 D5 D6
D7 D9
Figure 4: Data Layout in RAID 4 scheme
In order to prevent data loss in RAID systems, other than level 1, it is necessary to incorporate
2At any given moment, the heads of each disk are over the same logical sector
some sort of redundancy into the system. The simplest, and most widely adopted, system uses
single error correcting parity [Patterson et al. 1988], using XOR operations, and is able to prevent
single disk failures. This technique forms the basis of RAID 2-4.
RAID level 2 uses additional disks to store Hamming Code data, which is used to determine
which disk in the array failed. However, most modern drive controllers can detect which disk in the
array has failed, thus eliminating the need for these extra redundancy disks. This allows more of
the total capacity to be utilized for data storage rather than redundancy.
Since disk failure can now be detected by the controller, parity can be stored on a single separate
disk, and a single failed disk (parity or data) can be reconstructed from the remaining disks. This
is referred to as RAID 3 in the taxonomy. The two possible failure scenarios and an obvious
reconstruction scenario are illustrated in Figure 5and 6.
Data Parity
0 1 0 1
1 1 1 1
1 1 0 0
Normal Data Layout
Data Parity
0 1 0 ?
1 1 1 ?
1 1 0 ?
Failed Parity Disk
Data Parity
0 1 ? 1
1 1 ? 1
1 1 ? 0
Failed Data Disk
Figure 5: Illustration of the 2 possible failure scenarios in RAID 3
The reconstruction simply involves reading the data from all the undamaged disks for each stripe,
calculating the parity of that data, and then writing this value to the replacement disk. If the failed
disk was the parity disk, the recovery is done by simply recomputing the parity. If the failed disk
was a data disk, the scheme still works since the XOR operator is commutative. Figure 6 illustrates
this using the state represented by the Failed Data Disk scenario in Figure 5.
0 1
1 1
1 1 M
Figure 6: Reconstruction of lost data
RAID 4 still distributes data across disks, with a parity disk for redundancy, but now individual
¯les are kept on a single disk. This is meant to assist in the performance of small writes, but the
increase is minimal, and speedup through parallelism is sacri¯ced. RAID 4 is thus not commonly
To complete a write request, the new parity must be computed and written to disk. Hence, each
write must access the parity disk before it completes. Since multiple write requests will be queueing
for this single parity disk, a bottle neck is created in RAID levels 3 and 4.
P? = Parity Block
D1 D2 D3
Disk 1 Disk 2 Disk 3 Disk 4
Block 1
Block 2
Block 3
D4 D5
D7 D9
P2 D6
P3 D8
Block 3 P4 D10 D11 D12
D? = Data Block
Figure 7: Data Layout in RAID 5 scheme
2.2.4 Rotating Parity with Striped Data - RAID Level 5
RAID 5 improves on this \parity bottleneck" by distributing the parity (check) disk across all
disks in the array, thus reducing the bottleneck created by the check disk. This scheme also allows
simultaneous writes if the writes are to di®erent stripes, and there are no common clusters between
the writes.
2.3 Other Redundancy Schemes
EVENODD [Blaum et al. 1994] is an alternate scheme that guards against two disk failures, and
is e±ciently implementable in hardware. The layout described to prevent bottlenecks restricts the
array to a maximum of 259 disks, however.
Other schemes include balanced incomplete block designs (BIBD) [Holland and Gibson 1992]
(see Section 4.3.2), which attempt to uniformly distribute data and parity across a disk, and coding
methods proposed in [Hellerstein et al. 1994] which protect against arbitrary numbers of failures,
but have overheads that increase exponentially w.r.t. prevented failures. Additionally, the schemes
are fairly restrictive on array dimensions for optimal redundancy usage.
Finally, a scheme proposed in [Alvarez et al. 1997], DATUM, allows for recovery from an arbitrary
number of disk failures, using an optimal amount of redundant storage, whilst still allowing °exible
array con¯gurations, and ensuring both parity and data are evenly distributed across the disks.
Further explanation of these schemes may be found in Section 4.2
3 RAID Implementation
This section overviews some of the key issues of a typical RAID implementation. It covers: the
physical location and architecture; possible opportunities for parallelism; the method by which a
RAID is connected to a host; and the operation of the RAID controller.
3.1 Controller Location
When designing a RAID storage system, there exist several options regarding the architecture. The
array can be completely implemented in hardware as a black box that appears as a single disk to
the host machine. Alternatively, the drives in the array can be directly connected to the host and
an operating system driver performs the necessary controller functions, again presenting the array
as a single disk. Finally, hybrid systems exist which attempt to take advantage of both approaches.
3.1.1 Hardware RAID Systems
All processing and management of RAID is o²oaded to a dedicated processor on the hardware,
referred to as the RAID controller. This includes parity checking, management of recovery from disk
failures, and the physical striping of data across multiple disks. Internally drives are attached using
IDE, SATA or SCSI Interfaces. Connection to server is also via one these interfaces. The hardware
presents the RAID to the host system as a single, large disk. The con¯guration of various RAID
parameters3 is handled by the hardware. Most commercial implementations adopt this approach.
One possible con¯guration is illustrated in Figure 8
IDE / SCSI / SATA Interface
CPU Card
Scsi Bus
Figure 8: Typical architecture of a hardware RAID implementation
3.1.2 Software RAID Systems
Rather than have dedicated hardware to handle the operation of the RAID, this approach uses
normal disk controllers (like IDE and SATA interfaces available on most modern motherboards)
and software to achieve the same functionality. This is a less expensive option, as specialized
3stripe unit size, RAID level, cache policy
hardware is unnecessary, but CPU Load increases because of the overhead the software processing
which can become a bottleneck.
Software RAID Systems use a software driver, that communicates directly with the disk drives
present in the machine, which acts as a RAID controller. This driver appears to be a single
disk drive to the kernel. When requests are issued, the software driver intercepts these requests
and formulates the appropriate actions to service it (see Figures 11 and 12). The driver is also
responsible for managing and coordinating the operation of the individual drives in the array.
RAID parameters can be con¯gured via a software interface. The Linux RAID Enterprize Volume
Management System (EVMS) takes this approach.
3.1.3 Hybrid Approaches
Some hybrid approaches that have been attempted include the following:
1. Utilizing IDE Controllers on a motherboard for RAID storage, with controller operation un-
dertaken by an onboard chip. Basically, this operates very similarly to software RAID, except
that a dedicated hardware chip handles the tasks of the RAID controller.
This allows slightly better performance than the software approach, but since all the hard
drives are sharing bandwidth on the PCI bus, it is not the best solution. Many motherboards
are now available with this technology.
2. Intel RAIDIOS technology, which enables the use of the onboard SCSI/SATA controller for
RAID via a PCI RAID Card. This card utilizes the onboard controller to communicate with
the connected hard drives. It overrides the default controller operation to make it appear
at a hardware level as though the array is a single disk. It is almost identical to the former
solution, with the exception that the RAID controller is an optional add-on. If not present,
the disk controller (usually SCSI) operates normally. If the PCI Card is present, the controller
on the Card overrides the onboard controller and takes on the relevant RAID responsibilities.
3.2 Parallelism in RAID Storage Systems
Access to a RAID storage system is normally via a serial channel, usually SCSI or FibreChannel,
although IDE and SATA implementations exist. Some implementations, such as EZRAID, o®er
multiple access channels, but each channel can only access a designated part of the RAID. This is
achieved by partitioning the RAID and allowing each channel exclusive access to a subset of the
partitions. If the partitions are on physically separate volumes, true parallel access is supported,
since each channel can independently access its associated partitions as exclusive disk access is
possible. If all disks are shared by all partitions, this is not possible.
When considering RAID Storage System access there are 8 di®erent combinations of factors that
must be investigated:
Access Path File Size Read/Write
serial parallel large small read write
where large indicates a transfer of more than one stripe.
However all large accesses must be performed in serial since all disks are necessarily involved in
the transfer Hence, no disk can be accessed until the transfer is complete. Figure 9 illustrates this.
P? = Parity Block

D1 D2 D3
Disk 1 Disk 2 Disk 3 Disk 4
Block 1
Block 2
Block 3
D4 D5
D7 D9
P2 D6
P3 D8
Block 3 P4 D10 D11 D12
D? = Data Block
Figure 9: Large access in a RAID spanning multiple stripes
By contrast, most small accesses can be however be parallelized since each access may require
di®erent disks, as illustrated in Figure 10. The extent to which small accesses can be parallelized is a
measure of the performance of the RAID under a workload typical of Online Transaction Processing
P? = Parity Block

D1 D2 D3
Disk 1 Disk 2 Disk 3 Disk 4
Block 1
Block 2
Block 3
D4 D5
D7 D9
P2 D6
P3 D8
Block 3 P4 D10 D11 D12
D? = Data Block
Figure 10: Small accesses requiring disjunct sets of disks can be scheduled and completed in parallel
When a write or read request is issued, the sequence of events illustrated in Figures 11 and
12occur. The SCSI speci¯cation states that communication on the bus is asynchronous, and up to
256 SCSI commands can be relayed to any given device at once. This basically allows for multiple
requests to be passed to the RAID controller, which is then free to service them in whatever order is
most e±cient. This reordering does not allow requests to be served in parallel, however, since they
Worker Disk
Individual Disk
Block Read Request
Data from
Stripe Blocks
Block Read Result
Read Result
Read Request
To Stripes
Figure 11: Time sequence of events for a Read-request in a RAID system in normal mode
are treated as atomic, although it can reduce overall service time. Similar functionality is available
in SATA but not in IDE.
3.3 RAID System Connection to Host
A read/write request is passed to the RAID controller as a set of IDE or SCSI commands, depending
on the bus used. These commands are then translated by the RAID controller, using its knowledge
of the array con¯guration, which sends a stream of commands to the individual disks in the array.
These disks are also connected to the controller using IDE or SCSI interfaces. This allows commodity
disks to be attached to the array, without need for special alterations or hardware, thus complying
with the Inexpensive Disks part of the name. Having completed the relevant operations necessary
to serve the request, the controller sends a series of responses back along the connection interface.
At this level, access is identical to that for a single disk.
Block Write Result
Worker Disk
Individual Disk
Write Request
To Stripes
Read Old
Data and Parity
Block Read Request
Block Read Result
New Parity
Data, Old Parity,
Calculate New
Parity from Old
Write New Data
and Parity
Block Write Request
Figure 12: Typical events and communications for a Write request in a RAID in normal mode
3.4 Operation of the RAID Controller
In order for the RAID Storage System to appear like a single disk to the operating system, it
is necessary that the disk array be mapped onto a virtual disk. This can either be achieved by
creating speci¯c parameters (capacity, number of cylinders, tracks and heads) describing the disk,
or by using the Logical Block Addressing (LBA) scheme. LBA is the preferred method, and maps
data on a disk to a sequential series of equal sized blocks. Thus, requests to the RAID storage are
for a speci¯c sequence of blocks on the virtual disk.
It is the responsibility of the RAID storage controller to take these requests and translate them
to the physical storage. Each logical block requested may map to one or more stripe block and the
entire set of blocks requested may map to multiple stripes. To handle this, the controller must:
{ calculate the correct mapping from logical blocks to physical blocks;
{ issue commands to the drives requesting reads or writes;
{ collate the received data and return it to the host over the communication channel.
The commands issued to the drives are of the same type issued to the RAID (they both use one
of 2 interfaces) and are automatically handled by the drives.
In addition, the RAID controller is responsible for the following operations:
3.4.1 Caching
The RAID controller maintains a cache of instructions for each drive in the array. These caches
are ¯lled when requests are translated, and are sent to each drive sequentially as execution of the
previous instruction completes. Additionally, a bu®er is present where data to be written can be
temporarily stored or data that is being read from di®erent disks can be reassembled. There have
also been implementations where caches have been used in a similar strategy to virtual memory
systems, with predictive pre-fetching of stripes and so on.
3.4.2 Scheduling
Scheduling of accesses is also the responsibility of the RAID controller. It is necessary to establish
what order the outstanding requests to the RAID should be executed in for maximal e±ciency. This
is particularly true of SCSI RAID controllers, which can accept multiple, parallel requests. However,
it is also necessary to decide how the actions necessary for a given request should be scheduled.
For instance, 2 reads from a RAID 1 can be scheduled simultaneously if each read is directed to
a di®erent drive. Additionally, 2 (or more) small, non-overlapping reads from a RAID 5 can also
be scheduled simultaneously (see Figure 10). These accesses can be scheduled and completed in
3.4.3 Parity Calculation
Parity calculations are the responsibility of the RAID controller. For read requests, parity calcula-
tions are unnecessary unless the controller detects that one of the disks has failed. In this case, the
array operates in degraded mode, and all parity and data on the failed disk is calculated on the °y
using the remaining disks. For write requests, parity calculation is a necessity. Depending on the
size of the request, di®erent strategies can be used:
{ If the write request is a full stripe, the new parity can simply be calculated from the new
data, and written to disk at the same time as the data.
{ Otherwise, the blocks to be written, as well as the parity block, are read in. The old data
is XORed with the new data, then XORed with the old parity, and then both new data and
parity are written to disk.
{ If more than half the blocks in the stripe are to be written, it is more e±cient to read the
blocks that are not going to be written, XOR them with the new data and old parity, and then
write new data and parity to disk. This reduces the total number of disk accesses slightly.
4 RAID Performance
There are a number of areas where the di®erent RAID systems have di®erent behavior. These areas
usually include: Reliability; recovery and repair after disk failure; design and correctness of RAID
controllers and architectures; and performance of RAID architectures under speci¯c workloads areas.
The following is a summary of the most important aspects of these areas and related work.
4.1 RAID Workloads
A severe problem with RAID systems arises in their applicability to On-Line Transaction Processing
(OLTP) systems. These systems have disk access patterns that typically consist of read-modify-write
cycles. With the exception of RAID 1, this causes several problems for a RAID system. Firstly, a
write in a striped array requires reads of both data and parity blocks, computation of a new parity,
and writes of both new data and new parity . . . 4 times more accesses than for a single disk. Another
problem is that these accesses are small, and hence only a few blocks within a speci¯c stripe are
altered, yet the parity disk for the entire stripe is unavailable during the update - this e®ectively
reduces the performance of the array, by reducing the parallelism possible.
This problem was initially tackled by [Seltzer et al. 1993], who proposed a system wherein writes
were bu®ered until a su±ciently deep queue had developed to minimize the write penalty. The
problem with this approach is that a disk failure could lead to data loss unless the bu®ers used
are themselves fault tolerant. The work of [Menon and Mattson 1992] tries to solve this problem
using a technique referred to as Floating Data and Parity. Each cylinder in a disk is set to contain
either data or parity, and for each such cylinder, an empty track is set aside. During the update
cycle, rather than overwrite the old data, the new data is instead written to the rotationally closest
free block. This allows the read-compute parity-write to be executed without an extra rotational
delay. The main problem with this approach is that undermines large block reads, since logically
sequential data need not necessarily be stored sequentially on the disk.
The overhead required by this scheme is very low, but fault tolerant array controller storage
is required to track data and parity locations. Variations on this technique are the log structure
¯lesystem (LFS) [Rosenblum and Ousterhout 1992] and the distorted mirror approach [Solworth
and Orji 1991], which uses the 100% overhead of mirroring to maintain a copy of each lock in both
¯xed and °oating storage. All the above schemes require signi¯cant amounts of controller memory
to handle bu®ering and storage location information.
The most promising solution thus far seems to be the work of [Stodolsky et al. 1993; Stodolsky
et al. 1994]. They present a system wherein parity updates are bu®ered, then written to a log when
su±cient are accumulated to allow for e±cient disk transfer - data updates are written immediately.
This log is then periodically purged, with all parity updates in it being written to disk. This scheme
ensures data reliability, since if a data disk fails it can be recovered from the parity and remaining
data disks; if the parity or log disk fails, then the parity disk can be reconstructed from the remaining
data disks, and the log disk can be emptied.
One problem with this approach is that unless the array controller has fault tolerant bu®ers, a
failure could result in data loss. Another is that the log disk could easily become a bottleneck in
the system - this can be solved by distributing the log disk across all disks, much as is done with
the parity disk in RAID 5. The most problematic aspect of this approach, and one that does not
appear to have been addressed, is how user response will degrade during reconstruction of a failed
disk. Various schemes to address this for other RAID con¯gurations are presented in Section 4.3.
RAID Con¯guration Large Read Large Write Small Read Small Write
RAID 0 +++ +++ +++ +++
RAID 1 + + ++ ++
RAID 2 - 4 ++ ++ - {
RAID 5 ++ ++ + +
Table 1: Performance of RAID Variations under various Workloads
A fairly recent optimization for short transaction workloads presented in [Haruo 2000], Fault-
tolerant Bu®ering Disks, uses disks to provide double bu®ering, which increases write speed, as
well as backup for fault tolerance and read speed improvements. The system does not scale well,
and has a higher overhead than other systems, but for small arrays increases both throughput and
response time.
4.2 Encoding
Encoding is used to guard against single disk failures using parity. The scheme uses the XOR © operator on all blocks in a stripe to determine their parity, which is then stored to enable error
recovery. The XOR operator is typically applied to corresponding bits in each block as follows:
10011 © 01101 = 11110 (parity)
EVENODD [Blaum et al. 1994] encoding builds on the simple parity encoding above. It applies
the same technique, but in 2 di®erent passes. The ¯rst pass calculates a horizontal parity value
across all blocks in a stripe. The second pass calculates a diagonal parity across stripes and disks.
The combination of these 2 parities allow EVENODD to recover from 2 disk failures in the array.
Later extensions to this technique allow recovery from any number of disk failures, but the greater
the redundancy, the greater the number of parity disks required.
DATUM [Alvarez et al. 1997] uses an Information Dispersal Algorithm to allow a RAID array to
survive n failures using exactly n redundant parity disks. It uses a transformation of the form:
(d1; d2; : : : ; dm) ¢ T = (e1; e2; : : : ; em+n)
where m is the number of data blocks to be written, n is the number of redundant disks (and the
number of failures survived) and T is a transformation matrix. dn represent blocks of data and en
the transformed data which is written back to disk. One possible problem with this method is that
¯nding T for any general case is not simple, especially if the actual data is required to be unchanged
when written to disk (ie. di = ei; 1 · i · m). However, it does scale well and uses the minimal
number of redundant disks.
4.3 Reliability
Due to their decreased MTTF, preventing data loss in RAID systems is a very important consider-
ation. Redundancy is the primary fail safe, and many schemes exist to achieve this. Immediately
after a failure, it is necessary to perform some form of recovery. Finally, the failed disk needs to
be replaced and reconstructed to restore the system to full working e±ciency. This section covers
advances in these areas.
4.3.1 Recovery
Recovery is necessary after a disk failure, to ensure that operations in progress at that time are not
lost completely. There are currently three approaches to this problem. The ¯rst and most prevalent
solution, forward error correction (FEC), attempts to handle errors dependent on the current state
of the system and the state of execution of the requested disk operation. This method requires
enumeration of all possible states of the system, and handcrafting execution paths for each. This
is both time-consuming and error prone.
An alternate approach, backward error recovery (BEC)[Courtright II and Gibson 1994], uses an
approach popular in transactional systems which are required to support atomicity of operations.
The approach is to set out a small number of execution paths for each of the possible states of the
system such as error-free, disk failed, etc. Each execution path is composed from a set of simple,
reversible operations, which are logged as they execute. When a failure occurs during execution of
one of these paths, the execution is rolled-back by executing the inverse operations in reverse order.
When the original state is recovered, an alternate execution path, appropriate to the current state
of the system, is used to retry the failed operation.
The ¯nal alternative, roll-away error recovery (REC)[Courtright II 1997], uses a similar scheme to
backward error recovery, but adds commit barriers to simulate two-phase commit in transactional
systems. The idea is that when a failure occurs, execution is allowed to continue up to a commit
barrier, but not beyond. If the completed state is not reached by this, then an alternate execution
path is chosen, and the operation is re-attempted. This style of error recovery is popularized by
the RAIDframe system [Courtright II et al. 1996a] (see Section 5).
4.3.2 Reconstruction
A major consideration when recovering from a failed disk is the e®ect on user response times, i.e.,
does the reconstruction of the failed disk degrade the performance of the RAID? Normally this is
very true, since reconstructing any single disk requires access to all the other disks to reconstruct
every stripe, e®ectively rendering the RAID inaccessible during each such access. While stripe
reconstruction can be interleaved with user requests to allow the RAID to continue operation,
access latency will rise unacceptably and the Mean Time to Repair (MTTR) will increase. The
longer it takes to repair the RAID, the more likely it is a second disk will fail before the ¯rst is
recovered, resulting in data loss.
An innovative solution to this is presented in [Holland and Gibson 1992; Holland et al. 1993;
Holland et al. 1994; Holland 1994]. The authors suggest that performance degradation during
reconstruction can be reduced by sacri¯cing some of the data capacity of the RAID toward redun-
dancy. The crux of their work is the idea of a virtual topology that is mapped to the physical disk
topology of the system. Assuming that there are 7 disks available, the normal, intuitive solution
would be to treat all 7 as a large array with striping across all 7, and distributed parity. An alter-
native would be to treat this as an array of 4 disks, in a RAID 5 con¯guration. To allow this, the
authors discuss ways of mapping such a virtual topology to the physical one.
The bene¯t of this approach is that if a single disk fails, only particular stripes in the virtual array
will be a®ected. Importantly, since each stripe only consists of 4 virtual disks, reconstructing a®ected
stripes only requires read accesses to 3 other real disks. This greatly diminishes the bandwidth
required for reconstruction, and allows accesses to the other 34 disks to occur simultaneously.
4Remember that one disk has failed, and is in the process of being reconstructed
Additionally, the mapping scheme mentioned above ensures that the virtual sectors are uniformly
distributed, thus ensuring that no single disk gets overburdened during reconstruction. The only
requirement is increased redundancy overhead, since instead of a ratio of 6:1 of data:parity sectors,
the ratio is now 3:1.
The latest development in this ¯eld is something called data-reconstruction networks [Haruo
2000]. The idea is that disks are connected in subnetworks which are then interconnected to form
one large network. Reconstruction of a single failed disk is localized to a subnetwork, hence reducing
the impact on the whole network. Additionally, the overlapping of subnetworks allows the recovery
of more than one disk failure, depending on the architecture.
Other considerations during reconstruction are how to handle user requests. If a read is requested
of an as yet unreconstructed sector, the sector can recovered on the °y using parity and the remaining
data disks. However, once this data is calculated, the option arises to store it (which requires
bu®ering), write it to disk (which could upset the scheduling algorithm in use) or discard it (which
entails having to recalculate it later during the reconstruction). The choice of which approach to
take is dependent on the implementation.
If a write is requested during reconstruction, then this new value is simply written to replacement
disk, and the appropriate stripe is excluded from the rebuild list, which reduces reconstruction time.
Alternatively, all stripes are reconstructed in order, and new data is simply overwritten - this has
the advantage of signi¯cantly less bookkeeping, but there is a lot of unnecessary work performed.
5 RAID Performance Modelling
As RAID architectures are being developed, their performance is analyzed using either simulation
or analytical methods. Simulators are generally handcrafted, which entails code duplication and
potentially un reliable systems as outlined in [Holland and Gibson 1992]. Equally problematic is
that RAID architectures, once de¯ned, are di±cult to prove correct without extensive simulations.
One general solution is presented in [Courtright II et al. 1996b] and [Courtright II et al. 1996a].
These papers outline the design of RAIDframe, an application with a graphical interface that
enables structured speci¯cation of RAID architectures, as well as detailed testing using built-in
disk simulators or running the same code as real-world disk drivers. The system uses Directed
Acyclic Graphs (DAG) to de¯ne RAID architectures in terms of primitive operations, together with
the roll-away error recovery scheme, to enable quick development and testing. The system has
shown exceptional code reuse, and has been utilized by other, independent researchers, eg. [Alvarez
et al. 1997].
As a ¯rst step towards systematic proofs of correctness, the work of [Vaziri et al. 1997] identi¯es
key properties of RAID algorithms that need to be veri¯ed. Additionally, I/O automata and key
invariants are used to illustrate how RAID architectures can be proven or errors detected.
5.1 Analytical Modelling
Analytical models of RAID operations generally utilize drive characteristics to model typical oper-
ations [Stodolsky et al. 1993]. Key factors such as Seek Time (time to move to a speci¯ed track),
Rotational Latency (time to rotate disk to required sector) and Transfer Time (time to read or
write to disk) are used to derive mathematical expressions of the time taken for di®erent opera-
tions. Such expressions are usually independent of any particular hardware, and are derived from
analysis of typical actions performed during a given RAID operation. Such an approach is taken in
the work of [Lee and Katz 1993]. Most analytical models of RAID are based on other models of the
underlying disks driving the array, such as the work of [Ruemmler and Wilkes 1994]. Using these
drive characteristics, queuing models can be introduced to model the arrival of tasks at each disk
in a RAID, as such tasks are handed out by the RAID controller. Combining these queued disks
with arrival rates for a single disk in normal operation provides a starting point from which more
complicated RAID systems can be modelled.
5.2 Simulation
The most notable simulation tool for RAID systems is the previously mentioned RAIDframe system
[Courtright II et al. 1996a]. The system o®ers multiple ways to test any RAID architecture using
the previously mentioned, generic DAG representation. The simulator is able to use utilization data
gathered from real world systems to feed in to the simulator as well as accepting real requests from
outside systems. It can also be used to generate a Linux software driver to test an architecture in a
real world system. One downside to this approach is that, since all RAID operations are performed
in software, the controller software can easily become a bottleneck (up to 60% of total processing
due to software) and hence skew the results.
Another simulation tool presented in the literature (and available for academic use) is the RAID-
Sim application [Courtright II et al. 1996b]. It is built on top of a simulator for single disks, known
as DiskSim, developed at the University of Michigan. Unlike RAIDframe, RAIDSim is labelled as
very di±cult to use, and has no generic interface. One other tool the authors are aware of is Sim-
SAN, an environment for simulating and analyzing Storage Area Networks in which RAID usually
serves as the underlying storage.
Alvarez, G. A., Burkhard, W. A., and Cristian, F. 1997. Tolerating multiple failures
in RAID architectures with optimal storage and uniform declustering. In Proceedings of the
24th Annual International Symposium on Computer Architecture, IEEE Computer Society Press,
Blaum, M., Brady, J., Bruck, J., and Menon, J. 1994. Evenodd: An optimal scheme for
tolerating double disk failures in raid architectures. In Proceedings of the 21st Symp. on Computer
Architecture, 245{254.
Britton, D., and Gray, J. 1988. Disk shadowing.
Courtright II, W. V., and Gibson, G. A. 1994. Backward error recovery in redundant disk
arrays. In Proceedings of the 1994 Computer Measurement Group Conference (CMG), vol. 1,
Courtright II, W. V., Gibson, G., Holland, M., and Zelenka, J. 1996. Raidframe: rapid
prototyping for disk arrays. In Proceedings of the 1996 Conference on Measurement and Modeling
of Computer Systems (SIGMETRICS), vol. 24, 268{269.
Courtright II, W. V., Gibson, G., Holland, M., and Zelenka, J. 1996. A structured
approach to redundant disk array implementation. In Proceedings of the International Computer
Performance and Dependability Symposium (IPDS).
Courtright II, W. V. 1997. A Transactional Approach to Redundant Disk Array Implementation.
Master's thesis, Carnegie Mellon University.
Haruo, I. P., 2000. Performance and reliability of secondary storage systems.
Hellerstein, L., Gibson, G. A., Karp, R. M., Katz, R. H., and Patterson, D. A. 1994.
Coding techniques for handling failures in large disk arrays. Algorithmica 12, 2/3, 182{208.
Holland, M., and Gibson, G. A. 1992. Parity declustering for continuous operation in redun-
dant disk arrays. In Proceedings of the 5th Conference on Architectural Support for Programming
Languages and Operating Systems, 23{35.
Holland, M., Gibson, G. A., and Siewiorek, D. P. 1993. Fast, on-line failure recovery
in redundant disk arrays. In Proceedings of the 23rd Annual International Symposium on Fault-
Tolerant Computing.
Holland, M., Gibson, G. A., and Siewiorek, D. P. 1994. Architectures and algorithms for
on-line failure recovery in redundant disk arrays. Journal of Distributed and Parallel Databases
2, 3 (July), 295{335.
Holland, M. C. 1994. On-Line Data Reconstruction In Redundant Disk Arrays. Master's thesis,
Carnegie Mellon University.
Lee, E. K., and Katz, R. H. 1993. An analytic performance model of disk arrays. In Proceedings
of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems,
ACM Press, 98{109.
Menon, J., and Mattson, D. 1992. Performance of disk arrays in transaction processing
environments. In 12th International Conference on Distributed Computing Systems, 302{309.
Patterson, D. A., Gibson, G., and Katz, R. H. 1988. A case for redundant arrays of
inexpensive disks (raid).
Patterson, D. A., Chen, P., Gibson, G., and Katz, R. H. 1989. Introduction to redundant
arrays of inexpensive disks (raid).
Rosenblum, M., and Ousterhout, J. K. 1992. The design and implementation of a log-
structured ¯le system. ACM Trans. Comput. Syst. 10, 1, 26{52.
Ruemmler, C., and Wilkes, J. 1994. An introduction to disk drive modeling. IEEE Computer
27, 3, 17{28.
Seltzer, M. I., Bostic, K., McKusick, M. K., and Staelin, C. 1993. An implementation
of a log-structured ¯le system for UNIX. In USENIX Winter, 307{326.
Solworth, J. A., and Orji, C. U. 1991. Distorted mirrors. In Proceedings of the ¯rst interna-
tional conference on Parallel and distributed information systems, IEEE Computer Society Press,
Stodolsky, D., Gibson, G., and Holland, M. 1993. Parity logging overcoming the small write
problem in redundant disk arrays. In Proceedings of the 20th annual international symposium on
Computer architecture, ACM Press, 64{75.
Stodolsky, D., Holland, M., Courtright II, W. V., and Gibson, G. A. 1994. A
redundant disk array architecture for e±cient small writes. Tech. Rep. CMU-CS-94-170.
Vaziri, M., Lynch, N. A., and Wing, J. M. 1997. Proving correctness of a controller algorithm
for the RAID level 5 system. In Symposium on Fault-Tolerant Computing, 16{25.

RAID data recovery, Mac data recovery, Unix data recovery, Linux data recovery, Oracle data recovery, CD data recovery, Zip data recovery, DVD data recovery , Flash data recovery, Laptop data recovery, PDA data recovery, Ipaq data recovery, Maxtor HDD, Hitachi HDD, Fujitsi HDD, Seagate HDD, Hewlett-Packard HDD, HP HDD, IBM HDD, MP3 data recovery, DVD data recovery, CD-RW data recovery, DAT data recovery, Smartmedia data recovery, Network data recovery, Lost data recovery, Back-up expert data recovery, Tape data recovery, NTFS data recovery, FAT 16 data recovery, FAT 32 data recovery, Novell data recovery, Recovery tool data recovery, Compact flash data recovery, Hard drive data recovery, IDE data recovery, SCSI data recovery, Deskstar data recovery, Maxtor data recovery, Fujitsu HDD data recovery, Samsung data recovery, IBM data recovery, Seagate data recovery, Hitachi data recovery, Western Digital data recovery, Quantum data recovery, Microdrives data recovery, Easy Recovery, Recover deleted data , Data Recovery, Data Recovery Software, Undelete data, Recover, Recovery, Restore data, Unerase deleted data, unformat, Deleted, Data Destorer, fat recovery, Data, Recovery Software, File recovery, Drive Recovery, Recovery Disk , Easy data recovery, Partition recovery, Data Recovery Program, File Recovery, Disaster Recovery, Undelete File, Hard Disk Rrecovery, Win95 Data Recovery, Win98 Data Recovery, WinME data recovery, WinNT 4.x data recovery, WinXP data recovery, Windows2000 data recovery, System Utilities data recovery, File data recovery, Disk Management recovery, BitMart 2000 data recovery, Hard Drive Data Recovery, CompactFlash I, CompactFlash II, CF Compact Flash Type I Card,CF Compact Flash Type II Card, MD Micro Drive Card, XD Picture Card, SM Smart Media Card, MMC I Multi Media Type I Card, MMC II Multi Media Type II Card, RS-MMC Reduced Size Multi Media Card, SD Secure Digital Card, Mini SD Mini Secure Digital Card, TFlash T-Flash Card, MS Memory Stick Card, MS DUO Memory Stick Duo Card, MS PRO Memory Stick PRO Card, MS PRO DUO Memory Stick PRO Duo Card, MS Memory Stick Card MagicGate, MS DUO Memory Stick Duo Card MagicGate, MS PRO Memory Stick PRO Card MagicGate, MS PRO DUO Memory Stick PRO Duo Card MagicGate, MicroDrive Card and TFlash Memory Cards, Digital Camera Memory Card, RS-MMC, ATAPI Drive, JVC JY-HD10U, Secured Data Deletion, IT Security Firewall & Antiviruses, PocketPC Recocery, System File Recovery , RAID