Flexible 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:
receiving, by a data processing unit configured to implement a plurality of durability schemes for data reliability, a set of data to be stored;
identifying, by the data processing unit, a durability scheme from among the plurality of different durability schemes for data reliability, wherein each of the plurality of different durability schemes is implemented through use of a different one of a plurality of coefficient matrices;
determining, by the data processing unit and based on the identified durability scheme, an identified coefficient matrix appropriate for the identified durability scheme by determining which portions of the set of data are used to generate each of a plurality of parity fragments and by configuring the identified coefficient matrix to select, for each respective parity fragment in the plurality of parity fragments, the determined portions of the set of data when the identified coefficient matrix is applied to the set of data;
caching, by the data processing unit, a subset of coefficient matrices from the plurality of coefficient matrices, wherein caching the subset of coefficient matrices includes identifying which of the plurality of coefficient matrices has been used most recently to implement one or more of the plurality of data durability schemes; and
generating, by data durability circuitry within the data processing unit and by applying the identified coefficient matrix to the set of data, parity data, wherein the parity data includes the plurality of parity fragments.
2. The method of claim 1 , further comprising:
storing, by the data processing unit, the set of data and the parity data.
3. The method of claim 1 , further comprising:
receiving, by the data processing unit, a request to access at least a portion of the set of data;
identifying, by the data processing unit, available data from the stored set of data and the stored parity data;
generating, by the data durability circuitry within the data processing unit and by applying the identified coefficient matrix to the available data, a reconstructed set of data corresponding to the set of data; and
responding to the request by outputting, by the data processing unit, the reconstructed data.
4. The method of claim 3 , wherein generating a reconstructed set of data includes:
calculating an inverse matrix using the identified coefficient matrix; and
applying the inverse matrix to the available data.
5. The method of claim 4 , further comprising:
caching, by the data processing unit, the inverse matrix.
6. The method of claim 1 , wherein generating the parity data includes:
applying the identified coefficient matrix to the set of data through a vector dot product operation.
7. The method of claim 1 , wherein generating the parity data includes:
generating a plurality of parity data fragments; and
applying the identified coefficient matrix to select portions of the set of data for use in generating each of the plurality of parity data fragments.
8. The method of claim 1 , wherein generating the parity data includes:
performing a matrix multiplication operation using the identified coefficient matrix, wherein performing the matrix multiplication operation includes performing an operation using Galois Field mathematics.
9. The method of claim 1 , wherein identifying the durability scheme includes identifying the durability scheme based on at least one of:
stored instructions, configuration data, a programmable setting, or user input.
10. The method of claim 1 , wherein the plurality of different durability schemes includes at least one of:
an EVENODD scheme, an X-Code scheme, a HoVer scheme, a WEAVER scheme, a parity encoding scheme, a Reed Solomon scheme, an LRC scheme, a hierarchical erasure coding scheme, and a RAID scheme.
11. A data processing unit comprising:
at least one memory device;
data durability circuitry configured to implement a plurality of durability schemes for data reliability; and
processing circuitry capable of controlling the data durability circuitry, having access to the at least one memory device, and configured to:
receive a set of data to be stored,
identify a durability scheme from among the plurality of different durability schemes for data reliability, wherein each of the plurality of different durability schemes is implemented through use of a different one of a plurality of coefficient matrices,
determine, based on the identified durability scheme, an identified coefficient matrix appropriate for the identified durability scheme by determining which portions of the set of data are used to generate each of a plurality of parity fragments and by configuring the identified coefficient matrix to select, for each respective parity fragment in the plurality of parity fragments, the determined portions of the set of data when the identified coefficient matrix is applied to the set of data,
cache a subset of coefficient matrices from the plurality of coefficient matrices by identifying which of the plurality of coefficient matrices has been used most recently to implement one or more of the plurality of data durability schemes, and
cause the data durability circuitry to generate, by applying the identified coefficient matrix to the set of data, parity data, wherein the parity data includes the plurality of parity fragments.
12. The data processing unit of claim 11 , wherein the processing circuitry is further configured to:
store the set of data and the parity data;
receive a request to access at least a portion of the set of data;
identify available data from the stored set of data and the stored parity data;
cause the data durability circuitry to generate, by applying the identified coefficient matrix to the available data, a reconstructed set of data corresponding to the set of data; and
respond to the request by outputting the reconstructed data.
13. The data processing unit of claim 11 , further comprising a cache for storing coefficient matrices, and wherein the processing circuitry is further configured to:
receive a request to access at least a portion of the set of data;
identify available data from the stored set of data and the stored parity data;
cause the data durability circuitry to access, in the cache, an inverse matrix;
cause the data durability circuitry to generate, by applying the inverse matrix to the available data, a reconstructed set of data corresponding to the set of data; and
respond to the request by outputting the reconstructed data.
14. The data processing unit of claim 11 , wherein to cause the data durability circuitry to generate a reconstructed set of data, the processing circuitry is further configured to cause the data durability circuitry to:
calculate an inverse matrix using the identified coefficient matrix; and
apply the inverse matrix to the available data.
15. The data processing unit of claim 14 , wherein the processing circuitry is further configured to:
cache the inverse matrix.
16. The data processing unit of claim 11 , wherein to generate the parity data, the processing circuitry is further configured to:
apply the identified coefficient matrix to the set of data through a vector dot product operation.
17. A computer-readable storage medium comprising instructions that, when executed, configure processing circuitry of a computing system to:
receive a set of data to be stored;
identify a durability scheme from among a plurality of different durability schemes for data reliability, wherein each of the plurality of different durability schemes is implemented through use of a different one of a plurality of coefficient matrices;
determine, based on the identified durability scheme, identified coefficient matrix appropriate for the identified durability scheme by determining which portions of the set of data are used to generate each of a plurality of parity fragments and by configuring the identified coefficient matrix to select, for each respective parity fragment in the plurality of parity fragments, the determined portions of the set of data when the identified coefficient matrix is applied to the set of data;
cache a subset of coefficient matrices from the plurality of coefficient matrices by identifying which of the plurality of coefficient matrices has been used most recently to implement one or more of the plurality of data durability schemes; and
cause the processing circuitry to generate, by applying the identified coefficient matrix to the set of data, parity data, wherein the parity data includes the plurality of parity fragments.