Apparatus, system, and method for reconfiguring an array to operate with less storage elements

• US 8,307,258 B2
• Filed: 05/18/2009
• Issued: 11/06/2012
• 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, Aune, Joshua, Fillingim, Jeremy, Inskeep, Bill, Strasser, John, Vigor, Kevin
• Primary Examiner(s): ABRAHAM, ESAW T
• Application Number:
  US12/468,040
• Publication Number:
  US 20100293439A1
• Time in Patent Office: 1,268 Days
• Field of Search: 714/6, 714/763, 365/185.09, 365/201
• US Class Current: 714/763
• 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 protected using parity data. The storage element error module determines that one or more storage elements are unavailable to store data (“unavailable storage elements”). The storage element resides in an array with N number of storage elements storing a first ECC chunk and P number of storage elements storing first parity data. The reconfigure data read module reads data from storage elements other than the unavailable storage elements. The data regeneration module uses the first parity data to regenerate missing data from the first ECC chunk. The data reconfiguration module creates a second ECC chunk. The new configuration storage module stores a portion of the second ECC chunk and associated second parity data on (N+P)−Z number of storage elements, wherein 1≦Z≦P.

Claims

1. An apparatus to reconfigure an array of solid-state storage elements protected using parity data, the apparatus comprising:

a storage element error module that determines that one or more storage elements are unavailable to store data, the storage element in an array of three or more storage elements, each storage element in the array comprising non-volatile solid-state storage, wherein data is written to a logical page of the array, a logical page of the array comprising a page on each of the storage elements in the array and wherein the array comprises N number of storage elements storing a first ECC chunk and P number of storage elements storing first parity data generated from the first ECC chunk, the ECC chunk comprising data and a first error correcting code (“

ECC”

) generated from the stored data, a portion of the first ECC chunk is stored on each of N number of storage elements;

a reconfigure data read module that reads data from storage elements other than the unavailable storage elements, the available data comprising data from a logical page;

a data regeneration module that, in response to the available data comprising first parity data, uses the first parity data to regenerate missing data from the first ECC chunk;

a data reconfiguration module that generates second ECC from one or more of the available data, the missing data, and data received by a storage controller, the second ECC together with data used to create the second ECC comprise a second ECC chunk, and that generates second parity data from the second ECC chunk, the storage controller controlling data storage on the array of storage elements; and

a new configuration storage module that stores a portion of the second ECC chunk and associated second parity data on (N+P)−

Z number of storage elements, wherein 1≦

Z≦

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

2. The apparatus of claim 1, wherein each of the storage elements of the array comprises one or more append points and data is stored on the array of storage elements sequentially and wherein the new configuration storage module stores the second ECC chunk and associated parity data at an append point on each of the (N+P)−

Z storage elements, each append point moved to the end of data stored just prior to movement of the append point.

3. The apparatus of claim 1, further comprising a reconfiguration log module that identifies one or more regions in the array of storage elements where data is stored in (N+P)−

Z storage elements, a region comprising a portion of each of the N+P storage elements.

4. The apparatus of claim 3, wherein a region comprises one or more of a portion of a logical page, a logical page, a group of logical pages, a portion of an erase block, an erase block, a group of erase blocks, one or more dies, and one or more chips.

5. The apparatus of claim 3, wherein the reconfiguration log module tracks a storage region that is unavailable for data storage such that data is stored on (N+P)−

Z storage elements for the unavailable region and on N+P storage elements for locations outside the unavailable storage region, a storage region comprising a portion of each of the N+P storage elements.

6. The apparatus of claim 3, wherein the reconfiguration log module further tracks one or more unavailable storage regions where data is stored in (N+P)−

Z storage elements and one or more additional unavailable storage regions where data is stored in ((N+P)−

Z)−

Y storage elements, wherein in storage regions other than the unavailable storage regions data is stored in N+P storage elements.

7. The apparatus of claim 3, wherein a storage region comprises one or more of a portion of a logical page, a logical page, a plurality of logical pages, a portion of a logical erase block, a logical erase block, a plurality of logical erase blocks, a die, a plurality of dies, a chip, and a plurality of chips.

8. The apparatus of claim 3, wherein storage regions with more available storage elements have a higher performance than storage regions with less available storage elements and wherein data is stored and segregated in the array of storage elements by performance requirements of the data such that data with a higher performance requirement is given a higher priority to be stored in storage regions with a higher performance.

9. The apparatus of claim 1, wherein at least the reconfigure data read module, the data regeneration module, and the data reconfiguration module operate in a background process.

10. The apparatus of claim 9, wherein the background process comprises a storage space recovery operation.

11. The apparatus of claim 1, wherein the storage element error module determines that a storage element is in error by determining that errors in the first ECC chunk are uncorrectable using the ECC stored with the first ECC chunk.

12. The apparatus of claim 11, wherein the storage element error module further comprises a storage element error location module that uses data stored in one or more of the storage elements storing one or more ECC chunks and the storage elements storing associated parity data to identify the one or more storage elements that are unavailable to store data.

13. The apparatus of claim 12, wherein the storage element error location module uses hardware gates and logic to substitute the data stored in one or more of the storage elements storing one or more ECC chunks.

14. The apparatus of claim 1, wherein the storage element error module determines that a failing storage element is in error by determining that the failing storage element that is functioning has reached a replacement threshold.

15. The apparatus of claim 14, wherein the replacement threshold comprises one or more of a rate of errors in data stored on the failing storage element, a number of errors in data stored on the failing storage element, a number of read and/or write operations on the failing storage element, and an environmental condition in the failing storage element.

16. The apparatus of claim 1, wherein the new configuration storage module stores the second ECC chunk on (N−

Z) storage elements and the associated second parity data on P storage elements.

17. The apparatus of claim 1, wherein the new configuration storage module stores the second ECC chunk on N storage elements and the associated second parity data on P−

Z storage elements where P>

1.

18. The apparatus of claim 1, wherein in response to the storage element error module determining that one or more storage elements are unavailable and the reconfigure data read module, the data regeneration module, the data reconfiguration module, and the new configuration storage module acting to store one or more ECC chunks on (N+P)−

Z storage elements, the storage element error module determines that one or more additional storage elements are unavailable and the reconfigure data read module, the data regeneration module, the data reconfiguration module, and the new configuration storage module act to store one or more additional ECC chunks on ((N+P)−

Z)−

Y storage elements.

19. A system to reconfigure an array of solid-state storage elements protected using parity data, the system comprising:

a storage device comprising a storage controller and an array of storage elements controlled by the storage controller, the storage element in an array of three or more storage elements, each storage element in the array comprising non-volatile solid-state storage, wherein data is written to a logical page of the array, a logical page of the array comprising a page on each of the storage elements in the array and wherein the array comprises N number of storage elements storing a first ECC chunk and P number of storage elements storing first parity data generated from the first ECC chunk, the ECC chunk comprising data and a first error correcting code (“

ECC”

) generated from the stored data, a portion of the first ECC chunk is stored on each of N number of storage elements;

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

a reconfigure data read module that reads data from storage elements other than the unavailable storage elements, the available data comprising data from a logical page;

a data regeneration module that, in response to the available data comprising first parity data, uses the first parity data to regenerate missing data from the first ECC chunk;

a data reconfiguration module that generates second ECC from one or more of the available data, the missing data, and data received by a storage controller, the second ECC together with data used to create the second ECC comprise a second ECC chunk, and that generates second parity data from the second ECC chunk, the storage controller controlling data storage on the array storage elements; and

a new configuration storage module that stores a portion of the second ECC chunk and associated second parity data on (N+P)−

Z number of storage elements, wherein 1≦

Z≦

P and Z comprises a number of unavailable storage elements.

20. The system of claim 19, further comprising a driver on a server, the server in communication with the storage device over a computer network, the driver interacting with the storage controller to store data on the array of storage elements.

21. A computer readable storage medium storing computer usable program code executable to perform operations for reconfiguring an array of solid-state storage elements protected using parity data, the operations comprising:

determining that one or more storage elements are unavailable to store data, the storage element in an array of three or more storage elements, each storage element in the array comprising non-volatile solid-state storage, wherein data is written to a logical page of the array, a logical page of the array comprising a page on each of the storage elements in the array and wherein the array comprises N number of storage elements storing a first ECC chunk and P number of storage elements storing first parity data generated from the first ECC chunk, the ECC chunk comprising data and a first error correcting code (“

ECC”

) generated from the stored data, a portion of the first ECC chunk is stored on each of N number of storage elements;

reading data from storage elements other than the unavailable storage elements, the available data comprising data from a logical page;

in response to the available data comprising first parity data, using the first parity data to regenerate missing data from the first ECC chunk;

generating second ECC from one or more of the available data, the missing data, and data received by a storage controller, the second ECC together with data used to create the second ECC comprise a second ECC chunk, and that generates second parity data from the second ECC chunk, the storage controller controlling data storage on the array storage elements; and

storing a portion of the second ECC chunk and associated second parity data on (N+P)−

Z number of storage elements, wherein 1≦

Z≦

P and Z comprises a number of unavailable storage elements.