Choosing a leader in a replicated memory system

• US 10,078,464 B2
• Filed: 07/17/2016
• Issued: 09/18/2018
• Est. Priority Date: 07/17/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bortnikov, Vita, Carman, David H., Clay, Steven D., Shachor, Shlomit I., Shnayderman, Ilya
• Primary Examiner(s): Rossiter, Sean D
• Application Number:
  US15/212,274
• Publication Number:
  US 20180018120A1
• Time in Patent Office: 793 Days
• Field of Search: None
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0634 by changing the state or mode of one or more devices
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

An approach is provided in which a replicated memory system replicates a set of data between multiple replicas, whereby each of the replicas includes a sequence update number corresponding to an update state of its respective set of data. At least one of the replicas identifies a number of replicas to which it connects and, in turn, the replicas select one of replicas as a leader replica based at least on the selected leader replica'"'"'s sequence update number and the number of replicas to which the selected leader connects.

Claims

1. A method implemented by an information handling system that includes a memory and a processor, the method comprising:

operating a replicated memory system that replicates a set of data between each of a plurality of replicas, wherein each of the plurality of replicas includes a sequence update number corresponding to an update state of its respective set of data;

identifying, by at least one of the plurality of replicas, a number of the plurality of replicas to which it connects; and

selecting one of the plurality of replicas as a leader replica based at least on its sequence update number and the number of the plurality of replicas to which it connects.

2. The method of claim 1 further comprising:

determining, by the at least one of the plurality of replicas, a new leader request delay based at least on its sequence update number and the number of the plurality of replicas to which it connects; and

transmitting, by the at least one of the plurality of replicas, a new leader request to a set of the plurality of replicas at a point in time corresponding to the new leader request delay.

3. The method of claim 2 further comprising:

estimating a highest sequence update number corresponding to a most recent update state of the set of data in at least one of the plurality of replicas;

computing, by the at least one of the plurality of replicas, a sequence update delay based upon its respective sequence update number the estimated highest sequence update number; and

utilizing the sequence update delay during the determining of the new leader request delay.

4. The method of claim 3 further comprising:

determining a total number of replicas in the plurality of replicas;

computing, by the at least one of the plurality of replicas, a connectivity delay based on the determined total number of replicas and the number of the plurality of replicas to which the at least one of the plurality of replicas connects; and

utilizing the connectivity delay and the sequence update delay during the determining of the new leader request delay.

5. The method of claim 4 further comprising:

utilizing a sequence delay constant during the computing of the sequence update delay; and

utilizing a connectivity constant during the computing of the connectivity delay, wherein the connectivity constant has a higher weighting than the sequence delay constant during the determining of the new leader request delay.

6. The method of claim 2 further comprising:

receiving one or more leader vote messages from the set of the plurality of replicas in response to transmitting the new leader request;

determining, by the at least one of the plurality of replicas, to become a leader replica based on the received one or more leader vote messages; and

transmitting a new leader acknowledgment message to the set of the plurality of replicas that informs the set of the plurality of replicas that the selected replica is the leader replica.

7. The method of claim 1 wherein the replicated memory system is a distributed replicated cache system, and wherein each of the plurality of replicas include a cache that stores its respective set of data.

8. The method of claim 1 wherein the plurality of replicas determine the leader replica independent of an external administration selection.

9. An information handling system comprising:

one or more processors;

a memory coupled to at least one of the processors; and

a set of computer program instructions stored in the memory and executed by at least one of the processors in order to perform actions of;

operating a replicated memory system that replicates a set of data between each of a plurality of replicas, wherein each of the plurality of replicas includes a sequence update number corresponding to an update state of its respective set of data;

identifying, by at least one of the plurality of replicas, a number of the plurality of replicas to which it connects; and

selecting one of the plurality of replicas as a leader replica based at least on its sequence update number and the number of the plurality of replicas to which it connects.

10. The information handling system of claim 9 wherein at least one of the one or more processors perform additional actions comprising:

determining, by the at least one of the plurality of replicas, a new leader request delay based at least on its sequence update number and the number of the plurality of replicas to which it connects; and

transmitting, by the at least one of the plurality of replicas, a new leader request to a set of the plurality of replicas at a point in time corresponding to the new leader request delay.

11. The information handling system of claim 10 wherein at least one of the one or more processors perform additional actions comprising:

estimating a highest sequence update number corresponding to a most recent update state of the set of data in at least one of the plurality of replicas;

computing, by the at least one of the plurality of replicas, a sequence update delay based upon its respective sequence update number the estimated highest sequence update number; and

utilizing the sequence update delay during the determining of the new leader request delay.

12. The information handling system of claim 11 wherein at least one of the one or more processors perform additional actions comprising:

determining a total number of replicas in the plurality of replicas;

computing, by the at least one of the plurality of replicas, a connectivity delay based on the determined total number of replicas and the number of the plurality of replicas to which the at least one of the plurality of replicas connects; and

utilizing the connectivity delay and the sequence update delay during the determining of the new leader request delay.

13. The information handling system of claim 12 wherein at least one of the one or more processors perform additional actions comprising:

utilizing a sequence delay constant during the computing of the sequence update delay; and

utilizing a connectivity constant during the computing of the connectivity delay, wherein the connectivity constant has a higher weighting than the sequence delay constant during the determining of the new leader request delay.

14. The information handling system of claim 10 wherein at least one of the one or more processors perform additional actions comprising:

receiving one or more leader vote messages from the set of the plurality of replicas in response to transmitting the new leader request;

determining, by the at least one of the plurality of replicas, to become a leader replica based on the received one or more leader vote messages; and

transmitting a new leader acknowledgment message to the set of the plurality of replicas that informs the set of the plurality of replicas that the selected replica is the leader replica.

15. The information handling system of claim 9 wherein the plurality of replicas determine the leader replica independent of an external administration selection.

16. A computer program product stored in a computer readable storage medium, comprising computer program code that, when executed by an information handling system, causes the information handling system to perform actions comprising:

operating a replicated memory system that replicates a set of data between each of a plurality of replicas, wherein each of the plurality of replicas includes a sequence update number corresponding to an update state of its respective set of data;

identifying, by at least one of the plurality of replicas, a number of the plurality of replicas to which it connects; and

selecting one of the plurality of replicas as a leader replica based at least on its sequence update number and the number of the plurality of replicas to which it connects.

17. The computer program product of claim 16 wherein the information handling system performs additional actions comprising:

determining, by the at least one of the plurality of replicas, a new leader request delay based at least on its sequence update number and the number of the plurality of replicas to which it connects; and

transmitting, by the at least one of the plurality of replicas, a new leader request to a set of the plurality of replicas at a point in time corresponding to the new leader request delay.

18. The computer program product of claim 17 wherein the information handling system performs additional actions comprising:

estimating a highest sequence update number corresponding to a most recent update state of the set of data in at least one of the plurality of replicas;

computing, by the at least one of the plurality of replicas, a sequence update delay based upon its respective sequence update number the estimated highest sequence update number; and

utilizing the sequence update delay during the determining of the new leader request delay.

19. The computer program product of claim 18 wherein the information handling system performs additional actions comprising:

determining a total number of replicas in the plurality of replicas;

computing, by the at least one of the plurality of replicas, a connectivity delay based on the determined total number of replicas and the number of the plurality of replicas to which the at least one of the plurality of replicas connects; and

utilizing the connectivity delay and the sequence update delay during the determining of the new leader request delay.

20. The computer program product of claim 19 wherein the information handling system performs additional actions comprising:

utilizing a sequence delay constant during the computing of the sequence update delay; and

utilizing a connectivity constant during the computing of the connectivity delay, wherein the connectivity constant has a higher weighting than the sequence delay constant during the determining of the new leader request delay.