Patent ID: 8108446

Claim:
A method for identifying active data segments in a deduplicated data system, the method comprising: on a periodic basis, entering a unitary mark phase for marking referenced data segments within the deduplicated data system, the unitary mark phase comprising: identifying each file in the deduplicated data system; identifying each data segment in the deduplicated data system that is referenced by at least one file in the deduplicated data system; creating an active-data-segments set that identifies each data segment in the deduplicated data system that is referenced by at least one file in the deduplicated data system; entering an additional unitary mark phase for marking referenced data segments within the deduplicated data system, the additional unitary mark phase comprising: identifying a subset of files in the deduplicated data system that is statistically likely to contain changes within the deduplicated data system; identifying each data segment in the deduplicated data system that is referenced by at least one file in the subset of files; causing the active-data-segments set to identify each data segment in the deduplicated data system that is referenced by at least one file in subset of files.