Selection of units for garbage collection in flash memory

• US 8,417,878 B2
• Filed: 09/20/2010
• Issued: 04/09/2013
• Est. Priority Date: 09/20/2010
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Goss, Ryan James, Gaertner, Mark Allen
• Primary Examiner(s): Farrokh, Hashem
• Application Number:
  US12/886,196
• Publication Number:
  US 20120072639A1
• Time in Patent Office: 932 Days
• Field of Search: 711/103, 707/813
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

A data structure is formed that references a garbage collection metric for each of a plurality of associated garbage collection units of a flash memory device. Each garbage collection metric is based on one or more device state characteristics of the associated garbage collection unit. In response to a threshold change in the one or more device state variables, a region of interest within the data structure is sorted based on the garbage collection metrics. One or more garbage collection units are selected for garbage collection operations from the sorted region of interest.

Claims

1. A method comprising:

forming a data structure referencing a garbage collection metric for each of a plurality of associated garbage collection units of a flash memory device, each garbage collection metric based on one or more device state variables of the associated garbage collection unit;

in response to a threshold change in the one or more device state variables, sorting a region of interest within the data structure based on the garbage collection metrics; and

selecting one or more garbage collection units for garbage collection operations from the sorted region of interest.

2. The method of claim 1, wherein the garbage collection units with a high range of garbage collection metric values are selected first for the garbage collection operations, and wherein the region of interest comprises the garbage collection units having the high range of the garbage collection metric values.

3. The method of claim 2, wherein, if the region of interest does not comprise any garbage collection metrics, defining an other portion of the data structure as the region of interest and sorting within the other portion.

4. The method of claim 1, wherein the data structure comprises a plurality of segments each comprising one or more elements that make reference to the garbage collection metrics, wherein boundaries of the segments are determined based on the garbage collection metrics of the elements within the segments, and wherein the region of interest encompasses at least one of the plurality of segments.

5. The method of claim 4, further comprising:

determining a new element that is to be added to the data structure; and

if a garbage collection metric associated with the new element causes the new element to be added to the region of interest, inserting at least the new element in a sorted order into the region of interest.

6. The method of claim 5, further comprising, if the garbage collection metric associated with the new element does not cause the new element to be added to the region of interest, adding the new element into an other of the segments based on the boundaries of the other segment without performing sorting operations.

7. The method of claim 4, further comprising modifying the boundaries of the segments based on a change of a distribution of the garbage collection metrics within the data structure.

8. An apparatus, comprising:

a plurality of garbage collection units each comprising a plurality of flash memory units;

a controller configured to perform a garbage collection operation on the garbage collection units, the controller causing the apparatus to;

form a data structure referencing a garbage collection metric for each of a plurality of associated garbage collection units of a flash memory device, wherein each garbage collection metric is based, wherein each on one or more device state variables of the associated garbage collection unit;

in response to a threshold change in the one or more device state variables, sort a region of interest within the data structure based on the garbage collection metrics; and

select one or more garbage collection units for garbage collection operations from the sorted region of interest.

9. The apparatus of claim 8, wherein the garbage collection units with a high range of garbage collection metric values are selected first for the garbage collection operations, and wherein the region of interest comprises the garbage collection units having the high range of the garbage collection metric values.

10. The apparatus of claim 9, wherein the controller further causes the apparatus to, if the region of interest does not comprise any garbage collection metrics, define an other portion of the data structure as the region of interest and sorting within the other portion.

11. The apparatus of claim 8, wherein the data structure comprises a plurality of segments each comprising one or more of elements that make reference to the garbage collection metrics, wherein boundaries of the segments are determined based on the garbage collection metrics of the elements within the segments, and wherein the region of interest encompasses at least one of the plurality of segments.

12. The apparatus of claim 11, wherein the controller further causes the apparatus to:

determine a new element that is to be added to the data structure; and

if a garbage collection metric associated with the new element causes the new element to be added to the region of interest, insert at least the new element in a sorted order into the region of interest, otherwise add the new element into an other of the segments based on the boundaries of the other segment without performing sorting operations.

13. The apparatus of claim 11, wherein the controller further causes the apparatus to modify the boundaries of the segments based on a change of a distribution of the garbage collection metrics within the data structure.

14. A method comprising:

maintaining a collection of elements that each comprise a garbage collection metric of a respective one of a plurality of garbage collection units, wherein the garbage collection metrics are based on one or more device state variables;

forming a data structure comprising a plurality of second elements that are each associated with one of the elements of the collection, wherein the garbage collection units are selected for a garbage collection operation based on an order of the second elements within the data structure; and

in response to determining a threshold change in the device state variables, sorting only a region of interest within the data structure based on the garbage collection metrics of the second elements in the region of interest.

15. The method of claim 14, further comprising:

determining an event that triggers the garbage collection operation for at least one of the garbage collection units;

if the region of interest does not include any of the second elements, defining an other portion of the data structure as the region of interest and sorting the second elements within the other portion;

removing a selected second element from the region of interest; and

performing the garbage collection operation on a garbage collection unit associated with the selected second element.

16. The method of claim 14, wherein the number of second elements is smaller than the number of the elements of the collection such that one or more of the elements of the collection are not represented in the data structure.

17. The method of claim 14, wherein the data structure comprises a plurality of segments each comprising one or more of the second elements, wherein boundaries of the segments are determined based on the garbage collection metrics of the second elements within the segments, and wherein the region of interest encompasses at least one of the plurality of segments.

18. The method of claim 17, further comprising:

determining, from the collection of elements, a new second element that is to be added to the data structure; and

if a garbage collection metric associated with the new second element causes the new second element to be added to the region of interest, inserting at least the new second element in a sorted order into the region of interest, otherwise adding the new second element into an other of the segments based on the boundaries of the other segment without performing any sorting operations.

19. The method of claim 17, further comprising modifying the boundaries of the segments based on a change of a distribution of the garbage collection metrics within the data structure.

20. An apparatus comprising a plurality of flash memory units and a controller configured to cause the apparatus to perform the method of claim 14, wherein the plurality of garbage collection units each comprise a portion of the plurality of flash memory units.