Load Balancing

Routing Algorithms

// Algorithm 1: Round-robin
// Each request goes to the next server in sequence.
// Simple. Assumes all servers are equally capable and equally loaded.
function round_robin(servers, request):
    index = request_counter % length(servers)
    request_counter += 1
    return servers[index]

// Algorithm 2: Least connections
// Each request goes to the server with fewest active connections.
// Better for heterogeneous workloads where requests have varying duration.
function least_connections(servers, request):
    return server with minimum active_connections in servers

// Algorithm 3: IP hash (sticky routing)
// Each request from the same client IP goes to the same server.
// Required when sessions are stored on the server (stateful services).
// Breaks down if client IP changes (mobile, NAT) or server fails.
function ip_hash(servers, request):
    index = hash(request.client_ip) % length(servers)
    return servers[index]

// Algorithm 4: Consistent hashing (from Book 2, Ch 15)
// Server membership changes reroute only K/N keys, not all keys.
// Used for distributed caches: same key always maps to same server,
// minimising cache invalidation when the pool changes.
function consistent_hash(ring, request):
    position = hash(request.key)
    return ring.get_node(position)  // next node clockwise on ring

Health Checks: The Feedback Loop

A load balancer without health checks is dangerous — it will continue routing to a failing server, sending requests into a black hole.

// Health check loop — runs continuously for each server
function health_check_loop(server, interval_seconds):
    while true:
        sleep(interval_seconds)
        result = probe(server, timeout=2s)
        if result == HEALTHY:
            server.state = HEALTHY
            server.consecutive_failures = 0
        else:
            server.consecutive_failures += 1
            if server.consecutive_failures >= 3:
                server.state = UNHEALTHY
                remove_from_pool(server)
                alert("Server " + server.id + " marked unhealthy")

// Probe types:
// TCP probe: can we establish a TCP connection? (Layer 4 check)
// HTTP probe: does GET /health return 200? (Layer 7 check)
// Custom probe: does the application report it is ready to serve?

// Hysteresis: re-adding a server requires N consecutive successes,
// not just one success, to prevent flapping.
function recovery_check_loop(server, interval_seconds):
    while server.state == UNHEALTHY:
        sleep(interval_seconds)
        result = probe(server, timeout=2s)
        if result == HEALTHY:
            server.consecutive_successes += 1
            if server.consecutive_successes >= 3:
                server.state = HEALTHY
                add_to_pool(server)

Avoiding the Load Balancer as a SPOF

The load balancer must not itself be a single point of failure. Two patterns:

// Pattern 1: Active-passive pair
// Primary handles all traffic. Secondary monitors primary.
// If primary fails, secondary takes over using a shared virtual IP (VIP).

function primary_health_monitor(primary, secondary, virtual_ip):
    while true:
        if primary is UNHEALTHY:
            reassign_virtual_ip(virtual_ip, to=secondary)
            secondary.state = ACTIVE
            alert("Failover: secondary now active")
        sleep(1s)

// Pattern 2: DNS-level load balancing
// Multiple A records for the same domain.
// Clients connect to different IPs.
// Simpler but DNS TTL means failover is slow (seconds to minutes).
// Used for geographic distribution, not fast failover.

// Pattern 3: Anycast routing
// Multiple servers announce the same IP prefix via BGP.
// Routers direct packets to the geographically nearest server.
// Used by CDNs and DNS providers for global scale.

Connection Draining

When a server is removed from the pool, existing connections should not be abruptly terminated:

function graceful_remove(server, drain_timeout_seconds):
    server.state = DRAINING
    // No new connections routed to this server
    // Existing connections are allowed to complete
    deadline = now() + drain_timeout_seconds
    while server.active_connections > 0 and now() < deadline:
        sleep(1s)
    // After deadline: forcibly close remaining connections
    server.state = REMOVED

Level 2 — Apply

A service has a pool of 5 servers. A load balancer uses round-robin routing. Server 3 goes down. The health check interval is 30 seconds; the unhealthy threshold is 3 consecutive failures.

1. How long does it take for server 3 to be removed from the pool? How many requests are sent to the failing server during this window? At 1,000 RPS total, how many requests fail?

2. The team reduces the health check interval to 5 seconds. What is the new failure window? What is the operational cost of more frequent health checks?

3. After server 3 is removed, traffic is distributed across 4 servers. One server was already at 80% capacity. At 1,000 RPS with round-robin, how much additional load does the 80% server receive?

Level 3 — Design

A global e-commerce platform receives 500,000 RPS at peak. The platform has data centres in 3 regions (US, EU, Asia). Users must be routed to the nearest region to minimise latency. Within each region, load must be distributed across 50 application servers.

1. Design the two-tier load balancing architecture. What handles global routing? What handles within-region distribution? Name the algorithm used at each tier.

2. A deployment requires rolling 10 servers out of service simultaneously in each region. Design the drain procedure. How does the remaining capacity change during the drain, and what is the maximum safe drain size per region without exceeding 90% capacity on remaining servers?

3. A DDoS attack generates 2,000,000 RPS from 10,000 distinct IP addresses. The platform’s capacity is 500,000 RPS. Design a rate-limiting layer that integrates with the load balancer to protect backend servers. Name every tradeoff using AT notation.

A complete answer will: (1) correctly design the two-tier architecture — Anycast DNS or GeoDNS for global routing, weighted round-robin or least-connections within each region — and compute the maximum safe drain size numerically (50 servers × 90% = 45 servers max active, so 5 can drain per region at peak load), (2) identify FM3 (resource exhaustion — 4× capacity DDoS overwhelming backend servers) and FM6 (hotspot from 10,000 attacker IPs routing to the same region) as the failure modes the rate-limiting layer must address, (3) address the AT9 tradeoff between per-IP rate limiting (precise, distributed state required) and connection-count limiting at the load balancer (coarse, stateless, but blocks legitimate users behind shared IPs), and (4) specify the state storage for rate limit counters — shared across the 50 regional servers — and the propagation mechanism.