Granted Patent B2

US 10,152,389 · App. 14/744,444 · Granted Dec 11, 2018

Abstract

Claims (23)

1. An apparatus comprising:

a memory unit for storing data streams; and

a processor coupled to said memory unit, the processor configured to perform a compression operation and a deduplication operation in a single pass, said processor configured to:

use a subset of data from a data stream to generate a reference data block corresponding to said subset of data;

compute a first hash value for said subset of data and a second hash value for said reference block using a same function;

compare the first hash value computed for said subset of data to the second hash value computed for said reference data block, wherein said first hash value and said second hash value are stored in separate hash tables;

generate a compressed and deduplicated representation of said subset of data by at least modifying header data corresponding to said subset of data responsive to a detected match between said first hash value and said second hash value,

wherein said compressed representation is generated using said reference data block responsive to the detection of the match between said first hash value and said second hash value,

wherein said separate hash tables comprises a reference hash table and said second hash value is stored in said reference hash table; and

initiate decompression procedures upon storing said reference data block in a memory buffer and upon generation of said compressed representation.

2. The apparatus of claim 1 , wherein said separate hash tables comprises a compression hash table.

3. The apparatus of claim 1 , wherein said processor is operable to generate an interlock by the initiation of the decompression procedures upon storing said reference data block in said memory buffer.

4. The apparatus of claim 1 , wherein said processor is operable to modify said header data using a back-reference encoding format based on a heuristic.

5. A computer-implemented method of performing data reduction operations on an input data stream during a single pass, said method comprising:

receiving a subset of data from a data stream;

selecting a reference data block corresponding to said subset of data, wherein said reference data block is stored in a memory buffer;

comparing a first hash value computed for said subset of data to a second hash value computed for said reference data block, wherein said first hash value and said second hash value are stored in separate hash tables, wherein said first hash value and said second hash value are computed using a same function;

generating a compressed representation of said subset of data by at least modifying header data corresponding to said subset of data responsive to a detected match between said first hash value and said second hash value,

wherein said compressed representation is generated using said reference data block responsive to the detected match between said first hash value and said second hash value, wherein said separate hash tables comprises a reference hash table and said second hash value is stored in said reference table; and

initiating decompression procedures upon storing said reference data block in said memory buffer and upon generation of said compressed representation.

6. The computer-implemented method of claim 5 , wherein said separate hash tables comprises a compression hash table.

7. The computer-implemented method of claim 5 , further comprising: generating an interlock by the initiation of the decompression procedures upon storing said reference data block in said memory buffer.

8. The computer-implemented method of claim 5 , wherein said modifying further comprises modifying said header data using a back-reference encoding format based on a heuristic.

Assignments (10)