Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
1998-12-31
2001-12-04
Ray, Gopal C. (Department: 2181)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C711S114000
Reexamination Certificate
active
06327672
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to the area of computer data storage protection system. More specifically, this invention relates to the area of computer storage protection known as Redundant Array of Inexpensive Disk (RAID) Systems.
A variety of systems have been developed in the past that allow one to protect stored data in what is commonly referred to as a Redundant Array of Inexpensive Disks (RAID). This RAID technology has utilized several forms in the past. For example, a RAID zero system breaks data down into blocks and writes the blocks to separate disk drives. In this approach, if a single drive fails, all data that was stored on that drive will be lost. Therefore, when a drive is lost, only a portion of the data is lost. This is not a true RAID system, because it is not a fault tolerant system. Nevertheless, the data transfer capacity and I/O rate is very high for both reads and writes.
A second version of RAID is known as RAID 1 or mirroring. RAID 1 involves a mirroring or replicating of data on one drive to a duplicate drive. In this way, an exact duplicate of the data on a disk drive is accomplished on a redundant drive. As one can imagine, this is a very expensive way to back up data. In addition, the I/O rate for writes is slower than that of a single disk system. RAID 1 is frequently combined with RAID zero so that data is striped across pairs of drives. This approach can tolerate multiple drive failures, provided the failed drives do not compose a mirrored pair. However, if both drives in a mirrored pair fail, the data will be lost.
Yet another version of RAID technology is commonly referred to as RAID 2. RAID 2 utilizes a Hamming error correction code to protect data stored on the data drives. In this way, data distributed over several different disk drives can be protected through a parallel storage of error correction code information stored on additional drives. One drawback to RAID 2 is that it requires a very high ratio of error correction code drives to data drives.
Yet another RAID technology that has been proposed is RAID 3. RAID 3 subdivides the data blocks and writes those subdivisions onto separate data drives. This is commonly referred to as striping the data across the data drives. In addition to the striping, parity information is calculated and stored on a parity drive. Therefore, for every stripe of data, a corresponding block of parity information can be stored. In this manner, RAID 3 allows a lost drive of stored information to be recovered utilizing the remaining drives and the parity information. However, if two drives fail, e.g., a parity drive and a data drive, the entire storage system fails.
Another RAID technology is commonly referred to as RAID 4. RAID 4 is similar to RAID 3 except that rather than striping the data across several different disk drives, a block of data is stored on a single disk drive and additional blocks of data are stored on the additional disk drives. Then, parity information is calculated using the several independent blocks of information stored on the various disk drives. Again, as was the case in RAID 3, if a disk drive fails, the remaining disk drives and the drive that contains the parity information can be utilized to recover lost data that was stored on the failed drive. Once again, however, if any two drives should fail, then the entire system fails.
RAID 5 is yet another RAID technology that is utilized to protect data. RAID 5 uses parity information in addition to the distribution of blocks of data across several disk drives. However, in contrast to RAID 4 which stored all of the parity information on a single disk drive, RAID 5 spreads the parity information across the data drives themselves. In this way, parity information for a first row of information can be stored in the first row of the last data drive. Parity information for a second row of data can be stored in the second row of the second to the last data drive and so forth. This technique distributes the parity information across several data drives but the manner of recovering lost data with a parity scheme remains the same. Once again, loss of any two drives causes the entire storage system to fail.
RAID 6 is essentially an extension of RAID 5. It allows two parity calculations to be made for the data stored on the various data drives. For example, in RAID 6, two sets of parity information can be calculated for blocks of data stored in an array. Parity information can be calculated for each column of data blocks as well as each row of data blocks. Both of these sets of parity information can be distributed on the various disk drives as was done in the RAID 5 configuration. RAID 6 requires extensive controller overhead, however, in order to compute the parity addresses distributed throughout the array of drives.
As can be seen from the various RAID techniques that have been used in the past, none has been a perfect solution to the variety of protection needs that exist in the computer industry. Depending on the application of the data, there will be varying needs for protecting data. For example, some data will be so important that a very reliable fault tolerant system needs to be in place to protect the data. A system that is simple to implement and involves an uncomplicated design is preferable, as well.
SUMMARY OF THE INVENTION
The present invention provides an inventive method and apparatus to overcome problems of existing data backup systems. Various embodiments of the invention serve to protect data when more than one drive fails. In addition, one embodiment of the invention helps to allow a designer to determine an optimum number of drives that can be used in various data protection schemes. A designer can calculate the maximum number of data drives that can be protected by a given number of check drives. In addition, one embodiment of the invention permits a recovery of data by a method that allows chaining back through failed drives. Furthermore, another embodiment of the invention allows a check drive to be converted into a data drive so as to enhance data recovery and storage when a data drive fails or is unaccessible.
The invention can utilize an array of redundant data drives to accomplish data storage. In a unique manner, the invention can employ at least two check disks on which check information—such as parity information—can be stored. In this manner, the check drives can allow at least two data drives to fail and still permit the recovery of the information stored on the failed data drives.
A unique configuration of the invention provides at least two check drives per data drive in a chained configuration. In this configuration, a loss of more than one data drive allows the data to be recovered by chaining back to recalculate a failed drive using the two check drives and existing data drives that have not failed. In this manner, the data for each failed drive can be determined and then again utilized to calculate the data for a failed drive that neighbors the first failed drive. This chain configuration therefore allows numerous data and parity drives to fail while still permitting reconstruction of the data on the failed drives.
Another embodiment of the invention utilizes or permits calculation of the number of data drives that can be protected with a given number of check drives and a known number of failed drives. In this manner, the amount of check information overhead can be decreased to the least amount necessary to accomplish the backup function.
In another embodiment of the invention, a failed data drive can be replaced in the backup system by an existing check drive. The check drive then becomes a data drive and the lost data can be stored on this new data drive. While the ideal backup features of this configuration may then be lost, the old check drive
ew data drive serves as a stopgap measure until a convenient time when the failed data drive can be replaced or brought on-line. In this way, the speed of the data drive configuration can be regained while data backup is carried out b
LSI Logic Corporation
Ray Gopal C.
Townsend and Townsend and Crew L.L.P.
LandOfFree
Multiple drive failure tolerant raid system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple drive failure tolerant raid system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple drive failure tolerant raid system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2593418