Inline wire speed deduplication system

1. A device for inline data deduplication, comprising:

one or more input ports for receiving an input data stream containing duplicates;

one or more output ports for providing a data deduplicated output data stream; and

an inline data deduplication engine coupled to said one or more input ports and said one or more output ports to process input data containing duplicates into output data which is data deduplicated, said inline data deduplication engine having an inline data deduplication bandwidth of at least 4 Gigabytes per second,

wherein said inline data deduplication engine comprises:

frame memory comprising at least some of the received input data stream and at least some output data provided for inclusion in the output data stream;

chunking logic for subdividing input data extracted from the input data stream into input data chunks;

chunk identifier logic for generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, wherein each chunk identifier is uniquely associated with a particular sequence of chunk data; and

one or more data compression engines each comprising:

a plurality of hash memories each associated with a different lane of a plurality of lanes, and each lane comprising data bytes from at least one of the input data chunks;

an array comprising array elements each comprising a plurality of validity bits, wherein each validity bit within an array element corresponds to a different lane of the plurality of lanes;

control logic, coupled to the plurality of hash memories and the array, that initiates a read of a hash memory entry if a corresponding validity bit indicates that said entry is valid; and

an encoder, coupled to the plurality of hash memories and the control logic, that compresses at least the data bytes for the lane associated with the hash memory comprising the valid entry if said valid entry comprises data that matches the lane data bytes;

wherein the one or more data compression engines each operates at least at a rate that is the lower of the bandwidth of an input port of the one or more input ports from which uncompressed data is received and the bandwidth of an output port of the one or more output ports to which compressed data is directed.

2. A device for inline data deduplication, comprising:

one or more input ports for receiving an input data stream containing duplicates;

one or more output ports for providing a data deduplicated output data stream; and

an inline data deduplication engine coupled to said one or more input ports and said one or more output ports to process input data containing duplicates into output data which is data deduplicated, said inline data deduplication engine having an inline data deduplication bandwidth of at least 4 Gigabytes per second,

wherein said inline data deduplication engine comprises:

frame memory comprising at least some of the received input data stream and at least some output data provided for inclusion in the output data stream;

chunking logic for subdividing input data extracted from the input data stream into input data chunks;

chunk identifier logic for generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, wherein each chunk identifier is uniquely associated with a particular sequence of chunk data;

Bloom filter logic for identifying as non-matching data chunks at least some input data chunks that do not match any previously processed data chunks already provided as part of the output data stream;

Bloom filter array memory for storing Bloom filter status bits; and

processing logic for identifying non-matching data chunks not already identified by the Bloom filter, and for controlling the inclusion within the output data stream of the non-matching data chunks identified by the Bloom filter and the processing logic;

wherein the identification of non-matching data chunks by the Bloom filter and the processing logic is based at least in part on the chunk identifier.

3. The device of claim 2 ,

wherein said inline data deduplication engine further comprises a Bloom filter cache memory comprising at least some of the Bloom filter status bits most recently accessed by the Bloom filter logic; and

wherein if a first input/output (I/O) operation to access a first Bloom filter status bit stored within the Bloom filter cache memory is followed by a second I/O operation to access the same first Bloom filter status bit or to access a second Bloom filter status bit stored within the Bloom filter cache memory, the second I/O operation will not be held off pending completion of the first I/O operation.

4. A device for inline data deduplication, comprising:

one or more input ports for receiving an input data stream containing duplicates;

one or more output ports for providing a data deduplicated output data stream; and

an inline data deduplication engine coupled to said one or more input ports and said one or more output ports to process input data containing duplicates into output data which is data deduplicated, said inline data deduplication engine having an inline data deduplication bandwidth of at least 4 Gigabytes per second,

wherein said inline data deduplication engine comprises:

frame memory comprising at least some of the received input data stream and at least some output data provided for inclusion in the output data stream;

chunking logic for subdividing input data extracted from the input data stream into input data chunks;

chunk identifier logic for generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, wherein each chunk identifier is uniquely associated with a particular sequence of chunk data;

a content addressable storage (CAS) hash index table, at least part of the chunk identifier being used as an index to locate a pointer within the CAS hash index table; and

wherein the pointer, if valid, points to groups of one or more CAS entries corresponding to the index, each of the one or more CAS entries comprising a second pointer to a metadata record describing a non-matching data chunk that does not match any previously processed data chunks already provided as part of the output data stream, and further comprising any remaining chunk identifier bits not used as the index.

5. The device of claim 4 , wherein a matching input data chunk is identified if a CAS entry is found that corresponds to an index derived from the chunk identifier of the matching input data chunk, and that includes remaining chunk identifier bits that match the corresponding remaining chunk identifier bits of the matching input data chunk.

6. The device of claim 4 ,

wherein said inline data deduplication engine further comprises CAS cache memory; and

wherein at least some of the one or more CAS entries most recently accessed by said inline data deduplication engine are stored within the CAS cache memory.

7. The device of claim 6 ,

wherein a collection of adjacent groups of CAS entries are read into the CAS cache memory; and

wherein at least some of the CAS entries read into the CAS cache memory describe related non-matching data chunks.

8. The device of claim 4 ,

wherein said inline data deduplication engine further comprises metadata cache memory;

wherein at least some metadata records most recently accessed by said inline data deduplication engine are stored in the metadata cache as part of one or more metadata pages; and

wherein at least some metadata records within one of the one or more metadata pages describe related non-matching data chunks.

9. A data deduplication method performed by an inline deduplication engine, the method comprising:

receiving an input data stream containing duplicates;

providing a data deduplicated output data stream;

processing input data containing duplicates into output data which is data deduplicated, said processing being performed at a rate of at least 4 Gigabytes per second;

subdividing input data extracted from an input data stream into input data chunks;

generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, each chunk identifier uniquely associated with a particular sequence of chunk data;

associating a plurality of hash memories each with a different lane of a plurality of lanes, each lane comprising data bytes from at least one of the input data chunks;

initiating a read of a hash memory entry if a corresponding validity bit indicates that said entry is valid; and

compressing at least the data bytes for the lane associated with the hash memory comprising the valid entry if said valid entry comprises data that matches the lane data bytes, the compressing performed at least at a rate that is the lower of the bandwidth of an input port of the one or more input ports from which uncompressed data is received and the bandwidth of an output port of the one or more output ports to which compressed data is directed.

10. A data deduplication method performed by an inline deduplication engine, the method comprising:

receiving an input data stream containing duplicates;

providing a data deduplicated output data stream;

processing input data containing duplicates into output data which is data deduplicated, said processing being performed at a rate of at least 4 Gigabytes per second;

subdividing input data extracted from an input data stream into input data chunks;

generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, each chunk identifier uniquely associated with a particular sequence of chunk data;

using a Bloom filter to identify as non-matching data chunks at least some input data chunks that do not match any previously processed data chunks already provided as part of the output data stream;

updating Bloom filter status bits;

identifying the non-matching data chunks not already identified by the Bloom filter;

basing identification of non-matching data chunks at least in part on the chunk identifier; and

including within the output data stream the non-matching data chunks.

11. The method of claim 10 , further comprising:

accessing a first Bloom filter status bit within a Bloom filter cache with a first I/O operation;

accessing the first Bloom filter status bit, or a second Bloom filter status bit stored in the Bloom filter cache, with a second I/O operation; and

allowing the second I/O operation regardless of the completion status of the first I/O operation.

12. A data deduplication method performed by an inline deduplication engine, the method comprising:

receiving an input data stream containing duplicates;

providing a data deduplicated output data stream;

processing input data containing duplicates into output data which is data deduplicated, said processing being performed at a rate of at least 4 Gigabytes per second;

subdividing input data extracted from an input data stream into input data chunks;

generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, each chunk identifier uniquely associated with a particular sequence of chunk data;

using at least part of the chunk identifier as an index to locate a pointer within a content addressable storage (CAS) hash index table, wherein a valid pointer addresses groups of one or more CAS entries comprising a second pointer to a metadata record describing a non-matching data chunk that does not match any previously processed data chunks already provided as part of the output data stream, and further comprising any remaining chunk identifier bits not used as the index.

13. The method of claim 12 , further comprising identifying a matching input data chunk if a CAS entry is found that corresponds to an index derived from the chunk identifier of the matching input data chunk, and that includes remaining chunk identifier bits that match the corresponding remaining chunk identifier bits of the matching input data chunk.

14. The method of claim 12 , further comprising reading a collection of adjacent groups of CAS entries of the one or more CAS entries into a CAS cache, wherein at least some of the CAS entries read into the CAS cache describe related non-matching data chunks.

15. The method of claim 12 , further comprising storing at least some metadata records in a metadata cache, wherein the at least some metadata records describe related non-matching data chunks and are part of one or more metadata pages.

16. A device for inline data deduplication, comprising:

one or more input ports for receiving an input data stream containing duplicates;

one or more output ports for providing a data deduplicated output data stream;

an inline data deduplication engine coupled to said one or more input ports and said one or more output ports to process input data containing duplicates into output data which is data deduplicated, said inline data deduplication engine having an inline data deduplication bandwidth of at least 400 Megabytes per second per input port;

wherein said inline data deduplication engine comprises:

frame memory comprising at least some of the received input data stream and at least some output data provided for inclusion in the output data stream;

chunking logic for subdividing input data extracted from the input data stream into input data chunks;

chunk identifier logic for generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, wherein each chunk identifier is uniquely associated with a particular sequence of chunk data; and

one or more data compression engines each comprising:

a plurality of hash memories each associated with a different lane of a plurality of lanes, and each lane comprising data bytes from at least one of the input data chunks;

an array comprising array elements each comprising a plurality of validity bits, wherein each validity bit within an array element corresponds to a different lane of the plurality of lanes;

control logic, coupled to the plurality of hash memories and the array, that initiates a read of a hash memory entry if a corresponding validity bit indicates that said entry is valid; and

an encoder, coupled to the plurality of hash memories and the control logic, that compresses at least the data bytes for the lane associated with the hash memory comprising the valid entry if said valid entry comprises data that matches the lane data bytes;

wherein the one or more data compression engines each operates at least at a rate that is the lower of the bandwidth of an input port of the one or more input ports from which uncompressed data is received and the bandwidth of an output port of the one or more output ports to which compressed data is directed.

17. A device for inline data deduplication, comprising:

one or more input ports for receiving an input data stream containing duplicates;

one or more output ports for providing a data deduplicated output data stream;

an inline data deduplication engine coupled to said one or more input ports and said one or more output ports to process input data containing duplicates into output data which is data deduplicated, said inline data deduplication engine having an inline data deduplication bandwidth of at least 400 Megabytes per second per input port;

wherein said inline data deduplication engine comprises:

frame memory comprising at least some of the received input data stream and at least some output data provided for inclusion in the output data stream;

chunking logic for subdividing input data extracted from the input data stream into input data chunks;

chunk identifier logic for generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, wherein each chunk identifier is uniquely associated with a particular sequence of chunk data;

Bloom filter logic for identifying as non-matching data chunks at least some input data chunks that do not match any previously processed data chunks already provided as part of the output data stream;

Bloom filter array memory for storing Bloom filter status bits; and

processing logic for identifying non-matching data chunks not already identified by the Bloom filter, and for controlling the inclusion within the output data stream of the non-matching data chunks identified by the Bloom filter and the processing logic;

wherein the identification of non-matching data chunks by the Bloom filter and the processing logic is based at least in part on the chunk identifier.

18. The device of claim 17 ,

wherein said inline data deduplication engine further comprises a Bloom filter cache memory comprising at least some of the Bloom filter status bits most recently accessed by the Bloom filter logic; and

wherein if a first input/output (I/O) operation to access a first Bloom filter status bit stored within the Bloom filter cache memory is followed by a second I/O operation to access the same first Bloom filter status bit or to access a second Bloom filter status bit stored within the Bloom filter cache memory, the second I/O operation will not be held off pending completion of the first I/O operation.

19. A device for inline data deduplication, comprising:

one or more input ports for receiving an input data stream containing duplicates;

one or more output ports for providing a data deduplicated output data stream;

an inline data deduplication engine coupled to said one or more input ports and said one or more output ports to process input data containing duplicates into output data which is data deduplicated, said inline data deduplication engine having an inline data deduplication bandwidth of at least 400 Megabytes per second per input port;

wherein said inline data deduplication engine comprises:

frame memory comprising at least some of the received input data stream and at least some output data provided for inclusion in the output data stream;

chunking logic for subdividing input data extracted from the input data stream into input data chunks;

chunk identifier logic for generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, wherein each chunk identifier is uniquely associated with a particular sequence of chunk data;

a content addressable storage (CAS) hash index table, at least part of the chunk identifier being used as an index to locate a pointer within the CAS hash index table; and

wherein the pointer, if valid, points to groups of one or more CAS entries corresponding to the index, each of the one or more CAS entries comprising a second pointer to a metadata record describing a non-matching data chunk that does not match any previously processed data chunks already provided as part of the output data stream, and further comprising any remaining chunk identifier bits not used as the index.

20. The device of claim 19 , wherein a matching input data chunk is identified if a CAS entry is found that corresponds to an index derived from the chunk identifier of the matching input data chunk, and that includes remaining chunk identifier bits that match the corresponding remaining chunk identifier bits of the matching input data chunk.

21. The device of claim 19 ,

wherein said inline data deduplication engine further comprises CAS cache memory; and

wherein at least some of the one or more CAS entries most recently accessed by said inline data deduplication engine are stored within the CAS cache memory.

22. The device of claim 21 ,

wherein a collection of adjacent groups of CAS entries are read into the CAS cache memory; and

wherein at least some of the CAS entries read into the CAS cache memory describe related non-matching data chunks.

23. The device of claim 19 ,

wherein said inline data deduplication engine further comprises metadata cache memory;

wherein at least some metadata records most recently accessed by said inline data deduplication engine are stored in the metadata cache as part of one or more metadata pages; and

wherein at least some metadata records within one of the one or more metadata pages describe related non-matching data chunks.

24. A data deduplication method performed by an inline data deduplication engine, the method comprising:

receiving an input data stream containing duplicates;

providing a data deduplicated output data stream;

processing input data containing duplicates into output data which is data deduplicated, said processing being performed at a rate of at least 400 Megabytes per second per input port of the inline data deduplication engine;

subdividing input data extracted from an input data stream into input data chunks;

generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, each chunk identifier uniquely associated with a particular sequence of chunk data;

associating a plurality of hash memories each with a different lane of a plurality of lanes, each lane comprising data bytes from at least one of the input data chunks;

initiating a read of a hash memory entry if a corresponding validity bit indicates that said entry is valid; and

compressing at least the data bytes for the lane associated with the hash memory comprising the valid entry if said valid entry comprises data that matches the lane data bytes, the compressing performed at least at a rate that is the lower of the bandwidth of an input port of the one or more input ports from which uncompressed data is received and the bandwidth of an output port of the one or more output ports to which compressed data is directed.

25. A data deduplication method performed by an inline data deduplication engine, the method comprising:

receiving an input data stream containing duplicates;

providing a data deduplicated output data stream;

processing input data containing duplicates into output data which is data deduplicated, said processing being performed at a rate of at least 400 Megabytes per second per input port of the inline data deduplication engine;

subdividing input data extracted from an input data stream into input data chunks;

generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, each chunk identifier uniquely associated with a particular sequence of chunk data;

using a Bloom filter to identify as non-matching data chunks at least some input data chunks that do not match any previously processed data chunks already provided as part of the output data stream;

updating Bloom filter status bits;

identifying the non-matching data chunks not already identified by the Bloom filter;

basing identification of non-matching data chunks at least in part on the chunk identifier; and

including within the output data stream the non-matching data chunks.

26. The method of claim 25 , further comprising:

accessing a first Bloom filter status bit within a Bloom filter cache with a first I/O operation;

accessing the first Bloom filter status bit, or a second Bloom filter status bit stored in the Bloom filter cache, with a second I/O operation; and

allowing the second I/O operation regardless of the completion status of the first I/O operation.

27. A data deduplication method performed by an inline data deduplication engine, the method comprising:

receiving an input data stream containing duplicates;

providing a data deduplicated output data stream;

processing input data containing duplicates into output data which is data deduplicated, said processing being performed at a rate of at least 400 Megabytes per second per input port of the inline data deduplication engine;

subdividing input data extracted from an input data stream into input data chunks;

generating a chunk identifier for each of the input data chunks based at least in part upon data within the input data chunk, each chunk identifier uniquely associated with a particular sequence of chunk data;

using at least part of the chunk identifier as an index to locate a pointer within a content addressable storage (CAS) hash index table, wherein a valid pointer addresses groups of one or more CAS entries comprising a second pointer to a metadata record describing a non-matching data chunk that does not match any previously processed data chunks already provided as part of the output data stream, and further comprising any remaining chunk identifier bits not used as the index.

28. The method of claim 27 , further comprising identifying a matching input data chunk if a CAS entry is found that corresponds to an index derived from the chunk identifier of the matching input data chunk, and that includes remaining chunk identifier bits that match the corresponding remaining chunk identifier bits of the matching input data chunk.

29. The method of claim 27 , further comprising reading a collection of adjacent groups of CAS entries of the one or more CAS entries into a CAS cache, wherein at least some of the CAS entries read into the CAS cache describe related non-matching data chunks.

30. The method of claim 27 , further comprising storing at least some metadata records in a metadata cache, wherein the at least some metadata records describe related non-matching data chunks and are part of one or more metadata pages.