Design a Load Balancer

Layer 4 vs Layer 7 Packet Path Walkthrough

Layer 4 Load Balancer (NAT Mode) Packet Flow:

  1. Client sends initial packet:
     Source: 198.51.100.5:4321
     Destination: 10.0.0.1:80 (Virtual IP)
     
  2. Load balancer receives packet and selects Server 2 (10.0.1.6:8080):
     Rewrites destination address from 10.0.0.1:80 to 10.0.1.6:8080 (Destination NAT)
     Rewrites the client source to 10.0.0.254:55000 (Source NAT) so the response returns through the LB
     Stores flow mapping in connection table:
       {198.51.100.5:4321, 10.0.0.1:80} -> {10.0.1.6:8080, 10.0.0.254:55000}
     Forwards packet to backend network:
       Source: 10.0.0.254:55000
       Destination: 10.0.1.6:8080
     
  3. Server 2 produces response:
     Source: 10.0.1.6:8080
     Destination: 10.0.0.254:55000
     
  4. Load balancer intercepts return packet and consults connection table:
     Reverses source and destination NAT, restoring the client-facing tuple:
       Source: 10.0.0.1:80
       Destination: 198.51.100.5:4321
     Forwards packet to client.
     
  Client Transparency:
    Client communicates only with 10.0.0.1:80 and remains unaware of the internal backend topology.
  
  Operational Trade-offs:
    Per-packet cost: Two address rewrites per packet (inbound DNAT and outbound SNAT).
    Throughput: Kernel-level routing can process millions of packets per second with appropriately tuned hardware.
    Bottleneck: The load balancer must process all inbound and outbound traffic, creating a bandwidth constraint for egress-heavy workloads such as media streaming.

Layer 4 Load Balancer (Direct Server Return / DSR Mode) Packet Flow:

  1. Client sends initial packet:
     Source: 198.51.100.5:4321
     Destination: 10.0.0.1:80 (Virtual IP)
     
  2. Load balancer receives packet and selects Server 2:
     Rewrites the Layer 2 Ethernet frame MAC address to Server 2 MAC address.
     Leaves the Layer 3 IP headers completely unmodified.
     Packet arrives at Server 2 with Destination still set to 10.0.0.1:80.
     (Server 2 must have the Virtual IP configured on a local loopback interface with ARP disabled).
     
  3. Server 2 responds DIRECTLY to the client:
     Source: 10.0.0.1:80 (Virtual IP)
     Destination: 198.51.100.5:4321
     Return packets travel across the network switch directly to the client gateway, bypassing the load balancer entirely.
     
  Operational Advantages:
    Asymmetric bandwidth optimization: In typical web traffic, incoming requests average 1 KB while outgoing responses exceed 100 KB.
    The load balancer avoids return-path processing, so in the illustrative 1 KB request vs 100 KB response mix it handles roughly 100x less response traffic than NAT mode.
    
  Network Constraints:
    Classic ARP-based DSR typically requires the load balancer and backend servers to share a Layer 2 broadcast domain.
    Routed or tunneled DSR variants can relax this constraint. DSR still depends on the load balancer for the inbound path.

Layer 7 Load Balancer (Full Application Inspection) Request Flow:

  1. Client initiates connection:
     Client conducts TLS handshake with the load balancer.
     The load balancer terminates TLS and decrypts HTTP payload.
     Parses request: GET /api/v1/users/123 with Host: api.example.com
     
  2. Load balancer evaluates application routing rules:
     Path matches prefix "/api/v1/users/*" and routes to pool "user-service".
     Least-connections algorithm selects Server 3 because it has the lowest active connection count.
     
  3. Load balancer establishes an upstream TCP connection to Server 3:
     Source: Load_Balancer_Internal_IP
     Destination: 10.0.1.7:8080
     Injects proxy headers: X-Forwarded-For: 198.51.100.5, X-Forwarded-Proto: https
     Sends proxied request over a trusted private network or an HTTPS/mTLS upstream connection.
     
  4. Server 3 processes request and replies to load balancer:
     Load balancer receives upstream HTTP response, compresses payload where configured, re-encrypts over the client TLS session, and transmits response to client.
  
  Operational Trade-offs:
    Overhead: Full TCP connection termination, TLS cryptographic decryption, and HTTP parsing on every request.
    Throughput: Approximately 100K requests per second per instance in this illustrative comparison, vs millions of packets per second for tuned Layer 4 forwarding.
    Capabilities: Enables content-based routing, header rewriting, response caching, compression, and Web Application Firewall inspection.

Connection Table Scaling

Scaling the Layer 4 NAT Connection Table:

Memory Footprint Calculation:
  At 10M concurrent connections with 128 bytes per connection state record:
  10,000,000 connections * 128 bytes = 1.28 GB RAM.
  
Connection Table Operations:
  Insert: O(1) hash table insertion upon receiving initial TCP SYN packet.
  Lookup: O(1) hash lookup per packet indexed by 5-tuple: (src_ip, dst_ip, src_port, dst_port, protocol).
  Delete: O(1) removal upon TCP FIN/RST or inactivity timeout expiry.
  
Memory Bus and Cache Pressure:
  While 1.28 GB easily fits into physical RAM, a 10M-entry hash table causes continuous CPU L1/L2/L3 cache misses under random traffic access.
  Processing 1M packets per second requires 1M random memory lookups per second, which can create memory bus pressure and CPU cache thrashing under this access pattern.
  
High-Performance Solution: DPDK and XDP:
  DPDK can bypass the operating system network stack and process raw packets in user space using poll-mode drivers.
  XDP executes very early in the Linux networking path inside the kernel, reducing per-packet overhead without being a full user-space bypass.
  Pre-allocate connection table memory within huge pages (2 MB / 1 GB pages) to reduce Translation Lookaside Buffer (TLB) misses.
  Pin worker threads to dedicated CPU cores to reduce scheduler and context-switch overhead.
  Result: Can target 10M+ packets per second on appropriately tuned commodity server hardware, depending on packet size, NIC, CPU, and rule complexity.

Connection Inactivity Timeouts:
  TCP Established state: 300 seconds is an illustrative default.
  TCP TIME_WAIT state: 120 seconds is an illustrative value and is operating-system dependent.
  UDP stream state: 30 seconds is an illustrative default.
  Aggressive timeouts reclaim table capacity quickly, but risk resetting connections for slow or idle clients.

SNAT Port Exhaustion:
  NAT mode consumes source ports for each source-IP and destination tuple. At high fan-out, use multiple source IPs or equivalent port allocation strategies and monitor available SNAT ports to avoid ephemeral-port exhaustion.

Connection Table High Availability Synchronization:
  The active load balancer replicates active connection state records to the standby node through a dedicated low-latency state replication channel.
  A production design can target synchronization for more than 99% of established connection states, but any unsynchronized flows may still reset during failover.
  Any missing connection states receive TCP RST packets, prompting clean client-side reconnection.
  Under Direct Server Return (DSR), no return connection table is maintained at the load balancer, simplifying failover mechanics while the inbound path still depends on the active node.

Maglev Lookup and Bounded Load Spillover

Maglev Lookup and Bounded Loads:

Limitations of Standard Ring Consistent Hashing:
  Standard hash rings can produce significant imbalance when a node sits after a large gap on the ring.
  For example, Server S3 might receive 40% of traffic while S1 and S2 each receive 30%.
  While adding virtual nodes improves balance, it requires 100 to 200 virtual nodes per server, increasing memory and requiring O(log N) binary searches per lookup.

Google Maglev Lookup Table Construction:
  Precompute a lookup table of prime size M, typically M = 65537 entries.
  Each backend server generates a deterministic permutation preference list across table indices:
    preference[i] = (offset + i * skip) mod M
    offset = hash1(backend_name) mod M
    skip = hash2(backend_name) mod (M - 1) + 1
    
Table Population Algorithm:
  Iterate round robin through all backend servers, allowing each server to claim its next preferred unoccupied table index until all M slots are filled:
    Iteration 0: Backend A claims its highest preference available slot.
    Iteration 1: Backend B claims its highest preference available slot.
    Iteration 2: Backend C claims its highest preference available slot.
    Continue round-robin allocation until all M slots are occupied.
    
Packet Routing Lookup:
  backend = table[hash(5-tuple) mod M]
  
Key Architectural Properties:
  Minimal Disruption: Adding or removing 1 backend out of N instances moves only roughly 1/N of total table entries.
  Near-Perfect Uniformity: Each backend receives approximately floor(M/N) or ceil(M/N) table entries for an evenly built table.
  Sub-Microsecond Speed: Direct array indexing provides O(1) lookup time. A 65,537-entry table can remain cache-friendly when the stored backend reference is compact.

Bounded Loads Enforcement:
  Enforces a target upper load bound: no backend server should receive more than (1 + epsilon) * average_load, where epsilon is typically 0.25 (targeting a cap of 25% over average when capacity allows).
  If the hashed backend target exceeds its capacity bound:
    The load balancer walks sequentially to the next backend in the preference list.
    Repeats until locating an instance operating below the capacity threshold.
  Outcome: Limits workload skew while retaining the connection stability of consistent hashing. If every backend is at capacity, admission control and load shedding still protect the tier.

Defense in Depth: Reducing Single Points of Failure

Defense in Depth: Reducing Single Points of Failure

Tier 1: Local Active-Passive Redundancy (VRRP and Keepalived)
  Two load balancer nodes share a common Virtual IP address (VIP).
  The active node processes all incoming network traffic.
  The passive standby node monitors the active instance using heartbeats sent every 1 second.
  If the active node fails, the passive node broadcasts a gratuitous ARP to claim the VIP within about 3 seconds.
  New connections resume through the same VIP. Established NAT flows can still reset unless connection state is synchronized.
  Advantages: Simple and widely used operational model.
  Trade-offs: Standby node remains idle during normal operations (50% hardware utilization), and failover can cause a 1 to 3 second drop in active TCP connections.

Tier 2: Active-Active Clustering with DNS Round Robin
  Authoritative DNS returns multiple load balancer IP addresses (for example, 10.0.0.1 and 10.0.0.2).
  All load balancer nodes process production traffic simultaneously.
  If a node fails, automated DNS health probes remove the failing IP address from the record set.
  Advantages: 100% hardware utilization across all provisioned nodes under normal operation.
  Trade-offs: Recursive resolver and client DNS caching can delay failover until cached records expire, and DNS round robin does not adapt dynamically to backend load variations.

Tier 3: Anycast BGP Routing
  Multiple load balancer clusters advertise the identical public IP address using Border Gateway Protocol (BGP).
  Internet routers select a path according to routing policy and network topology, which often brings traffic to a nearby healthy load balancer cluster.
  If an entire cluster fails, BGP route withdrawals cause upstream routers to reconverge traffic to the next nearest cluster.
  Advantages: Automated, network-level failover within 10 to 30 seconds with natural geographic distribution.
  Trade-offs: Requires BGP-capable network infrastructure, and convergence time depends on the network and policy configuration. The illustrative design assumes 10 to 30 seconds during routing shifts.
  Commonly used by large-scale edge networks and implemented by several infrastructure platforms. Cloud providers may abstract the same global routing ideas behind managed products.

Tier 4: Distributed Sidecar Data Plane (Service Mesh)
  Augments centralized internal load balancing with decentralized Envoy sidecar proxies deployed alongside each application instance.
  Client applications dispatch requests to their local sidecar, which performs client-side load balancing, service discovery, and circuit breaking directly.
  Advantages: Moves much of the east-west load balancing and resiliency work into the service data plane, reducing centralized proxy bottlenecks for internal traffic.
  Trade-offs: Increases operational complexity and consumes additional CPU and memory resources per container pod.
  Commonly deployed in Kubernetes environments with service mesh control planes such as Istio or Linkerd.