Estimating worker nodes needed for performing garbage collection operations

Patent metadata

Field	Value
Publication number	US-10872037-B2
Application number	US-201916389763-A
Country	US
Kind code	B2
Filing date	Apr 19, 2019
Priority date	Apr 19, 2019
Publication date	Dec 22, 2020
Grant date	Dec 22, 2020

Abstract

Systems and methods for estimating the number of workers needed to perform a garbage collection operation are disclosed. Similarity groups are used to identify segments associated with objects in a computing system. Using deletion records that identify objects to be deleted, the similarity groups impacted by the deletion records can be identified. The number of workers can be determined based on the impacted similarity groups. More specifically, the number of impacted similarity groups and/or workers can be evaluated in terms of memory requirements, input/output constraints and/or time requirements to estimate the number or workers needed to clean similarity groups impacted by a garbage collection operation.

First claim

What is claimed is:

1. A method estimating a number of workers to perform a garbage collection operation, the method comprising:
determining a number of similarity groups impacted by the garbage collection operation, wherein each impacted similarity group is associated with a deleted object; and
determining a number of workers to clean the impacted similarity groups based on the number of similarity groups impacted by the garbage collection.

2. The method of claim 1 , further comprising determining the number of workers based on at least one of a predetermined size of each of the similarity groups or an actual size of each of the impacted similarity groups.

3. The method of claim 1 , further comprising determining the number of workers based on an estimated number of TOPS for cleaning the impacted similarity groups and TOPS capabilities of each worker.

4. The method of claim 1 , further comprising determining the number of workers based on memory allocated to each worker.

5. The method of claim 1 , further comprising determining how many impacted similarity groups a worker can clean and dividing the number of impacted similarity groups by the number of similarity groups a worker can clean.

6. The method of claim 1 , further comprising assigning the impacted similarity groups to the determined number of workers.

7. The method of claim 6 , further comprising assigning the impacted similarity groups such that the determined number of workers are load balanced.

8. The method of claim 7 , further comprising ordering the impacted similarity groups by ID and assigning a range of IDs to each of the determined number of workers.

9. The method of claim 1 , further comprising evaluating deletion records associated with deleted objects and listing slices associated with the deleted objects based on the deletion records.

10. The method of claim 9 , further comprising determining the number of impacted similarity groups based on the listed slices.

11. The method of claim 1 , wherein the determined number of workers accounts for one or more of memory of each worker, TOPS of each worker, or a time constraint on the garbage collection operation.

12. The method of claim 1 , further comprising releasing the workers, which were obtained from computing resources, back to the computing resources when the impacted similarity groups are cleaned.

13. The method of claim 1 , further comprising:
determining a first number of workers based on memory constraints;
determining a second number of workers based on TOPS constraints, wherein the number of workers determined is the greater of the first number of workers and the second number of workers.

14. A non-transitory computer readable medium comprising computer executable instructions that, when executed, perform a method estimating a number of workers to perform a garbage collection operation, the method comprising:
evaluating deletion records associated with deleted objects;
listing slices associated with the deleted objects;
determining a number of similarity groups impacted by the garbage collection operation from the listed slices, wherein each impacted similarity group is associated with at least one deleted object; and
determining a number of workers to clean the impacted similarity groups based on the number of similarity groups impacted by the garbage collection.

15. The method of claim 14 , further comprising determining the number of workers based on at least one of a predetermined size of each of the similarity groups or an actual size of each of the impacted similarity groups, an estimated number of TOPS for cleaning the impacted similarity groups, TOPS capabilities of each worker, and/or memory allocated to each worker.

16. The method of claim 14 , further comprising determining how many impacted similarity groups a worker can clean and dividing the number of impacted similarity groups by the number of similarity groups a worker can clean.

17. The method of claim 14 , further comprising assigning the impacted similarity groups to the determined number of workers.

18. The method of claim 17 , further comprising assigning the impacted similarity groups such that the determined number of workers are load balanced.

19. The method of claim 18 , further comprising ordering the impacted similarity groups by ID and assigning a range of IDs to each of the determined number of workers.

20. The method of claim 14 , further comprising releasing the workers, which were obtained from computing resources, back to the computing resources when the impacted similarity groups are cleaned.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Noto Nicholas A
• Arevalo Mariah
• Shilane Philip
• Brandt Joseph S

Classifications

• G06F12/0253 Primary

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F16/1744

  using compression, e.g. sparse files · CPC title

• G06F9/4843

  by program, e.g. task dispatcher, supervisor, operating system · CPC title

• G06F9/505

  considering the load · CPC title