Kubernetes load balancing flaw at scale
Databricks drops Kubernetes load balancing for client-side power-of-two-choices, cuts fleet 20% USENIXTL;DW
- Kubernetes load balances connections, not requests; gRPC over HTTP/2 multiplexes thousands of requests per connection, causing severe traffic skew (4-5x) across pods.
- Connection resets, headless services with DNS, and service meshes were rejected as solutions due to CPU overhead, DNS caching issues, control plane inflexibility, or operational complexity.
- Databricks built a custom endpoint discovery service (EDS) using push-based Xds protocol to replace Kubernetes load balancing with client-side intelligence.
- Power-of-two-choices algorithm: randomly select two pods, score each by pending requests plus latency and error rate signals, send to the pod with better score.
- Power-of-two-choices naturally avoids thundering herd problems unlike least-request algorithms, and is simple, cheap, and easily extensible with new scoring signals.
- Uniform request distribution via power-of-two-choices reduced average fleet size by 20% through better autoscaling decisions and latency stability.
- Naive round-robin distribution initially caused cold-start errors when new pods came online; power-of-two-choices with error-rate bias improved robustness during rollouts.
- Solution relies on Kubernetes as control plane source but decouples data plane; works across three clouds, 1500+ clusters, and 70+ regions at Databricks scale.
TL;DW
- Kubernetes load balances connections, not requests; gRPC over HTTP/2 multiplexes thousands of requests per connection, causing severe traffic skew (4-5x) across pods.
- Connection resets, headless services with DNS, and service meshes were rejected as solutions due to CPU overhead, DNS caching issues, control plane inflexibility, or operational complexity.
- Databricks built a custom endpoint discovery service (EDS) using push-based Xds protocol to replace Kubernetes load balancing with client-side intelligence.
- Power-of-two-choices algorithm: randomly select two pods, score each by pending requests plus latency and error rate signals, send to the pod with better score.
- Power-of-two-choices naturally avoids thundering herd problems unlike least-request algorithms, and is simple, cheap, and easily extensible with new scoring signals.
- Uniform request distribution via power-of-two-choices reduced average fleet size by 20% through better autoscaling decisions and latency stability.
- Naive round-robin distribution initially caused cold-start errors when new pods came online; power-of-two-choices with error-rate bias improved robustness during rollouts.
- Solution relies on Kubernetes as control plane source but decouples data plane; works across three clouds, 1500+ clusters, and 70+ regions at Databricks scale.
Kubernetes balances connections, not requests; with gRPC over HTTP/2, some pods received orders-of-magnitude more traffic, causing SLO violations. Databricks built an XDS-based endpoint discovery service enabling client-side scoring on pending requests, latency, and error rate, achieving even distribution and a 20% fleet size reduction with no proxy overhead.