US5235601A
Expired / Lapsed
US
⏱️ 0.0 years remaining
On-line restoration of redundancy information in a redundant array system
Assignee: EMC Corp
•
Filing: 1990-12-21
•
Granted: 1993-08-10
•
Expires: 2010-12-21
Abstract
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 recomputed 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.
Inventors
- 👤 David C. Stallmo
- 👤 William A. Brant
- 👤 David Gordon
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 12:32
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F11/14; G06F11/1402; G06F11/1415; G06F11/1435
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
172 words
In a redundant array of data storage units coupled to a controller, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, a method for restoration of a valid data block and at least one associated redundancy block to each data storage unit stripe after a potential corruption in either of such blocks caused by a temporary fault in a data storage unit during a data modification operation, comprising the steps 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.
Claim 2
Dependent Claim
172 words
In a redundant array of data storage units coupled to a controller, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, a method for restoration of a valid data block and at least one associated redundancy block to each data storage unit stripe after a potential corruption in either of such blocks caused by a temporary fault in a data storage unit during a data modification operation, comprising the steps 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.
Claim 3
Dependent Claim
31 words
The method of claim 1, wherein at least one redundancy block in each stripe contains parity information, and the step of computing the parity redundancy block comprises exclusively-OR'ing the accessed blocks.
Claim 4
Dependent Claim
62 words
The method of claim 1, wherein at least one saved computed redundancy block contains parity information, and the step of updating that parity redundancy block comprises the steps of: a. accessing the potentially corrupted data block; and 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.
Claim 5
Dependent Claim
24 words
The method of claim 1, further including the step of performing the steps of claim 1 as a task concurrently with other input/output tasks.
Claim 6
Dependent Claim
19 words
The method of claim 4, further including the step of locking each block being read or modified during restoration.
Claim 7
Dependent Claim
32 words
The method of claim 1, further including the step of storing each data modification operation submitted to the redundant array in a non-volatile storage device until the data modification operation is completed.
Claim 8
Dependent Claim
166 words
In a redundant array of data storage units coupled to a controller, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, a method for on-line restoration of a valid data block and at least one associated redundancy block to each data storage unit stripe after a potential corruption in either of such blocks caused by a temporary fault in a data storage unit during a data modification operation, comprising the steps 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.
Claim 9
Dependent Claim
166 words
In a redundant array of data storage units coupled to a controller, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, a method for on-line restoration of a valid data block and at least one associated redundancy block to each data storage unit stripe after a potential corruption in either of such blocks caused by a temporary fault in a data storage unit during a data modification operation, comprising the steps 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.
Claim 10
Dependent Claim
37 words
The method of claim 7, wherein at least one redundancy block in each stripe contains parity information, and the step of computing the parity redundancy block comprises exclusively-OR'ing the accessed blocks with the resubmitted valid data block.
Claim 11
Dependent Claim
19 words
The method of claim 7, further including the step of locking each block being read or modified during restoration.
Claim 12
Dependent Claim
32 words
The method of claim 7, further including the step of storing each data modification operation submitted to the redundant array in a non-volatile storage device until the data modification operation is completed.
Claim 13
Dependent Claim
130 words
In a redundant array of data storage units coupled to a controller, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, a method for restoration of at least one valid redundancy block to each data storage unit strip after a potential corruption in a data block and/or in such redundancy block in such stripe caused by a temporary fault in a data storage unit during a data modification operation, comprising the steps 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.
Claim 14
Dependent Claim
130 words
In a redundant array of data storage units coupled to a controller, the data storage units having at least one stripe containing a plurality of data blocks and at least one associated redundancy block, a method for restoration of at least one valid redundancy block to each data storage unit strip after a potential corruption in a data block and/or in such redundancy block in such stripe caused by a temporary fault in a data storage unit during a data modification operation, comprising the steps 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.
Claim 15
Dependent Claim
31 words
The method of claim 11, wherein at least one redundancy block in each stripe contains parity information, and the step of computing the parity redundancy block comprises exclusively-OR'ing the accessed blocks.
Claim 16
Dependent Claim
24 words
The method of claim 11, further including the step of performing the steps of claim 12 as a task concurrently with other input/output tasks.
Claim 17
Dependent Claim
19 words
The method of claim 13, further including the step of locking each block being read or modified during restoration.
Claim 18
Dependent Claim
32 words
The method of claim 11, further including the step of storing each data modification operation submitted to the redundant array in a non-volatile storage device until the data modification operation is completed.
Claim 19
Dependent Claim
199 words
A control system for use in conjunction with a 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 system for restoration of a valid data block and at least one associated redundancy block to each data storage unit stripe after a potential corruption in either of such blocks caused by a temporary fault in a data storage unit during a data modification operation, the control system including: a. coupling means for coupling the control system to the array of storage units; b. restoration means, coupled to the coupling means, for: (1) accessing all of the data blocks, including the potentially corrupted data block, in each stripe containing the potentially corrupted blocks; (2) computing at least one redundancy block from the accessed blocks; (3) saving the at least one computed redundancy block; (4) resubmitting the valid data block from the data modification operation to the redundant array of storage units for storage; (5) updating the at least one saved computed redundancy block; (6) storing the updated at least one redundancy block and the valid data block in the stripe.
Claim 20
Dependent Claim
199 words
A control system for use in conjunction with a 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 system for restoration of a valid data block and at least one associated redundancy block to each data storage unit stripe after a potential corruption in either of such blocks caused by a temporary fault in a data storage unit during a data modification operation, the control system including: a. coupling means for coupling the control system to the array of storage units; b. restoration means, coupled to the coupling means, for: (1) accessing all of the data blocks, including the potentially corrupted data block, in each stripe containing the potentially corrupted blocks; (2) computing at least one redundancy block from the accessed blocks; (3) saving the at least one computed redundancy block; (4) resubmitting the valid data block from the data modification operation to the redundant array of storage units for storage; (5) updating the at least one saved computed redundancy block; (6) storing the updated at least one redundancy block and the valid data block in the stripe.
Claim 21
Dependent Claim
30 words
The control system of claim 16, wherein at least one redundancy block in each stripe contains partity information, and the parity redundancy block is computed by exclusively-OR'ing the accessed blocks.
Claim 22
Dependent Claim
64 words
The control system of claim 16, wherein at least one saved computed redundancy block contains parity information, and the control system further includes means for updating that parity redundancy block by: a. accessing the potentially corrupted data block; and 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.
Claim 23
Dependent Claim
23 words
The control system of claim 16, wherein the control system includes means for performing restoration as a task concurrently with other input/output tasks.
Claim 24
Dependent Claim
23 words
The control system of claim 19, wherein the control system further includes means for locking each block being read or modified during restoration.
Claim 25
Dependent Claim
35 words
The control system of claim 16, further including a non-volatile storage device, coupled to the control system, for storing each data modification operation submitted to the redundant array until the data modification operation is completed.
Claim 26
Dependent Claim
193 words
A control system for use in conjunction with a 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 system for on-line restoration of a valid data block and at least one associated redundancy block to each data storage unit stripe after a potential corruption in either of such blocks caused by a temporary fault in a data storage unit during a data modification operation, the control system including: a. coupling means for coupling the control system to the array of storage units; b. restoration means, coupled to the coupling means, for: (1) resubmitting the valid data block from the data modification operation to the redundant array of storage units for storage; (2) accessing all of the uncorrupted data blocks in the stripe containing the potentially corrupted blocks; (3) computing at least one redundancy block from the accessed blocks and the resubmitted valid data block; (4) storing the computed at least one redundancy block and the valid data block in the stripe; (5) performing restoration as a task concurrently with other input/output tasks.
Claim 27
Dependent Claim
193 words
A control system for use in conjunction with a 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 system for on-line restoration of a valid data block and at least one associated redundancy block to each data storage unit stripe after a potential corruption in either of such blocks caused by a temporary fault in a data storage unit during a data modification operation, the control system including: a. coupling means for coupling the control system to the array of storage units; b. restoration means, coupled to the coupling means, for: (1) resubmitting the valid data block from the data modification operation to the redundant array of storage units for storage; (2) accessing all of the uncorrupted data blocks in the stripe containing the potentially corrupted blocks; (3) computing at least one redundancy block from the accessed blocks and the resubmitted valid data block; (4) storing the computed at least one redundancy block and the valid data block in the stripe; (5) performing restoration as a task concurrently with other input/output tasks.
Claim 28
Dependent Claim
36 words
The control means of claim 22, wherein at least one redundancy block in each stripe contains parity information, and the parity redundancy block is computed by exclusively-OR'ing the accessed blocks with the resubmitted valid data block.
Claim 29
Dependent Claim
23 words
The control system of claim 22, wherein the control system further includes means for locking each block being read or modified during restoration.
Claim 30
Dependent Claim
35 words
The control system of claim 22, further including a non-volatile storage device, coupled to the control system, for storing each data modification operation submitted to the redundant array until the data modification operation is completed.
Claim 31
Dependent Claim
157 words
A control system for use in conjunction with a 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 system for restoration of at least one valid redundancy block to each data storage unit stripe after a potential corruption in a data block and/or in such redundancy block in such stripe caused by a temporary fault in a data storage unit during a data modification operation, the control system including: a. coupling means for coupling the control system to the array of storage units; b. restoration means, coupled to the coupling means, for: (1) accessing all of the data blocks, including the potentially corrupted data block, in each stripe containing the potentially corrupted blocks; (2) computing at least one redundancy block from the accessed blocks; (3) saving the at least one computed redundancy block in the stripe.
Claim 32
Dependent Claim
157 words
A control system for use in conjunction with a 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 system for restoration of at least one valid redundancy block to each data storage unit stripe after a potential corruption in a data block and/or in such redundancy block in such stripe caused by a temporary fault in a data storage unit during a data modification operation, the control system including: a. coupling means for coupling the control system to the array of storage units; b. restoration means, coupled to the coupling means, for: (1) accessing all of the data blocks, including the potentially corrupted data block, in each stripe containing the potentially corrupted blocks; (2) computing at least one redundancy block from the accessed blocks; (3) saving the at least one computed redundancy block in the stripe.
Claim 33
Dependent Claim
31 words
The control system of claim 26, wherein at least one redundancy block in each stripe contains parity information, and the parity redundancy block is computed by exclusively OR'ing the accessed blocks.
Claim 34
Dependent Claim
23 words
The control system of claim 26, wherein the control system includes means for performing restoration as a task concurrently with other input/output tasks.
Claim 35
Dependent Claim
23 words
The control system of claim 28, wherein the control system further includes means for locking each block being read or modified during restoration.
Claim 36
Dependent Claim
35 words
The control system of claim 30, further including a non-volatile storage device, coupled to the control system, for storing each data modification operation submitted to the redundant array until the data modification operation is completed.
References Cited (Backward Citations)
US3893178A
Cited
US4092732A
Cited
US4467421A
Cited
US4562576A
Cited
US4849929A
Cited
US4817035A
Cited
US4667326A
Cited
US4754397A
Cited
US4768193A
Cited
US4722085A
Cited
US4761785A
Cited
US4761785B1
Cited
US4775978A
Cited
EP0297507A2
Cited
US4870643A
Cited
US4899342A
Cited
US4993030A
Cited
US4914656A
Cited
US4989206A
Cited
EP0371243A2
Cited
US5088081A
Cited
US5134619A
Cited
US5130992A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-08-09 | 1997-02-08 | 1997-08-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-08-09 | 2001-02-08 | 2001-08-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-08-09 | 2005-02-08 | 2005-08-10 | $7700.00 | Window Closed / Lapsed |