Efficient space reclamation in deduplication systems
A method, computer program product, computer system, and the like that provide for the efficient reclamation of storage space in a deduplication system are disclosed. The method, for example, includes identifying one or more storage constructs of a number of storage constructs and generating an indication that a reclamation operation is to be performed with respect to the one or more storage constructs. In an embodiment, each of the plurality of storage constructs includes metadata and a number of units of data. The one or more storage constructs are identified, at least in part, by determining that a portion of the number of units of data of each of the one or more storage constructs is in a state, wherein the determining is based, at least in part, on at least a portion of the metadata.
1. A method comprising:
deduplicating a first unit of data to an existing de-duplicated storage construct of a plurality of existing de-duplicated storage constructs, wherein each of the plurality of existing de-duplicated storage constructs comprises
metadata,
a plurality of units of data, and
the metadata includes a signature construct uniquely identifying the data contained in each of the plurality of units of data;
after deduplicating the first units of data, designating the existing de-duplicated storage construct for reclamation at least in part, by
determining a portion of the plurality of units of data of the existing de-duplicated storage construct that is in a given state, wherein
the given state is one of in-use or unused, and
the determining is based, at least in part, on at least a portion of the metadata of the existing de-duplicated storage construct, and
comparing an amount of data to a threshold value, wherein
the amount of data represents the portion of the plurality of units of data of the existing de-duplicated storage construct in the given state; and
in response to the comparing, generating an indication that a reclamation operation is to be performed with respect to the existing de-duplicated storage construct, wherein
the reclamation operation comprises re-deduplicating the first unit of data to another de-duplicated storage construct.
2. The method of claim 1 , wherein
each of the plurality of existing de-duplicated storage constructs is a container, each of the units of data is a data segment,
the method further comprises
in response to the indication, deallocating the existing de-duplicated storage construct.
3. The method of claim 2 , wherein
the plurality of existing de-duplicated storage constructs are among a set of storage constructs stored in a storage system,
the plurality of existing de-duplicated storage constructs represent one or more backup images, and
the one or more backup images were created during one or more full backup cycles.
4. The method of claim 3 , wherein
the one or more full backup cycles comprises a plurality of full backup cycles, and
each of the plurality of full backup cycles comprises a full backup and one or more incremental backups.
5. The method of claim 1 , wherein the plurality of existing de-duplicated storage constructs represent one or more backup images, and the identifying further comprises:
identifying the one or more backup images, wherein
the one or more backup images were created during one or more full backup cycles;
retrieving a plurality of tuples associated with the one or more backup images, wherein
each tuple is associated with a data segment of the one or more backup images and is one of a plurality of tuples comprised in metadata of a container in which the data segment is stored, and
the plurality of tuples are retrieved from metadata of one or more containers in which the data segments are stored; and
producing a list of container identifiers, using the plurality of tuples, wherein
each container identifier in the list of container identifiers identifies a container with respect to which a reclamation operation is to be performed.
6. The method of claim 5 , wherein the producing the list of container identifiers comprises:
generating a list of pairs, wherein
each pair in the list of pairs comprises
a container identifier identifying one of a plurality of containers, and
container size information indicating a size of the portion of the one of the plurality of containers; and
generating the list of container identifiers, wherein
the list of container identifiers is generated based, at least in part, on the list of pairs.
7. The method of claim 6 , wherein the generating the list of container identifiers comprises:
comparing the container size information for the one of the plurality of containers to a threshold; and
in response to a result of the comparing that indicates that the one of the plurality of containers should be reclaimed, including the container identifier in the list of container identifiers.
8. The method of claim 6 , further comprising:
sorting the plurality of tuples, wherein
each tuple of the plurality of tuples is a triple, and
each triple comprises
a container identifier,
a fingerprint of the data segment, and
size information, wherein
the size information is a size of the data segment.
9. The method of claim 8 , wherein
the sorting the plurality of tuples sorts the plurality of tuples using
the container identifier of each tuple as a primary key, and
the fingerprint of the data segment as a secondary key, wherein
the size of the data segment is represented by the fingerprint of the data segment.
10. The method of claim 8 , wherein
the plurality of tuples are sorted based, at least in part, on the size information of each of the plurality of tuples.
11. The method of claim 8 , further comprising:
in response to the indication, performing the reclamation operation, wherein
the reclamation operation comprises
removing fingerprints for data segments in the de-duplicated storage construct from a fingerprint cache.
12. The method of claim 8 , further comprising:
in response to the indication, excluding fingerprints for data segments in the de-duplicated storage construct, wherein
the fingerprints are in a set of fingerprints, and
the set of fingerprints are sent to a client as part of a backup operation.
13. The method of claim 1 , further comprising:
in response to the indication, performing the reclamation operation, wherein
the reclamation operation results in one or both of
associated metadata being updated to indicate that the existing de-duplicated storage construct no longer contains in-use data, wherein
the associated metadata is associated with the existing de-duplicated storage construct, and
the associated metadata is at least one of
the metadata of the de-duplicated storage construct, and/or
other metadata, or
the existing de-duplicated storage construct being deleted.
14. The method of claim 1 , wherein the indication indicates that the existing de-duplicated storage construct is to be reclaimed by virtue of:
indicating that a deduplication storage server should perform a reclamation operation, wherein
the reclamation operation comprises deletion of the existing de-duplicated storage construct.
15. A computer program product comprising:
a plurality of instructions, comprising
a first set of instructions, executable on a computer system, configured to designate an existing de-duplicated storage construct of a plurality of existing de-duplicated storage constructs, wherein each of the existing de-duplicated plurality of storage constructs comprises
metadata,
a plurality of units of data, and
the metadata includes a signature construct uniquely identifying the data contained in each of the plurality of units of data, and
the first set of instructions identifies the existing de-duplicated storage construct that is to be reclaimed, at least in part, by
determine a portion of the plurality of units of data of the existing de-duplicated storage construct that is in a given state,
wherein
the given state is one of in-use or unused, and
the determining is based, at least in part, on at least a portion of the metadata of the existing de-duplicated storage construct, and
compare an amount of data to a threshold value, wherein
the amount of data represents the portion of the plurality of units of data of the existing de-duplicated storage construct in the given state, and
a second set of instructions, executable on the computer system, configured to, in response to the comparing, generate an indication that a reclamation operation is to be performed with respect to the existing de-duplication storage construct, wherein
the reclamation operation comprises re-deduplicating data; and
a non-transitory computer-readable storage medium, wherein the first and second sets of instructions are encoded in the non-transitory computer-readable storage medium.
16. The computer program product of claim 15 , wherein the instructions further comprise:
a third set of instructions, executable on the computer system, configured to identify the plurality of existing de-duplicated storage constructs, wherein
the each of the plurality of existing de-duplicated storage constructs is a container,
each of the units of data is a data segment,
the plurality of existing de-duplicated storage constructs are among a set of storage constructs stored in a storage system,
the plurality of existing de-duplicated storage constructs represent one or more backup images, and
the one or more backup images were created during one or more full backup cycles; and
a fourth set of instructions, executable on the computer system, configured to, in response to the indication, deallocate the existing de-duplicated storage construct.
17. The computer program product of claim 16 , wherein the instructions further comprise:
a fifth set of instructions, executable on the computer system, configured to identify the one or more backup images;
a sixth set of instructions, executable on the computer system, configured to retrieve a plurality of tuples associated with the one or more backup images, wherein
each tuple is associated with a data segment of the one or more backup images and is one of a plurality of tuples comprised in the metadata of a container in which the data segment is stored, and
the plurality of tuples are retrieved from metadata of one or more containers in which the data segments are stored; and
a seventh set of instructions, executable on the computer system, configured to sort the plurality of tuples.
18. The computer program product of claim 17 , wherein the instructions further comprise:
a eighth set of instructions, executable on the computer system, configured to generate a list of pairs, wherein
each pair in the list of pairs comprises
a container identifier identifying one of a plurality of containers, and
container size information indicating a size of the portion of the one of the plurality of containers; and
an ninth set of instructions, executable on the computer system, configured to generate a list of container identifiers, wherein
the list of container identifiers is generated based, at least in part, on the list of pairs.
19. The computer program product of claim 15 , wherein the instructions further comprise:
a third set of instructions, executable on the computer system, configured to, in response to the indication, perform the reclamation operation, wherein
the reclamation operation results in one or both of
associated metadata being updated to indicate that the existing de-duplicated storage construct no longer contains in-use data, wherein
the associated metadata is associated with the existing de-duplicated storage construct, and
the associated metadata is at least one of
the metadata of the existing de-duplicated storage construct, and/or
other metadata, or
the existing de-duplicated storage construct being deleted.
20. A computer system comprising:
one or more processors;
a computer-readable storage medium coupled to the one or more processors; and
a plurality of instructions, encoded in the computer-readable storage medium and configured to cause the one or more processors to
designate an existing de-duplicated storage construct of a plurality of existing de-duplicated storage constructs that should be reclaimed, wherein
each of the plurality of existing de-duplicated storage constructs comprises metadata,
a plurality of units of data, and
the metadata includes a signature construct uniquely identifying the data contained in each of the plurality of unites of data, and
the instructions configured to cause the one or more processors to identify the existing de-duplicated storage construct that is to be reclaimed comprise one or more instructions configured to
determine a portion of the plurality of units of data of the existing de-duplicated storage construct that is in a given state, wherein the given state is one of in-use or unused,
the one or more instructions configured to determine use at least a portion of the metadata of the de-duplicated storage construct, and
compare an amount of data to a threshold value, wherein
the amount of data represents the portion of the plurality of units of data of the existing de-duplicated storage construct in the given state, and
in response to an indication that the existing de-duplicated storage construct should be reclaimed, generate an indication that a reclamation operation is to be performed with respect to the existing de-duplicated storage construct, wherein
the reclamation operation reclaims comprises re-deduplicating the units of data of the existing de-duplication storage construct to another de-duplicated storage construct.