Container reclamation using probabilistic data structures

1. A method comprising:

receiving a hash value, wherein

the hash value is a result of performing a hash function on data of a segment object, and

the segment object is stored in a data container;

identifying one or more elements in a probabilistic data structure, wherein

the identifying is performed using at least a portion of the hash value;

determining an element value for each of the one or more elements;

determining whether one or more element values indicate that the segment object should be maintained during compaction of the data container, wherein

the one or more element values indicate that the segment object should be maintained during compaction of the data container by returning a true value,

the one or more element values indicate that the segment object should not be maintained during compaction of the data container by returning a false value,

a first probability of the false value being returned for the segment object that should be maintained during compaction of the data container is zero, and

a second probability of the true value being returned for the segment object that should be maintained during compaction of the data container is, at least in part, a function of a size of the probabilistic data structure, a size of the hash value, and a uniqueness of the hash value; and

in response to a determination that the one of more element values indicate that the segment object should be maintained during compaction of the data container;

maintaining the segment object during compaction of the data container.

2. The method of claim 1 , wherein

the compaction of the data container comprises

maintaining another segment object during the compacting if the element value for each of the one or more elements in the probabilistic data structure is one, and

permitting compaction of the another segment object during the compacting if the element value for at least one element of the one or more elements is zero.

3. The method of claim 1 , further comprising:

determining a size of the probabilistic data structure, wherein

the size of the probabilistic data structure is based on determining that the portion of the hash value results in a false positive rate associated with the segment object, and

the false positive rate indicates that a hit ratio percentage meets or exceeds a deletion efficiency threshold.

4. The method of claim 3 , further comprising:

creating the probabilistic data structure prior to compaction of the data container, wherein

the creating the probabilistic data structure comprises

accessing the portion of the hash value, and

setting one or more bit values that the portion of the hash value indicates in the probabilistic data structure.

5. The method of claim 4 , further comprising:

determining a false positive rate associated with the probabilistic data structure, wherein

the false positive rate is a function of the size of the probabilistic data structure, a hash function count, and a fingerprint size; and

determining a false negative rate associated with the probabilistic data structure, wherein

the hit ratio percentage meets or exceeds the deletion efficiency threshold if the false negative rate is zero.

6. The method of claim 1 , wherein

the segment object is comprised in a data object, and

the probabilistic data structure is associated with the data object.

7. The method of claim 1 , wherein

the probabilistic data structure is a Bloom filter bitmap.

8. A non-transitory computer readable storage medium comprising program instructions executable to:

receive a hash value, wherein

the hash value is a result of performing a hash function on data of a segment object, and

the segment object is stored in a data container;

identify one or more elements in a probabilistic data structure, wherein the program instructions executable to identify use at least a portion of the hash value;

determining an element value for each of the one or more elements;

determining whether one or more element values indicate that the segment object should be maintained during compaction of the data container, wherein

the one or more element values indicate that the segment object should be maintained during compaction of the data container by returning a true value,

the one or more element values indicate that the segment object should not be maintained during compaction of the data container by returning a false value,

a first probability of the false value being returned for the segment object that should be maintained during compaction of the data container is zero, and

a second probability of the true value being returned for the segment object that should be maintained during compaction of the data container is, at least in part, a function of a size of the probabilistic data structure, a size of the hash value, and a uniqueness of the hash value; and

in response to a determination that the one of more element values indicate that the segment object should be maintained during compaction of the data container; and

in response to a determination that the one of more element values indicate that the segment object should be maintained,

maintain the segment object during compaction of the data container.

9. The non-transitory computer readable storage medium of claim 8 , wherein the compaction of the data container comprises

maintaining another segment object during the compacting if the element value for each of the one or more elements in the probabilistic data structure is one, and

permitting compaction of the another segment object during the compacting if the element value for at least one element of the one or more elements is zero.

10. The non-transitory computer readable storage medium of claim 8 , further comprising:

determining a size of the probabilistic data structure, wherein

the size of the probabilistic data structure is based on determining that the portion of the hash value results in a false positive rate associated with the segment object, and

the false positive rate indicates that a hit ratio percentage meets or exceeds a deletion efficiency threshold.

11. The non-transitory computer readable storage medium of claim 10 , further comprising:

creating the probabilistic data structure prior to compaction of the data container, wherein

the creating the probabilistic data structure comprises

accessing the portion of the hash value, and

setting one or more bit values that the portion of the hash value indicates in the probabilistic data structure.

12. The non-transitory computer readable storage medium of claim 11 , further comprising:

determining a false positive rate associated with the probabilistic data structure, wherein

the false positive rate is a function of the size of the probabilistic data structure, a hash function count, and a fingerprint size; and

determining a false negative rate associated with the probabilistic data structure, wherein

the hit ratio percentage meets or exceeds the deletion efficiency threshold if the false negative rate is zero.

13. The non-transitory computer readable storage medium of claim 8 , wherein

the segment object is comprised in a data object, and

the probabilistic data structure is associated with the data object.

14. The non-transitory computer readable storage medium of claim 8 , wherein

the probabilistic data structure is a Bloom filter bitmap.

15. A system comprising:

one or more processors; and

a memory coupled to the one or more processors, wherein the memory stores program instructions executable by the one or more processors to

receive a hash value, wherein

the hash value a result of performing a hash function on data of a segment object, and

the segment object is stored in a data container,

identify one or more elements in a probabilistic data structure, wherein

the program instructions executable by the one or more processors to identify use at least a portion of the hash value;

determining an element value for each of the one or more elements,

determining whether one or more element values indicate that the segment object should be maintained during compaction of the data container, wherein

the one or more element values indicate that the segment object should be maintained during compaction of the data container by returning a true value,

the one or more element values indicate that the segment object should not be maintained during compaction of the data container by returning a false value,

a first probability of the false value being returned for the segment object that should be maintained during compaction of the data container is zero, and

a second probability of the true value being returned for the segment object that should be maintained during compaction of the data container is, at least in part, a function of a size of the probabilistic data structure, a size of the hash value, and a uniqueness of the hash value, and

in response to a determination that the one of more element values indicate that the segment object should be maintained during compaction of the data container,

maintain the segment object during compaction of the data container.

16. The system of claim 15 , wherein

the compaction of the data container comprises

maintaining another segment object during the compacting if the element value for each of the one or more elements in the probabilistic data structure is one, and

permitting compaction of the another segment object during the compacting if the element value for at least one element of the one or more elements is zero.

17. The system of claim 15 , further comprising:

determining a size of the probabilistic data structure, wherein

the size of the probabilistic data structure is based on determining that the portion of the hash value results in a false positive rate associated with the segment object, and

the false positive rate indicates that a hit ratio percentage meets or exceeds a deletion efficiency threshold.

18. The system of claim 17 , further comprising:

creating the probabilistic data structure prior to compaction of the data container, wherein

the creating the probabilistic data structure comprises

accessing the portion of the hash value, and

setting one or more bit values that the portion of the hash value indicates in the probabilistic data structure.

19. The system of claim 18 , further comprising:

determining a false positive rate associated with the probabilistic data structure, wherein

the false positive rate is a function of the size of the probabilistic data structure, a hash function count, and a fingerprint size; and

determining a false negative rate associated with the probabilistic data structure, wherein

the hit ratio percentage meets or exceeds the deletion efficiency threshold if the false negative rate is zero.

20. The system of claim 15 , wherein

the segment object is comprised in a data object,

the probabilistic data structure is associated with the data object, and

the probabilistic data structure is a Bloom filter bitmap.