Systems and methods for adaptive data storage

• US 9,495,241 B2
• Filed: 03/04/2013
• Issued: 11/15/2016
• Est. Priority Date: 12/06/2006
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Longitude Enterprise Flash S.à r.l. (Vector Capital Corporation)
• Inventors: Flynn, David, Strasser, John, Inskeep, Bill
• Primary Examiner(s): Lamarre, Guy
• Application Number:
  US13/784,705
• Publication Number:
  US 20130179753A1
• Time in Patent Office: 1,352 Days
• Field of Search: 714/769, 714/770, 714/773, 711/217
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1044 with specific ECC/EDC distribution
• 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 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H05K 7/1444 Complex or three-dimensional-arrangements; Stepped or dual mother boards

Abstract

A storage module is configured to store data segments, such as error-correcting code (ECC) codewords, within an array comprising two or more solid-state storage elements. The data segments may be arranged in a horizontal arrangement, a vertical arrangement, a hybrid channel arrangement, and/or vertical stripe arrangement within the array. The data arrangement may determine input/output performance characteristics. An optimal adaptive data storage configuration may be based on read and/or write patterns of storage clients, read time, stream time, and so on. Data of failed storage elements may be reconstructed by use of parity data and/or other ECC codewords stored within the array.

Claims

1. A method, comprising:

managing storage operations on a plurality of solid-state storage elements, wherein each solid-state storage element of the plurality of solid-state storage elements is selected from the group including a package, a die, a plane, and a printed circuit board;

generating an ECC codeword comprising data for storage on the solid-state storage elements; and

storing portions of the ECC codeword on two or more solid-state storage elements of the plurality of solid-state storage elements.

2. The method of claim 1, further comprising:

generating a first set of ECC codewords comprising data of a first storage request;

generating a second set of ECC codewords comprising data of a second storage request;

storing the first set of ECC codewords in a first set of one or more solid-state storage elements of the plurality of solid-state storage elements; and

storing the second set of ECC codewords in a second, different set of one or more solid-state storage elements of the plurality of solid-state storage elements.

3. The method of claim 2, further comprising reading ECC codewords comprising the data of the first storage request from the first set of solid-state storage elements and ECC codewords comprising the data of the second storage request from the second set of solid-state storage elements in a single read operation.

4. The method of claim 1, further comprising:

dividing the plurality of solid-state storage elements into a plurality of independent channels, each independent channel comprising a respective subset of solid-state storage elements; and

storing ECC codewords corresponding to respective storage requests within respective independent channels.

5. The method of claim 4, further comprising determining an independent channel configuration based on one or more of a read time of the solid-state storage elements, a stream time of ECC codewords, and profiling data pertaining to storage operations.

6. The method of claim 1, further comprising:

marking the ECC codeword with relational information derived from a logical identifier corresponding to the data of the ECC codeword; and

validating the mark.

7. An apparatus, comprising:

a storage module configured to manage storage operations on a solid-state storage array comprising a plurality of columns, each column comprising a respective solid-state storage element, wherein each solid-state storage element is selected from the group including a package, a die, a plane, and a printed circuit board;

an error-correcting code (ECC) write module configured to generate ECC codewords comprising data segments for storage on the solid-state storage array; and

an adaptive write module configured to format the ECC codewords into vertical stripes, wherein the vertical stripes are configured to arrange data of the ECC codewords within respective columns of the solid-state storage array, and wherein two or more ECC codewords comprising one of the data segments are stored within two or more different columns of the solid-state storage array.

8. The apparatus of claim 7, further comprising an adaptive read module configured to identify two or more columns comprising ECC codewords comprising a requested data segment, and to read the ECC codewords comprising the requested data segment from the two or more columns in parallel.

9. The apparatus of claim 8, further comprising a read sequence module configured to reorder the ECC codewords in accordance with an order of the requested data segment and a vertical stripe arrangement of the ECC codewords within the solid-state storage array.

10. The apparatus of claim 7, further comprising an adaptive schedule module configured to combine two or more read operations into a combined read operation, the two or more read operations corresponding to ECC codewords stored within different sets of columns of the solid-state storage array.

11. The apparatus of claim 10, further comprising an ordered queue of storage requests, wherein the adaptive schedule module is configured to combine two or more read operations within the ordered queue into the combined read operation, wherein combining the two or more storage requests comprises modifying an order of the storage requests within the ordered queue.

12. The apparatus of claim 10, wherein the combined read operation comprises providing different addressing information to the different sets of columns of the solid-state storage array.

13. The apparatus of claim 7, further comprising:

an ECC read module configured to detect an uncorrectable ECC codeword in response to a first read operation; and

a data recovery module configured to recover the uncorrectable ECC codeword by reading other ECC codewords within the vertical stripe with the uncorrectable ECC codeword in a second read operation, decoding the other ECC codewords, and reconstructing the uncorrectable ECC codeword using the decoded ECC codewords and parity data of the vertical stripe.

14. A system, comprising:

means for generating ECC codewords comprising data segments for storage on a plurality of solid-state storage elements, wherein each solid-state storage element of the plurality of solid-state storage elements are communicatively coupled to a storage controller by a bus, and each solid-state storage element is selected from the group including a package, a die, a plane, and a printed circuit board;

means for arranging the ECC codewords for storage in a vertical stripe configuration, wherein the vertical stripe configuration comprises arranging each ECC codeword for storage within a respective one of the solid-state storage elements, and wherein ECC codewords comprising a data segment are arranged for storage on two or more different solid-state storage elements; and

means for storing the arranged ECC codewords on the solid-state storage elements.

15. The system of claim 14, wherein the vertical stripe configuration comprises arranging ECC codewords within the solid-state storage elements at a vertical stripe depth, wherein the vertical stripe depth is less than a page size of the solid-state storage elements and is an integral factor of a size of the ECC codewords.

16. The system of claim 14, wherein the means for arranging the ECC codewords for storage in the vertical stripe configuration comprises:

means for streaming data rows of the arranged ECC codewords to respective program buffers of the solid-state storage array; and

means for calculating parity data corresponding to each of the data rows.

17. The system of claim 16, further comprising means for reconstructing a corrupt ECC codeword, comprising:

means for reading one or more other ECC codewords stored within a vertical stripe comprising the corrupt ECC codeword;

means for correcting the one or more other ECC codewords; and

means for reconstructing the corrupt ECC codeword using the corrected one or more other ECC codewords and parity data corresponding to data rows of the vertical stripe.

18. The system of claim 14, further comprising means for adaptive scheduling, comprising:

means for identifying respective sets of one or more solid-state storage elements comprising data of each of a plurality of queued read requests; and

means for determining a read operation configured to perform two or more of the queued read requests in a single read operation on the plurality of solid-state storage elements.