# US 10,503,516 B1 · Concurrent data entropy and digest computation operating on same data for CPU cache efficiency

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,503,516 B1
- Document ID: US10503516B1
- Status: Granted
- Kind: B1
- Application number: 16/043,640
- Filed: 2018-07-24
- Granted: 2019-12-10
- Earliest claimed: 2018-07-24
- Assignees: EMC IP Holding Company LLC
- Applicants: EMC IP Holding Company LLC
- Inventors: Sorin Faibish; Ivan Bassov; Rustem Rafikov
- Web page: https://patentgrep.com/patent/US10503516B1

## CPC

- G06F 9/3869: {Implementation aspects, e.g. pipeline latches; pipeline synchronisation and clocking}
- G06F 16/1748: {De-duplication implemented within the file system, e.g. based on file segments (de-duplication techniques in storage systems for the management of data blocks G06F3/0641)}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/061: {Improving I/O performance}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 3/0688: {Non-volatile semiconductor memory arrays}
- G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores
- G06F 12/0835: {for main memory peripheral accesses (e.g. I/O or DMA)}
- H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- G06F 3/0638: {Organizing or formatting or addressing of data}
- G06F 3/0641: {De-duplication techniques}
- G06F 12/0868: Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
- G06F 16/1734: {Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs}
- G06F 16/178: Techniques for file synchronisation in file systems
- G06F 2212/1044: Space efficiency improvement
- G06F 2212/262: configured as RAID
- G06F 2212/312: In storage controller
- G06F 2212/401: Compressed data
- 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
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

Techniques for CPU cache efficiency may include performing concurrent processing, such as for first and second data operations, in a synchronized manner that prevents loading the same data chunk into the CPU cache more than once. Processing may include synchronizing the first and second data operations with respect to a first data chunk to ensure that both complete prior to proceeding with performing such processing on a second data chunk. The first and second data operations for a chunk may be deduplication digest computation and entropy computation performed inline as part of the data path. If the chunk cannot be deduplicated, the entropy value may be used with an adaptive entropy threshold to determine whether to compress the chunk inline. The entropy value may be determined using less than all bytes in the chunk. The chunk's entropy value may be determined based on a data set entropy value.

## Claims

### Claim 1

A method of performing data processing comprising:
performing, using a first processor, first processing that computes a data deduplication digest for a first data chunk;
performing, using a second processor, second processing that computes an entropy value for the first data chunk; and
synchronizing the first processing performed using the first processor and the second processing performed using the second processor with respect to the first data chunk, wherein said synchronizing ensures that both the first processing performed using the first processor and the second processing performed using the second processor have completed prior to proceeding with performing any of the first processing and the second processing on a second data chunk.

### Claim 2 (depends on 1)

The method of claim 1, wherein the first processing and the second processing for the first data chunk are performed in parallel.

### Claim 3 (depends on 2)

The method of claim 2, wherein one of the first processing and the second processing completes processing for the first data chunk prior to another one of the first processing and the second processing, and wherein said synchronizing does not allow the one of the first and second processing to proceed with processing the second data chunk until the another one of the first processing and the second processing has completed its processing for the first data chunk.

### Claim 4 (depends on 2)

The method of claim 2, wherein the first data processing and the second data processing are performed inline as part of I/O path processing.

### Claim 5 (depends on 2)

The method of claim 2, further comprising:
determining, using the data deduplication digest for a first data chunk, whether the first chunk can be deduplicated whereby the first chunk is a duplicate of an existing chunk currently associated with the data deduplication digest; and
responsive to determining that the first chunk can be deduplicated, deduplicating the first data chunk.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
responsive to determining that the first chunk cannot be deduplicated, performing processing including:
determining whether the entropy value for the first data chunk is greater than an entropy threshold;
responsive to determining that the entropy value for the first data chunk is not greater than the entropy threshold, determining not to compress the first data chunk inline as part of the I/O path; and
responsive to determining that the entropy value for the first data chunk is equal to or less than the entropy threshold, compressing the first data chunk inline as part of the I/O path.

### Claim 7 (depends on 6)

The method of claim 6, wherein the first data chunk is data of a write operation received at a data storage system and the method further comprises:
determining a current workload of the data storage system; and
modifying the entropy threshold in accordance with the current workload of the data storage system.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
determining whether the current workload is above a high workload threshold; and
responsive to determining the current workload is above the high workload threshold, decreasing the entropy threshold in accordance with the current workload.

### Claim 9 (depends on 7)

The method of claim 7, further comprising:
determining whether the current workload is less than a low workload threshold; and
responsive to determining the current workload is less than the low workload threshold, increasing the entropy threshold in accordance with the current workload.

### Claim 10 (depends on 1)

The method of claim 1, wherein the entropy value for the first data chunk is determined using less than all data of the first data chunk.

### Claim 11 (depends on 10)

The method of claim 10, wherein the entropy value for the first data chunk is determined using selected bytes of the first data chunk.

### Claim 12 (depends on 11)

The method of claim 11, wherein the first data chunk is included in a data set having a data set entropy value and the entropy value for the first data chunk is determined as the data set entropy value.

### Claim 13 (depends on 12)

The method of claim 12, wherein the data set includes a first plurality of data chunks and the method further comprising;
selecting a second plurality of data chunks of the data set, the second plurality being less than the first plurality of data chunks;
determining a plurality of entropy values for the second plurality of data chunks;
determining whether the plurality of entropy values are similar to one another; and
responsive to determining the plurality of entropy values are similar to one another, determining the data set entropy value in accordance with plurality of entropy values for the second number of data chunks of the data set.

### Claim 14

A system comprising:
one or more processors; and
a memory comprising code stored thereon that, when executed, performs a method of performing data processing comprising:
performing first processing that computes a data deduplication digest for a first data chunk;
performing second processing that computes an entropy value for the first data chunk; and
synchronizing the first processing and the second processing with respect to the first data chunk, wherein said synchronizing ensures that both the first processing and the second processing have completed prior to proceeding with performing any of the first processing and the second processing on a second data chunk.

### Claim 15

A computer readable medium comprising code stored thereon that, when executed, performs a method of performing data processing comprising:
performing first processing that computes a data deduplication digest for a first data chunk;
performing second processing that computes an entropy value for the first data chunk; and
synchronizing the first processing and the second processing with respect to the first data chunk, wherein said synchronizing ensures that both the first processing and the second processing have completed prior to proceeding with performing any of the first processing and the second processing on a second data chunk.

### Claim 16 (depends on 15)

The computer readable medium of claim 15, wherein the first processing and the second processing for the first data chunk are performed in parallel.

### Claim 17 (depends on 16)

The computer readable medium of claim 16, wherein one of the first processing and the second processing completes processing for the first data chunk prior to another one of the first processing and the second processing, and wherein said synchronizing does not allow the one of the first and second processing to proceed with processing the second data chunk until the another one of the first processing and the second processing has completed its processing for the first data chunk.

### Claim 18 (depends on 16)

The computer readable medium of claim 16, wherein the first data processing and the second data processing are performed inline as part of I/O path processing.

### Claim 19 (depends on 16)

The computer readable medium of claim 16, wherein the method further comprises:
determining, using the data deduplication digest for a first data chunk, whether the first chunk can be deduplicated whereby the first chunk is a duplicate of an existing chunk currently associated with the data deduplication digest; and
responsive to determining that the first chunk can be deduplicated, deduplicating the first data chunk.

### Claim 20 (depends on 19)

The computer readable medium of claim 19, wherein the method further comprises:
responsive to determining that the first chunk cannot be deduplicated, performing processing including:
determining whether the entropy value for the first data chunk is greater than an entropy threshold;
responsive to determining that the entropy value for the first data chunk is not greater than the entropy threshold, determining not to compress the first data chunk inline as part of the I/O path; and
responsive to determining that the entropy value for the first data chunk is equal to or less than the entropy threshold, compressing the first data chunk inline as part of the I/O path.