Dynamically controlling erasure code distribution in an object store

• US 10,459,821 B2
• Filed: 06/23/2017
• Issued: 10/29/2019
• Est. Priority Date: 02/18/2014
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Reinart, John
• Primary Examiner(s): Nguyen, Steve N
• Application Number:
  US15/631,486
• Publication Number:
  US 20170288702A1
• Time in Patent Office: 858 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: 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
• CPC Class 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

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

1. 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.

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

3. The apparatus of claim 2, 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.

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

5. The apparatus of claim 4, 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.

6. The apparatus of claim 5, 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.

7. The apparatus of claim 6, 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.

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

9. The apparatus of claim 8, 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, and at least one of;

a capacity balance measure exceeds a capacity balance threshold, or

a fault tolerance measure exceeds a fault tolerance threshold.

10. The apparatus of claim 3:

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.

11. The apparatus of claim 3:

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.

12. The apparatus of claim 3:

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.

13. The apparatus of claim 3:

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.