On-line reconstruction of a failed redundant array system

Claim 3

The method of claim 1, further including the steps of: a. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all other corresponding blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 4

The method of claim 2, wherein receipt of a write request includes the further steps of: a. if the at least one error-correction block associated with the data block to be modified is located on the replacement storage unit, then: (1) accessing all corresponding data blocks in the stripe containing the data block to be modified; (2) computing at least one error-correction block from the accessed blocks and the new data block; (3) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 5

The method of claim 1, further including the steps of: a. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its at least one associated error-correction block are located on the replacement storage unit, then: (a) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (b) computing at least one error-correction block from the accessed blocks and the new data block; (c) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 8

The method of claim 5, wherein receipt of a write request includes the further steps of: a. if the at least one error-correction block associated with the data block to be modified is located on the replacement storage unit, then: (1) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (2) computing at Least one error-correction block from the accessed blocks and the new data block; (3) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 18

A controller for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing each data block of the failed storage unit for each stripe in the array and storing each reconstructed data block on the replacement storage unit in the corresponding stripe; b. reading a requested data block during the reconstruction, by: (1) if the requested data block is located on the replacement storage unit, then: (a) accessing all other corresponding data blocks and the corresponding error-correction block in the stripe containing the requested data block; (b) reconstructing the requested data block from the accessed blocks; (2) if the requested data block is not located on the replacement storage unit, then: (a) accessing the requested data block directly.

Claim 19

A controller for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing each data block of the failed storage unit for each stripe in the array and storing each reconstructed data block on the replacement storage unit in the corresponding stripe; b. reading a requested data block during the reconstruction, by: (1) if the requested data block is located on the replacement storage unit, then: (a) accessing all other corresponding data blocks and the corresponding error-correction block in the stripe containing the requested data block; (b) reconstructing the requested data block from the accessed blocks; (2) if the requested data block is not located on the replacement storage unit, then: (a) accessing the requested data block directly.

Claim 20

The controller of claim 15, wherein the controller further includes means for: a. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all other corresponding blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 21

The controller of claim 16, wherein the controller further includes means, responsive to receipt of a write request, for: a. if the at least one error-correction block associated with the data block to be modified is located on the replacement storage unit, then: (1) accessing all corresponding data blocks in the stripe containing the data block to be modified; (2) computing at least one error-correction block from the accessed blocks and the new data block; (3) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 22

The controller of claim 15, wherein the controller further includes means for: a. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its at least one associated error-correction block are located on the replacement storage unit, then: (a) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (b) computing at least one error-correction block from the accessed blocks and the new data block; (c) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 23

A controller for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing each data block of the failed storage unit for each stripe in the array and storing each reconstructed data block on the replacement storage unit in the corresponding stripe; b. writing a new data block during the reconstruction, by: (1) if the data block to be modified and its associated error-correction block are not located on the replacement storage unit, then: (a) updating the associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all other corresponding blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 24

A controller for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing each data block of the failed storage unit for each stripe in the array and storing each reconstructed data block on the replacement storage unit in the corresponding stripe; b. writing a new data block during the reconstruction, by: (1) if the data block to be modified and its associated error-correction block are not located on the replacement storage unit, then: (a) updating the associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all other corresponding blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 25

The controller of claim 19, wherein the controller further includes means, responsive to receipt of a write request, for: a. if the at least one error-correction block associated with the data block to be modified is located on the replacement storage unit, then: (1) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (2) computing at least one error-correction block from the accessed blocks and the new data block; (3) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 26

A controller for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing each data block of the failed storage unit for each stripe in the array and storing each reconstructed data block on the replacement storage unit in the corresponding stripe; b. writing a new data block during the reconstruction, by: (1) if the data block to be modified and its associated error-correction block are not located on the replacement storage unit, then: (a) updating the associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its associated error-correction block are located on the replacement storage unit, then: (a) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (b) computing a error-correction block from the accessed blocks and the new data block; (c) writing the computed error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 27

A controller for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing each data block of the failed storage unit for each stripe in the array and storing each reconstructed data block on the replacement storage unit in the corresponding stripe; b. writing a new data block during the reconstruction, by: (1) if the data block to be modified and its associated error-correction block are not located on the replacement storage unit, then: (a) updating the associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its associated error-correction block are located on the replacement storage unit, then: (a) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (b) computing a error-correction block from the accessed blocks and the new data block; (c) writing the computed error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 28

The controller of claims 15, 19, or 21, wherein at least one error-correction block contains parity information, and wherein, for reconstructing each data block of the failed storage unit, the controller further includes means for: a. accessing all other corresponding data blocks and the corresponding parity error-correction block in the corresponding stripe; b. exclusively-OR'ing all of the accessed blocks to generate a new data block.

Claim 29

The controller of claims 16, 18, 19, or 21, wherein at least one error-correction block contains parity information, and wherein, for updating the at least one associated error-correction block in response to receipt of a write request, the controller further includes means for: a. reading the data block to be modified and the associated parity error-correction block; b. exclusively-OR'ing the parity error-correction block with the data block to be modified and the new data block to generate an updated parity error-correction block.

Claim 30

The controller of claims 17, 18, 20, or 21, wherein computing at least one error-correction block in response to receipt of a write request comprises exclusively-OR'ing the accessed blocks and the new data block.

Claim 31

The controller of claims 15, 16, or 18, wherein reconstructing the requested data block from the accessed blocks comprises exclusively-OR'ing the accessed blocks.

Claim 32

The controller of claims 16 or 19, wherein reconstructing the data block to be modified from the accessed blocks comprises exclusively-OR'ing the accessed blocks.

Claim 33

The controller of claims 15, 16, or 18, wherein the controller further includes means, when the requested data block is located on the replacement storage unit, for: a. if the block has previously been reconstructed, then: (1) accessing the requested data block directly; b. otherwise; (1) accessing all other corresponding data blocks and at least one corresponding error-correction block in the stripe containing the requested data block; (2) reconstructing the requested data block from the accessed blocks.

Claim 34

The controller of claims 15, 19, or 21, wherein reconstructing each data block of the failed storage unit for each stripe in the array is performed only for stripes that have not previously been reconstructed.

Claim 35

A control program tangibly stored on a storage device readable by a programmable control device when coupled to the storage device, such that the control device is configured and operated by the control program when the storage device is read by the control device, the configured control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a read request for a data block during reconstruction, then: (1) if the requested data block is located on the replacement storage unit, then: (a) accessing all other corresponding data blocks and at least one corresponding error-correction block in the stripe containing the requested data block; (b) reconstructing the requested data block from the accessed blocks; (2) if the requested data block is not located on the replacement storage unit, then: (a) accessing the requested data block directly.

Claim 36

A control program tangibly stored on a storage device readable by a programmable control device when coupled to the storage device, such that the control device is configured and operated by the control program when the storage device is read by the control device, the configured control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a read request for a data block during reconstruction, then: (1) if the requested data block is located on the replacement storage unit, then: (a) accessing all other corresponding data blocks and at least one corresponding error-correction block in the stripe containing the requested data block; (b) reconstructing the requested data block from the accessed blocks; (2) if the requested data block is not located on the replacement storage unit, then: (a) accessing the requested data block directly.

Claim 37

The control program of claim 29, wherein the control program is further configured to operate the control device to perform the function of: a. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all other corresponding blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 38

The control program of claim 30, wherein the control program is further configured to operate the control device to perform the function of: a. if the at least one error-correction block associated with the data block to be modified is located on the replacement storage unit, then: (1) accessing all corresponding data blocks in the stripe containing the data block to be modified; (2) computing at least one error-correction block from the accessed blocks and the new data block; (3) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 39

The control program of claim 29, wherein the control program is further configured to operate the control device to perform the function of: a. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its at least one associated error-correction block are located on the replacement storage unit, then: (a) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (b) computing at least one error-correction block from the accessed blocks and the new data block; (c) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 40

A control program tangibly stored on a storage device readable by a programmable control device when coupled to the storage device, such that the control device is configured and operated by the control program when the storage device is read by the control device, the configured control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all other corresponding blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 41

A control program tangibly stored on a storage device readable by a programmable control device when coupled to the storage device, such that the control device is configured and operated by the control program when the storage device is read by the control device, the configured control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all other corresponding blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 42

The control program of claim 33, wherein the control program is further configured to operate the control device to perform the function of: a. if the at least one error-correction block associated with the data block to be modified is located on the replacement storage unit, then: (1) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (2) computing at least one error-correction block from the accessed blocks and the new data block; (3) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 43

A control program tangibly stored on a storage device readable by a programmable control device when coupled to the storage device, such that the control device is configured and operated by the control program when the storage device is read by the control device, the configured control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its at least one associated error-correction block are located on the replacement storage unit, then: (a) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (b) computing at least one error-correction block from the accessed blocks and the new data block; (c) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 44

A control program tangibly stored on a storage device readable by a programmable control device when coupled to the storage device, such that the control device is configured and operated by the control program when the storage device is read by the control device, the configured control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its at least one associated error-correction block are located on the replacement storage unit, then: (a) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (b) computing at least one error-correction block from the accessed blocks and the new data block; (c) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 45

The control program of claims 29, 33, or 35, wherein at least one error-correction block contains parity information, and wherein the control program is further configured to operate the control device to perform the step of reconstructing each data block of the failed storage unit by the function of: a. accessing all other corresponding data blocks and the corresponding parity error-correction block in the corresponding stripe; b. exclusively-OR'ing all of the accessed blocks to generate a new data block.

Claim 46

The control program of claims 30, 32, 33, or 35, wherein at least one error-correction block contains parity information and wherein the control program is further configured to operate the control device to perform the step of updating the at least one associated error-correction block in response to receipt of a write request by the function of: a. reading the data block to be modified and the associated parity error-correction block; b. exclusively-OR'ing the parity error-correction block with the data block to be modified and the new data block to generate an updated parity error-correction block.

Claim 47

The control program of claims 31, 32, 34, or 35, wherein the control program is further configured to operate the control device to perform the step of computing at least one error-correction block in response to receipt of a write request by the function of exclusively-OR'ing the accessed blocks and the new data block.

Claim 48

The control program of claims 29, 30, or 32, wherein tile control program is further configured to operate the control device to perform the step of reconstructing the requested data block from the accessed blocks by the function of exclusively-OR'ing the accessed blocks.

Claim 49

The control program of claims 30 or 33, wherein the control program is further configured to operate the control device to perform the step of reconstructing the data block to be modified from the accessed blocks by the function of exclusively-OR'ing the accessed blocks.

Claim 50

The control program of claims 29, 30, 32, wherein when the requested data block is located on the replacement storage unit, the control program is further configured to operate the control device to perform the function of: a. if the block has previously been reconstructed then: (1) accessing the requested data block directly; b. otherwise; (1) accessing all other corresponding data blocks and at least one corresponding error-correction block in the stripe containing the requested data block; (2) reconstructing the requested data block from the accessed blocks.

Claim 51

The control program of claims 29, 33, or 35, wherein the control program is further configured to operate the control device to perform the step of reconstructing each data block of the failed storage unit for each stripe in the array only for stripes that have not previously been reconstructed.

Claim 52

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 perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a read request for a data block during reconstruction, then: (1) if the requested data block is located on the replacement storage unit, then: (a) accessing all other corresponding data blocks and at least one corresponding error-correction block in the stripe containing the requested data block; (b) reconstructing the requested data block from the accessed blocks; (2) if the requested data block is not located on the replacement storage unit, then: (a) accessing the requested data block directly.

Claim 53

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 perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a read request for a data block during reconstruction, then: (1) if the requested data block is located on the replacement storage unit, then: (a) accessing all other corresponding data blocks and at least one corresponding error-correction block in the stripe containing the requested data block; (b) reconstructing the requested data block from the accessed blocks; (2) if the requested data block is not located on the replacement storage unit, then: (a) accessing the requested data block directly.

Claim 54

The storage device of claim 43, wherein the control program is further configured to operate the control device to perform the function of: a. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all other corresponding blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated at least one error-correction block and the new data block in the stripe containing tile data block to be modified.

Claim 55

The storage device of claim 44, wherein the control program is further configured to operate the control device to perform the function of: a. if the at least one error-correction block associated with tile data block to be modified is located on the replacement storage unit, then: (1) accessing all corresponding data blocks in the stripe containing the data block to be modified; (2) computing at least one error-correction block from the accessed blocks and the new data block; (3) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 56

The storage device of claim 43, wherein the control program is further configured to operate the control device to perform the function of: a. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its at least one associated error-correction block are located on the replacement storage unit then: (a) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (b) computing at least one error-correction block from the accessed blocks and the new data block; (c) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 57

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 perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all other corresponding blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 58

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 perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all other corresponding blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 59

The storage device of claim 47, wherein the control program is further configured to operate the control device to perform the function of: a. if the at least one error-correction block associated with the data block to be modified is located on the replacement storage unit, then: (1) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (2) computing at least one error-correction block from the accessed blocks and the new data block; (3) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 60

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 perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its at least one associated error-correction block are located on the replacement storage unit, then: (a) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (b) computing at least one error-correction block from the accessed blocks and the new data block; (c) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 61

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 perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, the control program being configured to operate the control device to perform the function of: a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its at least one associated error-correction block are located on the replacement storage unit, then: (a) accessing all other corresponding data blocks in the stripe containing the data block to be modified; (b) computing at least one error-correction block from the accessed blocks and the new data block; (c) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.

Claim 62

The storage device of claims 43, 47, or 49, wherein at least one error-correction block contains parity information, and wherein the control program is further configured to operate the control device to perform the step of reconstructing each data block of the failed storage unit by the function of: a. accessing all other corresponding data blocks and the corresponding parity error-correction block in the corresponding stripe; b. exclusively-OR'ing all of the accessed blocks to generate a new data block.

Claim 63

The storage device of claims 44, 46, 47, or 49, wherein at least one error-correction block contains parity information, and wherein the control program is further configured to operate the control device to perform the step of updating the at least one associated error-correction block in response to receipt of a write request by the function of: a. reading the data block to be modified and the associated parity error-correction block; b. exclusively-OR'ing the parity error-correction block with the data block to be modified and the new data block to generate an updated parity error-correction block.

Claim 64

The storage device of claims 45, 46, 48, or 49, wherein the control program is further configured to operate the control device to perform the step of computing at least one error-correction block in response to receipt of a write request by the function of exclusively-OR'ing the accessed blocks and the new data block.

Claim 65

The storage device of claims 43, 44, or 46, wherein the control program is further configured to operate the control device to perform the step of reconstructing the requested data block from the accessed blocks by the function of exclusively-OR'ing the accessed blocks.

Claim 66

The storage device of claims 44 or 47, wherein the control program is further configured to operate the control device to perform the step of reconstructing the data block to be modified from the accessed blocks by the function of exclusively-OR'ing the accessed blocks.

Claim 67

The storage device of claims 43, 44, 46, wherein when the requested data block is located on the replacement storage unit, the control program is further configured to operate the control device to perform the function of: a. if the block has previously been reconstructed then: (1) accessing the requested data block directly; b. otherwise; (1) accessing all other corresponding data blocks and at least one corresponding error-correction block in the stripe containing the requested data block; (2) reconstructing the requested data block from the accessed blocks.

Claim 68

The storage device of claims 43, 47, or 49, wherein the control program is further configured to operate the control device to perform the step of reconstructing each data block of the failed storage unit for each stripe in the array only for stripes that have not previously been reconstructed.