DYNAMICALLY CONTROLLING ERASURE CODE DISTRIBUTION IN AN OBJECT STORE

• US 20170288702A1
• Filed: 06/23/2017
• Published: 10/05/2017
• 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
• Granted Patent: US 10,459,821 B2
• Time in Patent Office: 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, 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.

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

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

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

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

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

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.

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.

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

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

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

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

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

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

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

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

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

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

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

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