# US 2018/0024767 A1 · Reference Set Construction for Data Deduplication

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

- Number: US 2018/0024767 A1
- Document ID: US20180024767A1
- Status: Published application
- Kind: A1
- Application number: 15/604,588
- Filed: 2017-05-24
- Published: 2018-01-25
- Earliest claimed: 2016-07-19
- Assignees: Western Digital Technologies, Inc.
- Applicants: Western Digital Technologies, Inc.
- Inventors: Ashish Singhai; Ashwin Narasimha; Vijay Karamcheti; Tanay Goel
- Web page: https://patentgrep.com/patent/US20180024767A1

## 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/0641: {De-duplication techniques}
- G06F 3/0652: {Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket}
- G06F 3/0683: {Plurality of storage devices}
- G06F 11/3034: {where the computing system component is a storage system, e.g. DASD based or network based (digital input from or digital output to record carriers G06F3/06; digital recording or reproducing G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097)}
- G06F 11/3409: {for performance assessment}
- G06F 16/1724: {Details of de-fragmentation performed by the file system (saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064)}
- G06F 16/1727: {Details of free space management performed by the file system (saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064)}
- G06F 16/1752: {based on file chunks}
- G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
- G06F 16/2291: {User-Defined Types; Storage management thereof}
- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 11/1453: {using de-duplication of the data}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

By way of example, a data storage system may comprise a non-transitory storage device storing data blocks in chunks, and a storage logic coupled to the non-transitory storage device that manages storage of data on the storage device. The storage logic is executable to receive a data stream including one or more data blocks, identify a first chunk stored within the non-transitory storage device, retrieve a first local reference set from the first chunk, retrieve a global reference set from the non-transitory storage device, evaluate a performance of the first local reference set and the global reference set, select one of the first local reference set and the global reference set based on the evaluated performance, deduplicate each of the one or more data blocks using the selected reference set, and associate the deduplicated data blocks with the selected reference set.

## Claims

### Claim 1

A data storage system, comprising:
a non-transitory storage device storing data blocks in chunks;
a storage logic coupled to the non-transitory storage device that manages storage of data on the non-transitory storage device, the storage logic executable to:
receive a data stream including one or more data blocks;
identify a first chunk stored within the non-transitory storage device;
retrieve a first local reference set from the first chunk;
retrieve a global reference set from the non-transitory storage device;
evaluate a performance of the first local reference set and the global reference set;
select one of the first local reference set and the global reference set based on the evaluated performance;
deduplicate each of the one or more data blocks using the selected reference set; and
associate the deduplicated data blocks with the selected reference set.

### Claim 2 (depends on 1)

The data storage system of claim 1, wherein the first chunk has a range of continuous physical storage media that is filled sequentially and erased as a unit.

### Claim 3 (depends on 1)

The data storage system of claim 1, wherein the first local reference set is constructed with one or more data blocks within the first chunk.

### Claim 4 (depends on 1)

The data storage system of claim 1, wherein the performance of the first local reference set and the global reference set is evaluated based on a deduplication ratio.

### Claim 5 (depends on 1)

The data storage system of claim 1, wherein the performance of the first local reference set and the global reference set is evaluated based on a deduplication speed.

### Claim 6 (depends on 1)

The data storage system of claim 1, wherein the storage logic is further executable to:
assign a use count variable to the global reference set;
update the use count variable when the global reference set is used to deduplicate the data blocks; and
store the global reference set including the use count variable in the non-transitory storage device.

### Claim 7 (depends on 1)

The data storage system of claim 1, wherein the storage logic is further executable to:
initialize garbage collection for the first chunk;
reassemble the deduplicated data blocks using the first local reference set;
retrieve a second local reference set from a destination chunk associated with the garbage collection;
deduplicate each of the reassembled data blocks with the second local reference set;
associate each of the deduplicated data blocks with the second local reference set; and
store the deduplicated data blocks in the destination chunk.

### Claim 8 (depends on 1)

The data storage system of claim 1, wherein the storage logic is further executable to:
analyze a subsequent data stream to determine a namespace;
retrieve a namespace reference set from the determined namespace;
deduplicate the one or more data blocks of the subsequent data stream using the namespace reference set;
identify a first namespace chunk of the namespace hosting the one or more data blocks of the subsequent data stream;
retrieve the first local reference set from the first namespace chunk;
evaluate a second performance of the first local reference set and the global reference set;
select one of the first local reference set and the global reference set based on the evaluated second performance;
deduplicate each of the one or more data blocks of the subsequent data stream using the selected reference set; and
associate the deduplicated data blocks of the subsequent data stream with the selected reference set.

### Claim 9 (depends on 8)

The data storage system of claim 8, wherein the namespace hosts two or more data blocks with similar characteristics.

### Claim 10

A method comprising:
receiving, at a non-transitory storage device, a data stream including one or more data blocks;
identifying a first chunk stored within the non-transitory storage device;
retrieving a first local reference set from the first chunk;
retrieving a global reference set from the non-transitory storage device;
evaluating a performance of the first local reference set and the global reference set;
selecting one of the first local reference set and the global reference set based on the evaluated performance;
deduplicating each of the one or more data blocks using the selected reference set; and
associating the deduplicated data blocks with the selected reference set.

### Claim 11 (depends on 10)

The method of claim 10, wherein the first chunk has a range of continuous physical storage media that is filled sequentially and erased as a unit.

### Claim 12 (depends on 10)

The method of claim 10, wherein the first local reference set is constructed with one or more data blocks within the first chunk.

### Claim 13 (depends on 10)

The method of claim 10, wherein the performance of the first local reference set and the global reference set is evaluated based on a deduplication ratio.

### Claim 14 (depends on 10)

The method of claim 10, wherein the performance of the first local reference set and the global reference set is evaluated based on a deduplication speed.

### Claim 15 (depends on 10)

The method of claim 10, further comprising:
assigning a use count variable to the global reference set;
updating the use count variable when the global reference set is used to deduplicate the data blocks; and
storing the global reference set including the use count variable in the non-transitory storage device.

### Claim 16 (depends on 10)

The method of claim 10, further comprising:
initializing garbage collection for the first chunk;
reassembling the deduplicated data blocks using the first local reference set;
retrieving a second local reference set from a destination chunk associated with the garbage collection;
deduplicating each of the reassembled data blocks with the second local reference set;
associating each of the deduplicated data blocks with the second local reference set; and
storing the deduplicated data blocks in the destination chunk.

### Claim 17 (depends on 10)

The method of claim 10, further comprising:
analyzing a subsequent data stream to determine a namespace;
retrieving a namespace reference set from the determined namespace;
deduplicating the one or more data blocks of the subsequent data stream using the namespace reference set;
identifying a first namespace chunk of the namespace hosting the one or more data blocks of the subsequent data stream;
retrieving the first local reference set from the first namespace chunk;
evaluating a second performance of the first local reference set and the global reference set;
selecting one of the first local reference set and the global reference set based on the evaluated second performance;
deduplicating each of the one or more data blocks of the subsequent data stream using the selected reference set; and
associating the deduplicated data blocks of the subsequent data stream with the selected reference set.

### Claim 18 (depends on 17)

The method of claim 17, wherein the namespace hosts two or more data blocks with similar characteristics.

### Claim 19

A data storage system comprising:
means for receiving a data stream including one or more data blocks at a non-transitory storage device;
means for identifying a first chunk stored within the non-transitory storage device;
means for retrieving a first local reference set from the first chunk;
means for retrieving a global reference set from the non-transitory storage device;
means for evaluating a performance of the first local reference set and the global reference set;
means for selecting one of the first local reference set and the global reference set based on the evaluated performance;
means for deduplicating each of the one or more data blocks using the selected reference set; and
means for associating the deduplicated data blocks with the selected reference set.

### Claim 20 (depends on 19)

The data storage system of claim 19, wherein the first local reference set is constructed with one or more data blocks within the first chunk.