Method for replicating data in a backup storage system using a cost function

• US 9,875,163 B1
• Filed: 08/09/2016
• Issued: 01/23/2018
• Est. Priority Date: 06/08/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Douglis, Frederick, Patterson, R. Hugo, Shilane, Philip
• Primary Examiner(s): Song, Jasmine
• Application Number:
  US15/232,652
• Time in Patent Office: 532 Days
• Field of Search: 711162
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 11/3442 for planning or managing the needed capacity
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: G06F 2201/83 the solution involving signatures
• CPC Class Codes: G06F 2206/1504 Cost estimation
• CPC Class Codes: G06F 2206/1508 Load balancing
• CPC Class Codes: G06F 3/0221 Arrangements for reducing keyboard size for transport or storage, e.g. foldable keyboards, keyboards with collapsible keys G06F3/0216 takes precedence; for keyboards integrated in a laptop computer G06F1/1666
• CPC Class Codes: G06F 3/0647 Migration mechanisms

Abstract

An operating state of each of a plurality of storage units of a storage system is periodically monitored, including a storage capacity, a throughput, and overlap of clients associated with the storage units. In response to a request to redistribute data from a first of the storage units to another storage unit, a cost factor for each of remaining storage units to relocate the data of the first storage unit to each of the remaining storage units is determined. A cost factor of each of the remaining storage units is determined based on at least one of the storage capacity, the throughput, or the overlap of clients of the storage unit. A second of the storage units having a lowest cost factor amongst the remaining storage units is selected. At least a portion of the data of the first storage unit is migrated to the second storage unit.

Claims

1. A computer-implemented method for managing a storage space of a storage system, the method comprising:

periodically monitoring an operating state of each of a plurality of storage units of a storage system, including a storage capacity, a throughput, and overlap of clients associated with the storage units;

in response to a request to redistribute data from a first of the storage units to another storage unit, determining a cost factor for each of remaining storage units to relocate the data of the first storage unit to each of the remaining storage units, including calculating a penalty factor based on storage capacity utilization of the storage unit, wherein a cost factor of each of the remaining storage units is determined based on at least one of the storage capacity, the throughput, or the overlap of clients of the storage unit;

selecting a second of the storage units having a lowest cost factor amongst the remaining storage units; and

migrating at least a portion of the data of the first storage unit to the second storage unit.

2. The method of claim 1, further comprising redirecting subsequent access of the migrated data to the second storage unit.

3. The method of claim 1, wherein determining a cost factor for each of remaining storage units comprises calculating a fit penalty factor representing a number of clients whose data cannot be stored in the storage unit.

4. The method of claim 1, further comprising determining a cost factor for each of remaining storage units comprises calculating a data movement factor based on a movement weight representing a willingness of moving data of the storage unit.

5. A computer-implemented method for managing a storage space of a storage system, the method comprising:

periodically monitoring an operating state of each of a plurality of storage units of a storage system, including a storage capacity, a throughput, and overlap of clients associated with the storage units;

in response to a request to redistribute data from a first of the storage units to another storage unit, determining a cost factor for each of remaining storage units to relocate the data of the first storage unit to each of the remaining storage units, wherein determining a cost factor for each of remaining storage units comprises;

calculating a first penalty factor based on storage capacity utilization of the storage unit, and

calculating a second penalty factor based on a throughput utilization of the storage unit, wherein the cost factor is determined based on the first penalty factor and the second penalty factor, wherein a cost factor of each of the remaining storage units is determined based on at least one of the storage capacity, the throughput, or the overlap of clients of the storage unit;

selecting a second of the storage units having a lowest cost factor amongst the remaining storage units; and

migrating at least a portion of the data of the first storage unit to the second storage unit.

6. The method of claim 5, wherein the first penalty factor is calculated by applying a plurality of weights to the storage capacity utilization according to a plurality of the storage capacity utilization thresholds in view of the storage capacity utilization.

7. The method of claim 5, wherein the second penalty factor is calculated by applying a plurality of weights to the throughput utilization according to a plurality of throughput utilization thresholds in view of the throughput utilization.

8. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations of managing a storage space of a storage system, the operations comprising:

periodically monitoring an operating state of each of a plurality of storage units of a storage system, including a storage capacity, a throughput, and overlap of clients associated with the storage units;

in response to a request to redistribute data from a first of the storage units to another storage unit, determining a cost factor for each of remaining storage units to relocate the data of the first storage unit to each of the remaining storage units, including calculating a penalty factor based on storage capacity utilization of the storage unit, wherein a cost factor of each of the remaining storage units is determined based on at least one of the storage capacity, the throughput, or the overlap of clients of the storage unit;

selecting a second of the storage units having a lowest cost factor amongst the remaining storage units; and

migrating at least a portion of the data of the first storage unit to the second storage unit.

9. The machine-readable medium of claim 8, wherein the operations further comprise redirecting subsequent access of the migrated data to the second storage unit.

10. The machine-readable medium of claim 8, wherein determining a cost factor for each of remaining storage units comprises calculating a fit penalty factor representing a number of clients whose data cannot be stored in the storage unit.

11. The machine-readable medium of claim 8, wherein the operations further comprise determining a cost factor for each of remaining storage units comprises calculating a data movement factor based on a movement weight representing a willingness of moving data of the storage unit.

12. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations of managing a storage space of a storage system, the operations comprising:

periodically monitoring an operating state of each of a plurality of storage units of a storage system, including a storage capacity, a throughput, and overlap of clients associated with the storage units;

in response to a request to redistribute data from a first of the storage units to another storage unit, determining a cost factor for each of remaining storage units to relocate the data of the first storage unit to each of the remaining storage units, wherein determining a cost factor for each of remaining storage units comprises;

calculating a first penalty factor based on storage capacity utilization of the storage unit, and

calculating a second penalty factor based on a throughput utilization of the storage unit, wherein the cost factor is determined based on the first penalty factor and the second penalty factor, wherein a cost factor of each of the remaining storage units is determined based on at least one of the storage capacity, the throughput, or the overlap of clients of the storage unit;

selecting a second of the storage units having a lowest cost factor amongst the remaining storage units; and

migrating at least a portion of the data of the first storage unit to the second storage unit.

13. The machine-readable medium of claim 12, wherein the first penalty factor is calculated by applying a plurality of weights to the storage capacity utilization according to a plurality of the storage capacity utilization thresholds in view of the storage capacity utilization.

14. The machine-readable medium of claim 12, wherein the second penalty factor is calculated by applying a plurality of weights to the throughput utilization according to a plurality of throughput utilization thresholds in view of the throughput utilization.

15. A storage system, comprising:

a plurality of storage units;

a processor, and

a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform operations of managing a storage space of a storage system, the operations including

periodically monitoring an operating state of each of the plurality of storage units, including a storage capacity, a throughput, and overlap of clients associated with the storage units,

in response to a request to redistribute data from a first of the storage units to another storage unit, determining a cost factor for each of remaining storage units to relocate the data of the first storage unit to each of the remaining storage units, including calculating a penalty factor based on storage capacity utilization of the storage unit, wherein a cost factor of each of the remaining storage units is determined based on at least one of the storage capacity, the throughput, or the overlap of clients of the storage unit,

selecting a second of the storage units having a lowest cost factor amongst the remaining storage units, and

migrating at least a portion of the data of the first storage unit to the second storage unit.

16. The system of claim 15, wherein the operations further comprise redirecting subsequent access of the migrated data to the second storage unit.

17. The system of claim 15, wherein determining a cost factor for each of remaining storage units comprises calculating a fit penalty factor representing a number of clients whose data cannot be stored in the storage unit.

18. The system of claim 15, wherein the operations further comprise determining a cost factor for each of remaining storage units comprises calculating a data movement factor based on a movement weight representing a willingness of moving data of the storage unit.

19. A storage system, comprising:

a plurality of storage units;

a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform operations of managing a storage space of a storage system, the operations including

periodically monitoring an operating state of each of a plurality of storage units of a storage system, including a storage capacity, a throughput, and overlap of clients associated with the storage units,

in response to a request to redistribute data from a first of the storage units to another storage unit, determining a cost factor for each of remaining storage units to relocate the data of the first storage unit to each of the remaining storage units, wherein determining a cost factor for each of remaining storage units comprises;

calculating a first penalty factor based on storage capacity utilization of the storage unit, and

calculating a second penalty factor based on a throughput utilization of the storage unit, wherein the cost factor is determined based on the first penalty factor and the second penalty factor, wherein a cost factor of each of the remaining storage units is determined based on at least one of the storage capacity, the throughput, or the overlap of clients of the storage unit,

selecting a second of the storage units having a lowest cost factor amongst the remaining storage units, and

migrating at least a portion of the data of the first storage unit to the second storage unit.

20. The system of claim 19, wherein the first penalty factor is calculated by applying a plurality of weights to the storage capacity utilization according to a plurality of the storage capacity utilization thresholds in view of the storage capacity utilization.

21. The system of claim 19, wherein the second penalty factor is calculated by applying a plurality of weights to the throughput utilization according to a plurality of throughput utilization thresholds in view of the throughput utilization.