Dynamic duplication estimation for garbage collection

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 method of performing

• perfect physical garbage collection for use in a deduplication backup system that dynamically estimates duplicate containers, by:
• scanning, in an analysis phase of the garbage collection process, an index containing a mapping of fingerprints to a sequentially numbered container ID (CID) for a plurality of containers;
• returning, for each fingerprint, a fingerprint sequence associating each fingerprint with a respective unique container ID, wherein a last entry of the sequence is preserved and the remaining entries are considered duplicates;
• and
• maintaining a duplicate array of container IDs indexed by an incremental count, wherein the incremental count is incremented for each of the container IDs, and wherein the duplicate array comprises a duplicate counter that keeps track of a number of live duplicated segments for each container, and further wherein a live segment is a live duplicate segment if a segment with a same fingerprint exists in another container with a higher container ID number relative to other CIDs.