Erasure code prioritization
View Patent ↗Example apparatus and methods selectively generate and store erasure codes differently based on priorities associated with the erasure codes or based on conditions in a data storage system (DSS) that protects messages using erasure codes. Producing a systematic erasure code (EC) may be prioritized over producing a non-systematic EC. Producing an EC associated with correcting X erasures may be prioritized over producing an EC associated with correcting Y erasures, X and Y being numbers, X<Y. The priorities may depend on conditions in the DSS including an erasure code A/B policy, numbers of errors experienced by the DSS, types of errors experienced by the DSS, frequency of errors, an amount of power required to store or retrieve an EC in the DSS, or a network bandwidth required to store or retrieve an EC in the DSS. The priorities may be user configurable or self-adapting.
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 for controlling a data storage system (DSS) that uses erasure codes to provide redundancy for messages, the method comprising:
accessing a message for which a non-empty set of erasure codes are to be produced;
accessing an erasure code generator, where a first portion of the erasure code generator produces a first type of erasure code (EC) having a first priority, and where a second portion of the EC generator produces a second type of EC having a second different priority;
selectively producing the set of ECs for the message using the EC generator and the message, where the membership of the set and the order of ECs in the set depend, at least in part, on a generation priority, and
selectively storing a member of the set in a data storage device (DSD) in the DSS, where the member and the DSD are selected based, at least in part, on a storage priority.
2. The non-transitory computer-readable storage medium of claim 1 , comprising:
in response to detecting an erasure error associated with the message, retrieving a selected EC from a device in the DSD, where the selected member is selected based, at least in part, on a retrieval priority, and
recovering the message using the selected EC.
3. The non-transitory computer-readable storage medium of claim 2 , where the retrieval priority is a function of a cost to retrieve an EC from a DSD, a time to retrieve an EC from a DSD, an amount of energy used to retrieve an EC from a DSD, or a network bandwidth required to retrieve an EC from a DSD.
4. The non-transitory computer-readable storage medium of claim 1 , where the EC generator uses a matrix of EC generating values, where a row in the matrix has a priority ranking, and where producing the set of ECs for the message using the EC generator and the message includes multiplying the message by a number of rows in the matrix, where the number is controlled, at least in part, by the generation priority.
5. The non-transitory computer-readable storage medium of claim 4 , where the priority ranking is user configurable, or
where the priority ranking is self-adapting over time in response to performance data associated with the DSS, where the performance data includes a number of errors experienced by the DSS, a type of error experienced by the DSS, a frequency of errors experienced by the DSS, a cost of power used by the DSS, or a cost of network bandwidth used by the DSS.
6. The non-transitory computer-readable storage medium of claim 4 , where a priority ranking for a row associated with a systematic EC is higher than a priority ranking for a row associated with a non-systematic EC.
7. The non-transitory computer-readable storage medium of claim 6 , where a priority ranking for a row associated with a non-systematic EC varies inversely with the number of erasures for which the non-systematic EC corrects.
8. The non-transitory computer-readable storage medium of claim 1 , where the generation priority is a function of a complexity to compute a type of EC, a cost to compute a type of EC, a time to compute a type of EC, an amount of energy used to compute a type of EC, a depth of redundancy desired for the message, or a usefulness of a type of EC.
9. The non-transitory computer-readable storage medium of claim 1 , where the storage priority is a function of a cost to store an EC on a DSD, a time to store an EC on a DSD, an amount of energy used to store an EC on a DSD, or a network bandwidth required to store an EC on a DSD.
10. The non-transitory computer-readable storage medium of claim 1 , where the generation priority, the storage priority, or the retrieval priority are user configurable, or are self-adapting over time based, at least in part, on performance data associated with the DSS, where the performance data includes a number of errors experienced by the DSS, a type of error experienced by the DSS, a frequency of errors experienced by the DSS, a cost of power used by the DSS, or a cost of network bandwidth used by the DSS.
11. The non-transitory computer-readable storage medium of claim 1 , where the DSD is a disk that includes a platter that rotates, and where the method includes controlling the disk to position data on the platter based on a likelihood that the data will be used, where the distance to the data relative to the outer edge of the platter varies inversely with the likelihood that the data will be used.