Patent ID: 8868520

Claim:
A computer implemented method for removing one or more stale fingerprints from a fingerprint database used in deduplicating data from a storage system, the method comprising: storing a list of stale fingerprints in a stale fingerprint data structure of the storage system; sorting the list of stale fingerprints into an inode number order; performing an attributes intersect range calculation on the sorted list that computes a non-overlapping and latest consistency point (CP) range, wherein the non-overlapping and latest CP range is defined by a tuple including a starting value, an ending value, and a CP count associated with a given inode; and comparing the non-overlapping and latest CP range with the fingerprint database wherein the comparing includes: determining whether an identifier, associated with a block of data, is located between the starting value and the ending value, in response to determining that the identifier is located between the starting value and the ending value, determining whether one or more selected fingerprints associated with the block of data and in the fingerprint database have a specific CP count that is less than or equal to the CP count contained in the non-overlapping and latest CP range, removing the one or more selected fingerprints associated with the block of data and in the fingerprint database that have the specific CP count that is less than or equal to the CP count contained in the non-overlapping and latest CP range, wherein the one or more selected fingerprints that have the specific CP count that is less than or equal to the CP count are stale fingerprints, and maintaining one or more other fingerprints associated with the block of data in the fingerprint database that have one or more other CP counts that are greater than the CP count contained in the non-overlapping and latest CP range.