Selection of erasure code parameters for no data repair

• US 8,788,913 B1
• Filed: 02/22/2012
• Issued: 07/22/2014
• Est. Priority Date: 12/30/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Xin, Qin, Zhang, Feng, Bao, Qi
• Primary Examiner(s): Bhatia, Ajay
• Assistant Examiner(s): NGUYEN, THIEN DANG
• Application Number:
  US13/402,324
• Time in Patent Office: 881 Days
• Field of Search: None
• US Class Current: 714/776
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• 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

An improved data storage technique achieves a desired level of reliability by providing sufficient redundancy in erasure coded data to maintain the data, without repair, for a prescribed period of time. The improved technique employs a newly devised, continuous-time Markov chain model. The model can be applied in computerized systems to establish erasure coding parameters for storing and reliably maintaining data for a designated period of time, without any need to repair the data to reestablish an original or previous level of erasure coding redundancy.

Claims

1. A method of storing a set of data including at least one chunk of data, comprising:

receiving a value that designates a desired retention period over which a chunk of the set of data is to be retained;

selecting a pair of erasure coding parameters, N and K, wherein N represents a total number of fragments for storing the chunk and K represents a minimum number of the N fragments that are needed to ensure that the chunk can be recovered without data loss;

calculating a mean time to data loss (MTTDL) of the chunk by applying N and K in an equation for MTTDL;

testing whether the calculated MTTDL is at least as great as the designated retention period;

repeating the selecting, calculating and testing for at least one different value pair of N and K until values of N and K are identified for which the calculated MTTDL is at least as great as the designated retention period;

conducting, by a computing node on a network, an erasure coding operation on the chunk using erasure coding parameters N′ and

K′

, wherein N′ and

K′

are each at least as great as the respective identified values of N and K; and

storing the N′

fragments in multiple storage units, including at least one storage unit accessible to the computing node over the network.

2. The method as recited in claim 1, further comprising receiving a designated redundancy factor (R), wherein selecting the pair of erasure coding parameters includes choosing a value of K and calculating an accompanying value of N that meets the designated redundancy factor.

3. The method as recited in claim 2, wherein calculating the accompanying value of N includes assigning N to be the first integer that is at least as great as K*R.

4. The method as recited in claim 2, wherein selecting the pair of erasure coding parameters further includes beginning with a predetermined value of K for a first selection and increasing the value of K on successive selections.

5. The method as recited in claim 3, wherein K is incremented by one on successive selections to ensure that the identified values of N and K include the minimum value of K for which MTTDL is at least as great as the designated retention period.

6. The method as recited in claim 2, wherein calculating the MTTDL includes applying a model that prohibits damaged fragments from being repaired, wherein each failure of a fragment represented by the model reduces the number of undamaged fragments until only K−

1 undamaged fragments remain.

7. The method as recited in claim 6, wherein the MTTDL is computed using an equation drawn from a continuous-time Markov chain model depicting multiple states each indicating a number of failures ranging from zero to N−

K+1.

8. The method as recited in claim 7, further comprising receiving a mean time to failure (MTTF) applicable to a number of disks used to store the chunk, wherein calculating the MTTDL includes applying the MTTF and the number of disks used to store the chunk.

9. The method as recited in claim 8, wherein MTTDL is computed using the following equation:

10. The method as recited in claim 1, wherein the set of data includes a file, and wherein an instance of the testing includes determining whether the values of N and K used during the instance of the testing are sufficient to meet a desired level of availability of the file.

11. The method as recited in claim 10, further comprising increasing the value of K responsive to the values of N and K not begin sufficient to meet the desired level of availability of the file.

12. The method as recited in claim 10, wherein the file includes the at least one chunk and wherein the method further comprises computing the availability of the file using the following equation:

13. The method as recited in claim 10, wherein a value of K is first identified to meet the desired file availability and later increased until the calculated MTTDL meets the designated retention period.

14. The method as recited in claim 1, further comprising, prior to the storing:

running a data storage simulator multiple times using the identified values of N and K to determine whether the simulator indicates that data loss occurs within a predefined number of iterations of the data storage simulator; and

increasing K responsive to the simulator indicating that data loss occurs within the predetermined number of iterations of the data storage simulator.

15. The method as recited in claim 1, wherein the multiple storage units include N′

storage units, wherein each of the N′

storage units resides on a different computing node of the network.

16. A computerized apparatus, comprising:

a set of processors; and

memory, coupled to the set of processors, the memory arranged to store instructions executable by the set of processors,

wherein the set of processors executing instructions from the memory forms a specialized circuit arranged to;

receive a value that designates a desired retention period over which a chunk of a set of data is to be retained;

select a pair of erasure coding parameters, N and K, wherein N represents a total number of fragments for storing the chunk and K represents a minimum number of the N fragments that are needed to ensure that the chunk can be recovered without data loss;

calculate a mean time to data loss (MTTDL) of the chunk by applying N and K in an equation for MTTDL;

test whether the calculated MTTDL is at least as great as the designated retention period;

repeatedly select, calculate and test for at least one different value pair of N and K until values of N and K are identified for which the calculated MTTDL is at least as great as the designated retention period;

conduct an erasure coding operation on the chunk using erasure coding parameters N′ and

K′

, wherein N′ and

K′

are each at least as great as the respective identified values of N and K; and

store the N′

fragments in at least one storage unit.

17. The computerized apparatus as recited in claim 16, wherein the specialized circuit is further arranged to receive a designated redundancy factor (R), wherein, in being arranged to select the pair of erasure coding parameters, the specialized circuit is further arranged to choose a value of K and calculate an accompanying value of N, wherein N is the first integer that is at least as great as K*R.

18. The computerized apparatus as recited in claim 17, wherein the specialized circuit is further arranged to compute MTTDL using the following equation:

19. The computerized apparatus as recited in claim 18, wherein the specialized circuit is further arranged to compute a file availability of a file of the set of data that includes the at least one chunk using the following equation:

20. A computer program product including non-transitory computer readable medium having instructions which, when executed by a set of processors of a computerized apparatus, cause the set of processors to perform a method of storing a set of data including at least one chunk of data, the method comprising:

receiving a value that designates a desired retention period over which a chunk of the set of data is to be retained;

selecting a pair of erasure coding parameters, N and K, wherein N represents a total number of fragments for storing the chunk and K represents a minimum number of the N fragments that are needed to ensure that the chunk can be recovered without data loss;

calculating a mean time to data loss (MTTDL) of the chunk by applying N and K in an equation for MTTDL;

testing whether the calculated MTTDL is at least as great as the designated retention period;

repeating the selecting, calculating and testing for at least one different value pair of N and K until values of N and K are identified for which the calculated MTTDL is at least as great as the designated retention period;

conducting an erasure coding operation on the chunk using erasure coding parameters N′ and

K′

, wherein N′ and

K′

are each at least as great as the respective identified values of N and K; and

storing the N′

fragments in at least one storage unit.