Continuous operation during reconfiguration periods

• US 8,943,178 B2
• Filed: 08/29/2012
• Issued: 01/27/2015
• Est. Priority Date: 08/29/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bortnikov, Vita, Chockler, Gregory, Perelman, Dmitri, Shachor, Shlomit, Shnayderman, Ilya, Roytman, Alexey
• Primary Examiner(s): Luu, Le H
• Application Number:
  US13/597,273
• Publication Number:
  US 20140074996A1
• Time in Patent Office: 881 Days
• Field of Search: 709/223, 709/221, 709/220, 711/202, 370/255, 718/100, 717/168, 375/260, 702/186, 714/16
• US Class Current: 709/221
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/082 the condition being updates or upgrades of network functionality
• CPC Class Codes: H04L 41/0846 based on copy from other elements
• CPC Class Codes: H04L 41/0873 Checking configuration conflicts between network elements
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements

Abstract

A method for continuously updating a set of replicas. The method comprises storing a plurality of replicas of data in a current configuration of members from a plurality of nodes, receiving a reconfiguration command by a member of said current configuration, selecting at least one estimated configuration from said plurality of nodes, receiving at least one write command by a member of said current configuration, disseminating said at least one write command to each member of said at least one estimated configuration and validating said at least one estimated configuration. At least one estimated configuration processes at least one of the write commands before the validating is completed.

Claims

1. A method for updating a plurality of replicas, comprising:

storing a plurality of replicas of data in a current configuration of members from a plurality of nodes;

receiving a reconfiguration command by a member of said current configuration;

selecting at least one estimated configuration from said plurality of nodes;

receiving at least one write command by a member of said current configuration;

disseminating said at least one write command to each member of said at least one estimated configuration; and

validating said at least one estimated configuration;

wherein said at least one estimated configuration processes said at least one write command before said validating is completed.

2. The method of claim 1, wherein said plurality of nodes are nodes of a network cloud.

3. The method of claim 1, wherein said plurality of nodes are nodes of an elastic cluster.

4. The method of claim 1, wherein said validating operation is performed according to a Paxos agreement.

5. The method of claim 1, wherein said at least one estimated configuration comprises a plurality of estimated configurations and at least one estimated configuration processes said at least one write command before said validating is completed.

6. The method of claim 5, wherein at least one invalid estimated configuration from said plurality of estimated configurations is deleted after said validating.

7. The method of claim 5, wherein said plurality of estimated configurations are logged by a branching command log managed in each said replica.

8. A management system having a plurality of routing modules implementing the method of claim 1 on nodes.

9. A method for managing a plurality of estimated replica set configurations, comprising:

managing a branched command log;

adding a branch to said branched command log when a replica receives a new estimated configuration; and

executing a plurality of independent sequences of a state machine consensus protocol agreements by performing each write command in said command log branch;

wherein at least one of a plurality of said write command is executed in an estimated configurations prior to validation of said estimated configuration.

10. The method of claim 9, wherein said command log branch is identified by a slot number, a ballot number used to propose said reconfiguration command, and an identifier of a replica member proposed with said reconfiguration command.

11. The method of claim 9, wherein said state machine consensus protocol is Paxos.

12. The method of claim 9, wherein invalid estimated configurations for said reconfiguration command become obsolete upon said validation.

13. The method of claim 12, wherein a command log branch of an invalid configuration is deleted upon validation of an estimated configuration of a command log branch branching from a common tree node as said invalid command log branch.

14. A system for continuous operation of a network during reconfiguration periods, comprising:

a plurality of routing modules installed in a plurality of nodes which hosts a plurality of replicas of data, each said routing module receives and disseminate a write command;

a configuration manager which chooses a leader node from said plurality of network nodes; and

a plurality of replication groups having a plurality of said replicas;

wherein each said leader node is defined to receive a reconfiguration command from said configuration manager and to propose an estimated configuration, and said node disseminates a write command from a client in at least one said estimated configuration prior to validation of said estimated configuration.

15. The system of claim 14, wherein said configuration manager is said network node.

16. The system of claim 14, further comprising a branching command log hosted in said plurality of replicas;

wherein said leader node is further defined to save said plurality of estimated configurations in said branching command log.