Dynamic load balancing in a scalable environment

• US 8,868,711 B2
• Filed: 02/03/2012
• Issued: 10/21/2014
• Est. Priority Date: 02/03/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Calder, Bradley Gene, Wang, Ju, Skjolsvold, Arild E.
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): Abedin, Normin
• Application Number:
  US13/366,052
• Publication Number:
  US 20130204991A1
• Time in Patent Office: 991 Days
• Field of Search: 709/223, 709/224, 709/225, 709/226, 709/203
• US Class Current: 709/223
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Systems and methods are provided that enable a general framework for partitioning application-defined jobs (e.g., computation) in a scalable environment. The general framework decouples partitioning of a job from the other aspects of the job. As a result, the effort required to define the application-defined computation in a scalable environment is reduced or minimized, as the user is not required to provide a partitioning algorithm. The general framework further allows a user to provide load balancing conditions to allow for modification of how partitions are assigned.

Claims

1. A method for performing load balancing in a distributed computing environment, comprising:

receiving a namespace from an application comprising a plurality of key values that span the namespace, the namespace comprising at least one of a range of possible input values for a job or a range of possible identifiers for a job within a computing environment;

receiving an application-defined interface comprising expressions corresponding to load balancing conditions based on one or more of the application-defined metrics and one or more conditional logic expressions;

evaluating at least a first load balancing expression;

initiating a load balancing action responsive to the evaluated first load balancing expression, the load balancing action comprising;

determining a value for at least one conditional logic expression for selection of load balancing conditions;

selecting, responsive to at least the determined value for the at least one conditional logic expression for selection of load balancing conditions, a plurality of expressions corresponding to load balancing conditions for evaluation, the plurality of expressions being selected from the expressions corresponding to load balancing conditions from the application-defined interface, the order of evaluation of the plurality of expressions being dependent on at least the determined value for the at least one conditional logic expression;

determining that at least one load balancing condition corresponding to the selected one or more of the plurality of expressions is satisfied; and

performing a load balancing action corresponding to the satisfied load balancing condition, the load balancing action comprising;

removing the assignment of a partition front a first partition server;

selecting, by a fixed partitioning system interface, a partition server for assignment of the removed partition from a group of partition servers, the group of partition servers excluding at least one partition server based on the load balancing condition; and

assigning the removed partition to the selected partition server.

2. The method of claim 1, wherein the partition servers are implemented as virtual machines in a distributed computing environment.

3. The method of claim 1, wherein the conditional logic expression comprises an expression that can be evaluated to determine a value.

4. The method of claim 1, wherein the one or more expressions corresponding to the load balancing conditions comprise a procedure, the procedure utilizing two or more metrics as an input and specifying at least one of an optimization target or a constraint.

5. The method of claim 1, wherein the application-defined interface comprises a plurality of dimensions of application-defined metrics, a dimension of application-defined metrics including at least one expression for a partition metric, at least one expression for a server metric, and a condition based on one or more of the partition metric or server metric expressions.

6. The method of claim 1, wherein selecting the plurality of expressions corresponding to load balancing conditions for evaluation is further responsive to at least one value determined from a selected expression of the selected plurality of expressions.

7. A method for performing load balancing in a distributed computing environment, comprising:

receiving a namespace from an application comprising a plurality of key values that span the namespace, the namespace comprising at least one of a range of possible input values for a job or a range of possible identifiers for a job within a computing environment;

assigning, by a fixed partitioning system interface, a plurality of partitions based on the namespace to one or more partition servers, the plurality of partitions corresponding to key ranges that span the namespace, the partition servers implementing one or more application-defined partitioning system interfaces;

receiving one or more metrics from the partition servers based on activity related to assigned partitions;

receiving a plurality of application-defined load balancing conditions, a load balancing condition comprising an expression that can be evaluated based on at least one received metric, the plurality of load balancing conditions including a filter condition, the plurality of load balancing conditions further comprising a received ordering for the conditions, the filter condition comprising a condition that, when satisfied, modifies the received ordering for the conditions;

evaluating a first portion of the plurality of application-defined load balancing conditions according to the received ordering, the filter condition having an initial filter value prior to the evaluating of the plurality of application-defined load balancing conditions, the filter condition changing to a second filter value during the evaluating of the first portion of the plurality of application-defined load balancing condition;

modifying the received ordering of the plurality of application-defined load balancing conditions to a filtered order based on the changing of the filter condition to the second filter value;

evaluating a second portion of the plurality of application-defined load balancing conditions according to the filtered ordering; and

performing, by a fixed partitioning system interface, a load balancing action corresponding to a received load balancing condition, the load balancing action being performed based on the received load balancing condition being satisfied during said evaluation, the load balancing action including a change in a partition assignment for at least one partition server.

8. The method of claim 7, wherein the status of the filter condition is changed to the second filter value due to merging two partitions.

9. A method for performing load balancing in a distributed computing environment, comprising:

receiving a namespace from an application comprising a plurality of key values that span the namespace, the namespace comprising at least one of a range of possible input values for a job or a range of possible identifiers for a job within a computing environment;

receiving an application-defined interface comprising a) expressions corresponding to load balancing conditions based on one or more of the application-defined metrics and one or more conditional logic expressions, and b) a lookup table;

evaluating at least a first load balancing expression;

initiating a load balancing action responsive to the evaluated first load balancing expression, the load balancing action comprising;

determining a value for at least one expression from the received expressions corresponding to load balancing conditions;

selecting at least one additional expression for evaluation, the at least one additional expression being selected based on using the determined value to select the at least one additional expression from the received lookup table;

determining that at least one load balancing condition corresponding to the selected one or more of the plurality of expressions is satisfied; and

performing a load balancing action corresponding to the satisfied load balancing condition, the load balancing action comprising;

removing the assignment of a partition from a first partition server;

selecting, by a fixed partitioning system interface, a partition server for assignment of the removed partition from a group of partition servers, the group of partition servers excluding at least one partition server based on the load balancing condition; and

assigning the removed partition to the selected partition server.

10. The method of claim 9, wherein removing the assignment of a partition from a first partition server comprises:

identifying a first partition from the first partition server for splitting;

splitting the first partition to form a first split partition and a second split partition; and

removing the assignment of the second split partition.