Requirements

Functional Requirements:

• Distribute incoming traffic across backend servers using round-robin, least connections, weighted round-robin, and IP hash algorithms.
• Perform active health checks using periodic HTTP/TCP probes with configurable intervals and thresholds, and passive health checks by monitoring error responses and timeouts.
• Use a distributed cache (Redis) to map session IDs or client IPs to backend servers for session persistence.
• Offload SSL/TLS processing to the load balancer, decrypting incoming HTTPS traffic and forwarding it as HTTP to the backend.

Non-Functional Requirements:

• List the key non-functional requirements (eg low latency, scalability, reliability, etc.)...
• The system should be low latency
• The system should be avalible 99.9 percent of the time
• The system should have strong consistency
• the system should be scalable to a lot of machines

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

There are 1 million requests per second at peak, each node can handle ~100K requests/sec (limited by NIC throughput and CPU for L7 parsing). Need ~10-12 LB nodes at peak, with headroom for bursts.

• Concurrent connections: Each LB node maintains up to 100K concurrent TCP connections (tuned via kernel parameters: somaxconn, file descriptors). At 1M total connections, 10 nodes suffice. WebSocket connections are long-lived and consume more memory, plan for 50K WebSocket + 50K HTTP per node.
• Health check traffic: 10 LB nodes each probing 500 backend servers every 5 seconds = 1,000 probes/sec total. Negligible compared to production traffic.

• Inbound: Average request size 2KB x 1M/sec = 2GB/sec. A 10 Gbps NIC per LB node handles ~1.25GB/sec, so 2 nodes worth of ingress bandwidth. With 10 nodes, each handles 200MB/sec, well within NIC capacity.
• Outbound: Average response size 10KB x 1M/sec = 10GB/sec total. Each LB node forwards 1GB/sec outbound. 10 Gbps NICs handle this, but response-heavy workloads (video thumbnails, large JSON) may require 25 Gbps NICs.

Round-robin: O(1), advance a pointer in a circular array. ~1μs per decision. Least connections: O(log n), extract-min from a heap of n servers. With 500 servers, ~9 comparisons. ~5μs per decision. IP hash: O(1), compute hash, modulo server count. ~2μs per decision. Consistent hashing: O(log n), binary search on the hash ring. ~5μs per decision.

All algorithms add negligible overhead compared to network round-trip time (typically 0.5-2ms within a datacenter).

Why These Numbers Matter

The 1M req/sec throughput requirement drives the choice of a horizontally scalable, stateless LB design, no single box can handle this alone. The sub-millisecond routing overhead justifies in-memory data structures (arrays, heaps, hash maps) rather than database lookups for every request. The 100K connections per node limit is a kernel-level constraint (file descriptors, socket buffers) that determines fleet size.

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

POST /api/servers:

Register a new backend server. Body: address (IP:port), weight (for weighted algorithms), metadata (datacenter, version, tags). The server enters a "pending" state, receives health checks, and is added to the routing pool only after passing the health threshold. Returns server_id.

DELETE /api/servers/server_id:

Remove a server from the pool. Triggers connection draining: no new requests routed, in-flight requests complete (up to drain_timeout seconds), then full removal. Returns immediately with drain status.

GET /api/servers: List all backend servers with real-time status: health (healthy/unhealthy/draining), active_connections, total_requests, error_rate, weight, last_health_check timestamp. Paginated. Filterable by status and tags.

PUT /api/servers/:server_id: Update server configuration: weight, metadata, enabled/disabled. Weight changes take effect on the next routing decision. Disabling a server triggers connection draining.

Configuration

PUT /api/config/algorithm: Switch the active load balancing algorithm. Body: algorithm (round_robin, least_connections, weighted_round_robin, ip_hash, consistent_hash). Takes effect immediately, the next routing decision uses the new algorithm. No restart required.

PUT /api/config/health: Update health check parameters: interval_seconds, timeout_seconds, unhealthy_threshold (consecutive failures), healthy_threshold (consecutive successes for recovery). Applied to all servers on the next check cycle.

GET /api/config: Return current configuration: active algorithm, health check parameters, drain timeout, session persistence settings.

Monitoring

GET /api/metrics: Real-time metrics: total_requests_per_sec, active_connections, error_rate, average_latency_ms, requests_by_server (breakdown). Time-series data for the last hour at 10-second granularity. Used by dashboards and alerting.

GET /api/health: Load balancer's own health: is this LB node healthy, what's its role (primary/standby), how many backend servers are healthy vs total. Used by upstream monitoring (the system that monitors the monitor).

Session Management

GET /api/sessions?client_ip=1.2.3.4: Look up current session mapping for a client. Returns the backend server_id, session creation time, and TTL remaining. Used for debugging "why is this user stuck on a slow server" issues.

DELETE /api/sessions/:session_id: Manually evict a session mapping. The next request from this client will be routed algorithmically to a new server. Useful when a backend server is degraded but not yet flagged by health checks.

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

SSL Termination Module: The entry point. Decrypts incoming HTTPS using the configured certificate. Outputs plain HTTP to the routing pipeline. For L4 (TCP passthrough) mode, this module is bypassed, traffic is forwarded as-is. Hardware-accelerated TLS (Intel QAT, custom ASICs) handles 10K+ handshakes/sec on high-end LBs.

Session Affinity Layer: Before algorithmic routing, check Redis for an existing session mapping. If the request carries a session cookie or the client IP has a mapping, route directly to the mapped backend. If no mapping exists, fall through to the Traffic Distribution Module. On cache miss, the chosen server's ID is written back to Redis with a TTL.

Traffic Distribution Module: The algorithm engine. Maintains in-memory data structures for the active algorithm (circular array for round-robin, min-heap for least connections, hash ring for consistent hashing). Selects a backend server for each request. The algorithm is a pluggable strategy, swappable at runtime via the configuration API.

Health Monitor: Runs in a separate thread/process. Performs active health checks (HTTP GET /health every 5 seconds per server) and passive monitoring (tracking 5xx rates from real traffic). Publishes status changes to Redis. All LB nodes subscribe and update their local server pools. When a server transitions to "unhealthy," it's immediately removed from the routing data structure.

Connection Manager: Manages TCP connection pools to backend servers. Reuses persistent connections (HTTP keep-alive) to avoid the overhead of TCP handshake + TLS handshake per request. Tracks active connections per server for the least-connections algorithm.

API Server: Exposes the management and monitoring REST API. Runs on a separate port (e.g., :8443) from the traffic port (:443) to prevent management operations from competing with production traffic for resources.

Redis (Shared State Store): Session mappings, health statuses, and server metadata shared across all LB nodes. Not on the critical routing path, only consulted for session affinity lookups and state synchronization.

Let's trace a request from a returning user with a session cookie:

1. Client sends HTTPS request: GET /api/dashboard with cookie lb_session=abc123. Request arrives at the load balancer's VIP (virtual IP address) on port 443.
2. SSL termination: The TLS module decrypts the request using the server's private key. Outputs plain HTTP. Added latency: ~0.1ms (session resumption) to ~5ms (full handshake for new connections).
3. Session affinity check: LB extracts lb_server=backend-7 from the cookie. The server ID is embedded directly in the cookie, no Redis lookup needed. Route directly to backend-7, skipping algorithmic selection. (If the cookie contains an opaque session ID instead, the LB queries Redis: GET session:{id} → backend-7. This is slower but allows server-side session invalidation.)
4. Connection forwarding: LB picks a persistent connection from the pool to backend-7 (HTTP keep-alive). Forwards the request with added headers: X-Forwarded-For: {client_ip}, X-Forwarded-Proto: https, X-Request-Id: {uuid}.
5. Backend processes request: Backend-7 processes the request and returns a response (200 OK with JSON body).
6. Response forwarded to client: LB passes the response back to the client over the existing TLS connection. Total LB overhead: ~0.5ms (TLS + session resolution + forwarding).

First Request (No Session) Flow

1. Steps 1-2 same as above.
2. Session affinity check: No session cookie present. Redis lookup returns nil.
3. Algorithm selection: LB invokes the active algorithm (say, least connections). Min-heap returns backend-3 (fewest active connections).
4. Session creation: LB generates a session ID, writes SET session:{new_id} backend-3 EX 1800 to Redis, and injects a Set-Cookie: lb_session={new_id} header into the response.
5. From here, connection forwarding, backend processing, and response forwarding proceed as in the standard flow (steps 4-6 above).

Codemia

1. Problem

Editorial

Design a Load Balancer

System requirements

Functional

A load balancer is a network appliance that distributes incoming traffic across multiple backend servers so that no single server becomes a bottleneck. It sits between clients and your server fleet, making routing decisions on every request. Think Nginx, HAProxy, or AWS ALB.

Traffic distribution:

• Route incoming requests to backend servers using configurable algorithms, round-robin, least connections, weighted round-robin, IP hash, or consistent hashing
• Support dynamic algorithm switching without restart, an operator can change from round-robin to least-connections during a traffic spike via a management API
• Handle both L4 (TCP/UDP transport layer) and L7 (HTTP application layer) routing. L4 is faster but content-blind. L7 enables path-based routing, header inspection, and cookie-based session affinity

Health monitoring:

• Active health checks, periodically probe each backend with HTTP GET or TCP connect. Configurable interval (e.g., every 5 seconds), timeout (2 seconds), and failure threshold (3 consecutive failures before marking unhealthy)
• Passive health checks, monitor real traffic for error spikes (5xx rates, connection resets). If a server's error rate exceeds a threshold, mark it unhealthy immediately without waiting for the next active probe
• Graceful re-addition, when a failed server recovers, gradually ramp traffic back (10% → 50% → 100%) to avoid overwhelming it

Session persistence:

• Sticky sessions, route requests with the same session token or client IP to the same backend. Required for stateful applications where session data lives in server memory
• Session mappings stored in Redis with TTL. If the target server fails, the mapping is evicted and the next request is routed algorithmically to a new server
• Cookie injection (preferred), the LB inserts a cookie containing the backend server ID directly (e.g., lb_server=backend-7). Subsequent requests are routed by reading the cookie, no Redis lookup needed. Redis is used only as a fallback for cookie-less clients or when server-side session invalidation is required

Rate limiting:

• Per-client rate limiting via token bucket or sliding window, enforced at the LB before requests reach backends. Protects backend servers from abusive clients and implements API quotas. Configurable per endpoint (e.g., 100 req/sec for /api/search, 10 req/sec for /api/login). Excess requests receive 429 Too Many Requests

SSL/TLS termination:

• Decrypt HTTPS at the load balancer, forward plain HTTP to backends. Centralizes certificate management and offloads CPU-intensive TLS handshakes from backend servers

Non-Functional

• Throughput: Handle 1M+ requests/sec with sub-millisecond routing overhead. The LB must not become the bottleneck. At 100K concurrent connections per LB node, a cluster of 10 nodes handles 1M connections.
• Latency: Add less than 1ms of latency per request. Routing decisions (algorithm lookup, session check) must execute in microseconds. At L4, hardware-accelerated LBs add under 100μs.
• High availability: The LB itself must not be a single point of failure. Active-passive or active-active pairs with sub-second failover via virtual IP (VIP) takeover. Zero-downtime deploys of LB configuration changes.
• Scalability: Horizontally scalable. As traffic grows, add more LB nodes behind DNS round-robin or anycast. Each node is stateless (session state in Redis), so adding nodes is trivial.

Capacity estimation

Traffic

• Requests: 1M requests/sec peak across the entire fleet. Each LB node handles ~100K requests/sec (limited by NIC throughput and CPU for L7 parsing). Need ~10-12 LB nodes at peak, with headroom for bursts.
• Concurrent connections: Each LB node maintains up to 100K concurrent TCP connections (tuned via kernel parameters: somaxconn, file descriptors). At 1M total connections, 10 nodes suffice. WebSocket connections are long-lived and consume more memory, plan for 50K WebSocket + 50K HTTP per node.
• Health check traffic: 10 LB nodes each probing 500 backend servers every 5 seconds = 1,000 probes/sec total. Negligible compared to production traffic.

Bandwidth

• Inbound: Average request size 2KB x 1M/sec = 2GB/sec. A 10 Gbps NIC per LB node handles ~1.25GB/sec, so 2 nodes worth of ingress bandwidth. With 10 nodes, each handles 200MB/sec, well within NIC capacity.
• Outbound: Average response size 10KB x 1M/sec = 10GB/sec total. Each LB node forwards 1GB/sec outbound. 10 Gbps NICs handle this, but response-heavy workloads (video thumbnails, large JSON) may require 25 Gbps NICs.

Routing Decision Overhead

Round-robin: O(1), advance a pointer in a circular array. ~1μs per decision. Least connections: O(log n), extract-min from a heap of n servers. With 500 servers, ~9 comparisons. ~5μs per decision. IP hash: O(1), compute hash, modulo server count. ~2μs per decision. Consistent hashing: O(log n), binary search on the hash ring. ~5μs per decision.

All algorithms add negligible overhead compared to network round-trip time (typically 0.5-2ms within a datacenter).

Why These Numbers Matter

The 1M req/sec throughput requirement drives the choice of a horizontally scalable, stateless LB design, no single box can handle this alone. The sub-millisecond routing overhead justifies in-memory data structures (arrays, heaps, hash maps) rather than database lookups for every request. The 100K connections per node limit is a kernel-level constraint (file descriptors, socket buffers) that determines fleet size.

API design

Server Pool Management

POST /api/servers: Register a new backend server. Body: address (IP:port), weight (for weighted algorithms), metadata (datacenter, version, tags). The server enters a "pending" state, receives health checks, and is added to the routing pool only after passing the health threshold. Returns server_id.

DELETE /api/servers/:server_id: Remove a server from the pool. Triggers connection draining: no new requests routed, in-flight requests complete (up to drain_timeout seconds), then full removal. Returns immediately with drain status.

GET /api/servers: List all backend servers with real-time status: health (healthy/unhealthy/draining), active_connections, total_requests, error_rate, weight, last_health_check timestamp. Paginated. Filterable by status and tags.

PUT /api/servers/:server_id: Update server configuration: weight, metadata, enabled/disabled. Weight changes take effect on the next routing decision. Disabling a server triggers connection draining.

Configuration

PUT /api/config/algorithm: Switch the active load balancing algorithm. Body: algorithm (round_robin, least_connections, weighted_round_robin, ip_hash, consistent_hash). Takes effect immediately, the next routing decision uses the new algorithm. No restart required.

PUT /api/config/health: Update health check parameters: interval_seconds, timeout_seconds, unhealthy_threshold (consecutive failures), healthy_threshold (consecutive successes for recovery). Applied to all servers on the next check cycle.

GET /api/config: Return current configuration: active algorithm, health check parameters, drain timeout, session persistence settings.

Monitoring

GET /api/metrics: Real-time metrics: total_requests_per_sec, active_connections, error_rate, average_latency_ms, requests_by_server (breakdown). Time-series data for the last hour at 10-second granularity. Used by dashboards and alerting.

GET /api/health: Load balancer's own health: is this LB node healthy, what's its role (primary/standby), how many backend servers are healthy vs total. Used by upstream monitoring (the system that monitors the monitor).

Session Management

GET /api/sessions?client_ip=1.2.3.4: Look up current session mapping for a client. Returns the backend server_id, session creation time, and TTL remaining. Used for debugging "why is this user stuck on a slow server" issues.

DELETE /api/sessions/:session_id: Manually evict a session mapping. The next request from this client will be routed algorithmically to a new server. Useful when a backend server is degraded but not yet flagged by health checks.

Database design

Storage Architecture

A load balancer is unique among system design problems: it has almost no persistent storage needs. The critical data (routing decisions, session mappings, health status) changes on every request and must be accessed in microseconds. This means in-memory data structures and Redis, not PostgreSQL.

In-memory (on the LB process): The server pool (array/heap of backend server entries), algorithm state (round-robin pointer, connection counts), and the active configuration. This is the hot path, every request reads this data. It's rebuilt from Redis on LB startup.

Redis (shared state across LB nodes): Session affinity mappings (session_id → server_id, with TTL), health status per server (healthy/unhealthy/draining), server pool metadata (address, weight, tags). Redis is the source of truth that multiple LB nodes share. If an LB node restarts, it rebuilds its in-memory state from Redis.

Persistent store (PostgreSQL or config file): LB configuration (algorithm, health check parameters, SSL certs), server pool definitions, and historical metrics for dashboards. Written rarely, read on startup or config change. Not on the request hot path.

Key Data Structures

Server entry:

Round-robin state: Circular array of healthy server_ids. Atomic integer pointer incremented on each request: next = servers[counter.getAndIncrement() % servers.length].

Least-connections state: Min-heap (priority queue) keyed on active_connections. Extract-min returns the least-loaded server. Connection start: increment count, re-heapify. Connection end: decrement count, re-heapify.

Session mapping (in Redis):

SET session:{session_id} {server_id} EX 1800: Maps a session to a backend server with a 30-minute TTL. On each request from this session, the TTL is refreshed. Note: Redis lookup on every request adds ~0.5ms of latency. Production LBs prefer cookie-based routing (server ID embedded in cookie, zero Redis lookups). Redis is used as a fallback for cookie-less clients or when server-side invalidation is needed (e.g., evicting sessions when a server fails).

Health status (in Redis):

HSET server:{server_id} status healthy last_check 1709312400: Per-server health status, updated by the health monitor, read by all LB nodes.

Why Not a Traditional Database?

The LB makes a routing decision on every single request, at 1M req/sec, that's 1M reads/sec from the routing data structure. A PostgreSQL query with network round-trip takes ~1ms. That would add 1ms to every request and require a database capable of 1M reads/sec. In-memory data structures accessed in microseconds are the only viable option. Redis is used only for shared state (session mappings, health updates), and even Redis is not on the critical path for algorithm selection.

High-level design

Load balancer high-level architecture with SSL termination, routing, and health monitoring

Architecture Overview

SSL Termination Module: The entry point. Decrypts incoming HTTPS using the configured certificate. Outputs plain HTTP to the routing pipeline. For L4 (TCP passthrough) mode, this module is bypassed, traffic is forwarded as-is. Hardware-accelerated TLS (Intel QAT, custom ASICs) handles 10K+ handshakes/sec on high-end LBs.

Session Affinity Layer: Before algorithmic routing, check Redis for an existing session mapping. If the request carries a session cookie or the client IP has a mapping, route directly to the mapped backend. If no mapping exists, fall through to the Traffic Distribution Module. On cache miss, the chosen server's ID is written back to Redis with a TTL.

Traffic Distribution Module: The algorithm engine. Maintains in-memory data structures for the active algorithm (circular array for round-robin, min-heap for least connections, hash ring for consistent hashing). Selects a backend server for each request. The algorithm is a pluggable strategy, swappable at runtime via the configuration API.

Health Monitor: Runs in a separate thread/process. Performs active health checks (HTTP GET /health every 5 seconds per server) and passive monitoring (tracking 5xx rates from real traffic). Publishes status changes to Redis. All LB nodes subscribe and update their local server pools. When a server transitions to "unhealthy," it's immediately removed from the routing data structure.

Connection Manager: Manages TCP connection pools to backend servers. Reuses persistent connections (HTTP keep-alive) to avoid the overhead of TCP handshake + TLS handshake per request. Tracks active connections per server for the least-connections algorithm.

API Server: Exposes the management and monitoring REST API. Runs on a separate port (e.g., :8443) from the traffic port (:443) to prevent management operations from competing with production traffic for resources.

Redis (Shared State Store): Session mappings, health statuses, and server metadata shared across all LB nodes. Not on the critical routing path, only consulted for session affinity lookups and state synchronization.

Key Insight

The load balancer is structured as a sequential pipeline (SSL termination, session lookup, algorithm selection, forwarding) rather than a monolithic router. This pipeline design allows each stage to be optimized independently. You can hardware-accelerate SSL, swap routing algorithms at runtime, or adjust health check parameters without touching the other stages.

Why This Separation?

The SSL termination, session lookup, and algorithm selection form a pipeline: each request flows through them sequentially, each step adding microseconds. Separating them into modules allows independent optimization: hardware-accelerate SSL without touching the routing code, swap algorithms without affecting session logic, update health check parameters without restarting the traffic pipeline.

Interview Tip

In an interview, emphasize that the health monitor runs in a separate thread from the routing path. A health probe to a dying server might block for 4 seconds waiting for a timeout. If this ran on the routing thread, 400K requests would stall. This separation is a concrete example of isolating slow I/O from the fast path.

Level Expectations

Mid-level: explain the pipeline stages (SSL termination, session affinity, algorithm routing) and why the health monitor runs separately.

Senior: compare L4 vs L7 load balancing with concrete use cases (L4 for database connections, L7 for path-based microservice routing) and explain consistent hashing vs modulo hashing.

Staff: design the multi-datacenter deployment with GSLB, analyze split-brain scenarios in active-active failover, and quantify the performance tradeoffs of DSR vs full proxy mode.

Request flows

Standard HTTP Request Flow

Request routing through SSL termination, session check, and algorithm selection

Let's trace a request from a returning user with a session cookie:

1. Client sends HTTPS request: GET /api/dashboard with cookie lb_session=abc123. Request arrives at the load balancer's VIP (virtual IP address) on port 443.
2. SSL termination: The TLS module decrypts the request using the server's private key. Outputs plain HTTP. Added latency: ~0.1ms (session resumption) to ~5ms (full handshake for new connections).
3. Session affinity check: LB extracts lb_server=backend-7 from the cookie. The server ID is embedded directly in the cookie, no Redis lookup needed. Route directly to backend-7, skipping algorithmic selection. (If the cookie contains an opaque session ID instead, the LB queries Redis: GET session:{id} → backend-7. This is slower but allows server-side session invalidation.)
4. Connection forwarding: LB picks a persistent connection from the pool to backend-7 (HTTP keep-alive). Forwards the request with added headers: X-Forwarded-For: {client_ip}, X-Forwarded-Proto: https, X-Request-Id: {uuid}.
5. Backend processes request: Backend-7 processes the request and returns a response (200 OK with JSON body).
6. Response forwarded to client: LB passes the response back to the client over the existing TLS connection. Total LB overhead: ~0.5ms (TLS + session resolution + forwarding).

First Request (No Session) Flow

1. Steps 1-2 same as above.
2. Session affinity check: No session cookie present. Redis lookup returns nil.
3. Algorithm selection: LB invokes the active algorithm (say, least connections). Min-heap returns backend-3 (fewest active connections).
4. Session creation: LB generates a session ID, writes SET session:{new_id} backend-3 EX 1800 to Redis, and injects a Set-Cookie: lb_session={new_id} header into the response.
5. From here, connection forwarding, backend processing, and response forwarding proceed as in the standard flow (steps 4-6 above).

Health Check Driven Failover

Health monitor detecting failure and removing server from routing pool

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

A load balancer is unique among system design problems: it has almost no persistent storage needs. The critical data (routing decisions, session mappings, health status) changes on every request and must be accessed in microseconds. This means in-memory data structures and Redis, not PostgreSQL.

In-memory (on the LB process): The server pool (array/heap of backend server entries), algorithm state (round-robin pointer, connection counts), and the active configuration. This is the hot path, every request reads this data. It's rebuilt from Redis on LB startup.

Redis (shared state across LB nodes): Session affinity mappings (session_id → server_id, with TTL), health status per server (healthy/unhealthy/draining), server pool metadata (address, weight, tags). Redis is the source of truth that multiple LB nodes share. If an LB node restarts, it rebuilds its in-memory state from Redis.

Persistent store (PostgreSQL or config file): LB configuration (algorithm, health check parameters, SSL certs), server pool definitions, and historical metrics for dashboards. Written rarely, read on startup or config change. Not on the request hot path.

Server entry:

Round-robin state: Circular array of healthy server_ids. Atomic integer pointer incremented on each request: next = servers[counter.getAndIncrement() % servers.length].

Least-connections state: Min-heap (priority queue) keyed on active_connections. Extract-min returns the least-loaded server. Connection start: increment count, re-heapify. Connection end: decrement count, re-heapify.

Session mapping (in Redis):

SET session:{session_id} {server_id} EX 1800: Maps a session to a backend server with a 30-minute TTL. On each request from this session, the TTL is refreshed. Note: Redis lookup on every request adds ~0.5ms of latency. Production LBs prefer cookie-based routing (server ID embedded in cookie, zero Redis lookups). Redis is used as a fallback for cookie-less clients or when server-side invalidation is needed (e.g., evicting sessions when a server fails).

Health status (in Redis):

HSET server:{server_id} status healthy last_check 1709312400: Per-server health status, updated by the health monitor, read by all LB nodes.

Why Not a Traditional Database?

The LB makes a routing decision on every single request, at 1M req/sec, that's 1M reads/sec from the routing data structure. A PostgreSQL query with network round-trip takes ~1ms. That would add 1ms to every request and require a database capable of 1M reads/sec. In-memory data structures accessed in microseconds are the only viable option. Redis is used only for shared state (session mappings, health updates), and even Redis is not on the critical path for algorithm selection.

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

This is the heart of the load balancer. The algorithm must make correct routing decisions at 100K req/sec per node with microsecond overhead, while adapting to changing server health and capacity.

Round-robin: The simplest algorithm. Servers stored in a circular array. An atomic counter advances on each request: server = pool[counter.incrementAndGet() % pool.size()]. O(1), no state beyond the counter. Weakness: treats all servers as equal. A 4-core server and a 32-core server get the same traffic, overloading the smaller one.

Weighted round-robin: Each server has a weight proportional to capacity. A server with weight 3 gets 3x the traffic of weight 1. Naive implementation: expand the circular array, server A (weight 3) appears 3 times, server B (weight 1) appears once. But this creates burst patterns: A gets 3 consecutive requests before B gets 1. Production LBs (Nginx) use smooth weighted round-robin: each server has a running "current weight" that's incremented by its configured weight on each cycle. The server with the highest current weight is selected, then its current weight is decremented by the total weight. This interleaves requests (A, A, B, A for 3:1 weights) instead of bursting. Complexity: O(n) per decision (scan all servers), O(n) memory.

Least connections: Route to the server with fewest active connections. Data structure: either a min-heap (O(log n) per decision) or an unsorted array with linear scan (O(n) per decision, but cache-friendly for small n). Connection counts updated atomically on request start (increment) and request completion (decrement). Adapts naturally to slow servers, a server processing requests slowly accumulates connections and receives fewer new ones.

IP hash / Consistent hashing: hash(client_ip) % N for simple modulo, or a hash ring with virtual nodes for consistent hashing. Consistent hashing places servers at positions on a circular hash space. Each client IP hashes to a position, and the nearest server clockwise handles it. Adding/removing a server remaps only ~1/N of clients. Virtual nodes (each server mapped to 100-200 positions) prevent uneven distribution.

Power of two choices: A hybrid approach: randomly pick two servers, then route to the one with fewer connections. Achieves O(1) per decision (no heap, no scan) while avoiding the worst-case load imbalance of pure random. Mathematically proven to reduce max load from O(log n / log log n) to O(log log n), an exponential improvement. Used by Envoy proxy's default algorithm. Particularly effective at scale where maintaining a global min-heap becomes a contention bottleneck.

Key Insight

Power of two choices achieves near-optimal load distribution with O(1) overhead by picking just two random servers and routing to the less loaded one. This avoids the contention of a global min-heap while providing an exponential improvement over pure random selection. It is the default algorithm in Envoy proxy for good reason.

Why least connections is preferred for heterogeneous workloads:

Consider a pool with a fast server (50ms avg response) and a slow server (200ms avg response). Round-robin sends equal traffic to both. The slow server's connection count climbs (requests arrive faster than they complete), while the fast server's stays low. Least connections notices this immediately, new requests go to the fast server until connection counts equalize. It's a self-balancing feedback loop.

L4 vs L7 Load Balancing

L4 transport-layer routing vs L7 application-layer content-based routing

L4 (Transport Layer): Routes based on IP addresses and TCP/UDP port numbers. Doesn't inspect packet contents. Methods: NAT (rewrite destination IP), DSR (Direct Server Return, server responds directly to client, bypassing LB on the return path), or IP tunneling. Extremely fast, can be done in hardware or kernel space (IPVS, DPDK). Used for: database connections, game servers, any protocol that isn't HTTP.

L7 (Application Layer): Fully parses HTTP requests. Can route based on URL path (/api/* → API servers, /static/* → CDN), HTTP headers (A/B testing via custom headers), cookies (session affinity), and even request body (GraphQL query routing). Much more flexible but adds parsing overhead (1-5ms for large requests). Used for: web applications, API gateways, microservices routing.

Common Pitfall

Do not default to L7 load balancing for all traffic. L7 adds 1-5ms of HTTP parsing overhead per request. For non-HTTP protocols (database connections, game servers, raw TCP) or when you do not need content-based routing, L4 is significantly faster and can be done in kernel space with near-zero latency.

DSR (Direct Server Return): A powerful L4 optimization. The LB forwards the request to the backend, but the backend responds directly to the client (not through the LB). The LB only handles inbound traffic, cutting its bandwidth requirement in half. Used by high-traffic LBs where response size >> request size. Limitation: the LB can't modify responses, breaking features like response header injection and content compression.

Connection Draining

Graceful server removal with connection draining during rolling deploy

When a server is removed (maintenance, deploy, unhealthy):

1. Mark server as "draining", removed from algorithm selection, but existing connections continue.
2. Wait for in-flight requests to complete (configurable timeout, default 30s).
3. For WebSocket connections: send a close frame with a code indicating "server going away." Clients should reconnect (the LB will route to a different server).
4. After timeout: forcefully close any remaining connections. Server fully removed.

During rolling deploys: New version servers are added and health-checked first. Then old version servers are drained one at a time. At no point is capacity reduced below the minimum needed for current traffic. The deploy is "zero downtime" from the client's perspective.

Level Expectations

Mid-level: compare round-robin, weighted round-robin, and least connections with concrete examples of when each is appropriate.

Senior: explain the power-of-two-choices algorithm, design connection draining for zero-downtime deploys, and analyze L4 vs L7 tradeoffs.

Staff: design the consistent hash ring with virtual nodes, handle hot spots, and explain why gRPC requires L7 or client-side load balancing due to HTTP/2 multiplexing.