System and method for recursive de-duplication
A virtual computing system deduplicates data. The system includes one or more processors, and one or more computer-readable storage media communicably coupled to the one or more processors. The one or more computer-readable storage media has instructions stored thereon that, when executed by the one or more processors, cause the one or more processors to: scan extents for duplicate data chunks; calculate hash values for the extents at different chunk lengths; emit the hash values at the different chunk lengths; identify matching ones of the hash values; and select one or more candidates from among the matching ones of the hash values for dedup.
1. An apparatus comprising a processor having programmed instructions to:
scan a first extent and second extent to identify duplicate data chunks having a first common length;
emit hash values for data chunks in the first extent and the second extent;
identify matching hash values of data chunks in the scanned first and second extents;
upon identifying a match of hash values, emit a key-value to designate data chunks for de-duplication; and
based on a bit map and a list of selected regions for de-duplication using key-value pairs, scan the first extent and the second extent for smaller size chunks of a second common length for de-duplication without having to de-duplicate the selected regions before the scan of smaller size chunks.
2. The apparatus of claim 1 , wherein the processor is further programmed to update the bit map and the list of selected regions with new key-value pairs.
3. The apparatus of claim 2 , using the bit map and the list of selected regions, scan the first extent and the second extent for even smaller size chunks of a third common length for de-duplication without having to de-duplicate the selected regions before the scan of even smaller size chunks; and
updating the bit map and the list of selected regions with new key-value pairs.
4. The apparatus of claim 2 , further comprising skipping candidate data chunks having matching hash values and calculating hash values on remaining data chunks at the second common length.
5. The apparatus of claim 2 , wherein the second common length is calculated from a shift position different from that of the first common length.
6. The apparatus of claim 2 , wherein a maximum number of shifts at the first common length is different from a maximum number of shifts at the second common length.
7. A computer-implemented method comprising:
scanning, by a processor, a first extent and second extent to identify duplicate data chunks having a first common length;
emitting, by the processor, for data chunks in the first extent and the second extent;
identifying, by the processor, matching hash values of data chunks in the scanned first and second extents;
upon identifying a match of hash values, emitting a key-value to designate data chunks for de-duplication; and
based on a bit map and a list of selected regions for de-duplication using key-value pairs, scanning the first extent and the second extent for smaller size chunks of a second common length for de-duplication without having to de-duplicate the selected regions before the scan of smaller size chunks.
8. The method of claim 7 , further comprising
updating the bit map and the list of selected regions with new key-value pairs.
9. The method of claim 8 , using the bit map and the list of selected regions, scanning the first extent and the second extent for even smaller size chunks of a third common length for de-duplication without having to de-duplicate the selected regions before the scan of even smaller size chunks; and
updating the bit map and the list of selected regions with new key-value pairs.
10. The method of claim 8 , further comprising skipping, by the processor, candidate data chunks having matching hash values and calculating hash values on remaining data chunks at the second common length.
11. The method of claim 8 , wherein the second common length is calculated from a shift position different from that of the first common length.
12. The method of claim 8 , wherein a maximum number of shifts at the first common length is different from a maximum number of shifts at the common second length.
13. A non-transitory computer readable medium containing program instructions that, when executed by a processor, cause the processor to perform operations comprising:
scanning a first extent and second extent to identify duplicate data chunks having a first common length;
emitting hash values for data chunks in the first extent and the second extent;
identifying for data chunks in the first extent and the second extent;
upon identifying a match of hash values, emitting a key-value to designate data chunks for de-duplication; and
based on a bit map and a list of selected regions for de-duplication using key-value pairs, scanning the first extent and the second extent for smaller size chunks of a second common length for de-duplication without having to de-duplicate the selected regions before the scan of smaller size chunks.
14. The non-transitory computer readable medium of claim 13 , further comprising
updating the bit map and the list of selected regions with new key-value pairs.
15. The non-transitory computer readable medium of claim 14 , further comprising using the bit map and the list of selected regions, scan the first extent and the second extent for even smaller size chunks of a third common length for de-duplication without having to de-duplicate the selected regions before the scan of even smaller size chunks; and
updating the bit map and the list of selected regions with new key-value pairs.
16. The non-transitory computer readable medium of claim 14 , further comprising skipping candidate data chunks having matching hash values and calculating hash values on remaining data chunks at the second common length.
17. The non-transitory computer readable medium of claim 14 , wherein the second common length is calculated from a shift position different from that of the first common length.
18. The non-transitory computer readable medium of claim 14 , wherein a maximum number of shifts at the first common length is different from a maximum number of shifts at the second common length.