Consistent group membership for semi-active and passive replication

• US 7,185,236 B1
• Filed: 08/30/2003
• Issued: 02/27/2007
• Est. Priority Date: 08/30/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: Eternal Systems, Inc.
• Inventors: Melliar-Smith, Peter M., Moser, Louise E.
• Primary Examiner(s): Beausoliel; Robert
• Assistant Examiner(s): Ehne; Charles
• Application Number:
  US10/651,755
• Time in Patent Office: 1,277 Days
• Field of Search: 714/4, 714/10, 714/11, 714/13, 709/209
• US Class Current: 714/47.2
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/2028 eliminating a faulty processor or activating a spare
• CPC Class Codes: G06F 11/2041 with more than one idle spare processing component
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

This invention defines a method and mechanisms for maintaining a consistent group membership, based on the leader-follower strategy of Semi-Active or Passive replication. Each member of the group is assigned a rank, and a precedence, determined by the order in which it is added to the group. The Primary maintains the membership of the group, while each Backup monitors the behavior of the Primary. When a Backup detects that the Primary is faulty, the Backup announces that it is the new Primary and removes the faulty Primary from the membership of the group. The group membership algorithm disclosed here does not require a consensus decision to reconfigure the membership and effects a membership change more quickly in the common case where the Backup of lowest rank takes control as the new Primary when it determines that the existing Primary failed.

Claims

1. A method of maintaining consistent group membership for objects, wherein objects are distributed across a plurality of networked computers, said method comprising:

classifying one member of a group as a Primary;

classifying at least one other member of said group as a Backup;

assigning a rank to each member of said group, with said Primary member having the lowest rank;

assigning a unique precedence to each member of said group;

based on rank of a Backup member, allowing a Backup member to claim status as the Primary member if said Backup member detects the failure of said Primary member;

announcing the failure of said Primary member by said Backup member; and

removing Backup members having a lower rank than said Backup member that has claimed status as said Primary member.

2. A method as recited in claim 1, further comprising communicating a message to other members of said group that said Backup member has claimed Primary status, wherein said message includes a new primary view number.

3. A method as recited in claim 2, wherein said primary view number is utilized in communications with other groups so that said other groups can detect a change in primary view number that can indicate that messages communicated under the prior primary view number were lost.

4. A method as recited in claim 1, wherein members removed from the group membership by said Backup member that has assumed the role of the new Primary member may subsequently reapply for membership.

5. A method as recited in claim 1, wherein said Primary member determines the addition of Backup members to the group, and the removal of Backup members from the group.

6. A method as recited in claim 1, further comprising the determination that the Primary member has failed when a lack of valid activity from said Primary member is detected.

7. A method as recited in claim 6, further comprising the determination that a lack of valid activity has occurred when a message has not been received from said Primary member within a fault detection timeout interval.

8. A method as recited in claim 1, wherein if more than one Backup member determines that said Primary member is faulty, the selection of which Backup member assumes the role of the new Primary member depends on said precedence.

9. A method as recited in claim 8, wherein assigning said precedence is performed in the order in which members are added to said group.

10. A method as recited in claim 9, wherein the rank of a member is determined by its precedence.

11. A method as recited in claim 1, wherein the members of said group maintain a consistent group membership view in response to membership changes without the need for a multiple-round consensus algorithm.

12. A method as recited in claim 1, wherein said Primary member of said group operates as the leader of said group while the remaining members operate as Backup members which follow said Primary member.

13. A method as recited in claim 1, wherein consistent group membership comprises maintaining agreement between all members of said group on the membership of said group and which is the Primary member of the group.

14. A method as recited in claim 1, wherein consistent group membership comprises ensuring that all members of said group have the same view of the membership set of said group and the identity of said Primary member.

15. A method as recited in claim 1, wherein a new membership of said group can be formed after faults in any number of said members, provided that at least one member remains as non-faulty.

16. A method as recited in claim 1, wherein said new membership of said group is formed in response to a single message multicast by the new Primary member.

17. A method as recited in claim 1, wherein one or more rounds of message exchanges between members of said group is not required to reach agreement on the membership of the group.

18. A method of maintaining consistent group membership for objects, wherein objects are distributed across a plurality of networked computers, said method comprising:

classifying one member of a group as a Primary;

classifying at least one other member of said group as a Backup;

assigning a rank to each member of said group, with said Primary member having the lowest rank;

assigning a unique precedence to each member of said group;

based on rank of a Backup member, allowing a Backup member to claim status as the Primary member if said Backup member detects the failure of said Primary member; and

announcing the failure of said Primary member by said Backup member;

wherein the determination that the Primary member has failed when a lack of valid activity from said Primary member is detected;

wherein the determination that a lack of valid activity has occurred when a message has not been received from said Primary member within a fault detection timeout interval; and

wherein said fault detection timeout interval depends on said rank of said member.

19. A method of maintaining consistent group membership for objects, wherein objects are distributed across a plurality of networked computers, said method comprising:

classifying one member of a group as a Primary;

classifying at least one other member of said group as a Backup;

assigning a rank to each member of said group, with said Primary member having the lowest rank;

assigning a unique precedence to each member of said group;

based on rank of a Backup member, allowing a Backup member to claim status as the Primary member if said Backup member detects the failure of said Primary member; and

announcing the failure of said Primary member by said Backup member;

wherein the determination that the Primary member has failed when a lack of valid activity from said Primary member is detected;

wherein the determination that a lack of valid activity has occurred when a message has not been received from said Primary member within a fault detection timeout interval;

wherein a fault in the Primary member is detected by lower ranking Backup members having a shorter fault detection timeout interval than higher ranking Backup members; and

wherein said fault may be detected by lower ranking Backup members earlier than higher ranking Backup members.

20. A method of maintaining consistent group membership for objects, wherein objects are distributed across a plurality of networked computers, said method comprising:

classifying one member of a group as a Primary;

classifying at least one other member of said group as a Backup;

assigning a rank to each member of said group, with said Primary member having the lowest rank;

assigning a unique precedence to each member of said group;

based on rank of a Backup member, allowing a Backup member to claim status as the Primary member if said Backup member detects the failure of said Primary member; and

announcing the failure of said Primary member by said Backup member;

wherein the determination that the Primary member has failed when a lack of valid activity from said Primary member is detected;

wherein the determination that a lack of valid activity has occurred when a message has not been received from said Primary member within a fault detection timeout interval; and

wherein said fault detection timeout interval for the Backup member of lowest rank is set to a time period within which said Primary member is expected to have performed actions.

21. A computer system, in which application objects are replicated by semi-active or passive replication across a plurality of networked computers to provide fault tolerance, said system comprising:

replication software executable on one or more networked computers in said system; and

means associated with said replication software for maintaining a consistent membership view between a Primary member and Backup members, and wherein any of said Backup members can determine that the Primary member is faulty and can determine the new membership;

wherein replacement of a faulty Primary member and additional faulty Backup members is based on the ranks of the members, which determine the timeout periods necessary for detecting a fault.

22. A computer system as recited in claim 21, wherein said Primary member determines and communicates membership information to the other members of said group.

23. A computer system as recited in claim 21:

wherein a rank is assigned to each member of said group;

wherein the Backup member that first detects the failure of said Primary member asserts itself as the new Primary member and determines the group membership.

24. A computer system as recited in claim 23, wherein the timeout period for detecting the failure of a Primary member by a Backup member depends on the rank of said Backup member.

25. A computer system as recited in claim 24, further comprising assigning precedence values to the members of said group, wherein selection of said new Primary member is subject to said precedence when more than one Backup member detects that said Primary member is faulty.

26. A computer system as recited in claim 25, wherein said precedence is assigned to members of said group in response to the order in which members are added to said group.

27. A computer program having a computer readable medium with computer readable code stored thereon, said computer readable code executable on one or more computers in a system of networked computers wherein application objects are replicated by semi-active or passive replication across a plurality of networked computers for fault tolerance, said system comprising:

instructions for ranking members within a group of objects and communicating membership information from a Primary member to Backup members within a group of objects; and

instructions for said Backup members to detect the failure of said Primary member and to claim to be the new Primary member;

wherein the time required for a Backup member to detect the failure of said Primary member is determined by the ranking of said Backup member.

28. A computer program as recited in claim 27, wherein the first Backup member that detects a failure of said Primary member asserts itself as the new Primary member to determine the group membership.

29. A computer program as recited in claim 28, wherein if more than one Backup member asserts itself as the new Primary member, then the precedence of the Backup member determines which Backup member will operate as the new Primary member.

30. A computer program as recited in claim 29, wherein said precedence is assigned to members of said group in response to the order in which members are added to said group.

31. A method of maintaining group membership based on the leader-follower strategy of Semi-Active or Passive replication, comprising the steps of:

monitoring the behavior of a Primary member of a group by other members of the group;

forming a new membership for the group by choosing a new Primary member for the group in response to said Primary member being detected as faulty by a Backup member;

wherein the membership set and the choice of said new Primary member is consistent across the members of the group;

wherein the determination of the membership set and the choice of said new Primary member avoids the need for a consensus decision; and

wherein the determination of the membership set and the choice of said new Primary member avoids the overhead of the large number of messages that must be multicast in a consensus algorithm;

wherein the determination that said Primary member is faulty is based on the non-occurrence of events relating to said Primary member within the interval of a timeout; and

wherein the duration of said timeout at a Backup member is determined by the rank of the Backup member.

32. A method as recited in claim 31, wherein a new membership can be formed after faults arise in any number of members, provided that at least one member is non-faulty.

33. A method as recited in claim 31, wherein a new membership is formed by a single message multicast by said new Primary member without any rounds of message exchange with other members of said group.

34. A method as recited in claim 31, wherein the members of said group are assigned precedences that are determined by the order in which the members are added to said group.

35. A method as recited in claim 34, wherein if two Backup members both claim to be the new Primary member, the Backup member having the higher precedence prevails and becomes the new Primary member.

36. A method as recited in claim 31:

wherein the members of said group are assigned ranks;

wherein said Primary member has the lowest rank and said Backup members have higher ranks.

37. A method as recited in claim 36, wherein the rank of a member is determined by its precedence.

38. A method as recited in claim 31, wherein a new membership can be formed after faults arise in any number of members, provided that at least one member is non-faulty.

39. A method as recited in claim 31, wherein each Backup member monitors the behavior of said Primary member and is able to assume the role of the Primary as a result of determining that said Primary member is faulty.

40. A method as recited in claim 31, wherein said non-occurrence of events comprises the reception of messages or acknowledgments from said Primary member.

41. A method as recited in claim 31, wherein the duration of said timeout for the Backup member of lowest rank is determined in response to the time within which said Primary member is expected to have performed actions.

42. A method as recited in claim 41, wherein the duration of the timeout, in each Backup member of higher rank, for said Primary member is determined by the time within which said Primary member is expected to have performed actions plus the time within which the Backup member of the next lower rank is expected to have detected the faulty behavior of said Primary member and to have assumed the role of the Primary.

43. A method of maintaining group membership based on the leader-follower strategy of Semi-Active or Passive replication, comprising the steps of:

monitoring the behavior of a Primary member of a group by other members of the group;

forming a new membership for the group by choosing a new Primary member for the group in response to said Primary member being detected as faulty by a Backup member;

wherein the membership set and the choice of said new Primary member is consistent across the members of the group;

wherein the determination of the membership set and the choice of said new Primary member avoids the need for a consensus decision; and

wherein the determination of the membership set and the choice of said new Primary member avoids the overhead of the large number of messages that must be multicast in a consensus algorithm; and

wherein a given Backup member, having determined that said Primary member is faulty, multicasts a message to the group members announcing that said Primary member is faulty, and that said Backup member is the new Primary member, and that all Backup members of lower ranks than said Backup member are to remove themselves from said group.

44. A method as recited in claim 43, wherein members that were previously removed from said group, as a consequence of a Backup member announcing that it has become the new Primary member, can reapply for membership in said group.

45. A method as recited in claim 44, wherein an applicant on admission to said group, is assigned a higher precedence than the precedences of all of the current or prior members of said group.

46. A method as recited in claim 45, wherein said message multicast to said group also announces a new primary view number.

47. A method as recited in claim 46, wherein every request, reply or other message carries the primary view number.

48. A method as recited in claim 47, wherein said primary view number is utilized by members of other groups in request, reply and other messages to become informed that there is a new Primary member of the group and that request, reply or other messages containing the prior primary view number might have been lost.