Efficiency sets for determination of unique data

1. A method comprising:

applying, by a computing device, a bitmask to a first group of candidate block identifiers corresponding to a first data set in a distributed storage system to result in a first group of masked block identifiers, and further to a second group of candidate block identifiers corresponding to a second data set in the distributed storage system to result in a second group of masked block identifiers;

generating, by the computing device, a first efficiency set comprising one or more block identifiers of the first group of candidate block identifiers based on a comparison of a masked comparison block identifier to each identifier in the first group of masked block identifiers;

generating, by the computing device, a second efficiency set comprising one or more block identifiers of the second group of candidate block identifiers based on a comparison of the masked comparison block identifier to each identifier in the second group of masked block identifiers; and

estimating, by the computing device, an amount of memory used for storing unique data of the second data set based on a comparison of the first efficiency set and the second efficiency set, the amount of memory being based on a number of entries in a set difference resulting from the comparison of the first efficiency set and the second efficiency set.

2. The method of claim 1 , further comprising:

selecting, by the computing device, the bitmask based on a targeted probability of accuracy of the first efficiency set and the second efficiency set.

3. The method of claim 1 , further comprising:

selecting, by the computing device, an amount of bits of each candidate block identifier that the bitmask masks based on at least one of a memory storage target or computation target.

4. The method of claim 1 , further comprising:

adjusting, by the computing device, an amount of bits of each candidate block identifier that the bitmask masks while generating at least one of the first efficiency set or the second efficiency set based on a target fraction of a total number of data blocks referenced by the corresponding first or second efficiency sets.

5. The method of claim 1 , further comprising:

generating, by the computing device, the masked comparison block identifier by applying the bitmask to a randomly generated comparison block identifier.

6. The method of claim 1 , wherein the first data set and the second data set are stored at one volume.

7. The method of claim 1 , wherein one or more subsets of the first data set and one or more subsets of the second data set are stored at one or more volumes.

8. The method of claim 1 , further comprising:

removing, by the computing device, the unique data from the distributed storage system in response to a request to remove the second data set, wherein a difference between the second data set and the unique data remains used in the distributed storage system after completing the request to remove the second data set.

9. A computing device comprising:

a memory containing a machine-readable medium comprising machine executable code having stored thereon instructions for estimating an amount of memory used for storing unique data in a distributed storage system; and

a processor coupled to the memory, the processor configured to execute the machine executable code to:

apply a bitmask to a first group of candidate block identifiers corresponding to a first data set in a distributed storage system to result in a first group of masked block identifiers, and further to a second group of candidate block identifiers corresponding to a second data set in the distributed storage system to result in a second group of masked block identifiers;

generate a first efficiency set comprising each block identifier of the first group of candidate block identifiers corresponding to each respective masked block identifier of the first group of masked block identifiers that matches a masked comparison block identifier;

generate a second efficiency set comprising each block identifier of the second group of candidate block identifiers which corresponds to each respective masked block identifier of the second group of masked block identifiers that matches a masked comparison block identifier; and

estimate an amount of memory used for storing unique data referenced by the second data set based on a comparison of the first efficiency set and the second efficiency set, the amount of memory being based on a number of entries in a set difference resulting from the comparison of the first efficiency set and the second efficiency set.

10. The computing device of claim 9 , further comprising:

selecting, by the computing device, the bitmask based on a targeted probability of accuracy of the first efficiency set and the second efficiency set; and

selecting, by the computing device, an amount of bits that the bitmask masks based on at least one of a memory storage target or computation target.

11. The computing device of claim 9 , further comprising:

adjusting, by the computing device, an amount of bits that the bitmask masks while generating at least one of the first efficiency set or the second efficiency set based on a target fraction of a total number of data blocks referenced by the corresponding first or second efficiency sets.

12. The computing device of claim 9 , wherein the masked comparison block identifier is generated by the computing device by applying the bitmask to a randomly generated comparison block identifier.

13. The computing device of claim 9 , wherein the processor is configured, for the comparison of the first efficiency set and the second efficiency set, to execute the machine executable code to:

generate a union of the first efficiency set and the second efficiency to create a combined efficiency set; and

identify block identifiers included in the second efficiency set but not included in the combined efficiency set.

14. The computing device of claim 9 , wherein the processor is configured to execute the machine executable code to:

remove the unique data from the distributed storage system in response to a request to remove the second data set, wherein a difference between the second data set and the unique data remains used in the distributed storage system after completing the request to remove the second data set.

15. A non-transitory machine-readable medium having stored thereon instructions for estimating an amount of memory used for storing unique data in a distributed storage system, comprising machine executable code which when executed by at least one machine, causes the machine to:

apply a bitmask to a first group of candidate block identifiers corresponding to a first data set in the distributed storage system to result in a first group of masked block identifiers, and further to a second group of candidate block identifiers corresponding to a second data set in the distributed storage system to result in a second group of masked block identifiers, wherein the second group of candidate block identifiers is a subset of the first group of candidate block identifiers;

generate a first efficiency set comprising one or more block identifiers of the first group of candidate block identifiers based on a comparison of a masked comparison block identifier to each identifier in the first group of masked block identifiers;

generate a second efficiency set comprising one or more block identifiers of the second group of candidate block identifiers based on a comparison of the masked comparison block identifier to each identifier in the second group of masked block identifiers; and

estimate an amount of memory used for storing unique data of the second data set based on a set difference of the first efficiency set and the second efficiency set, the amount of memory being based on a number of entries in the set difference resulting from the comparison of the first efficiency set and the second efficiency set.

16. The non-transitory machine-readable medium of claim 15 , further comprising code which causes the machine to:

select the bitmask based on a targeted probability of accuracy of the first efficiency set and the second efficiency set; and

select an amount of bits that the bitmask masks based on at least one of a memory storage target or computation target.

17. The non-transitory machine-readable medium of claim 15 , further comprising code which causes the machine to:

adjust an amount of bits that the bitmask masks while generating at least one of the first efficiency set or the second efficiency set based on a target fraction of a total number of data blocks referenced by the corresponding first or second efficiency sets.

18. The non-transitory machine-readable medium of claim 15 , wherein one or more subsets of the first data set and one or more subsets of the second data set are stored at one or more volumes.

19. The non-transitory machine-readable medium of claim 15 , wherein the first efficiency set comprises a union of an efficiency set for each volume of a plurality of volumes in the distributed storage system.

20. The non-transitory machine-readable medium of claim 15 , further comprising code which causes the machine to:

remove the unique data from the distributed storage system in response to a request to remove the second data set, wherein a difference between the second data set and the unique data remains used in the distributed storage system after completing the request to remove the second data set.