Apparatus, system, and method for reconfiguring an array of storage elements

• US 8,495,460 B2
• Filed: 10/04/2012
• Issued: 07/23/2013
• Est. Priority Date: 05/18/2009
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Thatcher, Jonathan, Fillingim, Jeremy, Inskeep, Bill, Strasser, John, Vigor, Kevin, Aune, Joshua
• Primary Examiner(s): ABRAHAM, ESAW T
• Application Number:
  US13/645,353
• Publication Number:
  US 20130036327A1
• Time in Patent Office: 292 Days
• Field of Search: 714/758, 714/770, 714/799
• 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/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 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit

Abstract

An apparatus, system, and method are disclosed for reconfiguring an array of solid-state storage elements. The method includes determining that one or more storage elements are unavailable to store data. The storage elements are configured in an array of N storage elements that each store a portion of a first ECC chunk and P storage elements that store first parity data corresponding to the first ECC chunk. The method includes generating a second ECC chunk comprising at least a portion of the data of the first ECC chunk. The method includes storing the second ECC chunk and associated second parity data across (N+P)−Z storage elements where 1≦Z≦P.

Claims

1. A method for reconfiguring an array of solid-state storage elements, the method comprising:

determining that one or more storage elements are unavailable to store data, the storage elements configured in an array of N storage elements that each store a portion of a first ECC chunk and P storage elements that store first parity data corresponding to the first ECC chunk;

generating a second ECC chunk comprising at least a portion of the data of the first ECC chunk; and

storing the second ECC chunk and associated second parity data across (N+P)−

Z storage elements where 1≦

z≦

P.

2. The method of claim 1, further comprising regenerating data of the first ECC chunk using (N+P)−

Z storage elements, where Z comprises a number of unavailable storage elements.

3. The method of claim 1, further comprising storing the associated second parity data on one or more storage elements separate from storage elements storing the second ECC chunk.

4. The method of claim 1, wherein the (N+P)−

Z storage elements are configured to store data of the first ECC chunk previously stored on the Z storage elements.

5. The method of claim 1, further comprising tracking one or more regions in the array of storage elements having varying numbers of available storage elements, each region comprising a portion of the array of storage elements.

6. The method of claim 1, further comprising tracking a first storage region storing data on N+P storage elements, a second storage region storing data on (N+P)−

Z storage elements, and a third storage region storing data on ((N+P)−

Z)−

Y storage elements.

7. The method of claim 6, further comprising storing data in the array of storage elements based on performance requirements of the data such that data with a higher performance requirement is stored in storage regions with a greater number of available storage elements.

8. The method of claim 1, wherein determining that a storage element is unavailable further comprises determining that errors in the first ECC chunk are uncorrectable using an Error Correcting Code (“

ECC”

).

9. The method of claim 1, further comprising conducting parity computations on data stored in one or more of the storage elements storing the first ECC chunk and parity data in one or more storage elements storing the associated parity data, the parity computations identifying the unavailable storage element.

10. The method of claim 9, wherein the parity computations comprise a series of iterative substitution of parity data in one or more storage elements storing the associated parity data and data stored in one or more of the storage elements storing the first ECC chunk.

11. The method of claim 1, wherein determining that a storage element is unavailable to store data further comprises determining that a functional storage element satisfies a replacement threshold.

12. An apparatus to reconfigure an array of solid-state storage elements, the apparatus comprising:

a storage element error module configured to determine that one or more storage elements in an array of storage elements are in error, the storage elements configured in an array of N storage elements storing a first ECC chunk and P storage elements that store first parity data generated from the first ECC chunk;

a data reconfiguration module configured to generate a second ECC chunk comprising at least a portion of data of the first ECC chunk; and

a new configuration storage module configured to store the second ECC chunk and associated second parity data on (N+P)−

Z storage elements where 1≦

Z≦

P, wherein the storage element error module, the data reconfiguration module, and the new configuration storage module comprise one or more of logic hardware and executable code, the executable code stored on a computer readable storage medium.

13. The apparatus of claim 12, further comprising a data regeneration module configured to regenerate data of the first ECC chunk with the first parity data and a portion of data of the first ECC chunk.

14. The apparatus of claim 12, wherein the new configuration storage module is configured to store the associated second parity data on one or more storage elements separate from storage elements storing the second ECC chunk.

15. The apparatus of claim 12, wherein the first ECC chunk comprises first data and a first error correcting code (“

ECC”

) generated from the first data, wherein the data reconfiguration module is configured to generate second data comprising at least a portion of the first data and configured to generate second ECC from the second data, the data reconfiguration module configured to generate the second ECC chunk with the second data and the second ECC.

16. The apparatus of claim 12, wherein the (N+P)−

Z storage elements are configured to store data of the first ECC chunk previously stored on the Z storage elements.

17. The apparatus of claim 12, further comprising a reconfiguration log module configured to track one or more regions in the array of storage elements having varying numbers of available storage elements.

18. The apparatus of claim 12, wherein the storage element error module is configured to determine a storage element is in error by determining that bit errors in the first ECC chunk are uncorrectable using the ECC stored with the first ECC chunk.

19. The apparatus of claim 12, wherein the storage element error module further comprises a storage element error location module configured to conduct parity computations on data stored in one or more of the storage elements storing the first ECC chunk and parity data in one or more storage elements storing the associated parity data, the parity computations identifying the one or more storage elements in error.

20. A computer program product comprising a non-transitory computer readable storage medium having computer usable program code executable to perform operations for reconfiguring an array of solid-state storage elements, the operations comprising:

determining that one or more storage elements are retired, the retired storage elements comprising a subset of storage elements configured in an array of N storage elements that each store a portion of a first ECC chunk and P storage elements that store first parity data generated from the first ECC chunk;

reading data from one or more storage elements other than the retired storage elements and generating a second ECC chunk comprising at least a portion of the data of the first ECC chunk; and

storing the second ECC chunk and associated second parity data across (N+P)−

Z storage elements where 1≦

z≦

P and Z comprises a number of retired storage elements.

21. The computer program product of claim 20, the operations further comprising regenerating data of the first ECC chunk using (N+P)−

Z storage elements.

22. A system to reconfigure an array of solid-state storage elements, the system comprising:

a storage controller configured to control an array of N storage elements storing a first ECC chunk and P storage elements that store first parity data associated with the first ECC chunk;

a storage element error module configured to determine that one or more storage elements are unavailable to store data;

a data regeneration module configured to regenerate data of the first ECC chunk with the first parity data and a portion of data of the first ECC chunk;

a data reconfiguration module configured to generate second Error Correcting Code (“

ECC”

) and a second ECC chunk comprising the second ECC and at least a portion of data of the first ECC chunk; and

a new configuration storage module configured to store the second ECC chunk and associated second parity data on (N+P)−

Z storage elements where 1≦

z≦

P and Z comprises a number of unavailable storage elements, wherein the storage controller, the storage element error module, the data reconfiguration module, and the new configuration storage module comprise one or more of logic hardware and executable code, the executable code stored on a computer readable storage medium.

23. The system of claim 22, further comprising a computer device in communication with the storage controller over a system bus.

24. An apparatus for reconfiguring an array of solid-state storage elements, the apparatus comprising:

means for identifying one or more storage elements that are unavailable to store data, the storage elements configured in an array of N data storage elements that each store a portion of a first ECC chunk and P parity storage elements that store first parity data corresponding to the first ECC chunk;

means for regenerating data of the first ECC chunk with the first parity data and a portion of data of the first ECC chunk in response to available data of the first ECC chunk comprising parity data;

means for generating a second ECC chunk comprising at least a portion of the data of the first ECC chunk; and

means for storing the second ECC chunk and associated second parity data on (N+P)−

Z storage elements where 1≦

z≦

P and Z comprises a number of unavailable storage elements, wherein the means for identifying, the means for regenerating, the means for generating, and the means for storing comprise one or more of logic hardware and executable code, the executable code stored on a computer readable storage medium.

25. The apparatus of claim 24, further comprising means for tracking one or more regions in the array of storage elements having varying numbers of available storage elements, each region comprising a portion of the array of storage elements, wherein the means for tracking comprises one or more of logic hardware and executable code, the executable code stored on a computer readable storage medium.