Storing de-duplicated data with minimal reference counts
AssigneeEMC IP Holding Company LLC
InventorsKedar Patwardhan, Anand Ghatnekar
Life of this patent
Estimating the term…
Abstract
Systems and methods for adding backups to de-duplicated storage and for removing backups from de-duplicated storage are disclosed. Backups can be added to the de-duplicated storage with minimal reference count updates. Backup data sets can be removed without garbage collection processes being performed on the de-duplicated storage.
Claims18
A method for removing backup data of a client from a backup operation, wherein backups of the data are stored in a data set, the method comprising:
- selecting a backup data set for removal, wherein the backup data set has been divided into a plurality of chunks of data and wherein a fingerprint has been determined for each of the plurality of chunks;
- determining if the each chuck is a candidate chunk for removal by comparing the fingerprint of each chunk against one or more manifests of previous backup data sets and one or more manifests of subsequent backup data sets, wherein if the fingerprint for the each chunk is not found within the one or more manifests of previous backup data sets and one or more manifests of subsequent backup data sets, the chunk is a candidate chunk;
- decrementing a reference count associated with the candidate chunk in a reference database that stores reference counts of chunks stored in the de-duplicated storage, wherein the reference database associates reference counts with fingerprints of chunks;
- and
- removing the candidate chunk from the de-duplicated storage if the reference count is zero after being decremented.
A method for removing backup data set in a de-duplicated storage, wherein the de-duplicated storage stores previous backups, the method comprising:
- selecting a backup data set for removal, wherein the backup data set has been divided into a plurality of chunks of data and wherein a fingerprint has been determined for each of the plurality of chunks;
- for each chunk of data to be removed:
- referencing and comparing the fingerprint of each chunk to one or more manifests of previous backup data sets and one or more manifests of subsequent backup data sets, to determine if the chunk is found within the one or more manifests of previous backup data sets and one or more manifests of subsequent backup data sets,
- labeling the chunk as a candidate chunk if it is not found within the one or more manifests of previous backup data sets and one or more manifests of subsequent backup data sets;
- decrementing a reference count associated with the candidate chunk in a reference database that stores reference counts of chunks stored in the de-duplicated storage when the chunk is not present in the one or more previous backups and is present in the de-duplicated storage, wherein the reference database associates reference counts with fingerprints of chunks;
- and
- removing the candidate chunk and the associated fingerprint from the de-duplicated storage if the reference count is zero after being decremented.
Dependencies are inferred from the claim text.