Data deduplication with adaptive erasure code redundancy

• US 9,503,127 B2
• Filed: 07/09/2014
• Issued: 11/22/2016
• 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: Wideman, Roderick B, Lee, Jaewook, Arslan, Suayb Sefik, Goker, Turguy
• Primary Examiner(s): Ton, David
• Application Number:
  US14/326,774
• Publication Number:
  US 20160013815A1
• Time in Patent Office: 867 Days
• US Class Current: 1/1
• 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 cause the computer to perform a method, the method comprising:

accessing a message produced by a data deduplication system;

identifying a property of the message, and

generating W erasure code symbols for the message, 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 a property of the message.

2. The non-transitory computer-readable storage medium of claim 1, where the property is the importance of the message to the data deduplication system.

3. The non-transitory computer-readable medium of claim 2, where the importance is related to a number of reference counts associated with the message.

4. The non-transitory computer-readable storage medium of claim 2, where W, X, or Y are directly proportional to the property.

5. The non-transitory computer-readable storage medium of claim 2, where the symbol size of an erasure code in the W erasure code symbols is a function of the size of the message.

6. The non-transitory computer-readable storage medium of claim 2, the method comprising distributing members of the W erasure code symbols to Z different data stores according to a distribution policy, Z being an integer, Z being less than or equal to Y, where Z depends, at least in part, on the property.

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

8. The non-transitory computer-readable storage medium of claim 1, where the erasure codes are systematic erasure codes.

9. The non-transitory computer-readable storage medium of claim 8, where the erasure codes are rateless erasure codes.

10. The non-transitory computer-readable medium of claim 8, where the systematic erasure codes are at least partially parity based, and where the amount of parity generated by the X/Y erasure code policy depends, at least in part, on the property.

11. The non-transitory computer-readable medium of claim 1, where the message is a unique chunk produced by the data deduplication system.

12. The non-transitory computer-readable medium of claim 1, where the message is a group of unique chunks produced by the data deduplication system.

13. The non-transitory computer-readable medium of claim 1, comprising selectively grouping a set of unique chunks produced by the data deduplication system into the message.

14. The non-transitory computer-readable medium of claim 1, where a relationship between the property and the X/Y erasure code policy is controlled, at least in part, by a user-defined rule or by an automated rule.

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

upon determining that the property of the message has changed,

selectively updating the number of erasure code symbols stored for the message.

16. The non-transitory computer-readable medium of claim 15, the method comprising:

upon determining that the property indicates that the message has become more valuable, selectively increasing the number of erasure code symbols stored for the message.

17. The non-transitory computer-readable medium of claim 16, where selectively increasing the number of erasure code symbols stored for the message includes generating one or more additional erasure code symbols for the message.

18. The non-transitory computer-readable medium of claim 17, where the one or more additional erasure code symbols are generated using a generator matrix used to generate original erasure codes associated with the message.

19. The non-transitory computer-readable medium of claim 15, the method comprising:

upon determining that the property indicates that the message has become less valuable, selectively decreasing the number of erasure code symbols stored for the message.

20. The non-transitory computer-readable medium of claim 19, where selectively decreasing the number of erasure code symbols stored for the message includes deleting one or more erasure code symbols stored for the message.

21. The non-transitory computer-readable medium of claim 20, where deleting one or more erasure code symbols stored for the message includes logically deleting an erasure code symbol.

22. An apparatus, comprising:

a processor;

a memory;

a set of logics; and

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

the set of logics comprising;

a first logic that produces a set of n erasure code symbols for a message received from a data deduplication system, where the message has k symbols, where n is a function of a first attribute of the message, n and k being numbers, n>

k;

a second logic that selectively stores members of the n erasure code symbols on z different data storage devices, where z is a function of a second attribute of the message, z being a number.

23. The apparatus of claim 22, 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.

24. The apparatus of claim 22, where the second 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.

25. The apparatus of claim 22, where the message is a single unique chunk or a collection of unique chunks.

26. The apparatus of claim 22, where the symbols are systematic, rateless erasure codes.

27. The apparatus of claim 22, where the size of a member of the n erasure code symbols is a function of the size of the k symbols.

28. The apparatus of claim 22, where the composition of a member of the n erasure code symbols is a function of the first attribute or the second attribute.

29. The apparatus of claim 22, comprising a third logic that adapts how n is selected as a function of the first attribute.

30. The apparatus of claim 22, comprising a fourth logic that adapts how z is selected as a function of the second attribute.

31. The apparatus of claim 22, comprising a fifth logic that controls the first logic to selectively recalculate n upon determining that the first attribute has changed.

32. The apparatus of claim 31, where the fifth logic controls the second logic to selectively recalculate z upon determining that the second attribute has changed.