Apparatus and method for single pass entropy detection on data transfer

• US 10,089,360 B2
• Filed: 12/15/2016
• Issued: 10/02/2018
• Est. Priority Date: 06/19/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: Narasimha, Ashwin, Singhai, Ashish, Karamcheti, Vijay, Skandakumaran, Krishanth
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US15/380,826
• Publication Number:
  US 20170097960A1
• Time in Patent Office: 656 Days
• Field of Search: 707693
• CPC Class Codes: G06F 11/3072 where the reporting involves data filtering, e.g. pattern matching, time or event triggered, adaptive or policy-based reporting
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

Embodiments of the present invention include a memory unit and a processor coupled to a memory unit. The processor is operable to group a plurality of subsets of data from an input data stream and compute a first hash value corresponding to a first grouped subset of data. Additionally, the processor is operable to detect a match between the first hash value and a second hash value stored in a hash table. Furthermore, the processor is also configured to monitor a hash value match frequency for the input data stream in which the processor is operable to increment a counter value responsive to a detection of the match and determine an entropy level for the input data stream based on the counter value relative to a frequent hash value match threshold. The processor can generate an instruction to either initialize performance of a data compression operation when the counter value meets or exceeds the frequent hash value match threshold or refrain from the performance of the data compression operation when the counter value fails to meet the frequent hash value match threshold.

Claims

1. An apparatus comprising:

a memory unit configured to store an input data stream; and

a processor coupled to said memory unit, said processor configured to;

compute a hash value for a subset of data of said input data stream;

compare the hash value computed for the subset of data of said input data stream with a stored hash value in a hash table;

update a counter value if the hash value matches the stored hash value;

determine, based on the counter value, an entropy level for the subset of data of said input data stream, and perform a data reduction operation responsive to said entropy level.

2. The apparatus of claim 1, wherein said processor is operable to monitor a hash value match frequency for the subset of data of said input data stream to determine said entropy level.

3. The apparatus of claim 1, wherein said processor is operable to initialize said data reduction operation responsive to detection of a high entropy level, wherein the entropy level is high entropy level when the counter value satisfies a threshold value.

4. The apparatus of claim 1, wherein said processor is operable to halt said data reduction operation responsive to detection of a low entropy level, wherein the entropy level is low entropy level when the counter value is below a threshold value.

5. The apparatus of claim 1, wherein said data reduction operation comprises a compression operation.

6. The apparatus of claim 5, wherein said processor is operable to perform said compression operation using a hash table.

7. The apparatus of claim 5, wherein said processor is operable to modify a compression header format to perform said compression operation.

8. A computer-implemented method to detect entropy of an input data stream, said method comprising:

receiving an input data stream;

computing a hash value for a subset of data of said input data stream;

comparing the hash value computed for the subset of data of said input data stream with a stored hash value in a hash table;

updating a counter value if the hash value matches the stored hash value;

determining, based on the counter value, an entropy level for the subset of data of said input data stream; and

performing a data reduction operation responsive to said entropy level.

9. The computer-implemented method of claim 8, wherein said determining an entropy level further comprises:

monitoring a hash value match frequency for said input data stream.

10. The computer-implemented method of claim 8, wherein said performing a data reduction operation further comprises initializing said data reduction operation responsive to a detection of a high entropy level, wherein the entropy level is high entropy level when the counter value satisfies a threshold value.

11. The computer-implemented method of claim 8, wherein said performing a data reduction operation further comprises halting said data reduction operation responsive to a detection of a low entropy level, wherein the entropy level is low entropy level when the counter value is below a threshold value.

12. The computer-implemented method of claim 8, wherein said performing a data reduction operation further comprises performing a compression operation.

13. The computer-implemented method of claim 12, wherein said performing a compression operation comprises using a hash table.

14. The computer-implemented method of claim 12, wherein said performing a decompression operation further comprises modifying a compression header format to perform said compression operation.

15. An apparatus comprising:

a processor;

a memory storing sequences of instructions, which when executed by the processor, causes the processor to perform;

storing an input data stream;

computing a hash value for a subset of data of said input data stream;

comparing the hash value computed for the subset of data of said input data stream with a stored hash value in a hash table;

updating a counter value if the hash value matches the stored hash value; and

determining, based on the counter value, an entropy level for the subset of data of said input data stream and performing a data reduction operation responsive to said entropy level.

16. The apparatus of claim 15, wherein the stored sequences of instructions, which when executed by the processor, cause the processor to perform:

performing said data reduction operation using a plurality of hash tables.

17. The apparatus of claim 15, wherein said data reduction operation comprises a data deduplication operation.

18. The apparatus of claim 15, wherein said data reduction operation comprises a data compression operation.

19. The apparatus of claim 18, wherein the stored sequences of instructions, which when executed by the processor, cause the processor to perform:

modifying a compression header format to perform said compression operation using said hash table.