Managing dereferenced chunks in a deduplication system

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.

1 . A computer program product for maintaining data objects in a storage space, the computer program product comprising a 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 objects, wherein 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; and   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 object in 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 data object, 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 object, and wherein applying the criteria comprising 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 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 object, 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 data object to measure a 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 level of data object reference activity to the chunk, wherein the measurement of the level of data object reference activity of the first criteria is different from the measurement of the level of data object reference activity of the second criteria.   
     
     
         7 . The computer program product of  claim 6 , 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 data object, and 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. 
     
     
         8 . The computer program product of  claim 7 , 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 data object;   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 data objects.   
     
     
         9 . The computer program product of  claim 1 , 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 data object; and   decrementing the reference count for one chunk in response to one of removing the chunk from one data object, removing the data object including the chunk, and migrating one data object including the chunk to a second storage space.   
     
     
         10 . 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 objects in which the chunk is referenced and a reference measurement representing a level of data object references to the chunk; and   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 object in the storage space.   
     
     
         11 . The system of  claim 10 , wherein the reference measurement of each chunk comprises a time the chunk was most recently referenced in one data object, and wherein applying the criteria comprises selecting the chunk not referenced having the time that is oldest. 
     
     
         12 . The system of  claim 10 , 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 object, and wherein applying the criteria comprising selecting the chunk not referenced having the time that is oldest. 
     
     
         13 . The system of  claim 10 , wherein the reference measurement of each chunk comprises a total accumulated references indicating a number of times the chunk has been referenced in data objects, and wherein applying the criteria comprises selecting the chunk not referenced having a least number of total accumulated references. 
     
     
         14 . The system of  claim 10 , 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 object, 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. 
     
     
         15 . The system of  claim 10 , 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 object to measure a level of data object reference activity to the chunk;   second selecting from the first selected chunks based on a second criteria to measure a level of data object reference activity to the chunk, wherein the measurement of the level of data object reference activity of the first criteria is different from the measurement of the level of data object reference activity of the second criteria.   
     
     
         16 . The system of  claim 15 , 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 data object, and 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. 
     
     
         17 - 23 . (canceled) 
     
     
         24 . The system of  claim 16 , 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 data object;   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 data objects.   
     
     
         25 . The system of  claim 10 , 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 data object; and   decrementing the reference count for one chunk in response to one of removing the chunk from one data object, removing the data object including the chunk, and migrating one data object including the chunk to a second storage space.