MANAGING PARTITIONS IN A SCALABLE ENVIRONMENT

• US 20130204917A1
• Filed: 02/03/2012
• Published: 08/08/2013
• Est. Priority Date: 02/03/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: WANG, JU, CALDER, BRADLEY GENE, SKJOLSVOLD, ARILD E.
• Granted Patent: US 10,860,384 B2
• Time in Patent Office: Days
• US Class Current: 709/201
• CPC Class Codes: A01C 5/04 Machines for making or covering holes for sowing or planting
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Systems and methods are provided that enable a general framework for partitioning application-defined jobs 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 job is reduced or minimized, as the user is not required to provide a partitioning algorithm. The general framework also facilitates management of masters and servers performing computations within the distributed environment.

Claims

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

receiving one or more application-defined partitioning system interfaces;

creating a plurality of master role instances including the one or more application-defined partitioning system interfaces, the master role instances corresponding to a master storage object;

assigning a lease for the master storage object, each master role instance competing for the lease, the master role instance that is assigned the lease being the dictator master role instance;

assigning, by the dictator master role instance, a group of partitions to a plurality of partition servers; and

performing one or more computations corresponding to an application using the plurality of partition servers.

2. The method of claim 1, further comprising sending, by the dictator master role instance, a heartbeat message to the plurality of partition servers.

3. The method of claim 2, wherein one or more metrics are received from the partition servers in responses to heartbeat messages.

4. The method of claim 3, wherein at least one of the one or more metrics is an application-defined metric.

5. The method of claim 2, further comprising:

sending, by the dictator master role instance, a message assigning one or more partitions to a partition server from a plurality of partition servers while the dictator master role instance maintains the lease for the master storage object, the message from the dicatator master role instance including an epoch number; and

maintaining, by the partition server from the plurality of partition servers, the partition assignment received from the dictator master role instance.

6. The method of claim 5, further comprising,

associating, by the dictator master role instance, an assignment identifier with the assignment of the one or more partitions, the dictator master role instance sending the assignment identifier along with the message to the partition server;

updating, by the partition server, the content of a corresponding storage object to store the assignment identifier, and

sending, by the partition server, an acknowledgement message to the dictator master role instance.

7. The method of claim 5, further comprising:

associating, by the dictator master role instance, an assignment identifier with the assignment of the one or more partitions, the dictator master role instance sending the assignment identifier along with the message to the partition server;

receiving, by the partition server, the message from the dictator master role instance without sending an acknowledgement message to the dictator master;

breaking, by the dictator master role instance, a lease of the partition server on a corresponding storage object;

deleting, by the dictator master role instance, the storage object corresponding the partition server; and

detecting, by the partition server, the breaking of the lease, the partition server terminating in response to the detection of breaking the lease.

8. The method of claim 5, further comprising:

associating, by the dictator master role instance, an assignment identifier with the assignment of the one or more partitions, the dictator master role instance sending the assignment identifier along with the message to the partition server;

receiving, by the partition server, the message from the dictator master role instance without updating a content of a corresponding storage object;

breaking, by the dictator master role instance, a lease of the partition server on the corresponding storage object;

deleting, by the dictator master role instance, the storage object corresponding the partition server; and

detecting, by the partition server, the breaking of the lease, the partition server terminating in response to the detection of breaking the lease.

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

executing a computation comprising at least two namespaces and at least two master role instances, each master role instance corresponding to a different namespace, each master role instance being the dictator and holding a dictator lease on a master storage object for the corresponding namespace;

assigning at least one machine that provides failover service for a plurality of the dictator master role instances;

detecting a failover event for one of the dictator master role instances; and

creating, on the assigned machine, an additional instance of the master role corresponding to the detected failover event, the additional being assigned as the dictator for the namespace corresponding to the failover event.

10. The method of claim 9, wherein detecting a failover event comprises detecting a scheduled update for a dictator master role instance.

12. The method of claim 9, wherein at least one master role instance comprises one or more application-defined interfaces.

13. The method of claim 9, further comprising assigning, after detecting the failover event, an additional machine that provides failover service for the remaining dictator master role instances of the at least two master role instances and the additional dictator master role instance.

21. The method of claim 9, wherein detecting a failover event comprises a dictator master role instance losing the lease on the master storage object for the corresponding namespace.

11. (canceled)

14. A system for performing computing tasks in a distributed computing environment, the system comprising:

a plurality of processors executing computer-useable instructions that, when executed, provide a system comprising;

a plurality of partition servers, the partition servers having at least one partitioning system interface for managing the storage objects associated with partition servers and one or more application-defined partitioning system interfaces, a partition server having an associated storage object for storing information regarding assigned partitions;

a partition table containing partitions based on an application-defined namespace, the partitions corresponding to key ranges from the application-defined namespace that span the namespace, the partition table being accessible by a partitioning system;

a first master role instance including fixed partitioning system interfaces for managing the assignment of partitions to partition server virtual machines and maintaining the partition table assignments of partitions to partition server virtual machines; and

a client component with at least one fixed partitioning system interface for receiving client requests containing a key value from the namespace and returning addresses of a partition server corresponding to the key value.

15. The system of claim 14, wherein the system comprises a plurality of master role instances as part of the partitioning system, the first master role instance being an active master role instance.

16. The system of claim 15, further comprising a master selection component for selecting an active master role instance from a plurality of master role instances.

17. The system of claim 14, further comprising a fixed partitioning system interface for managing messages between the first master role instance and the plurality of partition server virtual machines.

18. The system of claim 14, wherein the master role instance and the partition servers comprise virtual machines in a distributed computing environment.

19. The system of claim 14, further comprising at least one application-defined interface for the master role instance.

20. The system of claim 14, further comprising a lease interface for assigning leases to the partition table and a master storage object to the active master role instance.