Distributed computing systems and system compnents thereof

• US 20060155729A1
• Filed: 01/11/2006
• Published: 07/13/2006
• Est. Priority Date: 01/12/2005
• Status: Active Grant

• Current Assignee: Cirata Incorporated
• Original Assignee: WANdisco, Inc.
• Inventors: Aahlad, Yeturu, Bhargava, Rahul
• Granted Patent: US 8,364,633 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 replicated state machine, comprising:

a proposal manager that facilitates management of proposals issued by a node of a distributed application for enabling coordinated execution of said proposals by all other nodes of the distributed application;

an agreement manager that facilitates agreement on said proposals;

a collision/back-off timer that precludes repeated preemptions of rounds in attempting to achieve agreement on said proposals; and

a storage reclaimer that reclaims persistent storage utilized for storing at least one of proposal agreements and said proposals.

2. The replicated state machine of claim 1 wherein at least a portion of said proposals include proposed steps corresponding to implementation of an information update initiated by the node of the distributed application.

3. The replicated state machine of claim 1 wherein an issuance order of said proposals is preserved while concurrent agreement on said proposals is facilitated.

4. The replicated state machine of claim 1 wherein:

a portion of said proposals are proposed write steps corresponding to a respective information update; and

the proposal manager assigns a local sequence number to each one of said proposed write steps and creates a globally unique interleaving of said proposed write steps such that all nodes of the distributed application executing said proposed write steps execute said proposed write steps in a common sequence.

5. The replicated state machine of claim 1, further comprising:

a local sequencer including a plurality of entries each associated with a respective one of said proposals; and

a global sequencer including a plurality of entries each referencing a respective one of said entries of the local sequencer;

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

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

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

6. The replicated state machine of claim 5 wherein the storage reclaimer reclaims persistent storage by deleting a record for said one proposal from persistent proposal storage after the position of the entry in the global sequencer is determined.

7. The replicated state machine of claim 5 wherein the collision/back-off timer precludes repeated preemptions by performing at least one of waiting for a computed preemption-delay duration to pass after starting a current one of said rounds for a first proposer before initiating a next one of said round for the first proposer and waiting for a computed round-in-progress delay duration to pass after starting a current one of said rounds for the first proposer before starting a next one of said rounds for a second proposer.

8. The replicated state machine of claim 1 wherein the collision/back-off timer precludes repeated preemptions by performing at least one of waiting for a computed preemption-delay duration to pass after starting a current one of said rounds for a first proposer before initiating a next one of said round for the first proposer and waiting for a computed round-in-progress delay duration to pass after starting a current one of said rounds for the first proposer before starting a next one of said rounds for a second proposer.

9. A multi-site computing system architecture, comprising:

a network system; and

a plurality of distributed computing systems interconnected via the network system;

wherein each one of said distributed computing systems includes a respective replicated state machine and a respective local application node connected to the respective replicated state machine;

wherein the respective replicated state machine of each one of said distributed computing systems;

facilitates management of proposals for enabling coordinated execution of said proposals by the distributed application node of all other ones of said distributed computing systems;

facilitates agreement on said proposals;

precludes repeated preemptions of rounds in attempting to achieve agreement on said proposals; and

reclaims persistent storage utilized for storing at least one of proposal agreements and said proposals.

10. The multi-site computing system architecture of claim 9 wherein:

a portion of said proposals are proposed write steps corresponding to a respective information update; and

the respective replicated state machine connected to the respective distributed application node that issued said proposed write steps assigns a local sequence number to each one of said proposed write steps and creates a globally unique interleaving of said proposed write steps such that the distributed application nodes of said other ones of said distributed application systems executing said proposed write steps execute said proposed write steps in a common sequence.

11. The multi-site computing system architecture of claim 9 wherein:

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

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

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

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

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

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

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

15. A method, comprising:

facilitating agreement on proposals received from a local application node;

precluding repeated preemptions of rounds in attempting to achieve agreement on said proposals; and

reclaiming respective persistent storage utilized for storing at least one of proposal agreements and said proposals.

16. The method of claim 15 wherein said precluding repeated preemptions includes preserving an issuance order of said proposals while concurrent agreement on said proposals is facilitated.

17. The method of claim 15:

wherein a portion of said proposals are proposed write steps corresponding to a respective information update; and

further comprising;

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

creating a globally unique interleaving of said proposed write steps such that all distributed application nodes executing said proposed write steps execute said proposed write steps in a common sequence.

18. The method of claim 15, further comprising:

assigning a unique local sequence number to a local sequencer entry of each one of said proposals, wherein the local sequencer entry corresponding to each one of said proposals resides within a local sequencer;

sequentially arranging the local sequencer entry corresponding to each one of said proposals with respect to the assigned local sequence number; and

after agreement on one of said proposals is successfully performed, creating an entry corresponding to said one proposal upon which agreement is facilitated within a global sequencer in response to determining a position in which the entry is positioned within the global sequencer.

19. The method of claim 18 wherein said reclaiming persistent storage includes deleting a record for said one proposal from persistent proposal storage after the position of the entry in the global sequencer is determined.

20. The method of claim 18 wherein precluding repeated preemptions includes at least one of:

waiting for a computed preemption-delay duration to pass after starting a current one of said rounds for a first proposer before initiating a next one of said round for the first proposer; and

waiting for a computed round-in-progress delay duration to pass after starting a current one of said rounds for the first proposer before starting a next one of said rounds for a second proposer.