Rate Limits, Token Buckets, and Shared Counters

By the end of this lesson, you will be able to...

• Design a rate limit around a named caller, route class, burst allowance, and average rate.

• Trace a token bucket through concurrent requests and explain why its update needs shared authority.

• Choose a failure policy and signals that make a rejected request an honest system boundary rather than a mystery.

Idea in one sentence: A rate limit is a promise about who may use a constrained resource and how quickly; the counter that enforces it must make the same decision for every relevant request.

Core Insight

Atlas Shop opens its inventory-write API to a partner called Northwind. The normal workload is two updates per second, but a faulty integration retries a batch and sends 80 updates in a few seconds. The database is still available, but its write queue grows and the storefront begins to show old stock.

The tempting response is “reject requests after some number.” That is too vague to be a useful contract. Which requests share the number? Is a short burst allowed? Does a request to read inventory spend the same budget as a write? What happens when the component that holds the number is unavailable?

The stronger model is a rate-limit policy with four visible parts: an identity key, an algorithm, an authority for its state, and an outcome when the limit or its authority cannot answer. A token bucket is a common choice when a tenant may burst briefly but must settle to an average rate. It protects the path only when all instances consult compatible, atomically updated state.

The Promise We Need to Keep

Atlas does not want to punish Northwind for a short, legitimate catch-up burst. It does need to protect inventory writes from a broken client. Its initial contract is deliberately narrow:

The numbers are a teaching model, not a universal production setting. A capacity comes from the burst the downstream path can absorb; a refill rate comes from its sustainable work. A costly bulk endpoint may spend five tokens per call, while a cheap read may use a separate policy or no tenant limit at all.

The boundary matters more than the word bucket. An IP key is helpful for anonymous abuse. It is a poor substitute for a paid tenant quota behind a shared NAT. A global key protects one dependency but lets one noisy tenant spend everyone else's budget. Choose the key from the promise being kept.

The Naive Design: A Counter on Every Server

The first implementation is simple. Each API instance keeps northwind_writes_this_second in memory, rejects after 10, and resets it every second. It works on one server with steady traffic.

Now place three API instances behind a load balancer. Northwind sends 30 writes. If the load balancer spreads them evenly, each instance sees 10 and admits all 30. The intended tenant-wide limit was 10; the effective limit silently became roughly 30. A retry that lands on a different instance can bypass the local counter again.

This trace is evidence of the missing design boundary:

intended policy: 10 writes / second for tenant northwind

instance A sees 10 -> allows 10
instance B sees 10 -> allows 10
instance C sees 10 -> allows 10

tenant total: 30 allowed

Local limits still have a use. They can stop one process from spending all of its CPU, and they can act as a safety valve during an outage. They cannot by themselves enforce a tenant-wide promise across instances. For that promise, the decision state must be shared, or the architecture must explicitly accept approximation.

Why a Fixed Window Is Not the Same Promise

A shared fixed-window counter is the next reasonable design: increment tenant:northwind:12:00, then reject above a limit and let the key expire. It is cheap and often sufficient for a coarse protection boundary. Redis documents INCR plus expiration as a fixed-window rate-limiter pattern, and also notes that the increment-and-expiry sequence needs atomic handling to avoid a leaked counter when a client fails between operations. Redis INCR.

But a window has an edge. With a limit of 10 per minute, Northwind can send 10 writes at 12:00:59 and 10 more at 12:01:00. Each window says “10,” while the database receives 20 writes in two seconds. That may be fine for a monthly reporting API. It is a poor fit when the immediate burst is the thing that hurts the database.

Two alternatives clarify the choice:

No algorithm is “the accurate one” outside its contract. Atlas needs a bounded immediate burst and a steady write rate, so it chooses a token bucket. A fixed window would be a sensible situated preference if a brief boundary burst cannot harm the constrained resource and very cheap state matters more.

A Better Boundary: One Shared Token Decision

In plain English, a token bucket is a small store of permission slips. Quiet time adds slips up to a maximum. Each admitted write spends one. When no slip remains, the next write is rejected until time has added another.

In Atlas's policy, the state is {tokens, last_refill} for the key tenant:northwind:inventory-write. It is not a counter of completed database writes; it is an admission decision made before the write enters the protected path.

The technical requirement is an atomic read-refill-spend-update operation. If two API processes both read one remaining token, both must not independently decide to spend it. A shared store can supply that authority, but only if the whole transition runs as one operation. Redis's token-bucket example uses a script to fetch state, calculate refill, consume if available, and store the resulting state atomically; without that, concurrent callers can double-spend a token or overwrite each other's update. Redis token bucket.

Here is Atlas's illustrative trace. It uses whole-token refill for clarity; a production implementation may use finer time units or fractional tokens.

The bucket allows a burst because it had saved unused capacity. It does not create database capacity. If the write queue can safely absorb only five concurrent writes, Atlas may need a lower capacity, a concurrency limit, or a queue as well. Rate limiting controls admission over time; it is not a substitute for every downstream control.

The Trade-off: Fairness Needs Scope, and Scope Needs State

The design trade-off is fairness and downstream protection versus precision, storage cost, and an extra dependency on the request path.

A tenant-wide shared bucket gives each tenant a consistent budget across API instances. It adds a synchronous shared-state lookup. A per-route bucket avoids one expensive endpoint consuming the budget for cheap calls, but creates more keys and policy surface. A global bucket can preserve a fragile third-party quota, but it is deliberately less fair: unrelated tenants now compete.

Layering limits is often clearer than pretending one key is enough:

global inventory writes      -> protect the database as a whole
tenant inventory writes     -> stop one tenant dominating that capacity
route or cost-class limit   -> account for unusually expensive work
local concurrency limit     -> stop one API process from becoming unhealthy

Each layer must say what it owns. Do not add four opaque 429s and call that defense in depth. Record which policy rejected the request, which key was charged, the configured capacity and refill, and a safe retry time when it can be estimated.

When the Shared Counter Is Unavailable

The counter store is now on the admission path. A network timeout means Atlas cannot know whether the tenant has budget. There is no failure-neutral default.

For inventory writes that could overload a fragile database, Atlas chooses to fail closed: return a controlled temporary error rather than admit unlimited work. That preference protects the scarce downstream resource, but lowers availability while the limiter is impaired. For a public product read, Atlas might fail open with a tight local emergency limit and an alert, because falsely rejecting every reader can be worse than admitting a bounded excess. Neither choice preserves a strict global quota during the outage.

Another boundary is identity. If an API key is shared by several real customers, a per-key limit is fair only to the key, not to each customer. If an attacker can cheaply rotate keys, a key-only limit does not control abuse. Identity, authentication, and billing rules determine whether the counter key matches the fairness claim.

Operational Consequences

The status code is not the whole interface. A good rejection tells a well-behaved client what happened and whether retrying later is useful. Standard HTTP rate-limit fields are defined for communicating quota information; use headers and a response body consistently with the actual policy rather than inventing a reset time the counter cannot justify. RFC 9333.

Watch the decision, the pressure, and the correctness boundary:

An increase in 429s is not automatically success or failure. If downstream write latency and queue depth fall while one faulty tenant is rejected, the limit may be working. If normal tenants see rejections while the database remains idle, the key, capacity, or refill rate is likely wrong. Look at both sides of the boundary.

Design Review

Check: Northwind has a capacity of 20 and refills two whole tokens per second. It has been idle long enough to fill the bucket. It sends 18 writes at once, then four more after one second. How many of the second group can the bucket admit?

Think first, then reveal.

Answer: The first group leaves two tokens. One second adds two, so four tokens are available. All four of the second group can be admitted. The answer changes if the policy also has a lower concurrency limit or if a request costs more than one token; a bucket is only one named admission rule.

Now review this proposal: “Use an in-memory fixed-window counter per server, keyed only by source IP, fail open if it overflows, and return a generic 500 on rejection.” It is small, but it does not keep Atlas's tenant-wide inventory-write promise. Different instances create separate budgets, a shared NAT can combine tenants, fail-open behavior is unspecified for the counter-store case, and 500 tells a client that the server failed rather than that a policy denied admission.

Practice: Design One Honest Limit

A document-export endpoint triggers expensive rendering. A customer may submit a short batch, but sustained requests saturate the renderer. The service runs on six instances. Design a policy with a key, algorithm, capacity, refill rate, authority, denial response, and counter-outage behavior. Say which signal would cause you to revise the policy.

A good answer should mention:

• a key based on the customer or authenticated tenant and the expensive export route, rather than only the instance or IP;
• a burst capacity and refill rate derived from renderer tolerance, clearly labeled as chosen assumptions;
• a shared, atomic decision if the promise is customer-wide across six instances;
• a 429 or another explicit admission response with retry guidance when the bucket is empty;
• an intentional fail-open or fail-closed choice for the counter outage, including what protection or availability it sacrifices; and
• a paired signal such as rejected exports plus renderer queue depth or render latency, not only the count of 429s.

Connections

Request coalescing prevented equivalent cache misses from multiplying one refill. A rate limit decides earlier whether a request may consume the constrained path at all. The next lesson moves to asynchronous work, where retries must preserve useful effort without multiplying a side effect.

Resources

• [DOCS] Redis rate limiter — Focus: Compare shared keys, fixed windows, sliding windows, token buckets, and atomic read-decide-update state.
• [DOCS] Token bucket rate limiter with Redis — Focus: Trace capacity, refill, consumption, and why concurrent requests need one atomic state transition.
• [STANDARD] RFC 9333: RateLimit Fields for HTTP — Focus: Separate the admission decision from how an HTTP API communicates quota and retry information.

Key Takeaways

• A rate limit begins with a promise: name the caller, protected work, burst, sustained rate, and denial outcome.
• A local counter can protect one process, but it cannot enforce a tenant-wide budget across load-balanced instances.
• Token buckets make burst capacity and average rate explicit; their shared state must update atomically to avoid double-spending permission.
• Fixed windows, sliding windows, and buckets encode different promises. Choose the one whose boundary matches the resource you need to protect.
• The limiter's own outage policy, identity key, downstream signals, and rejection interface are part of the design—not details to postpone.