ClusterClient: latency-aware read load balancing (power-of-two-choices + peak-EWMA)

[rajvarun77]

All four LoadBalancingStrategy options in redis/cluster.py are latency-blind: a degraded replica (GC pause, saturated host, cross-AZ hop) keeps its full read share until it fails outright, so read tail latency spikes long before errors appear.

Proposal: a LATENCY_BASED strategy using power-of-two-choices + peak-sensitive EWMA — pick two candidate nodes at random, route to the lower score = peak-EWMA of recent command latency × (in-flight + 1). O(1) per read, no probing; latency comes from command round-trips the client already performs. Zero required config, and slow cross-AZ replicas naturally deprioritize themselves.

I've implemented this algorithm in Apache brpc (apache/brpc#3367) and ClickHouse (ClickHouse/ClickHouse#109234); in brpc's benchmark with 1 degraded backend of 4, p99 dropped from 6.5ms (round-robin) to 337µs. Happy to open a PR with the strategy, tests, and docs if maintainers are open to it.

[petyaslavova]

Hey @rajvarun77, thanks for the detailed proposal — this is a genuinely useful direction. You're right that all four current LoadBalancingStrategy options are load-unaware: they select purely by index (round-robin counter or random), so a degraded-but-alive replica keeps its full read share. Power-of-two-choices with a peak-EWMA score is a well-proven fit for that gap, and gating it behind a new opt-in strategy keeps the existing ones untouched.

Before opening a PR, could we align on a short design note first? The main thing to work out isn't the scoring function (that part is self-contained) but the data it needs, which the load balancer doesn't see today: get_server_index() currently receives only a primary name and a node count, per-command round-trip latency isn't recorded anywhere it can reach, and in-flight tracking would have to be incremented/decremented across the shared execute path — including MOVED/ASK redirects and pipelines — in both the sync and async stacks. Please confirm that instrumentation activates only when LATENCY_BASED is selected so the default paths stay byte-for-byte unchanged, and that sync/async parity is maintained.

One more request: since the 6.5ms→337µs figures come from a C++ server-side load balancer, a small redis-py cluster benchmark (one degraded replica of N) would help set realistic expectations for a Python client-side implementation. With a design note and that benchmark, I'd be happy to review the PR.

[lh0156]

I would like to work on this with the following opt-in design:

• Add LoadBalancingStrategy.LATENCY_BASED; existing strategies remain unchanged.
• Keep the hot path disabled unless that strategy is selected. In particular, existing round-robin/random selection and their instrumentation remain untouched.
• Extend the shared LoadBalancer with per-node state keyed by node name: in-flight operation count and a peak-sensitive EWMA of completed node round trips. Selection samples two candidates from the slot's eligible nodes and chooses the lower peak_ewma * (in_flight + 1) score. Nodes without observations receive a neutral initial score so they are explored.
• Record and release in-flight state with try/finally around both standalone command execution and grouped pipeline execution. MOVED/ASK retries are recorded against the node that actually handled each attempt; a pipeline contributes one node-level batch sample because individual command round trips are not observable after a grouped write/read.
• Use the same synchronous LoadBalancer state machine for sync and asyncio clients. Its critical sections are bounded dictionary updates protected by the existing lock, so no await is added to the asyncio selection path.
• Add deterministic sync/async unit tests for candidate selection, cold-node exploration, EWMA decay/peak behavior, and in-flight cleanup on success and error. Add a small cluster benchmark with one deliberately delayed replica to measure selection share and tail latency against round-robin.

If this shape matches the intended API and semantics, I will open a draft PR with the implementation and benchmark results.