Redundant Arrays of Inexpensive Disks (RAIDs)

1 38 Redundant Arrays of Inexpensive Disks (RAIDs) When we use a disk , we sometimes wish it to be faster; I/O operationsare slow and thus can be the bottleneck for the entire system. When weuse a disk , we sometimes wish it to be larger; more and more data isbeingput online and thus our Disks are getting fuller and fuller. When we usea disk , we sometimes wish for it to be more reliable; when a disk fails, ifour data isn t backed up, all that valuable data is : HOWTOMAKEA LARGE, FAST, RELIABLEDISKHow can we make a large, fast, and reliable storage system? Whatarethe key techniques? What are trade-offs between different approaches?In this chapter, we introduce theRedundant array of InexpensiveDisksbetter known asRAID[P+88], a technique to use multiple Disks inconcert to build a faster, bigger, and more reliable disk system.

2 The termwas introduced in the late 1980s by a group of researchers at (led by Professors David Patterson and Randy Katz and then studentGarth Gibson); it was around this time that many different researchers si-multaneously arrived upon the basic idea of using multiple Disks to builda better storage system [BG88, K86,K88,PB86,SG86].Externally, a RAID looks like a disk : a group of blocks one can reador write. Internally, the RAID is a complex beast, consisting of multipledisks, memory (both volatile and non-), and one or more processors tomanage the system. A hardware RAID is very much like a computersystem, specialized for the task of managing a group of offer a number of advantages over a single disk . One advan-tage isperformance. Using multiple Disks in parallel can greatly speedup I/O times.

3 Another benefit iscapacity. Large data sets demand largedisks. Finally, RAIDs can improvereliability; spreading data across mul-tiple Disks (without RAID techniques) makes the data vulnerable to theloss of a single disk ; with some form ofredundancy, RAIDs can toleratethe loss of a disk and keep operating as if nothing were OFINEXPENSIVEDISKS (RAIDs) TIP: TRANSPARENCYENABLESDEPLOYMENTWhen considering how to add new functionality to a system, one shouldalways consider whether such functionality can be addedtransparently,in a way that demands no changes to the rest of the system. Requiring acomplete rewrite of the existing software (or radical hardware changes)lessens the chance of impact of an idea. RAID is a perfect example, andcertainly its transparency contributed to its success; administrators couldinstall a SCSI-based RAID storage array instead of a SCSI disk , and therest of the system (host computer, OS, etc.)

4 Did not have to change one bitto start using it. By solving this problem ofdeployment, RAID was mademore successful from day , RAIDs provide these advantagestransparentlyto systemsthat use them, , a RAID just looks like a big disk to the host system. Thebeauty of transparency, of course, is that it enables one to simply replacea disk with a RAID and not change a single line of software; the operat-ing system and client applications continue to operate without modifica-tion. In this manner, transparency greatly improves thedeployabilityofRAID, enabling users and administrators to put a RAID to use withoutworries of software now discuss some of the important aspects of RAIDs. We beginwith the interface, fault model, and then discuss how one can evaluate aRAID design along three important axes: capacity, reliability, and perfor-mance.

5 We then discuss a number of other issues that are important toRAID design and Interface And RAID InternalsTo a file system above, a RAID looks like a big, (hopefully) fast, and(hopefully) reliable disk . Just as with a single disk , it presents itself asa linear array of blocks, each of which can be read or written by thefilesystem (or other client).When a file system issues alogical I/Orequest to the RAID, the RAID internally must calculate which disk (or Disks ) to access in order to com-plete the request, and then issue one or morephysical I/Osto do so. Theexact nature of these physical I/Os depends on the RAID level, as we willdiscuss in detail below. However, as a simple example, considera RAID that keeps two copies of each block (each one on a separate disk ); whenwriting to such amirroredRAID system, the RAID will have to performtwo physical I/Os for every one logical I/O it is RAID system is often built as a separate hardware box, with a stan-dard connection ( , SCSI, or SATA) to a host.

6 Internally, however,RAIDs are fairly complex, consisting of a microcontroller that runs firmwareto direct the operation of the RAID, volatile memory such as DRAMto buffer data blocks as they are read and written, and in some cases,OPERATINGSYSTEMS[ ] OFINEXPENSIVEDISKS (RAIDs) 3non-volatile memory to buffer writes safely and perhaps even special-ized logic to perform parity calculations (useful in some RAID levels, aswe will also see below). At a high level, a RAID is very much a special-ized computer system: it has a processor, memory, and Disks ; however,instead of running applications, it runs specialized softwaredesigned tooperate the Fault ModelTo understand RAID and compare different approaches, we must havea fault model in mind. RAIDs are designed to detect and recover fromcertain kinds of disk faults; thus, knowing exactly which faults to expectis critical in arriving upon a working first fault model we will assume is quite simple, and has beencalled thefail-stopfault model [S84].

7 In this model, a disk can be inexactly one of two states: working or failed. With a working disk , allblocks can be read or written. In contrast, when a disk has failed, weassume it is permanently critical aspect of the fail-stop model is what it assumes about faultdetection. Specifically, when a disk has failed, we assume thatthis iseasily detected. For example, in a RAID array , we would assume that theRAID controller hardware (or software) can immediately observe when adisk has , for now, we do not have to worry about more complex silent failures such as disk corruption. We also do not have to worry abouta sin-gle block becoming inaccessible upon an otherwise working disk (some-times called a latent sector error). We will consider these more complex(and unfortunately, more realistic) disk faults How To Evaluate A RAIDAs we will soon see, there are a number of different approaches tobuilding a RAID.

8 Each of these approaches has different characteristicswhich are worth evaluating, in order to understand their strengths , we will evaluate each RAID design along three axes. Thefirst axis iscapacity; given a set ofNdisks each withBblocks, how muchuseful capacity is available to clients of the RAID? Without redundancy,the answer isN B; in contrast, if we have a system that keeps two copiesof each block (calledmirroring), we obtain a useful capacity of(N B) schemes ( , parity-based ones) tend to fall in second axis of evaluation isreliability. How many disk faults canthe given design tolerate? In alignment with our fault model, weassumeonly that an entire disk can fail; in later chapters ( , on data integrity),we ll think about how to handle more complex failure 2008 20, ARPACI-DUSSEAUTHREEEASYPIECES4 REDUNDANTARRAYS OFINEXPENSIVEDISKS (RAIDs) Finally, the third axis isperformance.

9 Performance is somewhat chal-lenging to evaluate, because it depends heavily on the workloadpre-sented to the disk array . Thus, before evaluating performance, we willfirst present a set of typical workloads that one should now consider three important RAID designs: RAID Level 0 (strip-ing), RAID Level 1 (mirroring), and RAID Levels 4/5 (parity-based re-dundancy). The naming of each of these designs as a level stems fromthe pioneering work of Patterson, Gibson, and Katz at Berkeley [P+88]. RAID Level 0: StripingThe first RAID level is actually not a RAID level at all, in that there isno redundancy. However, RAID level 0, orstripingas it is better known,serves as an excellent upper-bound on performance and capacityandthus is worth simplest form of striping willstripeblocks across the Disks of thesystem as follows (assume here a 4- disk array ): disk 0 disk 1 disk 2 disk 30123456789101112131415 Figure :RAID-0: Simple StripingFrom Figure , you get the basic idea: spread the blocks of the arrayacross the Disks in a round-robin fashion.

10 This approach is designed toextract the most parallelism from the array when requests are made forcontiguous chunks of the array (as in a large, sequential read, for exam-ple). We call the blocks in the same row astripe; thus, blocks 0, 1, 2, and3 are in the same stripe the example, we have made the simplifying assumption that only 1block (each of say size 4KB) is placed on each disk before moving on tothe next. However, this arrangement need not be the case. For example,we could arrange the blocks across Disks as in Figure : disk 0 disk 1 disk 2 disk 30246chunk size:13572 blocks81012149111315 Figure :Striping With A Bigger Chunk SizeIn this example, we place two 4KB blocks on each disk before movingon to the next disk . Thus, thechunk sizeof this RAID array is 8KB, anda stripe thus consists of 4 chunks or 32KB of [ ] OFINEXPENSIVEDISKS (RAIDs) 5 ASIDE: THERAID MAPPINGPROBLEMB efore studying the capacity, reliability, and performance characteristicsof the RAID, we first present an aside on what we callthe mapping prob-lem.