Bird
Raised Fist0

Consensus Algorithms - Paxos and Raft Intuition for Interviews

HLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Consensus Algorithms - Paxos and Raft Intuition for Interviews
Design and understand Paxos and Raft consensus algorithms for distributed coordination
mediumDistributed CoordinationFreq: high
⚙️
Functional Requirements
  • Achieve consensus on a single value or sequence of values among distributed nodes
  • Ensure safety: no two nodes decide conflicting values
  • Guarantee liveness: system eventually reaches consensus despite failures
  • Support leader election and log replication (Raft-specific)
  • Handle node failures and network partitions gracefully
  • Provide fault tolerance with minimal performance degradation
📊
Non-Functional Requirements
  • Support clusters of 3-7 nodes for fault tolerance
  • Achieve consensus decision latency under 100ms P99 in local datacenter
  • Ensure availability of 99.99% despite node failures
  • Handle up to 10K consensus requests per second per cluster
  • Minimize network overhead to under 1MB/s per node for consensus traffic
❓
Clarifying Questions to Ask
  • What failure model should we assume? Crash-stop or Byzantine?
  • Is the consensus for single-value or multi-value (log replication)?
  • What is the expected cluster size and network environment?
  • Are we optimizing for latency, throughput, or availability?
  • Should the system support dynamic membership changes?
  • Is leader election required or can consensus be leaderless?
Out of Scope
✗ Designing a full distributed database or storage system
✗ Handling Byzantine faults or malicious nodes (focus on crash faults)
✗ Multi-datacenter or geo-replication consensus
✗ Consensus for very large clusters (hundreds of nodes)
📌
Assumptions
  • Cluster size: 5 nodes (typical for Paxos/Raft)
  • Consensus requests per client: 1000 per second
  • Average consensus message size: 200 bytes
  • Retention window irrelevant as consensus state is small (few MBs)
⚡
QPS Calculation
write qps1000 consensus requests/sec per client × 5 nodes = 1000 consensus ops/sec
peak write qpsAssuming 2x peak load = 2000 consensus ops/sec
read qpsReads are local state machine queries, ~10x writes = 10,000 reads/sec
💾
Storage Estimate
daily storageConsensus logs ~200 bytes × 2000 ops/sec × 86400 sec = 34.56 GB/day
retentionRetain logs for 7 days = 34.56 GB × 7 = 242 GB
with replicationReplication factor 3 → 242 GB × 3 = 726 GB total
🖥️
Server Estimate
consensus nodes5 nodes to tolerate 2 failures (majority quorum)
client proxies2 proxy servers to handle 2K QPS load and route requests
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |      Client Apps      |
          +----------+-----------+
                     | Consensus Requests
                     v
          +----------------------+
          |   Client Proxy Layer  |
          +----------+-----------+
                     | Forward requests
                     v
  +--------+  +--------+  +--------+  +--------+  +--------+
  | Node 1 |  | Node 2 |  | Node 3 |  | Node 4 |  | Node 5 |
  +---+----+  +---+----+  +---+----+  +---+----+  +---+----+
      |           |           |           |           |
      +-----------+-----------+-----------+-----------+
                  | Consensus Protocol Messages (Paxos/Raft)
                  v
          +----------------------+
          |  Distributed Log &   |
          |  State Machine Layer |
          +----------------------+
🧩
Components
Client Proxy Layer
Receives client consensus requests and forwards them to cluster nodes
Why thisNginx or Envoy proxies provide load balancing and request routing with low latency
Why notDirect client-to-node communication causes uneven load and complicates client logic
Consensus Nodes
Run Paxos or Raft protocol to agree on values and replicate logs
Why thisRaft provides understandable leader election and log replication; Paxos is proven for consensus
Why notZookeeper's Zab protocol is less intuitive and harder to implement correctly
Distributed Log & State Machine Layer
Persist consensus decisions and apply them to replicated state machines
Why thisWrite-ahead logs on SSDs ensure durability and fast recovery
Why notIn-memory logs risk data loss on crashes; relational DBs add latency
Network Layer
Handles reliable message passing between nodes with failure detection
Why thisgRPC with TLS provides efficient, secure RPC calls with built-in retries
Why notRaw TCP lacks built-in serialization and retry logic, increasing complexity
Leader Election Module
Coordinates leader selection to optimize log replication and reduce conflicts
Why thisRaft's randomized election timeout reduces split votes and ensures quick leader election
Why notPaxos leader election is more complex and less deterministic, increasing latency
🔄
Data Flow
1
Client Apps → Client Proxy Layer
Send consensus request (e.g., propose value)
Proxies balance load and simplify client logic
2
Client Proxy Layer → Consensus Leader Node
Forward request to current leader
Leader coordinates consensus rounds
3
Leader Node → Follower Nodes
Send AppendEntries (Raft) or Prepare/Accept (Paxos) messages
Replicate proposed value to majority
4
Follower Nodes → Leader Node
Send acknowledgments or acceptances
Leader waits for majority quorum
5
Leader Node → Client Proxy Layer
Commit consensus decision and respond success
Leader applies value to state machine and confirms to client
6
Leader Node → Distributed Log & State Machine Layer
Persist committed entries and apply state changes
Ensures durability and consistency
7
Consensus Nodes → Leader Election Module
Trigger leader election on failure detection
Maintains availability during node failures

Practice

(1/5)
1. In the News Feed system, at step 4 the Delivery Worker reads from the fan-out queue to push updates to followers. What happens if the follower's cache entry for the feed is expired at this step?
easy
A. The Delivery Worker fetches the latest feed snapshot from the database before pushing
B. The Delivery Worker sends a stale cached feed to the follower
C. The Delivery Worker retries the message later without updating the cache
D. The Delivery Worker skips sending the update and marks it as delivered

Solution

  1. Step 1: Trace Delivery Worker decision at Step 4 -- follower cache TTL expired

    If the cache is expired, the Delivery Worker must fetch fresh data to ensure the follower receives the latest feed snapshot.

  2. Step 2: Evaluate other options

    Skipping (A) causes missed updates; retrying without cache update (C) delays delivery; sending stale data (D) violates freshness guarantees.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Expired cache triggers DB fetch for fresh feed [check]
Hint: Expired cache triggers DB fetch before delivery [check]
Common Mistakes:
2. A web API needs to enforce a rate limit of 100 requests per minute per user, allowing bursts but avoiding sudden resets at minute boundaries. Which rate limiting approach best fits this requirement?
easy
A. Fixed window counter, resetting counts exactly every minute
B. Sliding window counter, tracking requests over the last 60 seconds continuously
C. Token bucket with fixed refill intervals every minute
D. Leaky bucket with fixed drain rate per minute

Solution

  1. Step 1: Identify burst tolerance and smooth rate enforcement

    Fixed window counters reset abruptly at minute boundaries, causing spikes. Token and leaky buckets enforce steady rates but may not track exact recent usage.

  2. Step 2: Sliding window counters track requests continuously over the last 60 seconds, allowing bursts without sudden resets

    Sliding window counters provide smoother rate limiting by considering recent activity, avoiding boundary effects.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Sliding window smooths rate limits over time, avoiding fixed window spikes [check]
Hint: Sliding window smooths counts over time, fixed resets abruptly [check]
Common Mistakes:
3. In the metrics collection system, at step 4 the Aggregation Worker receives a batch of metrics from Kafka. What happens if the Aggregation Worker detects a missing metric timestamp in this batch?
easy
A. The Aggregation Worker skips the missing timestamp metric and processes the rest of the batch
B. The Aggregation Worker inserts a default timestamp and continues processing
C. The Aggregation Worker pauses processing and waits for manual intervention
D. The Aggregation Worker discards the entire batch and requests a retry from Kafka

Solution

  1. Step 1: Aggregation Worker error handling

    Discarding entire batch (A) or pausing (C) causes unnecessary delays; default timestamps (D) risk data corruption.

  2. Step 2: Skipping invalid metrics

    Skipping only the invalid metric preserves throughput and data integrity for valid metrics.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Skip invalid metrics, process valid batch entries [check]
Hint: Skip bad metrics, keep batch flowing smoothly [check]
Common Mistakes:
4. For a CDN serving frequently updated dynamic content, which origin content delivery strategy is best to ensure freshness without overloading the origin server?
medium
A. Pull model where edge nodes fetch content from origin on cache miss with TTL-based caching
B. Push model where origin proactively sends all content updates to edge nodes
C. Push model with edge nodes polling origin periodically for updates
D. Pull model with edge nodes never caching content and always fetching from origin

Solution

  1. Step 1: Analyze push vs pull for dynamic content freshness

    Push model can overload origin with frequent updates; polling adds unnecessary load.

  2. Step 2: Evaluate pull with TTL caching

    Pull with TTL balances freshness and origin load by caching briefly and refreshing on expiry.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Pull with TTL caching balances freshness and origin load [check]
Hint: Pull with TTL balances freshness and load [check]
Common Mistakes:
5. Without the retry queue component, what exactly breaks in the webhook delivery system when a subscriber's endpoint is temporarily unreachable?
medium
A. The system immediately drops the event, causing permanent loss
B. The Delivery Worker blocks sending other events to that subscriber until recovery
C. The event is lost silently, and the subscriber never receives it
D. The system continues sending events out of order, violating ordering guarantees

Solution

  1. Step 1: Understand retry queue role

    The retry queue buffers failed deliveries to preserve order by retrying later.

  2. Step 2: Trace failure without retry queue

    Without it, subsequent events may be sent immediately, causing out-of-order delivery.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    No retry queue -> out-of-order delivery possible [check]
Hint: No retry queue -> ordering breaks on failures [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard