Method and apparatus for election of group leaders in a distributed network

• US 6,993,587 B1
• Filed: 04/07/2000
• Issued: 01/31/2006
• Est. Priority Date: 04/07/2000
• Status: Expired due to Term

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Karge, Leroy R., Revsin, Vitaly S., Basani, Vijay R., Crovella, Mark E., LaRosa, Domenic J., Mangipudi, Krishna, Bestavros, Azer, Murach, Lynne M.
• Primary Examiner(s): Follansbee, John
• Assistant Examiner(s): Chang, Jungwon
• Application Number:
  US09/544,754
• Time in Patent Office: 2,125 Days
• Field of Search: 709/228, 709/229, 709/242, 709/208, 709/244, 714/4, 398/58, 359/118, 359/58
• US Class Current: 709/229
• 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/329 in the application layer [OSI layer 7]

Abstract

The present invention provides a system and apparatus for efficient and reliable, control and distribution of data files in large-scale distributed networks. The members of a group of servers in a multicast network elect a group leader whenever a new group leader is required, as when the prior group leader become unavailable, as detected by absence of a periodic heartbeat message published by the leader. The election is carried out by a system of voting by each candidate whereby each candidate has a priority calculated from its configuration, and the server with the highest priority is configured to claim the leadership faster than the other candidates. As part of the claim, each candidate multicasts its priority. Each candidate that receives a multicast claim for leadership from another candidate compares its own priority against the claimant and only votes for itself if its own priority is higher. After a preconfigured period of hearing no other claimants with higher priority, the candidate with the highest priority becomes the new leader.

Claims

1. A method for selecting a group leader among servers in a multicast network segment comprising the steps of:

configuring a set of said servers to participate in electing a leader, each said server having a corresponding voting priority;

determining when a new leader is needed by configuring each server that is not currently the group leader to listen for periodic messages from said group leader;

adapting each server to send said periodic messages only if said server is currently the group leader;

waiting a configurable period after no periodic messages are heard; and

multicasting said voting priority to each participant;

said set of servers electing one server of said set to become said new leader by voting wherein voting is performed by sending a leadership claim message including a priority claim at an interval determined by strength of a claim a candidate has on becoming the group leader.

2. The method of claim 1 in which said step of configuring a set of servers further comprises the steps of:

measuring a set of leader selection parameters in each participant in said set; and

calculating the corresponding voting priority according to said measurements.

3. The method of claim 1 in which said periodic messages are multicast on a predetermined network channel comprised of an IP multicast address and a port number.

4. The method of claim 1 in which said multicasting is addressed to a preconfigured IP multicast IP address and port combination for each server of said set of participating servers.

5. The method of claim 1 in which said step of electing further comprises the steps of:

sending a claim of leadership containing a sent voting priority;

listening for other servers to claim leadership;

comparing a received priority in any other claims to leadership with said sent voting priority; and

determining said new leader according to the server having claimed leadership with the highest voting priority.

6. The method of claim 5 in which said step of sending a claim of leadership is implemented using a multicast message on said multicast network segment.

7. A system for determining a group leader among a group of servers comprising:

a set of participant servers including at least some servers capable of participating in electing a group leader;

a communication channel from each participant to each other participant;

a monitor process in each participant to determine which server is the current group leader;

an election process in each participant to calculate a voting priority of said participant and to select a new group leader according to said voting priority, said election process triggered by said monitor process;

wherein voting is performed by sending a leadership claim message including a priority claim at an interval determined by strength of a claim a candidate has on becoming the group leader;

configuring each server that is not currently the group leader to listen for periodic messages from said group leader;

adapting each server to send said periodic messages only if said server is currently the group leader;

waiting a configurable period after no periodic messages are heard; and

multicasting said voting priority to each participant.

8. The system of claim 7 in which said monitor process further comprises:

a listener in each participant for determining how long since a group leader alive message has been heard on said communication channel;

a transmitter in each participant, operable in an elected group leader, that periodically signals each other participant who the current group leader is; and

a trigger adapted to detect that a group leader has not been heard from for a time longer than a threshold time, according to the period of said periodic signal.

9. The system of claim 8 in which said threshold time is configured such that a trigger will occur no less than five seconds after the last group leader alive message was received by said monitor process.

10. The system of claim 8 in which said predetermined voting time interval is no greater than 15 seconds.

11. The system of claim 7 in which said voting priority for each participant is determined dynamically according to at least one parameter selected from the set of:

how recently was said participant the group leader, the number of servers known to said participant, the amount of resources available to such participant, reliability of the participant, the amount of recent information content the participant has acquired, and a user-specified priority factor.

12. A system for determining a group leader among a group of servers comprising:

a set of participant servers including at least some servers capable of participating in electing a group leader;

a communication channel from each participant to each other participant;

a monitor process in each participant to determine which server is the current group leader; and

an election process in each participant to calculate a voting priority of said participant and to select a new group leader according to said voting priority, said election process triggered by said monitor process,

wherein said election process further comprises a state machine adapted to transition from a temporary state of group leader unknown to a stable state of either group leader known or group leader is me, according to the following steps;

in said state of group leader unknown, if one or more group leader claim messages (LC) are received in which a received voting priority is greater than said calculated voting priority, then transition to a concession state and wait for a group leader alive message (LA); and

if no LC is received before a period determined by said calculated voting priority, or no received voting priority is greater than said calculated voting priority, then transmit an LC including said calculated voting priority, and transition to a voting open state;

in said concession state, when an LA is received, transition to said group leader known state;

in said voting open state, if no LC or LA is received for a predetermined time interval, then transition to said group leader is me state and transmit an LA; and

if one or more LC is received prior to said predetermined voting time interval, then transition to said group leader unknown state and transmit an LC; and

if an LA is received, then transition to said group leader known state;

in said group leader is me state, periodically send an LA until an LC or LA is received, and then transition to said voting open state and send an LC; and

in said group leader known state, upon a trigger from said monitor process, transition to said group leader unknown state and transmit an LC;

whereby a participant having the highest calculated voting priority is elected group leader.

13. A method for determining registration of members of a cluster of servers on a network segment comprising the steps of:

(A) designating a group leader on said network segment;

(B) each member sending a registration message to said group leader;

(C) said group leader multicasting a registration report including an identifier corresponding to each registered member;

(D) sending another registration message from any member receiving said registration report in which said member'"'"'s corresponding identifier is missing;

(E) repeating steps (C) and (D) until each said member receives a registration report including its own corresponding identifier as a registered member;

in which said step of designating said group leader is carried out among a set of servers of said cluster according to a voting priority determined by at least some of said members from a set of dynamic parameters measured within themselves;

wherein voting is performed by sending a leadership claim message including a priority claim at an interval determined by strength of a claim a candidate has on becoming the group leader;

configuring each server that is not currently the group leader to listen for periodic messages from said group leader;

adapting each server to send said periodic messages only if said server is currently the group leader;

waiting a configurable period after no periodic messages are heard; and

multicasting said voting priority to each participant.

14. The method of claim 13 in which said step of multicasting said registration report occurs after a configurable interval has expired since the most recent registration request was received by said group leader.

15. The method of claim 13 in which said step (D) of sending another registration message occurs after a preconfigured interval, after receipt of a registration report or a registration request, comprised of a fixed interval and a random interval, said random interval being up to one second.

16. The method of claim 13 in which said registration requests include at least some identification information selected from the set of:

a server'"'"'s IP address, a server'"'"'s name, a server'"'"'s port number, and a secret key.

17. The method of claim 13 further comprising the steps of:

processing said registration reports in said group leader to create a cluster report; and

transmitting said cluster report to a network distribution server, whereby said cluster reports are dynamically collected from all clusters in said network.

18. The method of claim 17 in which said cluster report further includes at least some group leader information selected from the set of:

a list of registered members, identification information from at least some of said registered members, a network segment identifier, an IP address of said group leader, and a location parameter for said group leader.