Heuristic aware garbage collection scheme in storage systems

• US 9,639,463 B1
• Filed: 09/17/2013
• Issued: 05/02/2017
• Est. Priority Date: 08/26/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Kankani, Navneeth, Kulkarni, Anand, Kwong, Charles See Yeung
• Primary Examiner(s): Hasan, Syed
• Assistant Examiner(s): ALLEN, NICHOLAS E
• Application Number:
  US14/029,647
• Time in Patent Office: 1,323 Days
• Field of Search: 707814, 707711
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

The various implementations described herein include systems, methods and/or devices used to enable heuristic aware garbage collection in storage systems (e.g., non-volatile data storage systems using one or more flash memory devices). In one aspect, a time parameter (e.g., dwell time) and/or heuristics (e.g., error count, error rate, number of reads, number of times programmed, etc.) are used in a garbage collection scheme. For example, in some implementations, the method of garbage collection for a storage medium in a storage system includes (1) determining a time parameter for a block in the storage medium, and (2) in accordance with a determination that the time parameter for the block is greater than a first threshold time, enabling garbage collection of the block.

Claims

1. A method of garbage collection for a storage medium in a storage system, the method comprising:

determining a time parameter for a block in the storage medium;

adapting a first threshold time based on one or more parameter values of the block;

in accordance with a determination that the time parameter for the block is greater than the first threshold time, as adapted, enabling garbage collection of the block;

selecting a first set of multiple blocks from the storage medium;

determining a second threshold time for the first set of multiple blocks, wherein the second threshold time is distinct from the first threshold time; and

for each block in the first set of multiple blocks, in accordance with a determination that the time parameter for the block is less than the second threshold time, suspending garbage collection of the block for a remaining duration of the second threshold time.

2. The method of claim 1, including:

in accordance with a determination that the time parameter for the block is greater than the first threshold time and that the block meets predefined staleness criteria, enabling garbage collection of the block.

3. The method of claim 1, wherein the time parameter is a dwell time, the dwell time being a time since a last program command to modify data stored in the block.

4. The method of claim 1, wherein the first threshold time is determined in accordance with one or more characteristics of the block.

5. The method of claim 1, wherein determining the time parameter for the block includes determining a time when the block was last programmed.

9. The method of claim 1, wherein the storage medium comprises one or more flash memory devices.

6. A method of garbage collection for a storage medium in a storage system, comprising:

selecting a first set of multiple blocks from the storage medium, wherein the storage system uses one or more parameter values to select blocks to include in the first set of multiple blocks;

determining a threshold time for the first set of multiple blocks;

for each block in the first set of multiple blocks, in accordance with a determination that a time parameter for the block is less than the determined threshold time, suspending garbage collection of the block for a remaining duration of the determined threshold time; and

suspending, in succession, garbage collection of each set of blocks, in two or more other sets of blocks in the storage medium, for a respective threshold time, before suspending garbage collection of the first set of blocks again.

7. The method of claim 6, wherein the one or more parameter values include at least one parameter in the set consisting of an error count for a respective block, an error rate for the respective block, number of reads from the respective block, number of times the respective block has been programmed, number of times the respective block has been erased, a read scrub frequency for the respective block, a dynamic read frequency for the respective block, and a reading threshold voltage margin for the respective block.

8. The method of claim 6, further comprising adapting the threshold time based on the one or more parameter values of the set of blocks, wherein the one or more parameter values include at least one parameter in the set consisting of an error count for the set of blocks, an error rate for the set of blocks, number of reads from the set of blocks, number of times the set of blocks has been programmed, number of times the set of blocks has been erased, a read scrub frequency for the set of blocks, a dynamic read frequency for the set of blocks, and a reading threshold voltage margin for the set of blocks.

10. A method of garbage collection for a storage medium in a storage system, the method comprising:

determining a time parameter for each unerased block in a set of blocks in the storage medium, wherein the set of blocks includes a first set of multiple blocks and a second set of multiple blocks distinct from the first set of multiple blocks;

identifying, in accordance with the time parameter for each unerased block in the set of blocks, garbage collection eligible blocks from among the first set of multiple blocks in accordance with a first threshold time, and identifying garbage collection eligible blocks from among the second set of multiple blocks in accordance with a second threshold time that is greater than the first threshold time; and

selecting a subset of the set of garbage collection eligible blocks for garbage collection in accordance with predefined staleness criteria.

11. The method of claim 10, wherein the storage medium comprises one or more flash memory devices.

12. A device operable to perform garbage collection for a storage medium, the device comprising:

a storage medium interface for coupling the device to the storage medium; and

one or more modules, including a memory management module that includes one or more processors and memory storing one or more programs configured for execution by the one or more processors, the one or more modules coupled to the storage medium interface and configured to;

determine a time parameter for each unerased block in a set of blocks in the storage medium, wherein the set of blocks includes a first set of multiple blocks and a second set of multiple blocks distinct from the first set of multiple blocks;

identify, in accordance with the time parameter for each unerased block in the set of blocks, garbage collection eligible blocks from among the first set of multiple blocks in accordance with a first threshold time, and identify garbage collection eligible blocks from among the second set of multiple blocks in accordance with a second threshold time that is greater than the first threshold time; and

select a subset of the set of garbage collection eligible blocks for garbage collection in accordance with predefined staleness criteria.

13. The device of claim 12, wherein the garbage collection eligible blocks from among the first set of blocks are identified in accordance with a determination that the time parameter for the garbage collection eligible blocks is greater than the first threshold time.

14. The device of claim 12, wherein the time parameter is a dwell time, the dwell time being a time since a last program command to modify data stored in the block.

15. The device of claim 12, wherein the first threshold time is determined in accordance with one or more characteristics of the first set of multiple blocks.

16. The device of claim 12, wherein determining the time parameter for the block includes determining a time when the block was last programmed.

20. The device of claim 12, wherein the storage medium comprises one or more flash memory devices.

17. A device operable to perform garbage collection for a storage medium, the device comprising:

a storage medium interface for coupling the device to the storage medium; and

one or more modules, including a memory management module that includes one or more processors and memory storing one or more programs configured for execution by the one or more processors, the one or more modules coupled to the storage medium interface and configured to;

select a first set of multiple blocks from the storage medium, wherein the storage system uses one or more parameter values to select blocks to include in the first set of multiple blocks;

determine a threshold time for the first set of multiple blocks;

for each block in the first set of multiple blocks, in accordance with a determination that a time parameter for the block is less than the determined threshold time, suspend garbage collection of the block for a remaining duration of the determined threshold time; and

suspend, in succession, garbage collection of each set of blocks, in two or more other sets of blocks in the storage medium, for a respective threshold time, before suspending garbage collection of the first set of blocks again.

18. The device of claim 17, wherein the one or more parameter values include at least one parameter in the set consisting of an error count for a respective block, an error rate for the respective block, number of reads from the respective block, number of times the respective block has been programmed, number of times the respective block has been erased, a read scrub frequency for the respective block, a dynamic read frequency for the respective block, and a reading threshold voltage margin for the respective block.

19. The device of claim 17, wherein the one or more modules are further configured to adapt the threshold time based on one or more parameter values of the set of blocks, wherein the one or more parameter values include at least one parameter in the set consisting of an error count for the set of blocks, an error rate for the set of blocks, number of reads from the set of blocks, number of times the set of blocks has been programmed, number of times the set of blocks has been erased, a read scrub frequency for the set of blocks, a dynamic read frequency for the set of blocks, and a reading threshold voltage margin for the set of blocks.

21. A device operable to perform garbage collection for a storage medium, the device comprising:

a storage medium interface for coupling the device to the storage medium; and

one or more modules, including a memory management module that includes one or more processors and memory storing one or more programs configured for execution by the one or more processors, the one or more modules coupled to the storage medium interface and configured to;

determine a time parameter for a block in the storage medium;

adapt a first threshold time based on one or more parameter values of the block;

in accordance with a determination that the time parameter for the block is greater than the first threshold time, as adapted, enable garbage collection of the block;

select a first set of multiple blocks from the storage medium;

determine a second threshold time for the first set of multiple blocks, wherein the second threshold time is distinct from the first threshold time; and

for each block in the first set of multiple blocks, in accordance with a determination that the time parameter for the block is less than the second threshold time, suspend garbage collection of the block for a remaining duration of the second threshold time.