# US 2017/0255525 A1 · Similarity based deduplication for secondary storage

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

- Number: US 2017/0255525 A1
- Document ID: US20170255525A1
- Status: Published application
- Kind: A1
- Application number: 15/057,721
- Filed: 2016-03-01
- Published: 2017-09-07
- Earliest claimed: 2016-03-01
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Joseph W. Dain; Gregory T. Kishi
- Web page: https://patentgrep.com/patent/US20170255525A1

## CPC

- G06F 11/1453: {using de-duplication of the data}
- G06F 11/1464: {for networked environments}
- G06F 16/2255: {Hash tables}
- G06F 16/24568: {Data stream processing; Continuous queries}
- G06F 2201/80: Database-specific techniques
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

For similarity based deduplication of remote data repositories, a parse module generates a rolling hash value based on a portion of an incoming stream of backup data. A comparison module compares the rolling hash value with entries stored in a rolling hash index, and in response to matching the rolling hash value with an entry in the rolling hash index, generates a strong hash value and determines if a match of the strong hash value exists in a first strong hash index. The comparison module, in response to a determination that the match does not exist in the first strong hash index, compares the strong hash value with entries in a second strong hash index in the remote data repository. A migration module, in response to a determination that the strong hash value does not match any hash entries, stores the portion of backup data as new data.

## Claims

### Claim 1

An apparatus comprising:
a parse module that generates a rolling hash value based on a portion of an incoming stream of backup data;
a comparison module that compares the rolling hash value with entries stored in a rolling hash index, and in response to matching the rolling hash value with at least one entry in the rolling hash index, generates a strong hash value and determines if a match of the strong hash value exists in a first strong hash index of a primary data repository, and where the comparison module, in response to a determination that the match does not exist in the first strong hash index, further compares the strong hash value with entries in a second strong hash index in a secondary data repository; and
a migration module that, in response to a determination that the strong hash value does not match an entry in the first strong hash index or the second strong hash index, stores the portion of the incoming stream of backup data as new data in at least one of the primary data repository or the secondary data repository.

### Claim 2 (depends on 1)

The apparatus of claim 1, further comprising an import module that imports data from the secondary data repository into the primary data repository.

### Claim 3 (depends on 2)

The apparatus of claim 2, where the import module is further configured to import the second strong hash index into the primary data repository.

### Claim 4 (depends on 3)

The apparatus of claim 3, where the import module is further configured to only import entries that correspond to the portion of the incoming stream of backup data from the second strong hash index.

### Claim 5 (depends on 4)

The apparatus of claim 4, where the import module is further configured to only import entries that are cached in the primary data repository.

### Claim 6 (depends on 1)

The apparatus of claim 1, where the migration module is further configured to retrieve from the secondary data repository, in response to the determination that the strong hash value matches an entry in the second strong hash index, data corresponding to the entry in the second strong hash index.

### Claim 7 (depends on 1)

The apparatus of claim 1, where the comparison module, in response to a determination that the rolling hash value does not match an entry in the rolling hash index of the primary data repository, queries the secondary data repository with the strong hash value to determine if the secondary data repository contains a copy of the portion of the incoming stream of backup data.

### Claim 8

A method comprising:
generating a rolling hash value based on a portion of an incoming stream of backup data;
comparing the rolling hash value with entries stored in a rolling hash index, and in response to matching the rolling hash value with at least one entry in the rolling hash index, generating a strong hash value and determining if a match of the strong hash value exists in a first strong hash index of a primary data repository, and where the comparison module, in response to a determination that the match does not exist in the first strong hash index, further comparing the strong hash value with entries in a second strong hash index in a secondary data repository; and
storing, in response to a determination that the strong hash value does not match an entry in the first strong hash index or the second strong hash index, the portion of the incoming stream of backup data as new data in at least one of the primary data repository or the secondary data repository.

### Claim 9 (depends on 8)

The method of claim 8, further comprising importing data from the secondary data repository into the primary data repository.

### Claim 10 (depends on 8)

The method of claim 8, further comprising importing the second strong hash index into the primary data repository.

### Claim 11 (depends on 10)

The method of claim 10, further comprising importing only the entries that correspond to the portion of the incoming stream of backup data from the second strong hash index.

### Claim 12 (depends on 11)

The method of claim 11, further comprising importing only entries that are cached in the primary data repository.

### Claim 13 (depends on 8)

The method of claim 8, further comprising retrieving from the secondary data repository, in response to the determination that the strong hash value matches an entry in the second strong hash index, data corresponding to the entry in the second strong hash index

### Claim 14 (depends on 8)

The method of claim 8, further comprising querying, in response to a determination that the rolling hash value does not match an entry in the rolling hash index of the primary data repository, the secondary data repository with the strong hash value to determine if the secondary data repository contains a copy of the portion of the incoming stream of backup data.

### Claim 15

A computer program product, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions readable/executable by a processor to cause the processor to execute steps comprising:
generating, by processor, a rolling hash value based on a portion of an incoming stream of backup data;
comparing the rolling hash value with entries stored in a rolling hash index, and in response to matching the rolling hash value with at least one entry in the rolling hash index, generating a strong hash value and determining if a match of the strong hash value exists in a first strong hash index of a primary data repository, and where the comparison module, in response to a determination that the match does not exist in the first strong hash index, further comparing the strong hash value with entries in a second strong hash index in a secondary data repository; and
storing, in response to a determination that the strong hash value does not match an entry in the first strong hash index or the second strong hash index, the portion of the incoming stream of backup data as new data in at least one of the primary data repository or the secondary data repository.

### Claim 16 (depends on 15)

The computer program product of claim 15, where the steps further comprise importing data from the secondary data repository into the primary data repository.

### Claim 17 (depends on 16)

The computer program product of claim 16, where the steps further comprise importing the second strong hash index into the primary data repository.

### Claim 18 (depends on 17)

The computer program product of claim 17, further comprising importing only the entries that correspond to the portion of the incoming stream of backup data from the second strong hash index.

### Claim 19 (depends on 18)

The computer program product of claim 18, further comprising importing only entries that are cached in the primary data repository.

### Claim 20 (depends on 15)

The computer program product of claim 15, further comprising querying, in response to a determination that the rolling hash value does not match an entry in the rolling hash index of the primary data repository, the secondary data repository with the strong hash value to determine if the secondary data repository contains a copy of the portion of the incoming stream of backup data.
