Systems and methods for adaptive error-correction coding

• US 9,116,823 B2
• Filed: 03/14/2013
• Issued: 08/25/2015
• Est. Priority Date: 12/06/2006
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Intelligent Intellectual Property Holdings LLC
• Inventors: Fillingim, Jeremy, Flynn, David, Strasser, John, Inskeep, Bill
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Ahmed, Enam
• Application Number:
  US13/830,652
• Publication Number:
  US 20130205183A1
• Time in Patent Office: 894 Days
• Field of Search: 714/773
• US Class Current: 1/1
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• 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 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: 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/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics
• CPC Class Codes: H03M 13/353 Adaptation to the channel
• CPC Class Codes: H04L 12/46 Interconnection of networks
• 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]

Abstract

A storage module is configured to store data segments, such as error-correcting code (ECC) codewords, within an array comprising a plurality of columns. The ECC codewords may comprise ECC codeword symbols. The ECC symbols of a data segment may be arranged in a horizontal arrangement, a vertical arrangement, a hybrid channel arrangement, and/or vertical stripe arrangement within the array. The individual ECC symbols may be stored within respective columns of the array (e.g., may not cross column boundaries). Data of an unavailable ECC symbol may be reconstructed by use of other ECC symbols stored on other columns of the array.

Claims

1. An apparatus, comprising:

an error-correcting code (ECC) write module configured to generate a plurality of ECC codeword symbols comprising data of a storage request;

wherein each of the ECC codeword symbols is configured for storage within one or more respective columns of a solid-state storage array, each column comprising one or more solid-state storage elements; and

an adaptive write module configured to stream each of the ECC codeword symbols comprising the data of the storage request to at least one respective column of a set of two or more columns of the solid-state storage array,

wherein the ECC write module is configured to generate multi-byte ECC codeword symbols, wherein the adaptive write module is configured to stream portions of the multi-byte ECC codeword symbols to respective solid-state storage elements in each of a plurality of stream cycles, and wherein the adaptive write module is further configured to stream the portions of the multi-byte ECC codeword symbols such that the portions of each multi-byte ECC codeword symbol are streamed to a respective one of the solid-state storage elements.

2. The apparatus of claim 1, wherein the adaptive write module is configured to stream the ECC codeword symbols to the solid-state storage array in a plurality of data rows, each data row comprising data for storage within a respective one of the columns, the apparatus further comprising a parity module configured to generate parity data corresponding to each of the data rows.

3. The apparatus of claim 1, wherein the adaptive write module is configured to stream the ECC codeword symbols comprising the data of the storage request to a first independent channel comprising a subset of the columns of the solid-state storage array with ECC codeword symbols comprising data of another storage request to a different independent channel comprising a different subset of the columns of the solid-state storage array.

4. The apparatus of claim 1, further comprising:

a read module configured to read a plurality of ECC codeword symbols stored within a plurality of different solid-state storage elements, wherein each ECC codeword symbol is read from a respective one of the solid-state storage elements; and

a data recovery module configured to reconstruct an unavailable ECC codeword symbol read from a first one of the solid-state storage elements using other ECC codeword symbols stored on others of the solid-state storage elements.

5. The apparatus of claim 4, wherein the data recovery module is configured to reconstruct the unavailable ECC codeword symbol by use of parity data corresponding to the unavailable codeword and other ECC codeword symbols.

6. The apparatus of claim 1, wherein the data of the storage request comprises one of a data packet, a data segment, a block, and a sector, and wherein the ECC write module is configured to generate a plurality of ECC codeword symbols comprising the data, and wherein the adaptive write module is configured to distribute the ECC codeword symbols between a plurality of different solid-state storage elements.

7. The apparatus of claim 1, wherein the adaptive write module is configured to stream a respective ECC codeword symbol to a plurality of solid-state storage elements in each of a plurality of stream cycles, the apparatus further comprising a parity module configured to generate parity data corresponding to the ECC symbols being streamed to the plurality of solid-state storage elements in the stream cycle, wherein the adaptive write module is configured to stream the parity data with the ECC codeword symbols corresponding to the parity data.

8. The apparatus of claim 1, wherein the ECC write module is configured to generate one-byte ECC codeword symbols, and wherein the adaptive write module is configured to stream a respective one of the ECC codeword symbols to each of a plurality of solid-state storage elements in each of a plurality of bus cycles.

9. A computer program product comprising a non-transitory computer readable storage medium storing computer usable program code executable to perform operations, the operations comprising:

generating multi-byte error-correcting code (ECC) codeword symbols;

streaming portions of the multi-byte ECC codeword symbols to respective solid-state storage elements in each of a plurality of stream cycles, said streaming comprising streaming each multi-byte ECC codeword symbol to a respective one of the solid-state storage elements;

determining a storage location of a plurality of error-correcting code (ECC) codeword symbols comprising requested data;

identifying ECC codeword symbols comprising data of one or more other requests stored within different groups of the solid-state storage elements; and

scheduling a read operation configured to read the ECC codeword symbols of the requested data and ECC codewords comprising data of the one or more other requests in a single read operation on the solid-state storage elements.

10. The computer program product of claim 9, the operations further comprising verifying that the ECC codeword symbols comprise the requested data by verifying a mark on the ECC codeword symbols corresponding to relational information pertaining to the requested data.

11. The computer program product of claim 9, the operations further comprising:

queuing storage requests in a request buffer; and

determining a storage location of ECC codewords of one or more other requests in the request buffer.

12. The computer program product of claim 11, wherein scheduling the read operation comprises reordering one or more storage requests in the request buffer.

13. The computer program product of claim 11, wherein scheduling the read operation comprises indicating different addressing information for two or more of the solid-state storage elements.

14. The computer program product of claim 13, further comprising reordering contents of a read buffer to reconstruct a data packet stored within the plurality of ECC codeword symbols comprising the requested data.

15. A system, comprising:

means for generating a plurality of sets of error-correcting code (ECC) symbols, wherein each set of ECC symbols comprises data of different respective storage requests;

means for arranging the sets of ECC symbols for storage within different independent channels, each channel comprising two or more solid-state storage elements; and

means for storing the arranged sets of ECC symbols to the different independent channels, comprising means for storing each ECC symbol within a respective one of the solid-state storage elements of a respective independent channel,

wherein the means for generating is configured to generate multi-byte ECC codeword symbols, wherein the means for arranging is configured to stream portions of the multi-byte ECC codeword symbols to respective solid-state storage elements in each of a plurality of stream cycles, and wherein the means for arranging is further configured to stream the portions of the multi-byte ECC codeword symbols such that the portions of each multi-byte ECC codeword symbol are streamed to a respective one of the solid-state storage elements.

16. The system of claim 15, further comprising:

means for identifying an independent channel comprising a set of ECC symbols corresponding to requested data; and

means for extracting the requested data from the set of ECC symbols read from the identified independent channel.

17. The system of claim 15, further comprising means for combining two or more read requests pertaining to ECC symbols stored within different independent channels.

18. The system of claim 15, further comprising means for reconstructing an uncorrectable ECC symbol read from one of the solid-state storage elements by use of a plurality of ECC symbols stored within others of the solid-state storage elements.