How a request survives a billion-RPS gateway.
Nginx · Envoy · Kubernetes · mTLS.

The 80% in ten cards

If you internalize only this section, you can hold a credible gateway-architecture conversation. Every card links to the deep section where the "why" lives.

Before nginx ever sees a byte

Type api.example.com and hit enter. At billion-requests-per-day scale, four systems have already made decisions before any L7 software runs. You must know them, because half of "nginx performance problems" are actually problems here.

1. DNS + GSLB: which region?

Authoritative DNS doesn't return one IP; a global load balancer (GSLB) returns the IP of the healthiest, nearest region, based on the resolver's location and region health. TTLs are short (30–60 s) so a region can be drained in minutes.

2. Anycast + BGP: which datacenter edge?

The same IP prefix (say 203.0.113.0/24) is announced via BGP from 30 datacenters. Internet routers deliver each packet to the topologically nearest announcement. One IP, many physical locations — that's how a DDoS gets automatically diluted across the planet instead of concentrating on one site.

3. L4 load balancer: which nginx machine?

Inside the datacenter, an L4 balancer (IPVS, Maglev-style consistent hashing, or router ECMP) spreads TCP flows across hundreds of nginx boxes. It looks only at the 5-tuple (src IP, src port, dst IP, dst port, protocol). It never parses HTTP.

4. The kernel handshake, before your process wakes

SYN → SYN/ACK → ACK happens in the kernel. Completed connections sit in the accept queue (bounded by listen backlog and net.core.somaxconn) until nginx calls accept(). If that queue overflows, the kernel drops SYNs — clients see timeouts and no log line appears anywhere in nginx. First lesson of production debugging: the request you can't find in logs may have died in a kernel queue.

Nginx internals: how one core serves 50,000 connections

The problem nginx was built to kill: C10K

Apache's classic model: one process or thread per connection. Each thread costs a ~1 MB stack, kernel scheduling entries, and context switches (~1–5 µs each, plus trashed CPU caches). At 10,000 mostly-idle connections you burn gigabytes of RAM and most of your CPU on switching between threads that are all just waiting for bytes.

Igor Sysoev's observation (2002): a proxy's job is 99% waiting on the network and 1% computing. So don't dedicate an execution context to each wait. Instead, one process asks the kernel: "of my 50,000 sockets, which ones have something to do right now?" — and only touches those.

Process architecture: master + workers

• Master runs as root only to bind ports <1024 and read certs. It never touches traffic. It handles signals: HUP = reload, USR1 = reopen logs, USR2 = binary upgrade.
• Workers (one per core, pinned with worker_cpu_affinity) inherit the listening sockets across fork() and each run an independent event loop. A worker crash kills only its connections; master re-forks it.
• Hot reload: on HUP, master parses the new config, forks fresh workers, then tells old workers to stop accepting and finish in-flight requests. Two generations coexist briefly. No dropped connection, no lock, no "maintenance window".

The event loop, mechanically

WORKER LOOP (simplified from src/event/ngx_event.c)
for (;;) {
    timer = closest_timeout();            // e.g. 37ms until some client times out
    n = epoll_wait(ep, events, 512, timer); // SLEEP until sockets are ready
    for (i = 0; i < n; i++) {
        c = events[i].data.ptr;             // connection object
        c->handler(c);                      // run its state machine ONE step:
    }                                       //   read_request_line → read_headers →
    expire_timers();                        //   … → connect_upstream → send_response
}

Every connection is a state machine, and the handler pointer is the state. Read 300 bytes of a header, hit EAGAIN (no more bytes yet)? Save position, set handler to "continue reading headers", return to the loop. The worker instantly serves other sockets. When the kernel later signals readability, the machine resumes exactly where it left off. Concurrency without threads: it's cooperative multitasking where the kernel's readiness events are the scheduler.

One request through the worker, 1 cm resolution

1. accept. Listen fd is readable → accept4(..., SOCK_NONBLOCK). With reuseport, each worker has its own listen socket and the kernel hash-shards incoming connections — this removed the old "thundering herd" (all workers waking for one connection) and the accept-mutex workaround.
2. TLS. SSL_do_handshake() over multiple loop iterations. Session resumption (tickets/TLS1.3 PSK) skips a full asymmetric handshake — at scale this is a double-digit % CPU difference, since one RSA/ECDSA signature costs ~100µs–1ms of pure CPU.
3. parse. Request line and headers parsed by a hand-written state machine that consumes byte-by-byte and can pause mid-token. No regex, no allocation per header — pointers into the read buffer.
4. 11 phases. The parsed request walks nginx's phase pipeline: POST_READ → SERVER_REWRITE → FIND_CONFIG → REWRITE → PREACCESS (limit_req/limit_conn live here) → ACCESS (allow/deny, auth_request) → PRECONTENT → CONTENT (proxy_pass/static) → LOG. Modules register into phases — this is why config order sometimes doesn't matter (phase order wins) and why rate limiting runs before auth: reject cheap before verifying expensive.
5. upstream. Non-blocking connect() to the backend — ideally reused from a keepalive pool (saves a 3-way handshake, and with TLS an entire handshake, per request). Request forwarded; response streamed back through buffers.
6. respond. For files: sendfile() — kernel copies page cache → socket, zero trips through userspace. For proxied bodies: buffer chain. tcp_nopush coalesces headers+body into full packets.
7. log + reset. Access log line buffered; connection either closes or re-arms as keep-alive with a tiny memory footprint, request-scoped memory freed in one shot.

Memory pools — why nginx doesn't call malloc per header

Each request gets a pool: bump-pointer allocation from a slab; nothing is individually freed; when the request ends, the whole pool is destroyed at once. Consequences: allocation is ~a pointer increment, zero fragmentation over months of uptime, and no per-object leak class (you can't leak what dies with the pool). The trade-off — you can't free early — doesn't matter for request-scoped lifetimes measured in milliseconds.

Buffering: the impedance-matching job

A backend can emit a 2 MB response in 20 ms; a mobile client may need 20 s to receive it. If nginx streamed 1:1, the backend worker/connection is held hostage for 20 s (this is the classic slow client attack surface too). With proxy_buffering on, nginx slurps the response into memory (proxy_buffers) or temp file, frees the backend in 20 ms, and babysits the slow client itself — which costs it almost nothing (one epoll entry). Turn buffering off only for streaming/SSE/LLM token streams where time-to-first-byte matters more than backend efficiency. Notice this is exactly the IA-gateway tension: response inspection wants buffering; streaming UX wants none — hence chunk-wise scanning designs.

Making nginx fast — and proving it's fast

The tuning set that actually matters (with the why)

/etc/nginx/nginx.conf — annotated production baseline
worker_processes auto;              # one per core. More = context switching, not speed
worker_rlimit_nofile 200000;        # each conn = 1 fd client + often 1 fd upstream

events {
    worker_connections 65535;       # per worker. Real cap = fds & memory, not CPU
    multi_accept on;                # drain accept queue in bursts
}

http {
    sendfile on;                    # zero-copy file→socket, skips userspace
    tcp_nopush on;                  # full packets: headers+body coalesced
    keepalive_timeout 65s;          # client side: amortize TCP+TLS handshakes
    keepalive_requests 1000;

    ssl_session_tickets on;         # resume TLS w/o full asymmetric crypto
    ssl_protocols TLSv1.2 TLSv1.3;

    upstream app {
        server 10.0.1.10:8080;
        server 10.0.1.11:8080;
        keepalive 128;              # pooled upstream conns — the single biggest
    }                               #   proxy win: no handshake per request
    server {
        location / {
            proxy_pass http://app;
            proxy_http_version 1.1;         # required for upstream keepalive
            proxy_set_header Connection ""; # don't forward "close"
        }
    }
}

Confirming performance: the methodology, not a number

wrk2 -t16 -c1000 -d120s -R 80000 --latency https://edge/api/ping
# -R 80000: 80k RPS constant, regardless of how the server suffers
  p50 1.9ms · p99 12ms · p99.9 41ms   ← the tail IS the product

# CPU: user vs sys split — high %sys means kernel/network, not your config
mpstat -P ALL 1
# accept-queue overflow = invisible drops (the silent killer from §01)
ss -lnt        # Recv-Q vs backlog on :443
netstat -s | grep -i "listen"   # "times the listen queue overflowed"
# where is CPU actually going? flame graph:
perf record -F 99 -a -g -- sleep 30 && perf script | stackcollapse-perf.pl | flamegraph.pl > f.svg

Rate limiting: one box, then one thousand pods

Choose the algorithm by what "1000 req/s" should mean

Inside limit_req at 1 cm

nginx.conf
limit_req_zone $binary_remote_addr zone=perip:100m rate=10r/s;
# 100 MB shared memory ≈ state for ~800k distinct client keys
server {
  location /api/ {
      limit_req zone=perip burst=20 nodelay;
      limit_req_status 429;
  }
}

• The zone is a shared-memory red-black tree + LRU list keyed by client key; all workers see it; a spinlock guards updates (held for nanoseconds — fine, because the critical section is ~20 instructions).
• Per key it stores essentially two numbers: last_seen and excess (in milli-requests). On arrival: excess = max(0, excess − rate·Δt) + 1000. If excess > burst → reject. That's a leaky bucket computed lazily — no timers, no background drainer, state updates only when the key shows up. This is why it's O(1) and RAM-cheap.
• burst=20 without nodelay: over-rate requests are queued and released on schedule (true smoothing, adds latency). With nodelay: the 20 pass immediately, the bucket just remembers the debt — burst tolerance without added latency. Most APIs want nodelay.
• Memory pressure: when shm is full, nginx evicts the LRU keys — an attacker spraying millions of keys degrades you toward per-newest-keys limiting, not OOM. Bounded by design.

Now do it across 200 gateway pods

Kubernetes scales your gateway horizontally, and your per-pod limiter silently becomes 200 × limit. A client spraying requests across pods (which the L4 balancer does for them) gets 200× quota. Three honest designs:

Auth: verify at the door, carry identity inward

The core principle: stateless verification on the hot path

1B requests/day ≈ 12k RPS average, 50k+ peak. If every request needed a session-store lookup ("is token abc123 valid?"), the session store becomes your global bottleneck and blast radius. So modern edges verify signed tokens (JWT): the proof of validity travels inside the request.

Three nginx auth mechanics you should be able to sketch

1 · native JWT (nginx-plus / njs / lua) — verify inline
location /api/ {
    auth_jwt "api" token=$http_authorization;
    auth_jwt_key_request /jwks;          # cached public keys
    proxy_set_header X-User $jwt_claim_sub;   # identity flows inward as a header…
    proxy_pass http://app;                    # …signed variant: re-mint an internal token
}

2 · auth_request — subrequest to a policy service (complex logic)
location /api/ {
    auth_request /_authz;                # internal subrequest; 2xx=allow 401/403=deny
    auth_request_set $uid $upstream_http_x_user;
    proxy_pass http://app;
}
location = /_authz {
    internal;
    proxy_pass http://authz-svc/check;   # gets original URI+headers, returns verdict
    proxy_pass_request_body off;         # verdict needs headers, not the 10MB body
    proxy_cache authz_cache;             # cache allow-verdicts a few seconds
}

3 · mTLS client certs — machines, not humans (§09 for the crypto)
ssl_verify_client on;
ssl_client_certificate /etc/nginx/ca.pem;
proxy_set_header X-Client-DN $ssl_client_s_dn;

auth_request is the pattern Envoy generalizes as ext_authz — same shape: the data plane asks a sidecar/service "yes or no?" per request, with caching to keep the added latency at ~0 for repeat callers. Know the failure question: what does the gateway do when the authz service is down? Fail-closed for admin APIs, fail-open-with-alarm is sometimes accepted for read-only public data — say the words "explicit fail-policy per route" and you sound like you've operated this.

Security at scale: bloom filters and throwing away the bad 30%

At a real edge, a third or more of traffic is junk: scanners, credential stuffers, scrapers, botnets. The design goal is cost asymmetry — make each malicious request cost you nanoseconds and the attacker a real resource.

Know the layer, know the defense

Bloom filters: the datastructure of "is this one of the 10 million bad ones?"

You have a 10M-entry IP/token reputation blocklist, updated every minute, and 300k lookups/sec across workers. A hash set of strings costs ~600 MB+ and cache-miss-heavy probes; a remote lookup costs an RTT. A Bloom filter costs ~12 MB and answers in ~100 ns — with one honest caveat.

Deciding who's suspicious in the first place

1. Fingerprint beyond the IP. TLS ClientHello ordering (JA3/JA4 hash) exposes the actual client library — a "Chrome" User-Agent with a Python-requests JA3 is lying. HTTP/2 SETTINGS order and header order fingerprints similarly. Attackers rotate IPs cheaply; rotating a TLS stack is expensive. Always key detection on what's expensive to fake.
2. Behavioral stats per key. Request-rate percentiles, path entropy (scanners touch many 404s), inter-arrival regularity (bots are metronomes, humans are bursty), impossible geography (same session, two continents, 3 min apart). Count-min sketches + EWMA keep this O(1) per request.
3. Score, don't binary-block. Reputation score per fingerprint → tiered response: full service / rate-limited / challenged / tarpitted / dropped.

Kubernetes: the machine that runs your gateway fleet

The one idea underneath everything: reconciliation

Kubernetes is not a scheduler with an API bolted on. It is a database of desired state (etcd) plus a swarm of controllers, each running the same loop forever: observe actual state → diff against desired → act to shrink the diff. You never command "start a container"; you declare "3 replicas should exist" and controllers conspire until reality matches. This is why K8s self-heals: a dead pod is just a diff, and diffs get fixed.

What each piece really does (and the why behind its shape)

• kube-apiserver — the only door. Every request passes authn (certs/tokens/OIDC) → authz (RBAC) → admission webhooks (mutate/validate — this hook is how Istio injects sidecars, §08). It's stateless and horizontally scalable because all state lives in etcd. Its killer feature is watch: long-lived streams pushing object changes to every controller/kubelet — that's how 5,000 nodes stay current without polling melting the API.
• etcd — Raft-replicated KV store; every write is a quorum commit (2 of 3, 3 of 5). Why Raft? Split-brain on cluster state ("both halves think they own the pods") is catastrophic; quorum makes a minority partition read-only-and-safe instead of divergent. This is also etcd's cost: ~thousands of writes/sec, latency-sensitive to disk fsync — which is why K8s clusters cap around ~5k nodes and why you never store app data in etcd.
• scheduler — watches for pods with no node; two phases: filter (kick out nodes that can't: insufficient CPU, taints, port clash, affinity) then score (rank the survivors: spread, bin-packing, image locality), then writes one field: spec.nodeName. It only suggests; kubelet does the work.
• kubelet — the node agent. Watches "pods bound to me", drives the container runtime over CRI (containerd → runc), sets up cgroups (CPU/mem limits) and namespaces, runs liveness/readiness probes, reports status. Readiness vs liveness — the interview classic: readiness failing removes the pod from Service endpoints (stop sending traffic, don't kill); liveness failing restarts the container. Wiring a dependency check (DB reachable?) into liveness causes restart storms during a DB blip — one of the most common self-inflicted outages.
• Container = namespaces + cgroups, no magic. PID/net/mount/UTS/IPC namespaces give isolation of view; cgroups give isolation of consumption; it's all ordinary processes on the host kernel. Pods exist because the sidecar pattern needs two containers sharing one network namespace — "pod" is literally "a shared set of namespaces".

Services and kube-proxy: the load balancer that isn't there

A Service (ClusterIP 10.96.7.20:80) is a virtual IP — no process listens on it, no box hosts it. kube-proxy on every node watches Services/EndpointSlices and programs the kernel: "packets to 10.96.7.20:80 → DNAT to one of [pod IPs]". The load balancing happens inside the sender's own kernel at connection time.

conceptually, what kube-proxy writes (iptables mode)
-A KUBE-SERVICES -d 10.96.7.20/32 -p tcp --dport 80 -j KUBE-SVC-XYZ
-A KUBE-SVC-XYZ -m statistic --mode random --probability 0.333 -j KUBE-SEP-A   # → 10.244.1.5
-A KUBE-SVC-XYZ -m statistic --mode random --probability 0.500 -j KUBE-SEP-B   # → 10.244.2.9
-A KUBE-SVC-XYZ -j KUBE-SEP-C                                                  # → 10.244.3.4

Traffic from the internet inward

NodePort (every node opens 3xxxx port) → LoadBalancer (cloud LB → NodePorts) → Ingress / Gateway API: one L7 proxy deployment (nginx-ingress or Envoy) receives everything and routes by host/path to Services. The ingress controller is just the reconciliation pattern again: watch Ingress objects → render nginx.conf / Envoy xDS → hot-reload. Everything you learned in §02–06 applies verbatim to that pod fleet; §04's distributed rate limiting exists because the ingress is a fleet.

Envoy: the network stack you deploy instead of writing

Why the sidecar pattern exists at all

Every service needs the same networking features: mTLS, retries with budgets, timeouts, circuit breaking, telemetry, rate limits. Option A: a library per language (Java, Go, Python, Node…) — you now maintain N implementations, and upgrading means redeploying every service on every team's schedule. Option B: put one proxy next to each service instance, and force all traffic through it. Features become platform config; the app thinks it's talking plaintext on localhost.

How traffic gets captured: the iptables trick

The app is unmodified — so who reroutes its packets? An init container (injected by the mutating admission webhook from §07, or a CNI plugin) runs once with NET_ADMIN and writes iptables rules inside the pod's own netns:

inside the pod netns (conceptual)
iptables -t nat -A OUTPUT   -p tcp -j REDIRECT --to-port 15001  # app's outbound → envoy
iptables -t nat -A PREROUTING -p tcp -j REDIRECT --to-port 15006 # inbound → envoy first
# envoy's own uid 1337 exempted, or loops forever

Envoy learns the packet's original destination via SO_ORIGINAL_DST and routes accordingly. The app dialed payments:8080; Envoy intercepted, upgraded to mTLS, applied policy, load-balanced to a specific pod, and told nobody.

The four nouns + the API that feeds them

• Listener (LDS): an address to accept on, plus its filter chains — where TLS terminates.
• Filters: the extensibility spine. Network filters (tcp_proxy, mongo) and HTTP filters (jwt_authn, ext_authz, ratelimit, fault, WASM for custom logic). This is the slot where an AI-gateway's prompt-inspection filter conceptually lives: a body-buffering/streaming HTTP filter that scores content before router forwards it.
• Route (RDS): virtual hosts, path matches, per-route policy (timeouts, retries, mirror, traffic split 99/1 → canary).
• Cluster (CDS) + Endpoints (EDS): named upstreams with LB policy, health checks, circuit breakers, outlier detection (ejects a pod that starts throwing 5xx — passive health checking nginx OSS lacks).

Istio in three sentences

istiod (control plane) watches K8s (Services, pods, its own CRDs like VirtualService/DestinationRule), compiles them into per-proxy Envoy config, and streams it over xDS. The webhook injects the sidecar + init container into every pod at admission. istiod is also the CA: it signs each sidecar's workload certificate — which is the bridge into §09.

mTLS: both ends prove who they are — down to the bytes

First, plain TLS 1.3 in one breath

ClientHello (supported ciphers + client's ephemeral ECDHE public key) → ServerHello (chosen cipher + server's ephemeral key) → both sides compute the same shared secret (ECDHE) → server sends its certificate + CertificateVerify (a signature over the handshake transcript made with the private key matching the cert) → Finished. Client checks: cert chains to a trusted CA, name matches, signature valid. One round trip; everything after ServerHello is already encrypted.

What the "m" adds

The CertificateVerify is the part people miss: presenting a cert proves nothing (certs are public). The client signs the entire handshake transcript with its private key — proving possession of the key and binding the proof to this handshake, so it can't be replayed into another session.

Build a working mTLS pair by hand (know the plumbing before automating it)

1 · your own CA
openssl req -x509 -newkey ec -pkeyopt ec_paramgen_curve:P-256 \
  -keyout ca.key -out ca.crt -days 365 -nodes -subj "/CN=demo-mesh-ca"

2 · server cert (SAN is what's verified — CN matching is dead)
openssl req -newkey ec -pkeyopt ec_paramgen_curve:P-256 -keyout sv.key -out sv.csr \
  -nodes -subj "/CN=payments"
openssl x509 -req -in sv.csr -CA ca.crt -CAkey ca.key -CAcreateserial -days 30 \
  -out sv.crt -extfile <(printf "subjectAltName=DNS:payments.default.svc")

3 · client cert — identity as a URI SAN, SPIFFE-style
openssl req -newkey ec -pkeyopt ec_paramgen_curve:P-256 -keyout cl.key -out cl.csr \
  -nodes -subj "/CN=orders"
openssl x509 -req -in cl.csr -CA ca.crt -CAkey ca.key -CAcreateserial -days 30 \
  -out cl.crt -extfile <(printf "subjectAltName=URI:spiffe://demo/ns/default/sa/orders")

4 · nginx as the mTLS server
server {
    listen 443 ssl;
    ssl_certificate     sv.crt;   ssl_certificate_key sv.key;
    ssl_client_certificate ca.crt;
    ssl_verify_client on;                      # the one line that makes it mutual
    location / { proxy_set_header X-Peer $ssl_client_s_dn; proxy_pass http://127.0.0.1:8080; }
}

5 · prove it
curl https://payments/  --cacert ca.crt                      # → 400: no client cert
curl https://payments/  --cacert ca.crt --cert cl.crt --key cl.key   # → 200

The same thing, mesh-automated

istio: two objects = encrypted + authorized fleet
apiVersion: security.istio.io/v1
kind: PeerAuthentication
metadata: {name: default, namespace: prod}
spec:
  mtls: {mode: STRICT}          # plaintext to any pod in prod is now refused
---
apiVersion: security.istio.io/v1
kind: AuthorizationPolicy
metadata: {name: payments-callers, namespace: prod}
spec:
  selector: {matchLabels: {app: payments}}
  rules:
  - from:
    - source:
        principals: ["cluster.local/ns/prod/sa/orders"]   # cert SAN, not IP!
    to:
    - operation: {methods: ["POST"], paths: ["/charge"]}

• Issuance loop: Envoy's SDS asks the node agent for a cert → agent creates a key + CSR bound to the pod's ServiceAccount token → istiod validates the token with the K8s API, signs a cert with SAN spiffe://cluster.local/ns/prod/sa/orders → delivered to Envoy in memory (never touches disk). Lifetime ~24 h, rotated at ~half-life, automatically, fleet-wide.
• Why short-lived certs instead of revocation lists: CRL/OCSP distribution across 10k proxies is a hard, failure-prone push system; a 24 h expiry makes revocation a default outcome — stop issuing, and the identity dies within a day; kill the SA for instant effect. Short lifetime converts a hard distributed-systems problem into a clock.
• Why identity = ServiceAccount, not IP: pod IPs are recycled in seconds — yesterday's payments IP is today's cart. Firewall-by-IP in K8s is guessing; policy written against cryptographic identity survives rescheduling, scaling, and node failure. That is "zero trust" said concretely.
• Migration reality: nobody flips STRICT on day one; PERMISSIVE mode accepts both plaintext and mTLS so you can watch the plaintext fraction drop to zero in telemetry, then lock. Mentioning PERMISSIVE→STRICT is how you show you've actually rolled this out.

The why-not table: every decision, its rival, its number

Practice format: choice → rejected alternative → the quantitative reason. If you can deliver each row in ~20 seconds, you own the material.

Five questions to rehearse out loud

1. "Walk me through a request from browser to pod." Use FIG 0 order: DNS/GSLB → anycast/BGP → L4 ECMP → kernel queues → nginx phases → ingress Service → kube-proxy DNAT → Envoy inbound (mTLS) → localhost app. Name one failure mode per hop.
2. "Design rate limiting for a multi-region API." Start with the contract (protection vs quota), then layered limits, then local-buckets-plus-async-reconciliation, then the fail-open/fail-closed call.
3. "Nginx is at 90% CPU — go." user vs sys split → TLS handshake rate (resumption? keepalive?) → flame graph → accept-queue overflow check → only then scale out.
4. "Why is one pod hot behind a Service?" gRPC over connection-level DNAT → L7 balancing in the sidecar (least-request) fixes it.
5. "How would you inspect AI-bound traffic in this stack?" An Envoy HTTP filter at the egress/gateway tier: buffer-or-stream trade (§02 buffering tension), cheap pattern pass before expensive ML scoring (§06 pipeline order), fail-policy per route (§05). The whole manual composes into this answer.

TLS interception: seeing inside traffic that was designed to be unseeable

Everything so far was a reverse proxy: you own the destination, so you own the certificate, so decryption is your right. A secure-access / IA gateway is the opposite animal — a forward proxy: your employees and agents talking to other people's servers (openai.com, drive.google.com, a random paste site). TLS was explicitly engineered to stop a middlebox from reading that. So how does an inspection gateway do it legitimately?

Break-and-inspect, mechanically

1. Trust is pre-installed. Enterprise device management (MDM) pushes the corporate root CA into every managed device's trust store. This is the entire legal/technical basis: interception only works on devices that opted into the CA. Unmanaged devices get a cert warning — which is the correct outcome.
2. Client connects. The gateway learns the intended destination from the SNI field of the ClientHello (or from explicit-proxy CONNECT api.openai.com:443). It mints — and caches — a leaf certificate for that exact name, signed by the corp CA, and completes TLS session A as if it were the server.
3. Gateway connects outward. Session B to the real server, where the gateway behaves as a strict client: full WebPKI chain validation, hostname check, minimum TLS version. If the gateway skips this, it has silently downgraded every user's security to nothing — historically the #1 audit finding against inspection middleboxes.
4. Between A and B is plaintext. Request headers, bodies, prompts, file uploads. This is where §12's pipeline runs.

The protocol arms race: where visibility is eroding

The content inspection pipeline: Aho-Corasick first, ML second

You now have plaintext (from §11's gap, or natively at a reverse proxy). Budget: a few milliseconds per request, at hundreds of thousands of requests per second, scanning for thousands of things at once — DLP patterns, credentials, malware signatures, prompt-injection markers, tenant-specific keywords. The architecture that survives this budget is always the same shape: a cheap deterministic stage that touches every byte, gating an expensive probabilistic stage that touches few. Same law as §06's pipeline ordering, applied inside one request.

Stage 1: multi-pattern matching — why Aho-Corasick

Naive approach: run 5,000 patterns as 5,000 regex/string searches → cost is O(patterns × text). At 5k patterns over a 100 KB body that's dead on arrival. Aho-Corasick (1975, and still what powers Snort/DLP engines) matches all patterns in one pass over the text, O(text + matches) — cost is independent of pattern count.

• Build (offline, once per ruleset): insert all patterns into a trie; BFS to compute each node's failure link = the node for the longest proper suffix of the current path that is also some pattern's prefix. Merge output sets along failure chains.
• Scan (hot path): for each input byte, follow the goto edge; on mismatch, hop failure links until one matches (amortized O(1) — you can never fail back more than you advanced). Emit outputs at marked nodes. The text pointer never moves backwards — which is exactly the property that makes streaming (below) possible.
• Memory shape matters more than big-O: a dense 256-way goto table per node is fastest but fat; production engines (Hyperscan-class) compress states and use SIMD to chew multiple bytes per cycle. The interview-level point: stage 1 is memory-bandwidth-bound, not CPU-logic-bound.

Stage 2: the ML pass — and the gate between the stages

• What stage 1 can't see: paraphrased exfiltration, novel prompt injection ("ignore previous instructions" has infinite rewordings), intent. That needs a classifier — transformer-scale, ~1–50 ms on accelerators, thousands of times costlier per byte than stage 1.
• The gate: stage 1's verdict + cheap features (destination category from §11 SNI, user risk tier from §13, content type, entropy — high-entropy blobs are keys/ciphertext) decide: pass / block / escalate to stage 2. Only a few percent of traffic should ever reach the model. If 100% does, the design has failed regardless of model quality.
• Placement: in Envoy terms this is an ext_proc/WASM HTTP filter streaming body chunks to a scoring service over gRPC — the same shape as §05's ext_authz, generalized from headers to bodies.

The streaming problem: scanning what you refuse to buffer

§02 set up this tension: inspection wants the full body; LLM token streams and uploads want zero added latency. The resolution:

Agentic traffic and continuous access: when the "user" is software

Every model so far quietly assumed a human behind the request: bursty arrival patterns (§06), interactive login (§05), sessions that end when someone sleeps. AI agents break each assumption: they run 24/7, fan one instruction into hundreds of API calls, hold tokens far longer than any human session, and chain identities ("user asked agent, agent calls tool, tool calls API — who is this request?"). A gateway that can't answer that question can't police it.

Telling agents from humans (and from bots)

Identity chains: on-behalf-of, not shared secrets

• The anti-pattern: pasting a user's long-lived API key into an agent. Now an autonomous, prompt-injectable program (§12) holds full user power indefinitely, and logs can't distinguish agent actions from the human's.
• The pattern: the agent is a first-class principal (its own §09-style workload identity) that performs token exchange / on-behalf-of: presents the user's token + its own credential to the IdP, receives a token whose claims say "actor = agent, subject = user, scope = the narrow thing being done, TTL = minutes". Audit, rate limits (§04 — per agent quotas, since one agent equals hundreds of humans in RPS), and blast radius all follow from the token shape.

CAE: killing the token you already issued

§05's compromise was "short expiry ≈ revocation". Agents strain it: they refresh forever, so a compromised agent self-renews indefinitely; and even a 15-minute window is long for a machine doing thousands of ops/minute. Continuous Access Evaluation upgrades the model from timer-based to event-based:

Down to the metal: where the next 10× lives after config tuning

§03 tuned nginx. This section is what you do when the config is already perfect and the graphs say the machine itself is the ceiling. The unifying theme: at millions of packets per second, the enemy is per-packet fixed costs — syscall crossings, interrupts, memory copies, cache misses — not algorithmic work.

Know your unit costs (memorize this table)

Every technique below is just an attack on one row of this table. Say which row, and the technique explains itself.

Fewer crossings: batching and io_uring

• Batching is everywhere already: epoll returns up to 512 events per wakeup (§02's loop) — one syscall amortized over hundreds of sockets. NIC interrupt coalescing + NAPI polling do the same below the kernel: under load, Linux stops taking one interrupt per packet and polls the ring buffer.
• io_uring goes further: two shared-memory ring buffers (submission + completion) between app and kernel. You write operation descriptors into the ring — read this, write that, accept there — and the kernel consumes them, posting completions back, potentially with zero syscalls in steady state (kernel-side polling mode). It also makes disk I/O genuinely async, closing the one blocking hole §02 needed aio threads for. This is a completion model (like Windows IOCP) vs epoll's readiness model — "tell me when it's done" vs "tell me when I can try".

Fewer copies: zero-copy end to end

• sendfile (§02): file → socket without userspace. But it breaks the moment you must transform bytes — including TLS encryption. Enter…
• kTLS: after the handshake (still done in userspace OpenSSL), the session keys are pushed into the kernel; the kernel (or the NIC itself, with TLS offload hardware) encrypts during transmission. Now sendfile over TLS works — file → kernel encrypt → wire, zero userspace touches. Large-object serving (video, model weights, artifact registries) sees double-digit CPU savings.
• MSG_ZEROCOPY / RX zero-copy: pin user pages and let the NIC DMA directly — worth it above ~10 KB per send (page-pinning bookkeeping eats the win below that; the kernel documents exactly this threshold behavior).

Fewer kernels: XDP, eBPF, DPDK

Memory locality: NUMA, RSS, and false sharing

• RSS/RPS: the NIC hashes each flow's 5-tuple to a queue, each queue interrupts a fixed CPU — so one connection's packets always land on the same core, keeping its state hot in that core's cache. This is §02's per-core worker model extended down into silicon; reuseport + IRQ affinity align the whole path NIC-queue → CPU → worker.
• NUMA: a 2-socket box is two computers with a fast link. Cross-socket memory access costs ~1.5–2×, and a NIC is physically attached to one socket. Serious deployments run one nginx/envoy "instance-worth" of workers per socket, memory-local. Symptom of getting it wrong: mysteriously bimodal latency histograms.
• False sharing: two counters on the same 64-byte cache line, updated by different cores, ping-pong the line between caches — a "lock-free" stats array can serialize the whole fleet of cores. Fix: pad hot per-core counters to line size, aggregate on read. This is why nginx shm zones (§04) and Envoy stats are structured per-worker with periodic merge, not shared atomics per event.

Resilience: designing for the day the graphs go vertical

Fast systems die differently than slow ones: they die by positive feedback loops. A small slowdown triggers retries, retries add load, load adds slowdown. Every pattern in this section exists to break one specific loop. Learn them as loop-breakers and you'll never mix them up again.

Anatomy of a cascading failure (the canonical incident)

End state of an unprotected system: every server busy doing work that will time out before it's used — 100% utilization, 0% goodput, and it stays there even after the DB recovers because the retry backlog sustains the overload. This is a metastable failure; recovery requires shedding load, not adding capacity.

The loop-breakers, each matched to its loop

• Timeouts with a deadline budget. Not "30 s everywhere" — a per-request deadline set at the edge and propagated (gRPC deadline / header) so a call 5 hops deep knows only 80 ms remain and gives up instead of doing doomed work. Rule: your timeout ≥ dependency's p99.9, and inner timeouts strictly shorter than outer — inverted nesting means the outer layer retries while the inner call still runs: hidden load multiplication.
• Retries under a budget, with jittered backoff. Retry only idempotent ops, only on transient signals; exponential backoff spreads them in time; full jitter (uniform 0..backoff) spreads them so recovered servers aren't hit by a synchronized thundering herd. The crucial fleet-level control is a retry budget (Envoy: e.g. retries ≤ 20% of active requests): 3-attempts-each is per-caller and multiplies through layers (3 hops × 3 attempts = up to 27× at the bottom); a budget caps the multiplier globally.
• Circuit breakers. When a dependency's failure rate crosses a threshold, stop calling it entirely (open); after a cooldown, probe with a trickle (half-open); resume on success (closed). Breaks the "keep paying timeout-latency for guaranteed failures" loop and gives the dependency air to recover. Envoy splits this into connection/request/pending caps ("circuit breakers") plus outlier ejection (per-endpoint 5xx tracking, §08) — mention both to show you've read the actual knobs.
• Load shedding at admission. The gateway's version of triage: when queue depth / concurrency crosses the knee (§03), reject excess immediately with 429/503 + Retry-After. A fast no costs microseconds; a slow yes that times out costs the full work plus a retry. Shed by criticality class: checkout traffic survives, batch/scraper/optional-personalization traffic sheds first — which requires you to have labeled request criticality in advance (do that; almost nobody does until their second outage).
• Backpressure. Bounded queues everywhere, and when a queue fills, the fullness propagates upstream (TCP flow control, HTTP/2 window, or explicit rejection) instead of buffering unboundedly. §12's buffer caps were this; an unbounded queue is a promise to fail with OOM later instead of a 503 now.

Deployment resilience: assume the bug ships

Most incidents are self-inflicted by change. The gateway stack is also the safety mechanism: canary via §08 traffic-split (1% → compare error/latency vs baseline automatically → promote or auto-rollback); cell-based isolation — partition the fleet into independent cells, each with its own gateways/limiters/state, deploy cell-by-cell so blast radius is 1/N of users and a poisoned config (§02's reload makes config a deploy too!) can't take the world down; feature flags for instant behavioral rollback without a rollout. Config and rulesets (§12's patterns, §06's blocklists) need the same canary treatment as code — a bad regex pushed globally is the outage.

Observability: measuring a billion requests without a second billion-request problem

Instrumentation at scale has one central tension: the telemetry system's load scales with the traffic it watches. Every design below is a different answer to "how do we know everything while storing almost nothing?"

Metrics: the cardinality trap

Tracing: the request's own story

• Mechanics: the edge mints a trace ID; every hop creates a span (name, start, duration, parent) and propagates context in headers (W3C traceparent). The sidecar (§08) creates spans for free at every hop boundary — but the app must copy the headers from inbound to outbound requests, or the trace shatters. Envoy cannot do that for you; this is the single most common "why are my traces broken" answer.
• Sampling is the whole design. Storing every span at 1B req/day is a second data platform. Head sampling (decide at the edge, e.g. 0.1%) is cheap but decides before knowing if the request is interesting — you keep a million boring traces and miss the one 30-second outlier. Tail sampling buffers each trace briefly at the collector and keeps the interesting ones (errors, slow, rare routes) — 100% of the value at 0.1% of the storage, paid for with collector memory and complexity. Production answer: low-rate head sampling for the baseline + tail rules for anomalies.

Logs at the edge: the firehose discipline

• Structured (JSON/proto) from birth — grep doesn't scale to TB/day; fields do. Nginx: log_format json_combined escape=json … including $request_time, $upstream_response_time, trace ID, route, tenant.
• Budget math you should be able to do live: 1B req/day × ~400 bytes/line ≈ 400 GB/day raw, ~×2 replicated, before indexes. Hence: full logs for errors + sampled success logs (1–10%) + always full metrics (they're cheap). Sampling successes is safe because §16's metrics already count them exactly.
• Local buffering with caps (§15 backpressure applies to telemetry too): when the log pipeline backs up, drop debug-level locally rather than block the data plane. Telemetry must never be able to take down the thing it observes — write that sentence in every design doc.

Closing the loop: SLOs and error budgets

Four staff-level prompts, worked end to end

Format for each: restate → numbers first → architecture → the why-nots you volunteer before being asked → the follow-up the interviewer is holding in reserve. Practice delivering each in 12–15 minutes.

LAB 1 — "Design a shared TTL cache for gateway verdicts across 200 pods"

LAB 2 — "Design the egress gateway that inspects streaming AI traffic for a 100k-employee company"

LAB 3 — "Flash sale in 20 minutes; the edge fell over in the last one. Go."

LAB 4 — "Distribute a 10M-entry, minutely-updated blocklist to 10,000 proxies worldwide"

Active recall: answer aloud before you tap

Reading feels like knowing; retrieval is knowing. Answer each question out loud in full sentences, then open it. Wrong or fuzzy → the cited section is your reread list. Target: all green in two sittings.

Round 1 · Mechanisms — "how does it actually work?"

Round 2 · Numbers — "justify it quantitatively"

Round 3 · Traps — "the misconception the interviewer is fishing for"

Bloom filter & Aho-Corasick: real runs, real traces, real surprises

Everything below was actually executed — the bit positions, false positives, state transitions, and timings are genuine program output, including two accidents that teach more than the plan did. Full runnable source at the end of each half.

Part A · Bloom filter, five experiments

A1 — A 32-bit filter you can verify by eye

Three "malicious" IPs inserted into m=32 bits with k=3 hashes. Watch which bits each key claims:

RUN — insert phase
insert 203.0.113.9    -> bits [2, 5, 25]
insert 198.51.100.7   -> bits [4, 13, 16]
insert 192.0.2.44     -> bits [7, 8, 18]
bit array set positions: [2, 4, 5, 7, 8, 13, 16, 18, 25]  (9/32 set)

Now three queries — one true positive, two true negatives:

RUN — query phase
query 203.0.113.9    -> bits [2, 5, 25]  -> MAYBE (all set)          # true positive: its own bits
query 10.0.0.1       -> bits [1, 8, 11]  -> DEFINITELY NOT          # bit 1 is zero → proof of absence
query 172.16.5.5     -> bits [6, 11, 11] -> DEFINITELY NOT          # bit 6 is zero

Note 172.16.5.5: two of its three hashes landed on the same bit (11, 11). Legal and harmless — k hashes are independent draws, collisions among them just mean fewer distinct bits checked. It matters again in A1's false-positive hunt below.

A2 — Hunting a real false positive

Scan 10.0.0.0/24 — 256 addresses never inserted — and ask the filter about each:

RUN — 42 candidates scanned before 3 FPs found
FALSE POSITIVE: 10.0.0.0    bits [5, 16, 25]  # bit 5 from IP#1, 16 from IP#2, 25 from IP#1
FALSE POSITIVE: 10.0.0.24   bits [4, 5, 25]   # assembled from three different insertions
FALSE POSITIVE: 10.0.0.41   bits [2, 2, 5]    # self-collision! only needs TWO borrowed bits

This is the mechanism of a false positive laid bare: nobody inserted 10.0.0.0, but its three bits were each set by different legitimate insertions, and the filter cannot tell "all set by one key" from "all set by strangers." 10.0.0.41 shows the sharper edge: its internal hash collision means only two foreign bits had to be occupied — self-colliding keys have a higher personal FP probability. This 32-bit toy runs at ~28% fill and shows ~7% FP; that's why real sizing (next) targets ≤1%.

A3 — Theory vs measurement at 200k entries

RUN — sized by the formulas from §06
formula: m = 1,917,012 bits (234 KiB), k = 7, 9.59 bits/entry   # target p = 1%
measured FP rate: 1.064%   (theory ~1%)      # over 50,000 known non-members
measured FN rate: 0.000%   (theory: exactly 0, always)   # over 50,000 known members

The formulas are not approximations you hope hold — they land within measurement noise. 234 KiB for 200k keys; linearly, ~12 MB for 10M, confirming §06's claim from live code.

A4 — Saturation: what happens when you lie to the filter about n

RUN — same filter (sized for 200k), kept inserting
after 200,000 inserts: bits set  ~50%    FP rate   1.06%   # as designed
after 400,000 inserts: bits set  76.7%   FP rate  15.80%
after 600,000 inserts: bits set  88.8%   FP rate  43.42%   # nearly a coin flip

Fill fraction follows 1 − e^(−kn/m): plug n=400k in and you predict 76.8% — measured 76.7%. FP rate is (fill)^k, and it explodes: 2× overfill → 15× the error, 3× → 40×. Operational lesson: a Bloom filter fails silently and gradually — no exception, no OOM, just quietly rising junk verdicts. So production filters export their fill ratio as a metric (§16) and alert well before 60%, and the §06 rebuild-every-minute pipeline re-sizes from the current n each build.

A5 — Deletion: the counting variant, and its cost

RUN — counters instead of bits
query evil.example after insert : True
query evil.example after delete : False
query bad.example  (untouched)  : True   # shared positions survived: counters went 2→1, not 1→0

Plain Bloom can't delete — clearing a bit might destroy another key's evidence (exactly the sharing A2 exposed). Counting Bloom stores a small counter per position: delete = decrement, and shared positions survive. Price: 4-bit counters = 4× memory, and counter overflow must be handled (saturate, don't wrap). This is the honest bridge to §06's cuckoo-filter aside: if deletion is frequent, cuckoo beats counting-Bloom on space; if the set is rebuilt wholesale each minute, plain Bloom stays cheapest. Choose by the update pattern, not the lookup pattern.

import hashlib, math

def h(key, seed, m):
    d = hashlib.sha256(f"{seed}:{key}".encode()).digest()
    return int.from_bytes(d[:8], 'big') % m

class Bloom:
    def __init__(self, m, k):
        self.m, self.k, self.bits = m, k, bytearray((m+7)//8)
    def _idx(self, key):
        return [h(key, i, self.m) for i in range(self.k)]
    def add(self, key):
        for i in self._idx(key):
            self.bits[i//8] |= 1 << (i % 8)
    def query(self, key):                     # all() short-circuits on first zero bit
        return all(self.bits[i//8] >> (i%8) & 1 for i in self._idx(key))

def size_for(n, p):                           # §06 formulas
    m = math.ceil(-n * math.log(p) / (math.log(2)**2))
    k = max(1, round(m/n * math.log(2)))
    return m, k

class CountingBloom(Bloom):                   # deletable variant (A5)
    def __init__(self, m, k):
        self.m, self.k, self.cnt = m, k, [0]*m
    def add(self, key):
        for i in self._idx(key): self.cnt[i] += 1
    def remove(self, key):
        for i in self._idx(key): self.cnt[i] -= 1
    def query(self, key):
        return all(self.cnt[i] > 0 for i in self._idx(key))
# production notes: use 2 fast hashes + Kirsch-Mitzenmacher (h1+i*h2), not k sha256s;
# store bits in one contiguous array for cache locality (§14); export fill%% as a metric (§16)

Part B · Aho-Corasick, five experiments

B1 — The automaton for {he, she, his, hers}, fully dumped

RUN — every state: its path, goto edges, fail link, outputs
state  path    goto edges          fail   outputs
    0  [    ]  h->1, s->3            0    []
    1  [h   ]  e->2, i->6            0    []
    2  [he  ]  r->8                  0    ['he']
    3  [s   ]  h->4                  0    []
    4  [sh  ]  e->5                  1    []          # suffix "h" of "sh" = prefix of he/his
    5  [she ]                        2    ['she', 'he']  # inherits he via fail chain!
    6  [hi  ]  s->7                  0    []
    7  [his ]                        3    ['his']
    8  [her ]  s->9                  0    []
    9  [hers]                        3    ['hers']

Two things to point at. State 4's fail link = 1: after reading "sh", the longest suffix that is also some pattern's prefix is "h", so a mismatch resumes from the "h" state instead of root — no rescanning. State 5's output list contains he even though its path spells "she": outputs are merged down the fail chain at build time, which is why finishing "she" reports the overlapping "he" for free.

B2 — Positive trace: scanning "ushers"

RUN — one state integer, six characters, three matches
read 'u'  state  0 -> 0
read 's'  state  0 -> 3
read 'h'  state  3 -> 4
read 'e'  state  4 -> 5   MATCH: she@1  he@2     # two overlapping patterns, one step
read 'r'  state  5 -> 8   # "she"+r has suffix "her" → jumped INTO the hers branch via fail
read 's'  state  8 -> 9   MATCH: hers@2
matches: [(1,'she'), (2,'he'), (2,'hers')]

The 5→8 transition is the algorithm's soul: state 5 has no 'r' edge, so it falls to state 2 ("he"), which does — landing in "her". Three overlapping matches found in exactly six character-steps; a naive scanner would have re-read characters multiple times.

B3 — The "negative" trace that wasn't: an honest accident

This text was chosen as a true negative — "hazard shiv herd", full of near-misses. Watch what the run actually said:

RUN — near-misses dying via fail links… and one surprise
read 'h'  state 0 -> 1        # "hazard": h looks promising…
read 'a'  state 1 -> 0        # …'a' kills it, fail to root, no rescan
...
read 's'  state 0 -> 3        # "shiv": s-h builds "sh" (state 4)…
read 'h'  state 3 -> 4
read 'i'  state 4 -> 6        # no 'i' edge at 4 → fail to 1 ("h") → h+i = "hi"! pivoted mid-word
read 'v'  state 6 -> 0        # 'v' ends the "his" hope
...
read 'e'  state 1 -> 2   MATCH: he@12   # inside "herd" (!)
read 'r'  state 2 -> 8
read 'd'  state 8 -> 0
matches: [(12, 'he')]

Two lessons, one intended and one earned. Intended: the 4→6 pivot — "shi" seamlessly re-interpreted as "…hi" without moving the text pointer backwards. Earned: "herd" contains "he" — substring matchers do not know about word boundaries. In DLP terms: the pattern ssn fires inside "expressnotes"; a credit-card digit pattern fires inside a phone number. Production stage-1 therefore emits candidates, and a cheap post-filter (boundary check, checksum like Luhn for card numbers, context window) validates before the verdict — yet another instance of the manual's cheap-gate-then-verify pattern (§06, §12). A "false positive" here is not a bug in Aho-Corasick; it's the designed division of labor.

B4 — Streaming across the worst possible chunk boundary

Same "ushers" input, deliberately split so that both matches span chunk edges:

RUN — chunks "us" | "he" | "rs", carrying one integer of state
chunk 'us': state out 3, matches so far []
chunk 'he': state out 5, matches so far [(1,'she'), (2,'he')]   # "she" completed ACROSS the cut
chunk 'rs': state out 9, matches so far [(1,'she'), (2,'he'), (2,'hers')]
final == whole-text scan: identical

This is §12's claim, demonstrated: the automaton's entire memory is one state integer, so a gateway scanning a streamed LLM response or chunked upload stores 4 bytes per connection of scanner state — no buffering, no overlap windows, no missed boundary-spanning secrets. (The ML stage still needs windowed context; only the automaton stage gets this superpower.)

B5 — The scaling benchmark, with an honest handicap

RUN — 1 MB text; naive = one C-speed text.find() per pattern; AC = pure Python
patterns    naive k-scans        AC single pass
     100        0.078 s             0.266 s      # AC loses! interpreter tax
   1,000        0.787 s             0.342 s      # crossover
   5,000        3.931 s             0.517 s      # 7.6× — and growing linearly apart
(match counts agree at every size)

Read the shape, not the absolute numbers. Naive scales linearly with pattern count (0.078 → 3.93 s, a clean 50× for 50× patterns). AC is nearly flat (0.27 → 0.52 s — growth is only automaton cache pressure). And this is pure-Python AC giving compiled C a ~30× head start per operation; at parity (Hyperscan-class engines, SIMD, §12) the crossover moves from ~500 patterns to ~a handful. At §12's real scale — thousands of patterns, every byte of every request — the naive approach isn't slower, it's architecturally impossible: 5,000 passes over each request body versus one.

from collections import deque

class AC:
    def __init__(self, patterns):
        self.goto, self.fail, self.out = [{}], [0], [[]]
        for p in patterns:                        # 1) trie of all patterns
            s = 0
            for ch in p:
                if ch not in self.goto[s]:
                    self.goto.append({}); self.fail.append(0); self.out.append([])
                    self.goto[s][ch] = len(self.goto) - 1
                s = self.goto[s][ch]
            self.out[s].append(p)
        q = deque()                               # 2) fail links by BFS (depth order matters:
        for ch, s in self.goto[0].items():        #    a node's fail is always shallower)
            q.append(s)                           #    depth-1 nodes fail to root
        while q:
            r = q.popleft()
            for ch, s in self.goto[r].items():
                q.append(s)
                f = self.fail[r]                  # follow parent's fail chain until an
                while f and ch not in self.goto[f]:   # ancestor has a ch-edge
                    f = self.fail[f]
                self.fail[s] = self.goto[f].get(ch, 0)
                if self.fail[s] == s: self.fail[s] = 0
                self.out[s] += self.out[self.fail[s]] # 3) inherit outputs (why she⇒he)

    def step(self, state, ch):                    # amortized O(1): fails only give back
        while state and ch not in self.goto[state]:   # depth that gotos paid for
            state = self.fail[state]
        return self.goto[state].get(ch, 0)

    def scan(self, text, state=0, base=0):        # state in/out ⇒ streaming (B4)
        hits = []
        for i, ch in enumerate(text):
            state = self.step(state, ch)
            for p in self.out[state]:
                hits.append((base + i - len(p) + 1, p))
        return state, hits
# production notes: dense 256-wide goto arrays or double-array tries beat dicts (§14
# memory-bandwidth point); precompute the "next" DFA table to remove the fail loop
# from the hot path entirely; case-fold/normalize input BEFORE scanning or attackers
# trivially bypass with mixed case (normalization is itself attack surface — §12)

Consistent hashing & count-min sketch: the other two gateway workhorses

The manual leaned on both without opening them: consistent hashing carries §01's L4 tier and Lab 1's cache tier; count-min sketch powers §06's "which keys are hot right now." Same rules as §19 — every number below is real program output (200k keys / 1M-request zipfian stream).

Part A · Consistent hashing, three experiments

A1 — Why mod-N is a fleet-wide cache wipe

RUN — hash(key) mod N, growing 10 → 11 nodes
keys moved: 181,965 / 200,000 = 91.0%    (theory: 1 − 1/11 = 90.9%)

Adding one node relocated 91% of keys. Meaning, concretely: scale your cache tier up by 10% and you just invalidated 91% of it — a self-inflicted stampede (§17 Lab 1) at the exact moment you added capacity because load was high. The failure isn't performance, it's coupling: with mod-N, every key's placement depends on N itself, so any change of N changes almost everything. Consistent hashing's entire purpose is to make placement depend only on the key and the surviving nodes.

A2 — The ring, and what virtual nodes actually buy

RUN — ring: remap when adding node #11, and load balance across 10 nodes
 vnodes   moved on add   max/mean load   load stddev
      1        1.11%          2.24×         76.3%
     10       11.91%          1.54×         29.7%
    100       10.19%          1.07×          4.8%
   1000        9.01%          1.05×          3.5%
(theory for moved-on-add: 1/11 = 9.09%)

Two lessons hiding in one table:

• The vnodes=1 row is a trap worth staring at. Only 1.11% moved — better than theory? No: with one point per node, the new node claims one random arc whose size has huge variance; this run happened to land a small arc. The same variance shows up as 2.24× overload on the unluckiest node. Low-vnode rings aren't wrong on average — they're wrong in variance, and production dies of variance (§03's tail-latency arithmetic, resurfacing in placement).
• Vnodes are a variance knob. 100–1000 points per node concentrates both metrics toward theory: ~9% movement (exactly the unavoidable 1/(N+1)) and ~1.05× worst-case load. Cost: ring size × vnodes entries and log(ring) lookup — trivial. This is why Cassandra/Dynamo-style systems default to hundreds of tokens per node.

A3 — Maglev: trading a little churn for perfect balance

RUN — Maglev lookup table, M = 6007 slots, 10 backends
balance: min 600, max 601 slots (ideal 600)  →  max/mean 1.000×
remove node9: keys moved 10.94%
  unavoidable (node9's own keys):     10.00%
  collateral churn (didn't have to):   0.93%

Each backend generates a permutation of table slots (from two hashes: offset + skip) and backends take turns claiming their next preferred free slot until the table fills. Result measured above: balance is essentially perfect by construction (600 vs 601 slots), and lookup is a single array index — table[hash % M], no binary search, exactly what a §14-grade per-packet path wants.

The price is printed too: removing a node moved 10.94% of keys when only 10.00% had to move — 0.93% of keys were collateral churn, remapped despite their backend surviving. The ring never does that; Maglev accepts it deliberately.

Part B · Count-min sketch, four experiments

Setup: 1M requests from 100k client keys, zipf-distributed (few whales, long tail) — the honest shape of gateway traffic. Sketch: 4 rows × 2000 counters = 31 KiB, vs ~3.8 MB for the exact Counter. Structure: on add, increment one counter per row (row's own hash); on read, take the min across rows.

B1 — Heavy hitters: estimates vs truth

RUN — top clients, estimated from 31 KiB
   key      true   estimate   overcount
   ip0   134,634    134,725         +91
   ip1    63,421     63,557        +136
   ip2    40,329     40,397         +68
   ip3    29,403     29,532        +129
   ...      (all 8 shown in source run: overcounts +62…+170)

For the keys you actually care about — the whales — error is ~0.1–0.6%: collision noise from tail keys adds a few dozen counts to six-figure truths. The sketch is nearly exact precisely where precision matters, and that's structural: overcount magnitude is bounded by other keys' mass landing in your cells, which is the same for everyone — so it's relatively negligible for big counts and relatively brutal for small ones (B3).

B2 — The one-sided guarantee, measured across all 100k keys

RUN — error direction and bound
underestimates: 0            (theory: impossible — counters only increment, min() of
                              overestimates is still an overestimate)
mean overcount: 100    max: 859
within the ε·N = 1,359 bound: 100.00% of keys   (guarantee said ≥ 98.2%: 1 − e^−d)

ε = e/w gives the additive error bound; d rows drive the failure probability down exponentially (each row is an independent chance for a clean min). Both knobs measured landing inside their promises. Recognize the family resemblance: this is the Bloom filter's one-sided error, generalized from membership to frequency. Bloom never says "absent" wrongly; CMS never says "smaller" wrongly.

B3 — Where the error concentrates: the inflated minnow

RUN — worst-inflated key in the whole universe
key ip64982: true count 1  →  estimated 860

A key seen once, estimated at 860: all four of its row-cells happen to be shared with hot keys, and min() can only pick the least-polluted cell, not an unpolluted one. Absolute error (+859) is still inside ε·N — the guarantee never promised small relative error for small keys. Operational consequence: never use raw CMS estimates to punish small counts (e.g., "this IP made ~860 requests, throttle it" — it made one). CMS answers "is this key HUGE?"; for small-count decisions you need exact counters on the shortlist.

B4 — The actual job: detection quality

RUN — flag every key estimated above 0.5% of the stream (5,000)
actual heavy hitters: 20    flagged: 20    missed: 0    false flags: 0

Perfect recall is guaranteed (no underestimates ⇒ no whale can hide under the threshold); perfect precision this run is luck-adjacent (a tail key inflated past 5,000 would be a false flag — and B3's 860 shows the mechanism idling). So the production pattern is the manual's master pattern yet again: CMS as the cheap always-on stage streaming candidates → exact counters kept only for the few flagged keys → §04's limiter or §06's scorer acts on exact numbers. 31 KiB buys you the right to be exact about only twenty keys instead of a hundred thousand.

# --- consistent hash ring ---
class Ring:
    def __init__(self, nodes, vnodes):
        self.ring = sorted((H(f"{n}#v{v}"), n) for n in nodes for v in range(vnodes))
        self.pts  = [p for p, _ in self.ring]
    def owner(self, key_hash):
        i = bisect.bisect(self.pts, key_hash) % len(self.ring)   # clockwise successor
        return self.ring[i][1]

# --- minimal Maglev table ---
def maglev(nodes, M=6007):                       # M prime, M >> len(nodes)
    perm = {n: (H(n+"#off") % M, H(n+"#skip") % (M-1) + 1) for n in nodes}
    table = [None]*M; nxt = {n: 0 for n in nodes}; filled = 0
    while filled < M:
        for n in nodes:                          # round-robin turns = balance
            off, skip = perm[n]
            while True:                          # next free slot in MY permutation
                c = (off + nxt[n]*skip) % M; nxt[n] += 1
                if table[c] is None:
                    table[c] = n; filled += 1; break
            if filled == M: break
    return table                                 # dispatch = table[hash(5tuple) % M]

# --- count-min sketch ---
class CMS:
    def __init__(self, w, d):
        self.w, self.d = w, d
        self.t = [[0]*w for _ in range(d)]
    def add(self, key, c=1):
        for r in range(self.d):
            self.t[r][H2(key, r, self.w)] += c
    def est(self, key):                          # min across rows = least-polluted cell
        return min(self.t[r][H2(key, r, self.w)] for r in range(self.d))
# production notes: decay for "hot NOW" — halve all counters every T seconds, or run
# two alternating sketches (current+previous) and reset the older (§06's rebuild trick);
# use conservative update (only bump cells equal to the current min) to shrink overcounts;
# per-worker sketches merge by cell-wise addition — composable like §16's histograms