APPARATUS, SYSTEM, AND METHOD TO INCREASE DATA INTEGRITY IN A REDUNDANT STORAGE SYSTEM

• US 20120131413A1
• Filed: 05/18/2010
• Published: 05/24/2012
• Est. Priority Date: 05/18/2009
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Thatcher, Jonathan, Flynn, David, Aune, Joshua, Fillingim, Jeremy, Inskeep, Bill, Strasser, John, Vigor, Kevin
• Granted Patent: US 8,832,528 B2
• Time in Patent Office: Days
• US Class Current: 714/758
• CPC Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 11/0766 Error or fault reporting or storing
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing

Abstract

An apparatus, system, and method are disclosed to increase data integrity in a redundant storage system. The receive module receives a read request to read data from an ECC chunk spanning N storage elements of an array of N+P storage elements. The N storage elements each store a portion of the ECC chunk and the P storage elements store parity data. The data read module reads data from each of X number of storage elements of the N+P storage elements where (N+P)>X≧N. The ECC correction module corrects the read data of the ECC chunk using Error Correcting Code (“ECC”) in response to the ECC chunk comprising a number of bit errors below a correctable bit error threshold. The substitution module may correct the read data with substitute data from a substitute storage element.

Claims

1. An apparatus to increase data read performance in a redundant storage system, the apparatus comprising:

a receive module that receives a read request to read data from an ECC chunk spanning N storage elements of an array of N+P storage elements, the N storage elements each storing a portion of the ECC chunk and P storage elements storing parity data for the N storage elements;

a data read module that reads data from each of X number of storage elements of the N+P storage elements where (N+P)>

X≧

N;

an ECC correction module that corrects the read data of the ECC chunk using Error Correcting Code (“

ECC”

) in response to the ECC chunk comprising a number of bit errors below a correctable bit error threshold; and

a substitution module that corrects the read data with substitute data from a substitute storage element in response to the ECC chunk comprising a number of bit errors above a correctable bit error threshold.

2. The apparatus of claim 1, further comprising a regeneration module that, in response to a portion of the read data comprising parity data, regenerates a missing portion of the ECC chunk using the parity data.

3. The apparatus of claim 2, wherein the substitution module replaces the regenerated portion of the ECC chunk with the substitute data in response to the read data and the regenerated portion of the ECC chunk comprising a number of bit errors above the correctable bit threshold, the substitute data and read data together comprising a substitute ECC chunk having a number of bit errors below the correctable bit error threshold.

4. The apparatus of claim 2, wherein the substitution module combines the parity data with the substitute data to produce generated substitute data, the generated substitute data and read data together comprising a substitute ECC chunk having a number of bit errors below the correctable bit error threshold.

5. The apparatus of claim 1, wherein the substitution module generates a missing portion of the ECC chunk by way of a parity computation comprising the read data and parity data from the substitute storage element, the generated missing portion and read data together comprising a substitute ECC chunk having a number of bit errors below the correctable bit error threshold.

6. The apparatus of claim 1, further comprising an ECC check module that determines if the number of bit errors are below a correctable bit error threshold

7. The apparatus of claim 1, wherein the substitution module generates a substitute ECC chunk from the read data and the substitute data.

8. The apparatus of claim 7, wherein the substitute ECC chunk comprises one of no errors and a number of errors that are correctable.

9. The apparatus of claim 1, further comprising a device error determination module that determines which storage element comprises data with the errors.

10. The apparatus of claim 1, further comprising a periodic read module that periodically reads data from the one or more storage elements not read by the data read module.

11. The apparatus of claim 1, further comprising a parity rotation module that alternates which storage elements store parity data.

12. The apparatus of claim 11, wherein the rotation module alternates which storage element stores parity data after a storage space recovery operation.

13. The apparatus of claim 1, wherein the data read module further comprises a read rotation module that rotates which storage elements the data read module reads.

14. The apparatus of claim 1, wherein the storage elements of the X storage elements do not store parity data for the ECC chunk.

15. The apparatus of claim 1, wherein the P number of storage elements that store parity data comprise a data minor.

16. A system to increase data integrity in a redundant storage system, the system comprising:

a storage controller controlling an array of N storage elements that each store a portion of an ECC chunk and P storage elements storing parity data for the N storage elements;

a receive module that receives a read request to read data from the ECC chunk spanning the array of N+P storage elements;

a data read module that reads data from each of X number of storage elements of the N+P storage elements where X equals N; and

an ECC correction module that corrects the read data of the ECC chunk using Error Correcting Code (“

ECC”

) in response to the ECC chunk comprising a number of bit errors below a correctable bit error threshold; and

a substitution module that corrects the read data with substitute data generated from a substitute storage element in response to the ECC chunk comprising a number of bit errors above a correctable bit error threshold.

17. The system of claim 16, further comprising a computer in communication with the storage controller, wherein the computer comprises one of

a computer with an enclosure housing the storage controller and an array of storage elements;

a server sending storage requests to the storage controller; and

a client in communication with and sending storage requests to the storage controller.

18. A method for increasing data integrity in a redundant storage system, the method comprising:

receiving a read request to read data from an ECC chunk spanning N storage elements of an array of N+P storage elements, the N storage elements each storing a portion of the ECC chunk and P storage elements storing parity data for the N storage elements;

reading data from each of X number of storage elements of the N+P storage elements where X equals N;

regenerating a missing portion of the ECC chunk using parity data in response to a portion of the read data comprising the parity data; and

correcting the read data with substitute data from a substitute storage element in response to the ECC chunk comprising a number of bit errors above a correctable bit error threshold.

19. The method of claim 18, wherein the substitution module generates a substitute ECC chunk from the read data and the substitute data and wherein the substitute ECC chunk comprises one of no errors and a number of errors that are correctable.

20. The method of claim 18, further comprising alternating which storage elements store parity data.

21. The method of claim 18, further comprising rotating which storage elements in a set of N+P storage elements comprise the X storage elements.