High reliability erasure code distribution
View Patent ↗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.
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, where the first data store is located on cylinders on the outer half of a hard disk drive;
identifying a second data store that is available to store members of the set of n erasure codes, where the second data store is located on cylinders on the inner half of a hard disk drive;
identifying a property associated with both the first data store and the second data store, where the property is a speed with which an erasure code can be read from a data store, or where the property is a speed with which an erasure code can be written to a 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 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.
3. 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.
4. 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.
5. The non-transitory computer-readable storage medium of claim 4 , 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.
6. The non-transitory computer-readable storage medium of claim 5 , 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.
7. 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.
8. The non-transitory computer-readable storage medium of claim 7 , where the first subset is the k sized subset and the second subset is the n-k sized subset.
9. The non-transitory computer-readable storage medium of claim 7 , where the first subset includes at least the k sized subset and the second subset includes at least the n-k sized subset.
10. The non-transitory computer-readable storage medium of claim 9 ,
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.
11. The non-transitory computer-readable storage medium device of claim 1 , the method comprising causing the first subset to be stored on the first data store and causing the second subset to be stored on the second data store.
12. 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.
13. 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.
14. 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.
15. The non-transitory computer-readable storage medium of claim 1 , where the first subset and the second subset are mutually exclusive.
16. 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.
17. 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 a plurality of operating parameters for the plurality of data storage devices, where the plurality of operating parameters includes write speed and one or more of read speed, storage capacity, or storage cost, where the first logic produces a ranking of the plurality of data storage devices with respect to the plurality of parameters; 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 plurality of operating parameters, and the ranking.
18. The apparatus of claim 17 , 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.
19. The apparatus of claim 17 , 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.
20. The apparatus of claim 19 , 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.
21. The apparatus of claim 17 , comprising a third logic that produces a re-characterization of the plurality of 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.
22. A method, comprising:
accessing a set of systematic erasure codes;
producing a ranking of a first data store and a second data store, where the ranking is based on an operating parameter of the first data store and an operating parameter of the second data store;
selectively storing members of the set of systematic erasure codes from which a message can be reconstructed without erasure code decoding on the first data store based, at least in part, on the ranking; and
selectively storing members of the set of systematic erasure codes from which the message can be reconstructed using erasure code decoding on the second data store, based, at least in part on the ranking, where the second subset includes less than enough erasure codes to reconstruct the message, and where the second subset is stored, at least in part, in an unencrypted fashion,
where a member of the set of systematic erasure codes can be read from the first data store faster than from the second data store.
23. The method of claim 22 , where the first data store is a solid state drive and the second data store is a hard disk drive.
24. The method of claim 22 , where the first data store is a hard disk drive and the second data store is a tape.
25. The method of claim 22 , where the first data store is a hard disk drive and the second data store is in the cloud.
26. The method of claim 22 , where the first data store is located on cylinders closer to the outside of a hard disk drive than cylinders on the hard disk drive associated with the second data store.
27. The method of claim 22 , where the second data store is a publicly accessible data store.
28. The method of claim 27 , where the second data store resides in the cloud.