Method and system for implementing high yield de-duplication for computing applications
View Patent ↗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.
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.