RAID: High-Performance, Reliable Secondary Storage P. Chen, E. Lee, G. Gibson, R. Katz, and D. Patterson (This paper was written in 1994, as a summary of experience of work done on RAID since the original '88 paper. Motivation: CPU and Memory are getting faster quickly. Disks (especially * disk latencies) are not keeping up. Big Idea: We can use arrays of disks to create storage devices that are: * larger: more disks stores more data * faster: use disk striping for performance * more reliable: advantage of data redundancy Larger: * the more disks we have, the greater the odds of one of them failing. (This greatly motivates redundancy). Disk Striping: * distributes data transparently over multiple disks. * multiple independent requests can be serviced by different disks. This reduces queing time of i/o requests. * single multi-block requests can be serviced by coordinated disks. This increases effective bandwidth of transfer. * most raid organizations can be distinguished based on 1) granularity of data interleaving -> finer granularity uses more disks for greater bandwidth, but restricts # of simultaneous requests -> coarser granularity uses fewer disks, more simultaneous requets. 2) method and pattern of distributing data across disks Redundancy: * First: how do we compute redundant information? Most use parity bits. Some use Hamming or Reed-Solomon codes. * 2nd: how do we distribute redundant data? -> some concentrate redundant data on a small # of disks -> others distribute redundant data ~uniformly !Concepts are simple, but choosing between the different schemes of striping and redundancy are complex! The right choice depends on the application using the disk array, and whether they need raid for performance, reliability, or storage space concerns. RAID Types: * 7 levels of RAID (1-5 is original, 0 and 6 added later) * 0 (Nonredundant): employs no redundancy. good performance. * 1 (mirrored): stores everything twice. not as good performance. * 2 (Memory-Style ECC) * 3 (Bit-interleaved Parity) * 4 (Block-Interleaved Parity) * 5 (Block-Interleaved Distributed Parity) * 6 (P+Q redundancy): protects against up to two disk failures using Reed-Solomon codes. RAID level 1 and 3 are subclasses of level 5. RAID level 2 and 4 are in all practical cases inferior to 5. -> Selecting among raid levels is really a problem of choosing which parity group size and striping unit size to use for a level 5 RAID Small Write Problem: Small writes are expensive due to cost of reading all data, calculating parity, and writing changed block and parity out again. -> can buffer writes and cache reads. -> can calculate a "floating parity", or log it to a more convenient place -> can use log-based file systems that don't do "small writes"