Vector processing for segmentation hash values calculation

• US 10,459,961 B2
• Filed: 08/02/2017
• Issued: 10/29/2019
• Est. Priority Date: 04/19/2016
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: David, Yehonatan, Toaff, Yair, Hirsch, Michael
• Primary Examiner(s): Hwa, Shyue Jiunn
• Application Number:
  US15/667,267
• Publication Number:
  US 20170344559A1
• Time in Patent Office: 818 Days
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/3867 using instruction pipelines
• CPC Class Codes: H03M 7/3095 using variable length segments
• CPC Class Codes: H03M 7/6023 Parallelization

Abstract

A system for segmenting an input data stream using vector processing, comprising a processor adapted to repeat the following steps throughout an input data stream to create a segmented data stream consisting a plurality of segments: apply a rolling sequence over a sequence of consecutive data items of an input data stream, the rolling sequence includes a subset of consecutive data items of the sequence, calculate concurrently a plurality of partial hash values each by one of a plurality of processing pipelines of the processor, each for a respective one of a plurality of partial rolling sequences each including evenly spaced data items of the subset, determine compliance of each of the plurality of partial hash values with one or more respective partial segmentation criteria and designate the sequence as a variable size segment when at least some of the partial hash values comply with the respective partial segmentation criteria.

Claims

1. A system for block deduplication, comprising:

a non-transitory memory comprising instructions;

a vector processor in communication with the memory, wherein the vector processor is configured to execute the instructions to create, from an input data stream, a segmented data stream comprising a plurality of variable size segments, wherein defining a segment of the plurality of variable size segments comprises;

applying a rolling sequence over a sequence of consecutive data items of the input data stream, the rolling sequence including a subset of consecutive data items of the sequence;

calculating a plurality of partial hash values, wherein the plurality of partial hash values are calculated concurrently by a plurality of vector processing pipelines of the vector processor, wherein each partial hash value corresponds to a respective partial rolling sequence out of a plurality of partial rolling sequences, and wherein each partial rolling sequence is comprised of a plurality of evenly spaced data items of the subset;

determining compliance of each of the plurality of partial hash values with at least one respective partial segmentation criterion; and

designating a cut in the sequence which defines the segment of the sequence in response to at least one of the plurality of partial hash values complying with the at least one respective partial segmentation criterion; and

a deduplication application configured to receive the segmented data stream and perform block deduplication on the segmented data stream;

wherein the at least one respective partial segmentation criterion defines a data pattern; and

wherein determining compliance of each of the plurality of partial hash values with at least one respective partial segmentation criterion comprises;

checking whether a portion of each partial hash value equals a predefined value;

or

checking whether each partial hash value is larger than a predefined value.

2. The system according to claim 1, wherein the vector processor is a single-instruction-multiple data (SIMD) processor.

3. The system according to claim 1, wherein

each of the plurality of partial hash values is calculated as a partial rolling hash value using a respective partial hash value of a respective previous partial rolling sequence, an omitted data item which is omitted from the respective partial rolling sequence, and an added data item which is added to the respective partial rolling sequence.

4. The system according to claim 1, wherein designating the cut in the sequence is further in response to a number of consecutive complying partial hash values calculated for successive subsets of the sequence which comply with the at least one respective partial segmentation criterion exceeding the number of the plurality of partial rolling sequences.

5. The system according to claim 1, wherein the sequence includes a pre-defined minimum number of the consecutive data items.

6. The system according to claim 1, wherein the vector processor is further configured to execute the instructions to facilitate:

designating a cut in the sequence in response to a size of an uncut segment reaching a pre-defined maximum value.

7. A method for block deduplication, the method comprising:

creating, from an input data stream, a segmented data stream comprising a plurality of variable size segments, wherein defining a segment of the plurality of variable size segments comprises;

applying a rolling sequence over a sequence of consecutive data items of the input data stream, the rolling sequence includes a subset of consecutive data items of the sequence;

calculating a plurality of partial hash values, wherein the plurality of partial hash values are calculated concurrently by a plurality of vector processing pipelines of the vector processor, wherein each partial hash value corresponds to a respective partial rolling sequence out of a plurality of partial rolling sequences, and wherein each partial rolling sequence is comprised of a plurality of evenly spaced data items of the subset;

determining compliance of each of the plurality of partial hash values with at least one respective partial segmentation criterion; and

designating a cut in the sequence which defines the segment of the sequence in response to at least one of the plurality of partial hash values complying with the at least one respective partial segmentation criterion; and

performing block deduplication on the segmented data stream;

wherein the at least one respective partial segmentation criterion defines a data pattern; and

wherein determining compliance of each of the plurality of partial hash values with at least one respective partial segmentation criterion comprises;

checking whether a portion of each partial hash value equals a predefined value;

or

checking whether each partial hash value is larger than a predefined value.

8. The method according to claim 7, wherein each of the plurality of partial hash values is calculated as a partial rolling hash value using a respective partial hash value of a respective previous partial rolling sequence, an omitted data item which is omitted from the respective partial rolling sequence, and an added data item which is added to the respective partial rolling sequence.

9. The method according to claim 7, wherein designating the cut in the sequence is further in response to a number of consecutive complying partial hash values calculated for successive subsets of the sequence which comply with the at least one respective partial segmentation criterion exceeding the number of the plurality of partial rolling sequences.

10. The method according to claim 7, wherein the sequence includes a pre-defined minimum number of the consecutive data items.

11. The method according to claim 7, wherein the method further comprises:

designating a cut in the sequence in response to a size of an uncut segment reaching a pre-defined maximum value.

12. A non-transitory computer-readable medium having instructions stored thereon, wherein the instructions, when executed, facilitate:

creating, from an input data stream, a segmented data stream comprising a plurality of variable size segments, wherein defining a segment of the plurality of variable size segments comprises;

applying a rolling sequence over a sequence of consecutive data items of the input data stream, the rolling sequence includes a subset of consecutive data items of the sequence;

calculating a plurality of partial hash values, wherein the plurality of partial hash values are calculated concurrently by a plurality of vector processing pipelines of the vector processor, wherein each partial hash value corresponds to a respective partial rolling sequence out of a plurality of partial rolling sequences, and wherein each partial rolling sequence is comprised of a plurality of evenly spaced data items of the subset;

determining compliance of each of the plurality of partial hash values with at least one respective partial segmentation criterion; and

designating a cut in the sequence which defines the segment of the sequence in response to at least one of the plurality of partial hash values complying with the at least one respective partial segmentation criterion; and

performing block deduplication on the segmented data stream;

wherein the at least one respective partial segmentation criterion defines a data pattern; and

wherein determining compliance of each of the plurality of partial hash values with at least one respective partial segmentation criterion comprises;

checking whether a portion of each partial hash value equals a predefined value;

or

checking whether each partial hash value is larger than a predefined value.