# US 2014/0156607 A1 · Index for deduplication

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

- Number: US 2014/0156607 A1
- Document ID: US20140156607A1
- Status: Published application
- Kind: A1
- Application number: 14/234,146
- Filed: 2011-10-18
- Published: 2014-06-05
- Earliest claimed: 2011-10-18
- Assignees: Hewlett-Packard Developement Company, L.P.
- Applicants: Hewlett-Packard Developement Company, L.P.
- Inventors: Mark David Lillibridge
- Web page: https://patentgrep.com/patent/US20140156607A1

## 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/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Techniques for deduplication include an index, a receiver module, and an indexer module. The index can store information about data blocks. The receiver module can receive a data block. The indexer module can check whether information about the data block is in the index, and if information about the data block is not found in the index, then it can make a random decision about whether to store information about the data block in the index, and if the random decision is to store information about the data block in the index, then it can store information about the data block in the index.

## Claims

### Claim 1

A computer system for deduplication comprising:
an index to store information about date blocks;
a receiver module to receive a data block; and
an indexer module to:
check whether information about the data block is in the index, and
if information about the data block is not found in the index, then make a random decision about whether to store information about the data block in the index, and if the random decision is to store information about the data block in the index, then store information about the data block in the index.

### Claim 2 (depends on 1)

The computer system of claim 1, wherein the random decision about whether to store information about the data block in the index is made with a predetermined probability.

### Claim 3 (depends on 1)

The computer system of claim 1, wherein the random decision about whether to store information about the data block in the index is based on an output of a random number generator.

### Claim 4 (depends on 1)

The computer system of claim 1, wherein the indexer module is further configured to calculate a hash value based on the data block and check whether the hash value is in the index.

### Claim 5 (depends on 1)

The computer system of claim 1 wherein the information about the data block stored in the index comprises a hash value of the data block and a pointer to a physical address of the data block in storage.

### Claim 6 (depends on 1)

The computer system of claim 1, wherein the indexer module is configured to remove the stored information about a date block in the index based on a random decision made with a predetermined probability.

### Claim 7

A method of deduplication comprising:
receiving a data block;
checking whether information about the data block is in an index; and
if information about the data block is not found in the index, than making a random decision about whether to store information about the data block in the index; and if the random decision is to store information about the data block in the index, then storing information about the data block in the index.

### Claim 8 (depends on 7)

The method of claim 7, wherein the random decision about whether to store information about the data block in the index is made with a predetermined probability.

### Claim 9 (depends on 7)

The method of claim 7, wherein the random decision about whether to store information about the data block in the index is based on an output of a random number generator.

### Claim 10 (depends on 7)

The method of claim 7, further comprising calculating a hash value based on the data block and checking whether the hash value is in the index.

### Claim 11 (depends on 7)

The method of claim 7, wherein the information about the data block stored in the index comprises a hash value of the data block and a pointer to a physical address of the data block in storage.

### Claim 12 (depends on 7)

The method of claim 7, further comprising removing the stored information about a data block in the index based on a random decision made with a predetermined probability.

### Claim 13

A computer readable medium comprising code for deduplication that if executed causes a processor to:
receive a data block;
check whether information about the data block is in an index; and
if information about the data block is not found in the index, make a random decision about whether to store information about the data block in the index, and if the random decision is to store information about the data block in the index, store information about the data block in the index.

### Claim 14 (depends on 13)

The computer readable medium of claim 13 further comprising code that if executed causes a processor to:
make the random decision about whether to store information about the data block in the index with a predetermined probability.

### Claim 15 (depends on 13)

The computer readable medium of claim 13 further comprising code that if executed causes a processor to:
remove the stored information about a data block in the index based on a random decision made with a predetermined probability.