Gossip protocol in HLD - System Design Exercise

Design: Gossip Protocol System

Design focuses on the gossip protocol mechanism for state dissemination among nodes. Out of scope are the specific application data models and security mechanisms like encryption.

Functional Requirements

FR1: Nodes in a distributed system must share state updates efficiently.

FR2: Each node should periodically exchange information with a few random peers.

FR3: The system should ensure eventual consistency of data across all nodes.

FR4: The protocol must handle node failures and network partitions gracefully.

FR5: Updates should propagate quickly with minimal message overhead.

Non-Functional Requirements

NFR1: The system should scale to at least 10,000 nodes.

NFR2: Message latency for update propagation should be under 5 seconds for 90% of nodes.

NFR3: The system must tolerate up to 10% node failures without losing data consistency.

NFR4: Network bandwidth usage should be optimized to avoid flooding.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Node communication module

Peer selection algorithm

Message serialization and compression

Failure detection mechanism

State reconciliation logic

Design Patterns

Epidemic algorithms

Anti-entropy synchronization

Push, pull, and push-pull gossip styles

Vector clocks or version vectors for conflict resolution

Reference Architecture

          +-------------------+          
          |      Node A       |          
          |  +-------------+  |          
          |  | Gossip     |  |          
          |  | Protocol   |  |          
          |  +-------------+  |          
          +---------+---------+          
                    |                    
          Gossip messages over TCP/UDP  
                    |                    
          +---------+---------+          
          |      Node B       |          
          |  +-------------+  |          
          |  | Gossip     |  |          
          |  | Protocol   |  |          
          |  +-------------+  |          
          +-------------------+          
                    .                    
                    .                    
                    .                    
          +-------------------+          
          |      Node N       |          
          |  +-------------+  |          
          |  | Gossip     |  |          
          |  | Protocol   |  |          
          |  +-------------+  |          
          +-------------------+          

Components

Node

Any distributed system node (language agnostic)

Hosts the gossip protocol logic and application state.

Gossip Protocol Module

Custom implementation using TCP/UDP sockets

Handles periodic exchange of state updates with selected peers.

Peer Selection Algorithm

Randomized selection logic

Chooses a small subset of nodes to gossip with each cycle.

Failure Detector

Heartbeat or timeout-based mechanism

Detects unreachable or failed nodes to avoid wasting resources.

State Reconciliation Logic

Version vectors or timestamps

Merges incoming updates and resolves conflicts to maintain consistency.

Request Flow

1. 1. Each node periodically triggers a gossip cycle.

2. 2. The node selects a random subset of peers using the peer selection algorithm.

3. 3. The node sends its recent state updates to selected peers via gossip messages.

4. 4. Receiving nodes merge the updates with their local state using reconciliation logic.

5. 5. Nodes respond with their own updates if using push-pull style.

6. 6. Failure detector monitors peer responsiveness and marks unreachable nodes.

7. 7. Over multiple cycles, updates propagate to all nodes ensuring eventual consistency.

Database Schema

Not applicable as gossip protocol is a communication mechanism rather than a database schema. State data is application-specific and stored locally on each node.

Scaling Discussion

Bottlenecks

Network bandwidth saturation due to excessive gossip messages.

Slow propagation if peer selection is not well distributed.

Increased message duplication causing processing overhead.

Failure detector false positives causing unnecessary peer exclusion.

Solutions

Limit gossip message size and frequency to reduce bandwidth usage.

Use adaptive peer selection to ensure wide and random coverage.

Implement message deduplication and versioning to avoid redundant processing.

Tune failure detection timeouts and use multiple signals to improve accuracy.

Interview Tips

Time: Spend 10 minutes understanding requirements and clarifying assumptions, 20 minutes designing the architecture and data flow, 10 minutes discussing scaling and failure handling, 5 minutes summarizing.

Explain how gossip protocol achieves eventual consistency through epidemic spreading.

Discuss trade-offs between push, pull, and push-pull gossip styles.

Highlight importance of peer selection and failure detection.

Describe how version vectors help resolve conflicting updates.

Address scalability challenges and mitigation strategies.