Distributed Rate Limiter and Concurrency Controller

Learning outcomes

A rate limiter is trivial when it lives in one process: a counter, a clock, and a yes-or-no check. The trouble begins the moment you run a second copy of that process. Two copies each enforce the limit against their own private counter, so together they admit twice the intended traffic, and a tenth copy admits ten times. The limit you configured is no longer the limit you get. This concept teaches the machinery that fixes that: how to keep admission local and fast, yet accurate against a counter that is shared across a whole fleet.

After studying this page, you can:

• Map a distributed limiter service into its local in-process fast path and its shared, authoritative slow path, and explain why a decision is made locally then reconciled.
• Specify the Allow admission contract and the server-side token-bucket script that makes a cross-instance counter race-free.
• Contrast the token bucket, leaky bucket, and sliding window, and justify the lazy-refill bucket for the fast path and an atomic check-and-decrement for the slow path.
• Diagnose shard failure, clock skew, hot keys, lost increments, and multi-tenant starvation, and choose fail-open versus fail-closed deliberately.
• Apply lock-free counters, GC-free decision paths, batching, and circuit breaking to keep the limiter off its own hot path.
• Trace the topology changes forced at 10x, 100x, and 1000x scale, ending in edge-local decisions with eventual global reconciliation.
• Ground the design in how Grafana Mimir enforces per-tenant request and ingestion limits.

Before we dive in

Picture a checkout counter at a small shop. One clerk serves one queue, and if the queue gets too long the clerk simply closes the door for a minute. That clerk is a local rate limiter: it counts arrivals, holds a single number, and decides alone. As long as there is exactly one door, the count is the truth.

Now the shop opens a second door with its own clerk. Neither clerk can see the other’s queue. The owner told each clerk, “let no more than a hundred customers through per hour,” believing the shop would therefore serve a hundred. Instead it serves two hundred, because each clerk counts only the people it personally waved through. Add a third door, a fourth, a tenth, and the real admission rate climbs to ten times the number on the sign. The rule was enforced everywhere and honored nowhere.

This is the problem that forced the distributed rate limiter into existence, and it has nothing to do with clock drift or network partitions at first. It is a counting problem: the limit is a property of the whole fleet, but a decision must be made in one process in microseconds, before the request is even fully read. You cannot pause every admission for a global agreement without making the limiter slower than the thing it protects.

The shape of the answer is therefore a split. Keep a local limiter in every process so the common decision stays cheap, but back it with a shared store that holds the authoritative counter, so the sum across processes respects the configured limit. The hard parts are all in that split: how the local and global views reconcile, how the shared counter stays correct under concurrent writers, and what happens when the shared store lies, lags, or disappears. A second job, concurrency limiting, rides on the same machinery: instead of bounding a rate over time, it bounds the number of requests in flight at once, using a counter with a deadline.

Microservices topology and component interaction

A distributed limiter is two tiers of counters with a reconciliation channel between them. Every microservice that needs admission runs a local limiter in its own process, and all of them reach out to a shared store that holds the numbers that must agree globally.

Local fast path, shared slow path

The local limiter is the fast path. It lives inside each microservice process, holds a token bucket per limit key, and answers an admission question without any network hop on the common case. Because it sees only the traffic that hits this one process, its count is a private estimate, not the global truth.

The shared store is the slow path and the source of truth. It is typically a Redis cluster holding one counter per (tenant, route, key) tuple. When the local limiter needs to reconcile, or when a limit must be enforced across the whole fleet, it consults or mutates the shared counter. The authoritative decision lives there; the local limiter exists to serve the majority of requests without paying that round trip.

The diagram’s key idea is the asymmetry: most decisions never leave the process, which is what keeps the limiter cheap, but the ones that do reach a counter that every process agrees is authoritative.

Protocols and the read-versus-write interaction

The boundary between a microservice and the shared store is chosen for two properties: low latency on the hot path, and an atomic mutation primitive so a check and a decrement never separate. The primary protocol is the Redis serialization protocol, spoken directly to the cluster, because Redis offers a server-side script that runs the whole admission as one indivisible step. When a service cannot speak Redis directly, or needs a typed contract, it falls back to a gRPC service that wraps the same logic, trading a little latency for a versioned schema.

There are two distinct interactions, and confusing them breaks the design:

• A read is an admission decision: given a tenant, a key, and a cost, may this request proceed? It returns an allowed flag and the tokens remaining. The decision is the product, and it must be consistent with the counter.
• A write is the counter mutation: subtract the cost from the shared bucket, refresh the timestamp, and persist the new token count. The fatal mistake is to treat the read and the write as two separate commands. Between a read of the balance and the write of the new balance, a second request can read the same stale balance, and both proceed against the same tokens. The counter must be read and decremented in one atomic step.

Local limits and global limits serve different purposes and must be told apart. A local limit bounds what one process will admit before consulting the store, which protects the store from being hammered. A global limit bounds what the entire fleet may admit, which protects the protected resource. A correct limiter enforces both: the local bucket absorbs bursts and batches reconciliation, while the global counter guarantees the configured rate is not exceeded in aggregate.

Concrete API schemas

The admission contract is exercised on every rate-limited request, so it is specified in Protocol Buffers version 3: field additions stay backward compatible, and the wire format stays compact and fast to decode. The contract carries everything the decision needs in one call: who is asking, what they are asking to do, how much it costs, and the limit specification to enforce.

The matching server-side logic is a Lua script run inside the store, because only the store can make the check and the decrement atomic. The script reads the bucket, refills it for the elapsed time, and either admits and subtracts the cost or rejects, all before any other client can interleave.

Why the script matters

The entire admit body runs inside the store with no other client able to interleave. That is what kills the lost-update race: the balance is read and written in a single atomic step, so two concurrent requests can never both spend the same token.

Low-level data structures and execution

The limiter’s behavior under load is decided by three choices of structure: which counter algorithm the fast and slow paths use, how the shared counter stays atomic, how keys are spread across the cluster, and how concurrency is bounded separately from rate.

Token bucket, leaky bucket, and sliding window

Three algorithms dominate rate limiting, and the choice is a tradeoff between burst tolerance, smoothness, and what a shared store can compute atomically.

The token bucket holds a pool of tokens that refills at a fixed rate up to a ceiling. Each request removes a token; when the pool is empty the request is rejected. It forgives a burst up to the ceiling and then enforces the steady rate, which matches how real traffic behaves: mostly steady with occasional spikes.

The leaky bucket treats the bucket as a queue that drains at a fixed rate: requests pour in, and if the queue is full they spill over and are discarded. It produces a perfectly smooth outflow, which is ideal for shaping traffic to a downstream that cannot burst at all. Its drawback is that it has two interacting parameters, the average rate and the burst size, that are awkward to tune, and its check needs several distinct store operations that cannot easily be made atomic.

The sliding window approximates the rate by weighting the current and previous fixed windows, giving a smooth estimate without per-request timestamps. It uses only two numbers per counter and a single increment, which made it the right fit for systems constrained to memcached-style primitives, but its result is an approximation, not an exact count.

The fast-path local limiter uses a token bucket evaluated lazily. Rather than a background thread dripping tokens in, the limiter computes how much time has passed since the last request and adds the accrued tokens on read. That makes the local counter lock-light and correct, because the refill is a pure function of the clock. The refill is bounded by the capacity so a long idle period does not produce an unbounded burst.

A lazy-refill token bucket accrues tokens at the refill rate since the last request, capped at the capacity, so a tenant may burst briefly but cannot sustain a rate above the refill rate.

The slow path uses the same token-bucket math, but executed inside the store’s atomic script, so the shared counter that every process trusts is computed without races.

The atomic shared counter

The shared counter is the part most easily built wrong. The naive sequence is: read the balance, decide, write the new balance. Two requests that run this sequence at the same time both read the same balance, both decide to admit, and both write the same decremented value. One admission is free, charged against tokens that were already spent. Under load this lost-update race lets the real rate drift far above the configured limit.

The fix is to make the read, the decision, and the write a single atomic operation on the store. A server-side script does this: it runs to completion with no other command interleaving, so the balance is read and decremented as one indivisible step. No matter how many processes call concurrently, each call sees the balance as the previous call left it.

The separated check-and-decrement

The single most common bug is to call a GET to check the balance, admit the request, then call a separate SET or DECR to subtract. Between those two round trips a dozen other requests can read the same stale balance. The check and the decrement must be one server-side script, never two client commands.

Sharding keys across the cluster

A single Redis node cannot hold the counter load of a large fleet, so the shared store is a cluster. Redis Cluster does not use consistent hashing: it shards across a fixed number of hash slots, and the slot for a key is the CRC16 of the key modulo the slot count. Each node owns a subset of slots, and a client caches the slot-to-node map so it sends each command straight to the right shard.

The atomicity guarantee has a consequence: a script may touch only keys that live on the same shard, because the script runs on one node. To keep a tenant’s related counters together, a hash tag in the key forces them to share a slot. A key shaped like a tenant prefix inside braces hashes only on that prefix, so every counter for one tenant lands on one node and can be mutated in a single atomic script.

The original problem that forced consistent hashing at scale, keeping the rebalancing cost small when nodes join or leave, is solved in Redis Cluster by moving whole hash slots rather than individual keys: adding a node reshard a slice of slots, and only the keys in those slots move.

The concurrency limiter as an inflight counter

Rate limiting bounds work over time; concurrency limiting bounds work in flight at once, which protects a resource that fails under too many simultaneous requests even when the average rate is modest. The concurrency limiter is a counter incremented on admit and decremented on completion, with the crucial addition of a deadline: every increment sets a time-to-live, so a request whose handler crashes and never decrements does not leak a slot forever. The slot expires, and the counter self-heals.

The concurrency limit caps the count of requests admitted but not yet completed; a time-to-live on each increment reclaims slots lost to crashed handlers.

The concurrency limiter rides on the same shared store and the same atomic primitive, because it suffers the identical lost-update race: a check-then-increment split across two round trips lets two requests both see a slot free and both take it, over-admitting past the cap.

Edge cases and chaos engineering

A limiter that is correct on paper and wrong under failure is a liability. Four failure modes separate a toy limiter from a production one.

Shard failure: fail-open versus fail-closed

When the shared store is unreachable, the local limiter faces a binary choice, and it is a genuine tradeoff, not a bug either way. Fail-open means the local limiter continues to admit using only its private bucket, preserving availability at the cost of accuracy: the global limit is no longer enforced, and during the outage the fleet can over-admit. Fail-closed means the local limiter rejects when it cannot reconcile, preserving the limit at the cost of availability: the protected resource is safe, but the service itself becomes unavailable.

The right choice depends on what the limit protects. A limit that guards a billing system from double-charges should fail-closed, because the cost of over-admission is financial. A limit that guards an API gateway from rough fairness should fail-open, because briefly letting extra traffic through is better than taking the whole gateway down. Most production limiters fail-open for soft limits with a circuit breaker that bounds how long they will run unsynchronized, and fail-closed for hard limits. The decision must be explicit and documented, never an accident of the default.

Clock skew, hot keys, and lost increments

Lazy refill trusts the clock, and a clock that jumps forward makes the bucket accrue a huge spurious burst, while a clock that jumps backward can stall it. On a single host the monotonic clock avoids this, but the shared store’s refill uses wall-clock time supplied by the caller, and two callers with skewed clocks will disagree about how many tokens have accrued. The defense is to bound the refill: never accrue more than the capacity, and treat negative elapsed time as zero so a backwards jump cannot drive the count negative.

A hot key is a single counter that a disproportionate share of traffic hits, often one popular tenant or one busy route. Because Redis Cluster places a key on exactly one shard, that shard saturates while the rest of the cluster idles. The standard remedies are to split the logical counter into several physical sub-keys hashed to different shards, admit if the sum of their balances allows, and reconcile, or to lean harder on the local limiter for that key so the shared counter is touched far less often.

A local limiter that crashes between a local admit and its reconciliation to the store loses increments: the local bucket spent tokens the shared counter never learned about. On restart the local bucket resets to full, and the lost spend is gone. This is acceptable precisely because the shared counter is the authority, the local bucket is an optimistic estimate, and periodic reconciliation eventually resynchronizes the two. The system tolerates this drift by bounding how long the local limiter runs before it must re-sync.

The lost-update race, described earlier, is the quietest failure because it produces no error, only a slow upward drift in the real rate. The only signal is the protected resource complaining about load it should not have, weeks later.

Multi-tenant fairness

One noisy tenant must not be able to exhaust the shared store and starve every other tenant’s limit checks. The first defense is structural: each tenant’s counters live under distinct keys, so one tenant exhausting its bucket cannot touch another’s. The deeper defense is resource isolation on the store itself: a tenant whose key access rate is enormous can saturate the shard its keys land on, degrading the limit checks of every other tenant sharing that shard. The remedy is per-tenant quotas on request rate against the store, enforced at the client, and choosing shard placement so a single heavy tenant does not collide with many light ones.

The diagram captures the principle that fairness is a placement problem as much as a counting problem: even correct counters serve unfair latencies if one tenant’s heat is piled onto the shard the others must also use.

System hardening and programming realities

The limiter sits on the hot path of every request it guards, so its own cost is load-bearing. A limiter that takes a lock or allocates on every decision becomes the bottleneck it was built to prevent.

The local counter must be lock-free on the hot path. A mutex around the token check serializes every concurrent request through one process-wide point, and under high concurrency the contention, not the work, dominates latency. The fix is an atomic integer for the token count, updated with a compare-and-swap loop, so concurrent admits proceed without blocking. The token bucket’s lazy refill fits this naturally: compute the accrued tokens, attempt the decrement atomically, and retry if a concurrent writer moved the count.

The decision path must be GC-free in steady state. A limiter written in a garbage-collected language that allocates a counter object or a string per decision will fill the young generation and trigger frequent pauses, each pause a stall that reads as a latency spike to the retrying caller. The discipline is to hold the per-key state in pre-sized arrays or structs, reuse buffers, and avoid boxing numbers, so the steady-state allocation of an admit call approaches zero.

Redis round trips must be bounded. Every check that leaves the process pays a network latency, and at high request rates those round trips saturate both the client and the store. The local limiter batches reconciliation: it admits locally for a short window, then flushes the spent tokens to the store in one amortized call, so the per-request cost of the slow path drops by the batch size. A circuit breaker on the Redis client caps the damage when the store is slow or down: after a threshold of failures or timeouts, the client stops waiting and applies the configured fail-open or fail-closed policy, so a sick store cannot drag the whole limiter down with it.

Batch the slow path

Amortize the shared-counter round trip. Let the local bucket admit for a short window, then reconcile the spent tokens in one batched call. The per-request cost of the slow path divides by the batch size, and the store sees a fraction of the request rate.

Architectural evolution: 10x, 100x, 1000x

A limiter topology that is elegant at one scale becomes a bottleneck at the next, and each jump forces a specific change.

At 10x: a single store and the limit-over-replica-count trick

At ten times the starting load, the dominant cost is coordination, and the shared store is usually a single Redis instance. The hard problem is enforcing a global limit when the work is spread across many processes. The elegant trick is to give each local limiter a slice of the global limit: if the fleet target is a rate and the cluster runs a healthy replica count, each local limiter is configured with the target divided by that replica count. The sum across processes then approximates the global limit with no per-request coordination at all, as long as traffic is spread evenly.

This is exactly how the local-limiter-plus-divisor scheme works: each process learns the healthy replica count through a service-discovery ring, sets its local limit accordingly, and adjusts automatically when processes join or leave. The cost is an assumption that load balances evenly across processes, which a layer-7 load balancer in front of them exists to provide.

At 100x: a sharded cluster and local caching

At a hundred times, a single Redis instance saturates: its CPU or network becomes the ceiling, and one node cannot hold the counter throughput. The store becomes a Redis Cluster, sharded across many nodes by hash slot, so the counter load spreads and the cluster grows horizontally.

At this scale the local limiter also takes on more of the decision load to keep the cluster alive. The local bucket admits for a reconciliation window and flushes in batches, so the cluster sees a fraction of the request rate. Hot keys, which now stress a single shard, are split into sub-keys across shards. The gRPC fallback contract becomes the stable interface that hides whether a given limit is served locally, by one shard, or by several.

At 1000x: edge-local decisions and eventual reconciliation

At a thousand times, even a sharded cluster becomes a coordination liability: a single globally-shared counter store is a failure domain and a latency floor for every admission. The architecture moves the decision to the edge. Each edge node runs its own local limiter and admits based on a per-cell slice of the limit, with no synchronous round trip on the common case.

The global limit is enforced not synchronously but eventually. Each cell reports its spent tokens through an asynchronous channel, and a reconciliation process periodically redistributes the remaining global budget across cells. The decision is local and instant, the global accuracy is approximate and converging, and a failure in one cell cannot block admission in another because they share no synchronous path. This is the same decoupling that tamed ingestion at hyperscale: move the decision to where the request arrives, and let the global view catch up.

The cell boundary is a fault boundary: a request admitted in cell one shares no counter and no synchronous path with cell two, which is the only property that keeps admission available when any single piece fails.

How Grafana Mimir does it

This design is the shape Grafana Mimir takes on its write path. Mimir’s distributor is the stateless entry point that validates data and enforces tenant-specific limits before sharding series to ingesters, and rate limiting is one of those limits.

Mimir enforces two per-tenant limits on the distributor: a request rate, the maximum requests per second across the cluster for a tenant, and an ingestion rate, the maximum samples per second. When either is exceeded, the distributor drops the request and returns an HTTP 429. These are implemented with a per-distributor local rate limiter, and the local limit is set to the configured limit divided by the number of healthy distributor replicas. Each distributor joins a hash ring for service discovery so it knows that replica count, and the limit adjusts automatically when distributors join or leave. The design assumes write requests are evenly distributed across the pool of distributors, which a layer-7 load balancer in front of them provides.

The limits are tunable live. Mimir’s runtime configuration is reloaded every few seconds without restarting components, and the overrides section sets per-tenant values for the request rate, the ingestion rate, and the matching burst sizes, taking precedence over the startup values. An operator can double one tenant’s allowance and leave the default for the rest, which is the multi-tenant fairness mechanism. Beside the per-tenant limits, the distributor has instance limits that bound its own inflight push requests and ingestion rate, so a single overloaded distributor process is protected independently of any tenant’s configured limit.

This is the concrete instance of the principles taught here: admission stays local and stateless so it scales horizontally, the global limit is approximated by dividing it across the healthy replicas the ring reports, the throttle is a structured response that tells the caller how to back off, and the limits are adjustable per tenant without a redeploy. The concurrency side appears in the instance limits, the inflight push request cap, which bounds work in flight at once rather than over time, exactly the inflight-counter discipline described above.

Mastery Questions

Question

Ten identical microservices each run a local rate limiter set to admit 100 requests per second. Why does the fleet admit roughly 1000 per second, and what single structural change fixes it?

Question

An implementer checks the balance with GET, admits the request, then subtracts with DECR. Under load the real rate drifts above the limit with no error. What is happening, and how is it fixed?

Question

A local token bucket refills lazily: $\text{tokens}(t) = \min(C, \text{tokens}(t_0) + r(t-t_0))$. What two properties does the $\min$ with $C$ and the $\max(0, \cdot)$ on elapsed time protect against?

Question

The shared counter store goes down for thirty seconds. Contrast fail-open and fail-closed, and say which you would choose for a billing-system limit versus an API fairness limit.

Question

At 1000x scale, why does the system stop using a single globally-shared counter store for every admission?

Question

How does Grafana Mimir enforce a global per-tenant rate limit across many distributors without a per-request shared counter?

Answer

Each limiter counts only its own arrivals, so its private counter never sees the other nine. The configured limit is a property of the whole fleet, but the decision is made in one process against a private number. The fix is a shared, authoritative counter store that every process consults, so the sum across processes respects the configured limit. The local limiter stays for speed, but the authoritative decision lives in the shared counter.

Answer

A separated check-and-decrement is a lost-update race. Between the GET and the DECR, another request reads the same stale balance, also admits, and both decrement from the same starting value, so one admission is charged against already-spent tokens. The fix is to run the read, the decision, and the write as one server-side Lua script that executes atomically with no other command interleaving, so the balance is read and decremented in a single indivisible step.

Answer

The $\min$ with the capacity $C$ bounds the burst: a long idle period cannot accrue more tokens than the bucket holds, so the limiter never produces an unbounded spike after quiet. Treating negative elapsed time as zero protects against clock skew: if the wall clock jumps backward so $t < t_0$, the refill does not drive the count negative or stall the bucket. Lazy refill is correct only because the accrual is a pure, bounded function of the clock.

Answer

Fail-open lets the local limiter keep admitting from its private bucket, preserving availability but losing global accuracy during the outage. Fail-closed rejects when it cannot reconcile, preserving the limit but making the service itself unavailable. For a billing limit, fail-closed: over-admission means financial cost. For an API fairness limit, fail-open with a circuit breaker that bounds the unsynchronized window: briefly extra traffic is better than taking the gateway down. The choice must be explicit, never a default accident.

Answer

A globally-shared store becomes both a latency floor for every admission and a single failure domain: if it is slow or down, every cell's admission stalls. The architecture moves the decision to the edge: each cell admits from a local slice of the limit with no synchronous round trip, and the global budget is reconciled asynchronously, converging rather than agreeing instantly. The cell boundary becomes a fault boundary, so a failure in one cell cannot block admission in another.

Answer

Each distributor runs a local rate limiter whose limit is the configured per-tenant limit divided by the number of healthy distributor replicas, learned from a service-discovery hash ring. The sum across distributors approximates the global limit with no per-request coordination, assuming a load balancer spreads writes evenly. When exceeded, the distributor drops the request and returns HTTP 429. Per-tenant overrides are applied live via runtime configuration, and distributor instance limits cap inflight push requests as the concurrency control.

Question

Ten identical microservices each run a local rate limiter set to admit 100 requests per second. Why does the fleet admit roughly 1000 per second, and what single structural change fixes it?

Answer

Each limiter counts only its own arrivals, so its private counter never sees the other nine. The configured limit is a property of the whole fleet, but the decision is made in one process against a private number. The fix is a shared, authoritative counter store that every process consults, so the sum across processes respects the configured limit. The local limiter stays for speed, but the authoritative decision lives in the shared counter.

Prev1 / 6Next