# US 2021/0342297 A1 · Light-weight index deduplication and hierarchical snapshot replication

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

- Number: US 2021/0342297 A1
- Document ID: US20210342297A1
- Status: Published application
- Kind: A1
- Application number: 16/862,470
- Filed: 2020-04-29
- Published: 2021-11-04
- Earliest claimed: 2020-04-29
- Assignees: Rubrik, Inc.
- Applicants: Rubrik, Inc.
- Inventors: Anshul Gupta; Abdullah Reza; Guilherme Vale Ferreira Menezes
- Web page: https://patentgrep.com/patent/US20210342297A1

## CPC

- G06F 16/128: {Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16)}
- G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)}
- G06F 16/152: {using file content signatures, e.g. hash values}
- 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: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A lightweight deduplication system can perform resource efficient data deduplication using an extent index and a content index. The extent index can store full fingerprints of data segments to be deduplicated and the content index can store shortened versions of the full fingerprints. The system can alternate between the extent and content indexes, and cache portions of the indices to perform lightweight data deduplication. Further, the system can be configured with an efficient heuristic approach for selecting content index data lookups for chains of volumes for deduplication, such as a long chain of snapshots.

## Claims

### Claim 1

A method comprising:
generating first index data for a first dataset comprising a first set of segments, the first index data comprising a first full fingerprint for each segment in the first set of segments and a first shortened fingerprint for each segment in the first set of segments, each first shortened fingerprint for a given segment being a shortened version of a corresponding first full fingerprint of the given segment;
generating second index data for a second dataset comprising a second set of segments, the second index data comprising a second full fingerprint for each segment in the second set of segments and a second shortened fingerprint for each segment in the second set of segments, each second shortened fingerprint for a given segment being a shortened version of a corresponding second full fingerprint of the given segment; and
deduplicating the first dataset and the second dataset by removing duplicate aligned segments using full fingerprints followed by removing duplicate non-aligned segments using shortened fingerprints, the duplicate non-aligned segments being remaining segments not removed as aligned segments, the duplicate aligned segment having a same position in the first dataset and the second dataset, the duplicate non-aligned segments having different positions in the first dataset and the second dataset.

### Claim 2 (depends on 1)

The method of claim 1, wherein removing duplicate aligned segments comprises:
identifying, from the first set of segments, one or more first segments that have the same position as one or more second segments in the second set of segments;
determining that the one or more first segments and the one or more second segments at the same position have identical full fingerprints; and
replacing, in the second dataset, the one or more second segments with one or more references to the one or more first segments in the first dataset.

### Claim 3 (depends on 1)

The method of claim 1, wherein the duplicate non-aligned segments are segments that are determined to not have aligned segments with matching full fingerprints.

### Claim 4 (depends on 1)

The method of claim 1, wherein removing the duplicate non-aligned segments comprises:
identifying one or more first non-aligned segments in the first dataset that have first shortened fingerprints that match second shortened fingerprints of one or more non-aligned second segments in the second dataset;
confirming that the one or more first non-aligned segments identified using the first shortened fingerprint are duplicates of the one or more non-aligned second segments by determining that the one or more first non-aligned segments and the one or more second non-aligned segments have matching full fingerprints; and
in response to confirming that the one or more first non-aligned segments and the one or more second non-aligned segments have matching full fingerprints, replacing, in the second dataset, the one or more second non-aligned segments with one or more references to the one or more first non-aligned segments in the first dataset.

### Claim 5 (depends on 1)

The method of claim 1, wherein the first set of segments are in a sequential order and the second set of segments are also in the sequential order.

### Claim 6 (depends on 5)

The method of claim 5, wherein each position of each segment is an offset specifying a location in the sequential order.

### Claim 7 (depends on 1)

The method of claim 1, wherein each full fingerprint of each segment is a hash of the segment.

### Claim 8 (depends on 7)

The method of claim 7, wherein the shortened fingerprint of each segment is a truncated portion of the hash of the segment.

### Claim 9 (depends on 1)

The method of claim 1, wherein the first index data and the second index data store full fingerprint data and offset data in an extent key value structure with full fingerprints as keys and offsets as values that correspond to the keys.

### Claim 10 (depends on 9)

The method of claim 9, wherein the first index data and the second index data store shortened fingerprint data and offset data in a context key value structure with offsets as keys and shortened fingerprints as values that correspond to the keys.

### Claim 11

A system comprising:
one or more processors of a machine;
a memory storing instructions that, when executed by the one or more processors, cause the machine to perform operations comprising:
generating first index data for a first dataset comprising a first set of segments, the first index data comprising a first full fingerprint for each segment in the first set of segments and a first shortened fingerprint for each segment in the first set of segments, each first shortened fingerprint for a given segment being a shortened version of a corresponding first full fingerprint of the given segment;
generating second index data for a second dataset comprising a second set of segments, the second index data comprising a second full fingerprint for each segment in the second set of segments and a second shortened fingerprint for each segment in the second set of segments, each second shortened fingerprint for a given segment being a shortened version of a corresponding second full fingerprint of the given segment; and
deduplicating the first dataset and the second dataset by removing duplicate aligned segments using full fingerprints followed by removing duplicate non-aligned segments using shortened fingerprints, the duplicate non-aligned segments being remaining segments not removed as aligned segments, the duplicate aligned segment having a same position in the first dataset and the second dataset, the duplicate non-aligned segments having different positions in the first dataset and the second dataset.

### Claim 12 (depends on 11)

The system of claim 11, wherein removing duplicate aligned segments comprises:
identifying, from the first set of segments, one or more first segments that have the same position as one or more second segments in the second set of segments;
determining that the one or more first segments and the one or more second segments at the same position have identical full fingerprints; and
replacing, in the second dataset, the one or more second segments with one or more references to the one or more first segments in the first dataset.

### Claim 13 (depends on 11)

The system of claim 11, wherein the duplicate non-aligned segments are segments that are determined to not have aligned segments with matching full fingerprints.

### Claim 14 (depends on 11)

The system of claim 11, wherein removing the duplicate non-aligned segments comprises:
identifying one or more first non-aligned segments in the first dataset that have first shortened fingerprints that match second shortened fingerprints of one or more non-aligned second segments in the second dataset;
confirming that the one or more first non-aligned segments identified using the first shortened fingerprint are duplicates of the one or more non-aligned second segments by determining that the one or more first non-aligned segments and the one or more second non-aligned segments have matching full fingerprints; and
in response to confirming that the one or more first non-aligned segments and the one or more second non-aligned segments have matching full fingerprints, replacing, in the second dataset, the one or more second non-aligned segments with one or more references to the one or more first non-aligned segments in the first dataset.

### Claim 15 (depends on 11)

The system of claim 11, wherein the first set of segments are in a sequential order and the second set of segments are also in the sequential order.

### Claim 16 (depends on 15)

The system of claim 15, wherein each position of each segment is an offset specifying a location in the sequential order.

### Claim 17 (depends on 11)

The system of claim 11, wherein each full fingerprint of each segment is a hash of the segment.

### Claim 18 (depends on 17)

The system of claim 17, wherein the shortened fingerprint of each segment is a truncated portion of the hash of the segment.

### Claim 19 (depends on 11)

The system of claim 11, wherein the first index data and the second index data store full fingerprint data and offset data in an extent key value structure with full fingerprints as keys and offsets as values that correspond to the keys.

### Claim 20

A machine-readable storage device embodying instructions that, when executed by a machine, cause the machine to perform operations comprising:
generating first index data for a first dataset comprising a first set of segments, the first index data comprising a first full fingerprint for each segment in the first set of segments and a first shortened fingerprint for each segment in the first set of segments, each first shortened fingerprint for a given segment being a shortened version of a corresponding first full fingerprint of the given segment;
generating second index data for a second dataset comprising a second set of segments, the second index data comprising a second full fingerprint for each segment in the second set of segments and a second shortened fingerprint for each segment in the second set of segments, each second shortened fingerprint for a given segment being a shortened version of a corresponding second full fingerprint of the given segment; and
deduplicating the first dataset and the second dataset by removing duplicate aligned segments using full fingerprints followed by removing duplicate non-aligned segments using shortened fingerprints, the duplicate non-aligned segments being remaining segments not removed as aligned segments, the duplicate aligned segment having a same position in the first dataset and the second dataset, the duplicate non-aligned segments having different positions in the first dataset and the second dataset.
