File system with internal deduplication and management of data blocks

• US 8,131,687 B2
• Filed: 11/13/2008
• Issued: 03/06/2012
• Est. Priority Date: 11/13/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bates, Allen K., Haustein, Nils, Klein, Craig A., Krick, Frank, Troppens, Ulf, Winarski, Daniel
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Moser, Bruce
• Application Number:
  US12/270,101
• Publication Number:
  US 20100121825A1
• Time in Patent Office: 1,209 Days
• Field of Search: 707/202, 707/204, 707/999.202, 707/999.204, 707/692, 707/693, 707/674, 707/664, 707/200, 707/205, 707/206, 707/999.2, 707/999.205, 707/999.206, 707/609, 711/162
• US Class Current: 707/692
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641

Abstract

A method for deduplicating and managing data blocks within a file system includes adding a deduplication identifier to each pointer pointing to a data block to indicate whether the data block is deduplicated, detecting duplicate data blocks, determining whether one of the duplicate data blocks has been deduplicated, when detected, determining that one duplicate data block is a master copy when it is determined that one duplicate data block has been deduplicated, selecting one of the duplicate data blocks to be a master copy when it is determined that the duplicate data blocks have not been deduplicated, and setting the deduplication identifier of the selected duplicate data block to indicate deduplication, and determining that the other duplicate data block is a new duplicate data block and setting the deduplication identifier of the other duplicate data block to indicate deduplication and directing the respective pointer to the master copy.

Claims

1. A method for de-duplicating and managing data blocks within a file system, the method comprising:

adding a deduplication identifier to each pointer pointing to a respective data block, the deduplication identifier indicating whether the respective data block is already deduplicated;

detecting duplicate data blocks within the file system;

determining whether at least one of the duplicate data blocks has been deduplicated with other data blocks, when detected;

determining that the at least one duplicate data block is a master copy when it is determined that the at least one duplicate data block has been deduplicated;

selecting a first of the duplicate data blocks to be a master copy when it is determined that the duplicate data blocks have not been deduplicated, and setting the deduplication identifier of a respective pointer of the selected duplicate data block to indicate deduplication; and

determining that a second of the duplicate data blocks is a new duplicate data block and setting the deduplication identifier of a respective pointer of the second duplicate data block to indicate deduplication, and directing the respective pointer of the second duplicate data block to the master copy.

2. The method of claim 1, further comprising:

providing a database including a plurality of entries each corresponding to a respective master copy, to track an inventory of deduplicated data blocks; and

counting, via a counter, a number of pointers associated with each master copy;

and providing a pointer list corresponding to each master copy to indicate each pointer referencing each master copy.

3. The method of claim 2, wherein:

when it is determined that the at least one duplicate data block is a master copy and the respective pointer of the second duplicate data block is directed to the respective master copy, increasing the counter by one for the respective master copy, and adding the pointer of the second duplicate data block to the pointer list corresponding to the respective master copy.

4. The method of claim 3, wherein:

when selecting the first of the duplicate data blocks as a master copy, creating a new entry in the database for the master copy and setting the counter to one for the new entry to represent the duplicate data block selected as the master copy, adding the pointer of the selected duplicate data block to the pointer list corresponding to the respective master copy; and

when it is determined that the second of the duplicate data blocks is the new duplicate data block, increasing the counter by one for the respective master copy to represent the second duplicate data block.

5. The method of claim 4, further comprising:

determining whether a data block to be deleted has been deduplicated based on a setting of the deduplication identifier corresponding to the pointer of the data block wherein;

when the respective deduplication identifier indicates that the respective data block has not been deduplicated, deleting the respective data block, and

when the respective deduplication identifier indicates that the respective data block has been deduplicated, deleting the respective data block by decreasing the counter by one, determining whether the counter is equal to one and removing the respective pointer of the data block to be deleted from the pointer list for the associated master copy when it is determined that the counter is greater than one, and deleting the master copy associated with the data block to be deleted from the database when it is determined that the counter is equal to one.

6. The method of claim 4, further comprising:

determining whether a data block to be updated has been deduplicated based on the setting of the deduplication identifier corresponding to the pointer of the data block;

updating the data block when the deduplication identifier indicates that the data block is deduplicated, by decreasing the counter for the entry in the database representing the master copy of the data block to be updated, removing the respective pointer from the pointer list for the respective master copy, and allocating a new data block and directing the respective pointer to the new data block allocated.

7. The method of claim 1, wherein the deduplication identifier is a single, most significant bit (MSB) of a multiple bit i_block element that comprises the deduplication identifier added to the respective pointer, wherein remaining least significant bits of the i_block element comprise each respective pointer.

8. A computer program product comprising a non-transitory, computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to implement a method for deduplicating and managing data blocks within a file system, the method comprising:

adding a deduplication identifier to each pointer pointing to a respective data block, the deduplication identifier indicating whether the respective data block is already deduplicated;

detecting duplicate data blocks within the file system;

determining whether at least one of the duplicate data blocks has been deduplicated with other data blocks, when detected;

determining that the at least one duplicate data block is a master copy when it is determined that the at least one duplicate data block has been deduplicated;

selecting a first of the duplicate data blocks to be a master copy when it is determined that the duplicate data blocks have not been deduplicated, and setting the deduplication identifier of a respective pointer of the selected duplicate data block to indicate deduplication; and

determining that a second of the duplicate data blocks is a new duplicate data block and setting the deduplication identifier of a respective pointer of the second duplicate data block to indicate deduplication, and directing the respective pointer of the second duplicate data block to the master copy.

9. The computer program product of claim 8, wherein the method further comprises:

providing a database including a plurality of entries each corresponding to a respective master copy, to track an inventory of deduplicated data blocks; and

counting, via a counter, a number of pointers associated with each master copy; and

providing a pointer list corresponding to each master copy to indicate each pointer referencing each master copy.

10. The computer program product of claim 9, wherein when it is determined that the at least one duplicate data block is a master copy and the respective pointer of the second duplicate data block is directed to the respective master copy, increasing the counter by one for the respective master copy, and adding the pointer of the second duplicate data block to the pointer list corresponding to the respective master copy.

11. The computer program product of claim 10, wherein when selecting the first of the duplicate data blocks as a master copy, creating a new entry in the database for the master copy and setting the counter to one for the new entry to represent the duplicate data block selected as the master copy, adding the pointer of the selected duplicate data block to the pointer list corresponding to the respective master copy;

and when it is determined that the second of the duplicate data blocks is the new duplicate data block, increasing the counter by one for the respective master copy to represent the second duplicate data block.

12. The computer program product of claim 11, the method further comprising:

determining whether a data block to be deleted has been deduplicated based on a setting of the deduplication identifier corresponding to the pointer of the data block wherein;

when the respective deduplication identifier indicates that the respective data block has not been deduplicated, deleting the respective data block, and

when the respective deduplication identifier indicates that the respective data block has been deduplicated, deleting the respective data block by decreasing the counter by one, determining whether the counter is equal to one and removing the respective pointer of the data block to be deleted from the pointer list for the associated master copy when it is determined that the counter is greater than one, and deleting the master copy associated with the data block to be deleted from the database when it is determined that the counter is equal to one.

13. The computer program product of claim 11, the method further comprising:

determining whether a data block to be updated has been deduplicated based on the setting of the deduplication identifier corresponding to the pointer of the data block;

updating the data block when the deduplication identifier indicates that the data block is deduplicated, by decreasing the counter for the entry in the database representing the master copy of the data block to be updated, removing the respective pointer from the pointer list for the respective master copy, and allocating a new data block and directing the respective pointer to the new data block allocated.

14. The computer program product of claim 8, wherein the deduplication identifier is a single, most significant bit (MSB) of a multiple bit i_block element that comprises the deduplication identifier added to the respective pointer, wherein remaining least significant bits of the i_block element comprise each respective pointer.