Hardware efficient fingerprinting

• US 10,078,646 B2
• Filed: 08/25/2015
• Issued: 09/18/2018
• Est. Priority Date: 01/29/2015
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: HGST Netherlands B.V. (Western Digital Corporation)
• Inventors: Bandic, Zvonimir, Guyot, Cyril, Li, Dongyang, Narasimha, Ashwin, Wang, Qingbo, Yang, Ken
• Primary Examiner(s): Ortiz Ditren, Belix M
• Application Number:
  US14/835,622
• Publication Number:
  US 20160224595A1
• Time in Patent Office: 1,120 Days
• Field of Search: None
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: H03M 7/3091 Data deduplication
• CPC Class Codes: H03M 7/3093 using fixed length segments
• CPC Class Codes: H03M 7/6029 Pipelining

Abstract

An approach for fingerprinting large data objects at the wire speed has been disclosed. The techniques include Fresh/Shift pipelining, split Fresh, optimization, online channel sampling, and pipelined selection. The architecture can also be replicated to work in parallel for higher system throughput. Fingerprinting may provide an efficient mechanism for identifying duplication in a data stream, and deduplication based on the identified fingerprints may provide reduced storage costs, reduced network bandwidth consumption, reduced processing time and other benefits. In some embodiments, fingerprinting may be used to ensure or verify data integrity and may facilitate detection of corruption or tampering. An efficient manner of generating fingerprints (either via hardware, software, or a combination) may reduce a computation load and/or time required to generate fingerprints.

Claims

1. A system comprising:

a fingerprint pipeline configured to compute fingerprints for a data chunk, the fingerprint pipeline comprising;

a Fresh module configured to;

split a first shingle of data from the data chunk into a plurality of portions;

perform a first Fresh function on a first portion of the plurality of portions; and

perform a second Fresh function on a second portion of the plurality of portions using a result of the first Fresh function to compute a first fingerprint from the first shingle of data from the data chunk;

a first Shift module communicatively coupled with an output of the Fresh module, wherein the first Shift module is configured to compute a second fingerprint using the first fingerprint, the first shingle of data from the data chunk, and a second shingle of data from the data chunk;

a plurality of sampling modules communicatively coupled with the fingerprint pipeline, the plurality of sampling modules configured to sample candidate fingerprints for generating a sketch for the data chunk; and

a fingerprint selection module communicatively coupled with the plurality of sampling modules, the fingerprint selection module configured to select a plurality of fingerprints to create a sketch of the data chunk.

2. The system of claim 1, wherein the fingerprint pipeline further comprises:

a second Shift module communicatively coupled with an output of the first Shift module, wherein the second Shift module is configured to compute a third fingerprint using the second fingerprint, the second shingle of data from the data chunk, and a third shingle of data from the data chunk.

3. The system of claim 1, wherein the fingerprint pipeline further comprises:

a plurality of pipelines operating in parallel.

4. The system of claim 1, wherein one or more of the fingerprint pipeline, the plurality of sampling modules, and the fingerprint selection module are implemented using a field programmable gate array.

5. The system of claim 1, further comprising a deduplication module coupled with the fingerprint selection module, the deduplication module configured to use the sketch of the data chunk to compress storage of the data chunk.

6. The system of claim 1, further comprising:

a non-volatile memory express (NVMe) controller, wherein the NVMe controller includes one or more of the fingerprint pipeline, the plurality of sampling modules, and the fingerprint selection module.

7. The system of claim 1, wherein the fingerprints for the data chunk data are Rabin fingerprints based on an irreducible polynomial.

8. A method comprising:

receiving a data chunk including a plurality of shingles of data;

performing a Fresh function to compute a first fingerprint for a first shingle of data of the plurality of shingles of data k

splitting the first shingle of data into a plurality of portions;

performing a first Fresh function on a first portion of the plurality of portions; and

performing a second Fresh function on a second portion of the plurality of portions using a result of the first Fresh function; and

performing a Shift function to compute a second fingerprint for a second shingle of data of the plurality of shingles of data, wherein the Shift function uses the first fingerprint for the first shingle of data as an input.

9. The method of claim 8, further comprising:

performing a plurality of Shift functions to compute a plurality of fingerprints for the plurality of shingles of data, wherein each of the plurality Shift functions uses a fingerprint for a preceding shingle of data, a preceding shingle of data, and a current shingle of data as inputs.

10. The method of claim 9, further comprising:

sampling the plurality of fingerprints;

selecting a subset of the plurality of fingerprints; and

creating a sketch of the data chunk including the plurality of shingles of data, wherein the sketch of the data chunk comprises the subset of the plurality of fingerprints.

11. The method of claim 10, further comprising using the sketch of the data chunk to compress storage of the data chunk.

12. The method of claim 8, wherein the first fingerprint for the first shingle of data and the second fingerprint for the second shingle of data are Rabin fingerprints based on an irreducible polynomial.

13. The method of claim 12, further comprising:

selecting the irreducible polynomial to minimize computations over the Fresh and Shift functions.

14. A method comprising:

performing a plurality of Fresh functions in parallel to compute a first plurality of fingerprints for a first shingle of data, wherein each Fresh function comprises;

splitting the first shingle of data into a plurality of portions;

performing a first Fresh function on a first portion of the plurality of portions; and

performing a second Fresh function on a second portion of the plurality of portions using a result of the first Fresh function; and

performing a first plurality of Shift functions in parallel to compute a second plurality of fingerprints for a second shingle of data, wherein the first plurality of Shift functions use the first plurality of fingerprints for the first shingle of data, a plurality of portions of the first shingle of data, and a plurality of portions of the second shingle of data as inputs.

15. The method of claim 14, further comprising:

performing a second plurality of Shift functions in parallel to compute a third plurality of fingerprints for a third shingle of data, wherein each of the plurality Shift functions uses the second plurality of fingerprints for the second shingle of data, a plurality of portions of the second shingle of data, and a plurality of portions of the third shingle of data as inputs.

16. The method of claim 15, further comprising:

sampling the first plurality of fingerprints, the second plurality of fingerprints, and the third plurality of fingerprints;

selecting a subset of the first plurality of fingerprints, the second plurality of fingerprints, and the third plurality of fingerprints; and

creating a sketch of a data chunk including a plurality of data shingles, wherein the sketch of the data chunk comprises the subset of the first plurality of fingerprints, the second plurality of fingerprints, and the third plurality of fingerprints.

17. The method of claim 16, further comprising using the sketch of the data chunk to compress storage of the data chunk.

18. The method of claim 14, wherein the first plurality of fingerprints for the first shingle of data and the second plurality of fingerprints for the second shingle of data are Rabin fingerprints based on an irreducible polynomial.