Managing dereferenced chunks in a deduplication system

• US 8,775,390 B2
• Filed: 05/22/2012
• Issued: 07/08/2014
• Est. Priority Date: 08/30/2011
• Status: Active Grant

• 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:
  US13/477,908
• Publication Number:
  US 20130054545A1
• Time in Patent Office: 777 Days
• Field of Search: 707/672, 707/673, 707/679, 707/681, 707/693, 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 implemented-complemented 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, 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;

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, wherein the reference measurement of each chunk comprises a time most recently dereferenced indicating a time when the reference count for the chunk was decremented to indicate that the chunk is not referenced in one of the data objects; and

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

2. The method of claim 1, wherein applying the criteria comprising selecting the chunk not referenced having the time that is oldest.

3. The method of claim 1, wherein applying the criteria comprises selecting the chunk not referenced whose time indicates that the chunk has been dereferenced for a fixed time period.

4. The method 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.

5. The method of claim 4, wherein the first selecting chunks comprises selecting the chunks whose time most recently dereferenced indicates that the chunk has been dereferenced for a fixed time period.

6. The method of claim 5, wherein the second selecting based on the second criteria comprises one of:

a least recently referenced criteria, wherein the second selecting from the first selected chunks comprises selecting at least one chunk having an oldest time most recently referenced, wherein the time most recently referenced indicates a time the chunk was most recently referenced in one of the data objects;

a least recently dereferenced criteria, wherein the second selecting from the first selected chunks comprises selecting at least one chunk having the time most recently dereferenced that is oldest; and

a total accumulated references criteria, wherein the second selecting from the first selected chunks comprises selecting at least one chunk having a least number of total accumulated references, wherein the total accumulated references indicates a number of times the chunk has been added as a reference to the data objects.

7. The method of claim 1, wherein the storage space comprises a first storage space, and further comprising:

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

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 computer program product for maintaining data objects in a storage space, the computer program product comprising a computer readable storage medium, including a hardware component, 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, 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;

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, wherein the reference measurement of each chunk comprises a time most recently dereferenced indicating a time when the reference count for the chunk was decremented to indicate that the chunk is not referenced in one of the data objects; and

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

9. The computer program product of claim 8, wherein applying the criteria comprises selecting the chunk not referenced having the time that is oldest.

10. The computer program product of claim 8, wherein applying the criteria comprises selecting the chunk not referenced whose time indicates that the chunk has been dereferenced for a fixed time period.

11. The computer program product 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; 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.

12. The computer program product of claim 11, wherein the first selecting chunks comprises selecting the chunks whose time most recently dereferenced indicates that the chunk has been dereferenced for a fixed time period.

13. The computer program product of claim 12, wherein the second selecting based on the second criteria comprises one of:

a least recently referenced criteria, wherein the second selecting from the first selected chunks comprises selecting at least one chunk having an oldest time most recently referenced, wherein the time most recently referenced indicates a time the chunk was most recently referenced in one of the data objects;

a least recently dereferenced criteria, wherein the second selecting from the first selected chunks comprises selecting at least one chunk having the time most recently dereferenced that is oldest; and

a total accumulated references criteria, wherein the second selecting from the first selected chunks comprises selecting at least one chunk having a least number of total accumulated references, wherein the total accumulated references indicates a number of times the chunk has been added as a reference to the data objects.

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

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

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 system for maintaining data objects in a storage space, comprising:

a computer readable storage medium including a chunk index having information on chunks in the storage space referenced in objects, 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 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, wherein the reference measurement of each chunk comprises a time most recently dereferenced indicating a time when the reference count for the chunk was decremented to indicate that the chunk is not referenced in one of the data objects; and

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

16. The system of claim 15, wherein applying the criteria comprising selecting the chunk not referenced having the time that is oldest.

17. The system of claim 15, wherein applying the criteria comprises selecting the chunk not referenced whose time indicates that the chunk has been dereferenced for a fixed time period.

18. The system 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 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.

19. The system of claim 18, wherein the first selecting chunks comprises selecting the chunks whose time most recently dereferenced indicates that the chunk has been dereferenced for a fixed time period.

20. The system of claim 19, wherein the second selecting based on the second criteria comprises one of:

a least recently referenced criteria, wherein the second selecting from the first selected chunks comprises selecting at least one chunk having an oldest time most recently referenced, wherein the time most recently referenced indicates a time the chunk was most recently referenced in one of the data objects;

a least recently dereferenced criteria, wherein the second selecting from the first selected chunks comprises selecting at least one chunk having the time most recently dereferenced that is oldest; and

a total accumulated references criteria, wherein the second selecting from the first selected chunks comprises selecting at least one chunk having a least number of total accumulated references, wherein the total accumulated references indicates a number of times the chunk has been added as a reference to of the data objects.

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

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

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