Load balancers and reverse proxies

A load balancer receives the connections or requests sent to one address and spreads them over a pool of servers, so that a service survives the loss of any one server and grows by adding more. A reverse proxy is a server that accepts requests on behalf of other servers and passes them on; HTTP’s own specification calls it a gateway (RFC 9110, section 3.7). The two overlap. A layer-7 load balancer is a reverse proxy that reads each HTTP request and decides where it goes, while a layer-4 load balancer forwards TCP or UDP flows by their addresses and ports without reading what they carry. This lesson runs a small balancer with health checks, works out how long a dead server keeps receiving traffic, shows how the client’s address survives the trip through a proxy, and measures how consistent hashing keeps clients on the same server when the pool changes.

What sits in front of a service

Clients find the service by its name, and DNS gives them one address, often called a virtual IP (VIP) because no single server owns it: the balancer answers for it. Behind that address the balancer keeps four things:

• A pool of backend servers that can answer the request, each with an address, a port and often a weight.
• The health of each backend, learned from health checks and from how real requests go.
• An algorithm that picks a backend for each new connection or request.
• State for the connections it is carrying, so that every packet or request of one conversation goes to the same backend.

Layer 4 or layer 7

The numbers come from the OSI model, which puts TCP and UDP at its fourth level, transport, and HTTP at its seventh, application. What a balancer can read decides what it can do.

A layer-4 balancer works in one of three ways. In NAT mode it rewrites the destination address of each packet to a backend’s, and the replies must come back through it to be rewritten again. As a full proxy it ends the client’s TCP connection and opens a second one to the backend, copying bytes between them; the program below works this way. With direct server return it forwards each packet unchanged, inside an encapsulation or with only the link-layer address changed, and the backend answers the client directly from the VIP. Google’s Maglev balancer encapsulates packets in GRE and leaves the replies, which are usually much larger than the requests, to direct return (Maglev paper).

A layer-7 proxy ends both TCP and TLS, reads the request, and opens or reuses its own connection to a backend. It can send /api/ to one pool and /static/ to another, retry a failed GET on a second server, and spread the requests of one HTTP/2 connection over many backends. That last point catches people out: a layer-4 balancer balances connections, so a client that sends thousands of requests over one HTTP/2 or gRPC connection loads one backend only.

Where TLS ends is a choice of its own. The proxy can terminate TLS and talk plain HTTP to the backends on a private network, re-encrypt with a second TLS connection to each backend, or pass it through at layer 4, in which case only the backend holds the certificate. A pass-through balancer can still pick a pool by the server name indication (SNI), which a TLS ClientHello normally carries unencrypted, but it never sees the HTTP inside.

Choosing a backend

• Round robin gives each backend the next connection in turn; weighted round robin gives a server with weight 2 twice the share of a server with weight 1.
• Least connections picks the backend with the fewest open connections. HAProxy’s manual recommends it for long sessions such as databases or remote desktops and calls it ill suited to short HTTP requests (HAProxy configuration).
• Two random choices pick two backends at random and send the request to the less loaded one, which keeps many balancers with slightly stale counts from all choosing the same “least loaded” server at once; nginx offers it as random two least_conn (nginx upstream module).
• Hashing turns something about the client, such as its address, a cookie or the URL, into a backend, so the same client keeps reaching the same server. Caches and session affinity rely on it, and the last part of this lesson measures what happens to the hashes when the pool changes.

A balancer that runs

The program is a complete layer-4 balancer: it accepts each client connection, picks a healthy backend in turn, connects to it and copies bytes both ways without reading them. Between some of the requests it checks the backends with GET /health. Socket pairs stand in for TCP connections, so it needs no network:

"""A round-robin TCP load balancer with health checks, written with asyncio.

Two backends answer HTTP requests. The balancer accepts each client connection, picks a
healthy backend in turn, opens a connection to it and copies bytes both ways without
reading them: a layer-4 proxy. Socket pairs stand in for TCP connections, so the program
needs no network, but every byte really passes through the proxy's sockets.
"""
import asyncio
import socket

FALL, RISE = 2, 2  # failed checks before a backend is taken out, passed checks to bring it back


class Backend:
    def __init__(self, name):
        self.name, self.running = name, True

    async def serve(self, reader, writer):
        request = await reader.readuntil(b"\r\n\r\n")
        path = request.split(b" ")[1]
        body = b"ok\n" if path == b"/health" else f"hello from {self.name}\n".encode()
        writer.write(b"HTTP/1.1 200 OK\r\nContent-Length: %d\r\nConnection: close\r\n\r\n%s" % (len(body), body))
        await writer.drain()
        writer.close()


async def connect(backend):
    """Open a connection to a backend, as connect() would; a stopped backend refuses it."""
    if not backend.running:
        raise ConnectionRefusedError(f"{backend.name} refused the connection")
    near, far = socket.socketpair()
    asyncio.create_task(backend.serve(*await asyncio.open_connection(sock=far)))
    return await asyncio.open_connection(sock=near)


async def pipe(reader, writer):
    """Copy bytes from one connection to the other until the sender closes."""
    try:
        while data := await reader.read(65536):
            writer.write(data)
            await writer.drain()
    except ConnectionError:
        pass
    writer.close()


class Balancer:
    def __init__(self, backends):
        self.backends, self.turn = backends, 0
        self.up = {b.name: True for b in backends}
        self.streak = {b.name: 0 for b in backends}  # consecutive check results against the current state

    def pick(self):
        healthy = [b for b in self.backends if self.up[b.name]]
        backend = healthy[self.turn % len(healthy)]
        self.turn += 1
        return backend

    async def handle(self, client_reader, client_writer):
        backend = self.pick()
        try:
            backend_reader, backend_writer = await connect(backend)
        except ConnectionRefusedError:
            client_writer.close()  # a layer-4 proxy has no error page to send: it closes
            return
        await asyncio.gather(pipe(client_reader, backend_writer), pipe(backend_reader, client_writer))

    async def check(self):
        """One round of active health checks: GET /health on every backend."""
        for b in self.backends:
            try:
                r, w = await connect(b)
                w.write(b"GET /health HTTP/1.1\r\nHost: check\r\n\r\n")
                ok = (await r.read()).startswith(b"HTTP/1.1 200")
            except ConnectionRefusedError:
                ok = False
            self.streak[b.name] = self.streak[b.name] + 1 if ok != self.up[b.name] else 0
            if self.streak[b.name] == (FALL if self.up[b.name] else RISE):
                self.up[b.name], self.streak[b.name] = ok, 0
                print(f"   health check: {b.name} is now {'UP' if ok else 'DOWN'}")
            elif self.streak[b.name]:
                print(f"   health check: {b.name} {'passed' if ok else 'failed'} ({self.streak[b.name]} in a row)")


async def request(balancer, number):
    """A client connects to the balancer, sends GET / and reads until the connection closes."""
    near, far = socket.socketpair()
    handler = asyncio.create_task(balancer.handle(*await asyncio.open_connection(sock=far)))
    reader, writer = await asyncio.open_connection(sock=near)
    try:
        writer.write(b"GET / HTTP/1.1\r\nHost: shop.example\r\n\r\n")
        await writer.drain()
        reply = await reader.read()
    except ConnectionError:
        reply = b""
    writer.close()
    await handler
    answer = reply.split(b"\r\n\r\n", 1)[1].decode().strip() if reply else "FAILED: the connection closed with no reply"
    print(f"request {number:2}: {answer}")


async def main():
    a, b = Backend("app-a"), Backend("app-b")
    lb = Balancer([a, b])
    for n in range(1, 5):
        await request(lb, n)
    print("-- app-b stops")
    b.running = False
    await request(lb, 5)
    await request(lb, 6)
    await lb.check()
    await request(lb, 7)
    await request(lb, 8)
    await lb.check()
    await request(lb, 9)
    await request(lb, 10)
    print("-- app-b starts again")
    b.running = True
    await lb.check()
    await request(lb, 11)
    await lb.check()
    for n in range(12, 15):
        await request(lb, n)


asyncio.run(main())

request  1: hello from app-a
request  2: hello from app-b
request  3: hello from app-a
request  4: hello from app-b
-- app-b stops
request  5: hello from app-a
request  6: FAILED: the connection closed with no reply
   health check: app-b failed (1 in a row)
request  7: hello from app-a
request  8: FAILED: the connection closed with no reply
   health check: app-b is now DOWN
request  9: hello from app-a
request 10: hello from app-a
-- app-b starts again
   health check: app-b passed (1 in a row)
request 11: hello from app-a
   health check: app-b is now UP
request 12: hello from app-b
request 13: hello from app-a
request 14: hello from app-b

Read the run in four stages:

• Requests 1 to 4 alternate between the two backends: round robin.
• app-b stops and refuses connections, but the balancer has not checked yet, so request 6 still goes to it. This proxy works at layer 4, so all it can do is close the client’s connection; a layer-7 proxy would have retried on app-a or answered 502 Bad Gateway.
• One failed check is not enough. With FALL = 2 the balancer waits for a second failure, so request 8 fails too, and only then is app-b out of the pool.
• Coming back takes two passed checks (RISE = 2). Request 11 still goes to app-a after the first one; from request 12 the two alternate again.

Health checks, and how long a failure lasts

Active checks send a request of their own to each backend on a timer, as the program did. Passive checks watch real traffic and take a backend out after errors. HAProxy’s defaults are a check every 2 seconds (inter), 3 failures to take a server out (fall) and 2 successes to bring it back (rise) (HAProxy configuration). nginx’s upstream module counts failures in real traffic: by default, one failed attempt within 10 seconds (max_fails=1, fail_timeout=10s) marks a server unavailable for the next 10 seconds (nginx upstream module).

How long a dead backend keeps receiving traffic depends on those numbers and on how it died. A crashed process refuses connections, so checks fail at once; a hung one accepts them and never answers, so each check waits for its timeout:

"""How long does a balancer keep sending traffic to a backend that has died?

Four backends share 400 requests a second in turn, so app-3 gets one every 10 ms. It fails
at t = 10.3 s. A crashed process refuses connections, so a check or a request fails at
once; a hung one accepts them and never answers, so each fails only at its timeout.
Times are kept in whole milliseconds, so the arithmetic is exact.
"""

GAP_MS = 10  # app-3 receives a request every 10 ms (100 a second)
FAIL_MS = 10_300
CHECK_TIMEOUT_MS = 1_000
REQUEST_TIMEOUT_MS = 5_000


def active(inter_ms, fall, hung):
    """Checks start every inter_ms; the backend is taken out when the fall-th failure is known."""
    failed, start = 0, 0
    while True:
        if start >= FAIL_MS:
            failed += 1
            if failed == fall:
                return start + (CHECK_TIMEOUT_MS if hung else 0)
        start += inter_ms


def passive(errors, hung):
    """Real requests are watched instead: out after `errors` failed requests in a row."""
    first = -(-FAIL_MS // GAP_MS) * GAP_MS  # the first request at or after the failure
    last = first + (errors - 1) * GAP_MS
    return last + (REQUEST_TIMEOUT_MS if hung else 1)  # a refusal is known within a millisecond


print(f"app-3 hangs at t={FAIL_MS / 1000} s; checks every 2 s, fall 3, check timeout 1 s:")
start, failed = 0, 0
while failed < 3:
    if start >= FAIL_MS:
        failed += 1
        print(f"  check started at t={start / 1000:4.1f} s fails at t={(start + CHECK_TIMEOUT_MS) / 1000:4.1f} s ({failed} of 3)")
    start += 2_000
print()

methods = {
    "active, every 2 s, fall 3": lambda hung: active(2_000, 3, hung),
    "active, every 1 s, fall 2": lambda hung: active(1_000, 2, hung),
    "passive, 3 errors in a row": lambda hung: passive(3, hung),
}
print(f"{'detection':27} {'failure':8} {'out at':>8} {'after':>7} {'sent to app-3':>14}")
for name, out_at in methods.items():
    for hung in (False, True):
        out = out_at(hung)
        sent = len(range(-(-FAIL_MS // GAP_MS) * GAP_MS, out, GAP_MS))
        print(f"{name:27} {'hung' if hung else 'refused':8} {out / 1000:7.2f}s {(out - FAIL_MS) / 1000:6.2f}s {sent:>14}")

balancers, backends = 20, 50
print()
for inter in (2, 1):
    print(f"active checks every {inter} s from {balancers} balancers to {backends} backends: "
          f"{balancers * backends // inter:,} check requests a second, {balancers // inter} per backend")

app-3 hangs at t=10.3 s; checks every 2 s, fall 3, check timeout 1 s:
  check started at t=12.0 s fails at t=13.0 s (1 of 3)
  check started at t=14.0 s fails at t=15.0 s (2 of 3)
  check started at t=16.0 s fails at t=17.0 s (3 of 3)

detection                   failure    out at   after  sent to app-3
active, every 2 s, fall 3   refused    16.00s   5.70s            570
active, every 2 s, fall 3   hung       17.00s   6.70s            670
active, every 1 s, fall 2   refused    12.00s   1.70s            170
active, every 1 s, fall 2   hung       13.00s   2.70s            270
passive, 3 errors in a row  refused    10.32s   0.02s              3
passive, 3 errors in a row  hung       15.32s   5.02s            502

active checks every 2 s from 20 balancers to 50 backends: 500 check requests a second, 10 per backend
active checks every 1 s from 20 balancers to 50 backends: 1,000 check requests a second, 20 per backend

With the defaults, a crash at t = 10.3 s is noticed at the checks at 12, 14 and 16 seconds: 5.7 seconds in which 570 requests reached the dead backend. If it hangs, every check also waits a second for its timeout, and the gap grows to 6.7 seconds. Checking every second with fall 2 cuts the gap to 1.7 seconds, but doubles the checks: 20 balancers checking 50 backends send 1,000 check requests a second, 20 to every backend. Passive checks see a refusal within three requests but a hang only when requests time out, five seconds later. Most production set-ups combine both: passive detection for quick refusals, and active checks to notice hangs and to bring servers back.

A layer-7 proxy also tells the client what went wrong, with status codes defined in RFC 9110, section 15.6: 502 Bad Gateway when the backend’s answer was invalid or the connection failed, 503 Service Unavailable when no server can take the request, and 504 Gateway Timeout when the backend did not answer in time. It may retry on another backend, but only requests whose methods are idempotent, such as GET, PUT and DELETE (section 9.2.2), because a POST that reached the first server may already have charged a card.

Draining and session affinity

Draining takes a server out of the pool gently: the balancer stops giving it new connections or requests and lets the ones in flight finish, up to a time limit. A server that is shutting down helps its clients leave. Over HTTP/1.1 it sends Connection: close on its last responses (RFC 9112, section 9.6). Over HTTP/2 it sends a GOAWAY frame, which names the last stream it will process, so that the client opens new streams on another connection (RFC 9113, section 6.8). A clean deployment then runs in this order: drain, wait for the connections to end or the drain limit to pass, stop the old version, start the new one, and send traffic only once its checks pass. Some balancers also ramp a returning server’s weight up slowly (slow start), so a cold server is not handed its full share at once.

Session affinity, or sticky sessions, keeps a client on one backend, through a cookie that the balancer adds or a hash of the client’s address. It helps when a server keeps state in memory, such as a login session or a warm cache, but it costs balance, because a few heavy clients can pin one server, and the state is lost when that server dies. Keeping sessions in a shared store lets any backend serve any request, which is why affinity is best treated as a performance aid rather than as the only copy of anything.

Keeping the client’s address

Behind a proxy, the backend’s TCP peer is the proxy, so the client’s address, which logs, rate limits and fraud checks need, must be passed on in data:

• X-Forwarded-For is a de facto header: each proxy appends the address it received the request from, giving a comma-separated chain such as 203.0.113.66, 198.51.100.7.
• Forwarded is its standard form (RFC 7239), with named parameters for the client (for), the proxy (by), the original host and the protocol (proto). IPv6 addresses are quoted and bracketed: for="[2001:db8:cafe::17]".
• The PROXY protocol works at layer 4 for any TCP protocol, TLS included: the balancer sends one header in front of the client’s bytes. Version 1 is a text line of at most 107 bytes; version 2 is binary and starts with a fixed 12-byte signature (PROXY protocol).

None of these values can be trusted on their own. A client can send its own X-Forwarded-For or Forwarded header, and RFC 7239 warns that the field “cannot be relied upon to be correct” (section 8.1). The safe rule is to read the chain from the right, skip every address that belongs to your own proxies, and take the first one that does not:

"""Which address is the real client? Reading X-Forwarded-For, Forwarded and the PROXY protocol.

The application sees a connection from its own load balancer (10.0.2.15). The client's
address arrives in data that the balancer added, and in data the client may have forged.
Addresses are from the documentation ranges (RFC 5737, RFC 3849).
"""
import ipaddress
import struct

# Our own proxies, nothing else: the balancers' subnet and the CDN edge that sits in front of them.
TRUSTED = [ipaddress.ip_network(n) for n in ("10.0.0.0/8", "2001:db8:cafe::/48")]


def trusted(addr):
    try:
        return any(ipaddress.ip_address(addr) in net for net in TRUSTED)
    except ValueError:  # "unknown", an obfuscated "_name": not one of ours
        return False


def client_from_xff(peer, xff):
    """Walk the chain from the right: the first hop not added by our own proxies is the client."""
    chain = [part.strip() for part in xff.split(",")] + [peer]
    for addr in reversed(chain):
        if not trusted(addr):
            return addr
    return chain[0]


def client_from_forwarded(peer, value):
    """RFC 7239: one element per proxy, each of key=value pairs; IPv6 nodes are quoted and bracketed."""
    hops = []
    for element in value.split(","):
        pairs = dict(p.strip().split("=", 1) for p in element.split(";"))
        node = {k.lower(): v.strip('"') for k, v in pairs.items()}.get("for", "unknown")
        hops.append(node[1:node.index("]")] if node.startswith("[") else node.split(":")[0])
    for addr in reversed(hops + [peer]):  # the same rule: from the right, skip our own proxies
        if not trusted(addr):
            return hops, addr
    return hops, hops[0]


def proxy_v1(line):
    """PROXY protocol version 1: one text line in front of the client's own bytes."""
    word, family, src, dst, sport, dport = line.rstrip(b"\r\n").decode("ascii").split(" ")
    assert word == "PROXY" and family in ("TCP4", "TCP6")
    return src, int(sport), dst, int(dport)


SIGNATURE = b"\r\n\r\n\x00\r\nQUIT\n"  # the 12 bytes that start a version 2 header


def proxy_v2(data):
    """PROXY protocol version 2: a binary header; here TCP over IPv4 (family byte 0x11)."""
    assert data[:12] == SIGNATURE
    version_command, family, length = struct.unpack("!BBH", data[12:16])
    assert version_command == 0x21 and family == 0x11  # version 2, PROXY command; TCP over IPv4
    src, dst, sport, dport = struct.unpack("!4s4sHH", data[16:28])
    return str(ipaddress.ip_address(src)), sport, str(ipaddress.ip_address(dst)), dport, 16 + length


print("1. X-Forwarded-For, as the application receives it")
peer = "10.0.2.15"  # the TCP peer: our load balancer
xff = "203.0.113.66, 198.51.100.7"  # the client wrote the first entry itself; the balancer appended the second
print(f"   connection from {peer}, X-Forwarded-For: {xff}")
print(f"   first entry (what naive code uses):    {xff.split(',')[0]}")
print(f"   right-most untrusted (the real client): {client_from_xff(peer, xff)}")

print("2. Forwarded (RFC 7239), added by the CDN edge and then by our balancer")
value = 'for=198.51.100.7;proto=https, for="[2001:db8:cafe::17]:4711";by=10.0.2.15'
hops, client = client_from_forwarded(peer, value)
print(f"   Forwarded: {value}")
print(f"   hops: {' -> '.join(hops + [peer])}; the real client: {client}")

print("3. PROXY protocol version 1 (text) at the start of the TCP stream")
stream = b"PROXY TCP4 198.51.100.7 203.0.113.10 51000 443\r\nGET / HTTP/1.1\r\n"
header, rest = stream.split(b"\r\n", 1)
src, sport, dst, dport = proxy_v1(header)
print(f"   client {src}:{sport} connected to {dst}:{dport}; {len(header) + 2} header bytes, then {rest[:14]!r}")

print("4. PROXY protocol version 2 (binary), the same connection")
v2 = SIGNATURE + struct.pack("!BBH4s4sHH", 0x21, 0x11, 12,
                             ipaddress.ip_address("198.51.100.7").packed,
                             ipaddress.ip_address("203.0.113.10").packed, 51000, 443)
src, sport, dst, dport, size = proxy_v2(v2)
print(f"   client {src}:{sport} connected to {dst}:{dport}; {size} header bytes: {v2[:16].hex(' ')} ...")

1. X-Forwarded-For, as the application receives it
   connection from 10.0.2.15, X-Forwarded-For: 203.0.113.66, 198.51.100.7
   first entry (what naive code uses):    203.0.113.66
   right-most untrusted (the real client): 198.51.100.7
2. Forwarded (RFC 7239), added by the CDN edge and then by our balancer
   Forwarded: for=198.51.100.7;proto=https, for="[2001:db8:cafe::17]:4711";by=10.0.2.15
   hops: 198.51.100.7 -> 2001:db8:cafe::17 -> 10.0.2.15; the real client: 198.51.100.7
3. PROXY protocol version 1 (text) at the start of the TCP stream
   client 198.51.100.7:51000 connected to 203.0.113.10:443; 48 header bytes, then b'GET / HTTP/1.1'
4. PROXY protocol version 2 (binary), the same connection
   client 198.51.100.7:51000 connected to 203.0.113.10:443; 28 header bytes: 0d 0a 0d 0a 00 0d 0a 51 55 49 54 0a 21 11 00 0c ...

Hashing clients to servers

Hashing keeps a client on the same backend only while the pool stays the same. The simplest scheme, backend number hash % n, reshuffles almost everything when n changes. Consistent hashing places many points for each backend on a ring and sends each key to the first point clockwise from it, so a change moves only the keys next to the points that came or went:

"""How many clients change backend when a pool of five loses one, or gains a sixth?

Each of 10,000 client keys is hashed with SHA-256 (Python's own hash() of a string changes
from run to run). "Modulo" picks backend number hash % n. "Ring" places 100 points per
backend on a ring of 2**32 positions and picks the first point clockwise from the key.
"""
import bisect
import hashlib


def h(text):
    return int.from_bytes(hashlib.sha256(text.encode()).digest()[:4], "big")


def modulo(backends):
    return lambda key: backends[h(key) % len(backends)]


def ring(backends, points=100):
    marks = sorted((h(f"{b}#{i}"), b) for b in backends for i in range(points))
    positions = [p for p, _ in marks]

    def pick(key):
        i = bisect.bisect(positions, h(key)) % len(marks)
        return marks[i][1]

    return pick


keys = [f"client-{i:05}" for i in range(10_000)]
five = ["app-1", "app-2", "app-3", "app-4", "app-5"]
changes = {
    "remove app-3": [b for b in five if b != "app-3"],
    "add app-6": five + ["app-6"],
}

for change, after in changes.items():
    print(f"{change}: {len(five)} -> {len(after)} backends")
    for name, method in (("modulo", modulo), ("ring", ring)):
        before_pick, after_pick = method(five), method(after)
        moved = sum(before_pick(k) != after_pick(k) for k in keys)
        print(f"  {name:6}  {moved:5} of {len(keys)} keys move ({moved / len(keys):.1%})")

pick = ring(five)
load = {b: 0 for b in five}
for k in keys:
    load[pick(k)] += 1
print("keys per backend on the ring:", ", ".join(f"{b} {n}" for b, n in load.items()))

remove app-3: 5 -> 4 backends
  modulo   7992 of 10000 keys move (79.9%)
  ring     1927 of 10000 keys move (19.3%)
add app-6: 5 -> 6 backends
  modulo   8341 of 10000 keys move (83.4%)
  ring     1784 of 10000 keys move (17.8%)
keys per backend on the ring: app-1 2284, app-2 2009, app-3 1927, app-4 2012, app-5 1768

Removing one of five backends moved 79.9 % of the keys with modulo hashing, close to the 80 % that arithmetic predicts, and 19.3 % with the ring: exactly the keys that app-3 had held. Adding a sixth moved 83.4 % against 17.8 %, close to a sixth. The price is balance: with 100 points each, the five backends held between 1,768 and 2,284 of the 10,000 keys. More points per backend even out the share, and HAProxy’s manual notes that a consistent hash “will never be very smooth” for the same reason. Maglev uses a lookup table of 65,537 entries, filled so that every backend gets an almost equal share and a change disturbs few entries.

import bisect
import hashlib


def position(text):
    """The place of a text on the ring: the first 4 bytes of its SHA-256, from 0 to 2**32 - 1."""
    return int.from_bytes(hashlib.sha256(text.encode()).digest()[:4], "big")


class Ring:
    def __init__(self, nodes=(), points=100):
        self.points = points
        self.marks = []  # sorted (position, node) pairs, one per virtual node
        for node in nodes:
            self.add(node)

    def add(self, node):
        """Put the node's virtual nodes on the ring."""
        # Replace this line: add one (position, node) pair per virtual node and keep the list sorted.
        self.marks.append((0, node))

    def remove(self, node):
        """Take all of the node's virtual nodes off the ring."""
        # Replace this line.
        pass

    def lookup(self, key):
        """The node of the first virtual node at or after the key's position, wrapping around; None when empty."""
        # Replace this line.
        return self.marks[0][1] if self.marks else None


def moved_share(keys, before, after):
    """The share of keys (0.0 to 1.0) whose node differs between two rings."""
    # Replace this line.
    return 0.0

from hash_ring import Ring, moved_share, position


def first_at_or_after(ring_nodes, points, key):
    marks = sorted((position(f"{n}#{i}"), n) for n in ring_nodes for i in range(points))
    for p, n in marks:
        if p >= position(key):
            return n
    return marks[0][1]


def test_lookup_goes_clockwise():
    """returns the node of the first virtual node at or after the key"""
    nodes = ["app-1", "app-2", "app-3"]
    ring = Ring(nodes, points=10)
    for i in range(200):
        key = f"user-{i}"
        assert ring.lookup(key) == first_at_or_after(nodes, 10, key)
    assert Ring([]).lookup("anyone") is None


def test_wrap_around():
    """wraps past the largest position to the smallest one"""
    ring = Ring(["app-1", "app-2"], points=1)
    last = max(position("app-1#0"), position("app-2#0"))
    first_node = min(("app-1", "app-2"), key=lambda n: position(n + "#0"))
    key = next(f"k{i}" for i in range(10_000) if position(f"k{i}") > last)
    assert ring.lookup(key) == first_node


def test_remove_moves_only_that_nodes_keys():
    """removing a node moves its keys and leaves every other key where it was"""
    keys = [f"client-{i}" for i in range(2_000)]
    ring = Ring(["app-1", "app-2", "app-3", "app-4", "app-5"])
    before = {k: ring.lookup(k) for k in keys}
    ring.remove("app-3")
    for k in keys:
        if before[k] != "app-3":
            assert ring.lookup(k) == before[k]
        else:
            assert ring.lookup(k) in {"app-1", "app-2", "app-4", "app-5"}
    assert all(n != "app-3" for _, n in ring.marks)
    assert len(ring.marks) == 400


def test_moved_share():
    """adding a sixth node moves about a sixth of the keys"""
    keys = [f"client-{i}" for i in range(2_000)]
    five = ["app-1", "app-2", "app-3", "app-4", "app-5"]
    share = moved_share(keys, Ring(five), Ring(five + ["app-6"]))
    assert 0.10 < share < 0.25
    assert moved_share(keys, Ring(five), Ring(five)) == 0.0
    assert moved_share(["a", "b"], Ring(["x"]), Ring(["y"])) == 1.0

Many balancers behind one address

One balancer is itself a single point of failure, so large services run many instances that all announce the same VIP. With anycast, several sites announce the same address prefix and routing delivers each client to a nearby one (RFC 4786). Inside a site, the routers in front of the balancers use equal-cost multi-path (ECMP) routing: they hash the addresses and ports of each packet, so all packets of one flow reach the same instance. Maglev’s routers spread traffic over its machines this way, because every machine announces the VIP at the same cost.

The trouble starts when an instance is added or removed. The routers’ hash then sends some flows to a different instance in mid-connection: RFC 2992 works out that with its hash-threshold method, removing one of five equal next hops moves between 30 % and 50 % of all flows, depending on which one goes (RFC 2992), although only a fifth were on the hop that left. The new instance has no record of those connections. If it picks a backend with the same consistent hash as every other instance, it still sends the flow to the right server, which is why Maglev combines a connection table on each machine with consistent hashing shared by all of them.

Interview questions

How does a layer-4 load balancer differ from a layer-7 one?

A layer-4 balancer works with TCP or UDP flows: it reads IP addresses and ports, picks a backend for each new connection and forwards the bytes without reading them, by rewriting addresses, by proxying the connection, or by direct server return. It handles any protocol and long-lived connections cheaply, but it cannot route by URL and it balances connections, not requests. A layer-7 balancer is a reverse proxy for HTTP: it usually ends TLS, reads each request’s method, host, path and headers, routes by them, retries idempotent requests on another server and answers errors itself. It costs more work per request and must hold the certificate. Many sites use both: layer 4 to spread traffic over a fleet of layer-7 proxies.

Key takeaways

• A load balancer gives a pool of servers one address; a layer-7 balancer is a reverse proxy that routes each HTTP request, a layer-4 balancer forwards TCP or UDP flows without reading them.
• TLS ends at the proxy, is re-encrypted to the backends, or passes through at layer 4, where only the server name can guide the choice.
• Health checks decide how long a dead server keeps receiving traffic: with checks every 2 seconds and 3 failures, about 6 seconds; passive checks notice refusals almost at once but hangs only after a timeout.
• Draining lets in-flight requests finish before a server stops; HTTP/1.1 uses Connection: close and HTTP/2 a GOAWAY frame.
• The client’s address travels in X-Forwarded-For, Forwarded or the PROXY protocol; trust only entries that your own proxies added.
• Consistent hashing moves about 1/n of the keys when one of n backends changes, against almost all of them with hash % n.