Hardware efficient rabin fingerprints

• US 10,108,659 B2
• Filed: 08/25/2015
• Issued: 10/23/2018
• Est. Priority Date: 01/29/2015
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Guyot, Cyril, Li, Dongyang, Wang, Qingbo, Yang, Ken
• Primary Examiner(s): Ortiz Ditren, Belix M
• Application Number:
  US14/835,618
• Publication Number:
  US 20160224610A1
• Time in Patent Office: 1,155 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: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• 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 method comprising:

selecting an irreducible polynomial;

generating a Fresh function based on the irreducible polynomial and an input polynomial determined by a size of an input message;

computing a first fingerprint for a first shingle of data by;

splitting the Fresh function into a first Fresh portion and a second Fresh portion;

splitting the first shingle of data into a first shingle portion and a second shingle portion;

computing a fingerprint for each of the first shingle portion and the second shingle portion using the first Fresh portion and the second Fresh portion, wherein the second Fresh portion uses the fingerprint for the first shingle portion as an input;

generating a first Shift function, wherein the first Shift function uses the first fingerprint for the first shingle of data as an input; and

computing a second fingerprint for a second shingle of data using the first Shift function.

2. The method of claim 1, wherein generating the Fresh function comprises generating a plurality of equations to compute a remainder of dividing the input polynomial by the irreducible polynomial.

3. The method of claim 1, further comprising:

generating a plurality of Shift functions to follow the first Shift function, wherein each of the plurality of Shift functions uses a fingerprint for a preceding shingle of data, the preceding shingle of data, and a current shingle of data as inputs; and

computing a plurality of fingerprints for a plurality of shingles of data using the plurality of Shift functions.

4. The method of claim 3, wherein the irreducible polynomial is selected to minimize computations over the Fresh and Shift functions.

5. The method of claim 3, further comprising:

sampling the plurality of fingerprints for the plurality of shingles of data;

selecting a subset of the plurality of fingerprints; and

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

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

7. A system comprising:

one or more processors; and

a memory storing instructions, which when executed by the one or more processors, cause the one or more processors to;

select an irreducible polynomial;

generate a Fresh function based on the irreducible polynomial and an input polynomial determined by a size of an input message;

split the Fresh function into a first Fresh portion and a second Fresh portion;

split a first shingle of data into a first shingle portion and a second shingle portion;

compute a fingerprint portion for the first shingle portion using the first Fresh portion;

compute a first fingerprint for the first shingle of data using the second Fresh portion, wherein the second Fresh portion uses the fingerprint portion and the second shingle portion as inputs;

generate a first Shift function, wherein the first Shift function uses the first fingerprint for the first shingle of data as an input; and

compute a second fingerprint for a second shingle of data using the first Shift function.

8. The system of claim 7, wherein to generate the Fresh function, the instructions cause the one or more processors to generate a plurality of equations to compute a remainder of dividing the input polynomial by the irreducible polynomial.

9. The system of claim 7, wherein the instructions cause the one or more processors to:

generate a plurality of Shift functions to follow the first Shift function, wherein each of the plurality of Shift functions uses a fingerprint for a preceding shingle of data, the preceding shingle of data, and a current shingle of data as inputs; and

compute a plurality of fingerprints for a plurality of shingles of data using the plurality of Shift functions.

10. The system of claim 9, wherein the instructions cause the one or more processors to select the irreducible polynomial to minimize computations over the Fresh and Shift functions.

11. The system of claim 9, wherein the instructions cause the one or more processors to:

sample the plurality of fingerprints for the plurality of shingles of data;

select a subset of the plurality of fingerprints; and

create a sketch of a data chunk comprising the plurality of shingles of data, wherein the sketch of the data chunk comprises the subset of the plurality of fingerprints.

12. The system of claim 11, wherein the instructions cause the one or more processors to use the sketch of the data chunk to compress storage of the data chunk.

13. A computer program product comprising a non-transitory computer useable medium storing a computer readable program, wherein the computer readable program, when executed on a computer, causes the computer to:

select an irreducible polynomial;

generate a Fresh function as a first Fresh portion and a second Fresh portion based on the irreducible polynomial and an input polynomial determined by a size of an input message, wherein the Fresh function is configured to;

split a first shingle of data into a first shingle portion and a second shingle portion;

compute a fingerprint portion for the first shingle portion using the first Fresh portion;

compute a first fingerprint for the first shingle of data using the second Fresh portion, wherein the second Fresh portion uses the fingerprint portion and the second shingle portion as inputs; and

generate a first Shift function, wherein the first Shift function uses the first fingerprint for the first shingle of data as an input and is configured to compute a second fingerprint for a second shingle of data.

14. The computer program product of claim 13, wherein to generate the Fresh function, the computer readable program causes the computer to generate a plurality of equations to compute a remainder of dividing the input polynomial by the irreducible polynomial.

15. The computer program product of claim 13, wherein the computer readable program causes the computer to:

generate a plurality of Shift functions to follow the first Shift function, wherein each of the plurality of Shift functions uses a fingerprint for a preceding shingle of data, the preceding shingle of data, and a current shingle of data as inputs and each of the plurality of Shift functions are configure to compute a plurality of fingerprints for a plurality of shingles of data.

16. The computer program product of claim 15, wherein the computer readable program causes the computer to select the irreducible polynomial to minimize computations over the Fresh and Shift functions.

17. The computer program product of claim 15, wherein the computer readable program causes the computer to use the plurality of fingerprints to compress storage of the plurality of shingles of data.