Garbage collection assisted deduplication in a log structured file system

1. A computer-implemented method of performing deduplicated backups in a computer network comprising:

performing a garbage collection process of a file system to map each data segment fingerprint to a unique bit position in a perfect hash vector (PHV), wherein each bit represents whether or not a segment is live or dead based on its binary value of 0 or 1 liveness, wherein liveness comprises a referencing of the segment by any current content of the file system;

converting the fingerprint-based PHV to a region-based vector using region identifiers for each region of a plurality of regions, and container identifiers of the segments as keys;

defining two bits per segment in the region-based vector, wherein a first bit is set to the a binary live/dead live or dead value, and a second bit indicates whether or not an ingest writes a duplicate of the segment indicating a deduplication decision of the segment;

grouping ingested data into one or more regions of the plurality of regions based on the container identifier and region identifier;

first calculating a liveness of each region to classify a corresponding region as live versus dead by determining that a percentage of live segments in the corresponding region is greater than a defined liveness threshold;

allowing a programmed deduplication operation to be performed to prevent duplicate data segments being stored, and setting the first bit to the live state binary value;

second calculating a number of deduplicated segments of each region to determine that a number of segments in the corresponding region subject to the deduplication operation is less than a defined deduplication threshold; and

overriding the allowing step to prevent the deduplication operation being performed to thereby allow duplicate data segments to be stored, and setting the second bit to a no deduplication state.

2. The method of claim 1 wherein the first calculating step comprises:

tallying a number of live segments and a number of dead segments in the corresponding region based on the fingerprint marking;

subtracting the number of dead segments from the number of live segments to obtain a difference that determines the percentage of live segments;

defining the corresponding region as dead if the difference is less than the defined liveness threshold; and

defining the corresponding region as sufficiently live if the difference is greater than or equal to the defined liveness threshold.

3. The method of claim 1 further comprising maintaining the PHV between the garbage collection process and a subsequent garbage collection process to represent region liveness of the computer network.

4. The method of claim 3 wherein the computer network comprises at least part of a deduplication backup system including a data storage server running a Data Domain file system (DDFS).

5. The method of claim 4 wherein the file system implements a log structured file system in which data and metadata are written sequentially to a log that is implemented as a circular buffer.

6. A computer program product, comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein, the computer-readable program code adapted to be executed by one or more processors to implement a garbage collection assisted deduplication backup process in a computer network by which, when executed by a processor, cause the processor to perform a method to implement a garbage collection assisted deduplication backup process in a computer network, comprising:

dividing data to be stored in network storage media into a plurality of segments;

calculating a hash fingerprint for each segment of the plurality of segments;

maintaining an index table wherein each entry maps a fingerprint to a region of a plurality of regions, and a container identifier;

maintaining, in the fingerprint, a first bit indicating a liveness status of a corresponding segment, the first bit set to a live binary value or a dead binary value, and a second bit indicating a deduplication decision of the corresponding segment;

first determining, after in index lookup to the index table, that a percentage of live segments in the region is greater than a defined liveness threshold;

allowing a programmed deduplication operation to be performed to prevent duplicate data segments being stored and setting the first bit to a live state the live binary value;

second determining that a number of segments in the region subject to the deduplication operation is less than a defined deduplication threshold; and

overriding the allowing step to prevent the deduplication operation being performed to thereby allow the duplicate segments to be stored and setting the second bit to a no deduplication state

performing a garbage collection process of a file system to map each data segment fingerprint to a unique bit position in a perfect hash vector (PHV), wherein each bit represents a segment liveness, wherein liveness comprises a referencing of the segment by any current content of the file system;

converting the PHV to a region-based vector using region identifiers for each region of a plurality of regions, and container identifiers of the segments as keys;

defining two bits per segment in the region-based vector, wherein a first bit is set to a binary live or dead value, and a second bit indicating a deduplication decision of the segment;

grouping ingested data into one or more regions of the plurality of regions based on the container identifier and region identifier;

first calculating a liveness of each region to classify a corresponding region as live versus dead by determining that a percentage of live segments in the corresponding region is greater than a defined liveness threshold;

allowing a programmed deduplication operation to be performed to prevent duplicate data segments being stored, and setting the first bit to the live binary value;

second calculating a number of deduplicated segments of each region to determine that a number of segments in the corresponding region subject to the deduplication operation is less than a defined deduplication threshold; and

overriding the allowing step to prevent the deduplication operation being performed to thereby allow duplicate data segments to be stored, and setting the second bit to a no deduplication state.

7. The computer program product of claim 6 wherein the first calculating step comprises:

tallying a number of live segments and a number of dead segments in the corresponding region based on the fingerprint marking;

subtracting the number of dead segments from the number of live segments to obtain a difference that determines the percentage of live segments;

defining the corresponding region as dead if the difference is less than the defined liveness threshold; and

defining the corresponding region as sufficiently live if the difference is greater than or equal to the defined liveness threshold.

8. A system for performing deduplicated backups in a computer network comprising:

a processor comprising a garbage collection component of a file system mapping each data segment fingerprint to a unique bit position in a perfect hash vector (PHV), wherein each bit represents a segment liveness, wherein liveness comprises a referencing of the segment by any current content of the file system; and

a garbage collection assistance component of the processor:

converting the PHV to a region-based vector using region identifiers for each region of a plurality of regions, and container identifiers of the segments as keys;

defining two bits per segment in the region-based vector, wherein a first bit is set to a binary live or dead value, and a second bit indicating a deduplication decision of the segment;

grouping ingested data into one or more regions of the plurality of regions based on the container identifier and region identifier;

first calculating a liveness of each region to classify a corresponding region as live versus dead by determining that a percentage of live segments in the corresponding region is greater than a defined liveness threshold;

allowing a programmed deduplication operation to be performed to prevent duplicate data segments being stored, and setting the first bit to the live binary value;

second calculating a number of deduplicated segments of each region to determine that a number of segments in the corresponding region subject to the deduplication operation is less than a defined deduplication threshold; and

overriding the allowing step to prevent the deduplication operation being performed to thereby allow duplicate data segments to be stored, and setting the second bit to a no deduplication state.

9. The system of claim 8 wherein the first calculating comprises:

tallying a number of live segments and a number of dead segments in the corresponding region based on the fingerprint marking;

subtracting the number of dead segments from the number of live segments to obtain a difference that determines the percentage of live segments;

defining the corresponding region as dead if the difference is less than the defined liveness threshold; and

defining the corresponding region as sufficiently live if the difference is greater than or equal to the defined liveness threshold.

10. The system of claim 8 wherein the garbage collection assistance component further maintains the PHV between the garbage collection process and a subsequent garbage collection process to represent region liveness of the computer network.

11. The system of claim 8 wherein the computer network comprises at least part of a deduplication backup system including a data storage server running a Data Domain file system (DDFS).

12. The system of claim 11 wherein the file system implements a log structured file system in which data and metadata are written sequentially to a log that is implemented as a circular buffer.