# US 2017/0288702 A1 · Dynamically controlling erasure code distribution in an object store

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

- Number: US 2017/0288702 A1
- Document ID: US20170288702A1
- Status: Published application
- Kind: A1
- Application number: 15/631,486
- Filed: 2017-06-23
- Published: 2017-10-05
- Earliest claimed: 2014-02-18
- Assignees: Quantum Corporation
- Applicants: Quantum Corporation
- Inventors: John Reinart
- Web page: https://patentgrep.com/patent/US20170288702A1

## CPC

- G06F 11/3466: {Performance evaluation by tracing or monitoring}
- G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems}
- 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}
- G06F 3/064: {Management of blocks}
- 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

Example apparatus and methods monitor conditions in an object storage system. The conditions monitored may include a load balance measure in the system, a capacity balance measure in the system, a fault tolerance measure in the system, or a usage pattern measure in the system. A distribution plan or redistribution plan for storing or moving erasure codes in the object storage system may be determined based on the conditions. The distribution plan or the redistribution plan for the erasure codes may be updated dynamically in response to changing conditions in the object storage system. The distribution or redistribution may depend on a weighted combination of the load balance measure, the capacity balance measure, the fault tolerance measure, or the usage pattern measure so that responding to one sub-optimal condition (e.g., load imbalance) does not create a different sub-optimal condition (e.g., unacceptable fault tolerance).

## Claims

### Claim 1

An apparatus, comprising:
a processor;
a memory;
a set of logics that control the location of an erasure code in an erasure code based object store, where the object store includes a plurality of storage apparatus; and
an interface that connects the processor, the memory, and the set of logics;
the set of logics comprising:
a first logic that controls the location of the erasure code in the object store based on processing loads experienced by two or more members of the plurality of storage apparatus;
a second logic that controls the location of the erasure code in the object store based on storage capacities present in two or more members of the plurality of storage apparatus; and
a third logic that controls the location of the erasure code in the object store based on usage patterns experienced by two or more members of the plurality of storage apparatus and a fault tolerance measure associated with the object store.

### Claim 2 (depends on 1)

The apparatus of claim 1, where the first logic controls requests to store erasure codes in the object store to be handled by the member of the plurality of storage apparatus having the lowest processing load, or where first logic ranks the plurality of storage apparatus in order according to load, identifying which of the plurality of storage apparatus are operating above a load threshold, or identifying which of the plurality of storage apparatus are operating below a load threshold.

### Claim 3 (depends on 1)

The apparatus of claim 1, where:
the second logic controls requests to store erasure codes in the object store to be handled by the member of the plurality of storage apparatus having the most available storage capacity, or
the second logic controls erasure codes to be moved from the member of the plurality of storage apparatus having the least available storage capacity to the member of the plurality of storage apparatus having the most available storage capacity.

### Claim 4 (depends on 1)

The apparatus of claim 1, where the usage patterns concern a relationship between an ingest site and an accessing site, and a relationship between a plurality of objects or erasure codes to be stored in the erasure code based object store, and
where the third logic controls erasure codes to be moved from a member of the plurality of storage apparatus located at a site that accesses the erasure code the least to a member of the plurality of storage apparatus located at a site that accesses the erasure code the most.

### Claim 5 (depends on 1)

The apparatus of claim 1, where:
the first logic controls requests to store erasure codes in the object store to be handled by members of the plurality of storage apparatus having processing loads less than a processing load threshold;
the second logic controls requests to store erasure codes in the object store to be handled by members of the plurality of storage apparatus having a storage capacity greater than a storage capacity threshold;
the second logic controls erasure codes to be moved from members of the plurality of storage apparatus having a storage capacity less than the storage capacity threshold to members of the plurality of storage apparatus having a storage capacity greater than the storage capacity threshold, and
the third logic controls erasure codes to be moved from members of the plurality of storage apparatus located at sites that access the erasure codes less than a usage pattern threshold to members of the plurality of storage apparatus located at sites that access the erasure codes more than the usage pattern threshold.

### Claim 6 (depends on 5)

The apparatus of claim 5, comprising a fourth logic that controls the first logic, the second logic, and the third logic based on a combined utility function that weighs the processing loads, the storage capacities, and the usage patterns for two or more members of the plurality of storage apparatus.

### Claim 7

A system, comprising:
means for identifying where to store erasure codes in an object store based on a processing load and at least one of a storage capacity, a fault tolerance, or a usage pattern associated with an apparatus in the object store at a first time; and
means for identifying where to relocate erasure codes in the object store based on a processing load, a storage capacity, a fault tolerance level, or a usage pattern associated with an apparatus in the object store at a second, later time, where erasure codes are relocated based on a random approach redistribution plan, or a round-robin approach redistribution plan,
where the means for identifying where to store erasure codes is configured to optimize a weighted value computed from the processing load, the storage capacity, the fault tolerance, or the usage pattern at a time when an erasure code is stored in the object store, and
where the means for identifying where to relocate erasure codes is configured to optimize a weighted value computed from the processing load, the storage capacity, the fault tolerance, or the usage pattern at a time after the erasure code is stored in the object store.

### Claim 8

An apparatus that dynamically controls erasure code distribution in an object store, the apparatus comprising:
a processor;
a memory;
a set of circuits that control the location of an erasure code in an erasure code based object store, where the object store includes two or more devices on which an erasure code can be stored; and
an interface that connects the processor, the memory, and the set of circuits;
the set of circuits comprising:
a first circuit that accesses a first data concerning an operating condition associated with the object store, and that recognizes an association between a plurality of objects associated with an erasure code to be stored in the object store;
a second circuit that identifies a usage pattern associated with the plurality of objects, where the usage pattern is based, at least in part, on the association, where the usage pattern concerns a relationship between an ingest site and an accessing site, and a relationship between the plurality of objects or erasure codes to be stored in the object store;
a third circuit that generates a prediction of where, in the object store, a read operation will be performed on the plurality of objects, based, at least in part, on the usage pattern; and
a fourth circuit that creates a distribution plan to control distribution of erasure codes to members of the two or more devices when the erasure codes are stored in the object store, where the distribution plan is based, at least in part, on the first data and the prediction.

### Claim 9 (depends on 8)

The apparatus of claim 8, where the fourth circuit controls an erasure code to be stored in the object store at a location determined by the distribution plan.

### Claim 10 (depends on 9)

The apparatus of claim 9, comprising a fifth circuit that creates a redistribution plan to control redistribution of erasure codes between members of the two or more devices after the erasure codes have been stored in the object store, where the redistribution plan is based, at least in part, on the first data or the prediction.

### Claim 11 (depends on 10)

The apparatus of claim 10, where the redistribution plan is a random approach redistribution plan, or a round-robin approach redistribution plan.

### Claim 12 (depends on 11)

The apparatus of claim 11, where the fifth circuit controls an erasure code to be relocated from a first device in the object store to a second device in the object store according to the redistribution plan.

### Claim 13 (depends on 12)

The apparatus of claim 12, where the fourth circuit creates the distribution plan, or the fifth circuit creates the redistribution plan, in response to receiving a request to store an erasure code in the object store.

### Claim 14 (depends on 13)

The apparatus of claim 13, comprising a sixth circuit that accesses a second data concerning the operating condition and selectively manipulates the distribution plan or the redistribution plan based on the second data, where the second data is more up-to-date than the first data.

### Claim 15 (depends on 14)

The apparatus of claim 14, where the sixth circuit selectively manipulates the distribution plan or the redistribution plan according to a user-defined schedule.

### Claim 16 (depends on 15)

The apparatus of claim 15, where the sixth circuit selectively manipulates the distribution plan or the redistribution plan upon determining that:
a load balance measure exceeds a load balance threshold, where the load balance measure includes ranking the two or more devices in order according to load, identifying which of the two or more devices are operating above a load threshold, or identifying which of the two or more devices are operating below a threshold,
a capacity balance measure exceeds a capacity balance threshold, or
a fault tolerance measure exceeds a fault tolerance threshold.

### Claim 17 (depends on 10)

The apparatus of claim 10:
where the fourth circuit creates the distribution plan by identifying, based on a first user-defined rule, one or more members of the two or more devices that will support future requests to store erasure codes; and
where the fifth circuit creates the redistribution plan by identifying, based on a second user-defined rule, a source device in the object store from which a first erasure code will be relocated and a target device in the object store to which the first erasure code will be relocated.

### Claim 18 (depends on 10)

The apparatus of claim 10:
where the fourth circuit creates the distribution plan by identifying, based on a first automated rule, one or more members of the two or more devices that will support future request to store erasure codes; and
where the fifth circuit creates the redistribution plan by identifying, based on a second automated rule, a source device in the object store from which a first erasure code will be relocated and a target device in the object store to which the first erasure code will be relocated.

### Claim 19 (depends on 10)

The apparatus of claim 10:
where the distribution plan depends, at least in part, on a first weighted combination of two or more of, a load balance measure, a capacity balance measure, a fault tolerance measure, and the usage pattern; and
where the redistribution plan depends, at least in part, on a second weighted combination of two or more of, the load balance measure, the capacity balance measure, the fault tolerance measure, and the usage pattern.

### Claim 20 (depends on 10)

The apparatus of claim 10:
where the fourth circuit controls distribution of erasure codes to two or more different eligible devices in the object store according to a first plan or a schedule; and
where the fifth circuit controls redistribution of erasure codes to two or more different eligible devices in the object store according to a second plan or schedule.