# US 10,374,637 B1 · System and method for unbalanced load handling with distributed erasure coding

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

- Number: US 10,374,637 B1
- Document ID: US10374637B1
- Status: Granted
- Kind: B1
- Application number: 15/582,167
- Filed: 2017-04-28
- Granted: 2019-08-06
- Earliest claimed: 2017-04-28
- Assignees: EMC IP Holding Company LLC
- Applicants: EMC IP Holding Company LLC
- Inventors: Mikhail Danilov; Konstantin Buinov; Alexander Rakulenko; Andrey Kurilov; Kirill Gusakov
- Web page: https://patentgrep.com/patent/US10374637B1

## CPC

- H03M 13/293: {with erasure setting}
- 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/611: {Specific encoding aspects, e.g. encoding by means of decoding}
- 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 creating distributed erasure coding chunks in a distributed storage system with unbalanced load is disclosed. The operations comprise configuring the distributed storage system into at least k+m zones, wherein each zone accumulates at least l primary backup chunks of original data chunks replicated from different remote zones, and wherein l<k, and preparing the distributed storage system for recovery from a failure of 1 to m zones of the at least k+m zones including, in each zone, encoding the at least l primary backup chunks to create m coding chunks using an erasure coding having parameters k+m, wherein in each zone in which fewer than k primary backup chunks have been accumulated, at most k−l predetermined virtual chunks are used to create partial coding chunks.

## Claims

### Claim 1

A method for creating distributed erasure coding chunks in a distributed storage system with unbalanced load, comprising:
configuring the distributed storage system into at least k+m zones, wherein each zone accumulates at least l primary backup chunks of original data chunks replicated from different remote zones, and wherein l<k, and
preparing the distributed storage system for recovery from a failure of 1 to m zones of the at least k+m zones including, in each zone, encoding the at least l primary backup chunks to create m coding chunks using an erasure coding having parameters k+m, wherein in each zone in which fewer than k primary backup chunks have been accumulated, at most k−l predetermined virtual chunks are used to create partial coding chunks.

### Claim 2 (depends on 1)

The method of claim 1, wherein preparing the distributed storage system further includes, in each zone:
retaining one of the m coding chunks;
distributing to a different one of any m−1 remote zones each of the m−1 coding chunks not retained; and
deleting any primary backup chunks to reduce storage overhead.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
recovering unavailable chunks from a failure of 1 to m zones including performing, in each of the zones unaffected by the failure, any one or more of:
identifying any of still available coding chunks created and retained by the zone, and
retrieving any of the still available coding chunks distributed to the zone from another zone, and
creating local copies of any of still available original data chunks from which the still available coding chunks were created; and
reconstructing as many unavailable chunks as possible from the still available coding chunks and the still available original data chunks.

### Claim 4 (depends on 1)

The method of claim 1, further comprising adding a new data chunk to an incomplete protection group comprising m partial coding chunks.

### Claim 5 (depends on 1)

The method of claim 1, wherein the plurality of at least k+m zones into which the distributed storage system is configured is distributed across a geographical area.

### Claim 6 (depends on 1)

The method of claim 1, wherein the distributed storage system is a cloud-based storage system accessible over an inter-network.

### Claim 7

A non-transitory machine-readable medium having instructions stored therein which, when executed by a processor, cause the processor to perform storage operations, the operations comprising:
configuring a distributed storage system into at least k+m zones, wherein each zone accumulates at least l primary backup chunks of original data chunks replicated from different remote zones, and wherein l<k, and
preparing the distributed storage system for recovery from a failure of 1 to m zones of the at least k+m zones including, in each zone, encoding the at least l primary backup chunks to create m coding chunks using an erasure coding having parameters k+m, wherein in each zone in which fewer than k primary backup chunks have been accumulated, at most k−l predetermined virtual chunks are used to create partial coding chunks.

### Claim 8 (depends on 7)

The non-transitory machine-readable medium of claim 7, wherein preparing the distributed storage system further includes, in each zone:
retaining one of the m coding chunks;
distributing to a different one of any m−1 remote zones each of the m−1 coding chunks not retained; and
deleting any primary backup chunks to reduce storage overhead.

### Claim 9 (depends on 7)

The non-transitory machine-readable medium of claim 7, further comprising:
recovering unavailable chunks from a failure of 1 to m zones including performing, in each of the zones unaffected by the failure, any one or more of:
identifying any of still available coding chunks created and retained by the zone, and
retrieving any of the still available coding chunks distributed to the zone from another zone, and
creating local copies of any of still available original data chunks from which the still available coding chunks were created; and
reconstructing as many unavailable chunks as possible from the still available coding chunks and the still available original data chunks.

### Claim 10 (depends on 7)

The non-transitory machine-readable medium of claim 7, wherein the operations further comprise adding a new data chunk to an incomplete protection group comprising m partial coding chunks.

### Claim 11 (depends on 7)

The non-transitory machine-readable medium of claim 7, wherein the plurality of at least k+m zones into which the distributed storage system is configured is distributed across a geographical area.

### Claim 12 (depends on 7)

The non-transitory machine-readable medium of claim 7, wherein the distributed storage system is a cloud-based storage system accessible over an inter-network.

### Claim 13

A data processing system, comprising:
a processor; and
a memory coupled to the processor storing instructions which, when executed by the processor, cause the processor to perform storage operations, the operations including
configuring a distributed storage system into at least k+m zones, wherein each zone accumulates at least l primary backup chunks of original data chunks replicated from different remote zones, and wherein l<k, and
preparing the distributed storage system for recovery from a failure of 1 to m zones of the at least k+m zones including, in each zone, encoding the at least l primary backup chunks to create m coding chunks using an erasure coding having parameters k+m, wherein in each zone in which fewer than k primary backup chunks have been accumulated, at most k−1 predetermined virtual chunks are used to create partial coding chunks.

### Claim 14 (depends on 13)

The data processing system of claim 13, wherein preparing the distributed storage system further includes, in each zone:
retaining one of the m coding chunks;
distributing to a different one of any m−1 remote zones each of the m−1 coding chunks not retained; and
deleting any primary backup chunks to reduce storage overhead.

### Claim 15 (depends on 13)

The data processing system of claim 13, further comprising:
recovering unavailable chunks from a failure of 1 to m zones including performing, in each of the zones unaffected by the failure, any one or more of:
identifying any of still available coding chunks created and retained by the zone, and
retrieving any of the still available coding chunks distributed to the zone from another zone, and
creating local copies of any of still available original data chunks from which the still available coding chunks were created; and
reconstructing as many unavailable chunks as possible from the still available coding chunks and the still available original data chunks.

### Claim 16 (depends on 13)

The data processing system of claim 13, wherein the operations further comprise adding a new data chunk to an incomplete protection group comprising m partial coding chunks.

### Claim 17 (depends on 13)

The data processing system of claim 13, wherein the plurality of at least k+m zones into which the distributed storage system is configured is distributed across a geographical area.

### Claim 18 (depends on 13)

The data processing system of claim 13, wherein the distributed storage system is a cloud-based storage system accessible over an inter-network.