Methods, devices and systems for dynamically managing memberships in replicated state machines within a distributed computing environment

• US 9,521,196 B2
• Filed: 10/02/2015
• Issued: 12/13/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Cirata Incorporated
• Original Assignee: WANdisco, Inc.
• Inventors: Aahlad, Yeturu, Parkin, Michael, Akhtar, Naeem
• Primary Examiner(s): JEAN GILLES, JUDE
• Application Number:
  US14/873,631
• Publication Number:
  US 20160105507A1
• Time in Patent Office: 438 Days
• Field of Search: 709201-204, 709/221
• US Class Current: 1/1
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

A computer-implemented method may comprise processing agreements received over a computer network at a first replicated state machine deployed on processes belonging to a first membership in an order defined by a first globally ordered set of agreements associated with the first membership; receiving an agreement to change membership that is configured to cause the first replicated state machine to be deployed on processes belonging to a second membership that is associated with a second globally ordered set of agreements; and processing the agreement to change membership at a point within the first globally ordered set of agreements.

Claims

1. A distributed computing system, comprising, comprising:

a plurality of computing devices configured as state machines coupled to one another by a computer network, states of one of the plurality of state machines being replicated in a plurality of other state machines of the plurality of state machines to create a plurality of replicated state machines;

a plurality of processes associated with the plurality of replicated state machines; and

a first globally ordered set of agreements that is visible to and that maintains a consistency of all replicated state machines, the first globally ordered set of agreements being associated with the plurality of replicated state machines;

wherein, at an arbitrary point in a processing of the first globally ordered set of agreements, at least one of the plurality of processes changes and the plurality of replicated state machines become associated with the at least one changed process; and

wherein at least some of the plurality of processes associated with the plurality of replicated state machines change states while the change to the at least one of the plurality of processes is being made.

2. The distributed computing system of claim 1, wherein the changed at least one of the plurality of processes changes a role.

3. The distributed computing system of claim 2, wherein the role is one of proposer, acceptor and learner.

4. The distributed computing system of claim 2, wherein the changed at least one of the plurality of processes comprises at least some of the plurality of replicated state machines.

5. The distributed computing system of claim 1, wherein the plurality of state machines are configured to become associated with a second globally ordered set of agreements associated with the changed at least one of the plurality of processes.

6. The distributed computing system of claim 1, wherein the plurality of processes belong to a first membership and wherein changing the plurality of processes comprises changing the association of the plurality of replicated state machines to a second membership comprising the changed plurality of processes.

7. The distributed computing system of claim 1, wherein each of the replicated state machines is further configured to receive agreements to be processed at a point within the first globally ordered set of agreements.

8. The distributed computing system of claim 7, wherein each of the replicated state machines is further configured to receive the agreements for processing asynchronously and out of an order defined by the first globally ordered set of agreements.

9. The distributed computing system of claim 7, wherein the plurality of processes associated with the plurality of replicated state machines are changed upon receipt, by at least one of the replicated state machines, of an agreement to change from a current membership to a new membership.

10. The distributed computing system of claim 1, wherein the first globally ordered set of agreements comprises at least one agreement to change processes associated with the plurality of replicated state machines.

11. The distributed computing system of claim 1, wherein the changed plurality of processes associated with the plurality of replicated state machines comprises a learner that is added to the plurality of processes without affecting any existing learners learning from the first globally ordered set of agreements.

12. The distributed computing system of claim 11, wherein an application of the added learner is synchronized after the change to the plurality of processes is complete.

13. A replicated state machine in a distributed computing system, comprising:

a processor;

memory coupled to the processor, the processor being configured to execute sequences of instructions configured to;

process agreements received over a computer network at a first replicated state machine deployed on processes belonging to a first membership in an order defined by a first globally ordered set of agreements associated with the first membership;

receive an agreement to change membership that is configured to cause the first replicated state machine to be deployed on processes belonging to a second membership that is associated with a second globally ordered set of agreements; and

process the agreement to change membership at a point within the first globally ordered set of agreements.

14. The replicated state machine of claim 13, wherein the sequences of instructions are further configured to receive agreements to be processed on processes belonging to the second membership while agreements are processed by processes belonging to the first membership.

15. The replicated state machine of claim 14, wherein the sequences of instructions are further configured to persistently store the received agreements to be processed on processes belonging to the second membership for processing after the agreement to change membership has been processed.

16. The replicated state machine of claim 15, wherein the sequences of instructions are further configured to process the stored agreements to be processed on processes belonging to the second membership at a point within the second globally ordered set of agreements.

17. The replicated state machine of claim 13, wherein the sequences of instructions are further configured to process received agreements at the replicated state machine deployed on processes belonging to the first membership while the agreement to change memberships is being processed.

18. The replicated state machine of claim 13, wherein the sequences of instructions are further configured to one of add processes to and remove processes from the first membership while the received agreements are being processed at the replicated state machine deployed on other ones of the processes belonging to the first membership.

19. The replicated state machine of claim 13, wherein the sequences of instructions are further configured to change a role of a process belonging to the first membership while the received agreements are being processed at the replicated state machine deployed on other ones of the processes belonging to the first membership.

20. The replicated state machine of claim 19, wherein the sequences of instructions are further configured to change the role of the process to one of proposer, acceptor and learner.

21. The replicated state machine of claim 13, wherein the sequences of instructions are further configured to process received agreements at a second replicated state machine deployed on processes belonging to the first membership in the order defined by the first globally ordered set of agreements associated with the first membership, wherein the first and second replicated state machines remain consistent as agreements are received asynchronously and out of order.

22. A replicated state machine in a distributed computing system comprising a plurality of replicated state machines coupled to one another over a computer network, the replicated state machine comprising:

a processor; and

memory coupled to the processor, the processor being configured to execute sequences of instructions configured to;

asynchronously receive out of order agreements from a distributed co-ordination engine;

maintain at least a first membership comprising a first plurality of agreements comprising a first plurality of processes within a global sequence of agreements and a second membership comprising a second plurality of agreements comprising a second plurality of processes within the global sequence of agreements; and

dynamically change membership from the first membership to the second membership.

23. The replicated state machine in a distributed computing system of claim 22, wherein the first and second plurality of agreements are configured to enable processes to be added or removed therefrom.

24. The replicated state machine in a distributed computing system of claim 22, wherein changes are processed deterministically on the replicated state machine and on the plurality of replicated state machines.

25. The replicated state machine in a distributed computing system of claim 22, wherein the dynamic membership change is non-blocking.

26. The replicated state machine in a distributed computing system of claim 22, further comprising a persistent store configured to persistently store the first plurality of agreements for the first membership and persistently store the second plurality of agreements for the second membership.

27. The replicated state machine in a distributed computing system of claim 22, wherein the dynamic membership change from the first membership to the second membership is carried out a selected point within the global sequence of agreements.