# US 10,484,016 B2 · Data deduplication with adaptive erasure code redundancy

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

- Number: US 10,484,016 B2
- Document ID: US10484016B2
- Status: Granted
- Kind: B2
- Application number: 15/602,726
- Filed: 2017-05-23
- Published: 2017-09-07
- Granted: 2019-11-19
- Earliest claimed: 2014-07-09
- Assignees: Quantum Corporation
- Applicants: Quantum Corporation
- Inventors: Roderick B. Wideman; Suayb Sefik Arslan; Jaewook Lee; Turguy Goker
- Web page: https://patentgrep.com/patent/US10484016B2

## CPC

- H03M 13/154: {Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/064: {Management of blocks}
- G06F 3/0641: {De-duplication techniques}
- G06F 3/0673: {Single storage device}
- G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems}
- G06F 11/1453: {using de-duplication of the data}
- G06F 16/1752: {based on file chunks}
- H03M 13/3707: {Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code}
- H03M 13/373: {with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes}
- H03M 13/3761: {using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Example apparatus and methods combine erasure coding with data deduplication to simultaneously reduce the overall redundancy in data while increasing the redundancy of unique data. In one embodiment, an efficient representation of a data set is produced by deduplication. The efficient representation reduces duplicate data in the data set. Redundancy is then added back into the data set using erasure coding. The redundancy that is added back in adds protection to the unique data associated with the efficient representation. How much redundancy is added back in and what type of redundancy is added back in may be controlled based on an attribute (e.g., value, reference count, symbol size, number of symbols) of the unique data. Decisions concerning how much and what type of redundancy to add back in may be adapted over time based, for example, on observations of the efficiency of the overall system.

## Claims

### Claim 1

A non-transitory computer-readable storage medium storing computer-executable instructions that when executed by a computer control the computer to perform a method, the method comprising:
generating, by a processor, a characterization of segments of a plurality of segments with failure probabilities associated with the segments that indicate a likelihood of failure of the segments;
parsing, by a processor, the plurality of segments to generate a plurality of original chunks;
deduplicating, by a processor, the plurality of original chunks to generate a plurality of unique chunks;
grouping, by a processor, the plurality of unique chunks to form grouped chunks;
encoding, by a processor, the grouped chunks to generate a desired number of erasure code symbols that satisfy the failure probabilities associated with the segments; and
selectively storing members of the desired number of erasure code symbols on a number of storage devices.

### Claim 2 (depends on 1)

The non-transitory computer-readable storage medium of claim 1, further comprising:
calculating, by a processor, attributes of unique chunks of the plurality of unique chunks based, at least in part, on the failure probabilities; and where the encoding is based, at least in part, on the attributes being constrained by the failure probabilities.

### Claim 3 (depends on 2)

The non-transitory computer-readable storage medium of claim 2, where importance is an attribute of the attributes, and where importance is calculated based on a reference count to the data in a unique chunk.

### Claim 4 (depends on 2)

The non-transitory computer-readable storage medium of claim 2, where the attributes are variable, and where the desired number of erasure code symbols changes when an attribute changes.

### Claim 5 (depends on 2)

The non-transitory computer-readable storage medium of claim 2, where the number of storage devices is based, at least in part, on the attributes of the unique chunks.

### Claim 6 (depends on 1)

The non-transitory computer-readable storage medium of claim 1, where an erasure code symbol represents a number of connections between at least one segment and an erasure code symbol.

### Claim 7 (depends on 1)

The non-transitory computer-readable storage medium of claim 1, where the encoding is based on information stored in a generator matrix, and the method further comprising:
identifying, by a processor, attributes of unique chunks of the plurality of unique chunks; and
manipulating, by a processor, the generator matrix to control, at least in part, a size or composition of an erasure code symbol of the desired number of erasure code symbols.

### Claim 8

A method comprising:
generating, by a processor, a characterization of segments of a plurality of segments with failure probabilities associated with the segments that indicate a likelihood of failure of the segments;
parsing, by a processor, the plurality of segments to generate a plurality of original chunks,
deduplicating, by a processor, the plurality of original chunks to generate a plurality of unique chunks;
calculating, by a processor, attributes of unique chunks of the plurality of unique chunks based, at least in part, on the failure probabilities associated with corresponding segments;
grouping, by a processor, the plurality of unique chunks to form a grouped chunk;
encoding, by a processor, the grouped chunk to generate a desired number of erasure code symbols based, at least in part, on the attributes being constrained by the failure probabilities; and
selectively storing members of the desired number of erasure code symbols on a number of storage devices, where the number of storage devices is based, at least in part, on the attributes for the unique chunks.

### Claim 9 (depends on 8)

The method of claim 8, where the attributes include an importance of a unique chunk, a size of the unique chunk, or an age of the unique chunk.

### Claim 10 (depends on 8)

The method of claim 8, where importance is an attribute, and where importance is calculated, by a processor, based on a reference count to the data in a unique chunk.

### Claim 11 (depends on 8)

The method of claim 8, where the attributes are variable, and where the desired number of erasure code symbols changes when an attribute changes.

### Claim 12 (depends on 8)

The method of claim 8, where the desired number of erasure code symbols is greater than or equal to a minimum threshold of erasure code symbols but less than the total possible erasure codes.

### Claim 13 (depends on 12)

The method of claim 12, where the desired number of erasure code symbols, the minimum threshold of erasure code symbols, and the total possible erasure codes are directly proportional to a variation of the attributes.

### Claim 14 (depends on 8)

The method of claim 8, where the encoding is based on information stored in a generator matrix, the method further comprising:
identifying, by a processor, attributes of unique chunks of the plurality unique chunks; and
manipulating, by a processor, the generator matrix to control, at least in part, a size or composition of an erasure code symbol of the desired number of erasure code symbols.

### Claim 15

An apparatus, comprising:
a number of storage devices; and
a processor configured to:
generate a characterization of segments of a plurality of segments with failure probabilities associated with the segments that indicate a likelihood of failure of segments;
parse the plurality of segments to generate a plurality of original chunks,
deduplicate the plurality of original chunks to generate a plurality of unique chunks;
calculate attributes of unique chunks of the plurality of unique chunks based, at least in part, on the failure probabilities;
group the plurality of unique chunks to form at least one grouped chunk;
encode the at least one grouped chunk to generate a desired number of erasure code symbols that satisfy the failure probabilities associated with the segments, where the encoding is based, at least in part, on the attributes being constrained by the failure probabilities; and
selectively store members of the desired number of erasure code symbols on the number of storage devices, where the number of storage devices is based, at least in part, on the attributes for the unique chunks.

### Claim 16 (depends on 15)

The apparatus of claim 15, where importance is an attribute of the attributes, and where importance is calculated based on a reference count to the data in a unique chunk.

### Claim 17 (depends on 15)

The apparatus of claim 15, where the attributes are variable, and where the desired number of erasure code symbols changes when an attribute changes.

### Claim 18 (depends on 15)

The apparatus of claim 15, where an erasure code symbol represents a number of connections between at least one segment and an erasure code symbol.

### Claim 19 (depends on 15)

The apparatus of claim 15, where the encoding is based on information stored in a generator matrix, and where the processor is further configured to:
identify attributes of unique chunks of the plurality unique chunks; and
manipulate the generator matrix to control, at least in part, a size or composition of an erasure code symbol of the desired number of erasure code symbols.

### Claim 20 (depends on 19)

The apparatus of claim 19, where a non-zero entry in the generator matrix represents a node/edge probability distribution.