Fault tolerant disk drive matrix

Claim 2

A data storage device for a computer, comprising: (a) a plurality of disk drives arranged in a matrix, wherein each disk drive therein is identified by a row and column intersection of the matrix; (b) mapping means for associating a subset of the plurality of disk drives with a logical array, wherein each of the disk drives belongs to a plurality of different logical arrays, the mapping means further comprising means for mapping a logical unit number received from the computer into a column number and a row number of the matrix identifying a disk drive; and (c) storage means for subdividing a logical unit of data into blocks and storing the blocks in an interleaved manner across the disk drives associated with the logical array.

Claim 3

The data storage device of claim 1, wherein the logical arrays are RAID-5 arrays.

Claim 4

The data storage device of claim 1, further comprising: (d) at least one replacement disk drive; and (e) means for substituting the replacement disk drive for a failed disk drive in the logical array.

Claim 5

The data storage device of claim 3, further comprising: (f) means for reconstructing data blocks stored on the failed disk drive using redundancy blocks and data blocks from surviving disk drives within the logical array.

Claim 6

The data storage device of claim 1, wherein the mapping means comprises: (1) means for mapping a data address received from the computer into a logical data cylinder, according to formulae: HosCyl=HosAdr/CylSize DatCyl=HosCyl+HosCyl/(Width-Redund) * Redund (2) means for mapping the logical unit number received from the computer into the column number and the row number of the matrix identifying the data disk drive, according to the formulae: DatCol=HosLun % Width DatRow=HosLun/Width wherein: HosAdr is the data address received from the computer, CylSize is a logical cylinder size, HosCyl is a cylinder address computed from the data address received from the computer, HosLun is the logical unit number received from the computer, DatCyl is the logical data cylinder, DatCol is the column number identifying the data disk drive, DatRow is the row number identifying the data disk drive, Width is a width of the matrix, Redund is a total number of redundancy disk drives in the logical array, operator "/" indicates integer divide with truncation, operator "*" indicates multiplication, and operator "%" indicates modulo divide.

Claim 7

The data storage device of claim 5, further comprising: (3) means for mapping the logical data cylinder into a logical redundancy cylinder, according to the formula: ParCyl=(DatCyl/Width) * Width+(Width-Redund) (4) means for mapping the logical data cylinder and the column number and the row number of the matrix identifying the data disk drive into a column number and a row number of the matrix identifying a redundancy disk drive, according to the formulae: ParCol=(DatCyl+DatCol+1) % Width NumReg=Depth ** ((Width+Depth-1)/Depth) Region=(ParCyl/Width) % NumReg Angle=Region/Depth Offset=Region % Depth DatSide=DatCol/Depth ParSide=ParCol/Depth ParRow=(DatRow+Angle * (DatCyl+1) +(if DatSide<ParSide then Offset else 0) +(if DatSide>ParSide then Depth-Offset else 0)) % Depth wherein: ParCyl is the logical redundancy cylinder, ParCol is the column number identifying the redundancy disk drive, ParRow is the row number identifying the redundancy disk drive, Depth is a depth of the matrix, NumReg, Region, Angle, Offset, DatSide, and ParSide are computational terms, and operator "**" indicates exponentiation.

Claim 8

The data storage device of claim 5, further comprising: (3) means for mapping the logical data cylinder into a logical redundancy cylinder, according to the formula: ParCyl=(DatCyl/Width) * Width+(Width-Redund) (4) means for mapping the logical data cylinder and the column number of the matrix identifying the data disk drive into a column number of the matrix identifying a redundancy disk drive, according to the formula: ParCol=(DatCyl+DatCol+1) % Width (5) means for mapping the logical data cylinder and the row number of the matrix identifying the data disk drive into a row number of the matrix identifying the redundancy disk drive, according to the formulae: NumReg=Depth ** ((Width+Depth-1)/Depth) Region=(DatCyl/Width) % NumReg ParRow=(DatRow+Region * (DatCyl+1)) % Depth wherein: Redund is equal to 1, Depth is a depth of the matrix and is a prime number, Width is less than or equal to the Depth, but not less than 2, ParCyl is the logical redundancy cylinder, ParCol is the column number identifying the redundancy disk drive, ParRow is the row number identifying the redundancy disk drive, NumReg and Region are computational terms, and operator "**" indicates exponentiation.

Claim 9

The data storage device of claim 5, further comprising: (3) means for mapping the logical data cylinder into a logical redundancy cylinder, according to the formula: ParCyl=(DatCyl/Width) * Width+(Width-Redund) (4) means for mapping the logical data cylinder and the column number of the matrix identifying the data disk drive into a column number of the matrix identifying a redundancy disk drive, according to the formula: ParCol=(DatCyl+DatCol+1) % Width (5) means for mapping the logical data cylinder and the row number of the matrix identifying data disk drive into a row number of the matrix identifying the redundancy disk drive, according to the formulae: NumReg=Depth ** ((Width+Depth-1)/Depth) Region=(DatCyl/Width) % NumReg Angle=Region/Depth Offset=Region % Depth DatSide=DatCol/Depth ParSide=ParCol/Depth ParRow=(DatRow+Angle * (DatCyl+1) +(if DatSide<ParSide then Offset else 0) +(if DatSide>ParSide then Depth-Offset else 0)) % Depth wherein: Redund is equal to 1, Depth is a depth of the matrix and is a prime number, Width is greater than the Depth, but less than or equal to twice the Depth, ParCyl is the logical redundancy cylinder, ParCol is the column number identifying the redundancy disk drive, ParRow is the row number identifying the redundancy disk drive, NumReg, Region, Angle, Offset, DatSide, and ParSide are computational terms, and operator "**" indicates exponentiation.

Claim 10

The data storage device of claim 5, further comprising: (3) means for mapping the logical data cylinder into a logical parity cylinder and a logical quotient cylinder, according to the formulae: ParCyl=(DatCyl/Width) * Width+(Width-1) QuoCyl=(DatCyl/Width) * Width+(Width-2) (4) means for mapping the logical data cylinder and the column number of the matrix identifying the data disk drive into a column number of the matrix identifying a parity disk drive and a column number of the matrix identifying a quotient disk drive, according to the formulae: ParCol=(DatCyl+DatCol+1) % Width QuoCol=(DatCyl+DatCol+2) % Width (5) means for mapping the logical data cylinder and the row number of the matrix identifying the data disk drive into a row number of the matrix identifying the parity disk drive and a row number of the matrix identifying the quotient disk drive, according to the formulae: NumReg=Depth ** ((Width+Depth-1)/Depth) Region=(DatCyl/Width) % NumReg ParRow=(DatRow+Region * (DatCyl+1)) % Depth QuoRow=(DatRow+Region * (DatCyl+2)) % Depth wherein: Redund is equal to 2, Depth is a depth of the matrix and is a prime number, Width is less than or equal to the Depth, but not less than 4, ParCyl is the logical parity cylinder, ParCol is the column number identifying the parity disk drive, ParRow is the row number identifying the parity disk drive, QuoCyl is the logical quotient cylinder, QuoCol is the column number identifying the quotient disk drive, QuoRow is the row number identifying the quotient disk drive, NumReg and Region are computational terms, and operator "**" indicates exponentiation.

Claim 11

The data storage device of claim 5, further comprising: (3) means for mapping the logical data cylinder into a logical parity cylinder and a logical quotient cylinder, according to the formulae: ParCyl=(DatCyl/Width) * Width+(Width-1) QuoCyl=(DatCyl/Width) * Width+(Width-2) (4) means for mapping the logical data cylinder and the column number of the matrix identifying the data disk drive into a column number of the matrix identifying a parity disk drive and a column number of the matrix identifying a quotient disk drive, according to the formulae: ParCol=(DatCyl+DatCol+1) % Width QuoCol=(DatCyl+DatCol+2) % Width (5) means for mapping the logical data cylinder and the row number of the matrix identifying the data disk drive into a row number of the matrix identifying the parity disk drive and a row number of the matrix identifying the quotient disk drive, according to the formulae: NumReg=Depth ** ((Width+Depth-1)/Depth) Region=(DatCyl/Width) % NumReg Angle=Region/Depth Offset=Region % Depth DatSide=DatCol/Depth ParSide=ParCol/Depth QuoSide=QuoCol/Depth ParRow=(DatRow+Angle * (DatCyl+1) +(if DatSide<ParSide then Offset else 0) +(if DatSide>ParSide then Depth-Offset else 0)) % Depth QuoRow=(DatRow+Angle * (DatCyl+2) +(if DatSide<QuoSide then Offset else 0) +(if DatSide>QuoSide then Depth-Offset else 0)) % Depth wherein: Redund is equal to 2, Depth is a depth of the matrix and is a prime number, Width is greater than the Depth but less than or equal to twice the Depth, ParCyl is the logical parity cylinder, ParCol is the column number identifying the parity disk drive, ParRow is the row number identifying the parity disk drive, QuoCyl is the logical quotient cylinder, QuoCol is the column number identifying the quotient disk drive, QuoRow is the row number identifying the quotient disk drive, NumReg, Region, Angle, Offset, DatSide, ParSide, and QuoSide are computational terms, and operator "**" indicates exponentiation.

Claim 14

The method of claim 11, wherein the logical arrays are RAID-5 arrays.

Claim 15

The method of claim 11, further comprising: (d) substituting at least one replacement disk drive for a failed disk drive in the logical array.

Claim 16

The method of claim 13, further comprising: (e) reconstructing data blocks stored on the failed disk drive using redundancy blocks and data blocks from surviving disk drives within the logical array.

Claim 17

The method of claim 11, wherein the associating step comprises: (1) mapping a data address received from the computer into a logical data cylinder, according to formulae: HosCyl=HosAdr/CylSize DatCyl=HosCyl+HosCyl/(Width-Redund) * Redund (2) mapping the logical unit number received from the computer into the column number and the row number of the matrix identifying the data disk drive, according to the formulae: DatCol=HosLun % Width DatRow=HosLun/Width wherein: HosAdr is the data address received from the computer, CylSize is a logical cylinder size, HosCyl is a cylinder address computed from the data address received from the computer, HosLun is the logical unit number received from the computer, DatCyl is the logical data cylinder, DatCol is the column number identifying the data disk drive, DatRow is the row number identifying the data disk drive, Width is a width of the matrix, Redund is a total number of redundancy disk drives in the logical array, operator "/" indicates integer divide with truncation, operator "*" indicates multiplication, and operator "%" indicates modulo divide.

Claim 18

The method of claim 15, further comprising: (3) mapping the logical data cylinder into a logical redundancy cylinder, according to the formula: ParCyl=(DatCyl/Width) * Width+(Width-Redund) (4) mapping the logical data cylinder and the column number and the row number of the matrix identifying the data disk drive into a column number and a row number of the matrix identifying a redundancy disk drive, according to the formulae: ParCol=(DatCyl+DatCol+1) % Width NumReg=Depth ** ((Width+Depth-1)/Depth) Region=(ParCyl/Width) % NumReg Angle=Region/Depth Offset=Region % Depth DatSide=DatCol/Depth ParSide=ParCol/Depth ParRow=(DatRow+Angle * (DatCyl+1) +(if DatSide<ParSide then Offset else 0) +(if DatSide>ParSide then Depth-Offset else 0)) % Depth wherein: ParCyl is the logical redundancy cylinder, ParCol is the column number identifying the redundancy disk drive, ParRow is the row number identifying the redundancy disk drive, Depth is a depth of the matrix, NumReg, Region, Angle, Offset, DatSide, and ParSide are computational terms, and operator "**" indicates exponentiation.

Claim 19

The method of claim 15, further comprising: (3) mapping the logical data cylinder into a logical redundancy cylinder, according to the formula: ParCyl=(DatCyl/Width) * Width+(Width-Redund) (4) mapping the logical data cylinder and the column number of the matrix identifying the data disk drive into a column number of the matrix identifying a redundancy disk drive, according to the formula: ParCol=(DatCyl+DatCol+1) % Width (5) mapping the logical data cylinder and the row number of the matrix identifying the data disk drive into a row number of the matrix identifying the redundancy disk drive, according to the formulae: NumReg=Depth ** ((Width+Depth-1)/Depth) Region=(DatCyl/Width) % NumReg ParRow=(DatRow+Region * (DatCyl+1)) % Depth wherein: Redund is equal to 1, Depth is a depth of the matrix and is a prime number, Width is less than or equal to the Depth, but not less than 2, ParCyl is the logical redundancy cylinder, ParCol is the column number identifying the redundancy disk drive, ParRow is the row number identifying the redundancy disk drive, NumReg and Region are computational terms, and operator "**" indicates exponentiation.

Claim 20

The method of claim 15, further comprising: (3) mapping the logical data cylinder into a logical redundancy cylinder, according to the formula: ParCyl=(DatCyl/Width) * Width+(Width-Redund) (4) mapping the logical data cylinder and the column number of the matrix identifying the data disk drive into a column number of the matrix identifying a redundancy disk drive, according to the formula: ParCol=(DatCyl+DatCol+1) % Width (5) mapping the logical data cylinder and the row number of the matrix identifying the data disk drive into a row number of the matrix identifying the redundancy disk drive, according to the formulae: NumReg=Depth ** ((Width+Depth-1)/Depth) Region=(DatCyl/Width) % NumReg Angle=Region/Depth Offset=Region % Depth DatSide=DatCol/Depth ParSide=ParCol/Depth ParRow=(DatRow+Angle * (DatCyl+1) +(if DatSide<ParSide then Offset else 0)) +(if DatSide>ParSide then Depth-Offset else 0)) % Depth wherein: Redund is equal to 1, Depth is a depth of the matrix and is a prime number, Width is greater than the Depth, but less than or equal to twice the Depth, ParCyl is the logical redundancy cylinder, ParCol is the column number identifying the redundancy disk drive, ParRow is the row number identifying the redundancy disk drive, NumReg, Region, Angle, Offset, DatSide, and ParSide are computational terms, and operator "**" indicates exponentiation.

Claim 21

The method of claim 15, further comprising: (3) mapping the logical data cylinder into a logical parity cylinder and a logical quotient cylinder, according to the formulae: ParCyl=(DatCyl/Width) * Width+(Width-1) QuoCyl=(DatCyl/Width) * Width+(Width-2) (4) mapping the logical data cylinder and the column number of the matrix identifying the data disk drive into a column number of the matrix identifying a parity disk drive and a column number of the matrix identifying a quotient disk drive, according to the formulae: ParCol=(DatCyl+DatCol+1) % Width QuoCol=(DatCyl+DatCol+2) % Width (5) mapping the logical data cylinder and the row number of the matrix identifying the data disk drive into a row number of the matrix identifying the parity disk drive and a row number of the matrix identifying the quotient disk drive, according to the formulae: NumReg=Depth ** ((Width+Depth-1)/Depth) Region=(DatCyl/Width) % NumReg ParRow=(DatRow+Region * (DatCyl+1)) % Depth QuoRow=(DatRow+Region * (DatCyl+2)) % Depth wherein: Redund is equal to 2, Depth is a depth of the matrix and is a prime number, Width is less than or equal to the Depth, but not less than 4, ParCyl is the logical parity cylinder, ParCol is the column number identifying the parity disk drive, ParRow is the row number identifying the parity disk drive, QuoCyl is the logical quotient cylinder, QuoCol is the column number identifying the quotient disk drive, QuoRow is the row number identifying the quotient disk drive, NumReg and Region are computational terms, and operator "**" indicates exponentiation.

Claim 22

The method of claim 15, further comprising: (3) mapping the logical data cylinder into a logical parity cylinder and a logical quotient cylinder, according to the formulae: ParCyl=(DatCyl/Width) * Width+(Width-1) QuoCyl=(DatCyl/Width) * Width+(Width-2) (4) mapping the logical data cylinder and the column number of the matrix identifying the data disk drive into a column number of the matrix identifying a parity disk drive and a column number of the matrix identifying a quotient disk drive, according to the formulae: ParCol=(DatCyl+DatCol+1) % Width QuoCol=(DatCyl+DatCol+2) % Width (5) mapping the logical data cylinder and the row number of the matrix identifying the data disk drive into a row number of the matrix identifying the parity disk drive and a row number of the matrix identifying the quotient disk drive, according to the formulae: NumReg=Depth ** ((Width+Depth-1)/Depth) Region=(DatCyl/Width) % NumReg Angle=Region/Depth Offset=Region % Depth DatSide=DatCol/Depth ParSide=ParCol/Depth QuoSide=QuoCol/Depth ParRow=(DatRow+Angle * (DatCyl+1) +(if DatSide<ParSide then Offset else 0) +(if DatSide>ParSide then Depth-Offset else 0)) % Depth QuoRow=(DatRow+Angle * (DatCyl+2) +(if DatSide<QuoSide then Offset else 0) +(if DatSide>QuoSide then Depth-Offset else 0)) % Depth wherein: Redund is equal to 2, Depth is a depth of the matrix and is a prime number, Width is greater than the Depth but less than or equal to twice the Depth, ParCyl is the logical parity cylinder, ParCol is the column number identifying the parity disk drive, ParRow is the row number identifying the parity disk drive, QuoCyl is the logical quotient cylinder, QuoCol is the column number identifying the quotient disk drive, QuoRow is the row number identifying the quotient disk drive, NumReg, Region, Angle, Offset, DatSide, ParSide, and QuoSide are computational terms, and operator "**" indicates exponentiation.