Fragmentation control for performing deduplication operations

Abstract

The techniques introduced here provide for enabling deduplication operations for a file system without significantly affecting read performance of the file system due to fragmentation of the data sets in the file system. The techniques include determining, by a storage server that hosts the file system, a level of fragmentation that would be introduced to a data set stored in the file system as a result of performing a deduplication operation on the data set. The storage server then compares the level of fragmentation with a threshold value and determines whether to perform the deduplication operation based on a result of comparing the level of fragmentation with the threshold value. The threshold value represents an acceptable level of fragmentation in the data sets of the file system.

1 - 24 . (canceled) 
     
     
         25 . A method comprising:
 storing, by a storage server, a data set as an inode in a storage device, the inode including multiple indirect blocks storing multiple physical volume bock numbers (PVBNs), wherein in a first indirect block of the indirect blocks includes a first PVBN of the PVBNs, the first PVBN including a reference to a first physical block of the storage device containing a first portion of the data set;   calculating, by a storage server, a level of fragmentation that would be introduced to the data set in an event a deduplication operation were to be performed on the data set, the calculating including:
 determining, without performing the deduplication operation, addresses of multiple physical blocks that would contain portions of the data set in an event the deduplication operation is performed, the physical blocks being non-contiguous on the storage device, 
 sorting the addresses in the order they occur on the storage device to generate sorted addresses, and 
 calculating, based on the sorted addresses, a number of read operations needed to access the data set in an event the deduplication operation is performed; and 
   performing, by the storage server, the deduplication operation in an event the number of read operations to be performed is below a specified threshold.   
     
     
         26 . The method of  claim 25 , wherein performing the deduplication operation if the number of read operations to be performed is below the specified threshold includes:
 calculating the level of fragmentation as a function of the number of read operations needed to access the data set in an event the deduplication operation is performed and a number of read operations needed to access an ideal data set.   
     
     
         27 . The method of  claim 26  further comprising:
 performing the deduplication operation in response to determining that the level of fragmentation is below a threshold value. 
 
     
     
         28 . The method of  claim 27 , wherein the threshold value represents a maximum acceptable level of fragmentation for the data set. 
     
     
         29 . The method of  claim 27 , wherein the threshold value is set based on user input. 
     
     
         30 . The method of  claim 27 , wherein the threshold value is determined based on a minimum read performance to be provided by the storage server. 
     
     
         31 . The method of  claim 27 , wherein the threshold value is determined based on a minimum storage resource savings to be provided by the storage server. 
     
     
         32 . The method of  claim 27 , wherein the threshold value is of a first value if a storage criterion is based on a read performance and of a second value if the storage criterion is based on a storage resource savings, the first value being lower than the second value. 
     
     
         33 . The method of  claim 25 , wherein determining, without performing the deduplication operation, addresses of multiple physical blocks that would contain portions of the data set includes:
 determining a donor block in the storage device containing data whose fingerprint matches the first portion of the data set stored in the first physical block, the first physical block having a first address, the first address being one of multiple addresses in an address list having addresses of a set of physical blocks storing the portions of the data set,   determining an address of the donor block as an address of the first physical block without overwriting the first PVBN with the address of the donor block,   replacing the first address in the address list with the address of the donor block to generate a modified address list, and   determining addresses in the modified address list as the addresses of the physical blocks that would contain portions of the data set in an event the data duplication operation is performed.   
     
     
         34 . A computer-readable storage medium storing computer-readable instructions, the instructions comprising:
 instructions for storing a data set in multiple physical blocks of a storage device associated with a storage server, the data set including multiple portions of a first data file stored in a first set of the physical blocks and multiple portions of a second data file stored in a second set of the physical blocks;   instructions for calculating a fragmentation index representative of a level of fragmentation that would be introduced to the data set in an event a deduplication operation is performed on the data set, the calculating performed without executing the deduplication operation, the fragmentation index being a ratio of a number of read operations needed to access the first data file in an event the deduplication operation is performed and a number of read operations needed to access an ideal data set; and   instructions for performing the deduplication operation on the first data file if the fragmentation index is below a threshold value.   
     
     
         35 . The computer-readable storage medium of  claim 35 , wherein the instructions for storing the data set include:
 instructions for storing the first data file as a first inode in the storage device, the first inode including multiple indirect blocks that store multiple PVBNs, wherein in a first indirect block of the indirect blocks includes a first PVBN of the PVBNs, the first PVBN including a reference to a first physical block of the first set of the physical blocks storing a first portion of the first data file.   
     
     
         36 . The computer-readable storage medium of  claim 35 , wherein the instructions for calculating the fragmentation index include:
 instructions for determining, without performing the deduplication operation, addresses of a set of the physical blocks that would contain portions of the first data file in an event the deduplication operation is performed on the first data file, the set of the physical blocks being non-contiguous on the storage device, and   instructions for determining the number of read operations needed to access the first data file in an event the deduplication operation is performed based on the addresses.   
     
     
         37 . The computer-readable storage medium of  claim 37 , wherein the instructions for determining the addresses of the set of the physical blocks include:
 instructions for determining a donor block in the storage device containing data whose fingerprint matches a first portion of the first data file stored in a first physical block of the first set of the physical blocks, the first physical block having a first address, the first address being one of multiple addresses in an address list having addresses of the first set of the physical blocks,   determining an address of the donor block as an address of the first physical block without overwriting a first PVBN with the address of the donor block, the first PVBN storing the first address, and being one of multiple PVBNs of the first data file storing references to the first set of the physical blocks,   replacing the first address in the address list with the address of the donor block to generate a modified address list, and   determining addresses in the modified address list as the addresses of the set of the physical blocks that would contain portions of the data set in an event the data duplication operation is performed on the first data file.   
     
     
         38 . The computer-readable storage medium of  claim 35 , wherein the threshold value represents a maximum acceptable level of fragmentation for the data set. 
     
     
         39 . The computer-readable storage medium of  claim 35 , wherein the threshold value is set based on user input. 
     
     
         40 . The computer-readable storage medium of  claim 35 , wherein the threshold value is of a first value if a storage criterion is based on a read performance and of a second value if the storage criterion is based on a storage resource savings, the first value being lower than the second value. 
     
     
         41 . A storage server comprising:
 a processor;   a memory coupled with the processor, the memory storing instructions which when executed by the processor cause the processor to perform a plurality of operations, including:
 storing, by a storage server, a data set as an inode in a storage device, the inode including multiple indirect blocks storing multiple physical volume bock numbers (PVBNs), wherein in a first indirect block of the indirect blocks includes a first PVBN of the PVBNs, the first PVBN including a reference to a first physical block of the storage device containing a first portion of the data set; 
 calculating, by a storage server, a level of fragmentation that would be introduced to the data set in an event a deduplication operation were to be performed on the data set, the calculating including:
 determining, without performing the deduplication operation, addresses of multiple physical blocks that would contain portions of the data set in an event the deduplication operation is performed, the physical blocks being non-contiguous on the storage device, 
 sorting the addresses in the order they occur on the storage device to generate sorted addresses, and 
 calculating, based on the sorted addresses, a number of read operations needed to access the data set in an event the deduplication operation is performed; and 
 
 performing, by the storage server, the deduplication operation in an event the number of read operations to be performed is below a specified threshold. 
   
     
     
         42 . The storage server of  claim 42 , wherein the operations for performing the deduplication operation if the number of read operations to be performed is below the specified threshold include:
 calculating the level of fragmentation as a function of the number of read operations needed to access the data set in an event the deduplication operation is performed and a number of read operations needed to access an ideal data set.   
     
     
         43 . The storage server of  claim 43  wherein the operations further include:
 performing the deduplication operation in response to determining that the level of fragmentation is below a threshold value. 
 
     
     
         44 . The storage server of  claim 44 , wherein the threshold value represents a maximum acceptable level of fragmentation for the data set. 
     
     
         45 . The storage server of  claim 44 , wherein the threshold value is determined based on a minimum read performance to be provided by the storage server. 
     
     
         46 . The storage server of  claim 44 , wherein the threshold value is determined based on a minimum storage resource savings to be provided by the storage server. 
     
     
         47 . The storage server of  claim 44 , wherein the threshold value is of a first value if a storage criterion is based on a read performance and of a second value if the storage criterion is based on a storage resource savings, the first value being lower than the second value.