Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-08-11
2003-03-04
Lane, Jack A. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
Reexamination Certificate
active
06529997
ABSTRACT:
FIELD OF THE INVENTION
The present invention is directed to an apparatus and method for writing and reading data to and from a virtual volume of redundant storage devices. In particular, the present invention is directed to an apparatus and method in which metadata is stored for every block in a superblock written to a plurality of physical storage devices, such that a data volume may be easily rebuilt from any arbitrary subset of the redundant storage devices.
BACKGROUND OF THE INVENTION
To improve the performance of removable media, such as magnetic tapes and magnetic disks, the most efficient and known method is to build a Redundant Array of Independent Removable (RAIR) storage devices. Such arrays can provide increased throughput by striping data over multiple media located in multiple redundant storage devices. Additionally, these arrays of redundant storage devices can provide increased reliability by adding a parity mechanism used to correct for errors in reading/writing data to the media.
Redundant Array of Independent Tape (RAIT) systems are the tape implementation of a RAIR storage system. RAIT systems use a plurality of tape drives to improve the performance and reliability of the storage medium. Data may be striped across many tape drives to increase performance. However, the drawback is that any tape error renders the complete stripe group unreadable. Thus, when a storage device in the array of redundant storage devices fails, the data being written to or read from the failed storage device must be reconstructed.
A method for reconstructing missing data using cross-parity stripes on a storage medium, such as magnetic tape media, is described in commonly assigned and co-pending U.S. patent application Ser. No. 09/490,258 entitled “Apparatus and Method for Reconstructing Missing Data Using Cross-Parity Stripes on Storage Media” filed Jan. 24, 2000, which is hereby incorporated by reference. The apparatus and method described in U.S. patent application Ser. No. 09/490,258 makes use of a plurality of parity stripes for reconstructing missing data stripes. The parity symbol values in the parity stripes are used as a basis for determining the value of the missing data symbol in a data stripe. A correction matrix is shifted along the data stripes, correcting missing data symbols as it is shifted. The correction is performed from the outer most data stripes towards the inner data stripes to thereby use previously reconstructed data symbols to reconstruct other missing data symbols.
The data is reconstructed by organizing the received parity stripes in order. The smallest slope diagonal lines of the correction matrix, representing the linear equations of the parity symbols, may be used to correct the top and bottom most missing data stripes as deep as is necessary. Once the top and bottom most data stripes are corrected, the next largest slope lines may be used to correct the next inner missing data stripe and so forth until all the missing data stripes are corrected.
The use of parity stripes and parity symbols to reconstruct missing data, while beneficial, may greatly reduce the throughput of the overall RAIR system. Thus, it would be beneficial to have an apparatus and method that compensates for failures in storage devices without compromising the throughput of the overall RAIR system. In addition, it would be desirable to be able detect and reconstruct the failures in the system offline to the actual processing of the data in behalf of a using application.
SUMMARY OF THE INVENTION
The present invention provides apparatus and method for writing and reading data to and from a virtual volume of redundant storage devices. The apparatus and method make use of metadata identifying the number of data storage devices and number of redundancy storage devices in the virtual volume of redundant storage devices. In addition, other metadata, such as the identity of the data storage devices and parity storage devices may be utilized. The metadata is stored with each block written to each of the storage devices. In the event of a failure of a storage device, the metadata is modified to reflect the failure and the storage device to which the data intended for the failed storage device was written. In this way, if a failure of a storage device is encountered, each block in the virtual volume of redundant storage devices has enough information in the metadata to identify where to find the data that was intended for the failed storage device. Thus, reconstruction of data using redundancy information is not required.
REFERENCES:
patent: 5530948 (1996-06-01), Islam
patent: 5960169 (1999-09-01), Styczinski
patent: 6282670 (2001-08-01), Rezaul Islam et al.
Debiez Jacques
Hughes James Prescott
Milligan Charles Allen
Carstens Yee & Cahoon, L.L.P.
Lane Jack A.
Storage Technology Corporation
LandOfFree
Apparatus and method for writing and reading data to and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for writing and reading data to and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for writing and reading data to and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3013850