US 9,852,010 B2 · Decoupling partitioning for scalability

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.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims19

Dependent claims

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.

5 more elements

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.

3 more elements

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.

8 more elements

Dependencies are inferred from the claim text.

Description15,885 words

Summary323 words

#This application is related in subject matter to the following concurrently filed U.S. patent applications: U.S. patent application Ser. No. 13/366,039, entitled “MANAGING PARTITIONS IN A SCALABLE ENVIRONMENT,” filed Feb. 3, 2012, and U.S. patent application Ser. No. 13/366,052, entitled “DYNAMIC LOAD BALANCING IN A SCALABLE ENVIRONMENT,” filed Feb. 3, 2012, the entireties of the aforementioned applications are incorporated by reference herein.

#Cloud computing environments provide a potential platform for allowing users to have access to large amounts of computing resources without having to invest in corresponding infrastructure. Instead, the computing environment can be provided as a service by a cloud computing provider. This can allow a user to tune the requested computing resources to match the size and importance of a computing job. However, taking full advantage of the additional computing resources available as a service may require dividing computing tasks into smaller portions, so that multiple physical or virtual processors can be used to perform a task.

#In various embodiments, 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. Instead, a user may take advantage of the partitioning framework by providing application-defined interfaces to supplement the features to perform the desired job. Optionally, a user can provide additional information to allow for modification of how partitions are assigned.

Brief description of the drawings8 figures

#The invention is described in detail below with reference to the attached drawing figures, wherein:

#FIGS. 1 to 3 schematically show various aspects of an example of a distributed computing environment, in accordance with aspects of the present invention;

#FIG. 4 schematically shows the interaction between various interfaces for performing a job in a generic partitioning environment, in accordance with aspects of the present invention;

Detailed description15,372 words

#Overview

#Due to increases in the speed of data transmission over networks and improvements in other network features, it is increasingly possible to perform large scale computing tasks in an environment where computing resources are distributed over a large network. A user in a first location can submit a job or computing task to a computing service and have the task performed on a group of computers that the user has no direct knowledge of. The computing resources for performing the user's task may be distributed over multiple locations. A first group of computing resources located in one or more locations can store the data and other information for performing the user's computing task, while a second group of computing resources, in the same locations or possibly in a different set of one or more locations, can be used to perform the computing task.

#Access to a variety of distributed computing resources allows a user to perform job tasks without concern for where the computing resources are located. The distributed resources also provide an opportunity for a user to scale up (or scale down) the amount of resources used in order to meet goals for a computing task, such as completing the computing task by a specified time. However, using distributed computing resources poses a number of challenges for a user. Conventionally, a user or application designer would need to divert resources away from designing an application or job in order to determine how to take advantage of a specific distributed computing environment.

Facts

Application

13/366,018Filed 3 Feb 2012

Published

US 2013/0204990 A18 Aug 2013

Granted

26 Dec 2017

Term ends

3 Oct 2032

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 243 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification6 codes

G06F 9/5077
Partitioning or combining of resources: logical partitioning of resources; Management or configuration of virtualized resources
G06F 3/0644
Organizing or formatting or addressing of data: management of space entities, e.g. partitions, extents, pools
G06F 9/45558
Hypervisors; Virtual machine monitors: hypervisor-specific management and integration aspects
G06F 9/5083
Allocation of resources, e.g. of the central processing unit [CPU]: techniques for rebalancing the load in a distributed system

Timeline

3 Feb 2012Application filedUS 13/366,018
5 Apr 2012Assigned to Microsoft Corporationassignment of assignor's interest
8 Aug 2013PublishedUS 2013/0204990 A1
9 Dec 2014Assigned to Microsoft Technology Licensing, LLCassignment of assignor's interest
26 Dec 2017GrantedUS 9,852,010 B2
12 Oct 2026TodayWithin its term
3 Oct 2032Term endsEstimated, includes 243 days of adjustment

Decoupling partitioning for scalability

Life of this patent

Decoupling partitioning for scalability

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims19

Description15,885 words

Drawings

Classification6 codes

Life of this patent

Description15,885 words