Apparatus, system, and method for enhanced block-level deduplication

• US 8,204,867 B2
• Filed: 07/29/2009
• Issued: 06/19/2012
• Est. Priority Date: 07/29/2009
• Status: Active Grant

• Current Assignee: Daedalus Blue LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Walls, Andrew D., Benhase, Michael T.
• Primary Examiner(s): Cottingham, John R.
• Assistant Examiner(s): Uddin, Mohammed R
• Application Number:
  US12/511,827
• Publication Number:
  US 20110029497A1
• Time in Patent Office: 1,056 Days
• Field of Search: 707/692, 707/999.106
• US Class Current: 707/692
• 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/0676 Magnetic disk device

Abstract

An apparatus, system, and method are disclosed for enhanced block-level deduplication. A computer program product stores one or more express block signatures in an express directory that meet a reference count requirement. The computer program product also stores one or more primary block signatures and one or more reference counts for the primary block signatures in a primary directory. Each primary block signature has a corresponding reference count. The computer program product determines whether a block signature for a data block matches one of the one or more express block signatures stored in the express directory.

Claims

1. A computer program product comprising a computer readable storage medium having computer usable program code executable by a processor to perform operations for enhanced block-level deduplication, the operations comprising:

storing one or more express block signatures in an express directory, the one or more express block signatures comprising block signatures for data blocks meeting a reference count requirement, the one or more express block signatures corresponding to one or more data blocks received by a storage device, the reference count requirement comprising a minimum number of references to a particular data block for inclusion of a block signature for the particular data block in the express directory;

storing one or more primary block signatures and one or more reference counts for the primary block signatures in a primary directory, the one or more primary block signatures corresponding to the one or more data blocks, the primary block signatures comprising block signatures having a reference count below the reference count requirement, the primary directory distinct from the express directory; and

determining whether a block signature for a data block matches one of the one or more express block signatures stored in the express directory as the data block is received by a storage device.

2. The computer program product of claim 1, further comprising directing the storage device to store the data block in response to the block signature failing to match the one or more express block signatures stored in the express directory.

3. The computer program product of claim 2, further comprising determining whether the data block matches a stored data block associated with a matched express block signature in response to the block signature matching one of the one or more express block signatures.

4. The computer program product of claim 3, further comprising:

directing the storage device to store a pointer to the stored data block in response to the data block matching the stored data block; and

incrementing a reference count associated with a block signature corresponding to the stored data block.

5. The computer program product of claim 3, further comprising directing the storage device to store the data block in response to the data block failing to match the stored data block.

6. The computer program product of claim 1, further comprising promoting a block signature stored in the primary directory to the express directory in response to a reference count associated with the block signature meeting the reference count requirement.

7. The computer program product of claim 1, further comprising computing the block signature of the data block as the data block is received by the storage device.

8. The computer program product of claim 1, wherein storing one or more express block signatures in an express directory further comprises adjusting the reference count requirement in response to an express directory size meeting a predetermined threshold.

9. An apparatus for enhanced block-level deduplication, the apparatus comprising:

a processor;

a memory in communication with the processor;

an express directory module configured to store one or more express block signatures in an express directory, the one or more express block signatures comprising block signatures for data blocks meeting a reference count requirement, the one or more express block signatures corresponding to one or more data blocks received by a storage device, the reference count requirement comprising a minimum number of references to a particular data block for inclusion of a block signature for the particular data block in the express directory;

a primary directory module configured to store one or more primary block signatures and one or more reference counts for the primary block signatures in a primary directory, the one or more primary block signatures corresponding to the one or more data blocks, the primary block signatures comprising block signatures having a reference count below the reference count requirement, the primary directory distinct from the express directory;

a block signature module configured to compute a block signature of a data block as the data block is received by a storage device; and

a signature comparison module configured to determine whether the block signature for the data block matches one of the one or more express block signatures stored in the express directory.

10. The apparatus of claim 9, further comprising a block storage module configured to direct the storage device to store the data block in response to the block signature failing to match the one or more express block signatures stored in the express directory.

11. The apparatus of claim 10, further comprising a block comparison module configured to determine whether the data block matches a stored data block associated with a matched express block signature in response to the block signature matching one of the one or more express block signatures.

12. The apparatus of claim 11, further comprising:

a reference storage module configured to direct the storage device to store a pointer to the stored data block in response to the data block matching the stored data block;

a reference count module configured to increment a reference count associated with a block signature corresponding to the stored data block.

13. The apparatus of claim 11, wherein the block storage module is further configured to direct the storage device to store the data block in response to the data block failing to match the stored data block.

14. The apparatus of claim 9, further comprising a promotion module configured to promote a block signature stored in the primary directory to the express directory in response to a reference count associated with the block signature meeting the reference count requirement.

15. The apparatus of claim 9, wherein the express directory module further comprises an adjustment module configured to adjust the reference count requirement in response to an express directory size meeting a predetermined threshold.

16. A method for enhanced block-level deduplication, the method comprising:

storing one or more express block signatures in an express directory, the one or more express block signatures comprising block signatures for data blocks meeting a reference count requirement, the one or more express block signatures corresponding to one or more data blocks received by a storage device, the reference count requirement comprising a minimum number of references to a particular data block for inclusion of a block signature for the particular data block in the express directory, the express directory implemented on memory;

storing one or more primary block signatures and one or more reference counts for the primary block signatures in a primary directory, the one or more primary block signatures corresponding to the one or more data blocks, the primary block signatures comprising block signatures having a reference count below the reference count requirement, the primary directory distinct from the express directory;

computing the block signature of the data block as the data block is received by a storage device before the data block is written to a storage disk of the storage device so long as resource usage of the storage device is below a resource threshold; and

determining by a computer whether a block signature for a data block matches one of the one or more express block signatures stored in the express directory.

17. The method of claim 16, further comprising directing the storage device to store the data block in response to the block signature failing to match the one or more express block signatures stored in the express directory.

18. The method of claim 16, further comprising determining whether the data block matches a stored data block associated with a matched express block signature in response to the block signature matching one of the one or more express block signatures.

19. The method of claim 18, further comprising:

directing the storage device to store a pointer to the stored data block in response to the data block matching the stored data block;

incrementing a reference count associated with a block signature corresponding to the stored data block.

20. The method of claim 16, further comprising promoting a block signature stored in the primary directory to the express directory in response to a reference count associated with the block signature meeting the reference count requirement.