Look-ahead garbage collection for NAND flash based storage
One or more source locations in a group of solid state storage cells on which garbage collection is to be performed are stored in a garbage collection queue. A garbage collection speed is determined, including by: analyzing one or more source locations stored in the garbage collection queue; determining a look-ahead metric, wherein the look-ahead metric comprises an anticipated amount of freed up storage associated with the analyzed source locations; and determining the garbage collection speed based at least in part on the look-ahead metric. One or more garbage collection operations are performed interleaved with one or more host operations, wherein the ratio of garbage collection operations to host operations is based at least in part on the garbage collection speed.
1. A system, comprising:
a garbage collection queue configured to store one or more source locations, in a group of solid state storage cells on which garbage collection is to be performed;
a garbage collection scheduler configured to determine a garbage collection speed, including by:
analyzing one or more source locations stored in the garbage collection queue;
determining a look-ahead metric, wherein the look-ahead metric comprises an anticipated amount of freed up storage associated with the analyzed source locations; and
determining the garbage collection speed based at least in part on the look-ahead metric; and
a garbage collector configured to perform one or more garbage collection operations interleaved with one or more host operations, wherein the ratio of garbage collection operations to host operations is based at least in part on the garbage collection speed.
2. The system as recited in claim 1 , wherein a source location is a source block.
3. The system as recited in claim 2 , wherein determining the look-ahead metric comprises determining a number of valid pages within the analyzed source blocks.
4. The system as recited in claim 1 , wherein determining the look-ahead metric comprises analyzing one or more anticipated destination locations.
5. The system as recited in claim 1 , wherein the garbage collection scheduler is further configured to update the garbage collection speed.
6. The system as recited in claim 1 , wherein the group of solid state storage cells is associated with an LBA table update technique.
7. The system as recited in claim 6 , wherein the LBA table update technique comprises a delayed erase of source blocks.
8. The system as recited in claim 1 , wherein determining the look-ahead metric comprises determining a look-ahead parameter comprising a number of destination blocks to analyze.
9. The system as recited in claim 1 , wherein determining the look-ahead metric comprises finding a minimum quantity in an expression.
10. The system as recited in claim 1 , wherein determining the garbage collection speed further includes quantizing to a rational number.
11. The system as recited in claim 10 , wherein quantizing includes using a ceiling function.
12. The system as recited in claim 1 , wherein determining the look-ahead metric comprises determining a sum of free pages in a current host open block and total count of pages in all empty blocks.
13. The system as recited in claim 1 , wherein determining the look-ahead metric comprises determining a count of available pages in a block or superblock.
14. The system as recited in claim 1 , wherein determining the look-ahead metric comprises determining a count of written pages in a current destination block.
15. The system as recited in claim 1 , wherein determining the look-ahead metric comprises determining a minimum count of free pages guaranteed.
16. The system as recited in claim 1 , wherein determining the look-ahead metric comprises determining a count of former GC source blocks currently pending erasure.
17. The system as recited in claim 1 , wherein determining the look-ahead metric comprises determining a count of valid pages in one or more source blocks.
18. The system as recited in claim 1 , wherein determining the look-ahead metric comprises determining a smallest value that satisfies an inequality.
19. The system as recited in claim 18 , wherein the inequality comprises a fewest count of source blocks needed to fill up remaining pages in a current destination block and subsequent destination blocks.
20. A method, comprising:
storing in a garbage collection queue one or more source locations in a group of solid state storage cells on which garbage collection is to be performed;
determining a garbage collection speed, including by:
analyzing one or more source locations stored in the garbage collection queue;
determining a look-ahead metric, wherein the look-ahead metric comprises an anticipated amount of freed up storage associated with the analyzed source locations; and
determining the garbage collection speed based at least in part on the look-ahead metric; and
performing one or more garbage collection operations interleaved with one or more host operations, wherein the ratio of garbage collection operations to host operations is based at least in part on the garbage collection speed.