# US 2017/0286443 A1 · Optimizing data block size for deduplication

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

- Number: US 2017/0286443 A1
- Document ID: US20170286443A1
- Status: Published application
- Kind: A1
- Application number: 15/486,224
- Filed: 2017-04-12
- Published: 2017-10-05
- Earliest claimed: 2012-10-01
- Assignees: Western Digital Technologies, Inc.
- Applicants: Western Digital Technologies, Inc.
- Inventors: Tamir RAM
- Web page: https://patentgrep.com/patent/US20170286443A1

## CPC

- 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/0641: {De-duplication techniques}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 3/0671: {In-line storage system}
- G06F 11/1453: {using de-duplication of the data}
- G06F 11/1464: {for networked environments}
- G06F 16/1752: {based on file chunks}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Provided herein is technology relating to data deduplication and particularly, but not exclusively, to methods and systems for determining an efficiently optimal size of data blocks to use for backing up a data source. Also provided herein are systems for identifying duplicate data in data backup applications.

## Claims

### Claim 1

A method comprising:
obtaining a file of a file type;
determining a deduplication block size based on the file type, wherein the deduplication block size provides a maximum compression ratio for the file type; and
deduplicating a set of data blocks of the file based on the deduplication block size and a sliding window, wherein the sliding window moves backwards responsive to not detecting a duplicate data block.

### Claim 2 (depends on 1)

The method of claim 1, wherein deduplicating the set of data blocks comprises:
determining whether a first data block of the file is identical to a previous data block.

### Claim 3 (depends on 2)

The method of claim 2, wherein determining whether the first data block is a duplicate data block comprises:
calculating a first hash value of the first data block to identify the first data block as a potential duplicate data block; and
calculating a second hash value of the first data block to confirm that the first data block is the duplicate data block.

### Claim 4 (depends on 2)

The method of claim 2, wherein deduplicating the set of data blocks further comprises:
setting a beginning of the sliding window to an end of the first data block responsive to determining that the first data block is identical to the previous data block.

### Claim 5 (depends on 4)

The method of claim 4, wherein deduplicating the set of data blocks further comprises:
replacing the duplicate data block with a pointer to the previous data block, wherein the duplicate data block is identical to the previous data block.

### Claim 6 (depends on 1)

The method of claim 1, wherein deduplicating the set of data blocks comprises:
moving the sliding window backwards by one byte responsive to not detecting the duplicate data block.

### Claim 7 (depends on 1)

The method of claim 1, wherein a size of the sliding window is the same as the deduplication block size.

### Claim 8 (depends on 1)

The method of claim 1, wherein determining the deduplication block size comprises:
determining a plurality of compression ratios for a test file of the file type, wherein each compression ratio is associated with a test block size;
determining a maximum compression ratio from the plurality of compression ratios; and
selecting a first block size associated with the maximum compression ratio as the deduplication block size.

### Claim 9

An apparatus, comprising:
a memory configured to store a table associating a plurality of file types with a plurality of deduplication block sizes; and
a processor configured to:
obtain a file of a file type;
determine a deduplication block size based on the file type, wherein the deduplication block size provides a maximum compression ratio for the file type; and
deduplicate a set of data blocks of the file based on the deduplication block size and a sliding window, wherein the sliding window moves backwards responsive to not detecting a duplicate data block.

### Claim 10 (depends on 9)

The apparatus of claim 9, wherein the processor is configured to deduplicate the set of data blocks by:
determining whether a first data block of the file is identical to a previous data block.

### Claim 11 (depends on 10)

The apparatus of claim 10, wherein the processor is configured to determine whether the first data block is a duplicate data block by:
calculating a first hash value of the first data block to identify the first data block as a potential duplicate data block; and
calculating a second hash value of the first data block to confirm that the first data block is the duplicate data block.

### Claim 12 (depends on 10)

The apparatus of claim 10, wherein the processor is further configured to deduplicate the set of data blocks by:
setting a beginning of the sliding window to an end of the first data block responsive to determining that the first data block is identical to the previous data block.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the processor is further configured to deduplicate the set of data blocks by:
replacing the duplicate data block with a pointer to the previous data block, wherein the duplicate data block is identical to the previous data block.

### Claim 14 (depends on 9)

The apparatus of claim 9, wherein the processor is configured to deduplicate the set of data blocks by:
moving the sliding window backwards by one byte responsive to not detecting the duplicate data block.

### Claim 15 (depends on 9)

The apparatus of claim 9, wherein a size of the sliding window is the same as the deduplication block size.

### Claim 16 (depends on 9)

The apparatus of claim 9, wherein determining the deduplication block size comprises:
determining a plurality of compression ratios for a test file of the file type, wherein each compression ratio is associated with a test block size;
determining a maximum compression ratio from the plurality of compression ratios; and
selecting a first block size associated with the maximum compression ratio as the deduplication block size.

### Claim 17

A non-transitory computer-readable medium having stored thereon instructions that, when executed by a processor, cause the processor to perform operations comprising:
obtaining a file of a file type;
determining a deduplication block size based on the file type, wherein the deduplication block size provides a maximum compression ratio for the file type; and
deduplicating a set of data blocks of the file based on the deduplication block size and a sliding window, wherein the sliding window moves backwards responsive to not detecting a duplicate data block.

### Claim 18 (depends on 17)

The non-transitory computer-readable medium of claim 17, wherein deduplicating the set of data blocks comprises:
determining whether a first data block of the file is identical to a previous data block.

### Claim 19 (depends on 18)

The non-transitory computer-readable medium of claim 18, wherein deduplicating the set of data blocks further comprises:
setting a beginning of the sliding window to an end of the first data block responsive to determining that the first data block is identical to the previous data block.

### Claim 20 (depends on 17)

The non-transitory computer-readable medium of claim 17, wherein deduplicating the set of data blocks comprises:
moving the sliding window backwards by one byte responsive to not detecting the duplicate data block.
