Apparatus and method for inline compression and deduplication

• US 10,152,389 B2
• Filed: 06/19/2015
• Issued: 12/11/2018
• Est. Priority Date: 06/19/2015
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Narasimha, Ashwin, Singhai, Ashish, Karamcheti, Vijay
• Primary Examiner(s): Patel, Hitesh
• Application Number:
  US14/744,444
• Publication Number:
  US 20160371292A1
• Time in Patent Office: 1,271 Days
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: H03M 7/00 Conversion of a code where information is represented by a given sequence or number of digits to a code where the same , similar or subset of information is represented by a different sequence or number of digits
• CPC Class Codes: H03M 7/3091 Data deduplication

Abstract

An apparatus for inline compression and deduplication includes a memory unit and a processor coupled to the memory unit. The processor is configured to receive a subset of data from a data stream and select a reference data block corresponding to the subset of data, in which the reference data block is stored in a memory buffer resident in the memory unit. The processor is also configured to compare a first hash value computed for the subset of data to a second hash value computed for the reference data block, in which the first hash value and the second hash value are stored in separate hash tables and generate a compressed representation of the subset of data by modifying header data corresponding to the subset of data responsive to a detected match between the first hash value and the second hash value in one of the separate hash tables.

Claims

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.