Leader election in HLD - System Design Exercise

Design: Distributed Leader Election System

Design focuses on leader election mechanism and fault tolerance. Does not cover full distributed consensus or data replication.

Functional Requirements

FR1: Elect a single leader node among multiple distributed nodes

FR2: Handle node failures and re-elect leader if current leader fails

FR3: Ensure only one leader exists at any time (no split-brain)

FR4: Support dynamic addition and removal of nodes

FR5: Provide fast leader election to minimize downtime

FR6: Allow nodes to detect leader status and act accordingly

Non-Functional Requirements

NFR1: System must handle up to 1000 nodes

NFR2: Leader election latency should be under 5 seconds

NFR3: System availability target is 99.9% uptime

NFR4: Network partitions may occur and must be handled gracefully

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Node communication protocol (heartbeat, messaging)

Failure detection mechanism

Leader election algorithm implementation

State storage for leader info (in-memory or distributed store)

Timeout and retry logic

Design Patterns

Bully algorithm

Ring algorithm

Raft leader election phase

Paxos leader election

Heartbeat and timeout pattern

Reference Architecture

  +-------------------+       +-------------------+       +-------------------+
  |      Node 1       |<----->|      Node 2       |<----->|      Node 3       |
  +-------------------+       +-------------------+       +-------------------+
           |                          |                          |
           | Heartbeats & Election Messages                      |
           +----------------------------------------------------+
                                   |
                           Leader Election Logic
                                   |
                          +-------------------+
                          |   Leader Node      |
                          +-------------------+

Components

Nodes

Any distributed system nodes (servers, containers)

Participate in leader election and perform leader or follower roles

Communication Layer

TCP/UDP or RPC messaging

Exchange heartbeat and election messages between nodes

Failure Detector

Timeout-based heartbeat monitoring

Detect node failures by missing heartbeats

Leader Election Module

Algorithm implementation (e.g., Bully algorithm)

Run election process to select a single leader

State Store

In-memory or distributed key-value store

Store current leader identity and election state

Request Flow

1. 1. Each node periodically sends heartbeat messages to other nodes.

2. 2. Nodes monitor heartbeats to detect failures.

3. 3. When a node detects leader failure or startup, it initiates leader election.

4. 4. Nodes exchange election messages according to the chosen algorithm.

5. 5. Nodes agree on a single leader based on priority or ID.

6. 6. The elected leader broadcasts its status to all nodes.

7. 7. Nodes update their state to recognize the leader.

8. 8. If leader fails, process repeats.

Database Schema

Entities: - Node: node_id (PK), status (active, failed), priority - Leader: leader_node_id (FK to Node), election_term, timestamp Relationships: - One leader per election_term - Nodes participate in election terms This schema supports tracking current leader and node statuses.

Scaling Discussion

Bottlenecks

Network congestion due to many heartbeat and election messages

Slow failure detection with large number of nodes

Split-brain scenarios during network partitions

Leader election latency increases with node count

Solutions

Use hierarchical or partitioned election groups to reduce message overhead

Implement adaptive heartbeat intervals and failure detection thresholds

Use quorum-based election algorithms to avoid split-brain

Optimize election algorithm to reduce message rounds (e.g., use Bully algorithm with priority)

Leverage distributed consensus protocols like Raft for stronger guarantees if needed

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing the architecture and data flow, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing.

Clarify assumptions about network and node behavior

Explain choice of leader election algorithm and why

Describe failure detection and handling of node crashes

Discuss how to avoid split-brain and ensure single leader

Address scaling challenges and solutions

Mention trade-offs between simplicity and consistency

Practice

1. What is the main purpose of leader election in a distributed system?

easy

A. To delete inactive nodes automatically

B. To increase the number of nodes in the system

C. To encrypt communication between nodes

D. To select one node as the main coordinator for tasks

Solution

1. Step 1: Understand the role of leader election

   Leader election is used to pick one node to coordinate tasks in a distributed system.

2. Step 2: Identify the correct purpose

   Among the options, only selecting a main coordinator matches the leader election goal.

3. Final Answer:

   To select one node as the main coordinator for tasks -> Option D

4. Quick Check:

   Leader election = select coordinator [OK]

Hint: Leader election picks one main node to coordinate [OK]

Common Mistakes:

• Confusing leader election with node addition
• Thinking it deletes nodes automatically
• Assuming it handles encryption

2. Which of the following is a correct step in a leader election algorithm?

easy

A. Nodes send messages to agree on the leader

B. Nodes duplicate leader roles simultaneously

C. Nodes ignore messages from others

D. Nodes randomly shut down to reduce load

Solution

1. Step 1: Recall leader election communication

   Nodes communicate by sending messages to agree on who will be leader.

2. Step 2: Match options with correct behavior

   Only sending messages to agree fits the leader election process.

3. Final Answer:

   Nodes send messages to agree on the leader -> Option A

4. Quick Check:

   Leader election = message agreement [OK]

Hint: Leader election needs message exchange between nodes [OK]

Common Mistakes:

• Thinking nodes shut down randomly
• Believing nodes ignore others' messages
• Assuming multiple leaders run at once

3. Consider a ring of 4 nodes (A, B, C, D) running a leader election where each node sends its ID clockwise. If node C has the highest ID, which node will be elected leader?

medium

A. Node B

B. Node C

C. Node A

D. Node D

Solution

1. Step 1: Understand ring leader election

   Nodes pass IDs around; the highest ID wins and becomes leader.

2. Step 2: Identify highest ID node

   Node C has the highest ID, so it will be elected leader after messages circulate.

3. Final Answer:

   Node C -> Option B

4. Quick Check:

   Highest ID node = leader [OK]

Hint: Highest ID node in ring wins leader election [OK]

Common Mistakes:

• Choosing first node instead of highest ID
• Confusing direction of message passing
• Assuming multiple leaders

4. In a leader election algorithm, a node fails to send its election message. What is the likely impact?

medium

A. All nodes become leaders simultaneously

B. The system immediately elects a new leader without delay

C. The election process may stall or fail to complete

D. The failed node automatically becomes leader

Solution

1. Step 1: Analyze message failure impact

   If a node fails to send its election message, other nodes may wait indefinitely or miss information.

2. Step 2: Understand election process dependency

   Leader election relies on message exchange; missing messages can stall or break the process.

3. Final Answer:

   The election process may stall or fail to complete -> Option C

4. Quick Check:

   Missing message = election stalls [OK]

Hint: Missing messages can stall leader election [OK]

Common Mistakes:

• Assuming instant new leader election
• Thinking all nodes become leaders
• Believing failed node becomes leader

5. You design a distributed system with 100 nodes using leader election. To improve fault tolerance, you want to avoid single leader failure. Which approach is best?

hard

A. Use a leader and backup leaders that take over if leader fails

B. Use a single leader with frequent heartbeat checks and automatic re-election

C. Elect multiple leaders simultaneously to share tasks equally

D. Avoid leader election and let all nodes act independently

Solution

1. Step 1: Understand fault tolerance needs

   Single leader failure risks system downtime; backups improve reliability.

2. Step 2: Evaluate options for fault tolerance

   Using leader plus backups allows quick failover without multiple leaders conflicting.

3. Step 3: Reject unsafe or inefficient options

   Multiple leaders cause conflicts; no leader risks coordination issues; single leader alone is risky.

4. Final Answer:

   Use a leader and backup leaders that take over if leader fails -> Option A

5. Quick Check:

   Leader + backups = fault tolerance [OK]

Hint: Leader with backups prevents single point failure [OK]

Common Mistakes:

• Electing multiple leaders causing conflicts
• Relying on single leader without backups
• Skipping leader election causing chaos