Managing partitions in a scalable environment

Patent metadata

Field	Value
Publication number	US-10860384-B2
Application number	US-201213366039-A
Country	US
Kind code	B2
Filing date	Feb 3, 2012
Priority date	Feb 3, 2012
Publication date	Dec 8, 2020
Grant date	Dec 8, 2020

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.

First claim

What is claimed is:

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;
performing one or more computations corresponding to an application using the plurality of partition servers;
receiving, by the dictator master role instance, a message from a first partition server comprising partitions the first partition server reports to be currently serving; and
breaking, by the dictator master role instance, a lease of the first partition server on a corresponding first storage object, the breaking of the lease of the first partition server being at the first partition server responsive to detecting, by the dictator master role instance, that the first partition server is currently serving at least one partition the first partition server should not currently be serving as indicated by a conflict between one or more partitions assigned to the first partition server in a partition table and the partitions in the received message.

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

3. The method of claim 1 wherein the one or more application-defined partitioning system interfaces are each a client-provided function.

4. The method of claim 1 , further comprising in response to the detecting:
rebuilding a proper state of the partition table; and
ensuring all unknown storage objects are deleted before proceeding with partition assignments.

5. The method of claim 2 , further comprising:
sending, by the dictator master role instance, a message assigning one or more partitions to a second 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 dictator master role instance including an epoch number; and
maintaining, by the second 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 second partition server;
updating, by the second partition server, the content of a corresponding storage object to store the assignment identifier, and
sending, by the second 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 second partition server;
receiving, by the second 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 second partition server on a corresponding storage object;
deleting, by the dictator master role instance, the storage object corresponding the second partition server; and
detecting, by the second partition server, the breaking of the lease, the second 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 second partition server;
receiving, by the second 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 second partition server on the corresponding storage object;
deleting, by the dictator master role instance, the storage object corresponding to the second partition server; and
detecting, by the second partition server, the breaking of the lease, the second 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 for a corresponding namespace and holding a dictator lease on a master storage object for the corresponding namespace, the master role instances instantiating a common master module and common fixed-interfaces, while each being of a different master role and having a different application-defined interface, wherein breaking of the dictator lease is based on detecting, that a partition server is currently serving at least one partition that the partition server should not currently be serving as indicated by a conflict between one or more partitions assigned to the partition server in a partition table and the partitions in a received message comprising the partitions the partition server reports to be currently serving;
assigning a machine that provides failover service for the master role instances and comprises a backup used for each master role instance of the master role instances in response to a failure event being detected for the master role instance, the backup including the common master module and the common fixed-interfaces;
in response to detecting a failover event for a master role instance of the master role instances:
incorporating the different application-defined interface of the master role instance, needed by the backup on the assigned machine to take over for the master role instance, into the backup; and
assigning the backup comprising the common fixed interfaces and the incorporated different application-defined interface as the dictator for the namespace corresponding to the failover event.

10. The method of claim 9 , wherein the different application-defined interface of each of the master role instances is a client-provided function.

11. The method of claim 9 , wherein the common master module performs election of the dictator for the corresponding namespace, communication between the dictator and server role instances, and partition management.

12. The method of claim 9 , wherein a first of the master role instances is of a pool server role that handles pool management and pool transactions and a second of the master role instances is of a work item or job server role that handles creation, deletion, and updates of work items and jobs.

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

Assignees

• Wang Ju
• Calder Bradley Gene
• Skjolsvold Arild E
• Microsoft Technology Licensing Llc

Inventors

• Wang Ju
• Calder Bradley Gene
• Skjolsvold Arild E

Classifications

• H04L67/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] · CPC title

• A01C5/04

  Machines for making or covering holes for sowing or planting · CPC title

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F9/52

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title