Data deduplication with adaptive erasure code redundancy

• US 9,692,452 B2
• Filed: 08/03/2016
• Issued: 06/27/2017
• Est. Priority Date: 07/09/2014
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Arslan, Suayb Sefik, Lee, Jaewook, Goker, Turguy, Wideman, Roderick B.
• Primary Examiner(s): Ton, David
• Application Number:
  US15/227,285
• Publication Number:
  US 20160344413A1
• Time in Patent Office: 328 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/3707 Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code
• CPC Class Codes: 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
• CPC Class 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

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

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:

accessing unique data produced by a data deduplication system;

identifying a property of the unique data, and

manipulating, based at least in part on the property, a generator matrix representation of an encoding graph associated with an erasure encoder, where manipulating the generator matrix includes controlling a number of elements in the generator matrix or controlling the value of one or more elements in the generator matrix, where a non-zero entry in the generator matrix represents a node/edge probability distribution;

generating, using the erasure encoder, a set of W erasure code symbols for the unique data, where the erasure code symbols are generated according to an X/Y erasure code policy, W, X, and Y being integers, W being greater than or equal to X, W being less than or equal to Y, and where W, X, or Y depend, at least in part, on the property of the unique data, where W, X, or Y are directly proportional to the property; and

selectively storing members of the set of W erasure code symbols on Z different data storage devices, where Z is a function of a second property of the unique data, where the second property includes a size of the unique data, an age of the unique data, a cost to replace the unique data, or a user-assigned value, where the value of the second property may vary over time, Z being an integer.

2. The non-transitory computer-readable storage medium of claim 1, where the number of elements or the value of the one or more elements cause erasure code symbols produced by the erasure encoder to account for chunk level probability requirements associated with the unique data.

3. The non-transitory computer-readable storage medium of claim 1, where the property of the unique data is a probability of failure associated with the unique data.

4. The non-transitory computer-readable storage medium of claim 1, where manipulating the generator matrix controls, at least in part, the size or composition of an erasure code produced by the erasure encoder.

5. The non-transitory computer-readable storage medium of claim 4, where the composition of an erasure code controls, at least in part, a relevance of the erasure code to a selected portion of the unique data.

6. The non-transitory computer-readable storage medium of claim 5, where the composition of the erasure code includes a number of connections between a portion of the unique data an erasure codeword.

7. The non-transitory computer-readable storage medium of claim 1, the method comprising generating erasure code symbols from the unique data based, at least in part, on the generator matrix.

8. The non-transitory computer-readable storage medium of claim 1, where the erasure encoder employs a systematic erasure code, a rateless erasure code, or a systematic rateless erasure code.

9. The non-transitory computer-readable storage medium of claim 1, the method further comprising:

upon determining that the property of the unique data has changed,

selectively manipulating the generator matrix based, at least in part, on the property of the unique data that has changed.

10. The non-transitory computer-readable storage medium of claim 1, where the data deduplication system is a variable-length, block level system.

11. An apparatus, comprising:

a processor;

a memory;

a set of logics; and

an interface that connects the set of logics, the memory, and the processor, the set of logics comprising;

a first logic that manipulates a generator matrix representation of an encoding graph associated with an erasure encoder based on a first attribute of a message received from a data deduplication system, where the first attribute describes an importance of the message to the data deduplication system, a size of the message, an amount to be spent protecting the message, or an age of the message;

a second logic that produces, using the erasure encoder, a set of N erasure code symbols for the message, where the message has K symbols, where N is a function of the first attribute, N and K being integers, N being greater than K, where a member of the set of N erasure code symbols is a systematic, rateless erasure code; and

a third logic that selectively stores members of the set of N erasure code symbols on Z different data storage devices, where Z is a function of a second attribute of the message, Z being an integer.

12. The apparatus of claim 11, where the first logic controls a number of elements in the generator matrix or controls the value of one or more elements in the generator matrix, and where a non-zero entry in the generator matrix represents a node/edge probability distribution.

13. The apparatus of claim 11 further comprising a fourth logic that controls the first logic to selectively manipulate the generator matrix upon determining that the first attribute has changed.

14. The apparatus of claim 11 where the second attribute includes a size of the message, an age of the message, a cost to replace the message, or a user-assigned value, where the value of the second attribute may vary over time.

15. A method for storing de-duplicated data in a data storage system comprising:

accessing a message produced by a data deduplication system;

identifying a property of the message;

manipulating, based at least in part on the property, a generator matrix representation of an encoding graph associated with an erasure encoder;

generating, using the erasure encoder, a set of erasure code symbols for the message, where the erasure code symbols are generated according to a code rate that defines a minimum number of encoded symbols needed to recreate the message and a total number of encoded symbols that can be produced for the message, where the number of erasure code symbols in the set of erasure code symbols is greater than the minimum number of encoded symbols needed to recreate the message, where the number of erasure code symbols in the set of erasure code symbols is less than the total number of encoded symbols that can be produced for the message, and where the number of erasure code symbols in the set of erasure code symbols, the minimum number of encoded symbols needed to recreate the message, or the total number of encoded symbols that can be produced for the message depend, at least in part, on the property of the message.