Exactly 100, Not 101: Distributed Rate Limiting with Envoy and Redis

A handful of internal APIs were being overloaded by single tenants. It wasn't malice, just a retry loop here and a backfill there, and everyone else's latency suffered for it. We wanted per-tenant quotas that held no matter how many instances served the API, and we wanted them without asking any client to change.

This post covers the requirements, the tools we compared, how Envoy's global rate limiting actually works, how we tested it for correctness, and the plumbing that let a service opt in with one field in its deployment config.

Requirements

• Limits per second, minute and hour, keyed on a request header that identifies the tenant, with a default for everyone and higher limits for named groups.
• Distributed counting. A quota of 100 per hour means 100 across the fleet, not 100 per instance.
• No client changes. No new API keys, no new headers. The tenant header already existed.
• One mechanism for VMs and Kubernetes, on both x86 and ARM.
• Observable: how many requests were limited, for whom, and whether the limiter itself is healthy.

Options we compared

(The managed WAF has since added 1, 2 and 10 minute windows. Per-second and per-hour quotas are still out of scope for it.)

The Kong problem is worth explaining, because it's a common trap. Kong's rate-limiting plugin counts per consumer. To give each tenant its own tier, every tenant has to become a consumer, and the usual way to identify a consumer is the key-auth plugin, which means a new apikey header on every request. That's a client change, and that was our one hard constraint.

Load tests before choosing

We ran k6 against two API instances behind a load balancer, with Redis as the shared counter store, in three rounds:

1. Static responses from Envoy, Caddy and nginx alone, to measure the proxy's own overhead.
2. Two hops: Envoy or Caddy in front of the existing nginx, in front of uWSGI. This is the cautious migration path.
3. One hop: Envoy or Caddy talking to uWSGI directly, with nginx removed.

Round 3 is the configuration that matters. Adding a proxy in front of nginx makes no sense if you can replace nginx. Envoy and Caddy were both viable. Envoy won on the precision of its rate-limit model, its stats, and the drain behaviour we'd need on Kubernetes. The largest run pushed about two million requests across four machines without the limiter becoming the bottleneck.

How Envoy's global rate limiting works

Three components, and it helps to be exact about who does what:

client ──► Envoy (HTTP filter: envoy.filters.http.ratelimit)
              │  builds descriptors from the request
              │  gRPC ShouldRateLimit(domain, descriptors[])
              ▼
           ratelimit service (envoyproxy/ratelimit)
              │  matches descriptors against YAML config
              │  INCRBY key, EXPIRE key  (pipelined)
              ▼
           Redis  ── one counter per (descriptor, time bucket)

• Envoy doesn't count anything. On each request, the route's rate_limits actions turn request attributes (here, a header) into descriptors: ordered lists of key/value pairs.
• The rate-limit service gets the domain and every descriptor, finds the matching rule in its config, and increments a Redis key built from the descriptor and the current time bucket: the epoch divided by the unit length. If any descriptor goes over its limit, the answer is OVER_LIMIT and Envoy returns 429.
• Redis holds the counters. Keys expire after one unit, so there's nothing to clean up.

Three units at once means three descriptors

A detail that isn't obvious from the docs: one descriptor matches one rule, and one rule has one unit. To enforce per-second, per-minute and per-hour limits on the same tenant, Envoy has to send three descriptors, each tagged with the unit it represents:

# Envoy route config (fragment)
rate_limits:
  - actions:
      - generic_key: { descriptor_value: per_second }
      - request_headers: { header_name: x-tenant-id, descriptor_key: tenant }
  - actions:
      - generic_key: { descriptor_value: per_minute }
      - request_headers: { header_name: x-tenant-id, descriptor_key: tenant }
  - actions:
      - generic_key: { descriptor_value: per_hour }
      - request_headers: { header_name: x-tenant-id, descriptor_key: tenant }

# ratelimit service config
domain: internal-api
descriptors:
  - key: generic_key
    value: per_second
    descriptors:
      - key: tenant                 # default for any tenant
        rate_limit: { unit: second, requests_per_unit: 5 }
      - key: tenant
        value: tenant-b             # a premium group, listed explicitly
        rate_limit: { unit: second, requests_per_unit: 50 }
  - key: generic_key
    value: per_minute
    descriptors:
      - key: tenant
        rate_limit: { unit: minute, requests_per_unit: 20 }
  # ...per_hour follows the same shape

A tenant without a value-specific entry falls through to the bare key: tenant rule. Every tenant gets its own counter, because the value is part of the cache key even when the rule is the default one.

Envoy builds each descriptor by running that entry's actions in order. If any action can't contribute, a missing header for instance, Envoy drops the whole descriptor instead of sending a partial one. That rule is the mechanism behind the missing-header behaviour below.

What the counter actually is

It helps to see one. The rate-limit service builds each Redis key from the domain, every key/value pair in the descriptor, and the start of the current window:

key           = <domain>_<key>_<value>_<key>_<value>_..._<window start>
window start  = floor(now ÷ unit) × unit         unit = 1, 60, 3600 or 86400 seconds

internal-api_generic_key_per_hour_tenant_tenant-a_1670320800     # 10:00 to 10:59:59 UTC, 6 Dec 2022

Note the tenant_tenant-a in the middle: that's the per-tenant counter, whichever rule matched. For each descriptor in a request, the service pipelines two commands:

INCRBY <key> 1               → returns the count including this request
EXPIRE <key> 3600 + jitter   → jitter is random, up to 300 s by default

It answers OVER_LIMIT if the returned count is greater than requests_per_unit. Three properties follow from that design:

• Windows are aligned to the clock, not to a tenant's first request. Every hour window starts at :00 UTC for every tenant, and the key name changes when it does. Nothing is ever reset; a new window is simply a new key.
• The expiry is housekeeping, not logic. Because the window start is part of the key, a key that outlives its window can't extend it. The jitter just spreads expirations out instead of having a whole window's keys expire in the same second. Every request re-sends EXPIRE, so a key only ends up without a TTL if every one of those commands was lost.
• Per-second keys churn fastest. Every tenant gets a fresh per-second key every second. The service can route those to a separate Redis (REDIS_PERSECOND), which keeps that high-churn keyspace away from the minute and hour counters.

The JSON that teams actually write

Nobody should hand-write that YAML. Service teams write a small JSON file in their repository:

{
  "x-tenant-id": {
    "default": { "persecond": 5,  "perminute": 20, "perhour": 30 },
    "group_1": { "persecond": 50, "perminute": 70, "perhour": 100,
                 "header_value": ["tenant-b", "tenant-c"] }
  }
}

A Python step in the build pipeline validates it and expands it into both the Envoy rate_limits block and the rate-limit service YAML. That gives typos a single place to fail loudly, and the three-descriptor pattern stays an implementation detail.

Decisions that matter in production

Missing header. If the header isn't on the request, the request_headers action produces no descriptor, and the request isn't limited by that rule. That was what we wanted (internal health checks don't carry a tenant), but decide it deliberately. Set skip_if_absent per action if you need different behaviour: with it, Envoy still calls the service but leaves that entry out, so a request with no tenant header is checked against whatever rule, if any, matches the shorter descriptor.

When the limiter is down. Envoy's filter has failure_mode_deny, which defaults to false: if the rate-limit service errors or times out, the request is allowed. We kept fail-open. A rate limiter that takes down the API it protects has inverted its job. The filter's call timeout is short by default (20 ms), so a slow limiter adds bounded latency, not an outage. Every request let through this way increments the filter's failure_mode_allowed counter, which makes it the number to alert on.

Fixed windows. The counter is bucketed by clock time, so a tenant can spend a full quota at 10:59:59 and another at 11:00:00. For overload protection that's fine. For billing-grade quotas it isn't. Know which one you're building.

Hot tenants. When a tenant is far over its limit, every rejected request still costs a Redis round trip. The rate-limit service can keep an in-process cache of keys already known to be over limit, so a flood of 429s doesn't become a flood of Redis traffic. It's off until you give it memory (LOCAL_CACHE_SIZE_IN_BYTES). An entry lives for one full window length from the moment it's set, so it can outlast the window that created it. That's harmless precisely because the next window has a different key. On Redis Cluster this matters more than it looks: one tenant's key for one window hashes to a single slot, so one hot tenant is one hot shard. Pipelining Redis writes over a small window helps at high request rates.

Shadow mode first. The rate-limit service can evaluate rules and emit stats without enforcing them, per rule (shadow_mode: true) or globally. Turning a new limit on in shadow mode for a few days, then reading the near_limit and over_limit stats, tells you who would be hurt before anyone is. near_limit counts hits above 80% of the limit by default (NEAR_LIMIT_RATIO), and a shadow_mode counter records every request that would have been rejected.

Tell clients where they stand. With enable_x_ratelimit_headers: DRAFT_VERSION_03, Envoy adds X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset to responses, filled from what the rate-limit service returns. With three windows per tenant, the headers describe whichever window is closest to its limit, which is exactly the one a well-behaved client should back off for.

Fixed windows versus the alternatives

The fixed window is the cheapest correct algorithm, and its weakness is precise. With a limit of L per window, a client can send L requests in the last instant of one window and L more in the first instant of the next, so any interval one window long can contain up to 2L. The alternatives trade that edge away for more state or more work per request:

Envoy ships the token bucket too, in its local rate limit filter: a bucket with max_tokens, tokens_per_fill and fill_interval, held in each Envoy's memory, with no network call. The two compose well. A local bucket per instance absorbs a sudden spike at no cost and protects that one instance. The global fixed window enforces the tenant's quota across the fleet.

Proving correctness across instances

The interesting property isn't "does Envoy return 429". It's whether the quota holds when requests are spread over several machines.

The test: two instances behind a load balancer, one shared Redis, a quota of 100 requests per hour for a single tenant, and k6 sending 1,000 sequential requests with one virtual user.

run 1
  status 200 ............ count=100   avg=3.15ms  p99=8.21ms
  status 429 ............ count=900   avg=1.33ms  p99=5.27ms

run 2 (same hour)
  status 200 ............ count=0
  status 429 ............ count=1000  avg=1.08ms  p99=3.50ms

Exactly 100 got through, spread across both instances, and the second run inside the same hour got nothing. Two other details are worth noticing:

• 429s are about twice as fast as 200s. A rejected request never reaches the upstream application, so the cost of throttling is a Redis round trip, not an application request.
• We tagged every k6 status code with a threshold, not just 200 and 429, so that a 502 or 503 would show up as a count instead of disappearing into a failure rate. A limiter that "works" by breaking the upstream would otherwise look like a pass.

Why it's exactly 100, and what would break it

The result isn't luck; it falls out of how Redis executes commands. Redis runs commands one at a time, so a hundred concurrent INCRBYs on the same key return 1, 2, … 100 in some order, each value exactly once, no matter how many Envoys or rate-limit replicas sent them. The service admits a request only if its value is at most the limit, so at most 100 can ever be admitted. There are no locks, no read-modify-write and no coordination between instances. The counter is the coordination.

The sequential test proves the arithmetic. It doesn't prove the edges, and four of them can still let more than 100 through:

• A window boundary. A run that straddles the top of the hour gets up to 100 in each window. The second run got nothing because it stayed inside one window.
• Failing open. Every limiter error or timeout is an admitted request. That's what failure_mode_allowed is for.
• Redis failover. Replication is asynchronous. If the primary dies and a replica that missed the last few increments is promoted, those counts are gone, and the window admits them again.
• Counters split across Redis deployments. Each key has to live in exactly one place. Sharding by key is fine. Two independent Redis deployments behind different rate-limit replicas would each count to 100.

One more thing the counter isn't: a count of admitted requests. Unless the local cache short-circuits them, rejected requests increment it too, so after a run like the first one the key can hold anything from 101 to 1,000. Read admissions from the within_limit and over_limit stats, not from Redis.

Rolling it out on Kubernetes

On VMs, Envoy and the rate-limit service run as systemd units baked into the machine image. On Kubernetes, they're sidecars, and the goal was for a team to opt in with one field.

One field, generated patches

The deployment descriptor that every service already had grew a proxy_server field. When it says envoy, the manifest-generation step in CI applies a set of JSON 6902 patches with Kustomize:

• Replace the nginx sidecar with Envoy, and mount a shared emptyDir with the generated configs.
• Add the rate-limit service sidecar, with its config mounted and a readiness probe on its health endpoint.
• Add a statsd exporter sidecar, because the rate-limit service emits statsd. That turns over_limit, near_limit and per-descriptor counters into Prometheus metrics.
• Add a ServiceMonitor that scrapes the exporter and Envoy's /stats/prometheus.

Images were built multi-arch, so the same manifests run on x86 and Graviton nodes.

Traffic shift, not in-place swap

Swapping the proxy inside a running Deployment means a bad config hits every pod during the rollout. We did it differently: new Deployment, new target group, then shift traffic on the load balancer from the old nginx target group to the new Envoy one. Rollback is moving the weight back, which takes seconds and needs no rebuild. New target groups also got their own 4xx and 5xx alarms from day one.

Graceful shutdown

Envoy needs to be told to drain. Without that, a pod deletion closes connections mid-request. The pre-stop hook calls the admin endpoint:

lifecycle:
  preStop:
    exec:
      command: ["/bin/sh", "-c", "curl -s -X POST localhost:9901/drain_listeners?graceful; sleep 15"]

drain_listeners?graceful starts Envoy's drain sequence. For HTTP/1.1 it adds Connection: close to responses, so clients move to a new connection. For HTTP/2 it sends GOAWAY. The sleep keeps the container alive while the load balancer deregisters the target and in-flight requests finish. It has to fit inside terminationGracePeriodSeconds, alongside the target group's deregistration delay.

What we'd watch next time

• A shared Redis is a shared fate. One counter store served every service that adopted Envoy. That's fine at first, but per-business Redis instances belong in the roadmap before a noisy domain affects everyone else's latency.
• Alert on the limiter, not only on 429s. A sudden drop in over_limit can mean the rate-limit service is failing open.
• Limits are product decisions. We supplied the mechanism and a sensible default. The numbers for each group belong to the team that owns the API.

References

• Envoy global rate limiting: how the filter, the service and descriptors fit together.
• Envoy HTTP rate limit filter: descriptor composition, failure_mode_deny, the X-RateLimit headers and the filter's stats.
• Envoy local rate limit filter: the per-instance token bucket.
• envoyproxy/ratelimit: configuration format, shadow mode, the local over-limit cache, per-second Redis and the stats it emits.
• Redis INCR: atomic increments, and the rate-limiter pattern built on them.
• Redis replication: why replication is asynchronous and what a failover can lose.
• Envoy draining: what drain_listeners does to HTTP/1.1 and HTTP/2 connections.
• k6 thresholds: pass/fail criteria per tagged metric.