Container reclamation using probabilistic data structures
Disclosed herein is the creation of probabilistic data structures for container reclamation. One method involves retrieving a segment object list of a data container and creating a probabilistic data structure. The segment object list comprises a plurality of segment objects, the data container comprises the plurality of segment objects and a plurality of data objects, and each segment object of the plurality of segment objects comprises a hash value determined by performing a hashing function on a corresponding data object of the plurality of data objects. The creating includes, for each segment object in the segment object list, identifying an element of a plurality of elements of the probabilistic data structure using a hash value of the each segment object and setting the element to indicate the segment object references a corresponding data object of the plurality of data objects.
1. A computer-implemented method comprising:
retrieving a segment object list of a data container, wherein
the segment object list comprises a plurality of segment objects,
the data container comprises the plurality of segment objects and a plurality of data objects, and
each segment object of the plurality of segment objects comprises a hash value determined by performing a hashing function on a corresponding data object of the plurality of data objects; and
creating a probabilistic data structure, wherein
the creating comprises
for each segment object in the segment object list,
identifying an element of a plurality of elements of the probabilistic data structure using a hash value of the each segment object in the segment object list, and
setting the element of the plurality of elements of the probabilistic data structure to indicate the segment object references a corresponding data object of the plurality of data objects,
such that, upon completion of the creating,
an element value stored in each element of the plurality of elements of the probabilistic data structure indicate that a corresponding segment object of the plurality of segment objects by returning
a true value, if the corresponding segment object should be maintained during a compaction operation on the data container, and
a false value, if the corresponding segment object should not be maintained during the compaction operation on the data container,
a first probability of the false value being returned for a given 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 given segment object that should not be maintained during compaction of the data container is greater than zero.
2. The method of claim 1 , further comprising:
receiving another segment object, wherein
the another segment object is among the plurality of segment objects; and
updating the probabilistic data structure, wherein
the updating comprises
identifying another element of a plurality of elements of the probabilistic data structure using another hash value of the another segment object, and
setting another element value of the another element of the plurality of elements of the probabilistic data structure to indicate the another segment object references a corresponding data object of the plurality of data objects.
3. The method of claim 1 , further comprising:
receiving information identifying another segment object, wherein
the another segment object is among the plurality of segment objects; and
updating the probabilistic data structure, wherein
the updating comprises
identifying another element of a plurality of elements of the probabilistic data structure using another hash value of the another segment object identified by the information, and
clearing another element value of the another element of the plurality of elements of the probabilistic data structure to indicate the another segment object no longer references any data object of the plurality of data objects.
4. The method of claim 1 , wherein
each hash value of the plurality of hash values is a fingerprint of a plurality of fingerprints,
each fingerprint of the plurality of fingerprints are configured to be used to deduplicate a data segment of a plurality of data segments, and
deduplication of the plurality of data segments results in the plurality of data objects.
5. The method of claim 1 , wherein
compaction of the data container comprises
maintaining another segment object during the compaction, if an element value for each of one or more elements in the probabilistic data structure is set, 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 cleared.
6. 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 a portion of the hash value results in a false positive rate associated with the segment object.
7. The method of claim 6 , wherein
the false positive rate indicates that a hit ratio percentage meets or exceeds a deletion efficiency threshold.
8. The method of claim 1 , further comprising:
searching the probabilistic data structure using a mapping structure, wherein the mapping structure is a data change map.
9. The method of claim 1 , wherein
the second probability is a false positive rate that is, at least in part, a function of at least one of
a size of the probabilistic data structure,
a size of the hash value, or
a uniqueness of the hash value.
10. The method of claim 9 , further comprising:
determining the second probability, wherein
the second probability is determined based, at least in part, on a size of the probabilistic data structure, and
the size of the probabilistic data structure is determined based, at least in part, on a hit ratio, with regard to a deletion efficiency threshold.
11. The method of claim 10 , further comprising:
adjusting a hash function count of the probabilistic data structure, such that the hit ratio meets the deletion efficiency threshold.
12. A non-transitory computer-readable storage medium, comprising program instructions, which, when executed by one or more processors of a computing system, perform a method comprising:
retrieving a segment object list of a data container, wherein
the segment object list comprises a plurality of segment objects,
the data container comprises the plurality of segment objects and a plurality of data objects, and
each segment object of the plurality of segment objects comprises a hash value determined by performing a hashing function on a corresponding data object of the plurality of data objects; and
creating a probabilistic data structure, wherein
the creating comprises
for each segment object in the segment object list,
identifying an element of a plurality of elements of the probabilistic data structure using a hash value of the each segment object in the segment object list, and
setting the element of the plurality of elements of the probabilistic data structure to indicate the segment object references a corresponding data object of the plurality of data objects,
such that, upon completion of the creating,
an element value stored in each element of the plurality of elements of the probabilistic data structure indicate that a corresponding segment object of the plurality of segment objects by returning
a true value, if the corresponding segment object should be maintained during a compaction operation on the data container, and
a false value, if the corresponding segment object should not be maintained during the compaction operation on the data container,
a first probability of the false value being returned for a given 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 given segment object that should not be maintained during compaction of the data container is greater than zero.
13. The non-transitory computer-readable storage medium of claim 12 , the method further comprises:
receiving another segment object, wherein
the another segment object is among the plurality of segment objects; and
updating the probabilistic data structure, wherein
the updating comprises
identifying another element of a plurality of elements of the probabilistic data structure using another hash value of the another segment object, and
setting another element value of the another element of the plurality of elements of the probabilistic data structure to indicate the another segment object references a corresponding data object of the plurality of data objects.
14. The non-transitory computer-readable storage medium of claim 12 , the method further comprises:
receiving information identifying another segment object, wherein
the another segment object is among the plurality of segment objects; and
updating the probabilistic data structure, wherein
the updating comprises
identifying another element of a plurality of elements of the probabilistic data structure using another hash value of the another segment object identified by the information, and
clearing another element value of the another element of the plurality of elements of the probabilistic data structure to indicate the another segment object no longer references any data object of the plurality of data objects.
15. The non-transitory computer-readable storage medium of claim 12 , wherein
compaction of the data container comprises
maintaining another segment object during the compaction, if an element value for each of one or more elements in the probabilistic data structure is set, 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 cleared.
16. The non-transitory computer-readable storage medium of claim 12 , the method further comprises:
determining a size of the probabilistic data structure, wherein
the size of the probabilistic data structure is based on determining that a portion of the hash value results in a false positive rate associated with the segment object.
17. The non-transitory computer-readable storage medium of claim 16 , wherein
the false positive rate indicates that a hit ratio percentage meets or exceeds a deletion efficiency threshold.
18. The non-transitory computer-readable storage medium of claim 12 , the method further comprises:
searching the probabilistic data structure using a mapping structure, wherein the mapping structure is a data change map.
19. The non-transitory computer-readable storage medium of claim 12 , wherein
the second probability is a false positive rate that is, at least in part, a function of at least one of
a size of the probabilistic data structure,
a size of the hash value, or
a uniqueness of the hash value.
20. A computer-implemented method comprising:
receiving a segment object, wherein
the segment object is among a plurality of segment objects stored in a data container,
the data container comprises the plurality of segment objects and a plurality of data objects, and
each segment object of the plurality of segment objects comprises a hash value determined by performing a hashing function on a corresponding data object of the plurality of data objects, to which the each segment object corresponds; and
updating a probabilistic data structure, wherein
the updating comprises
identifying an element of a plurality of elements of the probabilistic data structure using a hash value of the segment object, and
setting an element value of the element of the plurality of elements of the probabilistic data structure to indicate the segment object references a corresponding data object of the plurality of data objects,
such that, upon completion of the updating,
an element value stored in each element of the plurality of elements of the probabilistic data structure indicate that a corresponding segment object of the plurality of segment objects by returning
a true value, if the corresponding segment object should be maintained during a compaction operation on the data container, and
a false value, if the corresponding segment object should not be maintained during the compaction operation on the data container,
a first probability of the false value being returned for a given 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 given segment object that should not be maintained during compaction of the data container is greater than zero.