Deduplication in an extent-based architecture

• US 8,600,949 B2
• Filed: 06/21/2011
• Issued: 12/03/2013
• Est. Priority Date: 06/21/2011
• Status: Active Grant

• 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:
  US13/165,631
• Publication Number:
  US 20120330903A1
• Time in Patent Office: 896 Days
• Field of Search: 707/692
• US Class Current: 707/664
• 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

A request is received to remove duplicate data. A log data container associated with a storage volume in a storage server is accessed. The log data container includes a plurality of entries. Each entry is identified by an extent identifier in a data structures stored in a volume associated with the storage server. For each entry in the log data container, a determination is made if the entry matches another entry in the log data container. If the entry matches another entry in the log data container, a determination is made of a donor extent and a recipient extent. If an external reference count associated with the recipient extent equals a first predetermined value, block sharing is performed for the donor extent and the recipient extent. A determination is made if the reference count of the donor extent equals a second predetermined value. If the reference count of the donor extent equals the second predetermined value, the donor extent is freed.

Claims

1. A computerized method for performing deduplication in an extent-based architecture including a storage server, the method comprising:

receiving, by the storage server, a request to remove duplicate data in the storage server;

accessing a log data container associated with a storage volume of the storage server, the log data container including a plurality of entries, wherein each entry is identified by an extent identifier in a data structure stored in a volume associated with the storage server; and

matching an entry in the log data container with another entry in the log data container

determining a donor extent and a recipient extent, and upon determining an external reference count associated with the recipient extent equals a first predetermined value, performing block sharing for the donor extent and the recipient extent, and upon determining the reference count of the donor extent equals a second predetermined value, freeing the donor extent.

2. The computerized method of claim 1, wherein the matching another entry in the log data container comprises:

for each data block associated with the entry,

comparing a fingerprint of the data block with a fingerprint of each data block associated with the another entry in the log data container; and

performing a comparison of each byte in the data block with each corresponding byte in the another data block upon determining the fingerprint of the data block compares in a predetermined manner with the fingerprint of the another data block in the log data container;

matching the data block to the another data block further comprises by comparing each byte in the data block in a predetermined manner with each corresponding byte in the another data block in the log data container.

3. The computerized method of claim 1, wherein determining a donor extent and a recipient extent is based on an age of the entry and an age of the another entry.

4. The computerized method of claim 1, wherein performing block sharing comprises:

updating an internal reference count associated with the recipient extent to include an internal reference count associated with the donor extent;

updating an internal reference count associated with the donor extent;

creating a new extent entry;

updating the donor extent; and

updating the recipient extent.

5. The computerized method of claim 1, wherein freeing the donor extent comprises:

freeing one or more data blocks associated with the donor extent; and

removing one or more entries in an extent-to-physical map associated with the donor extent.

6. The computerized method of claim 1, wherein the donor extent is an extent associated with the entry and the recipient extent is an extent associated with the another entry.

7. The computerized method of claim 1, wherein the donor extent is an extent associated with the another entry and the recipient extent is an extent associated with the entry.

8. The computerized method of claim 1, wherein the first predetermined value is a value greater than zero and the second predetermined value is zero.

9. A non-transitory computer-readable storage medium embodied with executable instructions that cause a processor to perform operations for deduplication in an extent-based architecture including a storage server, the operations comprising:

receiving a request to remove duplicate data in the storage server;

accessing a log data container associated with a storage volume of the storage server, the log data container including a plurality of entries, wherein each entry is identified by an extent identifier in a data structure stored in a volume associated with the storage server; and

matching an entry in the log data container with another entry in the log data container

determining a donor extent and a recipient extent, and upon determining an external reference count associated with the recipient extent equals a first predetermined value, performing block sharing for the donor extent and the recipient extent, and upon determining the reference count of the donor extent equals a second predetermined value, freeing the donor extent.

10. The non-transitory computer-readable storage medium of claim 9, wherein the matching another entry in the log data container comprises:

for each data block associated with the entry,

comparing a fingerprint of the data block with a fingerprint of each data block associated with the another entry in the log data container; and

performing a comparison of each byte in the data block with each corresponding byte in the another data block upon determining the fingerprint of the data block compares in a predetermined manner with the fingerprint of the another data block in the log data container;

matching the data block to the another data block further comprises by comparing each byte in the data block in a predetermined manner with each corresponding byte in the another data block in the log data container.

11. The non-transitory computer-readable storage medium of claim 9, wherein determining a donor extent and a recipient extent is based on an age of the entry and an age of the another entry.

12. The non-transitory computer-readable storage medium of claim 9, wherein performing block sharing comprises:

updating an internal reference count associated with the recipient extent to include an internal reference count associated with the donor extent;

updating an internal reference count associated with the donor extent;

creating a new extent entry;

updating the donor extent; and

updating the recipient extent.

13. The non-transitory computer-readable storage medium of claim 9, wherein freeing the donor extent comprises:

freeing one or more data blocks associated with the donor extent; and

removing one or more entries in an extent-to-physical map associated with the donor extent.

14. The non-transitory computer-readable storage medium of claim 9, wherein the donor extent is an extent associated with the entry and the recipient extent is an extent associated with the another entry.

15. The non-transitory computer-readable storage medium of claim 9, wherein the donor extent is an extent associated with the another entry and the recipient extent is an extent associated with the entry.

16. The non-transitory computer-readable storage medium of claim 9, wherein the first predetermined value is a value greater than zero and the second predetermined value is zero.

17. A computerized system comprising:

a processor coupled to a memory through a bus; and

instructions executed from the memory by the processor to cause the processor to receive a request to remove duplicate data in the computerized system;

access a log data container associated with a storage volume of the storage server, the log data container including a plurality of entries, wherein each entry is identified by an extent identifier in a data structure stored in a volume associated with the storage server; and

match an entry in the log data container with another entry in the log data container

determine a donor extent and a recipient extent, and upon determining an external reference count associated with the recipient extent equals a first predetermined value, performing block sharing for the donor extent and the recipient extent, and upon determining the reference count of the donor extent equals a second predetermined value, freeing the donor extent.

18. The computerized system of claim 17, wherein to matching the entry to another entry in the log data container comprises:

for each data block associated with the entry,

compare a fingerprint of the data block with a fingerprint of each data block associated with the another entry in the log data container; and

perform a comparison of each byte in the data block with each corresponding byte in the another data block upon determining the fingerprint of the data block compares in a predetermined manner with the fingerprint of the another data block in the log data container;

match the data block to the another data block further comprises by comparing each byte in the data block in a predetermined manner with each corresponding byte in the another data block in the log data container.

19. The computerized system of claim 17, wherein to determine a donor extent and a recipient extent is based on an age of the entry and an age of the another entry.

20. The computerized system of claim 17, wherein to perform block sharing comprises:

updating an internal reference count associated with the recipient extent to include an internal reference count associated with the donor extent;

updating an internal reference count associated with the donor extent;

creating a new extent entry;

updating the donor extent; and

updating the recipient extent.

21. The computerized system of claim 17, wherein to free the donor extent comprises:

freeing one or more data blocks associated with the donor extent; and

removing one or more entries in an extent-to-physical map associated with the donor extent.

22. A computerized system comprising:

a storage server coupled to a storage device, the storage server operative to;

receive a request to remove duplicate data in a storage server;

access a log data container associated with a storage volume of the storage server, the log data container including a plurality of entries, wherein each entry is identified by an extent identifier in a data structure stored in a volume associated with the storage server; and

match an entry in the log data container with another entry in the log data container

determine a donor extent and a recipient extent, and upon determining an external reference count associated with the recipient extent equals a first predetermined value, performing block sharing for the donor extent and the recipient extent, and upon determining if the reference count of the donor extent equals a second predetermined value, freeing the donor extent.

23. A computerized method comprising:

receiving, by a storage server, a request to remove duplicate data in the storage server;

accessing a log data container associated with a storage volume of the storage server, the log data container including a plurality of entries, wherein each entry is identified by an extent identifier in a data structure stored in a volume associated with the storage server; and

matching an extent identifier associated with an entry to an extent identifier associated with another entry in the log data container, updating a reference count and a pointer identifier of the extent identifier associated with the entry, updating a reference count and a pointer identifier of the extent identifier associated with the another entry,

freeing the extent identified by the extent identifier associated with the entry when the reference count of the extent identifier associated with the entry equals the predetermined value, and

freeing the extent identified by the extent identifier associated with the another entry when the reference count of the extent identifier associated with the another entry equals the predetermined value.

24. A non-transitory computer-readable storage medium embodied with executable instructions that cause a processor to perform operations comprising:

receiving a request to remove duplicate data in a storage server;

accessing a log data container associated with a storage volume of the storage server, the log data container including a plurality of entries, wherein each entry is identified by an extent identifier in a data structure stored in a volume associated with the storage server; and

matching an extent identifier associated with an entry to an extent identifier associated with another entry in the log data container, updating a reference count and a pointer identifier of the extent identifier associated with the entry, updating a reference count and a pointer identifier of the extent identifier associated with the another entry,

freeing the extent identified by the extent identifier associated with the entry when the reference count of the extent identifier associated with the entry equals the predetermined value, and

freeing the extent identified by the extent identifier associated with the another entry when the reference count of the extent identifier associated with the another entry equals the predetermined value.

25. A computerized system comprising:

a processor coupled to a memory through a bus; and

instructions executed from the memory by the processor to cause the processor to receive a request to remove duplicate data in a storage server;

access a log data container associated with a storage volume of the storage server, the log data container including a plurality of entries, wherein each entry is identified by an extent identifier in a data structure stored in a volume associated with the storage server; and

if match an extent identifier associated with an entry to an extent identifier associated with another entry in the log data container, update a reference count and a pointer identifier of the extent identifier associated with the entry, update a reference count and a pointer identifier of the extent identifier associated with the another entry,

free the extent identified by the extent identifier associated with the entry when the reference count of the extent identifier associated with the entry equals the predetermined value, and

free the extent identified by the extent identifier associated with the another entry when the reference count of the extent identifier associated with the another entry equals the predetermined value.

26. A computerized system comprising:

a storage server coupled to a storage device, the storage server operative to;

receive a request to remove duplicate data in a storage server;

access a log data container associated with a storage volume of the storage server, the log data container including a plurality of entries, wherein each entry is identified by an extent identifier in a data structure stored in a volume associated with the storage server; and

match an extent identifier associated with an entry to an extent identifier associated with another entry in the log data container, update a reference count and a pointer identifier of the extent identifier associated with the entry, update a reference count and a pointer identifier of the extent identifier associated with the another entry,

free the extent identified by the extent identifier associated with the entry when the reference count of the extent identifier associated with the entry equals the predetermined value, and

free the extent identified by the extent identifier associated with the another entry when the reference count of the extent identifier associated with the another entry equals the predetermined value.