System and method for allocating a storage unit for backup in a storage system with load balancing

• US 8,484,356 B1
• Filed: 06/29/2011
• Issued: 07/09/2013
• 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): VU, VIET DUY
• Application Number:
  US13/172,687
• Time in Patent Office: 741 Days
• Field of Search: 709/213, 709/214, 709/215, 709/223, 709/224, 709/226
• US Class Current: 709/226
• 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 request for allocating a storage unit of a storage system is received to back up data of one or more clients. The storage system includes multiple storage units and each storage unit storing data that is deduplicated within each storage unit. In response to the request, one or more of the storage units are selected based on an amount of deduplicated data that would be stored in each of the storage units after storing the data of the one or more clients. The selected one or more storage units are allocated to the one or more clients to back up the data of the one or more clients.

Claims

1. A computer-implemented method, comprising:

receiving a request for allocating a storage unit of a storage system to back up data of one or more clients, the storage system having a plurality of storage units, each storage unit storing data that is deduplicated within each storage unit;

in response to the request, selecting one or more of the plurality of storage units based on an amount of deduplicated data that would be stored in each of the storage units after storing the data of the one or more clients, including

comparing fingerprints of the data of the one or more clients with fingerprints of at least a portion of data stored in each of the storage units, and

identifying a first of the storage units as a selection candidate that contains a significant fraction of fingerprints of one or more of the one or more clients from the storage units based on the comparison; and

allocating the selected one or more storage units to the one or more clients to back up the data of the one or more clients.

2. The method of claim 1, further comprising:

determining at least one of a storage capacity and throughput capacity for each of the storage units; and

identifying a second of the storage units as the selection candidate that contains less of the fingerprints of the one or more clients than the first storage unit, wherein the second storage unit has at least one of an available storage capacity and throughput capacity that is higher than the first storage unit.

3. The method of claim 1, wherein the amount of deduplicated data is determined based on an estimate of samples of data stored in the storage units and samples of data of the client.

4. The method of claim 1, wherein the amount of deduplicated data is estimated using at least one of a Bloom filtering method and a sort-merge method on fingerprints of at least a portion of data stored in the storage units.

5. The method of claim 1, wherein selecting one or more of the storage units comprises:

assigning the one or more clients to one or more of the storage units; and

computing a cost based on estimated capacity and throughput requirements of the storage units in view of the assigned storage units associated with the one or more clients and the overlap of clients stored on the same storage unit.

6. The method of claim 5, further comprising iteratively performing the assigning and the computing until the cost drops below a first predetermined threshold or a number of iterations exceed a second predetermined threshold.

7. The method of claim 5, wherein the cost is calculated based on a first measure of variation of a capacity utilization and a second measure of variation of a throughput utilization amongst the storage units.

8. The method of claim 7, wherein computing the cost further comprises:

performing one or more of following operations;

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

calculating a second penalty factor based on a throughput utilization of each storage unit,

determining a fit penalty representing a number of clients whose data cannot be stored in each storage unit, and

determining a data movement factor based on a movement weight representing a willingness of moving data of each storage unit; and

determining the cost based on one or more of the first penalty factor, second penalty factor, fit penalty, and data movement factor of each of the storage units.

9. The method of claim 8, wherein calculating a first penalty factor based on a capacity utilization comprises computing the first penalty factor by applying a plurality of weights to the capacity utilization according to a plurality of capacity utilization thresholds in view of the capacity utilization.

10. The method of claim 8, wherein calculating a second penalty factor based on a throughput utilization comprises computing the second penalty factor by applying a plurality of weights to the throughput utilization according to a plurality of throughput utilization thresholds in view of the throughput utilization.

11. The method of claim 8, wherein computing the cost further comprises assigning an importance value to at least one of the one or more clients, wherein a fit penalty of a storage unit is determined based on the associated importance value of the at least one of the one or more clients.

12. The method of claim 5, further comprising:

periodically monitoring the capacity and throughput for each of the storage units; and

redistributing data stored in the storage units to another pool of storage units based on the monitored capacities and throughputs of the storage units.

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

receiving a request for allocating a storage unit of a storage system to back up data of one or more clients, the storage system having a plurality of storage units, each storage unit storing data that is deduplicated within each storage unit;

in response to the request, selecting one or more of the plurality of storage units based on an amount of deduplicated data would be stored in each of the storage units after storing the data of the one or more clients, including

comparing fingerprints of the data of the one or more clients with fingerprints of at least a portion of data stored in each of the storage units, and

identifying a first of the storage units as a selection candidate that contains a significant fraction of fingerprints of one or more of the one or more clients from the storage units based on the comparison; and

allocating the selected one or more storage units to the one or more clients to back up the data of the one or more clients.

14. The non-transitory machine-readable storage medium of claim 13, wherein the method further comprises:

determining at least one of a storage capacity and throughput capacity for each of the storage units; and

identifying a second of the storage units as the selection candidate that contains less of the fingerprints of the one or more clients than the first storage unit, wherein the second storage unit has at least one of an available storage capacity and throughput capacity that is higher than the first storage unit.

15. The non-transitory machine-readable storage medium of claim 13, wherein the amount of deduplicated data is determined based on an estimate of samples of data stored in the storage units and samples of data of the client.

16. The non-transitory machine-readable storage medium of claim 13, wherein the amount of deduplicated data is estimated using at least one of a Bloom filtering method and a sort-merge method on fingerprints of at least a portion of data stored in the storage units.

21. The non-transitory machine-readable storage medium of claim 13, wherein selecting one or more of the storage units comprises:

assigning the one or more clients to one or more of the storage units; and

computing a cost based on estimated capacity and throughput requirements of the storage units in view of the assigned storage units associated with the one or more clients and the overlap of clients stored on the same storage unit.

22. The non-transitory machine-readable storage medium of claim 21, wherein the method further comprises iteratively performing the assigning and the computing until the cost drops below a first predetermined threshold or a number of iterations exceed a second predetermined threshold.

23. The non-transitory machine-readable storage medium of claim 21, wherein the cost is calculated based on a first measure of variation of a capacity utilization and a second measure of variation of a throughput utilization amongst the storage units.

24. The non-transitory machine-readable storage medium of claim 23, wherein computing the cost further comprises:

performing one or more of following operations;

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

calculating a second penalty factor based on a throughput utilization of each storage unit,

determining a fit penalty representing a number of clients whose data cannot be stored in each storage unit, and

determining a data movement factor based on a movement weight representing a willingness of moving data of each storage unit; and

determining the cost based on one or more of the first penalty factor, second penalty factor, fit penalty, and data movement factor of each of the storage units.

25. The non-transitory machine-readable storage medium of claim 24, wherein calculating a first penalty factor based on a capacity utilization comprises computing the first penalty factor by applying a plurality of weights to the capacity utilization according to a plurality of capacity utilization thresholds in view of the capacity utilization.

26. The non-transitory machine-readable storage medium of claim 24, wherein calculating a second penalty factor based on a throughput utilization comprises computing the second penalty factor by applying a plurality of weights to the throughput utilization according to a plurality of throughput utilization thresholds in view of the throughput utilization.

27. The non-transitory machine-readable storage medium of claim 24, wherein computing the cost further comprises assigning an importance value to at least one of the one or more clients, wherein a fit penalty of a storage unit is determined based on the associated importance value of the at least one of the one or more clients.

28. The non-transitory machine-readable storage medium of claim 21, wherein the method further comprises:

periodically monitoring the capacity and throughput for each of the storage units; and

redistributing data stored in the storage units to another pool of storage units based on the monitored capacities and throughputs of the storage units.

17. A storage system, comprising:

a processor;

a plurality of storage units, each storage unit storing data that is deduplicated within each storage unit; and

a client assignment module executed by the processor, in response to a request for allocating a storage unit to back up data of one or more clients, to select one or more of the plurality of storage units based on an amount of deduplicated data that would be stored in each of the storage units after storing the data of the one or more clients and to allocate the selected one or more storage units to the one or more clients to back up the data of the one or more clients, wherein selecting one or more of the plurality of storage units comprises,

comparing fingerprints of the data of the one or more clients with fingerprints of at least a portion of data stored in each of the storage units, and

identifying a first of the storage units as a selection candidate that contains a significant fraction of fingerprints of one or more of the one or more clients from the storage units based on the comparison.

18. The system of claim 17, wherein the client assignment module is further configured to:

determine at least one of a storage capacity and throughput capacity for each of the storage units; and

identify a second of the storage units as the selection candidate that contains less of the fingerprints of the one or more clients than the first storage unit, wherein the second storage unit has at least one of an available storage capacity and throughput capacity that is higher than the first storage unit.

19. The system of claim 17, wherein the amount of deduplicated data is determined based on an estimate of samples of data stored in the storage units and samples of data of the client.

20. The system of claim 17, wherein the amount of deduplicated data is estimated using at least one of a Bloom filtering method and a sort-merge method on fingerprints of at least a portion of data stored in the storage units.