Distributed Rate Limiter Architecture in Depth

Accuracy, overhead and availability

Three quantities trade against each other. Accuracy is how close admitted traffic stays to the limit, with overshoot and undershoot as separate errors. Overhead is the latency and coordination traffic each decision adds. Availability is what happens to admission when the shared counter store is slow or down. No design maximises all three, so start by writing down which error you can tolerate: a billing quota that customers pay for usually tolerates small undershoot and no overshoot, while a backend-protection limit tolerates small overshoot and must never add a hard dependency.

Placement narrows the choice. The edge sees IP addresses but not tenants, so it handles volumetric abuse. The gateway authenticates the caller and knows the tenant, plan and endpoint, so most business limits live there. A service may add its own limit on expensive operations, such as report generation, because only it knows the true cost of a request. Each layer should be able to reject on its own; none should assume another layer has already done so.

Accuracy, overhead and availability

Three quantities trade against each other. Accuracy is how close admitted traffic stays to the limit, with overshoot and undershoot as separate errors. Overhead is the latency and coordination traffic each decision adds. Availability is what happens to admission when the shared counter store is slow or down. No design maximises all three, so start by writing down which error you can tolerate: a billing quota that customers pay for usually tolerates small undershoot and no overshoot, while a backend-protection limit tolerates small overshoot and must never add a hard dependency.

Placement narrows the choice. The edge sees IP addresses but not tenants, so it handles volumetric abuse. The gateway authenticates the caller and knows the tenant, plan and endpoint, so most business limits live there. A service may add its own limit on expensive operations, such as report generation, because only it knows the true cost of a request. Each layer should be able to reject on its own; none should assume another layer has already done so.

Strategy one: a central counter on every request

The simplest accurate design checks a shared counter on every request. Each pod runs an atomic script in Redis that reads the counter, decides and increments in one step, so concurrent pods cannot both see room for the last request. A sliding-window counter keeps two fixed-window counts and weights the previous one by how much of it still overlaps the window, which removes most of the double burst a fixed window allows at its boundary.

-- KEYS[1] = current window, KEYS[2] = previous window, e.g. rl:{t42}:orders:28745 and :28744
-- ARGV: limit, window_ms, now_ms, cost
local limit, window = tonumber(ARGV[1]), tonumber(ARGV[2])
local now, cost = tonumber(ARGV[3]), tonumber(ARGV[4])
local elapsed = now % window
local prev = tonumber(redis.call('GET', KEYS[2]) or '0')
local curr = tonumber(redis.call('GET', KEYS[1]) or '0')
local used = prev * (window - elapsed) / window + curr
if used + cost > limit then
  return {0, window - elapsed}            -- rejected; upper bound on wait in ms
end
redis.call('INCRBY', KEYS[1], cost)
redis.call('PEXPIRE', KEYS[1], window * 2)
return {1, math.floor(limit - used - cost)} -- allowed; remaining

Both keys share the {t42} hash tag so Redis Cluster places them in the same slot, which a multi-key script requires. Callers compute the window index from their own clock, so keep gateways on NTP; skew only misplaces requests near window edges. The cost is one round trip per request and a hard dependency on Redis for every decision.

Strategy two: a static split across pods

The opposite extreme involves no coordination: give each of N pods limit divided by N and enforce locally. It never overshoots, adds no latency and survives any store outage. Its error is undershoot whenever traffic is not spread evenly. Long-lived HTTP/2 connections, sticky load balancing or a tenant with few clients can concentrate one tenant on a handful of pods, and the effective limit collapses to the share of those pods. It also has to be recomputed whenever N changes during autoscaling.

Strategy three: local counting with periodic sync

A middle path counts locally and synchronises periodically. Each pod admits against its last view of the global count plus its own unsynchronised requests, and every T milliseconds pushes its delta and pulls the new total. Between syncs, every pod is blind to the others, so the worst-case overshoot is bounded by what the tenant can send across the whole fleet in one sync interval. Halving T halves the error and doubles the coordination traffic, which is now per pod per tenant per interval rather than per request.

# Per pod, per tenant: admit locally, reconcile with the shared count every T seconds.
class SyncedLimiter:
    def __init__(self, limit):
        self.limit, self.global_seen, self.local_delta = limit, 0, 0

    def allow(self, cost=1):
        if self.global_seen + self.local_delta + cost > self.limit:
            return False
        self.local_delta += cost
        return True

    def sync(self, store, key, window_s):        # called every T seconds
        total = store.incrby(key, self.local_delta)  # push our delta, get the new total
        store.expire(key, window_s * 2)
        self.global_seen, self.local_delta = total, 0

Strategy four: token leasing from a quota service

The fourth design treats budget like inventory. A quota service owns each tenant's budget and hands pods leases on batches of tokens; a pod spends its batch locally and asks for more when it runs low. Leases expire so unused tokens return to the pool. Overshoot is zero as long as the quota service is authoritative, and coordination happens once per batch. The error moves to undershoot: tokens leased to a pod that then receives no traffic are stranded until they expire, so batch size should track each pod's own recent rate, roughly one second of it, rather than a fixed number. Google's open-source Doorman project is an example of a capacity-leasing service built along these lines.

A concrete reference: Envoy local and global limits

Envoy shows how these combine in practice. Its local rate limit filter, envoy.filters.http.local_ratelimit, is a per-instance token bucket configured with max_tokens, tokens_per_fill and fill_interval, and answers 429 with no network call. Its global rate limit filter sends request descriptors over gRPC to an external rate limit service; the reference implementation, envoyproxy/ratelimit, keeps fixed-window counters in Redis. If the service errors, the filter allows the request unless failure_mode_deny is set. Envoy's documentation suggests using the local limit to absorb large bursts in front of the global one.

# envoyproxy/ratelimit service configuration
domain: public_api
descriptors:
  - key: tenant_id                 # any tenant: default limit
    rate_limit:
      unit: minute
      requests_per_unit: 6000
  - key: tenant_id
    value: t42                     # one large tenant
    rate_limit:
      unit: minute
      requests_per_unit: 60000
    shadow_mode: true              # count and report, do not enforce yet

Keys, sharding and hot tenants

Shard counters by tenant so load spreads across the cluster, and put all keys for one decision under one hash tag. The largest tenant then becomes a hot key on one shard. Two remedies work: move that tenant to leasing or periodic sync so it touches Redis per batch instead of per request, or split its budget across several sub-keys chosen at random and sum them when deciding, accepting a little more inaccuracy.

Limits across regions

A global limit across regions cannot afford a cross-region round trip per request. The usual design gives each region its own allocation, for example in proportion to its share of the tenant's traffic over the last few minutes, enforces that locally with any of the strategies above, and has a background job rebalance the allocations every few seconds. The error is bounded by how fast traffic shifts between regions relative to the rebalance period. If a region is cut off, it keeps its last allocation, which is usually the right failure behaviour for a quota.

Worked example: sizing a 40-pod gateway

Size the four designs for one gateway fleet: 40 pods, 200,000 requests per second in total, and a mid-sized tenant limited to 6,000 requests per minute that currently sends about 100 per second from a few clients, landing on only 4 pods because its connections are long-lived.

The central counter's cost is driven by total traffic, not by the number of tenants; at 200,000 calls per second it needs a sharded Redis tier sized and monitored like a production database. Leasing cuts that by roughly the batch size. For this fleet a sensible design is a local bucket per pod for burst protection, leasing for paying tenants whose quotas are contractual, and a static split as the outage fallback.

Failure modes

Testing it

Test the limiter as a distributed system, not as a function. Drive a load test with realistic skew, including one tenant pinned to a few pods, and measure admitted requests per window against the configured limit to get real overshoot and undershoot numbers. Then inject faults: add latency to Redis, kill a Redis primary, scale the gateway from 40 to 80 pods mid-test, and confirm each case lands in the behaviour you chose rather than the one you happen to get.

Operating it

Roll out new limits in shadow mode first, logging would-be rejections per tenant, and enforce only once the numbers look right. Return HTTP 429 (RFC 6585) with a Retry-After header (RFC 9110). The X-RateLimit-* headers are a widespread convention rather than a standard; the IETF RateLimit header fields are still an Internet-Draft, so treat their exact syntax as subject to change. Export allowed and shed counts per tenant and per limit, limiter check latency, fallback activations and, for sync or leasing designs, measured overshoot against the configured limit.

Trade-offs

Central counters buy accuracy with latency and a dependency. Static splits buy independence with undershoot. Periodic sync and leasing sit between them and differ in which error they allow: sync overshoots briefly, leasing strands tokens briefly. Most large systems layer them: an edge limit for abuse, a local bucket to protect each pod, and a coordinated limit only where the budget is contractual.

What to do next

1. For each limit, write down whether overshoot or undershoot is the worse error.
2. Measure how evenly each large tenant spreads across your pods before choosing a static split.
3. Put a local bucket in every gateway pod, independent of any shared store.
4. Choose central, sync or leasing per limit, and set a timeout and fail policy for each.
5. Launch every new limit in shadow mode and compare would-be rejections with expectations.
6. Return 429 with Retry-After and make your SDK back off with jitter.

Keep learning: GCRA and local token leasing, rate limiter design from requirements, rate versus concurrency limits, load shedding and Kafka quotas.