Systems and methods for storing data in page stripes of a flash drive

• US 9,176,812 B1
• Filed: 05/22/2012
• Issued: 11/03/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., Geiger, Peter Dau, Sadowsky, Jonathan
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): DORMAN, CHRISTIAN M
• Application Number:
  US13/477,568
• Time in Patent Office: 1,260 Days
• Field of Search: 714/773
• 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/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/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

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. Data is stored in page stripes. The page stripes can have varying amounts of payload capacity based on selected error correction code strength. Allocation blocks can be divided into journaling cells, correspond to minimum units of data for which a journaling engine or flash translation layer has a logical-to-physical mapping.

Claims

1. A method of storing data to an array of flash memory devices, the method comprising:

maintaining one or more lists of page stripes indicating at least which page stripes are available to be programmed, the one or more lists of page stripes associating, for an available page stripe, the following;

one or more physical addresses of pages or integer fractions of pages for the page stripe, wherein each page stripe comprises a fixed number of the pages or the integer fractions of the pages; and

a gear setting for the page stripe, the gear setting indicating an error correction scheme and corresponding payload size assigned to the page stripe, wherein the gear setting that is assigned to the page stripe is selected from one of a plurality of gear settings, wherein different gear settings of the plurality of gear settings vary in error correction code strength and in payload size, wherein the gear setting is selected to compensate for degradation in the performance of underlying memory cells of the page stripe;

maintaining one or more lists associating at least virtual addresses with physical addresses for data stored within the array of flash memory devices, wherein a virtual address is associated with at least one physical address;

receiving an allocation block, a virtual address identifying the allocation block, and a request for storage of the allocation block into the array of flash memory devices;

determining, based at least partly on the gear assigned to a current page stripe and an amount of data, if any, already assigned to the current page stripe, an extent to which the allocation block can be stored within an available payload of the current page stripe, wherein the current page stripe corresponds to a page stripe selected from the one or more lists of page stripes that are available to be programmed;

assigning at least a first subset of the allocation block to the payload of the selected page stripe;

storing an association of the virtual address with (a) the physical address of the current page stripe, and with (b) a starting location of the allocation block within the current page stripe;

when enough data has been collected to consider the payload of the current page stripe as full;

performing or having error correction encoding performed for the data of the payload in accordance with the gear setting associated with the current page stripe;

programming the current page stripe to the array;

associating the current page stripe with programmed page stripes;

selecting a next page stripe from the one or more lists of available page stripes for subsequent programming;

if the allocation block had not been fully assigned to the payload of the current page stripe;

assigning a remainder of the allocation block to a payload of the next page stripe; and

storing an additional association of the virtual address with the physical address of the next page stripe;

wherein the method is performed by an integrated circuit.

2. The method of claim 1, further comprising dividing the allocation block into a plurality of journaling cells each of constant payload size irrespective of gear setting, wherein a payload capacity of each page stripe corresponds to a capacity of a whole number of journaling cells at least equal to the maximum number of cells of an allocation block, wherein a journaling cell corresponds to a minimum unit of data for which a journaling engine or flash translation layer has a logical-to-physical mapping.

3. The method of claim 2, wherein the gear setting of a page stripe is encoded in the form of a payload capacity, represented as a whole number of journaling cells, of the page stripe when the gear setting is used.

4. The method of claim 1, when there has not been enough data collected to fill the payload of the current page stripe, waiting until more data is received unless there is not enough remaining payload capacity to store another allocation block in a block grid associated with the current page stripe, in which case, padding the remainder of the current page stripe for programming.

5. The method of claim 1, wherein the one or more lists of page stripes indicating at least which page stripes are available to be programmed also indicate page stripes that have been programmed, wherein a status of a particular page stripe is indicated by a flag in the one or more lists.

6. The method of claim 1, further comprising collecting data of multiple allocation blocks to be programmed to the current page stripe in a buffer of volatile memory until the current page stripe is ready to be ECC encoded and programmed to the array.

7. The method of claim 1, wherein the payload of the current page stripe is considered as full when an additional journaling cell cannot be accommodated.

8. An apparatus comprising:

a first circuit configured to maintain one or more lists of page stripes indicating at least which page stripes are available to be programmed, the one or more lists of page stripes associating, for an available page stripe, the following;

one or more physical addresses of pages or integer fractions of pages for the page stripe, wherein each page stripe comprises a fixed number of the pages or the integer fractions of the pages; and

a gear setting for the page stripe, the gear setting indicating an error correction scheme and corresponding payload size assigned to the page stripe, wherein the gear setting that is assigned to the page stripe is selected from one of a plurality of gear settings, wherein different gear settings of the plurality of gear settings vary in error correction code strength and in payload size, wherein the gear setting is selected to compensate for degradation in the performance of underlying memory cells of the page stripe;

the first circuit further configured to maintain one or more lists associating at least virtual addresses with physical addresses for data stored within an array of flash memory devices, wherein a virtual address is associated with at least one physical address;

the first circuit further configured to receive an allocation block, a virtual address identifying the allocation block, and a request for storage of the allocation block into the array of flash memory devices;

the first circuit further configured to determine, based at least partly on the gear assigned to a current page stripe and an amount of data, if any, already assigned to the current page stripe, an extent to which the allocation block can be stored within an available payload of the current page stripe, wherein the current page stripe corresponds to a page stripe selected from the one or more lists of page stripes available for programming;

the first circuit further configured to assign at least a first subset of the allocation block to the payload of the selected page stripe;

the first circuit further configured to store an association of the virtual address with (a) the physical address of the current page stripe, and with (b) a starting location of the allocation block within the current page stripe;

when enough data has been collected to consider the payload of the current page stripe as full;

a second circuit is configured to perform error correction encoding performed for the data of the payload in accordance with the gear setting associated with the current page stripe;

the first circuit is configured to program the current page stripe to the array;

the first circuit is configured to associate the current page stripe with programmed page stripes;

the first circuit is configured to select a next page stripe from the one or more lists of available page stripes for subsequent programming;

if the allocation block had not been fully assigned to the payload of the current page stripe;

the first circuit is configured to assign a remainder of the allocation block to a payload of the next page stripe; and

the first circuit is configured to store an additional association of the virtual address with the physical address of the next page stripe.

9. The apparatus of claim 8, wherein the first circuit is further configured to divide the allocation block into a plurality of journaling cells each of constant payload size, wherein a payload capacity of each page stripe corresponds to a capacity of a whole number of journaling cells at least equal to the maximum number of cells of an allocation block, wherein a journaling cell corresponds to a minimum unit of data for which a journaling engine or flash translation layer has a logical-to-physical mapping.

10. The apparatus of claim 9, wherein the gear setting of a page stripe is encoded in the form of a payload capacity, represented as a whole number of journaling cells, of the page stripe when the gear setting is used.

11. The apparatus of claim 8, when there has not been enough data collected to fill the payload of the current page stripe, the first circuit is configured to wait until more data is received unless there is not enough remaining payload capacity to store another allocation block in a block grid associated with the current page stripe, in which case, the first circuit is configured to pad the remainder of the current page stripe and program the current page stripe.

12. The apparatus of claim 8, wherein the one or more lists of page stripes indicating at least which page stripes are available to be programmed also indicate page stripes that have been programmed, wherein a status of a particular page stripe is indicated by a flag in the one or more lists.

13. The apparatus of claim 8, the first circuit is configured to collect data of multiple allocation blocks to be programmed to the current page stripe in a buffer of volatile memory until the current page stripe is ready to be ECC encoded and programmed to the array.

14. The apparatus of claim 8, wherein the payload of the current page stripe is considered as full when an additional journaling cell cannot be accommodated.

15. An apparatus for storing data to an array of flash memory devices, the apparatus comprising:

a means for maintaining one or more lists of page stripes indicating at least which page stripes are available to be programmed, the one or more lists of page stripes associating, for an available page stripe, the following;

one or more physical addresses of pages or integer fractions of pages for the page stripe, wherein each page stripe comprises a fixed number of the pages or the integer fractions of the pages; and

a gear setting for the page stripe, the gear setting indicating an error correction scheme and corresponding payload size assigned to the page stripe, wherein the gear setting that is assigned to the page stripe is selected from one of a plurality of gear settings, wherein different gear settings of the plurality of gear settings vary in error correction code strength and in payload size, wherein the gear setting is selected to compensate for degradation in the performance of underlying memory cells of the page stripe;

the maintaining means further maintaining one or more lists associating at least virtual addresses with physical addresses for data stored within the array of flash memory devices, wherein a virtual address is associated with at least one physical address;

a means for receiving an allocation block, a virtual address identifying the allocation block, and a request for storage of the allocation block into the array of flash memory devices;

a means for determining, based at least partly on the gear assigned to a current page stripe and an amount of data, if any, already assigned to the current page stripe, an extent to which the allocation block can be stored within an available payload of the current page stripe, wherein the current page stripe corresponds to a page stripe selected from the one or more lists of page stripes that are available to be programmed;

a means for assigning at least a first subset of the allocation block to the payload of the selected page stripe;

a means for storing an association of the virtual address with (a) the physical address of the current page stripe, and with (b) a starting location of the allocation block within the current page stripe;

when enough data has been collected to consider the payload of the current page stripe as full;

a means for performing or having error correction encoding performed for the data of the payload in accordance with the gear setting associated with the current page stripe;

a means for programming the current page stripe to the array;

a means for associating the current page stripe with programmed page stripes;

a means for selecting a next page stripe from the one or more lists of available page stripes for subsequent programming;

if the allocation block had not been fully assigned to the payload of the current page stripe;

the assigning means further assigning a remainder of the allocation block to a payload of the next page stripe; and

the association storing means further storing an additional association of the virtual address with the physical address of the next page stripe.

16. The apparatus of claim 15, further comprising means for dividing the allocation block into a plurality of journaling cells each of constant payload size, wherein a payload capacity of each page stripe corresponds to a capacity of a whole number of journaling cells at least equal to the maximum number of cells of an allocation block, wherein a journaling cell corresponds to a minimum unit of data for which a journaling engine or flash translation layer has a logical-to-physical mapping.

17. The apparatus of claim 16, wherein the gear setting of a page stripe is encoded in the form of a payload capacity, represented as a whole number of journaling cells, of the page stripe when the gear setting is used.

18. The apparatus of claim 15, when there has not been enough data collected to fill the payload of the current page stripe, the assigning means further waiting until more data is received unless there is not enough remaining payload capacity to store another allocation block in a block grid associated with the current page stripe, in which case, the assigning means is further configured to pad the remainder of the page stripe for programming.

19. The apparatus of claim 15, wherein the one or more lists of page stripes indicating at least which page stripes are available to be programmed also indicate page stripes that have been programmed, wherein a status of a particular page stripe is indicated by a flag in the one or more lists.

20. The apparatus of claim 15, the assigning means further collecting data of multiple allocation blocks to be programmed to the current page stripe in a buffer of volatile memory until the current page stripe is ready to be ECC encoded and programmed to the array.

21. The apparatus of claim 15, wherein the payload of the current page stripe is considered as full when an additional journaling cell cannot be accommodated.