OPTIMIZED PLACEMENT OF DATA CONTAINED IN A GARBAGE COLLECTED STORAGE SYSTEM

• US 20200133511A1
• Filed: 10/29/2018
• Published: 04/30/2020
• Est. Priority Date: 10/29/2018
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: MCGRATH, Michael Sean
• Granted Patent: US 10,802,726 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/068 Hybrid storage device

Abstract

A garbage collection process running on a computing device is configured to track the number of garbage collection cycles that storage fragments, called extents, are persisted in storage without being modified or deleted using a lifetime counter that is implemented using metadata. At each garbage collection cycle, the extents are sorted by lifetime values. Old extents (i.e., those existing at the start of the cycle) are bucketed together by lifetime values during garbage collection into new extents (i.e., those being created during the cycle). Thus, each of the new extents includes data having similar lifetime values. The lifetime value for the new extent equals the lowest lifetime value of the old source extent plus one additional increment on the counter. As extents are organized by garbage collection lifetime, placement on storage media can be optimized according to expected endurance requirements.

Claims

1. A computing device, comprising:

a non-transitory data storage system including at least a first storage medium and a second storage medium, the first storage media having higher endurance relative to the second storage medium;

one or more processors; and

at least one hardware-based non-transitory computer-readable memory device having computer-executable instructions stored thereon which, when executed by the one or more processors, cause the computing device to

track lifetime of data in each extent in the data storage system, in which lifetime is a number of garbage collection cycles for which an extent has been persisted,

initiate a garbage collection cycle,

coalesce extents existing at the initiation of the garbage collection cycle into new extents created during the garbage collection cycle so that each new extent contains data of similar lifetime,

place the new extents on the data storage system according to lifetime, such that new extents having lower lifetime values relative to other new extents are placed on the first storage medium, and the other new extents are placed on the second storage medium.

2. The computing device of claim 1 in which the instructions further cause the computing device to repeat the coalescing and placing for each garbage collection cycle.

3. The computing device of claim 1 in which the lifetime is expressed as an integer count, and the instructions further cause the computing device to assign a lifetime value to each new extent, in which the lifetime value is a lowest value of the existing extents that are coalesced into the new extent plus one count.

4. The computing device of claim 1 in which the data storage system comprises a plurality of storage media that each have different endurance characteristics and the instructions further cause the computing device to place new extents on the storage media based on endurance in which relatively lower lifetime values are associated with relatively higher endurance.

5. The computing device of claim 1 in which the data storage system comprises tiered storage using one or more solid state drives.

6. The computing device of claim 1 in which the data storage system comprises shingled magnetic recording (SMR) media.

7. The computing device of claim 1 in which the data storage system comprises at least one storage media implemented using a NAND-based memory device.

8. A method for placing data in extents on a plurality of storage media with varying endurance during each cycle of a garbage collection process, comprising:

tracking a lifetime of each extent using an integer counter, in which the counter is incremented for each garbage collection cycle that the extent is persisted;

garbage collecting old extents into new extents so that data in each new extent is sourced from old extents having similar lifetime values;

assigning a lifetime value for each new extent, in which the assigned lifetime value is equal to a lowest lifetime value of the old source extents plus one increment on the integer counter; and

placing the new extents on the plurality of storage media so that new extents having higher lifetime values relative to those of other new extents are placed on storage media having lower endurance relative to that of other storage media in the plurality, and new extents having lower lifetime values relative to those of other new extents are placed on storage media having higher endurance relative to that of other storage media in the plurality.

9. The method of claim 8 further comprising sorting the extents by lifetime value.

10. The method of claim 9 in which the sorting comprises organizing the extents by expected endurance requirements.

11. The method of claim 8 further including triggering a garbage collection cycle to meet predetermined free space criteria.

12. The method of claim 8 further including performing wear leveling operations on the plurality of storage media during the garbage collection.

13. The method of claim 8 in which one or more of the plurality of storage media comprises a solid state memory device.

14. The method of claim 13 in which the solid state memory device comprises flash memory elements that are subject to wear.

15. One or more hardware-based non-transitory computer-readable memory devices storing computer-executable instructions which, upon execution by one or more processors in a computing device that includes a data storage system, cause the computing device to

attach metadata to each data fragment that is stored in the data storage system in which the metadata provides a counter to count a number of garbage collection cycles that each data fragment has undergone;

sort the stored data fragments using the counter in each cycle of garbage collection;

distribute the sorted data fragments, in each cycle of garbage collection, into at least two buckets such that data fragments with higher relative counts are in one bucket, and data fragments with lower relative counts are in the other bucket; and

in each cycle of garbage collection, place the bucketed data fragments on different respective storage media, in which the storage media have respective different levels of endurance.

16. The one or more hardware-based non-transitory computer-readable memory devices of claim 15 in which the instructions further cause the computing device to repeat the sorting, distributing, and placing each time the garbage collection is triggered.

17. The one or more hardware-based non-transitory computer-readable memory devices of claim 15 in which the levels of endurance include higher relative endurance and lower relative endurance.

18. The one or more hardware-based non-transitory computer-readable memory devices of claim 15 in which the data storage system comprises solid state storage media and magnetic storage media.

19. The one or more hardware-based non-transitory computer-readable memory devices of claim 15 in which bucketed data fragments having relatively highest churn are placed on storage media having relatively highest endurance.

20. The one or more hardware-based non-transitory computer-readable memory devices of claim 15 in which bucketed data fragments having relatively highest stability are placed on storage media having relatively lowest endurance.