# US 11,442,644 B2 · Systems and methods for optimized re-striping in an erasure encoded storage

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

- Number: US 11,442,644 B2
- Document ID: US11442644B2
- Status: Granted
- Kind: B2
- Application number: 16/986,326
- Filed: 2020-08-06
- Published: 2021-09-16
- Granted: 2022-09-13
- Earliest claimed: 2020-03-11
- Assignees: Acronis International GmbH
- Applicants: Acronis International GmbH
- Inventors: Oleg Volkov; Andrey Zaitsev; Alexey Kuznetsov; Yuri Per; Stanislav Protasov; Serguei Beloussov
- Web page: https://patentgrep.com/patent/US11442644B2

## CPC

- G06F 3/0644: {Management of space entities, e.g. partitions, extents, pools}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/0629: {Configuration or reconfiguration of storage systems}
- G06F 3/064: {Management of blocks}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 3/0688: {Non-volatile semiconductor memory arrays}
- G06F 3/0689: {Disk arrays, e.g. RAID, JBOD}
- H03M 13/154: {Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial}
- 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

Aspects of the present disclosure describe methods and systems for optimized re-striping in an erasure encoded storage. In one exemplary aspect, a method may receive a request to re-stripe a plurality of data blocks arranged as a tile in the erasure encoded storage, wherein the request comprises a desired tile width. The method may identify (1) a number of data blocks in the tile and (2) a width of the tile. The method may determine a maximum number of data blocks that do not need to be rearranged when reconfiguring the tile to the desired tile width. Furthermore, the method may determine a tile reconfiguration with the desired tile width that does not rearrange the maximum number of the data blocks of the tile, and may re-stripe the tile in accordance with the tile reconfiguration.

## Claims

### Claim 1

A computer-implemented method for optimized re-striping in an erasure encoded storage, the method comprising:
receiving a request to re-stripe a plurality of data blocks arranged as a tile in the erasure encoded storage, wherein the request comprises a desired tile width;
identifying (1) a number of data blocks in the tile and (2) a width of the tile;
determining a maximum number of data blocks that do not need to be rearranged when reconfiguring the tile to the desired tile width;
determining a tile reconfiguration with the desired tile width that does not rearrange the maximum number of the data blocks of the tile by calculating tile configurations for all possible tile widths that the number of data blocks is divisible by; and
re-striping the tile in accordance with the tile reconfiguration.

### Claim 2 (depends on 1)

The method of claim 1, wherein applying CP transformation comprises:
determining a respective maximum number of data blocks that do not need to be rearranged when reconfiguring a given tile to a given tile width and determining a respective tile reconfiguration with the given tile width that does not rearrange the respective maximum number of the data blocks of the given tile.

### Claim 3 (depends on 2)

The method of claim 2, wherein calculating the tile configurations further comprises successively applying the CP transformation to all possible tiles with the number of data blocks in order of increasing heights starting from the tile specified by an initial width or height.

### Claim 4 (depends on 2)

The method of claim 2, wherein calculating the tile configurations further comprises successively applying the CP transformation to all possible tiles with the number of data blocks in order of increasing width starting from the tile specified by an initial width or height.

### Claim 5 (depends on 4)

The method of claim 4, wherein the initial height of the tile is equal to 1.

### Claim 6 (depends on 4)

The method of claim 4, wherein the initial tile width is equal to a width of a stripe where the data were originally stored.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
prior to determining the maximum number of the data blocks:
determining that at least one intermediate tile width exists between the width of the tile and the desired tile width such that the number of data blocks is divisible by the at least one intermediate tile width;
determining at least a second maximum number of data blocks that do not need to be rearranged; and
determining a second tile reconfiguration with the at least one intermediate tile width that does not rearrange the second maximum number of the data blocks of the tile,
wherein determining the maximum number of the data blocks that do not need to rearranged when reconfiguring the tile to the desired tile width is based on the second tile reconfiguration.

### Claim 8 (depends on 7)

The method of claim 7, wherein all determined tile reconfigurations of the plurality of data blocks are retained in the erasure encoded storage until the tile has been re-striped to the desired tile width, wherein the determined tile reconfigurations comprise a tile size, a current width or height and an initial width or height.

### Claim 9 (depends on 8)

The method of claim 8, wherein a coordinator node performs re-striping and wherein a centralized metadata service (MDS) determines configurations and delivers node assignments to the coordinator node in special storage mapping messages.

### Claim 10 (depends on 9)

The method of claim 9, further comprising:
subsequent to re-striping the tile to the desired tile width, sending a completion message to the MDS, wherein the MDS is configured to:
store (1) an initial tile configuration of the re-striped tile and the width and (2) the second tile reconfiguration of the re-striped tile and the desired tile width; and
deliver new mapping messages to all the storage nodes to confirm completion of the re-striping, wherein the storage nodes drop all data and metadata associated with the initial tile configuration of the re-striped tile.

### Claim 11 (depends on 1)

The method of claim 1, wherein the maximum number of data blocks is determined based on the number of data blocks in the tile and a maximum possible fraction Smax, wherein
Smax(n,m)=min(n,m)/max(n,m)
and wherein n is the width of the tile and m is the desired tile width.

### Claim 12

A system for optimized re-striping in an erasure encoded storage, the system comprising:
a hardware processor configured to:
receive a request to re-stripe a plurality of data blocks arranged as a tile in the erasure encoded storage, wherein the request comprises a desired tile width;
identify (1) a number of data blocks in the tile and (2) a width of the tile;
determine a maximum number of data blocks that do not need to be rearranged when reconfiguring the tile to the desired tile width;
determine a tile reconfiguration with the desired tile width that does not rearrange the maximum number of the data blocks of the tile by calculating tile configurations for all possible tile widths that the number of data blocks is divisible by; and
re-stripe the tile in accordance with the tile reconfiguration.

### Claim 13 (depends on 12)

The system of claim 12, wherein the hardware processor is further configured to apply CP transformation by:
determining a respective maximum number of data blocks that do not need to be rearranged when reconfiguring a given tile to a given tile width and determining a respective tile reconfiguration with the given tile width that does not rearrange the respective maximum number of the data blocks of the given tile.

### Claim 14 (depends on 13)

The system of claim 13, wherein the hardware processor is further configured to calculate the tile configurations by successively applying the CP transformation to all possible tiles with the number of data blocks in order of increasing heights starting from the tile specified by an initial width or height.

### Claim 15 (depends on 13)

The system of claim 13, wherein the hardware processor is further configured to calculate the tile configurations by successively applying the CP transformation to all possible tiles with the number of data blocks in order of increasing width starting from the tile specified by an initial width or height.

### Claim 16 (depends on 15)

The system of claim 15, wherein the initial height of the tile is equal to 1.

### Claim 17 (depends on 15)

The system of claim 15, wherein the initial tile width is equal to a width of a stripe where the data were originally stored.

### Claim 18

A non-transitory computer readable medium storing thereon computer executable instructions for optimized re-striping in an erasure encoded storage, including instructions for:
receiving a request to re-stripe a plurality of data blocks arranged as a tile in the erasure encoded storage, wherein the request comprises a desired tile width;
identifying (1) a number of data blocks in the tile and (2) a width of the tile;
determining a maximum number of data blocks that do not need to be rearranged when reconfiguring the tile to the desired tile width;
determining a tile reconfiguration with the desired tile width that does not rearrange the maximum number of the data blocks of the tile by calculating tile configurations for all possible tile widths that the number of data blocks is divisible by; and
re-striping the tile in accordance with the tile reconfiguration.