Stable leader selection for distributed services

Patent metadata

Field	Value
Publication number	US-10367676-B1
Application number	US-201514868274-A
Country	US
Kind code	B1
Filing date	Sep 28, 2015
Priority date	Sep 28, 2015
Publication date	Jul 30, 2019
Grant date	Jul 30, 2019

Abstract

A first role manager of a distributed service determines that a leadership assignment decision is to be made with respect to a particular node of the service. The first role manager identifies a particular role indicator value from a first subset of a set of role indicator values according to a value selection order of a role assignment policy of the service. The first role manager is not permitted to assign values from a different subset of the first set of role indicator values. The particular role indicator value is transmitted to the particular node, enabling the particular node to fulfill at least a first category of service requirements corresponding to the role of leader node.

First claim

What is claimed is:

1. A system, comprising:
a plurality of nodes of a distributed service, wherein individual ones of the plurality of nodes are implemented at respective computing devices; and
a distributed role manager implemented at a plurality of computing devices;
wherein the distributed role manager is configured to:
receive a leadership assignment request from a particular node of the plurality of nodes;
determine that designation of the particular node as a leader node of the distributed service is permitted by a role assignment policy of the distributed service, wherein the leader node is responsible for fulfilling a first category of service requirements of the distributed service;
select, from a first subset of a first set of dynamically-assignable role indicator values, in accordance with a role indicator value selection order of the role assignment policy, a particular role indicator value to be assigned to the particular node, wherein the distributed role manager is not authorized to assign role indicator values in a second subset of the first set, wherein the role indicator values in the second subset are different than the role indicator values in the first subset, and wherein a backup role manager of the distributed service is authorized to assign a second role indicator value from the second subset to a node of the distributed service in the event of a failure; and
transmit the particular role indicator value to the particular node; and

wherein the particular node of the distributed service is configured to:
after receiving the particular role indicator value from the distributed state manager, perform an operation to fulfill a service requirement of the first category.

2. The system as recited in claim 1 , wherein the first set of dynamically-assignable role indicator values comprises integers within a range, and wherein the second subset comprises those integers of the range which are not part of the first subset.

3. The system as recited in claim 1 , wherein, in accordance with the role indicator value selection order, the particular role indicator value selected for the particular node is higher than the highest role indicator value which was previously assigned by the default role manager.

4. The system as recited in claim 1 , wherein said operation to fulfill the requirement of the first category comprises:
preparing a first work request, wherein the first work request includes (a) an indication of a first task to be performed and (b) an indication that the particular node has been assigned the particular role indicator value;
transmitting the work request for implementation to a different node of the plurality of nodes.

5. The system as recited in claim 4 , wherein the different node is configured to:
prior to an initiation of the first task, verify, based at least in part on the particular role indicator value, that the different node has not received an indication that a node other than the particular node has been designated as the leader node.

6. A method, comprising:
receiving, at a default role manager implemented at one or more computing devices associated with a distributed service, a leadership assignment request from a particular node of a plurality of nodes of the distributed service, wherein a leader node of the plurality of nodes is responsible for fulfilling a first category of service requirements of the distributed service;
selecting, by the default role manager from a first subset of a first set of dynamically-assignable role indicator values, in accordance with a role indicator value selection order of a role assignment policy of the distributed service, a particular role indicator value to be assigned to the particular node, wherein the default role manager is not authorized to assign role indicator values in a second subset of the first set, wherein the role indicator values in the second subset are different than the role indicator values in the first subset, and wherein another role manager implemented at one or more computing devices associated with the distributed service is authorized to assign a second role indicator value from the second subset to a node of the distributed service; and
transmitting, by the default role manager, the particular role indicator value to the particular node; and
after receiving the particular role indicator value from the distributed state manager, performing, by the particular node, an operation to fulfill a service requirement of the first category.

7. The method as recited in claim 6 wherein the other role manager is a backup role manager, and further comprising:
determining, by the backup role manager, that (a) a failure associated with the default role manager has occurred, and (b) a node to which leadership was assigned by the default role manager is unable to fulfill at least one service requirement of the first category;
selecting, by the backup role manager, the second role indicator value from the second subset as a leadership indicator value; and
transmitting the new role indicator value to a second node of the plurality of nodes.

8. The method as recited in claim 6 , wherein a size of the first subset differs from a size of the second subset.

9. The method as recited in claim 6 , wherein, in accordance with the role indicator value selection order, the particular value is higher than the highest role indicator value which was previously assigned by the default role manager.

10. The method as recited in claim 6 , wherein according to a leadership determination criterion of the role assignment policy, the node assigned the highest role indicator value among role indicator values of the plurality of nodes is the leader node.

11. The method as recited in claim 6 , further comprising, performing by the default role manager after assigning the particular role indicator value to the particular node:
initiating a notification to a different node of the plurality of nodes, indicating that the particular node has been designated as the leader node.

12. The method as recited in claim 6 , wherein said operation to fulfill the requirement of the first category comprises:
preparing a first work request, wherein the first work request includes (a) an indication of a first task to be performed and (b) an indication that the particular node has been assigned the particular role indicator value;
transmitting the work request for implementation to a different node of the plurality of nodes.

13. The method as recited in claim 12 , further comprising:
receiving, by the different node, a second work request from a second node, wherein the second work request includes (a) an indication of a second task and (b) an indication of a second role indicator value assigned to the second node;
determining, by the different node, not to fulfill the second work request based at least in part on comparing the second role indicator value and the particular role indicator value.

14. The method as recited in claim 6 , wherein the default role manager comprises a plurality of voting subcomponents, further comprising:
implementing, by the plurality of voting subcomponents, a quorum-based protocol to determine that the particular node is to be assigned the particular role indicator value.

15. The method as recited in claim 6 , further comprising:
determining, by the particular node, to transmit the leadership assignment request to the default role manager, based at least in part on a time interval which has elapsed since the leader role was previously assigned by the default role manager.

16. The method as recit

Assignees

• Amazon Tech Inc

Inventors

• Vermeulen Allan Henry
• Tracy Leonard Thomas
• Certain Tate Andrew

Classifications

• H04L41/0668

  by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure · CPC title

• H04L41/50

  Network service management, e.g. ensuring proper service fulfilment according to agreements · CPC title

• H04L41/0213 Primary

  Standardised network management protocols, e.g. simple network management protocol [SNMP] · CPC title

• H04L41/30 Primary

  Decision processes by autonomous network management units using voting and bidding · CPC title