# US 2021/0173740 A1 · Erasure recovery in a distributed storage system

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

- Number: US 2021/0173740 A1
- Document ID: US20210173740A1
- Status: Published application
- Kind: A1
- Application number: 17/045,980
- Filed: 2019-04-10
- Published: 2021-06-10
- Earliest claimed: 2018-04-13
- Assignees: Institut Mines-Telecom
- Applicants: Institut Mines Telecom
- Inventors: Hana BACCOUCH; Nadia BOUKHATEM
- Web page: https://patentgrep.com/patent/US20210173740A1

## CPC

- G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/064: {Management of blocks}
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 3/0689: {Disk arrays, e.g. RAID, JBOD}
- G06F 11/076: {by exceeding a count or rate limit, e.g. word- or bit count limit}
- G06F 11/3034: {where the computing system component is a storage system, e.g. DASD based or network based (digital input from or digital output to record carriers G06F3/06; digital recording or reproducing G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097)}
- 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}
- 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

A method for coding (k, r) data and a method for reconstructing data are provided. The coding method includes steps consisting in: dividing an initial datum a into k data blocks ai; grouping the k data blocks into r−1 subsets Sj of data blocks; generating, for each subset Sj, a linear function gj(a) defined as a linear combination of the data blocks assigned to said subset Sj; and generating r parity functions comprising a primary parity function f0(a) as a linear combination of the k data blocks ai, and r−1 secondary parity functions, each secondary parity function fj(a) being defined as the sum of the primary parity function f0(a) and of a linear function gj(a).

## Claims

### Claim 1

A method for coding (k, r) data comprising:
dividing an initial datum a into k data blocks ai of the same size;
grouping the k data blocks into r−1 disconnected subsets Sj of data blocks;
generating, for each subset Sj, a linear function gi(a) defined as a linear combination of the data blocks assigned to said subset Sj; and
generating r parity functions comprising a primary parity function f0(a) as a linear combination of the k data blocks ai, and r−1 secondary parity functions, each secondary parity function fj(a) being defined as the sum of the primary parity function f0(a) and of a linear function gi(a).

### Claim 2 (depends on 1)

The method according to claim 1, wherein the step of generating r parity functions includes generating r encoding vectors comprising:
a primary encoding vector C0 composed of k primary encoding coefficients c0,1 to c0,k; and
r−1 secondary encoding vectors Cj (1<=j<=r−1), each secondary encoding vector being composed of k secondary encoding coefficients cj,1 to cj,k.

### Claim 3 (depends on 2)

The method according to claim 2, wherein each primary encoding coefficient c0,i corresponds to a non-zero random number, and a secondary encoding coefficient cj,i corresponds to a non-zero or zero random number depending on whether the data block ai belongs to or does not belong to the subset Sj.

### Claim 4 (depends on 3)

The method according to claim 3, wherein the step of generating a linear function gi(a) includes generating a linear combination from the k data blocks (a1, . . . , ak) and from the k secondary encoding coefficients cj,1 to cj,k of the secondary encoding vector Cj.

### Claim 5 (depends on 1)

The method according to claim 1, wherein k=10 and r=4.

### Claim 6 (depends on 1)

The method for storing k+r data comprising at least one step including storing, in k systematic storage devices Ni, i∈ {1, . . . , k}, k data blocks ai, and in storing, in r parity storage devices Ni, i∈{k+1, . . . , k+r}, r parity functions, the r parity functions being obtained according to the data coding method of claim 1.

### Claim 7 (depends on 1)

A device for coding data comprising means suitable for implementing the steps of the data coding method according to claim 1.

### Claim 8 (depends on 1)

A method for reconstructing the content of a storage device out of a plurality of devices storing k data blocks ai in k systematic storage devices Ni, i∈{1, . . . , k}, and r parity functions fj(a) in r parity storage devices Ni, i∈{k+1, . . . , k+r}, said k data blocks and r parity functions being obtained according to the method of claim 1, the reconstruction method comprising:
determining whether the storage device for which to reconstruct the content is a systematic or parity storage device;
if said device is a systematic storage device Ni, i∈{1, . . . , k}:
determining to which subset of data Sj the data block of said device belongs;
retrieving the primary and secondary parity functions stored in the parity storage devices k+1 and k+1+j;
computing the linear function gj(a) associated with the subset Sj;
retrieving the data blocks of the subset Sj except for the block ai; and
reconstructing the content of said systematic storage device Ni, i∈{1, . . . , k};
if said device is a parity storage device Ni, i∈{k+1, . . . , k+r}, determining the index i identifying said storage device;
if the index i is equal to k+1:
retrieving the secondary parity function f1(a) stored in the parity storage device of index i=k+2 and the data blocks ai of the subset S1;
computing the linear function g1(a) associated with the subset S1 and decoding the primary parity function f0(a); and
reconstructing the content of said parity device of index i=k+1;
if the index i is greater than k+1:
retrieving the primary parity function f0(a) stored in the parity storage device of index i=k+1 and the data blocks ai of the subset Si−k+1;
computing the linear function gi−k+1(a) associated with the subset Si−k+1 and decoding the secondary parity function fi−k+1(a); and
reconstructing the content of said parity device of index i>k+1.

### Claim 9 (depends on 8)

The method according to claim 8, wherein the steps of retrieving the parity functions includes transferring the data from the corresponding storage devices to a data collecting device.

### Claim 10 (depends on 8)

The method according to claim 8, wherein the step of computing the linear function gi(a), associated with the subset Sj for the reconstruction of a systematic node i such that i∈{1, . . . , k}, includes subtracting the primary parity function stored in the storage device Nk+1 from the secondary parity function stored in the storage device Nk+1+j.

### Claim 11 (depends on 8)

The method according to claim 8, wherein the step of computing the linear function g1(a), associated with the subset S1 for the reconstruction of a parity node i such that i=k+1, includes generating a linear combination from the data blocks of the subset S1 and from the encoding vector C1, and the step of computing the linear function gj(a), associated with the subset Sj for the reconstruction of a parity node i such that i∈{k+2, . . . , k+r}, includes generating a linear combination from the data blocks of the subset Sj and from the encoding vector Cj.

### Claim 12 (depends on 8)

The method according to claim 8, wherein the step of reconstructing the content of said systematic storage device includes decoding the data block ai from the linear function gj(a).

### Claim 13 (depends on 8)

The method according to claim 8, wherein the step of reconstructing the content of said parity storage device i such that i=k+1 includes decoding the secondary parity function of said parity device of index i=k+1 from the computed linear function g1(a), and the step of reconstructing the content of said parity storage device i such that i>k+1 includes decoding the secondary parity function of said parity device of index i>k+1 from the computed linear function gi−k+1(a).

### Claim 14 (depends on 8)

A device for reconstructing the content of a storage device out of a plurality of devices storing k data blocks ai in k systematic storage devices Ni, i∈{1, . . . , k}, and r parity functions fj(a) in r parity storage devices Ni, i∈{k+1, . . . , k+r}, said k data blocks and r parity functions being obtained according to a method for coding (k, r) data comprising:
dividing an initial datum a into k data blocks ai of the same size;
grouping the k data blocks into r−1 disconnected subsets Sj of data blocks;
generating, for each subset Sj, a linear function gj(a) defined as a linear combination of the data blocks assigned to said subset Sj; and
generating r parity functions comprising a primary parity function f0(a) as a linear combination of the k data blocks ai, and r−1 secondary parity functions, each secondary parity function fj(a) being defined as the sum of the primary parity function f0(a) and of a linear function gj(a);
the device further comprising means suitable for implementing the steps of the method for reconstructing the content of a storage device according to claim 8.

### Claim 15 (depends on 8)

A computer program product comprising a program, said program comprising code instructions making it possible to perform a method for coding (k, r) data comprising:
dividing an initial datum a into k data blocks ai of the same size;
grouping the k data blocks into r−1 disconnected subsets Sj of data blocks;
generating, for each subset Sj, a linear function gj (a) defined as a linear combination of the data blocks assigned to said subset Sj; and
generating r parity functions comprising a primary parity function f0(a) as a linear combination of the k data blocks ai, and r−1 secondary parity functions, each secondary parity function fj(a) being defined as the sum of the primary parity function f0(a) and of a linear function gj(a);
and/or comprising code instructions making it possible to perform the steps of the method according to claim 8 when said program is run on a computer.

### Claim 16 (depends on 7)

An integrated circuit of ASIC or FPGA type comprising at least one device according to claim 7.

### Claim 17 (depends on 8)

A use of the content reconstruction method according to claim 8 in a distributed storage system, said distributed storage system comprising a plurality of data storage nodes capable of storing data coded according to a method for coding (k, r) data comprising:
dividing an initial datum a into k data blocks ai of the same size;
grouping the k data blocks into r−1 disconnected subsets Sj of data blocks;
generating, for each subset Sj, a linear function gj(a) defined as a linear combination of the data blocks assigned to said subset Sj; and
generating r parity functions comprising a primary parity function f0(a) as a linear combination of the k data blocks ai, and r−1 secondary parity functions, each secondary parity function fj(a) being defined as the sum of the primary parity function f0(a) and of a linear function gj(a).

### Claim 18 (depends on 8)

The use of the content reconstruction method according to claim 8 in a local storage system, said local storage system comprising data storage discs capable of storing data coded according to a method for coding (k, r) data comprising:
dividing an initial datum a into k data blocks ai of the same size;
grouping the k data blocks into r−1 disconnected subsets Sj of data blocks;
generating, for each subset Sj, a linear function gj(a) defined as a linear combination of the data blocks assigned to said subset Sj; and
generating r parity functions comprising a primary parity function f0(a) as a linear combination of the k data blocks ai, and r−1 secondary parity functions, each secondary parity function fj(a) being defined as the sum of the primary parity function f0(a) and of a linear function gj (a).

### Claim 19 (depends on 14)

An integrated circuit of ASIC or FPGA type comprising at least one device according to claim 14.

### Claim 20 (depends on 14)

An integrated circuit of ASIC or FPGA type comprising at least one device according to claim 14, and at least one device for coding data comprising means suitable for implementing the steps of a method for coding (k, r) data comprising:
dividing an initial datum a into k data blocks ai of the same size;
grouping the k data blocks into r−1 disconnected subsets Sj of data blocks;
generating, for each subset Sj, a linear function gj(a) defined as a linear combination of the data blocks assigned to said subset Sj; and
generating r parity functions comprising a primary parity function f0(a) as a linear combination of the k data blocks ai, and r−1 secondary parity functions, each secondary parity function fj(a) being defined as the sum of the primary parity function f0(a) and of a linear function gj(a).
