Decoupling partitioning for scalability
First Claim
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 Assignments
0 Petitions
Accused Products
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.
39 Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
Specification