Patent ID: 8364644

Claim:
A data storage system, comprising: a processor; a physical storage device containing a data set comprising a plurality of data blocks; and a memory coupled with the processor, wherein the memory stores: a plurality of bitmaps comprising a plurality of bits, each of the plurality of bits are either asserted or deasserted, a plurality of persistent point-in-time image (PPI) bitmaps comprising a plurality of PPI map bits, each of the plurality of asserted PPI map bits corresponding to a PPI data block, a summary bitmap comprising a plurality of summary bits, each asserted summary bit corresponding to an asserted PPI map bit in one of the plurality of PPI bitmaps, an active bitmap comprising a plurality of active bits, each asserted active bit corresponding to a data block allocated to a file, an exclusion bitmap comprising a plurality of exclusion bits, each asserted exclusion bit corresponding to a data block to be excluded from a PPI bitmap of the data set; and instructions that, when executed by the processor, cause the processor to: compute a fingerprint for each of the plurality of data blocks from metadata related to the plurality of data blocks, store the fingerprint in a changelog file excluded from the PPI bitmap, compare a fingerprint of a first data block with a fingerprint of a second data block to determine whether the first data block and the second data block are duplicates, select one of the first data block and the second data block if one of the first data block and the second data block is a duplicate data block, update a reference to one of first data block and the second data block, wherein updating the one of the first data block and the second data block deallocates the duplicate data block, wherein an active bit corresponding to a deallocated data block is deasserted in the active bitmap; and create a new PPI bitmap of the data set, the new PPI bitmap including a plurality of PPI data blocks, wherein each data block in the plurality of PPI data blocks corresponds to a deasserted summary bit of the summary bitmap, an asserted active bit of the active bitmap, and a deasserted exclusion bit of the exclusion bitmap.