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

• US 7,451,221 B2
• Filed: 03/03/2005
• Issued: 11/11/2008
• 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): Chang; Jungwon
• Application Number:
  US11/071,655
• Publication Number:
  US 20050198359A1
• Time in Patent Office: 1,349 Days
• Field of Search: 709/201, 709/220, 709/224, 709/226, 709/229, 709/208, 714/4
• US Class Current: 709/226
• 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

A system and apparatus for control and distribution of data files in large-scale distributed networks. Members of a group of servers in a multicast network elect a group leader whenever a new group leader is required, as detected by absence of a periodic message published by the leader. 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 distributing content in a computer network, comprising:

receiving the content by a first server;

dividing a plurality of servers into a plurality of groups of servers, each group of servers having a plurality of servers;

selecting a group leader server by each group of servers, to form a plurality of group leader servers, each group having a group leader and one or more back end servers;

reporting the selection of the group leader servers to the first server;

deriving, by the first server, an optimally sorted list of the plurality of group leader servers for the distribution of content to the plurality of the group leader servers;

transmitting the content by the first server to a one or more of the group leader servers;

transmitting by the one or more group leader servers, in response to the optimally sorted list, the content to one or more other group leader servers; and

transmitting the content by each group leader server of the plurality of group leader servers to its back end servers.

2. The method as in claim 1, further comprising:

determining the group leader of the each group of servers by the servers of each group of servers executing the following method;

a set of participant servers, the participant servers selected from the plurality of servers forming the each group of 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 messages (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 sent 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.

3. The method as in claim 1, further comprising:

determining the group leader of the each group of servers by the servers of each group of servers executing the following method;

configuring a set of plurality of 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

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.

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

5. The method of claim 3 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.

6. The method of claim 1 in which said optimal list is arranged in order according to location.

7. The method of claim 1 in which said optimal list is arranged in order according to a dynamic network factors.

8. The method of claim 1 in which the election of a group leader is calculated using a voting method by the plurality of back end servers.

9. A computer network, comprising:

a first server to receive a content;

a plurality of servers divided into a plurality of groups of servers, each group of servers having a plurality of servers;

a group leader server to be selected by each group of servers, to form a plurality of group leader servers, each group having a group leader and one or more back end servers;

the selection of the group leader servers reported to the first server;

an optimally sorted list of the plurality of group leader servers, derived by the first server, for the distribution of content to the plurality of the group leader servers;

the first server to transmit the content to a one or more of the group leader servers;

one or more group leader servers to transmit, in response to the optimally sorted list, the content to one or more other group leader servers; and

each group leader of the plurality of group leader servers to transmit the content to its back end servers.