Reliability coding for storage on a network
This disclosure describes a programmable device, referred to generally as a data processing unit, having multiple processing units for processing streams of information, such as network packets or storage packets. This disclosure also describes techniques that include enabling data durability coding on a network. In some examples, such techniques may involve storing data in fragments across multiple fault domains in a manner that enables efficient recovery of the data using only a subset of the data. Further, this disclosure describes techniques that include applying a unified approach to implementing a variety of durability coding schemes. In some examples, such techniques may involve implementing each of a plurality of durability coding and/or erasure coding schemes using a common matrix approach, and storing, for each durability and/or erasure coding scheme, an appropriate set of matrix coefficients.
1. A method comprising:
accessing, by a computing system and over a network, a plurality of data fragments;
performing, by the computing system, a strided read operation across the plurality of data fragments by reading over the network, for each of the plurality of data fragments, data at a stride offset relative to a reference offset for each of the plurality of data fragments, wherein performing the strided read operation generates strided read data comprising data from each of the plurality of data fragments; and
applying an erasure coding algorithm, by the computing system and based on the strided read data, to generate a parity fragment from the plurality of data fragments, wherein applying the erasure coding algorithm includes applying the erasure coding algorithm to the strided read data so that less network activity is required to generate the parity fragment than applying the erasure coding algorithm to the plurality of data fragments.
2. The method of claim 1 , wherein the plurality of data fragments includes a first data fragment and a second data fragment, and wherein performing the strided read operation includes:
reading, from the first data fragment, a first subset of data; and
reading, from the second data fragment, a second subset of data.
3. The method of claim 2 , wherein applying the erasure coding algorithm includes:
performing a first matrix operation using the first subset of data;
performing a second matrix operation using the second subset of data; and
generating the parity fragment based on the first matrix operation and the second matrix operation.
4. The method of claim 2 , wherein performing the strided read operation across the plurality of data fragments includes:
reading the first subset of data only a single time; and
reading the second subset of data only a single time.
5. The method of claim 1 , wherein the strided read operation is a first strided read operation, wherein the stride offset is a first stride offset, and wherein the parity fragment is a first parity fragment, the method further comprising:
performing, by the computing system, a second strided read operation across the plurality of data fragments by reading, for each of the plurality of data fragments, data at a second stride offset relative to the reference offset of each of the plurality of data fragments; and
applying the erasure coding algorithm, by the computing system and based on the second strided read operation, to generate a second parity fragment from the plurality of data fragments.
6. The method of claim 5 , further comprising:
performing, by the computing system, a third strided read operation across the plurality of data fragments by reading, for each of the plurality of data fragments, data at a third stride offset relative to the reference offset of each of the plurality of data fragments; and
applying the erasure coding algorithm, by the computing system and based on the third strided read operation, to generate a third parity fragment from the plurality of data fragments,
wherein generating the third parity fragment is performed without modifying the first parity fragment or the second parity fragment.
7. The method of claim 6 , further comprising:
storing, by the computing system, the first parity fragment, the second parity fragment, and the third parity fragment across three different fault domains, wherein each fault domain includes one or more hardware subsystems not included within any other of the fault domains.
8. The method of claim 1 , wherein accessing the plurality of data fragments includes:
storing, before performing the strided read operation, each of the plurality of data split fragments within contiguous memory.
9. The method of claim 1 , further comprising:
receiving, by a data processing system and from a requesting device, a request to access at least a portion of the plurality of data fragments;
determining, by the data processing system, that one or more of the plurality of data fragments is not available;
identifying, by the data processing system, a plurality of available data fragments, wherein the plurality of available data fragments is a subset of the plurality of data fragments;
accessing, by the data processing system, the plurality of available data fragments;
accessing, by the data processing system, the parity fragment;
generating, by the data processing system, a reconstructed set of data from the plurality of available data fragments and the parity fragment; and
responding to the request by outputting, by the data processing system, the reconstructed data.
10. The method of claim 1 , wherein the erasure coding algorithm is a Reed Solomon erasure coding algorithm.
11. The method of claim 1 , wherein the computing system includes circuitry for efficiently performing matrix multiplication operations, and wherein applying the erasure coding algorithm includes:
performing, by the circuitry, matrix multiplication operations.
12. The method of claim 11 , wherein the circuitry includes circuitry for efficiently performing Galois Field mathematics operations, and wherein applying the erasure coding algorithm includes:
performing, by the circuitry, Galois Field mathematics operations.
13. The method of claim 12 , wherein performing the Galois Field mathematics operations include performing XOR operations and using at least one lookup table.
14. A system comprising a storage system and processing circuitry having access to the storage system, wherein the processing circuitry is configured to:
access a plurality of data fragments over a network;
perform a strided read operation across the plurality of data fragments by reading over the network, for each of the plurality of data fragments, data at a stride offset relative to a reference offset for each of the plurality of data fragments, wherein performing the strided read operation generates strided read data comprising data from each of the plurality of data fragments; and
apply an erasure coding algorithm, based on the strided read data, to generate a parity fragment from the plurality of data fragments, wherein applying the erasure coding algorithm includes applying the erasure coding algorithm to the strided read data so that less network activity is required to generate the parity fragment than applying the erasure coding algorithm to the plurality of data fragments.
15. The system of claim 14 , wherein the plurality of data fragments includes a first data fragment and a second data fragment, and wherein to perform the strided read operation, the processing circuitry is further configured to:
read, from the first data fragment, a first subset of data; and
read, from the second data fragment, a second subset of data.
16. The system of claim 15 , wherein to apply the erasure coding algorithm, the processing circuitry is further configured to:
perform a first matrix operation using the first subset of data;
perform a second matrix operation using the second subset of data; and
generate the parity fragment based on the first matrix operation and the second matrix operation.
17. The system of claim 15 , wherein to perform the strided read operation across the plurality of data fragments, the processing circuitry is further configured to:
read the first subset of data only a single time; and
read the second subset of data only a single time.
18. The system of claim 14 , wherein the strided read operation is a first strided read operation, wherein the stride offset is a first stride offset, wherein the parity fragment is a first parity fragment, and wherein the processing circuitry is further configured to:
perform a second strided read operation across the plurality of data fragments by reading, for each of the plurality of data fragments, data at a second stride offset relative to the reference offset of each of the plurality of data fragments; and
apply the erasure coding algorithm, based on the second strided read operation, to generate a second parity fragment from the plurality of data fragments.
19. The system of claim 18 , wherein the processing circuitry is further configured to:
perform a third strided read operation across the plurality of data fragments by reading, for each of the plurality of data fragments, data at a third stride offset relative to the reference offset of each of the plurality of data fragments; and
apply the erasure coding algorithm, based on the third strided read operation, to generate a third parity fragment from the plurality of data fragments,
wherein generating the third parity fragment is performed without modifying the first parity fragment or the second parity fragment.
20. A non-transitory computer-readable storage medium comprising instructions that, when executed, configure processing circuitry of a computing system to:
access a plurality of data fragments over a network;
perform a strided read operation across the plurality of data fragments by reading over the network, for each of the plurality of data fragments, data at a stride offset relative to a reference offset for each of the plurality of data fragments, wherein performing the strided read operation generates strided read data comprising data from each of the plurality of data fragments; and
apply an erasure coding algorithm, based on the strided read data, to generate a parity fragment from the plurality of data fragments, wherein applying the erasure coding algorithm includes applying the erasure coding algorithm to the strided read data so that less network activity is required to generate the parity fragment than applying the erasure coding algorithm to the plurality of data fragments.