Design a software load balancer

A software load balancer is a fleet of ordinary servers that share one virtual IP addressvirtual IP address (VIP): An IP address that belongs to a service rather than to one machine: several servers answer for it, so clients keep one address while the servers behind it come and go., or VIP: in the design below, 10 nodes for 30 million packets a second. The network’s routers spread the packets of that address over the fleet with equal-cost multipathequal-cost multipath (ECMP): A routing feature that spreads the traffic for one destination over several next hops of equal cost, usually by hashing each packet's addresses and ports, so that every packet of a flow takes the same next hop. (ECMP); each balancer node then picks a backend for the packet’s flow and tunnels the packet to it, and the backend replies to the client directly. The design has to keep every packet of a connection on the same backend while balancer nodes and backends come and go, so every node must choose the same backend for the same flow: a consistent-hashing table that all nodes build alike, plus a connection tableconnection table: A load balancer node's memory of the backend it chose for each flow it has seen, so that the flow's later packets go to the same backend without a new choice. on each node. A control plane hands out backend lists, and the nodes keep forwarding without it.

Requirements and estimate: direct return and 30 million open connections

A region serves web pages and APIs to millions of users through a few public addresses. A pair of hardware balancers carries it today, and every traffic peak is a capacity problem, because a pair grows only by replacing both boxes. Ask first:

Functional requirements: forward TCP and UDP for many VIPs; spread flows over a VIP’s backends by weight; health checks, draining and slow start; connection limits per backend; configuration by API. Non-functional requirements: line-rate forwarding of small packets; growth by adding nodes; no broken connections when a node fails or restarts; forwarding that continues while the control plane is down.

The first estimate, to change and run again:

# The first estimate for a region's layer-4 software load balancer. Every input is an assumption, written down so
# that you can change it and run the script again.
import math

PACKETS_IN = 30e6          # packets a second arriving for the region's virtual IPs at peak (requests and ACKs)
PACKET_BYTES = 120         # average size of an arriving packet
RESPONSE_RATIO = 12        # bytes sent back for every byte that arrives (pages, images, API responses)
NEW_CONNECTIONS = 1.5e6    # new TCP connections a second at peak
LIFETIME = 20              # seconds an average connection stays open
NODE_PPS = 8e6             # packets a second one balancer node can forward
TARGET = 0.5               # run the nodes at half their capacity at peak
SPARE = 2                  # nodes that may be down or in maintenance at the same time
ENTRY_BYTES = 64           # one connection-table entry: flow key, backend, timestamps

inbound = PACKETS_IN * PACKET_BYTES * 8 / 1e9
print("Traffic")
print(f"  arriving: {PACKETS_IN / 1e6:.0f} million packets a second x {PACKET_BYTES} bytes = {inbound:.1f} Gbit/s")
print(f"  leaving: {inbound * RESPONSE_RATIO:.1f} Gbit/s, sent by the backends straight to the clients")
print(f"  through the balancer, both ways would be {inbound * (1 + RESPONSE_RATIO):.1f} Gbit/s, "
      f"{1 + RESPONSE_RATIO:.0f} times as much")

nodes = math.ceil(PACKETS_IN / (NODE_PPS * TARGET))
print("Balancer nodes")
print(f"  {PACKETS_IN / 1e6:.0f} million / ({NODE_PPS / 1e6:.0f} million x {TARGET:.0%}) = {nodes} nodes, "
      f"plus {SPARE} spare = {nodes + SPARE}")

open_now = NEW_CONNECTIONS * LIFETIME
per_node = open_now / (nodes + SPARE)
print("Connection tables")
print(f"  open connections (Little's law): {NEW_CONNECTIONS / 1e6:.1f} million a second x {LIFETIME} s "
      f"= {open_now / 1e6:.0f} million")
print(f"  per node: {per_node / 1e6:.0f} million entries x {ENTRY_BYTES} bytes = {per_node * ENTRY_BYTES / 1e6:.0f} MB")
print(f"  when one node fails, at least its share, {open_now / (nodes + SPARE) / 1e6:.0f} million connections, "
      f"arrives at nodes that have never seen them")

Traffic
  arriving: 30 million packets a second x 120 bytes = 28.8 Gbit/s
  leaving: 345.6 Gbit/s, sent by the backends straight to the clients
  through the balancer, both ways would be 374.4 Gbit/s, 13 times as much
Balancer nodes
  30 million / (8 million x 50%) = 8 nodes, plus 2 spare = 10
Connection tables
  open connections (Little's law): 1.5 million a second x 20 s = 30 million
  per node: 3 million entries x 64 bytes = 192 MB
  when one node fails, at least its share, 3 million connections, arrives at nodes that have never seen them

Two numbers shape the design. Because responses go straight back, the balancer carries a thirteenth of the bytes. And 30 million open connections mean that every node holds millions of table entries, and that a failed node hands millions of connections to nodes that have never seen them.

The first design: every node picks the same backend

Each part of the design has one job:

• ECMP at the router: hashes each flow’s addresses and ports to one of the equal-cost next hops, the nodes.
• VIP announcement by BGP: each healthy node announces the virtual IP, and withdraws it when it is unhealthy.
• Maglev lookup table: a table of a prime number of entries filled with backends, the same on every node.
• Connection table: each node’s memory of the backend it chose for every flow it has seen.
• Encapsulation: the node wraps each packet in GRE or IP-in-IP addressed to the backend, leaving it intact.
• Direct server return: the backend answers the client from the virtual IP, never back through a node.
• Control plane: keeps VIPs, pools, weights and health, and pushes versioned configuration to every node.

Follow one connection’s packets through these parts:

The deep dives that decide whether the design works:

1. How is the lookup table built, how even is it, and how many flows move when a backend leaves?
2. What breaks connections when a node fails, restarts or joins, and what keeps them alive?
3. What happens when a node fails while the backends change at the same time?
4. How do the control plane and the data plane stay apart?
5. How many packets a second can a node forward, and what does a SYN flood do to its tables?
6. What does encapsulation cost, and where do TLS and HTTP features live?

An answer is judged on requirements and estimates, flow placement, connection persistence, failure handling, control-plane design and operations.

The API, and three structures in every node Pro: opens with a Pro, Premium or Ultimate pass