Managing dereferenced chunks in a deduplication system

• US 8,874,532 B2
• Filed: 10/23/2013
• Issued: 10/28/2014
• Est. Priority Date: 08/30/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Anglin, Matthew J., Cannon, David M., Dawson, Colin S., Elder, Robert S.
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US14/060,637
• Publication Number:
  US 20140052952A1
• Time in Patent Office: 370 Days
• Field of Search: 707/672, 707/673, 707/679, 707/681, 707/683, 707/698, 711/159, 711/161, 711/162
• US Class Current: 707/693
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

A chunk index has information on chunks in a storage space referenced in objects in the storage space. The chunk index includes a reference count for each chunk indicating a number of objects in which the chunk is referenced and a reference measurement representing a level of data object references to the chunk. One chunk is selected to remove from the storage space based on a criteria applied to the reference measurements of chunks having reference counts indicating that the chunks are not referenced in one object in the storage space.

Claims

1. A computer program product for maintaining data objects in a storage space, the computer program product comprising a non-transitory computer readable storage medium having computer readable program code embodied therein that executes to perform operations, the operations comprising:

maintaining a chunk index having information on chunks in the storage space referenced in the data objects to provide deduplication of the chunks, wherein the chunk index includes a reference count for each chunk indicating a number of the data objects in which the chunk is referenced and a reference measurement representing a level of the data objects references to the chunk;

incrementing the reference count for one chunk in response to including a reference to the chunk in one of the data objects;

selecting one chunk to remove from the storage space based on a criteria applied to the reference measurements of chunks having reference counts indicating that the chunks are not referenced in one of the data objects in the storage space; and

returning indication of the selected chunk to remove from the storage space.

2. The computer program product of claim 1, wherein the reference measurement of each chunk comprises a time the chunk was most recently referenced in one of the data objects, and wherein applying the criteria comprises selecting the chunk not referenced having the time that is oldest.

3. The computer program product of claim 1, wherein the reference measurement of each chunk comprises a time the reference count was set to a value indicating that the chunk is not referenced in one of the data objects, and wherein applying the criteria comprises selecting the chunk not referenced having the time that is oldest.

4. The computer program product of claim 1, wherein the reference measurement of each chunk comprises a total accumulated references indicating a number of times the chunk has been referenced in the data objects, and wherein applying the criteria comprises selecting the chunk not referenced having a least number of total accumulated references.

5. The computer program product of claim 1, wherein the reference measurement of each chunk comprises a time the reference count was set to a value indicating that the chunk is not referenced in one of the data objects, and wherein applying the criteria comprises selecting the chunk not referenced whose time indicates that the chunk has been dereferenced for a fixed time period.

6. The computer program product of claim 1, wherein selecting one chunk to remove from the storage space comprises:

first selecting chunks based on a first criteria applied to the reference measurements for the chunks not referenced in one of the data objects to measure a first level of data object reference activity to the chunk; and

second selecting from the first selected chunks based on a second criteria to measure a second level of data object reference activity to the chunk, wherein the measurement of the first level of data object reference activity of the first criteria is different from the measurement of the second level of data object reference activity of the second criteria.

7. The computer program product of claim 1, wherein the storage space comprises a first storage space, and wherein the operations further comprise:

decrementing the reference count for one chunk in response to one of removing the chunk from one of the data objects, removing one of the data objects including the chunk, and migrating one of the data objects including the chunk to a second storage space.

8. A system for maintaining data objects in a storage space, comprising:

a non-transitory computer readable storage medium including a chunk index having information on chunks in the storage space referenced in data objects to provide deduplication of the chunks, wherein the chunk index includes a reference count for each chunk indicating a number of the data objects in which the chunk is referenced and a reference measurement representing a level of the data objects references to the chunk;

a processor executing code to perform operations comprising;

incrementing the reference count for one chunk in response to including a reference to the chunk in one of the data objects;

selecting one chunk to remove from the storage space based on a criteria applied to the reference measurements of chunks having reference counts indicating that the chunks are not referenced in one of the data objects in the storage space; and

returning indication of the selected chunk to remove from the storage space.

9. The system of claim 8, wherein the reference measurement of each chunk comprises a time the chunk was most recently referenced in one of the data objects, and wherein applying the criteria comprises selecting the chunk not referenced having the time that is oldest.

10. The system of claim 8, wherein the reference measurement of each chunk comprises a time the reference count was set to a value indicating that the chunk is not referenced in one of the data objects, and wherein applying the criteria comprising selecting the chunk not referenced having the time that is oldest.

11. The system of claim 8, wherein the reference measurement of each chunk comprises a total accumulated references indicating a number of times the chunk has been referenced in one of the data objects, and wherein applying the criteria comprises selecting the chunk not referenced having a least number of total accumulated references.

12. The system of claim 8, wherein the reference measurement of each chunk comprises a time the reference count was set to a value indicating that the chunk is not referenced in one of the data objects, and wherein applying the criteria comprises selecting the chunk not referenced whose time indicates that the chunk has been dereferenced for a fixed time period.

13. The system of claim 8, wherein selecting one chunk to remove from the storage space comprises:

first selecting chunks based on a first criteria applied to the reference measurements for the chunks not referenced in one of the data objects to measure a first level of data object reference activity to the chunk;

second selecting from the first selected chunks based on a second criteria to measure a second level of data object reference activity to the chunk, wherein the measurement of the first level of data object reference activity of the first criteria is different from the measurement of the second level of data object reference activity of the second criteria.

14. The system of claim 8, wherein the storage space comprises a first storage space, and wherein the operations further comprise:

decrementing the reference count for one chunk in response to one of removing the chunk from one of the data objects, removing one of the data objects including the chunk, and migrating one of the data objects including the chunk to a second storage space.

15. A computer-implemented method for maintaining, by a processor, data objects in a storage space, comprising:

maintaining a chunk index having information on chunks in the storage space referenced in data objects to provide deduplication of the chunks, wherein the chunk index includes a reference count for each chunk indicating a number of the data objects in which the chunk is referenced and a reference measurement representing a level of the data objects references to the chunk;

incrementing the reference count for one chunk in response to including a reference to the chunk in one of the data objects;

selecting one chunk to remove from the storage space based on a criteria applied to the reference measurements of chunks having reference counts indicating that the chunks are not referenced in one of the data objects in the storage space; and

returning indication of the selected chunk to remove from the storage space.

16. The method of claim 15, wherein the reference measurement of each chunk comprises a time the chunk was most recently referenced in one of the data objects, and wherein applying the criteria comprises selecting the chunk not referenced having the time that is oldest.

17. The method of claim 15, wherein the reference measurement of each chunk comprises a time the reference count was set to a value indicating that the chunk is not referenced in one of the data objects, and wherein applying the criteria comprising selecting the chunk not referenced having the time that is oldest.

18. The method of claim 15, wherein the reference measurement of each chunk comprises a total accumulated references indicating a number of times the chunk has been referenced in the data objects, and wherein applying the criteria comprises selecting the chunk not referenced having a least number of total accumulated references.

19. The method of claim 15, wherein the reference measurement of each chunk comprises a time the reference count was set to a value indicating that the chunk is not referenced in one of the data objects, and wherein applying the criteria comprises selecting the chunk not referenced whose time indicates that the chunk has been dereferenced for a fixed time period.

20. The method of claim 15, wherein selecting one chunk to remove from the storage space comprises:

first selecting chunks based on a first criteria applied to the reference measurements for the chunks not referenced in one data of the data objects to measure a first level of data object reference activity to the chunk; and

second selecting from the first selected chunks based on a second criteria to measure a second level of data object reference activity to the chunk, wherein the measurement of the first level of data object reference activity of the first criteria is different from the measurement of the second level of data object reference activity of the second criteria.