Distributed state manager bootstrapping

Patent metadata

Field	Value
Publication number	US-9760529-B1
Application number	US-201414489451-A
Country	US
Kind code	B1
Filing date	Sep 17, 2014
Priority date	Sep 17, 2014
Publication date	Sep 12, 2017
Grant date	Sep 12, 2017

Abstract

A particular node of a distributed state manager (DSM) detects a triggering condition for an initiation of a DSM initialization protocol. The particular node transmits a first bootstrap message to a second node of a proposed members list of a first proposed DSM configuration, comprising at least a joined members list and metadata indicative of state transitions for which processing of respective commit requests has been at least initiated at the particular node. In response to a determination that an initialization protocol for a particular DSM configuration indicated in a different bootstrap message received at the particular node has been completed, the particular nodes proposes itself as a coordinator of the particular DSM configuration based at least in part on an analysis of state transition metadata indicated in the different bootstrap message.

First claim

What is claimed is:

1. A system, comprising a plurality of nodes of a distributed state manager (DSM) configured to commit state transitions of one or more applications using a consensus-based protocol;
wherein a first node of the plurality of nodes, instantiated at a first computing device, is configured to:
detect a triggering condition for an initiation of a DSM initialization protocol;
determine a proposed members list comprising at least a selected number of nodes of the plurality of nodes;
generate a first bootstrap message indicating at least (a) a joined members list indicating that the first node has accepted membership in a first proposed DSM configuration, (b) a last-committed transition identifier (LCTI) indicating a state transition that has been committed, and (c) a last-accepted transition identifier (LATI) indicating a requested state transition for which commit processing has at least begun; and
transmit the first bootstrap message to a selected node of the proposed members list for propagation at least to one or more other nodes of the proposed members list, wherein the selected node is instantiated at a different computing device; and
in response to a detection that a size of a joined members list indicated in a different bootstrap message received from a different node of the proposed members list is above a threshold, wherein the different bootstrap message includes an indication of a particular DSM configuration,
propose a selection of the first node as a coordinator node of the particular DSM configuration based at least in part on an analysis of one or more of: (a) an LCTI indicated in the different bootstrap message, or (b) an LATI indicated in the different bootstrap message; and
subsequent to an approval of the first node as the coordinator node, transmit an indication to at least the selected node to begin processing of client-submitted state transition requests.

2. The system as recited in claim 1 , wherein to detect the triggering condition, the first node determines that at least a first subset of nodes of the plurality of nodes have restarted subsequent to a selection of a jury comprising a second subset of nodes of the plurality of nodes, wherein the jury was selected to approve client-requested state transitions.

3. The system as recited in claim 2 , wherein to determine that at least a first subset of nodes of the plurality of nodes have restarted, the first node determines that a current process instantiation indicator of a particular node of the first subset of nodes differs from a previously-stored process instantiation indicator corresponding to the particular node.

4. The system as recited in claim 1 , wherein the selected node is configured to:
in response to (a) receiving the first bootstrap message and (b) determining that the selected node has not yet accepted membership in another DSM configuration,
store, in persistent storage of the selected node, a join-in-progress indicator comprising an identifier of the first proposed DSM configuration;
generate a modified version of the first bootstrap message, wherein a joined members list of the modified version includes an identifier of the selected node;
determine, based at least in part on state transition records stored at the selected node, whether to update one or more of the LCTI or the LATI of the first bootstrap message for inclusion in the modified version; and
transmit the modified version to a third node selected from the plurality of nodes.

5. The system as recited in claim 1 , wherein a size of the proposed members list is based at least in part on a minimum jury size associated with committing state transitions at the DSM.

6. A method, comprising:
performing, by a particular node of a plurality of nodes of a distributed state manager (DSM) responsible for processing state transitions of one or more applications:
detecting a triggering condition for an initiation of a DSM initialization protocol;
identifying a proposed members list comprising at least a selected number of nodes of the plurality of nodes;
transmitting a first bootstrap message to a second node of the proposed members list, wherein the first bootstrap message comprises at least (a) a joined members list indicating that the particular node has accepted membership in a first proposed DSM configuration, (b) state transition metadata indicative of one or more state transitions for which processing of respective commit requests has been at least initiated at the particular node; and
in response to determining that an initialization protocol for a particular DSM configuration indicated in a different bootstrap message received at the particular node has been completed, proposing, based at least in part on an analysis of state transition metadata indicated in the different bootstrap message, a selection of the particular node as a coordinator node of the particular DSM configuration.

7. The method as recited in claim 6 , wherein said detecting the triggering condition comprises determining that at least a first subset of nodes of the plurality of nodes have restarted subsequent to a selection of a jury comprising a second subset of nodes of the plurality of nodes, wherein the jury was selected to approve client-requested state transitions.

8. The method as recited in claim 7 , wherein said determining that at least a first subset of nodes of the plurality of nodes have restarted comprises determining that a current process instantiation indicator of a first node of the first subset of nodes differs from a previously-stored process instantiation indicator corresponding to the first node.

9. The method as recited in claim 7 , further comprising performing, by the particular node:
storing, in persistent storage of the particular node prior to transmitting the first bootstrap message, one or more of: (a) a join-in-progress indicator comprising an identifier of the first proposed DSM configuration (b) a last-committed transition identifier (LCTI) indicating a state transition that has been committed, (c) a last-accepted transition identifier (LATI) indicating a requested state transition for which commit processing has at least begun.

10. The method as recited in claim 9 , wherein said state transition metadata comprises one or more of: the LCTI or the LATI.

11. The method as recited in claim 6 , further comprising performing, by the second node:
in response to (a) receiving the first bootstrap message and (b) determining that the second node has not yet accepted membership in another DSM configuration,
storing, in persistent storage of the second node, a join-in-progress indicator comprising an identifier of the first proposed DSM configuration;
generating a modified version of the first bootstrap message, wherein a joined members list of the modified version includes an identifier of the second node;
determining, based at least in part on state transition records stored at the second node, whether to update one or more elements of state transition metadata of the modified version; and
transmitting the modified version to a third node selected from the plurality of nodes.

12. The method as recited in claim 6 , further comprising performing, by the second node:
in response to receiving a second bootstrap message indicating the first proposed DSM configuration,
determining, based at least in part on state transition records stored at the second node, whether one or more elements of state transition metadata of the second bootstrap message are to be updated; and
transmitting a version of the second bootstrap message to a third node selected from the plurality of nodes.

13.

Assignees

• Amazon Tech Inc

Inventors

• Ho Chi Hai

Classifications

• H04L43/10

  Active monitoring, e.g. heartbeat, ping or trace-route · CPC title

• G06F11/2025

  using centralised failover control functionality · CPC title

• H04L41/0893

  Assignment of logical groups to network elements · CPC title

• H04L41/0813

  characterised by the conditions triggering a change of settings · CPC title

• G06F17/30575

  Physics · mapped topic