Dynamically controlling erasure code distribution in an object store

• US 9,727,437 B2
• Filed: 02/18/2014
• Issued: 08/08/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
• Primary Examiner(s): NGUYEN, STEVE N
• Application Number:
  US14/183,310
• Publication Number:
  US 20150236724A1
• Time in Patent Office: 1,267 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. A non-transitory computer-readable storage medium storing computer-executable instructions that when executed by a computer cause the computer to perform a method, the method comprising:

accessing a first data concerning an operating condition associated with an erasure code based object storage system, the object storage system comprising two or more devices on which an erasure code can be stored, where the operating condition concerns a load balance measure associated with the object storage system, and at least one of a capacity balance measure associated with the object storage system, or a fault tolerance measure associated with the object storage system;

recognizing an association between a plurality of objects associated with an erasure code to be stored in the object storage system;

identifying 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 storage system;

generating a prediction of where, in the object storage system, a read operation will be performed on the plurality of objects, based, at least in part, on the usage pattern; and

creating 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 storage system, where the distribution plan is based, at least in part, on the first data and the prediction.

2. The non-transitory computer-readable storage medium of claim 1, the method comprising:

creating 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 storage system, where the redistribution plan is based, at least in part, on the first data or the prediction, where the redistribution plan is a random approach redistribution plan, or a round-robin approach redistribution plan.

3. The non-transitory computer-readable storage medium of claim 2, the method comprising creating the distribution plan or the redistribution plan in response to receiving a request to store an erasure code in the object storage system.

4. The non-transitory computer-readable storage medium of claim 2, the method comprising:

accessing a second data concerning the operating condition, where the second data is more up-to-date than the first data, and

selectively manipulating the distribution plan or the redistribution plan based on the second data.

5. The non-transitory computer-readable storage medium of claim 4, the method comprising selectively manipulating the distribution plan or the redistribution plan upon determining that:

the 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 load threshold,

the capacity balance measure exceeds a capacity balance threshold, or

the fault tolerance measure exceeds a fault tolerance threshold.

6. The non-transitory computer-readable storage medium of claim 2, the method comprising selectively manipulating the distribution plan or the redistribution plan according to a user-defined schedule.

7. The non-transitory computer-readable storage medium of claim 2,

where creating the distribution plan includes 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 creating the redistribution plan includes identifying, based on a second user-defined rule, a source device in the object storage system from which a first erasure code will be relocated and a target device in the object storage system to which the first erasure code will be relocated.

8. The non-transitory computer-readable storage medium of claim 2,

where creating the distribution plan includes identifying, based on a first automated rule, one or more members of the two or more devices that will support future requests to store erasure codes, and

where creating the redistribution plan includes identifying, based on a second automated rule, a source device in the object storage system from which a first erasure code will be relocated and a target device in the object storage system to which the first erasure code will be relocated.

9. The non-transitory computer-readable storage medium of claim 2,

where the distribution plan depends, at least in part, on a first weighted combination of two or more of, the load balance measure, the capacity balance measure, the fault tolerance measure, and the usage pattern measure, 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 measure.

10. The non-transitory computer-readable storage medium of claim 2,

where the distribution plan controls distribution of erasure codes to two or more different eligible devices in the object storage system according to a first plan or schedule, and

where the redistribution plan controls distribution of erasure codes to two or more different eligible devices in the object storage system according to a second plan or schedule.

11. The non-transitory computer-readable storage medium of claim 1, the method comprising controlling an erasure code to be stored in the object storage system at a location determined by the distribution plan.

12. The non-transitory computer-readable storage medium of claim 11, the method comprising controlling an erasure code to be relocated from a first device in the object storage system to a second device in the object storage system according to the redistribution plan.