Granted Patent B2

US 12,045,203 · App. 17/304,106 · Granted Jul 23, 2024

Inventors: Hemant P. Khachane (Sunnyvale, CA); Paul J. Hammer (Livermore, CA)

Assignee: EMC IP HOLDING COMPANY LLC

G06F16/1748G06F16/1727

Abstract

Claims (82)

1. A computer-implemented method of determining physical capacity of logical space units in a deduplicated file system, the method comprising:

populating a first smart filter to track a physical capacity of a first logical space unit;

adding a plurality of fingerprints from the first logical space unit to one or more registers of the first smart filter;

populating a second smart filter to track fingerprints to be deleted by garbage collection;

adding the to be deleted fingerprints to one or more registers of the second smart filter;

using the first smart filter and the second smart filter to calculate a number of segments in the first logical space unit that are freed by the garbage collection by determining an intersection cardinality of the first logical space unit and the to be deleted fingerprints;

determining a cardinality of unique fingerprints in the first logical space unit based at least on the intersection cardinality of the first logical space unit and the to be deleted fingerprints; and

determining the physical capacity of the first logical space unit based at least on the cardinality of unique fingerprints in the first logical space unit.

2. The method of claim 1 , wherein

the method further comprises: using the first smart filter the determine a cardinality of the first logical space unit; and

determining the cardinality of unique fingerprints in the first logical space unit comprises determining the cardinality of unique fingerprints in the first logical space unit based on (i) the intersection cardinality of the first logical space unit and the to be deleted fingerprints and (ii) the cardinality of the first logical space unit.

3. The method of claim 2 , wherein

the method further comprises: determining an L0 average segment size of the first logical space unit; and

determining the physical capacity of the first logical space unit comprises determining the physical capacity of the first logical space unit based on (i) the cardinality of unique fingerprints in the first logical space unit and (ii) the L0 average segment size of the first logical space unit.

4. The method of claim 1 , wherein determining the intersection cardinality of the first logical space unit and the to be deleted fingerprints comprises:

using the first smart filter to determine a cardinality of the first logical space unit,

using the second smart filter to determine a cardinality of the to be deleted fingerprints,

using the first smart filter to determine a cardinality of a union of the first logical space unit and the to be deleted fingerprints, and

determining the intersection cardinality of the first logical space unit and the to be deleted fingerprints based on (i) the cardinality of the first logical space unit, (ii) the cardinality of the to be deleted fingerprints, and (iii) the cardinality of the union of the first logical space unit and the to be deleted fingerprints.

5. The method of claim 1 , further comprising:

populating a third smart filter to track a physical capacity of a second logical space unit;

adding a plurality of fingerprints from the second logical space unit to one or more registers of the third smart filter;

using the first smart filter and the third smart filter to determine an intersection cardinality of the first logical space unit and the second logical space unit;

determining a cardinality of unique fingerprints in the second logical space unit based at least on the intersection cardinality of the first logical space unit and the second logical space unit; and

determining the physical capacity of the second logical space unit based at least on the cardinality of unique fingerprints in the second logical space unit.

6. The method of claim 5 , wherein

the method further comprises: using the third smart filter the determine a cardinality of the second logical space unit, and using the second smart filter to determine a cardinality of the to be deleted fingerprints;

determining the cardinality of unique fingerprints in the second logical space unit comprises determining the cardinality of unique fingerprints in the second logical space unit based on (i) the intersection cardinality of the first logical space unit and the second logical space unit, (ii) the cardinality of second first logical space unit, and (iii) the cardinality of the to be deleted fingerprints.

7. The method of claim 6 , wherein

the method further comprises: determining an L0 average segment size of the second logical space unit; and

determining the physical capacity of the second logical space unit comprises determining the physical capacity of the second logical space unit based on (i) the cardinality of unique fingerprints in the second logical space unit and (ii) the L0 average segment size of the second logical space unit.

8. The method of claim 1 , wherein the first logical space unit is an Mtree.

9. The method of claim 5 , wherein the first, second and third smart filters are implemented using HyperLogLog (HLL) or HLL++.

10. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations, the operations comprising:

populating a first smart filter to track a physical capacity of a first logical space unit;

adding a plurality of fingerprints from the first logical space unit to one or more registers of the first smart filter;

populating a second smart filter to track fingerprints to be deleted by garbage collection;

adding the to be deleted fingerprints to one or more registers of the second smart filter;

using the first smart filter and the second smart filter to calculate a number of segments in the first logical space unit that are freed by the garbage collection by determining an intersection cardinality of the first logical space unit and the to be deleted fingerprints;

determining a cardinality of unique fingerprints in the first logical space unit based at least on the intersection cardinality of the first logical space unit and the to be deleted fingerprints; and

determining the physical capacity of the first logical space unit based at least on the cardinality of unique fingerprints in the first logical space unit.

11. The non-transitory machine-readable medium of claim 10 , wherein

the operations further comprise: using the first smart filter the determine a cardinality of the first logical space unit; and

determining the cardinality of unique fingerprints in the first logical space unit comprises determining the cardinality of unique fingerprints in the first logical space unit based on (i) the intersection cardinality of the first logical space unit and the to be deleted fingerprints and (ii) the cardinality of the first logical space unit.

12. The non-transitory machine-readable medium of claim 11 , wherein

the operations further comprise: determining an L0 average segment size of the first logical space unit; and

determining the physical capacity of the first logical space unit comprises determining the physical capacity of the first logical space unit based on (i) the cardinality of unique fingerprints in the first logical space unit and (ii) the L0 average segment size of the first logical space unit.

13. The non-transitory machine-readable medium of claim 10 , wherein determining the intersection cardinality of the first logical space unit and the to be deleted fingerprints comprises:

using the first smart filter to determine a cardinality of the first logical space unit,

using the second smart filter to determine a cardinality of the to be deleted fingerprints,

using the first smart filter to determine a cardinality of a union of the first logical space unit and the to be deleted fingerprints, and

determining the intersection cardinality of the first logical space unit and the to be deleted fingerprints based on (i) the cardinality of the first logical space unit, (ii) the cardinality of the to be deleted fingerprints, and (iii) the cardinality of the union of the first logical space unit and the to be deleted fingerprints.

14. The non-transitory machine-readable medium of claim 10 , wherein the operations further comprise:

populating a third smart filter to track a physical capacity of a second logical space unit;

adding a plurality of fingerprints from the second logical space unit to one or more registers of the third smart filter;

using the first smart filter and the third smart filter to determine an intersection cardinality of the first logical space unit and the second logical space unit;

determining a cardinality of unique fingerprints in the second logical space unit based at least on the intersection cardinality of the first logical space unit and the second logical space unit; and

determining the physical capacity of the second logical space unit based at least on the cardinality of unique fingerprints in the second logical space unit.

15. The non-transitory machine-readable medium of claim 14 , wherein

the operations further comprise: using the third smart filter the determine a cardinality of the second logical space unit, and using the second smart filter to determine a cardinality of the to be deleted fingerprints;

determining the cardinality of unique fingerprints in the second logical space unit comprises determining the cardinality of unique fingerprints in the second logical space unit based on (i) the intersection cardinality of the first logical space unit and the second logical space unit, (ii) the cardinality of second first logical space unit, and (iii) the cardinality of the to be deleted fingerprints.

16. The non-transitory machine-readable medium of claim 15 , wherein

the operations further comprise: determining an L0 average segment size of the second logical space unit; and

determining the physical capacity of the second logical space unit comprises determining the physical capacity of the second logical space unit based on (i) the cardinality of unique fingerprints in the second logical space unit and (ii) the L0 average segment size of the second logical space unit.

17. The non-transitory machine-readable medium of claim 10 , wherein the first logical space unit is an Mtree.

18. The non-transitory machine-readable medium of claim 14 , wherein the first, second and third smart filters are implemented using HyperLogLog (HLL) or HLL++.

19. A data processing system, comprising:

a processor; and

a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform operations, the operations including:

populating a first smart filter to track a physical capacity of a first logical space unit;

adding a plurality of fingerprints from the first logical space unit to one or more registers of the first smart filter;

populating a second smart filter to track fingerprints to be deleted by garbage collection;

adding the to be deleted fingerprints to one or more registers of the second smart filter;

using the first smart filter and the second smart filter to calculate a number of segments in the first logical space unit that are freed by the garbage collection by determining an intersection cardinality of the first logical space unit and the to be deleted fingerprints;

determining a cardinality of unique fingerprints in the first logical space unit based at least on the intersection cardinality of the first logical space unit and the to be deleted fingerprints; and

determining the physical capacity of the first logical space unit based at least on the cardinality of unique fingerprints in the first logical space unit.

20. The data processing system of claim 19 , wherein the operations further include:

populating a third smart filter to track a physical capacity of a second logical space unit;

adding a plurality of fingerprints from the second logical space unit to one or more registers of the third smart filter;

using the first smart filter and the third smart filter to determine an intersection cardinality of the first logical space unit and the second logical space unit;

determining a cardinality of unique fingerprints in the second logical space unit based at least on the intersection cardinality of the first logical space unit and the second logical space unit; and

determining the physical capacity of the second logical space unit based at least on the cardinality of unique fingerprints in the second logical space unit.

Assignments (8)

Continuity (1)