Hardware efficient rabin fingerprints

BACKGROUND

The present disclosure relates to hardware efficient fingerprinting. In particular, the present disclosure relates to a pipelined hardware architecture for computing fingerprints on high throughput data.

As data increases rapidly, identifying and reducing the redundancy in the storage, transmission, and processing of data has become more and more important. One of the common techniques used in identifying redundant data is comparing sketches of data chunks to find duplication or similarity. To illustrate, Rabin fingerprints have proved to be effective and are widely used in the detection of data duplication and similarity. To get a sketch for a data chunk using Rabin fingerprints, the data is scanned using a fixed size window, e.g., 8 bytes long, that rolls one byte ahead every step. The data within the window, called a "shingle," is used to calculate a Rabin fingerprint. This process continues until the chunk of data is finished. During and after the scanning, the fingerprints are sampled to form a sketch for the data chunk. This algorithm is suitable for data de-duplication in off-line data backup and archive applications, but demands intense computation when working at wire speed for streaming data.

With storage devices approaching gigabyte per second throughput and sub-millisecond latency, software approaches to fingerprinting are inadequate for real-time data processing without committing a huge amount of computing power which may impact performance and resource utilization. In view of the foregoing, it may be understood that there may be significant problems and shortcomings associated with current technologies for generating fingerprints and deduplicating data. Examples of incremental computation of fingerprints of overlapping shingles are disclosed in <nplcit id="ncit0001" npl-type="b"><text>JAEHONG MIN ET AL: "Efficient Deduplication Techniques for Modern Backup Operation",IEEE TRANSACTIONS ON COMPUTERS, IEEE SERVICE CENTER, LOS ALAMITOS, CA, US, vol. 60, no. 6, 1 June 2011 (2011-06-01), pages 824-840, XP011354099,ISSN: 0018-9340, DOI: 10.1109/TC.2010.263</text></nplcit> and <patcit id="pcit0001" dnum="US2009024826A1"><text>US 2009/024826 A1</text></patcit> (ZHANG MING [US] ET AL) 22 January 2009 (2009-01-22).

SUMMARY

The present disclosure relates to systems and methods for hardware efficient fingerprinting.

Other implementations of one or more of these aspects include corresponding systems, apparatus, and computer programs, configured to perform the actions of the methods, encoded on computer storage devices. It should be understood that the language used in the present disclosure has been principally selected for readability and instructional purposes, and not to limit the scope of the subject matter disclosed herein.

BRIEF DESCRIPTION OF THE DRAWINGS

The present disclosure is illustrated by way of example, and not by way of limitation in the figures of the accompanying drawings in which like reference numerals are used to refer to similar elements. <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">Figure 1</figref> is a high-level block diagram illustrating an example system including a host, an interconnect, and a number of targets.</li><li><figref idref="f0002">Figure 2A</figref> is a block diagram illustrating an example host configured to implement techniques introduced herein.</li><li><figref idref="f0003">Figure 2B</figref> is a block diagram illustrating an example target configured to implement techniques introduced herein.</li><li><figref idref="f0004">Figure 3</figref> illustrates an example irreducible polynomial, p(x), for use in generating Rabin fingerprints and a set of example equations that result in the fingerprints, according to the techniques described herein.</li><li><figref idref="f0005">Figure 4</figref> is a graphic representation of shingles in a data stream, according to the techniques described herein.</li><li><figref idref="f0005">Figure 5</figref> is a graphic representation of an incremental computation pipeline design, according to the techniques described herein.</li><li><figref idref="f0006">Figure 6</figref> is a flow chart of an example method for incrementally computing fingerprints, according to the techniques described herein.</li><li><figref idref="f0007">Figure 7</figref> is a block diagram illustrating an example fingerprint module, according to the techniques described herein.</li><li><figref idref="f0008">Figure 8A</figref> is a block diagram illustrating an example fingerprint pipeline with split Fresh stages, according to the techniques described herein.</li><li><figref idref="f0009">Figure 8B</figref> is a block diagram illustrating an example parallel pipeline, according to the techniques described herein.</li><li><figref idref="f0010">Figure 9</figref> is a block diagram illustrating an example sampling module, according to the techniques described herein.</li><li><figref idref="f0011">Figure 10</figref> is a block diagram illustrating an example fingerprint selection module, according to the techniques described herein.</li></ul>

DETAILED DESCRIPTION

Systems and methods for implementing a pipelined hardware architecture for computing fingerprints on high throughput streaming data are described below. While the systems, methods of the present disclosure are described in the context of a particular system architecture, it should be understood that the systems, methods and interfaces can be applied to other architectures and organizations of hardware.

Rabin fingerprinting may effectively provide unique signatures or fingerprints to identify duplicate or similar portions of a data chunk. Rabin fingerprints may be generated using a randomly chosen polynomial (p). Given an n-bit message (e.g., m = m₀, m₁, ..., m_n-1), the message may be represented as a polynomial of degree n-1 over the finite field GF(2). A random polynomial p(x) of degree k over GF(2) is then selected, and the fingerprint of the message m is defined to be the remainder after division of f(x) by p(x) over GF(2), which can be viewed as a polynomial of degree k-1 or as a k-bit number. When p(x) is irreducible, two qualities make Rabin fingerprints a good candidate to bin various messages: 1) if two messages are equal, then they will generate the same fingerprints; 2) if two messages are different, the probability that those messages give the same fingerprint is low (e.g., close to 2^-k/2). However, in some embodiments, randomly choosing an irreducible polynomial may not be practical. Particularly, finding a random irreducible polynomial may not be a trivial task in hardware. In some embodiments, a polynomial may be selected that satisfies a few criteria and it may be reused multiple times. The criteria may include: 1) ensuring that collisions for real-world data are as rare as can reasonably be expected; and 2) representation of polynomial leads to efficient implementation based on optimization with respect to a) the number of operations required for fingerprint generation; b) reducing fan-in operations or gates required for fingerprint generation; and c) reducing fan-out operations or gates required for fingerprint generation.

In some embodiments, the techniques may be realized as a method for improving the generation of fingerprinting for efficient deduplication, data integrity verification and security, and other purposes. According to some embodiments, fingerprints may be produced by specialized hardware. A hardware fingerprinting module or component may be implemented in a system to obtain signatures of an incoming data stream. To ensure that fingerprint generation is capable of keeping up with a data stream, an optimized pipelined architecture can be created for a selected polynomial (the selected polynomial used for generation of Rabin fingerprints), which can reduce resource consumption for the design and/or balance resource allocation among one or more pipeline states. This may provide better overall system performance. 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. While the examples herein are directed to Rabin fingerprints, some of the techniques disclosed herein apply also to other types of cyclic redundancy checks and fingerprint computations as well.

<figref idref="f0001">Figure 1</figref> is a high-level block diagram illustrating an example system 100 including a host 102, an interconnect 108, and a number of targets 110, 116, and 122. The host system 102 can take any suitable form, such as, but not limited to, an enterprise server, a database host, a workstation, a personal computer, a mobile phone, a game device, a personal digital assistant (PDA), an email/text messaging device, a digital camera, a digital media <i>(e.g.,</i> MP3) player, a GPS navigation device, a TV system, or the like.

The host system 102 may be communicatively coupled with the targets 110, 116, and 122 through an interconnect 108 and/or a network (not shown). For example, the interconnect 108 may be a PCI express (PCIe) switch and may couple the targets 110, 116, and 122 with the host 102 via a PCIe root complex within the host. Similarly, the interconnect may be a host bus adapter (HBA) that connects the host 102 with targets 110, 116, and 122 via SCSI, Fibre Channel, SAS, SATA, eSATA, or the like. In the example of <figref idref="f0001">Figure 1</figref>, targets 110, 116, and 122 may be any suitable PCIe compatible device, for example, a Non-Volatile Memory express (NVMe) based target. Targets 110, 116, and 122 may each contain respective NVMe controllers 112, 118, and 124, and respective non-volatile storage devices 114, 120, and 126.

According to some embodiments, interface standards other than PCIe may be used for one or more portions of the link between the host 102 and the targets 110, 116, and 122. For example, the links may include, but are not limited to, Serial Advanced Technology Attachment (SATA), Advanced Technology Attachment (ATA), Small Computer System Interface (SCSI), PCI-extended (PCI-X), Fibre Channel, Serial Attached SCSI (SAS), Secure Digital (SD), Embedded Multi-Media Card (EMMC), Universal Flash Storage (UFS), or any other suitable interface standard or combination of interface standards.

The host system 102 and the target device can include additional components, which are not shown in <figref idref="f0001">FIG. 1</figref> to simplify the drawing. Also, in some embodiments, not all of the components shown are present. Further, the various controllers, blocks, and interfaces can be implemented in any suitable fashion. For example, a controller can take the form of one or more of, for example, a microprocessor or processor and a computer-readable medium that stores computer-readable program code <i>(e.g.,</i> software or firmware) executable by the (micro)processor, logic gates, switches, an application specific integrated circuit (ASIC), a programmable logic controller, and an embedded microcontroller.

<figref idref="f0002">Figure 2A</figref> is a block diagram illustrating an example host 200 configured to implement the techniques introduced here. In the example of <figref idref="f0002">Figure 2A</figref>, the host 102 includes a storage interface (I/F) module 202, a processor 204, and a memory 206. The components of the host 102 are communicatively coupled to a bus or software communication mechanism 220 for communication with each other.

The storage interface module 202, as described above, is configured to connect host 102 with targets 110, 116, and 122. For example, the storage interface module 202 may be a PCIe root complex, or the like for sending and/or receiving data from targets 110, 116, and 122.

The processor 204 may include an arithmetic logic unit, a microprocessor, a general purpose controller or some other processor array to perform computations. In some implementations, the processor 204 is a hardware processor having one or more processing cores. The processor 204 is coupled to the bus 220 for communication with the other components. Processor 204 processes data signals and may include various computing architectures including a complex instruction set computer (CISC) architecture, a reduced instruction set computer (RISC) architecture, or an architecture implementing a combination of instruction sets. Although only a single processor is shown in the example of <figref idref="f0002">Figure 2A</figref>, multiple processors and/or processing cores may be included. It should be understood that other processor configurations are possible.

The memory 206 stores instructions and/or data that may be executed by the processor 204. In the illustrated implementation, the memory 206 includes a fingerprint module 212, a deduplication module 214, a reference indexing module 216, and an application 218. The memory 206 is coupled to the bus 220 for communication with the other components of the host 102. The instructions and/or data stored in the memory 206 may include code for performing any and/or all of the techniques described herein. The memory 206 may be, for example, non-transitory memory such as a dynamic random access memory (DRAM) device, a static random access memory (SRAM) device, flash memory or some other memory devices. The memory may further include a file system (not shown) to provide file level data storage and retrieval for the application 218. Additionally, the memory may include a block level driver (not shown) to provide block level data access to a target storage device couple to the host 102 via the storage interface module 202.

The fingerprint module 212 may be configured to compute fingerprints for data blocks according to the techniques disclosed herein. Reference indexing module 216 may access, store, generate, and manage a reference block list with a signature field containing reference fingerprints generated from the reference blocks. Using fingerprints of incoming data blocks, reference indexing module 216 searches for a reference block that matches or is similar to the incoming data block that can be used by the deduplication module for compression of the incoming data block. The deduplication module 214 compares incoming data blocks to indexed reference blocks with matching or similar fingerprints to compress and/or eliminate duplicate data in the incoming data blocks. In one embodiment, if an incoming data block is identical to an existing reference block, the deduplication module 214 stores a reference to the existing data and not the new data itself. In another embodiment, if a new data block is similar to an existing reference block, the deduplication module stores only a delta showing the difference between the data from which the new fingerprint is generated and an existing reference data block from which the existing indexed fingerprint is generated.

<figref idref="f0003">Figure 2B</figref> is a block diagram illustrating an example target (e.g., target 110) configured to implement the techniques introduced here. In the example of <figref idref="f0003">Figure 2B</figref>, the target 110 includes a storage interface (I/F) module 228, a processor 224, a memory 226, a fingerprint module 232, a reference indexing module 236, a deduplication module 234, and a storage device 238. The components of the target 110 are communicatively coupled to a bus or software communication mechanism 240 for communication with each other. The modules in the example of <figref idref="f0003">Figure 2B</figref> may operate as described above with reference to the example of <figref idref="f0002">Figure 2A</figref> except that in <figref idref="f0003">Figure 2B</figref>, the modules may be implemented in hardware, e.g., on a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), or the like. While depicted in the example of <figref idref="f0003">Figure 2B</figref> as distinct modules, it should be understood that one or more of the modules may be implemented on the same hardware or various hardware devices.

In some embodiments, the fingerprint module processes multiple bits in one clock cycle to provide fingerprinting for high data rate applications. Using formal algebra, a single modulo operation (e.g., determining a Rabin fingerprint) can be turned into multiple calculations, each of which is responsible for one bit in the result. In the following examples, we assume the data string is 64 bits resulting in 16-bit Rabin fingerprints. <figref idref="f0004">Figure 3</figref> illustrates an example irreducible polynomial, p(x), for use in generating Rabin fingerprints and a set of 16 equations obtained using formal algebra that result in the fingerprints. In the example of <figref idref="f0004">Figure 3</figref>, (<i>a</i>₀, <i>a</i>₁, ..., <i>a</i>₆₃) represents the input bits and (<i>b</i>₀, <i>b</i>₁<i>,</i> ..., <i>b</i>₁₅) the Rabin fingerprint output.

In one embodiment, to implement one of these equations in hardware, a combinatorial circuit may be used to compute an exclusive-OR (XOR) all of the corresponding input bits. The combination of these 16 circuits is referred to herein as a Fresh function. For the Fresh function in the example of <figref idref="f0004">Figure 3</figref>, the maximum fan-in is 23, and maximum fan-out is 11, and the number of XORs is 261. Among 4080 irreducible polynomials of degree 16, the minimum number of XORs is 261, the minimum maximum fan-in 19, and the minimum maximum fan-out 8. So, when permitted by system design requirements, picking a polynomial presents an optimization opportunity for the hardware design of the Fresh function. Such a scheme is suitable for hardware implementation.

For applications of higher data rate, Rabin fingerprint computations are applied to all "shingles." An example of these shingles is shown in <figref idref="f0005">Figure 4. Figure 4</figref> depicts shingles in a data stream from <i>a</i>₀ to <i>a</i>₇₁, where <i>(X)</i> is the first shingle, and (X) is the second shingle. While the example of <figref idref="f0005">Figure 4</figref> depicts a shift of one byte, shingles can shift in various other multiples of bits. In one embodiment, to treat all of the shingles in real-time, the Fresh function may be replicated over each shingle. However, it is evident that overlapping computations occur in this scheme. The relation between the Rabin fingerprints of <i>A</i> and <i>B</i> can be calculated as: <maths id="math0001" num=""><math display="block"><mi>B</mi><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi><mo>=</mo><mfenced separators=""><mi>V</mi><mo>+</mo><mi>W</mi><mo>⋅</mo><msup><mi>X</mi><mn>56</mn></msup></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></math><img file="EP3051699B1_D0001.tif" /></maths><maths id="math0002" num=""><math display="block"><mi>B</mi><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi><mo>=</mo><mfenced separators=""><mfenced separators=""><mi>U</mi><mo>−</mo><mi>U</mi></mfenced><mo>⋅</mo><mfenced separators=""><msup><mi>X</mi><mrow><mo>−</mo><mn>8</mn></mrow></msup><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></mfenced><mo>+</mo><mi>V</mi><mo>+</mo><mi>W</mi><mo>⋅</mo><msup><mi>X</mi><mn>56</mn></msup></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></math><img file="EP3051699B1_D0002.tif" /></maths><maths id="math0003" num=""><math display="block"><mi>B</mi><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi><mo>=</mo><mfenced separators=""><mo>−</mo><mi>U</mi><mo>⋅</mo><mfenced separators=""><msup><mi>X</mi><mrow><mo>−</mo><mn>8</mn></mrow></msup><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></mfenced></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi><mo>+</mo><mfenced separators=""><mfenced separators=""><msup><mi>X</mi><mrow><mo>−</mo><mn>8</mn></mrow></msup><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></mfenced><mo>⋅</mo><mfenced separators=""><mi>U</mi><mo>+</mo><mi>V</mi><mo>⋅</mo><msup><mi>X</mi><mn>8</mn></msup></mfenced></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi><mo>+</mo><mfenced separators=""><mi>W</mi><mo>⋅</mo><msup><mi>X</mi><mn>56</mn></msup></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></math><img file="EP3051699B1_D0003.tif" /></maths><maths id="math0004" num=""><math display="block"><mi>B</mi><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi><mo>=</mo><mfenced separators=""><mi>W</mi><mo>⋅</mo><msup><mi>X</mi><mn>56</mn></msup><mo>−</mo><mi>U</mi><mo>⋅</mo><mfenced separators=""><msup><mi>X</mi><mrow><mo>−</mo><mn>8</mn></mrow></msup><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></mfenced></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi><mo>+</mo><mfenced separators=""><mfenced separators=""><msup><mi>X</mi><mrow><mo>−</mo><mn>8</mn></mrow></msup><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></mfenced><mo>⋅</mo><mfenced separators=""><mi>U</mi><mo>+</mo><mi>V</mi><mo>⋅</mo><msup><mi>X</mi><mn>8</mn></msup></mfenced></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></math><img file="EP3051699B1_D0004.tif" /></maths><maths id="math0005" num=""><math display="block"><mi>B</mi><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi><mo>=</mo><mfenced separators=""><mi>W</mi><mo>⋅</mo><msup><mi>X</mi><mn>56</mn></msup><mo>−</mo><mi>U</mi><mo>⋅</mo><mfenced separators=""><msup><mi>X</mi><mrow><mo>−</mo><mn>8</mn></mrow></msup><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></mfenced></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi><mo>+</mo><mfenced separators=""><mfenced separators=""><msup><mi>X</mi><mrow><mo>−</mo><mn>8</mn></mrow></msup><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></mfenced><mo>⋅</mo><mfenced separators=""><mi>U</mi><mo>+</mo><mi>V</mi><mo>⋅</mo><msup><mi>X</mi><mn>8</mn></msup></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></math><img file="EP3051699B1_D0005.tif" /></maths><maths id="math0006" num=""><math display="block"><mi mathvariant="italic">Let</mi><mspace width="1ex" /><msup><mi>x</mi><mrow><mo>−</mo><mn>8</mn></mrow></msup><mo>=</mo><msup><mi>X</mi><mrow><mo>−</mo><mn>8</mn></mrow></msup><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></math><img file="EP3051699B1_D0006.tif" /></maths><maths id="math0007" num=""><math display="block"><mi>B</mi><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi><mo>=</mo><mfenced separators=""><mi>W</mi><mo>⋅</mo><msup><mi>X</mi><mn>56</mn></msup><mo>−</mo><mi>U</mi><mo>⋅</mo><msup><mi>x</mi><mrow><mo>−</mo><mn>8</mn></mrow></msup></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi><mo>+</mo><mfenced separators=""><msup><mi>x</mi><mrow><mo>−</mo><mn>8</mn></mrow></msup><mo>⋅</mo><mi>A</mi><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></mfenced><mspace width="1ex" /><mi mathvariant="italic">mod</mi><mspace width="1ex" /><mi>P</mi></math><img file="EP3051699B1_D0007.tif" /></maths>

As can be seen, the fingerprint of the new shingle <i>B(x)</i> is dependent on the fingerprint of the old shingle <i>A(x),</i> the first byte of the old shingle <i>U(x),</i> and the first byte of incoming data <i>W(x),</i> which is the last byte of the new shingle <i>B(x).</i> Thus, the fingerprint calculation of each shingle can be optimized using the fingerprint calculation of the previous shingle.

Using a 64-bit wide data bus and a 64-bit shingle as an example, an incremental computation pipeline design is illustrated in <figref idref="f0005">Figure 5</figref>. The data is drawn from two consecutive clock cycles, for example (<i>a</i>₀, <i>a</i>₁, ..., <i>a</i>₆₃) from the preceding cycle and (<i>a</i>₆₄, <i>a</i>₆₅, ..., <i>a</i>₁₂₇) from the following cycle.

In some embodiments, the techniques disclosed herein include finding an irreducible polynomial for which Rabin fingerprint computation has the least amount of operations for one full computation and several incremental computations of a multiple byte data shingle to group the data in a stream (e.g., seven incremental computations for an eight byte data shingle). The techniques further include computing a Rabin fingerprint incrementally using the selected irreducible polynomial. For example, incremental computation may allow computation of a fingerprint to reuse calculations results from a previous fingerprint calculation of eight bytes. As an example, the fingerprint calculation may calculate the fingerprint of all eight bytes numbered zero to seven, and may shift one byte to the right for a next clock cycle. On the next clock cycle the calculations for bytes zero to seven may be reused and the calculations involving byte eight, and byte zero may be performed. Thus, the fingerprint for the shingle of bytes one to eight may be performed incrementally, reusing the calculations of the prior fingerprint for eight bytes and performing new calculations.

<figref idref="f0006">Figure 6</figref> is a flow chart of an example method for incrementally computing fingerprints. At 602, the first stage in the pipeline, the fingerprint module (e.g., fingerprint module 212 or 232) performs a Fresh function, for example to compute a fingerprint out of (<i>a</i>₀, <i>a</i>₁, ..., <i>a</i>₆₃) as described above. At 604, the fingerprint module performs a Shift function to compute a fingerprint for the next shingle of data, e.g., (<i>a</i>₈, <i>a</i>₉, ..., <i>a</i>₇₁). The Shift function takes as input the evicted byte from the previous shingle (e.g., the first shingle), the absorbed byte from the end of its own shingle, and the result from the previous shingle (e.g., the first shingle) to produce a fingerprint. For example the Shift function utilizes (<i>a</i>₀, <i>a</i>₁, ..., <i>a</i>₇), (<i>a</i>₆₄, <i>a</i>₆₅, ..., <i>a</i>₇₁), and the fingerprint result from the Fresh function of 602. The process continues until 8 fingerprints have been computed (e.g., the Shift function consumes (<i>a</i>₄₈, <i>a</i>₄₉, ..., <i>a</i>₅₅), (<i>a</i>₁₁₂, <i>a</i>₁₁₃, ..., <i>a</i>₁₁₉), and the result from the previous Shift function). At 606, if 8 fingerprints have been computed, the entire data from the following shingle, (<i>a</i>₆₄, <i>a</i>₆₅, ..., <i>a</i>₁₂₇), is treated by Fresh function at 602. Due to the reuse of previous computations, the complexity of the Shift function is lower than that of the Fresh function and therefore consumes less resources when implemented on hardware.

To improve performance, a single irreducible polynomial may be chosen for which a Rabin fingerprint computation has the least amount of operations for one full computation and seven incremental computations. As described above, incremental computation may allow computation of a fingerprint to reuse calculations from seven out of eight bytes of a previous fingerprint calculation. In one implementation, the irreducible polynomial that has one of the least amount of operations over the Fresh function and the seven Shift functions is <i>p</i>(<i>X</i>)=<i>X</i>¹⁶+<i>X</i>¹³+<i>X</i>¹²+<i>X</i>¹¹+1<i>.</i> For the irreducible polynomial described here, the maximum fan-in is 26, the maximum fan-out is 11, and the total number of XORs is 1153.

<figref idref="f0007">Figure 7</figref> is a block diagram illustrating an example fingerprint module 232. The example fingerprint module 232 includes a fingerprint pipeline 702, a number of sampling modules 704a-704n, and a fingerprint selection module 706. In the example single pipeline design depicted in <figref idref="f0007">Figure 7</figref>, data 708 flows from top to bottom through the fingerprint pipeline. The total number of fingerprints generated for a w-byte data chunk according to the techniques disclose here is <i>w-b</i>+1<i>,</i> where <i>b</i> is the size of the shingles. In some embodiments, to reduce the number of fingerprints compared by the deduplication modules, several fingerprints may be chosen from among all of the fingerprints as a sketch to represent the data chunk. In one embodiment, fingerprints with upper N bits having a specific pattern are selected for the sketch since these upper bits in each fingerprint can be considered as randomly distributed. The result of this selection is a good choice in terms of balancing processing speed, similarity detection, elimination of false positives, and resolution.

Fingerprint results produced at every pipeline stage are sent to the right for the corresponding channel sampling modules to process. As the data chunk runs through the pipeline, the fingerprints are sampled and stored in an intermediate buffer (shown in <figref idref="f0010">Figure 9</figref>). After the sampling for a data chunk is done, the fingerprint selection module will choose from the intermediate samples and returns a sketch for the data chunk. In some embodiments, the pipeline is composed of one Fresh function and several following Shift functions, it may very well be that picking a costly Fresh function works better for the whole design in terms of resource utilization. This possibility is due to the likelihood a more cost-efficient Shift function may be obtained in the situation. However, a costly Fresh function may adversely affect the clock rate of the pipeline.

In general, it is desirable to have similar design complexity among all of the stages of a pipelined architecture. As described above with reference to the Shift function, the Fresh function can also be split into multiple Fresh functions. For example, using the same example from the above, the Fresh function can be partitioned into two modules, named Fresh1 and Fresh2 here. Fresh1 treats (<i>a</i>₀, <i>a</i>₁, ..., <i>a</i>₃₈) in <figref idref="f0006">Fig. 6</figref>, while Fresh2 treats (<i>a</i>₃₉, <i>a</i>₄₀, ..., <i>a</i>₆₃). Since Fresh2 also takes the result from Fresh1 as input, the partition of the original Fresh may not be an even split. For example, a suitable partition can be had when Fresh1 treats the first 39 bits and Fresh2 the remaining 25 bits.

Table 1 lists the complexity of the individual split Fresh modules, the combined of the two, and that of the original single Fresh function. While the resource consumption does not change much with the split Fresh modules, the clock rate improves for the split Fresh design. <tables id="tabl0001" num="0001"><table frame="all"><title><b>Table 1</b></title><tgroup cols="5"><colspec colnum="1" colname="col1" colwidth="42mm" /><colspec colnum="2" colname="col2" colwidth="16mm" /><colspec colnum="3" colname="col3" colwidth="16mm" /><colspec colnum="4" colname="col4" colwidth="27mm" /><colspec colnum="5" colname="col5" colwidth="26mm" /><thead><row><entry>Logic Utilization</entry><entry align="center">Fresh1</entry><entry align="center">Fresh2</entry><entry align="center">Split Combined</entry><entry align="center">Original Fresh</entry></row></thead><tbody><row><entry valign="middle">Fan-in</entry><entry align="center" valign="middle">13</entry><entry align="center" valign="middle">11</entry><entry align="center" valign="middle">13</entry><entry align="center" valign="middle">24</entry></row><row><entry valign="middle">Fan-out</entry><entry align="center" valign="middle">7</entry><entry align="center" valign="middle">9</entry><entry align="center" valign="middle">9</entry><entry align="center" valign="middle">11</entry></row><row><entry valign="middle">XORs</entry><entry align="center" valign="middle">139</entry><entry align="center" valign="middle">143</entry><entry align="center" valign="middle">368</entry><entry align="center" valign="middle">362</entry></row><row><entry valign="middle">Maximum clock rate (MHz)</entry><entry align="center" valign="middle">551</entry><entry align="center" valign="middle">542</entry><entry align="center" valign="middle">548</entry><entry align="center" valign="middle">487</entry></row></tbody></tgroup></table></tables>

<figref idref="f0008">Figure 8A</figref> is a block diagram illustrating an example fingerprint pipeline with split Fresh stages. The example fingerprint pipeline includes two split Fresh stages 802 followed by 7 Shift stages 804 and registers 803a, 803b, and 806a-806n after each stage. Assuming a 64-bit input, the two Fresh modules compute the fingerprint for the 8 bytes of data from the preceding clock. The first 7 bytes from the preceding clock and the first 7 bytes from the following clock are passed via pipeline registers 803a and 803b to Shift1 804a where fingerprints are computed for corresponding shingles. Each stage consumes the result of the previous stage, the evicted byte from the preceding clock, and the absorbed byte from the following clock. After the computation is done, the evicted and absorbed bytes are dropped. Therefore, the pipeline registers decrease by two bytes every step forward, until there is no "evicted" and "absorbed" bytes for processing.

Compared to a pipeline with one Fresh unit, the split Fresh design introduces one more stage in the pipeline resulting in one additional clock cycle to the latency of the final result. However, this split Fresh module makes the processing delays of all stages in the pipeline smaller and uniform. If needed for a higher clock rate, the Fresh and Shift modules can be further split into more stages than two. At steady state, a fingerprint (FP_n) is output at every stage to a channel sampling unit, and fingerprint pipeline 702 produces eight fingerprints for every clock cycle.

<figref idref="f0009">Figure 8B</figref> is a block diagram illustrating an example parallel pipeline. The parallel pipeline includes a set of two Fresh functions 812 and 814 and two sets of Shift functions 814a-814n and 824a-824n. When the data bus width exceeds the defined shingle size, multiple pipelines in parallel may be used to produce more fingerprints for one clock cycle. For example, assume the input data comes in at 16 bytes per clock, and the shingle size remains 8 bytes. The data can be divided into low 8 bytes and high 8 bytes, (e.g. L1 and HI). L2 refers to the lower 8 bytes from the following clock. L1, H1, and L2 are fed into the pipelines, where L1 and H1 go through the upper pipeline to produce eight sets of fingerprints, and HI and L2 go through the lower pipeline number 2 to produce another eight sets of fingerprints. The number of the channel sampling units and the size of fingerprint selection module will increase accordingly, and one more clock latency is incurred every time the number of pipeline stages doubles. However, due to the saving of the registers across the multiple pipelines, the resource consumption for the whole design does not increase linearly.

<figref idref="f0010">Figure 9</figref> is a block diagram illustrating an example sampling module 704. As described above, each computed fingerprint may be divided into two parts, an index and a signature. The index may include a few of high order bits and the signature the remaining ones. For example, if the index has <i>m</i> bits, the signatures can be categorized into 2<i>^m</i> bins. Within a bin, the signatures are selected as one candidate for the final sketch. For each sampling module 704, there can be up to 2<i>^m</i> candidates for the final selection.

Continuing the example of 16 fingerprints from above, the sampling module 704 uses four MSBs, i.e. m=4, as an index (e.g., to address the buffer where the selected signatures are stored). The comparator 908 decides whether the minimum or maximum value is sampled into the buffer. The register 906 is used to buffer the incoming signature to compare with the buffer output from the same bin. The wr_bus carries the write enable (wen), the write address (addr), and the data to write (data).

When the buffer read address equals to the buffer write address, a read-after-write (RAW) hazard may occur. To avoid the RAW hazard, a data forwarding unit is designed to control which value to compare with the incoming signature. The XNOR gate 910 checks whether the read address and the write address clash. If they do, and the write enable is active at the moment, the current write value will be forwarded to the comparator. This forwarding is done by the MUX 904 controlled by the output of the AND gate 912. At the end of the channel sampling, each buffer is loaded with candidate signatures for all indices, some of which can be "0" if no index for the buffer entry ever appeared.

<figref idref="f0011">Figure 10</figref> is a block diagram illustrating an example fingerprint selection module 706. When all signatures are settled in the buffer of the channel sampling module, the fingerprint selection module 706 can start to select the signatures to create a sketch of the data chunk. According to Manber's theory, the number of signatures in a sketch may be dependent on the size of the data chunk. In one example embodiment, the fingerprint selection module selects eight signatures out of 16 possible ones. For example, the fingerprint selection module 706 may select indices are 0, 1, 3, 5, 7, 11, 13, and 15, although any subset of signatures may be selected.

Taking advantage of eight concurrently available channel buffers in the signature repository 1004 (e.g., the buffers of the eight channel sampling modules), the fingerprint selection module 706 uses a tree of comparators 1006, 1008 and 1010 to select the fingerprints for the sketch. Adding registers 1016 and 1018 between each level of the tree makes a pipelined fingerprint selection design. The index counter 1002 allows flexibly selecting signatures. For example, the index counter reads out 0, 1, 3, 5, 7, 11, 13, and 15, one at each clock cycle. The readout 1012 serves as the read address to all 8 channel buffers. The signature 1014 for an index returns at the end of the tree.

Systems and methods for implementing a pipelined hardware architecture for computing fingerprints on high throughput streaming data are described below. In the above description, for purposes of explanation, numerous specific details were set forth. It will be apparent, however, that the disclosed technologies can be practiced without any given subset of these specific details. In other instances, structures and devices are shown in block diagram form. For example, the disclosed technologies are described in some implementations above with reference to user interfaces and particular hardware. Moreover, the technologies disclosed above primarily in the context of on line services; however, the disclosed technologies apply to other data sources and other data types (e.g., collections of other resources for example images, audio, web pages).

Reference in the specification to "one implementation" or "an implementation" means that a particular feature, structure, or characteristic described in connection with the implementation is included in at least one implementation of the disclosed technologies. The appearances of the phrase "in one implementation" in various places in the specification are not necessarily all referring to the same implementation.

Some portions of the detailed descriptions above were presented in terms of processes and symbolic representations of operations on data bits within a computer memory. A process can generally be considered a self-consistent sequence of steps leading to a result. The steps may involve physical manipulations of physical quantities. These quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. These signals may be referred to as being in the form of bits, values, elements, symbols, characters, terms, numbers or the like.

These and similar terms can be associated with the appropriate physical quantities and can be considered labels applied to these quantities. Unless specifically stated otherwise as apparent from the prior discussion, it is appreciated that throughout the description, discussions utilizing terms for example "processing" or "computing" or "calculating" or "determining" or "displaying" or the like, may refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

The disclosed technologies may also relate to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may include a general-purpose computer selectively activated or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a computer readable storage medium, for example, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, and magnetic disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, flash memories including USB keys with non-volatile memory or any type of media suitable for storing electronic instructions, each coupled to a computer system bus.

The disclosed technologies can take the form of an entirely hardware implementation, an entirely software implementation or an implementation containing both hardware and software elements. In some implementations, the technology is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc.

Furthermore, the disclosed technologies can take the form of a computer program product accessible from a non-transitory computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system. For the purposes of this description, a computer-usable or computer-readable medium can be any apparatus that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.

A computing system or data processing system suitable for storing and/or executing program code will include at least one processor (e.g., a hardware processor) coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during execution.

Input/output or I/O devices (including but not limited to keyboards, displays, pointing devices, etc.) can be coupled to the system either directly or through intervening I/O controllers.

Network adapters may also be coupled to the system to enable the data processing system to become coupled to other data processing systems or remote printers or storage devices through intervening private or public networks. Modems, cable modems and Ethernet cards are just a few of the currently available types of network adapters.

Finally, the processes and displays presented herein may not be inherently related to any particular computer or other apparatus. Various general-purpose systems may be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear from the description below. In addition, the disclosed technologies were not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the technologies as described herein.

The foregoing description of the implementations of the present techniques and technologies has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the present techniques and technologies to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. In particular, it is explicitly envisaged that features of the various examples and embodiments discussed above may be provided together in any meaningful combination, and the scope of present disclosure is to be interpreted in that manner.

It is intended that the scope of the present techniques and technologies be limited not by this detailed description. The present techniques and technologies may be implemented in other specific forms without departing from the scope of the appended claims. Likewise, the particular naming and division of the modules, routines, features, attributes, methodologies and other aspects are not mandatory or significant, and the mechanisms that implement the present techniques and technologies or its features may have different names, divisions and/or formats. Furthermore, the modules, routines, features, attributes, methodologies and other aspects of the present technology can be implemented as software, hardware, firmware or any combination of the three. Also, wherever a component, an example of which is a module, is implemented as software, the component can be implemented as a standalone program, as part of a larger program, as a plurality of separate programs, as a statically or dynamically linked library, as a kernel loadable module, as a device driver, and/or in every and any other way known now or in the future in computer programming. Additionally, the present techniques and technologies are in no way limited to implementation in any specific programming language, or for any specific operating system or environment. Accordingly, the disclosure of the present techniques and technologies is intended to be illustrative, but not limiting.