US 5,613,059 AGrant
On-Line Restoration of Redundancy Information in a Redundant Array System
Issue Date:1997-03-18
•62 Claims
•4 Drawing Sheets
Abstract
A method for on-line restoration of redundancy information in a redundant array storage system. The invention provides alternative methods of restoring valid data to a storage unit after a Write failure caused by a temporary storage unit fault. In the first preferred method, a valid redundancy block is generated for the corresponding data blocks on all storage units. Resubmitting the interrupted Write operation causes the old (and potentially corrupted) data block to be "subtracted" out of the re-computed redundancy block. The uncorrupted new data block is written over the old data block, and is "added" into the re-computed redundancy block to create a new, corrected redundancy block. The new, corrected redundancy block is written to the appropriate storage unit. In the second preferred method, a new redundancy block is generated from all valid data blocks and the new data block. The new redundancy block and the new data block are then written to the appropriate storage units. In both cases, the entire method is done on-line, with insignificant interruption of normal operation of the redundant array system, and without requiring added processing during normal operation.
Metadata
Assignee
- EMC Corporation
Inventors
- David C. Stallmo
- William A. Brant
- David Gordon
Application Information
Application Number:US 3497666
Filing Date:1994-12-01
Priority Date:1990-12-21
Art Unit:243
Classifications
IPC:
G06F 1134G06F 1110
Field of Search:
37139510.2;10.3;40.1;40.2;51.1182.03;182.04;182.05;182.06
Patent Drawings (4 sheets)
Description
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to computer system data storage, and more particularly to methods for on-line restoration of parity information in a redundant array storage system.
2. Description of Related Art
A typical data processing system generally involves one or more storage units which are connected to a Central Processor Unit (CPU) either directly or through a control unit and a channel. The function of the storage units is to store data and programs which the CPU uses in performing particular data processing tasks.
Various type of storage units are used in current data processing systems. A typical system may include one or more large capacity tape units and/or disk drives (magnetic, optical, or semiconductor) connected to the system through respective control units for storing data.
However, a problem exists if one of the large capacity storage units fails such that information contained in that unit is no longer available to the system. Generally, such a failure will shut down the entire computer system.
The prior art has suggested several ways of solving the problem of providing reliable data storage. In systems where records are relatively small, it is possible to use error correcting codes which generate ECC syndrome bits that are appended to each data record within a storage unit. With such codes, it is possible to correct a small amount of data that may be read erroneously. However, such codes are generally not suitable for correcting or recreating long records which are in error, and provide no remedy at all if a complete storage unit fails. Therefore, a need exists for providing data reliability external to individual storage units.
Other approaches to such "external" reliability have been described in the art. A research group at the University of California, Berkeley, in a paper entitled "A Case for Redundant Arrays of Inexpensive Disks (RAID)", Patterson, et al., Proc. ACM SIGMOD, June 1988, has catalogued a number of different approaches for providing such reliability when using disk drives as storage units. Arrays of disk drives are characterized in one of five architectures, under the acronym "RAID" (for Redundant Arrays of Inexpensive Disks).
A RAID 1 architecture involves providing a duplicate set of "mirror" storage units and keeping a duplicate copy of all data on each pair of storage units. While such a solution solves the reliability problem, it doubles the cost of storage. A number of implementations of RAID 1 architectures have been made, in particular by Tandem Corporation.
A RAID 2 architecture stores each bit of each word of data, plus Error Detection and Correction (EDC) bits for each word, on separate disk drives (this is also known as "bit stripping"). For example, Flora et al. U.S. Pat. No. 4,722,085 discloses a disk drive memory using a plurality of relatively small, independently operating disk subsystems to function as a large, high capacity disk drive having an unusually high fault tolerance and a very high data transfer bandwidth. A data organizer adds 7 EDC bits (determined using the well-known Hamming code) to each 32-bit data word to provide error detection and error correction capability. The resultant 39-bit word is written, one bit per disk drive, on to 39 disk drives. If one of the 39 disk drives fails, the remaining 38 bits of each stored 39-bit word can be used to reconstruct each 32-bit data word on a word-by-word basis as each data word is read from the disk drives, thereby obtaining fault tolerance.
An obvious drawback of such a system is the large number of disk drives required for a minimum system (since most large computers use a 32-bit word), and the relatively high ratio of drives required to store the EDC bits (7 drives out of 39). A further limitation of a RAID 2 disk drive memory system is that the individual disk actuators are operated in unison to write each data block, the bits of which are distributed over all of the disk drives. This arrangement has a high data transfer bandwidth, since each individual disk transfers part of a block of data, the net effect being that the entire block is available to the computer system much faster than if a single drive were accessing the block. This is advantageous for large data blocks. However, this arrangement also effectively provides only a single read/write head actuator for the entire storage unit. This adversely affects the random access performance of the drive array when data files are small, since only one data file at a time can be accessed by the "single" actuator. Thus, RAID 2 systems are generally not considered to be suitable for computer systems designed for On-Line Transaction Processing (OLTP), such as in banking, financial, and reservation systems, where a large number of random accesses to many small data files comprises the bulk of data storage and transfer operations.
A RAID 3 architecture is based on the concept that each disk drive storage unit has internal means for detecting a fault or data error. Therefore, it is not necessary to store extra information to detect the location of an error; a simpler form of parity-based error correction can thus be used. In this approach, the contents of all storage units subject to failure are "Exclusive OR'd" (XOR'd) to generate parity information. The resulting parity information is stored in a single redundant storage unit. If a storage unit fails, the data on that unit can be reconstructed on to a replacement storage unit by XOR'ing the data from the remaining storage units with the parity information. Such an arrangement has the advantage over the mirrored disk RAID 1 architecture in that only one additional storage unit is required for "N" storage units. A further aspect of the RAID 3 architecture is that the disk drives are operated in a coupled manner, similar to a RAID 2 system, and a single disk drive is designated as the parity unit.
One implementation of a RAID 3 architecture is the Micropolis Corporation Parallel Drive Array, Model 1804 SCSI, that uses four parallel, synchronized disk drives and one redundant parity drive. The failure of one of the four data disk drives can be remedied by the use of the parity bits stored on the parity disk drive. Another example of a RAID 3 system is described in Ouchi U.S. Pat. No. 4,092,732.
A RAID 3 disk drive memory system has a much lower ratio of redundancy units to data units than a RAID 2 system. However, a RAID 3 system has the same performance limitation as a RAID 2 system, in that the individual disk actuators are coupled, operating in unison. This adversely affects the random access performance of the drive array when data files are small, since only one data file at a time can be accessed by the "single" actuator. Thus, RAID 3 systems are generally not considered to be suitable for computer systems designed for OLTP purposes.
A RAID 4 architecture uses the same parity error correction concept of the RAID 3 architecture, but improves on the performance of a RAID 3 system with respect to random reading of small files by "uncoupling" the operation of the individual disk drive actuators, and reading and writing a larger minimum amount of data (typically, a disk sector) to each disk (this is also known as block stripping). A further aspect of the RAID 4 architecture is that a single storage unit is designated as the parity unit.
A limitation of a RAID 4 system is that Writing a data block on any of the independently operating data storage units also requires writing a new parity block on the parity unit. The parity information stored on the parity unit must be read and XOR'd with the old data (to "remove" the information content of the old data), and the resulting sum must then be XOR'd with the new data (to provide new parity information). Both the data and the parity records then must be rewritten to the disk drives. This process is commonly referred to as a "Read-Modify-Write" sequence.
Thus, a Read and a Write on the single parity unit occurs each time a record is changed on any of the data storage units covered by the parity record on the parity unit. The parity unit becomes a bottle-neck to data writing operations since the number of changes to records which can be made per unit of time is a function of the access rate of the parity unit, as opposed to the faster access rate provided by parallel operation of the multiple data storage units. Because of this limitation, a RAID 4 system is generally not considered to be suitable for computer systems designed for OLTP purposes. Indeed, it appears that a RAID 4 system has not been implemented for any commercial purpose.
A RAID 5 architecture uses the same parity error correction concept of the RAID 4 architecture and independent actuators, but improves on the writing performance of a RAID 4 system by distributing the data and parity information across all of the available disk drives. Typically, "N+1" storage units in a set (also known as a "redundancy group") are divided into a plurality of equally sized address areas referred to as blocks. Each storage unit generally contains the same number of blocks. Blocks from each storage unit in a redundancy group having the same unit address ranges are referred to as "stripes". Each stripe has N blocks of data, plus one parity block on one storage unit containing parity for the remainder of the stripe. Further stripes each have a parity block, the parity blocks being distributed on different storage units. Parity updating activity associated with every modification of data in a redundancy group is therefore distributed over the different storage units. No single unit is burdened with all of the parity update activity.
For example, in a RAID 5 system comprising 5 disk drives, the parity information for the first stripe of blocks may be written to the fifth drive; the parity information for the second stripe of blocks may be written to the fourth drive; the parity information for the third stripe of blocks may be written to the third drive; etc. The parity block for succeeding stripes typically "processes" around the disk drives in a helical pattern (although other patterns may be used).
Thus, no single disk drive is used for storing the parity information, and the bottleneck of the RAID 4 architecture is eliminated. An example of a RAID 5 system is described in Clark et al U.S. Pat. No. 4,761,785.
As in a RAID 4 system, a limitation of a RAID 5 system is that a change in a data block requires a Read-Modify-Write sequence comprising two Read and two Write operations: the old parity block and old data block must be read and XOR'd, and the resulting sum must then be XOR'd with the new data. Both the data and the parity blocks then must be rewritten to the disk drives. While the two Read operations may be done in parallel, as can the two Write operations, modification of a block of data in a RAID 4 or a RAID 5 system still takes substantially longer then the same operation on a conventional disk. A conventional disk does not require the preliminary Read operation, and thus does have to wait for the disk drives to rotate back to the previous position in order to perform the Write operation. The rotational latency time alone can amount to about 50% of the time required for a typical data modification operation. Further, two disk storage units are involved for the duration of each data modification operation, limiting the throughput of the system as a whole.
Despite the Write performance penalty, RAID 5 type systems have become increasingly popular, since they provide high data reliability with a low overhead cost for redundancy, good Read performance, and fair Write performance.
A RAID 5 architecture has particular utility in OLTP computer systems. Many OLTP systems must be high-availability systems, meaning that complete failure of the system has a low-probability. High availability can be achieved by using high-reliability components, having a fault-tolerant design with a low mean-time-to-repair (MTTR), and designing for "staged" degradation, where the failure of a component may reduce system capability but without causing total system failure.
Although a principal feature of a RAID system is fault-tolerance, such capability alone does not guarantee a high-availability system. If a storage unit fails, general system operation cannot continue until the failed storage unit is replaced and the information on it is restored. When a storage unit fails in a RAID architecture, the art teaches that a replacement storage unit is substituted for the failed storage unit (either manually or electronically switched in from a set of one or more spares), and the "lost" data is reconstructed on the replacement storage unit by XOR'ing each parity block with all corresponding data blocks from the remaining storage unit drives in the redundancy group. Such reconstruction assumes that the parity information is valid.
However, data can be lost in situations not involving a failure of a storage unit. For example, if a temporary "failure" (such as a power loss or controller failure) occurs to a storage unit during a Write operation, there is no assurance that the data or the corresponding parity information were properly written and valid. Since two I/O operations are required to update the data and its associated parity, it is difficult to determine which I/O operation was completed before the system termination. Thus, the data that was being Written could be corrupted. Further, if a storage unit were to totally fail after corruption of some of the parity information stored on other storage units, the failed storage unit could not be fully reconstructed with good data.
One method taught in the art for resolving this problem is set forth in Clark et al U.S. Pat. No. 4,761,785. This reference teaches using version numbers stored in each data block and corresponding parity block. When a Write operation for a data block is completed, the version numbers in the data block and its corresponding parity block are equal. During recovery of a lost record, the version numbers are checked to ensure synchronization of the data blocks with the parity block. Forcing recovery without valid synchronization would produce unpredictable data. However, updating version numbers requires a processing overhead throughout normal operation, as well as slightly reduced capacity because of the need to store the version numbers with each block.
Therefore, a need exists for a simple method for ensuring that valid parity information is generated in a RAID system even in the event of a temporary "failure". It is also desirable to have a RAID system in which restoration of such parity information can be conducted "on-line", while general system operation continues in a normal fashion. It is also desirable to have a RAID system in which restoration of such parity information can be conducted without requiring added processing overhead during normal operation.
The present invention provides two such methods.
SUMMARY OF THE INVENTION
The present invention provides two methods of restoring valid data to a storage unit after a Write failure caused by a temporary storage unit fault. Either method is done on-line, with insignificant interruption of normal operation of the redundant array system, and without requiring added processing during normal operation.
The first preferred method includes the following steps:
(1) For the stripe that was being Written when the temporary failure occurred, re-computing the associated redundancy block using all data blocks in the stripe (including the potentially corrupted data block that was being Written before the failure).
(2) Storing the re-computed redundancy block.
(3) Resubmitting the interrupted Write operation from the CPU.
(4) Performing the resubmitted Write operation in normal fashion (i.e., writing over the corrupted data block with the new data block, and updating the re-computed redundancy block).
The first step creates a valid redundancy block for the corresponding data blocks on all storage units. Performing the resubmitted Write operation causes the old (and potentially corrupted) data block to be "subtracted" out of the re-computed redundancy block. The uncorrupted new data block is written over the old data block, and is "added" into the re-computed redundancy block to create a new, corrected redundancy block. The new, corrected redundancy block is written to the appropriate storage unit.
The second preferred method includes the following steps:
(1) Resubmitting the interrupted Write operation to the CPU.
(2) For the stripe that was being Written when the temporary failure occurred, computing a new redundancy block using all valid data blocks in the stripe (excluding the potentially corrupted data block that was being Written before the failure).
(3) Writing over the potentially corrupted old redundancy block with the re-computed redundancy block.
(4) Writing over the potentially corrupted data block with the new data block.
The details of the preferred embodiments of the present invention are set forth in the accompanying drawings and the description below. Once the details of the invention are known, numerous additional innovations and changes will become obvious to one skilled in the art.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is block diagram of a generalized RAID system in accordance with the present invention.
FIG. 2A is a diagram of a model RAID 5 system, showing an initial state.
FIG. 2B is a diagram of a model RAID 5 system, showing a failed data block on one storage unit.
FIG. 3 is a flowchart representing the restoration process for the first preferred embodiment of the present invention.
FIG. 4 is a flowchart representing the restoration process for the second preferred embodiment of the present invention.
Like reference numbers and designations in the drawings refer to like elements.
DETAILED DESCRIPTION OF THE INVENTION
Throughout this description, the preferred embodiment and examples shown should be considered as exemplars, rather than limitations on the method of the present invention.
Background Information
FIG. 1 is block diagram of a generalized RAID system in accordance with the present invention. Shown are a CPU 1 coupled by a bus 2 to an array controller 3. The array controller 3 is coupled to each of the plurality of storage units S1-S5 (five being shown by way of example only) by an I/O bus (e.g., a SCSI bus). The array controller 3 preferably includes a separately programmable, multi-tasking processor (for example, the MIPS R3000 RISC processor, made by MIPS Corporation of Sunnyvale, Calif.) which can act independently of the CPU 1 to control the storage units. The present invention is preferably implemented as a multi-tasking computer program executed by the controller 3.
The storage units S1-S5 can be grouped into one or more redundancy groups. In the illustrated examples described below, the redundancy group comprises all of the storage units S1-S5, for simplicity of explanation.
FIG. 2A is a diagram of a model RAID system, showing an initial state. The illustrated array comprises five storage units, S1-S5. Each row A-H is a stripe. Redundancy blocks are indicated by circled numbers, and are spread throughout the array. One bit "blocks" are shown for each storage unit in a stripe for simplicity. Each block could instead be any other unit of size, such as a byte, sector, or group of sectors.
In a modern RAID system, several Write operations can be "stacked", and thus several stripes may be corrupted when such Write operations are interrupted. For simplicity, the following description is directed to restoring a single stripe. However, it should be understood that the invention applies to the more general case of restoring a plurality of stripes after a temporary failure.
FIG. 2B shows the same RAID model as FIG. 2A, but with a temporary failure having occurred while Writing to stripe C (the x's representing corrupted data and/or redundancy blocks). Because of the failure, there is no assurance that the data from the CPU 1 or the corresponding redundancy information were properly written and valid. Such a failure can occur, for example, from a power loss to storage unit S1 or to all of the storage units, or from a failure of the controller 3.
After such a temporary failure has been detected and the cause of the failure rectified, either version of the present invention is used to properly restore the failed stripe.
First Preferred Method
FIG. 3 is a high-level flowchart representing the steps of the restoration process for a first preferred embodiment of the invention. The steps shown in FIG. 3 are referenced below.
For each stripe that was being Written when the temporary failure occurred (stripe C in FIG. 2A), the associated redundancy block (on S3 in FIG. 2B) is re-computed using all data blocks in the stripe (including the potentially corrupted data block that was being Written before the failure).
To re-compute the redundancy block in the preferred embodiment, the data blocks are Read from storage units S1, S2, S4, and S5 for stripe C in the array (Step 30) and XOR'd (Step 31). This first step creates a redundancy block that is valid for the actual values of the corresponding data blocks on all storage units, regardless of whether the data block on S1 is a "0" or a "1". The re-computed redundancy block may be stored in the corresponding location (S3 on stripe C) of the array, or saved in a "scratchpad" memory area for faster processing (Step 32).
Thereafter, the valid data block from the interrupted Write operation that was being executed by the CPU 1 is resubmitted to the array controller 3 for storage on S1 on stripe C (in this example) (Step 33). The Write operation is performed in normal fashion. That is, the re-computed redundancy block (from S3 on stripe C, or in scratchpad memory) and old "data" block (from S1 on stripe C) are Read from the array (Step 34), and the re-computed redundancy block is modified by "subtracting out" (XOR'ing in the preferred embodiment) the old "data" block and "adding in" (XOR'ing) the new data block (Step 35). The new redundancy block and the new data block are then stored on the appropriate storage units of the array (Step 36).
Performing the resubmitted Write operation causes the old (and potentially corrupted) data block to be "subtracted" out of the re-computed redundancy block. The uncorrupted new data block is written over the old data block, and is "added" into the re-computed redundancy block to create a new, corrected redundancy block. The new, corrected redundancy block is written to the appropriate storage unit. After each affected stripe is corrected, the array may then be used in normal fashion.
As is known in the art, the storage units involved in any restoration operation are preferably "locked" so that any concurrently operation I/O tasks cannot affect the restoration process.
Second Preferred Method
FIG. 4 is a flowchart representing the restoration process for a second preferred embodiment of the present invention. The steps shown in FIG. 4 are referenced below.
For each affected stripe, the valid data block from the interrupted Write operation that was being executed by the CPU 1 is resubmitted to the array controller 3 for storage (Step 40). For the stripe that was being Written when the temporary failure occurred (stripe C in FIG. 2A), a new redundancy block is computed using all valid data blocks in the stripe (excluding the potentially corrupted data block that was being Written before the failure, as well as the redundancy block for the stripe).
To compute the new redundancy block, the data blocks are Read from storage units S2, S4, and S5 for stripe C in the array (Step 30) and XOR'd (in the preferred embodiment) with the new data block (Step 41). This first step creates a redundancy block that is valid for the actual values of the corresponding valid data blocks on all storage units and for the new data block.
Thereafter, the new redundancy block is stored in the corresponding redundancy block location (S3 on stripe C) of the array, and the new data block is stored on the appropriate storage unit of the array (S1 on stripe C) (Step 43). After each affected stripe is corrected, the array may then be used in normal fashion.
Again, the storage units involved in any restoration operation are preferably "locked" so that any concurrently operation I/O tasks cannot affect the restoration process.
Additional Embodiments
Under both methods described above, the possibility exists that the CPU 1 cannot resubmit one or more Write requests that were outstanding at the time the array failed (e.g., because of some failure in the CPU 1). It is still necessary to assure that the redundancy data on the storage units is consistent with the valid user data in the data blocks of each stripe that were not being modified during the failure. Otherwise, a subsequent error cannot be corrected. Therefore, the redundancy block of each stripe affected by the failure is restored by reading each data block (including the corrupted data block) in the stripe, generating a new redundancy block from such data blocks, and storing the new redundancy block in its proper place in the stripe (i.e., essentially performing Steps 30, 31, and 32 described above), Preferably, such restoration is done on-line as a separate task while the array continues to function normally at least with respect to stripes that were not affected by the failure.
Although the above-described procedure assures that the redundancy block in each stripe affected by a temporary failure is restored, so that subsequent modifications to data blocks in the stripe are valid, it would be desirable to fully restore the data that was being written during the failure. Therefore, to provide greater reliability, the controller 3 for the RAID system of the present invention preferably includes a non-volatile storage device (e.g., battery powered RAM) as a data buffer for temporarily storing Write requests from the CPU 1 until each Write operation has completed. If a temporary failure occurs as described above, the controller 3 can first attempt to obtain the Write data from the non-volatile storage device. If that action fails for any reason, the controller 3 can attempt to obtain the Write data from the CPU 1.
Summary
The invention thus provides two simple methods for ensuring that valid redundancy information is generated in a RAID system even in the event of a temporary "failure". Because of the locking of each affected storage unit during a restoration operation and implementation as a concurrent task, either method can be used on-line with insignificant interruption of normal operation of the redundant array system, and without requiring added processing during normal operation.
A number of embodiments of the present invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. For example, the present invention can be used with RAID 3, RAID 4, or RAID 5 systems. Furthermore, an error-correction method in addition to or in lieu of the XOR-generated parity may be used for the necessary redundancy information. One such method using Reed-Solomon codes is disclosed in U.S. patent application Ser. No. 270,713, filed Nov. 14, 1988, entitled "Arrayed Disk Drive System and Method" and assigned to the assignee of the present invention. With the structure and method taught by that reference, the present invention can accommodate the loss of two storage units if both XOR and Reed-Solomon (or any other system) redundancy is used. Accordingly, it is to be understood that the invention is not to be limited by the specific illustrated embodiment, but only by the scope of the appended claims.
Claims
We claim:
1. A storage device readable by a programmable control device when coupled to the storage device, the storage device containing a control program tangibly stored thereon, such that the control device is operated by the control program when the storage device is read by the control device, the control device being operated to control a coupled redundant array of data storage units, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, the control program being configured to operate the control device to perform restoration of a valid data block and at least one associated redundancy block to at least each affected data storage unit stripe after a potential corruption in either type of block during a data modification operation, such restoration being performed by the combination of the control program and the control device to perform the function of: (a) accessing all of the data blocks, including the potentially corrupted data block, in each stripe containing the potentially corrupted blocks; (b) computing at least one redundancy block from the accessed blocks; (c) saving the at least one computed redundancy block; (d) resubmitting the valid data block from the data modification operation to the redundant array of storage units for storage; (e) updating the at least one saved computed redundancy block; (f) storing the updated at least one redundancy block and the valid data block in the stripe.
2. A storage device as set forth in claim 1, wherein at least one redundancy block in each stripe contains parity information, the control program being further configured to perform the function of computing the parity redundancy block by exclusively-OR'ing the accessed blocks.
3. A storage device as set forth in claim 1, wherein at least one redundancy block contains parity information, the control program being further configured to perform the step of updating that parity redundancy block by performing the function of: (a) accessing the potentially corrupted data block; (b) generating a new parity redundancy block by exclusively-OR'ing the accessed data block with the saved parity redundancy block and the resubmitted valid data block.
4. A storage device as set forth in claim 1, the control program being further configured to operate the control device to perform restoration as a task concurrently with other input/output tasks.
5. A storage device as set forth in claim 4, the control program being further configured to perform the function of locking each block being read or modified during restoration.
6. A storage device as set forth in claim 1, the control program being further configured to perform the function of storing each data modification operation submitted to the redundant array to a non-volatile storage device coupled to the control device at least until the data modification operation is completed.
7. A storage device as set forth in claim 1, the control program being further configured to operate the control device to perform restoration as a task concurrently with other read operations during which data is read from data storage units by the control device, and write operations during which data is written to the data storage units by the control device, such other read and write operations being essentially unrelated to the restoration operation.
8. A storage device readable by a programmable control device when coupled to the storage device, the storage device containing a control program tangibly stored thereon, such that the control device is operated by the control program when the storage device is read by the control device, the control device being operated to control a coupled redundant array of data storage units, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, the control program being configured to operate the control device to perform restoration of a valid data block and at least one associated redundancy block to at least each affected data storage unit stripe after a potential corruption in either type of block during a data modification operation, such restoration being performed by the combination of the control program and the control device to perform the function of: (a) resubmitting the valid data block from the data modification operation to the redundant array of storage units for storage; (b) accessing all of the uncorrupted data blocks in the stripe containing the potentially corrupted blocks; (c) computing at least one redundancy block from the accessed blocks and the resubmitted valid data block; (d) storing the computed at least one redundancy block and the valid data block in the stripe; (e) performing restoration as a task concurrently with other input/output tasks.
9. A storage device as set forth in claim 8, wherein at least one redundancy block in each stripe contains parity information, the control program being further configured to perform the function of computing the parity redundancy block by exclusively-OR'ing the accessed blocks with the resubmitted valid data block.
10. A storage device as set forth in claim 8, the control program being further configured to perform the function of locking each block being read or modified during restoration.
11. A storage device as set forth in claim 8, the control program being further configured to perform the function of storing each data modification operation submitted to the redundant array in a non-volatile storage device coupled to the control system at least until the data modification operation is completed.
12. A storage device readable by a programmable control device when coupled to the storage device, the storage device containing a control program tangibly stored thereon, such that the control device is operated by the control program when the storage device is read by the control device, the control device being operated to control a coupled redundant array of data storage units, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, the control program being configured to operate the control device to perform restoration of at least one valid redundancy block to at least each affected data storage unit stripe after a potential corruption in a data block and/or in such redundancy blocks in such stripes during a data modification operation, such restoration being performed by the combination of the control program and the control device to perform the function of: (a) accessing all of the data blocks, including the potentially corrupted data block, in each stripe containing the potentially corrupted blocks; (b) computing at least one redundancy block from the accessed blocks; (c) saving the at least one computed redundancy block in the stripe.
13. A storage device as set forth in claim 12, wherein at least one redundancy block in each stripe contains parity information, the control program being further configured to perform the function of computing the parity redundancy block by exclusively OR'ing the accessed blocks.
14. A storage device as set forth in claim 12, the control program being further configured to operate the control device to perform restoration as a task concurrently with other input/output tasks.
15. A storage device as set forth in claim 12, the control program being further configured to perform the function of locking each block being read or modified during restoration.
16. A storage device as set forth in claim 12, the control program being further configured to perform the function of storing each data modification operation submitted to the redundant array in a non-volatile storage device coupled to the control system at least until the data modification operation is completed.
17. A storage device as set forth in claim 12, the control program being further configured to operate the control device to perform restoration as a task concurrently with other read operations during which data is read from data storage units by the control device, and write operations during which data is written to the data storage units by the control device, such other read and write operations being essentially unrelated to the restoration operation.
18. A control program tangibly stored on a storage device readable by a programmable control device, such that the control device is operated by the control program when the storage device is read by the control device, the control device being operated to control a coupled redundant array of data storage units, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, the control program being configured to operate the control device to perform restoration of a valid data block and at least one associated redundancy block to at least each affected data storage unit stripe after a potential corruption in either type of block during a data modification operation, such restoration being performed by the combination of the control program and the control device to perform the function of: (a) accessing all of the data blocks, including the potentially corrupted data block, in each stripe containing the potentially corrupted blocks; (b) computing at least one redundancy block from the accessed blocks; (c) saving the at least one computed redundancy block; (d) resubmitting the valid data block from the data modification operation to the redundant array of storage units for storage; (e) updating the at least one saved computed redundancy block; (f) storing the updated at least one redundancy block and the valid data block in the stripe.
19. A control program as set forth in claim 18, wherein at least one redundancy block in each stripe contains parity information, the control program being further configured to perform the function of computing the parity redundancy block by exclusively-OR'ing the accessed blocks.
20. A control program as set forth in claim 18, wherein at least one redundancy block contains parity information, the control program being further configured to perform the step of updating that parity redundancy block by performing the function of: (a) accessing the potentially corrupted data block; (b) exclusively-OR'ing the accessed data block with the saved parity redundancy block and the resubmitted valid data block to generate a new parity redundancy block.
21. A control program as set forth in claim 18, the control program being further configured to operate the control device to perform restoration as a task concurrently with other input/output tasks.
22. A control program as set forth in claim 21, the control program being further configured to perform the function locking each block being read or modified during restoration.
23. A control program as set forth in claim 18, the data storage system further comprising a non-volatile storage device, the control program being further configured to perform the function of storing each data modification operation submitted to the redundant array in the non-volatile storage device at least until the data modification operation is completed.
24. A storage device as set forth in claim 18, the control program being further configured to operate the control device to perform restoration as a task concurrently with other read operations during which data is read from data storage units by the control device, and write operations during which data is written to the data storage units by the control device, such other read and write operations being essentially unrelated to the restoration operation.
25. A control program tangibly stored on a storage device readable by a programmable control device, such that the control device is operated by the control program when the storage device is read by the control device, the control device being operated to control a coupled redundant array of data storage units, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, the control program being configured to operate the control device to perform restoration of a valid data block and at least one associated redundancy block to at least each affected data storage unit stripe after a potential corruption in either type of block during a data modification operation, such restoration being performed by the combination of the control program and the control device to perform the function of: (a) resubmitting the valid data block from the data modification operation to the redundant array of storage units for storage; (b) accessing all of the uncorrupted data blocks in the stripe containing the potentially corrupted blocks; (c) computing at least one redundancy block from the accessed blocks and the resubmitted valid data block; (d) storing the computed at least one redundancy block and the valid data block in the stripe; (e) performing restoration as a task concurrently with other input/output tasks.
26. A control program as set forth in claim 25, wherein at least one redundancy block in each stripe contains parity information, the control program being further configured to perform the function of computing the parity redundancy block by exclusively-OR'ing the accessed blocks with the resubmitted valid data block.
27. A control program as set forth in claim 25, the control program being further configured to perform the function of locking each block being read or modified during restoration.
28. A control program as set forth in claim 25, the data storage system further comprising a non-volatile storage device, the control program being further configured to perform the function of storing each data modification operation submitted to the redundant array in the non-volatile storage device at least until the data modification operation is completed.
29. A control program tangibly stored on a storage device readable by a programmable control device, such that the control device is operated by the control program when the storage device is read by the control device, the control device being operated to control a coupled redundant array of data storage units, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, the control program being configured to operate the control device to perform restoration of at least one valid redundancy block to at least each affected data storage unit stripe after a potential corruption in a data block and/or in such redundancy blocks in such stripes during a data modification operation, such restoration being performed by the combination of the control program and the control device to perform the function of: (a) accessing all of the data blocks, including the potentially corrupted data block, in each stripe containing the potentially corrupted blocks; (b) computing at least one redundancy block from the accessed blocks; (c) saving the at least one computed redundancy block in the stripe.
30. A control program as set forth in claim 29, wherein at least one redundancy block in each stripe contains parity information, the control program being further configured to perform the function of computing the parity redundancy block by exclusively OR'ing the accessed blocks.
31. A control program as set forth in claim 29, the control program being further configured to operate the control device to perform restoration as a task concurrently with other input/output tasks.
32. A control program as set forth in claim 29, the control program being further configured to perform the function of locking each block being read or modified during restoration.
33. A control program as set forth in claim 29, the data storage system further including a non-volatile storage device, the control program being further configured to perform the function of storing each data modification operation submitted to the redundant array in the non-volatile storage device at least until the data modification operation is completed.
34. A storage device as set forth in claim 29, the control program being further configured to operate the control device to perform restoration as a task concurrently with other read operations during which data is read from data storage units by the control device, and write operations during which data is written to the data storage units by the control device, such other read and write operations being essentially unrelated to the restoration operation.
35. A method for on-line restoration of potentially invalid data stored in one or more physical blocks of storage comprising a portion of a plurality of physical blocks of storage and wherein at least one of said physical blocks of storage in said plurality of physical blocks of storage contains redundancy information associated with data stored in said plurality of physical blocks of storage in a computer system including a computer storage subsystem comprising an array of data storage units and wherein said plurality of physical blocks of storage containing data and redundancy information are arranged at a first set of predetermined positions in at least one first storage stripe across a subset of said data storage units in said array, said method comprising the steps of: accessing data corresponding to data stored in said plurality of physical blocks of storage in said at least one first storage stripe; computing an interim value for said associated redundancy information for said accessed data; resubmitting valid data corresponding to said potentially invalid data; recomputing an updated value for said associated redundancy information from said potentially invalid data, said interim value for said associated redundancy information, and said valid data; and storing data corresponding to said valid data and data corresponding to said updated value for said associated redundancy information to storage locations in said computer system corresponding to a second set of predetermined positions in at least one second storage stripe across a subset of said data storage units in said array.
36. The method of claim 35 wherein said step of accessing is carried out by the step of: reading said data from the plurality of storage blocks in said data storage units in said array.
37. The method of claim 35 wherein said step of accessing comprises the step of: determining at least one alternative non-volatile storage location within said computer system wherein a portion of said data corresponding to data stored in said plurality of physical blocks of storage in said at least one first storage stripe is maintained; and reading said portion of said data from said at least one alternative non-volatile storage location.
38. The method of claim 35 wherein said step of accessing comprises the step of: determining at least one alternative volatile storage location within said computer system wherein a portion of said data corresponding to data stored in said plurality of physical blocks of storage in said at least one first storage stripe is maintained; and reading said portion of said data from said at least one alternative volatile storage location.
39. The method of claim 35 wherein said step of computing is carried out by the step of: XORing blocks of data corresponding to data stored in said first storage stripe to provide said interim value for said associated redundancy information.
40. The method of claim 35 wherein said step of resubmitting is carried out by the step of: reattempting a previous data modification operation which resulted in said potentially invalid data; and completing said previous data modification operation to provide said valid data.
41. The method of claim 40 further comprising the step of: storing data indicative of said previous data modification operation in non-volatile storage.
42. The method of claim 35 wherein said step of recomputing is carried out by the step of: XORing said potentially invalid data, said interim value for said associated redundancy information, and said valid data, to provide said updated value for said associated redundancy information.
43. The method of claim 42 further comprising the step of: storing said updated value for said associated redundancy information in non-volatile storage.
44. The method of claim 35 wherein said step of storing is carried out by the step of: writing said valid data and said updated value for said associated redundancy information to said data storage units at said second set of predetermined positions in said at least one second storage stripe.
45. The method of claim 35 wherein said steps of computing and recomputing are carried out by a computer mass storage device controller operatively coupling said array of data storage units to a central processor unit of said computer system.
46. The method of claim 45 wherein said steps of accessing and storing are further carried out by said computer mass storage device controller and said array of data storage units.
47. The method of claim 35 wherein said steps of accessing, computing, resubmitting, recomputing and storing are carried out substantially concurrently with other input/output tasks of said computer mass storage device subsystem.
48. The method of claim 35 further comprising the step of: preventing access by other input/output processes to each storage block being accessed during said on-line restoration process.
49. The method of claim 35 wherein said first set of predetermined positions in said at least one first storage stripe across a subset of said data storage units is identical to said second set of predetermined positions in said at least one second storage stripe across a subset of said data storage units.
50. A method for on-line restoration of potentially invalid data stored in one or more physical blocks of storage comprising a portion of a plurality of physical blocks of storage and wherein at least one physical block of storage in said plurality of physical blocks of storage contains redundancy information associated with the data stored in said plurality of physical blocks of storage in a computer mass storage subsystem comprising an array of data storage units and wherein said plurality of physical blocks of storage containing data and redundancy information are arranged at a first set of predetermined positions in at least one first storage stripe across a subset of said data storage units in said array, said method comprising the steps of: accessing data corresponding to known valid data stored in said plurality of physical blocks of storage in said at least one first storage stripe; resubmitting valid data corresponding to said potentially invalid data; computing an updated value for said associated redundancy information from said accessed data and said valid data; and storing data corresponding to said valid data and data corresponding to said updated value for said associated redundancy information to storage locations in said computer mass storage subsystem corresponding to a second set of predetermined positions in at least one second storage stripe across a subset of said data storage units in said array.
51. The method of claim 50 wherein said step of accessing is carried out by the step of: reading said data from the plurality of storage blocks in said data storage units in said array.
52. The method of claim 50 wherein said step of accessing includes the step of: determining at least one alternative non-volatile storage location within said computer mass storage subsystem wherein a portion of said data corresponding to said known valid data stored in said plurality of physical storage blocks in said at least one first storage stripe is maintained; and reading said portion of said data from said at least one alternative non-volatile storage location.
53. The method of claim 50 wherein said step of accessing includes the step of: determining at least one alternative volatile storage location within said computer mass storage subsystem wherein a portion of said data corresponding to said known Valid data stored in said plurality of physical storage blocks in said at least one first storage stripe is maintained; and reading said portion of said data from said at least one alternative volatile storage location.
54. The method of claim 50 wherein said step of computing is carried out by the step of: XORing blocks of data corresponding to said accessed data and data corresponding to said resubmitted valid data to provide said updated value for said associated redundancy information.
55. The method of claim 50 wherein said step of resubmitting is carried out by the step of: reattempting a previous data modification operation which resulted in said potentially invalid data; and completing said previous data modification operation to provide said valid data.
56. The method of claim 55 further comprising the step of: storing data indicative of said previous data modification operation in non-volatile storage.
57. The method of claim 50 wherein said step of storing is carried out by the step of: writing said valid resubmitted data and said updated value for said associated redundancy information to said data storage units at said second set of predetermined positions in said at least one second storage stripe.
58. The method of claim 50 wherein said step of computing is carried out by a computer mass storage device controller operatively coupling said array of data storage units to a central processor unit.
59. The method of claim 58 wherein said steps of accessing and storing are further carried out by said computer mass storage device controller and said array of data storage units.
60. The method of claim 50 wherein said steps of accessing, resubmitting, computing and storing are carried out substantially concurrently with other input/output tasks of said computer mass storage device subsystem.
61. The method of claim 50 further comprising the step of: preventing access by other input/output processes to each storage block being accessed during said on-line restoration process.
62. The method of claim 50 wherein said first set of predetermined positions in said at least one first storage stripe across a subset of said data storage units is identical to said second set of predetermined positions in said at least one second storage stripe across a subset of said data storage units.
Patent Citations (23)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3893178 | 1975-07-01 | Sordello | |
| US4092732 | 1978-05-01 | Ouchi | |
| US4467421 | 1984-08-01 | White | |
| US4562576 | 1985-12-01 | Ratcliffe | |
| US4667326 | 1987-05-01 | Young et al. | |
| US4722085 | 1988-01-01 | Flora et al. | |
| US4754397 | 1988-06-01 | Varaiya et al. | |
| US4761785 | 1988-08-01 | Clark et al. | |
| US4768193 | 1988-08-01 | Takemae | |
| US4775978 | 1988-10-01 | Hartness | |
| US4817035 | 1989-03-01 | Timsit | |
| US4849929 | 1989-03-01 | Timsit | |
| US4870643 | 1989-09-01 | Bultman et al. | |
| US4899342 | 1990-02-01 | Potter et al. | |
| US4914656 | 1990-04-01 | Dunphy, Jr. et al. | |
| US4989206 | 1991-01-01 | Dunphy, Jr. et al. | |
| US4993030 | 1991-02-01 | Krakauer et al. | |
| US5088081 | 1992-02-01 | Farr | |
| US5130992 | 1992-07-01 | Frey, Jr. et al. | |
| US5134619 | 1992-07-01 | Hensen et al. | |
| US5148432 | 1992-09-01 | Gordon et al. | |
| EPX297507 | 1988-06-01 | ||
| EPX371243 | 1989-10-01 |
Non-Patent Literature (15)
- Patterson, D.A., et al., "A Case for Redundant Arrays of Inexpensive Disks (RAID)", Jun. 1, 1988.
- Lee, E.K., "Software and Performance Issues in the Implementation of a RAID Prototype", May 1990.
- Chen, P., et al., "Introduction to Redundant Arrays of Inexpensive Disks (RAID)", Dec. 1988.
- Chen, P., et al., "How reliable is RAID?", Feb. 1988.
- Chen, P., et al., "Evolution of the RAID 2 Architecture", Jun. 12, 1990.
- Maximum Strategy, Inc., "Strategy 2 Disk Array Controller Operation Manual", Nov. 2, 1988, San Jose, CA.
- Maximum Strategy, Inc., "Strategy 1 Disk Array Controller Operation Manual", Date Unknown, San Jose, CA.
- Gibson, G.A., "Performance and Reliability in Redundant Arrays of Inexpensive Disks", Date Unknown.
- Chen, P., "An Evaluation of Redundant Arrays of Disks Using an Amdahl 5890", May 1989.
- Katz, R. H., et al., "Disk System Architectures for High Performance Computing", Mar. 1989.
- Gray, J., et al., "Parity Striping of Disc Arrays: Low-Cost Reliable Storage with Acceptable Throughput", Jan. 1990.
- Schulze, M. E., "Considerations in the Design of a Raid Prototype", Aug. 1988.
- Clark, et al., "IBM Systems Journal, vol. 28, No. 3", 1989.
- Dishon, et al., "A Highly Avaliable Storage System Using the Checksum Method", IEEE 1987, pp. 176-181.
- IBM Technical Disclosure Bulletin, "Use of Non-Volatile Semiconductor Storage for Disk Array Parity", vol. 33, No. 6B, Nov. 1990.