Local rate limiter

Context

A global limit seems to need global agreement: a shared counter checked over the network on every request. But the only shared fact that matters is the replica count, and it changes rarely.

So each replica watches the count, takes its equal share of the limit, and enforces that share in memory. A cap of 100,000 requests per second over 10 replicas becomes 10,000 each. The request path stays local; the cap is only as fresh as the count.

Workflow

The workflow: a count change re-divides the limit while requests keep flowing.

Watch. Each replica observes the global limit and the live replica count; if the source is unreachable, the last observed count stands.

Divide. Each replica’s share is the global limit divided by the observed count, recomputed on each count change.

Enforce. Each request draws from an in-process token bucket refilled at the share rate. A draw against an empty bucket waits or fails, per the workload’s policy.

Traits

  • Linear scaling. Each limit is a local memory check. You can enforce many limits on one request, or apply them to a stream that grows from thousands to millions of requests per second, without adding coordination to the hot path.
  • Fine-grained enforcement. Every request is checked in memory, so the limiter can enforce rates at fine intervals.
  • Off-path dependency. Replicas watch their count in the background. Requests use the latest local value, never a network call.
  • Low overhead. Enforcement lives inside the service’s own processes; the check is a token draw in memory, negligible next to anything that crosses a network.

Requirements

  • Consistency tolerance. The cap holds approximately. Uneven traffic makes it tighter; a replica-count change briefly skews it either way. The workload has to tolerate both.
  • Burst tolerance. A token bucket enforces a sustained rate, not an even flow. Its size controls how many requests can pass at once; the downstream service must tolerate that burst.
  • Memory bound. Each request reads and updates local bucket state. The number of buckets has to fit in memory; at high rates, memory bandwidth and contention set a hard limit.
  • Observable replica count. Each replica needs a reasonably fresh count of its peers.
  • Meaningful shares. The limit must be large relative to the replica count, so each share is still a workable rate.

Example

A fan-out API: requests arrive from several sources, each accepted request goes out to a set of downstream consumers, and a fraction of the traffic is sampled. Each source, each consumer, and the sampler carries its own global limit, with its own value.

  • Envoy local rate limiting runs a token bucket per proxy process with no coordination; the aggregate limit is the per-process limit times the replica count, divided by hand at configuration time. This pattern makes the division automatic against the watched count.
  • Doorman (YouTube) has a central server lease capacity to clients, which enforce their leases locally. Shares follow what each client asks for, so traffic need not spread evenly; the price is a server every client refreshes against. Its fallback when that server is unreachable is capacity divided by client count: this pattern, held permanently.
  • Distributed rate limiting (Raghavan et al., 2007) studies a global limit enforced across sites; equal static shares are its baseline, and its Flow Proportional Share re-weights each site’s share by observed demand.
  • Gubernator (Mailgun) keeps the shared counter but drops the external store: consistent hashing elects one peer to own each counter, and batching amortizes the network hop the request path still takes.
  • Client-side adaptive throttling (Google SRE book) has each client cap its own traffic by the ratio of requests attempted to requests accepted: enforcement is local, but the cap emerges from rejections rather than a configured limit.