# US 2021/0342264 A1 · Scalable garbage collection for deduplicated storage

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0342264 A1
- Document ID: US20210342264A1
- Status: Published application
- Kind: A1
- Application number: 17/378,690
- Filed: 2021-07-17
- Published: 2021-11-04
- Earliest claimed: 2019-02-01
- Assignees: EMC IP Holding Company LLC
- Applicants: Emc IP Holding Company LLC
- Inventors: Philip Shilane; Kimberly Lu; Joseph Brandt; Nicholas Noto; Tipper Truong; Mariah Arevalo
- Web page: https://patentgrep.com/patent/US20210342264A1

## CPC

- G06F 3/0608: {Saving storage space on storage systems}
- G06F 12/0253: {Garbage collection, i.e. reclamation of unreferenced memory}
- G06F 3/0641: {De-duplication techniques}
- G06F 3/0652: {Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 2212/1044: Space efficiency improvement
- G06F 2212/1048: Scalability
- G06F 2212/154: Networked environment
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems and methods for cleaning a storage system. A deduplicated storage system is cleaned by identifying structures that include dead or unreferenced segments. This includes processing recipes to identify the segments that are no longer part of a live object recipe. Then, the dead segments are removed. This is accomplished by copying forward the live segments and then deleting, as a whole, the structure that included the dead segments.

## Claims

### Claim 1

A method for cleaning deleted objects from a storage system, the method comprising:
creating a plurality of workers to perform a garbage collection operation that cleans the deleted objects stored in the storage system from objects stored in the storage system;
identifying impacted similarity groups that are impacted by the garbage collection operation, wherein the impacted similarity groups include segments associated with the deleted objects and segments associated with live objects;
identifying live segments in the impacted similarity groups associated with the live objects;
removing the segments associated with the deleted objects;
updating the impacted similarity groups to reflect the segments associated with the deleted objects have been removed.

### Claim 2 (depends on 1)

The method of claim 1, further comprising initiating a controller to control the garbage collection operation, wherein the controller controls the plurality of workers.

### Claim 3 (depends on 1)

The method of claim 1, wherein removing the segments associated with the deleted objects includes copying the segments associated with the live objects to a new structure such that the new structure does not store the segments that are no longer referenced by live objects.

### Claim 4 (depends on 3)

The method of claim 3, further comprising deleting a structure storing the segments associated with deleted objects and the segments associated with the live objects after the new structure is completed.

### Claim 5 (depends on 1)

The method of claim 1, further comprising estimating, by the controller, a number of workers needed to perform the garbage collection operation.

### Claim 6 (depends on 1)

The method of claim 1, further estimating the number of workers by accounting for one or more factors that include an environment variable setting the number of workers, a memory allocation of each worker, a number and/or size of similarity groups impacted by the garbage collection process, Input/Output operations, or throughput.

### Claim 7 (depends on 1)

The method of claim 1, wherein an object recipe includes slice recipes and each slice recipe is associated with a similarity group, further comprising assigning a range of similarity groups to each of the plurality of workers.

### Claim 8 (depends on 1)

The method of claim 1, further comprising identifying the impacted similarity groups and subgroups.

### Claim 9 (depends on 8)

The method of claim 8, further comprising retrieving records corresponding to the deleted objects, wherein the records identify at least object recipes for the impacted similarity groups and subgroups and wherein the impacted similarity groups are identified from slice recipes associated with the object recipes.

### Claim 10 (depends on 8)

The method of claim 8, further comprising recording sizes of the impacted similarity groups.

### Claim 11 (depends on 1)

The method of claim 1, further comprising write locking at least impacted subgroups of the impacted similarity groups in order to support normal operation and the garbage collection operation concurrently.

### Claim 12 (depends on 1)

A non-transitory computer readable medium comprising computer executable instructions that, when executed, perform the method of claim 1.

### Claim 13

A method for cleaning deleted objects from a deduplicated storage system, wherein the deduplicated storage system stores objects using an object recipe that references slice recipes, wherein the slice recipes reference similarity groups and wherein the similarity groups reference compression regions, wherein segments of objects in the storage system are stored in the compression regions, the method comprising:
performing a startup phase of a garbage collection operation in order to instantiate a controller, wherein the garbage collection operation cleans unreferenced segments from the storage system;
estimating a number of workers, by the controller, needed to perform the garbage collection operation based on a number of impacted similarity groups and worker capacity;
determining impacted similarity groups in the storage system that are associated with the unreferenced segments, wherein the impacted similarity groups are associated with the unreferenced segments and live segments;
marking the live segments in the impacted similarity groups;
removing the unreferenced segments; and
updating the impacted similarity groups to reflect the unreferenced segments associated with the deleted objects have been removed.

### Claim 14 (depends on 13)

The method of claim 13, further comprising removing the unreferenced segments by copying forward the live segments from an existing compression region to a new compression region, wherein the unreferenced segments in the existing compression region are not copied into the new compression region.

### Claim 15 (depends on 13)

The method of claim 13, further comprising determining the impacted similarity groups based on deletion records.

### Claim 16 (depends on 15)

The method of claim 15, wherein the deletion records are stored in a deletion bucket of the storage system and wherein the deletion records include at least an object recipe.

### Claim 17 (depends on 16)

The method of claim 16, further comprising determining the impacted similarity groups based on slice recipes included in or referenced by the object recipe.

### Claim 18 (depends on 13)

The method of claim 13, further comprising partitioning the impacted similarity groups to the workers, wherein each worker receives a range of the impacted similarity groups based at least in part on anticipated sizes and identifiers of the impacted similarity groups.

### Claim 19 (depends on 13)

The method of claim 13, further comprising write locking the impacted similarity groups such that the garbage collection operation and normal operations can occur concurrently.

### Claim 20 (depends on 13)

A non-transitory computer readable medium including computer executable instructions for performing the method of claim 13.
