Global occupancy aggregator for global garbage collection scheduling

• US 10,241,716 B2
• Filed: 06/30/2017
• Issued: 03/26/2019
• Est. Priority Date: 06/30/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Mainali, Shane Kumar, Surla, Rushi Srinivas
• Primary Examiner(s): Rojas, Midys
• Application Number:
  US15/640,210
• Publication Number:
  US 20190004731A1
• Time in Patent Office: 634 Days
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• 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 12/0276 Generational garbage collection
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Computer systems and methods for scheduling garbage collection in a distributed environment that includes multiple partitions that reference various data blocks that store data objects. A global occupancy aggregator may access occupancy information for each of the partitions from an occupancy index of each of the partitions. This occupancy information specifies a portion of storage resources occupied by those data blocks referenced by each of the partitions. The global occupancy aggregator may aggregate the accessed occupancy information to generate a global occupancy index that combines the occupancy information of the partitions. The global occupancy aggregator may generate a global schedule for garbage collection for the partitions based on the global occupancy index. The global schedule specifies which of the data blocks included in the global occupancy index are to be subjected to garbage collection.

Claims

1. A computer system comprising:

one or more processors; and

one or more computer-readable storage media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computer system schedule garbage collection in a distributed environment that includes a plurality of partitions that point to a plurality of data blocks that store data objects, the computer-executable instructions including instructions that are executable to cause the computer system to perform at least the following;

accessing occupancy information for each of the plurality of partitions from an occupancy index of each of the plurality of partitions, wherein the occupancy information specifies a portion of storage resources occupied by those of the plurality of data blocks referenced by each of the plurality of partitions;

aggregating the accessed occupancy information to generate a global occupancy index that combines the occupancy information of the plurality of partitions; and

generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index, the global schedule specifying which of the plurality of data blocks included in the global occupancy index are to be subjected to garbage collection.

2. The computer system of claim 1, wherein the computer system is further caused to perform the following:

triggering garbage collectors associated with the plurality of partitions to perform the garbage collection on plurality of data blocks specified by the global schedule for garbage collection.

3. The computer system of claim 2, wherein the triggering of the garbage collectors is staggered such that not all of the garbage collectors begin garbage collecting at the same time.

4. The computer system of claim 1, wherein generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index comprises:

determining an age of each of plurality of data blocks, wherein those of the plurality of data blocks that are older than the other data blocks are included in the global schedule.

5. The computer system of claim 1, wherein generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index comprises:

determining an amount of unused space for each of the plurality of data blocks, wherein those of the plurality of data blocks with a large amount of unused space are included in the global schedule.

6. The computer system of claim 1, wherein generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index comprises:

determining an amount of valid data objects for each of the plurality of data blocks, wherein those of the plurality of data blocks with a large amount of invalid data objects are included in the global schedule.

7. The computer system of claim 1, wherein generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index comprises:

determining a threshold for garbage collection, wherein those of the plurality of data blocks having an amount of valid data below the threshold are included in the global schedule.

8. The computer system of claim 1, wherein generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index comprises:

receiving an indication that one or more of the plurality of data blocks are to be included in the global schedule; and

based on the indication, adding the one or more of the plurality of data blocks to the global schedule.

9. The computer system of claim 1, wherein the plurality of data blocks include one or more of a Binary Large Object (BLOB), a file, a table, or an index.

10. A method for scheduling garbage collection in a distributed environment that includes a plurality of partitions that reference a plurality of data blocks that store data objects, the method comprising:

an act of accessing occupancy information for each of the plurality of partitions from an occupancy index of each of the plurality of partitions, wherein the occupancy information specifies a portion of storage resources occupied by those of the plurality of data blocks referenced by each of the plurality of partitions;

an act of aggregating the accessed occupancy information to generate a global occupancy index that combines the occupancy information of the plurality of partitions; and

an act of generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index, the global schedule specifying which of the plurality of data blocks included in the global occupancy index are to be subjected to garbage collection.

11. The method of claim 10, further comprising:

an act of triggering garbage collectors associated with the plurality of partitions to perform the garbage collection on plurality of data blocks specified by the global schedule for garbage collection.

12. The method of claim 11, wherein the act of triggering comprises performing a cost analysis to determine which of the garbage collectors to trigger.

13. The method of claim 11, wherein the act of triggering the garbage collectors is staggered such that not all of the garbage collectors begin garbage collecting at the same time.

14. The method of claim 10, wherein the act of generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index comprises:

an act of determining an age of each of plurality of data blocks, wherein those of the plurality of data blocks that are older than the other data blocks are included in the global schedule.

15. The method of claim 10, wherein the act of generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index comprises:

an act of determining an amount of unused space for each of the plurality of data blocks, wherein those of the plurality of data blocks with a large amount of unused space are included in the global schedule.

16. The method of claim 10, wherein the act of generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index comprises:

an act of determining an amount of valid data objects for each of the plurality of data blocks, wherein those of the plurality of data blocks with a large amount of invalid data objects are included in the global schedule.

17. The method of claim 10, wherein the act of generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index comprises:

an act of determining a threshold for garbage collection, wherein those of the plurality of data blocks having an amount of valid data below the threshold are included in the global schedule.

19. The method of claim 10, wherein the act of generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index comprises:

an act of receiving an indication that one or more of the plurality of data blocks are to be included in the global schedule; and

based on the indication, an act of adding the one or more of the plurality of data blocks to the global schedule.

18. A computer system comprising:

one or more processors; and

one or more computer-readable storage media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computer system to instantiate in memory;

a global occupancy aggregator component that is configured to schedule garbage collection in a distributed environment that includes a plurality of partitions that point to a plurality of data blocks that store data objects, the global occupancy aggregator configured to perform at least the following;

accessing occupancy information for each of the plurality of partitions from an occupancy index of each of the plurality of partitions, wherein the occupancy information specifies a portion of storage resources occupied by those of the plurality of data blocks referenced by each of the plurality of partitions;

aggregating the accessed occupancy information to generate a global occupancy index that combines the occupancy information of the plurality of partitions; and

generating a global schedule for garbage collection for the plurality of partitions based on the global occupancy index, the global schedule specifying which of the plurality of data blocks included in the global occupancy index are to be subjected to garbage collection.

20. The computer system of claim 18, wherein the computer system is further configured to instantiate in memory:

a trigger component configured to triggering garbage collectors associated with the plurality of partitions to perform the garbage collection on plurality of data blocks specified by the global schedule for garbage collection.