Distributed Rate Limiting in Microservices: Sharing Quotas Across Replicas

Why per-replica rate limits break when you scale out

Distributed rate limiting means enforcing one quota across every replica of a service, so the limit applies to the client rather than to whichever pod happens to serve the request. A global rate limit of 1,000 requests per minute per API key should allow 1,000 requests in total, not 1,000 per process.

Per-replica limiters break that guarantee. Each replica keeps its own counter in memory, so with N replicas a client can send up to N times the configured limit. Take an illustrative example: a 1,000 rpm limit and six replicas give an effective ceiling of 6,000 rpm. When the autoscaler adds four more replicas during a traffic spike, the ceiling rises to 10,000 rpm. The limit grows at the moment you most need it to hold.

The effective limit also depends on routing. With even round-robin distribution, a client reaches every replica and gets the full N-times allowance. With sticky sessions or long-lived HTTP/2 and gRPC connections, a client may stay pinned to one replica and get throttled at exactly the configured value. Two clients on the same plan can therefore see very different limits.

A shared quota requires coordination, usually through a central store. That store adds a network round trip to every check and becomes a dependency that can fail. The core design choice is how much accuracy you are willing to trade for latency and availability.

This trade-off is worth making if you meter paid API tiers, need fairness between tenants on shared infrastructure, or protect a fragile downstream dependency that only has a fixed amount of capacity.

What distributed rate limiting is

Distributed rate limiting is a rate limiter whose state lives outside any single process. Instead of each replica counting requests in its own memory, all replicas read and update the same counters, usually in a shared in-memory store such as Redis. The quota is defined per key (an API key, a tenant, an endpoint or a downstream dependency), and every replica enforces that key's quota against the same numbers.

The result is a limit that stays the same regardless of how many replicas are running, how traffic is routed, or how often the autoscaler changes the fleet size.

How it works

Every request follows the same path:

1. Identify the key. The replica derives the limit key from the request, for example tenant42 or search-endpoint.
2. Check and update shared state atomically. The replica asks the store to apply the algorithm (token bucket, sliding window and so on) to that key. The read, the decision and the write happen as one atomic operation, typically a Lua script, so concurrent replicas cannot both spend the same token.
3. Act on the decision. If the request is allowed, it proceeds. If not, the replica returns HTTP 429 with a Retry-After value derived from the bucket state.
4. Handle store failure. If the store is slow or unreachable, the replica falls back to a local approximation instead of blocking or admitting everything.

Two refinements make this practical at scale. Leasing lets each replica claim a batch of tokens and spend them from memory, so most requests never touch the store. Sharding spreads keys across store nodes, with hash tags keeping each key's data together. The sections below cover each step in detail.

Who should use it

A shared quota fits teams that run horizontally scaled services and need the limit to mean the same thing at every fleet size:

• Public API providers with paid tiers, where a customer's quota is part of a contract and overshooting by the replica count gives away paid capacity.
• Multi-tenant platforms, where one tenant must not starve others on shared infrastructure.
• Services in front of a fixed-capacity dependency, such as a partner API with its own quota or a legacy database, where exceeding the limit causes errors or extra charges.
• Platform teams building a shared limiter library or sidecar for many service teams, so limits are enforced consistently.

When to avoid it

A shared store adds latency, an operational dependency and a new failure mode. Avoid it when:

• You run a single replica. An in-process limiter is already exact.
• Approximate limits are good enough. Internal service-to-service traffic usually tolerates a per-replica limit of the global quota divided by the replica count.
• The latency budget cannot absorb a network round trip on every request, and leasing's over-admission is also unacceptable.
• The goal is coarse abuse protection, such as per-IP flood control, which the gateway or load balancer can handle before traffic reaches your services.
• You cannot operate the store reliably. If nobody owns its alerting, failover and capacity, the limiter becomes a risk to availability rather than protection.
• Overshooting costs nothing. If exceeding the limit has no financial, contractual or capacity consequence, the coordination cost is not justified.

Choosing the limit key: API key, tenant, endpoint or downstream dependency

The key you limit on determines what the shared store has to hold and how hard it gets hit. It also tells you whether you need a shared store at all.

API key or tenant is the common choice for paid tiers and fairness. Cardinality grows with your customer count, and each bucket costs only a few fields, so memory is rarely the problem. Skew is. One large tenant can send most of the traffic to a single key, and that key lands on a single shard. Plan for hot keys from the start.

Endpoint keys have low cardinality and change slowly. A global limit on an expensive search route is easy to reason about. Combining endpoint with tenant multiplies cardinality, so add that dimension only when someone will act on the distinction.

Downstream dependency keys protect a fixed capacity, such as a partner API or a legacy database. There are few keys and they are very hot. Every replica contends for the same counter, so these keys benefit most from the leasing approach described later.

Not every limit needs exact global accounting:

• Internal service-to-service traffic can usually tolerate approximate limits. Dividing the global quota by the replica count gives a per-replica limit that is close enough and has no network dependency.
• A single replica has nothing to share, so an in-process limiter is exact.
• Coarse abuse protection, such as per-IP flood control, is often handled more cheaply at the gateway or load balancer, before requests reach your services.

Use a shared quota only when overshooting would cost real money or break a contract.

Comparing rate-limiting algorithms in a shared store

All four algorithms can run in a single round trip if you wrap the commands in a Lua script or a MULTI transaction. The real differences are memory per key and what happens near a window boundary.

The fixed window's flaw comes from how it resets. A client can spend the full limit in the last second of one window and again in the first second of the next. The sliding window counter fixes most of this by weighting the previous window's count. That weighting assumes traffic was evenly spread, so a spiky tenant can slip slightly past the limit.

Token bucket is the best default for quota sharing. It stores constant state per key, and refill is computed lazily from elapsed time, so nothing runs in the background. It also makes burst size an explicit parameter instead of a side effect of window alignment. That last property matters most when many replicas draw from one quota.

Choose the sliding log only when the contract demands exactness. Examples include billing-grade limits, compliance caps, or low limits where one extra request matters. Its memory grows with the limit. At 1,000 requests per minute you hold up to 1,000 entries per key, so it suits few keys with modest limits.

How to implement an atomic token bucket in Redis with Lua

A token bucket needs only two fields per key: the current token count and the timestamp of the last refill. The obvious implementation reads both with GET, computes the refill in application code, and writes the result with SET. Under concurrency this loses updates. Two replicas each read 1 token, both decide the request is allowed, and both write 0. The bucket admitted two requests against one token. With more replicas the overshoot grows, and it is worst during bursts, which is when the limit matters most.

A Lua script avoids this because Redis runs it atomically. No other command touches the key between the read and the write. The script stores both fields in a hash and runs these steps:

1. Read tokens and ts with HMGET.
2. Call TIME for the current seconds and microseconds.
3. Add elapsed × refill_rate to the token count, capped at capacity.
4. Subtract the requested cost if enough tokens remain.
5. Write both fields back.
6. Set PEXPIRE to the time needed to refill completely, so idle keys disappear on their own.

Calling TIME inside the script means every replica's request is measured against one clock: the Redis primary's. Skew between application hosts cannot inflate or shrink the refill.

The caller loads the script once with SCRIPT LOAD and invokes it with EVALSHA. If it receives a NOSCRIPT error, it falls back to EVAL. The bucket key goes in KEYS, not ARGV, so cluster routing works. Capacity, rate and cost go in ARGV.

The script returns three integers: an allowed flag, the remaining tokens, and the milliseconds until the next token arrives. Redis truncates Lua floats to integers in replies, so floor these values deliberately instead of relying on that truncation.

Copyimport redis

TOKEN_BUCKET = """
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])  -- tokens per second
local cost     = tonumber(ARGV[3])
-- One clock for every replica: the Redis server's
local t   = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)  -- ms
local s      = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or capacity  -- missing key = full bucket
local ts     = tonumber(s[2]) or now
-- Refill for elapsed time, capped at capacity
tokens = math.min(capacity, tokens + math.max(0, now - ts) * rate / 1000)
local allowed, wait_ms = 0, 0
if tokens >= cost then
  tokens, allowed = tokens - cost, 1
else
  wait_ms = math.ceil((cost - tokens) / rate * 1000)  -- until this cost fits
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
-- Expire once the bucket would be full again; idle keys clean themselves up
redis.call('PEXPIRE', KEYS[1], math.ceil((capacity - tokens) / rate * 1000) + 1)
-- Floor explicitly instead of relying on Redis truncating Lua floats
return {allowed, math.floor(tokens), wait_ms}
"""

r = redis.Redis(host="redis.internal", port=6379)
bucket = r.register_script(TOKEN_BUCKET)

allowed, remaining, wait_ms = bucket(keys=["rl:{user:42}"], args=[100, 10, 1])
if allowed:
    print(f"allowed, {remaining} tokens left")
else:
    print(f"rejected, retry after {wait_ms} ms")  # e.g. set Retry-After

A Lua token-bucket script that reads, refills, decrements and sets a TTL atomically using the Redis server clock, called from Python via EVALSHA with an automatic NOSCRIPT fallback.

Cutting latency with local token leasing and failure fallbacks

Calling Redis on every request adds a network round trip to each request and makes Redis throughput the ceiling for your API. Leasing removes most of those calls. Each replica keeps a small in-memory counter. A request decrements that counter and proceeds without any network call. When the counter runs out, the replica calls the bucket script to claim a batch of N tokens and refills its counter from whatever the script grants. Give each lease a short TTL, such as one second, so unused tokens stop being spendable.

Batch size trades Redis load against accuracy. Leased tokens can be spent after the central bucket has refilled, so the worst-case burst can exceed the bucket by roughly the sum of all outstanding leases. Leases held by a replica that crashes are lost until they expire, and other replicas cannot use them in the meantime.

Illustrative estimate. Assume a quota of 1,000 req/s, 20 replicas and even traffic:

Fallbacks

When Redis is slow or unreachable, the limiter must pick a behavior:

• Fail-open keeps your service available but leaves downstream dependencies unprotected.
• Fail-closed protects downstream dependencies but makes Redis a single point of failure for your API.

Neither is usually right. Set a client timeout of a few milliseconds so a struggling Redis cannot stall requests. Then fall back to a local limit of the global quota divided by the current replica count.

That replica count lags during scaling events. If you scale from 10 to 20 replicas and each replica still believes there are 10, the fleet admits about twice the quota until the count refreshes.

Copyimport time
import redis

r = redis.Redis(host="redis.internal", port=6379,
                socket_timeout=0.005, socket_connect_timeout=0.005)
claim = r.register_script(open("bucket.lua").read())

GLOBAL_QUOTA = 1000  # req/s across the whole fleet
BATCH = 10           # larger = fewer Redis calls, more possible over-admission
LEASE_TTL = 1.0      # seconds before unused leased tokens stop being spendable

class LeasedLimiter:
    def __init__(self, key, replica_count):
        self.key = key
        self.replica_count = replica_count  # refreshed from discovery; lags during scaling
        self.tokens, self.expires = 0, 0.0
        self.window, self.used = 0, 0

    def allow(self):
        now = time.monotonic()
        if now >= self.expires:
            self.tokens = 0  # expired lease: drop leftover tokens
        if self.tokens == 0:  # only touch Redis when the local lease is empty
            try:
                self.tokens = int(claim(keys=[self.key], args=[BATCH]))
                self.expires = now + LEASE_TTL
            except redis.exceptions.RedisError:  # includes timeouts and connection errors
                return self._fallback(now)
        if self.tokens > 0:
            self.tokens -= 1  # served from memory, no network call
            return True
        return False

    def _fallback(self, now):
        # Conservative local limit: this replica's share of the global quota per second.
        if int(now) != self.window:
            self.window, self.used = int(now), 0
        self.used += 1
        return self.used <= GLOBAL_QUOTA // max(self.replica_count, 1)

A replica serves requests from an in-memory token lease, claims a new batch from the Redis bucket script only when the lease is empty or expired, and falls back to quota divided by replica count when Redis times out or is unreachable.

Scaling the store: Redis Cluster, hash tags, hot tenants and multiple regions

A shared store removes that dependency on replica count, but the store itself now has to scale. Redis Cluster splits the keyspace into 16,384 hash slots, computed as CRC16 of the key modulo 16,384. Each slot lives on one primary. A Lua script runs on a single node, so every key it touches must hash to the same slot, or the cluster rejects the call with a CROSSSLOT error. Hash tags guarantee this. When a key contains {...}, only the text inside the first pair of braces is hashed. That means rl:{tenant42}:tokens and rl:{tenant42}:ts always land on the same slot.

That guarantee also pins each tenant to one node. A tenant hot enough to saturate that node can be split into N sub-keys, such as {tenant42:0} through {tenant42:7}. Each sub-key holds 1/N of the quota, and a request picks one at random. This spreads the load, but the limit becomes approximate. One sub-key can run dry while the others still have tokens, so a request can be rejected even though the tenant is under its total quota.

Replication is asynchronous. If a primary fails before its replica receives recent DECRBY writes, the promoted replica holds a stale count and readmits those requests. The WAIT command narrows this window but does not close it. For most rate limiting, a brief over-admission after failover is acceptable.

Across regions, choose your trade-off:

Copyimport math, random, time
from redis.cluster import RedisCluster

LUA = """
local cap, rate, now, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])
local tokens = tonumber(redis.call('GET', KEYS[1])) or cap
local ts = tonumber(redis.call('GET', KEYS[2])) or now
tokens = math.min(cap, tokens + math.max(0, now - ts) * rate)
local ok = 0
if tokens >= cost then tokens = tokens - cost; ok = 1 end
local ttl = math.ceil(cap / rate) * 2
redis.call('SET', KEYS[1], tostring(tokens), 'EX', ttl)
redis.call('SET', KEYS[2], tostring(now), 'EX', ttl)
return ok
"""

rc = RedisCluster(host="redis-cluster.internal", port=6379)
bucket = rc.register_script(LUA)

SHARDS = 8  # sub-keys for a hot tenant; use 1 for normal tenants

def allow(tenant: str, capacity: float, refill_per_sec: float, cost: int = 1) -> bool:
    # Pick a random sub-bucket so a hot tenant's load spreads over up to SHARDS slots.
    shard = random.randrange(SHARDS)
    # Hash tag: only the text in {...} is hashed, so tokens and ts share a slot.
    tag = f"{{{tenant}:{shard}}}"
    keys = [f"rl:{tag}:tokens", f"rl:{tag}:ts"]
    # Each sub-bucket holds 1/SHARDS of the quota, so the overall limit is approximate:
    # one sub-bucket can be empty while others still have tokens.
    args = [capacity / SHARDS, refill_per_sec / SHARDS, time.time(), cost]
    return bucket(keys=keys, args=args) == 1

if __name__ == "__main__":
    print(allow("tenant42", capacity=800, refill_per_sec=400))

A Redis Cluster token bucket that uses a hash tag to keep both keys of each Lua call in one slot, and splits a hot tenant across eight sub-buckets at the cost of an approximate limit.

Alternatives to a shared quota store

A central store is not the only way to bound traffic across replicas. Each alternative gives up something different:

• Per-replica limits scaled by replica count. Set each replica's limit to the global quota divided by the number of replicas, refreshed from service discovery. There is no network dependency, but accuracy depends on even load distribution and an up-to-date replica count, both of which break down during scaling events and with sticky connections.
• Gateway or load balancer limiting. Enforce limits at the edge before requests reach your services. This works well for per-IP or per-API-key flood control. It usually cannot see application-level keys, such as which downstream dependency a request will hit, and it still needs shared state if the gateway itself runs multiple instances.
• Key-affinity routing. Route every request for a given key to the same replica using consistent hashing, so that replica's in-memory limiter is exact for that key. This removes the store from the request path, but rebalancing when replicas are added or removed moves keys and briefly resets their counters, and a hot key concentrates load on one replica.
• Concurrency limits and load shedding. Cap the number of in-flight requests per replica or reject work when latency rises. This protects your own service and downstream dependencies from overload, but it does not enforce a per-client quota, so it cannot meter paid tiers or guarantee fairness.
• Queue-based admission. Put work for a fixed-capacity dependency on a queue and drain it at a controlled rate. This smooths bursts without rejecting requests, at the cost of added latency and the need for asynchronous request handling.

Many systems combine these: coarse flood control at the gateway, concurrency limits for self-protection, and a shared quota only for limits that are contractual or protect a scarce dependency.

Client responses, observability, and the cost to build and run it

Telling clients what happened

Reject with HTTP 429 and a Retry-After header set to the seconds until enough tokens refill. The bucket script already knows the refill rate, so return that value instead of a fixed guess. A fixed guess makes every rejected client retry at the same moment. Also send remaining quota and reset time, for example in X-RateLimit-*-style headers or the IETF draft RateLimit fields. Well-behaved clients can then slow down before they are rejected.

Metrics that let you tune limits

Count decisions by outcome (allowed, rejected, fallback) and label each count with the limit key class, such as tenant tier or endpoint. Do not label by raw tenant ID, because that creates too many metric series. Record a histogram of store latency. The metrics answer specific tuning questions:

• Rejections concentrated in a few tenants: the limit is working as intended.
• Rejections spread across many tenants: the limit is set too low.
• Rising fallback counts: you are enforcing approximate local limits, not the global limit.

What it costs

Each check adds a store round trip. In fail-closed mode the limiter also caps your own availability.

Illustrative estimate (assumed numbers, not a benchmark):

service availability × store availability = combined availability

With an assumed 99.95% for the service and 99.9% for the store: 0.9995 × 0.999 ≈ 99.85%.

The store also needs its own alerts and runbooks, which adds to on-call work.

A shared library or sidecar pays these costs once. Without one, each team writes its own per-replica limiter and later debugs the same problem independently: quotas that silently change when the autoscaler changes the replica count.

Copyimport math
from prometheus_client import Counter, Histogram

DECISIONS = Counter("ratelimit_decisions_total", "Limiter decisions", ["outcome", "key_class"])
STORE_LATENCY = Histogram("ratelimit_store_latency_seconds", "Shared store round trip")

CAPACITY = 100        # bucket size (example value)
REFILL_PER_SEC = 10   # tokens added per second (example value)

class StoreUnavailable(Exception):
    """Raised by the store client on timeout or connection failure."""

def check(store, local_limiter, key, key_class, cost=1):
    try:
        with STORE_LATENCY.time():  # every check pays this round trip
            allowed, tokens = store.take(key, cost, CAPACITY, REFILL_PER_SEC)
        outcome = "allowed" if allowed else "rejected"
    except StoreUnavailable:
        # Fail open to an approximate per-replica limit; tracked separately.
        allowed, tokens = local_limiter.take(key, cost)
        outcome = "fallback"
    DECISIONS.labels(outcome=outcome, key_class=key_class).inc()

    headers = {
        "X-RateLimit-Limit": str(CAPACITY),
        "X-RateLimit-Remaining": str(max(0, int(tokens))),
        # Seconds until the bucket is full again.
        "X-RateLimit-Reset": str(math.ceil((CAPACITY - tokens) / REFILL_PER_SEC)),
    }
    if allowed:
        return 200, headers
    # Derive the wait from the refill rate instead of a fixed guess.
    wait = math.ceil((cost - tokens) / REFILL_PER_SEC)
    headers["Retry-After"] = str(max(1, wait))
    return 429, headers

A limiter check that records allowed, rejected and fallback decisions and store latency with prometheus_client, then returns 429 with a Retry-After value computed from the bucket's refill rate plus remaining-quota headers.

How a shared limiter saves engineering time

The savings come from solving the problem once instead of repeatedly, and from removing a class of incidents that are slow to diagnose:

• One implementation instead of many. A shared library or sidecar gives every team the same atomic script, fallback behavior, headers and metrics. Teams configure a key and a quota instead of writing and testing their own limiter.
• Limits that do not drift with scaling. Because the quota no longer depends on replica count, nobody has to recompute per-replica limits after changing autoscaler settings, and nobody spends an incident discovering that a customer received several times their contracted quota during a traffic spike.
• Faster diagnosis. Consistent decision metrics labelled by outcome and key class mean that "is this tenant being throttled, and why?" is answered from a dashboard rather than by reading each service's code and logs.
• Central configuration changes. Raising a tenant's quota or tightening a limit on a fragile dependency becomes a configuration change in one place, not a coordinated deploy across every service that calls it.
• Fewer client support questions. Accurate Retry-After and remaining-quota headers let client developers handle throttling themselves instead of filing tickets to ask why requests are failing.

These gains depend on the limiter being owned and operated well. If the store has no on-call owner, the time saved in application teams is spent instead on store incidents.

How OneEnv can help

Disclosure: OneEnv is the product behind this blog.

OneEnv (oneenv.io) is a workspace-based governance platform for the things services share — environment variables, database structure, API routes and validation rules. A change to a shared value is staged on a branch, reviewed once, and then every affected service explicitly approves or rejects it before it goes live, so you can see who a change touches before it ships instead of finding out in production.

Applied to distributed rate limiting microservices, this is where it helps:

Saves time

• Every service that inherits a shared value is listed in one place, so nobody searches repos and chats to find out who is affected.
• One review per branch replaces coordinating each team separately; each service still keeps its own approve/reject.
• Changing a shared variable is one edit and one review instead of editing every service's .env by hand.

Saves cost

• Fewer production incidents and rollbacks caused by a shared value, route or column changing under a consumer unannounced.
• Less duplicated configuration to maintain: one shared definition inherited by many services.
• A wrong or stale value is caught at review time by the services it affects, not by a failed deploy.
• OneEnv has a free plan (1 workspace, unlimited services and members, full governance), so trying it costs nothing.

These are qualitative benefits, not measured results — how much you save depends on how many services share the value.

Want to try it? Start at oneenv.io.