Deduplication in an extent-based architecture

• US 9,043,287 B2
• Filed: 11/22/2013
• Issued: 05/26/2015
• Est. Priority Date: 06/21/2011
• Status: Expired due to Fees

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Periyagaram, Subramaniam, Yadav, Sandeep, Lewis, Blake, Faith, Rickard E., Prakash, Ashish, Kesavan, Ram, Subramanian, Ananthan
• Primary Examiner(s): To, Baoquoc N
• Application Number:
  US14/087,345
• Publication Number:
  US 20140201168A1
• Time in Patent Office: 550 Days
• Field of Search: 707/672
• US Class Current: 707/672
• 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
• 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/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

It is determined that a first data block contains the same data as a second data block. The first data block is associated with a first extent and the second data block is associated with a second extent. In response to determining that the first data block contains the same data as the second data block, the second data block is associated with the first extent and the first data block is disassociated with the second extent.

Claims

1. A method comprising:

accessing a plurality of extent mapping entries, wherein each of the plurality of extent mapping entries maps an extent identifier to one or more data blocks;

while accessing the plurality of extent mapping entries, determining that a first data block comprises the same data as a second data block, wherein the first data block is associated with a first extent that is associated with a first of the plurality of extent mapping entries, wherein the second data block is associated with a second extent that is associated with a second of the plurality of extent mapping entries; and

in response to said determining that the first data block comprises the same data as the second data block,

creating a third extent mapping entry that identifies the first extent and that comprises a reference to the second extent mapping entry, an offset identifying the location of the second data block within the second extent, an external reference count associated with the first extent, and an internal reference count associated with the first extent; and

disassociating the first data block from the first extent.

2. The method of claim 1, wherein said determining that the first data block comprises the same data as the second data block comprises:

while accessing the plurality of extent mapping entries, determining that a fingerprint associated with the first extent matches a fingerprint associated with the second extent; and

comparing a first set of one or more data blocks with a second set of one or more data blocks, wherein the first set of data blocks is associated with the first extent, wherein the second set of data blocks is associated with the second extent, wherein the first set of data blocks comprise the first data block, wherein the second set of data blocks comprise the second data block.

3. The method of claim 1 further comprising:

determining that a third data block comprises the same data as a fourth data block, wherein the third data block is associated with the first extent, wherein the fourth data block is associated with the second extent,

wherein the third extent mapping entry further comprises a length, wherein the offset and the length of the third extent mapping entry identifies a contiguous set of blocks that comprises the second data block and the fourth data block.

4. The method of claim 1, wherein said disassociating the first data block from the first extent comprises:

locating the first extent mapping, wherein the first extent mapping entry identifies a third set of one or more data blocks that comprise the first data block, wherein the first extent mapping entry indicates an offset and a length, wherein the offset and the length of the first extent mapping entry identify a first contiguous set of data blocks that comprises the first data block; and

updating at least one of the offset or the length to identify a second contiguous set of data blocks not comprising the first data block.

5. The method of claim 4 further comprising:

determining that the length indicated in the first extent mapping entry is zero;

in response to determining that the length is zero, decrementing an external reference count of the first extent mapping entry;

determining that the external reference count of the first extent mapping entry is zero; and

in response to determining that the external reference count of the first extent mapping entry is zero,

removing the first extent mapping entry; and

indicating that a third set of one or more contiguous data blocks associated with the first extent is available.

6. The method of claim 5 further comprising:

determining that the internal reference count of the first extent mapping entry is zero;

wherein said removing the first extent mapping entry and said indicating that the third set of one or more contiguous data blocks associated with the first extent is available is in response to said determining that the internal reference count of the first extent mapping entry is zero.

7. The method of claim 1 further comprising:

determining that a first internal reference count is greater than a predetermined value, wherein the first internal reference count is associated with the first extent; and

in response to determining that the first internal reference count is greater than a predetermined value, storing a sum of the first internal reference count and a second internal reference count to the second extent mapping entry, wherein the second extent mapping entry identifies the second extent.

8. The method of claim 1 further comprising:

determining that an external reference count is not equal to a predetermined value;

wherein said associating the second data block with the first extent and said disassociating the first data block from the second extent is further in response to said determining that the external reference count is not equal to the predetermined value.

9. A non-transitory machine readable medium having stored thereon instructions for data deduplication, the instructions to:

determine that a data block referenced by a first entry of a plurality of entries matches a data block referenced by a second entry of the plurality of entries, wherein each entry identifies an extent and each entry is associated with at least one volume of a storage system;

in response to a determination that a data block referenced by the first entry matches a data block referenced by the second entry of the plurality of entries, select one of the first entry and the second entry as a donor extent and select the other one of the first entry and the second entry as a recipient extent;

determine that a first reference count equals a predetermined value, wherein the first reference count is associated with the recipient extent; and

in response to a determination that the first reference count equals the first predetermined value, indicate that a set of one or more data blocks are shared between the donor extent and the recipient extent.

10. The non-transitory machine readable medium of claim 9, wherein said instructions to determine that the data block referenced by the first entry matches the data block referenced by the second entry comprises instructions to:

determine that a fingerprint associated with the first entry matches a fingerprint associated with the second entry; and

in response to a determination that the fingerprint associated with the first entry matches the fingerprint associated with the second entry, compare the first data block to the second data block.

11. The non-transitory machine readable medium of claim 9, wherein the instructions further comprise instructions to:

determine that a second reference count equals a second predetermined value, wherein the second reference count is associated with the donor extent; and

in response to a determination that the second reference count equals the second predetermined value, free the donor extent.

12. The non-transitory machine readable medium of claim 9, wherein said instructions to indicate that a set of data blocks are shared between the donor extent and the recipient extent comprises instructions to:

create a third entry that identifies the donor extent and that comprises a reference to the recipient extent, wherein the third entry identifies a subset of the recipient extent that comprises the set of data blocks; and

increment a second reference count, wherein the second reference count is associated with the recipient extent.

13. The non-transitory machine readable medium of claim 12, wherein said instructions to indicate that the set data blocks are shared between the donor extent and the recipient extent further comprises instructions to:

determine that a third reference count is greater than zero, wherein the third reference count is associated with the donor extent; and

in response to a determination that the third reference count is greater than zero, adding the third reference count to the second reference count;

wherein the third entry further comprises the third reference count.

14. The non-transitory machine readable medium of claim 9, wherein said instructions to select one of the first entry and the second entry as a donor extent and select the other one of the first entry and the second entry as a recipient extent further comprises instructions to select one of the first entry and the second entry as a donor extent and select the other one of the first entry and the second entry as a recipient extent is based, at least in part, on an age of the first entry and an age of the second entry, wherein the age of the first entry and the age of the second entry indicates when a data block associated with the respective entry was at least one of write allocated or modified.

15. An apparatus comprising:

a processor; and

a machine readable storage medium having program code stored therein that is executable by the processor to cause the apparatus to,

determine that a data block referenced by a first entry of a plurality of entries matches a data block referenced by a second entry of the plurality of entries, wherein each entry identifies an extent and each entry is associated with at least one volume of a storage system;

in response to a determination that a data block referenced by the first entry matches a data block referenced by the second entry of the plurality of entries, select one of the first entry and the second entry as a donor extent and select the other one of the first entry and the second entry as a recipient extent;

determine that a first reference count equals a predetermined value, wherein the first reference count is associated with the recipient extent; and

in response to a determination that the first reference count equals the first predetermined value, indicate that a set of one or more data blocks are shared between the donor extent and the recipient extent.

16. The apparatus of claim 15, wherein said program code being executable by the processor to cause the apparatus to indicate that one or more data blocks are shared between the donor extent and the recipient extent comprises program code executable by the processor to cause the apparatus to:

determine that a fingerprint associated with the first entry matches a fingerprint associated with the second entry; and

in response to a determination that the fingerprint associated with the first entry matches the fingerprint associated with the second entry, compare the first data block to the second data block.

17. The apparatus of claim 15, wherein said program code being executable by the processor to cause the apparatus to indicate that the set of data blocks are shared between the donor extent and the recipient extent comprises program code executable by the processor to cause the apparatus to:

create a third entry that identifies the donor extent and that comprises a reference to the recipient extent, wherein the third entry identifies a subset of the recipient extent that comprises the set of data blocks; and

increment a second reference count, wherein the second reference count is associated with the recipient extent.

18. The apparatus of claim 17, wherein said program code being executable by the processor to cause the apparatus to indicate that the set data blocks are shared between the donor extent and the recipient extent further comprises program code executable by the processor to cause the apparatus to:

determine that a third reference count is greater than zero, wherein the third reference count is associated with the donor extent; and

in response to a determination that the third reference count is greater than zero, adding the third reference count to the second reference count;

wherein the third entry further comprises the third reference count.

19. The apparatus of claim 15, wherein said program code being executable by the processor to cause the apparatus to select one of the first entry and the second entry as a donor extent and select the other one of the first entry and the second entry as a recipient extent further comprises program code being executable by the processor to cause the apparatus to select one of the first entry and the second entry as a donor extent and select the other one of the first entry and the second entry as a recipient extent is based, at least in part, on an age of the first entry and an age of the second entry, wherein the age of the first entry and the age of the second entry indicates when a data block associated with the respective entry was at least one of write allocated or modified.