Method and system for implementing high yield de-duplication for computing applications

• US 9,933,971 B2
• Filed: 12/30/2015
• Issued: 04/03/2018
• Est. Priority Date: 12/30/2015
• Status: Active Grant

• Current Assignee: Nutanix Incorporated
• Original Assignee: Nutanix Incorporated
• Inventors: Kenkre, Baban K., Muthukkaruppan, Kannan
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): EDOUARD, JEAN C
• Application Number:
  US14/984,394
• Publication Number:
  US 20170192712A1
• Time in Patent Office: 825 Days
• Field of Search: None
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Disclosed is an improved approach for implementing de-duplication, by selecting data such that the de-duplication efficacy of the storage will be increased without arbitrarily increasing metadata size.

Claims

1. A computer-implemented method for selectively performing data de-duplication in a storage device, comprising:

generating, by a storage management system of the storage device, a non-deduplication reference count for a fingerprint;

generating a de-duplication reference count for the fingerprint;

computing scores for a plurality of extents from the non-deduplication reference count and the de-duplication reference count;

ordering the plurality of extents from the scores to generate an ordered list of extents;

selecting at least some of the plurality of extents from the ordered list of the extents for de-duplication; and

removing copies of data from the at least some of the plurality of extents selected for de-duplication by replacing the copies of data removed with a reference to one or more remaining copies stored on another extent, wherein removing the copies of data from the at least some of the plurality of extents removes a contiguous portion of data from the storage device.

2. The method of claim 1, wherein the scores for the plurality of extents correlates to greater potential savings for data items having greater number of copies.

3. The method of claim 1, wherein the fingerprint corresponds to a SHA1 fingerprint.

4. The method of claim 1, wherein a threshold is established for an amount of data for de-duplication in a given processing cycle.

5. The method of claim 1, wherein a time period is established to periodically perform de-duplication processing.

6. The method of claim 1, wherein the scores are amalgamated on an extent group basis, and the method further comprises:

calculating extent group scores for a plurality of extents;

ordering the plurality of extent groups using the extent group scores; and

selecting at least some of the plurality of extents for de-duplication.

7. The method of claim 6, wherein the extent group scores are calculated as a total of scores of individual extents in an extent group minus fragmentation costs assessed for de-duplication of the individual extents.

8. The method of claim 6, wherein an extent group is filtered to exclude the extent group if (a) a dead space in the extent group exceeds 50% upon de-duplication or (b) if a number of remaining live extents in the extent group after the de-duplication is less than or equal to a number of dead and potential to-be-deduplicated extents.

9. The method of claim 1, wherein all data is fingerprinted and the fingerprints for extents having low yields for de-duplication are subsequently removed.

10. The method of claim 1, wherein map-reduce processing is performed to process de-duplication on multiple distributed processing nodes.

11. A computer program product embodied on a non-transitory computer readable medium, the non-transitory computer readable medium having stored thereon a sequence of instructions which, when executed by a processor causes the processor to execute a method for selectively performing data de-duplication in a storage device, the method comprising:

generating, by a storage management system of the storage device, a non-deduplication reference count for a fingerprint;

generating a de-duplication reference count for the fingerprint;

computing scores for a plurality of extents from the non-deduplication reference count and the de-duplication reference count;

ordering the plurality of extents from the scores to generate an ordered list of extents;

selecting at least some of the plurality of extents from the ordered list of the extents for de-duplication; and

removing copies of data from the at least some of the plurality of extents selected for de-duplication by replacing the copies of data removed with a reference to one or more remaining copies stored on another extent, wherein removing the copies of data from the at least some of the plurality of extents removes a contiguous portion of data from the storage device.

12. The computer program product of claim 11, wherein the scores for the plurality of extents correlates to greater potential savings for data items having greater number of copies.

13. The computer program product of claim 11, wherein the fingerprint corresponds to a SHA1 fingerprint.

14. The computer program product of claim 11, wherein a threshold is established for an amount of data for de-duplication in a given processing cycle.

15. The computer program product of claim 11, wherein a time period is established to periodically perform de-duplication processing.

16. The computer program product of claim 11, wherein the scores are amalgamated on an extent group basis, and the sequence of instructions further comprises:

calculating extent group scores for a plurality of extents;

ordering the plurality of extent groups using the extent group scores; and

selecting at least some of the plurality of extents for de-duplication.

17. The computer program product of claim 16, wherein the extent group scores are calculated as a total of scores of individual extents in an extent group minus fragmentation costs assessed for de-duplication of the individual extents.

18. The computer program product of claim 16, wherein an extent group is filtered to exclude the extent group if (a) a dead space in the extent group exceeds 50% upon de-duplication or (b) if a number of remaining live extents in the extent group after the de-duplication is less than or equal to a number of dead and potential to-be-deduplicated extents.

19. The computer program product of claim 11, wherein all data is fingerprinted and the fingerprints for extents having low yields for de-duplication are subsequently removed.

20. The computer program product of claim 11, wherein map-reduce processing is performed to process de-duplication on multiple distributed processing nodes.

21. A system for selectively performing data de-duplication in a storage device, comprising:

a processor to handle computing instructions to access the storage devices; and

a computer readable medium comprising executable code that is executable by the processor for generating, by a storage management system of the storage device, a non-deduplication reference count for a fingerprint, generating a de-duplication reference count for the fingerprint, computing scores for a plurality of extents from the non-deduplication reference count and the de-duplication reference count;

ordering the plurality of extents from the scores to generate an ordered list of extents;

selecting at least some of the plurality of extents from the ordered list of the extents for de-duplication; and

removing copies of data from the at least some of the plurality of extents selected for de-duplication by replacing the copies of data removed with a reference to one or more remaining copies stored on another extent, wherein removing the copies of data from the at least some of the plurality of extents removes a contiguous portion of data from the storage device.

22. The system of claim 21, wherein the scores for the plurality of extents correlates to greater potential savings for data items having greater number of copies.

23. The system of claim 21, wherein the fingerprint corresponds to a SHA1 fingerprint.

24. The system of claim 21, wherein a threshold is established for an amount of data for de-duplication in a given processing cycle.

25. The system of claim 21, wherein a time period is established to periodically perform de-duplication processing.

26. The system of claim 21, wherein the scores are amalgamated on an extent group basis, and the executable code further performs calculating extent group scores for a plurality of extents, ordering the plurality of extent groups using the extent group scores, and selecting at least some of the plurality of extents for de-duplication.

27. The system of claim 26, wherein the extent group scores are calculated as a total of scores of individual extents in an extent group minus fragmentation costs assessed for de-duplication of the individual extents.

28. The system of claim 26, wherein an extent group is filtered to exclude the extent group if (a) a dead space in the extent group exceeds 50% upon de-duplication or (b) if a number of remaining live extents in the extent group after the de-duplication is less than or equal to a number of dead and potential to-be-deduplicated extents.

29. The system of claim 21, wherein all data is fingerprinted and the fingerprints for extents having low yields for de-duplication are subsequently removed.

30. The system of claim 21, wherein map-reduce processing is performed to process de-duplication on multiple distributed processing nodes.