# US 11,307,765 B2 · System and methods for storage data deduplication

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

- Number: US 11,307,765 B2
- Document ID: US11307765B2
- Status: Granted
- Kind: B2
- Application number: 16/356,818
- Filed: 2019-03-18
- Published: 2019-08-15
- Granted: 2022-04-19
- Earliest claimed: 2015-07-27
- Assignees: VMware, Inc.
- Applicants: VMware, Inc.
- Inventors: R. Hugo Patterson, III; Sazzala Reddy; Vijayan Prabhakaran; Garrett Smith; Lakshmi Narayanan Bairavasundaram; Ganesh Venkitachalam
- Web page: https://patentgrep.com/patent/US11307765B2

## CPC

- G06F 3/06: Digital input from, or digital output to, record carriers {, e.g. RAID, emulated record carriers or networked record carriers}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0641: {De-duplication techniques}
- G06F 3/0683: {Plurality of storage devices}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/24552: {Database cache management}
- G06F 16/24556: {Aggregation; Duplicate elimination}
- G06F 16/285: {Clustering or classification}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Data in a storage system is deduplicated after receiving from at least one writing entity requests for a plurality of write operations for a corresponding plurality of data blocks in a storage object. The received blocks are buffered and sorted in order and a sequence of clumps is created from the buffered blocks, where each clump comprises a grouping of at least one of the sorted, buffered blocks. A boundary is determined between at least one pair of clumps based at least in part on the content of at least one of the buffered blocks, and it is then determined whether at least one of the clumps is a duplicate of a previously stored clump.

## Claims

### Claim 1

A method for managing data in a storage system comprising:
receiving, from at least one writing entity, requests for a plurality of write operations;
wherein the plurality of write operations are for writing a plurality of received blocks to storage;
wherein each block of the plurality of received blocks is associated with a Logical Block Address (LBA);
creating a sequence of clumps from the plurality of received blocks, wherein each clump comprises a group of blocks, and wherein a first clump includes a first group of blocks in which the LBAs of the blocks are not contiguous in LBA space, wherein creating the sequence of clumps comprises:
compressing each of the plurality of received blocks,
sorting the plurality of compressed blocks in LBA order, and
packing groups of blocks into corresponding clumps;
creating a data structure for storing LBA-to-clump mappings;
for each block of the plurality of received blocks, storing a corresponding entry in the data structure;
within each entry in the data structure, storing:
the LBA that is associated with the received block to which the entry corresponds, and
a reference tuple that includes a clump identifier for the clump that stores data for the corresponding LBA of the entry and a position of the block within the clump; and
after creating the data structure, using entries in the data structure to determine the clumps that store data for the received blocks.

### Claim 2 (depends on 1)

The method of claim 1 wherein:
the plurality of received blocks includes a particular block;
the particular block is associated with a particular LBA;
within the sequence of clumps, data for the particular block is stored in a particular clump;
storing a corresponding entry in the data structure includes storing, within the data structure, a particular entry for the particular LBA;
wherein the particular entry includes the particular LBA and a particular reference; and
the particular reference includes:
a particular clump identifier that identifies the particular clump; and
a particular block position that indicates a position, within the particular clump, of the data that corresponds to the particular LBA.

### Claim 3 (depends on 2)

The method of claim 2 wherein:
the particular reference is a first reference associated with a first snapshot;
the particular clump was written to storage during the first snapshot;
the particular entry includes a second reference associated with a second snapshot;
new data associated with the particular LBA was written to storage during the second snapshot; and
the second reference includes:
a second clump identifier that identifies a second clump that contains the new data; and
a second block position that indicates a position, within the second clump, of the new data.

### Claim 4 (depends on 3)

The method of claim 3 wherein the particular entry includes an indication of a snapshot ID of a snapshot during which the particular reference was created.

### Claim 5 (depends on 1)

The method of claim 1, in which the clump identifier stored in each reference is a clump fingerprint.

### Claim 6 (depends on 5)

The method of claim 5, in which the fingerprint is a hash value of the contents of the clump.

### Claim 7 (depends on 3)

The method of claim 3, further comprising scanning entries of the data structure to identify, as dead data blocks, those data blocks that are referenced by stale references, wherein a stale reference is a reference that (a) is associated with an LBA whose entry includes multiple references; and (b) is associated with a snapshot that is older than at least one other snapshot identified in the entry for the LBA.

### Claim 8 (depends on 7)

The method of claim 7, further comprising repacking clumps so as to retain only clumps having no dead data blocks.

### Claim 9 (depends on 1)

The method of claim 1, further comprising storing the data structure as a Log-Structured Merge tree.

### Claim 10

One or more non-transitory computer-readable media storing instructions for managing data in a storage system, wherein the instructions, when executed by one or more processors, cause:
receiving, from at least one writing entity, requests for a plurality of write operations;
wherein the plurality of write operations are for writing a plurality of received blocks to storage;
wherein each block of the plurality of received blocks is associated with a Logical Block Address (LBA);
creating a sequence of clumps from the plurality of received blocks, wherein each clump comprises a group of blocks, and wherein a first clump includes a first group of blocks in which the LBAs of the blocks are not contiguous in LBA space, wherein creating the sequence of clumps comprises:
compressing each of the plurality of received blocks;
sorting the plurality of compressed blocks in LBA order; and
packing groups of blocks into corresponding clumps;
creating a data structure for storing LBA-to-clump mappings;
for each block of the plurality of received blocks, storing a corresponding entry in the data structure;
within each entry in the data structure, storing:
the LBA that is associated with the received block to which the entry corresponds, and
a reference tuple that includes a clump identifier for the clump that stores data for the corresponding LBA of the entry and a position of the block within the clump; and
after creating the data structure, using entries in the data structure to determine the clumps that store data for the received blocks.

### Claim 11 (depends on 10)

The one or more non-transitory computer-readable media of claim 10 wherein:
the plurality of received blocks includes a particular block;
the particular block is associated with a particular LBA;
within the sequence of clumps, data for the particular block is stored in a particular clump;
storing a corresponding entry in the data structure includes storing, within the data structure, a particular entry for the particular LBA;
wherein the particular entry includes the particular LBA and a particular reference; and
the particular reference includes:
a particular clump identifier that identifies the particular clump; and
a particular block position that indicates a position, within the particular clump, of the data that corresponds to the particular LBA.

### Claim 12 (depends on 11)

The one or more non-transitory computer-readable media of claim 11 wherein:
the particular reference is a first reference associated with a first snapshot;
the particular clump was written to storage during the first snapshot;
the particular entry includes a second reference associated with a second snapshot;
new data associated with the particular LBA was written to storage during the second snapshot; and
the second reference includes:
a second clump identifier that identifies a second clump that contains the new data; and
a second block position that indicates a position, within the second clump, of the new data.

### Claim 13 (depends on 12)

The one or more non-transitory computer-readable media of claim 12 wherein the particular entry includes an indication of a snapshot ID of a snapshot during which the particular reference was created.

### Claim 14 (depends on 10)

The one or more non-transitory computer-readable media of claim 10, in which the clump identifier stored in each reference is a clump fingerprint.

### Claim 15 (depends on 14)

The one or more non-transitory computer-readable media of claim 14, in which the fingerprint is a hash value of the contents of the clump.

### Claim 16 (depends on 12)

The one or more non-transitory computer-readable media of claim 12, wherein execution of the instructions further causes scanning entries of the data structure to identify, as dead data blocks, those data blocks that are referenced by stale references, wherein a stale reference is a reference that (a) is associated with an LBA whose entry includes multiple references; and (b) is associated with a snapshot that is older than at least one other snapshot identified in the entry for the LBA.

### Claim 17 (depends on 16)

The one or more non-transitory computer-readable media of claim 16, wherein execution of the instructions further causes repacking clumps so as to retain only clumps having no dead data blocks.

### Claim 18 (depends on 10)

The one or more non-transitory computer-readable media of claim 10, wherein execution of the instructions further causes storing the data structure as a Log-Structured Merge tree.

### Claim 19

A system comprising one or more processors and one or more computer-readable media storing instructions that when executed cause the one or more processors to perform operations comprising:
receiving, from at least one writing entity, requests for a plurality of write operations;
wherein the plurality of write operations are for writing a plurality of received blocks to storage;
wherein each block of the plurality of received blocks is associated with a Logical Block Address (LBA);
creating a sequence of clumps from the plurality of received blocks, wherein each clump comprises a group of blocks, and wherein a first clump includes a first group of blocks in which the LBAs of the blocks are not contiguous in LBA space, wherein creating the sequence of clumps comprises:
compressing each of the plurality of received blocks;
sorting the plurality of compressed blocks in LBA order; and
packing groups of blocks into corresponding clumps;
creating a data structure for storing LBA-to-clump mappings;
for each block of the plurality of received blocks, storing a corresponding entry in the data structure;
within each entry in the data structure, storing:
the LBA that is associated with the received block to which the entry corresponds, and
a reference tuple that includes a clump identifier for the clump that stores data for the corresponding LBA of the entry and a position of the block within the clump; and
after creating the data structure, using entries in the data structure to determine the clumps that store data for the received blocks.

### Claim 20 (depends on 19)

The system of claim 19 wherein:
the plurality of received blocks includes a particular block;
the particular block is associated with a particular LBA;
within the sequence of clumps, data for the particular block is stored in a particular clump;
storing a corresponding entry in the data structure includes storing, within the data structure, a particular entry for the particular LBA; and
wherein the particular entry includes the particular LBA and a particular reference; the particular reference includes:
a particular clump identifier that identifies the particular clump; and
a particular block position that indicates a position, within the particular clump, of the data that corresponds to the particular LBA.

### Claim 21 (depends on 20)

The system of claim 20 wherein:
the particular reference is a first reference associated with a first snapshot;
the particular clump was written to storage during the first snapshot;
the particular entry includes a second reference associated with a second snapshot;
new data associated with the particular LBA was written to storage during the second snapshot; and
the second reference includes:
a second clump identifier that identifies a second clump that contains the new data; and
a second block position that indicates a position, within the second clump, of the new data.

### Claim 22 (depends on 21)

The system of claim 21 wherein the particular entry includes an indication of a snapshot ID of a snapshot during which the particular reference was created.

### Claim 23 (depends on 19)

The system of claim 19, in which the clump identifier stored in each reference is a clump fingerprint.

### Claim 24 (depends on 23)

The system of claim 23, in which the fingerprint is a hash value of the contents of the clump.

### Claim 25 (depends on 21)

The system of claim 21, further comprising scanning entries of the data structure to identify, as dead data blocks, those data blocks that are referenced by stale references, wherein a stale reference is a reference that (a) is associated with an LBA whose entry includes multiple references; and (b) is associated with a snapshot that is older than at least one other snapshot identified in the entry for the LBA.

### Claim 26 (depends on 25)

The system of claim 25, further comprising repacking clumps so as to retain only clumps having no dead data blocks.

### Claim 27 (depends on 19)

The system of claim 19, further comprising storing the data structure as a Log-Structured Merge tree.