Load balancing in cluster storage systems

• US 8,886,781 B2
• Filed: 12/13/2011
• Issued: 11/11/2014
• Est. Priority Date: 12/13/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jain, Navendu, You, Gae-won
• Primary Examiner(s): Gilles, Jude Jean
• Assistant Examiner(s): ALRIYASHI, ABDULKADER MOHAMED
• Application Number:
  US13/324,497
• Publication Number:
  US 20130151683A1
• Time in Patent Office: 1,064 Days
• Field of Search: 709/223, 709/224, 709/213, 709/248, 707/737, 707/E17.046, 711/165, 711/114
• US Class Current: 709/223
• CPC Class Codes: G06F 16/1827 Management specifically adapted to NAS management of storage area networks [SAN] G06F3/067
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0646 Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Methods and systems for load balancing in a cluster storage system are disclosed herein. The method includes identifying a source node within the cluster storage system from which to move a number of data objects, wherein the source node includes a node with a total load exceeding a threshold value. The method also includes selecting the data objects to move from the source node, wherein the data objects are chosen such that the total load of the source node no longer exceeds the threshold value. The method further includes determining a target node within the cluster storage system based on a proximity to the source node and the total load of the target node and moving the data objects from the source node to the target node.

Claims

1. A method for load balancing in a cluster storage system, comprising:

identifying a plurality of source nodes as hot spots within the cluster storage system from which to move a plurality of data objects, wherein a hot spot comprises a node with a total load exceeding a threshold value;

dividing the plurality of source nodes into a plurality of sets of source nodes, wherein each of the plurality of sets of source nodes comprises one source node or a small subset of source nodes with overlapping search radii;

selecting the plurality of data objects to move from each of the plurality of sets of source nodes, wherein the plurality of data objects are chosen in each node such that the total load of each source node no longer exceeds the threshold value;

determining a plurality of target nodes within a specific search radius from each of the plurality of sets of source nodes;

concurrently moving the plurality of data objects from each of the plurality of sets of source nodes to the plurality of target nodes.

2. The method of claim 1, comprising moving any of the plurality of data objects from the source node to any of a plurality of target nodes based on the total load on each of the plurality of target nodes and the proximity of each of the plurality of target nodes to the source node.

3. The method of claim 1, comprising:

identifying a plurality of source nodes with total loads exceeding the threshold value, wherein the plurality of source nodes are within a specific radial distance from one another;

selecting a plurality of data objects to move from each of the plurality of source nodes;

determining a plurality of target nodes within a specific search radius from the plurality of source nodes; and

concurrently moving the plurality of data objects from the plurality of source nodes to the plurality of target nodes.

4. The method of claim 1, comprising randomly selecting the plurality of data objects to move from the source node.

5. The method of claim 1, comprising selecting the plurality of data objects to move from the source node based on a load value, wherein the plurality of data objects are selected starting with a data object with a highest load value and continuing in a descending order.

6. The method of claim 5, wherein the load value comprises a number of input/output requests for a particular data object within the source node.

7. The method of claim 1, wherein moving the plurality of data objects from the source node to the target node comprises minimizing interference during reconfiguration by specifying a resource bandwidth budget or separating foreground traffic and background traffic via the use of transport protocols.

8. The method of claim 1, comprising selecting the plurality of data objects to move from the source node based on a real decision variable assigned to each data object within the source node, wherein the real decision variable comprises a real number between zero and one, or equal to zero or one, and wherein the plurality of data objects are selected to be moved starting with a data object with a highest real decision variable and continuing in a descending order.

9. The method of claim 1, comprising identifying the source node within the cluster storage system from which to move the plurality of data objects using a metadata service in response to an influx of a predetermined number of input/output requests for the source node from any of a plurality of client devices.

10. The method of claim 1, wherein the threshold value is a predetermined threshold value indicating load capacity of the source node comprising determining the threshold value such that a response time of the node may not increase above a specific value or throughput rate measured in terms of whether the number of transactions processed in a given time window exceeds a specific value.

11. A system for load balancing in a cluster storage system, comprising:

a plurality of source nodes, wherein each source node comprises a hot spot node within the cluster storage system with a first total load exceeding a threshold value, wherein the plurality of source nodes are divided into a plurality of sets of source nodes, wherein each of the plurality of sets of source nodes comprises one source node or a small subset of source nodes with overlapping search radii;

a plurality of target nodes, wherein each of the plurality of target nodes comprises a node within the cluster storage system with a second total load not exceeding the threshold value, and wherein each of the plurality the target nodes is within a specific search radius from each of the plurality of sets of source nodes;

a load balancing system configured to;

identify each of the plurality of target nodes by incrementally increasing the specific radius until the target node is identified;

select a plurality of data objects to move from each of the plurality of sets of source nodes to an associated target node, wherein the plurality of data objects are chosen such that the first total load of the source node no longer exceeds the threshold value; and

concurrently move the plurality of data objects from each of the plurality of sets of source nodes to the plurality of target nodes.

12. The system of claim 11, wherein the first total load and the second total load comprise a total number of input/output operations per second or a total number of bytes transferred per second for read and write operations.

13. The system of claim 11, comprising executing multiple instances of the load balancing system in parallel in order to concurrently move a plurality of data objects from each of a plurality of source nodes, wherein the plurality of source nodes comprise non-overlapping nodes that are at least a predetermined distance from one another.

14. The system of claim 11, wherein the target node and the source node comprise servers interconnected through a network, and wherein swap operations comprising swapping the role of a primary replica corresponding to the partition of the data object to be moved are performed prior to moving the data object.

15. The system of claim 11, wherein the system comprises a metadata service configured to map an incoming input/output request from a client device to specific data objects within the source node or the target node, or any combinations thereof.

16. One or more non-transitory, computer-readable storage media for storing computer-readable instructions, the computer-readable instructions providing a load balancing system when executed by one or more processing devices, the computer-readable instructions comprising code configured to:

identify a plurality of source nodes from which to move a plurality of data objects, wherein the plurality of source nodes each comprise a hot spot;

divide the plurality of source nodes into a plurality of sets of source nodes, wherein each of the plurality of sets of source nodes comprises one source node or a small subset of source nodes with overlapping search radii;

select the plurality of data objects to move from each of the plurality of sets of source nodes, wherein the plurality of data objects are chosen such that the source node is no longer the hot spot;

determine a plurality of target nodes within a specific search radius from each of the plurality of sets of source nodes, wherein the target node does not comprise a hot spot;

concurrently move the plurality of data objects from each of the plurality of sets of source nodes to the plurality of target nodes.

17. The one or more non-transitory, computer-readable storage media of claim 16, wherein the hot spot comprises a node with a total number of input/output operations per second or a total number of bytes transferred per second exceeding a threshold value.