# US 10,872,037 B2 · Estimating worker nodes needed for performing garbage collection operations > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,872,037 B2 - Document ID: US10872037B2 - Status: Granted - Kind: B2 - Application number: 16/389,763 - Filed: 2019-04-19 - Published: 2020-10-22 - Granted: 2020-12-22 - Earliest claimed: 2019-04-19 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Nicholas A. Noto; Mariah Arevalo; Philip Shilane; Joseph S. Brandt - Web page: https://patentgrep.com/patent/US10872037B2 ## CPC - G06F 9/5022: {Mechanisms to release resources} - G06F 12/0253: {Garbage collection, i.e. reclamation of unreferenced memory} - G06F 9/4843: {by program, e.g. task dispatcher, supervisor, operating system} - G06F 9/505: {considering the load} - G06F 16/1744: {using compression, e.g. sparse files} - G06F 2212/1044: Space efficiency improvement - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) The method of claim 1, further comprising determining the number of workers based on memory allocated to each worker. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) The method of claim 1, further comprising assigning the impacted similarity groups to the determined number of workers. ### Claim 7 (depends on 6) The method of claim 6, further comprising assigning the impacted similarity groups such that the determined number of workers are load balanced. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 1) 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. ### Claim 10 (depends on 9) The method of claim 9, further comprising determining the number of impacted similarity groups based on the listed slices. ### Claim 11 (depends on 1) 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. ### Claim 12 (depends on 1) 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. ### Claim 13 (depends on 1) 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. ### Claim 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. ### Claim 15 (depends on 14) 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. ### Claim 16 (depends on 14) 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. ### Claim 17 (depends on 14) The method of claim 14, further comprising assigning the impacted similarity groups to the determined number of workers. ### Claim 18 (depends on 17) The method of claim 17, further comprising assigning the impacted similarity groups such that the determined number of workers are load balanced. ### Claim 19 (depends on 18) 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. ### Claim 20 (depends on 14) 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.