Heuristic aware garbage collection scheme in storage systems
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
531 Citations
21 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. - View Dependent Claims (2, 3, 4, 5, 9)
-
-
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. - View Dependent Claims (7, 8)
-
-
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. - View Dependent Claims (11)
-
-
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. - View Dependent Claims (13, 14, 15, 16, 20)
-
-
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. - View Dependent Claims (18, 19)
-
-
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.
-
Specification