Additional Load Balancing Algorithms

[abdallahsamabd]

Problem

Today Praxis supports five load balancing strategies: round-robin, least-connections, consistent-hash, random, and power-of-two-choices. While these cover common use cases, they are insufficient for large-scale, multi-zone, and heterogeneous deployments:

1. No minimal-disruption hashing — the current consistent-hash implementation remaps ~1/N keys on topology changes and distributes B2's traffic unevenly to ring neighbors. Large clusters with caches or sticky state need Maglev-level guarantees (near-zero collateral movement, even redistribution across all survivors).

2. No configurable ring hash — the current consistent hash uses a fixed hash function (FNV-1a) and fixed virtual node count. Operators cannot tune ring size or hash function for their specific cluster size and distribution requirements.

3. No subset-based routing — there is no way to filter endpoints by metadata labels (e.g., GPU type, service version, canary group) before applying a load balancing algorithm within that subset.

4. No zone-aware routing — the proxy sends traffic equally to all endpoints regardless of locality. Multi-zone deployments incur unnecessary cross-zone egress costs and latency without the ability to prefer same-zone endpoints.

5. No priority tiering — all endpoints are treated equally. There is no way to define primary and failover groups with automatic spillover when primary capacity degrades.

Competing proxies (Envoy, HAProxy, Istio) provide all of these as standard capabilities.

Proposal

Expand the load balancer with the following algorithms:

• Maglev: Google's consistent hash algorithm using a fixed-size lookup table (65,537 slots). Provides near-perfect distribution uniformity, O(1) lookup, and minimal disruption on topology changes (only the removed backend's slots are redistributed, evenly across all survivors).

• Ring hash (configurable): Consistent hash with operator-configurable hash function and ring size, allowing tuning of distribution uniformity vs memory usage for different cluster sizes.

• Subset LB: Filter endpoints by metadata labels before applying an inner LB policy. Enables routing to specific endpoint groups (e.g., version: canary, gpu: a100) without affecting the rest of the cluster.

• Zone-aware / locality-aware: Prefer same-zone endpoints with configurable spillover thresholds. When local zone capacity drops below a configured percentage, proportionally spill traffic to remote zones.

• Priority levels: Define primary and failover endpoint tiers with configurable overprovisioning factors. Traffic uses primary endpoints exclusively until capacity is insufficient, then spills to lower-priority tiers proportionally.

Already implemented

• Random — merged in PR #888
• Power-of-two-choices — existed prior to this issue

Related

• Issue: Additional Load Balancing Algorithms #109
• Epic: Epic: Resilience and Traffic Management #163 (Resilience and Traffic Management)
• proposal: docs(proposal): add additional load balancing algorithms proposal #913

[shaneutt]

Yes, I don't see any reason to not accept any of these options. However, zone-aware will be nuanced.

+1 maintainer approval

[abdallahsamabd]

can you please review the proposal (what/why) and in case everything is ok to merge the PR,
so I can proceed with the next proposal (how section)
thanks