METHOD AND SYSTEM FOR IMPLEMENTING HIGH YIELD DE-DUPLICATION FOR COMPUTING APPLICATIONS

• US 20170192712A1
• Filed: 12/30/2015
• Published: 07/06/2017
• Est. Priority Date: 12/30/2015
• Status: Active Grant

• Current Assignee: Nutanix Incorporated
• Original Assignee: Nutanix Incorporated
• Inventors: Kenkre, Baban K., Muthukkaruppan, Kannan
• Granted Patent: US 9,933,971 B2
• Time in Patent Office: Days
• 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 method for performing de-duplication, comprising:

generating 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; and

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

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 the 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 computer usable medium, the computer readable medium having stored thereon a sequence of instructions which, when executed by a processor causes the processor to execute a method for performing de-duplication, the method comprising:

generating 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; and

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

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 the 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 performing de-duplication, comprising:

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

computer readable medium comprising executable code that is executable by the processor for generating 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, and selecting at least some of the plurality of extents from the ordered list of the extents for de-duplication.

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 method 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 the 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.