System and method for tolerating a failed page in a flash device

• US 9,047,214 B1
• Filed: 05/22/2012
• Issued: 06/02/2015
• Est. Priority Date: 05/22/2012
• Status: Active Grant

• Current Assignee: Ip Gem Group, LLC
• Original Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Inventors: Northcott, Philip L.
• Primary Examiner(s): Kerveros, James C
• Application Number:
  US13/477,635
• Time in Patent Office: 1,106 Days
• Field of Search: 714/763, 714/770, 714/773
• US Class Current: 1/1
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/1044 with specific ECC/EDC distribution
• CPC Class Codes: G06F 11/106 Correcting systematically all correctable errors, i.e. scrubbing
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers

Abstract

Apparatus and methods provide relatively low uncorrectable bit error rates, low write amplification, long life, fast and efficient retrieval, and efficient storage density such that a solid-state drive (SSD) can be implemented using relatively inexpensive MLC Flash for an enterprise storage application. A page is associated with a set of primary ECC codewords, and a page stripe is associated with a set of secondary codewords and primary over secondary parity (PoSP) ECC codewords. Two or more page stripes can form a page grid, wherein the page grid is associated with a group of tertiary ECC codewords, wherein the last page stripe of the page grid has a reduced payload capacity.

Claims

1. A method of programming data to a plurality of flash memory devices, the method comprising:

associating two or more flash memory pages or integer fractions of flash memory pages from one or more integrated circuits or planes with a page stripe, wherein a page is associated with a set of primary ECC codewords;

associating two or more page stripes from different integrated circuits or planes with a page grid, wherein the page grid is associated with a group of tertiary ECC codewords, wherein the tertiary ECC is usable as an erasure code, and wherein a last page stripe of the page grid has a reduced payload capacity;

receiving data to be programmed;

error correction encoding the received data to be stored within each page stripe to generate at least primary ECC codewords for the pages or integer fractions of pages of the page stripe, wherein the primary ECC codewords comprise both data and primary parity;

calculating tertiary ECC parity across the page grid, wherein a tertiary ECC codeword includes a number of symbols including both the data and the primary parity of the primary ECC codewords residing on every page no greater than the erasure capability of the tertiary ECC codeword;

arranging the tertiary parity data, wherein the tertiary parity data is broken up and spread for programming across the last page stripe of the page grid; and

programming the pages of the page grid to store at least the received data, the primary parity data, and the tertiary parity data, wherein each bit of the received data is protected by both primary parity and tertiary parity, wherein the data and the primary parity of primary ECC codewords are stored within the same page or same integer fraction of the page;

wherein at least performing error correction encoding is performed in an integrated circuit.

2. The method of claim 1, further comprising:

calculating fingerprints for pages based at least partly on physical addresses of the pages; and

programming the pages with the fingerprints.

3. The method of claim 1, wherein the flash memory devices comprise multi-level memory cells.

4. The method of claim 1, wherein the tertiary codewords are Reed-Solomon codewords.

5. The method of claim 1, wherein the Tertiary ECC has a correction capability equal to half of the maximum number of symbols that each tertiary codeword has on any one page of the page grid, plus at least TTs*(Ws−

1)/(Wt*Wg*Ws) symbols, wherein TTs is the total correction capability of ECC codewords calculated across multiple pages of a page stripe, Ws is the number of pages in a page stripe, Wt is the number of Tertiary codewords, and Wg is the number of page stripes in a page grid.

6. The method of claim 1, further comprising further encoding the tertiary parity symbols on each page of the last page stripe with a primary over tertiary parity (PoTP) code to form PoTP codewords, wherein the PoTP code is programmed into each page of the last page stripe.

7. The method of claim 1, further comprising:

reserving an area of scratchpad memory for storing interim tertiary parity calculation results;

calculating and updating calculations of tertiary parity symbols as data is being received for and written to pages of the page grid, wherein the interim parity calculation results are maintained in the scratchpad memory; and

when calculation of tertiary parity symbols is complete, retrieving the tertiary parity symbols from the scratchpad memory and programming the tertiary parity symbols to the last page stripe.

8. The method of claim 7, further comprising:

maintaining a plurality of areas of scratchpad memories for storing the interim parity calculation results of a plurality of page grids; and

calculating and updating calculations of tertiary parity symbols as data is being received for and written to pages of a plurality of different page grids, wherein the interim parity calculation results are maintained in the scratchpad memory such that an ECC encoder can encode page stripes of different page grids that are interleaved in time.

9. The method of claim 1, wherein a page stripe is associated with a set of secondary codewords and primary over secondary parity (PoSP) ECC codewords.

10. An apparatus comprising:

a first circuit configured to associate two or more flash memory pages or integer fractions of flash memory pages from one or more integrated circuits or planes with a page stripe, wherein a page is associated with a set of primary ECC codewords;

the first circuit is further configured to associate two or more page stripes from different integrated circuits or planes with a page grid, wherein the page grid is associated with a group of tertiary ECC codewords, wherein the tertiary ECC is usable as an erasure code, and wherein a last page stripe of the page grid has a reduced payload capacity;

the first circuit is further configured to receive data to be programmed;

a second circuit configured to error correction encode the received data to be stored within each page stripe to generate at least primary ECC codewords for the pages or integer fractions of pages of the page stripe, wherein the primary ECC codewords comprise both data and primary parity;

the second circuit is further configured to calculate tertiary ECC parity across the page grid in a sequence, wherein a tertiary ECC codeword includes a number of symbols including both the data and parity of the primary ECC codewords residing on every page no greater than the erasure capability of the tertiary ECC codeword;

the first circuit is further configured to arrange the tertiary parity data, wherein the tertiary parity data is broken up and spread for programming across the last page stripe of the page grid; and

the first circuit is further configured to program the pages of the page grid to store at least the received data, the primary parity data, and the tertiary parity data wherein each bit of the received data is protected by both primary parity and tertiary parity, wherein the data and the primary parity of primary ECC codewords are stored within the same page or same integer fraction of the page, wherein data is programmed to a plurality of flash memory devices.

11. The apparatus of claim 10, wherein the first circuit is further configured to:

calculate fingerprints for pages based at least partly on physical addresses of the pages; and

program the pages with the fingerprints.

12. The apparatus of claim 10, wherein the flash memory devices comprise multi-level memory cells.

13. The apparatus of claim 10, wherein the tertiary codewords are Reed-Solomon codewords.

14. The apparatus of claim 10, wherein the Tertiary ECC has a correction capability equal to half of the maximum number of symbols that each tertiary codeword has on any one page of the page grid, plus at least TTs*(Ws−

1)/(Wt*Wg*Ws) symbols, wherein TTs is the total correction capability of ECC codewords calculated across multiple pages of a page stripe, Ws is the number of pages in a page stripe, Wt is the number of Tertiary codewords, and Wg is the number of page stripes in a page grid.

15. The apparatus of claim 10, wherein the second circuit is further configured to encode the tertiary parity symbols on each page of the last page stripe with a primary over tertiary parity (PoTP) code to form PoTP codewords, wherein the first circuit is further configured to program the PoTP code into each page of the last page stripe.

16. The apparatus of claim 10, further comprising:

wherein the first circuit is further configured to reserve an area of scratchpad memory to store interim tertiary parity calculation results;

wherein the second circuit is further configured to calculate and update calculations of tertiary parity symbols as data is being received for and written to pages of the page grid, wherein the interim parity calculation results are maintained in the scratchpad memory; and

when calculation of tertiary parity symbols is complete, the first circuit is configured to retrieve the tertiary parity symbols from the scratchpad area and program the tertiary parity symbols to the last page stripe.

17. The apparatus of claim 16, further comprising:

wherein the first circuit is further configured to maintain a plurality of areas of scratchpad memories for storing the interim parity calculation results of a plurality of page grids; and

wherein the second circuit is further configured to calculate and update calculations of tertiary parity symbols as data is being received for and written to pages of a plurality of different page grids, wherein the interim parity calculation results are maintained in the scratchpad memory such that an ECC encoder can encode page stripes of different page grids that are interleaved in time.

18. The apparatus of claim 10, wherein a page stripe is associated with a set of secondary codewords and primary over secondary parity (PoSP) ECC codewords.

19. An apparatus for programming data to a plurality of flash memory devices, the apparatus comprising:

a means for associating two or more flash memory pages or integer fractions of flash memory pages from one or more integrated circuits or planes with a page stripe, wherein a page is associated with a set of primary ECC codewords;

a means for associating two or more page stripes from different integrated circuits or planes with a page grid, wherein the page grid is associated with a group of tertiary ECC codewords, wherein the tertiary ECC is usable as an erasure code, and wherein a last page stripe of the page grid has a reduced payload capacity;

a means for receiving data to be programmed;

a means for error correction encoding the received data to be stored within each page stripe to generate at least primary ECC codewords for the pages or integer fractions of pages of the page stripe, wherein the primary ECC codewords comprise both data and primary parity;

a means for calculating tertiary ECC parity across the page grid in a sequence, wherein a tertiary ECC codeword includes a number of symbols including both the data and parity of the primary ECC codewords residing on every page no greater than the erasure capability of the tertiary ECC codeword;

a means for arranging the tertiary parity data, wherein the tertiary parity data is broken up and spread for programming across the last page stripe of the page grid; and

a means for programming the pages of the page grid to store at least the received data, the primary parity data, and the tertiary parity data, wherein each bit of the received data is protected by both primary parity and tertiary parity, wherein the data and the primary parity of primary ECC codewords are stored within the same page or same integer fraction of the page.

20. The apparatus of claim 19, further comprising:

a means for calculating fingerprints for pages based at least partly on physical addresses of the pages; and

the programming means further programming the pages with the fingerprints.

21. The apparatus of claim 19, wherein the flash memory devices comprise multi-level memory cells.

22. The apparatus of claim 19, wherein the tertiary codewords are Reed-Solomon codewords.

23. The apparatus of claim 19, wherein the Tertiary ECC has a correction capability equal to half of the maximum number of symbols that each tertiary codeword has on any one page of the page grid, plus at least TTs*(Ws−

1)/(Wt*Wg*Ws) symbols, wherein TTs is the total correction capability of ECC codewords calculated across multiple pages of a page stripe, Ws is the number of pages in a page stripe, Wt is the number of Tertiary codewords, and Wg is the number of page stripes in a page grid.

24. The apparatus of claim 19, the error correction encoding means further encoding the tertiary parity symbols on each page of the last page stripe with a primary over tertiary parity (PoTP) code to form PoTP codewords, wherein the PoTP code is programmed into each page of the last page stripe.

25. The apparatus of claim 19, further comprising:

a means for reserving an area of scratchpad memory for storing interim tertiary parity calculation results;

a means for retrieving;

the error correction encoding means further calculating and updating calculations of tertiary parity symbols as data is being received for and written to pages of the page grid, wherein the interim parity calculation results are maintained in the scratchpad memory; and

when calculation of tertiary parity symbols is complete, the retrieving means retrieving the tertiary parity symbols from the scratchpad memory and the programming means further programming the tertiary parity symbols to the last page stripe.

26. The apparatus of claim 25, further comprising:

means for maintaining a plurality of areas of scratchpad memories for storing the interim parity calculation results of a plurality of page grids; and

the error correction encoding means further calculating and updating calculations of tertiary parity symbols as data is being received for and written to pages of a plurality of different page grids, wherein the interim parity calculation results are maintained in the scratchpad memory such that an ECC encoder can encode page stripes of different page grids that are interleaved in time.

27. The apparatus of claim 19, wherein a page stripe is associated with a set of secondary codewords and primary over secondary parity (PoSP) ECC codewords.