# US 2020/0401483 A1 · Reliability coding for storage on a network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0401483 A1
- Document ID: US20200401483A1
- Status: Published application
- Kind: A1
- Application number: 17/007,687
- Filed: 2020-08-31
- Published: 2020-12-24
- Earliest claimed: 2018-10-24
- Assignees: Fungible, Inc.
- Applicants: Fungible, Inc.
- Inventors: Rajan Goyal; Abhishek Kumar Dikshit
- Web page: https://patentgrep.com/patent/US20200401483A1

## CPC

- G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems}
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- H03M 13/1515: {Reed-Solomon codes}
- H03M 13/154: {Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial}
- H03M 13/373: {with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes}
- H03M 13/3761: {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}
- H03M 13/6516: {Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

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.

## Claims

### Claim 1

A method comprising:
accessing, by a computing system, a plurality of data fragments;
performing, by the computing system, a strided read operation across the plurality of data fragments by reading, 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; and
applying an erasure coding algorithm, by the computing system and based on the strided read operation, to generate a parity fragment from the plurality of data fragments.

### Claim 2 (depends on 1)

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;

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 2)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 1)

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.

### Claim 10 (depends on 1)

The method of claim 1, wherein the erasure coding algorithm is a Reed Solomon erasure coding algorithm.

### Claim 11 (depends on 1)

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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 12)

The method of claim 12, wherein performing the Galois Field mathematics operations include performing XOR operations and using at least one lookup table.

### Claim 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;
perform a strided read operation across the plurality of data fragments by reading, 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; and
apply an erasure coding algorithm, based on the strided read operation, to generate a parity fragment from the plurality of data fragments.

### Claim 15 (depends on 14)

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:
reading, from the first data fragment, a first subset of data; and
reading, from the second data fragment, a second subset of data;

### Claim 16 (depends on 15)

The system of claim 15, wherein to apply the erasure coding algorithm, the processing circuitry is further configured to:
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.

### Claim 17 (depends on 15)

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:
reading the first subset of data only a single time; and
reading the second subset of data only a single time.

### Claim 18 (depends on 14)

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:
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.

### Claim 19 (depends on 18)

The system of claim 18, wherein the processing circuitry is further configured to:
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.

### Claim 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;
perform a strided read operation across the plurality of data fragments by reading, 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; and
apply an erasure coding algorithm, based on the strided read operation, to generate a parity fragment from the plurality of data fragments.