envoyproxy / envoyproxy/envoy

redis_proxy: shardSize() performs 16,384 chooseHost() calls per SELECT on generic ROUND_ROBIN clusters

Open
#47,336 1 comment 0 reactions 0 assignees View on GitHub
area/redis bug
Dominant language
C++
Stars
28.9k
Forks
5.6k
Avg merge
1d 20h
Merged PRs (30d)
437

Description

## Description

Envoy Redis Proxy has severe CPU amplification when cluster-scope commands such as `SELECT` are routed to a generic `STATIC` or `STRICT_DNS` cluster using `ROUND_ROBIN`.

For every `SELECT`, `ThreadLocalPool::shardSize()` iterates through all 16,384 Redis slots and calls `chooseHost()` once per slot.

A generic load balancer does not understand `RedisSpecifyShardContextImpl`. With a single upstream host, it returns the same host for every slot, so the loop always runs the full 16,384 iterations before deduplicating the result to one host.

This makes one inexpensive Redis command consume approximately 1.7 ms of Envoy CPU in our environment.

## Environment

Tested with:

```text
Envoy: 1.38.2
Build SHA: f387231af8dd7274e37c5ae2cc797cb09a948818
Architecture: x86_64
vCPU: 4
Kernel: Linux 4.15
Redis upstream: single test Redis endpoint
Envoy concurrency: 4
```

Source inspection shows that the same `shardSize()` implementation is still present in:

```text
v1.38.4
v1.39.1
main
```

## Configuration

Minimal relevant configuration:

```yaml
static_resources:
listeners:
- name: redis_listener
address:
socket_address:
address: 0.0.0.0
port_value: 6380
filter_chains:
- filters:
- name: envoy.filters.network.redis_proxy
typed_config:
"@type": type.googleapis.com/envoy.extensions.filters.network.redis_proxy.v3.RedisProxy
stat_prefix: redis_test
settings:
op_timeout: 5s
prefix_routes:
catch_all_route:
cluster: redis_single

clusters:
- name: redis_single
type: STATIC
connect_timeout: 1s
lb_policy: ROUND_ROBIN
load_assignment:
cluster_name: redis_single
endpoints:
- lb_endpoints:
- endpoint:
address:
socket_address:
address: 127.0.0.1
port_value: 6379
```
`STRICT_DNS + ROUND_ROBIN` has the same behavior.
## Reproduction

Run a fixed-rate `GET` control:

```bash
memtier_benchmark \
-s 127.0.0.1 \
-p 6380 \
--protocol=redis \
--threads=1 \
--clients=1 \
--test-time=30 \
--rate-limiting=200 \
--command="GET __envoy_cpu_probe_nonexistent__" \
--command-is-read \
--command-miss-tracking=off \
--hide-histogram
```

Then run `SELECT 0` at the same rate:

```bash
memtier_benchmark \
-s 127.0.0.1 \
-p 6380 \
--protocol=redis \
--threads=1 \
--clients=1 \
--test-time=30 \
--rate-limiting=200 \
--command="SELECT 0" \
--command-is-read \
--hide-histogram
```

Monitor the Envoy process with `pidstat`, `perf stat`, or equivalent.

## Results

Both tests used one downstream connection and the same upstream Redis endpoint.

| Request | Rate | Envoy CPU | Average latency |
|---|---:|---:|---:|
| `GET` | 200 req/s | 0–1% of one core | 0.31 ms |
| `SELECT 0` with generic `ROUND_ROBIN` | 200 req/s | 35–36% of one core | 1.95–1.99 ms |
| `SELECT 0` with `envoy.clusters.redis` / `CLUSTER_PROVIDED` | 200 req/s | 0–1% of one core | 0.20 ms |

The commands completed successfully:

```text
SELECT requests: 4001
SELECT successes: 4001
SELECT errors: 0
upstream request timeouts: 0
upstream connection failures: 0
connections destroyed with active requests: 0
```

Swapping the workloads between two otherwise identical Envoy processes caused the CPU usage to follow the process receiving `SELECT`, ruling out process, port, or CPU-core differences.

A production-like test also reproduced the impact:

```text
Total rate: 111 req/s
SELECT rate: 41.7 req/s
GET rate: 69.3 req/s
Envoy CPU: 7–9% of one core
```

The same total rate using only `GET` consumed approximately 0–1% CPU.

## Source analysis
`ClusterScopeCmdRequest::create()` calls `shardSize()` for every cluster-scope command:
```cpp
shard_size = route ? route->upstream(command)->shardSize() : 0;
```
`ThreadLocalPool::shardSize()` currently does:
```cpp
absl::flat_hash_set unique_hosts;
unique_hosts.reserve(Envoy::Extensions::Clusters::Redis::MaxSlot);

for (uint16_t size = 0;
size < Envoy::Extensions::Clusters::Redis::MaxSlot;
size++) {
RedisSpecifyShardContextImpl lb_context(size, ...);
auto host = cluster_->loadBalancer().chooseHost(&lb_context);

if (!host) {
return size;
}

unique_hosts.insert(std::move(host));
}
```
`MaxSlot` is 16,384.
The Redis Cluster load balancer understands `RedisSpecifyShardContextImpl` and returns `nullptr` after the actual shard count, allowing the loop to terminate quickly.

Generic load balancers ignore the shard index. A single-host `ROUND_ROBIN` cluster therefore returns the same host 16,384 times. The code then returns `unique_hosts.size() == 1`, but only after all host-selection calls and the allocation/reservation of a 16,384-entry hash set.

The expensive work is repeated for every `SELECT`.

## Expected behavior

A cluster-scope command sent to a generic cluster with one configured upstream host should not require 16,384 load-balancer calls.

Its CPU cost should be proportional to the number of configured upstream hosts or shards, rather than `MaxSlot`.

## Regression history
`SELECT` and `KEYS` support was introduced in:

- https://github.com/envoyproxy/envoy/pull/37706

Issue #38508 reported that `KEYS` could hang indefinitely because `chooseHost()` never returned `nullptr` with a generic load balancer:

- https://github.com/envoyproxy/envoy/issues/38508

PR #39024 fixed the infinite loop by imposing the `MaxSlot` upper bound and deduplicating hosts:

- https://github.com/envoyproxy/envoy/pull/39024

That change prevents Envoy from hanging, but leaves an O(16,384) operation on every cluster-scope request when a generic load balancer is used.

This issue is about the remaining CPU amplification after that fix.

Contributor guide

Open the contributing guide

Research direction

Start at ThreadLocalPool::shardSize() and its caller, ClusterScopeCmdRequest::create(), then compare generic load-balancer behavior with the Redis cluster load balancer. Reproduce the SELECT workload using the configuration and memtier_benchmark commands in the issue, and verify that generic clusters no longer perform 16,384 host-selection calls per request while Redis cluster behavior remains correct.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, redis
Domain
backend, databases, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
56/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.