System and method for dynamically adjusting garbage collection policies in solid-state memory
View Patent ↗Embodiments of the invention are directed to optimizing the selection of memory blocks for garbage collection in solid state devices to efficiently maximize the amount of memory freed by garbage collection operations. The systems and methods disclosed herein provide for the efficient selection of optimal or near-optimal garbage collection candidate blocks, with the most optimal selection defined as block(s) with the most invalid pages. In one embodiment, a controller classifies memory blocks into various invalid block pools by the amount of invalid pages each block contains. In one embodiment, the controller selects for garbage collection a block from a non-empty pool of blocks with the highest minimum amount of invalid pages. One or more of the pools have minimum thresholds that can be dynamically adjusted according to an observed usage condition, such as a change of an over-provisioning amount in the storage state device.
1. A method for selecting memory blocks in a non-volatile solid-state memory array of a storage subsystem for garbage collection commands, the method comprising:
maintaining statistical data related to an amount of invalid data within the memory blocks; and
assigning the memory blocks to pools and recording assignments of the memory blocks to the pools, such that each pool consists of memory blocks having an amount of invalid data that satisfies the respective pool's minimum threshold, wherein at least some of the pools have different minimum thresholds than others, wherein at least some of the minimum thresholds are fixed and at least one minimum threshold is dynamic; and
dynamically adjusting the minimum threshold associated with at least one of the pools based on an observed usage condition in the non-volatile solid-state memory array.
2. The method of claim 1 , further comprising:
selecting a memory block assigned to a pool with the highest minimum threshold for garbage collection.
3. The method of claim 2 , wherein the selecting further comprises:
traversing said plurality of pools beginning with a pool with the highest minimum threshold to identify a pool with the highest minimum threshold with at least one memory block assigned to the pool.
4. The method of claim 1 , wherein the observed usage condition reflects a change in an amount of over-provisioned capacity in the non-volatile solid-state memory array.
5. The method of claim 1 , wherein the observed usage condition reflects one or more ranges of a number of invalid pages in memory blocks in the non-volatile solid-state memory array.
6. The method of claim 5 , wherein the range is detected through observing percentages of invalid pages in blocks that have been garbage collected.
7. The method of claim 6 , wherein the percentages are tracked in a histogram.
8. The method of claim 1 further comprising:
re-assigning at least one memory block in one of the plurality of pools other than the one with the adjusted minimum threshold to reflect the adjusting of the minimum threshold.
9. The method of claim 1 further comprising:
updating the statistical data when a memory command causes a validity of a page within one of the memory blocks to be changed; and
re-assigning the memory block containing the changed page to a new pool with a higher minimum threshold of invalid data when an amount of invalid data reflected in the updated statistical data meets the higher minimum threshold.
10. The method of claim 1 , wherein recording assignments of the memory blocks to the pools further comprises using a data marker to indicate the assignment of a memory block to a pool.
11. The method of claim 1 further comprising updating at least some of the assignments of the memory blocks to the pools as part of performing garbage collection.
12. A storage subsystem, comprising:
a non-volatile solid-state memory array; and
a controller configured to:
maintain, for a memory block in the non-volatile solid-state memory array, statistical data related to a number of invalid pages within the memory block;
assign the memory blocks to pools and record assignments of the memory blocks to the pools, such that each pool consists of memory blocks having an amount of invalid data that satisfies the respective pool's minimum threshold, wherein at least some of the pools have different minimum thresholds than others, wherein at least some of the minimum thresholds are fixed and at least one minimum threshold is dynamic; and
adjust the minimum threshold associated with at least one of the pools based on an observed usage condition in the non-volatile solid-state memory array.
13. The storage subsystem of claim 12 , wherein the controller is further configured to:
upon execution of a memory command that causes a change in a validity of a page within the memory block,
update the statistical data associated with the memory block; and
reassign the memory block to another pool when the updated statistical data reflects a number of invalid pages within the memory block that meets a minimum threshold of another pool with a higher minimum threshold than the minimum threshold of the pool to which the memory block is currently assigned.
14. The storage subsystem of claim 12 , wherein the observed usage condition reflects a change in an amount of over-provisioned capacity in the non-volatile solid-state memory array.
15. The storage subsystem of claim 12 , wherein the observed usage condition reflects one or more ranges of a number of invalid pages in memory blocks in the non-volatile solid-state memory array.
16. The storage subsystem of claim 15 , wherein the range is detected through observing percentages of invalid pages in blocks that have been garbage collected.
17. The storage subsystem of claim 16 , wherein the percentages are tracked in a histogram.
18. The storage subsystem of claim 12 , wherein the controller is further configured to select, for garbage collection, a memory block assigned to a pool with a highest minimum threshold.
19. The storage subsystem of claim 12 , wherein the plurality of pools comprise a pool configured for memory blocks with at least 7% invalid pages, a pool initially configured for memory blocks with at least 50% invalid pages, a pool initially configured for memory blocks with at least 75% invalid pages, a pool configured for memory blocks with 100% invalid pages, and a pool configured for memory blocks with a percent of invalid pages that match a percentage of capacity in the non-volatile solid-state memory array that is reserved for over-provisioning.
20. The storage subsystem of claim 12 , wherein the controller is configured to record assignments of the memory blocks to the pools further by using a data marker to indicate the assignment of a memory block to a pool.
21. The storage subsystem of claim 12 wherein the controller is further configured to update at least some of the assignment of the memory blocks to the pools as part of performing garbage collection.