Decoupling partitioning for scalability

• US 10,635,500 B2
• Filed: 12/26/2017
• Issued: 04/28/2020
• 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): Patel, Chirag R
• Application Number:
  US15/854,367
• Publication Number:
  US 20180217872A1
• Time in Patent Office: 854 Days
• 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 operations on a client defined namespace in a distributed computing environment, comprising:

receiving a namespace at a system, from a client application, the namespace comprising a plurality of key values that span the namespace;

receiving one or more application-defined interfaces, at the system, wherein application-defined interfaces are comprised of computations, operations, or functions defined by the client application;

dividing, by one or more fixed system interfaces, the received namespace into a plurality of partitions, wherein fixed interfaces are comprised of computations, operation, or functions integrated into the system;

assigning, by the one or more fixed interfaces, the plurality of partitions to one or more partition servers that implement at least one of the received application-defined interfaces, wherein the fixed interfaces and application-defined interfaces operationally separate distributed computing environment operations for the one or more partition servers, from application-specific operations for the one or more partition servers;

creating, by the one or more fixed interfaces, a storage object for each of the one or more partition servers, the storage object comprising information related to partitions assigned to the one or more partition servers;

receiving a client request to perform a computation, the request including a key value from the namespace;

identifying a partition server corresponding to the key value based on the assigned one or more partitions; and

returning, in response to the received request, an address for the identified partition server.

2. The method of claim 1, wherein assigning one or more partitions to a plurality of partition servers comprises:

constructing a partition table containing assignments of the plurality of partitions to the one or more partition servers; and

sending messages containing partition assignments to the one or more partition servers.

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

4. The method of claim 2, further comprising:

receiving a heartbeat response message from a first partition server comprising partition assignment information for at least one partition assigned to the partition server;

detecting a conflict between the partition assignment information from the heartbeat response message with the partition table; and

assigning the at least one partition to one or more different partition server virtual machines.

5. The method of claim 1, wherein the storage objects for the partition servers are created by a fixed interface.

6. The method of claim 1, wherein the one or more application-defined interfaces cannot access the partition table.

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

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

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

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

receiving a namespace at a system, from a client application comprising a plurality of key values that span the namespace;

accessing one or more application-defined interfaces, at the system, wherein application-defined interfaces are comprised of computations, operations, or functions defined by the client application;

providing a partition table comprising assignments of a plurality of partitions based on the received namespace to one or more partition servers that implement at least one of the received application-defined partitioning system interfaces;

modifying, by one or more fixed interfaces of a master role instance, one or more partition assignments in the partition table, wherein fixed interfaces are comprised of computations, operations, or functions integrated into the system, wherein the fixed interfaces and application-defined interfaces operationally separate distributed computing environment operations for the one or more partition servers, from application-specific operations for the one or more partition servers;

updating, by the one or more fixed interfaces of a partition server, a storage object for at least one partition server, the storage object comprising information related to partitions assigned to the partition server, the update corresponding to one or more of the modified partition assignments;

receiving a client request to perform a computation, the request including a key value from the namespace;

identifying a partition server corresponding to the key value based on the modified one or more partition assignments in the partition table; and

returning, in response to the received request, an address for the identified partition server.

11. The method of claim 10, further comprising:

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

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

13. The method of claim 10, further comprising:

receiving a heartbeat response message from a first partition server comprising partition assignment information for at least one partition assigned to the partition server virtual machine; and

detecting a conflict between the partition assignment information from the heartbeat response message with the partition table, wherein modifying the one or more partition assignments is in response to the detected conflict.

14. The method of claim 10, wherein the one or more application-defined interfaces cannot access the partition table.

15. One or more hardware computer-storage media storing computer-useable instructions that, when executed, perform a method for performing load balancing in a distributed computing environment, comprising:

receiving a namespace at a system, from an application, the namespace comprising a plurality of key values that span the namespace;

assigning, by one or more fixed interfaces, 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 interfaces, wherein fixed interfaces are comprised of computations, operations, or functions integrated into the system;

receiving, by one or more application-defined interfaces, an application-defined load balancing condition and a filter condition, the load balancing condition comprising a condition for performing a load balancing action, the condition being based on an expression including at least one metric received from the partition servers, wherein application-defined interfaces are comprised of computations, operations, or functions defined by the application, wherein the fixed interfaces and application-defined interfaces operationally separate distributed computing environment operations for the one or more partition servers, from application-specific operations for the one or more partition servers;

determining that the load balancing condition and the filter condition are satisfied; and

modifying, by the one or more fixed interfaces, a load balancing action corresponding to the load balancing condition based on the filter condition being satisfied; and

performing, by the one or more fixed interfaces, the modified load balancing action.

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

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

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

selecting, by the fixed 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.

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

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

selecting, by the fixed 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.

19. The method of claim 15, wherein the load balancing action is performed in a stateless manner.

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