High Reliability Erasure Code Distribution

Patent metadata

Field	Value
Publication number	US-2015378820-A1
Application number	US-201414314977-A
Country	US
Kind code	A1
Filing date	Jun 25, 2014
Priority date	Jun 25, 2014
Publication date	Dec 31, 2015
Grant date	—

Abstract

Example apparatus and methods treat some erasure codes differently than other erasure codes. For example, erasure codes that are only involved in error-recovery may never be read and thus may be stored using a different approach than erasure codes that are involved in more regular data reading. If different types of data stores are available, then the erasure codes that are more likely to be read may be stored in data stores having a first (e.g., higher, faster) type of read performance while the erasure codes that are less likely to be read may be stored in data stores having a second (e.g., lower, slower, less expensive) type of read performance. Different data stores may be located on different data storage devices. Different data stores may even be located on a single data storage device.

First claim

What is claimed is:

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 set of n erasure codes generated for a message having k symbols, n and k being numbers, n being greater than or equal to k; identifying a first data store that is available to store members of the set of n erasure codes; identifying a second data store that is available to store members of the set of n erasure codes; identifying a property associated with both the first data store and the second data store; identifying a first value for the property for the first data store; identifying a second value for the property for the second data store; selecting a first subset of the set of erasure codes to store in the first data store based, at least in part, on the first value or the second value, and selecting a second subset of the set of erasure codes to store in the second data store based, at least in part, on the first value or the second value.

2 . The non-transitory computer-readable storage medium of claim 1 , where the property is a speed with which an erasure code can be read from a data store.

3 . The non-transitory computer-readable medium of claim 1 , where the property is a speed with which an erasure code can be written to a data store.

4 . The non-transitory computer-readable storage medium of claim 1 , where the property is a combination of a speed with which an erasure code can be read from a data store and a speed with which an erasure code can be written to a data store.

5 . The non-transitory computer-readable storage medium of claim 1 , where the property is a cost for storing an erasure code on a data store.

6 . The non-transitory computer-readable storage medium of claim 1 , where a member of the set of n erasure codes has an associated read probability that describes how likely the member is to be read.

7 . The non-transitory computer-readable storage medium of claim 6 , where the first subset is selected so that members of the set of n erasure codes having a read probability above a threshold are stored on the first data store.

8 . The non-transitory computer-readable storage medium of claim 7 , where the second subset is selected so that members of the set of n erasure codes having a read probability below a threshold are stored on the second data store.

9 . The non-transitory computer-readable storage medium of claim 1 ,
where the set of n erasure codes are systematic erasure codes, where a k sized subset of the n erasure codes are erasure codes from which the message m can be reconstructed without decoding an erasure code, and where an n-k sized subset of the n erasure codes that is mutually exclusive with the k sized subset are erasure codes from which the message m can be reconstructed based, at least in part, on decoded members of the n-k sized subset.

10 . The non-transitory computer-readable storage medium of claim 9 , where the first subset is the k sized subset and the second subset is the n-k sized subset.

11 . The non-transitory computer-readable storage medium of claim 9 , where the first subset includes at least the k sized subset and the second subset includes at least the n-k sized subset.

12 . The non-transitory computer-readable storage medium of claim 11 ,
where a member of the set of n erasure codes has an associated read probability that describes how likely the member is to be read, where the first subset is selected so that members of the set of n erasure codes having a read probability above a threshold are stored on the first data store, and where the second subset is selected so that members of the set of n erasure codes having a read probability below a threshold are stored on the second data store.

13 . The non-transitory computer-readable storage medium of claim 1 , the method comprising causing the first subset to be stored on the first data store and causing second subset to be stored on the second data store.

14 . The non-transitory computer-readable storage medium of claim 1 , the method comprising selectively powering down the second data store after the second subset has been stored on the second data store.

15 . The non-transitory computer-readable storage medium of claim 1 , where the first data store and the second store are located on the same data storage device.

16 . The non-transitory computer-readable storage medium of claim 1 , where the first data store is located on cylinders on the outer half of a hard disk drive and the second data store is located on cylinders on the inner half of the hard disk drive.

17 . The non-transitory computer-readable storage medium of claim 1 , where the first data store and the second data store are located on different data storage devices.

18 . The non-transitory computer-readable storage medium of claim 1 , where the first subset and the second subset are mutually exclusive.

19 . The non-transitory computer-readable storage medium of claim 1 , where the first subset and the second subset are selected to maximize a utility measure that is a function of an erasure code read time, an erasure code write time, or an erasure code storage cost.

20 . An apparatus, comprising:
a processor; a memory; a set of logics that control how erasure codes are stored on a plurality of data storage devices; 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 characterization of one or more operating parameters for the plurality of data storage devices; and
a second logic that selectively causes the erasure codes to be stored on different members of the plurality of data storage devices based, at least in part, on the characterization of the one or more operating parameters.

21 . The apparatus of claim 20 , where the one or more operating parameters include write speed, read speed, storage capacity, or storage cost.

22 . The apparatus of claim 21 , where the plurality of data storage devices include a hard disk drive, a solid state drive, a tape drive, or a virtual storage device located in the cloud.

23 . The apparatus of claim 22 , where the first logic produces a ranking of the plurality of data storage devices with respect to the one or more parameters and where the second logic causes the erasure codes to be stored on different members of the plurality of data storage devices based, at least in part, on the ranking.

24 . The apparatus of claim 20 , where the second logic causes the erasure codes to be stored on selected members of the plurality of data storage devices to maximize a read utility measure.

25 . The apparatus of claim 24 , where the read utility measure is a function of a probability that an erasure code will be read and a time required to read the erasure code.

26 . The apparatus of claim 20 , comprising a third logic that produces a re-characterization of the one or more operating parameters for the plurality of data storage devices and causes the second logic to selectively move an erasure code from a current data storage device to a different data storage device based, at least in part, on the re-characterization.

27 . A method, comprising:
accessing a set of systematic erasure codes; storing m

Assignees

• Quantum Corp

Inventors

• Doerner Don

Classifications

• G06F11/1076 Primary

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• H03M13/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 title

• H03M13/3761 Primary

  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 · CPC title