Method and apparatus for recovering parity protected data

Claim 3

The method of operating a computer system of claim 1, wherein said reconstructing data step reconstructs data when attempts are made to access said data.

Claim 4

The method of operating a computer system of claim 1, wherein said storing data step stores the reconstructed data in said at least one error-correction storage block.

Claim 5

The method of operating a computer system of claim 3, wherein said reconstructing data step reconstructs data when attempts are made to access said data.

Claim 6

The method of operating a computer system of claim 1, wherein said data storage units contain a spare storage block, and said storing data step stores the reconstructed data in said spare storage block.

Claim 7

The method of operating a computer system of claim 5, wherein said reconstructing data step reconstructs data when attempts are made to access said data.

Claim 8

A storage apparatus for a computer system, comprising: at least three data storage units; at least one set of storage blocks, each set comprising a plurality of data storage blocks for containing data and at least one error-correction storage block for containing error correction information for the data stored in said data storage blocks, each of said storage blocks being contained on a respective data storage unit; means for reconstructing the data contained in one of said data storage blocks, while the data storage unit containing said data storage block is failing, from the remaining storage blocks in the set; and means for storing said reconstructed data on one of said data storage units other than said data storage unit which is failing, wherein said data storage unit upon which said reconstructed data is stored is a data storage unit containing one of said remaining storage blocks in said set from which said means for reconstructing the data reconstructs the data.

Claim 9

A storage apparatus for a computer system, comprising: at least three data storage units; at least one set of storage blocks, each set comprising a plurality of data storage blocks for containing data and at least one error-correction storage block for containing error correction information for the data stored in said data storage blocks, each of said storage blocks being contained on a respective data storage unit; means for reconstructing the data contained in one of said data storage blocks, while the data storage unit containing said data storage block is failing, from the remaining storage blocks in the set; and means for storing said reconstructed data on one of said data storage units other than said data storage unit which is failing, wherein said data storage unit upon which said reconstructed data is stored is a data storage unit containing one of said remaining storage blocks in said set from which said means for reconstructing the data reconstructs the data.

Claim 10

The storage apparatus for a computer system of claim 7, wherein said means for storing said reconstructed data stores said data in said at least one error-correction storage block.

Claim 11

The storage apparatus for a computer system of claim 8, wherein said means for reconstructing the data comprises a storage controller, said storage controller comprising: a programmable processor executing a storage management program; and a non-volatile random access memory.

Claim 12

The storage apparatus for a computer system of claim 8, wherein said data processing system comprises at least two of said sets of storage blocks; wherein each said at least one error-correction storage block of a set comprises a parity storage block containing parity of the data stored in said data blocks; and wherein said parity storage blocks are distributed among said data storage units in a round robin manner.

Claim 13

The storage apparatus for a computer system of claim 8, wherein each of said data storage units is a rotating magnetic disk drive storage unit.

Claim 14

The storage apparatus for a computer system of claim 7, wherein each of said data storage units contains a spare storage block; and wherein said means for storing said reconstructed data stores said data in one of said spare storage blocks.

Claim 15

The storage apparatus for a computer system of claim 12, wherein each of said data storage units is a rotating magnetic disk drive storage unit.

Claim 16

The storage apparatus for a computer system of claim 12, wherein the total storage capacity of said spare storage blocks contained on said data storage units is sufficient to contain all data reconstructed from said failing storage unit.

Claim 17

A storage controller for a computer system, comprising: a processor; a memory; means for controlling the operation of a plurality of data storage units, said data storage units containing at least one set of storage blocks, each set comprising a plurality of data storage blocks for containing data and at least one error-correction storage block for containing error correction information for the data stored in said data storage blocks, each of said storage blocks being contained on a respective data storage unit; means for maintaining said at least one error-connection storage block; means for reconstructing the data contained in one of said data storage blocks, while the data storage unit containing said data storage block is failing, from the remaining storage blocks in the set; and means for storing said reconstructed data on one of said data storage units other than said data storage unit which is failing, wherein said data storage unit upon which said reconstructed data is stored is a data storage unit containing one of said remaining storage blocks in said set from which said means for reconstructing the data reconstructs the data.

Claim 18

A storage controller for a computer system, comprising: a processor; a memory; means for controlling the operation of a plurality of data storage units, said data storage units containing at least one set of storage blocks, each set comprising a plurality of data storage blocks for containing data and at least one error-correction storage block for containing error correction information for the data stored in said data storage blocks, each of said storage blocks being contained on a respective data storage unit; means for maintaining said at least one error-connection storage block; means for reconstructing the data contained in one of said data storage blocks, while the data storage unit containing said data storage block is failing, from the remaining storage blocks in the set; and means for storing said reconstructed data on one of said data storage units other than said data storage unit which is failing, wherein said data storage unit upon which said reconstructed data is stored is a data storage unit containing one of said remaining storage blocks in said set from which said means for reconstructing the data reconstructs the data.

Claim 19

The storage controller for a computer system of claim 15, wherein said means for storing said reconstructed data stores said data in said at least one error-correction storage block.

Claim 20

The storage controller for a computer system of claim 15, wherein said plurality of data storage units contain at least two of said sets of storage blocks, wherein each said at least one error-correction storage block of a set comprises a parity storage block containing parity of the data stored in said data blocks; and wherein said parity storage blocks are distributed among said data storage units in a round robin manner.

Claim 21

The storage controller for a computer system of claim 15, wherein each of said data storage units contains a spare storage block; and wherein said means for storing said reconstructed data stores said data in one of said spare storage blocks.

Claim 22

The storage controller for a computer system of claim 18, wherein the total storage capacity of said spare storage blocks contained on said data storage units is sufficient to contain all data reconstructed from said failing storage unit.

Claim 23

A storage apparatus for a computer system, comprising: at least three data storage units, each said unit containing at least one storage block for storing data and a spare storage area; means for detecting a failure of one of said data storage units; means for reconstructing data stored in said data storage unit which failed; means for storing said reconstructed data in a plurality of said spare storage areas of said data storage units other than said data storage unit which failed.

Claim 24

A storage apparatus for a computer system, comprising: at least three data storage units, each said unit containing at least one storage block for storing data and a spare storage area; means for detecting a failure of one of said data storage units; means for reconstructing data stored in said data storage unit which failed; means for storing said reconstructed data in a plurality of said spare storage areas of said data storage units other than said data storage unit which failed.

Claim 25

The storage apparatus for a computer system of claim 20, further comprising: means for determining the parity of data stored in a plurality of said data storage units; and means for storing said parity on one of said data storage units, wherein said means for reconstructing data stored in a data storage unit which failed comprises means for exclusive-ORing data and parity stored on said data storage units other than said data storage unit which failed.

Claim 26

The storage apparatus for a computer system of claim 20, wherein the total storage capacity of said plurality of spare storage areas of said data storage units other than said data storage unit which failed is sufficient to contain all data reconstructed from said data storage unit which failed.

Claim 27

A storage apparatus for a computer system, comprising: at least three data storage units; parity generating means for generating parity blocks as a function of sets of data blocks, each parity block being generated as a function of a corresponding set of data blocks; storage management means for managing the storage of said data blocks and parity blocks on said data storage units; data reconstruction means for reconstructing data stored in an inaccessible storage block on one of said data storage units in the event of failure of said one data storage unit, wherein said storage management means manages the storage of said data and parity blocks such that said data reconstruction means is able to reconstruct data contained in said inaccessible storage block from the remaining storage blocks of the set of data storage blocks and corresponding parity storage block to which said inaccessible storage block belongs; and means for storing said reconstructed data on one of said data storage units other than said data storage unit which is failing, wherein said data storage unit upon which said reconstructed data is stored is a data storage unit containing at least one of said remaining storage blocks of the set of data storage blocks and corresponding parity storage block to which said inaccessible storage block belongs.

Claim 28

A storage apparatus for a computer system, comprising: at least three data storage units; parity generating means for generating parity blocks as a function of sets of data blocks, each parity block being generated as a function of a corresponding set of data blocks; storage management means for managing the storage of said data blocks and parity blocks on said data storage units; data reconstruction means for reconstructing data stored in an inaccessible storage block on one of said data storage units in the event of failure of said one data storage unit, wherein said storage management means manages the storage of said data and parity blocks such that said data reconstruction means is able to reconstruct data contained in said inaccessible storage block from the remaining storage blocks of the set of data storage blocks and corresponding parity storage block to which said inaccessible storage block belongs; and means for storing said reconstructed data on one of said data storage units other than said data storage unit which is failing, wherein said data storage unit upon which said reconstructed data is stored is a data storage unit containing at least one of said remaining storage blocks of the set of data storage blocks and corresponding parity storage block to which said inaccessible storage block belongs.

Claim 29

The storage apparatus for a computer system of claim 23, wherein said said storage management means comprises means for distributing each storage block of a set of data storage blocks and corresponding parity storage block on a respective one of said data storage units.

Claim 30

The storage apparatus for a computer system of claim 24, wherein each of said data storage units contains a spare storage area, and wherein said means for storing said reconstructed data stores said data in said spare storage area.

Claim 31

The storage apparatus for a computer system of claim 24, further comprising a storage controller which contains said parity generating means, said storage management means and said data reconstruction means, said storage controller having a programmable processor executing a storage management program and a random access memory.

Claim 34

A method in accordance with claim 27 and further including the steps wherein if data cannot be read from a sector of the inoperative disk, reading the information in the specified identification region of the system to determine whether the entry in the corresponding parity sector of the parity disk is the reconstructed data of the inoperative disk; and reading the data in the corresponding parity sector of the parity disk if the information in said identification region identifies the entry in the corresponding parity sector as the reconstructed data for the corresponding data sector of the inoperative disk.

Claim 35

A data storage apparatus, comprising: a set of at least three data storage units; a data storage controller communicating with said data storage units, said data storage controller managing the storage of data on said set of data storage units as a plurality of sets of blocks, each set of blocks comprising a plurality of data blocks and at least one error-correction block, each block of said set of blocks being stored on a different respective one of said data storage units; wherein said controller, in response to detecting a failure of any one of said data storage units, reconstructs data contained on the failing data storage unit, data contained in an inaccessible block stored on the failing data storage unit being reconstructed from the remaining blocks of the set of blocks to which the inaccessible block belongs; and wherein said controller stores said data reconstructed from the failing data storage unit in a plurality of the remaining data storage units of said set of data storage units.

Claim 36

A data storage apparatus, comprising: a set of at least three data storage units; a data storage controller communicating with said data storage units, said data storage controller managing the storage of data on said set of data storage units as a plurality of sets of blocks, each set of blocks comprising a plurality of data blocks and at least one error-correction block, each block of said set of blocks being stored on a different respective one of said data storage units; wherein said controller, in response to detecting a failure of any one of said data storage units, reconstructs data contained on the failing data storage unit, data contained in an inaccessible block stored on the failing data storage unit being reconstructed from the remaining blocks of the set of blocks to which the inaccessible block belongs; and wherein said controller stores said data reconstructed from the failing data storage unit in a plurality of the remaining data storage units of said set of data storage units.

Claim 37

The data storage apparatus of claim 29, wherein at least one error-correction block contains parity information, and wherein said controller reconstructs data contained in an inaccessible block by exclusively-OR'ing all of the remaining blocks of the set to which the inaccessible block belongs.

Claim 38

The data storage apparatus of claim 29, wherein said controller stores said data reconstructed from the failing data storage unit in said error-correction blocks.

Claim 39

The data storage apparatus of claim 29, wherein said data storage controller comprises: a programmable processor executing a storage management program; and a non-volatile random access memory.

Claim 40

The data storage apparatus of claim 29, wherein said error-correction blocks are distributed among said data storage units in a round robin manner.

Claim 41

The data storage apparatus of claim 29, wherein each of said data storage units contains at least one spare storage block, the total number of spare storage blocks contained in said data storage units being sufficient to store the contents of said failing data storage unit.

Claim 42

The data storage apparatus of claim 29, wherein said data storage controller records status information with respect to data blocks contained on the failing data storage unit, said status information including, for each respective data block, whether said data block has been reconstructed and stored in the remaining data storage units of said set of data storage units; wherein said controller, in response to a request to access an inaccessible data block contained on the failing data storage unit, uses said status information to determine whether the inaccessible data block has already been reconstructed; wherein said controller, in response to determining whether the inaccessible data block has already been reconstructed, reconstructs the inaccessible data block if it has not yet been reconstructed; and wherein said controller, in response to determining whether the inaccessible data block has already been reconstructed, does not reconstruct the inaccessible data block again if it has already been reconstructed.

Claim 45

The method of claim 36, wherein said storage blocks in which said reconstructed data is stored are distributed substantially evenly among all said storage units of said array other than said failing storage unit.

Claim 46

The method of claim 36, wherein said reconstructed data is stored in a plurality of said error-correction blocks.

Claim 47

The method of claim 36, wherein said reconstructed data is stored in a plurality of blocks otherwise used for storage of temporary data.

Claim 48

The method of claim 36, wherein said reconstructed data is stored in a plurality of spare storage blocks.

Claim 51

The method of claim 41, wherein at least one error-correction block contains parity information, and the step of reconstructing the requested data block from the accessed blocks comprises exclusively-OR'ing all of the accessed blocks to generate a new data block.

Claim 52

The method of claim 41, wherein said replacement storage comprises a plurality of blocks distributed among different respective storage units of said redundant array of storage units.

Claim 53

The method of claim 41, further including the steps of: e. receiving a request to write to an updated block of data of said array; f. with respect to said request to write to a data block to be updated; (1) if the data block to be updated is located on the failed storage unit, then: (a) using said status information to determine whether the data block to be updated has been reconstructed and stored in replacement storage; (b) if the data block to be updated has not yet been reconstructed and stored in said replacement storage, then: (i) accessing all of the other data blocks and at least one corresponding error-correction block in the set containing the data block to be updated; (ii) reconstructing the data block to be updated from the accessed blocks; (iii) storing the reconstructed data block to be updated in the replacement storage; (iv) updating said status information to reflect that said data block to be updated has been reconstructed and stored in replacement storage.

Claim 54

The method of claim 44, further including the steps of: f. with respect to said request to write to a data block to be updated; (2) if the data block to be updated is not located on the failed storage unit, then: (a) using said status information to determine whether an inaccessible data block of the failed storage unit belonging to the set of blocks to which the data block to be updated belongs has been reconstructed and stored in replacement storage; (b) if the inaccessible data block of the failed storage unit has not yet been reconstructed and stored in said replacement storage, then: (i) accessing all of the other data blocks and at least one corresponding error-correction block in the set containing the inaccessible data block; (ii) reconstructing the inaccessible data block from the accessed blocks; (iii) storing the reconstructed inaccessible data block in the replacement storage; (iv) updating said status information to reflect that said inaccessible block has been reconstructed and stored in replacement storage.

Claim 55

A storage subsystem for storing data of a computer system, comprising: at least three data storage units, each data storage unit for storing a plurality of blocks, each block being contained in one of a plurality of sets, each said set comprising a plurality of data blocks and at least one associated error-correction block, each block of a set being stored on a different respective one of said plurality of data storage units; a controller coupled to said data storage units, said controller comprising: a programmed processor for executing a storage management program to control the operation of said storage subsystem; a memory, said memory including a status map, said status map having a plurality of status entries recording the status of said blocks of data; an error-correction block generator for generating an error-correction block as a function of other blocks of the corresponding set of blocks; wherein in the event of failure of one of said data storage units, said storage management program causes said controller to: (a) allocate replacement storage for data stored on the failed data storage unit; (b) upon receiving a request to read a block of data stored in said storage subsystem, (1) if the requested data block is located on the failed storage unit, then: (a) access information stored in said status map to determine whether the requested data block has been reconstructed and stored in the replacement storage; (b) if the requested data block has not yet been reconstructed and stored in said replacement storage, then: (i) read all of the other data blocks and at least one corresponding error-correction block in the set containing the requested data block, (ii) reconstruct the requested data block from the read blocks, (iii) store the reconstructed data block in the replacement storage, and (iv) update said status map to reflect that the requested data block has been reconstructed; (c) if the requested data block has already been reconstructed and stored in replacement storage, then: read the requested data block directly from the replacement storage; (2) if the requested data block is not located on the failed storage unit, then: read the requested data block directly.

Claim 56

A storage subsystem for storing data of a computer system, comprising: at least three data storage units, each data storage unit for storing a plurality of blocks, each block being contained in one of a plurality of sets, each said set comprising a plurality of data blocks and at least one associated error-correction block, each block of a set being stored on a different respective one of said plurality of data storage units; a controller coupled to said data storage units, said controller comprising: a programmed processor for executing a storage management program to control the operation of said storage subsystem; a memory, said memory including a status map, said status map having a plurality of status entries recording the status of said blocks of data; an error-correction block generator for generating an error-correction block as a function of other blocks of the corresponding set of blocks; wherein in the event of failure of one of said data storage units, said storage management program causes said controller to: (a) allocate replacement storage for data stored on the failed data storage unit; (b) upon receiving a request to read a block of data stored in said storage subsystem, (1) if the requested data block is located on the failed storage unit, then: (a) access information stored in said status map to determine whether the requested data block has been reconstructed and stored in the replacement storage; (b) if the requested data block has not yet been reconstructed and stored in said replacement storage, then: (i) read all of the other data blocks and at least one corresponding error-correction block in the set containing the requested data block, (ii) reconstruct the requested data block from the read blocks, (iii) store the reconstructed data block in the replacement storage, and (iv) update said status map to reflect that the requested data block has been reconstructed; (c) if the requested data block has already been reconstructed and stored in replacement storage, then: read the requested data block directly from the replacement storage; (2) if the requested data block is not located on the failed storage unit, then: read the requested data block directly.

Claim 57

The storage subsystem of claim 46, wherein said replacement storage comprises a plurality of blocks distributed among different respective data storage units of said subsystem.

Claim 58

The storage subsystem of claim 47, wherein said error correction block generator generates a parity block as an exclusive-OR function of other blocks of the corresponding set of blocks.

Claim 59

A data storage apparatus for storing data on a set of at least three data storage units, said data storage apparatus comprising: error-correction generation means for generating error-correction blocks as a function of sets of data blocks, each error-correction block being generated as a function of a corresponding set of data blocks; storage management means for managing the storage of said data blocks and error-correction blocks on said data storage units; data reconstruction means for reconstructing data stored in inaccessible storage blocks on a failing data storage unit and storing reconstructed data in replacement storage, wherein said storage management means manages the storage of said data and error-correction blocks such that said data reconstruction means is able to reconstruct data contained in an inaccessible storage block from the remaining storage blocks of the set of data storage blocks and corresponding error-correction storage block to which said inaccessible storage block belongs; status mapping means for recording the reconstruction status of inaccessible storage blocks on said failing data storage unit, said status mapping means recording, for each respective inaccessible block, whether said inaccessible block has been reconstructed; failure mode data accessing means for responding to a request to mad data stored on said set of at least three storage units after failure of said failing data storage unit, said failure mode data accessing means cooperating with said status mapping means and said data reconstruction means to (a) access said data directly if said data is not stored on said failing data storage unit, (b) access said data in replacement storage if said data is stored in an inaccessible block on said failing data storage unit and said status mapping means indicates that said data has already been reconstructed, and (c) reconstructing and storing said data in replacement storage with said data reconstruction means, and updating status information with said status mapping means, if said data is stored in an inaccessible block on said failing data storage unit and said status mapping means indicates that said data has not yet been reconstructed.

Claim 60

A data storage apparatus for storing data on a set of at least three data storage units, said data storage apparatus comprising: error-correction generation means for generating error-correction blocks as a function of sets of data blocks, each error-correction block being generated as a function of a corresponding set of data blocks; storage management means for managing the storage of said data blocks and error-correction blocks on said data storage units; data reconstruction means for reconstructing data stored in inaccessible storage blocks on a failing data storage unit and storing reconstructed data in replacement storage, wherein said storage management means manages the storage of said data and error-correction blocks such that said data reconstruction means is able to reconstruct data contained in an inaccessible storage block from the remaining storage blocks of the set of data storage blocks and corresponding error-correction storage block to which said inaccessible storage block belongs; status mapping means for recording the reconstruction status of inaccessible storage blocks on said failing data storage unit, said status mapping means recording, for each respective inaccessible block, whether said inaccessible block has been reconstructed; failure mode data accessing means for responding to a request to mad data stored on said set of at least three storage units after failure of said failing data storage unit, said failure mode data accessing means cooperating with said status mapping means and said data reconstruction means to (a) access said data directly if said data is not stored on said failing data storage unit, (b) access said data in replacement storage if said data is stored in an inaccessible block on said failing data storage unit and said status mapping means indicates that said data has already been reconstructed, and (c) reconstructing and storing said data in replacement storage with said data reconstruction means, and updating status information with said status mapping means, if said data is stored in an inaccessible block on said failing data storage unit and said status mapping means indicates that said data has not yet been reconstructed.

Claim 61

The data storage apparatus of claim 49, wherein said error-correction blocks contains parity information, and the error-correction generation means generates each error-correction block as an exclusive-OR function of said corresponding set of data blocks.

Claim 62

The data storage apparatus of claim 49, wherein said replacement storage comprises a plurality of blocks distributed among different respective storage units of said set of at least three data storage units.