Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
1993-06-29
2001-07-31
Wright, Norman M. (Department: 2131)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C714S019000, C714S049000, C714S764000
Reexamination Certificate
active
06269453
ABSTRACT:
FIELD OF THE INVENTION
Data storage systems having a plurality of disks using RAID-4 or RAID-5 organizations experience a decrease in performance and reliability and an increase in the cost of operation of the array when one of the disks in the array fails and has not yet been replaced. The present invention is a method of reorganizing the data on the RAID array at the time of failure to prevent both a decrease in performance and reliability, and an increase in the cost of operation.
BACKGROUND OF THE INVENTION
RAID (Redundant Array of Independent/Inexpensive Disks) is an organization of data on a plurality of disks to achieve varying levels of availability and performance. One performance enhancing feature of RAID is “striping” which spreads data across the disks in the array. The data is broken down into segments referred to as “chunks.” A chunk is a group of consecutively numbered blocks that are placed consecutively on a single disk before placing blocks on a different disk. A block is the smallest unit of data that can be read or written to a disk. Thus, a chunk is the unit of data interleaving for a RAID array. For example, in a four disk RAID array the first chunk is placed on the first disk, the second chunk is placed on the second disk, the third chunk is placed on the third disk, the fourth chunk is placed on the fourth disk, the fifth chunk is placed on the first disk and so on. This spreading of data increases performance through load balancing.
As is well know, there are several levels of RAID, each of which has different characteristics that affect performance and availability. One common aspect of all RAID levels is that each array appears as one large virtual disk to the user. RAID storage systems can be implemented in hardware or software. In the hardware implementation the RAID algorithms are built into a controller that connects to the computer I/O bus. In the software implementation the RAID algorithms are incorporated into software that runs on the main processor in conjunction with the operating system. Both the hardware and software implementations of RAID are well known to those of ordinary skill in the field.
RAID level 4 (RAID-4) and RAID level 5 (RAID-5) are organizations of data for an array of n+1 disks that provide enhanced performance through the use of striping and enhanced data availability through the use of parity. Each disk in the RAID array is referred to as a member of the array. Furthermore, while disks are referred to throughout, any equivalent storage media could be used as would be apparent to one of ordinary skill in the field. A parity block is associated with every n data blocks. The data and parity information is distributed over the n+1 disks so that if a single disk fails, all of the data can be recovered. A strip is the collection of a parity chunk and all data chunks that contribute to it. RAID-4 is a level of organization of data for a RAID array where data blocks are organized into chunks which are interleaved among the disks and protected by parity and all of the parity, is written on a single disk. RAID-5 is a level of organization of data for a RAID array where data blocks are organized in chunks which are interleaved among the disks and protected by parity and the parity information is distributed over all of the disks in the array. In both RAID-4 and RAID-5 the ensemble or array of n+1 disks appears to the user as a single, more highly available virtual disk.
The contents of each bit of the parity block is the Exclusive-OR of the corresponding bit in each of the n corresponding data blocks. In the event of the failure of a single disk in the array, the data from a given data block on the failed disk is regenerated by calculating the Exclusive-OR of the contents of the corresponding parity block and the n−1 data blocks remaining on the surviving disks that contributed to that parity block. A spare disk may be added to the array to replace the failed disk. A block or set of blocks is repaired by writing the regenerated data. The regeneration and repair of data for a data block or set of data blocks on a disk in a RAID array is referred to as reconstruction.
Under some circumstances a failed disk in the RAID array cannot be reconstructed or replaced promptly. During the time that the failed disk remains out of the RAID array the cost of operations increases and both performance and reliability decrease. Accordingly, if the storage system is to operate for any period of time with a failed disk of the RAID array it is desirable to improve both performance and reliability and prevent an increase in the cost of operation.
SUMMARY OF THE INVENTION
The present invention is a method of preventing an increase in the cost of operation while improving the performance and reliability of a storage system using a RAID-4 or RAID-5 organization of data when one of the disks in the RAID array has failed and has not yet been replaced. The method of the present invention reorganizes the data in the RAID array at the time a disk in the array fails, so that read and write operations to the array require the optimal number of operations and so that the performance of the RAID array and reliability of the data stored on the array is maximized while the cost of operation to the array is minimized. The reorganization is performed on each strip of the array.
The unavailable data for each strip of the array is regenerated using the data from the other chunks of the strip and the parity chunk of the strip by applying the standard RAID algorithms. The regenerated data corresponds to the unavailable data on the failed disk. The regenerated data is then written over the parity information on the parity chunk of the strip. This process is repeated for each strip forming the RAID array. The resulting organization of data is essentially that of a RAID-0 organized array except that the disk on which a chunk of data is stored may be unconventional. RAID-0 is a level of organization of data for a RAID array where the data is non-redundant. The resulting organization of data is referred to as a “fully-folded” RAID array and the process of reorganizing the data on the array is referred to as “folding.”
When a replacement disk is added to a fully folded RAID array to restore the array to a redundant state, the folding process is reversed. For each strip in the array, if the replacement disk should contain parity information, an Exclusive-OR operation computes the parity from the data chunks on the other disks and writes the parity to the replacement disk. If the replacement disk should contain data, the data is read from the disk that originally contained parity and written on the replacement disk, then parity is computed from the corresponding data blocks and written on the appropriate disk.
REFERENCES:
patent: 4092732 (1978-05-01), Ouchi
patent: 4434487 (1984-02-01), Rubinson et al.
patent: 4775978 (1988-10-01), Hartness
patent: 4914656 (1990-04-01), Dunphy et al.
patent: 4989205 (1991-01-01), Dunphy et al.
patent: 4989206 (1991-01-01), Dunphy et al.
patent: 5574851 (1996-11-01), Rathunde
Chen et al., “RAID Hight Performance Reliable Secondary Storage,” ACM Computing Surveys, vol. 26, No. 2, pp. 141-146, 152-158, 164-166, 170-171, and 179-185, Jun. 1994.*
Burkhard et al., “Disk Aray storage system . . . ”, IEEE Computer Society, abstract, Jun. 1993.*
Chandy et al., “Failure evaluation of disk array organization,” IEEE Computer Society, abstract, May 1993.*
G. A. Gibson, “Redundant disk arrays . . . ”, vol. 52/08-b of dissertation abstract international, pp. 4309, 1991.*
A Case for Redundant Array of Inexpensive Disks(RAID), David A. Patterson, Garth Gibson, Randy H. Katz, Report No. UCB/CSD 87/391, Dec., 1987, Computer Science Division (EECS), University of California, Berkeley, CA 94720.
A Case for Redundant Arrays of Inexpensive Disks(RAID), David A. Patterson, Garth Gibson, and Randy H. Katz, ACM SIGMOD Conference—Jun. 1-3, 1988, Chicago, Illinois.
Two Papers on RAIDs, Peter Chen, Garth Gibson, Randy H. Katz, David A. Patterson, Mart
Compaq Computer Corporation
Hogan & Hartson LLP
Kubida William J.
Leaheey J. Bradford
Wright Norman M.
LandOfFree
Method for reorganizing the data on a RAID-4 or RAID-5 array... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for reorganizing the data on a RAID-4 or RAID-5 array..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for reorganizing the data on a RAID-4 or RAID-5 array... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2553556