Method for managing proposals in a distributed computing system

• US 10,481,956 B2
• Filed: 02/13/2008
• Issued: 11/19/2019
• Est. Priority Date: 01/12/2005
• Status: Active Grant

• Current Assignee: Cirata Incorporated
• Original Assignee: WANdisco, Inc.
• Inventors: Aahlad, Yeturu, Bhargava, Rahul, Campigli, James Milton, Richards, David James, Akhtar, Mohammad Naeem
• Primary Examiner(s): Jasmin, Lynda
• Assistant Examiner(s): Evans, Kimberly L
• Application Number:
  US12/069,986
• Publication Number:
  US 20080140726A1
• Time in Patent Office: 4,297 Days
• Field of Search: 705 11, 709220, 709226, 714 44, 707 8, 707610, 707201
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 17/00 Digital computing or data processing equipment or methods, specially adapted for specific functions information retrieval, database structures or file system structures therefor G06F16/00
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: H03K 19/00 Logic circuits, i.e. having at least two inputs acting on one output circuits for computer systems using fuzzy logic G06N7/02; Inverting circuits
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

In one embodiment of the present invention, a replicated state machine comprises a proposal manager, an agreement manager, a collision/back-off timer and a storage reclaimer. The proposal manager facilitates management of proposals issued by a node of a distributed application for enabling coordinated execution of the proposals by all other nodes of the distributed application. The agreement manager facilitates agreement on the proposals. The collision/back-off timer precludes repeated pre-emptions of rounds in attempting to achieve agreement on the proposals. The storage reclaimer reclaims persistent storage utilized for storing at least one of proposal agreements and the proposals.

Claims

1. A computer-implemented method, comprising:

receiving, at a first replicator comprising a first replicated state machine, a first proposal to update a first replicated repository associated with the first replicated state machine from a first application node of a plurality of peer application nodes coupled to a computer network, the first application node running on a first computing device coupled to the network;

receiving, at a second replicator comprising a second replicated state machine, a second proposal to update a second replicated repository associated with the second replicated state machine from a second application node of the plurality of peer application nodes coupled to the computer network, the second application node running on a second computing device coupled to the network;

propagating the first proposal from the first replicator to the second replicator and propagating the second proposal from the second replicator to the first replicator such that both the first and second replicators coordinate to maintain at least the first and second replicated repositories in sync with each other in a real-time manner;

enabling concurrent agreements to be reached on at least the first and second proposals received from at least the first and the second application nodes, each of the peer application nodes being configured to serve as a proposal proposer or a proposal acceptor at any given point in time, wherein the first and second replicated state machines are configured to enable the first replicated state machine to reach agreement on the first proposal concurrently with the second replicated state machine reaching agreement on the second proposal;

precluding repeated preemptions of rounds in attempting to reach agreement on the proposals;

storing in each of the plurality of peer applications nodes coupled to the computer network, using a persistent storage device, a local copy of an ordered global sequence of proposals that includes the first and second proposals, such that the local copy of the ordered global sequence of proposals stored in the persistent storage devices of all peer application nodes in the computer network is maintained to be identical;

periodically, by each peer application node, reclaiming memory space on the respective persistent storage device by a periodic exchange of messages among the other peer application nodes, the exchanged messages providing an indication of those proposals that are determined by the first and second replicated state machines as being no longer required by any of the peer application nodes and that may be deleted from at least the local copy of the ordered global sequence of proposals.

2. The computer-implemented method of claim 1, wherein precluding repeated preemptions comprises preserving an issuance order of the first and second proposals while concurrent agreement on the first and second proposals is enabled.

3. The computer-implemented method of claim 1, wherein the first and second proposals comprise proposed write steps corresponding to respective information updates of the first and second replicated repositories, respectively, and wherein further comprises:

assigning a local sequence number to each one of the proposed write steps; and

creating the ordered global sequence of proposals as a globally unique interleaving of the proposed write steps such that the first and second application nodes executing the proposed write steps execute the proposed write steps in a common sequence.

4. The computer-implemented method of claim 1, further comprising, for the first proposal:

assigning a first unique local sequence number to a first local sequencer entry that resides within a first local sequencer of the first replicated state machine;

sequentially ordering the first local sequencer entry with respect to the assigned first local sequence number; and

after agreement on the first proposal is successfully performed, creating a first entry corresponding to the first proposal within a first global sequencer of the first replicated state machines in response to determining a position in which the first entry is positioned within the global sequencer; and

for the second proposal,

assigning a second unique local sequence number to a second local sequencer entry that resides within a second local sequencer of the second replicated state machine;

sequentially ordering the second local sequencer entry with respect to the assigned second local sequence number; and

after agreement on the second proposal is successfully performed, creating a second entry corresponding to the second proposal within a second global sequencer of the second replicated state machines in response to determining a position in which the second entry is positioned within the global sequencer.

5. The computer-implemented method of claim 4 wherein the reclaiming memory space on the persistent storage device comprises deleting a record for the first or second proposal from the persistent storage device after a position thereof in the first or second global sequencer is determined.

6. The computer-implemented method of claim 4 wherein precluding repeated preemptions comprises at least one of:

after expiry of a computed preemption-delay duration after starting a current one of the rounds for a first proposer, initiating a next one of the round for the first proposer; and

after expiry of a computed round-in-progress delay duration after starting a current one of the rounds for the first proposer, starting a next one of the rounds for a second proposer.

7. The computer-implemented method of claim 1, wherein the first replicated state machine creates a first local sequence of proposals that is ordered according to the sequence in which proposals are received at the first replicated state machine and wherein the second replicated state machine creates a second local sequence of proposals that is ordered according to the sequence in which proposals are received at the second replicated state machine.

8. The computer-implemented method of claim 7, wherein each of the first and second proposals in each of the first and second local sequences occurs exactly once in the ordered global sequence.

9. The computer-implemented method of claim 8, wherein a relative ordering of the first and second proposals in any one of the first and second local sequences of proposals is preserved in the ordered global sequence.

10. The computer-implemented method of claim 7, further comprising the first replicated state machine assigning a first local sequence number to the received first proposal and the second replicated state machine assigning a second local sequence number to the received second proposal.

11. The computer-implemented method of claim 10, further comprising the first application node maintaining a first local sequence that includes contents of each of the proposals generated by the first application node and further comprising the second application node maintaining a second local sequence that includes contents of each of the proposals generated by the second application node.

12. The computer-implemented method of claim 11, wherein each of the first and second local sequences comprises:

(a) a proposer identifier;

(b) the local sequence number;

(c) the global sequence number;

(d) the agreement number; and

(e) the content of the proposal.

13. The computer-implemented method of claim 7, further comprising each of the first and second replicated state machines determining an agreement number for each proposal it receives, the agreement number determining a position of a given proposal received by the first and second replicated state machines in the ordered global sequence.

14. The computer-implemented method of claim 13 further comprising the first replicated state machine saving a record of the first proposal and the second replicated state machine saving a record of the second proposal, in the persistent storage device.

15. The computer-implemented method of claim 14, wherein the first proposal is forwarded by a first thread, and wherein the method further comprises the first replicated state machine assuming control of the first thread from the first application node, and wherein, after the first replicated state machine saves the record of the first proposal, the first replicated state machine returning control of the first thread to the first application node.

16. The computer-implemented method of claim 15 wherein, after the first thread is returned to the first application node, the method further comprises the first replicated state machine initiating an agreement protocol through which the first proposal is assigned a first proposal number, and through which agreement on the first proposal is sought from at least the second replicated state machine.

17. The computer-implemented method of claim 16 further comprising, if agreement on the first proposal is obtained from at least the second replicated state machine, the first replicated state machine concluding processing of the first proposal.

18. The computer-implemented method of claim 16 wherein, if agreement on the first proposal is not obtained from at least the second replicated state machine, the first replicated state machine repeats the steps of (a) assigning a new proposal number to the first proposal and (b) seeking agreement on the first proposal from at least the second replicated state machine until agreement on the first proposal is obtained.

19. The computer-implemented method of claim 18 wherein, if agreement on the first proposal is obtained from at least the second replicated state machine, each of the first and second application nodes enqueues the first proposal in the ordered global sequence.

20. The computer-implemented method of claim 19, further comprising the first and second application nodes subsequently dequeuing and executing the agreed-upon proposals contained within the ordered global sequence in an order specified by the ordered global sequence.

21. The computer-implemented method of claim 16, wherein each of the first and second proposals comprises:

(a) a proposer identifier which identifies the application node which generated the proposal;

(b) the local sequence number assigned to the proposal by the replicated state machine;

(c) the global sequence number assigned to the proposal;

(d) an agreement number; and

(e) the proposal contents.

22. The computer-implemented method of claim 13, wherein the ordered global sequence comprises the global sequence number for a series of proposals and a local sequence handle.

23. The computer-implemented method of claim 22, wherein the local sequence handle comprises a pointer to the respective local sequence.

24. The computer-implemented method of claim 22, wherein the local sequence handle comprises a key to a table of local sequences.

25. The computer-implemented method of claim 1, wherein the first proposal comprises at least one write operation to the first replicated repository associated with the first replicated state machine and wherein the second proposal comprises at least one write operation to the second replicated repository associated with the second replicated state machine.

26. The computer-implemented method of claim 25, further comprising maintaining data in the first and second replicated repositories to be identical.

27. A multi-site computing system, comprising:

a plurality of distributed computing systems interconnected via a computer network, each of the distributed computing systems including a peer respective replicated state machine that includes a persistent storage device, a replicated repository and a respective application node connected to the respective peer replicated state machine;

wherein each peer replicated state machine of the distributed computing systems is configured to;

serve as a proposal proposer or a proposal acceptor at any given point in time;

manage proposals to update the replicated repository and agreements on the proposals originating from the application node of others of the distributed computing systems, the proposals being propagated to and stored in the persistent storage device of each peer replicated state machine as a local copy of an ordered global sequence of proposals, such that the local copy of the ordered global sequence of proposals stored in the persistent storage devices of all peer application nodes in the computer network is maintained to be identical;

enable concurrent agreement to be reached on the proposals such that an agreement on a first proposal received from a first application node of the distributed computing systems may be made concurrently with an agreement on a second proposal received from a second application node of the distributed computing systems;

preclude repeated preemptions of rounds in attempting to achieve agreement on the proposals;

coordinate execution of the proposals of the local copy of the ordered global sequence of proposals stored in each of the plurality of peer applications nodes, such that the replicated repositories are updated in sync with each other in a real-time manner; and

at periodic intervals, reclaim persistent storage in the persistent storage device of each peer replicated state machine, utilized for storing at least one of proposal agreements and proposals by a periodic exchange of messages among the distributed computing systems that provides an indication of those proposals that are determined by the peer respective replicated state machines as being no longer required by any of the distributed computing systems and that may be deleted from at least the local copy of the ordered global sequence of proposals stored in the persistent storage devices of all peer application nodes in the computer network.

28. The multi-site computing system of claim 27 wherein:

the first and second proposals comprise proposed write steps corresponding to a respective information update; and

wherein the respective replicated state machine connected to the respective distributed application node that issued the proposed write steps is configured to assign a local sequence number to each one of the proposed write steps and to create a globally unique ordering of the proposed write steps such that the distributed application nodes of the other ones of the distributed application systems executing the proposed write steps execute the proposed write steps in a common sequence.

29. The multi-site computing system of claim 27 wherein:

each one of the replicated state machines comprises a local sequencer including a plurality of entries each associated with a respective one of the proposals and a global sequencer including a plurality of entries each referencing a respective one of the entries of the local sequencer;

each one of the entries of the local sequencer has a unique local sequence number assigned thereto;

each one of the entries of the local sequencer is sequentially arranged with respect to the assigned local sequence number; and

after agreement on one of the proposals is reached, an entry corresponding to the one proposal upon which agreement is reached is created in the global sequencer in response to determining a position in which the entry is positioned within the global sequencer.

30. The multi-site computing system of claim 29 wherein the replicated state machine reclaims the respective persistent storage by deleting a record for the one proposal from the persistent storage device after the position of the entry in the global sequencer is determined.

31. The multi-site computing system of claim 29 wherein the replicated state machine is further configured to preclude repeated preemptions by performing at least one of waiting for a computed preemption-delay duration to pass after starting a current one of the rounds for a first proposer before initiating a next one of the round for the first proposer and waiting for a computed round-in-progress delay duration to pass after starting a current one of the rounds for the first proposer before starting a next one of the rounds for a second proposer.

32. The multi-site computing system of claim 27 wherein the replicated state machine is further configured to preclude repeated preemptions by performing at least one of waiting for a computed preemption-delay duration to pass after starting a current one of the rounds for a first proposer before initiation a next one of the round for the first proposer and waiting for a computed round-in-progress delay duration to pass after starting a current one of the rounds for the first proposer before starting a next one of the rounds for a second proposer.