# US 8,280,860 B2 · Method for increasing deduplication speed on data streams fragmented by shuffling

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

- Number: US 8,280,860 B2
- Document ID: US8280860B2
- Status: Granted
- Kind: B2
- Application number: 12/946,779
- Filed: 2010-11-15
- Published: 2012-05-17
- Granted: 2012-10-02
- Earliest claimed: 2010-11-15
- Assignees: Quantum Corporation
- Inventors: Stephen P. Spackman; Don Doerner
- Web page: https://patentgrep.com/patent/US8280860B2

## CPC

- G06F 16/1756: {based on delta files}
- G06F 3/0641: {De-duplication techniques}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer-implemented method for deduplicating an incoming data sequence can include the steps of storing signature values for a plurality of data blocklets of a parent data sequence in a deduplication index, sequentially storing signature values for at least some of the plurality of data blocklets of the parent data sequence in a first storage location outside of the deduplication index, determining that a first data blocklet in the incoming data sequence is absent from the parent data sequence, storing a signature value for the first data blocklet in a second storage location outside of the deduplication index, storing a guarded link linking the first data blocklet to the second data blocklet into the second storage location, determining that a second data blocklet that follows the first data blocklet in the incoming data sequence is present in the parent data sequence, the second data blocklet having a signature value that is stored in the first storage location, and copying at least a portion of the contents of the first storage location and the second storage location into a cache to expedite access during deduplication of the incoming data sequence.

## Claims

### Claim 1

A computer-implemented method for deduplicating an incoming data sequence, the method comprising the steps of:
storing signature values for a plurality of data blocklets of a parent data sequence in a deduplication index;
sequentially storing signature values for at least some of the plurality of data blocklets of the parent data sequence in a first storage location outside of the deduplication index;
determining that a first data blocklet in the incoming data sequence is absent from the parent data sequence;
storing a signature value for the first data blocklet in a second storage location outside of the deduplication index;
determining that a second data blocklet that follows the first data blocklet in the incoming data sequence is present in the parent data sequence, the second data blocklet having a signature value that is stored in the first storage location; and
copying at least a portion of the contents of the second storage location into a cache to expedite access during deduplication of the incoming data sequence.

### Claim 2 (depends on 1)

The method of claim 1 wherein the cache is included as part of a computer usable volatile memory.

### Claim 3 (depends on 1)

The method of claim 1 wherein at least one of the storage locations includes a cluster header.

### Claim 4 (depends on 1)

The method of claim 1 wherein each of the storage locations includes a cluster header.

### Claim 5 (depends on 1)

The method of claim 1 wherein the second storage location includes a cluster header that is designated to only receive data blocklets that are absent from the parent data sequence.

### Claim 6 (depends on 1)

The method of claim 1 wherein the first data blocklet immediately follows another data blocklet that was found to be present in the parent data sequence.

### Claim 7 (depends on 1)

The method of claim 1 wherein the second data blocklet immediately follows the first data blocklet in the incoming data sequence.

### Claim 8 (depends on 1)

The method of claim 1 wherein the second data blocklet is spaced apart from the first data blocklet in the incoming data sequence by at least one other data blocklet.

### Claim 9 (depends on 1)

The method of claim 1 wherein the step of copying includes copying the entire contents of the second storage location into the cache.

### Claim 10 (depends on 1)

The method of claim 1 further comprising the step of storing a link in the first storage location, the link linking one of the data blocklets of the parent data sequence to the first data blocklet.

### Claim 11 (depends on 1)

The method of claim 1 further comprising the step of storing a guarded link in the second storage location, the guarded link linking the first data blocklet to the second data blocklet.

### Claim 12 (depends on 11)

The method of claim 11 wherein the step of copying includes copying the guarded link from the second storage location into the cache.

### Claim 13 (depends on 1)

A deduplication engine of a computer system, the deduplication engine utilizing the method of claim 1 to deduplicate the incoming data sequence.

### Claim 14

A computer-implemented method for deduplicating an incoming data sequence, the method comprising the steps of:
storing signature values for a plurality of data blocklets of a parent data sequence in a deduplication index;
sequentially storing signature values for at least some of the plurality of data blocklets of the parent data sequence in a first storage location outside of the deduplication index;
locating a transition data blocklet that is absent from the parent data sequence;
sequentially storing a signature value for the transition data blocklet into a second storage location outside the deduplication index;
determining that a signature value for a data blocklet that follows the transition data blocklet is included in the first storage location; and
copying at least a portion of the contents of the second storage location into a cache to expedite access during deduplication of the incoming data sequence.

### Claim 15 (depends on 14)

The method of claim 14 wherein the data blocklet that follows the transition data blocklet is immediately adjacent to the transition data blocklet.

### Claim 16 (depends on 14)

The method of claim 14 wherein the cache is included as part of a computer usable volatile memory.

### Claim 17 (depends on 14)

The method of claim 14 wherein at least one of the storage locations includes a cluster header.

### Claim 18 (depends on 14)

The method of claim 14 wherein each of the storage locations includes a cluster header.

### Claim 19 (depends on 14)

The method of claim 14 wherein the second storage location includes a cluster header that is designated to only receive data blocklets that are absent from the parent data sequence.

### Claim 20 (depends on 14)

The method of claim 14 further comprising the step of determining that a data blocklet that immediately precedes the transition data blocklet in the incoming data sequence is present in the parent data sequence.

### Claim 21 (depends on 14)

The method of claim 14 wherein the step of copying includes copying the entire contents of the second storage location into the cache.

### Claim 22 (depends on 14)

The method of claim 14 further comprising the step of storing a link in the first storage location, the link linking one of the data blocklets of the parent data sequence to the transition data blocklet.

### Claim 23 (depends on 14)

The method of claim 14 further comprising the step of storing a guarded link in the second storage location, the guarded link linking the transition data blocklet to the data blocklet that follows the transition data blocklet.

### Claim 24 (depends on 23)

The method of claim 23 wherein the step of copying includes copying the guarded link from the second storage location into the cache.

### Claim 25 (depends on 14)

A deduplication engine of a computer system, the deduplication engine utilizing the method of claim 14 to deduplicate the incoming data sequence.

### Claim 26

A computer-implemented method for deduplicating an incoming data sequence, the method comprising the steps of:
storing signature values for a plurality of data blocklets of a parent data sequence in a deduplication index;
sequentially storing signature values for at least some of the plurality of data blocklets of the parent data sequence in a first cluster header outside of the deduplication index;
locating a transition data blocklet that is absent from the parent data sequence;
determining that a data blocklet that immediately precedes the transition data blocklet in the incoming data sequence is present in the parent data sequence;
determining that a signature value for a data blocklet that immediately follows the transition data blocklet is included in the first cluster header;
storing a signature value for the transition data blocklet into a second cluster header that is designated to receive only transition data blocklets that are absent from the parent data sequence;
storing a link in a first storage location, the link linking one of the data blocklets of the parent data sequence to the transition data blocklet;
storing a guarded link in the second cluster header, the guarded link linking the transition data blocklet to the data blocklet that follows the transition data blocklet; and
copying the contents of the second cluster header into a cache that is embedded in a computer usable volatile memory to expedite access during deduplication of the incoming data sequence.
