Advanced deduplication efficiency by candidate sequence selection
Techniques for providing improved advanced deduplication efficiency by candidate sequence selection. The techniques include generating a score for each candidate sequence from among multiple candidate sequences based on dedupe criteria, such as a number of dedupe hints associated with pages in the candidate sequence. The techniques include performing an unaligned dedupe process on the candidate sequence(s) having the highest or higher scores. The dedupe criteria may include a compressibility of each page in the candidate sequence, a bias toward longer matching target sequences, and so on. The techniques include obtaining a correlation between an average score of a number of candidate sequences and a corresponding average unaligned DRR gain, predicting, using the correlation, an expected unaligned DRR gain based on a score for a candidate sequence, and performing an unaligned dedupe process on the candidate sequence based on whether the score and the expected unaligned DRR gain exceed minimum thresholds.
1 . A method comprising:
selecting, from among a plurality of unaligned data elements, two or more candidate sequences of unaligned data elements, the plurality of unaligned data elements being unaligned to native page boundaries of a storage system, and each candidate sequence satisfying predetermined deduplication criteria that includes a minimum candidate sequence length;
obtaining a de-duplicability hint for at least one unaligned data element in at least one of the two or more candidate sequences, the de-duplicability hint indicating that the at least one unaligned data element may be deduplicated based on at least one target data element; and
for a respective candidate sequence from among the two or more candidate sequences that has a highest number of de-duplicability hints, deduplicating the respective candidate sequence based on a target sequence that includes the at least one target data element.
2 . The method of claim 1 comprising:
deferring deduplicating at least one candidate sequence from among the two or more candidate sequences in response to the at least one candidate sequence having fewer de-duplicability hints than the respective candidate sequence.
3 . The method of claim 1 wherein the plurality of unaligned data elements have sequential logical addresses, respectively, and wherein the selecting of the two or more candidate sequences includes selecting the two or more candidate sequences based at least on the sequential logical addresses of the plurality of unaligned data elements.
4 . The method of claim 1 comprising:
generating a score for each candidate sequence from among the two or more candidate sequences based at least on an amount of de-duplicability hints associated with the candidate sequence.
5 . The method of claim 4 comprising:
determining that the score generated for the respective candidate sequence reaches a predetermined minimum score threshold; and
wherein the deduplicating of the respective candidate sequence includes deduplicating the respective candidate sequence in response to the score reaching the predetermined minimum score threshold.
6 . The method of claim 5 comprising:
deferring deduplicating at least one candidate sequence from among the two or more candidate sequences in response to the score generated for the at least one candidate sequence failing to reach the predetermined minimum score threshold.
7 . The method of claim 4 comprising:
obtaining a correlation function that takes the score generated for each candidate sequence as input, and produces an expected data reduction ratio (DRR) gain as output.
8 . The method of claim 7 wherein the deduplicating of the respective candidate sequence includes deduplicating the respective candidate sequence in response to the expected DRR gain exceeding a predetermined minimum DRR gain threshold.
9 . A system comprising:
a memory; and
processing circuitry configured to execute program instructions out of the memory to:
select, from among a plurality of unaligned data elements, two or more candidate sequences of unaligned data elements,
wherein the plurality of unaligned data elements are unaligned to native page boundaries of a storage system, and
wherein each candidate sequence satisfies predetermined deduplication criteria that includes a minimum candidate sequence length;
obtain a de-duplicability hint for at least one unaligned data element in at least one of the two or more candidate sequences,
wherein the de-duplicability hint indicates that the at least one unaligned data element may be deduplicated based on at least one target data element; and
for a respective candidate sequence from among the two or more candidate sequences that has a highest number of de-duplicability hints, deduplicate the respective candidate sequence based on a target sequence that includes the at least one target data element.
10 . The system of claim 9 wherein the processing circuitry is configured to execute the program instructions out of the memory to defer deduplicating at least one candidate sequence from among the two or more candidate sequences in response to the at least one candidate sequence having fewer de-duplicability hints than the respective candidate sequence.
11 . The system of claim 9 wherein the plurality of unaligned data elements have sequential logical addresses, respectively, and wherein the processing circuitry is configured to execute the program instructions out of the memory to select the two or more candidate sequences based at least on the sequential logical addresses of the plurality of unaligned data elements.
12 . The system of claim 9 wherein the processing circuitry is configured to execute the program instructions out of the memory to generate a score for each candidate sequence from among the two or more candidate sequences based at least on an amount of de-duplicability hints associated with the candidate sequence.
13 . The system of claim 12 wherein the processing circuitry is configured to execute the program instructions out of the memory to:
determine that the score generated for the respective candidate sequence reaches a predetermined minimum score threshold; and
deduplicate the respective candidate sequence in response to the score reaching the predetermined minimum score threshold.
14 . The system of claim 13 wherein the processing circuitry is configured to execute the program instructions out of the memory to defer deduplicating at least one candidate sequence from among the two or more candidate sequences in response to the score generated for the at least one candidate sequence failing to reach the predetermined minimum score threshold.
15 . The system of claim 12 wherein the processing circuitry is configured to execute the program instructions out of the memory to obtain a correlation function that takes the score generated for each candidate sequence as input, and produces an expected data reduction ratio (DRR) gain as output.
16 . The system of claim 15 wherein the processing circuitry is configured to execute the program instructions out of the memory to deduplicate the respective candidate sequence in response to the expected DRR gain exceeding a predetermined minimum DRR gain threshold.
17 . The system of claim 9 wherein the deduplication criteria includes an average compression ratio across target data elements of a possible target sequence being at least a desired ratio or percentage.
18 . The system of claim 9 wherein the deduplication criteria includes a bias toward longer possible target sequences.
19 . A computer program product including a set of non-transitory, computer-readable media having program instructions that, when executed by processing circuitry, cause the processing circuitry to perform a method comprising:
selecting, from among a plurality of unaligned data elements, two or more candidate sequences of unaligned data elements, the plurality of unaligned data elements being unaligned to native page boundaries of a storage system, and each candidate sequence satisfying predetermined deduplication criteria that includes a minimum candidate sequence length;
obtaining a de-duplicability hint for at least one unaligned data element in at least one of the two or more candidate sequences, the de-duplicability hint indicating that the at least one unaligned data element may be deduplicated based on at least one target data element; and
for a respective candidate sequence from among the two or more candidate sequences that has a highest number of de-duplicability hints, deduplicating the respective candidate sequence based on a target sequence that includes the at least one target data element.
20 . The computer program product of claim 19 wherein the method comprises:
deferring deduplicating at least one candidate sequence from among the two or more candidate sequences in response to the at least one candidate sequence having fewer de-duplicability hints than the respective candidate sequence.