Granted Patent B1

US 12,530,321 · App. 17/345,772 · Granted Jan 20, 2026

Inventors: Philip Shilane (Newtown, PA); George Mathew (Belmont, CA); Abhinav Duggal (Santa Clara, CA)

Assignee: EMC IP Holding Company LLC

G06F16/1748G06F16/152G06F16/1724

Abstract

Claims (49)

1 . A system for consistently grouping and routing data segments for deduplication, comprising:

one or more processors; and

a non-transitory computer readable medium storing a plurality of instructions, which when executed, cause the one or more processors to:

create a beginning part of an initial sequence of data segments by consecutively grouping sequential data segments from a stream of data until a size of the sequential data segments being grouped is larger than a minimum size, in response to receiving the stream of data;

create a next sequence of data segments by consecutively grouping sequential data segments which are next in the stream of data after the beginning part of the initial sequence of data segments until an aggregate of a size of the sequential data segments, after the beginning part of the initial sequence of data segments, being grouped and the size of the beginning part of the initial sequence of data segments is larger than a maximum size, the next sequence of data segments being distinct from the beginning part of the initial sequence of data segments

determine a feature value for each data segment in the next sequence of data segments;

select a value from the feature values, and a data segment corresponding to the selected value from the next sequence of data segments;

determine an additional feature value for at least one data segment in the next sequence of data segments;

divide the next sequence of data segments at the selected data segment into an ending part of the initial group sequence of data segments and a beginning part of the next group sequence of data segments;

combine the beginning part of the initial group sequence of data segments with the ending part of the initial sequence of data segments from the next sequence of data segments in the stream of data being routed for deduplication, the combination forming an initial group of data segments;

determine a similarity group identifier based on one of the at least one additional feature values,

route, based on the similarity group identifier, one of the initial group of data segments or a group of corresponding fingerprints for deduplication to one of a plurality of deduplication modules that are each uniquely responsible for corresponding groups of data segments associated with a range of similarity group identifiers including the determined similarity group identifier; and

deduplicate, by the one of the plurality of deduplication modules, one of the group of fingerprints or the corresponding initial group of data segments being similar to, but not identical to, the groups of data segments associated with the one of the plurality of deduplication modules.

2 . The system of claim 1 , wherein determining the feature value for each data segment of the second sequence of data segments is based on each result from applying a hash function to each data segment of the second sequence of data segments.

3 . The system of claim 2 , wherein being based on each result from applying the hash function to each data segment of the second sequence of data segments comprises selecting a series of bits from each result as each feature value.

4 . The system of claim 1 , wherein selecting the value from the feature values comprises identifying a mathematical relationship of the selected value to one of a maximal value and a minimal value of the feature values.

5 . The system of claim 1 , wherein determining the additional feature value for the at least one data segment of the second sequence of data segments is based on identifying a result from applying a hash function to the selected data segment and selecting a series of bits from the result, wherein the selected series of bits is mutually exclusive of any series of bits selected for any feature value.

6 . The system of claim 1 , wherein determining the additional feature value for the at least one data segment of the second sequence of data segments is based on each result from applying a hash function to each data segment of the second sequence of data segments, and selecting a series of bits from each result as each additional feature value, and wherein the similarity group identifier being based on one of the at least one additional feature value comprises identifying a mathematical relationship of the one of the at least one additional feature value to one of a maximal value and a minimal value of the at least one additional feature value.

7 . A computer program product comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein to be executed by one or more processors, the program code including instructions to:

create a first sequence of data segments by consecutively grouping sequential data segments from a stream of data until a size of the grouped sequential data segments is larger than a minimum size;

create a second sequence of data segments by consecutively grouping sequential data segments that immediately follow the first sequence of data segments in the data stream until an aggregate of a size of the grouped sequential data segments that immediately follow the first sequence of data segments and the size of the first sequence of data segments is larger than a maximum size, the second sequence of data segments being distinct from the first sequence of data segments;

determine a feature value for each data segment in the second sequence of data segments;

select a value from the feature values, and a data segment corresponding to the selected value from the second sequence of data segments;

determine an additional feature value for at least one data segment in the next sequence of data segments;

divide the next sequence of data segments at the selected data segment into an ending part of the initial group sequence of data segments and a beginning part of the next group sequence of data segments;

combine the beginning part of the initial group sequence of data segments with the ending part of the initial sequence of data segments from the next sequence of data segments in the stream of data being routed for deduplication, the combination forming an initial group of data segments;

determine a similarity group identifier based on one of the at least one additional feature values,

route, based on the similarity group identifier, one of the initial group of data segments or a group of corresponding fingerprints for deduplication to one of a plurality of deduplication modules that are each uniquely responsible for corresponding groups of data segments associated with a range of similarity group identifiers including the determined similarity group identifier; and

deduplicate, by the one of the plurality of deduplication modules, one of the group of fingerprints or the corresponding initial group of data segments being similar to, but not identical to, the groups of data segments associated with the one of the plurality of deduplication modules.

8 . The computer program product of claim 7 , wherein determining the feature value for each data segment of the second sequence of data segments is based on each result from applying a hash function to each data segment of the second sequence of data segments.

9 . The computer program product of claim 8 , wherein being based on each result from applying the function to each data segment of the second sequence of data segments comprises selecting a series of bits from each result as each feature value.

10 . The computer program product of claim 7 , wherein selecting the value from the feature values comprises identifying a mathematical relationship of the selected value to one of a maximal value and a minimal value of the feature values.

11 . The computer program product of claim 7 , wherein determining the additional feature value for the at least one data segment of the second sequence of data segments is based on identifying a result from applying a hash function to the selected data segment and selecting a series of bits from the result, wherein the selected series of bits is mutually exclusive of any series of bits selected for any feature value.

12 . The computer program product of claim 7 , wherein determining the additional feature value for the at least one data segment of the second sequence of data segments is based on each result from applying a hash function to each data segment of the second sequence of data segments, and selecting a series of bits from each result as each additional feature value, and wherein the similarity group identifier being based on one of the at least one additional feature value comprises identifying a mathematical relationship of the one of the at least one additional feature value to one of a maximal value and a minimal value of the at least one additional feature value.

13 . A computer-implemented method for consistently grouping and routing data segments for deduplication, comprising:

creating a first sequence of data segments by consecutively grouping sequential data segments from a stream of data until a size of the grouped sequential data segments larger than a minimum size;

creating a second sequence of data segments by consecutively grouping sequential data segments that immediately follow the first sequence of data segments in the data stream until an aggregate of a size of the grouped sequential data segments that immediately follow the first sequence of data segments and the size of the first sequence of data segments is larger than a maximum size, the second sequence of data segments being distinct from the first sequence of data segments;

determining a feature value for each data segment in the second sequence of data segments;

selecting a value from the feature values, and a data segment corresponding to the selected value from the second sequence of data segments;

determining an additional feature value for at least one data segment in the next sequence of data segments;

dividing the next sequence of data segments at the selected data segment into an ending part of the initial group sequence of data segments and a beginning part of the next group sequence of data segments;

combining the beginning part of the initial group sequence of data segments with the ending part of the initial sequence of data segments from the next sequence of data segments in the stream of data being routed for deduplication, the combination forming an initial group of data segments;

determining a similarity group identifier based on one of the at least one additional feature values,

routing, based on the similarity group identifier, one of the initial group of data segments or a group of corresponding fingerprints for deduplication to one of a plurality of deduplication modules that are each uniquely responsible for corresponding groups of data segments associated with a range of similarity group identifiers including the determined similarity group identifier; and

deduplicating, by the one of the plurality of deduplication modules, one of the group of fingerprints or the corresponding initial group of data segments being similar to, but not identical to, the groups of data segments associated with the one of the plurality of deduplication modules.

14 . The computer-implemented method of claim 13 , wherein determining the feature value for each data segment of the second sequence of data segments is based on each result from applying a hash function to each data segment of the second sequence of data segments, and then selecting a series of bits from each result as each feature value.

15 . The computer-implemented method of claim 13 , wherein selecting the value from the feature values comprises identifying a mathematical relationship of the selected value to one of a maximal value and a minimal value of the feature values.

16 . The computer-implemented method of claim 13 , wherein determining the additional feature value for the at least one data segment of the second sequence of data segments is based on identifying a result from applying a hash function to the selected data segment and selecting a series of bits from the result, wherein the selected series of bits is mutually exclusive of any series of bits selected for any feature value.

17 . The computer-implemented method of claim 13 , wherein determining the additional feature value for the at least one data segment of the second sequence of data segments is based on each result from applying a hash function to each data segment of the second sequence of data segments, and selecting a series of bits from each result as each additional feature value, and wherein the similarity group identifier being based on one of the at least one additional feature value comprises identifying a mathematical relationship of the one of the at least one additional feature value to one of a maximal value and a minimal value of the at least one additional feature value.

Assignments (8)

References Cited (3)