AI
Why DNS-Based Routing Failed at Spotify’s Scale
Spotify’s original service discovery system, Nameless, returned a flat list of IPs with no zone metadata. A custom load balancer called ELS (Expected Latency Selector) tried to pick the best IP by latency, but inter-zone and intra-zone latencies were nearly identical, so ELS was blind to zones. Adding a synthetic zone bias helped, but created a concert-bar problem: every client picked the same “shortest line” and overloaded one zone. The result was cross-zone traffic stuck at 40%, down from 70%, with no path to go further.
XDS as a Live Dispatcher: Two-Level Routing
XDS replaced DNS as the routing layer. The Endpoints Discovery Service (EDS) groups endpoints by locality, region, and zone, and assigns percentage weights. The Cluster Discovery Service (CDS) pushes a weighted round-robin load balancing policy to each client. The control plane decides the zone; ELS then picks the specific endpoint inside that zone. This two-level split gave Spotify a global view of every node in the mesh and the ability to push new routing weights in real time, something DNS could never do.
The Zone-Aware Routing Algorithm: Fill Local, Spill the Rest
The routing algorithm follows Envoy’s “fill local and spill the rest” heuristic. For each zone, it calculates how much traffic the local servers can absorb without overloading, keeps that fraction same-zone, then distributes the remainder to other zones proportional to their residual capacity. In a worked example with zones at 40/40/20% client split and 25/50/25% server split, the algorithm achieves 84-85% same-zone traffic. Spotify improved on Envoy’s heuristic by replacing assumed host-count traffic distributions with real per-client load reports from the XDS load reporting service (LRS).
System Architecture: Shameless, Zoneless, and Load Reports
Shameless is the XDS control plane. It watches Kubernetes endpoint slices, holds endpoints in memory, and pushes EDS responses every 10 seconds. Zoneless is a singleton aggregator running on a single beefy VM. It receives load reports from every Shameless instance and returns an aggregated zonal traffic distribution. Shameless feeds that distribution into the routing algorithm, then pushes weights back to clients. Three optimizations keep the pipeline stable: hash-based suppression avoids duplicate pushes, task cancellation prevents memory pressure from degraded networks, and staleness guards revert to unweighted routing when load reports go stale.
Production Incident: A Cold Pod and 30,000 Requests Per Second
A service handling 300,000 requests per second in a single region ran only a few instances and was zonally imbalanced. When the HPA scaled it up and the scheduler placed a new pod in zone C, zone-aware routing immediately assigned that pod 10% of traffic. The pod was still cold-starting with no JIT optimization and near-zero capacity. It received 30,000 requests per second, never recovered, and kept failing until the team was paged in the middle of the night and disabled zone-aware routing. The algorithm’s host-count assumption had no way to detect that the new host could not yet handle load.
Dynamic Capacity Model: Reactive and Proactive Signals
Spotify built the dynamic capacity model to fix the assumption that host count equals real capacity. It has two signals. The reactive signal watches inflight requests per zone from load reports; if one zone’s inflight count grows relative to others, the algorithm reduces that zone’s capacity estimate and redirects traffic. The proactive signal distrusts new hosts entirely, starting them at 5% of a full host and increasing trust only as successful requests accumulate. In experiments, the reactive signal cut errors by 91% on a degraded zone. The slow-start scenario that caused the incident produced zero errors under the new model.
Notable Quotes
we cut our cross zone eress by 75% using our XDS control plane. Yannick Epstein · ▶ 00:29
production sometimes writes its own stories and not everything goes as smooth as the theory uh proposes. Yannick Epstein · ▶ 19:24
you don’t trust new hosts right? You never trust new host. they could be bad hosts. Yannick Epstein · ▶ 23:53
we cut errors by 91% in this case. Yannick Epstein · ▶ 25:24
Key Takeaways
- DNS gave Spotify a flat IP list; XDS gave it per-zone weighted routing across two million nodes.
- The fill-local-spill-the-rest algorithm reaches 84-85% same-zone traffic without overloading any zone.
- Real LRS load reports replaced host-count assumptions, removing the biggest flaw in Envoy’s heuristic.
- A cold pod receiving 30,000 RPS instantly exposed the gap between host count and actual capacity.
- The dynamic capacity model cut degraded-zone errors by 91% and produced zero errors on slow-start pods.
About the Speaker(s)
Yannick Epstein is a Senior Engineer in Spotify’s Core Infrastructure group, where he works on systems that manage traffic and communication between backend services. He led the discovery and engineering effort for Spotify’s custom xDS control plane and the company’s dynamic capacity model.
Anya Hristova is a Senior Software Engineer at Spotify’s Core Infrastructure team, where she specialises in service discovery and backend services communication. She led key initiatives in the move to the custom xDS control plane, its implementation, and the rollout of zone-aware routing across Spotify’s multi-region infrastructure.