Decoupling partitioning for scalability

• US 9,852,010 B2
• Filed: 02/03/2012
• Issued: 12/26/2017
• Est. Priority Date: 02/03/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Skjolsvold, Arild E., Calder, Bradley Gene, Wang, Ju
• Primary Examiner(s): Wasel, Mohamed
• Assistant Examiner(s): WU, TSUNG YIN
• Application Number:
  US13/366,018
• Publication Number:
  US 20130204990A1
• Time in Patent Office: 2,153 Days
• Field of Search: None
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• 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 computations (e.g., jobs) in a scalable environment. The general framework decouples partitioning of a computation from the other aspects of the computation. As a result, the effort required to define an application-defined job is reduced or minimized, as the user is not required to provide a partitioning algorithm. A user can optionally take advantage of a partitioning framework by providing application-defined interfaces to perform the desired job. Optionally, a user can provide additional information to allow for modification of how partitions are assigned.

Claims

1. A method for performing partitioning on a client defined namespace in a distributed computing environment, comprising:

dividing, by a fixed partitioning system interface, a namespace into a plurality of partitions;

assigning, by the fixed partitioning system interface, the plurality of partitions to partition servers;

constructing a partition map containing assignments of the plurality of partitions to the partition servers;

receiving, from a user, an application-defined interface for collecting load balancing metrics on the partition servers, the application-defined interface defining load balancing information and adding the defined load balancing information to information included by partition servers in responses by a fixed interface, wherein the responses are automatically sent as part of the fixed interface in response to corresponding heartbeat messages of the fixed interface;

receiving a heartbeat response message of the responses from a first partition server, the heartbeat response message comprising partition assignment information that identifies at least one partition as being assigned to the first partition server and indicating the first partition server is attempting to serve the at least one partition, the heartbeat response message further including the load balancing information based on the adding by the application-defined interface;

determining a load balancing action based on the load balancing metrics using the load balancing information; and

performing the determined load balancing action on the plurality of partitions.

2. The method of claim 1, further comprising sending messages containing partition assignments to one or more of the partition servers to assign partitions to the one or more partition servers.

3. The method of claim 2, wherein the messages are heartbeat messages from a fixed partitioning system interface of a master role instance to one or more of the partition servers.

4. The method of claim 1, further comprising creating storage objects for the partition servers by a fixed partitioning system interface.

5. The method of claim 1, wherein a plurality of key values are provided by a client application to create the namespace.

6. The method of claim 1, wherein a subset of the plurality of partitions are assigned to at least one partition server, key value ranges for the subset not being contiguous in the namespace.

7. The method of claim 1, wherein key values of the namespace have a defined order when the namespace is serialized.

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

9. One or more removable or non-removable computer-storage media devices storing computer-useable instructions that, when executed, perform a method for performing partitioning on a client defined namespace in a distributed computing environment, comprising:

providing a partition map comprising assignments of a plurality of partitions to partition servers based on a namespace;

receiving, from a user, an application-defined interface for collecting load balancing metrics on the partition servers, the application-defined interface defining load balancing information and adding the defined load balancing information to information included by partition servers in responses by a fixed interface, wherein the responses are automatically sent as part of the fixed interface in response to corresponding heartbeat messages of the fixed interface;

receiving a heartbeat response message of the responses from a first partition server, the heartbeat response message comprising partition assignment information that identifies at least one partition as being assigned to the first partition server and indicating the first partition server is attempting to serve the at least one partition, the heartbeat response message further including the load balancing information based on the adding by the application-defined interface;

determining a load balancing action based on the load balancing metrics using the load balancing information; and

performing the determined load balancing action on the plurality of partitions.

10. The method of claim 9, further comprising:

sending a message containing modified partition assignments to at least one partition server.

11. The method of claim 10, wherein the message is a heartbeat message from a fixed partitioning system interface of a master role instance in the partitioning system to the at least one partition server.

12. The method of claim 9, wherein a plurality of key values are provided by a client application to create the namespace.

13. 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;

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

receiving, from a user, load balancing formulas that define respective load balancing metrics identified by the user for load balancing, each load balancing formula comprising at least one variable defined by the user using an expected format;

receiving, from the user, an application-defined interface for collecting at least one of the load balancing metrics on the partition servers, the application-defined interface defining load balancing information comprising the at least one of the load balancing metrics and adding the defined load balancing information to information included by partition servers in responses by a fixed interface, wherein the responses are automatically sent as part of the fixed interface in response to corresponding heartbeat messages of the fixed interface;

receiving, from the user, an application-defined load balancing condition comprising a condition for performing a load balancing action, the condition comprising an expression including one or more of the at least one of the load balancing metrics, wherein the at least one expression is provided by a user;

receiving, from the user, a filter condition comprising a condition for preventing a partition server from receiving a new partition assignment based on at least one of the at least one of the load balancing metrics;

determining that the load balancing condition and the filter condition are satisfied using the load balancing information from at least one of the responses;

modifying, by a fixed partitioning system interface, a load balancing action corresponding to the load balancing condition based on the filter condition being satisfied; and

performing, by a fixed partitioning system interface, the modified load balancing action,

wherein at least one partition server is assigned a second plurality of partitions, the key value ranges for the second plurality of partitions not being contiguous in the namespace.

14. The method of claim 13, wherein the filter condition is based on a partition load metric, a server load metric, or a combination thereof.

15. The method of claim 13, wherein the modified load balancing action comprises:

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 filter condition; and

assigning the removed partition to the selected partition server.

16. The method of claim 13, wherein the modified load balancing action comprises:

determining that a received condition trigger is satisfied for a first partition server;

selecting, by a fixed partitioning system interface, a partition for removal from the first partition server from a group of partitions assigned to the first partition server, the group of partitions excluding at least one partition based on the filter condition;

removing the assignment of the selected partition from the first partition server; and

assigning the removed partition to a second partition server.

17. The method of claim 13, wherein the load balancing information comprises load statistics collected by at least one of the partition servers.

18. The method of claim 13, wherein the assignments of partitions to partition servers are stored by a fixed partitioning system interface in a partition table, and wherein application-defined partitioning system interfaces cannot access the partition table.

19. The method of claim 13, wherein a first of the load balancing formulas is specific to a partition, and a second of the load balancing formulas corresponds to a value that is for all partitions assigned to a partition server.