# US 2019/0171523 A1 · Erased memory page reconstruction using distributed coding for multiple dimensional parities

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

- Number: US 2019/0171523 A1
- Document ID: US20190171523A1
- Status: Published application
- Kind: A1
- Application number: 16/228,431
- Filed: 2018-12-20
- Published: 2019-06-06
- Earliest claimed: 2015-12-14
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Mario Blaum; Aayush Gupta; James Hafner; Steven R. Hetzler
- Web page: https://patentgrep.com/patent/US20190171523A1

## 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/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for memory page erasure-correcting property generation in a storage array includes dividing data into multiple stripes for storage in a storage array including multiple storage devices with a topology of a hypercube of a dimension t≥3. The storage devices in same hypercubes of dimension t−1 including the hypercube of dimension t have even parity. An intersection of two non-parallel planes in the hypercube topology is a line, and each point along a line is a storage device in the storage array. Erasure-correcting properties are generated for the data using three nested codes, wherein a first nested code has even parity over planes of class 0, 1 and 2, a second nested code has a first global parity, and a third nested code has a second global parity and a third global parity.

## Claims

### Claim 1

A method for memory page erasure-correcting property generation in a storage array comprising:
dividing data into a plurality of stripes for storage in a storage array comprising a plurality of storage devices with a topology of a hypercube of a dimension t≥3, wherein the storage devices in same hypercubes of dimension t−1 comprising the hypercube of dimension t have even parity, an intersection of two non-parallel planes in the hypercube topology is a line, and each point along a line is a storage device in the storage array; and
generating erasure-correcting properties for the data using three nested codes, wherein a first nested code has even parity over planes of class 0, 1 and 2, a second nested code has a first global parity, and a third nested code has a second global parity and a third global parity.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
reconstructing, by a reconstructor processor, erased data for erased memory pages from non-erased data in the storage array by using parities in at least three dimensions based on the hypercube topology of the storage devices.

### Claim 3 (depends on 2)

The method of claim 2, wherein storage device accesses in the storage array are limited for reconstruction to at least one plane within the hypercube topology including non-erased memory pages, and a minimum distance d for the three nested codes provides reconstruction of d−1 erasures in the storage array.

### Claim 4 (depends on 3)

The method of claim 3, wherein:
the at least one plane comprises at least one of: a first plane including the erased data, and any other plane that intersects with a particular storage device in the hypercube topology that included the erased data; and
the storage devices are linked by one or more of the first global parity, the second global parity and the third global parity over a finite field.

### Claim 5 (depends on 2)

The method of claim 2, wherein the storage devices are linked by one of the first global parity, the second global parity and the third global parity, and d is 6.

### Claim 6 (depends on 2)

The method of claim 2, wherein the storage devices are linked by two of: the first global parity, the second global parity and the third global parity, and d is at least 7.

### Claim 7 (depends on 2)

The method of claim 2, further comprising:
retrieving any erased elements of a line by XORing non-erased elements in a plane; and
correcting a number of erasures using one or more of the first global parity, the second global parity and the third global parity.

### Claim 8

A computer program product for memory page erasure-correcting property generation in a storage array, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:
divide, by the processor, data into a plurality of stripes for storage in a storage array comprising a plurality of storage devices with a topology of a hypercube of a dimension t≤3, wherein the storage devices in same hypercubes of dimension t−1 comprising the hypercube of dimension t have even parity, an intersection of two non-parallel planes in the hypercube topology is a line, and each point along a line is a storage device in the storage array; and
generate, by the processor, erasure-correcting properties for the data using three nested codes, wherein a first nested code has even parity over planes of class 0, 1 and 2, a second nested code has a first global parity, and a third nested code has a second global parity and a third global parity.

### Claim 9 (depends on 8)

The computer program product of claim 8, further comprising program instructions executable by the processor to cause the processor to:
reconstruct, by the processor, erased data for erased memory pages from non-erased data in the storage array by using parities in at least three dimensions based on the hypercube topology of the storage devices.

### Claim 10 (depends on 9)

The computer program product of claim 9, wherein storage device accesses are limited for reconstruction to at least one plane within the hypercube topology including non-erased memory pages, and a minimum distance d for the three nested codes provides reconstruction of d−1 erasures in the storage array.

### Claim 11 (depends on 10)

The computer program product of claim 10, wherein:
the storage devices are linked by one or more of the first global parity, the second global parity and the third global parity over a finite field;
the at least one plane within the hypercube topology comprises at least one of: a first plane including the erased data; and
any plane that intersects with a particular storage device in the hypercube topology that included the erased data.

### Claim 12 (depends on 9)

The computer program product of claim 9, wherein the storage devices are linked by one of the first global parity, the second global parity and the third global parity, and d is 6.

### Claim 13 (depends on 9)

The computer program product of claim 9, wherein the storage devices are linked by two of: the first global parity, the second global parity and the third global parity, and d is at least 7.

### Claim 14 (depends on 9)

The computer program product of claim 9, wherein:
t=3;
wherein:
the hypercube topology comprises n0 parallel planes of n1n2 elements each, such that each 0≤i≤n0−1;
planes in the hypercube topology comprise the n1n2 elements entries (i, j, ) such that 0≤j≤n1−1 and 0≤≤n2−1, where n0 planes are class 0, n1 planes are class 1 including n0n2 elements each, and n2 planes are class 2 including n0n1 elements each; and
the three nested codes are represented as: Cn0,n1,n2(2)⊂Cn0,n1,n2(1)⊂Cn0,n1,n2(0) of length n0n1n2.

### Claim 15

An array of storage devices comprising:
a storage device array comprising a plurality of storage devices with a topology of a hypercube of a dimension t≤3, wherein the plurality of storage devices in same hypercubes of dimension t−1 comprising the hypercube of a dimension/have even parity, an intersection of two non-parallel planes in the hypercube topology is a line, and each point along a line is a storage device in the storage array; and
a processor configured to:
divide data into a plurality of stripes for storage in the storage array; and
generate erasure-correcting properties for the data using three nested codes, wherein a first nested code has even parity over planes of class 0, 1 and 2, a second nested code has a first global parity, and a third nested code has a second global parity and a third global parity.

### Claim 16 (depends on 15)

The array of storage devices of claim 15, wherein the processor is further configured to:
reconstruct erased data for erased memory pages from non-erased data in the storage array by using parities in at least three dimensions based on the hypercube topology of the storage devices.

### Claim 17 (depends on 16)

The array of storage devices of claim 16, wherein the processor is further configured to:
limit storage device accesses in the storage array for reconstruction to at least one plane within the hypercube topology including non-erased memory pages,
wherein a minimum distance d for the three nested codes provides reconstruction of d−1 erasures in the storage array.

### Claim 18 (depends on 17)

The array of storage devices of claim 17, wherein:
the at least one plane within the hypercube topology comprises at least one of: a first plane including the erased data, and any other plane that intersects with a particular storage device in the hypercube topology that included the erased data; and
the plurality of storage devices are linked by one or more of the first global parity, the second global parity and the third global parity over a finite field.

### Claim 19 (depends on 16)

The array of storage devices of claim 16, wherein the plurality of storage devices are linked by at least one global parity, and d is 6.

### Claim 20 (depends on 16)

The array of storage devices of claim 16, wherein the plurality of storage devices are linked by two of: the first global parity, the second global parity and the third global parity, and d is at least 7.
