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

• US 9,436,292 B1
• Filed: 06/29/2011
• Issued: 09/06/2016
• Est. Priority Date: 06/08/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Douglis, Frederick, Patterson, R. Hugo, Shilane, Philip N.
• Primary Examiner(s): Rutz, Jared
• Assistant Examiner(s): Ahmed, Hamdy S
• Application Number:
  US13/172,692
• Time in Patent Office: 1,896 Days
• Field of Search: 711/162
• US Class Current: 1/1
• 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

A cost function is determined for assigning first deduplicating storage units of a first storage system for replication onto second deduplicating storage units of a second storage system. One or more of the first storage units in the first storage system are assigned to one or more of the second storage units in the second storage system based on a minimized cost resulting from the cost function.

Claims

1. A computer-implemented method, comprising:

determining a cost function of assigning a plurality of first deduplicating storage units of a first storage system for replication onto a plurality of second deduplicating storage units of a second storage system;

calculating a cost using the cost function based on an amount of deduplicated data to be stored in each of the second storage units after storing data of one or more of the first storage units;

comparing the calculated cost with a first predetermined threshold to derive a minimized cost;

if the calculated cost is greater than the first predetermined threshold, reassigning at least one of the one or more first storage units to a different one of the second storage units;

iteratively performing calculating the cost using the cost function and comparing the cost with the first predetermined threshold until the cost drops below the first predetermined threshold or a number of iterations exceeds a second predetermined threshold; and

assigning one or more of the first storage units in the first storage system to one or more of the second storage units in the second storage system based on the minimized cost.

2. The method of claim 1, wherein the cost function is configured to calculate the cost further based on a storage capacity and a throughput capacity for each of the second storage units in view of a storage capacity requirement and a throughput requirement for each of the first storage units.

3. The method of claim 2, wherein the cost function is configured to calculate the cost further based on a first measure of variation of a capacity utilization and a second measure of variation of a throughput utilization of the second storage units.

4. The method of claim 1, wherein calculating a cost using the cost function based on an amount of deduplicated data comprises:

comparing fingerprints of at least a portion of data stored in the first storage units with fingerprints of at least a portion of data stored in the second storage units; and

identifying a storage unit candidate from the second storage units that contains a significant fraction of the fingerprints of the first storage units based on the comparison.

5. The method of claim 1, wherein the cost is calculated further based on at least one of a geographic requirement and a security requirement of the first storage units.

6. The method of claim 1, further comprising replicating data of the one or more first storage units to the assigned one or more second storage units, wherein a storage unit having a higher bandwidth to the one or more first storage units is replicated first.

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

determining a cost function of assigning a plurality of first deduplicating storage units of a first storage system for replication onto a plurality of second deduplicating storage units of a second storage system;

calculating a cost using the cost function based on an amount of deduplicated data that would be stored in each of the second storage units after storing data of the one or more of the first storage units;

comparing the calculated cost with a first predetermined threshold to derive a minimized cost;

if the calculated cost is greater than the first predetermined threshold, reassigning at least one of the one or more first storage units to a different one of the second storage units;

iteratively performing calculating the cost using the cost function and comparing the cost with the first predetermined threshold until the cost drops below the first predetermined threshold or a number of iterations exceeds a second predetermined threshold; and

assigning one or more of the first storage units in the first storage system to one or more of the second storage units in the second storage system based on the minimized cost.

8. The non-transitory machine-readable storage medium of claim 7, wherein the cost function is configured to calculate the cost further based on a storage capacity and a throughput capacity for each of the second storage units in view of a storage capacity requirement and a throughput requirement for each of the first storage units.

9. The non-transitory machine-readable storage medium of claim 8, wherein the cost function is configured to calculate the cost further based on a first measure of variation of a capacity utilization and a second measure of variation of a throughput utilization of the second storage units.

10. The non-transitory machine-readable storage medium of claim 7, wherein calculating a cost using the cost function based on an amount of deduplicated data comprises:

comparing fingerprints of at least a portion of data stored in the first storage units with fingerprints of at least a portion of data stored in the second storage units; and

identifying a storage unit candidate from the second storage units that contains a significant fraction of the fingerprints of the first storage units based on the comparison.

11. The non-transitory machine-readable storage medium of claim 7, wherein the cost is calculated further based on at least one of a geographic requirement and a security requirement of the first storage units.

12. The non-transitory machine-readable storage medium of claim 7, wherein the method further comprises replicating data of the one or more first storage units to the assigned one or more second storage units, wherein a storage unit having a higher bandwidth to the one or more first storage units is replicated first.

13. An apparatus, comprising:

a processor;

a memory coupled to the processor;

a cost calculator to determine a cost using a cost function for assigning a plurality of first deduplicating storage units of a first storage system for replication onto a plurality of second deduplicating storage units of a second storage system, wherein the cost calculator is configured to;

calculate the cost using the cost function based on an amount of deduplicated data that would be stored in each of the second storage units after storing data of the one or more of the first storage units; and

compare the cost with a first predetermined threshold to derive a minimized cost, wherein if the calculated cost is greater than the first predetermined threshold, at least one of the one or more first storage units is reassigned to a different one of the second storage units, and wherein the cost is iteratively calculated using the cost function and compared with the first predetermined threshold until the cost drops below the first predetermined threshold or a number of iterations exceeds a second predetermined threshold; and

a storage assignment unit to assign one or more of the first storage units in the first storage system to one or more of the second storage units in the second storage system based on the minimized cost resulting from the cost function.

14. The apparatus of claim 13, wherein the cost calculator is configured to calculate the cost further based on a storage capacity and a throughput capacity for each of the second storage units in view of a storage capacity requirement and a throughput requirement for each of the first storage units.

15. The apparatus of claim 14, wherein the cost calculator is configured to calculate the cost further based on a first measure of variation of a capacity utilization and a second measure of variation of a throughput utilization of the second storage units.

16. The apparatus of claim 13, wherein in determining the cost, the cost calculator is configured to:

compare fingerprints of at least a portion of data stored in the first storage units with fingerprints of at least a portion of data stored in the second storage units; and

identify a storage unit candidate from the second storage units that contains a significant fraction of the fingerprints of the first storage units based on the comparison.

17. The apparatus of claim 13, wherein the cost is calculated further based on at least one of a geographic requirement and a security requirement of the first storage units.

18. The apparatus of claim 13, wherein data of the one or more first storage units is replicated to the assigned one or more second storage units, wherein a storage unit having a higher bandwidth to the one or more first storage units is replicated first.